NAMO NAMAHA: Network Assisted Multicast Overlay ConstructioN Algorithms for Mobile Ad Hoc Applications

Minimum Dominating Set;Overlay Networks;Ad Hoc Networks;Ad hoc Multicast Routing;Steiner Tree

Acharya, Mithun Puthige ; Douglas Reeves, Committee Chair,Mladen Vouk, Committee Member,David Thuente, Committee Member,Acharya, Mithun Puthige ; Douglas Reeves ; Committee Chair ; Mladen Vouk ; Committee Member ; David Thuente ; Committee Member

University:North Carolina State University

关键词: Minimum Dominating Set;    Overlay Networks;    Ad Hoc Networks;    Ad hoc Multicast Routing;    Steiner Tree;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/1981/etd.pdf?sequence=1&isAllowed=y

美国|英语

来源: null

【 摘 要 】

Group communication is the most important mode of communication in ad hoc networks, because of the collaborative nature of mobile ad hoc applications. In this light, an efficient and light weight multicast routing protocol is necessary. Presently the multicast routing is either done entirely at the network layer, or at the application layer as stateless overlay mulitcasting. Owing to the dynamic nature of ad hoc networks, the first method incurs a large signaling overhead due to frequent modification of routing tables and exchanging of session state information. The latter approach uses the underlying unicast routing to build multicast data distribution trees without maintaining session state information thereby trading efficiency for minimal messaging overhead. For small groups with constant bound on the number of multicast group members, the overlay schemes, apart from having a trivial signaling overhead, are also known to be far more efficient than the network layer schemes. But the existing overlay schemes do not completely exploit the 'knowledge' possessed by the network layer; they just use the unicast routing at the network layer. We believe that, even for larger groups, the overlay schemes can function with reasonable efficiency along with trivial signaling overhead if they intelligently use the network layer information.In this thesis, we propose a network assisted multicast routing scheme, NAMO NAMAHA, which primarily operates as an overlay while getting assistance from the network layer unicast routing protocol, CEDAR. The overlay algorithms dynamically build an approximate Steiner data distribution tree, adopting the (CHINS)_T (Cheapest Insertion Heuristic with Table) algorithm for the distributed implementation of the well known Takahashi-Matsuyama heuristic. The Steiner trees are incrementally built over a subgraph of core nodes, which form the approximate Minimum Dominating Set (MDS) over the network nodes. The core nodes get computed by a network layer heuristic using local data at that layer, and they provide useful information for the NAMO NAMAHA tree computation algorithms at the overlay layer. The main idea in this thesis is that if the construction of overlays is aided by some minimal but useful information from the network layer that is almost invariant, local and that which would incur constant memory overhead, efficient overlays can be constructed.This thesis presents the algorithms for the protocol NAMO NAMAHA, offers proof of correctness for the protocol and shows that the time and memory complexity of the algorithms in the protocol are either constant, or linear with the number of graph edges or nodes. We compare our work with the MCEDAR protocol in terms of the cost of the multicast data distribution trees, the number of messages exchanged in building them and the time and memory complexity of the algorithms involved. We choose MCEDAR since other multicast protocols for ad hoc networks are either network based which does not scale for large nubmer of nodes, or function as overlays designed only for small groups. When compared to MCEDAR, NAMO NAMAHA has a simpler join protocol implemented by our unique Unicast Trap algorithm that does not make use of acknowledgements. Unlike MCEDAR, the sender discovery messages are not propagated all over the network; they are restricted to regions where it is absolutely necessary. In NAMO NAMAHA, at any given time, a path exists between any multicast subscriber and the sender (which is approximately the best path possible) with very high probability. Such a guarantee cannot be given in MCEDAR. Furthermore because of the incremental Steiner tree construction, the resulting multicast data distribution tree has nearly the least total cost. Cost is not minimized in MCEDAR. These advantages are obtained in NAMO NAMAHA just by using extra messages during tree construction, whose number is well below the actual number of nodes in the multicast group. The time and memory complexity of the NAMO NAMAHA algorithms are in the same order as that in MCEDAR.