Clos交换结构中采用贯序匹配的高效调度算法

使用Clos结构的多阶段互联是构建大规模分布式交换系统重要的解决方案,而如何在Clos拓扑上进行高效的调度成为业界和学术界一直感兴趣的问题.现有的调度算法CRRD存在两个不足而制约了其调度效率,首先是它采用接力式的匹配算法,导致匹配成功率以串行方式降低,其次是调度按照多对一的方式匹配,容易浪费调度机会.本文提出的贯序匹配算法SM-ACN在这两个方面进行了改进.SMACN采用直通式匹配,整个匹配过程一次完成,同时采取多对多的接受方式,最大程度利用了调度机会.数值模拟显示SMACN在各种流量场景下都比传统的CRRD有较高的吞吐率.     

高速IP路由器中输入排队调度算法综述

高速IP路由器一般采用基于定长信元的交换结构,其可扩展性和性能分别受排队策略和调度算法的影响.基于输入排队策略的路由器具有良好的可扩展性,但需要一个有效的调度算法的支持,才能保证吞吐率和延迟等性能.主要讨论输入排队调度算法,将现有的调度算法分为4类:最大(无权重)匹配、最大权重匹配、稳定婚姻匹配和确定型调度.对每一类算法,从技术特点和性能指标两个方面进行比较和分析.最后给出了输入排队调度算法的发展趋势.     

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

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

一种维序的基于组合输入输出排队的并行交换结构

提出一种按序排队(in-order queuing,简称IOQ)PPS体系结构,通过在分流控制器引入固定尺寸的缓冲区,实现负载在每个交换平面的均匀分配;中间层组合输入输出排队(combined input-and-output queuing,简称CIOQ)交换平面受控于中央调度器,在每个时间槽(timeslot),中央调度器将同一种匹配实施到每一个交换平面,称之为同步调度策略.可以证明,在该体系结构下,轮询(round robin)分派算法配合同步调度策略可以保证同一条流的信元按序从交换平面读出.进一步提出了严格最长队列优先同步调度算法,极大地减少了中央调度器需要维护的状态信息和信元重定序开销.与目前主流的PPS设计相比,IOQPPS(in-order queuing parallel packet switch)实现机制简单,易于硬件实现.模拟结果表明,IOQPPS具有最优的延迟性能.     

Crossbar输入排队调度算法的研究

研究高效易于硬件实现的队列调度算法的目的是为了提高交换系统吞吐率和降低延迟。在阐述输入排队、HOL阻塞、虚拟输出队列等概念的基础上,对MSM、PIM、RRM、iSLIP等调度算法进行了系统的比较,研究表明iSLIP算法是一种性能良好、实现简单的算法。     

基于输入排队的高速交换调度算法研究

高速交换网络一般采用基于定长信元的交换结构,其性能决定于排队策略和信元调度算法.输入排队策略只有和一个有效的调度算法相结合,才能保证交换结构具有良好的吞吐率和时延等性能.主要阐述了基于VOQ的最大数量匹配算法,最大权重匹配算法,稳定结合算法,神经网络算法等输入排队调度算法,分别从技术特点,性能指标和实现复杂度等多个方面进行比较和分析.分析了分布式和集中式两大类调度算法的工作方式,并根据各类算法的特点提出,神经网络算法可以通过定义其优先级函数实现其余各类算法.     

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

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

面向子流的低延迟数据调度算法

P2P流媒体是分发流媒体数据的高效方式,而数据传输延迟是决定P2P流媒体系统性能的重要参数。在分析"拉"模式数据调度模式传输延迟的基础上,本文在"推"、"拉"混合的调度模式下提出一种新的面向子流的低延迟数据调度算法。首先子流的调度问题被转换成等价的带权二部图匹配问题,其次针对转换后的二部图改进匈牙利算法,提出最小延迟、最大匹配的启发式匹配算法。该算法在保证最大匹配的同时使得每条子流的延迟尽可能地低。模拟实验表明本文的算法能够极大降低数据传输延迟。     

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

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

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

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

