Distributed Online Call Control on General Networks
The internet is increasingly used to transmit data of real-time applications such as audio and video. Thus, the provisioning of Quality-of-Service over the internet is becoming of key importance. In this work we consider the problem of the online admission and routing of connection requests, each one requesting the reservation of end-to-end bandwidth between the communicating parties. This problem is many times referred to as the "call control problem". We give novel online randomized algorithms on general network topologies, that with high probability achieve at least a polylogarithmic fraction of the optimal solution.
The decisions of our new algorithms do not depend on the current load of {\em all} network links, as in previous algorithms for general network topologies (the Awerbuch, Azar, Plotkin algorithm of 1993). Instead, their admission decisions depend only on link loads along a single path between the communicating parties. They can thus be performed in a distributed hop-by-hop manner through the network. Furthermore, our algorithms can handle concurrent requests in the network. These properties make our algorithms applicable in the framework of existing internet protocols.
Joint work with Harald Raecke.