Distributed online call control on general networks

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 polylogarithmic 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.