Multiplex communications – Diagnostic testing – Determination of communication parameters
Reexamination Certificate
1998-03-06
2002-04-09
Chin, Wellington (Department: 2664)
Multiplex communications
Diagnostic testing
Determination of communication parameters
Reexamination Certificate
active
06370119
ABSTRACT:
TECHNICAL FIELD
This invention relates high-speed packet switching networks and more particularly, to optimum path selection for connections between two nodes in such systems.
BACKGROUND ART
It has become increasingly useful to interconnect a plurality of data processing elements by means of a packet switching network in which data is transmitted as data assemblages called “packets”. Such networks include a plurality of interconnected switching nodes which, in turn, are connected to end nodes supporting data processing devices. Such packet networks can become quite large with an extensive geographical distribution. In such a situation, the selection of an efficient path between two end nodes which wish to communicate with each other becomes of paramount importance.
Typical methods for optimum path selection use a so-called additive cost approach to compute the shortest path. A given cost or weight is associated to each link of the network. The shortest path from a source node to a destination node will be the path having the smallest cumulative cost, i.e., the smallest sum of the costs of all the links of the path. Examples of typical cost criteria in this approach are the minimum hop count and the minimum path length. The hop count is the number of links used to construct the path between the two end nodes. The path length is a function of the overall transmission delay imposed by the path between the two end nodes. In high-speed packet switching networks, the computing of the shortest path in terms of delay and hop count is a typical problem which must be solved in order to minimize as much as possible the transmission delay and jitter between the two end nodes. This is particularly important for connections related to classes of service with real-time constraints such as video or voice. This problem is known in graph theory as the “single-source shortest path” problem. Several algorithms have been used in the prior art to solve this problem. Such algorithms are disclosed in “Introduction to Algorithms” by T. H. Cormen, C. E. Leiserson and R. L. Rivest, The MIT Press. Classical relaxation algorithms may be used, such as the so-called Dijkstra algorithm, the so-called Bellman-Ford algorithm, or a modified Bellman-Ford algorithm as disclosed in U.S. Pat. No. 5,233,604 to Ahmadi. These algorithms are widely used as they can be rapidly executed. Other algorithms have also been used which rely on linear programming methods, such as the so-called simplex algorithm, the so-called ellipsoid algorithm or the so-called Karmarkar algorithm. However, these linear programing algorithms are rarely used for solving path selection problems as they may have longer execution times.
With emerging standards such as the PNNI routing standard from the ATM Forum defined in “Private Network-Network Interface Specification Version 1.0”, Letter Ballot, March 1996, the problem of finding the shortest path has significantly changed. Now, the network administrator i.e. the person in charge of the network administration, can define for each link of the network an administrative weight (AW) which is actually an additive cost. This administrative weight is traditionally an integer value associated to each link of the network. The network administrator may set different values for this AW in order in order to privilege one path among others. As already stated, if a path is computed which comprises n hops, then the total AW of the path is the algebraic sum of the AW of the n links traversed. An interesting feature for tuning network performance is to define the shortest path not only as a function of the hop count but also in terms of the cumulative administrative weight of the path.
The PNNI standard also defines the maximum and available bandwidths specified for each link. It is helpful, in order to provide load balancing in the network, to take into account bandwidth parameters in the path selection algorithm and to select, among the shortest available paths, the path providing the “widest” bandwidth. Here again, several methods have been proposed in the prior art. For example, PCT patent application No. PCT/EP94/04159 filed on Dec. 15, 1995 and entitled “Method and apparatus for routing a communication in a network” discloses an algorithm that is a modification of the well-known Open Shortest Path First (OSPF) algorithm, which determines in a multi-dimensional manner a set of optimal paths with two-dimensional link costs. Multi-dimensional type algorithms have the disadvantage that they are complex and accordingly require significant processing power for fast execution.
The bandwidth characteristic of a link is typically a so-called restrictive cost; that is, the narrowest bandwidth segment (link) of the path will determine the overall path bandwidth. Furthermore the restrictive cost (e.g. available bandwidth) may be different when considering a path in one direction of transmission or the other. What is needed is a path selection algorithm that computes the best path taking into account both additive cost and restrictive cost, with the restrictive cost being dependent on the proposed direction of transmission. Furthermore, such an algorithm should be of a low complexity in order to executed rapidly while requiring low processing power. Such an algorithm is provided by the present invention.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a method and system for determining the best path for routing a connection through a high-speed packet switching network, with the determination being based upon restrictive and additive characteristics of the network links.
It is another object of the present invention to provide a method and system for determining the best path for a proposed connection in a high-speed packet switching network, with the determination being based upon evaluation of the path offering the widest bandwidth available for the direction of data transmission, the lowest additive cost, and the lowest hop count.
It is a further object of the present invention to provide a method and system to determine all the best paths to route data from a particular source node to all other nodes of a high-speed packet switching network, the determination of the paths being efficient with regard to consideration of both additive and restrictive links.
To achieve the foregoing objects the invention provides in one embodiment, a system for determining the optimal path for routing a communication between a source node and at least one destination node in a communication network comprising a plurality of nodes interconnected by a plurality of links. Each link of the network is associated with at least a restrictive cost and with an additive cost reflecting selected link characteristics. For a connection to be routed the system identifies a source node, a destination node and a maximum restrictive cost allowed for the connection. The system characterizes a path by a restrictive cost and an additive cost derived from the link costs of its component links. The system also determines and stores all the acceptable paths from the source node to all the other nodes of the network. Paths are considered acceptable if they have the lowest restrictive cost that is less than or equal to the maximum restrictive cost allowed by the connection, and if they have the lowest additive cost and minimum hop count. Finally, the system selects, as the optimal path for the connection, the path from the plurality of stored paths that originates from the source node and terminates at the destination node.
REFERENCES:
patent: 5142531 (1992-08-01), Kirby
patent: 5748486 (1998-05-01), Ashar et al.
patent: 5754543 (1998-05-01), Seid
patent: 5870564 (1999-02-01), Jensen et al.
patent: 6016306 (1999-02-01), Le Boudec et al.
patent: 6044075 (2000-03-01), Le Boudec et al.
patent: 6078575 (2000-06-01), Dommety
patent: 6094687 (2000-07-01), Drake, Jr. et al.
Basso Claude
Scotton Paolo
Cesari and McKenna LLP
Cisco Technology Inc.
Jones Prenell
LandOfFree
Computing the widest shortest path in high-speed networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computing the widest shortest path in high-speed networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the widest shortest path in high-speed networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2860455