QoS Routing in the Evolving Internet

Turgay Korkmaz, PhD.

Assistant Professor

Department of Computer Science

The University of Texas at San Antonio

The current Internet supports a best-effort service, in which data packets are delivered through the network without any guarantees on the anticipated packet delivery time or the packet loss rate. Although this best-effort service has been successfully used for supporting traditional network applications (e.g., e-mail, file transfer), it does not meet the demands of newly emerging distributed multimedia applications (e.g., video conferencing, Internet telephony), which require a priori guarantees on throughput, packet delivery time, and packet loss rate. This has motivated the development of new networking technologies (e.g., Intserv, Diffserv,MPLS) that are geared towards providing quality-of-service (QoS) guarantees and/or differentiations to prospective flows.

One of the key issues in providing QoS guarantees is how to determine a path that can satisfy users' QoS requirements while efficiently using the underlying network resources. In this talk, we discuss several key issues in QoS routing and present our proposed solutions that can be integrated into evolving state-dependent and hierarchical routing protocols (e.g., QoS-extended OSPF). First, we describe a hybrid mechanism developed based on both flooding and tree-based broadcasting for reliable and efficient dissemination of dynamic link-state parameters, such as bandwidth. Second, we present a scalable, source-oriented state aggregation methodology for hierarchical networks. Third, we introduce several heuristics and approximation algorithms for path selection under multiple QoS constraints, which is known to be an NP-complete problem. Fourth, we consider the path selection problem under inaccurate (probabilistically

modeled) state information, and provide a heuristic for a special yet important case of this problem, namely, routing under bandwidth and delay constraints. Finally, we give directions for future research.