Internet DRAFT - draft-yi-loadngsmartrreq
draft-yi-loadngsmartrreq
Network Working Group J. Yi
Internet-Draft T. Clausen
Intended status: Experimental LIX, Ecole Polytechnique
Expires: January 5, 2015 July 4, 2014
Smart Route Request for Lightweight On-demand Ad hoc Distance-vector
Routing - Next Generation
draft-yi-loadngsmartrreq-02
Abstract
This document describes the Smart Route Request extension for
Lightweight Ad hoc On-Demand - Next Generation (LOADng) distance
vector routing protocol. It allows making use of existed routing
information to forward Route Request message, and helps reducing
routing overhead in LOADng.
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 January 5, 2015.
Copyright Notice
Copyright (c) 2014 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
Yi & Clausen Expires January 5, 2015 [Page 1]
Internet-Draft LOADng Collection Tree Protocol July 2014
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Applicability Statement . . . . . . . . . . . . . . . . . . . 3
4. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 4
5. Protocol Signaling and Information Bases . . . . . . . . . . . 5
6. Protocol Functioning . . . . . . . . . . . . . . . . . . . . . 5
7. Smart Route Request Message . . . . . . . . . . . . . . . . . 6
7.1. RREQ_SMART Generation . . . . . . . . . . . . . . . . . . 6
7.2. RREQ_SMART Processing . . . . . . . . . . . . . . . . . . 6
7.3. RREQ_SMART Forwarding . . . . . . . . . . . . . . . . . . 6
7.4. RREQ_SMART Transmission . . . . . . . . . . . . . . . . . 7
8. Implementation Status . . . . . . . . . . . . . . . . . . . . 7
8.1. Implementation of Ecole Polytechnique . . . . . . . . . . 8
9. Security Considerations . . . . . . . . . . . . . . . . . . . 8
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8
11.1. Normative References . . . . . . . . . . . . . . . . . . . 8
11.2. Informative References . . . . . . . . . . . . . . . . . . 9
Appendix A. LOADng Smart Route Request Control Messages using
RFC5444 . . . . . . . . . . . . . . . . . . . . . . . 9
A.1. RREQ_SMART Messages Encoding Considerations . . . . . . . 9
Appendix B. RFC5444-Specific IANA Considerations . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
Yi & Clausen Expires January 5, 2015 [Page 2]
Internet-Draft LOADng Collection Tree Protocol July 2014
1. Introduction
Smart Route Request is an extension of LOADng protocol
[I-D.clausen-lln-loadng] for use in forwarding Route Request message
(RREQ), based on the routing information already known by the LOADng
router.
In LOADng [I-D.clausen-lln-loadng], on receiving an RREQ message
destined to other routers, an intermediate router has to multicast
the RREQ message to all its neighbor routers. The Smart RREQ
specified in this document makes use of available routing information
in the local router, if possible, to reduce message multicasting. It
does not require extract message exchange, and does not introduce
computation overload.
Compared to RREQ dissemination by classical flooding, Smart RREQ can
reduce up to 90% of route discovery overhead, depending on the
scenarios applied.
2. Terminology
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].
This document uses the terminology and notation defined in
[I-D.clausen-lln-loadng].
3. Applicability Statement
This protocol:
o Is an extension of LOADng for RREQ message forwarding.
o Makes use of routes available in the local router, and forward the
RREQ message in unicast to the desired destination, if possible.
o Can reduce the overhead used for route discovery in LOADng,
especially in the scenarios where the data packets are sent to a
few concentrators in the network.
o Can work seamlessly with LOADng protocol, even with the LOADng
Routers without Smart RREQ extension.
Yi & Clausen Expires January 5, 2015 [Page 3]
Internet-Draft LOADng Collection Tree Protocol July 2014
4. Problem Statement
In route discovery of LOADng [I-D.clausen-lln-loadng], the protocol
explicitly prohibits intermediate routers from replying RREQ
messages. Only the destination is permitted to respond to an RREQ by
unicasting a Route Reply (RREP) message. For example, as shown in
Figure 1, in a LOADng network, Router A initiates a route discovery
to Router D. Even the intermediate Routers (Router B and Router C in
this case) have already available routes to Router D, they have to
broadcast the RREQ message until the messsage reaches the final
destination Router D. The Router D can then send an RREP to build the
router from Router A to Router D.
RREQ RREQ RREQ
\ / \ / \ /
A <--RREP-- B <--RREP-- C <--RREP-- D
/ \ / \ / \
Figure 1: LOADng route discovery from Router A to Router D
Eliminating intermediate RREP can reduce the control message size and
protocol complexity, but can also cause unnecessary multicast in the
network. For example, in Figure 2, Router A initiates a route
discovery to Router D. Router B, C and E have already routes to D. On
receiving the RREQ, Router B, C and E still need to multicast the
RREQ message to the whole network. The retransmission of the RREQ
would be N (N is the number of routers in the network).
_ D__
/ | \
B ----A ---C
\ | /
- E -
Figure 2: LOADng route discovery from Router A to Router D. Router B,
C and E have already routes to Router D
In AODV [RFC3561], the intermediate routers can send reply to the
originator of the router discovery. In the example of Figure 2,
Router B, C and E will send an RREP to A directly, instead of
flooding the RREQ message to the whole network. In this way, the RRE
message can be kept "local" - but with the cost of complex sequence
number check to avoid loops, and extra Gratuitous RREP message
exchange.
Yi & Clausen Expires January 5, 2015 [Page 4]
Internet-Draft LOADng Collection Tree Protocol July 2014
The Smart Route Request described in this document reduces redundant
multicast RREQ in LOADng if possible, while keeps the lightweight
nature of LOADng.
5. Protocol Signaling and Information Bases
LOADng Smart Route Request is an extension of LOADng, and thus
inherits all the information bases and signaling defined in
[I-D.clausen-lln-loadng]. Only one additional flag for RREQ message
is introduced:
RREQ.smart-rreq is a boolean flag which, when set ('1'), indicates
the message is an RREQ_SMART message, and MUST be processed
according to this specification.
6. Protocol Functioning
This document concerns only RREQ dissemination of LOADng. When a
LOADng Router initiates a route discovery, it floods an RREQ message
with RREQ.smart-rreq flag set 1 (denoted RREQ_SMART message).
On receiving the RREQ_SMART message, the intermediate LOADng Router
MUST process the message according to Section 12.2 of
[I-D.clausen-lln-loadng]. Prior to the message being transmitted,
the LOADng Router will check if there is an available Routing Tuple
to the destination of RREQ_SMART. If such Routing Tuple is found,
the LOADng Router will unicast the RREQ_SMART message to the
R_next_addr of the Routing Tuple. Or else, the RREQ_SMART message is
transmitted according to the flooding operation specified for the
network.
Figure 3 illustrates an example of operation of Smart Route Request.
Router A requires a route discovery to Router D, and thus floods a
RREQ_SMART message. Router B and C has already available routes to
Router D. They will unicast the RREQ_SMART message to Router D.
RREQ_SMART
\ / --RREQ_SMART--> --RREQ_SMART-->
A <--RREP--- B <----RREP---- C <----RREP---- D
/ \
Figure 3: LOADng route discovery from Router A to Router D with Smart
Route Request. Router B and Router C have already availalbe routes to
Router D
Yi & Clausen Expires January 5, 2015 [Page 5]
Internet-Draft LOADng Collection Tree Protocol July 2014
In the example in Figure 2, Router B, C and E will unicast the
RREQ_SMART to Router D. Although those RREQ_SMART messages will not
be processed by Router D because the messages carries longer routes,
the RREQ_SMART message is kept local, instead of being flooded to the
whole network. This is not a rare case in real application, like all
the Routers send data to a concentrator in the network.
If the Smart RREQ defined in this specification is used, the
RREQ_RETRIES parameter (defined in [I-D.clausen-lln-loadng]) MUST be
great than 1. For a route discovery process, on the first RREQ
message can be a RREQ_SMART message. For the following retries, the
RREQ.smart-rreq flag MUST be cleared ('0').
7. Smart Route Request Message
The Smart Route Request Message (RREQ_SMART) are generated by a
LOADng Router for the first try, when it has a data packet to deliver
to a destination, but the LOADng Router has no matching tuple in the
Routing Set. The basic operation follows Section 12 of
[I-D.clausen-lln-loadng], except the RREQ.smart-rreq flag is treated
differently, as specified in this section.
7.1. RREQ_SMART Generation
A LOADng Router with Smart Route Request extension generate an
RREQ_SMART message for the first try of a route discovery process,
with the following content:
o RREQ.smart-rreq := TRUE;
o All the other fields are set according to Section 12.1 of
[I-D.clausen-lln-loadng].
If there was no RREP message received after 2*NET_TRAVERSAL_TIME,
anther RREQ message MUST be initiated. The following RREQ messages
MUST set RREQ.smart-rreq to FALSE, and be treated as normal RREQ
message as specified in Section 12 of [I-D.clausen-lln-loadng].
7.2. RREQ_SMART Processing
RREQ_SMART messages are processed according to Section 12.2 of
[I-D.clausen-lln-loadng].
7.3. RREQ_SMART Forwarding
The fields of an RREQ_SMART message considered for forwarding MUST be
updated following Section 12.3 of [I-D.clausen-lln-loadng], prior to
Yi & Clausen Expires January 5, 2015 [Page 6]
Internet-Draft LOADng Collection Tree Protocol July 2014
it being transmitted.
The RREQ_SMART message is then transmitted, according to Section 7.4.
7.4. RREQ_SMART Transmission
RREQ_SMART transmission is accomplished by the following procedure:
1. Find the Routing Tuple (henceforth, the "Matching Routing Tuple")
in the Route Set, where:
* R_dest_addr = RREQ.destination; and
* R_next_addr does not equal to the interface address from which
RREQ_SMART was received.
2. If a Matching Routing Tuple is found, find the Local Interface
Tuple (henceforth, matching Local Interface Tuple) in the Local
Interface Set where:
* I_local_iface_addr_list contains R_local_iface_addr from the
Matching Routing Tuple
The RREQ_SMART is transmitted over the LOADng Interface,
identified by the Matching Interface Tuple to the neighbor LOADng
Router, identified by R_next_addr from the Matching Routing
Tuple.
3. Otherwise, the RREQ_SMART is transmitted according to Section
12.4 of [I-D.clausen-lln-loadng].
8. Implementation Status
This section records the status of known implementations of the
protocol defined by this specification at the time of posting of this
Internet-Draft, and based on a proposal described in [RFC6982]. The
description of implementations in this section is intended to assist
the IETF in its decision processes in progressing drafts to RFCs.
Please note that the listing of any individual implementation here
does not imply endorsement by the IETF. Furthermore, no effort has
been spent to verify the information presented here that was supplied
by IETF contributors. This is not intended as, and must not be
construed to be, a catalog of available implementations or their
features. Readers are advised to note that other implementations may
exist.
According to [RFC6982], "this will allow reviewers and working groups
Yi & Clausen Expires January 5, 2015 [Page 7]
Internet-Draft LOADng Collection Tree Protocol July 2014
to assign due consideration to documents that have the benefit of
running code, which may serve as evidence of valuable experimentation
and feedback that have made the implemented protocols more mature.
It is up to the individual working groups to use this information as
they see fit".
There are currently one publicly-known implementation of smart route
request extension of LOADng specified in this document.
8.1. Implementation of Ecole Polytechnique
This implementation is developed by the Networking Group at Ecole
Polytechnique and applied to LOADng [I-D.clausen-lln-loadng] for RREQ
message forwarding. It can run over real network interfaces, and can
also be integrated with the network simulator NS2. It is a Java
implementation, and can be used on any platform that includes a Java
virtual machine.
The implementation is based on -00 revision of this document, and
includes about 20 line of additional code to the LOADng
implementation. Simulation results based on NS2 have been published
in [IEEE_ICWITS2012]. The results show that in point-to-point
scenarios, Smart RREQ extension can save 30% RREQ flooding overhead
compared to LOADng; in multipoint-to-point scenarios, Smart RREQ
extension can save up to 90% RREQ flooding overhead compared to
LOADng.
9. Security Considerations
This Smart RREQ extension inherits the vulnerabilities of LOADng, as
discussed in section 18 of [I-D.clausen-lln-loadng]. No additional
vulnerability is introduced in this extension.
10. IANA Considerations
IANA is requested to ....
11. References
11.1. Normative References
[I-D.clausen-lln-loadng]
Clausen, T., Verdiere, A., Yi, J., Niktash, A., Igarashi,
Y., Satoh, H., Herberg, U., Lavenu, C., Lys, T., and J.
Dean, "The Lightweight On-demand Ad hoc Distance-vector
Yi & Clausen Expires January 5, 2015 [Page 8]
Internet-Draft LOADng Collection Tree Protocol July 2014
Routing Protocol - Next Generation (LOADng)",
draft-clausen-lln-loadng-10 (work in progress),
October 2013.
[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.
11.2. Informative References
[IEEE_ICWITS2012]
Yi, J., Clausen, T., and A. Bas, "Smart Route Request for
on-demand route discovery in constrained environments",
Proceedings of IEEE ICWITS2012, IEEE International
Conference on Wireless Information Technology and Systems,
2012.
[RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
Demand Distance Vector (AODV) Routing", RFC 3561,
July 2003.
[RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running
Code: The Implementation Status Section", RFC 6982,
July 2013.
Appendix A. LOADng Smart Route Request Control Messages using RFC5444
This section presents how the abstract LOADng Smart Route Request
messages, used throughout this specification, are mapped into
[RFC5444] messages. It only concerns the flag RREQ.smart-rreq.
A.1. RREQ_SMART Messages Encoding Considerations
This protocol makes use of RREQ message defined in
[I-D.clausen-lln-loadng]. Therefore, it reuses the RREQ Message Type
defined in [I-D.clausen-lln-loadng], and defines one additional
flags: RREQ.smart-rreq. Table 1 describes how the flag is mapped
into [RFC5444].
Yi & Clausen Expires January 5, 2015 [Page 9]
Internet-Draft LOADng Collection Tree Protocol July 2014
+-----------------+-----------------+-------------------------------+
| RREQ Element | RFC5444-Element | Considerations |
+-----------------+-----------------+-------------------------------+
| RREQ.smart-rreq | FLAGS Message | Encoded by way of a |
| | TLV | Message-Type-specific Message |
| | | TLV of type FLAGS, defined in |
| | | Table 3 |
+-----------------+-----------------+-------------------------------+
Table 1: RREQ Message Elements for Smart Route Request
Appendix B. RFC5444-Specific IANA Considerations
This document only specifies one addition flag of RREQ, which has
been allocated in "Message Types" namespace of [RFC5444], in
[I-D.clausen-lln-loadng].
IANA is requested to add a RREQ Message-Type-specific Message TLV
Type, in accordance with Section 6.2.1 of [RFC5444], with allocation
policies as specified in Table 2.
+---------+-------------+-------------------+
| Type | Description | Allocation Policy |
+---------+-------------+-------------------+
| 129 | FLAGS | |
| 130-223 | Unassigned | Expert Review |
+---------+-------------+-------------------+
Table 2: RREQ Message-Type-specific TLV Type for LOADng-CT
Allocation of the FLAGS TLV from the RREQ Message-Type-specific
Message TLV Types in Table 2 will create a new Type Extension
registry, with type extension 0, as illustrated in Table 3.
+-------+------+-----------+-----+----------------------------------+
| Name | Type | Type | Bit | Description |
| | | Extension | | |
+-------+------+-----------+-----+----------------------------------+
| FLAGS | 129 | 0 | 0 | RREQ.smart-rreq flag (i.e., the |
| | | | | RREQ message is a RREQ_SMART |
| | | | | when it is set to 1) |
| FLAGS | 129 | 1-255 | | Unassigned |
+-------+------+-----------+-----+----------------------------------+
Table 3: Message TLV Type assignment: FLAGs
Yi & Clausen Expires January 5, 2015 [Page 10]
Internet-Draft LOADng Collection Tree Protocol July 2014
Authors' Addresses
Jiazi Yi
LIX, Ecole Polytechnique
Phone: +33 1 6933 4031
Email: jiazi@jiaziyi.com
URI: http://www.jiaziyi.com/
Thomas Clausen
LIX, Ecole Polytechnique
91128 Palaiseau Cedex,
France
Phone: +33-6-6058-9349
Email: T.Clausen@computer.org
URI: http://www.thomasclausen.org
Yi & Clausen Expires January 5, 2015 [Page 11]
