Quality of Service Routing in Internet (White Paper) Klara Nahrstedt Computer Science Department University of Illinois at Urbana-Champaign Internet became very fast growing and heavy loaded resource due to (1) large connectivity of PCs and workstations via academic and corporation- based networks such as Ethernet, FDDI, ATM and others and via distribution networks such as telephone networks; (2) computational support of media-rich environments such as digital images, audio, video, animation and virtual reality environments; (3) multimedia input/output devices with compression cards on end-host platforms; and (4) WWW and its browsers performance and accessibility. Due to all these factors, the performance of data delivery over Internet degrades which hits hard especially delivery of audio, video and other time and bandwidth sensitive media. Various partial solutions are used to deliver and guarantee timing and bandwidth constrains of continuous media such as local processing of continuous media only, donwloading of audio/video data to closely located servers, performing prefetching to proxy servers closely located to the users and other approaches moving data close to the user so that high-bandwidth and timely delivery can be guaranteed. However, these approaches satisfy only retrieval multimedia applications. How about interactive and conversational multimedia applications such as video conferencing, video- telephony, or tele-operations which need high-bandwidth and timely delivery over wide area networks from East Coast to West Coast? Even retrieval applications would benefit from high- bandwidth and timely guarantees for example in delivering hypermedia documents from Library of Congress to Urbana-Champaign. There are many changes which need to be put in place in current Internet to improve the performance of the shared network resource and quality of delivered digital media such as video and audio for future applications. Improved Internet means increase of users acceptance and revenues. One of the changes which need to be done to improve Internet performance for multimedia traffic is the routing of IP packets. We believe that the IP routing will need to be based on QoS requirements such as bandwidth and timing constraints. This will require changes in state information at the routers and change in protocols determining the routes between sources and destinations. Current routing protocols do not reflect these QoS requirements. For example, the `distance vector' routing algorithm determines the route based on the distance between source and destination. Each router is responsible for keeping track and informing its neighbors of its distance to each destination. The only information a router must know a-priori is its own ID and the cost of its links to each neighbor. For multicasting in mrouters, the `distance vector multicast routing protocol' is used. This protocol is also considered not be adequate for rapidly changing network topologies because the routing information propagates too slowly. More recently, the `link state' protocol was developed. Here, each router is responsible for determining the identities of its neighbors and constructing a `link state packet (LSP)', which lists its neighbors and the cost of the link to each of them. The LSP is transmitted to all of the other routers, which are responsible for storing the most recently generated LSPs. Given this LSP database, it is possible to calculate the route. An example of a LSP protocol, also used in mrouters, is the `open shortest path link state protocol' developed by Steve Deering. We are proposing to expand the routing algorithms based on QoS as follows: We assume that the routers create a directed graph and each router will have in its routing table an entry for its adjacent routers to which a message may be forwarded and a router will have a full knowledge about the link resource availability to any adjacent router such as bandwidth and delay availability. Bandwidth and delay availability information will represent the cost of the link and they will allow us to match the quality of service requirements to the network resource availability. This information can be then put into LSP and distributed similarly to LSP protocol. The question now is, once we have resource state information in the routers, how to determine the routes. We propose a two-phase QoS-based routing protocol. In the first phase using a distributed and recursive algorithm, the calling router side can send request messages to adjacent routers towards the callee router side to inquire possible multiple paths between caller and callee and their resource availability. Due to the recursion each router recursively propagates the request message (if multiple request messages arrive at a node, only one request message is forwarded). Once the callee side is reached, acknowledgment message is sent back with the best possible resource available. For example, if bandwidth is the requested resource, an intermediate router passes to its neighbor on the reverse path the acknowledgment with the minimal bandwidth between two most recent links passed by the acknowledgment from the callee to the intermediate router. Once the acknowledgments traverse along various paths from the callee to the caller router, the caller picks the path with the maximal resource available along the end-to-end paths (e.g., the maximal bandwidth path). Once the caller has the information about the resource availability, the second phase starts with a distributed and recursive algorithm which performs soft reservation similarly to RSVP (Resource reservation protocol). Our protocol utilizes the results of the first phase, and matches the requested QoS to its path resource availability. If the QoS requirement is higher than currently available resource, a rejection message is sent to the end host and the user must wait to transmit traffic. If the QoS requirement is within resource availability bounds, a reservation message is sent along the previously specified path. If some part of the specified route changed its resource availability in between, our protocol reacts dynamically and changes route because the individual results of the first phase are available in routers, hence at each router we can determine which path from there would be more suitable to the callee's side. This two-phase QoS-based routing protocol is currently under development and we apply various optimization algorithms to achieve best performance possible in the Internet environment.