초록 ▼

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 measur

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).

대표청구항 ▼

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

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.