Networking Working Group                                        P. Levis
Internet-Draft                                       Stanford University
Intended status: Informational                               A. Tavakoli
Expires: July 16, 24, 2009                                S. Dawson-Haggerty
                                                             UC Berkeley
                                                        January 12, 20, 2009

Overview of Existing Routing Protocols for Low Power and Lossy Networks
                  draft-ietf-roll-protocols-survey-03
                  draft-ietf-roll-protocols-survey-04

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   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.

   This Internet-Draft will expire on July 16, 24, 2009.

Copyright Notice

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

Abstract

   Networks of low power wireless devices introduce novel IP routing
   issues.  Low-power wireless devices, such as sensors, actuators and
   smart objects, have difficult constraints: very limited memory,
   little processing power, and long sleep periods.  As most of these
   devices are battery-powered, energy efficiency is critically
   important.  Wireless link qualities can vary significantly over time,
   requiring protocols to make agile decisions yet minimize topology
   change energy costs.  Routing over such low power and lossy networks
   has novel requirements that existing protocols may not address.  This
   document provides a brief survey of the strengths and weaknesses of
   existing protocols with respect to this class of networks.  From this
   survey it examines whether existing protocols as described in RFCs and mature drafts could IETF protocols can be
   used without modification in these networks, or whether further work
   is necessary.

Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [RFC2119].

Table of Contents

   1.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  4
   2.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Methodology  . . . . . . . . . . . . . . . . . . . . . . . . .  5  6
     3.1.  Protocols Considered . . . . . . . . . . . . . . . . . . .  6
     3.2.  Criteria . . . . . . . . . . . . . . . . . . . . . . . . .  7
     3.3.  Evaluation . . . . . . . . . . . . . . . . . . . . . . . .  7
   4.  Suitability Summary  . . . . . . . . . . . . . . . . . . . . .  7
     4.1.  Formal Definitions . . . . . . . . . . . . . . . . . . . .  8
     4.2.  Table Scalability  . . . . . . . . . . . . . . . . . . . .  8
     4.3.  Loss Response  . . . . . . . . . . . . . . . . . . . . . .  9
     4.4.  Control Cost . . . . . . . . . . . . . . . . . . . . . . .  9 10
     4.5.  Link and Node Cost . . . . . . . . . . . . . . . . . . . . 10 11
   5.  Routing Protocol Taxonomy  . . . . . . . . . . . . . . . . . . 11 12
     5.1.  Protocols Today  . . . . . . . . . . . . . . . . . . . . . 12 13
   6.  Link State Protocols . . . . . . . . . . . . . . . . . . . . . 13 14
     6.1.  OSPF & IS-IS . . . . . . . . . . . . . . . . . . . . . . . 13 14
     6.2.  OLSR & OLSRv2  . . . . . . . . . . . . . . . . . . . . . . 14
     6.3.  TBRPF  . . . . . . . . . . . . . . . . . . . . . . . . . . 15
   7.  Distance Vector protocols  . . . . . . . . . . . . . . . . . . 15
     7.1.  RIP  . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
     7.2.  Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 15 16
     7.3.  DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
     7.4.  DSR  . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 17
   8.  Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 16 17
     8.1.  IPv6 Neighbor Discovery  . . . . . . . . . . . . . . . . . 17
     8.2.  MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 17
   9.  Security Considerations  . . . . . . . . . . . . . . . . . . . 17 18
   10. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 17 18
   11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 17 18
   12. Annex A - Routing protocol scalability analysis References . . . . . . . . 18
   13. Annex B - Logarithmic scaling of control cost . . . . . . . . 21
   14. References . . . . . . . . . . 18
     12.1. Normative References . . . . . . . . . . . . . . . . . 22
     14.1. Normative References . . 18
     12.2. Informative References . . . . . . . . . . . . . . . . . 22
     14.2. Informative References . 18
   Appendix A.  Routing protocol scalability analysis . . . . . . . . 20
   Appendix B.  Logarithmic scaling of control cost . . . . . . . . . 22 24
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24 25

1.  Terminology

   AODV: Ad-hoc On Demand Vector Routing

   DSR: Dynamic Source Routing

   DYMO: Dynamic Mobile On-Demand

   IS-IS: Intermediate System to Intermediate System

   OLSR: Optimized Link State Routing

   OSPF: Open Shortest Path First

   RIP: Routing Information Protocol

   TBRPF: Topology Dissemination Based on Reverse Path Forwarding

   LLN: Low power and Lossy Network

   LSA: Link State Advertisement

   LSDB: Link State Database

   MANET: Mobile Ad-hoc Network

   MAC: Medium Access Control

   MPLS: Multiprotocol Label Switching

   MPR: Multipoint Relays

   MTU: Maximum Transmission Unit

   ROLL: Routing in Low power and Lossy Networks

   TDMA: Time Division Multiple Access

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [RFC2119].

2.  Introduction

   Wireless is increasingly important to computer networking.  As the
   technological progress underlying behind Moore's Law has reduced
   computer prices and form factors, networking
   includes has come to include not
   only servers and desktops, but laptops, palmtops, and cellphones.  As
   computing device costs and sizes have shrunk, small wireless sensors,
   actuators, and smart objects have emerged as an important next step
   in internetworking.  The sheer number of the low-
   power low-power networked
   devices means that they cannot depend on human intervention (e.g.,
   adjusting position) for good networking: they must have routing
   protocols that enable them to self-organize into multihop networks.

   Energy is a fundamental challenge in these devices.  Convenience and
   ease of use requires they be wireless and therefore battery powered.
   Correspondingly, low power operation is a key concern for these
   sensors and actuators so as to allow them to function for months and
   years without interruption.  Cost points and energy limitations cause
   these devices to have very limited resources: a few kB of RAM and a
   few MHz of CPU is typical.  As energy efficiency does not improve
   with Moore's Law, these limitations are not temporary.  This trend
   towards smaller, lower power, and more numerous devices has led to
   new low-power wireless link layers to support them.

   In practice, wireless networks observe much higher loss rates than
   wired ones do, and low-power wireless is no exception.  Furthermore,
   many of these networks will include powered as well as energy
   constrained nodes.  Nevertheless, for cost and scaling reasons, many
   of these powered devices will still have limited resources.

   These low power and lossy networks introduce constraints and
   requirements that other networks typically do not possess; for
   instance, in addition to the constraints of limited resources and
   small power sources which constrain the amount of traffic a protocol
   may generate, these applications demand an embrace of heterogeneous
   node capabilities, and good support for specific traffic patterns
   ([I-D.ietf-roll-home-routing-reqs] and
   [I-D.ietf-roll-indus-routing-reqs]).

   As they existing protocols were not designed with these requirements in
   mind, existing
   protocols they may or may not work well in LLNs.  The first step to
   reaching consensus on a routing protocol for LLNs is to decide which
   of these two is true.  If an existing protocol can meet LLN
   requirements without any changes, then barring extenuating
   circumstances, it behooves us to use an existing standard.  However,
   if no current protocol can meet LLN's requirements, then further work
   will be needed to define and standardize with a protocol that can.
   Whether or not such a protocol involves modifications to an existing
   protocol or a new protocol entirely is outside the scope of this
   document: this document simply seeks to answer the question: do LLNs
   require a new protocol specification document at all?

3.  Methodology

   To answer the question of LLNs require new protocol specification
   work, this document examines existing routing protocols and how well
   they can be applied to low power and lossy networks.  It provides a
   set of criteria with which to compare the costs and benefits of
   different protocol designs and examines existing protocols in terms
   of these criteria.

   The five criteria this

