research-article

Public Access

Augmented Queue: A Scalable In-Network Abstraction for Data Center Network Sharing

Authors:

T. S. Eugene NgAuthors Info & Claims

ACM SIGCOMM '23: Proceedings of the ACM SIGCOMM 2023 Conference

Pages 305 - 318

https://doi.org/10.1145/3603269.3604858

Published: 01 September 2023 Publication History

Abstract

Traffic aggregates in cloud data center networks are by and large buffered and transmitted by simple physical FIFO queues. Despite the crucial role they play, a well-known problem of physical FIFO queues is that they are unable to provide precise bandwidth guarantees. This leads to a range of negative impacts spanning the application layer, the transport layer, and the data link layer.

In this paper, we address this problem with Augmented Queue (AQ), a scalable in-network abstraction that provides precise bandwidth guarantees for traffic constituents. AQ serves multiple valuable use cases in data center networks. For example, AQ facilitates the isolation of traffic from different applications; ensures that different congestion control algorithms can properly co-exist; and enforces inbound and outbound bandwidth for virtual machines. We demonstrate via testbed and simulation experiments that AQ can provide precise bandwidth guarantees and scale to millions of traffic constituents.

References

[1]

2022. Amazon Elastic Compute Cloud (Amazon EC2). (2022). http://aws.amazon.com/ec2/

[2]

2022. Behavior Model of Programmable Switches. https://github.com/p4lang/behavioral-model. (2022).

[3]

Albert Gran Alcoz, Alexander Dietmüller, and Laurent Vanbever. 2020. SP-PIFO: Approximating Push-In First-Out Behaviors using Strict-Priority Queues. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20). 59--76.

[4]

Mohammad Alizadeh, Albert Greenberg, David A Maltz, Jitendra Padhye, Parveen Patel, Balaji Prabhakar, Sudipta Sengupta, and Murari Sridharan. 2010. Data center tcp (dctcp). In Proceedings of the ACM SIGCOMM 2010 Conference. 63--74.

Digital Library

[5]

Mohammad Alizadeh, Abdul Kabbani, Tom Edsall, Balaji Prabhakar, Amin Vahdat, and Masato Yasuda. 2012. Less Is More: Trading a Little Bandwidth for Ultra-Low Latency in the Data Center. In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12). 253--266.

[6]

Mina Tahmasbi Arashloo, Yaron Koral, Michael Greenberg, Jennifer Rexford, and David Walker. 2016. SNAP: Stateful network-wide abstractions for packet processing. In Proceedings of the 2016 ACM SIGCOMM Conference. 29--43.

Digital Library

[7]

Doru Gabriel Balan and Dan Alin Potorac. 2009. Linux HTB queuing discipline implementations. In 2009 First International Conference on Networked Digital Technologies. IEEE, 122--126.

[8]

Hitesh Ballani, Paolo Costa, Thomas Karagiannis, and Ant Rowstron. 2011. Towards predictable datacenter networks. In Proceedings of the ACM SIGCOMM 2011 Conference. 242--253.

Digital Library

[9]

Albert Banchs and Xavier Perez. 2002. Distributed weighted fair queuing in 802.11 wireless LAN. In 2002 IEEE International Conference on Communications. Conference Proceedings. ICC 2002 (Cat. No. 02CH37333), Vol. 5. IEEE, 3121--3127.

[10]

Manu Bansal, Jeffrey Mehlman, Sachin Katti, and Philip Levis. 2012. Openradio: a programmable wireless dataplane. In Proceedings of the first workshop on Hot topics in software defined networks. 109--114.

Digital Library

[11]

Pat Bosshart, Glen Gibb, Hun-Seok Kim, George Varghese, Nick McKeown, Martin Izzard, Fernando Mujica, and Mark Horowitz. 2013. Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN. ACM SIGCOMM Computer Communication Review 43, 4 (2013), 99--110.

Digital Library

[12]

Neal Cardwell, Yuchung Cheng, C Stephen Gunn, Soheil Hassas Yeganeh, and Van Jacobson. 2016. Bbr: Congestion-based congestion control: Measuring bottleneck bandwidth and round-trip propagation time. Queue 14, 5 (2016), 20--53.

Digital Library

[13]

