计网学习笔记二 Link Layer Service
在上一周的计网学习了network和Internet的总论。在这一周开始的未来几讲将集中在链路层
link layer，并且会有相应的计网lab完成。在这一讲中，我们主要关注链路层提供的服务。课程资料地址：https://cs.nju.edu.cn/lwz/networks/CH2-Direct Link Networks-1.pdf
链路层简介
来学习链路层之前，我们先来学一些术语：
layer-2：即data link layer，一种简化的称呼。node：节点，包括hosts和routers。links：链路，连接相邻节点的通信信道（communication channel）。link的种类有point-to-point，multiple access和wireless link(WIFI)。frame：链路层帧，layer-2的数据包称呼，为datagram的封装（datagram即网络层数据报）。
网络层负责的是任意两台主机之间的通信服务，链路层则是负责端到端的通信服务。
链路层实现位置
链路层由harware，software和firmware联合实现，具体设备在host和router(switch)里面。链路层的实现主体部分是在network adaptor中（网络适配器，有时称为网络接口卡，即网卡），network adaptor的例子有NIC、Ethernet Card、 802.11 Card等。
首先我们来看实现链路层硬件部分的网络适配器。位于网络适配器核心的是链路层控制器（一个芯片，实现了framing，link access， error detection等服务）。
在发送端，控制器取得了上层网络层发下来的数据报后，根据协议对其封装，设置差错检测比特，并将帧传进链路。
在接收端，控制器接收整个帧，对其进行差错检测，抽取出网络层数据报（向上传是软件负责）。
上图即链路层的实现位置：网络适配器硬件和运行在CPU上的软件。
链路层的软件组件实现了高速链路层功能，如组装链路层的寻址信息和负责激活控制器硬件。链路层软件在接收端负责的工作有响应控制器中断，处理差错条件以及将adaptor抽出的数据报向网络层传递。
所以，链路层可是协议栈中硬件与软件交接的地方！
链路层提供的服务
概括
| 服务 | 功能 | 备注 |
|---|---|---|
| framing | 将网络层数据报封装成链路层帧，由链路层协议决定帧的格式结构 | 不同种通信（有线和无线）加的头部信息都不一样 |
| link access | 通过MAC协议来规定帧在链路上的传输规则，尤其协调多节点的传输 | 协调多址接入的媒介（coordinate）；使用MAC来确定局部地址；Half-duplex and full-duplex 即半双工和全双工，收发同时进行 |
| reliable delivery | 保证无差错经链路层移动每个网络层数据报 | 易于产生高差错率的链路会实现服务，如无线传输，反之光纤这样的可靠传输就很少实现这个服务；还有流控机制 |
| error detection && correction | 差错检测服务给帧提供差错检测字段，让接收方可以检测帧中的比特差错；差错纠正则可以准确定位差错位置并进行纠正。 | 用来处理因噪声和信号衰减所造成的错误；发送信号用以重传或者把帧丢弃；这个服务实现不是必须的，但因为容易实现所以大多数都实现了 |
Framing 成帧
framing比较好理解，就是发送端将网络层传下来的数据报进行封装，加上一些信息例如像差错检测比特，流控（flow control）字段等；接收端就接收完整个帧后，根据封装信息进行差错检测，流控设置等操作，再抽出数据报传到网络层。
Link access 链路接入
链路接入有两种方式：point-to-point点对点链路接入 和 broadcast广播链路接入。
点到点链路接入是一种专用接入（只有单个发送方和单个接收方），它广泛用于长距离缆线连接，以及大部分的以太网技术。
而广播链路接入能够让多个发送方和接收方共享相同的单一的广播信道，如传统的以太网和WLAN。这种接入方式会产生一个多路访问问题（Multiple access problem）：
因为所有的节点都能传输帧，所以多个节点同时传输帧时，信道上的所有节点同时收到多个帧。此时就会在接收处发生帧的碰撞（即collisions）。这就导致碰撞的帧都丢失了，而且在碰撞时间间隔内信道也被浪费了。
这就需要协调多个节点对一个共享广播信道的访问。解决这个问题我们提出了MAC协议。它可以划分为三种类型：
Channel partitioning：信道划分协议。物理媒介角度上切片，均匀频率。Taking turns：轮流协议。时间角度上切，频率不均匀。Random access：随机接入协议。前面两种可能造成信道的浪费，这类协议允许冲突存在，并为冲突提供解决机制。
我们在这讲先不详细介绍，不然很难一下子消化。留到后面MAC的时候再写写。
Reliable delivery 可靠交付
对于这个服务的实现我们采用流控机制（flow control）。它可以确保我们的接收方不会被发送的帧给淹没，即预防接收方的buffer产生溢出。实现这个机制我们主要有两种协议：
1.Stop and Wait
这可以说是最早的链路层协议。它的实现很简单，对大的数据包传输的效率很不错（因为返回ACK信息的耗时和传输数据包的耗时相比不值一提），但ACK（“确定收到”信息）返回耗时对小包来说是耗不起的。它的过程就是你来我往一下一下，如下：
2.Sliding Window
我们直译是滑动窗口。相比于stop&wait协议的一次一包，滑动窗口协议每次传输都是一次发一批。
在这个协议中，有几个要点：
- 帧上有一个k位的字段，k的范围是0-8，用来做帧的序号2^k（0-255）；
- 接收方有一个buffer，即
window，它的大小为win个帧，win <= 2^k； - 发送端可以在没收到ACK的时候最多发送win个帧。
- ACK后面的数字表示：发送端你可以发n号帧了；
我们来看看滑动窗口是怎么操作的：
然后滑动窗口对数据丢失的处理又细分为两种协议：
GO-BACK-N：回退N协议。绝大多数硬件采用了这种实现（因为它的算法非常符合硬件，移位操作）Selective Reject：选择重传协议。少用，接收方需保有较大的足够的buffer。
我们可以来看这两篇文章：
[What is a Sliding Window Protocol in Computer Network ](https://www.tutorialspoint.com/what-is-a-sliding-window-protocol-in-computer-network#:~:text=A sliding window is also known as windowing.,Layer (OSI model) or Transmission Control Protocol (TCP).)
数据链路层-Data Link Layer：拆分比特流的成帧方法/滑动窗口协议/回退N协议/选择重传协议
Error detection and correction 差错检测和纠正
我们在链路层中实现的差错检测为比特级差错检测。一般在framing过程中我们把EDC字段加到数据报的末尾，它的检测逻辑如下：
可以说EDC越大，它给予的检测效果就越可靠。我们有两种主要的方法：
Parity Checking
奇偶检验。这差不多是最简单的检测方法，如果采用的是单个奇偶校验位，位的值取决于数据中1的数目是否为奇数/偶素。而二维奇偶检测的鲁棒性比一维的更高，它将数据划分为行列分布，并且按照行列来设置校验位，这可以让接收方根据行列位置进行对差错bit的修正。
Cyclic Redundancy Check
即CRC，循环冗余检测编码。详细操作如下：
这一讲就先写这么多，不然回看的时候没法消化……（第一讲写得太烂了）