Communication Systems and Computer Networks Part 11 PDF
Document Details
Uploaded by Deleted User
Prof. Shawkat K. Guirguis
Tags
Related
Summary
This document is a presentation on communication systems and computer networks, focusing on the data link layer and error handling techniques. The presentation covers concepts like framing, error control, and error correction codes, including Hamming codes.
Full Transcript
Communication Systems and Computer Networks (1404703) Prepared by: Prof. Shawkat K. Guirguis Professor of Computer Science & Informatics Part 11 2024-12-...
Communication Systems and Computer Networks (1404703) Prepared by: Prof. Shawkat K. Guirguis Professor of Computer Science & Informatics Part 11 2024-12-16 (c) Prof.Shawkat K. Guirguis 1 The Data Link Layer 2024-12-16 (c) Prof. Shawkat K. Guirguis 2 Data Link Layer Deals with the algorithms of achieving reliable & efficient communication between two adjacent machines Adjacent means physically connected via (e.g. coaxial, telephone, point-to-point wireless) 2024-12-16 (c) Prof. Shawkat K. Guirguis 3 Data Link Layer Design Issues Services Provided to the Network Layer Framing Error Control (May be found in upper layers in some networks) Flow Control 2024-12-16 (c) Prof. Shawkat K. Guirguis 4 Services provided to the Network Layer May vary from system to system but mainly: 1. Unacknowledged connectionless services 2. Acknowledged connectionless services 3. Acknowledged connection-oriented services 2024-12-16 (c) Prof. Shawkat K. Guirguis 5 Framing concept Relationship between packets coming from Network Layer and frames formed by the data link layer. 2024-12-16 (c) Prof. Shawkat K. Guirguis 6 Framing is achieved by: 1. Character counts 2. Flag bytes with byte stuffing 3. Starting and ending flags, with bit stuffing 4. Physical layer coding violations (Special coding of 1’s and 0’s in the physical layer) 2024-12-16 (c) Prof. Shawkat K. Guirguis 7 1. Character count framing A character stream. (a) Without errors. (b) With one error. 2024-12-16 (c) Prof. Shawkat K. Guirguis 8 2. Byte/character stuffing framing (a) A frame delimited by flag bytes (Suffers from data being interpreted as flags and cannot deal with longer characters such as UNICODE 16 bits) (b) Four examples of byte sequences before and after stuffing. 2024-12-16 (c) Prof. Shawkat K. Guirguis 9 3. Bit stuffing framing Bit stuffing deals with the variable length characters by stuffing e.g. 0 every five 1’s. Also, it has flag bits (actually a byte) (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. 2024-12-16 (c) Prof. Shawkat K. Guirguis 10 Physical layer coding violation Valid in some networks where the physical medium contains some redundancy, e.g. 1 bit: high-low pair 0 bit: low-high pair Therefore frames are delimited by high-high or low-low 2024-12-16 (c) Prof. Shawkat K. Guirguis 11 Error Detection and Correction Error-Detecting Codes Error-Correcting Codes NOTE: Errors tend to come in bursts 2024-12-16 (c) Prof. Shawkat K. Guirguis 12 Burst errors: They are much harder to correct Suppose a block size of 1000 bits and error rate of 0.001 then each block may have an error Suppose a block size of 100 bits then a frame may be in error out of a large number of good frames 2024-12-16 (c) Prof. Shawkat K. Guirguis 13 Detection or Correction? On fibers it is cheaper and very fast to retransmit a block when an error is detected so only error detection is needed On wireless transmission many errors may occur and error correction is essential 2024-12-16 (c) Prof. Shawkat K. Guirguis 14 Error-Detecting Codes Calculation of the polynomial code checksum. 2024-12-16 (c) Prof. Shawkat K. Guirguis 15 Error correcting codes (Codeword n bits) = (Message m bits ) + (redundancy r bits) Not all 2n codewords are legal Example: Assume only four valid codewords (0000000000) (0000011111) (1111100000) (1111111111) Then if (0000000111) is received it must be 0000011111 2024-12-16 (c) Prof. Shawkat K. Guirguis 16 Hamming method A codeword is formed from original message by having several formulas to compute the parity that is put in bits: 1,2,4,8,… etc. The message itself goes to bits 3,5,6,7,9…etc. 2024-12-16 (c) Prof. Shawkat K. Guirguis 17 Hamming method (2) Hamming codes can only correct single errors Burst errors of length k or less can be corrected by sending the block in a columnar form and then reassembled at receiver so that each row may have only one error (see next figure) 2024-12-16 (c) Prof. Shawkat K. Guirguis 18 Error-Correcting Codes Use of a Hamming code to correct burst errors. 2024-12-16 (c) Prof. Shawkat K. Guirguis 19