A new class of performance results for a fractional Brownian traffic model

Recent Bellcore studies have shown that high-speed data traffic exhibits long-range dependence, characterized byH>0.5, whereH is the Hurst parameter of the traffic. In the wake of those studies, there has been much interest in developing tractable analytical models for traffic with long-range dependence, for use in performance evaluation and traffic engineering. Norros has used a traffic model known as Fractional Brownian Motion (FBM) to derive several analytical results on the behavior of a queue subject to such an arrival process. In this paper, we derive a new class of results, also based on the FBM model, which reveal rather curious and unexpected crossover properties of the Hurst parameter of the traffic, as regards its effect on the behavior of queues. These results, together with those of Norros, serve to enhance our understanding of the significance of the Hurst parameterH for traffic engineering. In particular, Krishnan and Meempat have used the crossover property derived here to explain, in part, a gap that existed between the results of two sets of Bellcore studies, one casting doubt on the usefulness of Markovian traffic models and methods whenH>0.5, and the other furnishing an example of successful traffic engineering with Markovian methods for traffic known to haveH>0.5. The results derived here can be used to obtainconservative estimates of the multiplexing gains achieved when independent traffic sources with the same Hurst parameterH are multiplexed for combined transmission. In turn, such estimates yield guidelines for the engineering of ATM links that are subject to traffic with long-range dependence.     

Overflow and losses in a network queue with a self-similar input

This paper considers a discrete time queuing system that models a communication network multiplexer which is fed by a self-similar packet traffic. The model has a finite buffer of size h, a number of servers with unit service time, and an input traffic which is an aggregation of independent source-active periods having Pareto-distributed lengths and arriving as Poisson batches. The new asymptotic upper and lower bounds to the buffer-overflow and packet-loss probabilities P are obtained. The bounds give an exact asymptotic of log P/log h when h → to ∞. These bounds decay algebraically slow with buffer-size growth and exponentially fast with excess of channel capacity over traffic rate. Such behavior of the probabilities shows that one can better combat traffic losses in communication networks by increasing channel capacity rather than buffer size. A comparison of the obtained bounds and the known upper and lower bounds is done. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotically optimal importance sampling for Jackson networks with a tree topology

This note describes an importance sampling (IS) algorithm to estimate buffer overflows of stable Jackson networks with a tree topology. Three new measures of service capacity and traffic in Jackson networks are introduced and the algorithm is defined in their terms. These measures are effective service rate, effective utilization and effective service-to-arrival ratio of a node. They depend on the nonempty/empty states of the queues of the network. For a node with a nonempty queue, the effective service rate equals the node’s nominal service rate. For a node i with an empty queue, it is either a weighted sum of the effective service rates of the nodes receiving traffic directly from node i, or the nominal service rate, whichever smaller. The effective utilization is the ratio of arrival rate to the effective service rate and the effective service-to-arrival ratio is its reciprocal. The rare overflow event of interest is the following: given that initially the network is empty, the system experiences a buffer overflow before returning to the empty state. Two types of buffer structures are considered: (1) a single system-wide buffer shared by all nodes, and (2) each node has its own fixed size buffer. The constructed IS algorithm is asymptotically optimal, i.e., the variance of the associated estimator decays exponentially in the buffer size at the maximum possible rate. This is proved using methods from (Dupuis et al. in Ann. Appl. Probab. 17(4):1306–1346, 2007), which are based on a limit Hamilton–Jacobi–Bellman equation and its boundary conditions and their smooth subsolutions. Numerical examples involving networks with as many as eight nodes are provided.     

A heavy traffic limit theorem for a class of open queueing networks with finite buffers

We consider a queueing network of d single server stations. Each station has a finite capacity waiting buffer, and all customers served at a station are homogeneous in terms of service requirements and routing. The routing is assumed to be deterministic and hence feedforward. A server stops working when the downstream buffer is full. We show that a properly normalized d-dimensional queue length process converges in distribution to a fd-dimensional semimartingale reflecting Brownian motion (RBM) in a d-dimensional box under a heavy traffic condition. The conventional continuous mapping approach does not apply here because the solution to our Skorohod problem may not be unique. Our proof relies heavily on a uniform oscillation result for solutions to a family of Skorohod problems. The oscillation result is proved in a general form that may be of independent interest. It has the potential to be used as an important ingredient in establishing heavy traffic limit theorems for general finite buffer networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Reduced-Load Equivalence for Generalised Processor Sharing Networks with Long-Tailed Input Flows

