Methods and apparatus for optimum path selection in packet transmission networks
First Claim
1. 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 comprisingmeans 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, andmeans for accepting said optimal path only if said optimal path also has a transmission delay below a preselected threshold.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
15 Claims
-
1. 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.
-
6. 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.
-
11. 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.
Specification
-
- Resources
-
Current AssigneeInternational Business Machines Corporation
-
Original AssigneeInternational Business Machines Corporation
-
InventorsChen, Jeane S., Lee, Anthony M., Guerin, Roch, Chow, Chee-Seng, Tedijanto, Theodore E., Gun, Levent, Ahmadi, Hamid
-
Primary Examiner(s)Safourek, Benedict V.
-
Application NumberUS07/874,917Time in Patent Office462 DaysField of Search370/54, 370/58.1, 370/60, 370/60.1, 370/79, 370/84, 370/94.1, 370/94.3, 340/825.03, 340/827US Class Current370/238CPC Class CodesH04L 45/12 Shortest path evaluationH04L 45/123 Evaluation of link metrics ...
