调度基于截止时间限制的大文件传输调度方法的研究

上海交通大学

硕士学位论文

基于截止时间限制的大文件传输调度方法的研究姓名张彭善

申请学位级别硕士

专业通信与信息系统

指导教师郭薇

20080101

上海交通大学硕士学位论文

基于截止时间限制的大文件传输调度方法的研究

摘要

随着分布式计算以及网格计算的高速发展越来越多的应用需要将许多大数据量的文件从远程的数据采集中心汇聚到位于计算中心的超级计算机上进行计算、存储或者显示通过对这些大文件的分析处理最终得到想要的结果。在汇聚的传输过程中这些大数据量的文件没有数据丢失 同时每一个文件传输请求需要在一个给定的截止时间期限之前传输到唯一的目的点—计算中心这样才不会影响计算中心的数据操作。我们希望所有的大数据文件都能够在截止时间之前汇聚到计算中心但是在网络负载非常高的情况下总有文件会超过它们的截止时间才传输完成。此时允许一定数量的文件在其截止时间之后传输完成但是对于超过截止时间的传输任务超过的时间越少越好。这类问题我们称之为截止时间限制的大文件传输调度问题。

本文中我们首先给出以获得最小平均延迟时间为目的的大文件传输的一些解决方法的相关研究和分析然后分别给出了光网络中静态和动态情况下的截止时间限制的大文件传输问题的解决方案。

大文件传输是一个路由和调度结合的问题首先必须通过路由给每个大文件传输选择传输路径其次通过调度决定传输次序进而最终达到我们的目标。本文中我们提出一种新的用于计算路由的动态路由算法并将此动态路由和文件调度启发式算法结合起来解决我们的研究问题。通过动态路由来动态调整网络中的所有光路为每个文件传输请求获得最佳的传输路由然后通过文件调度启发式算法调度等待队列中的文件

第I页

上海交通大学硕士学位论文

传输请求来达到我们最终的优化目标。

在本文中我们给出了基于J ava的仿真结果用来验证所提出的算法的优越性。通过仿真我们发现在同一种调度算法下 比起传统的路由算法使用我们的动态路由算法性能更好在几种文件调度启发式调度算法中我们发现最小截止时间先调度算法可以最好地达到我们的优化目标。

关键词截止时间 网格大文件传输光网络动态路由调度

第II页

上海交通大学硕士学位论文

RESEARCH OF DEADLINE-CONSTRAINED

SCHEDULING METHODS FOR LARGE FILE

TRANSFERS IN OPTICAL NETWORKS

AB STRAC T

The high-speed development of distributed computing systems and grid systems needs lots of files with large scale data aggregating from local computers to remote data processing center for computing, storing or displaying.These large files are expected to be aggregated without data loss and reach their destination before given deadlines.All the files should be aggregated to the final data processing center before their deadlines.

However,a few number of files transmitted over their deadlines are also allowed in high load conditions.But we want to decrease the difference between the real finish time and the deadline for the file which is finished over its deadline.This problem is named as the Deadline-constrained Large File Transfer Problem(DLFTP).

In this paper,we introduce the recent research on large file transfers firstly,and then give the analysis and conclusions.Secondly,we give the solution of this problem in static and dynamic conditions.

DLFTP is a problem combining routing and scheduling.We have proposed a new dynamic routing algorithm to solve the routing problem.Then a novel algorithm to combine dynamic routing and scheduling in optical networks has also been proposed,which has two mainly processes.One is dynamic routing process by which we can find the“best”route for the file transfer and dynamically switch light-paths between the primate routing path and the alternate routing path to make more files get light-paths

第III页

上海交通大学硕士学位论文

with enough bandwidth.The other process is file scheduling process. In this process we schedule the files of the waiting queue according to the network traffic distribution to make more files transmission can be finished before their deadlines.We proposed many scheduling strategies in this paper.

In order to compare the performance of our algorithm,a Java-based simulator is also proposed.By simulation,we can find that by using our dynamic routing we can get better results than traditional routing algorithms in case of using the same scheduling strategy.For scheduling strategies proposed in this paper,we can find that Earliest Deadline First Scheduled strategy performs best.

