draft-ietf-roll-protocols-survey-01.txt   draft-ietf-roll-protocols-survey-02.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: March 29, 2009 S. Dawson-Haggerty Expires: April 20, 2009 S. Dawson-Haggerty
UC Berkeley UC Berkeley
September 25, 2008 October 17, 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-01 draft-ietf-roll-protocols-survey-02
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 March 29, 2009. This Internet-Draft will expire on April 20, 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
skipping to change at page 2, line 25 skipping to change at page 2, line 25
Table of Contents Table of Contents
1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 4
4. Suitability Summary . . . . . . . . . . . . . . . . . . . . . 5 4. Suitability Summary . . . . . . . . . . . . . . . . . . . . . 5
4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 6 4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 6
4.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 6 4.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 6
4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 7 4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 7
4.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 8 4.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 8
4.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 8 4.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 9
5. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 9 5. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 9
6. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 11 6. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 12
6.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.2. OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.2. OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7. Distance Vector protocols . . . . . . . . . . . . . . . . . . 13 7. Distance Vector protocols . . . . . . . . . . . . . . . . . . 13
7.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 7.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.2. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 13 7.2. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 14
7.3. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7.3. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
7.4. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7.4. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 14 8. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 15
8.1. IPv6 Neighbor Discovery . . . . . . . . . . . . . . . . . 14 8.1. IPv6 Neighbor Discovery . . . . . . . . . . . . . . . . . 15
8.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 15 8.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 15
9. Security Issues . . . . . . . . . . . . . . . . . . . . . . . 15 9. Security Considerations . . . . . . . . . . . . . . . . . . . 16
10. Manageability Issues . . . . . . . . . . . . . . . . . . . . . 15 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 16
12. Security Considerations . . . . . . . . . . . . . . . . . . . 15 12. Annex A - Routing protocol scalability analysis . . . . . . . 16
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 15 13. Annex B - Logarithmic scaling of control cost . . . . . . . . 19
14. Annex A - Routing protocol scalability analysis . . . . . . . 15 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20
15. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 14.1. Normative References . . . . . . . . . . . . . . . . . . . 20
15.1. Normative References . . . . . . . . . . . . . . . . . . . 19 14.2. Informative References . . . . . . . . . . . . . . . . . . 20
15.2. Informative References . . . . . . . . . . . . . . . . . . 19 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20 Intellectual Property and Copyright Statements . . . . . . . . . . 23
Intellectual Property and Copyright Statements . . . . . . . . . . 22
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
LLN: Low power and Lossy Network LLN: Low power and Lossy Network
skipping to change at page 8, line 28 skipping to change at page 8, line 28
the autonomous organization and configuration of the network at the the autonomous organization and configuration of the network at the
lowest possible energy cost [I-D.ietf-roll-urban-routing-reqs]. lowest possible energy cost [I-D.ietf-roll-urban-routing-reqs].
All routing protocols must transmit additional data to detect All routing protocols must transmit additional data to detect
neighbors, build routes, transmit routing tables, or otherwise neighbors, build routes, transmit routing tables, or otherwise
conduct routing. As low-power wireless networks can have very low conduct routing. As low-power wireless networks can have very low
data rates, protocols which require a minimum control packet rate can data rates, protocols which require a minimum control packet rate can
have unbounded control overhead. This is particularly true for have 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 significant control traffic even when there is no data
For these use cases, hard-coded timing constants are unacceptable, to send. For these use cases, hard-coded timing constants are
because they imply a prior knowledge of the expected data rate. unacceptable, because they imply a prior knowledge of the expected
data rate.
If control traffic is unbounded by data traffic, a protocol fails Of course, protocols require the ability to send at least a very
according to Control Cost metric. Protocols which pass bound their small amount of control traffic, in order to discover a topology.
control traffic rate to their data traffic. Protocols which pass do But this bootstrapping discovery and maintenance traffic should be
not use resources to maintain unused state. More specifically, any small: communicating once an hour is far more reasonable than
protocol which requires fixed-rate periodic control packets in the communicating once a second. So while control traffic should be
absence of data traffic fails. bounded by data traffic, it requires some leeway to bootstrap and
maintain a long-lived yet idle network.
In the case of control traffic, the communication rate (sum of
transmissions and receptions at a node) is a better measure than the
transmission rate (since energy is consumed for both transmissions
and receptions). Controlling the transmission rate is insufficient,
as it would mean that the energy cost (sum of transmission and
receptions) of control traffic could grow with O(L).
A protocol fails the control cost criterion if its per-node control
traffic (transmissions plus receptions) rate is not bounded by the
data rate plus a small constant. For example, a protocol using a
beacon rate only passes if it can be turned arbitrarily low, in order
to match the data rate. Furthermore, packet losses necessitate that
the control traffic may scale within a O(log(L)) factor of the data
rate. Meaning, if R is the data rate and e is the small constant,
then a protocol's control traffic must be on the order of O(R log(L)
+ e) to pass this criteria. The details of why O(log(L)) is
necessary are in Annex 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 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].
skipping to change at page 11, line 26 skipping to change at page 12, line 9
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. This table shows, based on the criteria described above,
whether these protocols meet ROLL criteria. Annex A contains the whether these protocols meet ROLL criteria. Annex A contains the
reasoning behind each value in the table. 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 ? ? 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
6. Link State Protocols 6. Link State Protocols
6.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
skipping to change at page 15, line 23 skipping to change at page 16, line 5
mechanisms for discovering a node's symmetric 2-hop neighborhood. It mechanisms for discovering a node's symmetric 2-hop neighborhood. It
maintains information on discovered links, their interfaces, status, maintains information on discovered links, their interfaces, status,
and neighbor sets. MANET-NHDP advertises a node's local link state; and neighbor sets. MANET-NHDP advertises a node's local link state;
by listening to all of its 1-hop neighbor's advertisements, a node by listening to all of its 1-hop neighbor's advertisements, a node
can compute its 2-hop neighborhood. MANET-NHDP link state can compute its 2-hop neighborhood. MANET-NHDP link state
advertisements can include a link quality metric. MANET-NHDP's node advertisements can include a link quality metric. MANET-NHDP's node
information base includes all interface addresses of each 1-hop information base includes all interface addresses of each 1-hop
neighbor: for low-power nodes, this state requirement can be neighbor: for low-power nodes, this state requirement can be
difficult to support. difficult to support.
9. Security Issues 9. Security Considerations
TBD
10. Manageability Issues
TBD This document presents, considers, and raises no security
considerations.
11. IANA Considerations 10. IANA Considerations
This document includes no request to IANA. This document includes no request to IANA.
12. Security Considerations 11. Acknowledgements
TBD
13. Acknowledgements
14. Annex A - Routing protocol scalability analysis 12. 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
skipping to change at page 17, line 39 skipping to change at page 18, line 10
can be advertised by the neighbor router [RFC3684]. Although the RFC can be advertised by the neighbor router [RFC3684]. Although the RFC
does not specify a policy for using these values, developing one does not specify a policy for using these values, developing one
could allow TBRPF to satisfy this requirement, leading to a ? for the could allow TBRPF to satisfy this requirement, leading to a ? for the
node cost requirement. node cost requirement.
"RIP" "RIP"
RIP is a distance vector protocol: all routers maintain a route to RIP is a distance vector protocol: all routers maintain a route to
all other routers. Routing table size is therefore O(N). However, all other routers. Routing table size is therefore O(N). However,
if destinations are known apriori, table size can be reduced to O(D), if destinations are known apriori, table size can be reduced to O(D),
resulting in a pass for table scalability. Each node broadcasts a resulting in a pass for table scalability. While standard RIP
beacon per period, and updates must be propagated by affected nodes, requires each node broadcast a beacon per period, and that updates
irrespective of data rate, failing the control cost metric. Loss must be propagated by affected nodes, triggered RIP only sends
triggers updates, only propagating if part of a best route, but even updates when network conditions change in response to the data path,
if the route is not actively being used, resulting in a fail for loss so RIP passes the control cost metric. Loss triggers updates, only
response. The rate of triggered updates is throttled, and these are propagating if part of a best route, but even if the route is not
only differential updates, yet this still doesn't account for other actively being used, resulting in a fail for loss response. The rate
control traffic (or tie it to data rate) or prevent the triggered of triggered updates is throttled, and these are only differential
updates from being flooded along non-active paths. [RFC2453] 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 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. It also receives a ? because the assigned to external networks. While RIP has the concept of a
concept of a network cost is introduced, which is added to link cost, network cost, it is insufficient to describe node properties and so
but does not describe its use. 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 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
skipping to change at page 19, line 18 skipping to change at page 19, line 37
for this criteria. Finally, a transmission failure only prompts an for this criteria. 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 criteria.
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.
15. References 13. Annex B - Logarithmic scaling of control cost
15.1. Normative References To satisfy the control cost criterion, a protocol's control traffic
communication rate must be bounded by the data rate, plus a small
constant. That is, if there is a data rate R, the control rate must
O(R + e), where e is a very small constant (epsilon). Furthermore,
the control rate may grow logarithmically with the size of the local
neighborhood L. Note that this is a bound: it represents the most
traffic a protocol may send, and good protocols may send much less.
So the control rate is bounded by O(R log(L)) + e.
The logarithmic factor comes from the fundamental limits of any
protocol that maintains a communication rate. For example, consider
e, the small constant rate of communication traffic allowed. Since
this rate is communication, to maintain O(e), then only one in L
nodes may transmit per time interval defined by e: that one node has
a transmission, and all other nodes have a reception, which prevents
them from transmitting. However, wireless networks are lossy.
Suppose that the network has a 10% packet loss rate. Then if L=10,
the expectation is that one of the nodes will drop the packet. Not
hearing a transmission, it will think it can transmit. This will
lead to 2 transmissions. If L=100, then one node will not hear the
first two transmissions, and there will be 3. The number of
transmissions, and the communication rate, will grow with O(log(L)).
This logarithmic bound can be prevented through explicit coordination
(e.g., leader election), but such approaches assumes state and
control traffic to elect leaders. As a logarithmic factor in terms
of density is not a large stumbling or major limitation, allowing the
much greater protocol flexibility it enables is worth its small cost.
14. References
14.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [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.
15.2. Informative References 14.2. Informative References
[I-D.ietf-manet-dymo] [I-D.ietf-manet-dymo]
Chakeres, I. and C. Perkins, "Dynamic MANET On-demand Chakeres, I. and C. Perkins, "Dynamic MANET On-demand
(DYMO) Routing", draft-ietf-manet-dymo-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.
 End of changes. 23 change blocks. 
60 lines changed or deleted 105 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/