draft-ietf-roll-protocols-survey-04.txt   draft-ietf-roll-protocols-survey-05.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 24, 2009 S. Dawson-Haggerty Expires: July 30, 2009 S. Dawson-Haggerty
UC Berkeley UC Berkeley
January 20, 2009 January 26, 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-04 draft-ietf-roll-protocols-survey-05
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 24, 2009. This Internet-Draft will expire on July 30, 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
skipping to change at page 3, line 13 skipping to change at page 3, line 13
is necessary. is necessary.
Table of Contents Table of Contents
1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
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. Suitability Summary . . . . . . . . . . . . . . . . . . . . . 7 4. Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 8 4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 8
4.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 8 4.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 9
4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 9 4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 9
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 . . . . . . . . . . . . . . . . . . . . . . 14
6.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7. Distance Vector protocols . . . . . . . . . . . . . . . . . . 15 7. Distance Vector protocols . . . . . . . . . . . . . . . . . . 15
7.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
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 . . . . . . . . . . . . . . . . . 17
8.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 17 8.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 17
9. Security Considerations . . . . . . . . . . . . . . . . . . . 18 9. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 18
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 10. Security Considerations . . . . . . . . . . . . . . . . . . . 18
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 18 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 18
12.1. Normative References . . . . . . . . . . . . . . . . . . . 18 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19
12.2. Informative References . . . . . . . . . . . . . . . . . . 18 13.1. Normative References . . . . . . . . . . . . . . . . . . . 19
Appendix A. Routing protocol scalability analysis . . . . . . . . 20 13.2. Informative References . . . . . . . . . . . . . . . . . . 19
Appendix A. Routing protocol scalability analysis . . . . . . . . 21
Appendix B. Logarithmic scaling of control cost . . . . . . . . . 24 Appendix B. Logarithmic scaling of control cost . . . . . . . . . 24
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25
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
skipping to change at page 4, line 50 skipping to change at page 4, line 50
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", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119]. 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 underlying behind Moore's Law has reduced technological progress behind Moore's Law has reduced computer prices
computer prices and form factors, networking has come to include not and form factors, networking has come to include not only servers and
only servers and desktops, but laptops, palmtops, and cellphones. As desktops, but laptops, palmtops, and cellphones. As computing device
computing device costs and sizes have shrunk, small wireless sensors, costs and sizes have shrunk, small wireless sensors, actuators, and
actuators, and smart objects have emerged as an important next step smart objects have emerged as an important next step in
in internetworking. The sheer number of the low-power networked internetworking. The sheer number of the low-power networked devices
devices means that they cannot depend on human intervention (e.g., means that they cannot depend on human intervention (e.g., adjusting
adjusting position) for good networking: they must have routing position) for good networking: they must have routing protocols that
protocols that enable them to self-organize into multihop networks. enable them to 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 Correspondingly, low power operation is a key concern for these
sensors and actuators so as to allow them to function for months and sensors and actuators so as to allow them to function for months and
years without interruption. Cost points and energy limitations cause years without interruption. Cost points and energy limitations cause
these devices to have very limited resources: a few kB of RAM and a 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 few MHz of CPU is typical. As energy efficiency does not improve
with Moore's Law, these limitations are not temporary. This trend with Moore's Law, these limitations are not temporary. This trend
towards smaller, lower power, and more numerous devices has led to towards smaller, lower power, and more numerous devices has led to
skipping to change at page 6, line 7 skipping to change at page 6, line 7
circumstances, it behooves us to use an existing standard. However, circumstances, it behooves us to use an existing standard. However,
if no current protocol can meet LLN's requirements, then further work if no current protocol can meet LLN's requirements, then further work
will be needed to define and standardize with a protocol that can. will be needed to define and standardize with a protocol that can.
Whether or not such a protocol involves modifications to an existing Whether or not such a protocol involves modifications to an existing
protocol or a new protocol entirely is outside the scope of this protocol or a new protocol entirely is outside the scope of this
document: this document simply seeks to answer the question: do LLNs document: this document simply seeks to answer the question: do LLNs
require a new protocol specification document at all? require a new protocol specification document at all?
3. Methodology 3. Methodology
To answer the question of LLNs require new protocol specification To answer the question of whether LLNs require new protocol
work, this document examines existing routing protocols and how well specification work, this document examines existing routing protocols
they can be applied to low power and lossy networks. It provides a and how well they can be applied to low power and lossy networks. It
set of criteria with which to compare the costs and benefits of provides a set of criteria with which to compare the costs and
different protocol designs and examines existing protocols in terms benefits of different protocol designs and examines existing
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 anywhere which could meet LLN application is any protocol outside the IETF which could meet LLN application
requirements. Rather, it seeks to answer whether protocols, as requirements. Rather, it seeks to answer whether any existing
specified in current IETF standards documents, 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. For example, there are many academic papers and unnecessary. Thhere are many academic papers and experimental
experimental protocol implementations available; while one or more of protocol implementations available. While one or more of these may
these may meet LLN requirements, if they are not specified in an RFC meet LLN requirements, if they are not specified in an RFC then a
then a working group will need to write a new RFC for them to be a working group will need to write a new RFC for them to be a standard.
standard. The question this document seeks to answer is not whether The question this document seeks to answer is not whether proposed,
proposed, evaluated, theoretical or hypothetical protocol designs can evaluated, theoretical or hypothetical protocol designs can satisfy
satisfy LLN requirements: the question is whether existing IETF LLN requirements: the question is whether existing IETF protocols
standards can. 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
mature draft that is a working item of an IETF working group. The stable and mature draft that is a working item of an IETF working
list of considered protocols is OSPF [RFC2328], IS-IS [RFC1142], RIP group. The list of considered protocols is OSPF [RFC2328], IS-IS
[RFC2453], OLSR [RFC3626], OLSv2 [I-D.ietf-manet-olsrv2], TBRPF [RFC1142], RIP [RFC2453], OLSR [RFC3626], OLSv2
[RFC3684], AODV [RFC3561], DYMO [I-D.ietf-manet-dymo], and DSR [I-D.ietf-manet-olsrv2], TBRPF [RFC3684], AODV [RFC3561], DYMO
[RFC4728]. This document also considers notable variants of these [I-D.ietf-manet-dymo], and DSR [RFC4728]. This document also
protocols, such as Triggered RIP [RFC2091]. considers notable variants of these protocols, such as Triggered RIP
[RFC2091].
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] no consider the DTN routing protocol PRoPHET [I-D.irtf-dtnrg-prophet]
because its design is based on the non-randomness of node mobility, because its design is based on the non-randomness of node mobility,
which does not exist in many LLN application domains. which does not exist in many LLN application domains.
This document does not examine the Network Mobility Basic Support This document does not examine the Network Mobility Basic Support
Protocol (NEMO RFC 3963 [RFC3963]) because it is not a routing Protocol (NEMO RFC 3963 [RFC3963]) because it is not a routing
skipping to change at page 7, line 42 skipping to change at page 7, line 43
through each specification and considering a hypothetical through each specification and considering a hypothetical
implementation which took advantage of the specification so as to implementation which took advantage of the specification so as to
perform as well as possible on the criteria. The judgement is based perform as well as possible on the criteria. The judgement is 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.
4. Suitability Summary 4. Criteria
In this section, we present five important requirements for routing In this section, we present five important criteria for routing in
in low power and lossy networks, and evaluate protocols against them. low power and lossy networks, and evaluate protocols against them.
This evaluation attempts to take a complicated and interrelated set This evaluation attempts to take a complicated and interrelated set
of design decisions and trade-offs and condense them to a simple 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 criterion will be 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. 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 most applications domains share.
Considering this very general and common set of requirements sets a Considering this very general and common set of requirements sets a
minimal bar for a protocol to be generally applicable. If a protocol minimal bar for a protocol to be generally applicable. If a protocol
cannot meet even these minimalist criteria, then it cannot be used cannot meet even these minimalist criteria, then it cannot be used
unchanged in several major ROLL application domains and so is unchanged in several major ROLL application domains and so is
unlikely to be a good candidate for use. Satisfying these minimal unlikely to be a good candidate for use within the broader scope of
criteria is necessary but not sufficient: they do not represent the all LLN application domains. Satisfying these minimal criteria is
complete intersection of application requirements and applications necessary but not sufficient: they do not represent the complete
introduce additional, more stringent requirements. But this intersection of application requirements and applications introduce
simplified view provides a first cut of the applicability of existing additional, more stringent requirements. But this simplified view
protocols, and those that do satisfy them might be reasonable provides a first cut of the applicability of existing protocols, and
candidates for further study. those that do satisfy them might be reasonable candidates for further
study.
The five criteria are "table scalability", "loss response", "control The five criteria are "table scalability", "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 RFC defining the protocol does not, as criterion, and that the document defining the protocol does not, as
written, contain sufficient flexibility to alter the protocol to do written, contain sufficient flexibility to allow the protocol to meet
so. Finally, "?" indicates that an implementation could exhibit the criterion while conforming to the specification. Finally, "?"
satisfactory performance while following the RFC or Internet draft, indicates that an implementation could exhibit satisfactory
but that the implementation decisions necessary to do so are not performance while following the protocol specification, but that the
specified and may require some exploration. In other words, a "fail" implementation decisions necessary to do so are not specified and may
means a protocol would have to be modified so it is not compliant require some exploration. In other words, a "fail" means a protocol
with its specification in order to meet the criterion, while a "?" would have to be modified so it is not compliant with its
means a protocol would require a supplementary document further specification in order to meet the criterion, while a "?" means a
constraining and specifying how a protocol should behave. protocol would require a supplementary document further constraining
and specifying how a protocol should behave.
A protocol failing to meet one or more of the criteria does not
exclude it from being used in LLNs. Rather, it means that, in order
to be used in LLNs, the protocol would need to be extended in ways
that do not conform with the current specification document.
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.
skipping to change at page 9, line 34 skipping to change at page 9, line 42
the larger Internet, scaling with the number of such collection the larger Internet, scaling with the number of such collection
points is reasonable. Protocols whose state scales with the number points is reasonable. Protocols whose state scales with the number
of destinations pass. of destinations pass.
More precisely, routing table size scaling with O(N) or O(L) fails. 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. A table 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 SINR threshold. It is important that link churn being close to the signal-to-noise threshold at the physical layer.
not trigger unnecessary responses by the routing protocol. This It is important that link churn not trigger unnecessary responses by
point is stressed in all the application requirement documents, the routing protocol. This point is stressed in all the application
pointing to the need to localize response to link failures with no requirement documents, pointing to the need to localize response to
triggering of global network re-optimization, whether for reducing link failures with no triggering of global network re-optimization,
traffic or for maintaining low route convergence times whether for reducing traffic or for maintaining low route convergence
([I-D.ietf-roll-home-routing-reqs], times ([I-D.ietf-roll-home-routing-reqs],
[I-D.ietf-roll-urban-routing-reqs], and [I-D.ietf-roll-urban-routing-reqs], and
[I-D.ietf-roll-indus-routing-reqs]). The industrial routing [I-D.ietf-roll-indus-routing-reqs]). The industrial routing
requirements draft states that protocols must be able to "recompute requirements draft states that protocols must be able to "recompute
paths based on underlying link characteristics which may change paths based on underlying link characteristics which may change
dynamically", as well as reoptimize when the device set changes to dynamically", as well as reoptimize when the device set changes to
maintain service requirements. The protocol should also "always be maintain service requirements. The protocol should also "always be
in the process of optimizing the system in response to changing link in the process of optimizing the system in response to changing link
statistics." Protocols with these properties should take care not to statistics." Protocols with these properties should take care not to
require global updates. require global updates.
skipping to change at page 10, line 29 skipping to change at page 10, line 37
[I-D.ietf-roll-home-routing-reqs], with multi-year deployments being [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 a common case [I-D.ietf-roll-indus-routing-reqs]. In terms of
routing structure, any proposed LLN routing protocol ought to support routing structure, any proposed LLN routing protocol ought to support
the autonomous organization and configuration of the network at the the autonomous organization and configuration of the network at the
lowest possible energy cost [I-D.ietf-roll-urban-routing-reqs]. lowest possible energy cost [I-D.ietf-roll-urban-routing-reqs].
All routing protocols must transmit additional data to detect All routing protocols must transmit additional data to detect
neighbors, build routes, transmit routing tables, or otherwise neighbors, build routes, transmit routing tables, or otherwise
conduct routing. As low-power wireless networks can have very low conduct routing. As low-power wireless networks can have very low
data rates, protocols which require a minimum control packet rate can data rates, protocols which require a minimum control packet rate can
have unbounded control overhead. This is particularly true for have an unbounded control overhead per data packet. This is
event-driven networks, which only report data when certain conditions particularly true for event-driven networks, which only report data
are met. Regions of a network which never meet the condition can be when certain conditions are met. Regions of a network which never
forced to send significant control traffic even when there is no data meet the condition can be forced to send significant control traffic
to send. For these use cases, hard-coded timing constants are even when there is no data to send. For these use cases, hard-coded
unacceptable, because they imply a prior knowledge of the expected timing constants are unacceptable, because they imply a prior
data rate. knowledge of the expected data rate.
Of course, protocols require the ability to send at least a very Of course, protocols require the ability to send at least a very
small amount of control traffic, in order to discover a topology. small amount of control traffic, in order to discover a topology.
But this bootstrapping discovery and maintenance traffic should be But this bootstrapping discovery and maintenance traffic should be
small: communicating once an hour is far more reasonable than small: communicating once an hour is far more reasonable than
communicating once a second. So while control traffic should be communicating once a second. So while control traffic should be
bounded by data traffic, it requires some leeway to bootstrap and bounded by data traffic, it requires some leeway to bootstrap and
maintain a long-lived yet idle network. maintain a long-lived yet idle network.
The control cost 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 criterion and yet are also unsuitable.
In the case of control traffic, the communication rate (sum of In the case of control traffic, the communication rate (sum of
transmissions and receptions at a node) is a better measure than the transmissions and receptions at a node) is a better measure than the
transmission rate (since energy is consumed for both transmissions transmission rate (since energy is consumed for both transmissions
and receptions). Controlling the transmission rate is insufficient, and receptions). Controlling the transmission rate is insufficient,
as it would mean that the energy cost (sum of transmission and as it would mean that the energy cost (sum of transmission and
receptions) of control traffic could grow with O(L). receptions) of control traffic could grow with O(L).
A protocol fails the control cost criterion if its per-node control A protocol fails the control cost criterion if its per-node control
traffic (transmissions plus receptions) rate is not bounded by the traffic (transmissions plus receptions) rate is not bounded by the
data rate plus a small constant. For example, a protocol using a 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 beacon rate only passes if it can be turned arbitrarily low, in order
to match the data rate. Furthermore, packet losses necessitate that to match the data rate. Furthermore, packet losses necessitate that
the control traffic may scale within a O(log(L)) factor of the data 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, 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) 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 + e) to pass this criteria. The details of why O(log(L)) is
necessary are in Appenix B. necessary are in Appendix B.
4.5. Link and Node Cost 4.5. Link and Node Cost
These two criteria specify how a protocol chooses routes for data These two criteria specify how a protocol chooses routes for data
packets to take through the network. Classical routing algorithms packets to take through the network. Classical routing algorithms
typically acknowledge the differing costs of paths and may use a typically acknowledge the differing costs of paths and may use a
shortest path algorithm to find paths. This is a requirement for low shortest path algorithm to find paths. This is a requirement for low
power networks, as links must be evaluated as part of an objective power networks, as links must be evaluated as part of an objective
function across various metric types, such as minimizing latency and function across various metric types, such as minimizing latency and
maximizing reliability [I-D.ietf-roll-indus-routing-reqs]. maximizing reliability [I-D.ietf-roll-indus-routing-reqs].
skipping to change at page 13, line 7 skipping to change at page 13, line 7
is a key component of many protocols, several general protocols and is a key component of many protocols, several general protocols and
protocol mechanisms have been designed to support it. A protocol's protocol mechanisms have been designed to support it. A protocol's
neighbor set is defined by how many "hops" away the set reaches. For 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 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 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 set is its own 1-hop neighbor set and the 1-hop neighbor sets of all
of its 1-hop neighbors. of its 1-hop neighbors.
Because nodes often have very limited resources for storing routing Because nodes often have very limited resources for storing routing
state, protocols cannot assume that they can store complete neighbor state, protocols cannot assume that they can store complete neighbor
information. For example, a node with 4kB of RAM cannot store full information. For example, a node with 4kB of RAM, a typical amount
neighbor state when it has 1000 other nodes nearby. This means that for top-end microcontrollers, cannot store full neighbor state when
ROLL protocols must have mechanisms to decide which of many possible it has 1000 other nodes nearby. This means that ROLL protocols must
neighbors they monitor as routable next hops. For elements such as have mechanisms to decide which of many possible neighbors they
2-hop neighborhoods, these decisions can have a significant impact on monitor as routable next hops. For elements such as 2-hop
the topology that other nodes observe, and therefore may require 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. intelligent logic to prevent effects such as network partitions.
5.1. Protocols Today 5.1. Protocols Today
Wired networks draw from both approaches. OSPF or IS-IS, for Wired networks draw from both approaches. OSPF or IS-IS, for
example, are link-state protocols, while RIP is a distance-vector example, are link-state protocols, while RIP is a distance-vector
protocol. protocol.
MANETs similarly draw from both approaches. OLSR is a link-state MANETs similarly draw from both approaches. OLSR is a link-state
protocol, while AODV and DYMO are distance vector protocols. The protocol, while AODV and DYMO are distance vector protocols. The
skipping to change at page 14, line 7 skipping to change at page 14, line 7
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 Table Loss Control Link Cost Node Cost
OSPF/IS-IS fail fail fail pass fail OSPF/IS-IS fail fail fail pass fail
OLSRv2 fail 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[-low] pass fail pass ? fail
DSR fail pass pass fail fail DSR fail pass pass fail fail
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
Autonomous System (AS). OSPF provides the ability to divide a Autonomous System (AS). OSPF provides the ability to divide a
network into areas, which can establish a routing hierarchy. The network into areas, which can establish a routing hierarchy. The
topology within an area is hidden from other areas and IP prefix topology within an area is hidden from other areas and IP prefix
reachability across areas (inter-area routing) is provided using reachability across areas (inter-area routing) is provided using
skipping to change at page 14, line 43 skipping to change at page 14, line 45
IS-IS (specified in [RFC1142]) is similar in many respects to OSPF, 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 but as a descendent of the OSI protocol suite differs in some places
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 [I-D.ietf-manet-olsrv2]) is a link state routing protocol for MANETs.
wireless mesh networks. OLSR routers flood link state advertisement OLSR routers flood link state advertisement packets throughout the
packets throughout the entire network, such that each node has a map entire network, such that each node has a map of the mesh topology.
of the mesh topology. Because link variations can lead to heavy Because link variations can lead to heavy flooding traffic when using
flooding traffic when using a link state approach, OLSR establishes a a link state approach, OLSR establishes a topology for minimizing
topology for minimizing this communication and imposes minimum time this communication, imposes minimum time interval between two
interval between two successive control transmissions by a router. successive control transmissions by a router, and makes triggered
Each node maintains a set of nodes called its Multipoint Relays updates optional. Each node maintains a set of nodes called its
(MPR), which is a subset of the one-hop neighbors whose connectivity Multipoint Relays (MPR), which is a subset of the one-hop neighbors
covers the two-hop neighborhood. Each node that is an MPR maintains whose connectivity covers the two-hop neighborhood. Each node that
a set called its MPR selectors, which are nodes that have chosen it is an MPR maintains a set called its MPR selectors, which are nodes
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
to its MPR selectors. Together, these three optimizations can to its MPR selectors. Together, these three optimizations can
greatly reduce the control traffic in dense networks, as the number greatly reduce the control traffic in dense networks, as the number
of MPRs should not increase significantly as a network becomes of MPRs should not increase significantly as a network becomes
denser. denser.
OLSR selects routes based on hop counts, and assumes an underlying OLSR selects routes based on hop counts, and assumes an underlying
protocol that determines whether a link exists between two nodes. protocol that determines whether a link exists between two nodes.
OLSR's optimized flooding allows it to quickly adapt to and propagate OLSR's optimized flooding allows it to quickly adapt to and propagate
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 leafs 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. TBRPF computes
a source tree, which provides routes to all reachable nodes. It a source tree, which provides routes to all reachable nodes. It
reduces control packet overhead by having nodes only transmit a reduces control packet overhead by having nodes only transmit a
subset of their source tree as well as by using differential updates. 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
skipping to change at page 17, line 19 skipping to change at page 17, line 21
Because the route is determined at a single place -- the source -- Because the route is determined at a single place -- the source --
DSR does not require sequence numbers or other mechanisms to prevent DSR does not require sequence numbers or other mechanisms to prevent
routing loops, as there is no problem of inconsistent routing tables. routing loops, as there is no problem of inconsistent routing tables.
Unlike AODV and DYMO, by pushing state into packet headers, DSR does Unlike AODV and DYMO, by pushing state into packet headers, DSR does
not require per-destination routing state. Instead, a node not require per-destination routing state. Instead, a node
originating packets only needs to store a spanning tree of the part originating packets only needs to store a spanning tree of the part
of the network it is communicating with. of the network it is communicating with.
8. Neighbor Discovery 8. Neighbor Discovery
A limit on maintained routing state (light footprint) prevents ROLL A limit on maintained routing table size (light footprint) prevents
protocols from assuming they know all 1-hop, 2-hop, or N-hop ROLL 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 18, line 9 skipping to change at page 18, line 12
mechanisms for discovering a node's symmetric 2-hop neighborhood. It mechanisms for discovering a node's symmetric 2-hop neighborhood. It
maintains information on discovered links, their interfaces, status, maintains information on discovered links, their interfaces, status,
and neighbor sets. MANET-NHDP advertises a node's local link state; 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 by listening to all of its 1-hop neighbor's advertisements, a node
can compute its 2-hop neighborhood. MANET-NHDP link state can compute its 2-hop neighborhood. MANET-NHDP link state
advertisements can include a link quality metric. MANET-NHDP's node advertisements can include a link quality metric. MANET-NHDP's node
information base includes all interface addresses of each 1-hop information base includes all interface addresses of each 1-hop
neighbor: for low-power nodes, this state requirement can be neighbor: for low-power nodes, this state requirement can be
difficult to support. difficult to support.
9. Security Considerations 9. Conclusion
Figure 1 shows that no existing IETF protocol specification meets the
criteria described in Section 4. Therefore, having a routing
protocol for LLNs requires new protocol specification documents.
Whether such documents describe modifications to existing protocols
or new protocols it outside the scope of this document and warrants
further discussion. However, the results in Figure 1 may provide
some insight or guidance in such a discusssion, indicating what
protocol mechanisms may be better suited to LLNs than others.
10. Security Considerations
This document presents, considers, and raises no security This document presents, considers, and raises no security
considerations. considerations.
10. IANA Considerations 11. IANA Considerations
This document includes no request to IANA. This document includes no request to IANA.
11. 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.
We are also indebted to the Sensor Network Architecture group at We are also indebted to the Sensor Network Architecture group at
Berkeley for contributing their helpful analysis: Prabal Dutta, Berkeley for contributing their helpful analysis: Prabal Dutta,
Rodrigo Fonseca, Xiaofan Jiang, Jaein Jeong, Jorge Ortiz, and Jay Rodrigo Fonseca, Xiaofan Jiang, Jaein Jeong, Jorge Ortiz, and Jay
Tanega. Tanega.
12. References 13. References
12.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.
12.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-16 (work in
progress), December 2008. progress), December 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.
skipping to change at page 22, line 9 skipping to change at page 22, line 25
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. failure of the table scalability 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. While OLSRv2 limits the rates of such floods by imposing a routing. OLSR makes these triggered floods optional, but as sending
minimum fixed interval between floods, this interval is independent no triggered updates will raise problems in topology consistency,
of the data rate. OLSR therefore fails 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)
skipping to change at page 24, line 34 skipping to change at page 24, line 50
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
communication rate must be bounded by the data rate, plus a small 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 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, O(R) + e, where e is a very small constant (epsilon). Furthermore,
the control rate may grow logarithmically with the size of the local the control rate may grow logarithmically with the size of the local
neighborhood L. Note that this is a bound: it represents the most neighborhood L. Note that this is a bound: it represents the most
traffic a protocol may send, and good protocols may send much less. traffic a protocol may send, and good protocols may send much less.
So the control rate is bounded by O(R log(L)) + e. So the control rate is bounded by O(R log(L)) + e.
The logarithmic factor comes from the fundamental limits of any The logarithmic factor comes from the fundamental limits of any
protocol that maintains a communication rate. For example, consider protocol that maintains a communication rate. For example, consider
e, the small constant rate of communication traffic allowed. Since e, the small constant rate of communication traffic allowed. Since
this rate is communication, to maintain O(e), then only one in L 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 nodes may transmit per time interval defined by e: that one node has
 End of changes. 34 change blocks. 
118 lines changed or deleted 135 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/