Torus交换结构中对多优先级业务交换性能的研究

论文摘要

随着互联网络的应用逐步深入人们工作和生活,各类基于网络的服务发展迅速。这对IP核心网络中的路由器提出了更高的要求:一方面要求路由器具备大容量数据交换能力;另一方面,各种不同的业务（如个人、企业级的不同应用）对服务质量有着不同的需求,要求路由器能进行区分服务。Torus多维交换结构是一种灵活的、可扩展的大容量交换结构,是对新一代大容量核心路由器—T比特路由器的交换结构的研究方向之一。在传统的交换结构研究领域,对多优先等级业务的区分服务主要依赖交换结构中的优先资源调度。由于Torus交换结构的特殊性,内部路由算法在系统的交换性能（吞吐量和时延）上起着决定性作用。本文主要研究了Torus交换结构中支持多优先等级业务的内部路由算法及其对交换性能的影响。文中提出了优先象限路由（PQR,Priority Quadrant Routing）算法。它是一种在Torus交换结构中支持多优先等级业务的无死锁的内部路由算法,能支持对时延有不同要求的多种业务。在n维的Torus交换结构中,PQR算法可以支持n+1个不同优先等级的业务。算法的核心思想是根据分组的源目节点对的坐标,将n维Torus交换网络分成n+1个不同优先等级的象限,对不同的业务根据其优先等级进行区分路由。算法中规定高优先等级业务（实时业务）只能在最短路径上路由,而低优先等级业务（准实时业务和非实时业务）则可以绕开热点资源,在较长路径上路由到达目的节点。PQR算法能保证实时业务的短时延要求。同时,由于业务可以分散到非最短路径上,提高了交换结构的吞吐量。同时,为了保证在不同业务模式（Traffic Pattern）下交换结构的吞吐量,文中还提出了业务均衡的优先象限路由（Priority Quadrant Routing with Load Balance,PQR-LB）算法。该算法的核心思想是,可以根据当前的网络负载状态对较低优先等级的业务进行自适应路由,使业务路由到负载相对较低的链路上。该算法相比于PQR算法,在不均衡的业务模式下也能达到较高的吞吐量,并保证实时业务的短时延。文章的结构如下。第一章介绍了T比特路由器和Torus交换结构,说明了虫孔路由交换方式和虚通道流控制方式,以及多虚网络的概念。第二章分析了在Torus交换结构模型下的内部路由和路由死锁问题。第三章中提出PQR算法的核心思想和流程。描述了PQR算法所支持的多优先级业务模型,说明了优先象限的划分方法,并给出了PQR算法的选路约束条件和路由方程,以及PQR的无死锁证明。根据路由方程,说明了不同优先级业务的区分路由和PQR算法的流程。第四章中提出了PQR-LB算法。分析了不均衡的业务模式对Torus的负载和交换性能的影响,提出了根据当前业务负载进行自适应选路的PQR-LB算法,并说明了算法对阻塞业务的处理以及流程;说明了PQR-LB算法所采用的两级调度机制,并给出了对多优先等级业务的区分调度策略。第五章对两种算法的仿真数据进行了分析。与现有算法进行了比较,分析了它们对系统的吞吐量、时延以及业务均衡的影响,分析了不同优先等级业务在不同算法下的吞吐量、时延及均衡性。在第2节给出了搭建的仿真平台的结构和模块。第六章对全文进行了总结。

论文目录

• 中文摘要
• Abstract
• 第一章 TORUS 交换结构概述
• 1.1 T 比特路由器与多维交换结构
• 1.2 多维交换结构的框架结构
• 1.3 可实现的多维交换结构－多虚网络TORUS 框架
• 第二章 TORUS 交换结构中的路由算法
• 2.1 TORUS 交换中的路由死锁问题
• 2.2 TORUS 结构中的路由
• 第三章 TORUS 交换结构中支持多优先等级业务的路由算法
• 3.1 研究背景
• 3.1.1 多优先等级业务模型
• 3.2 优先象限路由PQR（PRIORITY QUANDRANT ROUTING, PQR）算法
• 3.2.1 PQR 算法中的基本定义
• 3.2.2 PQR 算法中的象限划分与象限优先级
• 3.3 PQR 算法的路由策略
• 3.4 PQR 的虚通道与死锁解决
• 3.5 PQR 对多级业务的的区分路由
• 3.6 算法实现流程
• 3.7 PQR 算法的性能
• 第四章 TORUS 交换结构中支持多优先级业务的负载均衡路由算法
• 4.1 问题的提出
• 4.2 优先象限路由（PQR-LB）算法的策略
• 4.2.1 交换结构的链路负载状态记录
• 4.2.2 PQR-LB 算法中的选路条件与阻塞处理
• 4.2.3 PQR-LB 算法流程
• 4.3 调度算法对优先业务的支持
• 4.3.1 调度模型描述
• 4.3.2 支持多优先级业务的两级调度模型
• 4.4 PQR-LB 的业务均衡性
• 第五章 数据分析与仿真模型
• 5.1 仿真方案
• 5.2 数据分析
• 5.2.1 仿真数据定义
• 5.2.2 PQR 算法中对多优先等级业务的支持的分析
• 5.2.3 PQR-LB 算法的负载平衡分析
• 5.3 仿真模型
• 5.3.1 拓扑结构
• 5.3.2 交换节点
• 5.3.3 业务源模型
• 5.3.4 模块设计
• 第六章 全文总结
• 致谢
• 参考文献
• 本文作者在攻读硕士学位期间取得的成果
• 个人简历