We present a robust method to analyze a broad range of classical queueing models, e.g., the GI/G/1 queue with renewal arrivals, an AR/G/1 queue with alternating renewals (AR), as a special class of Semi-Markovian processes, and Markovian fluids queues. At the core of the method lies a standard change-of-measure argument to reverse the sign of the negative drift in the underlying random walks. Combined with a suitable representation of the overshoot, we obtain exact results in terms of series. Closed-form and computationally fast bounds follow by taking the series’ first terms, which are the dominant ones because of the positive drift under the new probability measure. The obtained bounds generalize the state-of-the-art class of martingale bounds and can be much sharper by orders of magnitude.

We construct a continuous-time martingale to analyze two queueing systems: One is the GIX/M/1 queue with light-tailed batch arrivals for which we obtain the first exact result in closed-form when X has a Geometric distribution, and stochastic bounds otherwise. The second application concerns queues with Semi-Markovian (SM) inter-arrival times; of particular interest is the scenario with multiplexed SM sources whose aggregate loses the SM property. Unlike existing exact but implicit solutions which rely on numerical transform methods, even in the Mr/M/1 case, our stochastic bounds are in closed-form and shown to be (mostly) numerically accurate.

Task replication has been advocated as a practical solution to reduce response times in parallel systems. The analysis of replication-based systems typically rests on some strong assumptions: Poisson arrivals, exponential service times, or independent service times of the replicas. This study is motivated not only by several studies which indicate that these assumptions are unrealistic, but also by some elementary observations highlighting some contriving behaviour. For instance, when service times are not exponential, adding a replication factor can stabilize an unstable system, i.e., having infinite delays, but a tempting higher replication factor can push the system back in a perilous unstable state. This behaviour disappears however if the replicas are sufficiently correlated, in which case any replication factor would even be detrimental.Motivated by the need to dispense with such common yet unrealistic and misleading assumptions, we provide a robust theoretical framework to compute stochastic bounds on response time distributions in general replication systems subject to Markovian arrivals, quite general service times, and correlated replicas. Numerical results show that our bounds are accurate and improve state-of-the-art bounds in the case of Markovian arrivals by as much as three orders of magnitude. We apply our results to a practical application and highlight that correctly setting the replication factor crucially depends on both the service time distributions of the replicas and the degree of correlation amongst.

We analyse a data-processing system with n clients producing jobs which are processed in batches by m parallel servers; the system throughput critically depends on the batch size and a corresponding sub-additive speedup function. In practice, throughput optimization relies on numerical searches for the optimal batch size, a process that can take up to multiple days in existing commercial systems. In this paper, we model the system in terms of a closed queueing network; a standard Markovian analysis yields the optimal throughput in ωn4 time. Our main contribution is a mean-field model of the system for the regime where the system size is large. We show that the mean-field model has a unique, globally attractive stationary point which can be found in closed form and which characterizes the asymptotic throughput of the system as a function of the batch size. Using this expression we find the asymptotically optimal throughput in O(1) time. Numerical settings from a large commercial system reveal that this asymptotic optimum is accurate in practical finite regimes.

Multi-tenant distributed systems composed of small services, such as Service-oriented Architectures (SOAs) and Micro-services, raise new challenges in attaining high performance and efficient resource utilization. In these systems, a request execution spans tens to thousands of processes, and the execution paths and resource demands on different services are generally not known when a request first enters the system. In this paper, we highlight the fundamental challenges of regulating load and scheduling in SOAs while meeting end-to-end performance objectives on metrics of concern to both tenants and operators. We design Wisp, a framework for building SOAs that transparently adapts rate limiters and request schedulers system-wide according to operator policies to satisfy end-to-end goals while responding to changing system conditions. In evaluations against production as well as synthetic workloads, Wisp successfully enforces a range of end-to-end performance objectives, such as reducing average latencies, meeting deadlines, providing fairness and isolation, and avoiding system overload.

