负载均衡自路由交换结构

为下一代网络提供服务质量保证的业务,提出了一种新颖的两级负载均衡多路径自路由交换结构.该结构的两级都使用一种多路径自路由结构.第一级通过简单的算法和少量缓存将输入端到达的数据流量均匀地派送到本级各输出端.第二级则通过自路由的方式将数据分组转发到其最终目的端口.数学分析和仿真证明,在理论研究常见的可容许(admissible)流量条件,该结构可以得到100%的吞吐率;在实际的统计可容许(statistical admissible)流量条件下,通过并行叠加机制可以得到100%的吞吐率.与其他结构相比,该结构无排队时延和抖动,硬件复杂性和传输时延也明显减小.     

输入排队Crossbar架构下的矩阵模型 及MM-LQF调度策略

输入排队Crossbar交换是高性能交换设备最为常用而关键的技术之一.本文建立了IQ-Crossbar架构下的矩阵模型,给出了IQ-Crossbar的状态矩阵、队长矩阵、到达矩阵和匹配矩阵的数学定义,并通过分析IQ-Crossbar的信元排队机理,提出和证明了队长矩阵迭代定理和状态矩阵迭代定理.该矩阵模型为分析IQ-Crossbar架构下的调度算法提供了理论依据.基于所建立的矩阵模型,在分析现有LQF调度算法优缺点的基础上,本文提出了一种新的调度策略MM-LQF,该策略的运算效率是LQF的3.72倍,支持的端口门限速率是LQF的2.35倍,在贝努利均匀流量重载条件下平均时延是LQF的1/2;在贝努利Diagonal流量条件下吞吐率为100%.     

保证100%吞吐率的两级组播交换结构

在路由器或交换机的交换结构中实现组播是提高组播应用速度的重要途径之一。传统的交叉开关结构(crossbar)组播调度方案有两种缺陷,一种是性能较低,另一种是实现的复杂度太高,无法满足高速交换的需要。该文提出了一个新的基于交叉开关的两级组播交换结构(TSMS),第1级是组播到单播的交换结构,第2级是联合输入和输出排队(CIOQ)交换,并为该结构设计了合适的最大扇出排队(FCN)优先-均匀分配中间缓存调度算法(LFCNF-UMBA)。理论分析和仿真实验都显示在该结构中,加速比低于22/(N+1)倍时吞吐率不可能实现100%;而采用LFCNF-UMBA调度算法,2倍加速比就可保证在任意允许(admissible)组播的吞吐率达到100%。     

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

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

高速信元交换调度算法研究

输入缓存交换结构的特点是缓存器和交换结构的运行速率与端口速率相等、实现容易,但存在队头阻塞(HOL),其吞吐率只有约58%.采用虚拟输出排队方法(VOQ)和适当的信元调度算法可消除HOL,使吞吐率达到100%.本文通过仿真对几种调度算法:PIM、iSLIP和LPF进行了全面地研究、比较和评价.     

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

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

一种新型可扩展的多级多平面分组交换结构的图论模型与性能分析

该文提出了一种新型可扩展的多级多平面(MPMS)分组交换结构。首先建立了MPMS的图论模型,定量地描述了MPMS中相邻连通性和端口可达性,定义了MPMS的均衡顶点和竞争顶点,并证明了MPMS决定交换性能的输入端口与输出端口间的无阻塞条件。从性能参数和结构复杂度等方面与单级交叉开关做了对比分析,结果表明MPMS可以获得P倍的最大端口速率,平方倍的最大端口数,线性比例增长的结构复杂度,具有良好的可扩展性。     

在CICQ交换结构下实现分布式的WFQ类加权公平调度算法

传统的基于crossbar的输入排队交换结构在提供良好的QoS方面存在很大的不足,而CICQ(Combined Input and Crosspoint buffered Queuing)交换结构与传统的交换结构相比,不但能在各种输入流下提供接近输出排队的吞吐率,而且能提供良好的QoS支持。该文基于CICQ结构,提出了在输入排队条件下实现基于流的分布式WFQ类分组公平调度算法的方案,并通过仿真验证了这一方案的有效性。     

