Computer Networks 1: Link Layer

Course Information

• Course: CNT 4007 - Computer Networks 1
• Topic: Link Layer
• Professor: Patrick Traynor
• Semester: Fall 2024

Reminders/Notes

• Homework 3 due Thursday
• Project 3 due next Tuesday
• Midterm grading started yesterday and progress is being tracked
• Students should keep an eye on the calendar for important dates.

Link Layer and LANs: Our Goals

• Understand link layer services (error detection, correction, broadcast channel sharing, multiple access)
• Learn about link layer addressing (e.g., Ethernet, VLANs)
• Learn about datacenter networks
• Implement various link layer technologies

Link Layer, LANs: Roadmap

• Introduction to Link Layer
• Error detection and correction
• Multiple access protocols
• Local Area Networks (LANs):
  • Addressing (e.g., ARP)
  • Ethernet
  • Switches
  • VLANs
• Link virtualization (e.g., MPLS)
• Data center networking
• Day in the life of a web request

Link Layer: Introduction

• Terminology:
  • Hosts and routers as nodes
  • Communication channels connecting nodes: links (wired, wireless, LANs)
  • Layer-2 packet: frame that encapsulates datagram.
• Link Layer's responsibility: Transferring datagrams between physically adjacent nodes.

Link Layer: Context

• Datagrams transferred by different link protocols over different links (e.g., WiFi to Ethernet)
• Each link protocol provides different services (e.g., reliable data transfer may or may not be available)

Link Layer: Services

• Framing, link access: encapsulating datagrams into frames and adding headers/trailers
• Channel access: relevant when multiple nodes share a common medium. MAC Addresses identify source and destination.
• Reliable delivery between adjacent nodes (though not frequently used on links with low error rates).
• Wireless links often have high error rates so link-level reliability is needed
• Flow control: pacing of data transmission between sending and receiving nodes
• Error detection methods: for identifying errors caused by signal attenuation, noise, etc.; receiver signals retransmission or drops frame.
• Error correction: identifying and correcting bit errors without retransmission
• Half-duplex and full-duplex: with half duplex transmissions are sent simultaneously, but full duplex ones aren't

Where is the Link Layer Implemented?

• Implemented in each network interface card (NIC) or on chip
• Specific to chip: Ethernet, WiFi cards or chips.
• Implemented using combination of hardware, software, and firmware. The NIC attaches to host's system buses

Interfaces Communicating

• Sending side encapsulates datagram into frame, adds error-checking bits, and handles reliable data transfer and flow control
• Receiving side checks for errors, extracts the datagram, and passes it to the upper layer

Link Layer, LANs: Roadmap (Page 11)

• Introduction
• Error detection and correction
• Multiple access protocols
• Local Area Networks (LANs): Addressing, ARP; Ethernet; Switches; VLANs
• Link virtualization (e.g., MPLS)
• Data center networking
• A day in the life of a web request

Error Detection

• EDC: error detection and correction bits (redundancy)
• Data protected by error checking (headers included).
• Error detection isn't 100% reliable.
• Larger EDC field improves accuracy and correctness

Why?

• Repeated discussions of error detection highlight their importance in networking.
• Special aspects of link layer requiring additional attention discussed.
• Supporting considerations and justifications are provided for the extra effort.

Parity Checking

• Single bit parity detects single bit errors (even parity ensures even number of 1's).
• Two-dimensional bit parity detects and corrects single bit errors.

Internet Checksum (review)

• Goal: Detect errors in transmitted segments.
• Sender: treats UDP segment contents as 16-bit integers; finds ones complement sum; puts checksum into UDP checksum field.
• Receiver: calculates checksum of received segment; checks if computed checksum equals checksum field value; error is indicated if checksums don't match.

Cyclic Redundancy Check (CRC)

• More powerful error-detection coding.
• Data bits (D) and generator bit pattern (G) used to calculate CRC bits (R).
• <D,R> is divisible by G in modulo 2 if no errors occur

Cyclic Redundancy Check (CRC): Example

• Specific example using a 10110111 generator formula to calculate the CRC bits.

Link Layer, LANs: Roadmap (Page 18)

• Introduction, error detection and correction
• Multiple access protocols
• LANs: Addressing, ARP; Ethernet; Switches; VLANs
• Link virtualization (e.g., MPLS)
• Data center networking
• A day in the life of a web request

Multiple Access Links, Protocols

• Two types of links: point-to-point (e.g., PPP, Ethernet switch to host) and broadcast (shared wire or medium, e.g., old-fashioned Ethernet, wireless LAN, upstream HFC cable)

Multiple Access Protocols

• Single shared broadcast channel. Interference occurs with two or more simultaneous transmissions.
• Collision occurs if a receiving node receives more than one signal.
• The multiple access protocol distributes the channel allocation among nodes by determining when nodes can transmit.
• Sharing must use the channel. No out-of-band channel for coordination.

An Ideal Multiple Access Protocol

• Desirable characteristics of an ideal multiple access protocol, a multiple access channel (MAC) operates at R bps

MAC Protocols: Taxonomy

• Three broad classes of multiple access protocols (MAC) :
  • Channel partitioning (allocating exclusive use of channel parts)
  • Random access (allows collisions and recovery)
  • Taking turns (nodes take turns)

Channel Partitioning MAC Protocols: TDMA

• TDMA: Time Division Multiple Access
• Each station accesses channel at fixed time slots.
• Unused slots remain idle.

Channel Partitioning MAC Protocols: FDMA

• FDMA: Frequency Division Multiple Access
• Channel spectrum divided into frequency bands.
• Each station gets a fixed frequency band.
• Unused transmission time is idle.

Random Access Protocols

• When a node has a packet, it transmits at full channel capacity
• Random access MAC protocol specifies procedures for collision detection, recovery (e.g., delayed retransmissions), etc.
• Examples include ALOHA and variations.

Slotted ALOHA

• Assumptions: frames are same size, time divided in equal size slots, synchronized nodes, etc.
• Operation: Obtaining frame, transmitting in next slot, handling collisions, retransmission strategy.
• Pro/con analysis: considering benefits and drawbacks.

Slotted ALOHA: Efficiency

• Efficiency (long run) of successful slots when many nodes transmit many frames.
• Maximum efficiency is calculated.

Pure ALOHA

• Simple unslotted version, no synchronization.
• Collision probability increases without synchronization.
• Efficiency is lower compared to the slotted version.

Conclusions

• Current topic is only a small piece of broader Link Layer concepts.
• Students are progressing well.
• Students should improve their reading and participation.
• See you Thursday.