一种具有信元保序能力的Clos网络分布式调度算法

分组交换三级Clos网络信元调度算法可分为集中式和分布式两种实现方式.分布式调度具有良好的可扩展性,适于在高速大容量环境中应用.然而由于分布式调度会带来同一分组各个信元间的乱序问题,给其实现带来困难.该文提出了一种具有信元保序能力的三级Clos网络分布式调度算法.该算法包括第一级的均匀负载分配、中间级的并行调度和第三级的按序输出调度三部分.文中对算法的性能进行了严格的理论证明和相关的仿真分析,表明该算法可以很好地解决传统分布式调度中的信元乱序问题,具有良好的性价比.     

一种并行结构路由器保序自适应负载平衡结构

论文提出了一种通用的并行结构路由器具有IP包保序功能的自适应负载平衡结构APOKLB(AdaptivePacket-Order-KeepingLoadBalancer)和一种有效的基于流分类的信元调度算法FCS(FlowClassification-basedScheduling)。分析了FCS的算法复杂度、APOKLB所需内存数量、带宽及其平均排队延迟,并给出了APOKLB与几种保序结构进行了比较。     

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

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

带输入队列并行交换的负载平衡分析

并行交换是新兴的交换技术,基于该技术能够利用小型交换模块来构建大容量的交换系统,例如太比特或更高容量的交换机.把带输入队列的并行交换称为带缓存并行交换(buffered parallel switch,简称BPS),重点研究其中并行且独立工作的交换模块之间的负载平衡问题.从不同角度出发,提出两种负载平衡的定义.基于两种定义,分别分析了BPS负载平衡的条件并提出分布式调度算法族.最后,提出一种简单而有效的调度算法,该算法能在无加速比BPS中同时满足两种定义,仿真实验结果表明了该算法的有效性和良好性能.另外,就算法的工程实现进行了讨论.     

并行分组交换中基于分路的分布式负载平衡技术

负载平衡是并行分组交换的一项关键技术,目前已知在高速率查表后应用负载平衡技术可取得良好效果,但在OC768（40Gbps）甚至OC3072（160Gps）下进行包处理工作是很困难的．基于分路包处理和分路负载平衡的思想,提出一种基于分路的分布式负载平衡控制结构和DDPA算法,依据工程设计考虑,还提出基于丢包策略的DDPA算法,对它们的有效性做出证明并定量地计算出其关键参数．     

基于ATM交换结构的Hopfield神经网络调度算法

针对ATM交换结构,采用输入缓冲和每条入线在同一个时隙内可传送多于一个信元的策略,利用神经网络具有的实时性、高度并行处理能力和易于电路或光电技术实现等特点,提出了一种Hopfield神经网络调度算法。实验仿真比较表明,该方法不但大大提高了吞吐率,消除了队头阻塞造成的性能恶化,而且降低了信元丢失率和较大程度地降低了平均信元时延,提高了ATM交换结构的性能,实现了信元的优化调度。     

并行分组交换中负载平衡充要条件的分析

负载平衡是并行分组交换(PPS-parallelpacketswitch)结构的一项关键技术,该文对带缓存PPS结构中负载平衡的充要条件进行了研究。首先基于守恒原理建立流体并行交换的流量守恒方程,并分析流体并行交换中负载平衡的充要条件,在此基础上建立PPS的流量守恒方程,并定义PPS负载平衡,分析PPS负载平衡算法应该满足的充要条件。     

iRSDRR:一种全异步的基于输入排队Crossbar交换结构的调度算法

DRR(DualRound-Robin)[1]调度算法是一种公平、高效、硬件实现简单的基于输入排队Crossbar交换结构的信元调度算法。为了进一步改善这种算法的性能,该文提出了一种全异步的多次迭代DRR算法,即iRSDRR(iterativeRo-tatingStaticDualRound-Robin)。该算法在开始时,将所有的输入、输出仲裁器的指针全部设置为异步的,以后每个时隙静态地更新所有的仲裁器的指针。仿真结果表明该算法在不同业务流条件下的性能都优于DRR调度算法。     

