M ULTICAST FOR U BIQUITOUS
S TREAMING OF M ULTIMEDIA C ONTENT
TO M OBILE T ERMINALS
N ETWORK A RCHITECTURE AND P ROTOCOLS
Doctoral Dissertation by
Mariann Hauge
Submitted to the Faculty of Mathematics and Natural Sciences at the University of Oslo in partial fulfilment of the requirements for the degree Doctor Scientiarum
(Dr. Scient.) in Computer Science
March 2007
© Mariann Hauge, 2007
Series of dissertations submitted to the
Faculty of Mathematics and Natural Sciences, University of Oslo Nr. 624
ISSN 1501-7710
All rights reserved. No part of this publication may be
reproduced or transmitted, in any form or by any means, without permission.
Cover: Inger Sandved Anfinsen.
Printed in Norway: AiT e-dit AS, Oslo, 2007.
Produced in co-operation with Unipub AS.
The thesis is produced by Unipub AS merely in connection with the
i
A BSTRACT
The Universal Mobile Telecommunication Services (UMTS) network was envisioned to carry a wide range of new services; however, the first UMTS release was not designed to efficiently support multimedia content. In this thesis we analyse several mechanisms, and suggest archi- tectural changes to improve UMTS’s capacity for a subset of the multimedia services; high- bandwidth group services.
In our initial work we have suggested how IP multicast protocols can be used in the UMTS network to reduce the required network capacity for group services. This proposal was one of many suggestions for the evolving Multimedia Broadcast/Multicast Service (MBMS) archi- tecture for UMTS.
The next technique we have suggested and analysed is a new wireless channel type named the “sticky-channel”; this channel is intended for sparsely populated multicast groups. The sticky-channel is able to stick to mobile multicast members in the boarder area of neighbour- ing radio cells, thus some base stations does not need to broadcast the multicast data. Conse- quently, the total number of broadcast channels needed to cover a given area is reduced. There is a marginal reduction of required resources with this technique.
In the main part of our work we have studied heterogeneous multihop wireless access for multicast traffic in the UMTS network. In a heterogeneous wireless access network, the wire- less resources needed to distribute high-bandwidth group services, can be shared among co- operating network technologies. Mobile terminals with a UMTS interface and an IEEE 802.11 interface are readily available, consequently a heterogeneous network with UMTS and 802.11 links will be easy to deploy. We have described a heterogeneous architecture based on those wireless technologies. In this architecture, the range of a UMTS radio channel is reduced, and local IEEE 802.11-based Mobile Ad Hoc Networks (MANETs) forward the data to users lo- cated outside the coverage of the reduced UMTS channel. The wireless resources required to transmit a data packet are proportional to (at least) the square of the distance the packet must travel, thus a reduction in the channel range releases a significant amount of UMTS radio re- sources. Detailed simulation results showed acceptable service quality when the UMTS broadcast channel range is more than halved.
Finally we have studied whether Forward Error Correction (FEC) at the packet-level on multicast flows could improve the performance of the heterogeneous wireless access network.
There is a marginal improvement. Most of the protection brought by the FEC code has been used to repair the increased packet-loss introduced by the FEC overhead.
P REFACE
This dissertation is submitted to the Department of Informatics, Faculty of Mathematics and Natural Sciences, University of Oslo, in partial fulfilment for the degree of Dr. Scient. My work for this dissertation started in August 1999. Part of the work has been done as a full-time student, and part of the work as a part time student. The timeframe spanning the dissertation project also includes a pregnancy followed by 12 months maternity leave, and 4 months leave to finish a project for my employer (at the time) and part funder; Ericsson AS.
The work was carried out at University Graduate Center at Kjeller (UniK) under supervi- sion of Professor Øivind Kure at the Norwegian University of Science and Technology, Trondheim and Professor Pål Spilling at UniK. Due to Pål Spilling’s retirement from his po- sition as a professor, Professor Knut Øvsthus at Bergen University College, and Associate Professor II Paal Engelstad at the Department of Informatics, University of Oslo, have also been assigned as my supervisors in the final year of the thesis work.
The research has been part of the Future Communication Systems (FUCS) program, partly funded by the Research Council of Norway. Ericsson AS funded the remaining half of my project. The work has also been supported by UniK and the Norwegian Defence Research Es- tablishment (FFI).
As an employee of Ericsson, I wanted to focus my research on wireless communication for mobile telecommunication networks. I chose the Universal Mobile Telecommunication Serv- ices (UMTS) network as the framework for my research, and decided to narrow my focus on UMTS’s low capacity for high-bandwidth group services. The remainder of this dissertation presents the result of this work; analysis of several mechanisms intended to improve UMTS’s performance for these types of service.
iii
A CKNOWLEDGMENTS
First and foremost, I want to thank my technical advisor Professor Øivind Kure for his excel- lent supervision of my research work. He has been a valuable and motivating discussion part- ner, for all my work. Øivind was always available when I needed his comments. Thank you!
I am grateful to my (former) advisor Professor Pål Spilling and my former employer Eric- sson AS for giving me the opportunity to pursue my PhD through the Future Communication Systems (FUCS) program at the University Graduate Center at Kjeller (UniK).
I would like to thank Dr. Frank Y. Li at UniK for his support, feedback and valuable sug- gestions for my research. I have also gained much insight from discussions with former and present PhD students at UniK, especially Andreas Hafslund, Eli Winjum and Lars Landmark.
The efficient and friendly administrative support I have been given by the staff at UniK, have been appreciated.
This dissertation is dedicated to my family. First and foremost my dedication goes to my mother Klara, who did not live to see my PhD work finished, and to my father Tørres. They taught me to appreciate challenges and to stubbornly keep working with a problem until it can be solved. Those two values were the most important qualities I needed to see my research work through.
I appreciate the support from my brother Trond and my niece Turid who have both proof- read and given comments to part of my work. Trond has also given me frequent Adobe© sup- port for high quality pdf documents. Turid has provided support for the cases when I was forced to use for my paper submissions.
This dissertation is also dedicated to my nearest family; Arild and our daughter Helene (she was born halfway through my PhD work). It goes without saying that Arild’s support has been essential for my work. I look forward to having more spare time to spend at home with them.
Oslo, March 25, 2007 Mariann Hauge
v
L IST OF P UBLICATIONS
The author of this thesis is the primary author of papers A through F and the research report G (appended as Part II of the thesis). Papers A through F are co-authored with the external, technical supervisor. He has been a valuable discussion partner for the work presented and has also provided structural suggestions to how the content could be presented in a clear and pre- cise manner. The multicast protocols proposed in paper D has benefited from technical dis- cussion with a larger set of co-authors. The research report G provides detailed description of a slightly modified version of one of the multicast protocols proposed in paper D.
The author of this thesis has contributed to papers H and I as a discussion partner. For paper H the author has also provided technical expertise of the IEEE 802.11 standard to form the basis for applying the proposed empirical approach.
All papers (except the research report) have been published at peer-reviewed conferences and workshops.
PAPER A: M. Hauge and Ø. Kure, “Multicast in 3G Networks: Employment of Existing IP Multicast Protocols in UMTS,” In proceedings of the 5th ACM International Workshop on Wireless Mobile Multimedia 2002 (WoWMoM'02), Atlanta, USA, 2002, pp. 96-103.
PAPER B: M. Hauge and Ø. Kure, “Sticky Point-to-multipoint Channel for Multicast in UMTS,”In proceedings of the 8th International Conference on Cellular and Intelligent Communications 2003 (CIC'03), Seoul, South Korea, 2003.
PAPER C: M. Hauge and Ø. Kure, “Multicast Service Availability in a Hybrid 3G-cellular and Ad Hoc Network,” In proceedings of the 1st International Workshop on Wireless Ad-hoc Networks 2004 (IWWAN'04), Oulu, Finland, 2004.
PAPER D: M. Hauge, A. Hafslund, F.Y. Li and Ø. Kure, “Multicast-service Distribution on a Cellular Network Assisted by Local Ad Hoc Networks,” In proceedings of the 3rd Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net'04), Bodrum, Turkey, 2004, pp. 68 - 80.
PAPER E: M. Hauge and Ø. Kure, “A Heterogeneous Cellular and Ad Hoc Network Architecture for Multipoint Streaming: A detailed performance analysis,” In proceedings of the 3rd International Conference on Mobile Computing and Ubiquitous Networking (ICMU’06), London, UK, 2006. (A version of this paper has been accepted for publication in a special issue of the Information Processing Society of Japan (IPSJ) Journal, featuring selected papers from ICMU 2006.) PAPER F: M. Hauge and Ø. Kure, “Evaluation of Packet-level FEC with Multicast
Streaming for a Heterogeneous 3G-Cellular and Ad Hoc Network,” In proceedings of the European Symposium on Mobile Media Delivery 2006 (EuMob’06), Alghero, Sardinia, Italy, 2006.
REPORT G: M. Hauge, “Multicast in a Hybrid Cellular and Ad Hoc Network: Specification of an Ad Hoc Routing Protocol with Cellular Assistance,” Department of Informatics, University of Oslo, Norway, Research Report no. 334, March 2006, http://www.duo.uio.no.
Related papers:
PAPER H: F.Y. Li, M. Hauge, A. Hafslund, Ø. Kure and P. Spilling, “Estimating Residual Bandwidth in 802.11-based Ad Hoc Networks: An Empirical Approach,” In proceedings of the 7th International Symposium on Wireless Personal Multimedia Communications 2004 (WPMC'04), Abano Terme, Italy, 2004, pp. 471-476.
PAPER I: F.Y. Li, A. Hafslund, M. Hauge, P. Engelstad, Ø. Kure and P. Spilling,
“Dilemma of Using High Datarate in IEEE 802.11b Based Multihop Ad Hoc Networks,”In proceedings of the The 3rd IASTED International Conference on Communications, Internet, and Information Technology 2004 (CIIT'04), St. Thomas, US Virgin Islands, 2004, pp. 231-237.
vii
L IST OF F IGURES
Figure 1: This figure shows a heterogeneous wireless access network. The range of the UMTS broadcast channel has been reduced to cover the small grey area, and MANETs are used to forward the multicast data to terminals in the remaining area of the radio cell. . . . 6
Figure 2: The figure shows shared tree routing. Each source (S1 and S2) sends the packets to the core node (C) which in turn forwards the data onto the multicast tree. . . 10
Figure 3: The figure pictures source specific multicast routing. One multicast tree is established for each source (S1 and S2). The red nodes are multicast members. 11
Figure 4: This figure shows the UMTS (Universal Mobile Telecommunications System) elements participating in the MBMS architecture. CN (Core Network) is a high capacity backbone network, while UTRAN (UMTS Terrestrial Radio Access Network) incorporates the low capacity radio links. . . . 13
Figure 5: The figure compares the different multicast types with respect to group size/density and the level of mobility. . . . 27
Figure 6: This figure pictures different ways to integrate MANETs with 3G cellular networks. The depicted scenarios represent increased connectivity beyond cellular range, ad hoc networks for load balancing between cells and ad hoc networks to provide high bandwidth to the cell border. . . 30
Figure 7: The figure (ref. [22]) shows the encoding and decoding process for an ideal systematic FEC code. . . 37
Figure 8: Network traffic generated by multicast distribution compared to unicast distribution. . . 42
Figure 9: This figure pictures a large cellular network. A cell (base station) is represented with three bullets (sectors). The dark-red bullets portray sectors using sticky point-
to-multipoint channels. Red bullets represent sectors covered by a neighbour’s sticky-channel. Light grey bullets represent no transmission, unicast and normal multicast . . . 43
Figure 10: The figures show the trade-off between the radius of the cellular broadcast channel (MZONE), the maximum path length (in number of hops, NOH) between a multicast member and the gateway node within cellular coverage, and the required coverage (served terminals in%). This is shown for MANET transmission rages of 200m and 250m. . . . 45
Figure 11: The figure shows the distribution of total received packets (%) as a function of the path length. The horizontal lines shows average received packets (%) for all terminals. . . 47
Figure 12: The figure shows the reliability of a multicast flow with and without FEC, as a function of the FEC overhead. . . . 48
Figure 13: The figure compares the packet loss for data + 20% FEC before and after repair, with the packet loss for the same unprotected data stream. FEC repair based on two FEC encoding block sizes are shown: block sizes equivalent to 5s and 20s of the CBT stream. . . . 49
ix
L IST OF T ERMS AND A CRONYMS
1xEV-DO 1x EVolution-Data Optimized 3G 3rd generation of mobile networks 3GPP Third Generation Partnership Project 3GPP2 Third Generation Partnership Project 2 4G 4th generation of mobile networks
AAA Authentication, Authorization, and Accounting AODV Ad-hoc On-demand Distance Vector
AuC Authentication Centre
APN Access Point Name
ARS Ad-hoc Relay Station
AS Autonomous System
ASM Any Source Multicast
BCMCS Broadcast/Multicast Services (for CMDA2000) BM-SC Broadcast Multicast - Service Center
CBT Core Based Tree
CDMA2000 CDMA2000 is a family of third-generation (3G) mobile
telecommunications standards mainly used on the American continent.
CDMA2000 is standardized by 3GPP2.
CeNALAN Cellular Network Assisted by Local Ad Hoc Networks
CGF Charging Gateway Function
CN Core Network
DVB Digital Video Broadcasting DVB-H DVB for handheld terminals EIR Equipment Identity Register
Erasure code An encoding of a block of data packets that allow the receiver to reconstruct a certain number of erasures (lost packets).
FACH Forward Access Channel
FEC Forward Error Correction
Flooding A mechanism to distribute a data packet to all nodes in a network. All nodes in the network broadcasts the incoming packet on all of its interfaces, once for each packet.
GGSN Gateway GPRS Support Node
GPRS General Packet Radio Service
HDR High Data Rate
HLR Home Location Register
HSDPA High Speed Downlink Packet Access
IEEE Institute of Electrical and Electronics Engineers IEEE 802.11 Wireless LAN standard developed by the IEEE IEEE 802.16 Wireless MAN standard developed by the IEEE
IETF Internet Engineering Task Force. A standardisation body for IP networking.
IGMP Internet Group Management Protocol
IP The Internet Protocol
IST Information Society Technologies
J-Sim Component based network simulator, coded in Java©
LAN Local Area Network
MAC Medium Access Control
MAN Metropolitan Area Network
MANET Mobile Ad hoc NETwork
MBC MBMS Bearer Context
MBGP Multicast Border Gateway Protocol
MBMS Multimedia Broadcast/Multicast Service (for UMTS) MLD Multicast Listener Discovery
MPR Multipoint Relay
MSDP Multicast Source Discovery Protocol Node-B The UTRAN base station
OLSR Optimized Link State Routing
Path-loss The attenuation undergone by an electromagnetic wave in transit from a transmitter to a receiver in a telecommunication system.
PIM-SM Protocol Independent Multicast - Sparse Mode
QoS Quality of Service
RAN Radio Access Network
Relay Repeater for a wireless data-channel.
xi Softstate Temporary state information that is deleted when a timer expires. The timer is refreshed before timeout if the state information is still valid and should be maintained.
SSM Single Source Multicast
SSM Source Specific Multicast
TDD Time Division Duplex
UE User Equipment
UMTS Universal Mobile Telecommunications System UTRAN UMTS Terrestrial Radio Access Network WCDMA Wideband Code Division Multiple Access WLAN Wireless Local Area Network
xiii
C ONTENTS
ABSTRACT . . . i
PREFACE. . . ii
ACKNOWLEDGMENTS . . . iii
LIST OF PUBLICATIONS. . . v
LIST OF FIGURES . . . vii
LIST OF TERMS AND ACRONYMS. . . ix
CONTENTS . . . xiii
P ART I
1 Introduction . . . 31.1 Background. . . 3
1.2 Motivation and Research Overview . . . 4
1.3 Thesis Outline. . . 8
2 Overview and Related Work . . . 9
2.1 Internet Protocol (IP) Multicast . . . 9
2.2 UMTS Multimedia Broadcast/Multicast Service . . . 12
2.3 Multicast for Mobile Ad Hoc Networks (MANETs) . . . 15
2.3.1 Tree-based Multicast Routing Protocols. . . 16
2.3.2 Mesh-based Multicast Routing Protocols . . . 20
2.3.3 Hybrid Tree-based and Mesh-based Protocols . . . 22
2.3.4 Multicast by Means of Broadcast (Flooding) . . . 25
2.3.5 Stateless Multicast . . . 26
2.3.6 Summary. . . 27
2.4 Dynamic Wireless Access Networks for UMTS . . . 28
2.4.1 Heterogeneous Access Networks . . . 29
2.4.2 Multihop Wireless Access Networks for Unicast. . . 30
2.4.3 Multihop Wireless Access Networks for Multicast . . . 35
2.4.4 Summary. . . 36
2.5 Forward Error Correction for Wireless Multicast . . . 37
3 Methods, Contribution and Discussion. . . 40
3.1 Methods and Assumptions . . . 40
3.2 Contribution . . . 41
3.2.1 IP Multicast Architecture for MBMS (Paper A) . . . 41
3.2.2 A Wireless Channel Type for Multicast in MBMS (Paper B) . . . 43
3.2.3 The Heterogeneous Wireless Network Architecture for Multicast Traffic (Paper C, Paper D, Paper E and Research Report G) . . . 44
3.2.4 Multicast with Forward Error Correction for the Heterogeneous Wireless
Network Architecture (Paper F) . . . 48
3.3 Discussion . . . 49
3.3.1 Future Work. . . 49
3.3.2 Conclusion . . . 50
References . . . 52
P ART II
PAPERA Multicast in 3G Networks: Employment of Existing IP Multicast Protocols in UMTS 1. Introduction . . . 632. Related Work . . . 64
3. UMTS Architecture Overview . . . 64
4. Multicast in UMTS. . . 65
4.1 Existing UTMS Multicast . . . 66
4.2 Multicast Routing Terminated in the RNC . . . 67
4.3 Multicast throughout the UMTS Network. . . 68
5. Conclusion . . . 69
References . . . 70
PAPERB Sticky Point-to-multipoint Channel For Multicast in UMTS 1. Introduction . . . 73
2. Related Work . . . 73
3. Sticky Multicast Architecture. . . 73
4. Sticky Multicast Analysis. . . 75
4.1. Isolated Subnetwork . . . 75
4.2. Large Network . . . 76
5. Conclusion and Future Work . . . 77
References . . . 77 PAPERC
Multicast Service Availability in a Hybrid 3G-cellular and Ad Hoc Network
xv
V. Conclusion . . . 85
References . . . 85
PAPERD Multicast-service Distribution on a Cellular Network Assisted by Local Ad Hoc Networks I. Introduction . . . 89
II. Related Work. . . 90
III. The CeNALAN architecture . . . 91
IV. Network Connectivity Study of the CeNALAN Architecture. . . 91
V. Routing Protocols for the Hybrid Network . . . 94
A. Centralized Multicast Routing Scheme . . . 94
B. Distributed Multicast Routing Scheme . . . 96
C. Preliminary Protocol-Overhead Analysis . . . 98
VI. Concluding Remarks . . . 99
References . . . 99
PAPERE A Heterogeneous Cellular and Ad Hoc Network Architecture for Multipoint Streaming: A detailed performance analysis 1 Introduction . . . 103
2 Related Work. . . 104
3 The Heterogeneous Network Architecture . . . 104
4 Routing Scheme. . . 105
5 Required Channel Range . . . 105
6 Simulation Setup and Results . . . 106
6.1 Simulation Objectives . . . 106
6.2 Sensitivity Analysis . . . 106
6.3 Simulation Assumptions . . . 106
6.4 Simulation Method . . . 107
6.5 Simulation Results . . . 108
6.6 Results of the Sensitivity Analysis. . . . 109
7 Conclusion . . . 110
References . . . 110
PAPERF Evaluation of Packet-level FEC with Multicast Streaming for a Heterogeneous 3G-Cellular and Ad Hoc Network 1. Introduction . . . 115
2. Related Work. . . 116
3. Network Architecture . . . 116
4. FEC Scheme . . . 116
5. Simulation Environment and Results . . . 117
5.1 Simulation Objectives . . . 117
5.2 Sensitivity Analysis . . . 117
5.3 Simulation Assumptions . . . 117
5.4 Simulation Method . . . 117
5.5 Simulation Results . . . 118
6. Conclusion . . . 119
References . . . 119
RESEARCH REPORTG Multicast in a Heterogeneous Cellular and Ad Hoc Network: Specification of an Ad Hoc Routing Protocol with Cellular Assistance 1 Introduction . . . 125
2 Abbreviations and Terminology. . . 125
3 Overview . . . 126
3.1 The Heterogeneous Architecture . . . 126
3.2 The Multicast Routing Protocol . . . 126
4 Message Formats . . . 127
4.1 Cellular Messages . . . 127
4.1.1 Instr_MQuery (unicast message) . . . 127
4.1.2 Instr_MConn (unicast message) . . . 128
4.1.3 Inf_No-Route (unicast message) . . . 128
4.1.4 Inf_NOH (unicast message). . . 128
4.2 Ad Hoc Messages . . . 128
4.2.1 MQuery (flooded, broadcast message) . . . 128
4.2.2 MConn (flooded, broadcast message) . . . 128
4.2.3 MReply (unicast message) . . . 129
4.2.4 MRepair (flooded, broadcast message) . . . 129
4.2.5 MAck (1-hop broadcast message) . . . 129
4.2.6 MTL (1-hop unicast message) . . . 129
5 Protocol Operation . . . 130
5.1 Establish a Multihop Multicast Tree. . . 130
5.1.1 Multicast tree establishment: 3G-cellular channel. . . 130
5.1.2 Multicast tree establishment: Ad hoc channel . . . 130
5.2 Add New Members to a Multicast Tree . . . 131
5.2.1 New multicast tree members: 3G-cellular channel . . . 131
5.2.2 New multicast tree members: Ad hoc channel . . . 131
5.3 Local Link Repair . . . 132
5.3.1 Local link repair: 3G-cellular channel . . . 132
5.3.2 Local link repair: Ad hoc channel . . . 133
5.4 Remove a Member from the Routing Tree . . . 134
xvii
5.6.1 Multicast tree refresh: 3G-cellular channel. . . 135
5.6.2 Multicast tree refresh: Ad hoc channel . . . 136
5.7 Timers and Constants. . . 137
5.7.1 Timers . . . 137
5.7.2 Constants . . . 138
Appendix A: MSC of selected message sequences . . . 140
1
PART I
I NTRODUCTION
3
1 Introduction
1.1 Background
The first release of the 3rd generation (3G) of mobile networks (e.g., Universal Mobile Tele- communication Services (UMTS) [2, 48]) was just completed when this thesis work started.
UMTS was designed to provide wireless access to the existing Internet services as well as UMTS specific services. A wide range of multimedia content was predicted to be an important set of new services. However, the UMTS network described in the first release did not have enough resources to support several concurrent multimedia streams.
A UMTS channel could provide maximum data-rates ranging from 64Kb/s - 2Mb/s de- pending of the environment. In later releases, the High Speed Downlink Packet Access (HSD- PA) channel has been introduced to provide maximum data-rates up to 11Mb/s. However, the highest data-rates are only available to users that experience a good channel quality. More im- portant, the maximum available data-rate to the user also defines the total available radio re- sources in each cell/sector, thus each radio cell/sector can support only a few high data-rate users simultaneously.
One example of a high-data rate service - streaming video of a sports event - requires a channel capacity of at least 256kb/s to provide adequate small screen video quality [30]. The resources required to support a wireless channel with a given bandwidth is proportional to (at least) the square of the channel range. Consequently, a bandwidth of 256kb/s might be avail- able in the close vicinity of the base station, however it will be difficult to support at the cell border. As wireless Internet access increase in popularity, we believed that the demand for high data-rate connections would rapidly exceed the available capacity.
The network capacity can be increased by deploying more base stations. However, such a solution has several disadvantages: First, there is a worldwide scarcity of frequencies suitable for outdoor mobile radio communication. Second, infrastructure equipment for the UMTS ra- dio access network is expensive. Thus, smaller cells increase the cost/bit significantly.
UMTS is an evolving network architecture that is being standardised in several stages. Its capabilities are still being extended. New research intended to enhance UMTS’s capacity for high data-rate services would therefore be of value.
We have focused on a subset of the high data-rate services; group services (i.e., services where the same data is sent to a group of subscribers). We believed that efficient network sup-
port for this resource-greedy service type, would become one of the enablers for a successful future wireless network. During this work there has been an increasing focus on group serv- ices from the research community [46]. There has also been an increasing focus on heteroge- neous wireless networking as a mean to increase the capacity of 3G and beyond networks. In heterogeneous wireless networks the resources needed to transmit high-bandwidth services can be shared among the cooperating network technologies. One example is the Satellite Dig- ital Multimedia Broadcast (SDMB) [86] technology developed in the European IST project MAESTRO [70]. The SDMB system is intended to complement the UMTS network with broadcast capacity for multimedia services.
Multicast is one alternative delivery method for group services. It is used on the Internet for e.g., video conferences, radio and video streaming, and game playing. Its advantages are bandwidth savings over thinner links, and reduced resource consumption in servers. Multicast improves the network's resource consumption by transmitting a packet requested by several users, only once on each link. The first UMTS release allowed a user to join an existing Inter- net group service; however, the network did not support multicast distribution. The service was delivered to the receiver through a point-to-point tunnel between the UMTS gateway and the mobile node. Clearly, this was an inefficient solution wasting limited UMTS networ re- sources.
We have formulated and analysed several schemes and architectures that improves UMTS’s capacity for high data-rate group services.
1.2 Motivation and Research Overview
The path of our work was formed as the research progressed. In the following we describe the motivation and intermediate findings that set the course of our research. This description in- cludes a brief overview of our work. The main contributions are presented in Section 3.2
The research for this thesis has involved several technologies and protocols. We have stud- ied physical layer through to network layer for IEEE 802.11-based [51, 52] ad hoc networks and the infrastructure-based UMTS [2, 48] network. The common theme in all our work has
5 multicast and broadcast traffic in the UMTS network. In this context, we considered it worth- while to study the applicability of the existing IETF IP multicast protocols for MBMS (Paper A). Reuse of IP multicast protocols in UMTS would reduce the complexity in applica- tion gateways, and reduce the time and cost for development of new protocols, as opposed to the design and implementation of new UMTS-specific protocols. We performed an analysis of the simple IP multicast solution provided with UMTS Release-99, and two IP multicast ar- chitectures suggested by us. This work showed that a multicast architecture based on IP mul- ticast mechanisms, could be a possible solution for the evolving MBMS.
In our IP multicast work, we studied multicast transport in the complete UMTS network except the wireless link between the mobile terminal and the base station (the radio cell).
However, the bottleneck in most UMTS network deployment is the capacity of the radio cell.
We have therefore focused on solutions to reduce the use of wireless resources in the radio cell (for multicast traffic), in the remainder of our work.
In Paper B we analysed and compared three different channel types (unicast, broadcast, and sticky-channel broadcast) for multicast distribution in the UTRAN (UMTS Terrestrial Radio Access Network) [6] radio cell. The motivation for this study was the following: It is cost-effective to use a one-to-many (broadcast) channel for multicast distribution in the wire- less cell for densely populated groups; however, the unicast channels utilize the radio resource much more efficiently than a broadcast channel. A broadcast channel has to be robust enough to reach all the multicast receivers. The resource cost is defined by the multicast receiver which at any instant experiences the worst channel quality. This robustness requires much wireless resources. Neither are fast power adjustments nor packet scheduling based on chan- nel quality available for a broadcast channel in contrast to a unicast channel. Thus it is best to choose wireless unicast to each of the multicast members in sparsely populated groups.
As a third alternative to existing unicast and broadcast, we suggested a physical channel type named sticky-channel where the mobile multicast terminal in a wide cell-border region
“sticks” to a broadcast channel from the neighbouring cell. This channel was based on the ob- servation that during resource planning of the UMTS network it is recommended to build your network such that a terminal is covered by two or more base stations in at least 40% of its con- nection time (e.g., [59]). The purpose of the sticky-channel was to reduce the total wireless resource consumption in a given region by eliminating the need for multicast transmission from a subset of all base stations deployed to serve the region. The sticky-channel showed a marginal reduction in wireless resources for sparsely populated multicast groups compared
with the broadcast and unicast options.
To further reduce the UTRAN radio resources needed to distribute high-bandwidth group services, we identified heterogeneous wireless networking as one feasible method. In our opinion, the 4th generation (4G) of mobile networks will most likely consist of a multitude of wireless standards that cooperate to form the 4G radio access network.
In Paper C we suggested a hetero- geneous multihop wireless access network for multicast traffic. In a heterogeneous wireless access net- work, the cost to distribute a high- bandwidth group service can be shared among the cooperating tech- nologies, e.g., the range of a UMTS radio channel can be reduced and lo- cal IEEE 802.11-based Mobile Ad Hoc Networks (MANETs) [25] can be used to forward the data to users located outside the reduced UMTS channel (see Figure 1 for an exam- ple). Since the path-loss on the radio channel is proportional to the nth
power of distance where n ranges between 2 and 4 [82], a reduction in the channel range can free a significant amount of UTRAN radio resources, and thus increase the network capacity.
When we started our work with the heterogeneous wireless access network, MANETs was becoming adequately mature, and mobile terminals with both IEEE 802.11 and UTRAN transceivers were readily available. Thus a combination of 3G cellular networks and IEEE 802.11-based MANETs was a feasible and easy-to-deploy architecture.
Mobile Ad Hoc Networks (MANETs) [25] operate independently of a fixed or preplanned infrastructure. The networks are autonomous and may be isolated, or interconnected to other networks through gateways. Each node in a MANET is also a router. A stand-alone routing
3G Base station
3G Radio cell
Figure 1: This figure shows a heterogeneous wireless access network. The range of the UMTS broadcast channel has been reduced to cover the small grey area, and MANETs are used to forward the multicast data to terminals in the remaining area of the radio cell.
7 to handle rapid route changes.
In Paper D we sketched two multicast routing protocols for the heterogeneous multihop ac- cess network; one distributed protocol with some central support and one fully centralised pro- tocol. The distributed protocol is described in detail in Research Report G. We chose to design new multicast protocols for our heterogeneous architecture to allow for efficient exploitation of the available centralised infrastructure (UMTS). The other option was to modify existing MANET multicast protocols. Some central support improves the efficiency of MANET mul- ticast routing. Our choice allowed us to build a distributed routing protocol based on (what we believed to be) the best components from several popular MANET protocols and introduce some central support to this design.
Encouraging results from the preliminary analysis of the heterogeneous wireless access network performed in Paper C and Paper D motivated for a detailed analysis of the architec- ture and the distributed multicast protocol (Research Report G). The analysis is presented in Paper E.
Traditionally the telecommunication industry has had a high focus on network reliability and quality of service (QoS) whereas best-effort data networks rely on redundant network ca- pacity to support some service quality. In resent years QoS mechanisms has become available for data networks as well, however large differences still exists between different network types. UMTS is a reliable network with efficient QoS mechanisms, whereas the MANETs are unreliable best-effort networks. Thus an important aspect of our detailed analyses of the het- erogeneous wireless access network has been to study the service quality in the heterogeneous multihop network in comparison with the standard, reliable, one-hop, wireless UTRAN chan- nel. We used this analysis to identify the maximum MANET size (and thus shortest UTRAN channel range) that provided an acceptable service quality. The heterogeneous architecture al- lowed a reduction of the UTRAN broadcast channel to approximately 45% of the cell range.
During our work with the heterogeneous wireless access network, we observed that most packet-loss was loss of single packets or short sequences of two or three packets. This led us to believe that forward error correction (FEC) used as an erasure code on the multicast packets could improve the performance of the heterogeneous network. This could allow larger MA- NETs and therefore, a further reduction of the range of the UMTS multicast radio channel (and consequently also a reduction in the required radio resources).
In packet-level FEC (FEC as an erasure code), a number of redundant packets are generated for each block of data packets. The redundant packets are used at the receiver to regenerate a
number of lost packets. Thus a FEC encoded multicast stream can be transmitted on a path with a higher packet loss ratio. Consequently, FEC could allow longer ad hoc paths and thus shorter UMTS channel range in our heterogeneous architecture. An analysis of multicast with FEC in the heterogeneous wireless access network showed some throughput improvement, but at a very high bandwidth cost (Paper F).
1.3 Thesis Outline
The thesis is organized in two parts. Part I is an introduction to the areas of which our work depends, and to the areas where the thesis contributes, whereas Part II consist of a set of pub- lished articles that presents the results of our research.
Part I
After a brief introduction that describes the background, motivation and outline of the thesis, chapter 2 gives an overview and presents related work of the research fields coved by our work. Chapter 3 describes our research methods, a summary of the main contributions and gives a short discussion of the work.
The list of figures and the list of terms and acronyms given in the beginning of the thesis are restricted to Part I. Likewise, since each article includes a reference list, the reference list found at the end of Part I, is exclusive to this part of the thesis.
Part II
Part II consists of the following six research papers and one research report:
• Multicast in 3G Networks: Employment of Existing IP Multicast Protocols in UMTS
• Sticky Point-to-multipoint Channel For Multicast in UMTS
• Multicast Service Availability in a Hybrid 3G-cellular and Ad Hoc Network
• Multicast-service Distribution on a Cellular Network Assisted by Local Ad Hoc Networks
• A Heterogeneous Cellular and Ad Hoc Network Architecture for Multipoint Streaming:
A detailed performance analysis
9
2 Overview and Related Work
This chapter presents an overview of the research areas covered by this thesis. The purpose is not to give a comprehensive overview of the different areas, but to provide necessary back- ground information, and describe important work related to our research.
The basics of IP multicast are presented in Section 2.1. Multicast is a common component in all our work, and the two multicast architectures for UMTS that we have suggested and an- alysed were based on IP multicast mechanisms. In Section 2.2 we present the Multimedia Broadcast/Multicast Service (MBMS) [3] for UMTS; MBMS is the current multicast archi- tecture for UMTS. Section 2.3 gives an overview of multicast routing for Mobile Ad Hoc Net- works (MANETs). MANET multicast mechanisms are used in the multicast protocols we have suggested for our heterogeneous wireless access network. The area of multihop and het- erogeneous wireless access networking for 3G and beyond is covered in Section 2.4. We have also studied packet-level forward error correction (FEC) for multicast on the heterogeneous wireless architecture; section 2.5 describes the use of packet-level FEC in wireless networks.
2.1 Internet Protocol (IP) Multicast
Multicast distribution over the Internet is based on the model introduced by Stephen Deering [27]. It is intended for one-to-many, few-to-many and many-to-many communica- tion. Multicast improves the network's bandwidth budget by transmitting a packet requested by several users only once on each link. Consequently its advantages are bandwidth savings over thinner links, and reduced resource consumption in servers.
Multicast sessions use a particular class of IP addresses, class D. Originally the portion of the address range that was intended for global multicast groups, was an unregulated and flat address space. Thus any multicast group could ask for any multicast address, which might re- sult in address collisions between groups. A portion of this range has later been assigned to GLOP addressing [71]; each Autonomous System (AS) is given a short range of static global multicast addresses in the GLOP address space. The Multicast Address-Set Claim (MASC) Protocol [80] provides one suggestion for how to handle global dynamic multicast address al- location for the remaining range, however this mechanism is not widely used on the Internet.
In the IP multicast model, sources need not be members of the multicast group, and can dynamically join or leave sessions. The multicast receivers can also dynamically join or leave
a session. The receivers do not need to know the sources in the session, and likewise, the sources do not need to know the receivers in the session.
Typically, nodes that want to join a multicast session inform the local router of this intent via the Internet Group Management Protocol (IGMP) [19], or Multicast Listener Discovery (MLD) [96]. Local routers that serve multicast members, join the multicast distribution tree maintained by a multicast routing protocol. Interdomain multicast routing is most commonly handled by the Multicast Border Gateway Protocol (MBGP) [13], with additional support from the Multicast Source Discovery Protocol (MSDP) [32] for shared distribution tree pro- tocols. The multicast routing protocols for intradomain routing can be classified into three groups:
• Shared distribution tree protocols
• Source specific tree protocols
• Stateless multicast.
Shared Distribution Tree Protocols
In shared tree multicast routing protocols, all sources for one multicast session use the same distri- bution tree. A core node is selected to root the multi- cast tree for a multicast session (Figure 2). New multicast members join the multicast tree by sending a join message towards the root of the common tree, and are subsequently attached to the tree. Using a shared multicast tree has the disadvantage that pack- ets are distributed to the multicast group along paths that can be much longer than the shortest paths from sources to receivers. The advantage is that routers only need to maintain one state object for each multi- cast group, and signalling traffic is required to main-
tain only one tree. Shared distribution tree protocols are also referred to as any source multicast (ASM).
S1
C S2
Figure 2: The figure shows shared tree routing. Each source (S1 and S2) sends the packets to the core node (C) which in turn forwards the data onto the multicast tree.
11 wards the data on the multicast tree. CBT maintains bidirectional trees; thus source data from a multicast member are distributed on the tree directly by the source. PIM-SM builds a unidi- rectional tree from the core to the multicast members. In PIM-SM, a new source always sends the encapsulated multicast packet to the core (Rendezvous Point), which in turn forwards the data on the multicast tree. Next, the core router performs a source specific join towards the source, to attach the source node to the distribution tree and avoid the encapsulation and (pos- sibly) inefficient paths. PIM-SM also allows receivers to switch to a source-based shortest path tree.
PIM-SM maintains temporary multicast state information (softstate) in the routers. The softstate is refreshed with periodic join messages addressed to the core node, from the routers that serve multicast members. CBT keeps hardstate information that is maintained with ac- knowledged join-requests and quit-requests. The shared multicast tree model is most useful in a few-to-many scenario for sparse member distributions.
A variant of PIM-SM, called Bi-directional Protocol Independent Multicast (BIDIR- PIM) [37], is being specified, this protocol is intended for many-to-many scenarios.
Source Specific Distribution Tree Protocols The alternative to shared trees is to build source specific trees from each source (Figure 3). A source specific tree trades complexity in the form of a large state space in routers and a larger number of links, for an efficient shortest path distribu- tion tree for the multicast data. Source Spe- cific Multicast (SSM) [47, 17] represents this routing type. SSM is in reality the source specific parts of PIM-SM [33].
These protocols are also referred to as sin- gle source multicast (SSM). SSM is most useful for one-to-many scenarios for sparse member distributions.
A different type of source specific tree multicast protocols is represented with Protocol In- dependent Multicast-Dense Mode (PIM-DM) [7]. This protocol type is intended for groups S2 S1
Figure 3: The figure pictures source specific multicast routing. One multicast tree is estab- lished for each source (S1 and S2). The red nodes are multicast members.
with high multicast member density. In PIM-DM, multicast sources periodically flood the multicast data in a given domain. Routers which are not interested in the multicast data explic- itly prune their branch of the distribution tree. Due to the periodic flooding, these protocols are not efficient for sparse multicast groups, and do not scale well with increasing group size.
Stateless Multicast
Stateless multicast is a different approach to multicast distribution. This protocol type does not maintain the multicast group states in the routers. The addresses (or some coded address) of all receivers must be present in the header of a stateless multicast data packet. Upon recep- tion of a multicast packet, the router consults its unicast protocol and chooses the correct net- work interface for the next hop towards each of the receivers. The packet is replicated, and the address list updated when different next-hop nodes are required to reach all the receivers.
Obviously this type of multicast does not scale well with increasing group size; however it, scales very well with increasing number of small multicast groups. Stateless multicast must be explicitly supported by all routers the multicast packet passes on its way to the destinations;
this is the main disadvantage with this protocol type. This protocol type is therefore most use- ful when the multicast source is connected to the rest of the network via narrow-bandwidth links. In this case only the narrow-bandwidth routers must support stateless multicast. The multicast packet is expanded to multiple unicast in a gateway between the narrow-band net- work and the rest of the network.
The IETF draft “Explicit Multicast (Xcast) Basic Specifications” [18] describes the general operation of this type of protocol. Differential Destination Multicast (DDM) [55] is an exam- ple of an Xcast protocol.
2.2 UMTS Multimedia Broadcast/Multicast Service
In the first UMTS release, multicast support in the UMTS standard was an optional solution that provided access to a multicast service by means of unicast tunnelling. The IP multicast routing was terminated in the GGSN (Gateway GPRS Support Node) between UMTS and the
13 mobile terminal to access an existing multicast service on the Internet, but did not exploit the potential network resource gain associated with multicast routing.
The Multimedia Broadcast/Multicast Service (MBMS) [3, 104] was introduced in the UMTS standard (Release-6) to improve the efficiency of group communication in UMTS. Our work presented in [43] and [45] suggested possible solutions to some parts of the MBMS ar- chitecture. The final MBMS design is split into the MBMS Bearer Service and the MBMS User Service.
The MBMS Bearer Service
The MBMS Bearer Service includes a Multicast and a Broadcast Mode. The advantage of the MBMS Bearer Service compared to the original UMTS bearer services is that a multicast rout- ing mechanism is introduced. One MBMS packet flow is replicated (when needed) by the UMTS network routing nodes: GGSN (Gateway GPRS Support Node), SGSN (Serving GPRS Support Node) and RNCs (Radio Network Controller) (ref. Figure 4).
In MBMS each multicast group is identified by a multicast IP address and an Access Point Name (APN). The APN represents a specific GGSN, and is set as the source of the data pack- ets for the multicast group. In contrary to IP multicast, MBMS allow only one known source for each group. Also, unknown multicast members are not allowed in MBMS; a User Equip- ment (UE) must register a join with the Broadcast Multicast - Service Center (BM-SC) to join a multicast group. This modified multicast model, where the source and all the receivers are
RNC
RNC UE
UE UE
SGSN GGSN
HLR, AuC,
Node B
BM-SC
SGSN Node B
UTRAN CN
Internet EIR, CGF
Figure 4: This figure shows the UMTS (Universal Mobile Telecommunications System) elements participating in the MBMS architecture. CN (Core Network) is a high capacity backbone network, while UTRAN (UMTS Terrestrial Radio Access Network) incorporates the low capacity radio links.
known, eases the mechanisms for security and the mechanisms for source and receiver charg- ing. The MBMS architecture addresses to some extent the multicast deployment problem is- sues raised in [28].
MBMS uses a query-and-response mechanism similar to unsolicited join and leave of IGMP [19], both for group management and for establishment of multicast forwarding trees.
A comparison between the MBMS mechanism and IGMP can be found in [103]. When a user equipment wants to join a multicast group, it sends a join to the GGSN, which in turn verifies with the BM-SC whether this user is allowed to join. The GGSN receives the address of the APN that administers the multicast group, from the BM-SC. A positive acknowledge to this join initiates a sequence of MBMS signalling messages. These messages create/modify the MBMS Bearer Context (MBC) state in all UMTS nodes on the path between the mobile ter- minal (UE) and the APN for the multicast group. The MBC stores (among other parameters) the multicast IP address, and the downlink interfaces that serve multicast members.
When a mobile multicast member wants to leave the multicast group, the mobile terminal (UE) sends a leave message to the GGSN. This message unsubscribes the user from the mul- ticast group, and removes the multicast state associated with this user in the network nodes.
When a mobile multicast member performs a handover to a new base station, this member must be associated with a new link in the multicast tree. The standard UMTS signalling mes- sages that support node mobility have been augmented to include information to support mul- ticast tree maintenance.
MBMS creates a standard multicast forwarding tree to distribute the multicast data in the Core Network and part of the radio network (UTRAN). The multicast tree spans the GGSNs, SGSNs and the RNCs.
The method for multicast data distribution from the RNCs via the base stations (Node-B) to the mobile user equipment, is selected based on the number of multicast subscribers asso- ciated with each radio cell/sector. If there are few members located in a cell/sector, a normal point-to-point unicast connection is setup between the RNC and the user equipment. Other- wise a common path is established between the RNC and the base station, and a broadcast channel is allocated for the wireless link to the mobile terminal (UE).
MBMS may use an advanced counting scheme to decide the approximate number of mul-
15 The Forward Access Channel (FACH) was selected to be the common point-to-multipoint wireless channel in the MBMS RAN (Radio Access Network) [5, 77]. FACH uses soft-com- bining and selective-combining to improve the reliability of the data reception and thus allow a reduction in the transmission power for the broadcast channel. Selective- and soft-combin- ing will both combine the broadcast transmissions from adjacent base stations. Soft-combin- ing is used to combine received power before channel decoding while selective-combining decodes the signal from each base station independently and compares the results before it chooses the one that has the highest probability of being correct.
The MBMS User Service
The MBMS User Service is basically the MBMS Service Layer. It offers a streaming and a download delivery method. The Streaming Delivery method can be used for continuous trans- missions like Mobile TV services. The Download Method is intended for “Download and Play” services. To increase the transmission reliability, an application layer FEC code may be used. Further, a file repair service may be offered to complement the download delivery meth- od.
2.3 Multicast for Mobile Ad Hoc Networks (MANETs)
A Mobile Ad Hoc Network (MANET) [25] is a multihop wireless network. It is a self-config- uring network of mobile routers (and associated hosts) connected by wireless links. The rout- ers are free to move randomly and organise themselves arbitrarily. The network's wireless topology may therefore change rapidly and unpredictably. Such a network may operate in a stand alone fashion, or it may be connected to the Internet.
The tree reorganization in MANETs is more frequent than in conventional wired networks, since the multicast protocols have to respond to network dynamics in addition to group dy- namics. Consequently, multicast protocols designed for fixed networks do not support the dy- namics of MANETs very well. The multicast protocols suggested specifically for MANETs can be classified in four categories [24]: Tree-based protocols, meshed-based protocols, hy- brid protocols, and stateless multicast. In addition to these four types, we include multicast by means of broadcast in our discussion. Geographic multicast protocols have emerged as a sixth category; however, since we did not consider geographic multicast for our work, these proto- cols are therefore not included in this introduction. Neither did we study energy-efficient pro-
tocols, nor multicast protocols that attempt to provide quality of service guarantees.
The tree-based protocols are based on the IP multicast protocols for fixed networks. These protocols strive to create an optimal multicast distribution tree where the multicast data is dis- tributed to all members with a minimum number of link broadcasts. These protocols are de- signed to handle some mobility; however, as the node mobility increases, the multicast throughput decreases (and the signalling traffic increases). A basic tree-based protocol is not able to repair broken links quickly enough in a highly mobile network.
Mesh-based protocols were introduced to increase the multicast distribution trees’ robust- ness to node mobility. These protocols introduce some redundancy in the multicast distribu- tion tree; when a link is broken in a mesh tree, the multicast data will (in many cases) continue to flow on a redundant link. This allows the protocol to continue forwarding multicast data while the broken link is being repaired. Clearly the multicast distribution is not optimal on a mesh since the data might travel on parallel paths to the multicast members; however, this in- efficiency is traded for better multicast throughput in highly mobile networks.
The hybrid multicast protocols attempt to get the most out of both the tree-based and the mesh-based protocols by combining the two.
In multicast by means of broadcast (flooding), multicast data is distributed with flooding.
In this case there is no need for a multicast routing protocol to maintain a multicast distribution tree, thus there is no signalling overhead. However, there will clearly be an overhead due to a high number of redundant packet transmissions; this redundancy is reduced as the density of multicast members increase. The method is very robust for mobility (it represents a fully re- dundant mesh).
Stateless multicast make use of the unicast routing protocol, thus the unicast protocol’s ro- bustness to node mobility is important for the performance of this multicast type. No multicast signalling is required, but all addresses of the multicast members must be listed in the header of each data packet. Stateless multicast is therefore efficient only for small multicast groups.
2.3.1 Tree-based Multicast Routing Protocols
Tree-based multicast is the traditional multicast forwarding mechanism used in fixed net-
17 rary softstates.
We have chosen to briefly describe the following tree-based multicast protocols:
• AMRIS [99] was one of the first stand-alone MANET multicast protocols. It uses ID num- bers to identify a node’s position in the tree hierarchy and consequently avoid routing loops.
• MAODV [85] and MOLSR [60] are multicast extensions to two popular unicast routing protocols. MAODV was also one of the first MANET protocols, it introduced sequence numbers to avoid routing loops. MOLSR exploits the efficient proactive routing mecha- nisms in OLSR [23].
• ADMR [54] gets the most out of passive signalling; it uses all overheard traffic to maintain multicast routing information, thus this is a protocol with low signalling overhead.
• ABAM [93] is an example of a protocol that uses a criteria different from the shortest path to establish the multicast tree. ABAM performs well i highly mobile networks because it chooses to route the multicast data over stable routing paths (paths between nodes with lit- tle mobility).
• ACMRP [76] is a tree-based protocol with a loose tree structure, it paves the way for a dis- cussion of tree-based versus mesh-based protocols.
Ad hoc Multicast Routing Protocol Utilizing Increasing Id-numbers (AMRIS) [99]
This is one of the first stand-alone MANET multicast protocols. AMRIS constructs a common distribution tree for all sources in a group. The tree construction is initiated by a message from an elected main source. This message is flooded to all nodes in the network, and it assigns an id number to each node; the id number indicates the node’s level in a forwarding tree. Multi- cast members reply with a unicast join request to the neighbour with the lowest id number. In this way, the join request propagates along the reverse path towards the multicast tree. Each network node sends a periodic one-hop message to announce its presence and current id number for all active multicast groups. Broken links are detected based on this message: The downlink node (with highest id number) performs a local link repair, where the id number is used to avoid routing loops. Multicast state information times out based on missing neighbour messages.
This protocol does not do any refresh of the distribution tree; after a sequence of link re- pairs, the forwarding tree might be less optimal. Neither does the protocol specify how to han- dle partition and reunion of the tree, or how to elect the main source.
Multicast Ad-hoc On-demand Distance Vector (MAODV) [85]
MAODV is an extension to the popular unicast AODV [79], and uses AODV’s route discov- ery mechanisms to find a path to the multicast distribution tree. One common multicast distri- bution tree is maintained for each active multicast group. A node that wants to join a multicast group floods a route-request (unicast can be used if the node has a route to the group), and on- tree group members reply to the request along the reverse path of the route request. Eventually the joining node activates one, of possibly many, replies. The first multicast member becomes the leader of the group, and periodically floods a group-hello message to maintain the for- warding tree.
All nodes monitor the radio channel for neighbour traffic and thus detect lost neighbours (links) within a timeout period. The node downstream of the break attempts a link repair with a range limited flood of the route-request message. The node upstream of the break waits some time for a possible reconnection before it removes the state information associated with the downlink node, and performs a tree prune in case it is now a non-member leaf node. MAODV has mechanisms to handle partition and reunion of the multicast tree.
Multicast Optimized Link State Routing (MOLSR) [60]
MOLSR is a suggested extension to the popular proactive unicast protocol, OLSR [23]. This protocol maintains one tree for each source (source-specific trees), and the tree formation is initiated by the source with a flood of the source-claim message. Note that the flooding is done by the OLSR Multipoint Relays (MPRs), and is thus less resource consuming than basic flood- ing. Multicast members respond to the source-claim with a one-hop parent-claim message.
The message follows the path to the source as specified in the routing table, but it does not necessarily follow the reverse path of the source-claim.
Periodic floods of the source-claim message with confirm-parent responses are used to maintain the forwarding tree. In addition, changes in the unicast topology can trigger changes in the multicast routing tree. If any node on the tree detects a change in the next hop towards a multicast source, it joins the new hop and may leave the previous parent (otherwise a soft- state mechanism will eventually remove the old link).
There is no need for local multicast link repair since the unicast protocol will find an alter-
19 vantage is a more robust protocol in highly mobile networks.
Adaptive Demand-Driven Multicast Routing Protocol (ADMR) [54]
ADMR attempts to reduce the periodic active signalling traffic to a minimum. This protocol maintains a distribution tree for each source; the source starts the establishment of the multi- cast tree by flooding the first multicast packet (including an ADMR header) on the network.
Multicast members respond with a join message on the reverse path to establish the tree. Sub- sequent multicast members attach to the tree with a flooded multicast solicitation message, wait for a response and validate one of the response messages in a three-way-handshake.
ADMR monitors the traffic pattern of the multicast stream. Based on that, the protocol can detect link breaks in the tree, as well as sources that have become inactive, and branches which are no longer needed. A limited number of “keep-alive” packets are transmitted in temporary breaks in the source data. The downlink node of a broken link attempts a link repair with a flooded reconnect message, and the source responds with a reply. If receivers experience fre- quent link breaks, the source is informed, and the source floods a few multicast data packets to start a refresh of the multicast forwarding tree.
Associativity-Based Multicast Routing (ABAM) [93]
ABAM creates source-specific trees where the trees are constructed based on link stability rather than hop distance. Each node keeps track of the link stability to each of its neighbours by registering the reliability of periodic one-hop beacons. A three-way handshake is used to create a multicast tree. Each source floods the network with a multicast query; nodes receiving the query will append the link stability, signal strength, power life, etc., to the query message and subsequently rebroadcast the message. Multicast receivers chooses the multicast query that has traversed the most stable route and unicast a reply on this path. Finally the source val- idates the tree by sending a setup message along the paths of the multicast tree.
Local repair is used to maintain the tree. The repair can be either a branch repair, a sub-tree repair or a full tree repair (in case the source node loses its connection to the rest of the three).
All repairs are performed with a three-way handshake in a query-reply-validate sequence.
This protocol achieves a high throughput in mobile networks since it chooses stable links for the forwarding tree. The disadvantage is a lower multicast efficiency due to larger paths.
There is also the risk that the most stable paths become congested since all sources and groups tend to choose the same paths.
The Adaptive Core Multicast Routing Protocol (ACMRP) [76]
ACMRP is a shared tree protocol. The tree establishment is initiated by the source, and it uses a periodic request (flooding) - reply, strategy to maintain the distribution tree. In this protocol there is one dynamic core, which is responsible for the formation and maintenance of the for- warding tree. One common tree is used by all the sources in a multicast group.
All nodes on the network keep a table of the current core for each group. The first source of a group takes the role as the core. Periodically this role is migrated to a node closer to the center of the multicast network, to improve the efficiency of the common multicast distribu- tion tree compared to source-based trees. The core initiates a limited link state signalling se- quence to identify a node closer to the center of the group that should take over the core role.
Thus the core role converges towards the best location in the group.
The authors classify this protocol as mesh-based; however, there is no explicit formation of redundant links in the multicast distribution tree. The broadcast nature of a radio network with a common channel is exploited to provide some redundancy. A node on the forwarding tree accepts new multicast packets from any of its neighbours. In tree-based protocols on fixed networks, a node accepts a packet only from its defined uplink to avoid loops. When a MAN- ET node accepts a packet from any of its links, it will receive a duplicate copy of the multicast data packet in the cases when there are two or more branches of the multicast distribution tree within radio range of each other. This redundancy can be exploited to improve throughput if each multicast packet can be uniquely identified, and each node keeps a history (cache) of re- ceived data packets. Several tree-based multicast protocols exploit this redundancy.
2.3.2 Mesh-based Multicast Routing Protocols
The mesh-based protocols provide richer connectivity compared with tree-based structures.
Some level of redundancy is added to the forwarding trees, thus these trees will in many cases have an alternative path to bypass a broken link. These protocols trade low overhead and ef- ficient multicast routing for better connectivity (and thus throughput). The relatively large overhead in the mesh protocols consists of signalling to create and maintain the mesh, and re- dundant data packets. Mesh-based mechanisms can be source initiated or receiver initiated,
21
• CAMP [34] is an efficient mesh protocol with little signalling overhead. It uses a common tree to reduce the signalling traffic, and is developed from the well known CBT [12] pro- tocol for fixed networks.
• ODMRP [61] is very robust in highly mobile networks. This protocol has shown high throughput in several performance studies (e.g., [62]). The protocol has a high overhead, therefore we also present DCMP [26], which is an extension to ODMRP, with reduced overhead.
The Core-Assisted Mesh Protocol (CAMP) [34]
CAMP extends the operation of the Core-Based Tree (CBT) [12] protocol with mesh func- tionality for wireless mobile networks. The protocol depends on an underlaying proactive link state unicast protocol, and this is one of the reasons why it has little signalling overhead.
CAMP establishes a common mesh for all sources in the multicast group. The protocol is re- ceiver initiated in the sense that multicast members unicast a join towards the core to connect to the multicast tree. The address of one (or several) core(s) is distributed in group member- ship reports. If no core is known, the receiver floods the join to all nodes in the network; a node that already is a multicast member can respond to the join and create a path to the mesh.
Each multicast member continuously consults the unicast routing table to check if the mul- ticast packets arrive from its neighbour that is on the reverse path towards the source. If not, then the multicast member sends a message on the shortest path towards the source to include this path in the mesh. The new path will be part of the common tree that is used by all sources, thus the number of sources, and their locations, define the level of redundancy in the network.
Old links in the mesh are removed upon a timeout.
Mesh maintenance is handled by the underlaying unicast protocol’s modification of the path towards the source. Members leave the multicast tree with a quit notification message.
The role of the core is to reduce the network signalling and to provide a first/redundant path to the mesh. The protocol has mechanisms to handle mesh partition and reunion. The core does not need not be a multicast member.
The On-Demand Multicast Routing Protocol (ODMRP) [61]
This is a popular mesh protocol. It is a stand-alone protocol that does not require underlying unicast routing. One common mesh is formed for each multicast group. Each source establish- es a source specific forwarding tree by flooding a join-query to all nodes in the network. Mul-
ticast members respond with a reply. The resulting mesh is the union of all the source specific forwarding trees, thus the level of redundancy in the mesh is dependant on the number of sources and their location relative to the receivers. Each source periodically floods a join-que- ry to refresh the mesh; thus group membership and forwarding state is maintained through softstate. Members do not send an explicit leave when they want to leave the multicast group, in stead the connection is left to timeout. If a link break is detected, a local temporary repair is performed until the next flooding of the join-query establishes a new tree.
This protocol provides good connectivity, and consequently good throughput, in highly mobile networks at the cost of a high signalling load and some redundant data transmission.
Due to the periodic flood of the join-query from each source, the signalling load is high. To reduce this load, the protocol provides an extension for passive clustering (similar to MPRs in OLSR [23]) to reduce the flooding overhead.
To further reduce the signalling overhead, the Dynamic Core Based Multicast Routing Pro- tocol (DCMP) [26] has been proposed. DCMP is ODMRP with some modifications. The ba- sic operation of ODMRP is kept, and in addition DCMP introduces some signalling to organize the group sources in three categories: active sources, core active sources and passive sources. The active sources behave like ODMRP sources, and the core active sources operate as ODMRP sources for nearby passive sources. Thus in situations with many sources, this pro- tocol variant reduces the level of redundancy in the group mesh, and consequently the over- head is reduced. An active source is allowed to be core for at most a defined number of passive sources, and a passive source is allowed to be at most a defined number of hops away from the core source. The number of active sources in the group, and thus the level of redundancy, can be adjusted with those two constants.
2.3.3 Hybrid Tree-based and Mesh-based Protocols
The tree-based multicast protocols provide high data forwarding efficiency at the expense of low robustness, whereas mesh-based multicast protocols provide better robustness at the ex- pense of higher forwarding overhead and increased network load. Thus, there is a possibility that a hybrid multicast solution may achieve better performance by combining the advantages
