CICQ的高性能LQF_DRR调度算法

通过研究4种经典的CICQ调度算法,提出一种高性能的LQF_DRR交换调度算法。该算法在输入端采用最长队列优先调度策略,在输出端采用DRR调度机制,通过输入端与输出端的相互配合,优先服务异常队列,以减小交换结构输入端长队列对算法性能的影响。仿真结果证明该算法在各种流量下都有良好的时延性能和稳定性。     

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

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

全光分组交换路由器缓存需求研究

针对当前只能在一个集成光电芯片上实现容量为几十个分组的光先来先服务（FCFS）缓存,大规模的光缓存仍无法实现的问题,利用接入链路速率远小于骨干链路速率这一特性,在牺牲25％的链路利用率的条件下,讨论小缓存能否满足采用CIOQ缓存队列的全光分组交换路由器的性能需求。从理论上证明采用CIOQ缓存队列的路由器的缓存需求小于采用OQ缓存队列的缓存需求,通过分析和仿真发现,20个分组的缓存即可满性能需求。     

iSLIP调度算法研究及其实现

目前，为提高交换系统吞吐率，设计开发高性能网络交换机或路由器内部交换结构的技术已趋成熟．但易于在硬件中实现的、高效的队列调度算法仍然是一项值得研究的重要技术．文章首先讨论了对于输入缓冲采用FIF0队列交换系统，其吞吐率主要受HOL队首阻塞的影响．然后研究了iSLIP调度算法的基本原理、迭代仲裁步骤及它在硬件中的实现．针对硬件交换转发判决这一关键问题，给出了在输入队列交换机中采用虚拟输出队列的交换结构和多优先级调度算法的硬件实现方案．最后，对isLIP算法的性能进行了分析比较，证明isLIP算法的实现方案不仅实现简单，而且具有良好的特性．     

基于Crossbar交换结构的虚输出队列研究

交换结构及队列调度算法是影响交换机性能的主要因素。此文对基于C rossbar结构的虚输出队列（VOQ）模型从交换结构、 排列模型、实现原理、吞吐率和调度算法方面进行了分析和研究，为构造高带宽的交换机提供了有意义的结论。     

一种可提供QoS保证的交换结构

面向以太网的物理帧时槽交换（EPFTS）是四川省网络与通信技术重点实验室提出的“单物理层用户数据传输平台网络”中的关键技术,它是以“面向以太网的帧”为数据传输单元的高速交换技术,正是针对实现EPFTS而提出的交换结构方案。在对常用的交换结构和调度算法进行分析的基础上,针对EPFTS要达到的目标和技术特点,提出了一种能够在物理层交换中保证服务质量的交换结构,称为基于总线的、每输入-输出独立的输出缓存交换结构,同时提出了逻辑队列的排队策略,并对该结构进行了软件仿真。仿真结果表明,使用加权公平调度算法,提出的交换结构对实时业务可提供端到端的QoS保证,对非实时业务可提供最大-最小公平服务。     

iLQF调度算法及其参数的仿真

文章介绍一种无内部阻塞ATM交换结构的输入缓存模型及其缓存信元的iLQF调度算法(即迭代的最长队列优先调度算法),并具体给出该算法的实现方案。通过仿真,分析和确定了交换结构的输入缓存长度和iLQF调度算法的迭代次数对信元丢失率的影响。     

共享缓存分组交换系统中的最佳阈值Pushout策略

提出了一种用于共享缓存分组交换设备的最佳闽值Pushout的缓存管理策略（OTP）。在这个策略巾，缓存区采用共享的方式，而每个输出端口分组调度采用Pushout策略。OTP策略的主要思想是将输出端口按照其队列长度分为括跃和非活跃端口，根据队列长度与端口的话跃程度决定分组的接纳或丢弃。仿真结果表明，OTP策略在多个输出队列的情况下具有较好的公平性和鲁棒性，同时在丢包率方面，OTP策略的分组丢失率接近于SP（Selection Pushout）策略。     

基于多输出端口的简单高效的交换结构

基于并行存储机制构建高性能PMS交换结构,采用流模型证明在不加速的情况下,PMS交换结构对满足强大数定律的可容许到达业务能实现100%的吞吐量。基于该交换结构,提出支持分组且具有多个输出端口的最短队列优先轮询算法SQF-RR。仿真结果表明,应用该算法的PMS交换结构能获得较好的性能。     

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

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

