Computer Networks- MODULE -2

Qn-1 : Define what is an error and explain different types with examples.

ANS:Error: In computer networks, when data is transmitted from a sender to a receiver, the
bits may get altered due to noise, interference, or signal [Link] error means the
received data does not match the transmitted data.

Types of Errors

1. Single-bit Error

 Only one bit of a data unit (byte, character, or packet) is changed.

 Example:
Sent: 1011001
Received: 1010001 (3rd bit flipped).
 Common in wireless channels but less likely in wired connections.

2. Burst Error

 Two or more consecutive bits in the data unit are altered.

 Example:
Sent: 1011001
Received: 1000111 (middle bits corrupted).
 More common in real networks because noise often affects multiple bits together.
 The length of a burst error is the distance between the first and last corrupted bits.

Qn- 2 : Explain redundancy in error detection and correction.

ANS:When we send data over a network, errors can occur. To handle this, the sender adds
some extra bits (called redundant bits) to the original data before transmission.

 These bits do not carry information, but they help the receiver detect (and sometimes
correct) errors.

 At the receiver side, these redundant bits are checked. If the pattern doesn’t match
what is expected, the receiver knows an error has occurred.

Types of Redundancy Techniques

1) Parity Bit (Single Parity Check)
2) Block Coding (Linear Block Codes)
3) Cyclic Redundancy Check (CRC)
4) Checksum
Qn- 3 : Differentiate between error detection and error correction.

ANS:Error Detection vs Error Correction

Aspect Error Detection Error Correction

Identifies if an error has occurred in Identifies and also corrects the error
Meaning
the received data. without retransmission.
To detect errors and request To detect and fix errors at the receiver
Purpose
retransmission. itself.
Redundancy Requires more redundant bits to locate
Requires fewer redundant bits.
Required the exact error position.
Complexity Simple and less costly. More complex and costly.
Hamming code, Reed–Solomon,
Methods Used Parity check, Checksum, CRC.
Convolutional codes.
If error is detected → data is If error is detected → error is
Action Taken discarded, and retransmission is corrected at the receiver (no need for
requested (ARQ). retransmission).

Qn- 4 : Define Hamming distance. How is it used for error detection and correction?
ANS :Definition:The Hamming distance between two binary words of the same length is
thenumber of bit positions in which they differ.

How it helps in Error Detection

Imagine we have a set of valid codewords.
If the minimum Hamming distance between any two codewords is dmin
o The code can detect up to (dmin – 1) errors.

How it helps in Error Correction

To correct errors, the receiver must figure out which original codeword was meant.
If the received word is closer (in Hamming distance) to one valid codeword than to
others, we assume that was the sent codeword.
For this to work, the minimum distance must be large enough:
o The code can correct up to (dmin−1)/2 errors.
Qn- 5 : Explain linear block codes with an example.

ANS :Inblock coding, the message is divided into blocks of fixed length k bits, called
datawords. To each dataword, we addredundant bits(r) to make a longer block of
n=k+r, bits, called acodeword. If the set of all codewords forms alinear subspace
the code is called aLinear Block Code.

Example: (7,4) Hamming Code

Here, k=4 (data bits), n=7 (codeword length), so r=3 (redundant bits).

Dataword: 4 bits (say 1011).

Codeword: 7 bits (data + redundancy).

Step 1: Place data bits

Positions 3, 5, 6, 7 carry data bits.
So initially: _ _ 1 _ 0 1 1

Step 2: Place parity (redundant) bits

Positions 1, 2, 4 are parity bits.

Rules (each parity covers certain positions):

p1 covers bits 1,3,5,7
p2 covers bits 2,3,6,7
p3 covers bits 4,5,6,7

Step 3: Calculate parity values (even parity)

For 1011 (d1=1, d2=0, d3=1, d4=1):
p1→ parity of (1,3,5,7) = (p1,1,0,1) → p1 = 0
p2→ parity of (2,3,6,7) = (p2,1,1,1) → p2 = 1
p3→ parity of (4,5,6,7) = (p3,0,1,1) → p3 = 0

Step 4: Final Codeword

So the 7-bit codeword = 0 1 1 0 0 1 1
Qn- 6 :Explain the parity-check code with encoder and decoder structure.

ANS :Parity-Check Code

A parity-check code is the simplest linear block code.
For each k-bit dataword, we add 1 redundant bit (parity bit) to make the number of 1s
in the codewordeven (even parity) or odd (odd parity).
So, n=k+1.
Minimum Hamming distance: dmin=2.
o Can detect 1-bit errors.
o Cannot correct any errors.

