Why Reactive Protocols are ill-suited for LLNs
draft-tripathi-roll-reactive-applicability-00

Networking Working Group                                J. Tripathi, Ed.
Internet-Draft                                    J. C. de Oliveira, Ed.
Intended status: Informational                         Drexel University
Expires: September 30, 2013                             JP. Vasseur, Ed.
                                                     Cisco Systems, Inc.
                                                          March 29, 2013

             Why Reactive Protocols are ill-suited for LLNs
             draft-tripathi-roll-reactive-applicability-00

Abstract

   This document describes serious issues regarding the use of reactive
   routing protocols in Low power and lossy network.  Routing
   requirements for various LLN deployments are studied in order to
   judge how reactive routing may or may not fit to those criteria.
   This document is intended to point out shortcomings of reactive
   protocols to operate in LLN.

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 September 30, 2013.

Copyright Notice

   Copyright (c) 2013 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

Tripathi, et al.       Expires September 30, 2013               [Page 1]
Internet-Draft    Reactive Protocol Evaluation in LLNs        March 2013

   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.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . .   3
   3.  Non-compliance with routing requirements in LLNs  . . . . . .   3
     3.1.  Inability to support P2MP traffic pattern . . . . . . . .   3
     3.2.  Inability to support MP2P traffic pattern . . . . . . . .   4
   4.  Dependency of control overhead on application module  . . . .   4
   5.  Flooding issues in LLNs . . . . . . . . . . . . . . . . . . .   5
     5.1.  Impact of flooding in battery operated nodes  . . . . . .   6
   6.  Impact on memory  . . . . . . . . . . . . . . . . . . . . . .   6
   7.  Lack of support for routing based on node capability  . . . .   6
   8.  High delay for emergency traffic  . . . . . . . . . . . . . .   7
   9.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .   8
   10. Informative References  . . . . . . . . . . . . . . . . . . .   8
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   9

1.  Introduction

   The IETF has chartered a Working Group called ROLL (Routing Over Low
   power and Lossy networks) in 2008 with the objective of specifying
   the routing requirements of Low power and Lossy Networks (LLN), and
   then either select an existing routing protocol or specify and design
   a new routing protocol in light of the unique requirements of these
   networks.  This led to the specification of a new routing protocol
   called RPL (see [RFC6550]) along with other specifications related to
   RPL.

   Despite the existence of a standard track routing protocol for LLN,
   discussions have been taken place as to whether other routing
   approaches could be taken, such as deploying reactive routing
   protocols in LLNs, such as Smart metering networks, industrial
   automation, water management networks.  The aim of this document is
   not to discuss a specific reactive routing protocol but why such
   routing protocols are ill-suited for LLNs.  For the sake of
   illustration, a reactive protocol such as LOADng
   ([I-D.clausen-lln-loadng]) is introduced in IETF, with results
   demonstrating how it offers improvement over standard AODV protocol
   for LLNs ([clausen-load-vtc]).  The aim of this document is to highly
   the number of shortcomings and technical issues in using reactive
   routing in such networks.  Note that reactive is perfectly applicable
   to other types of ad-hoc networks, this document exclusively
   discussed why reactive routing is ill-suited to LLNs such as Smart
   Grid networks, Industrial Automation networks to mention a few.

Tripathi, et al.       Expires September 30, 2013               [Page 2]
Internet-Draft    Reactive Protocol Evaluation in LLNs        March 2013

2.  Terminology

   Please refer to [ROLL-TERMS] for terminology.

3.  Non-compliance with routing requirements in LLNs

3.1.  Inability to support P2MP traffic pattern

   A LLN often has a more demanding traffic pattern than simple traffic
   between two peer nodes (P2P traffic).  The nature of deployments and
   applications running over a LLN often requires a given node to send
   the same data to multiple recipients, requiring multicasting or
   point-to-multipoint (P2MP) support from the routing protocol.  These
   destinations may be several hops away, requiring an efficient
   dissemination method.  Examples of such traffic include:

   o  management information multicasted to all nodes belonging to a
      certain region in a landscape, certain part of the manufacturing
      pipeline in an industrial automation setting, upgrade of a new
      firmware,

   o  new tariff notification to a group of users in a smart grid
      deployment,

   o  a single node providing sensed data to multiple servers.

   Indeed, [RFC5548] necessitates the support of P2MP traffic for a
   protocol to be suitable for U-LLN deployment.  It describes - "Thus,
   the protocol(s) should be optimized to support a large number of
   unicast flows from the sensing nodes or sensing clusters towards a
   LBR, or highly directed multicast or anycast flows from the nodes
   towards multiple LBRs."  and "A U-LLN may also need to support
   efficient large-scale messaging to groups of actuators."

   While a reactive routing protocol such as LOADng (see
   [I-D.clausen-lln-loadng]) may be altered to support an on-demand bi-
   directional route between any two nodes in the network, the protocol
   does not have provision to support P2MP traffic.  A naive and very
   costly solution would be to create a copy of the same message/
   application data to send for each destination.  Also, to find the
   route to each destination, the node may have to create separate route
   request (RREQ) messages and broadcast them.  This broadcast event
   creates a huge control overhead.  Number of intended destinations for
   this P2MP traffic can reach an order of hundreds or thousands, which
   is very common in a LLN deployed in urban area, or for a number of
   Advanced Metering Infrastructure (AMI) meters in a particular region
   in a smart grid deployment.  If such is the case, the protocol does
   not scale well with the network size in terms of control overhead.

