Internet Research Tast Force Yun Li, Qieli Liu Internet-Draft Wireless Network Laboratory, Intended status: Experimental Chongqing University of Posts Expires: June 1, 2011 and Telecommunications, China December 1, 2010 NER-DRP: Dissemination-based Routing Protocol with Network-layer Error Control draft-yunli-nerdrp-00.txt 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. 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on June 30,2011. Copyright Notice Copyright (c) 2010 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. Li Expires: June 3, 2011 [Page 1] Internet-Draft NER-DRP December 2010 Abstract To reliably hand over data packets to the destination in Delay Tolerant Networks (DTNs), many dissemination-based routing protocols are proposed. Dissemination-based routing protocols assure nodes including intermediate nodes and destinations have more chances to receive packets, which will increase the probability that the packets can be correctly received by the destination. However, the existing error recovery mechanisms in network layer use the simple CRC to check the data packets independently, and discard the error packets even if one correct packet can be obtained from more than one partly error packets. This document describes Dissemination-based Routing Protocol with Network-layer Error Control (NER-DRP). NER-DRP divides a data packet into RS blocks and inserts redundancy to each block. So the intermediate nodes and destinations can recover a correct data packet from multiple partially error copies of the same packet. Table of Contents 1. Introduction................................................2 2. The NER-DRP routing protocol.................................4 2.1. Error recovery in network layer.........................4 2.1.1. The procedure in the source node...................4 2.1.2. The procedure in intermediate nodes or destinations.5 2.2. The NER-DRP Routing Protocol............................7 3. Security Considerations......................................9 4. IANA Considerations.........................................9 5. Conclusions.................................................9 6. References..................................................9 6.1. Normative References....................................9 6.2. Informative References..................................9 1. Introduction The characteristics of DTNs, such as intermittent connectivity, long delay, asymmetric wireless link, make the traditional network architectures and protocols, for example the TCP/IP architecture, are not suitable. In recently years, some works have been conducted for these networks. The DTN (Delay Tolerant Networks) architecture is proposed by Delay Tolerant Network Research Group (DTNRG) of Internet Research Task Force (IRTF) when they study deep space Internet communications [1, 2]. DTN uses the store-and-forward message Li Expires: June 3, 2011 [Page 2] Internet-Draft NER-DRP December 2010 switching to overcome the problems associated with intermittent connectivity and long delay. One key issue on DTNs is to find the route to forward data packets. Routing techniques in DTNs typically aim to maximize the delivery ratio or to minimize the delay that each message experiences during delivery [3]. Given the frequent topology dynamics both proactive and reactive routing approaches fail in finding appropriate routes because they attempt to find complete paths between source and destination nodes, which do not exist in DTNs. So it is more successful to find a route on a hop-by-hop basis. For hop-by-hop routing, a next-hop node is chosen by exploiting local information (also is called knowledge) about the contacts available at each hop towards other nodes as well as the queues of pending messages (waiting for forwarding) both at the forwarder node and at its neighbour nodes. In [4,5], the authors introduces four knowledge categories named oracles, contacts summary oracle, contact oracle, queuing oracle and traffic demand oracle, and proposes different routing algorithms, each of them using a different set of oracles. Unfortunately, the assumption of availability of the oracles is not actually realistic. So most of the existing routing protocols on DTNs are not based on the knowledge about the future topology of the network, and dissemination-based routing protocols, including replication-based routing protocols [6-10], coding-based routing [11,12], utility-based routing [13-16], are proposed. The main problem of dissemination-based routing is that a large number of copies of the same packet exist in the network, and will be received and forwarded by many nodes, which exhausts the wireless bandwidth resource, and wastes the energy of mobile nodes. Another problem about dissemination-based routing is that the copies received by the intermediate nodes and destinations, especially the partially error copies, are directly dropped without fully utilization. To resolve the above problems, this document describes a network layer error recovery method, named NER. NER utilizes the characteristic of dissemination-based routing in DTNs, i.e., more than one copies can be received by the intermediate nodes and destinations, to recover a correct data packet from more than one partially error packets, which can increase the delivery ratio of messages. Moreover, a routing protocol integrating NER and EPI, named NER-DRP, is proposed to realize error control dissemination- based routing in DTNs. Li Expires: June 3, 2011 [Page 3] Internet-Draft NER-DRP December 2010 2. The NER-DRP routing protocol In this section, firstly the network layer error recovery method, named NER, is described. Then the procedure of NER-DRP routing protocol, which integrates epidemic routing and NER, is given. 2.1. Error recovery in network layer The error recovery in network layer based on FEC, named NER, mainly includes two procedures, one is the procedure in the source node, and the other is the procedure in the intermediate nodes or destinations. 2.1.1. The procedure in the source node The main function of NER in source nodes is to encapsulate messages in data packets, and divide each data packet into blocks. For each block, the redundant information will be added to check and correct the errors in the block. Although there are many error correcting codes can be used to FEC, in this document, Reed Solomon (RS) is selected to illustrate the procedures of NER. Figure 1 gives the several common RS code. In this document, the RS (127,117) is used for showing the procedure of NER in the source node. The detail procedure of NER using RS code in source node is shown in Figure 2. In Figure 2, the packet header is an independent block, and the payload is divided to N blocks, each block is 127 octets including 117 octets data and 10 octets redundancy. When length of data part of the last RS block is shorter than 117 octets, complement bits ??will be added. RS (127,117) code can correct up to 5 bytes errors or 10 bytes errors of known location. +------------------------------------------------------------------+ | Type |Speed(k/n)|Error correction ability| Fail probability| |---------- -|----------|------------------------|-----------------| |RS(511, 479)| 0.93 | 16 | 5.78e-1 | |------------|----------|---------------------- -|-----------------| |RS(255, 223)| 0.87 | 16 | 5.78e-1 | |------------|----------|------------------------|-----------------| |RS(127, 117)| 0.92 | 5 | 3.48e-3 | |------------|----------|------------------------|-----------------| |RS(63, 55) | 0.85 | 4 | 1.48e-4 | |------------|----------|------------------------|-----------------| |RS(31,25) | 0.81 | 3 | 1.03e-4 | +------------------------------------------------+-----------------+ Figure 1. Several common codes of RS. Li Expires: June 3, 2011 [Page 4] Internet-Draft NER-DRP December 2010 +----------+---------+----+-----------+ | Message 1|Message 2| ...| Message N | +----------+---------+----+-----------+ | \ | \-------------------------------------------->| +-----------------------+------------------------------+---+ | Header | Frame body MSDU |FCS| +-----------------------+------------------------------+---+ | |\ \------->\ | | \ \ +---------------+-------+ +---------+-------+---+---------+-------+ |Header Data(20)|FEC(10)| |DATA(117)|FEC(10)|...|DATA(117)|FEC(10)| +---------------+-------+ +---------+-------+---+---------+-------+ | | | | | | |<---Header block------>| |<--Data block 1->| |<-Data block N-->| Figure 2. The procedure of the packet in the source node 2.1.2. The procedure in intermediate nodes or destinations The main function of NER in intermediate nodes or destinations is to recover a correct data packet from one or more corrupted copies of a packet. The process flow chart of NER in intermediate nodes or destinations is shown in Figure 3, which mainly includes RS error correction and multi-copy recombining functions. In Figure 3, the variable Rcorrect shows whether a correct copy of the same packet is buffered or not, and Rrev shows whether a copy of the same packet is buffered or not. After receiving a copy of data packet, the intermediate nodes or destinations use the RS error correction function to try to correct each block in that packet, and the correct blocks are buffered. The multi-copy recombining is an important function, which is the main difference between NER and traditional network layer function. In traditional network layer, the corrupted packets will be wholly discarded. In NER, the correct blocks in a data packet will be buffered, and the different correct blocks in different copies of the same data packet will be recombined to try to recover a correct packet. Figure 4 shows an example of multi-copy recombining function, in which different blocks (B1, B2, B3, B4, and B5) from three copies (C1, C2, and C3) are recombined. In Figure 4, C1, C2, and C3 are three copies of the same packet P, and the symbol "xx" presents that the block is error. Li Expires: June 3, 2011 [Page 5] Internet-Draft NER-DRP December 2010 +---------------------------------+ | Initialize: Rcorrect=0,Rrev=0;| +---------------------------------+ \|/ +------------------------+ | Received a packet copy | +------------------------+ \|/ /-----------------\ Yes / Rcorrect = 1 ? /-------------------->| \-----------------/ | \|/ No | +--------------------------------------+ | | Using RS code to correct header block| | +--------------------------------------+ | \|/ | /---------------------------------\ No | /Can obtain correct header block ? /---------->| \---------------------------------/ | \|/ Yes \|/ +-------------------------------------+ +-----------------+ |Using RS code to correct data block | | Drop the packet | +-------------------------------------+ +-----------------+ \|/ | Yes /------\ No | |<------------/Rrev=1 ?\---->| | \|/ \--------/ | | +-----------------------+ \|/ | | Recombine data packet | +------------------------| | +-----------------------+ | Save correct data block| | | +------------------------| | No /---------------------\ | | <----/obtain correct packet? \ | | | \-----------------------/ | | \|/ | Yes | | +---------+ +----------+ | | | Rrev=1 | |Rcorrect=1| | | +---------+ +----------+ | | | | | | | | | | |------------>|------------>|<--------------------------| \|/ +--------+ | END | +--------+ Figure 3. RS error correction and multi-copy resembling process. Li Expires: June 3, 2011 [Page 6] Internet-Draft NER-DRP December 2010 B1 B2 B3 B4 B5 +---++---++---++---++---+ C1: | ||xxx|| || ||xxx|\ +---++---++---++---++---+ \ \ B1 B2 B3 B4 B5 +---++---++---++---++---+ \ +---++---++---++---++---+ C2: | || || ||xxx||xxx|---->| || || || || | +---++---++---++---++---+ / +---++---++---++---++---+ / +---++---++---++---++---+ / C3: |xxx|| ||xxx|| || |/ +---++---++---++---++---+ Figure 4. Multi-copy recombining process. 2.2. The NER-DRP Routing Protocol The NER-DRP routing protocol works as follows. Each node maintains a buffer including the packets that it has originated as well as the packet that it has received. The buffered packets consist of correct packets and partially error packets. All of the buffered packets include RS coded blocks as mentioned in Section 2.1. A hash table indexes this list of packets. For each partially error packet PKTi, a corresponding timer Ti is set. The value of Ti denotes the maximum time that the PKTi can be stores. When a partially error packet PKTi is received at first time, Ti is set. When Ti is timeout, PKTi is dropped. As in epidemic routing, each node stores a bit vector, called the summary vector that indicates which entries in their local hash tables are set. When node A comes into contact with node B, they will initiate a session to switch packet with each other. The detail that node A transmits packets to node B includes the following steps. Step 1: Node A transmits its summary vector, SVA to node B. SVA denotes the buffered packets in node A, which including the entire correct packet stand by PKTcA and the partly error packet stand by PKTeA. Step 2: When SVA is received, node B compares its summary vector with SVA to determine the packets buffered in node A but not buffered in node B as well as the packets buffered in node B with partial error. Li Expires: June 3, 2011 [Page 7] Internet-Draft NER-DRP December 2010 Then node B send request to node A to require it transmit these packets. Step 3: Node A transmits the required packets to Node B. Step 4: For every packet received from node A, node B proceed it according to procedure shown in Figure 5. +--------------------------------------------------------------+ | 1: For every received packet pkt from node A; | | 2: Node B tries to decode the RS blocks in pkt; | | 3: If (some RS blocks can not be decoded correctly) { | | 4: If (a partially error copy of packet pkt has buffered | | in node B) { | | 5: Node B uses the multi-copy recombining correction | | technique to recombine an new packet pkt' from | | the two partially error copies; | | 6: If (pkt' is a correct packet) | | 7: Goto line 21; | | 8: Else { | | 9: Buffer pkt' as partially error packet; | | 10: Drop the partially error copy of packet pkt; | | 11: } | | 12: } | | 13: Else { | | 14: Buffer pkt as partially error packet; | | 15: Start the corresponding timer Tpkt; | | 16 } | | 17: } | | 18: Else { | | 19: If (a partially error copy of packet pkt has buffered | | in node B)| | 20: Node B drops the partially error copy and deletes | | its corresponding timer; | | 21: If (pkt is destined to node B) | | 22: Node B deliveries pkt to up layer; | | 23: Else | | 24: Node B buffers pkt for forwarding; | | 25: } | +--------------------------------------------------------------+ Figure 5. The procedure for node B to proceed a packet received from node A. Li Expires: June 3, 2011 [Page 8] Internet-Draft NER-DRP December 2010 3. Security Considerations The NER-DRP block introduces no new security considerations beyond two nodes should trust each other before exchanging messages. 4. IANA Considerations This document has no IANA considerations. 5. Conclusions This document firstly present network layer error recovery for DTNs, which is named NER. NER uses RS code and multi-copy recombining scheme to improve the end-to-end performance of DTNs. Although this paper select RS code, we believe that NER is efficient for other FEC codes. Then based on the NER, the NER-DRP routing protocol is given. Although NER is only integrated to epidemic routing in this paper, we can use the similar way to embed NER to other dissemination-based routing protocols to improve their performance. 6. References 6.1. Normative References [1] V. Cerf, S. Burleigh, and A. Hooke, "Delay-tolerant networking architecture," IETF RFC4838, April, 2007. 6.2. Informative References [2] K. Fall, "A delay-tolerant network architecture for challenged internet," In Proceedings of SIGCOMM?3, Karlsruhe, Germany, Aug. 2003, pp. 27-34. [3] L. Pelusi, A. Passarella, and M. Conti, "Beyond MANETs: dissertation on opportunistic networking," IIT-CNR. Tech. Rep., May 2006. [4] J. Sushant, K. Fall, and R. Patra, " Routing in a delay tolerant network," Proceedings of SIGCOMM'04, Oregon, USA, August, 2004, pp. 145-158. [5] T. Hossmann, F. Legendre, and T. Spyropoulos, "From contacts to graphs: pitfalls in using complex network analysis for DTN routing," Proceedings of INFOCOM Workshop on NetSciCom, Rio de Janeiro, Brazil, April 2009, pp. 1-6. Li Expires: June 3, 2011 [Page 9] Internet-Draft NER-DRP December 2010 [6] A. Vahdat and D. Becker, "Epidemic routing for partially connected ad hoc networks," Tech. Rep. CS-2000-06, Department of Computer Science, Duke University, Durham, NC, 2000. [7] J. A. Davids, A. H. Fagg, and B. N. Levine, "Wearable computers as packet transport mechanisms in highly-partitioned ad-hoc networks," Proceedings of ISWC'01, New York, USA, Oct. 2001, pp. 141-148. [8] B. Burns, O. Brock, and B. N. Levine, "MV Routing and capacity building in disruption tolerant networks," Proceedings of IEEE INFOCOM, Miami, FL, USA, March 2005 pp. 398-408. [9] A. Balasubramanian, B. N. Levine and A. Venkataramani, "Replication routing in DTNs: a resource allocation approach," IEEE/ACM Trans. on Networking, 2010, 18(2), 596-609. [10] T. Spyropoulos, K. Psounis, and C. S. Raghavendra, "Spray and wait: an efficient routing scheme for intermittently connected mobile networks," Proceedings of ACM SIGCOMM Workshop on Delay Tolerant Networks, Philadelphia, PA, USA, August 2005, pp. 252- 259. [11] Y. Wang, S. Jain, M. Martonosi, and K. Fall, "Erasure coding based routing for opportunistic networks," Proceedings of ACM SIGCOMM Workshop on Delay Tolerant Networks, Philadelphia, PA, USA, August 2005, pp. 229-236. [12] J. Widmer and J.Y. Le Boudec, "Network coding for efficient communication in extreme networks," Proceedings of ACM SIGCOMM Workshop on Delay Tolerant Networks, Philadelphia, PA, USA, August 2005, pp. 284-291. [13] X. Chen and A. L. Murphy, "Enabling disconnected transitive communication in mobile ad hoc networks," Proceedings of the Workshop on Principles of Mobile Computing (collocated with PODC'01), Newport, RI, USA, August 2001, pp. 21-27. [14] Lindgren, A. Doria, and O. Schelen, "Probabilistic routing in intermittently connected networks," Mobile Computing and Communications Review, 2003, 7(3), 19-20. [15] M. Musolesi, S. Hailes, and C. Mascolo, "daptive routing for intermittently connected mobile ad hoc networks," Proceedings of WoWMoM, Taormina-Giardini Naxos, Italy, June 2005, pp. 183 - 189. Li Expires: June 3, 2011 [Page 10] Internet-Draft NER-DRP December 2010 [16] F. Tchakountio and R. Ramanathan, "Tracking highly mobile endpoints" Proceedings of WoWMoM'01, Rome, Italy, July 2001, pp. 83 - 94. Authors' Addresses Yun Li Wireless Network Laboratory, Chonqing University of Posts and Telecommunications, China Nan An District, Chongqing, China, 40065 Phone: 0086-23-62460218 Email: liyun@cqupt.edu.cn Qieli Liu Wireless Network Laboratory, Chonqing University of Posts and Telecommunications, China Nan An District, Chongqing, China, 40065 Phone: 0086-23-62460218 Email: liuql@cqupt.edu.cn Li Expires: June 3, 2011 [Page 11]