Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-08-17
2002-04-23
Vu, Huy D. (Department: 2733)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S351000
Reexamination Certificate
active
06377551
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to route computation for communication networks and particularly to a method for use in communication networks with multiple “Quality of Service” metrics.
BACKGROUND OF THE INVENTION
“Quality of Service” (QoS) metrics provide measures of performance. Multimedia applications such as digital video and audio often have stringent QoS requirements. In order to deliver performance guarantees, a network has to make resource reservations and exercise network control.
In traditional data networks, achieving an end-to-end connection was the sole or primary goal of routing. Routing protocols usually characterized the network with a single metric, such as hop-count or delay, and used shortest path algorithms for path computation. However, in order to support a wide range of QoS requirements, routing protocols need to have a more complex model where the network is characterized with multiple metrics, such as cost, delay, delay variability, loss probability and bandwidth. The basic objective with QoS routing is to find a path with the lowest cost (or shortest distance) that satisfies one or more QoS constraints in communication networks.
The difficulty in achieving this objective is that the computational complexity is NP-HARD (defined as a problem with n variables for which the computation time is higher than a
n
, for some a>1) and therefore, for all practical purposes, designing a perfect, efficient algorithm for achieving this objective is impossible.
Dijkstra's algorithm, which was developed by Edsger Dijkstra in 1959, is a well known method described in, for example, C. Papadimitriou, K. Steiglitz, (1982),
Combinatorial Optimization: Algorithms and Complexity
, Prentice-Hall, the contents of which are incorporated herein by reference. Using the algorithm, finding the shortest path for travelling from a given vertex on a graph to every other vertex is possible. Dijkstra's algorithm takes a graph with weighted links and a given root vertex as its input and returns, as its output, a label for each vertex on the graph. In the case where the weights represent the length of the links, each vertex label represents the length of the shortest path from the root vertex to the particular vertex. The output is called a minimum spanning tree.
In Zheng Wang and Jon Crowcroft, “Quality of Service Routing for Supporting Multimedia Applications,” (1996),
IEEE Jour. Sel. Area. Comm
., Vol. 14, No. 17, pp. 1228-1234, a bandwidth constraint is factored into a search for the shortest path. This is accomplished by removing links that do not satisfy the bandwidth requirement.
Finding a solution for two or more additive QoS metrics remains an open issue. Current implementations of Asynchronous Transfer Mode Private Network-Network Interface (ATM PNNI) protocols use only Dijkstra's Algorithm to optimize the cost with other constraint metrics checked during the generation of the spanning tree. (See, for example, Atshushi Iwata, et al., “PNNI Routing Algorithms for Multimedia ATM Internet,” (1997),
NEC Res. and Develop
., Vol. 38, No. 1; Data Connection, (1997),
DC-PNNI Specification
.) If no route is found, the cost optimization is ignored and Dijkstra's Algorithm is used with one constraint metric chosen as the optimization target and with other constraint metrics checked during the generation of the spanning tree. This implies that once cost optimization fails with other constraint metrics satisfied, cost optimization is abandoned. The weakness of the current practice is that the network resources may be wasted because high cost routes are selected.
U.S. Pat. No. 5,467,343 issued Nov. 14, of 1995 to Lee describes another approach that focuses on the design of a function which combines multiple metrics into one and then applies Dijkstra's Algorithm. The drawback of this approach is that the selected route may not satisfy the constraints, which results in repetitive re-computation and dynamic redefinition of the function.
Algorithms can be evaluated by a variety of criteria. Most often the interest lies in the rate of growth of the time required to solve increasingly larger instances of a problem. The size of the problem is an integer associated with a problem. The associated integer is a measure of the quantity of input data. For example, the size of a graph problem might be the number of edges.
The time needed by an algorithm, expressed as a function of the size of the problem, is called the time complexity of the algorithm. The limiting behaviour of the time complexity as the size increases is called the asymptotic time complexity. It is the asymptotic time complexity of an algorithm that ultimately determines the size of problems that can be solved by the algorithm. If an algorithm processes inputs of size n in time cn
2
for some constant c, then it is said that the time complexity of that algorithm is O(n
2
), read “order n
2
.”
J. M. Jaffe, “Algorithms for Finding Paths with Multiple Constraints,” (1984),
Networks
, Vol. 14, pp. 95-116, presents an algorithm that computes a path with two constraint metrics satisfied. That algorithm has the time complexity O(b*n
5
*log(n*b)) for n nodes with b as the largest possible weight or length.
SUMMARY OF THE INVENTION
An object of the present invention is to provide an improved route computation algorithm for communication networks with multiple quality of service metrics.
In accordance with an aspect of the present invention there is provided a route computation algorithm for communication networks with two quality of service metrics in which a spanning tree is generated which associates with each node a limiting constraint based on a secondary metric and computes a route from the start node to the destination node while selecting each link to both optimize the primary metric and stay within a limit on the secondary metric. In accordance with another aspect of the present invention the method is extended to compute a route to nearly optimize a primary metric while satisfying a limit on two or more secondary additive QoS metrics.
Accordingly, the present invention comprises a method for determining a route from a start node to a destination node in a communication system comprising nodes and links between said nodes, said method based on at least two quality of service link metrics, a primary link metric to be optimized and at least one secondary link metric to be limited to corresponding secondary link metric path constraints, each of said metrics being additive, said method comprising the steps of: for each of said at least one secondary link metric, associating a secondary link metric constraint with each of said nodes; initializing a set to include said start node; until said destination node is included in said set, undertaking the following steps: (a) for each node with a specified link to a node most recently included in said set, if a sum of a primary link metric of said most recently included node and a primary link metric associated with said link between said each node and said most recently included node is more optimal than any primary link metric associated with said each node and a first of said at least one secondary link metric constraints associated with said each node is more optimal than a corresponding secondary link metric constraint associated with said most recently included node then, associating said each node with said most recently included node and associating said new primary link metric with said each node, including a node in said set where said node was not in said set and had a primary link metric which was more optimal than any primary link metric associated with any other node not in said set; and selecting a route based on nodes in said set.
In other aspects, the method is applied in a router, a computer software media product and a communications system.
Advantages of the present invention are that the algorithm is very efficient and its computational complexity is O(n
3
).
REFERENCES:
patent: 4905233 (1990-02-01), Cain et al.
patent: 546
Huang Kaiyuan
Luo Gang
Wang Jianli
LandOfFree
QoS based route determination method for communications... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with QoS based route determination method for communications..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and QoS based route determination method for communications... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2868307