Tripathi, et al.       Expires September 30, 2013               [Page 3]
Internet-Draft    Reactive Protocol Evaluation in LLNs        March 2013

   If a number of nodes are added in a region, the situation may become
   worse.  Hence, reactive routing protocols in general may become
   unsuitable to be deployed in a large scale U-LLN where P2MP traffic
   needs to be supported, even if for 1-2 times a day.

3.2.  Inability to support MP2P traffic pattern

   Likewise P2MP traffic, MP2P traffic needs to be supported by a
   routing protocol intended to be designed for an LLN.  This traffic
   pattern arises when multiple nodes may try to send data to a single
   sink at the same time.  As [RFC5548] describes, "A U-LLN should
   support occasional large-scale traffic flows from sensing nodes
   through LBRs (to nodes outside the U-LLN), such as system-wide
   alerts."  By nature, this kind of traffic may be time-critical, and
   the alerts may need to be delivered within a small time-frame.
   Similar traffic may include critical scenarios in an industrial
   automation LLN deployment, where all nodes in one area may need to
   report malfunction, fire, or other emergency in that part of the
   manufacturing plant.

   Since by default, reactive routing does not provide any efficient
   MP2P routing paradigm, all nodes will create their own route request
   (RREQ) in order to find the route to the LBR or server, if the route
   is expired or not cached.  This situation will create separate
   broadcast control messages from each node, which may lead to a
   broadcast storm in the network, similar to the P2MP traffic scenario.
   The broadcast storm may result in individual RREPs reaching the
   initiator node much later, yielding a high delay for the time-
   critical alert packets.

   Since in reactive routing for MP2P traffic is not efficient, and does
   not follow an aggregation tree, it becomes difficult to implement a
   data aggregation algorithm compatible to AODV or any of its
   derivatives as well.

4.  Dependency of control overhead on application module

   A LLN that is provisioned to be used for data gathering purpose only
   may include additional application layer modules in the future.
   Smart grid deployments may need to implement new modules of
   management traffic from the base stations to AMI meters, in addition
   to what is envisioned at present.  LLNs are evolving and therefore it
   is expected that new applications and requirements will be part of
   its future (a LLN may also be re-purposed).

   Reactive protocols discover route to destination on an on-demand
   basis.  If communication between same source-destination pair are
   spaced far apart in time, the protocol tends to discover the routes

Tripathi, et al.       Expires September 30, 2013               [Page 4]
Internet-Draft    Reactive Protocol Evaluation in LLNs        March 2013

   every time communication is requested by the application layer.  With
   reactive routing protocols, adding a new application module which
   requires more data communication in between the existing data traffic
   pattern will incur control overhead.  Hence, if a network is designed
   to operate within bounds in terms of maximum control overhead load,
   adding new application modules may well force the control overhead to
   surpass the designed maximum limit.  For example, a deployment
   requiring both MP2P and P2P application may incur more overhead than
   a deployment which is currently working with only data aggregation.
   Since LLNs will undoubtedly require more application modules and
   management modules to be augmented in future, a suitable routing
   protocol should not incur more control overhead with each added
   traffic.  For the sake of illustration, many Smart Grid networks,
   which were originally designed for the purpose of advanced metering,
   now require a multi-service networks in support of a variety of
   applications including meter reading, use of meters of alarms,
   distribution automation and electric vehicles, leading to a variety
   of traffic patterns each with different Quality of Service
   requirements.

