Mobile Ad hoc Networks Working Group C. Perkins
Internet-Draft Futurewei
Intended status: Standards Track I. Chakeres
Expires: June 1, 2013 CenGen
November 28, 2012
Intermediate RREP for dynamic MANET On-demand (AODVv2) Routing
draft-perkins-irrep-02
Abstract
The Dynamic MANET On-demand (AODVv2) routing protocol is intended for
use by mobile routers in wireless, multihop networks. AODVv2
determines unicast routes among AODVv2 routers within the network in
an on-demand fashion, offering on-demand convergence in dynamic
topologies. This document specifies an extension to AODVv2 (and
possibly other reactive routing protocols) enabling intermediate
nodes to shorten route discovery times.
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). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
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 on June 1, 2013.
Copyright Notice
Copyright (c) 2012 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
Perkins & Chakeres Expires June 1, 2013 [Page 1]
Internet-Draft Intermediate RREP November 2012
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.
Table of Contents
1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology and Notation . . . . . . . . . . . . . . . . . . . 4
3. Unknown Prefix Convention . . . . . . . . . . . . . . . . . . 6
4. Intermediate and Unsolicited RREP . . . . . . . . . . . . . . 7
4.1. Intermediate RREP Generation . . . . . . . . . . . . . . . 7
4.2. Unsolicited RREP Generation . . . . . . . . . . . . . . . 8
5. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 9
6. Security Considerations . . . . . . . . . . . . . . . . . . . 9
7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.1. Normative References . . . . . . . . . . . . . . . . . . . 9
7.2. Informative References . . . . . . . . . . . . . . . . . . 10
Appendix A. Changes since the Previous Version . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10
Perkins & Chakeres Expires June 1, 2013 [Page 2]
Internet-Draft Intermediate RREP November 2012
1. Overview
The Dynamic MANET On-demand (AODVv2) routing protocol enables on-
demand, multihop unicast routing among participating AODVv2 routers.
The basic operations of the AODVv2 protocol are route discovery and
route maintenance. Route discovery is performed by an AODVv2 router
when one of its clients transmits a packet towards a destination for
which the router does not have a route.
During route discovery, the originator's AODVv2 router (i.e.,
OrigRtr) initiates flooding of a Route Request (RREQ) throughout the
network to find a route to a particular destination, via the AODVv2
router (i.e., TargRtr) responsible for that destination. During this
hop-by-hop flooding process, each intermediate AODVv2 router records
a route to the originator (i.e., OrigNode). If an intermediate
router has a route to the destination requested (i.e., TargNode) in
the RREQ, it may (by following the specification in this document)
supply that routing information to the originator of the RREQ. Such
an RREP message is termed an "Intermediate RREP" (iRREP). The
Intermediate router (i.e., InterRtr) also forwards another RREP
message, termed an "Unsolicited RREP" (uRREP), to the requested
destination. The Unsolicited RREP supplies TargRtr and other
intermediate routers with a route towards OrigNode. When OrigRtr
receives the iRREP, and TargRtr receives the uRREP, a bi-directional
route is established between OrigRtr and TargRtr.
In this document, RREQ always refers to the incoming RREQ message
received by InterRtr. OrigRtr, OrigNode, TargRtr, and TargNode
always refer to the nodes as defined in [I-D.ietf-manet-dymo]; they
are named from the context of the AODVv2 router originating the RREQ
message (OrigRtr).
Intermediate RREQ is particularly effective in conjunction with the
use of "expanding rings multicast", which is specified as an optional
feature in [I-D.ietf-manet-dymo]. Together, these two features
enable a simple "route repair" mechanism. When a route breaks
somewhere near the packet source (i.e., Originating Router), OrigRtr
MAY limit the flooding of a RREQ using expanding rings multicast.
Then, nearby AODVv2 routers can in many situations use iRREP to
supply a new route to the desired destination. Nearness of the
broken link relative to OrigRtr can be measured by the <msg-hop-
count> field of the RERR message (if included) indicating that a
route has broken.
When InterRtr receives an RREQ, it first uses the information in the
RREQ to update any relevant route table entries. Then, if InterRtr
is able to generate an iRREP to satisfy the RREQ, it uses the up-to-
date information in its route table to assign proper values to the
Perkins & Chakeres Expires June 1, 2013 [Page 3]
Internet-Draft Intermediate RREP November 2012
fields of the iRREP (and uRREP). In this way, message processing for
the outgoing RREP messages may be viewed as isolated from the message
processing for the incoming RREQ message.
2. Terminology and Notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in
[RFC2119]. Additionally, this document uses some terminology and
notation from [RFC5444] and [I-D.ietf-manet-dymo], duplicated here
for convenience.
AODVv2 Sequence Number (SeqNum)
An AODVv2 Sequence Number is maintained by each AODVv2 router
process. This sequence number is used by other AODVv2 routers to
identify the temporal order of routing information generated and
ensure loop-free routes.
Intermediate Route Reply (iRREP)
A RREP message that is originated by an AODVv2 router that is not
TargRtr.
Intermediate Router (InterRtr)
An AODVv2 router along a route between OrigRtr and TargRtr that
itself is not OrigRtr or TargRtr.
Originating Node (OrigNode)
The Originating Node is the source of a data packet that its
AODVv2 router has to deliver.
Originating Router (OrigRtr)
The AODVv2 router that provides network connectivity to the
Originating Node (OrigNode). OrigRtr creates a AODVv2 control
message (namely, RREQ) on behalf of OrigNode to discover a route
to communications endpoints as required by applications running on
OrigNode.
Route Reply (RREP)
A RREP message is used to supply routing information about the
TargNode to OrigRtr and the intermediate AODVv2 routers between
them.
Route Request (RREQ)
A RREQ message is used to discover a valid route to a particular
destination address, called the RREQ TargNode. When an AODVv2
router processes a RREQ, it acquires routing information on how to
Perkins & Chakeres Expires June 1, 2013 [Page 4]
Internet-Draft Intermediate RREP November 2012
reach the RREQ OrigNode.
Router Client
An AODVv2 router may be configured with a list of other IP
addresses and networks which correspond to other non-router nodes
which require the services of the AODVv2 router for route
discovery and maintenance. An AODVv2 is always its own client, so
that the list of client IP addresses is never empty.
Target Node (TargNode)
The Target Node is the ultimate destination of a data packet, and
the node for which a route discovery may be attempted by OrigRtr.
Target Router (TargRtr)
TargRtr is the AODVv2 router providing connectivity for TargNode;
in other words, TargNode is a router client of TargRtr.
Unsolicited Route Reply (uRREP)
An unsolicited RREP message is originated by an AODVv2 router, not
in response to an RREQ message by the uRREP destination. uRREP is
also sometimes called "Gratuitous RREP".
Perkins & Chakeres Expires June 1, 2013 [Page 5]
Internet-Draft Intermediate RREP November 2012
+---------------------+-------------------------------------------+
| Notation | Meaning |
+---------------------+-------------------------------------------+
| Route[Dest] | A route (or route table entry) to Dest |
| Route[Dest].{field} | A field in the route table entry |
| RREP.{field} | Field in RREP |
| -- | -- |
| MsgHdr | the RFC5444 Message Header |
| MsgTLV | an RFC5444 Message TLV |
| HopLimit | MsgHdr.<msg-hop-limit> |
| -- | -- |
| AddrBlk | an RFC5444 address block |
| AddrBlk[1] | The first address slot in AddrBlk |
| AddrBlk[N] | The Nth address slot in AddrBlk |
| AddrBlk[i].{field} | {field} value for AddrBlk[i] |
| AddrBlk[OrigNode] | AddrBlk[1] |
| AddrBlk[TargNode] | AddrBlk[2] |
| AddrBlk[uOrigNode] | AddrBlk[1] |
| AddrBlk[uTargNode] | AddrBlk[2] |
| RREP.PfxLen[i] | same as RREP.AddrBlk[i].PfxLen |
| HopCountTLV | HopCount TLV for AddrBlk addresses |
| SeqNumTLV | Sequence Number TLV for AddrBlk addresses |
| -- | -- |
| OrigRtr | RREQ Originating Router |
| OrigNode | Originating Node |
| InterRtr | Intermediate AODVv2 Router |
| TargRtr | Target Router |
| TargNode | Target Node |
| uOrigNode | IP address in the "OrigNode" uRREP slot |
| uTargNode | IP address in the "TargNode" uRREP slot |
+---------------------+-------------------------------------------+
Table 1
Note that Table 1 treats AddrBlk and TLV array values as if indexed
starting with 1 instead of 0, in contrast to RFC 5444 [RFC5444].
3. Unknown Prefix Convention
In this specification, it is possible that one of the two addresses
in the specified RREP AddrBlks has a known <prefix-length> value, but
the other address does not. In such cases, a <prefix-length> value
block MUST be supplied even though only one <prefix-length> is known.
Since RFC 5444 requires the <prefix-length>s to be supplied for both
addresses, in this document any unknown <prefix-length> in an RFC
5444 AddrBlk MUST be assigned the value of 0. Such a value for the
prefix length is not meaningful, and MUST NOT be stored as the prefix
Perkins & Chakeres Expires June 1, 2013 [Page 6]
Internet-Draft Intermediate RREP November 2012
length in any route table entry.
4. Intermediate and Unsolicited RREP
If an intermediate AODVv2 router (InterRtr) has a Route that can
satisfy an incoming RREQ, it MAY respond with an Intermediate RREP
(iRREP). As usual with any incoming RteMsg, InterRtr first updates
its route table using the information contained in the RREQ. For
instance, a route to OrigNode may be created. After the incoming
route update information is applied, InterRtr has valid routes to
both RREQ.OrigNode and RREQ.TargNode (namely, Route[OrigNode] and
Route[TargNode] respectively).
InterRtr SHOULD also issue a RREP to the RREQ TargNode, so that the
RREQ TargNode receives routing information on how to reach the RREQ
OrigNode. This RREP sent towards the RREQ TargNode is known as an
"Unsolicited RREP" (uRREP). Each AODVv2 router between InterRtr and
TargRtr that receives the uRREP, uses the uRREP information to update
their route table entry for OrigNode. The uRREP is constructed as if
it had been transmitted in response to a route discovery initiated by
TargRtr to discover a route for OrigNode.
The following conditions must be satisfied before the intermediate
router (InterRtr) can transmit iRREP and uRREP.
o InterRtr is not TargRtr
o RREQ does not contain the DestOnly message TLV
o InterRtr has a valid route for TargNode, namely Route[TargNode]
o Route[TargNode].SeqNum >= RREQ.SeqNumTLV[TargNode] (using signed
16-bit arithmetic)
4.1. Intermediate RREP Generation
The fields of the iRREP are assigned as follows.
o IP.DestinationAddr := Route[OrigNode].NextHop
o iRREP.HopLimit := Route[OrigNode].HopCount
o iRREP.AddrBlk[OrigNode] := Route[OrigNode].Addr
o iRREP.AddrBlk[TargNode] := Route[TargNode].Addr
Perkins & Chakeres Expires June 1, 2013 [Page 7]
Internet-Draft Intermediate RREP November 2012
o iRREP.SeqNumTLV[OrigNode] := Route[OrigNode].SeqNum
o iRREP.SeqNumTLV[TargNode] := Route[TargNode].Seqnum
o iRREP.HopCountTLV[TargNode] := Route[TargNode].HopCount
o If Route[TargNode].PfxLen is equal to 0, or the number of bits in
the addresses of the RREQ (32 for IPv4, 128 for IPv6), then no
<prefix-length> is included with the iRREP. Otherwise,
* iRREP.PfxLen[TargNode] := Route[TargNode].PfxLen
* iRREP.PfxLen[OrigNode] := 0
o iRREP.VALIDITY_TIME[TargNode] :=
(ACTIVE_INTERVAL+MAX_IDLETIME) - (Current_Time-Route.LastUsed)
No prefix length is needed for OrigNode, but due to RFC 5444 format
requirements, RREP.PfxLen[OrigNode] must be included if
RREP.PfxLen[TargNode] is included. In that case,
RREP.PfxLen[OrigNode] = 0. Therefore either 0 or two <prefix-length>
values are included with iRREP.AddrBlk. The VALIDITY_TIME TLV has
exactly one (1) element, which is the remaining time before the route
to TargNode expires. Since the route is a valid route, this is a
positive number.
4.2. Unsolicited RREP Generation
Since the uRREP is intended to fulfill the function of an RREP
response to an fictional RREQ message for discovering a route to
OrigNode, the order of the addresses in the uRREP AddrBlk has to be
reversed. In other words, RREQ.OrigNode has to be the IP address in
the "TargNode" slot of the uRREP, and would have been the "TargNode"
in the fictional RREQ message to which the uRREP is fictionally
responding. To reduce confusion, the IP address in the "OrigNode"
AddrBlk slot of the uRREP is denoted "uOrigNode", and it has the same
value as the IP address of the TargNode of the incoming RREQ.
Similarly, the IP address in the "TargNode" AddrBlk slot of the uRREP
is denoted "uTargNode", and it has the same value as the IP address
of the OrigNode of the incoming RREQ.
The fields of the uRREP are assigned as follows.
o IP.DestinationAddr := Route[TargNode].NextHop
o uRREP.HopLimit := Route[TargNode].HopCount
Perkins & Chakeres Expires June 1, 2013 [Page 8]
Internet-Draft Intermediate RREP November 2012
o uRREP.AddrBlk[uOrigNode] := Route[TargNode].Addr
o uRREP.AddrBlk[uTargNode] := Route[OrigNode].Addr
o uRREP.SeqNumTLV[uTargNode] := Route[OrigNode].SeqNum
o uRREP.HopCountTLV[uTargNode] := Route[OrigNode].HopCount
o If Route[OrigNode].PfxLen is equal to 0, or the number of bits in
the addresses of the RREQ (32 for IPv4, 128 for IPv6), then no
<prefix-length> is included with the uRREP AddrBlk. Otherwise,
* uRREP.PfxLen[uTargNode] := Route[OrigNode].PfxLen.
* uRREP.PfxLen[uOrigNode] := 0.
No prefix length is needed for uOrigNode == RREQ.TargNode, but due to
RFC 5444 format requirements, uRREP.PfxLen[uOrigNode] must be
included if uRREP.PfxLen[uTargNode] is included. In that case,
uRREP.PfxLen[uOrigNode] = 0. Therefore either 0 or two <prefix-
length> values are included with uRREP.AddrBlk.
5. Acknowledgments
TBD
6. Security Considerations
If AODVv2 RREP messages are not secured, then the threats are the
same. Otherwise, the ability of intermediate routers to issue RREP
on behalf of a destination node changes the security vulnerability of
the MANET. To improve security, then Intermediate Routers as well as
RREQ.OrigNode and RREQ.TargNode need to maintain security
associations with their neighbors in the MANET in order to verify
iRREP and uRREP. Doing this depends on the exact nature of the
method by which the control messages are made secure, and is beyond
the scope of this document.
7. References
7.1. Normative References
[I-D.ietf-manet-dymo]
Perkins, C. and I. Chakeres, "Dynamic MANET On-demand
(AODVv2) Routing", draft-ietf-manet-dymo-23 (work in
Perkins & Chakeres Expires June 1, 2013 [Page 9]
Internet-Draft Intermediate RREP November 2012
progress), October 2012.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
"Generalized Mobile Ad Hoc Network (MANET) Packet/Message
Format", RFC 5444, February 2009.
7.2. Informative References
[RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
Demand Distance Vector (AODV) Routing", RFC 3561,
July 2003.
Appendix A. Changes since the Previous Version
o Many changes for RFC 5444 compliance.
o Added unsolicitied RREP (uRREP).
o Added notational conventions from [I-D.ietf-manet-dymo].
o Rewrote many paragraphs to conform to above changes.
o Added section about "prefix-length"=0.
o Added this "Changes" section.
o More later...
Authors' Addresses
Charles E. Perkins
Futurewei Inc.
3300 Central Expressway
Santa Clara, CA 95053
USA
Phone: +1-408-330-5305
Email: charliep@computer.org
Perkins & Chakeres Expires June 1, 2013 [Page 10]
Internet-Draft Intermediate RREP November 2012
Ian D Chakeres
CenGen
9250 Bendix Road North
Columbia, Maryland 21045
USA
Email: ian.chakeres@gmail.com
URI: http://www.ianchak.com/
Perkins & Chakeres Expires June 1, 2013 [Page 11]