Networking Working Group P. Levis Internet-Draft Stanford University Intended status: Informational JP. Vasseur Expires: May 20, 2008 Cisco Systems, Inc D. Culler Arch Rock November 17, 2007 Overview of Existing Routing Protocols for Low Power and Lossy Networks draft-levis-rl2n-overview-protocols-02 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 May 20, 2008. Copyright Notice Copyright (C) The IETF Trust (2007). 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 Levis, et al. Expires May 20, 2008 [Page 1] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 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]. Levis, et al. Expires May 20, 2008 [Page 2] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 Table of Contents 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 8 3.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2. OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4. Distance Vector protocols . . . . . . . . . . . . . . . . . . 9 4.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2. DSDV . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.3. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 10 4.4. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.5. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5. Routing Considerations . . . . . . . . . . . . . . . . . . . . 11 5.1. Multi-path routing . . . . . . . . . . . . . . . . . . . . 11 5.2. Resource awareness . . . . . . . . . . . . . . . . . . . . 12 5.3. Small footprint . . . . . . . . . . . . . . . . . . . . . 13 5.4. Small MTU . . . . . . . . . . . . . . . . . . . . . . . . 13 5.5. Flooding Control and Density Awareness . . . . . . . . . . 14 5.6. Low power . . . . . . . . . . . . . . . . . . . . . . . . 14 5.7. Multi-topology Routing . . . . . . . . . . . . . . . . . . 15 5.8. Scalability analysis . . . . . . . . . . . . . . . . . . . 15 6. Security Issues . . . . . . . . . . . . . . . . . . . . . . . 16 7. Manageability Issues . . . . . . . . . . . . . . . . . . . . . 16 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 9. Security Considerations . . . . . . . . . . . . . . . . . . . 16 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 16 11. Annex A - Routing protocol scalability analsysis . . . . . . . 16 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 12.1. Normative References . . . . . . . . . . . . . . . . . . . 20 12.2. Informative References . . . . . . . . . . . . . . . . . . 21 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 Intellectual Property and Copyright Statements . . . . . . . . . . 24 Levis, et al. Expires May 20, 2008 [Page 3] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 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 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 May 20, 2008 [Page 4] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 5] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 6] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 7] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 8] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 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. 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 May 20, 2008 [Page 9] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 "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 May 20, 2008 [Page 10] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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-rl2n-home-routing-reqs] and[I-D.pister-rl2n-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 May 20, 2008 [Page 11] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 12] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 13] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 14] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 15] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 16] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 17] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 18] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 19] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 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 May 20, 2008 [Page 20] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 12.2. Informative References [I-D.brandt-rl2n-home-routing-reqs] Vasseur, J., "Home Automation Routing Requirement in Low Power and Lossy Networks", draft-brandt-rl2n-home-routing-reqs-02 (work in progress), November 2007. [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-11 (work in progress), November 2007. [I-D.ietf-manet-nhdp] Clausen, T., "MANET Neighborhood Discovery Protocol (NHDP)", draft-ietf-manet-nhdp-04 (work in progress), July 2007. [I-D.ietf-manet-olsrv2] Clausen, T., "The Optimized Link State Routing Protocol version 2", draft-ietf-manet-olsrv2-04 (work in progress), July 2007. [I-D.pister-rl2n-indus-routing-reqs] Networks, D., Enns, R., Vasseur, J., and P. Thubert, "Industrial Routing Requirements in Low Power and Lossy Networks", draft-pister-rl2n-indus-routing-reqs-00 (work in progress), November 2007. [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", RFC 2740, December 1999. Levis, et al. Expires May 20, 2008 [Page 21] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 [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 May 20, 2008 [Page 22] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 2007 D Culler Arch Rock 657 Mission St. Suite 600 San Francisco, CA 94105 USA Email: dculler@archrock.com Levis, et al. Expires May 20, 2008 [Page 23] Internet-Draft draft-levis-rl2n-overview-protocols-02 November 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 May 20, 2008 [Page 24]