Multi-COBS: A Novel Algorithm for Byte Stuffing at High Throughput
Open Access
- 27 July 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 10, 78848-78859
Abstract
Framing methods are used to break a data stream into packets in most digital communications. The use of a reserved symbol to denote the frame boundaries is a popular practice. This end-of-frame (EOF) marker should be removed from the packet content in a reversible manner. Many strategies, such as the bit and byte stuffing processes employed by high-level data link control (HDLC) and Point-to-Point Protocol (PPP), or the Consistent Overhead Byte Stuffing (COBS), have been devised to perform this goal. These bit and byte stuffing algorithms remove the reserved EOF marker from the packet payload and replace it with some extra information that can be used to undo the action later. The amount of data added is called overhead and is a figure-of-merit of such algorithms, together with the encoding and decoding speed. Multi-COBS, a new byte stuffing algorithm, is presented in this paper. Multi-COBS provides concurrent encoding and decoding, resulting in a performance improvement of factor four or eight in common word-based digital architectures while delivering an average and worst-case overhead equivalent to the state-of-the-art. On the reference 28-nanometer field programmable gate array (FPGA) (Artix-7), Multi-COBS achieves a throughput of 6.6 Gbps, instead of 1.7 Gbps of COBS. Thanks to its parallel elaboration capability, Multi-COBS is ideal for digital systems built in programmable logic as well as modern computers.Keywords
This publication has 19 references indexed in Scilit:
- Relocation-aware communication network for circuits on Xilinx FPGAs2017
- Internet Protocol, Version 6 (IPv6) Specification2017
- Clock Buffers, Nets, and Trees for On-Chip Communication: A Novel Network Access Technique in FPGAs2017
- High-level data link control (HDLC) procedures2015
- IEEE Standard for Ethernet - Section 52015
- The Point-to-Point Protocol (PPP)2006
- An Improvement to the Bit Stuffing AlgorithmIEEE Transactions on Information Theory, 2005
- PCI express and advanced switching: evolutionary path to building next generation interconnects2004
- A simple data link protocol for high-speed packet networksBell Labs Technical Journal, 2002
- Consistent overhead byte stuffingIEEE/ACM Transactions on Networking, 1999