计算机科学 ›› 2020, Vol. 47 ›› Issue (7): 213-219.doi: 10.11896/jsjkx.200300069

所属专题: 网络通信

• 计算机网络 • 上一篇    下一篇

限时点到多点跨数据中心传输的多源树调度算法

庄奕, 杨家海   

  1. 清华大学网络科学与网络空间研究院 北京100084
    北京信息科学与技术国家研究中心 北京100084
  • 收稿日期:2020-03-10 出版日期:2020-07-15 发布日期:2020-07-16
  • 通讯作者: 杨家海(yang@cernet.edu.cn)
  • 作者简介:stzhuangyi@gmail.com
  • 基金资助:
    国家自然科学基金(61432009,61462009)

Multi-source Tree-based Scheduling Algorithm for Deadline-aware P2MP Inter-datacenter Transfers

ZHUANG Yi, YANG Jia-hai   

  1. Institute for Network Sciences and Cyberspace,Tsinghua University,Beijing 100084,China
    Beijing National Research Center for Information Science and Technology,Beijing 100084,China
  • Received:2020-03-10 Online:2020-07-15 Published:2020-07-16
  • About author:ZHUANG Yi,born in 1995,master.His main research interests include cloud computing,and resource scheduling.
    YANG Jia-hai,born in 1966,professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include network mana-gement,network measurement and security,cloud computing and network functions virtualization.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(61432009,61462009)

摘要: 随着各种云应用的数据规模的增大,越来越多的云服务提供商开始关注跨数据中心的大数据块传输(bulk transfer)。跨数据中心的大数据块传输面临的主要挑战是:如何找到最佳的资源调度算法,在用户指定的时限内,用最少的传输资源将用户的数据传输到指定的地点。文中设计了一种有效的带传输时限(transfer deadlines)的、点到多点(Point-to-MultiPoint,P2MP)的跨数据中心数据传输调度算法MSTB(Multi-Source Tree-Based algorithm)。在多源机制和多播转发树的帮助下,MSTB表现得比现有的最优方法更好。仿真实验结果表明,MSTB可以在保证低传输完成时间和低计算复杂度的同时,增加最高达91%的传输请求接受数,增加最高达54%的有效吞吐量。

关键词: 带传输时限, 点到多点, 调度算法, 多源点, 数据中心

Abstract: With the growth of the data volume for cloud applications,more and more cloud service providers pay attention to inter-datacenter bulk transfer.The main challenge of inter-datacenter bulk transfer is how to find the best resource scheduling algorithm,which uses the least resources to transfer the user’s data to the specified destinations before the specified deadline.This paper proposes MSTB(Multi-Source Tree-Based) algorithm,an effective scheduling solution for deadline-aware P2MP inter-da-tacenter transfers.With the help of multi-source mechanism and multicast forwarding tree,MSTB outperforms the state-of-the-art method.Simulation experiments show that MSTB can increase the number of transfer requests accepted by up to 91% and increase effective throughput by up to 54% with short transfer completion time and low computation complexity.

Key words: Datacenter, Deadline-aware, Multi-source, Point-to-multipoint, Scheduling algorithm

中图分类号: 

  • TP302