Encoder Structure (Sender Side)

Input: k-bit dataword.
1. Count the number of 1s in the dataword.
2. If using even parity → set the parity bit so total number of 1s becomes even.
If using odd parity → set the parity bit so total number of 1s becomes odd.

Output: codeword of n=k+1 bits.

Decoder Structure (Receiver Side)

Input: n-bit received codeword.
1. Check the total number of 1s.
2. If it matches the expected parity (even or odd), assume no error.
3. If it does not match, declare error detected.
Action:
o If no error → accept data bits (drop parity).
o If error detected → discard dataword (retransmission needed).
Qn- 7 :Explain the concept of cyclic codes with examples.
ANS :Cyclic Codes
Cyclic codes are a class of linear block codeswith an extra property, If a valid
codeword is cyclically shifted (rotated), the result is still a valid [Link] are
widely used in computer networks for error detection
e.g., Cyclic Redundancy Check – CRC.

Encoder appends redundant bits to the dataword using polynomial division.

At the receiver, the same division is performed.
o If remainder = 0 → no error detected.
o If remainder ≠ 0 → error detected.
Generator polynomial g(x) decides the error detection capability.

Example
Dataword = 1001 → x3+1
Generator = 1011 → g(x)= x3+x+1

Append 3 zeros → 1001000

Divide by 1011 → remainder = 110

Final codeword = 1001110

If the receiver divides the received codeword by 1011 and remainder ≠ 0 → error
detected.

Advantages
1) Detects single-bit, many double-bit, odd number, and burst errors effectively.
2) Easy to implement in hardware/software.
Qn- 8 :Explain the working of Cyclic Redundancy Check (CRC) with encoder and decoder.
ANS :Cyclic Redundancy Check (CRC)
CRC is an error-detecting technique based on cyclic codes. It uses polynomial division to
generate redundancy bits (called CRC bits).

Working of CRC Encoder (Sender Side)

1. Represent the dataword as a polynomial M(x).
2. Choose a generator polynomial g(x) of degree r.
3. Append rrrzeros to the dataword → xr⋅M(x)
4. Divide xr⋅M(x) by g(x) using modulo-2 division.
5. The remainder R(x) (with r bits) is the CRC bits.
6. Append R(x) to the dataword → this forms the codeword.

Working of CRC Decoder (Receiver Side)

1. Receive the codeword (may contain errors).
2. Divide the received polynomial by the same generator polynomial g(x).
3. If the remainder = 0 → no error detected.
4. If the remainder ≠ 0 → error detected, discard/retransmit.

Example
 Dataword = 1001 → M(x)=x3+1
 Generator = 1011 → g(x)=x3+x+1, degree r=3
 Append 3 zeros → 1001000
 Divide by 1011 → remainder = 110
 Codeword = 1001 110

At receiver: Divide codeword by generator. If remainder = 0 → accept; else → error.

Qn9 : Represent a bit pattern as a polynomial. Explain polynomial addition and
division with examples.
ANS :
Bit Pattern as Polynomial
A binary bit pattern can be represented as a polynomial in which, each bit is a
coefficient (0 or 1).The position of the bit indicates the power of x.
Example:
Bit pattern 101101 = x5+x3+x2+1

Bits at positions 5,3,2,0 are 1 → corresponding terms appear in polynomial.

Polynomial Operations in Error Detection

1. Polynomial Addition (Modulo-2)

In binary polynomial arithmetic, addition = XOR.

Rules:
0+0=01+0=10+1=11+1=0

Example:
(x5+x3+x+1)+(x4+x3+x2+1)
= x5+(x3+x3)+x4+x2+x+(1+1)
= x5+x4+x2+x
Bitwise: 101011 + 110011 = 011010.

2. Polynomial Division (Modulo-2 Division)

Steps:
1. Align divisor (generator polynomial) with leftmost 1 of dividend.
2. Perform XOR.
3. Bring down next bit, repeat until done.
4. The remainder = CRC bits.

Example:
Divide 1001000 (i.e. x6+x3) by generator 1011 (i.e. x3+x+1)

Step 1: 1001 ÷ 1011 → Quotient bit = 1

XOR: 1001 ⊕ 1011 = 0010

Bring down next 0 → 00100

Divide 0100 by 1011 → Quotient bit = 0 (skip)

Bring down → 1000 ÷ 1011 → Quotient bit = 1

 XOR: 1000 ⊕ 1011 = 0011

Final remainder = 011 = (x+1)

