M04 Data Link Layer

• •Summarize the two approaches to media access control: controlled access and contention• Analyze the most common transmission errors, including their causes, prevention, and remediation• Calculate Even or Odd Parity, and explain the basic operation of checksums and cyclical redundancy checks• Assess the validity of error detection methods• Describe forward error correction techniques
• Data Link Layer

  •Layer 2 in the OSI model• Responsible for moving messages from one device to another• Controls the way messages are sent on media• Often divided into two sublayers:• Logical Link Control (LLC) sublayer connects to network layer above• Media Access Control (MAC) sublayer controls physical hardware• Major functions of a data link layer protocol◦ Media Access Control◦ Error Control◦ Message Delineation
• Media Access Control

  •Controls which device transmits and when• Important on: ◦ Multipoint (shared) circuits◦ Half-duplex point-to-point circuits• Two approaches 1. Contention access 2. Controlled access

  
• Controlled Access 


  •Common in wireless LANs• Access request◦Each device must get “permission” to transmit, similar to raising a hand.• Polling◦ Roll-call polling◦ Central device (controller) determines which devices can transmit.◦ Each client is checked periodically to see if it needs to transmit.◦ Hub polling (token passing)◦ One device begins the poll and then passes it to another device until each device has an opportunity to transmit; then start over
• Media Access Control

  
• Error Control 


  •Network errors: Types◦ Corrupted data◦ Lost data◦ Caused by problems in transmission (not humans)• Networks should be designed with: Error prevention◦ Error detection Error correction
• Sources of Network Errors


  •Line noise and distortion◦ Major reason for errors and caused by several sources◦ More likely on electrical media◦ Undesirable electrical signal◦ Degrades performance of a circuit◦ Manifestation◦ Extra bits◦ “Flipped” bits◦ Missing bits

  
• Error Prevention

  
• Error Detection


  •Receivers need to know when the data transmitted is not correct.• Add “check value” (error detection value) to message.

  • Check the value produced by a mathematical formula• Different implementations (parity bit, checksum, CRC)

  
• Error Detection (cont'd)

  •Both sender and receiver calculate check value•Receiver tests whether the check value received matches calculated value

  
• Error Detection – Parity Check


  •One-bit check value added to message• Based on the number of 1s in the message◦ Even parity: parity bit set so that an even number of 1s transmitted◦ Odd parity:  parity bit set so that an odd number of 1s transmitted• Simple, but only detects 50% of errors

  
• Error Detection – Checksum  


  Checksum  

  1-byte (typically) check value

  Checksum algorithms vary

  Standard: divide sum of character values by 255, use remainder as checksum

  Detects 95% of errors
• Contention 


  •Transmits data whenever circuit is available with no centralized control•Common in Ethernet LANs•When devices transmit at the same time, a collision occurs.•Devices must be “polite” and follow these steps:1.Listen for traffic2.If another device is transmitting, wait to transmit3.Otherwise, transmit (and keep listening)4.If another device begins to transmit, stop and wait. This loosely describes the Ethernet media access control, Carrier Sense Multiple Access/Collision Detection (CSMA/CD)
• Error Detection – Cyclic Redundancy Check (CRC)


  •Treats message as a single binary number• Divides by a preset number• Uses remainder as the check value• Preset number is chosen so that remainder is the correct number of bits• Modes:◦ CRC-16 (~99.998% error detection rate)◦ CRC-32 (>99.99999% error detection rate)
• Error Correction

  •Once detected, errors must be corrected.• Error correction techniques◦ Retransmission (or backward error correction) ◦Retransmission is simple and most common◦ Automatic Repeat reQuest (ARQ)◦ Stop-and-wait ARQ◦Continuous ARQ◦ These techniques can also provide flow control by limiting the number of messages sent.
• Forward Error Correction


  •Receiving device can correct messages without retransmission◦ Includes a certain level of redundancy in transmitted data so that receiving device can correct errors◦ Used only when retransmission is impossible, very costly, or time consuming (e.g., satellite connections)
• Forward Error Correction - Hamming Code

  
• Error Correction in Practice


  •On wired connections, errors are quite rare• Most modern data link layer software doesn’t correct errors, just detects and discards frames with errors• Error correction must then be done at a higher layer Transport Layer using continuous ARQ. ARQ = Automatic Repeat reQuest
• Learning Objectives


  •Explain synchronous and asynchronous transmission data transfer methods• Diagram the fields of a data link frame• Outline data link protocols: Async, SDLC, Ethernet, and PPP.• Differentiate between transmission efficiency and transmission throughput
• Data Link Protocols: Asynchronous and Synchronous

  
• Asynchronous transmission (start-stop transmission)


  •Older protocol (used for Unix/Linux Telnet)• Transmits one character at a time• Delineation indicated by start and stop bits (opposites)◦ Idle signal defined to be same as stop bit

  
• Synchronous Protocols – SDLC 

  •Synchronous transmission◦ Data sent in a large block called a frame◦ Includes addressing information◦ Includes synchronization characters to let the receiver know when data transmission begins• Synchronous Data Link Control (SDLC)◦ Synchronous bit-oriented protocol developed by IBM◦ Uses bit stuffing (zero insertion) to overcome transparency problem

  
• Synchronous Protocols – Ethernet 


  •IEEE 802.3 standard and Ethernet II• Most widely used LAN protocol• Uses contention media access control• Ethernet II Frame

  
• Synchronous Protocols – Point-to-Point Protocol (PPP


  •Common WAN protocol

  
• Transmission Efficiency 


  •The total number of information bits (i.e., bits in the message sent by the user) divided by the total bits in transmission (i.e., information bits plus overhead bits)◦ Information bits convey the user’s meaning. ◦ Overhead bits are used for purposes such as error checking and marking the start and end of characters and packets.• Efficiency is improved by reducing the number of overhead bits in each message or by increasing the number of information bits. 
• Transmission Efficiency

  
• The Effect of Frame Size on Throughput

  
• Throughput (TRIB)

  
• Cyber security Implications

  •The data link layer uses the MAC address (a.k.a. physical address) to recognize the source and destination addresses of two communicating computers. • MAC address filtering creates a list of MAC addresses that are allowed to connect to a Wi-Fi network or to a switch in corporate networks.• However, MAC address spoofing is a software-enabled technique that can change the hardcoded MAC address to any MAC address and thus overcome MAC address filtering. MAC address spoofing not illegal, but what done with it might be.
• Optical media is:

    

  less likely to suffer from noise than electrical media
• ARQ means that:

  a receiver that detects an error in a message simply asks the sender to retransmit the message until it is received without error
• On digital circuits, we use _________ to reshape the incoming signal and mitigate the effects of attenuation.

    

  repeaters
• ____________ is not a function of a data link protocol.

  Amplitude shift keying
• Stop-and-wait ARQ uses ___________ type of data flow.

  half duplex