Multicast Pull Scheduling: When Fairness Is Fine

Abstract. We investigate server scheduling policies to minimize average user perceived latency in pull-based client-server systems (systems where multiple clients request data from a server) where the server answers requests on a multicast/ broadcast channel. We first show that there is no O(1) -competitive algorithm for this problem. We then give a method to convert any nonclairvoyant unicast scheduling algorithm A to nonclairvoyant multicast scheduling algorithm B . We show that if A works well, when jobs can have parallel and sequential phases, then B works well if it is given twice the resources. More formally, if A is an s -speed c -approximation unicast algorithm, then its counterpart algorithm B is a 2s -speed c -approximation multicast algorithm. It is already known [5] that Equi-partition, which devotes an equal amount of processing power to each job, is a (2 + ε) -speed O(1 + 1/ε) -approximation algorithm for unicast scheduling of such jobs. Hence, it follows that the algorithm {BEQUI}, which broadcasts all requested files at a rate proportional to the number of outstanding requests for that file, is a (4 + ε) -speed O(1 + 1/ε) -approximation algorithm. We give another algorithm BEQUI-EDF and show that BEQUI-EDF is also a (4 + ε) -speed O(1 + 1/ε) -approximation algorithm. However, BEQUI-EDF has the advantage that the maximum number of preemptions is linear in the number of requests, and the advantage that no preemptions occur if the data items have unit size.     

A Comparison of Multicast Pull Models

We consider the setting of a web server that receives requests for documents from clients, and returns the requested documents over a multicast/broadcast channel. We compare the quality of service (QoS) obtainable by optimal schedules under various models of the capabilities of the server and the clients to send and receive segments of a document out of order. We show that allowing the server to send segments out of order does not improve any reasonable QoS measure. However, the ability of the clients to receive data out of order can drastically improve the achievable QoS under some, but not all, reasonable/common QoS measures.     

一种联合单播组播的全分布式调度方案

随着网络中组播业务比例的不断增长,交换结构及其调度策略必须能够为组播业务提供良好的支持.本文结合交换结构领域新的研究进展,基于带缓存交叉开关交换单元提出一种联合单播组播的全分布式调度方案DCUM.该方案利用交叉节点缓存的分布特性实现无需加速的组播复制,并通过支持组播加权因子的全分布式调度算法可同时支持单播业务与组播业务的调度.与传统组播调度方案相比,该方案结构简单,调度算法复杂度仅为O(log N),十分便于硬件实现.仿真结果表明,采用DCUM方案可获得良好的调度性能.     

基于调度集合的多播单播数据联合调度算法

首先定义和分析了IEEE802.16e无线城域网中的一个新问题,即如何在保证移动终端服务质量的前提下,通过合理地调度终端的单播业务和多播业务来降低终端能耗.针对该问题,提出一种基于调度集合的联合调度算法(scheduling set based integrated scheduling,简称SSBIS).SSBIS算法将所有移动终端划分到多播调度集合或单播调度集合中,并利用多播数据的传输特点,在多播数据传输的相邻时隙内发送多播调度集合中所有终端的单播数据,而对于单播调度集合中的终端,则通过凸优化方法求得使终端休眠时间最长的单播业务调度方案,以达到降低终端能耗的目的.仿真实验显示,SSBIS算法在满足移动终端的最小数据速率要求的同时,可以明显地降低终端能耗.     

应用层组播节点流媒体调度算法

针对终端转发机制存在的延迟问题和传输率波动问题,提出一种应用层组播节点流媒体调度算法,通过采用组播节点的缓冲延迟和视频编码预测信息,减弱流视频的突发性高带宽需求,从而实现实时流率平滑传输,以提供稳定的流视频服务。仿真实验结果表明,该算法是有效可行的。     

考虑公平和护士偏好的护士排班研究

针对护士排班问题涉及护士满意度的特点，在护士排班过程中加入护士偏好和公平的约束，寻求最优的排班表以增加护士的满意度。根据多目标问题的特点，采用粒子群多目标优化算法。在硬约束条件上，加入N班之后不能上A班和P班的约束，使护士在上N班之后能够得到足够的休息。在算法设计上，加入变异算子，扩大了粒子群的搜索空间。由于各优化目标之间存在一定的矛盾，用多目标决策理论可以更加科学客观地优化护士排班表。在最后的案例分析中，发现护士不同的偏好会产生不同的非劣解，因此在实际排班中，要充分考虑护士的偏好，以求出更加科学合理的排班表。     

Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness

