WRR算法在多类别实时数据流调度中的优化

随着融合型网络的发展,服务质量(包括可用带宽、端到端的时延、抖动和丢包率)对一些实时数据流应用(语音流、视频流等)越来越重要。由于传统的WRR算法只能满足各个应用队列的公平性要求,而不能保证多类别实时数据的低时延和低抖动性要求,所以本文在WRR算法的基础上提出了BSTL-RR调度算法,此算法运用了二层循环和借用时隙的两个思想。BSTLRR调度算法不仅在调度低时延和低抖动的多类别实时数据流帧方面要优于WRR调度算法,而且在一定程度上也保证了各优先级队列调度上的公平性。     

层次网络中基于跳数区分的任意汇聚算法

从服务质量的实现来看,任意汇聚具有良好的延迟性能和扩展性,层次网络是有规则的网络拓扑,相比平面网络为任意汇聚的方法提供了更多的优势条件.通过建立任意汇聚的数学模型,分析了在层次网络体系结构中在一定的网络利用率条件下任意汇聚的最坏延迟约束,提出了一种基于跳数区分的任意汇聚调度算法.最后进行了实验分析,结果表明该方法能有效的改善任意汇聚的最坏延迟性能.     

一种基于PID的实时控制与调度协同设计方法

针对实时控制领域中由于资源共享引起的控制系统性能下降问题，提出一种对延迟和抖动进行补偿的协同设计方法．讨论了协同设计中的周期分配问题，对一些变结构任务或混杂任务，采用任务周期动态调整的方法以适应其最坏执行时间的变化，并通过查询宏周期实例表，改进PID算法对延迟和抖动进行补偿．     

无线网络中基于WRR的实时业务调度算法

在WRR(WeightedRoundRobin,带权重的循环)算法的基础上,提出了一种适应无线局 域网特点的实时业务的调度算法。该算法工作在数据链路层,和无线局域网的介质访问控制(MAC) 层协议DCF(DistributedCoordinateFunction)紧密结合,有效避免了对列头部阻塞问题,提高了信道利 用率。通过采用补偿机制,近似达到了长期公平性。使用NS(NetworkSimulator)仿真进行性能评价, 结果表明该算法能有效提高实时业务的端端吞吐率,降低端端延迟和丢包率,延迟抖动也较小,可以 在一定程度上保证实时业务的服务质量。     

应用感知的容器资源调度优化方法

资源调度作为容器管理的关键技术之一,已有研究工作或满足公平性目标,将工作负载平均调度到所有物理节点上,关注吞吐率指标;或满足性能目标,将工作负载关联的多个容器载体调度到相同或相近的物理节点上,关注响应时间.提出应用感知的容器资源调度方法,采用多队列模型兼顾公平性和性能目标.实验结果显示,对于典型的大数据处理场景,本方法和已有公平性调度方法具有相当的吞吐率;对于典型的事务型应用场景,本方法相对于已有的公平性调度方法,事务型应用的延迟最多可减少100%.     

面向运动控制的调度抖动问题的研究

通用处理器以其优异的性能已经越来越广泛地应用到实时控制系统中，但其所采用的体系结构会引起指令执行时间的不确定性，导致基于它的实时系统存在调度抖动问题,调度抖动是实时控制系统的重要性能指标之一，本文讨论了抖动测试和分析技术，并介绍了减少抖动的补偿技术．     

一种提供延迟保证的多级FIFS队列包调度算法

包调度算法是提供服务质量保证的一个重要部分.传统的每流区分的包调度方法通常不能支持较好的扩展性,不适应当前网络带宽的迅速增长.而非每流区分的方法又不能提供每流的服务保证.动态包状态(dynamic packet state,简称DPS)方法提供了一种在无须维护每流状态下提供保证服务的方法,该方法在保证服务质量的同时大大提高了扩展性.但是它仍然需要每包的调度,其复杂度和包的数量有关.在DPS的基础上提出了一种用多级FIFS队列提供延迟保证的包调度算法,并给出了该算法实现服务保证的约束条件.理论分析和仿真实验结果都表明:该算法可以实现常数时间的包调度复杂性,同时具有和DPS同样的延迟性能.     

实时控制系统中固定优先级调度的延迟与抖动控制

在基于固定优先级调度实时控制系统中,任务的延迟与抖动是影响系统稳定性的重要因素,提出一种基于可抢占时间阈值的延迟与抖动控制策略,给出一种保证系统可调度的最优闽值分配算法,并通过对任务延迟和抖动的分析量化出阀值分配后的争最大可能IO延迟及抖动.最后通过仿真实验验证了该策略的有效性.     

一种基于双令牌的蓝牙调度算法

调度算法是短距离无线通信技术的主要问题。蓝牙网络中使用的Round Robin (RR)轮询调度算法严重影响了系统的性能，本文针对这个问题提出了一种改进的蓝牙调度算法——双令牌随机(DTPR)轮询算法．此算法有两个重要特点：一是访问采用随机次序解决从设备之间的不公平性；二是采用优先级调度策略，对拥有令牌的主从设备对进行调度，缩短了轮询周期。并对本文提出的算法与现已提出的算法进行了仿真实验，结果表明，本文提出的算法在系统的吞吐量、传输时延和公平性方面都优于现有的其它算法。     

