# 50.012 Lecture 17
# Link Layer
Textbook section 6.1, 6.2, 6.4
## Introduction
Terminologies:
* Hosts and routers: **Nodes**
* Communication channels that connect adjacent nodes along communication path: **Links**
* Wired Links
* Wireless Links
* Layer-2 Packet is known as **frame**, which encapsulates datagram.
* Data-link layer has the responsibility of transferring datagram from one node to *physically adjacent* node over a link.

## Types of Links
### Point-to-Point
There are only 2 ends in this type of link.
e.g.
* PPP (Point-to-point Protocol) is used for dial up access.
* Ethernet provides PP link between one port of the switch and the host.
### Broadcast (Shared Wire or Medium)
More than 2 nodes sharing the same link.
* Old-fashioned Ethernet
* Upstream HFC (used in cable TV)
* 802.11 wireless LAN
* When we talk in a group

## Context


The responsibility of the link layer is to send a frame from one node to its adjacent node (i.e. the nodes within the link layer broadcasting domain: we're supposed to be able to reach to the adjacent node within one hop, without going through the router).
When packet (datagram) travels from one host to another, it can be transferred over different link protocols over different links.

e.g. 802.11 on first link, PPP on second link, Ethernet on last link.

Each link protocol may provide different services. They may or may not provide reliable data transfer (rdt) over link.

:::info
There are different protocols used in the Transport layer, and different protocols used in the Link layer. However, the IP is the common protocol that is used in the Network layer that link these 2 layers.
:::

## Link Layer Services
### Framing, Link Access
* To encapsulate datagram into frame, adding header and trailer.
* If the link is a shared link, it also has to coordinate how each node accesses the channel.
* MAC (Medium Access Control) addresses are used in the frame headers to identify sources and destinations.

### Reliable Delivery between Adjacent Nodes
* Seldom used on low bit-error link (e.g. in fibers, there can be only few twisted pairs). We assume that most if not all the packets cross without any problem.
* However, in wireless links, the error rates are high.
* We need a way to do error recovery. Although rdt is implemented on TCP, link layer rdt is implemented to further improve the network performance.
e.g. if WiFi detects erroneous packets, the transmitter will try to retransmit (recover) (up to certain number of times) from the error.

### Half-Duplex vs. Full-Duplex
* More relevant for PP links
* Whether the 2 nodes can transmit at the same time or not.
* Half duplex allows both nodes of the link to transmit, but not at the same time.
* e.g. if we have a PP WiFi setup: Traditional WiFi operates on half duplex. If WiFi transceiver transmits and receives at the same time, the WiFi signal at the receiver side actually drops significantly and the receiver will be overwhelmed by the transmitter's own signal.
* Modern Ethernet with switches operate on full duplex.

### Multiple Access Protocol
Motivation Problem: 2 nodes simultaneously transmitting to each other will result in interference, causing a collision if node receives 2 or more signals at the same time.

It is a single shared broadcast channel. It is designed as a distributed algorithm that determines how nodes share channel (i.e. determine when a node can transmit).

Usually there is no separate control channel to coordinate the multiple access. Hence, we have to use the same channel to do so.

Given: broadcast channel of rate R bps.
Desiderata:
1. When one node wants to transmit, it can send at rate R.
2. When M nodes want to transmit, each can send at average rate R/M.
3. Fully decentralized:
* No special node to coordinate transmissions.
* No synchronization of clocks, slots.
4. Simple

### Implementation of Link Layer
Network and transport layers are usually implemented in the software level

Link layer is implemented in every host, in the "adaptor" (network interface card, NIC) or on a chip.

It attaches into host's system buses, and is a combination of hardware, software, and firmware.

#### Adaptors Communications
The interface between the network layer and the link layer is the network layer in the OS after the transport layer packet is encapsulated into a datagram.

Afterwards, this datagram will be sent to the host bus, and subsequently into the NIC.

This encapsulation (adding header and trailer) happens inside the NIC. It will then sent to the physical layer over the link.

At the receiver end, the physical layer will first process it and forward it to the link layer. Link layer will check for errors, rdt, flow control, etc. before extracting the datagram. The datagram will be the information that leaves the NIC and travel across the bus to the CPU.

### Local Area Network (LAN)
LAN is the first link that the packet will go through.

#### MAC Address
In a LAN, there are multiple nodes, with a router. If there are a lot of hosts within the same layer, they need to identify (without going through the router) the list of hosts that are within the same LAN.

In IPv4, the 32-bit IP Address was used for the network layer to identify which interface to forward the packet to.

In Link layer, MAC (or LAN or Ethernet) address is used to locally get frame from one interface to another physically-connected interface (same network in IP-addressing sense).
48-bit MAC address (for most LANs) are burned in NIC ROM, and is also sometimes software settable (ARP Spoofing).
e.g. IA-2F-BB-76-09-AD (hex notation), each numeral represents 4 bits.
Usually, the first 3 bytes contain the manufacturer's identifier (by IEEE) and the rest is assigned by manufacturers.
#### LAN Address

Each adapter on LAN has a unique LAN addresses.
IP Address is used to route packets to destination, whereas MAC Address is used to identify NIC.

The fact that MAC has a flat address means portability: LAN card can be moved from one LAN to another.

In contrary, IP hierarchical address is not portable. Address depends on IP subnet to which node is attached.

### Address Resolution Protocol (ARP)


Motivation question: Given an IP Address, how to determine the interface's MAC Address?

For each interface, there is an ARP table. Each row of this table contains the IP/MAC address mappings for some LAN node, and the Time To Live (TTL), which is the time after which this address mapping will be forgotten.

#### ARP within LAN
* A wants to send datagram to B. However, B's MAC Address is not on A's ARP table.
* A broadcasts ARP query packet that contains B's IP Address.
* Destination MAC Address is set to FF-FF-FF-FF-FF-FF
* All nodes on LAN receive this ARP query.
* A also puts A's MAC Address as the source MAC Address.
* B receives ARP packet and it will first check whether the IP Address specified in the query packet matches its own. If it does, B replies to A with B's MAC Address.
* Frame is sent to A's MAC Address.
* When B's reply reaches A, A will save the IP-to-MAC address pair in its ARP table, along with a TTL.
* This information is a soft state: it times out unless refreshed.
* ARP is "plug-and-play":
* When nodes come in and want to talk to some previously unknown neighbors, they don't have to be pre-configured. Each node is able to construct its own ARP table without any configuration needed.

#### ARP across Router
Assumptions:
* A knows about B's IP Address
* A knows IP Address of first hop router, R (through DHCP).
* A knows R's MAC Address (through ARP).

Procedure:

* A creates an IP datagram with IP source A and destination B. Before sending, A must first know that A and B are in different subnet (by looking at A's and B's network prefix).
* The IP Layer will send the datagram to the Link Layer. Link layer will then put the Link layer header (which includes the A's MAC address as the source MAC Address and R's MAC Address as the destination MAC Address) to the datagram. Recall: the Link Layer's main functionality is to ensure that the datagram is delivered to the adjacent note (i.e. from A to R).
* Once frame is sent from A to R, R will further process it in the IP layer. It will look up its IP forwarding table and choose which IP to forward it to.


* Once the IP layer finishes the forwarding decision, the packet will travel down the stack. A new link layer will be constructed at the NIC at the output port of R. The source and destination IP Address still remain the same (A and B's each). However, the MAC addresses changes such that the source MAC Address is R's and the destination MAC Address is B's MAC Address.
* Before sending the packet (on IP Layer), the interface will first check the destination IP address (of B) if it is within the same subnet as R. Since they are, R will use the ARP table to look up B interface's MAC Address to send to.
* This is so that when B replies, it knows which MAC Address to send the reply to.