一种基于GOV的交互式滑动调度算法

基于在曙光机上进行的MPEG-4视频标准并行编码研究，提出了一种基于GOV的交互式滑动调度算法．该算法考虑了MPEG-4视频编码中的交互需要，处理节点数目、编码延迟、加速比、负载平衡等多种因素．实验结果证明该算法调度费用相对较小，加速比较高，在实际编码中具有更强的可操作性．     

面向控制网络的交换机调度机制研究

针对基于虚拟输出排队的输入队列交换机应用于控制网络所存在的诸多困难,提出了一种新的输入队列交换机结构,并根据新的结构设计了一种基于记录矩阵和需求矩阵的信元传输川页序控制方案,以解决交换机中存在的信元行为及时延的不确定性问题。交换机采用两级调度机制,链接调度提供分级服务,交换调度实现端口匹配,以适应控制网络的流量特征。     

Load-balanced three-stage switch

A load-balanced two-stage switch is scalable and can provide close to 100% throughput. Its major problem is that packets can be mis-sequenced when they arrive at outputs. In a recent work, the packet mis-sequencing problem is elegantly solved by a feedback-based switch architecture. In this paper, we extend the feedback-based switch from two-stage to three-stage for further cutting down average packet delay while still ensuring in-order packet delivery and close to 100% throughput. The basic idea is to use the third stage switch to map heavy flows to experience less middle-stage delays. To identity heavy flows, an adaptive traffic estimation algorithm is proposed. To ensure max-min fairness in bandwidth allocation under any inadmissible traffic pattern, an efficient fair scheduler is devised.     

光纤通道交换机在强实时约束下的分组调度

以光纤通道交换网络强实时约束下的性能研究为背景,采用实时通信中的周期性任务模型,提出了负载匹配的加权轮循分组调度,导出了在该方法下网络消息集严格实时的充要条件,以最差情形下强实时的网络可达负载率为性能衡量指标推证了采用该算法的优越性并通过仿真进行了验证.     

移动自组网基于跨层协作的负载均衡队列调度算法

传统的路由协议都是基于"最短路径"的考虑,节点在对数据包进行调度转发的时候,无条件的为路由控制消息赋予较高的优先转发权,这样就会导致网络中处于骨干位置的节点负载过重,从而进一步影响整个网络的性能.本文提出一种新的基于跨层协作的负载均衡队列调度算法(CLLBS),通过在MAC层与网络层监视节点网络负载,配合路由协议,根据节点的负载状况实时动态地对数据流的转发优先权进行调整,在整个网络进行负载均衡,缓解那些拥塞节点的负载压力.仿真结果表明本文算法较之传统的简单优先权算法有明显的性能提高,可以有效地提高网络的吞吐量,降低丢包率.     

一种面向流媒体的多核处理器分组调度算法*

针对流媒体分组处理和多核网络处理器cache亲和性的特点,提出了综合流调度和分组调度优点的两级调度算法,即FBLA。FCFS调度算法可以达到分组级的细粒度负载均衡,但cache亲和性却很差。基于hash的调度算法可以保证很好的cache亲和性,但难以保证核间负载均衡。FBLA算法对这两种算法进行了折中,既通过cache亲和性提高处理器利用率,又能够达到细粒度的核间负载均衡。理论分析和仿真评估表明,FBLA算法具有良好的cache亲和性和负载均衡性,转发延迟和延迟波动比FCFS算法更低。在亲和因子较小时,F     

高性能分组交换机内部体系结构综述

交换机在电信部门和计算机行业发挥越来越重要的作用,其内部体系结构和调度算法决定交换容量和交换延迟,论文综述分组交换机的内部体系结构。分组交换机按结构可分为单级交换机和多级交换机。单级交换机内部结构可以分为输出缓冲的不相交路径拓扑结构、共享媒体结构、交叉开关结构、共用分组内存的时分结构、单级交换单元扩展的复合单级结构和并行交换单元结构,其特点是端口数目不多。多级交换机由多个级构成,每一级包含多个单级或多级交换单元,端口数目非常多,广泛应用于电信部门。     

