Computer Networks

(iv) 4

A code with minimum Hamming distance $d_{min}$ can detect up to $d_{min} - 1$ errors and correct up to $\lfloor (d_{min}-1)/2 \rfloor$ errors.

$$d_{min} - 1 = 5 - 1 = 4$$

Answer: (iii) Timeout occurs

The sender starts a timer after sending a frame. If no ACK arrives before the timer expires (frame or ACK lost/corrupted), it retransmits the same frame.

Answer: (i) Retransmit frame 5

In ARQ protocols, when the timer expires without an ACK, the sender assumes the frame (or its ACK) was lost and retransmits the same frame. It does not move on, discard earlier frames, or restart the connection.

Answer: (ii) CSMA/CA

CSMA (Carrier Sense Multiple Access) methods sense the channel before transmitting. CSMA/CA (used in Wi-Fi) listens first and tries to avoid collisions. ALOHA and Slotted ALOHA transmit without sensing, and token passing uses a token instead.

Answer: (iv) None of these

Hub, bridge and switch are all networking devices (physical layer, and data link layer devices respectively), so none of the options is the odd one out.

Given

• Message (dataword): 11001001
• Generator polynomial: $x^3 + 1 \Rightarrow$ divisor 1001 (degree 3, so append 3 zeros)

Step 1: Append zeros

11001001 + 000 = 11001001000

Step 2: Modulo-2 division by 1001

Step	Current bits	XOR with	Remainder
1	1100	1001	101
2	101+1 = 1011	1001	010
3	010+0 = 0100	0000	100
4	100+0 = 1000	1001	001
5	001+1 = 0011	0000	011
6	011+0 = 0110	0000	110
7	110+0 = 1100	1001	101
8	101+0 = 1010	1001	011

CRC (remainder) = 011

Check using polynomials: since $x^3 \equiv 1 \pmod{x^3+1}$, the message $x^7+x^6+x^3+1$ times $x^3$ gives $x^{10}+x^9+x^6+x^3 \equiv x + 1 + 1 + 1 = x + 1$, i.e. 011. ✔

Step 3: Transmitted message

Dataword + CRC = 11001001 | 011  ->  11001001011

Receiver check

Dividing 11001001011 by 1001 gives remainder 000, so no error is detected.

Principle of CRC

CRC is a polynomial-based error detection technique. The sender appends $r$ redundant bits (the CRC) to the dataword so that the resulting codeword is exactly divisible by a predetermined generator (divisor) using modulo-2 arithmetic (XOR, no carries). The receiver divides the received codeword by the same generator: remainder 0 means no error detected; nonzero means error.

Steps (sender):

1. Append $r$ zeros to the dataword ($r$ = degree of generator).
2. Divide by the generator using modulo-2 division.
3. Replace the appended zeros with the remainder; this is the codeword.

Given

• Dataword: 1101011011
• $G(x) = x^4 + x + 1 \Rightarrow$ divisor 10011 (degree 4, so append 4 zeros)
• Dividend: 1101011011 + 0000 = 11010110110000

Modulo-2 division

Step	Current bits	XOR with	Result (remainder)
1	11010	10011	01001 -> 1001
2	1001+1 = 10011	10011	00000 -> 0000
3	0000+1 = 00001	00000	0001
4	0001+0 = 00010	00000	0010
5	0010+1 = 00101	00000	0101
6	0101+1 = 01011	00000	1011
7	1011+0 = 10110	10011	00101 -> 0101
8	0101+0 = 01010	00000	1010
9	1010+0 = 10100	10011	00111 -> 0111
10	0111+0 = 01110	00000	1110

CRC (remainder) = 1110

Transmitted codeword

Dataword + CRC = 1101011011 | 1110  ->  11010110111110

Receiver verification (no bit altered)

The receiver divides 11010110111110 by 10011. Since the codeword equals dataword-with-zeros XOR remainder, the division leaves remainder 0000. A zero remainder means no error is detected and the dataword 1101011011 is accepted. If any bit flipped, the remainder would be nonzero (unless the error pattern is itself a multiple of $G(x)$), and the frame would be discarded.

Bluetooth

Bluetooth (IEEE 802.15.1) is a short-range wireless technology for connecting devices to form a Personal Area Network (PAN).

Features

• Operates in the 2.4 GHz ISM band
• Uses FHSS (frequency hopping, 1600 hops/s) to avoid interference
• Range about 10 m (Class 2), up to 100 m (Class 1)
• Low power and low cost

Architecture

• Piconet: one master and up to 7 active slaves
• Scatternet: multiple interconnected piconets
• Uses TDD with time slots of 625 microseconds

Applications

Wireless headsets, keyboards/mice, file transfer between phones, IoT devices and car hands-free systems.

Limitations

Short range, lower data rate than Wi-Fi, security concerns (pairing attacks).

Answer: (iii) The use of hamming codes

On a simplex link, signals travel in one direction only, so there is no return channel on which the receiver can send acknowledgements or NAKs. Any error-control scheme that depends on feedback is therefore impossible on such a link.

Hamming codes are forward error correction (FEC): the sender appends check (parity) bits, and the receiver uses them to detect and correct errors locally, entirely at the receiving end. No reverse path is needed, so Hamming coding is the only workable technique among the choices.

ARQ (ii) requires ACKs and retransmissions to flow back from receiver to sender - exactly what a simplex link cannot provide. BEC (backward error correction) and DEC (downward error correction) are not recognised error-control terms; the two real families are FEC and retransmission-based ARQ, so (i) and (iv) are distractors.