So, (x6+x3)÷(x3+x+1)=quotient+(x+1)

Qn10: A dataword1001 is to be transmitted using generator 1011. Show the steps to

generate the codeword.
ANS :
Given
Dataword = 1001 → M(x)=x3+1
Generator (divisor) = 1011 → g(x)=x3+x+1
Degree of generator = 3 → so r=3 redundant bits

Steps to Generate Codeword

Step 1: Append r zeros to dataword

Dataword = 1001
Append 3 zeros (since r = 3)

Dividend = 1001000

Step 2: Divide dividend by generator (Modulo-2 Division)

We divide 1001000 by 1011 (XOR instead of subtraction).Long Division Process:

Quotient: 1001
Divisor: 1011 ) 1001000
1011
-------------
00110
1011
-------------
1010
1011
-------------
011← Remainder
Final Remainder = 011 (3 bits).

Step 3: Append remainder to dataword

Dataword = 1001
Remainder = 011
Codeword = 1001 011

Final Answer: Remainder (CRC bits): 011Transmitted Codeword: 1001011

Qn11: Prove that a generator with factor (x+1) can detect all odd-number errors

ANS :Let g(x) be the generator polynomial and

suppose g(x) has (x+1) as a factor.

For any binary polynomial p(x)=∑aixi, evaluating at x=1gives the parity of its
coefficients:

p(1)=∑ai (mod2).

So p(1)=0if the number of 1s is even, and p(1)=1, if the number of 1s is odd.

Because g(x) contains factor (x+1), we have g(1)=0.

If a polynomial p(x)is divisible by g(x), then p(1)=g(1)⋅h(1)=0 p(1)

In short: any polynomial divisible by g(x) must evaluate to 0 at x=1.

Let e(x) be an error polynomial that represents an odd number of bit-flips.

By step 2, e(1)=1

If e(x) were divisible by g(x), step 3 would force e(1)=0. That contradicts e(1)=1.
Therefore e(x)is not divisible by g(x).

Since the receiver checks divisibility by g(x) (CRC check), the division yields a
nonzero remainder for every odd-weight error polynomial. Hence all odd-number
errors are detected.

Examples

Example 1 — single-bit error

Error: only bit 2 flipped → error polynomial e(x)=x2.
Evaluate at x=1 e(1)=1 (odd).
Because e(1)=1e(x) cannot be divisible by any polynomial that has factor (x+1).
So CRC with such a generator will give a nonzero remainder → error detected.

Example 2 — three-bit error

Error: bits 3,1,0 flipped → e(x)=x3+x+1
Evaluate at x=1: e(1)=1+1+1=3 (mod 2)
Again e(1)=1 so e(x) is not divisible by any generator having (x+1).
CRC remainder ≠ 0 → detected.
Qn12: Explain how cyclic codes detect:
1) Single-bit errors
2) Double-bit errors
3) Odd number of errors
4) Burst errors

ANS :Cyclic Codes and Error Detection

Cyclic codes, such as those used in Cyclic Redundancy Check (CRC), are
powerful error-detecting codes. Their detection ability depends on the properties of the
generator polynomial g(x). Different error patterns can be described as error
polynomials & CRC test detects them if those polynomials are not divisible by g(x).

1) Single-bit errors
A single-bit error means only one bit is flipped. The error polynomial is of the
form e(x)=xi.
If the generator polynomial g(x) has more than one term, then no single power
of x is divisible by g(x).
This guarantees that the remainder after division is nonzero, so all single-bit
errors are detected.

2) Double-bit errors
A double-bit error at positions i and j is given by e(x)=xi+xj=xj(xi−j+1).
Such an error will escape detection only if g(x) divides (xi−j+1).
By choosing a generator that does not divide any polynomial of the form (xt+1)
for small t, cyclic codes can detect all double-bit errors separated by up to certain
distances.
Thus, most double-bit errors are detected with a properly chosen generator
polynomial.

3) Odd number of errors

If the generator polynomial g(x) has the factor (x+1), then it evaluates to zero
when x=1. An error polynomial with an odd number of flipped bits evaluates to one,
when x=1.
This means it cannot be divisible by g(x), so every such error produces a
nonzero remainder.
Therefore, a generator with (x+1) detects all odd-number errors.

4) Burst errors
A burst error of length L means a sequence of consecutive bits is corrupted.
Cyclic codes can detect these very effectively:
 If L≤r (where r is the degree of the generator), all burst errors are detected.
If L=r+1, detection is guaranteed with probability 1− (1/2r−1).
If L>r+1, detection probability is 1−(1/2r).

Thus, cyclic codes are highly effective in detecting burst errors, which are the
most common in real communication channels.

Qn13: Explain how cyclic codes detect:

1) Single-bit errors
2) Double-bit errors
3) Odd number of errors
4) Burst errors
ANS : Cyclic codes are a type of linear block codes with special algebraic properties. Error
detection is
based on polynomial division:
Transmitted codeword is divisible by the generator polynomial G(x).
At the receiver, if the received polynomial is not divisible by G(x), an error is
detected.
1. Single-Bit Errors
A single-bit error at position iii means the error polynomial is E(x)= xi.
For detection, E(x) must not be divisible by the generator polynomial G(x).
Since G(x) has at least two terms (degree ≥ 2 in practical CRCs), it cannot divide xi.
Hence cyclic codes can detect all single-bit errors.

2. Double-Bit Errors
A double-bit error at positions i and j has error polynomial:
E(x)=xi+xj
Detection depends on whether G(x) divides 1+xi−j
If G(x) does not divide this polynomial, the error is detected.

3. Odd Number of Errors

If the generator polynomial G(x) includes the factor (x+1), then it can detect all error
patterns with an odd number of bit errors.

4. Burst Errors
1. All burst errors with L <=r will be detected.
2. All burst errors with L = r + 1 will be detected with probability 1 - (1/2)r-1
3. All burst errors with L >r + 1 will be detected with probability 1- (1/2)r
Qn14: Explain the checksum technique with a numerical example
ANS : Checksum Technique:
The checksum is an error detection method used in networking (like TCP/IP).
Sender and receiver agree on a fixed word size.

The sender:
1. Divides the data into equal-sized words.
2. Adds them using 1’s complement arithmetic.
3. Takes the 1’s complement of the sum → this becomes the checksum.
4. Sends data + checksum.

The receiver:
1. Adds all words (including checksum).
2. If the result is all 1’s (no carry left), the data is accepted as error-free.
3. Otherwise, an error is detected.

Example:
Qn15: Explain Internet checksum algorithm with a numerical example
ANS : Internet Checksum Algorithm
The Internet checksum is used in TCP/IP (for IP, TCP, UDP headers) to detect
errors during transmission. It works on the principle of 1’s complement addition.

Algorithm (Sender side)

1. Divide the data into fixed-size words (usually 16 bits).
2. Add all the words using 1’s complement addition (wrap around any carry).
3. Take the 1’s complement of the sum → this becomes the checksum.
4. Send the data + checksum.

Algorithm (Receiver side)

1. Divide received data into the same word size.
2. Add all the words (including checksum) using 1’s complement addition.
3. If the result = all 1’s → No error.
4. If the result ≠ all 1’s → Error detected.

Example:
Qn16: What are Data Link Layer services? Explain framing, flow control, and error control
ANS : The Data Link Layer (DLL) is the second layer in the OSI model. Its main role is to
ensure reliable communication between directly connected nodes over a physical link.

Main Services of Data Link Layer

1. Framing
2. Flow Control.
3. Error Control
4. Access Control

1. Framing:
The physical layer only sees raw bits. The DLL groups these bits into [Link]
frame has a header and trailer that carry information such as addresses, error-check
bits, etc.
Techniques:
o Character Count
o Character Stuffing
o Bit Stuffing:
By these techniques Receiver can identify where one frame ends and another begins.

