{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:49:51Z","timestamp":1750308591240,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,5,20]],"date-time":"2017-05-20T00:00:00Z","timestamp":1495238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Korean government","award":["MSIP; 2016 R1A2B4011799"],"award-info":[{"award-number":["MSIP; 2016 R1A2B4011799"]}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ICT R8Dprogram of MSIP\/IITP"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>Scalability of network processor-based routers heavily depends on limitations imposed by memory accesses and associated power consumption. Bandwidth shaping of a flow is a key function, which requires a token bucket per output queue and abuses memory bandwidth. As the number of output queues increases, managing token buckets becomes prohibitively expensive and limits scalability. In this work, we propose a scalable software-based token bucket management scheme that can reduce memory accesses and power consumption significantly. To satisfy real-time and low-cost constraints, we propose novel parallel heap data structures running on a manycore-based network processor. By using cache locking, the performance of heap processing is enhanced significantly and is more predictable. In addition, we quantitatively analyze the performance and memory footprint of the proposed software scheme using stochastic modeling and the Lyapunov central limit theorem. Finally, the proposed scheme provides an adaptive method to limit the size of heaps in the case of oversubscribed queues, which can successfully isolate the queues showing unideal behavior. The proposed scheme reduces memory accesses by up to three orders of magnitude for one million queues sharing a 100Gbps interface of the router while maintaining stability under stressful scenarios.<\/jats:p>","DOI":"10.1145\/3065926","type":"journal-article","created":{"date-parts":[[2017,5,22]],"date-time":"2017-05-22T12:20:31Z","timestamp":1495455631000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Scalable Bandwidth Shaping Scheme via Adaptively Managed Parallel Heaps in Manycore-Based Network Processors"],"prefix":"10.1145","volume":"22","author":[{"given":"Taehyun","family":"Kim","sequence":"first","affiliation":[{"name":"Sogang University, Seoul, Republic of Korea"}]},{"given":"Jongbum","family":"Lim","sequence":"additional","affiliation":[{"name":"Sogang University, Seoul, Republic of Korea"}]},{"given":"Jinku","family":"Kim","sequence":"additional","affiliation":[{"name":"Sogang University, Seoul, Republic of Korea"}]},{"given":"Woo-Cheol","family":"Cho","sequence":"additional","affiliation":[{"name":"Sogang University, Seoul, Republic of Korea"}]},{"given":"Eui-Young","family":"Chung","sequence":"additional","affiliation":[{"name":"Yonsei University, Seoul, Republic of Korea"}]},{"given":"Hyuk-Jun","family":"Lee","sequence":"additional","affiliation":[{"name":"Sogang University, Seoul, Republic of Korea"}]}],"member":"320","published-online":{"date-parts":[[2017,5,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCEA.2010.41"},{"volume-title":"Retrieved","year":"2007","key":"e_1_2_2_2_1"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11277-015-2661-2"},{"key":"e_1_2_2_4_1","unstructured":"K. J. \u00c5str\u00f6m and B. Wittenmark. 2013. Adaptive control (2nd. ed.). Courier Corporation North Chelmsford MA US.  K. J. \u00c5str\u00f6m and B. Wittenmark. 2013. Adaptive control (2nd. ed.). Courier Corporation North Chelmsford MA US."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2010.2048924"},{"volume":"1","volume-title":"Proceedings of the 15th Annual Joint Conference of the IEEE Computer Societies. Networking the Next Generation.","author":"Bennett J. C. R.","key":"e_1_2_2_6_1"},{"key":"e_1_2_2_7_1","unstructured":"P. Billingsley. 1995. Probability and measure (3rd. ed.). John Wiley 8 Sons New York NY.  P. Billingsley. 1995. Probability and measure (3rd. ed.). John Wiley 8 Sons New York NY."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024716.2024718"},{"volume-title":"Retrieved","year":"2008","author":"CAIDA.","key":"e_1_2_2_9_1"},{"volume-title":"Proceedings of IEEE\/IEE Real-Time Embedded Systems Workshop (Satellite of the IEEE Real-Time Systems Symposium).","author":"Campoy M.","key":"e_1_2_2_10_1"},{"volume-title":"Proceedings of International Conference on VLSI, Communication, Advanced Devices, Signals 8 Systems and Networking (VCASAN-2013)","author":"Chakravarthi S.","key":"e_1_2_2_11_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-81-322-1524-0"},{"volume-title":"Retrieved","year":"2011","key":"e_1_2_2_12_1"},{"volume-title":"Retrieved","year":"2014","key":"e_1_2_2_13_1"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31985-6_6"},{"key":"e_1_2_2_15_1","unstructured":"M. A. Franklin P. Crowley H. Hadimioglu and P. Z. Onufryk. 2003. Network Processor Design Volume 2: Issues and Practices. Morgan Kaufmann San Francisco CA.  M. A. Franklin P. Crowley H. Hadimioglu and P. Z. Onufryk. 2003. Network Processor Design Volume 2: Issues and Practices. Morgan Kaufmann San Francisco CA."},{"key":"e_1_2_2_16_1","unstructured":"R. Giladi. 2008. Network processors: architecture programming and implementation. Morgan Kaufmann Burlington MA.  R. Giladi. 2008. Network processors: architecture programming and implementation. Morgan Kaufmann Burlington MA."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851275.1851207"},{"key":"e_1_2_2_18_1","unstructured":"E. Horowits S. Sahani and S. Anderson-Freed. 1992. Fundamentals of data structures in c. Computer Science Press.  E. Horowits S. Sahani and S. Anderson-Freed. 1992. Fundamentals of data structures in c. Computer Science Press."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.70806"},{"volume-title":"Retrieved","year":"2005","key":"e_1_2_2_20_1"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2009.181"},{"volume-title":"10th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201913)","author":"Jeyakumar V.","key":"e_1_2_2_22_1"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2010.240"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/375506.375518"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1105734.1105747"},{"volume-title":"Retrieved","year":"2013","author":"Networks C.","key":"e_1_2_2_26_1"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.234856"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.2003.1258822"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486027"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2002.1181567"},{"volume-title":"11th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201914)","author":"Radhakrishnan S.","key":"e_1_2_2_31_1"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/L-CA.2011.4"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/217382.217453"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1999.749252"},{"volume-title":"Retrieved","year":"2016","key":"e_1_2_2_35_1"},{"key":"e_1_2_2_36_1","unstructured":"G. Varghese. 2010. Network algorithmics. Chapman 8 Hall\/CRC Boca Raton FL.  G. Varghese. 2010. Network algorithmics. Chapman 8 Hall\/CRC Boca Raton FL."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/885651.781062"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2002.1022267"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3065926","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3065926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:21Z","timestamp":1750273521000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3065926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,20]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3065926"],"URL":"https:\/\/doi.org\/10.1145\/3065926","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2017,5,20]]},"assertion":[{"value":"2016-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}