基于光网络的分布式计算系统中任务与通信的联合调度研究

论文摘要

分布式计算将分散在不同地方的计算、存储等资源集结起来,协同合作,从而获得可观的计算能力,以便用于实现复杂的科学计算任务。很多高级应用不但是计算密集型,更体现出数据密集型,即计算任务执行期间将会产生大量数据(从GB到TB甚至PB级),并在多个计算资源间进行大块数据传输。这就要求网络能够提供大带宽、低延迟的数据传输能力。传统的IP网络显然无法满足这种较高的QoS要求,因此研究人员将目光转向光网络,期望能够直接在光网络上构筑分布式计算系统以满足数据密集型的分布式科学计算应用。为了实现分布式计算,需要将复杂的、大型的计算任务分解为若干小任务,并将其调度到可用计算资源上,同时实现某种优化目标。分布式环境下的任务调度已有大量研究,但大都基于分组交换网络(如IP网络)。在数据量交换不多的情况下,很多研究直接将底层网络假设为任意节点对间可随时通信的全互联理想网络模型。当网络系统替换为光网络时,通信机制变为线路交换。由于传输数据之前需要事先建立固定带宽的光路连接,并且接入端口只具有单可达性,这就会使通信建立存在一定的阻塞概率。传统的任务调度模型无法直接应用于光网络互联场景,因此在将任务分配到计算资源上的同时,需要协同考虑资源间的光路建立。本论文研究任务分配与光路建立的联合调度问题,该问题之前鲜有研究。我们首先研究了在专有光网络下的联合调度模型和算法以及减少通信竞争冲突的优化策略,然后研究了在公共光网络下基于动态共享光虚拟专用网(OVPN,Optical Virtual Private Network)的联合调度问题,最后设计并实现了面向分布式计算应用的跨域OVPN服务接口体系。第一章绪论首先介绍了基于光网络互联的分布式计算的发展背景,然后分别综述了分布式计算中的任务调度和光网络中的光路调度的研究现状,并分析了研究联合调度的必要性。第二章研究了联合调度模型和算法。大规模的分布式科学计算应用大都由一系列具有相互依存关系的任务组成,并按照某种工作流方式实现最终计算任务。这种工作流一般采用有向无圈图(DAG: Directed Acyclic Graph)来统一描述。因此我们研究的联合调度可抽象为光网络感知的DAG调度问题。列表调度算法是DAG调度中最常用的启发式算法,为此我们根据联合调度模型对列表调度算法进行了扩展,在将DAG中的任务节点调度到计算资源上的同时,协同考虑将DAG边调度到网络的链路上,从而实现了任务与光路的联合调度。第三章基于扩展列表调度算法分别从路由策略和计算资源选择策略两个方面研究了如何减少网络资源冲突的优化措施。对于路由策略,我们提出了一个自适应路由算法,在调度某条光路时能够绕过拥塞链路并选取一条最先开始的最短路由;对于计算资源选择策略,我们的做法是尽量让后继任务节点调度到离前继任务节点所在资源较近的计算资源上,其思想是尽量减少光路的建立跳数,从而减少光路对资源的占用和产生冲突的可能性。仿真结果表明两种策略各有优势:自适应路由策略对于减小调度长度效果明显,而资源选择策略有利于提高任务调度对网络资源的使用使用效率。当二者结合使用时,优势互补,可获得最佳调度结果。第四章研究了在公共光网络上如何实现联合调度的问题。由于在公共光网络场景下运营商考虑到商业利益,不会向计算用户提供全网的资源信息,因此无法实现基于全网拓扑信息的联合调度,为此我们提出采用光虚拟专用网(OVPN)方式解决这一问题。OVPN资源可以是专有的或是共享的。对于专有OVPN可以直接使用之前提到的静态调度算法,但是会占用过多的网络资源。动态共享OVPN可以提高网络资源使用效率,但引入了网络资源的动态变化,为此我们提出了一种低开销的基于静态调度的动态重调度机制。仿真实验显示,在中等网络负载以下,基于动态共享OVPN的重调度机制可以获得接近于基于全网的静态联合调度的调度效果,并具有现实可行性。第五章研究了在多域光网络环境下如何为分布式计算应用实现跨域OVPN服务的接口体系。通过提供跨域OVPN服务,可以为计算用户屏蔽底层多域环境和复杂的域间操作,使之感觉仍然为单域环境。我们分析了面向分布式计算的跨域OVPN服务新的应用需求,并提出了一个层级式跨域OVPN服务平面体系构架。与其他OVPN服务平面实现方式不同,我们基于控制平面中的流量工程数据库(Traffic Engineering Database,TED)实现OVPN资源的分割和虚拟化;通过对OVPN资源及其操作封装并实例化为对象实现OVPN管理控制的划分和隔离。我们基于Webservice实现了跨域OVPN服务的调用接口,调度器可以直接编程实现OVPN资源的创建、信息获取,光路拆建等操作。最后在3TNet实验网上实现了跨2个ASON域的分布式计算调度模拟。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 基于光网络互联的分布式计算系统
• 1.2 分布式计算的任务调度
• 1.2.1 基于工作流的计算任务模型
• 1.2.2 资源管理系统
• 1.2.3 任务调度
• 1.3 光网络中的光路调度
• 1.3.1 路由和波长分配问题
• 1.3.2 预定光路调度
• 1.3.3 大文件传输
• 1.4 任务计算与光路通信的联合调度
• 1.5 本论文的研究内容和贡献
• 参考文献
• 第二章 计算任务与通信光路的联合调度模型
• 2.1 引言
• 2.2 联合调度模型
• 2.2.1 扩展资源模型
• 2.2.2 任务模型
• 2.2.3 光网络感知的DAG 调度
• 2.3 扩展列表调度算法
• 2.4 调度举例
• 2.5 仿真分析
• 2.6 本章小结
• 参考文献
• 第三章 通信竞争冲突的优化方法
• 3.1 引言
• 3.2 路由选择策略
• 3.2.1 自适应最先开始路径优先（AESPF）算法
• 3.2.2 不同路由策略下调度结果比较举例
• 3.3 资源选择策略
• 3.3.1 多级目标法
• 3.3.2 加权平均法
• 3.4 仿真分析
• 3.4.1 路由策略
• 3.4.2 资源选择策略
• 3.5 本章小结
• 第四章 基于OVPN 的动态重调度机制
• 4.1 引言
• 4.2 系统模型及问题描述
• 4.2.1 OVPN 设计
• 4.2.2 OVPN 资源管理
• 4.2.3 调度问题
• 4.3 计算和通信延迟感知的重调度机制
• 4.3.1 静态调度结果的鲁棒性
• 4.3.2 调度结果图
• 2DAR 重调度算法'>4.3.3 C²DAR 重调度算法
• 4.4 仿真分析
• 4.4.1 仿真设置
• 4.4.2 共享OVPN 场景下重调度性能评估
• 4.4.3 C2DAR 机制与CDAR 机制的比较
• 4.6 本章小结
• 参考文献
• 第五章 面向分布式计算的跨域OVPN服务系统设计与实现
• 5.1 引言
• 5.2 OVPN 服务相关工作
• 5.2.1 IETF L1VPN 网络构架和服务模型
• 5.2.2 已有的OVPN 实现
• 5.3 跨域OVPN 服务设计分析
• 5.3.1 新的需求
• 5.3.2 跨域OVPN 服务体系模型
• 5.3.3 跨域OVPN 拓扑计算和资源分配
• 5.4 跨域OVPN 服务具体设计
• 5.4.1 资源分割和管理隔离
• 5.4.2 单域SD-OVPN 服务
• 5.4.3 跨域MD-OVPN 服务
• 5.5 原型实现与性能测试
• 5.5.1 NETCONF 管理接口实现
• 5.5.2 单域OVPN 服务实现与测试
• 5.5.3 跨域OVPN 服务实现及DAG 调度实验
• 5.6 本章小节
• 参考文献
• 第六章 结束语
• 附录 A 基于WEB SERVICES 的光网络资源管理系统开发
• 附录 B 英文缩写对照
• 致谢
• 博士期间参加的科研项目
• 博士期间的论文工作