We consider networks where traffic is served according to the Generalised Processor Sharing (GPS) principle. GPS-based scheduling algorithms are considered important for providing differentiated quality of service in integrated-services networks. We are interested in the workload of a particular flow i at the bottleneck node on its path. Flow i is assumed to have long-tailed traffic characteristics. We distinguish between two traffic scenarios, (i) flow i generates instantaneous traffic bursts and (ii) flow i generates traffic according to an on/off process. In addition, we consider two configurations of feed-forward networks. First we focus on the situation where other flows join the path of flow i. Then we extend the model by adding flows which can branch off at any node, with cross traffic as a special case. We prove that under certain conditions the tail behaviour of the workload distribution of flow i is equivalent to that in a two-node tandem network where flow i is served in isolation at constant rates. These rates only depend on the traffic characteristics of the other flows through their average rates. This means that the results do not rely on any specific assumptions regarding the traffic processes of the other flows. In particular, flow i is not affected by excessive activity of flows with heavier-tailed traffic characteristics. This confirms that GPS has the potential to protect individual flows against extreme behaviour of other flows, while obtaining substantial multiplexing gains.     

Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm

We study a model of controlled queueing network, which operates and makes control decisions in discrete time. An underlying random network mode determines the set of available controls in each time slot. Each control decision “produces” a certain vector of “commodities”; it also has associated “traditional” queueing control effect, i.e., it determines traffic (customer) arrival rates, service rates at the nodes, and random routing of processed customers among the nodes. The problem is to find a dynamic control strategy which maximizes a concave utility function H(X), where X is the average value of commodity vector, subject to the constraint that network queues remain stable.We introduce a dynamic control algorithm, which we call Greedy Primal-Dual (GPD) algorithm, and prove its asymptotic optimality. We show that our network model and GPD algorithm accommodate a wide range of applications. As one example, we consider the problem of congestion control of networks where both traffic sources and network processing nodes may be randomly time-varying and interdependent. We also discuss a variety of resource allocation problems in wireless networks, which in particular involve average power consumption constraints and/or optimization, as well as traffic rate constraints.     

Long‐range dependence and performance in telecom networks

Telecommunications systems have recently undergone significant innovations. These call for suitable statistical models that can properly describe the behaviour of the input traffic in a network. Here we use fractional Brownian motion (FBM) to model cumulative traffic network, thus taking into account the possible presence of long‐range dependence in the data. A Bayesian approach is devised in such a way that we are able to: (a) estimate the Hurst parameter H of the FBM; (b) estimate the overflow probability which is a parameter measuring the quality of service of a network: (c) develop a test for comparing the null hypothesis of long‐range dependence in the data versus the alternative of short‐range dependence. In order to achieve these inferential results, we elaborate an MCMC sampling scheme whose output enables us to obtain an approximation of the quantities of interest. An application to three real datasets, corresponding to three different levels of traffic, is finally considered. Copyright © 2004 John Wiley & Sons, Ltd.     

Queueing at large resources driven by long-tailed M/G/∞-modulated processes

We analyze the queue at a buffer with input comprising sessions whose arrival is Poissonian, whose duration is long-tailed, and for which individual session detail is modeled as a stochastic fluid process. We obtain a large deviation result for the buffer occupation in an asymptotic regime in which the arrival rate nr, service rate ns, and buffer level nb are scaled to infinity with a parameter n. This can be used to approximate resources which multiplex many sources, each of which only uses a small proportion of the whole capacity, albeit for long-tailed durations. We show that the probability of overflow in such systems is exponentially small in n, although the decay in b is slower, reflecting the long tailed session durations. The requirements on the session detail process are, roughly speaking, that it self-averages faster than the cumulative session duration. This does not preclude the possibility that the session detail itself has a long-range dependent behavior, such as fractional Brownian motion, or another long-tailed M/G/∞ process. We show how the method can be used to determine the multiplexing gain available under the constraint of small delays (and hence short buffers) for multiplexers of large aggregates, and to compare the differential performance impact of increased buffering as opposed to load reduction. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analyzing Telephone Network Data

Abstract

As our reliance on computer networks grows, it becomes increasingly important that we understand the behavior of the traffic that they carry. Because of the speeds and sizes involved, working with traffic collected from a computer network usually means working with large datasets. This article describes our experience with traffic collected from the common channel signaling (CCS) network. I will briefly describe the data and how they are collected and discuss similarities with and differences from other large datasets. Next, I will describe our analysis tools and outline the reasons that they have been found useful. Finally, I will discuss the challenges facing us as we strive for a better understanding of more data from faster networks. Although my emphasis in this article is on the CCS network, it has been my experience that both the problems and the solutions generalize to data from other networks.     

Network design with grooming constraints

Networks are physically and logically decomposed into layers with different technological features. Often, the routing of a demand through a non-multiplexing layer is made by grooming several demands at another, multiplexing-capable layer, thus using less capacity on the former but more on the latter. The problem of designing such a multi-layer network so as to route a set of traffic demands can be solved by embedding multiplexing into a well-suited model. We restrict to a two-layer problem as this is most common in today's network world, then we represent grooming through a model based on paths and semi-paths, and propose a row-column generation approach to solve a set of problems on real-world large networks.     