2. Flow Control
Ensures that the sender does not transmit faster than the receiver can process.
Techniques:
o Stop-and-Wait Protocol:
o Sliding Window Protocols (Go-Back-N, Selective Repeat
These techniques Prevents data loss due to buffer overflow.

3. Error Control
Transmission errors can occur due to noise. DLL provides mechanisms for error
detection and sometimes error correction.
Techniques:
o Error Detection:
 Parity Bit
 Checksums
 Cyclic Redundancy Check (CRC)
o Error Correction / Recovery:
 Automatic Repeat Request (ARQ) methods
 Stop-and-Wait ARQ: Retransmit if no ACK received.
 Go-Back-N ARQ: Retransmit from the erroneous frame onward.
 Selective Repeat ARQ: Retransmit only the erroneous frame.
These techniques Ensures reliable frame delivery across a noisy physical link.
Qn17: Explain fixed-size framing and variable-size framing.
ANS : Framing is the process of dividing a continuous stream of bits into smaller called
frames. There are two types of framing: Fixed-size framing and Variable-size
framing.
1. Fixed-Size Framing:
Each frame has a constant, predefined length. The receiver can easily separate
frames since size is already known. No need for start/stop flags or additional overhead.

Advantages
1. Simple and efficient to implement.
2. No extra bits for markers → less overhead.

Disadvantages
1. Wastes bandwidth if data does not fill the entire frame.
Example: ATM (Asynchronous Transfer Mode) uses fixed 53-byte cells.

2. Variable-Size Framing
Frames can have different lengths depending on the data size. Requires
methods to define start/end of frames:
o Character Count
o Character Stuffing
o Bit Stuffing

Advantages
1. Efficient use of bandwidth
2. Flexible, supports both small and large messages.

Disadvantages
 More complex implementation.
 Needs extra bits or special patterns to detect frame boundaries.

Qn18: Explain Character-Orented framing and Bit-Oriented framing.

ANS : Framing is the process of dividing a continuous stream of bits into smaller called
frames. so that the receiver can recognize where each frame begins and ends.
Two major approaches are: Character-oriented framing and Bit-oriented framing.

1. Character-Oriented Framing

In this method, data is divided into frames based on characters. A special

character (called a flag or delimiter) is used to mark the beginning and end of each
frame. If the same flag character appears in the data, an escape character (ESC) is
inserted before it → called character stuffing.
Advantages
 Simple and easy to implement when communication is character-based.
 Easy to detect frame boundaries.
Disadvantages
 Extra overhead due to stuffing.

2. Bit-Oriented Framing

In this method, data is divided into frames of arbitrary bit patterns, not tied to
characters. A special bit sequence (flag) marks the start and end of the frame.
Standard flag: 01111110 (used in HDLC).To prevent confusion, whenever five
consecutive 1’s occur in data, a 0 is stuffed (inserted). Receiver removes the extra 0 →
called bit stuffing.
Qn19: Explain byte stuffing and bit stuffing with examples.
ANS : In data communication, framing is required so that the receiver can identify the
start and end of a message. Two important techniques used for this are byte stuffing
and bit stuffing.
In byte stuffing, the frame is marked with a special flag byte at the beginning
and end. If this flag byte appears in the actual data, it can confuse the receiver. To
overcome this problem, the sender inserts a special escape byte (ESC) before every
flag byte or escape byte that occurs in the data field. At the receiver’s side, whenever
an ESC is encountered, it is removed, and the following byte is treated as normal data.
For example, if the flag is F and the data contains F or E, the sender adds an ESC
before them. This way, the receiver can clearly separate the data from the frame
boundaries.
In bit stuffing, the technique works at the bit level. Here, a special bit pattern,
usually 01111110, is used as the start and end flag of the frame. If the same pattern
occurs in the data, it may be mistaken for a frame boundary. To avoid this, whenever
the sender finds five consecutive 1’s in the data, it automatically inserts a 0 bit after
them. This ensures that the pattern 01111110 never appears in the middle of the data.
The receiver, on the other hand, removes the extra 0 bits after detecting five
consecutive 1’s. For example, a data sequence 11111 will be transmitted as 111110 to
prevent confusion with the flag.
Thus, byte stuffing is a character-oriented method that uses escape bytes,
while bit stuffing is a bit-oriented method that uses inserted 0’s. Both techniques are
essential to maintain proper frame boundaries and ensure that the data is transmitted
accurately without being mistaken for control information.
Qn20: Explain connectionless and connection-oriented protocols.
ANS : In computer networks, communication between two devices can take place in
two ways: connectionless and connection-oriented protocols.
In a connectionless protocol, data is sent without first establishing a dedicated
connection between the sender and the receiver. Each packet, also called a datagram,
is treated independently and carries full addressing information. Since there is no prior
setup, delivery is not guaranteed, and packets may arrive out of order or get lost. The
Internet Protocol (IP) is the best example of a connectionless protocol. It is fast and
efficient for small messages or real-time applications where speed is more important
than reliability.
In contrast, a connection-oriented protocol requires that a connection be
established between the sender and the receiver before data transfer begins. Once the
connection is set up, data is transmitted in sequence, and the protocol ensures
reliability, error checking, and flow control. The Transmission Control Protocol (TCP)
is a well-known example. In this method, the receiver acknowledges the receipt of
packets, and if packets are lost, they are retransmitted. This makes it more reliable but
slightly slower due to the overhead of connection setup and management.
Thus, connectionless protocols are suitable for applications like video
streaming, online gaming, or voice calls where speed is crucial, while connection-
oriented protocols are used in applications like file transfer, emails, and web browsing
where accuracy and reliability are more important. Together, both approaches serve
different needs of data communication in computer networks.

Qn- 21: Explain the working of Stop-and-Wait ARQ protocol with FSM diagrams.
ANS: The Stop-and-Wait ARQ (Automatic Repeat reQuest) protocol is one of the
simplest error control methods used in computer networks to ensure reliable data
transmission. In this protocol, the sender transmits one frame at a time and then stops
to wait for an acknowledgment (ACK) from the receiver. If the ACK is received
within a fixed time (timeout period), the sender proceeds to transmit the next frame. If
the ACK is not received, or if a negative acknowledgment (NAK) is received, the
 sender retransmits the same frame. This ensures that lost or corrupted frames are
correctly delivered.
At the receiver’s side, when a frame arrives, it checks for errors using error
detection methods such as CRC. If the frame is error-free, the receiver sends an ACK
and delivers the frame to the higher layer. If the frame is corrupted, the receiver
discards it and sends a NAK, asking the sender to retransmit. Since only one frame is
“in transit” at any time, the protocol is simple but not very efficient for long-distance
or high-speed networks due to idle waiting time.

Qn-22: Explain the working of Go-Back-N and Selective Repeat protocols

ANS: In the Go-Back-N ARQ protocol, the sender can transmit several frames (up to
a window size N) without waiting for an acknowledgment. The receiver, however, is
simple and only accepts frames in order. If a frame is lost or arrives with errors, the
receiver discards it and does not acknowledge it. As a result, when the sender’s timer
for that frame expires, it retransmits the lost frame along with all the subsequent
frames, even if some of them were correctly received earlier. For example, if frame 3
is lost, the sender will retransmit frames 3, 4, 5, and so on. This ensures reliability but
can lead to unnecessary retransmissions.
 The Selective Repeat ARQ protocol is a more efficient version. Here, both the
sender and receiver maintain a sliding window. The receiver can accept frames that
arrive out of order and store them in a buffer until the missing frames are correctly
received. The sender only retransmits those frames for which a negative
acknowledgment (NAK) or timeout occurs, instead of retransmitting the entire
sequence. For example, if frame 3 is lost but frames 4 and 5 are received correctly, the
receiver buffers 4 and 5, and the sender retransmits only frame 3. This reduces
redundant retransmissions but requires more complex logic and larger buffer space at
the receiver.

Qn-23: Explain the HDLC frame structure with field formats.

ANS: High-Level Data Link Control (HDLC) is a bit-oriented protocol used for
reliable communication over point-to-point and multipoint links. It organizes data into
frames and provides flow control, error detection, and error recovery. The basic
HDLC frame consists of six fields: Flag, Address, Control, Information, and
Frame Check Sequence (FCS), and Flag.

The Flag field is 8 bits long and has the unique bit pattern 01111110. It is
placed at both the beginning and the end of every frame to mark boundaries. To avoid
confusion when the same bit sequence appears in the data, the protocol uses bit
stuffing. The Address field is usually 8 bits and identifies the secondary station
(receiver) in unbalanced configurations or both stations in balanced configurations. In
some cases, the address field may be longer than one byte.
The Control field is also typically 8 bits and defines the type of frame being
sent. HDLC supports three types of frames: Information (I-frames) used to carry user
data, Supervisory (S-frames) used for error and flow control, and Unnumbered (U-
frames) used for control purposes such as link setup and termination. Depending on
the frame type, the control field contains sequence numbers, acknowledgment
numbers, or control commands.
The Information field is of variable length and carries the actual payload (user
data). It is present only in I-frames and certain U-frames. The Frame Check
Sequence (FCS) field is usually 16 bits or 32 bits and contains the result of a Cyclic
Redundancy Check (CRC) applied to the address, control, and information fields. It
 allows the receiver to detect errors in transmission. Finally, the closing Flag field
01111110 indicates the end of the frame.
Thus, the HDLC frame structure is highly reliable because it clearly defines
boundaries with flag sequences, identifies communicating stations with the address
field, supports control and sequencing through the control field, transmits user data in
the information field, and ensures error detection using the FCS field.

Qn-24: Explain types of HDLC frames: I-frame, S-frame, U-frame.

ANS: In HDLC (High-Level Data Link Control), communication is organized into

three types of frames:
1) Information frames (I-frames),
2) Supervisory frames (S-frames), and
3) Unnumbered frames (U-frames).

