Bit and Byte Stuffing
Computer Networks: Bit and Byte Stuffing 1
Synchronous versus Asynchronous
Transmissions
• There exists a hierarchy of synchronization
tasks:
– Bit level : recognizing the start and end of each
bit
– Character or byte level : recognizing the start
and end of each character (or small unit of data)
– Block or message level : recognize the start and
end of each large unit of data (in networks this
is a frame).
Computer Networks: Bit and Byte Stuffing 2
Synchronous versus Asynchronous
Transmissions [Halsall]
A fundamental requirement of digital data communications
is that the receiver knows the starting time and the
duration of each bit.
Asynchronous transmission :: each character (or byte) is
treated independently for clock (bit) and character (byte)
synchronization purposes and the receiver resynchronizes
at the start of each character received.
Synchronous transmission :: the complete frame is
transmitted as a contiguous string of bits and the receiver
endeavors to keep in synchronism with the incoming bit
stream for the duration of the frame.
Computer Networks: Bit and Byte Stuffing 3
Synchronization
in Asynchronous Transmissions
Transmitted at random intervals (e.g., keyboard)
Direction of transmission
Data bits
Line Start Stop
idle 1 2 3 4 5 6 7 8
bit bit
3T/2 T T T T T T T
Receiver samples the bits
Copyright ©2000 The McGraw Hill Companies Leon-Garcia & Widjaja: Communication Networks Figure 3.68
Computer Networks: Bit and Byte Stuffing 4
Synchronous Transmissions
• More efficient, i.e., less overhead
• Blocks of characters transmitted without
start and stop codes
• The transmitted stream is suitably encoded
so the receiver can stay in “synch” by:
– Using a separate clock line
– Embedding clocking information into data (e.g.
biphase coding).
Computer Networks: Bit and Byte Stuffing 5
Frame Identification Methods
[Tanenbaum]
1. Byte counts
2. Starting/ending bytes [byte stuffing]
3. Starting/ending flags [bit stuffing]
4. Using physical layer coding
violations (i.e., invalid physical
codes)
Computer Networks: Bit and Byte Stuffing 6
The contents of each frame are encapsulated between a
pair of reserved characters or bytes for frame synchronization.
frame
Preamble Postamble
Bit Pattern Bit Pattern
Computer Networks: Bit and Byte Stuffing 7
BISYNC Frame Format
8 8 8 8 8 16
Header Body CRC
Figure 2.9
P&D slide
Computer Networks: Bit and Byte Stuffing 8
PPP Frame Format
8 8 8 16 16 8
Flag Address Control Protocol Payload Checksum Flag
Figure 2.10
P&D slide
Computer Networks: Bit and Byte Stuffing 9
DDCMP Frame Format
8 8 8 14 42 16
Count Header Body CRC
Figure 2.11
P&D slide
Computer Networks: Bit and Byte Stuffing 10
HDLC Frame Format
8 16 16 8
Beginning Header Body CRC Ending
sequence sequence
Figure 2.12
P&D slide
Computer Networks: Bit and Byte Stuffing 11
Byte Stuffing
[HDLC Example]
• Also referred to as character stuffing.
• ASCII characters are used as framing delimiters
(e.g. DLE STX and DLE ETX)
• The problem occurs when these character patterns
occur within the “transparent” data.
Solution: sender stuffs an extra DLE into the data
stream just before each occurrence of an
“accidental” DLE in the data stream.
The data link layer on the receiving end unstuffs the
DLE before giving the data to the network layer.
Computer Networks: Bit and Byte Stuffing 12
Byte Stuffing
[HDLC Example]
DLE STX Transparent Data DLE ETX
Before
DLE STX A B DLE H W DLE ETX
Stuffed
DLE STX A B DLE DLE H W DLE ETX
Unstuffed
DLE STX A B DLE H W DLE ETX
Computer Networks: Bit and Byte Stuffing 13
Bit Stuffing
• Each frame begins and ends with a special bit
pattern called a flag byte [01111110]. {Note this is
7E in hex}
• Whenever sender data link layer encounters five
consecutive ones in the data stream, it automatically
stuffs a 0 bit into the outgoing stream.
• When the receiver sees five consecutive incoming
ones followed by a 0 bit, it automatically destuffs
the 0 bit before sending the data to the network
layer.
Computer Networks: Bit and Byte Stuffing 14
Bit Stuffing
Input Stream
0110111111100111110111111111100000
Stuffed Stream
01101111101100111110011111011111000000
Stuffed bits
Unstuffed Stream
0110111111100111110111111111100000
Computer Networks: Bit and Byte Stuffing 15
PPP (Point-to-Point Protocol)
Frame Format
Flag Address Control Protocol Information flag
CRC 01111110
01111110 1111111 00000011
All stations are to Unnumbered
Specifies what kind of packet is contained in the
accept the frame frame
payload, e.g., LCP, NCP, IP, OSI CLNP, IPX
Copyright ©2000 The McGraw Hill Companies Leon-Garcia & Widjaja: Communication Networks Figure 5.40
Computer Networks: Bit and Byte Stuffing 16
PPP Byte Stuffing
Flag Address Control Protocol Information flag
Flag
CRC 01111110
01111110 1111111 00000011 01111110
Input
7E 7D 33 7E 42 7E
Stuffed Stream
7E 7D 5D 33 7D 5E 42 7E
Unstuffed Stream
7E 7D 33 7E 42 7E
Computer Networks: Bit and Byte Stuffing 17