Khóa luận Efficient core selection for multicast routing in mobile ad hoc networks

ast 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