TY - GEN

T1 - Minimizing average latency in oblivious routing

AU - Harsha, Prahladh

AU - Hayes, Thomas P.

AU - Narayanan, Hariharan

AU - Radhakrishnan, Jaikumar

AU - Rácke, Harald

PY - 2008

Y1 - 2008

N2 - We consider the problem of minimizing average latency cost while obliviously routing traffic in a network with linear latency functions. This is roughly equivalent to minimizing the function Σe(load(e)) 2 where for a network link e, load(e) denotes the amount of traffic that has to be forwarded by the link. We show that for the case when all routing requests are directed to a single target, there is a routing scheme with competitive ratio O(log n), where n denotes the number of nodes in the network. As a lower bound we show that no oblivious scheme can obtain a competitive ratio of better than Ω(√log n). This latter result gives a qualitative difference in the performance that can be achieved by oblivious algorithms and by adaptive online algorithms, respectively, since there exist a constant competitive online routing algorithm for the cost-measure of average latency[2]. Such a qualitative difference (in general undirected networks) between the performance of online algorithms and oblivious algorithms was not known for other cost measures (e.g. edge-congestion).

AB - We consider the problem of minimizing average latency cost while obliviously routing traffic in a network with linear latency functions. This is roughly equivalent to minimizing the function Σe(load(e)) 2 where for a network link e, load(e) denotes the amount of traffic that has to be forwarded by the link. We show that for the case when all routing requests are directed to a single target, there is a routing scheme with competitive ratio O(log n), where n denotes the number of nodes in the network. As a lower bound we show that no oblivious scheme can obtain a competitive ratio of better than Ω(√log n). This latter result gives a qualitative difference in the performance that can be achieved by oblivious algorithms and by adaptive online algorithms, respectively, since there exist a constant competitive online routing algorithm for the cost-measure of average latency[2]. Such a qualitative difference (in general undirected networks) between the performance of online algorithms and oblivious algorithms was not known for other cost measures (e.g. edge-congestion).

UR - http://www.scopus.com/inward/record.url?scp=58449110068&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449110068

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 200

EP - 207

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -