Networking Working Group P. Levis
Internet-Draft Stanford University
Intended status: Informational JP. Vasseur
Expires: November 7, 2008 Cisco Systems, Inc
D. Culler
Arch Rock
May 6, 2008
Overview of Existing Routing Protocols for Low Power and Lossy Networks
draft-levis-roll-protocols-survey-00
Status of this Memo
By submitting this Internet-Draft, each author represents that any
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
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on November 7, 2008.
Abstract
Networks of low power wireless devices introduce novel IP routing
issues. Low-power wireless devices, such as sensors, actuators and
smart objects, have difficult constraints: very limited memory,
little processing power, and long sleep periods. As most of these
devices are battery-powered, energy efficiency is critically
important. Wireless link qualities can vary significantly over time,
requiring protocols to make agile decisions yet minimize topology
change energy costs. Such low power and lossy networks (L2Ns) have
routing requirements that existing mesh protocols only partially
Levis, et al. Expires November 7, 2008 [Page 1]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
address. This document provides a brief survey of the strengths and
weaknesses of existing protocols with respect to L2Ns. It provides
guidance on how lessons from existing and prior efforts can be
leveraged in future protocol design.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
Table of Contents
1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 7
3.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2. OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4. Distance Vector protocols . . . . . . . . . . . . . . . . . . 8
4.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2. DSDV . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 9
4.4. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.5. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5. Routing Considerations . . . . . . . . . . . . . . . . . . . . 10
5.1. Multi-path routing . . . . . . . . . . . . . . . . . . . . 10
5.2. Resource awareness . . . . . . . . . . . . . . . . . . . . 11
5.3. Small footprint . . . . . . . . . . . . . . . . . . . . . 12
5.4. Small MTU . . . . . . . . . . . . . . . . . . . . . . . . 12
5.5. Flooding Control and Density Awareness . . . . . . . . . . 13
5.6. Low power . . . . . . . . . . . . . . . . . . . . . . . . 13
5.7. Multi-topology Routing . . . . . . . . . . . . . . . . . . 14
5.8. Scalability analysis . . . . . . . . . . . . . . . . . . . 14
6. Security Issues . . . . . . . . . . . . . . . . . . . . . . . 15
7. Manageability Issues . . . . . . . . . . . . . . . . . . . . . 15
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15
9. Security Considerations . . . . . . . . . . . . . . . . . . . 15
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 15
11. Annex A - Routing protocol scalability analsysis . . . . . . . 15
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19
12.1. Normative References . . . . . . . . . . . . . . . . . . . 19
12.2. Informative References . . . . . . . . . . . . . . . . . . 20
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21
Intellectual Property and Copyright Statements . . . . . . . . . . 23
Levis, et al. Expires November 7, 2008 [Page 2]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
1. Terminology
AODV: Ad-hoc On Demand Vector Routing
DSDV: Destination Sequenced Distance Vector
DSR: Dynamic Source Routing
DYMO: Dynamic Mobile On-Demand
MANET: Mobile Ad-hoc Networks
MAC: Medium Access Control
MPLS: Multiprotocol Label Switching
MPR: Multipoint Relays
MTU: Maximum Transmission Unit
L2N: Low power and Lossy Network
LSA: Link State Advertisement
LSDB: Link State Database
OLSR: Optimized Link State Routing
RL2N: Routing in Low power and Lossy Networks
TDMA: Time Division Multiple Access
2. Introduction
Wireless is increasingly important to computer networking. As
Moore's Law has reduced computer prices and form factors, networking
includes not only servers and desktops, but laptops, palmtops, and
cellphones. As computing device costs and sizes have shrunk, small
wireless sensors, actuators, and smart objects have emerged as an
important next step in inter-networking. The sheer number of the
low-power networked devices means that they cannot depend on human
intervention (e.g., adjusting position) for good networking: they
must have routing protocols that enable them to self-organize into
multihop networks.
Energy is a fundamental challenge in these devices. Convenience and
ease of use requires they be wireless and therefore battery powered.
Levis, et al. Expires November 7, 2008 [Page 3]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
Correspondingly, low power operation is a key concern for this class
of networked device. Cost points and energy limitations cause these
devices to have very limited resources: a few kB of RAM and a few MHz
of CPU is typical. As energy efficiency does not improve with
Moore's Law, these limitations are not temporary. This trend towards
smaller, lower power, and more numerous devices has led to new low-
power wireless link layers to support them. In practice, wireless
networks observe much higher loss rates than wired ones do, and low-
power wireless is no exception. Furthermore, many of these networks
will include powered as well as energy constrained nodes.
Nevertheless, for cost and scaling reasons, many of these powered
devices will still have limited resources.
These low power and lossy networks (L2Ns) introduce constraints and
requirements that other networks typically do not possess. Starting
from the L2N requirements stated in I-D.culler-rl2n-routing-reqs,
this document examines existing routing protocols and how well they
can be applied to L2Ns. It provides a basic framework with which to
compare the costs and benefits of different protocol designs and
examines existing protocols within this framework. From these
observations it provides guidance on how existing solutions can be
leveraged in future protocol design.
Routing Protocol Taxonomy
Routing protocols broadly fall into two classes: link-state and
distance-vector.
A router running a link-state protocol first establishes adjacency
with its neighbors and then reliably floods the local topology
information in the form of a Link State Advertisement packet. The
collection of LSAs constitutes the Link State Database (LSDB) that
represents the network topology, and routers synchronize their LSDBs.
Thus each node in the network has a complete view of the network
topology. Each router uses the LSDB to compute a routing table where
each entry (reachable IP destination address) points to the next hop
along the shortest path according to some metric. Link state
protocols (such as OSPF and IS-IS) support the concept of area
(called "level" for IS-IS) whereby all the routers in the same area
share the same view (they have the same LSDB) and areas are
interconnected by border routers according to specific rules that
advertise IP prefix reachability between areas.
A distance vector protocol exchanges routing information rather than
topological information. A router running a distance vector protocol
exchanges information with its "neighbors" with which it has link
layer connectivity. Tunneling and similar mechanisms can virtualize
link layer connectivity to allow neighbors that are multiple layer 2
Levis, et al. Expires November 7, 2008 [Page 4]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
hops away. Rather than a map of the network topology from which each
router can calculate routes, a distance vector protocol node has
information on what routes its neighbors have. Each node's set of
available routes is the union of its neighbors routes plus a route to
itself. In a distance vector protocol, nodes may only advertise
routes which are in use, enabling on-demand discovery. In comparison
to link state protocols, distance vector protocols have the advantage
of only requiring neighbor routing information, but also have
corresponding limitations which protocols must address, such as
routing loops, count to infinity, split horizon, and slow convergence
times. Furthermore, routing constraints are difficult to enforce
with distance vector protocols.
Neighbor discovery is a critical component of any routing protocol.
It enables a protocol to learn about which other nodes are nearby and
which it can use as the next hop for routes. As neighbor discovery
is a key component of many protocols, several general protocols and
protocol mechanisms have been designed to support it. A protocol's
neighbor set is defined by how many "hops" away the set reaches. For
example, the 1-hop neighbor set of a node is all nodes it can
directly communicate with at the link layer, while the 2-hop neighbor
set is its own 1-hop neighbor set and the 1-hop neighbor sets of all
of its 1-hop neighbors.
Because L2N nodes often have very limited resources for storing
routing state, protocols cannot assume that they can store complete
neighbor information. For example, an L2N node with 4kB of RAM
cannot store full neighbor state when it has 1000 other nodes nearby.
This means that L2N protocols must have mechanisms to decide which of
many possible neighbors they monitor as routable next hops. For
elements such as 2-hop neighborhoods, these decisions can have a
significant impact on the topology that other nodes observe, and
therefore may require intelligent logic to prevent effects such as
network partitions.
Later sections describe existing neighbor discovery protocols and how
they relate to the requirements of L2N routing protocols.
Protocols Today
Wired networks draw from both approaches. OSPF or IS-IS, for
example, are link-state protocols, while RIP is a distance-vector
protocol.
MANETs similarly draw from both approaches. OLSR is a link-state
protocol, while AODV, DSDV, and DYMO are distance vector protocols.
The general consensus in core networks is to use link state routing
protocols as IGPs for a number of reasons: in many cases having a
Levis, et al. Expires November 7, 2008 [Page 5]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
complete network topology view is required to adequately compute the
shortest path according to some metrics. For some applications such
as MPLS Traffic Engineering it is even required to have the knowledge
of the Traffic Engineering Database for constraint based routing.
Furthermore link state protocols typically have superior convergence
speeds (ability to find an alternate path in case of network element
failure), are easier to debug and troubleshoot, and introduce less
control packet overhead than distance vector protocols. In contrast,
distance vector protocols are simpler, require less computation, and
have smaller storage requirements. Most of these tradeoffs are
similar in wireless networks, with one exception. Because wireless
links can suffer from significant temporal variation, link state
protocols can have higher traffic loads as topology changes must
propagate globally, while in a distance vector protocol a node can
make local routing decisions with no effect on the global routing
topology. One major protocol, DSR, does not easily fit into one of
these two classes. Although it is a distance vector protocol, DSR
has several properties that make it differ from most other protocols
in this class. We discuss these differences in our discussion of
DSR.
The next two sections summarize several well established routing
protocols. Later sections consider the properties of these protocol
with respect to L2N routing requirements.
Neighbor Discovery
A limit on maintained routing state (light footprint) prevents L2N
protocols from assuming they know all 1-hop, 2-hop, or N-hop
neighbors. For this reason, while protocols such as MANET-NHDP
([I-D.ietf-manet-nhdp]) and IPv6's neighbor discovery ([RFC4861])
provide basic mechanisms for discovering link-layer neighbors, not
all of their features are relevant. This section describes these two
protocols, their capabilities, and how L2Ns can leverage them in
protocol design.
IPv6 neighbor discovery provides mechanisms for nodes to discover
single-hop neighbors as well as routers that can forward packets past
the local neighborhood. There is an implicit assumption that the
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
to a Router Solicitation requires that the number of routers with a
1-hop neighborhood is small, or there will be a reply implosion.
Furthermore, IPv6 neighbor discovery's support of address
autoconfiguration assumes address provisioning, in that addresses
reflect the underlying communication topology. IPv6 neighbor
discovery does not consider asymmetric links. Nevertheless, it may
Levis, et al. Expires November 7, 2008 [Page 6]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
be possible to extend and adapt IPv6's mechanisms to L2Ns in order to
avoid response storms and implosions.
The MANET Neighborhood Discovery Protocol (MANET-NHDP) provides
mechanisms for discovering a node's symmetric 2-hop neighborhood. It
maintains information on discovered links, their interfaces, status,
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
can compute its 2-hop neighborhood. MANET-NHDP link state
advertisements can include a link quality metric. MANET-NHDP's node
information base includes all interface addresses of each 1-hop
neighbor: for L2Ns, this state requirement can be difficult to
support.
3. Link State Protocols
3.1. OSPF
OSPF (specified in [RFC2328] for IPv4 and in [RFC2740] for IPv6)) is
a link state protocol designed for routing within an Internet
Autonomous System (AS). OSPF provides the ability to divide a
network into areas, which can establish a routing hierarchy. The
topology within an area is hidden from other areas and IP prefix
reachability across areas (inter-area routing) is provided using
summary LSAs. The hierarchy implies that there is a top-level
routing area (the backbone area) which connects other areas. Areas
may be connected to the back-bone area through a virtual link. OSPF
maintains routing adjacencies by sending hello messages. OSPF
calculates the shortest path to a node using link metrics (that may
reflect the link bandwidth, propagation delay, ...). OSPF Traffic
Engineering (OSPF-TE, [RFC3630]) extends OSPF to include information
on reservable, unreserved, and available bandwidth.
3.2. OLSR
Optimized Link State Routing (OLSR) (see [RFC3626] and
[I-D.ietf-manet-olsrv2]) is a link state routing protocol for
wireless mesh networks. OLSR nodes flood route discovery packets
throughout the entire network, such that each node has a map of the
mesh topology. Because link variations can lead to heavy flooding
traffic when using a link state approach, OLSR establishes a topology
for minimizing this communication. Each node maintains a set of
nodes called its Multipoint Relays (MPR), which is a subset of the
one-hop neighbors whose connectivity covers the two-hop neighborhood.
Each node that is an MPR maintains a set called its MPR selectors,
which are nodes that have chosen it to be an MPR.
Levis, et al. Expires November 7, 2008 [Page 7]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
OLSR uses these two sets to apply three optimizations. First, only
MPRs generate link state information. Second, nodes can use MPRs to
limit the set of nodes that forward link state packets. Third, an
MPR, rather than advertise all of its links, can advertise only links
to its MPR selectors. Together, these three optimizations can
greatly reduce the control traffic in dense networks, as the number
of MPRs should not increase significantly as a network becomes
denser.
OLSR selects routes based on hop counts, and assumes an underlying
protocol that determines whether a link exists between two nodes.
OLSR's constrained flooding allows it to quickly adapt to and
propagate topology changes.
OLSR is closely related to clustering algorithms in the wireless
sensor networking literature, in which cluster heads are elected such
that routing occurs over links between cluster heads and all other
nodes are leafs that communicate to a cluster head.
3.3. TBRPF
Topology Dissemination Based on Reverse Path Forwarding (see
[RFC3684]) is another proactive link state protocol. TBRPF computes
a source tree, which provides routes to all reachable nodes. It
reduces control packet overhead by having nodes only transmit a
subset of their source tree as well as by using differential updates.
The major difference between TBRPF and OLSR is the routing data that
nodes advertise and who chooses to aggregate information. In OLSR,
nodes select neighbors to be MPRs and advertise their link state for
them; in TBRPF, nodes elect themselves to advertise relevant link
state based on whether it acts as a next hop.
4. Distance Vector protocols
4.1. RIP
The Routing Information Protocol (RIP) (defined in [RFC2453])
predates OSPF. As it is a distance vector protocol, routing loops
can occur and considerable work has been done to accelerate
convergence since the initial RIP protocols were introduced. RIP
measures route cost in terms of hops, and detects routing loops by
observing a route cost approach infinity where "infinity" is referred
to as a maximum number of hops. RIP is typically not appropriate for
situations where routes need to be chosen based on real-time
parameters such as measured delay, reliability, or load or when the
network topology needs to be known for route computation.
Levis, et al. Expires November 7, 2008 [Page 8]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
"Triggered RIP" (defined in [RFC2091]) was originally designed to
support "on-demand" circuits. The aim of triggered RIP is to avoid
systematically sending the routing database on regular intervals.
Instead, triggered RIP sends the database when there is a routing
update or a next hop adjacency change: once neighbors have exchanged
their routing database, only incremental updates need to be sent.
Because incremental updates cannot depend on periodic traffic to
overcome loses, triggered RIP uses acknowledgment based mechanisms
for reliable delivery.
4.2. DSDV
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.
4.3. Ad-hoc On Demand Vector Routing (AODV)
AODV (specified in [RFC3561]) is a distance vector protocol intended
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
depth-scoped flooding process avoids discovery from expanding to the
most distant regions of the network that are in the opposite
direction of the destination. AODV chooses routes that have the
minimum hop count.
If an AODV route request reaches a node that has a route to the
destination (this includes the destination itself), that node sends a
reply along the reverse route. All nodes along the reverse route can
cache the route. When routes break due to topology changes, AODV
floods error messages and issues a new request. Because AODV is on-
demand, it does not maintain routes to all nodes as DSDV does;
instead, it only maintains routes for active nodes.
4.4. DYMO
Dynamic Mobile On-Demand routing (DYMO) (([I-D.ietf-manet-dymo]) is
an evolution of AODV. The basic functionality is the same, but it
has different packet formats, handling rules, and supports path
accumulation. Path accumulation allows a single DYMO route request
to generate routes to all nodes along the route to that destination.
Like AODV, DYMO uses hop counts as its routing metric.
Levis, et al. Expires November 7, 2008 [Page 9]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
4.5. DSR
Dynamic Source Routing ([RFC4728]) is a distance vector protocol, but
a DSR packet source explicitly specifies the route for each packet.
Because the route is determined at a single place -- the source --
DSR does not require sequence numbers or other mechanisms to prevent
routing loops, as there is no problem of inconsistent routing tables.
Unlike DSDV, AODV, and DYMO, by pushing state into packet headers,
DSR does not require per-destination routing state. Instead, a node
originating packets only needs to store a spanning tree of the part
of the network it is communicating with.
5. Routing Considerations
[I-D.culler-rl2n-routing-reqs] provides a superset of the
requirements a wide variety of L2Ns impose on routing. While it is
unlikely that a single routing protocol will satisfy all of them
well, it is useful to consider how well existing protocols meet these
requirements.
The goal of the R2LN initiative is derive requirements from specific
L2N application classes, and use these requirements as a foundation
in designing one or more L2N routing protocols. Use-case driven
requirements are documented in [I-D.brandt-roll-home-routing-reqs]
and[I-D.ietf-roll-indus-routing-reqs] for the industrial and
connected home applications respectively.
5.1. Multi-path routing
Whereas multipath routing has traditionally been viewed as a load
balancing mechanism, in L2Ns it is more fundamentally a reliability
mechanism. The connectivity between a pair of wireless nodes is
subject to frequent variations over time, regardless of traffic on
that link, because RF opaque obstructions may move between the two
devices, path loss characteristics of free space change with
environmental conditions, changes in the environment away from the
line of sight may introduce multipath effects, the noise level may be
raised at the receive due to other RF communication or unrelated
electromagnet emissions.
Layer 1 mechanisms to ameliorate these factors, such as multiple
antennas, that are common in physically large devices are less common
in small, embedded ones. Multipath routing provides an alternative
form of spatial diversity through multiple potential receivers.
However, none of the protocols in our survey (except in specific
conditions) maintain multiple candidates. Multiple candidates allow
the forwarding mechanism to select among them to achieve enhance
Levis, et al. Expires November 7, 2008 [Page 10]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
robustness, except where multiple paths of equal cost (ECMP) exist,
which is a strong restriction.
In particular, the tree-based discovery and reversal techniques in
AODV and DYMO bind many such single-path choices at time of
discovery. The route management traffic required to detect and
repair such links may exceed the actual data traffic of many L2N
applications dramatically. Reactive forwarding over diverse paths
may be more easily integrated into proactive protocols, such as OLSR,
and especially so among the reduced set of MPRs.
L2Ns of large extent will typically have multiple ingress/egress
points to well-provisioned networks. Thus, multipath routing has
considerations beyond the characteristics local to the hops along a
physically localized path. For communication external to the L2N, it
may be important to choose among geographically unrelated options in
exiting the L2N or in entering the L2N. The considerations are most
closely related to those in the inter-area routing where OSPF is
employed and are not yet addressed by the family of MANET protocols.
DSR actively supports path diversity. OSPF and IS-IS supports Multi-
path routing in case of ECMP (Equal Cost Multipath). All other
protocols use single path routing.
Note that it is not uncommon to require asymmetrical load balancing
of traffic flow along a set of paths of different cost. IGPs such as
OSPF, IS-IS or OLSR do not support such features (routing loop
issues).
5.2. Resource awareness
In all existing routing protocols the computed path is based on link
costs with no consideration of the node attributes and constraints.
None of the above protocols explicitly acknowledge the presence of
nodes whose unequal energy or memory resources may allow them to play
a different routing role. Such characteristics may be of a permanent
nature (mains powered device or device with sizable memory or both),
a predictable nature (solar powered device in full sun), or
evolutionary (battery has become depleted). In any case, the
criteria in the route selection is based on characteristics other
than the quality of the link or the capacity of the flows.
In such networks, it may be desirable to use a policy routing based
approach using hierarchical constraints: for example, avoid using a
path P1 traversing a node with Node-constraint > X (e.g. reflecting a
low battery) if an alternate path P2 can be found that provides a
path cost such that Cost(P2) < K * Cost(P1) (with K>1).
Levis, et al. Expires November 7, 2008 [Page 11]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
Furthermore, in some networks, it may be advantageous to follow a
path where data can be aggregated along the path to a data collector
(e.g. Sink). The knowledge of such node capability could be taken
into account by the routing process. Nevertheless, some of them can
manipulate their mechanisms to achieve this goal. For example, OLSR
can preferentially select more powerful nodes to be MPRs but this
does not provides a high degree of granularity in the routing
decision.
In other contexts, it might be desirable to select path avoiding
nodes with user defined characteristics (e.g a battery powered node
that is not easily reachable in a factory).
5.3. Small footprint
Most protocols have state (memory) requirements that can be
prohibitive in this domain, in particular the link state protocol
where a path to all destinations is systematically computed, which is
usually not need in most Sensor Networks or L2Ns where arbitrary
node-to-node communication is not yet common. For example, in
monitoring applications the vast majority of the flows are likely to
be between the sensor nodes and the data collection points. In
automation applications, the majority of the flows are likely to be
between actuation points (e.g. the light switch) and the associated
control points (the lights that are controlled by the switch). In
larger industrial settings, the control points feed to centralized
controllers for all control points, so again the majority of flows
are highly correlated. At the same time, field devices and remote
control units may move through the space introducing other point-to-
point flows, but in a monitory role.
For networks where there is traffic destinations are highly
concentrated, O(D) can be kept small. In the most degenerate case
where the traffic is mainly P2MP (Point to Multipoint) or MP2P
(Multipoint to Point), a collection tree, it can be O(1). Large and
complex protocols can have prohibitively large code bases. As a
simple point of comparison, typical collection tree implementations
today are 8K of code on a 16-bit microcontroller. Protocols such as
DYMO are slightly larger, as they typically require the same
complexity of link estimation by additionally have route maintenance
and timing. Protocols such as GPSR tend to be very large (20kB) due
to complexities that real world network behavior bring to
establishing very regular topologies such as planar graphs.
5.4. Small MTU
Most protocols intended for the Internet did not have the tiny MTUs
of low-power wireless in mind. The standard AODV header, for
Levis, et al. Expires November 7, 2008 [Page 12]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
example, is 24 bytes.
AODV requires route management packet bandwidth that increases with
the size of the network to maintain the consistency of the
distributed data structure. The protocols that carry a full path in
the routing packet generally assume the MTU is large enough to
accommodate the diameter of the network. This question of small MTU
is not expected to be only a short term concern. Low power generally
implies a low Eb/No (Energy per Bit/Spectral Noise Density) ratio.
The frame length shows up in the exponent part of the expect
probability of successful reception expression where it is applied to
a quantity smaller than one. In other words, low-power radios tend
to have simpler modulations and higher bit error rates, so shorter
packets are more likely to arrive successfully. Finally, small RAM
footprints make large MTUs difficult to handle.
5.5. Flooding Control and Density Awareness
Flooding is the straightforward approach to discover network routes
and neighbors. However, arbitrary retransmission can be dangerous
(Broadcast Storm), especially in very dense networks. Instead,
flooding protocols that adapt to network density (achieving coverage
without a retransmission implosion) enable flooding to maintain good
delivery rates and prevent network collapse.
5.6. Low power
None of the above protocols are inherently low power. Collection
trees are often used in a low-power application by simply pushing
power conservation to the MAC layer, either using TDMA or channel
sampling. Low-power operation typically adds latency, either through
TDMA or channel sampling.
Many L2N will employ deeply power managed layer 2 media managed
layers that leave the radio turned off for the vast majority (i.e
99%) of the time. These generally take one of two forms, sampling
techniques that frequently listen for very short intervals and
require the transmitter to expend effort to wake up the receiver and
TDMA-like techniques to schedule when a node listens to potentially
receive packets. Existing analysis of the routing protocols in the
survey assume underlying links are "always on." Sampling techniques
approximate this assumption, but still may impact the expected delay
of a flood, route notification propagation, etc. For networks where
data communication is measured in small packets every many minutes,
the overhead, scheduled reception may introduce minutes of delay.
Such characteristics may eliminate some protocol options.
Levis, et al. Expires November 7, 2008 [Page 13]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
5.7. Multi-topology Routing
MTR (Multi topology Routing) allows for multiple topologies that can
be used to route packets according to the shortest paths computed for
specific metrics but this comes at the price of high memory
consumption. None of the distance vector protocols above support
MTR, although link state protocols do such as OSPF and IS-IS do.
5.8. Scalability analysis
Scalability is undoubtedly a critical factor in L2Ns considering that
some networks may easily made of thousands of nodes. The aim of this
section is to consider how well existing protocols meet these
scalability requirements. To provide a sound basis for comparison,
we use parameters that present a very simplistic view of a real
network. The goal of these parameters is to give a sense of the
scalability of the algorithms of existing protocols, rather than the
absolute performance of specific implementations.
The parameters are:
N: Nodes in the network.
C: Communicating nodes: the set of nodes that are sources
and/or destinations.
P: Pairs of communicating nodes (active routes).
D: Destinations.
d: density, neighbors. The number of neighbors a node can
communicate with.
c: link churn. The rate at which links change between good
and bad.
h: maximum route length (hops).
We use these parameters, rather than traditional MANET ones such as
mobility speed, because they are more primitive and describe the
properties a protocol sees, rather than the causes of the properties.
Network traces and mobility models can be distilled to these four
properties. The S, D, and P parameters allows us to examine the
specialized workloads that are common to L2Ns, such as data
collection to one or more dedicated data sinks.
Using these parameters, we examine two properties that are critical
in L2Ns: control packet overhead and routing state. As these
analyses are very coarse big-0 notation, then undeniably smooth over
a few important constant factors and optimizations. These analyses
are intended to give a rough idea of how different properties affect
the scalability of the protocols: being big-O, they are of course
Levis, et al. Expires November 7, 2008 [Page 14]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
worst-case. The control overhead is the total traffic over the
network, while the routing state is the state an individual node must
maintain.
This table describes the scalability of existing protocols (details
for the analysis are provided in Section 11).
Protocol Intended Use Class Control Overhead Routing State
OSPF Wired Link-State O(NNdc) O(Nd)
OLSR Wireless Link-State O(NN) O(Nd)
TBRPF Wireless Link-State O(NN) O(Ndd)
RIP Wired Distance-Vector O(ND) O(D)
AODV Wireless Distance-Vector O(NCc) O(Cd)
DSDV Wireless Distance-Vector O(ND) O(D)
DYMO Wireless Distance-Vector O(NCch) O((Ch)+d)
DYMO-low Wireless Distance-Vector min(MN, NCc) O(C+d)
DSR Wireless Distance-Vector O(NDh) O(Dh)
6. Security Issues
TBD
7. Manageability Issues
TBD
8. IANA Considerations
This document includes no request to IANA.
9. Security Considerations
TBD
10. Acknowledgements
11. Annex A - Routing protocol scalability analsysis
This aim of this Annex is to provide the details for the analysis
routing scalability anaylsis.
Levis, et al. Expires November 7, 2008 [Page 15]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
OSPF
OSPF floods link state through a network. Each node has O(d) links.
So there are O(Nd) links in the network. Each node must receive this
complete link set, so there must be O(NNd) transmissions.
Furthermore, changes in the link set require re-flooding the network
link state, for a total cost of O(NNdc). As each node keeps the
entire link state of the network, this is O(Nd).
OLSR
Control overhead arises from TC and HELLO. TC messages spread
topology information between MPRs in the network, assisting in
construction of routing tables. These messages are flooded
periodically by every node, resulting in O(N^2) messages. In
practice, this is significantly improved by MPRs, which enable better
scaling characteristics. Since only MPRs forward topology
information, choosing restricted MPR sets diminish the number of
messages that must be sent. The sample TC emission interval provided
in RFC 3626 is 5 seconds. TC message size scales with d because
nodes advertise their neighbor set in each message.
HELLO messages inform 1-hop neighbors of a node's MPR Selector Set,
uni- and bi-directional neighbors, and duties as an MPR. Since each
node broadcasts these messages periodically, O(N) messages are
generated in the network every emission interval. These messages are
not propagated beyond one hop from their origin. The sample HELLO
emission interval provided in RFC 3626 is 2 seconds. HELLO message
size scales with d, as nodes advertise their entire one-hop neighbor
set in each message.
Routing state is held in a TC set, neighbor sets, and a routing
table. The TC set stores 1-hop neighbor information for each node in
the network, resulting in O(Nd) entries. This is the dominant
component in the scaling analysis. Other stored information are for
1-hop and 2-hop neighbors (O(d) and O(d^2) respectively) and a
routing table. The routing table stores a next hop for each
destination in the network, resulting in O(N) entries.
"TBRPF"
The information transmitted within a neighborhood is the union of all
the reported trees of the nodes, where the reported tree is defined
in the protocol. In the optimal case, this union comprises a single
copy of the entire Topology Graph, which has size O(n * d). Thus
given O(n / d) neighborhoods in the entire network, the total control
overhead will be O(n ^2). In the worst case, for example with high
churn, nodes within a neighborhood will transmit larger, overlapping
Levis, et al. Expires November 7, 2008 [Page 16]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
reported trees leading to more control traffic. Additionally, since
TBRPF makes extensive use of differental updates, the observed
control overhead may be much smaller if the topology is relatively
static.
Each node maintains the global network link-state, as reported by
each neighbor. Each of these copies has size O(n * d). Thus in the
worst case, where each neighbor reports the entire topology, this
information has size O(n * (d ^ 2)). However, in the optimal case
where each neighbor reports non-overlapping subsets of the topology,
the total state will be only O(n * d).
"RIP"
Control Overhead: nodes periodically beacon every T seconds. So
there is at least O(N) traffic from this every period T. Each
destination will add an entry to the updates, so the total number of
bytes sent is also proportional to D, or O(DN). There are also
triggered updates, when a route changes. This depends on c, on D
(the number of routes), and on the diameter of the network. When a
link breaks, all of the routes that use that link, from the sources
until the breaking point have to be updated. A link breaking is only
detected in 6T time.
Routing state is proportional to D, as each destination initiates a
tree propagation.
Traffic patterns: the dependence of state and control traffic on D
makes RIP-like protocols a good fit for collection where D ~ O(1), or
a few basestations. It can also be easily adapted to an anycast
model, in which more than one node act as a single logical
destination. In the opposite case of a few nodes to many, the
protocol will still build many routing trees.
"AODV"
Each node in the network maintains a table with several columns --
destination address, next hop address, destination sequence number,
valid destination sequence number flag, valid bit for this entry, hop
count, list of precursors, and lifetime of the entry. When a source
node wishes to construct a path to a destination, it floods a Route
Request (RREQ) message throughout the network. Upon receiving a
RREQ, a node inspects the packet and adds and entry in its table for
the source node, the destination node, and the node is received the
message from. If no next-hop exists for the given destination node,
the flood continues. When the flood finally reaches the destination,
the destination node sends a route reply message (RREP) along the
reverse path, back to the destination node. When an intermediate
Levis, et al. Expires November 7, 2008 [Page 17]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
node receives a RREP message, it adds the node it received the
message from into its table, then it forwards it to the next-hop node
towards the source node.
There are several entries in the table that dictate overall
performance. Each node maintains a precursor list for each
destination. A precursor list is the list of all nodes that use this
node as a next-hop towards a destination. The maximum size of the
precurser list is equal to the degree of this node. When link
failure is detected (through hello-message timeout or failure to
forward to the next-hop node), each node in the precursor list
receives a RERR message. In turn, each of those nodes follow the
same process. Eventually the RERR reaches every affected node that
routed to the given destination(s).
Because a node may need to maintain routing state on up to P routes
and each hop may have up to d precursors, AODV's routing state is O(P
* d).
Once it has established routes (assuming they do not decay), then
link churn can cause AODV to send RREQ and RREPs. Because each
routing change can require sending updated information through the
entire network, and the rate at which churn affects routes depends on
the number of active route, AODV's routing overhead is O(N * P * c).
"DSDV"
Routing state is proportional to D, as in the case of RIP.
Control Overhead: DSDV tries to reduce control traffic by using
differential updates whenever they are smaller than full dumps of the
routing table. The minimum update message is O(1), with no change.
The average update message is the advertisement of the k most
important route changes, where k is the number of advertisements that
fits in a packet. The routes included comprise the routes with
metric changes, and, if there is space after these, routes whose
sequence numbers have changed. In the worst case, an advertisement
is O(D). We multiply all these by N to obtain the network-wide
control traffic from advertisements. There is still the case of
triggered advertisements.
"DYMO/DYMO-low"
This analysis is in most aspects quite similar to the AODV analysis,
as the two major changes are in essence the removal of precursor
lists and path accumulation to reduce the number of messages. A
majority of changes deal with more compact packets or entries, but
this won't affect the big O() analysis. Furthermore, path
Levis, et al. Expires November 7, 2008 [Page 18]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
accumulation analysis is difficult, because in the worst case it buys
you nothing, but in the best case it can greatly reduce the number of
RREQ and RREP messages. Finally, they mention that an MPR based
backbone should be used for flooding, but with no mention of the
specific algorithm used for selecting these MPR's, no analysis can be
done. The closest that we can get is using the OLSR analysis. We
begin with an analysis of full DYMO, and then examine what changes
DYMO-low introduces. DYMO-Low was designed for 802.15.4 networks,
and specifically for 6LowPan, and makes a few modifications, such as
only allowing the destination to respond with an RREP, removing path
accumulation, and limiting the number of messages a node can send per
second. They also discuss the concept of control packet aggregation,
but we exclude this from our analysis because no algorithm or
mechanism for achieving this goal is provided.
Each node must maintain a routing table entry for each neighbor, as
well for each destination and source. Because of the path
accumulation feature, the node adds an entry for all intermediate
nodes along the path, which is h for each source and destination in
the worst case (if all paths are distinct and non-overlapping).
When a link breaks (due to churn), this message will continually be
broadcasted by all nodes that have a route entry for the target node,
potentially leading to N transmissions. We have to multiply this by
C, which approximates the number of destinations per node. Another
factor that must be considered is the the size of messages, which
will be on the order of O(h), since each node along the path adds its
own address.
DYMO-low is essentially DYMO without path accumulation. The one
major addition is a term M, which is the maximum control packet rate
a node will send.
"DSR"
Each node maintains a source route for each possible destination.
With D destinations and a hopcount of h, this is O(Dh) state.
Because nodes send source routes and there are N nodes, the control
overhead is O(NDh).
12. References
12.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
Levis, et al. Expires November 7, 2008 [Page 19]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
12.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-00 (work in progress),
February 2008.
[I-D.culler-rl2n-routing-reqs]
Vasseur, J. and D. Cullerot, "Routing Requirements for Low
Power And Lossy Networks",
draft-culler-rl2n-routing-reqs-01 (work in progress),
July 2007.
[I-D.ietf-manet-dymo]
Chakeres, I. and C. Perkins, "Dynamic MANET On-demand
(DYMO) Routing", draft-ietf-manet-dymo-13 (work in
progress), April 2008.
[I-D.ietf-manet-nhdp]
Clausen, T., Dearlove, C., and J. Dean, "MANET
Neighborhood Discovery Protocol (NHDP)",
draft-ietf-manet-nhdp-06 (work in progress), March 2008.
[I-D.ietf-manet-olsrv2]
Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized
Link State Routing Protocol version 2",
draft-ietf-manet-olsrv2-05 (work in progress),
February 2008.
[I-D.ietf-roll-indus-routing-reqs]
Networks, D. and P. Thubert, "Industrial Routing
Requirements in Low Power and Lossy Networks",
draft-ietf-roll-indus-routing-reqs-00 (work in progress),
April 2008.
[RFC1387] Malkin, G., "RIP Version 2 Protocol Analysis", RFC 1387,
January 1993.
[RFC2091] Meyer, G. and S. Sherry, "Triggered Extensions to RIP to
Support Demand Circuits", RFC 2091, January 1997.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453,
November 1998.
[RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6",
Levis, et al. Expires November 7, 2008 [Page 20]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
RFC 2740, December 1999.
[RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
Demand Distance Vector (AODV) Routing", RFC 3561,
July 2003.
[RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing
Protocol (OLSR)", RFC 3626, October 2003.
[RFC3630] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering
(TE) Extensions to OSPF Version 2", RFC 3630,
September 2003.
[RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology
Dissemination Based on Reverse-Path Forwarding (TBRPF)",
RFC 3684, February 2004.
[RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source
Routing Protocol (DSR) for Mobile Ad Hoc Networks for
IPv4", RFC 4728, February 2007.
[RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
"Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
September 2007.
Authors' Addresses
P Levis
Stanford University
Email: pal@cs.stanford.edu
JP Vasseur
Cisco Systems, Inc
1414 Massachusetts Avenue
Boxborough, MA 01719
USA
Email: jpv@cisco.com
Levis, et al. Expires November 7, 2008 [Page 21]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
D Culler
Arch Rock
657 Mission St. Suite 600
San Francisco, CA 94105
USA
Email: dculler@archrock.com
Levis, et al. Expires November 7, 2008 [Page 22]
Internet-Draft draft-levis-roll-protocols-survey-00 May 2008
Full Copyright Statement
Copyright (C) The IETF Trust (2008).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Levis, et al. Expires November 7, 2008 [Page 23]