Abstract
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.
| Original language | English |
|---|---|
| Pages | 791-800 |
| Number of pages | 10 |
| State | Published - 2005 |
| Externally published | Yes |
| Event | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: 23 Jan 2005 → 25 Jan 2005 |
Conference
| Conference | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| Country/Territory | United States |
| City | Vancouver, BC |
| Period | 23/01/05 → 25/01/05 |