Utility-based Resource and QoS Optimization in Packet Networks by Amr Mahmoud Mohamed B.Sc , Cairo University, 1993 M . S c , University Of British Columbia, 2001 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 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 August 2006 © Amr Mahmoud Mohamed, 2006 11 Abstract Resource Allocation (RA) is used to organize the usage of network's physical resources in such a way that guarantees optimal utilization while providing predictive performance to network flows in terms of inter-flow fairness and guaranteed Quality of Service (QoS). One approach to provide RA which is particularly suitable for traffic flows with relaxed QoS requirements (i.e. elastic traffic) is the Utility-based Resource Allocation (URA). URA assigns a utility function to each individual user flow to measure the degree of satisfaction of this user as a result of assigning a specific share of resources. The objective of the URA techniques is then to partition the network resources to take full advantage of them in satisfying the QoS requirements of each user flow while providing fair allocation of resource among users by maximizing the aggregate utility of all flows. The objective of this thesis is to devise new methods for URA in wired and wireless networks to provide fair resource sharing and predictive flow performance in terms of QoS while guaranteeing best resource utilization. In so doing, we propose a comprehensive set of algorithms that can be used to provide resource optimization both on the link level or on the network level. On the link level, the thesis proposes a group of algorithms for calculating the optimal Abstract iii classification for a set of traffic flows with diverse QoS requirements to a link with prede-termined service levels or predetermined class weights. These algorithms can be used to efficiently study the effect of selecting service levels or class weights according to the dis-tribution of the QoS requirements of the incoming traffic flows. For links with adjustable service levels, we propose two algorithms ( O Q P , and O Q P - O B A ) that calculate the optimal partitioning of traffic flows, the best service levels, and the optimal bandwidth allocation to minimize the quantization overhead as a result of QoS-based partitioning. Our simulation results for both link models show that using 4 or 5 service levels will achieve the trade-off between complexity and service level granularity irrespective of the QoS distributions. These algorithms indeed provide major enhancements in that fairly unexplored area. On the network level, a key contribution of this thesis is the development of a new decentralized algorithm ( O R A W M ) for resource optimization over multihop wireless networks. The algorithm is used to control the rates of the end-to-end sessions utilizing the bandwidth-efficiency feature of multicast to provide resource optimization in a to-tally distributed network environment without any synchronization requirements between network node calculations. Through analytical modeling and simulations, we prove the convergence of the asynchronous algorithm under slow network changing conditions such as channel capacity and node mobility. We also devise a detailed network architecture and discuss the protocol implementation for deploying O R A W M in an ad hoc network. We also extend our solution to include multicast sessions with heterogeneous receivers Abstract iv ( O R A H W M ) and discuss the modified network architecture to support multirate mul-ticast trees. The results show that O R A H W M not only provides flexibility in allocating resources across multicast sessions, but it also increases the aggregate system utility and improves the overall system throughput by almost 30% compared to homogeneous mul-ticasting ( O R A W M ) . We also provide a comprehensive set of simulations that show the effect of deploying these algorithms on the overall resource utilization in an ad hoc network with different environment settings and dynamic network changes (e.g. mobility and route changes). V Contents Abstract ii Contents v List of Tables List of Figures x i i List of Abbreviations xvii Dedication xix Acknowledgements xx 1 Introduction 1 1.1 Motivation 1 1.2 Network Resource Allocation 2 1.2.1 Elastic versus non-elastic network traffic 3 1.2.2 Resource provisioning for non-elastic traffic 4 1.2.3 Utility-based Resource Allocation for elastic traffic 5 Contents vi 1.2.4 Per-hop versus end-to-end resource allocation 6 1.3 The Thesis 8 1.3.1 Objectives _ 8 1.4 Contributions 8 1.5 Thesis Methodology and Road Map 9 1.6 Summary • 10 2 Resource Allocation in W i r e d and Wireless Networks 11 2.1 Introduction 11 2.2 Per-hop resource allocation in wired networks 12 2.3 End-to-end resource allocation in multi-hop networks 13 2.3.1 End-to-end resource allocation in wired networks 15 2.3.2 End-to-end resource allocation in multihop wireless networks . . . 16 2.4 Summary 18 3 Opt imal QoS-based Classification for Multi-class L ink Models . . . . 19 3.1 Introduction 19 3.2 Model and problem formulation 23 3.2.1 Model 23 3.2.2 Optimization Problem 27 3.2.3 Proportional Differentiation Model (PDM) 28 3.3 Optimal solution for fixed set of service levels and soft QoS requirements 30 Contents vii 3.4 Optimal solution in the context of admission control (hard QoS Require-ments) 31 3.5 Service differentiation based on class weights 34 3.6 Service differentiation based on class weights, and limited link capacity . 39 3.7 Optimal classification for stochastic QoS 40 3.8 Experimental Evaluation 42 3.8.1 Results for deterministic QoS 43 3.8.2 Results for stochastic QoS 48 3.9 Concluding Remarks 52 4 QoS-Based Partitioning and Resource Allocation 54 4.1 Introduction 54 4.2 Model and problem formulation 56 4.2.1 Model and notations 56 4.2.2 Optimization problem 58 4.3 Optimal solution for QoS-based partitioning 61 4.4 Optimal QoS-based partitioning with optimal bandwidth allocation (OQP-OBA) 66 4.5 Experimental evaluation 68 4.6 Concluding Remarks 72 5 Opt imal Resource Allocation for Homogeneous Wireless Multicast . 74 Contents viii 5.1 Introduction 75 5.2 Model and problem formulation 78 5.2.1 Model and Notations 79 5.2.2 Mathematical Formulation 84 5.3 Solution Approach 88 5.3.1 The Dual Problem 88 5.3.2 Interpretation of prices 90 5.4 Optimal resource allocation for wireless multicast (OR.AWM) 92 5.4.1 Group price calculation 94 5.4.2 ORAWM: Synchronous Distributed algorithm (ORAWMJ3D) . . 97 5.4.3 ORAWM: Asynchronous Distributed algorithm (ORAWM.AD) . 99 5.4.4 Time-varying environment 104 5.5 Experimental Evaluation 105 5.5.1 Implementations overview 105 5.5.2 Solution architecture and deployment 107 5.5.3 Simulation results 112 5.6 Concluding Remarks 125 6 Optimal Resource Allocation for Heterogeneous Wireless Multicast . 127 6.1 Introduction 127 6.2 Model and problem formulation 130 6.2.1 Model and notations 130 Contents ix 6.2.2 Mathematical Formulation 133 6.3 Solution approach 135 6.3.1 Interpretation of prices 136 6.3.2 Aggregated subtree price calculation 137 6.4 Optimal Resource Allocation for Heterogeneous Wireless Multicast (ORAHWM) 138 6.4.1 Simulation results 141 6.5 Related Work 149 6.6 Concluding Remarks 153 7 Conclusions and Future Research 155 7.1 Summary 155 7.2 Future Work 157 Bibliography 160 A QoS-Based Partitioning and Resource Allocation 172 A . l Proofs for Chapter 3 172 A.1.1. Lemma 3.1 172 A. 1.2 Lemma 3.2 174 A. 1.3 Lemma 3.3 174 A.1.4 Theorem 3.1 175 A. 1.5 Theorem 3.2 176 Contents x A. 2 Proofs for Chapter 4 177 A.2.1 Lemma 4.1 177 A.2.2 Theorem 4.1 178 B Resource Allocation for Wireless Multicast: Convergence Analysis . 180 B. l Proof of Theorem 5.2 180 B.2 Proof of Theorem 5.3 183 x i List of Tables 5.1 M A C and physical layer parameters used by our simulations 107 5.2 Multicast traffic pattern : 123 xii List of Figures 3.1 Link Model 23 3.2 QoS-based classification 28 3.3 Optimal QoS-based classification with fixed service levels (OQC-FSL). . . 32 3.4 OQC-FSL with arbitrary tolerance factors (OQC-FSL-ATF) 33 3.5 The effect of 7 on \I> for 3 Q[s and one uij 37 3.6 Differentiation factor 7 for minimum * 37 3.7 Differentiation factor 7 for minimum 'IP{TT*L) 38 3.8 OQC for predetermined class weights and limited link capacity ( O Q C -P C W ) 40 3.9 Example of a QoS probability density function 42 3.10 Variable sized sets for different number of service levels, W={10 1,10 2,..,10 8 }. 43 3.11 Variable sized sets for different number of service levels, W = {2~1,2~2,.., 2 - 8 }. 45 3.12 Variable load for different number of service levels, N=500, W= {2" 1 ,2- 2 , ..,2- 8}. 45 List of Figures xiii 3.13 Variable sized sets for 7 estimation methods, uniformly distributed QoS. 46 3.14 Effect of tolerance factor for different link loads, uniformly distributed QoS, using O Q C - F S L - A T F algorithm. . 47 3.15 Effect of tolerance factor for variable-sized sets, uniformly distributed QoS, using the O Q C - P C W algorithm 48 3.16 Effect of K for different number of service levels, uniform QoS distribution. 49 3.17 Effect of K for different number of service levels, for 4-cluster QoS distri-bution 50 3.18 Effect of total,load, for different number of service levels, for 2-cluster QoS distribution for N=200 50 3.19 Effect of 7 estimation methods for 2-cluster distribution using 5 service levels 51 3.20 Effect of tolerance factor for different link load, for 2-cluster QoS distrib-ution using 5 service levels 51 3.21 Effect of tolerance factor for variable-sized sets, for 4-cluster QoS distrib-ution 52 4.1 QoS-based partitioning model 57 4.2 QoS-based partitioning 58 4.3 Example of a piecewise concave function 63 4.4 Algorithm optimal QoS-based partitioning (OQP) 65 4.5 Algorithm OQP with optimal bandwidth allocation ( O Q P - O B A ) . . . . 67 List of Figures xiv 4.6 Difference between arbitrary and optimal partitioning 69 4.7 Variable sized sets for 5 service levels 70 4.8 Effect of link load for different partitioning and bandwidth allocation schemes 71 4.9 Number of service levels for different QoS distributions 72 4.10 Number of service levels for different QoS distributions 73 5.1 Wireless ad hoc network model 80 5.2 Example for resource allocation in unicast and multicast 85 5.3 Example for calculating the multicast group price 92 5.4 ORAWM: Synchronous Distributed algorithm 98 5.5 ORAWM: Asynchronous distributed algorithm 103 5.6 Simulation environments 106 5.7 Cross-layer architecture for O R A W M 108 5.8 Multicast-aware MAC protocol 109 5.9 Price and rate control packets I l l 5.10 Convergence for different simulation environments using fixed channel ca-pacity 114 5.11 Convergence for different simulation environments using dynamic channel capacity 115 5.12 Effect of step size a on convergence using the O R A W M _ F D A implemen-tation 116 List of Figures xv 5.13 Effect of estimation window B on convergence using the O R A W M _ F D A implementation 118 5.14 Convergence with different differentiation gains and start/stop times. . . 120 5.15 Impact of mobility and route changes 120 5.16 Convergence with mobility and route changes 121 5.17 Random wireless network with 30 nodes 123 5.18 Impact of mobility and route changes on convergence of O R A W M . . . . 124 5.19 Aggregated utility and packet overhead for eight random networks each with 30 nodes 126 6.1 Multirate multicast network model 131 6.2 Example for resource allocation in unirate and multirate multicast. . . . 133 6.3 ORAHWM: Asynchronous distributed algorithm 140 6.4 Effect of changing differentiation gains on the calculated rates and aggre-gate utility 142 6.5 Effect of changing differentiation gains on the calculated rates and aggre-gate utility 143 6.6 Calculated rates with dynamic capacity: gVu = 4,gVl4 = l,gV2A =5. . . . 146 6.7 Calculated rates with mobility: gVu = 4,g V l 4 = l,gV24 = 5 146 6.8 Multirate multicast network topology 147 6.9 Case 1 (unirate): calculated rate and throughput without using gateway node vu 147 List of Figures xvi 6.10 Case 2(multirate): calculated rate and throughput using gateway node vu for rate control on m\ 148 6.11 Aggregate utilities for Cases 1 (unirate) and 2 (multirate) 150 6.12 Total throughput for each multicast group for Cases 1 and 2: th\ is total throughput for m : 1 and thi is total throughput for m2 150 List of Abbreviations ACK Acknowledgment AODV Ad hoc On demand Distance Vector ATF Arbitrary Tolerance Factor BFE Brute Force Enumeration DCF Distributed Coordination Function Diffserv Differentiated Services DP Dropping Probability EMH Extended Multicast Header FCW Fixed Class Weights FSL Fixed Service Levels. GMPLS Generalized MPLS IP Internet Protocol LSR Label Switched Routers MAC Medium Access Control MAODV Multicast AODV MCQO Minimum Class Quantization Overhead List of Abbreviations xviii MMP Multicast aware MAC Protocol MPLS Multi-Protocol Label Switching NS Network Simulator OBA Optimal Bandwidth Allocation OQC Optimal QoS-based Classification OQP Optimal QoS-based Partitioning ORAHWM Optimal Resource Allocation for Heterogeneous Wireless Multicast ORAWM Optimal Resource Allocation for Wireless Multicast PCW Predetermined Class Weights PDF Probability Density Function PDM Proportional Differentiation Model QoS Quality of Service RA Resource Allocation SL Service Level SLA Service Level Agreement SP Service Provider SRP Statistical Resource Provisioning TCP Transmission Control Protocol UDP User Datagram Protocol URA Utility-based Resource Allocation VPN Virtual Private Network xix Dedication v _ U A To my beloved parents. X X Acknowledgements First and foremost, All praise be to Allah, for his countless blessings and guidance. I would like to express my profound gratitude and appreciation to my supervisor, Dr. Hussein Alnuweiri, for his guidance, technical advice, invaluable feedback, understanding, generous support, and friendship. I would like to thank Dr. Vikram Krishnamurthy and Dr. Rabab Ward for funding my research at some points during the program. I would like to express my appreciation to my thesis committee for their valuable comments which enhanced the-presentation of this thesis. I am very grateful to Dr. Fayez Gebali from University of Victoria for his valuable discussions regarding the work of QoS partitioning. I would like to express my sincere thanks to my friend Dr. Watheq El-Kharashi for carefully reviewing my thesis. His valuable comments and suggestions have been very useful in enhancing the presentation of this thesis. I would like to thank Dr. Yuan Xue from Vanderbilt University for her great help and support throughout the work of resource allocation in wireless multicast and providing the code for the NS implementation which was the starting point of my multicast-based Acknowledgements xxi resource allocation for ad hoc networks. I have been blessed to come in contact with many wonderful people throughout my study period at UBC. This page is definitely not enough to mention all of them, but, the least I can say to them is: thank you for making my stay at UBC such a pleasant experience. Among the many friends that I had during my study period, the following friends had the most positive effect on my life: Ahmed, Anwar, Ayman, AmrW, MohamedA, Khaled, Tamer, Watheq, Abdo, Junaid, Tariq, Maged, and Awad. Words cannot describe my feelings toward my parents. I can only pray to God to reward them for their constant support, and persistent encouragement. I would like to express my love and deep appreciation to the person who stood beside me through all times, my wife Marwa. She was always there for me with comforting words, encouraging thoughts, and a tranquil smile. I would like to extend my thanks to my brother Mohamed, for being a source of motivation and prayers. I would like also to thank my in-law's for all their prayers, encouragement, and sup-port. Last, but not least, I would like to thank my daughters, Sara and Yomna, for all the joy and happiness they have brought to my life. 1 Chapter 1 Introduction 1.1 M o t i v a t i o n The rapid growth of customer demands for fast, reliable, and differentiated network ser-vices will always go hand in hand with inventing new network infrastructure technologies. On the other hand, service providers (SPs) are striving, not only to fulfill user's demands but also to accommodate more users in order to reduce the service cost without affecting the service quality. This major trade-off has mandated the use of optimization techniques to increase network resource utilization while providing heterogeneous QoS for various types of customer applications. Problems such as guaranteed QoS or providing differentiated services have proved to be complex to implement on a wide scale despite the great deal of effort that has been dedicated to this subject. Without proper long-term network capacity planning and dynamic mechanisms for allocating and sharing network resources, providing QoS can be an expensive and unsuccessful exercise for network service providers. In recent years, it has become obvious that there is a need for a new paradigm that takes into consideration network wide topology and bandwidth resources to enable SPs to optimize their resource Chapter 1. Introduction 2 utilization, while maintaining the promised levels of service to customer flows. Proper dynamic resource allocation mechanisms will not only allow SPs to take best advantage of their existing network resources, but will also avoid unreasonable network upgrades as a first choice to respond to ever growing customer demands. Therefore, resource provisioning techniques must be designed to satisfy two primary objectives. The first objective is to satisfy the performance requirements for each customers flow. The second objective is to maximize the overall resource utilization efficiency of the network which in turn impacts the total revenue derived by the SP. 1.2 N e t w o r k R e s o u r c e A l l o c a t i o n Network resource allocation refers to the ability of the network to self organize the usage of its physical resources (e.g. bandwidth, buffer space, computation resources, etc.) in such a way that guarantees optimal utilization of these resources while providing predictive performance to individual network flows in terms of inter-flow fairness and guaranteed QoS. Resource Allocation (RA) can be a powerful tool for exploiting the trade-off between traffic performance from the user side and resource utilization from the network side. From the user side, the job of RA is to provide QoS guarantees such as bandwidth, delay, delay jitter, packet loss etc. From the network side, RA optimizes utilization of network resources to support maximum traffic throughput while providing the required level of QoS. Chapter 1. Introduction 3 In packet networks, information is incorporated into the Internet Protocol (IP) pack-ets, and transmitted from one source to one or more destinations in the form of network flows, or often called sessions. One of the most significant and basic network functions is to provide fair share of the network resources to the greatest number of these flows, while efficiently utilizing the resources and guaranteeing an acceptable level of service for each flow. One aspect of achieving this task is to assign individual rates to network flows so that they are able to share the network resources in a fair manner. Without fair allocation, some flows may take over the major part of the network resources while others suffer long network delays or significant data loss. Another important aspect of RA is the repartitioning of network resources to accommodate the flow rates at each network hop and hence guarantee the best resource utilization. Without doing that, some parts of the network may become congested while others may become under utilized, which is highly uneconomic. 1.2.1 Elastic versus non-elastic network traffic Elastic network traffic [1, 2] usually refers to the network traffic that carries digital objects which can be transmitted using a wide range of QoS requirements without affecting the transmission quality. Digital objects such as files, web pages, video clips, or even layered video streams [3, 4] can be transmitted using several possible rates or different QoS levels depending on the limit imposed by the system capacity. In other words, elastic data transmission adapts to available bandwidth via, possibly, feedback control from the Chapter 1. Introduction 4 network such as in the widely used Transmission Control Protocol (TCP). Non-elastic traffic (e.g. real time voice or video streams) typically supports hard QoS requirements which must be met by the network in order for this traffic to be admitted. Therefore, it is frequently assumed that elastic traffic has more tolerant QoS requirements compared with non-elastic traffic. The QoS requirements (e.g. delay, or loss bounds) for both of these types of traffic could be either deterministic or statistical. For example, deterministic delay requirements specify the bound on the absolute end-to-end delay for each packet (or over a very short period) while statistical delay requirements specify the end-to-end delay bound over a long period possibly with some probability of delay violation. 1.2.2 Resource provisioning for non-elastic traffic One approach to achieve the compromise between user requirements and network resource utilization which is particularly suitable for non-elastic traffic is the resource provisioning. In this approach, the network resources are partitioned between the individual user flows so as to satisfy the following two objectives: • The individual QoS requirements for each flow must be satisfied. • The number of user flows admitted to the network over the long term is maximized. These two objectives are often conflicting and in some cases it is hard to provide QoS guarantees without over-provisioning, network resources for individual flows, which is the Chapter 1. Introduction 5 main cause of resource under-utilization. Therefore, provisioning techniques frequently opt to provide statistical QoS guarantees [5]. 1.2.3 Utility-based Resource Allocation for elastic traffic One of the most common and efficient methods for modeling the R A problems in packet networks is the concept of Utility-based Resource Allocation (URA) for elastic traffic [1, 6, 7]. In this scheme, each network user is assigned a utility function that abstracts the user requirements and measures the degree of satisfaction as a result of assigning a specific share of resources to that user or sometimes it measures the amount of penalty if this user's QoS requirements are not met. In this case the objectives of partitioning network resources are: • Each network flow acquires a fair share of the network resources that satisfies its QoS requirements to the best degree possible. • The overall network resource utilization is maximized. In order to achieve this compromise between fairness and resource utilization, U R A techniques are often mapped into an optimization framework that incorporates the user utilities as part of the problem objective. The goal then is to maximize the aggregate utility of all users subject to a set of constraints derived by the limitation of network resources. Although, it may not be crucial that optimality is exactly attained in real networks, largely due to excessive complexity, the optimization framework offers a means to always Chapter 1. Introduction 6 steer the network towards a desirable operating point that achieves the trade off between fairness and utilization. Also, mapping the U R A problem into an optimization framework has the advantage of leveraging many efficient optimization techniques that can be used to devise and improve solutions that are suitable for distributed computations and can efficiently track network changing conditions in real time. 1.2.4 Per-hop versus end-to-end resource allocation The resource provisioning and the utility-based resource allocation schemes can address the problem of resource utilization from two levels. First, at the link level, the focus is on providing deterministic/statistical per-hop QoS guarantees for the incoming flows using the proper partitioning of link resources and scheduling flow packets in order to achieve the compromise between fairness and utilization [5, 8, 9]. The notion of end-to-end QoS guarantees is usually not addressed by these techniques. Therefore, resource allocation among per-hop flows may not be suitable for multi-hop flows where packets of the same flow are transmitted across more than one hop . This is due to the unawareness of network-wide bottlenecks and lack of coordination among different hops of the same flow. Second, at the path level, R A techniques focus on partitioning the resources of the entire network in order to provide end-to-end QoS while guaranteeing optimal resource utilization. The proposed solutions in the literature [6, 10, 11] normally use flow control paradigms to perform real-time adjustment on the sending characteristics of the end-to-end flow using feedback from the network. Chapter 1. Introduction 7 In this thesis, we focus on the analysis and design of utility-based resource alloca-tion techniques that can achieve optimal resource allocation both at the link (per-hop) level and at the path (end-to-end) level. We propose a comprehensive set of resource allocation algorithms that provide efficient partitioning of system resources, QoS-based classification of flows to these resources, and system-wide fairness for elastic network traffic. Details of the problems, and our proposed solutions will be presented in later chapters. At the link level, we focus on partitioning the link resources for a group of flows to obtain the optimal resource utilization while providing per-hop service granu-larity. This objective is reasonable for wired networks, especially for an accumulative QoS metric (e.g. dropping probability) since providing service granularity for one-hop flows will help meet the end-to-end QoS requirements. On the other hand, for multihop wireless networks, achieving certain criteria like fairness among single-hop flows may not be optimal for multi-hop flows, due to the challenging features including unpredictable channel behavior, location based contention, mobility, and route changes. Therefore, for multi-hop wireless networks, we focus on allocating rates (QoS metric) across the entire network to achieve optimal utilization while providing fairness to the end-to-end flows. Chapter 1. Introduction 8 1.3 T h e T h e s i s 1.3.1 Objectives The main objective of this thesis is to develop new methods for resource allocation in wired and wireless networks that provide fair resource sharing and predictive flow per-formance while guaranteeing best resource utilization. 1.4 C o n t r i b u t i o n s The contributions of this thesis can be highlighted as follows: • Proposal of a new set of algorithms for QoS-based classification for multi-class link models. Our algorithms, based on dynamic programming, will be explained in Chapter 3. This work is published or to be published in [12] [13] [14] . • Proposal of a new set of algorithms for QoS-based partitioning of link resources to provide resource allocation. Our algorithms will be explained in Chapter 4. This work is published or to be published in [17]. • Development of a new decentralized algorithm for end-to-end resource allocation in homogeneous wireless multicast-aware ad hoc networks. Our algorithm ( O R A W M ) and a detailed optimization model based on gradient projection, and distributed computation methods will be explained in Chapter 5. This work is published or to be published in [18] [19] [20]. Chapter 1. Introduction 9 • Design of a cross layer framework that realizes the problem of end-to-end resource allocation in wireless multicast. This framework utilizes a measurement-based tech-nique for wireless channel capacity estimation and a light-weight network H E L L O protocol for constructing contention domains. Our framework will also be explained in Chapter 5. This work is published or to be published in [21] [20]. • Development of a new decentralized algorithm for end-to-end resource allocation in heterogeneous wireless multicast-aware ad hoc networks. Our decentralized algo-rithm ( O R A H W M ) and a detailed optimization framework will be explained in Chapter 6. This work is published or to be published in [22] . 1.5 Thesis Methodology and Road Map For each of the contributions listed above, we devise a framework that realizes the re-source allocation problem as a non-linear optimization model, and we provide the analysis and the optimal solution using one of the most efficient and suitable techniques for opti-mizing the objective in this case. We also devise heuristic techniques that can be used to approximate the solution and provide analytical and simulation studies to compare these heuristic solutions with the optimal one. The rest of the thesis is organized as follows: Chapter 2 covers the literature review and provides an overview about the resource allocation techniques in wired and wireless networks. Chapter 1. Introduction 10 Chapter 3 proposes a set of algorithms for QoS-based classification for link models with a limited number of classes of service. Chapter 4 proposes the algorithms for QoS-based partitioning and bandwidth alloca-tion for link models with adjustable service levels. Chapter 5 provides a comprehensive solution for optimal resource allocation for ho-mogeneous wireless multicast ( O R A W M ) which is based on distributed computations, and iterative techniques. Chapter 6 provides the solution for optimal resource allocation for heterogeneous wireless multicast ( O R A H W M ) . Chapter 7 concludes this thesis and outlines future research directions. 1.6 S u m m a r y This chapter has covered an introduction to resource allocation in packet networks, and highlighted two solution scenarios for achieving the trade-off between providing QoS guarantees and attaining the best resource utilization, namely: resource provisioning for non-elastic traffic, and utility-based resource allocation for elastic traffic. It has also highlighted the main differences between elastic, and non-elastic traffic, and per-hop versus end-to-end QoS guarantees in developing resource allocation techniques in packet networks. The last sections of the chapter have covered objectives, contributions, methodology and road map for this thesis. 11 Chapter 2 Resource Allocation in Wired and Wireless Networks 2.1 I n t r o d u c t i o n In today's networks one of the main goals of a service provider is to satisfy their customer demands while using network resources efficiently. Some customer applications with hard QoS requirements require sophisticated QoS provisioning techniques to partition network resources in order to provide hard QoS guarantees for such applications. In some cases, the provisioning technique may have to over-estimate the amount of resources allocated to each customer flow to provide guaranteed QoS, which might lead to under-utilization of network resources. Other customer applications with relaxed QoS requirements require resource allocation techniques that guarantee different notions of fairness (e.g. propor-tional fairness, maxmin fairness [24-26]) among customer flows and maximize network resource utilization. Chapter 2. Resource Allocation in Wired and Wireless Networks 12 2.2 Per-hop resource allocation in wired networks Several techniques have been proposed in the area of providing per-hop resource allocation for wired networks using scheduling and bandwidth sharing mechanisms [23, 27-30]. Some of these techniques have focused on providing per-flow QoS guarantees while using the link capacity as a continuous set of rates that can be allocated freely to different flows [31]. These techniques adopt different policies for allocating link capacity into different flows so that the overall link utilization is maximized. Several other techniques provide differentiated services for aggregated flows on a single link that has a discrete set of predetermined QoS service levels [32-34]. The idea of the DiffServ architecture [35] is to provide a scalable solution to the problem of service differentiation by maintaining the state of only the aggregates of flows. However, the DiffServ architecture and techniques do not provide answers as to what are the best set of QoS service levels supported on each link that can achieve maximum resource utilization. Determining the number and the nature of service levels that each link can support are important issues that can lead to enhancing the link utilization. Increasing the number of QoS Service levels on each link will increase the overhead of flow management and classification while maintaining a small number of service levels may lead to waste of link resources. Also certain applications may inherently restrict the aggregation of traffic flows and therefore require special per-flow guarantees using a limited set of link service levels [8, 36, 37]. For example, multicast flows and some secured (e.g. VPN flows) trunks may impose some aggregation challenges at different parts of the network. For this type of flows, selecting the discrete set of service Chapter 2: Resource Allocation in Wired and Wireless Networks 13 levels supported by the link is a crucial issue for enhancing the link's resource utilization. This is because assigning a service level that provides better QoS than the one required by the flow will lead to waste of resources while, assigning a service level with worse QoS may not be accepted by the flow or the service agreement with the customer. Although per-hop resource allocation techniques have wide acceptance and they are wide spread across many of today's networks, they lack the concept of optimizing the en-tire network resources for multihop flows. This is because fairness of allocating resources among flows on one hop may not achieve overall fairness across multihop flows. 2 . 3 E n d - t o - e n d r e s o u r c e a l l o c a t i o n i n m u l t i - h o p n e t w o r k s End-to-end resource allocation techniques are designed to achieve global optimal resource utilization for the entire network while providing system-wide fairness among the incom-ing flows. Most of these techniques use flow control, sometimes combined with topology-aware congestion mechanisms, to perform real-time adjustment on the sending character-istics (e.g. sending rate) of the end-to-end flow. The purpose of flow control is to regulate the admission of traffic into the network in order to minimize network overload, without excessively restraining sessions when the network is not overloaded. Flow control tech-niques are usually divided into two categories, namely: window-based, and rate-based flow control. Chapter 2. Resource Allocation in Wired and Wireless Networks 14 Window-based flow control techniques [38, 39] use a limit on the maximum number of unacknowledged packets submitted to the network at any given time (the window size). They rely mainly on the time taken by the per-packet acknowledgment to be fed back to the source in estimating the congestion state of the network, and hence they use that time in controlling the sending rate of the flow source. If the network is highly congested, acknowledgments will take a longer time to reach the source and that will trigger the source to slow down by reducing its sending rate. While these techniques are intuitively simple to implement, they usually lack the coordination between the competing flows and therefore they provide poor inter-flow fairness. Besides, without using a network resource assignment scheme, window-based techniques do not provide deterministic guarantees neither on the network resource utilization nor on the end-to-end QoS of each flow. Rate-based flow control techniques on the other hand, use a combination of rate ad-justment and resource assignment functions to control the characteristics of the flows. The resource assignment function of the flow control technique divides the available re-sources (e.g. link or channel capacity) amongst flows to ensure that the QoS requested by each flow is fulfilled and resource utilization is maximized. Of course in that case, net-work topology plays an important role in allocating resources across the entire network. Also to maintain scalability and minimize the coordination between network nodes, the majority of the topology-aware resource assignment mechanisms are based on distrib-uted solutions which reduce the computations performed by each node and enhance the communication overhead. The rate adjustment function controls the sending rate of each Chapter 2. Resource Allocation in Wired and Wireless Networks 15 end-to-end flow based on feedback from the network to guarantee inter-flow fairness. Because of the complexity of achieving global optimal resource utilization and topology awareness, rate-based techniques are normally designed for a special type of network (e.g. optical, wireless, etc.) and for a special type of end-to-end flows (e.g. unicast, multicast flows etc.). 2.3.1 End-to-end resource allocation in wired networks In this class of end-to-end resource allocation techniques, the link between two network nodes represents the main resource entity for which flows at the network router con-tend for resources. Scheduling at each individual link regulates the provisioning of link bandwidth to each flow (i.e. time domain packet multiplexing). The problem of optimal and fair resource allocation has been extensively studied in the context of wired networks for unicast flows. Some techniques focused on providing end-to-end QoS guarantees while maximizing the number of admitted sessions by partitioning the end-to-end QoS requirements of each flow into local QoS on each network link based on the link's loading conditions [40, 41]. Other techniques have focused on providing optimal resource utilization while guaranteeing inter-flow fairness. These techniques adopt a pricing scheme to design a distributed solution for rate allocation for unicast flows [1, 10, 42]. They use a local congestion parameter (the price) to convey the information about the relationship between the capacity on each link and the load demanded by the flows and hence provide a congestion indication for each part of the network. Chapter 2. Resource Allocation in Wired and Wireless Networks 16 While resource allocation for unicast flows focuses on assigning resources to each source-destination pair, multicast flows present more challenge because of the correlation between the source-destination pairs on the same multicast tree. Such correlation requires special treatment especially for the case of multirate multicast [43]. Resource allocation for multicast wired networks has been studied in [44], [45] and [7]. They define the mul-ticast tree between one source and multiple receivers as group of terminal (non-junction) nodes and branch (junction) nodes. Each downstream on a branch node contributes to the load of the link that the downstream traverses. They also associate a utility function to each receiver on a multicast session to reflect the demand for bandwidth for this re-ceiver on each multicast session. The objective then is to find the allocation of resources across the multicast trees such that the aggregate utility of all receivers on all sessions is maximized, taking into consideration the correlation between the source-destination pairs of each multicast tree. 2.3.2 End-to-end resource allocation in multihop wireless networks In this class of end-to-end resource allocation techniques, wireless channel represents the main resource entity for which flows at the network nodes contend. All network nodes within the interference range of each other constitute a cluster of nodes for which only one node can send packet at any given time. Therefore, scheduling techniques for such wireless network regulate the access of the flows to the wireless channel using distributed Chapter 2. Resource Allocation in Wired and Wireless Networks 17 coordination between the interfering nodes both in time and spatial domains. Besides, unpredictable channel behavior caused by impairments, such as channel noise and inter-ference, introduces additional challenge that makes provisioning of channel bandwidth such a difficult job especially for providing QoS guarantees. Resource allocation, using MAC-layer fair scheduling for single-hop flows, has been studied in wireless ad hoc networks [46-48]. Such techniques, however, do not provide end-to-end resource optimization and therefore fairness among the multihop flows cannot be achieved only by local MAC layer scheduling. End-to-end resource allocation tech-niques (e.g. [6, 49-51]) complement such MAC layer scheduling techniques by providing a pricing mechanism that can be used to coordinate the global resource allocation for the case of multihop unicast flows. In this case, a utility is associated to each end-to-end unicast flow, and the objective is to maximize the aggregate utility subject to channel capacity limitations. Global optimality has also been addressed in the context of maxi-mizing the net benefit of each node as a result of relaying traffic for other nodes [52, 53]. There too, a utility is assigned to each user, and the objective is to maximize the aggre-gate profit of all nodes within the network subject to the limited resources of each node. Another context where the problem of global resource allocation has been addressed is the distributed power-based resource allocation [54-58]. In this case, a similar pricing mechanism is used to optimize the signal-to-interference (SIR) ratio using a distributed power control technique. None of these techniques, however, investigated the case of end-to-end multicast flows. Chapter 2. Resource Allocation in Wired and Wireless Networks 18 The one hop broadcast characteristic of the MAC layer in wireless ad hoc networks has prompted the use of multicast communication scheme as one of the natural strategies that can multiply the overall network throughput with very limited overhead. This is because multicast packets are forwarded once to reach all the multicast, members in the neighborhood using a single transmission, and this effect increases even more in multi-hop ad hoc networks. However, historically, multicast flows introduce new challenges for deployment due to its complexity and lack of standards and techniques that can effectively allocate network resources. The challenge in multicast resource allocation is that, not only the resource allocation has to regulate access to channel resources for each source-destination pair, but also it has to correlate different source-destination pairs on the same multicast group. This is crucial for utilizing the bandwidth efficiency of each multicast session (i.e. "intra-flow bandwidth efficiency") and achieving system-wide fairness across all multicast sessions (i.e. inter-flow fairness). 2.4 S u m m a r y This chapter has covered a literature review for resource allocation in wired and wireless networks. First, a survey on single-hop based resource allocation techniques which are designed for wired networks has been presented. Then, the latest techniques for end-to-end resource allocation for multihop networks has then been discussed including the motivation for our multicast resource allocation in multihop wireless ad hoc networks. 19 Chapter 3 Optimal QoS-based Classification for Multi-class Link Models In this chapter, we present a comprehensive set of algorithms for QoS-based classification for a multi-class link model with a small predetermined set of service levels. We present two main algorithms called O Q C - F S L and O Q C - P C W for calculating the optimal QoS-based classification using dropping probability as the QoS metric. We also provide a comparison between these algorithms and two heuristic techniques in calculating the quantization overhead resulting from the classification process. 3 . 1 I n t r o d u c t i o n The proliferation of differentiated services has been one of rising challenges to Internet SPs aiming to deploy cost-effective, large scale networks, supporting diverse applications and services ranging from web browsing to video-on-demand and T V broadcast. On the other hand, differentiated services promote the idea of supporting limited service levels °A version of this chapter has been published [12 14] Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 20 to provide QoS while maintaining the network scalability. This idea has wide range of acceptance by today's applications. However, some emerging applications and services such as TV-over-DSL, virtual private networks (VPNs), overlay networks, and multicast-based QoS networks, may inherently restrict the aggregation of traffic streams in network nodes. Nonetheless, they still require different levels of guarantees at each network node in order to guarantee the end-to-end QoS. Therefore, the problem of satisfying per-flow QoS guarantees in a network environment that supports only a fixed set of service levels and traffic classes has been the subject of extensive research [8, 36, 37]. To provide the required end-to-end QoS, many resource reservation mechanisms have been discussed in the literature and can be used to partition the end-to-end QoS into local QoS requirements on each network element (link) [40, 59, 60]. However, for a network framework that supports a limited set of service levels on each network link, the local QoS required for each connection (or flow) will be quantized based on these service levels. Assigning a service level which provides better QoS than the one required by the connection will lead to waste of network resources while, assigning a service level with worse QoS may not be accepted by the application or the service agreement with the network user. Therefore, an important network optimization problem is how to assign the network connections to the best service level that minimizes the total quantization overhead. Such an overhead is the quantization penalty that might have to be incurred by either the user or the service provider. Hence, addressing this problem will have a large significance especially for high speed links (e.g. optical links) that may potentially Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 2 1 carry large number of connections. In this chapter, we investigate the problem of optimal classification of connection requests into a set of service levels at a network link in order to minimize the penalty caused by QoS quantization. We consider a model where each connection request has a local QoS (e.g. delay, dropping probability, jitter, etc.) in addition to the bandwidth requirements. The link has a set of service levels that are either fixed or defined by a set of predetermined class weights. Each connection request is assigned to one of the link's service levels that best accommodates the connection QoS requirements, such that the total QoS quantization penalty is minimized. In Section 3.2, we define a utility function which will be used to measure the quanti-zation penalty at each service level based on the set of connection requests assigned to that level. We also define a set of conditions on this utility function that will be used by the call admission process to accept or reject new connection requests. We present two categories of efficient (polynomial time) algorithms which can be used for fixed service levels and for predetermined class weights given some realistic assumptions. The problem of obtaining optimal quantized service levels for a set of connection re-quests has been investigated before in [61], [4], and [62]. Rouskas et al. [61] defined a similar framework of assigning MPLS tunnels with specified data rates to a set of quan-tized service levels such that the performance penalty of wasted bandwidth is minimal. Both the deterministic and stochastic connection requests have been discussed. However, the case of having two joint requirements (e.g. Bandwidth, and dropping probability) Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 22 was not discussed. The authors in [4], and [62] considered the problem in a different context where the set of requests are group of receivers on a multicast tree. The target then was to find the small optimal set of offered rates (by the source) that maximizes the correlation between the total required rates requested by the receivers and the offered service levels. The present study offers solutions to the generalized problem where con-nections have both rate and QoS requirements and presents polynomial time algorithms for fixed service levels or predetermined class weights link model for soft and hard QoS requirements. The rest of the chapter is organized as follows. Section 3.2 formulates the model, the problems of QoS classification and relates our framework to QoS network architectures. The optimal solution for-fixed service levels is discussed in Section. 3.3. The optimal solution for admission control is investigated in Section 3.4. Sections 3.5 and 3.6 discuss the case of predetermined class weights and describe how the optimal solutions will be modified in this case. Section 3.8 depicts the results for. applying our solutions to a set of QoS requirements with different distributions. Finally, concluding remarks and future work are described in Section 3.9. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 23 3 . 2 M o d e l a n d p r o b l e m f o r m u l a t i o n 3.2.1 Model We assume a network element, or a link of capacity C that offers a set of service levels SL = {xi,x2, ••••>XL} for L number of classes. Typically, the values of the service levels are limited by the link capacity and dependent on the inherent link model and the characteristics of the input traffic. The l-th level corresponds to a connection with QoS level xi given that the bandwidth demand for this connection is < C. Similarly, we assume a set of ./V connection requests 5ft — { r i , r 2 , ...,r^v}, each defined by a bandwidth demand parameter cU plus one local QoS requirement Qi (e.g. average delay, dropping probability, jitter, etc.). Therefore, each connection request can be represented by a pair, viz. = {di,Qi} as shown in Figure 3.1. (IBIBBl service classes 1,..,L • traffic flows 1....N F i g u r e 3.1: Link Model. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 24 It is important to note the difference between parameters Xi and Qi. Essentially, Xi is the actual QoS achieved at service class 1, while Qi is the original (or absolute) QoS requirement of connection r, = {di,Qj}. The classification process assigns connections from the set 3ft = {r'i,?'2, ...,r/v} to service levels from the set Si = {xi,X2, •••,££,} using mapping functions that will be explained in the next section. As a result of the assignment process, a connection request may be assigned to a service class that provides the exact required QoS, inferior QoS, or better QoS to the connection. Unless otherwise stated, for the remaining of this chapter, if xi < Q,, this means connection i is assigned a better QoS (note that this will not be true if Q,;'s represent bandwidth or throughput for example). The difference between the absolute QoS and the achieved QoS, is tin important measure that will be used to evaluate different QoS classification schemes. In the following, we develop the definition of a utility function, U(Qt,xi), which measures the difference between the achieved and required (or absolute) QoS. It is important to note that providing xi lower than Qi (i.e. providing better QoS) will result in a waste of allocated resources whereas increasing xi over Qi may have a disadvantage for the application generating the traffic stream. Therefore, we will consider the general case where U(Qi,xi) measures the penalty in both scenarios (different from the one defined in [61]). The following are some common examples from the literature. The absolute difference tf(Qi,a;«) = | Q i - Z i | (3.1) Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 25 The least square U[Qux{) = {Qi-x{f (3.2) The logarithmic difference U(Quxi) = log(l + | Q i - . T ( | ) (3.3) We consider a subset of the possible classification policies where the connection re-quests are sorted based on the local QoS requirements in non-decreasing order, (i.e. Q i < Q-2 < Qs < QN)- This is called ordered classification. Definitions Ordered Classification: A group set TTL = { G I , . . , G L } is an ordered classification if Wi G Gaand Wj G Gj,, Q i < Q j , when a < b. Utility Property: Intuitively, the utility function is non-increasing in the interval Q i € [0,xi\ and it is non-decreasing in the intervalQi G [x;,oo[. In other words, the utility property can be defined using the following inequalities: 1. Vx,i = l,..,N j = l,..,L iiQt<Qj<x then U{Qux) > U(Qjtx) l f x < Q i < Q j then U{Ql,x) < U(Q,,x) 2. V Q , i = l,..,N j = 1,..,L if X i < X j < Q then U(Q,Xi) > U(Q,Xj) if Q < X i < X j then U(Q,Xi) < U(Q,Xj) Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 26 The importance of the last two definitions lies in the fact that if we choose a utility function that fulfills the utility property we only need to consider the ordered classifi-cations when we search for an optimal solution. This result is stated formally in the following fundamental lemma. Lemma 3 .1 . For any utility function U(Qi}xi) that satisfies the utility property, even with predetermined service levels, there always exists a classification n*L that is optimal and ordered. Proof. Given in Appendix A • In Section 3.5, we will impose one more restriction on the utility function which will lead to an elegant solution for the case of predetermined class weights. Lemma 3.1 is important because it limits the number of possible solutions for opti-mality, making the problem much more tractable. The following lemma highlights this fact and gives a deterministic value to the number of possible solutions for the ordered classification problem. Lemma 3.2. Brute Force Enumeration (BFE) of input streams using the ordered classi-fication policy will lead to a number of possible solutions in the order of 0(NL~l) where N is the number of traffic streams and L is the number of service levels. Proof. Given in Appendix A • Although, the lemma indicates that BFE for the input traffic streams will lead to an algorithm with exponential running time in L , we can argue that typical values for L are Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 27 normally small and the B F E method wi l l in fact lead to a polynomial-time solution for a fixed value of L. In the following sections, we wi l l show that the recommended value for L is, remarkably, small and in the range of 3 to 5 classes. We wil l also present our solutions which achieve polynomial running time regardless of the value of L. 3.2.2 Optimization Problem In general, the optimization problem of concern here is to classify N connection requests sft = { n , T'2, ...,TN} to one of the L service levels SL = {xi,%2, •••! XL} while minimizing the quantization overhead. Figure 3.2 illustrates the classification process for L = 4 service levels. Each point in the figure corresponds to a connection request wi th a QoS and bandwidth requirement. Vertical lines represent the separation between the service levels. Formally, we need to find the set of L classified groups (classes) ix*L — { C 7 * , G * , . . . , G £ } such that 'i/j(rr*L) < '^(TTI) where IP{TTL) measures the service quantization overhead and is defined as follows: Each connection request has to be assigned to exactly one service level. Also , because each service level must have some resources assigned to it (e.g. buffer, bandwidth, chan-nel, etc.), we wi l l restrict the groups Gi 1=1,... , L to be non-empty. In other words, the size of each group |G; | > 1, 1=1,... ,L. L (3.4) i=i V n e G , Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 28 o S% (J) cPo ' 0 , 0 o O Ip o O C Q . • « * ? v 0 ! ^ "ft . OoS Classification Figure 3.2: QoS-based classification. 3 .2 .3 P r o p o r t i o n a l D i f f e r e n t i a t i o n M o d e l ( P D M ) We consider a link that satisfies the proportional differentiation model (PDM) with a fixed set of weights for a finite number of traffic classes. Such a model has been adopted by several proposed mechanisms in different types of networks like [34], [33], and [32]. The PDM dictates the following relationship for all pairs of service classes. Xi(t,t + T) _ OJi (3-5) Xj(t,t + r) LOj where xiy and x.j are the service levels (e.g. average delay, dropping probability, etc.) achieved for two classes i and j over the time period r, and Ui and Uj are the weights assigned to these classes. We consider connection requests with life time long enough for Equation (3.5) to be valid. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 29 Example L i n k Model We consider for example the model used in [34], The statistical model for Dropping Probability (DP) is explained in [63]. The DP for Poisson traffic arrival is defined as „m+B DP = — (3.6) m m+B x ' m\mB[l + £ p^} + YI Pimm+B-i i=l i=m+l N where p is the link's total load (i.e. p di/C), rn is the number of data channels, and i=l B is the number of storage locations (in packets). Furthermore, if we divide this link into L classes where all classes are active, and traffic in all pairs of classes are statistically independent, the relationship between the total DP and xi values is as follows: L L DP = l - H ( l - xt) - log(l - DP) = - ^ log(l - X l) i=i i=i Considering that x/'s are <<1 (i.e. - log(l - xt) « xi), then L -\og(l-DP) *J2X> ^ i=i From Equations (3.5), (3.6), and (3.7), we can obtain the link's offered service levels for Poisson traffic. The same approach can be used with other dropping probability models for Poisson and voice traffic models such as those suggested in [64] and [65]. Example Assume we have 5 connection requests having a total bandwidth demand of 110Mbps, with the following set of D'Ps'Q= {0.00033027, 0.0036963, 0.024236, 0.043694, 0.074222}. Assume that we need to assign the 5 requests to 3 traffic classes with the following weights Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 30 W= {10~3,10~2,10 - 1}, given a link capacity of 100Mbps. In general, we have 6 possible ordered classifications for the 5 connections. We can obtain the service levels using the model explained before (p=l.l, m=l, B =200), SL= {0.000859, 0.008586, 0.085865}. We can then obtain the optimal classifi-cation using these service levels as will be explained in Section 3.3. Optimal classification TT* = {[0.00033027, 0.0036963], [0.024236, 0.043694], [0.074222]} and the total quantization overhead in this case is 0.065766 (using U(Qi, x{) — \Qi — Xi\). 3.3 O p t i m a l s o l u t i o n f o r fixed s e t o f s e r v i c e l e v e l s a n d s o f t Q o S r e q u i r e m e n t s For a set of service levels Si = {xi,x2, • •• ,«L} which may be based on the link's total load and a set of QoS requests ipN = {Qx, Q2, ...,QN}, we form the system matrix A N x L such that the elements of A are = U(Qi, Xj) i=l,...,N, and j=l,...,L. To minimize ^(TTL), we map the problem to the following dynamic program. where measures the minimum quantization overhead for the l-th service level and up to the i-th traffic stream recursively based on the overhead of previous service levels. Based on this equation, we propose an algorithm for finding the optimal QoS-based classification for a fixed service levels O Q C - F S L shown in Figure 3.3 for the classification problem. Note that the summation of Qji for j = k+1,... ,i can be pre-computed for all j=k+l Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 31 i—l,..,N and j=l,..,L leading to a complexity of 0(N2L). The matrix CG is used by the Dynamic-Program sub-algorithm to store the indices of the current best classified group for each service level. Lines 1 and 2 of the main algorithm O Q C - F S L have complexity of 0(N2) and 0(NL) respectively in the case that the QoS values are not sorted. The pre-computation complexity for the summation of ciji for j = k+l,... ,i for i,j=l,... ,N and k=l,... ,L in line 6 of the Dynamic_Program sub-algorithm is 0(N'2L) which is similar to the complexity of the DynamicJProgram. Therefore, the complexity of algorithm O Q C -F S L is 0(N2L). 3 . 4 O p t i m a l s o l u t i o n i n t h e c o n t e x t o f a d m i s s i o n c o n t r o l ( h a r d Q o S R e q u i r e m e n t s ) Until now, we have assumed that incoming traffic streams can tolerate service levels with a QoS value lower than the QoS it required initially. Although many practical applications can tolerate certain amount of QoS level drops, the level of tolerance can vary widely among different applications. Therefore, an admission control mechanism is needed to impose some restrictions on the minimum level of service achieved by all traffic streams (the new added steams plus the existing ones). Basically, to admit new streams, the link must be able to provide all traffic streams with a level of service which is within a certain tolerance limit from their required QoS. Otherwise, the admission Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 32 ( < / < « ) , < ) = O Q C - F S L {{Qi,...,QN}, {xlt.. ;XL}) 1. Qi V i are sorted in a non-decreasing order 2. Form matrix A^xi = {ay i = 1 , N j = 1,...,L} 3. ('(/•(TT*), 7T*) = Dynamic_Program (A) ('0(7r*), 7r*) = Dynamic_Program (A) 1. For / = 1 to L 2. For i = 1 to i V 3. ^{i,l) = oo, CG(i,0 = 0 4. For A; = / - 1 to i - 1 5. If Z - 1) + £ a,-, < ^ ( i , I) Then 6. Set I) = 4>{k, + £ and CG'(*> 0 = 3 7. 8. E n d If E n d For 9. E n d For 10. E n d For 11. ^(nl) = ^(N,L) 12. For m = L Down To 1 13. Set G*m £ *l = {ri, i = (CG(j,m) + 1 ) , j } 14. Set j = CG(j, rn) 15. E n d For Figure 3 . 3 : Optimal QoS-based classification with fixed service levels (OQC-FSL). control mechanism might reject the addition of new traffic streams. In order to capture this behavior, we introduce a new variable called the tolerance factor, 5. This factor Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 33 represents the maximum drop in QoS for the traffic stream that can be tolerated by the application generating this traffic. For example, in streaming applications the tolerance factor can be improved by adjusting the size of the play-back buffer at the receiver. The tolerance factor can be part of the service level agreement (SLA). Note that 5=0 means that the traffic stream cannot tolerate any service level drop. We will assume the most general case in which each traffic stream has a different tolerance factor (i.e. V i = {di,Qi,5i}). To accommodate this fact, we will add the following condition: ( Q i - Xj + 5i)>0 i = 1, ...,N j = 1 , L Or if 5i is defined as a percentage of QoS Q i , the condition becomes ((1 + 5i) Q i - Xj) > 0 i = l,...,N j = 1,...,L (3.8) = O Q C - F S L - A T F ({&}, {xu...,xL}) 1. Q i Vi are sorted in a non-decreasing order 2. Form matrix AN*L = {a-ij i — 1, N j = 1,...,L} 3. If ((1 + 5i) Q i - Xj) vr.y < 0 T h e n Set avj = oo 4. (4>(^*l),TT*L) = Dynamic_Program (A) Figure 3 .4 : OQC-FSL with arbitrary tolerance factors (OQC-FSL-ATF). To incorporate this condition in the O Q C - F S L algorithm we will exclude the assign-ments where condition (3.8) is not satisfied by setting a,j = oo as shown in Figure 3.4, This will force the Dynamic_Program to assign traffic streams only to the classes that can provide service levels within the tolerance factor. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 34 3 . 5 S e r v i c e d i f f e r e n t i a t i o n b a s e d o n c l a s s w e i g h t s We start by assuming that the maximum link capacity restriction is not enforced or, alternatively, assume that there is a light traffic load on the link. Obviously, if the link is lightly loaded, the QoS achieved by the traffic streams may potentially exceed the QoS requirements. In this case, we have some flexibility in assigning the traffic streams to the different service classes. One scheme would be to assign most of the traffic streams to the lowest service level(s) as long as the QoS requirements by the streams are satisfied. However, even in this case, it may be desirable to offer some service differentiation between traffic streams while saving the link resources, for example, to increase bandwidth available for best effort traffic. To achieve that, we follow the same methodology explained in Section 3.3. This time, we set atj = U(Qi,^ujj) such that u>j is the weight assigned to service class j, j=l,.. ,L, and 7 is the service differentiation factor selected based on the characteristics of incoming QoS requests. By choosing a specific value for 7, the problem reduces to fixed set of service levels which was explained in Section 3.3. Ideally, we need to select the value of 7 such that 4>(ir*) has the lowest value possible. However, this means that we need to try all possible values of 7 and get the optimal classification for each case, then select 7 such that the value of I}>{IT*L) is minimized. Such naive approach has very high complexity. In the following, we propose two heuristic estimates for the value of 7. Then, we drive the optimal value of 7 that guarantees a minimum value for ip(n*L) V7. First, we present the following lemma, Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 35 L e m m a 3.3. IfU(Qi,~fuJj) fulfills the utility property, and U(C/i, 7<^ j) = Cy*[/ (Qi/u>j,-y), where Cij is any constant, then in order to minimize the value ofip(ir*), 7 must be selected in the range [mm(Qi/uj) , max(Qi/u>j)] i = 1,...,N j = 1,...,L. Proof. Given in Appendix A • This lemma limits the range of possible values for 7 between the minimum and max-imum possible weighted QoS values. Using median as a heuristic estimate of 7 One natural choice for the value of 7 is the center of the sample data dy = Qi/ujj, or the statistical median(dy) i = l,...,N and j = 1,...,L. The intuition behind this selection is to try to lower the values of U{Qi,^LOj) by selecting 7 in the center of dy in order to minimize the value of tib{iT*). The co'mplexity of calculating the statistical median is known to be 0(NX)[66]. Using minimum summation as a heuristic for calculating 7 N L Another heuristic estimate is to select the value of 7 such that the total £ £ fly is minimized. The intuition is that if we minimize this summation, then we may potentially lower the value of the sum on any subset of i, and j. Although in this case, we have an infinite number of values for 7 to try, the following theorem limits the possible choices of 7 when some reasonable conditions on the utility function are satisfied. Theorem 3.1. / / U{Qi,^u)j) is a piecewise concave function, and 7W.,) = Cy * U(Qi/u>j,j) where Cy is any constant, then 7 must take one of the values of dij = Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 36 Qi/uij i = 1,...,N and j = 1,...,L in order to minimize the summation ^ YI aij for iei je.J any subset of i and j . Proof. Given in Appendix A • The above theorem implies that to get the value of 7 which minimizes the summation N L = Y2 aij' w e n e e d o n l y ^ 0 consider N*L possible values of 7 € {<% = Qi/<^j, i = »=ij=i 1.....N j = 1,...,L}, given that U(Qi,^tOj) is a piecewise concave function and the condition U(Qi,jVj) = Cy- * U(Qi/uij,j) is satisfied. Because it is a piecewise concave function, U(Qi,~fUj) is non-increasing concave in the interval Qi e[0, jujj] and non-decreasing concave in the interval Qi G[7WJ,OO[. Some examples for piecewise concave functions are defined by Equations (3.1) and (3.3). To illustrate the effect of Theorem 3.1, Figure 3.5 shows the summation \& for all pos-sible values of 7 using U(Qi,juJj) as defined by Equation (3.3) for three incoming traffic streams and one class of service. It is clear from the figure, that the possible minimum values of ^ correspond to 7 € {Qi/^i , Qil^>\^ Q-il^x)- Consequently, we can derive the value of 7 that minimizes the summation $ using the algorithm min_sum_df shown in Figure 3.6. The complexity of this algorithm is 0(N2L2) assuming the summation on line 4 is 0{NL). Theorem 3.1 also implies that determining the value of 7 that minimizes ip(ir*) can be done by first substituting 7 by one of the values, then obtaining the optimal classification for each possible value of7, and finally selecting the value of 7 that has the minimum IP(TT*). This is illustrated by algorithm min_opt_df in Figure 3.7. Note Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 37 Figure 3.5: The effect of 7 on * for 3 Q\s and one COJ. (7) = min_sum_df ({Qi,... ,QN}, WI,U)2,...,UL}) 1. Set min* = 00 2. For j = 1 to L 3. For i = 1 to N 4. Set 7' = Qi/ujj and * = YJ^., Y!j=. U(Qi,rujj) 5. If * < min* T h e n Set 7 = 7-6. E n d For 7. E n d For Figure 3.6: Differentiation factor 7 for minimum *. that the optimal classification 7r* may change by changing the value of 7. However, the following theorem states that algorithm min_opt_df does indeed find the optimal value of 7. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 38 Theorem 3.2. Algorithm min.opt.df finds the optimal value of 7* G {dij = Qi/uj, i = l , . . . , i V j = such that '0(7r2(7*), 7*) < ^ (^ (T)) 7) ^7 tfU(Qi, 7Wj) is o piecewise concave function, and U(Qi,jw:j) = * U(Qi/uj,j) where Cy is any constant. Proof. Given in Appendix A • By replacing line 6 of algorithm min_sum_df with a call to algorithm O Q C - F S L , we get the value of 7 that minimizes ip{ir*L) as shown in Figure 3.7. (7) = min_opt_df ({3ft}, {ui,u2, ...,^}) 1. Set min\I/ = 00 2. For / = 1 to L 3. For i = 1 to AT 4. Set 7- = Q,/u>j 5. * = OQC-FSL({3ft},(5 L)) 6. If * < m i n * 7. Set 7 = 7' 8. E n d If 9. E n d For 10. E n d For Figure 3.7: Differentiation factor 7 for minimum V K 7 1 " ! ) -From Section 3.4, we know that the complexity of O Q C - F S L is 0(N2L). Therefore, the complexity of this algorithm is 0(N3L2). Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 39 Example to illustrate the estimation of 7 Repeating the example in Section 3.2.3, with predetermined weights, and no capacity restriction, we can have some flexibility on setting the value of the 7. The following cases show the effect of the three different ways of estimating the value of 7 on the value of <MO 1. Using median(dij), 7-0.74222, ^(0=0.05070783, n*L = {[0.00033027, 0.0036963], [0.024236], [0.043694, 0.074222]}. 2. Using algorithm min_sum_df, 7=0.24236, '0(0=0.07080461, TT*L = {[0.00033027, 0.0036963, 0.024236], [0.043694], [0.074222]}. 3. Using algorithm min_opt_df, 7=0.74222, ^(0=0.05070783, TT* = {[0.00033027, 0.0036963], [0.024236], [0.043694, 0.074222]}. Note that for cases 1 and 3, the solution is identical and the value of 7 is the same while in both cases the value of I^(TT*L) is lower than the value based on min_sum_df. 3 . 6 Service differentiation based on class weights, and limited link capacity The link capacity C poses a restriction on the range of service differentiation values. We assume that the relationship between the capacity and the service differentiation factor is known through statistical modeling (e.g. such as the model described in Section 3.2.3) Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 40 or through numerical estimation. From this relationship, we can obtain the minimum value of 7, or j m i n (Line 2 in Figure 3.8), which can then be used to modify the algorithm min_opt_df to obtain the optimal classification V7 > 7mi n. The modified algorithm is shown in Figure 3.8. The complexity of this algorithm is still 0(N3L2). The algorithm uses the result of Theorem 3.2 and selects a subset of possible values of 7* G {dy = Qi/ujj, i = l,...,N j = 1 , . . . ,L} which are greater than 7mj n where 7 m i n is imposed by the limited link capacity. ( < / > « ) , < ) = O Q C - P C W (W, { W l W i } , C ) 1. Qi/ojj Vi Vj are sorted in a non-decreasing order 2. Initialize: Set -ymin = /({5£},C), and min* = 00 3. Vdy = Qi/uj , i = 1 , N j = 1 , L such that > 7m;n 4. Set 7- = dy, and SL = {7'w>, j = I, L} 1 5. (*,n)=OQC-FSL({3fc},{SL}) 6. If * < min* T h e n 7. Set 7 = 7', ^(TT£) = * , and ir*L = II 8. E n d If Figure 3 . 8 : OQC for predetermined class weights and limited link capacity ( O Q C -P C W ) . 3 . 7 Optimal classification for stochastic QoS In practice, sometimes the set of QoS demands may not bc explicitly known. Instead, the QoS requirements for the incoming traffic streams maybe determined by a continuous Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 41 random variable Q, which has a probability density function (pdf) f(Q) as shown in Figure 3.9. This QoS pdf may for instance be obtained empirically. The optimization problem in this case will be to find the L set of ranges 5ft£ = {R*, /?,*,R*L} defined on Q such that the expected value of the quantization overhead E(IP(?RL)) is minimized. In other words Where each of these ranges R* = {Qf i n , Qf**} is defined by the minimum and maximum values of Q and E(IJJ(^L)) is defined as follows: L E ( ^ L ) ) = ^2 U(Q,xt)*f(Q)dQ To leverage our solutions discussed before, we will sample the QoS pdf /(Q) using a delta step AQ, such that Q = kAQ, for k = 1, ,K where K = Qmax/L\Q is the K sampling size. The fc-th sample of f(kAQ) is scaled by AQ so that YI f(kAQ)=l, The k=l expected quantization overhead then becomes: L 1=1 Ri The system matrix A will change slightly such that aki = U{kAQ,xi) * f(kAQ) for k=l,..,K, and 1=1,..,L. The Dynamic_Program algorithm can then be run against this modified matrix to obtain the ranges in JJJ. Note that since lim AQ = 0, the ranges ?R*L ff->oo obtained by this solution will approach the optimal ranges for large values of K. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 42 3 . 8 E x p e r i m e n t a l E v a l u a t i o n In this section we examine the normalized quantization overhead defined as: N 1=1 For the deterministic case, or M^l) = E(mi))/E(Q) For the stochastic case. We measure this overhead in different scenarios using the algorithms presented above. For the results presented in this section, we consider the link dropping probability as the prime QoS requirements. We assume, for example, the model explained in Section 3.2.3 when it is relevant and we use the utility function defined by Equation (3.1). T3 Q. Figure 3 . 9 : Example of a QoS probability density function. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 43 3.8.1 Results for deterministic QoS Effect of increasing the number of service levels We present first the results for variable-sized sets of connection requests ranging from N= 10 to 500 requests. For each set, the DP is uniformly distributed from 10 - 1 to 10~10. The class weights are selected sequentially from the set W = {10 _ 1 ,10~ 2 ,10~ 8 } such that for L=2, we use only the first 2 weights, for L=3, we use the first 3 and so on. We consider the case where the link is slightly overloaded (i.e. link loacl«l.l) and we use algorithm O Q C - F S L to find an optimal classification based on fixed service levels calculated from the link's total load. 200 300 Set size (W) 500 Figure 3.10: Variable sized sets for different number of service levels, M/={IO-\IO- 2 , . . , IO- 8} . Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 44 Figure 3.10 shows the results in this case. Each point in this figure is taken from the average of 10 sets of uniformly distributed DP values each of size N. We notice from the results that the increase in the normalized overhead is negligible when the number of service levels is above 3. This in fact should be an indication that the class weights are not selected efficiently. To further investigate this point, we show the results for W= {2 _ 1 , 2 ~ 2 , 2 ~ 8 } as shown in Figure 3.11. We notice, in this case, that the change in overhead when increasing the service levels can reach 30% when the weights are selected appropriately. However, even in this case, it is clear that the gain of decreasing the normalized overhead is not significant when the number of service classes is above L=5. In. fact, the gain in decreasing the overhead by increasing the number of service levels will become more significant as the link load increases. Figure 3.12 shows the impact of increasing the link load on the normalized overhead for a connection request size N=500 uniformly distributed. We see that the effect of increasing the number of service levels magnifies as the link becomes more overloaded. Interestingly, in this case, the effect does not appear to be significant for L>5 service levels. Effect of different estimation methods of 7 on the normalized quantization Figure 3.13 demonstrates the effect of different estimation methods of 7 on the normalized quantization overhead when the QoS requirements have uniform distribution. The figure shows that the estimation of 7 using the min_sum_df algorithm performs slightly better than the median in case of uniform distribution. The estimation using the min_opt_df Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 45 200 300 Set size (W) 500 Figure 3.11: Variable sized sets for different number of service levels, W= {2-1,2-2,..,2-8}. Total load Figure 3.12: Variable load for different number of service levels, N=500, W-{2- 1 ,2- 2 , . . ,2- 8 }. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 46 performs consistently better than the two other methods. Figure 3.13: Variable sized sets for 7 estimation methods, uniformly distributed QoS. Effect of tolerance factor 5 on the normalized quantization Figure 3.14 and Figure 3.15 show the effect of the tolerance factor on the normalized quantization overhead. Figure 3.14 shows the tolerance effect for uniformly distributed QoS values using the O Q C - F S L - A T F algorithm for 4 service levels. We notice even when the link is lightly loaded, the quantization overhead is high. This is based on our original definition for the utility function. In other words, the link is best utilized when the load is close to the full load, in which case the quantization overhead is minimized. However, at certain loads, the link cannot offer the required QoS values, and in this case, some 'traffic streams might be rejected. This is illustrated by the discontinuation Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 47 in the quantization overhead curve. We also notice that by increasing the tolerance, the link has more possibility of accommodating more traffic streams. Figure 3.15 shows the tolerance effect for uniformly distributed QoS values using the O Q C - P C W algorithm using 4 service levels when the link is almost fully loaded. Clearly, increasing the tolerance factor plays a significant role in decreasing the quantization overhead regardless of the number of traffic streams. It is interesting to note that, increasing the tolerance factor limitations can be reduced through application-level adaptation. Our results are among the first to quantify the interrelation between application-level adaptation (tolerance) and QoS levels. 1 c O 0.9 CO £ 0.8 §0.7 CT "g 0.6 N 7 6 0.5 O 0.4 c 0.3 0.2'— 0.7 0.75 0.8 0.85 0.9 0.95 1 1.05 Total load F i g u r e 3 . 1 4 : Effect o f tolerance factor for different link loads, uniformly distributed QoS, using O Q C - F S L - A T F algorithm. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 48 0.5 0.45 • C o CO 0.4 -N S° 0.35-CT CD 0.3 • E 0.25 k o c 0.2 -0— 5 =60% 0 100 200 300 400 500 Set size (N) F i g u r e 3 . 1 5 : Effect of tolerance factor for variable-sized sets, uniformly distributed QoS, using the O Q C - P C W algorithm. 3.8.2 Results for stochastic QoS In this section, we study the effect of the QoS statistical distribution on the value of the quantization overhead. For all results here we use W— {IO - 1 ,1 .0~ 2 ,10~ 8 }. Fig-ures 3.16 to 3.19 show the results for the stochastic QoS requirements. Three important observations can be made from the six figures in addition to what was in the previous section. First, the quantization overhead tends to converge to its optimal value as the value of K grows large and in fact this convergence is faster as we increase the number of service levels. This implies that the selected value of K depends on how many service levels used and the distribution of the incoming traffic streams. Apparently, we can use K as low as 1.00 (i.e. only 1.00 samples of the pdf function) for most of the QoS distribu-Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 49 tions for number of service levels more than 2. However, for low number of service levels (e.g. L=2 in Figure 3.17), it is recommended to use higher values for K. Second, the algorithm min_surn_df performs worse than the median for the clustered QoS distribu-tion but still the min_opt_df outperforms both regardless of the QoS distribution. This indicates that the heuristic estimation for 7, while it is faster, its proximity to the optimal value is based on the input QoS distribution (see Figure 3.18). Finally, by increasing the tolerance factor progressively, the quantization overhead gain for the clustered distribu-tion does not seem to increase with the same rate. This implies that by increasing the tolerance factor, not only may this become unacceptable by the applications generating traffic streams, but also the overhead gain may not be as significant. — e — i.=2 L=3 i.=5 i.=8 l j e s © e e e e e e e e e e o c 3 o e © e e e Q o e e e e e e e e e e e e e e Q e e e e o o 0 100 200 300 400 500 600 700 800 900 1000 Sampling size (K) Figure 3.16: Effect of K for different number of service levels, uniform QoS distribution. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 50 200 400 600 800 1000 Sampling size (Kj Figure 3.17: Effect of K for different number of service levels, for 4-cluster QoS distri-bution. Figure 3.18: Effect of total load, for different number of service levels, for 2-cluster QoS distribution for N=200. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 51 1 0.9 C o 0.8 CO N V-< c CO 0.7 CT I 0.6 CO § 0.5 o c -©— median —«— min_sum_df -<?— min_opt_df geeeeeeeeeeeeeeeeeeeeeeeeoooooooocxieeeeeeeeeeec) 0 100 200 300 400 500 600 700 800 900 1000 Sampling size (K) Figure 3.19: Effect of 7 estimation methods for 2-cluster distribution using 5 service Figure 3.20: Effect of tolerance factor for different link load, for 2-cluster QoS distrib-ution using 5 service levels. Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 52 0.5 c o _N 0.45 -C 03 Z3 CT « 0.4-i— O c 0 100 200 300 400 500 600 700 800 900 1000 Sampling size (K) F i g u r e 3 . 2 1 : Effect of tolerance factor for variable-sized sets, for 4-cluster QoS distrib-ution. 3 . 9 C o n c l u d i n g R e m a r k s We have presented a group of algorithms for calculating the optimal classification for a set of traffic streams with diverse QoS requirements for a link model with a predetermined service levels or predetermined class weights. Our results show the effect of selecting the class weights based on the statistical distribution of the incoming connection requests. It was shown that by carefully selecting the class weights, the quantization overhead can be significantly reduced especially for 4 or 5 service levels using dropping probability as the QoS metric. The results also show that the effect of increasing the number of service levels diminishes as the service levels rises more than 5. We also studied the effect of the three proposed 7 estimation methods on the quantization overhead. The results show that Chapter 3. Optimal QoS-based Classification for Multi-class Link Models 53 the m i n _ o p t _ d f algorithm has the best performance over the other 2 heuristic methods regardless of the statistical distribution of the incoming QoS requirements. Furthermore, the expected quantization overhead for stochastic QoS requirements tends to converge as K (number of pdf samples) increases above 100 at least for all the QoS distributions discussed in this chapter. The exception from this is when we use service levels less than 3, in which case, K is recommended to be larger. 54 Chapter 4 QoS-Based Partit ioning and Resource Allocation In this chapter, we present two algorithms called O Q P and O Q P - O B A for calculating the optimal QoS-based partitioning and bandwidth allocation for a link model with a small set of variable service levels using dropping probability as the QoS metric. We formulate the partitioning process as a Dynamic Programming problem and present two polynomial time algorithms to obtain the optimal QoS-based partition with bandwidth allocation. 4 . 1 I n t r o d u c t i o n We consider a link model with variable service levels which may be mapped to a finite number of MPLS Label-Switched-Paths (LSPs). Our target is to partition a set of traffic streams each with arbitrary local QoS-demand into a small number of classes and find the service level for each class such that the residual-allocated-resources as a result of °A version of this chapter has been published [17] Chapter 4. QoS-Based Partitioning and Resource Allocation 55 the traffic partitioning is optimized. The residual allocated resources will be measured by the service quantization overhead which is the summation of the differences between the required QoS and the offered service level for all traffic streams. We formulate the partitioning process as a Dynamic Programming problem. We then present two polynomial time algorithms to obtain the QoS-based optimal partition with bandwidth allocation. The problem of obtaining optimal quantized service levels for a set of connection re-quests has been investigated before in [61], [4], and [13]. Rouskas et al. in [61] defined a similar framework of assigning MPLS tunnels with specified data rates to a set of quan-tized service levels such that the performance penalty of wasted bandwidth is minimal. Both the deterministic and stochastic connection requests have been discussed. However, the case of having two joint requirements (e.g. bandwidth, and dropping probability) was not discussed. The authors in [4] discussed the problem in a different context where the set of requests are group of receivers on a multicast tree. Even though this context was different from our framework, the target was rather similar which is to find the small optimal set of offered rates (by the source) that maximizes the correlation between the total required rates requested by the receivers and the offered service levels. The solution for joint requirements was discussed in [13] for a simpler case where the set of service levels are predetermined. The study presented in this chapter extends these partitioning frameworks to the QoS based partitioning with resource allocation. It also offers solutions to the generalized problem where connections have both rate and QoS requirements and Chapter 4. QoS-Based Partitioning and Resource Allocation 56 presents polynomial time algorithms for soft and hard QoS requirements. The rest of the chapter is organized as follows; Section 4.2 formulates the model and the problem and relates our framework to QoS network architectures. The optimal solution for QoS-based partitioning using variable service levels is discussed in Section 4.3. The optimal partitioning with bandwidth allocation is outlined in Section 4.4. Section 4.5 depicts the results for applying our solutions to a set of QoS requirements with different distribution. Finally, Section 4.6 summarizes the key contributions in this chapter and highlights the importance of using optimal partitioning with bandwidth allocation. 4 . 2 M o d e l a n d p r o b l e m f o r m u l a t i o n 4.2.1 Model and notations We consider a network of nodes that provide interconnection to a number of links. Each link has a variable set of L quantized service levels Si = {.Si,s2, •••,«£,}, such that each service level si, I =1, L represents the QoS maintained in this class 1. Each link also has a set of resources assigned to each class where some of these resources (e.g. link capacity C) might be shared amongst the service classes and are meant to be assigned arbitrarily to optimize certain criteria. Some other resources (e.g. buffer size B) might be assigned to the service levels permanently. We also have a set of N connections 3ft = {r\, r 2 , r N } . Each connection request T j is defined using both bandwidth demand di and one local QoS requirement Qi (e.g. Chapter 4. QoS-Based Partitioning and Resource Allocation 57 average delay, DP, jitter, etc.), namely r\ = [d^Qi]. If n G Gi and si < Qi, this means that traffic stream rx is assigned to class I and is achieving better QoS than required and that may entail a waste of link resources. F i g u r e 4 . 1 : QoS-based partitioning model. A partition PL= {Gi,G>2, ...,GL} is defined for L service levels as a set of L groups where each group G\ has one or more of the incoming traffic streams. Figure 4.1 shows the QoS-based partitioning model including the link model with a logical queue assigned for each service level and the resources assigned to each queue. The best QoS for service class / is constrained by the resources and the total bandwidth demands for the traffic streams assigned to this class. This relationship is characterized by a deterministic function /( £ di, Ci, Bi,...) which is used to calculate the best achieved teG'i QoS on a certain class given the allocated resources and the total load assigned to this Chapter 4. QoS-Based Partitioning and Resource Allocation 58 class. This function can for example be obtained empirically or by using one of the appropriate well known Markov chain based models such as M / M / l / B [26, 67] for Poisson traffic. The authors in [41] and [68] also provide analysis and modeling for vast scheduling disciplines using Poisson and voice sources. 4.2.2 Opt imiza t ion problem The optimization problem is to find the optimal set of service levels SI = {s{, s 2 , s * L } , the optimal partition of traffic streams P*L= {G*, G\,G*L}, and the optimal allocation of shared bandwidth C*L = {c{,c2, ...,c*L} that minimize the QoS quantization overhead. The QoS quantization overhead is used to calculate the total penalty of supporting a small set of service levels on the granularity of providing QoS to different connections (flows) and is defined by the following objective function: L (4.1) 1=1 Vr .eG ' i •o I TJ C 03 E 13 QoS F i g u r e 4 .2 : QoS-based partitioning. Chapter 4. QoS-Based Partitioning and Resource Allocation 59 U(Qi,si) is the utility function which measures the difference between the achieved and offered QoS. Figure 4.2 depicts the QoS-based partitioning process for a group of traffic streams defined by the 2 dimensional graph showing the bandwidth demand and QoS requirement for each traffic stream. It also shows the optimal service levels and the partitioned classes as a result of partitioning the traffic streams into 4 classes. The allocated bandwidth for each class (i.e. c*) is selected such that s(* > /( £ di, C\,Bi,...). In other words, service level j cannot exceed the value /( £ (k,Ci, Bi,...) for a given amount of resources (i.e. Q , BI, etc.) allocated to this class. The optimization problem can then be formulated as follows: minimize ^ { P L ) subject to si> fC^duCuBi,...) l = l,...,L (4.2) iec; L £ C i < C - (4.3) Where C is the total link capacity shared amongst all service classes. In section 4.3 we will add another constraint to this optimization problem to force a maximum limit on the service level of each class which might be forced by the applications generating the traffic streams. Without loss of generality, we consider a scheme of QoS-based partitioning where all traffic streams are sorted based on their QoS requirements and the utility function has certain constraints. The following definitions describe this partitioning scheme. Ordered Partit ion Chapter 4. QoS-Based Partitioning and Resource Allocation 60 A partition Pi = {G\, G%,GL} is called an ordered partition if Vr* € G„ and Wj G Gj, we have Qt < Qj, when sa < si,. Util i ty Property Intuitively, the utility function is non-increasing in the interval Qi £ [0, s{\ and it is non-decreasing in the interval Q, £ [s;,oo[. The importance of the these two definitions lies in the fact that if we choose a utility function that fulfills the utility property we only need to consider the ordered partitions when we search for an optimal solution (see Lemma 3.1). Indeed, considering only the ordered partitions will limit the number of possible solutions for optimality. However, in Chapter 3, we proved that brute force enumeration technique using ordered partitioning policy will lead to an exponential running time solution (see Lemma 3.2). Util i ty functions Selecting the appropriate utility function identifies the criteria used to minimize the objective defined by Equation (4.1). To illustrate this point we mention the following 3 cases: 1. We can select U(Qi,si) to measure the penalty of allocating unutilized resources for each service level-by decreasing the service level si below the QoS values Qi assigned to this class. log(l + Qi - S i ) . si < Qi Example : U(Qi,Sl) = { (4.4) 0 Otherwise Chapter 4. QoS-Based Partitioning and Resource Allocation 61 2. We can instead select it to measure the penalty of violating the QoS Qi required by each traffic stream. r si - Qi Qi < st Example : U(Q,,, Si) = < (4.5) 0 Otherwise 3. Or we can measure the penalty in both cases to obtain the best set of service levels that achieves the trade-off between the allocated resources without violating the QoS requirements for the traffic streams. Example : U{Qit st) = \Qt - sL\ (4.6) Hence, the support for all these aforementioned cases demonstrates the versatility of the proposed solutions discussed in this chapter. Notice that all the utility functions defined by Equations (4.4), (4.5), and (4.6) fulfill the utility property. 4 . 3 Optimal solution for QoS-based partitioning This section describes the solution for the optimal QoS-based partitioning (OQP) problem without taking into consideration the allocation of the shared bandwidth. In other words, we will assume a simplified version of the problem where the traffic streams have only QoS requirements, and we need to partition them so that the quantization overhead is minimized. Even though, in this case we do not have to consider the set of constraints defined by Equations (4.2) and (4,3), which makes the problem easier. The following lemma states that the OQP problem is N P - C o m p l e t e even for an arbitrary partition. Chapter 4. QoS-Based Partitioning and Resource Allocation 62 L e m m a 4.1. IfU(Qi,Si) is a step function defined as follows: a?; Qi < si (4.7) U{Qi,Sl) = bi Otherwise where an and bn are constants, then solving OQP for one specific partition PL is equiva-lent to solving the SUBSET SUM problem (see SP13 in [69]) which is an NP-Complete problem. In order to find the exact minimum value for OQP, we will impose another restriction on the utility function. Particularly, the following definition describes a specific class of utility functions for which we will develop the solution for OQP. Piecewise concave functions U(Qi, si) is a piecewise concave function if it is non-increasing concave in the interval Qi G [0, si] and non-decreasing concave in the interval Qi G [s;,co[. This means in addition to the fact that it fulfills the utility property, it is also concave on each interval separately. By concave function we mean that for any interval Qi G [a, b], U{Qi) satisfies this inequality Figure 4.3 shows an example of a piecewise concave function which is defined as follows: Proof. Given in Appendix A • U{aa-+{l-a)b) > a V(a) + (1 - a) U{b) 0 < a < l (4.8) U{Qi,st) = log(l + \Qi - si\) Chapter 4. QoS-Based Partitioning and Resource Allocation 63 Figure 4 . 3 : Example of a piecewise concave function. The following theorem then states the rule for finding the optimal service levels to mini-mize the quantization overhead. Theorem 4 . 1 . If all U(Qi,$i) VQ* are piecewise concave functions, then for each group Gf in the optimal partition PI, the value of the service level s* that coincides with one of the values Qi € Gi will always minimize the total overhead of class j such that U(Gi, s(*) < U{GuSl) V s t g { Q i : i e G , } . Proof. Given in Appendix A • This means that for each class Gi € Pi the service level s; must be one of the values in the set {Qi: i € G;} in order to minimize the summation U(Gi,s*) = YI U(Qi, s*t). VQ.-6G, One of the most efficient ways of solving this problem is by recursive enumeration which is the main idea of dynamic programming. Hence, the problem can be mapped to the Chapter 4. QoS-Based Partitioning and Resource Allocation 64 following dynamic program. i il>(i,l)= min [i>(k,l-l)+ min V [/(Q^QJ] (4.9) Kfc<t—1 k+\<m<i —' j=k+l where i/j(i, I) is the local optimal quantization overhead for requests up to request i using I service levels. This local optimal value is calculated based on recursive enumeration. Finding the value of k that minimizes Equation (4.9) is used to find the current, best partition class G*t G P£. In other words G\ = {Qk+\,Qi), such that i k = arg min[^(A:, I — 1) + min ' U(Qj, Qm)} \<k<i-l fc+Km<i .f—J Equation (4,9) utilizes the result of theorem 4.1 in calculating the minimum class quan-tization overhead as follows: i U(Gi = {Qk+l,Qi},s\) = min V U(Q3,Qm) fe+].<m<» J j=k+V j And s;= arg min Y\ U{Qj,Qm) (4.10) Qme{Qk+i Qt} jtk+i One thing to notice in Equation (4.10) is that the selected service level s* that min-imizes U(Gi = {Qi,Qj}, s*) may not be accepted by the applications generating the traffic streams. This is because the difference between the service level s* and the QoS requirements.maybe more than what the applications can tolerate. To account for this, either we have to incorporate the tolerance factor of each traffic stream into the utility function or we can add the tolerance factor as an additional parameter and select the service level such that the following condition is satisfied: ((1 + 5) Qi-Qm) >0 Chapter 4. QoS-Based Partitioning and Resource Allocation 65 where 6 is the maximum percentage of QoS drop that can be tolerated by any traffic stream v*. If 6=0, this means that the traffic stream cannot tolerate any service level drop. Hence, the minimum class quantization overhead (MCQO) can be redefined as follows: i U(Gi = {Qk+i,Qt}, s?) = min V U(Qjt Qm) (4.11) k+Km<i ' ((1+6) Qj-Qm) >0 j=k+l Based on this definition we can now write the dynamic program for solving OQP as shown in Figure 4.4. Optimal QoS-based partitioning [OQP] ({Qi}1? ,L) 1. Qi Vi are sorted in a non-decreasing order 2. For I = 1 to L 3. For i = 1 to TV 4. i>{i,l) = mm{ min [tp(k,l - 1) + U({Qk+i, ...,Qi},si)],ip(i,l - 1)} K f e < t - 1 5. E n d For 6. E n d For 7. Return ip{N,L) Figure 4 .4 : Algorithm optimal QoS-based partitioning (OQP). The complexity for lines 2 to 4 in Figure 4.4 is 0(N2L). The class utility defined by Equation (4.11), can be pre-computed for all i=l,..., N, and j=l,...,N with a complexity of 0(N3) (a similar pre-computation is explained in details in [4]). Therefore, the total complexity of O Q P is 0(N3). Chapter 4. QoS-Based Partitioning and Resource Allocation 66 4 . 4 Optimal QoS-based partitioning with optimal bandwidth allocation (OQP-OBA) This section describes the solution for the optimal QoS-based partitioning with optimal bandwidth allocation ( O Q P - O B A ) problem. In this case, we have a limited link capacity (as an example of a shared resource) that we divide freely amongst the QoS partition classes. This will limit the capacity assigned to each class, and hence, will affect the number of network flows that can be admitted to that class and the service level that this class can provide. Assuming the allocated bandwidth vector is C'L = {c[, c'2,c'L} (i.e. \\CL\\ = c% — i=l C), then for each class, the service level s* is constrained by c\ through the following inequality s\ >f(J2di,ct,Bh...) In this case, the MCQO in Equation (4.11) will become j U(Gi = {Qi,Qj], si cj) = .min. U(Q>» G " ) ( 4 1 2 ) Qm>f( E di4,Bh...) k = i The problem in this case becomes NP-Hard, and therefore, in order to get the optimal bandwidth allocation C£m, we will divide the capacity C into small parts using Ac where Ac is small. The bandwidth assigned to each class will then be w --.Ac, where w= 1,..., W and W = [C/L\c\ is the number of capacity divisions. The recursive equation for the Chapter 4. QoS-Based Partitioning and Resource Allocation 67 dynamic program will then become. il>{i,l,w)= min [il>{k,l-l,b)+ min U({G}lk+l,Qm, A)] (4.13) K f c < i - 1 fc+l<m<i Kb<w-1 • ' X=Ac(w-b) Figure 4.5 shows the O Q P - O B A dynamic program. Similar to the OQP case, we find the value k that minimizes Equation (4.13) for a particular bandwidth allocation b as follows: [k, b] = arg mm[*P(k, I - 1, 6) + min U{{G}\+,, Qm, A)] K f c < i - 1 , f e + A 1 < , m < L k k w - l A=Ac(iu -6) Then we get c* as follows: c* = Ac(w — b) and s* as follows: [s,*]= arg min U {{G}\+1, Q m , c*L) O Q P with Optimal Bandwidth Allocation [ O Q P - O B A ] ({Qi}" , L) 1. Vi are sorted in a non-decreasing order 2. For / = 1 to L 3. For i = l to N 4. For u> = 1 to M / 5. il>(i,l,w)= min [ ^ ( f c , / - l , 6 ) + min U({G}1+1, Qm, A)] l<A:<i—1 fc+l<m<j K k a i - 1 A=Ac(tu-ft) 6. E n d For 7. E n d For 8. E n d For 9. Return if>(N, L, W) Figure 4.5: Algorithm OQP with optimal bandwidth allocation ( O Q P - O B A ) . The complexity for lines 2 to 8 in Figure 4.5 is 0(N2W2L). The class utility defined by Equation (4.12), can be pre-computed for all i=l,..., N, j=l,...,N , and w = Chapter 4. QoS-Based Partitioning and Resource Allocation 68 1,...,W with a complexity of 0(N3W). So, the total complexity of O Q P - O B A is 0(max{N2W2L,N3W}). 4.5 Experimental evaluation In order to verify the feasibility of our algorithms, we consider other schemes for parti-tioning that we can use to measure the advantage of using O Q P - O B A . First, we con-sider the trivial arbitrary QoS-based partitioning with arbitrary bandwidth allocation (AQP-ABA). We also consider two other cases where either partitioning or bandwidth allocation is done arbitrarily and the other is using optimal value (i.e. O Q P - A B A , and A Q P - O B A ) . For all these cases, we measure the normalized quantization overhead as follows: N ^n{Pl) = ^Pl)/Y,Qi 2 = 1 We take the link's DP with different distributions in the range from 1CT1 to 1CT10 as an example for QoS. We measure the normalized quantization for the different cases mentioned above and compare it with the O Q P - O B A algorithm discussed in section 4,4. Figure 4.6 depicts the difference between Arbitrary Partitioning (AP) and Optimal Partitioning (OP) for a link with 5 service levels and QoS requirements distributed in 5 clusters and uniform bandwidth requirements as shown in the figure. We notice when using AP that the groups might be erratic and some flows may end up being assigned a much higher/lower QoS than what they ask for which causes discrepancy in utilizing the Chapter 4. QoS-Based Partitioning and Resource Allocation 69 link resources. OP, on the other hand, guarantees proper logical grouping for the flows and hence provide consistency in utilizing the link resources. Original flow £ m requirements m QoS Partitioning Arbitrary Partitioning 10 10 10 OoS Partitioning Optimal Partitioning F i g u r e 4.6: Difference between arbitrary and optimal partitioning. Figure 4.7 shows the normalized quantization overhead against variable sized sets of flows for a link with 5 service levels, QoS requirements distributed in 5 clusters and uniform bandwidth demands. We notice that O Q P - O B A consistently outperforms the other schemes by at least 50% for clustered QoS distribution. This is because O Q P -O B A guarantees the best logical grouping for the flows and selects the service level that Chapter 4. QoS-Based Partitioning and Resource Allocation 70 best fits each group. We also notice that O Q P - A B A outperforms the other 2 schemes which indicates that the effect of logical grouping is more crucial than allocating the bandwidth for clustered QoS distribution. 0.9 0.8 c °-7 o | 0.6 *— c § 0.5 o "§ 0.4 N 1 0.3 O Z 0.2 0.1 200 - e — OQP-OBA - * — OQP-ABA - * — AQP-OBA -0— AQP-ABA 400 600 N (no of flows) 800 1000 Figure 4.7: Variable sized sets for 5 service levels. Figure 4.8 depicts the effect of the link's total load on the normalized quantization for different partitioning and bandwidth allocation schemes using 5 service levels, 5-cluster QoS distribution and uniform bandwidth demands. Again, we notice that O Q P - O B A consistently outperforms the other schemes even for low link loads. We also notice that after specific link load, which is different for each case, the link cannot provide the QoS required without violating the QoS requirements on each group significantly. Therefore, even if the link is overloaded, O Q P - O B A guarantees graceful service degradation for Chapter 4. QoS-Based Partitioning and Resource Allocation 71 high link loads. This is a crucial feature especially in the absence of admission control mechanism. 10' c o 15 N I 10° o ~s E o z 10"' 0.7 0.8 0.9 1 1.1 1.2 1.3 Load F i g u r e 4 .8: Effect of link load for different parti t ioning and bandwidth allocation schemes. Figure 4.9 shows the effect of increasing the number of service levels on the normalized quantization using difference QoS distributions. We notice here that beyond 4 or 5 levels the normalized quantization tends to be almost constant regardless of the QoS distribution used. Since increasing the number of service levels may affect the complexity of the algorithm, this crucial result indicates that using 4 or 5 service levels wi l l achieve the trade-off between complexity and minimizing the normalized quantization overhead. Final ly, Figure 4.10 shows the effect of increasing the capacity divisions on the conver-gence of the O Q P - O B A algorithm for different number of service levels using uniform Chapter 4. QoS-Based Partitioning and Resource Allocation 72 Figure 4.9: Number of service levels for different QoS distributions. distribution for QoS requirements and bandwidth demands. We notice that the con-vergence happens for all values of L but tends to be faster for low values (e.g. L=2). However, even for high values of L , the convergence happens for a value of W less than 50. 4.6 Concluding R e m a r k s In this chapter, we have presented 2 algorithms for calculating the optimal partitioning and bandwidth allocation for a set of traffic streams with diverse QoS requirements for a link model with variable service levels. Such algorithms can be useful for service providers to design the network service levels that achieve the best granularity based Chapter 4. QoS-Based Partitioning and Resource Allocation 73 0.24 0.22' 0.2 | 0.18 w •S 0.16 c § O 0.14 h •S 0.12 h 1 g 0.1 0.08 0.06 0.04 10 - e — L = 2 - * — - L = 4 - * — L = 6 - 0 — L = 8 -0 0 0 0 oooooc 10 W (no of capacity divisions) 10 Figure 4.10: Number of service levels for different QoS distributions. on the different distributions for the QoS requirements and bandwidth demands. Our results using dropping probability as the QoS metric show that using 4 or 5 service levels will achieve the trade-off between complexity and granularity irrespective of the QoS distributions. They also show that using O Q P - O B A guarantees the best logical grouping and best selected service levels which achieve the best granularity. Moreover, using O Q P - O B A will guarantee graceful service degradation when the link is overloaded in the absence of admission control. 74 Chapter 5 Optimal Resource Allocation for Homogeneous Wireless Multicast In this chapter, we present a novel decentralized algorithm called O R A W M that achieves the optimal rates for a set of homogeneous multicast sessions such that the aggregate util-ity for all sessions is maximized. We present the formulation of the multicast resource allocation problem as a non-linear optimization model and highlight the cross-layer frame-work that can realize this problem in a real distributed ad hoc network environment with asynchronous computations. We also present a series of implementations based on differ-ent network settings and show that not only convergence to the optimal rates is attained in all these network settings but also network changing conditions such as mobility and dynamic channel capacity can be tracked in real time. °A version of this chapter has been published.[18 20] Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 75 5 . 1 I n t r o d u c t i o n The rapid growth of customer demands for fast, group-oriented, and mobile wireless services has mandated the need for inventing new wireless-based techniques that are scalable, bandwidth-efficient, and simple to implement and work with the existing wireless standards. Ad hoc networks empowered by multicast-based communication scheme is one of the potential strategies to achieve these features. Wireless ad hoc networks support peer-to-peer communication between active nodes through wireless links, and therefore, the network topology changes by changing the location of the wireless nodes caused by mobility. Active node has routing capability that allows it to create multihop path to any other node and, depending on its location, can forward packets for its neighboring nodes through that path. Therefore, ad hoc networks are extremely flexible, self-configurable, and do not require any infrastructure for their operation. This has opened the door for the possibility of providing many applications over wireless such as Videoconferencing, TV-over-wireless, intelligent transportation/traffic systems, field games, rescue and disaster recovery, and military operations. This consequently has led to the potential of using multicast as a bandwidth-efficient technique for communication. The one hop broadcast characteristic of the MAC layer in wireless ad hoc networks has triggered the use of multicast communication scheme as one of the natural strategies that can multiply the overall network throughput with very limited overhead. This is because multicast packets are forwarded once to reach all the multicast members in the neighborhood using a single transmission, and this effect increases even more in multi-hop Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 76 ad hoc networks. Multicast, however, introduces new challenges due to its complexity, and lack of stan-dards and techniques that can effectively allocate network resources. Efficient resource al-location is required to guarantee optimal resource utilization while providing system-wide fairness to different network flows end-to-end. The challenge in multicast resource alloca-tion is that, not only the resource allocation has to optimize access to network resources for each source-destination pair, but also it has to relate different source-destination pairs on the same multicast group to try to utilize the bandwidth efficiency of each multicast session (i.e intra-flow bandwidth efficiency) and achieve system-wide fairness across all multicast and unicast sessions (i.e. inter-flow fairness). One fundamental difference between multihop wireless networks and wired networks, in addition to the broadcast nature of the MAC layer, is the concept of location-based contention. In multihop wireless networks, flows may contend for the channel as long as they are within the interference range of each other, even if they are transferred on separate virtual wireless links. This imposes the problem of forming contention domains as part of resource allocation in order to map the logical network topology into the physical channel characteristics. The problem becomes trickier in case of multicast where different branches of the same multicast group may incur different levels of contention based on the location of the multicast members. In this chapter, we present an optimization model that captures the problem of mul-ticast resource allocation in wireless ad hoc networks and discuss the different possible Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 77 solutions to that model based on the network changing conditions and information dis-tribution amongst its wireless nodes. This optimization model must guarantee steering the entire network towards the optimal point in real time, and hence react to network conditions as they occur. Also, mapping the multicast resource allocation problem into an optimization model has the advantage of leveraging many efficient optimization tech-niques to devise and improve the problem solutions. The problem of resource allocation for unicast flows has been investigated before in [1, 10], and [6]. A common pricing mechanism has been used in all of them where each network resource calculates a price that represents the relationship between the load on this network resource and the capacity that it can offer. A utility is associated with each end-to-end flow to represent the flow's resource requirement. The objective then is to maximize the aggregate utility function for all flows subject to network resource constraints to achieve optimal resource utilization while providing system-wide fairness across all flows. The authors in [10] and [1] have studied the resource allocation in wired networks where they used the pricing mechanism to calculate a price on each link and then send this price through feedback to sources to calculate the required rate that opti-mizes the aggregate utilities of all network sources. Yuan et al. in [6] considered a similar pricing mechanism for allocating end-to-end unicast flow rates in ad hoc networks. A mechanism has been devised there to model the wireless nodes based on their locations into contention domains and then use them as the base for calculating the load on each contention domain versus the capacity offered by the wireless channel. None of these Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 78 studies, however, considered the multicast flows where resource allocation mechanism relates the multicast source-destination pairs to benefit from the bandwidth efficiency of multicast as a communication scheme (see example in Section 5.2.2). Resource allocation for multicast wired networks has been studied in [44, 45] and [7]. They define the multi-cast tree between one source and multiple receivers as group of terminal (non-junction) nodes and branch (junction) nodes and each downstream on a branch node contribute to the load of the link that the downstream traverses. However, as we will see in the following sections, the location based contention, one hop broadcast of the wireless MAC layer, and the absence of any centralized control in the multihop wireless networks make the problem in our case much more complex. The remainder of this chapter is organized as follows. In Section 5.2, we formulate the problem and provide some terminology. Our solution approach is presented in Section 5.3. We present our algorithm with its improvement to work in asynchronous network environments in Section 5.4. We then discuss the implementations of our algorithm in different network settings and provide a simulation-based study in Section 5.5. Finally, we conclude in Section 5.6. 5 . 2 M o d e l a n d p r o b l e m f o r m u l a t i o n We describe the model and explain the notations used in this chapter. Then we present a mathematical formulation of the optimization problem. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 79 5.2.1 Model and Notations We consider a wireless ad hoc network consisting of a set of nodes V spread over a wireless space each with a specific transmission range and interference range. We exploit the pro-tocol model explained in [70] and leveraged in [6] for wireless packet transmission. In this model, the transmission from node i is successfully received by node j G V) if (1) the distance between the two nodes is no more than a certain range (i.e. transmission range), and (2) for every other node k G V simultaneously transmitting over the same channel, the distance between j and k is more than a specific range (i.e. interference range). For some protocols which require acknowledgment from j to i (e.g. IEEE 802.11 MAC), node i is also required to be interference free at the time of sending the acknowledgment. We model the wireless ad hoc network as a directed graph G = (V, E) where E is the set of wireless virtual links produced as a result of nodes located within the transmission range of each other. Each wireless link e G E has two end nodes i, and j (i.e. e = {i,j}). The network is shared by a set of M end-to-end multicast groups. Each multicast group m has a unique source sm, a set of receivers Rrn = { r . m l , r m 2 , . . . } , and uses a set of wireless links Em and a set of nodes Vm for either receiving or relaying traffic. Thus, a multicast group m G M is defined by the triplet {sm, Rm, Em). Each multicast group has a rate xrn which is allowed to vary in the interval Im = [wm, Wm] [1], and / is the set of all such intervals. A fundamental difference between the unicast and multicast case, is the fact that one hop broadcast may be used to transfer traffic from one source to one or more destinations. To capture this notion, the one hop data transmission from one node Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 80 - - Wireless link ee E Sm Source node — Traffic flow bmij e Em r^ Receiver node >- Traffic flow end fmi Multicast subflow F i g u r e 5 . 1 : Wireless ad hoc network model. i to a set of nodes .7 C V,n within the multicast flow m along one or more wireless links (branches) is referred to as a multicast subflow of m or fmi. The set of multicast subflows on a multicast group m is referred to as Fm = {fmi, fm2, •••}, as shown in Figure 5.1. The set of all multicast subflows for all the M groups is referred to as F. Each multicast subflow uses one or more wireless links from one source i to a set of destinations J C Vm, he. fmi = {bmij • V6„„:J = {'i, j} j 6 ./}, with a cardinality Kmi equal to the number of branches of /„„;. We also define an active wireless link ay- G E to be the wireless link that carries traffic from at least one multicast group, and A C E is set of all such links. a,j refers the aggregated multicast subflow which is represented by the set of active links Uij j G J that are used by one or more multicast subflows fmi m € M, simultaneously. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 81 Based on the protocol model (explained in [48]) the traffic from two different subflows on two active wireless links contend with each other if either the source or the destination of one wireless link is within the interference range of the source or destination of the other wireless link. This means, that only one node on these two contending links may transmit packet at any given time. It is important to notice that for a multicast subfiow, different branches may experience different levels of contention based on the location of each destination on the subfiow. For example, in Figure 5.1, although branches bm$7, and 6 m 5 6 belong to the same multicast subfiow, they suffer different contention. The traffic on 6 m 5 7 contends with the set of active wireless links {(a 3 5, a3g), a4s, a-24, a13} , whereas the traffic on bm5(i contends with the set of active wireless links { ( 0 3 5 , a3 g), ci4g, a 24, a i 3 , agio} where links grouped with brackets identify the subgroups of links that carry the traffic from the same subfiow. This means that bm57 experiences less contention than bm5Q, and the same result could be derived for branches bmi2, and bmvi- Notice that 056 and a 5 7 do not contend because they carry the traffic from the same subfiow1. Due to the broadcast nature of the MAC layer and based on the scheduling mechanism used, if we increase the rate on these subflows beyond certain limit, some branches may suffer low throughput [72]. This intrafiow contention diversity maybe common in case of asymmetric network topology like the case of Figure 5.1. For simplicity, we assume that a packet is successfully transmitted over a multicast 'Here we assume that the multicast scheduler will guarantee that the acknowledgments from the group receivers (if any) may never contend. This can be achieved easily by assuming that each receiver has a certain time slot to send the acknowledgment back to the source [71]. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 82 subfiow fmi if (1) the packet reaches all destination nodes J on all the branches 6my; and (2) acknowledgments (using the notation of IEEE 802.11 MAC standards) have been received successfully from all these destinations back to the source node i [71]. This means that the maximum rate for subfiow fmi cannot exceed the rate that can be withstood on the most contended branch of that subfiow. Based on this assumption, the protocol model can be extended for multicast subflows as follow; the traffic from two different subflows on a group of active wireless links contend if either the source or any of the destinations of one subfiow is within the interference range of the source or any of the destinations of the other subfiow. To model the contention between the active wireless links, we use a contention domain mechanism [48] by forming a logical contention graph Gc = (Vc, Ec). Each vertex on that graph corresponds to the aggregated multicast subfiow au which carries the traffic from one or more subflows simultaneously. The links between two vertices represent whether the traffic on the two aggregated subflows contend with each other, which means any of the active links of one aggregated subfiow is located in the contention region of any of the active links of the other aggregated subfiow. A complete subgraph in Gc is referred to as a clique, and a maximal clique is the clique that is not part of any other cliques. This maximal clique represents the maximal set of active wireless links that contend with each other, which means that one "subfiow" within this clique may transmit a packet at any given time [6]. Therefore, the sum of the rates over this maximal clique cannot exceed the channel capacity achieved by using a particular scheduling mechanism in the MAC Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 83 layer (e.g. IEEE 802.11 DCF). Similar to the link in wired networks, the maximal clique is the resource entity that is used to drive the constraints in wireless ad hoc networks. As we will see later, a special consideration should be given to multicast subflows that have more than one branch in the same maximal clique in deriving these constraints. The following inequality formulates these set of constraints: where q is a maximal clique in the set of all maximal cliques Q, cq is the achieved channel capacity for clique q based on the scheduling discipline used in the MAC layer, and V£ C A are the set of vertices in Gc that belong to clique q. Note that unlike the unicast case [6] (where the active wireless link is used as entity to calculate the upper bound), we use the multicast subfiow (which groups one or more branches together) as the entity for calculating the upper bound within any maximal clique. This will reduce the number of constraints by removing any redundancy, while keeping the constraints linear and that will simplify the solution for the resource allocation problem as we will see later .We say that a multicast subfiow fmi € F uses the resources in a maximal clique q if at least one branch of fmi uses an active wireless link that exists as a node on Vf (see implementations in Section 5.5). In practice, the channel capacity achieved by a specific MAC scheduler may vary even with time. Thus, not only does the resource allocation algorithm have to converge quickly to the optimal values for multicast rates, but also, through online calculations, it has to track the changes in the achieved channel capacity of each maximal clique to maintain the trade-off between resource utilization, and system-wide fairness. Vqe Q (5.1) Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 84 5.2.2 Mathematical Formulation Each multicast group m G M is associated with a utility function Urn(xm) which measures the degree of satisfaction based on assigning a specific rate xm. The optimization problem then is to find the set of rates assigned to all multicast groups in M such that the aggregated utility function2 of all multicast groups, commonly referred to as the social welfare, is maximized. This can be formulated as a non-linear optimization problem as follows: P : maximize ^T^ Um{xm) (5.2) m€M subject to Tx<C <B Q (5.3) xm <E lm Vm G M (5.4) Equation (5.3) is the matrix form of (5.1) where x is a vector of all multicast group rates, and C is the vector of achieved capacities on all maximal cliques, r is the clique-group matrix with each element in F represents the number of multicast subflows within a maximal clique q. Throughout the rest of the chapter, we will make the following assumptions to facilitate the solution for the primal problem P: Assumption 1: There exists at least one vector x G I such that Y2me{FnvcQ)xm — cq Vq G Q and xm G Im (i.e. ]Cme(Fnv<?) ™™ — ci ^ 6 Q)- This means that admission control is out of the scope of this model. 2 We assume here that the utility function is additive, which means that the aggregated utility function for allocated vector x is the summation of all utility functions as defined by Equation 5.2. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 85 (a) Unicast flow pattern (b) Unicast contention graph (c) Multicast flow pattern (d) Multicast contention graph Figure 5.2: Example for resource allocation in unicast and multicast. Assumption 2: On the interval Im, all the utility functions Um Vm G M are increas-ing, strictly concave and twice continuously differentiable. Thus —U"n > "fm > 0. The importance of these 2 assumptions lies in the fact that Assumption 1 implies that problem P is feasible , i.e. it has a solution, while Assumption 2 forces this solution to be unique. Next, we present an example to illustrate the notations and highlight the difference between unicast and multicast in allocating rates in an ad hoc network. Figure 5.2 shows an example of an ad hoc network where there are 4 nodes: 1, 2, 3, and 4 connected Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 86 through wireless links as shown in the figure. Each of the Nodes 1, 2, and 3 needs to send traffic to the other 2 nodes, and Node 4 acts as the relay node for all traffic going from one node to another. Figure 5.2(a) shows the flow pattern to implement this scenario using only unicast flows. We notice here that each of the Nodes 1, 2, and 3 must send 2 unicast flows to the other 2 nodes . As shown in the figure, we need 6 unicast flows {ui, . . . , M 6 } , with rates represented by the vector x = {x\,......T6}. The aggregated subflows on each wireless link is represented by one node in the contention graph as shown in Figure 5.2(b). We notice here that all the subflows on all the links mutually contend with each other forming one maximal clique with an achieved capacity c1 as shown in Figure. On the other hand, Figure 5.2(c) shows the flow pattern in case of using multicast flows. We notice here that each node uses only one multicast group to send traffic to the other two nodes. We notice also that the multicast subflows(e.g. the one going from Node 4, to nodes 1, and 2), can leverage the broadcast nature of the MAC layer by using single packet broadcast to send data from Node 4 to the other two nodes simultaneously. Using this fact to implement this scenario, we only need 3 multicast groups {mi,7712,7713} for which rates are represented by a vector x = { x i . , x 2 , £ 3 } . Figure 5.2(d) shows the resulting contention graph representing each group of links used by multicast subfiow as a node on the graph. Here too the graph shows that all the subflows form one maximal clique q\, which means that only one node in the network can send a packet at any given time. Assume the achieved capacity on this clique is C\. then we can derive the Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 87 constraints in Equation (5.3) for unicast and multicast as follows: unicast : ^ 2 2 2 2 2 2 ^ x ' < c ' i multicast : ^ 2 2 2 ^ x ^ c i This shows that by using the notion of multicast subflow, which groups multiple branches together, the clique-group matrix dimension is reduced significantly in case of multicast. This is a key feature for multicast resource allocation especially for large networks. In this simple and symmetric topology, the solution can be guessed intuitively. Hence, to achieve optimum resource utilization while maintaining fairness amongst all groups, the elements in each of the vectors x and x must all have same value and the optimal value for each case can be calculated as follows: unicast : xu = cx/12 u = 1, • • • ,6 multicast: xm = C j /6 m = 1,2,3 which means that by using multicast, not only the number of flows is reduced (which means the processing overhead on each node is reduced), but also, the optimum allocated rate for each multicast group is close to double the value of the optimum allocated rate on any unicast flow (assuming the achieved capacities are almost equal, i.e. C i « c[). It is not hard to recognize that the effect of multicast intra-flow bandwidth efficiency will become even stronger when we increase the number of hops. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 88 5.3 S o l u t i o n A p p r o a c h Solving the resource allocation problem P centrally would require the knowledge of the utility functions and the knowledge of all contention domains and multicast groups which is impractical. Instead, we propose a decentralized scheme that minimizes the coordina-tion between networks nodes and adapts naturally to network changes. The key to this is the use of the duality theory [73] which suggests solving the dual problem by introducing additional dual variables called prices using the same notation like in [10], [6], [45] etc. 5.3.1 The Dual Problem The first step in our solution is to define the Lagrangian function L(x,p) for the opti-mization problem P as follows: L(x,p) = ]P Um(xm) + Y pq(cq - xrn rqm) msM qeQ = Y I Um(xm) - X m Y PlP<im j + Y P1C'' (5'5) m€M V qeQ J q e Q where p = (pq,q £ Q) is the vector of Lagrange multipliers. Notice that the first term in Equation (5.5) is separable in xm, which means that f Y Um(xm) - X m ^ PqFqm = YI J n f f ( Umipm) ~ Xm Yj Pd^l'" J "' meM V q€Q J rneMX"' '" \ q€Q / max x m e which means that this objective function can be divided into M subproblems. This decomposition of the problem solution into a set of subproblems each of which is easy to solve locally is a crucial advantage since it simplifies the overall solution and lays the base Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 89 for a layered protocol design. The objective function of the dual problem then becomes (see Section 3.4.2 in [74]) D(p) = max L(x,p) = pqcq + q£Q max Um{xm) - XmY\ Pq^qm (5-6) raSM \ </€<2 / and the dual problem D for the primal problem P can then be defined as follows: D : min D(p) (5.7) p>0 It is important at this point to mention two properties of this dual problem from our model standpoint. First, since the objective function of problem P is concave, the constraints in Equation (5.3) are linear, and based on assumption 1 that there is at least one feasible solution for x, then there is no duality gap (Proposition 5.2.1 of [73]). Consequently, since there is no duality gap, the set of dual optimal prices (Lagrange multipliers) will always exist and will be equal to the set of Lagrange multipliers pq\fq G Q (Proposition 5.1.4 of [73]). This suggests that by solving the dual problem in Equation (5.7) we can get optimal dual variables (which are the Lagrange multipliers) p*Vg G Q. Then, we will use this to solve the individual subproblerns each with objective 4>m{xm) = Um{xm) - xm ^2 p*qrqm Vm G M (5.8) Because these subproblerns are separated, they can be solved for each multicast tree (e.g. by a designated tree member like the source of the tree) without coordinating with other multicast trees. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 90 5.3.2 Interpretation of prices Here, pq may be interpreted as the price per unit bandwidth consumed at clique q. We can also define the aggregated price for group rn as a result of consuming bandwidth on all maximal cliques q 6 Q as follows: Kn = Y vqrqm (5.9) <;:(f ,mnvc")^0 For each clique, the price is the product of the price per unit bandwidth of that clique and the number of multicast subflows of group m that exist in that clique. To calculate the price in Equation (5.9) for any group m in a centralized fashion we require one node to have knowledge about all cliques and the number of multicast subflows end-to-end in m that exist in each clique. Because this is not practical, we must devise a mechanism for calculating this group price in such a way that allows each node to contribute to the end-to-end calculation. The first step in this mechanism is to decompose the group price into individual subflow prices. In other words, the group price for group m will be the aggregated price of all the multicast subflows that belong to group m. The price of one multicast subflow is the summation of the clique prices that this multicast subflow belongs to. This indicates that this price is correlated with both the congestion on this subflow and its span which is measured by how many cliques this subflow exists in. The multicast subflow fm,i belongs to any clique q if at least one of its branches (bmij Y) € J ) belongs to that clique. In other words, two subflows belong to the same clique (contend) if at least one branch on each subflow has a source or a destination in the interference range of the other branch. The following example illustrates this part of the model. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 91 Example for calculating group price Consider the example in Figure 5.3. The network topology shown in Figure 5.3(a) has one multicast group mi which has two receivers (Nodes 5 and 6), and traffic that goes along four multicast subflows as shown in the figure. Figure 5.3(a) shows the contention graph corresponding to this network topology and the two maximal cliques with Prices 'Pi and p2 as shown. Based on Equation (5.9), the price for the multicast group mi is A m = 3pi + 3p2i which is the sum of the product of the number of subflows of m\ in each clique and the price of this clique. If we define the price for a subfiow fmi or Xmi to be the total price of all the maximal cliques such that there is at least one branch of the subfiow in that clique,i.e. Xmi = Ylqe{fminQ)P<i> t n e n w e c a n r e w r i t e the group price as It is easy to see that Equation (5.10) is equivalent to (5.9). The reason for transforming the group price into this form is to facilitate the group price calculation in a distributed environment where we have all the nodes that are members of the group contributing in an accumulative fashion to the price calculation. Furthermore, for multicast group price calculation, we must consider all the branches of the multicast tree in the calculation because different subflows may exist in different branches of the tree. In the following sections, we will describe our approach for group price calculation which is a crucial part of our solution for resource allocation for wireless multicast. follows: (5.10) Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 92 °;({2} fl2{3,4) (a) Network topology (b) Contention graph F i g u r e 5 . 3 : Example for calculating the multicast group price. 5 . 4 Optimal resource allocation for wireless multicast (ORAWM) First, we present a distributed iterative algorithm that solves the primal problem P by applying the gradient projection method [73] to the dual problem D. This implies that the clique prices pq n+l) at iteration n + 1 are adjusted in the opposite direction to the gradient V.D(p) as follows: P" U" dPq 1 (5.11) where a > 0 is the step size, and [z}+ = max{2,0}. Since Um m G M are concave functions, D(p) is continuously differentiable (pp. 669 in [74]) and hence its gradient based on Equation (5.6) is dDjp) dpq ^ ~] %m, (p) Fqm m : ( F , „ n V c ' ) / 0 qeQ (5.12) Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 93 which is the difference between the clique's achieved capacity and the load demanded on that clique. The clique load is characterized by the rates of all groups that belongs to this clique multiplied by the number of multicast subflows they have in this clique. Substituting Equation (5.12) into (5.11) we have p (n+l) = b(n) _ a { C q _ Xm(p^)rqm)}+ (5.13) Although the dual objective in Equat ion (5.8) is not separable in p, the iterative algorithm in Equation (5.13) can be implemented in a decentralized way because only the local rates within each clique needs to be coordinated. Finally, to calculate the rate for each group we can rewrite Equation (5.8) as a function of the group price as follows: <t>m{xm) = Um(xm) - xmXm (5.14) which represents the net benefit or the difference between the utility and the price for group m by allocating rate xm. By Assumption 2, (j>m(xm) is strictly concave and twice continuously differentiable, and hence a unique maximizer exits and can be obtained as follows: Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 9 4 and hence the maximizer xm(Xm1 ) at iteration t is if U'-1^m))<W, *m(& = {w, m if u'-\xW)>w,, rn (5.15) U'^(X^) o.w where wm, and Wm are defined by the rate interval Im. 5.4.1 Group price calculation A crucial part of our algorithm is how to calculate the individual group prices A m in a decentralized way given the prices of the individual maximal cliques pq \/q € Q- To facilitate discussion in this part, we introduce the following new terms: 1. irm(i) : the parent node of node i along the tree of group m. 2. Xm(i) : the accumulated price for group m at node i.. Note that there is no parent node for the group source, i.e. 7rm(s.m) = 0, and the accumulated price at the source Am(s.m) = 0. We can then define the accumulated group price recursively as follows: where Kmnm^ is the cardinality of subflow /m7rm(,:). The reason for introducing the concept of accumulated group price will become evident when we discuss the different implementations of our algorithm (see Section 5.5.2). Equation (5.16) states that the A/71 (0 = Am(?rm(i)) 4- A. V* G VM (5.16) Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 95 accumulated price for group m at node i is the summation of the accumulated price at the parent node of i and the price for the multicast subfiow / m 7 r m ( , ; ) , divided then by the cardinality of this subfiow i ^ T O r r m ( i ) - This recursive algorithm will be the base for calculating the group price as illustrated by the following theorem. Theorem 5.1. : If3m C Rm such that %n ={i : fmi = 0 Vi} defines the set of terminal nodes for group m, then the group price can be calculated as follows: Proof. Assume that Qm(7t) is the set of all nodes i E Vm of group rn such that the depth of i is h, and H is the maximum depth of the tree of group m. Now it is easy to recognize that: A m S m ~t~ El A m i ~r" * * ' "f" El A m i We proceed by induction based on H as follows: • For II = 1: E A,„(i) = E A m ( i ) = K m s m \ n s m l K m S m = A m • For iY = 2: = A m . s m ~f~ A m i A m Notice that if / m j = 0, then \ m i = 0 . Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 96 • Assume that for H = n — 1: E ^m(i) = A m = i eOm(n - l ) Xrnsrn ~f ' ' ' ~t~ Am ?; • Hence, for H = n: E A m ( i ) = E mi — Kns1n + - ' • + E -A?m — A, and therefore the result follows. • Theorem 5.1 implies that in order to calculate the price for group m, we need to calculate the accumulated price on each branch using Equation (5.16) until we hit the terminal node of this branch. Then, send this accumulated price back to the source (or any other designated group member) to calculate the group price by simply adding the accumulated price of all branches. This simple mechanism for calculating the group price facilitates our solution due to the following features: 1. It is simple to implement using one header field that stores the accumulated price for all branches of subfiow fmi (i.e. note from Equation (5.16) that the accumulated price is the same for all branches that belong to the same subfiow). 2. It allows for distributed computation because each node needs to know (for each group) only the accumulated price for its parent node and the price of the next subfiow. Then, it performs a simple calculation to get the accumulated price for the following nodes. 3. It also allows for asynchronism because the source does not need to wait for all accumulated prices from all branches to calculate the group price and the next Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 97 group's optimal rate. Instead, it uses estimation based on the previously received values as will be shown next. Now we illustrate the result of Theorem 5.1 by an example. Consider the network topology in Figure 5.3. We can derive the accumulated price at Nodes 5, and 6 based on Equation (5.16) as follows: Ai(5) = ( A u + A 1 2)/2 + A 1 3 = 2Pl +p2 Ai(6) = (A n + A 1 2)/2 + A 1 4 = 2p2 + P l and we can easily see that A m = Aj(5) + Ai(6) = 3pi + 3p2. 5.4.2 O R A W M : Synchronous Distributed algorithm ( O R A W M . S D ) Now we describe the first version of our distributed algorithm where we assume that all the calculations happen in synchronization at specific time instances. Figure 5.4 depicts the main procedures performed in the network for calculating the optimal rates for each multicast group. This algorithm works by assuming that for each clique in the network, there is a representative node that has the topology information for the entire clique. This node will receive the rates for all the active multicast groups and calculate the clique price based on that. This node will then communicate this price to all the nodes within that clique to perform the subflow price calculations. In order to prove the convergence of Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 98 Clique procedure (by clique q): At iterations n = 1.2, • • • 1. Receive rates x'm from all groups rn where Fm n V§ £ 0 2. Update clique price as follows P{qn+1) = [pqn) - a(cq - Em:(Fmnv^)#0 xm(p(n))rqm)}+ 3. Send pqn+1^ to all nodes of group m such that Fm n Vcq ^ 0 Subflow procedure (by subflow fmi): At iterations n = 1,2, • • • 1. Receive prices from all maximal cliques q where D Vcq ^ 0 2. Calculate the subflow price (per hop price) A r r„ as follows A™ — Z^ 9 :( / ,„,nv;?)^0P'/ 3. Calculate the accumulated price on each branch brnij G / m j 4. Forward Xm(j) to all children subflows of / m ; , if no children, send back Xm(j) to sm Group procedure (by group source sm): At iterations n = 1,2, • • 1. Receive accumulated prices Am(?') from all branches of m Vi £ Qf m 2. Calculate the group price A m as follows A m = ! I i e Q m Am('i) 3. Calculate the next group rate as follows „.(™+1) _ rr' —lc \(™)\ 4. Send to all cliques q where Fm 0 V<? ^ 0 Figure 5.4: ORAWM: Synchronous Distributed algorithm. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 99 this algorithm, we define the following new terms: 1- Ym — J2qeQ ^qm which measures the number of subflows in clique q for group rn, and Y = rnax m e M YlqeQ ^qm indicates the number of subflows for the biggest group rn £ M. 2. Zq = YlmeM Fqm which measures the number of subflows of group rn in clique q, and Z = maxg€Q EmeA'/ Fam indicates the number of subflows in the most congested clique Q&Q. 3. 7 = m a x m £ M 7 m indicates the upper bound on all -U"n{xm) Vm £ M. Now, assuming that the initial price for each clique is feasible, i.e. pq > 0\/q £ Q, we can obtain the following convergence result: T h e o r e m 5.2. : For step size values of a that satisfy the inequality 0 < a < 2j/YZ, starting from any initial rate x(0) [xm £ /,„ V???, £ M), and clique prices p(0) > 0 Vo £ Q, every accumulation point (x*;p*) of the sequence (x(n);p(n)) generated by the Algorithm in Figure 5.4 is primal-dual optimal. The proof is shown in details in Appendix B. 5.4.3 O R A W M : Asynchronous D is t r ibu ted a lgor i thm ( O R A W I V L A D ) Our O R A W M L S D algorithm in Figure 5.4 assumes that updates at the cliques, subflows, and groups are synchronized which means that each of the iterations n = 1, 2, • • • occurs Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 100 at the same time in all three procedures. This restricts the calculations to be performed by minimum number of nodes in order to guarantee the synchronization amongst these nodes. Thus, it is better to elect a node within each clique to act as the master node that performs clique price calculations. Similarly, elect a group representative node (group source, or group leader as we will see later) that performs the group price based on which the next group rate is updated. Such synchronization, however, is difficult to achieve even between few number of nodes and requires lots of packet overhead to convey the synchronization information. Besides, the clique master election process is also difficult to achieve in real ad hoc networks because of mobility. As network nodes start to move, the clique topology changes and hence the master node of the clique may change. This calls for a modification to-this algorithm that works asynchronously on all the group members in such a way that distributes the calculations without any synchronization requirements. In the following, we present the asynchronous version of our algorithm ( O R A W M - A D ) and prove its convergence. This asynchronous model and the proof of convergence follow the class of partially asynchronous algorithms which were first discussed in Chapter 7 of [74]. For this partially asynchronous algorithm, we still assume that each clique has a master node denoted as vq, which performs the clique procedure through which a node calculates the estimated clique price and sends it to all nodes which have a subflow be-longing to that clique. In our implementations, however, we will show that even if the clique price calculations are performed by each node independently and asynchronously, Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 101 convergence is still attainable. Each node which is a member of any multicast group m G M performs the subflow procedure by receiving the clique prices for all cliques such that node i has a subflow fmi which belongs to that clique. This node then calculates the accumulated price through the recursive Equation (5.16), and forwards this price to children nodes. Finally, as we hit a terminal node of group m G Q f m , the accumulated price for that branch is fed back to the group source for preforming the group procedure through which the group source calculates the group price, and hence the next group rate. We also make the following assumption for the maximum delay bound between any two nodes: Assumption 3: For all groups m G M , cliques q G Q, and nodes i G M, the time between consecutive updates is at most B time units. Now, let T = {0,1,2, • • • } be the set of times at which either the rates or the prices are updated at any node. Hence, we define some time instance terminology as follows: 1. Tq C T: the set of time instances at which master node v(q) updates pq. 2. Tm C T: the set of time instances at which node i G M, which has fmi G Fm updates \ m i and \m{i). 3. Tm C T: the set of time instances at which the source of group m updates xm. The main idea of this asynchronous algorithm, is that for any update at any node, the node may not have the exact current value of either the rate or the price. Instead, it receives a sequence of recent values at different time instances. Therefore, the node will Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 102 use a weighted average of these values in estimating the price or the rate at any given time. The details for our asynchronous algorithm ( O R A W I V L A D ) are shown in Figure 5.5. This asynchronous model is general and can allow for any update policy for the rates or prices. For example, the accumulated price fed back to the source from some terminal nodes may be delayed or lost for some A(i, r) r G [t — B,... , t], but we can still guarantee the convergence by estimating the accumulated price based on the recent received values. Also, the algorithm attains convergence using some popular update policies such as the following: • L a t e s t i n s t a n t u p d a t e : only the last received clique price p,(r) for some r G [t - B, - •• ,t] is used to estimate A.m(t), i.e. bj(t ,t) = b\{t!,t) = b^tf ,t) = 1 if t = T and 0 otherwise. • L a t e s t ave rage u p d a t e : only the average over the latest k received values is used for estimation, i.e. 6?(/j', t), b\(t', t), b^t', t) > 0 for t' = r - k + 1, • • • , r and 0 otherwise. The support for these different update policies demonstrates the versatility of our asynchronous algorithm. The following theorem states this convergence result. T h e o r e m 5 . 3 . : For step size values of a that are sufficiently small, starting from any initial rate x(0) (xm G Im V m G M), and clique prices p(0) > 0 V17 G Q, every accumulation point (x*\p*) of the sequence (x(t);p(t)) generated by the asynchronous Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 103 Clique procedure (by clique q): At times t € Tq 1. Receive rates xm(t) from all groups m where Fm fl Vt? 7^ 0 and keep afm(£ ) for (i — B) < t < t 2. Estimate the rate xm(t) as follows: *m(0= E b]{t.t)xm{t) with E 6?(«',t) = l t'=l-B l'=t-B 3. Update clique price as follows p,(t + 1) = [p,(t) - a{cq - E *m(*)r,m)]+, Vi G T, and p,(t + 1) = p„(t) Vi £ T, 4. Send p ( /(i + 1) to all nodes of group rn such that F,„. n V'c'; 7^ 0 Subflow procedure (by subflow fmi): At times i e 1. Receive prices pq (i ) from all maximal cliques q where fmi fl V c ' ^ J and keep pq(t ) for (i - B) < t < t. 2. Estimate the clique price pq(t) as follows: = E 6*(t',i)p,(0 with £ 6j(t',t) = l t ' = t - B t'=t-B 3. Calculate the subflow price (per hop price) A m , as follows Ami( t + 1) = Eg :(/minV,?)?£0P«(*) 4. Calculate the accumulated price 011 each branch fjm?'y £ /Vm A m ( j , i + 1) = A m ( i . o + ^ ( t + i ) V j . 6 j v t 6 ^ ^ A m ( j - t + l) = A m ( j , i ) Vi g T^, 5. Forward A,„(j,i + 1) to all children subflows of /,„*, if no children, send back A m ( j , i + 1) to sm Group procedure (by group source sm): At times i € Tm 1. Receive accumulated prices \m(i, t ) from all branches of rn Vi € 3fm, and keep A„,(i, t ) Vi G $ m and {t — B) < t < t. 2. Estimate the accumulated price for each terminal node i £ Q'm as follows A m M = E lin(t',t)\m(i,t) with E f/m(i',f) = l t'mt-B t'=t-B 3. Calculate the next group price A m ( i + 1) as follows A m ( i + 1) = Eisa,„ ^m{i,t) 4. Calculate the next group rate as follows Xm{t + 1) = U'-l{Xm{t + 1)) Vi e T,„ and x m ( i + 1) = xm(t) Vi £ T m 5. Send xm{t + 1) to all cliques q where Fm n V c ' ^ f ) Figure 5.5: ORAWM: Asynchronous distributed algorithm. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 104 algorithm in Figure 5.5 is primal-dual optimal. The proof of this theorem is in Appendix B. 5.4.4 T ime-vary ing environment The two algorithms discussed so far, namely: O R A W M _ S D , and O R A W M _ A D with their convergence analysis, assume that the cliques' achieved capacity and the set of group utility functions are not functions of time (i.e. they do not change with time). However, due to online calculation, and subproblem decomposition, it can be shown that the algorithms work in the case when these quantities change with time. For example, the clique's capacity may be time varying depending on the scheduling discipline used at the MAC layer. In this case, the clique procedure in Figure 5.5 will be the same except that in computing VD(p(t)) at step 3, the current clique capacity cp(t) is used in place of the constant capacity cp. The same applies to the time-varying utility functions Um(xm,t). In general, if the change in the environment parameters is slow relative to the convergence rate of the algorithm, the algorithm can track the changes in the optimal rates based on changing these quantities with time. This is shown in our experimental evaluation discussed in the following section. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 105 5 . 5 E x p e r i m e n t a l E v a l u a t i o n In this section, we present a group of implementations for our algorithms in different wireless networking environment settings. We evaluate the performance of our algorithms using a set of simulation environments implemented using the ns-2 simulator. 5.5.1 Implementations overview We study the performance of our wireless multicast algorithm in different simulation environments as depicted in Figure 5.6. For convenience, we divide the implementations into two categories. The information distribution category defines three main simulation environments based on how price and rate information are handled by the network nodes. The first environment, referred to as O R A W M . C S , assumes that all the price and rate calculations for all multicast groups are performed by a designated node. This means that this node must have the topology information to construct all the maximal cliques and calculate the group prices for all multicast groups. Although such an environment is not practical and it poses many deployment issues especially in large networks, it is a straightforward way of guaranteeing synchronization, and hence would be interesting to compare the asynchronous environments against it. The second environment, referred to as O R A W M - P D A , implements the algorithm in Figure 5.5, assuming a clique master node for each clique, which performs the clique price calculations asynchronously as described before. Although this environment is more practical than the first one because of its asynchronous nature, it may still pose some deployment difficulties because of its Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 106 Centralized/ synchronous (ORAWM_CS) Implementation Categories Channel dynamics Information distribution Partially Distributed/ Fully Distributed/ n t t -, asynchronous asynchronous Constant capacity (ORAWM_PDA) ( O R A W M F D A ) Time-varying capacity Figure 5.6: Simulation environments. intra-clique centralized calculations. Communication between the master node and all other nodes within a clique each time the price changes causes some communication overhead. Also, electing a master node for each clique each time the topology changes may be complicated especially for networks with mobility or frequently changing topology. In the. third environment, referred to as O R A W M _ F D A , each node performs the clique price calculation independently based on the topology information it has. In [6], it is shown that, for clique construction, the status of all wireless links should be reported to all nodes as far as three hops away. This will enable all nodes to completely determine all the cliques containing any of its adjacent links'3 and hence the node will be able to perform clique and subfiow price calculations without having to coordinate prices with other nodes. This eliminates the communication overhead required to convey clique price information and does not require any intra-clique centralized calculations. Each of these three simulation environments can work under one of two network conditions illustrated by the channel dynamics category in Figure 5.6. One scenario 3Notice that this result applies directly to the clique construction for the multicast subflows. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 107 Table 5.1: MAC and physical layer parameters used by our simulations. Transmission range 250m Interference range 550m Radio propagation model Two-ray ground reflection Channel parameters basic rate 1Mbps data rate 1Mbps Simulation wireless area 1000 x 1000m2 assumes that the MAC layer scheduling is ideal in the sense that it can always achieve the wireless channel capacity (i.e. channel utilization is 1). The other scenario is more practical, because it can track the changes in the channel capacity regardless of the scheduling technique used in the MAC layer using window measurement techniques such as the one presented in [75]. Hence, it can work with almost any MAC layer scheduling. For this scenario, we use the common I E E E 802.11 DCF as the MAC protocol with multicast extensions as presented in [71], Table 5.1 summarizes the MAC and physical layer parameters used by our simulation environments. 5.5.2 Solution architecture and deployment Deploying our solution to real networks requires cross layer design and entails some modifications to the MAC, network, and transport layers. Figure 5.7 depicts the cross-layer architecture of our solution O R A W M based on the algorithm in Figure 5.5. The figure shows the main procedures of O R A W M (on the right hand side) and its interaction with the different layers including MAC, routing and transport layers. In the following, we highlight the modifications and show the interaction of O R A W M in each layer. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 108 Figure 5.7: Cross-layer architecture for O R A W M 1. M A C layer:. Unlike unicast, existing IEEE 802.11 MAC protocol does not provide any media access control recovery on multicast/broadcast packets. This means that the RTS/CTS/ACK mechanism is not used for multicast/broadcast packets from one sender to all the receivers on the same multicast subfiow. As a result, the reliability of the multicast/broadcast service is reduced due to the increased probability of lost packets resulting from interference or collisions. For time-varying channel capacity at different contention regions (cliques), a reliable deterministic technique is required for channel capacity estimation. The channel capacity estimation for multicast packets poses a real challenge because it requires monitoring the multicast packets on both the sender and all the receivers of the subfiow, and hence it calls for a synchronized clock to measure the delay of sending the multicast packet from the sender to all the receivers. Because Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 109 MRTS delay CTS1 CTSn data ACK1 ••• ACKn Packet f available at a interface queue Figure 5.8: Multicast-aware MAC protocol. this is not a practical solution, we devise a deployment technique which combines the multicast aware MAC protocol (MMP) [71] with a bandwidth management mechanism for measuring the channel capacity based on [75]. First, MMP provides a MAC layer support for multicast traffic by attaching an Ex-tended Multicast Header (EMH) which combines the address of the nexthop nodes using some routing information. The MAC layer then uses the EMH field to support an ACK based data delivery from the sender to all the receivers on the same multicast subflow. After sending the data packet, the transmitter waits for the ACK from each of its des-tinations in a strictly sequential order (hence, avoids the contention between the ACK packets on the sender side). A retransmission of the multicast packet is performed only if the ACK from any of the nodes in EMH is missing. The retransmission is clone using a similar technique like RTS/CTS, but this time using Multicast RTS or MRTS/CTS. Figure 5.8 shows the full scenario from the sender side for an MRTS/CTS/data/ACK from one sender to n receivers. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 110 Second, bandwidth estimation can then be performed using a measurement-based win-dow technique such as the one presented in [75] and adopted by [6]. In this technique, the achievable bandwidth of each multicast subflow is measured based on its recent received packets at the sender of this subflow. As shown in Figure 5.8, the packet becomes avail-able at the MAC layer interface queue at time ta, and when all the acknowledgments are received at the sender node, we claim that the packet is received at time tr. The trans-mission delay over this subflow is then tr — ta, which includes the contention period, and retransmissions (if any). We then use a window w of packets to measure the achievable bandwidth observed by the subflow as follows B(fmi): B(fm W - Z • Vw t{ - V where z is the packet size. 2. Network layer: The price and rate information are exchanged in the same level as the routing information. We have integrated our solution with the Multicast Ad hoc On demand Distance Vector (MAODV) presented in [76] for providing a distributed routing scheme for the multicast sessions. MAODV extends (AODV) [77] to offer multicast capa-bilities by building multicast trees as needed and providing tree operations (e.g. merge, and prune trees) for tree maintenance in a distributed fashion. For clique construction and price calculation, we use a multicast-based status which is conveyed in a gradient information header (gib) for each aggregated subflow within the clique. To accommodate network changes (i.e. changes due to mobility or source start/stop), this multicast-based status is stored using a caching mechanism in each node with expiry timestamp that Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 111 controls its lifetime. We piggyback this status information onto the HELLO packets and allow it to be transmitted as far as three hops away to enable each node to construct the clique and calculate the clique price. For clique construction, we use the Bierstone algorithm described in [78]. The accumulated price and group rate are also piggybacked within the price 'information header (pih) onto the data packets. The tree terminal nodes notify the group source of the new accumulated price by sending a feedback packet (fbp) as shown in Figure 5.9. This feedback packet is then used by the source to calculate the group price as explained in Section 5.4.3. These feedback packets need not be synchro-nized and in fact even if some of them are delayed or lost, the source can still estimate the group price using the estimation procedure highlighted in Figure 5.5. Figure 5.9: Price and rate control packets. 3. Transport layer: Our algorithm provides an end-to-end flow control in addition to optimizing network resources because it performs online control to the rates used by each transport agent of the multicast groups. Therefore, to minimize the communication Chapter 5. Optimal B.esource Allocation for Homogeneous Wireless Multicast 112 overhead we use UDP as the transport protocol and we add the rate and price adjustment as part of sending and receiving data. In particular, we add the functionality of sending a feedback packet asynchronously from the terminal nodes every time the accumulated price changes (i.e. before convergence happens). We also modify the sender transport agent to adjust the sending rate based on the summation of the accumulated prices from all terminal nodes4 . Using the result from Theorem 5.3, the sender can calculate the rate asynchronously based on the estimated value of the accumulated prices from all terminal nodes every time it receives a feedback packet from one of these terminal nodes. 5.5.3 S imulat ion results In/all our experiments, we use the utility functions Um(xm) = ,9m ln(xm) xm > 0 for im-posing proportional fairness amongst the multicast groups where gm is the differentiation gain, i.e. xrn(t) = (jm/\m(t)- Unless otherwise stated, we use the latest instant update for asynchronous calculations. Convergence for different simulation environments We first study the convergence of our O R A W M algorithm in the different implemen-tations explained in Section 5.5.1. We take as an example the network in Figure 5.2 with 3 multicast sessions as shown in Figure 5.2(c) with equal differentiation gain, i.e. gm : 1 Vm € M. However, we start each of these sessions in a different time to test the ''The termination criteria in all our simulations are |A m ( i ) — A* u | < \.i Vm e M with (i = 1 0 - 5 Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 113 ability of our algorithm to track network changes. The start times of sessions m\,m,2, and m 3 are 20,40. and 60 seconds respectively, and the initial rates x'm(0) Vm € M are selected from a uniform distribution in the range [50, 250] kbps. We fixed all the other parameters including the step size, and we measured the rate of each multicast session against time. Figures 5.10 and 5.11 show the results for fixed channel and time-varying channel capacity respectively. We notice in all these cases that our algorithm converges in the three environment set-tings and regardless of any initial settings, or the-initial rates set in each case. We notice that the only difference between O R A W M . C S and O R A W M _ P D A implementations is in the transient value of the rates against time. However, neither the convergence speed nor the optimal rates are affected by the asynchronism that we introduced by the O R A W M T D A implementation, which confirms the result we stated in Theorem 5.3. We notice that convergence also happens using the O R A W M . F D A implementation with occasionally very small error in the calculated optimal rates as shown in Figures 5.10(c) and 5.11(c). This small error happens because the clique price calculation is performed by each node within the clique independently based on the current status of the subflows. This small error, however, seems to be acceptable and should not increase by increasing the number of hops since it is localized within each clique. In Figure 5.11, we observe that although the MAC channel capacity (i.e. the basic, rate of sending data in IEEE 802.11 DCF) is set to 1Mbps, the achieved channel capacity changes with time and does not go above 800Kbps. Nevertheless, our algorithm continuously tracks the Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 114 change in channel capacity and provides proportional fairness amongst all the multicast sessions based on the current available channel capacity. 550 500 450 400 [A 350 300 0) £ 250 200 150 100 20 40 60 80 100 120 140 160 180 200 time (s) 550 500 450 400 W 350 •B £ . 300 01 gj 250 200 150 100 60 80 100 120 140 160 180 200 time (s) (a) O R A W M - C S (b) O R A W M _ P D A 550 500 450 400 & 300 JD 250 200 40 60 80 100 120 140 160 180 200 time (s) (c) O R A W M J F D A Figure 5.10: Convergence for different simulation environments using fixed channel ca-pacity. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 115 20 40 60 80 100 120 140 160 180 200 20 40 60 80 100 120 140 160 180 200 time (s) time (s) (a) O R A W M . C S (b) O R A W M . P D A 400 20 40 60 80 100 120 140 160 180 200 time (s) (c) O R A W M J F D A Figure 5.11: Convergence for different simulation environments using dynamic channel capacity. Effect of step size a on convergence using the O R A W M . F D A implementation In the previous experiment, we set a so that the convergence rate is in the best way possible. Now, we study the impact of this step size on the convergence using the Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 116 i 2 5 0 i 200! . optimal m t • optimal ms optimal m (d) a = 9 x l f r 7 (e) a = l f r 6 F i g u r e 5 . 1 2 : Effect of step size a on convergence using the O R A W I V L F D A implemen-tation. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 117 O R A W M . F D A implementation. We take the same network explained in the previ-ous experiments, we start the three sessions at time t = 20 seconds, and we set the differentiation factors ai,a2, and a 3 as 3, 2, and 1 respectively. Figure 5.12 shows the convergence behavior at different values of a. It is clear that our asynchronous algorithm achieves the global optimal rates for small values of a. As intuitively expected, however, for very small values of a < IO - 7 , the convergence rate tends to be slow (see Figure 5.12(a)). For large values of a (e.g. a = 10~6), the algorithm may not converge to the optimal rates. Effect of estimation window B on convergence using the O R A W M _ F D A implementation So far, we have used the latest instant update for asynchronous calculations. This means that, we only consider the latest value when we estimate the clique and group prices. In this experiment, we study the effect of using an estimation window B seconds, and estimate the prices based on the average in this window (i.e. b''(t',t) = l/n,blq(t',t) — 1 /n , and blm(t' ,t) = 1/n" Vi V<j Vm, where n, n , and n" are the number of received values within the window B). We notice from the results in Figure 5.13, that the convergence occurs in all values of B. However, by increasing B the convergence tends to happen with less fluctuations in the transient rates before they settle on the global optimal values. Hence, using a moderate estimation window might be useful, especially for large multicast trees, because some receivers may get overwhelmed by these rate fluctuations. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 118 We also notice that using large values of B (see Figure 5.13(c)) may affect the speed of convergence, and hence large estimation windows also might not be desirable. 550 500 450 400 . 350 I 300 ! 250 200 optimal m, optimal m, optimal mn 20 25 30 35 40 45 50 55 60 (a) B = 0.01 second 500 450 400 350 | 300 f 250 200 150 (b) B = 0.1 second . Optimal m ] . optimal m„ . optimal m. 20 25 30 35 40 45 50 55 60 time (s) (c) B = 1 second Figure 5.13: Effect of estimation window B on convergence using the O R A W M J F D A implementation. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 119 Effect of differentiation gain and session start/stop time on convergence using the O R A W M _ F D A implementation In this experiment, we use fixed channel capacity, assuming that the scheduling mecha-nism used in the MAC layer is ideal (i.e. channel utilization is always one). In addition to the session start times we set the stop time for sessions mi,m 2,rn,3 to 120,140,160 seconds respectively. We show the difference between the rates obtained using our algo-rithm running in a totally distributed and asynchronous environment, and the optimal theoretical rates calculated offline. Figure 5.14 shows the results using differentiation gains 3, 2, and 1 respectively. We notice that the algorithm converges online to the op-timal rates that guarantees maximum aggregated utility providing proportional fairness amongst all active multicast sessions at any given time. Furthermore, it responds fairly quickly to the changes resulting from adding or removing multicast sessions. Effect of mobility and route changes on convergence using the O R A W M _ F D A implementation In this experiment, we study the impact of mobility and route changes on our algorithm using the network in Figure 5.15(a). The corresponding contention graph for this case is shown in Figure 5.15(b). We generate a mobility pattern where Node 2 moves from Position 1 to Position 2 as shown in the figure using a speed of 3 m/s and a pause time of 20 seconds. We start 2 multicast sessions m\ and mi with receiver sets [4, 5] and [3, 6] respectively at time 20 seconds. Figure 5.16 shows the rates calculated by our algorithm Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 120 1 m2 • m 3 optimal m 1 optimal m 2 optimal m "T1 II I 60 80 100 120 140 time (s) 160 180 200 Figure 5.14: Convergence with different differentiation gains and start/stop times. • 3 ( 5 ) " 4 { 6 ) (a) Network topology (b) Contention graph for current position Figure 5.15: Impact of mobility and route changes. and the throughput observed at receivers [u,r0,r$}r*] respectively. The figure shows 3 different regions depending on the change of routes resulting from the node mobility. In Region 1. only node 4 is receiving traffic for group m\ and node 6 is receiving traffic for Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 121 200 time (s) (a) Calculated group rate (b) Receiver throughput F i g u r e 5 .16 : Convergence with mobility and route changes. Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 122 group m 2 . As expected in this case, our algorithm discriminates against the flow with longer path because it consumes more network resources, giving Group m i higher rate in this case (note that this discrimination can be compensated, if desired, by changing the utility functions). As Node 2 moves to Region 2, the routes for which are shown by Figure 5.15(a), all receivers become active and the optimal rates converge to the same value for both groups. The scenario in Region 1 will then be reversed in Region 3 giving m 2 higher rate in this case. Convergence in random network using the O R A W M _ F D A implementation In this experiment, we study the convergence behavior of our algorithm O R A W M with respect to both calculated rate and throughput in a randomly generated wireless network as shown in Figure 5.17. This network consists of 30 nodes deployed randomly over the 1000 x 1000 m? wireless space. We started 3 multicast sessions m i , m 2 , and m, a at time 20 seconds, each with one source Sj and four receivers as shown in Table 5.2 using a = 10~8. The utility functions for all the three sessions is ln(xm) (i.e. gm = 1 V m G M). Figure 5.18 shows the calculated rates and receiver throughput of each multicast session with time. From these results, we observe that our algorithm attains convergence with satisfactory speed even in relatively large scale networks. We also observe that the throughput achieved by each receiver on all sessions follows the calculated rates fairly well, which confirms the correctness of the calculated rates. Note that the optimal calculated rates are different for each session depending on the size of the multicast tree Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 123 and how much resources each session consumes from the total network resources. If this discrimination based on tree topology is undesirable, it can be compensated using different differentiation gains (gm) on each session. .•15 •27 • 6 -• m . • 4 : ,¥28 / -*Q-"•8 :j»23 • 2 § . : , . - ^ , - r •13 -•12 . -©20 •10 Figure 5.17: Random wireless network with 30 nodes. Table 5.2: Multicast traffic pattern. Session Source Receivers rnx so I'll, r 1 2 , ''"13, '*14 rn-2 r 1 6 , ' r 17 , r'is, 7*ig m3 s4 ' '26, ''"27, r ' 28 , '"29 Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 124 20 40 60 80 . 100 120 140 160 180 200 • 20 40 60 80 100 120 140 160 180 200 time (s) time (s) (a) Calculated rates (b) Receiver throughput Figure 5.18: Impact of mobility and route changes on convergence of O R A W M . Overhead study using the O R A W M J F D A implementation In this experiment, we evaluate the overhead of our algorithm O R A W M using different network topologies. We measure the aggregate utility and normalized overhead for eight different topologies generated randomly, each with 30 nodes. We start three multicast sessions at time 20 seconds with a traffic pattern as shown in Table 5.2. The aggregate utility is defined in Equation (5.2) and the normalized overhead is the ratio between the number of non-data packets and data packets delivered at each hop. This overhead includes the FEEDBACK packets sent by the receivers of each multicast session (i.e. fbp packet), and the AODV routing packets, which include the HELLO packets that carry the price information (i.e. gih header) and the price information header (i.e. pih header). Note that the FEEDBACK packets are sent by the terminal node only if the Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 125 accumulated price on that node changes (prior to convergence) in order to decrease the overhead. Furthermore, we compare the aggregate utility and overhead of O R A W M with two other heuristic algorithms. In these heuristic algorithms, the gih header is allowed to be transmitted either for one or two hops away instead of three as O R A W M does in order to reduce the overhead. In this case, the network nodes have only partial knowledge of the network topology and load, and hence, the constructed cliques and prices of them are computed approximately. Figure 5.19 shows the aggregate utility and normalized overhead for the three algo-rithms. We notice in Figure 5.19(a) that the optimal algorithm ( O R A W M ) outperforms the other two algorithms consistently for all topologies as expected whereas the difference in aggregate utility between the other two algorithms is insignificant. An interesting re-sult is shown in Figure 5.19(b) where the total overhead for the optimal algorithm is less than the 2-hop algorithm for some topologies (e.g. topology number 6). This is because more FEEDBACK packets are sent in the 2-hop case because of the approximate clique construction and price calculation, which increases the overall overhead. 5 . 6 C o n c l u d i n g R e m a r k s In this chapter we have presented a new multicast-based algorithm and analytical model for resource optimization over multihop ad hoc networks. This algorithm is used to control the rates of the multicast sessions in such a way that guarantees the optimal resource utilization of the wireless network resources while achieving fairness amongst the Chapter 5. Optimal Resource Allocation for Homogeneous Wireless Multicast 126 £ 13.5 ~ 13 CO 12.5 a> £> 1 2 m ro n 11.5 11 10.5 10 J 2-hop 1 BSC 1-hop j Optimal I. i'l : ;<: 1 !; :"! • 1 i I. H .! | j ; "i : tJ . 1 : I ;!i til : l ! ii Ji «: 11 -1? • •! »i I 'J 1 S ' ! 1 ! ' 1 I'l J : Si f • 1! if pi i n topology number (a) Aggregated utility 0.1 0.09 0.08 "D (0 V 0.07 c g 0.06 o •g005 N = 0.04 E S 0 0 3 c 0.02 0.01 1 •!. : s i i i •i t\,'. Wy-1 'i 1 •i • V <i *i 1 Ii ij 1 2-hop 1-hop Optimal 3 4 5 6 topology number (b) Normalized overhead Figure 5.19: Aggregated utility and packet overhead for eight random networks each with 30 nodes. multicast sessions utilizing the bandwidth-efficiency feature of multicast, which increases the overall network available bandwidth. Based on using maximal cliques as the main resource entity in the network, we modeled the multicast sessions in a form of contention domains and calculated the group price for the end-to-end multicast session. We proposed a mechanism for calculating the group price based on the branch accumulated price which allows the calculation to occur in a totally distributed and asynchronous way. We also demonstrated our theoretical claims and proofs by a series of simulations designed to capture different aspects of the wireless network conditions. 127 Chapter 6 Optimal Resource Allocation for Heterogeneous Wireless Multicast In this chapter, we present our algorithm called O R A H W M , which extends O R A W M to achieve the optimal rates for multirate multicast sessions. We present the general for-mulation of the multirate multicast resource allocation and provide a comparison between unirate and multirate multicast in allocating resources across multicast sessions. 6 . 1 I n t r o d u c t i o n Heterogeneous multicast, or often called multirate multicast, is an efficient mode of data delivery for many, especially, real-time applications (e.g. teleconferencing, audio/video broadcasting). In multirate multicast, the receivers of a multicast group can receive service at different rates corresponding to their different characteristics. For example, receivers may receive different service rates, commensurate with their capabilities (e.g. processing power limitations) or based on their local network conditions (e.g. surrounding °A version of this chapter has been submitted for publication [18-20] Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 128 wireless link states). Because of this receiver heterogeneity, multirate multicast allows the rate on some designated tree members to decrease in order to accommodate the congested receivers downstream, and hence it provides more flexibility in allocating rates across a multicast tree (see example in Section 6.2). Therefore, multirate multicast schemes have a great advantage over unirate multicast (homogeneous multicast) in adapting to diverse receiver requirements and heterogeneous network conditions. The simplest way of attaining multirate multicast is by frame dropping. In this approach, intermediate nodes over the multicast tree may drop data frames to lower the rate for the downstream nodes. Another way is by hierarchical encoding or layered streaming which is particularly suitable for audio/video traffic. In this approach, the sender provides data in several layers organized in a hierarchy. Receivers subscribe to the layers cumulatively to provide progressive refinement [3]. This means that the receiver can only choose from a discrete set of data rates on each link1. Another method of attaining multirate multicast, which is particularly suitable for overlay multicast [7] is stream adaptation through transcoding [79] using some media gateways, which allows the receivers to choose its streaming rate on a continuous range. We assume that the network has any of these capabilities at least at some designated nodes (gateway nodes). In this chapter, we present an optimal resource allocation algorithm for heteroge-neous multicast over wireless ad hoc networks. In order to understand the advantage that multirate multicast promises over unirate multicast, we need to mention some draw-1 Refer to the techniques explained in Chapter 4 for how to calculate the transmission rates on each link in order to achieve optimal resource utilization. Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 129 backs that our algorithm O R A W M (explained in previous chapter) suffers. One of these drawbacks is the inability of O R A W M to efficiently allocate network resources for mul-ticast groups that have some congested group members (receivers). For such multicast groups, O R A W M tends to allocate rates based on the most congested receivers which is an overall waste of network resources. Another drawback is that O R A W M tends to discriminate against large multicast groups (i.e. multicast groups that go through more wireless contention domains and links) by giving them lower rates because large groups utilize more network resources. However, large multicast groups with large number of receivers.should be favored over large groups with low number of receivers because the first would mean more data frames transmitted, and hence more network throughput. Indeed, this problem can be remedied by weighting the utility functions assigned to mul-ticast groups giving large receiver groups more priority over low receiver groups. This can simply be negotiated when a receiver joins the group by sending the source the weight (or differentiation gain) of the utility function assigned to that receiver. The source will then use the aggregate weight of all receivers in maximizing the overall utility of the system, hence, favor large receiver groups over low receiver ones. Note that the transmission rate from a multicast group node needs to be equal to the maximum of the rates of all receivers downstream and is not allowed to exceed the transmission rate coming from upstream nodes (see Section 6.2.2 for more information). The problem of resource allocation for multirate multicast has not been explored in the context of wireless ad hoc networks where resources are allocated for multicast subflows Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 130 across multiple contention domains (i.e. see Chapter 5). Resource allocation for multirate multicast in wired networks has been studied in [44, 45]. An iterative algorithm based on subgradient techniques [80] has been employed to account for the non-differentiability of the primal problem. The authors in [7] proposed an overlay strategy for allocating resources over a multirate multicast tree by considering each link as a point-to-point unicast session. Rates are then allocated across each unicast session such that aggregate utility across all unicast sessions is maximized. The remainder of this chapter is organized as follows. In Section 6.2, we explain new terminology used for heterogeneous multicast and formulate the optimization problem. The approach for multirate multicast is presented in Section 6.3. We present our distrib-uted asynchronous algorithm for the heterogeneous case in Section 6.4. We provide the simulation results in Section 6.4.1. Finally, we conclude in Section 6.6. 6 . 2 M o d e l a n d p r o b l e m f o r m u l a t i o n 6.2.1 Model and notations In addition to the network model explained in Section 5.2 we further divide the multicast tree nodes into gateway nodes and relay nodes as shown in Figure 6.1. Gateway nodes are the nodes that have rate control capabilities through one of the methods explained before, (e.g. layered transmission, transcoding, frame dropping, etc.). Relay nodes, on the other hand, merely forward data frames without performing any rate control functionality, Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 131 O Relay node % Gateway node F i g u r e 6 . 1 : Multirate multicast network model. denotes a gateway node at node i. If V{ is a member of multicast tree rn (hence denoted as Vmi), then Vi can control the rate of the downstream nodes. Fv denotes the set of multicast subflows that belong to the multicast subtree starting from gateway node v and ending at either a terminal node or another gateway node. This subtree is denoted as Tv. Y m = {v„a,vm2, •••}, is the set of all gateway nodes that are members of group m, and T is the set of all gateway nodes on all multicast trees Vm, G M. Each multicast group has at least one gateway node (group source is considered a gateway node) to control the rate to the downstream nodes. We denote irm(v) to be the parent gateway node of gateway node v by going upstream towards the source of group m (e.g. vm\ = 7r(f m 4 )) . Note that the source node has no parent gateway node (i.e. 7 r ( u r n l ) = 0). Also, note that for one multicast group, the rate that a gateway node is using for transmission at Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 132 any given time must be greater than or equal to the maximum rate of all downstream gateway/receiver nodes. For example, in Figure 6.1, the rate used by vm\ for transmission must be greater than or equal to the maximum rate used by any of the gateway nodes vm4, or vm5. This adds a set-of new constraints to the resource allocation problem which can be formulated by the following linear inequalities2. Xv < xnm(v) Vv e Tm s.t. Trm(v) # 0 \fm e M (6.1) where xv is the rate used by gateway node v and xVm(v) is the rate used by parent gateway of gateway node v across the multicast group rn. Example We present an example to illustrate the notations and highlight the main difference be-tween unirate and multirate multicast in allocating rates in an ad hoc network. Figure 6.2 shows an example of an ad hoc network where there are eight nodes connected through wireless links as shown in the figure. The network contains two sessions m, , and m 2 where m.2 has a traffic with fixed rate 800kbps as shown in the figure. m\ uses Node 1 as the group source, and receiving Nodes 5, 6, whereas m 2 uses Node 7 as the group source and receiving Node 8. The aggregated subflows are represented by one node in the contention graph as shown in Figure 6.2(b). Assume that the channel capacity is 1Mbps, which means that the aggregate rate for each maximal clique cannot exceed 1Mbps. In this case, the rate on subfiow fmi cannot exceed 200Kbps because the traffic on that 2Here we formulate the constraints without using maximum functions to keep the constraints linear. Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 133 (a) An example of a multirate multicast ad hoc network (b) Multicast contention graph Go = (Yc, Ee) Figure 6.2: Example for resource allocation in unirate and multirate multicast. subfiow contends with fm7 and hence they both exist in the same maximal clique. Using unirate multicast, we cannot assign a rate to group mi more than 200Kbps because one of the receivers on this multicast is congested. This means that using unirate multicast we allocate the rate based on the most congested receiver. On the other hands, multirate multicast using one gateway node at Node 4 can make the rate allocation more efficient because, in this case, the rate used by source node 1 is allowed to exceed 200Kbps pro-vided that gateway node 4 will adjust this rate to 200Kbps before forwarding the traffic to the downstream nodes. It can be shown that the rate used by source node 1 can be increased to 333Kbps in this case. 6.2.2 Mathematical Formulation Here, we assign a utility function Uv(xv) for each gateway node on every multicast group m G M to measure the degree of satisfaction based on assigning a specific rate xv to Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 134 that gateway node. The optimization problem is to find the set of rates assigned to all gateway nodes for all multicast groups such that the aggregated utility function of all gateway nodes is maximized. This can be formulated with the following modified set of constraints: P : maximize ^ [/„(£',,) (6.2) vex subject to ^ x v r q v < cq Vq e Q (6.3) v.(Fvnvc?)^<& Xv < x„m>v) G T m s.t. nm(v) ^ 0 Vm G M xv G Iv Vu G T where rqv represents the number of multicast subflows which belong to both clique q and the subtree Tv. With this problem formulation and the set of assumptions we stated in Section 5.2.2, we can leverage our solution approach discussed in Section 5.3 as we will see in the following section. Indeed, if we restrict each multicast group to have only one gateway (source) node, then the constraints in Equation 6.1 will be eliminated and problem P' will reduce to problem P discussed in Section 5.2. Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 135 6.3 Solution approach Similar to what we did for problem P, we define the Lagrangian function, this time, L(x,p,p) as follows: L(x,p,p) = J2 UV(XV) + E Vq{Cq - Fqv) + E Pv (X*m {v) ~ Xv) ver qeQ ver = E ver U V { X V ) - Xv ( E Pq rqv + P V - E Pv') </6Q v'eAm(v) + YlPqCq (6-4) qeQ where Am(v) is the set of all children gateway nodes of node v (if any) along multicast tree m. Vectors p = (pq V(? G Q), and p = (pv Vu € T) are two vectors of Lagrange multipliers. rqv represents the number of multicast subflows that belong to subtree Tv and clique q simultaneously. Again we notice that the first term of Equation (6.4) is separable in xv, and this entails max > vei = > mi ver max UV{XV) - Xv(J2Pqrqv + Po ~ Y '^v'' 96<3 t/eAm(i>) UV(XV) - XvCjTPqr<lv + Pv ~ Y Pv' «eQ v'eAm(v) which means that this objective function can be divided into |T | separate subproblems. Each subproblem for subtree Tv can be solved locally if the values of clique prices pq Mq : (Fv n V^') ^ 0 , gateway forwarding price p'v, and all children gateway forwarding prices p i V i / € Am(v) are known. The objective function of the dual problem then becomes: D{p,p ) = m&xL(x,p,p ) Yp^+ Y™? qeQ ver Uv (Xv) - Xv CYP<iriv +Pv- Y Pv' ) <i£Q v'eAm(v) Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 136 and the dual problem D' for the primal problem P' can then be defined as follows: D' : min D(p) (6.5) p>0 6.3.1 Interpretation of prices Consider PV(TV) as the profit of the subtree Tv which can be defined as follows: P v ( T v ) = Uv(xv)-xvC^jpqrqv+p'v- Pv') (6-6) <?£<? v'eAm(v) This profit represents the difference between the ut i l i ty that subtree Tv gains by having rate xv (i.e. Uv(xv)) minus the summation of prices (denoted by U(xv)) that this subtree has to pay for gaining such transmission rate, which is defined as U(XV) =Y^PqrqvXv+PvXv - ] P p\,Xv (6.7) <?eQ v'eKm(y) This summation of prices is divided into three components: • ^2qeQPqPqvXv which can be interpreted as the total price for uti l izing resources on all cliques Vq £ Q such that Fv n Vf ^ 0. In this case, pq can be interpreted, as before, as the price per unit bandwidth consumed at clique q. • p'vxv is the price that subtree Tv must pay to the parent subtree of the same group in order to have traffic with rate xv forwarded to it. In this case, p'v is the price per unit bandwidth for forwarding traffic to subtree Tv. • z L V e A m M P'v'Xv ' s ^ e total revenue that subtree Tv gains by forwarding traffic wi th rate xv to all children subtrees wi th each term p ,xv indicating the revenue for forwarding traffic to subtree Tv< such that v £ Am(v). Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 137 Note that at optimality, p'v = 0 if xv < x7rm(,;) since p'v indicates the price when the constraints in Equation (6.1) are violated or the maximum possible rate is used (i.e. %v = xTTm(o))- This means that a subtree Tv> is not charged for using rate xv if this rate is less than the rate at parent gateway node nm(v). For pq we can, similarly, define the price lor one subfiow fvi £ Tv as the total price for consuming bandwidth on all maximal cliques q £ Q as follows: and we can also define the aggregated price for subtree Tv as a result of consuming bandwidth on all maximal cliques q £ Q as follows: \ v = YI p*r*» (6-9) Equation (6.9) calls for a technique to calculate this price in a distributed network environment using the accumulated subtree price Xv(i) similar to the one explained in Section 5.4.1. This time Xv(i) can be defined as follows xv(i) = X ^ m ^ + A ^ - w v z e r „ (6.10) where KVirm(i) IS the cardinality of subfiow /Wm(,-). 6.3.2 Aggregated subtree price calculation In Section 6.4. we will explain the iterative method for calculating both clique price pq (hence subfiow price from Equation (6.8)), and the forwarding price for each gateway Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 138 node p'v. In order to calculate the total price denned by Equation (6.7) at any gateway node v. we need to calculate the accumulated price on each branch recursively using Equation (6.10) until we hit either a terminal node or another gateway node v £ Am(v). Each gateway node v 6 Am(v) subtracts the forwarding price p , from the accumulated price to get the net price for the branch leading to that gateway node. Children gateway and terminal nodes which are part of Tv then send the net price value back to node v to calculate the subtree aggregate price per unit bandwidth \{TV) by simply aggregating all net branch prices and the forwarding price pv as follows: \(Tv) = \ v + p'v- YI Pv' (6-u) v' eAm(v) 6 . 4 Optimal Resource Allocation for Heterogeneous Wireless Multicast (ORAHWM) To solve the primal problem P in a distributed asynchronous network environment, we use the gradient projection method as explained in Section 5.4. The clique prices pq{t+l) Vq e Q and forwarding prices p'v Vi> € T are calculated iteratively as follows: , C ( * + i ) - b ; w - « M r ( M 3 ) where a > 0 is the gradient step size. Since U„ \fv € T are concave functions, D(p,p ) is continuously differentiable and the gradients for D(p,p ) with respect to p, and p are Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 139 defined as follows: dD(p,p) cq J2 xv(t)rqv qeQ (6.14) ® P q u:(F„nvc:')#0 d D ^ ; p ) = x„miv)(i) - xv(t) v., nm(v) e Vm (6.15) Substituting in Equations (6.12), and (6.13) we get the supply and demand equations for calculating p, and p as follows: pq(t + 1) = \pq(t) - a(c, - J2 x-(t)rqv)}+ (6.16) v.{Fx,nv?)^% • 'i(t + l) = ^v{t)-a{x,m[v){t)-xv(t))}+ (6.17) We calculate the subtree aggregate price X(Tv,t + 1) defined by Equation (6.11) at time (t + 1) using the clique, and forwarding price values from Equation (6.16), and (6.17) as explained in Section 6.3.2. Finally, the transmission rate used by gateway node v at time [t + 1) is calculated as follows: The details for the asynchronous algorithm for heterogeneous wireless multicast is shown in Figure 6.3. In order to understand the association of this algorithm with the network architecture, we assume that each node i in the network has zero or more multicast subflows fvi Vu G T depending on the traffic passing by this node. Even though, the algorithm suggests that the clique procedure at clique q can be performed by a designated node from that clique (i.e. clique master), in our simulations we perform the clique procedure at each node i separately for all cliques that have fVi fl V£ ^ 0. The Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 140 Clique procedure (by clique q): At times t e Tq 1. Receive rates xv(t) from all subtrees Tv where Fv n V? ^ 0 2. Update clique price as follows pq(t + 1) = - a(cq - £ V l? e Q •u:(F vnV,?)^0 3. Send pq(t + 1) to all nodes of group rn such that Fm n l ^ ? / 9 Subflow procedure (by subfiow fvi): At times t eT^ 1. Receive prices from all maximal cliques q where n Vt? ^ 8 2. Calculate the subfiow price (per hop price) A „ i as follows A„»(t + 1) = Hg^/^nv")^^^') 3. Calculate the accumulated price on each branch 6 u,;J 6 /„{ 4. Forward A„(j,£ + 1) to all children subflows of fvi, if no children, send Xv(j,t + 1) to v. Subtree procedure (by gateway v): At times t e T „ 1. Receive the net prices Xv(i,t) - p\(t) from all terminal nodes of Tv (i.e.Vi € S„), and all children gateway nodes Vi 6 A m ( v ) //(note: pi = 0 Vi £ Q'„). 2. f f 7 r . m ( w ) ^ 0 //(i.e. v jt sm) • Receive rate x1Tm(v){t ) from parent subtree of Tv • Calculate the next forwarding price pv(t + 1) as follows: p'v{t + 1) = \p'v(t) - a{xnmM(t) - xv(t))} + Elsep<, (£ + 1) = 0 3. Calculate the next subtree aggregate price X(Tv,t + 1) as follows: X(Tv,t + l)=p'v(t + l)+ £ (K(ht)-Pi(t)) i e (0 „ , U A m (u) ) 4. Calculate the next subtree rate as follows: xv(t + l) = U'v-1(X(Tv,t + l)) 5. Send a;u(t + 1) to all cliques q where Fu n V c« + 0 Figure 6.3: O R A H W M : Asynchronous distributed algorithm. Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 141 subflow procedure is performed by each node i that has one or more multicast subflows fvi Vu £ T by simply calculating the accumulated prices at the branches of fvi based on the accumulated price at i. Finally, active gateway nodes3 perform the subtree procedure by calculating the optimal rate xv(t + 1) based on the aggregated prices for this subtree. The estimation of the price and rate values at time t from the received values at time instances in the range (t — B) < t' < t may follow any update policy such as the latest instant update or the latest average update as explained in Section 5.4.3. For example, the estimation of xv(t) at time t from the values of xv(t ) at times (t — B) < t < t follows the general weighted average model t t Xv{t) = Y 6'(*''*) w h 0 r C Z) ft< (*'*) = 1 t'=t-B t'=t-B Using this model, we proved in Chapter 5 through analytical modeling and simula-tions the convergence of the asynchronous algorithm regardless of the update policy used which was a key feature for these set of algorithms. Furthermore, all the implementation issues including cross-layer framework, distributed asynchronous computations, control messages, and overhead analysis are discussed in Section 5.5. The following experiments also show the same results for the case of heterogeneous wireless multicast. 6.4.1 Simulation results As in Chapter 5, we use the utility functions Uv{xv) = gv ln(a;„) xv > 0 for imposing proportional fairness amongst the multicast groups where gv is the differentiation gain "'Gateway nodes that have traffic from one or more multicast groups passing by them. Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 142 for gateway node v, i.e. xv(t) = gv/Xv(t). 213,4) ' 4161 P2 (a) Multicast network topology (b) Contention graph Figure 6.4: Effect of changing differentiation gains on the calculated rates and aggregate utility. Effect of changing differentiation gains on the calculated rates and aggregate utility In this experiments, we study the effect of changing the differentiation gains on the calculated rates for unirate and multirate multicast sessions. We consider the small topology shown in Figure 6.4. Two sessions mi, and m 2 are sharing this network with source and receiver nodes as shown in the figure. We consider three cases where we change the differentiation gain and show the effect on the calculated rates in each case. Case 1 is the unirate multicast where we use one gateway/source node for each multicast group, and we use equal differentiation gains for both sessions (i.e. gvn = gv.M = 5). For both cases 2 and 3, mi uses gateway node 4 for rate control . Case 2 uses differentiation gains gvn = 3,gVM = 2 whereas case 3 uses gVu = 4,gVM = 1. In all cases we start both multicast groups at t = 20 seconds, we fix all other parameters including a = 3 x IO - 7 Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 143 and we set the channel capacity for all maximal cliques to 1Mbps. a Si i 400 a ! : 300 • 200 • 100 1 20 30 40 50 60 70 time (s) (a) Case 1 (unirate): gvn = gu,M = 5 (b) Case 2 (multirate): gVu = 3,gVl4 = 2,gV2i = 5 800 f i 700 k | 6 0 0 1 •J- 500 a n i 400 ai 300 y-200 100 20 30 40 50 60 70 time (s) _ case 1, unirate, g =5, g =5 , case 2, multirate, g =3, g ~2, g =5 case 3, multirate, g =4, a . =1, g„ =5 =u *u 20 40 60 80 100 120 140 160 180 200 time (s) (c) Case 3 (multirate): gVn = 'i,gVl4 = 1,gV24 = 5 (d) Aggregate utility for cases 1, 2, and 3 Figure 6.5: Effect of changing differentiation gains on the calculated rates and aggregate utility. Figure 6.5 shows the calculated rates and the aggregated utility for the three cases. We Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 144 notice that for Case 1 (unirate), as expected, our algorithm O R A H W M will discriminate against session m\ because it uses more wireless links and hence utilizes more network resources. This happens because, for unirate, O R A H W M deals with each session as one entity regardless of how large this session is and how many links it uses. Multirate with additional gateway nodes can reduce this effect by providing more flexibility to assign more priority to some parts of the tree which in turn affects the aggregate utility of the entire system. This is depicted by the results in Figures 6.5(b), and 6.5(c). We notice that by increasing the differentiation gain for r, n,, we can increase the aggregate utility (shown in Figure 6.5(d)). Effect of dynamic capacity and mobility on the convergence of O R A H W M In this experiments, we study the effect of changing network conditions including chang-ing capacity and node mobility on the convergence of our algorithm O R A H W M . We consider the same topology and multicast sessions shown in Figure 6.4. and we use the First, we study the effect of measuring the real capacity on each clique using the MAC layer channel capacity estimator as explained in Section 5.5.2. Figure 6.6 shows the result of using a time-varying channel capacity realized by the MAC scheduler IEEE 802.11 DCF. From this figure, we observe that although the achieved channel capacity changes with time, our algorithm continuously tracks the change in channel capacity fairly well and provides proportional fairness amongst all the multicast sessions based on Chapter 6. Optimal Resource Allocation [or Heterogeneous Wireless Multicast 145 the current available channel capacity. We also study the impact of mobility and route changes on the convergence of our algorithm by generating a mobility pattern where Node 2 moves from Position 1 to Position 2 as shown in figure with average speed of 3 m/s and pause time of 20 seconds. Figure 6.7 shows the rates calculated by our algorithm with time. The figure shows three different regions depending on the change of routes resulting from the node mobility. In Region 1, only Node 6 is receiving traffic for both multicast sessions. As expected in this case, our algorithm converges to the same rates of Case 3 in the previous experiment. As Node 2 moves to Region 2, the routes for which are shown in Figure 6.4, both receivers at Nodes 5 and 6 become active for Session m,\ and the optimal rates converge to the same values, after some transient period, despite the route changes. When Node 2 moves to Region 3, both the receiver at Node 6 and Node 4 become inactive for Session mi, and Session rn2 can now use the whole channel for its traffic. Therefore, the optimal rate for m2 in this case is 1Mbps whereas the capacity is divided amongst the three subflows /n , / i2 , and / 1 3 for mi. Effect of using multirate on the total throughput for multicast flows In this experiment we study the effect of using gateway nodes for rate control as part of a multicast group. Consider Figure 6.8 which shows two multicast groups m\ and m2 shar-ing an ad hoc network on 11-nodes as shown in the figure, rrii uses gateway/source Node 1 (i.e. Vu), and has 3 receivers, namely: r 7 , r s , and r 9, whereas rn2 uses gateway/source Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 146 800 700 600 in 500 CL 400 a> 2 300 200 100 0 20 40 60 80 100 120 140 160 180 200 time (s) Figure 6.6: Calculated rates with dynamic capacity: gvu — 4,g v u = l,gu 20 40 60 80 100 120 140 160 180 200 time (s) Figure 6.7: Calculated rates with mobility: gVu = 4, gvu = l,gV24 = 5. Node 6 (i.e. V2G) and has two receivers, namely: rw, and r n . Here, to study the impact of using multirate multicast we consider two cases. Case 1 is the unirate multicast with equal differentiation gains for both multicast groups (i.e. gVu = gU26 = 3). For Case 2, mi uses an additional gateway node at 4 (i.e. vi4) for rate control. In this case, we Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 147 Figure 6.8: Multirate multicast network topology. set gVu = 2, gvu = 1 so the total differentiation gain is similar to Case 1, and we set 9v26 = 3. time (s) time (s) (a) Calculated rates (b) Receiver throughput Figure 6.9: Case 1 (unirate): calculated rate and throughput without using gateway node vu. Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 148 20 40 60 80 100 120 140 160 180 201 20 40 60 80 100 120 140 160 180 200 time (s) time (s) (a) Calculated rates (b) Receiver throughput F i g u r e 6 . 1 0 : Case 2(multirate): calculated rate and throughput using gateway node vu for rate control on mi. Figures 6.9 and 6.10 show the calculated rates and receiver throughput for Cases 1 and 2, respectively. We notice that in each case convergence is attained, and the throughput achieved by all receivers on each group tracks the calculated rates appropriately. Com-paring the two figures, we notice the effect of using gateway node vu for rrij which lowers the optimal rate on the subtree Tvu (i.e. xvu) allowing the other rates xv.n and xV26 to increase drastically. This happens because we set the differentiation gain g V l 4 = 1 giving this subtree lower priority based on our knowledge that this subtree has only one receiver (?*g) and the surrounding area has traffic load more than for example TVu and we used vu to give us the flexibility of setting xVi4 accordingly. Such knowledge can either be communicated between the receivers and gateway nodes or tuned manually by Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 149 an administrator. To study the effect of this heterogeneity within m\, we measure the aggregate utility and the total throughput achieved by each group for Cases 1 and 2. Figures 6.11 and 6.12 show the results for these measurements. We see from Figure 6.11 that the aggregate utility achieved for Case 2 is better as a result of using gateway node vu because both rates x v n and xV2(i increased significantly by reducing x V l i . This increase in rates caused the overall throughput achieved by both multicast groups to increase drastically (i.e. « 30%) as shown in Figure 6.12. 6.5 Related Work In this section, we evaluate and compare qualitatively the contributions in Chapters 5 and 6 in light of the previous work of resource allocation in wired and wireless networks. The problem of optimal and fair resource allocation has been widely studied in the context of wired networks. Among these studies (e.g. [10], [1], [7], [45], [44]), price-based methods have shown to be effective in achieving a decentralized solution for rate allocation. Resource allocation for unicast sessions has been covered in [10], [1], whereas [7], [45], [44] discussed the problem for multicast sessions. Although the role of the price in achieving a decentralized solution in our model is analogous to these studies, there are fundamental issues that our solution addresses and they have not been addressed by these models. Some of these issues can be highlighted as follows: Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 150 ! case 1, unirate, gv =g^ =3 case 2, multirate, g =1, g =2, g 5IU . . J ' ^ ' 1 20 40 60 80 100 120 140 160 180 200 time (s) Figure 6.11: Aggregate utilities for Cases 1 (unirate) and 2 (multirate). 12001 1 1 1 1 1 1 1 ' 1 time (s) Figure 6.12: Total throughput for each multicast group for Cases 1 and 2: th\ is total throughput for m i and th2 is total throughput for m^-• The location-based contention and the shared wireless channel characteristics of the wireless ad hoc networks represent major challenges in our model and require unique treatment in allocating network resources. Our model addresses these spe-cial characteristics by employing the protocol model in constructing contention Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 151 domains and maximal cliques that represent network resource entities. • The static nature of the end-to-end sessions in wired networks makes the conver-gence in wired networks simpler and more tractable. On the other hand, as part of our solution we addressed the behavior of the decentralized algorithm as a result of online changing conditions in the network such as mobility, route changes, and time-varying channel capacity. • None of these studies addressed the deployment issues as a result of deploying these solutions in real networks. One of the major contributions that we have emphasized is the design of a cross-layer architecture for realizing optimal fair resource allocation in real ad hoc networks. Such architecture adds more practicality to our results and demonstrates more potential to our solution. Resource allocation for single-hop and unicast flows has been studied in wireless ad hoc networks. Resource allocation using MAC-layer fair scheduling for single-hop flows has been studied in [46-48]. Such techniques, however, do not provide end-to-end re-source optimization and therefore fairness among the multihop flows cannot be achieved only by local MAC layer scheduling. In comparison, we address the end-to-end multi-hop flows, and provide a solution that takes into consideration the network topology and the coordination between different hops of the end-to-end flows in enhancing the overall network's resource utilization. In doing that, our solution uses the clique price as a signal to coordinate the relationship between the different hops and regions to at-Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 152 tain global resource allocation. The end-to-end resource allocation for unicast flows has been covered in [6, 49] using clique price for coordinating end-to-end resource allocation. We have provided a quantitative comparison between multicast and unicast in allocating resources across end-to-end sessions in Section 5.2.2. This comparison shows the major advantage of supporting wireless multicast in increasing the network's available band-width and reducing the number of end-to-end sessions for one-to-many communication. This nominates wireless multicast as a very attractive scheme, especially for multimedia applications. Also, it should be noted that our model represents the general formulation of resource allocation in wireless networks and can be reduced to the unicast model if all the end-to-end sessions are unicast. Therefore, our solution has major differences and additional characteristics both in the problem formulation and the architecture for deploying the algorithm in ad hoc networks, which can be highlighted as follows: • Our model promotes using the one-hop broadcast feature of the wireless medium in multiplying the network's available bandwidth through, the notion of multicast subflows. Such representation provides flexibility in allocating rates across the different parts of the multicast tree. It also allows supporting multirate multicast which provides ultimate flexibility in allocating rates while increasing network's resource utilization. • Dividing end-to-end sessions into multicast subflows, however, introduces major challenge in our model that requires unique treatment especially for constructing contention domains and maximal cliques (see Section 5.2.1). Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 153 • Calculating the price for multicast sessions in a decentralized way represents an-other challenge in our model, which motivated the development of our group price calculation mechanism described in Section 5.4.1. • The design of the network architecture for resource allocation has been influenced significantly by supporting multicast sessions. This appears in integrating multicast aware routing protocol (MAODV) and group HELLO packets for conveying aggre-gate subfiow status in the routing layer. We have suggested the use of Multicast-aware MAC layer protocol (MMP) for reliable multicast transfer, and multicast aware measurement-based technique for channel capacity estimation in the MAC layer. Lastly, we have suggested modifying the transport layer to deal with multiple feedback packets as part of the group procedure to calculate the group price. • To demonstrate the versatility of our solution for different network environments, we have considered a series of implementations based on the information distri-bution and channel dynamics and showed the convergence behavior in all these environments. 6.6 C o n c l u d i n g R e m a r k s In this chapter we have presented the resource optimization algorithm for the case of multirate multicast ( O R A H W M ) over multihop ad hoc networks. We have introduced the notion of gateway nodes used to control the rates for multirate multicast groups and Chapter 6. Optimal Resource Allocation for Heterogeneous Wireless Multicast 154 provided the optimization model that realizes the optimal rates used by each gateway node in order to maximize the overall aggregate utility for the entire system. Utilizing the flexibility of using gateway nodes across the multicast trees, O R A H W M is expected to increase the aggregate utility of the system and boost the overall throughput achieved by each multicast group provided that the differentiation gains are set appropriately. 155 Chapter 7 Conclusions and Future Research We conclude this thesis with a summary of our contributions and suggestions for future work. 7.1 S u m m a r y The main objective of this thesis was to offer a set of viable solutions that can close some essential gaps in providing optimal resource allocation in wired and wireless networks. We motivated the problems presented in this thesis and provided survey of the latest techniques in the area of resource allocation in Chapter 2. Later chapters then presented our major contributions which are summarized as follows: Chapter 3 presented a group of algorithms for calculating the optimal classification for a set of traffic streams with diverse QoS requirements for a link model with a predeter-mined service levels or predetermined class weights. It also studied the effect of the three proposed service differentiation (7) estimation methods on the quantization overhead and provided a comparison study based on complexity analysis and simulation. Using the dropping probability as the QoS metric, a conclusion has been deduced that using 4 Chapter 7. Conclusions and Future Research 156 or 5 service levels will achieve the compromise between complexity and minimizing the quantization overhead. Furthermore, the expected quantization overhead for stochastic QoS requirements has also been studied. Convergence analysis has then been provided to study the effect of sampling the QoS pdf functions on the quantization overhead. Results from this work appear in [12] [13] [14]. Chapter 4 presented the algorithms for calculating the optimal partitioning and band-width allocation for a set of traffic streams with diverse QoS requirements for a link model with variable service levels. Such algorithms can be useful for service providers to design the network service levels that achieve the best granularity based on the different distri-butions of the QoS requirements and bandwidth demands. It has been shown again that using 4 or 5 service levels will achieve the compromise between complexity and minimiz-ing the quantization overhead using dropping probability as the QoS metric. Moreover, it has also been shown that the optimal QoS partitioning with bandwidth allocation ( O Q P -O B A ) algorithm will guarantee graceful service degradation when the link is overloaded due to the absence of admission control. This work appears in [17]. Chapter 5 presented a new multicast-based algorithm and analytical model for re-source optimization over multihop ad hoc networks ( O R A W M ) . This algorithm is used to control the rates of the multicast sessions in such a way that guarantees the optimal resource utilization of the wireless network resources while achieving fairness amongst the multicast sessions utilizing the bandwidth-efficiency feature of multicast which in-creases the overall network available bandwidth. Based on using maximal cliques as the Chapter 7. Conclusions and Future Research 157 main resource entity in the network, the multicast sessions has been modeled in a form of contention domains, and the group price for the end-to-end multicast session has been calculated. This chapter also proposed a mechanism for calculating the group price based on the branch accumulated price which allows the calculation to occur in a totally dis-tributed and asynchronous way. It has been shown through simulations that convergence can still be attained with slow network changes including channel dynamics and node mobility. This work appears in [18]. Chapter 6 presented the resource optimization algorithm for the case of multirate multicast ( O R A H W M ) over multihop ad hoc networks. It introduced the notion of gateway nodes used to control the rates for multirate multicast groups and provided the optimization model that realizes the optimal rates used by each gateway node in order to maximize the overall aggregate utility for the entire system. Utilizing the flexibility of using gateway nodes across the multicast trees, O R A H W M is expected to increase the aggregate utility of the system and boost the overall throughput achieved by each multicast group compared to O R A W M provided that the differentiation gains are set appropriately. 7.2 Future Work In the following, we provide a list of possible future directions for research related to the work reported in this thesis. Chapter 7. Conclusions and Future Research 158 1. QoS classification and partitioning techniques discussed in Chapter 3 and Chapter 4 have been evaluated using statistical simulation models. Studying the effect of these techniques in a topological network could be of practical significance. In other words, it would be interesting to simulate these proposed techniques in a network with a specific topology and study the effect of using such techniques on the overall resource utilization of the network. 2. Mapping the service levels discussed for QoS classification/partitioning to protocol entities such as labels in Multi Protocol Label Switching (MPLS) [81] will allow us to devise a signaling mechanism that can be used to negotiate the calculated service levels among the network Label Switched Routers (LSRs). Such mapping will be crucial to evaluate the performance of these techniques in MPLS-enabled network. 3. Although our asynchronous algorithms O R A W M and O R A H W M presented in Chapter 5 and Chapter 6 converge online to the optimal rates, the convergence be-havior is critically sensitive to the value of the step size a. Therefore, it might be useful to design a technique which guarantees the convergence with less sensitivity on the step size. From the theory of optimization, several techniques (e.g. variations of Newton's method) exist for exactly this purpose [73] and they sometimes offer faster convergence compared to gradient methods. However, none of these methods can be implemented in a distributed environment with asynchronous computations. There-fore, designing a technique which achieves faster convergence with less sensitivity on a without sacrificing the important feature of distributed computations will have a Chapter 7. Conclusions and Future Research 159 significant potential. 4. Extending the multicast-based models in Chapter 5 and Chapter 6 to capture some wireless physical characteristics like power may be crucial for supporting power con-trol mechanisms for multihop wireless networks with multicast-based communication. Such a model will optimize some physical layer related objectives (e.g. signal to in-terference noise ratio (SIR.)) subject to some power limitations on the network nodes. 5. Our multicast-based model in Chapter 6 addresses the heterogeneity in the multicast receivers in terms of rate requirements while assuming that all nodes relay the traffic to other nodes homogeneously. However, another significant aspect of heterogeneity might be in the physical characteristics of each node (e.g. battery power). Such heterogeneity will affect the willingness of each node to relay the traffic for other nodes within the ad hoc network. An additional cost parameter may be used in this case to measure the willingness of each node to relay traffic to other nodes. The objective then is to optimize the aggregate utility of all sessions after deducting the cost of relaying the traffic from one node to another across each session. 6. Mapping the protocol entities for implementing O R A W M and O R A H W M to one of the existing standards for multihop wireless networks (e.g. 802.15.4/ZigBee ) could also be a potential area of research. Such mapping will allow us to study the effect of these multicast-based techniques on enhancing the functionality of a ZigBee network which would be of practical significance especially to SPs. 160 Bibliography [1] R. J. La and V. Anantharam. Utility-based rate control in the internet for elastic traffic. IEEE/ACM Transactions on Networking, 10(2):272-286, April 2002. [2] Y. Kogan W. Berger. Dimentioning bandwidth for elastic traffic in high-speed data networks. IEEE/ACM Transactions on networking, 8(5), October 2000. [3] S. Paul X. Li and M. Arnmar. Layered video multicast with retransmission (LVMR): Evaluation of hierarchical rate control. In proceedings of IEEE Infocom, March 1998. [4] Y. Richard Yang, Min Sik Kim, and Simon S. Lam. Optimal partitioning of multicast receivers. In proceedings of the 8th IEEE ICNP, 2000. [5] K. Gopala.n and T. Chiueh. Multi-resource allocation and scheduling for periodic soft real-time applications. In proceedings of Multimedia Computing and Networking, San Jose, CA. USA, pages 34-45, January 2002. [6] Y. Xue, B. Li , and K. Nahrstedt. Optimal resource allocation in wireless ad hoc networks: A price-based approach, in Technical Report UIUCDCS-R-2004-2505, University of Illinois at Urbana-Champaign, June 2004. Bibliography 161 [7] Y i Cui, Y. Xue, and K. Nahrstedt. Optimal resource allocation in overlay multicast,. In proceedings of the 11th International Conference on Network Protocols (ICNP), Atlanta, Georgia, November 2003. [8] J. Kuri P. Chaporkar. A network architecture for providing per flow delay guarantees with scalable core. Journal for High Speed Networks, 12(3):87—109, Jan 2002. [9] A. K. Parekh and R . G. Gallager. A generalized processor sharing approach to flow control in integrated service networks: The single node case. IEEE/ACM Transac-tions on Networking, l(3):344-357, June 1993. [10] S. H. Low and D. E. Lapsley. Optimization flow control: Basic algorithm and convergence,. IEEE/ACM Transactions on Networking, 7:861-874, 1999. [11] A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated service networks: The multiple node case. IEEE/ACM Transactions on Networking, 2(2):137—150, 1994. [12] A. Mohamed and H. Alnuweiri. Optimal QoS-based classification for multi-class link models with predetermined service levels. Submitted to IEEE/A CM Transactions on Networking, March 2006. [13] A. Mohamed and H. Alnuweiri. Dynamic programming QoS-based classification for links with limited service levels. In proceedings of IEEE Conference on local area networks LCN, Sydney, Australia, pages 51—58, November 2005. Bibliography 162 [14] A. Mohamed and H. Alnuweiri. Optimal QoS-based classification for link models with predetermined service levels. In proceedings of the 8th International Conference on Telecommunications, Contel, Zagreb, Croatia, 2:375- 382, June 2005. [15] A. Mohamed and H. Alnuweiri. Dynamic programming QoS-based classification for links with limited service levels. International Transactions on Computer Science and Engineering (GESTS), 19(1):97-108, October 2005. [16] A. Mohamed and H . Alnuweiri. Stochastic QoS-based classification for link models with calculated service levels. In proceedings of Conference on Communications, Computers and signal Processing, PACRIM, pages 364-367, August 2005. [17] A. Mohamed and H. Alnuweiri. QoS-based partitioning and resource allocation for link models with variable service levels. In proceedings of IEEE ISCC, Sardinia, Italy, June 2006. [18] A. Mohamed and H. Alnuweiri. A distributed iterative algorithm for optimal rate al-location for homogeneous wireless multicast. In proceedings of 1ST mobile & wireless communications summit, Greece, June 2006. [19] A. Mohamed and H. Alnuweiri. Optimal resource allocation for homogeneous wireless multicast. Accepted for publication in IEEE Globecom, San Francisco, November 2006. [20] A. Mohamed and H. Alnuweiri. Cross-layer distributed approach for optimal rate al-location for homogeneous wireless multicast. Submitted to IEE Proceedings Commu-Bibliography 163 nications, special Issue on Wireless Mobile Networks: Cross-Layer Communication, April 2007. [21] A. Mohamed and H. Alnuweiri. Design of a cross-layer optimization framework for rate allocation in wireless multicast. Accepted for publication in IEEE International conference on Mobile Ad-hoc and Sensor Systems (MASS), Vancouver, Canada, Oc-tober 2006. [22] A. Mohamed and H. Alnuweiri. Cross-layer optimal resource allocation for heteroge-neous wireless multicast. Submitted to IEEE Journal on Selected Areas in Communi-cations, special issue on cross layer optimized wireless multimedia communications, 2007. [23] A. Kaheel, T. Khattab, A. Mohamed, and H. Alnuweiri. Quality-of-service mecha-nisms in IP-over-WDM networks. IEEE Communications Magazine, 40(12):38-44, December 2002. [24] X. Wang and K. Kar. Cross-layer rate control for end-to-end proportional fairness in wireless networks with random access. In proceedings of the 6th ACM international symposium on Mobile ad hoe networking and computing, Urbana-Champaign, IL, USA, pages 157-168, 2005. [25] L. Tassiulas K. Kar, S. Sarkar. Achieving proportional fairness using local informa-tion in Aloha networks. In IEEE Transactions on Automatic Control, 49:1858-1863, November 2004, Bibliography 164 [26] D. Bertsekas and R. Gallager. Data Networks. Prentice Hall, 1987. [27] Z. Fang and B. Bensaou. Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad-hoc networks. In proceedings of the IEEE Infocom, 2004. [28] A. Elwalid and D. M i t r a . Design of generalized processor sharing schedulers which statistically multiplex heterogeneous qos classes. In proceedings of IEEE INFOCOM, pages 1220-1230, 1999. [29] Q. Ni, L. Romdhani, and T. Turletti. A survey of QoS enhancements for IEEE 802.11 wireless lan. Journal of Wireless Communications and Mobile Computing, Wiley, 4(5):547-566, 2004. [30] X. Long Huang and B. Bensaou. On max-min fairness and scheduling in wire-less ad-hoc networks: analytical framework and implementation. In proceedings of IEEE/ACM MobiHoc, Long Beach, CA, pages 221-231, October 2001. [31] A. Legout, J. Nonnenmacher, and E. W. Biersack. Bandwidth allocation policies for unicast and multicast flows. In Proceedings of IEEE INFOCOM'99, pages 254-261, New York, NY, USA, 1999. [32] H. C. Cankaya, S. Charcranoon, and T. S. El-Bawab. A preemptive scheduling technique for OBS networks with service differentiation. In proceedings of Globecom, pages 2704-2708, 2003. Bibliography 165 [33] N. Christin, J. Liebeherr, and T. Abdelzaher. A quantitative assured forwarding service. In proceedings of IEEE INFOCOM, New York, 2:864-873, June 2002. [34] Y. Chen, M. Hamdi, and D. H. K. Tsang. Proportional QoS over OBS networks. In proceedings of IEEE Globecom, New York, pages 1510-1514, 2001. [35] S. Blake, D. Black, M. Carlson, E. Davies, Z.Wang, and W.Weiss. An architecture for differentiated services. IETF RFC 2475, December 1998. [36] G. Bianchi, N. Blefari-Melazzi, and M. Femminella. Per-flow QoS support over a stateless differentiated services IP domain. The International Journal of Computer and Telecommunications Networking, 40(l):73-87, 2002. [37] M. Yang, Y. Huang, J. Kim, M. Lee, T. Suda, and M. Daisuke. An end-to-end QoS framework with on-demand bandwidth reconfiguration. IEEE INFOCOM, March 2004. [38] K. Takagaki, H. Ohsaki, and M. Murata. Analysis of a window-based flow control mechanism based on TCP vegas in heterogeneous network environment. In pro-ceedings of IEEE International Conference on Communications ICC, 10:3224-3228, June 2001. [39] H. Ohsaki, M. Murata, T. Ushio, and H. Miyahara. A control theoretical analysis of window-based flow control mechanism,based on TCP vegas,. High Quality Internet Workshop, October 1998. Bibliography 166 [40] D. H. Lorenz and A. Orda. Optimal partition of QoS requirements on unicast paths and multicast trees. IEEE/ACM Transactions on Networking, 10(1):102—114, February 2002. [41] R. Nagarajan, J. Kurose, and D. Towsley. Local allocation of end-to-end quality-of-service in high-speed networks. In IFIP TC6 Task Group/WG6.4 International Workshop on Performance of Communication Systems, pages 99 118, January 1993. [42] F. Kelly, A. Maulloo, and D. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research So-ciety, 49, 1998. [43] S. McCanne , V. Jacobson, and M. Vetterli. Receiver-driven layered multicast. ACM SIGCOMM, 26,4:117-130, August 1996. [44] K . Kar, S. Sarkar, and L. Tassiulas. Optimization based rate control for multirate multicast sessions. IEEE INFOCOM, pages 1.23-132, 2001. [45] K. Kar, S. Sarkar, and L. Tassiulas. A scalable low overhead rate control algorithm for multirate multicast sessions. IEEE Journal of Selected areas in Communications, special issue in Network Support for Multicast Communications, 20:1541-1557, Oc-tober 2002. [46] T. Nandagopal, T. Kim, X. Gao, and V. Bharghavan. Achieving MAC layer fairness in wireless packet networks. In proceedings of the international conference on Mobile computing and networking (MobiCom), Boston, MA, USA, pages 87-98, 2000. Bibliography 167 [47] L. Tassiulas and S. Sarkar. Maxmin fair scheduling in wireless networks. In proceed-ings of IEEE INFOCOM, pages 763-772, 2002. [48] H. Luo, S. Lu, and V. Bharghavan. A new model for packet scheduling in multihop wireless networks. MobiCom, Boston, Massachusetts, pages 76-86, 2000. [49] C. Curescu and S. Nadjm-Tehrani. Price/utility-based optimized resource allocation in wireless ad hoc networks. In proceedings of Second Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON), pages 85-95, September 2005. [50] T. Salonidis and L. Tassiulas. Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks. In proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, Urbana-Champaign, IL, USA, pages 145-156, 2005. [51] S. Sarkar and L. Tassiulas. End-to-end bandwidth guarantees through fair local spectrum share in wireless ad-hoc networks. In proceedings of IEEE Control and Decision Conference (CDC), Maui, HI, USA, December 2003. [52] L. Buttyan and J. P. Hubaux. Stimulating cooperation in self-organizing mobile ad hoc networks. ACM/Kluwer Mobile Networks and Applications (MONET), 8(5), October 2003. [53] Y. Qiu and P. Marbach. Bandwidth allocation in ad-hoc networks: A price-based approach. In proceedings of IEEE INFOCOM, 2003. Bibliography 168 [54] J. Tang, G. Xue, C. Chandler, and W. Zhang. Link scheduling with power control for throughput enhancement in multihop wireless networks. In proceedings of the second International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks (QSHINE), Lake Buena Vista, FL, USA, August 2005. [55] P. Djukic. Optimum resource allocation in multipath ad hoc networks. M.Sc. Thesis University of Toronto, 2003. [56] T. M. Heikkinen. On congestion pricing in a wireless network. Wireless Networks, Kluwer, 8(4):347-354, July 2002. [57] R. L iao , R. Wouhaybi, and A. Campbell. Incentive engineering in wireless lan based access networks. In proceedings of 10th IEEE International Conference on Network Protocols (ICNP), November 2002. [58] D. Julian, M. Chiang, D. ONeill, and S. Boyd. QoS and fairness constrained convex optimization of resource allocation for wireless cellular and ad hoc networks. In proceedings of IEEE INFOCOM, pages 477-486, June 2002. [59] Y. Shavitt D. Raz. Optimal partition of QoS requirements with discrete cost func-tions. IEEE Journal on Selected Areas in Communications, 8, 2000. [60] Y. Bejerano, Y. Breitbart, A. Orda, R. Rastogi, and A. Sprintson. Algorithms for computing QoS paths with restoration. IEEE/ACM Transactions on Networking (TON), 13:648-661, June 2005. Bibliography 169 [61] G. N. Rouskas and L. E. Jackson. Optimal granularity of MPLS tunnels. In pro-ceedings of the 18th International Teletraffic Congress (ITC-18), Berlin, Germany, pages 1-10, September 2003. [62] T. Jiang, M. H. Ammar, and E. W. Zegura. On the use of destination set grouping to improve inter-receiver fairness for multicast ABR sessions. In proceedings of IEEE INFOCOM, 2000. [63] J. Turner. Terabit burst switching,. Journal of High Speed Networks, 8:3-16, 1999. [64] R. Nagarajan, J. Kurose, and D. Towsley. Local allocation of end-to-end quality-of-service in high-speed networks. In IFIP TC6 Task Group/WG6-4 International Workshop on Performance of Communication Systems, pages 99-118, January 1993. [65] J.F. Kurose and D. Towsley. Approximation techniques for computing packet loss in finite-buffered voice multiplexers. IEEE Journal on Selected Areas in Communi-cations, 9(5), April 1991. [66] S. Battiato, D. Cantone, D. Catalano, G. Cincotti, and M. Hofri. An efficient algorithm for the approximate median selection problem. In proceedings of the Fourth Italian Conference, CIAC, Rome, 1767:226-238, 2000. [67] F. Gebali. Computer Communication Networks: Analysis and Design. Northstar Digital Design, 2005. Bibliography 170 [68] R. Nagarajan, J.F. Kurose, and D. Towsley. Approximation techniques for comput-ing packet loss in finite-buffered voice multiplexers. IEEE Journal on Selected Areas •in Communications, 9(5). April 1991. [69] M. R. Garey and D. S. Johnson. Computer & Intractability: A Guide to the Theory of NP-Completeness. W H Freeman, November 1979. [70] P. Gupta and P. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46:388-404, March 2000. [71] H. Gossain, N. Nandiraju, K. Anand, and D. P. Agrawal. Supporting MAC layer-multicast in I E E E 802.11 based manets: Issues and solutions. In proceedings of 29th Annual IEEE International Conference on Local Computer Networks (LCN), pages 172-179, 2004. [72] P. Chaporkar, A. Bhat, and S. Sarkar. An adaptive strategy for maximizing through-put in MAC layer wireless multicast. MobiHoc, pages 256-267, 2004, [73] D. Bertsekas. Nonlinear Programming. Athena Scientific, 1999. [74] D. Bertsekas and J. Tsitsiklis. Parallel and Distributed Computation. Prentice-Hall, 1989. [75] K, Nahrstedt S. H. Shah, K. Chen. Dynamic bandwidth management for single-hop ad hoc wireless networks. ACM/Kluwer Mobile Networks and Applications (MONET), 10, 2005. Bibliography 171 [76] E. M. Royer and C. E. Perkins. Multicast operation of the ad-hoc on-demand distance vector routing protocol. ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), pages 207-218, 1999. [77] C. Perkins and E. Royer. Ad-hoc on-demand distance vector routing,. In proceedings of 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA 99), 1999. [78] J. G. Augustson and J. Minker . An analysis of some graph theoretical cluster tech-niques,. In Journal of the Association for Computing Machinery, volume 17, pages 571-586, 1970. [79] E. Amir, S. McCanne, and R. Katz. An active service framework and its application to real-time multimedia transcoding. In proceedings of the ACM SIGCOMM '98, Vancouver, Canada, pages 178-189, 1998. [80] N. Z. Shor. Minimization Methods for Non-differentiable Functions. Springer-Verlag, 1985. [81] E. Rosen and A. Viswanathan. RFC 3031: Multiprotocol Label Switching Architec-ture. Internet Engineering Task Force (IETF), January 2001. [82] W. Rudin. Principles of Mathematical Analysis. McGraw-Hill, 1976. 172 Appendix A QoS-Based Partit ioning and Resource Allocation This appendix presents the proofs for the QoS-based classification and partitioning in Chapters 3 and 4. A . l P r o o f s f o r C h a p t e r 3 A.1.1 Lemma 3.1 Proof. Proceed by contradiction, assuming that we have an optimal classification n*L that is un-ordered, and for all ordered classifications TTL0 we have ^(TT*) < ip(nLo) W/-,0. In other words, n*L is such that for some pairs of groups Ga and G'?,, we have r,: £ Ga and Tj £ Gb, and Q i > Qj while xa < xb- We will define a re-arrangement operator r\ on n*L , and form another classification TT'L (i.e.7r^ = , ' ? ( 7 R ^ ) ) A N C ^ P R O V E that by applying r\ repeatedly until fx'L becomes ordered, we will ultimately have 'tp{7t'L) < i-'{^*L)- Notice that for predetermined service levels, xa and xb may be allowed to have values which are outside of the range of QoS requests in Ga and Gb (e.g. xa < min(Qi : Qi VV.; € Ga)), Appendix A. QoS-Based Partitioning and Resource Allocation 173 and operator n will still work in this case. Here is how operator n will work. 1. If Qi > Qj > Xb > xa or Qi > xb > Qj > xa, rj forms TT'L as follows: G'a =Ga- (n) G'b = Gbu in) A^ = U(Quxb)-U(Q.hxa)<0 2. If Xb > xa > Qi > Qj or x0 > Qi > xa > Qj, rj forms ir'L as follows: G'b = Gb - (rj) G'a = GaU(r3) A^ = U(Qj,xa)-U(Qj,xb)<0 3. If Xb > Qi > Qj > xa, rj forms 7r'Las follows: G'b = (Gb U [n]) - [rj] -»'iP(Gb) = U(Qi,xb) - U(Q:hxb) < 0 G'a = (Ga U [r ?]) - [n] - >P(Ga) = U(Q.j,xa) - U(Ql,xa) < 0 Aip = Aip(Ga) + Ai>(Gb) < 0 By applying operator r/ Vn G G« and Vr,- G with Qi > Qj and < xb,Va, and V6, we will obtain an ordered classification with i/j(n'L) < ip(n*L), which contradicts the original assumption that rc*L is an optimal classification. Therefore, 'p(ir'L) = ^(TT*), arid n'L is an optimal and ordered classification. • Appendix A. QoS-Based Partitioning and Resource Allocation 174 A.1.2 Lemma 3.2 Proof. Assuming the set of all possible ordered classifications for N traffic streams and L service levels is 9^, we proceed by induction. Clearly, the case of L=l is trivial. For the case of L=2, the number of possible solutions (|9^|) is N-1 which is O(N). Now assume that for L = rn. is 0(Nm~i), to get | when L = rn+1, we notice that the number of possible solutions is actually derived by the summation of | in the case of i — rn, m+1,... ,N — 1. This is because for ordered classifications, we can think of the groups as integer numbers and we want to get the possible combinations of numbers such that the total sum of all the numbers is N. Notice also that for TV < ra, \$fN\ =0. Therefore, for L = m+1, the possible combinations are the summation of |Qf* | for i = m, given that the last number is N — rn, plus |9 ' J for i — m+1, given the last number is N — m — 1, and so on. So, \QN , I can be written as follows: It is not hard to prove that the summation part of this equation is O(N) (e.g. Qf | = J2 {i ~ 2 ) x (i - l)/2 = 11/6 x N - N2 + 1/6 x Ns - 1 = 0(N3)). So, the A.1.3 Lemma 3.3 Proof. Since o#= Cij*U(Qi/wj,'f) is non-increasing in the interval7Wj € [0, Qi], and non-decreasing in the interval JWJ € [Qi,oo[, then btj = t/(Qj/w,-,7)» i s non-increasing for the N-1 i=3 result | 3 f | = 0(NL~X) follows. • Appendix A. QoS-Based Partitioning and Resource Allocation 175 values of 7 G [0,Qi/ujj], and non-decreasing for the values of 7 G [Qi/coj, 00[. Without loss of generality, assume the values of dy = Qi/ujj Vi, Vj are sorted in a non-decreasing order. The summation for any possible subset of i, j of IP(TTL) = E I ! * U{Qi/ojj,r)) ieijeJ is non-increasing in the interval of 7 G [Q,mm(Qi/u>j)], and it is non-decreasing in the interval 7G [max(Q,;/w.,), oo[, Vi e I Vj G J. So, in order to minimize the value of il'^t), 7 must be selected in the interval [min(Qi/ujj), max(Qi/wj)] i = 1, ...,iV j = 1,...,L. • A.1.4 Theorem 3.1 Proof. Again, without loss of generality, we assume the values dy = Qi/tOj V » , V j , are sorted in a non-decreasing order. From the proof of Lemma 3.3, we know that the summation $ = T J ^ a,.j for any subset of i, j is non-increasing for the values of 7 G [0, min(dy)], and non-decreasing for the values of 7 G [max(dy), 00[ ,Vi G / Vj G J. Now, between any two subsequent values dij = da, and dy = db such that d 0 < db, the summation \& for any subset of i, j is the summation of multiple concave functions. From the properties of concave functions, the summation * is a concave function in the range [da, db], which means that for any value 7 G [d0,dt], we have ^(a da + (1 — a)db) > a \I>(da) + (1 - a) *(d(,) 0 < a < 1. Therefore, to look for the minimum value of ^ within this range 7 G [da,dfc], we only need to check at da, and db- We repeat the same procedure for all successive values of dy Vi,Vj. So, the minimum value of ^ for any subset of i, j lies in the value set of 7 G {dy,i = 1,.., N j = 1,... L}. • Appendix- A. QoS-Based Partitioning and Resource Allocation 176 A.1.5 Theorem 3.2 Proof. Proceed by contradiction, assume that 7^(7') is the optimal classification for 7 such that (^TTJXV), 7') < ^(^(7) , 7) V7 and 7' $ {did = Ql/uj, i = 1,...,N j = 1 , L . We have 3 scenarios for 7' as follows: 1. 7' < mm(dij) We know from Theorem 3.1 that for the same classification 7^(7'), we have ^ ( V ) . m i n ( d i j ) ) < ^(7^(7), 7') We also know that considering the optimal classification for 7 = min(d»j)> we have ^(7r£(min(<iy)), min (dij)) < ^ (^(7), min(^j)) Therefore, ip(ir*L(mm(dij)),m'm(dij)) < IIJ(TT*L(^'), 7'), and this conflicts with the original assumption. 2 . da < 7' < d0, da > mm(dij) , db < max(dij) Again, from Theorem 3.1, i>(nl(j), 7') is concave in the interval da < 7' < <4. So, for the same classification 7^(7'), we have ^ ( ^ K T ' ) ) da)< ^(^L{I')I l) and ^ I ( V ) , dt) < n^lil), V ) - We also know that ^(ir*L(da), da) < V - ^ K T ' ) , 4) and i>{irl{db), db) < '0(TT2(7'), 4). Therefore, VOLWO, d « ) < ^ ( 7 ' ) , V ) and 'iJj(n*L(db), db) < V 'O'KT'W) which conflicts with the assumption. 3. 7 > max(^j) Appendix A. QoS-Based Partitioning and Resource Allocation 177 Similarly we can prove that ip(Tr*L(max(dij)), max(dy)) < ^(^Kl )> 7) which conflicts with the assumption. Therefore, for all 7' ^ {fi?;j = Qi/uij, i = 1,...,N ,j = 1,...,L}, we cannot have ^ ( ^ ( T ' ) ' 7') ^ ¥'(7rz.(7): 7) ^7- Then the values of 7* 6 {dij = Qi/ujj, i = 1 , N j = 1, constitute the optimal possible values such that V K ( 7 * ) , 7*) < ^ ( 7 ) , 7) V 7 . ' • A . 2 P r o o f s f o r C h a p t e r 4 A.2.1 Lemma 4.1 Proo/. To prove intractability, we will use the concept of restriction [69]. First, we can easily convert the OQP minimization problem to a decision problem by assuming that we will try to find whether there is a partition such that I)J(PL) = k. Later we can decrease k as low as possible to find the minimum value. Second, for U(Qi,si) defined by (4.7), and for a specific partition Pi, we have for each group Gi € Pi of size \Gi\ = M, we have M + 1 possible values for U(Qi,si)= h + YI a* depending on which range we select the value of S;. Now, we are ready to do the transformation. By checking the definition for the SUBSET SUM problem, we can map the set of sizes A to the possible values of summation on each group such that s(a) = J2 U(Qi, S ; ) . Remember for each group in OQP we have possible numbers, which means we have L x (|G;| +1) possible values for s(a) € A to cover all the L groups in OQP. Now, it is easy to see that finding Appendix A. QoS-Based Partitioning and Resource Allocation 178 the L subset (A' C A) of numbers such that s ( a ) = B where B is positive integer is aeA' equivalent to finding the service levels such that TJJ(PL) = k, hence the result follows. • A.2.2 Theorem 4.1 Proof. Without loss of generality, we assume that the values of QoS are sorted such that Qi < Q2 < ... < QN and we prove by contradiction as follows. Assume that P*= {G*, G*,.... G*} is the optimal partition with a corresponding optimal service levels S*L = {s*, s* ,s* } such that 5* has some service levels ,s* g {Qi : i € Gt} Vs* G S' C SL. In this case, we have the following 3 scenarios for each s* G 5': 1. s* < mm{Qi :ieG[} = Qf l i n We know from the utility property that the summation U(Qi,s) = U{Gi = {Qi, ...,Qj},s) as a function of s will be non-increasing in the range s G[0, Q"nn} and non-decreasing in the range s G [Q" ' a x , oo[. This means U(Gi,Qj"in) < U(Gi, s*) • and we can replace s* by Q""n in 5£. 2. s* > max{Qi :ieG,} = Q]nax We know from the utility property that the summation U(Gi,s) will be non-increasing in the range s G[0, Qf'n] and non-decreasing in the range s G [ Q ( M A X , oo[. This means U(Gt, Q| n a x) < U{Gi,sf) and we can replace s* by Q?™. 3. Q m < s < Q m + 1 m = 1 , N - 1 Appendix A. QoS-B&sed Partitioning and Resource Allocation 179 We notice for these ranges U(Gi,s) is a summation of multiple concave functions. From the properties of concave functions, this summation is also concave, which means U(Gi,Qm) < U(Gi,s*) and/or U(Gi,Qm+\) < U(Gi,s*). In this case, we can replace s* by either Qm or Qm+\ (based on which one gives lower value for U{Gus))mSl. • Therefore, in the previous 3 scenarios, we can replace service levels in S' by values s* G {Qi : i € Gi} Vs* G S' C SL and get lower value for the objective function which means that the replacement S* is also optimal. • 180 Appendix B Resource Allocation for Wireless Multicast: Convergence Analysis This appendix presents the convergence analysis for our algorithm ORAWM for both synchronous and asynchronous environments. B . l P r o o f o f T h e o r e m 5.2 The proof follows the same way as Theorem 1 of [10]. First we prove the following lemma: L e m m a B . l . : If u and v are any two feasible prices, i.e. u,v > 0, then based on Assumptions 1 and 2, V D satisfies the Lipscitch condition | |VD(tt) - VD(v)\\2 < YZ/i \\u - v\\2 Proof, from Equation (5.12), we have V£> = C - fx. Let §f(p) denote the \M\ x |Q| matrix whose {m,q) element %*-(£>) is (T\\ ic HU'm(Wm) <Pq<U'm(wm) 0 Otherwise Appendix B. Resource Allocation for Wireless Multicast: Convergence Analysis 181 If we define ,8m(p) as follows: . Pm.(p) = < umMv)) 0 Otherwise ifU'm(Wm)<pq<U'm(Wri then ^"-(p) in matrix form can be written as dx,„ (P) = -B(p) r7 where B(jp) = Diag(,6m(p);m G M) is the diagonal matrix with diagonal elements /3m(p). Hence, V 2 D = - r ~3 (PJ r B(P) r'1 (B.l) Now from Proposition A.25(e) in [74] and knowing that V2D = F B(p) rT is symmetric (i.e. ||r B(p) r r|| 1 = ||r B(p) rT\\j, then we have ||r.B(p)rT|| 2 < \\rB(p)rT\\x = nrAx(1J2[FB(p)FT}qq, i = maxq J2 F"M FQ'<» q m = max, Y2 Pmfr) rqm Y2 rg'm < YZ/j (B.2) Prom Theorem 9.19 in [82] we have for equation (B.2) \\VD(u)-VD(v)\\.2<YZ/j\\u-v\\2 and hence the result follows. • Appendix B. Resource Allocation for Wireless Multicast: Convergence Analysis 182 Proof. (Theorem 5.2) from lemma B . l . the dual objective function D is lower bounded and V D is Lipschitz. Then, limit point p* of the sequence {p{t)} generated by the gradient projection algorithm in Figure 5.4 for the dual problem is dual optimal provided that 0 < a < (see Proposition 3.4 in [74]). let {p(t)} be a subsequence converging to p*. Since U'm(xm) is defined on a compact interval hu>m,Wm], it is continuous and one-to-one (because of the strict concavity of Um(xm)). Thus, its inverse is continuous (see Theorem 4.17 in [82]) and hence from Equation (5.15), x(p) is continuous. Therefore, l imt_.oo2<'(£) = x(p*) and that proves the result of Theorem 5.2. • Appendix B. Resource Allocation for Wireless Multicast: Convergence Analysis 183 B . 2 P r o o f o f T h e o r e m 5 . 3 The proof for this theorem uses a similar approach like the one in Theorem 3 [6]. However, the difference in our case is that we consider asynchrony amongst the terminal nodes in calculating the accumulated price, which is relevant to the multicast case. We define a vector n(t) = p(t + 1) - p(t) which measures the successive price change with time. First, we prove that the error in rate calculation of group m is bounded by the successive price change 7r: L e m m a B .2 . : The estimated price for group m at time t is defined as follows: i. E E E VP<(*") • : / m i £ f m ?:/m.eV(? t" = t-2B where e t» is defined by a function c(t) = (eqt"(t),q G Q,t" G [t — 2B,t}) as follows: * b q ( t \ t ) . Y ^ B + B A K ^ , t ) ,if / m i € v ? 0 Otherwise and pq(t) = (pq(t"),t" G [t — 2B,t}) is the sequence of clique q's price at time instances t-2B,t-2B + l,--- ,t. Proof. From Equation (5.16) we can write the accumulated price for one branch from group source sm to one of the terminal nodes i G ^sm as follows: A m ( M + l ) = E ( II VA™;)Am,(i) (B.3) Appendix B. Resource Allocation for Wireless Multicast: Convergence Analysis 184 The estimated value at time t is then defined by \n(i,t) =E!'= t-B&m(*'.*) £ ( II l/kmj)\mj(t) j€am=>i j€sm=>i = E ( i i l / & m j ) £ t " = t - 2 B e 9 t " ( * ) P 9 ( * " ) because t t t ( rnin{t"+B,t} \ E M O - E ^ ' V 0 = E E W)U(*") t'=t-B t"=t'-D t"=t-2B \ t'=t-D ) From Theorem 5.1, the group price is then the summation of all the accumulated prices on all the branches and can be written as follows (see proof of Theorem 5.1): t E E E v^( f") i:fmieFm </:/m<eVc* t"=t-2B which proves the lemma. • L e m m a B .3 . : a) For all t 4 - 1 - u'm-\\,n(t))\ < i / 7 , „ YI E |^(*")| A m t"=t-2B i£Q b) For all t t - i | C ( M * ) ) - ^ " I ( A m ( r ) ) | < l / 7 m E E |^ (*')| r«'» t ' = T <?eO Proof. First, we denote x'm(e;p(i)) as xm(eyp{t)) = U'-\ E E E V ' P « ( * " ) ) ( B - 4 ) i:fmi€Fm q:fmieVcq t" =t-2D Appendix D. Resource Allocation for Wireless Multicast: Convergence Analysis 185 where p(t) is the vector of the sequence pq(t) \/q G Q. Hence dxm(e;p{t)) _ rqmpq(t") deqt" and by Assumption 2, we have that \dxm{e;p(t)) 0 < de qt Um(xm(e;p(t))) < {i/7m)rqmpq{t") (B.5) we also denote l(i) = (1 „t»(t)),q G Q,t" G [t - 2B,t]) as 1 ,iiFmnv«=t®,t" =t V'(*) = 4 0 , Otherwise Therefore, U'-\Xm(t)) = xm{e{t);p(t)) and U'~l{Xm(t)) = xm(l(t);p(t)), where xm(.,p(t)) is defined in Equation (B.3). By the mean value theorem (see Proposition A.22 in [73]), we have for some e, ^ dxm{e;p(t)): qeQ,t"e[t-2B,t} d£ql" (V(* ) -v) qt E rqmpqtll{t){iqtll{t)-e \qeQ,t"e[t-2B,t] < 1 /jm V rqm max p(/(0 - pq(t" t-2B<t"<t qt q€Q t-i < l / 7 m E E r ' ' m 7r?(*"' t"=t-2Bq£Q Similarly, also by the mean value theorem, we have that u'-\\m{t)) - U'-\Xm(r))\ < lh,nJ2rqm\pq(t)-pq(T) qeQ t-i < l / 7 m E E r 9 m t'=r Appendix B. Resource Allocation for Wireless Multicast: Convergence Analysis 186 which proves lemma B.3. • The next step is to formulate error in estimating the gradient for the dual objective function in the same way. To do that, we denote the vector £ = (£q(t),q £ Q) to be the gradient estimation used in our asynchronous algorithm. L e m m a B .4 . There exists a constant K\ > 0 such that t-i | |VZ)(p(t))-£(t) | |<i<:i E ||rr(t')|| (B.6) t'=t-2B Proof. First from equation (5.12) and the clique procedure in Figure 5.5 we have that [vD(P(t))-m}q = E r H E bj(t,t)xm(t)-Xm(t) rn : ( F m nK c V0 \l = t - B Where xm(t) is the rate of group m if the group source knows the exact group price Am.(£)• By Proposition A.2 in [74] (i.e. ||.||2 < K'[ H-H )^, we have that \\VD(p(t))-at)\\ < ^ m a x ]T P Y b'>(t',t)xm{t)-xm(t) t'=t-B < K[max. Pqm max xm(t) - xm(t) qeQ il—' t-B<t'<t m : F m n V c V 0 max - K'im*£ E r " m m:FmnV t?^0 Appendix B. Resource Allocation for Wireless Multicast: Convergence Analysis 187 Applying Lemma B.3, we have wvD(p(t))-m\\ Pqm qeQ m:FmnV^% ( max U:-\Xm{t))-U'~l{Xm{t)) + U'.-\Xm{t)) - U'-\Xm(t)) \ t - B < t <t < A,max > rm ~ qeQ ^ 1 max t-B<t'<t { t - i t - i EE' /v™MT)l + E E r , '«lv( r ) l T=i"q'eQ T=t"-2Bq'eQ t-1 = K'Lm&x V rqm max l/jrh V V T v |TT - (r) | t - i r=t-3B where the last inequality follows from Equation (B.2). Note that if we prove the con-vergence with respect to ||7r(t)||1: then the convergence happens with respect to all other norms (see Proposition A.9 in [73]). Hence, if we let K\ = K'tZY/j, then this proves Lemma B.4. • Now that we formulated the gradient in terms of | | 7 r ( £ ) | | , we now show that this norm sequence converges to zero in the following lemma. L e m m a B . 5 . Provided a is sufficiently small we have ||7r(i)|| —> 0 as t —> oo. Proof. First, by Lemma 5.1 in [74] (Section 7.5.4), we have for all t, £T(*)*"(*) < -(!/«) IKOI By Proposition A.32 in [74] and Lemma B . l , there exists K2 such that D(p(t + 1)) < D(p(t)) + \\VD(p(t))-^\\.\\n(t)\\-^-K2)\\7r(t)\\2 2 Appendix B. Resource Allocation for Wireless Multicast: Convergence Analysis 188 applying Lemma B.4 we have D(p(t + 1)) < D(p(t)) -(-- K 2 \ \\n(t)\\2 + K, J2 | H f VCK t"'=t-3B Now it can be shown that E ||T (0 | | - lk(*) l l<^ | |7 r ( t )|| a + i E |H'" t"'=t-3B t"'=t-3B Then we have /J(p(i + l ) ) < / J ( p ( t ) ) - Q - A ' 2 - ( ^ - i ) / r 1 ) | | 7 r ( i ) | | 2 E | H * " V J t"'=t-3B Now, applying this inequality recursively to all D(p(t)),r = t, t— 1, • • • ,1, taking ir(t) = 0 for t < 0, we have D(p(«+1)) < D(P(0))-(^-K2~(3B + 1)K^Y\\7T(T)\\2 By choosing c.v sufficiently small such that — K2 — (ZB + l)I<i) > 0 and since D(p(t)) is bounded, then as t —> oo, we must have YltLo H^ WI2 < °°> a n c ^ hence ||7r(i)|| —» 0 as £ —> oo. This proves Lemma B.5. • Proof. (Theorem 5.3) We first prove that the error due to asynchronism for calculating the group price and rates all converge to zero. Using Lemma B.2, we have that \kn{t) -KM = IE E E ( n v^)E E WW) i&^mt'=t-B jesm=>i j€sm=*i (l£Qt"=t'-B - E E ( II v ,^) E p»w\ = i i E E E • E # ' W O - E E PM i :/m*6F m q:fmieVcW=t-B t"=t'-B i:fmi£Fm q:fmieV* Appendix B. Resource Allocation for Wireless Multicast: Convergence Analysis 189 Similarly as we did in Lemma B.3, we have that \Ki{t) - Xm{t) \ = < Y]rqm max ~t t-2B<l."<t q£Q - -t <Er<^ E | H * " ) ; q&Q t"=t-2B which by Lemma B.5 converges to 0 as t —> oo. Because xm(t) and xm{t) are projections of J/,'"1 onto Im = [wm,Wm] and projection is nonexpansive (see Proposition 2.1.3 in [73]), we have that \xm{t) - x„M < \u'-\xm{t) - u'-\xm(t))\ t, <(l /7m)E r «- E IH^IL qeQ t"=t-2B which also by Lemma. B.5 converges to 0 as t —+ oo for all m G M. We now show that every limit point of the sequence {p(t)} generated by the asyn-chronous algorithm minimizes the dual problem. Let p* be a limit point of {p(t)}. At least one exists, as it is constrained to lie in the compact set, provided a is sufficiently small. Moreover, since the interval between consecutive updates is bounded (Assumption 3), it follows that there exists a sequence of elements of T along which p converges. Let {tk} be a subsequence such that {p(tjt)} converges to p*. By Lemma B.4, we have lim Z(tk) = lirnVD(p(tfc)) - VD(p*) k k Hence [p* - aVD(p*)}+ -p* = lim[p(t,) - a £(i f c)] + - p{tk) = lim ir(tk) = 0 k k Vq{t)-Pq{t) Appendix B. Resource Allocation for Wireless Multicast: Convergence Analysis 190 Then by the projection theorem (Propositions 2.1.3 in [73] and 3.3 in [74]), p* mini-mizes D over p > 0. By duality x* = x(p*) is the unique primal optimal rate. We now show that it is a limit point of {x(t)} generated by asynchronous algorithm. Consider a subsequence {x(tm)} of {x(tk)} such that {x(tm)} converges. Since \\x(t) — x(t)\\ —> 0, then lim x(tm) = lim x(tm) = lim x(p(tm)) = x(p*) fc k k This completes the proof for Theorem 5.3 •
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Utility-based resource and QoS optimization in packet...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Utility-based resource and QoS optimization in packet networks Mohamed, Amr Mahmoud 2006
pdf
Page Metadata
Item Metadata
Title | Utility-based resource and QoS optimization in packet networks |
Creator |
Mohamed, Amr Mahmoud |
Date Issued | 2006 |
Description | Resource Allocation (RA) is used to organize the usage of network’s physical resources in such a way that guarantees optimal utilization while providing predictive performance to network flows in terms of inter-flow fairness and guaranteed Quality of Service (QoS). One approach to provide RA which is particularly suitable for traffic flows with relaxed QoS requirements (i.e. elastic traffic) is the Utility-based Resource Allocation (URA). URA assigns a utility function to each individual user flow to measure the degree of satisfaction of this user as a result of assigning a specific share of resources. The objective of the URA techniques is then to partition the network resources to take full advantage of them in satisfying the QoS requirements of each user flow while providing fair allocation of resource among users by maximizing the aggregate utility of all flows. The objective of this thesis is to devise new methods for URA in wired and wireless networks to provide fair resource sharing and predictive flow performance in terms of QoS while guaranteeing best resource utilization. In so doing, we propose a comprehensive set of algorithms that can be used to provide resource optimization both on the link level or on the network level. On the link level, the thesis proposes a group of algorithms for calculating the optimal classification for a set of traffic flows with diverse QoS requirements to a link with predetermined service levels or predetermined class weights. These algorithms can be used to efficiently study the effect of selecting service levels or class weights according to the distribution of the QoS requirements of the incoming traffic flows. For links with adjustable service levels, we propose two algorithms (OQP, and OQP-OBA) that calculate the optimal partitioning of traffic flows, the best service levels, and the optimal bandwidth allocation to minimize the quantization overhead as a result of QoS-based partitioning. Our simulation results for both link models show that using 4 or 5 service levels will achieve the trade-off between complexity and service level granularity irrespective of the QoS distributions. These algorithms indeed provide major enhancements in that fairly unexplored area. On the network level, a key contribution of this thesis is the development of a new decentralized algorithm (ORAWM) for resource optimization over multihop wireless networks. The algorithm is used to control the rates of the end-to-end sessions utilizing the bandwidth-efficiency feature of multicast to provide resource optimization in a totally distributed network environment without any synchronization requirements between network node calculations. Through analytical modeling and simulations, we prove the convergence of the asynchronous algorithm under slow network changing conditions such as channel capacity and node mobility. We also devise a detailed network architecture and discuss the protocol implementation for deploying ORAWM in an ad hoc network. We also extend our solution to include multicast sessions with heterogeneous receivers (ORAHWM) and discuss the modified network architecture to support, multirate multicast trees. The results show that ORAHWM not only provides flexibility in allocating resources across multicast sessions, but it also increases the aggregate system utility and improves the overall system throughput by almost 30% compared to homogeneous multicasting (ORAWM). We also provide a comprehensive set of simulations that show the effect of deploying these algorithms on the overall resource utilization in an ad hoc network with different environment settings and dynamic network changes (e.g., mobility and route changes). |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-16 |
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.0064898 |
URI | http://hdl.handle.net/2429/18521 |
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_2006-200513.pdf [ 7.49MB ]
- Metadata
- JSON: 831-1.0064898.json
- JSON-LD: 831-1.0064898-ld.json
- RDF/XML (Pretty): 831-1.0064898-rdf.xml
- RDF/JSON: 831-1.0064898-rdf.json
- Turtle: 831-1.0064898-turtle.txt
- N-Triples: 831-1.0064898-rdf-ntriples.txt
- Original Record: 831-1.0064898-source.json
- Full Text
- 831-1.0064898-fulltext.txt
- Citation
- 831-1.0064898.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}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0064898/manifest