A calculus for network delay. II. Network analysis

For pt.I see ibid., vol.37, no.1, p.114-31 (1991). A method to analyze the flow of data in a network consisting of the interconnection of network elements is presented. Assuming the data that enters the network satisfies burstiness constraints, burstiness constraints are derived for traffic flowing between network elements. These derived constraints imply bounds on network delay and buffering requirements. By example, it is shown that the use of regulator elements within the network can reduce maximum network delay. It is also found that such a use of regulator elements can enlarge the throughput region where finite bounds for delay are found. Finally, it is shown how regulator elements connected in series can be used to enforce general burstiness constraints     

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.     

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     

Stochastic performance analysis of non-feedforward networks

Many Internet applications are both delay and loss sensitive, and need network performance guarantees that include bandwidth, delay/delay jitter, and packet loss rate. It is very important to quantify and exploit the capabilities of guaranteed service provisioning of communication networks. In this paper, we study the queueing behaviors of non-feedforward networks (a non-feedforward network is a network in which at least one set of acyclic traffic routes forms a cycle; a feedforward network is a network in which any set of acyclic traffic routes does not form a cycle) with FIFO scheduling discipline and Regulated, Markov On-Off, and Fractional Brownian traffic sources. We develop a new methodology to analyze the probabilistic bounds on the delays experienced by traffic. By leveraging the large deviations and fixed-point techniques, we turn probability problems into deterministic optimization problems and translate a probabilistic delay bound into a fixed point of a non-linear real function. Our contribution in this paper is the derivation of a probabilistic bound on the delays experienced by traffic in non-feedforward networks, based on an assumption, i.e., the tail probability of the difference between the beginning time of a busy interval of a server and the earliest arriving time at the corresponding network ingress of the traffic arrivals that arrive at this server during this busy interval can be bounded by the maximum of the violation probabilities of the accumulative upper stream delay bound suffered by this server‘s traffic arrivals. Consequently, our new results not only consummate the theory of stochastic analysis of network performance, but also facilitate the design of protocols and algorithms for non-feedforward networks to provide performance guarantees to various applications with diverse performance requirements.     

PERFORMANCE EVALUATION OF NON-BLOCKING ATM SWITCHES UNDER VARIOUS TRAFFIC AND BUFFERING SCHEMES

Broadband integrated services digital networks (BISDN) are designed to offer a variety of services with bit rates ranging from several kb/s (e.g. teleactions) to hundreds of Mb/s (e.g. HDTV), and in some cases approaching Gb/s (e.g. in interconnections of high-speed LANs). A multiplicity of rates and the burstiness of traffic sources lead naturally to systems based on the fast packet switching (or asynchronous transfer mode) concept. The requirements of data buffering and high-speed processing of packet headers have resulted in a plethora of proposals for ATM switching nodes and an equal number of ways for evaluating them. In particular, the class of non-blocking architectures of ATM switches has received the most attention from the research community. This paper reviews this class of architecture with emphasis on contention resolution methods and communication traffic performance. The contention resolution methods are divided into four categories: input buffering, output buffering, shared buffering, and hybrid buffering. The communication traffic characteristics are divided into two categories: uniform traffic and bursty traffic.     

Scaling properties of statistical end-to-end bounds in the network calculus

The stochastic network calculus is an evolving new methodology for backlog and delay analysis of networks that can account for statistical multiplexing gain. This paper advances the stochastic network calculus by deriving a network service curve, which expresses the service given to a flow by the network as a whole in terms of a probabilistic bound. The presented network service curve permits the calculation of statistical end-to-end delay and backlog bounds for broad classes of arrival and service distributions. The benefits of the derived service curve are illustrated for the exponentially bounded burstiness (EBB) traffic model. It is shown that end-to-end performance measures computed with a network service curve are bounded by /spl Oscr/(H log H), where H is the number of nodes traversed by a flow. Using currently available techniques, which compute end-to-end bounds by adding single node results, the corresponding performance measures are bounded by /spl Oscr/(H/sup 3/).     

Characterization of slice-based H.264/AVC encoded video traffic using token buckets

