Paper Info
Title
Minimizing average latency in oblivious routing
Abstract
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).
Year
DOI
Venue
2008
10.5555/1347082.1347105
SODA
Keywords
Field
DocType
average latency,oblivious algorithm,competitive ratio,average latency cost,oblivious routing,adaptive online algorithm,qualitative difference,routing scheme,log n,routing request,obliviously routing traffic,lower bound,online algorithm
Discrete mathematics,Online algorithm,Topology,Mathematical optimization,Link-state routing protocol,Multipath routing,Dynamic Source Routing,Latency (engineering),Upper and lower bounds,Computer science,Destination-Sequenced Distance Vector routing,Competitive analysis
Conference
ISBN
Citations 
PageRank 
978-0-89871-698-6
7
0.50
References 
Authors
8
5
Name
Order
Citations
PageRank
Prahladh Harsha137132.06
Thomas P. Hayes265954.21
Hariharan Narayanan311612.70
Harald Räcke482148.28
Jaikumar Radhakrishnan5112396.04