Method and apparatus for routing and link metric assignment in shortest path networks
First Claim
Patent Images
1. A method of routing information in a network, the method comprising the steps of:
- assigning link metrics in said network, wherein said network comprises nodes connected by links, the step of assigning comprising the steps of;
a. assigning an initial link metric value to each link;
b. determining an initial set of shortest paths between each pair of nodes in said network;
c. determining a level of initial performance of said network with said initial link metric values according to a performance measure;
d. finding a neighborhood to said initial set of shortest paths wherein said neighborhood is a set of neighbors and wherein each neighbor is a set of shortest paths and associated link metrics wherein only a minimum number of paths in the set of shortest paths for each neighbor are changed with respect to the initial set of shortest paths as a consequence of an increase in an initial link metric associated with a specific neighbor;
e. selecting the neighbor in said neighborhood that yields a performance level for said network meeting a first performance criterion as determined according to the performance measure; and
f. assigning as link metrics for said network the link metrics associated with said selected neighbor; and
routing information on a single path between a pair of nodes, said single path between said pair of nodes being determined as a function of the assigned link metrics.
5 Assignments
0 Petitions
Accused Products
Abstract
The invention discloses a method and apparatus for assigning link "distance" metrics that result in near optimal routing for a network formed of nodes (routers) and links, where each link has a capacity associated with it, and where source-destination flows are given. The routing optimality is measured with respect to some objective function (e.g., average network delay).
197 Citations
9 Claims
-
1. A method of routing information in a network, the method comprising the steps of:
-
assigning link metrics in said network, wherein said network comprises nodes connected by links, the step of assigning comprising the steps of; a. assigning an initial link metric value to each link; b. determining an initial set of shortest paths between each pair of nodes in said network; c. determining a level of initial performance of said network with said initial link metric values according to a performance measure; d. finding a neighborhood to said initial set of shortest paths wherein said neighborhood is a set of neighbors and wherein each neighbor is a set of shortest paths and associated link metrics wherein only a minimum number of paths in the set of shortest paths for each neighbor are changed with respect to the initial set of shortest paths as a consequence of an increase in an initial link metric associated with a specific neighbor; e. selecting the neighbor in said neighborhood that yields a performance level for said network meeting a first performance criterion as determined according to the performance measure; and f. assigning as link metrics for said network the link metrics associated with said selected neighbor; and routing information on a single path between a pair of nodes, said single path between said pair of nodes being determined as a function of the assigned link metrics. - View Dependent Claims (2, 3, 4, 5, 6, 8)
-
-
7. A system for routing information in a network by assigning link metrics in said network, wherein said network comprises nodes connected by links, said system comprising:
-
a. means for assigning an initial link metric value to each link; b. means for determining an initial set of shortest paths between each pair of nodes in said network; c. means for determining a level of initial performance of said network with said initial link metric values according to a performance measure; d. means for finding a neighborhood to said initial set of shortest paths wherein said neighborhood is a set of neighbors and wherein each neighbor is a set of shortest paths and associated link metrics such that only a minimum number of paths are changed with respect to the initial set of shortest paths as a consequence of an increase in each initial link metric; e. means for selecting the neighbor in said neighborhood that yields a performance level for said network meeting a predetermined criterion as determined according to a performance measure; f. means for assigning as link metrics for said network the link metrics associated with said selected neighbor; and g. means for routing information on a single path between a pair of nodes, said shortest path being determined as a function of the assigned link metrics. - View Dependent Claims (9)
-
Specification