Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-12-16
2002-11-05
Wiley, David (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
06477582
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to link selection during connection admission control for communication networks and, in particular, conservative link selection.
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. To deliver performance guarantees, a network has to 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” (ReSerVation Protocol) has been developed as a resource reservation protocol for the Internet. Multiple QoS metrics such as cost, delay, delay variation, loss probability and available 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.
A communications network may be modelled as a weighted graph where each link between two nodes is associated with certain QoS metrics as weights, such as cost and available bandwidth. Each switch on such a network may maintain a network graph with QoS weights associated with each link. It is necessary to keep the network graphs current. If, for example, available bandwidth of a link undergoes a significant change, the change is advertised by a broadcast of the new information to all other switches, called flooding. Due to the time delay of the flooding, the bandwidth information in the network graph of a particular switch may not be very accurate.
To set up a connection, a switch first selects, given the present network graph, a path from a source node to a destination node. Once a path has been selected, a call request is sent along the selected path to reserve the resources necessary for the eventual connection of the source and destination nodes. Call (or Connection.) Admission Controls (CACs) define procedures used by a switch at the edge of a network, whereby a call request is accepted or rejected based on the ability of the network to support the requested QoS. Generic CAC is used when routing a connection request through an ATM network.
In current practice, when a call setup request is received by a switch, the switch uses CAC to first eliminate all links from the present network graph which cannot satisfy the bandwidth request (see, for example, “Private Network-Network Interface Specification Version 1.0 (PNNI 1.0),” ATM Forum, 1996). Then the switch uses a path selection algorithm such as Dijkstra's algorithm to find a minimum cost path.
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.
Due to inaccurate bandwidth information, a call setup request may be blocked at some node along the path, especially when the network is heavily loaded. Furthermore, since the call setup request has already reserved bandwidth along the path from the source node to the blocking node, the reserved network bandwidth resource is wasted, which in turn may cause more call blocking. More frequent flooding to increase the accuracy of the bandwidth information consumes valuable network resources and may not be acceptable.
A high call blocking rate is currently solved by lowering the traffic load which is sent to the network. Since traffic load means revenue for the network service provider, this solution may be expensive.
SUMMARY OF THE INVENTION
The method of the subject invention involves conservatively selecting links in a path from a source node to a destination node in a communication network. The method first eliminates from consideration those links between nodes in the communication network whose concave metric does not exceed a required concave metric. The method then processes those links whose concave metric does not exceed an inflated value of the required concave metric. The processing comprises either reassigning an additive metric of each such link or eliminating each such link from consideration. A path from the source node to the destination node is then selected, using only links still under consideration, corresponding to a path wherein the additive metric is minimized.
In accordance with an aspect of the present invention there is provided a method for facilitating selection of a path in a communications network comprising nodes and links between the nodes, including comparing a function of one of a required concave link metric for the path and a concave link metric associated with a link with the other of the required concave link metric for the path and the concave link metric associated with the link and if the comparing results in a pre-defined outcome, processing the link. In another aspect of the invention a router may be provided to carry out the method. In another aspect of the invention a software medium permits a general purpose computer to carry out the method. In a further aspect of the present invention there is provided a communications system including a controller for facilitating selection of a path, the controller including means for carrying out the method of the invention.
In accordance with a still further aspect of the present invention there is provided for a communication system comprising nodes and links between the nodes, a method for selecting a path from a start node to a destination node, the method including eliminating from consideration each link for which a required concave link metric exceeds a concave link metric associated with the each link, the eliminating resulting a plurality of links still under consideration. The method next includes processing each link of the plurality of links still under consideration for which either an inflating function of the required concave link metric exceeds a concave link metric associated with the link or the required concave link metric exceeds a deflating function of a concave link metric associated with the link. The method concludes by selecting a path from the source node to the destination node, using only the plurality of links still under consideration.
REFERENCES:
patent: 6094687 (2000-07-01), Drake, Jr. et al.
patent: 6104701 (2000-08-01), Avargues et al.
patent: 6141325 (2000-10-01), Gerstel
patent: 6175870 (2001-01-01), Gawlick et al.
patent: 6189043 (2001-02-01), Buyukkoc et al.
Luo Gang
Sutherland Glenn
Wang Jianli
Millard Allan P.
Nortel Networks Limited
Wiley David
LandOfFree
Method and apparatus for conservative link selection does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for conservative link selection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for conservative link selection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2930621