Source-implemented constraint based routing with source routed protocol data units
View Patent ↗Source-implemented constraint-based routing with source routing enables traffic engineering to be performed and reservations to be made within a domain without requiring constraint information and reservation information to be disseminated to all nodes in the domain. In one embodiment, a focal node maintains a table containing metrics of links and connection reservations through the domain. When a connection is to be added, the focal node determines a path, given the constraints reflected in the table, and allocates resources on the links forming the path. The table is updated, and the path is used to generate headers for traffic associated with the connection. Traffic from the nodes toward the focal point follow the reverse path. If a node or link fails, connections carried through the failure are identified, reservations on links associated with the connections are released, and new reservations are made taking into account the new network topology.
1. A method of performing constraint based routing on a communication network, the method comprising the steps of:
obtaining information relating to a topology of the communication network by at least one focal node on the communication network;
maintaining a constraint table by the focal node, the constraint table containing metrics of links and connection reservations through the communication network;
using the constraint table by the focal node to determine a plurality of traffic engineered paths for a plurality of connections to be implemented on the communication network, each of the plurality of traffic engineered paths extending between the focal node and other nodes on the communication network; and
causing all traffic subject to traffic engineering to pass through the focal node prior to being passed onto the communication network, to enable the focal node to add source routing information to the traffic subject to traffic engineering before passing the traffic subject to traffic engineering onto the communication network so that the focal node can cause the traffic subject to traffic engineering to follow the determined plurality of traffic engineered paths on the communication network without requiring dissemination of path reservations for the traffic engineered paths on the communication network.
2. The method of claim 1 , further comprising the steps of receiving indications of a failure on the communication network, and updating the constraint table.
3. The method of claim 2 , wherein the step of updating the constraint table comprises releasing resources allocated to connections established on traffic engineered paths that pass through the failure, and reallocating resources for the connections on new traffic engineered paths through the communication network.
4. The method of claim 1 , wherein the step of maintaining a constraint table further comprises maintaining alternative traffic engineered paths for use by connections in the event of one or more failures on the communication network.
5. The method of claim 1 , wherein the source routed protocol data units contain a hop list of nodes on the communication network.
6. The method of claim 5 , wherein the hop list contains a list of node IDs.
7. The method of claim 5 , wherein the hop list contains a list of next hops.
8. The method of claim 1 , wherein each of the source routed protocol data units contains a list of hops or links defining the traffic engineered path through the network for the connection from the focal node to a target node.
9. The method of claim 8 , wherein an inverse of the list of hops or links may be used by the target node as a route to the focal node.
10. A focal node, comprising:
a processor comprising control logic configured to compute traffic engineered routes by maintaining a constraint table reflecting connections on a domain, making constraint based routing decisions on behalf of nodes on the domain, and making reservations for connections on the domain by updating the constraint table with metric reservation information for the connections without signaling the reservations for the connections on the domain, the domain comprising a group of network nodes configured to communicate on traffic engineered routes that pass through the focal node; and
a routing module implemented by the focal node and configured to generate source route headers for application to packets for transmission of the packets over the computed traffic engineered routes on the domain, such that all traffic subject to traffic engineering which is intended to be transmitted to one or more of the group of network nodes on the domain passes through the focal node and receives a source route header corresponding to a respective traffic engineered route prior to being transmitted onto the domain so that the traffic subject to traffic engineering will be transmitted over the traffic engineered routes computed by the focal node.
11. The focal node of claim 10 , wherein the control logic is further configured to release metric reservations for connections affected by a failure on the domain by updating the constraint table.
12. The focal node of claim 11 , wherein the control logic is further configured to reestablish the connections affected by the failure on the domain by making new constraint based routing decisions for the connections affected by the failure.
13. The focal node of claim 12 , wherein the new constraint based routing decisions are made before the failure.
14. The focal node of claim 10 , further comprising a plurality of network ports configured to interface links on the network and a switch fabric configured to interconnect the network ports under the control of the processor.
15. The focal node of claim 10 , further comprising at least one wireless network port.
16. The focal node of claim 10 , further comprising a security module, said security module configured to perform authentication, authorization, and accounting processes for the focal node.