网络磁盘阵列流水调度研究

存储系统采用流水处理技术有两个前提条件：(1)在前一个I／O命令没有完全结束之前，系统能获取下一个I／O命令的有关信息；(2)不同部件应能同时操作，资源不发生冲突．网络磁盘阵列满足这两个条件，可以在I／O调度过程中采用流水处理技术．根据I／O调度进程的重叠度，流水调度方式可以分为固定流水方式和柔性流水方式．在固定流水方式中，多进程按照固定的重叠方式执行；而在柔性流水方式中，则通过判断进程的完成顺序，在一定程度上自由组合多个进程进行重叠．实验结果证明，在多用户进程的条件下，两种流水调度方式都能提高网络磁盘阵列的带宽利用率．     

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

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

Tight end-to-end per-flow delay bounds in FIFO multiplexing sink-tree networks

Aggregate scheduling has been proposed as a solution for achieving scalability in large-size networks. However, in order to enable the provisioning of real-time services, such as video delivery or voice conversations, in aggregate scheduling networks, end-to-end delay bounds for single flows are required. In this paper, we derive per-flow end-to-end delay bounds in aggregate scheduling networks in which per-egress (or sink-tree) aggregation is in place, and flows traffic is aggregated according to a FIFO policy. The derivation process is based on Network Calculus, which is suitably extended to this purpose. We show that the bound is tight by deriving the scenario in which it is attained. A tight delay bound can be employed for a variety of purposes: for example, devising optimal aggregation criteria and rate provisioning policies based on pre-specified flow delay bounds.     

基于加权路径的指令调度算法

随着线延迟的逐渐增加,指令调度技术作为一种可以有效减少处理器片上通信的技术日益重要。本文介绍一种分片式处理器结构上基于加权路径的指令调度算法,该算法利用已经放置好的指令——锚指令信息精确计算路径长度,再用指令所在路径长度作为权值对指令进行调度。实验结果表明,本算法实现的调度器IPC比已有的两种TRIPS调度算法的IPC分别提高了21%和3%。     

调度算法在节点延时PMF正态化条件下的延时分析

若假设网络带宽足够大,可以将网络传输的QoS保证表示为以网络延时保证为前提,以丢包率为判决条件.本文分析网络现有调度算法对网络业务延时的影响,选择节点状态延时的概率函数（PMF）表示网络节点状态的统计信息.并利用其PMF的正态形式作为网络节点状态信息,分析调度算法的延时性能.通过仿真验证,当节点延时的PMF分布近似正态,即如果网络业务经过整形后以近似正态延时概率到达网络节点,业务在节点经过调度算法输出时其PMF仍近似保持正态分布形式.仿真分析了这种情况下各调度算法的延时表现,得到EDF算法在这种情况下延时随节点级数增加的特性最好.     

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

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

一种适用突发流量的数据中心网络流调度策略

云数据中心网络的流调度问题是当下的一个研究热点.比较具有实用性的流调度是不假设流信息预先可知,但目前这类流调度方案在流量突发时的表现并不理想.提出了一种针对流量突发情况的流调度方案,通过将每流排队与多级反馈队列调度相结合,实现了一个基于流隔离的多级调度方案FISH,解决了流量突发情况下不同流的排队竞争问题.实验结果表明,该方案性能稳定,可以将小流完成时间降低8.6%以上.     

Scheduling analysis with martingales

This paper proposes a new characterization of queueing systems by bounding a suitable exponential transform with a martingale. The constructed martingale is quite versatile in the sense that it captures queueing systems with Markovian and autoregressive arrivals in a unified manner; the second class is particularly relevant due to Wold’s decomposition of stationary processes. Moreover, using the framework of stochastic network calculus, the martingales allow for a simple handling of typical queueing operations: (1) flows’ multiplexing translates into multiplying the corresponding martingales, and (2) scheduling translates into time-shifting the martingales. The emerging calculus is applied to estimate the per-flow delay for FIFO, SP, and EDF scheduling. Unlike state-of-the-art results, our bounds capture a fundamental exponential leading constant in the number of multiplexed flows, and additionally are numerically tight.     

多媒体服务器混合磁盘调度策略

基于多媒体服务器的性能要求，提出了一种自适应的混合磁盘调度策略DRT-window．它既能满足实时请求对实时性的要求，根据实时请求的截止期动态选择窗口大小；又能在其松弛度内尽努力(best-effort)地服务非实时请求，从而减少非实时请求的响应时间。DRT-window采用了两级层次调度方案：第一层为不同类型的请求采用各自适合的调度策略；第二层为混合请求调度嚣，混合调度第一层中的不同类型的请求。通过性能比较和理论证明，表明此混合磁盘调度策略能在保证实时请求无抖动执行的同时，尽量地减少非实时请求的响应时间。