Quality of service routing in information networks over...

Details Quality of service routing in information networks over... Quality of service routing in information networks over...

2000-07-27

2004-02-24

Kiwu, Hassan (Department: 2662)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S203000, C370S231000

Reexamination Certificate

active

06697335

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method of routing packets of information over paths between source and destination nodes in an information network.
2. Discussion of the Known Art
Today's Internet incorporates so-called “best effort” routing. That is, a source node in the network is connected to a destination (sink) node over a path of network links, using protocols that do not always assure a given level of service quality. For example, given the dynamic nature of Internet traffic, it is possible (and presently permitted) that packets will encounter unexpected delays. While best effort routing has been adequate for traditional applications such as File Transfer Protocol (FTP), modern applications such as real-time audio or video require strict routing performance guarantees for satisfactory transmission via the Internet.
It is contemplated that the Internet will eventually have to support various levels of quality of service (QoS) in addition to a “best effort” one. For example, each level may have its own set of service guarantees, and packets associated with certain applications may be favored over others so as to satisfy a given performance requirement for such applications. Accordingly, users of these applications may be charged more than users of applications having less stringent transmission requirements.
Several proposals have been advanced to support various forms of guaranteed service classes. See, e.g., R. Braden, et al, Integrated Services in the Internet Architecture—An Overview, RFC 1633; and Differentiated Service for the Internet, URL=diffserv.lcs.mit.edu. A core component of these proposals is the identification of a routing path for an application based on (1) QoS requirements for the application, and (2) available resources of the network.
The QoS requirements of an application are specified as either a set of path-constraints, i.e., requirements on an entire path between source and sink nodes in a network, or a set of link-constraints, i.e., requirements on individual network links that form a given path. See W. Lee, et al, Routing Subject to Quality of Service Constraints in Integrated Communication Networks, IEEE Networks (July 1995); and R. Nagarajan, et al, Allocation of Local Quality of Service Constraints to Meet End-to-End Requirements, IFIP Workshop on the Performance Analysts of ATM Systems (1993). A path with sufficient network resources to satisfy the QoS requirements of a given application is called a feasible path. Further, one or more optimization criteria may then narrow a selection among the feasible paths. A goal of QoS routing then becomes finding the optimal feasible path. See E. Crawley, et al: A Framework for QoS-Based Routing in the Internet, RFC 2386 (August 1998).
In addition to improving the performance of individual applications, QoS routing may improve overall network efficiency. See G. Apostolpoulos, et al, Quality of Service Routing—A Performance Perspective, ACM Sigcomm (1998); Z. Wang, et al, Quality of Service Routing for Supporting Multi-Media Applications, IEEE Journal on Selected Areas in Communications, 14(7) at 1228-1234 (1996); and W. Lee, et al, supra. Such gains must be weighed carefully against the complexity and cost of implementing the required QoS routing algorithms in a given network, however. Unfortunately, most QoS problems belong in a class called “multi-objective optimization”, which tends to be NP (nondeterministic polynomial time)-hard. Thus, past efforts have concentrated on finding various heuristics, i.e., sub-optimal algorithms often lacking any performance guarantees, or algorithms guaranteed to be optimal only for certain special cases.
Consider a network of n nodes and m links, wherein each link has an associated cost function c
e
(d) representing a cost incurred by guaranteeing a delay of not more than d on link e. For a given source node s and a destination node t, an end-to-end delay constraint of D needs to be satisfied. The following two problems then arise:
1. Constrained minimum cost path (PATH): Find a path in the network from s to t, and determine how much to pay for each link of the path, in order that (a) the total delay over the path is not more than D, and (b) the total cost for all links of the path is minimized. p
1
2. Constrained minimum cost partition (PARTITION): Assume a feasible s-t path P of p links has been determined. Then determine how much to pay on each link of the path in order to (a) maintain the total delay constraint D, and (b) minimize the total cost for all links.
PARTITION thus maps a path constraint of PATH into link constraints. PATH is also a generalization of the so-called restricted shortest path problem (RSP), in which each link has one fixed cost c
e
with fixed delay d
e
. Both PATH and PARTITION may be solved optimally with dynamic programming. See R. Guerin, et al, QoS Based Routing in Networks With Inaccurate Information, IEEE/ACM Transactions on Networking, at 350-364 (June 1999). The running time 0(D
2
m) is pseudo-polynomial, however. The RSP, a special case of PATH, is also NP-hard.
Approximation techniques have been given for solving RSP. See R. Hassin, Approximation Schemes for the Restricted Shortest Path Problem, Mathematics of Operations Research, 17(1) at 36-42 (February 1992)(hereafter “Hassin”), which is incorporated by reference. Hassin uses a technique called “rounding-and-scaling” to solve RSP, wherein a set of possible delay values are “scaled” down to a small enough range so that the scaled problem may be solved optimally in polynomial time. The solution is then “rounded” back to the original delay values with some bounded error.
Throughout prior studies, cost functions for each link are assumed to be convex. In D. Lorenz, QoS Routing, supra, a “greedy” approach is disclosed for obtaining optimal solutions, as well as a polynomial time &egr;-approximation.
Generally, when running an &egr;-approximation procedure, a value (typically 0<&egr;<1) is chosen which corresponds to how “close” an approximation is desired. For example, if the approximation result is to be 90% accurate, &egr; is chosen so that 1/(1+&egr;)=0.9, or &egr;≈0.1. The smaller the value of &egr;, the more accurate the approximation but the longer it takes to run the procedure.
Variants of the greedy approach for PARTITION with improved polynomial running time are disclosed in D. Lorenz, et al, Optimal Partition of QoS Requirements on Unicast Paths and Multicast Trees, IEEE Infocom (1999).
SUMMARY OF THE INVENTION
According to the invention, a method of determining an optimal path from a source node to a destination node over a number of links in an information network having n nodes, wherein each link has an associated cost-delay function, the optimal path is constrained to an overall delay of D, and a total cost of all links along the path is minimized at a value OPT, includes maintaining a range [L, U] for OPT, wherein L is a lower bound and U is an upper bound, setting initial values of L and U, setting a cost value V corresponding to {square root over (U·L)}, and scaling a known cost c of each link from c to c′, wherein c′ corresponds to cn/V&egr;, and &egr;>0.
The method also includes determining if a feasible path exists having a delay of at most D and a total cost of at most V and, if no feasible path exists, then increasing the value of L and returning to the cost value setting and the link cost scaling steps, decreasing the value of U and continuing to increase the value of L until U/L<2 and a feasible path continues to exist, and identifying the links of the feasible path as the optimal path.


REFERENCES:
patent: 5233604 (1993-08-01), Ahmadi et al.
patent: 5274643 (1993-12-01), Fisk
patent: 6301244 (2001-10-01), Huang et al.
patent: 6363334 (2002-03-01), Andrews et al.
R. Hassin, Approximation Schemes for the Restricted Shortest Path Problem, Mathematics of Operations Research, v. 17, No. 1 (Feb. 1992).
D.H. Lorenz, et al., Optimal Partition of QoS Requi

Affiliated with

Also associated with

Rating

Quality of service routing in information networks over... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Quality of service routing in information networks over..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quality of service routing in information networks over... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3277794