Module - 2

Perspective of Connecting
Links
• point-to-point fiber links (for which SONET is the
prevalent example)
• Carrier Sense Multiple Access (CSMA) networks
(of which classical Ethernet and Wi-Fi are the
most famous examples);
• fiber-to-the home (for which PON is the dominant
standard) when compared to AON
• mobile wireless (where 4G is rapidly morphing
into 5G)
 Links (Bandwidth)

Common services available to connect your home

Encoding Techniques
■ Analog data to analog signal conversion
■ Amplitude Modulation

■ Phase Modulation &

■ Frequency Modulation

■ Digital data to analog signals

■ Amplitude Shift Keying

■ Frequency Shift Keying &

■ Phase Shift Keying

■ Digital data to Digital signals

■ Non-Return to Zero

■ Bi-phase encoding

■ Block encoding
Digital Encoding Techniques
■ Translate binary data onto two kinds of
signals
■ 0 => low signal
■ 1 => high signal
Unipolar (On-Off Keying or simply OOK)

❑ In Unipolar encoding, the polarity is assigned to the 1 binary state.

❑ In this, 1s are represented as a positive value and 0s are represented
as a zero value.
❑ In Unipolar Encoding, '1' is considered as a high voltage and '0' is
considered as a zero voltage.
❑ Unipolar encoding is simpler and inexpensive to implement.
Non Return to Zero/Level (NRZ / NRZ-L)
❑ Non Return to Zero signal involves both the positive and negative
voltages.

❑ Level of voltage determines the value of a bit.

❑ We take positive and negative voltages to represent bit 1 and 0
respectively or Vice-Versa

Data 01001110.
(NRZ / NRZ-L) - Problems
❑ Sequence of several consecutive 1s means that the signal stays high
on the link for an extended period of time.

❑ This creates a problem on the receiving end because, the clock

synchronization is lost due to lack of any transitions.

❑ It is difficult to determine the exact number of 0s or 1s in this

sequence
Non Return to Zero Inverted (NRZI)
❑ A magnetic recording and data modulation method
❑ the polarity of the bit is reversed when a 1 bit is
encountered
❑ All subsequent 0s following the 1 are recorded at the
same polarity
Manchester Encoding
❑ Manchester encoding is a widely used line coding scheme that
embeds timing information in the transmitted signal.

❑ There is a transition (high-to-low or low-to-high) in the middle of every

bit time.

❑ Each bit is transmitted in a fixed time (the "period").

❑ A 0 is expressed by a low-to-high transition, a 1 by high-to-low

transition (according to G. E. Thomas's convention – in the IEEE
802.3 convention, the reverse is true).

❑ The transitions which signify 0 or 1 occur at the midpoint of a period.

❑ Transitions at the start of a period are overhead and don't signify

data.
❑ Easy for the receiver to retrieve a clock signal from the incoming bit
stream and maintain synchronization with the transmitted signal
4B/5B Encoding.
❑ In Manchester encoding scheme , there is a transition after every bit.

❑ It means that we must have clocks with double the speed to send
same amount of data.

❑ This performance factor can be significantly improved if we use a

better encoding scheme.

❑ Like if we have a transition after every four bits, then we will be

sending 80% data of actual capacity.

❑ Here we convert 4-bits to 5-bits, ensuring at least one transition in

them.

❑ One leading 0
❑ no more than two trailing 0s
❑ ensured that we can never have more than three
consecutive 0s.
4B/5B Encoding.

Some control information like

line idle(11111),
line dead(00000),
Halt(00100) etc.
Types of Errors
Single-bit error
Multiple-bit error
Burst error
❑ The term burst error means that two or
more bits in the data unit have changed
from 1 to 0 or from 0 to 1.

❑ Burst errors does not necessarily mean

that the errors occur in consecutive bits,
the length of the burst is measured from the
first corrupted bit to the last corrupted bit.

❑ Some bits in between may not have been

corrupted.
 Error Detection

• Detection
• Correction
Basic concepts
★ Networks must be able to transfer data from
one device to another with complete accuracy.
★ Data can be corrupted during transmission.
★ Due to some noise or eavesdropping
★ Network connection issues etc.,
★ For reliable communication, errors must be
detected and corrected.

★ Error detection and correction are

implemented either at the data link layer or the
transport layer of the OSI model.
Network Units
Network Units
Frame
Part of a Data Link Layer (Transmits set of bits)
• A frame header contains control information
• A payload field for holding the packet (Actual Data
– your email content/video/audio/file/text etc…)
• A frame trailer
Framing.. Contd.,
• Frame Start bits
• Address (Source and Destination)
• Type of Data
• Quality Control

• Error Detection
• Frame Stop Bits
Types of Frames

• Fixed Size Framing

– No Issues in defining the boundaries
– Ex: - ATMs, WAN (Cells)

• Variable Size Framing

– Need to Identify the start and End
Ex: Let start and End be 11011
– 1101101101101011011

1101101101101011011
Solution for Variable Length Framing
Byte Counting Techniques
• Data link layer at sender sends the byte count.
• Data link layer at receiver counts the byte count, sent by
sender.
• If there is difference between bytes counts of sender and
receiver. There is error in data received.
• Else received data is correct.
Flag Byte with byte/Character stuffing
• Each frame should start and end with a special byte code
(Flag Byte).
• Two consecutive flag bytes indicate the end of one frame and
start of the next one.
• If flag bytes occur in the frame, stuff an extra frame called as
ESC (Escape) byte.
Bit stuffing
• Allows frame to contain arbitrary number of bits and
arbitrary character size.