In current networks, packet losses can occur if routers do not provide sufficiently large buffers. This paper studies how many buffers should be provided in a router to eliminate packet losses. We assume a network router has m incoming queues, each corresponding to a single traffic stream, and must schedule at any time on-line from which queue to take the next packet to send out. To exclude packet losses with a small amount of buffers, the maximum queue length must be kept low over the entire scheduling period. We call this new on-line problem the balanced scheduling problem (BSP). By competitive analysis, we measure the power of on-line scheduling algorithms to prevent packet losses. We show that a simple greedy algorithm is Θ(log m)-competitive which is asymptotically optimal, while Round-Robin scheduling is not better than m-competitive, as actually is any deterministic on-line algorithm for BSP. We also give a polynomial time algorithm for solving off-line BSP optimally. We also study another on-line balancing problem that tries to balance the delay among the m traffic streams.     

Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness

In current networks, packet losses can occur if routers do not provide sufficiently large buffers. This paper studies how many buffers should be provided in a router to eliminate packet losses. We assume a network router has m incoming queues, each corresponding to a single traffic stream, and must schedule at any time on-line from which queue to take the next packet to send out. To exclude packet losses with a small amount of buffers, the maximum queue length must be kept low over the entire scheduling period. We call this new on-line problem the balanced scheduling problem (BSP). By competitive analysis, we measure the power of on-line scheduling algorithms to prevent packet losses. We show that a simple greedy algorithm is (log m)-competitive which is asymptotically optimal, while Round-Robin scheduling is not better than m-competitive, as actually is any deterministic on-line algorithm for BSP. We also give a polynomial time algorithm for solving off-line BSP optimally. We also study another on-line balancing problem that tries to balance the delay among the m traffic streams.     

基于QoS的改进比例公平算法研究

提出了1种适用于无线网络的分组调度算法,该算法在原有比例公平算法的基础上,加入服务质量（QoS）的因素,在保证用户QoS的基础上,使系统容量最大化。通过分析研究,对比例公平算法以及改进算法同时进行了仿真。结果表明,改进比例公平算法在公平性上有所改善,然而在吞吐量方面有略微的损失。     

无线多跳网的一种端到端的最大最小公平调度算法

提出一种基于效用函数的分布式最大最小公平性调度算法及其跨层控制模型,算法针对无线多跳网中端到端的流,通过对偶规划以及拉格朗日松弛算法把问题分解成传输层和MAC层两个子问题,在传输层上采用基于最大价格的最大最小公平速率分配方案来交叉控制MAC层的调度,给出了跨层层控制模型.仿真结果表明该算法具有良好的公平性和调度性能.     

基于效用公平的多用户下行OFDM系统机会调度

基于对单信道系统中效用公平机会调度的研究,提出了一种多用户下行OFDM多载波系统中的调度方案.该方案充分利用信道的时变和频率选择特性,由参数更新和调度决策两个模块组成:参数更新模块根据调度结果更新控制参数;调度决策模块根据所有用户的信道信息和参数更新模块输出的公平性控制参数决定该时隙每个用户使用哪些子载波.仿真结果表明,参数选取合适时,所提的简单调度方案能够在保证效用公平性的前提下,达到比复杂的Max-Min子裁波分配算法更好的系统性能.     

认知无线电网络中QoS组播路由调度

在多跳认知无线电网络中,组播的信息通常要经由多个中间节点的转发才能到达最终的目的节点。现有的研究中已经有很多的组播路由协议,然而这些协议都是基于传统无线网络的,并不适合新型的认知无线电网络。本文解决的的问题是:在多跳无线网络中,给定一个具有QoS要求的组播请求,如何建立组播路由以及对路径节点进行传输调度,使得在满足QoS要求下整个传输过程的带宽消耗最小。本文提出了一个分布式的组播路由协议来解决该问题,该协议不仅实现了路由过程的建立,同时还完成了对节点传输过程的合理调度。实验结果证明本文的传输调度策略能有效地减少网络的带宽消耗,同时增加组播请求响应的成功率。     

一种优化时延的机会协同组播调度策略

