Multiple path routing

• US 6,347,078 B1
• Filed: 08/11/1998
• Issued: 02/12/2002
• Est. Priority Date: 09/02/1997
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Tzeng, Hong-Yi, Siu, Kai-Yeung, Narvaez-Guarnieri, Paolo
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Qureshi, Afsar M.
• Application Number:
  US09/132,032
• Time in Patent Office: 1,281 Days
• Field of Search: 370/230, 370/231, 370/235, 370/238, 370/252, 370/389, 370/400, 370/248, 370/406, 370/232, 709/238, 709/239, 709/241, 709/105
• US Class Current: 370/230
• 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/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic

Abstract

A novel data structure in a router helps to compute viable next hops for forwarding a data packet from a router to its destination along multiple alternate loop-free paths, which are not necessarily of shortest distance. Each viable next hop may also be specified with a degree of optimality, which enables a route to perform QoS routing and fault-tolerant routing efficiently. The data structure can be implemented as an add-on software to existing routing protocols and may be implemented in existing networks which use shortest path protocols, even where less than all of the routers use the data structure and multiple path scheme described herein.

Claims

1. A method for routing a data packet from an implementing router to a destination node in a packet switching network, said data packet originally from a source node in said packet switching network, said method comprising the steps of:

A. determining and storing in a data structure;

the shortest distance from the implementing router to the destination node, the cost of each link from the implementing router to each potential next hop;

for each of said potential next hop, the shortest distance from the implementing router to the destination node along a path traversing that particular next hop;

B. storing said data structure in a first memory means at said implementing router;

C. using said data structure to compute multiple viable next hops from the implementing router, each of said viable next hops lying on a path from said source to said destination node, by selecting next hops from the potential next hops whose shortest distance attribute traversing that next hop minus the cost of the link form the implementing router to the next stop is less than the shortest path from the implementing router to the destination node;

D. selecting the optimal of said one or more viable next hops to forward said data packet;

E. upon the failure of forwarding said data packet via the selected next hop, removing the selected next hop from list of viable next hops and repeating step D until the data packet is successfully forwarded to next hop.

2. A method according to claim 1 wherein each of said viable next hops are in a path from said destination whose shortest distance is less than the absolute shortest distance from said source node to said destination node.

3. A method according to claim 1 wherein each of said viable next hops leads to a loop free path from said source node to said destination node, but is not constrained to lead to a shortest path between said source node and said destination node.

4. A method according to claim 1 wherein said selecting steps are constrained to select a viable next hop leading to the shortest path as compared with all of said one or more viable next hops stored in said first memory means.

5. A method for determining multiple loop free paths from a source node to a destination node in a packet switching network, said packet switching network comprising a plurality of routers, said method comprising the step of selecting at each of said routers next hops from potential next hops whose shortest distance attribute traversing that next hop, minus the cost of the link from the source node to the next hop, is less than the shortest path from the source node to the destination node.

6. A router for use in a packet switching network for routing a data packet originating from a source node, to a destination node, comprising:

storage means for a data structure, said date structure comprising;

the shortest distance from said router to a destination node, the distance to each next hop from said router; and

for each of said next hops, the distance of the shortest path from said router to said destination node using said next hop; and

computer implemented means for determining one or more viable next hops from said data structure, by selecting next hops from potential next hops whose shortest distance attribute traversing that next hop minus the cost of the link form the implementing router to the next stop is less than the shortest path from the implementing router to the destination node.