一种多优先级变长调度星载IP交换机交换结构的设计

针对星载IP交换机中硬件资源使用受限的情况,设计实现了一种具有8个优先级、采用指针复制和变长分组调度机制的大容量共享存储交换结构,给出了电路的具体组成、关键调度算法和工作流程.使用Xilinx V4sx55 FPGA实现了完整的8×8交换结构,电路共占用了164K字节片上存储器资源和5982个4输入查找表,可以满足三模冗余设计要求.在系统工作主频为100MHz、片外采用SRAM、数据位宽为64的情况下,交换结构的峰值吞吐率可以达到1.6Gbps;片外采用133MHz DDR存储器、位宽为64时,交换结构的峰值吞吐率可以达到4.25Gbps;该交换单元进行多级扩展后,可以满足10Gbps以上的系统设计需求.     

一种基于最长队列预测的CICQ交换结构调度算法

CICQ(Combined Input Crosspoint Queued)是一种在crossbar交叉点加入少量缓存的交换结构,具有无需内部加速比及分布并行调度的特性。为了自适应网络环境中各种业务流量,提高在非均匀流量下的性能,该文提出了一种基于最长队列预测的高效CICQ交换结构调度算法RR-LQD (Round Robin with Longest Queue Detecting)。RR-LQD算法复杂度为O(1),具有良好的可扩展性;通过预测局部最长队列并尽力为其服务,保持调度中队列长度的均衡,能够适应各种非均匀流量的网络环境。仿真结果表明:在各种均匀和非均匀流量下,RR-LQD算法均能达到100%的吞吐量,并且具有优良的时延性能。该文使用FPGA芯片实现了RR-LQD算法仲裁器,能够满足高速、大容量交换结构的设计需要。     

The iSLIP scheduling algorithm for input-queued switches

An increasing number of high performance internetworking protocol routers, LAN and asynchronous transfer mode (ATM) switches use a switched backplane based on a crossbar switch. Most often, these systems use input queues to hold packets waiting to traverse the switching fabric. It is well known that if simple first in first out (FIFO) input queues are used to hold packets then, even under benign conditions, head-of-line (HOL) blocking limits the achievable bandwidth to approximately 58.6% of the maximum. HOL blocking can be overcome by the use of virtual output queueing, which is described in this paper. A scheduling algorithm is used to configure the crossbar switch, deciding the order in which packets will be served. Previous results have shown that with a suitable scheduling algorithm, 100% throughput can be achieved. In this paper, we present a scheduling algorithm called iSLIP. An iterative, round-robin algorithm, iSLIP can achieve 100% throughput for uniform traffic, yet is simple to implement in hardware. Iterative and noniterative versions of the algorithms are presented, along with modified versions for prioritized traffic. Simulation results are presented to indicate the performance of iSLIP under benign and bursty traffic conditions. Prototype and commercial implementations of iSLIP exist in systems with aggregate bandwidths ranging from 50 to 500 Gb/s. When the traffic is nonuniform, iSLIP quickly adapts to a fair scheduling policy that is guaranteed never to starve an input queue. Finally, we describe the implementation complexity of iSLIP. Based on a two-dimensional (2-D) array of priority encoders, single-chip schedulers have been built supporting up to 32 ports, and making approximately 100 million scheduling decisions per second     

Minimizing Internal Speedup for Performance Guaranteed Switches With Optical Fabrics

We consider traffic scheduling in an N times N packet switch with an optical switch fabric, where the fabric requires a reconfiguration overhead to change its switch configurations. To provide 100% throughput with bounded packet delay, a speedup in the switch fabric is necessary to compensate for both the reconfiguration overhead and the inefficiency of the scheduling algorithm. In order to reduce the implementation cost of the switch, we aim at minimizing the required speedup for a given packet delay bound. Conventional Birkhoff-von Neumann traffic matrix decomposition requires N2 - 2N + 2 configurations in the schedule, which lead to a very large packet delay bound. The existing DOUBLE algorithm requires a fixed number of only 2N configurations, but it cannot adjust its schedule according to different switch parameters. In this paper, we first design a generic approach to decompose a traffic matrix into an arbitrary number of Ns (N² - 2N + 2 > N_S > N) configurations. Then, by taking the reconfiguration overhead into account, we formulate a speedup function. Minimizing the speedup function results in an efficient scheduling algorithm ADAPT. We further observe that the algorithmic efficiency of ADAPT can be improved by better utilizing the switch bandwidth. This leads to a more efficient algorithm SRF (scheduling residue first). ADAPT and SRF can automatically adjust the number of configurations in a schedule according to different switch parameters. We show that both algorithms outperform the existing DOUBLE algorithm.     

