Multi-path dynamic routing algorithm
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
Specification