A basic calculus is presented for stochastic service guarantee analysis in communication networks. Central to the calculus are two definitions, maximum-(virtual)-backlog-centric (m.b.c) stochastic arrival curve and stochastic service curve, which respectively generalize arrival curve and service curve in the deterministic network calculus framework. With m.b.c stochastic arrival curve and stochastic service curve, various basic results are derived under the (min, +) algebra for the general case analysis, which are crucial to the development of stochastic network calculus. These results include (i) superposition of flows, (ii) concatenation of servers, (iii) output characterization, (iv) per-flow service under aggregation, and (v) stochastic backlog and delay guarantees. In addition, to perform independent case analysis, stochastic strict server is defined, which uses an ideal service process and an impairment process to characterize a server. The concept of stochastic strict server not only allows us to improve the basic results (i) -- (v) under the independent case, but also provides a convenient way to find the stochastic service curve of a serve. Moreover, an approach is introduced to find the m.b.c stochastic arrival curve of a flow and the stochastic service curve of a server.
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. We introduce the concept of generalized stochastically bounded burstiness (gSBB) for Internet traffic, the tail distribution of whose burstiness can be bounded by a decreasing function in a function class with few restrictions. This new concept extends the concept of stochastically bounded burstiness (SBB) introduced by previous researchers to a much larger extent - while the SBB model can apply to Gaussian self-similar input processes, such as fractional Brownian motion, gSBB traffic contains non-Gaussian self-similar input processes, such as spl alpha -stable self-similar processes, which are not SBB in general. We develop a network calculus for gSBB traffic. We characterize gSBB traffic by the distribution of its queue size. We explore the property of sums of gSBB traffic and the relation of input and output processes. We apply this calculus to a work-conserving system shared by a number of gSBB sources, to analyze the behavior of output traffic for each source and to estimate the probabilistic bounds for delays. We expect this new calculus to be of particular interest in the implementation of services with statistical qualitative guarantees. 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.   Many communication networks such as wireless networks only provide stochastic service guarantees. For analyzing stochastic service guarantees, research efforts have been made in the past few years to develop stochastic network calculus, a probabilistic version of (min, +) deterministic network calculus. However, many challenges have made the development difficult. Some of them are closely related to server modeling, which include output characterization, concatenation property, stochastic backlog guarantee, stochastic delay guarantee, and per-flow service under aggregation. In this paper, we propose a server model, called stochastic service curve to facilitate stochastic service guarantee analysis. We show that with the concept of stochastic service curve, these challenges can be well addressed. In addition, we introduce strict stochastic server to help find the stochastic service curve of a stochastic server, which characterizes the service of the server by two stochastic processes: an ideal service process and an impairment process. The deterministic network calculus offers an elegant framework for determining delays and backlog in a network with deterministic service guarantees to individual traffic flows. A drawback of the deterministic network calculus is that it only provides worst-case bounds. Here we present a network calculus for statistical service guarantees, which can exploit the statistical multiplexing gain of sources. We introduce the notion of an effective service curve as a probabilistic bound on the service received by an individual flow, and construct an effective service curve for a network where capacities are provisioned exclusively to aggregates of flows. Numerical examples demonstrate that the calculus is able to extract a significant amount of multiplexing gain in networks with a large number of flows. A method for evaluating the performance of packet switching communication networks under a fixed, session-based, routing strategy is proposed. The approach is based on properly bounding the probability distribution functions of the system input processes. The suggested bounds which are decaying exponentials, possess three convenient properties. When the inputs to an isolated network element are all bounded, they result in bounded outputs and assure that the delays and queues in this element have exponentially decaying distributions. In some network settings, bounded inputs result in bounded outputs. Natural traffic processes can be shown to satisfy such bounds. Consequently, this method enables the analysis of various previously intractable setups. Sufficient conditions are provided for the stability of such networks, and derive upper bounds for the parameters of network performance are derived. > In most network models for quality of service support, the communication links interconnecting the switches and gateways are assumed to have fixed bandwidth and zero error rate. This assumption of steadiness, especially in a heterogeneous internet-working environment, might be invalid owing to subnetwork multiple-access mechanism, link-level flow error control, and user mobility. Techniques are presented in this paper to characterize and analyze work-conserving communication nodes with varying output rate. In the deterministic approach, the notion of "fluctuation constraint," analogous to the "burstiness constraint" for traffic characterization, is introduced to characterize the node. In the statistical approach, the variable-rate output is modelled as an "exponentially bounded fluctuation" process in a way similar to the "exponentially bounded burstiness" method for traffic modelling. Based on these concepts, deterministic and statistical bounds on queue size and packet delay in isolated variable-rate communication server-nodes are derived, including cases of single-input and multiple-input under first-come-first-serve queueing. Queue size bounds are shown to be useful for buffer requirement and packet loss probability estimation at individual nodes. Our formulations also facilitate the computation of end-to-end performance bounds across a feedforward network of variable-rate server-nodes. Several numerical examples of interest are given in the discussion. The issue of Quality of Service (QoS) performance analysis in packet switching networks has drawn a lot of attention in the networking community in recent years. There is a lot of work including an elegant theory under the name of network calculus focusing on analysis of deterministic worst case QoS performance bounds. In the meantime, other researchers have studied the stochastic QoS performance for specific schedulers. As yet, there has been no systematic investigation and analysis of end-to-end stochastic QoS performance. On the other hand, most of the previous work on deterministic QoS analysis or stochastic QoS analysis only considered a server which provides deterministic service, i.e. deterministically bounded rate service. Few works have considered the behavior of a stochastic server providing input flows with variable rate service. In this report, we propose a stochastic network calculus to systematically analyze the end-to-end stochastic QoS performance of a system with stochastically bounded input traffic over a series of deterministic and stochastic servers. The proposed framework is also applied to analyze per-flow stochastic QoS performance since a server serving an aggregate of flows can be regarded as a stochastic server for individual flows within the aggregate under aggregate scheduling. Keywords Stochastic Modeling, Network Calculus, Quality of Service We propose a probabilistic characterization of network traffic. This characterization can handle traffic with heavy-tailed distributions in performance analysis. We show that queue size, output traffic, virtual delay, aggregate traffic, etc. at various points in a network can easily be characterized within the framework. This characterization is measurable and allows for a simple probabilistic method for regulating network traffic. All of these properties of the proposed characterization enable a systematic approach for providing end-to-end probabilistic QoS guarantees 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 O(Hlog H), where H is the number of nodes traversed by a flow. Using currently available techniques that compute end-to-end bounds by adding single node results, the corresponding performance measures are bounded by O(H3).