一种新型的负载均衡-交叉点缓冲交换结构

针对混合输入-交叉点队列(CICQ)交换结构受限于"流控通信延时"、"需要2倍内部加速仿真输出队列(OQ)交换"以及单纯交叉点缓冲(CQ)存在"非均衡流量模式下吞吐量性能不足"等问题,本文提出一种新型的"负载均衡交叉点缓冲交换结构".采用固定模式时隙轮转匹配进行负载均衡处理,将到达输入端口的非均衡流量转化为近似均衡流量并且平均分配到同一输出端口对应的交叉缓冲中,从而可以利用较小的交叉点缓冲来模拟输出队列调度,简化调度过程并且提高吞吐量.理论分析证明了这种新结构的稳定性以及模拟输出队列交换的能力.同时仿真表明,采用该交换结构可以在不需要内部加速的条件下获得相当于输出队列交换的性能,并且有效地解决了交叉点缓冲队列非均衡流量性能不足的问题.     

Deficit round-robin scheduling for input-queued switches

We address the problem of fair scheduling of packets in Internet routers with input-queued switches. The goal is to ensure that packets of different flows leave a router in proportion to their reservations under heavy traffic. First, we examine the problem when fair queuing is applied only at output link of a router, and verify that this approach is ineffective. Second, we propose a flow-based iterative deficit-round-robin (iDRR) fair scheduling algorithm for the crossbar switch that supports fair bandwidth distribution among flows, and achieves asymptotically 100% throughput under uniform traffic. Since the flow-based algorithm is hard to implement in hardware, we finally propose a port-based version of iDRR (called iPDRR) and describe its hardware implementation.     

一种可提供QoS保障的新型交换结构

本文采用带缓存交叉开关作为核心交换单元,构建了一种空分复用扩展的联合输入/交叉节点/输出排队(SDM-CICOQ)交换结构,从理论上证明了当扩展因子为2时,SDM-CICOQ交换结构可以获得100%的吞吐量,并且能够完全模拟输出排队(OQ)交换结构,从而能够提供服务质量(QoS)保障.本文还给出了一种层次化优先级调度(HPS)方案作为SDM-CICOQ交换结构调度机制的工程设计参考,仿真结果表明采用HPS调度方案SDM-CICOQ交换结构可获得良好的性能.     

Asymptotic Performance Limits of Switches With Buffered Crossbars Supporting Multicast Traffic

Input queued (IQ) switches exploiting buffered crossbars (CICQ switches) are widely considered very promising architectures that outperform IQ switches with bufferless switching fabrics both in terms of architectural scalability and performance. Indeed the problem of scheduling packets for transfer through the switching fabric is significantly simplified by the presence of internal buffers in the crossbar, which makes possible the adoption of efficient, simple and fully distributed scheduling algorithms. This paper studies the throughput performance of CICQ switches supporting multicast traffic, showing that, similarly to IQ architectures, also CICQ switches with arbitrarily large number of ports may suffer of significant throughput degradation under ldquopathologicalrdquo multicast traffic patterns. Despite the asymptotic nature of these results, the authors believe that they can contribute to a deeper understanding of the behavior of CICQ architectures supporting multicast traffic.     

Cell Switching Versus Packet Switching in Input-Queued Switches

