基于双轮转指针的输入与交叉点联合排队型(CICQ)交换结构调度算法

CICQ交换结构因具有良好的分布式调度特性而成为构建太比特（Tb／s）级以上交换机的一种理想选择．轮转型调度算法因硬件实现的简单性而得到广泛的研究，尽管此类型的调度算法在均匀流量下具有较高的吞吐率，然而在非均匀的流量下其性能则明显下降．指出了已有轮转型算法在非均匀流量下性能下降的原因，提出了一类基于双指针的轮转型调度算法，即每个输入调度器均有两个轮转指针（主指针和辅助指针）．主指针对应的队列具有最高的调度优先级，算法可以根据各个队列的状态动态决定何时更新主指针。当主指针对应的队列被流控机制阻塞时，将根据辅助指针依次公平服务其他队列．实验结果表明，基于双指针的调度算法可以显著提高CICQ交换机在非均匀流量下的性能．     

混合优化的CICQ交换结构调度算法

联合输入端和交叉点排队（CICQ）的Crossbar是一种性能优于传统结构的交换结构,对CICQ交换结构的特点进行了讨论并提出一种新的混合优化调度（HOPS）算法,算法在输入端调度时采取混合优化的策略,首先尽力保证系统的吞吐率性能,然后根据长队列优先的原则优化系统的时延性能。算法以轮询调度为基础,最多只在输入端进行一次比较操作,其算法复杂度仅为O(1),实现简单。通过流体模型证明该算法对满足强大数定律的许可输入流量能够达到100%的吞吐率性能。仿真结果进一步表明HOPS调度算法在各种流量模型下都能稳定运行,且具有良好的时延和吞吐率性能。     

基于交叉点缓存状态的CICQ调度算法

针对现有的联合输入交叉点排队(CICQ)调度算法在设计时未充分利用交叉点缓存状态信息的问题,提出一种CICQ状态堆调度算法。该算法分布式地运行于CICQ结构的各个输入端口和输出端口。仿真结果表明,在均匀或非均匀流量模型下,基于该算法的CICQ结构都能获得与输出排队结构相当的性能,且具有较高的时延。     

时隙间迭代的输入队列交换机Round-Robin调度算法

输入队列因具有良好的可扩展性而广泛应用于高速交换机和路由器中,但输入队列需要精心设计调度算法以获取较好的性能.Round-Robin算法因其简单性和并行性而得到广泛的研究,但现有的Round-Robin算法在突发流量和非均匀流量下的负荷-延迟性能较差.提出了调度决策在时隙间进行迭代的思想,并利用队列长度具有随机性的特点设计了能近似最大匹配的Round-Robin算法--iSLOT.仿真结果表明,iSLOT不仅在均匀流量下是稳定的,在非均匀流量和突发流量下的吞吐率及延迟性能均远好于现有的Round-Robin算法.     

卫星CICQ交换系统调度算法研究

联合输入交叉点排队(CICQ)交换结构由于在交叉点引入少量缓存,可以将输入端口和输出端口进行有效隔离,降低调度算法的复杂度,并适用于大容量交换。为此,研究基于交叉点缓存的各种调度算法和基于CICQ的交换结构,提出一种基于流量控制的FCSA算法,通过OPNET仿真分析表明该算法在均匀分布和突发业务源的情况下具有较好的时延性能,并且复杂度低,吞吐量大。将该算法应用于星载交换机,结果表明,该算法可以满足星载交换机多业务突发传输的特点,易于硬件实施。     

输入缓冲交换开关的多步调度策略

输入缓冲交换开关已经在越来越多的ATM交换机和高性能路由器中使用.对于独立的信元到达,VOQ(virtual output queueing)技术与LQF(1ongest queue first)和OCF(oldest cell first)等加权调度算法的结合使用可以使利用交换开关的吞吐率达到100%.然而LQF和OCF等加权调度算法过于复杂,无法用硬件实现.提出了多步调度策略,使得用硬件实现加权调度算法成为可能.在该策略下,对于独立的信元到达,LQF算法仍可以达到100%的利用开关吞吐率,并具有良好的     

