ODMRP-ASYM (On Demand Multicast Routing Protocol) For LinuxImplementationEric Bostrom, Jason Lin, Joon-Sang Park{ebostrom, jasonl, jspark}@cs.ucla.edu University of California, Los AngelesLos Angeles, CA 90095AbstractThis paper presents our work with an ODMRP (on demand multicast Routing Protocol)to extend its functionality to work with asymmetric links in a Linux Environment. We were giventhe functional code for the ODMRP protocol, as well as a test-bed to work with which consistedof five Dell Lattitude laptops equipped with Lucent Wireless PCMCIA 802.11 cards. Ourimplementation consists of adding to the existing ODMRP code two packet definition types, aswell as handlers for these packet types. The packet types are the new Loop Discovery Packet andLoop Marking Packet. These are used to detect loops in order to solve the asymmetric linkproblem in routing. This is done in the reply phase of the path discovery for ODMRP. When thenode sending the Join Table Packet times out while waiting for an acknowledgement, the LoopDiscovery Packet is then transmitted from that node. This packet goes around the loop collectingIP addresses of the nodes in the loop, and when the node that timed out sees this packet again,the loop has been discovered. That node then sends out the Loop Marking Packet, which marksall the nodes in that loop as forwarding nodes. Through this procedure, the forwarding group iscreated even with asymmetric links, and the sending node is able to have an established path tothe receiving node. Much of the difficulty of this implementation was in the configuration of thetest-bed to be able to enable the laptops to communicate correctly with each other.1. IntroductionMost routing protocols developed for wireless ad-hoc networks do not consider theexistence of asymmetric links—namely, links with different characteristics (e.g., range, quality,etc) in the two directions. The most common cause of this asymmetry is the difference intransmitting power from one node to another, but other causes may be the presence of externalinterference. In the extreme case, the asymmetric link becomes a unidirectional link, i.e. a linkthat connects node A to node B, but not node B to node A. Asymmetric links are often found inthe real deployment of wireless ad-hoc networks as shown in recent experimental studies.Other sources of asymmetric links include directional antennas and power (or topology)control algorithms. Directional antennas, which concentrate radio signals toward a specificdirection instead of spreading signals out to a circular area surrounding the transmitter, is devisedto overcome performance limitations of the conventional omni-directional antenna system. Alllinks using the directional antenna system are inherently asymmetric. Power control algorithmsare used to protract the lifetime of a network. In some wireless ad-hoc network scenarios, such assensor networks with intrinsically limited resources, it is important to use power efficiently sothat these networks can have longer lifetimes. Most power control protocols disallow or disregardasymmetric links, yet some yield asymmetric links.On-demand routing protocols using reverse path technique that backtrack upstream nodewill not work if they confront asymmetric links in the route discovery stage. This problem isreferred to as the asymmetric link problem in routing. Recently, a number of researchersinvestigated the impact of asymmetric links on the performance of unicast routing protocols andextended them to support asymmetric links.There are two ways to tackle the asymmetric link problem. Most of the existing workdeals with asymmetric links by simply detecting and eliminating them. This approach is naturalfor unicast routing in that the point-to-point data transmission (i.e. unicast) in the standardwireless MAC protocol, IEEE 802.11 DCF, works well only with bi-directional links as itrequires RTS/CTS/ACK handshaking. The other approach is to exploit asymmetric links, whichwe advocate because of the following reasons. First of all we believe that routing protocolsshould guarantee to find a path if a path exists. If a routing protocol fails to find an existing route,it is considered to have a serious flaw. The problem with the elimination of asymmetric links isthat one cannot get 100% route discovery guarantee in sparse networks even if the topology isconnected. Partitioning is also a consideration in network performance, which makes disregardingasymmetric links unacceptable.In Section 2, a background is given about how our protocol supports asymmetric links inthe multicast protocol. Section 3 gives us further details regarding the implementation. Section 4describes our testbed and testbed configuration. Section 5 describes the shortcomings of ourimplementations, and possibly future work to correct these. And finally Section 6 contains ourconclusions about this project.2. BackgroundODMRP-ASYM was based on the ODMRP, which was developed at the WirelessAdaptive Mobility Lab (WAM) at UCLA. ODMRP uses on-demand routing to techniques toimprove channel overhead and efficiency as well as improve scalability. ODMRP uses a mesh-based structure to ensure that only a subset of nodes are responsible for forwarding multicastpackets along a shortest path between any member pairs. This forwarding group mesh-basedconcept is a departure from a tree-based multicast scheme. On-demand routing schemes flood todiscover routes as needed. Generally, flooding by the source is used to discover a path to thedestination. ODMRP uses this forwarding group to building a forwarding mesh by creating a setof nodes to forward multicast data on the shortest paths between any member pairs. ODMRP-ASYM is an extension of ODMRP that enables routing with asymmetric links and around theloops.The purpose of Loop Detection procedure is to find an alternate path from a node whichdoes not have a link to an upstream node. Basically, a packet called Loop Detect Packet (LDP) isflooded with the limited TTL (Time-To-Live) which is the expected maximum size of the loop.Experimentally, we choose 6 for this TTL. When the LDP gets back to its sender, it includes a listof node addresses in the order in which they saw the packet.In original ODMRP, different from Join Query packets, every Join Reply packet is to
View Full Document
Unlocking...