【作者】 马祥杰；

【导师】 兰巨龙；

【作者基本信息】 解放军信息工程大学 ， 通信与信息系统， 2008， 博士

【摘要】 随着信息网络朝着传输高速化和接入宽带化方向演进,路由交换设备交换结构的扩展能力受到严峻挑战。多级多平面(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调度算法满足业务带宽保证调度需求。更多还原

【Abstract】 With the evolution towards high-speed transportation as well as access network, the scalability of network routers is challenged rigorously. The novel multiple plane and multiple stage (MPMS) packet switching technology can integrate multiple small-scale switching units into a large switching network, which is able to break the bottleneck of single switching fabric and increase the scalability of network routers. Therefore, the MPMS switching technology is causing more and more attention from academic and industry domains. The MPMS switching technology, however, is only at its initial research phase for lacking of theoretic basis and mathematics models. Many important technical issues of MPMS have not been studied deeply, which holds back its application in practical network routers seriously.Combined with the research work of the National Basic Research Program of China (973 program) of“the integrated network architecture model and the switching and routing theory and technology”, regarding to the scalability requirement of router switching fabric, a universe architecture and mathematics model of the MPMS are proposed, and the analysis methods and performance evaluation techniques are built up, which are based the functional units and linking structure. Two novel MPMS switching system with different buffering methods are proposed and studied evaluated. To meet the bandwidth sensitive services in Internet, a bandwidth guaranteed scheduling technique is proposed. The main research work of this paper includes:1. The universal architecture and the directed graph model (DGM) are proposed. The universal architecture and organization method are proposed and analyzed based on the functional unit subsets and linking connection subsets. With the directed graph theory, the DGM model of the MPMS switching system is proposed, and the characters including neighboring relations and port reachability are defined, and the model graph is also provided. Based on the defined model character, the vertex competing and balancing property and the switching path are defined. The performance expansive ratio is defined to describe the scalability accurately.2. A novel input/output buffered Clos-type MPMS (MSMC&MPMS) packet switching system is studied, and its topological structure is proposed, and then its DGM model is built up. The topological characters, including graph complexity, neighboring connectivity, and port reachability, are studied, and then the topological measure graph is given of the MSMC&MPMS system. It is shown that, demultiplexors and input switching units belong to balancing vertex, while middle switching units, output switching units and multiplexors belong to competing vertex in the MSMC&MPMS system. The switching path count between any demultiplexor and multiplexor pair is equal to P×m, where P is the switching plane number and m is the middle switching unit number. The number of switching ports can be expanded to PN times, where PN refers to the maximum port count of single switching fabric, and the rate of switching ports to P times, and the switching capacity to P×PN times, while the fabric structure is only linearly increased with the switching plane numbers.3. A novel central stage buffered Clos-type MPMS (CBC&MPMS) packet switching system is studied. Its topological structure is proposed, and then its DGM model is built up. The topological characters, including graph complexity, neighboring connectivity, and port reachability, are studied, and then the topological measure graph is given of the CBC&MPMS system. Demultiplexors, input switching units and middle switching units I belong to balancing vertex, while middle switching units II, output switching units and multiplexors belong to competing vertex. The switching path count between any demultiplexor and multiplexor is P×m×k, k times the MSMC&MPMS system. It has the same expansive parameters with that of MSMC&MPMS, but its fabric complexity is 33.3% higher than that of MSMC&MPMS.4. MSMC&MPMS is proved to be fabric non-blocking under condition of P×m×k≥N or P×m≥n, where k is input/output switching unit count, N is system port count and n is input/ output switching port count, while CBC&MPMS is fabric non-blocking with parameters satisfying P×m×k2≥N or P×k×m≥n, needing much less input/output switching units. Meanwhile, MSMC&MPMS is proved to emulate an OQ switch with speedup factor satisfying S≥2/P or S≥N/(P×m×k), while CBC&MPMS can emulate an OQ switch if S≥1/P and m≥N/(P×k), whose TSP is only 1/2P times that of MSMC&MPMS.5. A novel bandwidth guaranteed scheduling technique of the MPMS switching system is provided. The scheduling model of demultiplexors, multiplexors and input/output /middle switching units are provided, and a bandwidth guaranteed concurrent round-robin dispatching algorithm (called BG-CRRD) is also designed. Simulation results show that, the algorithm can achieve 100% throughput under Bernoulli uniform traffic, and the optimal delay can be achieved when the switching plane count is three. Under nonuniform traffic, it can gain a throughput much higher than CRRD, and can achive a throghput of 92% under worst case, which is 29% higher than that of the CRRD algorithm. Under overloaded traffic, it can allocate output-link bandwidth among Cell flows according to their reserved bandwidth, and therefore can satisfy the bandwidth requirement of service folw and share bandwidth fairly. So the BG-CRRD scheduling algorithm can satisfy the scheduling demands of different bandwidth sensitive services.更多还原