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.
One type uses a sequence of random variables to stochastically bound the arrival process @cite_34 or the service process @cite_38 . Similar properties as (P.1), (P.3), (P.4) and (P.5) have been studied @cite_34 @cite_38 . These studies generally need the independence assumption. Under this type of traffic and service models, several problems remain open, which are out of the scope of this paper. One is the concatenation property (P.2), another is the general case analysis and the third is researching designing approaches to map known traffic and service characterizations to the required sequences of random variables.
@cite_38 @cite_34
2062706778 1985431233
Networks that support multiple services through "link-sharing" must address the fundamental conflicting requirement between isolation among service classes to satisfy each class' quality of service requirements, and statistical sharing of resources for efficient network utilization. While a number of service disciplines have been devised which provide mechanisms to both isolate flows and fairly share excess capacity, admission control algorithms are needed which exploit the effects of inter-class resource sharing. In this paper, we develop a framework of using statistical service envelopes to study inter-class statistical resource sharing. We show how this service envelope enables a class to over-book resources beyond its deterministically guaranteed capacity by statistically characterizing the excess service available due to fluctuating demands of other service classes. We apply our techniques to several multi-class schedulers, including generalized processor sharing, and design new admission control algorithms for multi-class link-sharing environments. We quantify the utilization gains of our approach with a set of experiments using long traces of compressed video. We present a technique for computing upper bounds on the distribution of individual per-session performance measures such as delay and buffer occupancy for networks in which sessions may be routed over several “hops.” Our approach is based on first stochastically bounding the distribution of the number of packets (or cells) which can be generated by each traffic source over various lengths of time and then “pushing” these bounds (which are then shown to hold over new time interval lengths at various network queues) through the network on a per-session basis. Session performance bounds can then be computed once the stochastic bounds on the arrival process have been characterized for each session at all network nodes. A numerical example is presented and the resulting distributional bounds compared with simulation as well as with a point-valued worst-case performance bound.