The Information frame (I-frame) is used to carry user data from the network
layer to the destination. Along with the data, it also carries control information such as
send sequence numbers and receive sequence numbers. These numbers are used for
error detection and flow control by acknowledging which frames have been received
correctly. I-frames form the backbone of HDLC communication since they transport
the actual payload.
The Supervisory frame (S-frame) is used only for control purposes,
particularly for error handling and flow control. It does not carry user data. Instead, it
contains functions like Receive Ready (RR) to indicate readiness to receive more
frames, Receive Not Ready (RNR) to pause the sender, Reject (REJ) to request
retransmission from a specific frame, and Selective Reject (SREJ) to ask for
retransmission of a particular erroneous frame. This helps manage smooth data
transfer and recovery from transmission errors.
The Unnumbered frame (U-frame) is used for link management and control
functions that are not related to data sequencing. These include activities like
establishing a connection, disconnecting a link, or exchanging control commands.
They may also carry system management information.
Qn-25: Explain the Point-to-Point Protocol (PPP) frame format & transition phases.

ANS: The Point-to-Point Protocol (PPP) is a data link layer protocol used to
establish direct communication between two nodes over serial links such as telephone
lines, ISDN, or dedicated connections. PPP provides framing, error detection,
authentication, and supports multiple network layer protocols like IP, IPX, and
AppleTalk.
The PPP frame format is similar to that of HDLC but simplified. Each frame
starts and ends with a Flag field (8 bits, 01111110) which marks boundaries. The
Address field (8 bits) is usually set to 11111111 since PPP is always point-to-point
and does not require unique addressing. The Control field (8 bits) is fixed to
00000011, meaning an unnumbered frame, as PPP does not use sequence numbers.
The Protocol field (16 bits) identifies which network layer protocol is being carried,
such as IP (0x0021) or LCP (0xC021). The Information field contains variable-length
user data, and finally, the Frame Check Sequence (FCS), either 16 or 32 bits,
provides error detection using CRC.
PPP also defines several transition phases in establishing and terminating a
link. The process begins with the Dead phase, where no connection exists. When a
physical connection is detected, it moves to the Establish phase, where the Link
Control Protocol (LCP) is used to configure and test the link. If authentication is
required, the Authenticate phase follows, where methods like PAP or CHAP verify
the identity of the user. Once authentication succeeds, the protocol enters the Network
phase, during which Network Control Protocols (NCPs) are used to configure
different network layer protocols. Finally, data transfer occurs in the Open phase, and
when communication ends, the link is terminated, returning to the Dead phase.