[1]HONG C Y,KANDULA S,MAHAJAN R,et al.Achievinghigh utilization with software-driven WAN[C]//Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM.2013:15-26.
[2]JAIN S,KUMAR A,MANDAL S,et al.B4:Experience with a globally-deployed software defined WAN[J].ACM SIGCOMM Computer Communication Review,2013,43(4):3-14.
[3]SUN G,XU Z,YU H,et al.Toward SLAs guaranteed scalable VDC provisioning in cloud data centers[J].IEEE Access,2019,7:80219-80232.
[4]Multi-datacenter replication in cassandra[OL].http://www.datastax.com/dev/ blog/multi-datacenter-replication.
[5]Azure sql database now supports powerful geo-replication features for all service tiers[OL].https://goo.gl/aD5iRv.
[6]Mapping Netflix:Content Delivery Network Spans 233 Sites[OL].http://datacenterfrontier.com/mapping-netflix-content-delivery-network.
[7]KANDULA S,MENACHE I,SCHWARTZ R,et al.Calendaring for wide area networks[C]//Proceedings of the 2014 ACM Conference on SIGCOMM.2014:515-526.
[8]ZHANG H,CHEN K,BAI W,et al.Guaranteeing deadlines for inter-data center transfers[J].IEEE/ACM Transactions on Networking,2016,25(1):579-595.
[9]LUO L,YU H,YE Z,et al.Online deadline-aware bulk transfer over inter-datacenter wans[C]//IEEE INFOCOM 2018-IEEE Conference on Computer Communications.IEEE,2018:630-638.
[10]JALAPARTI V,BLIZNETS I,KANDULA S,et al.Dynamicpricing and traffic engineering for timely inter-datacenter transfers[C]//Proceedings of the 2016 ACM SIGCOMM Confe-rence.2016:73-86.
[11]LUO L,KONG Y,NOORMOHAMMADPOUR M,et al.Deadline-Aware Fast One-to-Many Bulk Transfers over Inter-Datacenter Networks[J].IEEE Transactions on Cloud Computing,2019,doi:10.1109/TCC.2019.2935435.
[12]NOORMOHAMMADPOUR M,RAGHAVENDRA C S,RAO S,et al.Dccast:Efficient point to multipoint transfers across datacenters[C]//9th Workshop on Hot Topics in Cloud Computing (HotCloud 17).2017.
[13]NOORMOHAMMADPOUR M,RAGHAVENDRA C S,KANDULA S,et al.QuickCast:Fast and efficient inter-datacenter transfers using forwarding tree cohorts[C]//IEEE INFOCOM 2018-IEEE Conference on Computer Communications.IEEE,2018:225-233.
[14]ZHANG Y,JIANG J,XU K,et al.BDS:a centralized near-optimal overlay network for inter-datacenter data replication[C]//Proceedings of the Thirteenth EuroSys Conference.2018:1-14.
[15]JI S,LIU S,LI B.Deadline-aware scheduling and routing for inter-datacenter multicast transfers[C]//2018 IEEE International Conference on Cloud Engineering (IC2E).IEEE,2018:124-133.
[16]WANG Y,SU S,LIU A X,et al.Multiple bulk data transfers scheduling among datacenters[J].Computer Networks,2014,68:123-137.
[17]Tag:OpenFlow [OL].https://www.opennetworking.org/tag/openflow.
[18]Equinix Cloud Exchange Fabric [OL].https://www.equinix.com/interconnection-services/cloud-exchange-fabric.
[19]BANG-JENSEN J,GUTIN G Z.Digraphs:theory,algorithms and applications[M].Springer Science & Business Media,2008.
[1] 潘志勇, 程宝雷, 樊建席, 卞庆荣.
数据中心网络BCDC上的顶点独立生成树构造算法
Algorithm to Construct Node-independent Spanning Trees in Data Center Network BCDC
计算机科学, 2022, 49(7): 287-296. https://doi.org/10.11896/jsjkx.210500170
[2] 易怡, 樊建席, 王岩, 刘钊, 董辉.
BCube在2-限制连通度下的容错路由算法
Fault-tolerant Routing Algorithm in BCube Under 2-restricted Connectivity
计算机科学, 2021, 48(6): 253-260. https://doi.org/10.11896/jsjkx.200900203
[3] 张登科, 王兴伟, 何强, 曾荣飞, 易波.
可重构数据中心网络研究综述
State-of-the-art Survey on Reconfigurable Data Center Networks
计算机科学, 2021, 48(3): 246-258. https://doi.org/10.11896/jsjkx.201100038
[4] 蒋建峰, 尤澜涛.
基于MPLS-TE的数据中心网络QoS优化
QoS Optimization of Data Center Network Based on MPLS-TE
计算机科学, 2021, 48(11A): 485-489. https://doi.org/10.11896/jsjkx.210900190
[5] 窦浩铭, 姜慧, 陈思光.
基于SDN的负载均衡网络控制器算法
SDN-based Network Controller Algorithm for Load Balancing
计算机科学, 2019, 46(6A): 312-316.
[6] 李晓光, 邵超.
基于网格数据中心的密度峰值聚类算法
Density Peak Clustering Algorithm Based on Grid Data Center
计算机科学, 2019, 46(6A): 457-460.
[7] 金勇, 刘亦星, 王欣欣.
基于SDN的数据中心网络多路径流量调度算法
SDN-based Multipath Traffic Scheduling Algorithm for Data Center Network
计算机科学, 2019, 46(6): 90-94. https://doi.org/10.11896/j.issn.1002-137X.2019.06.012
[8] 樊自甫,李书,张丹.
基于流量调度的SDN数据中心网络拥塞控制算法
Traffic Scheduling Based Congestion Control Algorithm for Data Center Network on Software Defined Network
计算机科学, 2017, 44(Z6): 266-269. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.061
[9] 乔焰,焦俊,饶元.
基于数据中心流量特征的端到端流量估计算法
Traffic Estimation for Data Center Network Based on Traffic Characteristics
计算机科学, 2017, 44(2): 171-175. https://doi.org/10.11896/j.issn.1002-137X.2017.02.026
[10] 林强,吴国伟,万安民,于军帅.
一种无线网络控制系统的时空实时任务调度算法
Real Time Scheduling Algorithm for Temporal and Spatial Tasks in Wireless Networked Control Systems
计算机科学, 2016, 43(Z11): 278-281. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.065
[11] 张颜.
一种Credit调度算法的改进算法
Improved Scheduler of Credit
计算机科学, 2016, 43(Z11): 264-267. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.061
[12] 孟飞,兰巨龙,胡宇翔.
基于Richards模型的数据中心骨干网络带宽分配策略
Richards Model Based Data Center Backbone Network Bandwidth Allocation Policy
计算机科学, 2016, 43(1): 133-136. https://doi.org/10.11896/j.issn.1002-137X.2016.01.030
[13] 郑剑,蔡婷,杜兴.
数据中心电费最小化的负载调度策略
Workload Scheduling for Minimizing Electricity Cost of Data Center
计算机科学, 2015, 42(Z11): 542-543.
[14] 黄兆年,李海山,赵君.
基于双适应度遗传算法的虚拟机放置的研究
Virtual Machine Placement Algorithm Based on Improved Genetic Algorithm
计算机科学, 2015, 42(Z11): 406-407.
[15] 李曌,滕飞,李天瑞,杨浩.
一种Hadoop中基于作业类别和截止时间的调度算法
Scheduler Algorithm Based on Type Specific and Deadline in Hadoop
计算机科学, 2015, 42(6): 28-31. https://doi.org/10.11896/j.issn.1002-137X.2015.06.006
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!