The Project

Traffic on the internet is directed by routers. When a router receives a request, it makes a decision about where to send that request based on its knowledge about the state of the network. Routers can only perform simple operations, and there is a limited amount of space in each routing table for storing data about the network. A goal of routing algorithms is to increase the probability of delivering packets quickly and successfully using only this limited information.

QoS stands for Quality of Service. It represents constraints imposed on connection requests. When establishing a connection, routers must attempt to satisfy these restraints, which may include delay, delay jitter, and bandwidth requirements. QoS is especially important in the context of today's internet, which has an increasingly large number of streaming multimedia services. While delay jitter doesn't make much of a difference when sending email or downloading files, it can make a huge difference in services such as video conferencing, where irregularly spaced packets can distort the end result.

Unicast, Multicast, and Anycast
Unicast routing involves one sender and one recipient, such as an email to a colleague. Multicast designates a system with one sender and multiple recipients, such as a memo sent to everyone in a department. Anycast routing involves one sender and one recipient chosen from a group of possible recipients. A busy website could be kept on mirrors in several locations, for example, and when a user requests that website the routers involved must pick one of the mirrors. Ideally, the mirror chosen should be close and reachable by a path with high bandwidth, but it is often difficult to achieve this result with the limited information available to most routers.

Several problems arise when dealing with algorithms for anycast routing. It would be easy to select a "good" destination if enough information about the state of the network were available to every router. In reality, this is costly and impractical. Routing algorithms should be compatible with the current infrastructure of the internet, with any extra information needed being accessible through existing protocols. Another problem arises when, in some cases, it is possible for a loop to occur in the path from source to destination. Practical routing algorithms must take care to avoid the possibility of loops. Finally, a router's information about the rest of the network may be inaccurate, and it is useful for algorithms to take this into account when selecting a target from the anycast recipient group.

The Project
Working with Professor Jianer Chen, I will be spending this summer working on algorithms for anycast routing. We will consider QoS, as well as inaccurate link-state information. Using mathematical analysis and computer simulation, we will evaluate the performance of various anycast routing techniques and compare the results to those produced by our own algorithms. In addition to developing new algorithms, we hope to gain a better understanding of the theory behind this increasingly-important type of routing.

Home Site Index