{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:40:08Z","timestamp":1750308008506,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2006,7,5]],"date-time":"2006-07-05T00:00:00Z","timestamp":1152057600000},"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":["SIGCOMM Comput. Commun. Rev."],"published-print":{"date-parts":[[2006,7,5]]},"abstract":"<jats:p>\n            The delay and throughput characteristics of a packet switch depend mainly on the queueing scheme and the scheduling algorithm deployed at the switch. Early research on scheduling algorithms has mainly focused on maximum weight matching scheduling algorithms. It is known that maximum weight matching algorithms guarantee the stability of input-queued switches, but are impractical due to their high computational complexity. Later research showed that the less complex maximal matching algorithms can stabilize input-queued switches when they are deployed with a speed-up of two. For practical purposes, neither a high computational complexity nor a speed-up of two is desirable.In this paper, we investigate the application of matching algorithms that approximate maximum weight matching algorithms to scheduling problems. We show that while having a low computational complexity, they guarantee the stability of input queued switches when they are deployed with a moderate speed-up.In particular, we show that the\n            <jats:italic>improve_matching<\/jats:italic>\n            algorithm stabilizes input-queued switches when it is deployed with a speed-up of 3&lt;over&gt;2+\u03b5.In a second step, we further improve on these results by proposing a class of maximal weight matching algorithms that stabilize an input-queued switch without any speed-up.Whereas initial research has only focused on scheduling algorithms that guarantee the stability of a single switch, recent work has shown how scheduling algorithms for single switches can be modified in order to design\n            <jats:italic>distributed<\/jats:italic>\n            scheduling algorithms that stabilize networks of input-queued switches. Using those results, we show that the switching algorithms proposed in this paper do not only stabilize a single switch, but also networks of input-queued switches.\n          <\/jats:p>","DOI":"10.1145\/1140086.1140090","type":"journal-article","created":{"date-parts":[[2006,7,24]],"date-time":"2006-07-24T17:00:26Z","timestamp":1153760426000},"page":"15-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Low complexity, stable scheduling algorithms for networks of input queued switches with no or very low speed-up"],"prefix":"10.1145","volume":"36","author":[{"given":"Claus","family":"Bauer","sequence":"first","affiliation":[{"name":"Dolby Laboratories, San Francisco, CA"}]}],"member":"320","published-online":{"date-parts":[[2006,7,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proc. of Infocom 2002","author":"Ajmone M.M.","year":"2002","unstructured":"Ajmone , M.M. , Leonardi , E. , Mellia , M. , Neri , F. , On the throughput achievable by isolated and interconnected input-queued switches under multiclass traffic , Proc. of Infocom 2002 , New York City , June 2002 . Ajmone, M.M., Leonardi, E., Mellia, M., Neri, F., On the throughput achievable by isolated and interconnected input-queued switches under multiclass traffic, Proc. of Infocom 2002, New York City, June 2002."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2003.810522"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2000.832559"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2001.916664"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/AICT.2005.29"},{"key":"e_1_2_1_6_1","volume-title":"Proc. of ICOIN","author":"Bauer C.","year":"2004","unstructured":"Bauer , C. , Throughput and delay bounds for input buffered switches using maximal weight matching algorithms and a speed-up of less than two , Proc. of ICOIN 2004 , Pusan, Korea, Springer LNCS 3090. Bauer, C., Throughput and delay bounds for input buffered switches using maximal weight matching algorithms and a speed-up of less than two, Proc. of ICOIN 2004, Pusan, Korea, Springer LNCS 3090."},{"key":"e_1_2_1_7_1","volume-title":"Proc. of IEEE Infocom 2000","author":"Dai J.G.","year":"2000","unstructured":"Dai , J.G. , Prabhakar , B. , The throughput of data switches with and without speed-up , Proc. of IEEE Infocom 2000 , Tel Aviv , March 2000 . Dai, J.G., Prabhakar, B., The throughput of data switches with and without speed-up, Proc. of IEEE Infocom 2000, Tel Aviv, March 2000."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICC.2002.997269"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00393-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764149.1764158"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077472"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/115234.115366"},{"key":"e_1_2_1_13_1","volume-title":"SODA","author":"Gabow H.N.","year":"1990","unstructured":"Gabow , H.N. , Data structures for weighted matching and nearest common ancestors with linking , SODA 1990 , 434--443. Gabow, H.N., Data structures for weighted matching and nearest common ancestors with linking, SODA 1990, 434--443."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing","author":"McKeown N.","year":"2001","unstructured":"McKeown , N. , Keslassy , I. , Analysis of scheduling algorithms that provide 100% throughput in input-queued switches , Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing . Monticello, Illinois , October 2001 . McKeown, N., Keslassy, I., Analysis of scheduling algorithms that provide 100% throughput in input-queued switches, Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing. Monticello, Illinois, October 2001."},{"issue":"8","key":"e_1_2_1_15_1","first-page":"1260","volume":"47","author":"McKeown N.","year":"1999","unstructured":"McKeown , N. , Mekkittikul , A. , Anantharam , V. , Walrand , J. , Achieving 100% throughput in an input queued switch, IEEE Trans. on Communications , vol. 47 , no. 8 , Aug. 1999 , 1260 -- 1272 . McKeown,N., Mekkittikul, A., Anantharam, V., Walrand, J., Achieving 100% throughput in an input queued switch, IEEE Trans. on Communications, vol. 47, no. 8, Aug. 1999, 1260--1272.","journal-title":"on Communications"},{"key":"e_1_2_1_16_1","volume-title":"Proc. of the Conf. on Information Sciences and Systems","author":"Neely M.M.","year":"2002","unstructured":"Neely , M.M. , Modiano , E. , Rohrs , C.E. , Tradeoffs in Delay Guarantees and Computation Complexity for Nx N Packet Switches , Proc. of the Conf. on Information Sciences and Systems , Princeton: March 2002 . Neely, M.M., Modiano, E., Rohrs, C.E., Tradeoffs in Delay Guarantees and Computation Complexity for NxN Packet Switches, Proc. of the Conf. on Information Sciences and Systems, Princeton: March 2002."},{"key":"e_1_2_1_17_1","volume-title":"Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Preis R.","year":"1999","unstructured":"Preis , R. , Linear time 1\/2 approximation algorithm for maximum weighted matching in general graphs , Symposium on Theoretical Aspects of Computer Science (STACS) 1999 , Springer LNCS 1563, 259--269. Preis, R., Linear time 1\/2 approximation algorithm for maximum weighted matching in general graphs, Symposium on Theoretical Aspects of Computer Science (STACS) 1999, Springer LNCS 1563, 259--269."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2002.1019350"},{"key":"e_1_2_1_19_1","volume-title":"Proc. 39th Annual Allerton Conference on Communication, Control and Computing","author":"Shah D","year":"2001","unstructured":"Shah , D ,; Stable Algorithms for input queued switches , Proc. 39th Annual Allerton Conference on Communication, Control and Computing , Oct. 2001 . Shah, D,; Stable Algorithms for input queued switches, Proc. 39th Annual Allerton Conference on Communication, Control and Computing, Oct. 2001."}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1140086.1140090","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1140086.1140090","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:32Z","timestamp":1750259192000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1140086.1140090"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7,5]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7,5]]}},"alternative-id":["10.1145\/1140086.1140090"],"URL":"https:\/\/doi.org\/10.1145\/1140086.1140090","relation":{},"ISSN":["0146-4833"],"issn-type":[{"type":"print","value":"0146-4833"}],"subject":[],"published":{"date-parts":[[2006,7,5]]},"assertion":[{"value":"2006-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}