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))², 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).

REFERENCES

• 1: David Applegate , Edith Cohen, Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863991]
• 2: B. Awerbuch , Y. Azar , E. F. Grove , Ming-Yang Kao , P. Krishnan , J. S. Vitter, Load balancing in the L/sub p/ norm, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.383, October 23-25, 1995
• 3: Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Racke, Optimal oblivious routing in polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780599]
• 4: P. G. Doyle and J. L. Snell, Random Walks and Electric Networks, Mathematical Association of America, 1984.
• 5: Anupam Gupta , Mohammad T. Hajiaghayi , Harald Räcke, Oblivious network design, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.970-979, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109665]
• 6: MohammadTaghi Hajiaghayi , Jeong Han Kim , Tom Leighton , Harald Räcke, Oblivious routing in directed graphs with random demands, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060619]
• 7: Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton , Harald Räcke, Oblivious routing on node-capacitated and directed graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777419]
• 9: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 10: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 11: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Algorithms, Design, Theory