Khóa luậ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 and a 0x12 IGMPv1 Host Membership report. These values are compared with the values of IGMPv2.  Function send Host Membership Report:  The host used IGMPv1 Host Membership report message to respond to IGMP query packets and inform the router that the computer wants to receive multicast. The host IGMPv1 report uses multicast messages to communicate with the router, specifies the multicast group address to which it would like to receive. In IGMPv1, a host sending a message IGMPv1 Host membership report under the following circumstances: - When a host receives a packet IGMPv1 Query from the router, the host will assume HostMembership report sent to all multicast group that it wants to receive traffic. This message is called IGMPv1 Solicited Host Membership report. - When a host to join a new group, it wants to send out immediately IGMPv1 Host Membership report to inform the router that it wants to receive traffic for that group without waiting for IGMPv1 Query packet. This message is called unsolicited IGMPv1 Host Membership report. IGMPv1 Querier Router query: To increase reserves, we can implement multiple multicast routers on the same network. Nevertheless, if all the routers send packets every 60 seconds, the query would be very wasteful of bandwidth. Thus, a router should have assigned the role to send query packets and multicast traffic transmitted into or out subnet. If a router is down, second router can assume responsibility. IGMPv1 usually based on the multicast routing information to solve this problem elect router. 2.3.2 IGMPv2 IGMPv2 version introduces several differences compared with the first version. The query packet is now known as General Queries. These packages can be sent to address all-hosts or to specific groups. Another improvement is that the hosts are allowed to leave the group. When a host leaves a group decided to join it, it sends messages to LeaveGroup all-routers address. All routers on a network segment will heed the message and the router will continue the query process. The router will respond with a message on the message sent by the group access. This message will ask that there is also host to groups that want to get traffic again. Any host should respond by membership report messages. Otherwise, the router will safely conclude that moving traffic is not necessary for that group on that network segment. Around this time, the default is 3 minutes. One of the reasons for developing the IGMPv2 is that it provides a mechanism to leave the group better. IGMPv2 has added some new features: - Group-specific Query: allows the router to send query for a specific group rather than for all group - Maximum Response Time: A new field in the query packet, allowing the adjustment period for host membership report message. This feature can be useful when a large number of groups exists on a subnet and you want to reduce the number of messages responded by prolonged response messages over a longer period. - Leave group message: allow hosts to inform routers that hosts want to leave the group. - Query router rating: Provide mechanisms for routers to send out the vote message when a query with multiple routers connected to a subnet. Membership report message is sent when a host to join a group. Occasionally, this type of message is also used to answer queries from the query router. When a host to join a group, it will not wait for query packet from the router. Instead, it will send a membership report. Destination address of the membership report is the group destination address. To ensure that the router receives this message, hosts will send several messages, each 10 seconds apart. IGMP v2 has four fields, is defined as follows: 1) Type: 8bit length field, indicating one of four types of messages defined by IGMPv2. The possible values are: a. Membership query (value 0x11): used by routers to find the presence of hosts on a subnet. The message of this type of value assigned to the group address as in IGMPv1 0.0.0.0. A query message for a given group will address the group in this field. A message of this type is usually sent when the router receives a leave group message from a host IGMPv2 leave group. The message type is used to determine if there, still any member of a particular group. b. Version 1 Membership report (code 0x12): used by IGMPv2 for compatibility with IGMPv1 c. Version 2 Membership report (code 0x16) is sent by the member to notify the router when there is at least one member on the network. d. Leave Group (0x17): submitted by members of the group if it is the last member to send membership report messages. The router that hosts the message are reported for leaving the group 2) Maximum Response Time (Maximum Response Time): 8bit length of query messages. The default value for this field is 100 (approximately 10 seconds). The value will change from 1 to 255 (i.e., from 0.1 seconds to 25.5 seconds). 3) Checksum: Contains 16bit values calculated by machine source. IGMP checksum calculated over the entire load of the IP, not just the first 8bytes although 8bytes IGMPv2 length. 4) Group Address: Assign the value of the query packet and assigns the group address if the message is specific to each group. The membership report messages or leave group messages can carry the group's address in this field. If there are multiple routers on the same connection, the router with the smallest IP address will send out query packets. Therefore, when a router receives a packet from a router, it will check the source address of the packet there. If the source address of the router is under a local source address in packet arrival, the router will continue to send a query packet because it knows that it will function as the query. If the source address of query packets is smaller, the router will abandon the role query. IGMPv2 support backward compatibility with IGMPv1. Code for the type of query and report messages of IGMPv2 and IGMPv1 are the same as 0x11 and 0x12. This allows hosts and routers running IGMPv2 realized IGMPv1 hosts on the network. IGMPv2 helps reducing the number of report messages sent by the host by allowing the administrator to change the query time. IGMPv1 has no parameters Maximum Response Time (MRT), so the host simply use the default period is 10 seconds. However, IGMPv2 messages include the MRT; MRT indicates the time used by all hosts on the LAN IGMPv2. The process of the host sending the message Report is the same in IGMPv1 and IGMPv2. There is a small difference is the router IGMPv2 queries sent packets every 125 seconds instead of every 60 seconds. The process IGMPv2 query and report use a query mechanism for specific groups. In IGMPv2, when a host leaving a group, it sends out a group of IGMPv2 leave messages. When a router receives messages, IGMPv2 leave group, instead of waiting for a period of 125 seconds, the router will immediately send a query message for that group. This message is just to ask if the host also want to receive multicast traffic for that group. The primary advantages compared IGMPv2 with IGMPv1 is that IGMPv2 provides a mechanism for a host to leave the multicast group faster. 2.4 Multicast Routing in Internet 2.4.1 Distance Vector Multicast Routing Protocol (DVMRP) RFC 1075 describes the first version of DVMRP. DVMRP has many versions. The activities of DVMRP PIM-DM are similar. The differences between PIM-DM and DVRMP are defined as follow: - Cisco IOS does not support DVMRP, but it supports connection to a DVMRP network. - DVMRP routing protocol itself, is similar to RIPv2. It sends updates every 60 seconds and 32 is the limit on the hop. DVMRP routing protocol should take its own additional costs compared with PIM-DM. - DVMRP probe messages used to find neighboring routers. 2.4.2 Multicast Open Shortest Path First (MOSPF) MOSPF is defined in RFC1584, is an extended version of the unicast routing protocols OSPFv2. MOSPF's basic operations are described as follows: - MOSPF LSA group use the type 6 address. Along with unicast OSPF, all MOSPF routers in one area must have the same database link so that all MOSPF routers in an area can be calculated with a SPT algorithm. - SPT algorithm is calculated on demand. - Update the calculation process; all the routers know where the group members based on group membership LSAs. - After some SPF calculations are completed, the information will be included in multicast routing table. - Like OSPF unicast routing, shortest path tree is not a loop and know all the router ports upstream / downstream. The result does not need the RPF check. - MOSPF can only work with OSPF unicast routing. MOSPF is suitable for small networks. When multiple machines start sending multicast traffic, the routers have to perform some calculations Dijkstra, result in wastage of CPU resources. Cisco IOS does not support MOSPF. 2.4.3 PIM 2.4.3.1 PIM dense mode (PIM-DM) The PIM router can be configured by type Dense Mode (also called PIM-DM) if the hosts are participating in multicast group located anywhere within the subnet. Multicast source address becomes the root of the tree and a multicast tree is built from source to destinations. This mechanism is also known by the symbol (S, G) in which the path from source to group members is unique. PIM-DM is useful when sending and receiving machines are close together and multiple machines send and receives high-density traffic multicast, but multicast traffic flow did not change. Multicast tree is built by allowing the dispersal of traffic from source to all routers in the network. Tree will grow from top to bottom. In a short time, the unnecessary traffic flow will be like in the broadcast traffic. Nevertheless, when the router receives traffic for a group, the router will decide it wants the computer to receive data or not? If yes, the router will remain silent and continue to flow. If no host registers for that Multicast group (via IGMP), the router would sends Prune message to its neighboring routers in the direction of the root of the tree. Branch of the tree will then be removed so that unnecessary traffic will not be distributed in that direction. Multicast tree will be built according to the requirements to join the group. Then the router which can not join the hosts will be deleted from the tree. PIM-DM will recognize neighboring devices by exchanging hello packets. Neighbor information is used first to build the tree to all its neighbors. Then, the branch of the tree will be removed in turn. When a multicast stream starts, the tree will be built. Trees will only exist when its members remain active. If a new host joins the group, branch of the network segment will be attached to the tree. 2.4.3.2 PIM sparse mode (PIM-SM) Multicast routing protocols dense mode is useful when the application is multicast dense traffic and you need to distribute virtually the entire network. However, if the user has only a few subnets, routing protocols dense rule will remain spread over the entire flow of inter-network, wasting bandwidth and resources. In these cases, sparse style routing, PIM-SM instance can be used to reduce the wastage of network resources. The basic difference between dense mode and sparse mode related to its default state. By default, the protocol rule of dense traffic continued to pass unless a group of routers below indicates that it does not want to get that traffic. The sparse mode protocol does not transmit traffic to any router of the group unless it receives a message request copies of the packet for a multicast group. Neighboring routers receive packets only require one to two purposes: - The router has received a request to receive a packet from the router. - A host on a network segment sent IGMP Join message for that group. Operation of the PIM sparse mode began when the packet is pushed on a special router called the Rendezvous Point (RP). When the flow of the RP group, unlike in the dense, no RP router to automatically push any traffic on any router. A router must request this flow. 2.5 Multicast routing in ad hoc networks 2.5.1 Tree-based approaches Tree-based multicast is a well defined concept in cable network. Most schemes for offering multicast in cable networks are either source-or shared-tree-based. Various researchers have attempted to extend tree-based effort to support multicast in a MANET s environment. This section provides an overview of some of these approaches. - Ad Hoc Multicast Routing Protocol Utilizing Increasing ID Numbers (AMRIS) is an on-demand protocol that builds a shared multicast delivery tree to support multiple transmitters and receivers in one multicast session. AMRIS dynamically assigns an ID number to each node in each multicast session. Based on the ID number, a multicast delivery tree - established at a specific node with Smallest-ID (Sid) - is created and ID number increases with tree extends from Sid. To sum up, Sid is the source or the nodethat initiates a multicast session. - Multicast Ad hoc On-Demand Distance Vector (MAODV) Protocol – MAODV determines multicast routes on demand by a broadcast path discovery mechanism to apply the identical route request (RREQ) and route reply (RREP) messages found in the unicast AODV protocol. A mobile node forms a RREQ message when it wants to join a multicast group or has information to send to a multicast group, but exists no route to this group. Only one member of the preferred multicast group may react to a join RREQ. If the RREQ is not a JOIN request, whichever node with a new adequate route (based on group sequence number) to the multicast group can reply. If a transitional node receives a join RREQ for a multicast group to which it is not a member, or, it receives a RREQ and not has a route to this group; it rebroadcasts the RREQ to its neighbors. 2.5.2 Mesh-based approaches Unlike a tree approach, mesh-based multicast protocols may have numerous paths between any source and destination. Presented studies show that tree-based protocols are not essentially best for the multicast in a MANET where network topology changes regularly. In such a situation, mesh-based protocols seem to do better than tree-based protocols due to the availability of alternative paths, which allows multicast datagram to be transmitted to the recipients even if the links stop working. This section presents an overview of some of the mesh-based approaches in a MANET. On-Demand Multicast Routing Protocol (ODMRP) — ODMRP is a mesh-based protocol that uses a forwarding group concept. A soft state advance is taken in ODMRP to preserve multicast group members. No unequivocal control message is necessary to leave the group. In ODMRP, group membership and multicast routes are built and updated by demand of the source. When a multicast source has packets to transmit, having no route to the multicast group, it broadcast a Join-Query control packet to the whole network. This Join-Query packet is regularly broadcast to update member information and routes. When a transitional node receives a Join-Query packet, it keeps the source ID and sequence number in its message cache to identify any possible duplication. Routing table is updated with a proper node ID (i.e. backward knowledge) from which message is received. If the message is not a replica and TTL is greater than zero, it is rebroadcast. Core-Assisted Mesh Protocol (CAMP) helps multicasting by creating a common mesh for each multicast group. Meshes then created help maintain connection for multicast users, even with moving node. It based on concepts from CBT, but in contrast to CBT where all traffic flows through the central node, the central nodes in CAMP are used to limit the control traffic. The fundamental operation of CAMP includes construction and maintenances the multicast meshes for a multicast group. It requires a mapping service that gives routers with the addresses of groups identified by their names. It also involves access to router information from a unicast routing protocol. Each router maintains a routing table (RT). CAMP adapts this table when a multicast group must be inserted or removed. Based on RT, a multicast routing table (MRT) was built. A router can update its MRT based on topological changes or communication received from its neighbors. 2.6 Conclusion Steve Deering wrote the first RFC for multicast mechanism in 1986. Nevertheless, a few years later, the huge demand for multicast mechanism has exploded, from a communication needs such as audio, video, TV programs ... Multicast also has been studied as a component of the Internet, known as Project Multicast backbone, Mbone. Today, as the need for a protocol that can be used for moving devices, such as cell phone, cars,.. many protocols for MANETs have been proposed such as CAMP, MAODV. It will be interesting to see how the deployment multicast routing in MANETs plays out over the next decade of computer networking. CHAPTER 3: AN EFFICIENT AND ROBUST MULTICASTING ROUTING PROTOCOL FOR MANETS 3.1 Introduction PUMA [5], as an abbreviation of Protocol for unified multicasting through announcement, is a multicast routing protocol. PUMA is a receiver-initiated shared mesh. PUMA has shown to perform better than most of the representative multicast routing protocols. PUMA, compares with other multicast routing protocol, achieves a better data delivery ratio with a very low control overhead. Furthermore, all transmissions in PUMA are broadcast, it does not require any unicast protocol to work. Like CAMP [3] and MAODV [10], PUMA uses a receiver initiated approach in which a receiver joins a multicast group by using the address of a special node (core in CAMP or group leader in MAODV) without having to perform a network-wide flooding of control and data packets from every sources of the group. PUMA also bypasses the need for a unicast routing protocol and the assignment of cores to multicast groups beforehand. 3.2 Core based model PUMA uses a distributed algorithm in order to select one of the recipients of a group to be the core of the group, and each router in the network, at the distance of at least one next-hop to the chosen core of each group is also informed about the core election. Within a limited time proportional to the time needed for the router to arrive to the router farthest away from the core of a group, each router almost have one or more path to the elected core. Each receiver is connected to the core along all of the shortest paths between the receiver and the elected core. All nodes on shortest paths between any receiver and the core form the mesh collectively. A transmitter sends a data packet to the group along one of the shortest path. When a data packet arrived at the mesh, it then will be flooded within the mesh. As a result, all of the mesh member receive the packet. Each node maintains a packet ID cache to prevent packet duplication. Especially, PUMA only uses a control message to maintain all of its functions, which is call multicast announcement. Each multicast announcement contains a sequence number, the group’s address (group ID), the core’s address (core ID), the distance to the core, a mesh_member flag which is set when the sending node is a member of the mesh and lastly, a parent preferred by the neighbor to reach the core. With the information retrieved by the announcements, nodes elect the core for the mesh, select the best routes to reach the core from outside of a multicast group, notify other nodes about the mesh’ state, and maintain the mesh. 3.3 Message structures and connectivity list A node that believes it is the core of a multicast group periodically transmitted announcement messages for that group. As multicast message passing through the network, it established a connectivity list in every node in the network. Using the connectivity list, a node can set up a mesh, as a result, routes data packets from the sender to the receivers. Every node store the necessary information acquired from the entire multicast announcement it received from its neighbors in its connectivity list... Newer multicast message from a neighbor (for example, with a higher sequence number) will replace entries in which the sequence numbers are lower for the same group. Thus, for a certain group, a node will have only one entry in the list of its connections from a given neighbor, and it just keeps that information with the latest sequence numbers for each core. Each item in the connectivity list, in addition to storing multicast announcement messages, it also stores the time when the packet was received, neighbor from which it received. The node then creates its own multicast announcement message, by selecting the best entry in the connectivity list. For announcement with same core ID, multicast message with the highest sequence number is chosen. For announcement with same core ID and same sequence number, then the message with smaller distances to the core is valid. If all of these criteria are the same, the multicast announcement that the first reach the nodes is considered better. After choosing the best-multicast announcement message, the node creates its multicast announcement follow by these rules: Core ID: best-multicast announcement core-id Group ID: Group id of the best-multicast announcement Sequence number: Best-multicast announcement’s sequence number Distance to core: The distance to core of the best-multicast announcement plus one Parent: Neighbor from which this node received the best-multicast announcement Mesh member: Flag Figure 3: Connectivity List The connectivity list stores information on one or more links that exist to reach the core. When a particular group undergoes a core change, then the node deletes all the entries in the old list of connectivity and built a new one. Figure 3 show the process of propagating multicast announcement messages and constructing the connectivity list. The bold arrows represent the neighbor from which a node gets its best multicast announcement message. Node 6 has three entries in its list of connectivity for the neighbors of 5, 1 and 7. However, it chose the entry that received from 5 as the best entry, because it has the shortest distance to the core, moreover, was received earlier than the message from node 1. Node 6 uses these inputs to generate its own multicast announcement, which specifies: Group ID = 224.0.0.6, Core ID = 11, Sequence number = 79, Distance to the core = 2 And Parent = 5. If a node wants to transmit data packets to the group, it sends to the node that it received its best multicast announcement from. If this link is broken, then it will try the next best, the same applies if this link is broken. Therefore, each network node has one or more route to the core. Multicast announcement sent by the core has the distance to the core set to zero and the parent field is invalid_address. By default, multicast announcements are creating by the core every three seconds. When a node receives a multicast announcement with a new sequence number, it waits for a short period (for example, 100 ms) to collect multicast announcement from many neighbors before trying to generate iits own multicast announcement message. When multiple groups exist, nodes gather all multicast announcement they receive, and disseminate them periodically every multicast announcement interval (3 seconds). On the contrary, for announcement that belong to the group that was heard for the first time, which will lead to a new core, or changes in mesh membership status, is sent immediately, without wait for gathering. It helps avoid critical situations, such as fight for core or the establishment of the mesh. 3.4 Mesh Organization Apparently, only the receiving nodes consider themselves to be the members of the network and set the mesh member flag to true before trying to send the multicast announcement messages to their neighbor. Node who are not receiver will consider themselves as members of the mesh if only there at least one child in their list of connectivity. A node in the connectivity list is a mesh child if the following conditions are met: (a) mesh_member flag is set, (b) The distance from the core of the next node is greater than its distance from the core, and (c) Multicast announcement corresponding to this node has been received within a period equal to two intervals of the multicast announcement. The third condition is used to make sure that a neighbor is still the neighborhood. If a node has a child and is a member of mesh, then there is a shortest path from a receiver to the core, which crosses the node. Figure 4: Mesh Creation As shown in Figure 4, the node M is chosen as the core of the group and the network nodes to know their distance to the core by plus one to the best entry in their list of connectivity. The receivers (in this example: node I, F, A, B, D and M) set the mesh member flag to TRUE in their multicast announcement message. Upon receipt of the multicast announcement message from node F, node G and H, they considered themselves as mesh members. Node F is considered a child mesh for each of them, because the distance from F to the cores (3) is greater than theirs (2). In addition, nodes J, K, L, C and E also consider themselves members of mesh. Because mesh-members are considered as a mesh child of all nodes, which have the distance to the core smaller than its own, therefore it results in all of them becoming mesh members. The above scheme results in the integration of all shortest paths between the receiver and the core of the network. In the example, two shortest path of distance 3 from the receiver F to the core M exists F -> G -> L -> M and F -> H -> L -> M. Moreover, both paths are one part of the mesh. When a node constructs a multicast announcement message, it put the mesh member flag, depending on whether or not it is a member of the mesh at that point in time. Besides constructing a multicast message when it discovers a core change, or when it receives a new multicast announcement, a node also creates a new multicast announcement message if it detects a change in its mesh membership status. This would occur when a child mesh node is discovered for the first time, or when a node that previously had a child mesh detects it has no mesh children. This scheme of works even if a node does not generate a multicast announcement immediately after detecting a change in the mesh member status, and waits for the next batch of fresh multicast announcement message to the report its brand-new mesh membership status. However, this could lead to a delay in the implementation of the proper mesh, and can lead to dropping packets as well as redundant transmissions of data packets, or unnecessary retransmission. However, we will see that this kind of approach will not increase the total amount of control packet overhead dramatically. As we describe earlier, the PUMA control overhead is not a serious matter. As long as the group core has not changed, the node would create a multicast announcement message whenever they receive a new announcement message (I.e. the one with the higher number). The core create a multicast announcement message periodically (3 seconds), which results follow by each node in the network creates a multicast announcement message each multicast_announcement_interval i.e. every three seconds. This is the main origin overhead of control early in each node. Additional multicast announcement message, which is generated whenever a node detects a change to the core. However, this does not result in a significant increase because of the changes happen per core node is very small as described. Nodes also created multicast announcement messages when they detect a change in the status of their mesh membership status as described. Almost all of these types of multicast announcement are created immediately after an election-core when the network is being established. In addition, because the number of core election is small, as a result, the generation of this type of packet is limited. In steady state network can be divided into three types of node: a) Those that are in the center of the grid: The node does not create packet, because they tend to have more children. Having one more or less a child does not enable them to create these types of packets. b) The remote network: these nodes never have children and therefore do not mesh created multicast message types. c) The node at the periphery of the grid: The nodes are more likely to move in and out by the mobile network, and therefore create all kinds of multicast message. However, the node detects a link break only if they do not receive multicast notice period for 3 x multicast message i.e. 9 seconds, if a node to move in and out of quickly, it does not create multiple multicast announcement. 3.5 Core election process When a receiver wants to join a multicast group, firstly, it determines whether it has received a multicast announcement message for that group or not: If the node has, then it uses the core indicate that it has received, and start sending multicast announcement, specify the same core group. Otherwise, it considers itself the core of the group, and starts sending multicast announcement message on a regular basis to its neighbors, indicating itself is their core group and 0 distance_to_core to itself. Node broadcast multicast announcement message by selecting the best multicast announcement they receive from their neighbor. A multicast announcement message, which has a higher core ID, is considered better than multicast messages that have announced with a lower core ID. An election process is also held if the network undergoes partition. Election is held in the partition where it does not have the old core. As for detecting a partition: A node detects a partition if after a timeout of 3 x multicast announcement interval, it does not receive any fresh core announcement. Once a node detects partition, it acts exactly the same way it would upon joining the group and participates in core election process. The stability of a core is significant for the effectiveness in performance of PUMA. Frequent rate of core changes, in addition to leading to overload of control message, would also lead to a dramatic rise in number of packet drops. Because the mesh would always in a state of reconstruction, this is avoided in PUMA because PUMA satisfies two important aspects: (a) Core elections would not happen even if the partition and reconnection were occurring frequently. (b) Nodes do not discover a partition when one has not underwent. The first (a) condition is met because nodes detect a partitioning in PUMA if and only if they fail to receive a multicast announcement message from a core for three consecutive multicast announcement period’s (for example: 9 seconds) from any neighbor. As a result, if partitions and reconnections are rapidly occurring then nodes shall not trigger a core election process. It will only happen when a node is partitioned away of the core for a period of 9 seconds a receiver node engages in the core selection process. Nodes might detect a partition when it has not happened if they repeatedly fail to receive multicast announcement messages from the group core. Different multicasting protocols would face with similar problems as well if important control information were consistently lost. Note that a node receives a core announcement message along all paths that connect it to the core. It discovers a false partition only if it is not able to receive a single multicast announcement message on the entire path for three times multicast announcement intervals, (i.e. 9 seconds). 3.6 Forwarding data packet The parent’s field of the list of connectivity entry for a particular neighbor corresponds to the node which the neighbor received its best multicast announcement message. This field allows nodes that are not the members of the group to forward multicast packets towards the mesh of a group. A node forwards a multicast data or control packet it receives from its neighbor if and only the parent for the neighbor is the node itself. As a result, multicast data packets move hop by hop, based on the connectivity list, until they reach any mesh member. When it happens, the packets then are flooded within the mesh, and group members use a message ID cache to detect and discard packet duplication. This is shown in Figure 4. Nodes O and Q represent in the multicast announcement message that their parent is node N. On the same behavior, node P indicates in its multicast announcement message that its parent is node K. Let us assume that nodes O and node P are the senders. Node N will forward a data packet from O, but not from node P, because only node O has informed node N that it considers node N to be its parent. Even though that node J is not the parent of node P, it would still forwards the packet when it receives it from node P. This happens because all mesh members do not check their connectivity list before forwarding a packet. As a result, receiver (node I) gets the packet sooner. Node J does not schedule a rebroadcast the packet when it receives the packet for the second time from node K, because the packet’s ID is stored in its message ID cache. The routing of data packets (or control packet) from senders to receivers is also used to update the connectivity list of the receiving node. When a non-member broadcasts a packet, it would expect its parent to continue forward the packet. Because all of the communication is broadcast, the node, which first broadcast a data packet, also receives the data packet when it is forwarded by broadcasting by its parent. This is used as an implicit acknowledgment of the packet transmission process. If the node does not receive an implicit acknowledgment within ACK_TIMEOUT, which means there is something wrong with the path, and as a result, it removes the parent from its connectivity list. 3.7 Sequence Numbers Recycle Similar to other unicast or multicast routing protocols that used sequence numbers, PUMA needs to recycle sequence numbers every now and then, and handle exception that cause a group core to reset the sequence number which is assigned to a multicast group. Because the sequence number of a multicast announcement message is only increased by the core member of the group, moreover, because the core would floods its announcement messages periodically with the same mechanisms which are used for the handling of sequence numbers in many link-state routing protocols such as OSPF or in the building a spanning tree algorithm. It is enough to ensure that nodes can believe the most recent multicast announcement message. In particular, when a node recovers from a network failure, it then must apply a hold-down timeout, long enough to make sure that no node in the network still considers the just recovered node to be the core of any multicast group. 3.8 Conclusion Protocol for Unified Multicasting through Announcements (PUMA) is created and based on the original idea of using a simple multicast notification to select a core for a group, and to inform all the routers of the distance and next hop to the core, joining, and leaving their multicast group. In addition to having the lowest control overhead compared with ODMRP and MAODV [10], PUMA provides a very tightly bounded threshold of control overhead. In other words, the controls overhead of PUMA remains almost unchanged when mobility, the number of transmitter, number members of receivers, or traffic load are changed. PUMA also provide the highest delivery rate compare with ODMRP and MAODV. The networks constructed by PUMA limit redundancy to the area that contains receivers. As a result, it reduces unnecessary transmissions of multicast data packets. PUMA does not depend on the existence of pre-core assignment or unicast routing protocol. CHAPTER 4: AN ADAPTIVE CORE SELECTION BASED MULTICAST ROUTING PROTOCOL FOR MANETs 4.1 Introduction Mobile ad hoc networks (MANET) consist of mobile computing devices with radio transmission and reception capacity. Two nodes who are neighbors in the network and can communicate directly when they are within the transmission range of each other and radio propagation condition in vicinity of these nodes is sufficient. Communication between non-neighboring nodes demands a multihop routing protocol [1]. Although mobile ad hoc networks have been primarily used in military applications, they become increasingly apply for civilian applications such as virtual classes’ rooms, wireless LANs, and rule enforcement lately. It expected that in future such ad hoc networks collaboration with overlay cellular networks would provide a widely used computing environment. The motivation for this work comes from the challenges of mobile ad hoc networks to support reliable and efficient communication for distributed computing. Mobile Ad Hoc networks present another network model different from traditional communication protocol design and implementation. Topology of the network changes with node movements, variations in radio propagation conditions and depletion of battery power of nodes. The rate of topological fluctuation may be varied at different times and in different regions of the network. The network may experience frequent network partitioning and may require reestablishment of the partitioned sub networks. Moreover, radio bandwidth is a relatively expensive resource and must conserved. Hence in a mobile ad hoc Network: 1. Old links do not exist and new compounds are formed over time because of node movement.  2. Nodes may be unavailable because they can go to sleep.  3. Bandwidth available on a (logical) link between two neighboring nodes change with time and  4. Topology can be interrupted. Since this dynamic network model is significantly different from the current static network model used to developing communication protocols, researches are needed to examine the appropriateness of the existing protocols and hence, develop an effective, reliable and scalable collective communication protocols for mobile ad hoc networks. Multicast is an important group communication, and it involves sending a message to an arbitrary subset of nodes in the network. It is useful in wide range applications in a distributed system where a set of nodes need to be informed of a specific event. Multicast protocols distributed systems with a static network have been studied a lot. Multicast protocols are evaluated in terms of 1) Bandwidth consumed in the whole process and 2) Maximum delay incurred in delivering the message to all member of the multicast group. A multicast message can be sent to each member of the multicast group separately . This wastes bandwidth since the message can be repeatedly sent over the same communication link. In theory, this wastage can be avoided by constructing a minimal cost tree spans with all members of the multicast group, and then forward the message from the root of the tree (core of the message) along tree edges. Unfortunately, the problem of calculating minimum cost multicast tree spanning at any number of nodes (members of the multicast group) in a given weighted graph is NP-complete, and therefore people have concentrated on designing heuristic algorithms to designing near optimal multicast trees for granted multicast groups and analysis of their results. In practice, a shortest-path tree has proved to give good balance between bandwidth consumption and complexity of designing a multicast tree. Further, to reduce overhead of maintaining multiple multicast tree per group one for each source in the multicast-group, the most recent multicast protocols employ group-shared shortest path trees. A group shared tree is rooted in a central node (also known as a center node or rendezvous point). In static networks, core nodes can be manually configured and pre-assigned. Nevertheless, in mobile ad hoc networks this approach may not be optimal when the topology changes frequently. Dynamic selection of center nodes is important for a good performance. A good core node can be one, which is at center of the part of the network, which spans to all members of multicast group, which is a member of multicast group, which is relatively stable. Each time you select the core network node, it would lead to expense in terms of mobile network topology changes overhead and bandwidth use. In addition, frequently switching to another core node would lead to possible loss of data packets and additional waste of bandwidth lost due to retransmission of packets. Therefore, it is important to design a heuristic method to control the rate of new core node selection. In this thesis, we will combine the core problem choice and after core migration. These problems essentially are tied together. Our selection of core based on the concept of a central transition protocol requires a current multicast tree; minimum data is maintained at each node in the network. The reasons for using the multicast tree itself are as follows: Topology graph of a mobile network is expected to be sparse. The network is composed of broadcast channels, which are modeled as multiple point to point edges; node degree is high enough to keep the connected graph, but node degree is much less than the total number nodes in the network, making the number of edges of the graph typically close enough to be linear in the number of nodes. Therefore, the multicast tree is a good approximation to the network sub graph covers all nodes in the multicast group. Routing protocols designed for mobile ad hoc networks maintain only approximate and minimal topology information, and therefore designing a center selection heuristics require more precise information than what is available. The median of a tree corresponding to centroid of a tree has some nice mathematical properties. This helps in increasing variety of the central node. This is important to make the protocol suitable for mobile network with unrestricted mobility node. The information required to calculate the centroid node can easily integrate with the existing CBT multicast protocol for mobile ad hoc networks. The rest of the chapter is organized as follows: part 2 to 5 describing core-based multicast routing and concepts median and centroid of a tree [9]. Sequential and distributed algorithms for calculating the centroid with some of its properties are also presented to motivate the protocol for mobile ad hoc networks. Part 6 presents our core competencies transfer method. 4.2 Core-based multicast routing protocol The mobile multihop network consists of multiple mobile hosts (nodes) with unique identifiers. These mobile hosts communicate with each other over a packet radio network. When a node transmits (local broadcasts) a message, the nodes in coverage of the sender can simultaneously receive the notice. The topology of the mobile ad hoc networks are modeled by an (undirected) graph G = (V, E, Wx, We), where: - V is the set of nodes, - E is the set of connections between adjacent nodes, - Wx: V-> R+ is the node weight function, and lastly - We: E -> R+ is the edge weight function (Used for shortest-path routing algorithm). Note that the edges represent the logical connection between nodes, i.e. there is an edge between two nodes u and v if they can hear each other local broadcast message. Since nodes are mobile, the network topology graph will almost in change with time. An example of the multicast routing problem consists of a set of sources S (S Î V) and a set of receivers R (RÎ V). The set M = S U R contains the members of the multicast group. For a given graph G and I for example, a multicast routing algorithm defines a multicast tree, which provides the path followed by each packet sent from a source on the way to all recipients. Core-based multicast routing algorithms root multicast tree at a particular node called the core node c. The core node is also called a center node or a rendezvous point. Note that a multicast tree may consist of some nodes not multicast group members. These nodes are called as forwarding nodes. The quality of multicast tree is determined by three performance metrics that are related: 1. Average (maximum) delay: the average (maximum) number of links traversed by any data packet in traveling from a sender to a receiver. 2. Bandwidth: the total number of (single hop) packet transmissions in order to deliver packet from each sending node to all receiving nodes. 3. Traffic concentration: the number of packets traversed across each link in the multicast tree when each source transmits to all receivers. We will then call 1-median as simply median. In the median case, a function H: V -> R+ is defined as follows: H(v) = ∑ Wx(u)d(u,v) (u Î V) Where d(u,v) is the cost of the minimum weight path from u to v in G. The median of the graph is node v with minimum H value, i.e. H(v*) = min H(v) (v Î V) Example 1. An example ad hoc network graph is illustrated in Fig. 5a. We assume that all links have unit weight; multicast group nodes have weight one, and the remaining nodes (forwarding nodes for example) have weight 0 Note that node 1 is the median of the graph of H (1) = 8 Fig. 5b shows a shortest-path multicast tree with node 1 is the core node. Figure 5: Multicast tree The median of an arbitrary graph with n nodes can be calculated in O (n2) time. Nevertheless, when the graph is a tree, the median is calculated in linear time because for a tree graph, median is the same as w-centroid (or just a centroid) of the tree and the centroid of a tree can be calculated in linear time. A median of a tree that is proved equivalent to the term w-centroid of a tree. We briefly list the relevant properties of a centroid of a tree to facilitate the discussion of our distributed core selection algorithm. Consider a vertex v degree k in a tree T = (V,E) Let Tv be the wood obtained by removing v from T with Tv1, Tv2…Tvk be the connected sub trees of Tv. Define that: W(Tv-i) = ∑ Wx(u) (u Î Tv-i, i = 1,2,3..k) And F(v) = max W(Tv,i) A vertex v* Î V is called the centroid of T if and only if F(v*) = min f(v) (v Î V). For example, consider the tree illustrated in Fig. 5b. Using the node weight function as defined before, F(1)=2 and F(4)=6. It can be determined that F(1) is minimum and, therefore, node 1 is the centroid of the tree. Note that the concept of centroid is depending only on the node weights and not the distances between the nodes. We note the following result from: Example 2. Consider the tree in Fig. 5b. Initially, w(1) for all nodes (except node 6). Assume that the nodes are pruned from the tree in increasing order of node number; the following is the sequence of actions taken: |2, w(1) = 2 |->|3, w(6) = 1 |-> |4, w(1) = 3 | -> |5, w(1) = 4 | Where action |v, w(u) =a | denotes that node v is deleted and w(u) is incremented to value a before node 1 notices that w(1) ≥ 7/2, so it’s not fit to be a centroid node anymore. We are interested in calculating the centroid in a distributed manner. This can be done if each node in the tree knows the weight in each of its sub trees. Our core competencies placement algorithm works as follows: 1) Originally, an arbitrary group member chosen as core node and a shortest-path multicast tree is designed using this core node. 2) The core node keeps track of the sum of node weights in each of its sub tree and uses Theorem 2 to discover when it is no longer a centroid of the multicast tree.  3) The core node initiates core migration procedure towards current centroid of the multicast tree. Multicast tree can be built in distributed fashion as is done in Core Base Tree (CBT) multicast protocol. Moreover, JOIN and QUIT messages in CBT can slightly increased contribution to maintaining the necessary information of the central node to determine whether it is a centroid node or not. Before we present how the core migration is conducted, we describe some properties centroid used in our core transfer method. 4.3 Core-based Tree Multicast for MANET The Core Based Tree (CBT) [11] protocol was implemented for Internet. It uses a shared multicast tree rooted at a core or center node. CBT protocol uses receiver-based tree establishment. A node, which is interested in participating in the multicast tree associated with a multicast group, sends a JOIN reference to the core node of that group. The JOIN-REQUEST guided towards the central node through underlying unicast routing protocol. An intermediate node receives a JOIN-Request only forward it to the next node on the route to the core node, except to be an established node in the multicast tree in which case node responds by sending JOIN-ACK to node which began JOIN request. A node intersected by JOIN-ACK detects parent (upstream) node and child (downstream) node. In effect, JOIN-ACK grafts a tree branch from the node, which reacted with JOIN-ACK and the node that initiated the corresponding JOIN-REQUEST. A node, which is wishing to leave the multicast group, simply sends a QUIT-REQUEST to the core node along its branch. A node that receives a QUIT-REQUEST erases node at which it received the QUIT-REQUEST from its children connectivity list. Furthermore, it forwards QUIT-REQUEST to its parent node whose children list becomes empty and that in it is not a multicast group node. The CBT protocol also provides mechanisms to handle link / node failures and central node failure. Link error discovered through the exchange of periodic keep_alive messages between the neighboring nodes. If a node does not receive a certain fixed number of consecutive keep_alive messages from the parent node, it assumes that the connection to its parent node has failed/broken. If a non_core node discovers that its parent node or any link to its parent node has failed, it has two possibilities for the lack of recovery: 1) It can try to connect the multicast tree by sending a JOIN-REQUEST against core node and 2) It can send a FLUSH-TREE message downstream, so each node in the root of the tree the independent trying to attach to multicast tree again. The first option may result in the formation of loops in multicast tree and hence, the CBT protocol provides a loop discovery mechanism. In mobile ad hoc networks, node movement results in failure of the old links and network topology of new connections. A new CBT protocol for mobile ad hoc networks has been proposed by doing the following two changes. Firstly, grant the JOIN-ACK message permission to cross a different path than the corresponding JOIN- REQUEST message. This allows the node movement between transmitting the JOIN-REQUEST message and receiving JOIN-ACK message and hence is more suitable for highly mobile nodes. However, it can form loops because of that. To avoid loops, it is necessary that a multicast tree node, after receiving a JOIN-ACK message, send a QUIT_REQUEST to node who sent this JOIN-ACK message, and at the same time forwarding JOIN-ACK to the next node towards the destination node. Secondly, on a discovery of failure of its parent link or node, a node always sends a FLUSH-TREE message downstream. This has two advantages as follow: 1) Any loop information is avoided and 2) The nodes in the tree have possibly better route to the multicast tree after. However, reconfiguring a sub tree when a tree link fails is costly in terms of additional control messages and therefore it needs adjustment. Moreover, it can result in data loss packets to node in the tree that has crashed. 4.4 Properties of Centroids in Tree with Weights The following properties are based on the assumption that each node has a unit weight. That is, F-value of any node is simply the maximum number of nodes in any of the under trees originating from that node. We will later demonstrate how these properties vary when we have zero node weight nodes in the graph. Furthermore, we assume that there are n nodes in the tree T. Let there be k in trees of node x, with s1, s2, ... , sk vertices in these respective under trees. Note that the degree of vertex x is k, and s1+s2+ … + sk = n-1, where n is the total number of nodes presenting in the tree. We now have the following properties of the centroid node of a tree: Lemma 1. [9] At most, one of the sub trees at a vertex can contain a centroid Lemma 2. [9] There are at most two centroids in a tree, and if two centroids exist, they are adjacent. Theorem 3. [9] Consider a rooted tree obtained from a tree by assuming that x is the root node. Suppose there are k sub trees of root x with s1;s2; ... ;sk vertices in these respective sub trees. Further, let y1;y2; ... ;yk be the roots of these k sub trees. Then, the centroid is in sub tree yj if sj > ∑(si) – sj (i=1 -> k) Corollary 1. [9] The vertex x is the only centroid of a tree if and only if Sj ≤ ∑(si) – sj (i=1 -> k) and with 1 ≤ j ≤ k Corollary 2. [9] A tree with two centroids has an even number of vertices, and the F-value of each centroid is n/2 4.5 Core migration process Due to the unconstrained movement of mobile nodes ad hoc networks, the network’s topology keeps changing. Regarding the multicast tree, a movement of a node shows itself as a deletion of a node of the tree by adding the node to the tree. In addition, new nodes could join the multicast group, and thus the tree. Hence, a node, which is a good root node for the multicast tree at a given time time could not remain good after these changes. Therefore, a new core node must be chosen periodically. However, change the basic node requires informing all the other nodes of the network kernel and modifying the multicast tree so that the new node is the root of the multicast tree. In static networks, the two tasks: 1) Determine a new root and 2) Informing the multicast group members of the new root node and changing multicast trees are carried out separately.  In a mobile ad hoc network, this approach is not appropriate because of the need to minimize general base relocation (migration) and accelerate process to make it fit to the presence of highly mobile node. In addition, we also need to face the problem of network partitioning. Conceptually, we want to use the centroid of the current multicast tree (considered as a tree without roots) than new (or next) multicast tree’s core. However, a multicast tree has both members of the multicast group nodes and forwarding nodes that are not in the group. In addition, we want only a member of the multicast group to be the multicast tree’s core; the obvious advantage is the ability to reduce the number of messages transmitted by the core to multicast members. If we apply the concept of centroid, then we are faced with the issue of a centroid, which is not a multicast member. Other difficulties, even for a fixed term numbers of members of the multicast group, are that the total number of nodes in the multicast tree can continue to change and multicast tree need to adapt to the movement node (including or excluding of certain forwarding nodes of the tree). In order to overcome these problems, we base the centroid calculation on the number of members of multicast group not the total number of nodes in the multicast tree. This is done using the following node weight function: Wx(u) = 1 if u Î M Wx(u) = 0 otherwise However, this changes some properties of the centroid in the tree with all nodes with the weights of units. In particular, now a tree that has two centroids should not be adjacent. 4.6 Algorithm Outline Generally, assume that there is a multicast tree whose the current core is the node x. Each multicast group multicast tree node keeps track of the number of multicast group members in each sub-tree. Furthermore, consider n as the number of multicast group. Let k sub-trees, T1, T2,. . . , Tk be rooted at x with S1. . . Sk multicast group members in these sub-trees respectively. The node that is currently in transit may not be connected to one of the sub-tree and therefore, the sum of Si may be less than n.   Since we want members of the multicast group to contribute to the election of the core node, the system described in the preceding paragraph should be amended to take into account the nodes in the multicast trees playing only the role of forwarders. Whenever the current core node x determines that it does not fit to be the core of the group and the centroid node is in subtree Tj, it send a Become_core() message to the root of Tj, said y. Every time a node v receives a Become_core() message from node u: 1. Node v determines whether a centroid is in one of any of its sub-tree, if so, it sends the message BecomeCore to the root node of that tree. 2. Otherwise, node v determines if a node is a centroid. If yes, then it considers itself the centroid node and sends ACK to u. In the case v is a forwarding node, then it sends a NAK message back to u. This procedure ensures that the core is moved to the multicast group node nearest to the centroid node on the path from the current core node to the centroid node. The core movement is hop by hop. The core move by a hop, then announces that it is the new core and then repeats the process. However, due to the dynamic of MANETs, this kind of approach might lead to increase in control overhead. Furthermore, core change happens rapidly if the current core and the centroid are far from each other, the network might undergoes serious packet loss because the mesh need to reorganize during the core movement. 4.7 Conclusion In this section, a distributed core selection and core migrating algorithms for mobile ad hoc networks has been presented and debated. Because of the unrestricted node movements, the topologies of the mobile ad hoc networks are always under changing. Thus, it is difficult to maintain a complete network topology at each of the network nodes. The most desirable scheme is that the core selection procedure is based on local topology information, which let information easily gathered at each node. This core selection strategy is based on the median of the current tree of multicast; which leads to significant improvement since the median (or the centroid) calculation in a tree does not need the distance information. Apparently, that core-migration would be more beneficial when the group membership is somewhat sparse and the group size is moderate. CHAPTER 5: OUR PROPOSITION AND RESULTS 5.1 Motivation As we mention earlier, PUMA has shown to be the most stable and efficient protocol. 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. Inspired by the idea of core selection from [9], we propose an improvement of PUMA with an adaptive core selection mechanism our own algorithm. The core selection method, which we have described in chapter 4, has a drawback. The core move hop by hop, then announces that it is the new core and then repeats the process.  This process ensures the core is moved to the closest possible node to the centroid. However, if we implement it on PUMA, this kind of approach will lead to noticeable control overhead’s increment. 5.2 Protocol description PUMA uses a single control message to maintain the mesh, which is called the MULTICAST ANNOUNCEMENT. This control message is first originated from the core node and then is sent to the core’s neighbors. Every time a node v receives a MULTICAST ANNOUCEMENT, v uses the message’s information to update its connectivity list. The connectivity list helps v to discern which the shortest way to reach the core node is. V then sends its own MULTICAST ANNOUNCEMENT to its neighbors. To reduce the control overhead when implement the core migration method. We decide to make use of the MULTICAST ANNOUNCEMENT to help each node calculate its weight. First, we add a weight field to the MULTICAST ANNOUNCEMENT message. When v receives the message from u, v first checks if u is one of its child member. If yes, v uses the weight field to update u’s weight in v’s connectivity list. When v wants to send a MULTICAST ANNOUNCEMENT message, it set the weight field in its message equal to the sum of all of its child weight. About the core migration process, the first step is similar to what we have described in 4.6. However, we want the core to be moved directly to the new core, not hop by hop. Therefore, our method is as follows. Every time a node v receives a Become_core() message from node u:  1. Node v determines whether a centroid is in one of any of its sub-tree, if so, it forwards the message to Become_Core the root node of that sub-tree. 2. Otherwise, node v determines if a node is centroid. If yes, then it considers itself to be the centroid node and send NewCore() message to the network, claim itself to be the core of the group. If v is a forwarding node, then it means the centroid is u. v then sends a Response() message back to u. Upon receiving Response() from v, u knows that it is the centroid and broad cast Become_core message accordingly. This approaches still ensures that the core is move to the nearest multicast group node. However, core change happens only once in order to avoid packet loss and control overhead increment Example: Figure 6: Core Migration In Fig 6.a, the core node (node 0) determines that subtree rooted at 1 has a node which deserves to be the core of the group. Therefore it send a multicast_annoucement( type = become_core, dest = 1) and set the confirm_wait to 1 to imply that it has sent a message to 1. 1 receives the message and repeats the process and send a multicast announcement to 6. When 6 receives the message, it then determines that’s it fits to be the core, however, 6 is a forwarding node, so it send a multicast_announcement(type = become_core, dest = 1) back to 1. When 1 receive the message, by checking the confirm_wait, it knows the core node cannot move any further, so it becomes the core of the group. In Fig 6.b, the new core node is node 8, and 8 is a receiver, so it simple becomes the core of the group. 5.3 Pseudo code Handle Multicast announcement procedure at node “this” Input: N - Numbers of nodes Ma – Multicast announcement Begin If this.id = core_id { If this.maxChildWeight > N/2 { bestChild = this.get_best_children(); Send a BecomeCore(this.id, bestChild); } } If (ma.type == BECOME_CORE){ If ma.destination == this.id{ bestChild = this.get_best_children(); If (confirm_wait == bestChild) {Send a NewCore(this.id); confirm_wait = null;} Else if this.weight > N/2{ Send a BecomeCore(this.id, bestChild); Confirm_wait = bestChild; } Else if (this.is_receiver){ Send a NewCore(this.id); } Else {Send a BecomeCore(this.id, ma.source);} } Else { Update_weight_table(); } } End Get_best_child procedure: Begin For every child c of this{ If c.weight > CurrentBestChild.weight { CurrentBestChild = c;} } Return CurrentBestChild; End Update_weight_table() procedure: Input: id, _weight Begin For every child c of this{ If c == id{ c.weight = _weight; } } End 5.4 Network Simulator 2 (NS2) NS (Network simulator) [2] is a network simulation software which controls separate event object-oriented, and was developed at UC Berkeley, NS2 [12] was written in C++ and OTcl. NS is useful for simulating wide area network (WAN) and local network (LAN). The four prominent benefit of NS-2 are as follow:  • Ability to check the stability of the existing network protocols.  • Ability to evaluate new network protocols in use before.  • Ability to execute large network model that is almost impossible to implement in practice.  • Ability to simulate a variety of different network.  NS-2 (Network Simulator version 2.xx) is a open source, free, network emulator. NS-2 is used widely used in universities (which study computer network and communication). NS-2 is extremely effective in simulation, which serve studying the network protocols, from the MAC layer to the Transport layer. Using NS-2, anyone can simulate a Wired networks, Wireless Networks, Mobile ad hoc networks - MANETs, combined networks, etc. The events occur in the network and simulation parameters are usually written in the "trace files” or a text file. To get the desired results, we need to process these files and simulate the results, usually in the form of graphs. A short overview of NS-3: NS-3 is a new open source software which is developed recently, version 3.1 was released in June 2008, the latest version is 3.6 released in October 10/2009. NS-3 is independent software, and is not compatible with NS-2. NS-3 offers features superior network simulator NS-2, for example: IPv6 extension, wifi improvements, new test framework... 5.5 Peer-to-Peer content distribution in MANETs P2MAN [8] is chosen to test and analysis the delivery time of the edited PUMA versions. A short description, P2MAN leverages on the PUMA protocol, its function is to deliver content at application layer. Sidney Doria developed both P2MAN and PUMA. Both program’s source code are publicly available [7] [8]. 5.6 Experimental result and analysis 5.6.1 Simulation environment Control overhead, packet delivery ratio Delivery time Simulator NS2 Number of rounds 10 Total nodes 30 Simulation Time 400 seconds Simulation Area 500m x 500m Node placement Fixed Radio range 250m Pause time 0 s Bandwidth 2 Mbps Data packet size 512 bytes MAC Protocol 802.11 DCF Simulator NS2 Number of rounds 10 Total nodes 100 Simulation Time 600 seconds Simulation Area 1000m x 1000m Node placement Random Radio range 250m Pause time 0 s Bandwidth 2 Mbps Data packet size 512 bytes MAC Protocol 802.11 DCF 5.6.2 Control overhead Figure 6: Senders varied across {5, 20, 30}, members = 30, mobility = 0 m/s, Traffic Load = 10 pkts/s, Multicast groups = 1. Figure 7: Senders = 5, members = 25, mobility = 0 m/s, Traffic Load varied across {2, 5, 10, 20} pkts/s, Multicast groups = 1. Figure 7: Control overhead x Senders Figure 8: Control overhead x Traffic Load As we can see, the total control overhead does increases, but only a very slight amount. The reason is that we integrate the calculating node weight process into the Multicast_announcement message. Therefore, the control message for maintaining the mesh and for calculating node weight is in the same control message, which results in a slight increase in control overhead. 5.6.3 Packet delivery ratio Figure 8: Senders varied across {5, 10, 15, 20}, member = 25, mobility = 0 m/s, Traffic Load = 10 pkts/s, Multicast groups = 1. Figure 9: Senders = 5, members = 25, mobility = 0 m/s, Traffic Load varied across {5, 10, 20, 40} pkts/s, Multicast groups = 1. Figure 9: Packet loss ratio x Senders Figure 10: Packet loss ratio x Traffic Load In both graph, PUMA v2 show to be a better protocol by its lower packet loss ratio. PUMA v1 does decrease packet loss ratio a bit, however, it still cannot compensate to its control overhead increment. Furthermore, as shown in figure 8, the packet loss ratio of PUMA v1 and PUMA come closer and closer to each other as the senders grows. 5.6.4 Delivery time Senders = 1, receivers = 20, mobility = 0-1 m/s, Content size varied across {50, 100, 200, 400} KB Figure 11: Delivery time x Content Size At first, with the content size are 50kb and 100kb, the result show only a slight different. However, when the content size became larger, resulting longer delivery time, the mesh itself finds the best core in the whole process. As a result, the difference in delivery time between these three versions of PUMA became more and more vividly, as shown in the figure. PUMA v2 outperforms PUMA v1 due to its better core migrating method. Senders = 1, receivers varied across {5, 10, 15, 20} mobility = 0-1 m/s, content size = 100 KB Figure 12: Delivery time x Number of concurrent requesting nodes Similar to the previous graph, as the network operate, the mesh become more and more stable overtime. As a result, the differences in delivery time between PUMA and PUMA v1, PUMA v2 grow larger. PUMA v2 and PUMA v1 perform closely to each other in this scenario. Senders = 1, receivers = 20, mobility varied across {0, 2, 5, 10, 30} m/s, Content size = 100 KB. Figure 13: Delivery time x Mobility One significant feature of P2MAN is that the delivery time does not depend on the mobility of the network. To put it simpler, no matter how fast each node move, it does not affect the content delivery time. We have run tests to compare the average delivery time between three versions of PUMA. As illustrated, even though delivery time does not depend on the mobility of each node, PUMA v2 still prove itself more effective in delivery content throughout the network. CHAPTER 6: CONCLUSION In this thesis we have present a particular method to improve the PUMA multicast routing protocol, which result in a slightly increase of total control overhead, but a good improvement in the packet delivery ratio and content delivery time. The primitive ideas are to choose the most appropriate node to become the core of the node, by using a simple yet effective function to calculate the weight of each node, and then move the core the closest possible true core node. Core is not move hop by hop, but directly to the new core. This idea minimizes the control overhead yet results better packet delivery ratio than the former one. Based on extensive experimental simulation, our improved version of PUMA routing protocol has shown to provide good performance results. We intend to separate multicast announcement with weight request function in PUMA, which might lead to unpredictable increase in control overhead. However, the core node would be selected faster and the mesh is well organized in the fastest possible time. Another direction we want to focus on is to improve the weight calculating method by implementing a link delay function. In this thesis, the weight of each node only considers whether it is a mesh member or a forwarding node, but does not consider the delay characteristics. REFERENCE [1] C. Perkins and P. Bhagwat, “Routing Over Multihop Wireless Network of Mobile Computers,” Mobile Computing, T. Imielinski and H.F. Korth, eds., pp. 182-205, Kluwer Academic Publisher, 1996. [2] Eitan Altman and Tania Jimenez, “NS Simulator for beginners”, Univ. de Los Andes, Merida, Venezuela and ESSI, Sophia-Antipolis, France, 2003. [3] E.L Madruga, “Multicasting in Ad-hoc Networks”, University of California, 2002 [4] F.K James and W.R Keith, “Computer networking: A Top-down Approach Featuring the Internet”, 2000 [5] R. Vaishampayan and J. J. Garcia-Luna-Aceves, "Efficient and robust multicast routing in mobile ad hoc networks", IEEE International Conference on Mobile Ad-hoc and Sensor Systems, pp. 304-313, 2004 [6] S. Doria and M. A. Spohn, "Puma multicast routing protocol source code for ns-2," hoc. [7] S. Doria and M. A. Spohn, "Peer-to-manet source code for ns-2," [8] S. Doria and M. A. Spohn , “A multicast approach for peer-to-peer content distribution in mobile ad hoc networks”, IEEE conference on Wireless Communications & Networking, pp. 2920-2925, 2009. [9] S.K.S. Gupta and P.K. Srimani, “Adaptive Core Selection and Migration Method for Multicast Routing in Mobile Ad Hoc Networks”, IEEE transactions on parallel and distributed systems, vol. 14, no. 1, January 2003 [10] T.A. Dewan, “Multicasting in Ad-hoc Networks”, University of Ottawa, 2005 [11] T. Ballardie, P. Francis, and J. Crowcroft, “Core Based Trees (CBT): An Architecture for Scalable Inter Domain Multicast Routing,” Proc. ACM SIGCOMM, pp. 85-95, 1993. [12] "The network simulator,"