Data Link Layer Protocols

Chapter 3: Datalink Layer

• Goals include understanding link layer services, framing, error detection/correction, multiple access sharing, MAC addressing, and local area networks like Ethernet and VLANs.
• Includes instantiation, implementation of various link layer technologies

Link Layer/LAN Outline

• The data link layer: introduction, services
• Framing as a link layer characteristic
• Error detection and correction as part of link layer functions
• Data link protocols like stop-n-wait and stop-n-wait ARQ

Link Layer Introduction

• Hosts and routers are nodes within the data link layer.
• Communication channels connecting adjacent nodes compose links. Links can be wired, wireless, or LAN-based.
• Layer-2 packets, known as frames, encapsulate datagrams.
• The data-link layer transfers datagrams from one node to physically adjacent node over a link

Link Layer Context

• Datagrams are transferred across various links using different link protocols (e.g., Ethernet, Frame Relay, 802.11)
• Each link protocol offers varied services.
• Link protocols may or may not offer reliable data transfer (rdt) over a link.
• Analogy: Transportation of tourists (datagrams) via different transportation modes (link layer protocols), communication links representing transport segments.

Link Layer Services

• Framing/Link Access: Encapsulates datagrams into frames by adding headers and trailers; used for channel access in shared mediums; employs MAC addresses in frame headers for source/destination identification, which differ from IP addresses.
• Reliable Delivery between Adjacent Nodes: Achieved through protocols learned in Chapter 3, seldom used in low bit-error links (e.g., fiber), but often used with wireless links with high error rates, for link-level and end-to-end reliability.

More Link Layer Services

• Flow control: coordinates pacing between adjacent sending and receiving nodes
• Error Detection: Identifies errors from signal attenuation or noise; receivers detect errors, signaling sender for retransmission or frame drops.
• Error Correction: Corrects bit errors without retransmission
• Half and Full Duplex: Half-duplex nodes at both ends of link transmit, but not concurrently, full-duplex allows simultaneous transmission in both directions

Link Layer Implementation

• Implemented in every host's "adaptor" (adapter, network interface card-NIC) or on a chip.
• Adaptors may be Ethernet cards, 802.11 cards, or an Ethernet chipset.
• Implements the link and physical layers, attaches to the host's system buses
• Hardware, software, and firmware combine to implement the data link layer

Adaptor Communication

• Sending side: encapsulates datagram into a frame, adds error checking bits, rdt, flow control information.
• Receiving side: checks for errors, rdt, flow control, extracts datagram, and passes it to upper layer.

Framing Methods

• Byte count, flag bytes with byte stuffing, flag bytes with bit stuffing, and physical layer coding violations are framing methods.
• Frame Header: Contains source and destination addresses
• Payload Field: Contains the message to be delivered.
• Trailer: Contains error detection and error correction bits
• Flags: Start and end of frame, is protocol dependent

Framing: Byte Count

• Length of the frame indicated by a byte at the beginning.
• This method is problematic because a corrupted byte count can lead to misinterpretation of frame boundaries.

Framing: Flag with Byte Stuffing

• A frame is delimited by flag bytes.
• In byte stuffing, an escape character (ESC) is added before any byte in the message that matches the flag byte pattern
• If the ESC character itself is present, it is also escaped by adding another ESC before it.

Framing: Flag with Bit Stuffing

• Insert an extra 0 bit after any sequence of five consecutive 1s to prevent them from being misinterpreted as flag bytes, mainly for HDLC.
• At the receiver's end, these inserted bits are removed. This method is used to prevent flag byte patterns

Framing: Physical Layer Coding Violations

• Using some redundancies, some LANs encode 1 bit of data by using 2 physical bits such as a high-low pair represents 1 and a low-high pair represents 0.
• The bit sequences are not used for data but for delimiting frames.

Error Detection

• Error Detection and Correction (EDC) bits provide redundancy for this process
• “D" signifies data protected by error checking, potentially including header fields.
• Error detection, though valuable, is not 100% reliable.
• Larger EDC fields improve error detection and correction capabilities

Error Detection Methods

• Common methods for error detection include: Parity check, Internet checksum, and Cyclic redundancy check (CRC).

Parity Checking

• Single Bit Parity: Detects single bit errors
• Two-Dimensional Bit Parity: Detects and corrects single bit errors.
• Two types of parity checking are even parity and odd parity.
• Even Parity: Number of 1s bits is even, then the parity bit is 0
• Odd Parity: Number of 1s bits is odd, the parity bit is 1

Internet Checksum

• Goal: to detect "errors" (flipped bits) in the transmitted packet
• Specifically used at transport layer
• Sender: treats segment contents as sequence of 16-bit integers, computes checksum as the addition (1's ement su complement sum) of segment contents, and puts value into UDP checksum field.
• Receiver: computes checksum of received segment, and checks if computed checksum equals value: NO = error, YES = no error.

Cyclic Redundancy Check (CRC)

• Employs more powerful error-detection coding with data bits (D) viewed as a binary number.
• An r value represents the "degree" of a "generator" G.
• The r CRC bits (R) are chosen sush that <D, R> is exactly divisible by G
• Known by receivers, G divides <D, R> by G. Zero remainder indicates no errors detected; non-zero reveals existence.
• Can detect all burst errors less than bits.
• Used in Ethernet, 802.11 WiFi, and ATM.

Elementary Data Link Protocols

• Utopian Simplex Protocol
• Simplex Stop-and-Wait Protocol; Error-Free/Noisy Channel
• Sliding Window Protocol; Go-back-N/Selective repeat

Utopian Simplex Protocol

• Provides unidirectional data transmission over an ideal channel
• Has error free transmissions
• Not realistic, and is called utopian simplex protocol

Simplex Stop-and-Wait Protocol for a Noisy Channel

• Popularly known as Stop-and-Wait Automatic Repeat Request (ARQ) protocol.
• Adds error control facilities to the basic Stop-and-Wait protocol.

Sliding Window Protocols

• Multiple frames can be sent by a sender before receiving an acknowledgment from the receiver.
• Imaginary boxes hold frames and a buffer is called the sending window.
• The receiver has a buffer called the receiving window with two categories

Protocol using Go-Back-N

• This protocol uses error recovery and Pipelining.
• Receiver's window size is 1

Protocol using Selective Repeat

• A protocol provides sending multiple frames before receiving the first frame acknowledgment.
• Here only the good/erroneous/lost frames are retransmitted/buffered.

Data Link Protocols

• HDLC – High-Level Data Link Control
• Data Link Layer in the Internet

HDLC – High-Level Data Link Control

• Layer 2 protocols which transmit synchronous data packets between point-to-point nodes (RFC 1662).
• It uses a zero-insertion/deletion process (bit stuffing) which ensures bit pattern of delimiter flag does not occur in the fields between flags.
• Frame format:
  • Bits 01111110 Address Control Data Checksum 01111110
  • Contains the source, and destination addresses of the frame, as well as error detection and correction bits.

HDLC Control Field

• Information, supervisory, and unnumbered frames, data is usually sent in multiples of 8 bits
• Only some variations require this/others provide the data alignments other than 8 bit boundaries.
• The frame check sequence (FCS) is a 16 - bit CRC or a 32-bit CRC computed over the Address, Control, and Information fields.

Summary of Principles

• Framing link layer consists of byte count, byte/bit stuffing.
• Error detection and correction methods of Parity, checksum, and CRC.
• Elementary data link protocols such as Utopian, Simplex, or Sliding Window.