MPFS: A truly scalable router architecture for next generation Internet

A new generation architecture of IP routers called massive parallel forwarding and switching （MPFS） is proposed, which is totally different from modern routers. The basic idea of MPFS is mapping complicated forwarding process into multilevel scalable switch fabric so as to implement packet forwarding in a pipelining and distributed way. This processing mechanism is named forwarding in switching （FIS）. By interconnecting multi-stage, lower speed components, called forwarding and switching nodes （FSN）, MPFS achieves better scalability in forwarding and switching performance just like MPP. We put emphasis upon IPv6 lookup problem in MPFS and propose a method for partitioning IPv6 FIB and mapping them to switch fabric. Simulation and computation results suggest that MPFS routers can support line-speed forwarding with a million of IPv6 prefixes at 40 Gbps. We also propose an implementation of 160 Tbps core router based on MPFS architecture at last.     

Modular multicast ATM switching architecture

A modular multicast packet switching architecture is proposed for the B-ISDN/ATM. In this switching architecture, we use the abilities of a broadcast bus suitable for multicasting services. Instead of using the concatenation of a copying network and a routing network, we use the same switching network to perform both copying and routing of multicast packets. This multicast switch architecture treats unicast and multicast packets in the same way; the delay time for these two kinds of packets has the same characteristics for the affective load in the switching. Through the modularity of this switching architecture, it is easy to dimension the switching system. We also include a mathematical analysis of this architecture.     

基于分配格理论的大规模线速组播交换系统

采用Altera公司的StratixIV系列FPGA芯片为平台,根据代数分配格理论,构造适合组播的排序结构;结合已建立的多路径自路由结构;最终构造出基于代数分配格的线速组播交换结构。同时,研究此结构应用于大规模组播交换的方法,并设计支持该结构的自路由组播线速扇出复制过程的带内信令机制和控制机制。     

高性能交换与调度仿真平台的设计与实现

仿真实验已成为交换结构和调度策略性能评价的重要手段,而目前存在的交换结构与调度策略的仿真软件在可继承性与可扩展性方面还存在缺陷.基于Crossbar交换结构,建立数学模型,引入系统级设计方法,采用面向对象技术,设计并实现了用于研究交换结构和调度策略的仿真平台——SPES(switching performance evaluation system).该平台集成了输入排队、输出排队、联合输入输出排队、联合输入交叉点排队等多种交换结构以及相应调度策略.设计上实现了业务流、交换结构和调度策略三者之间的分离,具有良好的可继承、可扩展特性.用户通过与仿真平台之间的简单交互,完成模块的添加与仿真环境参数的配置,在支持变长业务、区分服务质量模型和多交换平面仿真方面具有良好的特性.通过简单扩展。该平台还可以实现网络级性能仿真.最后给出了基于该平台,在CICQ(combined input and crosspoint queuing)交换结构下,对所提出的支持DiffServ模型的分布式调度策略DS(DiffServ supporting algorithm)在不同业务流模型下的性能测试结果,并与输入、输出排队交换结构进行了比较,展示了DS良好的性能,验证了仿真平台的合理性.     

使用多级交换网络进行高性能路由器设计

拓扑结构和路由算法是影响多级交换网络性能的重要因素．在比较多种多级互连拓扑属性的基础上,提出将3D Torus结构应用于大规模交换网络设计．然后针对3D Torus交换网络中报文路由面临的两个关键问题：多路径负载均衡和报文保序,提出一种基于维序的多路径路由算法DMR(dimension-order—based multi—path routing)．该算法可在保证报文顺序的同时在多条路径上平衡负载,提高交换网络吞吐率．最后通过模拟验证了算法的性能,并与维序路由和随机路由算法进行了比较．模拟结果表明,DMR算法的性能优于维序路由算法,能够达到随机路由算法性能水平,同时具有随机路由算法所不具备的报文保序特性．     

一种面向MSM型Clos交换结构的启发式并发调度算法

调度算法一直是交换系统中不可或缺的研究内容.为满足新型高速路由及交换系统的研究需求,提出一种主动授权并发轮询调度算法——CRRD-AG算法.多级交换结构Clos交换网络以其良好的可扩展性作为高速交换结构倍受关注,但与之相适应的调度算法却并不多.目前主流算法,如并发分派算法(CD)和基于轮询的并发分派算法(CRRD),不是吞吐率较低就是所处理的业务流单一.CRRD-AG算法以CRRD为基础,将经典的"请求-授权-接受"的匹配计算模式改进为"主动授权-接受"的匹配模式,不仅能够降低CRRD算法在第1阶段的仲裁信息量,而且充分利用了中间级链路带宽,从而降低了整个系统的平均延迟,提高了吞吐率.进行充分的实验后,其结果表明,无论是在均匀业务,还是在突发业务环境中,CRRD-AG算法都能保证100%的吞吐率,更为重要的是,在不降低吞吐率的情况下能够显著改善分组的平均延迟.     

A note on models for non-probabilistic analysis of packet switching networks

We consider two models commonly used in the literature to model adversarial injection of packets into a packet switching network. We establish the relation between these two types of models, and between them and the set of sequences of packets that allow stability. We also consider the adaptive setting in which packets are injected with only their source and destination but without a prescribed path to follow.     

A Novel Framework for IP DiffServ over Optical Burst Switching Networks

This paper presents a novel framework for IP Differentiated Services (DiffServ) over optical bursts witching (OBS), namely, DS-OBS. The network architecture, functional model of edge nodes and core nodes,the control packet format, a novel burst assembly scheme at ingress nodes and scheduling algorithm of core nodes are presented. The basic idea is to apply DiffServ capable burst assembly at ingress nodes and perform different per hop behavior (PHB) electronic treatments for control packets of different QoS class services at core nodes. Simulation results show that the proposed schemes can provide the best differentiated service for expedited forwarding (EF), assured forwarding (AF) and best effort (BE) services in terms of end-to-end delay, throughput and IP packet loss probability.     

数据中心网络光电交换架构下的流调度算法研究

研究了基于多级Clos数据中心网络的光电交换架构下的流量调度算法,以减少数据传输时延,同时也保证无丢包。传统ADAPT调度算法能实现加速比最小化,但仍然有一些空闲时间槽,而造成带宽未被充分利用。为了解决该问题,在多级Clos网络中,提出了一个多跳路由和调度（Multi-Hop Routing and Scheduling,MHRS）算法,该算法可以在不增加加速比的同时充分利用空闲的带宽。与ADAPT算法类似,MHRS算法先将流量矩阵分解为商矩阵和余矩阵,然后实现两步调度,即将单跳作为第一步,将多跳作为第二步。第一步将余矩阵中的一些数据包调度到商矩阵所形成的配置矩阵的空闲时间槽中,而当这些数据包不能在第一步中被直接调度时,则采用第二步绕道的多跳调度过程传输数据包。仿真结果证明,在多级Clos网络中MHRS算法比ADAPT算法性能更好。     

A method to evaluate the spatial extensibility of a switching unit and network

Switching units and networks have been analyzed as extensible fabrics,mostly in terms of their scheduling algorithms.The traditional literature on switching extensibility has provided complexity theory only relating to the total numbers of inputs(or outputs)and exchange lines.This paper analyzes switching extensibility in terms of not only the scheduling algorithm and also the fabric itself.It is found that determining extensibility from soft complexity related to the number of inputs(or outputs)of the scheduling algorithm and the fabric extensibility in previous studies without quantization is a flawed conception.A method is thus proposed to express the spatial extensibility of a switching unit or network in terms of the connections of a switching resource and capacity.The method calculates parameter ES(the efciency of switching)of an m×n switching unit and obtains two functions of the switching unit to describe spatial extensibility along with the number of unilateral inputs or outputs.It is found that the range of ES is(0,1]and three types of switching unit and two types of crosspoint networks have ES=1.ES is calculated for banyan,Clos,parallel packet,fully interconnected and recirculation switching networks.The ES value for the banyan switching network is larger than that for other networks,and switching networks are classified into three types that have absolute/linear/denied spatial extensibility according to the limES value.It is demonstrated that a switching network has the largest ES value when it contains only the five types of switching unit for which ES=1.Finally,a group-switching-first self-routing banyan switching network with lower blocking probability and time delay is deduced,and the ES method is contrasted with two other methods of evaluating spatial extensibility in terms of their mathematical expressions and intuitive graphics,for the five types of switching network listed above.