5.  Flooding issues in LLNs

   A reactive protocol is well-suited for a traffic pattern where data
   transfer is not very frequent.  However, if the traffic pattern
   includes periodic data reporting, even as low as a few times in a
   day, the traffic pattern will induce periodic broadcast of route
   request throughout the network.  A simple example scenario can
   clarify this: assume an application in a U-LLN requires periodic data
   reporting every 6 hours or 4 times in a day - morning, noon, evening
   and night.  If the network consists of 2000 nodes, which is a very
   conservative number in a typical U-LLN, the application alone will
   create a route request broadcast for each sensor node every 11
   seconds, on average.  Thus, over the life of the sensor network, a
   reactive protocol will use more control overhead than a proactive
   protocol.

   The amount of flooding to discover routes may also be controlled via
   tweaking the route expiry time or route validity time.  If a route is
   active, nodes should not waste network resources trying to find out
   the route to the same destination.  Keeping a high expiry time for
   the routes, on the other hand may prevent flooding when next time
   data is generated for the same destination.  However, the path may
   well have been invalid by the route expiry time.  Considering LLN
   link characteristics, link flipping is a very frequent event.  Hence,
   high route expiry time may lead a node to find out invalidity of a
   path, thus forcing to flood the network again for route discovery.
   Thus, increasing route expiry time or route validity time for an
   AODV-based reactive protocol may not prove to control flooding in

Tripathi, et al.       Expires September 30, 2013               [Page 5]
Internet-Draft    Reactive Protocol Evaluation in LLNs        March 2013

   LLN.  Proactively choosing a back-up path proves to be effective way
   to ensure valid routing path in presence of link flaps.  Furthermore,
   if traffic is sent along a broken path, a new request would
   consequently be generated, thus increasing the control traffic load,
   in addition to incurring additional delays for the user data.

5.1.  Impact of flooding in battery operated nodes

   Note that there is a lot of experimental evidence supporting the
   claim that using floods or scoped floods to discover routes is ill-
   suited to low-power and lossy networks (LLNs).  This is due to the
   low-power requirement.  In low-power wireless networks, broadcast
   packets usually cost much more to transmit than unicast ones.

6.  Impact on memory

   Reactive routing protocols usually relies on route caching for
   discovered destination.  Hence, if any node participates in multiple
   active flows in the network, the node needs to store next hop (and
   validity) information for each source and destination node in the
   network.  Thus, depending on the user traffic, some nodes tend to
   increase their routing table size proportional to number of flows
   passing through themselves.  Hence, the nodes require more memory
   storage to operate successfully in these networks, depending on the
   traffic pattern.  However, characteristics of LLNs never guarantee
   enough storage space in any node for storing routing tables.  In
   LLNs, thus it is always advantageous to store route to a subset of
   nodes and still be able to find a path to any destination in the
   network.  Reactive routing protocols, in their current specification
   or any variant, fail to achieve low memory requirement in nodes.

   Destination oriented flooding in LLN, tends to worsen this situation.
   Multiple route requests may reach the same node at the same time for
   different destinations.  Even though the destination may never be
   reached through the concerned node, the node still have to process
   and re-broadcast each request, along with its neighbors.  Vital
   memory is consumed in RREQ/RREP processing and buffering in this
   method.

7.  Lack of support for routing based on node capability

   Apart from providing a route between any two nodes in the network, a
   routing protocol suitable for LLN should be able to handle additional
   constraints.  A LLN mainly consists of constrained devices, both
   functionality and memory-wise, and inherently heterogeneous in
   nature.  Hence, any routing protocol suitable for LLN should support
   node constraint based routing.  This requirement is mandated in
   [RFC5548] as follows: " the routing protocol MUST be able to

Tripathi, et al.       Expires September 30, 2013               [Page 6]
Internet-Draft    Reactive Protocol Evaluation in LLNs        March 2013

   advertise node capabilities that will be exclusively used by the
   routing protocol engine for routing decision".  For example, the
   routing protocol should avoid a node with less battery power while
   routing to reach a server.  Similarly, for industrial automation
   requirements, [RFC5673] also needs a routing protocol to provide
   device-aware routing, as it describes "The routing algorithm MUST
   support node-constrained routing (e.g., taking into account the
   existing energy state as a node constraint).  Node constraints
   include power and memory, as well as constraints placed on the device
   by the user, such as battery life".  For home routing automation,
   [RFC5826] specifies, " The routing protocol SHOULD route via mains-
   powered nodes if possible.  The routing protocol MUST support
   constraint-based routing taking into account node properties (CPU,
   memory, level of energy, sleep intervals, safety/convenience of
   changing battery)".

   Clearly, recognizing a node's capability and routing accordingly is
   an important aspect for any routing protocol designed to be suitable
   for LLNs.  However, any AODV-based protocol (such as DYMO [I-D.DYMO],
   LOADng) in their current specification, fail to provide routes based
   on any such constraint.  Currently known reactive routing protocols
   do not have any provision to determine whether the next-hop node in a
   route has enough battery power to sustain the route, or whether the
   next-hop node is main powered or provides a particular functionality.
   Thus, these protocols fail to provide requirements mandated by
   [RFC5548], [RFC5673] and [RFC5826] for routing in a LLN.

