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.     

Internet中的包延迟分布与包丢失关系研究

包延迟的分布特征是Internet端到端行为特征的一个重要组成部分，前人已在该方面进行了大量研究，但许多研究结论只适用于丢包率较小的情况，通过研究我国科技网和教育网上34条端到端路径上的延迟特征，得出了如下结论：（1）包延迟的分布特征与丢包率存在一定的关系；（2）在丢包率较小的情况下，包延迟的分布多具有单峰性，但随着丢包率的增大，包延迟的分布不再具有单峰性，而是呈现出越来越分散的特点；（3）随着丢包率的增大，固有延迟的发生次数呈现逐渐减少的趋势，当丢包率增大到一定程度，固有延迟的发生次数就很少了。     

Queuing network models of packet switching networks part 1: Open networks

An overview of the application of product-form queuing network models to the performance analysis of store-and-forward packet-switching networks is presented. Multiple routing chains are used to model the different routing behaviors of data packets. Queuing networks with open chains are considered in this paper. Kleinrock's formula for the mean end-to-end delay of packets is first derived. The application of this delay formula to optimal channel capacity assignment and optimal routing is discussed. Analytic results for the mean and distribution of the end-to-end delay of each chair are presented. The issue of fairness among chains is also addressed.The application of queuing networks with closed chains and population size constraints to the performance analysis of store-and-forward packet-switching networks is illustrated in a companion paper [1].     

WDM网络中满足延迟和延迟差约束的分布式组播路由与波长分配算法

在WDM网络中,由于每条链路上可用波长是动态变化的,在考虑波长转换延迟时间的条件下,实现实时组播连接的路由与波长分配是十分困难的。论文提出了一种用于建立满足延迟时限和延迟差要求的实时组播连接的分布式路由与波长分配算法。该算法假定每个节点没有全局路由信息,只根据关联链路的信息进行路由选择,且将路由与波长分配统一进行。组播路由算法以Prim最小生成树算法为基础,生成一棵满足给定延迟时限的最小成本树。对不满足延迟时限的目的节点,通过增加回路边构造回路再消除长延迟路径的方式,加入到组播树中。对不满足延迟差的目的节点,采用重构Steiner树的方法,使其满足延迟差的要求。波长分配使用最少波长转换和负载平衡策略。     

VOIP动态缓出时延算法研究分析

在以包为单位进行数据传输合、语音应用程序(VOIP,Voice Over Internet Protocol)中,为了补偿数据包在网络传输中不可预知的网络传输延迟,在接收端首先必须把接收到的数据包缓存起来,缓存一定的时间再播放出来,以减少通话的抖动,得到比较满意的通话质量。文章主要研究动态缓出时延算法,力求使这个缓出时延尽可能小,同时尽可能减少包的丢失率。文章提出了一个有效动态缓出时延算法,该算法主要跟踪最近到达的数据包的网络传输时延求出其近似分布函数,并利用这些信息和延迟峰的侦测算法预测下一个语音峰的缓出时延。实验结果表明利用该算法可以在缓出时延和包丢失率之间达到最佳平衡,是一种理想、有效的算法。     

宏移动协议和微移动协议中包丢失率的比较

移动IP是支持IP移动性的协议,但是当其用于移动节点驻留在远离归属网络的外地网络时,将会产生严重的注册延迟,从而引起严重的包丢失和通信吞吐量的下降,为了改变这些不足,人们把移动节点的移动方式分为宏移动和微移动,并且提出了很多应用于微移动的移动性管理方案。文章深入研究了宏移动协议(RFC2002)和微移动协议的包丢失率,给出了计算公式,并且对计算结果进行了详细的分析。     

数据包时延及控制策略的研究

许多网络应用使用TCP协议,为了能够获得可靠的数据传送服务,作为开发人员除了关心可靠性外,还要考虑拥塞控制的问题,本文中提到的拥塞控制窗口,能够实现数据速率的控制。TCP协议采用慢启动和拥塞避免策略实现端到端的数据传送。     

TSLBS: A Time-Sensitive and Load Balanced Scheduling Approach to Wireless Sensor Actor Networks

