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]