（通信与信息系统专业论文）obs网络调度算法及obs网络特性对tcp性能的影响.pdf

摘要 本文研究内容分为两部分，第一部分研究了光突发交换( o b s ) n 络中核心节点 的调度算法，第二部分研究了光突发交换网络特性对t c p 性能的影响。光突发交 换作为一种全光网络中的交换方式，相比现有的波长路由交换方式，具有资源利 用率高、适应动态的突发业务等特点。光突发交换网络中核心节点处的调度算法 是o b s 的关键技术之一，其目的是更好的利用信道资源以降低网络中突发的丢弃 率。本文对现有的调度算法进行了改进，并利用作者搭建的o b s 仿真平台将改进 后的算法与其他调度算法进行了比较，仿真结果表明了本算法能进一步的提升突 发的预约成功率。在研究光突发交换网络特性对t c p 性能的影响中，本文详细研 究了汇聚时延及汇聚后的突发长度对t c p 吞吐量性能的影响，发现并证明了当丢 失的突发中含有三个或更多连续的传输段时，t c p 发端必将超时重传。该发现有 助于建立光突发交换网络下的t c p 吞吐量模型。 关键词：光突发交换调度算法t c p 吞吐量 a b s t r a c t o p t i c a lb u r s ts w i t c h i n g ( o b s ) i sap r o m i s i n gs o l u t i o nf o ra l lo p t i c a lw d m n e t w o r k s i tc o m b i n e st h eb e n e f i t so fo p t i c a lp a c k e ts w i t c h i n ga n dw a v e l e n g t hr o u t i n gw h i l e t a k i n gi n t oa c c o u n tt h el i m i t a t i o n so ft h ec u r r e n to p t i c a lt e c h n o l o g y t h ep a p e rs t u d i e s t h es c h e d u l i n ga l g o r i t h m sa tt h ec o r en o d ei no b sn e t w o r k sa n dt h ei m p a c to fo b s n e t w o r k s c h a r a c t e r i s t i c so nt c pt h r o u g h p u t b a s e do nt h ee x i s t i n gs c h e d u l i n g a l g o r i t h m s ，an e ws c h e d u l i n ga l g o r i t h mi sp r o p o s e da n di ss h o w nt ob em o r ee f f e c t i v e t or e d u c et h eb u r s tl o s sp r o b a b i l i t yi no b sn e t w o r k i nt h er e s e a r c ho fo b sn e t w o r k s i m p a c to nt c pt h r o u g h p u t ，t h ea s s e m b l yd e l a ya n dt h eb u r s tl e n g t h si m p a c to nt c p p e r f o r m a n c ei ss t u d i e di nd e t a i l i ti sf o u n db ys i m u l a t i o na n d t h e o r e t i c a la n a l y s i st h a t w h e nal o s tb u r s tc o n t a i n st h r e eo rm o r ec o n t i n u o u ss e g m e n t s ，t h et c ps e n d e rw i l l s u r e l yt i m e o u t t h er e s u ki su s e f u lf o rb u i l d i n gt c pt h r o u g h p u tm o d e l so v e ro b s n e t w o r k s k e y w o r d ：o p t i c a lb u r s ts w i t c h i n g s c h e d u l i n ga l g o r i t h m t c p t h r o u g h p u t 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：馥叁 日期：卵占i f 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电乎科技大学， 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布_ _ 沦文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文：( 保密的论 文在解密后遵守此规定) 本人签名 导师签名 f 1 j 朝：坦厶：! 垡 日期：星盟! ! ! ! 第。章绪论 第一章绪论 1 1 引言 随着全球范围内通信业务尤其是i p 业务的迅猛发展，对通信网带宽和交换速 率的要求正以前所未有的速度增加。网络带宽方面，以1 9 7 6 年第一次实现光纤通 信为标志，此后，光纤通信技术以远远超乎人们预料的速度发展，目前，在光层 采用d w d m 技术使一根光纤上可利用的波长数可达2 5 6 个，每波长带宽可达 4 0 g b p s ，光纤总带宽超过1 0 t b i t s 左右，光纤传输上所取得的技术成就对网络节 点的交换能力提出了新的要求。而目前通信网的每个节点所采用的电交换技术已 经接近了电子速率的极限，其固有的r c 参数、抖动、漂移、串扰、响应速度慢等 缺点限制了交换速率的进一步提高，使得交换速率远远低于传送线路能提供的带 宽。这样，通信网的瓶颈就由传送线路的带宽转移到了交换系统上。为了克服这 个瓶颈，进而实现透明的、具有高度生存性的全光通信网，采用光交换技术成为 必然的发展趋势。 1 2 光交换技术概述 所谓光交换技术，是指在网络节点处到达的光信号不经过光电光转换，而是 在光域直接将输入的光信号交换到相应的输出端。光交换技术克服了电交换与光 传输子网并存带来的需配置大量光电接口和速率不匹配等问题，其优点包括大量 节省建网和网络升级成本，提高了网络的重构灵活性和生存性，加快网络恢复速 度，简化网络控制操作等。 为利用光交换带来的优势，人们相继提出了几种光交换的方法。与传统的电 交换技术类似，光交换技术从交换体制上也可以大致划分为光线路交换( o c s ， o p t i c a lc i r c u i ts w i t c h i n g ) 和光分组交换( o p s ，o p t i c a lp a c k e ts w i t c h i n g ) 两个大类。 光线路交换类似于现存的电路交换技术，它采用o x c 、o a d m 等光器件设置 光通路，中间节点不需要使用光缓存。其交换过程可分为三个阶段：光路建立、 光路保持、光路释放。光线路交换的成熟应用是波长路由光网络( w r o n ) ，它采 用多协议标签交换机制，对波长进行选路。借助波长转换器，波长路由可以得到 较好的应用。波长路由具有速度快、带宽大、对数据速率及格式透明的优点。但 这种面向连接的交换对于数据业务而言，链路的建立时间相对于链路的保持时间 较长，因而带宽利用率不高，且不够灵活u j 。 另外一种光交换方式称为光分组交换o p s ，该技术可以看作是电分组交换在 光域上的实现。分组的数据部分及头部信息一起发送到中间节点中，在中间节点， o b s 网络调度算法及o b s 网络特性对t c p 性能的影响 头部信息被处理( 可以是在光域或电域中进行) ，同时，数据部分在光域中暂时缓 存起来。光分组交换虽然仍遵循分组交换的“存储转发”原则，但分组的存储和 转发都是在光域中进行的。o p s 在交换粒度、带宽利用率、延时和适应性等方面 性能都比较好。光分组交换是一种非常有前途的技术，是光交换技术的最终发展 方向。但目前o p s 存在以下难点【l 】： ( a ) 光分组交换通常工作于同步状态，提取和插入分组头，需要时钟同步， 难度较大； ( b )光分组交换本质上是一种存储转发机制，现阶段缺乏可以实现随机存 取的光缓存设备，在研究中采用光纤延迟线( f d l ) 充当光缓存，只能 将相应的光分组数据按序延时一定的时间，而且通过增加延迟线数目 来满足大容量缓存需求也是刁i 实际的； ( c )光分组交换对配置光交换矩阵延时要求较严格。 因此，在一些关键性的光器件如高速光开关、光缓存器、光逻辑器件等取得 重大突破之前，光分组交换技术尚难以走出实验室。 针对目前光线路交换和光分组交换技术中存在的一些问题，近年来，人们提 出了一种新的光交换技术一光突发交换o b s ( o p t i c a lb u r s ts w i t c h i n g ) ，并迅速得到 国内外学者们的广泛研究。 1 3 1 光突发交换技术概述 1 3 光突发交换技术 光突发交换技术是由纽约州立大学布法罗( b u f f a l o ) 分校的c h t m m i n gq i a o 和华 盛顿大学的j o n a t h a n s t u r n e r 首先提出的【”1 2 1 。光突发交换技术结合了光线路交换 和光分组交换的一些优点，又克服了两者的不足，因此在企业界以及学术领域内 都引起了人们的研究兴趣。 光突发交换网络中的基本交换单元叫做突发( b u r s t ) ，也有文章称之为数据突发 f d a t ab u r s t ，d b ) ，以区别与突发相对应的控制分组( b u r s tc o n t r o lp a c k e t ，b c p ) 。本 文中将采用“突发”这一名词。在o b s 网络中，突发是指由到达o b s 网络边缘节 点处的业务分组( 可以是i p 分组，以太网帧等) 按照某种汇聚算法汇聚而成的一个 数据块，组装在同一个突发中的业务分组须具有相同的属性，这里相同的属性可 以是相同的目的地址，相同的业务等级等。突发的控制分组中包含有突发的一些 基本信息，如突发长度、偏置时间、突发的预定传输波长等。 光突发交换的一个显著特点在于突发的控制分组和突发在空间和时间域上完 全分离。在空间域上，o b s 为控制分组分配专用的波长信道，即突发和控制分组 在不同的波长上传输，使得控制分组可以经过光电光转换在电域中处理，而突发 第章绪论 不用经过光电光转换在全光域中进行传输。在时间域上，控制分组比突发提前一 段时间发送，以保证核心节点有足够的时间处理控制分组，控制分组在核心节点 中经过光电转换后在电域内进行处理，为其相应的突发预约网络资源，这种预约 网络资源的方式称为“单向预约”，即不论预约成功与否，核心节点都不向边缘节 点返回预约的确认消息。如果控制分组成功的预约了网络资源，则随后到达的突 发在核心节点中可以透明的在光域中交换传输，避免使用光存储设备。如果控制 分组在某个核心节点处预约网络资源失败，则随后到达的突发会在该核心节点处 被丢弃。 o b s 网络中包括两种功能节点：边缘节点与核心节点。其中边缘节点主要负 责突发的汇聚和拆分功能。在o b s 网络的入边缘节点处，所有进入该节点的业务 分组根据其目的地址和q o s 等属性被重新分类、排队，然后按照某种汇聚算法将 这些业务分组封装为一个个的突发，并根据突发的属性产生一个相应的控制分组。 边缘节点封装好突发后，先将控制分组发送到o b s 网络中，经过一段时间( 称为 o f f s e t t i m e ，即偏置时间) 后，才发送相应的突发。o b s 网络中的核心节点主要由光 交换矩阵和交换控制单元组成，负责对突发的控制分组进行处理，以及为突发配 置相应的交换矩阵。当突发到达o b s 网络的出边缘节点时被还原为一个个的业务 分组。由于控制分组的提前发送和处理，使得突发在交换节点处不必经过光缓存， 缓解了光分组交换对光缓存技术的苛求。 光突发交换网络的结构如图1 1 所示。 图1 1 光突发交换网络结构 1 3 2 光突发交换技术的研究现状 鉴于光波长交换的不灵活和光分组交换技术在近期内难以实现等因素，o b s 4 o b s 网络调度算法及o b s 网络特性对t c p 性能的影响 概念一经提出便受到了国内外越来越多的研究机构和学者的重视。目前，美国、 日本、韩国、欧洲、我国大陆和台湾等国家和地区都有研究机构从事o b s 方面的 研究。其中较有影响的有美国的纽约州立大学、华盛顿大学、卡罗来纳大学以及 阿尔卡特公司等。在我国，近几年都有o b s 的研究计划列为8 6 3 项目计划。其中， 清华大学、北京邮电大学和上海交通大学在国家8 6 3 计划的支持下对o b s 的关键技 术做了较为深入的研究，并初步建立了0 b s 的研究平台【3 d 到目前为止，对o b s 的研究主要集中在以下几个方面： 1 ) o b s 网络边缘节点的突发组装：伦敦大学的m d u s e r 用大偏差理论 来估计自相似业务流中数据分组长度的均值和方差，进而提出利用估 计值来使突发长度获得稳定的白适应组装算法 4 1 ：台湾新竹交通大学 的m c y u n g 提出了称为q b t ( q o sb u r s t i f i c a t i o n ) s n 装算法1 5 ，它着眼 于在不同类的业务之间保证公平性。此外，还有其他一些关于组装算 法的研究报道。虽然理论分析表明上述组装算法都可以得到一定的效 果，但它们都过于复杂。因此，目前用于o b s 研究的最通用的组装 算法仍然是传统的基于组装时间加突发长度限制的算法 2 ) o b s 信令协议：美国纽约州立大学的m y u n g s i k y o o 和c h u n m i n gq i a o 提出了适用于o b s 的带宽利用率高的传输协议j e t ( j u s t - e n o u g h t i m e ) 协议1 6 j ，该协议还能利用额外的偏置时间来在o b s 网络中实现对业务 q o s 的支持：t e l c o r d i a 公司的j o h ny w e i 等人提出将j i t ( j u s t i n - t i m e ) 协议用于o b s 网络【”，并在m o n e t 平台上做了j i t 协议的实验。 3 ) o b s 网络节点结构：波士顿n o k i a 研究中心的s a n j e e vv e r m a 对o b s 与i p o v e r - d w i ) m 的结合进行了研究，提出了网络边缘节点处m a c 层的功能结构【8 1 ；华盛顿大学的j o n a t h a ns t u r n e r 和a l c a t e l 美国分公 司的y i i u nx i o n g 也对o b s 网络节点的结构进行了研究和设计例。 4 ) o b s 网络核心节点信道调度算法：j o n a t h a ns t u r n e r 提出了水平调度 算法 2 1 ，该算法也被称为l a u c 算法【9 】；a l c a t e l 公司的l j u b i at a n c e v s k i 在l a u c 算法的基础上提出了效率更高的l a u c v f 算法【l0 】；美国得 克萨斯大学的m e iy a n g 提出了一种支持q o s 的调度算法【l ”，该算法 以l a u c v f 为基础，采用了为高优先级的突发先分配信道的策略。 5 )突发竞争的解决：当有多个突发控制分组在预约同一个输出光纤上的 同一个波长的时间上有重叠时，就会产生竞争冲突。在传统的电交换 机中，解决冲突的办法比较简单，即将发生冲突的分组利用电缓存暂 时储存起来随后发送，而在光突发交换网络中，突发在核心节点中的 交换传输都是在光域中进行的，目前尚难以提供与电缓存类似的光缓 存技术，因此对于发生冲突的突发，要么在核心节点中被丢弃，要么 第。章绪论 必须在突发到达核一t l , 节点之前就做好解决冲突的准备措旆。目前的解 决方案多集中在利用光纤延迟线和偏射路由技术上，此外还有几种技 术，如s a n j e e vv e r m a 提出的突发流整形技术”l 和意大利罗马大学的 a n d r e ad e t t i 提出的组合式突发技术o c b s 1 2 】，以及得克萨斯大学的 v i n o dm v o k k a r a n e 提出的突发分段技术i f ”。 6 )o b s 网络的数学理论建模：目前，对o b s 的研究绝大多数都是基于 计算机仿真的方法，而采用数学分析方法的研究很少，但已经开始起 步。比如，北卡罗来纳大学的l i s o n g x u 提出了o b s 网络边缘节点的 一种数学理论模型f 1 4 l 。 7 ) o b s 与其他技术的结合：这方面也有一些报道。例如，一部分学者研 究了o b s 在网络组播方面的应用；c h u n m i n gq i a o 提出了标记o b s 的概念i ”1 ；还有一部分学者研究了o b s 与波长路由技术的结合，以 及o b s 网络对t c p 性能的影响等i l “。 尽管o b s 的研究取得了相当的进展，但o b s 仍然处于实验室研究阶段。真正 的o b s 网络还不存在，o b s 离商用化尚有一段距离。o b s 还有一些问题尚未解决， 在诸如o b s 网络如何支持i p 等业务、如何把来自不同网络的数据适配进o b s 网 络并组装成突发、如何最有效地解决突发之间的竞争、o b s 协议及其具体实施、 o b s 与m p l s 的结合以及o b s 网络节点的硬件实现等问题上还需要进一步的研 究。 1 4 本文工作安排 本文在国内外现有研究成果的基础之上，对o b s 所涉及的部分关键技术做了 进一步的深入研究。主要包括波长转换器数目受限情况下的o b s 调度算法以及 o b s 网络特性对t c p 性能的影响。 全文内容安排如下： 第一章绪论，介绍了光突发交换技术的研究背景和意义，以及光突发交换的 有关关键技术及国内外研究现状。 第二章首先介绍了现有的调度算法，在分析现有调度算法的基础上提出了一 种新的调度算法m i n s v e v 。 第三章利用o p n e t 仿真软件实现了o b s 的仿真平台，并利用该平台对 m i n s v e v 算法及其他调度算法进行了仿真，对比结果表明本算法在丢包性能上有 所改进。 第四章研究了光突发交换网络对t c p 性能的影响因素，重点分析了汇聚时延 及突发长度对t c p 性能的影响，证明了当丢失的突发中含有三个或更多连续的分 6 o b s 网络调度算法及o b s 网络特性对t c p 性能的影响 组时，t c p 发端最终将超时重传。该结论有助于建立o b s 网络下的t c p 吞吐量模 型。 第五章结束语总结全文，并指出了几处需要进一步改进和研究的问题。 第二章波长转换器数目受限情况下的o b s 调度算法 第二章波长转换器数目受限情况下的o b s 调度算法 2 1 引言 o b s 网络中突发的丢弃率是一个比较严重的问题，带来此问题的关键是由于 光缓存技术的不成熟。在传统的电交换方式下，可以将发生冲突的分组在电缓存 中暂时存储起来，等待有可以利用的网络资源时再进行处理，电缓存技术已经非 常成熟，因此利用电缓存技术可以简单高效的降低网络的分组丢失率。o b s 网络 中缺乏相应的光缓存技术，因此需要采用其他手段来解决突发的冲突问题。常用 的光纤延迟线( f d l ) 技术通过将突发延迟段时间，将突发从有冲突的时间域转 移到无冲突的时间域上，但f d l 并不具备随机存储读取等的灵活性，只能实现 相对固定的时间延迟等简单功能。偏射路由( d e f l e c t i o nr o u t i n g ) 技术为发生冲突的 突发重新指配一条路由，将突发从有冲突的输出端口转移到无冲突的输出端口， 偏射路由技术给突发带来了较大的时延，且增加了核心节点的复杂度。其他的冲 突解决方案也存在类似的局限性。 以上的冲突解决方案可以称为是“事后”解决方案，即在冲突已经发生之后 的补救措施。相对于“事后”解决方案，调度算法可以称为“事前”解决方案， 因为调度算法的最终目标虽然也是使整个网络的突发丢弃率达到最低，但这个目 标是通过最大限度的避免突发发生冲突来达到的。o b s 网络中必须将发生冲突之 后的懈决方案和高效的调度算法结合起来才能使突发丢弃率达到最低。 调度算法的研究问题是如何为突发选择合适的波长从而减小突发发生冲突的 概率，因此在o b s 网络的核心节点中配置波长转换器是调度算法得以执行的基本 条件。现有的调度算法中，大多数没有考虑波长转换器个数的限制问题，既使突 发能在其原波长上进行传输而不必经波长转换时，在许多情况下也被转换到了其 它波长进行传输，这样其实就造成了波长转换器的浪费。由于可调谐波长转换器 在性能及价格上的原因，在核心节点中尚不可能为每个输出链路上的每个波长都 配置一个波长转换器，大多数情况下是采用节点共享波长转换器的方式，因此与 选择波长的调度算法类似，当在某个时间段内有多个波长转换器空闲时，如何有 效的选择其中之一扶而能最大程度的节省波长转换器的使用数目。也存在一个选 择策略问题。 本章在已有调度算法的研究基础上，对现有的调度算法做了些改进，提出 了一种新的调度算法，称为m i n s v e v 算法。为节省核心节点中波长转换器的使 用数目，在介绍了两种波长转换器的共享结构后，本文提出了一种波长转换器的 选择方法。 o b s 网络调度算法及o b s 网络特性剥t c p 性能的影响 2 2 核心节点中数据信道的调度算法 o b s 网络的一个关键技术是为到达核心节点的突发设计一个高效的调度算 法。调度算法研究的问题是，当一个到达核心节点的突发在其预定的输出链路上 有多个空闲的输出波长可供选择时，如何有效的选择其中的一个波长从而可以最 大的降低未来的突发发生冲突的概率。理想的调度算法应该能够在突发到达之前 足够快的对控制包处理完毕，同时还应该为突发选择一个最合适的空隙。否则， 就会因在突发到达时但尚未对其预约资源而被丢弃，或者因调度算法不够合理而 使有些突发不能得到资源的预约。 考虑到o b s 网络应用单向预约机制，例如j e t 协议f 6 j ，以及突发在核心节点 中不能被缓存( 缺乏有效的光缓存器件) ，突发的丢失率在o b s 网络中是一个十 分值得关心的问题。因此，设计一个既能快速处理调度又能有效预约资源的调度 算法在o b s 网络设计中是一个寸分重要的问题。 2 2 1 研究背景 目前性能较好的调度算法都采用了利用波长信道中的空隙的方法来对突发进 行调度，本小节首先阐述了波长中的空隙是如何产生的以及为什么可以利用空隙， 然后介绍了不同的为突发分配空闲波长的方法会如何影响将来的突发冲突概率。 在o b s 网络中，控制分组比相应的突发提前o 个单位到达核心节点，该时间 被称为偏置时间。如图2 1 所示，控制分组b c p l 与其相对应的突发b u r s t l 之间 的偏置时间为0 1 ，b c p 2 与其相应的突发b u r s t 2 之间的偏置时间为0 2 。虽然b c p l 早于b c p 2 到达核心节点，但由于偏置时间d j 比0 2 大许多的缘故，使得b u r s t l 到达核心节点的时间要晚于b u r s t 2 。由于b u r s t l 和b u r s t 2 在时间上的不连续，造 成了空隙v o i d 的产生。在传统网络中( 如i p 网络) ，分组之间也会有空隙，但该 环境下的空隙是不会被利用的，因为它位于过去的时间域内。在o b s 网络中，空 隙有可能位于将来的时间域内，因此就有可能被后来的突发利用，这就是调度算 法中常见的茔艨蜘v o i d - f i l l i n g ) 思想的由来。 赫盼啪鼍一一 瞪 突发信遒 ；! 劂岫 i + 1 叫o l 图2 1 空隙填充思想的坂理 第二率波长转换器数目受限情况下的o b s 调度算法 每个波长信道最初可以看作是一个从当前时刻到将来的空隙。每个空隙五可 以用一个有序对( s ，p ，) 来表示，其中5 ，和p ，分别代表空隙与的开始和结束时刻， 并且有e ， j ，。我们称一个空隙5 适合于一个突发b = 以刀，当且仅当s ， = f 。当把一个突发分配到一个合适的空隙耳中时，将有两个新的空隙产生， 分别为( s ，) 和( ，e ) 。 当某个突发预定的传输时间段在输出链路中有多个波长上都有合适的空隙 时，核心节点必须做出判断选择其中之一作为输出波长。不同的波长选择策略对 于将来的突发是否会避免竞争冲突会产生不同的影响，下面用图2 2 来解释这个 现象。 图丽圜露翮 縻黑聚霞飘 j 縻溺溺阑 f 麟黼黼 i， 隧麟鳓鳓湖 ， 一 ：7 n e w b u r s t 2 图2 2 不同的波长选择策略对突发冲突的影响 图2 2 给出了某核心节点中某一输出链路中的所有波长的突发分配情况，浅 色方块表示已经分配好的突发传输时间，n e w b u r s t l 是当前时刻新到达的控制分 组所要预定的突发传输时间，n e w b u r s t 2 是假设的未来的某个突发所要占用的传 输时间。 如果波长选择策略选择地做为n e w b u r s t l 的输出波长，则将来的n e w b u r s t 2 就会因为所有波长上都无合适的空隙雨被丢弃掉。如果选择九1 或者尬做为 n e w b u r s t l 的输出波长，则将来n e w b u r s t 2 可以选择波长地上的空隙进行传输。 由此可见，不同的波长选择策略对突发的冲突影响是不一样的，如何最大程度的 避免未来的突发冲突是调度算法的关键所在。 2 2 2 已有的调度算法 到目前为止已有不少学者提出了众多的o b s 网络中的数据信道调度算法，如 h o r i z o n 算法，l a u c 算法，l a u c v f 算法，m i n s v 算澍1 7 1 等，这些算法基本 上可以分为两类：带空隙填充和不带空隙填充。下面重点介绍两种最为典型的调 度算法，分别为l a u c 算法和l a u c v f 算法。 o b s 网络调度算法及o b s 网络特性剥t c p 性能的影响 一l a u c 算法【9 】 l a u c ( l a t e s t a v a i l a b l eu n u s e dc h a n n e l ) ，即最近可用未调度信道算法。在该 算法中，每个核心节点只记录每个波长信道上的最近到达的突发的离开时刻，即 从该时刻起的时间内该波长信道开始空闲，该时刻称为“最近未调度时刻”。由 于到达核心节点的突发的偏置时间各不相同，控制分组的到达顺序不一定与相应 的突发的到达顺序一致，l a u c 算法的思想是通过为每个到达的突发选择最近的 空闲数据信道以使调度后生成的空隙最小。假设一个持续时间为上的突发在t 时 刻到达某核心节点，信道调度器首先寻找在r 时刻未安排使用的波长信道。如果 有多个这样的可用信道，则选择最近可使用的信道，即最近末调度时刻和t 之间 间隙最小的信道。然后将该信道的最近未调度时刻更新为t + l 。 例如，在图2 3 中，假设突发预定在时刻r 到达核心节点，突发的长度为，一 ，假设该突发预定的输出链路上有四个波长，从图中可以看出，只有九1 和心 波长的最近未调度时刻在突发的到达时刻r 之前，由于九1 的最近未调度时刻比九2 更接近突发的到达时刻，因此，按照l a u c 算法，将选择九1 作为突发的输出波 长。 l a u c 算法的主要优点是只考虑每个信道的最近未调度时刻，核心节点需要 记录的信息量非常少，因此调度器寻找合适波长的时间非常短，且该算法实现简 单。在对计算时间要求十分苛刻的环境下，该优点显得十分重要。但该算法存在 一个严重的的缺点，即算法的信道利用率非常低，原因在于各波长上突发之间的 时间空隙都被浪费掉了。 豳豳黼瀚豳豳圈 裁麓瑷嘲黼露舞蹒蹬鞠 隧黼i l _ _ - _ o i 瞄黧嗣 t r e n t 嚣一 二l a u c v f 算法【l o 】 图2 3l a u c 算法示例 第二章波长转换器数目受限情况下的o b s 调度算法 为提高信道利用率，可以考虑将每个波长信道上突发之问的空隙也利用上， 这就是l a u c v f 算法较l a u c 算法的改进之处。当类发预定的输出链路上有多 个波长具备合适的空隙时，l a u c v f 算法选择突发的预定到达时刻与空隙的开 始时刻之间距离最近的那个波长信道，这样做的目的是为了使空隙尽可能的不被 浪费，从而使信道利用率得到提高。 鼷震蕊熏嘲：1 麟瀚徽i t l l 新突发 f - 浚戮戮灞黼图蓊缀熏阙 t 2i 隧燃渤粼燃激糕燃图蕊懑蕊隧圈 隧：! 匿嘲赫黧燃尉剿 竺 - 图2 4l a u c v f 算法示例 例如在图2 4 中，突发预定到达时刻为t ，该突发的输出链路中有5 个数据 信道，其中九1 、地、m 波长上都有可以容纳该突发的空隙，而九3 和x 5 波长则因 为在突发的预定传输时间内有别的突发占用该波长而不能被新突发使用。因为x 2 波长中的空隙开始时刻离新突发的到达时刻间隔最小，即t t 2 t t l s ，用b = ( e 厂) 来表示一个预定传输时刻为，结束时刻为厂的突发。 当有多个波长上都有合适的空隙可以承载该突发时，存在多种进行选择空隙的策 略。在空隙五处插入突发后，会造成两个新的空隙s v ( s ，r ) ，e v 何p ，) ，其中s v 表示s t a r t i n gv o i d ，即在原空隙的首端造成的新的空隙，e v 表示e n d i n gv o i d ，即 在原空隙的尾端造成的新的空隙。对于l a u c - v f 算法，其“选择最近可获得的 4 o b s 网络调度算法及o b s 网络特性对t c p 性能的影响 未使用的波长信道来最小化空隙”的策略，即是在所有合适的空隙中寻找使s v 达到最小的波长信道，同样的策略还包括m i n s v 算法。c h u n m i n gq i a o 还提出并 比较了另外几种调度算法w r l m i n - e v ，m a x s v , m a x e v ，这些算法的思想是在所 有合适的空隙中寻找使s v 或者e v 最大或最小的那个空隙，其仿真结果表明 m i n s v 和m i n - e v 的性能要优于m a x s v 及m a x e v ，m i n e v 性能比m i n s v 性 能略有下降，其原因在于每个空隙的首端比尾端更容易因随着时间的进行而过期。 多数的调度算法都没有考虑核心节点中波长转换器个数的限制问题。文章i i 中，作者假定只要存在有空闲的波长信道，则突发一定不会被丢弃。因此其潜在 的假设是波长转换器数目不受限制。该文的主要创新在于作者提出将所有波长上 的v o i di n t e r v a l 用一种平衡树的结构来表示，从而算法的执行时间比l a u c v f 算法要大大降低。文章i l8 】中，作者的目标是比较在达到与s p c 结构相同的丢包率 的情况下，其提出的s p n 、s p l 结构能够节省多少的t o w c 。所以该文可以称为 是在t o w c 数目受限的情况下来研究丢包率问题的，但该文的调度算法采用的是 随机选择一空闲波长的方法，因此其丢包率性能并未达到最优。 结合文献1 7 】 1 8 】中的有益思想，我们对现有的调度算法做了改进，提出了 种新的o b s 调度算法，即m i n s v e v 算法，该算法区别于别的调度算法的地方在 于：( 1 ) 考虑到核心节点中的波长转换器也是一种稀缺资源，因此当突发能在原 波长上进行传输时，就不再进行波长转换而直接选择原波长。( 2 ) 对于必须进行 波长转换的突发，再按照m i n s v e v 的原则选择合适的波长。 假设突发到达核心节点时所在的波长为丑，该突发的预定传输时间为b = ( e ，) ，用 ，p ，) 来表示空隙五。空闲波长的选择算法如下： 1 ) 如果突发能够在输出光纤中的波长七上传输，即在输出波长 上 有一空隙能容纳该突发。则不必经过波长转换，选择 作为输出 波长。 2 )如果该突发的预定传输时间在输出波长丑上与别的突发有冲突， 即在输出波长 ，上没有能容纳该突发的空隙，则要查询是否有可 用的波长转换器，如果没有可用的波长转换器，则丢弃该突发，如 果有多个可用的波长转换器，则按照波长转换器的选择算法( 下文 介绍) 选择一个合适的波长转换器。然后查询其它波长，寻找每个 波长上是否有满足s j ， f e j 的空隙，如果存在多个满足该条件 的空隙( 即存在多个有这样的空隙的波长，因为每个满足条件的空 隙对应于一个波长，一个波长上最多只有一个满足该条件的空隙) ， 则选择能使m i n ( ，一s j ，e j 力值达到最小的那个波长。 例如，在图2 7 中，假设新到达的突发( r ，d 的输入波长为m ，其输出光纤中 的波长m 上有一个已经预定好的突发与其在时间域上冲突，因此该新到达的突发 第二章波长转换器数目受限情；，| ! - 下的o b s 调度算法 需要进行波长转换，在输出波长x 1 、九2 及x 3 上都有合适的空隙能容纳该新突发， 如果按照l a u c - v f 算法，将选择波长九3 作为输出波长，但按照本算法，如果有 可用的波长转换器的话，最后将选择九2 作为输出波长。 麟豳圜圈豳 豳露翻豳濯函 强黼鞲 隧豳圈麟瀛劁躐黼麟 竣麟瀚黼黝 t r e l l t z = = - 。 图2 7m i n s v e v 算法示例 m i n s v e v 算法中所用到的波长转换器的选择算法描述如下： 每个波长转换器都记录所有已经预定使用本波长转换器的突发，预定使用同 一个波长转换器的两个相邻的突发之间也有空隙，一个波长转换器能否被使用取 决于此波长转换器是否在突发预定的传输时间内空闲，即是否有合适的空隙。仍 用b = ( 力表示需要波长转换的突发的预定传输时刻，用 ，p ) 来表示波长转换 器上适合承载该突发的空隙。当有多个波长转换器上都有可用的空隙时，仍按照 使m i n ( r s ，e j ，) 值最小的策略来确定波长转换器。 m i n s v e v 调度算法的仿真实现及性能分析将在下一章中进行。 第三章o b s 仿真平台实现 第三章o b s 仿真平台实现 本章首先简要介绍网络仿真软件o p n e t ，然后介绍o b s 仿真平台的实现过 程，最后分析比较了m i n s v e v 调度算法的性能。 3 1 网络仿真技术与o p n e t 仿真工具简介 网络仿真是一种利用数学建模和统计分析的方法模拟网络行为，从而获取特 定的网络特性参数的技术。在网络规模较大、网元类型繁多、网络拓扑复杂的情 况下，以经验为主的设计方法很难达到设计的目标。一方面，不可能在设计阶段 开展与拟建网络规模可比的网络试验来获得设计所需的依据；另一方面，数学计 算和估算方法对于大型复杂网络的应用往往是非常困难的，得到的结果的可信性 也是比较低的。在这种情况下，网络仿真成为了协议机制分析、网络性能分析与 规划的重要手段。它为分析与评价提供客观、可靠的定量依据，提高了设计的客 观性和设计结果的可靠性。 o p n e tm o d e l e r 是o p n e t 公司开发的一套集开发和应用为一体的通信系统仿 真软件，它采用面向对象的建模方法和图形化的编辑方式，支持在网络各个层次 的设备、链路和协议的精确建模，并提供了丰富的外界开发接口。 在仿真驱动机制上，o p n e t m o d e l e r 采用了离散事件驱动( d i s c r e t e e v e n t d r i v e n ) 的模拟机制，所谓“事件”是指网络状态的变化，也就是说，只有网络状 态发生变化时，模拟机才工作，否则不执行任何模拟计算。一个事件的发生会触 发一系列的特定类型的、特定时刻上的事件，从而推动仿真系统中时间的流逝。 与时间驱动相比，离散事件驱动的模拟机计算效率得到很大提高。 在建模机制上，o p n e t m o d e l e r 以包为基本单位模拟实际物理网络中数据的流 动，包括在网络设备间的流动和网络设备内部的处理过程、实际网络协议中的组 包和拆包的过程。可以生成、编辑任何标准的或自定义的包格式，并且利用调试 功能，在模拟过程中察看任何特定的包的包头( h e a d e r ) 、净荷( p a y l o a d ) 等内 容，从而使得仿真过程清晰明了，易于控制。 在建模方式上，o p n e t m o d e l e r 采用层次化建模结构，分网络( n e t w o r k ) 、 节点( n o d e ) 和进程( p r o c e s s ) 三个层次建模，其中最底层为进程模型，它以有 限状态机( f s m ，f i n i t es t a t em a c h i n e ) 来描述模块的工作过程，实现模块的功能， 对中断进行响应及设定；其次为节点模型，模拟节点对数据包的处理过程，由多 个模块的组合实现整个节点的功能，各个模块的功能和接1 ：3 需要详细的定义。最 上层为网络模型，体现闷络拓扑及流量设定。 o p n e tm o d e l e r 具有丰富的统计量收集和分析功能，可以直接收集常用的各个 o b s 网络调度算法及o b s 网络特性对t c p 。i i i i 的影响 网络层次的性能统计参数，并有多种统计参数的采集和处理方法，还可以通过底 层列络模型编程，收集特殊的j 叫络参数。o p n e t 还具有丰富的图表显示和编辑功 能、模拟错误提示和告警功能，能够方便地编制和输出仿真报告。 3 2o b s 仿真平台构建 本仿真平台是为了分析o b s 网络中调度算法m i n s v e v 的性能面搭建的，该 算法是在o b s 网络中的核心节点c o r e 中实现的，为模拟突发在核心节点中的冲 突情况，本网络采用两个源节点( 边缘节点) s r c l ，s r c 2 ，这两个源节点独立的 按照服从某种分布的随机时间间隔产生突发。链路默认为w d m 链路，其上的波 长数由i n i t 节点( 初始化节点) 中的参数设定。网络拓扑如图3 1 所示。 3 2 1 初始化节点 中。 图3 1 仿真网络拓扑结构 图3 2 初始化节点结构图 初始化节点功能结构比较简单，其功能主要包括： 1 在仿真开始阶段自动发现网络拓扑，并将拓扑信息存入全局变量二维数组 2 识别网络中核心节点及边缘节点，并为这些节点分配网络地址。 第三章o b s 仿真平台实现9 3 有关全局变量的初始化动作。 为统计网络稳定运行时的丢包率，在进程模型中设嚣了一个自中断，即从仿 真系统运行一段时间后才开始统计丢包，并在系统结束前段时间终止统计。 初始化节点中可配置的属性有：s p n 波长转换器共享方式下的核心节点中波长 转换器的个数；光纤中的波长数。 3 2 2 边缘节点 图3 3 边缘节点结构图 边缘节点负责产生o b s 网络业务源。为方便起见，边缘节点只产生控制分组 突发的信息，如长度、目的地址、所在波长等，都包含在控制分组中，因此在该 环境下控制分组可以用来代替突发，因此该节点中可省去突发的汇聚过程。 边缘节点的进程模型主要包括两个阶段，一个是初始化阶段，进程根据仿真 环境所设置的一些参数来对要产生的控制分组进行配置；第二个阶段是控制分组 的产生阶段，根据仿真环境所设置的控制分组之间的产生间隔分布函数来设置分 组的产生中断。当仿真结束时，进程转为“s t o p 状态。 该节点中可配置的属性主要包括：突发的长度分布函数；控制分组之间的时 间间隔分布函数；控制分组的格式；偏置时间。 2 0 o b s 网络调度算法及o b s 网络特性剥t c p 性能的影响 3 2 3 核心节点 图3 4 核心节点结构图 核心节点是本仿真平台中最关键的节点，它负责执行o b s 网络的调度算法。 在进程模型的初始化阶段，利用初始化节点提供的网络拓扑信息，调用d i j k s t r a 算 法在核心节点中建立路由表。虽然本仿真平台的拓扑比较简单，路由算法在本拓 扑中不是十分重要，但该核心节点中的进程模型支持扩展的网络拓扑，在网络拓 扑改变的情况下不必修改进程模型。初始化阶段的动作还包括每个波长及每个波 长转换器上a v l 树的初始化。在进程模型进入控制分组的处理阶段后，每个控制分 组的到达都引起进程的一个中断，该进程根据控制分组的信息来对突发进行相应 的处理。 核心节点中可配置的属性包括：控制分组在核心节点中的处理时延；信道传 输带宽等。 3 2 4 目的节点 图3 5 目的节点结构图 第三章o b s 仿真平台实现 目的节点主要功能统计成功接收到的突发数目，并销毁接收到的控制分组以释 放内存。 3 2 5 控制分组的格式 图3 6 控制分组格式 在o p n e t 的包编辑器里可以设置突发控制分组的格式，控制分组包