Bryce Cronkite-Ratcliff, Aran Bergman, Shay Vargaftik, Madhusudhan Ravi, Nick McKeown, Ittai Abraham, and Isaac Keslassy. 2016. Virtualized congestion control. In Proceedings of the 2016 ACM SIGCOMM Conference. 230--243.

Digital Library

[14]

Nick G Duffield, Pawan Goyal, Albert Greenberg, Partho Mishra, Kadangode K Ramakrishnan, and Jacobus E van der Merive. 1999. A flexible model for resource management in virtual private networks. In Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication. 95--108.

Digital Library

[15]

Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, Aditya Akella, Kuangching Wang, Glenn Ricart, Larry Landweber, Chip Elliott, Michael Zink, Emmanuel Cecchet, Snigdhaswin Kar, and Prabodh Mishra. 2019. The Design and Operation of CloudLab. https://www.flux.utah.edu/paper/duplyakinatc19. In Proceedings of the USENIX Annual Technical Conference (ATC). 1--14.

[16]

Thomas Erlebach and Maurice Ruegg. 2004. Optimal bandwidth reservation in hose-model VPNs with multi-path routing. In IEEE INFOCOM 2004, Vol. 4. IEEE, 2275--2282.

[17]

Sally Floyd, Tom Henderson, and Andrei Gurtov. 2004. The NewReno modification to TCP's fast recovery algorithm. Technical Report.

[18]

Sally Floyd and Van Jacobson. 1993. Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on networking 1, 4 (1993), 397--413.

Digital Library

[19]

Tommaso Frassetto, Patrick Jauernig, Christopher Liebchen, and Ahmad-Reza Sadeghi. 2018. {IMIX}:{In-Process} Memory Isolation {EXtension}. In 27th USENIX Security Symposium (USENIX Security 18). 83--97.

[20]

Peter Gomber and Martin Haferkorn. 2015. High frequency trading. In Encyclopedia of Information Science and Technology, Third Edition. IGI Global, 1--9.

[21]

Chuanxiong Guo, Guohan Lu, Helen J Wang, Shuang Yang, Chao Kong, Peng Sun, Wenfei Wu, and Yongguang Zhang. 2010. Secondnet: a data center network virtualization architecture with bandwidth guarantees. In Proceedings of the 6th International COnference. 1--12.

Digital Library

[22]

Sangtae Ha, Injong Rhee, and Lisong Xu. 2008. CUBIC: a new TCP-friendly high-speed TCP variant. ACM SIGOPS operating systems review 42, 5 (2008), 64--74.

Digital Library

[23]

David Hancock and Jacobus Van der Merwe. 2016. Hyper4: Using p4 to virtualize the programmable data plane. In Proceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies. 35--49.

Digital Library

[24]

Keqiang He, Eric Rozner, Kanak Agarwal, Yu Gu, Wes Felter, John Carter, and Aditya Akella. 2016. AC/DC TCP: Virtual congestion control enforcement for datacenter networks. In Proceedings of the 2016 ACM SIGCOMM Conference. 244--257.

Digital Library

[25]

Kuo-Feng Hsu, Ryan Beckett, Ang Chen, Jennifer Rexford, Praveen Tammana, and David Walker. 2020. Contra: A programmable system for performance-aware routing. In 17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020.

[26]

Chengchen Hu, Yi Tang, Xuefei Chen, and Bin Liu. 2007. Per-flow queueing by dynamic queue sharing. In IEEE INFOCOM 2007-26th IEEE International Conference on Computer Communications. IEEE, 1613--1621.

Digital Library

[27]

Călin Iorgulescu, Reza Azimi, Youngjin Kwon, Sameh Elnikety, Manoj Syamala, Vivek Narasayya, Herodotos Herodotou, Paulo Tomita, Alex Chen, Jack Zhang, et al. 2018. {PerfIso}: Performance Isolation for Commercial {Latency-Sensitive} Services. In 2018 USENIX Annual Technical Conference (USENIX ATC 18). 519--532.

[28]

Keon Jang, Justine Sherry, Hitesh Ballani, and Toby Moncaster. 2015. Silo: Predictable message latency in the cloud. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. 435--448.

Digital Library

[29]

Vimalkumar Jeyakumar, Mohammad Alizadeh, David Mazières, Balaji Prabhakar, Albert Greenberg, and Changhoon Kim. 2013. {EyeQ}: Practical Network Performance Isolation at the Edge. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 297--311.

[30]

