基于存储的光电路交换网络资源调度-张涛.pdf

《基于存储的光电路交换网络资源调度-张涛.pdf》由会员分享，可在线阅读，更多相关《基于存储的光电路交换网络资源调度-张涛.pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2018 年第 2 期中文核心期刊光网络基于存储的光电路交换网络资源调度Resource scheduling of optical circuitswitching network based on storageZHANG Tao, GUO Wei(School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China)Abstract: In transport networks with unbalanced link bandw

2、idth, the traditional circuit switching (TCS) end- to-end path establishment mechanism will cause bandwidth resource wastage. For this problem, a stor-age-based resource scheduling algorithm, Intermediate Store and Transfer Schedule(ISTS) algorithm has been proposed in this paper. The simulation res

3、ults show that, compared with TCS, ISTS algorithm can effectively improve the transmission success rate and link utilization.Key words: bulk data transfer; optical circuit switch; resource scheduling; static traffic; data storage张 涛，郭 薇（上海交通大学 电子信息与电气工程学院，上海 200240）摘要：在链路带宽具有不均衡性的传输网络中，传统电路交换（TCS）端到

4、端的建路机制会造成带宽资源浪费。针对此问题， 提出了一种基于存储的资源调度算法，即中间存储转发调度(ISTS)算法。仿真结果表明，与TCS相比，ISTS能够有效提高传输成功率和链路利用率。关键词：大数据传输；光电路交换；资源调度；静态业务；数据存储中图分类号：915.41 文献标识码：A 文章编号：1002-5561（2018）02-0005-04DOI：10.13921/ki.issn1002-5561.2018.02.0020 引言亚马逊、微软和 Facebook 等云服务提供商为了追求所提供的服务更靠近用户且能耗更低，通常会在全球建立多个数据中心1。 为了保证服务质量和提高访问的容错率，

5、这些云服务提供商需要定期同步和备份数据中心之间的数据，而这些数据量通常在 TB 到 PB范围之间2，这也意味着大数据传输会占据大量的带宽资源，并花费高昂的传输成本。 光电路交G80G81为G82低能耗、大带宽和高G83靠G84等G85G86成为大数据传输的G87G88G89G8A。在数据中心间的传输G8BG8C中，G8DG8BG8EG8FG90在G91G92用所G93G94的交G95G96G97量会G98G85G99G9AG9B，G82G9CG9D同G9E数据中心间的数据所G93G94的G9FG84G97量，这GA0G97量通常GA1需要在GA2定的GA3间GA4GA5成传输，GA6数据GA7

6、GA8的传输GA3GA9要求宽GAA3,4。G81GAB，用GACGADGAEG9FG84G97量的带宽GAFG87GB0GB1GB2G84。 而GB3文GB4GB5的GB6G9D带G87GB7GB8GA3间的大数据传输GB9务。 GA6GAC电路交G80，G82GBA到GBA的建路GBBGBC，在GBDGBE传输路GBFGC0所G87GC1路GC2GC3的带宽GC4GC5GC6GC7GC8GC9GBDGCA，G81GAB在GC1路带宽GAFG87GB0GB1GB2G84的G8BG8C中，GCBGCCGCD成带宽资源GCE费，且GCFG87G83能GD0GCAGD1求GD2GD3在GD4定GA

7、3间GA4GA5成传输。为了GD5GD6GC0GD7问GD8，GB3文提GD9在光电路交G80G8BG8C的中间GDAG86GDBGDCGDDGDEGDFGE0，GE1要GE2GA6大数据传输问GD8中的GE3GE4GE5务。 GE6：GD1求的GE7GE8G9D提GE9GEAGEB的，GECGED在GBD个云服务供G92商的数据中心间的传输G8BG8C中GEEGEF大数据传输， 在GA2定GD1求和G8BG8C资源GE7GE8GF0GF1GF2，GF3GF4G83能多的GD1求在GD4定GA3间GA4GA5成传输为GF5GF6，GF7GF8GBA到GBA的传输路GBFGC0GF9GFAGFB

8、GEFGB0GB1GFC的带宽GFD率，GFE而G87G88提高带宽资源GFF用率。收稿日期：2017-10-11。基金项目：国家自然科学基金（61471238、61433009）资助。作者简介：张涛（1993-），男，硕士研究G94，GE1要研究G89向为传输G8B路G8D与资源调度。 万方数据2018年第 2期1问题描述大数据传输的资源调度，需要解决以下 3 个方面的问题：时间窗的选择，每个请求都有各自的到达时间和截止时间，组成了相应的时间窗口，需要在时间窗口内选择进行数据传输的时间段； 路由计算，根据当前网络资源状况，选择一条合适的从源点到目的点的路径；带宽分配，根据所选择的传输路径，为

