数据中心网络路由研究进展

摘要/Abstract

摘要： 随着云计算的迅速发展，运营商对数据中心的需求与日俱增。作为数据中心网络的关键技术，路由负责在数据中心内部以及数据中心之间为流量选路，为不同服务质量要求的流量提供差异化的路由转发服务。当数据中心规模比较大时，由于应用不可预估的通信流量以及数据中心网络的拓扑特点，传统因特网路由方法不能提供令人满意的高吞吐率和资源利用率，网络拥塞使得无法为具有服务质量要求的数据流提供带宽或时延保证。首先对数据中心网络的路由问题进行分类分析，然后着重介绍了单播路由方法的研究进展，进一步对拥塞感知的路由方法进行了介绍，最后讨论了新型数据中心网络的路由技术。

关键词: 数据中心网络, 路由协议, 拥塞控制, 联合优化

Abstract: Due to the rapid development of cloud computing, the demand of Internet service providers for data centers is increasing rapidly. As a key technology of data center networks, routing is responsible for selecting routes for network traffic within or across data centers. It can also provide diffe- rential services for traffic with different QoS (Quality of Service) requirements. However, for large-scale data centers, due to the unpredictable traffic of applications and the topology characteristic of data centers, the traditional routing methods in the Internet cannot provide satisfactory high throughput and resource utilization. Network congestion make it hard to provide guaranteed bandwidth or transmission delay for flows with the demand of QoS. This paper classifies and compares the routing problems in data centers, and then emphatically introduces the research progress about the unicast routing methods. Further, the congestion-aware routing methods are introduced. Finally, the routing technology of the new data center networks is discussed.

Key words: data center network, routing protocol, congestion control, joint optimization

段晨, 彭伟, 王宝生. 数据中心网络路由研究进展[J]. 计算机工程与科学, 2022, 44(04): 631-644.

DUAN Chen, PENG Wei, WANG Bao-sheng. Research progress of routing techniques for data center networks[J]. Computer Engineering & Science, 2022, 44(04): 631-644.

参考文献［54］