Existing works on scheduling in Wireless Sensor Actor Networks (WSANs) are mostly concerned with energy savings and ignore time constraints and thus increase the make-span of the network. Moreover, these algorithms usually do not consider balance of workloads on the actor nodes and hence, sometimes some of the actors are busy when some others are idle. These problem causes the actors are not utilized properly and the actors’ lifetime is reduced. In this paper we take both time awareness and balance of workloads on the actor in WSANs into account and propose a convex optimization model (TAMMs) to minimize make-span. We also propose a protocol called LIBP to improve load balancing that allocates tasks to actors according to their measured capabilities in such a way to enhance balances of workloads on the actors. Finally, by combination of TAMMs and LIBP, a time-sensitive and load balanced scheduling approach (TSLBS) is proposed. TSLBS considers both local and global tasks and the distribution requirements of WSANs (i.e. WSANs with hybrid architecture). The results of simulations on typical scenarios shows that TSLBs is more efficient in terms of both the make-span and load balancing compared to stochastic task scheduling algorithm (STSA). We also show that TSLBs performs significantly better than STSA in terms of actor’s lifetime.     

On-Line Resource Management with Application to Routing and Scheduling

We propose a framework to model on-line resource management problems based on an on-line version of positive linear programming. We consider both min cost problems and max benefit problems and propose logarithmic competitive algorithms that are optimal up to a constant factor. The proposed framework provides a general methodology that applies to a wide class of on-line problems: shop scheduling, packet routing, and in general a class of packing and assignment problems. Previously studied problems as on-line multiprocessor scheduling and on-line virtual circuit routing can also be modeled within this framework. Received December 18, 1996; revised March 2, 1997.     

用遗传算法解带时延及时延抖动约束的组播路由优化问题

带约束条件的组播路由是网络应用的发展所提出的新的问题,根据不同的约束条件有不同的变种,该文讨论了带时延及时延抖动约束的组播路由优化问题,给出了该问题的数学模型,提出了求解该问题的一种基于候选路由库的遗传算法,并对该算法的仿真结果与前人的结果进行了比较。结果证明,用遗传算法解决这类问题是有效的。     

基于弹性定额值的分组轮询调度算法

提出了一种新的适用于变长分组的调度算法——弹性定额值轮询调度算法(Resilient Quantum Round Robin,RQRR),与现有算法不同,该算法中每个数据流的定额值不是固定不变的,定额值的生成依赖于前一个轮次中各个数据流的发送情况。理论分析表明,RQRR可以保证数据流之间具有较好的公平性,它的公平性度量具有上界值7Max-1,其中Max为分组的最大长度。RQRR对每个分组的处理复杂度为O(1),易于实现、适用于高速网络。     

异构集群环境下负载平衡调度算法研究与实现

围绕平衡负载这一目标,针对进程级并行任务的动态调度问题进行了研究,提出了一个异构集群环境下动态负载平衡算法,它结合了自适应数据采集与交换算法,有效的解决了服务器之间负载不平衡的问题,提高了系统的吞吐率。     

Gnutella协议及数据包结构分析

结合作者参与的相关课题研究工作,在调研国内外相关研究的基础上,该文对Gnutella的协议及数据包结构进行了分析和归纳,可为进一步研究Gnutella类软件的运行机制提供借鉴和帮助。     

网络QoS的分组调度算法仿真研究

随着Internet的不断发展,实时数据的应用对网络提出了更高的服务质量控制要求,分组调度是实现网络服务质量控制的核心技术之一.分组调度按照一定的规则决定队列中分组的发送次序并分配共享链路带宽.文中介绍了一种先进的分组调度和资源管理模型:链路共享模型, 以及两种不同的实现算法:CBQ和HPFQ,分析了它们用于传输实时流的可行性.HPFQ算法为实时数据提供了严格的时延保证和完全意义上的等级链路共享服务.文中使用网络仿真工具NS2,对链路共享模型下实时流传输的服务质量性能进行了仿真分析.     

Improved Bounds for On-Line Load Balancing

We consider the following load balancing problem. Jobs arrive on-line and must be assigned to one of m machines thereby increasing the load on that machine by a certain weight. Jobs also depart on-line. The goal is to minimize the maximum load on any machine, the load being defined as the sum of the weights of the jobs assigned to the machine divided by the machine capacity. The scheduler also has the option of preempting a job and reassigning it to another machine. Whenever a job is assigned or reassigned to a machine, the on-line algorithm incurs a reassignment cost depending on the job. For arbitrary reassignment costs and identical machines, we present an on-line algorithm with a competitive ratio of 3.5981 against current load , i.e., the maximum load at any time is less than 3.5981 times the lowest achievable load at that time. Our algorithm also incurs a reassignment cost less than 6.8285 times the cost of assigning all the jobs. For arbitrary reassignment costs and related machines we present an algorithm with a competitive ratio of 32 and a reassignment factor of 79.4. We also describe algorithms with better performance guarantees for some special cases of the problem. Received August 24, 1996; revised August 6, 1997.     