Input Queued (IQ) switches have been well studied in the past two decades by researchers. The main problem concerning IQ switches is scheduling the switching fabric in order to transfer packets from input ports to output ports. Scheduling is relatively easier when all packets are of the same size. However, in practice, packets are of variable length. In the current implementation of switches, variable length packets are segmented into fixed length packets—also knowns as cells—for the purpose of scheduling. However, such cell-based switching comes with some significant disadvantages: (a) loss of bandwidth due to the existence of incomplete cells; and (b) additional overhead of segmentation of packets and re-assembly of cells. This is a strong motivation to study packet-based scheduling, i.e., scheduling the transfer of packets without segmenting them. The problem of packet scheduling was first considered by Marsan They showed that under any admissible Bernoulli IID (independent and identically distributed) arrival traffic, a simple modification of the Maximum Weight Matching (MWM) algorithm achieves 100% throughput. In this paper, we first show that no work-conserving (i.e., maximal) packet-based algorithm is stable for arbitrary admissible arrival processes. Thus, the results of Marsan are strongly dependent on the arrival distribution. Next, we propose a new class of “waiting” algorithms. We show that the “waiting”-MWM algorithm is stable for any admissible traffic using the fluid limit technique. We would like to note that the algorithms presented in this paper are distribution independent or universal. The algorithms and proof methods of this paper may be useful in the context of other scheduling problems.     

Greedy–knapsack algorithm for optimal downlink resource allocation in LTE networks

The long term evolution as a mobile broadband technology supports a wide domain of communication services with different requirements. Therefore, scheduling of all flows from various applications in overload states in which the requested amount of bandwidth exceeds the limited available spectrum resources is a challenging issue. Accordingly, in this paper, a greedy algorithm is presented to evaluate user candidates which are waiting for scheduling and select an optimal set of the users to maximize system performance, without exceeding available bandwidth capacity. The greedy–knapsack algorithm is defined as an optimal solution to the resource allocation problem, formulated based on the fractional knapsack problem. A compromise between throughput and QoS provisioning is obtained by proposing a class-based ranking function, which is a combination of throughput and QoS related parameters defined for each application. The simulation results show that the proposed method provides high performance in terms of throughput, loss and delay for different classes of QoS over the existing ones, especially under overload traffic.     

带偏射补偿机制的Birkhoff-von-Neumann交换机方案及其性能分析

Birkhoff-von-Neumann(BvN)交换机具有较低的执行复杂度和较高的吞吐量,但无法在业务突发的环境下提供性能保证。为此,提出一种带偏射的BvN(D-BvN)交换机制来增强交换机性能。D-BvN交换机通过平均业务矩阵的BvN分解,为每个虚电路(VC)提供均值带宽保证,同时通过偏射来处理业务突发。其主要思想是利用处于空闲状态的VC的闲置容量处理处于溢出状态的VC的溢出业务。具体地,偏射机制利用空闲VC的闲置容量完成两件事情:一是把溢出业务偏射到其他VC,二是给偏射业务提供到达目的端口的带宽。分析和仿真结果表明,所提方法不仅可以获得接近100%的输入负载吞吐量,而且具有较低的包乱序概率和较小的业务包延时。     

面向可重构服务承载网的分域混合承载组调度研究

传统网络技术体系,网络是封闭的、刚性的,无法满足未来网络大量差异化业务的规模化应用,由此提出了面向服务提供的柔性网络技术体系,该体系将传统网络中的用户业务、网络服务和网络基础设施中的紧耦合关系转变为松耦合关系,通过资源分割构建可重构服务承载网实现对业务的服务质量保证。该文分析了服务承载网映射到交换结构的需求,提出分域调度的思想。通过选择关闭部分交叉节点的方法建立了crossbar交换结构分域模型,实现了分域调度的端口分离。提出了支持可重构服务承载网构建的混合承载组调度(HCGS)算法,推导了承载组内SDRR(Smoothed Deficit Round Robin)调度、单个域内基于时间戳的输入端口调度和交叉节点输出端口调度算法,证明了HCGS具有良好的时延性能和最坏公平指数(WFI)公平性。仿真结果表明:在均匀分布的泊松业务源条件下,分域HCGS算法具有更优的时延性能,可保证业务带宽的公平性。在diagonal非均匀允许流量条件下,该算法的吞吐量可达100%。