INTERNET-DRAFT Thomas Clausen IETF MANET Working Group LIX, Ecole Polytechnique, France Expiration: 14 April 2005 Kenichi Mase Niigata University, Japan 15 October 2004 Link Buffering for MANETs draft-clausen-manet-linkbuffer-00.txt Status of this Memo This document is a submission to the Mobile Ad Hoc Networking Working Group of the Internet Engineering Task Force (IETF). Comments should be submitted to the manet@ietf.org mailing list. Distribution of this memo is unlimited. By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668 This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026. 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. Abstract A number of MANET routing protocols employ the ability to temporarily buffer undeliverable IP datagrams until a route to a destination becomes available. This is indeed the case for reactive protocols, which largely are based on the ability to store an undeliverable IP datagram while a route discovery operation is carried out. Current specifications of proactive routing-protocols do, however, also indiate that they may benefit from such a mechanism: while a local Clausen, Mase Linkbuffer [Page 1] INTERNET-DRAFT Linkbuffer 14 October 2004 link breakage may imply that a selected route to a given destination breaks, buffering an undeliverable IP datagram may allow a local topology discovery mechanism to select an alternative route. This document describes a generic mechanism for buffering IP datagrams in MANETs. The mechanism is based on the idea that while a local link may make a route to a destination fail, it does not imply that an alternative route to that destination is not available. Hence, IP datagrams for transmission along that route are buffered to allow the routing protocol time to construct an alternative route. The IP datagram is discarded only if the routing protocol hasné^Â^ƒt been able to provide an alternative route within a determined small delay. We note, that this specification does not mandate a required behavior for MANET routing protocols. Rather, since the mechanisms currently employed in the four existing MANET routing protocol specification are similar in what they try to accomplish, it is the goal of this specification to generalize and expand on these mechanisms, thereby provide a framework for (i) discussing and refining the mechanism in isolation and (ii) providing a common element, which may be usefull for multiple MANET routing protocols. Clausen, Mase Linkbuffer [Page 2] INTERNET-DRAFT Linkbuffer 14 October 2004 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Applicability Section . . . . . . . . . . . . . . . . . . . . . 5 2. Link Buffering Details . . . . . . . . . . . . . . . . . . . . . 5 2.1. IP Datagram Transmission . . . . . . . . . . . . . . . . . . . 6 2.1.1. Destination States . . . . . . . . . . . . . . . . . . . . . 6 2.1.2. State Transitions . . . . . . . . . . . . . . . . . . . . . . 8 2.1.3. State Diagram . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2. Link Buffer . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3. Restoration . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4. Routing Protocol Interface . . . . . . . . . . . . . . . . . . 13 3. Authors Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 4. References . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 14 7. Security Considerations . . . . . . . . . . . . . . . . . . . . . 14 8. Copyright Statement . . . . . . . . . . . . . . . . . . . . . . . 15 Clausen, Mase Linkbuffer [Page 3] INTERNET-DRAFT Linkbuffer 14 October 2004 1. Introduction Routing protocols in MANETé^Â^ƒs, in general, fall into two distinct cat- egories: proactive protocols such as OLSR [1] and TBRPF [2], and reactive protocols such as AODV [3] and DSR [4]. These protocols serve the task of, on a best effort basis, constructing and maintain- ing connected paths between pairs of nodes, with the purpose of being able to route IP datagrams between any two nodes in the MANET. OLSR, TBRPF, AODV and DSR all specify that, if available, link-layer notifications of local link disconnections should be employed in order to increase the protocols ability to respond to topology changes. However the exact behaviour of the four routing protocols differs: the proactive protocols, in general, take link disconnection into account by adjusting their internal topology graph according to a disappearing link, and then either routing IP datagrams along alternative paths or dropping them as undeliverable if alternative paths are unavailable. For the reactive protocols, a route repair or route discovery cycle is initiated when a link along an active route is no longer available for delivering IP datagrams. Until the route repair or route discovery is completed, undeliverable IP datagrams are buffered for possible later delivery. The aim of this specification is to extract from the four MANET rout- ing protocols a common mechanism for MANET protocols, both proactive and reactive, to employ when local link disconnection is detected on the MAC layer, as well as to accommodate for the needs to buffer IP datagrams while routes are being discovered. When link disconnection is detected, IP datagrams to be transmitted over the now disconnected link are stored in a "link buffer", expecting that the entries in the routing table, which had the disconnected node as next hop, will be updated. Similarly, any IP datagrams in MAC queues, which would now be undeliverable, are extracted and buffered for later delivery -- a technique known as "restoration". When these entries are updated, buffered IP datagrams in the link buffer can be reexamined, and transmitted according to the new information. If the entries are not updated within a reasonable time-frame, buffered IP datagrams can be discarded. We note, that this specification does not mandate a required behavior for MANET routing protocols. Rather, since the mechanisms currently employed in the four existing MANET routing protocol specification are similar in what they try to accomplish, it is the goal of this specification to generalize and expand on these mechanisms, thereby provide a framework for (i) discussing and refining the mechanism in isolation and (ii) providing a common element, which may be usefull for multiple MANET routing protocols. This document specifies a nodes internal behaviour in response to Clausen, Mase Linkbuffer [Page 4] INTERNET-DRAFT Linkbuffer 14 October 2004 local link disconnection and undeliverable packets, and specifies an interface to the routing protocols. 1.1. Terminology The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [5]. In this specification, the following additional terminology is employed: local link disconnect when traffic can no longer be exchanged over a link between a node and its immediate neighbour. This implies that (i) the neighbour may become unavailable as a destination and (ii) the neighbour disappears as a potential "next hop" for routes to nodes farther away in the network. 1.2. Applicability Section The basic assumption for the mechanism proposed is, that while the topology in the network may change quite frequently, nodes disconnect permanently from the network relatively rarely. Therefore, even if a route to a node disappears due to a local link disconnect, it can be assumed the node will remain in the network and an alternative route will become available. For reactive protocols, an alternative route may become available once route repair or route discovery completes successfully. For proactive protocols, an alternative route may become available once topological information has been successfully diffused to the entire network (or until the routing algorithm has found an alternative path through the topology graph). Either class of protocols experiences a delay from a link disconnect is detected and until an alternative route is established. During that delay, IP datagrams, which were to be delivered over the disconnected link, can be buffered for later transmission when a path to their respective destinations has been reestablished -- or discarded when it has been determined that alternative paths can not be found. The proposed mechanism supports both the requirements of proactive and reactive MANET routing protocols. 2. Link Buffering Details In this section, the details regarding link buffering with respect to routing of IP datagrams in MANETs are described. Clausen, Mase Linkbuffer [Page 5] INTERNET-DRAFT Linkbuffer 14 October 2004 2.1. IP Datagram Transmission A node behaves differently with respect to IP datagram transmission to a given destination depending on if the destination is known and available, known but due to a local link disconnection temporarily unavailable or if it is not know if a destination is available in the network. Each node maintains a routing table which allows it to route data, destined for the other nodes in the network, and is primarily popu- lated by the routing protocol governing a node. Additionally, for the purpose of this specification, each entry in the routing table has an associated state, R_dest_state, and lifetime R_dest_lifetime. The use of these additional fields are specified in the following sections. 2.1.1. Destination States Traditional IP datagram transmission considers, essentially, two "states" for any destination: either a route exists (in which case IP datagrams can be transmitted) or no route exists (in which case IP datagrams are to be dropped). Reactive MANET protocols implicitly introduce a third state "route discovery in progress", implying that - packets to the destination should be buffered for potential later delivery; - a route discovery should not be initiated to this destination since one is already ongoing. These two implications SHOULD be separated: the routing protocol is responsible for maintaining routes, hence state in the routing proto- col pertaining to route maintenance SHOULD, if applicable, be estab- lished to prevent multiple concurrent route discoveries for the same destination. Link buffering pertains to whether IP datagrams should be buffered for expected later delivery, or whether they should be dropped. This state concerns IP datagram transmissions, and MUST be maintained for the mechanism in this specification. Thus, three states MUST be maintained in R_dest_state for each desti- nation in the network: Clausen, Mase Linkbuffer [Page 6] INTERNET-DRAFT Linkbuffer 14 October 2004 State | Description | Action ==============|================================|=============== No Route | No routing information is | Buffer | available for this destination | IP Datagrams | | | | Notify routing | | protocol | | | | Route Valid | A route entry exists for | Transmit | this destination, and the | IP Datagrams | link to the next hop towards | | this destination is not | | disconnected | | | | | Route invalid | A route entry exists for this | Buffer | destination, but the next hop | IP Datagrams | towards the destination has | | become disconnected | Notify routing | | protocol The state "No Route" corresponds to the usual situation where no entry in the routing table exists for a given destination. In that case, the default behaviour of a reactive protocol is to initiate route discovery, whereas the default behaviour of a proactive proto- col is to drop IP datagrams. This can be accomplished through having the proactive routing proto- col respond to the notification by simply clearing the buffered pack- ets (through the event "No Destination" described in section 2.1.2 ) The state "Route Valid" corresponds to the usual situation where an entry in the routing table exists for a given destination. In that case, IP datagrams to this destination MUST be forwarded as specified in [6]. I.e. in the case of "No Route" and "Route Valid", the standard behaviour of proactive and reactive routing protocols is preserved. The state "Route Invalid" corresponds to the situation where a desti- nation is believed to be present in the network, although the previ- ously selected "next hop" currently is unavailable. IP datagrams to a destination in this state are inserted into the "Link Buffer". Fur- thermore, the routing protocol governing the node MUST be notified such that corrective action can be taken. Clausen, Mase Linkbuffer [Page 7] INTERNET-DRAFT Linkbuffer 14 October 2004 2.1.2. State Transitions Five events impact the way a node determines its course of action with respect to transmitting an IP datagram: Clausen, Mase Linkbuffer [Page 8] INTERNET-DRAFT Linkbuffer 14 October 2004 Event | Cause ========================|====================================== Route Entry Updated | This event is caused by the routing | protocol when updating routing infor- | mation for a given destination. This | MUST be done in accordance with the | routing protocol specification. | | As an example, a proactive routing | protocol would cause this event for | a destination when receiving a | control message pertaining to that | destination or constructing a path | to the destination. | Route Entry Expired | This event is caused by absence of | "Route Entry Updated" events for a | given destination. This event MUST | be done in accordance with the | routing protocol specification, and | MUST take into account the time it | takes for the routing protocol to | repair/discover a route (reactive | protocols) or to update routing | table based on periodic advertise- | ments (proactive protocols). | Link Disconnected | This event is caused by the node | being informed of link disconnection | based on link layer notification. | Route Lost | This event is caused by the routing | protocol detecting that a destination | is no longer reachable. This may e.g. | be due to absence of a periodic | advertisement. | This event is symmetric to "Link | Disconnected" described above, except | that it is generated by the routing | protocol. | No Destination | This event is caused by the routing | protocol detecting that a destination | can not be discovered in the network. | The complete state changes and actions following these events can be summarised in the following table: Clausen, Mase Linkbuffer [Page 9] INTERNET-DRAFT Linkbuffer 14 October 2004 Current | Event | Next | Action State | | State | ==========|==============|===========|================== Route | Route Entry | Route | Forward all Invalid | Updated | Valid | packets in | | | "Link Buffer" | | | for destination | | | Update | | | R_dest_lifetime --------------|-----------|------------------ | Route Entry | No | Purge corre- | Expired | Route | sponding IP data- | | | grams from "Link | | | Buffer" --------------|-----------|------------------ | Link | Route | Perform | Disconnected | Invalid | "Restoration" | | | (section 2.3 ) --------------|-----------|------------------ | No | No | Purge corre- | Destination | Route | sponding IP data- | | | grams from "Link | | | Buffer" --------------|-----------|------------------ | Route | Route | None | Lost | Invalid | ----------|--------------|-----------|------------------ Route | Route Entry | Route | Update Valid | Updated | Valid | R_dest_lifetime --------------|-----------|------------------ | Route Entry | No | None | Expired | Route | --------------|-----------|------------------ | Link | Route | Perform | Disconnected | Invalid | "Restoration" | | | (section 2.3 ) --------------|-----------|------------------ | No | Route | None (*) | Destination | Invalid | --------------|-----------|------------------ | Route | Route | None | Lost | Invalid | ----------|--------------|-----------|------------------ (Continued on next page) Clausen, Mase Linkbuffer [Page 10] INTERNET-DRAFT Linkbuffer 14 October 2004 (Continued from previous page) Current | Event | Next | Action State | | State | ==========|==============|===========|================== No | Route Entry | Route | Forward all(**) Route | Updated | Valid | packets in | | | "Link Buffer" | | | for destination. | | | Update | | | R_dest_lifetime --------------|------------------------------ | Route Entry | No | None (*) | Expired | Route | --------------|-----------|------------------ | Link | No | None (*) | Disconnected | Route | --------------|-----------|------------------ | No | No | Purge corre- | Destination | Route | sponding IP data- | | | grams from "Link | | | Buffer" (**) --------------|-----------|------------------ | Route | No | None (*) | Lost | Route | | | | ----------|--------------|-----------|------------------ Transitions marked by (*) SHOULD not occur, but are included for com- pleteness of the table. The action marked by (**) represents the action when a reactive pro- tocol has succeed in discovering a route to a previously unknown des- tination. 2.1.3. State Diagram A nodes behaviour when transmitting IP datagrams, as described above, can be summarised into the following state diagram: Clausen, Mase Linkbuffer [Page 11] INTERNET-DRAFT Linkbuffer 14 October 2004 ----------- No | | Destination | ------- ------>| |--------------------- | No | | Route ----------->| Route |<--------- | Entry Route | No | | |Route | Updated Lifetime | Destination ------- |Lifetime | Expired | |Expired | | | | --------- Route Entry Updated --------- | | |---------------------->| |<-- | Route | | Route |--- Route | Invalid | Link Disconnected | Valid | | Entry | |<----------------------| |<-- Updated | | No Destination | | -->| | Link Lost | | | | | | | | --------- --------- | | -------- Link Disconnected Notice, that only "valid" transitions are included in this diagram. 2.2. Link Buffer IP datagrams, which cannot be delivered due to the corresponding entries in the routing table being in the "Route Invalid" state, MUST be stored in the Link Buffer. The IP datagrams MUST be stored until the state of the corresponding entry in the routing table changes to "No Route". 2.3. Restoration When link disconnection is detected by link layer notification as the result of a packet not able to be delivered (e.g. through absence of MAC-layer acknowledgement), the packet in the MAC queue, for which the transmission failure occurs, SHOULD be restored as an IP datagram in the Link Buffer. All other packets in the MAC queue with the same next hop MAY be restored as IP datagrams in the Link Buffer (full restoration) or may simply be cleared (simple restoration). Clausen, Mase Linkbuffer [Page 12] INTERNET-DRAFT Linkbuffer 14 October 2004 2.4. Routing Protocol Interface The interface FROM the routing protocol TO the link buffering mecha- nism is described through the events in section 2.1.2. This involves ensuring the transitions and actions as defined for the events: - Route Entry Updated - No Destination - Route Lost The interface FROM the link buffering mechanism TO the routing protocol can be described through two simple functions, which the routing proto- col must provide: - When a link-layer notification detects a link disconnection, a function "link_disconnect(neighb)" MUST be invoked in the routing protocol. Consequently, such a function MUST be pro- vided by the routing protocol. - When a packet is buffered in the Link Buffer, the routing pro- tocol MUST be notified through invoking a function "pkt_buffered(next_hop,destination)". This includes the situa- tion of notifying a reactive routing protocol that route dis- covery is needed when attempting to transmit IP datagrams to a previously unknown node. Consequently, such a function MUST be provided by the routing protocol. 3. Authors Addresses Thomas Heide Clausen, Project PCRI Pole Commun de Recherche en Informatique du plateau de Saclay, CNRS, Ecole Polytechnique, INRIA, Universite Paris Sud, Ecole polytechnique, Laboratoire dé^Â^ƒinformatique, 91128 Palaiseau Cedex, France Phone: +33 1 69 33 40 73, Email: T.Clausen@computer.org Clausen, Mase Linkbuffer [Page 13] INTERNET-DRAFT Linkbuffer 14 October 2004 Kenichi Mase, Niigata University, Niigata 950-2181, Japan, Phone: +81 25 262 7446, Email: mase@ie.niigata-u.ac.jp 4. References 1. T. Clausen, P. Jacquet, Optimized Link State Routing Protocol. Request for Comments (Experimental) 3626, October 2003 2. R. Ogier, F. Templin, M. Lewis. Topology Dissemination Based on Reverse-Path Forwarding. Request for Comments (Experimental) 3684, February 2004 3. C. Perkins, E. Belding-Royer, S. Das. Ad hoc On-Demand Distance Vec- tor (AODV) Routing, Request for Comments (Experimental) 3561, July 2003 4. D. Johnson, D. Maltz, Y. Hu, J. Jetcheva. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks, draft-ietf-manet-dsr-09.txt, work in progress, november 2001 5. S. Bradner. Key words for use in RFCs to Indicate Requirement Lev- els. Request for Comments (Best Current Practice) 2119, Internet Engineering Task Force, March 1997. 6. F. Baker. Requirements for IP Version 4 Routers Request for Comments (Standards Track) 1812, Internet Engineering Task Force, June 1995. 5. Changes This is the initial version of this specification. 6. IANA Considerations This document does currently not specify IANA considerations. 7. Security Considerations No message exchange is specified through this document. Packets from the MAC queue which are restored (extracted from the MAC queue and reinserted into the IP queue) will be restored in an unaltered state. Hence, any security and authentication information associated with restored IP datagrams remains unaltered. Clausen, Mase Linkbuffer [Page 14] INTERNET-DRAFT Linkbuffer 14 October 2004 8. Copyright Statement "Copyright (C) The Internet Society (2004). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights." "This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRE- SENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."