{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:15Z","timestamp":1759637895401,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2005,9,1]],"date-time":"2005-09-01T00:00:00Z","timestamp":1125532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2005,9]]},"abstract":"<jats:p>\n            In a wireless network, a basestation transmits data to mobiles at\n            <jats:italic>time-varying, mobile-dependent<\/jats:italic>\n            rates due to the ever changing nature of the communication channels. In this article, we consider a wireless system in which the channel conditions and data arrival processes are governed by an\n            <jats:italic>adversary<\/jats:italic>\n            . We first consider a single server and a set of users. At each time step\n            <jats:italic>t<\/jats:italic>\n            , the server can only transmit data to one user. If user\n            <jats:italic>i<\/jats:italic>\n            is chosen, the transmission rate is\n            <jats:italic>\n              r\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            (\n            <jats:italic>t<\/jats:italic>\n            ). We say that the system is (\n            <jats:italic>w<\/jats:italic>\n            , \u03b5)-\n            <jats:italic>admissible<\/jats:italic>\n            if in any window of\n            <jats:italic>w<\/jats:italic>\n            time steps the adversary can schedule the users so that the total data arriving to each user is at most 1\u2212\u03b5 times the total service it receives.Our objective is to design online scheduling algorithms to ensure stability in an admissible system. We first show, somewhat surprisingly, that the admissibility condition alone does not guarantee the existence of a stable online algorithm, even in a subcritical system (i.e., \u03b5 &gt; 0). For example, if the nonzero rates in an infinite rate set can be arbitrarily small, then a subcritical system can be unstable for any deterministic online algorithm.On a positive note, we present a tracking algorithm that attempts to mimic the behavior of the adversary. This algorithm ensures stability for all (\n            <jats:italic>w<\/jats:italic>\n            , \u03b5)-admissible systems that are not excluded by our instability results. As a special case, if the rate set is finite, then the tracking algorithm is stable even for a critical system (i.e., \u03b5 = 0). Moreover, the queue sizes are independent of \u03b5. For subcritical systems, we also show that a simpler max weight algorithm is stable as long as the user rates are bounded away from zero.The offline version of our problem resembles the problem of scheduling unrelated machines and can be modeled by an integer program. We present a rounding algorithm for its linear relaxation and prove that the rounding technique cannot be substantially improved.\n          <\/jats:p>","DOI":"10.1145\/1089023.1089028","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"809-834","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Scheduling over a time-varying user-dependent channel with applications to high-speed wireless data"],"prefix":"10.1145","volume":"52","author":[{"given":"Matthew","family":"Andrews","sequence":"first","affiliation":[{"name":"Bell Laboratories, Murrray Hill, New Jersey"}]},{"given":"Lisa","family":"Zhang","sequence":"additional","affiliation":[{"name":"Bell Laboratories, Murrray Hill, New Jersey"}]}],"member":"320","published-online":{"date-parts":[[2005,9]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"359","volume-title":"Proceedings of the 30th Annual ACM Symposium on Theory of Computing","author":"Aiello W.","unstructured":"Aiello , W. , Kushilevitz , E. , Ostrovsky , R. , and Rosen , A . 1998. Adaptive packet routing for bursty adversarial traffic . In Proceedings of the 30th Annual ACM Symposium on Theory of Computing ( Dallas, TX, May), ACM, New York , pp. 359 -- 368 . 10.1145\/276698.276788 Aiello, W., Kushilevitz, E., Ostrovsky, R., and Rosen, A. 1998. Adaptive packet routing for bursty adversarial traffic. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (Dallas, TX, May), ACM, New York, pp. 359--368. 10.1145\/276698.276788"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2004.833419"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/363647.363677"},{"key":"e_1_2_1_4_1","unstructured":"Andrews M. Kumaran K. Ramanan K. Stolyar A. Vijayakumar R. and Whiting P. 2000. CDMA data QoS scheduling on the forward link with variable channel conditions. Bell Labs Tech. Memo. (Apr.).  Andrews M. Kumaran K. Ramanan K. Stolyar A. Vijayakumar R. and Whiting P. 2000. CDMA data QoS scheduling on the forward link with variable channel conditions. Bell Labs Tech. Memo. (Apr.)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/35.900644"},{"volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing (Montreal, Ont., Canada, May). ACM","author":"Anshelevich E.","key":"e_1_2_1_6_1","unstructured":"Anshelevich , E. , Kempe , D. , and Kleinberg , J . 2002. Stability of load balancing algorithms in dynamic adversarial systems . In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (Montreal, Ont., Canada, May). ACM , New York. 10.1145\/509907.509968 Anshelevich, E., Kempe, D., and Kleinberg, J. 2002. Stability of load balancing algorithms in dynamic adversarial systems. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (Montreal, Ont., Canada, May). ACM, New York. 10.1145\/509907.509968"},{"key":"e_1_2_1_7_1","first-page":"158","volume-title":"Proceedings of the 42nd Annual Symposium on Foundations of Computer Science","author":"Awerbuch B.","unstructured":"Awerbuch , B. , Berenbrink , P. , Brinkmann , A. , and Scheideler , C . 2001. Simple routing strategies for adversarial systems . In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science ( Las Vegas, NV, Oct.). IEEE Computer Society Press, Los Alamitos, CA , pp. 158 -- 167 . Awerbuch, B., Berenbrink, P., Brinkmann, A., and Scheideler, C. 2001. Simple routing strategies for adversarial systems. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (Las Vegas, NV, Oct.). IEEE Computer Society Press, Los Alamitos, CA, pp. 158--167."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/363647.363659"},{"volume-title":"Proceedings of IEEE INFOCOM '01","author":"Borst S.","key":"e_1_2_1_9_1","unstructured":"Borst , S. , and Whiting , P . 2001. Dynamic rate control algorithms for CDMA throughput optimization . In Proceedings of IEEE INFOCOM '01 ( Anchorage, AK). IEEE Computer Society Press, Los Alamitos, CA. Borst, S., and Whiting, P. 2001. Dynamic rate control algorithms for CDMA throughput optimization. In Proceedings of IEEE INFOCOM '01 (Anchorage, AK). IEEE Computer Society Press, Los Alamitos, CA."},{"key":"e_1_2_1_10_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability---A Guide to the Theory of NP-Completeness. W. H. Freeman and Company New York.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability---A Guide to the Theory of NP-Completeness. W. H. Freeman and Company New York."},{"volume-title":"Proceedings of the IEEE Semiannual Vehicular Technology Conference, VTC2000-Spring","author":"Jalali A.","key":"e_1_2_1_11_1","unstructured":"Jalali , A. , Padovani , R. , and Pankaj , R . 2000. Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system . In Proceedings of the IEEE Semiannual Vehicular Technology Conference, VTC2000-Spring ( Tokyo, Japan, May). IEEE Computer Society Press, Los Alamitos, CA. Jalali, A., Padovani, R., and Pankaj, R. 2000. Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system. In Proceedings of the IEEE Semiannual Vehicular Technology Conference, VTC2000-Spring (Tokyo, Japan, May). IEEE Computer Society Press, Los Alamitos, CA."},{"volume-title":"Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing.","author":"Kushner H.","key":"e_1_2_1_12_1","unstructured":"Kushner , H. , and Whiting , P . 2002. Asymptotic properties of proportional-fair sharing algorithms . In Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing. Kushner, H., and Whiting, P. 2002. Asymptotic properties of proportional-fair sharing algorithms. In Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing."},{"volume-title":"Proceedings of IEEE INFOCOM '02","author":"Neely M.","key":"e_1_2_1_13_1","unstructured":"Neely , M. , Modiano , E. , and Rohrs , C . 2002. Power and server allocation in a multi-beam satellite with time varying channels . In Proceedings of IEEE INFOCOM '02 ( New York, NY, June). IEEE Computer Society Press, Los Alamitos, CA. Neely, M., Modiano, E., and Rohrs, C. 2002. Power and server allocation in a multi-beam satellite with time varying channels. In Proceedings of IEEE INFOCOM '02 (New York, NY, June). IEEE Computer Society Press, Los Alamitos, CA."},{"volume-title":"Proceedings of the IEEE Semiannual Vehicular Technology Conference, VTC2001-Fall (Atlantic City, N.J., Oct.). IEEE Computer Society Press","author":"Rhee J.","key":"e_1_2_1_14_1","unstructured":"Rhee , J. , Kim , T. , and Kim , D . 2001. Wireless fair scheduling algorithm for 1xEV-DO system . In Proceedings of the IEEE Semiannual Vehicular Technology Conference, VTC2001-Fall (Atlantic City, N.J., Oct.). IEEE Computer Society Press , Los Alamitos, CA. Rhee, J., Kim, T., and Kim, D. 2001. Wireless fair scheduling algorithm for 1xEV-DO system. In Proceedings of the IEEE Semiannual Vehicular Technology Conference, VTC2001-Fall (Atlantic City, N.J., Oct.). IEEE Computer Society Press, Los Alamitos, CA."},{"volume-title":"Proceedings of ACM Workshop on Wireless and Mobile Multimedia Seattle, WA (Aug.). ACM","author":"Shakkottai S.","key":"e_1_2_1_15_1","unstructured":"Shakkottai , S. , and Srikant , R . 1999. Scheduling real-time traffic with deadlines over a wireless channel . In Proceedings of ACM Workshop on Wireless and Mobile Multimedia Seattle, WA (Aug.). ACM , New York. 10.1145\/313256.313273 Shakkottai, S., and Srikant, R. 1999. Scheduling real-time traffic with deadlines over a wireless channel. In Proceedings of ACM Workshop on Wireless and Mobile Multimedia Seattle, WA (Aug.). ACM, New York. 10.1145\/313256.313273"},{"volume-title":"Proceedings of 17th International Teletraffic Congress (ITC-17)","author":"Shakkottai S.","key":"e_1_2_1_16_1","unstructured":"Shakkottai , S. , and Stolyar , A . 2001. Scheduling algorithms for a mixture of real-time and non-real-time data in HDR . In Proceedings of 17th International Teletraffic Congress (ITC-17) (Salvador da Bahia, Brazil). Shakkottai, S., and Stolyar, A. 2001. Scheduling algorithms for a mixture of real-time and non-real-time data in HDR. In Proceedings of 17th International Teletraffic Congress (ITC-17) (Salvador da Bahia, Brazil)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Shakkottai S. and Stolyar A. L. 2002. Scheduling for multiple flows sharing a time-varying channel: The exponential rule. In Analytic Methods in Applied Probability in Memory of Fridrih karpelevich. Yu. M. Shov Ed. American Mathematical Society Translations Series 2. American Mathematical Society Providence RI vol. 207 pp. 185--202.  Shakkottai S. and Stolyar A. L. 2002. Scheduling for multiple flows sharing a time-varying channel: The exponential rule. In Analytic Methods in Applied Probability in Memory of Fridrih karpelevich. Yu. M. Shov Ed. American Mathematical Society Translations Series 2. American Mathematical Society Providence RI vol. 207 pp. 185--202.","DOI":"10.1090\/trans2\/207\/12"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585178"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1040.0156"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1109\/9.182479","article-title":"Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks","volume":"37","author":"Tassiulas L.","year":"1992","unstructured":"Tassiulas , L. , and Ephremides , A. 1992 . Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks . IEEE Trans. Automat. Cont. 37 , 12 (Dec.), 1936--1948. Tassiulas, L., and Ephremides, A. 1992. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Automat. Cont. 37, 12 (Dec.), 1936--1948.","journal-title":"IEEE Trans. Automat. Cont."},{"key":"e_1_2_1_21_1","unstructured":"Tse D. 200X. Multiuser diversity in wireless networks. http:\/\/www.eecs.berkeley.edu\/~dtse\/stanford416.ps.  Tse D. 200X. Multiuser diversity in wireless networks. http:\/\/www.eecs.berkeley.edu\/~dtse\/stanford416.ps."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089023.1089028","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1089023.1089028","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:22Z","timestamp":1750262902000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1089023.1089028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2005,9]]}},"alternative-id":["10.1145\/1089023.1089028"],"URL":"https:\/\/doi.org\/10.1145\/1089023.1089028","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2005,9]]},"assertion":[{"value":"2005-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}