［1］	Habib S, Bokhari F S,Khan S U.Routing techniques in data center networks［M］∥Handbook on Data Centers.New York:Springer,2015:507-532.
［2］	Quttoum A N.Interconnection structures,management and routing challenges in cloud-service data center networks:A survey［J］.International Journal of Interactive Mobile Technologies (iJIM),2018,12(1):36-60.
［3］	Rekhter Y, Li T, Hares S. A border gateway protocol 4 (BGP-4):RFC 4271［S］.New York:The Internet Society,2006.
［4］	Lapukhov P,Facebook,A.Premji,et al.Use of BGP for routing in large-scale data centers:RFC 7938［S］.New York:The Internet Society,2016.
［5］	Li D,Li Y,Wu J,et al.ESM:Efficient and scalable data center multicast routing［J］.IEEE/ACM Transactions on Networking,2011,20(3):944-955.
［6］	Abu-Libdeh H,Costa P,Rowstron A,et al.Symbiotic routing in future data centers［C］∥Proc of the ACM SIGCOMM 2010 Conference,2010:51-62.
［7］	Chen C C,Yuan L,Greenberg A,et al.Routing-as-a-service (RaaS):A framework for tenant-directed route control in data center［J］.IEEE/ACM Transactions on Networking,2013,22(5):1401-1414.
［8］	Besta M, Schneider M, Cynk K,et al.FatPaths:Routing in supercomputers,data centers,and clouds with low-diameter networks when shortest paths fall short［J］.arXiv:1906.10885,2019.
［9］	Greenberg A,Hamilton J R,Jain N,et al.VL2:A scalable and flexible data center network［C］∥Proc of the ACM SIGCOMM 2009 Conference on Data Communication,2009:51-62.
［10］	Al-Fares M,Loukissas A,Vahdat A.A scalable,commodity data center network architecture［J］.ACM SIGCOMM Computer Communication Review,2008,38(4):63-74.
［11］	Guo C, Lu G, Li D, et al. BCube:A high performance,server- centric network architecture for modular data centers［C］∥Proc of the ACM SIGCOMM 2009 Conference on Data Communication,2009:63-74.
［12］	Guo C, Wu H, Tan K, et al. Dcell:A scalable and fault- tolerant network structure for data centers［C］∥Proc of the ACM SIGCOMM 2008 Conference on Data Communication,2008:75-86.
［13］	Wang T,Su Z,Xia Y,et al.SprintNet:A high performance server-centric network architecture for data centers［C］∥Proc of 2014 IEEE International Conference on Communications (ICC),2014:4005-4010.
［14］	Benson T,Anand A,Akella A,et al.MicroTE:Fine grained traffic engineering for data centers［C］∥Proc of the 7th Conference on Emerging Networking Experiments and Techno- logies,2011:1-12.
［15］	Wu X,Yang X.Dard:Distributed adaptive routing for datacenter networks［C］∥Proc of 2012 IEEE 32nd International Conference on Distributed Computing Systems,2012:32-41.
［16］	Li Z,Zhang Y,Li D,et al.OPTAS:Decentralized flow monitoring and scheduling for tiny tasks［C］∥Proc of the 35th Annual IEEE International Conference on Computer Communications(INFOCOM 2016),2016:1-9.
［17］	Al-Fares M,Radhakrishnan S,Raghavan B,et al.Hedera:Dynamic flow scheduling for data center networks［C］∥Proc of the 7th USENIX Conference on Networked Systems Design and Implementation, 2010: 19-20.
［18］	Nong Huang-wu, Huang Chuan-he, Huang Xiao-peng. SDN-based multipath routing algorithm for Fat-tree data center networks［J］. Computer Science, 2016, 43(6):32-34. (in Chinese)
［19］	Yang Yang,Yang Jia-hai, Qin Dong-hong. Multipath rout- ing algorithm for data center networks［J］. Journal of Tsinghua University(Science and Technology), 2016, 56(3):262-268. (in Chinese)
［20］	Peng Da-qin, Lai Xiang-wu, Liu Yan-lin. Multi-path rout- ing algorithm for Fat-tree data center network based on SDN［J］. Computer Engineering, 2018, 44(4): 41-45. (in Chinese)
［21］	Tam A S-W, Xi K, Chao H J.Use of devolved controllers in data center networks［C］∥Proc of 2011 IEEE Conference on Computer Communications Workshops,2011:596-601.
［22］	Spring N T, Mahajan R, Wetherall D.Measuring ISP topo- logies with rocketfuel［J］.ACM SIGCOMM Computer Communication Review,2002,32(4):133-145.
［23］	Ramos R M, Martinello M,Esteve R C.SlickFlow:Resilient source routing in data center networks unlocked by OpenFlow［C］∥Proc of the 38th Annual IEEE Conference on Local Computer Networks,2013:606-613.
［24］	Wang Y C,You S Y.An efficient route management framework for load balance and overhead reduction in SDN-based data center networks［J］.IEEE Transactions on Network and Service Management,2018,15(4):1422-1434.
［25］	Chen Song, Xie Wei. Routing optimization design for data center network traffic［J］. Communications Technology, 2018, 51(8):1883-1887.(in Chinese)
［26］	He K,Rozner E,Agarwal K,et al.Presto:Edge-based load balancing for fast datacenter networks［J］.ACM SIGCOMM Computer Communication Review,2015,45(4):465-478.
［27］	Sinha S, Kandula S, Katabi D.Harnessing TCP’s burstiness with flowlet switching［C］∥Proc of the 3rd ACM Workshop on Hot Topics in Networks (HotNets), 2004:1.
［28］	Shang Y F,Li D, Xu M W. Energy-aware routing in data center network［C］∥Proc of the 1st ACM SIGCOMM Workshop on Green Networking,2010:1-8.
［29］	Xu M W, Shang Y F, Li D,et al.Greening data center networks with throughput-guaranteed power-aware routing［J］.Computer Networks,2013,57(15):2880-2899.
［30］	He Rong-xi, Lei Tian-ying, Lin Zi-wei. Multi-constrained energy-saving routing algorithm in software-defined data center networks［J］. Journal of Computer Research and Development, 2019, 56(6):1219-1230.(in Chinese)
［31］	Alizadeh M,Greenberg A,Maltz D,et al.DCTCP:Efficient packet transport for the commoditized data center［J］.ACM SIGCOMM Computer Communication Review, 2010, 40(4):63-74.
［32］	Vamanan B, Hasan J, Vijaykumar T N. Deadline-aware datacenter TCP (d2TCP)［J］.ACM SIGCOMM Computer Communication Review,2012,42(4):115-126.
［33］	Mittal R, Lam V T,Dukkipati N,et al.TIMELY:RTT-based congestion control for the datacenter［J］.ACM SIGCOMM Computer Communication Review,2015,45(4):537-550.
［34］	Zhu Y, Eran H, Firestone D,et al.Congestion control for large-scale RDMA deployments［J］.ACM SIGCOMM Computer Communication Review,2015,45(4):523-536.
［35］	Montazeri B, Li Y, Alizadeh M, et al. Homa:A receiver- driven low-latency transport protocol using network priorities［C］∥Proc of 2018 Conference of the ACM Special In- terest Group on Data Communication,2018:221-235.
［36］	Cho I,Jang K,Han D.Credit-scheduled delay-bounded congestion control for datacenters［C］∥Proc of 2017 Conference of the ACM Special Interest Group on Data Communication,2017:239-252.
［37］	Kanagavelu R,Mingjie L N,Mi K M,et al.OpenFlow based control for re-routing with differentiated flows in data center networks［C］∥Proc of 2012 18th IEEE International Conference on Networks (ICON),2012:228-233.
［38］	Kanagevlu R,Aung K M M.SDN controlled local re-routing to reduce congestion in cloud data center［C］∥Proc of 2015 International Conference on Cloud Computing Research and Innovation (ICCCRI),2015:80-88.
［39］	Perry J,Ousterhout A,Balakrishnan H,et al.Fastpass:A centralized “zero-queue” datacenter network［J］. ACM SIGCOMM Computer Communication Review, 2014,44(4):307-318.
［40］	Vissicchio S,Tilmans O,Vanbever L,et al.Central control over distributed routing［C］∥Proc of 2015 Conference of the ACM Conference on Special Interest Group on Data Communication,2015:43-56.
［41］	Alizadeh M,Edsall T,Dharmapurikar S,et al.CONGA:Distributed congestion-aware load balancing for datacenters［J］. ACM SIGCOMM Computer Communication Review, 2014, 44(4):503-514.
［42］	Kandula S,Katabi D,Sinha S,et al.Dynamic load balancing without packet reordering［J］.ACM SIGCOMM Computer Communication Review,2007,37(2):51-62.
［43］	Katta N,Hira M,Kim C,et al.HULA:Scalable load balanc- ing using programmable data planes［C］∥Proc of the Symposium on SDN Research,2016:1-12.
［44］	Fan F,Hu B,Yeung K L.Routing in black box:Modularized load balancing for multipath data center networks［C］∥Proc of IEEE Conference on Computer Communications,2019:1639-1647.
［45］	Zhang J,Ren F,Huang T,et al.Congestion-aware adaptive forwarding in datacenter networks［J］.Computer Communications,2015,62:34-46.
［46］	Ghorbani S, Yang Z,Godfrey P B,et al.Drill:Micro load balancing for low-latency data center networks［C］∥Proc of 2017 Conference of the ACM Special Interest Group on Data Communication,2017:225-238.
［47］	Mitzenmacher M.The power of two choices in randomized load balancing［J］.IEEE Transactions on Parallel and Distributed Systems,2001,12(10):1094-1104.
［48］	Huang J,Lü W,Li W,et al.QDAPS:Queueing delay aware packet spraying for load balancing in data center［C］∥Proc of 2018 IEEE 26th International Conference on Network Protocols (ICNP),2018:66-76.
［49］	Kabbani A, Sharif M. Flier:Flow-level congestion-aware routing for direct-connect data centers［C］∥Proc of IEEE Conference on Computer Communications,2017:1-9.
［50］	Bao J, Dong D, Zhao B. DETOUR:A large-scale non- blocking optical data center fabric［C］∥Proc of Asian Conference on Supercomputing Frontiers,2018:30-50.
［51］	Wang G H,Andersen D G,Kaminsky M,et al.c-Through:Part-time optics in data centers［C］∥Proc of the ACM SIGCOMM 2010 Conference,2010:327-338.
［52］	Farrington N,Porter G,Radhakrishnan S,et al.Helios:A hybrid electrical/optical switch architecture for modular data centers［C］∥Proc of the ACM SIGCOMM 2010 Confe- rence,2010:339-350.
［53］	Chen L,Chen K,Zhu Z,et al.Enabling wide-spread communications on optical fabric with megaswitch［C］∥Proc of Networked Systems Design and Implementation,2017:577-593.
［54］	Yang Ting-ting. Study on topology reconstruction strategy for the intra data center optical switching network［D］. Beijing :Beijing University of Posts and Telecommunications, 2017. (in Chinese)
［55］	Sankaran G C,Sivalingam K M.A survey of hybrid optical data center network architectures［J］.Photonic Network Communications,2017,33(2):87-101.
［56］	Wang C H,Javidi T,Porter G.End-to-end scheduling for all-optical data centers［C］∥Proc of IEEE Conference on Computer Communications,2015:406-414.
［57］	Kandula J P S,Bahl P.Flyways to de-congest data center networks［Z］. United States: Microsoft, 2009.
［58］	Hamza A S.Recent advances in the design of optical wireless data center networks［C］∥Proc of Broadband Access Communication Technologies XIII.International Society for Optics and Photonics,2019:109450K.
［59］	Cui Y,Wang H,Cheng X,et al.Wireless data center networking［J］.IEEE Wireless Communications,2011,18(6):46-53.
［60］	Kuhn H W. The Hungarian method for the assignment problem［J］.Naval Research Logistics Quarterly,1955,2(1-2):83-97.
［61］	Celik A,Al-Ghadhban A,Shihada B,et al.Design and provisioning of optical wireless data center networks:A traffic grooming approach［C］∥Proc of 2018 IEEE Wireless Communications and Networking Conference,2018:1-6.
［62］	AlGhadhban A,Celik A,Shihada B,et al.SoftFG:A dynamic load balancer for soft reconfiguration of wireless data centers［C］∥Proc of 2020 IEEE Wireless Communications and Networking Conference,2020:1-5.
［63］	Vanini E,Pan R,Alizadeh M,et al.Let it flow:Resilient asymmetric load balancing with flowlet switching［C］∥Proc of the 14th USENIX Symposium on Networked Systems Design and Implementation,2017:407-420.
	附中文参考文献：
