A study of demand oblivious routing algorithms

Abstract

Nowadays, people make use of communication networks (e.g. Internet) everyday and expect high quality from the offered services. Providing a good quality of service and optimizing the utilization of the network resources are the main objectives in designing a routing. It has always been believed that traffic demands play an important role in this design because the better the traffic demands are known, the more properly they can be allocated. However, understanding and estimating these traffic demands is not a trivial task. In 2002 Räcke asked himself an important question: ``how important is accurate knowledge of traffic demands for obtaining good utilization of the network?" This marked the beginning of a new kind of routing algorithms: the demand oblivious routing algorithms or oblivious routing. These routing algorithms ignore the current status of the network when making routing decisions and they only base their decisions on the source, destination of the flows and, in certain cases, some random values. These kind of algorithms have evolved a lot during the last years in three different directions. Nevertheless, according to the knowledge of the author, there has been no study until now that evaluates the performance of algorithms from these three branches. Firstly, this thesis will present a complete and exhaustive study based on the three papers that originated the different kinds of oblivious routing. Then, a framework will be developed to compare these three algorithms under the same conditions and with a range of metrics from theoretical calculations to more practical ones. Finally, based on the results obtained, possible improvements for these families of algorithms will be suggested.