Yimin Jiang, Yibo Zhu, Chang Lan, Bairen Yi, Yong Cui, and Chuanxiong Guo. 2020. A Unified Architecture for Accelerating Distributed {DNN} Training in Heterogeneous GPU/CPU Clusters. In 14th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 20). 463--479.

[31]

Leonard Kleinrock. 1976. Computer applications. Queueing systems 3 (1976).

[32]

Alok Kumar, Sushant Jain, Uday Naik, Anand Raghuraman, Nikhil Kasinadhuni, Enrique Cauich Zermeno, C Stephen Gunn, Jing Ai, Björn Carlin, Mihai Amarandei-Stavila, et al. 2015. BwE: Flexible, hierarchical bandwidth allocation for WAN distributed computing. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. 1--14.

Digital Library

[33]

Amit Kumar, Rajeev Rastogi, Avi Silberschatz, and Bulent Yener. 2002. Algorithms for provisioning virtual private networks in the hose model. IEEE/ACM transactions on networking 10, 4 (2002), 565--578.

Digital Library

[34]

Gautam Kumar, Nandita Dukkipati, Keon Jang, Hassan MG Wassel, Xian Wu, Behnam Montazeri, Yaogong Wang, Kevin Springborn, Christopher Alfeld, Michael Ryan, et al. 2020. Swift: Delay is simple and effective for congestion control in the datacenter. In Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication. 514--528.

Digital Library

[35]

Praveen Kumar, Nandita Dukkipati, Nathan Lewis, Yi Cui, Yaogong Wang, Chonggang Li, Valas Valancius, Jake Adriaens, Steve Gribble, Nate Foster, et al. 2019. PicNIC: predictable virtualized NIC. In Proceedings of the ACM Special Interest Group on Data Communication. 351--366.

Digital Library

[36]

Vinh The Lam, Sivasankar Radhakrishnan, Rong Pan, Amin Vahdat, and George Varghese. 2012. Netshare and stochastic netshare: predictable bandwidth allocation for data centers. ACM SIGCOMM Computer Communication Review 42, 3 (2012), 5--11.

Digital Library

[37]

Ang Li, Xiaowei Yang, Srikanth Kandula, and Ming Zhang. 2010. CloudCmp: comparing public cloud providers. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement. 1--14.

Digital Library

[38]

Shen Li, Yanli Zhao, Rohan Varma, Omkar Salpekar, Pieter Noordhuis, Teng Li, Adam Paszke, Jeff Smith, Brian Vaughan, Pritam Damania, and Soumith Chintala. 2020. Pytorch distributed: Experiences on accelerating data parallel training. arXiv preprint arXiv:2006.15704 (2020).

[39]

Yuliang Li, Rui Miao, Hongqiang Harry Liu, Yan Zhuang, Fei Feng, Lingbo Tang, Zheng Cao, Ming Zhang, Frank Kelly, Mohammad Alizadeh, et al. 2019. HPCC: High precision congestion control. In Proceedings of the ACM Special Interest Group on Data Communication. 44--58.

[40]

Shao Liu, Tamer Başar, and Ravi Srikant. 2006. TCP-Illinois: A loss and delay-based congestion control algorithm for high-speed networks. In Proceedings of the 1st international conference on Performance evaluation methodolgies and tools. 55--es.

Digital Library

[41]

James McCauley, Aurojit Panda, Arvind Krishnamurthy, and Scott Shenker. 2019. Thoughts on load distribution and the role of programmable switches. ACM SIGCOMM Computer Communication Review 49, 1 (2019), 18--23.

Digital Library

[42]

Paul E McKenney. 1990. Stochastic fairness queueing. In IEEE INFOCOM'90. IEEE Computer Society, 733--734.

[43]

Radhika Mittal, Vinh The Lam, Nandita Dukkipati, Emily Blem, Hassan Wassel, Monia Ghobadi, Amin Vahdat, Yaogong Wang, David Wetherall, and David Zats. 2015. TIMELY: RTT-based congestion control for the datacenter. ACM SIGCOMM Computer Communication Review 45, 4 (2015), 537--550.

Digital Library

[44]

Abhay K Parekh and Robert G Gallager. 1993. A generalized processor sharing approach to flow control in integrated services networks: the single-node case. IEEE/ACM transactions on networking 1, 3 (1993), 344--357.

[45]