3.1.  Protocols Considered

   This document uses are derived from a set of drafts
   that describe does not seek to answer the requirements question of a few major LLN application
   scenarios.  The five criteria, presented in Section 4, are neither
   exhaustive nor complete.  Instead, they are one specific subset of
   high-level requirements shared across all of the application
   requirement drafts.  Because every application requirement draft
   specifies these criteria, then a whether there
   is any protocol anywhere which does not could meet one of
   them cannot LLN application
   requirements.  Rather, it seeks to answer whether protocols, as
   specified in current IETF standards documents, can meet such
   requirements.  If an existing protocol specification can be used without modifications or extensions.  However,
   because these criteria represent a subset of the intersection of the
   application requirements, any given application domain may impose
   unchanged, then writing additional requirements which a particular protocol may not meet. specifications is
   unnecessary.  For this reason, these criteria example, there are "necessary but not sufficient."
   A many academic papers and
   experimental protocol that does not implementations available; while one or more of
   these may meet the criteria cannot be used as
   specified, but it is possible that a protocol meets the criteria yet
   is LLN requirements, if they are not able to meet the requirements of specified in an RFC
   then a particular application
   domain.  Nevertheless, working group will need to write a protocol that meets all of the criteria
   would new RFC for them to be very promising, and deserve a closer look and consideration
   in light of
   standard.  The question this document seeks to answer is not whether
   proposed, evaluated, theoretical or hypothetical protocol designs can
   satisfy LLN application domains.

   This requirements: the question is whether existing IETF
   standards can.

   Therefore, this document considers "existing routing protocols" to be
   protocols that are specified in RFCs or, in the cases of DYMO
   [I-D.ietf-manet-dymo] or OLSRv2 [I-D.ietf-manet-olsrv2], a very
   mature draft which will most likely become that is a working item of an RFC.  We do not
   consider IETF working group.  The
   list of considered protocols is OSPF [RFC2328], IS-IS [RFC1142], RIP
   [RFC2453], OLSR [RFC3626], OLSv2 [I-D.ietf-manet-olsrv2], TBRPF
   [RFC3684], AODV [RFC3561], DYMO [I-D.ietf-manet-dymo], and DSR
   [RFC4728].  This document also considers notable variants of these
   protocols, such as Triggered RIP [RFC2091].

   This document does not consider DTN bundles [RFC5050] or the DTN
   Licklider protocol [RFC5326] as suggested by the ROLL working group
   charter, because they are not routing protocols.

   We do  This document does
   no consider the DTN routing protocol PRoPHET [I-D.irtf-dtnrg-prophet]
   because its design is based on the non-randomness of node mobility,
   which does not exist in many LLN application domains.

   This document does not examine the Network Mobility Basic Support
   Protocol (NEMO RFC 3963 [RFC3963]) because it is not a routing
   protocol.  We do  It does not examine hierarchical NEMO
   [I-D.thubert-tree-discovery] as a candidate because it only maintains
   a default route and so is insufficient for general routing.  Although
   NEMO itself is not a suitable routing solution to LLNs, some of its
   mechanisms, such as loop-free tree formation, might be useful in an
   LLN routing protocol.

   This

3.2.  Criteria

   The five criteria this document does not seek to answer uses are derived from a set of drafts
   that describe the question requirements of whether there
   is any protocol anywhere which could meet a few major LLN application
   requirements.  Rather, it seeks to answer whether protocols, as
   specified
   scenarios.  The five criteria, presented in current IETF standards documents, can meet such
   requirements.  If an existing protocol specification can be used
   unchanged, then writing additional protocol specifications is
   unnecessary.  For example, there Section 4, are neither
   exhaustive nor complete.  Instead, they are many academic papers and
   experimental protocol implementations available; while one or more specific subset of
   high-level requirements shared across all of the application
   requirement drafts.  Because every application requirement draft
   specifies these may meet LLN requirements, if they are not specified in an RFC criteria, then a working group will need to write a new RFC for protocol which does not meet one of
   them to cannot be a
   standard.  The question this document seeks to answer is not whether
   proposed, evaluated, theoretical used without modifications or hypothetical protocol designs can
   satisfy LLN requirements: extensions.  However,
   because these criteria represent a subset of the question is whether existing IETF
   standards can. intersection of the
   application requirements, any given application domain may impose
   additional requirements which a particular protocol may not meet.
   For this reason, these criteria are "necessary but not sufficient."
   A protocol that does not meet the criteria cannot be used as
   specified, but it is possible that a protocol meets the criteria yet
   is not able to meet the requirements of a particular application
   domain.  Nevertheless, a protocol that meets all of the criteria
   would be very promising, and deserve a closer look and consideration
   in light of LLN application domains.

3.3.  Evaluation

   Whether a protocol meets these criteria was judged by thinking
   through each specification and considering a hypothetical
   implementation which took advantage of the specification so as to
   perform as well as possible on the metrics. criteria.  The judgement is based
   on what a specification allows, rather than any particular
   implementation of that specification.  For example, while many DYMO
   implementations use hopcount as a routing metric, the DYMO
   specification allows a hop to add more than one to the routing
   metric, so DYMO as a specification can support some links or nodes
   being more costly than others.

4.  Suitability Summary

   In this section, we present five important requirements for routing
   in low power and lossy networks, and evaluate protocols against them.
   This evaluation attempts to take a complicated and interrelated set
   of design decisions and trade-offs and condense them to a simple
   "pass", "fail", or "?".  As with any simplification, there is a risk
   of removing some necessary nuance.  However, we believe that being
   forced to take a position on whether or not these protocols are
   acceptable according to binary criterion will be constructive.

   We derive these criteria from existing documents that describe ROLL
   network application requirements.  These metrics criteria do not encompass
   all application requirements.  Instead, they are a common set of
   routing protocol requirements that most applications domains share.
   Considering this very general and common set of requirements sets a
   minimal bar for a protocol to be generally applicable.  If a protocol
   cannot meet even these minimalist criteria, then it cannot be used
   unchanged in several major ROLL application domains and so is
   unlikely to be a good candidate for further analysis and examination. use.  Satisfying these minimal
   criteria is necessary but not sufficient: they do not represent the
   complete intersection of application requirements and applications
   introduce additional, more stringent requirements.  But this
   simplified view provides a first cut of the applicability of existing
   protocols, and those that do satisfy them might be reasonable
   candidates for further study.

   The five criteria are "table scalability", "loss response", "control
   cost", "link cost", and "node cost".  For each of these, the value
   "pass" indicates that a given protocol has satisfactory performance
   according to the metric. criterion.  The value "fail" indicates that the
   protocol does not have acceptable performance according to the
   metric,
   criterion, and that the RFC defining the protocol does not, as
   written, contain sufficient flexibility to alter the protocol to do
   so.  Finally, "?" indicates that an implementation could exhibit
   satisfactory performance while following the RFC, RFC or Internet draft,
   but that the implementation decisions necessary to do so are not
   specified and may require some exploration.  In other words, a "fail"
   means a protocol would have to be modified so it is not compliant
   with its RFC specification in order to meet the criterion, while a "?"
   means a protocol would require a supplementary document further
   constraining and specifying how a protocol should behave.

4.1.  Formal Definitions

   To provide precise definitions of these metrics, criteria, we use formal big-O
   notation, where N refers to the number of nodes in the network, D
   refers to the number of unique destinations, and L refers to the size
   of a node's local, single-hop neighborhood (the network density).  We
   explain the derivation of each metric criterion from application
   requirements in its corresponding section.

