Full Text:
<434>
CLC number: TP393
On-line Access: 2024-11-08
Received: 2023-08-31
Revision Accepted: 2024-11-08
Crosschecked: 2024-03-10
Cited: 0
Clicked: 775
Citations: Bibtex RefMan EndNote GB/T7714
HSDBA: a hierarchical and scalable dynamic bandwidth allocation for programmable data planes
| ||||||||||||||
Dengyu RAN, Xiao CHEN, Lei SONG. HSDBA: a hierarchical and scalable dynamic bandwidth allocation for programmable data planes[J]. Frontiers of Information Technology & Electronic Engineering, 2024, 25(10): 1337-1352.
@article{title="HSDBA: a hierarchical and scalable dynamic bandwidth allocation for programmable data planes",
author="Dengyu RAN, Xiao CHEN, Lei SONG",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="25",
number="10",
pages="1337-1352",
year="2024",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2300593"
}
%0 Journal Article
%T HSDBA: a hierarchical and scalable dynamic bandwidth allocation for programmable data planes
%A Dengyu RAN
%A Xiao CHEN
%A Lei SONG
%J Frontiers of Information Technology & Electronic Engineering
%V 25
%N 10
%P 1337-1352
%@ 2095-9184
%D 2024
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2300593
TY - JOUR
T1 - HSDBA: a hierarchical and scalable dynamic bandwidth allocation for programmable data planes
A1 - Dengyu RAN
A1 - Xiao CHEN
A1 - Lei SONG
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 25
IS - 10
SP - 1337
EP - 1352
%@ 2095-9184
Y1 - 2024
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2300593
Abstract: dynamic bandwidth allocation (DBA) is a fundamental challenge in the realm of networking. The rapid, accurate, and fair allocation of bandwidth is crucial for network service providers to fulfill service-level agreements, alleviate link congestion, and devise strategies to counter network attacks. However, existing bandwidth allocation algorithms operate mainly on the control plane of the software-defined networking paradigm, which can lead to considerable probing overhead and convergence latency. Moreover, contemporary network architectures necessitate a hierarchical bandwidth allocation system that addresses latency requirements. We introduce a fine-grained, hierarchical, and scalable DBA algorithm, i.e., the HSDBA algorithm, implemented on the programmable data plane. This algorithm reduces network overhead and latency between the data plane and the controller, and it is proficient in dynamically adding and removing network configurations. We investigate the practicality of HSDBA using protocol-oblivious forwarding switches. Experimental results show that HSDBA achieves fair bandwidth allocation and isolation guarantee within approximately 25 packets. It boasts a convergence speed 0.5 times higher than that of the most recent algorithm, namely, approximate hierarchical allocation of bandwidth (AHAB); meanwhile, it maintains a bandwidth enforcement accuracy of 98.1%.
[1]Alcoz AG, Dietmüller A, Vanbever L, 2020. SP-PIFO: approximating push-in first-out behaviors using strict-priority queues. Proc 17th USENIX Conf on Networked Systems Design and Implementation, p.59-76.
[2]Al-Fares M, Radhakrishnan S, Raghavan B, et al., 2010. Hedera: dynamic flow scheduling for data center networks. Proc 7th USENIX Conf on Networked Systems Design and Implementation, Article 19.
[3]Barach D, Linguaglossa L, Marion D, et al., 2018. High-speed software data plane via vectorized packet processing. IEEE Commun Mag, 56(12):97-103.
[4]Bennett JCR, Zhang H, 1996. WF/sup 2/Q: worst-case fair weighted fair queueing. Proc IEEE INFOCOM, p.120-128.
[5]Bennett JCR, Zhang H, 1997. Hierarchical packet fair queueing algorithms. IEEE/ACM Trans Netw, 5(5):675-689.
[6]Benson T, Anand A, Akella A, et al., 2011. MicroTE: fine grained traffic engineering for data centers. Proc 7th Conf on Emerging Networking Experiments and Technologies, Article 8.
[7]Cardwell N, Cheng Y, Gunn CS, et al., 2017. BBR: congestion-based congestion control. Commun ACM, 60(2):58-66.
[8]Cascone C, Bonelli N, Bianchi L, et al., 2017. Towards approximate fair bandwidth sharing via dynamic priority queuing. IEEE Int Symp on Local and Metropolitan Area Networks, p.1-6.
[9]Chen L, Li BC, Li B, 2016. Barrier-aware max-min fair bandwidth sharing and path selection in datacenter networks. IEEE Int Conf on Cloud Engineering, p.151-160.
[10]Curtis AR, Kim W, Yalagandula P, 2011. Mahout: low-overhead datacenter traffic management using end-host-based elephant detection. Proc IEEE INFOCOM, p.1629-1637.
[11]Dalton M, Schultz D, Adriaens J, et al., 2018. Andromeda: performance, isolation, and velocity at scale in cloud network virtualization. Proc 15th USENIX Conf on Networked Systems Design and Implementation, p.373-387.
[12]Devera M, 2003. Linux Hierarchical Token Bucket. http://luxik.cdi.cz/devik/qos/htb/ [Accessed on Aug. 31, 2023].
[13]Floyd S, Jacobson V, 1995. Link-sharing and resource management models for packet networks. IEEE/ACM Trans Netw, 3(4):365-386.
[14]Guo CX, 2001. SRR: an O(1) time complexity packet scheduler for flows in multi-service packet networks. ACM SIGCOMM Comput Commun Rev, 31(4):211-222.
[15]Hong CY, Kandula S, Mahajan R, et al., 2013. Achieving high utilization with software-driven WAN. Proc ACM SIGCOMM, p.15-26.
[16]Hu YX, Li D, Sun PH, et al., 2020. Polymorphic smart network: an open, flexible and universal architecture for future heterogeneous networks. IEEE Trans Netw Sci Eng, 7(4):2515-2525.
[17]Jain S, Kumar A, Mandal S, et al., 2013. B4: experience with a globally-deployed software defined WAN. ACM SIGCOMM Comput Commun Rev, 43(4):3-14.
[18]Jing LN, Chen X, Wang JL, 2021. Design and implementation of programmable data plane supporting multiple data types. Electronics, 10(21):2639.
[19]Jing LN, Wang JL, Chen X, 2022. MSSA: constant time state search through multi-scope state area. Appl Sci, 12(2):559.
[20]Kumar A, Jain S, Naik U, et al., 2015. BwE: flexible, hierarchical bandwidth allocation for WAN distributed computing. Proc ACM Conf on Special Interest Group on Data Communication, p.1-14.
[21]Lee SSW, Chan KY, 2019. A traffic meter based on a multicolor marker for bandwidth guarantee and priority differentiation in SDN virtual networks. IEEE Trans Netw Serv Manag, 16(3):1046-1058.
[22]Li ZY, Hu YX, Tian L, et al., 2023. Packet rank-aware active queue management for programmable flow scheduling. Comput Netw, 225:109632.
[23]Luangsomboon N, Liebeherr J, 2021. HLS: a packet scheduler for hierarchical fairness. IEEE 29th Int Conf on Network Protocols, p.1-11.
[24]MacDavid R, Chen XQ, Rexford J, 2023. Scalable real-time bandwidth fairness in switches. IEEE Conf on Computer Communications, p.1-10.
[25]Noormohammadpour M, Raghavendra CS, 2018. Datacenter traffic control: understanding techniques and tradeoffs. IEEE Commun Surv Tutor, 20(2):1492-1525.
[26]Pfaff B, Pettit J, Koponen T, et al., 2015. The design and implementation of Open vSwitch. Proc 12th USENIX Conf on Networked Systems Design and Implementation, p.117-130.
[27]Ramabhadran S, Pasquale J, 2003. Stratified round robin: a low complexity packet scheduler with bandwidth fairness and bounded delay. Proc Conf on Applications, Technologies, Architectures, and Protocols for Computer Communications, p.239-250.
[28]Saeed A, Zhao YM, Dukkipati N, et al., 2019. Eiffel: efficient and flexible software packet scheduling. Proc 16th USENIX Conf on Networked Systems Design and Implementation, p.17-32.
[29]Sharma NK, Liu M, Atreya K, et al., 2018. Approximating fair queueing on reconfigurable switches. Proc 15th USENIX Conf on Networked Systems Design and Implementation, p.1-16.
[30]Sharma NK, Zhao CXY, Liu M, et al., 2020. Programmable calendar queues for high-speed packet scheduling. Proc 17th USENIX Conf on Networked Systems Design and Implementation, p.685-699.
[31]Shieh A, Kandula S, Greenberg A, et al., 2011. Sharing the data center network. Proc 8th USENIX Conf on Networked Systems Design and Implementation, p.309-322.
[32]Shrivastav V, 2019. Fast, scalable, and programmable packet scheduler in hardware. Proc ACM Special Interest Group on Data Communication, p.367-379.
[33]Sivaraman A, Subramanian S, Alizadeh M, et al., 2016. Programmable packet scheduling at line rate. Proc ACM SIGCOMM, p.44-57.
[34]Stoica I, Shenker S, Zhang H, 1998. Core-stateless fair queueing: achieving approximately fair bandwidth allocations in high speed networks. Proc ACM SIGCOMM, p.118-130.
[35]Thapeta VS, Shinde K, Malekpourshahraki M, et al., 2021. Nimble: scalable TCP-friendly programmable in-network rate-limiting. Proc ACM SIGCOMM Symp on SDN Research, p.27-40.
[36]Wang JL, Jing LN, Chen X, et al., 2022. Programmable data processing method and system design for polymorphic network. J Commun, 43(4):14-25.
[37]Wu XY, Wang Z, Wang WT, et al., 2023. Augmented queue: a scalable in-network abstraction for data center network sharing. Proc ACM SIGCOMM, p.305-318.
[38]Xia WF, Zhao P, Wen YG, et al., 2017. A survey on data center networking (DCN): infrastructure and operations. IEEE Commun Surv Tutor, 19(1):640-656.
[39]Xylomenos G, Ververidis CN, Siris VA, et al., 2014. A survey of information-centric networking research. IEEE Commun Surv Tutor, 16(2):1024-1049.
[40]Yang Y, Jiang HY, Wu YL, et al., 2021. C2QoS: CPU-cycle based network QoS strategy in vSwitch of public cloud. IFIP/IEEE Int Symp on Integrated Network Management, p.438-444.
[41]Yu JZ, Wang XZ, 2014. POFSwitch v1.0. https://github.com/ProtocolObliviousForwarding/pofswitch [Accessed on Aug. 31, 2023].
[42]Yu LC, Sonchack J, Liu V, 2022. Cebinae: scalable in-network fairness augmentation. Proc ACM SIGCOMM, p.219-232.
[43]Yu ZL, Hu CH, Wu JF, et al., 2021a. Programmable packet scheduling with a single queue. Proc ACM SIGCOMM, p.179-193.
[44]Yu ZL, Wu JF, Braverman V, et al., 2021b. Twenty years after: hierarchical core-stateless fair queueing. Proc 18th USENIX Symp on Networked Systems Design and Implementation, p.29-45.
ORCID: 
Open peer comments: Debate/Discuss/Question/Opinion
<1>