draft-ietf-roll-protocols-survey-00.txt   draft-ietf-roll-protocols-survey-01.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: February 6, 2009 S. Dawson-Haggerty Expires: March 29, 2009 S. Dawson-Haggerty
UC Berkeley UC Berkeley
August 5, 2008 September 25, 2008
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-00 draft-ietf-roll-protocols-survey-01
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of 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
skipping to change at page 1, line 36 skipping to change at page 1, line 36
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 February 6, 2009. This Internet-Draft will expire on March 29, 2009.
Abstract Abstract
Networks of low power wireless devices introduce novel IP routing Networks of low power wireless devices introduce novel IP routing
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 requirements that existing mesh protocols only partially address. has novel requirements that existing protocols may not address. This
This document provides a brief survey of the strengths and weaknesses document provides a brief survey of the strengths and weaknesses of
of existing protocols with respect to this class of networks. It existing protocols with respect to this class of networks. From this
provides guidance on how lessons from existing and prior efforts can survey it examines whether existing protocols as described in RFCs
be leveraged in future protocol design. and mature drafts could be used without modification in these
networks, or whether further work is necessary.
Requirements Language Requirements Language
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].
Table of Contents Table of Contents
1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Suitability Summary . . . . . . . . . . . . . . . . . . . . . 4 3. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 5 4. Suitability Summary . . . . . . . . . . . . . . . . . . . . . 5
3.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 5 4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 6
3.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 6 4.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 6
3.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 6 4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 7
3.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 7 4.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 8
4. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 7 4.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 8
5. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 9 5. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 9
5.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 6. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 11
5.2. OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 6.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.2. OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6. Distance Vector protocols . . . . . . . . . . . . . . . . . . 11 6.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 7. Distance Vector protocols . . . . . . . . . . . . . . . . . . 13
6.2. DSDV . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 7.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.3. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 12 7.2. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 13
6.4. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 7.3. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.5. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 7.4. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
7. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 13 8. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 14
7.1. IPv6 Neighbor Discovery . . . . . . . . . . . . . . . . . 13 8.1. IPv6 Neighbor Discovery . . . . . . . . . . . . . . . . . 14
7.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 13 8.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 15
8. Security Issues . . . . . . . . . . . . . . . . . . . . . . . 13 9. Security Issues . . . . . . . . . . . . . . . . . . . . . . . 15
9. Manageability Issues . . . . . . . . . . . . . . . . . . . . . 14 10. Manageability Issues . . . . . . . . . . . . . . . . . . . . . 15
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15
11. Security Considerations . . . . . . . . . . . . . . . . . . . 14 12. Security Considerations . . . . . . . . . . . . . . . . . . . 15
12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 14 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 15
13. Annex A - Routing protocol scalability analysis . . . . . . . 14 14. Annex A - Routing protocol scalability analysis . . . . . . . 15
14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18 15. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19
14.1. Normative References . . . . . . . . . . . . . . . . . . . 18 15.1. Normative References . . . . . . . . . . . . . . . . . . . 19
14.2. Informative References . . . . . . . . . . . . . . . . . . 18 15.2. Informative References . . . . . . . . . . . . . . . . . . 19
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20
Intellectual Property and Copyright Statements . . . . . . . . . . 21 Intellectual Property and Copyright Statements . . . . . . . . . . 22
1. Terminology 1. Terminology
AODV: Ad-hoc On Demand Vector Routing AODV: Ad-hoc On Demand Vector Routing
DSDV: Destination Sequenced Distance Vector
DSR: Dynamic Source Routing DSR: Dynamic Source Routing
DYMO: Dynamic Mobile On-Demand DYMO: Dynamic Mobile On-Demand
LLN: Low power and Lossy Network
LSA: Link State Advertisement
LSDB: Link State Database
MANET: Mobile Ad-hoc Networks MANET: Mobile Ad-hoc Networks
MAC: Medium Access Control MAC: Medium Access Control
MPLS: Multiprotocol Label Switching MPLS: Multiprotocol Label Switching
MPR: Multipoint Relays MPR: Multipoint Relays
MTU: Maximum Transmission Unit MTU: Maximum Transmission Unit
LSA: Link State Advertisement
LSDB: Link State Database
OLSR: Optimized Link State Routing OLSR: Optimized Link State Routing
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
2. Introduction 2. Introduction
Wireless is increasingly important to computer networking. As Wireless is increasingly important to computer networking. As
Moore's Law has reduced computer prices and form factors, networking Moore's Law has reduced computer prices and form factors, networking
skipping to change at page 4, line 17 skipping to change at page 4, line 17
smaller, lower power, and more numerous devices has led to new low- smaller, lower power, and more numerous devices has led to new low-
power wireless link layers to support them. In practice, wireless power wireless link layers to support them. In practice, wireless
networks observe much higher loss rates than wired ones do, and low- networks observe much higher loss rates than wired ones do, and low-
power wireless is no exception. Furthermore, many of these networks power wireless is no exception. Furthermore, many of these networks
will include powered as well as energy constrained nodes. will include powered as well as energy constrained nodes.
Nevertheless, for cost and scaling reasons, many of these powered Nevertheless, for cost and scaling reasons, many of these powered
devices will still have limited resources. devices will still have limited resources.
These low power and lossy networks introduce constraints and These low power and lossy networks introduce constraints and
requirements that other networks typically do not possess requirements that other networks typically do not possess
([I-D.brandt-roll-home-routing-reqs] and ([I-D.ietf-roll-home-routing-reqs] and
[I-D.ietf-roll-indus-routing-reqs]). This document examines existing [I-D.ietf-roll-indus-routing-reqs]). As they were not designed with
routing protocols and how well they can be applied to low power and these requirements in mind, existing protocols may or may not work
lossy networks. It provides a basic framework with which to compare well in LLNs. The first step to reaching consensus on a routing
the costs and benefits of different protocol designs and examines protocol for LLNs is to decide which of these two is true. If an
existing protocols within this framework. From these observations it existing protocol can meet LLN requirements without any changes, then
provides guidance on how existing solutions can be leveraged in barring extenuating circumstances, it behooves us to use an existing
future protocol design. standard. However, if no current protocol can meet LLN's
requirements, then further work will be needed to define and
standardize with a protocol that can. Whether or not such a protocol
involves modifications to an existing protocol or a new protocol
entirely is outside the scope of this document: this document simply
seeks to answer the question: do LLNs require a new protocol
specification document at all?
3. Suitability Summary 3. Methodology
To answer the question of LLNs require new protocol specification
work, this document examines existing routing protocols and how well
they can be applied to low power and lossy networks. It provides a
set of criteria with which to compare the costs and benefits of
different protocol designs and examines existing protocols in terms
of these criteria.
The five criteria this document uses are derived from a set of drafts
that describe the requirements of a few major LLN application
scenarios. The five criteria, presented in Section 3, are neither
exhaustive nor complete. Instead, they are one specific subset of
high-level requirements shared across all of the application
requirement drafts. Because every application requirement draft
specifies these criteria, then a protocol which does not meet one of
them cannot be used without modifications or extensions. However,
because these criteria represent a subset of the intersection of the
application requirements, any given application domain may impose
additional requirements which a particular protocol may not meet.
For this reason, these criteria are "necessary but not sufficient."
A protocol that does not meet the criteria cannot be used as
specified, but it is possible that a protocol meets the criteria yet
is not able to meet the requirements of a particular application
domain. Nevertheless, a protocol that meets all of the criteria
would be very promising, and deserve a closer look and consideration
in light of LLN application domains.
This document considers "existing routing protocols" to be protocols
that are specified in RFCs or, in the cases of DYMO
[I-D.ietf-manet-dymo] or OLSRv2 [I-D.ietf-manet-olsrv2] , a very
mature draft which will most likely become an RFC. 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
through each specification and considering the best implementation
possible. The judgement is based on what a specification allows,
rather than any particular implementation of that specification. For
example, while many DYMO implementations use hopcount as a routing
metric, the DYMO specification allows a hop to add more than one to
the routing metric, so DYMO as a specification can support some links
or nodes being more costly than others.
4. Suitability Summary
In this section, we present five important requirements for routing In 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.
Our evaluation attempts to take a complicated and interrelated set of This evaluation attempts to take a complicated and interrelated set
design decisions and trade-offs and condense them to a simple "pass", of design decisions and trade-offs and condense them to a simple
"fail", or "?". As with any simplification, there is a risk of "pass", "fail", or "?". As with any simplification, there is a risk
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 metrics 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 metrics do not encompass all
application requirements. Instead, they are a common set of routing application requirements. Instead, they are a common set of routing
protocol requirements that most applications domains share. 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 in
several major ROLL application domains and so is unlikely to be a several major ROLL application domains and so is unlikely to be a
good candidate for further analysis and examination. Satisfying good candidate for further analysis and examination. Satisfying
these minimal criteria is necessary but not sufficient: they do not these minimal criteria is necessary but not sufficient: they do not
represent the complete intersection of application requirements and represent the complete intersection of application requirements and
applications introduce additional, more stringent requirements. But applications introduce additional, more stringent requirements. But
this simplified view provides a first cut of the applicability of this simplified view provides a first cut of the applicability of
existing protocols, and those that do satisfy them might be existing protocols, and those that do satisfy them might be
reasonable candidates for further study. reasonable candidates for further study.
The five metrics 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 metric. 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 appear to metric, and that the RFC defining the protocol does not, as written,
contain sufficient flexibility to alter the protocol to do so. contain sufficient flexibility to alter the protocol to do so.
Finally, "?" indicates that an implementation could exhibit Finally, "?" indicates that an implementation could exhibit
satisfactory performance while following the RFC, but that design satisfactory performance while following the RFC, but that the
considerations necessary to do so are not specified. implementation descisions necessary to do so are not specified and
may require some exploration. In other words, a "fail" means a
protocol would have to be modified so it is not compliant with its
RFC in order to meet the criterion, while a "?" means a protocol
would require a supplementary document further constraining and
specifying how a protocol should behave.
3.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 metrics, 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 single-hop local 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 metric from application requirements
in its corresponding section. in its corresponding section.
3.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 the application requirements documents mentioned key requirement by all three application requirements documents.
above, with size ranging from a minimum of 250 nodes Network sizes range from a minimum of 250 nodes in the home routing
([I-D.brandt-roll-home-routing-reqs]) to very large networks requirements [I-D.ietf-roll-home-routing-reqs] to very large networks
([I-D.dohler-roll-urban-routing-reqs]), and network depths of up to of "tens of thousands to millions" of devices noted of the urban
20 hops ([I-D.ietf-roll-indus-routing-reqs]). Given that network requirements [I-D.ietf-roll-urban-routing-reqs]. Networks are
expected to have similar size in industrial settings, the
requirements draft states that depths of up to 20 hops are to be
expected [I-D.ietf-roll-indus-routing-reqs]. Given that network
information maintained at each node is stored in routing and neighbor 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 metric examines whether routing tables scale within reasonable
memory resources of low-power nodes. According to this metric, memory resources of low-power nodes. According to this metric,
routing protocols that scale linearly with the size of the network or routing protocols that scale linearly with the size of the network or
a node's neighborhood fail. Scaling with the size of the network a node's neighborhood fail. Scaling with the size of the network
prevents networks from growing to reasonable size, while scaling with prevents networks from growing to reasonable size, while scaling with
the network density precludes dense deployments. However, as many the network density precludes dense deployments. However, as many
low-power and lossy networks behave principally as data collection low-power and lossy networks behave principally as data collection
networks and principally communicate through routers to data networks and principally communicate through routers to data
collection points in the larger Internet, scaling with the number of collection points in the larger Internet, scaling with the number of
such collection points is reasonable. Protocols whose state scales such collection points is reasonable. Protocols whose state scales
with the number of destinations pass. 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.
3.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,
pointing to the need to localize response to link failures with no pointing to the need to localize response to link failures with no
triggering of global network re-optimization, whether for reducing triggering of global network re-optimization, whether for reducing
traffic or for maintaining low route convergence times traffic or for maintaining low route convergence times
([I-D.brandt-roll-home-routing-reqs], ([I-D.ietf-roll-home-routing-reqs],
[I-D.dohler-roll-urban-routing-reqs], and [I-D.ietf-roll-urban-routing-reqs], and
[I-D.ietf-roll-indus-routing-reqs]). [I-D.ietf-roll-indus-routing-reqs]). The industrial routing
requirements draft states that protocols must be able to "recompute
paths based on underlying link characteristics which may change
dynamically", as well as reoptimize when the device set changes to
maintain service requirements. The protocol should also "always be
in the process of optimizing the system in response to changing link
statistics." Protocols with these properties should take care not to
require global updates.
A protocol which requires many link changes to propagate across the A protocol which requires many link changes to propagate across the
entire network fails. Protocols which constrain the scope of entire network fails. Protocols which constrain the scope of
information propagation to only when they affect routes to active information propagation to only when they affect routes to active
destinations, or to local neighborhoods, pass. destinations, or to local neighborhoods, pass. Protocols which allow
proactively path maintenance pass if the choice of which paths to
maintain is user-specified.
More precisely, loss responses that require O(N) transmissions fail, More precisely, loss responses that require O(N) transmissions fail,
while responses that can rely on O(1) local broadcasts or O(D) route while responses that can rely on O(1) local broadcasts or O(D) route
updates pass. updates pass.
3.4. Control Cost 4.4. Control Cost
Battery-operated devices are a critical component of all three Battery-operated devices are a critical component of all three
application spectrums, and as such special emphasis is placed on application spectrums, and as such special emphasis is placed on
minimizing power consumption to achieve long battery lifetime, minimizing power consumption to achieve long battery lifetime,
([I-D.brandt-roll-home-routing-reqs]), with multi-year deployments [I-D.ietf-roll-home-routing-reqs], with multi-year deployments being
being a common case ([I-D.ietf-roll-indus-routing-reqs]). In terms a common case [I-D.ietf-roll-indus-routing-reqs]. In terms of
of routing structure, any proposed L2N routing protocol ought to routing structure, any proposed L2N routing protocol ought to support
support the autonomous organization and configuration of the network the autonomous organization and configuration of the network at the
at the lowest possible energy cost lowest possible energy cost [I-D.ietf-roll-urban-routing-reqs].
([I-D.dohler-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 unbounded control overhead. This is particularly true for
event-driven networks, which only report data when certain conditions event-driven networks, which only report data when certain conditions
are met. Regions of a network which never meet the condition can be are met. Regions of a network which never meet the condition can be
forced to send control traffic even when there is no data to send. forced to send control traffic even when there is no data to send.
For these use cases, hard-coded timing constants are unacceptable, For these use cases, hard-coded timing constants are unacceptable,
because they imply a prior knowledge of the expected data rate. because they imply a prior knowledge of the expected data rate.
If control traffic is uncorrelated with data traffic, a protocol If control traffic is unbounded by data traffic, a protocol fails
fails according to Control Cost metric. Protocols which pass bound according to Control Cost metric. Protocols which pass bound their
their control traffic rate to their data traffic. Protocols which control traffic rate to their data traffic. Protocols which pass do
pass do not use resources to maintain unused state. More not use resources to maintain unused state. More specifically, any
specifically, any protocol which requires fixed-rate periodic control protocol which requires fixed-rate periodic control packets in the
packets in the absence of data traffic fails. absence of data traffic fails.
3.5. Link and Node Cost 4.5. Link and Node Cost
These two metrics specify how a protocol chooses routes for data These two metrics 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 routing through particular routers. Applications require
node or parameter constrained routing, which takes into account node node or parameter constrained routing, which takes into account node
properties abd attributes such as power, memory, and battery life properties and attributes such as power, memory, and battery life
that dictate a router's willingness or ability to route other that dictate a router's willingness or ability to route other
packets([I-D.brandt-roll-home-routing-reqs], packets. Home routing requirements note that devices will vary in
[I-D.dohler-roll-urban-routing-reqs]). Node cost refers to the their duty cycle, and that routing protocols should prefer nodes with
ability for a protocol to incorporate router properties into routing permanent power [I-D.ietf-roll-home-routing-reqs]. The urban
metrics and use node attributes for constraint-based routing. requirements note that routing protocols may wish to take advantage
of differing data processing and managment capabilities among network
devices [I-D.ietf-roll-urban-routing-reqs]. Finally, industrial
requirements cite differing lifetime requirements as an important
factor to account for [I-D.ietf-roll-indus-routing-reqs]. Node cost
refers to the ability for a protocol to incorporate router properties
into routing metrics and use node attributes for constraint-based
routing.
A "pass" indicates that the protocol contains a mechanism allowing A "pass" indicates that the protocol contains a mechanism allowing
these considerations to be considered when choosing routes. these considerations to be considered when choosing routes.
4. Routing Protocol Taxonomy 5. Routing Protocol Taxonomy
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
skipping to change at page 8, line 51 skipping to change at page 10, line 40
the topology that other nodes observe, and therefore may require 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.
Protocols Today 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, DSDV, and DYMO are distance vector protocols. protocol, while AODV and DYMO are distance vector protocols. The
The general consensus in core networks is to use link state routing general consensus in core networks is to use link state routing
protocols as IGPs for a number of reasons: in many cases having a protocols as IGPs for a number of reasons: in many cases having a
complete network topology view is required to adequately compute the complete network topology view is required to adequately compute the
shortest path according to some metrics. For some applications such shortest path according to some metrics. For some applications such
as MPLS Traffic Engineering it is even required to have the knowledge as MPLS Traffic Engineering it is even required to have the knowledge
of the Traffic Engineering Database for constraint based routing. of the Traffic Engineering Database for constraint based routing.
Furthermore link state protocols typically have superior convergence Furthermore link state protocols typically have superior convergence
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,
skipping to change at page 9, line 28 skipping to change at page 11, line 18
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 major protocol, DSR, does not easily fit into one of topology. One major protocol, DSR, does not easily fit into one of
these two classes. Although it is a distance vector protocol, DSR these two classes. Although it is a distance vector protocol, DSR
has several properties that make it differ from most other protocols has several properties that make it differ from most other protocols
in this class. We examine these differences in our discussion of in this class. We examine these differences in our discussion of
DSR. DSR.
The next two sections summarize several well established routing The next two sections summarize several well established routing
protocols. Later sections consider the properties of these protocol protocols. This table shows, based on the criteria described above,
with respect to ROLL requirements. This table shows, based on the whether these protocols meet ROLL criteria. Annex A contains the
criteria described above, whether these protocols meet ROLL criteria. reasoning behind each value in the table.
Protocol Table Loss Control Link Cost Node Cost Protocol Table Loss Control Link Cost Node Cost
OSPF fail fail fail pass fail OSPF fail fail fail pass fail
OLSRv2 fail fail fail pass pass OLSRv2 fail fail fail pass pass
TBRPF fail pass fail pass ? TBRPF fail pass fail pass ?
RIP pass fail fail ? fail RIP pass fail fail ? ?
AODV pass fail pass fail fail AODV pass fail pass fail fail
DSDV pass fail fail ? fail DYMO[-low] pass fail pass ? fail
DYMO[-low] pass fail pass ? ? DSR fail pass pass fail fail
DSR fail ? pass fail ?
5. Link State Protocols 6. Link State Protocols
5.1. OSPF 6.1. OSPF
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
summary LSAs. The hierarchy implies that there is a top-level summary LSAs. The hierarchy implies that there is a top-level
routing area (the backbone area) which connects other areas. Areas routing area (the backbone area) which connects other areas. Areas
may be connected to the back-bone area through a virtual link. OSPF may be connected to the back-bone area through a virtual link. OSPF
maintains routing adjacencies by sending hello messages. OSPF maintains routing adjacencies by sending hello messages. OSPF
calculates the shortest path to a node using link metrics (that may calculates the shortest path to a node using link metrics (that may
reflect the link bandwidth, propagation delay, ...). OSPF Traffic reflect the link bandwidth, propagation delay, ...). OSPF Traffic
Engineering (OSPF-TE, [RFC3630]) extends OSPF to include information Engineering (OSPF-TE, [RFC3630]) extends OSPF to include information
on reservable, unreserved, and available bandwidth. on reservable, unreserved, and available bandwidth.
5.2. OLSR 6.2. OLSR
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 route discovery packets wireless mesh networks. OLSR nodes flood route discovery packets
throughout the entire network, such that each node has a map of the throughout the entire network, such that each node has a map of the
mesh topology. Because link variations can lead to heavy flooding mesh topology. Because link variations can lead to heavy flooding
traffic when using a link state approach, OLSR establishes a topology traffic when using a link state approach, OLSR establishes a topology
for minimizing this communication. Each node maintains a set of for minimizing this communication. Each node maintains a set of
nodes called its Multipoint Relays (MPR), which is a subset of the nodes called its Multipoint Relays (MPR), which is a subset of the
one-hop neighbors whose connectivity covers the two-hop neighborhood. one-hop neighbors whose connectivity covers the two-hop neighborhood.
skipping to change at page 11, line 5 skipping to change at page 12, line 38
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 constrained flooding allows it to quickly adapt to and
propagate topology changes. propagate 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.
5.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
nodes advertise and who chooses to aggregate information. In OLSR, nodes advertise and who chooses to aggregate information. In OLSR,
nodes select neighbors to be MPRs and advertise their link state for nodes select neighbors to be MPRs and advertise their link state for
them; in TBRPF, nodes elect themselves to advertise relevant link them; in TBRPF, nodes elect themselves to advertise relevant link
state based on whether it acts as a next hop. state based on whether it acts as a next hop.
6. Distance Vector protocols 7. Distance Vector protocols
6.1. RIP 7.1. RIP
The Routing Information Protocol (RIP) (defined in [RFC2453]) The Routing Information Protocol (RIP) (defined in [RFC2453])
predates OSPF. As it is a distance vector protocol, routing loops predates OSPF. As it is a distance vector protocol, routing loops
can occur and considerable work has been done to accelerate can occur and considerable work has been done to accelerate
convergence since the initial RIP protocols were introduced. RIP convergence since the initial RIP protocols were introduced. RIP
measures route cost in terms of hops, and detects routing loops by measures route cost in terms of hops, and detects routing loops by
observing a route cost approach infinity where "infinity" is referred observing a route cost approach infinity where "infinity" is referred
to as a maximum number of hops. RIP is typically not appropriate for to as a maximum number of hops. RIP is typically not appropriate for
situations where routes need to be chosen based on real-time situations where routes need to be chosen based on real-time
parameters such as measured delay, reliability, or load or when the parameters such as measured delay, reliability, or load or when the
skipping to change at page 11, line 44 skipping to change at page 13, line 30
"Triggered RIP" (defined in [RFC2091]) was originally designed to "Triggered RIP" (defined in [RFC2091]) was originally designed to
support "on-demand" circuits. The aim of triggered RIP is to avoid support "on-demand" circuits. The aim of triggered RIP is to avoid
systematically sending the routing database on regular intervals. systematically sending the routing database on regular intervals.
Instead, triggered RIP sends the database when there is a routing Instead, triggered RIP sends the database when there is a routing
update or a next hop adjacency change: once neighbors have exchanged update or a next hop adjacency change: once neighbors have exchanged
their routing database, only incremental updates need to be sent. their routing database, only incremental updates need to be sent.
Because incremental updates cannot depend on periodic traffic to Because incremental updates cannot depend on periodic traffic to
overcome loses, triggered RIP uses acknowledgment based mechanisms overcome loses, triggered RIP uses acknowledgment based mechanisms
for reliable delivery. for reliable delivery.
6.2. DSDV 7.2. Ad-hoc On Demand Vector Routing (AODV)
Destination Sequenced Distance Vector Routing uses distance vectors
to continuously maintain routes throughout a network. Unlike RIP,
DSDV uses per-node sequence numbers to provide a total ordering on
route information age in order to prevent loops. In DSDV, each node
maintains a route to each other node.
6.3. 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 mobile ad-hoc networks. When one AODV node requires a route to
another, it floods a request in the network to discover a route. A another, it floods a request in the network to discover a route. A
depth-scoped flooding process avoids discovery from expanding to the depth-scoped flooding process avoids discovery from expanding to the
most distant regions of the network that are in the opposite most distant regions of the network that are in the opposite
direction of the destination. AODV chooses routes that have the direction of 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 does not maintain routes to all nodes as DSDV does; demand it only maintains routes for active nodes. When a link
instead, 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. giving loss response a fail.
6.4. DYMO 7.3. DYMO
Dynamic Mobile On-Demand routing (DYMO) (([I-D.ietf-manet-dymo]) is Dynamic Mobile On-Demand routing (DYMO) ([I-D.ietf-manet-dymo]) is an
an evolution of AODV. The basic functionality is the same, but it evolution of AODV. The basic functionality is the same, but it has
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 hop counts as its routing metric, but links may Like AODV, DYMO uses hop counts as its routing metric, but links may
have a cost >= 1, allowing DYMO to represent link costs. Like AODV, have a cost >= 1, allowing DYMO to represent link costs. Like AODV,
on link breaks DYMO issues a new route request message (RREQ), with a on link breaks DYMO issues a new route request message (RREQ), with a
higher sequence number so nodes do not respond from their route higher sequence number so nodes do not respond from their route
caches. Correspondingly, a route request can flood the entire caches. Correspondingly, a route request can flood the entire
network. network.
6.5. DSR 7.4. DSR
Dynamic Source Routing ([RFC4728]) is a distance vector protocol, but Dynamic Source Routing ([RFC4728]) is a distance vector protocol, but
a DSR packet source explicitly specifies the route for each packet. a DSR packet source explicitly specifies the route for each packet.
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 DSDV, AODV, and DYMO, by pushing state into packet headers, Unlike AODV and DYMO, by pushing state into packet headers, DSR does
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.
7. Neighbor Discovery 8. Neighbor Discovery
A limit on maintained routing state (light footprint) prevents ROLL A limit on maintained routing state (light footprint) prevents ROLL
protocols from assuming they know all 1-hop, 2-hop, or N-hop protocols from assuming they know all 1-hop, 2-hop, or N-hop
neighbors. For this reason, while protocols such as MANET-NHDP neighbors. For this reason, while protocols such as MANET-NHDP
([I-D.ietf-manet-nhdp]) and IPv6's neighbor discovery ([RFC4861]) ([I-D.ietf-manet-nhdp]) and IPv6's neighbor discovery ([RFC4861])
provide basic mechanisms for discovering link-layer neighbors, not provide basic mechanisms for discovering link-layer neighbors, not
all of their features are relevant. This section describes these two all of their features are relevant. This section describes these two
protocols, their capabilities, and how ROLL protocols could leverage protocols, their capabilities, and how ROLL protocols could leverage
them. them.
7.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
single-hop neighbors as well as routers that can forward packets past single-hop neighbors as well as routers that can forward packets past
the local neighborhood. There is an implicit assumption that the the local neighborhood. There is an implicit assumption that the
delegation of whether a node is a router or not is static (e.g., delegation of whether a node is a router or not is static (e.g.,
based on a wired topology). The fact that all routers must respond based on a wired topology). The fact that all routers must respond
to a Router Solicitation requires that the number of routers with a to a Router Solicitation requires that the number of routers with a
1-hop neighborhood is small, or there will be a reply implosion. 1-hop neighborhood is small, or there will be a reply implosion.
Furthermore, IPv6 neighbor discovery's support of address Furthermore, IPv6 neighbor discovery's support of address
autoconfiguration assumes address provisioning, in that addresses autoconfiguration assumes address provisioning, in that addresses
reflect the underlying communication topology. IPv6 neighbor reflect the underlying communication topology. IPv6 neighbor
discovery does not consider asymmetric links. Nevertheless, it may discovery does not consider asymmetric links. Nevertheless, it may
be possible to extend and adapt IPv6's mechanisms to wireless in be possible to extend and adapt IPv6's mechanisms to wireless in
order to avoid response storms and implosions. order to avoid response storms and implosions.
7.2. MANET-NHDP 8.2. MANET-NHDP
The MANET Neighborhood Discovery Protocol (MANET-NHDP) provides The MANET Neighborhood Discovery Protocol (MANET-NHDP) provides
mechanisms for discovering a node's symmetric 2-hop neighborhood. It mechanisms for discovering a 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.
8. Security Issues 9. Security Issues
TBD TBD
9. Manageability Issues 10. Manageability Issues
TBD TBD
10. IANA Considerations 11. IANA Considerations
This document includes no request to IANA. This document includes no request to IANA.
11. Security Considerations 12. Security Considerations
TBD TBD
12. Acknowledgements 13. Acknowledgements
13. Annex A - Routing protocol scalability analysis 14. Annex A - Routing protocol scalability analysis
This aim of this Annex is to provide the details for the analysis This aim of this Annex is to provide the details for the analysis
routing scalability analysis. routing scalability analysis.
"OSPF" "OSPF"
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
the network link state even if the changed links were not being used. the network link state even if the changed links were not being used.
Since link state changes in wireless networks are often uncorrelated Since link state changes in wireless networks are often uncorrelated
with data traffic and are instead caused by external (environmental) with data traffic and are instead caused by external (environmental)
factors, this causes OSPF to fail both the control cost and loss factors, this causes OSPF to fail both the control cost and loss
response criteria. OSPF routers can impose policies on the use of response criteria. OSPF routers can impose policies on the use of
links and can consider link properties (Type of Service), so receive links and can consider link properties (Type of Service), as the cost
a pass for link cost. However, there is no way to associate metrics associated with an edge is configurable by the system administrator
with routers when computing paths, and so fails the node cost [RFC2328], so receive a pass for link cost. However, there is no way
criteria. to associate metrics with routers (as costs are only applied to
outgoing interfaces, i.e. edges) when computing paths, and so fails
the node cost criteria. While [RFC3630] discusses paths that take
into account node attributes, it specifically states that no known
algorithm or mechanism currently exists for incoporating this into
the OSPF RFC.
"OLSRv2" "OLSRv2"
OLSRv2 is a proactive link state protocol, flooding this information OLSRv2 is a proactive link state protocol, flooding this information
through a set of multipoint relays (MPRs). Routing state includes through a set of multipoint relays (MPRs). Routing state includes
1-hop neighbor information for each node in the network, 1-hop and 1-hop neighbor information for each node in the network, 1-hop and
2-hop information for neighbors, and a routing table, resulting in 2-hop information for neighbors (for MPR selection), and a routing
state proportional to network size and density (O(N*L + L^2)), and table (consisting of destination, and next hop), resulting in state
failing the table scalability criteria. proportional to network size and density (O(N*L + L^2)), and failing
the table scalability criteria.
Unacceptable control traffic overhead arises from flooding and Unacceptable control traffic overhead arises 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). As L is bounded by N, this means control traffic is O(N^2). MPRs reduce this load to O(N^2 / L). As the number of MPRs
proportional to O(N). MPRs reduce this load to O(N^2 / L). As the is inversely proportional to the density of the network and L is
number of MPRs is inversely proportional to the density of the bounded by N, this means control traffic is at best proportional to
network and L is bounded by N, this means control traffic is at best O(N), and fails the control cost metric.
proportional to O(N), and fails the control cost metric.
Furthermore, changes in the link set require re-flooding the network Furthermore, changes in the link set require immediately re-flooding
link state even if those links were not being used by routing, which the network link state even if those links were not being used by
fails the loss response metric. routing, which fails the loss response metric.
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 metrics.
"TBRPF" "TBRPF"
As a link state protocol, TBRPF routing table size scales with As a link state protocol where each node maintains a database of the
network size, leading to table sizes which are O(N * L) when a node entire network topology, TBRPF's routing table size scales with
receives disjoint link sets from its neighbors. However, this causes network size and density, leading to table sizes which are O(N * L)
the protocol to fail the table size criteria. The protocol's use of when a node receives disjoint link sets from its neighbors. This
differential updates should allow both fast response time and causes the protocol to fail the table size criteria. The protocol's
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 are triggered overhead criteria. However, its differential updates triggered by
by a link failure do not immediately cause a global re-flooding of link failure do not immediately cause a global re-flooding of state
state, leading to a pass for loss response. (but only to affected routers) [RFC3684], leading to a pass for loss
response.
TBRPF has a flexible neighbor management layer which enables it to TBRPF has a flexible neighbor management layer which enables it to
incorporate various link metrics into its routing decision. As a incorporate various types of link metrics into its routing decision
result, it receives a pass for link cost. It also provides a by enabling a USE_METRIC flag [RFC3684]. As a result, it receives a
mechanism whereby routers are able to advertise their "willingness to pass for link cost. It also provides a mechanism whereby routers can
route." Although the RFC does not specify a policy for using these maintain multiple link metrics to a single neighbor, some of which
values, developing one could allow TBRPF to satisfy this requirement, can be advertised by the neighbor router [RFC3684]. Although the RFC
leading to a ? for the node cost requirement. does not specify a policy for using these values, developing one
could allow TBRPF to satisfy this requirement, leading to a ? for the
node cost requirement.
"RIP" "RIP"
RIP is a distance vector protocol, with all routers maintaining a RIP is a distance vector protocol: all routers maintain a route to
route to all other routers, and as such table size being O(N). all other routers. Routing table size is therefore O(N). However,
if destinations are known apriori, table size can be reduced to O(D),
However, if destinations are known apriori, table size can be reduced resulting in a pass for table scalability. Each node broadcasts a
to O(D), resulting in a pass for table scalability. Each node beacon per period, and updates must be propagated by affected nodes,
broadcasts a beacon per period, and updates must be propagated by irrespective of data rate, failing the control cost metric. Loss
affected nodes, irrespective of data rate, failing the control cost triggers updates, only propagating if part of a best route, but even
metric. Loss triggers updates, only propagating if part of a best if the route is not actively being used, resulting in a fail for loss
route, even if the route is not actively being used, resulting in a response. The rate of triggered updates is throttled, and these are
fail for loss response. only differential updates, yet this still doesn't account for other
control traffic (or tie it to data rate) or prevent the triggered
updates from being flooded along non-active paths. [RFC2453]
RIP receives a ? for link cost, because while current implementations RIP receives a ? for link cost because while current implementations
focus on hop count, any number can theoretically be used to advertise focus on hop count and that is the metric used in [RFC2453], the RFC
link quality. There is no concept of router quality, and so it also mentions that more complex metrics such as differences in
receives a fail for the node cost criteria. bandwidth and reliability could be used. However, the RFC also
states that real-time metrics such as link-quality would create
instability and the concept of node cost only appears as metrics
assigned to external networks. It also receives a ? because the
concept of a network cost is introduced, which is added to link cost,
but does not describe its use.
"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 criteria. 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. This information is not sent (with a RERR) of the topology change. However, the RERR message is
as a flood, leading to an acceptable of traffic for a loss. forwarded by all nodes that have a route that uses the broken link,
Furthermore, the router encountering a broken link may initiate local even if the route is not currently active, leading to a fail for loss
repair via a scoped flood. However, link churn may also result in response [RFC3561].
RERR messages being flooded to the entire network. Therefore, AODV
receives a fail for loss response.
AODV allows the source router to wait and collect a number of RREP
messages before choosing which route is to be used. This allows that
router to evaluate the link cost of the different alternatives,
although it is not clear how this should be done. AODV fails the
link cost requirement because it does not appear that that a design
goal was to choose paths which are minimal under some metric. It
fails the node cost requirement because there is no way for a router
to indicate its [lack of] willingness to route while still adhering
to the RFC.
"DSDV"
DSDV is another distance vector protocol, similar to RIP, with the
only main difference being in the usage of destination-based sequence
numbers to prevent routing loops. As such the following analysis
applies, which is the same as RIP's.
DSDV receives a pass for scalability because table size can be AODV fails the link cost metric because the only metric used is hop
limited to O(D) if all destinations are known apriori. Control cost count, and this is hardcoded in the route table entry, according to
is a fail, because periodic beaconing, irrespective of data rate, is the RFC [RFC3561]. It fails the node cost requirement because there
required, with updates propagating throughout the network. Loss is no way for a router to indicate its [lack of] willingness to route
response is also a fail since although loss only results in while still adhering to the RFC.
propagation to routers that utilize that link in their routing
tables, there is no mechanism for restricting this propagation to
active routes, rather than all routes. Link cost is a ? since
theoretically distance metrics other than hops could be used, but are
not covered in the protocol description, and node cost is a fail as
there is no provision for router quality.
"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. Table size is somewhat precursor lists and compact various messages. It still passes the
smaller, including entries for neighboring DYMO routers and routes table size criteria because it only maintains routes requested by
passing through the router. Control overhead has been reduced RREQ messages, resulting in O(D) table size. Control traffic (RREQ,
somewhat, and DYMO does not generate spurious RERRs; these messages RREP, and RREQ) are still driven by data, and hence DYMO passes the
are only generated when a forwarding failure occurs. Nevertheless, control cost criterion. However, RERR messages are forwarded by any
these RERRs can flood the entire network, imposing an O(N) cost. nodes that have a route using the link, even if inactive, leading to
DYMO includes mechanisms to add additional routing information a fail of the loss reponse criteria [I-D.ietf-manet-dymo].
(potentially including router willingness), but does not define
explicit policy mechanisms for choosing routers along a path. Its While DYMO does indicate that the metric used for a link can vary
extensible packet format could allow router properties to be from 1-65535, it specifically refers to this as distance, which is
specified in headers, giving it a ? on node cost. Rather than rely incremented by at least one at each hop [I-D.ietf-manet-dymo],
solely on hopcount, DYMO allows links to have costs in the range of leading to a ? in link cost. While additional routing information
1-65535, but does not specify how these might be used, giving it a ? can be added DYMO messages, there is no mention of node cost, leading
on link cost. to a fail in node cost.
"DSR" "DSR"
DSR performs source routing of packets, discovering packets through a DSR performs on-demand route discovery, and source routing of
route discovery mechanism. Only table entries needed by the data are packets. It maintains a source route for all destinations, and also
maintained, which is equivalent to the number of unique next hops a blacklist of all unidirectional neighbor links [RFC4728], leading
needed to access all desired destinations. Control traffic is only to a total table size of O(D + L), failing the table size criterion.
initiated when a new route is being discovered, or when an existing Control traffic is completely data driven, and so DSR receives a pass
route fails, and as such is proportional to the data rate. Loss does for this criteria. Finally, a transmission failure only prompts an
not trigger updates, unless the path is used. Routes are selected unreachable destination to be sent to the source of the message,
based on hop count, with no mechanism for differentiating between passing the loss response criteria.
"routers".
DSR fails the table criterion because it maintains a blacklist of DSR fails the link cost criterion because its source routes are
neighbors with whom connectivity is not bidirectional: this scales advertised only in terms of hops, such that all advertised links are
with O(L). DSR receives a ? on the loss criterion because some of considered equivalent. DSR also fails the node cost criterion
its mechanisms, such as automatic route shortening and route cache because a node has no way of indicating its willingness to serve as a
suggest that it may be able to meet the loss criterion, but exactly router and forward messages.
how these are implemented will affect its efficiency. DSR passes the
control criterion because all control traffic is on-demand, and so is
bound to data traffic rates. DSR fails the link cost criterion
because its source routes are advertised only in terms of hops, such
that all advertised links are considered equivalent. DSR has a ? on
the node cost criterion because sources decide on whom to send
packets through, and nodes cannot announce their capabilities in this
regard. However, a new route reply option could possibly achieve
this goal.
14. References 15. References
14.1. Normative References 15.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.
14.2. Informative References 15.2. Informative References
[I-D.brandt-roll-home-routing-reqs]
Brandt, A., "Home Automation Routing Requirement in Low
Power and Lossy Networks",
draft-brandt-roll-home-routing-reqs-01 (work in progress),
May 2008.
[I-D.dohler-roll-urban-routing-reqs]
Dohler, M., Watteyne, T., Jacquenet, C., Madhusudan, G.,
and G. Chegaray, "Urban WSNs Routing Requirements in Low
Power and Lossy Networks",
draft-dohler-roll-urban-routing-reqs-01 (work in
progress), April 2008.
[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-14 (work in (DYMO) Routing", draft-ietf-manet-dymo-14 (work in
progress), June 2008. progress), June 2008.
[I-D.ietf-manet-nhdp] [I-D.ietf-manet-nhdp]
Clausen, T., Dearlove, C., and J. Dean, "MANET Clausen, T., Dearlove, C., and J. Dean, "MANET
Neighborhood Discovery Protocol (NHDP)", Neighborhood Discovery Protocol (NHDP)",
draft-ietf-manet-nhdp-07 (work in progress), July 2008. draft-ietf-manet-nhdp-07 (work in progress), July 2008.
[I-D.ietf-manet-olsrv2] [I-D.ietf-manet-olsrv2]
Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized
Link State Routing Protocol version 2", Link State Routing Protocol version 2",
draft-ietf-manet-olsrv2-07 (work in progress), July 2008. draft-ietf-manet-olsrv2-07 (work in progress), July 2008.
[I-D.ietf-roll-home-routing-reqs]
Brandt, A., Buron, J., and G. Porcu, "Home Automation
Routing Requirement in Low Power and Lossy Networks",
draft-ietf-roll-home-routing-reqs-03 (work in progress),
September 2008.
[I-D.ietf-roll-indus-routing-reqs] [I-D.ietf-roll-indus-routing-reqs]
Networks, D., Thubert, P., Dwars, S., and T. Phinney, Networks, D., Thubert, P., Dwars, S., and T. Phinney,
"Industrial Routing Requirements in Low Power and Lossy "Industrial Routing Requirements in Low Power and Lossy
Networks", draft-ietf-roll-indus-routing-reqs-01 (work in Networks", draft-ietf-roll-indus-routing-reqs-01 (work in
progress), July 2008. progress), July 2008.
[I-D.ietf-roll-urban-routing-reqs]
Dohler, M., Watteyne, T., Winter, T., Jacquenet, C.,
Madhusudan, G., Chegaray, G., and D. Barthel, "Urban WSNs
Routing Requirements in Low Power and Lossy Networks",
draft-ietf-roll-urban-routing-reqs-01 (work in progress),
July 2008.
[RFC2091] Meyer, G. and S. Sherry, "Triggered Extensions to RIP to [RFC2091] Meyer, G. and S. Sherry, "Triggered Extensions to RIP to
Support Demand Circuits", RFC 2091, January 1997. Support Demand Circuits", RFC 2091, January 1997.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453, [RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453,
November 1998. November 1998.
[RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", [RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6",
RFC 2740, December 1999. RFC 2740, December 1999.
 End of changes. 75 change blocks. 
270 lines changed or deleted 326 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/