{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T15:31:59Z","timestamp":1759073519568,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T00:00:00Z","timestamp":1497312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"US NSF grants","award":["CNS-1423182, CNS-1302197"],"award-info":[{"award-number":["CNS-1423182, CNS-1302197"]}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council grant","doi-asserted-by":"crossref","award":["DP110103505"],"award-info":[{"award-number":["DP110103505"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2017,6,13]]},"abstract":"<jats:p>\n            Most present day switching systems, in Internet routers and data-center switches, employ a single input-queued crossbar to interconnect input ports with output ports. Such switches need to compute a matching, between input and output ports, for each switching cycle (time slot). The main challenge in designing such matching algorithms is to deal with the unfortunate tradeoff between the quality of the computed matching and the computational complexity of the algorithm. In this paper, we propose a general approach that can significantly boost the performance of both SERENA and iSLIP, yet incurs only O(1) additional computational complexity at each input\/output port. Our approach is a novel proposing strategy, called\n            <jats:italic>Queue-Proportional Sampling (QPS)<\/jats:italic>\n            , that generates an excellent\n            <jats:italic>starter matching<\/jats:italic>\n            . We show, through rigorous simulations, that when starting with this starter matching, iSLIP and SERENA can output much better final matching decisions, as measured by the resulting throughput and delay performance, than they otherwise can.\n          <\/jats:p>","DOI":"10.1145\/3084440","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T18:28:08Z","timestamp":1521829688000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Queue-Proportional Sampling"],"prefix":"10.1145","volume":"1","author":[{"given":"Long","family":"Gong","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}]},{"given":"Paul","family":"Tune","sequence":"additional","affiliation":[{"name":"University of Adelaide, Adelaide, Australia"}]},{"given":"Liang","family":"Liu","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}]},{"given":"Sen","family":"Yang","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}]},{"given":"Jun (Jim)","family":"Xu","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}]}],"member":"320","published-online":{"date-parts":[[2017,6,13]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"HdrHistogram: A High Dynamic Range (HDR) Histogram. https:\/\/github.com\/HdrHistogram\/HdrHistogram.  HdrHistogram: A High Dynamic Range (HDR) Histogram. https:\/\/github.com\/HdrHistogram\/HdrHistogram."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/161541.161736"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2012.198"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.59"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.915695"},{"key":"e_1_2_1_6_1","unstructured":"G. Birkhoff.1946 Tres observaciones sobre el algebra lineal. Univ. Nac. Tucum\u00e1n Rev. Ser. Abi 5 (1946) pages 147--151.  G. Birkhoff.1946 Tres observaciones sobre el algebra lineal. Univ. Nac. Tucum\u00e1n Rev. Ser. Abi 5 (1946) pages 147--151."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"volume-title":"Proceedings of ITCom (Modeling and Design of Wireless Networks)","author":"Eryilmaz A.","key":"e_1_2_1_8_1"},{"first-page":"954 0191","volume-title":"49th IEEE Conference on Decision and Control (CDC).","author":"Ghaderi J.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2003.810496"},{"key":"e_1_2_1_11_1","first-page":"1634","volume-title":"Proceedings of the IEEE INFOCOM.","volume":"3","author":"Goudreau M. W."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492101.1555361"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1987.1096719"},{"volume-title":"Proceedings of the Allerton Conference on Communication, Control and Computing.","author":"Keslassy I.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745864"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.769767"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.780463"},{"key":"e_1_2_1_19_1","first-page":"792","volume-title":"Proceedings of the IEEE INFOCOM.","volume":"2","author":"Mekkittikul A."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140277.1140283"},{"key":"e_1_2_1_21_1","first-page":"5","volume-title":"Contributions to the Theory of Games 2","author":"v. Neumann J.","year":"1953"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2177101"},{"volume-title":"2016 Inequalities: theory of majorization and its applications","author":"Olkin I.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555349.1555365"},{"key":"e_1_2_1_25_1","first-page":"1647 1550","volume-title":"2006 Queue Proportional Scheduling in Gaussian Broadcast Channels. 2006 IEEE International Conference on Communications","volume":"4","author":"Seong K."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2006.879404"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/40.988685"},{"key":"e_1_2_1_28_1","first-page":"1024","volume-title":"Proceedings of the IEEE INFOCOM","volume":"2","author":"Shah D."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP763"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2318857.2254762"},{"volume-title":"Proceedings of the IEEE INFOCOM","author":"Shah D.","key":"e_1_2_1_31_1"},{"first-page":"1","volume-title":"Proceedings of the IEEE INFOCOM.","author":"Shah D.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1998.665071"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.182479"},{"key":"e_1_2_1_35_1","first-page":"191","volume-title":"Journal of Applied Probability","author":"Tweedie R.","year":"1983"},{"volume-title":"2001 A note on the Glauber dynamics for sampling independent sets. Electronic Journal of Combinatorics","year":"2001","author":"Vigoda E.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591971.2591987"},{"first-page":"1683","volume-title":"Proceedings of the 48th Annual Allerton Conference.","author":"Ye S.","key":"e_1_2_1_38_1"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084440","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3084440","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:22Z","timestamp":1750217422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084440"}},"subtitle":["A Better Approach to Crossbar Scheduling for Input-Queued Switches"],"short-title":[],"issued":{"date-parts":[[2017,6,13]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,6,13]]}},"alternative-id":["10.1145\/3084440"],"URL":"https:\/\/doi.org\/10.1145\/3084440","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2017,6,13]]},"assertion":[{"value":"2017-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}