4.2.  Table Scalability

   Scalability support for large networks of sensors is highlighted as a
   key requirement by all three application requirements documents.
   Network sizes range from a minimum of 250 nodes in the home routing
   requirements [I-D.ietf-roll-home-routing-reqs] to very large networks
   of "tens of thousands to millions" of devices noted of the urban
   requirements [I-D.ietf-roll-urban-routing-reqs].  Networks are
   expected to have similar size in industrial settings, the
   requirements draft states that depths of up to 20 hops are to be
   expected [I-D.ietf-roll-indus-routing-reqs].  Given that network
   information maintained at each node is stored in routing and neighbor
   tables, along with the constrained memory of nodes, necessitates
   bounds on the size of these tables.

   This metric examines criterion indicates whether routing tables scale reasonably
   within reasonable the memory resources of low-power nodes.  According to this metric,
   criterion, routing protocols tables that scale linearly with the size of the
   network or a node's neighborhood fail.  Scaling with the size of the
   network prevents networks from growing to reasonable size, while to the sizes necessary for
   many LLN applications when faced with the memory constraints devices
   in such applications exhibit.  Similarly, scaling with the network
   density precludes dense deployments.  However, as many low-power and
   lossy networks behave principally as data collection networks and
   principally communicate through routers to data collection points in
   the larger Internet, scaling with the number of such collection
   points is reasonable.  Protocols whose state scales with the number
   of destinations pass.

   More precisely, routing table size scaling with O(N) or O(L) fails.
   A table that scales O(D) (assuming no N or L) passes.

4.3.  Loss Response

   In low power and lossy networks, links routinely come and go due to
   being close to the SINR threshold.  It is important that link churn
   not trigger unnecessary responses by the routing protocol.  This
   point is stressed in all the application requirement documents,
   pointing to the need to localize response to link failures with no
   triggering of global network re-optimization, whether for reducing
   traffic or for maintaining low route convergence times
   ([I-D.ietf-roll-home-routing-reqs],
   [I-D.ietf-roll-urban-routing-reqs], and
   [I-D.ietf-roll-indus-routing-reqs]).  The industrial routing
   requirements draft states that protocols must be able to "recompute
   paths based on underlying link characteristics which may change
   dynamically", as well as reoptimize when the device set changes to
   maintain service requirements.  The protocol should also "always be
   in the process of optimizing the system in response to changing link
   statistics."  Protocols with these properties should take care not to
   require global updates.

   A protocol which requires many link changes to propagate across the
   entire network fails.  Protocols which constrain the scope of
   information propagation to only when they affect routes to active
   destinations, or to local neighborhoods, pass.  Protocols which allow
   proactively path maintenance pass if the choice of which paths to
   maintain is user-specified.

   More precisely, loss responses that require O(N) transmissions fail,
   while responses that can rely on O(1) local broadcasts or O(D) route
   updates pass.

4.4.  Control Cost

   Battery-operated devices are a critical component of all three
   application spectrums, and as such special emphasis is placed on
   minimizing power consumption to achieve long battery lifetime,
   [I-D.ietf-roll-home-routing-reqs], with multi-year deployments being
   a common case [I-D.ietf-roll-indus-routing-reqs].  In terms of
   routing structure, any proposed LLN routing protocol ought to support
   the autonomous organization and configuration of the network at the
   lowest possible energy cost [I-D.ietf-roll-urban-routing-reqs].

   All routing protocols must transmit additional data to detect
   neighbors, build routes, transmit routing tables, or otherwise
   conduct routing.  As low-power wireless networks can have very low
   data rates, protocols which require a minimum control packet rate can
   have unbounded control overhead.  This is particularly true for
   event-driven networks, which only report data when certain conditions
   are met.  Regions of a network which never meet the condition can be
   forced to send significant control traffic even when there is no data
   to send.  For these use cases, hard-coded timing constants are
   unacceptable, because they imply a prior knowledge of the expected
   data rate.

   Of course, protocols require the ability to send at least a very
   small amount of control traffic, in order to discover a topology.
   But this bootstrapping discovery and maintenance traffic should be
   small: communicating once an hour is far more reasonable than
   communicating once a second.  So while control traffic should be
   bounded by data traffic, it requires some leeway to bootstrap and
   maintain a long-lived yet idle network.

   The control cost metric criterion is a necessary but not sufficient
   condition for a protocol to be a viable routing protocol for LLNs.
   Protocols not meeting this bound are unacceptable for use in this
   environment; however, there may be protocols which receive a "pass"
   for this
   metric criterion and yet are also unsuitable.

   In the case of control traffic, the communication rate (sum of
   transmissions and receptions at a node) is a better measure than the
   transmission rate (since energy is consumed for both transmissions
   and receptions).  Controlling the transmission rate is insufficient,
   as it would mean that the energy cost (sum of transmission and
   receptions) of control traffic could grow with O(L).

   A protocol fails the control cost criterion if its per-node control
   traffic (transmissions plus receptions) rate is not bounded by the
   data rate plus a small constant.  For example, a protocol using a
   beacon rate only passes if it can be turned arbitrarily low, in order
   to match the data rate.  Furthermore, packet losses necessitate that
   the control traffic may scale within a O(log(L)) factor of the data
   rate.  Meaning, if R is the data rate and e is the small constant,
   then a protocol's control traffic must be on the order of O(R log(L)
   + e) to pass this criteria.  The details of why O(log(L)) is
   necessary are in Annex Appenix B.

4.5.  Link and Node Cost

   These two metrics criteria specify how a protocol chooses routes for data
   packets to take through the network.  Classical routing algorithms
   typically acknowledge the differing costs of paths and may use a
   shortest path algorithm to find paths.  This is a requirement for low
   power networks, as links must be evaluated as part of an objective
   function across various metric types, such as minimizing latency and
   maximizing reliability [I-D.ietf-roll-indus-routing-reqs].

   However, in low power networks it is also desirable to account for
   the cost of routing forwarding through particular routers.  Applications
   require node or parameter constrained routing, which takes into
   account node properties and attributes such as power, memory, and
   battery life that dictate a router's willingness or ability to route
   other packets.  Home routing requirements note that devices will vary
   in their duty cycle, and that routing protocols should prefer nodes
   with permanent power [I-D.ietf-roll-home-routing-reqs].  The urban
   requirements note that routing protocols may wish to take advantage
   of differing data processing and management capabilities among
   network devices [I-D.ietf-roll-urban-routing-reqs].  Finally,
   industrial requirements cite differing lifetime requirements as an
   important factor to account for [I-D.ietf-roll-indus-routing-reqs].
   Node cost refers to the ability for a protocol to incorporate router
   properties into routing metrics and use node attributes for
   constraint-based routing.

   A "pass" indicates that the protocol contains a mechanism allowing
   these considerations to be considered when choosing routes.

