Multiple path routing
First Claim
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.
7 Assignments
0 Petitions
Accused Products
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.
-
Citations
6 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. - View Dependent Claims (2, 3, 4)
-
-
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.
-
Specification