Computer Networking Lecture Notes

2014 October 20 • 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.

Where We Were

The Data-Link Layer

What are Subnets?

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

  

• Point-to-point channels.

  

A Little More Detail

• Separate services provided from implementation.

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.

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.

Addressing

• Data-link layer hosts are identified by a MAC address.
  • Assigned to the interface.
• A MAC address is 6 bytes (48 bits) in two 3-byte parts.

  

• Specified as 12 hex digits.

MAC Address Examples

• 00:11:25 — IBM; 00:12:f0 — Intel; 00:26:62 — Actiontec Electronics.

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

• macaddress.webwat.ch

---

This page last modified on 2014 October 20.