5.  Routing Protocol Taxonomy

   Routing protocols broadly fall into two classes: link-state and
   distance-vector.

   A router running a link-state protocol first establishes adjacency
   with its neighbors and then reliably floods the local topology
   information in the form of a Link State Advertisement packet.  The
   collection of LSAs constitutes the Link State Database (LSDB) that
   represents the network topology, and routers synchronize their LSDBs.
   Thus each node in the network has a complete view of the network
   topology.  Each router uses the its LSDB to compute a routing table where
   each entry (reachable IP destination address) points to the next hop
   along the shortest path according to some metric.  Link state
   protocols (such as OSPF and IS-IS) support the concept of area
   (called "level" for IS-IS) whereby all the routers in the same area
   share the same view (they have the same LSDB) and areas are
   interconnected by border routers according to specific rules that
   advertise IP prefix reachability between areas.

   A distance vector protocol exchanges routing information rather than
   topological information.  A router running a distance vector protocol
   exchanges information with its "neighbors" with which it has link
   layer connectivity.  Tunneling and similar mechanisms can virtualize
   link layer connectivity to allow neighbors that are multiple layer 2
   hops away.  Rather than a map of the network topology from which each
   router can calculate routes, a distance vector protocol node has
   information on what routes its neighbors have.  Each node's set of
   available routes is the union of its neighbors routes plus a route to
   itself.  In a distance vector protocol, nodes may only advertise
   routes which are in use, enabling on-demand discovery.  In comparison
   to link state protocols, distance vector protocols have the advantage
   of only requiring neighbor routing information, but also have
   corresponding limitations which protocols must address, such as
   routing loops, count to infinity, split horizon, and slow convergence
   times.  Furthermore, routing constraints are difficult to enforce
   with distance vector protocols.

   Neighbor discovery is a critical component of any routing protocol.
   It enables a protocol to learn about which other nodes are nearby and
   which it can use as the next hop for routes.  As neighbor discovery
   is a key component of many protocols, several general protocols and
   protocol mechanisms have been designed to support it.  A protocol's
   neighbor set is defined by how many "hops" away the set reaches.  For
   example, the 1-hop neighbor set of a node is all nodes it can
   directly communicate with at the link layer, while the 2-hop neighbor
   set is its own 1-hop neighbor set and the 1-hop neighbor sets of all
   of its 1-hop neighbors.

   Because nodes often have very limited resources for storing routing
   state, protocols cannot assume that they can store complete neighbor
   information.  For example, a node with 4kB of RAM cannot store full
   neighbor state when it has 1000 other nodes nearby.  This means that
   ROLL protocols must have mechanisms to decide which of many possible
   neighbors they monitor as routable next hops.  For elements such as
   2-hop neighborhoods, these decisions can have a significant impact on
   the topology that other nodes observe, and therefore may require
   intelligent logic to prevent effects such as network partitions.

5.1.  Protocols Today

   Wired networks draw from both approaches.  OSPF or IS-IS, for
   example, are link-state protocols, while RIP is a distance-vector
   protocol.

   MANETs similarly draw from both approaches.  OLSR is a link-state
   protocol, while AODV and DYMO are distance vector protocols.  The
   general consensus in core networks is to use link state routing
   protocols as IGPs for a number of reasons: in many cases having a
   complete network topology view is required to adequately compute the
   shortest path according to some metrics.  For some applications such
   as MPLS Traffic Engineering it is even required to have the knowledge
   of the Traffic Engineering Database for constraint based routing.

   Furthermore link state protocols typically have superior convergence
   speeds (ability to find an alternate path in case of network element
   failure), are easier to debug and troubleshoot, and introduce less
   control packet overhead than distance vector protocols.  In contrast,
   distance vector protocols are simpler, require less computation, and
   have smaller storage requirements.  Most of these tradeoffs are
   similar in wireless networks, with one exception.  Because wireless
   links can suffer from significant temporal variation, link state
   protocols can have higher traffic loads as topology changes must
   propagate globally, while in a distance vector protocol a node can
   make local routing decisions with no effect on the global routing
   topology.

   One protocol, DSR, does not easily fit into one of these two classes.
   Although it is a distance vector protocol, DSR has several properties
   that make it differ from most other protocols in this class.  We
   examine these differences in our discussion of DSR.

   The next two sections summarize several well established routing
   protocols.  This  The table below shows, based on the criteria described
   above, whether these protocols meet ROLL criteria.  Annex  Appendix A
   contains the reasoning behind each value in the table.

     Protocol      Table   Loss  Control   Link Cost  Node Cost
     OSPF/IS-IS    fail    fail    fail      pass       fail
     OLSRv2        fail    fail     ?        pass       pass
     TBRPF         fail    pass    fail      pass        ?
     RIP           pass    fail    pass       ?         fail
     AODV          pass    fail    pass      fail       fail
     DYMO[-low]    pass    fail    pass       ?         fail
     DSR           fail    pass    pass      fail       fail

6.  Link State Protocols

6.1.  OSPF & IS-IS

   OSPF (specified in [RFC2328] for IPv4 and in [RFC2740] for IPv6)) is
   a link state protocol designed for routing within an Internet
   Autonomous System (AS).  OSPF provides the ability to divide a
   network into areas, which can establish a routing hierarchy.  The
   topology within an area is hidden from other areas and IP prefix
   reachability across areas (inter-area routing) is provided using
   summary LSAs.  The hierarchy implies that there is a top-level
   routing area (the backbone area) which connects other areas.  Areas
   may be connected to the back-bone area through a virtual link.  OSPF
   maintains routing adjacencies by sending hello messages.  OSPF
   calculates the shortest path to a node using link metrics (that may
   reflect the link bandwidth, propagation delay, ...).  OSPF Traffic
   Engineering (OSPF-TE, [RFC3630]) extends OSPF to include information
   on reservable, unreserved, and available bandwidth.

   IS-IS (specified in [RFC1142]) is similar in many respects to OSPF,
   but as a descendent of the OSI protocol suite differs in some places
   such as the way areas are defined and used.  However, routing
   adjacencies are also maintained by local propagation of the LSDB, and
   a shortest path computation is used over a metric space which may
   measure delay, errors, or other link properties.

6.2.  OLSR & OLSRv2

   Optimized Link State Routing (OLSR) (see [RFC3626] and
   [I-D.ietf-manet-olsrv2]) is a link state routing protocol for
   wireless mesh networks.  OLSR nodes routers flood link state advertisement
   packets throughout the entire network, such that each node has a map
   of the mesh topology.  Because link variations can lead to heavy
   flooding traffic when using a link state approach, OLSR establishes a
   topology for minimizing this communication. communication and imposes minimum time
   interval between two successive control transmissions by a router.
   Each node maintains a set of nodes called its Multipoint Relays
   (MPR), which is a subset of the one-hop neighbors whose connectivity
   covers the two-hop neighborhood.  Each node that is an MPR maintains
   a set called its MPR selectors, which are nodes that have chosen it
   to be an MPR.

   OLSR uses these two sets to apply three optimizations.  First, only
   MPRs generate link state information.  Second, nodes can use MPRs to
   limit the set of nodes that forward link state packets.  Third, an
   MPR, rather than advertise all of its links, can advertise only links
   to its MPR selectors.  Together, these three optimizations can
   greatly reduce the control traffic in dense networks, as the number
   of MPRs should not increase significantly as a network becomes
   denser.

   OLSR selects routes based on hop counts, and assumes an underlying
   protocol that determines whether a link exists between two nodes.
   OLSR's constrained optimized flooding allows it to quickly adapt to and propagate
   topology changes.

   OLSR is closely related to clustering algorithms in the wireless
   sensor networking literature, in which cluster heads are elected such
   that routing occurs over links between cluster heads and all other
   nodes are leafs that communicate to a cluster head.

6.3.  TBRPF

   Topology Dissemination Based on Reverse Path Forwarding (see
   [RFC3684]) is another proactive link state protocol.  TBRPF computes
   a source tree, which provides routes to all reachable nodes.  It
   reduces control packet overhead by having nodes only transmit a
   subset of their source tree as well as by using differential updates.

   The major difference between TBRPF and OLSR is the routing data that
   nodes advertise and who chooses to aggregate information.  In OLSR,
   nodes select neighbors to be MPRs and advertise their link state for
   them; in TBRPF, nodes elect themselves to advertise relevant link
   state based on whether it acts as a next hop.

7.  Distance Vector protocols