Qn-26: Explain random access protocols with examples.

ANS: Random access protocols are methods used in networks where stations can
transmit data whenever they have data, without reserving the channel. If two or more
stations transmit simultaneously, a collision occurs, and the affected stations
 retransmit after waiting for a random time interval. Examples include ALOHA (Pure
and Slotted), where Slotted ALOHA reduces collisions by dividing time into slots, and
CSMA (Carrier Sense Multiple Access), where a station listens to the channel before
transmitting. These protocols are simple, decentralized, and work efficiently when
network traffic is low to moderate, but collisions increase as traffic grows.

Qn-27: Explain random access protocols with examples.

ANS: Pure ALOHA is a random access protocol used in computer networks where a station
sends a frame whenever it has data to transmit, without checking if the channel is free.
If two frames collide (i.e., overlap in time), both are considered lost and must be
retransmitted after a random delay.
Working of Pure ALOHA:
1. A station transmits a frame immediately when it has data.
2. The frame may either be received correctly or collide with another frame.
3. If an acknowledgment (ACK) is not received within a certain time, the sender waits
for a random time and retransmits the frame.
4. Collisions are resolved by random retransmissions, making the protocol simple but
inefficient at high traffic.
Throughput Derivation:
 Let G = average number of frames generated per frame time
 A frame is successfully transmitted if no other frame is sent in the vulnerable period,
which for Pure ALOHA is 2 × frame time.
 The probability of no collision is:
Psuccess=e−2GP
 Throughput S is the rate of successful frames per frame time:
S=G×Psuccess
S=G×e−2G
The maximum throughput occurs when G=0.5
Smax=0.5×e−1 ≈ 0.184
This means at best, only about 18.4% of the channel capacity is used effectively.
Qn-28: Explain slotted ALOHA and derive its throughput
Ans: Slotted ALOHA is an improvement over Pure ALOHA that reduces collisions by dividing time into
discrete slots equal to the frame transmission time. A station is allowed to send a frame only at the
beginning of a time slot, which reduces the vulnerable period and increases efficiency.
Working of Slotted ALOHA (Step by Step):
1. Time is divided into slots of one frame duration.
2. A station transmits a frame at the start of a time slot.
3. If only one station transmits in a slot, the frame is successfully received.
4. If two or more stations transmit in the same slot, a collision occurs, and the frames are lost.
5. Collided frames are retransmitted after waiting for a random number of slots.
Throughput Derivation:
 Let G be the average number of frames generated per time slot.
 In Slotted ALOHA, a frame is successful if exactly one frame is transmitted in a slot.
 Probability of successful transmission in a slot:
Psuccess=G⋅e−GP
 Throughput SSS (successful frames per slot) is:
S=G⋅e−G
 Maximum throughput occurs when G=1
Smax=1⋅e−1≈0.368S
This means Slotted ALOHA can use about 36.8% of the channel effectively, which is double the
efficiency of Pure ALOHA.

Qn-29: Explain CSMA, CSMA/CD

ANS: Carrier Sense Multiple Access (CSMA) is a random access protocol used in
networks where multiple stations share a common communication channel. Before
transmitting, a station senses the channel to check if it is free. If the channel is idle,
the station sends its data; if the channel is busy, the station waits for a random time
before trying again. This reduces collisions compared to Pure ALOHA and Slotted
ALOHA.
There are different types of CSMA based on how collisions are handled:
1. Non-persistent CSMA: If the channel is busy, the station waits for a random time
before sensing again.
2. 1-persistent CSMA: The station continuously senses the channel and transmits
immediately once it becomes free, which may cause collisions if multiple stations are
waiting.
 3. p-persistent CSMA: Used in slotted channels; the station transmits with probability p
when the channel is free and waits for the next slot with probability 1-p.
CSMA with Collision Detection (CSMA/CD) is an enhancement of CSMA used
in Ethernet networks. Here, a station continues to monitor the channel while
transmitting. If it detects a collision, it immediately stops transmission and sends a jam
signal to inform all stations. The station then waits for a random backoff time before
attempting to retransmit. CSMA/CD greatly reduces wasted bandwidth caused by
collisions.

Qn-30: Explain persistent and non-persistent CSMA strategies.

ANS: Carrier Sense Multiple Access (CSMA) protocols help stations share a common
communication channel by sensing it before transmitting. The way a station behaves
when the channel is busy defines the persistence strategy.
1. 1-Persistent CSMA:
o The station continuously senses the channel.
o If the channel is idle, it transmits immediately.
o If the channel is busy, it keeps sensing until the channel becomes free.
o This method is aggressive and can lead to collisions if multiple stations are
waiting to transmit.
o It is simple and provides low delay under low traffic but higher collision
probability under high traffic.
2. Non-Persistent CSMA:
o The station senses the channel before transmitting.
o If the channel is idle, it transmits immediately.
o If the channel is busy, the station waits for a random time before checking the
channel again.
o This method is less aggressive and reduces the probability of collisions
compared to 1-persistent CSMA.
o It is slightly slower but more efficient under high traffic.
Qn-31: Write short notes on token passing in ring topology.
ANS: Token passing is a controlled access protocol used in ring topology
networks to regulate data transmission and avoid collisions. In this method, a special
frame called a token circulates continuously around the ring. Only the station that
possesses the token is allowed to transmit data, ensuring that only one station sends at
a time. After the station finishes transmitting, it releases the token so that the next
station in the ring can use it.
This method provides fair and orderly access to all stations, as each station
gets a chance to transmit in turn. It also eliminates collisions, which are common in
random access protocols like CSMA. Token passing is particularly suitable for
deterministic networks where predictable performance is important, such as in
industrial or real-time systems. Examples include the IBM Token Ring network and
FDDI (Fiber Distributed Data Interface).

Qn-32: Write a short notes on Reservation and Polling in ring topology.

Ans: Reservation:
In the reservation method, each station indicates its need to transmit by setting a
reservation bit in a control field of the circulating frame or token. Stations that
require transmission mark their bit, and when the token arrives at a station with a
reservation, it is allowed to transmit data. Once the data is sent, the token continues to
circulate. This method ensures fair and orderly access and is suitable for networks
with variable traffic, as stations transmit only when they have data to send.

Polling:
In the polling method, a central controller or master station sequentially
contacts each station on the ring to check if it has data to transmit. When a station is
polled, it sends its data if ready; otherwise, the controller moves to the next station.
Polling guarantees collision-free communication and is simple to implement, but it
introduces a small delay because each station must wait for its turn to be polled.