US5233604A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for optimum path selection in packet transmission networks
Assignee: International Business Machines Corp
•
Filing: 1992-04-28
•
Granted: 1993-08-03
•
Expires: 2012-04-28
Abstract
Abstract A packet communications system utilizes a route determining mechanism by identifying principal paths between the source and the destination in the system. Principal paths are minimum hop count paths with a transmission delay less than a specified threshold. Principal path links are accepted as legs of the optimum path, if feasible, i.e., if the resulting load on the link is less than a specified principal threshold. Secondary links are accepted only if the resulting load on the link is less than a specified secondary threshold, where the secondary threshold is less than the principal threshold. All paths must also have a transmission delay less than a specified threshold. Each request for a route includes the source node, the destination node, the load required, the maximum transmission delay and, if desired, the quality of service parameters which all of the legs of the route must satisfy. A modified Bellman-Ford breadth-first search algorithm is used to identify the principal links and, using these principal link identifications, determining the optimum path.
Inventors
- 👤 Hamid Ahmadi
- 👤 Jeane S. Chen
- 👤 Chee-Seng Chow
- 👤 Roch Guerin
- 👤 Levent Gun
- 👤 Anthony M. Lee
- 👤 Theodore E. Tedijanto
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 09:31
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12; H04L45/123
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
163 words
A packet communications system comprising a first plurality of packet switching nodes for receiving and sending data packets in said system, a second larger plurality of transmission links interconnecting pairs of said packet switching nodes, means for determining optimum routes through said communications system between a packet originating node in said system and a packet destination node in said system, said means for determining optimum routes comprising means for identifying principal paths between said originating node and said utilizing node, said principal paths each including a minimal hop count and, if more than one principal path has the the same minimal hop count, the one having a minimal transmission delay, where a hop is a single one of said transmission links in said principal path, means utilizing said principal path identifications 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
163 words
A packet communications system comprising a first plurality of packet switching nodes for receiving and sending data packets in said system, a second larger plurality of transmission links interconnecting pairs of said packet switching nodes, means for determining optimum routes through said communications system between a packet originating node in said system and a packet destination node in said system, said means for determining optimum routes comprising means for identifying principal paths between said originating node and said utilizing node, said principal paths each including a minimal hop count and, if more than one principal path has the the same minimal hop count, the one having a minimal transmission delay, where a hop is a single one of said transmission links in said principal path, means utilizing said principal path identifications 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
22 words
The packet communications system according to claim 1 wherein said means for determining optimal paths includes means for utilizing a Bellman-Ford algorithm.
Claim 4
Dependent Claim
44 words
The packet transmission system according to claim 1 wherein said means for determining an optimal path comprises means for weighing each said transmission link in accordance with a weighing function dependent on the non-allocated bandwidth available in the corresponding one of said transmission links.
Claim 5
Dependent Claim
40 words
The packet transmission system according to claim 3 wherein said means utilizing said principal path identifications comprises means for providing a larger effective bandwidth for links when in said principal paths than for links when not in said principal paths.
Claim 6
Dependent Claim
71 words
The packet transmission system according to claim 1 wherein said means for determining principal paths comprises means for weighing each said transmission link according to the equation ##EQU4## where d kl is the incremental delay between nodes k and l, C kl =total bandwidth of said transmission link from Node k to l, C kl .sup.(1) =already allocated bandwidth before this route, and C kl .sup.(2) =allocated bandwidth after this route.
Claim 7
Dependent Claim
124 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, said principal paths each including a minimal hop count, and, if two or more of said principal paths have the same minimal hop count, the path also having a minimal transmission delay, where a hop is a single one of said transmission links in said principal path. means, responsive to said means for identifying principal paths, for determining an optimal path through said communications system between said originating and destination nodes, and means for accepting said optimal path only if said optimal path has a transmission delay below a preselected threshold.
Claim 8
Dependent Claim
124 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, said principal paths each including a minimal hop count, and, if two or more of said principal paths have the same minimal hop count, the path also having a minimal transmission delay, where a hop is a single one of said transmission links in said principal path. means, responsive to said means for identifying principal paths, for determining an optimal path through said communications system between said originating and destination nodes, and means for accepting said optimal path only if said optimal path has a transmission delay below a preselected threshold.
Claim 9
Dependent Claim
21 words
The route controller according to claim 6 wherein said means for identifying principal paths includes means for utilizing a Bellman-Ford algorithm.
Claim 10
Dependent Claim
42 words
The route controller according to claim 6 wherein said means for identifying principal paths comprises means for weighing each said transmission link in accordance with a weighing function dependent on the non-allocated bandwidth available in the corresponding one of said transmission links.
Claim 11
Dependent Claim
42 words
The route controller according to claim 8 wherein said means responsive to said means for identifying principal paths comprises means for specifying a larger effective bandwidth for links when in said principal paths than for links when not in said principal paths.
Claim 12
Dependent Claim
70 words
The route controller according to claim 6 wherein said means for identifying principal paths comprises means for weighing each said transmission link according to the equation ##EQU5## where d kl is the incremental delay between nodes k and l, C kl =total bandwidth of said transmission link from Node k to l, C kl .sup.(1) =already allocated bandwidth before this route, and C kl .sup.(2) =allocated bandwidth after this route.
Claim 13
Independent Claim
134 words
A method for determining routes 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 with a second larger 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 and, if two or more of said principal paths include the same minimal hop count, the path also having a minimal transmission delay, where a hop is a single one of said transmission links in said principal path. utilizing said principal path identifications for determining an optimal path between said originating and destination nodes, and accepting said optimal path only if said optimal path has a transmission delay below a preselected threshold.
Claim 14
Independent Claim
134 words
A method for determining routes 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 with a second larger 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 and, if two or more of said principal paths include the same minimal hop count, the path also having a minimal transmission delay, where a hop is a single one of said transmission links in said principal path. utilizing said principal path identifications for determining an optimal path between said originating and destination nodes, and accepting said optimal path only if said optimal path has a transmission delay below a preselected threshold.
Claim 15
Dependent Claim
21 words
The method according to claim 11 wherein said step of identifying principal paths includes the step of utilizing a Bellman-Ford algorithm.
Claim 16
Dependent Claim
42 words
The method according to claim 11 wherein said step of identifying principal paths comprises the step of weighing each said transmission link in accordance with a weighing function dependent on the non-allocated bandwidth available in the corresponding one of said transmission links.
Claim 17
Dependent Claim
40 words
The method according to claim 13 wherein said step of utilizing said principal path identifications comprises the step of specifying a larger effective bandwidth for links when in said principal paths than for links when not in said principal paths.
Claim 18
Dependent Claim
72 words
The method according to claim 11 wherein said step of identifying principal paths comprises the step of means for weighing each said transmission link according to the equation ##EQU6## where d kl is the incremental delay between nodes k and l, C kl =total bandwidth of said transmission link from Node k to l, C kl .sup.(1) =already allocated bandwidth before this route, and C kl .sup.(2) =allocated bandwidth after this route.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-08-02 | 1997-02-01 | 1997-08-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-08-02 | 2001-02-01 | 2001-08-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-08-02 | 2005-02-01 | 2005-08-03 | $7700.00 | Window Closed / Lapsed |