基于集群的负载平衡调度算法研究与实现

在集群系统的负载调度研究中,针对请求的服务时间变化大的特点,该文提出了一个动态反馈负载平衡算法,它结合内核中的加权连接调度算法,根据动态反馈回来的负载信息来调整服务器的权值,从而有效地解决服务器问的负载不平衡问题,提高了系统的吞吐率。     

Ancient and New Algorithms for Load Balancing in the l p Norm

We consider the on-line load balancing problem where there are m identical machines (servers) and a sequence of jobs. The jobs arrive one by one and should be assigned to one of the machines in an on-line fashion. The goal is to minimize the sum (over all machines) of the squares of the loads, instead of the traditional maximum load. We show that for the sum of the squares the greedy algorithm performs within 4/3 of the optimum, and no on-line algorithm achieves a better competitive ratio. Interestingly, we show that the performance of Greedy is not monotone in the number of machines. More specifically, the competitive ratio is 4/3 for any number of machines divisible by 3 but strictly less than 4/3 in all the other cases (although it approaches 4/3 for a large number of machines). To prove that Greedy is optimal, we show a lower bound of 4/3 for any algorithm for three machines. Surprisingly, we provide a new on-line algorithm that performs within 4/3 -δ of the optimum, for some fixed δ>0 , for any sufficiently large number of machines. This implies that the asymptotic competitive ratio of our new algorithm is strictly better than the competitive ratio of any possible on-line algorithm. Such phenomena is not known to occur for the classic maximum load problem. Minimizing the sum of the squares is equivalent to minimizing the load vector with respect to the l ₂ norm. We extend our techniques and analyze the exact competitive ratio of Greedy with respect to the l _p norm. This ratio turns out to be 2 - Θ(( ln p)/p) . We show that Greedy is optimal for two machines but design an algorithm whose asymptotic competitive ratio is better than the ratio of Greedy. Received January 2, 1998; revised December 12, 1998.     

一个有效的延迟费用受限的多路径算法

在集成网络中,服务质量(QoS)的一个重要方面是寻找满足端到端约束的可行路径,从而有效利用网络资源。考虑端到端的延迟约束和传输费用,对宽度优先算法(BFS)进行扩展,提出了满足延迟约束多路径算法K_DCP,并对其进行改进,得到多路径算法K_EDCP。仿真结果显示,两种算法性能良好。     

A new step toward load balancing based on competency rank and transitional phases in Grid networks

Grid computing is a network of software-hardware capabilities. It serves as a comprehensive and complete system for organizations by which the maximum utilization from resources is achieved. Resource distribution in a heterogeneous and unstable environment and also effective load distribution among these resources are the important and difficult problems in Grid networks. Using dynamic and static algorithms or searching tree and Branch and Bound algorithm are considered to be among the available methods to reach the load balancing in Grid networks. This paper presents a new method for dynamic load balancing. In this method, we use the subtraction of forward and backward ants as a competency rank to take the priority of the sites, and we use a control word to search the suitable resource as well. Our main purpose is to devote jobs to the existing resources based on their processing power. Simulation results show that the proposed method can reduce the total completion time and also total tardiness to get the load balancing. The cost of using resources as an effective factor in load balancing is also observed.     

Subjective Quality of Speech Over Packet Networks as a Function of Packet Loss, Delay and Delay Variation

An expanding proportion of voice traffic is being carried by packet networks. Speech quality can be impaired in qualitatively new ways in packet networks when packets are lost or the spacing between them is distorted. Three parameters that characterize the performance of packet networks were examined for their relative impact on speech quality as judged by human observers: network delay or latency, packet loss, and packet delay variation or jitter. We manipulated these variables via a network emulator made available by NIST. This report summarizes five laboratory experiments that examined the variables in a variety of experimental procedures for presenting and judging speech. The experiments agreed in showing that the relative importance of the variables for affecting speech quality was, in decreasing order: packet loss, jitter, delay. The effect on speech quality of 200 ms of network delay was shown to be equivalent to the effect of one percentage point of packet loss. Many consumers also traded off some speech quality for a free, added feature, unified messaging.