(ii) A bridge uses IP addresses while a router uses MAC addresses — this statement is NOT true (it has the roles reversed).

The correct relationship is the opposite: a bridge operates at the Data Link layer and forwards frames using MAC addresses; a router operates at the Network layer and forwards packets using IP addresses.

The other statements are all true: both devices selectively forward traffic (rather than broadcasting everything); a transparent bridge does build its forwarding table by inspecting (learning from) the source addresses of incoming frames; and a router, working at the Network layer, is capable of connecting a LAN to a WAN (crossing different network technologies), unlike a bridge which stays within the same LAN/broadcast domain type.

Hamming code is a forward error-correcting code that adds multiple parity bits to a data word, positioned at specific bit locations (powers of 2: 1, 2, 4, 8, ...), such that the pattern of which parity checks fail directly points to the exact bit position of a single-bit error — allowing the receiver not just to detect, but to locate and correct a single-bit error without retransmission.

Each parity bit covers a specific subset of data bit positions (determined by the binary representation of the position numbers). If an error occurs, the XOR of the failed parity checks gives the binary position number of the erroneous bit directly, which can then simply be flipped to correct it.

A Hamming code with r parity bits can correct 1-bit errors and detect 2-bit errors in a block of up to 2^r - 1 total bits (data + parity), provided 2^r - r - 1 >= (number of data bits).

Answer: (iii) flow control

A sliding window protocol lets the sender transmit several frames before an acknowledgement arrives, limited by the window size. The window slides forward as ACKs are received, so the sender never overwhelms the receiver. Its main role is flow control; it also supports error control when combined with ARQ (Go-Back-N, Selective Repeat).

(iv) Channel coding

The Data Link layer performs framing (organizing bits into frames), error control (detecting/correcting errors via checksums/CRC), and flow control (regulating transmission rate between sender and receiver).

Channel coding (adding redundancy to combat channel noise at the signal level, e.g. line coding schemes) is a Physical layer function, not a Data Link layer function — it deals with how bits are represented as signals, which is below the Data Link layer's scope.

Piggybacking is the technique of attaching ("riding along with") an acknowledgement to an outgoing data frame, instead of sending the ACK as a separate, standalone frame.

In a full-duplex or bidirectional connection, both sides are typically sending data to each other. Rather than wasting a whole frame just to carry an ACK, the ACK field is embedded within the header of the next data frame that station happens to be sending anyway, so a single frame carries both new data and the acknowledgement for previously received data.

Benefit: it reduces the number of frames transmitted (and hence the overhead) needed to keep both directions of communication flowing reliably.

Answer: (ii) A microwave link

IEEE 802.3 defines Ethernet over wired (guided) physical media only. The other three choices are all standard 802.3 media: thin coaxial cable for 10BASE2 (i), twisted pair for 10BASE-T, 100BASE-TX and 1000BASE-T (iii), and optical fibre for 10BASE-F and the 1000BASE-SX/LX variants (iv).

A microwave link (ii) is an unguided wireless medium. Wireless media belong to the IEEE 802.11 (Wi-Fi) family of standards, not to 802.3, so microwave cannot serve as an 802.3 Ethernet medium.

A switch is a Data Link layer networking device that connects multiple devices within a LAN and forwards frames selectively — only out the specific port leading to the destination MAC address — rather than broadcasting to every port like a hub does.

It builds and maintains a MAC address table by learning the source address and incoming port of every frame it sees, allowing it to make intelligent per-frame forwarding decisions. This reduces unnecessary traffic, eliminates collisions (each port is its own collision domain), and allows multiple simultaneous conversations on different port pairs at once (full-duplex operation).

When a station transmitting in CSMA/CD detects a collision, it doesn't just stop silently — it immediately sends a short jam signal (typically 32–48 bits) onto the channel.

Purpose of the jam signal:

1. To ensure that all other stations on the shared medium become aware that a collision has occurred, even those that may not have detected the collision themselves (e.g. due to their position on the cable).
2. This guarantees the collision lasts long enough to be reliably detected by every transmitting station involved, so none of them mistakenly believe their frame was sent successfully.
3. It prompts all colliding stations to stop transmitting and enter the random backoff (exponential backoff) phase before attempting retransmission, avoiding repeated immediate re-collision.

(iii) M + N

In a sliding window ARQ scheme with sender window size N and receiver window size M, the minimum number of distinct sequence numbers required is N + M.

Why: Sequence numbers must be large enough that the sender's window and the receiver's window can never simultaneously refer to overlapping sequence numbers in a way that causes ambiguity between old and new frames. If the total range of usable sequence numbers were smaller than N + M, it would become possible for a frame from a previous window cycle to be mistaken for a frame in the current cycle, since the sender's and receiver's windows could "wrap around" and overlap incorrectly.

This is a well-known general result (a classic GATE-style question) that applies to any generic sliding window ARQ with independent sender/receiver window sizes — note that this differs from the more commonly quoted Go-Back-N-specific rule (sequence numbers ≥ N+1) because that assumes a receiver window of size 1 (M=1), giving N+M = N+1, consistent with the general formula.

(ii) two times