An explicit slice-based mode type selection scheme for use in H.264/AVC has recently been developed, which reduces the burstiness effect of standard frame-based H.264/AVC by breaking up the Group of Picture structure. In this paper, slice-based encoded video streams are characterized using the token bucket traffic model and compared to standard frame-based encoded streams. Both lossless, loss bounded and delay bounded token bucket models are investigated and the high quantiles are found for the amount of loss. Loss above the amount given by the high quantiles will happen only with a very small probability. It is shown that the reduced burstiness for the slice-based video encoding leads to lower token bucket parameters compared to frame-based video encoding for a stream without scene changes, and a larger reduction in the token bucket parameters compared to the frame-based video encoding when a small amount of delay or loss is allowed for the stream with scene changes. Next, reshuffling of the frames of the video streams with scene changes is employed to better understand the effects of long-range dependence on the token bucket parameters. Only small effects are found from reshuffling the scenes, but reshuffling of the frames inside the scenes leads to lower token bucket parameters. Finally, an approach to estimate the parameters for the token bucket model using simple characteristics of the slice-based stream is developed.     

Node pacing for small optical RAM-buffered packet-switching networks

One of the difficulties with optical packet switched (OPS) networks is buffering optical packets in the network. The only available solution that can currently be used for buffering in the optical domain is using long fiber lines called fiber delay lines (FDLs), which have severe limitations. Moreover, the research on optical RAM presently being done is not expected to achieve a large capacity soon. However, the burstiness of Internet traffic causes high packet drop rates and low utilization in very small buffered OPS networks. We therefore propose a new node-based pacing algorithm for decreasing burstiness. We show that by applying some simple pacing at the edge or core backbone nodes, the performance of very small optical RAM buffered core OPS networks with variable-length packets can be notably increased.     

Buffer sizing for synchronous self-routeing broadband packet switches with bursty traffic

Previous studies on the performance of synchronous self-routeing packet switches have assumed that the input traffic is random, i.e. there is no correlation between adjacent packet arrivals. This assumption is generally not valid in the data communication environment (e.g. host-to-host communication) where a file transfer usually generates a string of correlated packets. The consequence is that the random traffic assumption greatly underestimates the buffer requirement of the switch. In this paper, we model each input traffic stream as a binary source as a first step to understand the performance of a packet switch in a bursty traffic environment. We found that, given a fixed traffic load (or switch utilization), the required buffer size increases linearly as the burstiness index (the average burst length) of the traffic increases. In addition, the required buffer size is more sensitive to the burstiness of the traffic, when the average traffic load is higher and when the packet loss requirement is more stringent. Initial applications of broadband packet switches are likely to be the interconnections of LANs and hosts. The results of the study indicate that the high burstiness in certain broadband traffic significantly reduces the allowable switch utilization, given a fixed amount of buffers. To increase the switch utilization, an appropriate congestion control mechanism needs to be implemented.     

考虑排队时延的系统保护通信网络路由选择算法

目前满足系统保护通信网络的路由算法是在综合时延和可靠性的要求下,计算一条快速且可靠传输的路径,而没有考虑到当电网发生故障或网络中通信量过大时,通信网络中许多节点的排队时延会极大地增加,忽略排队时延对路径传输总时延的影响会导致路径的错误选择,从而影响系统保护的实时性。针对此问题,提出了一种考虑排队时延的路由选择算法,用于计算信息传输总时延最小的最优路径,以提高系统保护通信的实时性。实验结果表明,通过本文提出的路由选择算法计算得到的路径在满足系统保护可靠性要求的基础上信息传输总时延最小。     

Smoothing Streams in an In-Home Digital Network: Optimization of Bus and Buffer Usage

In an in-home digital network it may be expected that several data streams (audio, video) run simultaneously over a shared communication device, e.g., a bus. The burstiness of a data stream can be reduced by buffering data at the sending and receiving side, thereby allowing a lower bus share allocation for the stream. In this paper we present an algorithm that determines how much of the bus capacity and buffer space should be allocated to each stream, in order to have a feasible transmission schedule for each stream. Furthermore, the algorithm determines a transmission schedule for each stream, indicating how much data is transmitted over time. We show how this multiple-stream problem can be solved by repeatedly solving single-stream problems. We present efficient algorithms to solve these single-stream problems. Furthermore, we present some experimental results. This revised version was published online in September 2006 with corrections to the Cover Date.     

Worst-case fraction of CBR teletraffic unpunctual due tostatistical multiplexing

