The Data Link Layer

Question 1

Link layer: introduction

Answer 1

terminology:
- nodes: hosts and routers
- links: communication channels that connect adjacent nodes along a communication path
* wired links
* wireless links
* LANs
- frame: a layer-2 packet that encapsulates a datagram

data-link layer has responsibility of transferring a datagram from one node to another phy-layer-adjacent node over a link

Question 2

Link layer: context

Answer 2

• datagrams are transferred by different link protocols over different links:
  
  • e.g., Ethernet on first link, frame relay on
    intermediate links, 802.11 on last link
• each link protocol may provide quite different
  services
  
  • e.g., may or may not provide reliability

transportation analogy:
- trip from Lancaster to Lausanne
* Lancaster to MCR: taxi
* MCR to Geneva: plane
* Geneva to Lausanne: train
- datagram = tourist
- communication link = transport segment
- link-layer protocol = transportation mode
- routing algorithm = travel agent

Question 3

Link layer sub-layers
logical link control (LLC) sublayer

Answer 3

• abstraction of passing a datagram over a link
• “higher” level mechanisms like flow control, reliability

Question 4

Link layer sub-layers
medium access control (MAC) sublayer

Answer 4

• interfaces directly with the hardware
• e.g. mediates access to a physical broadcast medium
• MAC addresses are used in frame headers to identify source, destination

Question 5

Where is the link layer implemented?

Answer 5

• in each and every node!
• in an “adaptor” (aka network interface card NIC) or on a chip
  
  • Ethernet card, 802.11 card; Ethernet chipset
  • implements link, physical layer
• attaches into host’s system bus
• combination of hardware, software, firmware

Question 6

Two main types of “links”

Answer 6

• point-to-point
  
  • PPP for dial-up access
  • point-to-point link between Ethernet switch, host
  • frame relay
• broadcast (shared wire or medium)
  
  • old-fashioned Ethernet
  • 802.11 wireless LAN
  • this is our focus…

Question 7

MAC protocols for broadcast media

Answer 7

Taxonomy: we’ll look at two main classes:

• channel partitioning
• divide channel into smaller “pieces” (time slots, frequency bands)
• allocate a piece to a broadcast link’s channel for exclusive use by a node
• random access
• channel not divided, allow collisions
• … and then “recover” from collisions

Question 8

Channel partitioning MAC protocols: TDMA

Answer 8

TDMA: time division multiple access

§ access to channel is structured in “rounds” of time
§ each node, or “station”, gets a fixed length slot in each round (slot length = frame transmission time)
§ example: 6-station LAN, 1,3,4 have frames to send, slots 2,5,6 idle

Question 9

Channel partitioning MAC protocols: FDMA

Answer 9

FDMA: frequency division multiple access
- channel spectrum is divided into frequency bands
- each station is assigned a fixed frequency band
- example: 6-station LAN, 1,3,4 have packet to send, frequency bands 2,5,6 idle

Question 10

Random-access protocols

Answer 10

• when a node has a frame to send
  
  • transmit at full channel rate R
  • no a priori coordination among nodes
• two or more transmitting nodes ➜ “collision”,
• random access MAC protocol specifies:
  
  • how to detect collisions
  • how to recover from collisions (e.g., via delayed retransmissions)
• examples of random access MAC protocols:
  
  • CSMA/CD
  • but also ALOHA, CSMA, CSMA/CA, …

Question 11

CSMA (carrier sense multiple access)

Answer 11

CSMA: listen before transmit:
if channel sensed idle: transmit entire frame
if channel sensed busy: defer transmission
human analogy: don’t interrupt others when
they’re talking!

Question 12

CSMA collisions

Answer 12

§ collisions can still occur: propagation delay means two nodes may not hear each other’s
transmissions

§ collision: entire frame transmission time wasted

• plus, frame is not delivered – will need to
  be re-sent by higher-level protocol if reliability is needed

Question 13

CSMA/CD (collision detection)

Answer 13

CSMA/CD: carrier sensing, deferral as in CSMA
* collisions detected within short time
* colliding transmissions are aborted, thereby reducing channel wastage

• collision detection:
  
  • easy in wired LANs: compare transmitted, received signals
  • difficult in wireless LANs: received signal strength is overwhelmed by local transmission strength
• human analogy: the polite conversationalist

Question 14

CSMA/CD (collision detection)

Answer 14

Question 15

Ethernet

Answer 15

the “dominant” wired LAN technology:
- single chip, multiple speeds (e.g., Broadcom BCM5761)
- first widely used LAN technology
- simple, cheap
- has managed to keep up with speed race: 10 Mbps – 10 Gbps

