多级多平面分组交换技术研究
Study on the Multiple-plane and Multiple-stage Packet Switching Technology

随着信息网络朝着传输高速化和接入宽带化方向演进,路由交换设备交换结构的扩展能力受到严峻挑战.多级多平面(MPMS)分组交换技术能够将多个小规模交换单元汇聚成大规模交换网络,从而突破单一交换单元的容量限制,极大地提高了路由交换设备的可扩展性.因此,多级多平面分组交换技术得到了学术界和产业界的广泛重视.但是,由于缺乏理论基础和数学模型,多级多平面分组交换技术的研究目前尚处于起步阶段,很多重要的技术难题尚未解决,严重影响了实际应用.结合十一五国家973计划项目ǎ一体化网络体系结构模型及交换路由理论与技术ǐ的研究工作,针对路由交换设备对于交换技术的可扩展性需求,本文在深入分析功能实体和连接链路互连结构的基础上,提出了多级多平面分组交换系统的通用架构和数学模型,建立了多级多平面分组交换技术的模型分析方法和性能评估手段.在此基础上,提出两种缓存结构的多级多平面交换系统,并进行建模分析和性能评估.为了适应互联网中带宽敏感业务需求,提出一种多级多平面交换系统的带宽保证调度技术.本文的主要研究内容包括以下几个方面:1.研究了多级多平面分组交换系统的通用架构,提出了一种基于有向图的MPMS交换结构理论分析模型.根据MPMS中功能子集和链路子集提出了MPMS交换系统的通用架构,分析了系统级和平面级通用架构的组织方式和连通结构.运用有向图建模理论,提出了MPMS交换结构的有向图DGM模型,定义了DGM模型的相邻连通性和端口可达性等模型特征,并提出了MPMS的模型拓扑图.基于模型特征,定义了模型顶点的竞争均衡性和交换路径,描述了可以定量描述MPMS交换系统可扩展能力的性能扩展比等参量.2.提出了一种输入/输出级缓存Clos型MPMS(MSMC&MPMS)分组交换系统,给出了MSMC&MPMS交换系统的拓扑结构,建立了MSMC&MPMS交换系统的DGM模型.研究了MSMC&MPMS模型的拓扑图复杂性.相邻连通性和端口可达性等拓扑特征,提出了拓扑测度图.研究表明,MSMC&MPMS交换系统中的分路器和输入交换单元为均衡顶点,中间交换单元.输出交换单元和合路器为竞争顶点.MSMC&MPMS交换系统中分路器和合路器间的交换路径数SwPC值等于P*m(P为交换平面数,m为中间交换单元数);交换端口数量可以扩展至PN倍(PN为单一交换结构最大端口数),交换端口速率可以扩展至P倍,交换容量可以扩展至P*PN倍,交换结构复杂度仅随交换平面数呈线性提高.3.提出了一种中间级缓存Clos型MPMS(CBC&MPMS)分组交换系统.提出了CBC&MPMS交换系统的拓扑结构,建立了CBC&MPMS交换系统的DGM模型.研究了CBC&MPMS模型的拓扑图复杂性.相邻连通性和端口可达性等拓扑特征,提出了拓扑测度图.研究表明,CBC&MPMS交换系统中的分路器.输入交换单元以及第I类中间交换单元为均衡顶点,第II类中间交换单元.输出交换单元和合路器为竞争顶点;CBC&MPMS交换系统中分路器与合路器之间的交换路径数为P*m*k,是MSMC&MPMS交换系统的k倍;CBC&MPMS交换系统与MSMC&MPMS交换系统具有相同的交换端口数量.交换端口速率.交换容量扩展能力;但交换结构复杂度比MSMC&MPMS高出约33.3%.4.推导出MSMC&MPMS交换系统结构无阻塞需要的拓扑参数条件是P*m*k≥N或者P*m≥n(k为输入/输出交换单元数,N为交换系统端口数,n为输入/输出交换单元端口数);CBC&MPMS交换系统结构无阻塞需要的拓扑参数条件是P*m*k2≥N或者P*k*m≥n,需要更少的输入/输出交换单元即可实现交换结构无阻塞.推导出MSMC&MPMS模拟OQ交换结构所需的内部加速比S值约为S≥2/P或者S≥N/(P*m*k);CBC&MPMS交换结构模拟OQ交换结构需要的内部加速比S值为S≥1/P和拓扑参数条件为m≥N/(P*k),成本时空积TSP值仅为MSMC&MPMS交换系统的1/2P倍.5.提出了一种MPMS交换系统的带宽保证调度技术.分析了Cell分组流在MPMS交换系统中链路和路径的带宽分布特征,提出了MPMS交换系统中分路器.合路器.输入/中间/输出交换单元的调度模型,设计了一种MPMS交换系统的支持带宽保证并发轮转(BG-CRRD)调度算法.BG-CRRD算法在Bernoulli均匀流量时可以获得100%的吞吐率,交换平面数P值增加至3时收敛至最优平均时延性能;在非均匀流量时可以获得的吞吐率性能明显优于CRRD算法,极坏情况下可以获得的吞吐率高达92%,比CRRD算法吞吐率高29%;在过载流量时根据预留带宽在各分组流间分配输出链路带宽,从而保证业务流的带宽需求和带宽分配的公平性.因此BG-CRRD调度算法满足业务带宽保证调度需求.