计算机网络知识点——3.数据链路层
一些术语：
- 主机和路由器都是节点（nodes）
- 连接相邻节点的通道时链路（links），分为有线链路(wired links),无线链路(wireless links),局域网(LANS）
- 第二层的数据包(packet)是帧（frame）
- 链路层主要在网络接口卡及其驱动程序上实现。
功能：
数据链路层负责把数据从一个节点通过链路传给相邻的另一个节点，即在物理网络中传输数据帧。
- 形成帧（framing）
- 差错检测（error detect）：比特错，纠错
- 差错控制（error control）：丢包，重复，错序。流控制（flow control）。
- 介质访问控制（medium access control）：多路访问，碰撞（collision）。
差错检测：
奇偶校验：
如果一组给定数据位中1的个数是奇数，那么偶校验位就置为1，从而使得1的个数是偶数。如果给定一组数据位中1的个数是偶数，那么奇校验位就置为1，使得总的1的个数是奇数。
此处为奇校验，因为1的个数为9个，加上一个0使之继续为奇数。
二维的奇偶校验码（偶校验）如下，横竖1的个数均为奇数的那一位为出错位。其中，最下方和最右方为添加的校验位。
循环冗余校验码（cyclic redundanry check,CRC)：
如果传输过程中没有出现比特错，接收方用相同的除数去除数据加CRC校验码，余数应该为0.
例子：
数据为：101110000，除数为：1001,求校验码。
解：每一步计算为按位异或：
| 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | |||||
| 1 | 0 | 1 | 0 | |||||
| 1 | 0 | 0 | 1 | |||||
| 1 | 1 | 0 | 0 | |||||
| 1 | 0 | 0 | 1 | |||||
| 1 | 0 | 1 | 0 | |||||
| 1 | 0 | 0 | 1 | |||||
| 1 | 1 | |||||||
解得校验码为011，将数据加上11为101110011，除上1001，余数为0.
注：链路层常用CRC检验，因为容易用硬件实现，速度快，检错率很高。
可靠数据传输：
- 如果不纠错，出现比特错的帧将被丢弃，即出现丢包错误（loss）。
- 自动重发请求(Automatic Repeat request, ARQ),每发送一帧都启动一个超时定时器，哪个帧超时将重传该帧，并重启定时器。
- 确认帧是接收方发给发送方用来表示已经收到数据帧的一个控制帧。
- 停等协议和滑动窗口协议都是自动重发请求协议。
1
问题：为什么ARQ协议的超时时间不应设置得太长？
答：如果ARQ设置过大将会使发送方经过较长时间的等待才能发现帧丢失，通过超时重传来纠正这些错误
需要太长的时间，降低了连接数据传输的吞吐量；但也不能设置的太短，导致接收方会误认为大量帧丢失而导致大量不必要的重传。
停等协议（stop-and-wait):
只有收到前一个数据帧的确认才可以发送下一个数据帧。
停等协议正常情况下是不需要序号的，但是为了避免出错，至少需要两个序号。出错的情况有三种：（1）数据帧丢失（2）确认帧丢失（3）确认帧在超时时间之后返回。如果没有序号， 若确认帧丢失或延时，则超时重发机制会使接收方接收到两个同样的数据帧，导致重复数据帧出现 。若接收方收到序号相同的数据帧，就表明出现了重复帧。这时接收方应当丢弃这个重复帧，同时向发送方发送一个确认帧。 因为接收方这时已经知道发送方没有收到上一次发送的确认帧。如果数据帧丢失，则接收方将重新接收到的应该接受的序号的帧接收。对于停等协议，由于每发送一个数据帧就停止等待，所以说用序号轮流使用0和1就足够了。
滑动窗口协议（sliding window):
不需要等待前面发送的帧的确认回来，就可以连续发送多个帧，其个数由发送窗口来控制。
发送窗口：是个序号范围，表示可以连续发送多少未确认的数据帧，主要用于流控制。
发送窗口大小(Sending Window Size,SWS)：表示发送窗口的大小，也是发送缓冲区的大小。
确认帧(Acknowledgement Frame)：表示这一帧（确认号为ACK）及之前的数据帧全部收到并已交给上层协议。
问题：滑动窗口协议的确认帧的确认号表示什么含义，它这样表示的好处是什么？
答：表示该帧以及之前的帧均已被接收方收到。通过延迟确认，可以少发送确认帧。如果前面的确认帧丢失，后面到达的确认帧也可以对前面帧的确认，提高了可靠性。
回退N协议（go back N):
例子：
如果使用回退N滑动窗口协议，发送窗口大小为4，可以循环使用的序号为0~7，RTT大于4帧的发送时间。如果发送方发送了从序号3开始的10个数据帧，除了第2帧（序号为4）和第5帧（序号为7）丢失，包含重传帧在内的其它帧均正确到达接收方，问接收方依次收到这些帧（含重传帧）的序号（序号之间用一个空格隔开）
解析：接收方依次接受到的帧序号为：3 5 6 4 5 6 7 0 1 2 3 4因为发送窗口大小为4，当发送了3456之后，收到了3的ACK，然后发送7等待4的ACK返回，在这个过程中接收方收到56，但是没有收到4的ACK，所以回退到发送4和567，一共发送了10个帧，在7之后还发送了01234，所以接收方收到序列为35645701234.
选择性重传(Selective Repeat):
否定性确认帧（Negative Acknowledgement,NAK）:用于表示这一帧之前的数据帧全部收到并已交给上层协议，要求发送方重传这一帧。每个帧只发送一次NAK。
接收窗口：用于确定应该保存哪些帧，用序号范围表示。
接收窗口大小（Receiving Window Size,RWS）:表示接收窗口的大小，也是接收缓冲区的大小。
问题1：选择性重传协议的RWS大于SWS是否有意义？
答：没意义。错序到达的帧加上期待接收的帧最多SWS个。 发送方发送的未确认的帧最多只有SWS个，接收方只需要缓存这些帧，故RWS没有必要大于SWS。
问题2：选择性重传协议需要的最少序号个数与SWS和RWS有什么关系 ？
答：序号个数>=SWS+RWS。如果接收方收到新的SWS帧，发回的确认全部丢失，在这种情况下，重发时要求这些帧的序号
不落在当前接收窗口的序号范围内。，序号少了就会出现重复错误。
问题3：选择性重传协议可能会收到落在接收窗口之外的数据帧。这句话是否正确？
答：正确。因确认帧丢失而重传的帧都会落在接收窗口之外。
问题4：回退N协议可能会收到落在发送窗口之外的确认帧。这句话是否正确？
答：正确。如果因确认帧迟到而出现超时重传，就可能收到一个帧的两个确认帧。第二个确认帧就会落在发送窗口之外 。
问题5：选择性重传协议丢失了NAK并非致命错误。这句话是否正确？
答：正确，因为还有超时重传机制确保可靠性。
例题：如果上题（回退N滑动窗口协议中的例题）改为选择性重传，并且接收窗口大小等于发送窗口大小，并且只有第2帧丢失，问接收方依次收到这些帧（含重传帧）的序号（序号之间用一个空格隔开）
解析：序列为：3 5 6 7 4 0 1 2 3 4
发送3456之后，收到3的ACK，继续发送7，但是此时没有收到4的ACK，重发4，在4收到之前收到567，所以序列为3567401234.
PPP协议：
PPP协议（Point-to-Point Protocol)：是点到点网络的数据链路层协议。
- PPP协议可以提供连接认证、传输加密和压缩功能。
- PPP协议用IPCP协议获取IP地址。
- PPP协议使用LCP协议确定是否需要身份认证和确定链路层的参数。