Question 16

Ethernet CSMA/CD algorithm

Answer 16

1. NIC receives datagram from network layer,
   creates frame
2. If NIC senses channel idle, starts frame
   transmission. If NIC senses channel busy,
   waits until channel idle, then transmits
3. If NIC transmits entire frame without detecting another transmission, NIC is done with frame !
4. If NIC detects another transmission while
   transmitting, aborts and sends jam signal
5. After aborting, NIC enters binary (exponential) backoff:
   
   • waits to try again – and there’s a random
     element to wait time: minimise probability of
     another collision

Question 17

Ethernet: physical topology

Answer 17

• bus: popular through mid 90s
  
  • all nodes in same collision domain (can collide with each other)
• star: prevails today
  
  • active switch in center
  • each “spoke” runs a (separate) Ethernet protocol instance (nodes do not collide with each other)

Question 18

Ethernet frame structure

Answer 18

sending NIC encapsulates an IP datagram in an Ethernet frame

preamble: 8 byte pattern used to synchronize receiver, sender clock rates
- other fields…

Question 19

Ethernet frame structure (more)

Answer 19

• addresses: 6 byte source, destination MAC addresses
  
  • if NIC receives frame with matching destination address, or with broadcast address (e.g. ARP packet – see later), it passes data in frame up to network layer protocol
  • otherwise, NIC discards frame
• type: indicates higher layer protocol (usually IP)
• CRC: cyclic redundancy check at receiver
  
  • error detected => frame is dropped

Question 20

Ethernet: connectionless, unreliable

Answer 20

• connectionless: no handshaking between sending and receiving NICs
• unreliable: receiving NIC doesn’t send acks or nacks to sending NIC
  
  • data in dropped frames is recovered only if sender uses a reliable protocol on top (e.g., TCP), otherwise dropped data is lost

Question 21

MAC addresses in LANs

Answer 21

• we already know about IP addresses…
  
  • 32 bits
  • network-layer address for interface
  • function: layer 3 (network layer) forwarding
• MAC (or LAN or physical or Ethernet) address:
  
  • function: used ‘locally” to get a frame from one interface to another phy-connected interface (i.e., across a single network, in the IP-addressing sense)
  • for most LANs, this is a 48 bit MAC address burned into the NIC’s ROM
  • e.g.: 1A-2F-BB-76-09-AD

Question 22

ARP: address resolution protocol

Answer 22

Question: how to determine an interface’s MAC address, knowing its IP address?

ARP table: each IP node (host, router) on LAN has a table
* IP/MAC address mappings for local LAN
nodes:
< IP address; MAC address; TTL>
* TTL (Time To Live): time after which address
mapping will be forgotten (typically 20
min)

Question 23

ARP protocol: same LAN

Answer 23

• A wants to send a datagram to B
  
  • B’s MAC address not in A’s ARP table.
• A broadcasts an ARP query packet, containing B’s IP address
  
  • destination MAC address = FF-FF-FF-FF-FF-FF
  • broadcast: all nodes on the LAN receive ARP query
• when B receives the ARP packet, it replies to A with its (B’s) MAC address
  
  • frame sent to A’s MAC address (unicast)
• A caches saves the IP-toMAC address pair in its ARP table until information becomes old (times out)
  
  • soft state: information that times out (goes away) unless refreshed
• ARP is “plug-and-play” :
  
  • nodes create their ARP tables without intervention from net administrator

Question 24

Addressing: routing to another LAN

Answer 24

walkthrough: send datagram from A to B via R

• focus on addressing – at IP (datagram) and MAC layer (frame)
• assume A knows B’s IP address
• assume A knows IP address of first hop router, R
• assume A knows R’s MAC address
• A creates IP datagram with IP source A, destination B
• A creates link-layer frame with R’s MAC address as destination address,
  frame contains A-to-B IP datagram
• frame sent from A to R
• frame received at R, datagram removed, passed up to IP
• R forwards datagram with IP source A, destination B
• R creates link-layer frame with B’s MAC address as destination address, frame contains A-to-B IP datagram

Question 25

Summary

Answer 25

- a link layer protocol (layer-2 protocol) is implemented in all “nodes” (i.e. all hosts and routers) - there may be many different link layer protocols underlying an end-to-end route through the internet - many link layer protocols are LAN-based and employ broadcast media * of these, there are many design options for how to share the media among multiple nodes (“stations”) * we’ve had a look at Ethernet…