Lucian Popa, Gautam Kumar, Mosharaf Chowdhury, Arvind Krishnamurthy, Sylvia Ratnasamy, and Ion Stoica. 2012. FairCloud: Sharing the network in cloud computing. In Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication. 187--198.

Digital Library

[46]

Lucian Popa, Praveen Yalagandula, Sujata Banerjee, Jeffrey C Mogul, Yoshio Turner, and Jose Renato Santos. 2013. Elasticswitch: Practical work-conserving bandwidth guarantees for cloud computing. In Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM. 351--362.

Digital Library

[47]

Henrique Rodrigues, Jose Renato Santos, Yoshio Turner, Paolo Soares, and Dorgival Guedes. 2011. Gatekeeper: Supporting bandwidth guarantees for multi-tenant datacenter networks. In 3rd Workshop on I/O Virtualization (WIOV 11).

[48]

Ahmed Saeed, Nandita Dukkipati, Vytautas Valancius, Vinh The Lam, Carlo Contavalli, and Amin Vahdat. 2017. Carousel: Scalable traffic shaping at end hosts. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication. 404--417.

Digital Library

[49]

Jörg Schad, Jens Dittrich, and Jorge-Arnulfo Quiané-Ruiz. 2010. Runtime measurements in the cloud: observing, analyzing, and reducing variance. Proceedings of the VLDB Endowment 3, 1--2 (2010), 460--471.

Digital Library

[50]

Alexander Sergeev and Mike Del Balso. 2018. Horovod: fast and easy distributed deep learning in TensorFlow. arXiv preprint arXiv:1802.05799 (2018).

[51]

Naveen Kr Sharma, Antoine Kaufmann, Thomas E Anderson, Arvind Krishnamurthy, Jacob Nelson, and Simon Peter. 2017. Evaluating the Power of Flexible Packet Processing for Network Resource Allocation. In NSDI. 67--82.

[52]

Naveen Kr Sharma, Chenxingyu Zhao, Ming Liu, Pravein G Kannan, Changhoon Kim, Arvind Krishnamurthy, and Anirudh Sivaraman. 2020. Programmable calendar queues for high-speed packet scheduling. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20). 685--699.

[53]

Alan Shieh, Srikanth Kandula, Albert Greenberg, Changhoon Kim, and Bikas Saha. 2011. Sharing the data center network. In 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 11).

[54]

Madhavapeddi Shreedhar and George Varghese. 1995. Efficient fair queueing using deficit round robin. In Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication. 231--242.

Digital Library

[55]

Arjun Singh, Joon Ong, Amit Agarwal, Glen Anderson, Ashby Armistead, Roy Bannon, Seb Boving, Gaurav Desai, Bob Felderman, Paulie Germano, et al. 2015. Jupiter rising: A decade of clos topologies and centralized control in google's datacenter network. ACM SIGCOMM computer communication review 45, 4 (2015), 183--197.

[56]

Anirudh Sivaraman, Keith Winstein, Suvinay Subramanian, and Hari Balakrishnan. 2013. No silver bullet: extending SDN to the data plane. In Proceedings of the Twelfth ACM Workshop on Hot Topics in networks. 1--7.

Digital Library

[57]

Vibhaalakshmi Sivaraman, Srinivas Narayana, Ori Rottenstreich, Shan Muthukrishnan, and Jennifer Rexford. 2017. Heavy-hitter detection entirely in the data plane. In Proceedings of the Symposium on SDN Research. 164--176.

Digital Library

[58]

Brent E Stephens, Darius Grassi, Hamidreza Almasi, Tao Ji, Balajee Vamanan, and Aditya Akella. 2021. TCP is Harmful to In-Network Computing: Designing a Message Transport Protocol (MTP). In Proceedings of the Twentieth ACM Workshop on Hot Topics in Networks. 61--68.

Digital Library

[59]

Vineeth Sagar Thapeta, Komal Shinde, Mojtaba Malekpourshahraki, Darius Grassi, Balajee Vamanan, and Brent E Stephens. 2021. Nimble: Scalable tcp-friendly programmable in-network rate-limiting. In Proceedings of the ACM SIG-COMM Symposium on SDN Research (SOSR). 27--40.

Digital Library

[60]

