Clos网络中变长分组交换及调度算法研究

Clos网络是多端口的路由器和交换机中经常采用的交换网络,其优点在于它是一个结构全对称的网络。比较了多级Clos网络分布式调度算法中定长分组和变长分组交换的特点;给出一种基于变长分组交换的MSM型三级Clos交换网络结构和相应的ACBS调度算法;消除了分组负载分配的不公平性。分析表明该调度算法优于传统算法,并通过仿真实验验证了算法的有效性。     

星载Clos网络的全分布式容错调度算法

针对星载交换结构受空间辐射影响造成的可靠性严重下降问题,该文提出了一种支持全分布式调度的三级Clos网络及其全分布式容错(Fully Distributed Fault Tolerant, FDFT)调度算法,以提高星载交换结构在交叉点故障下的容错能力。该Clos网络的中间级和输出级采用联合输入交叉点队列,以支持Clos网络和交换单元内部的全分布式调度。FDFT采用一种分布式故障检测算法获得交叉点故障信息。基于对交叉点故障影响范围的分析,FDFT在输入级采用一种容错信元分发算法,实现无故障路径的负载均衡。理论分析证明,当任一输入/输出级交换单元故障个数不超过(m-n)或所有中间级交换单元故障个数不超过(m-n)时,其中m, n分别为输入级交换单元输入、输出端口数,FDFT能够达到100%吞吐率。仿真结果进一步验证,故障随机发生情况下,FDFT能够抵抗比故障任意发生情况下更多的故障,且在不同的业务场景下具有良好的吞吐率和时延性能。     

分组交换网络调度算法概述

为了合理利用网络资源,提高网络吞吐率,降低通信时延,需要采取有效的调度算法实现输入端和输出端的匹配.基于VOQ的输入排队交换结构是当前分组交换网络最常用的结构.本文介绍了几种基于VOQ的调度算法:用于单级crossbar的PIM、iRRM和iSLIP算法,以及适用于三级Clos网络的RD和CDDR算法.对每种算法,介绍其基本原理和性能,以及与其他算法的区别.     

使用多级交换网络进行大容量光纤通道交换机设计

介绍了三级Clos网络拓扑,在此基础上设计了基于Clos网络的大容量光纤通道交换机体系结构.针对三级Clos网络存在的信元调度和路由分配问题,提出了一种新颖的采用流水线并行处理方式的双重匹配帧调度策略.该设计和策略对大容量光纤通道交换机的研制具有一定参考意义.     

一种基于全局调度的改进CLOS结构及其调度算法

现有的关于Clos交换结构的调度算法在关注调度性能的同时,逐渐忽略了其在硬件实现上的复杂度。该文根据一款星载交换芯片的设计实现,提出了一种改进型的Clos结构,且在此基础上设计了一种硬件实现简单且能实现极大匹配的调度算法。     

用于多级交换网络的一种高效自寻路技术

自寻路交换是多级交换网络中的一种常用技术,但它容易因冲突而形成网络内部阻塞.为减少连续冲突,进一步提升网络性能,基于三级交换网络前端采取“信元间插”策略,将分组的连续信元在时间轴上打散,保证业务被均匀地发送至网络中,从而大大减轻了网络内部阻塞;同时,通过在第一级交换单元中设置“逻辑指示器”,为不同的业务流合理地选取第二级交换单元,一定程度上保证了第二级的负载均衡.理论分析和仿真实验表明,与CRRD(Current Round-Robin Dispatching)等其他交换调度方式相比,新自寻路机制下的信元平均网络时延明显减小Clos网络,提出了一种新的高效自寻路机制.通过在     

LTE网络中多目标优化的动态负载均衡算法

小区间动态负载均衡算法的优劣对网络性能有很大的影响,现有算法大都顾此失彼,难以保证网络关键性能指标(如呼叫阻塞率等)达到最佳。为解决这个问题,该文将负载均衡问题建模为多目标优化问题,分别对不同服务质量要求用户建模其相应目标优化函数,对有服务质量要求用户的目标函数是负载均衡指示函数和网络平均负载函数的联合优化函数,而对没有服务质量要求用户(BE用户)的目标函数是所有BE用户吞吐量的总效用函数,并将小区可用资源数和用户服务质量要求作为约束条件。另外,考虑到在实际系统中运行的计算复杂度问题,提出一种复杂度较低的分布式负载均衡算法。包括资源调度策略,用户切换条件和呼叫接入控制。仿真结果表明,该文算法可达到较好的负载均衡效果,能有效降低有服务质量要求用户的呼叫阻塞率,提高网络资源利用率。     

面向稳定性和负载均衡的Ad hoc分簇算法

Ad hoc网络是一种移动设备通过无线连接的移动自组织网络。分簇算法被证明是管理自组织网络资源的有效方法。因此,一个更加稳定的分簇结构对整个网络的性能将会产生直接的影响。文章提出了一种面向稳定性和负载均衡的分簇算法SLCA（Stability-oriented and Load-balanced Clustering Algorithm）,这种算法通过改善节点度和在簇维护阶段引入蒙特卡洛思想的方法,提高了簇的稳定性和负载均衡。通过仿真,结果显示SLCA算法的性能相比NWBCA较优越。     

基于PF调度的多源多中继协作网络节点选择

针对多源多中继协作网络模型,提出一种公平的节点选择与用户调度方案。出于优化平均信道质量的思想,每个传输时隙,选择信道条件差异最大的两个用户同时进行传输信息。中继节点选择基于PF比例公平调度算法,能保证中继节点处的负载均衡。然后在中继端采用一种网络编码传输方案。最后,与其他2种调度方案相比较仿真系统的误码率性能。     

