draft-ietf-roll-protocols-survey-03.txt   draft-ietf-roll-protocols-survey-04.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 16, 2009 S. Dawson-Haggerty Expires: July 24, 2009 S. Dawson-Haggerty
UC Berkeley UC Berkeley
January 12, 2009 January 20, 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-03 draft-ietf-roll-protocols-survey-04
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 16, 2009. This Internet-Draft will expire on July 24, 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 2, line 18 skipping to change at page 2, line 18
issues. Low-power wireless devices, such as sensors, actuators and issues. Low-power wireless devices, such as sensors, actuators and
smart objects, have difficult constraints: very limited memory, smart objects, have difficult constraints: very limited memory,
little processing power, and long sleep periods. As most of these little processing power, and long sleep periods. As most of these
devices are battery-powered, energy efficiency is critically devices are battery-powered, energy efficiency is critically
important. Wireless link qualities can vary significantly over time, important. Wireless link qualities can vary significantly over time,
requiring protocols to make agile decisions yet minimize topology requiring protocols to make agile decisions yet minimize topology
change energy costs. Routing over such low power and lossy networks change energy costs. Routing over such low power and lossy networks
has novel requirements that existing protocols may not address. This has novel requirements that existing protocols may not address. This
document provides a brief survey of the strengths and weaknesses of document provides a brief survey of the strengths and weaknesses of
existing protocols with respect to this class of networks. From this existing protocols with respect to this class of networks. From this
survey it examines whether existing protocols as described in RFCs survey it examines whether existing and mature IETF protocols can be
and mature drafts could be used without modification in these used without modification in these networks, or whether further work
networks, or whether further work is necessary. is necessary.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
Table of Contents Table of Contents
1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1. Protocols Considered . . . . . . . . . . . . . . . . . . . 6
3.2. Criteria . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 7
4. Suitability Summary . . . . . . . . . . . . . . . . . . . . . 7 4. Suitability Summary . . . . . . . . . . . . . . . . . . . . . 7
4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 8 4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 8
4.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 8 4.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 8
4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 9 4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 9
4.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 9 4.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 10
4.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 10 4.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 11
5. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 11 5. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 12
5.1. Protocols Today . . . . . . . . . . . . . . . . . . . . . 12 5.1. Protocols Today . . . . . . . . . . . . . . . . . . . . . 13
6. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 13 6. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 14
6.1. OSPF & IS-IS . . . . . . . . . . . . . . . . . . . . . . . 13 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) . . . . . . . . . . 15 7.2. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 16
7.3. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 7.3. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.4. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 7.4. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
8. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 16 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 . . . . . . . . . . . . . . . . . . . 17 9. Security Considerations . . . . . . . . . . . . . . . . . . . 18
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 17 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 18
12. Annex A - Routing protocol scalability analysis . . . . . . . 18 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18
13. Annex B - Logarithmic scaling of control cost . . . . . . . . 21 12.1. Normative References . . . . . . . . . . . . . . . . . . . 18
14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22 12.2. Informative References . . . . . . . . . . . . . . . . . . 18
14.1. Normative References . . . . . . . . . . . . . . . . . . . 22 Appendix A. Routing protocol scalability analysis . . . . . . . . 20
14.2. Informative References . . . . . . . . . . . . . . . . . . 22 Appendix B. Logarithmic scaling of control cost . . . . . . . . . 24
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24 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
IS-IS: Intermediate System to Intermediate System IS-IS: Intermediate System to Intermediate System
skipping to change at page 4, line 43 skipping to change at page 4, line 43
MPLS: Multiprotocol Label Switching MPLS: Multiprotocol Label Switching
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",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "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 Wireless is increasingly important to computer networking. As the
Moore's Law has reduced computer prices and form factors, networking technological progress underlying behind Moore's Law has reduced
includes not only servers and desktops, but laptops, palmtops, and computer prices and form factors, networking has come to include not
cellphones. As computing device costs and sizes have shrunk, small only servers and desktops, but laptops, palmtops, and cellphones. As
wireless sensors, actuators, and smart objects have emerged as an computing device costs and sizes have shrunk, small wireless sensors,
important next step in internetworking. The sheer number of the low- actuators, and smart objects have emerged as an important next step
power networked devices means that they cannot depend on human in internetworking. The sheer number of the low-power networked
intervention (e.g., adjusting position) for good networking: they devices means that they cannot depend on human intervention (e.g.,
must have routing protocols that enable them to self-organize into adjusting position) for good networking: they must have routing
multihop networks. protocols that 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 5, line 34 skipping to change at page 5, line 38
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 they were not designed with these requirements in mind, existing As existing protocols were not designed with these requirements in
protocols may or may not work well in LLNs. The first step to 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 reaching consensus on a routing protocol for LLNs is to decide which
of these two is true. If an existing protocol can meet LLN of these two is true. If an existing protocol can meet LLN
requirements without any changes, then barring extenuating requirements without any changes, then barring extenuating
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 LLNs require new protocol specification
work, this document examines existing routing protocols and how well work, this document examines existing routing protocols and how well
they can be applied to low power and lossy networks. It provides a they can be applied to low power and lossy networks. It provides a
set of criteria with which to compare the costs and benefits of set of criteria with which to compare the costs and benefits of
different protocol designs and examines existing protocols in terms different protocol designs and examines existing protocols in terms
of these criteria. of these criteria.
3.1. Protocols Considered
This document does not seek to answer the question of whether there
is any protocol anywhere which could meet LLN application
requirements. Rather, it seeks to answer whether protocols, as
specified in current IETF standards documents, can meet such
requirements. If an existing protocol specification can be used
unchanged, then writing additional protocol specifications is
unnecessary. For example, there are many academic papers and
experimental protocol implementations available; while one or more of
these may 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. The question this document seeks to answer is not whether
proposed, evaluated, theoretical or hypothetical protocol designs can
satisfy LLN requirements: the question is whether existing IETF
standards can.
Therefore, this document considers "existing routing protocols" to be
protocols that are specified in RFCs or, in the cases of DYMO
[I-D.ietf-manet-dymo] or OLSRv2 [I-D.ietf-manet-olsrv2], a very
mature draft that is a working item of an IETF working group. The
list of considered protocols is OSPF [RFC2328], IS-IS [RFC1142], RIP
[RFC2453], OLSR [RFC3626], OLSv2 [I-D.ietf-manet-olsrv2], TBRPF
[RFC3684], AODV [RFC3561], DYMO [I-D.ietf-manet-dymo], and DSR
[RFC4728]. This document also considers notable variants of these
protocols, such as Triggered RIP [RFC2091].
This document does not consider DTN bundles [RFC5050] or the DTN
Licklider protocol [RFC5326] as suggested by the ROLL working group
charter, because they are not routing protocols. This document does
no consider the DTN routing protocol PRoPHET [I-D.irtf-dtnrg-prophet]
because its design is based on the non-randomness of node mobility,
which does not exist in many LLN application domains.
This document does not examine the Network Mobility Basic Support
Protocol (NEMO RFC 3963 [RFC3963]) because it is not a routing
protocol. 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
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 drafts
that describe the requirements of a few major LLN application that describe the requirements of a few major LLN application
scenarios. The five criteria, presented in Section 4, are neither scenarios. The five criteria, presented in Section 4, are neither
exhaustive nor complete. Instead, they are one specific subset of exhaustive nor complete. Instead, they are one specific subset of
high-level requirements shared across all of the application high-level requirements shared across all of the application
requirement drafts. Because every application requirement draft requirement drafts. Because every application requirement draft
specifies these criteria, then a protocol which does not meet one of specifies these criteria, then a protocol which does not meet one of
them cannot be used without modifications or extensions. However, them cannot be used without modifications or extensions. However,
because these criteria represent a subset of the intersection of the because these criteria represent a subset of the intersection of the
application requirements, any given application domain may impose application requirements, any given application domain may impose
additional requirements which a particular protocol may not meet. additional requirements which a particular protocol may not meet.
For this reason, these criteria are "necessary but not sufficient." For this reason, these criteria are "necessary but not sufficient."
A protocol that does not meet the criteria cannot be used as A protocol that does not meet the criteria cannot be used as
specified, but it is possible that a protocol meets the criteria yet specified, but it is possible that a protocol meets the criteria yet
is not able to meet the requirements of a particular application is not able to meet the requirements of a particular application
domain. Nevertheless, a protocol that meets all of the criteria domain. Nevertheless, a protocol that meets all of the criteria
would be very promising, and deserve a closer look and consideration would be very promising, and deserve a closer look and consideration
in light of LLN application domains. in light of LLN application domains.
This document considers "existing routing protocols" to be protocols 3.3. Evaluation
that are specified in RFCs or, in the cases of DYMO
[I-D.ietf-manet-dymo] or OLSRv2 [I-D.ietf-manet-olsrv2], a very
mature draft which will most likely become an RFC. We do not
consider DTN bundles [RFC5050] or the DTN Licklider protocol
[RFC5326] as suggested by the ROLL working group charter, because
they are not routing protocols.
We do not examine the Network Mobility Basic Support Protocol (NEMO
RFC 3963 [RFC3963]) because it is not a routing protocol. We do not
examine hierarchical NEMO [I-D.thubert-tree-discovery] as a candidate
because it only maintains a default route and so is insufficient for
general routing. Although NEMO itself is not a suitable routing
solution to LLNs, some of its mechanisms, such as loop-free tree
formation, might be useful in an LLN routing protocol.
This document does not seek to answer the question of whether there
is any protocol anywhere which could meet LLN application
requirements. Rather, it seeks to answer whether protocols, as
specified in current IETF standards documents, can meet such
requirements. If an existing protocol specification can be used
unchanged, then writing additional protocol specifications is
unnecessary. For example, there are many academic papers and
experimental protocol implementations available; while one or more of
these may 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. The question this document seeks to answer is not whether
proposed, evaluated, theoretical or hypothetical protocol designs can
satisfy LLN requirements: the question is whether existing IETF
standards can.
Whether a protocol meets these criteria was judged by thinking Whether a protocol meets these criteria was judged by thinking
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 metrics. 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. Suitability Summary
In this section, we present five important requirements for routing In this section, we present five important requirements for routing
in low power and lossy networks, and evaluate protocols against them. in 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 metrics do not encompass all network application requirements. These criteria do not encompass
application requirements. Instead, they are a common set of routing all application requirements. Instead, they are a common set of
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 in cannot meet even these minimalist criteria, then it cannot be used
several major ROLL application domains and so is unlikely to be a unchanged in several major ROLL application domains and so is
good candidate for further analysis and examination. Satisfying unlikely to be a good candidate for use. Satisfying these minimal
these minimal criteria is necessary but not sufficient: they do not criteria is necessary but not sufficient: they do not represent the
represent the complete intersection of application requirements and complete intersection of application requirements and applications
applications introduce additional, more stringent requirements. But introduce additional, more stringent requirements. But this
this simplified view provides a first cut of the applicability of simplified view provides a first cut of the applicability of existing
existing protocols, and those that do satisfy them might be protocols, and those that do satisfy them might be reasonable
reasonable candidates for further study. 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 metric. 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
metric, and that the RFC defining the protocol does not, as written, criterion, and that the RFC defining the protocol does not, as
contain sufficient flexibility to alter the protocol to do so. written, contain sufficient flexibility to alter the protocol to do
Finally, "?" indicates that an implementation could exhibit so. Finally, "?" indicates that an implementation could exhibit
satisfactory performance while following the RFC, but that the satisfactory performance while following the RFC or Internet draft,
implementation decisions necessary to do so are not specified and may but that the implementation decisions necessary to do so are not
require some exploration. In other words, a "fail" means a protocol specified and may require some exploration. In other words, a "fail"
would have to be modified so it is not compliant with its RFC in means a protocol would have to be modified so it is not compliant
order to meet the criterion, while a "?" means a protocol would with its specification in order to meet the criterion, while a "?"
require a supplementary document further constraining and specifying means a protocol would require a supplementary document further
how a protocol should behave. constraining and specifying how a protocol should behave.
4.1. Formal Definitions 4.1. Formal Definitions
To provide precise definitions of these metrics, 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 metric from application requirements explain the derivation of each criterion from application
in its corresponding section. requirements in its corresponding section.
4.2. Table Scalability 4.2. Table Scalability
Scalability support for large networks of sensors is highlighted as a Scalability support for large networks of sensors is highlighted as a
key requirement by all three application requirements documents. key requirement by all three application requirements documents.
Network sizes range from a minimum of 250 nodes in the home routing 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 requirements [I-D.ietf-roll-home-routing-reqs] to very large networks
of "tens of thousands to millions" of devices noted of the urban of "tens of thousands to millions" of devices noted of the urban
requirements [I-D.ietf-roll-urban-routing-reqs]. Networks are requirements [I-D.ietf-roll-urban-routing-reqs]. Networks are
expected to have similar size in industrial settings, the expected to have similar size in industrial settings, the
requirements draft states that depths of up to 20 hops are to be requirements draft states that depths of up to 20 hops are to be
expected [I-D.ietf-roll-indus-routing-reqs]. Given that network expected [I-D.ietf-roll-indus-routing-reqs]. Given that network
information maintained at each node is stored in routing and neighbor information maintained at each node is stored in routing and neighbor
tables, along with the constrained memory of nodes, necessitates tables, along with the constrained memory of nodes, necessitates
bounds on the size of these tables. bounds on the size of these tables.
This metric examines whether routing tables scale within reasonable This criterion indicates whether routing tables scale reasonably
memory resources of low-power nodes. According to this metric, within the memory resources of low-power nodes. According to this
routing protocols that scale linearly with the size of the network or criterion, routing tables that scale linearly with the size of the
a node's neighborhood fail. Scaling with the size of the network network or a node's neighborhood fail. Scaling with the size of the
prevents networks from growing to reasonable size, while scaling with network prevents networks from growing to to the sizes necessary for
the network density precludes dense deployments. However, as many many LLN applications when faced with the memory constraints devices
low-power and lossy networks behave principally as data collection in such applications exhibit. Similarly, scaling with the network
networks and principally communicate through routers to data density precludes dense deployments. However, as many low-power and
collection points in the larger Internet, scaling with the number of lossy networks behave principally as data collection networks and
such collection points is reasonable. Protocols whose state scales principally communicate through routers to data collection points in
with the number of destinations pass. 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. 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 SINR threshold. It is important that link churn
not trigger unnecessary responses by the routing protocol. This not trigger unnecessary responses by the routing protocol. This
point is stressed in all the application requirement documents, point is stressed in all the application requirement documents,
skipping to change at page 10, line 23 skipping to change at page 10, line 45
data rate. 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 metric is a necessary but not sufficient condition The control cost criterion is a necessary but not sufficient
for a protocol to be a viable routing protocol for LLNs. Protocols condition for a protocol to be a viable routing protocol for LLNs.
not meeting this bound are unacceptable for use in this environment; Protocols not meeting this bound are unacceptable for use in this
however, there may be protocols which receive a "pass" for this environment; however, there may be protocols which receive a "pass"
metric and yet are also unsuitable. 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 Annex B. necessary are in Appenix B.
4.5. Link and Node Cost 4.5. Link and Node Cost
These two metrics 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].
However, in low power networks it is also desirable to account for However, in low power networks it is also desirable to account for
the cost of routing through particular routers. Applications require the cost of forwarding through particular routers. Applications
node or parameter constrained routing, which takes into account node require node or parameter constrained routing, which takes into
properties and attributes such as power, memory, and battery life account node properties and attributes such as power, memory, and
that dictate a router's willingness or ability to route other battery life that dictate a router's willingness or ability to route
packets. Home routing requirements note that devices will vary in other packets. Home routing requirements note that devices will vary
their duty cycle, and that routing protocols should prefer nodes with in their duty cycle, and that routing protocols should prefer nodes
permanent power [I-D.ietf-roll-home-routing-reqs]. The urban with permanent power [I-D.ietf-roll-home-routing-reqs]. The urban
requirements note that routing protocols may wish to take advantage requirements note that routing protocols may wish to take advantage
of differing data processing and management capabilities among of differing data processing and management capabilities among
network devices [I-D.ietf-roll-urban-routing-reqs]. Finally, network devices [I-D.ietf-roll-urban-routing-reqs]. Finally,
industrial requirements cite differing lifetime requirements as an industrial requirements cite differing lifetime requirements as an
important factor to account for [I-D.ietf-roll-indus-routing-reqs]. important factor to account for [I-D.ietf-roll-indus-routing-reqs].
Node cost refers to the ability for a protocol to incorporate router Node cost refers to the ability for a protocol to incorporate router
properties into routing metrics and use node attributes for properties into routing metrics and use node attributes for
constraint-based routing. constraint-based routing.
A "pass" indicates that the protocol contains a mechanism allowing A "pass" indicates that the protocol contains a mechanism allowing
skipping to change at page 11, line 40 skipping to change at page 12, line 16
Routing protocols broadly fall into two classes: link-state and Routing protocols broadly fall into two classes: link-state and
distance-vector. distance-vector.
A router running a link-state protocol first establishes adjacency A router running a link-state protocol first establishes adjacency
with its neighbors and then reliably floods the local topology with its neighbors and then reliably floods the local topology
information in the form of a Link State Advertisement packet. The information in the form of a Link State Advertisement packet. The
collection of LSAs constitutes the Link State Database (LSDB) that collection of LSAs constitutes the Link State Database (LSDB) that
represents the network topology, and routers synchronize their LSDBs. represents the network topology, and routers synchronize their LSDBs.
Thus each node in the network has a complete view of the network Thus each node in the network has a complete view of the network
topology. Each router uses the LSDB to compute a routing table where topology. Each router uses its LSDB to compute a routing table where
each entry (reachable IP destination address) points to the next hop each entry (reachable IP destination address) points to the next hop
along the shortest path according to some metric. Link state along the shortest path according to some metric. Link state
protocols (such as OSPF and IS-IS) support the concept of area protocols (such as OSPF and IS-IS) support the concept of area
(called "level" for IS-IS) whereby all the routers in the same area (called "level" for IS-IS) whereby all the routers in the same area
share the same view (they have the same LSDB) and areas are share the same view (they have the same LSDB) and areas are
interconnected by border routers according to specific rules that interconnected by border routers according to specific rules that
advertise IP prefix reachability between areas. advertise IP prefix reachability between areas.
A distance vector protocol exchanges routing information rather than A distance vector protocol exchanges routing information rather than
topological information. A router running a distance vector protocol topological information. A router running a distance vector protocol
skipping to change at page 13, line 19 skipping to change at page 13, line 41
speeds (ability to find an alternate path in case of network element speeds (ability to find an alternate path in case of network element
failure), are easier to debug and troubleshoot, and introduce less failure), are easier to debug and troubleshoot, and introduce less
control packet overhead than distance vector protocols. In contrast, control packet overhead than distance vector protocols. In contrast,
distance vector protocols are simpler, require less computation, and distance vector protocols are simpler, require less computation, and
have smaller storage requirements. Most of these tradeoffs are have smaller storage requirements. Most of these tradeoffs are
similar in wireless networks, with one exception. Because wireless similar in wireless networks, with one exception. Because wireless
links can suffer from significant temporal variation, link state links can suffer from significant temporal variation, link state
protocols can have higher traffic loads as topology changes must protocols can have higher traffic loads as topology changes must
propagate globally, while in a distance vector protocol a node can propagate globally, while in a distance vector protocol a node can
make local routing decisions with no effect on the global routing make local routing decisions with no effect on the global routing
topology. One protocol, DSR, does not easily fit into one of these topology.
two classes. Although it is a distance vector protocol, DSR has
several properties that make it differ from most other protocols in One protocol, DSR, does not easily fit into one of these two classes.
this class. We examine these differences in our discussion of DSR. Although it is a distance vector protocol, DSR has several properties
that make it differ from most other protocols in this class. We
examine these differences in our discussion of DSR.
The next two sections summarize several well established routing The next two sections summarize several well established routing
protocols. This table shows, based on the criteria described above, protocols. The table below shows, based on the criteria described
whether these protocols meet ROLL criteria. Annex A contains the above, whether these protocols meet ROLL criteria. Appendix A
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 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
skipping to change at page 14, line 23 skipping to change at page 14, line 44
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
wireless mesh networks. OLSR nodes flood link state advertisement wireless mesh networks. OLSR routers flood link state advertisement
packets throughout the entire network, such that each node has a map packets throughout the entire network, such that each node has a map
of the mesh topology. Because link variations can lead to heavy of the mesh topology. Because link variations can lead to heavy
flooding traffic when using a link state approach, OLSR establishes a flooding traffic when using a link state approach, OLSR establishes a
topology for minimizing this communication. Each node maintains a topology for minimizing this communication and imposes minimum time
set of nodes called its Multipoint Relays (MPR), which is a subset of interval between two successive control transmissions by a router.
the one-hop neighbors whose connectivity covers the two-hop Each node maintains a set of nodes called its Multipoint Relays
neighborhood. Each node that is an MPR maintains a set called its (MPR), which is a subset of the one-hop neighbors whose connectivity
MPR selectors, which are nodes that have chosen it to be an MPR. covers the two-hop neighborhood. Each node that is an MPR maintains
a set called its MPR selectors, which are nodes that have chosen it
to be an MPR.
OLSR uses these two sets to apply three optimizations. First, only OLSR uses these two sets to apply three optimizations. First, only
MPRs generate link state information. Second, nodes can 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 constrained flooding allows it to quickly adapt to and OLSR's optimized flooding allows it to quickly adapt to and propagate
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 leafs 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
skipping to change at page 15, line 47 skipping to change at page 16, line 23
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 intended
for mobile ad-hoc networks. When one AODV node requires a route to for MANETs. When one AODV node requires a route to another, it
another, it floods a request in the network to discover a route. A floods a request in the network to discover a route. A depth-scoped
depth-scoped flooding process avoids discovery from expanding to the flooding process avoids discovery from expanding to the most distant
most distant regions of the network that are in the opposite regions of the network that are in the opposite direction of the
direction of the destination. AODV chooses routes that have the destination. AODV chooses routes that have the minimum hop count.
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.
giving loss response a fail.
7.3. DYMO 7.3. DYMO
Dynamic Mobile On-Demand routing (DYMO) ([I-D.ietf-manet-dymo]) is an Dynamic Mobile On-Demand routing (DYMO) ([I-D.ietf-manet-dymo]) is an
evolution of AODV. The basic functionality is the same, but it has evolution of AODV. The basic functionality is the same, but it has
different packet formats, handling rules, and supports path different packet formats, handling rules, and supports path
accumulation. Path accumulation allows a single DYMO route request accumulation. Path accumulation allows a single DYMO route request
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
skipping to change at page 18, line 11 skipping to change at page 18, line 29
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. Annex A - Routing protocol scalability analysis 12. References
This aim of this Annex is to provide the details for the analysis 12.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
12.2. Informative References
[I-D.ietf-manet-dymo]
Chakeres, I. and C. Perkins, "Dynamic MANET On-demand
(DYMO) Routing", draft-ietf-manet-dymo-16 (work in
progress), December 2008.
[I-D.ietf-manet-nhdp]
Clausen, T., Dearlove, C., and J. Dean, "MANET
Neighborhood Discovery Protocol (NHDP)",
draft-ietf-manet-nhdp-07 (work in progress), July 2008.
[I-D.ietf-manet-olsrv2]
Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized
Link State Routing Protocol version 2",
draft-ietf-manet-olsrv2-07 (work in progress), July 2008.
[I-D.ietf-roll-home-routing-reqs]
Porcu, G., "Home Automation Routing Requirements in Low
Power and Lossy Networks",
draft-ietf-roll-home-routing-reqs-06 (work in progress),
November 2008.
[I-D.ietf-roll-indus-routing-reqs]
Networks, D., Thubert, P., Dwars, S., and T. Phinney,
"Industrial Routing Requirements in Low Power and Lossy
Networks", draft-ietf-roll-indus-routing-reqs-03 (work in
progress), December 2008.
[I-D.ietf-roll-urban-routing-reqs]
Dohler, M., Watteyne, T., Winter, T., Barthel, D.,
Jacquenet, C., Madhusudan, G., and G. Chegaray, "Urban
WSNs Routing Requirements in Low Power and Lossy
Networks", draft-ietf-roll-urban-routing-reqs-03 (work in
progress), January 2009.
[I-D.irtf-dtnrg-prophet]
Lindgren, A. and A. Doria, "Probabilistic Routing Protocol
for Intermittently Connected Networks",
draft-irtf-dtnrg-prophet-01 (work in progress),
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",
RFC 1142, February 1990.
[RFC2091] Meyer, G. and S. Sherry, "Triggered Extensions to RIP to
Support Demand Circuits", RFC 2091, January 1997.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453,
November 1998.
[RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6",
RFC 2740, December 1999.
[RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
Demand Distance Vector (AODV) Routing", RFC 3561,
July 2003.
[RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing
Protocol (OLSR)", RFC 3626, October 2003.
[RFC3630] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering
(TE) Extensions to OSPF Version 2", RFC 3630,
September 2003.
[RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology
Dissemination Based on Reverse-Path Forwarding (TBRPF)",
RFC 3684, February 2004.
[RFC3963] Devarapalli, V., Wakikawa, R., Petrescu, A., and P.
Thubert, "Network Mobility (NEMO) Basic Support Protocol",
RFC 3963, January 2005.
[RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source
Routing Protocol (DSR) for Mobile Ad Hoc Networks for
IPv4", RFC 4728, February 2007.
[RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
"Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
September 2007.
[RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol
Specification", RFC 5050, November 2007.
[RFC5326] Ramadas, M., Burleigh, S., and S. Farrell, "Licklider
Transmission Protocol - Specification", RFC 5326,
September 2008.
Appendix A. Routing protocol scalability 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 table size criterion because
it requires each router to discover each link in the network, for a it requires each router to discover each link in the network, for a
total routing table size which is O(N * L). This also causes it to total routing table size which is O(N * L). This also causes it to
fail the control cost criterion, since this information must be 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
skipping to change at page 19, line 4 skipping to change at page 21, line 33
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 criteria. Fisheye routing does not failing the table scalability criterion.
alter the table size.
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 impliment 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, or a there is no specification of how this should be accomplished. Thus,
guarentee that implementations with different algorithms for deciding OLSR receives a "?" for the control traffic criterion. Fisheye
how frequently to age and retransmit topology updates. Thus, OLSR routing does not alter the table size, so it does not modify OLSR's
receives a "?" for the control traffic metric. failure of the table scalability criterion.
Furthermore, changes in the link set may require immediately re- Furthermore, changes in the link set may require re-flooding the
flooding the network link state even if those links were not being network link state even if those links were not being used by
used by routing, which fails the loss response metric. routing. While OLSRv2 limits the rates of such floods by imposing a
minimum fixed interval between floods, this interval is independent
of the data rate. OLSR therefore fails 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 metrics. 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 criteria. The protocol's causes the protocol to fail the table size criterion. The protocol's
use of differential updates should allow both fast response time and use of differential updates should allow both fast response time and
incremental changes once the distributed database of links has been incremental changes once the distributed database of links has been
established. Differential updates are only used to reduce response established. Differential updates are only used to reduce response
time to changing network conditions, not to reduce the amount of time to changing network conditions, not to reduce the amount of
topology information sent, since each node will periodically send topology information sent, since each node will periodically send
their piece of the topology. As a result, TBRPF fails the control their piece of the topology. As a result, TBRPF fails the control
overhead criteria. However, its differential updates triggered by overhead criterion. However, its differential updates triggered by
link failure do not immediately cause a global re-flooding of state link failure do not immediately cause a global re-flooding of state
(but only to affected routers) [RFC3684], leading to a pass for loss (but only to affected routers) [RFC3684], leading to a pass for loss
response. 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
skipping to change at page 20, line 24 skipping to change at page 23, line 6
"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 table scalability. While standard RIP
requires each node broadcast a beacon per period, and that updates requires each node broadcast a beacon per period, and that updates
must be propagated by affected nodes, triggered RIP only sends must be propagated by affected nodes, triggered RIP only sends
updates when network conditions change in response to the data path, updates when network conditions change in response to the data path,
so RIP passes the control cost metric. Loss triggers updates, only so RIP passes the control cost criterion. Loss triggers updates,
propagating if part of a best route, but even if the route is not only propagating if part of a best route, but even if the route is
actively being used, resulting in a fail for loss response. The rate not actively being used, resulting in a fail for loss response. The
of triggered updates is throttled, and these are only differential rate of triggered updates is throttled, and these are only
updates, yet this still doesn't account for other control traffic (or differential updates, yet this still doesn't account for other
tie it to data rate) or prevent the triggered updates from being control traffic (or tie it to data rate) or prevent the triggered
flooded along non-active paths. [RFC2453] updates from being flooded along 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 criteria. As an on-demand protocol, AODV does passes the table size criterion. As an on-demand protocol, AODV does
not generate any traffic until data is sent, and so control traffic not generate any traffic until data is sent, and so control traffic
is correlated with the data and so it receives a pass for control is correlated with the data and so it receives a pass for control
traffic. When a broken link is detected, AODV will use a precursor traffic. When a broken link is detected, AODV will use a precursor
list maintained for each destination to inform downstream routers list maintained for each destination to inform downstream routers
(with a RERR) of the topology change. However, the RERR message is (with a RERR) of the topology change. However, the RERR message is
forwarded by all nodes that have a route that uses the broken link, forwarded by all nodes that have a route that uses the broken link,
even if the route is not currently active, leading to a fail for loss even if the route is not currently active, leading to a fail for loss
response [RFC3561]. response [RFC3561].
AODV fails the link cost metric because the only metric used is hop AODV fails the link cost criterion because the only metric used is
count, and this is hardcoded in the route table entry, according to hop count, and this is hardcoded in the route table entry, according
the RFC [RFC3561]. It fails the node cost requirement because there to the RFC [RFC3561]. It fails the node cost requirement because
is no way for a router to indicate its [lack of] willingness to route there is no way for a router to indicate its [lack of] willingness to
while still adhering to the RFC. route while still adhering to the RFC.
"DYMO/DYMO-low" "DYMO/DYMO-low"
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 criteria because it only maintains routes requested by table size 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. However, RERR messages are forwarded by any
nodes that have a route using the link, even if inactive, leading to nodes that have a route using the link, even if inactive, leading to
a fail of the loss reponse criteria [I-D.ietf-manet-dymo]. a fail of the loss reponse criterion [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 table size criterion.
Control traffic is completely data driven, and so DSR receives a pass Control traffic is completely data driven, and so DSR receives a pass
for this criteria. Finally, a transmission failure only prompts an for this criterion. Finally, a transmission failure only prompts an
unreachable destination to be sent to the source of the message, unreachable destination to be sent to the source of the message,
passing the loss response criteria. 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.
13. Annex 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.
skipping to change at page 22, line 30 skipping to change at page 25, line 13
lead to 2 transmissions. If L=100, then one node will not hear the lead to 2 transmissions. If L=100, then one node will not hear the
first two transmissions, and there will be 3. The number of first two transmissions, and there will be 3. The number of
transmissions, and the communication rate, will grow with O(log(L)). transmissions, and the communication rate, will grow with O(log(L)).
This logarithmic bound can be prevented through explicit coordination This logarithmic bound can be prevented through explicit coordination
(e.g., leader election), but such approaches assumes state and (e.g., leader election), but such approaches assumes state and
control traffic to elect leaders. As a logarithmic factor in terms control traffic to elect leaders. As a logarithmic factor in terms
of density is not a large stumbling or major limitation, allowing the of density is not a large stumbling or major limitation, allowing the
much greater protocol flexibility it enables is worth its small cost. much greater protocol flexibility it enables is worth its small cost.
14. References
14.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
14.2. Informative References
[I-D.ietf-manet-dymo]
Chakeres, I. and C. Perkins, "Dynamic MANET On-demand
(DYMO) Routing", draft-ietf-manet-dymo-16 (work in
progress), December 2008.
[I-D.ietf-manet-nhdp]
Clausen, T., Dearlove, C., and J. Dean, "MANET
Neighborhood Discovery Protocol (NHDP)",
draft-ietf-manet-nhdp-07 (work in progress), July 2008.
[I-D.ietf-manet-olsrv2]
Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized
Link State Routing Protocol version 2",
draft-ietf-manet-olsrv2-07 (work in progress), July 2008.
[I-D.ietf-roll-home-routing-reqs]
Porcu, G., "Home Automation Routing Requirements in Low
Power and Lossy Networks",
draft-ietf-roll-home-routing-reqs-06 (work in progress),
November 2008.
[I-D.ietf-roll-indus-routing-reqs]
Networks, D., Thubert, P., Dwars, S., and T. Phinney,
"Industrial Routing Requirements in Low Power and Lossy
Networks", draft-ietf-roll-indus-routing-reqs-03 (work in
progress), December 2008.
[I-D.ietf-roll-urban-routing-reqs]
Dohler, M., Watteyne, T., Winter, T., Barthel, D.,
Jacquenet, C., Madhusudan, G., and G. Chegaray, "Urban
WSNs Routing Requirements in Low Power and Lossy
Networks", draft-ietf-roll-urban-routing-reqs-03 (work in
progress), January 2009.
[I-D.thubert-tree-discovery]
Thubert, P., Bontoux, C., Montavont, N., and B. McCarthy,
"Nested Nemo Tree Discovery",
draft-thubert-tree-discovery-07 (work in progress),
August 2008.
[RFC1142] Oran, D., "OSI IS-IS Intra-domain Routing Protocol",
RFC 1142, February 1990.
[RFC2091] Meyer, G. and S. Sherry, "Triggered Extensions to RIP to
Support Demand Circuits", RFC 2091, January 1997.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453,
November 1998.
[RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6",
RFC 2740, December 1999.
[RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
Demand Distance Vector (AODV) Routing", RFC 3561,
July 2003.
[RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing
Protocol (OLSR)", RFC 3626, October 2003.
[RFC3630] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering
(TE) Extensions to OSPF Version 2", RFC 3630,
September 2003.
[RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology
Dissemination Based on Reverse-Path Forwarding (TBRPF)",
RFC 3684, February 2004.
[RFC3963] Devarapalli, V., Wakikawa, R., Petrescu, A., and P.
Thubert, "Network Mobility (NEMO) Basic Support Protocol",
RFC 3963, January 2005.
[RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source
Routing Protocol (DSR) for Mobile Ad Hoc Networks for
IPv4", RFC 4728, February 2007.
[RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
"Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
September 2007.
[RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol
Specification", RFC 5050, November 2007.
[RFC5326] Ramadas, M., Burleigh, S., and S. Farrell, "Licklider
Transmission Protocol - Specification", RFC 5326,
September 2008.
Authors' Addresses Authors' Addresses
Philip Levis Philip Levis
Stanford University Stanford University
358 Gates Hall, Stanford University 358 Gates Hall, Stanford University
Stanford, CA 94305-9030 Stanford, CA 94305-9030
USA USA
Email: pal@cs.stanford.edu Email: pal@cs.stanford.edu
 End of changes. 54 change blocks. 
281 lines changed or deleted 309 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/