Chernoff bounds for mean overflow rates

A number of independent traffic streams arrive at a queueing node which provides a finite buffer and a non-idling service at constant rate. Customers which arrive when the buffer is full are dropped and counted as overflows. We present Chernoff type bounds for mean overflow rates in the form of finite-dimensional minimization problems. The results are based on bounds for moment generating functions of buffer and bandwidth usage of the individual streams in an infinite buffer with constant service rate. We calculate these functions for regulated, Poisson and certain on/off sources. The achievable statistical multiplexing gain and the tightness of the bounds are demonstrated by several numerical examples.     

Buffer allocation for a class of nonlinear stochastic knapsack problems

In this paper, we examine a class of nonlinear, stochastic knapsack problems which occur in manufacturing, facility or other network design applications.Series, merge-and-split topologies of series-parallelM/M/1/K andM/M/C/K queueing networks with an overall buffer constraint bound are examined. Bounds on the objective function are proposed and a sensitivity analysis is utilized to quantify the effects of buffer variations on network performance measures.     

Symmetry property of the throughput in closed tandem queueing networks with finite buffers

In this paper we consider closed tandem queueing networks with finite buffers and blocking before service. With this type of blocking, a server is allowed to start processing a job only if there is an empty space in the next buffer. It was recently conjectured that the throughput of such networks is symmetrical with respect to the population of the network. That is, the throughput of the network with population N is the same as that with population C − N, where C is the total number of buffer spaces in the network. The main purpose of this paper is to prove this result in the case where the service time distributions are of phase type (PH-distribution). The proof is based on the comparison of the sample paths of the network with populations N and C − N. Finally, we also show that this symmetry property is related to a reversibility property of this class of networks.     

Deterministic Routing With Bounded Buffers: Turning Offline Into Online Protocols

In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is analyzed in terms of the size of the network and the routing number of the network. Given a network H of n nodes, the routing number of H is defined as the maximum over all permutations on {1, ..., n} of the minimal number of steps to route offline in H. We show that for any network H of size n with routing number R our protocol needs time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing. In particular, our result yields optimal deterministic routing protocols for arbitrary networks with diameter or bisection width , constant. Furthermore we can extend our result to deterministic compact routing. This yields, e.g., a deterministic routing protocol with runtime O(R logn) for arbitrary bounded degree networks if only O(logn) bits are available at each node for storing routing information. Our protocol is a combination of a generalized ``routing via simulation' technique with an new deterministic protocol for routing h-relations in an extended version of a multibutterfly network. This protocol improves upon all previous routing protocols known for variants of the multibutterfly network. The ``routing via simulation' technique used here extends a method previously introduced by the authors for designing compact routing protocols. Received July 18, 1997     

On the departure process of a leaky bucket system with long-range dependent input traffic

Due to the strong experimental evidence that the traffic to be offered to future broadband networks will display long-range dependence, it is important to study the possible implications that such traffic may have for the design and performance of these networks. In particular, an important question is whether the offered traffic preserves its long-range dependent nature after passing through a policing mechanism at the interface of the network. One of the proposed solutions for flow control in the context of the emerging ATM standard is the so-called leaky bucket scheme. In this paper we consider a leaky bucket system with long-range dependent input traffic. We adopt the following popular model for long-range dependent traffic: Time is discrete. At each unit time a random number of sessions is initiated, having the distribution of a Poisson random variable with mean λ. Each of these sessions has a random duration τ, where the integer random variable τ has finite mean, infinite variance, and a regularly varying tail, i.e., P(τ >К) ~ К^-Lα L(К), where 1 < α < 2 L(·) is a slowly varying function. Once a session is initiated, it generates one cell at each unit of time until its termination. We examine the departure process of the leaky bucket policing mechanism driven by such an arrival process, and show that it too is long-range dependent for any token buffer size and any - finite or infinite - cell buffer size. Moreover, upper and lower bounds for the covariance sequence of the output process are established. The above results demonstrate that long-range dependence cannot be removed by the kinds of flow control schemes that are currently being envisioned for broadband networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

A feedback fluid queue with two congestion control thresholds

Feedback fluid queues play an important role in modeling congestion control mechanisms for packet networks. In this paper we present and analyze a fluid queue with a feedback-based traffic rate adaptation scheme which uses two thresholds. The higher threshold B ₁ is used to signal the beginning of congestion while the lower threshold B ₂ signals the end of congestion. These two parameters together allow to make the trade-off between maximizing throughput performance and minimizing delay. The difference between the two thresholds helps to control the amount of feedback signals sent to the traffic source. In our model the input source can behave like either of two Markov fluid processes. The first applies as long as the upper threshold B ₁ has not been hit from below. As soon as that happens, the traffic source adapts and switches to the second process, until B ₂ (smaller than B ₁) is hit from above. We analyze the model by setting up the Kolmogorov forward equations, then solving the corresponding balance equations using a spectral expansion, and finally identifying sufficient constraints to solve for the unknowns in the solution. In particular, our analysis yields expressions for the stationary distribution of the buffer occupancy, the buffer delay distribution, and the throughput.     

