eitf45 -L3- data link layer MAC.pdf

# Data link layer and local area networks The data link layer and local area networks focus on how devices within a limited geographical area communicate, particularly through shared media and various network topologies [3](#page=3) [5](#page=5). ## 1. Data link layer and local area networks ### 1.1 Introduction to local area networks (LANs) Local Area Networks (LANs) are networks that are limited in size and traditionally designed for private areas. Historically, LANs were characterized by a "shared-medium" concept, where multiple devices connected to the same communication channel. This meant that all devices on the network could potentially see all traffic [5](#page=5) [6](#page=6) [8](#page=8). ### 1.2 LAN topologies Various network topologies have been used for LANs to structure how devices are interconnected. These include [7](#page=7): * **Mesh topology**: In a mesh topology, every device is connected to every other device on the network. This provides high redundancy but can be complex and expensive to implement [7](#page=7). * **Bus topology**: In a bus topology, all devices are connected to a single central cable, known as the bus. Data is sent along the bus, and all devices receive the data, but only the intended recipient processes it [7](#page=7). * **Ring topology**: In a ring topology, devices are connected in a circular fashion. Data travels in one direction around the ring, passing through each device until it reaches its destination [7](#page=7). * **Star topology**: In a star topology, all devices are connected to a central hub or switch. This is a common topology in modern LANs, offering easier management and fault isolation [7](#page=7). ### 1.3 Data transfer on a shared medium On a shared medium, data is typically broadcast to all devices connected to the medium. A packet is sent from a source device, and all other devices receive it. The network interface card (NIC) of each device then checks the destination address in the packet to determine if it should process the data or discard it. To manage this shared access effectively and prevent collisions (when multiple devices try to transmit simultaneously), specific access methods and protocols are required [3](#page=3) [8](#page=8). ### 1.4 IEEE's LAN standards (Project 802) The Institute of Electrical and Electronics Engineers (IEEE) has established standards for LANs under Project 802. These standards define various aspects of LAN technologies, including different media access control methods and physical layer specifications. Notable standards include [9](#page=9): * **IEEE 802.3**: This standard primarily defines Ethernet, which is one of the most widely used LAN technologies [9](#page=9). * **IEEE 802.4**: This standard relates to Token Bus networks [9](#page=9). * **IEEE 802.5**: This standard defines Token Ring networks [9](#page=9). These standards aim to ensure interoperability between different network devices and vendors [9](#page=9). > **Tip:** Understanding the evolution from shared-medium LANs to switched networks is crucial. While older topologies like bus and ring are less common today, the principles of shared access and medium contention remain relevant, especially in wireless contexts. > **Example:** Imagine a simple bus topology where Device A wants to send data to Device C. Device A broadcasts the packet. Device B receives it, checks the destination (C), and discards it. Device C receives it, checks the destination (C), and accepts it. Device D receives it, checks the destination (C), and discards it [8](#page=8). --- # Ethernet and medium access control methods This section delves into the foundational aspects of standard Ethernet, tracing its evolution from shared collision domains to modern switched networks, while also detailing the structure of an Ethernet frame and the principles of Carrier Sense Multiple Access with Collision Detection (CSMA/CD) [10](#page=10) [11](#page=11) [12](#page=12) [13](#page=13) [14](#page=14) [15](#page=15) [16](#page=16) [17](#page=17) [29](#page=29) [30](#page=30) [31](#page=31) [32](#page=32). ### 2.1 Evolution of Ethernet and collision domains Ethernet has evolved significantly, particularly concerning how network devices share the transmission medium. In early Ethernet implementations, a single coaxial cable often formed a shared collision domain. A collision domain is a network segment where data packets originating from multiple devices can collide with each other, corrupting the data [12](#page=12). #### 2.1.1 Hubs and repeaters Hubs and repeaters act as multi-port repeaters, extending the physical length of a network segment and, importantly, also extending collision domains. All devices connected to a hub are part of the same collision domain [12](#page=12). #### 2.1.2 Switched Ethernet The advent of switches revolutionized Ethernet by segmenting collision domains. A network switch intelligently forwards data packets only to the intended destination port, based on MAC addresses. This drastically reduces the occurrence of collisions [13](#page=13). #### 2.1.3 Full-duplex switched Ethernet Modern switched Ethernet often operates in full-duplex mode. In full-duplex, a device can send and receive data simultaneously without the possibility of collisions on that link. This is because each port on the switch can have its own dedicated collision domain, effectively making each link a separate domain [14](#page=14). ### 2.2 Ethernet frame structure An Ethernet frame is the basic unit of data transmission on an Ethernet network. While the specific content and length can vary, a typical Ethernet frame consists of several fields, including [16](#page=16): * **Preamble:** A sequence of bits used for synchronization [16](#page=16). * **Start Frame Delimiter (SFD):** Marks the end of the preamble and the beginning of the frame's actual data [16](#page=16). * **Destination MAC Address:** The physical hardware address of the intended recipient [16](#page=16). * **Source MAC Address:** The physical hardware address of the sender [16](#page=16). * **Type/Length:** Indicates the protocol of the payload or the length of the frame [16](#page=16). * **Payload:** The actual data being transmitted [16](#page=16). * **Frame Check Sequence (FCS):** A checksum used for error detection [16](#page=16). > **Tip:** The MAC address is a unique 48-bit hardware address assigned to network interface controllers (NICs). You can view your system's MAC address using commands like `ipconfig /all` on Windows or `ifconfig` on Linux/macOS [15](#page=15). > **Example:** The hexadecimal view on page 17 shows a sample Ethernet frame, illustrating the arrangement of these fields [17](#page=17). ### 2.3 Carrier Sense Multiple Access with Collision Detection (CSMA/CD) CSMA/CD is a media access control (MAC) protocol used in early Ethernet networks to manage shared access to a common transmission medium. It was developed to handle situations where multiple devices might attempt to transmit data simultaneously, leading to collisions [29](#page=29). #### 2.3.1 Carrier Sense The "Carrier Sense" part means that a transmitting device first listens to the transmission medium to detect if it is currently busy. If the medium is idle, the device proceeds to transmit. If it is busy, the device waits [29](#page=29). #### 2.3.2 Multiple Access "Multiple Access" signifies that multiple devices share the same transmission medium, all capable of sending and receiving data [29](#page=29). #### 2.3.3 Collision Detection (CD) "Collision Detection" is the crucial component that differentiates CSMA/CD from basic CSMA. While transmitting, a device continues to monitor the medium. If it detects that its transmission is interfering with another transmission (i.e., a collision has occurred), it immediately aborts its transmission [29](#page=29) [30](#page=30). * **Collision Procedure:** Upon detecting a collision, the device stops transmitting its current frame and sends a jamming signal to ensure that all other stations on the network are aware of the collision. After sending the jamming signal, the device waits for a random amount of time (using a binary exponential backoff algorithm) before attempting to retransmit the frame [30](#page=30). > **Tip:** The purpose of the jamming signal is to ensure that all stations detect the collision and stop transmitting, preventing further corruption [30](#page=30). #### 2.3.4 Minimum frame size A critical aspect of CSMA/CD is the minimum frame size requirement. The sending station must be able to detect a collision *before* it finishes transmitting the last bit of the frame. This ensures that a device doesn't complete a corrupted transmission without realizing it [31](#page=31). The minimum frame size is determined by the round-trip propagation delay of the network segment. The formula for the minimum frame size is related to the propagation speed and the maximum segment length. Let $T_{prop}$ be the propagation delay and $R$ be the bit rate. The minimum time a station must be able to detect a collision is $2 \times T_{prop}$ [31](#page=31). The minimum frame size $L_{min}$ in bits is given by: $$ L_{min} = R \times (2 \times T_{prop}) $$ Where $T_{prop}$ is the time it takes for a signal to travel from one end of the network segment to the other and back. For a segment of length $D$ with propagation speed $v_{prop}$, $T_{prop} = D / v_{prop}$ [31](#page=31). > **Example:** Consider a 10 Mbps link that is 5 km long, with a propagation speed of 2/3 of the speed of light ($v_{prop} = \frac{2}{3} \times 300,000 \text{ km/s} = 200,000 \text{ km/s} = 2 \times 10^8 \text{ m/s}$) [32](#page=32). > > First, convert the length to meters: $D = 5 \text{ km} = 5000 \text{ m}$. > > Calculate the propagation delay: > $$ T_{prop} = \frac{D}{v_{prop}} = \frac{5000 \text{ m}}{2 \times 10^8 \text{ m/s}} = 2.5 \times 10^{-5} \text{ s} $$ > > The minimum time to detect a collision is $2 \times T_{prop}$: > $$ 2 \times T_{prop} = 2 \times 2.5 \times 10^{-5} \text{ s} = 5 \times 10^{-5} \text{ s} $$ > > The bit rate is $R = 10 \text{ Mbps} = 10 \times 10^6 \text{ bits/s}$. > > Calculate the minimum frame size: > $$ L_{min} = R \times (2 \times T_{prop}) = (10 \times 10^6 \text{ bits/s}) \times (5 \times 10^{-5} \text{ s}) = 500 \text{ bits} $$ > > Therefore, the minimum frame size that must be applied for the system to function end-to-end is 500 bits [32](#page=32). --- # Random access methods for network communication This topic explores fundamental random access methods used in network communication, focusing on ALOHA and the foundational principles of Carrier Sense Multiple Access (CSMA). ### 3.1 ALOHA ALOHA is a multiple-access method that was pioneered by the ALOHANET, one of the first wireless local area networks developed by the University of Hawaii. It allows multiple stations to share a communication channel without prior coordination [19](#page=19). #### 3.1.1 Pure ALOHA In Pure ALOHA, stations can transmit a frame at any time they have data to send. If two or more stations transmit simultaneously, their frames collide, leading to data corruption [20](#page=20) [21](#page=21). * **Collision Scenario:** A collision occurs if a frame is transmitted while another frame is already in transit or has not yet finished its transmission. The vulnerable period for a frame is twice the frame transmission time, as any transmission starting within that window will collide with the original frame [21](#page=21). #### 3.1.2 Slotted ALOHA Slotted ALOHA divides time into discrete slots of fixed duration, typically equal to the time required to transmit one frame. Stations are only allowed to transmit at the beginning of a slot [22](#page=22). * **Collision Reduction:** By synchronizing transmissions to the start of slots, Slotted ALOHA reduces the probability of collisions compared to Pure ALOHA. A collision can only occur if multiple stations attempt to transmit at the beginning of the *same* slot. The vulnerable period is reduced to the duration of a single slot [23](#page=23) [24](#page=24). #### 3.1.3 ALOHA resend strategy When a collision is detected, stations employing ALOHA employ a resend strategy. * **Backoff Time:** Stations wait for a random amount of time, known as the backoff time ($T_B$), before attempting to resend the frame [25](#page=25). * **Binary Exponential Backoff:** A common backoff strategy is binary exponential backoff, where the backoff time is chosen from a range that doubles with each retransmission attempt. The backoff time is chosen uniformly from $[0, 2^k - 1 \times T_f$, where $k$ is the attempt number and $T_f$ is the frame transmission time [25](#page=25). * **Maximum Attempts:** If a frame cannot be successfully transmitted after a maximum number of attempts ($K_{max}$), the station gives up and tries again later or aborts the transmission [25](#page=25). #### 3.1.4 ALOHA throughput The maximum theoretical throughput for Pure ALOHA is approximately 18% of the channel capacity, while Slotted ALOHA can achieve a theoretical maximum throughput of approximately 36% [26](#page=26). > **Tip:** Understanding the throughput limitations of ALOHA highlights the need for more efficient access methods, especially in busy networks. ### 3.2 Carrier Sense Multiple Access (CSMA) Carrier Sense Multiple Access (CSMA) is a method where stations first listen to (sense) the medium to determine if it is busy before transmitting [27](#page=27). * **Basic CSMA Strategies:** * **Persistent CSMA:** If the medium is busy, the station continues to sense the medium and transmits as soon as it becomes idle [27](#page=27). * **Non-persistent CSMA:** If the medium is busy, the station waits for a random amount of time, senses the medium again, and transmits if it is idle [27](#page=27). * **p-persistent CSMA:** If the medium is idle, the station transmits with probability $p$. With probability $1-p$, it waits for the next time slot and senses again. If the medium is busy, it waits and senses again [27](#page=27). #### 3.2.1 CSMA vulnerable time The vulnerable time in CSMA, during which collisions can still occur, is primarily influenced by the **propagation time** of the signal across the network. Even with carrier sensing, a station might begin transmitting just as another station has finished sensing and the medium has become busy, but before the signal from the transmitting station has reached it [28](#page=28). --- # Wireless local area networks and collision avoidance This section details wireless local area networks (WLANs), the challenges they face, and the mechanisms employed to manage them, primarily focusing on Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) and its related techniques [33](#page=33) [34](#page=34). ### 4.1 Introduction to wireless LANs The popularity of the Internet and the increasing demand for mobility have driven the widespread adoption of wireless local area networks (WLANs). Unlike wired networks, wireless environments present unique challenges for data transmission and collision detection [33](#page=33) [34](#page=34). ### 4.2 The hidden terminal problem A significant issue in wireless networks is the "hidden terminal problem". This problem arises when two nodes can communicate with a central access point (AP), but cannot directly communicate with each other due to distance or obstructions. In such scenarios, a node might transmit data, unaware that another node is also transmitting, leading to a collision at the AP that neither of the transmitting nodes can detect. This makes collision detection mechanisms like Carrier Sense Multiple Access with Collision Detection (CSMA/CD), commonly used in wired networks, ineffective in wireless environments [34](#page=34). > **Tip:** The hidden terminal problem is a critical distinction between wired and wireless network design, necessitating different medium access control strategies. ### 4.3 Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) To address the limitations of collision detection in wireless networks and mitigate issues like the hidden terminal problem, Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) was developed. CSMA/CA is a protocol that aims to avoid collisions by implementing several mechanisms [35](#page=35): 1. **Interframe Space (IFS):** Before transmitting, a station waits for a specific period of time known as an Interframe Space (IFS). Different IFS durations are used to prioritize traffic and manage access [35](#page=35). 2. **Contention Window (CW):** If the medium is sensed idle after the IFS, the station draws a random backoff time from a contention window (CW). The size of the CW determines the range of random backoff times. A smaller CW leads to more frequent transmissions and potentially more contention, while a larger CW reduces contention but increases waiting times [35](#page=35). 3. **Request to Send/Clear to Send (RTS/CTS):** This is a specific mechanism designed to solve the hidden terminal problem [35](#page=35) [36](#page=36). #### 4.3.1 RTS/CTS mechanism The Request to Send/Clear to Send (RTS/CTS) mechanism provides a more robust way to manage access and prevent collisions, particularly in the presence of hidden terminals. The process works as follows [36](#page=36): * A station intending to transmit first sends a small RTS (Request to Send) frame to the intended recipient (e.g., the access point) [36](#page=36). * Upon receiving the RTS, if the recipient is ready to receive, it sends back a CTS (Clear to Send) frame [36](#page=36). * Both the RTS and CTS frames contain information about the duration of the upcoming data transmission. * Any other station that overhears either the RTS or CTS frame will defer its transmission for the duration specified in these frames, effectively preventing it from transmitting and causing a collision while the actual data transfer is in progress. This ensures that stations that might be hidden from each other but can hear the AP (which can hear both) are informed about the ongoing transmission [36](#page=36). > **Example:** Consider three nodes: Node A, Node B, and an Access Point (AP). Node A can communicate with the AP, and Node B can communicate with the AP, but Node A and Node B cannot directly communicate with each other (hidden terminal problem). > 1. Node A wants to send data to the AP. > 2. Node A sends an RTS to the AP. > 3. Node B is within hearing range of the AP and overhears the RTS. Node B knows a transmission is about to occur and defers its own transmission. > 4. The AP receives the RTS and sends a CTS back to Node A. > 5. Node B is also within hearing range of the AP and overhears the CTS. Node B continues to defer its transmission. > 6. Node A receives the CTS and proceeds to send its data frame to the AP. > 7. Both Node A and Node B have avoided a collision at the AP. #### 4.3.2 CSMA/CA control logic The overall control logic for CSMA/CA involves sensing the medium, waiting for the appropriate IFS, performing a random backoff if necessary, and potentially using RTS/CTS for explicit channel reservation. If a transmission is successful, the station enters a listening state. If a collision is detected (or inferred through timeouts), the CW size may be increased, and the backoff process is repeated [37](#page=37). ### 4.4 IEEE 802.11 standard The IEEE 802.11 project is the standard that defines wireless local area networking (WLAN). This standard incorporates CSMA/CA and its associated mechanisms to ensure reliable data communication in unlicensed radio frequency bands. The standard has evolved over time with various amendments (e.g., 802.11a, 802.11b, 802.11g, 802.11n, 802.11ac) to improve data rates, range, and efficiency [35](#page=35) [38](#page=38). --- ## Common mistakes to avoid - Review all topics thoroughly before exams - Pay attention to formulas and key definitions - Practice with examples provided in each section - Don't memorize without understanding the underlying concepts