8.  High delay for emergency traffic

   Some data in a LLN are delay sensitive by nature.  While data
   generated for periodic reporting can be delivered even up to few
   seconds later, emergency alarms, fault notification and alert packets
   need to be delivered as quickly as possible.  According to [RFC5673],
   in an industrial automation setting, "Non-critical closed-loop
   applications have a latency requirement that can be as low as 100
   milliseconds but many control loops are tolerant of latencies above 1
   second".  Clearly, the types of alert packets need a path to the
   destination beforehand as soon as they are generated.  However,
   reactive protocols depend on finding a path first when data is
   generated.  Since the receipt of an RREP packet can take up to the
   network traversal time, for large networks the delivery of an
   emergency packet may take more than few hundred milliseconds.  Also,
   if this emergency situation initiates a system wide alert from all
   nodes in the region to one or multiple servers outside the LLN, each
   node will create their own broadcast to reach the destination.
   Similar to the condition in section 3, the broadcast storm may lead
   to huge delay in receipt of RREP packets, and thus delay in
   delivering the emergency packet.  The broadcast will lead to high

Tripathi, et al.       Expires September 30, 2013               [Page 7]
Internet-Draft    Reactive Protocol Evaluation in LLNs        March 2013

   control overhead, clogging the network, as well as loss of some RREQ/
   RREP packets.

9.  Acknowledgements

   TBD

10.  Informative References

   [I-D.DYMO]
              Perkins, C., Ed., Ratliff, S., Ed., and J. Dowdell, Ed.,
              "Dynamic MANET On-demand (AODVv2) Routing", Work in
              Progress, February 2013.

   [I-D.clausen-lln-loadng]
              Clausen, T., Ed., Yi, J., Ed., Niktash, A., Ed., Igarashi,
              Y., Ed., Satoh, H., Ed., Herberg, U., Ed., Lavenu, C.,
              Ed., Lys, T., Ed., Perkins, C., Ed., and J. Dean, Ed.,
              "The Lightweight On-demand Ad hoc Distance-vector Routing
              Protocol - Next Generation (LOADng)", Work in Progress,
              January 2013.

   [RFC5548]  Dohler, M., Ed., Watteyne, T., Ed., Winter, T., Ed., and
              D. Barthel, Ed., "Routing Requirements for Urban Low-Power
              and Lossy Networks", RFC 5548, May 2009.

   [RFC5673]  Pister, K., Ed., Thubert, P., Ed., Dwars, S., and T.
              Phinney, "Industrial Routing Requirements in Low-Power and
              Lossy Networks", RFC 5673, October 2009.

   [RFC5826]  Brandt, A., Buron, J., and G. Porcu, "Home Automation
              Routing Requirements in Low-Power and Lossy Networks", RFC
              5826, April 2010.

   [RFC5867]  Martocci, J., Ed., De Mil, P., Riou, N., and W. Vermeylen,
              "Building Automation Routing Requirements in Low-Power and
              Lossy Networks", RFC 5867, June 2010.

   [RFC6550]  Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R.,
              Levis, P., Pister, K., Struik, R., Vasseur, JP., and R.
              Alexander, "RPL: IPv6 Routing Protocol for Low-Power and
              Lossy Networks", RFC 6550, March 2012.

   [ROLL-TERMS]
              Vasseur, JP., "Terminology in Low power And Lossy
              Networks", Work in Progress, September 2011.

   [clausen-load-vtc]

Tripathi, et al.       Expires September 30, 2013               [Page 8]
Internet-Draft    Reactive Protocol Evaluation in LLNs        March 2013

              Clausen, T., Ed., Yi, J., Ed., and A. de Verdiere, Ed.,
              "LOADng: Towards AODV Version 2", Vehicular Technology
              Conference (VTC Fall), 2012 IEEE, September 2012.

Authors' Addresses

   Joydeep Tripathi (editor)
   Drexel University
   3141 Chestnut Street 7-313
   Philadelphia, PA  19104
   USA

   Email: jt369@drexel.edu

   Jaudelice C. de Oliveira (editor)
   Drexel University
   3141 Chestnut Street 7-313
   Philadelphia, PA  19104
   USA

   Email: jau@coe.drexel.edu

   JP Vasseur (editor)
   Cisco Systems, Inc.
   11, Rue Camille Desmoulins
   Issy Les Moulineaux  92782
   France

   Email: jpv@cisco.com

Tripathi, et al.       Expires September 30, 2013               [Page 9]