第六章
链路层概述
链路层在何处实现
链路层的主体部分是在网络适配器（网络接口卡）实现的。大部分链路层是在硬件中实现的。
差错检测和纠正技术
链路层有比特级差错检测和纠正。在发送节点，为了保护bit免受差错，使用差错检测和纠正比特EDC来增强数据。
不过即使使用EDC也有可能未检出比特差错。
奇偶校验
假设 $D$ 有 $d$ 比特，那只需要一个附加的比特，使得 $d+1$ 个比特中1的总数是偶数。若接收方发现1的bit有奇数个，就是发生了奇数个比特错误。如果出现了偶数个比特差错，会导致一个未检出的差错，但是这个概率是极小的。然而差错经常“突发”地聚集在一起，所以这个不太健壮。
如图，二维奇偶校验能够检测并纠正一个bit错误，能检测（但不能纠正）两个bit错误的任意组合。
接收方检测和纠正差错的能力叫前向纠错FEC。它们可以减少发送方重发的次数，避免了往返时延。
检验和方法
$d$比特数据被作为一个$k$比特整数的序列处理。因特网检验和就是将数据的字节作为16比特的整数求和取反码。接收方对接收的数据（和检验和）求和取反码，有0就出现了差错。在tcp，udp中对所有字段求因特网检验和。
循环冗余检测
循环冗余检测CRC编码也称为多项式编码，它把发送的比特串视为0/1系数多项式，对比特串的操作解释为多项式算数。
发送方接收方首先必须协商一个$r+1$比特模式称为生成多项式，表示为$G$。
考虑$d$比特的数据$D$，发送方要选择$r$个附加比特$R$，把他们附加到$D$上，使得到的$d+r$比特模式（被解释为一个二进制数）用模2算数恰好能被$G$整除。
接收方用$G$去除接收到的$d+r$比特，如果余数非0，就是出现了差错。
所有CRC计算用模2算数来做，加法不进位减法不借位，其实就是个XOR……
乘$2^k$就是比特模式左移$k$个位置。
我们要求出$R$使得对于$n$有$D2^r\mathrm{xor} R=nG$，$D2^r=nG\mathrm{xor} R$，也就是用$G$除$D2^r$余数刚好是$R$。
所以$R=\mathrm{remainder}\dfrac{D\cdot 2^r}{G}$。
国际标准已经定义了8、12、16、32比特生成多项式。$G_{CRC-32}=100000100110000010001110110110111$这种。
每个CRC标准都能检测小于$r+1$比特的突发差错。长度大于$r+1$比特的突发差错检测到的概率是$1-0.5^r$。每个CRC标准也都能检测任意奇数个比特差错。
多路访问链路和协议
有两种类型的网络链路：点对点链路和广播链路。要通过多路访问协议来规范共享的广播信道上的传输行为。
因为所有节点都能传输帧，所以多节点可能会同时传输帧，这时所有节点同时接收到多个帧，传输的帧在所有接收方碰撞，结果没有一个节点能有效获得任何帧……
信道划分协议
一种做法是划分信道，时分多路复用TDM和频分多路复用FDM。
tdm非常公平。但是节点总是被限制于$R/N$的平均速率并且总是需要等待它在传输序列中的轮次。
fdm的平均速率也被限制。
第三种是码分多址CDMA，tdm和fdm分别为节点分配时隙和频率，而cdma对每个节点分配一种不同的编码，然后每个节点用唯一的编码来对发送的数据编码。这样不同节点能同时传输并且各自的接收方仍能正确接受发送方编码的数据（如果接收方知道发送方的编码）。
随机接入协议
一个传输节点总是全速发送，碰撞时等待一个随机时延然后重发帧。
时隙ALOHA协议：菜菜的。要求所有帧由L比特组成，时间划分成长度为$L/R$秒的时隙，节点只在时隙起点传输帧，每个节点都知道时隙何时开始，如果一个时隙中出现了碰撞那么所有节点都能在该时隙结束前检测到该碰撞事件。
操作是有在一个时隙开始的时候传输整个帧，要是有碰撞就以$p$的概率在后面的时隙重传，直到传输成功。但是效率非常低。纯ALOHA就更加白给。
载波侦听多路访问CSMA：说话之前先听（这是载波侦听）。和他人同时开始说话就停止说话（这是碰撞检测）。
大致过程：侦听到信道空闲——传输——没有检测到信号能量就完成传输，检测到就中止传输，等待一个随机时间量重传
选择随机时间量用二进制指数后退算法。该帧经历了一连串的$n$次碰撞，就从${0, 1, 2, \ldots, 2^n-1}$里选择一个$K$值。
对于以太网，一个节点等待的实际时间量是$512K$比特时间（发送512比特进入以太网所需时间量的$K$倍），$n\leq 10$。
轮流协议
ALOHA和CSMA协议不具备“当有$M$个节点活跃时，每个活跃节点的吞吐量接近$R/M$的特性。
轮询协议：指定一个主节点，以循环的方式轮询每个节点。先给主机1发报文，告诉它能够传输的帧的最多数量。节点1传输了某些帧以后告诉节点2能传输的帧的最多数量……
令牌传递协议：没有主节点，一个被称为令牌的特殊帧在节点之间以某种固定次序交换。一个节点要是没有帧发送就立刻传令牌给下一个节点，有的话就发送最大数目的帧数然后传给下一个节点。
交换局域网
MAC地址
主机或路由器的适配器（网络接口）具有链路层地址，但是链路层交换机并不具备和接口关联的链路层地址。这是因为交换机透明地执行在主机和路由器之间承载数据报的任务。
MAC地址长度6字节，有$2^{48}$种可能的mac地址。它被设计成永久的，但可能通过软件修改它。
一个生产适配器的公司购买前24个比特固定下来，自己生成后面的24个比特。
mac地址具有扁平结构（而不是ip地址那样的层次结构）
适配器接收到一个帧时检查帧的目的地址是否和自己的mac地址匹配，匹配就提取出封装的数据报并将它沿协议栈向上传递，不匹配就丢弃。当然也有mac广播地址FF-FF-FF-FF-FF-FF。
地址解析协议
在网络层地址（ip地址）和链路层地址（mac地址），这是地址解析协议。
用ARP将一个ip地址解析为一个mac地址。跟dns挺像，不过arp只为在同一个子网上的主机和路由器接口解析ip地址。
arp表有ip地址，mac地址，ttl（寿命，常为20min），但是这张表不必为该子网上所有主机和路由器都包含一个表项。
要是arp表里有目的ip地址的条目好说，没有的话就使用arp协议来解析这个地址。发送方构搞一个arp分组，指示适配器用mac广播地址来发送这个分组。arp即插即用，是跨越链路层和网络层边界两边的协议。
发送数据报到子网以外
如图，从左上到右下，先发给111.111.111.110（用arp得到mac地址，创建一个帧，发到子网中。路由器看到这个链路层帧向它寻址就把这个帧传给路由器），然后路由器查询转发表， 知道了要在右边的接口发送……就发成了
以太网
以太网是目前最流行的有限局域网技术。
以太网帧结构：
数据字段承载ip数据报，长度在46-1500之间，多了分片少了填充。
类型字段允许以太网复用多种网络层协议。
crc用来循环冗余检测
前同步码：前七个字节为10101010，最后一个字节是10101011，目的是唤醒接收适配器并将它们时钟和发送方时钟同步。
所有以太网技术都向网络层提供无连接服务，提供不可靠服务。
链路层交换机
交换机转发和过滤：过滤是决定一个帧应该转发到某个接口还是要丢弃，转发是决定一个帧应该被导向哪个接口，并把帧移过去。它们借助于交换机表完成。交换机表有内容，接口，时间。
假设有一个目的地址为DD-DD-DD-DD-DD-DD的帧从交换机接口$x$到达，如果
- 表中没有对于它的表项，就向接口$x$以外的所有接口前面的输出缓存转发该帧副本
- 表中有一个表项联系它和接口$x$，丢弃
- 表中有一个表项联系它和接口$y \not = x$，该帧放到接口$y$前的输出缓存
自学习：tql
- 交换机表初始为空
- 对于每个接口接收到的每个帧，在表中存储源地址字段中的mac地址，到达接口号，当前时间
- 一段时间（老化期）以后，没有接收到以该地址作为源地址的帧，就在表中删除这个地址
所以交换机也是即插即用的。它还是全双工的。
性质：
- 消除碰撞。没有因为碰撞而浪费的带宽
- 异质的链路。交换机将链路彼此隔离，局域网中的不同链路能以不同的速率甚至是在不同的媒体上运行
- 好管理
比较：
交换机即插即用，有相对高的分组过滤和转发速率；交换网络的活跃拓扑限制为一棵生成树，要求在主机和路由器中有大的arp表，对广播风暴不提供任何保护措施。
路由器没有生成树限制，可以以丰富的拓扑结构构建因特网。对第二层的广播风暴提供防火墙保护；不是即插即用的，催每个分组的处理时间比交换机更长。
| 集线器 | 路由器 | 交换机 | |
|---|---|---|---|
| 流量隔离 | Y | Y | |
| 即插即用 | Y | Y | |
| 优化路由 | Y |
虚拟局域网
支持虚拟局域网VLAN的交换机允许经一个单一的物理局域网基础设施定义多个虚拟局域网。
接口由网管划分成组，每个组构成一个vlan，每个vlan中的端口构成一个广播域（来自一个端口的广播流量仅能到达该组中其他端口）
至于vlan之间的通信，看书吧。
链路虚拟化：网络作为链路层
多协议标签交换
多协议标签交换MPLS云里雾里，跳了
数据中心网络
数据中心的主机称为刀片，每个机架堆放20-40台刀片，每个机架顶部有一台“机架顶部交换机”，它们和机架上主机互联，和数据中心其他交换机互联。
负载均衡
外部请求首先被定向到一个负载均衡器，它平衡主机间的工作负载，还提供类似nat的功能。
等级体系结构
图为示意。
发展趋势
全连接拓扑和模块化数据中心。
回顾：Web页面请求的历程
掏出你的电脑，连到以太网交换机，开始冲浪（x
超绝详细的部分看书
准备：DHCP、UDP、IP和以太网
先用udp和dhcp让你的电脑知道ip地址，在ip转发表中安装默认网关。
仍在准备：DNS和ARP
在浏览器敲入www.bilibili.com的时候，浏览器生成tcp套接字，向bilibili发送http请求——在这之前要知道bilibili的dns。
电脑生成一个dns查询报文丢进udp报文段向dns服务器丢过去——在这之前你需要用arp知道网关路由器的mac地址。用arp一通操作成了。
仍在准备：域内路由选择到dns服务器
网关路由器接收到包含dns查询的报文，查找目的地址（比如dns服务商comcast），发到comcast网络的边缘路由器，根据转发表确定出接口发过去（转发表已经被rip、ospf、is-is、BGP这一套东西填好了）
经过一番dns查找，确定了google服务器的ip地址，返回，准备连接
Web客户——服务器交互：TCP和HTTP
生成tcp套接字，建立连接，发送http get报文，获得http响应报文……一通操作，你看到了2233。