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

doi:10.11896/jsjkx.200300069

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

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

庄奕, 杨家海

清华大学网络科学与网络空间研究院北京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

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)

摘要/Abstract

摘要： 随着各种云应用的数据规模的增大,越来越多的云服务提供商开始关注跨数据中心的大数据块传输(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

庄奕, 杨家海. 限时点到多点跨数据中心传输的多源树调度算法[J]. 计算机科学, 2020, 47(7): 213-219.

ZHUANG Yi, YANG Jia-hai. Multi-source Tree-based Scheduling Algorithm for Deadline-aware P2MP Inter-datacenter Transfers[J]. Computer Science, 2020, 47(7): 213-219.

参考文献 19

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献 19

相关文章 15

Metrics

本文评价

推荐阅读 10

[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.