A generalized processor sharing approach to flow control inintegrated services networks: the multiple node case

Worst-case bounds on delay and backlog are derived for leaky bucket constrained sessions in arbitrary topology networks of generalized processor sharing (GPS) servers. The inherent flexibility of the service discipline is exploited to analyze broad classes of networks. When only a subset of the sessions are leaky bucket constrained, we give succinct per-session bounds that are independent of the behavior of the other sessions and also of the network topology. However, these bounds are only shown to hold for each session that is guaranteed a backlog clearing rate that exceeds the token arrival rate of its leaky bucket. A much broader class of networks, called consistent relative session treatment (CRST) networks is analyzed for the case in which all of the sessions are leaky bucket constrained. First, an algorithm is presented that characterizes the internal traffic in terms of average rate and burstiness, and it is shown that all CRST networks are stable. Next, a method is presented that yields bounds on session delay and backlog given this internal traffic characterization. The links of a route are treated collectively, yielding tighter bounds than those that result from adding the worst-case delays (backlogs) at each of the links in the route. The bounds on delay and backlog for each session are efficiently computed from a universal service curve, and it is shown that these bounds are achieved by “staggered” greedy regimes when an independent sessions relaxation holds. Propagation delay is also incorporated into the model. Finally, the analysis of arbitrary topology GPS networks is related to Packet GPS networks (PGPS). The PGPS scheme was first proposed by Demers, Shenker and Keshav (1991) under the name of weighted fair queueing. For small packet sizes, the behavior of the two schemes is seen to be virtually identical, and the effectiveness of PGPS in guaranteeing worst-case session delay is demonstrated under certain assignments     

Optimal call admission control on a single link with a GPS scheduler

The problem of call admission control (CAC) is considered for leaky bucket constrained sessions with deterministic service guarantees (zero loss and finite delay bound) served by a generalized processor sharing scheduler at a single node in the presence of best effort traffic. Based on an optimization process, a CAC algorithm capable of determining the (unique) optimal solution is derived. The derived algorithm is also applicable, under a slight modification, in a system where the best effort traffic is absent and is capable of guaranteeing that if it does not find a solution to the CAC problem, then a solution does not exist. The numerical results indicate that the CAC algorithm can achieve a significant improvement on bandwidth utilization as compared to a (deterministic) effective bandwidth-based CAC scheme.     

Latency-rate servers: a general model for analysis of trafficscheduling algorithms

We develop a general model, called latency-rate servers (ℒℛ servers), for the analysis of traffic scheduling algorithms in broadband packet networks. The behavior of an ℒℛ server is determined by two parameters-the latency and the allocated rate. Several well-known scheduling algorithms, such as weighted fair queueing, virtualclock, self-clocked fair queueing, weighted round robin, and deficit round robin, belong to the class of ℒℛ servers. We derive tight upper bounds on the end-to-end delay, internal burstiness, and buffer requirements of individual sessions in an arbitrary network of ℒℛ servers in terms of the latencies of the individual schedulers in the network, when the session traffic is shaped by a token bucket. The theory of ℒℛ servers enables computation of tight upper bounds on end-to-end delay and buffer requirements in a heterogeneous network, where individual servers may support different scheduling architectures and under different traffic models     

A generalized processor sharing approach to flow control inintegrated services networks: the single-node case

The problem of allocating network resources to the users of an integrated services network is investigated in the context of rate-based flow control. The network is assumed to be a virtual circuit, connection-based packet network. It is shown that the use of generalized processor sharing (GPS), when combined with leaky bucket admission control, allows the network to make a wide range of worst-case performance guarantees on throughput and delay. The scheme is flexible in that different users may be given widely different performance guarantees and is efficient in that each of the servers is work conserving. The authors present a practical packet-by-packet service discipline, PGPS that closely approximates GPS. This allows them to relate results for GPS to the packet-by-packet scheme in a precise manner. The performance of a single-server GPS system is analyzed exactly from the standpoint of worst-case packet delay and burstiness when the sources are constrained by leaky buckets. The worst-case session backlogs are also determined     

End-station performance under leaky bucket traffic shaping

The shaping of traffic at its source is a prominent congestion control solution in ATM networks. The “leaky bucket” with a “cell spacer” is a very popular traffic-shaping approach. By sizing the leaky bucket and spacer parameters, an end station shapes its traffic to conform to a “good behaviour” contract with the network. The leaky bucket delays the transmission of a selected number of cells, while the spacer forces a minimum time distance between transmitted cells. When a contracted transmission rate is close to the traffic generation rate of the end station, this traffic stream will utilize most of the bandwidth available on its virtual connection. The high utilization of such a connection leads to large queues of frames and cells at the end station, with high adverse consequences for end-to-end delay and jitter. Based on the negotiated traffic parameters and source traffic characteristics, we study, through simulations, the contribution of the leaky bucket plus cell spacer subsystem to the delay and jitter in an end station. We also study the distribution of the size of the bursts of cells leaving the end station and entering the network. Finally, we derive the theoretical upper bound for the size of bursts of the cells     

Analysis of leaky bucket mechanism based on burstiness characterization