Randomized load balancing is a cost efficient policy for jobscheduling in parallel server queueing systems whereby, with everyincoming job, a central dispatcher randomly polls some servers andselects the one with the smallest queue. By exactly deriving thejobs' delay distribution in such systems, in explicit and closedform, Mitzenmacher [13] proved the so-called 'power-of-two' result, which states that the random polling of only two serversyields an exponential improvement in delay over randomly selectinga single server. Such a fundamental result, however, was obtainedin an asymptotic regime in the total number of servers, and doesdo not necessarily provide accurate estimates for practical finiteregimes with small or moderate number of servers. In this paper weobtain stochastic lower and upper bounds on the jobs' averagedelay in non-asymptotic/finite regimes, by extending ideas foranalyzing the particular case of the Join-the-Shortest-Queue (JSQ) policy. Numerical illustrations indicate not only that the (lower) bounds are remarkably accurate, but also that the asymptoticapproximation can be misleading in scenarios with a small numberof servers, and especially at very high utilizations.

Task replication has recently been advocated as a practical solution to reduce latencies in parallel systems. In addition to several convincing empirical studies, analytical results have been provided, yet under some strong assumptions such as independent service times of the replicas, which may lend themselves to some contrasting and perhaps contriving behavior. For instance, under the independence assumption, an overloaded system can be stabilized by a replication factor, but can be sent back in overload through further replication. Motivated by the need to dispense with such common and restricting assumptions, which may cause unexpected behavior, we develop a unified and general theoretical framework to compute tight bounds on the distribution of response times in general replication systems. These results immediately lend themselves to the optimal number of replicas minimizing response time quantiles, depending on the parameters of the system (e.g., the degree of correlation amongst replicas).

