On-line routing of virtual circuits with applications to load balancing and machine scheduling

ABSTRACT

In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to route all requests while minimizing the required bandwidth. We concentrate on the case of Permanent virtual circuits (i.e., once a circuit is established it exists forever), and describe an algorithm that achieves on O (log n) competitive ratio with respect to maximum congestin, where nis the number of nodes in the network. Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an O (log n) factor. We also show that this result is tight, that is, for any on-line algorithm there exists a scenario in which ***(log n) increase in bandwidth is necessary in directed networks. We view virtual circuit routing as a generalization of an on-line load balancing problem, defined as follows: jobs arrive on line and each job must be assigned to one of the machines immediately upon arrival. Assigning a job to a machine increases the machine's load by an amount that depends both on the job and on the machine. The goal is to minimize the maximum load. For the related machines case, we describe the first algorithm that achieves constant competitive ratio. for the unrelated case (with nmachines), we describe a new method that yields O(logn)-competitive algorithm. This stands in contrast to the natural greed approach, whose competitive ratio is exactly n. show that this result is tight, that is, for any on-line algorithm there exists a scenario in which ***(log n) increase in bandwidth is necessary in directed networks.

REFERENCES

• 1: SPECIAL ISSUE ON ASYNCHRONOUS TRANSFER MODE. Int. J. Digital Analog Cabled Syst. 1, 4, 1988.
• 2: AWERBUCH, B., AND AZAR, Y. 1994. Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 240-249.
• 3: Baruch Awerbuch , Yossi Azar, Competitive multicast routing, Wireless Networks, v.1 n.1, p.107-114, Feb. 1995 [doi>10.1007/BF01196262]
• 4: AWERBUCH, B., AZAR, f., AND FIAT, A. 1996. Packet routing via min-cost circuit routing. In Proceedings of the 4th Israeli Symposium on Theory of Computing and Systems. pp. 37-42.
• 5: 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
• 6: AWERBUCH, B., AZAR, Y., AND PLOTKIN, S. 1993. Throughput competitive on-line routing. In Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science (Nov.). IEEE, New York, pp. 32-40.
• 7: Baruch Awerbuch , Yossi Azar , Serge Plotkin , Orli Waarts, Competitive routing of virtual circuits with unknown duration, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.321-327, January 23-25, 1994, Arlington, Virginia, United States
• 8: AWERBUCH, B., GAWLICK, R., LEIGHTON, T., AND RABANI, Y. 1994a. On-line admission control and circuit routing for high-performance computing and communication. In Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science (Nov.). IEEE, New York, pp. 412-423.
• 9: Baruch Awerbuch , Yair Bartal , Amos Fiat , Adi Rosén, Competitive non-preemptive call control, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.312-320, January 23-25, 1994, Arlington, Virginia, United States
• 10: AZAR, Y., BRODER, A., AND KARLIN, A. 1992. On-line load balancing. In Proceedings of the 33rd IEEE Annual Symposium on Foundations of Computer Science. pp. 218-225.
• 11: Yossi Azar , Bala Kalyanasundaram , Serge A. Plotkin , Kirk Pruhs , Orli Waarts, Online Load Balancing of Temporary Tasks, Proceedings of the Third Workshop on Algorithms and Data Structures, p.119-130, August 11-13, 1993
• 12: Yossi Azar , Joseph Naor , Raphael Rom, The competitiveness of on-line assignments, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.203-210, September 1992, Orlando, Florida, United States
• 13: Yair Bartal , Amos Fiat , Howard Karloff , Rakesh Vohra, New algorithms for an ancient scheduling problem, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.51-58, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129718]
• 14: Allan Borodin , Nathan Linial , Michael E. Saks, An optimal on-line algorithm for metrical task system, Journal of the ACM (JACM), v.39 n.4, p.745-763, Oct. 1992 [doi>10.1145/146585.146588]
• 15: GARAY, J., GOPAL, I., KUTTEN, S., MANSOUR, Y., AND YUNG, M. 1993. Efficient on-line call control algorithms. In Proceedings of 2nd Annual Israel Conference on Theory of Computing and Systems.
• 16: Juan A. Garay , Inder S. Gopal, Call preemption in communication networks, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 3), p.1043-1050, May 1992, Florence, Italy
• 17: R. Gawlick , C. Kalmanek , K. G. Ramakrishnan, On-line routing for permanent virtual circuits, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 1)-Volume, p.278, April 02-06, 1995
• 18: Rainer Gawlick , Anil Kamath , Serge Plotkin , K. G. Ramakrishnan, Routing and Admission Control in General Topology Networks, Stanford University, Stanford, CA, 1995
• 19: GRAHAM, R. L. 1966. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563-1581.
• 20: GRAHAM, R. L., LAWLER, E. L., LENSTRA, J. K., AND RINNOOY NAN, A. H.G. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Disc. Math. 5, 287-326.
• 21: Anil Kamath , Omri Palmon , Serge Plotkin, Routing and admission control in general topology networks with Poisson arrivals, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 28-30, 1996, Atlanta, Georgia, United States
• 22: KARGER, D., PHILLIPS, S., AND TORNG, E. 1993. A better algorithm for an ancient scheduling problem. Unpublished manuscript.
• 23: David Karger , Serge Plotkin, Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.18-25, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225073]
• 24: KARLIN, A. R., MANASSE, M. S., RUDOLPH, L., AND SLEATOR, D. D. 1988. Competitive snoopy caching. Algorithmica 1, 3, 70-119.
• 25: R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]
• 26: Philip Klein , Serge Plotkin , Clifford Stein , Eva Tardos, Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts, SIAM Journal on Computing, v.23 n.3, p.466-487, June 1994 [doi>10.1137/S0097539792241175]
• 27: J. Kzeinberg , E. Tardos, Disjoint paths in densely embedded graphs, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.52, October 23-25, 1995
• 28: Tom Leighton , Fillia Makedon , Serge Plotkin , Clifford Stein , Éva Tardos , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Journal of Computer and System Sciences, v.50 n.2, p.228-243, April 1995
• 29: Serge Plotkin , Yuan Ma, An Improved Lower Bound for Load Balancing of Tasks with Unknown Duration, Stanford University, Stanford, CA, 1996
• 30: Mark Manasse , Lyle McGeoch , Daniel Sleator, Competitive algorithms for on-line problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.322-333, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62243]
• 31: Steven Phillips , Jeffery Westbrook, Online load balancing and network flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.402-411, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167201]
• 32: PLOTKIN, S. 1995. Competitive routing in ATM networks. Special issue on Advances in the Fundamentals of Networking. IEEE J. Select. Areas Commun. 1128-1136. (Aug.).
• 33: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 34: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 35: David B. Shmoys , Joel Wein , David P. Williamson, Scheduling parallel machines on-line, Proceedings of the 32nd annual symposium on Foundations of computer science, p.131-140, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185361]
• 36: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 37: TAKAHASHI, H., AND MATSUYAMA, A. 1980. An approximate solution for the Steiner problem in graphs. Math. Japonica, 24.

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms, Theory

Keywords:
high-speed networks, on-line algorithms, optimization, routing