Minimizing average latency in oblivious routing
Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan · 2008
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 [AAG+ in a distributed environment, which makes them very attractive from a practical point of view. However, an important question in this area is whether obliviousness is too simplistic an approach to guarantee good routing performance, and whether one has to resort to adaptive protocols instead. For undirected networks it has been shown that oblivious algorithms perform remarkably well for several costfunctions. Work in this area was initiated by Valiant and Brebner [VB81] who developed an oblivious routing protocol for routing in the hypercube that routes any permutation in time that is only a logarithmic factor away from optimal. For the cost-measure congestion (the maximum load of a network link) in a virtual circuit routing model, Räcke [Räc02] proved the existence of an oblivious routing scheme with polylogarithmic competitive 95]. ratio for any undirected network. This result was subse-Such a qualitative difference (in general undirected netquently made constructive by Harrelson, Hildrum and works) between the performance of online algorithms Rao [HHR03] and improved to a competitive ratio of and oblivious algorithms was not known for other cost O(log measures (e.g. edge-congestion). 1