两级分布式共享存储器结构及算法

商用存储器的随机访问速率和交换结构的交换速率一直是限制高速路由器性能提高的主要因素，改善交换结构使其降低对存储器存取速率的要求是解决问题的关键。本文提出了两级分布式共享存储器(TSDSM)结构，给出了该结构模拟输出排队调度算法所需存储器个数的下界及相应的模拟FCFS与PIFO输出排队算法，并对算法模拟输出排队算法的可行性给出了证明。TSDSM结构及相应的算法控制机制不仅使目前商用存储器的存取速率能满足交换速率的要求，而且交换结构可以工作于非加速状态。     

基于输入端无冲突算法的面向输出排队的交换结构

该文提出了一种全新的面向输出排队的交换结构,该结构将信元存储于输入端,而信元的调度请求面向输出端排队.利用输入端无冲突调度算法,可以使结构对存储器带宽的需求和输入排队交换机一致.该文设计的调度矩阵使算法复杂度和端口规模呈线性关系,且每一步只需要一次按位"与"操作.文章同时证明了结构要达到稳定的充分条件是使用2倍传输加速比.仿真实验表明,对于均匀流量,该结构时延性能和主流交换结构相似,且抖动性能远优于主流交换结构,而在2倍传输加速比时,其时延性能和OQ完全相同;对于非均匀流量,该结构吞吐率性能优于主流交换结构,且在使用1.14倍传输加速比时,其吞吐率性能和OQ相同.     

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

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

基于OPC UA的历史数据存取

论文以OPCUA技术为基础,设计了一种文件结构作为历史数据存储器。同时,在符合OPCUA规范定义的条件下,通过存储过程、存储方式和查询过程三部分给出一种历史数据的存取机制,以便客户高效地处理历史数据。最后,通过实验用程序实现数据存取模拟,并对存储和查询性能进行了测试。     

宽带路由器输入排队调度策略的综合研究

1 引言输入调度策略可以分成输入排队的调度策略和输出排队的调度策略。长期以来,人们一直认为输入排队的调度策略性能比较差,因而对输出排队的调度策略进行了大量的研究。但是,输出排队的调度策略要求输出端的接口速率是输入端的N倍(N是端口数量),否则就会出现大量丢包的情况。随着输入端口速度的不断提高和输入端口数量的增多,输出排队的调度策略已经不能满足高速交叉开关的要求。分组在交换前被拆分成定长的数据包,数据包经过交换结构后在目的端口被组装成原分组,然后送往物理线路。目前的宽带路由器基本上采用输入缓冲的方式。这主要有以下两个方面的原因:第一,采用输入缓冲方式对存储器的速度要求不高。同输出缓冲方式和共享缓冲方式相比,输入缓冲方式对存储器的要求同交换结构的规模无关,从而可以使得路由器的规模较大。第二,在因特网上TCP数据所占的比例很大。TCP数据具有突     

Gigabit路由器中变长分组输入排队的神经网络调度

高速有效的分组调度算法是影响Gigabit路由顺性能的关键。该文基于Hopfield神经网络,提出了一种输入排队的变长分组调度算法,并给出了调度系统的结构。模拟运行显示该算法是高效的。同时提出了硬件实现的电路模型,以利于该算法的实际应用。     

Crossbar交换结构单播调度算法研究

Crossbar交换网络作为目前大容量路由器主流的交换结构,通过对其研究分析,基于VOQ的输入排队交换网络结构性能好,且易实现,并针对该结构提出了调度算法,解决了调度中的匹配问题。     

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

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

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

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

BYS91─1多机系统存储器频带的分析

ＢＹＳ９１－１是基于ＲＩＳＣｉ８６０ＸＰ设计的具有局部存储和共享存储的多机系统。本文以排队论为工具，建立了该系统存储器的排队模型，给出了存储器使用频带的解析式，并结合具体的设计参数，分析了系统中处理机个数、存储空间配置对存储器有效频带的影响。     

