Constraint route dissemination using distributed route exchanges

1. A method of establishing explicit constrained edge-to-edge paths in a one of an Internet Protocol (IP), MPLS and Optical network that uses a modified open shortest path first (OSPF) routing protocol for constraint route distribution and path computation, comprising steps of:

provisioning at least one OSPF router in the network that supports constraint path setup with traffic engineering route exchange router (TE-X) functionality to provide edge routers in the network with access to explicit constraint routes;

sending traffic engineering link state advertisement (TE-LSA) messages directly via unicast from the OSPF routers to only a nearest one of the at least one TE-X, without flooding the TE-LSAs to other routers in the network, to permit each of the at least one TE-X to maintain a traffic engineering link-state database (TE-LSDB) to compute constraint-based traffic engineering routes; and

querying the nearest one of the at least one TE-X to obtain an explicit edge-to-edge path satisfying specified traffic engineering (TE) constraints.

2. The method as claimed in claim 1 wherein the step of querying is performed by a first edge router in the network.

3. The method as claimed in claim 1 further comprising a step of discovering the nearest one of the at least one TE-X via normal OSPF Router Link-State Advertisement messages.

4. The method as claimed in claim 3 further comprising a step of compiling and storing a list of all TE-Xs in a routing area and using the list to select a nearest TE-X based on a route cost factor associated with a shortest path route to respective TE-Xs in the list.

5. A method as claimed in claim 1 further comprising a step of discovering peer TE-Xs in the network by learning at each TE-X of other TE-Xs using normal OSPF Router Link-State Advertisement messages (Router LSAs), and storing a list of other TE-Xs discovered in the network.

6. A method as claimed in claim 5 further comprising a step of sending one of a Hello and Keep-Alive message directly via unicast to each other TE-X discovered in the network.

7. The method as claimed in claim 6 further comprising a step of sending tic engineering link states from each of the at least one TE-X to each other TE-X discovered in the network using a bi-directional communications connection set up with each other TE-X, in order to synchronize the TE-LSDBs.

8. The method as claimed in claim 1 wherein each of the at least one TE-X advertises its capability as a TE-X using a TE-bit in an Options field of Router Link-State Advertisement (Router LSA) messages.

9. The method as claimed in claim 1 further comprising a step of sending resources reserved (RR) TE-LSAs from the TE-X directly to peer TE-Xs in the network using a bi-directional communications connection set up with each peer TE-X to advise the peer TE-Xs of resources reserved when an explicit constrained path is established.

10. The method as claimed in claim 9 further comprising a step of sending a release explicit route message from an OSPF router that requested an explicit constrained path directly via unicast to the nearest TE-X, after the explicit constrained path is released, to permit the TE-X to flush RR TE LSAs related to the explicit constrained path that was released.

11. The method as claimed in claim 10 further comprising a step of sending resource reserved (RR) TE-LSAs from the TE-X to peer TE-Xs using a bi-directional communications connection set up with each peer TE-X in the network to permit the peer TE-Xs to flush the RR TE-LSAs related to the explicit constrained path that was released.

12. The method as claimed in claim 1 wherein the TE-LSAs include type, length, value (TLV) fields to define router addresses and link states.

13. The method as claimed in claim 12 wherein the TE-LSAs further include sub-TLV fields.

14. The method as claimed in claim 12 wherein the sub-TLV is a VPN sub-TLV used to indicate to other nodes in the network the VPN Identifier (VPN ID) that is associated with a router.

15. The method as claimed in claim 13 wherein the sub-TLV is a Replicating Capable sub-TLV used to indicate to other nodes that a router is capable of replicating data to more than one end point.

16. A traffic engineering route exchange router (TE-X) in a network that uses an open shortest path first (OSPF) routing protocol, comprising:

a) a traffic engineering link-state data base (TE-LSDB) compiled using traffic engineering link-state advertisement (TE-LSA) messages received directly via unicast from OSPF routers in the network, each TE-X in the network receiving the TE-LSAs only from OSPF routers that have determined that the TE-X is a nearest one of the TE-Xs in the network and computing explicit edge-to-edge constraint-based routers through the network using the TE-LSDB;

b) a messaging system for exchanging TE-LSA messages with peer TE-Xs in the network using a bi-directional communications connection set up with each peer TE-X; and

c) a modified OSPF routing protocol for constraint route distribution and constraint path computation.

17. The TE-X as claimed in claim 16 wherein the TE-X is an area border router (ABR).

18. The TE-X as claimed in claim 17 wherein the ABR exchanges summary TE-LSAs with peer TE-Xs in other routing areas to provide information respecting paths across the other routing areas, and available resources associated with the paths.

19. The TE-X as claimed in claim 16 wherein on initialization the TE-X advertises its presence in the network using router link-state advertisement (Router LSA) messages.

20. The TE-X as claimed in claim 16 wherein a TE-bit is set in the Router LSA messages to advertise other routers in the network that the TE-X has traffic engineering route exchange capability.

21. The TE-X as claimed in claim 16 wherein the TE-X discovers peer TE-Xs in the network.

22. The TE-X as claimed in claim 21 wherein the TE-X discovers peer TE-Xs in the network by exchanging normal OSPF routing information with other routers in the network and creating adjacencies with neighbors in the network.

23. The TE-X as claimed in claim 22 wherein the TE-X further derives and stores a list of peer TE-Xs in the network using a downloaded domain link-state database.

