October 29, 1999
Zhansong Ma
Electrical and Communications Engineering
Helsinki University of Technology
zma@cc.hut.fi
Abstract
The emerging Gigabit-per-second high speed switching technologies and the rapid growth of the Internet enables IP-based networks to support a variety of services in particular for requests with specific QoS constraints, e.g., distributed multimedia communication applications. These requirements for services might contain a number of QoS constraints such as delay, delay jitter, loss ratio , bandwidth and so on. Among them, one of key issues is QoS Routing, whose basic function is to find feasible paths under a single or multiple QoS constraints. This paper aims to give a general discussion about QoS Routing in the Internet. It includes: background of QoS Routing, QoS Routing problems, introduction of QoS Routing algorithms, and possible extensions to QoS Routing.
1. Introduction
2. Background of QoS Routing
References
Further Information
The current global Internet based on IP protocol supports only the best effort services, network resources are contended and fairly shared by all traffic injected into the networks. Data packets of a session may follow different paths to the destination. However, with the success of Internet in recent years, IP networks are also expected to support various services, not only the traditional services such as email and ftp, but also the upcoming high speed and real time services such as audio-vedio real-time transmission and virtual private network. The latter cases exhibit much more different traffic characteristics from the former cases in terms of bit rate and burst, and they require fixed QoS assurances in the duration of transmission. How to support the QoS requirements is becoming a hot topic in the Internet community[8,9].
QoS Routing, however, has been recognized as a missing part in the evolution of QoS_based services offering in the Internet[4, 6]. The basic function of QoS Routing is to find a feasible path(tree) that has the sufficient residual resources to satisfy the QoS constraints of a connection. The Objectives of QoS_based routing scheme is to aid the efficient utilization of network resources by improving the total network throughput. Besides, QoS_based routing provides flexibility in support for various service requirements by customers.
More and more attentions are being paid on the field of QoS Routing: the QoS Routing Workgroup is established in IETF and has fulfilled a RFC on the general framework for QoS Routing in the Internet[4]; some other work on this area have presented a number of unicast or muticast QoS routing algorithms[1,3,5,6,10].
This paper aims to give general discussion of the overall issues involved in QoS Routing problem. The rest of this paper is organized as followed. Section 2 gives the background information on QoS Routing in the Internet. Section 3 presents the QoS Routing problems and its classification. In section 4, a brief introduction of QoS Routing algorithms is done. Some possible extensions to QoS Routing are described in section 5.
In traditional data networks, routing is primarily concerned with connectivity. Current routing protocol (e.g., OSPF and RIP) usually characterize the network with a single metric such as hop-count or delay and use shortest-path algorithms for path computation. These protocols do not use alternative paths with acceptable but non-optimal cost to route traffic. In comparison with best-effort routing, QoS Routing support traffic using various services with requirements for additional routing metrics, e.g, delay, and available bandwidth. QoS routing also provides support for alternate routing. If the best existing path can not admit a new flow, the associated traffic can be forwarded in an adequate alternate path. QoS routing algorithms can prevent traffic shifting from one path to another "better" path only if the current path meet the service requirements of the existing traffic.
2.1. Benefit and Cost of QoS Routing
QoS Routing determines the paths for flows under the knowledge of network
resource availability, as well as the requirements of flows. It aims to
dynamically choose a feasible path from multiple choices, according to
and policy constrains, such as cost, provider selection, etc. As
a result, the performance of applications is guaranteed or improved in
comparison with that without QoS Routing. Meanwhile, QoS Routing optimizes
the resource usage in the network by improving the total network
throughput. However, these benefits of QoS Routing also incur the cost
of developing new routing protocols or extending the existing ones. Moreover,
it potentially increases higher communication, processing and storage overheads.
QoS Routing raises some following issues[4]:
How do routers determine QoS capability and reserve resource?
How do routers determine QoS_based paths computed for unicast/multicast
flows?
How is scalability achieved?
......
RSVP [2] is a reservation protocol in the Internet, which can be used in conjunction with QoS Routing. Specially, RSVP PATH message can serve as the trigger to query QoS Routing. During the processing of RSVP PATH message, RSVP queries QoS Routing to obtain the next hop for forwarding the PATH message. The PATH message is then forwarded on the interface returned by QoS Routing. On the other hand, because of the variation in the availability of resources in the network, routes between the same source and destination and for the same QoS may often differ depending on when the request is made. Thus, it is important to "pine" or "unpine" the path. Path pinning or unpinning considered as RSVP domain operations particularly impacts the frequency of processing QoS Routing, which also affects the performance.
OSPF [7] is a widely used link-state routing
protocol, which is designed to be run internal to a single autonomous system
topology. From this database, a routing table is calculated by constructing
a shortest-path tree. OSPF has some distinguished features, such as fast,
loopless convergence, support of precise metrics, support of multiple paths
to a destination, separate representation of external routes and so on.
OSPF can be extended to provide QOS routing, called QOSPF. These
extensions include: 1)link advertisement with additional QoS metrics; 2)mechnanisms
to trigger the link state update; 3) algorithms on computing the QoS_based
paths.
There are some alternatives of link state update mechanism such as
on the basis of the variation of available resource or just periodically.
The path can also be calculated according to various algorithms in replace
of that in QOSPF.
There are some considerations in defining suitable link and node metrics [4]. First, the metrics must represent the basic network properties of interest, which include residual bandwidth, delay etc. Moreover, the flow QoS requirements have to be mapped on path metrics. Second, the path computation based on a certain metrics or a combination of metrics must not be too complex as to render them impractical. A common strategy to allow flexible combinations of metrics is to utilize "sequential filtering", that is, paths based on a primary metric and so forth until a single path is found. Once suitable link and node metrics are defined, a uniform representation of them is required. Particularly, encoding of the maximum, minimum, range, and granularity of the metrics are needed.
A network can be modeled as a graph (V, E). Nodes (V) of the graph represents switches, routers, and hosts. Edges (E) represent communication links. The edges are undirected only if the links are always symmetric. For most real networks the communication links are asymmetric, hence each link is represented by two directed edges in the opposite directions. Thus, the network can be modeled as a weighted graph measured by the QoS metrics concern. For example, the link state is a triple consisting of residual bandwidth, delay, and cost. The cost of a link is defined in dollars or as a function of the buffer or bandwidth utilization. Moreover, each node also has a state on node resource, e.g., CPU bandwidth. The state of a node can be consider in conjunction with the link state.
According to [3], The QoS routing problems can be divided into two major classes: unicast routing and multicast routing. The unicast routing problem is defined as follows: given a source code s, a destination t, a set of QoS constraints C, and possibly an optimization goal, find the best feasible path from s to t which satisfies C. The multicast routing problem is defined as follows: given a source code s, a set R of destination nodes, a set of QoS constraints C, and possibly an optimization goal, find the best feasible tree covering s to all nodes in R which satisfies C.
In each class, routing problems can be partitioned into subclasses according to the QoS based metrics. In unicast routing domain, for metrics of bandwidth and residual buffer space, the routing problems can be divided into two subclasses: link-optimization routing and link-constrained routing. An example of link (bandwidth)-optimization routing is to find a path that has the largest bandwidth on the bottleneck link. An example of link (bandwidth)-constrained routing is to find a path whose bottleneck bandwidth is above a required value. For other metrics such as delay, delay jitters and cost, the routing problems can be divided into two subclasses: path-optimization routing and path-constrained routing. Many composite routing problems can be derived from the above four basic problems. Unfortunately, there are two NP-complete problem classes, that is, path-constrained path-optimization routing (PCPO) and multi-path-constrained routing (MPC). An example of PCPO is delay-constrained least-cost routing, which is to find the least-cost path with bounded delay. An example of MPC is delay-delay-jitter-constrained routing, which is to find a path with both bounded delay and bounded delay jitter.
Multicast routing is different from unicast routing that an optimization
or a constraint must be applied to the entire tree instead of a single
path. There are several well-known multicast routing problems. The Steiner
tree problem is to find the least-cost tree, the tree covering a group
of destinations with the minimum total cost over all links. The constrained
Steiner tree problem is to find the least-cost tree with bounded delay.
The delay-delay-jitter-constrained multicast routing problem belongs to
the multi-tree-constrained routing problem class. The above multicast routing
problems are all NP-complete.
4. Introduction of QoS Algorithms
There are some requirements for a routing algorithm:
There are three routing strategies: source routing, distributed routing and hierarchical routing. They are classified according to how the state information is maintained and how the search of feasible paths is carried on[3].
In this subsection, only the list of the various routing algorithms is given. The more detailed content of this subsection can be found in [3] and its references.
4.3.1. Unicast Routing Algorithms
Source routing algorithms
- Wang-Crowcraft algorithm
- Guerin-Orda algorithm
- Chen-Nahrstedt algorithm
- Awerbuch et al. algorithm
The above algorithms required global state to be maintained at every
node. Most algorithms transform the routing problem to a shortest-path
problem and then solve it by Dijkstra's or the Bellman-Ford algorithm.
Distributed routing algorithm
- Wang-Crowcroft algorithm
- Salama et al. algorithm
- Sun-Landgendorfer algorithm
- Cidon et al. algorithm
- Shin-Chou algorithm
- Chen-Nahrstedt algorithm
- Ticket-Based Probing
Hierarchical routing algorithm
- PNNI
4.3.2. Multicast routing algorithms
Source routing algorithms
- MOSPF
- Kou et al. algorithm
- Takahashi-Matsuyama algorithm
- Kompella et al. algorithm
- Sun-Langendoerfer algorithm
- Widyono algorithm
- Zhu et al. algorithm
- Rouskas-Baldine algorithm
All the above algorithms require global state to be maintained at every node. Most heuristic algorithm for the NP-complete multicast routing problems construct a constrained tree incrementally by adding one destination into the tree each time based on certain selection criteria.
Distributed routing algorithm
- Kompella et al. algorithm
- Chen-Nahrstedt algorithm
- Carlberg-Crowcoft algorithm
5. Possible extensions to QoS Routing
5.1. Efficient unicast/multicast routing algorithms
Most source heuristic algorithms for the NP-complete routing problems are not scalable due to prohibitively high time to complexity, especially in the case of multicast routing. New efficient algorithms are required to achieve a good balance between the computation time and the connection-success ratio so that the time complexity can be reduced to the shortest-path computation range while the success ratio is still acceptable. The more dynamic and adaptive routing algorithms are possibly based on the fuzzy or intelligent theory.
5.2. routing with imprecise state information
Most existing routing algorithms assume the availability of precise state information. However, state information is inherently imprecise in a distributed network environment. The imprecision directly affects routing performance. Therefore, the design of routing algorithms for large networks should take the information imprecision into consideration.
5.3. routing in network advance reservation
Advance reservation are likely to become increasingly important as networks and distributed application become functionally richer, and there has been a number of previous works and investigations that have explored various related aspects. The impact of advance reservations on path selection is a topic that has been left largely untouched. There are several service models for advance reservations, which range from the traditional basic model of reserving a given amount of bandwidth for sometime in the future, to more sophisticated models aimed at increasing the flexibility of services available through advance reservations.
5.4. QoS routing in wireless networks
The emergence of nomadic applications have generated a lot of interest in wireless network infrastructures which support multimedia services. The QoS routing can inform the source of the bandwidth and quality of service available to any destinations in the wireless network. It also enables the establishment of QoS connection within the wireless networks and the efficient support of real time, multimedia traffic.
5.5. integration with or extensions to IntServ or DiffServ model
The QoS architectures of IntServ and DiffServ provide the need for QoS routing, however, the considerations on the implementation of QoS under these architectures are incomplete. The interfaces to other components in these architectures need to be specified.
[1] Apostolopoulos, G. & Guerin,
R. & Kamat, S. & Orda, A. & Tripathi, S.,
Intra-Domain QoS Routing in IP Networks: A Feasibility and Cost/Benefit
Analysis. [Referred 28.10.1999]
< http://www.seas.upenn.edu/~guerin
>
[2] Braden, R. & Zhang,
L. & Berson, S. & Herzog, S. & Jamin, S.,
Resource ReSerVation Protocol (RSVP) --Version 1 Functional Specification,
RFC 2205, September 1997. [Referred 28.10.1999]
< ftp://ftp.isi.edu/in-notes/rfc2205.txt
>
[3] Chen, S. & Nahrstedt, K., An overview of quality of service routing for next-generation high-speed networks: problems and solutions, IEEE Network Volume: 12 6 , November/December 1998 , Page(s): 64 -79. [Referred 28.10.1999]
[4] Crawley, E. & Nair,
R. & Rajagopalan, B . & Sandick, H. , A Framework for QoS-based
Routing in the Internet, RFC 2386, August 1998. [Referred 28.10.1999]
< ftp://ftp.isi.edu/in-notes/rfc2386.txt
>
[5] Guerin, R & Kammat, S.,
Implementation and Performance Measurements of QoS Routing Extensions to
OSPF." Proceedings 9of INFOCOM'99, New York, NY, March 1999. [Referred
28.10.1999]
< http://www.seas.upenn.edu/~guerin/qos_ospf.html
>
[6] Guerin, R. & Orda, A. & Williams, D., QoS routing mechanisms and OSPF extensions, Global Telecommunications Conference, 1997. GLOBECOM '97., IEEE Volume: 3 , 1997 , Page(s): 1903 -1908 vol.3. [Referred 28.10.1999]
[7] Moy, J., OSPF Version
2, RFC 2328, April 1998. [Referred 28.10.1999]
< ftp://ftp.isi.edu/in-notes/rfc2328.txt
>
[8] Schmitt, J. & Wolf,
L. C., Quality of Service-An overview. [Referred 28.10.1999]
< http://www.kom.e-technik.tu-darmstadt.de/~lars/publications.html
>
[9] Steinmetz, R. & Wolf,
L.C., Quality of Service-Where are we?. May, 1997. [Referred 28.10.1999]
< http://www.kom.e-technik.tu-darmstadt.de/~lars/publications.html#HEADING1-6
>
[10] Zheng, W. & Crowcroft, J., Quality-of-service routing for supporting multimedia applications, Selected Areas in Communications, IEEE Journal on Volume: 14 7 , Sept. 1996 , Page(s): 1228 -1234 . [Referred 28.10.1999]
[1] Chen, T. & Tsai, J.T. & Gerla, M., QoS routing performance in multihop, multimedia, wireless networks, Universal Personal Communications Record, 1997. Conference Record., 1997 IEEE 6th International Conference on Volume: 2 , 1997 , Page(s): 557 -561 vol.2 . [Referred 28.10.1999]
[2] Guerin, R. & Kammat,
S. & Tripathi, D.K., Quality of Service Routing: A Performance
Perspective , Computer Communication Review, a publication of ACM
SIGCOMM, volume 28, number 4, October 1998. ISSN #0146-4833. [Referred
28.10.1999]
< http://www.acm.org/sigcomm/sigcomm98/tp/abs_02.html
>
[3] Nelakuditi, S. & Tsang, R.P. & Zhang, Z., Quality of service Routing without global information exchange, Quality of Service, 1999, IWQoS'99, 1999 Seventh International Wotkshop on, 1999, pages(s): 129-131. [Referred 28.10..1999]
[4] Shaikh, A. & Rexford, J. & Shin, K. G., Evaluating the overhead of cource-directed Quality of Service routing, Network Protocols, 1998, Proceedings. Sixth International Conference on, 1998. Page(s): 42-51. [Referred 28.10.1999]
[5] Vogel, R. & Herrtwich, R.G.
& Kalfa, W. & Wittig, H. & Wolf, L.C.,
QoS-Based Routing of Multimedia Streams in Computer Networks, IEEE Journal
on Selected Areas in Communications, Special Issue on Distributed Multimedia
Systems and Technology, Vol. 14, No.7, September 1996, pp. 1235-1244. [Referred
28.10.1999]
< http://www.kom.e-technik.tu-darmstadt.de/~lars/publications.html
>