9、请求在相应链路上分配带宽。给定一个网络拓扑，用图 G=（V，E）表示，其中 V表示节点集合，E表示链路集合。因为本文研G80的大数据传输G81G82为G83G84G81G82G85G86，因G87传输请求的G88G89G8AG8B前G8CG8D的。 一个数据传输请求G88G89定G8E为：ri=(si,di,Fi,Ai,Di) （1）表示在请求集 R= ri1in! 中的请求ri需要从源点si传输 Fi大G8F的数据G90目的点 di，请求的到达时间为Ai， 请求需要在 Ai+DiG91前传输G92成。 相G93G94传输时G95，本文G96G97传G98时G95。本文G99G83G84请求的

10、资源调度问题目G9A定为G9BG9CG9DG9EG9FGA0的请求，GA1GA2大GA3请求GA4GA5传输成GA6GA7：GA2大GA3传输成GA6GA7=成GA6传输的请求数到达的请求GA8数2 中间存储转发调度 （Intermediate Store andTransfer Schedule, ISTS）算法因为G83G84大数据传输的资源调度问题GA9GAA到时间窗的选择、路由选择和带宽分配，GABG94 NP-Complete问题，GACGADGAE到一个算GAD在有GAF的GA0GB0GB1时间内GB2GB3GA2GB4解。 因G87，本文G8BGB5一GB6GB7GB8GB1算G

11、ADISTS 算GAD，GB9GBAGBB为GBC问题求GB3G9E行解。ISTS 算GAD以GBDGBE的GBF度GC0GC1GA0个G83G84G81G82请求，GBC算GADGC2要分为GC3个GC4段。 第一GC4段，GC5G94给定的请求GC6GC7GC8GB6GC9GCA进行GCBGCC，本文GCD用以 Fi/Di为GCE数从大到G8F的GCBGCCGCFG97， GCE数GD0大的请求GD1GD2GD3GD4GD5GD6，GB4GD7GD8GCBG87GD9请求的资源调度。 第GDAGC4段，GC5G94GCBGCCGDB的请求GDCGDD在各自到达时GDE的网络状况下进行路由G

12、DFGE0， GE1GE2GE3用 Dijkstra GA2GE4路径算GADGB9GE5GB3传输路径，GE6在到达时GDEGACGADGDFGE0到路由，GCAGE7请求GE8GE9GEAGEBGECGED。 第GC3GC4段，在上一GEEGDFGE0到的路径上进行带宽的GEFGF0，GE1GE2GCD用GF1GF2GEFGF0方GAD（Greedy Reserva-tion, GR）。根据GRGCFG97，GE6请求G9F在GC9定时间内G92成传输，GCAGD3GF3带宽资源；GF4GCA，GE7当前请求GE8GE9到GEAGEBGECGED。 在GC5GCBGCCGDB的请求G92成

13、以上GC3个GC4段GF5，GF6GC5GEAGEBGECGEDGE2的请求GF7行第GDA、GC3GC4段的GC0GC1。为了方GF8GC5 ISTS 算GAD的GF9GFA，GFBGFCGC5GFDGFEGFF如下定G8E：BW：网络中链路的剩余带宽集合；SR：成GA6调度的请求集合；QR：经GCBGCCG91GF5的有GCC请求集合；WR：需要GEAGEB的请求集合；Pi：请求 ri的传输路由；Ti：请求 riG92成传输的时GDE；T：请求推迟的时间单位；：时间段；S：请求传输路径上中间节点存储情况；reserveBW： 请求传输路径上每条链路带宽GEFGF0情况。基G94以上ISTS

14、 算GAD的GFDGFE定G8E，GFBGFC用表 1 中的伪代码GB9GF9GFAISTS 算GAD的流程。ISTS算GADRequire:ri=(si,di,Fi,Ai,Di)，BWStep 0. 初始GA3 SR=Step 1. GC5 N个请求（R= ri1iN! ）GC6GC7文件大G8F与截止时间的G93值从大到G8FGCBGCCGB3到 QRStep 2. forGC5G94每个 QR中的请求 rido2.1 以 Ai时GDE网络的链路剩余带宽的倒数为代价值，生成代价矩阵2.2 运用 DijkstraGA2GE4路径算GAD在代价矩阵上GE5GB3路由 Pi；GF4GCAGD4G

15、E9GEAGEBGECGEDWR2.3 根据 Pi，利用 Greedy Reservation(BW, Pi)方GAD进行带宽GEFGF0，并求GB3请求G92成传输时GDE Ti2.4 GE6 Tibwli thenrli=bwlielserli=(rli-1+si)/ end ifend forreturn reserveBW表2 用伪代码描述 GR算法的流程图 1 传输成功率 vs请求数图 2 链路利用率 vs仿真时间张涛，郭薇：GEE于存储的光电路交换G80G81GA0GA1调度 万方数据2018年第 2期光网络不同速率的带宽，以更加充分地利用带宽资源。 而TCS的带宽预约受限于传输路