KEY WORDS:Deadline,Grid,Large File Transfer,Optical Network,Dynamic Routing,Sche duling

第IV页

上海交通大学硕士学位论文

图片目录

图1 TPSP图形表示. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12

图2某条路由的带宽函数. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23

图3 VBLS的带宽利用示意图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23

图4动态路由示例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30

图5拓扑结构和文件集合. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33

图6最小截止时间先调度算法的最优性证明. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36

图7 MDFF-R、 LFF-R、 SDFF-R、 SLFF-R的超过截止时间的最大滞后时间

的比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38

图8 MDFF-R、 LFF-R、 SDFF-R、 SLFF-R的超过截止时间的任务数量结果

的比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38

图9 MDFF-R、 SDFF-R、 SLFF-R和LFF-R的平均滞后时间的比较. . . . . . . . . . . .39图10 MDFF-R、 SDFF-R、 SLFF-R、 LFF-R和OILP的平均延迟时间的比较

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39

图11路由和调度算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46

图12动态路由和调度算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .48

图13拓扑结构和文件集合. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49

图14时序图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49

图15 14-Node NSFNET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51

图16 LCA-FAFS、 LCA-EDFS、 LCA-SLFS、 LCA-SBFS超过截止时间的最

大滞后时间的比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53

图17 DRA-FAFS、 DRA-EDFS、 DRA-SLFS、 DRA-SBFS超过截止时间的

最大滞后时间的比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53

图18 LCA-EDFS、 DRA-EDFS得到超过截止时间的最大滞后时间的比较. . .54图19 LCA-FAFS、 LCA-EDFS、 LCA-SLFS、 LCA-SBFS超过截止时间的任

务数量的比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .54

图20 DRA-FAFS、 DRA-EDFS、 DRA-SLFS、 DRA-SBFS超过截止时间的

任务数量的比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55

图21 LCA-SLFS、 DRA-SLFS超过截止时间的任务数量的比较. . . . . . . . . . . . . . . . . . . .55

图22 LCA-FAFS、 LCA-EDFS、 LCA-SLFS、 LCA-SBFS的平均滞后时间的

比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56

第VII页

上海交通大学硕士学位论文

图23 DRA-FAFS、 DRA-EDFS、 DRA-SLFS、 DRA-SBFS的平均滞后时间

的比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56

图24 LCA-EDFS、 DRA-EDFS的平均滞后时间的比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57

图25 LCA-FAFS、 DRA-FAFS、 DRA-EDFS、 DRA-SLFS、 DRA-SBFS的

平均延迟时间的比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57

第VIII页

上海交通大学硕士学位论文

表格目录

表1性能比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34

表2性能比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50

第IX页

上海交通大学硕士学位论文

符号说明

ASON Automatic Switched OpticalNetwork智能光网络ATM Asynchronous Transfer Mode异步传输模式

DP Disjoint-Path Scheduling不相干路径调度

DRA Dynamic Routing Algorithm动态路由算法

FAFS First Arrive First Serve先来先服务

KSPA K-ShortestPathAlgorithmK最短路径算法

LCA Least CongestionAlgorithm最小拥塞算法

LFF LongestFileFirst最大文件先调度

MDFF MostDistanceFileFirst最远文件先调度

OXC OpticalCross Connect光交叉连接

QS QualityofService服务质量

SBFS Smallest BandwidthFirst Serve最小带宽先服务SDFF Smallest Deadline File First最小截止时间文件先调度SDFS Smallest Deadline First Serve最小截止时间先服务SDH Synchronous Digital Hierarchy同步数字体系

SLFF Smallest LaxityFile First最小松弛文件先调度SLFS Smallest LaxityFirstServe最小松弛先服务

SONET Synchronous Optical Network同步光网络

SPA Shortest PathAlgorithm最短路径算法

TPSP Time-PathScheduling Problem时间路径调度问题TRC TimeRange Capacity时间范围容量

VBLS Variable Bandwidth List Scheduling可变带宽列表调度VLBI Very Long Baseline Interferometry超远距离基准调度仪WDM Wavelength Division Multiplexing波分复用

第X页