Feedback mechanisms are integral components of network protocols and traffic control algorithms. Their performance evaluation is hard due to intricate time correlations introduced by feedback. Network calculus has been successfully applied for the analysis of feedback mechanisms in deterministic systems. However, an extension to random systems has remained an open problem for more than a decade. We present a stochastic network calculus analysis of a random system with feedback, specifically, a window flow control system with random service and fixed feedback delay. We quantify the service impediment due to the feedback mechanism by deriving statistical lower bounds on the available service, and obtain complementary upper bounds. We also discover special cases where an exact description of the service is feasible.

A fundamental problem for the delay and backlog analysis across multihop paths in wireless networks is how to account for the random properties of the wireless channel. Since the usual statistical models for radio signals in a propagation environment do not lend themselves easily to a description of the available service rate, the performance analysis of wireless networks has resorted to higher-layer abstractions, e.g., using Markov chain models. In this paper, we propose a network calculus that can incorporate common statistical models of fading channels and obtain statistical bounds on delay and backlog across multiple nodes. We conduct the analysis in a transfer domain, where the service process at a link is characterized by the instantaneous signal-to-noise ratio at the receiver. We discover that, in the transfer domain, the network model is governed by a dioid algebra, which we refer to as the (min, ×) algebra. Using this algebra, we derive the desired delay and backlog bounds. Using arguments from large deviations theory, we show that the bounds are asymptotically tight. An application of the analysis is demonstrated for a multihop network of Rayleigh fading channels with cross traffic at each hop.

A fundamental problem for the delay and backlog analysis across multi-hop paths in wireless networks is how to account for the random properties of the wireless channel. Since the usual statistical models for radio signals in a propagation environment do not lend themselves easily to a description of the available service rate, the performance analysis of wireless networks has resorted to higher-layer abstractions, e.g., using Markov chain models. In this work, we propose a network calculus that can incorporate common statistical models of fading channels and obtain statistical bounds on delay and backlog across multiple nodes. We conduct the analysis in a transfer domain, which we refer to as the SNR domain, where the service process at a link is characterized by the instantaneous signal-to-noise ratio at the receiver. We discover that, in the transfer domain, the network model is governed by a dioid algebra, which we refer to as (min, ×) algebra. Using this algebra we derive the desired delay and backlog bounds. An application of the analysis is demonstrated for a simple multi-hop network with Rayleigh fading channels.

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.

We study how the choice of packet scheduling algorithms influences end-to-end performance on long network paths. Taking a network calculus approach, we consider both deterministic and statistical performance metrics. A key enabling contribution for our analysis is a significantly sharpened method for computing a statistical bound for the service given to a flow by the network as a whole. For a suitably parsimonious traffic model we develop closed-form expressions for end-to-end delays, backlog, and output burstiness. The deterministic versions of our bounds yield optimal bounds on end-to-end backlog and output burstiness for some schedulers, and are highly accurate for end-to-end delay bounds.

We seek to provide an analytical answer whether the impact of link scheduling algorithms on end-to-end delays diminishes on long network paths. The answer is provided through a detailed multi-hop delay analysis, which is applicable to a broad class of scheduling algorithms, and which can account for statistical multiplexing. The analysis is enabled by two contributions: (1) We derive a function that can characterize the available bandwidth at a buffered link for various scheduling algorithms. This characterization is sharp enough to provide necessary and sufficient conditions for satisfying worst-case delay bounds at a single link; (2) We obtain end-to-end delay bounds by solving an optimization problem, in which the service received on a multi-hop path is subsumed into a single function. Since our analysis captures the properties of a broad group of schedulers in a single parameter, it can provide insight how the choice of scheduling algorithms impacts end-to-end delay bounds. An important finding of this paper is that schedulers may exhibit noticeable performance differences which persist in a network setting with long paths.

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.

We seek to provide an analytical answer whether the impact of the selection of link scheduling algorithms diminishes on long network paths. The answer is provided through a detailed multi-node delay analysis, which is applicable to a broad class of scheduling algorithms, and which can account for statistical multiplexing. The analysis is enabled by two contributions: (1) We derive a function that can characterize the available bandwidth at a node for various scheduling algorithms. The function has an accuracy that recovers necessary and sufficient conditions for satisfying worst-case delay bounds at a single node, (2) We obtain end-to-end delay bounds by providing an explicit solution to an optimization problem, in which the service received at multiple nodes is subsumed into a single function. By presenting a unified analysis that captures the properties of a broad group of schedulers in a single parameter, we can provide insight how the choice of scheduling algorithms impacts end-to-end delay bounds. An important finding of this paper is that some schedulers show noticeable performance differences which persist in a network setting with long paths.

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.

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

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

Scalability concerns of QoS implementations have stipulated service architectures where QoS is not provisioned separately to each flow, but instead to aggregates of flows. This paper determines stochastic bounds for the service experienced by a single flow when resources are managed for aggregates of flows and when the scheduling algorithms used in the network are not known. Using a recently developed statistical network calculus, per-flow bounds can be calculated for backlog, delay, and the burstiness of output traffic.

A statistical network service which allows a certain fraction of traffic to not meet its QoS guarantees can extract additional capacity from a network by exploiting the statistical properties of the traffic. Here we consider a statistical service which assumes statistical independence of flows, but does not make any assumptions on the statistics of traffic sources, other than that they are regulated, e.g., by a leaky bucket. Under these conditions, we present functions, so-called local effective envelopes and global effective envelopes, which are, with high certainty, upper bounds of multiplexed traffic. We show that these envelopes can be used to obtain bounds on the amount of traffic on a link that can be provisioned with statistical QoS. A key advantage of our bounds is that they can be applied with a variety of scheduling algorithms. In fact, we show that one can reuse existing admission control functions that are available for scheduling algorithms with a deterministic service. We present numerical examples which compare the number of flows with statistical QoS guarantees that can be admitted with our effective envelope approach to those achieved with existing methods.

Network services for the most demanding advanced networked applications which require absolute, per-flow service assurances can be deterministic or statistical. By exploiting the statistical properties of traffic, statistical assurances can extract more capacity from a network than deterministic assurances. We consider statistical service assurances for traffic scheduling algorithms. We present functions, so-called effective envelopes, which are, with high certainty, upper bounds of multiplexed traffic. Effective envelopes can be used to obtain bounds on the amount of traffic on a link that can be provisioned with statistical service assurances. We show that our bounds can be applied to a variety of traffic scheduling algorithms. In fact, one can reuse existing admission control functions for scheduling algorithms with deterministic assurances. We present numerical examples which compare the number of flows with statistical assurances that can be admitted with our effective envelope approach to those achieved with existing methods.

Optimal scheduling of real-time tasks on multiprocessor systems is known to be computationally intractable for large task sets. Any practical scheduling algorithm for assigning real-time tasks to a multiprocessor system presents a trade-off between its computational complexity and its performance. In this study, new schedulability conditions are presented for homogeneous multiprocessor systems where individual processors execute the rate-monotonic scheduling algorithm. The conditions are used to develop new strategies for assigning real-time tasks to processors. The performance of the new strategies is shown to be significantly better than suggested by the existing literature. Under the realistic assumption that the load of each real-time task is small compared to the processing speed of each processor, it is shown that the processors can be almost fully utilized.