Luận văn Efficient core selection for multicast routing in mobile ad hoc networks

HANOI NATIONAL UNIVERSITY UNIVERSITY OF TECHNOLOGY AND ENGINEERING Binh Minh Nguyen EFFICIENT CORE SELECTION FOR MULTICAST ROUTING IN MOBILE AD HOC NETWORKS  GRADUATION THESIS Faculty of Information Technology HA NOI - 2010 HA NOI - 2010 HANOI NATIONAL UNIVERSITY UNIVERSITY OF TECHNOLOGY AND ENGINEERING Binh Minh Nguyen EFFICIENT CORE SELECTION FOR MULTICAST ROUTING IN MOBILE AD HOC NETWORKS  GRADUATION THESIS Faculty of Information Technology Supervisor: Dr. Dai Tho Nguyen HA NOI - 2010 ABSTRACT There are many multicast routing protocols that use the notion of group-shared trees, for example: Protocol Independent Multicast (PIM), Core-Based Tree. As constructing of a minimal-cost spanning tree to all members of the network is nearly impossible due to its excessive cost in terms of convergence time and network overhead, the core-based approach is chosen as a heuristic method to cope with multicast routing. The core node, which is also referred as center node or rendezvous point, is chosen from a selective group by different algorithm. However, most of protocols for core election in static networks are not suitable for mobile ad hoc network, since these algorithms require the knowledge of the whole network, the total number of nodes participating, the network topology, link state,.. Which are not available or too expensive to acquire in mobile ad hoc networks. There are many proposed protocol for multicast routing in mobile ad hoc networks, such as PUMA, ODMRP or MAODV. In those protocols, PUMA (Protocol for unified multicasting through announcements) has shown to outperform others. PUMA uses a single multicast announcement to establish and maintain the mesh. However, there is still a serious drawback, PUMA elects core by selecting the node with the highest ID and the core remains fixed afterwards. In this thesis, we present an improvement of PUMA by integrating an adaptive core selection mechanism into it. The result show that the new PUMA achieves higher packet delivery ratios, lower delivery times than the old one, while incurring only a little control overhead increment. ACKNOWLEDGMENT This thesis would not have been possible without the support of many people. Firstly, I am heartily thankful to my supervisor, Dr. Dai Tho Nguyen, whose encouragement, guidance and support from the initial to the final step enabled me to develop a throughout understanding of the subject. I also would like to convey my thanks to the University of Technology and Engineering - Hanoi National University for providing me the knowledge and experience in these four years. Lastly, I offer my regards and gratitude to all of those who supported me in any respect during my studies. Binh Minh Nguyen Hanoi, May 2010 TABLE OF CONTENT TABLE OF FIGURES Figure 1: Multicast 5 Figure 2: Multicast group 7 Figure 3: Connectivity List 20 Figure 4: Mesh Creation 23 Figure 5: Multicast tree 33 Figure 6: Core Migration 41 Figure 7: Control overhead x Senders 46 Figure 8: Control overhead x Traffic Load 47 Figure 9: Packet loss ratio x Senders 48 Figure 10: Packet loss ratio x Traffic Load 48 Figure 11: Delivery time x Content Size 49 Figure 12: Delivery time x Number of concurrent requesting nodes 50 Figure 13: Delivery time x Mobility 51 TABLE OF ABBREVIATIONS ADMR Adaptive Demand-driven Multicast Routing BGP Border Gateway Protocol CBT Core-based Tree DM Dense Mode DVMRP Distance Vector Multicast Routing Protocol ICMP Internet Control Message Protocol IGMP Internet Grouping Management Protocol IOS Internetwork Operating System IP Internet Protocol LAN Local Area Network LSA Link-State Advertisement MANET Mobile Ad Hoc Networks MAODV Multicast Ad hoc On Demand Distance Vector MOSPF Multicast Open Shortest Path First MRT Maximum Response Time NS Network Simulator ODMRP On Demand Multicast Routing Protocol OSPF Open Shortest Path First OTcl Object-oriented Tool Command Language P2MAN Peer-to-MANET PIM Protocol Independent Multicast PUMA Protocol for unified multicasting through announcement RFC Requests for Comments RPF Reverse Path Forwarding SM Sparse Mode SPF Shortest Path First SPT Shortest Path Tree TTL Time to Live CHAPTER 1: INTRODUCTION 1.1 Overview Multipoint communications have been existed for quite a long time. According to researches, the idea of one or more nodes sending data packet to many receivers simultaneously has been available since at least the early of 1980. The term multicasting only became widely known after Deering established the first internet request-for-comments on the field (aka RFC). [4] After being proposed by Deering as the model to be followed by groups of users or computers to communicate among themselves simultaneously, IP Multicasting has been developed. Since then, a world-wide multicast backbone testbed also known as MBONE has been constructed to test many protocols and applications. Multicast communication has been implemented for a large number of applications. Some of these applications are video-conferencing, whiteboard, group communication tools, and software and information distribution. Initially, almost all of these applications were being used in intranets or in MBONE, and now, there are some Internet service providers providing supports for these multicast applications in their backbone. 1.2 Problem’s description However, most of the research and development being done so far only consider physically connected networks, where devices are connected together by the use of cables and wires. Due to the wired connections among them, the locations of nodes are fixed and the only dynamic aspect in the networks is node and link failures. Wireless networks are a very attractive and promising way of computing due to computer and infrastructure devices and computers are not cabled together. These networks constitute an environment where everyone is free to move beyond the scope of his place. He can take his devices such as computer, cell phone to anywhere and still be able to communicate, exchange information with his colleagues. The core of the thesis’s approach and contribution is multicasting over wireless network, which consists of enabling the propagation of multicast data packets over connected meshes. Multicasting over meshes is a significant departure for multicasting over mobile ad hoc network. Meshes have a high tolerance toward faults of node or link failures. Moreover, the algorithm used to build meshes is rather simpler and easy to deploy. Among most representative multicast routing protocols, PUMA [5] has shown to be the most stable and efficient protocol due to its performance compare with other protocols such as MAODV or ADMR [10] … The most noticeable aspect of PUMA is that it uses a very simple and effective method to establish and maintain the mesh, this results in a low control overhead. PUMA uses a single control message, a multicast announcement to be precise, to maintain the mesh. All transmissions are broadcast and no unicast protocol is needed. PUMA uses a core-based approach to build the mesh. However, the method of selecting core in PUMA has a serious drawback: PUMA selects the node with the highest core id to become the core of the multicast group. Furthermore, core changes only happen when the mesh undergoes partition or the old core leaves the mesh. In this thesis, we will concentrate on improving PUMA in two aspects: Firstly, create a function to determine which nodes should be the core node of the multicast group. The core node should be able to reach every receiving node as quickly as possible. Secondly, due to the mobility of the mobile ad hoc networks, the core node could malfunction unexpectedly and no longer fit to be the core of the group. As a result, a core change to cope with these exceptions should be implemented. Inspired by the idea of core selection from [9], we propose an improvement of PUMA with an adaptive core selection mechanism our own algorithm. Our work has made PUMA perform approximately twenty percent better in term of delivery time than the old one. The new implementation suffers from roughly two to five percent increase in total control overhead, which we consider can be compensated by its superior delivery time and packet delivery ratio. As an addition contribution, we also implement the algorithm for core selection, which is described in [9] to compare with our algorithm. Still, our implementation has shown to have lower control overhead, better packet delivery ratio, and better delivery time. 1.3 Disposition The rest of this thesis is organized as follows: Multicast is presented in chapter 2, and in chapter 3, an in-depth description of PUMA is presented. Chapter 4 describes the algorithm, implementation in details. Lastly, chapter 5 concludes this thesis with our proposition, performance results and analysis. CHAPTER 2: MULTICAST ROUTING 2.1 Introduction Nowadays, a lot of emerging network applications requires the delivery of packets from one or more transmitter to a group of receivers. These applications include bulk data transferring (i.e., the transfer of a software upgrade from software developers to users needing the upgrade), streaming of continuous media (e.g., the transfer of the audio, video and text of a live lecture to a set of distributed lecture participants), sharing data applications (i.e., a teleconferencing or whiteboard application that is shared among many distributed participants), data feeds (e.g., stock quotes), and interactive gaming (i.e., distributed interactive virtual environments or multi-player games). For each of these applications, a significantly useful abstraction is the notion of a multicast: the sending of a packet from one sender to multiple receivers with only a single "transmit" operation. In this section, we consider the network layer aspects of multicast. 2.2 Common mechanism From the network perspective, multicast abstraction – a send operation that results in a copy of the data sent and delivered to many receivers – can be implemented in several ways. One possibility is for the sender to use a separate unicast transport connection to each receiver. An application-layer [4] data unit that is forwarded to the transport-layer [4] is then duplicated at the sender and then transmitted over each individual connection. This approach is an implementation of one-sender-to-many multicast using the basic abstraction layer unicast networks. It does not require explicit multicast support from the network layer [4] to implement multicast abstraction but simulates multicast by using multiple point-to-point unicasts. This is shown on the left of Figure 1, with a network router in the shade of white, which means they are not actively involved in support multicast. In this example, the multicast sender uses three separate unicast connections to three receivers. Figure 1: Multicast A second alternative provides explicit support for multicast at the network layer. In second approach, a single datagram passed from the sending host. This datagram (or a copy of this datagram) is then replicated in a network router whenever it must be sent over multiple links to reach the recipient. The right side of Figure 1 illustrates this second method, with certain routers shaded in green to indicate that they are actively involved in supporting the multicast. Here, the sender transmits a single datagram packet. The router within network then mirrors this datagram; a copy transfer to a recipient on the other end and the other copy is transferred to the rightmost router. At the rightmost router, the multicast datagram that is broadcast over Ethernet with two receivers connected to the rightmost router. Apparently, this second approach towards multicast make more efficient use of network bandwidth in which only a single copy of a datagram will ever go through a link. Other the other hand, significant network layer support is necessary to make a multicast-aware network layer. For the rest of this section we will focus on a multicast-aware network layer, as this approach is done on the Internet and put out some interesting challenge. For multicast communications, we are immediately faced with two problems are much more complicated in the case of unicast - how to determine the recipient of a multicast datagram and how to address a datagram sent to the recipients. In the case of unicast communication, the IP addresses of the recipient (destination) are made for each IP unicast datagram and determine recipients only. However, in the case of multicast, we now have more collection. Does it make sense for each to implement datagram multicast IP address of all the many recipients? While this approach may be feasible with a small number of recipients, it will not scale to the cases of hundreds or thousands of recipients, the amount of information in solving datagram would swamp the amount of data actually carried in the datagram's payload field. Explicit identification of the receivers by the sender also requires that the sender know the identities and addresses of all of the receivers. We will see shortly that there are cases where this requirement might be undesirable. For these reasons, the Internet architecture, a multicast datagram aims to address indirection. That is, an "identifier" is used for the group of receivers, and a copy of the datagram that is addressed to the group with the single "identifier" is supplied to all multicast receivers associated with that group. In the Internet, the single "identifier", which represents a group of receivers, is a class D multicast address. The group of receivers associated with a class D address is referred to as a multicast group. The multicast group abstraction is illustrated in Figure 2. Here are four hosts (shown in red) in relation to the group multicast and receives all multicast datagram that address. The problem that we need is that each host a unique IP address is the unicast address that is completely independent of the address of the multicast group in which it participates. Figure 2: Multicast group While the multicast group abstraction is simple, it raises many questions. How does a group get started and how does it terminate? How is the group address chosen? How are new hosts added to the group (as senders or receivers)? Can anyone join a group (and send to, or receive from, that group) or is group membership restricted and if so, by whom? Do group members know the identities of the other group members as part of the network layer protocol? How do the network routers interoperate with each other to deliver a multicast datagram to all group members? For the Internet, the answers to all of these questions involve the Internet Group Management Protocol [RFC 2236]. So, let us next consider the IGMP protocol and then return to these broader questions. 2.3 Multicast routing in LAN IGMP (Internet Group Management Protocol) protocol developed from the Host Membership Protocol, described in the documents of Deering. IGMP development IGMPv1 (RFC1112) to IGMPv2 (RFC2236) and the final version of IGMPv3 (RFC3376). IGMP messages are sent inside IP packets with the protocol number of 2, in which the TTL value by 1. IGMP packets are transmitted only in the LAN and not be further transferred to other LAN the TTL value of it. Two of the most important goal is IGMP: - Inform the multicast router is a machine that wants to receive multicast traffic of a specific group. - Notice that a router is a machine to leave a multicast group (in other words, a computer is no longer interested in receiving multicast traffic again). The IGMP router used to maintain information for each port of the router is the router multicast group does need to move and want to get the host. Before a host can do any multicast traffic, a multicast application to be installed and running on that host. After a host to join a group, the software will calculate a multicast address and network card will then start listening to a multicast MAC address. Before a host or a user wants to join a group, users need to know if the group exists and how to join that group. For application level programs, users simply click a link on a website or multicast addresses can be preconfigured on the client. For example, a user may be required to log into a server and authenticate with user name and. If the username is authenticated, multicast applications are automatically installed on the user's PC, meaning users have to participate in the multicast group. When users no longer want to use multicast applications, users must leave the group. For example, users simply close the application for leave multicast groups. For multicast mechanism, a user needs to find out what they want to run applications, multicast address used by applications. How a router to know the machine needs to hear the multicast traffic? To receive multicast traffic from a source, both the source and the receiver must first join to a multicast group. This group was identified through a multicast address. A host can join a multicast group by sending requests to the nearest router. Operations are conducted through IGMP protocol. IGMPv1 is defined in RFC1112 and its improvements, IGMPv2 is defined in RFC2236. When there are few hosts want to join the group, PIM protocol will inform each other between the router and the multicast tree formed between routers. IGMP and ICMP have many similarities, share some similar functions. IGMP is also packed in packets (IP protocol number 2), but only IGMP limit in a layer 2 connection. To ensure continued router never transfer packets, the TTL field of IGMP always equal to 1. 2.3.1 IGMPv1 Every 60 seconds, a router on each network segment will send the query to all hosts to check if this host is also interested in receiving multicast traffic again. This router is called query IGMPv1 Querier router and its function is to invite the host to join the group. If a host wants to join a group, or it wants to continue receiving traffic from a group that was involved, it must respond with the membership-report message. The host can join the multicast group at any time. However, IGMPv1 has no mechanism to enable a host to leave a group if that host is no longer interested in the contents of that multicast group. Rather, the router will conclude a port of the bundle does not belong to a multicast group if the router does not receive message-report membership for three consecutive cycles’ queries. This means that, in default mode, the multicast traffic is sent on a network segment in three consecutive cycles after querying all members of the group who no longer listen to multicast traffic. In addition, the router cannot keep a complete list of machines for each multicast group members. Instead, it needs to do is save the multicast group exists on the gate of it. A message has IGMPv1 five fields: 1. Version: This field is 4-bit length, always with an assigned value. 2. Type: School 4bit value, indicating two types of messages defined by IGMPv1. Type 1 is the type Host Membership Query, which is used only by routers. Type 2 is the type of Host Membership report was used only by the host. 3. Unused: 8bit length field contains the value 0 when sent and ignored when received. 4. Checksum: 16bit checksum value is calculated by the source of the IGMP messages. Equipment typically receives checksum value and check if this value is not exactly equals the calculated value, the receiver will remove the frame. 5. Group Address: The value assigned to the router 0.0.0.0 Membership query packet sent out. This value is the value assigned to the multicast group address when sending a Membership report message. Note that when you combine two versions and the type, the value of a hexadecimal IGMPv1 Host Membership Query packet is 0x11