24. The TE-X as claimed in claim 23 wherein the TE-X further sends one of Hello and Keep-Alive messages directly via unicast to the other TE-Xs in the list, in order to discover a designated TE-X and a backup designated TE-X in the network.

25. A TE-X as claimed in claim 24 wherein the TE-X exchanges TE-LSA messages with the designated TE-X after peering with the designated TE-X, to obtain all current TE-LSAs for the network, and stores the TE-LSAs in the TE-LSDB.

26. A TE-X as claimed in claim 25 wherein the TE-X flushes from the TE-LSDB obsolete TE-LSAs when more current TE-LSAs are received from an OSPF router in the network, which originated the TE-LSA.

27. A TE-X as claimed in claim 26 wherein the TE-X updates the TE-LSDB when the information respecting the explicit route is sent to the first OSPF edge router.

28. A TE-X as claimed in claim 16 wherein the TE-X:

a) accepts queries from a first OSPF edge router for an explicit route between the first OSPF edge router and a second OSPF edge router in the network;

b) computes the explicit route using information stored in the TE-LSDB; and

c) sends information relating to the explicit route to the first OSPF edge router.

29. A method of reducing traffic engineering messaging loads in an OSPF network, comprising steps of:

configuring at least one OSPF router that supports constraint path setup in the OSPF network as a traffic engineering route exchange router (TE-X) to provide edge routers in the network with access to explicit constraint routes;

provisioning the at least one TE-X to advertise to other OSPF routers in the network—; and

provisioning the other OSPF routers in the network to send traffic engineering link state advertisement (TE-LSA) messages directly via unicast to only a nearest one of the at least one TE-X, and to query only the nearest one of the at least one TE-X for an explicit constraint route to an edge router in the network to obtain an explicit edge-to-edge path satisfying specified traffic engineering constraints.

30. The method as claimed in claim 29 further comprising a step of enabling the at least one TE-X to build a traffic engineering link-state database (TE-LSDB) using the TE-LSA messages sent directly via unicast from the OSPE routers in the network, and further enabling the TE-X to use the TE-LSDB for computing the explicit route.

31. The method as claimed in claim 30 further comprising a step of enabling the at least one TE-X to send copies of the TE-LSA messages directly using a bi-directional communications connection set up with each peer TE-X in the OSPF network, and to receive TE LSA messages directly using a bi-directional communications connection set up with each peer TE-X in the OSPF network.

32. The method as claimed in claim 31 further comprising a step of enabling the at least one TE-X to flush outdated TE-LSAs from the TE-LSDB when a more current TE-LSA is received.

33. The method as claimed in claim 29 further comprising steps of:

enabling the other OSPF routers in the network to compile a list of the at least one TE-X in the network using network routing information; and

to select the nearest TE-X based on a least cost route of respective routes to respective ones of the at least one TE-X.

34. The method as claimed in claim 33 further comprising a step of enabling the other OSPF routers in the network to select a nearest TE-X by sending a probe message to the at least one TE-X in an order of least cost route until a one of the at least one TE-X acknowledges the probe message, thereby accepting to serve as nearest TE-X to the other OSPF router sending the probe message.

35. The method as claimed in claim 34 further comprising a step of enabling the other OSPF routers in the network to select a backup TE-X by sending a probe message to TE-Xs remaining after selecting the nearest TE-X in an order of least cost route until a one of the remaining TE-Xs acknowledges the probe message, thereby accepting to serve as backup TE-X to the other OSPF router sending the probe message.

36. The method as claimed in claim 29 further comprising a step of enabling the at least one TE-X to advertise to other OSPF routers in the network using a TE-bit in an Option field of an OSPF Router LSA message.

37. A data network that uses an open shortest path first (OSPF) routing protocol, comprising:

a) a plurality of OSPF routers, at least one of the OSPF routers that supports constraint path set up being provisioned to function as a traffic engineering route exchange router (TE X) to provide edge routers in the network with explicit constraint routes; and

b) a remainder of the routers being provisioned to send traffic engineering link-state advertisement (TE-LSA) messages directly via unicast to only a nearest one of the at least one TE-X, to enable the nearest TE-X to maintain a traffic engineering link-state database (TE-LSDB) for computing explicit constraint-based traffic engineering routes between edge routers in the data network.

38. A data network as claimed in claim 37 wherein the nearest TE-X is further adapted to send a copy of each TE-LSA received from the other OSPF routers in the data network directly using a bi-directional communications connection set up with each peer TE-X in the data network.

39. A data network as claimed in claim 38 wherein the other routers in the data network query the nearest one of the at least one TE-X to obtain an explicit route to another router in the data network.

40. A data network as claimed in claim 37 wherein the nearest TE-X is an area border router (ABR) in a routing area of the data network.

41. A data network as claimed in claim 40 wherein the ASBR peers with TE-Xs in other routing areas of the data network to which the ASBR is connected.

42. A data network as claimed in claim 37 wherein the nearest TE-X is an autonomous system border router (ASBR) in an autonomous system of the data network.

43. A data network as claimed in claim 42 wherein the ASBR peers with TE-Xs in other autonomous systems and other routing areas of the data network to which the ASBR is connected.

44. A data network as claimed in claim 37 wherein the data network is one of an Internet Protocol (IP), Multi-protocol Label Switched (MPLS), and Optical network.