In pure ALOHA, a station transmits a frame whenever it has data, with no coordination with other stations. A collision occurs if any other station starts transmitting within one frame-time before OR after this station's transmission begins.

         <-- Tfr -->|<-- Tfr -->|<-- Tfr -->
   ...---[frame X starts]------[frame X ends]---...
         ^                                  ^
   vulnerable window                 vulnerable window
   (1 frame-time before)             (1 frame-time after)

So the total vulnerable period = 1 frame-time (before) + 1 frame-time (after) = 2 x frame transmission time. This large vulnerable window is why pure ALOHA has a low maximum throughput (~18.4%), compared to slotted ALOHA's vulnerable time of just 1 frame-time (throughput ~36.8%).

(i) Media Access Control (MAC) sublayer

The Data Link layer is commonly split into two sublayers:

• LLC (Logical Link Control): medium-independent — handles flow control, error control, and framing in a way that's the same regardless of the underlying physical medium (Ethernet, Wi-Fi, etc.).
• MAC (Media Access Control): medium-dependent — handles the specific rules for accessing the shared physical medium, which vary by technology (e.g. CSMA/CD for Ethernet, CSMA/CA for Wi-Fi). It also handles physical/MAC addressing.

Since the MAC sublayer's functions specifically depend on the type of medium in use, it is the correct answer.

Dividing a large Ethernet LAN into smaller segments using a bridge offers several advantages:

1. Smaller collision domains — each segment becomes its own collision domain, so collisions on one segment don't affect stations on another, improving overall performance.
2. Reduced traffic congestion — the bridge forwards a frame to the other segment only if the destination actually lies there, filtering out traffic that doesn't need to cross, keeping local traffic local.
3. Increased total bandwidth — since each segment operates somewhat independently, the aggregate usable bandwidth across the whole LAN increases compared to one large shared segment.
4. Fault isolation — a problem (e.g. excessive collisions, a faulty NIC) on one segment is contained and doesn't necessarily degrade the entire network.
5. Extended physical distance/size — bridging lets a LAN span a larger physical area or more stations than a single segment's physical/electrical limits would allow, since it regenerates/forwards frames rather than just repeating raw signal.

A bridge is a Data Link layer device that connects two or more LAN segments and forwards frames between them selectively, based on the destination MAC address — rather than blindly repeating everything (like a hub/repeater) or routing based on IP (like a router).

Key roles:

1. Filtering — examines each frame's destination MAC address and forwards it only to the segment where that address actually resides, keeping traffic local to its own segment when the destination is nearby.
2. Learning — builds a forwarding/MAC address table automatically by observing the source addresses of incoming frames, associating each address with the port it arrived on.
3. Segmenting collision domains — by splitting one large shared LAN into smaller segments, it reduces collisions and increases effective usable bandwidth.
4. Extending the LAN — links physically separate LAN segments (possibly using different media) into a single logical network, transparently to the higher layers.

CSMA/CD exists specifically to detect and handle collisions that occur when two stations transmit simultaneously on a shared (half-duplex) medium.

In a full-duplex switched Ethernet, each device has a dedicated, point-to-point link to the switch, with separate physical send and receive paths (e.g. separate wire pairs). Because:

1. Each link is used by only one device (not shared among multiple stations), collisions between different devices cannot occur on that link.
2. Since the send and receive channels are physically separate, a device can transmit and receive at the same time without its own outgoing signal interfering with incoming data.

Since the fundamental precondition for a collision (multiple stations contending for the same shared channel at the same time) simply doesn't exist in this topology, CSMA/CD's collision detection and backoff mechanism becomes unnecessary and is disabled in full-duplex mode.

(ii) 2^(n-1)

For Selective Repeat with n-bit sequence numbers (giving 2^n distinct sequence numbers in total), the maximum window size is limited to half of the total sequence number space: 2^(n-1).

Why it must be half (not 2^n − 1 like Go-Back-N): Selective Repeat receivers must distinguish between a retransmitted OLD frame and a NEW frame carrying the same sequence number (after wraparound). If sender and receiver windows were each allowed to be larger than half the sequence space, their windows could overlap in a way that makes an old, already-received frame indistinguishable from a new one with the same sequence number — causing the receiver to accept a duplicate as if it were new data. Capping both windows at 2^(n-1) guarantees the sender's and receiver's windows never overlap incorrectly.

(iii) 16

Since Go-Back-N is used, whenever a packet is lost, every packet sent after it in that window also has to be resent (even if those later packets were themselves successfully transmitted), because the receiver discards any out-of-order arrival and only cumulatively acknowledges up to the last correctly received in-order packet.

Tracking every transmission A makes (numbering them 1st, 2nd, 3rd... in the order sent, including retransmissions), and marking every 5th one as lost:

Phase 1 (initial send, window=3):
  Send: 1, 2, 3, 4, 5(LOST— 5th transmission), 6, 7
  -> 7 transmissions so far. Timeout on packet 5.

Phase 2 (go back to 5, resend + continue):
  Send: 5, 6, 7(LOST — 10th transmission overall), 8, 9
  -> 5 more transmissions (total 12). Timeout on packet 7.

Phase 3 (go back to 7, resend + continue):
  Send: 7, 8, 9(LOST — 15th transmission overall)
  -> 3 more transmissions (total 15). Timeout on packet 9.

Phase 4 (go back to 9, resend):
  Send: 9 — succeeds (16th transmission, not a multiple of 5)
  -> 1 more transmission (total 16). All 9 packets now delivered.

Total transmissions = 7 + 5 + 3 + 1 = 16

