Content deleted Content added
Adding short description: "Algorithm for encoding data bytes" |
mNo edit summary |
||
Line 2:
'''Consistent Overhead Byte Stuffing''' ('''COBS''') is an [[algorithm]] for encoding data bytes that results in efficient, reliable, unambiguous [[Packet (information technology)#Packet framing|packet framing]] regardless of packet content, thus making it easy for receiving applications to recover from malformed packets. It employs a particular byte value, typically zero, to serve as a ''packet [[delimiter]]'' (a special value that indicates the boundary between packets). When zero is used as a delimiter, the algorithm replaces each zero data byte with a non-zero value so that no zero data bytes will appear in the packet and thus be misinterpreted as packet boundaries.
'''Byte stuffing''' is a process that transforms a sequence of data bytes that may contain 'illegal' or 'reserved' values (such as packet delimiter) into a potentially longer sequence that contains no occurrences of those values. The extra length of the transformed sequence is typically referred to as the [[Overhead (computing)|overhead]] of the algorithm. [[High-Level_Data_Link_Control#Asynchronous_framing|HDLC framing]] is a well-known example, used particularly in [[Point-to-point protocol|PPP]] (see [https://datatracker.ietf.org/doc/html/rfc1662#section-4.2 RFC 1662 § 4.2]). Although HDLC framing has an overhead of <1% in the ''average'' case, it suffers from a very poor ''worst''-case overhead of 100%; for inputs that consist entirely of bytes that require escaping, HDLC byte stuffing will double the size of the input.
The COBS algorithm, on the other hand, tightly bounds the worst-case overhead. COBS requires a minimum of 1 byte overhead, and a maximum of {{ceil|''n''/254}} bytes for ''n'' data bytes (one byte in 254, rounded up). Consequently, the time to transmit the encoded byte sequence is highly predictable, which makes COBS useful for real-time applications in which jitter may be problematic. The algorithm is computationally inexpensive, and in addition to its desirable ''worst''-case overhead, its ''average'' overhead is also low compared to other unambiguous framing algorithms like HDLC.<ref>
| |||