EP0631413A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for shortest path routing
Assignee: AT&T Inc
•
Filing: 1994-06-15
•
Granted: —
•
Expires: 2014-06-15
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 Gopalaswamy Ramakrishnan
- 👤 Manoel Alberto Rodrigues
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-05 19:09
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12; H04L45/123
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
168 words
A method of assigning link metrics in a network, wherein said network comprises nodes connected by links, said method 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 the 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 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. selecting the neighbor in said neighborhood that yields the best performance for said network according to a performance measure; and f. assigning as link metrics for said network the link metrics associated with said selected neighbor.
Claim 2
Dependent Claim
151 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 said shortest path 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 the best performance and increasing the metric of said link by the perturbation for said link.
Claim 3
Dependent Claim
28 words
The method of claim 1 further comprising the step of sending a signal to said nodes in said network wherein said signal comprises information regarding said link metrics.
Claim 4
Dependent Claim
29 words
The method of claim 1 wherein said initial link metric for each link in said network is initially selected as the inverse of the link capacity for said link.
Claim 5
Dependent Claim
13 words
The method of claim 1 wherein said performance measure is average network delay.
Claim 6
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 7
Independent Claim
177 words
A system for assigning link metrics in a 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 the 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 the best performance for said network according to a performance measure; and f. means for assigning as link metrics for said network the link metrics associated with said selected neighbor.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.