高速多级分组交换网络若干关键技术的研究

论文摘要

随着Internet业务爆炸式增长和光宽带传输技术的迅猛发展,网络结点逐渐成为网络宽带化的瓶颈。路由器(交换机)的内部交换网络作为网络结点的核心部件,是目前高性能宽带信息网络研究的热点之一。单Crossbar交换网络是目前核心路由器的主流交换结构,其研究成果十分丰富,但是,由于受工程实现的限制(机架供电、芯片体积等),单Crossbar交换网络容量无法做到很大。采用多级交换结构是构建大容量分组交换网络的常用途径。直接连接网络和间接连接网络是空分多级交换网络的两种主要拓扑类型。直接连接网络虽然具有良好的可扩展性,但是网络性能难以控制,只是在大容量分组交换网络研究初期得到应用;间接连接网络是目前多级分组交换网络研究的重点。目前对多级间接连接网络(如三级Clos网络,并行分组交换和两级交换网络等)的研究是对单Crossbar交换网络研究的简单推广,从本质上说是一种集中式控制方式,这种方式会带来调度算法实现困难,交换网络性能难以控制和无法充分发挥多级交换网络拓扑优势等问题,本文针对这些问题对多级高速间接连接分组交换网络的若干关键技术进行了研究,主要工作和贡献如下:1.提出了多级间接分组交换网络分布式调度思想。按照交换网络各级交换单元在网络中的地位不同,将它们分为负载均匀级交换单元和调度级交换单元,分别通过负载均衡策略和交换单元内部调度策略来实现交换控制。这样将多级间接连接网络的调度问题分解为负载均衡和交换单元内部的调度两个子问题来处理,带来了以下优点:(1)实现了调度算法的完全分布式,便于多机架实现。由于在分布式调度思想中,通过负载均衡级来协调调度级交换单元的业务负载,不需要在交换网络的各级和级内交换单元间进行控制信息的交换,因此,这种调度算法是完全分布式的;(2)调度算法具有良好的继承性。在分布式调度多级间接连接分组交换网络中,调度级交换单元的调度就是单Crossbar内部的调度,可以完全借鉴现有单Crossbar交换网络的研究成果;(3)算法实现简单,算法性能便于控制和分析。2.分析了三级Clos网络分布式调度保证性能的资源需求。研究表明在三级Clos网络分布式调度中,保证性能的网络资源需求是Clos网络保证性能的最少资源。信元乱序是三级Clos网络分布式调度采用定长信元机制面临的主要问题之一,本文提出了一种可以实现信元保序的三级Clos网络分布式调度调度算法——LDVSA算法,通过分析表明该算法不仅具有较好的性能同时可以实现分组信元的完全保序。3.本文在一种实现简单的分布式调度算法——RRBSA算法下,对三级Clos网络分布式调度的交换机制进行了研究。研究表明,定长信元交换机制和变长分组交换机制在三级Clos网络分布式调度中都具有一定的局限性,为此,本文提出了一种结合定长信元和变长分组交换机制优势的混合交换机制。这种交换机制以变长分组为单位实现负载均衡,解决了信元乱序问题;通过采用一种新型的令牌机制实现了变长分组负载分配的公平性;在Clos网络的后两级采用定长信元交换机制,获得了良好的业务适应性,研究表明混合交换机制是一种适合三级Clos网络分布式调度的交换机制。4.对三级Clos网络的故障进行了分析,提出了三级Clos网络分布式调度的故障模型,通过将网络故障归结为对输入级不同队列的影响,提出了三级Clos网络分布式调度的容错算法。对算法的容错方式、容错能力进行了分析,研究表明,该算法具有较好的容错能力。5.将分布式调度思想应用到目前研究较多的两种多级交换网络结构——并行分组交换(PPS)和两级交换网络中,克服了这两种交换网络现有研究的不足。在两级交换网络中实现了在分布式调度思想下和三级Clos网络的统一,使得三级Clos网络分布式调度算法得到进一步简化。利用本文的研究成果构建超大(100Tb/s以上)容量分组交换网络,可以在现有成熟技术下实现最大容量为655.36Tb/s的交换网络,远远高于现有研究成果的水平。6.提出了一种具有良好可扩展性的交换网络拓扑结构——MR网络。该网络通过在交换网络中间级引入具有直接连接网络特点的环形网络和巧妙的级间连接关系,克服了传统间接连接网络可扩展性的不足。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 高速、大容量路由器发展的必要性
• 1.1.2 路由器内部交换网络的地位和作用
• 1.1.3 路由器内部交换网络的发展历史
• 1.1.4 高速、大容量分组交换网络主要研究问题
• 1.2 单Crossbar 交换网络研究
• 1.2.1 单Crossbar 交换网络结构发展
• 1.2.2 输入排队交换网络调度机制的研究
• 1.2.3 输入排队交换网络交换机制的研究
• 1.3 本文主要研究内容和成果
• 第二章 三级Clos 网络分布式调度算法研究
• 2.1 三级Clos 网络研究历史介绍
• 2.2 分组交换三级Clos 网络研究现状分析
• 2.2.1 概述
• 2.2.2 MSM 结构三级Clos 网络调度算法分析
• 2.2.3 SSS 结构三级Clos 网络调度算法分析
• 2.3 三级Clos 网络分布式调度思想的提出和特性分析
• 2.3.1 概述
• 2.3.2 多级交换网络分布式调度思想的提出
• 2.3.3 三级Clos 网络分布式调度的基本特性
• 2.4 具有信元保序能力的三级Clos 网络分布式调度算法
• 2.4.1 概述
• 2.4.2 输入级完全负载均匀分配算法（FLBDA）
• 2.4.3 中间级调度算法
• 2.4.4 输出级调度算法
• 2.4.5 LDVSA 调度算法性能分析
• 2.5 本章小结
• 第三章 三级Clos 网络分布式调度交换机制研究
• 3.1 基于变长分组的三级Clos 网络分布式调度性能研究
• 3.1.1 概述
• 3.1.2 变长分组交换三级Clos 网络分布式调度特性分析
• 3.2 RRBSA 调度算法下两种不同交换机制性能研究
• 3.2.1 算法描述
• 3.2.2 算法性能分析
• 3.3 混合交换机制三级Clos 网络分布式调度算法
• 3.3.1 概述
• 3.3.2 输入级业务分配算法
• 3.3.3 中间级和输出级调度算法
• 3.3.4 算法性能仿真分析
• 3.4 本章小结
• 第四章 三级Clos 网络分布式调度容错机制研究
• 4.1 引言
• 4.2 三级 Clos 网络故障模型
• 4.3 三级Clos 网络分布式容错调度算法
• 4.3.1 概述
• 4.3.2 网络故障时输入容错负载分配算法
• 4.3.3 算法性能分析
• 4.4 本章小结
• 第五章 典型多级间接连接网络分布式调度研究
• 5.1 引言
• 5.2 并行分组交换网络分布式调度算法研究
• 5.2.1 现有PPS 研究成果分析
• 5.2.2 PPS 网络分布式调度算法研究
• 5.2.3 小结
• 5.3 两级交换网络中分布式调度算法研究
• 5.3.1 概述
• 5.3.2 两级交换网络分布式调度算法研究
• 5.3.3 小结
• 5.4 利用三级Clos 网络分布式调度构建超大容量分组交换网络
• 5.4.1 概述
• 5.4.2 现有构架超大容量分组交换网络方案分析
• 5.4.3 利用三级Clos 网络分布式调度构建超大容量分组交换网络
• 5.5 本章小结
• 第六章 基于环的大容量可扩展分组交换网络
• 6.1 传统交换网络拓扑分析
• 6.1.1 直接连接网络分析
• 6.1.2 间接连接网络分析
• 6.2 MR 网络拓扑结构和基本路由算法
• 6.2.1 MR 网络拓扑结构
• 6.2.2 MR 网络基本路由算法
• 6.3 MR 网络中间级环网络结点容量和可扩展性分析
• 6.3.1 MR 网络中间级环网络结点容量分析
• 6.3.2 MR 网络可扩展性能分析
• 6.4 MR 网络可扩展性能仿真分析
• 6.6 本章小结
• 第七章 总结和展望
• 7.1 本文主要工作和结论
• 7.2 有待进一步研究的问题
• 致谢
• 参考文献
• 攻读博士学位期间完成的论文和工作