This paper analyzes queueing behavior subject to multiplexing a stochastic process M(n) of flows, and not a constant as conventionally assumed. By first considering the case when M(n) is iid, it is shown that flows' multiplexing `hurts' the queue size (i.e., the queue size increases in distribution). The simplicity of the iid case enables the quantification of the `best' and `worst' distributions of M(n), i.e., minimizing/maximizing the queue size. The more general, and also realistic, case when M(n) is Markov-modulated reveals an interesting behavior: flows' multiplexing `hurts' but only when the multiplexed flows are sufficiently long. An important caveat raised by such observations is that the conventional approximation of M(n) by a constant can be very misleading for queueing analysis.

Amongst data center structures, flattened butterfly (FBFly) networks have been shown to outperform their common counterparts such as fat-trees in terms of energy proportionality and cost efficiency. This efficiency is achieved by using less networking equipment (switches, ports, cables) at the expense of increased control plane complexity. In this paper we show that cabling complexity can be further reduced by an order of magnitude, by reconfiguring the optical fully meshed components into optical “pseudo”-fully meshed components. Following established methods, optical star networks are obtained by exchanging the FBFly's regular (grey) optical transceivers for dense wavelength division multiplexing (DWDM or colored) optical transceivers and placing an arrayed waveguide grating router (AWGR) in the center. Depending on the data center configuration and equipment prices, our colored FBFly (C-FBFly) proposal yields lower capital expenditure than the original FBFly. The key advantage of our structural modification of FBFly, however, is that in large FBFly networks (e.g., > 50K nodes) it reduces the number of inter-rack cables by a factor as large as 48.

This paper proposes a martingale extension of effective-capacity, a concept which has been instrumental in teletraffic theory to model the link-layer wireless channel and analyze QoS metrics. Together with a recently developed concept of an arrival-martingale, the proposed service-martingale concept enables the queueing analysis of a bursty source sharing a MAC channel. In particular, the paper derives the first rigorous and accurate stochastic delay bounds for a Markovian source sharing either an Aloha or CSMA/CA channel, and further considers two extended scenarios accounting for 1) in-source scheduling and 2) spatial multiplexing MIMO. By leveraging the powerful martingale methodology, the obtained bounds are remarkably tight and improve state-of-the-art bounds by several orders of magnitude. Moreover, the obtained bounds indicate that MIMO spatial multiplexing is subject to the fundamental power-of-two phenomena.

In a Fork-Join (FJ) queueing system an upstream fork station splits incoming jobs into N tasks to be further processed by N parallel servers, each with its own queue; the response time of one job is determined, at a downstream join station, by the maximum of the corresponding tasks' response times. This queueing system is useful to the modelling of multi-service systems subject to synchronization constraints, such as MapReduce clusters or multipath routing. Despite their apparent simplicity, FJ systems are hard to analyze.

Despite decades of operational experience and focused research efforts, standards for sizing and configuring buffers in network systems remain controversial. An extreme example of this is the recent claim that excessive buffering (i.e., bufferbloat) can severely impact Internet services. In this paper, we systematically examine the implications of buffer sizing choices from the perspective of factors impacting end user experience. To assess user perception of application quality under various buffer sizing schemes we employ Quality of Experience (QoE) metrics. We evaluate these metrics over a wide range of end-user applications (e.g., web browsing, VoIP, and RTP video streaming) and workloads in two realistic testbeds emulating access and backbone networks. The main finding of our extensive evaluations is that network workload, rather than buffer size, is the primary determinant of end user QoE. Our results also highlight the relatively narrow conditions under which bufferbloat seriously degrades QoE, i.e., when buffers are oversized and sustainably filled.

In asymptotic regimes, both in time and space (network size), the derivation of network capacity results is grossly simplified by brushing aside queueing behavior in nonJackson networks. This simplifying double-limit model, however, lends itself to conservative numerical results in finite regimes. To properly account for queueing behavior beyond a simple calculus based on average rates, we advocate a system theoretic methodology for the capacity problem in finite time and space regimes. This methodology also accounts for spatial correlations arising in networks with CSMA/CA scheduling and it delivers rigorous closed-form capacity results in terms of probability distributions. Unlike numerous existing asymptotic results, subject to anecdotal practical concerns, our transient results can be used in practical settings, e.g., to compute the time scales at which multi-hop routing is more advantageous than single-hop routing.

The practicality of the stochastic network calculus (SNC) is often questioned on grounds of potential looseness of its performance bounds. In this paper, it is uncovered that for bursty arrival processes (specifically Markov-Modulated On-Off (MMOO)), whose amenability to per-flow analysis is typically proclaimed as a highlight of SNC, the bounds can unfortunately be very loose (e.g., by several orders of magnitude off). In response to this uncovered weakness of SNC, the (Standard) per-flow bounds are herein improved by deriving a general sample-path bound, using martingale based techniques, which accommodates FIFO, SP, and EDF scheduling. The obtained (Martingale) bounds capture an extra exponential decay factor of O (e−αn) in the number of flows n. Moreover, numerical comparisons against simulations show that the Martingale bounds are not only remarkably accurate, but they also improve the Standard SNC bounds by factors as large as 100 or even 1000.

This paper investigates the throughput capacity of a flow crossing a multi-hop wireless network, whose geometry is characterized by general randomness laws including Uniform, Poisson, Heavy-Tailed distributions for both the nodes' densities and the number of hops. The key contribution is to demonstrate how the per-flow throughput depends on the distribution of 1) the number of nodes Njinside hops' interference sets, 2) the number of hops K, and 3) the degree of spatial correlations. The randomness in both Nj's and K is advantageous, i.e., it can yield larger scalings (as large as Θ(n)) than in non-random settings. An interesting consequence is that the per-flow capacity can exhibit the opposite behavior to the network capacity, which was shown to suffer from a logarithmic decrease in the presence of randomness. In turn, spatial correlations along the end-to-end path are detrimental by a logarithmic term.

This paper analyzes queueing behavior in queues with a random number of parallel flows, and not static as typically assumed. By deriving upper and lower bounds on the queue size distribution, the paper identifies extremal properties in such dynamic queues. The extremal best-case distribution (minimizing the queue) is simply the constant, whereas the worst-case distribution (maximizing the queue) has a bimodal structure. From a more practical point of view, this paper highlights an idiosyncrasy of dynamic queues: unlike in static queues whereby capacity dimensioning is dominated by average-values (subject to certain safety margins), in dynamic queues the capacity dimensioning is dominated instead by peak-values.

TTL caching models have recently regained significant research interest, largely due to their ability to fit popular caching policies such as LRU. In this extended abstract we briefly describe our recent work on two exact methods to analyze TTL cache networks. The first method generalizes existing results for line networks under renewal requests to the broad class of caching policies whereby evictions are driven by stopping times. The obtained results are further generalized, using the second method, to feedforward networks with Markov arrival processes (MAP) requests. MAPs are particularly suitable for non-line networks because they are closed not only under superposition and splitting, as known, but also under input-output caching operations as proven herein for phase-type TTL distributions. The crucial benefit of the two closure properties is that they jointly enable the first exact analysis of feedforward networks of TTL caches in great generality.

Energy consumption imposes a significant cost for data centers; yet much of that energy is used to maintain excess service capacity during periods of predictably low load. Resultantly, there has recently been interest in developing designs that allow the service capacity to be dynamically resized to match the current workload. However, there is still much debate about the value of such approaches in real settings. In this paper, we show that the value of dynamic resizing is highly dependent on statistics of the workload process. In particular, both slow time-scale non-stationarities of the workload (e.g., the peak-to-mean ratio) and the fast time-scale stochasticity (e.g., the burstiness of arrivals) play key roles. To illustrate the impact of these factors, we combine optimization-based modeling of the slow time-scale with stochastic modeling of the fast time scale.

The practicality of the stochastic network calculus (SNC) is often questioned on grounds of potential looseness of its performance bounds. In this paper it is uncovered that for bursty arrival processes (specifically Markov-Modulated On-Off (MMOO)), whose amenability to per-flow analysis is typically proclaimed as a highlight of SNC, the bounds can unfortunately indeed be very loose (e.g., by several orders of magnitude off). In response to this uncovered weakness of SNC, the (Standard) per-flow bounds are herein improved by deriving a general sample-path bound, using martingale based techniques, which accommodates FIFO, SP, and EDF scheduling disciplines. The obtained (Martingale) bounds capture an additional exponential decay factor of O(e-α n) in the number of flows $n$, and are remarkably accurate even in multiplexing scenarios with few flows.

The high variability of solar power due to intrinsic diurnal variability, as well as additional stochastic variations due to cloud cover, have made it difficult for solar farms to participate in electricity markets that require pre-committed constant power generation. We study the use of battery storage to 'firm' solar power, that is, to remove variability so that such a pre-commitment can be made. Due to the high cost of storage, it is necessary to size the battery parsimoniously, choosing the minimum size to meet a certain reliability guarantee. Inspired by recent work that identifies an isomorphism between batteries and network buffers, we introduce a new model for solar power generation that models it as a stochastic traffic source. This permits us to use techniques from the stochastic network calculus to both size storage and to maximize the revenue that a solar farm owner can make from the day-ahead power market. Using a 10-year of recorded solar irradiance, we show that our approach attains 93% of the maximum revenue in a summer day that would have been achieved in daily market had the entire solar irradiance trace been known ahead of time.

This paper investigates the origins of the spamming process, specifically concerning address harvesting on the web, by relying on an extensive measurement data set spanning over three years. Concretely, we embedded more than 23 million unique spamtrap addresses in web pages. 0.5% of the embedded trap addresses received a total of 620,000 spam messages. Besides the scale of the experiment, the critical aspect of our methodology is the uniqueness of the issued spamtrap addresses, which enables the mapping of crawling activities to the actual spamming process.

ACM Sigcomm 2006 published a paper [26] which was perceived to unify the deterministic and stochastic branches of the network calculus (abbreviated throughout as DNC and SNC) [39]. Unfortunately, this seemingly fundamental unification---which has raised the hope of a straightforward transfer of all results from DNC to SNC---is invalid. To substantiate this claim, we demonstrate that for the class of stationary and ergodic processes, which is prevalent in traffic modelling, the probabilistic arrival model from [26] is quasi-deterministic, i.e., the underlying probabilities are either zero or one. Thus, the probabilistic framework from [26] is unable to account for statistical multiplexing gain, which is in fact the raison d'être of packet-switched networks. Other previous formulations of SNC can capture statistical multiplexing gain, yet require additional assumptions [12], [22] or are more involved [14], [9] [28], and do not allow for a straightforward transfer of results from DNC. So, in essence, there is no free lunch in this endeavor.

Energy consumption imposes a significant cost for data centers; yet much of that energy is used to maintain excess service capacity during periods of predictably low load. Resultantly, there has recently been interest in developing designs that allow the service capacity to be dynamically resized to match the current workload. However, there is still much debate about the value of such approaches in real settings. In this paper, we show that the value of dynamic resizing is highly dependent on statistics of the workload process. In particular, both slow time-scale non-stationarities of the workload (e.g., the peak-to-mean ratio) and the fast time-scale stochasticity (e.g., the burstiness of arrivals) play key roles. To illustrate the impact of these factors, we combine optimization-based modeling of the slow time-scale with stochastic modeling of the fast time scale. Within this framework, we provide both analytic and numerical results characterizing when dynamic resizing does (and does not) provide benefits.

Renewable energy such as solar and wind generation will constitute an important part of the future grid. As the availability of renewable sources may not match the load, energy storage is essential for grid stability. In this paper we investigate the feasibility of integrating solar photovoltaic (PV) panels and wind turbines into the grid by also accounting for energy storage. To deal with the fluctuation in both the power supply and demand, we extend and apply stochastic network calculus to analyze the power supply reliability with various renewable energy configurations. To illustrate the validity of the model, we conduct a case study for the integration of renewable energy sources into the power system of an island off the coast of Southern California. In particular, we asses the power supply reliability in terms of the average Fraction of Time that energy is Not-Served (FTNS).

Traffic with self-similar and heavy-tailed characteristics has been widely reported in communication networks, yet, the state-of-the-art of analytically predicting the delay performance of such networks is lacking. This work addresses heavy-tailed traffic that has a finite first moment, but no second moment, and presents end-to-end delay bounds for such traffic. The derived performance bounds are non-asymptotic in that they do not assume a steady state, large buffer, or many sources regime. The analysis follows a network calculus approach where traffic is characterized by envelope functions and service is described by service curves. The system model is a multi-hop path of fixed-capacity links with heavy-tailed self-similar cross traffic at each node. A key contribution of the paper is a probabilistic sample-path bound for heavy-tailed arrival and service processes, which is based on a scale-free sampling method. The paper explores how delay bounds scale as a function of the length of the path, and compares them with lower bounds. A comparison with simulations illustrates pitfalls when simulating self-similar heavy-tailed traffic, providing further evidence for the need of analytical bounds.

Ensuring a high customer satisfaction by monitoring Quality of Experience (QoE) aspects has become common practice for service providers. Such monitoring solutions, together with underlying QoE models, are mostly limited to measures captured in the core or access network and may thus neglect the QoE impact of recovery mechanisms deployed at client-side, e.g., FEC or ARQ. This limitation makes QoE models prone to mispredict QoE and consequently may lead the operators to misleading interpretations of customer experience. In this paper, we empirically study the behavior of the Microsoft TV Set-top Box (STB) with respect to the deployed ARQ recovery mechanism. As the ARQ implementation details of the STB are proprietary, we implement and simulate three ARQ algorithms of different complexities and evaluate their performance by comparing with corresponding empirical measurements. This comparison reveals insights into the ARQ scheme implemented in the STB. Moreover, it leads us to speculate that MSTV uses simple ARQ schemes which are sufficient to drastically improve the QoE in the presence of a multitude of loss patterns.

Many of computing and communication systems are based on FIFO queues whose performance, e.g., in terms of throughput and fairness, is highly influenced by load fluctuations, especially in the case of short-term overload. This paper analytically proves that, for both Markovian and heavy-tailed/self-similar arrivals, overloaded FIFO queues are asymptotically fair in the sense that each flow or aggregate of flows receives a weighted fair share over large time scales. In addition, the paper provides the corresponding transient results and convergence rates, i.e., the amount of time it takes for a flow to probabilistically attain the fair share. Interestingly, for Markovian arrivals, the paper indicates smaller convergence rates at higher utilizations, which is exactly the opposite behavior characteristic to underloaded queueing systems.

Convolution-form networks have the property that the end-to-end service of network flows can be expressed in terms of a (min, +)-convolution of the per-node services. This property is instrumental for deriving end-to-end queueing results which fundamentally improve upon alternative results derived by a node-by-node analysis. This paper extends the class of convolution-form networks with stochastic settings to scenarios with flow transformations, e.g., by loss, dynamic routing or retransmissions. In these networks, it is shown that by using the tools developed in this paper end-to-end delays grow as O(n) in the number of nodes n; in contrast, by using the alternative node-by-node analysis, end-to-end delays grow as O(n2).

The practicality of available (throughput) capacity results in multi-access networks, which dispense with coding schemes, is often questioned for several reasons including 1) the underlying asymptotic regimes, and 2) the assumption of saturated traffic sources. This paper jointly addresses these limitations by providing capacity results in non-asymptotic regimes, i.e., holding at all time scales and network sizes, for the very broad class of exponentially bounded burstiness (EBB) traffic sources. Both upper and lower bounds on capacity are derived in terms of probability distributions, which immediately yield all the moments. The explicit and closed-form nature of the results enable the investigation of the impact of burstiness on non-asymptotic network capacity. In particular, the results show that for the EBB class the non-asymptotic end-to-end capacity rate decays linearly in the number of hops.

The class of Gupta-Kumar results, which predict the throughput capacity in wireless networks, is restricted to asymptotic regimes. This tutorial presents a methodology to address a corresponding non-asymptotic analysis based on the framework of the stochastic network calculus, in a rigorous mathematical manner. In particular, we derive explicit closed-form results on the distribution of the end-to-end capacity and delay, for a fixed source-destination pair, in a network with broad assumptions on its topology and degree of spatial correlations. The results are non-asymptotic in that they hold for finite time scales and network sizes, as well as bursty arrivals. The generality of the results enables the research of several interesting problems, concerning for instance the effects of time scales or randomness in topology on the network capacity.

We investigate scaling properties of end-to-end delays in packet networks for a flow that traverses a sequence ofHnodes and that experiences cross traffic at each node. When the traffic flow and the cross traffic do not satisfy independence assumptions, we find that delay bounds scale faster than linearly. More precisely, for exponentially bounded packetized traffic, we show that delays grow with Θ(HlogH) in the number of nodes on the network path. This superlinear scaling of delays is qualitatively different from the scaling behavior predicted by a worst-case analysis or by a probabilistic analysis assuming independence of traffic arrivals at network nodes.

The stochastic network calculus is an analytical tool which was mainly developed to compute tail bounds on backlogs and delays. From these, bounds on average backlogs and delays are derived in the literature by integration. This paper improves such bounds on average backlogs by using Jensen's inequality; improved bounds on average delays follow immediately from Little's Law. The gain factor can be substantial especially at high utilizations, e.g., of order Ω (1/1-ρ ) when ρ → 1. This gain is further numerically illustrated for Markov-modulated On-Off arrival processes. Moreover, the paper shows how to improve standard stochastic network calculus performance bounds by suitably using FIFO service curves.

Traffic with self-similar and heavy-tailed characteristics has been widely reported in networks, yet, only few analytical results are available for predicting the delay performance of such networks. We address a particularly difficult type of heavy-tailed traffic where only the first moment can be computed, and present the first non-asymptotic end-to-end delay bounds for such traffic. The derived performance bounds are non-asymptotic in that they do not assume a steady state, large buffer, or many sources regime. Our analysis considers a multi-hop path of fixed-capacity links with heavy-tailed self-similar cross traffic at each node. A key contribution of the analysis is a probabilistic sample-path bound for heavy-tailed arrival and service processes, which is based on a scale-free sampling method. We explore how delays scale as a function of the length of the path, and compare them with lower bounds. A comparison with simulations illustrates pitfalls when simulating self-similar heavy-tailed traffic, providing further evidence for the need of analytical bounds.

Recent findings showing that the output of traffic flows at packet switches has similar characteristics as the corresponding input enable a decomposition analysis of a network where nodes can be studied in isolation, thus simplifying an end- to-end analysis of networks. However, network decomposition results currently available are mostly many-sources asymptotics. In this paper we explore the viability of network decomposition in a non-asymptotic regime with a finite number of flows. For traffic with Exponentially Bounded Burstiness (EBB) we derive statistical bounds for the output traffic at a FIFO buffer and compare them with bounds on the input. By evaluating the accuracy of the output bounds with exact results available for special cases and by using numerical examples we find that conditions for network decomposition appear favorable even if the number of flows is relatively small.

A recent result in network calculus theory provided statistical delay bounds for exponentially bounded traffic that grow as O(H log H) with the number of nodes on the network path. In this paper we establish the corresponding lower bound which shows that for such such types of traffic, typical end-to-end delays can indeed grow as Theta (H log H). The lower bound is obtained by analyzing the end-to-end delay in a tandem network where each packet maintains the same service time at each traversed node. The results of this paper provide conclusive evidence that, in general, delays have a qualitatively different scaling behavior than is suggested by a worst-case analysis or by an analysis that assumes independent service times at network nodes.

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/).

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).

Multiplexing gain has been studied extensively in the context of statistical characterizations of traffic streams with quality-of-service criteria such as packet loss probability, mean delay, and delay variance. In this paper, we demonstrate that multiplexing gain can also arise in the context of deterministic traffic constraint functions, service curve scheduling, and quality-of-service requirements based on deterministic delay constraints. We show how to evaluate this multiplexing gain via the use of deterministic network calculus for both worst-case and time-averaged delay constraints. We show that significant multiplexing gain can be achieved in a deterministic setting using numerical examples drawn from a number of well-known MPEG video traces. Our results have application to provisioning services with tight, real-time constraints on end-to-end delay performance.