硕士论文-多级交换结构及其调度算法研究.pdf

电子科技大学
硕士学位论文
多级交换结构及其调度算法研究
姓名:雷雯
申请学位级别:硕士
专业:通信与信息系统
指导教师:许都
20060601
摘要交换网络处理的业务流量增长要求交换网络的容量需要不时地进行升级,单级交换机由于受芯片的管脚和实现复杂度的限制,无法应用于大规模可扩展交换机,因此,采用由多个交换单元构成的多级网络是目前常用的解决方案。另一方面,用于多级交换结构的传统调度算法往往忽略了输入业务的特性,如:不同业务的相对优先级、时延、时延抖动或不同的服务等级等特性,在支持可扩展性和满足各种业务特性方面,还有待改进。针对以上问题,本文的主要贡献和创新在于:通过对公司某交换芯片的研究,对腿禖峁棺龀隽烁慕簧杓屏艘砸滴裉匦晕5枷的两种调度算法:惴ê虲算法;搭建了通用的仿真模型实现两种算法,对其进行了多方面的仿真实验并对算法性能进行了分析和讨论。仿真表明,改进结构和两种调度算法能取得较好的性能。首先,本文从交换机的作用和地位,交换技术的基本理论,交换结构和调度算法在交换机中的作用几个角度出发介绍了本文的背景知识,并展望了交换网络的技术发展趋势。然后分析了分组交换结构从单级结构到多级结构的演进历程,分析当前大容量分组交换网络的现状,并研究讨论了用于单级结构和多级结构的不同调度算法。其次,本文对偷娜禖峁棺龀隽烁慕慕慕换唤峁鼓苤С分布式的“拉”式调度算法,具有更加灵活的可扩展性。再次,在改进结构基础上设计了两种调度算法和,两种算法均属于流调度算法,采用分布式的调度方式,与传统的用于多级结构的集中式两次匹配的调度算法有很大的区别,传统算法将输入端口的数据包“推”向交换结构的输出端口,而算法和算法是通过输出调度器将数据包从输入端口“拉”向输出端口。在中,输入输出之间采用异步交互控制信息的方式进行分布式的一次调度算法,仿真表明,它能充分考虑业务特性和输出带宽进行调度,在均匀负载的情况下能取得较高的吞吐率,降低数据包的平均时延,较好地适用于热点业务,同时能方便地支持负载均衡;通过令牌进行调度,输入级瓸—
关键词:多级交换,三级,算法,算法,业务特性采用时分复用的方式共享链路,它能降低工程实践的复杂度,并且也能在考虑业务特性基础上调度,能较好的支持不同的业务特性,对不同优先级业务表现出较好的性能,也能有效而简易地支持负载均衡。最后,为了考察基于改进腿禖峁沟牧街炙惴ǖ男阅埽颐谴建了基于这种交换结构的通用仿真模型,并在此基础上实现了上述两种算法,对它们做了多方面的仿真实验和仿真结果分析,对目前系统的不足提出了下一步的改进方向。电子科技大学硕士学位论文
,琩,,,.畁猻:,畉,,.·.篿,—籺,”琽,:.;珹甀皁—眘甋.
—,,,.甀..,
简略字表——基于令牌异步调度换唤峁异步传输模式基于令牌时分复用调度并发轮询分配算法解复用器密集波分复用最早时限优先先进先出队头阻塞内部连线阻塞内部连线冲突互联网协议输入排队迭代轮询匹配使用的迭代轮询匹配缓存一缓存一缓存多协议标签交换缓存一空分一缓存复用器狿猂
输出端冲突输出排队开放系统互连参考模型并行迭代匹配服务质量随机分配轮询算法分段重组串行线路接口协议空分一空分一空分时分复用虚拟输出队列加权公平排队加权轮询电子科技大学硕士学位论文猄
日期:确选望签名::.渺暌自拢日关于论文使用授权的说明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名:本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。C艿难宦畚脑诮饷芎笥ψ袷卮斯娑导师签名:
,人们对通信带宽的需求也渐渐提高,同时,对姆衲谌莺头裰柿恳蔡岢隽烁高的要求。随着光传输技术的发展和成熟应用,传输链路和传送节点己不再是限制骨干网发展的主要因素,而作为业务节点的交换机与路由器却成为制约网络性能的“瓶颈”【俊NA耸视ν缌髁亢痛浯淼脑龀に俣龋笕萘拷换患际趺媪着新的挑战,成为当前国内外研究的持续热点。下面,我们将详细介绍交换技术的发展和研究现状,为后续章节的进一步展开做好铺垫。分组交换技术是在计算机技术发展