Method and system for a local and fast non-disruptive path switching in high speed packet switching networks

• US 7,593,321 B2
• Filed: 08/04/2003
• Issued: 09/22/2009
• Est. Priority Date: 02/11/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Fichou, Aline, Bertin, Olivier, Galand, Claude, Maurel, Olivier, Nicolas, Laurent
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): Chery; Dady
• Application Number:
  US10/634,060
• Publication Number:
  US 20040042402A1
• Time in Patent Office: 2,241 Days
• Field of Search: 370/228, 370/225, 370/238, 370/248, 370/229, 370216-218, 370/221, 370/227, 370/392, 370254-256, 370/400, 370/406, 370/409, 370/410, 709239-244, 340/825.01
• US Class Current: 370/218
• CPC Class Codes: H04L 1/22 using redundant apparatus to increase reliability
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A method for operating a node in a computer network is disclosed, where the network is made up of nodes connected by links. The method has the steps: determining an alternate path for one or more links; reserving resources for the alternate path; and rerouting traffic on the alternate path in case of a link failure. The alternate path may be periodically updated. A plurality of alternate paths may be maintained. The alternate paths may not have any links in common. User traffic may be rerouted substantially simultaneously to each link of the alternate path in the event of failure of a primary path.

Claims

1. A method for operating a node in a computer network, the node connected to other nodes by links, comprising:

determining a path to a destination, the path including one or more links;

determining at least one alternate path having at least some of its one or more links differing from the links of the path;

reserving bandwidth for said at least one alternate path by sending one or more set-up request messages;

enabling said at least one alternate path at one or more other nodes along said at least one alternate path, but not enabling said at least one alternate path at the node, wherein the node is a head node of said at least one alternate path;

subsequent to reserving bandwidth and enabling, detecting a link failure on the path; and

rerouting traffic on said at least one alternate path in case of a link failure by enabling said at least one alternate path in the node, and absent sending any additional set-up messages to the one or more other nodes along said at least one alternate path.

2. The method as in claim 1, further comprising:

periodically updating said at least one alternate path.

3. The method as in claim 1, further comprising:

determining a plurality of alternate paths for the path, and said plurality of alternate paths do not have any link in common.

4. The method as in claim 1, further comprising:

rerouting user traffic substantially simultaneously to each link of said at least one alternate path.

5. The method as in claim 1, further comprising:

reserving bandwidth on said at least one alternate path for switching real-time connections first.

6. The method as in claim 1, further comprising:

sending one or more set-up request messages to one or more nodes associated with each of the one or more alternate paths, to allocate a connection along each of the one or more alternate paths;

maintaining the connection along each of the one or more alternate paths in a standby mode; and

in response to a link failure on the path, activating the connection along at least one of the one or more alternate paths.

7. A node in a computer network connected by links, said node comprising:

means for determining a path to a destination, the path including one or more links;

means for determining at least one alternate path having at least some of its one or more links differing from the links of the path;

means for reserving bandwidth for said at least one alternate path prior to detecting a link failure on the path by sending one or more set-up request messages;

means for enabling said at least one alternate path at one or more other nodes along said at least one alternate path, but not enabling said at least one alternate path at the node, wherein the node is a head node of said at least one alternate path; and

means for rerouting traffic on said at least one alternate path in case of a link failure by enabling said at least one alternate path in the node, and absent sending any additional set-up messages to the one or more other nodes along said at least one alternate path.

8. The node as in claim 7, further comprising:

means for periodically updating said at least one alternate path.

9. The node as in claim 7, further comprising:

means for determining a plurality of alternate paths for the path, and said plurality of alternate paths do not have any link in common.

10. The node as in claim 7, further comprising:

means for rerouting user traffic substantially simultaneously to each link of said at least one alternate path.

11. The node as in claim 7, further comprising:

means for reserving bandwidth on said at least one alternate path for switching real-time connections first.

12. A node in a computer network connected by links, said node comprising:

a transit connection manager (TCM) adapted to

set up transit connections for a path,

update routing tables,

route traffic; and

an alternate path manager adapted to

determine at least one alternate path for use in case of failure of a link of the path,

allocate connections on said at least one alternate path prior to a link failure on the path,

reserve bandwidth on said at least one alternate path prior to a link failure on the path by sending one or more set-up request messages,

cause one or more other nodes along said at least one alternate path to enable said at least one alternate path,

cause the node to not enable said at least one alternate path, wherein the node is a head node of said at least one alternate path.

request to said TCM the rerouting of traffic on said at least one alternate path in case of a link failure by enabling said at least one alternate path in the node, and absent sending any additional set-up messages to said one or more other nodes along said at least one alternate path.

