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 -