［18］	农黄武,黄传河,黄晓鹏.基于SDN的胖树数据中心网络的多路径路由算法［J］.计算机科学,2016,43(6):32-34.
［19］	杨洋,杨家海,秦董洪.数据中心网络多路径路由算法［J］.清华大学学报(自然科学版),2016,56(3):262-268.
［20］	彭大芹,赖香武,刘艳林.基于SDN的胖树数据中心网络多路径路由算法［J］.计算机工程,2018,44(4):41-45.
［25］	陈松,谢卫.面向数据中心网络流量的路由优化设计［J］.通信技术,2018,51(8):1883-1887.
［30］	何荣希,雷田颖,林子薇.软件定义数据中心网络多约束节能路由算法［J］.计算机研究与发展,2019,56(6):1219-1230.
［54］	杨婷婷.数据中心内光交换网络重构策略研究［D］.北京:北京邮电大学,2017.

[1]	周静, 关玉蓉. 基于SDN的DWSN技术分析及性能优化研究[J]. 计算机工程与科学, 2021, 43(08): 1413-1421.
[2]	李树楠1,2,3，詹男杰1,2,3，章玥1,2. 面向数据中心租户带宽特征的虚拟拥塞控制方法性能分析[J]. 计算机工程与科学, 2018, 40(09): 1562-1571.
[3]	任秀江1，斯添浩1，周建毅1，谢向辉2. 基于网络包延迟偏差的硬件动态拥塞控制机制[J]. 计算机工程与科学, 2018, 40(02): 200-209.
[4]	陈文广，牛玉刚，邹媛媛. 基于改进AOMDV路由协议的WSNs拥塞控制和能耗均衡策略[J]. 计算机工程与科学, 2016, 38(09): 1776-1783.
[5]	陈庭平，虞万荣，吴纯青. TCP传输中往返时延偏移智能响应机制研究[J]. 计算机工程与科学, 2016, 38(08): 1647-1653.
[6]	汪晓洁，郭文强，王思秀，蔡咏梅. 一种高效的最短路径完全动态更新算法[J]. J4, 2016, 38(03): 449-453.
[7]	罗旭，吴晓军. 蚁群优化算法在WSN路由中的应用研究[J]. J4, 2015, 37(04): 740-746.
[8]	陈雪寒，陈志刚，曾锋，吴嘉. WSN中一种基于时空相关性的网内数据聚合路由协议[J]. J4, 2015, 37(01): 48-55.
[9]	滕艳平，王海珍，金梅，李大辉. 一种Ad Hoc网络端到端的TCP拥塞控制改进方案[J]. J4, 2014, 36(08): 1493-1499.
[10]	吴斌，马继涛，邬平，谭鹏. 基于特征分析方法消解RED冗余参数[J]. J4, 2014, 36(08): 1519-1523.
[11]	程友清，余少华. IPv6网络中一种基于路由协议的PMTU发现机制[J]. J4, 2013, 35(2): 43-48.
[12]	陶勇1,2,龚正虎2. 一种节点权重自适应调整的DTN拥塞控制[J]. J4, 2013, 35(1): 52-56.
[13]	王璨，骆坚，张大方，黎文伟. 一种基于移动性的无线传感器网络分簇路由协议[J]. J4, 2012, 34(3): 6-12.
[14]	张华，廖明华. 一种基于博弈的拥塞控制改进算法G-Vegas[J]. J4, 2011, 33(3): 23-27.
[15]	彭立宏,张鹤颖,姜新文,窦文华. 基于价格的拥塞控制模型扩展[J]. J4, 2011, 33(2): 7-11.