7.1.  RIP

   The Routing Information Protocol (RIP) (defined in [RFC2453])
   predates OSPF.  As it is a distance vector protocol, routing loops
   can occur and considerable work has been done to accelerate
   convergence since the initial RIP protocols were introduced.  RIP
   measures route cost in terms of hops, and detects routing loops by
   observing a route cost approach infinity where "infinity" is referred
   to as a maximum number of hops.  RIP is typically not appropriate for
   situations where routes need to be chosen based on real-time
   parameters such as measured delay, reliability, or load or when the
   network topology needs to be known for route computation.

   "Triggered RIP" (defined in [RFC2091]) was originally designed to
   support "on-demand" circuits.  The aim of triggered RIP is to avoid
   systematically sending the routing database on regular intervals.
   Instead, triggered RIP sends the database when there is a routing
   update or a next hop adjacency change: once neighbors have exchanged
   their routing database, only incremental updates need to be sent.
   Because incremental updates cannot depend on periodic traffic to
   overcome loses, triggered RIP uses acknowledgment based mechanisms
   for reliable delivery.

7.2.  Ad-hoc On Demand Vector Routing (AODV)

   AODV (specified in [RFC3561]) is a distance vector protocol intended
   for mobile ad-hoc networks. MANETs.  When one AODV node requires a route to another, it
   floods a request in the network to discover a route.  A depth-scoped
   flooding process avoids discovery from expanding to the most distant
   regions of the network that are in the opposite direction of the
   destination.  AODV chooses routes that have the minimum hop count.

   If an AODV route request reaches a node that has a route to the
   destination (this includes the destination itself), that node sends a
   reply along the reverse route.  All nodes along the reverse route can
   cache the route.  When routes break due to topology changes, AODV
   floods error messages and issues a new request.  Because AODV is on-
   demand it only maintains routes for active nodes.  When a link
   breaks, AODV issues a Route Error (RERR) and a new route request
   message (RREQ), with a higher sequence number so nodes do not respond
   from their route caches.  These packets can flood the entire network,
   giving loss response a fail. network.

7.3.  DYMO

   Dynamic Mobile On-Demand routing (DYMO) ([I-D.ietf-manet-dymo]) is an
   evolution of AODV.  The basic functionality is the same, but it has
   different packet formats, handling rules, and supports path
   accumulation.  Path accumulation allows a single DYMO route request
   to generate routes to all nodes along the route to that destination.
   Like AODV, DYMO uses a distance value as its routing metric which
   must be at least the hop count, but allows DYMO to represent link
   costs.  Like AODV, on link breaks DYMO issues a new route request
   message (RREQ), with a higher sequence number so nodes do not respond
   from their route caches.  Correspondingly, a route request can flood
   the entire network.

7.4.  DSR

   Dynamic Source Routing ([RFC4728]) is a distance vector protocol, but
   a DSR packet source explicitly specifies the route for each packet.
   Because the route is determined at a single place -- the source --
   DSR does not require sequence numbers or other mechanisms to prevent
   routing loops, as there is no problem of inconsistent routing tables.
   Unlike AODV and DYMO, by pushing state into packet headers, DSR does
   not require per-destination routing state.  Instead, a node
   originating packets only needs to store a spanning tree of the part
   of the network it is communicating with.

8.  Neighbor Discovery

   A limit on maintained routing state (light footprint) prevents ROLL
   protocols from assuming they know all 1-hop, 2-hop, or N-hop
   neighbors.  For this reason, while protocols such as MANET-NHDP
   ([I-D.ietf-manet-nhdp]) and IPv6's neighbor discovery ([RFC4861])
   provide basic mechanisms for discovering link-layer neighbors, not
   all of their features are relevant.  This section describes these two
   protocols, their capabilities, and how ROLL protocols could leverage
   them.

8.1.  IPv6 Neighbor Discovery

   IPv6 neighbor discovery provides mechanisms for nodes to discover
   single-hop neighbors as well as routers that can forward packets past
   the local neighborhood.  There is an implicit assumption that the
   delegation of whether a node is a router or not is static (e.g.,
   based on a wired topology).  The fact that all routers must respond
   to a Router Solicitation requires that the number of routers with a
   1-hop neighborhood is small, or there will be a reply implosion.
   Furthermore, IPv6 neighbor discovery's support of address
   autoconfiguration assumes address provisioning, in that addresses
   reflect the underlying communication topology.  IPv6 neighbor
   discovery does not consider asymmetric links.  Nevertheless, it may
   be possible to extend and adapt IPv6's mechanisms to wireless in
   order to avoid response storms and implosions.

8.2.  MANET-NHDP

   The MANET Neighborhood Discovery Protocol (MANET-NHDP) provides
   mechanisms for discovering a node's symmetric 2-hop neighborhood.  It
   maintains information on discovered links, their interfaces, status,
   and neighbor sets.  MANET-NHDP advertises a node's local link state;
   by listening to all of its 1-hop neighbor's advertisements, a node
   can compute its 2-hop neighborhood.  MANET-NHDP link state
   advertisements can include a link quality metric.  MANET-NHDP's node
   information base includes all interface addresses of each 1-hop
   neighbor: for low-power nodes, this state requirement can be
   difficult to support.

9.  Security Considerations

   This document presents, considers, and raises no security
   considerations.

10.  IANA Considerations

   This document includes no request to IANA.

11.  Acknowledgements

   The authors would like to thank all the members of the ROLL working
   group for their valuable comments, and the chairs for their helpful
   guidance.

   We are also indebted to the Sensor Network Architecture group at
   Berkeley for contributing their helpful analysis: Prabal Dutta,
   Rodrigo Fonseca, Xiaofan Jiang, Jaein Jeong, Jorge Ortiz, and Jay
   Tanega.

12.  Annex A - Routing protocol scalability analysis

   This aim of this Annex is to provide the details  References

12.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for the analysis
   routing scalability analysis.

   "OSPF & IS-IS"

   OSPF floods link state through a network.  Each router must receive
   this complete link set.  OSPF fails the table size criterion because
   it requires each router to discover each link use in the network, for a
   total routing table size which is O(N * L).  This also causes it RFCs to
   fail the control cost criterion, since this information must be
   propagated.  Furthermore, changes Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

