idnits 2.17.1 draft-schulte-amp-mesh-protocol-00.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 doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (28 April 2021) is 1093 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. S. Schulte 3 Internet-Draft Technische Universitaet Berlin 4 Intended status: Experimental 28 April 2021 5 Expires: 30 October 2021 7 AMP Mesh Protocol 8 draft-schulte-amp-mesh-protocol-00 10 Abstract 12 This memo describes a decentralized multi-domain mesh networking 13 protocol for low power embedded systems. Its decentralized 14 architecture allows for large scale dynamic topologies across 15 multiple wireless domains. The protocol is optimized for low power 16 wireless devices by using zero-maintenance addressing algorithms. A 17 decentralized ad-hoc reactive routing algorithm enables fast route 18 convergence with low communication overhead. 20 Status of This Memo 22 This Internet-Draft is submitted 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 https://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 30 October 2021. 37 Copyright Notice 39 Copyright (c) 2021 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 (https://trustee.ietf.org/ 44 license-info) in effect on the date of publication of this document. 45 Please review these documents carefully, as they describe your rights 46 and restrictions with respect to this document. 48 Table of Contents 50 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 51 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . 3 52 1.2. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 3 53 1.3. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 4 54 1.4. AMP Terminology . . . . . . . . . . . . . . . . . . . . . 4 55 1.5. Requirements Language . . . . . . . . . . . . . . . . . . 5 56 2. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 5 57 2.1. Operating Environment . . . . . . . . . . . . . . . . . . 5 58 2.2. Relation to other Protocols . . . . . . . . . . . . . . . 5 59 2.3. Addressing . . . . . . . . . . . . . . . . . . . . . . . 6 60 2.3.1. Address Format and Notation . . . . . . . . . . . . . 7 61 2.3.2. Domain Separation . . . . . . . . . . . . . . . . . . 7 62 2.3.3. Address Acquisition on Boot (ZAL/AQ) . . . . . . . . 8 63 2.3.4. Address Allocation (ZAL/AL) . . . . . . . . . . . . . 9 64 2.3.5. Address Space Rebalancing (ZAL/DE) . . . . . . . . . 10 65 2.3.6. Address Revocation . . . . . . . . . . . . . . . . . 11 66 2.4. Routing . . . . . . . . . . . . . . . . . . . . . . . . . 12 67 2.4.1. Route Detection . . . . . . . . . . . . . . . . . . . 12 68 2.4.2. Route Updates . . . . . . . . . . . . . . . . . . . . 13 69 2.4.3. Route Removal . . . . . . . . . . . . . . . . . . . . 13 70 2.4.4. Forwarding . . . . . . . . . . . . . . . . . . . . . 13 71 2.5. Datagrams . . . . . . . . . . . . . . . . . . . . . . . . 14 72 2.6. Gateways . . . . . . . . . . . . . . . . . . . . . . . . 15 73 3. Message Specification . . . . . . . . . . . . . . . . . . . . 15 74 3.1. Message Header . . . . . . . . . . . . . . . . . . . . . 16 75 3.2. Addressing Messages . . . . . . . . . . . . . . . . . . . 17 76 3.2.1. POOL_ADVERTISEMENT . . . . . . . . . . . . . . . . . 17 77 3.2.2. POOL_ACCEPTED . . . . . . . . . . . . . . . . . . . . 18 78 3.2.3. POOL_ASSIGNED . . . . . . . . . . . . . . . . . . . . 18 79 3.2.4. POOL_REVOKED . . . . . . . . . . . . . . . . . . . . 19 80 3.2.5. BIN_CAPACITY_REQUEST . . . . . . . . . . . . . . . . 19 81 3.2.6. BIN_CAPACITY_REPLY . . . . . . . . . . . . . . . . . 19 82 3.3. Control Messages . . . . . . . . . . . . . . . . . . . . 20 83 3.3.1. HELLO . . . . . . . . . . . . . . . . . . . . . . . . 20 84 3.3.2. GOODBYE . . . . . . . . . . . . . . . . . . . . . . . 20 85 3.3.3. GOODBYE_ACK . . . . . . . . . . . . . . . . . . . . . 20 86 3.4. Data Messages . . . . . . . . . . . . . . . . . . . . . . 20 87 3.4.1. DATAGRAM . . . . . . . . . . . . . . . . . . . . . . 21 88 3.4.2. ACKNOWLEDGED_DATAGRAM . . . . . . . . . . . . . . . . 21 89 3.4.3. DATAGRAM_ACK . . . . . . . . . . . . . . . . . . . . 22 90 3.5. Routing Messages . . . . . . . . . . . . . . . . . . . . 22 91 3.5.1. ROUTE_DISCOVERY . . . . . . . . . . . . . . . . . . . 22 92 3.5.2. ROUTE_REPLY . . . . . . . . . . . . . . . . . . . . . 22 93 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 94 5. Security Considerations . . . . . . . . . . . . . . . . . . . 23 95 5.1. Out-of-Scope Attacks . . . . . . . . . . . . . . . . . . 23 96 5.2. Denial of Service Attacks . . . . . . . . . . . . . . . . 23 97 5.3. Attacks on the Addressing Algorithm . . . . . . . . . . . 24 98 5.4. Attacks on the Routing Algorithm . . . . . . . . . . . . 24 99 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 24 100 6.1. Normative References . . . . . . . . . . . . . . . . . . 24 101 6.2. Informative References . . . . . . . . . . . . . . . . . 25 102 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 25 104 1. Introduction 106 1.1. Motivation 108 Our modern society is heavily influenced by ubiquitous embedded 109 computing devices. Wearables, smart home, or manufacturing devices 110 are quite useful on their own, but only live up to their full 111 potential, when they start to communicate with other devices. 112 Communication between embedded devices is what makes automated homes, 113 buildings, or factories smart. Autonomous communication enables the 114 devices to form a larger system-of-systems. Aggregation of 115 information from the entire communication domain enables the system 116 to be aware of its environment and react to it. 118 Embedded devices often communicate wireless, using technologies such 119 as WLAN, Bluetooth, or IEEE 802.15.4 based protocols. These 120 communication stacks are designed and optimized for specific use 121 cases and environments. In large systems, such as smart factories, 122 many fundamentally different device classes might be used. This can 123 range from handbeld mobile devices to large manufacurting equipment. 124 These have different communication requirements and therefore use 125 different technologies. This document proposes a dedicated 126 networking protocol for wireless embedded devices to enable efficient 127 on-site inter-domain communication. 129 1.2. Scope 131 The AMP Mesh Protocol (AMP) is designed to facilitate the formation 132 of a dynamic and self optimizing ad-hoc network across wireless 133 domains. It is therefore a layer 3 networking protocol. AMP 134 transports connection-less datagrams between individual nodes. The 135 protocol focuses on two main features: addressing and routing. 137 The protocol adheres to the ISO/OSI layers and does not depend on, or 138 use, any TCP/IP technology. Features like fragmentation, congestion 139 control, or Quality-of-Service guarantees are not part of the 140 protocol and left to other layers. The same is true for name 141 resolution and node or service discovery. 143 1.3. Interfaces 145 To ensure broad compatibility, AMP demands only basic features of the 146 data link layer. It must provide bidirectional connectivity between 147 neighboring nodes. There needs to be an automatically maintained 148 link state for each connection. Each frame on that link must be able 149 to transport 1024 bytes. Optionally, the data-link layer may provide 150 a leader-election mechanism to be used in address distribution. 152 AMP provides multiple services to upper layers. Each node is 153 assigned a unique address in the network upon boot. The protocol 154 provides the information if a remote node with a certain address is 155 reachable through the network, as well as it's distance as hop count. 156 Datagrams can be sent with an optional acknowledgment. 158 1.4. AMP Terminology 160 Node: A computing device, participating in the network with an 161 assigned address. A single physical system may incorporate 162 multiple virtual nodes. 164 Domain: From AMP's perspective, a domain is any set of nodes, 165 connected via the same data link layer. This may be for example a 166 WLAN network, a Bluetooth Mesh, or a wired bus. 168 Gateway: A gateway consists of two nodes from different domains. 169 They share a common layer 2 technology to transparently transfer 170 messages between domains. A gateway may be a single physical 171 device with multiple interfaces. 173 Layer: Layers are to be interpreted as in the ISO/OSI convention. 175 Address: An address is a unique identifier assigned to a node in 176 the network. AMP defines its own address format. 178 Address Pool: An address pool describes a range of addresses. A 179 pool is defined by a start address and the address count, i.e. the 180 pool size. 182 Parent: In the scope of address assignment (ZAL/AQ and ZAL/DE), a 183 parent is the node assigning address pools to a child. 185 Child: In the scope of address assignment (ZAL/AQ and ZAL/DE), a 186 child is a node requesting address pools from potential parents. 188 Bin: In scope of distribution equalisation (ZAL/DE), a bin are the 189 nodes within signal transmission ranges of each other, i.e. the 190 immediate neighbors of a node. 192 1.5. Requirements Language 194 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 195 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 196 document are to be interpreted as described in RFC 2119 [1]. 198 2. Protocol Operation 200 2.1. Operating Environment 202 To enable the protocol to be used in a broad variety of environments, 203 it does not require any specific topology of the used data link 204 layers. The data link layer must provide a bidirectional link 205 between neighboring nodes. 207 AMP operates on an undirected, connected, and finite graph. The 208 preferred topology is a sparse mesh. Within a given scope, there 209 only ever exists one network. There is no concept of subnets, 210 partitions, or merges. 212 All nodes in the network are created equal. The network is fully 213 decentralized and does not rely on the services of single nodes. 214 There is no central coordinator. All algorithms are fully 215 distributed. 217 The network is self-configuring and self-healing. Nodes may join or 218 leave the network at runtime. Links between nodes may be formed or 219 dropped at will. Nodes are expected to be nomadic: They may change 220 their position, address, and connectivity in the network, but not 221 very frequently. The routing algorithm reacts to topology changes. 222 Addresses may be assigned and revoked at any time. 224 Adhering to the best-effort principle, all nodes should execute the 225 required networking operations to their best of ability. The network 226 relies on the cooperation of all nodes. It uses the least amount of 227 messages, i.e. is most efficient, when all nodes implement the full 228 standard. 230 2.2. Relation to other Protocols 232 AMP is an overlay network, specifically designed to be used atop a 233 wide variety of communication technologies. It is not exclusively 234 bound to use classic link-layer technologies. AMP messages may for 235 example be transported via Ethernet, IP, or ZigBee. In the scope of 236 this document, technologies used for data transmission are refered to 237 as "layer 2" or "data link layer". Gateways translate between these 238 incompatible domains. Gateways are nodes that happen to have more 239 than one communication interface. 241 +-----------+ +-----------+ 242 | Layer 4 | | Layer 4 | 243 +----+------+ +-----^-----+ 244 | | 245 +----v-------+ +------------+ +-----+-----+ 246 | AMP | | AMP | | AMP | 247 +-----------++ +-^---------++ +-----^-----+ 248 | | | | 249 +--------+ +v------+-----+ +v----------+-----+ 250 |Layer 2A| | Gateway | | Layer 2B | 251 +--------+ +-------------+ +-----------------+ 253 Figure 1: Layers and Gateways 255 Figure 1 shows a message-flow between two nodes in separate domains. 256 The data is transferred between domains via the gateway medium. 258 2.3. Addressing 260 One of AMP's core features is addressing. This does include the 261 address format a well as the assignment and management mechanisms. 262 These mechanisms are fully distributed throughout the network. To 263 minimize the number of transferred messages, the "Zero-Maintenance 264 Address Allocation" (ZAL) algorithms by Hu and Li are applied [4]. 265 The paper describes three algorithms to manage address space in a 266 network: Address Allocation (ZAL/AL), Address Acquisition (ZAL/AQ), 267 and Distribution Equalization (ZAL/DE). 269 Following the ZAL approach, address assignment is done in a 270 decentralized manner, using as few messages as possible. Upon boot, 271 a node has no address. To participate in the network a node requests 272 the assignment of an address pool from its neighbors (ZAL/AQ). 273 Available address pools are selected and assigned (ZAL/AL). This 274 process continues recursively, so each node re-distributes its 275 assigned address space to child nodes. Address pools are leased to a 276 child as long as the link, via which the assignment was performed, is 277 active. If the number of available addresses in a section of the 278 network falls under the specified limit, the distribution 279 equalization (ZAL/DE) algorithm is triggered. If none of the 280 neighboring nodes has assignable address space, the child assigns a 281 random temporary address with the reserved prefix to itself (see 282 Section 3). 284 Address assignment starts from an an initial node, which holds the 285 full address pool of the domain. AMP defines the recursive address 286 assignment algorithm. It does explicitly not define how the initial 287 node is selected. The initial node and address space should be 288 configured manually by the network's administrator. Alternatively, 289 the election of the initial node may be done by layer 2. Many 290 protocols such as ZigBee or Bluetooth Mesh have an intrinsic leader 291 which may be used as initial node for the respective domain. The 292 actual address pool should be defined by the administrator. It can 293 optionally be assigned automatically by a deterministic algorithm or 294 an auxiliary protocol. The initial address pool size per domain 295 should be at least 2^32. 297 2.3.1. Address Format and Notation 299 AMP uses 64-bit addresses. This deliberately oversized address space 300 allows for efficient and robust distributed address assignment. 301 Large pool sizes result in a lower risk of address depletion. The 302 probability of duplicated temporary addresses is also reduced 303 greatly. 305 The text representation of AMP addresses follows the same 306 specification as IPv6 addresses as defined in RFC 4291 [2]. The 307 addresses byte values are written in hexadecimal notation and split 308 in 4 blocks of 16 bits, separated by a colon. Addresses with leading 309 zeros should be shortened as described in RFC 4291 [2]. 311 All addresses are uniquely assigned in a network and used for 312 unicast. There are no classes or scopes. With the exception of the 313 following set, all addresses can be assigned. 315 0000:0000:0000:0000 316 Unspecified address: Reserved for Address Acquisition. 318 Is shortened to "::". 320 FFFF:FFFF:FFFF:FFFF 321 Invalid Address. Message must be dropped immediately. 323 FFxx:xxxx:xxxx:xxxx 324 Prefix for temporary addresses. 326 2.3.2. Domain Separation 328 Although an AMP network is always interpreted as a single coherent 329 network, the address assignment algorithm is only ever executed 330 within the boundaries of a domain. Address management messages must 331 not be sent via gateways. 333 This domain separation adds to the robustness of address assignment 334 and revocation: When the node that assigned an address block goes 335 offline, the address pool and all derived child-pools become invalid. 336 When an intermediate node in the addressing tree goes offline, the 337 branch becomes stale and new addresses need to be assigned to the 338 affected nodes. If the initial node, the root of the addressing 339 tree, goes offline, all addresses within the respective domain become 340 stale. A new initial node needs to be selected and new pools need to 341 be assigned throughout the entire domain. Keeping the address 342 assignment within domains reduces the number of necessary 343 reassignments to a confined part of the larger network. 345 2.3.3. Address Acquisition on Boot (ZAL/AQ) 347 Upon boot, a node has neither any knowledge over the network, nor an 348 address. To participate in the network, it needs to acquire an 349 address. 351 The joining node sends HELLO messages via all its available 352 interfaces. Sender and receiver address must be unspecified (::) to 353 indicate a ZAL/AQ request. All potential parent nodes should reply 354 with a set of assignable address pools in a POOL_ADVERTISEMENT 355 message. If a potential parent does not reply within a timeout 356 period, this node should be ignored. The child must choose the 357 advertisement with the highest count of total addresses. If two 358 advertisements offer the same number of addresses, the child may 359 choose between them at will. 361 To accept a set of advertised addresses, the child replies with a 362 POOL_ACCEPTED message to the selected parent. This should be 363 acknowledged by the parent with a POOL_ASSIGNED message. Only when 364 the assignment is explicitly completed, the child must use the 365 advertised address pools. It must not start doing so any sooner. 366 When the POOL_ASSIGNED message is received, the child must assign the 367 lowest of the received addresses to itself. No other address shall 368 be used for communication. When the assignment is complete, the 369 child should send HELLO messages to the remaining neighbors. The 370 sender and receiver address must be populated with the repective 371 addresses. This indicates to the other neighbors, their 372 advertisement was not accepted. After the child has an assigned 373 address, it should recursively advertise and assign address pools 374 itself. 376 If the parent is no longer able to assign the previously advertised 377 address pools, it replies with an empty POOL_ADVERTISEMENT message. 378 In this case the pools must not be used by the child. The child may 379 chose another parent or restart the ZAL/AQ algorithm with new HELLO 380 messages. 382 The POOL_ADVERTISEMENT and POOL_ASSIGNED messages must contain the 383 address of the parent as sender address. This means there is an 384 implicit neighbor discovery mechanism built in to the ZAL/AQ 385 mechanism. The child knows all of its neighbors, since they 386 announced their address in the advertisement. The chosen parent 387 knows that the child did choose the lowest of its assigned addresses. 388 Any remaining nodes should receive a HELLO message with the chosen 389 address. 391 As discussed above, AMP does not define how the initial node and the 392 root address pool in a domain is chosen. When bootstrapping a new 393 domain, the ZAL/AQ algorithm is first executed between the initial 394 node and its neighbors. The algorithm then cascades recursively 395 throughout the entire domain. Nodes with no immediate connection to 396 the initial node send out HELLO messages and reply with empty 397 POOL_ADVERTISEMENT messages. When none of the neighbors replies with 398 a populated advertisement, the child should continue sending HELLO 399 messages periodically. The interval may optionally be increased with 400 a back-off algorithm. This idle state is maintained until one or 401 more neighbors acquired addresses and answer with populated 402 advertisements. Optionally, a node can chose random address from the 403 reserved address space to itself while waiting. 405 When a node receives a HELLO message with a populated sender address 406 and an undefined receiver address from a newly established link, the 407 ZAL/AQ algorithm must not be triggered. This message means that the 408 neighboring node already has an address and simply announces itself. 409 The receiving peer should answer with a fully populated HELLO message 410 to complete the handshake. 412 2.3.4. Address Allocation (ZAL/AL) 414 The ZAL/AQ algorithm discussed above defines the communication 415 pattern between a child and its potential parent. The address 416 allocation algorithm (ZAL/AL) is triggered during this process in the 417 potential parent nodes. It defines how the assignable addresses are 418 safely managed. 420 The algorithm is designed to prevent address duplication. The pools 421 are reserved before they are advertised by the parent. They must 422 only be used by the child when the assignment is completed. If the 423 confirmation message is lost, the reserved pools might be lost. If a 424 link goes down, the child must no longer use the addresses assigned 425 over this link. A parent can therefore safely reassign the pools, 426 without the risk of address duplication. 428 A node holds a list of address pools, it was assigned. Each entry 429 consists of the pool itself and its current state: {AVAILABLE | 430 RESERVED | ASSIGNED}. Derived from this list, the total count of 431 available addresses is known. When an assignment request arrives, 432 half of the available space should reserved for the request. In case 433 of an uneven count, the number must be rounded down. Reservation of 434 addresses should start at the numerically highest available address. 435 Counting down from this highest value, pools are reserved until the 436 desired count is reached. If necessary, a pool in the list is split, 437 to fit the exact count. The state of these pools is changed from 438 AVAILABLE to RESERVED. The reserved pools are then send in an 439 POOL_ADVERTISEMENT message to the requesting node. If there are no 440 addresses available, the advertisement message should be send with 441 empty payload. Address assignment requests should be processed in 442 the order they arrive. 444 If the child answered with a POOL_ACCEPTED message, the state of the 445 address pools is changed from RESERVED to ASSIGNED. The parent 446 completes the process by sending a POOL_ASSIGNED message. This 447 message must only be sent after the internal state is changed. If 448 the child answered with a HELLO message, the advertisement was 449 rejected and the address pools can be assigned to other nodes. The 450 state of the address pools is changed from RESERVED to AVAILABLE. 452 2.3.5. Address Space Rebalancing (ZAL/DE) 454 Even with large address pools, the available space can be depleted 455 quickly in bad conditions. The distribution equalisation (ZAL/DE) 456 algorithm is designed to redistribute address space throughout the 457 domain, if a bin has less available address space than the defined 458 target capacity. 460 The probability of address space depletion is relatively low, 461 especially with large address pool sizes. With the recommended 462 initial pool size of 2^32, the probability is negligible, especially 463 for smaller domains. Even if the address space is depleted in a 464 region of the domain, joining nodes use an address from the reserved 465 pool for temporary addresses. The probability for address 466 duplications is also negligible. The implementation of the ZAL/DE 467 algorithm is therefore optional. The decision to omit this feature 468 should be based on a careful evaluation of the probabilities of 469 depletion for a given use case. 471 The algorithm itself as well as the equations to calculate bin target 472 capacities and probabilities are defined in the paper by Hu and Li 473 [4] and are not reproduced here. Only the AMP specific messages and 474 details are described here. 476 The initialization of ZAL/DE is based on the target bin capacity Se. 477 The value of Se depends on the size of the initial address pool. To 478 eliminate the need to distribute Se throughout the domain, it is set 479 to a fixed value, based on the recommended initial pool size of 2^32. 480 In AMP domains, Se always set to the value 12. 482 As all addressing algorithms, ZAL/DE is only executed within the 483 boundaries of a given domain. Associated messages must not be 484 delivered via gateways. 486 When a bin falls under its target capacity and the ZAL/DE mechanism 487 is triggered, the BIN_CAPACITY_REQUEST and BIN_CAPACITY_REPLY 488 messages are used to determine the distribution of address space. To 489 redistribute address space, the POOL_ADVERTISEMENT, POOL_ACCEPTED, 490 and POOL_ASSIGNED messages are used as described in the ZAL/AQ 491 algorithm. Both source and destination address must be specified at 492 all times. 494 When pools are distributed horizontally through the domain, nodes 495 must keep track from where they received address pools and to where 496 they were assigned. If the link via which a pool was received goes 497 offline, the addresses are no longer valid and need to be revoked. 498 This is done by sending POOL_REVOKED messages to all children, which 499 were assigned addresses from the now invalid pool. The detailed 500 revocation process is described below. 502 2.3.6. Address Revocation 504 There are three ways for addresses to be revoked: Graceful, with 505 either a GOODBYE or a POOL_REVOKED message, or ungraceful, by a link 506 going offline. Revocation means that the revoked address pools are 507 no longer valid and therefore not usable or assignable. Revocations 508 must be forwarded to nodes, that were assigned the revoked addresses. 509 Revocations therefore cascade through the network. Revocations can 510 happen anytime, even during the ZAL/AQ process. 512 Graceful revocation happens with GOODBYE or POOL_REVOKED messages. 513 If a node goes offline in a controlled manner, it must send a GOODBYE 514 message to all its neighbors, informing them of the imminent 515 shutdown. The receiving nodes must revoke the associated address 516 pools and should reply with a GOODBYE_ACK message. The node which is 517 powering down should wait for these acknowledgments. If an neighbor 518 did not acknowledge, the GOODBYE message should be resend after a 519 timeout period. 521 Receiving a POOL_REVOKED message means, an upstream node has gone 522 offline, which invalidated the associated address pools. Child nodes 523 which were assigned the now invalid addresses must immediately be 524 notified with a POOL_REVOKED message. 526 Ungraceful shutdown or connection loss can happen at any time. Since 527 the layer 2 infrastructure is required to maintain and provide a link 528 state, nodes immediately know when a neighbor is no longer available. 529 In this case, all address pools which were assigned over the now 530 unavailable link, are invalid. This is true for pools retrieved via 531 the ZAL/AQ algorithm at startup and redistributed pools via ZAL/DE. 532 POOL_REVOKED messages must be send to the affected neighbors. 534 2.4. Routing 536 AMP uses a decentralized reactive ad-hoc routing algorithm, similar 537 to AODV [3]. The distance vector routing algorithm uses the hop 538 count as metric. A route is represented by its destination, the 539 associated interface, the hop count and a timeout. By using a 540 timeout, unused routes are removed after a while. Also stale routes, 541 where the nodes are no longer active, are eventually removed. The 542 timeout counter is started along with the creation of the route and 543 should be reset, every time a route is used. Nodes start with zero 544 knowledge over the network and continuously build up a routing table 545 on demand. Routing tables are considered volatile and must not be 546 reused when a node restarts, rejoins, or moves within a network. 548 The routing algorithm is designed for low communication overhead, 549 fast convergence and passive route maintenance and optimization. 551 Upon boot, a node initiates the ZAL/AQ algorithm and subsequently 552 knows its immediate neighbors. These are added to the routing table 553 with a hop count of 1. Since the connectivity to the neighbours is 554 monitored via the layer 2 link state, there must not be a timeout for 555 these routes. 557 2.4.1. Route Detection 559 When a node has no route for a desired destination, it should 560 initiate a route discovery. A ROUTE_DISCOVERY message should be send 561 via all interfaces. The destination node should respond with a 562 ROUTE_REPLY. Route discoveries should be flooded by all nodes, but 563 not to the interface it was received from. A node may receive 564 multiple replies on different interfaces. Only the route with the 565 least hops should be kept. If multiple interfaces have the same hop 566 count to a destination, only one should be kept. If no reply to the 567 discovery message was received, the node should not send any data 568 messages to the irresponsive destination address. Optionally, the 569 hop limit of the discovery message can be set to a low count and 570 increased in subsequent runs, to limit the range of the request and 571 therefore the number of generated messages. 573 When a forwardable message is received, the routing table should 574 always be validated against it. This allows for passive route 575 discovery and maintenance. If source address of the message is not 576 known yet, a route should be created. If a route is already known, 577 but the hop count of the received message is lower than the known 578 one, the route should be updated. If a route is used or updated, the 579 timeout should be reset. 581 When a ROUTE_DISCOVERY message is received, the node should add the 582 source address to its routing table. If the source is already 583 present in the routing table, the node should only reply, if the hop 584 count of the discovery message is equal or less than in the existing 585 route. This reduces communication overhead for nonoptimal routes. 587 2.4.2. Route Updates 589 A nodes routing table should be updated with every incoming message, 590 regardless of the type and recipient. If there is no entry for the 591 source-address of the message, a new route with the address, 592 receiving interface, hop count, and a timeout should be created. If 593 there is an entry in the table, the hop count should be validated. 594 If it is lower than the stored value, it should be updated. If the 595 receiving interface is different to the old route, it should also be 596 changed. When a route is used or updated, the timeout should be 597 reset. 599 2.4.3. Route Removal 601 Routes may be deleted on three different occasions: timeout, address 602 revocation, or a link going offline. When a route times out, it 603 should be removed from the table, since it is no longer in active 604 use. When address pools are revoked via a GOODBYE or POOL_REVOKED 605 message, routes to these addresses must be removed. The subsequent 606 assignments are no longer valid and must therefore no longer be 607 forwarded to. When a link goes offline, all routes associated with 608 that interface must be removed. Also routes to addresses which are 609 actively or passively revoked by the link going down must be removed. 611 2.4.4. Forwarding 613 Of the four message categories (see Section 3), only data and route- 614 discovery messages are forwardable. Addressing and control messages 615 must never be forwarded. 617 When a message is received which is not addressed to the receiving 618 node, the message should be forwarded. The messages hop count must 619 be incremented. If a route is found in the local routing table, the 620 timeout of the used route should be reset. The message is then 621 transmitted via the link, associated with the route's interface. If 622 there is no known route for the desired destination, the message 623 should be flooded to all interfaces, except the one, the message was 624 received from. The routing table should be updated before forwarding 625 a message. 627 There are several measures in place to prevent loops, duplicates, and 628 redundant messages: Route discoveries with a higher hop count than 629 the locally stored route should be dropped. If the shortest route to 630 a destination is associated with the same interface a message is 631 received from, the message should be dropped to avoid loops. A node 632 must not initiate a route discovery for a destination of a 633 forwardable message it received. If incrementing the hop count would 634 exceed the hop limit, the message must be dropped. 636 Nodes with tight processing or memory budget may omit the routing 637 algorithm entirely. Instead of selecting the best interface, 638 messages may be flooded via all interfaces. Although this behaviour 639 is legal, it is not recommended, since it produces higher message 640 load on the network. 642 2.5. Datagrams 644 The main purpose of this protocol is the delivery of payload data 645 between nodes. Data is transported in connectionless DATAGRAM 646 messages. Datagrams are standalone messages, comparable to UDP. AMP 647 does not add any further context to the message, other than the 648 header fields needed for the network operation. A datagram can 649 transport up to 1003 bytes of payload. 651 Many applications might rely on a delivery guarantee. To eliminate 652 the need for every application to implement such a mechanism, AMP 653 offers the ACKNOWLEDGED_DATAGRAM. This message adds an 654 identification code to a datagram. When a node receives a 655 ACKNOWLEDGED_DATAGRAM, it should reply with a DATAGRAM_ACK message to 656 the sender. This acknowledges the successful transfer of the 657 datagram, by including the received identification code. The 658 transaction is uniquely identified by the combination of the source 659 address, the destination address, and the identification code. 661 The 16-bit identification code allows for up to 65536 in-flight 662 messages per node pair. The sender must keep track of the used 663 identification codes and ensure their uniqueness. 665 AMP does provide the messages for acknowledgment, but no redelivery 666 or timeout algorithms. The implementation of these mechanisms is 667 left to upper layers or the application itself. 669 2.6. Gateways 671 Gateways are a core component of AMP, enabling inter-domain 672 communication. Gateways consist of two nodes in different domains, 673 connected by a common interface. 675 In the scope of addressing, a gateway link is special and needs to be 676 treated with care. Gateway nodes must be aware of the fact they are 677 a gateway. A gateway link is not part of a domain, addressing 678 messages must therefore not be transmitted via this link. Gateway 679 links must only be used after a node has acquired a valid address. 680 In the scope of routing and forwarding, gateway links are treated as 681 every other link in the network graph. 683 Gateway links may be formed and dropped at any time. To initiate a 684 gateway, a node sends a HELLO message with its source address and 685 unspecified destination address. If the second node replies with a 686 fully populated HELLO message, the neighbor discovery is complete and 687 the gateway is operational. A gateway is terminated, when the link 688 goes offline or one of the nodes sends a GOODBYE message. 690 Gateways may consist of two separate nodes in two domains, connected 691 by a common physical interface. Alternatively a single physical node 692 with interfaces to multiple domains may behave as soft gateway. Data 693 can be transferred internally, instead of a common interface. In any 694 other regard, soft gateways must behave as if they were physically 695 separate nodes. 697 There may be multiple gateways between two domains. This is 698 recommended, since gateways can be a potential bottle-neck and 699 single-point-of failure. More gateways between domains result in a 700 more robust network. 702 3. Message Specification 704 Sets of transmittes bits in the AMP Mesh Protocol are called 705 messages. There are four message classes for different features of 706 the protocol. These message classes, the message header and common 707 features are specified here. 709 The network byte ordering is big-endian. Messages must not be longer 710 than 1024 bytes, including the header. If necessary, zeroes should 711 be added as padding. 713 3.1. Message Header 715 All messages have a common header. It contains the minimal data set 716 needed for the operation of the network. The three header fields 717 required by all messages are the message type, the source address, 718 and destination address. Some message types may add additional 719 header fields and payload. 721 8 Bit 64 Bit 64 Bit max. 1007 Bytes 722 +--------+------------+---------------+----------------------------- 723 | Type | Source | Destination | opt. Headers & Payload ... 724 +--------+------------+---------------+----------------------------- 726 Figure 2: Message Header 728 Type: 729 Unsigned 8-bit integer 731 Specifies the message type 733 Source: 734 Unsigned 64-bit integer 736 Source address of the message 738 Destination: 739 Unsigned 64-bit integer 741 Destination address of the message 743 Payload: 744 Up to 1007 bytes 746 Optional auxiliary headers and payload 748 The first 8 bit define the messages type. The notation for message 749 types is hexadecimal. The first nibble indicates the message class, 750 the second nibble defines the type. This structure allows for future 751 additions. The class distinction in the first nibble using 752 hexadecimal letters also increases readability for humans. 754 After the message type, source and destination address are given as 755 64-bit unsigned integers. If not explicitly stated otherwise in the 756 message specification, both header fields must always be populated 757 with valid addresses. 759 Not all messages add a payload. Some messages, such as HELLO, do not 760 need more data than type and addresses. Detailed specifications for 761 all messages are given below. 763 A distinction is to be made between forwardable and non-forwardable 764 messages. Addressing and control messages must never be forwarded. 765 They are only ever exchanged between neighbors. Address and control 766 messages with other addresses than the two peer's or the unspecified 767 (::) address must be dropped immediately. Data and routing messages 768 may be forwarded. The header must always be fully populated. If it 769 contains an invalid or unspecified address, the message must be 770 dropped immediately. 772 Forwardable messages add hop counter and hop limit fields. The hop 773 counter must start with zero and must be incremented on every hop. 774 If incrementing the hop count would exceed the hop limit, the message 775 must be dropped. 777 3.2. Addressing Messages 779 Addressing messages must only be exchanged between neighboring nodes. 780 Addressing messages must not be forwarded. Source and destination 781 address must only contain the unspecified or the peers' addresses. 783 Addressing messages must never be exchanged over a gateway link. 784 Addressing messages are only valid within the same domain. 786 Addressing messages are identified by a hexadecimal "A" in the high 787 nibble of the message type. 789 3.2.1. POOL_ADVERTISEMENT 791 This message is used in ZAL/AQ and ZAL/DE algorithms. It advertises 792 assignable address pools to a neighboring node. 794 The advertisement adds a list of assignable address pools to the 795 payload of the message. First, the count of message pools is given, 796 then the pools are listed. Each pool is defined by the starting 797 address and the size of the pool. Restricted by the message size, up 798 to 62 address pools can be added. If there are no assignable pools 799 available, the message should be send with an empty payload. 801 If used during the ZAL/AQ algorithm, the destination address must be 802 unspecified. In all other cases, address fields must be populated. 804 The POOL_ADVERTISEMENT adds the following fields to the message: 806 Message type 0xA1 807 Count: 808 Unsigned 8-bit integer 810 Gives the number of message pools 812 1 to 62 message pools, each consisting of: 814 Address pool start address: 815 Unsigned 64-bit integer 817 Address pool size: 818 Unsigned 64-bit integer 820 3.2.2. POOL_ACCEPTED 822 This message is used in ZAL/AQ and ZAL/DE algorithms. It indicates 823 that a node accepted the address pool advertisement of a parent. No 824 additional header fields or payload are added to the message. 826 If used during the ZAL/AQ algorithm, the source address must be 827 unspecified. In all other cases, address fields must be populated. 829 Message type 0xA2 831 3.2.3. POOL_ASSIGNED 833 This message is used in ZAL/AQ and ZAL/DE algorithms. It indicates 834 that address pools are assigned to a child node. 836 Adds a list of the assigned address pools to the payload of the 837 message. This must be the same set of pools as in the original 838 advertisement. First, the count of message pools is given, then the 839 pools are listed. Each pool is defined by the starting address and 840 the size of the pool. Restricted by the message size, up to 62 841 address pools can be added. 843 If used during the ZAL/AQ algorithm, the destination address must be 844 unspecified. In all other cases, address fields must be populated. 846 Message type 0xA3 848 Count: 849 Unsigned 8-bit integer 851 Gives the number of message pools 853 1 to 62 message pools, each consisting of: 855 Address pool start address: 856 Unsigned 64-bit integer 858 Address pool size: 859 Unsigned 64-bit integer 861 3.2.4. POOL_REVOKED 863 Indicates that a set of address pools is no longer valid and 864 routable. Their usage for routing and communication must immediately 865 be stopped. 867 Adds a list of the revoked address pools to the payload of the 868 message. First, the count of message pools is given, then the pools 869 are listed. Each pool is defined by the starting address and the 870 size of the pool. Restricted by the message size, up to 62 address 871 pools can be added. 873 Message type 0xA5 875 Count: 876 Unsigned 8-bit integer 878 Gives the number of message pools 880 1 to 62 message pools, each consisting of: 882 Address pool start address: 883 Unsigned 64-bit integer 885 Address pool size: 886 Unsigned 64-bit integer 888 3.2.5. BIN_CAPACITY_REQUEST 890 This message is used in the ZAL/DE algorithm. It is used to 891 determine the available address space in the local bin. 893 This message type does not add any payload. 895 Message type 0xA5 897 3.2.6. BIN_CAPACITY_REPLY 899 This message is used in the ZAL/DE algorithm. It is a reply to the 900 BIN_CAPACITY_REQUEST. The message adds the amount of available 901 address space as payload. 903 Message type 0xA6 905 Bin capacity: 906 Unsigned 64-bit integer 908 3.3. Control Messages 910 Control messages must not be forwarded. There is no payload in 911 control messages. 913 Control messages are identified by a hexadecimal "C" in the high 914 nibble of the message type. 916 3.3.1. HELLO 918 This message is used by to announce the existence and address of a 919 node to its neighbors. If the source address is empty, the ZAL/AQ 920 algorithm is initiated. 922 This message type does not add any payload. 924 Message type 0xC1 926 3.3.2. GOODBYE 928 This message is used to indicate the graceful shutdown of a node or 929 the termination of a link. 931 This message type does not add any payload. 933 Message type 0xC2 935 3.3.3. GOODBYE_ACK 937 This message is used as acknowledgement for a GOODBYE message, so the 938 retiring node knows that its GOODBYE message was received and 939 processed. 941 This message type does not add any payload. 943 Message type 0xC3 945 3.4. Data Messages 947 Data is transported through the network as datagrams. Data messages 948 are forwardable. They add hop counter and hop limit header fields. 950 Data messages are identified by a hexadecimal "D" in the high nibble 951 of the message type. 953 3.4.1. DATAGRAM 955 This message is used to transport data through the network. 957 Message type 0xD1 959 Hop count: 960 Unsigned 8-bit integer 962 Hop limit: 963 Unsigned 8-bit integer 965 Payload length: 966 Unsigned 16-bit integer 968 Gives the length of the payload in bytes 970 Payload: 971 Up to 1003 bytes of payload 973 3.4.2. ACKNOWLEDGED_DATAGRAM 975 This message adds an identification code to a datagram. This enables 976 the receiver of the message to acknowledge the successful transfer of 977 the message to the sender. The message can be uniquely identified by 978 the combination of source address, destination address, and 979 identification code. 981 Message type 0xD2 983 Hop count: 984 Unsigned 8-bit integer 986 Hop limit: 987 Unsigned 8-bit integer 989 Identification Code: 990 Unsigned 16-bit integer 992 Used to uniquely identify the message 994 Payload length: 995 Unsigned 16-bit integer 997 Gives the length of the payload in bytes 999 Payload: 1000 Up to 1001 bytes of payload 1002 3.4.3. DATAGRAM_ACK 1004 This message is used to acknowledge, that a ACKNOWLEDGED_DATAGRAM was 1005 successfully received. Although this message is in the class of data 1006 messages, it does not add any payload other than the header fields 1007 listed below. 1009 Message type 0xD3 1011 Hop count: 1012 Unsigned 8-bit integer 1014 Hop limit: 1015 Unsigned 8-bit integer 1017 Identification Code: 1018 Unsigned 16-bit integer 1020 Used to uniquely identify the message 1022 3.5. Routing Messages 1024 Routing messages are used to discover routes between two nodes in the 1025 network. Routing messages are forwardable, but do not transport any 1026 payload other than hop counter and hop limit header fields. 1028 Routing messages are identified by a hexadecimal "F" (for "find") in 1029 the high nibble of the message type. 1031 3.5.1. ROUTE_DISCOVERY 1033 This message is used to initiate a route discovery. 1035 Message type 0xF1 1037 Hop count: 1038 Unsigned 8-bit integer 1040 Hop limit: 1041 Unsigned 8-bit integer 1043 3.5.2. ROUTE_REPLY 1045 This message is the reply to a ROUTE_DISCOVERY. The hop limit must 1046 be set equal the hop counter of the received ROUTE_DISCOVERY message. 1048 Message type 0xF2 1050 Hop count: 1051 Unsigned 8-bit integer 1053 Hop limit: 1054 Unsigned 8-bit integer 1056 4. IANA Considerations 1058 This memo includes no request to IANA. 1060 5. Security Considerations 1062 To keep wide compatibility with low power devices, the protocol does 1063 not have any built-in security features. The protocol is therefore 1064 vulnerable to malicious nodes. Both the addressing and the routing 1065 algorithm can be interfered with by modified or malicious messages. 1066 AMP is to be considered inherently insecure. 1068 5.1. Out-of-Scope Attacks 1070 Data integrity is left to the underlying layers. There are no 1071 encryption or authentication features. If needed, they must be added 1072 by higher layers. Without added security by other layers in the 1073 communication stack, AMP is susceptible for eavesdropping, replay, 1074 message insertion, deletion, modification, and man-in-the-middle 1075 attacks. 1077 5.2. Denial of Service Attacks 1079 Both direct and distributed denial of service attacks are possible. 1080 A node can force its direct neighbours to invest memory and 1081 processing resources by sending large datagrams with malicious header 1082 fields. This can be invalid addresses or a hop count/hop limit which 1083 require the message to be dropped. To prevent this attack, the 1084 attacked node can simply drop the connection to the malicious 1085 neighbor. This is fully compliant with the best-effort principle. 1086 The routing algorithm will adapt to the change in topology. 1088 A distributed denial of service attack can be executed by forging the 1089 source address of a ROUTE_REQUEST. When a malicious node sends route 1090 requests to multiple nodes in the network, they all send responses to 1091 the node with the forged source address. This attack is somewhat 1092 dampened by the routing algorithm. ROUTE_REQUEST messages with a 1093 non-ideal route are dropped. A successful DDoS attack therefore 1094 requires inferred knowledge about the networks topology. 1096 The hop limit field can be forged by malicious nodes. If it is set 1097 to a higher value than intended by the sender, this can result in 1098 network congestion. This is especially true for ROUTE_DISCOVERY 1099 messages, which are selectively flooded. This attack is confined to 1100 the boundaries of a domain. 1102 5.3. Attacks on the Addressing Algorithm 1104 The addressing algorithms can be interfered with, by provoking 1105 duplicate addresses. A malicious node can advertise address pools, 1106 which it was not officially assigned. Alternatively, the same pool 1107 can be assigned to multiple nodes. 1109 Address revocations can also be malicious. Therefore messages must 1110 only be processed, if they are received over the link the addresses 1111 were originally assigned over. This contains the impact of a 1112 misbehaving node to a single branch of the addressing tree. 1114 5.4. Attacks on the Routing Algorithm 1116 Manipulated hop count header fields can interfere with the routing 1117 algorithm. Off-path attackers can direct selected message flow 1118 towards them by decrementing the hop count, which enables MITM 1119 attacks. 1121 Maliciously incremented hop counts can lead to route diversions. 1122 Traffic can be diverted to other parts of the network, which can 1123 result in higher overall network load and lead to congestion. This 1124 attack requires at least some knowledge over the networks topology. 1126 6. References 1128 6.1. Normative References 1130 [1] Bradner, S., "Key words for use in RFCs to Indicate 1131 Requirement Levels", BCP 14, RFC 2119, 1132 DOI 10.17487/RFC2119, March 1997, 1133 . 1135 [2] Hinden, R. and S. Deering, "IP Version 6 Addressing 1136 Architecture", RFC 4291, DOI 10.17487/RFC4291, February 1137 2006, . 1139 [3] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 1140 Demand Distance Vector (AODV) Routing", RFC 3561, 1141 DOI 10.17487/RFC3561, July 2003, 1142 . 1144 6.2. Informative References 1146 [4] Hu, Z. H. and B. L. Li, "ZAL: Zero-Maintenance Address 1147 Allocation in Mobile Wireless Ad Hoc Networks", March 1148 2005, . 1150 Author's Address 1152 Aljoscha Schulte 1153 Technische Universitaet Berlin 1155 Email: a.schulte@tu-berlin.de