具有服务质量保障的片上网络路由仲裁控制

片上网络(Network on Chip,NoC)通过仲裁机制控制各个端口间的数据交换。经典的RR(Round-Robin)算法保障了各端口间的公平性,但却难以为时延敏感业务提供具有低数据交换等待时延的QoS保障。为此,提出一种区分优先级并行调度RR(PP-RR)算法,其根据端口数据负载提供区分优先级服务,高优先级端口数据享有更多仲裁成功机会。采用并行调度两级轮控制模型实现了对PP-RR仲裁算法的数学建模,获得了时延性能的数学解析。     

分组交换网络中分布式调度控制算法研究

文章首先对目前分组交换网络中支持QoS的队列调度算法进行了比较研究,分析了其性能指标和技术特点。然后以Internet核心路由器中线卡级和交换级的队列调度设计为例,从控制论的角度提出了一种支持QoS的分布式加权轮询调度控制算法,同时对交换网络进行了仿真实验,吞吐率达到96％的仿真实验结果表明所提出的算法是有效的,最后,文章认为在实际应用中,应针对不同情况设计不同的调度控制算法,以便在复杂性、公平性、快速性及有效性等特性方面取得了一个折衷方案,以使分组交换网络的整体性能更好。     

Internal Scheduling and Memory Contention

It has been suggested that the algorithm used to schedule those processes active and in main memory can have an effect on memory contention. We create models for memory contention in a system that uses global LRU replacement and either round robin or priority internal scheduling. Parameters to our model include the ratio of secondary storage to primary storage access times, thus allowing consideration of a variety of storage technologies. The round robin quantum size is included and is shown to have some effect. Our model uses LRU miss ratio curves and thus reflects actual program characteristics. Trace driven simulations are used to verify the accuracy of the models. We find that in most cases internal scheduling has only a small effect on page fault rates and CPU utilization. In certain cases, however priority scheduling is found to besignificant in relieving thrashing.     

顺序分布式变长分组调度算法:SDMCRR

通过引入分布式思想对CRR调度算法进行改进,提出了一种基于输入排队VOQ结构的输入端口轮转和输出端口轮询的顺序分布式改进补偿轮询调度算法SDMCRR。并通过分析以及和其它轮询算法的比较,得出该算法具有单个报文调度O（1）的复杂度、较好的隔离恶意流的公平性和时延特性。     

Achieving fair service with a hybrid scheduling scheme for CICQ switches

Providing performance guarantees for arriving traffic flows has become an important measure for today’s routing and switching systems. However, none of current scheduling algorithms built on CICQ (combined input and cross-point buffered) switches can provide flow level performance guarantees. Aiming at meeting this requirement, the feasibility of implementing flow level scheduling is discussed thoroughly. Then, based on the discussion, it comes up with a hybrid and stratified fair scheduling (HSFS) scheme, which is hierarchical and hybrid, for CICQ switches. With HSFS, each input port and output port can schedule variable length packets independently with a complexity of O(1). Theoretical analysis show that HSFS can provide delay bound, service rate and fair performance guarantees without speedup. Finally, we implement HSFS in SPES (switch performance evaluation system) to verify the analytical results.     

支持公平服务的CICQ分层混合调度策略

为到达业务提供性能保障是衡量一个交换系统性能的重要参考.针对现有联合输入交叉点排队交换结构(CICQ)调度策略缺乏基于流的服务质量保障,探讨了在CICQ交换结构实施基于"流"调度的可能性,提出了一种能够为到达业务流的提供公平服务的分层混合调度策略(HSFS).HSFS采用分层的混合调度机制,每个输入、输出端口可独立地进行变长分组交换,其复杂度为O(1),具有良好可扩展特性.理论分析结果表明,HSFS无需加速便能为到达业务提供时延上限、速率和公平性保障.最后,基于SPES对HSFS的性能进行了评估.     