12.2.  Informative References

   [I-D.ietf-manet-dymo]
              Chakeres, I. and C. Perkins, "Dynamic MANET On-demand
              (DYMO) Routing", draft-ietf-manet-dymo-16 (work in the link set require re-flooding
   the network link state even if the changed links were not being used.
   Since link state changes
              progress), December 2008.

   [I-D.ietf-manet-nhdp]
              Clausen, T., Dearlove, C., and J. Dean, "MANET
              Neighborhood Discovery Protocol (NHDP)",
              draft-ietf-manet-nhdp-07 (work in wireless networks are often uncorrelated
   with data traffic progress), July 2008.

   [I-D.ietf-manet-olsrv2]
              Clausen, T., Dearlove, C., and are instead caused by external (environmental)
   factors, this causes OSPF to fail both the control cost P. Jacquet, "The Optimized
              Link State Routing Protocol version 2",
              draft-ietf-manet-olsrv2-07 (work in progress), July 2008.

   [I-D.ietf-roll-home-routing-reqs]
              Porcu, G., "Home Automation Routing Requirements in Low
              Power and loss
   response criteria.  OSPF routers can impose policies on the use of
   links Lossy Networks",
              draft-ietf-roll-home-routing-reqs-06 (work in progress),
              November 2008.

   [I-D.ietf-roll-indus-routing-reqs]
              Networks, D., Thubert, P., Dwars, S., and can consider link properties (Type of Service), as the cost
   associated with an edge is configurable by the system administrator
   [RFC2328], so receive a pass for link cost.  However, there is no way
   to associate metrics with routers (as costs are only applied to
   outgoing interfaces, i.e. edges) when computing paths, T. Phinney,
              "Industrial Routing Requirements in Low Power and so fails
   the node cost criteria.  While [RFC3630] discusses paths that take
   into account node attributes, it specifically states that no known
   algorithm or mechanism currently exists for incoporating this into
   the OSPF RFC.

   IS-IS receives the same results as OSPF, because it maintains a
   consistent LSDB using similar mechanisms, and can account for link
   costs but not router costs Lossy
              Networks", draft-ietf-roll-indus-routing-reqs-03 (work in its shortest path computation.

   "OLSRv2"

   OLSRv2 is a proactive link state protocol, flooding link state
   information through a set of multipoint relays (MPRs).
              progress), December 2008.

   [I-D.ietf-roll-urban-routing-reqs]
              Dohler, M., Watteyne, T., Winter, T., Barthel, D.,
              Jacquenet, C., Madhusudan, G., and G. Chegaray, "Urban
              WSNs Routing state
   includes 1-hop neighbor information for each node Requirements in the network,
   1-hop Low Power and 2-hop information Lossy
              Networks", draft-ietf-roll-urban-routing-reqs-03 (work in
              progress), January 2009.

   [I-D.irtf-dtnrg-prophet]
              Lindgren, A. and A. Doria, "Probabilistic Routing Protocol
              for neighbors (for MPR selection), and a
   routing table (consisting of destination, and next hop), resulting Intermittently Connected Networks",
              draft-irtf-dtnrg-prophet-01 (work in
   state proportional to network size and density (O(N*L + L^2)), progress),
              November 2008.

   [I-D.thubert-tree-discovery]
              Thubert, P., Bontoux, C., Montavont, N., and
   failing the table scalability criteria.  Fisheye routing does not
   alter the table size.

   Unacceptable control traffic overhead may arise from flooding B. McCarthy,
              "Nested Nemo Tree Discovery",
              draft-thubert-tree-discovery-07 (work in progress),
              August 2008.

   [RFC1142]  Oran, D., "OSI IS-IS Intra-domain Routing Protocol",
              RFC 1142, February 1990.

   [RFC2091]  Meyer, G. and
   maintenance.  HELLO messages are periodically broadcast local beacon
   messages, but TC messages spread topology information throughout the
   network (using MPRs).  As such, control traffic is proportional to
   O(N^2).  MPRs reduce this load to O(N^2 / L).  As the number of MPRs
   is inversely proportional S. Sherry, "Triggered Extensions to the density of the network and L is
   bounded by N, this means control traffic is at best proportional RIP to
   O(N).

   Fisheye routing is a technique to reduce the frequency routing
   updates as the routing update propagates away from its source.  This
   has the potential to reduce the control overhead to acceptable
   levels,
              Support Demand Circuits", RFC 2091, January 1997.

   [RFC2328]  Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.

   [RFC2453]  Malkin, G., "RIP Version 2", STD 56, RFC 2453,
              November 1998.

   [RFC2740]  Coltun, R., Ferguson, D., and it is possible to impliment this technique without
   violating the specification because the specification does not
   require that all updates be sent with the same frequency.  However,
   there is no specification of how this should be accomplished, or a
   guarentee that implementations with different algorithms J. Moy, "OSPF for deciding
   how frequently to age IPv6",
              RFC 2740, December 1999.

   [RFC3561]  Perkins, C., Belding-Royer, E., and retransmit topology updates.  Thus, OLSR
   receives a "?" for the control traffic metric.

   Furthermore, changes in the link set may require immediately re-
   flooding the network link state even if those links were not being
   used by routing, which fails the loss response metric.

   OLSR allows for specification of link quality, S. Das, "Ad hoc On-
              Demand Distance Vector (AODV) Routing", RFC 3561,
              July 2003.

   [RFC3626]  Clausen, T. and also provides a
   'Willingness' metric to symbolize node cost, giving it a pass for
   both those metrics.

   "TBRPF"

   As a link state protocol where each node maintains a database of the
   entire network topology, TBRPF's routing table size scales with
   network size P. Jacquet, "Optimized Link State Routing
              Protocol (OLSR)", RFC 3626, October 2003.

   [RFC3630]  Katz, D., Kompella, K., and density, leading to table sizes which are O(N * L)
   when D. Yeung, "Traffic Engineering
              (TE) Extensions to OSPF Version 2", RFC 3630,
              September 2003.

   [RFC3684]  Ogier, R., Templin, F., and M. Lewis, "Topology
              Dissemination Based on Reverse-Path Forwarding (TBRPF)",
              RFC 3684, February 2004.

   [RFC3963]  Devarapalli, V., Wakikawa, R., Petrescu, A., and P.
              Thubert, "Network Mobility (NEMO) Basic Support Protocol",
              RFC 3963, January 2005.

   [RFC4728]  Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source
              Routing Protocol (DSR) for Mobile Ad Hoc Networks for
              IPv4", RFC 4728, February 2007.

   [RFC4861]  Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
              "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
              September 2007.

   [RFC5050]  Scott, K. and S. Burleigh, "Bundle Protocol
              Specification", RFC 5050, November 2007.

   [RFC5326]  Ramadas, M., Burleigh, S., and S. Farrell, "Licklider
              Transmission Protocol - Specification", RFC 5326,
              September 2008.

