Fractional Brownian motion (fBm) emerged as a useful model for self-similar and long-range dependent Internet traffic. Approximate performance measures are known from large deviations theory for single queuing systems with fBm through traffic. In this paper we derive end-to-end performance bounds for a through flow in a network of tandem queues under fBm cross traffic. To this end, we prove a rigorous sample path envelope for fBm that complements previous approximate results. We find that both approaches agree in their outcome that overflow probabilities for fBm traffic have a Weibullian tail. We employ the sample path envelope and the concept of leftover service curves to model the remaining service after scheduling fBm cross traffic at a system. Using composition results for tandem systems from the stochastic network calculus we derive end-to-end statistical performance bounds for individual flows in networks under fBm cross traffic. We discover that these bounds grow in O(n (log n)^(1 (2-2H))) for n systems in series where H is the Hurst parameter of the fBm cross traffic. We show numerical results on the impact of the variability and the correlation of fBm traffic on network performance.
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 ). This article presents a method for the computation of the equivalent bandwidth of an aggregate of heterogeneous self-similar sources, as well as the time scales of interest for queueing systems fed by a fractal Brownian motion (fBm) process. Moreover, the fractal leaky bucket, a novel policing mechanism capable of accurately monitoring self-similar sources, is introduced. The network calculus offers an elegant framework for determining worst-case bounds on delay and backlog in a network. This paper extends the network calculus to a probabilistic framework with statistical service guarantees. The notion of a statistical service curve is presented as a probabilistic bound on the service received by an individual flow or an aggregate of flows. The problem of concatenating per-node statistical service curves to form an end-to-end (network) statistical service curve is explored. Two solution approaches are presented that can each yield statistical network service curves. The first approach requires the availability of time scale bounds at which arrivals and departures at each node are correlated. The second approach considers a service curve that describes service over time intervals. Although the latter description of service is less general, it is argued that many practically relevant service curves may be compliant to this description A network calculus is developed for processes whose burstiness is stochastically bounded by general decreasing functions. This calculus is useful for a large class of input processes, including important processes exhibiting "subexponentially bounded burstiness" such as fractional Brownian motion. Moreover, it allows judicious capture of the salient features of real-time traffic, such as the "cell" and "burst" characteristics of multiplexed traffic. This accurate characterization is achieved by setting the bounding function as a sum of exponentials. Several types of network traffic have been shown to exhibit long-range dependence (LRD). In this work, we show that the busy period of an ATM system driven by a long-range dependent process can be very large. We introduce a new traffic model based on a fractional Brownian motion envelope process. We show that this characterization can be used to predict queueing dynamics. Furthermore, we derive a new framework for computing delay bounds in ATM networks based on this traffic model. We show that it agrees with results given by large deviation theory with less computational complexity. This paper establishes a link between two principal tools for the analysis of network traffic, namely, effective bandwidth and network calculus. It is shown that a general version of effective bandwidth can be expressed within the framework of a probabilistic version of the network calculus, where both arrivals and service are specified in terms of probabilistic bounds. By formulating well-known effective bandwidth expressions in terms of probabilistic envelope functions, the developed network calculus can be applied to a wide range of traffic types, including traffic that has self-similar characteristics. As applications, probabilistic lower bounds are presented on the service given by three different scheduling algorithms: static priority, earliest deadline first, and generalized processor sharing. Numerical examples show the impact of specific traffic models and scheduling algorithms on the multiplexing gain in a network. Network calculus, a theory dealing with queuing systems found in computer networks, focuses on performance guarantees. The development of an information theory for stochastic service-guarantee analysis has been identified as a grand challenge for future networking research. Towards that end, stochastic network calculus, the probabilistic version or generalization of the (deterministic) Network Calculus, has been recognized by researchers as a crucial step. Stochastic Network Calculus presents a comprehensive treatment for the state-of-the-art in stochastic service-guarantee analysis research and provides basic introductory material on the subject, as well as discusses the most recent research in the area. This helpful volume summarizes results for stochastic network calculus, which can be employed when designing computer networks to provide stochastic service guarantees. Features and Topics: Provides a solid introductory chapter, providing useful background knowledge Reviews fundamental concepts and results of deterministic network calculus Includes end-of-chapter problems, as well as summaries and bibliographic comments Defines traffic models and server models for stochastic network calculus Summarizes the basic properties of stochastic network calculus under different combinations of traffic and server models Highlights independent case analysis Discusses stochastic service guarantees under different scheduling disciplines Presents applications to admission control and traffic conformance study using the analysis results Offers an overall summary and some open research challenges for further study of the topic Key Topics: Queuing systems Performance analysis and guarantees Independent case analysis Traffic and server models Analysis of scheduling disciplines Generalized processor sharing Open research challenges Researchers and graduates in the area of performance evaluation of computer communication networks will benefit substantially from this comprehensive and easy-to-follow volume. Professionals will also find it a worthwhile reference text. Professor Yuming Jiang at the Norwegian University of Science and Technology (NTNU) has lectured using the material presented in this text since 2006. Dr Yong Liu works at the Optical Network Laboratory, National University of Singapore, where he researches QoS for optical communication networks and Metro Ethernet networks. 