Computer Networking Lecture Notes

23 October 2012 • The Data-Link Layer

---

Outline

• Review
• Data-link layer and end-point connectivity.
• Data-link layer services.
  • Reliability and connectivity.
• Example data-link layer protocols.
  • Perfect links.
  • Rate mismatched links.
  • Corrupting links.

The Application Layer

The Transport Layer

The Network Layer

The Data-Link Layer

A Little More Detail

End-Point Connectivity

• Point-to-point (shared) channels.

  

• Shared (multiaccess, broadcast, random access) channels.

  

Data-Link Sublayers

• Logical link control frames data and ensures transmission characteristics.
  • Error and flow control.
• Media access control accesses the physical layer appropriately.

  Point-to-point: relatively easy.
  Shared: considerably harder.

Data Link Services

• Data transmission.
  • Unacknowledged connectionless service.
    • Simple and unreliable.
  • Acknowledged connectionless service.
    • Paying for reliability.
  • Acknowledged connection-oriented service.
    • Multiplex a single channel.
• Addressing.

Channel Characteristics

• The data-link channel can be noisy, which could induce errors.
  • Value in error detection and perhaps correction.
• Shared channels may need addressing.
• Abstract from the media access control sublayer.
• These issues can be dealt with by framing (encapsulation).

Framing

• Framing adds information to support data transmission.

• Packet: Network PDU, most likely.
• First question: how are frames framed?
  • What delimits a frame on the wire?

Byte Counts

• First try: the header is a byte count.

  

• Problems:

  

  • Hard to recover from errors.
  • No information to request retransmission.

Byte Flags

• Second try: explicitly mark frame ends.

  

• The mark is called the flag byte, a frame-unique value.
• Successive flag bytes mark the start of a frame.

  

Byte Stuffing

• A flag byte is just a byte value.
• What happens when the flag byte occurs in the payload?
  • Confusion may reign.
• Use an escape byte to neutralize payload flag-byte values.
  • An escape byte is an other frame-unique byte value.
• Preceding a payload flag-byte value with an escape byte escapes (neutralizes) the value.

Byte-Stuffing Example

• But isn’t the escape byte a byte value too?

  

Bit Stuffing

• Byte stuffing might double the frame size.
  • And what happens when the payload isn’t byte oriented?
• Bit stuffing is an alternative to byte stuffing.
• The frame flag is still a frame-unique byte value as a bit pattern.
  • High-Level Data Link Control (HDLC) uses 7E₁₆ = 01111110₂.

Stuffing Bits

• Using the HDLC flag every sequence of 5 1 bits is followed by (stuffed with) a 0 bit.

  

• Bit stuffing adds at most 20% to the frame length.
• Stuffing (bits or bytes) is invisible outside the data-link layer.

Error Control

• Reliable data-link transmissions should recognize and handle errors.
  • It’s more efficient at the data-link layer, but not necessary
• The usual schemes come into play at the data-link layer:
  • Acknowledgments provide feedback.
  • Sender time-outs recover from lost acks.
  • Sequence numbers protect against duplicates.

Flow Control

• Heterogeneous end-points may have mismatched capabilities.
• Flow control smooths over end-point differences.
  • Flow control can be either rate-based or feedback-based.
• Modern network interface cards (NICs) tend to make flow control a less serious problem.
  • But old or limited end-points.

Basic Data-Link Protocols

• Correct communication is easy in the absence of errors.
  • But there are lots of errors.
• As usual, “correct” means “accurately reproduced” on the receiver side.
  • Spatial correctness; temporal correctness is another matter.
• The data-link layer is the first (or last) place these matters can dealt with concretely.

Perfect Links

• Assume perfect links, links that
  • are errorless, and
  • have rate-matched end-points.
• Data-link PDUs are simple under these conditions.

    struct frame
      byte payload[]
  

  • But not simple if payload size varies.

Perfect Link Protocol

data-link-sender()
  frame f

  while true
    f.payload = from-network-layer()
    to-physical-layer(f)


data-link-receiver()

  while true
    frame f = from-physical-layer()
    to-network-layer(f.payload)

Rate Mismatches

• Remove the rate-matched assumption.
  • The sender could overrun the receiver.
• There are two general solutions:
  • Rate-based transmission.
  • Stop-and-wait transmission.
• Errors and rate-based transmission don’t go well together.

Stop-and-Wait Sender

data-link-sender()

  frame f, ack

  while true
    f.payload = from-network-layer()
    to-physical-layer(f)
    ack = from-physical-layer()

Stop-and-Wait Receiver

data-link-receiver()

  frame ack

  while true
    frame f = from-physical-layer()
    to-network-layer(f.payload)
    to-physical-layer(ack)

Link Errors

• Remove the errorless assumption.
  • Now frames can be corrupted or lost.
  • Corrupted frames can be tossed for a loss.
• Losses can be recovered from on the sender side with time-outs.
  • The receiver makes no assumptions about frame arrivals.
• Lost acks could result in duplicate frames being sent.

Error-Handling Sender

data-link-sender()
  frame f, ack
  event e

  f.seq-no = 0
  f.payload = from-network-layer()
  while true
    to-physical-layer(f)
    start-timer(f.seq-no)
    e = wait-for-event()
    if e == frame-arrival
      ack = from-physical-layer()
      if ack.seq-no == f.seq-no
        stop-timer(f.seq-no)
        f.payload = from-network-layer()
        f.seq-no = (f.seq-no + 1) mod 2
    // else time-out, corruption 

Error-Handling Receiver

data-link-receiver()
  unsigned expected-seq-no = 0

  while true
    frame f = from-physical-layer()
    if frame-uncorrupted(f)
      if f.seq-no == expected-seq-no
        to-network-layer(f.payload)
        expected-seq-no = (expected-seq-no + 1) mod 2

      f.payload = []
      f.seq-no = 1 - expected-seq-no
      to-physical-layer(f)

Summary

• The data-link layer offers transmission service to the network layer.
  • Reliable or not, connectionless or not.
• Link-channel complexity causes the logical-link and media-access control sublayers split.
• The data-link (and physical) layer is where network abstractions are implemented.
• The end-to-end argument becomes clear at the data-link layer.

References

• A Stream Input-Output System by Dennis Ritchie in AT&T Bell Labs Technical Journal, October, 1984.
• The Structuring of Systems Using Upcalls by David Clark in The Proceedings of the Tenth Symposium on Operating System Principles, 1985.
• The x-Kernel: An Architecture for Implementing Network Protocols by Norman Hutchinson and Larry Peterson in IEEE Transactions on Software Engineering, January, 1991.
• The Fox Project: A Language-Structured Approach to Network Software by Jeremy Buhler in Crossroads, September, 1995.

---

This page last modified on 2012 October 23.