US6016306A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Routing bandwidth-reserved connections in information networks
Assignee: International Business Machines Corp
•
Filing: 1993-12-24
•
Granted: 2000-01-18
•
Expires: 2013-12-24
Abstract
Abstract This invention defines a routing method which allows a determination of best paths from link weights in situations where these weights are not additive, but the characteristic of a concatenated path is determined mainly by single "bottleneck" links. To be compatible, the metric must be chosen from a specific set of metrics, called bottleneck metrics in this description. The new widest-path method has some characteristics in common with the known Dijkstra method for additive weights. Implementations in communication networks are disclosed which lead to new nodes, new networks and new network protocols.
Inventors
- 👤 Jean-Yves Le Boudec
- 👤 Antoni B. Przygienda
- 👤 Robert Sultan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 12:42
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12; H04L45/123; H04L45/34; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04Q3/00; H04Q3/64; H04Q3/66; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5619
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
133 words
For use at a node in a network having a plurality of nodes interconnected by links, each of the links having an assigned link weight reflecting a selected link characteristic, a method of selecting a least weight path from a source to a destination comprising the steps of: constructing a set of loop-free paths from the source to the destination; for each path in the set, determining the amount of currently-available bandwidth on each link in the path; for each path in the set, assigning a path weight as a function of the minimum amount of bandwidth currently available anywhere along the path; establishing a subset of paths including each path having a path weight equal to the lowest assigned path weight; and selecting a final path from the established subset of paths.
Claim 2
Dependent Claim
133 words
For use at a node in a network having a plurality of nodes interconnected by links, each of the links having an assigned link weight reflecting a selected link characteristic, a method of selecting a least weight path from a source to a destination comprising the steps of: constructing a set of loop-free paths from the source to the destination; for each path in the set, determining the amount of currently-available bandwidth on each link in the path; for each path in the set, assigning a path weight as a function of the minimum amount of bandwidth currently available anywhere along the path; establishing a subset of paths including each path having a path weight equal to the lowest assigned path weight; and selecting a final path from the established subset of paths.
Claim 3
Dependent Claim
49 words
A method as set forth in claim 1 wherein the step of selecting a final path includes the following additional step where the subset includes more than one path: selecting as the final path the path in the subset having the minimum number of links between source and destination.
Claim 4
Dependent Claim
125 words
A path selection apparatus for a node in a network having a plurality of nodes interconnected by links comprising: a memory for storing the network topology, including the currently available bandwidth on each link in the network; path generation logic for generating a set of possible paths between a source and a destination in the network; path weighting logic for assigning a path weight to each generated path, the assigned path weight being a function of the lowest amount of currently available bandwidth over the generated path; path selection logic for establishing a subset of paths including each path having a path weight equal to the lowest assigned path weight; and final selection logic for choosing a final path from the established subset of paths.
Claim 5
Dependent Claim
125 words
A path selection apparatus for a node in a network having a plurality of nodes interconnected by links comprising: a memory for storing the network topology, including the currently available bandwidth on each link in the network; path generation logic for generating a set of possible paths between a source and a destination in the network; path weighting logic for assigning a path weight to each generated path, the assigned path weight being a function of the lowest amount of currently available bandwidth over the generated path; path selection logic for establishing a subset of paths including each path having a path weight equal to the lowest assigned path weight; and final selection logic for choosing a final path from the established subset of paths.
Claim 6
Dependent Claim
34 words
An apparatus as set forth in claim 3 wherein the final selection logic selects the path in the subset which has the minimum number of links between source and destination as the final path.
References Cited (Backward Citations)
US5088032A
Cited
US5115495A
Cited
US5163042A
Cited
US5218676A
Cited
US5596719A
Cited
US5521910A
Cited
US5606669A
Cited
US5596722A
Cited
US5608721A
Cited
US5600794A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-17 | 2003-07-19 | 2004-01-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-17 | 2007-07-19 | 2008-01-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-17 | 2011-07-19 | 2012-01-18 | $7700.00 | Window Closed / Lapsed |