ABSTRACT Title of dissertation: MULTICAST COMMUNICATION SUPPORT OVER SATELLITE NETWORKS Gcurrency1un Akkor, Doctor of Philosophy, 2005 Dissertation directed by: Professor John S. Baras Department of Electrical and Computer Engineering In this dissertation, we focus on providing multicast communication support over satellite networks. We investigate the possible performance enhancements in terms of the throughput, capacity, and scalability of a Ka-band, multiple spot-beam satellite com- munication system that supports unicast and multicast services. The role satellite sys- tems play in today?s communication infrastructure is changing rapidly, fueled by the technological advance in the design of new satellite systems, and by the new multimedia service applications, such as on-demand multimedia content delivery, distance learning, and distributed software updates that would bene t from the wide-area coverage, direct and ubiquitous access capability of the satellite systems. These applications require concurrent transmission of the same content to multiple users. In order for multicasting-based services to grow over satellite networks, there must be an incentive to deploy them. We address the problem of user heterogeneity that occurs when multicast users that are located across several different spot-beam locations experience different channel conditions. We propose a novel power allocation scheme for smoothing out the heterogeneity experienced by the multicast groups, while making sure that unicast users get a fair share of system resources as well. Our power allocation scheme would bene t from user feedback in determining the channel conditions. However, collecting feedback from a large set of users is a challenging task in satellite systems, since access to the uplink bandwidth is to be shared between several users, and the resources are usually limited. We introduce a novel algorithm that reduces the volume of feedback information that is to be transmitted over the satellite segment of the network, while maintaining that the relevant information is collected in a timely manner. Finally, we focus our attention to the potential bene ts of integrating packet level forward error correction coding to packet delivery for reliable multicast services over satellite networks. Forward error protection helps recover corrupted data, and minimizes the need for retransmissions over the satellite channel. We investigate the use of a special form of forward error correcting (FEC) code and couple it with an adaptive control mechanism to dynamically adjust the number of encoding packets forwarded to the users. MULTICAST COMMUNICATION SUPPORT OVER SATELLITE NETWORKS by Gcurrency1un Akkor Dissertation submitted to the Faculty of the Graduate School of the University of Maryland, College Park in partial ful llment of the requirements for the degree of Doctor of Philosophy 2005 Advisory Committee: Professor John S. Baras, Chair Professor Ashok K. Agrawala Professor Anthony Ephremides Professor S?ennur Ulukus? Professor Min Wu c Copyright by Gcurrency1un Akkor 2005 To my parents... ACKNOWLEDGMENTS First and foremost I would like to thank my advisor, Dr. John S. Baras, for giving me an invaluable opportunity to work with him on numerous projects over the course of my studies, all of which contributed to the development of my career. I would also like to thank him for his guidance, suggestions, and encouragement during my studies. I would like to thank Dr. Ashok K. Agrawala, Dr. Anthony Ephremides, Dr. S?ennur Ulukus?, and Dr. Min Wu for reading and commenting on my dissertation, and also for the honor they gave me by accepting to take part in my committee. Sincere thanks are due to Dr. Armand Makowski for his mentorship and support during my rst years in this program. I would also like to thank Dr. Michael Hadjitheodosiou who has kindly shared his experience with me, and provided insights and suggestions from an early stage onwards. I would like to acknowledge several institutions that have provided funding for my research. This work has been supported in part by National Aeronautics and Space Administration (NASA award numbers NAG59150 and NCC8235), Lockheed Martin Global Telecommunications (LMGT MIPS award number 251715), and by Hughes Net- work Systems (Hughes MIPS Phase II award number 3027.22). I am also grateful to my friends and colleagues, Karthikeyan Chandrashekar, Ayan Roy-Chowdhury, Majid Raissi-Dehkordi, Mounya El Hilali, Ulas Can Kozat, Kyriakos iii Manousakis, and Georgios Theodorakopoulos. Their support and collaboration have made my experience in this program a memorable one. I would like to thank everyone who in one way or the other helped me to complete my degree. Finally, my gratitude is far less than they deserve for my wonderful parents. With- out their love, endless support, and understanding, this would not be possible. iv TABLE OF CONTENTS List of Tables viii List of Figures ix 1 Introduction 1 1.1 Satellite systems for multimedia and Internet traf c . . . . . . . . . . . 3 1.2 Multicast communication support over satellite networks . . . . . . . . 8 1.2.1 User heterogeneity in multicast communications . . . . . . . . 8 1.2.2 Ef cient feedback collection . . . . . . . . . . . . . . . . . . . 9 1.2.3 Using FEC for reliable multicast delivery . . . . . . . . . . . . 10 2 Multicast-aware Power Allocation in Multiple Spot-beam Satellite Systems 12 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4.1 Solution under BAS-I policy . . . . . . . . . . . . . . . . . . . 27 2.4.2 Solution under BAS-II policy . . . . . . . . . . . . . . . . . . 29 2.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.5.1 The rate-power curve . . . . . . . . . . . . . . . . . . . . . . . 32 2.5.2 Channel model . . . . . . . . . . . . . . . . . . . . . . . . . . 34 v 2.5.3 Spot-beam and antenna con guration . . . . . . . . . . . . . . 36 2.5.4 Rate allocation policy . . . . . . . . . . . . . . . . . . . . . . 41 2.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.6.1 Results under BAS-I policy with logarithmic weights . . . . . . 44 2.6.2 Results under BAS-II policy with logarithmic weights . . . . . 52 2.6.3 Results under BAS-I policy with linear weights . . . . . . . . . 56 2.6.4 Results under BAS-II policy with linear weights . . . . . . . . 60 2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3 A Multiple Subset Sum Formulation for Ef cient Feedback Collection 64 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.2 CSI collection protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3 FIS algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.3.1 Algorithm formulation . . . . . . . . . . . . . . . . . . . . . . 73 3.3.2 Algorithm properties . . . . . . . . . . . . . . . . . . . . . . . 76 3.3.3 Collision avoidance strategy . . . . . . . . . . . . . . . . . . . 78 3.4 Performance analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.4.1 Analysis results . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.5 Multicast-aware power allocation with FIS . . . . . . . . . . . . . . . . 87 3.5.1 Performance of BAS-I policy with FIS . . . . . . . . . . . . . . 90 3.5.2 Performance of BAS-II policy with FIS . . . . . . . . . . . . . 96 3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 vi 4 Integrated FEC Coding for Reliable Multicast Transport 103 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.2 Network scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.3 Packet level FEC coding for reliable multicast communication . . . . . 111 4.3.1 Construction of LT codes . . . . . . . . . . . . . . . . . . . . . 113 4.3.2 Integration of LT codes to packet transmission . . . . . . . . . 115 4.3.3 Adaptive transmission of encoding packets . . . . . . . . . . . 118 4.4 Performance analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 4.4.1 Simulation setup . . . . . . . . . . . . . . . . . . . . . . . . . 120 4.4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 5 Conclusions 133 5.1 Suggestions for future study . . . . . . . . . . . . . . . . . . . . . . . 137 Bibliography 139 vii LIST OF TABLES 2.1 Numerical values for link-budget parameters. . . . . . . . . . . . . . . 34 3.1 Average absolute error. . . . . . . . . . . . . . . . . . . . . . . . . . . 81 viii LIST OF FIGURES 1.1 Hybrid satellite system approach of DirecPC. . . . . . . . . . . . . . . 4 1.2 Two-way satellite system approach of DirecWay. . . . . . . . . . . . . 5 2.1 Satellite communication system architecture. The satellite provides two- way broadband access to users across multiple spot-beam locations. . . 17 2.2 Conceptual view of on-board satellite system and queues. . . . . . . . . 18 2.3 Transmission round concept. . . . . . . . . . . . . . . . . . . . . . . . 21 2.4 Representation of supportable session rates and maximum sustainable session rates for four active ows. . . . . . . . . . . . . . . . . . . . . 23 2.5 Rate-power curves for different rain attenuation levels. . . . . . . . . . 35 2.6 A sample attenuation time series and the cumulative distribution func- tion of rain attenuation. . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.7 Locations of the 48 beams in two polarizations over the United States for the example satellite system. . . . . . . . . . . . . . . . . . . . . . 38 2.8 Beam family and polarization of regional spot-beams. Spot-beams op- erating at the same frequency band are served by the same antenna. . . . 39 2.9 Connection probability distribution. This probability distribution is used to create connections between the NOC and the spot-beam locations. . . 40 2.10 Allocation of spot-beams queues to transmission frame slots. . . . . . . 41 ix 2.11 Percent rate change in the sustainable session rates of all active ows averaged over the test duration under BAS-I policy, compared to the session rates under EAS policy when using logarithmic weight allocation. 45 2.12 Percent of total test time BAS-I session rates are equal to or better than EAS session rates for all active ows when using logarithmic weight allocation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.13 Average power assigned to each spot-beam queue as percentage of total system power over the test duration under BAS-I policy when using logarithmic weight allocation. . . . . . . . . . . . . . . . . . . . . . . 48 2.14 Average service rates of the spot beam queues over the test duration under BAS-I policy when using logarithmic weight allocation. . . . . . 48 2.15 Average rate change in the sustainable session rates of unicast ows averaged over all active unicast ows and average rate change in the sustainable session rates of multicast ows averaged over all active mul- ticast ows under the BAS-I policy when using logarithmic weight allo- cation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.16 Percent of total test time BAS-I session rates of unicast ows are equal to or better than EAS session rates averaged over all active unicast ows and percent of total test time BAS-I session rates of multicast ows are equal to or better than EAS session rates averaged over all active multi- cast ows when using logarithmic weight allocation. . . . . . . . . . . 51 x 2.17 Percent rate change in the sustainable rates of all active ows averaged over the test duration under BAS-II policy, compared to the session rates under EAS policy when using logarithmic weight allocation. . . . . . . 52 2.18 Average power assigned to each spot-beam queue as percentage of total system power over the test duration under BAS-II policy when using logarithmic weight allocation. . . . . . . . . . . . . . . . . . . . . . . 53 2.19 Average service rates of the spot beam queues over the test duration under BAS-II policy when using logarithmic weight allocation. . . . . . 54 2.20 Average rate change in the sustainable session rates of unicast ows averaged over all active unicast ows and average rate change in the sustainable session rates of multicast ows averaged over all active mul- ticast ows under the BAS-II policy when using logarithmic weight al- location. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.21 Percent rate change in the sustainable session rates of all active ows averaged over the test duration under BAS-I policy, compared to the session rates under EAS policy when using linear weight allocation. . . 57 2.22 Percent of total test time BAS-I session rates are equal to or better than EAS session rates for all active ows when using linear weight allocation. 57 2.23 Head-to-head comparison of percent rate change in the sustainable ses- sion rates of unicast ows averaged over all active unicast ows under the BAS-I policy for logarithmic and linear weight allocations. . . . . . 58 xi 2.24 Head-to-head comparison of percent rate change in the sustainable ses- sion rates of multicast ows averaged over all active multicast ows under the BAS-I policy for logarithmic and linear weight allocations. . . 58 2.25 Head-to-head comparison of fraction of total test time BAS-I session rates of unicast ows are equal to or better than EAS session rates when averaged over all active unicast ows for logarithmic and linear weight allocations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.26 Head-to-head comparison of fraction of total test time BAS-I session rates of multicast ows are equal to or better than EAS session rates when averaged over all active multicast ows for logarithmic and linear weight allocations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.27 Percent rate change in the sustainable session rates of all active ows averaged over the test duration under BAS-II policy, compared to the session rates under EAS policy when using linear weight allocation. . . 61 2.28 Head-to-head comparison of percent rate change in the sustainable ses- sion rates of unicast ows averaged over all active unicast ows under the BAS-II policy for logarithmic and linear weight allocations. . . . . . 61 2.29 Head-to-head comparison of percent rate change in the sustainable ses- sion rates of multicast ows averaged over all active multicast ows under the BAS-II policy for logarithmic and linear weight allocations. . 62 xii 3.1 Satellite communication system architecture. The satellite provides broad- band access to users across multiple spot-beam locations. . . . . . . . . 67 3.2 Probability of transmission as a function of . . . . . . . . . . . . . . . 79 3.3 Time-series plot of actual channel attenuation level (dashed-line) versus the level calculated at the NOC (solid-line) for a set of 200 users. . . . . 81 3.4 (a) Fraction of the users suppressed by the FIS algorithm as a function of the number of available uplink time-slots (200 users). (b) Channel usage pro le as a function of the number of available uplink time-slots (200 users). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.5 Average error versus number of available uplink time-slots as a function of the number of active users. . . . . . . . . . . . . . . . . . . . . . . . 84 3.6 Percentage of total time BER target is not met by a user as a function of number of available uplink time-slots (100 users). . . . . . . . . . . . . 85 3.7 Percentage of total time BER target is not met by a user as a function of number of available uplink time-slots (200 users). . . . . . . . . . . . . 86 3.8 Percentage of total time BER target is not met by a user as a function of number of available uplink time-slots (500 users) . . . . . . . . . . . . 86 3.9 Time-slot usage pro le and suppression ef ciency of spot-beams as a function of active multicast groups when using binpacking formulation. 91 3.10 Time-slot usage pro le and suppression ef ciency of spot-beams as a function of active multicast groups when using subset sum formulation. 92 xiii 3.11 Average rate change in the sustainable session rates of unicast ows averaged over all active unicast ows under the BAS-I policy for each of the feedback collection scenarios. . . . . . . . . . . . . . . . . . . . 93 3.12 Average rate change in the sustainable session rates of multicast ows averaged over all active multicast ows under the BAS-I policy for each of the feedback collection scenarios. . . . . . . . . . . . . . . . . . . . 93 3.13 Percent of total test time BAS-I session rates of unicast ows are equal to or better than EAS session rates averaged over all active unicast ows for each of the feedback collection scenarios. . . . . . . . . . . . . . . 94 3.14 Percent of total test time BAS-I session rates of multicast ows are equal to or better than EAS session rates averaged over all active multicast ows for each of the feedback collection scenarios. . . . . . . . . . . . 95 3.15 Percent change in the value of the cost function after optimization with respect to the starting value under BAS-I policy for each of the feedback collection scenarios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.16 Time-slot usage pro le and suppression ef ciency of spot-beams as a function of active multicast groups when using binpacking formulation. 97 3.17 Time-slot usage pro le and suppression ef ciency of spot-beams as a function of active multicast groups when using subset sum formulation. 98 xiv 3.18 Average rate change in the sustainable session rates of unicast ows averaged over all active unicast ows under the BAS-II policy for each of the feedback collection scenarios. . . . . . . . . . . . . . . . . . . . 98 3.19 Average rate change in the sustainable session rates of multicast ows averaged over all active multicast ows under the BAS-II policy for each of the feedback collection scenarios. . . . . . . . . . . . . . . . . . . . 99 3.20 Percent of total test time BAS-II session rates of unicast ows are equal to or better than EAS session rates averaged over all active unicast ows for each of the feedback collection scenarios. . . . . . . . . . . . . . . 99 3.21 Percent of total test time BAS-II session rates of multicast ows are equal to or better than EAS session rates averaged over all active multi- cast ows for each of the feedback collection scenarios. . . . . . . . . . 100 3.22 Percent change in the value of the cost function after optimization with respect to the starting value under BAS-II policy for each of the feed- back collection scenarios. . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.1 Satellite communication system architecture. . . . . . . . . . . . . . . 109 4.2 Proposed breakup of the communication session. . . . . . . . . . . . . 111 4.3 Block diagram for LT encoding. . . . . . . . . . . . . . . . . . . . . . 115 4.4 Average number of encoding packets per batch transmitted in order to complete the le transfer as averaged over all 100 session instantiations. 124 xv 4.5 Average number of transmission rounds per batch in order to complete the le transfer as averaged over all 100 session instantiations. . . . . . 125 4.6 Average size of the transmission window W1 as averaged over all 100 session instantiations. . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.7 Average size of the transmission window W2 as averaged over all 100 session instantiations. . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 4.8 Average time it takes to complete the le transfer at all users, as aver- aged over all 100 session instantiations. . . . . . . . . . . . . . . . . . 127 4.9 Average number of encoding packets per batch transmitted in order to complete the le transfer as averaged over only the sessions that required more than K encoding packets per batch. . . . . . . . . . . . . . . . . 128 4.10 Average number of transmission rounds per batch in order to complete the le transfer as averaged over only the sessions that required more than K encoding packets per batch. . . . . . . . . . . . . . . . . . . . 129 4.11 Average size of the transmission window W1 as averaged over only the sessions that required more than K encoding packets per batch. . . . . . 130 4.12 Average size of the transmission window W2 as averaged over only the sessions that required more than K encoding packets per batch. . . . . . 130 4.13 Average time it takes to complete the le transfer at all users, as aver- aged over only the sessions that required more than K encoding packets per batch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 xvi Chapter 1 Introduction The role satellite systems play in today?s communication infrastructure is changing rapidly. Two main ingredients fuel this change. The rst one is the technological ad- vance in the design of new satellite systems. Next generation satellite communication systems that utilize higher frequency bands, such as the Ka-band, and support spot- beam technology, on-board packet processing and switching are currently under devel- opment [1 3]. These new technologies allow higher data rates, and enable the use of small, low-power, and low-cost user terminals, thereby making satellite communication systems more competitive in price and performance against other broadband commu- nication solutions (cable, digital subscriber line (DSL)). Therefore, satellite commu- nication systems are emerging as a solution for providing integrated voice, data, and multimedia communications to a broader range of users. The second component is the new multimedia service applications for home and business users, such as on-demand multimedia (voice, data, video) content delivery, dis- tance learning, distributed software updates, telemedicine, and e-commerce, that have recently emerged in the Internet. These applications are distributed in nature and require concurrent transmission of the same content to multiple users. Satellite communication systems, with their wide-area coverage, direct and ubiquitous access to large number of 1 users, clearly have an inherent advantage in supporting such services and providing con- nectivity to geographically dispersed regions. According to a report cited by Chitre and Gupta [4], communication satellites carried an estimated 10.5 Gigabit/second of Inter- net traf c in the year 2000. Therefore, despite recent concerns on the future of nancial markets, the share of satellite communication systems in the global communication in- frastructure is likely to increase as these new applications become more mature. In order for multicasting-based services to grow over satellite networks, there must be an incentive to deploy them. From service providers? point of view, there will be an incentive to use multicast delivery only if it results in considerable bandwidth savings and allows deployment of new applications. The problem of providing users with an incentive to use multicast delivery is more dif cult. From a user?s point of view, a high service satisfaction, such as high transmission speed or low service delay, is required whether the provider uses unicast or multicast to deliver the content. Therefore, it is im- perative that the next generation satellite systems provide support for these services, and make sure that they perform favorably compared to existing services and applications. In this dissertation, we investigate the possible performance enhancements in terms of the throughput, capacity and scalability of a multiple-spot beam satellite com- munication system that supports both unicast and multicast services. The favorable char- acteristics of a satellite system, such as the global reach, exible bandwidth-on-demand, and broadcast capability, as well as the shortcomings, such as the relatively long prop- agation delays and the complications of a wireless channel, constitute a unique design 2 space for supporting multicast services. In this dissertation, we combine this design space with the advances in system design, such as on-board switching and spot-beam technology, to achieve performance improvements. In the remainder of this chapter, we provide an overview of the relevant satellite network architectures and current system proposals. Then, we outline the organization of the remaining chapters and highlight our contributions to the literature. 1.1 Satellite systems for multimedia and Internet traf c In the recent years, the amount of data traf c carried over the Internet has increased tremendously as the number of Internet users grew from an estimated 241.5 million in the year 2000, to a projected number of 775.7 million in the year 2005. Although, the capacity and the speed of the links, routers, and switches in the terrestrial backbone net- work have been keeping up with this surge, as service providers increase their capacity, access to the backbone network remains poor for most of the users. While much of the broadband access is via cable (cable modem) or over telephone lines (DSL), there is still a signi cant segment of users that does not have these types of access, especially in parts of the world where the terrestrial infrastructure is less developed. Therefore, there is a market opportunity for satellite service providers in expanding their offerings to support multimedia and Internet traf c. The rst company to provide Internet access via satellite was Hughes Network Systems (HNS) with their DirecPC R service, which since then became the DirecWay R 3 Figure 1.1: Hybrid satellite system approach of DirecPC. system. The DirecPC service employed a hybrid satellite system, where requests for content ( le download, WWW access) were made over the telephone network using a modem connection, while the responses were delivered by the DirecPC Ku-band satel- lite. DirecPC system required a subscription to an Internet Service Provider (ISP) for modem connection, as well as to the HNS system. A hybrid user terminal sent the requests to the Internet server over the telephone network by encapsulating them in a header that routed the response to the HNS satellite gateway rather than back to the user. The gateway was responsible for decapsulating and reformatting the traf c for satellite transmission. The traf c was sent over the satellite network directly to the user terminal (Fig. 1.1). DirecWay system is the next-generation system that supports two-way connectiv- ity over the Ku-band satellite. DirecWay user terminals receive and transmit data over 4 Figure 1.2: Two-way satellite system approach of DirecWay. the satellite network and through the DIRECWAY Network Operation Center, thereby avoid the requirement for the additional connectivity through the telephone network. DirecWay system supports downlink (satellite-to-user terminal) transmission rates of up to 48 Mbps, and uplink (user terminal-to-satellite) transmission rates of 64, 128, and 256 Kbps (Fig. 1.2). DirecWay system is one of the major competitors in the market for providing Internet services over a satellite only network. In addition, there have been several other proposals for launching new systems op- erating primarily at the Ku and Ka frequency bands. Because of the spectrum congestion of the C and Ku frequency bands at the geostationary orbital arc, there is no available or- bital location to place a new satellite without causing interference to any of the existing systems. This have lead to proposals for low-earth-orbit (LEO) or medium-earth-orbit (MEO) satellite constellations at the Ku-band for providing global or near-global cover- 5 age. A list of these systems could be found in [3]. However, due to weak market condi- tions most of these systems are either abandoned or postponed. Besides marketing and nancial concerns, the proposed LEO and MEO systems that operate at the Ku-band were also challenged by the satellite operators of geosynchronous-earth-orbit (GEO) systems that operate at the same band due to the possibility of interference to their sys- tems. We believe that Skybridge system by Alcatel Telecommunications is the only one among the listed systems that is still being pursued. The original Skybridge system was made up of a constellation of 80 LEO satellites that provided a near-global coverage. However, currently, Skybridge services are supported by existing GEO satellites that operate at the C- and Ku-bands, and the LEO constellation is planned to be deployed subsequently if the demand for the services increases in time. Inside the footprint of the satellites, Skybridge gateways aggregate traf c to and from a large number of user termi- nals, and connect them to corporate networks and Internet service providers. Skybridge system supports downlink transmission rates of up to 45 Mbps, and uplink transmit rates of 64 K to 1 Msymbols/second depending on the terminal transmit power [5]. The availability of geosynchronous orbital locations and the wider frequency band segments at the Ka-band have lead to proposals for GEO Ka-band satellite systems, despite the possibility of severe signal attenuation due to rain. A list of these systems could be found in [3]. These systems have also suffered from weak market conditions and the unpredictability of the customer base, and therefore, have either gone through extensive revisions or been abandoned. Among these systems are the Spaceway system 6 proposed by Hughes Network Systems, and the Euroskyway system proposed by the Italian Alenia Aerospazio. Spaceway?s original design comprises of a system of Ka- band satellites that provide coverage using 48 narrow spot-beams (1o 3o) per satellite and 125 MHz of transmission bandwidth per spot-beam. Spaceway satellites support downlink transmission rates of up to 92 Mbps, and uplink transmission rates of 384 Kbps to 1.5 Mbps depending on the terminal. Moreover, they include on-board processing and buffering capabilities that allow packet switching on-board the satellite from one spot- beam to another [6]. Euroskyway system, on the other hand, is made up of a system of Ka-band satellites that support on-board switching and provide downlink transmission rates of up to 32 Mbps, and uplink transmit rates of 160 Kbps to 2 Mbps depending on the terminal type [7]. Additional information on these and similar systems may be found in [2], even though some of the technical speci cations do not agree with other sources due to frequent technical revisions on the design of these systems. Even though the availability and the commercial success of these systems are not known, there are some common traits among them that provide a template for a next- generation system. First of all, utilizing the Ka-band frequency is very desirable, be- cause of the availability of orbital locations, and wider bandwidth segments that would enable the support for multimedia applications. Use of multiple-spot beam coverage enables satellite power to be focused on a smaller area, thereby allowing smaller, low- cost, and low-power user terminals. In order to provide high connectivity, and to support multicast applications between users that are located in different spot-beam coverage ar- 7 eas, however, new systems must also utilize on-board switching and buffering functions. Finally, to make the most out of the broadcast capability and the wide-area coverage of satellites, and to remain competitive against other broadband solutions, these systems must provide the support for emerging multicast services. In this dissertation, we focus on a satellite system template with the characteristics outlined as above, and investigate the requirements for providing multicast support. We leave the discussion of the properties of our system to the subsequent chapters, and choose to introduce them in parallel with the relevant problems we address. In the next section, we give an overview of these problem and our contributions to the literature. 1.2 Multicast communication support over satellite networks 1.2.1 User heterogeneity in multicast communications Utilizing the Ka-band and having multiple spot-beams bring up additional challenges in the design of systems. At Ka-band frequencies, transmitted signals are highly sus- ceptible to degradation due to rain and other atmospheric effects. For high availability, these systems must have means for mitigating the effects of rain attenuation. Moreover, since rain events happen in areas of smaller dimension compared to the satellite foot- print, users across different spot-beam locations are likely to have very different channel characteristics. These effects become more pronounced in case of multicast communi- cation, since the performance of the communication session depends, collectively, on the performance of a group of users that are possibly located across several different 8 spot-beam locations and experiencing different channel conditions. Therefore, there is a need for handling this performance heterogeneity among the users of a multicast session in order to have a quality of service that is acceptable to all of them. Chapter 2 inves- tigates this problem, and proposes a novel power allocation policy for smoothing out the heterogeneity experienced by the multicast group members, while making sure that other users (such as unicast) get a fair share of the system resources as well. Part of our results on this chapter has been presented previously. Earlier work on this subject has been presented in the AIAA International Communications Satellite Systems Confer- ence (ICSSC 2004) [8]. Some of our recent results are included in the paper submitted to the International Journal of Satellite Communication and Network for consideration for publication. 1.2.2 Ef cient feedback collection Any system that adapts to changing propagation conditions would bene t from user feedback. However, collecting feedback from a large set of users is a challenging task in satellite communication systems, since access to the uplink bandwidth is to be shared between several users, and the resources are usually limited. Therefore, allocating a large portion of the available uplink resources to feedback collection is not a viable op- tion. In Chapter 3, we introduce a novel algorithm that reduces the volume of feedback information that is to be transmitted over the satellite segment of the network, while maintaining that the relevant information is collected in a timely manner. We achieve 9 this goal by exploiting the nature of the feedback to be collected and by using the fact that most of the time, only the behavior of a subset of users needs to be tracked. The power allocation policy of Chapter 2 relies on the knowledge of channel conditions across spot-beams in determining the power levels. Therefore, it requires the collection of channel state information from the users. In this chapter, we also integrate our feed- back collection algorithm into the power allocation policy of the previous chapter, and discuss their performance when the two cooperates. Part of the results of this chapter has been presented in the IEEE GLOBECOM Conference (2003) [9] and in the Confer- ence on Information Science and Systems (CISS 2004) [10]. More recent results have been submitted to upcoming IEEE GLOBECOM Conference (2005). 1.2.3 Using FEC for reliable multicast delivery For reliable multicast services over satellite networks, retransmissions of missing data segments are undesirable due long propagation delays and time-varying channel condi- tions. Therefore, primary focus on this topic has been on providing some form of for- ward error protection by transmitting redundant information along with the forwarded data. Forward error protection helps recover missing data segments, and thus, mini- mizes the need for retransmissions over the satellite network. In Chapter 4, we inves- tigate the potential bene ts of using packet level forward error correcting (FEC) codes as a part of a reliable multicast transport protocol. We discuss the limitations of xed- block length FEC codes, and test the use of a special form of packet level FEC codes, 10 namely the Luby?s Transform (LT) codes, which are capable of generating a large num- ber of encoding packets for the same group of input packets. This exibility in the number of encoding packets improves protocol?s robustness against bursty periods of unfavorable channel conditions (e.g. when the transmitted signal experiences deep fad- ing). However, use of forward error protection also reduces the bandwidth ef ciency of the transmission. Therefore, we propose a scheme for adaptively adjusting the number of transmitted encoding packets to the changing propagation conditions. Part of the re- sults of this chapter has been presented in the Conference on Information Science and Systems (CISS 2004) [10]. A more general discussion on reliable multicast transport protocols was presented in the International Journal on Satellite Communication and Networking [11]. 11 Chapter 2 Multicast-aware Power Allocation in Multiple Spot-beam Satellite Systems 2.1 Introduction Unlike unicast communication, where the attributes of the communication session are adjusted according to the capabilities of a single user (receiver), multicast communica- tion is signi cantly complicated by the widely varying capabilities of the members of the multicast group, in terms of available network bandwidth, supportable transmission rates, and traf c load. Heterogeneity in the performance of the receiver group becomes more pronounced in wide-area multicast, where the group members are likely to span several different network domains. This heterogeneity forces the multicast session to adjust to the capabilities of the user or the subset of users with the worst performance. Therefore, the group experiences a performance level that is below the network?s capa- bility. There are several papers in the literature that address the problem of receiver het- erogeneity in terrestrial multicast communication, based on what is identi ed as the source of heterogeneity, and the type of the multicast application. In terrestrial net- works, receiver heterogeneity is generally attributed to the varying congestion levels 12 across different network domains, and to the network bandwidth available to the users behind different bottleneck links. In this case, the multicast session rate has to be set to the level supportable by the most congested link, penalizing the users with higher available bandwidth. To overcome this problem, several authors have suggested lay- ered organization of the transmitted content [12, 13]. In layered multicast transmission, sender distributes the content using layers of increasing bandwidth, while receivers add or drop layers based on their perception of available bandwidth on the path to the sender. This allows each receiver to match its desired rate. However, layered distribution of con- tent is effective, only if the users behind the same bottleneck link act in a coordinated manner, because the action of a receiver dropping a layer (for example, due to perceived congestion) would not be effective unless all the receivers sharing the same bottleneck link drop the same layer. Moreover, if a receiver causes congestion on the bottleneck link by adding a new layer, another might interpret the resulting losses as a consequence of its current level and drop a layer. Therefore, fairness of the protocol requires that all of them have a coordinated behavior [13]. As another point, a layered organization is only possible if the content to be delivered supports it. Layered organization is more ef- fective for video and audio-conferencing applications, where content can be effectively organized into layers of increasing quality [14]. However, for bulk data transfer, this is not always possible. By using a proper arrangement, a similar approach could be used [15, 16], if the data can be processed beforehand. For data generated on the y, it becomes more complex to nd a suitable data organization without wasting network 13 capacity. In multiple spot-beam satellite networks, receiver heterogeneity is also the result of temporal and spatial variation of the physical communication channel. Transmitted signals over the wireless channel are susceptible to fading due to atmospheric and rain attenuation. Rain fading becomes signi cant for systems operating at Ka-band frequen- cies and beyond. Spatial and temporal analysis of rainfall rates in different parts of the world show that the size of intense rain cells range from hundreds of meters to a few kilometers [17], and are of small dimension compared to the footprint of a spot-beam (650km in diameter for a 1o narrow spot-beam of a geosynchronous earth orbit satel- lite). Moreover, instantaneous rainfall rates of two locations that are more than 100km apart can be considered to be independent [18]. Therefore, users residing in different geographical locations are likely to experience highly variable channel conditions. Mitigating the effects of rain attenuation has been an area of focus in the research community. The measures against signal degradation can be grouped into two as diver- sity techniques and compensation techniques. Diversity techniques, such as site- and frequency-diversity, avoid signal degradation by switching between the signals obtained at different receiver sites or between different frequency bands. Site diversity takes advantage of the fact that probability of high attenuation occurring simultaneously at two or more receiver sites is signi cantly lower than any single site. Therefore, sig- nals obtained at multiple sites can be combined (at some central location) to improve the signal-to-noise ratio. Frequency diversity makes use of the fact that signals suffer 14 more from atmospheric attenuation as the frequency of operation increases. Hence, a Ka-band system may switch to lower frequency bands (C or Ku) when the attenuation due to rain exceeds a certain threshold. Other diversity techniques include time- and orbital-diversity [19]. Compensation techniques, such as adaptive coding and modulation, transmission rate reduction, and power control, avoid signal degradation by restoring the signal qual- ity to the initial level. Adaptive coding involves changing the amount of redundancy introduced to the transmitted information as the quality of the link changes. The proba- bility of successful transmission increases as the redundancy level is increased, however, transmission (bandwidth) ef ciency decreases at the same time. Adaptive modulation schemes decrease the required signal-to-noise ratio for achieving a target bit error rate (BER) by reducing the spectral ef ciency (in bps/Hz) of the transmitted signal when fad- ing occurs. A satellite system may switch between higher-order modulation schemes, such as 16-PSK (phase shift keying), 64-PSK, or 254-QAM (quadrature amplitude mod- ulation), under clear sky conditions, and lower-order modulation schemes like BPSK (binary PSK) and QPSK (quadrature PSK) under deep fading. Data rate reduction, on the other hand, achieves an extra margin over the required signal-to-noise ratio by decreasing the information data rate whenever the system experiences deep fading. Fi- nally, in adaptive power control schemes, transmitted power is adjusted dynamically based on the attenuation levels. Power control can be applied on the satellite downlink by changing the satellite effective isotropic radiated power (EIRP), or on the uplink, 15 by controlling the power of earth stations. Adaptive power control (APC) is more ef- cient than providing xed power margins, since severe attenuation occurs typically in short durations. APC can also be easily combined with other compensation techniques if larger fade margins are required [19, 20]. While diversity and compensation techniques improve transmission quality of the users located inside the footprint of the satellite spot-beam, they do not take into account the interaction between the users, such as those belonging to the same multicast group, and the type of the communication (unicast or multicast). The techniques dealing with user heterogeneity in terrestrial multicast communication, on the other hand, focus on the requirements of the multicast communication, however, do not address the hetero- geneity arising from the impairment of the physical channel. This chapter bridges the gap, and investigates the theoretical gains of a multiple spot-beam satellite system that supports both unicast and multicast ows in terms of its utilization and capacity, when adaptive power control and transmission rate reduction are integrated as tools to deal with user heterogeneity in satellite multicast communication. We show that user heterogeneity across spot-beam queues arises not only as a result of the load variation and the types of communication sessions, but also because of the variation of the physical channel conditions. This heterogeneity results in lower allocated session rates for active ows, and may be perceived as unsatisfactory by po- tential users when both unicast and multicast ows are active in the system. We propose an optimization-based approach that controls system power with the goal of smoothing 16 Figure 2.1: Satellite communication system architecture. The satellite provides two-way broadband access to users across multiple spot-beam locations. user heterogeneity, and show that resulting session rates are higher on the average for both unicast and multicast ows. 2.2 Overview In this chapter, we consider a star topology satellite network, where a Ka-band, geo- synchronous satellite provides broadband services to a large number of users located inside its footprint. The satellite supports multiple spot-beams and on-board packet processing and switching technologies that allow transmission of data to multiple users in multiple spot-beam locations (Fig. 2.1). Users that are equipped with two-way direct communication terminals access the backbone terrestrial network through a gateway node referred to as the network operations center (NOC). 17 On-board spot-beam queues On-board antenna sub-system On-board processor, switch Satellite uplink NOC queue Figure 2.2: Conceptual view of on-board satellite system and queues. In this multiple spot-beam satellite system, we consider the delivery of content from NOC to users in response to requests. We assume that each delivery session is identi ed by a unique ow, and packets of several active ows are queued at the NOC, which forwards them to the satellite at a rate limited by the uplink capacity of the sys- tem. An on-board processor and switch forward the packets to one or multiple spot- beam queues, duplicating the packets in the latter case. A packet belonging to a unicast ow is forwarded to a single spot-beam queue, corresponding to the spot-beam location in which the end user resides. In case of a multicast ow, however, members of the mul- ticast session may reside in multiple spot-beam coverage areas, and therefore, packets need to be duplicated and forwarded to multiple spot-beam queues on-board the satellite (Fig. 2.2). At every spot-beam queue, several ows (unicast and multicast) share the total service rate of the queue. The rate-share of a ow that belongs to a particular queue 18 depends on several factors, such as the number of ows currently active in that queue, the type of the ows, and the rate allocation policy between different type of ows, i.e. unicast and multicast. We call this rate-share as the supportable session rate of the ow at that particular queue. A unicast ow would have a single supportable session rate determined by the queue corresponding to the spot-beam location in which the end user resides. However, a multicast ow could have several supportable session rates if the user group was to span more than one spot-beam location. In order to avoid over- owing of any of the on-board queues, the input rate of a ow at the NOC queue have to be determined by the minimum rate the ow can be served at the spot-beam queues. We refer to this rate as the maximum sustainable session rate of the ow. For a unicast ow, the maximum sustainable session rate at the NOC queue equals to its single supportable session rate. The sustainable session rate of a multicast ow, on the other hand, is determined by the minimum of its supportable session rates across (potentially) multiple spot-beam queues. Therefore, heterogeneity in the supportable session rates of a multicast ow would limit its maximum sustainable rate, and may be deemed unsatisfactory by some users. In this system, heterogeneity in the supportable session rates of a multicast ow would occur depending on several factors: - The service rate of each spot-beam queue varies as a function of the allocated power and the channel state, for a given modulation scheme and BER target. Therefore, not all queues can be served at the same effective rate. 19 - The packets of a unicast ow affect the load on only one spot-beam queue, while, in case of a multicast ow, a single session may affect the load on several spot- beam queues. Factors, such as the distribution of users across geographical spot- beam locations and the type of the ows, affect the individual rate-shares of every ow. - The rate allocation policy on how unicast ows are treated in comparison to mul- ticast ows sharing the same queue directly affects how the service rate of the queue is shared between active ows. Therefore, supportable session rate of a multicast ow is determined by the number of active unicast ows in the same queue, causing a variation across different spot-beam queues. In this chapter, the goal is to minimize the heterogeneity that multicast ows expe- rience by smoothing the variation in the supportable session rates of all ows. We show that this type of smoothing could result in higher rate allocations for most active ows, improving the total utilization of the system. In the following section, we describe this approach in an optimization framework and specify the parameters of interest. 2.3 Problem formulation In this system, M on-board spot-beam queues are served by K on-board antennas in a time-divided manner. The downlink transmission is organized into bursts, each of which occupies a xed time interval. During a burst, an antenna serves only one spot- beam queue. We de ne the time it takes to serve each spot-beam queue only once 20 1 2 K 1 2 3 LL-1 Transmission round (frame) A1 A2 AL Figure 2.3: Transmission round concept. with no antenna idling as a transmission round. A transmission round can be viewed as a frame of K rows, each corresponding to an on-board antenna, and L = M=K columns, where we assume, without loss of generality, that L is an integer. We denote byAl; l = 1; 2; : : :; L, as the set of spot-beam queues that are served simultaneously, corresponding to a column of the frame (Fig. 2.3). The transmission rate rj of spot-beam bj; j = 1; 2; : : :; M, at the time of its burst interval, depends on the allocated power pj, and the current channel state sj, according to a general concave rate-power curve j(pj; sj). For any state sj of the downlink chan- nel, rate-power curve represents the rate, under a speci c set of coding schemes, that achieves a target bit error rate as a function of the allocated power. The power levels of 21 all beams satisfy: 0 lj pj Ptot; j = 1; 2; : : :; M; and (2.1) X j2Al pj = Ptot; l = 1; 2; : : :; L; (2.2) where Ptot is the total available system power andfljgMj=1 is a set of lower bounds on the power levels of the queues. A ow fi, for i = 1; 2; : : :; N, which is forwarded to spot-beam queue bj is as- signed a rate-share wij of the service rate of the queue, depending on the load of the queue, and the type of the ows forwarded to it, such that wij = 0 if i =2Bj; (2.3) 0 < wij 1 if i2Bj; (2.4) X i2Bj wij = 1 j = 1; 2; : : :; M; (2.5) where,Bj is the set of all ows that are forwarded to the spot-beam queue bj. Therefore, the packets of ow fi could be served at a supportable session rate of ij = wij rj = wij j(pj; sj); (2.6) at the spot-beam queue bj. However, the maximum sustainable session rate of the ow at the NOC queue is limited to the minimum rate that the ow could be served across spot-beam queues, i.e. i = min j: i2Bj f ijg; (2.7) in order to avoid over owing of the spot-beam queues (Fig. 2.4). 22 On-board spot-beam queues On-board antenna sub-system On-board processor, switch Satellite uplink NOC queue m (1 p ,s )1 1 m (2 p ,s )2 2 M M M(p ,s )m 1 2 M 1 2 K l ,l ,l ,l4 3 2 1 31,l ,l21 11l l ,l32 22 l ,l4M 3M Figure 2.4: Representation of supportable session rates and maximum sustainable ses- sion rates for four active ows. For unicast ows, there exists a single spot-beam queue index j for which i2Bj, corresponding to the beam where the destination user resides. However, for multicast ows, there are several indices for which this may be true. The variation in f ijgMj=1 can be minimized by adjusting the service rates of spot-beam queues, i.e. frjgMj=1. The service rates, in turn, depend on the allocated power levels and the channel states. Therefore, our goal is to minimize this variation by arranging the power level allocated to each queue, subject to a total power constraint, and a given set of channel states. In other words, we would like to nd the optimal vector of power levels p = [p 1 : : :p M] that would minimize the sum of the rate variances of all ows across spot-beam queues: p = arg min p NX i=1 2i ; (2.8) 23 subject to constraints 0 lj pj Ptot j = 1; 2; : : :M; (2.9) X j2Al pj = Ptot l = 1; 2; : : :; L; (2.10) given s = [s1 : : :sM]; (2.11) where, 2i = 1N i MX j=1 xij ( ij mi)2; (2.12) mi = 1N i MX j=1 xij ij; (2.13) xij = 8> >< >>: 1; if i2Bj 0; if i =2Bj ; (2.14) Ni = MX j=1 xij: (2.15) Note that for unicast ows, Ni = 1, and 2i = 0. Therefore, unicast ows do not contribute to the cost function, but they affect the solution since they change the total load on the system and consequently the rate-shares of every ow, i.e. fwijg. In the remainder of this chapter, the rate-power curve is assumed to be of the form rj = (sj) pj; 8j. This assumption is later validated in Section 2.5. In the next section, we provide a solution to (2.8). 24 2.4 Solution When no distinction is made among the spot-beam queues, the simplest assignment would be to set equal power levels for all, such that pj = PtotK ; j = 1; 2; : : :; M: (2.16) We call this assignment, the equal-antenna-share (EAS) policy and denote it by the vector pEAS. Given the channel state vector s, the power vector pEAS completely deter- mines the service rate of each spot-beam queue and the sustainable session rate of each active ow: rEASj = min (sj) pEASj ; rmax ; j = 1; 2; : : :; M; (2.17) EASi = min j: i2Bj w ij rEASj ; i = 1; 2; : : :; N; (2.18) where rmax is the maximum system downlink rate determined by the set of available modulation and coding methods. In the remainder of this chapter, we use the EAS policy as the basis for comparison. Equation (2.17) states that, the EAS policy power assignments may be in excess of the power levels required to achieve the maximum system downlink rate for a given channel state. From (2.18), we can conclude that the supportable session rates of a multicast ow, which are higher than the minimum in (2.18) could be reduced without effecting the maximum sustainable session rate of that ow. Consequently, it may be possible to maintain the same session rate at a lower queue service rate, resulting in a lower power level requirement for a given channel state. Combining these two observa- 25 tions, it is possible to calculate the set of minimum power levels that will maintain the EAS session rates: pminj = max i: i2Bj EAS i (sj) wij ; j = 1; 2; : : :; M: (2.19) Observe that pminj is always less than or equal to pEASj for all spot-beam queues. There- fore, the power difference between the two levels can be re-distributed to other spot- beam queues to possibly improve the session rates of active ows. The power vector with power levels given as in (2.19) is denoted by pMIN. We refer to the solution to (2.8) as the balanced-antenna-share (BAS) policy and denote it by the vector pBAS. We consider two different solutions to (2.8). In the rst case, which we will refer to as the BAS-I policy, the lower bounds on the power levels are set to zero for all beams, i.e. lj = 0; 8j. The total available system power is re-distributed among the spot-beam queues. This setting allows some queues to get power level assignments that are lower than the minimum power levels given in (2.19). Consequently, some ows may be served at rates lower than their rates under the EAS policy. In this case, the fairness of the algorithm becomes an issue, since it does not have control over which ow rates are reduced as a result of the optimization performed. In the second case, which we will refer to as the BAS-II policy, we set lower bounds on the power levels, such that no ow gets a lower sustainable session rate than its rate under the EAS policy, i.e. set lj = pminj 8j. This choice, however, restricts the optimization space since only the excess power could be distributed, but guarantees that the optimization will return rates that are no worse than the EAS policy rates for all 26 active ows. We will elaborate more on the fairness and the effects of having lower bounds in Section 2.6. In the next two sections, we present the solution under both policies. 2.4.1 Solution under BAS-I policy Before proceeding with the solution, we classify spot-beam queues into three sets: (i)E, the set of empty queues for whichBj =;, (ii)U, the set of spot-beam queues with only unicast ows, and (iii)Uc, the set of beam queues with both unicast and multicast ows. Based on this classi cation, the solution power vector can be re-arranged, without loss of generality, as pBAS-I = [pBAS-IE jpBAS-IU jpBAS-IUc ]T: (2.20) Under BAS-I policy, empty spot-beam queues are removed from the calculation by set- ting pj = 0; 8j 2E. The queues with only unicast ows are excluded from the cal- culations as well, because, independent of their service rates, the unicast ows that are forwarded to such queues will have zero rate variance. Therefore, we assign minimum power levels for such queues in order to guarantee that the session rates of the unicast ows are no worse than the EAS session rates, and set pj = pminj ; 8j 2U. Having determined the power levels for the rst two components of the solution vector, where pBAS-IE = 0 and pBAS-IU = pMINU , the values for the power vector pBAS-IUc , of cardinalityjUcjcan be calculated using a Lagrangian formulation as pBAS-IUc = G + Z d; (2.21) 27 where G = X-1 X-1 BT (B X-1 BT) 1 B X-1; (2.22) Z = X-1 BT (B X-1 BT) 1; (2.23) and X is ajUcjxjUcjmatrix, B is a LxjUcjmatrix, d is a Lx1 vector, and is ajUcjx1 vector of Lagrangian multipliers. The matrix X is given by (A 2 VT V), where A is ajUcjxjUcjdiagonal matrix with entries ajj = NX i=1 2 Ni (sj) 2 w2 ij; 8j 2U c; (2.24) and V is a NxjUcjmatrix with entries vij = 1N i (sj) wij; 8j 2Uc; (2.25) and i = 1; 2; : : :; N. The entries of the matrix B represents the mapping of spot-beam queues to antenna groups and given by blj = 8> >< >: 1; if j 2Al 0; if j =2Al ; 8j 2Uc; (2.26) and l = 1; 2; : : :; L. The vector d represents the remaining power available for distribu- tion to the spot-beam queues in setUc following the power assignments to queues in set U, and given by dl = Ptot X j2(U TAl) pMINj ; (2.27) 28 for l = 1; 2; : : :; L. In the solution of (2.21), a non-zero Lagrangian multiplier implies that the corresponding power level must be zero, and we have pj strictly greater than zero when the multiplier j vanishes in (2.21). The service rate vector rBAS-I is determined by pBAS-I and the channel state vector as rBAS-Ij = min( (sj) pBAS-Ij ; rmax); (2.28) for j = 1; 2; : : :; M. 2.4.2 Solution under BAS-II policy Following a classi cation similar to that of the previous case, we assign pBAS-IIE = 0, and pBAS-IIU = pMINU . Under BAS-II policy, all queues that are not empty are guaranteed the minimum power level assignment given in (2.19). Therefore, we start the solution with a base power vector, pBASE, such that pBASE = [0jpMINU jpMINUc ]T: (2.29) Total power used by each subgroup of spot-beam queues under this assignment is given by dBASEl = X j2Al pBASEj ; (2.30) and the remaining power for redistribution is equal to dl = Ptot dBASEl ; (2.31) 29 for l = 1; 2; : : :; L. Therefore, if9l such that dl = 0, there remains no additional power to distribute to spot-beam queues inAl while satisfying the minimum requirement, and those queues will have to remain at their minimum power level assignments. Based on this observation, we can further classify the queues inUc as those in set H = [ l fj : j 2(Uc\Al) and dl > 0g (2.32) and its complement,Hc such thatUc =H[Hc. Also, letLbe de ned as L =fl : dl > 0g: (2.33) Then, the power level assignments for pBAS-IIHc = pMINHc , and the power level assignments for pBAS-IIH of cardinalityjHjis given by pBAS-IIH = pMINH + G + Z d; (2.34) where G and Z are as de ned in (2.22) and (2.23), respectively. X is ajHjxjHjmatrix, B is a jLjxjHj matrix, d is a jLjx1 vector, and is a jHjx1 vector of Lagrangian multipliers. Equation (2.34) represents the power that can be distributed in addition to minimum power assignments. The matrix X is given by (A 2 VT V), where A is ajHjxjHjdiagonal matrix with entries, ajj = NX i=1 2 Ni (sj) 2 w2 ij; 8j 2H; (2.35) and V is a NxjHjmatrix with entries, vij = 1N i (sj) wij; 8j 2H; (2.36) 30 and i = 1; 2; : : :; N. The entries of the matrix B represents the mapping of spot-beam queues to antenna groups and are given by blj = 8 >< >>: 1; if j 2Al 0; if j =2Al ; 8l2L; 8j 2H: (2.37) The vector d represents the remaining power available for distribution to the spot-beam queues in setH following the minimum power assignments to the queues and is given by (2.31) for all l 2 L. In the solution of (2.34), a non-zero Lagrangian multiplier implies that the corresponding power level must remain at the minimum power level, and we have pj > pminj when the multiplier j vanishes in (2.34). The nal solution vector is represented as pBAS-II = [0jpMINU jpBAS-IIH jpBAS-IIHc ]T: (2.38) The service rate vector rBAS-II is determined by pBAS-II and the channel state vector as rBAS-IIj = min( (sj) pBAS-IIj ; rmax); (2.39) for j = 1; 2; : : :; M. In the next section, we describe our analysis framework for evaluating the effec- tiveness of this approach. 2.5 Evaluation In order to evaluate the effectiveness of our approach, we rst have to de ne several components that directly affect its performance. The rst component is the rate-power 31 curve that determines the rate that achieves a target BER, given the allocated power level and the channel state. The next component is the channel model that the channel states are based up on. In order to realistically re ect the distribution of ows across spot-beam queues and to determine the queue-antenna mappings, we have to describe the spot-beam con guration of our architecture. Lastly, we have to determine the rate- allocation policy between the unicast and multicast ows that share the same spot-beam queue. The following sections describe these components in detail. 2.5.1 The rate-power curve The rate-power curve is based on the following link power-budget calculation adapted from an application for a commercial satellite system [2, 6, 21]. For a given transmit power Pt in decibel Watts (dBW), the Equivalent Isotropically Radiated Power (EIRP) for the antenna system in dBW is given by EIRP = Pt + Gt Lt; (2.40) where Gt and Lt are the antenna gain, and the losses in the transmitting equipment in decibels (dB), respectively. The losses due to signal propagation through the atmosphere and rain attenuation are calculated as Lo = Lp + Lr; (2.41) where, Lp and Lr are the losses due to propagation, and rain attenuation, respectively, both in dB. Then, the ratio of signal power to noise power spectral density in decibel 32 Hertz (dBHz) follows as C=No = EIRP Lo + G=T k; (2.42) where G=T in decibels per Kelvin (dB/K) is called the gure of merit of the receiver determined by the antenna gain G (dB) and its overall noise temperature T in Kelvin (K), and k is the Boltzmann constant in dBW/K/Hz. For a bit rate of Rb in dBHz, the ratio of bit energy to noise power density becomes Eb=No = C=No Rb in dB: (2.43) The rain attenuation becomes substantial at Ka-band frequencies, and is the most impor- tant factor. Therefore, we assume that all other effects remaining constant we can express the rate as a function of the transmit power Pt and the rain attenuation level Lr for a given Eb=No value that guarantees a target BER for a given coding and modulation scheme. Consequently, one can rewrite (2.43), to determine the rate that achieves the target BER for a given power and rain attenuation level: Rb = Pt + (Lr); (2.44) where (Lr) = Gt Lt Lp + G=T k Eb=No Lr. It is possible to express (2.44) in linear terms: Rb = (Lr) Pt in bps: (2.45) We will use (2.45) in calculating the rate-power relationship for a given rain attenuation level of the channel. Figure 2.5 shows rate-power relationship for different levels of 33 Gt (dB) Lt (dB) Lp (dB) 46:50 0:50 210:75 G=T (dB/K) k (dB/K/Hz) Eb=No (dB) 16:37 228:60 3:56 Table 2.1: Numerical values for link-budget parameters. rain attenuation. Throughout this analysis, we assume that rate is a continuous function of power, even though, in real systems, not all rates may be achievable depending on the set of modulation and coding schemes available for implementation. The numerical values for the link-budget parameters are given in Table 2.1. 2.5.2 Channel model The choice of the frequency band is not restrictive for our problem setting, but we be- lieve that next generation systems are moving in the direction of using higher frequency bands, because higher bands offer wider bandwidth segments that are not available at more crowded lower frequency bands. Therefore, we use a Ka-band channel model in our evaluations. In order to determine the rain attenuation levels for the Ka-band channel, we use a model that is based on the simulator developed at DLR (German Aerospace Center), Institute for Communications and Navigation [22, 23]. The model is based on speci c channel model parameters from the DLR measurement campaign carried out at Oberp- 34 0 0.5 1 1.5 2 2.5 3 106 107 108 Power (W) Rate (bps) 2 dB 4 dB 8 dB 16 dB Rain Attenuation (dB) Figure 2.5: Rate-power curves for different rain attenuation levels. 35 faffenhofen near Munich, Germany, in the years 1994 till 1997 with the 40 GHz beacon of the Italian satellite ITALSAT. The channel simulator generates a time-series of atten- uation, and calculates the cumulative distribution of attenuation. It is also possible to extract the probability of being in a fade exceeding a given duration and exceeding a fading depth given as parameter. The simulator generates a time-series with 64 seconds resolution. Each attenua- tion level sample in decibels is input to (2.44), which through the link-budget calculation gives the downlink rate as a function of allocated antenna power. Figure 2.6 shows a sample realization of the rain attenuation time series and the corresponding cumulative distribution function for the channel model simulator. 2.5.3 Spot-beam and antenna con guration In order to evaluate the performance of our approach, we need to create unicast and multicast ows between the NOC and the spot-beam locations. However, the number of unicast and multicast ows forwarded to each spot-beam location and the distribution of the multicast users across these locations should re ect the possible load imbalance in a real multiple spot-beam satellite system. Therefore, we rst consider the beam locations and the corresponding antenna assignments of a geostationary satellite proposed for a commercial satellite system in [6, 21]. Figure 2.7 shows the approximate locations of the M = 48 spot-beams in two polarizations over the United States for this system as indicated by 24 circles. In each circle, the upper and lower identi ers denote the left- 36 0 1 2 3 4 5 6 7 8 9 10?50 ?40 ?30 ?20 ?10 0 Time (days) Signal attenuation (dB) 0 5 10 15 20 25 30 35 40 45 5010 ?5 100 Attenuation (dB) P(a ? x) Figure 2.6: A sample attenuation time series and the cumulative distribution function of rain attenuation. 37 Figure 2.7: Locations of the 48 beams in two polarizations over the United States for the example satellite system. and right-polarized spot-beam signals, respectively. The frequency assignments for each beam family are as shown in Fig. 2.8. Next, based on the approximate geographical area covered by each spot-beam, we have calcu- lated the approximate population illuminated by each spot-beam, using the most recent U.S. Census Data [24]. Assuming that a ow fi is more likely to be forwarded to spot- beam queue bj if the spot-beam illuminates a larger fraction of the total population, we calculated the probability distribution plotted in Fig. 2.9. This distribution gives the probability of a ow being forwarded to a spot-beam for all 48 spot-beams and is used to initiate sessions between the NOC and the spot-beam locations. 38 Figure 2.8: Beam family and polarization of regional spot-beams. Spot-beams operating at the same frequency band are served by the same antenna. 39 Figure 2.9: Connection probability distribution. This probability distribution is used to create connections between the NOC and the spot-beam locations. The spot-beams share the access to K = 4 on-board antennas in TDM fashion. Therefore, we have to determine the sets,Al; l = 1; 2; : : :; L = M=K = 12, of spot- beams that correspond to the allocation of TDM slots. The spot-beam queues that belong to the same set will access the antennas simultaneously. Therefore, two spot-beams operating at the same frequency band should not belong to the same set. In addition, to limit interference, the left- and right-polarized signals serving the same spot-beam location should operate in different sets. The problem of allocating spot-beams to TDM slots can be put into an optimization framework by itself. However, it is out of the scope of our problem setting. In this chapter, we assume that the system would make an attempt to distribute the load evenly among the antennas, and therefore, divide the spot-beam queues into 4 groups based on their connection probability values given in 40 1 3 K=4 1 L=12 A1 A12 2 A 1 -R A 2 -R A 3 -R A 4 -R A 5 -R A 6 -R B 1 -L B 2 -L B 3 -L B 4 -L B 5 -L B 6 -L B 6 -R B 5 -R B 2 -R B 1 -R B 4 -R B 3 -R A 5 -L A 4 -L A 1 -L A 2 -L A 3 -L A 6 -L C 5 -R C 1 -L C 2 -R C 4 -L C 3 -L C 3 -R C 2 -L C 1 -R C 5 -L C 4 -R D 6 -R D 4 -R D 2 -R D 1 -R D 3 -R D 7 -R D 5 -R D 1 -L D 4 -L D 7 -L D 2 -L D 3 -L D 5 -L D 6 -L Figure 2.10: Allocation of spot-beams queues to transmission frame slots. Fig. 2.9. We, then, pick one spot-beam queue from each group when assigning them to the sets subject to the constraints given as above. The resulting sets are shown in Fig. 2.10. Though this assignment is possibly not unique, any assignment that adheres to the constrains that we have imposed is suf cient for our purposes. 2.5.4 Rate allocation policy Finally, we have to determine how the service rate of each spot-beam queue is shared among the unicast and multicast ows forwarded to the beam. The policy determines how multicast ows are treated compared to unicast ows sharing the same bottleneck, in this particular case, the same spot-beam queue. In order to give some incentive for multicast delivery over unicast, rate allocation proportional to the number of users down- 41 stream of the bottleneck has been suggested in the literature. In [25], authors compare three policies that allocate resources: (i) as a logarithmic function of the number of users downstream of the bottleneck, (ii) as a linear function of the number of users, and (iii) as equally between unicast and multicast ows independent of the number of users. Their analysis show that logarithmic allocation achieves the best tradeoff between user satis- faction and fairness among unicast and multicast ows compared to other alternatives. In this dissertation, we test our algorithm with linear and logarithmic weight allocation policies. Independent allocation of weights to unicast and multicast ows is of no inter- est to us, since we believe that, for effective deployment of multicast delivery, there is a need to allocate more resources to multicast sessions over unicast ones. The rate-share wij of a ow fi in spot-beam queue bj is determined by nij, which is the number of receivers of the ow that resides in the area illuminated by the beam. In linear allocation, the weights are given by wij = 8 >>> < >>> : 0; if nij = 0 nijP k2Bj nkj ; if nij 6= 0 (2.46) for i = 1; 2; : : :; N and j = 1; 2; : : :; M. This scheme allocates n times more resources to a multicast ow with n downstream users than a unicast ow with one downstream user. However, this policy may be too aggressive in favoring multicast ows. The alternative is to use a logarithmic distribution. For logarithmic allocation, the weights 42 are distributed as wij = 8> >>< >>> : 0; if nij = 0 1+log(nij)P k2Bj 1+log(nkj); if nij 6= 0 (2.47) for i = 1; 2; : : :; N and j = 1; 2; : : :; M. In the next section, we calculate the power levels of all spot-beam queues and the maximum sustainable rates of every ow under BAS policy and compare our results to the values under EAS policy. 2.6 Results In this section, we will present numerical results on the performance of our approach. The results on BAS policy are given in comparison to the performance under the EAS policy, i.e when power levels are equally distributed. In each case, the system is loaded with Lu unicast connections, and Lm multicast connections that are generated between the NOC and the spot-beam locations, according to the distribution function given in Fig. 2.9. The multicast group size Gm is assumed to be distributed log-normally such that mean and standard deviation of log(Gm) is log(25) and 0:5, respectively. In the numerical results, the number of active unicast connections is set to Lu = 350, such that in the absence of multicast connections, the average session rate of a unicast ow is approximately 10 Mbps. The maximum downlink rate is set to rmax = 92 Mbps. Each set of calculations are repeated for 100 different session con gurations to obtain the statistical results. In the following sections, we discuss our results under both BAS-I 43 and BAS-II policies. 2.6.1 Results under BAS-I policy with logarithmic weights In this section, we start looking at the results under BAS-I policy when using logarith- mic weight allocation. The rst set of results looks at the performance of the algorithm for a x number of unicast and multicast connections while channel conditions change over time. In this scenario, there are Lu = 350 active unicast connections, and Lm = 25 active multicast connections. In our analysis we assume that the optimization is per- formed every 64 seconds, which is the step size of our channel simulator for generating an attenuation level sample. An independent instance of the channel simulator is run for each spot-beam. At every step, the channel states for all 48 spot-beams are sampled and power distribution levels under the BAS-I policy are re-calculated. Using the rate-power curve, the service rates of all spot-beam queues, and the sustainable session rates of all active ows are calculated for each time step. The test is performed for a simulated time of 720 minutes corresponding to T = 675 samples. In Fig. 2.11, we plot the percent change in the sustainable session rates of all active ows averaged over the total number of samples, given by BAS-Ii = 100 1T TX t=1 BAS-I i [t] EAS i [t] EASi [t] : (2.48) for i = 1; 2; : : :; Lu + Lm. We observe that all of the active multicast and unicast sessions are served at higher average session rates compared to the EAS policy case. The multicast ows experience 44 Figure 2.11: Percent rate change in the sustainable session rates of all active ows av- eraged over the test duration under BAS-I policy, compared to the session rates under EAS policy when using logarithmic weight allocation. an average increase of 95% in their sustainable session rates, while unicast ows expe- rience average gains of 37%. Unicast ows experience a more moderate improvement compared to multicast ows. There are two factors behind this behavior. First, the op- timization policy tries to minimize the rate variance experienced by all multicast ows, without taking into account the rates of the unicast ows sharing the same queues as the multicast ows. As a result, multicast ows bene t the most from the re-arrangement of power levels across spot-beam queues. Therefore, the fairness of the BAS-I policy at a per- ow level is an issue, even though, the net system throughput is increased. Secondly, BAS-I policy allows power levels to go to zero, therefore, the service rates of some spot-beam queues drop down to levels that are lower than their EAS rates 45 at the end of the optimization. Consequently, the ows incident to them have lower session rates. As a result, the instantaneous rate of an active ow may drop down to a level lower than the EAS rate, even though the average rate of the ow remains higher than the EAS rate. Therefore, it is important to look at the percentage of total time the sustainable session rates of all active ows remain at a level equal to or higher than their EAS session rates. In Fig. 2.12, we look at this metric given by BAS-Ii = 100 1T TX t=1 1 BAS-Ii [t] EASi [t] ; (2.49) for i = 1; 2; : : :; (Lu + Lm), where 1( ) is the indicator function. We observe that for unicast connections, the ow rates are below the EAS rates approximately 25% of the time, while this number is approximately 5% for multicast ows over the same duration. Therefore, for unicast ows, the instantaneous ow rates drop below EAS rates for a signi cant fraction of the time. From a user point of view, this uctuation in the session rate of an active ow may not be desirable for some applications, even thought the session rate is higher on the average. In Fig. 2.13, we plot the percentage of total power assigned to each spot-beam queue, and in Fig. 2.14 the corresponding service rates, given by pBAS-Ij = 100 1T TX t=1 pBAS-Ij [t]; and (2.50) rBAS-Ij = 1T TX t=1 rBAS-Ij [t]; (2.51) respectively, for j = 1; 2; : : :; M. Observe that several spot-beam queues have average power levels that are below the minimum power levels that would maintain the EAS 46 Figure 2.12: Percent of total test time BAS-I session rates are equal to or better than EAS session rates for all active ows when using logarithmic weight allocation. session rates. Consequently, all unicast ows forwarded to such queues have lower session rates than their EAS rates giving rise to the behavior we observe in Fig. 2.12. The second set of results looks at the average performance of the BAS-I policy under changing group dynamics. In these experiments, there are Lu = 350 unicast ows, while the number of active multicast groups is varied between Lm = 5 to 30. In Fig. 2.15, we plot the change in the sustainable session rates averaged over all active unicast and multicast ows, i.e. BAS-Iu = 1L u LuX i=1 BAS-Ii ; (2.52) and BAS-Im = 1L m (Lu+Lm)X i=Lu+1 BAS-Ii ; (2.53) as the number of active multicast groups is varied. 47 Figure 2.13: Average power assigned to each spot-beam queue as percentage of total system power over the test duration under BAS-I policy when using logarithmic weight allocation. Figure 2.14: Average service rates of the spot beam queues over the test duration under BAS-I policy when using logarithmic weight allocation. 48 Figure 2.15: Average rate change in the sustainable session rates of unicast ows av- eraged over all active unicast ows and average rate change in the sustainable session rates of multicast ows averaged over all active multicast ows under the BAS-I policy when using logarithmic weight allocation. 49 We observe that unicast ows experience an increase of 20 40% in their average session rates while the number of active multicast connections is varied. The increase in the average session rate becomes more signi cant as the system is loaded with more active multicast ows. This is because, when there are very few multicast ows, most of the queues have only unicast connections and our optimization framework excludes such queues, i.e such queues remain with their minimum power assignments. As the unicast and multicast ow mix increases, more queues are included in the re-distribution of power. Multicast ows experience 70 100% increase in their average sustainable session rates. Finally, in Fig. 2.16, we plot the percentage of time ows have higher session rates than their EAS rates as the number of active multicast connections is varied. From the results of this section, we conclude that BAS-I policy increases the aver- age session rates for both types of ows, however, (i) the policy is unfair against unicast ows, and some unicast ows may see a decrease in their rates, and (ii) although the session rates are higher compared to EAS session rates on the average, instantaneous values may drop below the EAS values. BAS-II policy elevates these issues by impos- ing bounds on the power levels to guarantee that session rates remain at or above EAS policy values at all times for both types of ows. In the next section, we look at the performance of the BAS-II policy under similar test settings. 50 Figure 2.16: Percent of total test time BAS-I session rates of unicast ows are equal to or better than EAS session rates averaged over all active unicast ows and percent of total test time BAS-I session rates of multicast ows are equal to or better than EAS session rates averaged over all active multicast ows when using logarithmic weight allocation. 51 Figure 2.17: Percent rate change in the sustainable rates of all active ows averaged over the test duration under BAS-II policy, compared to the session rates under EAS policy when using logarithmic weight allocation. 2.6.2 Results under BAS-II policy with logarithmic weights In this section, we look at the same set of metrics under the BAS-II policy when using logarithmic weight allocation. In Fig. 2.17, we plot the percent change in the sustainable session rates of all active ows averaged over a similar test duration of 720 minutes corresponding to T = 675 samples. Under BAS-II policy, unicast ows experience an average increase of around 17% in their sustainable session rates, while multicast ows have an increase of around 27%. We observe that, compared to BAS-I policy, the increase in the session rates of both types of ows is down, however, instantaneous session rates of all unicast and multicast ows remain above the EAS session rates at all times for all ows, i.e. BAS-IIi = 100%; 8i. 52 Figure 2.18: Average power assigned to each spot-beam queue as percentage of total system power over the test duration under BAS-II policy when using logarithmic weight allocation. In Fig. 2.18, we plot the percentage of total power assigned to each spot-beam queue, and in Fig. 2.19, the corresponding service rates. Note that under this policy, all power levels are at or over the minimum power levels required to maintain EAS policy session rates for all active ows. We observe that, the average power levels and service rates across spot-beam queues are now more uniformly distributed compared to the levels under the BAS-I policy. The second set of results look at the average performance of the BAS-II policy under changing group dynamics. In these experiments, there are Lu = 350 unicast ows, while the number of active multicast ows is varied between Lm = 5 to 30. In Fig. 2.20, we plot the change in the sustainable session rates averaged over all ows as 53 Figure 2.19: Average service rates of the spot beam queues over the test duration under BAS-II policy when using logarithmic weight allocation. the number of active multicast connections is varied. Under BAS-II policy, both types of ows bene t less from the optimization, however, their average rates remain 15 30% above their EAS session rates. One important observation to make is that this time mixing of unicast and multicast ows negatively affect the improvement of multicast ows (compare to Fig. 2.15). This follows from the fact that when more active ows are present under BAS-II policy, the lower bound constraints restrict the optimization space, and the system has less exibility in distributing the power. Therefore, we would expect under BAS-II policy that a very heavy loaded system would cause all ows to remain at their EAS policy session rates. We can conclude that BAS-II policy still attains desirable performance improve- ments in terms of the average sustained session rates, while solving the fairness related 54 Figure 2.20: Average rate change in the sustainable session rates of unicast ows av- eraged over all active unicast ows and average rate change in the sustainable session rates of multicast ows averaged over all active multicast ows under the BAS-II policy when using logarithmic weight allocation. 55 issues of the BAS-I policy. In the following sections, we look at the effect of having linear weight allocation on the performance of our allocation policies. 2.6.3 Results under BAS-I policy with linear weights In this section, we make a head-to-head comparison to the results of the previous sec- tions. We rst look at the performance for a x number of unicast and multicast connec- tions while channel conditions change over time. In this scenario, there are Lu = 350 active unicast connections, and Lm = 25 active multicast connections as in the previous cases, but the weights are allocated linearly in the system. In Fig. 2.21, we plot the percent change in the sustainable session rates of all active ows averaged over the total number of samples, and in Fig. 2.22, the corresponding gure for the total fraction of time session rates are above the EAS rates. In both cases, we observe a very similar performance trend in comparison to the cases when using logarithmic weights. In the next set of gures, we compare how having linear weights fares when the number of ac- tive multicast groups is varied. Figures 2.23 and 2.24 compare the average rate change experienced by unicast and multicast ows, respectively under the two different weight allocation schemes. We observe that with both logarithmic and linear weights, the per- formance improvement over the EAS policy case remains in the same range. Therefore, we conclude that, in terms of the relative improvement over the EAS policy, the results are insensitive to the choice of the weights. Figures 2.25 and 2.26 compare the fraction of total test time BAS-I session rates 56 Figure 2.21: Percent rate change in the sustainable session rates of all active ows av- eraged over the test duration under BAS-I policy, compared to the session rates under EAS policy when using linear weight allocation. Figure 2.22: Percent of total test time BAS-I session rates are equal to or better than EAS session rates for all active ows when using linear weight allocation. 57 Figure 2.23: Head-to-head comparison of percent rate change in the sustainable session rates of unicast ows averaged over all active unicast ows under the BAS-I policy for logarithmic and linear weight allocations. Figure 2.24: Head-to-head comparison of percent rate change in the sustainable session rates of multicast ows averaged over all active multicast ows under the BAS-I policy for logarithmic and linear weight allocations. 58 Figure 2.25: Head-to-head comparison of fraction of total test time BAS-I session rates of unicast ows are equal to or better than EAS session rates when averaged over all active unicast ows for logarithmic and linear weight allocations. of unicast and multicast ows are equal to or better than EAS session rates, respectively, when using logarithmically and linearly allocated weights. We observe that having linear weight allocation mostly favors multicast ows in terms of the fraction of total time these ows are allocated a rate above their EAS rates. This result is attributed to the fact that under linear weight allocation, consistently more bandwidth is allocated to multicast ows than unicast ows. However, on the overall, our observations suggest that weight allocation scheme does not have a pronounce effect on the performance of our algorithm. 59 Figure 2.26: Head-to-head comparison of fraction of total test time BAS-I session rates of multicast ows are equal to or better than EAS session rates when averaged over all active multicast ows for logarithmic and linear weight allocations. 2.6.4 Results under BAS-II policy with linear weights This section presents the corresponding performance graphs when using linear weights under BAS-II policy. Figure 2.27 plots the average rate change in the sustainable session rates of all active ows over the test duration when using linear weights. Figures 2.28 and 2.29 provide head-to-head comparison of logarithmic and linear weights in terms of the percent rate change experienced by unicast and multicast ows, respectively, un- der BAS-II policy. These results strengthen the conclusion that the choice of weight allocation scheme does not have a pronounce effect on the performance of both policies. 60 Figure 2.27: Percent rate change in the sustainable session rates of all active ows av- eraged over the test duration under BAS-II policy, compared to the session rates under EAS policy when using linear weight allocation. Figure 2.28: Head-to-head comparison of percent rate change in the sustainable session rates of unicast ows averaged over all active unicast ows under the BAS-II policy for logarithmic and linear weight allocations. 61 Figure 2.29: Head-to-head comparison of percent rate change in the sustainable session rates of multicast ows averaged over all active multicast ows under the BAS-II policy for logarithmic and linear weight allocations. 2.7 Summary In this chapter, we have introduced an optimization framework for balancing the spot- beam queue service rates such that the sum of the rate variances of all active multi- cast ows is minimized. This is achieved through the re-distribution of system power among spot-beam queues, taking into account the load on the queues and the channel states. The rate variance metric effectively captures the fact that multicast ows affect the load distribution of multiple spot-beam queues, and is used to achieve performance improvements from it. We provided two alternative policies, BAS-I and BAS-II, re- spectively. BAS-I policy does not impose any lower bounds on the minimum power level to be assigned to each spot-beam queue, and therefore may be unfair at a per- ow 62 level. However, the policy increases the sustainable session rates of multicast ows by 70 100% when averaged over all active multicast ows. BAS-II policy imposes tight lower bounds on the power levels and, therefore, the multicast ows experience an in- crease of up to 30%. However, the policy also guarantees that the unicast ows do not see a performance degradation in their rates at the end of the optimization. Depending on the application, the type of the ows, and the service rate guarantees provided by the service provider, it may not be necessary to require a strict minimum rate for all active ows. Therefore, an extension to the current policies is under study to provide a quality of service (QoS) or priority based minimum rate requirement to all active ows. In this alternative policy, a QoS level is attached to all ows to determine which ows are allowed a reduced rate, and what are the minimum rate requirements. This information is used to determine the minimum power levels for each spot-beam queue. On the overall, we conclude that it is possible to improve the performance of the system by careful tuning of system parameters to the requirements of the ows supported by it, and provide an example to the fact that future systems must be designed to support multiple types of ows. 63 Chapter 3 A Multiple Subset Sum Formulation for Ef cient Feedback Collection 3.1 Introduction The previous chapter overviewed various adaptive schemes for mitigating the effects of atmospheric and rain fading in satellite communication systems, and focused on an adaptive power allocation and rate reduction policy for overcoming user heterogeneity in multicast communication over satellite networks. Although the policy explicitly relies on the knowledge of channel states for calculating the effective downlink rates of each spot-beam queue, we have simply assumed that this information was readily available to the system, and have not discussed how it was obtained. In general, however, any scheme that adapts system parameters to the changing propagation conditions would typically have to perform a series of common functions that involves the monitoring, prediction, and estimation of the channel conditions. User feedback would be a valuable input for a number of such components, how- ever, collecting periodic feedback from a large number of users would result in the well-known feedback implosion problem. Feedback implosion is identi ed as a major problem when a large number of users try to transmit their feedback messages to a cen- tral node, causing high traf c concentration and backlog in the network. Although not 64 unique to satellite based networks, feedback implosion phenomenon has additional side effects in this context, since a signi cant portion of the uplink resources may be hold up to transmit these feedback messages instead of useful data traf c, and the access to the shared medium may be clogged [11, 26]. The fact that the satellite return channel (uplink) is a shared medium, and that the satellite spectrum is limited and expensive, makes it necessary to minimize the amount of bandwidth required for transmission of user feedback. Feedback implosion problem has been studied in the literature as part of several terrestrial multicast transport protocols, which rely on user feedback for providing reli- able transmission. In this context, feedback implosion arises when individual users con- rm reception of a data packet by sending positive acknowledgments, or request retrans- mission of a data packet by sending negative acknowledgments to the source. Therefore, several existing terrestrial multicast protocols adopt feedback suppression and feedback aggregation schemes to control the number, and the ow of feedback packets. Feedback aggregation is applicable in networks where a logical or physical hierarchy is possible. Feedback aggregation relies on intermediate entities in the network, such as routers, to collect, lter-out and combine feedback information as it traverses the network towards the source. For example, an intermediate router could collect positive acknowledgments sent by several users for the same data packet, and forward only one (aggregated) ac- knowledgment towards the source. This aggregation towards the root of the hierarchy cuts back on the number of feedback reports and prevents receivers from contacting the 65 source directly, enabling the protocol to scale over a larger set of receivers. Feedback aggregation schemes require additional functionality at the intermediate routers of the network [27]. This raises questions about whether such router extensions can be standardized, deployed, and automatically con gured in the backbone network. In order to circumvent this problem, feedback suppression algorithms control the num- ber of feedback packets created and forwarded by every user, instead of controlling the volume of feedback information by aggregation. In terrestrial networks, a typical implementation of feedback suppression would require users to listen to the feedback messages that were multicasted or broadcasted to the network by other users, and to suppress their own feedback if the message is redundant or is covered by some other message. For example, a user could suppress its own negative acknowledgment for a missing packet, if some other user has already sent a negative acknowledgment for the same packet, since the source would be multicasting the packet to all users as soon as the rst acknowledgment is received. Coupled with random timers and statistical back- off, this type of feedback suppression would, in an ideal setting, let only one feedback report to be returned to the sender for every missing packet [28 31]. However, multicast (broadcast) forwarding of feedback reports must be scoped by use of time-to-live (TTL) elds to minimize the ooding of the network by feedback packets. Revisiting the typical satellite deployment scenario from the previous chapter (Fig. 3.1), feedback aggregation would not be a viable solution in this architecture, since the star topology of the network does not lend itself into a hierarchy, and users 66 Figure 3.1: Satellite communication system architecture. The satellite provides broad- band access to users across multiple spot-beam locations. have to share the uplink access in each spot beam location. Even if feedback aggrega- tion techniques are used in the local domains, such as the local area networks, feedback implosion would remain to be a challenge due to the potentially large number of termi- nals. A feedback suppression implementation similar to that of the terrestrial networks is also not possible, since in general, there exists no secondary network or communi- cation among the users to distribute the feedback messages. Even though the satellite can replay back the feedback packet it received from a user by broadcasting it to all the receivers, delay incurred during the coordination would be unacceptable in most cases, because of the long propagation delays. For example, a user would have to wait on the order of seconds to listen to the feedback messages of others before deciding on whether to transmit its own message. 67 However, other possible implementations of feedback suppression is possible, if, for example, a representative (or a set of representatives) among the users could be se- lected to transmit feedback messages for the group. Several proposals look at ef cient transmission of feedback messages over the satellite uplink without relying on terrestrial return paths. In [32], the proposed algorithm uses a round-robin time division multiple access (TDMA) scheme on the uplink channel. The disadvantage is that, it does not scale well with increasing number of receivers, since more uplink bandwidth has to be allocated for feedback transmission. In [33], the authors group receivers into clusters, where only the cluster heads transmit feedback over the satellite link. Although this scoping reduces the number of users that have to access the uplink channel, the ap- proach assumes that receivers inside a cluster are able to communicate with each other through a secondary network. Some of the more recent work tries to avoid any commu- nication and collaboration between the users. To our knowledge, the approach described in [34] is one of the rst proposals to solve the feedback implosion problem over satellite networks without any secondary communication between the users. The disadvantage of this approach is that the feedback resolution requires multiple round trip times over the high latency satellite channel. In [35], the authors propose forming receiver clusters based on their spatial correlations, e.g. rain fall precipitation data, which is a prime factor that degrades service quality. Receivers in the same cluster use different return channels, while receivers in different clusters may use the same channel since there is a low probability of receivers located away from each other sending feedback simultane- 68 ously. We believe that the requirement for terrestrial return links, as well as the require- ment for secondary communication between the users, are restrictive, and in general contradicts with the reasons for deployment of satellite networks. The feedback im- plosion and the uplink bandwidth sharing problem should be studied without these as- sumptions. In this chapter, we present a feedback implosion suppression algorithm for ef cient feedback collection from a large set of users without relying on any collabora- tion among them, and on any secondary network infrastructure. We show that, in some of the cases, it is possible to reduce the volume of user feedback by exploiting the nature of the information and by considering that (i) the feedback may contain redundant in- formation (due to correlations among the users), and (ii) the protocol may need to track the behavior of only a subset of users, e.g. the group of users with worst case channel conditions. In the following sections, we rst look at the problem as a part of a protocol that collects periodic channel state information from users, in order to complement the policy behavior of the previous chapter. We later integrate the algorithm with the power allocation policy of the previous chapter and look at the performance results when the two cooperates. 3.2 CSI collection protocol In this chapter, we refer to the network architecture given in Fig. 3.1, and assume that a protocol performs between the satellite gateway (NOC) and a group of direct users that 69 are located inside the footprint of the satellite, in an attempt to collect periodic channel state information (CSI). Users submit their channel state information by accessing the uplink channel and sending a feedback message. In each spot-beam, the users access the uplink in multiple-frequency time-division multiple access (MF-TDMA) mode, where multiple frequency channels are allocated for uplink access, and the TDMA scheme is used within each frequency channel. The users acquire access by requesting a number of time-slots from the NOC, which invokes a resource allocation algorithm to share the uplink capacity (available time-slots) of the spot-beam among all active users. The result of the resource allocation is broadcast to all active users. We assume that a feedback message can be transmitted in a single uplink time-slot. First, we present the CSI collection protocol behavior that will be relevant to the operation of our feedback implosion suppression algorithm. The CSI of interest, in this case, is the signal attenuation level due to atmospheric and rain fading as measured at the input of the user receiver equipment. The goal of the protocol is to calculate the maximum signal attenuation level of each spot-beam location by collecting periodic reports on the attenuation levels of all active users inside coverage area. The maximum signal attenuation level is used as input to various fade mitigation algorithms in order to compensate for the user with worst channel conditions. It is assumed that the set of all active users are readily available at the NOC at all times, since this information is also required for login, bandwidth allocation, and pos- sibly billing purposes. Therefore, when a user terminal ui becomes active, the protocol 70 initializes and keeps a state variable ^si at the NOC for recording the attenuation level of that user. At this point the protocol has no information on the attenuation level of the user, therefore, the initial value of the variable is set to the expected attenuation level A. The expected attenuation level may be calculated through empirical data (off-line), or by modeling. The protocol updates the state variables for all active users, and calculates a new maximum for every spot-beam bj at every collection period by following a two-step process: 1. Let si(kT) denote the attenuation level sample measured by user ui at the start of collection period k at time t = kT, where T is the collection period. Active users send their measurements to the NOC, which collects and updates the correspond- ing state variable values: ^si[k] si(kT)8i2Uk; (3.1) whereUk is the set of active users at the time of collection period k. 2. LetUjk denote the set of active users inside the coverage area of spot-beam bj. At the NOC the maximum attenuation level for the spot-beam is calculated as sjmax[k] a= max i 2 Ujk f^si[k]g b= max i 2 Ujk fsi(kT)g; (3.2) for j = 1; 2; : : :; M, where M is the number of spot-beams, andUk = S 8j Ujk. The update operation in (3.1) requires all active users to acquire access to up- link time-slots to transmit their feedback messages. However, observe that, for every 71 spot-beam, feedback volume would be minimized if only the user with the maximum attenuation level responded at every collection period. We can consider two extreme scenarios for illustrative purposes: (i) all users communicate among each other through a secondary network (possibly a terrestrial connection) before deciding on whether to transmit a feedback message, and suppress the feedback messages of all but the user with the maximum; (ii) every user is assigned a separate uplink time-slot, over which the feedback message is transmitted to the satellite. The former scenario requires additional infrastructure and collaboration among users, which we believe is an overly restrictive requirement and is usually contradictory to the reasons for deployment of a satellite net- work in the rst place. The latter situation gives rise to the feedback implosion problem as well as the waste of uplink resources. In order to reduce the volume of feedback information that is transmitted through the network, our FIS algorithm modi es the behavior of the CIS collection protocol such that, with FIS in place, only a subset ^Uk Uk of active users report their measurements using at most Ck uplink time-slots for the collection period. Therefore, not all state variables are updated as in (3.1) at the end of collection period k: ^si[k] si(kT)8ui2 ^Uk; (3.3a) ^si[k] ^si[k 1]8ui =2 ^Uk: (3.3b) Consequently, the maximum attenuation levels calculated for each spot-beam using the state variables may not be equal to the maximum of the attenuation samples of active users measured at time t = kT, i.e equality (b) in (3.2) may not hold in general. 72 Therefore, we denote the maximum attenuation levels calculated when FIS algorithm is in place by ^sjmax[k] for j = 1; 2; : : :; M, where: ^sjmax[k] = max i2Ujk f^si[k]g; (3.4) andUk = S 8j Ujk. The goal of the FIS algorithm is, therefore, to limit the error between the actual maximum in (3.2) and the partial maximum in (3.4) by determining the users in set ^Uk and their assignments to a given number of uplink time-slots at every collection period. In the next section, we describe the FIS algorithm for determining set ^Uk. 3.3 FIS algorithm 3.3.1 Algorithm formulation In this section, we will describe the algorithm behavior for a single spot-beam. We assume that identical copies of the algorithm run for each spot-beam in order to suppress the feedback information from users covered by them. Let Cjk be the maximum number of time-slots that can be allocated to transmission of feedback messages for collection period k in spot-beam bj. The system may reserve a xed number of time-slots for feedback transmission, or the value of Cjk can be determined by the remaining time-slots after the user requests for data transmissions are accommodated. The FIS algorithm selects users and assigns them to one of the Cjk available uplink time-slots by solving a multiple subset sum problem (MSSP) [36]. Multiple subset sum problem is a variant 73 of the bin packing problem in which the number of bins is given. Mathematically, the MSSP can be described as follows: De nition 1 Given a set fuigNi=1 of items, each item ui having a positive weight wi, and a setfhlgCl=1 of identical bins with positive capacity H, what is the assignment that maximizes: max CX l=1 NX i=1 wixil (3.5a) subject to NX i=1 wixil H; 8l; (3.5b) CX l=1 xil 1; 8i; (3.5c) xil 2f0; 1g; 8i; l: (3.5d) Without loss of generality, we assume that N C, otherwise the problem is trivially solved. At the start of the CSI collection period k, using the set of active users inUjk, and the state variables f^si[k 1]gi 2 Uj k , the FIS protocol solves an instance of the MSSP where, N =jUjkj; cardinality of the setUjk; (3.6a) C = Cjk; number of available time-slots; (3.6b) wi = minf^si[k 1]; Amaxg; 8i2Ujk; (3.6c) H = Amax; (3.6d) 74 where Amax is the maximum attenuation level that can be compensated by the fade countermeasures implemented by the system. Equation (3.6c) allows all users with a reported attenuation level larger than Amax be treated as equals since the system does not have the means to compensate for their attenuation level above this limit. Let xk be the solution vector that represents the assignment of items to bins. The assignment of items to bins represents the assignment of users to uplink time-slots, such that xkil = 1 if user ui is selected and assigned to time-slot l for 8i 2Ujk, and l = 1; 2; : : :; Cjk , else xkil = 0. The NOC broadcasts the solution vector over the network as a part of the existing on-demand bandwidth allocation procedure and reserves the necessary uplink time-slots for the collection period. The MSSP formulation provides a procedure for selecting and assigning users to available uplink time-slots, however, it may assign more than one user to a particular time-slot. Therefore, the FIS algorithm must have a collision avoidance strategy to limit the number of collisions. In order to avoid collisions, a user ui chooses to transmit its feedback message during its assigned time-slot with probability pi(k). The procedure for choosing collision avoidance probability values is discussed in the subsequent sections. The set ^Ujk is constructed as: ^Uj k =fui : x k il = 1\1(Ei)g; (3.7) where 1(:) is the indicator function, Ei is the event that ui transmits in period k, such that E(1(Ei)) = pi(k)8i. 75 In the following section, we discuss the important properties of this algorithm formulation that enable ef cient feedback suppression in the context of CSI collection. 3.3.2 Algorithm properties MSSP is a NP-hard problem, and we assume that best- t-decreasing (BFD) approxi- mation is implemented for the solution [36], not only because it is one of the fastest heuristics, but also it has desirable properties in achieving the goals of the FIS algo- rithm. Property 1 BFD algorithm starts the selection and allocation of the items rst from the ones with the largest weights. The algorithm always selects the rst Cjk largest items. The remaining items are selected only if there is room. Property 1 states that the rst Cjk users with the highest reported attenuation levels are always selected and assigned to a time-slot in the current collection period. This approach gives priority to users that have reported a high attenuation level in the past collection periods, over the users that reported a lower attenuation level. The remaining users face the possibility of suppression depending on their attenuation levels and the number of available time-slots. Assuming channel state varies slowly, this property effectively reduces the size of the user set that will be selected in the next period. Property 2 Items with larger weights, if selected, are more likely to occupy a bin that has few other items since they ll most of the capacity of a bin. 76 Property 2 decreases the probability that a user with a high reported attenuation level will be involved in a collision in the current collection period, since it is more likely to be assigned to a time-slot with few other users. Property 1 and Property 2 together achieves the goal of reducing the feedback volume by restricting the transmissions to a group of users that are expected to attain the maximum attenuation level. Property 3 Items with smaller weights are only selected if there is available bin space after placement of items with larger weights. Finally, Property 3 states that users with lower reported attenuation levels are sup- pressed by the selection process. The suppression becomes more severe as the number of available uplink time-slots decreases, since the MSSP algorithm runs with fewer bins. It may be argued that selecting the largest Cjk items and allocating them into bins one-by- one for the collection period k would have been a better strategy, since that would have avoided collisions between users. However, note that the allocation decision at the NOC is based solely on the last successfully reported attenuation level of each user, rather than the current value measured by the user. Such a strategy would cause a user with a previously low attenuation level to remain suppressed for a long time, even if it currently measures a high attenuation level, and would consequently reduce the robustness of FIS algorithm against the changes in the channel conditions. This observation also is the basis for our collision avoidance strategy which we describe in the next section. 77 3.3.3 Collision avoidance strategy At every collection period, an active user only knows its channel assignment for that period and the value of its current attenuation level measurement. We assume that users can also listen to their own transmissions and detect collisions. Therefore, all users keep a record of the value of the last attenuation sample they successfully transmitted to the NOC. This value is equal to the value of the state variable kept at the NOC for the user, which the NOC always uses in calculating the maximum as well as in determining the channel assignment vector for the FIS algorithm. The transmission probability pi(k) of the user ui should be proportional to the discrepancy between its current measured level si(kT) and the last reported level, ^si[k 1], since the error would not only affect the selection and suppression criterion in the subsequent collection periods, but more impor- tantly would increase the error between the true maximum and the calculated maximum. Therefore, a user assigned to an uplink time-slot chooses to transmit it feedback with probability proportional to the square of the difference between the current attenuation level and the last successfully reported value. The user behaves more aggressively in transmitting its feedback message, if there is a signi cant change in its condition. How- ever, in order to put a cap on the aggressiveness of a user, the functional relationship between the square of the difference and probability of transmission should saturate as the difference goes to in nity. We choose the family of curves of the form: f(y; z) = 2(1 + e y2=z) 1:0; (3.8) 78 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 50 0.2 0.4 0.6 0.8 1 Di(k) p i (k) Figure 3.2: Probability of transmission as a function of . where, z determines how sharp the curve saturates. Let i(k) be de ned as i(k) =j^si[k 1] si(kT)j (3.9) for user ui at collection period k. Then, the probability of transmission for the user in this interval is given by pi(k) = 2(1 + e i(k)2=z) 1:0; (3.10) for a given z. In Fig. 3.2, we plot this curve for z = 0:7. 3.4 Performance analysis 3.4.1 Analysis results In this section, we rst look at the performance of the FIS algorithm for a xed set of U = 200 active users inside one spot-beam coverage area over a simulated time of 1280 minutes. Therefore, in the remainder of this section, we drop the index for spot- beams. This test duration corresponds to a total of K = 1200 CSI collection periods 79 with an interval of T = 64 seconds, which is the granuality of our channel simulator (Section 2.5.2). The test is repeated 100 times, and average results are reported. During the simulation, a separate instance of the channel simulator is run for each user, modeling its attenuation level. The attenuation time series generated for a user is independent from other users. In general, this assumption may not always be valid, since attenuation due to rain typically occurs in cells of certain diameter that may include more than one user. In this case, the users that are located close to each other geographically may have correlated attenuation levels. However, a study by Fukuchi [18] found that this correlation decreases rapidly with increasing distance, and that instantaneous rainfall rates at two locations more than about 100 km apart can be regarded as independent. Also, we may argue that such a correlation would only improve the performance of our algorithm by decreasing the number of users with different attenuation measurements. In Fig. 3.3, we plot a realization of the time series of maximum channel attenua- tion calculated from the user samples (dashed-line), smax[k] = max i2U fsi(kT)g; k = 1; 2; : : :; K; (3.11) versus the maximum channel attenuation level calculated from state variables at the NOC (solid-line), ^smax[k] = max i2U f^si[k]g; k = 1; 2; : : :; K; (3.12) for C = 2; 10; 20 uplink time-slots. We observe that the time-series are in close agree- ment for C = 20 and C = 10, but the discrepancy becomes more signi cant for C = 2. We calculate the average absolute error between the two curves as a function of number 80 0 200 400 600 800 1000 12000 15 30 45 20 Time?slots 0 200 400 600 800 1000 12000 15 30 45 10 Time?slots 0 200 400 600 800 1000 12000 15 30 45 Time index (each tick = 64 seconds) 2 Time?slots Maximum attenuation (dB) Figure 3.3: Time-series plot of actual channel attenuation level (dashed-line) versus the level calculated at the NOC (solid-line) for a set of 200 users. of available uplink time-slots: error(C) = 11200 1200X k=1 jsCmax[k] ^sCmax[k]j; (3.13) which we tabulate in Table 3.1. C 30 20 10 2 1 Error (dB) 0.3973 0.7117 1.4855 3.7733 4.5522 Table 3.1: Average absolute error. In Fig. 3.4(a), we plot the fraction of the total users suppressed by the FIS algo- rithm as a function of the number of available uplink time-slots. A user?s feedback may 81 be suppressed in one of the two ways: (i) it is not selected by the MSSP solution, or (ii) its feedback experiences a collision and is not reported successfully to the NOC. Figure 3.4(a) shows the contribution of the two cases in each instance. We observe that, 95 99% of users are suppressed on the average by the FIS algorithm. Considering that the algorithm successfully keeps track of the maximum level for up to 10 time-slots (cor- responds to 5% of total user population), this is a promising result showing that the algo- rithm correctly identi es the group of users that attain the maximum attenuation level. The type of suppression changes as the number of available uplink time-slots decreases. More users are suppressed through the selection process than channel collisions. When there are available time-slots, MSSP formulation selects and assigns more users. This leads to more collisions on the average per user in the assigned time-slots, however, also gives the opportunity to sample a larger user space if some feedback successfully reaches to the NOC. When there are very few time-slots, MSSP formulation suppresses most of the users. This leads to fewer collisions per user, however, increases the error if the wrong subset of users are assigned to the time-slots (compare to Table 3.1). In Fig. 3.4(b), we look at the time-slot usage pro le as a function of available uplink time-slots. We see that a time-slot is utilized successfully 30 35% of the time. This percentage remains relatively constant independent of the ratio of the number of available time-slots to the number of users. In order to assess the performance of our algorithm under different user group sizes, we plot, in Fig. 3.5, the average error in the calculated attenuation level versus the 82 30 20 10 2 10 20 40 60 80 100 Suppressed users (%) Number of available uplink time?slots (200 users) By Collision By Selection 30 20 10 2 10 10 20 30 40 50 60 Channel usage (%) Number of available uplink time?slots (200 users) Collision Success Idle Figure 3.4: (a) Fraction of the users suppressed by the FIS algorithm as a function of the number of available uplink time-slots (200 users). (b) Channel usage pro le as a function of the number of available uplink time-slots (200 users). 83 100 101 102 0 2 4 6 8 Number of available uplink time?slots Average error (dB) 100 users 200 users 500 users Figure 3.5: Average error versus number of available uplink time-slots as a function of the number of active users. number of available uplink time-slots for a range of user groups. We observe that for a given number of time-slots, the average error of FIS algorithm increases as the number of users increase. This result is expected since the algorithm is forced to select and allocate users from a larger set to a xed number of time-slots. Therefore, more users are suppressed by the algorithm, resulting in less accurate calculation of the maximum attenuation level. However, more importantly, if the ratio of available time-slots to the number of users is kept constant, then we observe that the algorithm performs equally well for all group sizes. Although average error in the calculated attenuation level is an indicator of the performance of the FIS algorithm, from a system provider?s or user?s perspective, a more important performance metric would be the effect of this error as an input to a fade compensation algorithm. In order to assess this performance, we look at the use of the attenuation level as an input to a simple downlink power control scheme. We 84 100 20 15 10 5 10 5 10 15 20 Number of available uplink time?slots (100 users) Fraction of total time (%) Maximum Average Minimum Figure 3.6: Percentage of total time BER target is not met by a user as a function of number of available uplink time-slots (100 users). assume that the system has a 10dB link-budget power margin that is used to compensate for the signal attenuation due to atmospheric and rain fading. The system allocates this power margin based on the calculated maximum attenuation in order to meet a target bit-error-rate (BER). With no FIS in place, the system will not be able to meet this BER target, only when the maximum attenuation level is more than the 10dB power margin. However, with FIS in place, the error in calculating the maximum attenuation level may cause the system to underestimate the actual attenuation level. This would result in additional time instances when the BER target is not met by some users. On the other hand, over-compensation would result in signal enhancement, leading to an increased risk of co- and cross-channel interference. In Figures 3.6 to 3.8, we look at the maximum, average and minimum percentage of time a user will not meet the BER target as a function of the number of available uplink time-slots for user groups of 100; 200 and 500. 85 200 30 20 10 2 10 4 8 12 16 20 24 Number of available uplink time?slots (200 users) Fraction of total time (%) Maximum Average Minimum Figure 3.7: Percentage of total time BER target is not met by a user as a function of number of available uplink time-slots (200 users). 500 75 50 25 5 10 5 10 15 20 25 Number of available uplink time?slots (500 users) Fraction of total time (%) Maximum Average Minimum Figure 3.8: Percentage of total time BER target is not met by a user as a function of number of available uplink time-slots (500 users) 86 We observe that, average performance degradation experienced by a user remains acceptable even if the number of available time-slots is as low as 5% of the total user population. 3.5 Multicast-aware power allocation with FIS In this section, we re-visit the multicast-aware power allocation policy that we have pre- sented in the previous chapter. In the previous chapter, we assumed that the algorithm had perfect knowledge of the channel states for every spot-beam at the time of the opti- mization. In this section, we assume that CSI is collected from the active users inside the coverage area of every spot-beam, and the channel state of the spot-beam is determined by the user with the worst channel condition. In order to minimize the total number of uplink channels required for information collection in every spot-beam, we use the FIS algorithm and compare the results to the case where we had the perfect knowledge of the channel states. We keep the same test setup as in the previous chapter. We create Lu unicast and Lm multicast connections between the NOC and spot-beam locations using the connec- tion probability function given in Fig. 2.9. Once this process is completed, total number of unicast and multicast users in each spot-beam location is known. Instead of running a separate instance of our channel simulator per spot-beam, this time we run a separate instance of the channel simulator for every user. Since the time resolution of the chan- nel simulator is T = 64 seconds, NOC updates the channel state of each spot-beam by 87 collecting CSI from all the active users inside that spot-beam location every T seconds. The test is performed for a simulated time of 720 minutes, where the channel states are updated for a total of K = 675 times. Each test is repeated for 100 different session con gurations to achieve the statistical results. We use logarithmic weight allocation when running the power-allocation policy. We look at three different scenarios for CSI collection: Perfect CSI case: Information is collected from every active user inside the spot- beam coverage area using separate return channels for every user. The channel state for spot-beam bj at the end of collection period k, where there arejUjkjactive users, is given by sjmax[k] = max i2Ujk fsi(kT)g; (3.14) for j = 1; 2; : : :; M, where M is the number of spot-beams. In this scenario, the number of time-slots used for each round of information collection is equal to the number of active users, i.e. Cjk =jUjkj; 8j. Binpacking case: Binpacking formulation is an extension of MSSP formulation, where the number of bins is not given, but determined by the minimum number re- quired to t all items. In our problem setting, this translates into having a variable number of allocated time-slots in each collection period and for every spot-beam, since the number of users and the channel state samples of these users vary over time. In binpacking case, at each collection time, all users are assigned to a time- slot, and potentially the number of allocated slots may be equal to the number of 88 active users. However, due to the possibility of collisions, the set of users that successfully report their CSI is a subset of the active user set. The channel state for spot-beam bj at the end of collection period k is given by ^sjmax[k] = max i 2 Ujk f^si[k]g; (3.15) for j = 1; 2; : : :; M. The number of time-slots used in this case is always less than or equal to the number of active users, i.e. Cjk jUjkj; 8j. Subset Sum case: This is the nal variation, where we use the MSSP formulation, and the number of channels allocated is given and xed through out the tests. In this scenario, at each collection time, not all users are allocated a channel. Moreover, of the users that are allocated a channel, not all successfully transmit their CSI information due to collisions. Hence, the channel state for spot-beam bj at the end of collection period k is given by ^sjmax[k] = max i 2 Ujk f^si[k]g; (3.16) for j = 1; 2; : : :; M. The number of time-slots used in this case is xed, i.e. Cjk = C; 8j. In the next two sections, we look at the performance of BAS-I and BAS-II policies for each of the above scenarios. 89 3.5.1 Performance of BAS-I policy with FIS In this section, we compare the performance of BAS-I policy under different feedback implosion suppression scenarios. In order to assess the changes in performance of our policy, we rst have to compare the extend of suppression introduced by each FIS sce- nario, and the corresponding time-slot usage pro le. In Fig. 3.9, we look at the time-slot usage pro le under binpacking scenario, when there are Lu = 350 active unicast connec- tions and Lm = 5 to 30 active multicast groups. Under binpacking scenario, the number of slots used per collection period and per spot-beam varies over time. In Fig. 3.9 we plot three metrics: (i) the maximum of the average time-slot usage over all spot-beams, given by Cmax = max j 1 K KX k=1 Cjk; (3.17) (ii) time-slot usage averaged over all spot-beams, given by Cavg = 1M MX j=1 1 K KX k=1 Cjk; (3.18) and (iii) the average suppression ef ciency, which is the ratio of average number of time-slots used to average number of active users. We observe that, the FIS algorithm achieves a suppression ratio of 70% 74%, but maximum number of time-slots used by a spot-beam may go up to 3 times higher than the average time-slot usage. In Fig. 3.10, we look at the time-slot usage pro le under the subset sum scenario. For subset sum scenario, we have to specify the maximum number of bins available to the FIS algorithm. In order to test the performance to the limit, under this scenario, we set the maximum 90 Figure 3.9: Time-slot usage pro le and suppression ef ciency of spot-beams as a func- tion of active multicast groups when using binpacking formulation. number of time-slots available to every spot-beam to be equal to the average number of channels used for the binpacking case, rounded off to the nearest integer, i.e. set Cjk = Cavg 8j; k. We observe that, average number of channels used by a spot-beam is still lower than the maximum we set, since for some very lightly loaded spot-beams not all bins are required in the solution of the subset sum problem. The suppression ratio is forced to be higher, since maximum number of channels have a tight cap, going up to a maximum of 78%. Under both binpacking and subset sum scenarios, the FIS algorithm achieves very good suppression ratios. However, it is important to test how the performance of the power allocation policy, which relies on the channel state information obtained by the FIS algorithm, is affected compared to the perfect CSI case. The change in performance 91 Figure 3.10: Time-slot usage pro le and suppression ef ciency of spot-beams as a func- tion of active multicast groups when using subset sum formulation. is a consequence of the fact that with partial CSI, the power levels calculated by the policy may over- or under-estimate the actual power requirements of the spot-beams. As a result of this, the rates allocated to particular ows may not re ect the actual supportable rates. In Fig. 3.11, we look at the average rate change in the sustainable session rates of unicast ows for each of the feedback collection scenarios. We observe that the perfor- mance under binpacking scenario is on a par with the perfect CSI scenario. However, the performance under subset sum scenario remains sub par for all cases. Similar results are observed for multicast ows as well. These results are attributed to the fact that un- der binpacking scenario, the FIS algorithm has access to as many time-slots as needed under time-varying conditions. Therefore, binpacking scenario closely follows the per- 92 Figure 3.11: Average rate change in the sustainable session rates of unicast ows av- eraged over all active unicast ows under the BAS-I policy for each of the feedback collection scenarios. Figure 3.12: Average rate change in the sustainable session rates of multicast ows averaged over all active multicast ows under the BAS-I policy for each of the feedback collection scenarios. 93 Figure 3.13: Percent of total test time BAS-I session rates of unicast ows are equal to or better than EAS session rates averaged over all active unicast ows for each of the feedback collection scenarios. formance of perfect CSI scenario. Under subset sum scenario there is a tight cap on the maximum number of available time-slots. This in exibility under changing propagation conditions causes degradation in performance. However, improvement in the average session rates of unicast and multicast ows remains higher than 15% and 50%, respec- tively even though the average number of allocated time-slots is in the range of 22% to 28% of the average number of users, which shows that FIS algorithm works well in conjunction with our power-allocation policy. A similar performance trend is observed when we look at the fraction of time session rates of unicast and multicast ows remain over the EAS session rates under the BAS-I policy (Figures 3.13 and 3.14). Finally, we look at the change in the value of cost function of the optimization for 94 Figure 3.14: Percent of total test time BAS-I session rates of multicast ows are equal to or better than EAS session rates averaged over all active multicast ows for each of the feedback collection scenarios. each of the feedback collection scenarios. We observe that the optimization performs equally well in minimizing the cost function, reducing its value to 90 95% of the starting value for all scenarios. Therefore, the performance degradation we see is not a result of the performance of the optimization, but because of the discrepancy between the attenuation level values the algorithm uses versus the ones that sessions actually experience. In the next section, we look at the performance of BAS-II policy under different feedback collection scenarios. 95 Figure 3.15: Percent change in the value of the cost function after optimization with respect to the starting value under BAS-I policy for each of the feedback collection scenarios. 3.5.2 Performance of BAS-II policy with FIS Figures 3.16 to 3.19 show similar performance trends in terms of time-slot usage, sup- pression ef ciency, and average rate change in the sustainable session rates of unicast and multicast ows. Binpacking case performs on a par level with perfect CSI case, while subset sum case causes performance degradation in the average rate increase that the ows experience as a result of the optimization. A more important performance change in the results of BAS-II policy comes in the fraction of time ows attain rates that are higher than EAS rates after the optimization. BAS-II policy guarantees that the session rates of all ows remain at a rate higher than the EAS session rates at all time under perfect CSI. However, in Figures 3.20 and 3.21, we observe that BAS-II policy no 96 Figure 3.16: Time-slot usage pro le and suppression ef ciency of spot-beams as a func- tion of active multicast groups when using binpacking formulation. longer has this guarantee due to the discrepancy between the attenuation level values. Finally, we look at the change in the value of cost function of the optimization for each of the feedback collection scenarios. We observe that under BAS-II policy, optimization reduces the value of the cost function to 40 65% of the start value for all scenarios. We observe that this is considerably less than the values attained under BAS-I policy. This result, however, is a direct consequence of the fact that BAS-II policy works with a much smaller search space due to the restrictions imposed by the minimum power requirements, as discussed earlier in the previous chapter. 97 Figure 3.17: Time-slot usage pro le and suppression ef ciency of spot-beams as a func- tion of active multicast groups when using subset sum formulation. Figure 3.18: Average rate change in the sustainable session rates of unicast ows av- eraged over all active unicast ows under the BAS-II policy for each of the feedback collection scenarios. 98 Figure 3.19: Average rate change in the sustainable session rates of multicast ows averaged over all active multicast ows under the BAS-II policy for each of the feedback collection scenarios. Figure 3.20: Percent of total test time BAS-II session rates of unicast ows are equal to or better than EAS session rates averaged over all active unicast ows for each of the feedback collection scenarios. 99 Figure 3.21: Percent of total test time BAS-II session rates of multicast ows are equal to or better than EAS session rates averaged over all active multicast ows for each of the feedback collection scenarios. Figure 3.22: Percent change in the value of the cost function after optimization with respect to the starting value under BAS-II policy for each of the feedback collection scenarios. 100 3.6 Summary In this chapter, we presented a feedback implosion suppression algorithm that uses a multiple subset sum (MSS) formulation in order to select and assign users to a limited number available uplink channels (time-slots). MSS formulation is based on the obser- vation that for most of the multicast scenarios where user feedback is used to probe the condition of the members of the multicast group, it is suf cient to only track the behavior of only a certain subset of users (e.g. subset of users with the worst channel conditions). In this case, it is possible to prioritize the users based on the importance of their feed- back to the task at hand, and allocate them accordingly. However, in most of the cases, the priority level of a user is not known to or can not be communicated to other users to help in the allocation process. Moreover, the decision mechanism may have partial or outdated information on the group. Therefore, determining the right subset of users to collect feedback is a challenging task. Our formulation successfully achieves this task, and successfully tracks the user(s) with the highest channel attenuation, when the number of available uplink time-slots is larger than 5% of the multicast group size. In the MSS formulation, the number of available uplink slots is given and xed. However, it may not be possible to know, in advance, the required number of uplink time-slots for acceptable performance. There- fore, in this chapter, we also investigated the extension of the algorithm to binpacking formulation, where the number of uplink time-slots is not xed. The algorithm uses as many uplink time-slots as needed in order to allocate all active users according to the 101 selection mechanism. The binpacking formulation outperforms the MSS formulation due to this exibility. However, the number of uplink time-slots used by the binpacking formulation can potentially be as large as the number of active users, in which case the suppression ratio goes to zero. On the other hand, binpacking formulation can be used as a guideline to set the maximum number of available time-slots in MSS formulation. Fi- nally, in this chapter, we integrated our feedback implosion suppression algorithm to the power allocation policy of the previous chapter. The channel state information required by the power allocation policy is collected from the users through the feedback implo- sion algorithm. We showed that it is possible to reach suppression ratios of 70 78% while maintaining the initial performance of the power allocation policy. 102 Chapter 4 Integrated FEC Coding for Reliable Multicast Transport 4.1 Introduction In the previous chapters, we have discussed the advantages of supporting multicast ser- vices over satellite networks, and presented two features that enable multicast-aware power allocation and ef cient feedback collection. These features provide support for distribution of multicast content to multiple users. In addition, some of the multicast applications in the Internet, such as distributed computing, software updates, distance- learning, and telemedicine, may also require or bene t from reliable multicast commu- nication. Therefore, in this chapter, we focus on some of the issues related to the reliable delivery of multicast content over satellite networks. Reliable delivery requires that all data segments transmitted over the network are received correctly by all receivers. In order to achieve this goal, missing or cor- rupted data segments must be detected and recovered. In traditional schemes, such as the automatic-repeat-request (ARQ), receivers detect missing data segments and auto- matically request for retransmissions by transmitting a feedback message of one of the following forms to the sender: Positive acknowledgments (ACK): Receivers return ACK packets to the sender, 103 indicating the data segments that have been received correctly. Negative acknowledgments (NACK): Receivers return NACK packets to the sender, indicating only the data segments that are missing. A hybrid approach: Receivers use both ACK(s) and NACK(s). In these schemes, a missing ACK or a received NACK for a particular data segment acts as a trigger, in response to which the sender initiates retransmission of the missing segment. However, a recovery mechanism that is based solely on ARQ does not perform well in case of multicast communication. ACK-based loss noti cation causes feedback implosion, since every member of the multicast group has to separately acknowledge the successful receipt of every data segment. Additionally, the sender is required to keep track of the size, and the current state of the members of the multicast group, in order to identify the last data segment correctly received by all. Both problems negatively affect the ef ciency and scalability of the protocol. NACK-based loss noti cation alleviates some of these problems. The performance comparison study presented in [37] con rms that NACK-based multicast transport protocols deliver better performance than their ACK-based counterparts in wireline terrestrial networks. In NACK-based feedback, receivers detect missing packets by checking for gaps in the packet sequence numbers and report missing segments to the sender. The sender neither needs to know the size of the receiver group, nor keeps track of the current state of every receiver in its group. Also, the number of NACK packets is expected to be less than that of ACK packets at low error rates. A disadvantage, however, is that it is more dif cult for the sender 104 to know when it can free the transmission buffers, since not receiving a NACK may either indicate successful transmission of the corresponding data segment, or loss of the noti cation packet itself. These performance related issues are only aggravated over satellite networks. For a GEO satellite, the propagation delay between the user terminals and the satellite is about 125ms, which adds up to a round-trip-time (RTT) of about 500ms for a two-way system over the satellite segment. Therefore, ARQ-based recovery of individual data segments increases transmission delay signi cantly. In addition, retransmission of indi- vidual data segments, in response to individual receiver requests, does not make good use of the broadcast capabilities of the satellite channel, because retransmitted segments only bene t one receiver while discarded by many others. Moreover, because of the large bandwidth-delay product typical to such networks (e.g. 20Mbps 500ms for a GEO satellite operating at K/Ka-band frequency), the transport protocol would put a large amount of data onto the network before getting responses for old segments. Therefore, the number of outstanding data segments that have not yet been acknowledged would be large, forcing the protocol to keep a large amount of data in the transmission buffers. Fi- nally, deep channel fading due to atmospheric effects may lead to bursty periods where several data segments are lost back to back. Recovery of these data segments over the high latency network through the repeat-request process would be inef cient, and may trigger feedback implosion even in the NACK-based case. Although it is not possible to completely abandon an ARQ-based scheme, and still 105 provide full reliability, we conclude that in order to support reliable multicast services over a satellite network, the transport protocol should act proactively to protect trans- mitted data against losses, and consequently, to minimize the need for retransmissions. Forward error correction (FEC) coding is a well-known technique for protecting data against losses and corruption [38 40]. FEC coding can be applied against bit-level cor- ruption, in which case the FEC encoder generates (n k) parity symbols (e.g. bytes) for a k-symbol packet. Such codes are capable of recovering the k-symbol packet if the number of corrupted symbols are less than or equal to t = (n k)=2. This, in ef- fect, decreases the effective loss rate of the channel and causes the upper layers to see a more reliable network [41]. However, unrecoverable packets are still retransmitted from the source, and different packets are retransmitted in response to requests of different receivers. An alternative application of FEC codes to multicast protocols is as an era- sure code at the packet level. [40, 42 44]. In this case, lower network layers detect and discard corrupted packets (possibly by application of a separate FEC coding), and the erasure code works at the higher network layers (e.g. transport layer) to recover missing packets. The FEC encoder generates n encoding packets from k original data packets, and the original k data packets can be recovered as long as k out of the transmitted n encoding packets are received correctly. Use of FEC coding at the packet level offers some solution to a number of problems. One immediate bene t of packet level FEC coding is reducing the number of missing data packets. This minimizes the number of feedback messages (e.g. NACK), 106 as well as the need for retransmissions, and thereby improves ef ciency and scalabil- ity. FEC coding has an additional bene t in case of satellite multicast services. Unlike unicast communication, where the retransmission of a data packet exclusively bene ts the receiver that has made the request, in multicast, the protocol has the option to ei- ther unicast or multicast the retransmitted packet. Multicasting of retransmitted packets would bene t multiple receivers in case of correlated loss. However, it may as well degrade channel utilization in case of uncorrelated loss. Because of the broadcast na- ture of the satellite channel, however, all packets can be received by all members of the multicast group. Therefore, transmission of encoding packets signi cantly improves the channel utilization, because FEC encoding packets can be useful to all receivers in the recovery process of an encoding block, even when different encoding packets are received at different receivers. Also, the protocol becomes more scalable in the number of receivers. The protocol does not need to know which packets have been lost by the receivers of the session per encoding block, but only the maximum number of packets lost by any receiver of the session. Therefore, the feedback from a single receiver has been reduced [42, 45 47]. Many of the recent reliable multicast transport protocols integrate some form of packet level FEC coding [48 50] in their design. However, implementation of packet level FEC coding is dif cult for typical data packet sizes. Also, number of encoding packets that can be transmitted against packet losses is limited to the block size of the code. Therefore, there has been an effort in the research community that is initiated 107 primarily by the IETF working groups, to de ne schemes that could work with large packet sizes and over large block sizes [43, 44]. As an example, in [51] authors propose a scheme using Tornado codes, which are capable of working over large block sizes. In this chapter, we investigate the potential bene ts of using packet level FEC cod- ing for reliable multicast delivery over a satellite-based communication system. We con- sider application of a special form of packet level FEC codes, namely the LT codes [52, 53], which are capable of generating a large number of encoding packets for the same group of input packets. We discuss the possibility of adjusting the number of encoding packets adaptively in response to changing channel conditions and receiver feedback. In the next section, we start by describing our target network scenario, and discuss where the application of packet level FEC would t within the network layers. 4.2 Network scenario We assume that the multicast content (software, webpage, le) is located at a server on an IP based terrestrial network. This content is to be distributed reliably to multiple user locations, which are within the coverage area of the satellite network. In this scenario, users that are equipped with two-way direct communication terminals access the ter- restrial network through a gateway node we refer to as the Network Operations Center (NOC). Therefore, the NOC is responsible for fetching the content from the server, and then distributing it over the satellite network (Fig. 4.1). We assume that the session is established using the idea of connection split- 108 Figure 4.1: Satellite communication system architecture. ting [54, 55] that has recently been of much interest to the research community. In this scenario, the session is split into three components: (a) a TCP/IP connection is established between the server and the satellite gateway, (b) over the satellite portion of the network, a satellite reliable multicast transport protocol is run, and (c) between the user terminal and the user machines another TCP/IP connection is established. We assume that data reliability is ensured natively by the TCP protocol in sub-connections (a) and (c). Therefore, we are primarily interested in the behavior and performance of the transport protocol over the satellite portion of the network. Our decision to go with the idea of connection splitting in this type network scenario is motivated by several observations. The rst one stems from the particular structure of the network topology where the connections from the server to the gateway, and from the user terminal to the user machines are essentially point-to-point. Inside the satellite core, on the other hand, 109 the star topology allows satellite to push content in single hop to all users. Secondly, the transmission characteristics, such as the transmission delay and error patterns, over the satellite portion are widely different than those that are over the terrestrial network. Finally, satellite service providers are more likely to favor this setup compared to an end-to-end solution between the server and user machines, since the former allows them to have total control over the traf c ow inside their network for activities ranging from resource allocation, and security to billing. Under this setup, we assume that Digital Video Broadcasting (DVB) [56] standard for data broadcasting is implemented for delivering data packets inside the satellite core network, although, the discussion in the remainder of this chapter does not depend on the behavior of a particular packet delivery scheme. DVB standard for data broadcast- ing allows encapsulation of IP datagrams into MPEG-2 Transport Stream Packets using the Multiple Protocol Encapsulation (MPE) standard [56]. The incoming stream of IP datagrams are segmented into 188-Bytes (4 Bytes packet header and 184 Bytes pay- load) transport packets at the satellite gateway. The DVB channel encoder encodes each packet, rst using a shortened (204,188) RS code (adds 16 parity bytes to each transport packet), and then, passing the packet bit stream through an interleaver. The interleaved symbols are encoded by a rate punctured convolutional encoder capable of supporting variable rates of 1/2, 2/3, 3/4, 5/6, and 7/8, and transmitted through the physical channel. In the rest of this chapter, we assume that DVB channel coding is capable of de- tecting all corrupted packets and discarding them. Therefore, only correctly received 110 Figure 4.2: Proposed breakup of the communication session. packets are forwarded to the MPEG transport layer, and missing packets have to be recovered at this point. Reliability at the MPEG transport layer is assisted by the appli- cation of the packet level FEC coding as an erasure code (Fig. 4.2). In the next section, we give an overview of the structure of the class of packet level codes we consider for application under this network scenario, and de ne how coding is integrated into the transmission of data packets. 4.3 Packet level FEC coding for reliable multicast communication Application of packet level FEC coding using some of the traditional block codes, such as Reed-Solomon codes, are limited because of the dif culty in implementing them for large symbol sizes, and the restrictions on the encoding block sizes. In order to 111 be applicable to our scenario, the FEC coding should be able to accept packet sizes of several hundred bytes as input symbols. Additionally, the code should be able to generate a large number of encoding packets, preferably, on demand, to overcome bursty packet losses. In order to achieve some of these goals, we make use of a special class of FEC codes, referred to as the LT codes [52, 53] in the literature. Unlike block codes, there is no predetermined number of encoding symbols that can be generated for LT codes. Instead, the LT encoder can generate as few or as many unique encoding symbols as required on demand. Moreover the input symbol sizes for the LT encoder can be arbi- trary. The construction of the LT codes allows end-users to recover an original batch of k transport packets, if they manage to accumulate a slightly larger set of K = (1+ ) k of the encoding packets that are generated from the same input packet batch. Addition- ally, the number of encoding packets that can be generated from the same input packet batch is typically much larger than the size of the batch. The bene t of this construction is two-fold. First, it allows the satellite gateway to transmit additional encoding packets as long as there are users that have not yet accumulated enough packets from the batch. Secondly, it simpli es the user requests for additional packets, since now only infor- mation that has to be forwarded to the satellite gateway is comprised of the number of additional encoding packets (from the same batch) that is required by each receiver until all receivers complete the reception. This construction also makes very good use of the broadcast nature of the satellite channel since every transmitted encoding packet bene- 112 ts all the users equally. In the next section, we provide an overview of the construction of LT codes. 4.3.1 Construction of LT codes The process of generating an encoding packet from a batch of input packets is concep- tually easy to describe [53]. We assume that data to be distributed can be organized into B batches of k input packets. Let l be the size of an input packet. For an input batch, an encoding packet of size l is generated by the following procedure (Fig. 4.3): 1. From a degree distribution (a good degree distribution is the key to the operation of LT codes and it will be discussed in more detail), randomly choose the degree d of the encoding packet. 2. Choose, uniformly at random d distinct input packets as neighbors of the encoding packet. 3. The value of the encoding packet is the bitwise exclusive-or (XOR) of the d neigh- bors (d input packets). When using the encoding packets to recover the original input packets, the decoder needs to know the degree and the set of the neighbors of each encoding packet. This in- formation can be communicated to the decoder in many different ways but one ef cient example is to use a key to seed the random number generators that generates the degree value and the neighbor list. A good candidate for the key is the sequence number in the 113 header of each encoding packet. Then, the sequence number of each encoding packet can be used to obtain its degree and neighbor information. The decoder uses the following rule to recover input packets. If there is at least one encoding packet that has exactly one neighbor (degree d = 1), then the neighbor (corre- sponding input packet) can be recovered immediately since it is the copy of the encoding packet. The recovered input packet is XOR?ed into any remaining encoding packets that also have that input packet as a neighbor. Recovered input packet is removed from the neighbors of these encoding packets and the degree of each such encoding packet is decreased by one to re ect this removal. The decoding process continues at each step by processing encoding packets with degree one, and completes successfully if all input packets are recovered in this manner. Therefore, the initial degree distribution has to be such that there exists a non-empty set of encoding packets with degree one at the end of each step. If the set of encoding packets with degree one becomes empty before all input packets are recovered, then the decoding fails. The LT process is a generalization of the classical process of throwing balls ran- domly into bins. A classical analysis shows that K = ln(k= ) k balls are necessary on the average to ensure that each of the k bins is covered by at least one ball with probability of at least 1 . In the analysis of the LT process, encoding packets are analogous to balls and input packets are analogous to bins and the process succeeds if at the end all input packets are covered. The analysis in [53] shows a construction of a degree distribution such that the input batch of k packets can be recovered using 114 Figure 4.3: Block diagram for LT encoding. K = k + O(ln2(k= ) pk) encoding packets. In the next section, we discuss how LT codes can be integrated into the transmission of MPEG-2 transport stream packets. 4.3.2 Integration of LT codes to packet transmission In this section, we will describe how a generic transport protocol could incorporate LT codes into the transmission of packets in order to provide reliability over the satellite segment of the network. We assume that data can be organized into B batches of k MPEG-2 transport stream packets at the NOC following the multi-protocol encapsula- tion. Let K be the number of encoding packets, such that the probability of a receiver recovering the original batch of k input packets after accumulating K encoding packets is greater than 1 , for some > 0. Each batch is encoded using LT coding, and encoding packets are forwarded to the DVB channel encoder for transmission. 115 Transmission of batches proceeds in transmission rounds. In transmission round, r, where 1 r B, the protocol attempts transmission of batch r for the rst time. Because of the construction of LT codes, users have to accumulate at least K encoding packets in order to successfully recover any input batch. Therefore, for batch r, the protocol has to transmit at least K encoding packets in this rst attempt. The number of encoding packets transmitted in the rst attempt of a batch is controlled by a transmis- sion window, which we refer to as W1. In round r, W1(r) encoding packets are generated for batch r and placed in an outgoing queue Q1. Only after the transmission of W1(r) encoding packets for the batch, the users can start the recovery process. Therefore, the value of W1(r) is at least equals to W min1 = K, for 1 r B. However, protocol may choose to transmit more than K encoding packets for a batch in its rst attempt in order to proactively account for the possible packet losses during the transmission. A user may fail to complete the recovery process of a batch following the initial attempt, for two reasons: (i) packet loss over the channel is too severe, and not enough packets have been accumulated, or (ii) K encoding packets are not suf cient for decod- ing of this particular instance of the LT encoding which may happen with probability , for some > 0. In these two cases, the recovery of the batch is not completed af- ter the rst attempt, and additional encoding packets are transmitted in the subsequent attempts. A second window, W2, controls the transmission of additional packets for all failed batches. In transmission round r, the protocol transmits additional encoding 116 packets for batches i = 1; : : :; r 1, such that W2(r) = r 1X i=1 Ai(r); (4.1) where Ai(r) is the additional number of encoding packets required at round r for a failed batch i with initially A1(1) = 0 and W2(1) = 0. Additional encoding packets for failed batches are stored in an outgoing queue Q2. Q2 always holds additional encoding packets for previously failed batches. If all previous batches are recovered before the current round, then W2(r) = W min2 = 0. The transmission of packets in queue Q1 and queue Q2 follow a time division, where transmission of packets in Q1 is followed by the transmission of the packets of in Q2. This constitutes the completion of transmission round r. After completion of the transmission round, the NOC awaits feedback reports from the users. When the protocol receives a feedback report from a user u, it gets information on the decoding status of the last transmitted and all previously failed batches. This feedback report consists of a set of indices of the batches that failed at user u, Iu f1; 2; : : :; rg, and the number of additional encoding packets required in the subsequent round to complete the decoding in the next round, i.e.fAui (r+1)gi2Iu. After collecting feedback reports, the protocol calculates the maximum number of additional encoding packets required for all batches, over all users: Ai(r + 1) = max u:i2Iu fAui (r + 1)g; i = 1; : : :; r: (4.2) The protocol then proceeds with the next transmission round until all batches are completed successfully by all users. Ideally, the goal of the protocol would be to com- 117 plete the transmission in B rounds. However, because of possible packet losses, it may be required to transmit additional encoding packets for several batches after round B. In this case, W1(r) = 0, for r > B, since initial transmission attempts for all batches have been completed. 4.3.3 Adaptive transmission of encoding packets From user perspective, the protocol must make sure that every batch can be recovered at the end of the rst attempt of transmission, because additional rounds add to the overall delay. At the same time, protocol should transmit as few encoding packets as possible (ideally completing the recovery after transmitting K encoding packets) for bandwidth ef ciency. These two requirements constitute a trade-off. In one extreme scenario, the protocol may set W1 >> K, in which case, all users complete decoding of a batch after initial attempt with very high probability. On the other hand, if packet loss rate is low, this approach would result in transmission of many unnecessary encoding packets. In the other extreme, the protocol may set W1 = K, and transmit additional encoding packets reactively in response to user requests. This guarantees that minimum number of encoding packets are transmitted for the batch. However, because, the propagation delay for a two-way satellite system is much larger than the transmission delay at high data rates, this approach would result in increased delays. In this section, we look at the possibility of using channel state condition for deter- mining the number of encoding packets transmitted in each round. At the end of trans- 118 mission round r, each user transmit a set of indices Iu f1; 2; : : :; rgcorresponding to the batches that are not completed at the end of the round, and the number of additional encoding packets requested in the next round, i.e. fAui (r + 1)gi2Iu 8u 2U. This information can be used to calculate the average loss rate of the user in the previous round by, Pu(r + 1) = 8> >>< >>> : 1 jIuj P i2Iu frg Aui (r+1) Ai(r) + Ar(r+1) W1(r) ; r2Iu 1 jIuj P i2Iu Aui (r+1) Ai(r) ; r =2Iu (4.3) In the next transmission round, these loss probability estimates are used to scale the number of encoding packets transmitted to the users according to the following rules: P(r + 1) =dmax u2U fPu(r + 1) : Pu(r + 1) ge (4.4) W1(r + 1) = P(r + 1) K; (4.5) W2(r + 1) = rX i=1 (P(r + 1) Ai(r + 1)); (4.6) where, P(r + 1) is the maximum packet loss rate based on the feedback information collected at the end of the previous round, and is a threshold value. The threshold value is required to limit the number of additional encoding packets transmitted for the current round when the maximum packet loss rate is very high. We are going to use as a tunable parameter. Intuitively, if some user is experiencing a very deep fade, resulting in a very high packet loss rate, even the large number of additional encoding packets transmitted would not be enough for it to accumulate the necessary packets for the purpose of decoding. Therefore, the bene t to the worst case user would be minimal while the bandwidth ef ciency for users in better channel conditions drops drastically. 119 In the next section, we analyze the potential bene ts of this approach for an exam- ple scenario, in an attempt to gain better understanding of the uses of packet level FEC coding as an aid in reliable multicast communication. 4.4 Performance analysis 4.4.1 Simulation setup In this section, we look at the distribution of a 184Mb le to U = 20 users over the satellite network. The le is organized as B = 100 batches of k = 10000 MPEG-2 transport stream packets (184 Bytes payload and 4 Bytes header). The analysis in [53] shows that the decoding overhead for batches of this size over repeated experiments never exceeds 10% for LT codes. Therefore, as a worse case analysis, we assume that a user successfully recovers an input batch if it accumulates at least K = 11000 encoding packets. In order to study the performance of packet distribution with integrated LT coding, we need to establish connection between the channel states of each user and the corre- sponding packet loss rates. The channel state for each user is simulated independently according to the channel model previously discussed in Section 2.5.2. This model gen- erates a time series of signal attenuation over a satellite channel operating at Ka-band frequencies. For every user, signal attenuation level sample generated by the simulator is input to the downlink link power-budget calculation for the satellite system (see Sec- tion 2.5.1), for a transmission power level of P = 5:0 Watts and downlink data rate of 120 92 Mbps. The link power-budget calculation determines the ratio of bit energy to noise power spectral density (Eb=No) for every user. Assuming that the DVB channel encoder uses the standard concatenated coding with (188,204) RS outer code to encode each 188-Bytes LT encoding packet, ideally interleave the packet symbols, and then pass it through a rate 1=2 convolutional coder, the packet error probability at the output of the DVD channel decoder for a user is given by the following well-known approximations: 1. For the convolutional inner code, the probability that the output bit-stream will differ from the original bit-stream in exactly d positions is given by Pd = 12erfc( rE b No d); (4.7) for BPSK modulation. 2. The probability of bit error at the output of the convolutional decoder can be ap- proximated by Pcb dmaxX d=df cd Pd; (4.8) where df is the free distance of the convolution code, and cd is the number of possible output bit-streams that differ from the original one by d positions. The rst eighteen values of cd for the df = 10 convolutional code used by the DVB encoder is given by cd = [36 0 211 0 1404 0 11633 0 77433 0 5026900 3322763 0 21292910 0 134365911 0]: (4.9) 121 3. The symbol error probability can be upper-bounded by Ps min(8 Pcb; 1:0): (4.10) During the simulations, symbol error probability of each user is calculated using this analysis and the corresponding propagation conditions. Based on the assumption that the symbol errors within a packet occur independently of each other due to the presence of symbol interleaver, for each user packet erasure events are determined. Packet erasure events take into account the error detecting and correction capabilities of the outer RS code. In the next section, we provide our simulation results under this test setup. 4.4.2 Results The behavior of the algorithm depends heavily on the packet loss patterns of the users, which depend on the channel propagation conditions. Therefore, we look at 100 differ- ent instantiations of the le transfer described in the previous section over a period of 24 hours simulated time. There are several metrics of interest in this scenario: 1. Average number of encoding packets per batch: This is the average number of encoding packets transmitted per batch over the lifetime of the le transfer (over 100 batches) including the packets transmitted during the initial attempt and any subsequent attempts. The le transfer consists of 100 batches of K = 11000 encoding packets. Therefore, this average is always equal to or greater than K. 2. Average number of transmission rounds per batch: This is the average number of attempts made by the NOC in order to complete the transmission of a batch over 122 the lifetime of the le transfer. At least one attempt is made in order to transmit a batch, hence, this average is always equal to or greater than one. 3. Session time: This is the time it takes for all users to complete the reception of the le transfer. 4. Average size of W1: This is the average size of the transmission window W1 over the lifetime of the le transfer. 5. Average size of W2: This is the average size of the transmission window W2 over the lifetime of the le transfer. In Figures 4.4 to 4.7, we look at these ve metrics as averaged over all 100 session instantiations. The rst observation we make is that the channel conditions are favor- able for most of the 24 hours period. The average channel attenuation during this period remains is in the range of 2 3dB, and the 5dB. transmit power, coupled with the strong DVD channel encoding, is capable of keeping the symbol error rates at low gures even when the channel attenuation is as high as 5 6dB. Therefore, most of the sessions complete batch transmissions in one round, with transmitting only few more additional encoding packets per batch. In Fig. 4.4, we plot the average number of encoding pack- ets transmitted per batch in order to complete decoding by all users as a function of the threshold . We observe that batches are completed on average only with 75 80 ad- ditional encoding packets. Moreover, as we increase the threshold value, the algorithm transmits more packets proactively. Because the algorithm decides on the number of 123 Figure 4.4: Average number of encoding packets per batch transmitted in order to com- plete the le transfer as averaged over all 100 session instantiations. packets to be transmitted proactively based on an estimate of the actual packet loss rate, and because the channel conditions may vary by the time the feedback reaches NOC, the increased value of the threshold results in the transmission of unnecessary encoding packets (observed as the increased number of packet per batch completion). However, proactive transmission of encoding packets also helps decrease the av- erage number of rounds required to complete a batch by all active users. This results can be observed in two different ways; (i) directly from Fig. 4.5, where average number of transmission rounds per batch is plotted as a function of the packet loss threshold , or (ii) from the fact that the average size of W1 increases (i.e. more packets are transmitted with the initial attempt), while the average size of W2 decreases (i.e. fewer packets are transmitted in the subsequent rounds). These results are plotted in Figures 4.6 and 4.7. 124 Figure 4.5: Average number of transmission rounds per batch in order to complete the le transfer as averaged over all 100 session instantiations. Figure 4.6: Average size of the transmission window W1 as averaged over all 100 session instantiations. 125 Figure 4.7: Average size of the transmission window W2 as averaged over all 100 session instantiations. Although the average number of transmission rounds per batch decreases as more packets are transmitted in advance, the session time to complete the transmission may actually increase as a result (Fig. 4.8). This counter-intuitive observation results from the fact that even though the number of rounds per batch decreases, the time it takes to complete a single round increases because of the additional encoding packets. When averaged over all 100 instantiations of the le transfer, the results are not able to re ect clearly the bene ts of using an adaptive window size for proactively trans- mitting additional encoding packets. This is because most of the sessions that are initial- ized during the 24hr period actually encounter favorable channel conditions and there- fore complete the le transfer without the need for retransmissions or additional encod- ing packets. As a result of this, when we look at the average results over all sessions, the 126 Figure 4.8: Average time it takes to complete the le transfer at all users, as averaged over all 100 session instantiations. additional bene ts of having adaptive mechanisms appear minimal. Therefore, in the next set of results, we look at the same performance metrics over only the sessions that required on the average more than K = 11000 encoding packets per batch to complete the le transfer. In Fig. 4.9, we plot the average number of encoding packets required per batch for these sessions. We observe that for these sessions the number of additional encod- ing packets required to complete a batch can be considerably larger than the minimum number K. The exibility in the number of encoding packets that can be generated for a batch by the LT coding structure proves very valuable particularly in these cases. However, the effect of changing the loss rate threshold follows a similar trend for these instances as well. As more encoding packets are transmitted proactively, the algorithm 127 Figure 4.9: Average number of encoding packets per batch transmitted in order to com- plete the le transfer as averaged over only the sessions that required more than K encoding packets per batch. faces the risk of transmitting more than necessary since the calculations are based on estimates. The number of transmission rounds required per batch, on the other hand, decreases with the proactive approach (Fig. 4.10). Similar trends are observed for the sizes of transmission windows W1 and W2, even though the dynamic range is much larger for this subset of sessions (Figures 4.11 and 4.12). Clearly, the results establish the conclusion that as more encoding pack- ets are transmitted proactively, the requirement for additional encoding packets in the subsequent rounds decreases. However, the results also show that the algorithm faces the risk of transmitting to many encoding packets in advance, while trying to predict future packet losses, thereby increasing the time to complete the session for all users 128 Figure 4.10: Average number of transmission rounds per batch in order to complete the le transfer as averaged over only the sessions that required more than K encoding packets per batch. (Fig. 4.13). In the next section, we sum up our observations from this chapter and comment on the insights we gained on the use of packet level FEC coding. 4.5 Summary In this chapter, we have discussed the potential bene ts of using packet level FEC coding as an aid in reliable multicast communication. Integration of packet level FEC coding is useful in reliable multicast communication because it helps in recovering from packet losses without relying on retransmission of speci c packets. This is the most important feature of the packet level FEC codes in satellite multicast transmission. A transmitted 129 Figure 4.11: Average size of the transmission window W1 as averaged over only the sessions that required more than K encoding packets per batch. Figure 4.12: Average size of the transmission window W2 as averaged over only the sessions that required more than K encoding packets per batch. 130 Figure 4.13: Average time it takes to complete the le transfer at all users, as averaged over only the sessions that required more than K encoding packets per batch. encoding packet recovers losses of different packets in different users, and the broadcast nature of the satellite channel enables easy dissemination of encoding packets to several users in single hop. However, packet losses in satellite networks occur in bursts that hap- pen in time-scales that are much larger than the duration of a single packet transmission. Therefore, in order to be useful, packet level FEC coding should be able to generate a fairly large number of encoding packets per input batch. Otherwise, the system would run out of encoding packets to transmit before all users accumulate enough packets to continue with the decoding of a batch. The LT encoding structure we have discussed in this chapter has been the choice primarily because of its ability to generate a very large number of encoding packets per input batch. We also investigated the possibility of adjusting the number of encoding packets 131 transmitted in response to the estimated packet losses. The bene t of this approach ap- pears to be limited for several reasons. First of all, the packet loss rate remains low for most of the operational time due to the existence of link power-margins and strong channel coding implemented for typical systems. Therefore, for most of the sessions, transmission of additional encoding packets in response to user requests prove to be ef- cient enough. In cases where channel fading is deep enough to cause severe packet loss patterns, it is dif cult to estimate the packet loss rates in advance to act proactively, especially for short session durations. Therefore, the algorithm risks transmitting more encoding packets than needed. In conclusion, we expect adaptive transmission of en- coding packets to be more application speci c and be applied to dissemination of large data, rather than being a standard part of a multicast transmission protocol. 132 Chapter 5 Conclusions In this dissertation, we focused on investigating the possible performance enhancements in terms of the throughput, capacity and scalability of a multiple-spot beam satellite communication system that supports both unicast and multicast services. Towards this goal, Chapter 2 and Chapter 3 were dedicated to providing schemes for more ef cient allocation and use of system resources when multicast applications share the system re- sources with unicast applications. On the other hand, Chapter 4 investigated the funda- mentals of reliable multicast communication over satellite networks from the transport protocol perspective. In this work, we targeted a star topology satellite network, where a Ka-band, geo- synchronous satellite provided broadband services to a large number of users located inside its footprint. The multiple spot-beam, on-board packet processing and switch- ing technologies allowed transmission of data to multiple users in multiple spot-beam locations, while users that are equipped with two-way direct communication terminals accessed the backbone terrestrial network through the network operations center. In this network setup, we highlighted the performance related issues that arise when multicast sessions are introduced to the system, and when they compete with existing unicast ses- sions. This network template, and its discussion throughout the dissertation, provides 133 a guideline for future work on this topic by clearly differentiating the design and solu- tion spaces for multicast communication over satellite system, from that of the wireline systems. More speci cally, in Chapter 2, we looked at the problem of user heterogeneity in multicast communication. In a multiple spot-beam satellite networks, we showed that user heterogeneity occurs a result of the temporal and spatial variations of the physical communication channel. We argued that this variations become signi cant particularly for systems operating at the Ka-band frequencies and beyond. These observations have lead to the conclusion that users residing in different geographical locations are likely to experience highly variable channel conditions, and in order for multicast services to per- form favorably, the system has to compensate for these variations, not in an individual basis, but as a group. Towards this end, we showed that schemes primarily targeted for the mitigation of the effects of signal fading, such as adaptive power allocation, could be made aware of the number, distribution and the type of the sessions operating at the higher network layers. Our contribution allows adaptive power allocation to multiple spot-beams with the goal of smoothing user heterogeneity, and result in average service rates that are higher for both unicast and multicast sessions. This work also pushes the envelope for the possibility of more cross-layer interaction between functionalities that have been considered to operate separately. In Chapter 3, we provided methods for ef cient feedback collection from a large group of users. We identi ed ef cient feedback collection as a key issue, not only be- 134 cause it complements the operation of our multicast-aware power allocation scheme, but also because it is a key part in providing additional multicast services, such as reliable multicast communication. Our discussion shows that providing ef cient feedback col- lection and at the same time controlling the volume of information owing through the network is a more complicated task in our target scenario than similar approaches tar- geted primarily for wireline networks where users share or receive information among them more easily. However, our framework proved that it is possible, in most cases, to reduce the volume of user feedback by exploiting the nature of the information to be transmitted and by considering that only a subset of users need to be tracked. We rst formulated our solution as a stand alone application to the problem of collecting channel state information from a set of users that can access to only a limited number of channels for communicating their feedback information. The solution, which is based on the idea that the users with the breaking news should be given immediate priority in communicating their information, proved successful in limiting the volume of feedback information generated, while maintaining the collection of relevant information. Fol- lowing our stand-alone evaluation, we integrated this algorithm to our multicast-aware power allocation scheme to complement its operations. Our contributions in this chapter showed that, it is possible to rely on user feedback for various multicast services, even in the case of large number of users, without allocating a large portion of system resources. The last part of the thesis investigated multicast communication support from a different angle that looked at the problem from the point of view of individual multicast 135 sessions rather than the global optimization of system resources among all active unicast and multicast sessions. In Chapter 4, we evaluated the use of packet level FEC coding as a part of a generic transport protocol that provides reliable multicast communication. Our experimental setup was more geared towards understanding the bene ts and limits of having packet level FEC coding in this context than providing a full protocol descrip- tion. Our experiments con rmed that packet level FEC coding is ef cient in recovering from losses in the context of satellite networks because of the possibility of recovering different packets losses in different users by dissemination of encoding packets. The main contribution of this chapter is in the use of a more complicated and more realistic channel model in experiments. Our setup included a time-series generator for simulat- ing the channel attenuation levels, the output of which is fed into a real-life link-budget calculation in order to estimate the packet loss rates. This setup was more complicated, and presumably more realistic, than previous cases in the literature, which set the packet loss rates as an external parameter, rather than going through the complete stack we have used. This setup was crucial in providing the insights we have obtained on the adaptive application of packet level FEC coding. Although this thesis covered a signi cant number of topics related to multicast communication support over satellite communication networks, there remain equally important open problems to dwell up on. The next section, highlight some of these problems for future work on this topic. 136 5.1 Suggestions for future study The following points remain open to further study: In Chapter 2, we tested our power allocation policy for different number of ses- sions and different session con gurations, however, they were set at the beginning of the analysis and remained xed in time during the course of the simulations. A more realistic scenario would have to investigate dynamic session con gurations that take into account the session connection and termination rates and session durations into effect. In Chapter 2, we assumed that the power-rate curve was a continuous function. However, in a real system, the set of power levels that can be supported and the corresponding transmission rates for a given set of modulation schemes are likely to be nite. Therefore, it is desirable test this approach under more stringent system constraints. It may be an interesting direction to link the minimum power levels associated with each active session in Chapter 2 to some form of a quality of service (QoS) metric. Minimum power levels guarantee the support of a minimum rate that can be negotiated before the start of the session as a QoS level. In Chapter 3, we chose a simple functional relationship for determining the trans- mission probability of individual users. Our analytical results were limited in favor of using a more complicated channel model, which did not lend itself into a 137 easy mathematical description. Therefore, we relied on simulations and intuitive analysis. It would be interesting to see if this can be taken a step further to get better understanding of the form of the transmission probability curve. In Chapter 4, we relied on simple averages to estimate the packet loss rate for future frames. However, it might be possible to extract more information on the channel behavior if other parameters such as fade durations, and the conditional probability distributions for fade levels could be obtained from the underlying channel model. Therefore, an interesting direction, which was outside the scope of this dissertation, would be extract statistical information on the channel behavior and to incorporate it to the estimation of future packet loss rates for adaptive packet level FEC encoding. 138 BIBLIOGRAPHY [1] F. Gargione, T. Iida, F. Valdoni, and F. Vatalaro, Services, technologies, and sys- tems at Ka band and beyond: A survey, IEEE J. Select. Areas Commun., vol. 17, no. 2, pp. 133 144, February 1999. [2] E. Lutz, M. Werner, and A. Jahn, Satellite systems for personal and broadband communications. Springer-Verlag, 2000. [3] J. V. Evans, Communication satellite systems for high speed Internet access, IEEE Antennas and Propagation Magazine, vol. 43, no. 5, October 2001. [4] P. Chitre and R. Gupta, Satellite systems for multimedia and Internet traf c, in Proc. of IEEE Microwave Symposium Digest, vol. 2, May 2001, pp. 20 25. [5] A. Bertout, G. Christiansen, J. Couetet, and P. Spencer, Skybridge ser- vices, Alcatel Telecommunications Review, Tech. Rep., 4th Quarter 2001, http://www.alcatel.com/atr/. [6] E. J. Fitzpatrick, SPACEWAY system summary, Space Communications, vol. 13, pp. 7 23, 1995. [7] G. Losquadro and V. Marziale, The Euroskyway network with on-board process- ing to support fast Internet and interactive TV services for residential users, in Proc. of IEEE-IBC Colloquium, London, October 2000, www.euroskyway.it. 139 [8] G. Akkor, J. S. Baras, and M. Hadjitheodosiou, An optimization-based approach to ow control and resource allocation problem in satellite communication sys- tems, in Proc. of AIAA ICSSC 2004, Monterey, CA, May 2004. [9] , A feedback implosion suppression algorithm for satellite reliable multi- cast, in Proc. of IEEE GLOBECOM, vol. 7, San Francisco, CA, December 2003, pp. 3765 3769. [10] G. Akkor and J. S. Baras, A reliable multicast transport protocol with feedback implosion suppression for satellite communication systems, in Proc. of CISS, Princeton, NJ, March 2004. [11] G. Akkor, M. Hadjitheodosiou, and J. S. Baras, Transport protocols in multicast via satellite, Int. J. Sat. Comm., vol. 22, no. 6, pp. 611 627, November/December 2004. [12] S. McCanne, V. Jacobson, and M. Vetterli, Receiver-driven layered multicast, in Proc. of ACM SIGCOMM, 1996, pp. 117 130. [13] L. Vicisano, J. Crowcroft, and L. Rizzo, TCP-like congestion control for layered multicast data transfer, in Proc. of IEEE INFOCOM, vol. 3, March 1998, pp. 117 130. [14] X. Li, S. Paul, and M. Ammar, Layered video multicast with retransmissions: Evaluation of hierarchical rate control, in Proc. of IEEE INFOCOM, vol. 3, March 1998, pp. 1062 1072. 140 [15] V. Roca, Packet scheduling for heterogeneous multicast transmissions, in Proc. of PfHSN, August 1999, pp. 101 116. [16] M. J. Donahoo, M. H. Ammar, and E. W. Zegura, Multiple channel multicast scheduling for scalable bulk-data transport, in Proc. of IEEE INFOCOM, vol. 2, 1999, pp. 847 855. [17] C. Enjamio, E. Vilar, and F. P. Fontan, Spatial distribution of rainfall rate: bene ts of the site diversity as a dynamic fade mitigation technique, in Proc. of COST Action 280, First International Workshop, July 2002. [18] H. Fukuchi, Quantitative analysis of the effect of adaptive satellite power control as a rain attenuation countermeasure, in Proc. of IEEE International Symposium on Antennas and Propagation, vol. 2, 1994, pp. 1332 1335. [19] A. D. Panagopoulos, P.-D. M. Arapoglou, and P. G. Cottis, Satellite communi- cations at Ku, Ka, and V bands: propagation impairments and mitigation tech- niques, IEEE Communication Surveys and Tutorials, vol. 6, no. 3, Third Quarter 2004, www.comsoc.org/pubs/surveys. [20] M. M. J. L. van de Kamp, Climatic radiowave propagation models for the de- sign of satellite communication systems, Ph.D. dissertation, Eindhoven Technical University, Eindhoven, The Netherlands, November 1999. 141 [21] Hughes Communications Galaxy Inc., Application of Hughes Communication Galaxy, Inc. before the Federal Communications Commission for two Ka-band domestic xed communication satellites, December 1993. [22] U.-C. Fiebig, A time-series generator modeling rain fading and its seasonal and diurnal variations, in Proc. of 1st International Workshop of COST-Action 280, Malvern, UK, 2002. [23] , A time-series generator modeling rain fading, in Proc. of Open Symposium on Propagation and Remote Sensing. Garmisch-Partenkirchen: URSI Commis- sion F, 2002. [24] Population Division U.S. Census Bureau, Table NST-EST2003-01, Annual estimates of the population for the United States, and for Puerto Rico: April 1, 2000 to July 1, 2003, release date: December 18, 2003. [Online]. Available: http://eire.census.gov/popest/data/states/tables/NST-EST2003-01.php [25] A. Legout, J. Nonnenmacher, and E. W. Biersack, Bandwidth allocation policies for unicast and multicast ows, IEEE/ACM Trans. Networking, vol. 9, no. 4, pp. 464 478, August 2001. [26] M. W. Koyabe and G. Fairhurst, Reliable multicast via satellite: A comparison survey and taxonomy, Int. J. Sat. Comm., vol. 19, no. 1, pp. 3 23, 2001. 142 [27] P. Radoslavov, C. Papadopoulos, R. Govindan, and D. Estrin, A comparison of application-level and router-assisted hierarchical schemes for reliable multicast, in Proc. of IEEE INFOCOM, 2001, pp. 229 238. [28] J. P. Macker and R. B. Adamson, The multicast dissemination protocol toolkit, in Proc. of IEEE MILCOM 1999, vol. 1, November 1999, pp. 626 630. [29] S. Floyd, V. Jacobson, C. Liu, S. McCanne, and L. Zhang, A reliable multicast framework for light-weight sessions and application level framing, IEEE J. Select. Areas Commun., vol. 15, pp. 407 421, 1997. [30] T. Speakman and et al., Pragmatic general multicast (PGM) reliable transport protocol speci cation, Internet Society Request for Comments, December 2001, RFC3208. [31] S. K. Kumar, S. Bhattacharyya, M. Keaton, D. Kiwior, J. Kurose, D. Towsley, and S. Zabele, Scalable fair reliable multicast using active services, IEEE Network, January 2000. [32] C. Wang and V. C. M. Leung, Performance evaluations of SRMTP for reliable multicasting over satellite networks, in Proc. of WCNC, vol. 3, March 2003, pp. 1813 1818. [33] G. Cao and Y. Wu, Reliable multicast via satellite, in Proc. of IIT: Coding and Computing, April 2001, pp. 183 188. 143 [34] S. Cho and I. F. Akyildiz, A poker-game-based feedback suppression algorithm for satellite reliable multicast, in Proc. of IEEE GLOBECOM 2002, November 2002. [35] E. Ichihara, K. Kikuchi, T. Tsuchida, K. Kawazoe, and H. Kazama, Reliable IP- multicast protocol for bi-directional satellite communication systems, in Proc. of AIAA ICSSC, April 2003, Online Technical Information. [36] M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP completeness. San Francisco: W. H. Freeman and Company, 1979. [37] D. Towsley, J. Kurose, and S. Pingali, A comparison of sender-initiated and receiver-initiated reliable multicast protocols, IEEE J. Select. Areas Commun., vol. 15, no. 3, pp. 398 406, April 1997. [38] R. E. Blahut, Theory and Practice of Error Control Codes. MA: Addison Wesley, 1984. [39] A. J. MacAuley, Reliable broadband communication using a burst erasure cor- recting code, in Proc. of ACM SIGCOMM, Philadelphia, PA, September 1990. [40] L. Rizzo, Effective erasure codes for reliable computer communication proto- cols, ACM Computer Communication Review, vol. 27, no. 2, pp. 24 36, April 1997. 144 [41] S. Cho, A. Goulart, I. F. Akyildiz, and N. Jayant, An adaptive FEC with QoS provisioning for real-time traf c in LEO satellite networks, in Proc. of IEEE ICC, June 2001, pp. 2938 2942. [42] J. Nonnenmacher, E. W. Biersack, and D. Towsley, Parity-based loss recovery for reliable multicast transmission, IEEE/ACM Trans. Networking, vol. 6, no. 4, pp. 349 361, August 1998. [43] M. Luby, L. Vicisano, J. Gemmell, L. Rizzo, M. Handley, and J. Crowcroft, For- ward error correction building blocks, Internet Society Request for Comments, December 2002, RFC3452. [44] , The use of forward error correction in reliable multicast, Internet Society Request for Comments, December 2002, RFC3453. [45] L. Rizzo and L. Vicisano, A reliable multicast data distribution protocol based on software FEC techniques, in Proc. of HPCS, 1997. [46] D. Rubenstein, S. Kasera, D. Towsley, and J. Kurose, Improving reliable multicast using active parity encoding services, in Proc. of IEEE INFOCOM, 1999. [47] I. Rhee, S. R. Joshi, M. Lee, S. Muthukrishnan, and V. Ozdemir, Layered multi- cast recovery, in Proc. of IEEE INFOCOM, vol. 2, 2000, pp. 805 813. [48] A. Donner, S. Bovelli, and S. Shabdanov, Reliable multicast based on DVB- RCS, in Proc. of AIAA ICSSC, May 2002, Online Technical Information. 145 [49] H. Ernst, S. Shabdanov, A. Donner, and S. Scalise, Reliable multicast for land mobile satellite channels, in Proc. of AIAA ICSSC, April 2003, Online Technical Information. [50] F. Tommasi, S. Molendini, and A. Tricco, Design of the satellite reliable distri- bution protocol (SRDP), in Proc. of IEEE GLOBECOM, vol. 6, December 2003, pp. 3284 3289. [51] J. W. Byers, M. Luby, M. Mitzenmacher, and A. Rege, A digital fountain approach to reliable distribution of bulk data, in Proc. of ACM SIGCOMM 1998. [52] M. Luby, Information additive code generator and decoder for communication systems, U. S. Patent No. 6,307,487, October 2001. [53] , LT codes, in Proc. of Symposium on Foundation of Computer Science, 2002. [54] X. Zhou and J. S. Baras, TCP over GEO satellite hybrid networks, in Proc. of MILCOM 2002, vol. 1, October 2002, pp. 29 34. [55] Y. Shang and M. Hadjitheodosiou, TCP splitting protocol for broadband aeronau- tical satellite network, in Proc. of DASC 2004, vol. 2, 2004, pp. 1 9. [56] Digital Video Broadcasting (DVB): DVB speci cation for data broadcasting, ETSI EN 301 192 v.1.3.1 ed., European Telecommunication Standards Institute, 2003. 146