WiMAX接入技术在IPTV系统中的应用研究

在分析IPTV接入网的要求和WiMAX技术优势的基础上,提出了WiMAX应用于IPTV的系统模型,并具体分析了系统流程;针对IPTV业务下行数据量比较大的特点,提出了适合IPTV业务特点的下行链路实时调度(DLRTS)算法,该算法的主要目的在于降低实时业务的时延,从而保证IPTV的服务质量(QoS)。仿真结果表明,与常用的轮叫调度(Round R0bin)算法相比,本文算法在实时业务的时延和吞吐量两方面的性能都有明显提高,可很好地支持IPTV业务。     

并行交换中支持包保序的新技术

由于并行交换结构的负载平衡特性和并行原理,到达同一目的输出端口的分组包被分散到了各个交换模块,当它们抵达输出端口时,其先后顺序无法得到保障。文章为解决该难题提出一种新技术,包括虚拟输入排队(VIQ)结构和包保序轮询(SKRR)算法,并且从理论上分析了这种新技术的吞吐率和时延性能。     

基于赤字轮询算法的无线Mesh网络公平性研究*

无线Mesh网络在负载较重时会出现严重的空间不公平现象,即远离网络中心的节点很难将其数据传送到网关。赤字轮询算法能够保证节点数据传输的公平性要求,但却存在吞吐量平均化的问题。在分析无线Mesh网络公平性问题的基础上,提出基于最小均方的动态赤字轮询算法,其核心思想是动态调整轮询权重值。仿真在IEEE 802.11 DCF机制下将所提出的算法与传统的赤字轮询及弃尾算法进行比较,结果表明,所提出的方法能够保证吞吐量需求不同的业务流之间的公平性,并使网络总吞吐量获得提高。     

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.     

Design of a crossbar VOQ real-time switch with clock-driven scheduling for a guaranteed delay bound

Most commercial network switches are designed to achieve good average throughput and delay needed for Internet traffic, whereas hard real-time applications demand a bounded delay. Our real-time switch combines clearance-time-optimal switching with clock-based scheduling on a crossbar switching fabric. We use real-time virtual machine tasks to serve both periodic and aperiodic traffic, which simplifies analysis and provides isolation from other system operations. We can then show that any feasible traffic will be switched in two clock periods. This delay bound is enabled by introducing one-shot traffic, which can be constructed at the cost of a fixed delay of one clock period. We carry out simulation to compare our switch with the popular iSLIP crossbar switch scheduler. Our switch has a larger schedulability region, a bounded lower end-to-end switching delay, and a shorter clearance time which is the time required to serve every packet in the system.     

一种支持QoS的多级交换网络调度算法

现有MSM多级交换结构在非均匀业务源下性能不高.在深入分析多级交换网络内部拥塞控制理论的基础上,提出了一种中间级带缓存的多级交换结构-CB-3Clos结构及信用分发模式下基于背压的流控策略.通过理论分析了中间级负载分配算法应该满足的条件,给出了一种能够有效支持QoS的简单的类iSLIP调度算法-RGA算法.仿真结果表明:与现有的CRRD算法相比,RGA算法具有与业务源模型无关的高吞吐量特性,并在不均衡业务源模型下具有较好的时延性能.     

A proportional fairness scheduling for wireless sensor networks

This paper describes a packet scheduling algorithm for wireless sensor networks (WSNs) that meets the proportional fairness principle. Based on the weighted round-robin strategy, the proposed scheduling algorithm allocates a different service quota to different traffic according to the average packet arrival rate. This guarantees proportional fairness in terms of the average packet delivery delay and the average packet loss ratio. Since the scheduling algorithm does not perform high-load operations such as time stamping and sorting, it can be implemented easily and is suitable for resource-limited WSNs. The proposed scheduling algorithm is tested in a WSN and is found to guarantee the proportional fairness of the average packet delivery delay when this is used as the performance metric, and to realize proportional fairness in the average packet loss ratio when all the queues are overflowing and the average packet loss ratio is used as the performance metric.