Notice the pattern: each time, the packet landing on a multiple of 5 (5th, 10th, 15th transmission) is exactly the one lost, forcing a fresh Go-Back-N retransmission cycle from that point.

(iii) Both CSMA/CD and CSMA/CA

Both are multiple access protocols in the "random access with carrier sense" family, used to control which station gets to use a shared channel at a given moment:

• CSMA/CD (Collision Detection) — used in traditional (shared-medium) Ethernet; detects collisions after they occur and stops transmission early.
• CSMA/CA (Collision Avoidance) — used in Wi-Fi (802.11); since wireless collisions are hard to detect, it proactively tries to avoid them (via random backoff and optional RTS/CTS handshaking).

HDLC (High-Level Data Link Control) is not a multiple access protocol at all — it's a bit-oriented, point-to-point/point-to-multipoint data link protocol for framing and reliable transfer, unrelated to shared-channel access control.

Redundancy means sending extra bits along with the actual data — bits that are mathematically derived from the data itself (e.g. parity bits, checksum, CRC remainder) but carry no new information on their own.

How it enables error detection:

1. The sender computes these redundant bits from the original data using an agreed-upon algorithm (e.g. XOR-based parity, polynomial division for CRC) and appends them to the message before transmission.
2. The receiver, upon receiving the message, independently recomputes the same redundant bits from the received data using the identical algorithm.
3. It then compares its freshly computed redundant bits against the redundant bits that were actually received (sent by the sender).
4. If they match, the data is assumed to have arrived without errors (the check is consistent). If they don't match, it means the data was altered in transit — an error is detected.

