Bandwidth allocation with preemption

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Bandwidth allocation with preemption

Full text

Pdf (1.02 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-seventh annual ACM symposium on Theory of computing table of contents

Las Vegas, Nevada, United States

Pages: 616 - 625

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Amotz Bar-Noy	IBM Research Division, T.J. Watson Research, Center, Yorktown Heights, NY
Ran Canetti	Dept. of Applied Mathematics & Computer Science, Weizmann Institute, Israel
Shay Kutten	IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY
Yishay Mansour	Computer Science Department, Tel-Aviv University, Israel
Baruch Schieber	IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 20, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/225058.225279 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line load balancing with applications to machine scheduling and virtual circuit routing, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.623-631, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167248]
	2	B. Awerbuch, Y. Azar% and S. Plotkin. Throughput-competitive of on-line routing, In PTOC. 30th IEEE $ymp, on Foundations of C'omputeT Science, pages 32-40, 1993.
	3	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
	4	B. Awerbuch, R. Gawlick, T, Leighton and Y. Ra-bani. On-line Admission Control and Circuit Rout-ing for High Performance Computing and Commu-nication, In PTOC. 35th IEEE Symp. on I'ounda-tions of Compute~ Science, pages 412-423, 1994.
	5	Special Issue on Asynchronous Transfer Mode. Int. Journal of Digital and Analog Cabled Systems, 1(4), 1988.
	6	A. Bar-Noy , R. Canetti , S. Kutten , Y. Mansour , B. Schieber, Bandwidth Allocation with Preemption, Weizmann Science Press of Israel, Jerusalem, Israel, 1995
	7	S. Baruah, G. Koren, D. Mao, B. Mishra, A. Raghunathan, L. Rosier, D. Shasha, and F. Wang. On the competitiveness of on-line real-time task scheduling. In PTOC. 32nd IEEE Symp. on Real Time Systems, pages 106-115, December 1991,
	8	S. Baruah , G. Koren , B. Mishra , A. Raghunathan , L. Rosier , D. Shasha, On-line scheduling in the presence of overload, Proceedings of the 32nd annual symposium on Foundations of computer science, p.100-110, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185354]
	9	Ran Canetti , Sandy Irani, Bounding the power of preemption in randomized scheduling, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.606-615, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225278]
	10	L Cidon and I. Gopal. PARIS: An approach to in-tegrated high-speed private networks. Int. Journal of Digital and Analog Cabled Systems, 1(2):77-86, 1988.
	11	P. F. Chimento, J. E. Drake, L. Gum, W. A. Her-vatic, C. P. Immanuel, G. A. Ma,rin, R. O. On-vural, S. A. Owen and T. E. Tedijanto. Broad-band Network Services for High Speed Multimedia Networks. an IBM publication, I13M, Networking Systems Architecture, P.O. Box 12195, Triangle Research Park, NC 27709.
	13	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
	14	J.A. Garay, 1.S. Gopal, S. Kutten, Y. Mansour, and M. Yung. Efficient on-line call control algo-rithms. In Proc. 2nd IsTael Conf, on TheoTy of Computing and Systems, pages 28$-293, 1993.
	15	G. Koren and D. Shasha. Dover: An optimal on-line scheduling algorithm for overloaded real-time systems, TR 594, Courant Institute, New York University, 1992.
	16	R. Lipton, Online interval scheduling, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.302-311, January 23-25, 1994, Arlington, Virginia, United States
	18	K. K. Ramakrishnan , Lev Vaitzblit , Cary G. Gray , Uresh Vahalia , Dennis Ting , Percy Tzelnic , Steve Glaser , Wayne Duso, Operating System Support for a Video-On-Demand File Service, Proceedings of the 4th International Workshop on Network and Operating System Support for Digital Audio and Video, p.216-227, November 03-05, 1993
	20	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]
	22	Fuxing Wang , Decao Mao, Worst Case Analysis for On-Line Scheduling in Real-Time Systems, University of Massachusetts, Amherst, MA, 1991

CITED BY 13

	Amotz Bar-Noy , Yishay Mansour , Baruch Schieber, Competitive dynamic bandwidth allocation, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.31-39, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Leslie Ann Goldberg , Mike Paterson , Aravind Srinivasan , Elizabeth Sweedyk, Better approximation guarantees for job-shop scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.599-608, January 05-07, 1997, New Orleans, Louisiana, United States
	Ran Adler , Yossi Azar, Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 17-19, 1999, Baltimore, Maryland, United States
	Michael H. Goldwasser, Patience is a virtue: the effect of slack on competitiveness for admission control, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.396-405, January 17-19, 1999, Baltimore, Maryland, United States
	Gilad Koren , Amihood Amir , Emanuel Dar, The power of migration in multi-processor scheduling of real-time systems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.226-235, January 25-27, 1998, San Francisco, California, United States
	Ran Canetti , Sandy Irani, Bounding the power of preemption in randomized scheduling, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.606-615, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Minos N. Garofalakis , Yannis E. Ioannidis , Banu Özden , Avi Silberschatz, Throughput-competitive admission control for continuous media databases, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.79-88, June 01-04, 1998, Seattle, Washington, United States
	Eric Bach , Joan Boyar , Leah Epstein , Lene M. Favrholdt , Tao Jiang , Kim S. Larsen , Guo-Hui Lin , Rob Van Stee, Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem, Journal of Scheduling, v.6 n.2, p.131-147, March/April 2003
	Ran Adler , Yossi Azar, Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms, Journal of Scheduling, v.6 n.2, p.113-129, March/April 2003
	Michael H. Goldwasser , Boris Kerbikov, Admission control with immediate notification, Journal of Scheduling, v.6 n.3, p.269-285, May/June 2003
	S. S. Manvi , P. Venkataram, An agent based adaptive bandwidth allocation scheme for multimedia applications, Journal of Systems and Software, v.75 n.3, p.305-318, March 2005
	Minos Garofalakis , Yannis Ioannidis , Banu Özden , Avi Silberschatz, Competitive on-line scheduling of continuous-media streams, Journal of Computer and System Sciences, v.64 n.2, p.219-248, March 2002
	Cory Beard, Preemptive and delay-based mechanisms to provide preference to emergency traffic, Computer Networks and ISDN Systems, v.47 n.6, p.801-824, 22 April 2005