• The frames are separated by separating flag.

• Each frame begins and ends with a special bit pattern,

01111110 called a flag byte.

• When five consecutive l's are encountered in the data, it

automatically stuffs a '0' bit into outgoing bit stream.
 Error detection
Error detection means to decide whether the
received data is correct or not without having a
copy of the original message.

Error detection uses the concept of redundancy,

which means adding extra bits for detecting
errors at the destination.
Methods for Detection
• Parity Checker

• Checksum

• Cyclic Redundancy Check

Simple Parity Check
• One extra bit is transmitted in addition to the original bits.
– To make the number of 1’s even in the case of even parity
– odd in the case of odd parity

• While creating a frame, the sender counts the amount of 1’s in it.

• The receiver just counts how many 1s are in a frame.

– If the number of 1s is even and even parity is utilized, the frame is
regarded as uncorrupted and approved.
– Similarly for odd parity

• The receiver can identify a single bit flip in transit by counting the
number of 1s.
Parity = The fact of being even or odd.
 Two-Dimensional Parity Check:
• Used especially for large block of data (32 Bit, 64 Bit, 128
Bit etc.,)
• Overcomes Single parity check limitations
– Every block need to be appended with additional parity bit
– Cannot check even no. of 1’s in a single blocks.
Checksum Error Method
• The data is divided into k segments each of m bits.

Sender Side
• The segments are added using 1’s complement arithmetic to get the sum.
• The Final sum is complemented to get the checksum.
• The checksum segment is sent along with the data segments.

Receiver Side
• At the receiver’s end, all received segments are added using 1’s
complement arithmetic to get the sum.
• The sum is complemented.
• If the result is zero, the received data is accepted; otherwise discarded.
Example
Cyclic Redundancy Check (CRC)
❑ Error detection technique to detect errors in data that has been
transmitted on a communications link.

❑ Works w.r.t Polynomial Math.

❑ Application
❑ Digital Networks (At Data Link Layer)
❑ Storage Devices
IEEE 802.3 Ethernet Format
CRC - Overview
Basic Steps

1. CRC Generator ( Sender Side)

2. CRC Checker (Receiver Side)
CRC - Method
Sender Side
1. Sender has a generator G(x) polynomial.
2. Sender appends (n-1) zero bits to the data.
3. Where n= no of bits in generator
4. Dividend appends the data with generator G(x) using modulo 2 division
(arithmetic).
5. Remainder of (n-1) bits will be CRC.

Objective : Generate Code Word = Data bits + CRC bits.

Example :
1. Data is 10110.
2. code generator is 1101 (Sometimes Mentioned in Terms of Polynomial)
CRC – Method Contd.,
Calculate CRC Bits:

1. Follows XOR Operation.

Cyclic redundancy check is 101. Thus, the sender sends

10110101 to the receiver.
CRC - Method
Receiver Side:
1. Receiver has same generator G(x).
2. Receiver divides received data (data + CRC) with generator.
3. If remainder is zero, data is correctly received.
4. Else, there is error.

Note: It does not add any padding bits, rather calculates from the entire received code
word.

The CRC bits are calculated to

be different. Thus, there is an
error detected.
Exercise
The data stream is 10110011 and the generator
polynomial is x4+x+1.
Check for CRC
CRC - Standards
Six generator polynomials that have become international
standards are:
– CRC-8 = x8+x2+x+1
– CRC-10 = x10+x9+x5+x4+x+1
– CRC-12 = x12+x11+x3+x2+x+1
– CRC-16 = x16+x15+x2+1
– CRC-CCITT = x16+x12+x5+1
– CRC-32 = x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1

Detailed Information : [Link]

Summary
Reliable Transmission
❑ CRC is used to detect errors.
❑ Some error codes are strong enough to correct errors.
❑ The overhead is typically too high.
❑ Corrupt frames must be discarded.
❑ A link-level protocol that wants to deliver frames reliably
must recover from these discarded frames.
❑ This is accomplished using a combination of two
fundamental mechanisms.
❑ Acknowledgements and Timeouts
Solution 1 : Stop and Wait Protocol

• After transmitting one frame, the

sender waits for an acknowledgement
before transmitting the next frame.

• If the acknowledgement does not arrive

after a certain period of time, the
sender times out and retransmits the
original frame.
Stop and Wait Protocol
Stop and Wait Protocol
Issue/Problem
• If the acknowledgment is lost or delayed in arriving

– The sender times out and retransmits the original frame, but the
receiver will think that it is the next frame since it has correctly
received and acknowledged the first frame.

– As a result, duplicate copies of frames will be delivered

Solution (Automatic Repeat Request)

Use 1 bit sequence number (0 or 1)

When the sender retransmits frame 0, the receiver can determine that
it is seeing a second copy of frame 0 rather than the first copy of
frame 1 and therefore can ignore it (the receiver still acknowledges it,
in case the first acknowledgement was lost)
Assumptions of Stop and Wait
• It assumes that the communication channel is
perfect and noise free.

• Data packet sent by the sender can never get

corrupt.

• There is no concept of negative acknowledgements.

• There is no concept of time out timer.

• There is no concept of sequence numbers.

 Self Study

Stop and Wait ARQ | Sliding Window Protocols

1. What is the solution when data packet is lost?

2. Solution when acknowledgement is lost?

3. Solution when acknowledgement is delayed?

4. Solution when the packet gets damaged?