Consistent overhead byte stuffing

Byte stuffing is a process that encodes a sequence of data bytes that may contain “illegal” or “reserved” values, using a potentially longer sequence that contains no occurrences of these values. The extra length is referred to here as the overhead of the encoding. To date, byte stuffing algorithms, such as those used by SLIP, PPP, and AX.25, have been designed to incur low average overhead, but little effort has been made to minimize their worst-case overhead. However, there are some increasingly popular network devices whose performance is determined more by the worst case than by the average case. For example, the transmission time for ISM-band packet radio transmitters is strictly limited by FCC regulation. To adhere to this regulation, the current practice is to set the maximum packet size artificially low so that no packet, even after worst-case overhead, can exceed the transmission time limit. This paper presents a new byte stuffing algorithm, called consistent overhead byte stuffing (COBS), which tightly bounds the worst-case overhead. It guarantees, in the worst case, to add no more than 1 byte in 254 to any packet. For large packets, this means that their encoded size is no more than 100.4% of their pre-encoding size. This is much better than the 200% worst-case bound that is common for many byte stuffing algorithms, and is close to the information-theoretic limit of about 100.07%. Furthermore, the COBS algorithm is computationally cheap, and its average overhead is very competitive with that of existing algorithms