Data Link Layer
Open in the Padhaiko app3.1 Data link layer functions - Framing, error control, flow control, access control
The Data Link Layer (Layer 2) transforms the raw, unverified transmission facility of the physical layer into a reliable, structured communication link between adjacent nodes on a network.
Primary Functions of the Data Link Layer
- Framing: Encapsulates network layer packets into discrete logical units called frames by delimiting boundaries using header and trailer markers.
- Error Control: Detects and corrects transmission errors introduced by physical channel noise through error-detecting codes and retransmission protocols (Automatic Repeat Request, ARQ).
- Flow Control: Prevents a fast sender from overwhelming a slow receiver with more frames than its input buffer can process.
- Media Access Control (MAC): Coordinates access to shared broadcast transmission media to minimize or resolve packet collisions among multiple transmitting stations.
- Physical Addressing: Embeds unique hardware (MAC) addresses in frame headers to ensure frames are received by the intended adjacent interface.
Framing Techniques
To delineate where one frame ends and the next begins, data link protocols use three primary framing methods:
- Character (Byte) Count:
- The frame header contains an integer field specifying the total number of characters/bytes in the frame.
- Weakness: If transmission noise corrupts the count field, the receiver loses framing synchronization entirely and cannot locate subsequent frames.
- Byte (Character) Stuffing:
- Used in byte-oriented protocols (such as PPP). Frames start and end with a reserved flag byte (e.g.,
0x7Ein HDLC/PPP). - Stuffing Rule: If the pattern
0x7Eoccurs naturally inside the user payload, the sender inserts an Escape character (ESC,0x7D) immediately before it. If0x7Ditself appears in user data, it is escaped as0x7D 0x5D. The receiver strips out the escape character, restoring original payload transparency.
- Used in byte-oriented protocols (such as PPP). Frames start and end with a reserved flag byte (e.g.,
- Bit Stuffing:
- Used in bit-oriented protocols (such as HDLC). Every frame begins and ends with the unique flag byte
01111110(). - Stuffing Rule: Whenever the transmitting hardware detects five consecutive s in the user payload bitstream, it automatically inserts (stuffs) a bit immediately following the fifth .
- The receiving hardware continuously monitors incoming bits: whenever it observes five consecutive s followed by a , it automatically discards (destuffs) the bit. If five s are followed by a and then a , it recognizes the true end-of-frame flag
01111110.
- Used in bit-oriented protocols (such as HDLC). Every frame begins and ends with the unique flag byte
3.2 Error control codes: Parity, checksum, CRC
Physical transmission channels are subject to thermal noise, electromagnetic interference, and signal attenuation, which can flip bits during transit. Error control incorporates detection and correction algorithms:
1. Parity Checks
- Simple Parity: Appends a single parity bit to each data word so that the total number of -bits is even (Even Parity) or odd (Odd Parity).
- Detects all single-bit errors; fails completely if an even number of bits () flip simultaneously.
- Two-Dimensional (2D) Parity: Arranges data into a rectangular matrix (table) of rows and columns. A parity bit is computed for each row (Longitudinal Redundancy Check) and each column (Vertical Redundancy Check).
- Detects burst errors and can pinpoint and correct any isolated single-bit error at the intersection of the erroneous row and column.
2. Internet Checksum
Used extensively at higher layers (IPv4 header, TCP, UDP):
- The data is divided into consecutive integers.
- All words are summed using one's complement arithmetic (any carry bit generated from the most significant bit is wrapped around and added to the least significant bit).
- The one's complement of the resulting sum is taken and placed in the checksum header field.
- At the receiver, all words including the checksum are summed in one's complement. If the result is all s (
0xFFFF), the frame is accepted as uncorrupted.
3. Cyclic Redundancy Check (CRC)
The Cyclic Redundancy Check is an exceptionally powerful, hardware-friendly polynomial division code deployed in Ethernet (FCS), Wi-Fi, and storage controllers.
Cyclic Redundancy Check (CRC) Mechanism
A data block of bits is treated as algebraic coefficients of a polynomial of degree . Sender and receiver agree upon a fixed Generator Polynomial of degree :
- Append zero bits to the data bitstream, forming .
- Divide by the generator polynomial using modulo-2 arithmetic (binary polynomial division where addition and subtraction are identical to bitwise XOR, with no carries or borrows).
- The division yields an remainder polynomial , called the Frame Check Sequence (FCS).
- The transmitted frame polynomial is:
- The receiver divides the incoming frame by using modulo-2 arithmetic. If the remainder is strictly zero, no error is detected; otherwise, the frame is corrupted and discarded.
Standard generator polynomials:
- CRC-8: (ATM headers)
- CRC-16-CCITT: (HDLC, X.25)
- CRC-32 (IEEE 802.3 Ethernet):
CRC-32 detects all single-bit errors, all double-bit errors, all odd numbers of bit errors, and all burst errors of length .
3.3 Data link protocols: PPP, HDLC
High-Level Data Link Control (HDLC)
Standardized by ISO (ISO 3309 / 4335), HDLC is a foundational bit-oriented synchronous data link protocol:
- Frame Structure:
- Flag Field: Delimited by
01111110(0x7E) with hardware bit stuffing. - Three Frame Types (Identified by Control Field):
- Information Frames (I-Frames): Transport user payload data from the network layer. Embed sequence numbers and piggybacked acknowledgement numbers for sliding window flow/error control.
- Supervisory Frames (S-Frames): Carry flow and error control commands when no user data is waiting to piggyback:
RR(Receive Ready): Acknowledges frames up to and indicates readiness to receive.RNR(Receive Not Ready): Acknowledges frames but halts transmission due to buffer congestion.REJ(Reject): Requests Go-Back-N retransmission starting from .SREJ(Selective Reject): Requests retransmission of only the single missing frame .
- Unnumbered Frames (U-Frames): Manage link initialization, mode setting, and disconnection (e.g.,
SABMfor Set Asynchronous Balanced Mode,DISCfor Disconnect,UAfor Unnumbered Acknowledgment).
Point-to-Point Protocol (PPP)
Standardized in RFC 1661, PPP is a byte-oriented protocol designed for direct communication over dial-up, DSL (PPPoE), and leased serial lines:
- Three Core Architectural Components:
- Framing: HDLC-like framing using flag byte
0x7Eand byte stuffing. - Link Control Protocol (LCP): Establishes, configures, tests, and terminates the physical point-to-point data link. Negotiates Maximum Receive Unit (MRU) and authentication protocols:
- PAP (Password Authentication Protocol): Insecure two-way handshake; sends plaintext username and password.
- CHAP (Challenge Handshake Authentication Protocol): Secure three-way handshake; server sends random challenge, client returns MD5 hash of
(secret + challenge), preventing replay attacks.
- Network Control Protocols (NCP): A family of independent protocols that establish and configure network-layer protocols over the PPP link (e.g., IPCP assigns an IPv4 address and DNS servers dynamically to the client).
- Framing: HDLC-like framing using flag byte
3.4 Logical link control (LLC) and media access control (MAC) sublayers
In local area networks (LANs), multiple devices share a single common transmission medium. To separate medium-independent functions from medium-dependent hardware mechanisms, the IEEE 802 committee partitioned the OSI Data Link Layer into two distinct sublayers:
| Aspect | Logical Link Control (LLC) | Media Access Control (MAC) |
|---|---|---|
| OSI Sublayer Position | Upper sublayer of Layer 2 (interfaces with Layer 3 Network Layer) | Lower sublayer of Layer 2 (interfaces with Layer 1 Physical Layer) |
| Medium Dependence | Completely independent of underlying physical transmission medium | Hardware-dependent; tailored to specific physical media (copper, fiber, RF) |
| Core Functions | Multiplexes multiple network protocols; provides flow and error control | Frame delineation, physical MAC addressing, channel access contention |
| Addressing Mechanism | Service Access Points: Destination SAP (DSAP) and Source SAP (SSAP) | 48-bit physical hardware MAC addresses burned into the NIC |
| Standard Scope | Single standard: IEEE 802.2 used uniformly across all 802 LANs | Diverse standards: IEEE 802.3 (Ethernet), 802.11 (Wi-Fi), 802.15 (Bluetooth) |
3.5 Random access protocols: ALOHA, CSMA, CSMA/CD, CSMA/CA
In broadcast networks, when two or more nodes transmit simultaneously over a shared channel, their signals collide and corrupt the data. Multiple Access protocols coordinate channel usage:
1. Pure ALOHA
Developed by Norman Abramson at the University of Hawaii (1970):
- Principle: A station transmits immediately whenever it has a frame ready.
- Vulnerable Period: A collision occurs if any other station starts transmitting within one frame transmission time () before or after the start of the current frame. Thus, the vulnerable period is:
- Throughput (): Under Poisson arrival of frames with offered channel traffic load (average frames per frame transmission time):
Maximum throughput occurs at :
2. Slotted ALOHA
Roberts (1972) improved ALOHA efficiency by discretizing channel time:
- Principle: Time is divided into synchronized discrete slots of duration . Stations are allowed to transmit only at the exact beginning of a time slot.
- Vulnerable Period: Reduced by half:
- Throughput ():
Maximum throughput occurs at :
3. Carrier Sense Multiple Access (CSMA)
Instead of blindly transmitting like ALOHA, CSMA requires stations to "listen before talk" (carrier sensing). If the channel is sensed busy, transmission is deferred:
- 1-Persistent CSMA: If channel is busy, listen continuously; as soon as it becomes idle, transmit immediately with probability . High probability of collision when two stations wait for an ongoing transmission to finish.
- Non-Persistent CSMA: If channel is busy, wait a random amount of time before sensing the channel again. Reduces collisions, but increases idle channel delay.
- p-Persistent CSMA: Used in slotted channels. If idle, transmit with probability ; defer to next slot with probability .
4. CSMA/CD (Carrier Sense Multiple Access with Collision Detection — IEEE 802.3)
Deploys "listen while talk" in wired Ethernet:
- Station senses the channel; if idle, begins transmitting.
- Station continues monitoring the channel voltage while transmitting its frame.
- If the signal voltage exceeds normal threshold, a collision is detected.
- Station aborts transmission immediately, broadcasts a jam signal to notify all network stations, and backs off.
- Truncated Binary Exponential Backoff: After -th consecutive collision (), the station waits a random integer number of slot times ( in ), where:
After 10 collisions, backoff range freezes at ; after 16 failed attempts, the frame is aborted.
- Minimum Frame Size Constraint: A station must not finish transmitting before a collision signal from the farthest station on the cable can propagate back:
In Ethernet with maximum round-trip propagation time , .
5. CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance — IEEE 802.11)
In wireless RF environments, collision detection is physically impossible because a station's own transmitter swamps its sensitive receiver (dynamic range mismatch) and nodes cannot sense collisions at distant receivers (hidden terminal problem). Therefore, Wi-Fi uses collision avoidance:
- Interframe Spaces (IFS): Strict priority waiting intervals: SIFS (Short IFS, for immediate ACKs), PIFS (PCF IFS), and DIFS (Distributed IFS, for regular data).
- RTS/CTS Handshake:
- Sender transmits a short Request to Send (RTS) frame.
- Receiver replies with a Clear to Send (CTS) frame.
- All neighboring stations hearing either RTS or CTS update their internal timer, the Network Allocation Vector (NAV), deferring transmission and avoiding collisions at both sender and receiver.
- Every successfully received unicast data frame must be acknowledged with an immediate explicit ACK frame after SIFS.
3.6 Token based protocols: Token bus, token ring, FDDI
Unlike contention-based random access protocols, token-based systems are deterministic collision-free protocols:
- Token Ring (IEEE 802.5):
- Stations are wired logically and physically in a closed loop. A special 3-byte control frame called the token continuously circulates around the ring.
- When a station with pending data captures the free token, it flips a bit in the token (converting it to a start-of-frame delimiter), appends its data frame, and transmits it downstream.
- Each downstream station inspects the frame; if the destination MAC matches, it copies the frame and sets frame-status bits (
A = 1,C = 1). - The frame returns to the sender, which strips the frame from the ring and releases a new free token.
- Active Monitor Station: Eliminates orphaned frames and regenerates lost tokens.
- Token Bus (IEEE 802.4):
- Stations are physically connected via a linear coaxial or broadband bus, but logically organized in a circular token ring ordered by descending station addresses.
- Common in industrial manufacturing automation (MAP architecture).
- Fiber Distributed Data Interface (FDDI):
- An ANSI / ISO standard operating at over optical fiber up to connecting up to stations.
- Dual Counter-Rotating Rings: Features a Primary Ring (transmits data and tokens clockwise) and a Secondary Ring (transmits counter-clockwise).
- If a fiber cable is severed or a station fails, neighboring stations automatically reconfigure internal optical bypass switches to loop (wrap) the primary ring into the secondary ring, creating a single continuous folded ring (self-healing ring).
3.7 Ethernet (IEEE 802.3) and its evolution, bridged and switched Ethernet
Ethernet is the universal dominant LAN technology. Originally designed by Robert Metcalfe at Xerox PARC (1973), it was standardized under IEEE 802.3.
The IEEE 802.3 Ethernet Frame Format
| Field Name | Size (Bytes) | Purpose and Structure |
|---|---|---|
| Preamble | 7 bytes | Alternating pattern 10101010 used by receiver to synchronize bit clock |
| Start of Frame Delimiter (SFD) | 1 byte | Byte 10101011 indicating that destination address immediately follows |
| Destination MAC Address | 6 bytes | 48-bit hardware address of receiving station (unicast, multicast, broadcast) |
| Source MAC Address | 6 bytes | 48-bit hardware address of transmitting network interface card |
| Length / EtherType | 2 bytes | Value denotes length (802.3); value (0x0600) denotes protocol Type (Ethernet II: 0x0800 for IPv4, 0x86DD for IPv6, 0x0806 for ARP) |
| Payload Data | 46 to 1500 bytes | Network layer PDU (e.g., IP datagram). Padded to if payload |
| Frame Check Sequence (FCS) | 4 bytes | 32-bit CRC (CRC-32) computed over destination, source, type, and payload |
- Minimum Ethernet frame size: (excluding Preamble and SFD).
- Maximum Ethernet frame size: (excluding Preamble and SFD).
Evolution: Shared Bus Bridged Switched Ethernet
- Shared Bus / Hubs: All devices share a single coaxial cable or hub, forming one shared collision domain operating in half-duplex CSMA/CD.
- Bridged Ethernet (Transparent Bridging):
- Multiport bridges connect LAN segments. A bridge maintains a Forwarding Database (MAC table) via:
- Learning: Reads the source MAC address of every arriving frame and records
(Source MAC, Ingress Port, Aging Timer)in its table. - Forwarding / Filtering: Inspects the destination MAC address. If the destination MAC is in the table on a different port, it forwards the frame to that specific port only; if on the same port, it drops (filters) it.
- Flooding: If destination MAC is unknown or is a broadcast/multicast address, the bridge floods the frame to all ports except the arrival port.
- Learning: Reads the source MAC address of every arriving frame and records
- Multiport bridges connect LAN segments. A bridge maintains a Forwarding Database (MAC table) via:
- Spanning Tree Protocol (IEEE 802.1D STP):
- Redundant physical links between bridges prevent single points of failure but create fatal forwarding loops, resulting in catastrophic broadcast storms and duplicate frame delivery.
- STP dynamically elects a Root Bridge and disables (blocks) redundant switch ports, calculating a loop-free logical spanning tree. If an active link fails, blocked ports are automatically unblocked.
- Switched Ethernet: Modern Ethernet replaces shared links entirely with dedicated full-duplex microsegmentation on high-speed hardware ASIC switches. Collisions are eliminated ( collision-free), rendering CSMA/CD obsolete in full-duplex gigabit/10-gigabit links.
3.8 WLAN (Wi-Fi) and IEEE 802.11
Standardized by IEEE 802.11, Wireless Local Area Networks (WLANs) provide high-speed untethered network connectivity using RF spectrum in the unlicensed ISM () and UNII (, ) bands:
802.11 Architectural Topologies
- Basic Service Set (BSS): The fundamental building block consisting of wireless mobile stations and an optional central Access Point (AP) operating in Infrastructure Mode.
- Independent BSS (IBSS): An Ad-Hoc network formed directly between peer stations without an Access Point.
- Extended Service Set (ESS): Multiple BSS cells interconnected by a wired backbone distribution system (DS), allowing mobile clients to roam transparently across coverage areas.
The Hidden and Exposed Terminal Problems
- Hidden Terminal Problem: Node and Node can both communicate with central node , but cannot hear each other due to distance or physical obstacles. If both transmit to simultaneously, their frames collide at .
- Solution: IEEE 802.11 RTS/CTS handshake. When responds to 's RTS with a CTS frame, the CTS is heard by , instructing to reserve the channel via its NAV timer.
- Exposed Terminal Problem: Node is transmitting to . Neighboring node wants to transmit to (out of range of ). Sensing 's transmission, needlessly defers, wasting channel capacity. RTS/CTS resolves this because hears 's RTS but not 's CTS, allowing to transmit safely to .
| Standard | Frequency Band | Maximum Theoretical Physical Data Rate | Modulation / Channel Bandwidth |
|---|---|---|---|
| 802.11b | DSSS, CCK () | ||
| 802.11a | OFDM () | ||
| 802.11g | OFDM () | ||
| 802.11n (Wi-Fi 4) | / | MIMO (up to 4 spatial streams), | |
| 802.11ac (Wi-Fi 5) | 256-QAM, MU-MIMO, | ||
| 802.11ax (Wi-Fi 6) | 1024-QAM, OFDMA, Target Wake Time |
3.9 VLAN and its importance
Virtual Local Area Network (VLAN)
A Virtual LAN (VLAN) is a logical subgrouping of network devices configured by software to communicate as if they were attached to the same isolated physical broadcast domain, regardless of their actual physical switch attachment.
Importance and Engineering Benefits of VLANs
- Broadcast Containment: Broadcast frames (such as ARP requests and DHCP discoveries) are confined strictly within the originating VLAN, preventing network congestion across other departments.
- Enhanced Security: Sensitive departmental traffic (e.g., Finance or Human Resources) is cryptographically or logically isolated at Layer 2; cross-VLAN communication requires routing through an explicit Layer 3 firewall or access control list (ACL).
- Cost Reduction and Geographic Flexibility: Users moving offices do not require physical recabling; administrators simply reassign their switch port to the appropriate VLAN via software configuration.
Access Ports vs. Trunk Ports and IEEE 802.1Q Tagging
- Access Port (Untagged): Connects to an end-user host (PC, server). Belongs to a single VLAN and carries ordinary untagged Ethernet frames.
- Trunk Port (Tagged): Interconnects switches or connects a switch to a router (Router-on-a-Stick). Carries multiplexed traffic belonging to multiple VLANs simultaneously.
- IEEE 802.1Q Frame Tagging: To track which VLAN a frame belongs to across a trunk link, a header is inserted immediately after the Source MAC address:
- TPID (Tag Protocol Identifier, 2 bytes): Always set to
0x8100to indicate an 802.1Q tagged frame. - TCI (Tag Control Information, 2 bytes):
- PCP (Priority Code Point, 3 bits): 802.1p Quality of Service priority (–).
- DEI (Drop Eligible Indicator, 1 bit): Packet discard preference during congestion.
- VID (VLAN Identifier, 12 bits): Uniquely identifies the VLAN ( to ). VIDs and are reserved; usable VLAN IDs range from to .
- TPID (Tag Protocol Identifier, 2 bytes): Always set to
3.10 Virtual circuit switching: ATM, MPLS
Connection-oriented virtual circuit networks combine the high throughput and predictable QoS of circuit switching with the flexible multiplexing efficiency of packet switching:
Asynchronous Transfer Mode (ATM)
- Cell-Based Switching: Transports all traffic (voice, video, data) packaged into small, fixed-size packets called cells of exactly :
- Header: Contains flow control, Virtual Path Identifier (VPI), Virtual Channel Identifier (VCI), Payload Type, and Header Error Control (HEC).
- Information Payload: User data payload.
- Why Fixed 53-Byte Cells? In early telecommunications, voice required minimal packetization latency and predictable queuing jitter, whereas computer data demanded large payload efficiency. Compromise between Europe ( payload) and the USA ( payload) yielded . Fixed cell size allowed fast switching entirely in hardware.
- Hierarchical VPI/VCI Routing: Virtual paths aggregate multiple virtual channels, simplifying routing table hierarchies across carrier backbones.
Multiprotocol Label Switching (MPLS)
MPLS (IETF RFC 3031) has superseded ATM as the universal high-speed core transport protocol for Internet Service Providers:
- Operating Concept ("Layer 2.5"): Integrates Layer 2 switching speed with Layer 3 IP routing flexibility. A short, fixed-length MPLS Label ("shim header") is prepended between the Layer 2 data link header and the Layer 3 IP header:
- Label (20 bits): The local virtual path identifier used for forwarding lookup.
- Traffic Class (TC / EXP, 3 bits): Quality of Service and DiffServ class priority.
- Bottom of Stack (S, 1 bit): Indicates whether this is the final label or if labels are stacked (hierarchical tunneling).
- Time to Live (TTL, 8 bits): Replicates IP TTL to prevent infinite looping.
- MPLS Network Elements:
- Label Edge Router (LER / Ingress): Evaluates incoming IP packet, maps it to a Forwarding Equivalence Class (FEC), pushes an MPLS label onto the packet, and sends it into the MPLS domain.
- Label Switch Router (LSR / Core): Reads the 20-bit label, swaps it for an outgoing label from its Label Forwarding Information Base (LFIB), and forwards the packet out the designated interface at wire speed without inspecting the IP header.
- Egress LER: Pops the final label and forwards the original IP packet to the destination network.
- Applications: MPLS Traffic Engineering (MPLS-TE), Layer 2 and Layer 3 Virtual Private Networks (BGP/MPLS IP VPNs), and guaranteed Quality of Service (QoS).
Worked Out Examples
3.1
A transmitter uses Cyclic Redundancy Check (CRC) error detection. The transmitter wants to send an 8-bit user data bitstring:
Sender and receiver agree upon the generator polynomial:
- Convert the generator polynomial into its corresponding binary divisor representation.
- Determine the degree of the generator polynomial and calculate the number of zero bits that must be appended to the data bitstring.
- Perform modulo-2 polynomial division to determine the -bit Frame Check Sequence (FCS) remainder.
- Construct the complete transmitted codeword bitstring and verify that the codeword is divisible by without remainder.
Formulating Divisor Binary and Augmented Data:
- The generator polynomial is:
This corresponds directly to the binary divisor:
- Degree of is .
- Therefore, append zeros to the right of the data bitstring :
Executing Modulo-2 Long Division: Modulo-2 division uses bitwise XOR (with no borrows or carries):
10001111 (Quotient)
-----------------
10101 ) 101001000000
10101
-----
000011000000 -> Bring down next bits until length equals 5
11000
10101
-----
011010
10101
-----
011110
10101
-----
010110
10101
-----
00011 -> Remainder (4 bits): 0011The division yields the FCS remainder:
Constructing and Verifying Transmitted Codeword:
- The transmitted codeword is formed by replacing the appended 4 zeros with the remainder :
- Verification at Receiver: Dividing by using modulo-2 arithmetic leaves remainder . Hence, error-free transmission is confirmed.
- Binary divisor: .
- Polynomial degree ; append zeros.
- FCS remainder: .
- Transmitted codeword: .
3.2
A legacy IEEE 802.3 CSMA/CD Ethernet bus operates at transmission speed (). The maximum physical distance between the two farthest stations across the bus is . Assume:
- Propagation velocity of electrical signals in coaxial copper .
- Four intermediate signal repeaters are deployed along the path, contributing a combined hardware repeating delay of round-trip.
Calculate:
- The one-way cable propagation delay in microseconds ().
- The total worst-case round-trip propagation time (), including repeater delays.
- The absolute minimum frame size in bits and bytes necessary to ensure collision detection operates reliably.
- Explain why Ethernet standardizes the minimum frame size at ().
Calculating One-Way and Worst-Case Round-Trip Delay:
- One-way cable propagation delay:
- Worst-case round-trip propagation time ():
Evaluating Minimum Frame Size Requirement: In CSMA/CD, the frame transmission time must be at least equal to the worst-case round-trip collision slot time:
In bytes:
Why IEEE Standardizes at (): To provide an engineering safety margin and accommodate maximum permissible cable topologies with repeaters and long drop cables (worst-case slot time of ):
If a frame is smaller than , the transmitter would complete transmission before the collision signal arrived back, wrongly concluding the frame was delivered without collision.
- One-way propagation delay: .
- Total round-trip collision time: .
- Minimum calculated frame size: ().
- Standard Ethernet specifies () to cover maximum allowable worst-case topologies with an engineering safety margin.
3.3
A shared broadcast radio channel operates at a digital transmission rate of (). Multiple ground stations generate fixed-length packets of . Assume Poisson frame arrival statistics across all stations with aggregate offered traffic rate .
- Calculate the frame transmission time in milliseconds ().
- Determine the maximum theoretical channel throughput in under Pure ALOHA, and state the value of offered traffic load at which this occurs.
- Determine the maximum theoretical channel throughput in under Slotted ALOHA, and state the value of offered traffic load at which this occurs.
- Explain mathematically why Slotted ALOHA achieves exactly twice the throughput of Pure ALOHA.
Calculating Frame Transmission Time: The time required to transmit one 1000-bit frame onto the channel:
Evaluating Maximum Throughput for Pure ALOHA and Slotted ALOHA:
- Pure ALOHA Throughput:
Differentiating with respect to and setting to zero yields maximum throughput at :
Maximum throughput in kbps:
- Slotted ALOHA Throughput:
Maximum throughput occurs at :
Maximum throughput in kbps:
Mathematical Justification of Performance Advantage:
- In Pure ALOHA, stations transmit asynchronously at any moment. A packet transmitted at time is vulnerable to collisions from any packet that started transmitting between and . Thus, the vulnerable period is , yielding collision-free probability .
- In Slotted ALOHA, stations transmit only at synchronized slot boundaries. A packet is vulnerable only to packets that arrived during the preceding single slot (). Thus, the vulnerable period is cut in half to , doubling the maximum throughput from to .
- Frame transmission time: .
- Pure ALOHA: Max throughput = () at .
- Slotted ALOHA: Max throughput = () at .
- Slotted ALOHA restricts transmissions to discrete slot boundaries, reducing the collision vulnerable period from to , thereby doubling channel efficiency.
Practice Exercises
Practice Exercises — Data Link Layer & MAC Protocols
Explain the Bit Stuffing framing algorithm. A data link transmitter receives the following payload bitstream from the network layer:
- Show the exact bitstream after bit stuffing is applied at the transmitter.
- Explain how the receiving data link layer recognizes frame boundaries and restores the original bitstream.
Bit Stuffing Algorithm and Transformation:
- Rule: The flag pattern is (). Whenever the sender detects five consecutive s in user data, it immediately inserts a stuffed bit, regardless of whether the subsequent bit is a or a .
- Input stream breakdown:
0110: No five consecutive 1s.11111: Five consecutive 1s detected stuff a0followed by1.0: Followed by zero.11111: Five consecutive 1s detected stuff a0followed by0.010: No five consecutive 1s.11111: Five consecutive 1s detected stuff a0followed by remaining11001.
- Concatenating all stuffed segments:
Receiver De-Stuffing and Delimiting Operation:
- The receiver scans incoming bits. Whenever it observes five consecutive s:
- If the 6th bit is a , it is recognized as a stuffed bit and is automatically discarded (de-stuffed).
- If the 6th bit is a and the 7th bit is a , the receiver recognizes the genuine end-of-frame flag
01111110. - If the 6th and 7th bits are both s (
1111111), it indicates a transmission error or abort signal.
- Stuffed bitstream:
011011111010111110001011111011001(three -bits stuffed after each run of five s). - The receiver discards any -bit immediately following five consecutive s, and identifies
01111110as the true frame boundary.
A data link layer uses CRC error detection with generator polynomial:
The transmitter transmits a 10-bit data message:
- Represent the generator polynomial as a binary bitstring.
- Compute the 4-bit CRC Frame Check Sequence (FCS) remainder using modulo-2 arithmetic.
- Formulate the transmitted codeword frame.
Divisor Bitstring and Modulo-2 Division:
- (, degree ).
- Append zeros to : ().
- Execute modulo-2 division by :
- bring down .
- bring down bits .
- bring down .
- bring down .
- remainder is .
- The 4-bit remainder FCS is:
Constructing Transmitted Codeword:
- Appending the FCS remainder to the original 10-bit data:
- Divisor bitstring: .
- FCS remainder: .
- Transmitted codeword: .
Compare CSMA/CD (Ethernet) and CSMA/CA (Wi-Fi) multiple access mechanisms. Explain why CSMA/CD cannot be used directly in wireless local area networks, detailing the Hidden Terminal Problem and the RTS/CTS mechanism.
Why CSMA/CD Fails in Wireless Networks:
- Dynamic Signal Power Range: Wireless transmissions attenuate rapidly with distance (inverse square law). A station's own transmitter radiates strong local RF power that completely overwhelms the millivolt-level signal from a distant colliding station; the station cannot hear collisions while transmitting.
- Half-Duplex Radio Constraints: Standard Wi-Fi transceivers cannot transmit and receive simultaneously on the exact same radio channel.
- Hidden Terminal Problem: Two wireless stations ( and ) separated by a wall or distance may both be within range of an Access Point (), but cannot detect each other's RF carriers. If both transmit simultaneously to , a destructive collision occurs at despite carrier sensing at and .
The RTS/CTS Solution in CSMA/CA:
- Sender sends a short Request to Send (RTS) control frame containing the intended data transmission duration.
- Receiver broadcasts a Clear to Send (CTS) frame containing the reserved duration.
- Hidden terminal hears 's CTS and updates its internal Network Allocation Vector (NAV) timer, voluntarily suppressing its own transmissions until 's data and ACK complete.
CSMA/CD is unworkable in wireless LANs due to enormous RF dynamic range differences, half-duplex radio hardware, and hidden terminal problems. CSMA/CA uses collision avoidance with interframe spaces (DIFS/SIFS), random backoff, and the RTS/CTS handshake (which alerts hidden terminals via CTS broadcast and NAV timer reservations) to prevent collisions before they occur.
Describe how a Transparent Learning Switch operates. Explain how it builds its Forwarding Database (CAM table) and describe the three actions (filtering, forwarding, and flooding) it performs upon receiving a frame. Explain the purpose of the Spanning Tree Protocol (STP).
Transparent Learning Switch Operation:
- A switch begins with an empty Media Access Control (MAC) address table.
- Learning (Source Address Inspection): Whenever a frame arrives on port , the switch reads its Source MAC address and records the mapping
(Source MAC, Port P_x, Timestamp)into its Content-Addressable Memory (CAM) table. - Forwarding Decision (Destination Address Inspection):
- Filtering: If the Destination MAC is in the table and resides on the same ingress port , the frame is filtered (discarded), as the destination already received it directly.
- Forwarding: If the Destination MAC is in the table on a different port , the switch selectively forwards the frame only out of port .
- Flooding: If the Destination MAC is not in the table, or is a broadcast/multicast address, the switch floods the frame out of all ports except the arrival port .
Role of Spanning Tree Protocol (IEEE 802.1D STP):
- Redundant physical links between switches create closed switching loops. When a switch floods an unknown or broadcast frame, the frame circulates endlessly around the loop in both directions, consuming bandwidth (broadcast storm) and corrupting MAC tables.
- STP uses Bridge Protocol Data Units (BPDUs) to elect a Root Bridge, compute shortest path costs, and selectively place redundant ports into a blocking state, guaranteeing a loop-free logical tree while maintaining automatic standby failover paths.
A transparent switch automatically learns host locations by recording arriving Source MACs into its CAM table. It forwards known unicast frames to the specific destination port, filters frames on the same port, and floods unknown/broadcast frames out all other ports. The Spanning Tree Protocol (STP) prevents devastating broadcast storms by dynamically blocking redundant physical loops, creating a loop-free active forwarding topology.
Explain the concept of a Virtual Local Area Network (VLAN) and distinguish between Access Ports and Trunk Ports.
- Describe the structure of the IEEE 802.1Q tag header.
- Calculate the maximum theoretical number of distinct VLANs supported by the 802.1Q standard.
- Explain how "Router-on-a-Stick" enables inter-VLAN routing using a single physical router interface.
Access Ports, Trunk Ports, and 802.1Q Tag Structure:
- Access Port: Connects end-user hosts; belongs to a single VLAN and transmits standard untagged frames.
- Trunk Port: Connects switch-to-switch or switch-to-router; multiplexes traffic for multiple VLANs using IEEE 802.1Q tags inserted between Source MAC and EtherType:
- TPID (Tag Protocol Identifier, 16 bits): Set to
0x8100to indicate an 802.1Q frame. - PCP (Priority Code Point, 3 bits): Layer 2 802.1p Quality of Service priority.
- DEI (Drop Eligible Indicator, 1 bit): Congestion discard indicator.
- VID (VLAN Identifier, 12 bits): Identifies the VLAN.
- TPID (Tag Protocol Identifier, 16 bits): Set to
- Maximum VLAN Count: With , there are possible IDs. Since VID (reserved for priority frames) and VID (reserved) cannot be assigned, there are:
Inter-VLAN Routing via "Router-on-a-Stick":
- Because switches maintain strict Layer 2 isolation between different VLANs, traffic cannot pass between VLAN 10 and VLAN 20 within the switch.
- In "Router-on-a-Stick", a single physical Ethernet cable connects a trunk switch port to a router physical interface.
- The router physical interface is partitioned into logical sub-interfaces (e.g.,
FA0/0.10andFA0/0.20), each configured with 802.1Q encapsulation for its respective VLAN ID and assigned that VLAN's default gateway IP. - Traffic from VLAN 10 travels up the trunk link tagged as VLAN 10, is routed by the router CPU into the VLAN 20 sub-interface, and is sent back down the same physical link tagged as VLAN 20.
- Access ports carry untagged single-VLAN traffic; trunk ports carry multiplexed multi-VLAN traffic tagged with a 802.1Q header (
TPID 0x8100, PCP, DEI, VID). - Maximum usable VLAN IDs: ().
- Router-on-a-Stick configures logical sub-interfaces on a single physical router port connected to a switch trunk, routing tagged frames across subnets over the same physical cable.