分组交换光网络中的调度算法研究与仿真.pdf

摘要随着绲母咚俜⒄购涂泶际醯牟欢细拢泶悠怠⒍嗝教宓雀髦质凳数据流量急剧增加,对通信网的带宽和核心路由器的性能提出了更高的要求一更高的传输速率和提供确定的服务质量保障毖佣抖⑼掏铝康。为了适应日益增长的带宽资源需求,作为通信网的两大主要组成部分一传输和交换都在不断的发展和革新。近几年,由于光通信技术尤其是技术的成熟,光网络因其巨大的频带资源和优越的传输性能,使主干链路的传输带宽不再成为问题。然而,传统的基于总线和中央处理器结构的路由器,由于其体系结构上的局限已经无法满足组建高速主干网络的需求。国际上提出了用交换结构提高各接口单元之间的数据通信速度的基本思想,交换结构成为影响交换机性能的核心模块,光交换技术已经成为实现全光网络的核心技术。但目前世界上的光交换技术都处于电控光交换阶段,即信号交换是全光的,光器件的控制仍由电子电路来完成。为了保证一定的服务质量,核心路由器必须设法增加交换能力。在普遍采用的定长分组交换结构中,忽略同步和传输时延的情况下,核心交换机的性能主要受排队策略和调度算法的影响。排队策略决定如何缓存到达的分组;调度算法则是通过解决在每一个时隙中发生在相同输出端口的冲突问题,控制业务流对交换网络结构的有序访问。本文中基于目前最有发展前景的电存储一光交换混合结构,针对带有虚拟输出队列慕换煌缃峁梗芯苛朔肿榻换还馔缰械母咄掏铝亢偷投抖牡鞫任侍猓用基于矩阵分解的静态调度算法进行求解。在深入研究和分析了以往的调度模型与调度算法的基础上,,并制定了该问题特有的编码、交叉和变异等遗传算子的设计方案。最后,运用仿真程序分析了该算法的吞吐量、抖动性能,并与传统的算法进行了比较。关键词:调度,虚拟输出队列,遗传算法,抖动,吞吐量南京邮电大学硕士研究生学位论文第
.’甌瑃瑆曲甌瑃琷,:,琯瑄—。.,.,..甀瑂,,琧,疭瑆第页疭
符号说明虚拟输出队列服务质量遗传算法算法贪婪低抖动算法整数线性规划光分组交换链头阻塞波分复用无源光网络光网络单元光线路终端光/电/光转换。范南京邮电大学硕士研究生学位论文疎疧第页
~始蜘期:遍够侈髋蝼各渺瓤坐华够侈二鲁雅⋯名:埤嗍挫弛哆南京邮电大学学位论文独创性声明南京邮电大学学位论文使用授权声明工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材明确的说明并表示了谢意。本人所送交学位论文的复印件和电子文档,可以采用影印、缩印或其本人声明所呈交的学位论文是我个人在导师指导下进行的研究料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外,允许论文被查阅和借阅,可以公布ǹ论文的全部或部分内容。论文的公布ǹ授权南京邮电大学研究生部办理。
第一章绪论调度的基本概念调度算法类型随着计算机和通信网络的发展,人们对网络服务种类和质量提出越来越高的要求。针对现有的网络规模,如何高效管理和使用这些网络资源,如何对有限的网络资源进行合理分配,以便使现有的网络资源最大限度的发挥功效,来为更多的用户提供更优质的服务,成为网络调度的一个核心问题。网络调度不仅需要一个好的网络结构,更重要的是设计一种好的调度算法控制和协调业务流量,为用户提供满意的服务质量。相反,如果一个效率低下的调度算法,不仅会浪费资源,甚至会导致死锁,使得网络不能正常运行甚至瘫痪。广义的调度通常是指对工作、任务、资源等进行适当的分配和规划,从而满足预定的目标。狭义的调度是指一个与时间次序有关的资源分配的概念,即在多个用户争用资源时,如何确定一种服务次序,使各方面的利益最大化。从理论体系上讲,调度算法属于排对理论的一个分支。包括六个要素:调度者、被调度对象、调度目标、调度结构、调度算法和调度代价。其中调度算法鞫裙嬖颉⒌鞫然制橇悠渌鞲鲆K氐呐Υ6杓频鞫人惴ㄊ保枰T诘鞫却酆偷鞫饶勘曛间进行折衷。因此,调度问题实际上可以描述为一个多目标优化问题。根据被调度对象和调度代价的行为是否呈现出随机时变特性,可以将调度算法分为两种类型:静态调度和动态调度。静态调度是指事先为每一个预计要发生的特定业务分配一个固定的服务时隙,故也称为分配调度,属于一种非权重调度算法。动态调度则是根据业务需求的动态变化,在发生资源争用的情况下,灵活地采用相应策略对资源进行重新分配,避免了业务的拥塞和长时间等待,属于一种有权重调度算法。静态调度和动态调度优缺点:由于静态调度中,给定的资源需求和约束通常是在一段时间内固定不变的,所以调度算法不受计算时间的限制,一