在CICQ交换结构下PGPS调度算法的实现

基于CICQ结构提出了在输入排队结构下实现基于流的PGPS分组公平调度算法的方案,该结构在可管理的输入流下可提供接近100％的吞吐率。     

一种适合于多播和单播的集成调度算法

具有输入队列结构的路由器或交换机内部交换可以工作在线路速率上，适应了高速网络交换的要求，但现有输入队列调度方案将单播和多播流量分开考虑，使用不同的交换结构和调度算法，不适合网络中多播流和单播流并存的实际情况．该文提出一种不区分多播、单播分组，遵循同一入队策略和同一调度规则的集成调度算法EOPF、(Extented Oldest Port First)．仿真实验表明EOPF算法在各种多播和单播负载组成比例下始终保持高吞吐率，并能在全单播流量下达到100％吞吐率，适合于多播、单播混合存在的网络流量。     

CICQ交换的流控实现机制和交叉点缓存容量分析

传统的基于crossbar的输入排队交换结构在提供良好的QOS方面存在很大的不足，而CICQ（combined input and crosspoint buffered queuing）交换结构与传统的交换结构相比，不但能在各种输入流下提供接近输出排队的吞吐率，而且能提供良好的QoS支持。文章分析了CICQ结构的流控实现机制，讨论了基于信用的流控机制的开销和实现方案，对crosspoint缓存容鼍作了分析，给出了在各种存储器写入条件下，保持交换结构100％吞吐率所需的最小缓存容量。     

支持多优先级分组交换调度算法研究及其调度器设计

输入缓存交换结构的特点是缓存器和交换结构的运行速率与端口速率相等、实现容易,但存在队头阻塞。如果采用虚拟输出排队方法和适当的分组调度算法可予以消除,使吞吐率达到100%。文章首先研究讨论了并行迭代匹配算法,滑动迭代匹配调度算法的基本原理、迭代仲裁步骤及其硬件实现;对高速分组交换调度算法的性能进行了分析比较。然后给出了在高速输入队列交换机中实现多优先级调度算法的调度器设计与实现方案。经设计实现证明高速分组交换调度算法不仅硬件实现简单,而且具有良好的特性。     

缓冲交叉开关交换结构多播调度算法研究

高性能核心交换设备多播调度受到越来越多的关注·交叉开关结构下的多播调度方案或者性能较差,或者过于复杂,难于应用在高速交换场合·为此,提出一种面向多播的多输入队列缓冲交叉开关体系结构·将多播调度分解为信元分派、输入调度、输出调度3个可分布式并行执行的子问题,并设计了相应的调度算法,降低了算法复杂性·实验结果表明,交叉点缓冲区容量与输入队列数量对多播性能都具有很大的影响·在突发流量到达下,与单多播输入队列的体系结构相比,无论是采用O(1)复杂度的HA-RR-RR还是复杂度更高的调度算法,均能显著提高系统吞吐性能·     

Trends in highly scalable crossbar-based packet switch architecture

A combined input and crosspoint queued (CICQ) switch is receiving significant attention to be the next generation high speed packet switch for its scalability; however, a multi-cabinet implementation of a combined input and crosspoint queued (CICQ) switch unavoidably introduces a large round-trip time (RTT) latency between the line cards and switch fabric, resulting a large crosspoint (CP) buffer requirement. In this paper, virtual crosspoint queues (VCQs) that significantly reduces the CP buffer requirement of the CICQ switch is investigated. The VCQs unit resides inside the switch fabric, is dynamically shared among virtual output queues (VOQ) from the same source port, and is operated at the line rate, making the implementation practical. A threshold-based exhaustive round-robin (T-ERR) arbitration is employed to reduce buffer hogging at VCQ. The T-ERR at VCQ and CP arbiters serves packets residing in a longer queue more frequently than packet residing in a shorter queue. Consequently, the T-ERR, drastically increases the throughput of the CICQ switch with small CP buffers. A multi-cabinet implementation of CICQ switch do not support multicasting traffic well since a combination of small CP buffer in the switch fabric and a large RTT latency between the line cards and switch fabric results in non-work conservation of the intra-switch link. Deployment of multicast FIFO buffer between the input buffer and CP buffer shows a promise. With its ability to achieve high throughput independent of RTT and switch port size, the integration of the VCQ architecture and T-ERR scheduler to the CICQ switch is ideal for supporting ever-increasing Internet traffic that requires higher data rate, larger switch size, and efficient multicasting.     

