Distributed connection establishment and restoration
View Patent ↗Connection constraints are flooded using an extension to a routing protocol being used to control forwarding on network. Nodes maintain topology and connection database and calculate routes for connections based on the constraints. If a node is on a calculated route for a connection it will install forwarding state for the connection. Since each node has a consistent view of the network topology and has been provided with the constraints associated with the connection, each node on the network will calculate the same route for the connection. When a failure occurs, the nodes will calculate restoration paths for the connections on a network-wide priority basis to enable restoration paths to be created for the affected connections without requiring the restoration paths to be signaled. Time-stamps are used to allow events to be applied by nodes in a consistent order regardless of the order in which they arrive.
1. A method of distributed connection establishment in a network, the method comprising:
maintaining consistent views of network topology by a plurality of nodes on the network;
advertising, by a head-end node of the plurality of nodes, in order to establish a new connection, constraints associated with the new connection to the plurality of nodes;
calculating, by each node of the plurality of nodes on the network, a route identifying the head-end node, at least one intermediate node of the plurality of nodes, and a destination node of the plurality of nodes for the new connection based on the constraints; and
installing a forwarding state for the new connection by each node on the calculated route, wherein installing the forwarding state for the new connection by each node on the calculated route comprises, for each node of the plurality of nodes:
determining by the each node whether the each node is on the calculated route;
if the each node is on the calculated route, installing on the each node the forwarding state for the new connection; and
if the each node is not on the calculated route, not installing on the each node the forwarding state for the new connection.
2. The method of claim 1 , wherein the network is a link state protocol controlled Ethernet network.
3. The method of claim 1 , wherein the plurality of nodes maintains a connection database containing entries defining a plurality of connections that have been established on the network and a corresponding route for each of the plurality of connections.
4. The method of claim 1 , wherein the constraints identify at least the head-end node, the destination node, an indication of the bandwidth associated with the new connection, and a priority indication for the new connection.
5. The method of claim 4 , further comprising calculating a plurality of routes, each route corresponding to a different connection, in priority order.
6. The method of claim 1 , wherein each node of the plurality of nodes maintains both a current view of the network topology having a first timestamp, an earlier view of the network topology having a second timestamp, and a list of time-stamped events that have occurred between a time associated with the earlier view of the network topology and a time associated with the current view of the network topology.
7. The method of claim 6 , further comprising receiving an event notification containing a third timestamp.
8. The method of claim 7 , wherein the event notification relates to at least one of addition of a new node or link on the network, deletion of a node or link on the network, a connection addition, a connection deletion, a failure of a node or link on the network, and a recovery of a previously failed node or link on the network.
9. The method of claim 7 , further comprising comparing the third timestamp of the event notification with the first timestamp of the current view of the network topology.
10. The method of claim 9 , further comprising applying the event notification to the current view of the network topology if the third timestamp of the event notification is after the first timestamp of the current view of the network topology.
11. The method of claim 9 , further comprising reverting to the earlier view of the network topology if the third timestamp of the event notification is before the first timestamp of the current view of the network topology, and re-applying events from the list of time-stamped events along with the event notification.
12. A method of selectively installing a forwarding state by a node of a plurality of nodes on a link state protocol controlled Ethernet network, the method comprising:
receiving, by the node from a head-end node, a link state protocol control message containing constraint information associated with a new connection to be established on the link state protocol controlled Ethernet network;
calculating, by the node, a route for the new connection based on the constraint information and a view of a network topology of the link state protocol controlled Ethernet network, the route identifying the head-end node, at least one intermediate node of the plurality of nodes, and a destination node of the plurality of nodes for the new connection;
updating, by the node, the view of the network topology to reflect the new connection on the calculated route;
installing the forwarding state for the new connection, by the node, based on the determination, wherein installing the forwarding state for the new connection by each node on the calculated route comprises, for each node of the plurality of nodes:
determining by the each node whether the each node is on the calculated route;
if the each node is on the calculated route, installing on the each node the forwarding state for the new connection; and
if the each node is not on the calculated route, not installing on the each node the forwarding state for the new connection.
13. The method of claim 12 , further comprising:
maintaining a connection database by the node, the connection database containing entries associated with connections that have been established on the link state protocol controlled Ethernet network, the entries containing at least the constraint information associated with the connections.
14. The method of claim 13 , wherein the connection database maintains the connections in priority order.
15. The method of claim 14 , further comprising:
receiving a fault notification indicating an occurrence of a fault on the link state protocol controlled Ethernet network;
updating the view of the network topology to reflect the fault;
determining, from the connection database, which connections are affected by the fault; and
calculating restoration routes for the affected connections in order of priority.
16. The method of claim 15 , wherein calculating restoration routes for the affected connections comprises retrieving the constraint information associated with the connections and processing the constraint information against the view of the network topology to determine a restoration route for the connections.
17. The method of claim 16 , wherein calculating restoration routes for the affected connections comprises:
returning bandwidth associated with the affected connections back to a network topology database;
selecting a highest priority connection;
determining a restoration route for the highest priority connection;
allocating bandwidth for the highest priority connection from the network topology database; and
selectively installing the forwarding state, by the node, if the node is on the restoration route for the highest priority connection;
iterating the steps of selecting, determining, allocating, and selectively installing for the remaining connections in priority order.