draft-ietf-roll-protocols-survey-05.txt   draft-ietf-roll-protocols-survey-06.txt 
Networking Working Group P. Levis Networking Working Group P. Levis
Internet-Draft Stanford University Internet-Draft Stanford University
Intended status: Informational A. Tavakoli Intended status: Informational A. Tavakoli
Expires: July 30, 2009 S. Dawson-Haggerty Expires: August 18, 2009 S. Dawson-Haggerty
UC Berkeley UC Berkeley
January 26, 2009 Feb 14, 2009
Overview of Existing Routing Protocols for Low Power and Lossy Networks Overview of Existing Routing Protocols for Low Power and Lossy Networks
draft-ietf-roll-protocols-survey-05 draft-ietf-roll-protocols-survey-06
Status of this Memo Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
skipping to change at page 1, line 34 skipping to change at page 1, line 34
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on July 30, 2009. This Internet-Draft will expire on August 18, 2009.
Copyright Notice Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. to this document.
Abstract Abstract
Networks of low power wireless devices introduce novel IP routing Low-power wireless devices, such as sensors, actuators and smart
issues. Low-power wireless devices, such as sensors, actuators and objects, present difficult constraints: very limited memory, little
smart objects, have difficult constraints: very limited memory, processing power, and long sleep periods. As most of these devices
little processing power, and long sleep periods. As most of these are battery-powered, energy efficiency is critically important.
devices are battery-powered, energy efficiency is critically Wireless link qualities can vary significantly over time, requiring
important. Wireless link qualities can vary significantly over time, protocols to make agile decisions yet minimize topology change energy
requiring protocols to make agile decisions yet minimize topology costs. Routing over such low power and lossy networks introduces
change energy costs. Routing over such low power and lossy networks requirements that existing routing protocols may not fully address.
has novel requirements that existing protocols may not address. This Using existing application requirements documents, this document
document provides a brief survey of the strengths and weaknesses of derives a minimal and not exhaustive set of criteria for routing in
existing protocols with respect to this class of networks. From this low-power and lossy networks. It provides a brief survey of the
survey it examines whether existing and mature IETF protocols can be strengths and weaknesses of existing protocols with respect to these
used without modification in these networks, or whether further work criteria. From this survey it examines whether existing and mature
is necessary. IETF protocols can be used without modification in these networks, or
whether further work is necessary. It concludes that no existing
IETF protocol meets the requirements of this domain.
Table of Contents Table of Contents
1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1. LLN Properties . . . . . . . . . . . . . . . . . . . . . . 5
2.2. Question to Answer . . . . . . . . . . . . . . . . . . . . 6
3. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 6 3. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1. Protocols Considered . . . . . . . . . . . . . . . . . . . 6 3.1. Protocols Considered . . . . . . . . . . . . . . . . . . . 6
3.2. Criteria . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2. Criteria . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 7 3.3. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 7
4. Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4. Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 8 4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 9
4.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 9 4.2. Routing State . . . . . . . . . . . . . . . . . . . . . . 9
4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 9 4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 10
4.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 10 4.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 10
4.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 11 4.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 11
5. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 12 5. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 12
5.1. Protocols Today . . . . . . . . . . . . . . . . . . . . . 13 5.1. Protocols Today . . . . . . . . . . . . . . . . . . . . . 13
6. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 14 6. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 14
6.1. OSPF & IS-IS . . . . . . . . . . . . . . . . . . . . . . . 14 6.1. OSPF & IS-IS . . . . . . . . . . . . . . . . . . . . . . . 14
6.2. OLSR & OLSRv2 . . . . . . . . . . . . . . . . . . . . . . 14 6.2. OLSR & OLSRv2 . . . . . . . . . . . . . . . . . . . . . . 15
6.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7. Distance Vector protocols . . . . . . . . . . . . . . . . . . 15 7. Distance Vector protocols . . . . . . . . . . . . . . . . . . 16
7.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.2. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 16 7.2. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 16
7.3. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 7.3. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.4. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 7.4. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
8. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 17 8. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 17
8.1. IPv6 Neighbor Discovery . . . . . . . . . . . . . . . . . 17 8.1. IPv6 Neighbor Discovery . . . . . . . . . . . . . . . . . 18
8.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 17 8.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 18
9. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 18 9. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 18
10. Security Considerations . . . . . . . . . . . . . . . . . . . 18 10. Security Considerations . . . . . . . . . . . . . . . . . . . 19
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19
12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 18 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 19
13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19
13.1. Normative References . . . . . . . . . . . . . . . . . . . 19 13.1. Normative References . . . . . . . . . . . . . . . . . . . 19
13.2. Informative References . . . . . . . . . . . . . . . . . . 19 13.2. Informative References . . . . . . . . . . . . . . . . . . 19
Appendix A. Routing protocol scalability analysis . . . . . . . . 21 Appendix A. Routing protocol scalability analysis . . . . . . . . 21
Appendix B. Logarithmic scaling of control cost . . . . . . . . . 24 Appendix B. Logarithmic scaling of control cost . . . . . . . . . 25
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 26
1. Terminology 1. Terminology
AODV: Ad-hoc On Demand Vector Routing AODV: Ad-hoc On Demand Vector Routing
DSR: Dynamic Source Routing DSR: Dynamic Source Routing
DYMO: Dynamic Mobile On-Demand DYMO: Dynamic Mobile On-Demand
IS-IS: Intermediate System to Intermediate System IS-IS: Intermediate System to Intermediate System
skipping to change at page 4, line 44 skipping to change at page 4, line 44
MPR: Multipoint Relays MPR: Multipoint Relays
MTU: Maximum Transmission Unit MTU: Maximum Transmission Unit
ROLL: Routing in Low power and Lossy Networks ROLL: Routing in Low power and Lossy Networks
TDMA: Time Division Multiple Access TDMA: Time Division Multiple Access
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
document are to be interpreted as described in RFC 2119 [RFC2119]. "OPTIONAL" in this document are to be interpreted as described in RFC
2119 [RFC2119].
2. Introduction 2. Introduction
Wireless is increasingly important to computer networking. As the Wireless is increasingly important to computer networking. As the
technological progress behind Moore's Law has reduced computer prices technological progress behind Moore's Law has reduced computer prices
and form factors, networking has come to include not only servers and and form factors, networking has come to include not only servers and
desktops, but laptops, palmtops, and cellphones. As computing device desktops, but laptops, palmtops, and cellphones. As computing device
costs and sizes have shrunk, small wireless sensors, actuators, and costs and sizes have shrunk, small wireless sensors, actuators, and
smart objects have emerged as an important next step in smart objects have emerged as an important next step. The sheer
internetworking. The sheer number of the low-power networked devices number of such low-power networked devices means that they cannot
means that they cannot depend on human intervention (e.g., adjusting depend on human intervention (e.g., adjusting position) for good
position) for good networking: they must have routing protocols that connectivity: they must have routing protocols that enable them to
enable them to self-organize into multihop networks. self-organize into multihop networks.
Energy is a fundamental challenge in these devices. Convenience and Energy is a fundamental challenge in these devices. Convenience and
ease of use requires they be wireless and therefore battery powered. ease of use requires they be wireless and therefore battery powered.
Correspondingly, low power operation is a key concern for these Low power operation is a key concern for these sensors and actuators
sensors and actuators so as to allow them to function for months and so as to allow them to function for months and years without
years without interruption. Cost points and energy limitations cause interruption. Cost points and energy limitations cause these devices
these devices to have very limited resources: a few kB of RAM and a to have very limited computational and storage resources: a few kB of
few MHz of CPU is typical. As energy efficiency does not improve RAM and a few MHz of CPU is typical. As energy efficiency does not
with Moore's Law, these limitations are not temporary. This trend improve with Moore's Law, these limitations are not temporary. This
towards smaller, lower power, and more numerous devices has led to trend towards smaller, lower power, and more numerous devices has led
new low-power wireless link layers to support them. to new low-power wireless link layers to support them.
In practice, wireless networks observe much higher loss rates than In practice, wireless networks observe much higher loss rates than
wired ones do, and low-power wireless is no exception. Furthermore, wired ones do, and low-power wireless is no exception. Furthermore,
many of these networks will include powered as well as energy many of these networks will include powered as well as energy
constrained nodes. Nevertheless, for cost and scaling reasons, many constrained nodes. Nevertheless, for cost and scaling reasons, many
of these powered devices will still have limited resources. of these powered devices will still have limited resources.
These low power and lossy networks introduce constraints and These low power and lossy networks introduce constraints and
requirements that other networks typically do not possess; for requirements that other networks typically do not possess; for
instance, in addition to the constraints of limited resources and instance, in addition to the constraints of limited resources and
small power sources which constrain the amount of traffic a protocol small power sources which constrain the amount of traffic a protocol
may generate, these applications demand an embrace of heterogeneous may generate, these applications demand an embrace of heterogeneous
node capabilities, and good support for specific traffic patterns node capabilities, and good support for specific traffic patterns
([I-D.ietf-roll-home-routing-reqs] and ([I-D.ietf-roll-home-routing-reqs] and
[I-D.ietf-roll-indus-routing-reqs]). [I-D.ietf-roll-indus-routing-reqs]).
As existing protocols were not designed with these requirements in 2.1. LLN Properties
mind, 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 In short, LLN routing protocols must operate under a set of
of these two is true. If an existing protocol can meet LLN constraints that traditional protocols typically do not consider.
requirements without any changes, then barring extenuating
circumstances, it behooves us to use an existing standard. However, o They need to operate with a hard, very small bound on state.
if no current protocol can meet LLN's requirements, then further work
will be needed to define and standardize with a protocol that can. o In most cases, they optimize for preserving energy.
Whether or not such a protocol involves modifications to an existing
protocol or a new protocol entirely is outside the scope of this o Typical application data patterns are not simply unicast flows.
document: this document simply seeks to answer the question: do LLNs
require a new protocol specification document at all? o They need to be effective with very small packet sizes, such as
less than 127 octets.
o They have to be very careful when trading off in-node efficiency
for generality; most LLN nodes don't have computational or memory
resources to waste.
2.2. Question to Answer
As existing protocols were not designed with all of these constraints
in mind, they have made trade-offs which may or may not be
appropriate for 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 such an existing protocol. However, if no current protocol can
meet LLN's requirements, then further work will be needed to define
and standardize a protocol that can. Whether or not such a protocol
involves extensions to an existing protocol or developing a new
protocol 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 3. Methodology
To answer the question of whether LLNs require new protocol To answer the question of whether LLNs require new protocol
specification work, this document examines existing routing protocols specification work, this document examines existing routing protocols
and how well they can be applied to low power and lossy networks. It 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 provides a set of criteria with which to compare the costs and
benefits of different protocol designs and examines existing benefits of different protocol designs and examines existing
protocols in terms of these criteria. protocols in terms of these criteria.
3.1. Protocols Considered 3.1. Protocols Considered
This document does not seek to answer the question of whether there This document does not seek to answer the question of whether there
is any protocol outside the IETF which could meet LLN application is any protocol outside the IETF which could meet LLN application
requirements. Rather, it seeks to answer whether any existing requirements. Rather, it seeks to answer whether any existing
protocols developed and specified by the IETF can meet such protocols developed and specified by the IETF can meet such
requirements. If an existing protocol specification can be used requirements. If an existing protocol specification can be used
unchanged, then writing additional protocol specifications is unchanged, then writing additional protocol specifications is
unnecessary. Thhere are many academic papers and experimental unnecessary. There are many academic papers and experimental
protocol implementations available. While one or more of these may protocol implementations available. While one or more of these may
meet LLN requirements, if they are not specified in an RFC then a meet LLN requirements, if they are not specified in an RFC then a
working group will need to write a new RFC for them to be a standard. working group will need to specify those in a new RFC for them to be
The question this document seeks to answer is not whether proposed, a standard. The question this document seeks to answer is not
evaluated, theoretical or hypothetical protocol designs can satisfy whether proposed, evaluated, theoretical or hypothetical protocol
LLN requirements: the question is whether existing IETF protocols designs can satisfy LLN requirements: the question is whether
can. existing IETF protocols can.
Therefore, this document considers "existing routing protocols" to be Therefore, this document considers "existing routing protocols" to be
protocols that are specified in RFCs or, in the cases of DYMO 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 [I-D.ietf-manet-dymo] or OLSRv2 [I-D.ietf-manet-olsrv2], a very
stable and mature draft that is a working item of an IETF working stable and mature draft that is a charter item of an active IETF
group. The list of considered protocols is OSPF [RFC2328], IS-IS working group. The list of considered protocols is OSPF [RFC2328],
[RFC1142], RIP [RFC2453], OLSR [RFC3626], OLSv2 IS-IS [RFC1142], RIP [RFC2453], OLSR [RFC3626], OLSv2
[I-D.ietf-manet-olsrv2], TBRPF [RFC3684], AODV [RFC3561], DYMO [I-D.ietf-manet-olsrv2], TBRPF [RFC3684], AODV [RFC3561], DYMO
[I-D.ietf-manet-dymo], and DSR [RFC4728]. This document also [I-D.ietf-manet-dymo], and DSR [RFC4728]. This document also
considers notable variants of these protocols, such as Triggered RIP considers notable variants of these protocols, such as Triggered RIP
[RFC2091]. [RFC2091].
Some of these protocols are still works in progress, and so are
changing over time. To enable this document to be correct yet not
dependent on this evolution, it document considers specifications as
of a specific date: November 31, 2008.
This document does not consider DTN bundles [RFC5050] or the DTN This document does not consider DTN bundles [RFC5050] or the DTN
Licklider protocol [RFC5326] as suggested by the ROLL working group Licklider protocol [RFC5326] as suggested by the ROLL working group
charter, because they are not routing protocols. This document does charter, because they are not routing protocols. This document does
no consider the DTN routing protocol PRoPHET [I-D.irtf-dtnrg-prophet] not consider the DTN routing protocol PRoPHET
because its design is based on the non-randomness of node mobility, [I-D.irtf-dtnrg-prophet] because its design is based on the non-
which does not exist in many LLN application domains. randomness of node mobility, which is not common to 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. 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.
3.2. Criteria 3.2. Criteria
The five criteria this document uses are derived from a set of drafts The five criteria this document uses are derived from a set of
that describe the requirements of a few major LLN application documents that describe the requirements of a few major LLN
scenarios. The five criteria, presented in Section 4, are neither application scenarios. The five criteria, presented in Section 4,
exhaustive nor complete. Instead, they are one specific subset of are neither exhaustive nor complete. Instead, they are one specific
high-level requirements shared across all of the application subset of high-level requirements shared across all of the
requirement drafts. Because every application requirement draft application requirement drafts. Because every application
specifies these criteria, then a protocol which does not meet one of requirement draft specifies these criteria, then a protocol which
them cannot be used without modifications or extensions. However, does not meet one of them cannot be used without modifications or
because these criteria represent a subset of the intersection of the extensions. However, because these criteria represent a subset of
application requirements, any given application domain may impose the intersection of the application requirements, any given
additional requirements which a particular protocol may not meet. application domain may impose additional requirements which a
For this reason, these criteria are "necessary but not sufficient." particular protocol may not meet. For this reason, these criteria
A protocol that does not meet the criteria cannot be used as are "necessary but not sufficient." A protocol that does not meet
specified, but it is possible that a protocol meets the criteria yet the criteria cannot be used as specified, but it is possible that a
is not able to meet the requirements of a particular application protocol meets the criteria yet is not able to meet the requirements
domain. Nevertheless, a protocol that meets all of the criteria of a particular application domain. Nevertheless, a protocol that
would be very promising, and deserve a closer look and consideration meets all of the criteria would be very promising, and deserve a
in light of LLN application domains. closer look and consideration in light of LLN application domains.
3.3. Evaluation 3.3. Evaluation
Whether a protocol meets these criteria was judged by thinking This document evaluates the above protocols by thinking through each
through each specification and considering a hypothetical specification and considering a hypothetical implementation that
implementation which took advantage of the specification so as to performs as well as possible on the criteria. The evaluation is
perform as well as possible on the criteria. The judgement is based based on what a specification allows, rather than any particular
on what a specification allows, rather than any particular
implementation of that specification. For example, while many DYMO implementation of that specification. For example, while many DYMO
implementations use hopcount as a routing metric, the DYMO implementations use hopcount as a routing metric, the DYMO
specification allows a hop to add more than one to the routing specification allows a hop to add more than one to the routing
metric, so DYMO as a specification can support some links or nodes metric, so DYMO as a specification can support some links or nodes
being more costly than others. being more costly than others. The analysis does not consider
hypothetical extensions to protocols that require additional fields
or message exchanges.
4. Criteria 4. Criteria
In this section, we present five important criteria for routing in This section presents five important criteria for routing in low
low power and lossy networks, and evaluate protocols against them. power and lossy networks. Later sections evaluate protocols against
This evaluation attempts to take a complicated and interrelated set them. The evaluation attempts to take a complicated and interrelated
of design decisions and trade-offs and condense them to a simple set of design decisions and trade-offs and condense them to a simple
"pass", "fail", or "?". As with any simplification, there is a risk "pass", "fail", or "?". As with any simplification, there is a risk
of removing some necessary nuance. However, we believe that being of removing some necessary nuance. However, we believe that being
forced to take a position on whether or not these protocols are forced to take a position on whether or not these protocols are
acceptable according to binary criterion will be constructive. acceptable according to binary criteria is constructive.
We derive these criteria from existing documents that describe ROLL We derive these criteria from existing documents that describe ROLL
network application requirements. These criteria do not encompass network application requirements [I-D.ietf-roll-home-routing-reqs]
[I-D.ietf-roll-urban-routing-reqs]
[I-D.ietf-roll-indus-routing-reqs]. These criteria do not encompass
all application requirements. Instead, they are a common set of all application requirements. Instead, they are a common set of
routing protocol requirements that most applications domains share. routing protocol requirements that the applications domains in these
Considering this very general and common set of requirements sets a documents share. Considering this very general and common set of
minimal bar for a protocol to be generally applicable. If a protocol requirements sets a minimal bar for a protocol to be applicable for
cannot meet even these minimalist criteria, then it cannot be used an LLN deployment.
unchanged in several major ROLL application domains and so is
If a protocol cannot meet 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 use within the broader scope of unlikely to be a good candidate for use within the broader scope of
all LLN application domains. Satisfying these minimal criteria is all LLN application domains. Satisfying these minimal criteria is
necessary but not sufficient: they do not represent the complete necessary but not sufficient. They do not represent the complete
intersection of application requirements and applications introduce intersection of application requirements and applications introduce
additional, more stringent requirements. But this simplified view additional, more stringent requirements. But this simplified view
provides a first cut of the applicability of existing protocols, and provides a first cut of the applicability of existing protocols, and
those that do satisfy them might be reasonable candidates for further those that do satisfy them might be reasonable candidates for further
study. study.
The five criteria are "table scalability", "loss response", "control The five criteria are "routing state", "loss response", "control
cost", "link cost", and "node cost". For each of these, the value cost", "link cost", and "node cost". For each of these, the value
"pass" indicates that a given protocol has satisfactory performance "pass" indicates that a given protocol has satisfactory performance
according to the criterion. The value "fail" indicates that the according to the criterion. The value "fail" indicates that the
protocol does not have acceptable performance according to the protocol does not have acceptable performance according to the
criterion, and that the document defining the protocol does not, as criterion, and that the document defining the protocol does not, as
written, contain sufficient flexibility to allow the protocol to meet written, contain sufficient flexibility to allow the protocol to meet
the criterion while conforming to the specification. Finally, "?" the criterion while conforming to the specification. Finally, "?"
indicates that an implementation could exhibit satisfactory indicates that an implementation could exhibit satisfactory
performance while following the protocol specification, but that the performance while following the protocol specification, but that the
implementation decisions necessary to do so are not specified and may implementation decisions necessary to do so are not specified and may
skipping to change at page 9, line 7 skipping to change at page 9, line 30
4.1. Formal Definitions 4.1. Formal Definitions
To provide precise definitions of these criteria, we use formal big-O To provide precise definitions of these criteria, we use formal big-O
notation, where N refers to the number of nodes in the network, D 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 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 of a node's local, single-hop neighborhood (the network density). We
explain the derivation of each criterion from application explain the derivation of each criterion from application
requirements in its corresponding section. requirements in its corresponding section.
4.2. Table Scalability 4.2. Routing State
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 criterion indicates whether routing tables scale reasonably This criterion indicates whether routing state scales reasonably
within the memory resources of low-power nodes. According to this within the memory resources of low-power nodes. According to this
criterion, routing tables that scale linearly with the size of the criterion, routing state that scales linearly with the size of the
network or a node's neighborhood fail. Scaling with the size of the network or a node's neighborhood fail. Scaling with the size of the
network prevents networks from growing to to the sizes necessary for network prevents networks from growing to to the sizes necessary for
many LLN applications when faced with the memory constraints devices many LLN applications when faced with the memory constraints devices
in such applications exhibit. Similarly, scaling with the network in such applications exhibit. Similarly, scaling with the network
density precludes dense deployments. However, as many low-power and density precludes dense deployments.
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. However, as many low-power and lossy networks behave principally as
A table that scales O(D) (assuming no N or L) passes. 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 state scaling with O(N) or O(L) fails. State
that scales O(D) (assuming no N or L) passes.
4.3. Loss Response 4.3. Loss Response
In low power and lossy networks, links routinely come and go due to In low power and lossy networks, links routinely come and go due to
being close to the signal-to-noise threshold at the physical layer. being close to the signal-to-noise threshold at the physical layer.
It is important that link churn not trigger unnecessary responses by It is important that link churn not trigger unnecessary responses by
the routing protocol. This point is stressed in all the application the routing protocol. This point is stressed in all the application
requirement documents, pointing to the need to localize response to requirement documents, pointing to the need to localize response to
link failures with no triggering of global network re-optimization, link failures with no triggering of global network re-optimization,
whether for reducing traffic or for maintaining low route convergence whether for reducing traffic or for maintaining low route convergence
skipping to change at page 14, line 5 skipping to change at page 14, line 21
One protocol, DSR, does not easily fit into one of these two classes. One protocol, DSR, does not easily fit into one of these two classes.
Although it is a distance vector protocol, DSR has several properties Although it is a distance vector protocol, DSR has several properties
that make it differ from most other protocols in this class. We that make it differ from most other protocols in this class. We
examine these differences in our discussion of DSR. examine these differences in our discussion of DSR.
The next two sections summarize several well established routing The next two sections summarize several well established routing
protocols. The table below shows, based on the criteria described protocols. The table below shows, based on the criteria described
above, whether these protocols meet ROLL criteria. Appendix A above, whether these protocols meet ROLL criteria. Appendix A
contains the reasoning behind each value in the table. contains the reasoning behind each value in the table.
Protocol Table Loss Control Link Cost Node Cost Protocol State Loss Control Link Cost Node Cost
OSPF/IS-IS fail fail fail pass fail OSPF/IS-IS fail fail fail pass fail
OLSRv2 fail ? ? pass pass OLSRv2 fail ? ? pass pass
TBRPF fail pass fail pass ? TBRPF fail pass fail pass ?
RIP pass fail pass ? fail RIP pass fail pass ? fail
AODV pass fail pass fail fail AODV pass fail pass fail fail
DYMO[-low] pass fail pass ? fail DYMO pass ? pass ? fail
DSR fail pass pass fail fail DSR fail pass pass fail fail
Figure 1 Figure 1
6. Link State Protocols 6. Link State Protocols
6.1. OSPF & IS-IS 6.1. OSPF & IS-IS
OSPF (specified in [RFC2328] for IPv4 and in [RFC2740] for IPv6)) is OSPF (specified in [RFC2328] for IPv4 and in [RFC2740] for IPv6)) is
a link state protocol designed for routing within an Internet a link state protocol designed for routing within an Internet
skipping to change at page 14, line 47 skipping to change at page 15, line 18
such as the way areas are defined and used. However, routing such as the way areas are defined and used. However, routing
adjacencies are also maintained by local propagation of the LSDB, and adjacencies are also maintained by local propagation of the LSDB, and
a shortest path computation is used over a metric space which may a shortest path computation is used over a metric space which may
measure delay, errors, or other link properties. measure delay, errors, or other link properties.
6.2. OLSR & OLSRv2 6.2. OLSR & OLSRv2
Optimized Link State Routing (OLSR) (see [RFC3626] and Optimized Link State Routing (OLSR) (see [RFC3626] and
[I-D.ietf-manet-olsrv2]) is a link state routing protocol for MANETs. [I-D.ietf-manet-olsrv2]) is a link state routing protocol for MANETs.
OLSR routers flood link state advertisement packets throughout the OLSR routers flood link state advertisement packets throughout the
entire network, such that each node has a map of the mesh topology. entire network, such that each node has a map of the network
Because link variations can lead to heavy flooding traffic when using topology. Because link variations can lead to heavy flooding traffic
a link state approach, OLSR establishes a topology for minimizing when using a link state approach, OLSR establishes a topology for
this communication, imposes minimum time interval between two minimizing this communication, imposes minimum time interval between
successive control transmissions by a router, and makes triggered two successive control transmissions by a router, and makes triggered
updates optional. Each node maintains a set of nodes called its updates optional. Each node maintains a set of nodes called its
Multipoint Relays (MPR), which is a subset of the one-hop neighbors Multipoint Relays (MPR), which is a subset of the one-hop neighbors
whose connectivity covers the two-hop neighborhood. Each node that whose connectivity covers the two-hop neighborhood. Each node that
is an MPR maintains a set called its MPR selectors, which are nodes is an MPR maintains a set called its MPR selectors, which are nodes
that have chosen it to be an MPR. that have chosen it to be an MPR.
OLSR uses these two sets to apply three optimizations. First, only OLSR uses these two sets to apply three optimizations. First, only
MPRs generate link state information. Second, nodes use MPRs to MPRs generate link state information. Second, nodes use MPRs to
limit the set of nodes that forward link state packets. Third, an limit the set of nodes that forward link state packets. Third, an
MPR, rather than advertise all of its links, can advertise only links MPR, rather than advertise all of its links, can advertise only links
skipping to change at page 15, line 33 skipping to change at page 15, line 51
topology changes. topology changes.
OLSR is closely related to clustering algorithms in the wireless OLSR is closely related to clustering algorithms in the wireless
sensor networking literature, in which cluster heads are elected such sensor networking literature, in which cluster heads are elected such
that routing occurs over links between cluster heads and all other that routing occurs over links between cluster heads and all other
nodes are leaves that communicate to a cluster head. nodes are leaves that communicate to a cluster head.
6.3. TBRPF 6.3. TBRPF
Topology Dissemination Based on Reverse Path Forwarding (see Topology Dissemination Based on Reverse Path Forwarding (see
[RFC3684]) is another proactive link state protocol. TBRPF computes [RFC3684]) is another proactive link state protocol for MANETs.
a source tree, which provides routes to all reachable nodes. It
reduces control packet overhead by having nodes only transmit a TBRPF computes a source tree, which provides routes to all reachable
subset of their source tree as well as by using differential updates. 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 The major difference between TBRPF and OLSR is the routing data that
nodes advertise and who chooses to aggregate information. In OLSR, nodes advertise and who chooses to aggregate information. In OLSR,
nodes select neighbors to be MPRs and advertise their link state for nodes select neighbors to be MPRs and advertise their link state for
them; in TBRPF, nodes elect themselves to advertise relevant link them; in TBRPF, nodes elect themselves to advertise relevant link
state based on whether it acts as a next hop. state based on whether it acts as a next hop.
7. Distance Vector protocols 7. Distance Vector protocols
7.1. RIP 7.1. RIP
skipping to change at page 16, line 24 skipping to change at page 16, line 43
systematically sending the routing database on regular intervals. systematically sending the routing database on regular intervals.
Instead, triggered RIP sends the database when there is a routing Instead, triggered RIP sends the database when there is a routing
update or a next hop adjacency change: once neighbors have exchanged update or a next hop adjacency change: once neighbors have exchanged
their routing database, only incremental updates need to be sent. their routing database, only incremental updates need to be sent.
Because incremental updates cannot depend on periodic traffic to Because incremental updates cannot depend on periodic traffic to
overcome loses, triggered RIP uses acknowledgment based mechanisms overcome loses, triggered RIP uses acknowledgment based mechanisms
for reliable delivery. for reliable delivery.
7.2. Ad-hoc On Demand Vector Routing (AODV) 7.2. Ad-hoc On Demand Vector Routing (AODV)
AODV (specified in [RFC3561]) is a distance vector protocol intended AODV (specified in [RFC3561]) is a distance vector protocol for
for MANETs. When one AODV node requires a route to another, it MANETs. When one AODV node requires a route to another, it floods a
floods a request in the network to discover a route. A depth-scoped request in the network to discover a route. A depth-scoped flooding
flooding process avoids discovery from expanding to the most distant process avoids discovery from expanding to the most distant regions
regions of the network that are in the opposite direction of the of the network that are in the opposite direction of the destination.
destination. AODV chooses routes that have the minimum hop count. AODV chooses routes that have the minimum hop count.
If an AODV route request reaches a node that has a route to the If an AODV route request reaches a node that has a route to the
destination (this includes the destination itself), that node sends a destination (this includes the destination itself), that node sends a
reply along the reverse route. All nodes along the reverse route can reply along the reverse route. All nodes along the reverse route can
cache the route. When routes break due to topology changes, AODV cache the route. When routes break due to topology changes, AODV
floods error messages and issues a new request. Because AODV is on- floods error messages and issues a new request. Because AODV is on-
demand it only maintains routes for active nodes. When a link demand it only maintains routes for active nodes. When a link
breaks, AODV issues a Route Error (RERR) and a new route request breaks, AODV issues a Route Error (RERR) and a new route request
message (RREQ), with a higher sequence number so nodes do not respond message (RREQ), with a higher sequence number so nodes do not respond
from their route caches. These packets can flood the entire network. from their route caches. These packets can flood the entire network.
skipping to change at page 17, line 9 skipping to change at page 17, line 28
to generate routes to all nodes along the route to that destination. to generate routes to all nodes along the route to that destination.
Like AODV, DYMO uses a distance value as its routing metric which 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 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 costs. Like AODV, on link breaks DYMO issues a new route request
message (RREQ), with a higher sequence number so nodes do not respond message (RREQ), with a higher sequence number so nodes do not respond
from their route caches. Correspondingly, a route request can flood from their route caches. Correspondingly, a route request can flood
the entire network. the entire network.
7.4. DSR 7.4. DSR
Dynamic Source Routing ([RFC4728]) is a distance vector protocol, but Dynamic Source Routing ([RFC4728]) is a distance vector protocol for
a DSR packet source explicitly specifies the route for each packet. MANETs, but a DSR packet source explicitly specifies the route for
Because the route is determined at a single place -- the source -- each packet. Because the route is determined at a single place --
DSR does not require sequence numbers or other mechanisms to prevent the source -- DSR does not require sequence numbers or other
routing loops, as there is no problem of inconsistent routing tables. mechanisms to prevent routing loops, as there is no problem of
Unlike AODV and DYMO, by pushing state into packet headers, DSR does inconsistent routing tables. Unlike AODV and DYMO, by pushing state
not require per-destination routing state. Instead, a node into packet headers, DSR does not require per-destination routing
originating packets only needs to store a spanning tree of the part state. Instead, a node originating packets only needs to store a
of the network it is communicating with. spanning tree of the part of the network it is communicating with.
8. Neighbor Discovery 8. Neighbor Discovery
A limit on maintained routing table size (light footprint) prevents A limit on maintained routing state (light footprint) prevents ROLL
ROLL protocols from assuming they know all 1-hop, 2-hop, or N-hop protocols from assuming they know all 1-hop, 2-hop, or N-hop
neighbors. For this reason, while protocols such as MANET-NHDP neighbors. For this reason, while protocols such as MANET-NHDP
([I-D.ietf-manet-nhdp]) and IPv6's neighbor discovery ([RFC4861]) ([I-D.ietf-manet-nhdp]) and IPv6's neighbor discovery ([RFC4861])
provide basic mechanisms for discovering link-layer neighbors, not provide basic mechanisms for discovering link-layer neighbors, not
all of their features are relevant. This section describes these two all of their features are relevant. This section describes these two
protocols, their capabilities, and how ROLL protocols could leverage protocols, their capabilities, and how ROLL protocols could leverage
them. them.
8.1. IPv6 Neighbor Discovery 8.1. IPv6 Neighbor Discovery
IPv6 neighbor discovery provides mechanisms for nodes to discover IPv6 neighbor discovery provides mechanisms for nodes to discover
skipping to change at page 17, line 49 skipping to change at page 18, line 24
Furthermore, IPv6 neighbor discovery's support of address Furthermore, IPv6 neighbor discovery's support of address
autoconfiguration assumes address provisioning, in that addresses autoconfiguration assumes address provisioning, in that addresses
reflect the underlying communication topology. IPv6 neighbor reflect the underlying communication topology. IPv6 neighbor
discovery does not consider asymmetric links. Nevertheless, it may discovery does not consider asymmetric links. Nevertheless, it may
be possible to extend and adapt IPv6's mechanisms to wireless in be possible to extend and adapt IPv6's mechanisms to wireless in
order to avoid response storms and implosions. order to avoid response storms and implosions.
8.2. MANET-NHDP 8.2. MANET-NHDP
The MANET Neighborhood Discovery Protocol (MANET-NHDP) provides The MANET Neighborhood Discovery Protocol (MANET-NHDP) provides
mechanisms for discovering a node's symmetric 2-hop neighborhood. It mechanisms for discovering a MANET router's symmetric 2-hop
maintains information on discovered links, their interfaces, status, neighborhood. It maintains information on discovered links, their
and neighbor sets. MANET-NHDP advertises a node's local link state; interfaces, status, and neighbor sets. MANET-NHDP advertises a
by listening to all of its 1-hop neighbor's advertisements, a node node's local link state; by listening to all of its 1-hop neighbor's
can compute its 2-hop neighborhood. MANET-NHDP link state advertisements, a node can compute its 2-hop neighborhood. MANET-
advertisements can include a link quality metric. MANET-NHDP's node NHDP link state advertisements can include a link quality metric.
information base includes all interface addresses of each 1-hop MANET-NHDP's node information base includes all interface addresses
neighbor: for low-power nodes, this state requirement can be of each 1-hop neighbor: for low-power nodes, this state requirement
difficult to support. can be difficult to support.
9. Conclusion 9. Conclusion
Figure 1 shows that no existing IETF protocol specification meets the Figure 1 shows that no existing IETF protocol specification meets the
criteria described in Section 4. Therefore, having a routing criteria described in Section 4. Therefore, having a routing
protocol for LLNs requires new protocol specification documents. protocol for LLNs requires new protocol specification documents.
Whether such documents describe modifications to existing protocols Whether such documents describe modifications to existing protocols
or new protocols it outside the scope of this document and warrants or new protocols it outside the scope of this document and warrants
further discussion. However, the results in Figure 1 may provide further discussion. However, the results in Figure 1 may provide
some insight or guidance in such a discusssion, indicating what some insight or guidance in such a discusssion, indicating what
protocol mechanisms may be better suited to LLNs than others. protocol mechanisms may be better suited to LLNs than others.
Such a discussion should not, however, be limited to the protocols
listed in Figure Figure 1. There are many existing protocols which
are unsuitable as a general routing protocol but describe mechanisms
that could be very useful in the context of LLNs. Any such future
discussion ought to consider how routing in LLNs may benefit from
examining mechanisms from a broader suite of protocols than those
listed in Figure Figure 1.
10. Security Considerations 10. Security Considerations
This document presents, considers, and raises no security LLNs have security considerations. These considerations vary greatly
considerations. depending on application domain. For example, deployers industrial
monitoring networks may impose more stringent confidentiality
requirements than home automation networks do. Such requirements are
an important consideration in protocol design, but their variety
makes distilling them to a minimalist set of "necessary but not
sufficient" criteria is of limited use. The criteria in this
document are not the only requirements and considerations in LLN
protocols, and as such the omission of a security criterion should
not be interpreted as a lack of a need for security in LLNs.
11. IANA Considerations 11. IANA Considerations
This document includes no request to IANA. This document includes no request to IANA.
12. Acknowledgements 12. Acknowledgements
The authors would like to thank all the members of the ROLL working The authors would like to thank all the members of the ROLL working
group for their valuable comments, and the chairs for their helpful group for their valuable comments, and the chairs for their helpful
guidance. guidance.
skipping to change at page 19, line 14 skipping to change at page 19, line 44
13.1. Normative References 13.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
13.2. Informative References 13.2. Informative References
[I-D.ietf-manet-dymo] [I-D.ietf-manet-dymo]
Chakeres, I. and C. Perkins, "Dynamic MANET On-demand Chakeres, I. and C. Perkins, "Dynamic MANET On-demand
(DYMO) Routing", draft-ietf-manet-dymo-16 (work in (DYMO) Routing", draft-ietf-manet-dymo-15 (work in
progress), December 2008. progress), November 2008.
[I-D.ietf-manet-nhdp] [I-D.ietf-manet-nhdp]
Clausen, T., Dearlove, C., and J. Dean, "MANET Clausen, T., Dearlove, C., and J. Dean, "MANET
Neighborhood Discovery Protocol (NHDP)", Neighborhood Discovery Protocol (NHDP)",
draft-ietf-manet-nhdp-07 (work in progress), July 2008. draft-ietf-manet-nhdp-07 (work in progress), July 2008.
[I-D.ietf-manet-olsrv2] [I-D.ietf-manet-olsrv2]
Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized
Link State Routing Protocol version 2", Link State Routing Protocol version 2",
draft-ietf-manet-olsrv2-07 (work in progress), July 2008. draft-ietf-manet-olsrv2-07 (work in progress), July 2008.
skipping to change at page 19, line 52 skipping to change at page 20, line 36
WSNs Routing Requirements in Low Power and Lossy WSNs Routing Requirements in Low Power and Lossy
Networks", draft-ietf-roll-urban-routing-reqs-03 (work in Networks", draft-ietf-roll-urban-routing-reqs-03 (work in
progress), January 2009. progress), January 2009.
[I-D.irtf-dtnrg-prophet] [I-D.irtf-dtnrg-prophet]
Lindgren, A. and A. Doria, "Probabilistic Routing Protocol Lindgren, A. and A. Doria, "Probabilistic Routing Protocol
for Intermittently Connected Networks", for Intermittently Connected Networks",
draft-irtf-dtnrg-prophet-01 (work in progress), draft-irtf-dtnrg-prophet-01 (work in progress),
November 2008. November 2008.
[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", [RFC1142] Oran, D., "OSI IS-IS Intra-domain Routing Protocol",
RFC 1142, February 1990. RFC 1142, February 1990.
[RFC2091] Meyer, G. and S. Sherry, "Triggered Extensions to RIP to [RFC2091] Meyer, G. and S. Sherry, "Triggered Extensions to RIP to
Support Demand Circuits", RFC 2091, January 1997. Support Demand Circuits", RFC 2091, January 1997.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453, [RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453,
November 1998. November 1998.
skipping to change at page 20, line 38 skipping to change at page 21, line 17
Protocol (OLSR)", RFC 3626, October 2003. Protocol (OLSR)", RFC 3626, October 2003.
[RFC3630] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering [RFC3630] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering
(TE) Extensions to OSPF Version 2", RFC 3630, (TE) Extensions to OSPF Version 2", RFC 3630,
September 2003. September 2003.
[RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology [RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology
Dissemination Based on Reverse-Path Forwarding (TBRPF)", Dissemination Based on Reverse-Path Forwarding (TBRPF)",
RFC 3684, February 2004. 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 [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source
Routing Protocol (DSR) for Mobile Ad Hoc Networks for Routing Protocol (DSR) for Mobile Ad Hoc Networks for
IPv4", RFC 4728, February 2007. IPv4", RFC 4728, February 2007.
[RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
"Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
September 2007. September 2007.
[RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol [RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol
Specification", RFC 5050, November 2007. Specification", RFC 5050, November 2007.
skipping to change at page 21, line 17 skipping to change at page 21, line 40
September 2008. September 2008.
Appendix A. Routing protocol scalability analysis Appendix A. Routing protocol scalability analysis
This aim of this Appendix is to provide the details for the analysis This aim of this Appendix is to provide the details for the analysis
routing scalability analysis. routing scalability analysis.
"OSPF & IS-IS" "OSPF & IS-IS"
OSPF floods link state through a network. Each router must receive OSPF floods link state through a network. Each router must receive
this complete link set. OSPF fails the table size criterion because this complete link set. OSPF fails the routing state criterion
it requires each router to discover each link in the network, for a because it requires each router to discover each link in the network,
total routing table size which is O(N * L). This also causes it to for a total routing table size which is O(N * L). This also causes
fail the control cost criterion, since this information must be it to fail the control cost criterion, since this information must be
propagated. Furthermore, changes in the link set require re-flooding propagated. Furthermore, changes in the link set require re-flooding
the network link state even if the changed links were not being used. the network link state even if the changed links were not being used.
Since link state changes in wireless networks are often uncorrelated Since link state changes in wireless networks are often uncorrelated
with data traffic and are instead caused by external (environmental) with data traffic and are instead caused by external (environmental)
factors, this causes OSPF to fail both the control cost and loss factors, this causes OSPF to fail both the control cost and loss
response criteria. OSPF routers can impose policies on the use of response criteria. OSPF routers can impose policies on the use of
links and can consider link properties (Type of Service), as the cost links and can consider link properties (Type of Service), as the cost
associated with an edge is configurable by the system administrator associated with an edge is configurable by the system administrator
[RFC2328], so receive a pass for link cost. However, there is no way [RFC2328], so receive a pass for link cost. However, there is no way
to associate metrics with routers (as costs are only applied to to associate metrics with routers (as costs are only applied to
skipping to change at page 21, line 49 skipping to change at page 22, line 25
costs but not router costs in its shortest path computation. costs but not router costs in its shortest path computation.
"OLSRv2" "OLSRv2"
OLSRv2 is a proactive link state protocol, flooding link state OLSRv2 is a proactive link state protocol, flooding link state
information through a set of multipoint relays (MPRs). Routing state information through a set of multipoint relays (MPRs). Routing state
includes 1-hop neighbor information for each node in the network, includes 1-hop neighbor information for each node in the network,
1-hop and 2-hop information for neighbors (for MPR selection), and a 1-hop and 2-hop information for neighbors (for MPR selection), and a
routing table (consisting of destination, and next hop), resulting in routing table (consisting of destination, and next hop), resulting in
state proportional to network size and density (O(N*L + L^2)), and state proportional to network size and density (O(N*L + L^2)), and
failing the table scalability criterion. failing the routing state criterion.
Unacceptable control traffic overhead may arise from flooding and Unacceptable control traffic overhead may arise from flooding and
maintenance. HELLO messages are periodically broadcast local beacon maintenance. HELLO messages are periodically broadcast local beacon
messages, but TC messages spread topology information throughout the messages, but TC messages spread topology information throughout the
network (using MPRs). As such, control traffic is proportional to 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 O(N^2). MPRs reduce this load to O(N^2 / L). As the number of MPRs
is inversely proportional to the density of the network and L is is inversely proportional to the density of the network and L is
bounded by N, this means control traffic is at best proportional to bounded by N, this means control traffic is at best proportional to
O(N). O(N).
Fisheye routing is a technique to reduce the frequency routing Fisheye routing is a technique to reduce the frequency routing
updates as the routing update propagates away from its source. This updates as the routing update propagates away from its source. This
has the potential to reduce the control overhead to acceptable has the potential to reduce the control overhead to acceptable
levels, and it is possible to implement this technique without levels, and it is possible to implement this technique without
violating the specification because the specification does not violating the specification because the specification does not
require that all updates be sent with the same frequency. However, require that all updates be sent with the same frequency. However,
there is no specification of how this should be accomplished. Thus, there is no specification of how this should be accomplished. Thus,
OLSR receives a "?" for the control traffic criterion. Fisheye OLSR receives a "?" for the control traffic criterion. Fisheye
routing does not alter the table size, so it does not modify OLSR's routing does not alter the table size, so it does not modify OLSR's
failure of the table scalability criterion. result ("fail") on the routing state criterion.
Furthermore, changes in the link set may require re-flooding the Furthermore, changes in the link set may require re-flooding the
network link state even if those links were not being used by network link state even if those links were not being used by
routing. OLSR makes these triggered floods optional, but as sending routing. OLSR makes these triggered floods optional, but as sending
no triggered updates will raise problems in topology consistency, no triggered updates will raise problems in topology consistency,
OLSRv2 receives a '?' in the loss response criterion. OLSRv2 receives a '?' in the loss response criterion.
OLSR allows for specification of link quality, and also provides a OLSR allows for specification of link quality, and also provides a
'Willingness' metric to symbolize node cost, giving it a pass for 'Willingness' metric to symbolize node cost, giving it a pass for
both those criteria. both those criteria.
"TBRPF" "TBRPF"
As a link state protocol where each node maintains a database of the As a link state protocol where each node maintains a database of the
entire network topology, TBRPF's routing table size scales with entire network topology, TBRPF's routing table size scales with
network size and density, leading to table sizes which are O(N * L) network size and density, leading to table sizes which are O(N * L)
when a node receives disjoint link sets from its neighbors. This when a node receives disjoint link sets from its neighbors. This
causes the protocol to fail the table size criterion. The protocol's causes the protocol to fail the routing state criterion. The
use of differential updates should allow both fast response time and protocol's use of differential updates should allow both fast
incremental changes once the distributed database of links has been response time and incremental changes once the distributed database
established. Differential updates are only used to reduce response of links has been established. Differential updates are only used to
time to changing network conditions, not to reduce the amount of reduce response time to changing network conditions, not to reduce
topology information sent, since each node will periodically send the amount of topology information sent, since each node will
their piece of the topology. As a result, TBRPF fails the control periodically send their piece of the topology. As a result, TBRPF
overhead criterion. However, its differential updates triggered by fails the control overhead criterion. However, its differential
link failure do not immediately cause a global re-flooding of state updates triggered by link failure do not immediately cause a global
(but only to affected routers) [RFC3684], leading to a pass for loss re-flooding of state (but only to affected routers) [RFC3684],
response. leading to a pass for loss response.
TBRPF has a flexible neighbor management layer which enables it to TBRPF has a flexible neighbor management layer which enables it to
incorporate various types of link metrics into its routing decision incorporate various types of link metrics into its routing decision
by enabling a USE_METRIC flag [RFC3684]. As a result, it receives a 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 pass for link cost. It also provides a mechanism whereby routers can
maintain multiple link metrics to a single neighbor, some of which maintain multiple link metrics to a single neighbor, some of which
can be advertised by the neighbor router [RFC3684]. Although the RFC can be advertised by the neighbor router [RFC3684]. Although the RFC
does not specify a policy for using these values, developing one does not specify a policy for using these values, developing one
could allow TBRPF to satisfy this requirement, leading to a ? for the could allow TBRPF to satisfy this requirement, leading to a ? for the
node cost requirement. node cost requirement.
"RIP" "RIP"
RIP is a distance vector protocol: all routers maintain a route to RIP is a distance vector protocol: all routers maintain a route to
all other routers. Routing table size is therefore O(N). However, all other routers. Routing table size is therefore O(N). However,
if destinations are known apriori, table size can be reduced to O(D), if destinations are known apriori, table size can be reduced to O(D),
resulting in a pass for table scalability. While standard RIP resulting in a pass for routing state. While standard RIP requires
requires each node broadcast a beacon per period, and that updates each node broadcast a beacon per period, and that updates must be
must be propagated by affected nodes, triggered RIP only sends propagated by affected nodes, triggered RIP only sends updates when
updates when network conditions change in response to the data path, network conditions change in response to the data path, so RIP passes
so RIP passes the control cost criterion. Loss triggers updates, the control cost criterion. Loss triggers updates, only propagating
only propagating if part of a best route, but even if the route is if part of a best route, but even if the route is not actively being
not actively being used, resulting in a fail for loss response. The used, resulting in a fail for loss response. The rate of triggered
rate of triggered updates is throttled, and these are only updates is throttled, and these are only differential updates, yet
differential updates, yet this still doesn't account for other this still doesn't account for other control traffic (or tie it to
control traffic (or tie it to data rate) or prevent the triggered data rate) or prevent the triggered updates from being flooded along
updates from being flooded along non-active paths. [RFC2453] non-active paths. [RFC2453]
RIP receives a ? for link cost because while current implementations RIP receives a ? for link cost because while current implementations
focus on hop count and that is the metric used in [RFC2453], the RFC focus on hop count and that is the metric used in [RFC2453], the RFC
also mentions that more complex metrics such as differences in also mentions that more complex metrics such as differences in
bandwidth and reliability could be used. However, the RFC also bandwidth and reliability could be used. However, the RFC also
states that real-time metrics such as link-quality would create states that real-time metrics such as link-quality would create
instability and the concept of node cost only appears as metrics instability and the concept of node cost only appears as metrics
assigned to external networks. While RIP has the concept of a assigned to external networks. While RIP has the concept of a
network cost, it is insufficient to describe node properties and so network cost, it is insufficient to describe node properties and so
RIP fails the node cost criterion.. RIP fails the node cost criterion..
"AODV" "AODV"
AODV table size is a function of the number of communicating pairs in AODV table size is a function of the number of communicating pairs in
the network, scaling with O(D). This is acceptable and so AODV the network, scaling with O(D). This is acceptable and so AODV
passes the table size criterion. As an on-demand protocol, AODV does passes the routing state criterion. As an on-demand protocol, AODV
not generate any traffic until data is sent, and so control traffic does not generate any traffic until data is sent, and so control
is correlated with the data and so it receives a pass for control traffic is correlated with the data and so it receives a pass for
traffic. When a broken link is detected, AODV will use a precursor control traffic. When a broken link is detected, AODV will use a
list maintained for each destination to inform downstream routers precursor list maintained for each destination to inform downstream
(with a RERR) of the topology change. However, the RERR message is routers (with a RERR) of the topology change. However, the RERR
forwarded by all nodes that have a route that uses the broken link, message is forwarded by all nodes that have a route that uses the
even if the route is not currently active, leading to a fail for loss broken link, even if the route is not currently active, leading to a
response [RFC3561]. fail for loss response [RFC3561].
AODV fails the link cost criterion because the only metric used is AODV fails the link cost criterion because the only metric used is
hop count, and this is hardcoded in the route table entry, according hop count, and this is hardcoded in the route table entry, according
to the RFC [RFC3561]. It fails the node cost requirement because to the RFC [RFC3561]. It fails the node cost requirement because
there is no way for a router to indicate its [lack of] willingness to there is no way for a router to indicate its [lack of] willingness to
route while still adhering to the RFC. route while still adhering to the RFC.
"DYMO/DYMO-low" "DYMO"
The design of DYMO shares much with AODV, with some changes to remove The design of DYMO shares much with AODV, with some changes to remove
precursor lists and compact various messages. It still passes the precursor lists and compact various messages. It still passes the
table size criterion because it only maintains routes requested by routing state criterion because it only maintains routes requested by
RREQ messages, resulting in O(D) table size. Control traffic (RREQ, RREQ messages, resulting in O(D) table size. Control traffic (RREQ,
RREP, and RREQ) are still driven by data, and hence DYMO passes the RREP, and RREQ) are still driven by data, and hence DYMO passes the
control cost criterion. However, RERR messages are forwarded by any control cost criterion. The DYMO specification places very few
nodes that have a route using the link, even if inactive, leading to requirements on how nodes respond to route error RERR messages that
a fail of the loss reponse criterion [I-D.ietf-manet-dymo]. denote a broken route. Therefore, while it is possible for a DYMO
implementation to meet the loss response criterion, the specification
is not clear on how to meet the criterion while still maintaining
routes as link breaks . This leads to a ? in loss repsonse
[I-D.ietf-manet-dymo].
DYMO indicates that the "distance" of a link can vary from 1-65535 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 [I-D.ietf-manet-dymo], leading to a ? in link cost. While additional
routing information can be added DYMO messages, there is no mention routing information can be added DYMO messages, there is no mention
of node properties, leading to a fail in node cost. of node properties, leading to a fail in node cost.
"DSR" "DSR"
DSR performs on-demand route discovery, and source routing of DSR performs on-demand route discovery, and source routing of
packets. It maintains a source route for all destinations, and also packets. It maintains a source route for all destinations, and also
a blacklist of all unidirectional neighbor links [RFC4728], leading a blacklist of all unidirectional neighbor links [RFC4728], leading
to a total table size of O(D + L), failing the table size criterion. to a total table size of O(D + L), failing the routing state
Control traffic is completely data driven, and so DSR receives a pass criterion. Control traffic is completely data driven, and so DSR
for this criterion. Finally, a transmission failure only prompts an receives a pass for this criterion. Finally, a transmission failure
unreachable destination to be sent to the source of the message, only prompts an unreachable destination to be sent to the source of
passing the loss response criterion. the message, passing the loss response criterion.
DSR fails the link cost criterion because its source routes are DSR fails the link cost criterion because its source routes are
advertised only in terms of hops, such that all advertised links are advertised only in terms of hops, such that all advertised links are
considered equivalent. DSR also fails the node cost criterion considered equivalent. DSR also fails the node cost criterion
because a node has no way of indicating its willingness to serve as a because a node has no way of indicating its willingness to serve as a
router and forward messages. router and forward messages.
Appendix B. Logarithmic scaling of control cost Appendix B. Logarithmic scaling of control cost
To satisfy the control cost criterion, a protocol's control traffic To satisfy the control cost criterion, a protocol's control traffic
 End of changes. 59 change blocks. 
241 lines changed or deleted 268 lines changed or added

This html diff was produced by rfcdiff 1.35. The latest version is available from http://tools.ietf.org/tools/rfcdiff/