Consistent Overhead Byte Stuffing
Byte stuffing is a process that transforms a sequence of data bytes that may contain ‘illegal’ or ‘reserved’ values into a potentially longer sequence that contains no occurrences of those values. The extra length is referred to in this paper as the overhead of the algorithm. To date, byte stuffing algorithms, such as those used by SLIP [RFC1055], PPP [RFC1662] and AX.25 [ARRL84], have been designed to incur low average overhead but have made little effort to minimize worst case overhead. Some increasingly popular network devices, however, care more about the worst case. For example, the transmission time for ISM-band packet radio transmitters is strictly limited by FCC regulation. To adhere to this regulation, the 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), that tightly bounds the worst case overhead. It guarantees in the worst case to add no more than one byte in 254 to any packet. Furthermore, the algorithm is computationally cheap, and its average overhead is very competitive with that of existing algorithms.
Summary
This paper introduces Consistent Overhead Byte Stuffing (COBS), an encoding that eliminates reserved byte values while guaranteeing a strict upper bound on added framing overhead. Readers will learn the algorithm, its worst-case overhead analysis, and why it is useful for constrained embedded and wireless systems where predictable packet size matters.
Key Takeaways
- Explain the COBS encoding algorithm and how it guarantees a fixed worst-case overhead per packet.
- Implement COBS in firmware for microcontrollers and serial links to avoid delimiter collisions without unbounded growth.
- Calculate and compare average vs. worst-case overhead for COBS versus traditional byte-stuffing schemes like SLIP/PPP/AX.25.
- Apply COBS to constrained wireless/ISM-band systems to meet regulatory or timing limits by bounding transmit time.
- Replace or augment existing framing schemes to improve predictability of packet sizes in IoT and embedded communications.
Who Should Read This
Embedded firmware engineers and protocol designers (intermediate level) working on microcontroller-based IoT or wireless links who need predictable framing and worst-case packet-size bounds.
TimelessIntermediate
Related Documents
- PID Without a PhD TimelessIntermediate
- Introduction to Embedded Systems - A Cyber-Physical Systems Approach Still RelevantIntermediate
- Can an RTOS be really real-time? TimelessAdvanced
- Memory Mapped I/O in C TimelessIntermediate
- Design and Implementation of the lwIP Stack Still RelevantAdvanced