In high-speed networks, a congestion control strategy has to manage bandwidth allocation based on the characteristics of input traffic sources. Accordingly, the definition of traffic characterization becomes significant in all aspects concerning network performance. In this paper, the burstiness characterization of a traffic stream is based on a virtual queue principle. We study the leaky bucket mechanism as a regulator element that controls input traffic before access to a newwork, as well as inside a network. To protect an input traffic stream, we investigate the optimal parameter settings of a leaky bucket. In addition, we analyse the worst case performance, and obtain upper bounds on loss probability and packet delay. We also determine the characteristics of an output stream in the worst case. Such performance bounds reveal the effectiveness of a leaky bucket, and provide enough information for the QOS satisfaction of the network users.     

基于分形漏桶整形器的通用处理器共享系统性能分析

为了分析自相似业务流对通用处理器共享（GPS）系统性能的影响,研究了GPS系统性能与业务流自相似参数等因素之间的关系.通过使用分形漏桶的包络曲线对进入GPS系统的自相似业务流进行整形,推导了利用自相似业务流作为输入的GPS系统的队列长度和时延统计上界.数值结果与分析显示,基于分形漏桶的GPS系统性能模型对自相似业务流具有较好的性能.     

Generalized guaranteed rate scheduling algorithms: a framework

In this paper, we define a class of generalized guaranteed rate (GR) scheduling algorithms that includes algorithms which allocate a variable rate to the packets of a flow. We define work-conserving generalized virtual clock, packet-by-packet generalized processor sharing, and self-clocked fair queueing scheduling algorithms that can allocate a variable rate to the packets of a flow. We also define scheduling algorithms suitable for servers where packet fragmentation may occur. We demonstrate that if a class of rate controllers is employed for a flow in conjunction with any scheduling algorithm in GR, then the resulting non-work-conserving algorithm also belongs to GR. This leads to the definition of several non-work-conserving algorithms. We then present a method for deriving the delay guarantee of a network of servers when: (1) different rates are allocated to packets of a flow at different servers along the path and the bottleneck server for each packet may be different, and (2) packet fragmentation and/or reassembly may occur. This delay guarantee enables a network to provide various service guarantees to flows conforming to any specification. We illustrate this by utilizing delay guarantee to derive delay bounds for flows conforming to leaky bucket, exponentially bounded burstiness, and flow specification. Our method for determining these bounds is valid in internetworks and leads to tighter results     

Any work-conserving policy stabilizes the ring with spatial re-use

We consider the ring network with spatial reuse. Traffic streams may enter and exit the network at any node. We adopt an arrival traffic model with deterministic constraints on its sample paths, which conforms to the output traffic of a leaky bucket rate control mechanism. A transmission policy specifies each time at which the traffic stream will be transmitted at the outgoing link by each node. We provide an upper bound on the asymptotic backlog of the ring that holds for all work-conserving policies and is independent of the initial conditions. This bound remains finite as long as the maximum load of every link is less than one. The latter condition is also necessary for the existence of an asymptotic bound that is independent of the initial conditions     

