EP0568477A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and apparatus for optinum path selection in packet transmission networks
Assignee: International Business Machines Corp
•
Filing: 1993-03-23
•
Granted: —
•
Expires: 2013-03-23
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 Shu-Chun Chen
- 👤 Chee-Seng Chow
- 👤 Roch Guerin
- 👤 Levent Gun
- 👤 Anthony Mangchuen Lee
- 👤 Theodore E. Tedijanto
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-27 05:15
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12; H04L45/123
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
148 words
A packet communications system comprising a first plurality of packet switching nodes (11) for receiving and sending data packets in said system (10), a second larger plurality of transmission links (A,L) interconnecting pairs of said packet switching nodes (11), means for determining optimum routes between a packet originating node (i) in said system (10) and a packet destination node (j) in said system (10), said means for determining optimum routes characterized in that they comprise (FIG. 5) : - means for identifying principal paths including minimal hop count and minimal transmission delay below a preselected threshold (P T ) between said originating node (i) and said utilizing node (j) (43), - means utilizing said principal path identifications for determining an optimal path between said originating (i) and destination (j) nodes (44), and - means for limiting the transmission delay in said optimal path to a preselected threshold (45).
Claim 2
Dependent Claim
23 words
The packet communications system (10) according to claim 1 wherein said means for determining optimal paths comprises a modified Bellman-Ford algorithm (FIG. 8).
Claim 3
Dependent Claim
45 words
The packet transmission system (10) according to claim 1 wherein said means for limiting the transmission delay comprises means for weighing each said tranmission link in accordance with a weighing function dependent on the non-allocated bandwidth available in the corresponding one of said transmission links.
Claim 4
Dependent Claim
41 words
The packet transmission system (10) 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 5
Dependent Claim
102 words
The packet transmission system (10) according to claim 1 wherein said means for limiting the transmission delay comprises means for weighing each said transmission link according to the equation (FIG. 10) : d kl = C kl (C kl - C ¯ kl (1) )(C kl - C ¯ kl (2) ) where d kl is the incremental delay between nodes k and 1, C kl = total bandwidth of said transmission link from Node k to l, C ¯ kl (1) = already allocated bandwidth before this route, and C ¯ kl (2) = allocated bandwidth after this route.
Claim 6
Dependent Claim
101 words
A route controller (37) for a packet communications system (10) comprising packet switching nodes (11) interconnected by transmission links (A, L) characterized in that it comprises (FIG. 5) : means for identifying principal paths including minimal hop count and minimal transmission delay below a predetermined threshold P T between an originating node (i) and a destination (j) in said system (10) (43), means, responsive to said means for identifying principal paths, for determining an optimal path between said originating (i) and destination (j) nodes (44), and means for limiting the transmission delay in said optimal path to a preselected threshold (45).
Claim 7
Dependent Claim
22 words
The route controller (37) according to claim 6 wherein said means for identifying principal paths comprises a modified Bellman-Ford algorithm (FIG. 6).
Claim 8
Dependent Claim
44 words
The route controller (37) according to claim 6 wherein said means for limiting the transmission delay comprises means for weighing each said tranmission link in accordance with a weighing function dependent on the non-allocated bandwidth available in the corresponding one of said transmission links.
Claim 9
Dependent Claim
43 words
The route controller (37) 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 10
Dependent Claim
101 words
The route controller (37) according to claim 6 wherein said means for limiting the transmission delay comprises means for weighing each said transmission link according to the equation (FIG. 10) : d kl = C kl (C kl - C ¯ kl (1) )(C kl - C ¯ kl (2) ) 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 (1) = already allocated bandwidth before this route, and C ¯ kl (2) = allocated bandwidth after this route.
Claim 11
Independent Claim
117 words
A method (FIG. 6) for determining routes in a packet communications system characterized in that it comprises the step of interconnecting a first plurality of packet switching nodes (11) for receiving and sending data packets in said system (10) with a second larger plurality of transmission links (A, L), identifying principal paths including both a minimal hop count and a minimal transmission delay below a predetermined threshold (P T ) between an originating node (i) and a destination node (j) in said system (43), utilizing said principal path identifications for determining an optimal path between said originating (i) and destination (j) nodes (44), and limiting the transmission delay in said optimal path to a preselected threshold (45).
Claim 12
Dependent Claim
21 words
The method according to claim 11 wherein said step of identifying principal paths (43) utilizes a modified Bellman-Ford algorithm (FIG. 6).
Claim 13
Dependent Claim
43 words
The method according to claim 11 wherein said step of limiting the transmission delay comprises the step of weighing each said tranmission link in accordance with a weighing function dependent on the non-allocated bandwidth available in the corresponding one of said transmission links.
Claim 14
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 15
Dependent Claim
100 words
The method according to claim 11 wherein said step of limiting the transmission delay comprises the step of weighing each said transmission link according to the equation (FIG. 10) : d kl = C kl (C kl - C ¯ kl (1) )(C kl - C ¯ kl (2) ) where d kl is the incremental delay between nodes k and 1, C kl = total bandwidth of said transmission link from Node k to l, C ¯ kl (1) = already allocated bandwidth before this route, and C ¯ kl (2) = allocated bandwidth after this route.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.