James Aspnes
Amos Fiat
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.
- SPECIAL ISSUE ON ASYNCHRONOUS TRANSFER MODE. Int. J. Digital Analog Cabled Syst. 1, 4, 1988.Google Scholar
- 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.Google Scholar
- AWERBUCH, B., AND AZAR, Y. 1995. Competitive multicast routing. Wireless Netw. 1, 107-114. Google ScholarDigital Library
- 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.Google Scholar
- AWERBUCH, B., AZAR, Y., GROVE, E., KAO, M., KRISHNAN, P., AND VITTER, J. 1995. Load balancing in the lp norm. In Proceedings of the 36th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 383-391. Google Scholar
- 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.Google Scholar
- AWERBUCH, B., AZAR, Y., PLOTKIN, S., AND WAARTS, 0. 1994. Competitive routing of virtual circuits with unknown duration. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 321-327. Google Scholar
- 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.Google Scholar
- AWERBUCH, B., BARTAL, Y., FIAT, A., AND ROSEN, A. 1994b. Competitive nonpreemptive call control. In Proceedings of the 5th A CM-SIAM Symposium on Discrete Algorithms. Google Scholar
- 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.Google Scholar
- AZAR, Y., KALYANASUNDARAM, B., PLOTKIN, S., PRUHS, K., AND WAARTS, O. 1993. On-line load balancing of temporary tasks. In Proceedings of the Workshop on Algorithms and Data Structures. (Aug.). pp. 119-130. Google Scholar
- AZAR, Y., NAOR, J., AND ROM, R. 1992. The competitiveness of on-line assignments. In Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms (Orlando, Fla. Jan. 27-29). ACM, New York, pp. 203-210. Google Scholar
- BARTAL, Y., FIAT, A., KARLOFF, H., AND VOHRA, R. 1992. New algorithms for an ancient scheduling problem. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 51-58. Google Scholar
- BORODIN, A., LINIAL, N., AND SAKS, M. 1992. An optimal online algorithm for metrical task systems. J. ACM 39, 4 (Oct.), 745-763. Google ScholarDigital Library
- 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.Google Scholar
- GARAY, J. A., AND GOPAL, I.S. 1992. Call preemption in communication networks. In Proceedings of INFOCOM '92, vol. 44. (Florence, Italy). pp. 1043-1050. Google Scholar
- GAWLICK, R., KALMANEK, C., AND RAMAKRISHNAN, K. 1995a. On-line permanent virtual circuit routing. In Proceedings of IEEE Infocom (Apr.). IEEE, New York. Google Scholar
- GAWLICK, R., KAMATH, A., PLOTKIN, S., AND RAMAKRISHNAN, K. 1995b. Routing and admission control in general topology networks. Tech. Rep. STAN-CS-TR-95-1548. Stanford Univ., Stanford, CA. Google Scholar
- GRAHAM, R. L. 1966. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563-1581.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- KAMATH, A., PALMON, O., AND PLOTKIN, S. 1996. Routing and admission control in general topology networks with poisson arrivals. In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, pp. 269-278. Google Scholar
- KARGER, D., PHILLIPS, S., AND TORNG, E. 1993. A better algorithm for an ancient scheduling problem. Unpublished manuscript.Google Scholar
- KARGER, D., AND PLOTKIN, S. 1995. Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (Las Vegas, Nev., May 29-June 1). ACM, New York, pp. 18-25. Google Scholar
- KARLIN, A. R., MANASSE, M. S., RUDOLPH, L., AND SLEATOR, D. D. 1988. Competitive snoopy caching. Algorithmica 1, 3, 70-119.Google Scholar
- KARP, R., VAZIRANI, U., AND VAZIRANI, g. 1990. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing (Baltimore, Md., May 14-16). ACM, New York, 352-358. Google Scholar
- KLEIN, P., PLOTKIN, S., STEIN, C., AND TARDOS, 1#. 1994. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM J. Comput. 23, 3, 466-487. Google ScholarDigital Library
- KLEINBERG, J., AND TARDOS, IE. 1995. Disjoint path in densely embedded graphs. In Proceedings of the 36th IEEE Annual Symposium on Foundations of Computer Science. IEEE, New York. Google Scholar
- LEIGHTON, T., MAKEDON, F., PLOTKIN, S., STEIN, C., TARDOS, t#., AND TRAGOUDAS, S. 1995. Fast approximation algorithms for multicommodity flow problem. J. Comput. Syst. Sci. 50, 228-243. Google ScholarDigital Library
- HA, Y., AND PLOTKIN, S. 1996. Improved lower bounds for load balancing of tasks with unknown duration. Tech. Rep. STAN-CS-TN 96-37. Stanford Univ., Stanford, Calif. Google Scholar
- MANASSE, M. S., MCGEOCH, L. A., AND SLEATOR, D.D. 1988. Competitive algorithms for on-line problems. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, (Chicago, Ill., May 2-4). ACM, New York, pp. 322-332. Google Scholar
- PHILLIPS, S., AND WESTBROOK, J. 1993. Online load balancing and network flow. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, (San Diego, Calif., May 16-18) ACM, New York, pp. 402-411. Google Scholar
- 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.).Google ScholarDigital Library
- PLOTKIN, S., SHMOYS, D., AND TARDOS, }#. 1995. Fast approximation algorithms for fractional packing and covering problems. Math. Op. Res. 20, 2, 257-301. Google ScholarDigital Library
- SHAHROKHI, F., AND MATULA, D. 1990. The maximum concurrent flow problem. J. ACM 37, 2 (Apr.), 318-334. Google ScholarDigital Library
- SHMOYS, D., WEIN, J., AND WILLIAMSON, D. P. 1991. Scheduling parallel machines on-line. In Proceedings of the 32nd IEEE Annual Symposium on Foundations of Computer Science. IEEE, New York, pp. 131-140. Google ScholarDigital Library
- SLEATOR, D. D., AND TARJAN, R.E. 1985. Amortized efficiency of list update and paging rules. Commun. ACM 28 2 (Feb.), 202-208. Google Scholar
- TAKAHASHI, H., AND MATSUYAMA, A. 1980. An approximate solution for the Steiner problem in graphs. Math. Japonica, 24.Google Scholar
Index Terms
- On-line routing of virtual circuits with applications to load balancing and machine scheduling
Recommendations
Routing with load balancing: increasing the guaranteed node traffics
In this paper we introduce the novel routing scheme based on load balancing and shortest-path routing. First, we present the linear program for routing optimization. The nonblocking network is considered, which only limits the traffic loads of the ...
Optimal on-line flow time with resource augmentation
Special issue: Efficient algorithmsWe study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which ...
On-line algorithms for 2-space bounded 2-dimensional bin packing
In 2-space bounded model of on-line bin packing, there are 2 active bins, and each item can be packed only into one of the active bins. If it is impossible to pack an item into any active bin, we close one of the current active bins and open a new ...
Reviews
Douglas M. Campbell
Point-to-point circuit routing is a generalization of online load balancing. Jobs arrive online and must be assigned immediately. Assigning a job to a machine increases the machine's load according to a load vector. All coordinates of the load vector are the same if all machines are related. If the machines are unrelated, then the coordinates are either infinity or a value that depends only on the job (not the machine). The goal is to minimize the maximum load. The effectiveness of an online algorithm is its competitive ratio: the ratio of the maximum relative load of the online algorithm to the maximum relative load achieved by an optimal offline algorithm as a function of n, the number of nodes in a network. The paper gives an algorithm that achieves a constant competitive ratio when the machines are related. It also gives an algorithm that achieves an O log n competitive ratio when the machines are unrelated. The result is tight in a directed network. That is, for any online algorithms in a directed network, there exists a scenario in which a log n increase in bandwidth is necessary. The paper contrasts these bounds with the bounds (which it proves) for a natural greedy approach. If the machines are related, the greedy approach has a competitive ratio of log n ; if the machines are unrelated, it has a competitive ratio of n . The paper solves the multicast online allocation problem by modifying its point-to-point algorithm to route over min-weight Steiner trees instead of min-weight paths. The same big-Oh bounds hold for multicast upon using a 2-approximation to the NP-hard problem of determining a min-weight Steiner tree.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments