Link Layer (Summary)

COMP211 Lectures Summaries 2021-11-12

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

The link layer concerns the links that connect various nodes (hosts and routers) on a network. The link layer only needs to transfer a frame from a node to an adjacent node.

Services

The link layer provides the following services:

Datagram encapsulated in frames with a header and trailer.
Channel access for shared mediums.
MAC addresses in frame headers identify source and destination.
Reliable delivery between adjacent nodes:
- Used on links with high error rates.
Flow Control
Error Detection
Error Correction
- The receiver corrects errors without re-transmission.

Hardware Implementation

The link layer is implemented in the network interface. This can be:

NIC (Network Interface Card)
Built-in network cards.

Network interfaces also implement the physical layer too as they physically connect to the network.

graph
subgraph computer
CPU --- Bus
Bus --- Memory
Bus --- Controller
Controller --- Physical
subgraph NIC
Controller
Physical
end
end
Physical --- Network

Error Detection

Error detection isn’t always 100% reliable:

Larger check-sums yield better detection and correction

Parity Checking

Single bit parity can detect single bit errors:

$d$ Data Bits	Parity Bit
0111101001010010111101	1

Two dimensional bit parity can detect and correct single bit errors:

$d_{1,1}$	$\ldots$	$d_{1,j}$	$d_{1,j+1}$
$d_{2,1}$	$\ldots$	$d_{2,j}$	$d_{2,j+1}$
$\ldots$	$\ldots$	$\ldots$	$\ldots$
$d_{i,1}$	$\ldots$	$d_{i,j}$	$d_{i,j+1}$
$d_{i+1,1}$	$\ldots$	$d_{i+1,j}$	$d_{i+1,j+1}$

The right most column and bottom row are the parity bits.
The parity of a row or column is the single bit sum of that row or column.
The bottom right parity digit can be used as singe bit parity for the parity bits.

Cyclic Redundancy Check (CRC)

This is a more powerful error-detection coding:

$D$ - Data bits given as a binary number.
$G$ - Bit pattern (generator), or $r+1$ bits.

One bit longer than the number of CRC bits.

We need to choose $r$ CRC bits, $R$ such that $<D,R>$ exactly divisible by $G$ (mod 2):

Receiver knows $G$, divides $<D,G>$ by $G$. If non-zero remainder then an error is detected.
Can detect all burst errors less than $r+1$ bits.

This method is used in Ethernet and WiFi.

CRC Example

Before we divide by the generator $G$ we shift the data $D$ to the left by $r$ bits, or the length of the generator - 1:

\[R = \text{remainder}[\frac{D\cdot2^r}{G}]\]

To calculate this we do modulo 2 division on data using the generator completing an XOR in each step:

Example of modulo 2 division.

Multiple Access Protocols

Broadcast links are a shared link such as WiFi. If two or nodes transmit at the same time then there is interference:

Collision - If a node receives two or more signals at the same time.

Ideally, multiple access protocols are distributed algorithms that have the following properties:

Determine how nodes share the channel.
- Determine when nodes can transmit.
Communication about channel sharing must use the channel.
- No out of band channel coordination is allowed.
When one node wants to transmit, it can do so at the line speed.
When multiple nodes transmit, they can do so at an equal divisor of the line speed.
Fully decentralised:
- No special nodes.
- No synchronisation of clocks.

There are three broad classes of multiple access channel protocols:

Channel Partitioning
- Divide channel into smaller pieces (time, frequency, code).
- Allocate piece to node for exclusive use.
Random Access
- Channel not divided, allowing collisions.
- Recover from collisions.
Taking Turns
- Nodes take turns, but nodes with more to send can take longer turns.

Time Division Multiple Access (TDMA)

Access to channel in rounds.
Each station gets a fixed length slot (length = packet transmission time) in each round.
Unused slots go idle.

Frequency Division Multiple Access (FDMA)

Channel spectrum divided into frequency bands.
Each station assigned fixed frequency bands.
Unused transmission time in frequency bands go idle.

Random Access Protocols

Slotted ALOHA

Slotted ALOHA has the following assumptions:

All frames are the same size.
Time is divided into equal size slots (time to transmit 1 frame).
Nodes start to transmit only slot beginning.
Nodes are synchronised.
If 2 or more nodes transmit in slot, all nodes detect collision.

It operates like so:

When node obtains fresh frame transmit in the next slot.
- If no collision - Node can send new frame in next slot.
- If collision - Node re-transmits frame in each subsequent slot with probability $p$ until success.
  
  Randomisation is included such that different nodes don’t re-transmit at the same time.

Carrier Sense Multiple Access (CSMA)

The simple implementation listens before transmit:

If channel is sensed idle - Transmit entire frame.
If channel sensed busy - Defer transmission.

Collision detection (CSMA/CD) is implemented like so:

Collisions detected within short time.
Colliding transmissions aborted, reducing channel wastage.
- You can abort before the whole frame is transmitted.
Collision detection is difficult in wireless when you can’t listen to the entire broadcast area or you transmit and receive on the same areal.

Propagation delay can cause collisions, as you can start transmitting before you have heard an existing transmission.

Ethernet CSMA/CD Algorithm

NIC receives datagram from network layer, creates frame.
If NIC senses channel:
- If idle - Start frame transmission.
- If busy - Wait until channel idle, then re-transmit.
If NIC transmits entire frame without collision, NIC is done with frame.
If NIC detects another transmission while sending - Abort send and send jam signal.
After aborting, NIC enters binary exponential backoff:
- After $m^\text{th}$ collision, NIC chooses $K$ at random, from $\{0,1,2,\ldots,2^{m}-1\}$. NIC waits $K\times512$ bit times, returns to step 2.
- More collisions result in higher backoff interval.

Taking Turns Protocols

Polling