| Term | Definition | |------|------------| | Data Link Layer | The second layer of the OSI model, responsible for reliable data transfer between nodes on a network segment. It handles physical addressing, framing, and error detection. | | Local Area Network (LAN) | A computer network that interconnects computers within a limited area such as a residence, school, laboratory, university campus or office building. | | Shared Medium | A network medium that is used by multiple devices simultaneously, requiring mechanisms to manage access and prevent collisions. | | Network Topology | The arrangement of the elements (links, nodes, etc.) of a communication network. Common topologies include bus, ring, star, and mesh. | | Ethernet | A family of wired computer networking technologies commonly used in local area networks (LAN), metropolitan area networks (MAN) and wide area networks (WAN). | | Medium Access Control (MAC) | A sublayer of the Data Link Layer that controls how network devices gain access to a shared transmission medium and transmits data. | | CSMA/CD (Carrier Sense Multiple Access with Collision Detection) | A network protocol that listens to the communication channel before transmitting and detects if a collision has occurred after transmission, aborting if necessary. | | ALOHA | A random-access method for sharing a broadcast channel, allowing multiple users to transmit data packets at any time. It is known for its simplicity but can lead to collisions. | | Pure ALOHA | A variant of ALOHA where stations can transmit frames at any time, leading to a higher probability of collisions. | | Slotted ALOHA | An improvement over Pure ALOHA where time is divided into discrete slots, and stations can only transmit at the beginning of a slot, reducing collision probability. | | Throughput | The rate at which data is successfully transferred over a network connection, often expressed as bits per second. | | Backoff Time | A random waiting period implemented by network protocols after a collision before retransmitting data, to reduce the likelihood of repeated collisions. | | CSMA (Carrier Sense Multiple Access) | A protocol that determines when to transmit a data packet on a network medium by first sensing whether the medium is in use. | | Collision Detection | The process of identifying when two or more devices transmit data simultaneously on a shared network medium, causing data corruption. | | CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) | A protocol used in wireless networks that attempts to avoid collisions before they happen, often by using mechanisms like acknowledgments and contention windows. | | Hidden Terminal Problem | A situation in wireless networking where two nodes can communicate with an access point but not with each other, making collision detection difficult. | | RTS/CTS (Request to Send/Clear to Send) | A mechanism used in wireless networks to mitigate the hidden terminal problem by allowing nodes to reserve the medium before transmitting data. | | IEEE 802.11 | A set of media access control and error-checking protocols for digital network communications commonly employed in wireless local area networks (WLANs). | | Ethernet Frame | A data packet format used in Ethernet networks, typically containing source and destination MAC addresses, type/length information, payload data, and a frame check sequence. | | MAC Address | A unique identifier assigned to network interfaces for communications at the data link layer of a network segment. |