Open-Mesh

My GSoC 2012 task centered around the question how batman-adv could better handle backward compatibility when new features requiring packet format changes are added. The batman-adv packets already carry a compatibility number but it was time to introduce a less obtrusive mechanism on top of it - the TVLV infrastructure.

Introduction¶

While looking at the originator packet (OGM) which is used for the routing algorithm and announcing features the dilemma becomes quite obvious. The OGM contains the aforementioned compatibility number along with a number of fields needed for the routing (like interval, sequence number, TQ, etc) plus some features fields (for example gateway flags, tt version, etc).

Illustration of an OGM packet:

  0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |  Packet Type  |    Version    |     TTL       |     Flags     |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                       Sequence Number                         |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                     Originator Address                        |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |      Originator Address       |    Previous Sender Address    |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                   Previous Sender Address                     | 
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 | Gateway Flags |       TQ      |TT Num Changes |     TT VN     |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |            TT CRC             |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Here, the task of the compatibility number is to ensure that a node receiving an OGM packet is able to parse it and that every node interprets the routing information contained in the packet in the same way. There is not much we can do about the latter but many newly added features only need some form of announcement and can be useful even if only some nodes support it (as long as the feature does not touch vital parts of the mesh network).

A real world example: The soon to-be-added distributed ARP table (DAT) allows to retrieve the mac address belonging to a client without going through a time consuming ARP discovery operation. Nodes with this new feature enabled could perform the fast lookup for their clients while the non-DAT nodes can still use the standard ARP mechanism. The fast lookup requires to know which of the peer nodes also supports the fast lookup and which nodes don't. This can easily be addressed by advertising DAT support via OGMs.

TVLV Concept¶

The project's goal is to provide the infrastructure for sending, receiving and parsing information 'containers' while preserving backward compatibility. TVLV (based on the commonly known Type Length Value technique) was chosen as the format for those containers.

TVLV layout:

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |   TVLV Type   |    Version    |    Length     |  Value
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The 'tvlv type' field describes the content of 'value' and the 'length' field the number of bytes till the end of the container. Even if a node does not know the tvlv type of a certain container it can simply skip the current container and proceed with the next. Past experience has shown features evolve over time, so a 'version' field was added right from the start to allow differentiating between feature variants - hence the name: T(ype) V(ersion) L(ength) V(alue).

All the OGM will carry in the future are the bare routing information and a collection of TVLV containers. If a node wishes to send a new / unknown TVLV type it can do so without requiring each node in the network to be able to parse it. A lean TVLV API will be provided to make using the TVLV infrastructure as painless as possible.

Further information¶

All features currently taking advantage of the OGM to flood information through the network have to be converted to the TVLV infrastructure. Of course, TVLVs are not limited to OGM packets only. Other packet types may also benefit from this abstraction (TT_REQUEST and vis packets are good examples). Typical packet types not suitable for tvlv-ization are performance critical packets such as unicast payload. For those packets the overhead does not justify the gain in compatibility. The TVLV page contains an overview about the various TVLV types and the API as well as the state of development.

Keep in mind that by implementing the TVLV infrastructure batman-adv does not magically become backward compatible in every single aspect. TVLV is a starting point allowing individual features to build upon. How backward compatibility can be ensured and whether it is feasible has to be decided on a case-by-case basis. Each feature will have to implement a mechanism to handle 'old' versions of the same feature.

When TVLVs are going to be merged into the mainline repository the compatibility number has to be increased once more because the packet format changes. As a consequence, the TVLVs won't be merged before the tvlv-ization of the existing features has been completed.