US5600638A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for improving the processing time of the path selection in a high speed packet switching network
Assignee: International Business Machines Corp
•
Filing: 1994-12-12
•
Granted: 1997-02-04
•
Expires: 2014-12-12
Abstract
Abstract The routing paths between origin and destination nodes in a packet switching network are selected more efficiently by reducing the total number of links potentially visited by the routing algorithm. The path selection technique involves two phases, the first phase for principal links identification, and the second phase for selection of the best point-to-point path in the network. Principal paths are minimum hop count paths with a transmission delay less than a specified threshold. The algorithm limits the screening of the network links in the second phase to the principal links and excludes the secondary links. The exploration of a much smaller number of links has the advantage to considerably reduce the computation time required for the path selection. The fact the number of principal links is generally small compared with the total number of links potentially explored, allows to limit the additional processing time necessary in case of unsuccessful attempt.
Inventors
- 👤 Olivier Bertin
- 👤 Olivier Maurel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 23:19
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12; H04L45/122; H04L45/24; H04L45/243
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
172 words
A packet communications system comprising: a first plurality of packet switching nodes for receiving and sending data packets in the system; a second plurality of transmission links interconnecting pairs of said packet switching nodes; and means for determining an optimum path through said communications system between an originating node in said system and a destination node in said system, said means for determining an optimum path comprising means for identifying principal paths between said originating node and said destination node, said principal paths each including a minimal hop count wherein a hop is a single one of said transmission links in a principal path, means for identifying a set of principal links, a principal link being a link on a principal path identified by said principal path identifying means, means utilizing only the links in said set of principal links for determining an optimal path between said originating and destination nodes, and means for accepting said optimal path only if said optimal path also has a transmission delay below a preselected threshold.
Claim 2
Dependent Claim
172 words
A packet communications system comprising: a first plurality of packet switching nodes for receiving and sending data packets in the system; a second plurality of transmission links interconnecting pairs of said packet switching nodes; and means for determining an optimum path through said communications system between an originating node in said system and a destination node in said system, said means for determining an optimum path comprising means for identifying principal paths between said originating node and said destination node, said principal paths each including a minimal hop count wherein a hop is a single one of said transmission links in a principal path, means for identifying a set of principal links, a principal link being a link on a principal path identified by said principal path identifying means, means utilizing only the links in said set of principal links for determining an optimal path between said originating and destination nodes, and means for accepting said optimal path only if said optimal path also has a transmission delay below a preselected threshold.
Claim 3
Dependent Claim
123 words
A route controller for a packet communications system comprising packet switching nodes interconnected by transmission links comprising: means for identifying principal paths between an originating node and a destination node in said system, each said principal path including a minimal hop count where a hop is a single one of said transmission links in a principal path; means for identifying a set of principal links, a principal link being a link on a principal path identified by said identifying means, means utilizing only the links in said set of principal links for determining an optimal path between said originating and destination nodes, and means for accepting said optimal path only if said optimal path also has a transmission delay below a preselected threshold.
Claim 4
Dependent Claim
123 words
A route controller for a packet communications system comprising packet switching nodes interconnected by transmission links comprising: means for identifying principal paths between an originating node and a destination node in said system, each said principal path including a minimal hop count where a hop is a single one of said transmission links in a principal path; means for identifying a set of principal links, a principal link being a link on a principal path identified by said identifying means, means utilizing only the links in said set of principal links for determining an optimal path between said originating and destination nodes, and means for accepting said optimal path only if said optimal path also has a transmission delay below a preselected threshold.
Claim 5
Independent Claim
135 words
A method for determining paths in a packet communications system comprising the steps of: interconnecting a first plurality of packet switching nodes for receiving and sending data packets in said system through a second plurality of transmission links; identifying principal paths between an originating node and a destination node in said system, each said principal path including a minimal hop count where a hop is a single one of said transmission links in a principal path; identifying a set of principal links, a principal link being a link on an identified principal path, determining an optimal path between said originating node and said destination nodes means utilizing only the links in said set of principal links, and accepting said optimal path only if said optimal path also has a transmission delay below a preselected threshold.
Claim 6
Independent Claim
135 words
A method for determining paths in a packet communications system comprising the steps of: interconnecting a first plurality of packet switching nodes for receiving and sending data packets in said system through a second plurality of transmission links; identifying principal paths between an originating node and a destination node in said system, each said principal path including a minimal hop count where a hop is a single one of said transmission links in a principal path; identifying a set of principal links, a principal link being a link on an identified principal path, determining an optimal path between said originating node and said destination nodes means utilizing only the links in said set of principal links, and accepting said optimal path only if said optimal path also has a transmission delay below a preselected threshold.
Claim 7
Dependent Claim
138 words
For use in a packet communications system comprising a plurality of packet switching nodes interconnected by a plurality of transmission links, a method of determining an optimal path between an originating node and a destination node, said method comprising the steps of: identifying principal paths between the originating node and the destination node in said system, each said principal path including a minimal hop count where a hop is a single one of said transmission links in said principal path; identifying a set of principal links, a principal link being a link on an identified principal path, determining an optimal path between said originating node and said destination node utilizing only the links in said set of principal links, and accepting said optimal path only if said optimal path also has a transmission delay below a preselected threshold.
Claim 8
Dependent Claim
138 words
For use in a packet communications system comprising a plurality of packet switching nodes interconnected by a plurality of transmission links, a method of determining an optimal path between an originating node and a destination node, said method comprising the steps of: identifying principal paths between the originating node and the destination node in said system, each said principal path including a minimal hop count where a hop is a single one of said transmission links in said principal path; identifying a set of principal links, a principal link being a link on an identified principal path, determining an optimal path between said originating node and said destination node utilizing only the links in said set of principal links, and accepting said optimal path only if said optimal path also has a transmission delay below a preselected threshold.
References Cited (Backward Citations)
US4905233A
Cited
US5142531A
Cited
US5233604A
Cited
EP0568477A2
Cited
US5347511A
Cited
US5317566A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-02-04 | 2000-08-05 | 2001-02-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-02-04 | 2004-08-05 | 2005-02-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-02-04 | 2008-08-05 | 2009-02-04 | $7700.00 | Window Closed / Lapsed |