{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T06:32:38Z","timestamp":1790231558803,"version":"4.1.0"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>Bandwidth allocation is a fundamental problem in the design of networks where bandwidth has to be reserved for connections in advance. The problem is intensified when the overall requested bandwidth exceeds the capacity and not all requests can be served. Furthermore, acceptance\/rejection decisions regarding connections have to be made online, without knowledge of future requests. We show that the ability to preempt (i.e., abort) connections while in service in order to schedule \"more valuable\" connections substantially improves the throughput of some networks. We present bandwidth allocation strategies that use preemption and show that they achieve constant competitiveness with respect to the throughput, given that any single call requests at most a constant fraction of the bandwidth. Our results should be contrasted with recent works showing that nonpreemptive strategies have at most inverse logarithmic competitiveness.<\/jats:p>","DOI":"10.1137\/s0097539797321237","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1806-1828","source":"Crossref","is-referenced-by-count":32,"title":["Bandwidth Allocation with Preemption"],"prefix":"10.1137","volume":"28","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Canetti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Kutten","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts,\n                      Online load balancing with applications to machine scheduling and virtual circuit routing\n                      , in Proceedings Twenty\u2010Fifth ACM Symposium on Theory of Computing, San Diego, CA, 1993, pp. 623\u2013631.","DOI":"10.1145\/167088.167248"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, and S. Plotkin,\n                      Throughput\u2010competitive of online routing\n                      , in Proceedings Thirty\u2010Fourth IEEE Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 32\u201340.","DOI":"10.1109\/SFCS.1993.366884"},{"key":"R3","unstructured":"B. Awerbuch, Y. Bartal, A. Fiat, and A. Ros\u00e9n,\n                      Competitive non\u2010preemptive call control\n                      , in Proceedings of the Fifth Annual ACM\u2010SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 1994, pp. 312\u2013320."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, R. Gawlick, T. Leighton, and Y. Rabani,\n                      Online admission control and circuit routing for high Performance computing and communication\n                      , in Proceedings Thirty\u2010Fifth IEEE Symposium on Foundations of Computer Science, Sante Fe, NM, 1994, pp. 412\u2013423.","DOI":"10.1109\/SFCS.1994.365675"},{"key":"R5","unstructured":"Special Issue on Asynchronous Transfer Mode\n                      . Internat. Digital Analog Cabled Systems, 1 (1988)."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"S. Baruah, G. Koren, D. Mao, B. Mishra, A. Raghunathan, L. Rosier, D. Shasha, and F. Wang,\n                      On the competitiveness of online real\u2010time task scheduling\n                      , in Proceedings Twelfth IEEE Symposium on Real Time Systems, San Antonio, TX, 1991, pp. 106\u2013115.","DOI":"10.1109\/REAL.1991.160364"},{"key":"R7","unstructured":"S. Baruah, G. Koren, B. Mishra, A. Raghunathan, L. Rosier, and D. Shasha,\n                      Online scheduling in the presence of overload\n                      , in Proceedings Thirty\u2010Second IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1991, pp. 101\u2013110."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795283292"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/dac.4520010208"},{"key":"R10","unstructured":"P. F. Chimento, J. E. Drake, L. Gun, W. A. Hervatic, C. P. Immanuel, G. A. Marin, R. O. Onvural, S. A. Owen, and T. E. Tedijanto,\n                      Broadband Network Services for High Speed Multimedia Networks\n                      , Tech report 29.1761, IBM, Research Triangle Park, NC, 1993."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00112-5"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"J. A. Garay and I. S. Gopal,\n                      Call preemption in communication networks\n                      , in Proceedings INFOCOM \u201992, Florence, Italy, 1992, pp. 1043\u20131050.","DOI":"10.1109\/INFCOM.1992.263457"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J. A. Garay, I. S. Gopal, S. Kutten, Y. Mansour, and M. Yung,\n                      Efficient online call control algorithms\n                      , in Proceedings Second Israel Conference on Theory of Computing and Systems, Netanya, Israel, 1993, pp. 285\u2013293.","DOI":"10.1109\/ISTCS.1993.253460"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236882"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90165-1"},{"key":"R16","unstructured":"R. J. Lipton and A. Tomkins,\n                      Online interval scheduling\n                      , in Proceedings Fifth Annual ACM\u2010SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 1994, pp. 302\u2013311."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"C. Lund, S. Phillips, and N. Reingold,\n                      IP over connection\u2010oriented networks and distributional paging\n                      , in Proceedings Thirty\u2010Fifth IEEE Symposium on Foundations of Computer Science, Santa Fe, NM, 1994, pp. 424\u2013434.","DOI":"10.1109\/SFCS.1994.365674"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"K. K. Ramakrishnan, L. Vaitzblit, C. Gray, U. Vahalia, D. Ting, P. Tzelnic, S. Glaser, and W. Duso,\n                      Operating system support for a video\u2010on\u2010demand file service\n                      , in Proceedings Network and Operating System Support for Digital Audio and Video: Fourth International Workshop, Lecture Notes in Comput. Sci. 846, D. Shepherd, G. Blair, G. Coulson, N. Davies, F. Garcia, eds., Springer\u2010Verlag, Berlin, New York, 1994, pp. 216\u2013227.","DOI":"10.1007\/3-540-58404-8_20"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"N. Shacham,\n                      Preemption based admission control in multi media multi party communications\n                      , in Proceedings INFOCOM \u201995, Boston, MA, 1995, pp. 827\u2013834.","DOI":"10.1109\/INFCOM.1995.515953"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793248317"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"F. Toutain and O. Huber,\n                      A general preemption\u2010based admission control policy using smart market approach\n                      , in Proceedings INFOCOM \u201996, San Francisco, CA, 1996, pp. 794\u2013801.","DOI":"10.1109\/INFCOM.1996.493377"},{"key":"R22","unstructured":"F. Wang and D. Mao,\n                      Worst Case Analysis for On\u2010Line Scheduling in Real\u2010Time Systems\n                      , Tech. report 91\u201054, Department of Computer and Information Science, University of Massachusetts, Amherst, MA, 1991."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539797321237","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:07Z","timestamp":1787335987000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539797321237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":22,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1137\/S0097539797321237"],"URL":"https:\/\/doi.org\/10.1137\/s0097539797321237","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}