Node to Node Protocol
Louis "Ne02ptzero" Solofrizzo
0x5c
MeshNet Project
ABSTRACT
The Node to Node protocol (N2NP) is intended for use as a
reliable host‐to‐host protocol between node devices (hosts) in
packet‐switched embedded computer communication networks over
radio waves.
This document describes the function to be performed by the Node
to Node Protocol, the programs that implement it, and its inter‐
face through a kernel device driver.
MeshNet [Page 1]
December 2017 ‐2‐ Node to Node Protocol
Table of Contents
1. INTRODUCTION ............................................................. 3
1.1 Scope of this document ................................................. 3
1.2 Abbreviations .......................................................... 3
2. GENERAL DESCRIPTION ...................................................... 4
2.1 Protocol Description ................................................... 4
2.2 Frame .................................................................. 5
2.3 Device Identification ................................................. 5
2.4 Packet Type ............................................................ 5
2.5 Payload ................................................................ 5
2.6 Version & Length ....................................................... 5
3. PACKET TYPES ............................................................. 6
3.1 PING ................................................................... 6
3.2 PONG ................................................................... 6
3.3 SERVICE ................................................................ 6
3.4 PEERS .................................................................. 7
4. SERVICES ................................................................. 10
4.1 CHAT .................................................................. 10
4.1.1 Sequence Number ................................................... 10
4.1.2 Flags ............................................................. 11
4.1.3 Message ........................................................... 13
4.2 BROADCAST ............................................................. 14
4.2.1 Issued Timestamp & Expires ........................................ 15
4.2.2 Message ........................................................... 15
5. ROUTING ................................................................. 16
5.1. PEER INFORMATION ..................................................... 16
5.1.1. Score calculation ................................................ 16
5.1.2. Update Broadcast ................................................. 16
5.1.3. Update Broadcast data optimization ............................... 17
5.2. ROUTING ALGORITHM .................................................... 17
5.2.1. General Description .............................................. 17
5.2.2. Dijkstra’s algorithm ............................................. 18
5.2.3. Broadcast routing ................................................ 18
5.2.4. Protocol routing ................................................. 19
MeshNet [Page 2]
December 2017 ‐3‐ Node to Node Protocol
1. INTRODUCTION
1.1. Scope of this document
N2NP is a transport and applicative layer for the MeshNet project. It provides
communication between two nodes through radio signals. The physical layer
(radio) is not yet defined as of this day, and it’s not in the scope of this
document. This document shall describe the internal mechanisms of the proto‐
col, and its integration within the MeshNet project.
1.2. Abbreviations
┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Abbreviation ┃ Meaning ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┩
│ N2NP │ Node‐to‐Node protocol │
├──────────────┼──────────────────────────────────────────────────────────────┤
│ HW │ Hardware │
└──────────────┴──────────────────────────────────────────────────────────────┘
MeshNet [Page 3]
December 2017 ‐4‐ Node to Node Protocol
2. GENERAL DESCRIPTION
2.1. Protocol Description
Protocol Layering
+‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐+
| |
| Physical Layer |
| |
+‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐+
| |
| N2NP |
| |
+‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐+
Figure 1
The N2NP is over the physical layer [Figure 1] The physical layer is charged
with transportation of the packet, and will be likely over radio waves with
low frequencies. That implies very low bandwidth, and the protocol must be
designed with this requirement in mind. Since it does not handle transporta‐
tion, the N2NP can focus on the Routing and the data side of a communication.
It is assumed that if a packet is not compliant with this specification, a
client should drop it.
2.2. Frame
┏━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Octet ┃ 0 ┃ 1 ┃
┃ ┣━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━╋━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┫
┃ ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃ 7 ┃ 8 ┃ 9 ┃ 10 ┃ 11 ┃ 12 ┃ 13 ┃ 14 ┃ 15 ┃
┡━━━━━━━╇━━━┻━━━┻━━━┻━━━╇━━━┻━━━┻━━━┻━━━╇━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┩
│ 0 │ Major Version │ Minor Version │ Packet Length │
├───────┼───────────────┴───────────────┼─────────────────────────────────────┤
│ 2 │ Packet Length │ Packet Type │
├───────┼───────────────────────────────┴─────────────────────────────────────┤
│ 4 │ │
├───────┤ Source Device Identifier │
│ 6 │ │
├───────┼─────────────────────────────────────────────────────────────────────┤
│ 8 │ │
├───────┤ Destination Device Identifier │
│ 10 │ │
├───────┼─────────────────────────────────────────────────────────────────────┤
MeshNet [Page 4]
December 2017 ‐5‐ Node to Node Protocol
│ 12 │ │
├───────┤ Next Physical Device Identifier │
│ 14 │ │
├───────┼─────────────────────────────────────────────────────────────────────┤
│ 16 │ Data ... │
└───────┴─────────────────────────────────────────────────────────────────────┘
2.3. Device Identification
In order to identify a device uniquely, the N2NP uses a hashed identifier with
a length of 4 bytes. The original hashed content and the size of those fields
are not finally decided yet, so those are subject to change. In a packet, the
protocol shall define a source identifier (FROM) and a destination identifier
(TO). These fields are to be used by the neighboring nodes in order to relay
the packet to its final destination. Since a node can have multiple neighbors,
and assuming the physical layer of the protocol (radio) can’t handle a non‐
broadcast emission, a third ID is used; It describes the physical neighbor
that will relay this packet. If the final destination node is within physical
reach, this field is useless, and its value should be set to ’0’ (zero).
2.4. Packet Type
In order to perform multiple actions, a packet type, 1 byte in length, is set
in the packet. This field contains a common integer that describes the type of
action to be performed. Read the Type * sections for more information about
them.
2.5. Payload
The payload of a packet (Data, in the Frame in 2.2) is filled with data. This
field does not have a fixed size, and its content depends on the packet type.
For example, a PING will not have any data.
2.6. Version & Length
The first byte of the packet is used to describe the protocol version. The
first 4 bits are used for the major version, the last 4 bits for the minor
version.
Example version byte
0100 .... = Major Version 4
.... 0101 = Minor Version 5
MeshNet [Page 5]
December 2017 ‐6‐ Node to Node Protocol
The length field describes the total length of the packet, starting from byte
0 of the N2NP header and ending at the last byte of the data field.
MeshNet [Page 6]
December 2017 ‐7‐ Node to Node Protocol
3. PACKET TYPES
3.1. PING
The PING packet type describes an action to test the reachability and the
availability of a device. This type does not have any data associeated with
it. On a PING a device shall respond with a PONG in order to assure the orig‐
inal sender of its reachability. It is described with the value 0x1 (1) in
the packet type field.
Typical ping‐pong exchange
CLIENT_1 ‐> PING ‐> CLIENT_2
CLIENT_1 <‐ PONG <‐ CLIENT_2
3.2. PONG
The PONG packet type describes a response to a previous PING packet. It is
used to assure the availability of the receiver to the original sender. PONG
is an obligatory response to a PING packet. If a client does not respond to a
PING with a PONG, the original sender will assume that the receiver is not
reachable. This type does not have any data paired with. It is described with
the value 0x2 (2) in the packet type field.
3.3. SERVICE
The SERVICE packet is used to describe a payload type, in order for the
receiver to know what type of data will follow the header. If a SERVICE type
is specified, a data payload MUST follow the header. A data payload shall
always be in the following frame:
Example Service Payload
┏━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Octet ┃ 0 ┃ 1 ┃
┃ ┣━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━╋━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┫
┃ ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃ 7 ┃ 8 ┃ 9 ┃ 10 ┃ 11 ┃ 12 ┃ 13 ┃ 14 ┃ 15 ┃
┡━━━━━━━╇━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━╇━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┩
│ 0 │ Service Type │ Data Length │
├───────┼───────────────────────────────┴─────────────────────────────────────┤
│ 2 │ Data ... │
└───────┴─────────────────────────────────────────────────────────────────────┘
The Service Type field describes a 1 byte code used to define the service that
this payload is processed with. Data Length describes the size of the follow‐
ing data field. One can chain multiple SERVICE payloads:
MeshNet [Page 7]
December 2017 ‐8‐ Node to Node Protocol
Two services payloads
┏━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Octet ┃ 0 ┃ 1 ┃
┃ ┣━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━╋━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┫
┃ ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃ 7 ┃ 8 ┃ 9 ┃ 10 ┃ 11 ┃ 12 ┃ 13 ┃ 14 ┃ 15 ┃
┡━━━━━━━╇━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━╇━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┩
│ 0 │ First Service Type │ First Data Length │
├───────┼───────────────────────────────┴─────────────────────────────────────┤
│ 2 │ │
├───────┤ First Data │
│ X │ │
├───────┼───────────────────────────────┬─────────────────────────────────────┤
│ X │ Second Service Type │ Second Data Length │
├───────┼───────────────────────────────┴─────────────────────────────────────┤
│ X │ │
├───────┤ Second Data │
│ X │ │
└───────┴─────────────────────────────────────────────────────────────────────┘
See the SERVICES general section for more information about the content of
data. The SERVICE packet type is described with 0x3 (3) in the packet type
field.
3.4. PEERS
The PEERS packet type describes the state of a node with its neighbors. It can
be used for different purposes, when a client is joining the network, to
update the score of a peer or when a node looses a peer. It is described with
the value 0x4 (4) in the packet type field.
PEERS packet header
┏━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Octet ┃ 0 ┃ 1 ┃
┃ ┣━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━╋━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┫
┃ ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃ 7 ┃ 8 ┃ 9 ┃ 10 ┃ 11 ┃ 12 ┃ 13 ┃ 14 ┃ 15 ┃
┡━━━━━━━╇━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━╇━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┩
│ 0 │ Peer size │ Data │
├───────┼───────────────────────────────┘ │
│ 2 │ Data ... │
└───────┴─────────────────────────────────────────────────────────────────────┘
The Peer size field describes the number of score‐ID couples present in the
packet. A score ‐ device ID pair is a simple data structure:
MeshNet [Page 8]
December 2017 ‐9‐ Node to Node Protocol
┏━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Octet ┃ 0 ┃ 1 ┃
┃ ┣━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━╋━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┫
┃ ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃ 7 ┃ 8 ┃ 9 ┃ 10 ┃ 11 ┃ 12 ┃ 13 ┃ 14 ┃ 15 ┃
┡━━━━━━━╇━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━╇━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┩
│ 0 │ Score │ Device ID │
├───────┼───────────────────────────────┘ │
│ 2 │ Device ID │
├───────┤ ┌─────────────────────────────────────┘
│ 4 │ Device ID │
└───────┴───────────────────────────────┘
The Score field describes the current score of the Device ID node perceived by
the source node; It is used to choose a best path when routing is needed. The
Device ID describes the peer device ID on 4 bytes.
Those packets are broadcast by nature; if a client happens to receive a PEERS
packet, the Destination Device Identifier in the N2NP header shall be set to
0. Upon joining, a new node wanting to announce itself on the network must use
a PEER packet: it announces the current peers of the node, and their score.
For peer list and score calculation, see the relevant section. It is also used
when a node want to announce an update on his peers: a peer has been lost, a
peer score has changed, or a new peer has arrived.
Upon reception of a PEER packet, a client must update his internal routing ta‐
ble with the information in the PEER packet. A routing table entry consists of
two things: the mother device ID, and a list of paired score‐IDS of the peers
linked with the mother device. It could be represented like this:
struct {
uint32_t node_id;
struct {
uint8_t score;
uint32_t id;
struct list_head next;
} neighbors;
};
The PEER packet is join‐agnostic: a client receiving a packet must not care if
the sender just joined the network or is just updating information about his
peers. The client must update his internal routing table either way, and cre‐
ate a new entry when it is required. A C representation of the routing table
could be:
typedef struct {
struct node_entry_s {
uint32_t node_id;
MeshNet [Page 9]
December 2017 ‐10‐ Node to Node Protocol
struct {
uint8_t score;
struct node_entry_s *id;
struct list_head next;
};
struct list_head next;
};
} routing_table_t;
It is worth noting that a pointer or a 32 bits unsigned int for the ID field
will be the same thing, as both types takes 4 bytes in ARMv5l. Theoretically,
an entry will size 25 bytes in memory; In practice, GCC will align the struct
on an 8 byte word, therefore padding the structure up to 32 bytes.
4. SERVICES
4.1. CHAT
The CHAT service is used to describe a chat message between two or more users.
It is described by the value 0x1 (1) in the service type field.
┏━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Octet ┃ 0 ┃ 1 ┃
┃ ┣━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━╋━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┫
┃ ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃ 7 ┃ 8 ┃ 9 ┃ 10 ┃ 11 ┃ 12 ┃ 13 ┃ 14 ┃ 15 ┃
┡━━━━━━━╇━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┩
│ 0 │ │
├───────┤ Sequence Number │
│ 2 │ │
├───────┼──────────────────────────────┬──────────────────────────────────────┤
│ 4 │ Flags │ Message Length │
├───────┼──────────────────────────────┴──────────────────────────────────────┤
│ 6 │ Data │
└───────┴─────────────────────────────────────────────────────────────────────┘
4.1.1. Sequence Number
The Sequence Number field is used to describe a sequence in the communication.
This information is useful to the devices in order to track a progression in a
communication. On the beginning of a session, the first packet sender shall
set this field to 0. The mechanic behind it is the same as TCP [1] , the
───────────
1 Information Sciences Institute, “TCP RFC793” in INTERNET STAN‐
DARD (September 1981).
MeshNet [Page 10]
December 2017 ‐11‐ Node to Node Protocol
receiver shall increment this field with the length of the data it received.
Example of a communication
CLIENT_1 ‐> CHAT "Hello", MSG, sequence_number = 0 ‐> CLIENT_2
CLIENT_1 <‐ CHAT "Hey there !", MSG & ACK, sequence_number = 5 <‐ CLIENT_2
CLIENT_1 ‐> CHAT, ACK, sequence_number = 17 ‐> CLIENT_2
The ACK flag is described in the 4.1.3 section. If a sequence number exceeds
the maximum value of a 2 byte integer the client that will overflow the
sequence number shall start over at 1.
4.1.2. Flags
The Flags field is used to describe multiple boolean informations
1... .... = ACK
.1.. .... = CHA
..1. .... = FRG
...1 .... = MSG
.... 1... = CRT
.... .1.. = UPD
.... ..1. = Reserved
.... ...1 = Reserved
The ACK flag describes an acknowledgment of data. If the ACK flag is set, the
sequence number field shall contain the sequence of the data acknowledged.
The CHA flag describes a message that is to be sent to multiple people (a
Channel). If this flag is set, the payload will not be a simple UTF‐8 message,
but rather this payload:
┏━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Octet ┃ 0 ┃ 1 ┃
┃ ┣━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━╋━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┫
┃ ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃ 7 ┃ 8 ┃ 9 ┃ 10 ┃ 11 ┃ 12 ┃ 13 ┃ 14 ┃ 15 ┃
┡━━━━━━━╇━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┩
│ 0 │ Channel ID │
├───────┼─────────────────────────────────────────────────────────────────────┤
│ 2 │ Data │
└───────┴─────────────────────────────────────────────────────────────────────┘
The Channel ID, 2 bytes in legth, describes the ID of a channel that a client
wants to pass his message to. This ID is handled with the CRT message
mechanic, see the appropriate section for more information. This packet is, in
essence, a broadcast; The destination device ID should be set to 0. Every
client must relay this message to their neighbors, and log it internally. This
way, when a client joins a channel, it will have a history (at least from the
MeshNet [Page 11]
December 2017 ‐12‐ Node to Node Protocol
moment he joined the network). When a client wants to join / leave a channel,
he will be doing this internally, without announcing it to the network.
A client must deduce the data length from the following math:
chat‐>message_length ‐ sizeof(CHA‐>channel_id)
The FRG flag describes a fragmentation of data. If this flag is set, the
receiver shall expect one or more further packets in order to complete the
data.
Incorrect fragmented exchange:
CLIENT_1 ‐> CHAT "Hello", FRG & MSG, seq = 0 ‐> CLIENT_2
CLIENT_1 <‐ CHAT, ACK, seq = 5 <‐ CLIENT_2
CLIENT_1 ‐> CHAT "World !", MSG, seq = 0 ‐> CLIENT_2
CLIENT_1 <‐ CHAT, ACK, seq = 12 <‐ CLIENT_2
In the example above, one can see that CLIENT_2 ACKed the data before
the reception of the second and final packet: this is not standard;
CLIENT_1 shall not wait for an acknowledgment of data before sending more
fragmented packets. The exchange above should have happened like this:
Correct fragmented exchange:
CLIENT_1 ‐> CHAT "Hello", FRG & MSG, seq = 0 ‐> CLIENT_2
CLIENT_1 ‐> CHAT "World !", MSG, seq = 0 ‐> CLIENT_2
CLIENT_1 <‐ CHAT, ACK, seq = 12 <‐ CLIENT_2
A client must unset the FRG flag when sending the final packet of fragmented
data; otherwise the other client will wait indefinitely for another packet.
The MSG flag describes a standard chat exchange: the payload will be nothing
more than a normal UTF‐8 message. This flag cannot be set with the CHA flag.
The CRT flag describes the creation of a channel to the entire network, and
announce a channel ID with a human‐readable name. If this flag is set, the
payload will not be a simple UTF‐8 message, but rather this payload:
┏━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Octet ┃ 0 ┃ 1 ┃
┃ ┣━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━╋━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┫
┃ ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃ 7 ┃ 8 ┃ 9 ┃ 10 ┃ 11 ┃ 12 ┃ 13 ┃ 14 ┃ 15 ┃
┡━━━━━━━╇━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┩
│ 0 │ Channel ID │
├───────┼─────────────────────────────────────────────────────────────────────┤
│ 2 │ Channel Name │
└───────┴─────────────────────────────────────────────────────────────────────┘
MeshNet [Page 12]
December 2017 ‐13‐ Node to Node Protocol
The channel ID will be used for all the exchanges to come on this particular
channel: A client must save it internally. If a CHA message would arrive, and
a client did not know the concerned ID, this packet must be queued waiting for
a CRT packet to come.
In case of a join / re‐join, when a client was not connected during the time
of the creation of a channel, this client, upon reception of a CHA packet,
must ask his direct neighbors an update of his internal channel ID table. He
will be doing so using the UPD flag.
The UPD flag describes a request from a client whose internal channel ID table
is outdated, whether he was disonnected at the time of the creation, or simply
miss it, to his direct neighbors. The payload shall be simply:
┏━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Octet ┃ 0 ┃ 1 ┃
┃ ┣━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━╋━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┫
┃ ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃ 7 ┃ 8 ┃ 9 ┃ 10 ┃ 11 ┃ 12 ┃ 13 ┃ 14 ┃ 15 ┃
┡━━━━━━━╇━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┩
│ 0 │ Channel ID │
└───────┴─────────────────────────────────────────────────────────────────────┘
And the neighbors, upon reception must look in their internal channel ID ta‐
ble, and respond with a simple payload too:
┏━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Octet ┃ 0 ┃ 1 ┃
┃ ┣━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━╋━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┫
┃ ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃ 7 ┃ 8 ┃ 9 ┃ 10 ┃ 11 ┃ 12 ┃ 13 ┃ 14 ┃ 15 ┃
┡━━━━━━━╇━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┩
│ 0 │ Channel Name │
└───────┴─────────────────────────────────────────────────────────────────────┘
The ACK and UPD flag must be set for this response. In the case where the
neighbor does not know the channel ID either, it must ask his neighbors (minus
the original sender) for this information, following the same process. Upon
reception of the response, it must update his table, and pass the information
to the original sender.
4.1.3. Message
The Message field contains the payload message sent by the user to another
one. It is assumed that this field is encoded with UTF‐8. The size of this
field is described in the Message Length field. If this field is set to 0, it
is assumed that the Message field will be empty.
MeshNet [Page 13]
December 2017 ‐14‐ Node to Node Protocol
4.2. BROADCAST
The BROADCAST packet is used to describe a global message that needs to be
sent to all the members of the network. It is described by the value 0x2 (2)
in the service type field. It is worth noting that with this packet, the con‐
cept of destination is voided, since everyone on the network shall receive
this packet. In this case, the Destination Device ID field in the N2NP header
frame shall be set to 0 (zero).
MeshNet [Page 14]
December 2017 ‐15‐ Node to Node Protocol
┏━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Octet ┃ 0 ┃ 1 ┃
┃ ┣━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━╋━━━┳━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┳━━━━┫
┃ ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃ 7 ┃ 8 ┃ 9 ┃ 10 ┃ 11 ┃ 12 ┃ 13 ┃ 14 ┃ 15 ┃
┡━━━━━━━╇━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┻━━━━┩
│ 0 │ │
├───────┤ │
│ 2 │ │
├───────┤ Issued Timestamp │
│ 4 │ │
├───────┤ │
│ 6 │ │
├───────┼──────────────────────────────┬──────────────────────────────────────┤
│ 8 │ Expires │ Message Length │
├───────┼──────────────────────────────┴──────────────────────────────────────┤
│ 10 │ Message │
└───────┴─────────────────────────────────────────────────────────────────────┘
4.2.1. Issued Timestamp & Expires
The first eight bytes describes a Unix EPOCH timestamp. This timestamp is the
time at which the original author sent the broadcast. It can’t be in the
future, if such a thing would happen, a client must drop the broadcast, and
not relay it. The Expires field describes the number of hours that the broad‐
cast is valid starting from the Issued timestamp. Clients should be doing the
following addition in order to check the validity of a broadcast
Condition to check the validity of broadcast
time(NULL) < issued_timestamp + (expires * 3600)
4.2.2. Message
The Message field contains the data to be delivered; It is not formatted in
any fashion. In order to get the size of this data, one must use the Message
Length field.
MeshNet [Page 15]
December 2017 ‐16‐ Node to Node Protocol
5. ROUTING
Within the N2NP protocol, routing is done in a special way. Since the network
mesh is router‐less, the routing protocol needs to be gateway agnostic. We also
have low‐data requirements due to the physical transportation limitation. Also,
as a node on the network may be moving, high reliability is a must.
The entire routing is based on the principle that all nodes on the network know
every node’s neighbors; therefore, every node can determine a path for every
packet.
5.1. Peer Information
Peer’s neighbors are not the only information provided by every host on the
network; every host assigns a score to their neighbors, based on signal
strength and distance. This value is to be used in the heuristic algorithm in
order to evaluate the weight of a path.
5.1.1. Score calculation
A score describes the state of a node from the point of view of another node.
Those two nodes must be within physical reach of each other for a score to be
determined: it is used as weight value for the path‐finding heuristic. A
score is determined through the following equation / heuristic:
/!\ To be determined, needs to be on one byte maximum /!\
5.1.2. Update Broadcast
This broadcast is launched when one of the following conditions are met: ‐ A
new node is joining the network ‐ An existing node got a new neighbor (New
client or a moving node) ‐ A node has timed out ‐ A peer score has changed
In all of these cases, the main node needs to update the whole network with
this new information; In order to calculate a path reliably, every node on the
network must know the neighbors of everyone: it is not intended to be a real‐
time information, but rather an indicative information. In order to do that,
the node must send a PEERS packet with all the neighbors information. If a
peer did timeout, the main node must sent a PEER entry with a score of 0
(zero). If a peer did not change score, the main node must not add it in its
PEERS packet.
MeshNet [Page 16]
December 2017 ‐17‐ Node to Node Protocol
5.1.3. Update broadcast data optimization
In order to optimize usage of data bandwidth, broadcast peer update data must
be packed whenever possible.
If a node B is to retransmit the update data of the node A, and the node B
itself has broadcast data in the output pipe, the B node must pack the node A
information with it’s information, and send only one packet to be relayed by
its peers.
Of course, this packed data length should not exceed the packet maximum size,
otherwise the first packet must be relayed without re‐writing, and the second
one sent as well. A client, receiving broadcast update data from multiple
clients in one packet must deduce the number of nodes implicated by looking at
the total length in the N2NP header.
5.2. ROUTING ALGORITHM
When a packet is sent from one device with the intent of speaking to a another
device directly, routing must be involved. In order to assure delivering reli‐
ably, the N2NP uses a mix between the HEAT algorithm, with node score attribu‐
tion, and a static route routing algorithm. You can find the details about score
attribution in the relevant section, along with the routing table information.
5.2.1. General Description
The concept of this routing algorithm is quite simple: every node bound to
route a packet from node A to node B must determine which route is the best,
on every hop.
Let’s say we have node A wanting to send a packet to node Z; the simple sce‐
nario is that those two nodes are physically next to each other: therefore, no
routing is needed.
But, if those two nodes are not directly connected to each other, node A must
determine the best route to reach node Z. In order to do that, and with all
the information about all the nodes on the network (See PEERS), node A must
run a heuristic algorithm on all his peer nodes (physically connected) with
the score of each node as weight.
In order not to loose time in the process, the depth used for the algorithm
should be minimal: node A does not need to determine an exact perfect path all
the way to node Z, but rather choose the direct peer that will be most suited
to route this packet.
MeshNet [Page 17]
December 2017 ‐18‐ Node to Node Protocol
Example mesh network
/ ‐ Node C ‐ \ /‐‐‐ Node E ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ \
/ Node B Node D ‐‐‐> Node F \
Node A \ Node G ‐‐‐‐‐ / | \‐‐ Node H Node Z
\ Node I \ ‐‐‐ Node J ‐‐‐ /
Let’s take the above schema: node A still wants to reach node Z. In order to
do that, node A must determine the best path through one of his direct peers;
in this case it’s quite simple; node A only has one peer.
Node A sends the packet to node B, and it’s now the turn of node B to deter‐
mine the best path through one of his direct peers. Here, we got two peer
nodes: C and G. With the score of both it’s direct peers, and all the ones
beyond these, node B must now determine the best path to route this packet.
It is important to note that node B’s internal routing table, that describes
all the scores of everyone on the network, does not need to be updated in real
time: the node can determine a good‐enough path to the next hop with its data.
Let’s say, for the sake of the example, that node C has a score of 40, and G a
score of 55. Since both C and G share the same output node, D, their exit
score will be the same. So the node B must compare the score of C and G in
order to route the packet properly.
In this example, G got a bigger score than C, so node B will route the packet
to G. Node G, upon reception, will do the same algorithm in order to route the
packet to the next node, and the next node will do the same, and so on until
the destination node is reached.
5.2.2. Dijkstra’s algorithm
In order to compute the best path for a packet, a node must use Dijkstra’s
algorithm [2]. Instead of using distance as a sole weight parameter, the score
of the nodes is to be used. See the relevant sections for score calculations.
5.2.3. Broadcast routing
By nature, broadcast packets do not have a destination: All the members of the
networks shall receive the packet. Therefore, the routing algorithm cannot be
used in this case. A flood routing algorithm shall be used.
───────────
2 Melissa Yan, “Dijkstra’s Algorithm” in MIT (2007).
MeshNet [Page 18]
December 2017 ‐19‐ Node to Node Protocol
Simple 4 nodes network
Node A
/ \
Node B Node D
\ /
Node C
Lets take the above schema: in this example, node A wants to broadcast a
packet to the network: first, it will send it to his direct neighbors: B and
D. Before sending, the node must compute a checksum of the full packet, start‐
ing at the N2NP header, and store it.
The node D, upon reception of the packet, and before treatment in userland,
must do the same: compute a checksum, and send the packet to his direct neigh‐
bors, A and C. C has never seen the packet before: therefore it will compute
and relay it.
But the node A has already seen the packet (Since he’s the one who sent it).
So, upon reception, A will compute the checksum, check with his internal stor‐
age, see that this packet has already been relayed, and simply drop it.
With this method, we keep simplicity through routing, without much data over‐
head and broadcast replay problems.
5.2.4. Protocol routing
When the next peer ID has been determined, the node must physically route and
send the packet to the said node. In order to do that, the field ’Next Physi‐
cal Device Identifier’ in the header (Section 2.2 Frame) must be set to this
ID.
The two other fields, Source / Destination ID, should not be changed in any
way by a relay‐node; it is not necessary.
Upon reception of a packet, a node should look at those fields:
‐ If the Destination Device ID is his ID and the Next Physical ID is set to 0,
the packet should be sent to userspace for treatment.
‐ If the Destination Device ID is not his ID but the Next Physical ID is, the
packet should not leave kernel‐space and be properly relayed according to this
specification (Section 5 ROUTING).
‐ Otherwise, the packet should be dropped.
MeshNet [Page 19]