基于令牌交换结构调度算法研究.pdf

独创性声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作
及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方
外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为
获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与
我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的
说明并表示谢意。

签名: 日期: 年月日


关于论文使用授权的说明
本学位论文作者完全了解电子科技大学有关保留、使用学位论文
的规定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘,
允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全
部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描
等复制手段保存、汇编学位论文。
(保密的学位论文在解密后应遵守此规定)

签名: 导师签名:
日期: 年月日
摘要
摘要
路由器是通信网络中的重要设备之一,随着通信网络业务量的增加,路由器
的转发能力和规模剧增。目前,电信级核心路由器、企业高端路由器等大型路由
设备主要由线路接口物理层芯片、网络处理器、流量管理器、交换单元四种芯片
组成,每种芯片具有各自的作用。例如:流量管理器完成信元缓存、流量整形、
拥塞避免等功能,交换单元完成将信元从输入端口交换到输出端口的功能。多个
交换单元以及输入输出端口模块以一定的拓扑结构和内部协议连接就构成了路由
器内部的交换网。
交换网的技术是路由器的核心技术之一,采用不同的配置时,交换网的规模
可以实现从几十 Gbit/s 扩展到几十 Tbit/s。随着容量的提高,业务的多样性,提高
交换网的调度效率,资源使用效率和服务质量的支持是进来网络研究的热点和难
点。现有的交换网调度算法在支持多业务特性和调度效率方面还有待改进。本文
主要贡献和创新在于,针对这两点在传统的令牌调度算法基础上设计了两项分布
式调度机制,基于令牌的流量状态调度机制(Credit-Based Traffic State scheduling
mechanism)CBTS 和,基于令牌的单组播调度(Credit-Based Unicast and Multicast
Scheduling mechanism)机制 CBUM。
本文首先介绍交换网的技术背景和研究现状,对现有调度算法和其存在改进
的方面进行介绍,然后详细描述改进的算法和其应用效果。然后以多级多平面
CLOS 交换网络为例,搭建了通用的 仿真平台,在其基础上实现这两种调
度算法。对于两种改进算法,和普通令牌调度算法采用相同的业务源模型,比较
验证算法在服务多优先级业务方面的可行性和有效性。
仿真表明两种算法在一定业务环境下可以达到预想的实验效果,对分布式令
牌调度算法的分组时延和多业务的支持有一定的改进,具有实用性。


关键词:交换结构,交换网,调度算法,分布式,令牌


I
ABSTRACT
ABSTRACT
High performance routers are essential equipments in munication
networks. With the increasesing of valume work services, the
forwarding capability and scale is surging. At present, the carrier-class core routers,
enterprise routers and other high-end large-scale routing equipment are mainly consisted
by the physical layer interface chips, network processors, traffic managers, and
switching modules. For example, traffic managers excute the functions of buffing data
cells, shaping traffic, avoiding congestion. The switching modules switch the cells from
the input ports to the output ports. The certain topology which interconnected by
switching modules, input and output modul