A fundamental problem in 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 on a wireless link, 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,x)-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 and for a network with cross traffic.
There is a collection of recent works that apply stochastic network calculus methods @cite_40 to wireless networks with fading channels. The stochastic network calculus is closely related to the effective bandwidth theory, in that it seeks to develop bounds on performance metrics under assumptions also found in the effective bandwidth literature. Different from effective bandwidth literature, stochastic network calculus methods seek to develop non-asymptotic bounds. An attractive element of a network calculus analysis is that sometimes it is possible to extend a single node analysis to a tandem of nodes, using the convolution operation seen in the introduction.
@cite_40
2098142032 2158352245 1589801689 2142114607
In this paper, we develop a method for analyzing time-varying wireless channels in the context of the modern theory of the stochastic network calculus. In particular, our technique is applicable to channels that can be modeled as Markov chains, which is the case of channels subject to Rayleigh fading. Our approach relies on theoretical results on the convergence time of reversible Markov processes and is applicable to chains with an arbitrary number of states. We provide two expressions for the delay tail distribution of traffic transmitted over a fading channel fed by a Markov source. The first expression is tighter and only requires a simple numerical minimization, the second expression is looser, but is in closed form. 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 ). Network calculus, a theory dealing with queuing systems found in computer networks, focuses on performance guarantees. The development of an information theory for stochastic service-guarantee analysis has been identified as a grand challenge for future networking research. Towards that end, stochastic network calculus, the probabilistic version or generalization of the (deterministic) Network Calculus, has been recognized by researchers as a crucial step. Stochastic Network Calculus presents a comprehensive treatment for the state-of-the-art in stochastic service-guarantee analysis research and provides basic introductory material on the subject, as well as discusses the most recent research in the area. This helpful volume summarizes results for stochastic network calculus, which can be employed when designing computer networks to provide stochastic service guarantees. Features and Topics: Provides a solid introductory chapter, providing useful background knowledge Reviews fundamental concepts and results of deterministic network calculus Includes end-of-chapter problems, as well as summaries and bibliographic comments Defines traffic models and server models for stochastic network calculus Summarizes the basic properties of stochastic network calculus under different combinations of traffic and server models Highlights independent case analysis Discusses stochastic service guarantees under different scheduling disciplines Presents applications to admission control and traffic conformance study using the analysis results Offers an overall summary and some open research challenges for further study of the topic Key Topics: Queuing systems Performance analysis and guarantees Independent case analysis Traffic and server models Analysis of scheduling disciplines Generalized processor sharing Open research challenges Researchers and graduates in the area of performance evaluation of computer communication networks will benefit substantially from this comprehensive and easy-to-follow volume. Professionals will also find it a worthwhile reference text. Professor Yuming Jiang at the Norwegian University of Science and Technology (NTNU) has lectured using the material presented in this text since 2006. Dr Yong Liu works at the Optical Network Laboratory, National University of Singapore, where he researches QoS for optical communication networks and Metro Ethernet networks. Network calculus is an established theory for deterministic quality of service analysis of fixed networks. Due to the failures inherent in fading channels it is, however, not applicable to radio systems. Emerging probabilistic equivalents allow closing this gap. Based on the recent network calculus with moment generating functions we present a methodology for performance analysis of fading channels. We use a service curve representation of radio links which facilitates an efficient analysis of radio networks. We investigate fading channels with memory and our results show that the fading speed impacts service guarantees significantly. Numerical performance bounds are provided for an example taken from cellular radio communications for which the effects of opportunistic scheduling are quantified. Simulation results are shown which confirm the efficiency of the approach.