Shuai Wang, Kaihui Gao, Kun Qian, Dan Li, Rui Miao, Bo Li, Yu Zhou, Ennan Zhai, Chen Sun, Jiaqi Gao, et al. 2022. Predictable vFabric on informative data plane. In Proceedings of the ACM SIGCOMM 2022 Conference. 615--632.

Digital Library

[61]

Di Xie, Ning Ding, Y Charlie Hu, and Ramana Kompella. 2012. The only constant is change: Incorporating time-varying network reservations in data centers. In Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication. 199--210.

Digital Library

[62]

Yunjing Xu, Zachary Musgrave, Brian Noble, and Michael Bailey. 2013. Bobtail: Avoiding long tails in the cloud. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 329--341.

[63]

Liangcheng Yu, John Sonchack, and Vincent Liu. 2022. Cebinae: scalable in-network fairness augmentation. In Proceedings of the ACM SIGCOMM 2022 Conference. 219--232.

Digital Library

[64]

Zhuolong Yu, Chuheng Hu, Jingfeng Wu, Xiao Sun, Vladimir Braverman, Mosharaf Chowdhury, Zhenhua Liu, and Xin Jin. 2021. Programmable packet scheduling with a single queue. In Proceedings of the 2021 ACM SIGCOMM 2021 Conference. 179--193.

Digital Library

[65]

Hui Zhang and Jon CR Bennett. 1996. WF2Q: worst-case fair weighted fair queueing. In IEEE INFOCOM, Vol. 96. 120--128.

[66]

Hang Zhu, Tao Wang, Yi Hong, Dan RK Ports, Anirudh Sivaraman, and Xin Jin. 2022. NetVRM: Virtual Register Memory for Programmable Networks. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22). 155--170.

[67]

Yibo Zhu, Haggai Eran, Daniel Firestone, Chuanxiong Guo, Marina Lipshteyn, Yehonatan Liron, Jitendra Padhye, Shachar Raindel, Mohamad Haj Yahia, and Ming Zhang. 2015. Congestion control for large-scale RDMA deployments. ACM SIGCOMM Computer Communication Review 45, 4 (2015), 523--536.

Digital Library

[68]

Yibo Zhu, Monia Ghobadi, Vishal Misra, and Jitendra Padhye. 2016. ECN or Delay: Lessons Learnt from Analysis of DCQCN and TIMELY. In Proceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies. 313--327.

Digital Library

Cited By

Ran DChen XSong L(2024)HSDBA: a hierarchical and scalable dynamic bandwidth allocation for programmable data planesHSDBA: 一种面向可编程数据平面的分层可扩展动态带宽分配方法Frontiers of Information Technology & Electronic Engineering10.1631/FITEE.230059325:10(1337-1352)Online publication date: 5-Nov-2024
https://doi.org/10.1631/FITEE.2300593

Index Terms

Augmented Queue: A Scalable In-Network Abstraction for Data Center Network Sharing
1. Networks
  1. Network properties
    1. Network dynamics
  2. Network services
    1. In-network processing

Recommendations

Queue-Length Distribution for the Discriminatory Processor-Sharing Queue

In this paper, we study a multiple class discriminatory processor-sharing queue. The queue is assumed to have Poisson input and exponentially distributed service times. In this discipline there are K classes of customers. When there are n _i ...
A Scalable Framework for IP-Network Resource Provisioning Through
Scalable network architectures for providing per-flow service guarantees

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ACM SIGCOMM '23: Proceedings of the ACM SIGCOMM 2023 Conference

September 2023

1217 pages

ISBN:9798400702365

DOI:10.1145/3603269

Chairs:
Henning Schulzrinne,
Vishal Misra,
Program Chairs:
Eddie Kohler,
David Maltz

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF (National Science Foundation)

Conference

ACM SIGCOMM '23

Sponsor:

SIGCOMM

ACM SIGCOMM '23: ACM SIGCOMM 2023 Conference

September 10, 2023

NY, New York, USA

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
944
Total Downloads

Downloads (Last 12 months)544
Downloads (Last 6 weeks)39

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ran DChen XSong L(2024)HSDBA: a hierarchical and scalable dynamic bandwidth allocation for programmable data planesHSDBA: 一种面向可编程数据平面的分层可扩展动态带宽分配方法Frontiers of Information Technology & Electronic Engineering10.1631/FITEE.230059325:10(1337-1352)Online publication date: 5-Nov-2024
https://doi.org/10.1631/FITEE.2300593

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents