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。

1. 初始部分 1011，执行 XOR 1001，结果为 0100。

2. 将 0100 右移一位并添加下一个位：0100，执行 XOR 1001，结果为 1000。

3. 将 1000 右移一位并添加下一个位：0000，执行 XOR 1001，结果为 0010。

4. 将 0010 右移一位并添加下一个位：0100，执行 XOR 1001，结果为 1000。

5. 将 1000 右移一位并添加下一个位：0000，执行 XOR 1001，结果为 0010。

6. 将 0010 右移一位并添加下一个位：0100，执行 XOR 1001，结果为 1000。

7. 将 1000 右移一位并添加下一个位：0000，执行 XOR 1001，结果为 0100。

8. 将 0100 右移一位：010，没有更多的位可以添加，即这是最终的余数。

接收端

与发送端使用相同的除数，余数为 0 说明数据正确

多路访问协议

信道划分协议

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.

随机访问协议

Pure (unslotted) ALOHA

💬

不监听信道，不按时间槽发送，随机重发

只要有新的分组到达，就立即被发送并期望不与别的分组发生碰撞。一旦分组发生碰撞，则随机退避一段时间后进行重传。

Slotted ALOHA

💬

用时钟来统一用户的数据发送

时隙开始传送，时隙宽度为分组传输时间，易受破环区间为一个时间单位。

轮转协议

Token Passing Protocol

1. 令牌生成：网络中的一个节点（主节点或监控站）生成一个作为“令牌”的特殊数据包。

2. 令牌传递：令牌沿着网络中的节点顺序传递。每个节点轮流获得令牌。

3. 发送数据：当一个节点获得令牌时，它有权发送数据。如果节点没有数据要发送，它会将令牌传递给下一个节点。
• up to some max time

4. 接收确认：发送数据后，发送节点等待接收到确认，然后释放令牌，将其传递给下一个节点。

5. 令牌循环：这个过程持续进行，令牌在网络中的节点间循环传递。

Sliding Window Protocol

1. 窗口大小：发送方和接收方各自维护一个“窗口”，其大小决定了可以发送的数据量，以及没有收到确认的数据量。

2. 发送数据：发送方发送一系列数据帧。

3. 接收确认：接收方收到数据帧后，发送确认（ACK）回发送方。确认通常包括下一个期望接收的帧的序号。

4. 窗口滑动：当发送方接收到确认后，它会“滑动”其窗口，允许发送更多的数据帧。窗口向前移动的距离取决于接收到的ACK。这意味着已确认的帧会从窗口中移出，为新的数据帧腾出空间。

1️⃣

Go-Back-N: 回退 N 重传

1. 发送方可以发送多个帧，但它必须保持这些帧的副本直到它们被确认。

2. 如果一个帧丢失或发生错误，接收方将丢弃该帧及其后的所有帧，即使它们可能已经正确接收。

2️⃣

Selective Repeat: 选择重传

1. 发送方可以发送多个帧，接收方接受和存储出错帧之后的帧。

2. 如果一个帧丢失或错误，接收方只需丢弃错误的帧，而不是丢弃随后的帧。

MAC

• 交换机（Switch）主要工作在链路层，有些高级交换机也能执行部分网络层的功能，被称为多层交换机。

• 它用于连接网络中的多个设备（如计算机、打印机等），并在它们之间转发数据帧。它还能够学习和存储 MAC 地址信息，从而有效地将数据帧直接从一个端口转发到目的端口。

地址解析协议

How to determine interface’s MAC address, knowing its IP address?

1. 当一个设备需要知道另一个设备的物理地址（MAC 地址），但只知道其 IP 地址时，它会发送一个 ARP 请求包。这个请求包在局域网内广播，询问拥有指定 IP 地址的设备。

2. 网络上所有的设备都会收到这个 ARP 请求，但只有 IP 地址与请求中指定的 IP 地址匹配的设备会回应。
• All nodes on LAN receive ARP query

3. 匹配的设备会回复一个 ARP 响应，其中包含其物理地址。

4. 发送ARP请求的设备收到响应后，会将 IP 地址与物理地址的对应关系存储在本地的 ARP 缓存中，以便将来的通信使用。