Parallel desynchronized block matching: A feasible scheduling algorithm for the input-buffered wavelength-routed switch

The input-buffered wavelength-routed (IBWR) switch is a promising switching architecture for slotted optical packet switching (OPS) networks. The benefits of the IBWR fabric are a better scalability and lower hardware cost, when compared to output buffered OPS proposals. A previous work characterized the scheduling problem of this architecture as a type of matching problem in bipartite graphs. This characterization establishes an interesting relation between the IBWR scheduling and the scheduling of electronic virtual output queuing switches. In this paper, this relation is further explored, for the design of feasible IBWR scheduling algorithms, in terms of hardware implementation and execution time. As a result, the parallel desynchronized block matching (PDBM) algorithm is proposed. The evaluation results presented reveal that IBWR switch performance using the PDBM algorithm is close to the performance bound given by OPS output buffered architectures. The performance gap is especially small for dense wavelength division multiplexing (DWDM) architectures.     

On scheduling transactions in a grid processing system considering load through Ant Colony Optimization

Load balanced transaction scheduling problem is an important issue in distributed computing environments including grid system. This problem is known to be NP-hard and can be solved by using heuristic as well as any meta-heuristic method. We ponder over the problem of the load balanced transaction scheduling in a grid processing system by using an Ant Colony Optimization for load balancing. The problem that we consider is to achieve good execution characteristics for a given set of transactions that has to be completed within their given deadline. We propose a transaction processing algorithm based on Ant Colony Optimization (ACO) for load balanced transaction scheduling. We modify two meta-heuristic along with ACO and three heuristic scheduling algorithms for the purpose of comparison with our proposed algorithm. The results of the comparison show that the proposed algorithm provides better results for the load balanced transaction scheduling in the grid processing system.     

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

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

基于流映射的负载均衡调度算法研究

网络管理者需要能够提供可扩展性、吞吐率保证及报文顺序的高性能路由器体系结构.目前基于Crossbar的集中式路由器体系结构难以实现性能和规模的可扩展,基于两级Mesh网络的负载均衡交换结构成为扩展Internet路由器容量的有效的途径.负载均衡路由器存在严重的报文乱序现象,输出端报文重定序复杂度为O(N2).文中提出一种区域均等的负载均衡交换结构,每k个连续的中间级输入端口划分为一个区域,输入端采用基于流映射的负载分配算法UFFS-k(Uniform Fine-grain Frame Spreading,k为聚合粒度,简称UFFS-k),在k个连续的外部时间槽,以细粒度的方式将同一条流的k个信元分派到固定的映射区域,通过理论证明,该调度策略可获得100%吞吐率并能够保证报文的顺序.为避免流量区域集中现象,采用双循环(dual-rotation)方式构建不同输入端口的流到区域的映射关系;为实现负载在中间级输入端口的均衡分布,每个输入端口维护全局统一视图的流量分布矩阵,UFFS-k调度算法根据流量分布矩阵调度单位帧,可以证明,对任意输出端口j,同一区域OQj队列长度相同且不同区域OQj队列长度至多差1,从而实现了100%负载均衡度.UFFS-k调度算法分布于每个输入端口独立执行,根据流到区域的映射关系及负载分布状态分派信元,模拟结果显示,当聚合粒度k=2时,UFFS-k算法在同类维序算法中表现出最优延迟性能.     

基于多跳间时延协作的最久分组优先算法

提出了一种基于多跳间时延协作的Crossbar调度算法。该算法以分组头中记录的时延为权重对分组进行调度，通过控制分组在各跳上的时延来达到调节端到端时延的目的。算法还使路由器避免了维护每个流的状态信息以及对单个流进行的复杂的队列管理和调度。计算机仿真表明，算法具有较高的资源利用率、较低的端到端时延抖动和较低的分组丢弃率等特点。