Effectiveness of the `leaky bucket' policing mechanism in ATMnetworks

The performance of the leaky bucket, a device for controlling the source traffic parameters of an ATM network is analyzed. The most critical situation, i.e., an on/off bursty source, is assumed. Moreover, the delay jitter introduced by a possible multiplexing of sources inside the customer premises network is not considered. The leaky bucket can be analyzed as a G/D/1/N queue with finite waiting room N and a suitable arrival process. An alternative approach, the fluid flow approximation, in which the bit flow is considered as a continuous variable, is presented. By comparison with the exact model, it is shown that the accuracy of the fluid flow approach is sufficient for practical purposes. An explicit formula for the cell loss probability, in case of exponential distributions for both the burst duration and the inactivity period of the source, is derived. On the basis of that formula, some numerical evaluations are presented with the aim of assessing the effectiveness of the leaky bucket mechanism. It is concluded that while the leaky bucket can easily control the peak rate, difficulties arise in controlling the mean bit rate (because of the long time required) and the burst duration (because of the poor selectivity)     

Bursty ATM user traffic allowed by a jitter tolerant leaky bucket and its impact on link utilization

In a network based on the asynchronous transfer mode (ATM), quality of service requirements have to be met even in the presence of users who send traffic as bursty as the policing device allows. For peak cell rate policing with a jitter tolerant leaky bucket, a periodic maximally bursty traffic pattern allowed by the leaky bucket is derived. The impact of this kind of bursty user traffic on the cell loss performance of the remaining sources is investigated by introducing, solving and applying the queueing model Geo(n) + P/D/1/K, where P stands for ‘periodic’. Taking bursty user traffic into account, it is shown that the maximal jitter or cell delay variation allocated to the user and tolerated by the leaky bucket is an important parameter for link utilization. The results help to answer the question under which conditions a shaping function is needed in conjunction with the usage parameter control function.     

模糊漏桶在ATM网络UPC中的应用

本文提出了模糊漏桶模型，研究了它与普通漏桶在用户量参数控制（ＵＰＣ）中的作用。由于ＣＡＣ初步协议的不完全合理性，在实际应用中动态调节是必要的；仿真结果表明在降低信元丢失率、时延和时延抖动方面，及在动态利用网络资源方面，模糊漏桶算法要比普通的优越。我们还给出了合适的模糊控制规则。     

Rate Proportional SCFQ Algorithm for High‐Speed Packet‐Switched Networks

Self‐Clocked Fair Queueing (SCFQ) algorithm has been considered as an attractive packet scheduling algorithm because of its implementation simplicity, but it has unbounded delay property in some input traffic conditions. In this paper, we propose a Rate Proportional SCFQ (RP‐SCFQ) algorithm which is a rate proportional version of SCFQ. If any fair queueing algorithm can be categorized into the rate proportional class and input is constrained by a leaky bucket, its delay is bounded and the same as that of Weighted Fair Queueing (WFQ) which is known as an optimal fair queueing algorithm. RP‐SCFQ calculates the timestamps of packets arriving during the transmission of a packet using the current value of system potential updated at every packet departing instant and uses a starting potential when it updates the system potential. By doing so, RP‐SCFQ can have the rate proportional property. RP‐SCFQ is appropriate for high‐speed packet‐switched networks since its implementation complexity is low while it guarantees the bounded delay even in the worst‐case input traffic conditions.     

ATM突发性业务阻塞控制

在ＡＴＭ网里业务阻塞控制是一个十分重要的问题，本文对一种缓冲漏桶业务阻塞控制算法在突发性业务输入情况下的性能进行了计算机模拟分析，模拟结构表明缓冲漏桶算法是一种适合于突发性业务的阻塞控制算法，文章在模拟结果的基础上给出了缓冲漏桶算法中参量选择的算法。     

提供端到端时延和时延抖动保障的QoS控制

 提出了一类具有最大速率控制的速率保障(Maximum Rate Control-Guaranteed Rate,MRC-GR)算法,可对流同时提供速率保障和最大速率控制.当网络各节点执行MRC-GR算法时,提供了确定网络端到端时延上限和下限的方法,针对服从令牌桶模型和同步单元模型的业务源给出了网络时延上限和下限.针对MRC-GR算法实例——具有最大速率控制的最差情形公平加权公平排队(worst-case fair weighted fair queueing with maximum rate control)调度算法进行仿真实验,仿真结果验证了理论分析.     

Bounded‐delay and loss‐free guarantees for real‐time video in integrated services packet networks

In this paper, we analyse upper bounds on the end‐to‐end delay and the required buffer size at the leaky bucket and packet switches within the network in the context of the deterministic bandwidth allocation method in integrated services packet networks. Based on that formulation, we then propose a CAC method suitable to ISPN to guarantee the bounded end‐to‐end delay and loss‐free packet transmissions. As an example application, the GOP–CBR MPEG‐2 is considered. In that case, we also show tighter bounds by slightly modifying the coding method of GOP–CBR MPEG‐2. Using the actual traced data of GOP–CBR MPEG‐2, we discuss the applicabilities of our analytical results and proposed CAC by comparing with simulation. Numerical results show that the loose upper bounds can also achieve more utilization even in the context of deterministic bandwidth allocation compared with the peak bandwidth allocation strategy. Copyright © 2000 John Wiley & Sons, Ltd.     

ANALYSIS OF THE LEAKY BUCKET ALGORITHM FOR PRIORITY SERVICES

The leaky bucket algorithm with loss priorities is studied in this paper. The analytical expression of the relation among leaky bucket performance, statistical parameters of input traffic and leaky bucket, parameters for various priority services is obtained, and the effect of adjustment factor on leaky bucket performance of higher-priority service and lower-priority service is studied with two priority classes.     

动态缓冲区门限漏桶方案的性能分析

本文提出了缓冲区门限随着有漏桶速率变化的动态缓冲区门限漏桶方案,以马尔可夫调制泊松过程（ＭＭＰＰ）作为信源输入人流,用嵌入马尔可夫过程这系统,得到了系统状态在嵌入点和任意时刻的极限分面具人而获得信损失率、信元平均时延及占用的有效带宽性能测度,数值分析表明本方案的信元人率及平均信元时延性能较缓冲区门限漏桶方案有显著提高,而且占用更少的带宽。     

ATM业务监控的最差通过流分析及二级漏桶算法

讨论了一定算法下最差通过流的概念，强调了最差通过流的参数特性是评价一种业务监控算法的重要指标之一。对基本漏桶和缓冲漏桶逄法进行了比较。     

Performance limitation of the leaky bucket algorithm for ATMnetworks

The performance limitation of the “leaky bucket algorithm” is analyzed for usage parameter control and traffic management in asynchronous transfer mode (ATM) networks. Simulation results show that the conventional statistical bandwidth allocation method, which uses “the worst pattern derived from the cell interarrival time moments” permitted by the leaky bucket algorithm, can not guarantee the quality of service (QOS). As a result, this paper proves that the VC/VP bandwidth allocation method based on the leaky bucket algorithm is unsatisfactory