16、径上链路的瓶颈带宽。请求平均传输时间。 TCS与ISTS在请求平均传输时间上随请求数的差异如图 3 所示, 此处针对成功传输请求的平均传输时间。 从图 3 可以看出，ISTS 在平均传输时间方面要略低于 TCS，这也意味着 ISTS 中请求在截止时间之前传输完成的前提下还能够更快地完成传输。 由于TCS的带宽预约方式受限于传输路径上链路的带宽瓶颈，而ISTS 又允许传输路径上运行不均G80的带宽速率，G81传输路径上前G82G83链路预约的带宽G84于G85G82G83链路预约的带宽时，G86G87的数G88G89G8AG8B在中间G8CG8D。 G81G85G82G83链路所能预约的带宽G8

17、4于前G82G83链路时，G89G8EG8FG8A在中间G8CG8D的数G88G90G91传输G92G93G8D。G94此，ISTS能更快地G95数G88传输完，ISTS中请求所G96的平均传输时间更G97。G8CG8DG98G99G8AG8B。图4 G9A对ISTS G9BG9C在不同请求数的G9DG9E下，G8CG8DG8AG8BG9F用G98G99的GA0GA1，从中可以看GA2，G8AG8BG98G99用GA3G84GA4GA5GA6在 600Gb GA7GA8，这GA9在G8CG8DGAAGABGACGAD的G8AGAEGAFGA3提GB0GB1GB2GB3。 由于GB4GB5G9A

18、以地GB6分GB7的数G88中GB8之间的传输GB9GBAGBBGBCGBDGBEGBF，G94此GC0GC1可以利用数G88中GB8GC2GC3的G8AGAE资源GC4GC5GC6在中间G8CG8D的G8AGAE。 随着GC7G8AGAEGC8GC9GCAGCBGCCG8AGAEGCDGCE的GCFGD0成GD1，G8AGAEGD2GD3G95GD4以更低的成GD5提GB0更GD6GD7的GD8GD9。4 结束语由于数G88中GB8间传输GB9GBA中GDAGDB式GDCGA3的G8A在，对于带GDD截止时间的G84数G88传输GDEGD9而GDF，GB9GBA链路带宽资源GE0GDD不均G

19、E1GE2，GD4GE3GA4利用 TCS 方式GE4行传输GE5成带宽资源GE6GE7的G9DG9E。 GD5GB5提GA2在传输GB9GBA的中间G8CG8DGE8GE9G8AG8BGD2GD3GC4G8FG8A时GEAGAFGEB的数G88，GEC能GED分利用GB9GBA的带宽资源，又能提GD6请求的传输成功率。 GEEGEF于传GA0的TCS方G9C，GD5GB5提GA2的ISTS G9BG9CGDDGD7提GD6GB1请求传输成功率GC8GB9GBAGF0GF1链路带宽利用率。 GF2此之GF3， 在平均传输时间方面，ISTS 也略低于TCS。GF4GC5上，G8AGAE在中间G8

20、CG8D的数G88可能GD4GDDGF5GF6方面的GF7GF8，这可以GF9GFA数G88加GFBGC8数G88GFCGFDGFEGFF等方G9C得到GDDGD7解决， 但GE0GF1方G9C不在GD5GB5GBCGBD范围内。G85G91工作，GC0GC1GD4G95不同的排序策略GC8不同GEF例的带宽分配方式对GB9GBAGE2能的影响作GBB主要GBCGBD内GAF。参考文献：1 WU Y, ZHANG Z, WU C, et al. Orchestrating bulk data transfers across geo-distributed datacenters J. IEE

21、E Transactions on Cloud Computing, 2017, 5(1): 112-125.2 SU S, WANG Y, JIANG S, et al. Efficient algorithms for scheduling multiple bulk data transfers in inter-datacenter networks J. International Journal of Communication Systems, 2014, 27(12): 4144-4165.3 NOORMOHAMMADPOUR M, RAGHAVENDRA C S, RAO S

22、, et al.RCD：Rapid Close to Deadline Scheduling for datacenter networks C/World Automation Congress (WAC), July31-August4, 2016, Rio Grande.Piscataway: IEEE, 2016.4 ZHANG H, CHEN K, BAI W, et al. Guaranteeing Deadlines for In-ter-Data Center Transfers J. IEEE/ACM Transactions on Networking, 2017, 25(1): 579-595. 图 3 请求平均传输时间vs请求数图 4 ISTS节点峰值存储 vs请求数张涛，郭薇：基于G8AGAE的光电路GDA换GB9GBA资源调度 万方数据