idnits 2.17.1 draft-ietf-roll-protocols-survey-01.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 979. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 990. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 997. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1003. 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 495 has weird spacing: '... fail fai...' == Line 496 has weird spacing: '... fail fai...' == Line 497 has weird spacing: '... fail pas...' == Line 498 has weird spacing: '... pass fai...' == Line 499 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 (September 25, 2008) is 5693 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: '-low' is mentioned on line 500, 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 (-11) exists of draft-ietf-roll-home-routing-reqs-03 == Outdated reference: A later version (-06) exists of draft-ietf-roll-indus-routing-reqs-01 == Outdated reference: A later version (-05) exists of draft-ietf-roll-urban-routing-reqs-01 -- Obsolete informational reference (is this intentional?): RFC 2740 (Obsoleted by RFC 5340) Summary: 2 errors (**), 0 flaws (~~), 16 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: March 29, 2009 S. Dawson-Haggerty 6 UC Berkeley 7 September 25, 2008 9 Overview of Existing Routing Protocols for Low Power and Lossy Networks 10 draft-ietf-roll-protocols-survey-01 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 March 29, 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 novel requirements that existing protocols may not address. This 48 document provides a brief survey of the strengths and weaknesses of 49 existing protocols with respect to this class of networks. From this 50 survey it examines whether existing protocols as described in RFCs 51 and mature drafts could be used without modification in these 52 networks, or whether further work is necessary. 54 Requirements Language 56 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 57 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 58 document are to be interpreted as described in RFC 2119 [RFC2119]. 60 Table of Contents 62 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 63 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 64 3. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 4 65 4. Suitability Summary . . . . . . . . . . . . . . . . . . . . . 5 66 4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 6 67 4.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 6 68 4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 7 69 4.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 8 70 4.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 8 71 5. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 9 72 6. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 11 73 6.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 74 6.2. OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 75 6.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 12 76 7. Distance Vector protocols . . . . . . . . . . . . . . . . . . 13 77 7.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 78 7.2. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 13 79 7.3. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 80 7.4. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 81 8. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 14 82 8.1. IPv6 Neighbor Discovery . . . . . . . . . . . . . . . . . 14 83 8.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 15 84 9. Security Issues . . . . . . . . . . . . . . . . . . . . . . . 15 85 10. Manageability Issues . . . . . . . . . . . . . . . . . . . . . 15 86 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 87 12. Security Considerations . . . . . . . . . . . . . . . . . . . 15 88 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 15 89 14. Annex A - Routing protocol scalability analysis . . . . . . . 15 90 15. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 91 15.1. Normative References . . . . . . . . . . . . . . . . . . . 19 92 15.2. Informative References . . . . . . . . . . . . . . . . . . 19 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20 94 Intellectual Property and Copyright Statements . . . . . . . . . . 22 96 1. Terminology 98 AODV: Ad-hoc On Demand Vector Routing 100 DSR: Dynamic Source Routing 102 DYMO: Dynamic Mobile On-Demand 104 LLN: Low power and Lossy Network 106 LSA: Link State Advertisement 108 LSDB: Link State Database 110 MANET: Mobile Ad-hoc Networks 112 MAC: Medium Access Control 114 MPLS: Multiprotocol Label Switching 116 MPR: Multipoint Relays 118 MTU: Maximum Transmission Unit 120 OLSR: Optimized Link State Routing 122 ROLL: Routing in Low power and Lossy Networks 124 TDMA: Time Division Multiple Access 126 2. Introduction 128 Wireless is increasingly important to computer networking. As 129 Moore's Law has reduced computer prices and form factors, networking 130 includes not only servers and desktops, but laptops, palmtops, and 131 cellphones. As computing device costs and sizes have shrunk, small 132 wireless sensors, actuators, and smart objects have emerged as an 133 important next step in inter-networking. The sheer number of the 134 low-power networked devices means that they cannot depend on human 135 intervention (e.g., adjusting position) for good networking: they 136 must have routing protocols that enable them to self-organize into 137 multihop networks. 139 Energy is a fundamental challenge in these devices. Convenience and 140 ease of use requires they be wireless and therefore battery powered. 141 Correspondingly, low power operation is a key concern for this class 142 of networked device. Cost points and energy limitations cause these 143 devices to have very limited resources: a few kB of RAM and a few MHz 144 of CPU is typical. As energy efficiency does not improve with 145 Moore's Law, these limitations are not temporary. This trend towards 146 smaller, lower power, and more numerous devices has led to new low- 147 power wireless link layers to support them. In practice, wireless 148 networks observe much higher loss rates than wired ones do, and low- 149 power wireless is no exception. Furthermore, many of these networks 150 will include powered as well as energy constrained nodes. 151 Nevertheless, for cost and scaling reasons, many of these powered 152 devices will still have limited resources. 154 These low power and lossy networks introduce constraints and 155 requirements that other networks typically do not possess 156 ([I-D.ietf-roll-home-routing-reqs] and 157 [I-D.ietf-roll-indus-routing-reqs]). As they were not designed with 158 these requirements in mind, existing protocols may or may not work 159 well in LLNs. The first step to reaching consensus on a routing 160 protocol for LLNs is to decide which of these two is true. If an 161 existing protocol can meet LLN requirements without any changes, then 162 barring extenuating circumstances, it behooves us to use an existing 163 standard. However, if no current protocol can meet LLN's 164 requirements, then further work will be needed to define and 165 standardize with a protocol that can. Whether or not such a protocol 166 involves modifications to an existing protocol or a new protocol 167 entirely is outside the scope of this document: this document simply 168 seeks to answer the question: do LLNs require a new protocol 169 specification document at all? 171 3. Methodology 173 To answer the question of LLNs require new protocol specification 174 work, this document examines existing routing protocols and how well 175 they can be applied to low power and lossy networks. It provides a 176 set of criteria with which to compare the costs and benefits of 177 different protocol designs and examines existing protocols in terms 178 of these criteria. 180 The five criteria this document uses are derived from a set of drafts 181 that describe the requirements of a few major LLN application 182 scenarios. The five criteria, presented in Section 3, are neither 183 exhaustive nor complete. Instead, they are one specific subset of 184 high-level requirements shared across all of the application 185 requirement drafts. Because every application requirement draft 186 specifies these criteria, then a protocol which does not meet one of 187 them cannot be used without modifications or extensions. However, 188 because these criteria represent a subset of the intersection of the 189 application requirements, any given application domain may impose 190 additional requirements which a particular protocol may not meet. 191 For this reason, these criteria are "necessary but not sufficient." 192 A protocol that does not meet the criteria cannot be used as 193 specified, but it is possible that a protocol meets the criteria yet 194 is not able to meet the requirements of a particular application 195 domain. Nevertheless, a protocol that meets all of the criteria 196 would be very promising, and deserve a closer look and consideration 197 in light of LLN application domains. 199 This document considers "existing routing protocols" to be protocols 200 that are specified in RFCs or, in the cases of DYMO 201 [I-D.ietf-manet-dymo] or OLSRv2 [I-D.ietf-manet-olsrv2] , a very 202 mature draft which will most likely become an RFC. This document 203 does not seek to answer the question of whether there is any protocol 204 anywhere which could meet LLN application requirements. Rather, it 205 seeks to answer whether protocols, as specified in current IETF 206 standards documents, can meet such requirements. If an existing 207 protocol specification can be used unchanged, then writing additional 208 protocol specifications is unnecessary. For example, there are many 209 academic papers and experimental protocol implementations available; 210 while one or more of these may meet LLN requirements, if they are not 211 specified in an RFC then a working group will need to write a new RFC 212 for them to be a standard. The question this document seeks to 213 answer is not whether proposed, evaluated, theoretical or 214 hypothetical protocol designs can satisfy LLN requirements: the 215 question is whether existing IETF standards can. 217 Whether a protocol meets these criteria was judged by thinking 218 through each specification and considering the best implementation 219 possible. The judgement is based on what a specification allows, 220 rather than any particular implementation of that specification. For 221 example, while many DYMO implementations use hopcount as a routing 222 metric, the DYMO specification allows a hop to add more than one to 223 the routing metric, so DYMO as a specification can support some links 224 or nodes being more costly than others. 226 4. Suitability Summary 228 In this section, we present five important requirements for routing 229 in low power and lossy networks, and evaluate protocols against them. 230 This evaluation attempts to take a complicated and interrelated set 231 of design decisions and trade-offs and condense them to a simple 232 "pass", "fail", or "?". As with any simplification, there is a risk 233 of removing some necessary nuance. However, we believe that being 234 forced to take a position on whether or not these protocols are 235 acceptable according to binary criterion will be constructive. 237 We derive these criteria from existing documents that describe ROLL 238 network application requirements. These metrics do not encompass all 239 application requirements. Instead, they are a common set of routing 240 protocol requirements that most applications domains share. 241 Considering this very general and common set of requirements sets a 242 minimal bar for a protocol to be generally applicable. If a protocol 243 cannot meet even these minimalist criteria, then it cannot be used in 244 several major ROLL application domains and so is unlikely to be a 245 good candidate for further analysis and examination. Satisfying 246 these minimal criteria is necessary but not sufficient: they do not 247 represent the complete intersection of application requirements and 248 applications introduce additional, more stringent requirements. But 249 this simplified view provides a first cut of the applicability of 250 existing protocols, and those that do satisfy them might be 251 reasonable candidates for further study. 253 The five criteria are "table scalability", "loss response", "control 254 cost", "link cost", and "node cost". For each of these, the value 255 "pass" indicates that a given protocol has satisfactory performance 256 according to the metric. The value "fail" indicates that the 257 protocol does not have acceptable performance according to the 258 metric, and that the RFC defining the protocol does not, as written, 259 contain sufficient flexibility to alter the protocol to do so. 260 Finally, "?" indicates that an implementation could exhibit 261 satisfactory performance while following the RFC, but that the 262 implementation descisions necessary to do so are not specified and 263 may require some exploration. In other words, a "fail" means a 264 protocol would have to be modified so it is not compliant with its 265 RFC in order to meet the criterion, while a "?" means a protocol 266 would require a supplementary document further constraining and 267 specifying how a protocol should behave. 269 4.1. Formal Definitions 271 To provide precise definitions of these metrics, we use formal big-O 272 notation, where N refers to the number of nodes in the network, D 273 refers to the number of unique destinations, and L refers to the size 274 of a node's local, single-hop neighborhood (the network density). We 275 explain the derivation of each metric from application requirements 276 in its corresponding section. 278 4.2. Table Scalability 280 Scalability support for large networks of sensors is highlighted as a 281 key requirement by all three application requirements documents. 282 Network sizes range from a minimum of 250 nodes in the home routing 283 requirements [I-D.ietf-roll-home-routing-reqs] to very large networks 284 of "tens of thousands to millions" of devices noted of the urban 285 requirements [I-D.ietf-roll-urban-routing-reqs]. Networks are 286 expected to have similar size in industrial settings, the 287 requirements draft states that depths of up to 20 hops are to be 288 expected [I-D.ietf-roll-indus-routing-reqs]. Given that network 289 information maintained at each node is stored in routing and neighbor 290 tables, along with the constrained memory of nodes, necessitates 291 bounds on the size of these tables. 293 This metric examines whether routing tables scale within reasonable 294 memory resources of low-power nodes. According to this metric, 295 routing protocols that scale linearly with the size of the network or 296 a node's neighborhood fail. Scaling with the size of the network 297 prevents networks from growing to reasonable size, while scaling with 298 the network density precludes dense deployments. However, as many 299 low-power and lossy networks behave principally as data collection 300 networks and principally communicate through routers to data 301 collection points in the larger Internet, scaling with the number of 302 such collection points is reasonable. Protocols whose state scales 303 with the number of destinations pass. 305 More precisely, routing table size scaling with O(N) or O(L) fails. 306 A table that scales O(D) (assuming no N or L) passes. 308 4.3. Loss Response 310 In low power and lossy networks, links routinely come and go due to 311 being close to the SINR threshold. It is important that link churn 312 not trigger unnecessary responses by the routing protocol. This 313 point is stressed in all the application requirement documents, 314 pointing to the need to localize response to link failures with no 315 triggering of global network re-optimization, whether for reducing 316 traffic or for maintaining low route convergence times 317 ([I-D.ietf-roll-home-routing-reqs], 318 [I-D.ietf-roll-urban-routing-reqs], and 319 [I-D.ietf-roll-indus-routing-reqs]). The industrial routing 320 requirements draft states that protocols must be able to "recompute 321 paths based on underlying link characteristics which may change 322 dynamically", as well as reoptimize when the device set changes to 323 maintain service requirements. The protocol should also "always be 324 in the process of optimizing the system in response to changing link 325 statistics." Protocols with these properties should take care not to 326 require global updates. 328 A protocol which requires many link changes to propagate across the 329 entire network fails. Protocols which constrain the scope of 330 information propagation to only when they affect routes to active 331 destinations, or to local neighborhoods, pass. Protocols which allow 332 proactively path maintenance pass if the choice of which paths to 333 maintain is user-specified. 335 More precisely, loss responses that require O(N) transmissions fail, 336 while responses that can rely on O(1) local broadcasts or O(D) route 337 updates pass. 339 4.4. Control Cost 341 Battery-operated devices are a critical component of all three 342 application spectrums, and as such special emphasis is placed on 343 minimizing power consumption to achieve long battery lifetime, 344 [I-D.ietf-roll-home-routing-reqs], with multi-year deployments being 345 a common case [I-D.ietf-roll-indus-routing-reqs]. In terms of 346 routing structure, any proposed L2N routing protocol ought to support 347 the autonomous organization and configuration of the network at the 348 lowest possible energy cost [I-D.ietf-roll-urban-routing-reqs]. 350 All routing protocols must transmit additional data to detect 351 neighbors, build routes, transmit routing tables, or otherwise 352 conduct routing. As low-power wireless networks can have very low 353 data rates, protocols which require a minimum control packet rate can 354 have unbounded control overhead. This is particularly true for 355 event-driven networks, which only report data when certain conditions 356 are met. Regions of a network which never meet the condition can be 357 forced to send control traffic even when there is no data to send. 358 For these use cases, hard-coded timing constants are unacceptable, 359 because they imply a prior knowledge of the expected data rate. 361 If control traffic is unbounded by data traffic, a protocol fails 362 according to Control Cost metric. Protocols which pass bound their 363 control traffic rate to their data traffic. Protocols which pass do 364 not use resources to maintain unused state. More specifically, any 365 protocol which requires fixed-rate periodic control packets in the 366 absence of data traffic fails. 368 4.5. Link and Node Cost 370 These two metrics specify how a protocol chooses routes for data 371 packets to take through the network. Classical routing algorithms 372 typically acknowledge the differing costs of paths and may use a 373 shortest path algorithm to find paths. This is a requirement for low 374 power networks, as links must be evaluated as part of an objective 375 function across various metric types, such as minimizing latency and 376 maximizing reliability [I-D.ietf-roll-indus-routing-reqs]. 378 However, in low power networks it is also desirable to account for 379 the cost of routing through particular routers. Applications require 380 node or parameter constrained routing, which takes into account node 381 properties and attributes such as power, memory, and battery life 382 that dictate a router's willingness or ability to route other 383 packets. Home routing requirements note that devices will vary in 384 their duty cycle, and that routing protocols should prefer nodes with 385 permanent power [I-D.ietf-roll-home-routing-reqs]. The urban 386 requirements note that routing protocols may wish to take advantage 387 of differing data processing and managment capabilities among network 388 devices [I-D.ietf-roll-urban-routing-reqs]. Finally, industrial 389 requirements cite differing lifetime requirements as an important 390 factor to account for [I-D.ietf-roll-indus-routing-reqs]. Node cost 391 refers to the ability for a protocol to incorporate router properties 392 into routing metrics and use node attributes for constraint-based 393 routing. 395 A "pass" indicates that the protocol contains a mechanism allowing 396 these considerations to be considered when choosing routes. 398 5. Routing Protocol Taxonomy 400 Routing protocols broadly fall into two classes: link-state and 401 distance-vector. 403 A router running a link-state protocol first establishes adjacency 404 with its neighbors and then reliably floods the local topology 405 information in the form of a Link State Advertisement packet. The 406 collection of LSAs constitutes the Link State Database (LSDB) that 407 represents the network topology, and routers synchronize their LSDBs. 408 Thus each node in the network has a complete view of the network 409 topology. Each router uses the LSDB to compute a routing table where 410 each entry (reachable IP destination address) points to the next hop 411 along the shortest path according to some metric. Link state 412 protocols (such as OSPF and IS-IS) support the concept of area 413 (called "level" for IS-IS) whereby all the routers in the same area 414 share the same view (they have the same LSDB) and areas are 415 interconnected by border routers according to specific rules that 416 advertise IP prefix reachability between areas. 418 A distance vector protocol exchanges routing information rather than 419 topological information. A router running a distance vector protocol 420 exchanges information with its "neighbors" with which it has link 421 layer connectivity. Tunneling and similar mechanisms can virtualize 422 link layer connectivity to allow neighbors that are multiple layer 2 423 hops away. Rather than a map of the network topology from which each 424 router can calculate routes, a distance vector protocol node has 425 information on what routes its neighbors have. Each node's set of 426 available routes is the union of its neighbors routes plus a route to 427 itself. In a distance vector protocol, nodes may only advertise 428 routes which are in use, enabling on-demand discovery. In comparison 429 to link state protocols, distance vector protocols have the advantage 430 of only requiring neighbor routing information, but also have 431 corresponding limitations which protocols must address, such as 432 routing loops, count to infinity, split horizon, and slow convergence 433 times. Furthermore, routing constraints are difficult to enforce 434 with distance vector protocols. 436 Neighbor discovery is a critical component of any routing protocol. 437 It enables a protocol to learn about which other nodes are nearby and 438 which it can use as the next hop for routes. As neighbor discovery 439 is a key component of many protocols, several general protocols and 440 protocol mechanisms have been designed to support it. A protocol's 441 neighbor set is defined by how many "hops" away the set reaches. For 442 example, the 1-hop neighbor set of a node is all nodes it can 443 directly communicate with at the link layer, while the 2-hop neighbor 444 set is its own 1-hop neighbor set and the 1-hop neighbor sets of all 445 of its 1-hop neighbors. 447 Because nodes often have very limited resources for storing routing 448 state, protocols cannot assume that they can store complete neighbor 449 information. For example, a node with 4kB of RAM cannot store full 450 neighbor state when it has 1000 other nodes nearby. This means that 451 ROLL protocols must have mechanisms to decide which of many possible 452 neighbors they monitor as routable next hops. For elements such as 453 2-hop neighborhoods, these decisions can have a significant impact on 454 the topology that other nodes observe, and therefore may require 455 intelligent logic to prevent effects such as network partitions. 457 Protocols Today 459 Wired networks draw from both approaches. OSPF or IS-IS, for 460 example, are link-state protocols, while RIP is a distance-vector 461 protocol. 463 MANETs similarly draw from both approaches. OLSR is a link-state 464 protocol, while AODV and DYMO are distance vector protocols. The 465 general consensus in core networks is to use link state routing 466 protocols as IGPs for a number of reasons: in many cases having a 467 complete network topology view is required to adequately compute the 468 shortest path according to some metrics. For some applications such 469 as MPLS Traffic Engineering it is even required to have the knowledge 470 of the Traffic Engineering Database for constraint based routing. 472 Furthermore link state protocols typically have superior convergence 473 speeds (ability to find an alternate path in case of network element 474 failure), are easier to debug and troubleshoot, and introduce less 475 control packet overhead than distance vector protocols. In contrast, 476 distance vector protocols are simpler, require less computation, and 477 have smaller storage requirements. Most of these tradeoffs are 478 similar in wireless networks, with one exception. Because wireless 479 links can suffer from significant temporal variation, link state 480 protocols can have higher traffic loads as topology changes must 481 propagate globally, while in a distance vector protocol a node can 482 make local routing decisions with no effect on the global routing 483 topology. One major protocol, DSR, does not easily fit into one of 484 these two classes. Although it is a distance vector protocol, DSR 485 has several properties that make it differ from most other protocols 486 in this class. We examine these differences in our discussion of 487 DSR. 489 The next two sections summarize several well established routing 490 protocols. This table shows, based on the criteria described above, 491 whether these protocols meet ROLL criteria. Annex A contains the 492 reasoning behind each value in the table. 494 Protocol Table Loss Control Link Cost Node Cost 495 OSPF fail fail fail pass fail 496 OLSRv2 fail fail fail pass pass 497 TBRPF fail pass fail pass ? 498 RIP pass fail fail ? ? 499 AODV pass fail pass fail fail 500 DYMO[-low] pass fail pass ? fail 501 DSR fail pass pass fail fail 503 6. Link State Protocols 505 6.1. OSPF 507 OSPF (specified in [RFC2328] for IPv4 and in [RFC2740] for IPv6)) is 508 a link state protocol designed for routing within an Internet 509 Autonomous System (AS). OSPF provides the ability to divide a 510 network into areas, which can establish a routing hierarchy. The 511 topology within an area is hidden from other areas and IP prefix 512 reachability across areas (inter-area routing) is provided using 513 summary LSAs. The hierarchy implies that there is a top-level 514 routing area (the backbone area) which connects other areas. Areas 515 may be connected to the back-bone area through a virtual link. OSPF 516 maintains routing adjacencies by sending hello messages. OSPF 517 calculates the shortest path to a node using link metrics (that may 518 reflect the link bandwidth, propagation delay, ...). OSPF Traffic 519 Engineering (OSPF-TE, [RFC3630]) extends OSPF to include information 520 on reservable, unreserved, and available bandwidth. 522 6.2. OLSR 524 Optimized Link State Routing (OLSR) (see [RFC3626] and 525 [I-D.ietf-manet-olsrv2]) is a link state routing protocol for 526 wireless mesh networks. OLSR nodes flood route discovery packets 527 throughout the entire network, such that each node has a map of the 528 mesh topology. Because link variations can lead to heavy flooding 529 traffic when using a link state approach, OLSR establishes a topology 530 for minimizing this communication. Each node maintains a set of 531 nodes called its Multipoint Relays (MPR), which is a subset of the 532 one-hop neighbors whose connectivity covers the two-hop neighborhood. 533 Each node that is an MPR maintains a set called its MPR selectors, 534 which are nodes that have chosen it to be an MPR. 536 OLSR uses these two sets to apply three optimizations. First, only 537 MPRs generate link state information. Second, nodes can use MPRs to 538 limit the set of nodes that forward link state packets. Third, an 539 MPR, rather than advertise all of its links, can advertise only links 540 to its MPR selectors. Together, these three optimizations can 541 greatly reduce the control traffic in dense networks, as the number 542 of MPRs should not increase significantly as a network becomes 543 denser. 545 OLSR selects routes based on hop counts, and assumes an underlying 546 protocol that determines whether a link exists between two nodes. 547 OLSR's constrained flooding allows it to quickly adapt to and 548 propagate topology changes. 550 OLSR is closely related to clustering algorithms in the wireless 551 sensor networking literature, in which cluster heads are elected such 552 that routing occurs over links between cluster heads and all other 553 nodes are leafs that communicate to a cluster head. 555 6.3. TBRPF 557 Topology Dissemination Based on Reverse Path Forwarding (see 558 [RFC3684]) is another proactive link state protocol. TBRPF computes 559 a source tree, which provides routes to all reachable nodes. It 560 reduces control packet overhead by having nodes only transmit a 561 subset of their source tree as well as by using differential updates. 563 The major difference between TBRPF and OLSR is the routing data that 564 nodes advertise and who chooses to aggregate information. In OLSR, 565 nodes select neighbors to be MPRs and advertise their link state for 566 them; in TBRPF, nodes elect themselves to advertise relevant link 567 state based on whether it acts as a next hop. 569 7. Distance Vector protocols 571 7.1. RIP 573 The Routing Information Protocol (RIP) (defined in [RFC2453]) 574 predates OSPF. As it is a distance vector protocol, routing loops 575 can occur and considerable work has been done to accelerate 576 convergence since the initial RIP protocols were introduced. RIP 577 measures route cost in terms of hops, and detects routing loops by 578 observing a route cost approach infinity where "infinity" is referred 579 to as a maximum number of hops. RIP is typically not appropriate for 580 situations where routes need to be chosen based on real-time 581 parameters such as measured delay, reliability, or load or when the 582 network topology needs to be known for route computation. 584 "Triggered RIP" (defined in [RFC2091]) was originally designed to 585 support "on-demand" circuits. The aim of triggered RIP is to avoid 586 systematically sending the routing database on regular intervals. 587 Instead, triggered RIP sends the database when there is a routing 588 update or a next hop adjacency change: once neighbors have exchanged 589 their routing database, only incremental updates need to be sent. 590 Because incremental updates cannot depend on periodic traffic to 591 overcome loses, triggered RIP uses acknowledgment based mechanisms 592 for reliable delivery. 594 7.2. Ad-hoc On Demand Vector Routing (AODV) 596 AODV (specified in [RFC3561]) is a distance vector protocol intended 597 for mobile ad-hoc networks. When one AODV node requires a route to 598 another, it floods a request in the network to discover a route. A 599 depth-scoped flooding process avoids discovery from expanding to the 600 most distant regions of the network that are in the opposite 601 direction of the destination. AODV chooses routes that have the 602 minimum hop count. 604 If an AODV route request reaches a node that has a route to the 605 destination (this includes the destination itself), that node sends a 606 reply along the reverse route. All nodes along the reverse route can 607 cache the route. When routes break due to topology changes, AODV 608 floods error messages and issues a new request. Because AODV is on- 609 demand it only maintains routes for active nodes. When a link 610 breaks, AODV issues a Route Error (RERR) and a new route request 611 message (RREQ), with a higher sequence number so nodes do not respond 612 from their route caches. These packets can flood the entire network, 613 giving loss response a fail. 615 7.3. DYMO 617 Dynamic Mobile On-Demand routing (DYMO) ([I-D.ietf-manet-dymo]) is an 618 evolution of AODV. The basic functionality is the same, but it has 619 different packet formats, handling rules, and supports path 620 accumulation. Path accumulation allows a single DYMO route request 621 to generate routes to all nodes along the route to that destination. 622 Like AODV, DYMO uses hop counts as its routing metric, but links may 623 have a cost >= 1, allowing DYMO to represent link costs. Like AODV, 624 on link breaks DYMO issues a new route request message (RREQ), with a 625 higher sequence number so nodes do not respond from their route 626 caches. Correspondingly, a route request can flood the entire 627 network. 629 7.4. DSR 631 Dynamic Source Routing ([RFC4728]) is a distance vector protocol, but 632 a DSR packet source explicitly specifies the route for each packet. 633 Because the route is determined at a single place -- the source -- 634 DSR does not require sequence numbers or other mechanisms to prevent 635 routing loops, as there is no problem of inconsistent routing tables. 636 Unlike AODV and DYMO, by pushing state into packet headers, DSR does 637 not require per-destination routing state. Instead, a node 638 originating packets only needs to store a spanning tree of the part 639 of the network it is communicating with. 641 8. Neighbor Discovery 643 A limit on maintained routing state (light footprint) prevents ROLL 644 protocols from assuming they know all 1-hop, 2-hop, or N-hop 645 neighbors. For this reason, while protocols such as MANET-NHDP 646 ([I-D.ietf-manet-nhdp]) and IPv6's neighbor discovery ([RFC4861]) 647 provide basic mechanisms for discovering link-layer neighbors, not 648 all of their features are relevant. This section describes these two 649 protocols, their capabilities, and how ROLL protocols could leverage 650 them. 652 8.1. IPv6 Neighbor Discovery 654 IPv6 neighbor discovery provides mechanisms for nodes to discover 655 single-hop neighbors as well as routers that can forward packets past 656 the local neighborhood. There is an implicit assumption that the 657 delegation of whether a node is a router or not is static (e.g., 658 based on a wired topology). The fact that all routers must respond 659 to a Router Solicitation requires that the number of routers with a 660 1-hop neighborhood is small, or there will be a reply implosion. 661 Furthermore, IPv6 neighbor discovery's support of address 662 autoconfiguration assumes address provisioning, in that addresses 663 reflect the underlying communication topology. IPv6 neighbor 664 discovery does not consider asymmetric links. Nevertheless, it may 665 be possible to extend and adapt IPv6's mechanisms to wireless in 666 order to avoid response storms and implosions. 668 8.2. MANET-NHDP 670 The MANET Neighborhood Discovery Protocol (MANET-NHDP) provides 671 mechanisms for discovering a node's symmetric 2-hop neighborhood. It 672 maintains information on discovered links, their interfaces, status, 673 and neighbor sets. MANET-NHDP advertises a node's local link state; 674 by listening to all of its 1-hop neighbor's advertisements, a node 675 can compute its 2-hop neighborhood. MANET-NHDP link state 676 advertisements can include a link quality metric. MANET-NHDP's node 677 information base includes all interface addresses of each 1-hop 678 neighbor: for low-power nodes, this state requirement can be 679 difficult to support. 681 9. Security Issues 683 TBD 685 10. Manageability Issues 687 TBD 689 11. IANA Considerations 691 This document includes no request to IANA. 693 12. Security Considerations 695 TBD 697 13. Acknowledgements 699 14. Annex A - Routing protocol scalability analysis 701 This aim of this Annex is to provide the details for the analysis 702 routing scalability analysis. 704 "OSPF" 706 OSPF floods link state through a network. Each router must receive 707 this complete link set. OSPF fails the table size criterion because 708 it requires each router to discover each link in the network, for a 709 total routing table size which is O(N * L). This also causes it to 710 fail the control cost criterion, since this information must be 711 propagated. Furthermore, changes in the link set require re-flooding 712 the network link state even if the changed links were not being used. 713 Since link state changes in wireless networks are often uncorrelated 714 with data traffic and are instead caused by external (environmental) 715 factors, this causes OSPF to fail both the control cost and loss 716 response criteria. OSPF routers can impose policies on the use of 717 links and can consider link properties (Type of Service), as the cost 718 associated with an edge is configurable by the system administrator 719 [RFC2328], so receive a pass for link cost. However, there is no way 720 to associate metrics with routers (as costs are only applied to 721 outgoing interfaces, i.e. edges) when computing paths, and so fails 722 the node cost criteria. While [RFC3630] discusses paths that take 723 into account node attributes, it specifically states that no known 724 algorithm or mechanism currently exists for incoporating this into 725 the OSPF RFC. 727 "OLSRv2" 729 OLSRv2 is a proactive link state protocol, flooding this information 730 through a set of multipoint relays (MPRs). Routing state includes 731 1-hop neighbor information for each node in the network, 1-hop and 732 2-hop information for neighbors (for MPR selection), and a routing 733 table (consisting of destination, and next hop), resulting in state 734 proportional to network size and density (O(N*L + L^2)), and failing 735 the table scalability criteria. 737 Unacceptable control traffic overhead arises from flooding and 738 maintenance. HELLO messages are periodically broadcast local beacon 739 messages, but TC messages spread topology information throughout the 740 network (using MPRs). As such, control traffic is proportional to 741 O(N^2). MPRs reduce this load to O(N^2 / L). As the number of MPRs 742 is inversely proportional to the density of the network and L is 743 bounded by N, this means control traffic is at best proportional to 744 O(N), and fails the control cost metric. 746 Furthermore, changes in the link set require immediately re-flooding 747 the network link state even if those links were not being used by 748 routing, which fails the loss response metric. 750 OLSR allows for specification of link quality, and also provides a 751 'Willingness' metric to symbolize node cost, giving it a pass for 752 both those metrics. 754 "TBRPF" 756 As a link state protocol where each node maintains a database of the 757 entire network topology, TBRPF's routing table size scales with 758 network size and density, leading to table sizes which are O(N * L) 759 when a node receives disjoint link sets from its neighbors. This 760 causes the protocol to fail the table size criteria. The protocol's 761 use of differential updates should allow both fast response time and 762 incremental changes once the distributed database of links has been 763 established. Differential updates are only used to reduce response 764 time to changing network conditions, not to reduce the amount of 765 topology information sent, since each node will periodically send 766 their piece of the topology. As a result, TBRPF fails the control 767 overhead criteria. However, its differential updates triggered by 768 link failure do not immediately cause a global re-flooding of state 769 (but only to affected routers) [RFC3684], leading to a pass for loss 770 response. 772 TBRPF has a flexible neighbor management layer which enables it to 773 incorporate various types of link metrics into its routing decision 774 by enabling a USE_METRIC flag [RFC3684]. As a result, it receives a 775 pass for link cost. It also provides a mechanism whereby routers can 776 maintain multiple link metrics to a single neighbor, some of which 777 can be advertised by the neighbor router [RFC3684]. Although the RFC 778 does not specify a policy for using these values, developing one 779 could allow TBRPF to satisfy this requirement, leading to a ? for the 780 node cost requirement. 782 "RIP" 784 RIP is a distance vector protocol: all routers maintain a route to 785 all other routers. Routing table size is therefore O(N). However, 786 if destinations are known apriori, table size can be reduced to O(D), 787 resulting in a pass for table scalability. Each node broadcasts a 788 beacon per period, and updates must be propagated by affected nodes, 789 irrespective of data rate, failing the control cost metric. Loss 790 triggers updates, only propagating if part of a best route, but even 791 if the route is not actively being used, resulting in a fail for loss 792 response. The rate of triggered updates is throttled, and these are 793 only differential updates, yet this still doesn't account for other 794 control traffic (or tie it to data rate) or prevent the triggered 795 updates from being flooded along non-active paths. [RFC2453] 797 RIP receives a ? for link cost because while current implementations 798 focus on hop count and that is the metric used in [RFC2453], the RFC 799 also mentions that more complex metrics such as differences in 800 bandwidth and reliability could be used. However, the RFC also 801 states that real-time metrics such as link-quality would create 802 instability and the concept of node cost only appears as metrics 803 assigned to external networks. It also receives a ? because the 804 concept of a network cost is introduced, which is added to link cost, 805 but does not describe its use. 807 "AODV" 809 AODV table size is a function of the number of communicating pairs in 810 the network, scaling with O(D). This is acceptable and so AODV 811 passes the table size criteria. As an on-demand protocol, AODV does 812 not generate any traffic until data is sent, and so control traffic 813 is correlated with the data and so it receives a pass for control 814 traffic. When a broken link is detected, AODV will use a precursor 815 list maintained for each destination to inform downstream routers 816 (with a RERR) of the topology change. However, the RERR message is 817 forwarded by all nodes that have a route that uses the broken link, 818 even if the route is not currently active, leading to a fail for loss 819 response [RFC3561]. 821 AODV fails the link cost metric because the only metric used is hop 822 count, and this is hardcoded in the route table entry, according to 823 the RFC [RFC3561]. It fails the node cost requirement because there 824 is no way for a router to indicate its [lack of] willingness to route 825 while still adhering to the RFC. 827 "DYMO/DYMO-low" 829 The design of DYMO shares much with AODV, with some changes to remove 830 precursor lists and compact various messages. It still passes the 831 table size criteria because it only maintains routes requested by 832 RREQ messages, resulting in O(D) table size. Control traffic (RREQ, 833 RREP, and RREQ) are still driven by data, and hence DYMO passes the 834 control cost criterion. However, RERR messages are forwarded by any 835 nodes that have a route using the link, even if inactive, leading to 836 a fail of the loss reponse criteria [I-D.ietf-manet-dymo]. 838 While DYMO does indicate that the metric used for a link can vary 839 from 1-65535, it specifically refers to this as distance, which is 840 incremented by at least one at each hop [I-D.ietf-manet-dymo], 841 leading to a ? in link cost. While additional routing information 842 can be added DYMO messages, there is no mention of node cost, leading 843 to a fail in node cost. 845 "DSR" 847 DSR performs on-demand route discovery, and source routing of 848 packets. It maintains a source route for all destinations, and also 849 a blacklist of all unidirectional neighbor links [RFC4728], leading 850 to a total table size of O(D + L), failing the table size criterion. 851 Control traffic is completely data driven, and so DSR receives a pass 852 for this criteria. Finally, a transmission failure only prompts an 853 unreachable destination to be sent to the source of the message, 854 passing the loss response criteria. 856 DSR fails the link cost criterion because its source routes are 857 advertised only in terms of hops, such that all advertised links are 858 considered equivalent. DSR also fails the node cost criterion 859 because a node has no way of indicating its willingness to serve as a 860 router and forward messages. 862 15. References 864 15.1. Normative References 866 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 867 Requirement Levels", BCP 14, RFC 2119, March 1997. 869 15.2. Informative References 871 [I-D.ietf-manet-dymo] 872 Chakeres, I. and C. Perkins, "Dynamic MANET On-demand 873 (DYMO) Routing", draft-ietf-manet-dymo-14 (work in 874 progress), June 2008. 876 [I-D.ietf-manet-nhdp] 877 Clausen, T., Dearlove, C., and J. Dean, "MANET 878 Neighborhood Discovery Protocol (NHDP)", 879 draft-ietf-manet-nhdp-07 (work in progress), July 2008. 881 [I-D.ietf-manet-olsrv2] 882 Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized 883 Link State Routing Protocol version 2", 884 draft-ietf-manet-olsrv2-07 (work in progress), July 2008. 886 [I-D.ietf-roll-home-routing-reqs] 887 Brandt, A., Buron, J., and G. Porcu, "Home Automation 888 Routing Requirement in Low Power and Lossy Networks", 889 draft-ietf-roll-home-routing-reqs-03 (work in progress), 890 September 2008. 892 [I-D.ietf-roll-indus-routing-reqs] 893 Networks, D., Thubert, P., Dwars, S., and T. Phinney, 894 "Industrial Routing Requirements in Low Power and Lossy 895 Networks", draft-ietf-roll-indus-routing-reqs-01 (work in 896 progress), July 2008. 898 [I-D.ietf-roll-urban-routing-reqs] 899 Dohler, M., Watteyne, T., Winter, T., Jacquenet, C., 900 Madhusudan, G., Chegaray, G., and D. Barthel, "Urban WSNs 901 Routing Requirements in Low Power and Lossy Networks", 902 draft-ietf-roll-urban-routing-reqs-01 (work in progress), 903 July 2008. 905 [RFC2091] Meyer, G. and S. Sherry, "Triggered Extensions to RIP to 906 Support Demand Circuits", RFC 2091, January 1997. 908 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 910 [RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453, 911 November 1998. 913 [RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", 914 RFC 2740, December 1999. 916 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 917 Demand Distance Vector (AODV) Routing", RFC 3561, 918 July 2003. 920 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing 921 Protocol (OLSR)", RFC 3626, October 2003. 923 [RFC3630] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering 924 (TE) Extensions to OSPF Version 2", RFC 3630, 925 September 2003. 927 [RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology 928 Dissemination Based on Reverse-Path Forwarding (TBRPF)", 929 RFC 3684, February 2004. 931 [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source 932 Routing Protocol (DSR) for Mobile Ad Hoc Networks for 933 IPv4", RFC 4728, February 2007. 935 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 936 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 937 September 2007. 939 Authors' Addresses 941 Philip Levis 942 Stanford University 943 358 Gates Hall, Stanford University 944 Stanford, CA 94305-9030 945 USA 947 Email: pal@cs.stanford.edu 949 Arsalan Tavakoli 950 UC Berkeley 951 Soda Hall, UC Berkeley 952 Berkeley, CA 94707 953 USA 955 Email: arsalan@eecs.berkeley.edu 957 Stephen Dawson-Haggerty 958 UC Berkeley 959 Soda Hall, UC Berkeley 960 Berkeley, CA 94707 961 USA 963 Email: stevedh@cs.berkeley.edu 965 Full Copyright Statement 967 Copyright (C) The IETF Trust (2008). 969 This document is subject to the rights, licenses and restrictions 970 contained in BCP 78, and except as set forth therein, the authors 971 retain all their rights. 973 This document and the information contained herein are provided on an 974 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 975 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 976 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 977 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 978 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 979 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 981 Intellectual Property 983 The IETF takes no position regarding the validity or scope of any 984 Intellectual Property Rights or other rights that might be claimed to 985 pertain to the implementation or use of the technology described in 986 this document or the extent to which any license under such rights 987 might or might not be available; nor does it represent that it has 988 made any independent effort to identify any such rights. Information 989 on the procedures with respect to rights in RFC documents can be 990 found in BCP 78 and BCP 79. 992 Copies of IPR disclosures made to the IETF Secretariat and any 993 assurances of licenses to be made available, or the result of an 994 attempt made to obtain a general license or permission for the use of 995 such proprietary rights by implementers or users of this 996 specification can be obtained from the IETF on-line IPR repository at 997 http://www.ietf.org/ipr. 999 The IETF invites any interested party to bring to its attention any 1000 copyrights, patents or patent applications, or other proprietary 1001 rights that may cover technology that may be required to implement 1002 this standard. Please address the information to the IETF at 1003 ietf-ipr@ietf.org.