Internet DRAFT - draft-clausen-manet-linkbuffer
draft-clausen-manet-linkbuffer
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."
