A Min-plus System Theory Approach for Performance Evaluation and Quality-of-Service Provisioning in Wireless Data Networks by Farshid Agharebparast A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T OF T H E R E Q U I R E M E N T S F O R T H E D E G R E E OF D O C T O R OF P H I L O S O P H Y in T H E F A C U L T Y OF G R A D U A T E STUDIES (Electrical and Computer Engineering) T H E U N I V E R S I T Y OF BRITISH C O L U M B I A October 2007 © Farshid Agharebparast, 2007 11 Abstract Recent advances in various wireless data networking technologies and their successful implementations have put the dream of ubiquitous high-quality multimedia communications within our reach. However, achieving reasonable service quality is still a main challenge. It is necessary to evaluate the performance of a new or functional network and to study its service quality factors, such as delay and throughput. This thesis proposes and evaluates a set of analyti-cal techniques based on the modern min-plus system theory that collectively presents an effective methodology for modeling, performance evaluation and quality of service (QoS) provisioning in wireless networks. Min-plus system theory is a successful alternative and complement to queuing theory, whose application in deterministic QoS guarantees is known as Network Calculus (NC) or (CT, p)-calculus. The contributions of this work can be grouped under three main categories: slope domain modeling, stochastic min-plus system theorems and their applications in wireless networking, and filter-bank-based wireless channel models. Slope domain modeling is a useful technique whose role in min-plus theory is similar in concept to that of the Fourier domain in traditional system theory. It facilitates analysis of communications networks, and for certain problems is the only viable solution. This method is used in numerous applications, such as system identification, optimal smoothing and priority scheduling. This thesis proposes a stochastic min-plus system theory approach that is used as a practi-cal and efficient methodology for QoS performance evaluations in wireless networks, when the service can be defined by its second-order statistics. The method is then used in optimal traffic shaping and resource allocation for transmission over wireless fading channels. Finally, the Ill concept of load spectrum is introduced as the slope domain representation of this stochastic min-plus theory. As an alternative method, a wireless link model based on the filter banks of N C elements is introduced. The model employs modular concatenations of selected N C components to represent the effect of a wireless link on the statistical QoS performance at the link layer. This technique is used in optimal smoothing to successfully solve the problem of playback delay and buffer size calculations for multimedia streaming via a wireless network. Table of Contents Abstract ii Table of Contents iv List of Tables vii List of Figures viii List of Acronyms xii List of Symbols xiii Acknowledgements xiv Dedications xvi Chapter 1: Introduction 1 1.1. Motivations and Obj ectives 3 1.2. Main Contributions 5 1.3. Organization of the Thesis 7 Chapter 2: Background 8 2.1. A Brief History 9 2.2. Min-plus System Theory Fundamentals 10 2.3. Min-plus Algebra 14 2.4. Traffic Characterizations 17 2.5. Deterministic Network Calculus 19 2.6. Stochastic Min-plus Approaches 22 2.7. Mathematical Transformations for Min-plus Systems 25 Chapter 3: Slope Domain Modeling and Analysis of Data Communication Networks 26 3.1. Introduction 26 3.2. The Slope Transform 28 3.3. Slope Domain Analysis of Networks 33 3.4. Non-Preemptive Priority Scheduling Example 35 3.5. Network Identification Application 39 3.6. Optimal Smoothing for Multimedia Streaming 46 3.7. Load Spectrum 49 3.8. Further Applications 49 3.9. Comparing Fourier and Slope Domains 50 3.10. Comparing Slope with the Legendre Transform and Fenchel Conjugate 51 3.11. Computational Improvement Using the Legendre Transform and Fenchel Conjugate 53 3.12. Summary 54 Chapter 4: A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 55 4.1. Introduction 56 4.2. Background 57 4.3. Min-Plus Systems with Stochastic Inputs 59 4.4. Min-Plus Stochastic Systems 64 4.5. Wireless Channel Modeling, Performance Evaluation and Cross-layer Design 66 4.5.1. System Model 68 4.5.2. Service Curve of the Channel 69 4.5.3. Methodology '. 72 4.6. Numerical Results 75 4.7. Discussion 83 4.8. Summary j 89 Chapter 5: Optimal Leaky-Bucket Shaper and Resource Allocation for the Transmission of Multimedia over Wireless Fading Channels 90 5.1. Introduction 91 5.2. Optimal Leaky-Bucket Shaper 92 5.3. System Model and Building Blocks 96 5.4. Methodology 98 5.5. Numerical Results 99 5.6. Summary 116 Chapter 6: An Alternative Wireless Link Model Using Filter Banks of NC Elements 117 6.1. Introduction 117 6.2. Wireless Link Model 119 6.3. Application in Wireless Video Streaming.... 122 6.4. Numerical Example 128 6.5. Discussion 129 6.6. Summary 131 vi Chapter 7: Summary and Future Work 132 7.1. Summary 132 7.2. Further Work 134 References 136 vii List of Tables Table 3.1 Properties of the lower slope transform 32 Table 3.2 Properties of the upper slope transform 32 Table 3.3 Lower slope transforms of some useful N C functions 35 Table 4.1. Parameters used in the example and their values 75 Table 5.1. Common parameters and their values used in the numerical examples 100 V l l l List of Figures Figure 2.1 Min-plus system input/output representation 11 Figure 2.2 NC-based wireless link modeling 24 Figure 3.1 Modeling a network in N C and slope domains 31 Figure 3.2 Slope transforms of the peak-rate and rate-latency functions, and their convolution 37 Figure 3.3 Slope transforms of the affine and rate-latency functions, and their convolution. 38 Figure 3.4 System identification by applying the slope domain analysis: (a) Plot of the service curve and inputs of the form b+at for different values of a. (b) Plot of the observed outputs minus the inputs 41 Figure 3.5 System identification by applying the slope domain analysis: Comparison of the numerical result with the analytical slope response 42 Figure 3.6 System identification using OPNET simulations 43 Figure 3.7 Video streaming network topology 46 Figure 4.1 Calculation of the autocorrelation. In the left figure, the two instances of time needed for the calculation of the autocorrelation are two possible instances observed at different times but for the same transmission time; on the right, they are at two different transmission times 64 Figure 4.2 Statistical characterizations of the received traffic using the stochastic min-plus system theory. 66 Figure 4.3 The transmitted traffic (input) and 50 different instances of the channel output due to the time-varying Rayleigh fading channel 67 Figure 4.4 System model and building blocks 68 Figure 4.5 Graphical illustration of calculations of the second-order statistics of the delay. .74 Figure 4.6 A n example of (a) the traffic delivered to the link layer, (b) shaped traffic ready to be transmitted through the channel, and (c) cumulative representations of traffic in a and b 76 ix Figure 4.7 3D plots of the autocorrelation of the service (a) and the output (b). The x axis designates the transmission time and the y axis represents 50 different instances of observations (with its mirror towards -50) 78 Figure 4.8 (a) Traffic and 50 instances of channel service curves, (b) Comparison of analytical and simulation results for mean outputs 79 Figure 4.9 Graphical calculations of mean and worst delays from the mean and worst-case outputs 80 Figure 4.10 Mean and worst delays for different values of u/a with a 95% confidence interval (30 iterations of 50 instances each) 81 Figure 4.11 (a) Delay versus b (shapers burst tolerance), when E{y} and \ila are 10 dB and 0.8, respectively, with a 95% confidence interval (30 iterations of 50 instances each) 82 Figure 4.12 Delay versus average SNR (E{y}) in dB when \ila is 0.8, with a 95% confidence interval (30 iterations of 50 instances each) 82 Figure 4.13 Delay versus different values of shaping rate with the consideration of convolutional channel codes and bit error dependency. 86 Figure 5.1 Delay and buffer calculations. Method A : using the input and output traffic (a). Method B : using the arrival and service curves (b) 94 Figure 5.2 The effect of variations of arrival and service parameters on the maximum delay and buffer requirements for a rate-latency server and leaky-bucket-shaped traffic. 95 Figure 5.3 Calculation of mean and worst delays and buffer sizes, (a) Method A : using the input and output traffic flows, (b) Method B : using the arrival and service curves. 99 Figure 5.4 Plots of the mean delays versus b and a 104 Figure 5.5 Contours of plots in Figure 5.4. The values on the graphs are the corresponding mean delays 104 Figure 5.6 Plots of the worst delays versus b and a 105 Figure 5.7 Contours of plots in Figure 5.6. The values on the graphs are the corresponding worst delays 105 Figure 5.8 Plots of the mean buffer sizes versus b and a 106 Figure 5.9 Contours of plots in Figure 5.8. The values on the graphs are the corresponding mean buffer sizes 106 Figure 5.10 Plots of the worst buffer sizes versus b and a 107 Figure 5.11 Contours of plots in Figure 5.10. The values on the graphs are the corresponding worst buffer sizes 107 Figure 5.12 Plots of the mean delays versus b and a 108 Figure 5.13 Contours of plots in Figure 5.12. The values on the graphs are the corresponding mean delays 108 Figure 5.14 Plots of the worst delays versus b and a 109 Figure 5.15 Contours of plots in Figure 5.14. The values on the graphs are the corresponding worst delays 109 Figure 5.16 Plots of the mean buffer sizes versus b and \i 110 Figure 5.17 Contours of plots in Figure 5.16. The values on the graphs are the corresponding mean buffer sizes 110 Figure 5.18 Plots of the worst buffer sizes versus b and (j. I l l Figure 5.19 Contours of plots in Figure 5.18. The values on the graphs are the corresponding worst buffer sizes I l l Figure 5.20 Mean delays versus b and a - dependent bit error scenario 112 Figure 5.21 Worst delays versus b and a - dependent bit error scenario 112 Figure 5.22 Mean buffer sizes versus b and a - dependent bit error scenario 113 Figure 5.23 Worst buffer sizes versus b and a - dependent bit error scenario 113 Figure 5.24 Mean delay versus b and \x - dependent bit error scenario 114 Figure 5.25 Worst delay versus b and u - dependent bit error scenario 114 Figure 5.26 Mean buffer sizes versus b and u - dependent bit error scenario 115 Figure 5.27 Worst buffer sizes versus b and n - dependent bit error scenario 115 Figure 6.1 Wireless link modeling 119 xi Figure 6.2 a) Clipper, b) Clipper equivalent with A R Q 120 Figure 6.3 Network schematic in the study of video streaming application 123 Figure 6.4 N C modeling of G(t) in Figure 6.3 124 Figure 6.5 Playback delay and buffer size calculation for the Jurassic Park video trace streaming 128 xii List of Acronyms A T M Asynchronous Transfer Mode A R Q Automatic Repeat-reQuest A W G N Additive White Gaussian Noise B E R Bit Error Rate D E D S Discrete Event Dynamic Systems DiffServ Differentiated Services DTI Dilation Translation-Invariant ETI Erosion Translation-Invariant GPRS General Packet Radio Service GPS Generalized Processor Sharing IntServ Integrated Services M A N Metropolitan Area Network M E R Minimum Envelope Rate M R S V P Mobile Resource ReSerVation Protocol N C Network Calculus pdf. Probability Density Function P E R Packet Error Rate QoS Quality of Service Q P S K Quadrature Phase-Shift Keying R S V P Resource ReSerVation Protocol S L A Service Level Agreement SNR Signal to Noise Ratio TSPEC Traffic Specification U M T S Universal Mobile Telecommunications System V B R Variable Bit Rate W F Q Weighted Fair Queuing W i M A X Worldwide Interoperability for Microwave Access WSS Wide-Sense Stationary xiii List of Symbols infox A Infimum min Minimum sup Supremum ® Convolution, min-plus convolution 0 Min-plus deconvolution * Max-plus convolution • Max-plus deconvolution C(-) Arrival curve (general notation) x(.) System input, input traffic h(.) Service curve, system function y(-) System output, output traffic $L {•} (a) > -^zA •) > o r X( •) Lower slope transform STJ{ .}(a) or XV(.) Upper slope transform H(a) Slope response F{.} Fourier transform ¥ { . } ( . ) Legendre transform Fenchel conjugate L(.) or Lh(.) Min-plus system operator Ls(.) Traditional system operator E{.}(.) or r| Expectation, statistical average Rx(.), Rx(.,.) Correlation function A,(.) Zero step function Y Signal to noise ratio QC) Complementary error function xiv Acknowledgements "A hundred times every day I remind myself that my inner and outer life are based on the labors of other [people], living and dead, and that I must exert myself in order to give in the same measure as I have received and am still receiving. " — Albert Einstein, "The World as I See It" I would like to gratefully thank my academic advisor Prof. Victor C M . Leung for his support and supervision, as well as his faith in my research abilities. It was a great privilege and invaluable experience to work under the guidance of this world-renowned expert, scholar, and gentleman. I would also like to express my gratitude to the supervisory committee members (Prof. Vikram Krishnamurthy, Prof. Son T. Vuong and Prof. Vincent Wong,), the university examiners (Prof. Philip Loewen and Prof. Rabab Ward), and the external examiner (Prof. Rene L . Cruz) for their valuable and constructive comments. I would also like to thank my current and former colleagues, and professors of the communications research group, who made my academic life at U B C rewarding and whose knowledge I benefited greatly from; with special thanks to Prof. Cyri l Leung, Prof. Matthew Yedlin, Dr. Joo-Han Song, and Dr. Yaser P. Fallah. I would also like to thank the friendly and helpful staff at the E C E office, and Craig Wilson of I O C S for helping me to make this dissertation more readable. I would like to appreciatively acknowledge the following federal, provincial and institu-tional organizations that graciously and generously supported my Ph.D. studies through post-graduate scholarships, fellowships or grants: the Natural Sciences and Engineering Research Council of Canada (NSERC PGS-B Postgraduate Scholarship and Grant RGPIN44286-04), the Canadian Wireless Telecommunications Associat ion ( C W T A Graduate Scholarship), the Advanced Systems Institute of British Columbia (ASI Graduate Scholarship), and the University of British Columbia ( U B C Graduate Fellowship, Top-Up and Tuition Fee awards). I salute U B C , this great university that has provided me with the opportunity to grow XV through exposure to academia, arts, music and dance, sports and fitness, and culture. U B C is one of those rare places where a wealth of natural beauty, supreme-quality academia, and a rich multicultural environment coexist harmoniously. The U B C affiliate, St. John's Residential Graduate College, fostered a magnificent opportunity for me to better grow towards being a well-rounded individual, with its vibrant international community, numerous seminars, and cultural events. While residing at the College, I met so many bright, talented and kind individuals whom I am proud to be friends with. I would like to pay tribute especially to Dr. K a i Hilpert, Paola Ceruti, Rebecca Klady, and Farzad Moin Afshar. A n d last but not least, my utmost gratitude and respect to my parents, without whom I would be nowhere. They are everything to me and everything I am. It is my privilege to have had the love, support and encouragement of my beloved parents, sister and brothers throughout my life. xvi To my beloved parents. 1 Chapter 1. Introduction With the ever-increasing popularity and usefulness of wireless data devices such as data-enabled phones, PDAs (personal digital assistant), and laptops, it is an unquestionable fact that a cost-effective high quality anywhere-anytime data communication capability is greatly desirable. The availability of such a service wi l l benefit the general public with an integrated, ubiquitous means of communication. The objective of such systems is to make a wide range of data applica-tions economically available, such as those provided by the Internet. The increasing availability of G P R S (general packet radio service) and U M T S (universal mobile telecommunications system) services, the great success of the commercialized wireless local area networks ( W L A N ; in particular the I E E E 802.11b standard, which commercially is referred to as W i - F i (wireless fidelity) to assure interoperability), as well as impending widespread implementations of wireless metropolitan area networks (interoperable via W i M A X forum) particularly advocate this proposi-tion. In order to make such services economically available, it is necessary to find a set of technol-ogies and methodologies to provide data and Internet resources, as well as high quality voice/ video services, to mobile users through efficient wireless packet-switched networks with accept-able quality of service (QoS). This goal challenges researchers and telecommunications companies to not only devise the required infrastructure but to ensure a high degree of service quality. The characteristics of multimedia applications are their wide range of delay, bandwidth, and content preservation requirements. The QoS required by each application differs and is specified by these characteristics. For some applications, a certain QoS guarantee is crucial for Chapter 1. Introduction 2 their proper operation. For example, a multimedia streaming application needs to meet certain maximum delay and delay jitter criteria. This QoS is negotiated with the user through the service level agreement (SLA) phase. Based on the S L A , the network guarantees some level of service, provided that the user complies with the agreed upon conditions. In order to implement a network capable of providing and guaranteeing a set of pre-defined QoS throughout a communication session, traffic management techniques are devised and used. Traffic management methods include resource allocation, shaping, scheduling, and buffer management mechanisms [1][2]. Performance evaluation is a critical process in which a number of analytical, simulation or emulation procedures are utilized to ensure that a particular network is capable of providing the required service, in all of the design, implementation and enhancement phases. Min-plus system theory is a modern approach for the study and performance evaluation of a system where a number of customers compete to obtain the service of a number of available resources, such as queuing networks. The theory is based on a special algebra whose operators differ from those of the algebra that we traditionally deal with. Under this algebra, a traditionally non-linear system becomes linear and can be easily studied. The application of this theory in the deterministic study of data communications networks has been called Network Calculus (NC) or (rj, p )-calculus. Due to a book with this title, the term Network Calculus has been widely adopted for the application of deterministic min-plus theory in data networking. N C , a fairly new approach in networking analysis, provides further insight in to queuing theory. Some successful examples of N C applications for traffic management in wired networks are its widespread use in the study of A T M (asynchronous transfer mode), IntServ (integrated services) [3], DiffServ (differentiated services) [4] [5], and service-curve-based schedulers such as the generalized processor sharing (GPS) [6]. Min-plus system theory is an alternative and complement to the traditional Markovian queuing theory. The main distinction starts with a different traffic characterization. Based on this traffic characterization, a set of theorems and concepts are introduced that provides a filtering theory for the analysis and design of computer communication networks. Although N C is at an elaborate stage and has been widely used for the deterministic analysis of wired data networks, methods for considering servers with stochastic behavior are still under development. Wireless networks are perfect examples of such servers. This thesis contrib-Chapter 1. Introduction 3 utes to the performance evaluation and QoS provisioning in wireless data networks based on the min-plus system theory and its application in some specific problems. In addition, some of the key methods introduced here complement min-plus system theory and enhance its general applicability in data networking. In the next subsection, the motivations and objectives inspiring this thesis are stated. 1.1. Motivations and Objectives Min-plus system theory is a sophisticated modern approach to performance modeling and QoS provisioning in computer communication networks and discrete event dynamic systems (DEDS) [7]. N C or (rj, p )-calculus is a successful framework based on the min-plus algebra for deterministic performance guarantees in queuing systems and has been successfully used in the analysis of networking principles [8] [9]. It provides an alternative approach to the study of queuing systems, and facilitates the design and performance evaluation of data communication networks. In some scenarios that are difficult to analyze using traditional queuing theory, it is the preferred method [10][11][12]. A n example of the successful application of network calculus is the introduction of service-curve-based schedulers. These schedulers are based on the widely adopted rate-latency service model and show link-sharing and decoupled delay bandwidth guarantees [6][13][14][15]. Inspired by the success of N C and its various applications, we were motivated to contrib-ute in this thesis to the min-plus system theory and its application in wireless networking. In order to ensure complete compatibility with the deterministic N C and to facilitate an end-to-end perfor-mance evaluation in a network consisting of wired and wireless sections, throughout this thesis the traffic characterization is based on the concept of arrival curves, which wi l l be explained in detail in Chapter 2, Section 2.4. Following this assumption, this thesis contributes to the general theory of stochastic min-plus systems, the application of the slope domain modeling and then application of these concepts in wireless networking. The main challenge involved is the random behaviour of a wireless channel; therefore, it practically can only be modeled as a stochastic server. The physical layer characteristics of the channel are usually known, and can be used to define a stochastic service for the channel. Thus, i f a stochastic min-plus theory is available, the channel can be modeled. Chapter 1. Introduction 4 Two major stochastic treatments of the min-plus system theory exist in the literature: 1) The (a(6), p(0))-calculus extends the application of N C by introducing a stochastic traffic characterization based on the log-moment generating function using effective bandwidth theory [8]. The main advantage of such a traffic model is that it extends the application of N C to include traditional traffic models such as Poisson. However, we would like to work with an arrival-curve traffic characterization and consider a stochastic server representing a wireless link or network. Even the effective capacity method [16], which is based on the role reversal of effective bandwidth, is suitable for a standalone link only. 2) The statistical N C is another method that provides general direction in studying a system when a stochastic service curve with a meaningful probability of occurrence is given [17] [18] [19]. The stochastically bounded burstiness [20] method is a subdivision of the statistical N C methods. The practical problem with this method is how to actually define such a service curve. Chapter 6 of this thesis provides an alternative channel model based on this method. Therefore, a stochastic min-plus theory is needed that • fits within the N C filtering theory • can model a wireless link accurately from the channel's statistical characteristics • is applicable independent of the traffic model used • has useful applications for solving practical problems in wireless data networking • and can be used in an end-to-end QoS analysis of a network consisting of both wired and wireless sections, and therefore is compatible with the arrival curve traffic characterization. In summary, the motivations for this work can be expressed as follow: • Network Calculus is a successful framework for the performance evaluation of data communication networks. How can this framework be extended and modified in order to be utilized in a network that consists of wireless data networks, in a simple yet gen-eral framework? We focus on the arrival-curve traffic characterization. Chapter 1. Introduction 5 • The min-plus system theory is similar to traditional system theory in many re-spects. Is there a similar framework for stochastic input/output characterization? • Following a similar reasoning, is there a relationship between the statistics of the input and output of a min-plus system when one is a stochastic process, similar to the traditional system theory? • The Fourier transform is a fundamental tool with many applications in traditional system theory. Does a mathematical transform exist for the min-plus theory with a broad range of applications in data networking that is not constrained by the limitations that the Legendre transform is constrained by? • In turn, can the aforementioned frameworks and techniques provide an effective approach to performance evaluation of wireless networks, and to a variety of network-ing problems, such as optimal smoothing, optimal shaping, and network identification? • In summary, the objectives of the thesis are the development of a required stochas-tic min-plus system theory and useful techniques for its application in performance evaluation and QoS provisioning in wireless data networks. The next subsection lists the main contributions of the thesis. 1.2. Main Contributions This thesis contributes to the performance evaluation and QoS provisioning techniques in wireless networks by utilizing the min-plus system theory approach. It introduces several new methods that enhance and extend the application of the min-plus theory in queuing systems, including slope domain modeling and a new stochastic min-plus system theory. Based on these methods, models for a wireless channel and consequently a wireless network are presented. These models are then used in a number of applications, such as performance modeling and evaluation of service quality, optimal traffic shaping and resource allocation, optimal smoothing, and system identification. The contributions of this dissertation can be classified under the following three main themes: Chapter 1. Introduction 6 * Slope domain modeling and its applications: The development of slope domain modeling and its application in data communications are contributed by this thesis [21]. The proposed approach is based on the application of the mathematical concept of slope transform in min-plus system theory. Slope domain modeling supersedes and encompasses models based on the Legendre transform, as it is not limited to convex (or concave) or differentiable functions. Similar to the application of the Fourier transform in the conventional system theory, the slope transform maps functions in the min-plus domain into another domain, called the slope domain. Similar to the Fourier's frequency domain, this mapping not only facilitates performance modeling and evaluation of data networks, but also is sometimes the only method available for solving certain problems. Slope domain modeling establishes an analytical framework with numerous applications. In particular, system identification, priority scheduling, and optimal smoothing are studied in this thesis. * A stochastic min-plus system theory approach and wireless channel modeling: A set of stochastic system theorems is presented that characterizes the input/output relationship of a system with stochastically defined input or service [22][23]. These theorems are then used as the basis for a technique in stochastic min-plus system theory. The method identifies the second-order statistics of the output of a min-plus system using the results of two mathematical theorems. This method is similar in approach and application to the traditional stochastic system theory. The dissertation considers a wireless channel model as a stochastic rate-latency server. In conjunction with the proposed stochastic system technique, this model is used to characterize a traffic stream passing through a wireless channel. This is also a practical methodology for perfor-mance modeling of any stochastic min-plus server. In addition, an alternative channel model based on the implementations of a filter bank of concatenated deterministic N C elements is proposed [24] [25]. These two models collectively provide a practical methodology for modeling wireless networks using min-plus theory. * Applications in wireless data networking: This dissertation investigates the application of the proposed techniques in wireless data networking, including • performance evaluations and QoS provisioning in wireless data networking [23][26] Chapter 1. Introduction 7 • optimal smoothing for the calculations of the playback delay and buffer size at the receiver side [24] • and optimal shaping and resource allocation for transmission of multimedia over wireless channels [27]. 1.3. Organization of the Thesis The outline of the thesis is as follows. The current chapter presents the motivations and objectives of this work in an itemized format and is an introduction to the methodologies used. The next chapter provides an overview of min-plus filtering theory and explains the mathematical foundation, theorems and notation used throughout this thesis. The main body of the thesis consists of chapters 3, 4, 5, and 6. Chapter 3 introduces slope domain modeling as a complement to N C theory. Slope domain modeling facilitates analysis of networks in a fashion similar to the Fourier domain in traditional systems. A number of particularly useful applications of the proposed methodology are then discussed. Chapter 4 presents a stochastic min-plus system theory approach in which the input/output relationship of a min-plus system is derived in terms of the second-order statistics. This concept is then used in performance modeling of wireless networks. Chapter 5 proposes optimal traffic shaping and resource allocation techniques in wireless networks, making use of the theorems introduced in Chapter 4. Finally, Chapter 6 presents an alternative methodology that utilizes deterministic N C elements to model a wireless link. This approach is then applied to optimal smoothing application in streaming variable bit rate traffic over a wireless network. Finally, Chapter 7 summarizes the thesis and proposes future work. 8 Chapter 2 . Background In this chapter, an introduction to the basic concepts and ideas of the min-plus system theory is presented, and the required mathematical background is described. The chapter provides a concise yet complete survey of the history, background and related min-plus techniques used in communications networking, (a, p )-calculus [8] and deterministic N C [9] are subdivisions of this discrete event dynamic systems (DEDS), called min-plus system theory in this thesis. First, we introduce the fundamental concepts, explain the advantages and disadvantages of this approach, and discuss available alternatives. Second, different deterministic and stochastic traffic character-izations under this theory are presented. Then, deterministic N C and various stochastic approaches are discussed. This chapter consists of the following sections: • A brief history of Network Calculus and min-plus system theory fundamentals • Min-plus algebra • Min-plus traffic characterization • Deterministic Network Calculus • Statistical and stochastic min-plus system theory approaches • Min-plus theory for wireless networking • Mathematical transformations for min-plus system theory For clarification, we briefly define and enlist critical min-plus terms used in this thesis. Deterministic N C (or simply N C ) is a min-plus theory in which both traffic and server are deterministically defined. Stochastic min-plus theory has three branches: 1) Stochastic min-plus Chapter 2. Background 9 theory based on moment generating functions and effective bandwidth theory, where either the traffic or the server is stochastically defined. The ((rj(0), p(0)))-calculus of [8] is of this category for stochastic traffic characterizations. Also, the effective capacity method is of this type. N C filtering theory is not directly applicable to this method. 2) Statistical methods such as stochastically bounded burstiness. 3) The stochastic min-plus theory presented in this thesis. The N C filtering theory is applicable to this method. 2.1. A Brief History The development of a modern calculus for the study of data communication systems has been underway for the last few decades. The calculus is based on a special algebra whose mathematics was conclusively explained in [7]. In their book, Baccel l i et al. presented the application of such a calculus in the modeling and analysis of D E D S . The specific application of the min-plus theory in data communications networks was first introduced with the pioneering works of Cruz in his seminal papers on the calculation of network delay [28][29], and discussed further in [30]. Kurose then contributed to the computation of the upper bounds of per-session performance measures such as delay and buffer occupancy [31]. The concept then was elaborately developed into a comprehensive and useful theory in two independent books. Network Calculus by Le Boudec and Thiran is the main reference for deterministic service guarantees [9]. In his prominent book, Chang [8] elaborated on the concept of the deterministic N C by presenting the (rj, p)-calculus. He also introduced stochastic (a(0), p(0))-calculus based on moment generating functions. This work has been the prime reference for the stochastic treatment of min-plus systems, using the theory of effective bandwidth. Most subsequent stochastic N C models and applications are based on the effective bandwidth theory. Many others have contributed to different aspects and applications of the theory. Liebeherr et al. presented a method for providing end-to-end statistical service guarantees [17]. In this significant work, a statistical alternative is presented as a framework for the statistical analysis of non-deterministic systems. L i u et al. [20] and Starobiniski et al. [32] also presented a general Chapter 2. Background 10 stochastic N C , based on stochastically bounded burstiness. Chang and Cruz presented the time-vary filtering theory of min-plus systems [33]. The application of the Legendre transform in N C was first mentioned by Cruz in his pioneering papers on N C [28][29], and then was discussed as an alternative to N C domain modeling by Hisakado et al. [34]. However, the Legendre transform has a number of limitations. Slope transform is a more general transform that does not have those limitations and includes the Legendre transform as a special case [35]. Concurrent to the develop-ment of our slope domain model, other works on such alternative domains have been published by Pandit et al. [36], and by Fidler and Recker [37], based on the Legendre transform. The application of N C in wireless networking has been investigated quite recently. M R S V P (mobile resource reservation protocol) is a resource reservation protocol for an integrated services network with mobile hosts [38]. This protocol is an extension of the R S V P (resource reservation protocol) proposal for wired networks. Hamdi and Lee presented a packet-drop mechanism for deterministic packet delay and packet losses in wireless networks [39]. Wu and Negi presented a model, called effective capacity, based on the reverse role of the effective bandwidth concept [16]. Although the method makes brilliant use of the moment generating function concept in stochastic traffic characterization by swapping the roles of input and service to model a wireless channel, it has a number of shortcomings. First, it is based on a constant traffic rate, and it is not clear how it can be applied to many other practical traffic models. In practice, traffic flow obeys arrival curves of different forms. Second, it only models a single wireless link (single hop) and cannot be used in a scalable end-to-end N C analysis. Finally, the effective bandwidth concept, which is based on the moment generating functions, is a complex concept to use in both practice and theory. 2.2. Min-plus System Theory Fundamentals The min-plus system theory is based on D E D S modeling of the time behaviour of a class of systems where a number of customers compete to obtain the service of a number of available resources [7]. Computer communications networks and queuing networks belong to such classes of systems. The time-behavior dynamics of these systems can be described by the concepts of synchronization and concurrency [7]. Synchronization is a basic operation of a D E D S , and Chapter 2. Background 11 h{t) Figure 2.1 Min-plus system input/output representation describes how its elementary parts interact. Synchronization requires many users to be present at the same time as a number of resources. Concurrency occurs when the users have a choice and must select one from a number of resources (such as in routing algorithms). Min-plus (or its dual max-plus) algebra has proven to be a good candidate for modeling D E D S when they do not involve concurrency. Such systems are linear, when modeled by the min-plus theory [7]. The definition of min-plus linearity wi l l be explained later in this section. Min-plus system theory has a number of advantages. First, it provides a set of theorems and rules that establish a sophisticated filtering theory for the analysis of complex D E D S . This systematic approach is similar in many respects to the familiar traditional system theory. Second, its unique traffic characterization is simple yet efficient, practical, easy to define and has both deterministic and stochastic models. This is a fundamental aspect differentiating it from traditional queuing theory. Third, it has been proven to be the best candidate for the analysis of a number of frameworks, including Internet IntServ, DiffServ and A T M . Also, it can be applied to systematically estimate deterministic and stochastic bounds for QoS metrics of delay, buffer requirements and throughput. Figure 2.1 illustrates the input/output representation of a min-plus system. In min-plus system with an input x(t), a service curve (system function) h(t), the output is defined by the system operator, L(.), by When it is clear that h(t) is the service curve, for the simplicity of notation, the system operator may be noted only by L(.). If h(t) is a lower service curve, then y(t) > L(x(t)), and i f h(t) is an upper service curve, then y(t) <L(x(t)). A l l functions, (i.e. x(i), h(t) and y(t)) are non-decreasing. y(t) = I n w ( x ( 0 ) . (2.1) Chapter 2. Background 12 A min-plus system with a system function L(.) is linear when L[inf(a + xl(t),b + x2(t))] = inf(a + L[x{(t)], b + L[x2(t)]). (2.2) In a broader sense, this concept is also an instance of the infimum-of-sums superposition princi-ple, which is addressed later in Section 2.4 by (2.5). A min-plus system is shift-invariant i f it commutes with a shift operation on the input, i.e., a shift in time of the input causes the same shift of the output [7]. In a communication network, the box (system) represents a network element (link, node, network); x(t) (input) represents the cumulative incoming traffic (up to t) in units of bits (or bytes); and y(t) (output) represents the cumulative outgoing traffic (or received by an element at the other end) in units of bits. The service curve h(t) defines the service provided by the network. The exact definitions and models defining x(t) and h(t) are presented in Sections 2.4 and 2.5. Traditionally, the behavior of communications networks has been modeled and analyzed by the so-called queuing theory, in which the system is modeled by an A/B/m/N queue, a notation popularized by D. G. Kendall [40]. While the traffic flow and the server can be characterized by arbitrary stochastic processes in this method, most of the studies available in the literature are devoted to the study of the M/M/l queues, where the inter-arrival and service times are exponen-tially distributed. Although these models are the foundation of modern networking theory and have been crucial in giving us a preliminary understanding of how networks function, they become very complicated when we apply them to the study of real networks with sophisticated scheduling techniques that guarantee service quality. N C , on the other hand, is a new approach to studying computer communication networks and their elements, such as shapers, multiplexers, and queues. It has been proven to simplify the study of numerous networking problems, especially those related to QoS provisioning [ 10][ 11 ]. N C is usually compared with system theory, which is used in the systematic study of circuits and systems in electrical engineering. Two main features characterize N C theory. First, the traffic flow is defined by a non-decreasing (or a wide-sense increasing, as it is called in [9]) function of time called the "arrival envelope" or "arrival curve." Second, the behavior of the system serving the Chapter 2. Background 13 traffic is defined by "service curves," so that the output is calculated by a special convolution of the input and this service curve. The theory is mathematically founded on "min-plus" (or its dual max-plus) algebra, and has been developed into a set of theorems of filtering theory. N C has found fundamental applications in the analysis of QoS-enabled packet networks such as A T M networks, and the Internet, employing the IntServ and DiffServ frameworks [9]. N C is an effective approach to developing optimal smoothing algorithms in video transmission over (lossless) wired networks [41]. The theory is based on the pioneering work of Cruz [28][29]. There are two independent yet very closely related main interpretations of this theory, described in books by Le Boudec and Thiran [9] and by Chang [8]. The latter book introduces a stochastic traffic characterization as an extension to the theory. Although deterministic N C is just defined by deterministic arrival and service curves, stochastic N C has been characterized in a number of ways. In this thesis when not specifically mentioned or not obvious from the context, N C should be considered as analogous to deterministic N C . The N C theory provides numerous benefits. It is ideal for the study of D E D S characterized by synchronization. Also, it can be readily used to study non-linear systems, as most communica-tion systems are. Owing to its concatenation property, it is modular in its modeling of cascades of network elements with known service curves. The traffic characterization of N C is its major difference from traditional queuing theory, and also its great advantage where the only informa-tion we need is the traffic envelope. N C ' s powerful filtering theory simplifies more accurate studies of many problems that otherwise are impossible or hard to solve. System identification methods in N C can be used to identify an unknown element. Like any other tool or theory, N C has its limitations. First, in order to derive tight bounds, the functions describing the traffic and the service need to be "good" functions. In min-plus algebra, this translates to being a subadditive function. The implications of this condition are addressed later in Section 2.5, where the subadditive concept is explained. In addition, functions are mostly desired to be convex or concave, particularly when the analysis relies on the Legendre transform tools. Another limitation, similar to the G / G / l theory, is that the queue needs to be zero at the reference time zero; a non-zero queue requires extra care, which creates difficulty in Chapter 2. Background 14 working with time-varying systems. N C has limited tools for describing packet loss in the network; there is only the clipper element, which is used in N C . 2.3. Min-plus Algebra The mathematics of N C is min-plus algebra, which is based on the dioid of (9? u { o o } , A , +) in which A is the infimum (or minimum) operator and "+" is the well-known algebraic addition [7]. Infimum is the greatest lower bound of a set, but it does not need to be in it, e.g., a in the set (a, b]. If this value is in the set, it is called the minimum, such as a in the set [a, b]. A dioid is an algebraic structure in which a set is endowed with two operators (here the set 5H and operators A and +) that satisfies 10 axioms of: closure of A and +, associativity of A and +, existence of a zero element for A and a neutral element for +, idempotency of A , commutativity of A , distributivity of + with respect to A and finally "the zero element of A is absorbing for +" [9]. The set of axioms used for definition of a dioid is similar to a ring, except that the idempo-tency of the addition is replaced for the existence of the negative element for the addition. As a comparison, the normal algebra we are used to is based on the algebraic field of (5R u { o o } , +, x ). In the min-plus algebra, computation of minimum replaces addition, and addition replaces multiplication in (SR u { c o } , +, x ). In the literature, the operators are sometimes denoted by © for the first operator and <8> for the second operator, as in (9? u { o o } , © , ® ) . Therefore, in normal algebra © stands for normal addition and in min-plus algebra for minimum, while in normal algebra ® stands for normal multiplication and in min-plus algebra for normal addition. However, since <S> is also a common notation for min-plus convolution and is used for that purpose in this thesis, we use the obvious notations of + for algebraic addition, min or A for minimum, x or • as algebraic multiplication and ® for convolution, unless explicitly clarified, as in the following example. As 2 an example, we calculate the matrix operation of A for the matrix A = operation): 3 7 (for min-plus 2 4 Chapter 2. Background 15 A2 = A ®A = 3 7 3 7 . min(3 + 3, 7 + 2) min(3 + 7, 7 + 4) 6 10 2 4 2 4 « m ( 2 +'3, 4 + 2) min(2 + 7, 4 + 4) 5 8_ which is similar to the multiplication of matrices in normal algebra, by replacing addition with minimum operation and multiplication with addition. As another example, a difference equation describing a traditional system is n x(t+ 1) = Ax(t) or *,•(»•+ 1) = ^ A ^ t ) . (2.3) j = 1 In the min-plus system theory, a similar difference equation describing a min-plus system would be x(t+ 1) = ,4+Jt(0 o r 1 ) = min-iAjj + Xjit)). (2.4) The dual to the min-plus algebra is the max-plus algebra, where the infimum operator is replaced with supremum operator, resulting in almost similar theorems and results. In general, these two algebras describe two sets of systems. The systems that obey the infimum-of-sums superposition principle are called erosion translation-invariant (ETI) systems in morphological signal processing [35] and are used with the min-plus algebra. The infimum-of-sums superposi-tion principle states that the system operator, L(.), obeys Z[/wi«(c ( + x i(r))] = min(ci + L[xt(t)]). (2.5) Some other systems obey the supremum-of-sums superposition property (so-called dilation translation-invariant (DTI) system in morphological signal processing) and are used with the max-plus algebra [35]. Other than a few references in the literature, such as [34], which primarily considers max-plus theory for analyzing queuing systems, the role of the max-plus is generally complementary, only to assist in solving certain problems. Chapter 2. Background 16 Convolution and Deconvolution Operators: The <S> operator characterizes the min-plus convolution defined by (x®h)(t) = inf0<s<t{x(t-s) + h(s)}, (2.6) in which inf is infimum. A n important property of the convolution is commutativity, i.e., x <8> h = h®x. Another important operation is the deconvolution defined by (x0h)(t) = inf0<s{x(s + t)-h(s)}, (2.7) where sup denotes the supremum of a set. In max-plus algebra, the convolution is defined as (x*h)(t) = sup0<s<t{x(t-s) + h(s)}, (2.8) and the deconvolution is defined as (xUh)(t) = sup0<s{x(s)-h(t-s)}. (2.9) Min-plus System Operator and Convolution: In a linear shift-invariant min-plus system, the system operator can be defined by the min-plus convolution. If x(t) is a non-decreas-ing function representing the input, and the system function (service curve) is h(t), then Lh{'\x(t)) = x(t)®h(t) = inf0<sil(x(t-s) + h(s)). (2.10) ^h(t) For a max-plus system, the system operator L is defined by the max-plus convolution as follows: L (x(0) = x(t)*h(t) = sup0<s<t(x(t-s) + h(s)). Chapter 2. Background 17 Convex and Concave Functions: A function / is convex i f f(va + (1 - v)b) < u/(a) + (1 - u)/(/3), (2.11) for every a, b e 9t and all u e 9? with 0 < u < 1. In other words, i f f(i) has a second derivative in [a, b], then a necessary and sufficient condition for it to be convex in that interval is that the second derivative f'(t) > 0, for all t in [a, b] [42]. A function g is concave i f -g is convex. Also, g(t) is concave when g(t) > ~ &++ V*'+ P), Vp, q > 0 and W , (2.12) and g(t) < co for all f. 2.4. Traffic Characterizations Traditionally, traffic models are modeled by stochastic processes and distributions. The most notable of these are based on renewal processes, Markov chains, recursive models, transform-expand-sample models, and self-similar models [43][44][45]. Poisson models are the primary traffic models. The fundamental theory of traffic modeling is based on the Poisson renewal model, in which interarrival times of the traffic units are distributed according to an exponential distribution. The Poisson model is supported by a vast amount of literature and is used extensively. Modern measurement and understanding of traffic flows, however, suggest self-similar models for traffic [46]. Although the Poisson model is an integral part of our current understanding, design and analysis of queuing systems, there is cautionary advice about the use (or overuse) of Poisson-based traffic models. It has been well discussed and proven that this model should be avoided when dealing with many new traffic types, such as packet video or multimedia ([40], pp. 21-26). In deterministic N C , the cumulative traffic needs only to be constrained by a curve (a function). In stochastic traffic characterization, the moment generating function is constrained, which could provide more statistical knowledge than most widely used traditional traffic models [8]. Chapter 2. Background 18 Deterministic Traffic Characterizations: This model is based on the concept of arrival curves which define an envelope function for the traffic. A traffic flow x(t) is said to have an arrival curve r(t) , or to be constrained by a given non-decreasing function r(t), i f and only i f for all t > 0 and 0 < s < t, the following holds: x is also called C, -smooth. This is the main traffic model used throughout this thesis. A more elaborate definition of it and its usage wil l be presented in the next subsection. Example 2.1: A flow with an arrival curve ya b(t) = b + at, t > 0 and 0 otherwise, can be realized by a leaky-bucket shaper with leak rate of a and bucket size of b. This arrival curve, also called the affine function, is the most widely used arrival curve in N C . Example 2.2: For A T M V B R traffic and for the IntServ traffic with T-SPEC (traffic specification) ( M , P, r, b), where M is the maximum packet size; P is the peak rate; r is the mean rate; and b is the burst tolerance, the arrival curve is r(t) = min(M+ Pt, rt+b). Example 2.3: A deterministic bit rate flow, which is also improperly called "constant bit rate" (CBR), has an arrival curve defined by r(t) - rt. Stochastic Traffic Characterizations: The first stochastic characterization of traffic flows was introduced by Kurose [31], who defined a flow by a family of discrete random variables (R1., r.). Each of these random variables, R*. , defines a bound over a time length t-. Therefore, the flow is defined by x(t)-x{s) <C,(t-s). (2.13) or in compact form by S ~ {(Rk, k)\\/k > 1} . Chapter 2. Background 19 A more elaborate stochastic traffic characterization is defined in ((a(0), p(G)))-calculus using the 0-envelope [8]. This traffic characterization is based on the concept of the moment generating functions. A traffic flow x is said to have a 0 - envelope rate function, p(0) , when p(0)>a*(e), (2.14) where a*(0) is called the 0 -minimum envelope rate (0 -MER) of x, and is defined by a*(0) = limsupl^x^sups>0log(E[exp(Q(x(t + s)-x(s)))]). (2.15) This model is a stochastic extension of the arrival curves used in the deterministic N C or ((a, p))-calculus. It is shown in [8] that this traffic characterization includes more information than the usual traditional traffic models, and can be used as an alternative for most traditional traffic models. 2.5. Deterministic Network Calculus N C is a comprehensive collection of theorems, operators, and elements that form a filter-ing theory that allows us to analyze a data communication network and calculate the deterministic end-to-end QoS bounds, provided that the incoming traffic complies with certain constraints. It is mathematically founded on min-plus algebra [7]. In N C , the behaviour of an element, a node or a network (the system) is characterized by a function called the service curve [9], which is very similar to the system function defined in conventional system theory. A traffic flow is represented by a non-decreasing (or wide-sense increasing) function of time, x(t), which is the cumulative traffic until time t. Except for some special situations, it is assumed that x{t) = 0 for t < 0 . The traffic characterization is based on the concept of arrival curves (explained in the previous section) and so the traffic flow is constrained by the arrival curve. In the following, these terms and some fundamental topics in N C are discussed in more detail. Ref. [8] and [9] comprehen-sively study this new approach to networking. Chapter 2. Background 20 Arrival Curve: In NC, the traffic characterization is based on the definition of arrival curves. This concept was explained in the previous section. In a class of curves, £ ; ( r ) , that satisfy (2.13), one "good" arrival curve, C,(t), exists so that C^C,j, for all i. Such a function is subadditive ([9], pp. 15). Function f(t) is subadditive, i f and only i f f®f = f. B y using the subadditive closure, the subadditive equivalent of any curve can be found. The subadditive closure of any function g(t), g(t), is defined by g(0) = 0 and g(t) = min[g(t), min0<s<t[g(t) + g(t-s)]] f o r r > 0 [8]. B y using subadditive functions, it is ensured that the curve is an accurate model of the traffic, and results in correct calculations of QoS bounds. Service Curve: In this model, the per hop behaviour or the level of traffic treatment of a node is modeled by a curve h(t), called the service curve. This function defines the amount of service a traffic flow receives during any time interval. For the input flow x(t) and output y(t), the lower service curve guarantees that for all / > 0 and 0 < s < t, In order to define the service curve of a server as a min-plus system function, the convolu-tion operator is used. Similar to the classical system theory, this service curve is all that is needed to describe the system and to calculate the output of the system, given the input. A network element with a lower service curve h(t) for an input traffic stream x(t) satisfies where y(t) is the output, the <8> operator represents the min-plus convolution, and inf denotes infimum. If the equality holds in (2.17), then h(t) is called the service curve (or exact service curve, for clarity), i.e. y(t)>x(s) + h(t-s)). (2.16) y(t)>x(t)® h(t) = infs>t{x(s) + h(t-s)} , (2.17) .KO = x(t)®h(t). (2.18) If y(t) < x(t) ® h(t), then h(t) is an upper service curve. Chapter 2. Background 21 This concept can be exemplified by the GPS scheduler used to explain the physical meaning of a service curve. A GPS scheduler assigns a rate r to a traffic aggregate, or put differ-ently, for any time interval ([ / 0 , / ] , Vr, tQ > 0) : y(t) - ^ ( r 0 ) ^ r x ( l ~ 'o) > w n e r e *o * s t n e s t a r t ° f the last busy period. In N C terms, the scheduler has a service curve of yr 0 ( r ) = rr , resulting in y(i) >x(tQ) + yr 0(t-10), which in turn leads to y > x <8> yr 0 , as in (2.17). In the following, two widely used service curves and the network elements that realize them are introduced. Leaky-bucket Shaper: A leaky-bucket shaper is a network element with a service curve of ya b(t) = at + b, t > 0, and 0 otherwise (an affine function). The shaper forces the input traffic to an output with a rate of a and a burst size of b, and is a good example for a server with an exact service curve. The output of this shaper has ya b(t) as its arrival curve. Rate-latency Server: The most widely used service curve is the rate-latency curve. A rate-latency server is a node that guarantees a (minimum) rate R and a (maximum) delay T, when serving a particular traffic flow. The rate-latency service curve is T(t) = Rx(t— T)+. A practical example of such servers is the W F Q (weighted fair queuing) scheduler. Concatenation Property: In order to analyze a network, it is normally necessary to apply the convolution on service curves of different parts of the network and the input, either individu-ally one after the other or by applying the concatenation property. The service curve of a chain of network elements is equal to the convolution of their service curves. This is known as the concat-enation property, which allows modular modeling and analysis of networks. Deterministic QoS Bounds: For an arrival process x(t) with a given arrival curve r(t) , that passes through a system with the lower or exact service curve h(t), the three bounds on the backlog, delay and the output flow y(i) are given by these three theorems. When studying a communication network, the first theorem is used to calculate the amount of traffic that is inside the network at any given time, from which the maximum required buffer size can be calculated. Chapter 2. Background 22 Similarly, the second theorem presents a bound on the maximum delay that the traffic flow experiences. Finally, the third theorem defines the arrival curve that models the output, which is useful when the output flow is itself an input to the next network in concatenation. Theorem 2.1 - Bound on the Backlog: The backlog x(t) —y(t) for any given time t is x(t)-y(t) < v(C, h) = sups > 0(£O) - h(s)) (2.19) where v(< ,^ h) graphically is the maximum vertical distance between the arrival and the service curves. Theorem 2.2 - Bound on the Delay: The virtual delay d{t) at any give time t satisfies d(t)<k(t;,h) = sup s > 0(inf{T:T>0 and C.(s) < h(s + T)}) (2.20) where k(C„ h) graphically is the maximum horizontal distance between the arrival and the service curves. Theorem 2.3 - Output Flow: The output flow is constrained by the curve C* = supu^{C,{t + u)-h(u)} = C,<Zh (2.21) i.e., the output can be assumed to be the input traffic to the next node with an arrival curve of C*(t). The proofs of these theorems can be found in [9]. 2.6. Stochastic Min-plus Approaches Deterministic N C gives the worst-case bounds for numerous QoS metrics such as delay, service rate, and packet loss, provided the assumed conditions on the traffic and service properties are met. For some applications, though, these worst-case bounds are either loose or cannot be defined, for example, when the traffic is not deterministically constrained or when the service available can only be guaranteed within certain probability. These limitations provide the motiva-tion to consider stochastic extension of network calculus. Chapter 2. Background 23 There are two main perspectives regarding stochastic N C in the literature. Analogous to the traditional queuing theory, the first perspective assumes that traffic is stochastically constrained [8]. Instead of the traffic itself, a function of the moment generating function of the cumulative traffic is assumed to be constrained by (p(t), a(t)). The second method is based on the statistical representation of the service curve [17]. The statistically bounded burstiness method is a subdivision of the latter method [20]. As a main contribution of this thesis, a stochastic system theory approach is proposed for modeling min-plus (or its dual max-plus) systems with stochastic input or stochastic service curves. This method wi l l be elaborated upon in Chapter 4. (a(0), p(9)) -Calculus: In this calculus, traffic is stochastically characterized. A cumula-tive traffic x(t) is called a (a(9), p(Q))- upper constrained, for some 0 > 0, i f Based on this traffic characterization, the theory of effective bandwidth is introduced. This calculus is the primary stochastic method in scenarios where the traffic characterization can only be done stochastically. The service curve, however, is assumed to be deterministic. The role of the traffic and service can be swapped to represent a stochastic server [16]. However, this method is very complex and does not end up with an easy to use and general model for a practical stochastic server. Statistical Service Guarantees Method: The theory of N C is usually extended to a statis-tical framework by considering that the service represented by (2.17) is guaranteed with a pre-defined probability. In this method, the arrival process x(t) is still constrained by a deterministic curve r(t), but the system can only stochastically guarantee the service. The lower service curve Gs(t) is defined in correspondence with a probability 1 - E (as shown in Figure 2.2), so that eo(/)-*(j)) ] > p ( 0 ) ( r - s ) + o(0) , \/s,0<s<t. (2.22) P{y(t)>(x®Ge)(t)}>l-e (2.23) Chapter 2. Background 24 c > In G\t) Out < Transmitter Receiver Figure 2.2 NC-based wireless link modeling. For an exact service curve G (t), in (2.23) inside the probability equality holds. This methodology is useful and compatible with the deterministic N C . However, its application depends on the accurate definition of the service curve with a meaningful probability. Chapter 6 of this thesis is based on this method. Unlike the deterministic N C , which characterizes the worst-case bounds, in statistical N C the bounds are defined based on the probability 1 - 8 . This Gs(t) is sufficient to derive bounds on the backlog, delay and output in the system with a probability of 1 - s, using the following three theorems [17]. As before, it is assumed that the arrival process x(t) has an arrival curve of r(t) and that the output flow is y(t). The follow-ing theorems are the statistical equivalents of Theorems 2.1 to 2.3, respectively; therefore, their physical interpretations are similar to those explained earlier in Section 2.5. T h e o r e m 2.4 ( B a c k l o g B o u n d ) : The p r o b a b i l i s t i c bound for the b a c k l o g , B(t) = x(t)-y(t), for r > 0 is Pr{B(t)<C,0G\O))>\-£. (2.24) Theorem 2.5 (Delay Bound): The maximum delay is Pr(d(t)<dmax)>l-E, (2.25) where dmax = inf{d>0\Vt>0-r(t-d)<Ge(t)} (2.26) Chapter 2. Background 25 Theorem 2.6 (Output Envelope): The output process y(i) is stochastically bounded with an envelope (arrival curve), C*(t), i.e., Pr(Q*(t)<Cl(t)<Z>G\t))> 1 - e . (2.27) The proofs of the above theorems can be found in [17]. 2.7. Mathematical Transformations for Min-plus Systems Similar to the Fourier transform, a mathematical transformation with similar properties can be very useful to the min-plus system theory. The Fourier transform is an important tool in system theory. The Fourier transform of the convolution of two functions is equal to the multipli-cation of the Fourier transform of each function, i.e., F{x(t) ® y(t)} = F{x(t)} • F{y(t)}. The conversion of the convolution into multiplication usually facilitates the analysis. Chapter 3 considers such a transform, called slope transform and introduces its application as an alternative min-plus domain in the analysis and QoS provisioning of data communication networks. The slope transform is a general transformation that can be replaced by the Legendre transform when dealing with convex or concave functions. Since in the min-plus algebra, the computation of minimum replaces addition and addition replaces multiplication in a real number field, i.e., the min-plus algebra is based on the Dioid (9? u {<»}, A , +) where A is the infimum and + is algebraic addition, here the convolutions are converted into algebraic additions. 26 Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks Min-plus filtering theory (or its dual, max-plus), commonly called Network Calculus (NC), is a sophisticated modern framework for modeling and analysis of data communication networks. In this chapter, we complement N C theory by proposing the application of slope domain analysis in N C using the slope transform, an analytical framework that is analogous to frequency domain analysis based on the Fourier transform in traditional system theory. This work was inspired by the introduction of the application of the Legendre transform for this purpose in [34] , and by the slope transform-based morphological signal processing in [35]. We describe the principles and properties of slope domain analysis, and how it can be effectively applied in the analysis of computer networks. We illustrate the application of the proposed method in system identification and priority scheduling, to demonstrate that slope domain analysis is a much more convenient and efficient, and in some cases, the only, viable approach to solving some N C problems. We conclude the chapter by presenting the Legendre transform and Fenchel conjugate as close relatives of the slope transform that might facilitate fast calculations. 3.1. Introduction In this chapter, we propose the application of the slope transform [35] in modeling and performance evaluations of networks through N C theory. Similar to the application of the Fourier transform in conventional system theory, the slope transform maps functions in the min-plus Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 27 domain into another domain, called the slope domain. This transformation translates convolution operations in the min-plus domain to algebraic additions in the slope domain. The Legendre and Fenchel transforms are special cases of the slope transform. The objective of this chapter is to establish, in the same manner as frequency domain analysis in traditional system theory, an analytical framework that employs the slope domain as an effective alternative, with numerous applications to facilitate modeling and analysis of queuing systems using N C . The slope transform indicates the slope contents of a function. In N C , the traffic and service are characterized by non-decreasing functions. Since the instantaneous slope in these functions represents the traffic or service rates, the slope domain is a logical representation of the rate contents of those function, similar to the fact that the frequency content of a signal is represented in the frequency domain. In the same manner as the Fourier transform, the slope transform simplifies or even makes possible complicated N C calculations and analysis, because convolution operators are transformed into normal additions in the slope domain. The application of the Legendre transform in data networking was originally introduced by Hisakado et al. [34]. However, the Legendre transform has a number of limitations. The transform is only defined for convex or concave functions, and is usually applicable when the function is differentiable and has an invertible derivative. The application of the slope transform instead of the Legendre transform eliminates these limitations [35]. In fact, the Legendre transform is a special case of the slope transform. In addition, slope transform is applicable to both min-plus and max-plus systems. Fenchel conjugate is a close relative of the slope transform that is discussed is Section 3.10. Concurrent with the development of our slope domain model, there are some works on the development of such alternative domains by Pandit et al. [36], and by Fidler and Recker [37], based on the application of these transforms for convex functions. The slope transform is a general mathematical transform that was originally introduced in morphological signal [35] and image processing [47][48], and has been proven to have a similar set of properties and characteristics as the Fourier transform. Two types of slope transforms, upper and lower slope transforms, target the max-plus and min-plus algebras, respectively, and are closely related. Dealing with data communication systems, we mainly work with systems that obey the infimum-of-sums superposition, and thus the min-plus algebra; consequently the lower Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 28 slope transform is primarily used. However, we address both lower and upper slope transforms here for the following reasons. First, they are very closely related and both are involved in some properties, e.g., P9 in Table 3.1. Second, max-plus algebra has been used in some previous work to model queuing systems as well, such as in [34]. Finally, both are used in describing some of the slope transform properties such as the reverse transformations, as well as facilitating notations. The Legendre and Fenchel transforms are special cases of the slope transform. Their original forms, however, have some limitations, as primarily they are defined for and are applied to convex or concave functions [42]. Even the extended definition of the Legendre transform fails to inclusively serve in all N C applications, since the transformation result wi l l be set-valued, i.e., the result wi l l be a set instead of a single value [34]. In the next section, the slope transform, its properties and some important theorems are addressed. The application of the slope transform in modeling queuing systems is presented in Section 3.3. The slope domain modeling approach is then applied in various applications, such as priority scheduling (Section 3.4), network identification (Section 3.5), and optimal smoothing of multimedia streaming (Section 3.6). The concept of load spectrum, traffic aggregation, and slope selective filters are other useful applications that are presented in the following sections. In Section 3.9, the slope transform is compared with the Fourier. The benefits and limitations of two special cases of the slope transform, the Legendre transform and Fenchel conjugate, and some practical considerations for fast computations, are discussed in Sections 3.10 and 3.11. Finally, a summary in presented in Section 3.12. 3.2. The Slope Transform The Fourier transform is an important tool in conventional system theory. The Fourier transform of the convolution of two functions is equal to the product of the Fourier transforms of functions, i.e., F{x(t) ®y(t)} = F{x(t)} • F{y(t)}. The conversion of the convolution into multiplication usually facilitates the analysis. The slope transform serves as a tool analogous to the Fourier transform in min-plus algebra. Since in min-plus algebra the addition and computation of minimum replace multiplication and addition, respectively, in the field of the real numbers, correspondingly the convolutions are converted into algebraic additions in the slope domain. The Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 29 slope transform can similarly be applied to max-plus algebra, which is dual to min-plus algebra, with similar concepts and properties. The max-plus properties can be derived i f minimum is replaced by maximum and infimum by supremum [9]. The Slope Transform: The slope transform indicates the slope contents of a min-plus function. For any function x(r):SR —» SR u { + 0 0 } , its lower slope transform is defined by XL(a)-M -> SR u { ± 0 0 } as follows [35] : XL(a) = SL{x(t)}(a) = infte^(x(t)-at). (3.1) Similarly, the upper slope transform is defined by Xv(a) = ^ { x ( 0 } ( a ) = sup, e n(x(t) - at). (3.2) From these definitions, it can easily be shown that the upper and lower slope transforms are related by the following expression: SL{x(t)}(a) = - ^ { - x C O K - a ) = -Su{-x(-t)}(a). (3.3) Proof: SL{x(t)}(a) = inft{x(t) - at) = -sup,{-x(t) + at} = -supt{-x(t)-(-a)t} -» -Su{-x(t)}(-a) = -sup_x{-x(-x) + a(-x)} = -supt{-x(-t) - at) - » -iS'[/{-jc(-r)}(a) • In this chapter, unless otherwise specified, by slope transform we mean the lower slope transform. The lower slope transform is always concave, and the upper slope transform is always convex. I f the function x(t) is convex and has an invertible derivative, then its Legendre transform is equal to its lower slope transform. Similarly, i f the function x(t) is concave and has an invertible derivative, then its Legendre transform is equal to its upper slope transform. If the function is neither concave nor convex, then its Legendre transform is not single-valued, but its slope transform is defined regardless. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 30 The following two theorems supply the required tools for the application of the slope transform in min-plus (or equivalently in max-plus) algebra and consequently in N C analysis. Theorem 3.1. For min-plus functions x(t) and y(t), we have S{x®y} = S{x}+S{y}, (3.4) where <8> is the convolution operator. Proof: S{x(t)®y(t)} = inft{infz{x(x) + y(t-x)}-at} = infx{x(x) + inft{y(t-x)-at}} = infx{x(x) + Y(a) - ax} = X(a) + 7 ( a ) • Figure 3.1 illustrates this theorem regarding the input-output relation of a system with a service curve h(t). Following an analogy to the traditional system theory, H(a) is called the slope response of the system. Theorem 3.2. For any function, x(t), the function x(t) = supa(XL(a) + at), (3.5) expresses the inverse lower slope transform of x(t), i.e., x(t) ->X(a)->Jc(0- (3-6) This relationship can be better described by using both lower and upper slope transform notations, as follows: X(a) = SL{x(t)}(a) x(t) = Sv{X(a)}(-t) (3.7) Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 31 X(t) y(t) = h(t)®x(t) X{a) H{a) Y(a) = H(a)+X(a) Figure 3.1 Modeling a network in NC and slope domains. If x(t) is convex, then x(t) = x(t); otherwise for al l t, x(t) <x(t). Therefore, (3.7) reduces to S^S^x^t)}} = *( - 0 for a convex function, proving a duality between time and slope domains. X(a) is always concave and x(t) is always convex. Similarly, the inverse upper slope transform is defined, following its duality to the lower slope transform. We view function x.Xi) as an inverse upper slope transform, where x(t) < x^t). x^t) is always concave. If x(t) is concave, then x(t) = x^t). I f the first transformation is the upper slope transform, then the reverse transformation is the lower slope transform and vice versa. Table 3.1 summarizes the properties of the lower slope transform. For the proofs, the reader is referred to [35]. Similarly, Table 3.2 summarizes the properties of the upper slope transform. In the tables, t0 indicates a constant shift in time, and a 0 a constant shift in the slope domain. (3.8) Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks > 32 Table 3.1 Properties of the lower slope transform. Property Function Lower slope transform Definition x(t) X(a) = inft{x{t) - at) PI infiict + XjO)} inf^ + X^a)} P2 x(t-tQ) X(a) - atQ P3 x(t) + a0t X(a - a 0 ) P4 x(rt) X(a/r) P5 rx(t), r>0 rX(a/r) P6 x(-t) X(-a) P7 x(t)®y(t) X(a) + 7(a) P8 sup(x(t),y(t)) > sup(X(a), 7(a)) P9 x(t)+y(t), y is concave XL(a) eg) Yv(a) Table 3.2 Properties of the upper slope transform . Property Function Slope transform Definition x(0 X(a) = sup {x(t) - at) PI SUPjiCj + Xjit)} suptiCi + Xjia)} P2 x(t-t0) X(a) - at0 P3 x(?) + a0t X(a - a 0 ) P4 x(rt) X(a/r) P5 rx(t), r>0 rX(a/r) P6 x(-0 X(-a) P7 x(t)*y(t) X(a) + 7(a) P8 inf(x(t),y(t)) < inf(X(a), 7(a)) P9 x(t)+y(t), y is convex Xria)®YL(a) Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 33 3.3. Slope Domain Analysis of Networks Based on the two theorems described in the previous section, slope domain provides an alternative to traditional N C methods for modeling and analysis of data communication systems. In this section, we first derive the slope transforms of some well-known arrival and service curves, and specialized functions in N C . Thereafter, we illustrate the methodology by presenting its applications in priority scheduling and system identification. The notations used throughout this chapter are chosen to be as close as possible to those in [9] and [35], for ease of reference. A s explained in the previous chapter, computer communications systems obey the infimum-of-sums superposition property. These ETI systems are well suited to be used with the lower slope transform. Some other systems are DTI systems that obey the supremum-of-sums superposition property and are used with the upper slope transform. Example 3.1: The slope transform of the zero impulse function defined by H z(0= I °' t = ° ' (3-9) I -co, t*0, is SL{-\iz(t- t0)} = Sjj{p.z(t-10)} = -atQ, where t0 is a constant shift in time. Example 3.2: The zero step function is defined as M 0 = 1 °' t " 0 ' ( 3 1°) [ -co, t<0. The lower and upper slope transforms of the zero function with a constant shift in time, t0, are SL{-'k(t-t0)} = -at0 + X(-a) and £ ^ { ^ ( 7 - r 0 ) } = -oU 0 - A , ( a ) , respectively. B y subtracting (adding, in the upper slope transform) a zero function from any function a r ight-s ided function is formed. For a r ight-s ided (or causal) function x(t), we have Si{x(t)} = inft>0(x(t)-at)) = inf((x(t)-X(t)-at)) = SL{x(t)-X(t)}, i.e., the lower slope transform of x(t) is equal to SL{x(t)-X(t)}. Similarly Sv{x(t)} = 5 , c /{x(r) + X(t)}. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 34 The Delta function that is sometimes used in the N C literature can be defined using the zero function by 8^(0 = -X(-1 + T). Example 3.3: The affine function is yr b(t) = b + rt for f >0 and 0 otherwise, and characterizes the output of a leaky-bucket server with parameters (b,r). Since the function is right-sided, its lower slope transform is ^ { y ^ 6 ( 0 - A,(r)} = X(r-a). Quite interestingly, a leaky-bucket node behaves like a slope lowpass filter. When expressed in the slope domain, it rejects all of the slopes (rates) greater than r and passes the rest. Similarly, 5 ^ ( 7 ^ ( 0 +MO} = M<*-r) . F o r a n o n - c a u s a l a f f ine f u n c t i o n , a + pr, t a k i n g s i m i l a r s teps, we have ^ { r j + pf} = rj + | i z ( a - p ) . Also, SL{o + pt-X(t)} = a + M p - a ) . Example 3.4: The peak rate function that describes the C B R traffic is pR(t) = Rt, for t > 0. With similar manipulations used in Example 3.3, we have SL{Rt- MO} = M ^ ~ °0 • Example 3.5: The rate-latency function, $R T(t) = R(t-T)+, is a widely used N C function that particularly characterizes a rate-latency server which was explained in Section 2.5. The slope transform of this function is derived as follows: S{R(t-T)+}(a) = inft(R(t-T)+-at) = inf(inft>T(R(t-T)-at), inft<T(-at)) inf(-co, -aT) = -co a > R infi-aT, -aT) = -aT 0<a<R inf(-aT, -co) = -oo a < 0 = X(R - a) - Ta + \(a) Table 3.3 tabulates the lower slope transforms of some well-known N C functions for ease of reference. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 3.4. Non-Preemptive Priority Scheduling Example 35 Consider a scheduling system that employs non-preemptive priority scheduling to serve incoming traffic with two classes of priority (high and low). This type of scheduler is typically used in DiffServ-based Internet. The server serves the queue with a constant rate C , while an absolute non-preemptive priority is given to the high priority traffic class. It can be easily shown that this scheduler serves the high priority flow as a rate-latency server fiR T(t) with parameters L L + L R = C and T = lmax/C, resulting in service curve P(r) = C(t-lmax/C) , where lmax is the maximum packet size of the low priority traffic ([9], pp. 21). In N C , for any high priority traffic described by the arrival rate /*(t), the output is calculated by y\t) = (/* <8> P)(0, using the convolution operator. As an illustrative example, assume that the high priority traffic has an arrival curve of f1 (0 = Pr(0 = rt-> 0 <r<C, known as C B R traffic. Using the N C convolution, the output is equal to ( p r ® P ) ( r ) = min{r(t-lLmax/C),C(t-lmax/C)). (3.11) Table 3.3 Lower slope transforms of some useful NC functions. Function Lower slope transform -X(t-t0) -oU0 - X(a) b + rt b + u z(a - r) Y r . j C O - M O X(r-a) ^ (0 = Rt-X(t) X(R - a) PR,T = Rx(t-T)+ X(R - a) - Ta + X(a) exp(t) a( l -log(a))-A,(a) rK ' - ' o ) -ra'o Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 36 Slope domain analysis, however, provides a more convenient solution. Relying on Theorem 3.1, the output can also be derived using slope domain analysis by calculating 7(a) = F ^ ( a ) + 5 ( a ) . By using Theorem 3.1, we derive S{/;r} + S{P} = (lLmax/C)a + X(r-a) + X(a), since 0 < r < C. This is simply the slope transform of the function (f* ® P)(0, formulated by (3.11). Figure 3.2 graphically illustrates these functions. Following a similar procedure, the low priority flow is served by a rate-latency server with rate R = C- r and latency b/(C- r). A s a comparison, in the above example, we replace f1 (t) = pr(t) = rt with a leaky-bucket shaper which has an arrival curve of f1 (t) = yr b(t), 0 < r < C, and /*(0) = 0. Using the N C convolutions, the output is equal to (Y r,6®P)(0 = min(b + r(t-lLmax/Q,C(t-lLmax/C)). (3.12) Similar to the previous example, by using Theorem 3.1, we have SM+S { P } = (lLmax/C)a + X(r-a) + X(a), s ince 0 < r < C. T h i s is a lso the s lope t r ans form o f the func t ion {J1 ® p)(r)» i-e. S{yr b ® P} = (lLmax/C)a + X(r-a) + X(a). However, as discussed in Theorem 3.2, when a function x(t) is not convex, the inverse slope transform of its slope transform results in a function x(t) <x(t). Since yr b ® p is not convex, we observe that the inverse slope transform o f 5{Y r > i®P} i s ^{^{y^®P } } ( -0 = mm(r(t-lLmax/Q,C(t-lLmax/C))<yr>b®p. However, the difference between these two functions is always less than b, and negligible in practice as r » b. Figure 3.3 graphically illustrates theses functions. er 3. Slope Domain Modeling and Analysis of Data Communication Networks Figure 3.3 Slope transforms of the affine and rate-latency functions, and their convolution. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 39 3.5. Network Identification Application A prominent application of the slope transform is the identification of the minimum service curve of an unknown node or network, a practice analogous to the system identification concept in traditional system theory. System identification is used in manifold applications, such as modeling, measurement and control of arbitrarily complicated networks. While it is practically impossible to use normal N C filtering theory in this application, we show that the slope transform can be readily employed to derive the slope response of any system. Assuming that the input x(t) and output y(t) to a system is known, we know that y(t) = x(t) ® h(t), where h(t) is the system service curve. Other than for simple functions, it is mathematically very difficult to solve this convolution-based equation to find h(t). However, using the slope domain, the system is naturally identified by Therefore, knowing the slope transforms of some known input and output curves, and using (3.13), one can readily obtain the slope response of the system. Although (3.13) explains the concept and presents a clear and logical way of finding the slope response of a system, in the following we introduce another more practical and numerically attractive approach. The method is based on direct observations of the outputs of the system to a set of affine functions, since the affine function is the eigenfunction of min-plus systems, i.e., Therefore, in order to find the slope response of a system, we need to feed a set of affine functions related to a set of desired a,- values, and then by using (3.14), the corresponding set of / f ( a ; ) values can be calculated. In practice, these functions can be obtained by using a leaky-bucket server that is saturated, and therefore outputs a traffic resembling the affine function. H(a) = L{y(t)}-L{x(t)}. (3.13) y(t) = (at + b)®h(t) = inf{a{t-x) + b + h(x)} = at + b + H(a). (3.14) Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 40 This is a favorably effective method both in theory and in practice, as it works by observ-ing the actual outputs to a set of inputs, and does not require using any convolution or slope transformation. To demonstrate the methodology by an example, let us assume that a hypothetical 2 network has a service curve o f h(t) = 5t + 3t -X(t). The lower slope transform of this 2 function, and therefore the system's slope response, is equal to H(a) = ( - l / 1 2 ) ( a - 5 ) . Details of the analytic derivation of H(a) are presented in Section 3.11. If we consider a set of 10 affine inputs with the form at + b, 5 < a < 95 and 6 = 4 (shown in Figure 3.4a), and then subtract the corresponding set of the observed (or calculated) outputs from these affine functions (shown in Figure 3.4b), the results are equal to the values of the slope response at the corresponding a(- values. As shown in Figure 3.4b, it takes some time for the network to exhibit the corresponding value of the slope response, particularly with smaller values of a , . This lag is due to the fact that up to this time, the input is much less than the available guaranteed service. Figure 3.5 compares the plot of the analytical slope response with that calculated using the above methodology. As shown in the plots, we were able to identify the slope response of the unknown system by observing the outputs resulting from the affine functions. In order to explain what the points are whose envelope represents the slope response, we present here the actual set of values of the calculated H(a) for the instance of a = 25 . This set of points (represented by the coloured dots highlighted on the figure) are the equidistant time samples of the plot associated with a = 25 in Figure 3.4b (one sample every time unit, which is Is here). The result is a set of 31 values of [-4, -21 , -32, -37, -16, -33 , - 3 3 ] . As we see, after just 5 values, it reaches a steady value of-33 and stays at that value (representing the slope response at a = 25) for the rest of the set. In fact, the envelope consists of the overlap of many points of equal value that represent the steady state value. Similar to the behaviour of the traditional system functions, we also observe a small overshoot with the minimum value of-37, just before we reach a steady state condition. Similarly, for a = 75 , it is observed that after 12 initial values, it reaches the steady state value of -408 (also highlighted on the figure). Chapter 3. Slope Domain Modeling and Analysis of Data Communication Ne works 41 3000 Time (Sec) Figure 3.4 System identification by applying the slope domain analysis: (a) Plot of the service curve and inputs of the form b+at for different values of a. (b) Plot of the observed outputs minus the inputs. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 42 X 0 -100 -200 -300 -400 -500 -600 -700 • • 0 • • • • A T V • a =25 i ' • • — • — . • • • • • • • • • • I I 1 1 1 1 1 1 1 1 • • • a • • • r r i i i ! a = 7 5 - ^ 1 I T 1 • W 1 * r r i i i i i i 1 • i • • • • m v ^•—Analytic slope response \ • • Slope responses derived from the observed outputs }J i i < i 0 20 40 60 80 100 a Figure 3.5 System identification by applying the slope domain analysis: Comparison of the numerical result with the analytical slope response. S imula t ion Methodology: The previous analytical calculations were carried out in MATLAB® 1 . In the following, the results from the analytical calculation are compared with the simulation results by using the OPNET® modeler. The simulation methodology is as follows. A source generates a traffic stream with exponential inter-arrival times and constant packet sizes. This traffic is then shaped based on the y b(t) = att + b function. The traffic source is set so that the shaped traffic, x(t), is as close as possible to the arrival curve, i.e., in the definition of the arrival curve equality holds (x(t) -x(s) = ya b(t-s)). The network is modeled by a work 2 conserving scheduler with the service curve of h(t) = 5t + 3t , i.e., the scheduler ensures that during any time interval [s, / ] , the amount of service dedicated to the traffic flow equals h(t-s). A s expressed by (3.14), the cumulative traffic received at the destination is equal to y a b(t) + / / ( a ; ) . Then by using (3.14), the corresponding H(a{) is calculated. Since the MATLAB is a registered trademark of The Math Works, Inc., and OPNET is a registered trademark of OPNET Technologies, Inc. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 43 200 100 0 -100 _ -200 x -300 -400 -500 -600 -700 '••-Calculated slope response • OPNET outputs minus (b+ at) 0 20 40 60 80 100 a Figure 3.6 System identification using OPNET simulations. measured / / (a ,) reaches a steady value (as shown in Figure 3.4b for t > 15s), only one value of the cumulative traffic received at the destination at any of these steady state times is needed. Thus, the measurements can be done offline or online. The simulation is repeated for all the previous 10 values considered for at. Figure 3.6 compares the calculated slope response from the above analysis with the scaled simulation results. Similar to Figure 3.5, the points represent the measured values of H(<x^ versus a , at equidistant time samples during the simulation. The plot shows that the simulation results match closely with the analytic results, and therefore demonstrates that the slope domain analysis method closely identifies the slope response of the network. As seen, the results from the simulation exhibit some unexpected values, in addition to the overshoot effect seen in the analysis. This is mainly due to the fact that the actual traffic flow to the network is not exactly of the form ya b(t) - at + b; also in each simulation, the system needs some time to reach its steady state condition. However, the envelope of the results closely matches the expected slope Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 44 response. Discussion on the practical application of the method: The above method helps us find the service curve of an unknown network, or to verify that an implemented network actually behaves according to the required service curve. In order to apply the above method to identify a network, we must consider the following issues: 1) The method works only i f the network under examination has been designed to serve based on a service curve. It goes without saying that i f the time domain convolution does not hold in the first place, the obtained results wi l l not be meaningful. Therefore, the method applies only to QoS-based networks or network elements, not to best-effort ones. 2) A practical issue for using the network identification method is to consider a proper set of values for a (-. Here we discuss the situations when too large or too small values are chosen. First, it is worth emphasizing that a service curve is guaranteed for a specific input traffic flow, only i f the flow obeys the negotiated arrival curve. Therefore, input traffic flows with large values of a ; do not comply with the negotiated service quality constraints, and wi l l be served only up to the negotiated service quality. In theory, this w i l l not have an impact on the application of the method, since the value of H^a,) (which is a negative value) decreases as a(- increases. However, practical systems do not have infinite buffer sizes and the excess traffic may be dropped. In this condition, the observed output traffic flow no longer represents what we expect by (3.14). Second, i f the values of a(- are chosen too small, then it may take a long time for the system to serve enough traffic to reach a steady state. If the test duration is short, the results w i l l not reflect the slope response of the network. This condition can be viewed from Figure 3.4, when t< 10s. However, as explained earlier, the measurements can be done online, so the test duration can be set dynamically. This is done by observing the measurements, and stopping when they reach a steady value. These conditions occur when the network is completely unknown, and the range of values for a(- or the test duration is not selected correctly. In practice, we usually have a basic understanding of the examined network that helps us consider educated values for a ;-. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 45 3) In a network, service curves are usually associated with specific input traffic flows. For example, a network of W F Q (weighted fair queuing) schedulers serves different traffic classes with different service curves. Therefore, the traffic has to be tagged with an appropriate traffic class. 4) The method works only for shift-invariant service curves. This is a reasonable assump-tion for most QoS-aware networks, such as IntServ, Diffserv and A T M , and is a desirable charac-teristic for man-made systems. The validity of such an assumption can be tested by repeating the identification method for the same input traffic and comparing the received output traffic flows. A related condition is when a faulty node is in the path of the traffic flow. In this condition, the service curve has actually changed; therefore, the results w i l l not reflect the service curve of the network in normal conditions. 5) When a server is not exact, it guarantees that the complying traffic stream wi l l receive a minimum (or maximum) service defined by the service curve (as explained in Chapter 2). As an example, assume that a W F Q server assigns a lower service curve (t - Tt)rt to class i. This traffic class wi l l be served more that the amount specified by this service curve, i f other traffic classes are not fully using their shares. Therefore, it should be ensured that there is enough mix of traffic in the system, when the purpose is to identify lower service curves. This way, the examined traffic flow w i l l receive only up to its assigned service and the results w i l l reflect the correct service curve. 6) In order to create the required affine functions, leaky-bucket shapers in saturation can be used. However, in practice the values and range of values of a,- that can be actually achieved depend on the practical aspect of implementing a leaky-bucket server that is capable of working with the required range of rates. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 46 Decoding y(t) Buffer Decoder Smoother Figure 3.7 Video streaming network topology. 3.6. Optimal Smoothing for Multimedia Streaming In a network that offers guaranteed service based on a service curve G(t), to variable bit rate (VBR) traffic A(t) that is smoothed using a traffic envelope ^(r) , an optimal strategy for the smoother exists that minimizes the playback delay and the required receiver buffer size [41]. Therefore, in contrast to shaping or rate control, smoothing focuses on meeting the QoS criteria at the receiver side. Figure 3.7 shows the assumed system topology. Optimal smoothing is explained and used in Chapter 6. For such a scenario, the optimal smoothing strategy, and correspondingly, the required minimum playback delay and buffer size, are expressed by the following main results [41]: R I ) The minimum playback delay is defined by D = h(A,^®G), (3.15) where h(A,fi) = sups>0{inf{ T: T> 0 and A(s) < p(s + 7)}} R2) The optimal smoother is A' = A0(Z,®G). (3.16) The optimum output A\t) gives the latest time at which every packet of the flow should be scheduled ([41], pp. 690). Note that A\t + u)-A\t) < ^(w). R3) The maximum optimal required buffer size is X~ = supt>0{A-(t) -A(t)}, where Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 47 A~(t) = A ® £, is the shifted optimal smoother output ([41], pp. 693). Now we show that analogously, and somewhat more easily, the slope domain approach can be used to present or implement the above results. We first present and prove some required concepts. P r o p o s i t i o n 3.1. For any function f(t, x ) , inft{infx{f(t,x)}} = infx{inft{j\t,x)}} . Proof: Assume that infx{f(t,x)} = g r ( 0 and inft(gx(t)) = m'. Then for V(r, x ) , m'<f(t,x). N o w assume that inft{f(t, x)} = g2(x) and infx(g2(x)) = m". Then for V(r, x ) , m" <f(t,x). Then m" = m', concluding the proof. • P r o p o s i t i o n 3.2. For a set of real numbers, M : sup(M) = -inf(-M). Proof: Let m - sup(M), i.e. V m ' e M, m>m'. Then -m < -m', i.e. -m = inf(-M). • T h e o r e m 3.3. For two min-plus functions x(t) and y(t), SL{x0y} = SLW-SUW, where 0 is the deconvolution operator expressed by (2.7). Proof: SL{x(t)0y(t)} = inft{infx{x(t + x)-y(x)}-at} = infx{inft{x(t + x)-at}-y(x)} = ^ / T { ^ r ( a ) + a x - ^ ( x ) } = XL(a) + infx{ax-y(x)} = XL(a)-Yu(a) • In the second line, Proposition 3.1 is used. In the third line, P2 of Table 3.1 is applied, and finally, in the fifth line, Proposition 3.2 is used. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 48 In the following, the equivalent slope representation of R I and R2 are presented. R3 can be used as is and needs no extra manipulations. Proposition 3.3. For two functions x(f) and y(t), i f x <y V r , then S{x(t)} <S{y(t). Proof: x<_K=>x-ar<j>-ar=> inft{x - at) < inft{y - at) , proving the proposition. The proof is based on the fact that i f x <y then inf{x} < inf{y). • R I - S) Expression (3.15) in RI translates to D = h(S{A}, S{t,} + S(G) - aT). Proof: h(A, G) is the maximum value of the set of the smallest 7"s that for each s > 0 satisfies: A(s) < G(s + T). Using Proposition 3.3, h(A, G) is also the maximum value of the set of the smallest T's that for each A satisfies: ^{^(s)} < S{G(s)} +aT, which again translates to the maximum horizontal distance between the slope transform of A(s) and the shifted slope transform of G(s) . The slope transform of G(s) is shifted by aT which is a simple line in the slope domain with a constant slope of T. Therefore, h (A, % <8> G) is the maximum value of the set of the smallest T's that for each s, s > 0 satisfies A(s) < (^ eg) G)(s + T). Therefore, (3.15) is equal to It is worth noting that (^ eg) G)(t + T) is not equivalent to the convolution of %(f + T) and G(t + T), which by using Theorem 3.1 incorrectly results in S{a} - aT+ S(p) - aT. But (aCg>p)(r) needs to be c a l c u l a t e d , and then a shif t i n t ime o f t+T needs to be D = h(S{A},S{$}+S(G)-aT). (3.17) applied. • R2 - S) Using Theorem 3.3, (3.16) can be rewritten as SL{A'} = S ^ - i S ^ + S^G)) (3.18) Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 49 3.7. Load Spectrum Power spectrum is the application of the Fourier transform to stochastic signals and systems. Similarly, based on the theorems presented in the next chapter, the concept of the load spectrum is introduced, which extends the application of the slope transform to the stochastic settings. This concept is addressed in detail in Chapter 4. 3.8. Further Applications Slope domain may be used in many other applications. One can look at numerous applica-tions of the Fourier transform and find or replicate similar applications for the slope transform. In the following, several more of these applications are addressed. Slope Selective Filters: A practical advantage of the slope transform is its application in filtering certain slope elements. Principal filters that are normally used in traditional system theory to design various filter actions include low-pass, band-pass and high-pass, notch and all-pass filters. These filters filter out parts of a signal with certain frequency content. Slope domain modeling provides similar types of servers. Slope low-pass filter. As we saw earlier, the leaky-bucket shaper is a slope low-pass filter. In general, a slope low-pass filter is defined by a 0 r - X(t), with a slope response of A,(a 0 - a ) , which rejects all slopes higher than oc0 and passes the rest. Similarly, these filters can be used to devise more advanced filters, by using them in concatenation or in parallel. Traffic Aggregation (Slope Domain Modulation): In traditional system theory, the multiplication of two signals results in the convolution of the signals in the frequency domain (called modulation). In the min-plus theory, the addition of two signals results in their convolution in slope domain, which we call slope modulation. Therefore, when a number of traffic flows are multiplexed (added), the slope domain of the resulting traffic flow is their slope modulation. This concept may provide insight into the concept of traffic aggregation versus per-flow analysis. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 50 3.9. Comparing Fourier and Slope Domains The Fourier transform is a fundamental tool in the study of signals and systems and has many applications. In particular, this transformation provides valuable insight and effective tools in many aspects of design and analysis of communication systems, filtering methods, and signal processing algorithms [49] [50]. The slope transform is in many respects similar to the Fourier transform. The main advantage of both transforms is the transformation of the convolution operator into easier algebraic operators. This property not only facilitates many mathematical calculations, but also creates a myriad of properties with important applications, such as the modulation property. Interestingly, most properties of one transform are similar to those of the other and can be guessed from the other, for example, the time shift or scaling properties. In fact, many of the applications and properties considered for the slope transform are inspired by the corresponding Fourier transform concepts. In the following, some of the prime characteristics of each are compared. 1) For any system, the response to the signal ael* is aH(s])eSlt, where aex' is the eigenvalue and H(s{) is the eigenfunction of the system. In addition, axe + a2e —>alH(sl)e + a2H(s2)e . For any min-plus system, for the input at + b we have at + b —» at + b + S(a), where at + b is the eigenvalue and S(a) is the eigenfunction of the system. In addition, min(axt +bx,a2t +b2) = (axt + b^ A a2t + b2) (alt + bl A a2t + b2) -> bx + •S'(a1) A a2t + b2 + S(a2)) 2) In the Fourier domain, the following relationships hold for the fundamental operators of (+ , x ) and <8>: For (+):F{x(t)+y(t)} = F{x(t)} + F{y(t)}. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 51 F o r (x ) : F{x(OxXO} = F{x(t)} ® F{y(t)} . For convolution: F{x(t) ®y(t)} = F{x(t)} • F{y(t)} . Similarly, in the slope domain, the following relationships for the fundamental operators of (A, +) and Cg) hold: For (A): S{x Ay} = S{x} AS{y}. For (+) : S{x+y} = S{x} eg) S{y}. For convolution: S{x ®y) = S{x) + S{y}. It is crucial to note that the addition and multiplication operators in the traditional algebra are replaced with the minimum and addition operators in min-plus algebra, respectively. Also, the idempotent property of the min-plus algebra plays a unique role in both time and slope domains. 3.10. Comparing Slope with the Legendre Transform and Fenchel Conjugate The objective of this chapter in presenting the slope domain methodology was to find the best transformation domain for the application of the min-plus system theory in data communica-tions networks. This work was originally motivated by the introduction of the application of the Legendre transform for this purpose in [34], and by the slope transform-based morphological signal processing in [47]. Therefore, we need to introduce the Legendre Transform and Fenchel conjugate and compare them with the slope transform. Concurrent with our work, some recent papers have been published on these transforms that focus only on convex functions [36][37]. The Legendre transform is a familiar transform in the mathematics of min-plus algebra. The Legendre transform presents some drawbacks, for example, it is only defined for convex functions, and is only in accordance with min-plus algebra. In contrast, the slope domain model is complete and systematic and considers all cases. Actually, the Legendre transform is a special instance of the slope transform that is defined for and used with convex or concave functions with invertible Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 52 derivatives [47]. The Fenchel conjugate is a close relative of the upper slope transform. Since a vast quantity of literature is available on them, they also bring further insights to the application of and analysis in the slope domain. Legendre Transform. For a concave or convex function x(w) which has an invertible derivative, its Legendre transform is defined as [34] T{x (r )}(s) = x(u*)-su*, where 5 = d(x(u*))/du, (3.19) s is the slope of the function at u*, as s = l im —x(w_) «-»«* u — u* Writing (3.19) based only on the variable s [35], the transform is also defined as ¥{*(/)}(*) = x((xr\s))-S[(xr\s)]. (3.20) If a function in the Legendre domain, X, is also convex or concave and has an invertible derivative, then the inverse Legendre transform is defined by X(t) = x((xy\-t)) + f[(jn-1(-o] • (3-2i> Fenchel Conjugate. For a function c(x), its Fenchel conjugate is defined as [51] 3{c(x)}(0) = supx(Qx-c(x)). (3.22) The Fenchel conjugate is closely related to the slope transforms. The slope transforms can be expressed by the Fenchel conjugate, as follows: SL{x(t)}(a) = m/, e S R(x(/)-aO = -supt e ^(at-x(t)) = - 3 { x ( r ) } ( a ) , and Su{x(t)}(a) = supteyi(x(t)-at) = supt sy{((-a)t-(-x(t))) = 3 { - x ( r ) } ( - a ) . Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 53 Similar to the slope transform, the Fenchel conjugate can be used with al l functions. However, the main focus of the literature addressing the Fenchel conjugate is on convex functions, since when applied to a reasonably convex function, the function can be reconstructed by applying the Fenchel conjugate a second time. Originally, it was defined as an alternative to the Legendre transform, based on the supremum notation. Therefore, unlike the Legendre transform, it does not require the function to be differentiable. The next section discusses how the Legendre transform and Fenchel conjugate may serve as useful tools to facilitate calculations and enhance the application of the slope transforms. 3.11. Computational Improvement Using the Legendre Transform and Fenchel Conjugate The slope transform is comprehensive, straightforward and self-sufficient both in analyti-cal and numerical computations. However, due to the proximity of the slope transforms with the Legendre transform and Fenchel conjugate, the literature related to these transforms are advanta-geous and can be used to facilitate calculations of the slope transforms both numerically and analytically. In the following, we present two important applications. 1) As mentioned earlier, the Legendre transform of a function is equal to its lower slope transform when the function is convex with invertible derivatives, and is equal to its upper slope transform when the function is concave with invertible derivatives, ignoring possible differences due to boundary effects. Since the Legendre and the reverse Legendre transforms have easier-to-find and easier-to-use closed-form representations, when applicable, the Legendre transform provides an easier way of finding the slope transform of a function analytically. 2 As an analytical example, for the parabola function x(u) = u , the lower slope transform is equal to its Legendre transform, i.e. SL{x(u)}(s) = ¥{x (0}(s) = (s/2)2-s(s/2) = -s2/A. Chapter 3. Slope Domain Modeling and Analysis of Data Communication Networks 54 Another analytical example is the function x(t) = 5t + 3t , which we used in Section 3.5. Similarly, since it is convex and has invertible derivatives, its lower slope transform is equal to its Legendre t r ans form, w h i c h is easier to de r ive . We have a = x'(t) = 5 + 6t, then t = ( (a - 5 ) / 6 ) . Using (3.20), we have XL{a) = 5 ( ( a - 5 ) / 6 ) + 3 ( ( a - 5 ) / 6 ) 2 - a ( ( a - 5 ) / 6 ) , 2 resulting in XL(a) = (-1 / 12)(a - 5) . Since the function is causal and is zero for t < 0 , then XL(a) is defined as above for a > 5. 2) The close proximity of the slope transforms with the Fenchel conjugate allows us to use the efficient algorithms that are available for the calculation of the Fenchel conjugate, for numeri-cal computation of the slope transforms. A number of such fast computation methods are the fast Legendre-Fenchel transform [52], linear-time Legendre-Fenchel transform (LLT) [53], and parallel fast Legendre-Fenchel transform [54]. These algorithms serve a role analogous to FFT in the conventional system theory, where they can be used in the analysis of complex networks with arbitrary arrival and service curves. 3.12. Summary In this chapter, we have introduced the slope domain analysis of queuing systems as a complement to the N C approach. The transform and related properties are discussed and the slope transforms of useful N C service curves and arrival curves have been tabulated. We have elaborated on the efficiency of the slope transform in the analysis of computer networks, by applying the methodology to system identification and non-preemptive priority scheduling problems. We have discussed the special cases of the Legendre transform and Fenchel conjugate as useful tools for fast calculation of the slope transform for some common functions. 55 Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks In this chapter, we develop a framework for efficient stochastic QoS evaluations and cross-layer design in wireless networks. The methodology is based on a proposed stochastic min-plus system theory. This novel theory characterizes the second-order statistics of the system output and can be used to model or analyze any stochastic system, in particular a wireless channel, with manifold advantages. Due to its clearly similar representation to the familiar traditional stochastic system theory, it is an easy yet elaborate modeling and performance evalua-tion tool, even with just a basic familiarity of N C theory. Above all, as it only deals with second-order statistics, it is a practical technique for establishing a packet-level cross-layer methodology for a wireless channel at the link layer by the knowledge of its second-order statistics at the physical layer. Finally, it conforms and can be easily coupled with N C , a sophisticated min-plus system theory for QoS evaluation and modeling of data communication networks, which is an important requirement for end-to-end QoS. We demonstrate the effectiveness of the method by using the proposed methodology to calculate the delay bounds and/or how to set the transmission rates to meet a certain delay bound, and present comparisons between analytic and simulation results. The chapter concludes with a thorough discussion on the underlying assumptions, related topics and applications with different settings. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 56 4.1. Introduction Deterministic N C is a well-established, sophisticated min-plus system theory for deterministic QoS evaluations and modeling of data communication networks [9]. However, in wireless networks in which a wireless link behaves like a stochastic server, deterministic N C might estimate loose QoS bounds. Currently, there are two different frameworks for stochastic or probabilistic N C extensions. The (a(0), p(6)) -calculus and effective bandwidth method [8] are based on the constrained moment generating function of the traffic, and the other method is based on stochastically bounded burstiness [20]. In this chapter, we propose and develop a stochastic min-plus theory as an efficient alternative method for performance evaluations and modeling, especially suited to wireless networks. The proposed methodology also serves as the foundation of a cross-layer design and modeling framework for wireless networks. In contrast with other stochastic N C methods, our proposal has the important advantage that it can easily be coupled or used with deterministic N C , an important requisite for end-to-end QoS. In addition, due to its clearly similar representation to the traditional stochastic system theory, it is much easier to use and is well-understood, even with a basic familiarity of N C theory. Simply, the traffic needs to be represented by N C ' s cumulative traffic characterization, and min-plus (or max-plus) convolution is used for input-output represen-tations. The approach that is presented in this chapter was inspired by the traditional system theory for modeling linear systems with stochastic inputs [55]. Min-plus (or its dual, max-plus) systems, as the basis of N C theory, are min-plus (or max-plus) linear. We demonstrate that a similar approach can be used to stochastically characterize the output of such systems, when the charac-teristics of the system and/or of the input are only stochastically provided. For ease of notation and to follow the system theory model, we refer to a network element (such as a link, node, or a whole network) as a system. Similarly, the incoming traffic to the system is called input, and the outgoing traffic from the system is called output, both with bytes as their units of measure. In our wireless link, the input is the traffic transmitted over the link, and the output is the traffic passed through and received at the other end of the link, observed at the link layer. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 57 The outline of the chapter is as follows. In the next section, a brief overview of the traditional system theory with a stochastic input is presented, which serves as a point of reference for and comparison with the presented stochastic min-plus theory. Second-order input-output relationships of a min-plus system with a stochastic input are presented in Section 4.3. Then, by utilizing the commutative property of the convolution operator, we modify the previous method to analyze a min-plus system with a stochastic service curve. This modification provides us with an efficient method for modeling communication networks with stochastically defined arrival or service processes, such as wireless channels. Based on this new system theory, we propose a packet-level performance evaluation and cross-layer framework for wireless networks, when the second-order statistics of the physical layer are known. The link layer uses these statistics to calculate the second-order statistics of the traffic that w i l l be received at the other end of the channel, and consequently the projected delays. From these information, suitable parameters of operation, such as the transmission rate, are decided upon. Two well-known channel models of A W G N and Rayleigh fading are examined. B y analysis and simulation via an example, we demonstrate how effectively delay as the QoS metric of interest is calculated. Finally, after some discussions, the chapter is concluded in Section 4.8. 4.2. Background A restricting and challenging characteristic of a wireless channel is that it is random and time-varying, and so is regarded as a stochastic system. Therefore, practical modeling of wireless networks naturally requires stochastic models. In Chapter 6, we present a method based on the definition of the channel's service curve using filter banks of deterministic N C elements, where the service is guaranteed with some probability [25]. Although the method is efficient and serves as a natural extension of the deterministic N C , its successful application relies on the derivation of the piece-wise service curve with a meaningful probability. Other efforts are rooted in the stochas-tic traffic characterization, assuming that some function of the moment generating function of the underlying process is constrained [8]. These models, such as the effective capacity model [16], are not only complicated and require knowledge of the asymptotic log-moment generating functions, but are also mainly suited to the analysis of a standalone link. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 58 In this chapter, we present a systematic and effective methodology for the derivation of second-order statistics of the output of a stochastic min-plus system. Since our method takes a course different from those referred to by stochastic N C in the literature (such as [8] or [20]), we differentiate it by entitling it stochastic min-plus systems theory. However, the methodology conforms with N C theory, and can actually be categorized as a stochastic N C approach and be integrated to a NC-based analysis of a network, especially with deterministic N C . In contrast to the stochastic N C models where the moment generating of the stochastic process is considered, here we deal with the second-order statistics of mean and autocorrelation. This is a practical approach, as such statistics are usually available from the underlying physical layer models. This information may be used by the link layer to set its parameters accordingly. The approach has many advantages. It is inspired by and shares many of the advantages of the traditional stochastic system theory ([55], Ch 10): it is easy to use, easily understood, system-atic and scalable. Also, since the classical system theory is familiar to engineers, our proposed stochastic min-plus system theory is accessible to practitioners even with just a basic familiarity with min-plus theory (or N C ) . In terms of its applicability, the requirements are that the cumula-tive traffic be characterized by a non-decreasing envelope and the min-plus convolution be applied. Finally, it is based on the second-order statistics which can be used for efficient QoS evaluations and resource allocation in multi-service networks [56][57]. In the following, we summarize the input-output relationship of a traditional linear system with a stochastic input, as a reference and a point of comparison. Then we present a concise overview of the min-plus system service curve to describe the notations used in this chapter. 4.2.1. Traditional Systems with Stochastic Inputs In the traditional system theory, the relationship between the input x(t) and the output y(t) of a linear system with response h(t) is characterized by the convolution operator defined by the notation y(t) = Ls[x(t)], where Ls[x(t)] = \x(t-s)h(s)ds. (4.1) Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 59 We use a superscript s with L to differentiate the system operator of the traditional systems from the corresponding min-plus notation. For a stochastic input x(t) where its mean E{x(t)} and its autocorrelation function Rxx(tx, t2) are given, similar statistics of the output are characterized based on the following two fundamental theorems. Theorem 4.1. E{L [x(t)]} = L [E{x(t)}], which also results in ny = nx® h. This is an extension of the linearity of the expected values to arbitrary linear operators ([55], pp. 309). Theorem 4.2. The autocorrelation of the output is characterized by ([55], pp. 311) Rxy(tx,t2) = Ls2[Rxx(tx,t2)}, (4.2) Ryy(tx,t2) = L\[Rxy(tut2)], where L2 means that the system operates on the variable t2 and treats tx as a parameter, and vice versa for Lx. The autocorrelation function is defined by Rxx(tx, t2) = E{x(tx)x*(t2)}, t2>tx. A process is wide-sense stationary ( W S S ) i f and only i f its mean is constant: E{x(t)} = r | , V7 and i ts a u t o c o r r e l a t i o n depends o n l y on x = t2-tx: E{x(t + x)x(t)} = R(z), V r . Then, Rxy(x) = Rxx(x)®h*(-T), ^ Ryy(x) = Rxy(x)®h(x). (4'3> 4.3. Min-Plus Systems with Stochastic Inputs The min-plus system theory and its system function were introduced in Chapter 2 and depicted in Figure 2.1. In a min-plus system, the output y(t) is characterized by the min-plus convolution of the input x(t) and the service curve (system function) h(t) by Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 60 Ln("[x(t)} = x(t)®h(t) = infQ^t(x{t-s) + h(s)) = inf0<s<t(x(s) + h(t-s)). (4.4) and y(t) > Lh^\x(t)], i f h(t) is a lower service curve, y(i) = Lh^'\x(t)], i f h(t) is an exact service curve, (4-5) y(t) < Lh("'\x(t)], i f h(t) is an upper service curve. In this section, we introduce the theory of min-plus systems with stochastic inputs by presenting two fundamental theorems characterizing the mean and autocorrelation of the output. We consider only exact and upper service curves. Due to the commutative property of the min-plus convolution, later we simply swap the role of input as the stochastic process with the service. Therefore, this section lays the foundation for the stochastic min-plus system theory presented in the following section. In order to comply with the N C theory, all functions describing the input, system and output are positive and cumulative, and therefore non-decreasing. Note that for x(t), we have the option of using either the actual traffic or its arrival curve. The former gives the actual instance of the output, while the latter gives an envelope for the output. Since for an arrival process x(t) with an arrival curve <^ (r) we have x(t + x)-x(t) < C,(x) , V(x > 0) . B y setting t = 0 , we have x(t)<C,(t) for V(7>0) and x(0) = 0. F ina l l y , us ing the isotonic i ty o f <8> [9] leads to y(t) < C,(f) ® h(t), which means the output obeys a curve of (C, <8> h)(t). For any cumulative function x(t), a rate function X(t) is defined. If x(t) is continuous and has a derivative, then x(t) = £ = QX(x)dx [28]. For a discrete time model, the input is mapped by sampling every time slot 8 [9]. In communications systems, the statistics of X(t) (which is WSS) are usually known. If X(t) is WSS, then E{X(t)} = r\, simply resulting in E{x(t)} = r\t, for both continuous and discrete time cases. Obviously x(t) itself is not WSS, unless rj = 0 . Similarly for the autocorre-lation of the continuous case, we have Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 61 Rx(tx,t2) = E\ \ X{m)dm\ X(n)dn \ = \ \R^m, n)dndm. [ Jo Jo J Jo Jo For an uncorrelated process (i.e. E{X(m + n)X(m))} — 0 , for n * 0), this reduces to Rx(,h,t2) = VAR(X)txt2, where VAR(X) = R ^ ) is the variance of X. Before presenting the fundamental theorems, we address some essential propositions and lemmas. Proposition 4.1. For a set of real numbers X, inj\X+c) = inf(X) + c, and inffl-x) = inf{x), p > 0 . P roo f : A s s u m e x* = infiX), then x * < x for V x e l . Then x* + c<x + c and p - x * < p - x , V p > 0 . S o x * + c = infiX+c) a n d p - x * = infifi-X). • Proposition 4.2. For two random variables x and y, i f x >y (i.e., for any outcome the value of x is greater than or equal to y), then E{x} > E{y} . Lemma 4.1. For a set of random variables Xs, E{infsiXs))<infsiE{Xs}) (4.6) Proof: Assume that for s° we have Xsc = infiXs), then Xso ^Xs, Vs e S. Using the results of Proposition 4.2, we have E{XS.) <E{XS), i.e. E{infs(Xs)} <infs{E{Xs}). • Theorem 4.3. In a min-plus system with a service curve hit) and random process x(r ) , E{L[xit)]}<L[E{xit)}], (4.7) Proof: A t a given time t, define a random variable Y* = / « / 0 < J < / ( x ( r - 5 ) + his)), in which hit) is a function of time. From Lemma 4.1, E ^ } < E'{x(t - s) + his)} , V(s,0<s<t). Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 62 Thus, ElY*} < inf0<s<t(E{x(t-s)} +h(s)). From the definition stated by (4.4), we have L[x(t)] = Y* and L[E{x(t)}] = inf0<s<t{E{x(t-s)} + h(s)} , thus (4.7) follows. • Theorem 4.4. In a min-plus system with an exact or upper service curve h(t) r\y < r\x ® h (4.8) Proof: By applying Theorem 4.3 in (4.5), the stated result follows. Similar to (4.2) in Theorem 4.2, the autocorrelation functions of the output in a min-plus system are derived as follows: Theorem 4.5. For a min-plus system Rxy(tx,t2)<L^)K'2)[Rxx(tx,t2)], (4.9) and Ryy(tx,t2)<LY'2)Kti)[Rxyox,t2)], <4-10> when h(t) is an exact or upper service curve. In the above equations, L2 means that the system operates on the variable t2 and treats tx as a parameter, and Lx means that the system operates on the variable tx and treats t2 as a parameter. Proof: We prove the theorem for exact service curves. For upper service curves, the proof is similar by just replacing the equalities on the first three lines with < . To prove (4.9), we start with the convolution equation and then multiply the two sides with the positive value x(tx). We apply expectation to both sides, then by using Lemma 4.1, (4.9) follows with t = t2. Similarly, we start with the convolution equation but this time we multiply the two sides with the positive value y(t2). Then we apply expectation to both sides and by using Lemma 4.1, (4.10) follows with t = ty . Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 63 y(t) = L"""[x(t)] y(t)x(tx) = infs(x(t-s) + h(s))x(tl) E{y(t)x(tx)} = E{infs(x(t-s) + h(s))x(tx)} < E{ infs(x(t - s)x(tx) + h(s)x(tx))} <infs(E{x(t-s)x(tx)}+h(s)E{x(tx)}) <infs(Rxx(tx,t-s) + y]x(tx)h(s)) and y(t) = LKl)[x(t)] y(t)y(t2) = infs(x(t-s) + h(s))y(t2) E{y{t)y(t2)} = E{infs(x(t-s) + h(s))(y(t2))} < infs(E{x(t - s)y(t2)} + h(s)E{y(t2)}) < infs(Rxy(t-s,t2) + r]y(t2)h(s)) Ryy(tx,t2)<Ln/h)K'l)[Rxy(tx,t2)] • As demonstrated in Figure 4.1, we may use two different time axes to define the two time instances tx and t2 that we need to calculate the autocorrelation. For clarity and only in this figure, we use two different notations for time, in order to differentiate between the transmission times (x ) and observation times (f). In other words, the autocorrelation can be calculated for one instance of output over actual time span during a transmission, or two different times of two different instances of output. Here we are interested in calculating the autocorrelation over a constant x , for tx, t2 due to two reasons. First, we are interested in the variability of the output for a transmission. Second, this w i l l ensure that R is WSS, provided that the underlying physical layer process (signal-to-noise ratio (SNR) here) is WSS, which is a widely accepted and valid assumption. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 64 Tx T T, T2 T Figure 4.1 Calculation of the autocorrelation. In the left figure, the two instances of time needed for the calculation of the autocorrelation are two possible instances observed at different times but for the same transmission time; on the right, they are at two different transmission times. Fundamental Theorems in Max-plus Algebra: Since max-plus algebra is the dual of min-plus algebra, both of the fundamental theorems proved here are applicable to max-plus systems as well. O f course, all infimum operators are replaced with supremum, and the direction of inequalities is revered for the service curve h(t). Theorem 4.3 becomes E{T[x(t)]} >E{T[x(t)]} , i.e., r]y >T\*h, which again gives a lower bound on the expected value of the output. Similarly, (4.9) is rewritten as Ryy(tx,t2)> L\ [Rxy(tx, t2)]. 4.4. Min-Plus Stochastic Systems In the previous section, we established a system theory for min-plus (max-plus) systems with a stochastic input. This is a logical approach, for example, for a network router with a deterministic service curve but a stochastically defined characterization for the incoming traffic. Since the min-plus convolution is commutative, i.e., (f<8> g)(t) = (g Cg) f)(t), then when dealing with stochastic systems with an input constrained by an arrival curve, we can readily apply the results and theorems of the previous sections by just swapping the role of h(t) with x(t). This Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 65 w i l l provide us with the theorems required to analyze a system with a stochastic service curve (exact or upper), and an input shaped to have a N C arrival curve. Therefore, we rewrite (4.7) as r\y<r]h®x. (4.11) The correlation equations of (4.9) are rewritten as: ^ 1 , ^ 2 ) < Z ? ( ' l W ' 2 ) [ ^ ( ^ , r 2 ) ] (4.12) and R(tv t2)<L.Yh)X{h\Rhy(h, t2)]. (4.13) Figure 4.2 shows an end-to-end path from the source to the destination, in a network consisting of a wired and a wireless part. The wired network is analyzed by N C . The input x(t) from the wired network is the traffic that enters the wireless network passing through a stochasti-cally defined wireless channel. Using the theorems presented in this section, in the following section we present a methodology that calculates the corresponding statistics of the output y(t) (received by the destination). For the uplink path, the above approach is used similarly in reversed order. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 66 g(t) Kt) z(t) x(t) AO Figure 4.2 Statistical characterizations of the received traffic using the stochastic min-plus system theory. 4.5. Wireless Channel Modeling, Performance Evaluation and Cross-layer Design In the previous section, we developed a general framework for modeling min-plus stochastic systems. Since a wireless channel is time-varying, the effective transmission rate available from the link layer perspective is variable and time-varying. Therefore, for a given transmitted traffic (input), different possible channel outputs are observed. For example, Figure 4.3 plots 50 different observed outputs of the plotted traffic passing through a Rayleigh fading channel. A stop-and-wait A R Q protocol is used to compensate for packet errors, so that any point on an instance of the output corresponds to a point on the input with the same amount of traffic. Due to fading, each instance experiences a different P E R versus time, thus it is different from the other possible instances of the output. In the following, we show how the theorems presented earlier are used to calculate the statistics of such outputs. In order to do so, the packet-level statistical service characteristic of the wireless channel, h(t), needs to be appropriately defined. A good example of such a service characterization is presented in 4.5.2. We then apply Equations (4.11) and (4.12) to find the statis-Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 67 180 Time (second) Figure 4.3 The transmitted traffic (input) and 50 different instances of the channel output due to the time-varying Rayleigh fading channel. tics of the output for a given arrival process passing through the wireless channel (or network, using the concatenation property). Therefore, by using the information from the current physical layer behaviour, the statistical characteristics of the output are determined. B y using this informa-tion, the parameters of the link layer are set accordingly. For example, such information is used to set the rate parameter of the shaper at the transmitter in Section 4.6. This is in addition to the requirements considered by the transmitter to conform to the negotiated QoS policies. The method is general and comprehensive. h(i) can be defined to be as elaborate and complex as required. For a cross-layer design, this service curve should be defined in such a way that it accurately translates the statistical properties of the physical layer, which in turn is used to adjust the operation of the link layer or to allow efficient allocation of network resources. In this section, a service curve of this nature is first addressed, based on the second-order B E R statistics at the physical layer. Then we introduce a framework that utilizes the theorems presented earlier Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 68 Link layer < Shaper >^ x(t) ^ y(t) - - < Kt) y-K-i Destination IARQ S-W I T" I I Physical layer • Wireless Channel • Physical layer Figure 4.4 System model and building blocks, for performance modeling and analysis of wireless channels. The technique is applicable for both uplink and downlink, but is particularly well-suited to the downlink, where the results from the deterministic N C modeling of the previous wired parts of the path can be most easily used for end-to-end QoS support. 4.5.1. System Model Figure 4.4 shows the overall system model. We are interested in calculating the traffic received by the destination at the link layer. The traffic is first shaped and then sent through a wireless Rayleigh fading channel. We assume that the wireless user is assigned a dedicated bandwidth; therefore, we only consider the effect of Rayleigh fading on packet errors. We assume that packets are retransmitted based on the stop-and-wait A R Q protocol in order to compensate for packet errors. Therefore, it is ensured that a packet is transmitted successfully before the transmission of the next packet is initiated. A similar variability of outputs is observed when no retransmission mechanism is used. However, in this case the delay cannot be calculated from the horizontal distance between the input and output graphs (or curves), which wi l l become clear when calculation of delay is explained later in this section. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 69 4.5.2. Service Curve of the Channel The framework established earlier is general and can be used with any stochastic server such as a wireless network, where a proper h(i) is available. Depending on the physical channel behavior, the link layer protocol, the required QoS bounds and the application, there are different ways of modeling the dynamics of the wireless channel. A reasonable way of defining h(t) is by direct consideration of the available physical channel models, and to translate it to the packet-level service at the link layer. One practical approach is to characterize the instantaneous service rate of a wireless channel at the link layer by rc(t) = (\-PER{t))\i, (4.14) when the packet error rate at any given time (PER(t) ) and the channel transmission capacity (p.) measured in packet units at A time interval (A —> 0) are known [60]. p. can be set to the Shannon capacity by using 51og(l + SNR)), when a dedicated bandwidth of size B is available to the wireless user. This is a reasonable assumption, as the errors are accounted for by PER. Whenever this method presents an overly optimistic bound for the channel capacity, other more elaborate methods for the calculation of the channel capacity may be used. In wireless networks where the users contend to use the wireless channel, p. can be set as the total available channel capacity, while PER is defined so that it includes packet errors due to contention as well. Equation (4.14) describes the instantaneous rate that is seen to be available by the l ink layer for successful transmissions. This equation holds whether a retransmission mechanism is implemented or not. In this chapter, we assume that packets are retransmitted, based on the stop-and-wait A R Q protocol, in order to compensate for packet errors. With this condition, a point on the input function (representing an amount of cumulative traffic) corresponds with a point on the output function that has the same value. Since the channel is time-varying, P E R is a random process. The second-order statistics of P E R are all we need to use (4.14). Here we consider a set of widely-used assumptions, in order to focus on describing the methodology. Alternatives to these assumptions are discussed using more sophisticated methods in Section 4.7. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 70 The service curve of the channel is the cumulative service, which is the integral (or summation for sampled or discrete representations) of (4.14): t t h(t) = \rc(x)dx = \(l-PER(x))ixdx. (4.15) 0 0 It is interesting to note that the above equation results in a stochastic rate-latency server (of the form p r T = (t- T)r), with a stochastic latency T = \PER(x)dx and rate r = p.. o Calculation of Bit Error Rate (BER): Without loss of generality, we assume use of a Q P S K modulation scheme, and no channel coding. For a ( 7 i / 4 ) - Q P S K scheme, B E R is a function of SNR, denoted by [61]: BER(t) = Q(j2SNR(i)), (4.16) Q(.) is the scaled complementary error function. In the following, the distribution of SNR for two cases of Additive White Gaussian Noise (AWGN) and Rayleigh fading channels are discussed. Case I - AWGN Channels: For an A W G N channel, the S N R is a stochastic process whose distribution depends on and is directly derived from the distribution of the additive noise, which is zero-mean Gaussian. Case II - Rayleigh Fading Channels: The instantaneous SNR per bit, y , for an uncorre-lated time-varying Rayleigh fading channel with Alamouti transmit diversity has a central chi-square distribution with two degrees of freedom. The Alamouti transmit diversity scheme is one of the methods proposed for IEEE 802.16 ( W i M A X ) to achieve 2-way diversity without adding an extra antenna, as described in the IEEE 802.16abc-01/53 specification. The probability density function (pdf) of such a process is [62] Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 71 Py(r) = gj^exp(-r2N0/E),r>0, (4.17) where £ { 7 } = E/2N0 is the average SNR per bit. For the case of a fully correlated Rayleigh fading channel with Alamout i transmit diversity, the pdf is in the form of a central chi-square distribution with four degrees of freedom, denoted by pJr) = - -exTp(-r2NQ/E) , r > 0. (4.18) (E/2N0)2 In both cases, similar assumptions for the modulation scheme and packet error allocation are considered. Thus, given SNR, the distribution of B E R is calculated by using (4.16). Calculat ion of Packet E r r o r Rate ( P E R ) : Without loss of generality, independent bit errors are assumed which leads to uniform distributions of bit errors in each packet. For complete-ness, in Section 4.7., an elaborate method of P E R calculation is discussed. Given the above assumption, P E R is defined by PER(t) = 1 - ( 1 -BER(t))", (4.19) where n is the number of bits in the packet. We assume that the packet size is set so that B E R stays constant over the packet transmission time. This condition can be achieved by breaking up the packets into smaller fragments over which B E R can be assumed constant, and then sending each fragment as a separate packet. Packet segmentation is a basic function of the link layer [63] [64]. For a more conservative calculation, the maximum B E R that occurs during the packet transmission time can be considered instead. Since we have the statistics of B E R , using (4.19) the statistics of P E R are calculated. The probability density function is pPER = -j-FpER(a), where FPER(a) = P{PER < a} . It can be Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 72 shown that FPER(a) = FB(\ - "Jl - a) + (1 -FB( \ + "Jl - a))%(n), where %(n) is 1 i f n is even, and is 0 otherwise [59][65]. In this chapter, only the mean and autocorrelation of the processes are needed, and can be calculated either directly or from the probability density function when available. For complete-ness, the distributions have been presented here briefly. Direct derivations of the mean and autocorrelation functions of P E R and then the process rc{t) are performed by cascaded calcula-tions of the statistics of B E R , PER, rc, from (4.16), (4.19), and (4.14), respectively. 4.5.3. Methodology In brief, the following steps are taken: 51) In order to use (4.14), the second-order statistics of P E R need to be derived. Without loss of generality, we use the following widely used two sub-steps (see Section 4.7 for an elaborated alternative that is more realistic), (a) From the physical layer model, the second-order statistics of bit error rate (BER) are given. The statistics of B E R are obviously dependent on the modulation scheme and any error correcting code (channel coding) used by the transceivers, and is a function of the signal to noise ratio (SNR). (b) B E R is used to find the second-order statistics of the PER. This can be done by assuming uniform distributions of bit errors, or by using other methods in the presence of error dependency and channel coding (as wi l l be explained in Section 4.7). 52) Then (4.14) is used to find the statistics of the channel service rate. Simply, we have E{rc) = (1 -E{PER})n, and R^t^, t2) = (1 -2E[PER] + RPER(tl, t2))\x2. From (4.15), the N C compatible service curve of the channel (i.e., cumulative and thus non-decreasing) is calculated. The above steps provide us with the statistics of a compatible service curve for the channel. The following two steps are performed to calculate the delay bounds: 53) Equations (4.11) and (4.12) are used to obtain the second-order statistical properties of the output. These equations are applicable when h(t) is an exact or upper service curve. h(t) is Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 13 an exact service curve, when the wireless channel is dedicated to the user, such as the one defined in Section 4.5.2. When the wireless channel is shared between the users in a random multiple access (such as by Aloha), h(t) is an upper service curve. Finally, when the wireless channel is shared between the users by some QoS-based scheduling technique (such as by a WFQ), h(t) is a lower service curve. S4) Finally, N C filtering theory is used to calculate the delay bound (or other QoS bounds) for a given input. The mean function gives us the expected value of the output, and the autocorrelation function gives us sufficient statistical information about its variation. The approach we choose to follow here is based on the standard deviation function. At any given time t, the variance of the 2 outpu t p r o c e s s is Var(y)(t) - Ryy(t, t) -r\y(t), and the s t anda rd d e v i a t i o n is Std(y)(t) = JVar(y)(t). The output w i l l vary around its mean w i t h i n a bracket o f [r\y(t) - K • Std(y), r\y(t) + K • Std(y)] with a high probability, where K is a constant. The lower and upper values of this interval are called the best and worst output curves, respectively. Since we use these concepts to find the standard deviation of the delay, we set K = 1. For example, for a normal distribution, the process is within one standard deviation around the mean with a probability of 68%, and within two standard deviations around the mean with a probability of 95%. Therefore, we can use these two bounds as the worst and best possible outputs. Calculat ion of Delay Bounds: Having the output curve is all that is required for us to utilize N C theorems to find the delay bounds. As we have assumed that in order to compensate for packet errors, a stop-and-wait A R Q protocol is implemented, any two points of the input and the output that have the same value represent the same amount of traffic. Then the delay that a packet transmitted at time t encounters is given by d(t) = inf{A>0:x(t)<y(t + A)}, (4.20) which graphically is the horizontal distance between the two graphs. The maximum delay is dmax = sup{d(t)}. However, here this delay is a stochastic process, since y(t) is stochastic. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 74 *(0 ^ E{y(f)} E{y{tVp^ ^E{d(t)y^' i ^E{y(t)}-Std{y(t)} • . i w t t + T t ime Figure 4.5 Graphical illustration of calculations of the second-order statistics of the delay. From the output curves that we have calculated, we can define the second-order statistics of the delay. Figure 4.5 illustrates these calculations. First, the mean delay is equal to E{d(i)} = inf{A > 0: x(t) < E{y(t + A)} } , therefore, the maximum value of the mean delay throughout the session, dmean, is dmean < sup{E{d(t)}} . Second, the standard deviation of the delay is equal to Std{d(t)} = / « / { A > 0 : E{y(t)} <(E{y)-Std{y})(t + A)} . Therefore, the maximum value of the standard deviation of the delay throughout the session, dStd, is dStd< sup{Std{d(t)}}. From these values, we can readily define the statistical worst-case values for the delay, Dmax . For example, for a Gaussian distribution, Pr(Dmax < dmean + dStd) > 1 - 8 j , where 8, = 0.32, and Pr(DmJ2 < dmean +2dStd)> I - e2, where 8 2 = 0.05. The numerical example presented in the next section elaborates upon this procedure. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 75 4.6. Numerical Results In the previous section, we detailed the methodology through four steps. In this section, we use a numerical example for a Rayleigh fading channel to compare the analytical results with simulation results, using MATLAB® 2 . Following the four steps of the methodology, Equations (4.11) and (4.12) are used to first obtain the second-order statistical properties of the output. Having the statistics of the output, the delay bounds are calculated. The nature and values of the parameters, as well as the assumptions used in the numerical example are as follows. The traffic that enters the channel is shaped by a leaky-bucket controller to conform with an arrival curve of the affine function at + b, where a is the rate and b is the bucket size (co-called burst tolerance). Figure 4.6 illustrates this operation with an example. The parameters of the shaper have to be defined according to the negotiated QoS policies. The actual rate of the traffic source can be less, equal or larger than that of the shaper. For better presentation of the results and since the arrival curve is a good QoS benchmark, we have set the value so that the shaped traffic is close to the shaping envelope. A n instance of the traffic from the source, shaped traffic, and their cumulative representations are shown in Figure 4.6, subplots a, b and c, respectively. The channel is assumed to be uncorrelated Rayleigh fading with Alamouti transmit diversity with average S N R E{y}, and rate u , as discussed in Section 4.5. This is a diversity method used in W i M A X . A (n/4) - Q P S K modulation and no channel coding are assumed. The values of the parameters used in the example are summarized in Table 4.1. Table 4.1. Parameters used in the example and their values. Parameter notation Value Mean inter-arrival times MlntArr 0.7 (ms) Mean packet size MPkSz 3 (KB) Shaper rate a MPkSz/MIntArr (MB/s) Shaper burst tolerance b 5*MPkSz Average SNR EM 10 (dB) Channel rate H [0.5 \.2]*a 2 M A T L A B is a registered trademark of The MathWorks, Inc. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 76 (a) (b) 20 40 60 80 T i m e (second) 100 40 60 80 100 T i m e (second) (c) 400 350 CO 300 u> o LL 250 O se ra i_ 200 I-> ra 150 E £ 100 o 50 0 — — Cummulative traffic to the shaper - - - - Cummulative traffic out of the shaper p> 1 J i -icy \ t • : j g * m * . . 20 40 60 Time (second) 80 100 Figure 4.6 An example of (a) the traffic delivered to the link layer, (b) shaped traffic ready to be transmitted through the channel, and (c) cumulative representations of traffic in a and b. The simulation methodology is as follows. A source generates a traffic stream with exponential inter-arrival times and packet sizes. This traffic is then shaped based on a leaky-bucket shaper (ya b(t) = at + b , t>0 and 0 otherwise); the values of its parameters are given in Table 4.1. A packet is segmented i f its size is larger than b. The traffic source is set so that the Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 11 shaped traffic, x(t), is as close as possible to the arrival curve. This shaped traffic flow enters the channel. A random generator is used to generate a sequence of random numbers based on the distribution of the SNR. Each random number is associated with a packet that is transmitted at that time. This set of numbers is used in turn to calculate the B E R and then the channel rate. In order to have a similar setting as the numerical method, it is assumed that the channel provides a service curve of the form (4.14). Based on this service curve, the channel acts as a stochastic server for the input traffic flow. Finally, a set of 50 instances of the output flow is used to calculate its second-order statistics. For the figures that present the results with a 95% confidence interval [66], the calculations were iterated 30 times. Figure 4.7 shows the three-dimensional plots of the autocorrelation of the service and the output. Since the underlying process is a WSS process, these are accordingly WSS. The x axis designates the transmission time and they axis represents 50 different instances of observations, including its mirror towards the negative side, with a collective span of [-49, 50]. Figure 4.8-a shows the traffic (arrival) passing through the channel, and a set of 50 instances of possible service curves that occurred due to the time-varying fading channel. Figure 4.8-b shows the mean output calculated from the analytical approach as well as the mean of the actual outputs from the simulation. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 78 Instances Figure 4.7 3D plots of the autocorrelation of the service (a) and the output (b). The x axis designates the transmission time and the y axis represents 50 different instances of observations (with its mirror towards -50). Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 79 Figure 4.8 (a) Traffic and 50 instances of channel service curves simulation results for mean outputs. (b) Comparison of analytical and Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 80 Knowing the input and output, the delay bound can be easily calculated. First, we use the graph of the mean output to calculate mean delay. Mean delay is the maximum horizontal distance between the input and the mean output. Similarly, the standard deviation is used to plot the best and worst output curves, as explained in detail in Section 4.5.3. Following the same procedure, the worst delay is calculated, which is the maximum horizontal distance between the input and the worst output. Figure 4.9 shows the mean, worst and best outputs and illustrates the above procedure for graphically calculating the mean and worst delays. Obviously, the shaper rate (value of parameter a) relative to \i is an important factor in the value of the observed delay. Figure 4.10 plots mean and worst delays for different values of the ratio of the channel and shaper rates ( u / a ) , within a wide range of [0.5, 1.2]. The figure compares the analytic and simulation values with a 95% confidence interval, considering 30 iterations per each value of the above ratio, with 50 instances of channel service curves. Figures 4.11 and 4.12 demonstrate the plots of delay when the other two effective parame-ters, b and E {y}, are changing. Figure 4.11 shows the delay versus the b parameter of the shaper, Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 81 i 1 1 1 1 1 1 r u/a ratio Figure 4.10 Mean and worst delays for different values of \Ja with a 95% confidence interval (30 iterations of 50 instances each). and Figure 4.12 plots the delay for a wide range of values of average SNR (E{y} in dB). Therefore, the link layer shapes the traffic with a rate that not only conforms to the negoti-ated QoS policy, but also considers the wireless channel condition. Hence, the value of the parameter a is reconsidered and adjusted to implement the above cross-layer design. Depending on how often the second-order statistics of the physical layer are acquired, the value of a can be adjusted accordingly. This procedure is the so-called impedance matching for the channel condition [67], in addition to traffic and congestion conditions, and QoS policies. Since in our scenario the channel is under a wide-sense stationary condition, only E{y} needs to be passed up from the physical layer. As discussed earlier, this is a practical assumption for a fading channel, which obeys a chi-square distribution. The figures show a close match of the analytical and simulation results. Our analysis also finds similar results in the case of a fully correlated time-varying Rayleigh fading channel with Alamouti transmit diversity, which was discussed in Section 4.5. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 82 S 2 0 f ( 3 ) :\. •^m >1 ^ ( 1 ) ^ ( 2 ) | J \ — — Mean delay from analysis ( 1 ) - e - Mean delay from simulation ( 2 ) i Worst delay from analysis ( 3 ) 1 1 >$<> Worst delay from simulation ( 4 ) ° 0 5 1 0 1 5 2 0 2 5 3 0 3 5 4 0 b (KB) Figure 4.11 (a) Delay versus b (shapers burst tolerance), when E{y) and \Ja are 10 dB and 0.8, respectively, with a 95% confidence interval (30 iterations of 50 instances each). Figure 4.12 Delay versus average SNR (£{y}) in dB when \Ja is 0.8, with a 95% confidence interva (30 iterations of 50 instances each). Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 83 4.7. Discussion In this section, we first discuss practical aspects and advantages and limitations of the proposed method. We then elaborate upon applying the proposed method to applications with different settings. Thus far, we have assumed a Q P S K modulation scheme, no channel coding, and uniform distribution of errors. In this section, we discuss how to incorporate channel coding and/or other modulation schemes into the model. In addition, an elaborate method for the deriva-tion of PER, considering bit error dependency, is given. Some topics of interest that further expand the scope of the proposed methodology are also discussed. A short note on how to consider mobility is presented; analysis of systems with both stochastic traffic and service curve is addressed; and the statistical service guarantee in N C in relation to the proposed method is discussed. Finally, slope domain representations of the fundamental theorems are derived. Practical Considerations in Using the Method in Wireless Data Networking: In order to determine the scope of application of the discussed method, we first address when the underly-ing Theorems 4 .3 and 4 .5 are valid. Three aspects, linearity, shift-invariance and stationary conditions need to be addressed. Linearity: Theorems 4.3 and 4.5 can be used only when the min-plus system is min-plus linear. As explained earlier, in order for a D E D S to be min-plus linear, there should not be a number of servers available for the input to choose from (so-called concurrency) [7]. In practice, this condition holds for most queuing nodes or data networks, when the routing path is pre-set by the transmission connection. Shift-invariance: In order to use the convolution operator in place of the system operator L(.) in Theorems 4 .3 and 4 . 5 , the min-plus system should be shift-invariant. This condition applies when a shift in input creates a similar shift in output. In practice, QoS-aware networks are usually designed with the aim that this property holds. However, this requirement does not exclude stochastic systems. Usually, in stochastic settings the wide-sense stationary (WSS) assumption replaces the shift-invariant assumption. Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 84 Stationary assumption: Theorems 4.3 and 4.5 are val id regardless of the stationary condition. However, in practice, in order to define a meaningful stochastic service curve for the channel, we need to consider a WSS condition. This is a valid and widely used assumption, especially for Rayleigh fading channels ([68], pp. 65). It goes without saying that the applicability of the method relies on the requirement that the wireless network can be reliably modeled by a stochastic service rate whose second-order statistics can be calculated. Detailed P E R Calculations: So far in this chapter we have assumed that the bit errors in a packet occur independently and that no channel coding is implemented. We did so to be able to clearly explain the methodology without becoming sidetracked by irrelevant details. However, channel coding plays a significant role in wireless communication [69]. For example, deployment of a convolutional code can lower B E R by two orders of magnitude ([70], pp. 260). In this section, however, we revise our assumptions and consider error dependency in the presence of convolutional channel coding, to demonstrate that the same methodology applies. As a replacement for (4.19), Equation (4.22), which was introduced in [71], is used. Although these equations look similar, (4.22) not only considers error dependency but also takes into account convolutional coding as an error correction code. The procedure for P E R calculations remains almost unchanged. The statistics of SNR are first calculated. Then instead of finding B E R , a new function called E E R (error event rate) is used, from which P E R is calculated. We take the following steps: 1) EER(SNR) is defined by EER(SNR) *Ad exp(R • SNR • dfrpp), where Ad is the number of paths of length djr 'ree in the code trellis and R is the code rate. 2) From EER(SNR) the value of another function XS(SNR) is defined by EER(z) (4.21) 1 - (u + l ) + 1 EER(z) nc(z/2-j2z7c + rc)j Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 85 where rc = kc/nc is the code rate and u is the constraint length of the (nc, kc, o) convolutional code. It is shown in [71] that XS(SNR) is the mean of a geometric distribution characterizing errorless period lengths. 3) Finally, the P E R is calculated as follows: PER(t) = 1 - ( 1 -Xs(SNR(t)))". (4.22) It is interesting to note that the above formula appears similar to (4.19), with B E R replaced with a new function, XS(SNR). Under similar considerations as applied to our previous numerical and simulation settings, we derive the mean and worst delays using (4.22). Based on [72] for a U M T S system, a convolu-tional code with rate 1/2 and u = 9 is assumed. For this code dj-ree = 12. We assume that the value of nr is equal to the mean packet length and that A J = 1. ^ ufree Figure 4.13 shows the analytical and simulation results for the delay. The observed delays are worse due to the bit error dependency (as compared with those in Figure 4.10), but the methodology is still applicable. Effect of the Modulation Scheme: Until now in this chapter, we have assumed a Q P S K modulation scheme. For a different modulation scheme, only the equation describing B E R as a function of SNR needs to be changed. For example, for the D B P S K modulation scheme, (4.16) is replaced with: BER(t) = 0.5 exp(-SNR(t)). Systems with Both Stochastic Input and Service: When the service and input are both stochastically defined, the theorems are modified as follows, and can be used accordingly. In the following, only the results for systems with exact or upper service curves are presented. A ) The mean of the output is r]y<r]x®r]h. Proof: Similar to the proof of Theorem 4.3, we have (4.23) Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 86 0.9 1 1.1 |i7a ratio Figure 4.13 Delay versus different values of shaping rate with the consideration of convolutional channel codes and bit error dependency. E{L[x(t)]} = E{x(t)®h(t)} = E{infQ<s<l(x(t-s) + h(s))} <info<s<t(E{x(t-S)}+E{h(s)}) <E{x(t)}®E{h(t)} n B) Similarly, the autocorrelation function can be calculated from the following: Ryy(txj2)<LR^'h)[Rxy(tx,t2)]. (4.24) Note that this equation is slightly different from (4.12), as we need to calculate Rhy as well as i? v „ . Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks Proof: y(t) = Lh(l)[x(t)] y(t)x(tx) = infs(x(t-s) + h(s))x(tx) E{y{t)x{tx)} = E{infs(x(t-s) + h(s))x(tl)} < infs{E{x{t - s)x{tx) } + E{ h(s)x(tx)}) <infs(Rxx(tx,t-S) + Rxh(tx,s)) Rxyih,t)<Rxx(tx,t)®Rxh{tx,t) Rxy(h,h)^^(tl't2)[Rxx(tx,t2)] and y(t) = LKt)[x(t)] y{t)h{tx) = infs(x(t-s) + h(s))h(tx) E{y{t)h(tx)} = E{infs(x(t-s) + h(s))h(tx)} <infs{E{x{t-s)h(tx)}+E{h{s)h(tx)}) <infs(Rhx(tx,t-s) + Rhh(tx,s)) Rhy{tx,t)<Rhx{tx,t)®Rhh{tx,t) V'i''2)^(''''2W('i>>2)] Finally, Ryy{tx, t2) is determined as follows: y{t) = LK'\x(t)] y(t)y(t2) = infs(x(t-s) + h(s))y(t2) E{y(t)y(t2)} = E{wfs(x(t-s) + h(s))(y(t2))} < infs(E{x(t-s)y(t2)} + E{h(s)y(t2)}) <infs(Rxy(t-s, t2)+Rhy(s, t2)) Ryy(t,t2)<Rxy(t,t2)®Rhy(t,t2) R(tx,t2)<LRxhAh'h)[R(tx,t2)] Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 88 Mobility: The proposed method is practical, regardless of whether the transmitter and/or receiver are fixed or mobile. Since all of the equations in this chapter are time-dependent, the location of the node is already incorporated. In this approach, both large-scale path loss and shadowing, as well as small-scale fading are considered. Path loss is mainly dependent on the receiver-transmitter distance from which the average SNR (expectation of SNR) is calculated. To account for mobility, this value in Equation (4.17) (or (4.18)) would be time varying and needs to be reconsidered at any given time. Statistical Guarantees: Our method fits in and can be used with statistical N C [17][24], in which the QoS evaluations are based on a statistical exact (or upper) service curve hs(t), satisfying Pr{y(t)= x(t) ® h\t)} > 1 - e , (4.25) since such a service curve is derived for the channel. A l l QoS bound theorems for delay, backlog and output bound of N C are valid as well under the above definition, and can be used to calculate QoS metrics of interest [17]. End-to-End QoS Evaluations: The method presented in this chapter can be used in end-to-end QoS evaluations. The concatenation property applies to a combination of stochastic and deterministic N C elements; i.e., assuming that the service curve of the rest of the network is hx(i) and the service characterization of the channel is h(t), then the end-to-end service curve is defined by he(t) = hx(t) ® h(t). Therefore, Equations (4.11) to (4.11) are applied to this new service curve. Slope Domain Representations - Load Spectrum: In system theory, the Fourier spectrum is used for spectral representations of random signals. The power spectrum of a random process is the Fourier transform of its autocorrelation function: PS(a>) = ^R(x)e~j<*xdx ([55], pp. 416). Then, the power spectrum function of the output is Chapter 4. A Stochastic Min-plus System Theory Approach to Performance Modeling of Wireless Networks 89 P S M = PSXMH((o) = PS((O)\H(CO)2 . yy• xy In Chapter 3, we presented slope domain modeling of networks, which serves in regard to min-plus systems as the Fourier domain to traditional system theory. In this section, we use the slope transform defined by (3.1) to find the slope domain representations of (4.23) and (4.24). Similar to power spectrum, we introduce the slope transform of the autocorrelation functions as load spectrum, using the notation Syy(a) = S{Ryy(x)}(a). A n immediate advantage of using slope domain analysis is that all the convolution operators are translated to algebraic additions. Also, the load spectrum demonstrates how traffic load is distributed over different rates (slopes). The slope transform of (4.12) leads to Sh ( a ) £ S A A ( a ) + T i ^ ( a / T i ^ (4.26) ^ ( a ) < ^ ( a ) + r 1 ^ r ( a / r i , ) which finally results in: Syy(a) < Shh(a) + r ^ c c / r ^ ) + ^ ( a / r i p . (4.27) The autocorrelation of the output is then calculated by the inverse slope transform of 4.8. Summary In this chapter, we have introduced a stochastic min-plus methodology that not only serves as a general extension to N C for efficient modeling and performance evaluations of wireless networks, but also as a method for cross-layer design at the transmitter. This is an effective method when the second-order statistics of the service can be calculated. We have presented a simple-to-use framework from which the second-order statistics of the traffic passing through a channel are calculated, using the second-order statistics of the physical layer. This information is used to calculate delay bounds in order to verify whether the desired delay as the QoS metric of interest is met. 9 0 Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation for the Trans-mission of Multimedia over Wireless Fading Channels In the previous chapter, the focus of our analysis was on performance evaluations. In this chapter, we concentrate on configuring system parameters so that the desired QoS metrics are achieved. We derive the parameters of an optimal leaky-bucket shaper and/or the required channel bandwidth for the transmission of constrained traffic over a wireless fading channel. The analysis is based on the stochastic min-plus system theory for the derivation of second-order statistics, discussed in Chapter 4, as a wireless fading channel is a stochastic rate-latency server. The shaper is optimal in the sense that it minimizes the end-to-end delay and buffer requirements under the constraints dictated by the lower layer characteristics, in particular the wireless fading channel. In the case of the resource allocation application, the method presents the minimum required channel rate that results in favourable service quality. Our model is used to plot the analytic delay and buffer sizes in comparison to simulation results for various values of shaper parameters and the available channel rates, from which the optimal or sub-optimal solution is calculated. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 91 5.1. Introduction The traffic entering a network may be shaped for a number of reasons. It is shaped at the source or a network edge to conform to a predefined service level agreement to make it eligible for receiving the negotiated QoS. Traffic shaping is also used to ensure a fair and stable utilization of the network, even for the best-effort service. Finally, it is implemented as a rate-control mechanism to smooth a bursty traffic stream. In a wireless network, the bottleneck is usually the time-varying wireless channel. Therefore, the available effective rate should be taken into consideration. In this chapter, we show how to derive the parameters of a leaky-bucket shaper and/or the bandwidth assignment, in order to minimize end-to-end delay and the buffer requirements. The minimization is done under constraints dictated by the physical layer characteristics such as S N R statistics and channel rate, or by the traffic requirements, for example, a permitted traffic burstiness. The buffer requirement is dependent on the available buffer sizes of the involved layers for a reliable transmission especially when an A R Q mechanism for loss-free transmissions is deployed. The analytical model is based on the stochastic min-plus system theory that was thoroughly discussed in Chapter 4. The theory explains the input/output relationship of a stochas-tic min-plus system. It is used to derive the second-order statistics of the output, when input and/ or service are stochastically characterized. As explained before, a wireless fading channel is modeled by a stochastic rate-latency server whose second-order statistics are easily calculated from the knowledge of the physical layer characteristics. Therefore, we use this method to find the statistics of the traffic (the output) that passes through a wireless channel; i.e., the mean and autocorrelation of the traffic at the output of the channel. Then by using N C theorems [9], the optimal values for the parameters of the shaper and/or the requisite channel assignment are calculated. The outline of the chapter is as follows. In the next section, an overview on the theory of optimal traffic shaping is presented. The system model, assumptions and descriptions of the underlying concepts and building blocks are addressed in Section 5.3 . The theory of shaping for transmission over a wireless channel and the methodology for calculating the parameters of the Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 92 optimal shaper are presented in Section 5.4. The numerical and simulation results are discussed in Section 5.5. We present the results when either of the channel rate or the shaper rate are select-able. For each case, two scenarios of bit error dependency and independency in packets are studied. Finally, a summary of the chapter is presented in Section 5.6. 5.2. Optimal Leaky-Bucket Shaper We use the widely accepted min-plus system theory or N C [9] representations for the traffic and service. A system is a representation of a network or a network element (link, node, or sub-network) that provides a service defined by h(t). The incoming traffic (input) is represented by x(t), and y(t) represents the outgoing traffic (output received by the end element), both in units of bytes. The traffic and service are characterized by the arrival and service curves, respec-tively. The traffic (input or output), arrival curve and service curve are represented by non-decreasing functions. For a cumulative traffic x(t) and an arrival curve C,(t), it is guaranteed that x(t + x)-x(t) < ^ (x) , \/t, x. Similarly, a system with lower service curve h(t) guarantees that the cumulative output traffic y(i) obeys y(t + x)-y(i) < h(x), V / , x . The output of a system with input x(t) and exact service curve h(t) is expressed by y(t) = L(x(t)), where Lm(x(t)) = x(t) ® h(t). The min-plus convolution operator is defined by x(t)®h(t) = inf0<s<t(x(t-s) + h(s)). Leaky-Bucket Shaper: A leaky-bucket server is a well-known and widely used shaper, with two parameters: a the average rate and b the burst tolerance. Any traffic passing through such a shaper wi l l have an arrival curve of ya b(t). The Traffic Specification (TSPEC) is an extension of the leaky-bucket shaper, with an arrival curve of {pt + M, rt + b), where M> b and p > r. Without loss of generality, here we limit our analysis to arrival curves of at + b. Rate-Latency Server: The rate-latency server T = | i ( r - T)+ is a widely used model Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation . 93 describing a service that guarantees a service rate \x and service latency T. For example, the W F Q (weighted fair queuing) scheduler is a rate-latency server. As explained in this chapter, a wireless fading channel can be modeled by a stochastic rate-latency server. C a l c u l a t i o n o f D e l a y a n d B u f f e r R e q u i r e m e n t : There are two analytical methods for delay and buffer calculations, denoted here by A and B . In method A , the input and output functions are used. The delay that the data transmitted at time t encounters is given by d(i) = inf{A: A>0 and x(t)<y(t + A ) } , (5.1) and the virtual backlog at time t inside the system is B(t) = x(t)-y(t). (5.2) Then the maximum delay and required buffer are, respectively dmax = Kx,y) = SUp,^0(d(t)), (5.3) Bmax = V<<X^) = ™Pt>o(B(t))- (5-4) The maximum delay dm is the maximum horizontal distance, and the maximum required buffer bm is the maximum vertical distance, between the transmitted (input) and the received (output) traffic. Method B gives a looser bound, but is more convenient. It is based on finding the maximum delay and backlog from the arrival and service curves. When the arrival and service curves tightly represent the input and service, method B gives a good estimate for the delay and buffer size [9]. It is proven in [9] that the delay bound for a system with a service curve of h(t) and input traffic with an arrival curve of £,(t) is k(^,h) = sups>0(inf{T:T> 0 and ^(s) <h(s + T)}), (5.5) which graphically is the maximum horizontal distance between the graphs of h{t) and £,(t). The Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 94 Figure 5.1 Delay and buffer calculations. Method A: using the input and output traffic (a). Method B: using the arrival and service curves (b). maximum buffer size is v(\,h) = sup{%(t)-h(t)}, (5.6) which graphically is the maximum vertical distance between the graphs of h(t) and £,(/) . In this chapter we call this method B . Figures 5.1-a and 5.1-b graphically depict these concepts. Opt imal Traffic Shaping: A n optimal leaky-bucket shaper is the one that minimizes the maximum delay and buffer requirement: minimize(dmax,Bmax). (5.7) This minimization is subject to the constraint dictated by the QoS policy (affecting the Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation ... 95 b Figure 5.2 The effect of variations of arrival and service parameters on the maximum delay and buffer requirements for a rate-latency server and leaky-bucket-shaped traffic. selection region for the shaper parameters) and the physical layer characteristics such as S N R (affecting the service curve). In this section, we briefly derive the optimal parameters using method B for a traffic shaped by a leaky-bucket shaper passing through a rate-latency server. This procedure gives us insight into the mechanism involved and the effect of the parameters in the selection of the optimal shaper, which is not obvious from method A . However, method A is preferred and is used in the numerical results of Section 5.5. This concept is explained in Section 5.4. The analysis depends on the relative values of a and \i. When a < (j., then it can easily be shown that the maximum delay and required buffer are dmax - T+ b/\i and Bmax = b + a • T, respectively, as shown in Figure 5.1-b. Therefore, when u. is given, in order to satisfy a desired maximum delay and required buffer, the shapers parameters need to be calculated as follows: b = (dmax- T)n and a = (Bmax-b)/T. (5.8) If the QoS policy indicates a shaping of apt + bp, then we should choose min{a, ap) and min(b, bp). Figure 5.2 shows the effect of the variation of a, b, T and | _ i . Note that the value of the Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 96 delay depends mainly on the value of T, and also on b and u . However, it is independent of a. Similarly, the value of the required buffer size depends mainly on the value of b, and also on T and a. However, it is independent of p.. When a> p , the arrival and service curves diverge. Therefore, the maximum delay depends on the length of the transmission session and increases accordingly. Unless the session is short, this may increase without bound, when t -> co. 5.3. System Model and Building Blocks The system model used in this chapter is similar to that used in Chapter 4, as shown in Figure 4.4, which was explained in Section 4.5.1. For completeness, we very briefly explain the model and assumptions in this section. The packet-level transmission over a wireless link is modeled as a system with shaped input x{t), a stochastic server with a service curve h{t), and output y{t), which is received at the link layer at the other end of the channel. The traffic is shaped with a leaky-bucket shaper and sent to a buffer for transmission over a Rayleigh fading channel with Alamouti diversity. We assume the transmitter w i l l be acknowledged by the next available slot, whether a retransmission is required or not. The function that is used here to practically characterize the instantaneous service rate of a wireless channel is rc(t) = (1 -PER(t))\x, given by (4.14). Thus, the service curve of the t t channel is h(t) = jrc(t)dt = |(1 -PER{t))\ idt . These functions were explained in Section o o 4.5.2. The instantaneous SNR per bit, y, is given by (4.17). In order to derive the PER, two different scenarios are considered. In order to clearly explain the methodology without becoming sidetracked by irrelevant details, we first consider independent bit errors, and then the practical dependent distribution of bit error in each packet is considered. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 97 Independent Bit Error Scenario: B y assuming a (n/4) -QPSK modulation, independent d i s t r i b u t i o n o f b i t errors i n each n-bit packet and no channe l c o d i n g , we have BER(t) = Q(j2SNR(t)) (from (4.16)) and PER(t) = 1 - ( 1 -BER(t))" (from (4.19)). Dependent Bit Error Scenario: To consider a practical scenario, we also assume dependent bit errors and a convolutional channel coding. This scenario was explained in pp. 84-85 of Chapter 4. From (4.22), the P E R is calculated from PER(t) = 1 - (1 - Xs(SNR(t))f. Stochastic Output Characterization: In Chapter 4, we proved two fundamental theorems that define the second-order statistics of the output of a min-plus stochastic system, when the second-order statistics of the service curve are given. The second-order statistics of h(t) are its mean E(h{t)) = r\h and autocorrelation Rnh(t\,t2) = E{h(tx)h(t2)}, h - h • The 2 variance is then Var(h)(t) = Rhh(t, t) - r\h(t). In Chapter 4, based on Theorems 4.3 and 4.5, the input/output relationship of a stochastic system was described by (4.11), (4.12) and (4.13). Equation (4.11) states that in a min-plus system with service curve h(t), r\y<r\h®x. (5.9) Equations (4.12) and (4.13) state that for a min-plus system with service curve h(t), (5.10) Ryy{tx,t2)<LYh)x{t\Rhy{h,t2)}, Equations (5.9) and (5.10) are the main analytical tools that we use in this chapter. They are used to find the expected and worst delays at the receiver, in order to find the optimal values for the shaper or channel allocation. The methodology is explained in the next section. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 98 5.4. Methodology Two methodologies based on the aforementioned methods A and B are presented in this section. The methods are used to find the parameters of the optimal leaky-bucket shaper that minimizes the overall delay and required buffer for transmitting data over a wireless fading channel. The main challenge is the stochastic behaviour of the channel. The optimization constraints are the characteristics of the wireless channel (incorporated in the service curve), as well as factors such as allowing a certain desirable burst tolerance. Method A : In order to use method A , we first use Equations (5.9) and (5.10) to find the second-order statistics (mean and autocorrelation) of the output; i.e., its mean r\y(t) and variance Var(y)(t). Then we calculate the mean and worst-case output curves. The worst-case output is defined using r|^(r) - JVar(y)(t). A s an example for a normal distribution, it is within one standard deviation around the mean with a probability of 68%, and within two standard deviations around the mean with a probability of 95%. Since the purpose is to calculate the mean and standard deviation of the delay and buffer size, the output within one standard deviation of its mean is considered; this concept was explained in the delay calculation subsection of Section 4.5.1. We can then use (5.3) and (5.4) to find the values of the expected and worst delays and buffer requirements for different values of the parameters. These results are then used to select the parameters of the optimal (or sub-optimal) shaper. Figure 5.3a graphically depicts this method. The statistical calculations of the delay were explained in Chapter 4. Method B: A s (4.15) suggests, a wireless channel is a stochastic rate-latency server whose T is a random process, and whose second-order statistics can be calculated. Having the mean latency Tm and worst-case latency Tw, the mean and worst-case delays are calculated (as shown in Figure 5.3b). We can use (4.15) to find the optimal values for the parameters a and b, using the value of either the mean or worst latency, depending on the required level of service quality. Method A is the preferred methodology for a number of reasons. First, the bounds derived Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 99 Figure 5.3 Calculation of mean and worst delays and buffer sizes, (a) Method A: using the input and output traffic flows, (b) Method B: using the arrival and service curves. by method B are loose and overestimated, especially when the actual traffic and service are not close to their curves. In addition, method B is only applicable for a leaky-bucket and rate-latency server, and only when a < u . In contrast, method A is general and may be used for any type of shaper and service curve. In the next section, we present numerical and simulation results by plotting and comparing the delay and buffer requirements, in order to derive the optimal values for the parameters of the leaky-bucket shaper. 5.5. Numerical Results In this section, we present the numerical results for a practical scenario in which a server is transmitting continuous-media data to a wireless user via a base station in a wireless data network. The base station can be either the originating source or a last-mile connecting point. For an end-Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 100 to-end scenario with concatenations of n rate-latency nodes, we wi l l have an overall rate-latency service curve of \ia{t- Ta) where | i 0 = min(\ix, u^) and Ta = . n We assume exponentially distributed inter-arrival times and packet sizes. The traffic must be shaped, and we would like to minimize the delay and buffer requirements considering the imposed constraints. The values of the parameters used in the example are summarized in Table 5.1. We plot the delays and required buffer sizes from analysis (using method A ) and simulations. The numerical and simulation methods used in this chapter are similar to those used in Chapter 4. Based on the explained methodology, (5.9) and (5.10) are used to find the mean and variance of the output, from which the mean and worst output curves are derived. Then we use the N C theorems to find the mean and worst delays and backlogs as explained in Section 5.2 (Figure 5.3-a). The simulation setting is similar to that used in Chapter 4. These results are derived with the assumption that the channel still follows the service curve of (4.15); therefore, the output can be obtained using the convolution operator. The values are chosen similar to their counterparts in the numerical results. In the following, we present two sets of results for two different applications of optimal traffic shaping and resource allocation. Also, for each application, both cases of dependent and independent bit errors in the packets are studied. A p p l i c a t i o n 1: O p t i m a l S h a p i n g , a is to be selected: In this application, the optimal values for the a and b parameters of a leaky-bucket shaper need to be selected, when the available channel rate is given and fixed. Table 5.1. Common parameters and their values used in the numerical examples. Parameter Notation : Value Mean inter-arnval umes MlntArr 0.7 (ms) Mean packet size MPkSz 3 (KB) Shaper burst tolerance b [2 12]*MPkSz Average SNR E{y) 10 (dB) Chapter 5. Optima! Leaky-Bucket Shaper and Resource Allocation 101 We plot the mean and worst delay and buffer sizes for a wide range of values: for b e [2, 3, 5, 7, 9, 12] x MPkSz and a e [0.5, 0.7, 0.8,0.9, 1, 1.1, 1.2] x p . In this case, we have assumed that the channel rate, p , is given and is equal to the ratio of the mean packet size and mean interarrival times (MPkSz/MIntArr). Application 2: Resource Allocation, u is to be selected: In this application, the value of a (and/or b) is given, and we would like to find the best values for p. and b. We plot the mean and worst delay and buffer sizes for a wide range of values: for b e [2, 3, 5, 7, 9, 12] x MPkSz and p e [0.5, 0.7, 0.8, 0.9, 1, 1.1, 1.2] x a. In this case, we have assumed that the shaper rate, a, is set to MPkSz/MIntArr. For both of the above applications, we consider a wide range of values for a and p., even those whose ratio is smaller than one, i.e., the delay and buffer sizes are session-length dependent. This condition is normally avoided, except when the transmission session is short. Also, the results for both scenarios of dependent and independent bit errors are presented. In the dependent bit error case, the values of the parameters are based on a U M T S system [72] [73] [74], so a convolutional code with rate 1/2 and u = 9 is assumed, where dfree = 12 . We assume that the value of nc is equal to the mean packet length and that Ad = 1. Figures 5.4 to 5.11 plot the results for the case of the optimal traffic shaping application, independent bit error scenario. Figure 5.4 shows the three dimensional plots of the results of the calculated mean delays from analysis and simulation for the independent bit error scenario. This 3-D figure is presented to show the shape of the results in a quantitative visual way. However, since the values of the delay cannot be easily read from this figure, the contours of it are plotted in Figure 5.5. The values on the contours show the delay for the corresponding values of b and a. We observe a close match between the two sets of results. Figure 5.6 shows the three-dimensional plots of the results of the calculated worst delays from analysis and simulation, and Figure 5.7 plots the contours of the plots in Figure 5.6. The values on the contours show the delay for the corresponding values of b and a. Similarly, Figures Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 102 5.8 to 5.15 show the three-dimensional plots and contours of the mean and worst buffer sizes resulting from the analytical and simulation results for the independent bit error scenario. Figures 5.5, 5.7, 5.9 and 5.11 collectively present a set of results that need to be used to define the values of a and b, so that the desired mean and/or worst-case values for delay and buffer are achieved. We either select one of these shaper parameters and calculate the other, or calculate both in a mutual and adaptive way. A n optimal value is the smallest one that satisfies the required service quality (delay and buffer size) for all of these four figures. For a given wireless system, a table of values based on these figures can be written and used at the design or implementation phase. For example, i f we are constrained by a worst-case delay of 15s and buffer size of 60MB, and the available channel rate is p. = 4.2 MB/s , then by selecting a « 3.7 MB/s and b = 25 K B from the graphs, these QoS requirements are met. Figures 5.12 to 5.19 plot the results for the case of the resource allocation application, independent bit error scenario. The figures are presented in a similar order to the optimal shaping application discussed above, i.e., the 3-D plots and their contours present mean and worst delay and buffer sizes. The 3-D figures are presented to help visualize the resulting delay and buffer sizes, whereas their contours are used to calculate these QoS metrics. Similarly, Figures 5.13, 5.15, 5.17 and 5.19 collectively act as a tool with which to define proper configurations for efficient allocation of the channel resources. Based on these figures, a table of values can be obtained that are used at the design or implementation phase for a given wireless system. These graphs correspond to a given value of a; for other values of a, other sets of graphs need to be plotted in a similar manner. In the case of the resource allocation application, from the graphs (Figures 5.13, 5.15, 5.17 and 5.19) the best value for |_i is chosen that corresponds with the given values for a (and probably b). From these graphs, the best value for b can also be calculated. For example, i f we are constrained by a worst-case delay of 15s and buffer size of 6 0 M B , and the required rate is a = 4.2 M B / s and b = 25 K B , then from the graphs we have to choose (j. « 3.7 M B / s to meet Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation . 103 these QoS requirements. Finally, Figures 5.20 to 5.27 present similar results for the dependent bit error case. Naturally, the observed values are worse due to the bit error dependency (as compared with those in previous figures), but the methodology is similarly applicable. We observe a very close match between the mean values of the numerical and simulation results. In fact, for both applications of optimal shaping and resource allocation, and both scenar-ios of independent and dependent bit errors, the results are similar. Also, the plots representing the worst-case values match very closely, when a is given and p. is to be found (resource allocation application). However, it is interesting to note that there is a slight mismatch between the results of the worst-case values, when p is given and a is to be found (optimal shaping application), i.e., in Figures 5.7 and 5.9 (for the independent bit error case) and Figures 5.21 and 5.23 (for the dependent bit error case). This slight mismatch is due to the fact that the actual shaped traffic and its arrival curve do not exactly match, which happens when we shape the same traffic input with a wide range of shaping rates. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 104 Figure 5.4 Plots of the mean delays versus b and a. 10 15 20 25 30 b (KB) Figure 5.5 Contours of plots in Figure 5.4. The values on the graphs are the corresponding mean delays. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation . 105 Figure 5.6 Plots of the worst delays versus b and a. b (KB) Figure 5.7 Contours of plots in Figure 5.6. The values on the graphs are the corresponding worst delays. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation . 106 Figure 5.8 Plots of the mean buffer sizes versus b and a. 10 15 20 25 30 b (KB) Figure 5.9 Contours of plots in Figure 5.8. The values on the graphs are the corresponding mean buffer sizes. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation . 107 Figure 5.10 Plots of the worst buffer sizes versus b and a. b (KB) Figure 5.11 Contours of plots in Figure 5.10. The values on the graphs are the corresponding worst buffer sizes. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 108 u (MB/s) Figure 5.12 Plots of the mean delays versus b and a. 10 15 20 25 30 35 b(KB) Figure 5.13 Contours of plots in Figure 5.12. The values on the graphs are the corresponding mean delays. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation . 109 u (MB/s) 2 1.5 0 Figure 5.14 Plots of the worst delays versus b and a. Contour of worst delay from analysis Contour of worst delay from simulation ( )| 20 25 b(KB) Figure 5.15 Contours of plots in Figure 5.14. The values on the graphs are the corresponding worst delays. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation . 110 u (MB/s) Figure 5.16 Plots of the mean buffer sizes versus b and |it. 10 15 20 25 30 35 b(KB) Figure 5.17 Contours of plots in Figure 5.16. The values on the graphs are the corresponding mean buffer sizes. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation . I l l 40 Figure 5.18 Plots of the worst buffer sizes versus b and u. b(KB) Figure 5.19 Contours of plots in Figure 5.18. The values on the graphs are the corresponding worst buffer sizes. Chapter 5. Optimal Leaky-Bucket Shaper and Resource A llocation ... 112 b (KB) Figure 5.20 Mean delays versus b and a - dependent bit error scenario. b (KB) Figure 5.21 Worst delays versus b and a - dependent bit error scenario. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation ... 113 „ 3.8 CO. Figure 5.22 Mean buffer sizes versus b and a - dependent bit error scenario. > Contour of worst buffer from analysis > Contour of worst buffer from simulation ( )| T V Figure 5.23 Worst buffer sizes versus b and a - dependent bit error scenario. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 114 _^=5>2> Contour of mean delay from analysis Contour of mean delay from simulation 20 25 b (KB) Figure 5.24 Mean delay versus b and u. - dependent bit error scenario. 4h Contour of worst delay from analysis Contour of worst delay from simulation ( )| 20 25 b (KB) Figure 5.25 Worst delay versus b and u - dependent bit error scenario. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation . 115 Contour of mean buffer from analysis Contour of mean buffer from simulation 20 25 b (KB) Figure 5.26 Mean buffer sizes versus b and u. - dependent bit error scenario. i — r 1 - R H 1 Contour of worst buffer from analysis ! Contour of worst buffer from simulation ( )| J 200 _ _ i i _ 20 25 b (KB) Figure 5.27 Worst buffer sizes versus b and u. - dependent bit error scenario. Chapter 5. Optimal Leaky-Bucket Shaper and Resource Allocation 116 Effect of S N R : Figures 5.4 to 5.27 are plotted under the assumption that the average SNR is 10 dB. The statistics of the latency (T) of the rate-latency server are directly related to S N R (and other physical layer assumptions such as modulation). Since the value of T (its mean and variance) changes depending on SNR, the value of the delay is accordingly affected by SNR (as was explained by Figure 5.3). The effect of the SNR on delay was discussed in Chapter 4, where Figure 4.12 showed the values of the mean and worst delays versus average SNR. The figure showed that for any value larger than 10 dB, the delay stays nearly constant. Therefore, this value is the best choice for this scenario. 5.6. Summary In this chapter, we have presented a methodology for the derivation of optimal parameters of a leaky-bucket shaper for transmission over wireless fading channels. The method is based on a stochastic min-plus system theory approach for second-order statistics. The shaper results in minimum (or feasible minimum) delay and buffer requirements, given the imposed constraints. We have presented numerical and simulation results to support the proposed methodology in two applications of optimal traffic shaping and resource allocation. 117 Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements In this chapter, an alternative methodology for evaluation of QoS in wireless networks based on N C theory and components is introduced. The proposed model employs modular concat-enation of selected N C components to represent the effect of wireless links on QoS performance at the link layer. We present a mathematical analysis that applies the model to evaluate the perfor-mance of a wireless video streaming application, by deriving estimates of the playback delay and buffer size at the receiver side. Owing to the analytical strength of N C , the model offers an efficient way of deriving end-to-end QoS characteristics in wireless networks. 6.1. Introduction For the analysis and end-to-end N C study of a network including wireless links, we need to represent its different parts by N C components. Although there is a rich literature on modeling the wireline parts of a network by N C , to the best of our knowledge, there is no model available for wireless links based on N C components in the open literature. Such an N C model is expected to be very effective for theoretical performance evaluations of QoS-enabled packet networks incorporating wireless links, and to yield benefits of efficiency, a systematic approach and simplicity of analysis, as in its more well-known applications in wired networks. The method has a number of advantages. First, the model is constructed from the familiar N C components and therefore is completely compatible with deterministic N C theory. Second, it Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 118 is statistically based on the widely used Markov chain models for wireless channels. Finally, it is an efficient method when a statistical service curve is required in order to solve certain network-ing problems. For example, we use our proposed method to find an optimal smoother for the application of multimedia streaming in wireless networks. This feature is an advantage not offered by the stochastic approaches presented in the literature. The main challenge of applying N C to wireless networks, however, is to account for the variability of the wireless link's property and its effects on the transmitted traffic. In Chapter 4, we laid the foundations for applying the theory of N C in QoS evaluation of wireless networks using stochastic min-plus theory. In this chapter, to consider the time-varying nature of the channel, we map its finite-state Markov chain characterization into a time sequence. This sequence then corresponds to an f-server bank whose branches consist of a concatenation of N C components. Applying a novel methodology to this model, we are able to use the robust N C theory to evaluate the statistical QoS of wireless networks. When evaluating a wireless network, this model is used in place of the wireless links to enable the use of N C in determining the end-to-end performance. Figure 6.1 shows the position of such a model in the network. The model uses a set of N C components that collectively represent the properties of a wireless link. We make use of different N C f-servers, such as shapers, rate-latency servers, and clippers. Then we use the proposed model to calculate the playback delay and buffer size at the receiver for streaming smoothed variable bit-rate (VBR) video to mobile users. We show that by employing the proposed N C model, such a difficult task becomes easily manageable. In the next section, the building blocks that are needed to model a wireless link are introduced. The model is characterized by a finite-state Markov chain, and then this general paradigm is instantiated to derive an equivalent model for the well-known two-state Markov wireless channel model. The proposed model is then applied to evaluate the performance of wireless video streaming in Section 6.3. A numerical example is presented in Section 6.4, and the proposed method is discussed in Section 6.5. Finally, a summary of the chapter is presented in Section 6.6. Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 119 x(t) r , ^ ^ y(t) PkLoss ^>—Bandwidth [-•<' Delay )^ • • • • G(t,v) Figure 6.1 Wireless link modeling. 6.2. Wireless Link Model In this section, the general characteristics of a wireless l ink are modeled by using a number of different stages, each defined by an N C component. These components are organized in sequence, each modeling one property of the link. This modular approach allows us to include only properties desired in different applications. In the literature, two types of channel models are usually considered: link-level and radio-level. The link-level metrics are: delay, packet loss, and time-varying bandwidth of the link, while at the radio-level, bit error rate and signal-to-noise-plus-interference ratio are characterized. In the following, three N C elemental stages of the proposed l ink model are defined, modeling packet loss, delay, and bandwidth of a simplex link. A duplex link is modeled by two simplex links for the two opposite directions of communications. Packet loss: In N C , packet losses are modeled by a component called the clipper. A clipper (Figure 6.2a) is used to simulate packet losses that occur in the transmitter or the receiver due to the limited capacity of the link (congestion), packet time-outs, or non-correctable errors in the physical layer. Chapter 6: An Alternative Wireless Link Model Using Filter Banks of NC Elements 120 (a) (b) Clipper (Sink) Clipper —• + tr Figure 6.2 a) Clipper, b) Clipper equivalent with ARQ. For an incoming traffic A(t), with total losses of l(t), the amount of actual traffic that passes through the link (input) is x(t) = A(t) - /(f). Due to the difficulty in using clippers when applying the concatenation property, the following procedure can be applied instead. Depending on the traffic type and application, packet loss modeling can be handled in two ways. If the link is equipped with an A R Q scheme to combat transmission errors, such as in transmission of elastic Internet traffic, then the clipper plus the A R Q mechanism (Figure 6.2b) is replaced with a lossless system followed by a compensator element [9], adding the correctly retransmitted traffic, l\t), to the arrival process as x(t) = (A(t) - /(f)) + /"(f). /"(f) is defined based on the deployed A R Q mechanism, using the (a(f), p(f)) calculus [8] characterization. For real-time applications, however, the input is just considered as x(t), as shown by Figure 6.2a. The above methods are particularly helpful when the wireless link is the first or last link in the end-to-end path, as usually is the case. Time-varying Bandwidth: This stage is the crucial block in modeling the time-varying nature of the wireless link. We use a bank of time-invariant f-servers to model a Markov process channel model. Shapers or rate-latency servers can be used in place of these general f-servers. Here we use shapers. A time-varying shaper (p(r) , cr(f)) represents the available bandwidth p(f) and/or burst tolerance a(f) of the link. The burst tolerance models the feasible size of the traffic burst that can pass the link, which could depend on factors such as the capacity of the transceivers, workload and/or the available bandwidth itself. A shaper with a service curve expressed with a function of two time variables, h(t, v ) , forces the output y(t) to comply with y(t) < hit, v) + yiy), where Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 121 h(t,v) = <-(/) + \piy)dy. (6.1) V To model the time-varying channel bandwidth, we consider the following two aspects. As a wireless channel is commonly modeled by a finite-state Markov chain [75][76][77], we can represent its statistical behaviour by mapping the state changes and holding time with a time sequence with an associated probability p. Second, we consider a bank of time-invariant f-servers. Each f-server corresponds to a channel condition (in particular, bandwidth) in each state of the known finite-state Markov chain model. Therefore, i f we associate the f-server bank to this sequence, we have an N C model with a known probability. Now we can apply the deterministic N C theory to this model to derive different QoS bounds, with probability p. Depending on the application, each state is associated with some conditions. In physical layer channel models, the conditions are the BERs ; here we associate the states with different QoS metrics. Depending on which state the channel is in, the traffic chooses one of the possible branches upon arrival. We assume that the channel has an m-state Markov model with known transition probabil-ities, with each state represented by an f-regulator (a ; , p ( ) . The sample space of this Markov chain can be translated to a time series o f instants when the channel changes state: r = {x-|(z = 1, 2, . . . ) } , where the channel changes states at times x;-, Xj = 0. Each time series has a probability p, and a corresponding series of channel states S = , i.e., the channel is in state st starting at time xi. One of the m shapers is selected at each state transition time starting at X ; . The shaper bank and the sequence (controller) together define the service curve h(t, v ) . Fo r any v<t, we suppose that there are M state changes occu r r ing dur ing [v, /] , Xj < v < x 2 , x M < t < xM+ j . Thus, the time-varying shaper has the following general service curve: M h(t,v) = £ {ps(mi+l-mi) + ^s,} + PsM(t-mM) + G . (6.2) Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 122 where mx = v,m2 = x 2 , mM = iM, mM+ \ = t, and u(t) is the step function. Although there are infinite numbers of such sequences and correspondingly of h(t, v ) , a probability can be associated to each of these piece-wise linear service curves. Depending on the shape of the service, the probability indicates the chance of other service curves being within its service region (i.e., at time t, its value being less than the others), therefore resulting in smaller maximum delays. This concept w i l l be explained in the next section, where we introduce a lemma that allows us to reduce the required calculations in deriving meaningful QoS bounds. This service curve allows us to use the statistical N C framework. As discussed earlier in Chapter 2, in the statistical N C theory, a service curve with probabilistic service guarantees is used. B y using the theorems and the filtering concept of this theory, we can derive all of the required statistical QoS metrics of delay, buffer size and output. Constant Delay: The overall delay can be broken up into fixed and variable delays. The variable delay, which is caused by the channel conditions, is modeled by the previous component. Assuming that the total of all constant delays, such as propagation and transmission delays, is T, a delay stage is defined with a service curve of 8 r ( r ) : which is similar to the delta function in system theory, causing the input function to shift in time after convolution. Analysis of V B R video transmission over a lossless deterministic network by N C was studied in [11] and [41], where the calculations of the minimum playback delay and buffer capacity at the receiver side were presented. Our proposed service curve for the wireless link can now be incorporated in this model to calculate the optimal playback delay and buffer size for a wireless user who receives streamed video over a wireless network. N C is the most efficient i f t > T, otherwise, (6.3) 6.3. Application in Wireless Video Streaming Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 123 Decoder a(t) Decoding y(t) Buffer Smoother x(t-D) Figure 6.3 Network schematic in the study of video streaming application. method for such a study. In contrast, the schedule optimization method [78] employing arrival and playout vectors to derive optimal buffer allocation and playback delay assignments in a wireline network has a 0 ( 0 ) optimization complexity, where <J> is the maximum number of frames in the video trace for a single-link system. In a tandem model, the complexity increases multiplicatively by the number of intermediate nodes, 9, i.e., (0(6$)), making it difficult in practice to study real networks. Figure 6.3 illustrates the considered scenario. The video server (encoder) transmits a pre-recorded video over a wireline sub-network with service curve §(t), and then through a wireless link with service curve G{t), to a user. The traffic is first smoothed to produce a conforming flow according to the QoS service agreement. The receiver needs to buffer the incoming data and then starts the playback after some playback delay D, to compensate for the unpredictable network delays. We also wish to calculate the minimum buffer size, X, required for keeping the received data. The challenge now is to estimate the minimum playback delay and required buffer size, and to suggest the optimal smoothing output. Without loss of generality, we assume that is a null network, i.e., <(>(f) = 5 0 ( f ) . The main results defining the playback delay and buffer size, as well as optimal smoothing strategy, were briefly discussed in Chapter 3, Section 3.6. We first use the building blocks that were described in the previous section to derive a N C model to replace G(t) in Figure 6.3. Without loss of generality and for ease of discussions, here we consider a two-state channel model. The following methodology can be extended to any finite-state Markov or Fritchman model. The Markov model has a state space of a good (G) and a bad Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 124 Figure 6.4 NC modeling of G(t) in Figure 6.3. state (B), i.e., s- e {G,B} with transition probabilities {P B,PB }. For a Rayleigh fading channel, the probabilities of being in state G or B are, respectively, PG = e A , or PB = 1 -PQ, where A is the Rayleigh fading envelope normalized to the local rms level [79]. We assume that the durations in which the channel stays in the Good or Bad states are exponentially distributed with means 1/8 and 1 / K , respectively. Each state is associated with a branch in the f-server bank with service curves HB(t) and HG(t), incorporating the three stages of the previous section. In state G, the channel is modeled by a shaper with a rate of pG and burst tolerance of a G , defining HG(t) = pGt + aG, and a packet loss of lG(t). Similarly in state B, the channel behaves as a shaper with (HB(t) = pBt + <JB) and a clipper with a packet loss of lB{t). A n overall constant delay of T is also assumed. Figure 6.4 shows the proposed model. B y applying the N C theory, we can now derive the input/output relationship. The output y(t) of the link is where b(t) is the sum of the outputs of the filter branches; these outputs are non-overlapping, as the channel exclusively chooses one of the possible states and correspondingly only one of the branches of the filter bank. Since x(t) is the cumulative traffic, x(x ( + \ )—x(xt) represents the accepted traffic during [x-, x / + x ] . Assuming there are N intervals where the channel changes y(t) = 6 ( 0 ®8y ( 0 = b(t-T), (6.4) state during [0, t], i.e. N = (max(j)\Xj < t), then Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 125 KO = Y f K W - ^ + ^ x , ) ) ® ^ - - ^ . ^ / ( 6 5 ) ( % ( 0 - + * ( % ) ) ® -where 5(- e {G, B), and x 5 (t) is calculated by x , . ( 0 = As{t)-Ls{t), (6.6) where J V - 1 As(t) = £ ( ^ ( T i + 1 ) - ^ ( x , ) ) x l { ^ J i } + ( / l ( 0 ^ ( x w ) ) x l { ^ = i j } , (6.7) /•= 1 and 9(x () is the corresponding queue content at time xt with q(0) = 0 . At each xt, the value of # ( T - ) is derived by using b(xj)-x(xi). Also, Hs(t-Xj) indicates a shift of origin to T ; - for the service. The above derivations are based on the results for a shaper with non-empty initial buffer ([9], pp. 213), and the fact that for any two functions/and g, we h a v e / ® g <f when g(0) = 0. The indicator function 1 { C 0 „ ^ , ; 0 „ } has the value 1 when the condition is true, and 0 otherwise. Equations (6.4), (6.5) and (6.6) are sufficient to evaluate the effects of the wireless link on the QoS performance. In a wireless network, the wireless link is replaced by the representing service curve and then by applying the convolution and concatenation properties of N C , the end-to-end QoS can be evaluated. The delay that the data arriving at time t encounters is given by d(t) = inf{A>0: x(t) <y(t + A)} and the vir tual backlog at time t inside the system is x(f) -y{t). Differently put, the delay bound for a system with a service curve of G(t) and input traffic with an arrival curve of %(t) is Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 126 k&G) = sups>0(inf{T:T>Q and Z,(s) < G(s + T)}), (6.8) which graphically is the maximum horizontal distance between the graphs of G(t) and . The maximum buffer size is which graphically is the maximum vertical distance between the graphs of G(t) and 4(f). Despite the somewhat formidable look of these equations, they are simply the summation of the analysis in different intervals of the mapped sequence. Since the branch selector of the filter bank works based on the transition probabilities of the Markov chain, the resulting service curve is one of many possible piece-wise linear service curves. To each of these service curves, a probability can be associated that indicates the chance of every other service curve being within its service region, therefore resulting in smaller maximum delays. This condition applies when for the times that maximum delays occur, the value of this service curve is less than that of the other service curves. The service curve consid-ered in Lemma 6.1 is a good example of this case, where with a very high probability, results in the calculation of the worst-case delay. Through this lemma, we present an approach that further reduces the calculations and makes this analysis more appealing. Lemma 6.1: In transmission time tT, for a class of all sequences whose total time with the channel in the Bad state is tB, (tT- tB in the Good state), the sequence in which the channel first stays in the Bad state for the whole tB and then switches to the Good state for the rest of the transmission time, represents the worst-case bounds for that class. This lemma allows us to simplify the calculation greatly, by considering this worst-case sequence. Equations (6.8) and (6.9) intuitively justify Lemma 6.1, since the stated bounds are the maximum vertical or horizontal distances between the arrival and service curves, which occurs when the service curve is farthest away from the arrival curve. This occurs when the entire time that the channel is in the Bad state occurs at the beginning. This concept is shown graphically by v($,G) = sup{Ut)-G(t)} (6.9) Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 127 Figure 6.5 which is related to the results of the next section. This reduces the final service curve to the following: G(t, tB) = HB(t)(u(t)-u(t - tB)) + HG(t, tB)u(t- tB), (6.10) where HQ^, tB) is simply HG(t- tB) +HB(tB). The probability associated with this service curve is the probability of the channel being cumulatively in the Bad state for tB. Since this lemma proposes a worst-case bound for the delay, it is necessary to evaluate how loose the bound is. We study this considering the length of the transmission session. A ) If the transmission time is in the same order as the average holding time in the Bad state, i.e., when tT « ( 1 / K ) , then the above probabilistic method obviously does not apply. In this situation, the best design factor is to consider tT as the worst-case delay, which is reasonable in practice as the value of 1 / K is usually very small. B) If the transmission time is much longer than the expected mean of the Bad state holding time, i.e., whenever tB»{ 1 / K ) , then Lemma 6.1 is applicable. Since tB is a random variable, it needs to be evaluated over the range of values for which it is valid. A scalable way of calculating tB to be used with Lemma 6.1 is to consider tB = PBtT, whenever ? 5 » ( 1 / K ) . However, the longer the transmission time, the more conservative the value of the estimated worst-case delay wi l l be. As mentioned in the previous section, in order to account for the packet losses, for ease of calculations, we can consider an equivalent model where the packet losses are incorporated in the arrival process, when the application allows it (as here). Otherwise, equivalent clipper models must be included. This way the final model looks lossless, as there is no clipper, therefore, = ^ ( 0 = 0. This enables us to readily calculate the overall service curve of the link model, G(t) from (6.10) with a likelihood p. Now, for a given traffic arrival curve <^(t), Equations (6.8) and (6.9) can be used to Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 128 0 50 100 150 200 250 300 350 400 Time (Sec) Figure 6.5 Playback delay and buffer size calculation for the Jurassic Park video trace streaming. calculate the minimum playback delay and buffer size, respectively. The optimal smoother output can be calculated by f ( f ) = supu>0tV>0{x(t-u-v)-Z,(u)-G(v)} , also known as deconv{x, % <8> G) > t 0 achieve the optimal transmission schedule [41]. 6.4. Numerical Example A s a numerical example, we consider a pre-recorded high-quality M P 4 trace of the Jurassic Park movie [80] that is streamed to a wireless user. The traffic specification (T-Spec) of this trace is 4(0 = min{M+pt,rt + b) where the peak and average frame rates are Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 129 p = 3.3Mbps and r = 110Kbps, the maximum frame size is M = \30Kbits and a burst tolerance b = \Mbits is considered, corresponding to 74 frames. Let the link have Good and Bad states with bandwidths of pG = \Mbps and p 5 = 120Kbps, respectively. We consider that during the total transmission time of [0, 360] seconds, the channel is in the Bad state for a total duration of 130 seconds (36%), which represents a hostile condition. Figure 6.5 depicts four different possible curves with this assumption, in addition to the arrival envelope. For example, 51 represents a sequence in which during [50, 120] and [220, 280] seconds, it is in the Bad state and S2 represents the curve addressed by Lemma 6.1. The minimum playback delay D and minimum required buffer size X are readily estimated by considering 52 and graphically applying Equations (6.8) and (6.9), respectively. Using the plot of Figure 6.5 leads to Dw = 120s and Xw = 12 MB. To verify how extreme these values are, we calculate these bounds using another service curve, 54. In 54, the duration in which the channel stays in the Bad state is evenly distributed over the total transmission time, based on the mean holding time of the Bad state. Therefore, 54 represents the smallest bounds among the service curves in this scenario. These lower bounds, as shown in Figure 6.5, are DS4 = 50s and XS4 - 6.3MB. This method is straightforward and systematic, and the model can be used to incorporate more elaborate service curves and/or to include the effects of the intermediate nodes in the analysis. 6.5. Discussion The method presented in this chapter has advantages and disadvantages. The main advantages are as follows: In comparison with the method presented in Chapter 4, this method can be used when a service curve with calculable second-order statistics cannot be found that mod-els the wireless channel. It only requires the Markov chain model of the channel. Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 130 The method is based on the Markov chain channel models; therefore, it can take ad-vantage of the various channel models available in the literature. Here, a two-state Markov chain with exponential holding times was used. In general, for each of the states of a multi-state Markov chain, a branch is added to the filter bank. The model can be used in accordance with the statistical N C framework. When the resulting piece-wise service curves can be associated with a probability indicating their level of service guarantees, this curve can be used in the statistical N C theory ex-plained in Chapter 2. • The method uses different N C components in concatenation to model different channel characteristics in a modular manner. Therefore, in different applications, one can focus on the QoS metric of interest. This modularity usually decreases the com-plexity of the analysis. • The method presents a piece-wise service curve for the channel, which can be used in an NC-based end-to-end performance analysis by using the concatenation property. A useful application of such a technique is in the context of the M R S V P [38] mecha-nism. The disadvantages of this method are as follows: The only available N C model for packet loss is based on clippers. Since a clipper is not a lossless element and is not modeled by a usable service curve, elaborate and com-plex considerations are required to use it within the N C filtering theory for practical scenarios. A n example of such considerations is the modification of the input, as ex-plained in this chapter. Since the filter bank model depends on the use of clippers for modeling packet loss, it inherits a similar complexity. • The procedure for defining a practical and meaningful probability associated with each service curve is not straightforward. In a more involved practical scenario, such as when the holding times are not exponential, defining such probabilities may not be easily possible. • The calculated bounds may be loose, when the service curve does not tightly repre-sent the characteristics of the channel. In particular, for a long transmission session, the worst-case delay derived from Lemma 6.1 can be conservative. Chapter 6. An Alternative Wireless Link Model Using Filter Banks of NC Elements 131 6.6. Summary In this chapter, an alternative Network Calculus model has been developed so that the theory of N C can be applied to the stochastic performance evaluation of wireless networks. We have instantiated the general model to derive an equivalent model of the widely used two-state Markov channel model. The model was then applied to effectively solve the problem of playback delay and buffer size calculation for V B R streaming over a wireless network. 132 Chapter 7. Summary and Future Work We conclude this dissertation by summarizing its content and contributions, and suggest-ing some directions for future work. 7.1. Summary In the first chapter of this thesis, the objectives and motivations inspiring the work were presented. Specifically, we stated that out objective was to contribute to the performance evalua-tion and QoS provisioning techniques in wireless data networking, based on the min-plus system theory. A n introductory background on the min-plus filtering theory wad provided in Chapter 2, explaining its mathematical foundation, traffic and service characterizations, notations, and related topics. The min-plus system theory is based on min-plus algebra, a special algebra with two operators of infimum and addition. The chapter addressed Network Calculus as a determinis-tic min-plus filtering theory, as well as arrival and service curves and min-plus convolution. Stochastic traffic characterization and statistical N C were discussed. The main body of the thesis consists of Chapters 3, 4, 5 and 6. Chapter 3 introduced the slope domain modeling technique as a useful complement to Network Calculus and the min-plus system theory in general [21]. Based on the application of slope transform, this method facilitates NC-based analysis of data communication networks. Slope transform is a general mathematical transformation that is applicable to any function. For a convex or concave function with an invert-Chapter 7. Summary and Future Work 133 ible derivative, its slope transform is equal to its Legendre transform. Also, a number of useful applications of this theory, such as network identification and priority scheduling, were discussed. For the network identification application, analytical and simulation examples were presented and practical considerations were discussed. The chapter also identified the available fast computation algorithms. Chapter 4 presented a stochastic min-plus system theory approach, which is one of the main contributions of the thesis [22][23]. The method is based on two theorems and presents a technique for calculating the second-order statistics of the system output, when input or service is stochastic. This method can be used to study stochastic min-plus servers. We presented an example model of a wireless link, by which the application of the method in performance evalua-tions of wireless data networks was explained. The model considered a wireless Rayleigh fading channel for a user with an assigned dedicated bandwidth. Simulation and analytical results were plotted and explained. In conjunction with the slope domain modeling approach presented in Chapter 3, the useful concept of load spectrum was introduced, which may facilitate calculation of the equations in the theorems. . Chapter 5 used the concept introduced in Chapter 4 for QoS provisioning in wireless data networks, to address two applications of optimal traffic shaping and resource allocation for transmission over wireless fading channels [27]. In these applications, the method is used to find the best set of values for the system parameters in order to achieve the desired service quality. In the case of the traffic shaping application, shaper parameters are set so that it results in minimum delay and buffer sizes. For the resource allocation application, the required channel rate is determined. Depending on the given constraints, the solution is optimal or sub-optimal. Chapter 6 addressed an alternative method for modeling a wireless link layer, using a filter bank consisting of Network Calculus components [25][24]. A general model was then instantiated to derive an equivalent model of the widely used two-state Markov channel model. This method was then used in playback delay and buffer size calculations at the receiver side for V B R stream-ing over a wireless network. The chapter also discussed the application of the model for defining the optimal smoothing scheme to minimize playback delay and buffer size. Chapter 7. Summary and Future Work 134 7.2. Further Work In the course of the investigations reported in this thesis, a number of interesting problems were encountered that merit further study. Slope domain modeling is a useful concept that needs to be studied in greater detail, both for the applications introduced in this thesis, and for possible new applications. Some intriguing areas for further study include the following: * Although the analytical aspect of the network identification method was thoroughly studied in the thesis and simulation results for a network were presented, the practical limitations and advantages of such a method need to be investigated further by using test-beds or actual networks. In addition, a systematic way of properly selecting the rate of the affine functions, as well as implementation of the method based on adaptive shapers, require more study. Some other related issues of interest are: exact specifications of stability conditions, applications in stochastic services, and applicability regions of the method. * There is no fast computation algorithm for the slope transform, which may limit applica-tion of the method to off-line cases. Therefore, research on finding fast algorithms, specially based on available fast algorithms for the Fenchel conjugate, wi l l create the possibility of on-line applications for this modeling domain. * Load spectrum was introduced to facilitate calculations of the stochastic min-plus theorems. However, this concept corresponds to the power spectrum in traditional system theory, which suggests the likelihood of better applications for this concept. The stochastic min-plus theorems presented in this thesis and their applications in wireless networking require further consideration, as follows: * In order to use the proposed stochastic method in more advanced multiuser congestion-prone wireless links, elaborate calculations of PER need to be applied instead of (4.19) or (4.22). Examples of such PER models are studied in [86] [87]. * The wireless channel model that was presented in the thesis considers that a dedicated bandwidth is assigned to the user. Since the presented method is also applicable to upper service curves, the technique may be applied in the analysis of multiuser wireless networks with random multiple access (such as Aloha), when P E R is accordingly modified. In these systems, the user Chapter 7. Summary and Future Work 135 either has to contend for bandwidth and/or suffers from interference. Such an extension in application needs further study. A n immediate approach is to use the B E R statistics calculation methods that are available in the literature for such scenarios instead of (4.16) or (4.21). Also the effect of different error correcting codes and systems [88][89], and A R Q protocols on the model needs to be studied [90] [92]. * In order to apply the method to systems with lower service curves, further study is required to define the exact conditions in which equalities hold in (4.11), (4.12) and (4.13). A good candidate for such condition can be based on convexity for use in Jensen's inequality. * In this thesis, only Rayleigh fading channels are considered. However, the application of the proposed method may be extended for other channel models, when second-order statistics of the service can be obtained. * Similarly, the effect of the above issues on the optimal shaping and resource allocation applications of Chapter 5 requires further investigation. For the effective use of the filter-bank modeling method for wireless channel modeling, the method requires improvement in the following aspects. * In Chapter 6, a two-state Markov chain with exponential holding times was used. In order to use this method with more advanced channel models, the application of the method based on multi-state Markov chains with non-exponential holding times needs to be studied. * Although the filter bank channel model is a useful method, its actual implementation requires further improvement. The method relies on using either Lemma 6.1 or selecting another piece-wise service curve with a known associated probability. The lemma presents the worst-case scenario, which is not necessarily the best selection. For the latter case, due to the complexity of the filter branch selection mechanism in a more involved practical scenario, defining an accurate probability requires future work. As explained in Chapter 2, the min-plus theory used in this dissertation applies to the class of D E D S where synchronization but no concurrency occurs. This is a basic principle ensuring linearity. However, there are available methods that ease these conditions at a cost, and can be used to model special cases in data networking. One such method is discussed by De Schutter and van den Boom in [93]. Also, the application of the proposed method at higher layers [94], as well as in the multi-variable D E D S , are interesting topics for future work [95][96][97]. 136 R e f e r e n c e s [I] A . Jamalipour, "Research on wireless mobile Internet," IEICE Communications Society Global Newsletter, vol. 1 (2), pp. 26-29, November 2002. [2] J. K i m and A . Jamalipour, "Traffic management and QoS provisioning in future wireless IP networks," IEEE Personal Communications, vol. 8 (5), pp. 46-55, October 2001. [3] R. Braden, D. Clark, and S. Shenker, "Integrated services in the Internet architecture: an overview," IETF RFC 1633, June 1994. [4] B .E . Carpenter and K . Nichols, "Differentiated services in the Internet," Proceedings of the IEEE, vol. 90 (9), pp. 1479-1494, September 2002. [5] Y. Bernet, S. Blake, D. Grossman, and A . Smith, " A n informal management model for DiffServ routers," IETF RFC 3290, May 2002. [6] A . K . Parekh and R. G. Gallager, " A generalized processor sharing approach to flow control in integrated services," IEEE/ACM Transactions on Networking, vol. 1 (3), pp. 344-357, June 1993. [7] F. Baccelli, G. Cohen, G. J. Olsder, and J. P. Quadrat, Synchronization and Linearity, An Algebra for Discrete Event Systems, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, August 1992. [8] C.-S. Chang, Performance Guarantees in Communication Networks, Springer-Verlag, 1st edition, Apr i l 2000. [9] J.-Y. Le Boudec and P. Thiran, Network Calculus: A Theory of Deterministic Queuing Systems for the Internet, Springer-Verlag Lecture Notes in Computer Science, vol. 2050, January 2002. [10] J.-Y. Le Boudec, "Application of Network Calculus to guaranteed service networks," IEEE Transactions on Information Theory, vol. 44 (3), pp. 1087-1096, May 1998. [II] V. Firoiu, J.-Y. Le Boudec, D. Towsley, and Z. L . Zhang, "Theories and models for Internet quality of service," Proceedings of the IEEE, vol. 90 (9), pp. 1565-1591, September 2002. 137 [12] J.-Y. Le Boudec, "Network calculus made easy," Technical report EPFL-DI96/218, Ecole Polytechnique Federate de Lausanne, December 1996. [13] R . A . Malaney and G. Rogers, "Network calculus and service curve scheduling in heterogeneous networks," Proc. IEEE International Conference on Networks (ICON'99), pp. 250-254, September 1999. [14] H . Zhang, "Service disciplines for guaranteed performance service in packet-switching networks," Proceedings of the IEEE, vol. 83(10), pp. 1374-1396, October 1995. [15] I. Stoica, H . Zhang, and T. S. E. Ng, " A hierarchical fair service curve algorithm for link-sharing, real-time, and priority services," IEEE/ACM Transactions on Networking, vol. 8 (2), pp. 185-199, Apr i l 2000. [16] D. Wu and R. Negi, "Effective capacity: a wireless link model for support of quality of service," IEEE Transactions on Wireless Communications, vol. 2 (4), pp. 630-643, July 2003. [17] J. Liebeherr, S. Patek, and A . Burchart, " A calculus for end-to-end statistical service guarantees," Technical report CS-2001-19, University of Virginia, 2001. [18] K . Lee, "Performance bounds in communication networks with variable-rate links," Proc. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, New York, 1995. [19] J. P. Quadrat, "Min-plus probability calculus," Actes 26eme ecole de printemps d'informatique theorique, Noirmoutier, 1998. [20] Y. L iu , C . -K. Tham, and Y. Jiang, " A stochastic Network Calculus," Technical Report ECE-CCN-0301, National University of Singapore, November 2004. [21] F. Agharebparast and V. C. M . Leung, "Slope domain modeling and analysis of data communication networks: a Network Calculus complement," Proc. IEEE International Conference on Communications (ICC'06), Istanbul, Turkey, June 2006. [22] F. Agharebparast and V. C. M . Leung, " A novel stochastic min-plus system theory approach for performance modeling and cross-layer design of wireless fading channels", Proc. International Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs '06), Yorkshire, U . K . , September 2006. [23] F. Agharebparast and V. C. M . Leung, " A novel stochastic min-plus system theory approach for performance evaluation and design of wireless networks," Accepted for publication in Kluwer International Journal of Wireless and Personal Communications (WIRE HET-NETs Journal Issue 4), 2007. [24] F. Agharebparast and V. C. M . Leung, "Link-layer modeling of a wireless channel using stochastic Network Calculus," Proc. IEEE Canadian Conference on Electrical and Computer Engineering (CCECE'04), Niagara Falls, Ontario, Canada, May 2004. 138 [25] F. Agharebparast and V. C. M . Leung, "Modeling wireless link layer by Network Calculus for efficient evaluations of multimedia quality of service", Proc. IEEE International Conference on Communications (ICC "05), Seoul, Korea, May 2005. [26] F. Agharebparast and V. C. M . Leung, "Evaluation of the U M T S QoS support using OPNET U M T S model suite," Proc. Opnetwork Conference, Washington D C , August 2002. [27] F. Agharebparast and V. C. M . Leung, "Optimal shaping for transmission over wireless fading channels," Proc. IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM'07), Helsinki, Finland, June 2007. [28] R. L . Cruz, " A calculus for network delay. I. Network elements in isolation," IEEE Transactions on Information Theory, vol. 37 (1), pp. 114-131, January 1991. [29] R. L . Cruz, " A calculus for network delay. II. Network analysis," IEEE Transactions on Information Theory, vol. 37 (1), pp. 132-141, January 1991. [30] R. L . Cruz, "Quality of service guarantees in virtual circuit switched networks," IEEE Journal on Selected Areas in Communications, vol. 13 (6), pp. 1048-1056, August 1995. [31] J. Kurose, "On computing per-session performance bounds in high-speed multi-hop computer networks," ACM Performance Evaluation Review, vol. 2 (1), pp. 128-139, June 1992. [32] D. Starobinski and M . Sisi, "Stochastically bounded burstiness for communication networks," IEEE Transactions on Information Theory, vol. 46 (1), pp. 206-212, January 2000. [33] C.-S. Chang and R. L . Cruz, " A time varying filtering theory for constrained traffic regulation and dynamic service guarantees," Proc. IEEE Conference on Computer Communications (Infocom '99), vol. 1, pp. 63-70, March 1999. [34] T. Hisakado, K . Okumura, V. Vukadinovic, and L . Trajkovic, "Characterization of a simple communication network using Legendre transform," Proc. IEEE Int. Symp. Circuits and Systems, vol. I l l , pp. 738-741, Bangkok, Thailand, May 2003. [35] P. Maragos, "Slope transforms: theory and application to non-linear signal processing," IEEE Transactions on Signal Processing, vol. 43 (5), pp. 864-877, Apr i l 1995. [36] K . Pandit, J. Schmitt, C. Kircher, and R. Steinmetz, " A transform for network calculus and its application to multimedia networking," Proc. SPIE Conference on Multimedia Computing and Networking, January 2006. [37] M . Fidler and S. Recker, "Conjugate network calculus: a dual approach applying the Legendre transform," Elsevier Computer Networks, vol. 50 (8), pp. 1026-1039, June 2006. [38] A . K . Talukdar, B . R. Badribath, and A . Acharya, " M R S V P : a resource reservation protocol for an integrated services network with mobile hosts," Wireless Networks, Kluwer Academic Publishers, vol. 7 (1), pp. 5-19, 2001. 139 [39] M . Hamdi and F. K . L . Lee, "Providing deterministic packet delays and packet losses in multimedia wireless networks," Wireless Communications and Mobile Computing, John Wiley & Sons, vol. 3, pp. 3-22, 2003. [40] M . Schwartz, Broadband Integrated Networks, 1st edition, Prentice Hall PTR, 1996. [41] J.-Y. Le Boudec and O. Verscheure, "Optimal smoothing for guaranteed service," IEEE/ ACM Transactions on Networking, vol. 8 (6), pp. 689-696, December 2000. [42] J. V. Tiel, Convex Analysis, An Introductory Text, John Wiley & Sons, 1984. [43] A . Adas, "Traffic models in broadband networks," IEEE Communications Magazine, vol. 35 (7), pp. 82-89, July 1997. [44] W. Willinger, M . Taqqu, and A . Erramilli, " A bibliographical guide to self-similar traffic and performance modeling for modern high-speed networks," in Stochastic Networks: Theory and Applications, Oxford University Press, pp. 339-366, 1996. [45] D. L . Jagerman, B . Melamed, and W. Willinger, "Stochastic Modeling of Traffic Processes," Frontiers in queuing: Models, Methods and Problems (J.H. Dshalalow, Ed.), CRC Press, 1996. [46] K . Park and W. Willinger, Self-similar Network Traffic and Performance Evaluation, John Wiley and Sons, 2000. [47] P. Maragos, "Differential morphology: multi-scale image dynamics, max-min difference equations, and slope transforms," Proc. IEEE International Conference on Image Processing (ICIP'94), pp. 545-549, 1994. [48] P. Maragos, "Differential morphology and image processing," IEEE Transactions on Image Processing, vol. 5(6), pp. 922-937, 1996. [49] A . V. Oppenheim and A . Willsky, Signals and Systems, Prentice Hall , 1983. [50] A . V. Oppenheim and R. W. Schafer, Discrete-time Signal Processing, Prentice Hall , 1989. [51] J. P. Quadrat and Max-Plus working group, "Max-plus algebra and applications to system theory and optimal control," Proc. International Congress of Mathematicians, Zurich, August 1994. [52] L . Corrias, "Fast Legendre-Fenchel transform and applications to Hamilton-Jacobi equations and conservation laws," SI AM Journal on Numerical Analysis, vol. 33 (4), pp. 1534-1558, August 1996. [53] Y. Lucet, "Faster than the fast Legendre transform, the linear-time Legendre transform," Numerical Algorithms, Baltzer A G Science Publishers, vol. 16 (2), pp. 171-185, 1997. [54] M . A . de Inda, R. H . Bisseling, and D. K . Maslen, "Parallel fast Legendre transform," Proc. ECMWF Workshop on the Use of Parallel Processors in Meteorology - Towards Tera Computing, Reading, U K , November 1998. 140 [55] A . Papoulis, Probability, Random Variables and Stochastic Processes, 3rd edition, McGraw-Hil l , 1991. [56] E . W. Knightly, "Second moment resource allocation in multi-service networks," ACM SIGMETRICS Performance Evaluation Review, vol. 25 (1), pp. 181-191, June 1997. [57] J.-Y. Qiu, C. Cetinkaya, C. L i , and E. W. Knightly, "Inter-class resource sharing using statistical service envelopes," Proc. IEEE Conference on Computer Communications, New York, March 1999. [58] A . Kumar, D. Manjunath, J. Kuri , Communication Networking: An Analytical Approach, Morgan Kaufmann, 2004. [59] S. Ross, A First Course in Probability, Collier Macmillan Canada, 1976. [60] Y. Y. K i m and S.-Q. L i , "Modeling multipath fading channel dynamics for packet data performance analysis," Wireless Networks, vol. 6 (6), pp. 481-492, Baltzer A G Publishers, 2000. [61] T. S. Rappaport, Wireless Communications Principles and Practice, Pearson Education, 2002. [62] A . Vielmon, Y. L i , and J. R. Barry, "Performance of Alamouti transmit diversity over time-varying Rayleigh fading channels," IEEE Transactions on Wireless Communications, vol. 3 (5), pp. 1369-1373, September 2004. [63] A . S. Tanenbaum, Computer Networks, 3rd addition, Prentice Hall , 1996. [64] D. Bertsekas and R. Gallager, Data Networks, 2nd edition, Prentice Hall , 1992. [65] S. M . Ross, Introduction to Probability Models, 7th edition, Academic Press, 2000. [66] J . -Y Le Boudec, Performance Evaluation of Computer and Communication Systems, V.2.0. p .1, Apr i l 2006, Available at http://icalwww.epfl.ch/perfeval/. [67] S. Shakkottai, T. S. Rappaport, and P. C. Karlsson, "Cross-layer design for wireless networks," IEEE Communications Magazine, vol. 41 (10), pp. 74-80, October 2003. [68] A . Goldsmith, Wireless Communications, Cambridge University Press, 2005. [69] S. B . Wicker, Error Control Systems for Digital Communication and Storage, Prentice Hall , 1995. [70] H . V. Poor and G. W. Wornell, Wireless Communications, Signal Processing Perspectives, Prentice Hall PTR, 1998. [71] R. Khali l i and K . Salamatian, " A new analytic approach to evaluation of packet error rate in wireless networks," Proc. IEEE Communication Networks and Services Research Conference, May 2005. 141 [72] ETSI TS 125 212 V7.0.0 Technical Specification (2006-03), Universal Mobile Telecommunications System (UMTS); Multiplexing and Channel Coding (FDD) (3GPP TS 25.212 version 7.0.0 Release 7). [73] G. Mandyam and J. La i , Third Generation CDMA Systems for Enhanced Data Services, Academic press, 2002. [74] H . Kaaranen, A . Ahtiainen, L . Laitinen, S. Naghian, and V. Niemi, UMTS Networks: Architecture, Mobility and Services, John Wiley and Sons, 2001. [75] M . Zorzi, R. R. Rao, L . B . Milstein, "On the accuracy of a first-order Markov model for data transmission on fading channels," Proc. IEEE International Conference on Universal Personal Communications, pp. 211-215, November 1995. [76] B . D. Fritchman, " A binary channel characterization using partitioned Markov chains," IEEE Transactions on Information Theory, vol. 13 (2), pp. 221-227, Apri l 1967. [77] A . Konrad, A . D. Joseph, and R. Ludwig, B . Y. Zhao, " A Markov-based channel model algorithm for wireless networks," Report UCB/CSD-01-1142, University of California, May 2001. [78] J. Rexford and D. Towsley, "Smoothing variable-bit-rate video in an internetwork," IEEE/ ACM Transactions on Networking, vol. 7 (2), pp. 202-215, Apr i l 1999. [79] P. Lettieri, C. Schurgers, and M . Srivastava, "Adaptive link layer strategies for energy efficient wireless networking," ACM Wireless Networks, vol. 5 (5), pp. 339-355, October 1999. [80] Jurassic Park mp4 trace statistics, available at http://www-tkn.ee.tu-berlin.de/~fitzek/ TRA CE/pics/FrameStat/statldee. html. [81] I.F. Akyildiz , I. Joe, and D . A . Levine, " A slotted C D M A protocol with B E R scheduling for wireless multimedia networks," IEEE/ACM Transactions on Networking, vol. 7 (2), pp. 146-158, Apr i l 1999. [82] M . Vojnovic and J.-Y. Le Boudec, "Elements of probabilistic Network Calculus for packet scale rate guarantee nodes," Proc. International Symposium on Mathematical theory of Networks and Systems, Indiana, U.S. , August 2002. [83] S. Floyd and V. Jacobson, "Link-sharing and resource management models for packet networks," IEEE/ACM Transactions on Networking, vol. 3, pp. 365-386, August 1995. [84] Y. Cao and V.O.K. L i , "Scheduling algorithms in broadband wireless networks," Proceedings of the IEEE, vol. 89 (1), pp. 76-87, January 2001. [85] T. Chen and L . Hu, "Internet performance monitoring," Proceedings of the IEEE, vol. 90 (9), pp. 1592-1603, September 2002. 142 [86] O. Awoniyi and F. A . Tobagi, "Packet error rate in OFDM-Based wireless L A N s operating in frequency selective channels," Proc. IEEE International Conference on Computer Communications (Infocom '06), pp. 1-13, Barcelona, Apr i l 2006. [87] B . A . Bjerke, J. Ketchum, R. Walton, S. Nanda, I. Medvedev, M . Wallace, and S. Howard, "Packet error probability prediction for system level simulations M I M O - O F D M based 802.1 In W L A N s , " Proc. IEEE International Conference on Communications (ICC'05), vol. 4, pp. 2538-2542, San Diego, C A , May 2005. [88] J. R. Yee and E . J. Weldon, "Evaluation of the performance of error-correcting codes on a Gilbert channel," IEEE Transactions on Communications, vol. 43 (8), pp. 2316-2323, August 1995. [89] M . Zorzi, R. R. Rao, L . B . Milstein, "Error statistics in data transmission over fading channels," IEEE Transactions on Communications, vol. 46 (11), pp. 1468-1477, November 1998. [90] R. G. Mukhtar, S. Hanly, M . Zukerman, and F. Cameron, " A model for the performance evaluation of packet transmissions using type-II hybrid A R Q over a correlated error channel," Wireless Networks, Kluwer Academic Publishers, vol. 10 (1), pp. 7-16, January 2004. [91] L . Badia, M . Rossi, and M . Zorzi "Some results on the statistics of delay terms in SR A R Q on Markov channels," Proc. International Symposium on Wireless Communication Systems, pp. 64-68, September 2005. [92] J. G. K i m and M . M . Krunz, "Bandwidth allocation in wireless networks with guaranteed packet-loss performance," IEEE/ACM Transactions on Networking, vol. 8 (3) pp. 337-349, June 2000. [93] D. De Schutter and T. van den Boom, "Model predictive control for discrete event systems with soft and hard synchronization constraints," Proc. Workshop on Max-plus Algebras and Their applications to Discrete Event Systems, Theoretical Computer Science and Optimization, Prague, Czech Republic, August 2001. [94] F. Baccelli and D. Hong, "TCP is max-plus linear and what it tells us on its throughput," Proc. ACM Special Interest Group on Data Communication (SIGCOMM'00), pp. 219-230, Stockholm, Sweden, 2000. [95] R. Luders and R. Santos-Mendes, "Generalized multi-variable control of discrete event systems in Dioids," Proc. International Workshop on Discrete Event Systems, 2002. [96] G. Cohen, S. Gaubert, and J.-P. Quadrat, "Max-plus algebra and system theory: where we are and where to go now," Proc. IFAC Conference on System Structure and Control, France, July 1998. [97] S. Lahaye, J.-L. Boimond, and L . Hardouin, "Optimal control of (min,+) linear time-varying systems," Proc. International Workshop on Petri Nets and Performance Models, Washington, D . C , 1999. 143 [98] L . Cohen, "Time-frequency distributions - a review," Proceedings of the IEEE, vol. 77 (7), pp. 941-981, July 1998. [99] H . D'Angelo, Linear Time-varying Systems: Analysis and Synthesis, A l l y n and Bacon INC., 1970. [100]L. L . Peterson and B . S. Davie, Computer Networks, A Systems Approach, 2nd edition, Morgan Kaufmann Publishers, 2000. [101] I. Stojmenovic, Handbook of Wireless Networks and Mobile Computing, John Wiley and Sons, 2002.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A min-plus system theory approach for performance evaluation...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A min-plus system theory approach for performance evaluation and quality-of-service provisioning in wireless… Agharebparast, Farshid 2007
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | A min-plus system theory approach for performance evaluation and quality-of-service provisioning in wireless data networks |
Creator |
Agharebparast, Farshid |
Publisher | University of British Columbia |
Date Issued | 2007 |
Description | Recent advances in various wireless data networking technologies and their successful implementations have put the dream of ubiquitous high-quality multimedia communications within our reach. However, achieving reasonable service quality is still a main challenge. It is necessary to evaluate the performance of a new or functional network and to study its service quality factors, such as delay and throughput. This thesis proposes and evaluates a set of analytical techniques based on the modern min-plus system theory that collectively presents an effective methodology for modeling, performance evaluation and quality of service (QoS) provisioning in wireless networks. Min-plus system theory is a successful alternative and complement to queuing theory, whose application in deterministic QoS guarantees is known as Network Calculus (NC) or (σ, ρ)-calculus. The contributions of this work can be grouped under three main categories: slope domain modeling, stochastic min-plus system theorems and their applications in wireless networking, and filter-bank-based wireless channel models. Slope domain modeling is a useful technique whose role in min-plus theory is similar in concept to that of the Fourier domain in traditional system theory. It facilitates analysis of communications networks, and for certain problems is the only viable solution. This method is used in numerous applications, such as system identification, optimal smoothing and priority scheduling. This thesis proposes a stochastic min-plus system theory approach that is used as a practical and efficient methodology for QoS performance evaluations in wireless networks, when the service can be defined by its second-order statistics. The method is then used in optimal traffic shaping and resource allocation for transmission over wireless fading channels. Finally, the concept of load spectrum is introduced as the slope domain representation of this stochastic minplus theory. As an alternative method, a wireless link model based on the filter banks of NC elements is introduced. The model employs modular concatenations of selected NC components to represent the effect of a wireless link on the statistical QoS performance at the link layer. This technique is used in optimal smoothing to successfully solve the problem of playback delay and buffer size calculations for multimedia streaming via a wireless network. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-02-11 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0100601 |
URI | http://hdl.handle.net/2429/31201 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2007-317242.pdf [ 12.45MB ]
- Metadata
- JSON: 831-1.0100601.json
- JSON-LD: 831-1.0100601-ld.json
- RDF/XML (Pretty): 831-1.0100601-rdf.xml
- RDF/JSON: 831-1.0100601-rdf.json
- Turtle: 831-1.0100601-turtle.txt
- N-Triples: 831-1.0100601-rdf-ntriples.txt
- Original Record: 831-1.0100601-source.json
- Full Text
- 831-1.0100601-fulltext.txt
- Citation
- 831-1.0100601.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0100601/manifest