Mạng máy tính 1 - Chapter 3: The data link layer

The Data Link Layer Chapter 3 Data Link Layer Design Issues • Services Provided to the Network Layer • Framing • Error Control • Flow Control Functions of the Data Link Layer • Provide service interface to the network layer • Dealing with transmission errors • Regulating data flow • Slow receivers not swamped by fast senders Functions of the Data Link Layer (2) Relationship between packets and frames. Services Provided to Network Layer (a) Virtual communication. (b) Actual communication. Services Provided to Network Layer (2) Placement of the data link protocol. Framing A character stream. (a) Without errors. (b) With one error. Framing (2) (a) A frame delimited by flag bytes. (b) Four examples of byte sequences before and after stuffing. Framing (3) Bit stuffing (a) The original data. (b) The data as they appear on the line. (c) The data as they are stored in receiver’s memory after destuffing. bit pattern: 01111110 (in fact, flag byte) Error Detection and Correction • Error-Correcting Codes • Error-Detecting Codes Error-Correcting Codes Parity bit: The parity bit is chosen so that the number of 1 bits in the codeword is even (or odd). Example: Even parity: 1011010 → 10110100 Odd parity: 1011010 → 10110101 Error-Correcting Codes Calculating parity bits (even parity): p0 = p(1, 3, 5, 7): all bits at position whose number ending with 1 (bin) P1 = p(2,3,6,7): second least significant bit is 1 (bin) The (7,4) Hamming code All possible values of 3 bits 001 → 1 010 → 2 011 → 3 100 → 4 101 → 5 110 → 6 111 → 7 Error-Correcting Codes The (7,4) Hamming code table Error-Correcting Codes Single-error code received: 1001110 Check the parity bits: p1 = p(1,0,1,0) = 0 [right], p2 = p(0,0,1,0) = 1 [error] p3 = p(1,1,1,0) = 1 [error] Number of erroneous bit: x = p2p1p0 = 110 (bin) = 6 (dec) The receiver flips the bit at position 6 to correct the block. Error-Detecting Codes in practice, another method is in widespread use: the polynomial code, also known as a CRC (Cyclic Redundancy Check). Where?  Assume block size 1000 bits. 10 check bits are needed for error-correction;  To detect a block with a single 1-bit error, one parity bit per block will suffice. Improvement Data as a rectangular matrix n bits wide and k bits high. A parity bit is computed separately for each column and append to the matrix as the last row. Flow Control  feedback-based flow control, the receiver sends back information (feedback) to the sender to control the flow.  rate-based flow control, the protocol has a built-in mechanism that limits the rate at which senders may transmit data.