One document matched: draft-levis-rl2n-overview-protocols-00.txt
Networking Working Group P. Levis
Internet-Draft Stanford University
Intended status: Informational JP. Vasseur
Expires: January 1, 2008 Cisco Systems, Inc
D. Culler
Arch Rock
June 30, 2007
Overview of Existing Wireless Mesh Routing Protocols for Low Power and
Lossy Networks
draft-levis-rl2n-overview-protocols-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 January 1, 2008.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Abstract
Networks of low power wireless devices introduce novel IP routing
issues. Nodes (such as sensor, actuator or various forms of objects)
are constrained in several ways: limited memory and processing power
and so on. Furthermore most of them are battery-powered thus making
Levis, et al. Expires January 1, 2008 [Page 1]
Internet-Draft draft-levis-rl2n-overview-protocols-00 June 2007
the use of energy efficient routing protocol of high importance.
Wireless links can vary significantly over time, requiring protocols
to make agile decisions yet minimize the energy cost of topology
changes. Thus such networks also referred to as L2N (Low Power and
Lossy networks) have very specific routing requirements that are
partially addresses by existing mesh routing protocols. The aim of
this document is to provide a brief survey of their strengths and
weaknesses with respect to these issues and to provide an overview of
the major open IETF protocols in this space, in order to provide
guidance on how their lessons 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].
Levis, et al. Expires January 1, 2008 [Page 2]
Internet-Draft draft-levis-rl2n-overview-protocols-00 June 2007
Table of Contents
1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 6
3.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2. OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4. Distance Vector protocols . . . . . . . . . . . . . . . . . . 7
4.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2. DSDV . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.3. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 7
4.4. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.5. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5. Routing Considerations . . . . . . . . . . . . . . . . . . . . 8
5.1. Multi-path routing . . . . . . . . . . . . . . . . . . . . 8
5.2. Resource awareness . . . . . . . . . . . . . . . . . . . . 9
5.3. Small footprint . . . . . . . . . . . . . . . . . . . . . 9
5.4. Small MTU . . . . . . . . . . . . . . . . . . . . . . . . 9
5.5. Flooding Control and Density Awareness . . . . . . . . . . 10
5.6. Low power . . . . . . . . . . . . . . . . . . . . . . . . 10
5.7. Multi-topology Routing . . . . . . . . . . . . . . . . . . 10
6. Security Issues . . . . . . . . . . . . . . . . . . . . . . . 10
7. Manageability Issues . . . . . . . . . . . . . . . . . . . . . 10
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
9. Security Considerations . . . . . . . . . . . . . . . . . . . 10
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 11
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11
11.1. Normative References . . . . . . . . . . . . . . . . . . . 11
11.2. Informative References . . . . . . . . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
Intellectual Property and Copyright Statements . . . . . . . . . . 12
Levis, et al. Expires January 1, 2008 [Page 3]
Internet-Draft draft-levis-rl2n-overview-protocols-00 June 2007
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 Networks
LSA: Link State Advertisement
LSDB: Link State Database
OLSR: Optimized Link State Routing
RL2N: Routing in Low power and Loosy Networks
TDMA: Time Division Multiple Access
2. Introduction
Networks of low power wireless devices introduce novel IP routing
issues. Nodes (such as sensor, actuator or various forms of objects)
are constrained in several ways: limited memory and processing power
and so on. Furthermore most of them are battery-powered thus making
the use of energy efficient routing protocol of high importance.
Wireless links can vary significantly over time, requiring protocols
to make agile decisions yet minimize the energy cost of topology
changes. Thus such networks also referred to as L2N (Low Power and
Lossy networks) have very specific routing requirements that are
partially addresses by existing mesh routing protocols. The aim of
this document is not to provide an exhaustive tutorial on routing
protocols but to provide a brief survey of their strengths and
weaknesses with respect to these issues and to provide an overview of
Levis, et al. Expires January 1, 2008 [Page 4]
Internet-Draft draft-levis-rl2n-overview-protocols-00 June 2007
the major open IETF protocols in this space, in order to provide
guidance on how their lessons can be leveraged in future protocol
design.
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 floods the local
topology information in the form of a Link State Advertisement packet
using a reliable flooding mechanism across the network. The
collection of LSAs constitutes the Link State Database (LSDB) that
represents the network topology. Thus each node in the network has a
complete view of the network topology. Each router then uses the
LSDB to compute the routing table where each entry (reachable IP
destination address) points to the next hop along the shortest path
according to some metric.
A distance vector protocol exchanges routing information, rather than
link, information. A distance vector protocol exchanges information
with its "neighbors," or nodes with which it has link layer
connectivity. Tunneling and similar mechanisms can virtualize link
layer connectivity to allow neighbors that are multiple layer 2 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, ...), slow
convergence times to mention a few of them.
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 the Internet community is to use link state
routing protocols as IGPs for a number of reasons: in many cases
having a 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 protocol are usually superior in term of
Levis, et al. Expires January 1, 2008 [Page 5]
Internet-Draft draft-levis-rl2n-overview-protocols-00 June 2007
convergence speed (ability to find an alternate path in case of
network element failure), they are easier to debug and troubleshoot
and so on and require less bandwidth 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
Section 4.5.
3. Link State Protocols
3.1. OSPF
OSPF 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
routing topology within an area is hidden from other areas and IP
prefix reachability across areas (inter-area routing) is provided
using summary LSA. The hierarchy implies that there is a top-level
routing area (the backbone area) which connects other areas. Routing
adjacencies with neighbors are maintained by sending OSPF 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) extends OSPF to include
information on reservable, unreserved, and available bandwidth,
affinity and so on.
3.2. OLSR
Optimized Link State Routing (OLSR) is a link state routing protocol
intended 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 January 1, 2008 [Page 6]
Internet-Draft draft-levis-rl2n-overview-protocols-00 June 2007
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. Together, these optimizations mean that an OLSR node
maintains closer to O(n) rather than O(n^2) state.
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.
4. Distance Vector protocols
4.1. RIP
The Routing Information Protocol (RIP) (defined in [RFC1058])
predates OSPF. As it is a distance vector protocol, routing loops
can occur. RIP measures route cost in terms of hops, and detects
routing loops by observing a route cost approach infinity. 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.
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, which has O(n) state.
4.3. Ad-hoc On Demand Vector Routing (AODV)
AODV 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. If the route request
reaches the destination or a node that already has a route to the
destination, the recipient 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 issues a new request. If an AODV
network supports active flows to D different destinations, a node may
require O(D) state. In the worst case, an AODV node must maintain a
Levis, et al. Expires January 1, 2008 [Page 7]
Internet-Draft draft-levis-rl2n-overview-protocols-00 June 2007
route to every node, requiring O(n) state.
4.4. DYMO
Dynamic Mobile On-Demand routing (DYMO) is an evolution of AODV. The
basic functionality is the same, but it has different packet formats,
handling rules, and supports path accumulation. Like AODV, DYMO can
require each node to store O(D) state and uses hop counts as its
routing metric.
4.5. DSR
Dynamic Source Routing (DSR) 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 all nodes to store O(n) state. Instead, a node
originating packets needs to store up to O(n) state (the spanning
tree of routes). In degenerate topologies such as lines, a single
route may require O(n) state, but in meshes the state an originator
must maintain is dependent on the number of destinations and the
topology of the network.
5. Routing Considerations
[I-D.culler-rsn-routing-reqs] defines a set of requirements for L2N.
Note that [I-D.culler-rsn-routing-reqs] provides a superset of the
requirements of a wide variety of low power networks. 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 the
requirements of L2Ns. Of course, none of these protocols were
designed with all these considerations in mind, and so it is not
surprising that some of the issues remain unsolved.
5.1. Multi-path routing
DSR actively supports path diversity. OSPF and IS-IS allows ECMP
(Equal Cost Multipath). All other protocols use single path routing.
Note that it is not uncommon to require the 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).
Levis, et al. Expires January 1, 2008 [Page 8]
Internet-Draft draft-levis-rl2n-overview-protocols-00 June 2007
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.
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.
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 node-to-node
communication is not common. Requiring per-flow state in the network
fundamentally constrains the degree of concurrency in communication.
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. A typical
collection tree is 8K of code on a 16-bit micro controller.
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
example, is 24 bytes. Among the research protocols, BVR has the
largest header size, as it scales with the number of beacons, while
VRR and S4 have the smallest -- S4 is merely a collection tree packet
with a destination address in it.
Levis, et al. Expires January 1, 2008 [Page 9]
Internet-Draft draft-levis-rl2n-overview-protocols-00 June 2007
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.
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 vectors currently defined supports
for MTR.
6. Security Issues
TBD
7. Manageability Issues
TBD
8. IANA Considerations
This document includes no request to IANA.
9. Security Considerations
TBD
Levis, et al. Expires January 1, 2008 [Page 10]
Internet-Draft draft-levis-rl2n-overview-protocols-00 June 2007
10. Acknowledgements
11. References
11.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
11.2. Informative References
[I-D.culler-rsn-routing-reqs]
Cullerot, D. and J. Vasseur, "Routing Requirements for
Sensor Networks", draft-culler-rsn-routing-reqs-00 (work
in progress), April 2007.
[RFC1058] Hedrick, C., "Routing Information Protocol", RFC 1058,
June 1988.
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
D Culler
Arch Rock
657 Mission St. Suite 600
San Francisco, CA 94105
USA
Email: dculler@archrock.com
Levis, et al. Expires January 1, 2008 [Page 11]
Internet-Draft draft-levis-rl2n-overview-protocols-00 June 2007
Full Copyright Statement
Copyright (C) The IETF Trust (2007).
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.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
Levis, et al. Expires January 1, 2008 [Page 12]
| PAFTECH AB 2003-2026 | 2026-04-23 01:58:14 |