This paper quantitatively analyzes the queueing delay of the constant-bit-rate (CBR) traffic in a multiplexer, where the CBR traffic is mixed with the traffic of another session (interfering traffic) that has throughput and burstiness constraints. This paper focuses as a quality-of-service (QoS) measure on the fraction of the CBR traffic that fails to meet a certain delay requirement. Results include the worst-case QoS of CBR traffic as a function of the throughput and burstiness parameters imposed on the interfering traffic. Results of this paper can be applied to traffic management and call processing of asynchronous transfer mode (ATM) networks     

基于OPNET的混合关键性网络建模与仿真分析

混合关键性网络是一种新型的通信架构,可以满足非实时性和实时性业务的需求.为分析其网络性能,提出在OPNET网络仿真环境中建模的方法.以开放式系统互联模型为基础,采用层次化建模,构建网络的节点模型和进程模型.该模型考虑了事件触发和时间触发消息的特点,通过设计调度算法和容错方式,实现了仿真实验的灵活配置和端到端延迟抖动等性能指标的验证.对仿真结果的性能分析表明,混合关键性网络能够保证实时业务的确定性以及兼容标准以太网的非实时业务.     

一种适用于星载光交换网络的资源预留协议

根据卫星光交换网络应用需求,结合现有的地面光突发交换资源预留方法,提出了一种基于突发流的资源预留协议。首先通过流量估计把突发数据按照目的地址和QoS区分为单个突发和突发流,然后按照这两种分类对卫星光网络资源进行了成功预留。为了对该预留方法进行考察,建立了平均端-端时延、吞吐量、链路利用率数学分析模型。理论分析与仿真证明了该资源预留方法通过降低光交换矩阵的重置时间和交换时延,有效降低了端-端时延,提高了网络吞吐量,适用于星载光交换网络。     

Distributed probabilistic medium access with multipacket reception and Markovian traffic

Enabling multipacket reception (MPR) at the physical layer is a promising way to achieve higher bandwidth efficiency while reducing the complexity of the medium access control layer in distributed wireless networks. We study distributed probabilistic access where transmitting nodes access the shared wireless medium with a probability based on the node’s information about the aggregate traffic carried by the network. We model bursty traffic by rate-controlled two-state Markov sources and introduce a parameter that describes the “burstiness” level of the offered traffic. A throughput-optimal medium access strategy utilizing limited feedback is then described and its performance is examined for traffic with different levels of burstiness. It is shown that the bursty nature of the traffic in data networks allows for improvement of the bandwidth efficiency. Bounds on the system throughput are proposed and the queuing delay is analyzed.     

Leaky-bucket based rate control algorithm for C VBR video encoding

A rate control algorithm is presented for constrained variable bit rate (C VBR) encoding to make the compressed video stream more friendly to the user network interface (UNI) than in free VBR coding. Experiments show that the algorithm would not only meet the delay constraint and traffic contract of VBR transfer so as to avoid the cell loss over UNI, but also benefit the statistical multiplexing by reducing the burstiness of the MPEG encoded stream     

Application of network calculus to guaranteed service networks

We use previous network calculus results to study some properties of lossless multiplexing as it may be used in guaranteed service networks. We call network calculus a set of results that apply min-plus algebra to packet networks. We provide a simple proof that shaping a traffic stream to conform to a burstiness constraint preserves the original constraints satisfied by the traffic stream. We show how all rate-based packet schedulers can be modeled with a simple rate latency service curve. Then we define a general form of deterministic effective bandwidth and equivalent capacity. We find that call acceptance regions based on deterministic criteria (loss or delay) are convex, in contrast to statistical cases where it is the complement of the region which is convex. We thus find that, in general, the limit of the call acceptance region based on statistical multiplexing when the loss probability target tends to 0 may be strictly larger than the call acceptance region based on lossless multiplexing. Finally, we consider the problem of determining the optimal parameters of a variable bit rate (VBR) connection when it is used as a trunk, or tunnel, given that the input traffic is known. We find that there is an optimal peak rate for the VBR trunk, essentially insensitive to the optimization criteria. For a linear cost function, we find an explicit algorithm for the optimal remaining parameters of the VBR trunk     

Optimal bandwidth and buffer allocation method for heterogeneoustraffic with multiple QoS in ATM networks

An optimal bandwidth and buffer allocation scheme is proposed which maximises network utilisation and satisfies both cell loss rate (CLR) and delay requirements for heterogeneous traffic with multiple quality of service. Simulation results show that the proposed scheme satisfies CLR and delay requirements and also utilises network resources efficiently