Systems and methods for multipath routing

• US 20060133282A1
• Filed: 09/29/2005
• Published: 06/22/2006
• Est. Priority Date: 12/21/2004
• Status: Abandoned Application

• Current Assignee: Avaya Incorporated
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Ramasamy, Jesuraj
• Application Number:
  US11/238,746
• Publication Number:
  US 20060133282A1
• Time in Patent Office: Days
• US Class Current: 370/238
• 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/12 Shortest path evaluation
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A method and system for directing data packets from an origin node to a destination node in a multipath communication network having a plurality of nodes, where each node is connected to at least one other node by links. The apparatus includes a processor for obtaining cost information relating to each link in the network and for determining the least-cost route between the origin node and the destination node based on the cost information relating to each link. The processor establishes a cost margin representing a range of costs above the cost of the least cost route and identifies one or more alternate routes. A data storage device stores the cost information, and a network interface selectively routes the data packets through one or more of the least cost route and the one or more alternate routes falling within the established cost margin thus balancing the network load and providing alternate data paths in case the least-cost path is unavailable.

Claims

1. A method for establishing a routing protocol in a multipath communication network having a plurality of nodes, each node connected to at least one other node by links, the method comprising:

identifying one or more routes from a source node to a destination node;

determining a cost of each route;

determining a least-cost route between the source node and the destination ( node;

establishing a cost margin, the cost margin representing a range of costs above the cost of the least cost route; and

identifying one or more alternate routes, the alternate routes falling within the established cost margin.

2. The method of claim 1, wherein the one or more alternate routes are non-looping routes.

3. The method of claim 1, further comprising selectively routing data packets through one or more of the least cost route and the one or more alternate routes.

4. The method of claim 1, further comprising buffering the identity of the one or more alternate routes, and routing the data packets through the least cost route.

5. The method of claim 1, further comprising revising the cost margin in order to identify one or more different routes, the one or more different routes having costs falling within the revised cost margin.

6. The method of claim 1, wherein the routing protocol is an ECMP routing protocol and the cost of the one or more alternate routes within the established cost margin are considered equal to the cost of the least-cost route.

7. The method of claim 6, wherein the data packets are not routed through any routes having costs that fall outside the established cost margin.

8. The method of claim 1, wherein the cost of a route is comprised of the sum of the costs between each link in the route.

9. The method of claim 1, wherein the cost margin is established to identify at least one alternate route.

10. An apparatus for directing data packets from an origin node to a destination node in a multipath communication network having a plurality of nodes, each node connected at least one other node by links, the apparatus comprising:

a processor for obtaining cost information relating to each link in the network and for determining the least-cost route between the origin node and the destination node based on the cost information relating to each link, wherein the processor establishes a cost margin representing a range of costs above the cost of the least cost route and identifies one or more alternate routes;

a data storage device for storing the cost information and the identity of the one or more alternate routes; and

a network interface for selectively routing the data packets through one or more of the least cost route and the one or more alternate routes falling within the established cost margin.

11. The apparatus of claim 10, wherein the one or more alternate routes are non-looping routes.

12. The apparatus of claim 10, wherein the data storage device buffers the identity of the one or more alternate routes and the network interface routes the data packets through the least cost route.

13. The apparatus of claim 10, wherein the processor is adapted to revise the cost margin in order to identify one or more different routes, the cost of the one or more different routes falling within the revised cost margin.

14. The apparatus of claim 10, wherein the cost of a route is comprised of the sum of the costs between each link in the route.

15. The apparatus of claim 10, wherein the cost margin is established to identify at least one alternate route.

16. A storage medium storing a computer program which when executed by a processing unit performs a method for establishing a routing protocol in a multipath communication network having a plurality of nodes, each node connected to at least one other node by links, the method comprising:

identifying all possible routes from a source node to a destination node;

determining a cost of each route;

determining a least-cost route between the source node and the destination node;

establishing a cost margin, the cost margin representing a range of costs above the cost of the least cost route; and

identifying one or more alternate routes, the alternate routes falling within the established cost margin.

17. The storage medium of claim 16, wherein the one or more alternate routes are non-looping routes.

18. The storage medium of claim 16, wherein the data packets are selectively routed through one or more of the least cost route and the one or more alternate routes.

19. The storage medium of claim 16, wherein the storage device buffers the identity of the one or more alternate routes, and the data packets are routed through the least cost route.

20. The storage medium of claim 16, wherein the cost margin is revised in order to identify one or more different routes, the one or more different routes falling within the revised cost margin.

21. The storage medium of claim 16, wherein the routing protocol is an ECMP routing protocol and the cost of the one or more alternate routes within the established cost margin are considered equal to the cost of the least-cost route.

22. The storage medium of claim 21, wherein the data packets are not routed to any routes having costs that fall outside the established cost margin.

23. The storage medium of claim 16, wherein the cost of a route is comprised of the sum of the costs between each link in the route.

24. The storage medium of claim 16, wherein the cost margin is established to identify at least one alternate route.