Chapter 2: Data Link Layer - PDF

Chair of Distributed Systems and Security School of Computation, Information and Technology Technical University of Munich Computer Networking and IT Security (CNS) INHN0012 – WiSe...

Chair of Distributed Systems and Security School of Computation, Information and Technology Technical University of Munich Computer Networking and IT Security (CNS) INHN0012 – WiSe 2024/25 Prof. Dr.-Ing. Stephan Günther Chair of Distributed Systems and Security School of Computation, Information and Technology Technical University of Munich Saturday 2nd November, 2024 14:49 Chapter 2: Data link layer Representation of networks as graphs Characterizing connections, multiple access, and access control Framing, addressing, and error detection Connecting nodes on Layers 1 and 2 Security Considerations Summary References Chapter 2: Data link layer 2-1  Chapter 2: Data link layer Placement in the ISO/OSI model Horizontal communication 7 Application Layer 7 Application Layer Vertical communication 6 Presentation Layer 6 Presentation Layer 5 Session Layer 5 Session Layer 4 Transport Layer 4 Transport Layer 3 Network Layer 3 Network Layer 2 Data Link Layer 2 Data Link Layer 1 Physical Layer 1 Physical Layer Transmission channel (copper, ber optics, radio) Chapter 2: Data link layer 2-2 Chapter 2: Data link layer We rst deal with local area networks (LANs), i. e. all attached nodes can be reached directly and are accessible by means of (mostly) unstructured addresses on layer 2, there is no routing, relaying messages based on layer 2 addresses (“bridging” and “switching”) is, however, possible. Examples: Individual local networks (connections via bus / hub, but also by means of switches) Connection between a base station and a cellular phone Bus systems within a computer, e. g. USB, PCI, etc. Chapter 2: Data link layer 2-3 Chapter 2: Data link layer The essential tasks of the Data-Link Layer are media access control, error detection of transmitted frames, and addressing within the directly connected network. Media access control: Hubs create a star topology only at a rst glance All attached computer are internally connected to a single bus Concurrent transmissions result in collisions and loss of frames Chapter 2: Data link layer 2-4 Chapter 2: Data link layer The essential tasks of the Data-Link Layer are media access control, error detection of transmitted frames, and addressing within the directly connected network. Error detection: 00101 01001 Transmission errors occur despite channel coding 11001 11000 These must be detected 10101 11011 Defective messages must not be forwarded to higher layers Retransmission of defective or missing frames is sometimes left to higher lay- ers Chapter 2: Data link layer 2-4 Chapter 2: Data link layer The essential tasks of the Data-Link Layer are media access control, error detection of transmitted frames, and addressing within the directly connected network. Addressing within local area networks: ? A frame may be received by multiple nodes, e. g. in case of a bus or wireless network Receivers must decide to whom a frame was addressed Chapter 2: Data link layer 2-4 Chapter 2: Data link layer Representation of networks as graphs Directed graphs Undirected graphs Paths in networks Network topologies Adjacency and distance matrix Creating tree structures Characterizing connections, multiple access, and access control Framing, addressing, and error detection Connecting nodes on Layers 1 and 2 Security Considerations Summary Chapter 2: Data link layer 2-5 Directed graphs Motivation Directed or undirected graphs are commonly used to represent network topologies and node connections. In the following, we introduce the corresponding notation and basic terms. An asymmetric network can be represented as directed graph G = (N ,A) with N denoting the set of nodes (Nodes or vertices) and A = {i,j } | i,j ∈ N ∧ i , j are connected by a directed arc} denoting the set of directed arcs. Example: N = {1,2,3,4}, A = {(1,2),(2,3),(2,4),(1,4)} 1 2 4 3 Chapter 2: Data link layer — Representation of networks as graphs 2-6 Undirected graphs A symmetric network can be represented as undirected graph G = (N ,E ) with N denoting the set of nodes and E = {{i,j } | i,j ∈ N ∧ i , j are connected undirectedly} denoting the set of (undirected) edges. Beispiel: N = {1,2,3,4}, E = {{1,2},{2,3},{2,4},{1,4}} 1 2 4 3 Note: Undirected graphs can be understood as directed graphs with symmetric arcs. An edge {i,j } of an undirected graph with weight (cost) cij thus corresponds to the two arcs (i,j) and (j,i) of a direcgted graph with weights (consts) cji = cij. cij cij i j i j cji = cij Chapter 2: Data link layer — Representation of networks as graphs 2-7 Paths in networks Paths can be represented in graphs: A path between two nodes1 s,t ∈ N is a set Pst = {(s,i),(i,j),... ,(k ,l),(l,t)} of edges that connect s and t with each other over a number of intermediate nodes.  A path’s cost is the sum of the costs of the used edges: c(Pst ) = cij. (i,j)∈Pst A path’s length is the number of intermediate nodes: l(Pst ) = |Pst |. On Layer 3 we refer to the path costs as hop count, which is not common on Layer 2. Example: P15 = {(1,4),(4,2),(2,5)} 4 2 5 1 1 1 3 1 4 4 1 3 c(P15 ) = 3 + 1 + 4 = 8, l(P15 ) = 3 1 Source and destination (terminal) are commonly denoted as s and t , respectively. Chapter 2: Data link layer — Representation of networks as graphs 2-8 Network topologies The topology describes the structure how nodes are connected with each other. We differentiate between physical and logical topology. Well-known topologies: Point-to-point i j Chain 1 2... N Star 7 8 6 1 z 5 2 4 3 Chapter 2: Data link layer — Representation of networks as graphs 2-9 Network topologies Mesh 2 3 5 4 1 Tree (mostly a logical topology) 2 2 3 3 5 5 4 4 1 1 Bus 1 3 2 Chapter 2: Data link layer — Representation of networks as graphs 2-10 Adjacency and distance matrix Adjacency matrix Networks can easily represented as matrices. The adjancency matrix  1 ∃(i,j) ∈ A N ×N A = (a)ij = , ∀i,j ∈ N , A ∈ {0,1} 0 otherwise denotes whether node i is directlly connected to node j. Example: 2 5  0 1 1 1 0  1 0 0 1 1 A=  1 0 0 1 0    1 4 1 1 1 0 1 0 1 0 1 0 3 The element aij of A is 1 if there is a connection from node i to node j. A is symmetric (A = A T ) if for each arch (i,j) there is also an anti-paralell arc (j,i). Chapter 2: Data link layer — Representation of networks as graphs 2-11 Adjacency and distance matrix Distance matrix The Distance matrix  cij ∃(i,j) ∈ A N ×N D = (d)ij = 0 wenn i = j , ∀i,j ∈ N , D ∈ R0+ ∞ sonst contains the costs of paths of length 1 between all pairs of nodes. Example: 4 2 5  0 1 4 3  ∞ 1 1 1 1 0 ∞ 1 4 D =  4 0 1  3  ∞ ∞  1 4 3 1 1 0 1 ∞ 4 ∞ 1 0 4 1 3 The element dij of D denotes the distance between i and j. If there is no direct connection between i and j , then we have that dij = ∞. D ist symmetric, if the network is symmetric, i. e., for each arc (i,j) there is an anti-parallel arc (j,i) with the same costs. Chapter 2: Data link layer — Representation of networks as graphs 2-12 Adjacency and distance matrix Question: How do we obtain a matrix that denotes the costs of the shortest path between each pair of nodes? Chapter 2: Data link layer — Representation of networks as graphs 2-13 Adjacency and distance matrix Question: How do we obtain a matrix that denotes the costs of the shortest path between each pair of nodes? Answer: Calculate powers of D with respect to the min-plus product n n −1 n  n −1  D =D ⊗ D with dij = min dik + dkj. k ∈N The n-th power D n contains the costs of the shortest path between each pair of nodes over a distance of at most n hops. The power series converges for a nite n ∈ N, i. e., D n+1 = D n = D ∗. Chapter 2: Data link layer — Representation of networks as graphs 2-13 Adjacency and distance matrix Question: How do we obtain a matrix that denotes the costs of the shortest path between each pair of nodes? Answer: Calculate powers of D with respect to the min-plus product n n −1 n  n −1  D =D ⊗ D with dij = min dik + dkj. k ∈N The n-th power D n contains the costs of the shortest path between each pair of nodes over a distance of at most n hops. The power series converges for a nite n ∈ N, i. e., D n+1 = D n = D ∗. Example: How we obtain the element (1,5) of D 2 ? 4  0 1 4 3 ∞  2 5 1 1 1 1 0 ∞ 1 4 D=  4 0 1  3  ∞ ∞  1 4 3 1 1 0 1 ∞ 4 ∞ 1 0 4 1 3 Row 1 denotes the costs of the shortest path of length 1 hop from node 1 to each other note. Column 5 denotes the costs by which node 5 can be reached by each other node over a path of at most 1 hop. Chapter 2: Data link layer — Representation of networks as graphs 2-13 Adjacency and distance matrix How often do we have to multiply? The power n such that D n = D n+1 = D ∗ is upper bounded by the longest simple path in the network. The longest simple path in turn is bounded above by the number of nodes N. ⇒n 1 (channel is fully and perfectly utilized). Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-30 ALOHA and slotted ALOHA Variant: With slotted ALOHA nodes must no longer start transmitting at arbitrary points in time but only at multiples of transmission intervals t = nT for n = 0,1,... Station A Station B Station C Station D Station E Kollision Kollision t −λ The critical time frame is reduced from 2T to T ⇒ S = λ · e p0 = S 1.0 optimal media access 0.8 0.6 Efciency: ∼ 37 % 0.4 Slotted ALOHA 0.2 ALOHA λ 0.5 1.0 1.5 2.0 2.5 Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-31 CSMA, CSMA/CD, CSMA/CA Carrier sense multiple access (CSMA) A simple improvement over slotted ALOHA: “listen before talk” Listen for ongoing transmissions on the medium Start transmitting only when the medium is idle Different variants: 1-persistent CSMA 1. If medium idle, start transmitting 2. If medium busy, wait until it becomes free and start in the following time slot p -persistent CSMA 1. If medium idle, start transmitting with probability p or delay the transmission with probability 1 − p by one time slot – then continue with 1. 2. If medium busy, wait until it becomes idle – then continue with 1. non-persistent CSMA 1. If medium idle, start transmitting 2. If medium busy, wait a random amount of slot times – then continue with 1. Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-32 CSMA, CSMA/CD, CSMA/CA Comparison of all approaches discussed so far Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-33 CSMA, CSMA/CD, CSMA/CA CSMA/CD (collision detection) Detect collisions and repeat the transmission if necessary A transmission is assumed to be successful if it is completed without errors, i. e., no collision is detected while transmitting Since no acknowledgements are used, the scheme is only suitable if the probability of random transmission errors is sufciently small Problem: The transmitter must be able to detect the collision while it is still transmitting. Prerequisites for CSMA/CD Assuming that two stations i and j communicate over a distance d using CSMA/CD. In order that collisions can be detected, the messages must be at least of size 2d Lmin = r. ν c0 i j i j Lmin  r al al Jam sign Jam sign t t Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-34 CSMA, CSMA/CD, CSMA/CA If we use 1-persistent CSMA with collision detection, the following problem occurs: The collision destroys both messages involved. At least one of the stations transmits a jam signal. When the medium becomes idle again, both stations concurrently start the retransmission. ⇒ The messages collide again Solution: Wait a “random” number of time slots if the previous transmission caused a collision Binary exponential backoff At the k -th attempt to transmit a specic message   the transmitter chooses a random number n ∈ 0,... , min{2k −1 − 1,1023} and delays the retransmission by n time slots. When the medium becomes busy in the mean time, the counter is stopped and resumed when the medium becomes idle again. By these random delays that increase in case of consecutive collisions (which corresponds to a high load on the channel / large λ), the probability of further collisions is reduced. Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-35 CSMA, CSMA/CD, CSMA/CA CSMA/CA (collision avoidance) In wireless networks, CSMA/CD cannot be used since the transmitter may be unable to detect a collision in every situation. „Hidden station“: Nodes i and j transmit at the same time Node c detects the collision i c j But neither i nor j detect the collision since they are out of range CSMA/CA is based on p -persistent CSMA, i. e., 1. If the medium is idle, start transmitting with probability p or delay the transmission with probability 1 − p for one slot time – then continue with 1. 2. If the medium is busy, wait until it becomes idle – then continue with 1. Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-36 CSMA, CSMA/CD, CSMA/CA Case study: IEEE 802.11 DCF (distributed coordination function) Fixed time interval between frames: DIFS (DCF interframe spacing). If the medium is idle for at least a DIFS period, uniformely and independently draw a number of backoff slots from    the set 0,1,2,... , min 2c+k −1 − 1,255 by which the transmission is deferred. c depends on the actual PHY (physical layer implementation), e. g. c = 4, k denotes the number of transmission attempts. DIFS Contention window SIFS Busy medium Backoff slots Next frame Slot time Defer access Backoff interval Figure 3: IEEE 802.11 DCF Since c > 0, we always have a contention window (main difference to Ethernet). With IEEE 802.11, a transmission is assumed to be successful in the following cases: for unicasts the receiver transmits an acknowledgement after SIFS (which is shorter than DIFS) ⇒ no other node may start transmitting after this time for multicasts and broadcasts, the transmission is assumed to be successful if no errors were detected during transmission (in general, a station does not know from whom to expect acknowledgements, and acknowledgements from multiple stations may cause collisions themselves) Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-37 CSMA, CSMA/CD, CSMA/CA Optional extension: RTS/CTS (request to send / clear to send) In infrastructure mode, transmissions are controlled by a base station (access point) Before a node may start a transmission, it transmits an RTS to the base station Only if the space station answers by CTS, a transmission may begin Example: A transmits a RTS that may in general not be received RTS 1. by B due to the distance. A AP B The base station answers with a CTS that is received CTS CTS 2. by both A and B , making B aware that a transmission is about to start A AP B A may start transmitting while B has to wait a dened 3. time period before it is even allowed to transmit a RTS. A AP B Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-38 CSMA, CSMA/CD, CSMA/CA Optional extension: RTS/CTS (request to send / clear to send) Advantage: Collisions and the effect of hidden stations are reduced but not fully prevented. Disadvantages: There may still be collisions, e. g. if B does not overhear the CTS. RTS/CTS takes some additional time before a transmission may begin, thus reducing the achievable data rate under optimal conditions. Notes: RTS/CTS is part of the so called virtual carrier sensing since the medium is reserved for a specic duration. To reduce the loss probability for RTS/CTS messages, these are transmitted at the most robust modulation and coding scheme, i. e., the lowest supported data rate. This does not hurt much since these messages are very small. All devices receiving a CTS should consider the medium busy for the respective time frame, independent on whether or not they belong to the same service set2 2 The term “service set” denotes a group of IEEE 802.11 devices communicating with each other – informally speaking: being associated with the same AP. Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-39 Token Passing Idea: collision-free operation by forwarding a token in a ring 7 Stations are connected to a logical ring. 8 6 A token circulates through the ring by passing it on from node to node. 1 5 If a stations wants to transmit a message, it waits until it obtains the token. After transmitting a message, the token ist passed on again. 2 4 3 Receiving messages: A message is passed through the ring just like the token. The receiver marks the message as read and passes it on. When the message arrives again at the transmitter, it removes the message and instead passes on the token. What happens if the token is „lost“? There is a monitor station that is somehow elected, e. g. the station with the (numerically interpreted) largest address. That monitor station creates a new token when needed and removes endless circulating message or duplicate tokens. If the monitor station is removed, the remaining stations elect a new monitor station. Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-40 Token Passing Advantages: No retransmissions due to collisions There is a guaranteed maximum delay until a node can start transmitting (determinism) Disadvantages and problems: If the token is lost, it must be replaces → one station needs to take over responsibility (Monitor-Station). Defective or selsh behavior of a node may impact the whole network. The transmission delay may be larger compared to CSMA since a transmitter has to wait for the token. Creating the ring topology can be complex. Usage nowaday: Token Ring (IEEE 802.5) has been completely replaced by Ethernet (IEEE 802.3). FDDI (Fiber Distributed Data Interface) is a collective term for ber optical rings up to a distance of several hundred km. The are, for instance, used as backbone by local service providers in metropolitan scales. Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-41 Summary In this subchapter we learned about different dynamic approaches for time division multiple access. In contrast to static time division multiplex the available channel bandwidth is not exclusively reserved for inactive nodes. Competitive access: ALOHA and Slotted ALOHA CSMA (non-persistent, 1-persistent, p -persistent) CSMA/CD (collision detection) IEEE 802.3 Ethernet CSMA/CA (collision avoidance) IEEE 802.11 WLAN Controlled access: CSMA/CA with RTS/CTS IEEE 802.11 WLAN Token Passing (collision prevention) IEEE 802.5 Token Ring, Fiber Distributed Data Interface (FDDI) Chapter 2: Data link layer — Characterizing connections, multiple access, and access control 2-42 Chapter 2: Data link layer Representation of networks as graphs Characterizing connections, multiple access, and access control Framing, addressing, and error detection Frame boundary detection and code transparency Addressing and error detection Connecting nodes on Layers 1 and 2 Security Considerations Summary References Chapter 2: Data link layer 2-43 Framing, addressing, and error detection Motivation So far we have only talked about messages without thinking about their format. From the point of view of the physical layer, a message is just a sequence of bits. However, this conception is no longer sufcient for a consideration of the data link layer. In the following, we will consider how individual messages can be kept apart, what additional information link layer protocols require, and how transmission errors that occur despite channel coding can be detected. In the context of the data link layer we refer to messages as frames. Chapter 2: Data link layer — Framing, addressing, and error detection 2-44 Frame boundary detection and code transparency Detection 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 Frame n Frame n + 1 How can the receiver detect frames, especially if frames have different sizes and there is not constant user data on the line (idle periods)? Chapter 2: Data link layer — Framing, addressing, and error detection 2-45 Frame boundary detection and code transparency Detection 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 Frame n Frame n + 1 How can the receiver detect frames, especially if frames have different sizes and there is not constant user data on the line (idle periods)? There are many approaches: Length specication of payload Control characters (start / end) Boundary elds and “bit stufng” Code rule violation The goal of all these procedures is to maintain code transparency, i. e., to allow the transmission of arbitrary strings. Chapter 2: Data link layer — Framing, addressing, and error detection 2-45 Frame boundary detection and code transparency Length specication of payload At the beginning of the frame is the length of the following payload (or the total length of the frame). Prerequisite: the length eld and thus the beginning of a message must be clearly recognizable 30 B Data 60 B Data How can the beginning of a frame be detected? Chapter 2: Data link layer — Framing, addressing, and error detection 2-46 Frame boundary detection and code transparency Length specication of payload At the beginning of the frame is the length of the following payload (or the total length of the frame). Prerequisite: the length eld and thus the beginning of a message must be clearly recognizable 30 B Data 60 B Data How can the beginning of a frame be detected? Control characters (start / ende) Prepend bounding elds Due to loss of the carrier signal between the frames (code rule violation, see Chapter 1) Chapter 2: Data link layer — Framing, addressing, and error detection 2-46 Frame boundary detection and code transparency Control characters In Chapter 1 we got to know the 4B5B code which is used in combination with line codes like MLT-3 on the physical layer. Each 4 bit input is mapped to 5 bit output A frame is preceded by the start symbols J/K After a frame the end symbols T/R are inserted Input Output Meaning Input Output Meaning 0000 11110 hex data 0 - 00000 quiet (signal loss) 0001 01001 hex data 1 - 11111 idle (pause) 0010 10100 hex data 2 - 11000 start #1 (J) 0011 10101 hex data 3 - 10001 start #2 (K) 0100 01010 hex data 4 - 01101 end (T) 0101 01011 hex data 5 - 00111 reset (R)......... - 11001 set 1111 11101 hex data F - 00100 halt Example: Input: 1011 0101 0110 Output: 11000 10001 10111 01011 01110 01101 00111 start #1 start #2 data data data end reset Chapter 2: Data link layer — Framing, addressing, and error detection 2-47 Frame boundary detection and code transparency Control characters are not only used on layers 1 and 2. On layer 6 (presentation layer), the ASCII code (American Standard Code for Information Interchange) is used (7 bit code words): ASCII (hex) Character ASCII (hex) Character ASCII (hex) Character ASCII (hex) Character 00 NUL 20 SP 40 @ 60 ˋ 01 SOH 21 ! 41 A 61 a 02 STX 22 " 42 B 62 b 03 ETX 23 # 43 C 63 c 04 EOT 24 $ 44 D 64 d 05 ENQ 25 % 45 E 65 e 06 ACK 26 & 46 F 66 f 07 BEL 27 ' 47 G 67 g 08 BS 28 ( 48 H 68 h 09 TAB 29 ) 49 I 69 i 0A LF 2A * 4A J 6A j 0B VT 2B + 4B K 6B k 0C FF 2C , 4C L 6C l 0D CR 2D - 4D M 6D m 0E SO 2E. 4E N 6E n 0F SI 2F / 4F O 6F o 10 DLE 30 0 50 P 70 p 11 DC1 31 1 51 Q 71 q 12 DC2 32 2 52 R 72 r........................ Chapter 2: Data link layer — Framing, addressing, and error detection 2-48 Frame boundary detection and code transparency What if control characters occur randomly in the payload data? 1. In the case of the 4B5B code, this cannot happen: 4 bit data words are injectively mapped to 5 bit code words Some of the remaining 5 bit code words are used as control characters 2. The ASCII-Code is merely an interpretation rule: Some code words represent text characters (digits, numbers,... ), others are control characters To be able to transmit a control character as a date, this is marked by a special control character: escape character If this special control character itself is to be transmitted, it is doubled This procedure is called character stufng Mostly code transparency is taken care of automatically, so users do not have to worry about it. This is not true for programming languages. System.out.println("A \" must be escaped"); Within the string to be output, quotes must be escaped using a backslash. More examples: Bash (Ctrl+C) Text editors (Emacs, vim) Chapter 2: Data link layer — Framing, addressing, and error detection 2-49 Frame boundary detection and code transparency Bounding elds and bit stufng Mark start and end of a message with a specic bit sequence Make sure that the marker does not occur randomly in the payload data (“bit stufng”) Example: Let 01111110 be the start / end marker To prevent the marker from appearing in payload data, insert after ve consecutive 1 bits a 0 bit in the payload Input: 1100101111110111111 Output: 01111110 110010111110101111101 01111110 Receiver removes the following 0 bit after ve consecutive 1 bits. Used e. g. by HDLC (High Level Data Link Control), layer 2 protocol for serial lines. Chapter 2: Data link layer — Framing, addressing, and error detection 2-50 Frame boundary detection and code transparency Code rule violation Many line codes (e. g. Return-to-Zero and Manchester) have certain changes in signal levels independent of the actual data being transmitted. Idea: Omit certain signal changes In this way an invalid symbol (not existing in the code) is created This can be used to mark the start and end of frames. Example: Manchester code Frame: 11001 Code rule violation Chapter 2: Data link layer — Framing, addressing, and error detection 2-51 Frame boundary detection and code transparency Case studies IEEE 802.3a/i (Ethernet): 10 Mbit/s The Manchester code is used as line code The end of a frame is indicated by code rule violation IEEE 802.3u (FastEthernet): 100 Mbit/s MLT-3 is used as line code in combination with 4B5B encoding Start and end of frames are marked by control characters of the 4B5B code IEEE 802.3z (Gigabit Ethernet over ber): 1000 Mbit/s NRZ is used as line code in combination with 8B10B encoding Start and end of frames are marked by control characters of the 8B10B code IEEE 802.3ab (Gigabit Ethernet over copper) uses another line codes since the attenuation would be too large with NRZ In addition, in all these examples, each frame is still preceded by a preamble (see Chapter 1). This also ensures clock synchronization between transmitter and receiver, even when using the MLT-3 code. Chapter 2: Data link layer — Framing, addressing, and error detection 2-52 Addressing and error detection So far, we know how a binary data stream is transmitted and how the receiver recognizes frame boundaries. However, we do not yet know how the payload coming from layer 3 and higher is handled by the data link layer, how the receiver of a frame is addressed, and how a frame is created from the payload (service data unit) and protocol-specic information. Remark: All of the following concepts are explained using the IEEE 802 standards. The main points are transferable to other protocols with minor modications. Chapter 2: Data link layer — Framing, addressing, and error detection 2-53 Addressing and error detection Addressing in local area networks: All nodes can be reached directly There is no routing Requirements for addresses on layer 2: Unique identication of nodes within the respective local area network Usually there is a broadcast address, which addresses all nodes in the respective local area network In addition, there may be multicast addresses1 , which address certain groups of nodes Addresses on layer 2 are generally referred to as MAC addresses, where MAC stands for media access control. Example: RA TA (Control) L3 PDU (data) (RA = receiver address, TA = transmitter address)2 1 Multicast addresses are handled like broadcasts in many cases on layer 2. However, they are extensively used in switched networks when IPv6 is used on layer 3. 2 Since MAC addresses only address the next hop in each case, we avoid talking about source and destination addresses. Chapter 2: Data link layer — Framing, addressing, and error detection 2-54 Addressing and error detection MAC addresses of all IEEE 802 standards (e. g. Ethernet, WLAN, Bluetooth) have the following structure: RA TA (Control) L3 PDU (data) Offset in B 0 1 2 3 4 5 OUI Device ID bit 7 6 5 4 3 2 1 0 0: unicast 1: multicast 0: global unique 1: locally administered Network cards have a MAC address stored in the ROM (read-only memory). Separation into OUI (organizationally unique identier) and device ID enables network card manufacturers to assign unique MAC addresses. Consequently, the manufacturer of a network card can be identied by its MAC address (e. g. 7c:6d:62 =ˆ Apple). The broadcast address is dened as ff:ff:ff:ff:ff:ff (“all ones”). Whether an address is a unicast or multicast address is determined by the lowest order bit of the rst octet. Remark: For certain applications, it makes sense to dispense with cross-vendor uniqueness, e. g. virtualized network adapters. For this purpose the so called local-administrated addresses (second bit of the rst octet) are provided for this purpose. Chapter 2: Data link layer — Framing, addressing, and error detection 2-55 Addressing and error detection Error detection Despite channel coding, transmission errors (bit errors) can occur. It can therefore happen that an incorrect payload is forwarded to higher layers. To further reduce the probability of such errors, additional error-detecting codes are used (so-called checksums): In contrast to channel coding (error-correcting codes), the checksum of a layer 2 protocol is usually not used for error correction but only for error detection. Chapter 2: Data link layer — Framing, addressing, and error detection 2-56 Addressing and error detection Cyclic redundancy check (CRC) Unlike error-correcting codes (channel codes, Chapter 1), CRC is a family of codes used primarily for error detection. The following objectives are pursued with their use: A large number of errors (single-bit, multi-bit, burst errors) should be detected. The amount of added redundancy should be small. Errors should primarily be detected, not corrected. Chapter 2: Data link layer — Framing, addressing, and error detection 2-57 Addressing and error detection Cyclic redundancy check (CRC) Unlike error-correcting codes (channel codes, Chapter 1), CRC is a family of codes used primarily for error detection. The following objectives are pursued with their use: A large number of errors (single-bit, multi-bit, burst errors) should be detected. The amount of added redundancy should be small. Errors should primarily be detected, not corrected. Basics: A data word of length n bit can be represented by a polynomial n −1  i a(x) = ai x mit ai ∈ F2 mit F2 = {0,1}. i=0 All data words of length exactly n bit constitute the set   n −1  Fq [x] =  a  a(x) =  i ai x , ai ∈ F2. i=0 Together with appropriately dened addition and multiplication a so calles nite extension eld ⟨Fq [x], + ,·⟩ with q = 2n elements is formed, on which the usual rules for addition and multiplication apply. Chapter 2: Data link layer — Framing, addressing, and error detection 2-57 Addressing and error detection What means “appropriately dened”? Summation: For the some of a,b ∈ Fq [x] we dene n −1  i c(x) = a(x) + b(x) = (ai + bi ) x , i=0 where the sum ai + bi of coefcients is dened according to the rules of GF(2)2 , i. e., the sum of two data words is the bitwise XOR. 2 Galois eld, nite eld (cmp. Discrete Structures) Chapter 2: Data link layer — Framing, addressing, and error detection 2-58 Addressing and error detection What means “appropriately dened”? Summation: For the some of a,b ∈ Fq [x] we dene n −1  i c(x) = a(x) + b(x) = (ai + bi ) x , i=0 where the sum ai + bi of coefcients is dened according to the rules of GF(2)2 , i. e., the sum of two data words is the bitwise XOR. Multiplication: Multiplication is more complex since the degree of d(x) = a(x) · b(x) can be larger than n − 1 and therefore d(x) ∈ ◁ Fq [x]. We thus choose a reduction polynomial r(x) with grad(r(x)) = n and dene the product of a,b ∈ Fq [x] as d(x) = (a(x) · b(x)) mod r(x). This corresponds to a normal polynomial multiplication (where the addition corresponds to an XOR-connection) followed by a modulo operation over r(x). The modulo operation corresponds to a polynomial division with the remainder as result. This ensures that grad(d(x)) < n. 2 Galois eld, nite eld (cmp. Discrete Structures) Chapter 2: Data link layer — Framing, addressing, and error detection 2-58 Addressing and error detection Example: F4 [x] = {0,1,x,x + 1} with r(x) = x 2 + x + 1. Is r(x) irreducible, i. e., it cannot be represented as product of two polynomials with degree strictly less than n (n = 2 in this example)? Chapter 2: Data link layer — Framing, addressing, and error detection 2-59 Addressing and error detection Example: F4 [x] = {0,1,x,x + 1} with r(x) = x 2 + x + 1. Is r(x) irreducible, i. e., it cannot be represented as product of two polynomials with degree strictly less than n (n = 2 in this example)? ⊙ 0 1 x x+1 0 0 1 0 1 x 0 x x2 x+1 0 x+1 x2 + x „x 2 + 2x + 1“ = x 2 + 1 Addition over F4 [x] is equivalent to addition over F2 between monomials of the same degree. ⇒ Yes, r(x) is irreducible since it cannot be represented as product a ⊙ b with a,b ∈ F4 [x]. Chapter 2: Data link layer — Framing, addressing, and error detection 2-59 Addressing and error detection Example: F4 [x] = {0,1,x,x + 1} with r(x) = x 2 + x + 1. Is r(x) irreducible, i. e., it cannot be represented as product of two polynomials with degree strictly less than n (n = 2 in this example)? ⊙ 0 1 x x+1 0 0 1 0 1 x 0 x x2 x+1 0 x+1 x2 + x „x 2 + 2x + 1“ = x 2 + 1 Addition over F4 [x] is equivalent to addition over F2 between monomials of the same degree. ⇒ Yes, r(x) is irreducible since it cannot be represented as product a ⊙ b with a,b ∈ F4 [x]. For multiplication, we need r(x) to reduce the colored results in the table above: + 0 1 x x+1 · 0 1 x x+1 0 0 0 0 1 1 0 1 0 1 x x x+1 0 x 0 x x+1 x+1 x+1 x 1 0 x+1 0 x+1 1 x Multiplication examples: 2 2 2 2 2 2 x : (x + x + 1) = 1, remainder: x + 1 (x + x) : (x + x + 1) = 1, remainder: 1 (x + 1) : (x + x + 1) = 1, remainder: x Chapter 2: Data link layer — Framing, addressing, and error detection 2-59 Addressing and error detection Remarks: If we choose an irreducible polynomial for r(x), i. e., r(x) cannot be represented as product of a,b ∈ Fq [x], then we obtain a nite eld with q = 2n elements. For CRC one usually chooses r(x) = p(x)(x + 1) with p ∈ Fq [x] as reduction polynomial of degree n: p(x) and x + 1 are elements of Fq [x] and r(x) is therefore obviously not irreducible. With this choice for r(x), ⟨Fq [x], + ,·⟩ is not a nite eld. However, this choice allows to detect all bit errors of odd number. The choice of r(x) determines not only the length of the checksum but also the error detection properties. Chapter 2: Data link layer — Framing, addressing, and error detection 2-60 Addressing and error detection Remarks: If we choose an irreducible polynomial for r(x), i. e., r(x) cannot be represented as product of a,b ∈ Fq [x], then we obtain a nite eld with q = 2n elements. For CRC one usually chooses r(x) = p(x)(x + 1) with p ∈ Fq [x] as reduction polynomial of degree n: p(x) and x + 1 are elements of Fq [x] and r(x) is therefore obviously not irreducible. With this choice for r(x), ⟨Fq [x], + ,·⟩ is not a nite eld. However, this choice allows to detect all bit errors of odd number. The choice of r(x) determines not only the length of the checksum but also the error detection properties. Back to CRC CRC calculates a checksum of xed length for a given data block (e. B. L2-PDU). Code words are polynomials a ∈ Fq [x]. The degree n of the reduction polynomial r(x) determines the maximum degree n − 1 of valid code words a ∈ Fq [x] and which types of errors (single-bit, multi-bit, burst errors) can be detected. Ethernet uses CRC32 with the reduction polynomial 32 26 23 22 16 12 11 10 8 7 5 4 2 r(x) = x +x +x +x +x +x +x +x + x + x + x + x + x + x + 1. Chapter 2: Data link layer — Framing, addressing, and error detection 2-60 Addressing and error detection How does CRC work? Suppose we have a reduction polynomial r(x) of degree n and a message m(x) of degree k , i. e. the message consists of k + 1 bit, that is to be secured using CRC: 1. Append n zeros to m(x): m ′ (x) = m(x) · x n. 2. Determine the remainder c(x) = m ′ (x) mod r(x), which represents the checksum. 3. The message to be transmitted is s(x) = m ′ (x) + c(x). Chapter 2: Data link layer — Framing, addressing, and error detection 2-61 Addressing and error detection How does CRC work? Suppose we have a reduction polynomial r(x) of degree n and a message m(x) of degree k , i. e. the message consists of k + 1 bit, that is to be secured using CRC: 1. Append n zeros to m(x): m ′ (x) = m(x) · x n. 2. Determine the remainder c(x) = m ′ (x) mod r(x), which represents the checksum. 3. The message to be transmitted is s(x) = m ′ (x) + c(x). The receiver checks the incoming message s ′ (x) = s(x) + e(x), which may contain an error e(x) ̸= 0: 1. The remainder c ′ (x) = s ′ (x) mod r(x) = (s(x) + e(x)) mod r(x) is determined. 2. If c ′ (x) = 0, then with high probability no error occurred. If c ′ (x) ̸= 0, then there was an error for sure. Chapter 2: Data link layer — Framing, addressing, and error detection 2-61 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 1. Determine coefcients: r(x) =ˆ 1101 and m(x) =ˆ 10100101 Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 1. Determine coefcients: r(x) =ˆ 1101 and m(x) =ˆ 10100101 2. grad(r(x)) = 3 ⇒ multiply data by x 3. This corresponds to “appending” 3 zeros: m ′ (x) = m(x) · x 3 =ˆ 10100101000 Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 1. Determine coefcients: r(x) =ˆ 1101 and m(x) =ˆ 10100101 2. grad(r(x)) = 3 ⇒ multiply data by x 3. This corresponds to “appending” 3 zeros: m ′ (x) = m(x) · x 3 =ˆ 10100101000 3. Determine the remainder of the polynomial division m ′ (x)◁r(x), which is the checksum c(x). Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 m ′ (x) r(x) 1 0 1 0 0 1 0 1 0 0 0 : 1 1 0 1 = Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 m ′ (x) r(x) 1 0 1 0 0 1 0 1 0 0 0 : 1 1 0 1 = 1 1 1 0 1 0 1 1 1 Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 m ′ (x) r(x) 1 0 1 0 0 1 0 1 0 0 0 : 1 1 0 1 = 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 m ′ (x) r(x) 1 0 1 0 0 1 0 1 0 0 0 : 1 1 0 1 = 1 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 1 Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 m ′ (x) r(x) 1 0 1 0 0 1 0 1 0 0 0 : 1 1 0 1 = 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 m ′ (x) r(x) 1 0 1 0 0 1 0 1 0 0 0 : 1 1 0 1 = 1 1 0 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 1 Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 m ′ (x) r(x) 1 0 1 0 0 1 0 1 0 0 0 : 1 1 0 1 = 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 m ′ (x) r(x) 1 0 1 0 0 1 0 1 0 0 0 : 1 1 0 1 = 1 1 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 m ′ (x) r(x) 1 0 1 0 0 1 0 1 0 0 0 : 1 1 0 1 = 1 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 0 0 0 1 = c(x) Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 1. Determine coefcients: r(x) =ˆ 1101 and m(x) =ˆ 10100101 2. grad(r(x)) = 3 ⇒ multiply data by x 3. This corresponds to “appending” 3 zeros: m ′ (x) = m(x) · x 3 =ˆ 10100101000 3. Determine the remainder of the polynomial division m ′ (x)◁r(x), which is the checksum c(x). 4. The message to be transmitted is s(x) = m ′ (x) + c(x). The addition is a bitwise XOR operation since we operate over GF(2). 1 0 1 0 0 1 0 1 0 0 0 = m ′ (x) ⊕ 0 0 1 = c(x) 1 0 1 0 0 1 0 1 0 0 1 = s(x) Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Example: Reduction polynomial r(x) = x 3 + x 2 + 1, data m(x) = x 7 + x 5 + x 2 + 1 1. Determine coefcients: r(x) =ˆ 1101 and m(x) =ˆ 10100101 2. grad(r(x)) = 3 ⇒ multiply data by x 3. This corresponds to “appending” 3 zeros: m ′ (x) = m(x) · x 3 =ˆ 10100101000 3. Determine the remainder of the polynomial division m ′ (x)◁r(x), which is the checksum c(x). 4. The message to be transmitted is s(x) = m ′ (x) + c(x). The addition is a bitwise XOR operation since we operate over GF(2). 1 0 1 0 0 1 0 1 0 0 0 = m ′ (x) ⊕ 0 0 1 = c(x) 1 0 1 0 0 1 0 1 0 0 1 = s(x) The receiver checks the message by determining c ′ (x) = (s(x) + e(x)) mod r(x), where e(x) represents possible transmission errors: c ′ (x) ̸= 0 means that there were errors. c ′ (x) = 0 means that with high probability there were no errors. Chapter 2: Data link layer — Framing, addressing, and error detection 2-62 Addressing and error detection Which errors are detected by CRC32? Let n denote the length of the checksum, i. e. n = grad(r(x)). Then the following types of errors can be detected: all 1 bit errors isolated 2 bit errors, i. e., errors at bit positions i and j where i > j such that i − j > n some burst errors that are longer than n Depending on the concrete choice of the reduction polynomial we could also detect either all burst errors with length smaller than n or all error patterns with an odd number of ipped bits. Which errors cannot or not reliably detected? errors with more than n ipped bits errors consisting of multiple bursts all errors that are a multiple of the reduction polynomial Chapter 2: Data link layer — Framing, addressing, and error detection 2-63 Addressing and error detection Can CRC really not be used to correct errors? It can, but... CRC is initially designed as an error-detecting code, i. e. correction is not in the foreground. This does not exclude, however, that with a suitable choice of the reduction polynomial and with an appropriate ratio of useful data to redundancy, certain errors cannot also be corrected. Examples1 : ATM (Asynchronous Transfer Mode), for instance, uses a 1 B checksum to detect von 1,2,3 bit errors and to correct single-bit errors in the 4 B ATM Header. Bluetooth secures 10 bit data blocks with a 5 bit checksum, which allows to correct single-bit errors. So in both cases, CRC is used as an error-correcting block code. The code rate is 4◁5 with ATM and 2◁3 with Bluetooth. What about Ethernet? Ethernet frames have a default length of up to 1500 · 8 bit (not considering so called “jumbo frames”). The checksum is 32 bit long. That results in a code rate of approximately 0,997. CRC is not used here for error correction. 1 http://einstein.informatik.uni- oldenburg.de/rechnernetze/fehlerkorrektur1.htm Chapter 2: Data link layer — Framing, addressing, and error detection 2-64 Addressing and error detection Case study: IEEE 802.3u (FastEthernet) Frame before 4B5B encoding: 7B 1B 6B 6B 2B 46 – 1500 B 4B SFD Preamble DA SA Type Data (L3-PDU) FCS (CRC-32) Ethernet frame 64 − 1518 B Preamble and Start Frame Delimiter (SFD) are used for clock recovery. One Byte of the preamble is replaced by the J/K symbol of the 4B5B code (SFD). After the Frame Check Sequence (FCS), the T/R symbol is appended. The data between the J/K and T/R symbols are encoded according to the 4B5B code. The type eld indicates the type of the frame, e. g. 0x0800 =ˆ IPv4 payload, 0x0806 =ˆ ARP). The data eld eld must be at least 46 B before encoding – otherwise it is padded up to the minimal length. Chapter 2: Data link layer — Framing, addressing, and error detection 2-65 Addressing and error detection Case study: IEEE 802.11a/g (WLAN) Data frame as used in the infrastructure mode, i. e., with access point, without encryption: 2B 2B 6B 6B 6B 2B 4–? B ≤? B 4B Dur Seq SNAP PLCP FC Address 1 Address 2 Address 3 Data (L3-PDU) FCS ID Ctrl Header Physical Layer Convergence Procedure (PLCP) Header of the physical layer (comparable to the preamble in Ethernet) Serves for synchronization as well as for communication of transmission parameters (data rate, modulation, code rate, etc.) Not part of the L2 header Chapter 2: Data link layer — Framing, addressing, and error detection 2-66 Addressing and error detection Case study: IEEE 802.11a/g (WLAN) Data frame as used in the infrastructure mode, i. e., with access point, without encryption: 2B 2B 6B 6B 6B 2B 4–? B ≤? B 4B Dur Seq SNAP PLCP FC Address 1 Address 2 Address 3 Data (L3-PDU) FCS ID Ctrl Header 2 bit 2 bit 4 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit More Pow More Version Type SubType ToDS FromDS Retry PF Order Frag Mgmt Data Frame Control (FC) Indicates the type of the frame (data, management, or control frame) Denes how the addresses contained in the header are interpreted (ToDS / FromDS Bits) Various other parameters: Do other fragments follow that belong to the same frame? Is it a retransmit of a previous frame that was assumed to be lost? Does the transmitter has more data to send?... Chapter 2: Data link layer — Framing, addressing, and error detection 2-66 Addressing and error detection Case study: IEEE 802.11a/g (WLAN) Data frame as used in the infrastructure mode, i. e., with access point, without encryption: 2B 2B 6B 6B 6B 2B 4–? B ≤? B 4B Dur Seq SNAP PLCP FC Address 1 Address 2 Address 3 Data (L3-PDU) FCS ID Ctrl Header 2 bit 2 bit 4 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit More Pow More Version Type SubType ToDS FromDS Retry PF Order Frag Mgmt Data Variable number of MAC addresses depending on frame type and operation mode, here data frames in infrastructure mode address1 = AP.MAC address1 = C2.MAC Address 1 species the receiver address2 = C1.MAC address2 = AP.MAC (receiver address, RA) address3 = C2.MAC address3 = C1.MAC Address 2 species the transmitter (transmitter address, TA) AP Address 3 species the source (source address, SA) or the destination C1 C2 (destination address, DA) Chapter 2: Data link layer — Framing, addressing, and error detection 2-66 Addressing and error detection Case study: IEEE 802.11a/g (WLAN) Data frame as used in the infrastructure mode, i. e., with access point, without encryption: 2B 2B 6B 6B 6B 2B 4–? B ≤? B 4B Dur Seq SNAP PLCP FC Address 1 Address 2 Address 3 Data (L3-PDU) FCS ID Ctrl Header 2 bit 2 bit 4 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit More Pow More Version Type SubType ToDS FromDS Retry PF Order Frag Mgmt Data Sequence Control Sequence number of the frame Used to detect missing frames and to sort incoming frames Note: In contrast to Ethernet, WLAN uses acknowledgements on layer 2 since the transmission medium is too unreliable. This is not a replacement for acknowledgements on higher layers, but a necessity that protocols on higher layers can operate at all. Chapter 2: Data link layer — Framing, addressing, and error detection 2-66 Addressing and error detection Case study: IEEE 802.11a/g (WLAN) Data frame as used in the infrastructure mode, i. e., with access point, without encryption: 2B 2B 6B 6B 6B 2B 4–? B ≤? B 4B Dur Seq SNAP PLCP FC Address 1 Address 2 Address 3 Data (L3-PDU) FCS ID Ctrl Header 2 bit 2 bit 4 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit More Pow More Version Type SubType ToDS FromDS Retry PF Order Frag Mgmt Data Subnetwork Access Protocol (SNAP) Variable length header indicating the type of the L3 PDU Roughly comparable to the Ethertype (but much more exible) Chapter 2: Data link layer — Framing, addressing, and error detection 2-66 Addressing and error detection Case study: IEEE 802.11a/g (WLAN) Data frame as used in the infrastructure mode, i. e., with access point, without encryption: 2B 2B 6B 6B 6B 2B 4–? B ≤? B 4B Dur Seq SNAP PLCP FC Address 1 Address 2 Address 3 Data (L3-PDU) FCS ID Ctrl Header 2 bit 2 bit 4 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit More Pow More Version Type SubType ToDS FromDS Retry PF Order Frag Mgmt Data Data (L3 PDU) Variable length data eld The maximum frame length with IEEE 802.11 is multiple times larger than with Ethernet due to the expensive media access The media access requires a lot of time (large overhead) The smaller individual frames are, the more time is consumed by repeated media access ⇒ Frames tend to be larger even so that increases the probability of transmission errors Chapter 2: Data link layer — Framing, addressing, and error detection 2-66 Addressing and error detection Case study: IEEE 802.11a/g (WLAN) Data frame as used in the infrastructure mode, i. e., with access point, without encryption: 2B 2B 6B 6B 6B 2B 4–? B ≤? B 4B Dur Seq SNAP PLCP FC Address 1 Address 2 Address 3 Data (L3-PDU) FCS ID Ctrl Header 2 bit 2 bit 4 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit 1 bit More Pow More Version Type SubType ToDS FromDS Retry PF Order Frag Mgmt Data Frame Check Sequence (FCS) 32 bit CRC checksum over the whole L2 frame (everything exept the PLCP and the FCS itself) Except for implementation details identical to Ethernet A different reduction polynomial is used compared to Ethernet Chapter 2: Data link layer — Framing, addressing, and error detection 2-66 Chapter 2: Data link layer Representation of networks as graphs Characterizing connections, multiple access, and access control Framing, addressing, and error detection Connecting nodes on Layers 1 and 2 Hubs, bridges, and switches WLAN access points Security Considerations Summary References Chapter 2: Data link layer 2-67 Hubs, bridges, and switches Links on layer 1: hub Node A transmits a frame destined for node D The hub interconnects the individual links to a common bus The frame is received by all nodes Consequently, at any time only one node may transmit, otherwise collisions occur A→D A→D B A B A A→D A→D C D C D Important: Most layer 2 implementations are connectionless, i. e., there is no connection setup or teardown between source and destination1. 1 Ethernet uses the terms source and destination, although transmitter and receiver may be more precise and avoid confusion with source and destination from the perspective of layer 3. Making things even more confusing, all four terms are required to describe the addresses in wireless networks. Therefore, we stick to the usual naming convention. Chapter 2: Data link layer — Connecting nodes on Layers 1 and 2 2-68 Hubs, bridges, and switches Node D answers to the frame of A This answer is again received by all nodes D→A D→A B A B A D→A D→A C D C D Denition (Collision Domain) A collision domain is that part of a local area network within which a collision can occur when multiple nodes are transmitting simultaneously. It is commonly referred to as segment. Chapter 2: Data link layer — Connecting nodes on Layers 1 and 2 2-69 Hubs, bridges, and switches Are hubs more than just star distributors? A distinction is made between active and passive hubs: Active hubs (repeaters) amplify signals on the physical layer without checking the elds in frames like addresses or checksums Passive Hubs are really just star distributors – you might as well solder the individual wires of the patch cables together Can you cascade hubs? Yes, but for Ethernet (IEEE 802.3a/i) the 5-4-3 rule applies1 : Not more than 5 segments (of 100 m length each), connected by 4 repeaters, with active nodes in only 3 of these segments. Note: Each segment should be no longer than 185 m for 802.3a (10BASE-2), and no longer than 100 m for 802.3i (10BASE-T) between the hub and the end device due to attenuation. Due to reliable collision detection, 100BASE-TX results in a maximum extension of 500 m (will be discussed in the tutorial). Can hubs connect different types of media? Yes, if the same media access method is used on all sections (for example, connecting Ethernet via BNC and patch cables, each with the same data rate). It is not possible if the media access control schemes differ. 1 Note that this rule does not apply to modern, switched Ethernets. Chapter 2: Data link layer — Connecting nodes on Layers 1 and 2 2-70 Hubs, bridges, and switches Links on layer 2: switch A→D A→D B A B A→D A→D A 0 1 0 1 A→D A→D Host A is on port 1 C D C D Two groups of hosts, each connected by hubs, are coupled by a switch in the above example. The switch initially works like a hub with 2 ports (learning phase). Thereby the switch remembers over which port a frame was received. Thus, it assigns to ports 0 and 1 the MAC addresses of the nodes connected to the respective port. A switch with only two ports (which is more common again today in the context of virtualization) is also called bridge. Chapter 2: Data link layer — Connecting nodes on Layers 1 and 2 2-71 Hubs, bridges, and switches Links on layer 2: switch D→A B A B D→A A x 0 1 0 1 D→A Host A is on port 1 Host A is on port 1 Host D is on port 1 C D C D The destination address of incoming frames is compared with the entries in the switching table. If an entry exists, the frame is forwarded only to the destination port in question. Otherwise the frame is broadcast over all ports (except the port from which it was initially received.) Entries receive a timestamp and are invalidated after a xed time interval. One port may have mappings for several MAC addresses. Chapter 2: Data link layer — Connecting nodes on Layers 1 and 2 2-72 Hubs, bridges, and switches Links on layer 2: switch