Multi-path dynamic routing algorithm

• US 7,233,574 B2
• Filed: 01/22/2002
• Issued: 06/19/2007
• Est. Priority Date: 06/07/2000
• Status: Expired due to Fees

• Current Assignee: Clay Corporation, Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Plotkin, Serge, Worfolk, Patrick A., Aaronson, Itai, Ravid-Rabinovitz, Shmuel
• Primary Examiner(s): Vu; Huy D.
• Assistant Examiner(s): Shand; Roberta A
• Application Number:
  US10/056,178
• Publication Number:
  US 20030128687A1
• Time in Patent Office: 1,974 Days
• Field of Search: 370/396, 370/409
• US Class Current: 370/238
• 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

Abstract

Disclosed is a routing algorithm that uses a new concept of node metric system for optimizing the throughput of a network, in particular, a shared medium network. The measure of congestion of a path in the network is represented by a path metric which is computed by summing the node metrics of the intermediate nodes on the path. Factors used in computing node metrics include the following: 1. future traffic load from neighboring nodes to the node; and 2. future traffic load from the node to the neighboring nodes.

Claims

1. A method of routing traffic from a source node to a destination node in a mesh topology network connected to a plurality of hosts, said network having a plurality of nodes that are routers, including source node and destination node and a plurality of links connecting said nodes, the method comprising:

calculating a from-neighbor component of a node metric for a node, said from-neighbor component reflecting the future traffic load from a plurality of neighbors of said node to said node;

calculating a to-neighbor component of said node metric for a node, said to-neighbor component reflecting the future traffic load from said node to said plurality of neighbors; and

combining said from-neighbor component with said to-neighbor component to yield said node metric;

determining a path metric for each path of a plurality of paths from source node to destination node; and

allocating the load from source node to destination node to said plurality of paths according to the path metric of each path of said plurality of paths.

2. The method of claim 1 wherein said calculating a from-neighbor component of said node metric comprises:

determining a first future traffic load for each link of a first plurality of links of said node; and

combining the first future traffic load of said first plurality of links of said node to yield said from-neighbor component of said node metric.

3. The method of claim 1 wherein said calculating a to-neighbor component of said node metric comprises:

determining a second future traffic load for each link of a second plurality of links of said node; and

combining the second future traffic load of said second plurality of links of said node to yield said to-neighbor component of said node metric.

4. The method of claim 2 wherein said determining a first future traffic load for each link of a first plurality of links of said node comprises:

determining the length of a first queue in a first neighbor at the other end of said link, said first queue storing the packets to be sent to said node;

determining the available bandwidth of said first neighbor for sending data to said node; and

analyzing said length of said first queue and said available bandwidth of said first neighbor to yield said first future traffic load for said link.

5. The method of claim 2 wherein said calculating a to-neighbor component of said node metric comprises:

determining a second future traffic load for each link of a second plurality of links of said node; and

combining the second future traffic load of said second plurality of links of said node to yield said to-neighbor component of said node metric.

6. The method of claim 4 wherein said analyzing also takes into account a bandwidth granted by said node to said first neighbor.

7. The method of claim 4 wherein said analyzing comprises using an interpolation method.

8. The method of claim 3 wherein said determining a second future traffic load for each link of a second plurality of links of said node comprises:

determining the length of a second queue in said node, said second queue storing the packets to be sent to a second neighbor being at the other end of said link;

determining the available bandwidth of said node for sending data to said second neighbor; and

analyzing the length of said second queue and said available bandwidth of said node to yield said second future traffic load for said link.

9. The method of claim 8 wherein said analyzing also takes into account a bandwidth granted by said node to said second neighbor.

10. The method of claim 8 wherein said analyzing comprises using an interpolation method.

11. A method of routing a traffic load from a source node to a destination node in a mesh topology network connected to a plurality of hosts, said network having a plurality of nodes that are routers, including source node and destination node and a plurality of links connecting said nodes, the method comprising:

computing a node metric for a node by determining a first future traffic load for a link from a neighbor being at the other end of said link to said node,

determining a second future traffic load for said link from said node to said neighbor, and

combining said first future traffic load and said second future traffic load to yield a metric contribution for said link;

accounting for future scheduled traffic to and from the node in each link, and combining said metric contributions of said first plurality of links to yield said node metric;

determining a path metric for each path of a plurality of paths from source node to destination node; and

allocating the load from source node to destination node to said plurality of paths according to the path metric of each path of said plurality of paths.

12. The method of claim 11 wherein said determining a first future traffic load comprises:

determining the length of a first queue in said neighbor, said first queue storing the packets to be sent to said node;

determining the available bandwidth of said neighbor for sending data to said node; and

analyzing said length of said first queue and said available bandwidth of said neighbor to yield said first future traffic load for said link.

13. The method of claim 12 wherein said determining said second future traffic load comprises:

determining the length of a second queue in said node, said second queue storing the packets to be sent to a said neighbor;

determining the available bandwidth of said node for sending data to said neighbor; and

analyzing the length of said second queue and said available bandwidth of said node to yield said second future traffic load for said link.

14. The method of claim 12 wherein said analyzing also takes into account a bandwidth granted by said node to said neighbor.

15. The method of claim 12 wherein said analyzing comprises using an interpolation method.

16. The method of claim 12 wherein said determining said second future traffic load comprises:

determining the length of a second queue in said node, said second queue storing the packets to be sent to a said neighbor;

determining the available bandwidth of said node for sending data to said neighbor; and

analyzing the length of said second queue and said available bandwidth of said node to yield said second future traffic load for said link.

17. The method of claim 13 wherein said analyzing also takes into account a bandwidth granted by said neighbor to said node.

18. The method of claim 13 wherein said analyzing comprises using an interpolation method.