The key idea: since the redundant bits are a deterministic function of the correct data, any change to the data bits during transmission (that isn't precisely compensated for) will very likely cause a mismatch, revealing the presence of an error without needing to know the original data independently.

A byte-oriented protocol treats the frame being transmitted as a sequence of bytes (characters) rather than as a raw stream of individual bits. Framing and control information are defined in terms of whole bytes — e.g. special reserved control bytes (like flag or escape bytes) mark the start/end of a frame, and byte-stuffing is used to escape any byte pattern within the data that would otherwise be misinterpreted as a control byte.

Examples: PPP (Point-to-Point Protocol), older protocols like BISYNC (Binary Synchronous Communication).

This contrasts with bit-oriented protocols (e.g. HDLC), which treat the frame as a raw sequence of bits and use bit-stuffing (inserting a single extra bit) to prevent a specific bit pattern from appearing accidentally within the data.

(ii) 11001001011

The generator polynomial x^3 + 1 corresponds to the bit pattern 1001 (degree 3 → 4-bit divisor, coefficients of x^3,x^2,x^1,x^0 = 1,0,0,1). The number of CRC bits to append = degree of generator = 3 bits.

Step 1: Append 3 zero bits to the message: 11001001 → 11001001000

Step 2: Divide this by the generator 1001 using XOR (mod-2 division), tracking the remainder:

11001001000  ÷  1001  (mod-2 division)

1100  XOR 1001 = 0101
bring down 1 → 1011  XOR 1001 = 0010
bring down 0 → 0100  (leading 0, no XOR)
bring down 0 → 1000  XOR 1001 = 0001
bring down 1 → 0011  (leading 0, no XOR)
bring down 0 → 0110  (leading 0, no XOR)
bring down 0 → 1100  XOR 1001 = 0101
bring down 0 → 1010  XOR 1001 = 0011

Remainder (last 3 bits) = 011

Step 3: Replace the appended zeros with this remainder:

Transmitted message = 11001001 + 011 = 11001001011

This matches option (ii).

Answer: (iii) Token ring

IEEE 802.5 defines the Token Ring LAN. A special frame called a token circulates around the ring, and only the station holding the token may transmit. This gives collision-free, deterministic access.

CSMA/CD belongs to IEEE 802.3 (Ethernet) and token bus to IEEE 802.4.

The sliding window protocol at the Data Link layer allows a sender to transmit multiple frames before requiring an acknowledgement for each one, improving throughput compared to stop-and-wait, while still providing flow control.

How it works

1. Both sender and receiver maintain a window — a range of sequence numbers currently valid for sending (sender's window) or accepting (receiver's window).

Sender's window (size N):

  [sent & ACKed] [sent, unACKed] [can send now] [cannot send yet]
       ...         S1  S2  S3          -            -
                   <----- window (size N) ----->

2. The sender can transmit any frame whose sequence number falls within its current window without waiting for an individual ACK — up to N outstanding (unacknowledged) frames at once.

3. As the receiver correctly receives frames, it sends back ACKs (either individually or cumulatively, depending on the variant — Go-Back-N uses cumulative ACKs, Selective Repeat uses individual ACKs).

4. Each time the sender receives an ACK for the oldest outstanding frame (the left edge of its window), the window "slides" forward by one (or more) positions, freeing up room to send new frames.

5. If a frame is lost or corrupted (detected via timeout or NACK), depending on the variant:

   • Go-Back-N: the sender resends the lost frame and every frame sent after it (since the receiver discards out-of-order frames).
   • Selective Repeat: only the specific lost frame is resent, since the receiver buffers out-of-order frames until the gap is filled.

6. The receiver's window similarly defines which sequence numbers it's currently willing to accept; for Go-Back-N the receiver window size is 1 (strict in-order only), while for Selective Repeat it matches the sender's window size to allow buffering.

Purpose: by keeping multiple frames "in flight" at once (pipelining), the sliding window protocol keeps the transmission link busy instead of idling while waiting for each individual ACK's round-trip time, significantly improving throughput on high-bandwidth or long-delay links.

CRC for data 1010011110 with divisor 1011

Given: data = 1010011110 (10 bits), divisor (generator) = 1011 (4 bits, i.e. x³ + x + 1).

Step 1: append zeros

The divisor has 4 bits, so append 3 zeros (divisor length − 1):

Dividend = 1010011110 + 000 = 1010011110000 (13 bits)

Step 2: modulo-2 (XOR) division

Step	Working bits	Action	XOR result	Remainder (3 bits)
1	1010	1010 ⊕ 1011	0001	001
2	0010 (bring down 0)	leading 0, ⊕ 0000	0010	010
3	0101 (bring down 1)	leading 0, ⊕ 0000	0101	101
4	1011 (bring down 1)	1011 ⊕ 1011	0000	000
5	0001 (bring down 1)	leading 0	0001	001
6	0011 (bring down 1)	leading 0	0011	011
7	0110 (bring down 0)	leading 0	0110	110
8	1100 (bring down 0)	1100 ⊕ 1011	0111	111
9	1110 (bring down 0)	1110 ⊕ 1011	0101	101
10	1010 (bring down 0)	1010 ⊕ 1011	0001	001

Remainder = 001, so the CRC = 001.

Step 3: transmitted codeword

Data + CRC = 1010011110 001 = 1010011110001

Step 4: check at the receiver

Divide the received word 1010011110001 by 1011. The steps are identical up to step 9 (remainder 101). In step 10 the last bit is now 1:

• Step 10: bring down 1 → 1011 ⊕ 1011 = 0000 → remainder 000

The remainder is zero, so no error is detected and the answer is verified.

(Quotient = 1001000111. If a bit were flipped in transit the remainder would be non-zero.)

Random access protocols are a category of multiple access (MAC sublayer) protocols in which no station has a scheduled turn or fixed priority — any station with data ready may attempt to transmit at any time, without needing permission or a pre-assigned time slot. Because multiple stations can attempt to transmit simultaneously, collisions are possible, and the protocol must define rules for how stations detect, handle, and recover from them (e.g. random backoff before retrying). Examples include ALOHA, CSMA, CSMA/CD, and CSMA/CA.

Pure ALOHA vs Slotted ALOHA

Aspect	Pure ALOHA	Slotted ALOHA
Transmission timing	A station transmits immediately whenever it has data ready, with no synchronization	Time is divided into fixed-length slots (= 1 frame transmission time); a station may only begin transmitting at the start of a slot
Vulnerable time	2 x frame transmission time (a collision can occur if any other station starts within one frame-time before or after)	1 x frame transmission time (since all stations are synchronized to slot boundaries, overlaps can only happen if two stations pick the same slot)
Maximum throughput	~18.4% (S = G x e^(-2G), max at G=0.5)	~36.8% (S = G x e^(-G), max at G=1), exactly double pure ALOHA
Synchronization needed	No	Yes — requires a global clock/synchronization mechanism among all stations
Delay at low load	Lower (no waiting for slot boundary)	Slightly higher (must wait for next slot start)

By halving the vulnerable time, slotted ALOHA significantly reduces the collision probability at any given load, roughly doubling the maximum achievable throughput compared to pure ALOHA — at the cost of requiring all stations to be time-synchronized.

Go-Back-N Sliding Window Protocol

Definition. Go-Back-N (GBN) is an ARQ sliding-window protocol in which the sender may keep up to N unacknowledged frames in flight, while the receiver accepts only in-order frames (its window size is 1). Whenever an error or a timeout is detected, the sender goes back N: it retransmits the damaged/lost frame and every frame sent after it, even those the receiver had already accepted correctly.

Operating parameters

• Sequence numbers are taken from 0 to $2^m - 1$ with m bits and used modulo $2^m$.
• The sender window must satisfy N less than or equal to $2^m - 1$; otherwise the receiver could not tell a new frame from an old duplicate.
• Receiver window = 1, so an out-of-order frame is never buffered.
• Ideal utilisation on an error-free link: $U = N / (1 + 2a)$, where $a = T_{prop} / T_{trans}$ (capped at 1).

Sender operation

1. Maintain a window over frames that have been sent but not yet acknowledged, plus a timer for the oldest unacknowledged frame.
2. Transmit the next frame whenever the window has a free slot - this gives flow control: when N frames are outstanding the sender must stop.
3. Accept a cumulative ACK: an acknowledgement for frame k means k and everything before it arrived correctly. Slide the window forward past k and restart the timer.
4. On timeout of the oldest unacknowledged frame, retransmit that frame and all later frames still in the window (the go-back-N step), then restart the timer.
5. Duplicate or stale ACKs for frames already acknowledged are ignored.

Receiver operation

1. Expect exactly one sequence number at a time; deliver it to the network layer only if it is the expected one and the FCS/checksum is valid.
2. Send an ACK for each correctly received in-order frame.
3. If a frame arrives out of order or corrupted, discard it (no reordering buffer) and re-acknowledge the last correctly received in-order frame. That duplicate ACK tells the sender nothing was delivered beyond that point, so recovery rests on the sender's timer.

Example of operation (N = 4)

 Sender  window [ 0 ][ 1 ][ 2 ][ 3 ]      transmits 0,1,2,3
   |
   |---- F0 ---->|                         OK   -> ACK 0
   |---- F1 ---->|                         OK   -> ACK 1
   |---- F2 --X--|                         LOST
   |---- F3 ---->|                         arrives out of order -> discarded, ACK 1
   |
   |  timer for F0/F2 expires -> GO BACK N
   |---- F2 ---->|                         OK   -> ACK 2
   |---- F3 ---->|                         OK   -> ACK 3
   |
   window now slides:      [ 4 ][ 5 ][ 6 ][ 7 ]

Note that F3 was received correctly the first time yet had to be sent again - this wasted bandwidth is the main drawback of GBN.

Efficiency (worked example)

Formula: $U = N / (1 + 2a)$, with $a = T_{prop} / T_{trans}$.

• Take N = 4 frames and propagation time = 2 transmission times, so a = 2.
• $U = 4 / (1 + 2 \times 2) = 4 / 5 = 0.8$
• Channel utilisation = 80 %. Compare stop-and-wait (N = 1): $U = 1 / 5 = 0.2$, only 20 %. GBN therefore gives about 4 times the throughput of stop-and-wait for the same link.

Merits, demerits and comparison with Selective Repeat

	Go-Back-N	Selective Repeat
Receiver window	1 (no buffering)	N (buffers out-of-order frames)
On error	Retransmits the lost frame and all later frames	Retransmits only the lost/corrupt frames
Receiver complexity	Very low	Higher (reorder buffer)
Bandwidth efficiency	Lower on error-prone links	Higher
Maximum window	$2^m - 1$	$2^{m-1}$

GBN is simple and cheap to implement at the receiver, which is why it is used in many data-link protocols; its weakness is that a single loss forces retransmission of a whole window of already-correct frames.

Pure ALOHA has less delay than Slotted ALOHA at low load.

Reasoning:

In pure ALOHA, a station transmits a frame the instant it becomes ready, with no waiting for any external timing signal.

In slotted ALOHA, time is divided into discrete slots (equal to one frame transmission time), and a station must wait until the start of the next slot boundary before it's allowed to transmit — even if the frame was ready earlier.

At low load, collisions are rare in both schemes (few stations contending), so the throughput/success-rate difference between the two barely matters. What dominates delay at low load is simply how long a station has to wait before it's permitted to send:

• Pure ALOHA: transmits immediately upon readiness — zero extra waiting time.
• Slotted ALOHA: must wait, on average, half a slot time (frame transmission time) for the next slot boundary to arrive, even when there's no contention at all.

So at low load, pure ALOHA's average access delay is lower simply because it doesn't impose the slot-alignment waiting overhead that slotted ALOHA requires — the throughput advantage of slotted ALOHA (from fewer collisions) only becomes the dominant factor at higher loads, where collision avoidance matters more than the small alignment delay.

Go-Back-N ARQ is a sliding-window protocol used for error and flow control, where a sender can transmit multiple frames before needing an acknowledgment — up to a window size N — but the receiver only accepts frames in strict order.

How it works

• The sender maintains a window of size N, allowing up to N unacknowledged frames to be in transit at once.
• Frames are numbered using sequence numbers modulo 2^m (m = bits used for numbering), and the window size must satisfy N <= 2^m - 1.
• The receiver uses a single variable to track the next expected frame. It discards any out-of-order frame — even if it arrived correctly — and re-sends an ACK for the last correctly received in-order frame (cumulative ACK).
• If the sender's timer for the oldest unacknowledged frame expires, it retransmits every frame from that point onward — not just the lost one. This is the "go back N" behavior.

Example

Sender window (N=4): frames 0,1,2,3 sent
Frame 1 is lost in transit
Receiver gets: 0 (accept, ACK1) -> 2 (discard, out of order) -> 3 (discard, out of order)
Sender's timer for frame 1 expires -> resends frames 1,2,3

Trade-off

Go-Back-N is simple to implement (receiver needs no buffering for out-of-order frames) but wastes bandwidth on retransmission, since even correctly-received frames after a lost one get discarded and re-sent. This is what Selective Repeat improves on, at the cost of a more complex receiver.

For pure ALOHA, throughput is given by:

S = G x e^(-2G)

where G is the offered load (average number of frames generated per frame-transmission-time).

Step 1: Frame transmission time

Frame size = 200 bits
Bandwidth  = 200 kbps = 200,000 bits/sec

Tfr = Frame size / Bandwidth = 200 / 200,000 = 0.001 sec = 1 ms

Case (i): 1000 frames/sec

G = (frames/sec) x Tfr = 1000 x 0.001 = 1

S = G x e^(-2G) = 1 x e^(-2) = 1 x 0.1353 = 0.1353  (13.53%)

Throughput = S x (frames/sec) = 0.1353 x 1000 ≈ 135 frames/sec successfully delivered

Case (ii): 500 frames/sec

G = 500 x 0.001 = 0.5

S = G x e^(-2G) = 0.5 x e^(-1) = 0.5 x 0.3679 = 0.1839  (18.39%)

Throughput = 0.1839 x 1000 ≈ 184 frames/sec successfully delivered

Observation: G = 0.5 gives the maximum possible throughput for pure ALOHA (~18.4%), which is exactly what case (ii) hits. Case (i)'s higher offered load (G=1) actually results in a lower successful throughput (13.53%) than case (ii), because more collisions occur as load increases beyond the optimal point — illustrating pure ALOHA's low ceiling on maximum achievable throughput.

Byte-oriented vs Bit-oriented protocols

Aspect	Byte-oriented protocol	Bit-oriented protocol
Unit of framing	Treats the frame as a sequence of bytes/characters	Treats the frame as a raw sequence of individual bits
Delimiters	Uses special reserved control bytes (e.g. flag byte, escape byte) to mark frame boundaries	Uses a specific bit pattern (e.g. 01111110) as the flag to mark frame boundaries
Data transparency technique	Byte stuffing	Bit stuffing
Examples	PPP, BISYNC	HDLC, SDLC
Overhead granularity	Overhead added/removed at byte level	Overhead added/removed at bit level, more flexible/fine-grained

Byte-stuffing vs Bit-stuffing

Aspect	Byte-stuffing	Bit-stuffing
What it protects against	Accidental occurrence of the flag byte (e.g. specific 8-bit pattern) inside the actual data payload	Accidental occurrence of the flag bit pattern (e.g. six consecutive 1s: 011111 10) inside the actual data payload
Mechanism	Whenever the flag byte (or the designated ESC byte itself) appears in the data, an extra ESC (escape) byte is inserted immediately before it. The receiver removes any ESC byte it finds and treats the following byte as literal data.	Whenever five consecutive 1s appear in the data, the sender inserts an extra 0 immediately after them. The receiver, upon seeing five consecutive 1s followed by a 0, removes that inserted 0.
Example	Data containing byte 01111110 (same as flag) → sender inserts ESC before it: ESC 01111110	Data 011111 1 (contains five 1s in a row) → sender inserts a 0: 0111110 1
Granularity	Operates at byte level (coarser)	Operates at bit level (finer, more precise, no wasted stuffing when only a few bits match)
Used with	Byte-oriented protocols	Bit-oriented protocols

In essence, both techniques serve the same purpose — preventing an accidental appearance of the frame delimiter pattern from being mistaken for an actual frame boundary — but operate at different granularities matching their respective protocol style.

Topology: Source S and Destination D are connected via two intermediate routers R1 and R2:

  S ---- R1 ---- R2 ---- D

There are 3 links (hops) total: S-R1, R1-R2, R2-D.

Layer visit count

Data Link Layer — visited once per link/hop the packet crosses, because a new frame (with fresh MAC addressing) must be created for each physical link:

S -> R1 : 1 visit (frame created at S, processed at R1)
R1 -> R2: 1 visit (new frame created at R1, processed at R2)
R2 -> D : 1 visit (new frame created at R2, processed at D)

Total Data Link layer visits = 3 (once per link)

Network Layer — visited once at each node the packet passes through (source, every intermediate router, and destination), since routing/forwarding decisions (or final delivery) happen at the Network layer at every node:

At S : Network layer processes the packet once (originates it)
At R1: Network layer processes it once (routing decision)
At R2: Network layer processes it once (routing decision)
At D : Network layer processes it once (final delivery, passed up to Transport layer)

Total Network layer visits = 4 (once per node: S, R1, R2, D)

Summary: For a path with k intermediate routers (here k=2), a packet visits the Network layer (k+2) times (source + k routers + destination) and the Data Link layer (k+1) times (once per link). Here: Network layer = 4 times, Data Link layer = 3 times.

CRC for message 101001101101 with G(x) = x⁵ + x⁴ + x² + 1

Message: 1010011011 01 = 101001101101 (12 bits)

Generator: x⁵ + x⁴ + x² + 1 → coefficients of x⁵ x⁴ x³ x² x¹ x⁰ = 1 1 0 1 0 1 → 110101 (6 bits, degree 5)

Step 1: append 5 zeros (degree of G)

Dividend = 101001101101 + 00000 = 10100110110100000 (17 bits)

Step 2: modulo-2 division by 110101

Step	Working bits	XOR with	Result	Remainder (5 bits)
1	101001	110101	011100	11100
2	111001 (bring 1)	110101	001100	01100
3	011000 (bring 0)	000000	011000	11000
4	110001 (bring 1)	110101	000100	00100
5	001001 (bring 1)	000000	001001	01001
6	010010 (bring 0)	000000	010010	10010
7	100101 (bring 1)	110101	010000	10000
8	100000 (bring 0)	110101	010101	10101
9	101010 (bring 0)	110101	011111	11111
10	111110 (bring 0)	110101	001011	01011
11	010110 (bring 0)	000000	010110	10110
12	101100 (bring 0)	110101	011001	11001

Remainder = 11001, so the CRC = 11001.

Step 3: transmitted frame

Message + CRC = 101001101101 11001 = 10100110110111001

Step 4: verification at the receiver

Divide 10100110110111001 by 110101. Steps 1–7 are the same (remainder 10000), then:

Step	Working bits	XOR with	Remainder
8	100001 (bring 1)	110101	10100
9	101001 (bring 1)	110101	11100
10	111000 (bring 0)	110101	01101
11	011010 (bring 0)	000000	11010
12	110101 (bring 1)	110101	00000

The remainder is zero, so the frame is accepted as error-free.

Pure ALOHA

In pure ALOHA, a station transmits a frame the moment it has one ready, without checking whether the channel is idle or coordinating with other stations in any way. If two stations' transmissions overlap in time even partially, both frames are destroyed (collision), and each station must wait a random backoff time before retrying.

• Vulnerable time = 2 x Tfr (frame transmission time), since a collision can happen if any other station starts within one frame-time before or after this station's own transmission begins.
• Maximum throughput ≈ 18.4% (at G = 0.5), where G is the offered load.

Example: Station A sends a frame at t=5ms. If Station B starts transmitting anytime between t=4ms and t=6ms (assuming Tfr=1ms), both frames collide and are lost.

Slotted ALOHA

Slotted ALOHA improves on pure ALOHA by dividing time into discrete slots, each exactly equal to one frame transmission time. A station is only permitted to begin transmission at the start of a slot — it must wait if its data becomes ready mid-slot.

• Vulnerable time = 1 x Tfr, since collisions can now only occur if two stations pick the exact same slot (partial overlaps across slot boundaries are eliminated by the synchronization).
• Maximum throughput ≈ 36.8% (at G = 1) — exactly double pure ALOHA's maximum.

Example: With 1ms slots, if Station A transmits in the slot starting at t=5ms, a collision only occurs if Station B also chooses to transmit in that same [5ms, 6ms) slot; B cannot start mid-slot at, say, t=5.5ms.

Key contrast

Aspect	Pure ALOHA	Slotted ALOHA
Transmission timing	Immediate, unsynchronized	Must align to slot boundaries
Vulnerable time	2 x Tfr	1 x Tfr
Max throughput	~18.4%	~36.8%
Needs global clock sync	No	Yes

Halving the vulnerable window by requiring slot-synchronized transmission is what allows slotted ALOHA to double pure ALOHA's maximum achievable throughput, at the cost of needing all stations to share a common time reference.

Stop-and-Wait ARQ requires the sender to transmit exactly one frame, then wait idle until an ACK for that frame arrives before sending the next one. This is simple but very inefficient on links with significant propagation delay or high bandwidth, motivating the move to Go-Back-N:

1. Poor channel utilization on high-delay/high-bandwidth links — the sender sits idle for the entire round-trip time (RTT) after every single frame, even though the link is physically capable of carrying much more data during that idle period. On a long-distance or high-speed link, this wasted idle time can dominate total transfer time, driving utilization down toward zero as bandwidth-delay product grows.

2. Underutilizes available bandwidth — since only one frame is ever "in flight" at a time, the link's full capacity is never actually exploited; a link capable of carrying many frames simultaneously is used as if it could only carry one.

3. Throughput doesn't scale with bandwidth — simply upgrading to a faster link doesn't meaningfully improve throughput under Stop-and-Wait, since the RTT-bound idle time remains the dominant factor, not the transmission time itself.

Go-Back-N's fix: by introducing a sliding window that allows multiple frames (up to window size N) to be transmitted and outstanding (unacknowledged) simultaneously, the sender can keep pushing new frames onto the link while still waiting for earlier ACKs, keeping the pipe continuously full instead of idling after each frame. This dramatically improves throughput on links where the bandwidth-delay product is large, at the modest cost of needing sequence numbers, a window mechanism, and (in the event of a lost frame) potentially retransmitting more than the single lost frame.

ALOHA: throughput and delay

Notation: T = frame time, G = average number of frame transmissions per frame time (offered load, including retransmissions), S = throughput (successful frames per frame time). Frame arrivals are assumed to follow a Poisson process.

1. Pure ALOHA

Stations transmit whenever they have data. A frame sent at time t₀ is successful only if no other frame starts in the vulnerable period [t₀ − T, t₀ + T], which is 2T long.

• Probability of no other transmission in 2T: P₀ = e^(−2G)
• Throughput: S = G · e^(−2G)
• Maximum: dS/dG = 0 gives G = 0.5, so S_max = 1/(2e) ≈ 0.184 (18.4%)

Delay: the probability of a frame succeeding on one try is e^(−2G), so the average number of transmissions per frame is e^(2G), i.e. e^(2G) − 1 retransmissions. If each failed attempt costs one frame time plus propagation time Tₚ plus an average back-off time B:

D_pure ≈ T + Tₚ + (e^(2G) − 1)(T + Tₚ + B)

Delay grows exponentially with load G.

2. Slotted ALOHA

Time is divided into slots of length T. A station may start transmission only at the beginning of a slot. Two frames either collide completely or do not collide at all. The vulnerable period shrinks to T.

• Probability of no other transmission in one slot: P₀ = e^(−G)
• Throughput: S = G · e^(−G)
• Maximum: G = 1, so S_max = 1/e ≈ 0.368 (36.8%)

Delay: average transmissions per frame = e^G, so retransmissions = e^G − 1. A frame also waits on average T/2 for the next slot boundary:

D_slotted ≈ T/2 + T + Tₚ + (e^G − 1)(T + Tₚ + B)

Comparison

Basis	Pure ALOHA	Slotted ALOHA
Time	Continuous	Discrete slots
Synchronisation	Not required	Required (common clock)
Vulnerable period	2T	T
Throughput	S = G·e^(−2G)	S = G·e^(−G)
Maximum throughput	0.184 at G = 0.5	0.368 at G = 1
Collision probability	Higher (partial overlaps possible)	Lower (only full overlaps)
Delay at high load	Grows as e^(2G)	Grows as e^G; lower
Delay at very low load	Lower (send immediately)	Slightly higher (wait for slot start)
Complexity	Simple	Needs slot synchronisation

Conclusion: slotted ALOHA doubles the maximum throughput of pure ALOHA and has much better delay under load, at the cost of clock synchronisation.