计算机科学 ›› 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, Scheduling algorithm, Deadline-aware, Point-to-multipoint, Multi-source

中图分类号: 

  • 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] 窦浩铭, 姜慧, 陈思光. 基于SDN的负载均衡网络控制器算法[J]. 计算机科学, 2019, 46(6A): 312-316.
[2] 李晓光, 邵超. 基于网格数据中心的密度峰值聚类算法[J]. 计算机科学, 2019, 46(6A): 457-460.
[3] 金勇, 刘亦星, 王欣欣. 基于SDN的数据中心网络多路径流量调度算法[J]. 计算机科学, 2019, 46(6): 90-94.
[4] 王海燕,胡婷,王俊. 智慧警务系统在地市公安局的应用研究[J]. 计算机科学, 2018, 45(6A): 518-522.
[5] 樊自甫,李书,张丹. 基于流量调度的SDN数据中心网络拥塞控制算法[J]. 计算机科学, 2017, 44(Z6): 266-269.
[6] 乔焰,焦俊,饶元. 基于数据中心流量特征的端到端流量估计算法[J]. 计算机科学, 2017, 44(2): 171-175.
[7] 林强,吴国伟,万安民,于军帅. 一种无线网络控制系统的时空实时任务调度算法[J]. 计算机科学, 2016, 43(Z11): 278-281.
[8] 张颜. 一种Credit调度算法的改进算法[J]. 计算机科学, 2016, 43(Z11): 264-267.
[9] 孟飞,兰巨龙,胡宇翔. 基于Richards模型的数据中心骨干网络带宽分配策略[J]. 计算机科学, 2016, 43(1): 133-136.
[10] 郑剑,蔡婷,杜兴. 数据中心电费最小化的负载调度策略[J]. 计算机科学, 2015, 42(Z11): 542-543.
[11] 黄兆年,李海山,赵君. 基于双适应度遗传算法的虚拟机放置的研究[J]. 计算机科学, 2015, 42(Z11): 406-407.
[12] 李曌,滕飞,李天瑞,杨浩. 一种Hadoop中基于作业类别和截止时间的调度算法[J]. 计算机科学, 2015, 42(6): 28-31.
[13] 周东清,佀庆乾. 异构云平台中能源有效的虚拟机部署研究[J]. 计算机科学, 2015, 42(3): 81-84.
[14] 张天宇,关楠,邓庆绪. Xen虚拟机Credit调度算法的实时性能分析[J]. 计算机科学, 2015, 42(12): 115-119.
[15] 龙玉江,朱州. 基于本体的数据中心配置管理方法研究[J]. 计算机科学, 2014, 41(Z6): 494-498.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .