--- 1/draft-ietf-roll-protocols-survey-01.txt 2008-10-18 01:12:23.000000000 +0200 +++ 2/draft-ietf-roll-protocols-survey-02.txt 2008-10-18 01:12:23.000000000 +0200 @@ -1,20 +1,20 @@ Networking Working Group P. Levis Internet-Draft Stanford University Intended status: Informational A. Tavakoli -Expires: March 29, 2009 S. Dawson-Haggerty +Expires: April 20, 2009 S. Dawson-Haggerty UC Berkeley - September 25, 2008 + October 17, 2008 Overview of Existing Routing Protocols for Low Power and Lossy Networks - draft-ietf-roll-protocols-survey-01 + draft-ietf-roll-protocols-survey-02 Status of this Memo 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 @@ -25,21 +25,21 @@ 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 March 29, 2009. + This Internet-Draft will expire on April 20, 2009. Abstract Networks of low power wireless devices introduce novel IP routing issues. Low-power wireless devices, such as sensors, actuators and smart objects, have difficult constraints: very limited memory, little processing power, and long sleep periods. As most of these devices are battery-powered, energy efficiency is critically important. Wireless link qualities can vary significantly over time, requiring protocols to make agile decisions yet minimize topology @@ -60,45 +60,44 @@ Table of Contents 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 4 4. Suitability Summary . . . . . . . . . . . . . . . . . . . . . 5 4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 6 4.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 6 4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 7 4.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 8 - 4.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 8 + 4.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 9 5. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 9 - 6. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 11 - 6.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 + 6. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 12 + 6.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.2. OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 - 6.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 12 + 6.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 13 7. Distance Vector protocols . . . . . . . . . . . . . . . . . . 13 7.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 - 7.2. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 13 + 7.2. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 14 7.3. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7.4. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 - 8. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 14 - 8.1. IPv6 Neighbor Discovery . . . . . . . . . . . . . . . . . 14 + 8. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 15 + 8.1. IPv6 Neighbor Discovery . . . . . . . . . . . . . . . . . 15 8.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 15 - 9. Security Issues . . . . . . . . . . . . . . . . . . . . . . . 15 - 10. Manageability Issues . . . . . . . . . . . . . . . . . . . . . 15 - 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 - 12. Security Considerations . . . . . . . . . . . . . . . . . . . 15 - 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 15 - 14. Annex A - Routing protocol scalability analysis . . . . . . . 15 - 15. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 - 15.1. Normative References . . . . . . . . . . . . . . . . . . . 19 - 15.2. Informative References . . . . . . . . . . . . . . . . . . 19 - Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20 - Intellectual Property and Copyright Statements . . . . . . . . . . 22 + 9. Security Considerations . . . . . . . . . . . . . . . . . . . 16 + 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 + 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 16 + 12. Annex A - Routing protocol scalability analysis . . . . . . . 16 + 13. Annex B - Logarithmic scaling of control cost . . . . . . . . 19 + 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 + 14.1. Normative References . . . . . . . . . . . . . . . . . . . 20 + 14.2. Informative References . . . . . . . . . . . . . . . . . . 20 + Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 + Intellectual Property and Copyright Statements . . . . . . . . . . 23 1. Terminology AODV: Ad-hoc On Demand Vector Routing DSR: Dynamic Source Routing DYMO: Dynamic Mobile On-Demand LLN: Low power and Lossy Network @@ -347,30 +346,50 @@ the autonomous organization and configuration of the network at the lowest possible energy cost [I-D.ietf-roll-urban-routing-reqs]. All routing protocols must transmit additional data to detect neighbors, build routes, transmit routing tables, or otherwise conduct routing. As low-power wireless networks can have very low data rates, protocols which require a minimum control packet rate can have unbounded control overhead. This is particularly true for event-driven networks, which only report data when certain conditions are met. Regions of a network which never meet the condition can be - forced to send control traffic even when there is no data to send. - For these use cases, hard-coded timing constants are unacceptable, - because they imply a prior knowledge of the expected data rate. + forced to send significant control traffic even when there is no data + to send. For these use cases, hard-coded timing constants are + unacceptable, because they imply a prior knowledge of the expected + data rate. - If control traffic is unbounded by data traffic, a protocol fails - according to Control Cost metric. Protocols which pass bound their - control traffic rate to their data traffic. Protocols which pass do - not use resources to maintain unused state. More specifically, any - protocol which requires fixed-rate periodic control packets in the - absence of data traffic fails. + Of course, protocols require the ability to send at least a very + small amount of control traffic, in order to discover a topology. + But this bootstrapping discovery and maintenance traffic should be + small: communicating once an hour is far more reasonable than + communicating once a second. So while control traffic should be + bounded by data traffic, it requires some leeway to bootstrap and + maintain a long-lived yet idle network. + + In the case of control traffic, the communication rate (sum of + transmissions and receptions at a node) is a better measure than the + transmission rate (since energy is consumed for both transmissions + and receptions). Controlling the transmission rate is insufficient, + as it would mean that the energy cost (sum of transmission and + receptions) of control traffic could grow with O(L). + + A protocol fails the control cost criterion if its per-node control + traffic (transmissions plus receptions) rate is not bounded by the + data rate plus a small constant. For example, a protocol using a + beacon rate only passes if it can be turned arbitrarily low, in order + to match the data rate. Furthermore, packet losses necessitate that + the control traffic may scale within a O(log(L)) factor of the data + rate. Meaning, if R is the data rate and e is the small constant, + then a protocol's control traffic must be on the order of O(R log(L) + + e) to pass this criteria. The details of why O(log(L)) is + necessary are in Annex B. 4.5. Link and Node Cost These two metrics specify how a protocol chooses routes for data packets to take through the network. Classical routing algorithms typically acknowledge the differing costs of paths and may use a shortest path algorithm to find paths. This is a requirement for low power networks, as links must be evaluated as part of an objective function across various metric types, such as minimizing latency and maximizing reliability [I-D.ietf-roll-indus-routing-reqs]. @@ -488,21 +508,21 @@ The next two sections summarize several well established routing protocols. This table shows, based on the criteria described above, whether these protocols meet ROLL criteria. Annex A contains the reasoning behind each value in the table. Protocol Table Loss Control Link Cost Node Cost OSPF fail fail fail pass fail OLSRv2 fail fail fail pass pass TBRPF fail pass fail pass ? - RIP pass fail fail ? ? + RIP pass fail pass ? fail AODV pass fail pass fail fail DYMO[-low] pass fail pass ? fail DSR fail pass pass fail fail 6. Link State Protocols 6.1. OSPF OSPF (specified in [RFC2328] for IPv4 and in [RFC2740] for IPv6)) is a link state protocol designed for routing within an Internet @@ -671,39 +692,32 @@ 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 low-power nodes, this state requirement can be difficult to support. -9. Security Issues - - TBD - -10. Manageability Issues +9. Security Considerations - TBD + This document presents, considers, and raises no security + considerations. -11. IANA Considerations +10. IANA Considerations This document includes no request to IANA. -12. Security Considerations - - TBD - -13. Acknowledgements +11. Acknowledgements -14. Annex A - Routing protocol scalability analysis +12. Annex A - Routing protocol scalability analysis This aim of this Annex is to provide the details for the analysis routing scalability analysis. "OSPF" OSPF floods link state through a network. Each router must receive this complete link set. OSPF fails the table size criterion because it requires each router to discover each link in the network, for a total routing table size which is O(N * L). This also causes it to @@ -777,39 +791,41 @@ can be advertised by the neighbor router [RFC3684]. Although the RFC does not specify a policy for using these values, developing one could allow TBRPF to satisfy this requirement, leading to a ? for the node cost requirement. "RIP" RIP is a distance vector protocol: all routers maintain a route to all other routers. Routing table size is therefore O(N). However, if destinations are known apriori, table size can be reduced to O(D), - resulting in a pass for table scalability. Each node broadcasts a - beacon per period, and updates must be propagated by affected nodes, - irrespective of data rate, failing the control cost metric. Loss - triggers updates, only propagating if part of a best route, but even - if the route is not actively being used, resulting in a fail for loss - response. The rate of triggered updates is throttled, and these are - only differential updates, yet this still doesn't account for other - control traffic (or tie it to data rate) or prevent the triggered - updates from being flooded along non-active paths. [RFC2453] + resulting in a pass for table scalability. While standard RIP + requires each node broadcast a beacon per period, and that updates + must be propagated by affected nodes, triggered RIP only sends + updates when network conditions change in response to the data path, + so RIP passes the control cost metric. Loss triggers updates, only + propagating if part of a best route, but even if the route is not + actively being used, resulting in a fail for loss response. The rate + of triggered updates is throttled, and these are only differential + updates, yet this still doesn't account for other control traffic (or + tie it to data rate) or prevent the triggered updates from being + flooded along non-active paths. [RFC2453] RIP receives a ? for link cost because while current implementations focus on hop count and that is the metric used in [RFC2453], the RFC also mentions that more complex metrics such as differences in bandwidth and reliability could be used. However, the RFC also states that real-time metrics such as link-quality would create instability and the concept of node cost only appears as metrics - assigned to external networks. It also receives a ? because the - concept of a network cost is introduced, which is added to link cost, - but does not describe its use. + assigned to external networks. While RIP has the concept of a + network cost, it is insufficient to describe node properties and so + RIP fails the node cost criterion.. "AODV" AODV table size is a function of the number of communicating pairs in the network, scaling with O(D). This is acceptable and so AODV passes the table size criteria. As an on-demand protocol, AODV does not generate any traffic until data is sent, and so control traffic is correlated with the data and so it receives a pass for control traffic. When a broken link is detected, AODV will use a precursor list maintained for each destination to inform downstream routers @@ -852,28 +867,59 @@ for this criteria. Finally, a transmission failure only prompts an unreachable destination to be sent to the source of the message, passing the loss response criteria. DSR fails the link cost criterion because its source routes are advertised only in terms of hops, such that all advertised links are considered equivalent. DSR also fails the node cost criterion because a node has no way of indicating its willingness to serve as a router and forward messages. -15. References +13. Annex B - Logarithmic scaling of control cost -15.1. Normative References + To satisfy the control cost criterion, a protocol's control traffic + communication rate must be bounded by the data rate, plus a small + constant. That is, if there is a data rate R, the control rate must + O(R + e), where e is a very small constant (epsilon). Furthermore, + the control rate may grow logarithmically with the size of the local + neighborhood L. Note that this is a bound: it represents the most + traffic a protocol may send, and good protocols may send much less. + So the control rate is bounded by O(R log(L)) + e. + + The logarithmic factor comes from the fundamental limits of any + protocol that maintains a communication rate. For example, consider + e, the small constant rate of communication traffic allowed. Since + this rate is communication, to maintain O(e), then only one in L + nodes may transmit per time interval defined by e: that one node has + a transmission, and all other nodes have a reception, which prevents + them from transmitting. However, wireless networks are lossy. + Suppose that the network has a 10% packet loss rate. Then if L=10, + the expectation is that one of the nodes will drop the packet. Not + hearing a transmission, it will think it can transmit. This will + lead to 2 transmissions. If L=100, then one node will not hear the + first two transmissions, and there will be 3. The number of + transmissions, and the communication rate, will grow with O(log(L)). + + This logarithmic bound can be prevented through explicit coordination + (e.g., leader election), but such approaches assumes state and + control traffic to elect leaders. As a logarithmic factor in terms + of density is not a large stumbling or major limitation, allowing the + much greater protocol flexibility it enables is worth its small cost. + +14. References + +14.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. -15.2. Informative References +14.2. Informative References [I-D.ietf-manet-dymo] Chakeres, I. and C. Perkins, "Dynamic MANET On-demand (DYMO) Routing", draft-ietf-manet-dymo-14 (work in progress), June 2008. [I-D.ietf-manet-nhdp] Clausen, T., Dearlove, C., and J. Dean, "MANET Neighborhood Discovery Protocol (NHDP)", draft-ietf-manet-nhdp-07 (work in progress), July 2008.