无线组播面临的最大问题是各个用户信道状态的不均匀性和波动性,无法同时满足所有用户的服务质量需求。无线蜂窝通信系统中,为实现可靠组播,数据包不可避免地需要被重传多次,组播的时延也因此增加。本文我们首先分析了协同组播调度CMS策略的时延,并且推导了基于信道信息全知条件下的最小时延。另外,我们在部分信道信息未知条件下提出了一种机会协同组播策略来优化组播时延。仿真数据显示,我们提出的机会协同组播调度OCMS策略在时延性能上几乎达到了我们所分析的CMS策略的最小值而且明显优于其他调度策略。     

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

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

一种适合于多播和单播的集成调度算法

具有输入队列结构的路由器或交换机内部交换可以工作在线路速率上,适应了高速网络交换的要求,但现有输入队列调度方案将单播和多播流量分开考虑,使用不同的交换结构和调度算法,不适合网络中多播流和单播流并存的实际情况．该文提出一种不区分多播、单播分组,遵循同一入队策略和同一调度规则的集成调度算法EOPF、(Extented Oldest Port First)．仿真实验表明EOPF算法在各种多播和单播负载组成比例下始终保持高吞吐率,并能在全单播流量下达到100％吞吐率,适合于多播、单播混合存在的网络流量。     

ModelTalk: When Everything Is a Domain-Specific Language

Many see a great future for domain-specific software development. Yet, the path to fulfilling the potential of domain-specific languages on a large scale remains largely uncharted. This article presents ModelTalk, a model-driven framework for DSL-based development. ModelTalk can be used to produce a product line of commercial business support systems for the telecommunications industry.     

When Are Group Scheduling Tools Useful?

A geographically dispersed department at the MITRE Corporation participated in a field test of groupware tools. This paper documents the results of their use of a group scheduling tool, Meeting Maker Version 1.5. Research in the late 1980s showed that early group scheduling tools were not useful, in part because they only benefited some users and hence critical mass could not be attained. This study was undertaken to determine whether and how far the tools have evolved. Participants said that Meeting Maker made it easy to schedule meetings and maintain their calendars, and 90% wished to continue using it after the study was complete. Problems were noted when not everyone used or had access to the tool, and three generic solutions are discussed: capabilities that allow users to communicate with non-users, capabilities that allow users to stay connected, and lightweight methods of participation.     

实时多播流的弹性公平性和基于门限的拥塞控制策略

该文提出了关于实时IP多播流基于速率弹性的公平性定义，并结合有关多播组规模估计的机制和多播拥塞控制算法。实现了一种基于门限的实时多播业务的等级拥塞控制策略，使实时多播流在满足瞬态弹性公平性的同时，也基本满足稳态的比例公平性，并对此进行了仿真验证。     

FFCS:WiMAX Mesh网络中一种流公平集中式调度算法

在WiMAX Mesh集中式调度模式下,通常难以同时保证带宽分配的公平性和网络的吞吐量,从而造成拥塞或低吞吐量等问题.本文综合考虑公平性和空间重用性两个方面,提出基于流公平的WiMAX Mesh集中式调度模型,将调度问题归结为0-1非线性规划问题.由于非线性规划是一个NP难解问题,难以求出最优解,本文提出一种启发式调度算法FFCS,采用拉斯维加斯随机算法思想,将随机初始调度调换成较优调度,通过增加随机次数取优逼近最优解.仿真实验表明,FFCS在带宽分配的公平性上比两个典型调度算法LIF和MRF略有提高,当带宽请求较少时网络吞吐量分别比两个算法提高了12.2%和19.8%,带宽请求较多时可提高15.5%和21.6%.     

OFDMA中继系统中比例公平调度算法研究

研究网络资源调度优化问题,中继技术是发展网络的关键技术。传统的资源调度算法中,部分比例公平调度(PPF)与两跳比例公平调度(THPF)均有不足,PPF算法能获得较高的系统吞吐率,但不能保证用户的公平性,THPF算法则相反。为了解决系统同时获得吞吐率与用户公平性问题,根据THPF算法设计了一种基于最少好信道优先的两跳比例公平调度算法(S-THPF),通过优先给好信道较少的用户分配信道资源,从而保证尽可能多的用户获得最优的信道。仿真表明算法在提高系统吞吐率的同时能满足用户公平性要求。