Appendix A.  Routing protocol scalability analysis

   This aim of this Appendix is to provide the details for the analysis
   routing scalability analysis.

   "OSPF & IS-IS"

   OSPF floods link state through a node receives disjoint network.  Each router must receive
   this complete link sets from its neighbors.  This
   causes set.  OSPF fails the protocol table size criterion because
   it requires each router to fail discover each link in the network, for a
   total routing table size criteria.  The protocol's
   use of differential updates should allow both fast response time and
   incremental which is O(N * L).  This also causes it to
   fail the control cost criterion, since this information must be
   propagated.  Furthermore, changes once in the distributed database of link set require re-flooding
   the network link state even if the changed links has been
   established.  Differential updates were not being used.
   Since link state changes in wireless networks are only used often uncorrelated
   with data traffic and are instead caused by external (environmental)
   factors, this causes OSPF to reduce fail both the control cost and loss
   response
   time to changing network conditions, not to reduce criteria.  OSPF routers can impose policies on the amount use of
   topology information sent, since each node will periodically send
   their piece
   links and can consider link properties (Type of Service), as the topology.  As a result, TBRPF fails the control
   overhead criteria.  However, its differential updates triggered cost
   associated with an edge is configurable by
   link failure do not immediately cause a global re-flooding of state
   (but only to affected routers) [RFC3684], leading to the system administrator
   [RFC2328], so receive a pass for loss
   response.

   TBRPF has a flexible neighbor management layer which enables it to
   incorporate various types of link cost.  However, there is no way
   to associate metrics with routers (as costs are only applied to
   outgoing interfaces, i.e. edges) when computing paths, and so fails
   the node cost criteria.  While [RFC3630] discusses paths that take
   into its routing decision
   by enabling a USE_METRIC flag [RFC3684].  As a result, account node attributes, it specifically states that no known
   algorithm or mechanism currently exists for incoporating this into
   the OSPF RFC.

   IS-IS receives the same results as OSPF, because it maintains a
   pass
   consistent LSDB using similar mechanisms, and can account for link cost.  It also provides
   costs but not router costs in its shortest path computation.

   "OLSRv2"

   OLSRv2 is a mechanism whereby routers can
   maintain multiple proactive link metrics to a single neighbor, some state protocol, flooding link state
   information through a set of which
   can be advertised by the multipoint relays (MPRs).  Routing state
   includes 1-hop neighbor router [RFC3684].  Although the RFC
   does not specify a policy for using these values, developing one
   could allow TBRPF to satisfy this requirement, leading to a ? information for the each node cost requirement.

   "RIP"

   RIP is a distance vector protocol: all routers maintain in the network,
   1-hop and 2-hop information for neighbors (for MPR selection), and a route to
   all other routers.  Routing table size is therefore O(N).  However,
   if destinations are known apriori,
   routing table size can be reduced to O(D), (consisting of destination, and next hop), resulting in a pass for
   state proportional to network size and density (O(N*L + L^2)), and
   failing the table scalability.  While standard RIP
   requires each node scalability criterion.

   Unacceptable control traffic overhead may arise from flooding and
   maintenance.  HELLO messages are periodically broadcast a local beacon per period, and that updates
   must be propagated by affected nodes, triggered RIP only sends
   updates when
   messages, but TC messages spread topology information throughout the
   network conditions change in response (using MPRs).  As such, control traffic is proportional to
   O(N^2).  MPRs reduce this load to O(N^2 / L).  As the data path,
   so RIP passes number of MPRs
   is inversely proportional to the control cost metric.  Loss triggers updates, only
   propagating if part density of a best route, but even if the route network and L is not
   actively being used, resulting in a fail for loss response.  The rate
   of triggered updates
   bounded by N, this means control traffic is throttled, and these are only differential
   updates, yet this still doesn't account for other control traffic (or
   tie it at best proportional to data rate) or prevent
   O(N).

   Fisheye routing is a technique to reduce the triggered frequency routing
   updates as the routing update propagates away from being
   flooded along non-active paths.  [RFC2453]

   RIP receives a ? for link cost because while current implementations
   focus on hop count its source.  This
   has the potential to reduce the control overhead to acceptable
   levels, and that it is possible to implement this technique without
   violating the metric used in [RFC2453], specification because the RFC
   also mentions specification does not
   require that more complex metrics such as differences in
   bandwidth and reliability could all updates be used. sent with the same frequency.  However,
   there is no specification of how this should be accomplished.  Thus,
   OLSR receives a "?" for the RFC also
   states that real-time metrics such as link-quality would create
   instability and control traffic criterion.  Fisheye
   routing does not alter the concept table size, so it does not modify OLSR's
   failure of node cost only appears as metrics
   assigned to external networks. the table scalability criterion.

   Furthermore, changes in the link set may require re-flooding the
   network link state even if those links were not being used by
   routing.  While RIP has OLSRv2 limits the concept rates of such floods by imposing a
   network cost, it
   minimum fixed interval between floods, this interval is insufficient to describe node properties and so
   RIP independent
   of the data rate.  OLSR therefore fails the loss response criterion.

   OLSR allows for specification of link quality, and also provides a
   'Willingness' metric to symbolize node cost criterion..

   "AODV"

   AODV table size is cost, giving it a function of the number pass for
   both those criteria.

   "TBRPF"

   As a link state protocol where each node maintains a database of communicating pairs in
   the network, scaling with O(D).  This is acceptable and so AODV
   passes the
   entire network topology, TBRPF's routing table size criteria.  As an on-demand protocol, AODV does
   not generate any traffic until data is sent, and so control traffic
   is correlated scales with the data
   network size and so it receives a pass for control
   traffic.  When density, leading to table sizes which are O(N * L)
   when a broken node receives disjoint link is detected, AODV will use a precursor
   list maintained for each destination sets from its neighbors.  This
   causes the protocol to inform downstream routers
   (with a RERR) fail the table size criterion.  The protocol's
   use of differential updates should allow both fast response time and
   incremental changes once the distributed database of links has been
   established.  Differential updates are only used to reduce response
   time to changing network conditions, not to reduce the amount of
   topology change.  However, information sent, since each node will periodically send
   their piece of the RERR message is
   forwarded by all nodes that have topology.  As a route that uses the broken link,
   even if result, TBRPF fails the route is control
   overhead criterion.  However, its differential updates triggered by
   link failure do not currently active, immediately cause a global re-flooding of state
   (but only to affected routers) [RFC3684], leading to a fail pass for loss
   response [RFC3561].

   AODV fails the
   response.

   TBRPF has a flexible neighbor management layer which enables it to
   incorporate various types of link cost metric because the only metric used is hop
   count, and this is hardcoded in the route table entry, according metrics into its routing decision
   by enabling a USE_METRIC flag [RFC3684].  As a result, it receives a
   pass for link cost.  It also provides a mechanism whereby routers can
   maintain multiple link metrics to a single neighbor, some of which
   can be advertised by the neighbor router [RFC3684].  Although the RFC [RFC3561].  It fails
   does not specify a policy for using these values, developing one
   could allow TBRPF to satisfy this requirement, leading to a ? for the
   node cost requirement because there requirement.

   "RIP"

   RIP is no way for a router to indicate its [lack of] willingness to distance vector protocol: all routers maintain a route
   while still adhering to the RFC.

   "DYMO/DYMO-low"

   The design of DYMO shares much with AODV, with some changes to remove
   precursor lists and compact various messages.  It still passes the
   all other routers.  Routing table size criteria because it only maintains routes requested by
   RREQ messages, is therefore O(N).  However,
   if destinations are known apriori, table size can be reduced to O(D),
   resulting in O(D) a pass for table size.  Control traffic (RREQ,
   RREP, scalability.  While standard RIP
   requires each node broadcast a beacon per period, and RREQ) are still driven that updates
   must be propagated by data, and hence DYMO affected nodes, triggered RIP only sends
   updates when network conditions change in response to the data path,
   so RIP passes the control cost criterion.  However, RERR messages are forwarded by any
   nodes that have  Loss triggers updates,
   only propagating if part of a route using the link, best route, but even if inactive, leading to
   a fail of the loss reponse criteria [I-D.ietf-manet-dymo].

   DYMO indicates that the "distance" of route is
   not actively being used, resulting in a link can vary from 1-65535
   [I-D.ietf-manet-dymo], leading fail for loss response.  The
   rate of triggered updates is throttled, and these are only
   differential updates, yet this still doesn't account for other
   control traffic (or tie it to data rate) or prevent the triggered
   updates from being flooded along non-active paths.  [RFC2453]

   RIP receives a ? in for link cost.  While additional
   routing information can be added DYMO messages, there cost because while current implementations
   focus on hop count and that is no mention
   of node properties, leading to a fail the metric used in node cost.

   "DSR"

   DSR performs on-demand route discovery, and source routing of
   packets.  It maintains a source route for all destinations, [RFC2453], the RFC
   also mentions that more complex metrics such as differences in
   bandwidth and reliability could be used.  However, the RFC also
   a blacklist
   states that real-time metrics such as link-quality would create
   instability and the concept of all unidirectional neighbor links [RFC4728], leading node cost only appears as metrics
   assigned to external networks.  While RIP has the concept of a total
   network cost, it is insufficient to describe node properties and so
   RIP fails the node cost criterion..

   "AODV"

   AODV table size is a function of O(D + L), failing the number of communicating pairs in
   the network, scaling with O(D).  This is acceptable and so AODV
   passes the table size criterion.
   Control  As an on-demand protocol, AODV does
   not generate any traffic until data is completely sent, and so control traffic
   is correlated with the data driven, and so DSR it receives a pass for this criteria.  Finally, a transmission failure only prompts an
   unreachable control
   traffic.  When a broken link is detected, AODV will use a precursor
   list maintained for each destination to be sent to the source inform downstream routers
   (with a RERR) of the message,
   passing topology change.  However, the RERR message is
   forwarded by all nodes that have a route that uses the broken link,
   even if the route is not currently active, leading to a fail for loss
   response criteria.

   DSR [RFC3561].

   AODV fails the link cost criterion because its source routes are
   advertised the only metric used is
   hop count, and this is hardcoded in terms of hops, such that all advertised links are
   considered equivalent.  DSR also the route table entry, according
   to the RFC [RFC3561].  It fails the node cost criterion requirement because a node has
   there is no way of indicating for a router to indicate its [lack of] willingness to serve as a
   router
   route while still adhering to the RFC.

   "DYMO/DYMO-low"

   The design of DYMO shares much with AODV, with some changes to remove
   precursor lists and forward compact various messages.

