【正文】 ecification and Verification ? Example Data Link Protocols Ch. 4 Ch. 3 Data Link Layer 2 Data Link Layer Design Issues ? Services Provided to the Network Layer ? Framing ? Error Control ? Flow Control Ch. 3 Data Link Layer 3 Services Provided to the Network Layer (1) Ch. 3 Data Link Layer 4 Services Provided to the Network Layer (2) ? Three reasonable services: – Unacknowledged Connectionless – Acknowledged Connectionless – Acknowledged ConnectionOriented ? Example – Routers connected by pointtopoint leased telephone lines 187。 1: Hardware in Physical Layer 187。 3: Software in Network Layer ˇ ˇ Ch. 3 Data Link Layer 5 Framing (1) ? Framing – To break the bit stream into discrete frames – To specify destination and source addresses – To pute the checksum for each frame – To include other control messages – … ? How to distinguish frames (to mark the start and the end of a frame)? – (1) Character count – (2) Starting and ending characters, with character stuffing – (3) Starting and ending flags, with bit stuffing – (4) Physical layer coding violation – (5) Hybrid Ch. 3 Data Link Layer 6 Framing (2) – (1) Character count Ch. 3 Data Link Layer 7 Framing (3) – (2) Starting and ending characters, with character stuffing 187。IBM SDLC 01111110 Frame contents (in bit) 01111110 Insert 0 after 5 consecutive 1’s Ch. 3 Data Link Layer 9 Framing (5) – (4) Physical layer coding violation 187。 Differential Manchester Encoding (used in ) ◆ Transition in the middle of every bit ◆ In the start of a bit: 0 – Transition 1 – No transition ⊕ Transitions in the middle of every bit are synchronization ⊕ Constant Power consumption ∴ Encoding Violation: No transition in the middle of a bit? HiHi or LoLo o o o o o o x x x x x Ch. 3 Data Link Layer 10 Error Control (1) ? To ensure reliable delivery for reliable services – The sender put error detection code in the data frame。If the data is correct, then the receiver ACKs。If the sender receives the PACK, then it can send the next data frame. * Widely used D Data (1) PACK (1) Data (2) S ? Ch. 3 Data Link Layer 11 Error Control (2) 187。[Solution 1] ? The sender keeps a timer (計(jì)時(shí)器 ). ? If the timer expires (timeout, 逾時(shí) ), the sender retransmits (重送 ) the frame. – This method is called: Positive ACK. With Retransmission (PAR) 或 Automatic Repeat reQuest (ARQ) Timer out ? ReTx D Data (1) Data (1) S ? Timer ? Ch. 3 Data Link Layer 12 Error Control (3) 187。[Solution 2] ? Each frame contains a sequence number (序號 ). ? The receiver checks for duplicated frame. ? If a frame is duplicated, the receiver discards the duplicated frames and sends PACK. D S Duplicate ? Discard amp。If the data is correct, then the receiver does not ACK。If the sender receives the NACK, then it retransmit the frame. 187。[Solution] ? The receiver keeps a timer. When the timer expires, it sends another NACK. D Data (1) Data (2) S Time out amp。The receiver sends a special feedback message to the sender, asking the sender to slow down or speed up the transmission 187。The transmitter decides by itself whether to slow down or speedup the transmission 187。Example: Flow control of TCP depends on how ACKs are received Ch. 3 Data Link Layer 15 Error Detection and Correction (1) ? Two categories of Error Handling – Error Correction (錯誤修正 ) 187。More redundant information 187。Suitable for channels with high error rate, such as wireless works – Error Detection (錯誤偵測 ) 187。Less redundant information 187。Suitable for channels with low error rate, such as wireline works, such as copper wire and optical fiber Ch. 3 Data Link Layer 16 Error Detection and Correction (2) ? ErrorCorrecting Codes ? ErrorDetection Codes Ch. 3 Data Link Layer 17 ErrorCorrecting Codes (1) ? Codeword (字碼 ) – For a frame of bit stream (n bits), including m message bits and r redundant bits, . n = m + r ? Hamming distance (漢明距離 ) – The number of bit positions in which two codewords differ 187。To correct d errors ? 2d+1 codewords – Error Detecting Code 187。Example: If m = 8 ? ( 8 + r + 1 ) ≦ 2r ? r = 4 – At the sender (1) Bit Position ? Number codeword bits: starting with bit 1 at left end ( …) ? Place the redundant (check) bits (currently unknown) at bit 1, 2, 4, 8, …, 2n ? Place the message bits (. ‘H’ = 1001000) to the rest of the bits ?