US5596719A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for routing and link metric assignment in shortest path networks
Assignee: Nokia of America Corp
•
Filing: 1995-08-29
•
Granted: 1997-01-21
•
Expires: 2015-08-29
Abstract
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).
Inventors
- 👤 Kajamalai G. Ramakrishnan
- 👤 Manoel A. Rodrigues
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 10:15
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12; H04L45/123
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
233 words
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.
Claim 2
Independent Claim
233 words
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.
Claim 3
Dependent Claim
162 words
The method of claim 1 wherein said step of finding a neighborhood further comprises the steps of: a. for each link l: determining the shortest paths between each pair of nodes with link l removed; determining a set of increases in the length in said shortest paths over said initial set of shortest paths; ordering elements of said set of increases in ascending order; defining as a perturbation for link l the average of the first and second positive minimum elements of said set of increases; increasing the link metric for link l by said perturbation and determining a new set of shortest paths; determining the performance of said network according to said performance measure for said new set of shortest paths; resetting the link metric for link l; and b. finding the link that provides a performance level for said network which meets a predetermined second performance criterion and increasing the metric of said link by the perturbation for said link.
Claim 4
Dependent Claim
40 words
The method of claim 1 wherein the step of assigning comprises the step of sending a signal from a network manager processor to said nodes in said network wherein said signal comprises information regarding a subset of said link metrics.
Claim 5
Dependent Claim
43 words
The method of claim 1 wherein each link in the network is characterized by a link capacity and wherein said initial link metric for each link in said network is initially selected as the inverse of the link capacity for said each link.
Claim 6
Dependent Claim
13 words
The method of claim 1 wherein said performance measure is average network delay.
Claim 7
Dependent Claim
28 words
The method of claim 1 wherein said initial link metric is based on a measure of traffic between sets of nodes in said network measured over an interval.
Claim 8
Independent Claim
218 words
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.
Claim 9
Independent Claim
218 words
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.
Claim 10
Dependent Claim
28 words
The method of claim 1 wherein said single path is the shortest path between said pair of nodes as determined as a function of the assigned link metrics.
Claim 11
Dependent Claim
28 words
The system of claim 7 wherein said single path is the shortest path between said pair of nodes as determined as a function of the assigned link metrics.
References Cited (Backward Citations)
US4905233A
Cited
US4912656A
Cited
US5115495A
Cited
US4974224A
Cited
US5253161A
Cited
US5404451A
Cited
US5272638A
Cited
US5233604A
Cited
US5289462A
Cited
US5347511A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-01-21 | 2000-07-22 | 2001-01-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-01-21 | 2004-07-22 | 2005-01-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-01-21 | 2008-07-22 | 2009-01-21 | $7700.00 | Window Closed / Lapsed |