一种支持DiffServ模型的CICQ调度策略

结合大规模接入汇聚路由器需要对不同汇聚业务流进行不同的处理这一实际需求，基于CICQ交换结构，该文给出了一种支持DiffServ模型的调度策略(DS)，该算法以“节点行为”方式对业务流进行调度。和以往算法相比，DS采取了分布式的控制策略，并且具有较低的时间复杂度，工程上更易实现。仿真结果表明，DS不仅能够为EF和AF业务提供带宽保证，而且具有良好的时延性能。     

一种优化指针策略的输入排队调度算法

针对FIRM（fcfs in round-robin matching）算法在处理非均匀业务时,延时和丢包性能出现缺陷的问题,在FIRM算法的基础上设计并实现了一种优化指针策略的low—FIRM（longest oldest weighted FIRM）算法。该算法根据队列长度和队首信元等待时间的权值修改输入端口的轮询指针。使得权值大的队列趋于优先服务,从而优化了在非均匀业务下的调度性能。接着给出了low—FIRM算法的性能分析和仿真,与iSLIP（iterative round—robin matching with slip）算法、FIRM算法进行了比较。仿真结果表明,low—FIRM与经典算法相比,在均匀业务下的性能近似,而在非均匀业务下性能有了较大的提升。     

一种交错编码的多重门限调度算法

提出一种交错编码的多重门限调度算法(interleaving coded multi-threshold scheduling,简称ICMTS).该算法将前、后级队列门限标记交错编码作为权值表征输入调度过程前、后两级队列的整体调度需求,根据交错编码的权值对前级虚拟输出队列进行优化调度判决,并通过多重门限机制降低算法的硬件资源开销.采用流模型证明当加速因子为2时,ICMTS算法可获得100%的吞吐量,并给出ICMTS算法的工程简化设计方案,复杂度为O(logN).仿真仿真结果表明,采用ICMTS算法的工程简化方案即可获得比现有算法更优的调度性能.     

Port partitioning and dynamic queueing for IP forwarding

With the increase of internet protocol (IP) packets the performance of routers became an important issue in internet/working. In this paper we examine the matching algorithm in gigabit router which has input queue with virtual output queueing. Dynamic queue scheduling is also proposed to reduce the packet delay and packet loss probability. Port partitioning is employed to reduce the computational burden of the scheduler in a switch which matches the input and output ports for fast packet switching. Each port is divided into two groups such that the matching algorithm is implemented within each pair of groups in parallel. The matching is performed by exchanging the pair of groups at every time slot. Two algorithms, maximal weight matching by port partitioning (MPP) and modified maximal weight matching by port partitioning (MMPP) are presented. In dynamic queue scheduling, a popup decision rule for each delay critical packet is made to reduce both the delay of the delay critical packet and the loss probability of loss critical packet. Computational results show that MMPP has the lowest delay and requires the least buffer size. The throughput is illustrated to be linear to the packet arrival rate, which can be achieved under highly efficient matching algorithm. The dynamic queue scheduling is illustrated to be highly effective when the occupancy of the input buffer is relatively high.Scope and purposeTo cope with the increasing internet traffic, it is necessary to improve the performance of routers. To accelerate the switching from input ports to output in the router partitioning of ports and dynamic queueing are proposed. Input and output ports are partitioned into two groups A/B and a/b, respectively. The matching for the packet switching is performed between group pairs (A, a) and (B, b) in parallel at one time slot and (A, b) and (B, a) at the next time slot. Dynamic queueing is proposed at each input port to reduce the packet delay and packet loss probability by employing the popup decision rule and applying it to each delay critical packet.The partitioning of ports is illustrated to be highly effective in view of delay, required buffer size and throughput. The dynamic queueing also demonstrates good performance when the traffic volume is high.