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.
Another type is built upon moments or moment generating functions. This type was initially used for traffic @cite_10 @cite_8 and has also been extended to service @cite_20 @cite_15 . Independence assumption is generally required between arrival and service processes. Extensive study has been conducted for deriving the characteristics of a process under this type of model from some known characterization of the process @cite_10 @cite_24 @cite_20 . Main open problems for this type are the concatenation property (P.2) and the general case analysis. Although these problems are out of the scope of this paper, we prove in Section results that relate the moment generating function model to the proposed m.b.c stochastic arrival curve and stochastic service curve. These results will allow to further relate known traffic service characterization to the proposed traffic and service models in this paper.
@cite_8 @cite_24 @cite_15 @cite_10 @cite_20
2090888999 2112919802 2115632051 2111764355 1978905175
A crucial problem for the efficient design and management of integrated services networks is how to best allocate network resources for heterogeneous and bursty traffic streams in multiplexers that support prioritized service disciplines. In this paper, we introduce a new approach for determining per-connection performance parameters such as delay-bound violation probability and loss probability in multi-service networks. The approach utilizes a traffic characterization consisting of the variances of a stream's rate distribution over multiple interval lengths, which captures its burstiness properties and autocorrelation structure. From this traffic characterization, we provide a simple and efficient resource allocation algorithm by deriving stochastic delay-bounds for static priority schedulers and employing a Gaussian approximation over intervals. To evaluate the scheme, we perform trace-driven simulation experiments with long traces of MPEG-compressed video and show that our approach is accurate enough to capture most of the inherent statistical multiplexing gain, achieving average network utilizations of up to 90 for these traces and substantially outperforming previous "effective bandwidth" techniques. Considers stochastic linear systems under the max-plus algebra. For such a system, the states are governed by the recursive equation X sub n =A sub n spl otimes X sub n-1 spl oplus U sub n with the initial condition condition X sub 0 =x sub 0 . By transforming the linear system under the max-plus algebra into a sublinear system under the usual algebra, we establish various exponential upper bounds for the tail distributions of the states X sub n under the independently identically distributed (i.i.d.) assumption on (A sub n ,U sub n ) sub 1 n spl ges 1 and a couple of regularity conditions on (A sub 1 ,U sub 1 ) and the initial condition x sub 0 . These upper bounds are related to the spectral radius (or the Perron-Frobenius eigenvalue) of the nonnegative matrix in which each element is the moment generating function of the corresponding element in the state-feedback matrix A sub 1 . In particular, we have Kingman's upper bound for GI GI 1 queue when the system is one-dimensional. We also show that some of these upper bounds can be achieved if A sub 1 is lower triangular. These bounds are applied to some commonly used systems to derive new results or strengthen known results. To facilitate the efficient support of quality of service (QoS) in next-generation wireless networks, it is essential to model a wireless channel in terms of connection-level QoS metrics such as data rate, delay, and delay-violation probability. However, the existing wireless channel models, i.e., physical-layer channel models, do not explicitly characterize a wireless channel in terms of these QoS metrics. In this paper, we propose and develop a link-layer channel model termed effective capacity (EC). In this approach, we first model a wireless link by two EC functions, namely, the probability of nonempty buffer, and the QoS exponent of a connection. Then, we propose a simple and efficient algorithm to estimate these EC functions. The physical-layer analogs of these two link-layer EC functions are the marginal distribution (e.g., Rayleigh-Ricean distribution) and the Doppler spectrum, respectively. The key advantages of the EC link-layer modeling and estimation are: 1) ease of translation into QoS guarantees, such as delay bounds; 2) simplicity of implementation; and 3) accuracy, and hence, efficiency in admission control and resource reservation. We illustrate the advantage of our approach with a set of simulation experiments, which show that the actual QoS metric is closely approximated by the QoS metric predicted by the EC link-layer model, under a wide range of conditions. We present two types of stability problems: 1) conditions for queueing networks that render bounded queue lengths and bounded delay for customers, and 2) conditions for queueing networks in which the queue length distribution of a queue has an exponential tail with rate spl theta . To answer these two types of stability problems, we introduce two new notions of traffic characterization: minimum envelope rate (MER) and MER with respect to spl theta . We also develop a set of rules for network operations such as superposition, input-output relation of a single queue, and routing. Specifically, we show that: 1) the MER of a superposition process is less than or equal to the sum of the MER of each process, 2) a queue is stable in the sense of bounded queue length if the MER of the input traffic is smaller than the capacity, 3) the MER of a departure process from a stable queue is less than or equal to that of the input process, and 4) the MER of a routed process from a departure process is less than or equal to the MER of the departure process multiplied by the MER of the routing process. Similar results hold for MER with respect to spl theta under a further assumption of independence. For single class networks with nonfeedforward routing, we provide a new method to show that similar stability results hold for such networks under the first come, first served policy. Moreover, when restricting to the family of two-state Markov modulated arrival processes, the notion of MER with respect to spl theta is shown to be equivalent to the recently developed notion of effective bandwidth in communication networks. > From the Publisher: Providing performance guarantees is one of the most important issues for future telecommunication networks. This book describes theoretical developments in performance guarantees for telecommunication networks from the last decade. Written for the benefit of graduate students and scientists interested in telecommunications-network performance this book consists of two parts.