On the Integration of Unicast and Multicast Cell Scheduling in Buffered Crossbar Switches

Internet traffic is a mixture of unicast and multicast flows. Integrated schedulers capable of dealing with both traffic types have been designed mainly for Input Queued (IQ) buffer-less crossbar switches. Combined Input and crossbar queued (CICQ) switches, on the other hand, are known to have better performance than their buffer-less predecessors due to their potential in simplifying the scheduling and improving the switching performance. The design of integrated schedulers in CICQ switches has thus far been neglected. In this paper, we propose a novel CICQ architecture that supports both unicast and multicast traffic along with its appropriate scheduling. In particular, we propose an integrated round-robin-based scheduler that efficiently services both unicast and multicast traffic simultaneously. Our scheme, named multicast and unicast round robin scheduling (MURS), has been shown to outperform all existing schemes under various traffic patterns. Simulation results suggested that we can trade the size of the internal buffers for the number of input multicast queues. We further propose a hardware implementation of our algorithm for a 16 times 16 buffered crossbar switch. The implementation results suggest that MURS can run at 20 Gbps line rate and a clock cycle time of 2.8 ns, reaching an aggregate switching bandwidth of 320 Gbps.     

一种适合实时变比特率视频传输的IP区分服务调度算法

在建立的区分服务网络模型的基础上，提出一种针对实时变比特率突发业务的调度算法，称为加权开关赤字轮循(weighted switch deficit round robin，WSDRR)算法．根据不同的队列等级分配加权的带宽，并根据队列中分组状况动态调节服务量．该策略是针对网络拥塞下传输实时突发视频业务而提出的．基于一种吞吐量公平测度的比较，WSDRR算法与传统赤字轮循DRR算法具备相同的公平性．实验结果表明，与DRR算法相比，WSDRR算法能够降低实时突发视频业务的端对端延时和延时抖动，从而进一步使实时视频传输的要求得到满足．     

一种支持DiffServ模型的全分布式调度算法

调度算法设计对于网络路由设备实现区分服务(DiffServ)模型的单跳行为(per hop behavior,简称PHB)至关重要.现有支持DiffServ模型的调度算法普遍基于输出排队(output queued,简称OQ)或是输入排队(input queued,简称IQ)交换结构进行设计,均无法在高速环境下提供高性能的调度.基于联合输入/交叉节点排队(combinedinput-crosspoint-queued,简称CICQ)交换结构提出一种支持DiffServ模型的全分布式调度算法DDSS (distributed DiffServ supporting scheduling),并通过理论分析对其公平性进行了验证.DDSS算法采用基于预约带宽的逐级流量控制机制实现所有预约带宽在快速转发(expedited forwarding,简称EF)业务与确保转发(assured forwarding,简称AF)业务之间的分配,采用优先级调度机制为EF业务提供低延迟服务,算法复杂度为O(log N).仿真结果表明,DDSS算法具有良好的时延性能和公平特性,与现有算法相比,能够更好地支持DiffServ模型.     

PowerTrust: A Robust and Scalable Reputation System for Trusted Peer-to-Peer Computing

We propose a new fair scheduling technique, called OCGRR (output controlled grant-based round robin), for the support of DiffServ traffic in a core router. We define a stream to be the same-class packets from a given immediate upstream router destined to an output port of the core router. At each output port, streams may be isolated in separate buffers before being scheduled in a frame. The sequence of traffic transmission in a frame starts from higher-priority traffic and goes down to lower-priority traffic. A frame may have a number of small rounds for each class. Each stream within a class can transmit a number of packets in the frame based on its available grant, but only one packet per small round, thus reducing the intertransmission time from the same stream and achieving a smaller jitter and startup latency. The grant can be adjusted in a way to prevent the starvation of lower priority classes. We also verify and demonstrate the good performance of our scheduler by simulation and comparison with other algorithms in terms of queuing delay, jitter, and start-up latency