13. The node according to claim 12, further comprising:

said at least one alternate path is a plurality of alternate paths that each include one or more links and the plurality of alternate paths do not have any link in common.

14. The node according to claim 12, further comprising:

said alternate path manager adapted to reroute user traffic to each link of said at least one alternate path.

15. The node according to claim 12, further comprising:

said alternate path manager adapted to reserve bandwidth on said at least one alternate path for making real-time connections first.

16. The node as in claim 12, wherein the TCM is configured to allocate connections by transmission of one or more set-up request messages to one or more nodes associated with each of the one or more alternate paths, to maintain a connection along each of the one or more alternate paths in a standby mode, and to activate the connection along at least one of the one or more alternate paths in response to a link failure.

17. A method of non-disruptive packet switching in a network having nodes interconnected with transmission trunks, said method comprising:

pre-selecting at least on alternate path for each trunk;

reserving connections at each node to make said at least one alternate path;

reserving bandwidth resources to transmit packets on said at least one alternate path by sending one or more set-up request messages;

enabling said at least one alternate path at one or more nodes along said at least one alternate path, but not enabling said at least one alternate path at a head node of said at least one alternate path;

subsequent to the reserving connections and reserving resources and enabling, detecting a failure of a particular trunk; and

switching the path of a packet from said particular trunk, in response to failure of said particular trunk, to said at least one alternate path by enabling said at least one alternate path in the head node, and absent sending any additional set-up messages to said one or more nodes along said at least one alternate path.

18. The method according to claim 17 further comprising:

said at least one pre-selected alternate path is a plurality of alternate paths that each include one or more trunks, and the plurality of paths do not have any trunk in common.

19. The method according to claim 17 further comprising:

rerouting user traffic to each trunk of said at least one alternate path.

20. The method according to claim 17 further comprising:

reserving resources on said at least one alternate path for making a real-time connection first.

21. A method comprising:

determining a path to a destination, the path including one or more links;

determining at least one alternate path having at least some of its one or more links differing from the links of the path;

sending one or more setup request messages along the at least one alternate path to request one or more nodes along the path reserve resources for, and enable, the at least one alternate path;

reserving resources for, but not enabling, the at least one alternate path at a head node of the at least one alternate path;

subsequent to steps of sending and reserving, detecting a link failure on the path; and

rerouting traffic on the at least one alternate path in case of a link failure by enabling the at least one alternate path in the head node, absent sending additional set-up messages to one or more nodes along the at least one alternate path.

22. The method as in claim 21 wherein the resources include bandwidth for passing traffic, and the one or more set-up request messages request the one or more nodes reserve bandwidth for the alternate path.

23. The method as in claim 21 further comprising:

periodically updating the at least one alternate path in response to changes in available bandwidth.

24. The method as in claim 21 wherein the least one alternate path is a plurality of alternate paths that do not have any links in common.

25. An apparatus comprising:

a plurality of ports;

a route controller configured to determine a path to a destination via one of the plurality of ports, the path including one or more links; and

an alternate path manager (AMP) configured to,

determine at least one alternate path via one of the plurality of ports, the at least one alternate path having at least some links that differ from the links of the path,

send one or more set-up request messages along the at least one alternate path to request one or more nodes along the path reserve resources for, and enable, the at least one alternate path,

reserve resources for, but not enable, the at least one alternate path at the apparatus, wherein the apparatus is a head of the at least one alternate path;

detect a link failure on the path, and

reroute traffic on the at least one alternate path in case of a link failure by enabling the at least one alternate path in the apparatus, absent a send of additional set-up messages to one or more nodes along the at least one alternate path.

26. The apparatus as in claim 25 wherein the resources include bandwidth for passing traffic, and the one or more set-up request messages request the one or more nodes reserve bandwidth for the alternate path.

27. The apparatus of claim 25 wherein the AMP is further configured to periodically update the at least one alternate path in response to changes in available bandwidth.

28. The apparatus of claim 25 wherein the least one alternate path is a plurality of alternate paths that do not have any links in common.

29. An apparatus comprising:

means for determining a path to a destination, the path including one or more links;

means for determining at least one alternate path, the at least one alternate path having at least some links that differ from the links of the path;

means for sending one or more set-up request messages along the at least one alternate path to request one or more nodes along the path reserve resources for, and enable, the at least one alternate path;

means for reserving resources for, but not enabling, the at least one alternate path at the apparatus, wherein the apparatus is a head of the at least one alternate path;

means for detecting a link failure on the path; and

means for rerouting traffic on the at least one alternate path in case of a link failure by enabling the at least one alternate path in the apparatus, absent sending additional set-up messages to one or more nodes along the at least one alternate path.