Preliminaries
=============

A list of n bytes is represented by n+1 bytes: the first byte is the
length of the list, and the other bytes the content.  Example: 

  3  el1 el2 el3 
+---+---+---+---+...

A data content is represented with a byte that counts the length of
the content, and with the bytes of the content itself, for example: 

  4   d1  d2  d3  d4
+---+---+---+---+---+...


General Packet Structure
========================

There are two types of packets: Broadcast, and Routed. 
Their content is as follows. 

Broadcast
---------

  1  src nce body...
+---+---+---+-----------

- 1 means broadcast
- src is the source address
- nce is a "nonce", a non-recently used byte to prevent rebroadcasts
- body is the body of the packet (see later). 

Routed
------

  2  src route list   body
+---+---+-----------+---------....

- 2 means routed
- src is the source address

- route is a list of addresses, prescribing the route. 
  For example, a route of 3, 5, 6 means that the packet should be
  forwarded by 3, with the new route 5, 6. When the route is a single
  integer, for intance 6, and node 6 receives the packet, then the
  packet has arrived at the destination. 

- body: described later.  


Broadcast packets: body structure
=================================

There are two types of broadcast packets: RR (Route Request) and RP
(Route Reply).  The body of each type has the following format: 

RR packet
---------

  1  dst visited list
+---+---+------------+

- 1 means body RR 
- dst is the destination
- visited list is the list of nodes that have routed this packet so
  far, including the originating node. 

RP packet
---------

  2  dst visited list reverse path
+---+---+------------+------------+

- 2 means body RP
- dst is the destination
- visited list is the list of nodes that have routed this packet so
  far, including the originating node. 
- reverse path is the list of nodes visited in the original direction
  of the query, starting with the original source node (what is now
  dst), and ending with the original destination node (what is now
  src).


Routed packets: body structure
==============================

There are three types of routed packets: RC (route confirmation), DT
(data), AK (acknowledge).  The body of each type has the following
structure: 

RC packet
---------

  1  reverse path
+---+------------+

- 1 means RC body
- reverse path is the path from the destination of this packet to the
  source. 

DT packet
---------

  2  data content
+---+------------+

- 2 means DT body 
- data content is, well, the data content. 



Example
=======

Assume that host 1 tries to establish communication with host 7, with
route 1 -> 3 -> 7 and reverse route 7 -> 4 -> 1. 
The flow of packets is as follows (I just list one integer per byte,
spaces are non-significant): 

================================================================

Sent from 1: 

1 1 8  1 7 1 1 

Broadcast, source is 1, nonce is 8.  
RR body, dest is 7, route list is 1. 

================================================================

Sent from 3: 

1 1 8  1 7 2 1 3 

As above, but now the route list is 1 3. 

================================================================

sent from 7: 

1 7 5  2 1  1 7  3 1 3 7 

Broadcast, source is 7, nonce is 5. 
RP body, dest is 1, route list is 7, reverse list is 1 3 7. 

================================================================

sent from 4: 

1 7 5  2 1  2 7 4  3 1 3 7 

Broadcast, source is 7, nonce is 5. 
RP body, dest is 1, route list is 7 4, reverse list is 1 3 7. 

================================================================

sent from 1: 

2 1  2 3 7  1 3 7 4 1

Routed, from 1, route is 3 7.
RC body: reverse list 7 4 1 

================================================================

sent from 3: 

2 1  1 7  1 3 7 4 1

Routed, from 1, route is 7.
RC body: reverse list 7 4 1 

================================================================

At this point, the communication is established. 
Now, we follow a data from 1 to 7, followed by the ack. 

================================================================

sent from 1: 

2 1  2 3 7  2  8 1 2 3 4 5 6 7 8

Routed, from 1, route is 3 7.
DT body, content is 1 2 3 4 5 6 7 8. 

================================================================

sent from 3: 

2 1  1 7  2  8 1 2 3 4 5 6 7 8

Routed, from 1, route is 7.
DT body, content is 1 2 3 4 5 6 7 8. 

================================================================