Multiplex communications – Pathfinding or routing
Reexamination Certificate
1998-12-11
2001-10-09
Hsu, Alpus H. (Department: 2661)
Multiplex communications
Pathfinding or routing
C370S238000
Reexamination Certificate
active
06301244
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to communication networks and is particularly concerned with QoS-oriented route selection.
BACKGROUND OF THE INVENTION
In traditional data communication networks, routing is primarily concerned with connectivity. To achieve efficient utilization of network resources, the cheapest routes are usually selected by finding the shortest paths using algorithms such as Dijkstra's.
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. 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. Thus the algorithm allows finding the shortest path for travelling from a given vertex on a graph to every other vertex.
With the arrival of multimedia applications such as video and audio, it is realized that connectivity alone is far from adequate for such applications to be successful. Unlike traditional data communication applications such as e-mail and remote file transfers, live video and audio cannot tolerate excessive delay and need guaranteed maximum delay and bandwidth. To deliver such Quality of Service (QoS) guarantees, a network must make resource reservations and exercise network control. In “Private Network-Network Interface Specification Version 1.0 (PNNI 1.0),” ATM Forum, 1996, resource reservation has been incorporated in the PNNI protocol for Asynchronous Transfer Mode (ATM) communication. As well, “RSVP” has been developed as a resource reservation protocol for the Internet. Multiple QoS metrics such as cost, delay, delay variation, loss probability and bandwidth are accommodated by the PNNI protocol. As a result, the routing problem, that of achieving efficient utilization of network resources, is further complicated by these QoS metrics. The route selection problem is now to find a path from the source to the destination that satisfies all QoS constraints and has the lowest cost.
The most studied QoS metrics fall into two categories. The first category is concave, in which the aggregate metric over a path is the minimum of the values of this metric for all sections of the path. The second category is additive, in which the aggregate metric over a path is the sum of the values of this metric for all sections of the path.
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, and R. Guerin et al., “QoS Routing Mechanism and OSPF Extensions,” Internet Draft, Mar. 25, 1997, demonstrated that concave metrics can be easily handled by simply ignoring those links between nodes that do not satisfy the constraints since a decision can be made locally at a link. For example, all links that do not satisfy the bandwidth constraints can be removed before selecting a route.
Selecting a route is not simple, however, for additive metrics. This is because a decision cannot be made until the value of the metric for each link on a path has been examined. For example, to determine if a path satisfies a given delay constraint it is necessary to compare the sum of the delays of all links on the path to the constraint. Finding an algorithm that can handle two or more additive parameters has been challenging. No efficient, that is to say “polynomial-time”, algorithms have been found so far to solve the problem completely, even if not considering any other QoS metrics. Worst of all, it is unlikely that any polynomial-time algorithm can ever be found. The intrinsic difficulty lies in that this problem is in the category of NP-HARD problems. An NP-HARD problem is defined as a problem with n variables for which the computation time is higher than a
n
, for some a>1. This problem was identified as NP-HARD in J. M. Jaffe, “Algorithms for Finding Paths with Multiple Constraints,” (1984),
Networks
, Vol. 14, pp. 95-116. For practical purposes, no polynomial time algorithms can be found for any NP-HARD problems.
A few heuristic approaches have been attempted to solve the QoS-oriented route selection problem. A common heuristic algorithm used by several ATM vendors uses Dijkstra's algorithm to find a minimum cost route and check the validity of this route against other constraints. (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
.) In the case of failure to find a route, the Dijkstra algorithm is used to find a shortest path route in terms of another additive metric, say delay, and then the validity of this route is checked against other metrics. The problem with this approach is that the algorithm gives up looking for minimum cost routes too easily and is likely to miss existing routes that satisfy all constraints and have minimum cost.
U.S. Pat. No. 5,467,343 issued Nov. 14, of 1995 to Lee proposes to combine all additive metrics into one and then solve the problem in polynomial time. (See also W. C. Lee, et al., “Rule based Call-by-Call Source Routing for Integrated Communication Networks”, Infocom '93, pp.987-993, 1993 and W. C. Lee, et al., “Multi-Criteria Routing Subject to Resource and Performance Constraints,” ATM Forum, 94-0280, March 1994.) Unfortunately, a function can not generally be formulated for this conversion. This is especially so where the metrics are independent. Consider, for example, delay and cost. At first glance, the delay and cost might be considered related and proportional. However, a carrier may want to consider any route going through a third party's network to be more expensive than his own. Thus, in general, these metrics must be considered to be independent.
SUMMARY OF THE INVENTION
In accordance with an aspect of the present invention there is provided a method for selecting paths from a source node to other nodes in a communications network having a primary link metric to be limited to a primary link metric path constraint and a secondary link metric to be optimized. Each metric is additive. The method includes constructing a reachability graph, the reachability graph including (i) links and (ii) nodes which terminate the links, for which a sum of the primary link metrics along every path in the reachability graph starting at the source node and passing through the link is no greater than the primary link metric path constraint and selecting a path from the source node to each node in the reachability graph, using only the links in the reachability graph, corresponding to a path wherein the secondary link metric is minimized.
In accordance with another aspect of the present invention there is provided a method for selecting paths from a source node to other nodes in a communications network having a primary link metric to be limited to a primary link metric path constraint and a secondary link metric to be optimized. Each the metric is additive. The method includes adding to a reachability graph from the source node any link from a node in the reachability graph to a first node where the link is associated with a primary link metric which, when summed with a primary link metric assigned to the node in the reachability graph from which the link extends, is less than the primary link metric path constraint. The method also includes, if at least one link to the first node is added to the reachability graph, adding the first node to the reachability graph and assigning, as a primary link metric for the first node, a maximum sum utilizing only links in the reachability graph, selecting paths from the source node through the reachability
Huang Kaiyuan
Luo Gang
Wang Jianli
Hsu Alpus H.
Millard Allan P.
Nguyen Brian
Nortel Networks Limited
LandOfFree
QoS-oriented one-to-all route selection method for... 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-oriented one-to-all route selection method for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and QoS-oriented one-to-all route selection method for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2603961