Internet DRAFT - draft-schulte-amp-mesh-protocol
draft-schulte-amp-mesh-protocol
Network Working Group A. S. Schulte
Internet-Draft Technische Universitaet Berlin
Intended status: Experimental 28 April 2021
Expires: 30 October 2021
AMP Mesh Protocol
draft-schulte-amp-mesh-protocol-00
Abstract
This memo describes a decentralized multi-domain mesh networking
protocol for low power embedded systems. Its decentralized
architecture allows for large scale dynamic topologies across
multiple wireless domains. The protocol is optimized for low power
wireless devices by using zero-maintenance addressing algorithms. A
decentralized ad-hoc reactive routing algorithm enables fast route
convergence with low communication overhead.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 30 October 2021.
Copyright Notice
Copyright (c) 2021 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Schulte Expires 30 October 2021 [Page 1]
Internet-Draft AMP April 2021
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 4
1.4. AMP Terminology . . . . . . . . . . . . . . . . . . . . . 4
1.5. Requirements Language . . . . . . . . . . . . . . . . . . 5
2. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 5
2.1. Operating Environment . . . . . . . . . . . . . . . . . . 5
2.2. Relation to other Protocols . . . . . . . . . . . . . . . 5
2.3. Addressing . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.1. Address Format and Notation . . . . . . . . . . . . . 7
2.3.2. Domain Separation . . . . . . . . . . . . . . . . . . 7
2.3.3. Address Acquisition on Boot (ZAL/AQ) . . . . . . . . 8
2.3.4. Address Allocation (ZAL/AL) . . . . . . . . . . . . . 9
2.3.5. Address Space Rebalancing (ZAL/DE) . . . . . . . . . 10
2.3.6. Address Revocation . . . . . . . . . . . . . . . . . 11
2.4. Routing . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4.1. Route Detection . . . . . . . . . . . . . . . . . . . 12
2.4.2. Route Updates . . . . . . . . . . . . . . . . . . . . 13
2.4.3. Route Removal . . . . . . . . . . . . . . . . . . . . 13
2.4.4. Forwarding . . . . . . . . . . . . . . . . . . . . . 13
2.5. Datagrams . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6. Gateways . . . . . . . . . . . . . . . . . . . . . . . . 15
3. Message Specification . . . . . . . . . . . . . . . . . . . . 15
3.1. Message Header . . . . . . . . . . . . . . . . . . . . . 16
3.2. Addressing Messages . . . . . . . . . . . . . . . . . . . 17
3.2.1. POOL_ADVERTISEMENT . . . . . . . . . . . . . . . . . 17
3.2.2. POOL_ACCEPTED . . . . . . . . . . . . . . . . . . . . 18
3.2.3. POOL_ASSIGNED . . . . . . . . . . . . . . . . . . . . 18
3.2.4. POOL_REVOKED . . . . . . . . . . . . . . . . . . . . 19
3.2.5. BIN_CAPACITY_REQUEST . . . . . . . . . . . . . . . . 19
3.2.6. BIN_CAPACITY_REPLY . . . . . . . . . . . . . . . . . 19
3.3. Control Messages . . . . . . . . . . . . . . . . . . . . 20
3.3.1. HELLO . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3.2. GOODBYE . . . . . . . . . . . . . . . . . . . . . . . 20
3.3.3. GOODBYE_ACK . . . . . . . . . . . . . . . . . . . . . 20
3.4. Data Messages . . . . . . . . . . . . . . . . . . . . . . 20
3.4.1. DATAGRAM . . . . . . . . . . . . . . . . . . . . . . 21
3.4.2. ACKNOWLEDGED_DATAGRAM . . . . . . . . . . . . . . . . 21
3.4.3. DATAGRAM_ACK . . . . . . . . . . . . . . . . . . . . 22
3.5. Routing Messages . . . . . . . . . . . . . . . . . . . . 22
3.5.1. ROUTE_DISCOVERY . . . . . . . . . . . . . . . . . . . 22
3.5.2. ROUTE_REPLY . . . . . . . . . . . . . . . . . . . . . 22
4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23
5. Security Considerations . . . . . . . . . . . . . . . . . . . 23
5.1. Out-of-Scope Attacks . . . . . . . . . . . . . . . . . . 23
Schulte Expires 30 October 2021 [Page 2]
Internet-Draft AMP April 2021
5.2. Denial of Service Attacks . . . . . . . . . . . . . . . . 23
5.3. Attacks on the Addressing Algorithm . . . . . . . . . . . 24
5.4. Attacks on the Routing Algorithm . . . . . . . . . . . . 24
6. References . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.1. Normative References . . . . . . . . . . . . . . . . . . 24
6.2. Informative References . . . . . . . . . . . . . . . . . 25
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 25
1. Introduction
1.1. Motivation
Our modern society is heavily influenced by ubiquitous embedded
computing devices. Wearables, smart home, or manufacturing devices
are quite useful on their own, but only live up to their full
potential, when they start to communicate with other devices.
Communication between embedded devices is what makes automated homes,
buildings, or factories smart. Autonomous communication enables the
devices to form a larger system-of-systems. Aggregation of
information from the entire communication domain enables the system
to be aware of its environment and react to it.
Embedded devices often communicate wireless, using technologies such
as WLAN, Bluetooth, or IEEE 802.15.4 based protocols. These
communication stacks are designed and optimized for specific use
cases and environments. In large systems, such as smart factories,
many fundamentally different device classes might be used. This can
range from handbeld mobile devices to large manufacurting equipment.
These have different communication requirements and therefore use
different technologies. This document proposes a dedicated
networking protocol for wireless embedded devices to enable efficient
on-site inter-domain communication.
1.2. Scope
The AMP Mesh Protocol (AMP) is designed to facilitate the formation
of a dynamic and self optimizing ad-hoc network across wireless
domains. It is therefore a layer 3 networking protocol. AMP
transports connection-less datagrams between individual nodes. The
protocol focuses on two main features: addressing and routing.
The protocol adheres to the ISO/OSI layers and does not depend on, or
use, any TCP/IP technology. Features like fragmentation, congestion
control, or Quality-of-Service guarantees are not part of the
protocol and left to other layers. The same is true for name
resolution and node or service discovery.
Schulte Expires 30 October 2021 [Page 3]
Internet-Draft AMP April 2021
1.3. Interfaces
To ensure broad compatibility, AMP demands only basic features of the
data link layer. It must provide bidirectional connectivity between
neighboring nodes. There needs to be an automatically maintained
link state for each connection. Each frame on that link must be able
to transport 1024 bytes. Optionally, the data-link layer may provide
a leader-election mechanism to be used in address distribution.
AMP provides multiple services to upper layers. Each node is
assigned a unique address in the network upon boot. The protocol
provides the information if a remote node with a certain address is
reachable through the network, as well as it's distance as hop count.
Datagrams can be sent with an optional acknowledgment.
1.4. AMP Terminology
Node: A computing device, participating in the network with an
assigned address. A single physical system may incorporate
multiple virtual nodes.
Domain: From AMP's perspective, a domain is any set of nodes,
connected via the same data link layer. This may be for example a
WLAN network, a Bluetooth Mesh, or a wired bus.
Gateway: A gateway consists of two nodes from different domains.
They share a common layer 2 technology to transparently transfer
messages between domains. A gateway may be a single physical
device with multiple interfaces.
Layer: Layers are to be interpreted as in the ISO/OSI convention.
Address: An address is a unique identifier assigned to a node in
the network. AMP defines its own address format.
Address Pool: An address pool describes a range of addresses. A
pool is defined by a start address and the address count, i.e. the
pool size.
Parent: In the scope of address assignment (ZAL/AQ and ZAL/DE), a
parent is the node assigning address pools to a child.
Child: In the scope of address assignment (ZAL/AQ and ZAL/DE), a
child is a node requesting address pools from potential parents.
Bin: In scope of distribution equalisation (ZAL/DE), a bin are the
nodes within signal transmission ranges of each other, i.e. the
immediate neighbors of a node.
Schulte Expires 30 October 2021 [Page 4]
Internet-Draft AMP April 2021
1.5. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [1].
2. Protocol Operation
2.1. Operating Environment
To enable the protocol to be used in a broad variety of environments,
it does not require any specific topology of the used data link
layers. The data link layer must provide a bidirectional link
between neighboring nodes.
AMP operates on an undirected, connected, and finite graph. The
preferred topology is a sparse mesh. Within a given scope, there
only ever exists one network. There is no concept of subnets,
partitions, or merges.
All nodes in the network are created equal. The network is fully
decentralized and does not rely on the services of single nodes.
There is no central coordinator. All algorithms are fully
distributed.
The network is self-configuring and self-healing. Nodes may join or
leave the network at runtime. Links between nodes may be formed or
dropped at will. Nodes are expected to be nomadic: They may change
their position, address, and connectivity in the network, but not
very frequently. The routing algorithm reacts to topology changes.
Addresses may be assigned and revoked at any time.
Adhering to the best-effort principle, all nodes should execute the
required networking operations to their best of ability. The network
relies on the cooperation of all nodes. It uses the least amount of
messages, i.e. is most efficient, when all nodes implement the full
standard.
2.2. Relation to other Protocols
AMP is an overlay network, specifically designed to be used atop a
wide variety of communication technologies. It is not exclusively
bound to use classic link-layer technologies. AMP messages may for
example be transported via Ethernet, IP, or ZigBee. In the scope of
this document, technologies used for data transmission are refered to
as "layer 2" or "data link layer". Gateways translate between these
incompatible domains. Gateways are nodes that happen to have more
than one communication interface.
Schulte Expires 30 October 2021 [Page 5]
Internet-Draft AMP April 2021
+-----------+ +-----------+
| Layer 4 | | Layer 4 |
+----+------+ +-----^-----+
| |
+----v-------+ +------------+ +-----+-----+
| AMP | | AMP | | AMP |
+-----------++ +-^---------++ +-----^-----+
| | | |
+--------+ +v------+-----+ +v----------+-----+
|Layer 2A| | Gateway | | Layer 2B |
+--------+ +-------------+ +-----------------+
Figure 1: Layers and Gateways
Figure 1 shows a message-flow between two nodes in separate domains.
The data is transferred between domains via the gateway medium.
2.3. Addressing
One of AMP's core features is addressing. This does include the
address format a well as the assignment and management mechanisms.
These mechanisms are fully distributed throughout the network. To
minimize the number of transferred messages, the "Zero-Maintenance
Address Allocation" (ZAL) algorithms by Hu and Li are applied [4].
The paper describes three algorithms to manage address space in a
network: Address Allocation (ZAL/AL), Address Acquisition (ZAL/AQ),
and Distribution Equalization (ZAL/DE).
Following the ZAL approach, address assignment is done in a
decentralized manner, using as few messages as possible. Upon boot,
a node has no address. To participate in the network a node requests
the assignment of an address pool from its neighbors (ZAL/AQ).
Available address pools are selected and assigned (ZAL/AL). This
process continues recursively, so each node re-distributes its
assigned address space to child nodes. Address pools are leased to a
child as long as the link, via which the assignment was performed, is
active. If the number of available addresses in a section of the
network falls under the specified limit, the distribution
equalization (ZAL/DE) algorithm is triggered. If none of the
neighboring nodes has assignable address space, the child assigns a
random temporary address with the reserved prefix to itself (see
Section 3).
Address assignment starts from an an initial node, which holds the
full address pool of the domain. AMP defines the recursive address
assignment algorithm. It does explicitly not define how the initial
node is selected. The initial node and address space should be
configured manually by the network's administrator. Alternatively,
Schulte Expires 30 October 2021 [Page 6]
Internet-Draft AMP April 2021
the election of the initial node may be done by layer 2. Many
protocols such as ZigBee or Bluetooth Mesh have an intrinsic leader
which may be used as initial node for the respective domain. The
actual address pool should be defined by the administrator. It can
optionally be assigned automatically by a deterministic algorithm or
an auxiliary protocol. The initial address pool size per domain
should be at least 2^32.
2.3.1. Address Format and Notation
AMP uses 64-bit addresses. This deliberately oversized address space
allows for efficient and robust distributed address assignment.
Large pool sizes result in a lower risk of address depletion. The
probability of duplicated temporary addresses is also reduced
greatly.
The text representation of AMP addresses follows the same
specification as IPv6 addresses as defined in RFC 4291 [2]. The
addresses byte values are written in hexadecimal notation and split
in 4 blocks of 16 bits, separated by a colon. Addresses with leading
zeros should be shortened as described in RFC 4291 [2].
All addresses are uniquely assigned in a network and used for
unicast. There are no classes or scopes. With the exception of the
following set, all addresses can be assigned.
0000:0000:0000:0000
Unspecified address: Reserved for Address Acquisition.
Is shortened to "::".
FFFF:FFFF:FFFF:FFFF
Invalid Address. Message must be dropped immediately.
FFxx:xxxx:xxxx:xxxx
Prefix for temporary addresses.
2.3.2. Domain Separation
Although an AMP network is always interpreted as a single coherent
network, the address assignment algorithm is only ever executed
within the boundaries of a domain. Address management messages must
not be sent via gateways.
This domain separation adds to the robustness of address assignment
and revocation: When the node that assigned an address block goes
offline, the address pool and all derived child-pools become invalid.
When an intermediate node in the addressing tree goes offline, the
Schulte Expires 30 October 2021 [Page 7]
Internet-Draft AMP April 2021
branch becomes stale and new addresses need to be assigned to the
affected nodes. If the initial node, the root of the addressing
tree, goes offline, all addresses within the respective domain become
stale. A new initial node needs to be selected and new pools need to
be assigned throughout the entire domain. Keeping the address
assignment within domains reduces the number of necessary
reassignments to a confined part of the larger network.
2.3.3. Address Acquisition on Boot (ZAL/AQ)
Upon boot, a node has neither any knowledge over the network, nor an
address. To participate in the network, it needs to acquire an
address.
The joining node sends HELLO messages via all its available
interfaces. Sender and receiver address must be unspecified (::) to
indicate a ZAL/AQ request. All potential parent nodes should reply
with a set of assignable address pools in a POOL_ADVERTISEMENT
message. If a potential parent does not reply within a timeout
period, this node should be ignored. The child must choose the
advertisement with the highest count of total addresses. If two
advertisements offer the same number of addresses, the child may
choose between them at will.
To accept a set of advertised addresses, the child replies with a
POOL_ACCEPTED message to the selected parent. This should be
acknowledged by the parent with a POOL_ASSIGNED message. Only when
the assignment is explicitly completed, the child must use the
advertised address pools. It must not start doing so any sooner.
When the POOL_ASSIGNED message is received, the child must assign the
lowest of the received addresses to itself. No other address shall
be used for communication. When the assignment is complete, the
child should send HELLO messages to the remaining neighbors. The
sender and receiver address must be populated with the repective
addresses. This indicates to the other neighbors, their
advertisement was not accepted. After the child has an assigned
address, it should recursively advertise and assign address pools
itself.
If the parent is no longer able to assign the previously advertised
address pools, it replies with an empty POOL_ADVERTISEMENT message.
In this case the pools must not be used by the child. The child may
chose another parent or restart the ZAL/AQ algorithm with new HELLO
messages.
The POOL_ADVERTISEMENT and POOL_ASSIGNED messages must contain the
address of the parent as sender address. This means there is an
implicit neighbor discovery mechanism built in to the ZAL/AQ
Schulte Expires 30 October 2021 [Page 8]
Internet-Draft AMP April 2021
mechanism. The child knows all of its neighbors, since they
announced their address in the advertisement. The chosen parent
knows that the child did choose the lowest of its assigned addresses.
Any remaining nodes should receive a HELLO message with the chosen
address.
As discussed above, AMP does not define how the initial node and the
root address pool in a domain is chosen. When bootstrapping a new
domain, the ZAL/AQ algorithm is first executed between the initial
node and its neighbors. The algorithm then cascades recursively
throughout the entire domain. Nodes with no immediate connection to
the initial node send out HELLO messages and reply with empty
POOL_ADVERTISEMENT messages. When none of the neighbors replies with
a populated advertisement, the child should continue sending HELLO
messages periodically. The interval may optionally be increased with
a back-off algorithm. This idle state is maintained until one or
more neighbors acquired addresses and answer with populated
advertisements. Optionally, a node can chose random address from the
reserved address space to itself while waiting.
When a node receives a HELLO message with a populated sender address
and an undefined receiver address from a newly established link, the
ZAL/AQ algorithm must not be triggered. This message means that the
neighboring node already has an address and simply announces itself.
The receiving peer should answer with a fully populated HELLO message
to complete the handshake.
2.3.4. Address Allocation (ZAL/AL)
The ZAL/AQ algorithm discussed above defines the communication
pattern between a child and its potential parent. The address
allocation algorithm (ZAL/AL) is triggered during this process in the
potential parent nodes. It defines how the assignable addresses are
safely managed.
The algorithm is designed to prevent address duplication. The pools
are reserved before they are advertised by the parent. They must
only be used by the child when the assignment is completed. If the
confirmation message is lost, the reserved pools might be lost. If a
link goes down, the child must no longer use the addresses assigned
over this link. A parent can therefore safely reassign the pools,
without the risk of address duplication.
A node holds a list of address pools, it was assigned. Each entry
consists of the pool itself and its current state: {AVAILABLE |
RESERVED | ASSIGNED}. Derived from this list, the total count of
available addresses is known. When an assignment request arrives,
half of the available space should reserved for the request. In case
Schulte Expires 30 October 2021 [Page 9]
Internet-Draft AMP April 2021
of an uneven count, the number must be rounded down. Reservation of
addresses should start at the numerically highest available address.
Counting down from this highest value, pools are reserved until the
desired count is reached. If necessary, a pool in the list is split,
to fit the exact count. The state of these pools is changed from
AVAILABLE to RESERVED. The reserved pools are then send in an
POOL_ADVERTISEMENT message to the requesting node. If there are no
addresses available, the advertisement message should be send with
empty payload. Address assignment requests should be processed in
the order they arrive.
If the child answered with a POOL_ACCEPTED message, the state of the
address pools is changed from RESERVED to ASSIGNED. The parent
completes the process by sending a POOL_ASSIGNED message. This
message must only be sent after the internal state is changed. If
the child answered with a HELLO message, the advertisement was
rejected and the address pools can be assigned to other nodes. The
state of the address pools is changed from RESERVED to AVAILABLE.
2.3.5. Address Space Rebalancing (ZAL/DE)
Even with large address pools, the available space can be depleted
quickly in bad conditions. The distribution equalisation (ZAL/DE)
algorithm is designed to redistribute address space throughout the
domain, if a bin has less available address space than the defined
target capacity.
The probability of address space depletion is relatively low,
especially with large address pool sizes. With the recommended
initial pool size of 2^32, the probability is negligible, especially
for smaller domains. Even if the address space is depleted in a
region of the domain, joining nodes use an address from the reserved
pool for temporary addresses. The probability for address
duplications is also negligible. The implementation of the ZAL/DE
algorithm is therefore optional. The decision to omit this feature
should be based on a careful evaluation of the probabilities of
depletion for a given use case.
The algorithm itself as well as the equations to calculate bin target
capacities and probabilities are defined in the paper by Hu and Li
[4] and are not reproduced here. Only the AMP specific messages and
details are described here.
The initialization of ZAL/DE is based on the target bin capacity Se.
The value of Se depends on the size of the initial address pool. To
eliminate the need to distribute Se throughout the domain, it is set
to a fixed value, based on the recommended initial pool size of 2^32.
In AMP domains, Se always set to the value 12.
Schulte Expires 30 October 2021 [Page 10]
Internet-Draft AMP April 2021
As all addressing algorithms, ZAL/DE is only executed within the
boundaries of a given domain. Associated messages must not be
delivered via gateways.
When a bin falls under its target capacity and the ZAL/DE mechanism
is triggered, the BIN_CAPACITY_REQUEST and BIN_CAPACITY_REPLY
messages are used to determine the distribution of address space. To
redistribute address space, the POOL_ADVERTISEMENT, POOL_ACCEPTED,
and POOL_ASSIGNED messages are used as described in the ZAL/AQ
algorithm. Both source and destination address must be specified at
all times.
When pools are distributed horizontally through the domain, nodes
must keep track from where they received address pools and to where
they were assigned. If the link via which a pool was received goes
offline, the addresses are no longer valid and need to be revoked.
This is done by sending POOL_REVOKED messages to all children, which
were assigned addresses from the now invalid pool. The detailed
revocation process is described below.
2.3.6. Address Revocation
There are three ways for addresses to be revoked: Graceful, with
either a GOODBYE or a POOL_REVOKED message, or ungraceful, by a link
going offline. Revocation means that the revoked address pools are
no longer valid and therefore not usable or assignable. Revocations
must be forwarded to nodes, that were assigned the revoked addresses.
Revocations therefore cascade through the network. Revocations can
happen anytime, even during the ZAL/AQ process.
Graceful revocation happens with GOODBYE or POOL_REVOKED messages.
If a node goes offline in a controlled manner, it must send a GOODBYE
message to all its neighbors, informing them of the imminent
shutdown. The receiving nodes must revoke the associated address
pools and should reply with a GOODBYE_ACK message. The node which is
powering down should wait for these acknowledgments. If an neighbor
did not acknowledge, the GOODBYE message should be resend after a
timeout period.
Receiving a POOL_REVOKED message means, an upstream node has gone
offline, which invalidated the associated address pools. Child nodes
which were assigned the now invalid addresses must immediately be
notified with a POOL_REVOKED message.
Ungraceful shutdown or connection loss can happen at any time. Since
the layer 2 infrastructure is required to maintain and provide a link
state, nodes immediately know when a neighbor is no longer available.
In this case, all address pools which were assigned over the now
Schulte Expires 30 October 2021 [Page 11]
Internet-Draft AMP April 2021
unavailable link, are invalid. This is true for pools retrieved via
the ZAL/AQ algorithm at startup and redistributed pools via ZAL/DE.
POOL_REVOKED messages must be send to the affected neighbors.
2.4. Routing
AMP uses a decentralized reactive ad-hoc routing algorithm, similar
to AODV [3]. The distance vector routing algorithm uses the hop
count as metric. A route is represented by its destination, the
associated interface, the hop count and a timeout. By using a
timeout, unused routes are removed after a while. Also stale routes,
where the nodes are no longer active, are eventually removed. The
timeout counter is started along with the creation of the route and
should be reset, every time a route is used. Nodes start with zero
knowledge over the network and continuously build up a routing table
on demand. Routing tables are considered volatile and must not be
reused when a node restarts, rejoins, or moves within a network.
The routing algorithm is designed for low communication overhead,
fast convergence and passive route maintenance and optimization.
Upon boot, a node initiates the ZAL/AQ algorithm and subsequently
knows its immediate neighbors. These are added to the routing table
with a hop count of 1. Since the connectivity to the neighbours is
monitored via the layer 2 link state, there must not be a timeout for
these routes.
2.4.1. Route Detection
When a node has no route for a desired destination, it should
initiate a route discovery. A ROUTE_DISCOVERY message should be send
via all interfaces. The destination node should respond with a
ROUTE_REPLY. Route discoveries should be flooded by all nodes, but
not to the interface it was received from. A node may receive
multiple replies on different interfaces. Only the route with the
least hops should be kept. If multiple interfaces have the same hop
count to a destination, only one should be kept. If no reply to the
discovery message was received, the node should not send any data
messages to the irresponsive destination address. Optionally, the
hop limit of the discovery message can be set to a low count and
increased in subsequent runs, to limit the range of the request and
therefore the number of generated messages.
Schulte Expires 30 October 2021 [Page 12]
Internet-Draft AMP April 2021
When a forwardable message is received, the routing table should
always be validated against it. This allows for passive route
discovery and maintenance. If source address of the message is not
known yet, a route should be created. If a route is already known,
but the hop count of the received message is lower than the known
one, the route should be updated. If a route is used or updated, the
timeout should be reset.
When a ROUTE_DISCOVERY message is received, the node should add the
source address to its routing table. If the source is already
present in the routing table, the node should only reply, if the hop
count of the discovery message is equal or less than in the existing
route. This reduces communication overhead for nonoptimal routes.
2.4.2. Route Updates
A nodes routing table should be updated with every incoming message,
regardless of the type and recipient. If there is no entry for the
source-address of the message, a new route with the address,
receiving interface, hop count, and a timeout should be created. If
there is an entry in the table, the hop count should be validated.
If it is lower than the stored value, it should be updated. If the
receiving interface is different to the old route, it should also be
changed. When a route is used or updated, the timeout should be
reset.
2.4.3. Route Removal
Routes may be deleted on three different occasions: timeout, address
revocation, or a link going offline. When a route times out, it
should be removed from the table, since it is no longer in active
use. When address pools are revoked via a GOODBYE or POOL_REVOKED
message, routes to these addresses must be removed. The subsequent
assignments are no longer valid and must therefore no longer be
forwarded to. When a link goes offline, all routes associated with
that interface must be removed. Also routes to addresses which are
actively or passively revoked by the link going down must be removed.
2.4.4. Forwarding
Of the four message categories (see Section 3), only data and route-
discovery messages are forwardable. Addressing and control messages
must never be forwarded.
When a message is received which is not addressed to the receiving
node, the message should be forwarded. The messages hop count must
be incremented. If a route is found in the local routing table, the
timeout of the used route should be reset. The message is then
Schulte Expires 30 October 2021 [Page 13]
Internet-Draft AMP April 2021
transmitted via the link, associated with the route's interface. If
there is no known route for the desired destination, the message
should be flooded to all interfaces, except the one, the message was
received from. The routing table should be updated before forwarding
a message.
There are several measures in place to prevent loops, duplicates, and
redundant messages: Route discoveries with a higher hop count than
the locally stored route should be dropped. If the shortest route to
a destination is associated with the same interface a message is
received from, the message should be dropped to avoid loops. A node
must not initiate a route discovery for a destination of a
forwardable message it received. If incrementing the hop count would
exceed the hop limit, the message must be dropped.
Nodes with tight processing or memory budget may omit the routing
algorithm entirely. Instead of selecting the best interface,
messages may be flooded via all interfaces. Although this behaviour
is legal, it is not recommended, since it produces higher message
load on the network.
2.5. Datagrams
The main purpose of this protocol is the delivery of payload data
between nodes. Data is transported in connectionless DATAGRAM
messages. Datagrams are standalone messages, comparable to UDP. AMP
does not add any further context to the message, other than the
header fields needed for the network operation. A datagram can
transport up to 1003 bytes of payload.
Many applications might rely on a delivery guarantee. To eliminate
the need for every application to implement such a mechanism, AMP
offers the ACKNOWLEDGED_DATAGRAM. This message adds an
identification code to a datagram. When a node receives a
ACKNOWLEDGED_DATAGRAM, it should reply with a DATAGRAM_ACK message to
the sender. This acknowledges the successful transfer of the
datagram, by including the received identification code. The
transaction is uniquely identified by the combination of the source
address, the destination address, and the identification code.
The 16-bit identification code allows for up to 65536 in-flight
messages per node pair. The sender must keep track of the used
identification codes and ensure their uniqueness.
AMP does provide the messages for acknowledgment, but no redelivery
or timeout algorithms. The implementation of these mechanisms is
left to upper layers or the application itself.
Schulte Expires 30 October 2021 [Page 14]
Internet-Draft AMP April 2021
2.6. Gateways
Gateways are a core component of AMP, enabling inter-domain
communication. Gateways consist of two nodes in different domains,
connected by a common interface.
In the scope of addressing, a gateway link is special and needs to be
treated with care. Gateway nodes must be aware of the fact they are
a gateway. A gateway link is not part of a domain, addressing
messages must therefore not be transmitted via this link. Gateway
links must only be used after a node has acquired a valid address.
In the scope of routing and forwarding, gateway links are treated as
every other link in the network graph.
Gateway links may be formed and dropped at any time. To initiate a
gateway, a node sends a HELLO message with its source address and
unspecified destination address. If the second node replies with a
fully populated HELLO message, the neighbor discovery is complete and
the gateway is operational. A gateway is terminated, when the link
goes offline or one of the nodes sends a GOODBYE message.
Gateways may consist of two separate nodes in two domains, connected
by a common physical interface. Alternatively a single physical node
with interfaces to multiple domains may behave as soft gateway. Data
can be transferred internally, instead of a common interface. In any
other regard, soft gateways must behave as if they were physically
separate nodes.
There may be multiple gateways between two domains. This is
recommended, since gateways can be a potential bottle-neck and
single-point-of failure. More gateways between domains result in a
more robust network.
3. Message Specification
Sets of transmittes bits in the AMP Mesh Protocol are called
messages. There are four message classes for different features of
the protocol. These message classes, the message header and common
features are specified here.
The network byte ordering is big-endian. Messages must not be longer
than 1024 bytes, including the header. If necessary, zeroes should
be added as padding.
Schulte Expires 30 October 2021 [Page 15]
Internet-Draft AMP April 2021
3.1. Message Header
All messages have a common header. It contains the minimal data set
needed for the operation of the network. The three header fields
required by all messages are the message type, the source address,
and destination address. Some message types may add additional
header fields and payload.
8 Bit 64 Bit 64 Bit max. 1007 Bytes
+--------+------------+---------------+-----------------------------
| Type | Source | Destination | opt. Headers & Payload ...
+--------+------------+---------------+-----------------------------
Figure 2: Message Header
Type:
Unsigned 8-bit integer
Specifies the message type
Source:
Unsigned 64-bit integer
Source address of the message
Destination:
Unsigned 64-bit integer
Destination address of the message
Payload:
Up to 1007 bytes
Optional auxiliary headers and payload
The first 8 bit define the messages type. The notation for message
types is hexadecimal. The first nibble indicates the message class,
the second nibble defines the type. This structure allows for future
additions. The class distinction in the first nibble using
hexadecimal letters also increases readability for humans.
After the message type, source and destination address are given as
64-bit unsigned integers. If not explicitly stated otherwise in the
message specification, both header fields must always be populated
with valid addresses.
Schulte Expires 30 October 2021 [Page 16]
Internet-Draft AMP April 2021
Not all messages add a payload. Some messages, such as HELLO, do not
need more data than type and addresses. Detailed specifications for
all messages are given below.
A distinction is to be made between forwardable and non-forwardable
messages. Addressing and control messages must never be forwarded.
They are only ever exchanged between neighbors. Address and control
messages with other addresses than the two peer's or the unspecified
(::) address must be dropped immediately. Data and routing messages
may be forwarded. The header must always be fully populated. If it
contains an invalid or unspecified address, the message must be
dropped immediately.
Forwardable messages add hop counter and hop limit fields. The hop
counter must start with zero and must be incremented on every hop.
If incrementing the hop count would exceed the hop limit, the message
must be dropped.
3.2. Addressing Messages
Addressing messages must only be exchanged between neighboring nodes.
Addressing messages must not be forwarded. Source and destination
address must only contain the unspecified or the peers' addresses.
Addressing messages must never be exchanged over a gateway link.
Addressing messages are only valid within the same domain.
Addressing messages are identified by a hexadecimal "A" in the high
nibble of the message type.
3.2.1. POOL_ADVERTISEMENT
This message is used in ZAL/AQ and ZAL/DE algorithms. It advertises
assignable address pools to a neighboring node.
The advertisement adds a list of assignable address pools to the
payload of the message. First, the count of message pools is given,
then the pools are listed. Each pool is defined by the starting
address and the size of the pool. Restricted by the message size, up
to 62 address pools can be added. If there are no assignable pools
available, the message should be send with an empty payload.
If used during the ZAL/AQ algorithm, the destination address must be
unspecified. In all other cases, address fields must be populated.
The POOL_ADVERTISEMENT adds the following fields to the message:
Message type 0xA1
Schulte Expires 30 October 2021 [Page 17]
Internet-Draft AMP April 2021
Count:
Unsigned 8-bit integer
Gives the number of message pools
1 to 62 message pools, each consisting of:
Address pool start address:
Unsigned 64-bit integer
Address pool size:
Unsigned 64-bit integer
3.2.2. POOL_ACCEPTED
This message is used in ZAL/AQ and ZAL/DE algorithms. It indicates
that a node accepted the address pool advertisement of a parent. No
additional header fields or payload are added to the message.
If used during the ZAL/AQ algorithm, the source address must be
unspecified. In all other cases, address fields must be populated.
Message type 0xA2
3.2.3. POOL_ASSIGNED
This message is used in ZAL/AQ and ZAL/DE algorithms. It indicates
that address pools are assigned to a child node.
Adds a list of the assigned address pools to the payload of the
message. This must be the same set of pools as in the original
advertisement. First, the count of message pools is given, then the
pools are listed. Each pool is defined by the starting address and
the size of the pool. Restricted by the message size, up to 62
address pools can be added.
If used during the ZAL/AQ algorithm, the destination address must be
unspecified. In all other cases, address fields must be populated.
Message type 0xA3
Count:
Unsigned 8-bit integer
Gives the number of message pools
1 to 62 message pools, each consisting of:
Schulte Expires 30 October 2021 [Page 18]
Internet-Draft AMP April 2021
Address pool start address:
Unsigned 64-bit integer
Address pool size:
Unsigned 64-bit integer
3.2.4. POOL_REVOKED
Indicates that a set of address pools is no longer valid and
routable. Their usage for routing and communication must immediately
be stopped.
Adds a list of the revoked address pools to the payload of the
message. First, the count of message pools is given, then the pools
are listed. Each pool is defined by the starting address and the
size of the pool. Restricted by the message size, up to 62 address
pools can be added.
Message type 0xA5
Count:
Unsigned 8-bit integer
Gives the number of message pools
1 to 62 message pools, each consisting of:
Address pool start address:
Unsigned 64-bit integer
Address pool size:
Unsigned 64-bit integer
3.2.5. BIN_CAPACITY_REQUEST
This message is used in the ZAL/DE algorithm. It is used to
determine the available address space in the local bin.
This message type does not add any payload.
Message type 0xA5
3.2.6. BIN_CAPACITY_REPLY
This message is used in the ZAL/DE algorithm. It is a reply to the
BIN_CAPACITY_REQUEST. The message adds the amount of available
address space as payload.
Schulte Expires 30 October 2021 [Page 19]
Internet-Draft AMP April 2021
Message type 0xA6
Bin capacity:
Unsigned 64-bit integer
3.3. Control Messages
Control messages must not be forwarded. There is no payload in
control messages.
Control messages are identified by a hexadecimal "C" in the high
nibble of the message type.
3.3.1. HELLO
This message is used by to announce the existence and address of a
node to its neighbors. If the source address is empty, the ZAL/AQ
algorithm is initiated.
This message type does not add any payload.
Message type 0xC1
3.3.2. GOODBYE
This message is used to indicate the graceful shutdown of a node or
the termination of a link.
This message type does not add any payload.
Message type 0xC2
3.3.3. GOODBYE_ACK
This message is used as acknowledgement for a GOODBYE message, so the
retiring node knows that its GOODBYE message was received and
processed.
This message type does not add any payload.
Message type 0xC3
3.4. Data Messages
Data is transported through the network as datagrams. Data messages
are forwardable. They add hop counter and hop limit header fields.
Schulte Expires 30 October 2021 [Page 20]
Internet-Draft AMP April 2021
Data messages are identified by a hexadecimal "D" in the high nibble
of the message type.
3.4.1. DATAGRAM
This message is used to transport data through the network.
Message type 0xD1
Hop count:
Unsigned 8-bit integer
Hop limit:
Unsigned 8-bit integer
Payload length:
Unsigned 16-bit integer
Gives the length of the payload in bytes
Payload:
Up to 1003 bytes of payload
3.4.2. ACKNOWLEDGED_DATAGRAM
This message adds an identification code to a datagram. This enables
the receiver of the message to acknowledge the successful transfer of
the message to the sender. The message can be uniquely identified by
the combination of source address, destination address, and
identification code.
Message type 0xD2
Hop count:
Unsigned 8-bit integer
Hop limit:
Unsigned 8-bit integer
Identification Code:
Unsigned 16-bit integer
Used to uniquely identify the message
Payload length:
Unsigned 16-bit integer
Gives the length of the payload in bytes
Schulte Expires 30 October 2021 [Page 21]
Internet-Draft AMP April 2021
Payload:
Up to 1001 bytes of payload
3.4.3. DATAGRAM_ACK
This message is used to acknowledge, that a ACKNOWLEDGED_DATAGRAM was
successfully received. Although this message is in the class of data
messages, it does not add any payload other than the header fields
listed below.
Message type 0xD3
Hop count:
Unsigned 8-bit integer
Hop limit:
Unsigned 8-bit integer
Identification Code:
Unsigned 16-bit integer
Used to uniquely identify the message
3.5. Routing Messages
Routing messages are used to discover routes between two nodes in the
network. Routing messages are forwardable, but do not transport any
payload other than hop counter and hop limit header fields.
Routing messages are identified by a hexadecimal "F" (for "find") in
the high nibble of the message type.
3.5.1. ROUTE_DISCOVERY
This message is used to initiate a route discovery.
Message type 0xF1
Hop count:
Unsigned 8-bit integer
Hop limit:
Unsigned 8-bit integer
3.5.2. ROUTE_REPLY
This message is the reply to a ROUTE_DISCOVERY. The hop limit must
be set equal the hop counter of the received ROUTE_DISCOVERY message.
Schulte Expires 30 October 2021 [Page 22]
Internet-Draft AMP April 2021
Message type 0xF2
Hop count:
Unsigned 8-bit integer
Hop limit:
Unsigned 8-bit integer
4. IANA Considerations
This memo includes no request to IANA.
5. Security Considerations
To keep wide compatibility with low power devices, the protocol does
not have any built-in security features. The protocol is therefore
vulnerable to malicious nodes. Both the addressing and the routing
algorithm can be interfered with by modified or malicious messages.
AMP is to be considered inherently insecure.
5.1. Out-of-Scope Attacks
Data integrity is left to the underlying layers. There are no
encryption or authentication features. If needed, they must be added
by higher layers. Without added security by other layers in the
communication stack, AMP is susceptible for eavesdropping, replay,
message insertion, deletion, modification, and man-in-the-middle
attacks.
5.2. Denial of Service Attacks
Both direct and distributed denial of service attacks are possible.
A node can force its direct neighbours to invest memory and
processing resources by sending large datagrams with malicious header
fields. This can be invalid addresses or a hop count/hop limit which
require the message to be dropped. To prevent this attack, the
attacked node can simply drop the connection to the malicious
neighbor. This is fully compliant with the best-effort principle.
The routing algorithm will adapt to the change in topology.
A distributed denial of service attack can be executed by forging the
source address of a ROUTE_REQUEST. When a malicious node sends route
requests to multiple nodes in the network, they all send responses to
the node with the forged source address. This attack is somewhat
dampened by the routing algorithm. ROUTE_REQUEST messages with a
non-ideal route are dropped. A successful DDoS attack therefore
requires inferred knowledge about the networks topology.
Schulte Expires 30 October 2021 [Page 23]
Internet-Draft AMP April 2021
The hop limit field can be forged by malicious nodes. If it is set
to a higher value than intended by the sender, this can result in
network congestion. This is especially true for ROUTE_DISCOVERY
messages, which are selectively flooded. This attack is confined to
the boundaries of a domain.
5.3. Attacks on the Addressing Algorithm
The addressing algorithms can be interfered with, by provoking
duplicate addresses. A malicious node can advertise address pools,
which it was not officially assigned. Alternatively, the same pool
can be assigned to multiple nodes.
Address revocations can also be malicious. Therefore messages must
only be processed, if they are received over the link the addresses
were originally assigned over. This contains the impact of a
misbehaving node to a single branch of the addressing tree.
5.4. Attacks on the Routing Algorithm
Manipulated hop count header fields can interfere with the routing
algorithm. Off-path attackers can direct selected message flow
towards them by decrementing the hop count, which enables MITM
attacks.
Maliciously incremented hop counts can lead to route diversions.
Traffic can be diverted to other parts of the network, which can
result in higher overall network load and lead to congestion. This
attack requires at least some knowledge over the networks topology.
6. References
6.1. Normative References
[1] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[2] Hinden, R. and S. Deering, "IP Version 6 Addressing
Architecture", RFC 4291, DOI 10.17487/RFC4291, February
2006, <https://www.rfc-editor.org/info/rfc4291>.
[3] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
Demand Distance Vector (AODV) Routing", RFC 3561,
DOI 10.17487/RFC3561, July 2003,
<https://www.rfc-editor.org/info/rfc3561>.
Schulte Expires 30 October 2021 [Page 24]
Internet-Draft AMP April 2021
6.2. Informative References
[4] Hu, Z. H. and B. L. Li, "ZAL: Zero-Maintenance Address
Allocation in Mobile Wireless Ad Hoc Networks", March
2005, <https://doi.org/10.1109/ICDCS.2005.87>.
Author's Address
Aljoscha Schulte
Technische Universitaet Berlin
Email: a.schulte@tu-berlin.de
Schulte Expires 30 October 2021 [Page 25]
