Layer 2 fragmentation

GSoC 2012: Martin Hundebøll's Final Report
Added by Marek Lindner almost 12 years ago

As one of the three "batman-adv students" in this years Google Summer of Code (GSoC), I was selected to redesign and implement the fragmentation feature in batman-adv.

The old implementation was designed before features like Translation Tables (TT) were added to batman-adv and thus lacks certain features that we would like to see. So we started the projects by defining a set of goals for the new design and came up with the following:

| Feature                       | Old | New |
| All Unicast Types             |     |  x  |
| Variable Number of Fragments  |     |  x  |
| Encapsulation                 |     |  x  |
| Early Merge                   |  x  |  x  |
| TTVN Path Altering            |  x  |     |

The new fragmentation supports both current and future unicast packet types; If needed it fragments packets into to more than two fragments; It uses encapsulation to be agnostic to other features in batman-adv; Intermediate hops on the path may merge the packet if it can be transmitted as one, but they cannot change the final destination if a client roams, because this requires information from the payload.


Packets too big to be transmitted on the selected outgoing interface are passed to the fragmentation code. Here, they are chopped into several smaller fragments and a fragment header is prepended to each fragment.

When being received by either the destination or an intermediate hop, the fragments are buffered until all fragments are received. When the last fragment arrives, the fragments are merged to the original packet, which is passed to the primary receive function in batman-adv.

Handling Very-Big-Translation-Tables™

The client handling system (also known as Translation Tables, TT, described here) occasionally needs to transmit a full table that might too large to be in one packet. Since the old fragmentation only handles unicast packets, it can not fragment these full table packets, and thus the TT code was made to simply cut of the end of the table if needed. This approach lead to a mismatch in checksums across the network and is more or less broken.

With the new fragmentation feature, full table packets (which are of a special unicast type) are now fragmented without the TT code knowing about it. This allows much bigger tables to be transmitted, but the size is now limited by the maximum number of fragments (16). To avoid sending truncated tables across the network, the TT code now checks size of the table before adding new entries, and thus always keeping the size of the table below the limit.

Further Information

Technical specification is given at the fragmentation page and questions are welcome on the mailing list.

fragment.png (6.64 KB) fragment.png Sven Eckelmann, 02/13/2017 07:53 PM
fragment.svg (7.32 KB) fragment.svg Sven Eckelmann, 02/13/2017 07:53 PM
rx_factory.png (31.2 KB) rx_factory.png Sven Eckelmann, 02/13/2017 07:53 PM
tx_factory.png (22 KB) tx_factory.png Sven Eckelmann, 02/13/2017 07:53 PM
unicast.png (1.77 KB) unicast.png Sven Eckelmann, 02/13/2017 07:53 PM
unicast.svg (3.47 KB) unicast.svg Sven Eckelmann, 02/13/2017 07:53 PM