idnits 2.17.00 (12 Aug 2021) /tmp/idnits25821/draft-wunderlich-openmesh-manet-routing-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 1016. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1027. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1034. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1040. 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 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (Apr 07, 2008) is 5157 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Unused Reference: 'RFC3552' is defined on line 960, but no explicit reference was found in the text == Outdated reference: draft-narten-iana-considerations-rfc2434bis has been published as RFC 5226 Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Neumann 3 Internet-Draft C. Aichele 4 Intended status: Experimental M. Lindner 5 Expires: October 9, 2008 S. Wunderlich 6 Apr 07, 2008 8 Better Approach To Mobile Ad-hoc Networking (B.A.T.M.A.N.) 9 draft-wunderlich-openmesh-manet-routing-00 11 Status of this Memo 13 By submitting this Internet-Draft, each author represents that any 14 applicable patent or other IPR claims of which he or she is aware 15 have been or will be disclosed, and any of which he or she becomes 16 aware will be disclosed, in accordance with Section 6 of BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft will expire on October 9, 2008. 36 Copyright Notice 38 Copyright (C) The IETF Trust (2008). 40 Abstract 42 This document specifies a simple and robust algorithm for 43 establishing multi-hop routes in mobile ad-hoc networks. It ensures 44 highly adaptive and loop-free routing while causing only low 45 processing and traffic cost. 47 Table of Contents 49 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 50 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 51 1.2. Protocol Overview . . . . . . . . . . . . . . . . . . . . 4 52 2. Protocol and Port Number . . . . . . . . . . . . . . . . . . . 6 53 3. B.A.T.M.A.N. Packet Formats . . . . . . . . . . . . . . . . . 6 54 3.1. General B.A.T.M.A.N. Packet Format . . . . . . . . . . . . 6 55 3.2. Originator Message (OGM) Format . . . . . . . . . . . . . 8 56 3.2.1. Originator Message (OGM) Fields . . . . . . . . . . . 8 57 3.3. HNA Message Format . . . . . . . . . . . . . . . . . . . . 9 58 3.3.1. HNA Message Fields . . . . . . . . . . . . . . . . . . 9 59 4. Conceptual Data Structures . . . . . . . . . . . . . . . . . . 9 60 4.1. Originator List . . . . . . . . . . . . . . . . . . . . . 9 61 4.2. Sequence Numbers, Ranges, and Windows . . . . . . . . . . 11 62 5. Flooding Mechanism . . . . . . . . . . . . . . . . . . . . . . 13 63 5.1. Broadcasting own Originator Messages (OGMs) . . . . . . . 13 64 5.2. Receiving Originator Messages . . . . . . . . . . . . . . 14 65 5.3. Bidirectional Link Check . . . . . . . . . . . . . . . . . 14 66 5.4. Neighbor Ranking . . . . . . . . . . . . . . . . . . . . . 15 67 5.5. Re-broadcasting other nodes' OGMs . . . . . . . . . . . . 15 68 6. Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 69 6.1. Route Selection and Establishing . . . . . . . . . . . . . 16 70 6.2. Route Deletion . . . . . . . . . . . . . . . . . . . . . . 17 71 6.3. Opportunistic Routing Deletion Policy . . . . . . . . . . 17 72 6.3.1. Opportunistic Routing Deletion Policy Consideration . 17 73 7. Gateway . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 74 7.1. Gateway Announcement . . . . . . . . . . . . . . . . . . . 17 75 7.2. Gateway Selection . . . . . . . . . . . . . . . . . . . . 18 76 7.3. Gateway Tunneling/Encapsulation . . . . . . . . . . . . . 19 77 7.4. Gateway hopping (testing/accepting) . . . . . . . . . . . 19 78 8. Proposed Values for Constants . . . . . . . . . . . . . . . . 19 79 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 80 10. Security Considerations . . . . . . . . . . . . . . . . . . . 20 81 10.1. Confidentiality . . . . . . . . . . . . . . . . . . . . . 20 82 10.2. Overflow of routing entries . . . . . . . . . . . . . . . 20 83 10.3. Route manipulation . . . . . . . . . . . . . . . . . . . . 21 84 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 85 11.1. Normative References . . . . . . . . . . . . . . . . . . . 21 86 11.2. Informative References . . . . . . . . . . . . . . . . . . 22 87 Appendix A. Contributors . . . . . . . . . . . . . . . . . . . . 22 88 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 89 Intellectual Property and Copyright Statements . . . . . . . . . . 24 91 1. Introduction 93 B.A.T.M.A.N. is a proactive routing protocol for Wireless Ad-hoc Mesh 94 Networks, including (but not limited to) Mobile Ad-hoc Networks 95 (MANETs). The protocol proactively maintains information about the 96 existence of all nodes in the mesh that are accessible via single-hop 97 or multi-hop communication links. The strategy of B.A.T.M.A.N. is to 98 determine for each destination in the mesh one single-hop neighbor, 99 which can be utilized as best gateway to communicate with the 100 destination node. In order to perform multi-hop IP-based routing, 101 the routing table of a node must contain a link-local gateway for 102 each host or network route. To learn about the best next-hop for 103 each destination is all that the B.A.T.M.A.N. algorithm cares about. 104 There is no need to find out or calculate the complete route, which 105 makes a very fast and efficient implementation possible. 107 Wireless mesh networks have special difficulties unlike wired 108 networks: Data packets can and will get lost in noisy areas. Mesh 109 networks consisting of nodes with only one wireless communication 110 interface (which are usually operating on the same wireless channel) 111 have to cope with self-inflicted interference caused by their own 112 wireless traffic. Thus communication links may have varying quality 113 in terms of packet loss, data rates, and interference. Even the 114 protocol traffic from the routing protocol itself causes 115 interference. Therefore communication link quality changes even in 116 static network topologies. New links appear and known links 117 disappear frequently, especially in MANETs. The quality of one 118 communication direction may differ to the opposite direction ( e.g. 119 asymmetric links). 121 B.A.T.M.A.N. considers these challenges by doing statistical analysis 122 of protocol packet loss and propagation speed and does not depend on 123 state or topology information from other nodes. Rather than trusting 124 on metadata contained in received protocol traffic - which could be 125 delayed, outdated, or lost - routing decisions are based on the 126 knowledge about the existence or lack of information. B.A.T.M.A.N. 127 protocol packets contain only a very limited amount of information 128 and are therefore very small. Lost protocol packets due to 129 unreliable links are not countered with redundancy, but are detected 130 and utilized for better routing decisions. B.A.T.M.A.N. chooses the 131 most reliable route upon the next-hop routing decision of individual 132 nodes. This approach has shown in practise that it is reliable and 133 loop-free. 135 Comments are solicited and should be addressed to the B.A.T.M.A.N. 136 mailing list at b.a.t.m.a.n@open-mesh.net and/or the authors. 138 1.1. Terminology 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 Node - A mesh router which utilizes the B.A.T.M.A.N. protocol as 145 specified in this document on at least one network interface. 147 Link - wired or wireless communication link, which can be 148 unidirectional or bidirectional 150 Direct Link - single-hop communication link between two particular 151 B.A.T.M.A.N. interfaces 153 Bidirectional Link - direct link with bidirectional (symmetric) 154 communication capability 156 Unidirectional Link - direct link with only unidirectional 157 (asymmetric) communication capability 159 Bidirectional Neighbor - single-hop neighbor, available via a direct 160 bidirectional link 162 Best Link - the most promising outgoing interface and next hop 163 towards a given originator 165 B.A.T.M.A.N. Interface - Network interface utilized by B.A.T.M.A.N. 166 This is also a synonym for an Originator. 168 Host Network Announcement (HNA) - Message type, used to announce a 169 gateway to a network or host 171 Originator Message (OGM) - B.A.T.M.A.N. protocol message advertising 172 the existence of an Originator. OGMs are used for link quality and 173 path detection. 175 Originator - Synonym for a B.A.T.M.A.N. Network Interface, announced 176 by B.A.T.M.A.N. Originator Messages. 178 1.2. Protocol Overview 180 B.A.T.M.A.N. detects the presence of B.A.T.M.A.N.-Originators, no 181 matter whether the communication path to/from an Originator is a 182 single-hop or multi-hop communication link. The protocol does not 183 try to find out the full routing path, instead it only learns which 184 link-local neighbor is the best gateway to each Originator. It also 185 keeps track of new Originators and informs its neighbors about their 186 existence. The protocol ensures that a route consists of 187 bidirectional links only. 189 On a regular basis every node broadcasts an originator message (or 190 OGM), thereby informing its link-local neighbors about its existence 191 (first step). Link-local neighbors which are receiving the 192 Originator messages are relaying them by rebroadcasting it, according 193 to specific B.A.T.M.A.N. forwarding rules. The B.A.T.M.A.N. mesh 194 network is therefore flooded with Originator messages. This flooding 195 process will be performed by single-hop neighbors in the second step, 196 by two-hop neighbors in the third step, and so forth. OGMs are send 197 and repeated as UDP broadcasts, therefore OGMs are flooded until 198 every node has received it at least once, or until they got lost due 199 to packet loss of communication links, or until their TTL (time to 200 live) value has expired. In practise OGM packet loss caused by 201 interference, collision or congestion is significant. The number of 202 OGMs received from a given Originator via each link-local neighbor is 203 used to estimate the quality of a (single-hop or multi-hop) route. 204 In order to be able to find the best route to a certain Originator, 205 B.A.T.M.A.N counts the originator-messages received and logs which 206 link-local neighbor relayed the message. Using this information 207 B.A.T.M.A.N. maintains a table with the best link-local router 208 towards every Originator on the network. By using a sequence number, 209 embedded in each OGM, B.A.T.M.A.N. can distinguish between new 210 Originator message packets and duplicates ensuring that every OGM 211 gets only counted once. 213 B.A.T.M.A.N. was not designed to operate on stable and reliable 214 media, such as cable networks, but rather to function on unreliable 215 media inherently experiencing high levels of instability and data 216 loss. The protocol was devised to counteract the side effects of a 217 network's fluctuation and compensate its instability, thus allowing 218 for a high level of robustness. It also embodies the idea of 219 collective intelligence opposed to link state routing. The 220 topographical information is not handled by a single node, but spread 221 across the whole network. No central entity knows all possible ways 222 through the network. Every node only determines the data to choose 223 the next hop, making the protocol very lightweight and quickly 224 adapting to fluctuating network topologies. 226 B.A.T.M.A.N. Originators can announce themselves as gateways to the 227 internet. Their announcement includes a gateway-class, which is 228 specifying the connection speed of their up- and downlink to the 229 internet. Gateways also send a port-number which is used by gateway 230 clients to establish a unidirectional UDP-tunnel to the gateway. The 231 decision which gateway is selected for a destination is performed by 232 the gateway-client. 234 The method of tunneling between a B.A.T.M.A.N. internet gateway 235 client and the internet gateway ensures a stable route to the 236 internet as long as the protocol can maintain a working communication 237 path between both peers. This is particularly important when the 238 internet gateway has to perform Network Address Translation (NAT) 239 between nodes using private IP address space in the mesh and public 240 IP networks. 242 Once the tunnel is established the network topology and routing paths 243 between the B.A.T.M.A.N. gateway and the gateway client may change 244 but the data will get routed via the initial gateway and back without 245 changes, as long as the protocol can provide a working communication 246 route. Thus, B.A.T.M.A.N. is capable to provide stable session-based 247 internet-traffic in MANETs with more than one gateway to other 248 network segments. Apart from stable routing the tunneling also 249 allows for techniques such as black hole detection to be used in 250 B.A.T.M.A.N. networks. 252 2. Protocol and Port Number 254 Packets in B.A.T.M.A.N. are communicated using UDP. Port 4305 has 255 been assigned by IANA for exclusive usage by the B.A.T.M.A.N. 256 protocol. 258 3. B.A.T.M.A.N. Packet Formats 260 3.1. General B.A.T.M.A.N. Packet Format 262 The general layout of a B.A.T.M.A.N. packet (without the trailing IP 263 and UDP header). 265 General B.A.T.M.A.N. packet format. 267 0 1 2 3 268 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 269 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 270 | | 271 + + 272 | Originator Message (OGM) | 273 + + 274 | | 275 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 276 : Optional HNA Messages : 277 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 278 : | : 279 +-+-+-+-+-+-+-+-+ : 280 : (etc.) : 282 Figure 1 284 Each B.A.T.M.A.N. packet is encapsulated in a single UDP data packet. 286 A B.A.T.M.A.N. packet consists of one originator message (OGM) and 287 zero or more attached HNA extension messages. 289 Originator Message (OGM): 291 OGMs have a fixed size of 12 octets. They are further 292 described in Section Section 3.2. 294 Optional HNA Extension Messages: 296 An OGM may be followed by zero or more HNA extension 297 messages. Each extension message following a preceding OGM 298 is associated with the preceding OGM and MUST be processed 299 respectively. 301 HNA messages have a fixed size of 5 octets. It is 302 described in Section Section 3.3. 304 3.2. Originator Message (OGM) Format 306 Originator Message (OGM) format. 308 0 1 2 3 309 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 310 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 311 | Version |U|D| | TTL | GWFlags | 312 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 313 | Sequence Number | GW Port | 314 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 315 | Originator Address | 316 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 318 Figure 2 320 3.2.1. Originator Message (OGM) Fields 322 Version: 324 MUST be set to VERSION. Each packet received with a 325 version field different from VERSION MUST be ignored. 327 Is-direct-link flag: 329 This flag indicates whether a Node is a direct neighbor or 330 not. 332 Unidirectional flag: 334 This flag indicates whether the neighboring node is 335 bidirectional or not. 337 TTL (Time To Live): 339 The TTL can be used to define an upper limit on the number 340 of hops an OGM can be transmitted 342 Gateway flags (GWFlags): 344 MUST be set according to description in Section 7.1. 346 Sequence Number: 348 The originator of an OGM consecutively numbers each new OGM 349 with an incremented (by one) sequence number. To get an 350 overview about the Sequence Number handling see 351 Section 4.2. 353 Originator Address: 355 The IPv4 address of the B.A.T.M.A.N. interface on which 356 behalf the OGM has been generated. 358 3.3. HNA Message Format 360 HNA-extension-message format. 362 0 1 2 3 363 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 364 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 365 | Network Address | 366 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 367 | Netmask | 368 +-+-+-+-+-+-+-+-+ 370 Figure 3 372 3.3.1. HNA Message Fields 374 Netmask: 376 The number of bits presenting the size of the announced 377 network. 379 Network Address: 381 The IPv4 network address of the announced network. 383 4. Conceptual Data Structures 385 Each node must maintain certain information about its own and other 386 B.A.T.M.A.N. originators in the network and how these originators are 387 related to neighboring nodes and to the B.A.T.M.A.N. interfaces of 388 the node itself. This Section conceptionally describes the 389 information necessary to conform to the protocol described in this 390 document. 392 4.1. Originator List 394 Each node maintains information about the known other originators 395 (B.A.T.M.A.N. Interfaces) in the network in an Originator List. The 396 Originator List contains one entry for each Originator from which or 397 via which an OGM has been received within the last PURGE_TIMEOUT 398 seconds. If OGMs from different Originators (B.A.T.M.A.N. 399 interfaces) of the same node are received then there MUST be one 400 entry for each Originator. In fact, the receiving node does not 401 necessarily know that certain different Originators (and 402 corresponding IP addresses) are belonging to the same B.A.T.M.A.N. 403 node. 405 For each Originator the following Information must be maintained: 407 o Originator IPv4 Address: 409 The IPv4 address of the Originator (B.A.T.M.A.N. Interface) 410 as given in the corresponding field of the received OGM. 412 o Last Aware time: 414 A timestamp which MUST be updated with every OGM that has 415 been received from or via the given Originator. 417 o Bidirect Link(s) Sequence Number: 419 The bidirectional Link Check requires a Node to save the 420 information which direct neighbor successfully rebroadcasted 421 its own OGM. Therefore, the Sequence Number of the last 422 accepted self-initiated OGM received from a direct link 423 neighbor is to be saved here on a per Interface basis. This 424 is described in Section 5.3. 426 o Current Sequence Number: 428 The newest OGM Sequence Number that has been accepted from 429 the given Originator. This is described in Section 4.2. 431 o HNA List: 433 All announced Networks of the Originator with their IP-Range 434 and Netmask. 436 o Gateway capabilities: 438 If the Originator offers a Gateway, and its announced 439 parameters. 441 o Neighbor information List: 443 for each Direct Link to each Neighbor of the node the 444 following information must be maintained: 446 + Sliding Window: 448 For each In-Window Sequence Number it is remarked if 449 an OGM with this Sequence Number has been received. 450 This is described in Section 4.2. 452 + Packet Count: 454 The amount of Sequence Numbers recorded in the 455 Sliding Window. It is used as a metric for the path 456 to the Originator via this neighbor. 458 + Last Valid Time: 460 The timestamp when the last valid OGM was received 461 via this neighbor. 463 + Last TTL: 465 The TTL of the last OGM which was received via this 466 neighbor. 468 4.2. Sequence Numbers, Ranges, and Windows 470 B.A.T.M.A.N. is Sequence Number oriented. In fact, the Sequence 471 Number of a received OGM is the key information that is transmitted 472 with each OGM. 474 Sequence Numbers are recorded in dedicated sliding windows until they 475 are considered Out-Of Range. Thus, such a sliding window always 476 contains the set of recently received Sequence Numbers. The amount 477 of Sequence Numbers recorded in the Sliding Window is used as a 478 metric for the quality of detected links and paths. 480 The Sequence Number range is not an infinite space but is limited to 481 the range of 0 .. 2^16 - 1. Since the space is limited, all 482 arithmetical operations must be performed modulo 2^16. With this, 483 sequence numbers cycle from 0 to 2^16-1 and start from 0 again when 484 reaching the maximum value. Therefore, special care must be taken 485 with comparisons. For example, the 7 Sequence Numbers below 5 modulo 486 2^16 are 4,3,2,1,0,65535 and 65534. 488 Conceptional illustration of In-Window and Out-Of-Range Sequence 489 Numbers for a WINDOW_SIZE of 8 (The proposed WINDOW_SIZE constant is 490 defined in Section 8) 492 n=Current Sequence Number 493 <...- - - - - - - - - - + + + + + + + + + + + + + + + + + + + + + +..> 494 1 0 1 2 495 0 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 496 <--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-> 497 |<------------>| 498 | WINDOW_SIZE | 499 | | 500 <------->|<------------>|<-----------------------------------------> 501 Out-Of- | In-Window | Out-Of Range 502 Range | | 504 Figure 4 506 In-Window Sequence Numbers: 508 The In-Window Sequence Numbers represent the latest 509 sequence numbers. They include the Current Sequence Number 510 from this Originator and the WINDOW_SIZE - 1 Sequence 511 Numbers below it. 513 The Current Sequence Number of each Originator MUST be 514 maintained, as well as information if an OGM has been 515 received or not for each In-Window Sequence Number. 517 If an OGM from this Originator with a In-Window Sequence 518 Number is received, the Current Sequence Number will NOT be 519 updated, and therefore the Sliding Window is not moved. It 520 must be memorized that an OGM with Sequence Number has been 521 received. 523 Out-Of-Range Sequence Numbers: 525 Out-Of-Range Sequence Numbers are all Sequence Numbers 526 which are not in the In-Window range. They are considered 527 new or next-expected Sequence Numbers. 529 If an OGM from this Originator with an Out-Of-Range 530 Sequence Number is received, the Current Sequence Number is 531 set to this new Sequence Number. This means that the 532 Sliding Window is moved, and Sequence Numbers which are not 533 in the In-Window Range anymore drop out of the Window. 534 Information if OGMs have been received or not with Sequence 535 Numbers which dropped out of the Window MUST be purged. 537 5. Flooding Mechanism 539 The flooding mechanism can be divided into several parts: 541 o How to generate and broadcast OGMs is described in Section 5.1. 543 o The reception and evaluation of OGMs is described in Section 5.2. 545 o The update and usage of the Bidirectional Link Check is explained 546 in Section 5.3. 548 o The Neighbor Ranking and Best Link detection is described in 549 Section 5.4. 551 o The rebroadcast mechanism is described in Section 5.5. 553 5.1. Broadcasting own Originator Messages (OGMs) 555 Each node MUST periodically generate and broadcast OGMs for each 556 B.A.T.M.A.N. Interface. The Message(s) MUST be broadcasted every 557 ORIGINATOR_INTERVAL via all B.A.T.M.A.N. Interfaces. A jitter may be 558 applied to avoid collisions. The OGM MUST be initialized as follows: 560 o Version: Set your internal compatibility version. 562 o Flags: Set the Is-direct-link and Unidirectional flag to zero. 564 o TTL: Set the TTL to the desired value in the range of TTL_MIN and 565 TTL_MAX. 567 o Sequence number: On first broadcast set the sequence number to an 568 arbitrary value and increment the field by one for each following 569 broadcast. 571 o GWFlags: If this host offers an internet connection set the field 572 as described in Section 7.1 otherwise set it to zero. 574 o GWPort: If this host offers an internet connection set the field 575 to your desired tunneling port otherwise set it to zero. 577 o Originator Address: Set this field to the IP address of this 578 B.A.T.M.A.N. Interface. 580 If this Node wants to announce access to non-B.A.T.M.A.N. networks 581 via HNA it SHOULD append an HNA Extension Messages for every network 582 to be announced. See Section 3.3 for a detailed description of that 583 message type. 585 5.2. Receiving Originator Messages 587 Upon receiving a general B.A.T.M.A.N. packet a Node MUST perform the 588 following preliminary checks before the packet is further processed: 590 1. If the OGM contains a version which is different to the own 591 internal version the message MUST be silently dropped (thus, it 592 MUST NOT be further processed or broadcasted). 594 2. If the sender address of the OGM belongs to one of the 595 B.A.T.M.A.N. interfaces the message MUST be silently dropped as 596 this OGM originated from this Node. 598 3. If the sender address of the OGM is a broadcast address of an own 599 B.A.T.M.A.N. interface the message MUST be silently dropped. 601 4. If the Originator Address of the OGM is identical with any of the 602 Nodes' own B.A.T.M.A.N. Interfaces then the OGM has been 603 originated by the Node itself. The processing of the OGM MUST 604 continue as described in Section 5.3 and afterwards silently 605 dropped. 607 5. If the unidirectional flag of the OGM is set the message MUST be 608 silently dropped. 610 6. If the OGM has been received via a Bidirectional link AND 611 contains a New Sequence Number (is NOT a duplicate) then the OGM 612 MUST be processed as described in Section 5.4. 614 7. The OGM has to be rebroadcasted as described in Section 5.5 if: 616 * the OGM has been received from a single hop neighbor (sender 617 address equals Originator Address) 619 * the OGM was received via a Bidirectional link AND via the Best 620 Link AND is either not a duplicate or has the same TTL as the 621 last packet which was not a duplicate (last TTL) 623 5.3. Bidirectional Link Check 625 A Bidirectional Link check is used to verify that a detected link to 626 a given neighbor can be used in both directions. 628 Therefore the Sequence Number of each self-originated OGM (re- 629 broadcasted by a direct link neighbor) for each Interface must be 630 recorded (Bidirect Link Sequence Number) if: 632 o the self-originated OGM has been received via the Interface for 633 which the OGM has been generated 635 o the direct-link-flag is set 637 o the Sequence Number matches the Sequence Number send with the last 638 OGM broadcasted for that Interface 640 The bidirectional link check succeeds if the last originated Sequence 641 number does not differ more than BI_LINK_TIMEOUT from the recorded 642 Sequence number. 644 5.4. Neighbor Ranking 646 Upon reception of an OGM from another node the following must be 647 performed: 649 o The Packet Count MUST be updated. 651 o If the OGMs Sequence Number is newer than the Current Sequence 652 Number: 654 * The new Current Sequence Number MUST be set to the Sequence 655 Number contained in the received OGM. 657 * The Last TTL of this neighbor MUST be updated. 659 * The Sliding Windows of all known links to the Originator of the 660 OGM must be updated (purged) to reflect the new upper and lower 661 boundaries of the Ranking Range. The Sequence Number of the 662 received OGM must be added to the Sliding Window representing 663 the link via which the OGM has been received. 665 o If the Sliding Window of the link via which the OGM has been 666 received contains the most (In-Ranking-Range) Sequence Numbers 667 then this link is said to be the new Best Link to the Originator 668 of the OGM. Otherwise the previously considered Best Link MUST 669 NOT change. 671 5.5. Re-broadcasting other nodes' OGMs 673 When an OGM is to be re-broadcasted some of the message fields MUST 674 be changed others MUST be left unchanged. All fields not mentioned 675 in the following section remain untouched: 677 o The TTL must be decremented by one. If the TTL becomes zero 678 (after the decrementation) the packet MUST be dropped. 680 o The Is-direct-link MUST be set if the OGM has been received from a 681 Direct Link Neighbor AND if it is re-broadcasted via the link via 682 which it has been received. 684 o The Unidirectional flag must be set if an OGM is to be re- 685 broadcasted that has been received via an unidirectional link. 687 6. Routing 689 In order to maintain the routing table of a B.A.T.M.A.N. node, the 690 routing daemon keeps track of incoming new OGMs and maintains a list 691 of all Originators which have sent Originator messages as shown in 692 section Section 4. 694 B.A.T.M.A.N. maintains one dedicated routing entry for each known 695 Originator and HNA announcement. Each routing entry defines the 696 outgoing B.A.T.M.A.N. interface and the IP address of the next-hop 697 direct-link neighbor towards the corresponding Originator. 698 B.A.T.M.A.N. must add a host route to all Originators, even if they 699 are link-local bidirectional single-hop neighbors. 701 6.1. Route Selection and Establishing 703 If a OGM from an unknown Originator or to an unknown network/host via 704 HNA is received, it will be added to the routing table, and the best 705 ranking link-local bidirectional neighbor is selected as gateway to 706 the destination. If the destination is a host, a host route will be 707 added via the best ranking bidirectional single-hop neighbor for the 708 destination. If the destination is a network, announced by HNA 709 information included in a OGM message, a network route is added via 710 the best ranking bidirectional single-hop neighbor. A bidirectional 711 single-hop neighbor may or may not be selected as gateway to itself. 712 In case a single-hop Originator is not the best gateway to itself, an 713 host route via another bidirectional single-hop neighbor MUST be 714 chosen. 716 If the best ranking neighbor to the destination changes, the routing 717 table must be updated. 719 The gateway of each host route to an Originator must be in sync with 720 the Best Link identified for the Originator, as described in Section 721 Section 5.4. The gateway of each HNA related host or network route 722 must be in sync with the host route of the Originator that ownes the 723 corresponding HNA message. 725 6.2. Route Deletion 727 In case a node does not receive a single OGM or HNA from a known 728 Originator for a time longer than the sliding WINDOW_SIZE and the 729 PURGE_TIMEOUT interval, the route is considered to be expired and 730 will be removed from the routing table. 732 6.3. Opportunistic Routing Deletion Policy 734 B.A.T.M.A.N. should behave opportunistic when deleting routes: The 735 suggested purging intervals for routes should be long, compared to 736 the sliding window size (Recommended value: PURGE_TIMEOUT = 10 x 737 WINDOW_SIZE x ORIGINATOR_INTERVAL). 739 6.3.1. Opportunistic Routing Deletion Policy Consideration 741 A routing entry to a destination that is no longer working, is a 742 minor problem in terms of managing network traffic efficiently. The 743 only disadvantage is, that a node may utilize the network trying to 744 send information to an unreachable destination for a while, before 745 giving up. On the other hand, having no routing entry to a 746 destination that would otherwise be accessible, is problematic in 747 terms of routing functionality. To avoid an overflow of routing 748 information, the routing table is purged from expired entrys 749 according to the PURGE_TIMEOUT interval. However, as soon as new 750 OGMs from a destination are received, the routing entry is updated if 751 a change in the network topology has occurred. 753 7. Gateway 755 7.1. Gateway Announcement 757 A B.A.T.M.A.N. node with access to the internet and routing 758 capabilities MAY act as a internet Gateway. The Gateway is announced 759 with the GWFlags transmitted within the B.A.T.M.A.N.-OGM packets. If 760 the node does not provide access to the internet, it MUST set GWFlags 761 to 0. Otherwise, the GWFlags contains the provided bandwidth encoded 762 as described below. The providing node SHOULD set this value to the 763 best approximate estimate of available bandwidth. 765 The GWFlags fields. 767 0 768 0 1 2 3 4 5 6 7 769 +-+-+-+-+-+-+-+-+ 770 |S| down | up | 771 +-+-+-+-+-+-+-+-+ 773 Figure 5 775 The GWFlags encodes the approximate available bandwidth in kbit per 776 second. The downstream and upstream bandwidth is calculated based on 777 the fields, which are interpreted as binary numbers: 779 downstream bandwidth = 32 * (S + 2) * 2^down kbit/s 781 upstream bandwidth = ((up +1) * (downstream bandwidth)) / 8 782 kbit/s 784 (annotation: 2^x means 2 raised to the power of x) 786 7.2. Gateway Selection 788 The B.A.T.M.A.N.-nodes can determine the gateway in several ways. 789 The individual node on the network can either choose to decide upon 790 the gateway to be used according to the download speed and connection 791 quality or only according to the connection speed with the gateway 792 itself or as a suitable solution for mobile nodes only by checking 793 for the gateway with the best download speed, but this inherits a 794 frequent change in the gateway used. 796 It is suggested that the B.A.T.M.A.N.-nodes should, in order to 797 guarantee functionality, be able to determine and decide upon their 798 internet-gateways in multiple ways. It would seem useful that the 799 individual user could, for example, be able to choose any given 800 combination of the download speed and the connection strength to the 801 internet-gateway i.e. only looking at a combination of the conditions 802 noted or decide to disregard one. This might be important for mobile 803 nodes for example as it could be their priority to have a good 804 connection to their gateway rather than having the focus on their 805 internet-connection's speed. On the other hand would this allow for 806 static users to accept a worse connection to the gateway itself to 807 have a faster connection to the internet. And in some cases it might 808 prove useful to combine both methods although a dynamically chosen 809 internet-gateway always brings with it the possibility of all 810 connections being reset due to switching from one gateway to another. 811 Hence it is strongly suggested that the routing-protocol should 812 include the possibility for the user to set his gateway statically 813 and not having the protocol deciding upon the best route to the 814 internet but using this as a fallback method should the gateway 815 configured by the user not be reachable. 817 7.3. Gateway Tunneling/Encapsulation 819 A GW-client node tunnels all data to the internet (all IP packets 820 with a destination address that does only match the default route) 821 via a selected GW node. No encapsulation is used for packets from 822 the internet to the GW-client nodes. The GW-client node encapsulates 823 the internet data into a IP/UDP datagram and forwards the 824 encapsulated data to the selected GW node. The GW node identifies 825 the encapsulated packets based on the port number of the outer UDP 826 header. It decapsulates the original packet and forwards it to its' 827 original destination. This procedure is completely stateless. 829 For encapsulation, a GW-client node MUST set the outer IP header 830 source and destination address to the Originator Address of the GW- 831 Client node and the GW node. The outer UDP source and destination 832 MUST be set to the GW Port number given by the OGM of the GW node. 833 The inner IP header and all following data represents the original IP 834 packet. All data of the inner IP packet MUST be left unchanged. If 835 the size of the original IP packet does not fit into the payload 836 section of the outer UDP datagram the packet must be dropped. If 837 virtual interfaces are used to integrate an implementation of the 838 B.A.T.M.A.N protocol into a network environment then the maximum 839 transfer unit (MTU) of the virtual interface should reflect the 840 maximum payload size of the inner UDP datagram. 842 7.4. Gateway hopping (testing/accepting) 844 test the gateway (is it connected to the internet?) choose a better 845 gateway if its not available. 847 8. Proposed Values for Constants 849 VERSION = 4 851 TTL_MIN = 2 853 TTL_MAX = 255 855 SEQNO_MAX = 65535 857 BROADCAST_DELAY_MAX (Milliseconds) = 100 859 ORIGINATOR_INTERVAL (Milliseconds) = 1000 860 ORIGINATOR_INTERVAL_JITTER (Milliseconds)= 200 862 WINDOW_SIZE = 128 864 PURGE_TIMEOUT = 10 x WINDOW_SIZE x ORIGINATOR_INTERVAL 866 9. IANA Considerations 868 This memo includes no request to IANA. 870 All drafts are required to have an IANA considerations section (see 871 the update of RFC 2434 [I-D.narten-iana-considerations-rfc2434bis] 872 for a guide). If the draft does not require IANA to do anything, the 873 section contains an explicit statement that this is the case (as 874 above). If there are no requirements for IANA, the section will be 875 removed during conversion into an RFC by the RFC Editor. 877 10. Security Considerations 879 Routing protocols have to rely on information from other nodes in the 880 network. Therefore they are susceptible to various attacks and 881 B.A.T.M.A.N. being one of these protocols has to bear with them. The 882 B.A.T.M.A.N. protocol can be enhanced by the use of common encryption 883 and authentication technologies to insure that routing information is 884 only accepted from trusted nodes. To increase the level of security, 885 all information on the wireless layer itself may also be encrypted. 886 However, these approaches do not solve the challenges of a mesh 887 network consisting of non-authenticated, non-trusted peers and are 888 not in the scope of this document. In case there is no closed 889 trusted group of peers, the routing algorithm itself has to be robust 890 against false protocol informations. B.A.T.M.A.N.'s protocol design 891 inherently limits the impact of different attack vectors. 893 10.1. Confidentiality 895 A B.A.T.M.A.N. Node knows of the existence of all other nodes in the 896 network which are in the range of multi-hop communication links, but 897 due to its design it does not know the whole topology of the network. 898 A Nodes' topology view is limited to a one hop horizon. B.A.T.M.A.N. 899 accepts packets from arbitrary sources and builds its routing table 900 by analyzing the statistics of received Originator Messages. 902 10.2. Overflow of routing entries 904 A malicious host could send Originator Messages that are announcing 905 the existence of non-existing nodes to cause an overflow of routing 906 entrys or excessive cpu load and memory consumption. This attack can 907 be intercepted by sanity checks. If the number of routing entries 908 goes through the roof, Originators with very low Originator Message 909 count must be removed. 911 10.3. Route manipulation 913 An attacker can also generate OGMs from an existing Originator with 914 continuing valid Sequence Numbers that he actually didn't receive - 915 in order to manipulate other hosts routing, and redirect the route to 916 the destination to itself. Since routing decisions are based on 917 statistical analysis of the number of incoming Originator Messages, 918 rather than on information contained in packets, the attacker has to 919 generate many falsified protocol messages. Like valid protocol 920 messages, phony messages created by the attacker are subject to 921 packet loss. If an attacker wants to make sure that a route via his 922 controlled host will be chosen, he has to win the ranking towards the 923 destination continuously. This limits the range of successful 924 attacks to areas where the attacker can deliver enough false messages 925 to override valid messages. 927 If the Sequence numbers sent by the attacker differ more than the 928 sliding window size, the victims will assume that the other host has 929 restarted and will purge the ranking. The attacker can constantly 930 generate OGMs with Sequence numbers that induce all receiving nodes 931 to purge the ranking every time they receive a phony OGM. But every 932 time a valid OGM is received by the victims, his phony routing 933 information will be purged again. This limits the range and duration 934 of a successful attack. 936 The attacker may send phony OGMs for an existing Originator, that are 937 a few counts ahead of the real Sequence Number. This way the packets 938 from the attacker will be preferred in the ranking, and will not 939 induce the victims to purge the ranking. However if the number of 940 phony OGMs delivered to the victim is too low to win the ranking, the 941 attack will have no effect. Again, the range of an attack is 942 limited. 944 11. References 946 11.1. Normative References 948 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 949 Requirement Levels", BCP 14, RFC 2119, Current Status BEST 950 CURRENT PRACTICE, March 1997. 952 11.2. Informative References 954 [I-D.narten-iana-considerations-rfc2434bis] 955 Narten, T. and H. Alvestrand, "Guidelines for Writing an 956 IANA Considerations Section in RFCs", 957 draft-narten-iana-considerations-rfc2434bis-09 (work in 958 progress), March 2008. 960 [RFC3552] Rescorla, E. and B. Korver, "Guidelines for Writing RFC 961 Text on Security Considerations", BCP 72, RFC 3552, 962 July 2003. 964 Appendix A. Contributors 966 This specification is the result of the joint efforts of the 967 following contributors -- listed alphabetically. 969 Andreas Langer 971 Axel Neumann 973 Corinna (Elektra) Aichele 975 Felix Fietkau 977 Ludger Schmudde 979 Marek Lindner 981 Simon Wunderlich 983 Thomas Lopatic 985 Authors' Addresses 987 Axel Neumann 989 Email: axel@open-mesh.net 991 Corinna (Elektra) Aichele 993 Email: elektra@open-mesh.net 994 Marek Lindner 996 Email: lindner_marek@yahoo.de 998 Simon Wunderlich 1000 Email: siwu@hrz.tu-chemnitz.de 1002 Full Copyright Statement 1004 Copyright (C) The IETF Trust (2008). 1006 This document is subject to the rights, licenses and restrictions 1007 contained in BCP 78, and except as set forth therein, the authors 1008 retain all their rights. 1010 This document and the information contained herein are provided on an 1011 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1012 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1013 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1014 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1015 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1016 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1018 Intellectual Property 1020 The IETF takes no position regarding the validity or scope of any 1021 Intellectual Property Rights or other rights that might be claimed to 1022 pertain to the implementation or use of the technology described in 1023 this document or the extent to which any license under such rights 1024 might or might not be available; nor does it represent that it has 1025 made any independent effort to identify any such rights. Information 1026 on the procedures with respect to rights in RFC documents can be 1027 found in BCP 78 and BCP 79. 1029 Copies of IPR disclosures made to the IETF Secretariat and any 1030 assurances of licenses to be made available, or the result of an 1031 attempt made to obtain a general license or permission for the use of 1032 such proprietary rights by implementers or users of this 1033 specification can be obtained from the IETF on-line IPR repository at 1034 http://www.ietf.org/ipr. 1036 The IETF invites any interested party to bring to its attention any 1037 copyrights, patents or patent applications, or other proprietary 1038 rights that may cover technology that may be required to implement 1039 this standard. Please address the information to the IETF at 1040 ietf-ipr@ietf.org. 1042 Acknowledgment 1044 Funding for the RFC Editor function is provided by the IETF 1045 Administrative Support Activity (IASA).