idnits 2.17.1 draft-ietf-roll-protocols-survey-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. 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 and authors Copyright Line does not match the current year == Line 580 has weird spacing: '... fail fai...' == Line 581 has weird spacing: '... fail fai...' == Line 582 has weird spacing: '... fail pas...' == Line 583 has weird spacing: '... pass fai...' == Line 584 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 (January 20, 2009) is 5574 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: '-low' is mentioned on line 585, but not defined == Outdated reference: A later version (-26) exists of draft-ietf-manet-dymo-16 == 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-06 == Outdated reference: A later version (-06) exists of draft-ietf-roll-indus-routing-reqs-03 == Outdated reference: A later version (-05) exists of draft-ietf-roll-urban-routing-reqs-03 == Outdated reference: A later version (-10) exists of draft-irtf-dtnrg-prophet-01 == Outdated reference: A later version (-08) exists of draft-thubert-tree-discovery-07 -- Obsolete informational reference (is this intentional?): RFC 1142 (Obsoleted by RFC 7142) -- Obsolete informational reference (is this intentional?): RFC 2740 (Obsoleted by RFC 5340) Summary: 1 error (**), 0 flaws (~~), 18 warnings (==), 3 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: July 24, 2009 S. Dawson-Haggerty 6 UC Berkeley 7 January 20, 2009 9 Overview of Existing Routing Protocols for Low Power and Lossy Networks 10 draft-ietf-roll-protocols-survey-04 12 Status of this Memo 14 This Internet-Draft is submitted to IETF in full conformance with the 15 provisions of BCP 78 and BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on July 24, 2009. 35 Copyright Notice 37 Copyright (c) 2009 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. 47 Abstract 49 Networks of low power wireless devices introduce novel IP routing 50 issues. Low-power wireless devices, such as sensors, actuators and 51 smart objects, have difficult constraints: very limited memory, 52 little processing power, and long sleep periods. As most of these 53 devices are battery-powered, energy efficiency is critically 54 important. Wireless link qualities can vary significantly over time, 55 requiring protocols to make agile decisions yet minimize topology 56 change energy costs. Routing over such low power and lossy networks 57 has novel requirements that existing protocols may not address. This 58 document provides a brief survey of the strengths and weaknesses of 59 existing protocols with respect to this class of networks. From this 60 survey it examines whether existing and mature IETF protocols can be 61 used without modification in these networks, or whether further work 62 is necessary. 64 Table of Contents 66 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 67 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 68 3. Methodology . . . . . . . . . . . . . . . . . . . . . . . . . 6 69 3.1. Protocols Considered . . . . . . . . . . . . . . . . . . . 6 70 3.2. Criteria . . . . . . . . . . . . . . . . . . . . . . . . . 7 71 3.3. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 7 72 4. Suitability Summary . . . . . . . . . . . . . . . . . . . . . 7 73 4.1. Formal Definitions . . . . . . . . . . . . . . . . . . . . 8 74 4.2. Table Scalability . . . . . . . . . . . . . . . . . . . . 8 75 4.3. Loss Response . . . . . . . . . . . . . . . . . . . . . . 9 76 4.4. Control Cost . . . . . . . . . . . . . . . . . . . . . . . 10 77 4.5. Link and Node Cost . . . . . . . . . . . . . . . . . . . . 11 78 5. Routing Protocol Taxonomy . . . . . . . . . . . . . . . . . . 12 79 5.1. Protocols Today . . . . . . . . . . . . . . . . . . . . . 13 80 6. Link State Protocols . . . . . . . . . . . . . . . . . . . . . 14 81 6.1. OSPF & IS-IS . . . . . . . . . . . . . . . . . . . . . . . 14 82 6.2. OLSR & OLSRv2 . . . . . . . . . . . . . . . . . . . . . . 14 83 6.3. TBRPF . . . . . . . . . . . . . . . . . . . . . . . . . . 15 84 7. Distance Vector protocols . . . . . . . . . . . . . . . . . . 15 85 7.1. RIP . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 86 7.2. Ad-hoc On Demand Vector Routing (AODV) . . . . . . . . . . 16 87 7.3. DYMO . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 88 7.4. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 89 8. Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . 17 90 8.1. IPv6 Neighbor Discovery . . . . . . . . . . . . . . . . . 17 91 8.2. MANET-NHDP . . . . . . . . . . . . . . . . . . . . . . . . 17 92 9. Security Considerations . . . . . . . . . . . . . . . . . . . 18 93 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 94 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 18 95 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18 96 12.1. Normative References . . . . . . . . . . . . . . . . . . . 18 97 12.2. Informative References . . . . . . . . . . . . . . . . . . 18 98 Appendix A. Routing protocol scalability analysis . . . . . . . . 20 99 Appendix B. Logarithmic scaling of control cost . . . . . . . . . 24 100 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25 102 1. Terminology 104 AODV: Ad-hoc On Demand Vector Routing 106 DSR: Dynamic Source Routing 108 DYMO: Dynamic Mobile On-Demand 110 IS-IS: Intermediate System to Intermediate System 112 OLSR: Optimized Link State Routing 114 OSPF: Open Shortest Path First 116 RIP: Routing Information Protocol 118 TBRPF: Topology Dissemination Based on Reverse Path Forwarding 120 LLN: Low power and Lossy Network 122 LSA: Link State Advertisement 124 LSDB: Link State Database 126 MANET: Mobile Ad-hoc Network 128 MAC: Medium Access Control 130 MPLS: Multiprotocol Label Switching 132 MPR: Multipoint Relays 134 MTU: Maximum Transmission Unit 136 ROLL: Routing in Low power and Lossy Networks 138 TDMA: Time Division Multiple Access 140 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 141 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 142 document are to be interpreted as described in RFC 2119 [RFC2119]. 144 2. Introduction 146 Wireless is increasingly important to computer networking. As the 147 technological progress underlying behind Moore's Law has reduced 148 computer prices and form factors, networking has come to include not 149 only servers and desktops, but laptops, palmtops, and cellphones. As 150 computing device costs and sizes have shrunk, small wireless sensors, 151 actuators, and smart objects have emerged as an important next step 152 in internetworking. The sheer number of the low-power networked 153 devices means that they cannot depend on human intervention (e.g., 154 adjusting position) for good networking: they must have routing 155 protocols that enable them to self-organize into multihop networks. 157 Energy is a fundamental challenge in these devices. Convenience and 158 ease of use requires they be wireless and therefore battery powered. 159 Correspondingly, low power operation is a key concern for these 160 sensors and actuators so as to allow them to function for months and 161 years without interruption. Cost points and energy limitations cause 162 these devices to have very limited resources: a few kB of RAM and a 163 few MHz of CPU is typical. As energy efficiency does not improve 164 with Moore's Law, these limitations are not temporary. This trend 165 towards smaller, lower power, and more numerous devices has led to 166 new low-power wireless link layers to support them. 168 In practice, wireless networks observe much higher loss rates than 169 wired ones do, and low-power wireless is no exception. Furthermore, 170 many of these networks will include powered as well as energy 171 constrained nodes. Nevertheless, for cost and scaling reasons, many 172 of these powered devices will still have limited resources. 174 These low power and lossy networks introduce constraints and 175 requirements that other networks typically do not possess; for 176 instance, in addition to the constraints of limited resources and 177 small power sources which constrain the amount of traffic a protocol 178 may generate, these applications demand an embrace of heterogeneous 179 node capabilities, and good support for specific traffic patterns 180 ([I-D.ietf-roll-home-routing-reqs] and 181 [I-D.ietf-roll-indus-routing-reqs]). 183 As existing protocols were not designed with these requirements in 184 mind, they may or may not work well in LLNs. The first step to 185 reaching consensus on a routing protocol for LLNs is to decide which 186 of these two is true. If an existing protocol can meet LLN 187 requirements without any changes, then barring extenuating 188 circumstances, it behooves us to use an existing standard. However, 189 if no current protocol can meet LLN's requirements, then further work 190 will be needed to define and standardize with a protocol that can. 191 Whether or not such a protocol involves modifications to an existing 192 protocol or a new protocol entirely is outside the scope of this 193 document: this document simply seeks to answer the question: do LLNs 194 require a new protocol specification document at all? 196 3. Methodology 198 To answer the question of LLNs require new protocol specification 199 work, this document examines existing routing protocols and how well 200 they can be applied to low power and lossy networks. It provides a 201 set of criteria with which to compare the costs and benefits of 202 different protocol designs and examines existing protocols in terms 203 of these criteria. 205 3.1. Protocols Considered 207 This document does not seek to answer the question of whether there 208 is any protocol anywhere which could meet LLN application 209 requirements. Rather, it seeks to answer whether protocols, as 210 specified in current IETF standards documents, can meet such 211 requirements. If an existing protocol specification can be used 212 unchanged, then writing additional protocol specifications is 213 unnecessary. For example, there are many academic papers and 214 experimental protocol implementations available; while one or more of 215 these may meet LLN requirements, if they are not specified in an RFC 216 then a working group will need to write a new RFC for them to be a 217 standard. The question this document seeks to answer is not whether 218 proposed, evaluated, theoretical or hypothetical protocol designs can 219 satisfy LLN requirements: the question is whether existing IETF 220 standards can. 222 Therefore, this document considers "existing routing protocols" to be 223 protocols that are specified in RFCs or, in the cases of DYMO 224 [I-D.ietf-manet-dymo] or OLSRv2 [I-D.ietf-manet-olsrv2], a very 225 mature draft that is a working item of an IETF working group. The 226 list of considered protocols is OSPF [RFC2328], IS-IS [RFC1142], RIP 227 [RFC2453], OLSR [RFC3626], OLSv2 [I-D.ietf-manet-olsrv2], TBRPF 228 [RFC3684], AODV [RFC3561], DYMO [I-D.ietf-manet-dymo], and DSR 229 [RFC4728]. This document also considers notable variants of these 230 protocols, such as Triggered RIP [RFC2091]. 232 This document does not consider DTN bundles [RFC5050] or the DTN 233 Licklider protocol [RFC5326] as suggested by the ROLL working group 234 charter, because they are not routing protocols. This document does 235 no consider the DTN routing protocol PRoPHET [I-D.irtf-dtnrg-prophet] 236 because its design is based on the non-randomness of node mobility, 237 which does not exist in many LLN application domains. 239 This document does not examine the Network Mobility Basic Support 240 Protocol (NEMO RFC 3963 [RFC3963]) because it is not a routing 241 protocol. It does not examine hierarchical NEMO 242 [I-D.thubert-tree-discovery] as a candidate because it only maintains 243 a default route and so is insufficient for general routing. Although 244 NEMO itself is not a suitable routing solution to LLNs, some of its 245 mechanisms, such as loop-free tree formation, might be useful in an 246 LLN routing protocol. 248 3.2. Criteria 250 The five criteria this document uses are derived from a set of drafts 251 that describe the requirements of a few major LLN application 252 scenarios. The five criteria, presented in Section 4, are neither 253 exhaustive nor complete. Instead, they are one specific subset of 254 high-level requirements shared across all of the application 255 requirement drafts. Because every application requirement draft 256 specifies these criteria, then a protocol which does not meet one of 257 them cannot be used without modifications or extensions. However, 258 because these criteria represent a subset of the intersection of the 259 application requirements, any given application domain may impose 260 additional requirements which a particular protocol may not meet. 261 For this reason, these criteria are "necessary but not sufficient." 262 A protocol that does not meet the criteria cannot be used as 263 specified, but it is possible that a protocol meets the criteria yet 264 is not able to meet the requirements of a particular application 265 domain. Nevertheless, a protocol that meets all of the criteria 266 would be very promising, and deserve a closer look and consideration 267 in light of LLN application domains. 269 3.3. Evaluation 271 Whether a protocol meets these criteria was judged by thinking 272 through each specification and considering a hypothetical 273 implementation which took advantage of the specification so as to 274 perform as well as possible on the criteria. The judgement is based 275 on what a specification allows, rather than any particular 276 implementation of that specification. For example, while many DYMO 277 implementations use hopcount as a routing metric, the DYMO 278 specification allows a hop to add more than one to the routing 279 metric, so DYMO as a specification can support some links or nodes 280 being more costly than others. 282 4. Suitability Summary 284 In this section, we present five important requirements for routing 285 in low power and lossy networks, and evaluate protocols against them. 286 This evaluation attempts to take a complicated and interrelated set 287 of design decisions and trade-offs and condense them to a simple 288 "pass", "fail", or "?". As with any simplification, there is a risk 289 of removing some necessary nuance. However, we believe that being 290 forced to take a position on whether or not these protocols are 291 acceptable according to binary criterion will be constructive. 293 We derive these criteria from existing documents that describe ROLL 294 network application requirements. These criteria do not encompass 295 all application requirements. Instead, they are a common set of 296 routing protocol requirements that most applications domains share. 297 Considering this very general and common set of requirements sets a 298 minimal bar for a protocol to be generally applicable. If a protocol 299 cannot meet even these minimalist criteria, then it cannot be used 300 unchanged in several major ROLL application domains and so is 301 unlikely to be a good candidate for use. Satisfying these minimal 302 criteria is necessary but not sufficient: they do not represent the 303 complete intersection of application requirements and applications 304 introduce additional, more stringent requirements. But this 305 simplified view provides a first cut of the applicability of existing 306 protocols, and those that do satisfy them might be reasonable 307 candidates for further study. 309 The five criteria are "table scalability", "loss response", "control 310 cost", "link cost", and "node cost". For each of these, the value 311 "pass" indicates that a given protocol has satisfactory performance 312 according to the criterion. The value "fail" indicates that the 313 protocol does not have acceptable performance according to the 314 criterion, and that the RFC defining the protocol does not, as 315 written, contain sufficient flexibility to alter the protocol to do 316 so. Finally, "?" indicates that an implementation could exhibit 317 satisfactory performance while following the RFC or Internet draft, 318 but that the implementation decisions necessary to do so are not 319 specified and may require some exploration. In other words, a "fail" 320 means a protocol would have to be modified so it is not compliant 321 with its specification in order to meet the criterion, while a "?" 322 means a protocol would require a supplementary document further 323 constraining and specifying how a protocol should behave. 325 4.1. Formal Definitions 327 To provide precise definitions of these criteria, we use formal big-O 328 notation, where N refers to the number of nodes in the network, D 329 refers to the number of unique destinations, and L refers to the size 330 of a node's local, single-hop neighborhood (the network density). We 331 explain the derivation of each criterion from application 332 requirements in its corresponding section. 334 4.2. Table Scalability 336 Scalability support for large networks of sensors is highlighted as a 337 key requirement by all three application requirements documents. 338 Network sizes range from a minimum of 250 nodes in the home routing 339 requirements [I-D.ietf-roll-home-routing-reqs] to very large networks 340 of "tens of thousands to millions" of devices noted of the urban 341 requirements [I-D.ietf-roll-urban-routing-reqs]. Networks are 342 expected to have similar size in industrial settings, the 343 requirements draft states that depths of up to 20 hops are to be 344 expected [I-D.ietf-roll-indus-routing-reqs]. Given that network 345 information maintained at each node is stored in routing and neighbor 346 tables, along with the constrained memory of nodes, necessitates 347 bounds on the size of these tables. 349 This criterion indicates whether routing tables scale reasonably 350 within the memory resources of low-power nodes. According to this 351 criterion, routing tables that scale linearly with the size of the 352 network or a node's neighborhood fail. Scaling with the size of the 353 network prevents networks from growing to to the sizes necessary for 354 many LLN applications when faced with the memory constraints devices 355 in such applications exhibit. Similarly, scaling with the network 356 density precludes dense deployments. However, as many low-power and 357 lossy networks behave principally as data collection networks and 358 principally communicate through routers to data collection points in 359 the larger Internet, scaling with the number of such collection 360 points is reasonable. Protocols whose state scales with the number 361 of destinations pass. 363 More precisely, routing table size scaling with O(N) or O(L) fails. 364 A table that scales O(D) (assuming no N or L) passes. 366 4.3. Loss Response 368 In low power and lossy networks, links routinely come and go due to 369 being close to the SINR threshold. It is important that link churn 370 not trigger unnecessary responses by the routing protocol. This 371 point is stressed in all the application requirement documents, 372 pointing to the need to localize response to link failures with no 373 triggering of global network re-optimization, whether for reducing 374 traffic or for maintaining low route convergence times 375 ([I-D.ietf-roll-home-routing-reqs], 376 [I-D.ietf-roll-urban-routing-reqs], and 377 [I-D.ietf-roll-indus-routing-reqs]). The industrial routing 378 requirements draft states that protocols must be able to "recompute 379 paths based on underlying link characteristics which may change 380 dynamically", as well as reoptimize when the device set changes to 381 maintain service requirements. The protocol should also "always be 382 in the process of optimizing the system in response to changing link 383 statistics." Protocols with these properties should take care not to 384 require global updates. 386 A protocol which requires many link changes to propagate across the 387 entire network fails. Protocols which constrain the scope of 388 information propagation to only when they affect routes to active 389 destinations, or to local neighborhoods, pass. Protocols which allow 390 proactively path maintenance pass if the choice of which paths to 391 maintain is user-specified. 393 More precisely, loss responses that require O(N) transmissions fail, 394 while responses that can rely on O(1) local broadcasts or O(D) route 395 updates pass. 397 4.4. Control Cost 399 Battery-operated devices are a critical component of all three 400 application spectrums, and as such special emphasis is placed on 401 minimizing power consumption to achieve long battery lifetime, 402 [I-D.ietf-roll-home-routing-reqs], with multi-year deployments being 403 a common case [I-D.ietf-roll-indus-routing-reqs]. In terms of 404 routing structure, any proposed LLN routing protocol ought to support 405 the autonomous organization and configuration of the network at the 406 lowest possible energy cost [I-D.ietf-roll-urban-routing-reqs]. 408 All routing protocols must transmit additional data to detect 409 neighbors, build routes, transmit routing tables, or otherwise 410 conduct routing. As low-power wireless networks can have very low 411 data rates, protocols which require a minimum control packet rate can 412 have unbounded control overhead. This is particularly true for 413 event-driven networks, which only report data when certain conditions 414 are met. Regions of a network which never meet the condition can be 415 forced to send significant control traffic even when there is no data 416 to send. For these use cases, hard-coded timing constants are 417 unacceptable, because they imply a prior knowledge of the expected 418 data rate. 420 Of course, protocols require the ability to send at least a very 421 small amount of control traffic, in order to discover a topology. 422 But this bootstrapping discovery and maintenance traffic should be 423 small: communicating once an hour is far more reasonable than 424 communicating once a second. So while control traffic should be 425 bounded by data traffic, it requires some leeway to bootstrap and 426 maintain a long-lived yet idle network. 428 The control cost criterion is a necessary but not sufficient 429 condition for a protocol to be a viable routing protocol for LLNs. 430 Protocols not meeting this bound are unacceptable for use in this 431 environment; however, there may be protocols which receive a "pass" 432 for this criterion and yet are also unsuitable. 434 In the case of control traffic, the communication rate (sum of 435 transmissions and receptions at a node) is a better measure than the 436 transmission rate (since energy is consumed for both transmissions 437 and receptions). Controlling the transmission rate is insufficient, 438 as it would mean that the energy cost (sum of transmission and 439 receptions) of control traffic could grow with O(L). 441 A protocol fails the control cost criterion if its per-node control 442 traffic (transmissions plus receptions) rate is not bounded by the 443 data rate plus a small constant. For example, a protocol using a 444 beacon rate only passes if it can be turned arbitrarily low, in order 445 to match the data rate. Furthermore, packet losses necessitate that 446 the control traffic may scale within a O(log(L)) factor of the data 447 rate. Meaning, if R is the data rate and e is the small constant, 448 then a protocol's control traffic must be on the order of O(R log(L) 449 + e) to pass this criteria. The details of why O(log(L)) is 450 necessary are in Appenix B. 452 4.5. Link and Node Cost 454 These two criteria specify how a protocol chooses routes for data 455 packets to take through the network. Classical routing algorithms 456 typically acknowledge the differing costs of paths and may use a 457 shortest path algorithm to find paths. This is a requirement for low 458 power networks, as links must be evaluated as part of an objective 459 function across various metric types, such as minimizing latency and 460 maximizing reliability [I-D.ietf-roll-indus-routing-reqs]. 462 However, in low power networks it is also desirable to account for 463 the cost of forwarding through particular routers. Applications 464 require node or parameter constrained routing, which takes into 465 account node properties and attributes such as power, memory, and 466 battery life that dictate a router's willingness or ability to route 467 other packets. Home routing requirements note that devices will vary 468 in their duty cycle, and that routing protocols should prefer nodes 469 with permanent power [I-D.ietf-roll-home-routing-reqs]. The urban 470 requirements note that routing protocols may wish to take advantage 471 of differing data processing and management capabilities among 472 network devices [I-D.ietf-roll-urban-routing-reqs]. Finally, 473 industrial requirements cite differing lifetime requirements as an 474 important factor to account for [I-D.ietf-roll-indus-routing-reqs]. 475 Node cost refers to the ability for a protocol to incorporate router 476 properties into routing metrics and use node attributes for 477 constraint-based routing. 479 A "pass" indicates that the protocol contains a mechanism allowing 480 these considerations to be considered when choosing routes. 482 5. Routing Protocol Taxonomy 484 Routing protocols broadly fall into two classes: link-state and 485 distance-vector. 487 A router running a link-state protocol first establishes adjacency 488 with its neighbors and then reliably floods the local topology 489 information in the form of a Link State Advertisement packet. The 490 collection of LSAs constitutes the Link State Database (LSDB) that 491 represents the network topology, and routers synchronize their LSDBs. 492 Thus each node in the network has a complete view of the network 493 topology. Each router uses its LSDB to compute a routing table where 494 each entry (reachable IP destination address) points to the next hop 495 along the shortest path according to some metric. Link state 496 protocols (such as OSPF and IS-IS) support the concept of area 497 (called "level" for IS-IS) whereby all the routers in the same area 498 share the same view (they have the same LSDB) and areas are 499 interconnected by border routers according to specific rules that 500 advertise IP prefix reachability between areas. 502 A distance vector protocol exchanges routing information rather than 503 topological information. A router running a distance vector protocol 504 exchanges information with its "neighbors" with which it has link 505 layer connectivity. Tunneling and similar mechanisms can virtualize 506 link layer connectivity to allow neighbors that are multiple layer 2 507 hops away. Rather than a map of the network topology from which each 508 router can calculate routes, a distance vector protocol node has 509 information on what routes its neighbors have. Each node's set of 510 available routes is the union of its neighbors routes plus a route to 511 itself. In a distance vector protocol, nodes may only advertise 512 routes which are in use, enabling on-demand discovery. In comparison 513 to link state protocols, distance vector protocols have the advantage 514 of only requiring neighbor routing information, but also have 515 corresponding limitations which protocols must address, such as 516 routing loops, count to infinity, split horizon, and slow convergence 517 times. Furthermore, routing constraints are difficult to enforce 518 with distance vector protocols. 520 Neighbor discovery is a critical component of any routing protocol. 521 It enables a protocol to learn about which other nodes are nearby and 522 which it can use as the next hop for routes. As neighbor discovery 523 is a key component of many protocols, several general protocols and 524 protocol mechanisms have been designed to support it. A protocol's 525 neighbor set is defined by how many "hops" away the set reaches. For 526 example, the 1-hop neighbor set of a node is all nodes it can 527 directly communicate with at the link layer, while the 2-hop neighbor 528 set is its own 1-hop neighbor set and the 1-hop neighbor sets of all 529 of its 1-hop neighbors. 531 Because nodes often have very limited resources for storing routing 532 state, protocols cannot assume that they can store complete neighbor 533 information. For example, a node with 4kB of RAM cannot store full 534 neighbor state when it has 1000 other nodes nearby. This means that 535 ROLL protocols must have mechanisms to decide which of many possible 536 neighbors they monitor as routable next hops. For elements such as 537 2-hop neighborhoods, these decisions can have a significant impact on 538 the topology that other nodes observe, and therefore may require 539 intelligent logic to prevent effects such as network partitions. 541 5.1. Protocols Today 543 Wired networks draw from both approaches. OSPF or IS-IS, for 544 example, are link-state protocols, while RIP is a distance-vector 545 protocol. 547 MANETs similarly draw from both approaches. OLSR is a link-state 548 protocol, while AODV and DYMO are distance vector protocols. The 549 general consensus in core networks is to use link state routing 550 protocols as IGPs for a number of reasons: in many cases having a 551 complete network topology view is required to adequately compute the 552 shortest path according to some metrics. For some applications such 553 as MPLS Traffic Engineering it is even required to have the knowledge 554 of the Traffic Engineering Database for constraint based routing. 556 Furthermore link state protocols typically have superior convergence 557 speeds (ability to find an alternate path in case of network element 558 failure), are easier to debug and troubleshoot, and introduce less 559 control packet overhead than distance vector protocols. In contrast, 560 distance vector protocols are simpler, require less computation, and 561 have smaller storage requirements. Most of these tradeoffs are 562 similar in wireless networks, with one exception. Because wireless 563 links can suffer from significant temporal variation, link state 564 protocols can have higher traffic loads as topology changes must 565 propagate globally, while in a distance vector protocol a node can 566 make local routing decisions with no effect on the global routing 567 topology. 569 One protocol, DSR, does not easily fit into one of these two classes. 570 Although it is a distance vector protocol, DSR has several properties 571 that make it differ from most other protocols in this class. We 572 examine these differences in our discussion of DSR. 574 The next two sections summarize several well established routing 575 protocols. The table below shows, based on the criteria described 576 above, whether these protocols meet ROLL criteria. Appendix A 577 contains the reasoning behind each value in the table. 579 Protocol Table Loss Control Link Cost Node Cost 580 OSPF/IS-IS fail fail fail pass fail 581 OLSRv2 fail fail ? pass pass 582 TBRPF fail pass fail pass ? 583 RIP pass fail pass ? fail 584 AODV pass fail pass fail fail 585 DYMO[-low] pass fail pass ? fail 586 DSR fail pass pass fail fail 588 6. Link State Protocols 590 6.1. OSPF & IS-IS 592 OSPF (specified in [RFC2328] for IPv4 and in [RFC2740] for IPv6)) is 593 a link state protocol designed for routing within an Internet 594 Autonomous System (AS). OSPF provides the ability to divide a 595 network into areas, which can establish a routing hierarchy. The 596 topology within an area is hidden from other areas and IP prefix 597 reachability across areas (inter-area routing) is provided using 598 summary LSAs. The hierarchy implies that there is a top-level 599 routing area (the backbone area) which connects other areas. Areas 600 may be connected to the back-bone area through a virtual link. OSPF 601 maintains routing adjacencies by sending hello messages. OSPF 602 calculates the shortest path to a node using link metrics (that may 603 reflect the link bandwidth, propagation delay, ...). OSPF Traffic 604 Engineering (OSPF-TE, [RFC3630]) extends OSPF to include information 605 on reservable, unreserved, and available bandwidth. 607 IS-IS (specified in [RFC1142]) is similar in many respects to OSPF, 608 but as a descendent of the OSI protocol suite differs in some places 609 such as the way areas are defined and used. However, routing 610 adjacencies are also maintained by local propagation of the LSDB, and 611 a shortest path computation is used over a metric space which may 612 measure delay, errors, or other link properties. 614 6.2. OLSR & OLSRv2 616 Optimized Link State Routing (OLSR) (see [RFC3626] and 617 [I-D.ietf-manet-olsrv2]) is a link state routing protocol for 618 wireless mesh networks. OLSR routers flood link state advertisement 619 packets throughout the entire network, such that each node has a map 620 of the mesh topology. Because link variations can lead to heavy 621 flooding traffic when using a link state approach, OLSR establishes a 622 topology for minimizing this communication and imposes minimum time 623 interval between two successive control transmissions by a router. 624 Each node maintains a set of nodes called its Multipoint Relays 625 (MPR), which is a subset of the one-hop neighbors whose connectivity 626 covers the two-hop neighborhood. Each node that is an MPR maintains 627 a set called its MPR selectors, which are nodes that have chosen it 628 to be an MPR. 630 OLSR uses these two sets to apply three optimizations. First, only 631 MPRs generate link state information. Second, nodes use MPRs to 632 limit the set of nodes that forward link state packets. Third, an 633 MPR, rather than advertise all of its links, can advertise only links 634 to its MPR selectors. Together, these three optimizations can 635 greatly reduce the control traffic in dense networks, as the number 636 of MPRs should not increase significantly as a network becomes 637 denser. 639 OLSR selects routes based on hop counts, and assumes an underlying 640 protocol that determines whether a link exists between two nodes. 641 OLSR's optimized flooding allows it to quickly adapt to and propagate 642 topology changes. 644 OLSR is closely related to clustering algorithms in the wireless 645 sensor networking literature, in which cluster heads are elected such 646 that routing occurs over links between cluster heads and all other 647 nodes are leafs that communicate to a cluster head. 649 6.3. TBRPF 651 Topology Dissemination Based on Reverse Path Forwarding (see 652 [RFC3684]) is another proactive link state protocol. TBRPF computes 653 a source tree, which provides routes to all reachable nodes. It 654 reduces control packet overhead by having nodes only transmit a 655 subset of their source tree as well as by using differential updates. 657 The major difference between TBRPF and OLSR is the routing data that 658 nodes advertise and who chooses to aggregate information. In OLSR, 659 nodes select neighbors to be MPRs and advertise their link state for 660 them; in TBRPF, nodes elect themselves to advertise relevant link 661 state based on whether it acts as a next hop. 663 7. Distance Vector protocols 665 7.1. RIP 667 The Routing Information Protocol (RIP) (defined in [RFC2453]) 668 predates OSPF. As it is a distance vector protocol, routing loops 669 can occur and considerable work has been done to accelerate 670 convergence since the initial RIP protocols were introduced. RIP 671 measures route cost in terms of hops, and detects routing loops by 672 observing a route cost approach infinity where "infinity" is referred 673 to as a maximum number of hops. RIP is typically not appropriate for 674 situations where routes need to be chosen based on real-time 675 parameters such as measured delay, reliability, or load or when the 676 network topology needs to be known for route computation. 678 "Triggered RIP" (defined in [RFC2091]) was originally designed to 679 support "on-demand" circuits. The aim of triggered RIP is to avoid 680 systematically sending the routing database on regular intervals. 681 Instead, triggered RIP sends the database when there is a routing 682 update or a next hop adjacency change: once neighbors have exchanged 683 their routing database, only incremental updates need to be sent. 684 Because incremental updates cannot depend on periodic traffic to 685 overcome loses, triggered RIP uses acknowledgment based mechanisms 686 for reliable delivery. 688 7.2. Ad-hoc On Demand Vector Routing (AODV) 690 AODV (specified in [RFC3561]) is a distance vector protocol intended 691 for MANETs. When one AODV node requires a route to another, it 692 floods a request in the network to discover a route. A depth-scoped 693 flooding process avoids discovery from expanding to the most distant 694 regions of the network that are in the opposite direction of the 695 destination. AODV chooses routes that have the minimum hop count. 697 If an AODV route request reaches a node that has a route to the 698 destination (this includes the destination itself), that node sends a 699 reply along the reverse route. All nodes along the reverse route can 700 cache the route. When routes break due to topology changes, AODV 701 floods error messages and issues a new request. Because AODV is on- 702 demand it only maintains routes for active nodes. When a link 703 breaks, AODV issues a Route Error (RERR) and a new route request 704 message (RREQ), with a higher sequence number so nodes do not respond 705 from their route caches. These packets can flood the entire network. 707 7.3. DYMO 709 Dynamic Mobile On-Demand routing (DYMO) ([I-D.ietf-manet-dymo]) is an 710 evolution of AODV. The basic functionality is the same, but it has 711 different packet formats, handling rules, and supports path 712 accumulation. Path accumulation allows a single DYMO route request 713 to generate routes to all nodes along the route to that destination. 714 Like AODV, DYMO uses a distance value as its routing metric which 715 must be at least the hop count, but allows DYMO to represent link 716 costs. Like AODV, on link breaks DYMO issues a new route request 717 message (RREQ), with a higher sequence number so nodes do not respond 718 from their route caches. Correspondingly, a route request can flood 719 the entire network. 721 7.4. DSR 723 Dynamic Source Routing ([RFC4728]) is a distance vector protocol, but 724 a DSR packet source explicitly specifies the route for each packet. 725 Because the route is determined at a single place -- the source -- 726 DSR does not require sequence numbers or other mechanisms to prevent 727 routing loops, as there is no problem of inconsistent routing tables. 728 Unlike AODV and DYMO, by pushing state into packet headers, DSR does 729 not require per-destination routing state. Instead, a node 730 originating packets only needs to store a spanning tree of the part 731 of the network it is communicating with. 733 8. Neighbor Discovery 735 A limit on maintained routing state (light footprint) prevents ROLL 736 protocols from assuming they know all 1-hop, 2-hop, or N-hop 737 neighbors. For this reason, while protocols such as MANET-NHDP 738 ([I-D.ietf-manet-nhdp]) and IPv6's neighbor discovery ([RFC4861]) 739 provide basic mechanisms for discovering link-layer neighbors, not 740 all of their features are relevant. This section describes these two 741 protocols, their capabilities, and how ROLL protocols could leverage 742 them. 744 8.1. IPv6 Neighbor Discovery 746 IPv6 neighbor discovery provides mechanisms for nodes to discover 747 single-hop neighbors as well as routers that can forward packets past 748 the local neighborhood. There is an implicit assumption that the 749 delegation of whether a node is a router or not is static (e.g., 750 based on a wired topology). The fact that all routers must respond 751 to a Router Solicitation requires that the number of routers with a 752 1-hop neighborhood is small, or there will be a reply implosion. 753 Furthermore, IPv6 neighbor discovery's support of address 754 autoconfiguration assumes address provisioning, in that addresses 755 reflect the underlying communication topology. IPv6 neighbor 756 discovery does not consider asymmetric links. Nevertheless, it may 757 be possible to extend and adapt IPv6's mechanisms to wireless in 758 order to avoid response storms and implosions. 760 8.2. MANET-NHDP 762 The MANET Neighborhood Discovery Protocol (MANET-NHDP) provides 763 mechanisms for discovering a node's symmetric 2-hop neighborhood. It 764 maintains information on discovered links, their interfaces, status, 765 and neighbor sets. MANET-NHDP advertises a node's local link state; 766 by listening to all of its 1-hop neighbor's advertisements, a node 767 can compute its 2-hop neighborhood. MANET-NHDP link state 768 advertisements can include a link quality metric. MANET-NHDP's node 769 information base includes all interface addresses of each 1-hop 770 neighbor: for low-power nodes, this state requirement can be 771 difficult to support. 773 9. Security Considerations 775 This document presents, considers, and raises no security 776 considerations. 778 10. IANA Considerations 780 This document includes no request to IANA. 782 11. Acknowledgements 784 The authors would like to thank all the members of the ROLL working 785 group for their valuable comments, and the chairs for their helpful 786 guidance. 788 We are also indebted to the Sensor Network Architecture group at 789 Berkeley for contributing their helpful analysis: Prabal Dutta, 790 Rodrigo Fonseca, Xiaofan Jiang, Jaein Jeong, Jorge Ortiz, and Jay 791 Tanega. 793 12. References 795 12.1. Normative References 797 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 798 Requirement Levels", BCP 14, RFC 2119, March 1997. 800 12.2. Informative References 802 [I-D.ietf-manet-dymo] 803 Chakeres, I. and C. Perkins, "Dynamic MANET On-demand 804 (DYMO) Routing", draft-ietf-manet-dymo-16 (work in 805 progress), December 2008. 807 [I-D.ietf-manet-nhdp] 808 Clausen, T., Dearlove, C., and J. Dean, "MANET 809 Neighborhood Discovery Protocol (NHDP)", 810 draft-ietf-manet-nhdp-07 (work in progress), July 2008. 812 [I-D.ietf-manet-olsrv2] 813 Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized 814 Link State Routing Protocol version 2", 815 draft-ietf-manet-olsrv2-07 (work in progress), July 2008. 817 [I-D.ietf-roll-home-routing-reqs] 818 Porcu, G., "Home Automation Routing Requirements in Low 819 Power and Lossy Networks", 820 draft-ietf-roll-home-routing-reqs-06 (work in progress), 821 November 2008. 823 [I-D.ietf-roll-indus-routing-reqs] 824 Networks, D., Thubert, P., Dwars, S., and T. Phinney, 825 "Industrial Routing Requirements in Low Power and Lossy 826 Networks", draft-ietf-roll-indus-routing-reqs-03 (work in 827 progress), December 2008. 829 [I-D.ietf-roll-urban-routing-reqs] 830 Dohler, M., Watteyne, T., Winter, T., Barthel, D., 831 Jacquenet, C., Madhusudan, G., and G. Chegaray, "Urban 832 WSNs Routing Requirements in Low Power and Lossy 833 Networks", draft-ietf-roll-urban-routing-reqs-03 (work in 834 progress), January 2009. 836 [I-D.irtf-dtnrg-prophet] 837 Lindgren, A. and A. Doria, "Probabilistic Routing Protocol 838 for Intermittently Connected Networks", 839 draft-irtf-dtnrg-prophet-01 (work in progress), 840 November 2008. 842 [I-D.thubert-tree-discovery] 843 Thubert, P., Bontoux, C., Montavont, N., and B. McCarthy, 844 "Nested Nemo Tree Discovery", 845 draft-thubert-tree-discovery-07 (work in progress), 846 August 2008. 848 [RFC1142] Oran, D., "OSI IS-IS Intra-domain Routing Protocol", 849 RFC 1142, February 1990. 851 [RFC2091] Meyer, G. and S. Sherry, "Triggered Extensions to RIP to 852 Support Demand Circuits", RFC 2091, January 1997. 854 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 856 [RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453, 857 November 1998. 859 [RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", 860 RFC 2740, December 1999. 862 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 863 Demand Distance Vector (AODV) Routing", RFC 3561, 864 July 2003. 866 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing 867 Protocol (OLSR)", RFC 3626, October 2003. 869 [RFC3630] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering 870 (TE) Extensions to OSPF Version 2", RFC 3630, 871 September 2003. 873 [RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology 874 Dissemination Based on Reverse-Path Forwarding (TBRPF)", 875 RFC 3684, February 2004. 877 [RFC3963] Devarapalli, V., Wakikawa, R., Petrescu, A., and P. 878 Thubert, "Network Mobility (NEMO) Basic Support Protocol", 879 RFC 3963, January 2005. 881 [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source 882 Routing Protocol (DSR) for Mobile Ad Hoc Networks for 883 IPv4", RFC 4728, February 2007. 885 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 886 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 887 September 2007. 889 [RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol 890 Specification", RFC 5050, November 2007. 892 [RFC5326] Ramadas, M., Burleigh, S., and S. Farrell, "Licklider 893 Transmission Protocol - Specification", RFC 5326, 894 September 2008. 896 Appendix A. Routing protocol scalability analysis 898 This aim of this Appendix is to provide the details for the analysis 899 routing scalability analysis. 901 "OSPF & IS-IS" 903 OSPF floods link state through a network. Each router must receive 904 this complete link set. OSPF fails the table size criterion because 905 it requires each router to discover each link in the network, for a 906 total routing table size which is O(N * L). This also causes it to 907 fail the control cost criterion, since this information must be 908 propagated. Furthermore, changes in the link set require re-flooding 909 the network link state even if the changed links were not being used. 910 Since link state changes in wireless networks are often uncorrelated 911 with data traffic and are instead caused by external (environmental) 912 factors, this causes OSPF to fail both the control cost and loss 913 response criteria. OSPF routers can impose policies on the use of 914 links and can consider link properties (Type of Service), as the cost 915 associated with an edge is configurable by the system administrator 916 [RFC2328], so receive a pass for link cost. However, there is no way 917 to associate metrics with routers (as costs are only applied to 918 outgoing interfaces, i.e. edges) when computing paths, and so fails 919 the node cost criteria. While [RFC3630] discusses paths that take 920 into account node attributes, it specifically states that no known 921 algorithm or mechanism currently exists for incoporating this into 922 the OSPF RFC. 924 IS-IS receives the same results as OSPF, because it maintains a 925 consistent LSDB using similar mechanisms, and can account for link 926 costs but not router costs in its shortest path computation. 928 "OLSRv2" 930 OLSRv2 is a proactive link state protocol, flooding link state 931 information through a set of multipoint relays (MPRs). Routing state 932 includes 1-hop neighbor information for each node in the network, 933 1-hop and 2-hop information for neighbors (for MPR selection), and a 934 routing table (consisting of destination, and next hop), resulting in 935 state proportional to network size and density (O(N*L + L^2)), and 936 failing the table scalability criterion. 938 Unacceptable control traffic overhead may arise from flooding and 939 maintenance. HELLO messages are periodically broadcast local beacon 940 messages, but TC messages spread topology information throughout the 941 network (using MPRs). As such, control traffic is proportional to 942 O(N^2). MPRs reduce this load to O(N^2 / L). As the number of MPRs 943 is inversely proportional to the density of the network and L is 944 bounded by N, this means control traffic is at best proportional to 945 O(N). 947 Fisheye routing is a technique to reduce the frequency routing 948 updates as the routing update propagates away from its source. This 949 has the potential to reduce the control overhead to acceptable 950 levels, and it is possible to implement this technique without 951 violating the specification because the specification does not 952 require that all updates be sent with the same frequency. However, 953 there is no specification of how this should be accomplished. Thus, 954 OLSR receives a "?" for the control traffic criterion. Fisheye 955 routing does not alter the table size, so it does not modify OLSR's 956 failure of the table scalability criterion. 958 Furthermore, changes in the link set may require re-flooding the 959 network link state even if those links were not being used by 960 routing. While OLSRv2 limits the rates of such floods by imposing a 961 minimum fixed interval between floods, this interval is independent 962 of the data rate. OLSR therefore fails the loss response criterion. 964 OLSR allows for specification of link quality, and also provides a 965 'Willingness' metric to symbolize node cost, giving it a pass for 966 both those criteria. 968 "TBRPF" 970 As a link state protocol where each node maintains a database of the 971 entire network topology, TBRPF's routing table size scales with 972 network size and density, leading to table sizes which are O(N * L) 973 when a node receives disjoint link sets from its neighbors. This 974 causes the protocol to fail the table size criterion. The protocol's 975 use of differential updates should allow both fast response time and 976 incremental changes once the distributed database of links has been 977 established. Differential updates are only used to reduce response 978 time to changing network conditions, not to reduce the amount of 979 topology information sent, since each node will periodically send 980 their piece of the topology. As a result, TBRPF fails the control 981 overhead criterion. However, its differential updates triggered by 982 link failure do not immediately cause a global re-flooding of state 983 (but only to affected routers) [RFC3684], leading to a pass for loss 984 response. 986 TBRPF has a flexible neighbor management layer which enables it to 987 incorporate various types of link metrics into its routing decision 988 by enabling a USE_METRIC flag [RFC3684]. As a result, it receives a 989 pass for link cost. It also provides a mechanism whereby routers can 990 maintain multiple link metrics to a single neighbor, some of which 991 can be advertised by the neighbor router [RFC3684]. Although the RFC 992 does not specify a policy for using these values, developing one 993 could allow TBRPF to satisfy this requirement, leading to a ? for the 994 node cost requirement. 996 "RIP" 998 RIP is a distance vector protocol: all routers maintain a route to 999 all other routers. Routing table size is therefore O(N). However, 1000 if destinations are known apriori, table size can be reduced to O(D), 1001 resulting in a pass for table scalability. While standard RIP 1002 requires each node broadcast a beacon per period, and that updates 1003 must be propagated by affected nodes, triggered RIP only sends 1004 updates when network conditions change in response to the data path, 1005 so RIP passes the control cost criterion. Loss triggers updates, 1006 only propagating if part of a best route, but even if the route is 1007 not actively being used, resulting in a fail for loss response. The 1008 rate of triggered updates is throttled, and these are only 1009 differential updates, yet this still doesn't account for other 1010 control traffic (or tie it to data rate) or prevent the triggered 1011 updates from being flooded along non-active paths. [RFC2453] 1013 RIP receives a ? for link cost because while current implementations 1014 focus on hop count and that is the metric used in [RFC2453], the RFC 1015 also mentions that more complex metrics such as differences in 1016 bandwidth and reliability could be used. However, the RFC also 1017 states that real-time metrics such as link-quality would create 1018 instability and the concept of node cost only appears as metrics 1019 assigned to external networks. While RIP has the concept of a 1020 network cost, it is insufficient to describe node properties and so 1021 RIP fails the node cost criterion.. 1023 "AODV" 1025 AODV table size is a function of the number of communicating pairs in 1026 the network, scaling with O(D). This is acceptable and so AODV 1027 passes the table size criterion. As an on-demand protocol, AODV does 1028 not generate any traffic until data is sent, and so control traffic 1029 is correlated with the data and so it receives a pass for control 1030 traffic. When a broken link is detected, AODV will use a precursor 1031 list maintained for each destination to inform downstream routers 1032 (with a RERR) of the topology change. However, the RERR message is 1033 forwarded by all nodes that have a route that uses the broken link, 1034 even if the route is not currently active, leading to a fail for loss 1035 response [RFC3561]. 1037 AODV fails the link cost criterion because the only metric used is 1038 hop count, and this is hardcoded in the route table entry, according 1039 to the RFC [RFC3561]. It fails the node cost requirement because 1040 there is no way for a router to indicate its [lack of] willingness to 1041 route while still adhering to the RFC. 1043 "DYMO/DYMO-low" 1045 The design of DYMO shares much with AODV, with some changes to remove 1046 precursor lists and compact various messages. It still passes the 1047 table size criterion because it only maintains routes requested by 1048 RREQ messages, resulting in O(D) table size. Control traffic (RREQ, 1049 RREP, and RREQ) are still driven by data, and hence DYMO passes the 1050 control cost criterion. However, RERR messages are forwarded by any 1051 nodes that have a route using the link, even if inactive, leading to 1052 a fail of the loss reponse criterion [I-D.ietf-manet-dymo]. 1054 DYMO indicates that the "distance" of a link can vary from 1-65535 1055 [I-D.ietf-manet-dymo], leading to a ? in link cost. While additional 1056 routing information can be added DYMO messages, there is no mention 1057 of node properties, leading to a fail in node cost. 1059 "DSR" 1061 DSR performs on-demand route discovery, and source routing of 1062 packets. It maintains a source route for all destinations, and also 1063 a blacklist of all unidirectional neighbor links [RFC4728], leading 1064 to a total table size of O(D + L), failing the table size criterion. 1065 Control traffic is completely data driven, and so DSR receives a pass 1066 for this criterion. Finally, a transmission failure only prompts an 1067 unreachable destination to be sent to the source of the message, 1068 passing the loss response criterion. 1070 DSR fails the link cost criterion because its source routes are 1071 advertised only in terms of hops, such that all advertised links are 1072 considered equivalent. DSR also fails the node cost criterion 1073 because a node has no way of indicating its willingness to serve as a 1074 router and forward messages. 1076 Appendix B. Logarithmic scaling of control cost 1078 To satisfy the control cost criterion, a protocol's control traffic 1079 communication rate must be bounded by the data rate, plus a small 1080 constant. That is, if there is a data rate R, the control rate must 1081 O(R + e), where e is a very small constant (epsilon). Furthermore, 1082 the control rate may grow logarithmically with the size of the local 1083 neighborhood L. Note that this is a bound: it represents the most 1084 traffic a protocol may send, and good protocols may send much less. 1085 So the control rate is bounded by O(R log(L)) + e. 1087 The logarithmic factor comes from the fundamental limits of any 1088 protocol that maintains a communication rate. For example, consider 1089 e, the small constant rate of communication traffic allowed. Since 1090 this rate is communication, to maintain O(e), then only one in L 1091 nodes may transmit per time interval defined by e: that one node has 1092 a transmission, and all other nodes have a reception, which prevents 1093 them from transmitting. However, wireless networks are lossy. 1094 Suppose that the network has a 10% packet loss rate. Then if L=10, 1095 the expectation is that one of the nodes will drop the packet. Not 1096 hearing a transmission, it will think it can transmit. This will 1097 lead to 2 transmissions. If L=100, then one node will not hear the 1098 first two transmissions, and there will be 3. The number of 1099 transmissions, and the communication rate, will grow with O(log(L)). 1101 This logarithmic bound can be prevented through explicit coordination 1102 (e.g., leader election), but such approaches assumes state and 1103 control traffic to elect leaders. As a logarithmic factor in terms 1104 of density is not a large stumbling or major limitation, allowing the 1105 much greater protocol flexibility it enables is worth its small cost. 1107 Authors' Addresses 1109 Philip Levis 1110 Stanford University 1111 358 Gates Hall, Stanford University 1112 Stanford, CA 94305-9030 1113 USA 1115 Email: pal@cs.stanford.edu 1117 Arsalan Tavakoli 1118 UC Berkeley 1119 Soda Hall, UC Berkeley 1120 Berkeley, CA 94707 1121 USA 1123 Email: arsalan@eecs.berkeley.edu 1125 Stephen Dawson-Haggerty 1126 UC Berkeley 1127 Soda Hall, UC Berkeley 1128 Berkeley, CA 94707 1129 USA 1131 Email: stevedh@cs.berkeley.edu