INTERNET-DRAFT Dr. Humayun Bakht Expires: October 2011 Independent Researcher (MANET) Request for Comments Email: humayunbakht@yahoo.co.uk draft-bakht-maoddp-01.txt Category: Informational June 2011 Mobile Ad-hoc On-Demand Data Delivery Protocol (MAODDP) Abstract Routing in mobile ad-hoc network is achieved through the mutual cooperation of mobile devices that form routes in between two mobile nodes.It is one of the challenging issues in mobile ad-hoc network [1]. The current protocols for an ad-hoc network can generally be categorized into two groups i.e. pro-active and re-active[15,16,17,18]. Pro-active protocols by continuously evaluating the known and attempting to discover new routes. These protocols try to maintain the most up-to-date view of the network[2]. This allows them to efficiently forward packets as the route is known in advanced [14]. In contrast reactive protocols determine the route only when require [3, 5, 6]. Mobile Ad-hoc On Demand Data Delivery protocol (MAODDP) establishes route on demand and delivers the data at the same time one after the other [22].MAODDP support both unicast and multicast routing. It is designed to minimize reaction to topological changes. In order to ensure the freshness of route MAODDP uses combination of sequence numbers and broadcast ID. MAODDP is loop-free, self-starting protocol whic can scales to different size of networks. MAODDP offers quick adaptation to the dynamic link conditions and determines routes to the destinations on demand. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html "Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as work in progress." This Internet-Draft will expire in November, 2011. Copyright Notice Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Bakht Informational [Page 1] RFC Mobile Ad-hoc On-Demand Data Delivery Protocol June 2011 Table of Contents Abstract 1 Status of This Memo 1 2. Introduction 2 3. Mobile Ad-hoc On-Demand Data Delivery Protocol 4 3.1. Broadcasting Joining Message 4 3.2. Broadcasting Route Query and Data Delivery Packet (RQDD) 4 3.3. Forwarding Route Query and Data Delivery Packet (RQDD) 4 3.4. Creating Reverse Routes 4 3.5. Broadcasting and Forwarding Acknowledge Message (ACK) 4 3.6. Managing Sequence Numbers 5 3.7. Error Detection and Broadcasting Error Messages 5 3.8. Power Saving Mode 5 3.9. Multicast Joining Request 5 3.10. Multicasting 5 3.11. Security 6 3.12. Evaluation Environment 6 3.12.A. Evaluation Results 7 4. Acknowledgements 1. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in "Key words for use in RFCs to Indicate Requirement Levels". Bakht Informational [Page 2] RFC Mobile Ad-hoc On-Demand Data Delivery Protocol June 2011 2. Introduction Routing in Mobile Ad-hoc Network (MANET) is an interesting and challenging issue. Much effort[7,8,9,10,11,12,13] has been going on to develop a routing mechanism which can full-fill the specific routing needs of MANET. Existing literature reports schemes which can be classified into one of two types i.e. tables driven and on-demand routing protocols. Mobile Ad-hoc on-Demand Data Delivery Protocol (MAODDP) adopts an intermediate approach in between the two types mentioned above. MAODDP offer a routing solution capable of meeting other routing associated issues in MANET. MAODDP has been evaluated in SWANS where it showed satisfactory performance both on its own and against other routing scheme of similar type. This document is a specification of mobile ad-hoc on-demand data delivery protocol(MAODDP)[19,20]. It defines different functions and details various features of the protocol. In addition, an explanation to the implementation and evaluation details of the protcol is also covered in this document. 3. Mobile Ad-hoc On-Demand Data Delivery Protocol Mobile Ad-hoc On Demand Data Delivery Protocol adopts an intermediate approach in between tables driven and existing on-demand routing protocols [4]. The key feature of MAODDP is the route establishment of the route and data delivery one after the other. Definition and explanation of MAODDP functions are as follows. 3.1. Broadcasting Joining Message Joining message is broadcasted in one of two situations. If number of mobile nodes want to form an ad-hoc network they broadcast joining message. This message in this case, serves as an initial point of contact for the other nodes in the network. Alternatively, if a mobile node wants to join an established ad-hoc network, it broadcasts join message indicating joining of new node in the network. 3.2. Broadcasting Route Query and Data Delivery Packet (RQDD) A node floods RQDD packet containing both route query information and data. RQDD is to a destination for which node does not have no route information available. Bakht Informational [Page 3] RFC Mobile Ad-hoc On-Demand Data Delivery Protocol June 2011 3.3. Forwarding Route Query and Data Delivery Packet (RQDD) Whenever a RQDD reaches to a node, it takes following steps in sequence. Legitimacy of RQDD: if the same packet has arrived before. To find out the freshness of received RQDD, receiving node check the sequence number and the broadcast ID of RQDD against stored information. If sequence number and broadcast ID matches with stored information nodes take no further action and simply discard the packet. Updating routing information: A node updates routing information: if it finds no previous information about the received RQDD or if the RQDD contains the latest information about the source and the destination node. Forwarding RQDD: Receiving node takes one ofthe following actions. If the destination node is its next hop neighbor or it has no information about the destination. it forwards RQDD to destination or the next hop neighbor. The other alternative is, if the node has fresh enough route to the destination. it forwards the RQDD using the available route. 3.4. Creating Reverse Routes All the nodes through which RQDD passes to destination form a reverse route to the source of RQDD. 3.5. Broadcasting and Forwarding Acknowledge Message (ACK) Destination nodes broadcast an ACK message on recepition of RQDD. This ACK message is forwarded to the source node using the reverse route. 3.6. Managing Sequence Numbers Each node is responsible for maintaining its own sequence number to ensure loop free routing. 3.7. Error Detection and Broadcasting Error Messages In MAODDP, error detection occurs in one of the two conditions. When a node detects a link breakage for the next hop and if it receives route error message (RER) from one of the neighbour. Broadcast of these route error messages are limited to the neighbouring nodes or to the mobile nodes in an establish route for data transfer. 3.8. Power Saving Mode MAODDP is adaptable to existing power saving mechanisms [19] besides its own power saving scheme. Nodes are allowed to switch in between one of two states i.e. soft/sleep or active state. A node can switch into sleep mode if it does not hear from other node within a time limit known as Listening Time (LT). Similarly, after a specific time interval known as Active Time (AT) a node can switch back to an active state. Bakht Informational [Page 4] RFC Mobile Ad-hoc On-Demand Data Delivery Protocol June 2011 In practice, the time between the two modes are kept as minimum as possible to reduce loss of any incoming packet. 3.9. Multicast Joining Request If a node wishes to join a multicast tree for which it is not a member. It can invoke multicast joining request by broadcasting a Multicast Joining query (MJR). On the other hand, if a node wants to share some information with a node part of some other multicast tree it can broadcast multicast route query and data delivery (MRQDD). 3.10. Multicasting MAODDP has been implemented in a manner which allows integration of multicast operations of other schemes within the protocolstructure. MAODDP multicast operation depends on the combination of flooding and formation of the multicast tree structure. It is known that flooding is suitable for high data traffic and offers lowest control overheads while tree based routing reduces data traffic in the network but requires many control data exchanges. MAODDP focus on maintaining only those routes that are active. Expired or invalid route entries automatically deleted from the route table. For multicast operations multicast tree is maintained for the life of the multicast group. 3.11. Security MAODDP deal security at an intermediate level. However, implementation of the protocol allows for other security mechanisms e.g. [17] to integrate within the protocol. MAODDP security mechanism uses trusted certificate server C, whose public keys known to all valid nodes. Two or more mobile nodes collectively can act as a trusted server. Keys are priority generated and are exchanged through mutual relationship between C and each node. Each node obtains a certificate with exactly a single key from the trusted certificate server on joining the network. The certificate details different aspect of connecting node such as node addresses, a public key and a time stamp T1 and T2. T1 defines the certificate issue time and T2 stands for the expiry time of the certificate. These certificates are authenticated and signed by the server C. The goal of communication between source and the destination is to make sure that data is reached safely at the destination.MAODDP allocated public key to all the mobile nodes at the joining of the network. Public key contains a certificate and expiry time. For each RQDD the receiver node extracts the public key from the certificate C to validate the signature and to make sure that the certificate is not expired and is still valid. The same procedure is repeated in forwarding ACKs from the destination to the source node. Bakht Informational [Page 5] RFC Mobile Ad-hoc On-Demand Data Delivery Protocol June 2011 3.12. Evaluation Environment The SuSE Linux 10.1 operating environment was used for all simulation experiments[21]. In total six sets of experiments with each set comprising nine different tests were conducted. Simulation environment were generated using selection of different input parameters. Details of each of these parameters and how these were used are as follows Nodes were placed in a grid type area range of 5x5 to 30x30 within a two dimension fixed field size of 500X500 meters. In one set of experiments nodes were placed randomly with the same fixed field as described above. Nodes were selected from the range of 25 to 450 mobile nodes. All simulation starts at 10 seconds with a fixed resolution time of 60 seconds. MAODDP was evaluated both for short and long simulations run therefore simulation stop time was chosen from the range of 600 to 800 seconds. A fixed pause time of 10 seconds was used in all simulations experiments. In some sets mobility was defined as static and for others following mobility modelswere used. Random Walk: In Random Walk Mobility model mobile nodes moves in turn. Random Way Point: Random Way Point model is an extension of the random walk model. In this model each node at the beginning of its turn first moves to a new position selected at random in the unit square. Teleport Model: This was another model which was used in some of the simulation experiments. Packet loss for most of the experiments defined as default. Adding packet loss to the simulation does not really test anything new, since the simulation already have packet loss even without specifying it. Definition and explanation of conclusions drawn from the simulation results are as follows. Data Delivery: It defines the ratio between the number of ACKs sent and broadcast RQDD. Route Formed: Defines number of new route added. Elapsed Time: It defines the time period in between simulation start and stop time. Memory Saved: It is the difference of total memory and memory used in a simulation cycle. Total Memory: It is the memory allocated by the SWANS[22] based on the input parameters used in a simulation cycle. Memory Used: It defines the amount of memory used in a simulation cycle. 3.12. A.Evaluation Results In the light of evaluation results it can be drawn that MAODDP is well suited in different types of environments. Almost all the operations as defined in MAODDP specification are practically applicable and can produce good results.Variations of different types of tests have been conducted over MAODDP. These simulation environments were selected in a manner which can best reflect the nature of communication pattern of mobile ad-hoc network. Messages activities both in terms of broadcasting RQDDs and sending ACKs were quite high.This indicates that MAODDP has a good scalability factor. Bakht Informational [Page 6] RFC Mobile Ad-hoc On-Demand Data Delivery Protocol June 2011 It was noted that the addition of mobile nodes yields little affect on the protocol behaviour and performance. Evaluation experiments were run with three above mentioned mobility models. In these experiments message activities were observed as low however, with a higher data delivery rate. Average collective data delivery of all the evaluation experiments found as 79 percent. This indicates that MAODDP is capable of delivering high data rates in various network environments. A higher data delivery rate was observed for mobile nodes ranges from 100 to 125. With respect to the time, highest data delivery was at in the middle of the simulation time. Variation of data delivery is partially due to the change in grid area which has its due affects in data communication. New route formation implies more active paths fordata communication. In this context, MAODDP showed an impressive and normal behavior as some of the well known routing protocols. Probability of new route formation was increased with the addition of mobile nodes.Average number of new route formed calculated was 613 percent. Energy conservations an important aspect mobile ad-hoc network. On average MAODDP saved 67.5 percent of available memory. Teleport model in compression with random walk and random way point model conserved the highest amount of available memory. 4. Acknowledgements The author work on this specification would be incomplete without the assistance of project supervisors who have assisted him from the beginning till the end of this research project. Bakht Informational [Page 7] RFC Mobile Ad-hoc On-Demand Data Delivery Protocol June 2011 5. References [1]. G. Holland and N.Vaidya. Analysis of TCP Performance over Mobile Ad Hoc Networks. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom). 1999. [2]. S.Kannan, John E Mellor, and D.D.Kouvatsos, Investigation of routing in DSDV. 4th Annual Post-Graduate Symposium on the Convergence of Telecommunications, Networking and Broadcasting, Liverpool UK, 2003. [3]. Charles E. Perkins and Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing. Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, February 1999: p. pp. 90 to 100. [4]. H.Bakht, M.Merabti, and R.Askwith, Mobile Ad-hoc On Demand Data Delivery Protocol. 3rdAnnual Post- Graduate Symposium on the Convergence of Telecommunications, Networking and Broadcasting, 2002. [5]. H.Bakht. A Study of Routing Protocols for Mobile Ad-hoc Networks. in 1st International Computer Engineering Conference. December 2004. Cairo , Egypt. [6]. H.Bakht, M.Merabti, and R.Askwith. Centralized Frame for Routing in Mobile Ad-hocNetworks. in In Proceedings othe International Conference on Computer Communication(ICCC). September, 2004. Beijing, China. [7]. D. B. Johnson and D.A. Maltz, Dynamic Source Routing in Ad hoc Wireless Networks. Mobile Computing, 1996. 353. Bakht Informational [Page 8] RFC Mobile Ad-hoc On-Demand Data Delivery Protocol June 2011 [8]. C. E. Perkins and E. M. Royer, Ad-hoc On- Demand Distance Vector Routing. 2nd IEEE Workshop on Mobile Computing Systems and Applications, February 1999: p. 90-100. [9]. A. Aaron and J. WengA. Aaron and J. Weng, Performance Comparison of Ad- Hoc Routing Protocols for Networks with Node Energy Constraints. June ,2001, EE 360 Class Project,Stanford University. [10]. I. D. Aron and S. K.S.Gupta, On the Scalability of On-Demand Routing Protocols for Mobile Ad-hoc Networks: An Analytical Study. Journal of Interconnection Networks, January ,2001. [11]. J. Broch, et al., A Performance Comparsion of Multi-Hop Wireless Ad- Hoc Network Routing Protocols. In Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), 1998. [12]. M.Asim and A.J. PullinM.Asim and A.J. Pullin, Comparison analysis of MAODDP with some other prominent Wireless ad hoc routing protocols, in IBITE Computing. 2005, Liverpool Hope University: Liverpool. [13]. C. E. Perkins. Performance Comparsion of two On-Demand Routing Protocols for Ad Hoc Networks. in IEEE Conference on Computer Communications (INFOCOM). March 2000. [14]. E. Royer and C.Toh, A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks. IEEE Personal Communications Magazine, April 1999: p. 46-55. [15]. S. Sesay, et al., Simulation Comparsion of Four Wireless Ad hoc Routing Protocols. Information Technology, 2004. 3(3): p. 219-226. [16]. C.K. Toh, S.J.Lee, and M.Gerla, A simulation study of table driven and ondemand routing protocols for mobile ad hoc networks. IEEE Network, 1999. 13: p. 48-54. [17]. W. Wang, Y. Lu, and B. Bhargava. On Security Study of Two Distance Vector RoutingProtocols for Mobile Ad Hoc Networks. in IEEE International Conference on Pervasive Computing and Communications. March 2003. Dallas-Fort Worth, Texas,USA. [18]. D. Kim, et al., Routing Mechanisms for Mobile Ad Hoc Networks based on the EnergyDrain Rate. IEEE Transactions on Mobile Computing, April-June 2003. 2(2): p. 161-173. [19]. M Saleemand, MA Sheikh. An Empirical Analysis of Ad hoc Routing Protocols for Hybrid Wireless Sensor Networks. International Conference on Electrical Engineering, ICEE 07, 2007. Bakht Informational [Page 9] RFC Mobile Ad-hoc On-Demand Data Delivery Protocol June 2011 [20]. R.L. Gilaberte and L.P. Herrero. Routing Protocols in Mobile Ad-Hoc Networks. Communication Systems and Networks.2005. [21]. H.bakht, On Demand Routing in Mobile Ad-hoc Network GEJC Computer Sciences and Telecommunication, No 5(22). [22]. Swans, Java in Simulation Time / Scalable Wireless Ad hoc Network Simulator http://jist.ece.cornell.edu/. Bakht Informational [Page 10] Expires: November 2011 RFC Mobile Ad-hoc On-Demand Data Delivery Protocol June 2011 Editors' Addresses Dr. Humayun Bakht Independent Researcher (MANET) Taitec College Manchester Manchester, UK.