Master node invites other nodes to transmit in turn.
Typically used with dumb devices.

This method can the following issues:

Polling Overhead
Latency
Single point of failure.

Token Passing

Control token passed from one node to the next sequentially.
Node with token can transmit.

This method can the following issues:

Token Overhead
Latency
Single point of failure (token)

LANs

MAC Addresses

MAC addresses are used to get a from from one interface to another physically connected interface. They are a 48-bits long and are generally burned into the NIC ROM:

\[\text{1A-2F-BB-76-09-AD}\]

They are designed to be unique.
- Each manufacturer buys a portion of the MAC address space from the IEEE.
MAC addresses are portable (with the NIC) from one LAN to another.

Address Resolution Protocol (ARP)

Each IP node on a LAN has a table that tracks IP to MAC address mappings:

IP Address	MAC Address	TTL

TTL (time to live) is typically set to 20 mins.

Suppose that $A$ wants to find $B$’s MAC address:

$A$ broadcasts ARP query, containing $B$’s IP address:
- Destination MAC address is FF-FF-FF-FF-FF-FF.
- All nodes on LAN receive ARP query.
```
 Source MAC: 71-65-F7-2B-08-53
 Source IP: 137.196.7.23
 Target IP address: 137.196.7.14
```

$B$ will send its MAC address back to $A$:

 Target IP address: 137.196.7.14
 Target MAC address: 58-23-D7-FA-20-B0

$A$ receives $B$’s reply and logs it in its local ARP table:

IP Address MAC Address TTL

137.196.7.14 58-23-D7-FA-20-B0 500

IP Address	MAC Address	TTL
137.196.7.14	58-23-D7-FA-20-B0	500

Ethernet

Ethernet can have the following topologies:

Bus - All noes in the same collision domain.
Switched:
- Active link-layer 2 switch in the centre.
- Each spoke runs a separate Ethernet protocol.

Ethernet Frames

The sending interface encapsulates the payload in an Ethernet frame:

graph
subgraph frame
preamble
destAddress
sourceAddress
type
data
CRC
end

Preamble - used to synchronise the receiver and sender clock rates. 7 bytes of 10101010 followed by one byte of 10101011.
Addresses - MAC addresses. If an adaptor receives a frame with it’s own address or a broadcast it is passed up to the network layer. Otherwise the frame is discarded.
Type - Indicates higher layer protocol (IP, Novell, IPX, AppleTalk).
CRC - If errors are detected the frame is dropped.

Ethernet Properties

Connection-less - No handshaking between sending and receiving NICs.
Unreliable - Receiving NIC doesn’t send ACKs to the sending NIC.
Ethernet MAC Protocol - Un-slotted CSMA/CD with binary backoff.

There are many different 802.3 Ethernet standards. They define:

Different speeds.
Different physical layer media.

Switches

An Ethernet switch is a link-layer device that takes and active role:

Store and forward Ethernet frames.
Examine incoming frame’s MAC address and selectively forward frames to one-or-more outgoing links. When the frame is to be forwarded on segment it uses CSMA/CD to access the segment.

The host is unaware of switches as they are transparent.

The difference between switches and routers are that switches are layer 2 devices and routers are layer 3.

Multiple Simultaneous Transmissions

When there are multiple transmissions:

Each device can operate at full link speed.
Transmissions to all different interfaces can happen simultaneously.
Transmissions to the same interface will get buffered.

Switch Tables

These record which hosts can be reached through each interface. They are not managed by a routing protocol.

When a node sends a frame then the switch records the senders MAC address and interface.
When the destination is unknown then it floods all other interfaces with the frame.
If the destination address is in the switch table then the frame is sent on that interface.

Wireless Links & WLAN

Wireless links have the following characteristics compared to wired links:

Decreased Signal Strength - Radio signal attenuates as it propagates through matter (path loss).
Interference - Wireless network frequencies can be shared by many devices.
Multi-path Propagation - Radio signals can reflect off objects and arrive at the destination at slightly different times.

IEEE 802.11 Wireless LAN

This standard includes WiFi and all use CSMA/CA for multiple access and have base station and ad-hoc variants.

Multiple Access (CSMA/CA)

IEEE 802.11 implements the following to facilitate multiple access:

CSMA - Sense before transmitting to not collide with existing transmissions.
No collisions detection. Instead collision avoidance (CSMA/CA) is implemented.
- Collision detection is impossible in wireless settings as you can’t listen to the whole network from one device.

802.11 Sender

We must first reserve the channel using small reservation packets:

Sender transmits a small request to send (RTS) packet to the base-station using CSMA.
- These may collide but they are short.
Base station broadcasts a clear to send (CTS) in response to the RTS.
CTS is heard by all nodes:
- Sender continues to send data.
- Other stations defer transmissions.

To send the data we complete the following:

If we sense the channel is idle for DIFS (a set amount of time to sense) then transmit the entire frame (no CD).
If we sense the channel is busy then start random backoff timer. Transmit when timer expires if the channel is idle.
If no ACK increase random backoff interval, repeat 2.

802.11 Receiver

If frame received OK, return ACK after SIFS (short time after receiving).

RTS-CTS Exchange

sequenceDiagram
par
A ->> AP:RTS(A)
and
note over AP: Reservation collision.
and
B ->> AP:RTS(B)
end
A ->> AP:RTS(A)
par
AP ->> A:CTS(A)
and
AP ->> B:CTS(A)
end
note over B:Defer until ACK(A)
A ->> AP:Data(A)
par
AP ->> A:ACK(A)
and
AP ->> B:ACK(A)
end

Blocks called par happen in parallel.

As this is a shared medium, $A$ and $B$ have the chance of seeing each other’s messages (albeit with some propagation delay). The only node that you are guaranteed to receive from is the AP.