一种新的应用于光突发交换网络保证流量均衡的波长调度算法

在现有波长调度方法(LAUC_VF)的基础上,结合跳数优先级技术和动态资源分配技术,提出了一种新的可以提供流量均衡的波长调度算法(HP_JET)。通过仿真,证明这种波长调度算法在改善全网阻塞率以及均衡流量方面比原有的波长调度算法有更好的性能。     

On evil-twin routing in Clos networks

The evil twin randomized routing algorithm is successfully applied to three-stage Clos networks in packet-switching platforms. Here we show the essence of evil twin permutations and how to construct evil twin permutations. The concept of evil twin permutations is also generalized in this letter.     

A unifying approach to determine the necessary and sufficient conditions for nonblocking multicast 3-stage Clos networks

The 3-stage Clos network is the most-studied switching network. However, exact conditions on the strictly nonblocking multicast three-stage Clos network under various models are difficult to get, due to the messy detail and because each case employs a different argument. Hwang and Liaw (2000) made the latest attempt and pointed out errors in previous attempts. However, they made errors, too. In this paper, we propose a unifying approach to study those models systematically (which also applies to some wide-sense nonblocking (WSNB) networks). We also propose a new routing algorithm, and use the unifying approach to derive a necessary and sufficient condition for WSNB.     

A New Architecture for Nonblocking Optical Switching Networks

With the current technology, all-optical networks require nonblocking switch architectures for building optical cross-connects. The crossbar switch has been widely used for building an optical cross-connect due to its simple routing algorithm and short path setup time. It is known that the crossbar suffers from huge signal loss and crosstalk. The Clos network uses a crossbar as building block and reduces switch complexity, but it does not significantly reduce signal loss and crosstalk. Although the Spanke's network eliminates the crosstalk problem, it increases the number of switching elements required considerably (to 2N ² - 2N). In this paper, we propose a new architecture for building nonblocking optical switching networks that has much lower signal loss and crosstalk than the crossbar without increasing switch complexity. Using this architecture we can build non-squared nonblocking networks that can be used as building block for the Clos network. The resulting Clos network will then have not only lower signal loss and crosstalk but also a lower switch complexity.     

Matching algorithms for three-stage bufferless Clos network switches

Three-stage Clos network switches are an attractive solution for future broadband packet routers due to their modularity and scalability. Most three-stage Clos network switches assume either all modules are space switches without memory (bufferless), or employ shared memory modules in the first and third stages (buffered). The former is also referred to as the space-space-space (S/sup 3/) Clos network switch, while the latter is referred to as the memory-space-memory (MSM) Clos network switch. We provide a survey of recent literature concerning switching schemes in the S/sup 3/ Clos network switch. The switching problem in the S/sup 3/ Clos network switch can be divided into two major parts, namely port-to-port matching (scheduling) and route assignment between the first and third stages. Traditionally, researchers have proposed algorithms to solve these issues separately. Recently, a new class of switching algorithms, called matching algorithms for Clos (MAC), has been proposed to solve scheduling and route assignment simultaneously. We focus on the MAC schemes and show that the new class of algorithms can achieve high performance and maintain good scalability.     

Semi-rearrangeably nonblocking operation of Clos networks in themultirate environment

We study the semi-rearrangeably nonblocking (SRN) operation of asymmetrical three-stage Clos (1953) switching networks in the multirate environment. We develop a basic algorithm that balances the established connections among middle-stage switches by performing a small number of rearrangements per disconnection. For this algorithm, we first derive general conditions under which rearranging from a single middle-stage switch is sufficient to achieve SRN operation. In the most general case, however, a sequence of rearrangements from several middle-stage switches may be required for SRN operation. An algorithm to achieve this sequence of rearrangements is presented and its correctness is proved. The minimum resource requirements to achieve SRN operation, in terms of the number of middle-stage switches, are derived for various cases     

On the blocking performance of EGS networks under multicast traffic

Extended generalized shuffle (EGS) networks are a wide class of interconnection networks introduced by Richards (1993). In this work, we study the blocking performance of EGS networks under point-to-multipoint traffic. Two new routing algorithms for multicast connections in EGS networks are defined, and a theorem proving that these algorithms construct minimum-cost connection trees is enclosed. Simulation results show that the blocking performance of EGS networks under multicast traffic is much better than that of three-stage Clos networks of equal complexity     

PetaStar: a petabit photonic packet switch

This paper presents a new petabit photonic packet switch architecture, called PetaStar. Using a new multidimensional photonic multiplexing scheme that includes space, time, wavelength, and subcarrier domains, PetaStar is based on a three-stage Clos-network photonic switch fabric to provide scalable large-dimension switch interconnections with nanosecond reconfiguration speed. Packet buffering is implemented electronically at the input and output port controllers, allowing the central photonic switch fabric to transport high-speed optical signals without electrical-to-optical conversion. Optical time-division multiplexing technology further scales port speed beyond electronic speed up to 160 Gb/s to minimize the fiber connections. To solve output port contention and internal blocking in the three-stage Clos-network switch, we present a new matching scheme, called c-MAC, a concurrent matching algorithm for Clos-network switches. It is highly distributed such that the input-output matching and routing-path finding are concurrently performed by scheduling modules. One feasible architecture for the c-MAC scheme, where a crosspoint switch is used to provide the interconnections between the arbitration modules, is also proposed. With the c-MAC scheme, and an internal speedup of 1.5, PetaStar with a switch size of 6400 /spl times/ 6400 and total capacity of 1.024 petabit/s can be achieved at a throughput close to 100% under various traffic conditions.