Data Networks Midterm

OSI Model Layers

Application, Presentation, Session, Transport, Network, Data Link, Physical.

Connection-Oriented vs Connectionless

Connection-oriented requires setup, data transfer, and teardown; connectionless sends data without setup.

Encapsulation

Each layer adds its own header to data from the upper layer before transmission.

Frames vs Packets

Frames encapsulate packets at the data link layer, including headers and trailers.

Fraction of Bandwidth Used for Headers

Given n layers with header size h and message M, fraction = nh / (nh + M).

Purpose of Modulation

Convert digital data into analog form suitable for transmission over analog media.

Amplitude Modulation

Signal amplitude varies with the carrier, while frequency and phase remain constant.

Frequency Modulation

Carrier frequency varies with the input signal amplitude.

Phase Modulation

Carrier phase varies with the input signal amplitude.

QPSK (Quadrature Phase Shift Keying)

Uses four distinct phase shifts to send two bits per symbol.

QAM (Quadrature Amplitude Modulation)

Combines amplitude and phase variations to send multiple bits per symbol (e.g., 4–6 bits/symbol).

Baud Rate

Number of symbols transmitted per second, not necessarily equal to bit rate.

Bandwidth

Range of frequencies that can pass through a channel without significant attenuation.

Time Division Multiplexing (TDM)

Shares a channel by assigning each signal a fixed time slot in a repeating cycle.

Frequency Division Multiplexing (FDM)

Shares a channel by allocating distinct frequency bands to different signals.

Wavelength Division Multiplexing (WDM)

Optical version of FDM; multiple wavelengths carried on a single fiber.

Delta Modulation

Encodes the direction of change (+1 or -1) between consecutive samples using a single bit.

Predictive Encoding

Transmitter predicts next sample value; only sends difference from prediction.

Message Switching

Entire messages are stored and forwarded, causing delay until message arrival.

Packet Switching

Messages are broken into packets sent independently; improves efficiency and resource use.

Circuit Switching

Establishes a dedicated physical path between sender and receiver for duration of communication.

Stop-and-Wait Protocol

Sender transmits one frame, waits for ACK before sending next; simple but inefficient for long delays.

Piggybacking

ACKs are attached to outgoing data frames to reduce overhead, but delayed data may cause retransmissions.

Bit Stuffing

Inserts a 0 after five consecutive 1s to prevent confusion with the flag pattern (01111110).

Byte Stuffing

Adds escape (ESC) characters before special bytes like FLAG or ESC in data stream.

Flag Pattern in Framing

01111110 is used to mark start and end of frames in bit-oriented protocols like HDLC or PPP.

Purpose of Checksum

Detects transmission errors by comparing recomputed value with the received one.

Hamming Distance

Minimum number of bit changes required to convert one valid codeword to another.

Error Correction Ability

A code with Hamming distance d can detect up to d−1 errors and correct up to (d−1)/2.

Hamming Code Parity Bit Positions

Parity bits are placed at positions 1, 2, 4, 8, 16… corresponding to powers of two.

Hamming Code Example

For 16-bit data, five parity bits are enough to correct single-bit errors (fits within 31 bits).

CRC (Cyclic Redundancy Check)

Uses polynomial division over binary data to generate a remainder that detects burst errors.

CRC Detection Mechanism

Receiver divides received bits by generator polynomial; nonzero remainder indicates error.

Polynomial Used in CRC Example

x³ + 1 corresponds to binary 1001.

Purpose of Sequence Numbers

Distinguish new frames from retransmissions and ensure proper ordering.

Positive Acknowledgment with Retransmission (PAR)

Sender retransmits frame if ACK not received within timeout; ensures reliability over noisy channels.

Timer Expiration

When ACK doesn’t arrive before timeout, sender retransmits the unacknowledged frame.

Simplex Stop-and-Wait (Protocol 2)

Adds flow control to prevent receiver buffer overflow; uses dummy ACK frames.

Simplex for a Noisy Channel (Protocol 3)

Adds sequence numbers and timers for error + flow control; 1-bit sequence prevents duplication.

Sliding Window Protocol

Allows multiple outstanding frames before ACKs; improves efficiency over long-delay channels.

Sender Window

Set of sequence numbers sender can send before blocking; equals max unacknowledged frames.

Receiver Window

Set of frames receiver is willing to accept; outside this range are discarded.

Go-Back-N Protocol

On error, sender retransmits from the damaged frame onward; receiver only accepts next expected frame.

Selective Repeat Protocol

Only the specific damaged frame is retransmitted; receiver buffers out-of-order frames.

Window Size in Selective Repeat

Must be ≤ (sequence number space / 2) to avoid ambiguity between new and old frames.

Stop-and-Wait Efficiency Formula

η = 1 / (1 + 2a), where a = propagation delay / transmission time.

Frame Transmission Delay

Frame size (bits) / channel bandwidth (bps).

Propagation Delay

Distance / propagation speed; for 800 km fiber at 2×10⁵ km/s, delay = 4 ms.

Queuing Delay Formula

(nL + (L − x)) / R, where n = packets waiting, L = length, R = link rate, x = bits already sent.

Channel Utilization Example (Satellite)

With 1 Mbps link, 1000-bit frames, and 270 ms one-way delay, efficiency ≈ 0.18%.

Collisions in Broadcast Subnet

Fraction wasted = 1 − (np(1−p)ⁿ⁻¹ + (1−p)ⁿ), where n = hosts, p = transmit probability.

ATM Fixed-Length Cells

Small, fixed cells (53 bytes) simplify fast hardware switching and reduce delay variation.

Connection Setup Phases

Connection establishment → data transfer → connection release.

Negotiation in Protocols

Exchange of control messages to agree on parameters like max size or QoS before data transfer.

Flow Control Purpose

Prevents sender from overwhelming receiver with data faster than it can process.

Error Control Purpose

Ensures corrupted or lost frames are detected and retransmitted to maintain reliability.

Data Link Layer Services

Framing, error control, flow control, and reliable frame delivery to the network layer.

Piggybacking Problem

If receiver has no data to send back soon, delayed ACKs can cause sender timeouts.

Abnormal Case in 1-Bit Sliding Window

Occurs when sender and receiver start transmitting simultaneously, causing duplication.

One-Bit Sliding Window Equivalence

Stop-and-Wait; window size = 1.

Difference Between Go-Back-N and Selective Repeat

Go-Back-N retransmits all frames after error; Selective Repeat retransmits only the lost one.

Acknowledgment Types

Individual ACK for each frame or cumulative ACK acknowledging all up to a given frame.

When to Use Selective Repeat

Preferred when propagation delay is high and bandwidth is large; minimizes retransmission overhead.

Parity Check in 2D Scheme

Detects all single and double errors; may miss some triple errors if aligned along same row/column.

Role of Data Link Layer

Provides reliable communication over a single link between adjacent nodes.

Why Use Small Fixed-Length Cells in ATM

Simplifies switch design and reduces delay for real-time traffic.

Why Multiplexing is Cost-Effective

Combines multiple low-bandwidth channels into one high-bandwidth trunk, reducing infrastructure cost.

Bandwidth vs Bit Rate

Bandwidth is frequency range (Hz); bit rate is data transmitted per second (bps).

Propagation vs Transmission Delay

Propagation = time signal takes to travel; transmission = time to push bits into medium.

Difference Between Packet, Message, and Circuit Switching

Circuit = dedicated path; packet = split data units; message = store-and-forward entire message.

Go-Back-N Behavior on Error

Receiver discards erroneous and subsequent frames; sender retransmits from error frame onward.

Selective Repeat Receiver Behavior

Buffers correct frames received after an error; waits for missing frame to complete sequence.

Purpose of ACK Number

Specifies the next frame expected; confirms receipt of all prior frames.

Bit Errors and Checksums

Longer checksum reduces probability of undetected error, but never to zero.

Importance of Window Size

Determines pipeline length and channel utilization efficiency.

Advantages of Layered Design

Simplifies debugging, allows interoperability, and isolates changes between protocol layers.

OSI vs TCP/IP Layers

Both have network, transport, and application layers; OSI has more layers and supports both service types.

Reasons for Using Standards

Enable interoperability and economies of scale, though they can become outdated or politically compromised.

Connection-Oriented Example

TCP uses connection-oriented service for reliable stream delivery.

Connectionless Example

UDP sends datagrams without establishing a connection.

Common Physical Media

Twisted pair, coaxial cable, optical fiber, and wireless radio.

Nyquist Sampling for PCM

Requires at least twice the signal bandwidth (4 kHz voice → 8 kHz sampling → 125 µs/sample).

FDM Guard Band Purpose

Prevents channel overlap and interference between adjacent frequency bands.

Header Overhead Calculation Example

For 7 layers adding 20 bytes each to a 1000-byte message → 140 / 1140 = 12.3% overhead.

Reason for Using Hamming Codes

Allows single-bit error correction and double-bit detection at the data link layer.

CRC Remainder Example

Dividing x⁷ + x⁵ + 1 by x³ + 1 yields remainder x² + x + 1.

Transmission Efficiency Improvement

Achieved by pipelining frames via Go-Back-N or Selective Repeat protocols.

Problem Solved by Sliding Window Protocols

Overcome inefficiency of Stop-and-Wait in long-delay networks.

Purpose of Dummy Frames in Protocol 2

Receiver uses dummy frames to signal readiness and regulate data flow.

When ACK is Lost

Sender retransmits frame; receiver discards duplicate and sends ACK again.

Window Size = 1 Implication

Equivalent to Stop-and-Wait operation, fully sequential transmission.

Ack Timeout Too Short

Causes unnecessary retransmissions even when frames were correctly received.

Ack Timeout Too Long

Decreases efficiency due to idle waiting before retransmission.

Checksum vs CRC

Checksum sums bits modulo arithmetic; CRC uses polynomial division for stronger error detection.

Advantages of Packet Switching

Efficient bandwidth use, resilience to failure, and dynamic routing capability.

Purpose of Error Control in DLL

Ensures frames are delivered correctly to network layer through retransmission schemes.

Reason for Piggybacking Limitation

Waiting for data to send can delay ACK, triggering sender’s timer and retransmission.

Propagation Delay Dominant Channels

In long-distance satellite or fiber links, pipelined transmission significantly increases utilization.

Fraction of Slots Wasted in Collisions

1 − [n p (1−p)ⁿ⁻¹ + (1−p)ⁿ] represents wasted slots due to multiple simultaneous transmissions.

Benefit of Predictive Encoding

Reduces redundancy by sending only differences from predicted signal, improving compression.