idnits 2.17.1 draft-baccelli-multi-hop-wireless-communication-06.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: ---------------------------------------------------------------------------- No issues found here. 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 -- The document date (Jul 29, 2011) is 4655 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC4903' is defined on line 347, but no explicit reference was found in the text == Unused Reference: 'IPev' is defined on line 361, but no explicit reference was found in the text Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 MANET Autoconfiguration (Autoconf) E. Baccelli 3 Internet-Draft INRIA 4 Intended status: Informational C. Perkins 5 Expires: January 30, 2012 Tellabs 6 Jul 29, 2011 8 Multi-hop Ad Hoc Wireless Communication 9 draft-baccelli-multi-hop-wireless-communication-06 11 Abstract 13 This document describes some characteristics of communication between 14 nodes in a multi-hop ad hoc wireless network. These are not 15 requirements in the sense usually understood as applying to 16 formulation of a requirements document. Nevertheless, protocol 17 engineers and system analysts involved with designing solutions for 18 ad hoc networks must maintain awareness of these characteristics. 20 Status of This Memo 22 This Internet-Draft is submitted to IETF in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at http://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on January 30, 2012. 37 Copyright Notice 39 Copyright (c) 2011 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 2. Multi-hop Ad Hoc Wireless Networks . . . . . . . . . . . . . . 3 56 3. Common Packet Transmission Characteristics in Multi-hop Ad 57 Hoc Wireless Networks . . . . . . . . . . . . . . . . . . . . . 3 58 3.1. Asymmetry, Time-Variation, and Non-Transitivity . . . . . . 4 59 3.2. Radio Range and Wireless Irregularities . . . . . . . . . . 5 60 4. Alternative Terminology . . . . . . . . . . . . . . . . . . . . 7 61 5. Security Considerations . . . . . . . . . . . . . . . . . . . . 8 62 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8 63 7. Informative References . . . . . . . . . . . . . . . . . . . . 8 64 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . . 9 66 1. Introduction 68 The goal of this document is to describe some aspects of multi-hop ad 69 hoc wireless communication. Experience gathered with [RFC3626] 70 [RFC3561] [RFC3684] [RFC4728] [RFC5449] [RFC2501] [DoD01] shows that 71 this type of communication presents specific challenges. This 72 document briefly describes these challenges, which one should 73 maintain awareness of, when designing Internet protocols for ad hoc 74 networks. 76 2. Multi-hop Ad Hoc Wireless Networks 78 For the purposes of this document, a multi-hop ad hoc wireless 79 network will be considered to be a collection of devices that each 80 have a radio transceiver, that are using the same physical and medium 81 access protocols, that are moreover configured to self-organize and 82 provide store-and-forward functionality on top of these protocols as 83 needed to enable communications. The devices providing network 84 connectivity are considered to be routers. Other non-routing 85 wireless devices, if present in the ad hoc network, are considered to 86 be "end-hosts". The considerations in this document apply equally to 87 routers or end-hosts; we use the term "node" to refer to any such 88 network device in the ad hoc network. 90 An example of multi-hop ad hoc wireless network is a wireless 91 community network such as Funkfeuer [FUNKFEUER] or Freifunk 92 [FREIFUNK], that consists in routers running OLSR [RFC3626] on 802.11 93 in ad hoc mode with the same ESSID at link layer. Multi-hop ad hoc 94 wireless networks may also run on link layers other than 802.11. 96 Note however that simple hosts communicating through an access point 97 with 802.11 in infrastructure mode do not form a multi-hop ad hoc 98 wireless network, since the central role of the access point is 99 determined a priori, and since nodes other than the access point do 100 not generally provide store-and-forward functionality. 102 3. Common Packet Transmission Characteristics in Multi-hop Ad Hoc 103 Wireless Networks 105 Let A and B be two nodes in a multi-hop ad hoc wireless network N. 106 Suppose that, when node A transmits a packet through its interface on 107 network N, that packet is correctly received by node B without 108 requiring storage and/or forwarding by any other device. We will 109 then say that B "hears" packets from A. Note that therefore, when B 110 can hear IP packets from A, the TTL of the IP packet heard by B will 111 be precisely the same as it was when A transmitted that packet. 113 Let S be the set of nodes that can hear packets transmitted by node A 114 through its interface on network N. The following section gathers 115 common characteristics concerning packet transmission over such 116 networks, which were observed through experience with [RFC3626] 117 [RFC3561] [RFC3684] [RFC4728] [RFC5449]. 119 3.1. Asymmetry, Time-Variation, and Non-Transitivity 121 First, there is no guarantee that a node C within S can, 122 symmetrically, send IP packets directly to node A. In other words, 123 even though C can "hear" packets from A (since it is a member of set 124 S), there is no guarantee that A can "hear" packets from C. Thus, 125 multi-hop ad hoc wireless communications may be "asymmetric". Such 126 cases are not uncommon. 128 Second, there is no guarantee that, as a set, S is at all stable, 129 i.e. the membership of set S may in fact change at any rate, at any 130 time. Thus, multi-hop ad hoc wireless communications may be "time- 131 variant". Such variations are not unusual in multi-hop ad hoc 132 wireless networks due to variability of the wireless medium, and to 133 node mobility. 135 Now, conversely, let V be the set of nodes from which A can directly 136 receive packets -- in other words, A can "hear" packets from any node 137 in set V. Suppose that node A is communicating at time t0 through its 138 interface on network N. As a consequence of time variation and 139 asymmetry, we observe that A: 141 1. cannot assume that S = V, 143 2. cannot assume that S and/or V are unchanged at time t1 later than 144 t0. 146 Furthermore, transitivity is not guaranteed over multi-hop ad hoc 147 wireless networks. Indeed, let's assume that, through their 148 respective interfaces within network N: 150 1. node B and node A can hear each other (i.e. node B is a member of 151 sets S and V), and, 153 2. node A and node C can also hear each other (i.e. node C is a also 154 a member of sets S and V). 156 These assumptions do not imply that node B can hear node C, nor that 157 node C can hear node B (through their interface on network N). Such 158 "non-transitivity" is not uncommon on multi-hop ad hoc wireless 159 networks. 161 In a nutshell: multi-hop ad hoc wireless communications can be 162 asymmetric, non-transitive, and time-varying. 164 3.2. Radio Range and Wireless Irregularities 166 Section 3.1 presents an abstract description of some common 167 characteristics concerning packet transmission over multi-hop ad hoc 168 wireless networks. This section describes practical examples, which 169 illustrate the characteristics listed in Section 3.1 as well as other 170 common effects. 172 Wireless communication links are subject to limitations to the 173 distance across which they may be established. The range-limitation 174 factor creates specific problems on multi-hop ad hoc wireless 175 networks. In this context, it is not uncommon that the radio ranges 176 of several nodes partially overlap. Such partial overlap causes 177 communication to be non-transitive and/or asymmetric, as described in 178 Section 3.1. 180 For example, as depicted in Figure 1, it may happen that a node B 181 hears a node A which transmits at high power, whereas B transmits at 182 lower power. In such cases, B can hear A, but A cannot hear B. This 183 examplifies the asymmetry in multi-hop ad hoc wireless communications 184 as defined in Section 3.1. 186 Radio Ranges for Nodes A and B 188 <~~~~~~~~~~~~~+~~~~~~~~~~~~~> 189 | <~~~~~~+~~~~~~> 190 +--|--+ +--|--+ 191 | A |======>| B | 192 +-----+ +-----+ 194 Figure 1: Asymmetric Link example. Node A can communicate with 195 node B, but B cannot communicate with A. 197 Another example, depicted in Figure 2, is known as the "hidden node" 198 problem. Even though the nodes all have equal power for their radio 199 transmissions, they cannot all reach one another. In the figure, 200 nodes A and B can hear each other, and A and C can also hear each 201 other. On the other hand, nodes B and C cannot hear each other. 202 When nodes B and C try to communicate with node A at the same time, 203 their radio signals collide. Node A will only be able to detect 204 noise, and may even be unable to determine the source of the noise. 205 The hidden terminal problem illustrates the property of non- 206 transitivity in multi-hop ad hoc wireless communications as described 207 in Section 3.1. 209 Radio Ranges for Nodes A, B, C 211 <~~~~~~~~~~~~~+~~~~~~~~~~~~~> <~~~~~~~~~~~~~+~~~~~~~~~~~~~> 212 |<~~~~~~~~~~~~~+~~~~~~~~~~~~~>| 213 +--|--+ +--|--+ +--|--+ 214 | B |=======>| A |<=======| C | 215 +-----+ +-----+ +-----+ 217 Figure 2: The hidden node problem. Nodes C and B 218 try to communicate with node A at the same time, 219 and their radio signals collide. 221 Another situation, shown in Figure 3, is known as the "exposed node" 222 problem. In the figure, node A is transmitting (to node B). As 223 shown, node C cannot communicate properly with node D, because of the 224 on-going transmission of node A, polluting C's radio-range. Node C 225 cannot hear D, but node D can hear C because D is outside A's radio 226 range. Node C is then called an "exposed node", because it is 227 exposed to co-channel interference from node A and thereby prevented 228 from exchanging protocol messages to enable transmitting data to node 229 D -- even though the transmission would be successful and would not 230 interfere with the reception of data sent from node A to node B. 232 Radio Ranges for Nodes A, B, C, D 234 <~~~~~~~~~~~~+~~~~~~~~~~~~> <~~~~~~~~~~~~+~~~~~~~~~~~> 235 |<~~~~~~~~~~~~+~~~~~~~~~~~~>|<~~~~~~~~~~~~+~~~~~~~~~~~~> 236 +--|--+ +--|--+ +--|--+ +--|--+ 237 | B |<======| A | | C |======>| D | 238 +-----+ +-----+ +-----+ +-----+ 240 Figure 3: The exposed node problem. When node A is communicating 241 with node B, node C is an "exposed node". 243 Hidden and exposed node situations are not uncommon in multi-hop ad 244 hoc wireless networks. Problems with asymmetric links may also arise 245 for reasons other than power inequality (e.g., multipath 246 interference). Such problems are often resolved by specific 247 mechanisms below the IP layer. However, depending the link layer 248 technology in use and the position of the nodes, such problems due to 249 range-limitation and partial overlap may affect the IP layer. 251 Besides radio range limitations, wireless communications are affected 252 by irregularities in the shape of the geographical area over which 253 nodes may effectively communicate (see for instance [MC03], [MI03]). 254 For example, even omnidirectional wireless transmission is typically 255 non-isotropic (i.e. non-circular). Signal strength often suffers 256 frequent and significant variations, which are not a simple function 257 of distance. Instead, it is a complex function of the environment 258 including obstacles, weather conditions, interference, and other 259 factors that change over time. The analytical formulation of such 260 variation is often considered intractable. 262 These irregularities also cause communications on multi-hop ad hoc 263 wireless networks to be non-transitive, asymmetric, or time-varying, 264 as described in Section 3.1, and may impact the IP layer. There may 265 be no indication to IP when a previously established communication 266 channel becomes unusable; "link down" triggers are generally absent 267 in multi-hop ad hoc wireless networks. 269 4. Alternative Terminology 271 Many terms have been used in the past to describe the relationship of 272 nodes in a multi-hop ad hoc wireless network based on their ability 273 to send or receive packets to/from each other. The terms used in 274 this document have been selected because the authors believe (or at 275 least hope) they are unambiguous, with respect to the goal of this 276 document (see Section 1). 278 Nevertheless, here are a few other terms that describe the same 279 relationship between nodes in multi-hop ad hoc wireless networks. In 280 the following, let network N be, again, a multi-hop ad hoc wireless 281 network. Let the set S be, as before, the set of nodes that can 282 directly receive packets transmitted by node A through its interface 283 on network N. In other words, any node B belonging to S can "hear" 284 packets transmitted by A. Then, due to the asymmetry characteristic 285 of wireless links: 287 - We may say that node B is reachable from node A. In this 288 terminology, there is no guarantee that node A is reachable from 289 node B, even if node B is reachable from node A. 291 - We may say that node A has a link to node B. In this 292 terminology, there is no guarantee that node B has a link to node 293 A, even if node A has a link to node B. 295 - We may say that node B is adjacent to node A. In this 296 terminology, there is no guarantee that node A is adjacent to node 297 B, even if node B is adjacent to node A. 299 - We may say that node B is downstream from node A. In this 300 terminology, there is no guarantee that node A is downstream from 301 node B, even if node B is downstream from node A. 303 - We may say that node B is a neighbor of node A. In this 304 terminology, there is no guarantee that node A is a neighbor of 305 node B, even if node B a neighbor of node A. As it happens, the 306 terminology for "neighborhood" is quite confusing for asymmetric 307 links. When B can hear signals from A, but A cannot hear B, it is 308 not clear whether B should be considered a neighbor of A at all, 309 since A would not necessarily be aware that B was a neighbor. 310 Perhaps it is best to avoid the "neighbor" terminology except for 311 symmetric links. 313 This list of alternative terminologies is given here for illustrative 314 purposes only, and is not suggested to be complete or even 315 representative of the breadth of terminologies that have been used in 316 various ways to explain the properties mentioned in Section 3. 318 5. Security Considerations 320 This document does not have any security considerations. 322 6. IANA Considerations 324 This document does not have any IANA actions. 326 7. Informative References 328 [RFC2501] Corson, M. and J. Macker, "Mobile Ad hoc Networking 329 (MANET): Routing Protocol Performance Issues and 330 Evaluation Considerations", RFC 2501, January 1999. 332 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 333 Demand Distance Vector (AODV) Routing", RFC 3561, 334 July 2003. 336 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State 337 Routing Protocol (OLSR)", RFC 3626, October 2003. 339 [RFC3684] Ogier, R., Templin, F., and M. Lewis, "Topology 340 Dissemination Based on Reverse-Path Forwarding (TBRPF)", 341 RFC 3684, February 2004. 343 [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source 344 Routing Protocol (DSR) for Mobile Ad Hoc Networks for 345 IPv4", RFC 4728, February 2007. 347 [RFC4903] Thaler, D., "Multi-Link Subnet Issues", RFC 4903, 348 June 2007. 350 [RFC5449] Baccelli, E., Jacquet, P., Nguyen, D., and T. Clausen, 351 "OSPF Multipoint Relay (MPR) Extension for Ad Hoc 352 Networks", RFC 5449, February 2009. 354 [DoD01] Freebersyser, J. and B. Leiner, "A DoD perspective on 355 mobile ad hoc networks", Addison Wesley C. E. Perkins, 356 Ed., 2001, pp. 29--51, 2001. 358 [FUNKFEUER] "Austria Wireless Community Network, 359 http://www.funkfeuer.at", 2009. 361 [IPev] Thaler, D., "Evolution of the IP Model", 362 draft-thaler-ip-model-evolution-01.txt (work in 363 progress), 2008. 365 [MC03] Corson, S. and J. Macker, "Mobile Ad hoc Networking: 366 Routing Technology for Dynamic, Wireless Networks", IEEE 367 Press Mobile Ad hoc Networking, Chapter 9, 2003. 369 [MI03] Kotz, D., Newport, C., and C. Elliott, "The Mistaken 370 Axioms of Wireless-Network Research", Dartmouth College 371 Computer Science Technical Report TR2003-467, 2003. 373 [FREIFUNK] "Freifunk Wireless Community Networks", 2009. 375 Appendix A. Acknowledgements 377 This document stems from discussions with the following people, in 378 alphabetical order: Jari Arkko, Teco Boot, Carlos Jesus Bernardos 379 Cano, Ian Chakeres, Thomas Clausen, Christopher Dearlove, Ralph 380 Droms, Ulrich Herberg, Paul Lambert, Kenichi Mase, Thomas Narten, 381 Erik Nordmark, Alexandru Petrescu, Stan Ratliff, Zach Shelby, 382 Shubhranshu Singh, Fred Templin, Dave Thaler, Mark Townsley, Ronald 383 Velt in't, and Seung Yi. 385 Authors' Addresses 387 Emmanuel Baccelli 388 INRIA 390 Phone: +33-169-335-511 391 EMail: Emmanuel.Baccelli@inria.fr 392 URI: http://www.emmanuelbaccelli.org/ 394 Charles E. Perkins 395 Tellabs 397 Phone: +1-408-970-6560 398 EMail: charliep@tellabs.com