Link Layer and Switching

Topics Covered: Link Layer, ALOHA, CSMA/CD, Ethernet Switching

Link Layer

The link layer is responsible for transferring packets between two physically connected nodes (routers, hosts). Like IP or TCP, there is a link layer packet which the upper layers are encapsulated within. Rather than IP, we use something called MAC (Medium Access Control) addressing, which are 48 bits long, and grouped into 6 groups of 8 bits each with some separator. The link layer frames data (marks start and end), detects errors, but mostly we will discuss its ability to manage channel access through a suite of protocols.

Note: I've been mostly referring to everything as a packet regardless of layer. Technically they have different names. Packet is specific for IP, segment for TCP, datagram for UDP (easy way to remember is that TCP is stream protocol), data frame for link. Frames' end are denoted by 01111110. If 01111110 appears in the data, then it is replaced by 0111111001111110 (similar logic to escaping a \ in C).

ARP

ARP (Address Resolution Protocol) runs on every IP node, and is tasked with constructing a table of IP Address: MAC Address : TTL tuples. The TTL is actually important here. This table resembles a soft-state cache: the TTL is reset when there is a lookup, and the entry deletes itself after TTL expires.

Here's how it works.

Let's say hosts A and 10.0.0.2 (which we will refer to as B from now on), are on the same LAN. At first, A does not know the MAC address of B, but A knows the IP address of B. A will broadcast an ARP query (destination MAC FF-FF-FF-FF-FF-FF which is link layer equivalent of 255.255.255.255). The switch in the middle (we'll get to this later) will broadcast to all connected nodes, and B will reply with its MAC address, which the switch will relay to A. A then fills out an entry in its ARP table with B's info, and B does the same with A. Simple as that.

Random Access Protocols Inspiration

Multiple Access Control refers to the fact that we have a bunch of nodes and they all use the same medium to transfer frames, so we need to come up with a way to share the resource efficiently. One idea is to have some master node regulate who sends and when, but that's pretty bad, since we would need the overhead of polling and increased latency, and if the master node goes down then nothing gets sent. So we use random access protocols, which are probablistic (therefore not perfect) but generally are more efficient than the alternative. We'll define the imperfections as collisions, when two or more senders are trying to transmit at the same time. So our goal is then to figure out:

1. How to detect a collision
2. How to recover from a collision, and make sure everyone gets to transmit

ALOHA

Originally developed for a wireless network in Hawaii, this isn't really relevant nowadays but it's a good starting point for motivation. I would focus more on CSMA/CD and CSMA/CA for your studying.

The basic idea is that if a node has data to send, then send it immediately. If there is a collision, then retransmit with probability

$p$.

Slotted ALOHA

Divide time into fixed-size interval "slots", and a collision is when two or more nodes try to transmit at the beginning of that slot. Otherwise we maintain the retransmission in subsequent slots with probability

$p$ until success. Slotted ALOHA is more efficient than standard ALOHA. I'll omit the calculations for efficiency, since the course slides are adequately concise and this isn't a math class.

CSMA/CD

The key idea behind CSMA (Carrier Sense Multiple Access) is that instead of transmitting naively, we sense the channel beforehand (like a scan) to make sure it's idle. If it's busy, then wait. If it is idle, then we do one of three things:

1. 1-persistant CSMA: retry immediately
2. p-persistant CSMA: retry immediately with probability
   $p$
3. Non-persistant CSMA: retry after some random interval

Reminder: collisions are still possible. These solutions are probablistic.

CD (Collision Detection) is just a way to detect whether a collision occurred quickly. If the transmitted signal is not the same as the received signal, then abort.

Ethernet CSMA/CD

• Use 1-persistent transmission
• If collision detected (CD) after transmitting even after originally thought idle, then abort
• Enter binary exponential backoff, meaning that after the
  $m$th collision, choose
  $K\in \{0,1,2,\dots ,2^m-1\}$ at random, and wait
  $K$ slots before trying to transmit again.
  • After 4th collision, choose
    $K\in \{0,1,2,3,4,5,6,7\}$ randomly. So each choice has probability
    $\frac{1}{8}$.

Switching

Switches are like the "routers" of the link layer, with a few key differences. They speak Ethernet protocol at each interface, and hosts are not aware of the presence of a switch. They are plug-and-play devices (no configuration required), but use a similar store-and-forward as routers. They also keep track of a forwarding table, containing a map of Host MAC Addr : Interface for Host MAC Addr along with a TTL.

These forwarding tables are self-learned (hence the plug-and play).

• When a frame arrives at a switch interface, look at the source MAC address
  • If we already have an entry with matching information in the forwarding table, then reset TTL
  • Otherwise, add the source MAC and the interface where it arrived on
• Look up the destination MAC
  • If we already have an entry for the destination MAC, then forward the frame to the corresponding interface
  • Otherwise, broadcast (flood all interfaces except the one it arrived on).

On problems involving multiple connected switches, don't overcomplicate things. Go through the above algorithm for each switch and fill out the forwarding tables at each step.

Next Week's Topics: Wireless, Mobility, Indirect Routing, Brief Cumulative Review