Multiscale Analysis and Data Networks

The empirical finding of self-similarity in data network traffic over many time scales motivates the need for analysis tools that are particularly well adapted for identifying structures in network traffic. These structures span a range of time scales or are scale-dependent. Wavelet-based scaling analysis methods are especially successful, both collecting summary statistics from scale to scale and probing the local structure of packet traces. They include both spectral density estimation to identify large time-scale features and multifractal estimation for small time-scale bursts. While these methods are primarily statistical in nature, we may also adapt them to visualize the “burstiness” or the instantaneous scaling features of network traffic. This expository paper discusses the theoretical and implementation issues of wavelet-based scaling analysis for network traffic. Because data network traffic research does not consist solely of analysis, we show how these wavelet-based methods may be used to monitor and infer network properties (in conjunction with on-line algorithms and careful network experimentation). More importantly, we address what types of networking questions we can and cannot investigate with such tools.     

A hierarchical clustering scheme approach to assessment of IP-network traffic using detrended fluctuation analysis

This paper presents an approach to the assessment of IP-network traffic in terms of the time variation of self-similarity. To get a comprehensive view in analyzing the degree of long-range dependence (LRD) of IP-network traffic, we use a hierarchical clustering scheme, which provides a way to classify high-dimensional data with a tree-like structure. Also, in the LRD-based analysis, we employ detrended fluctuation analysis (DFA), which is applicable to the analysis of long-range power-law correlations or LRD in non-stationary time-series signals. Based on sequential measurements of IP-network traffic at two locations, this paper derives corresponding values for the LRD-related parameter α that reflects the degree of LRD of measured data. In performing the hierarchical clustering scheme, we use three parameters: the α value, average throughput, and the proportion of network traffic that exceeds 80% of network bandwidth for each measured data set. We visually confirm that the traffic data can be classified in accordance with the network traffic properties, resulting in that the combined depiction of the LRD and other factors can give us an effective assessment of network conditions at different times.     

Networks of probabilistic events in discrete time

The usual methods of applying Bayesian networks to the modeling of temporal processes, such as Dean and Kanazawa’s dynamic Bayesian networks (DBNs), consist in discretizing time and creating an instance of each random variable for each point in time. We present a new approach called network of probabilistic events in discrete time (NPEDT), for temporal reasoning with uncertainty in domains involving probabilistic events. Under this approach, time is discretized and each value of a variable represents the instant at which a certain event may occur. This is the main difference with respect to DBNs, in which the value of a variable V_i represents the state of a real-world property at time t_i. Therefore, our method is more appropriate for temporal fault diagnosis, because only one variable is necessary for representing the occurrence of a fault and, as a consequence, the networks involved are much simpler than those obtained by using DBNs. In contrast, DBNs are more appropriate for monitoring tasks, since they explicitly represent the state of the system at each moment. We also introduce in this paper several types of temporal noisy gates, which facilitate the acquisition and representation of uncertain temporal knowledge. They constitute a generalization of traditional canonical models of multicausal interactions, such as the noisy OR-gate, which have been usually applied to static domains. We illustrate the approach with the example domain of modeling the evolution of traffic jams produced on the outskirts of a city, after the occurrence of an event that obliges traffic to stop indefinitely.     

Performance analysis of virtual circuit connections for bursty data sources in ATM networks

ATM is a packet-like transmission mode that has been proposed for BISDN. It is characterized by an asynchronous slotted transmission mechanism that provides a high bandwidth, low delay connection-oriented transport service to the end user. In this paper, we provide an analytical approach for determining the performance of a virtual circuit connection for data transmission in a high-speed ATM network with finite buffers at the network nodes. The analysis assumes that the network operates using thebest effort delivery strategy and that the end-to-end virtual circuit is responsible for guaranteeing the integrity of the connection. Since the normal Markovian assumptions do not apply, a concise exact solution is impossible to obtain. This provides motivation for developing approximate techniques such as those found in Whitt's QNA paper that allow us to use general distributions for the traffic streams and service times. However, even these techniques assume infinite buffer capacities and hence cannot model buffer overflow. We have therefore developed a hybrid model that allows us to incorporate finite buffers at the nodes. This enables us to study the effect on the performance of both link errors and buffer overflow in conjunction with an end-to-end packet loss recovery scheme.This work was supported in part by a grant from AT&T and in part by NSF under Grant No. 8914447.Work done while at the University of Pennsylvania, Philadelphia, PA 19104, USA