ICS Theory Group

ICS 269, Fall 2005: Theory Seminar

Distributed Online Call Control on General Networks

John Augustine

November 4, 2005, in CS 259


This talk will be a presentation of a paper by Harald Räcke, and Adi Rosén from SODA 2005.

We study the problem of online call admission and routing ("call control") on general networks. We give new algorithms that with high probability achieve a poly-logarithmic fraction (in the size of the network) of the optimal solution. The decisions of our algorithms do not depend on the current load of all network links, as in previous algorithms for general network topologies [AAP93]. Instead, their admission decisions depend only on link loads along a single path between the communicating parties, and they can thus be performed in a distributed hop-by-hop manner through the network. Furthemore, our algorithms can handle concurrent requests in the network.