AFP header desciption

The information needed to reconstruct events from fragments is encoded in the AFP header. The header is optimized for size to be usable as well for network protocols with low payload, like CAN.

The AFP header consists of one to multiple sub-headers, depending on the AFP configuration used. The Basic Fragment Header is always part of the AFP header. It may be followed by one or multiple Extension headers.

Numbers are encoded in network byte order. All fragments except the last event data fragment occupy the complete MTU, only this one may be smaller.

Basic Fragment Header

The length of the basic AFP header is the minimum length necessary to encode the fragment sequence number.

The header contains whether there are extension headers behind the basic header, if the current fragment is the first fragment of an event and the fragment sequence number. The fragment sequence number specifies how many fragments follow behind the current fragment. Thus it's downcounting from fragment_count-1 to 0. The length of the fragment sequence number is encoded in the first part of header in unary coding.

Header Bits	# Bytes Header	# Bits of fragment sequence number (s)
0efs ssss	1	5
10ef ssss | ssss ssss	2	12
110e fsss | ssss ssss | ssss ssss	3	19
1110 efss | ssss ssss | ssss ssss | ssss ssss	4	26
1111 0efs | ssss ssss | ssss ssss | ssss ssss | ssss ssss	5	33
...

• e: extension header?
• f: first fragment?
• ssss ....: fragment sequence number = how many fragments will be there behind this fragment (downcounting to zero)

Extension headers

Both implemented extension headers start with a zero bit followed by a bit that indicates whether there is one more extension header behind the current header and a zero bit that selects implicit size coding. The remaining bits of the first byte selects the header type.

In this implementation all fragments of an event must have the same extension headers and use implicit size coding.

Event Sequence Numbers

Event sequence numbers are not used to guarantee any order in delivery of events, but only to distinguish between concurrent events, including events overlapping in time because of packet loss or reordering. Currently AFP supports only 32 bit event sequence numbers.

Header Bits	# Bytes Header	# Bits of event sequence number (s)
0e00 0000 | ssss ssss | ssss ssss | ssss ssss | ssss ssss	5	32

• e: one more extension header?
• ssss ....: event sequence number (unique for one publisher for a long time)

Forward Error Correction

AFP provides forward error correction to provide the possibility to increase reliability of event delivery in face of packet loss. For this purpose it uses a block oriented erasure code based on Vandermonde matrices. The current AFP implementation utilizes a FEC library written by Luigi Rizzo that can be found at http://info.iet.unipi.it/~luigi/fec.html.

Because the currently used forward error correction library requires the fragment's payload sizes to be equal, the current implementation differs from the concept described in the paper. While the header may differ in length, the payload length is constant for all fragments. Thus, the MTU is not occupied completely for all fragments. The used FEC library also suffers from the restriction that the payload must have an even length. If p = (MTU - largest header length) is odd, the payload is set to p-1.

To increase the probability that an event consisting of k fragments can be reconstructed in face of packet loss, (n-k) fragments are added that consist of redundancy information. The FEC code used is able to reconstruct the message even if (n-k) arbitrary fragments are lost.

The number of event data fragments k is included in the FEC header, because this information is only in the Basic Fragment Header of the first fragment of an event which may be lost.

The header also contains the redundancy quota r in percent. It is used to calculate the total number of fragments n (sum of event data and redundancy fragment count).

n = (k * r) / 100 + k

It has to be calculated using integer arithmetics. The quotient (k * r) / 100 is an integer devision rounding up.

The header also contains the length of the last non-redundancy (event data) fragment l. In case this fragment is lost we need the information to find out the total length of the reconstructed event.

Header Bits	# Bytes Header
0e01 1001 | rrrr rrrr | kkkk kkkk | kkkk kkkk | kkkk kkkk | kkkk kkkk | llll llll | llll llll	8
0e01 0101 | rrrr rrrr | kkkk kkkk | kkkk kkkk | llll llll | llll llll Not implemented yet.	6
0e01 0000 | rrrr rrrr | kkkk kkkk | llll llll Not implemented yet.	4

• e: one more extension header?
• rrrr rrrr: redundancy in %
• kkkk ...: # data / non-redundancy fragments
• llll ...: length of last data / non-redundancy fragment

Others

There may be future extensions.