idnits 2.17.1 draft-ietf-roll-protocols-survey-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 17. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 922. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 933. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 940. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 946. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Expected the document's filename to be given on the first page, but didn't find any Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year == Line 410 has weird spacing: '... fail fai...' == Line 411 has weird spacing: '... fail fai...' == Line 412 has weird spacing: '... fail pas...' == Line 413 has weird spacing: '... pass fai...' == Line 414 has weird spacing: '... pass fai...' == (2 more instances...) == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. == Couldn't figure out when the document was first submitted -- there may comments or warnings related to the use of a disclaimer for pre-RFC5378 work that could not be issued because of this. Please check the Legal Provisions document at https://trustee.ietf.org/license-info to determine if you need the pre-RFC5378 disclaimer. -- The document date (August 5, 2008) is 5735 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: '-low' is mentioned on line 416, but not defined == Outdated reference: A later version (-26) exists of draft-ietf-manet-dymo-14 == Outdated reference: A later version (-15) exists of draft-ietf-manet-nhdp-07 == Outdated reference: A later version (-19) exists of draft-ietf-manet-olsrv2-07 == Outdated reference: A later version (-06) exists of draft-ietf-roll-indus-routing-reqs-01 -- Obsolete informational reference (is this intentional?): RFC 2740 (Obsoleted by RFC 5340) Summary: 2 errors (**), 0 flaws (~~), 14 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Networking Working Group P. Levis 3 Internet-Draft Stanford University 4 Intended status: Informational A. Tavakoli 5 Expires: February 6, 2009 S. Dawson-Haggerty 6 UC Berkeley 7 August 5, 2008 9 Overview of Existing Routing Protocols for Low Power and Lossy Networks 10 draft-ietf-roll-protocols-survey-00 12 Status of this Memo 14 By submitting this Internet-Draft, each author represents that any 15 applicable patent or other IPR claims of which he or she is aware 16 have been or will be disclosed, and any of which he or she becomes 17 aware will be disclosed, in accordance with Section 6 of BCP 79. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as Internet- 22 Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt. 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 This Internet-Draft will expire on February 6, 2009. 37 Abstract 39 Networks of low power wireless devices introduce novel IP routing 40 issues. Low-power wireless devices, such as sensors, actuators and 41 smart objects, have difficult constraints: very limited memory, 42 little processing power, and long sleep periods. As most of these 43 devices are battery-powered, energy efficiency is critically 44 important. Wireless link qualities can vary significantly over time, 45 requiring protocols to make agile decisions yet minimize topology 46 change energy costs. Routing over such low power and lossy networks 47 has requirements that existing mesh protocols only partially address. 48 This document provides a brief survey of the strengths and weaknesses 49 of existing protocols with respect to this class of networks. It 50 provides guidance on how lessons from existing and prior efforts can 51 be leveraged in future protocol design. 53 Requirements Language 55 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 56 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 57 document are to be interpreted as described in RFC 2119 [RFC2119]. 59 Table of Contents 61 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 62 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 63 3. Suitability Summary . . . . . . . . . . . . . . . . . . . . . 4 64 3.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 5 65 3.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 5 66 3.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 6 67 3.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 6 68 3.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 7 69 4. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 7 70 5. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 9 71 5.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 72 5.2. OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 73 5.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 11 74 6. Distance Vector protocols . . . . . . . . . . . . . . . . . . 11 75 6.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 76 6.2. DSDV . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 77 6.3. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 12 78 6.4. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 79 6.5. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 80 7. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 13 81 7.1. IPv6 Neighbor Discovery . . . . . . . . . . . . . . . . . 13 82 7.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 13 83 8. Security Issues . . . . . . . . . . . . . . . . . . . . . . . 13 84 9. Manageability Issues . . . . . . . . . . . . . . . . . . . . . 14 85 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 86 11. Security Considerations . . . . . . . . . . . . . . . . . . . 14 87 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 14 88 13. Annex A - Routing protocol scalability analysis . . . . . . . 14 89 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18 90 14.1. Normative References . . . . . . . . . . . . . . . . . . . 18 91 14.2. Informative References . . . . . . . . . . . . . . . . . . 18 92 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19 93 Intellectual Property and Copyright Statements . . . . . . . . . . 21 95 1. Terminology 97 AODV: Ad-hoc On Demand Vector Routing 99 DSDV: Destination Sequenced Distance Vector 101 DSR: Dynamic Source Routing 103 DYMO: Dynamic Mobile On-Demand 105 MANET: Mobile Ad-hoc Networks 107 MAC: Medium Access Control 109 MPLS: Multiprotocol Label Switching 111 MPR: Multipoint Relays 113 MTU: Maximum Transmission Unit 115 LSA: Link State Advertisement 117 LSDB: Link State Database 119 OLSR: Optimized Link State Routing 121 ROLL: Routing in Low power and Lossy Networks 123 TDMA: Time Division Multiple Access 125 2. Introduction 127 Wireless is increasingly important to computer networking. As 128 Moore's Law has reduced computer prices and form factors, networking 129 includes not only servers and desktops, but laptops, palmtops, and 130 cellphones. As computing device costs and sizes have shrunk, small 131 wireless sensors, actuators, and smart objects have emerged as an 132 important next step in inter-networking. The sheer number of the 133 low-power networked devices means that they cannot depend on human 134 intervention (e.g., adjusting position) for good networking: they 135 must have routing protocols that enable them to self-organize into 136 multihop networks. 138 Energy is a fundamental challenge in these devices. Convenience and 139 ease of use requires they be wireless and therefore battery powered. 140 Correspondingly, low power operation is a key concern for this class 141 of networked device. Cost points and energy limitations cause these 142 devices to have very limited resources: a few kB of RAM and a few MHz 143 of CPU is typical. As energy efficiency does not improve with 144 Moore's Law, these limitations are not temporary. This trend towards 145 smaller, lower power, and more numerous devices has led to new low- 146 power wireless link layers to support them. In practice, wireless 147 networks observe much higher loss rates than wired ones do, and low- 148 power wireless is no exception. Furthermore, many of these networks 149 will include powered as well as energy constrained nodes. 150 Nevertheless, for cost and scaling reasons, many of these powered 151 devices will still have limited resources. 153 These low power and lossy networks introduce constraints and 154 requirements that other networks typically do not possess 155 ([I-D.brandt-roll-home-routing-reqs] and 156 [I-D.ietf-roll-indus-routing-reqs]). This document examines existing 157 routing protocols and how well they can be applied to low power and 158 lossy networks. It provides a basic framework with which to compare 159 the costs and benefits of different protocol designs and examines 160 existing protocols within this framework. From these observations it 161 provides guidance on how existing solutions can be leveraged in 162 future protocol design. 164 3. Suitability Summary 166 In this section, we present five important requirements for routing 167 in low power and lossy networks, and evaluate protocols against them. 168 Our evaluation attempts to take a complicated and interrelated set of 169 design decisions and trade-offs and condense them to a simple "pass", 170 "fail", or "?". As with any simplification, there is a risk of 171 removing some necessary nuance. However, we believe that being 172 forced to take a position on whether or not these protocols are 173 acceptable according to binary criterion will be constructive. 175 We derive these metrics from existing documents that describe ROLL 176 network application requirements. These metrics do not encompass all 177 application requirements. Instead, they are a common set of routing 178 protocol requirements that most applications domains share. 179 Considering this very general and common set of requirements sets a 180 minimal bar for a protocol to be generally applicable. If a protocol 181 cannot meet even these minimalist criteria, then it cannot be used in 182 several major ROLL application domains and so is unlikely to be a 183 good candidate for further analysis and examination. Satisfying 184 these minimal criteria is necessary but not sufficient: they do not 185 represent the complete intersection of application requirements and 186 applications introduce additional, more stringent requirements. But 187 this simplified view provides a first cut of the applicability of 188 existing protocols, and those that do satisfy them might be 189 reasonable candidates for further study. 191 The five metrics are "table scalability", "loss response", "control 192 cost", "link cost", and "node cost". For each of these, the value 193 "pass" indicates that a given protocol has satisfactory performance 194 according to the metric. The value "fail" indicates that the 195 protocol does not have acceptable performance according to the 196 metric, and that the RFC defining the protocol does not appear to 197 contain sufficient flexibility to alter the protocol to do so. 198 Finally, "?" indicates that an implementation could exhibit 199 satisfactory performance while following the RFC, but that design 200 considerations necessary to do so are not specified. 202 3.1. Formal Definitions 204 To provide precise definitions of these metrics, we use formal big-O 205 notation, where N refers to the number of nodes in the network, D 206 refers to the number of unique destinations, and L refers to the size 207 of a node's single-hop local neighborhood (the network density). We 208 explain the derivation of each metric from application requirements 209 in its corresponding section. 211 3.2. Table Scalability 213 Scalability support for large networks of sensors is highlighted as a 214 key requirement by the application requirements documents mentioned 215 above, with size ranging from a minimum of 250 nodes 216 ([I-D.brandt-roll-home-routing-reqs]) to very large networks 217 ([I-D.dohler-roll-urban-routing-reqs]), and network depths of up to 218 20 hops ([I-D.ietf-roll-indus-routing-reqs]). Given that network 219 information maintained at each node is stored in routing and neighbor 220 tables, along with the constrained memory of nodes, necessitates 221 bounds on the size of these tables. 223 This metric examines whether routing tables scale within reasonable 224 memory resources of low-power nodes. According to this metric, 225 routing protocols that scale linearly with the size of the network or 226 a node's neighborhood fail. Scaling with the size of the network 227 prevents networks from growing to reasonable size, while scaling with 228 the network density precludes dense deployments. However, as many 229 low-power and lossy networks behave principally as data collection 230 networks and principally communicate through routers to data 231 collection points in the larger Internet, scaling with the number of 232 such collection points is reasonable. Protocols whose state scales 233 with the number of destinations pass. 235 More precisely, routing table size scaling with O(N) or O(L) fails. 236 A table that scales O(D) (assuming no N or L) passes. 238 3.3. Loss Response 240 In low power and lossy networks, links routinely come and go due to 241 being close to the SINR threshold. It is important that link churn 242 not trigger unnecessary responses by the routing protocol. This 243 point is stressed in all the application requirement documents, 244 pointing to the need to localize response to link failures with no 245 triggering of global network re-optimization, whether for reducing 246 traffic or for maintaining low route convergence times 247 ([I-D.brandt-roll-home-routing-reqs], 248 [I-D.dohler-roll-urban-routing-reqs], and 249 [I-D.ietf-roll-indus-routing-reqs]). 251 A protocol which requires many link changes to propagate across the 252 entire network fails. Protocols which constrain the scope of 253 information propagation to only when they affect routes to active 254 destinations, or to local neighborhoods, pass. 256 More precisely, loss responses that require O(N) transmissions fail, 257 while responses that can rely on O(1) local broadcasts or O(D) route 258 updates pass. 260 3.4. Control Cost 262 Battery-operated devices are a critical component of all three 263 application spectrums, and as such special emphasis is placed on 264 minimizing power consumption to achieve long battery lifetime, 265 ([I-D.brandt-roll-home-routing-reqs]), with multi-year deployments 266 being a common case ([I-D.ietf-roll-indus-routing-reqs]). In terms 267 of routing structure, any proposed L2N routing protocol ought to 268 support the autonomous organization and configuration of the network 269 at the lowest possible energy cost 270 ([I-D.dohler-roll-urban-routing-reqs]). 272 All routing protocols must transmit additional data to detect 273 neighbors, build routes, transmit routing tables, or otherwise 274 conduct routing. As low-power wireless networks can have very low 275 data rates, protocols which require a minimum control packet rate can 276 have unbounded control overhead. This is particularly true for 277 event-driven networks, which only report data when certain conditions 278 are met. Regions of a network which never meet the condition can be 279 forced to send control traffic even when there is no data to send. 280 For these use cases, hard-coded timing constants are unacceptable, 281 because they imply a prior knowledge of the expected data rate. 283 If control traffic is uncorrelated with data traffic, a protocol 284 fails according to Control Cost metric. Protocols which pass bound 285 their control traffic rate to their data traffic. Protocols which 286 pass do not use resources to maintain unused state. More 287 specifically, any protocol which requires fixed-rate periodic control 288 packets in the absence of data traffic fails. 290 3.5. Link and Node Cost 292 These two metrics specify how a protocol chooses routes for data 293 packets to take through the network. Classical routing algorithms 294 typically acknowledge the differing costs of paths and may use a 295 shortest path algorithm to find paths. This is a requirement for low 296 power networks, as links must be evaluated as part of an objective 297 function across various metric types, such as minimizing latency and 298 maximizing reliability ([I-D.ietf-roll-indus-routing-reqs]). 300 However, in low power networks it is also desirable to account for 301 the cost of routing through particular routers. Applications require 302 node or parameter constrained routing, which takes into account node 303 properties abd attributes such as power, memory, and battery life 304 that dictate a router's willingness or ability to route other 305 packets([I-D.brandt-roll-home-routing-reqs], 306 [I-D.dohler-roll-urban-routing-reqs]). Node cost refers to the 307 ability for a protocol to incorporate router properties into routing 308 metrics and use node attributes for constraint-based routing. 310 A "pass" indicates that the protocol contains a mechanism allowing 311 these considerations to be considered when choosing routes. 313 4. Routing Protocol Taxonomy 315 Routing protocols broadly fall into two classes: link-state and 316 distance-vector. 318 A router running a link-state protocol first establishes adjacency 319 with its neighbors and then reliably floods the local topology 320 information in the form of a Link State Advertisement packet. The 321 collection of LSAs constitutes the Link State Database (LSDB) that 322 represents the network topology, and routers synchronize their LSDBs. 323 Thus each node in the network has a complete view of the network 324 topology. Each router uses the LSDB to compute a routing table where 325 each entry (reachable IP destination address) points to the next hop 326 along the shortest path according to some metric. Link state 327 protocols (such as OSPF and IS-IS) support the concept of area 328 (called "level" for IS-IS) whereby all the routers in the same area 329 share the same view (they have the same LSDB) and areas are 330 interconnected by border routers according to specific rules that 331 advertise IP prefix reachability between areas. 333 A distance vector protocol exchanges routing information rather than 334 topological information. A router running a distance vector protocol 335 exchanges information with its "neighbors" with which it has link 336 layer connectivity. Tunneling and similar mechanisms can virtualize 337 link layer connectivity to allow neighbors that are multiple layer 2 338 hops away. Rather than a map of the network topology from which each 339 router can calculate routes, a distance vector protocol node has 340 information on what routes its neighbors have. Each node's set of 341 available routes is the union of its neighbors routes plus a route to 342 itself. In a distance vector protocol, nodes may only advertise 343 routes which are in use, enabling on-demand discovery. In comparison 344 to link state protocols, distance vector protocols have the advantage 345 of only requiring neighbor routing information, but also have 346 corresponding limitations which protocols must address, such as 347 routing loops, count to infinity, split horizon, and slow convergence 348 times. Furthermore, routing constraints are difficult to enforce 349 with distance vector protocols. 351 Neighbor discovery is a critical component of any routing protocol. 352 It enables a protocol to learn about which other nodes are nearby and 353 which it can use as the next hop for routes. As neighbor discovery 354 is a key component of many protocols, several general protocols and 355 protocol mechanisms have been designed to support it. A protocol's 356 neighbor set is defined by how many "hops" away the set reaches. For 357 example, the 1-hop neighbor set of a node is all nodes it can 358 directly communicate with at the link layer, while the 2-hop neighbor 359 set is its own 1-hop neighbor set and the 1-hop neighbor sets of all 360 of its 1-hop neighbors. 362 Because nodes often have very limited resources for storing routing 363 state, protocols cannot assume that they can store complete neighbor 364 information. For example, a node with 4kB of RAM cannot store full 365 neighbor state when it has 1000 other nodes nearby. This means that 366 ROLL protocols must have mechanisms to decide which of many possible 367 neighbors they monitor as routable next hops. For elements such as 368 2-hop neighborhoods, these decisions can have a significant impact on 369 the topology that other nodes observe, and therefore may require 370 intelligent logic to prevent effects such as network partitions. 372 Protocols Today 374 Wired networks draw from both approaches. OSPF or IS-IS, for 375 example, are link-state protocols, while RIP is a distance-vector 376 protocol. 378 MANETs similarly draw from both approaches. OLSR is a link-state 379 protocol, while AODV, DSDV, and DYMO are distance vector protocols. 380 The general consensus in core networks is to use link state routing 381 protocols as IGPs for a number of reasons: in many cases having a 382 complete network topology view is required to adequately compute the 383 shortest path according to some metrics. For some applications such 384 as MPLS Traffic Engineering it is even required to have the knowledge 385 of the Traffic Engineering Database for constraint based routing. 387 Furthermore link state protocols typically have superior convergence 388 speeds (ability to find an alternate path in case of network element 389 failure), are easier to debug and troubleshoot, and introduce less 390 control packet overhead than distance vector protocols. In contrast, 391 distance vector protocols are simpler, require less computation, and 392 have smaller storage requirements. Most of these tradeoffs are 393 similar in wireless networks, with one exception. Because wireless 394 links can suffer from significant temporal variation, link state 395 protocols can have higher traffic loads as topology changes must 396 propagate globally, while in a distance vector protocol a node can 397 make local routing decisions with no effect on the global routing 398 topology. One major protocol, DSR, does not easily fit into one of 399 these two classes. Although it is a distance vector protocol, DSR 400 has several properties that make it differ from most other protocols 401 in this class. We examine these differences in our discussion of 402 DSR. 404 The next two sections summarize several well established routing 405 protocols. Later sections consider the properties of these protocol 406 with respect to ROLL requirements. This table shows, based on the 407 criteria described above, whether these protocols meet ROLL criteria. 409 Protocol Table Loss Control Link Cost Node Cost 410 OSPF fail fail fail pass fail 411 OLSRv2 fail fail fail pass pass 412 TBRPF fail pass fail pass ? 413 RIP pass fail fail ? fail 414 AODV pass fail pass fail fail 415 DSDV pass fail fail ? fail 416 DYMO[-low] pass fail pass ? ? 417 DSR fail ? pass fail ? 419 5. Link State Protocols 421 5.1. OSPF 423 OSPF (specified in [RFC2328] for IPv4 and in [RFC2740] for IPv6)) is 424 a link state protocol designed for routing within an Internet 425 Autonomous System (AS). OSPF provides the ability to divide a 426 network into areas, which can establish a routing hierarchy. The 427 topology within an area is hidden from other areas and IP prefix 428 reachability across areas (inter-area routing) is provided using 429 summary LSAs. The hierarchy implies that there is a top-level 430 routing area (the backbone area) which connects other areas. Areas 431 may be connected to the back-bone area through a virtual link. OSPF 432 maintains routing adjacencies by sending hello messages. OSPF 433 calculates the shortest path to a node using link metrics (that may 434 reflect the link bandwidth, propagation delay, ...). OSPF Traffic 435 Engineering (OSPF-TE, [RFC3630]) extends OSPF to include information 436 on reservable, unreserved, and available bandwidth. 438 5.2. OLSR 440 Optimized Link State Routing (OLSR) (see [RFC3626] and 441 [I-D.ietf-manet-olsrv2]) is a link state routing protocol for 442 wireless mesh networks. OLSR nodes flood route discovery packets 443 throughout the entire network, such that each node has a map of the 444 mesh topology. Because link variations can lead to heavy flooding 445 traffic when using a link state approach, OLSR establishes a topology 446 for minimizing this communication. Each node maintains a set of 447 nodes called its Multipoint Relays (MPR), which is a subset of the 448 one-hop neighbors whose connectivity covers the two-hop neighborhood. 449 Each node that is an MPR maintains a set called its MPR selectors, 450 which are nodes that have chosen it to be an MPR. 452 OLSR uses these two sets to apply three optimizations. First, only 453 MPRs generate link state information. Second, nodes can use MPRs to 454 limit the set of nodes that forward link state packets. Third, an 455 MPR, rather than advertise all of its links, can advertise only links 456 to its MPR selectors. Together, these three optimizations can 457 greatly reduce the control traffic in dense networks, as the number 458 of MPRs should not increase significantly as a network becomes 459 denser. 461 OLSR selects routes based on hop counts, and assumes an underlying 462 protocol that determines whether a link exists between two nodes. 463 OLSR's constrained flooding allows it to quickly adapt to and 464 propagate topology changes. 466 OLSR is closely related to clustering algorithms in the wireless 467 sensor networking literature, in which cluster heads are elected such 468 that routing occurs over links between cluster heads and all other 469 nodes are leafs that communicate to a cluster head. 471 5.3. TBRPF 473 Topology Dissemination Based on Reverse Path Forwarding (see 474 [RFC3684]) is another proactive link state protocol. TBRPF computes 475 a source tree, which provides routes to all reachable nodes. It 476 reduces control packet overhead by having nodes only transmit a 477 subset of their source tree as well as by using differential updates. 479 The major difference between TBRPF and OLSR is the routing data that 480 nodes advertise and who chooses to aggregate information. In OLSR, 481 nodes select neighbors to be MPRs and advertise their link state for 482 them; in TBRPF, nodes elect themselves to advertise relevant link 483 state based on whether it acts as a next hop. 485 6. Distance Vector protocols 487 6.1. RIP 489 The Routing Information Protocol (RIP) (defined in [RFC2453]) 490 predates OSPF. As it is a distance vector protocol, routing loops 491 can occur and considerable work has been done to accelerate 492 convergence since the initial RIP protocols were introduced. RIP 493 measures route cost in terms of hops, and detects routing loops by 494 observing a route cost approach infinity where "infinity" is referred 495 to as a maximum number of hops. RIP is typically not appropriate for 496 situations where routes need to be chosen based on real-time 497 parameters such as measured delay, reliability, or load or when the 498 network topology needs to be known for route computation. 500 "Triggered RIP" (defined in [RFC2091]) was originally designed to 501 support "on-demand" circuits. The aim of triggered RIP is to avoid 502 systematically sending the routing database on regular intervals. 503 Instead, triggered RIP sends the database when there is a routing 504 update or a next hop adjacency change: once neighbors have exchanged 505 their routing database, only incremental updates need to be sent. 506 Because incremental updates cannot depend on periodic traffic to 507 overcome loses, triggered RIP uses acknowledgment based mechanisms 508 for reliable delivery. 510 6.2. DSDV 512 Destination Sequenced Distance Vector Routing uses distance vectors 513 to continuously maintain routes throughout a network. Unlike RIP, 514 DSDV uses per-node sequence numbers to provide a total ordering on 515 route information age in order to prevent loops. In DSDV, each node 516 maintains a route to each other node. 518 6.3. Ad-hoc On Demand Vector Routing (AODV) 520 AODV (specified in [RFC3561]) is a distance vector protocol intended 521 for mobile ad-hoc networks. When one AODV node requires a route to 522 another, it floods a request in the network to discover a route. A 523 depth-scoped flooding process avoids discovery from expanding to the 524 most distant regions of the network that are in the opposite 525 direction of the destination. AODV chooses routes that have the 526 minimum hop count. 528 If an AODV route request reaches a node that has a route to the 529 destination (this includes the destination itself), that node sends a 530 reply along the reverse route. All nodes along the reverse route can 531 cache the route. When routes break due to topology changes, AODV 532 floods error messages and issues a new request. Because AODV is on- 533 demand, it does not maintain routes to all nodes as DSDV does; 534 instead, it only maintains routes for active nodes. When a link 535 breaks, AODV issues a Route Error (RERR) and a new route request 536 message (RREQ), with a higher sequence number so nodes do not respond 537 from their route caches. These packets can flood the entire network, 538 giving loss response a fail. 540 6.4. DYMO 542 Dynamic Mobile On-Demand routing (DYMO) (([I-D.ietf-manet-dymo]) is 543 an evolution of AODV. The basic functionality is the same, but it 544 has different packet formats, handling rules, and supports path 545 accumulation. Path accumulation allows a single DYMO route request 546 to generate routes to all nodes along the route to that destination. 547 Like AODV, DYMO uses hop counts as its routing metric, but links may 548 have a cost >= 1, allowing DYMO to represent link costs. Like AODV, 549 on link breaks DYMO issues a new route request message (RREQ), with a 550 higher sequence number so nodes do not respond from their route 551 caches. Correspondingly, a route request can flood the entire 552 network. 554 6.5. DSR 556 Dynamic Source Routing ([RFC4728]) is a distance vector protocol, but 557 a DSR packet source explicitly specifies the route for each packet. 558 Because the route is determined at a single place -- the source -- 559 DSR does not require sequence numbers or other mechanisms to prevent 560 routing loops, as there is no problem of inconsistent routing tables. 561 Unlike DSDV, AODV, and DYMO, by pushing state into packet headers, 562 DSR does not require per-destination routing state. Instead, a node 563 originating packets only needs to store a spanning tree of the part 564 of the network it is communicating with. 566 7. Neighbor Discovery 568 A limit on maintained routing state (light footprint) prevents ROLL 569 protocols from assuming they know all 1-hop, 2-hop, or N-hop 570 neighbors. For this reason, while protocols such as MANET-NHDP 571 ([I-D.ietf-manet-nhdp]) and IPv6's neighbor discovery ([RFC4861]) 572 provide basic mechanisms for discovering link-layer neighbors, not 573 all of their features are relevant. This section describes these two 574 protocols, their capabilities, and how ROLL protocols could leverage 575 them. 577 7.1. IPv6 Neighbor Discovery 579 IPv6 neighbor discovery provides mechanisms for nodes to discover 580 single-hop neighbors as well as routers that can forward packets past 581 the local neighborhood. There is an implicit assumption that the 582 delegation of whether a node is a router or not is static (e.g., 583 based on a wired topology). The fact that all routers must respond 584 to a Router Solicitation requires that the number of routers with a 585 1-hop neighborhood is small, or there will be a reply implosion. 586 Furthermore, IPv6 neighbor discovery's support of address 587 autoconfiguration assumes address provisioning, in that addresses 588 reflect the underlying communication topology. IPv6 neighbor 589 discovery does not consider asymmetric links. Nevertheless, it may 590 be possible to extend and adapt IPv6's mechanisms to wireless in 591 order to avoid response storms and implosions. 593 7.2. MANET-NHDP 595 The MANET Neighborhood Discovery Protocol (MANET-NHDP) provides 596 mechanisms for discovering a node's symmetric 2-hop neighborhood. It 597 maintains information on discovered links, their interfaces, status, 598 and neighbor sets. MANET-NHDP advertises a node's local link state; 599 by listening to all of its 1-hop neighbor's advertisements, a node 600 can compute its 2-hop neighborhood. MANET-NHDP link state 601 advertisements can include a link quality metric. MANET-NHDP's node 602 information base includes all interface addresses of each 1-hop 603 neighbor: for low-power nodes, this state requirement can be 604 difficult to support. 606 8. Security Issues 608 TBD 610 9. Manageability Issues 612 TBD 614 10. IANA Considerations 616 This document includes no request to IANA. 618 11. Security Considerations 620 TBD 622 12. Acknowledgements 624 13. Annex A - Routing protocol scalability analysis 626 This aim of this Annex is to provide the details for the analysis 627 routing scalability analysis. 629 "OSPF" 631 OSPF floods link state through a network. Each router must receive 632 this complete link set. OSPF fails the table size criterion because 633 it requires each router to discover each link in the network, for a 634 total routing table size which is O(N * L). This also causes it to 635 fail the control cost criterion, since this information must be 636 propagated. Furthermore, changes in the link set require re-flooding 637 the network link state even if the changed links were not being used. 638 Since link state changes in wireless networks are often uncorrelated 639 with data traffic and are instead caused by external (environmental) 640 factors, this causes OSPF to fail both the control cost and loss 641 response criteria. OSPF routers can impose policies on the use of 642 links and can consider link properties (Type of Service), so receive 643 a pass for link cost. However, there is no way to associate metrics 644 with routers when computing paths, and so fails the node cost 645 criteria. 647 "OLSRv2" 649 OLSRv2 is a proactive link state protocol, flooding this information 650 through a set of multipoint relays (MPRs). Routing state includes 651 1-hop neighbor information for each node in the network, 1-hop and 652 2-hop information for neighbors, and a routing table, resulting in 653 state proportional to network size and density (O(N*L + L^2)), and 654 failing the table scalability criteria. 656 Unacceptable control traffic overhead arises from flooding and 657 maintenance. HELLO messages are periodically broadcast local beacon 658 messages, but TC messages spread topology information throughout the 659 network (using MPRs). As such, control traffic is proportional to 660 O(N^2). As L is bounded by N, this means control traffic is 661 proportional to O(N). MPRs reduce this load to O(N^2 / L). As the 662 number of MPRs is inversely proportional to the density of the 663 network and L is bounded by N, this means control traffic is at best 664 proportional to O(N), and fails the control cost metric. 666 Furthermore, changes in the link set require re-flooding the network 667 link state even if those links were not being used by routing, which 668 fails the loss response metric. 670 OLSR allows for specification of link quality, and also provides a 671 'Willingness' metric to symbolize node cost, giving it a pass for 672 both those metrics. 674 "TBRPF" 676 As a link state protocol, TBRPF routing table size scales with 677 network size, leading to table sizes which are O(N * L) when a node 678 receives disjoint link sets from its neighbors. However, this causes 679 the protocol to fail the table size criteria. The protocol's use of 680 differential updates should allow both fast response time and 681 incremental changes once the distributed database of links has been 682 established. Differential updates are only used to reduce response 683 time to changing network conditions, not to reduce the amount of 684 topology information sent, since each node will periodically send 685 their piece of the topology. As a result, TBRPF fails the control 686 overhead criteria. However, its differential updates are triggered 687 by a link failure do not immediately cause a global re-flooding of 688 state, leading to a pass for loss response. 690 TBRPF has a flexible neighbor management layer which enables it to 691 incorporate various link metrics into its routing decision. As a 692 result, it receives a pass for link cost. It also provides a 693 mechanism whereby routers are able to advertise their "willingness to 694 route." Although the RFC does not specify a policy for using these 695 values, developing one could allow TBRPF to satisfy this requirement, 696 leading to a ? for the node cost requirement. 698 "RIP" 700 RIP is a distance vector protocol, with all routers maintaining a 701 route to all other routers, and as such table size being O(N). 703 However, if destinations are known apriori, table size can be reduced 704 to O(D), resulting in a pass for table scalability. Each node 705 broadcasts a beacon per period, and updates must be propagated by 706 affected nodes, irrespective of data rate, failing the control cost 707 metric. Loss triggers updates, only propagating if part of a best 708 route, even if the route is not actively being used, resulting in a 709 fail for loss response. 711 RIP receives a ? for link cost, because while current implementations 712 focus on hop count, any number can theoretically be used to advertise 713 link quality. There is no concept of router quality, and so it 714 receives a fail for the node cost criteria. 716 "AODV" 718 AODV table size is a function of the number of communicating pairs in 719 the network, scaling with O(D). This is acceptable and so AODV 720 passes the table size criteria. As an on-demand protocol, AODV does 721 not generate any traffic until data is sent, and so control traffic 722 is correlated with the data and so it receives a pass for control 723 traffic. When a broken link is detected, AODV will use a precursor 724 list maintained for each destination to inform downstream routers 725 (with a RERR) of the topology change. This information is not sent 726 as a flood, leading to an acceptable of traffic for a loss. 727 Furthermore, the router encountering a broken link may initiate local 728 repair via a scoped flood. However, link churn may also result in 729 RERR messages being flooded to the entire network. Therefore, AODV 730 receives a fail for loss response. 732 AODV allows the source router to wait and collect a number of RREP 733 messages before choosing which route is to be used. This allows that 734 router to evaluate the link cost of the different alternatives, 735 although it is not clear how this should be done. AODV fails the 736 link cost requirement because it does not appear that that a design 737 goal was to choose paths which are minimal under some metric. It 738 fails the node cost requirement because there is no way for a router 739 to indicate its [lack of] willingness to route while still adhering 740 to the RFC. 742 "DSDV" 744 DSDV is another distance vector protocol, similar to RIP, with the 745 only main difference being in the usage of destination-based sequence 746 numbers to prevent routing loops. As such the following analysis 747 applies, which is the same as RIP's. 749 DSDV receives a pass for scalability because table size can be 750 limited to O(D) if all destinations are known apriori. Control cost 751 is a fail, because periodic beaconing, irrespective of data rate, is 752 required, with updates propagating throughout the network. Loss 753 response is also a fail since although loss only results in 754 propagation to routers that utilize that link in their routing 755 tables, there is no mechanism for restricting this propagation to 756 active routes, rather than all routes. Link cost is a ? since 757 theoretically distance metrics other than hops could be used, but are 758 not covered in the protocol description, and node cost is a fail as 759 there is no provision for router quality. 761 "DYMO/DYMO-low" 763 The design of DYMO shares much with AODV, with some changes to remove 764 precursor lists and compact various messages. Table size is somewhat 765 smaller, including entries for neighboring DYMO routers and routes 766 passing through the router. Control overhead has been reduced 767 somewhat, and DYMO does not generate spurious RERRs; these messages 768 are only generated when a forwarding failure occurs. Nevertheless, 769 these RERRs can flood the entire network, imposing an O(N) cost. 770 DYMO includes mechanisms to add additional routing information 771 (potentially including router willingness), but does not define 772 explicit policy mechanisms for choosing routers along a path. Its 773 extensible packet format could allow router properties to be 774 specified in headers, giving it a ? on node cost. Rather than rely 775 solely on hopcount, DYMO allows links to have costs in the range of 776 1-65535, but does not specify how these might be used, giving it a ? 777 on link cost. 779 "DSR" 781 DSR performs source routing of packets, discovering packets through a 782 route discovery mechanism. Only table entries needed by the data are 783 maintained, which is equivalent to the number of unique next hops 784 needed to access all desired destinations. Control traffic is only 785 initiated when a new route is being discovered, or when an existing 786 route fails, and as such is proportional to the data rate. Loss does 787 not trigger updates, unless the path is used. Routes are selected 788 based on hop count, with no mechanism for differentiating between 789 "routers". 791 DSR fails the table criterion because it maintains a blacklist of 792 neighbors with whom connectivity is not bidirectional: this scales 793 with O(L). DSR receives a ? on the loss criterion because some of 794 its mechanisms, such as automatic route shortening and route cache 795 suggest that it may be able to meet the loss criterion, but exactly 796 how these are implemented will affect its efficiency. DSR passes the 797 control criterion because all control traffic is on-demand, and so is 798 bound to data traffic rates. DSR fails the link cost criterion 799 because its source routes are advertised only in terms of hops, such 800 that all advertised links are considered equivalent. DSR has a ? on 801 the node cost criterion because sources decide on whom to send 802 packets through, and nodes cannot announce their capabilities in this 803 regard. However, a new route reply option could possibly achieve 804 this goal. 806 14. References 808 14.1. Normative References 810 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 811 Requirement Levels", BCP 14, RFC 2119, March 1997. 813 14.2. Informative References 815 [I-D.brandt-roll-home-routing-reqs] 816 Brandt, A., "Home Automation Routing Requirement in Low 817 Power and Lossy Networks", 818 draft-brandt-roll-home-routing-reqs-01 (work in progress), 819 May 2008. 821 [I-D.dohler-roll-urban-routing-reqs] 822 Dohler, M., Watteyne, T., Jacquenet, C., Madhusudan, G., 823 and G. Chegaray, "Urban WSNs Routing Requirements in Low 824 Power and Lossy Networks", 825 draft-dohler-roll-urban-routing-reqs-01 (work in 826 progress), April 2008. 828 [I-D.ietf-manet-dymo] 829 Chakeres, I. and C. Perkins, "Dynamic MANET On-demand 830 (DYMO) Routing", draft-ietf-manet-dymo-14 (work in 831 progress), June 2008. 833 [I-D.ietf-manet-nhdp] 834 Clausen, T., Dearlove, C., and J. Dean, "MANET 835 Neighborhood Discovery Protocol (NHDP)", 836 draft-ietf-manet-nhdp-07 (work in progress), July 2008. 838 [I-D.ietf-manet-olsrv2] 839 Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized 840 Link State Routing Protocol version 2", 841 draft-ietf-manet-olsrv2-07 (work in progress), July 2008. 843 [I-D.ietf-roll-indus-routing-reqs] 844 Networks, D., Thubert, P., Dwars, S., and T. Phinney, 845 "Industrial Routing Requirements in Low Power and Lossy 846 Networks", draft-ietf-roll-indus-routing-reqs-01 (work in 847 progress), July 2008. 849 [RFC2091] Meyer, G. and S. Sherry, "Triggered Extensions to RIP to 850 Support Demand Circuits", RFC 2091, January 1997. 852 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 854 [RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453, 855 November 1998. 857 [RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", 858 RFC 2740, December 1999. 860 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 861 Demand Distance Vector (AODV) Routing", RFC 3561, 862 July 2003. 864 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing 865 Protocol (OLSR)", RFC 3626, October 2003. 867 [RFC3630] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering 868 (TE) Extensions to OSPF Version 2", RFC 3630, 869 September 2003. 871 [RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology 872 Dissemination Based on Reverse-Path Forwarding (TBRPF)", 873 RFC 3684, February 2004. 875 [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source 876 Routing Protocol (DSR) for Mobile Ad Hoc Networks for 877 IPv4", RFC 4728, February 2007. 879 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 880 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 881 September 2007. 883 Authors' Addresses 885 Philip Levis 886 Stanford University 887 358 Gates Hall, Stanford University 888 Stanford, CA 94305-9030 889 USA 891 Email: pal@cs.stanford.edu 892 Arsalan Tavakoli 893 UC Berkeley 894 Soda Hall, UC Berkeley 895 Berkeley, CA 94707 896 USA 898 Email: arsalan@eecs.berkeley.edu 900 Stephen Dawson-Haggerty 901 UC Berkeley 902 Soda Hall, UC Berkeley 903 Berkeley, CA 94707 904 USA 906 Email: stevedh@cs.berkeley.edu 908 Full Copyright Statement 910 Copyright (C) The IETF Trust (2008). 912 This document is subject to the rights, licenses and restrictions 913 contained in BCP 78, and except as set forth therein, the authors 914 retain all their rights. 916 This document and the information contained herein are provided on an 917 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 918 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 919 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 920 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 921 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 922 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 924 Intellectual Property 926 The IETF takes no position regarding the validity or scope of any 927 Intellectual Property Rights or other rights that might be claimed to 928 pertain to the implementation or use of the technology described in 929 this document or the extent to which any license under such rights 930 might or might not be available; nor does it represent that it has 931 made any independent effort to identify any such rights. Information 932 on the procedures with respect to rights in RFC documents can be 933 found in BCP 78 and BCP 79. 935 Copies of IPR disclosures made to the IETF Secretariat and any 936 assurances of licenses to be made available, or the result of an 937 attempt made to obtain a general license or permission for the use of 938 such proprietary rights by implementers or users of this 939 specification can be obtained from the IETF on-line IPR repository at 940 http://www.ietf.org/ipr. 942 The IETF invites any interested party to bring to its attention any 943 copyrights, patents or patent applications, or other proprietary 944 rights that may cover technology that may be required to implement 945 this standard. Please address the information to the IETF at 946 ietf-ipr@ietf.org.