Link Layer: 考虑怎样在链路上确保数据的有效传输
基本概念
A computer network is a set of nodes that are connected together by communication links.
- Nodes: Computers, Switches, Routers, Hubs, Printers, and Servers.
- Links: Fiber optics, Coaxial pair cable, Copper, Radio wave, Micro wave
- i.e., communication channels that connect adjacent nodes
Link layer has responsibility of transferring datagram from one node to physically adjacent node over a link.
错误检测
奇偶校验
Parity，错误检测方案最基本的方法
- 为了检测出数据传送过程中可能出现的错误，通常在二进制编码中额外加上一个校验位，用于表示编码中 1 的个数是奇数还是偶数。
- 奇偶校验位 (Parity bit) 也称校验位 (check bit) 或 冗余位 (redundant bit)
- 偶校验 (even parity)：当字符编码中 1 的个数为偶数时，校验位为 0
- 奇校验 (odd parity)：当字符编码中 1 的个数为奇数时，校验位为 0
ㅤ | 偶校验 | 奇校验 |
1000001 | 01000001 | 11000001 |
多维度奇偶校验
Multidimensional parity-check code (MDPC)
奇偶校验将数据块中的所有比特位相加，并根据和的奇偶性来确定奇偶校验位的值。
BH 位置上的数据错误，因为水平和垂直列的奇偶校验与预期不符 。
校验和
循环冗余检测
Lecture 5 Cyclic Redundancy Check, CRC
核心思想：将传输的数据当做一个位数很长的数。将这个数除以另一个数。得到的余数作为校验数据附加到原数据后面。
发送端
模 2 除法 可以视为 XOR 运算
→ 如果两个输入位相同，则输出 0；如果两个输入位不同，则输出 1。
- 初始部分
1011，执行 XOR1001，结果为0100。
- 将
0100右移一位并添加下一个位：0100，执行 XOR1001，结果为1000。
- 将
1000右移一位并添加下一个位：0000，执行 XOR1001，结果为0010。
- 将
0010右移一位并添加下一个位：0100，执行 XOR1001，结果为1000。
- 将
1000右移一位并添加下一个位：0000，执行 XOR1001，结果为0010。
- 将
0010右移一位并添加下一个位：0100，执行 XOR1001，结果为1000。
- 将
1000右移一位并添加下一个位：0000，执行 XOR1001，结果为0100。
- 将
0100右移一位：010，没有更多的位可以添加，即这是最终的余数。
接收端
与发送端使用相同的除数，余数为 0 说明数据正确
多路访问协议
Multiple access protocols，MCP，协调多个用户如何高效共享一个物理链路资源
信道划分协议
Channel partitioning protocol，将信道的资源划分成较小的部分来管理（固定多址）
TDMA
Time division multiple access
- Transmission time on a single channel is divided into nonoverlapped time slots.
- Signals from different sources are divided into units with same size.
- Access to channel in “rounds”.
FDMA
Frequency division multiple access
- The total bandwidth is divided into a series of nonoverlapping frequency sub-bands.
- Channel spectrum is divided into frequency bands.
随机访问协议
Random access protocol ，通过采取某种机制来解决用户发送数据带来的冲突（随机多址）
Pure (unslotted) ALOHA
不监听信道，不按时间槽发送，随机重发
只要有新的分组到达，就立即被发送并期望不与别的分组发生碰撞。一旦分组发生碰撞，则随机退避一段时间后进行重传。
Slotted ALOHA
用时钟来统一用户的数据发送
时隙开始传送，时隙宽度为分组传输时间，易受破环区间为一个时间单位。
CSMA
Carrier sense multiple access，载波监听多路访问，在 ALOHA 的基础上加入了数据传输前的线路检查，其包含几种不同的方案
- Non-Persistent: 对于发送端的每次传输请求，都先检查线路是否空闲，若空闲，则立刻传输数据；若线路忙碌，则等待一段随机长度的时间后再重新尝试传输，以避免多个发送端同时提起发送请求的情况。并且每一次迭代都将增加等待时间的长度。在该方案下，线路有可能在发送端等待的时间里处于空闲状态，造成线路资源的浪费。
- P-Persistent: 对于发送端的每次传输请求，都先检查线路是否空闲，若空闲，则存在两种情况，一种为立即发送数据（概率为 p）；另一种则为延后一段固定的时间后再重新尝试传输（概率为1-p）。而如果线路忙碌，则持续等待，直到线路空闲后再开始上述过程。
- …
轮转协议
Taking-turns protocol
Token Passing Protocol
- 令牌生成：网络中的一个节点（主节点或监控站）生成一个作为“令牌”的特殊数据包。
- 令牌传递：令牌沿着网络中的节点顺序传递。每个节点轮流获得令牌。
- 发送数据：当一个节点获得令牌时，它有权发送数据。如果节点没有数据要发送，它会将令牌传递给下一个节点。
- up to some max time
- 接收确认：发送数据后，发送节点等待接收到确认，然后释放令牌，将其传递给下一个节点。
- 令牌循环：这个过程持续进行，令牌在网络中的节点间循环传递。
Sliding Window Protocol
- 窗口大小：发送方和接收方各自维护一个“窗口”，其大小决定了可以发送的数据量，以及没有收到确认的数据量。
- 发送数据：发送方发送一系列数据帧。
- 接收确认：接收方收到数据帧后，发送确认（ACK）回发送方。确认通常包括下一个期望接收的帧的序号。
- 窗口滑动：当发送方接收到确认后，它会“滑动”其窗口，允许发送更多的数据帧。窗口向前移动的距离取决于接收到的ACK。这意味着已确认的帧会从窗口中移出，为新的数据帧腾出空间。
Go-Back-N: 回退 N 重传
- 发送方可以发送多个帧，但它必须保持这些帧的副本直到它们被确认。
- 如果一个帧丢失或发生错误，接收方将丢弃该帧及其后的所有帧，即使它们可能已经正确接收。
Selective Repeat: 选择重传
- 发送方可以发送多个帧，接收方接受和存储出错帧之后的帧。
- 如果一个帧丢失或错误，接收方只需丢弃错误的帧，而不是丢弃随后的帧。
MAC
局域网地址（LAN）通常被称为 MAC 地址（Media Access Control Address），用于确保数据包在同一网络或子网内正确地从一个物理设备传输到另一个物理设备。
它是一个固定长度（通常为 48 位或 6 个字节）的地址，固定分配给网络设备硬件的，通常被烧录在网络接口卡上，不依赖于网络所在的位置。它以十六进制数表示，格式如
00:1A:2B:3C:4D:5E。
- 交换机（Switch）主要工作在链路层，有些高级交换机也能执行部分网络层的功能，被称为多层交换机。
- 它用于连接网络中的多个设备（如计算机、打印机等），并在它们之间转发数据帧。它还能够学习和存储 MAC 地址信息，从而有效地将数据帧直接从一个端口转发到目的端口。
地址解析协议
Lecture 5 Address Resolution Protocol, ARP
在同一个 LAN 内解析或获取目标 IP 地址对应的 MAC 地址
How to determine interface’s MAC address, knowing its IP address?
- 当一个设备需要知道另一个设备的物理地址（MAC 地址），但只知道其 IP 地址时，它会发送一个 ARP 请求包。这个请求包在局域网内广播，询问拥有指定 IP 地址的设备。
- 网络上所有的设备都会收到这个 ARP 请求，但只有 IP 地址与请求中指定的 IP 地址匹配的设备会回应。
- All nodes on LAN receive ARP query
- 匹配的设备会回复一个 ARP 响应，其中包含其物理地址。
- 发送ARP请求的设备收到响应后，会将 IP 地址与物理地址的对应关系存储在本地的 ARP 缓存中，以便将来的通信使用。
APR 将发到当前 LAN （MAC → 收件地址）的数据包，找到具体的 IP （收件人）