13.  Annex B - Logarithmic scaling of control cost

   To satisfy  It still passes the control cost criterion, a protocol's control
   table size criterion because it only maintains routes requested by
   RREQ messages, resulting in O(D) table size.  Control traffic
   communication rate must be bounded (RREQ,
   RREP, and RREQ) are still driven by data, and hence DYMO passes the data rate, plus
   control cost criterion.  However, RERR messages are forwarded by any
   nodes that have a small
   constant.  That is, route using the link, even if there is inactive, leading to
   a data rate R, fail of the control rate must
   O(R + e), where e is a very small constant loss reponse criterion [I-D.ietf-manet-dymo].

   DYMO indicates that the "distance" of a link can vary from 1-65535
   [I-D.ietf-manet-dymo], leading to a ? in link cost.  While additional
   routing information can be added DYMO messages, there is no mention
   of node properties, leading to a fail in node cost.

   "DSR"

   DSR performs on-demand route discovery, and source routing of
   packets.  It maintains a source route for all destinations, and also
   a blacklist of all unidirectional neighbor links [RFC4728], leading
   to a total table size of O(D + L), failing the table size criterion.
   Control traffic is completely data driven, and so DSR receives a pass
   for this criterion.  Finally, a transmission failure only prompts an
   unreachable destination to be sent to the source of the message,
   passing the loss response criterion.

   DSR fails the link cost criterion because its source routes are
   advertised only in terms of hops, such that all advertised links are
   considered equivalent.  DSR also fails the node cost criterion
   because a node has no way of indicating its willingness to serve as a
   router and forward messages.

Appendix B.  Logarithmic scaling of control cost

   To satisfy the control cost criterion, a protocol's control traffic
   communication rate must be bounded by the data rate, plus a small
   constant.  That is, if there is a data rate R, the control rate must
   O(R + e), where e is a very small constant (epsilon).  Furthermore,
   the control rate may grow logarithmically with the size of the local
   neighborhood L. Note that this is a bound: it represents the most
   traffic a protocol may send, and good protocols may send much less.
   So the control rate is bounded by O(R log(L)) + e.

   The logarithmic factor comes from the fundamental limits of any
   protocol that maintains a communication rate.  For example, consider
   e, the small constant rate of communication traffic allowed.  Since
   this rate is communication, to maintain O(e), then only one in L
   nodes may transmit per time interval defined by e: that one node has
   a transmission, and all other nodes have a reception, which prevents
   them from transmitting.  However, wireless networks are lossy.
   Suppose that the network has a 10% packet loss rate.  Then if L=10,
   the expectation is that one of the nodes will drop the packet.  Not
   hearing a transmission, it will think it can transmit.  This will
   lead to 2 transmissions.  If L=100, then one node will not hear the
   first two transmissions, and there will be 3.  The number of
   transmissions, and the communication rate, will grow with O(log(L)).

   This logarithmic bound can be prevented through explicit coordination
   (e.g., leader election), but such approaches assumes state and
   control traffic to elect leaders.  As a logarithmic factor in terms
   of density is not a large stumbling or major limitation, allowing the
   much greater protocol flexibility it enables is worth its small cost.

14.  References

14.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

14.2.  Informative References

   [I-D.ietf-manet-dymo]
              Chakeres, I. and C. Perkins, "Dynamic MANET On-demand
              (DYMO) Routing", draft-ietf-manet-dymo-16 (work in
              progress), December 2008.

   [I-D.ietf-manet-nhdp]
              Clausen, T., Dearlove, C., and J. Dean, "MANET
              Neighborhood Discovery Protocol (NHDP)",
              draft-ietf-manet-nhdp-07 (work in progress), July 2008.

   [I-D.ietf-manet-olsrv2]
              Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized
              Link State Routing Protocol version 2",
              draft-ietf-manet-olsrv2-07 (work in progress), July 2008.

   [I-D.ietf-roll-home-routing-reqs]
              Porcu, G., "Home Automation Routing Requirements in Low
              Power and Lossy Networks",
              draft-ietf-roll-home-routing-reqs-06 (work in progress),
              November 2008.

   [I-D.ietf-roll-indus-routing-reqs]
              Networks, D., Thubert, P., Dwars, S., and T. Phinney,
              "Industrial Routing Requirements in Low Power and Lossy
              Networks", draft-ietf-roll-indus-routing-reqs-03 (work in
              progress), December 2008.

   [I-D.ietf-roll-urban-routing-reqs]
              Dohler, M., Watteyne, T., Winter, T., Barthel, D.,
              Jacquenet, C., Madhusudan, G., and G. Chegaray, "Urban
              WSNs Routing Requirements in Low Power and Lossy
              Networks", draft-ietf-roll-urban-routing-reqs-03 (work in
              progress), January 2009.

   [I-D.thubert-tree-discovery]
              Thubert, P., Bontoux, C., Montavont, N., and B. McCarthy,
              "Nested Nemo Tree Discovery",
              draft-thubert-tree-discovery-07 (work in progress),
              August 2008.

   [RFC1142]  Oran, D., "OSI IS-IS Intra-domain Routing Protocol",
              RFC 1142, February 1990.

   [RFC2091]  Meyer, G. and S. Sherry, "Triggered Extensions to RIP to
              Support Demand Circuits", RFC 2091, January 1997.

   [RFC2328]  Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.

   [RFC2453]  Malkin, G., "RIP Version 2", STD 56, RFC 2453,
              November 1998.

   [RFC2740]  Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6",
              RFC 2740, December 1999.

   [RFC3561]  Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
              Demand Distance Vector (AODV) Routing", RFC 3561,
              July 2003.

   [RFC3626]  Clausen, T. and P. Jacquet, "Optimized Link State Routing
              Protocol (OLSR)", RFC 3626, October 2003.

   [RFC3630]  Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering
              (TE) Extensions to OSPF Version 2", RFC 3630,
              September 2003.

   [RFC3684]  Ogier, R., Templin, F., and M. Lewis, "Topology
              Dissemination Based on Reverse-Path Forwarding (TBRPF)",
              RFC 3684, February 2004.

   [RFC3963]  Devarapalli, V., Wakikawa, R., Petrescu, A., and P.
              Thubert, "Network Mobility (NEMO) Basic Support Protocol",
              RFC 3963, January 2005.

   [RFC4728]  Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source
              Routing Protocol (DSR) for Mobile Ad Hoc Networks for
              IPv4", RFC 4728, February 2007.

   [RFC4861]  Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
              "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
              September 2007.

   [RFC5050]  Scott, K. and S. Burleigh, "Bundle Protocol
              Specification", RFC 5050, November 2007.

   [RFC5326]  Ramadas, M., Burleigh, S., and S. Farrell, "Licklider
              Transmission Protocol - Specification", RFC 5326,
              September 2008.

Authors' Addresses

   Philip Levis
   Stanford University
   358 Gates Hall, Stanford University
   Stanford, CA  94305-9030
   USA

   Email: pal@cs.stanford.edu

   Arsalan Tavakoli
   UC Berkeley
   Soda Hall, UC Berkeley
   Berkeley, CA  94707
   USA

   Email: arsalan@eecs.berkeley.edu

   Stephen Dawson-Haggerty
   UC Berkeley
   Soda Hall, UC Berkeley
   Berkeley, CA  94707
   USA

   Email: stevedh@cs.berkeley.edu