Ch3: 数据链路层

主机$H_1$和主机$H_2$的通信可能会经过路由器，然而只有在$H_1$和$H_2$处数据包会完整经过网络的所有层，而在路由器处一般只经过最后三层$物理层、数据链路层、网络层$。

单看某一层，可以当作这个传输过程只经过了该层。也就是可以只关心传输过程中协议栈水平方向上的数据链路层。

数据链路层使用的信道主要有：

1. 点对点信道
2. 广播信道

1. 点对点信道的数据链路层#

定义$1.1.1$ 链路是一个节点到另一个相邻节点的物理数据通路。数据通路则是在链路上添加实现协议的软件和硬件。其中实现数据传输层的软件和硬件设备一般使用网络适配器。一般网络适配器实现数据链路层和物理层这两层的功能。

规程和协议在数据链路层是同义的。

数据链路层的主要功能是:

1. 发送方把上一层网络层交下来的数据添加上首部和尾部构成帧，再交由物理层发送到相邻节点。
2. 接收方把物理层递上来的帧数据包解包，提取出其中的报文，若无错误则交给上层网络层，否则就丢弃。

点对点信道传输要解决的有3个大问题:

1. 如何封装$IP$数据包为帧
2. 如何进行透明传输
3. 如何进行差错检验

数据链路层的协议多样，但基本上都是为了解决如上三个大问题所设计的。

比较有代表性的是$PPP$协议。

$PPP$协议主要传送的数据分为三种：

1. $IP$数据报文
2. **链路控制协议$LCP(Link \ Control \ Protocol)$**报文: 建立、配置和测试数据链路的连接。
3. **网络控制协议$NCP(Network Control Protocol)$**报文: 支持不同种类的网络层协议

其中$LCP$可用来识别身份。

1.1 封装成帧#

封装成帧(framing)指的是在要发送的数据的首部和尾部分别加上一些控制信息，比如帧定界。

帧定界符包括$SOH(Start \ of \ header)$和$EOT(End \ of \ Transmission)$。

只有完整的拥有$SOH$和$EOT$的帧才是完整的帧，其余不完整的帧一律丢弃。

每一种链路层协议都规定了帧能够传送的数据部分的最大长度最大传送单元MTU(Max Transfer Unit)

$PPP$协议的格式如下:

首部有4个字段，5个字节，尾部2个字段，3个字节。

其中首部第一个和尾部最后一个是Flag标记字段，分别是$SOH$和$EOT$，是$0$x$7E$。

首部第二个字段$A(0$x$FF)$和第三个字段$C(0$x$03)$是附加信息，至今未有含义，可自己定义。

首部第四个字段是协议字段

而尾部第一个字段是$FCS$校验字段($CRC$校验序列)。

1.2 透明传输#

透明传输所做的是不管要传送的数据是如何形式，包含何种字符，都要能够正确地传输。

此处特指传送数据中如果包含定界标识符的情形。如果不加处理，则会把数据中本身要发送的数据认定为定界符，导致传输出错。

具体解决的办法是: 添加转义字符。比如在要传送数据的部分中出现定界符之前加入$ESC$表示转义字符，并且在传送数据部分的出现$ESC$之前也要再加入一个转义字符$ESC$。

$PPP$协议中为了保证透明传输，主要有两种做法：

1. 添加转义字符0x$7D$:

2. 0比特填充

$PPP$协议的帧定界符是$0$x$7E$即$01111110B$其中出现连续的6个1。

则规定: 在要传送的数据中每当出现连续的5个1，就加入一个$0$。就能保证要传送的数据中的字符不可能和$0$x$7E$弄混。

1.3 差错检测#

定义$1.3.1$ 由于通信链路本身存在不可靠性，会把传输的$0/1$变为$1/0$，这种差错叫做比特差错。

定义$1.3.2$ 传输错误的比特数占所有传输比特总数的比叫做误码率(Bit Error Rate)。

一般用循环冗余校验CRC(Cyclic Redundancy Check)来进行检错：

选定一个$(k+1)$位的除数$P$来模$2$除要发送的数据$D$，得到$k$位的余数$R$，最后发送$D\cdot R$。

接收端收到数据$D'$后也用$P$模2除，余数为0则说明只有很小很小的概率出错，则接受它。否则就丢弃。

可以用一句话来描述这个过程: 凡是接受的帧，都几乎没有差错。[$PPP$协议也采用$CRC$校验]

不过要注意的是，$PPP$协议只保证了比特差错几乎消失，并不包含帧丢失，帧重复，帧乱序这种差错，即传输差错。

因此现在的主流做法是：

对通信质量不好的线路，在数据链路层上添加重传、帧编号和确认机制，而通信质量好的线路则不添加这部分协议。

1.4 PPP协议的工作状态#

$PPP$​协议的最大特点在于简单，支持多种网络层协议。

其工作状态主要是：

连接:

断开:

其中$LCP$配置以$LCP$配置请求帧的形式传输，配置选项包括: 最大帧长、鉴别协议、是否使用PPP协议首部的第二、三字段A和C。

对于被请求方收到$LCP$配置请求后可以回答:

1. 配置确认帧：听懂并接受
2. 配置否认帧：听懂但拒绝
3. 配置拒绝帧：没听懂

当被请求方回复确认帧后则进入鉴别状态，使用配置阶段所选择的PAP或者更加复杂安全的CHAP协议进行鉴别。

鉴别成功后则进入网路层协议配置即NCP配置状态，此时主要是配置双方各自使用哪一种网络层协议，$PPP$协议能够支持通信两端的

网络协议不一样！

配置完毕后则链路配置完毕，可以相互传送数据！

当某一方发送终止请求LCP分组，而对方回复确认终止LCP分组后，则进入链路终止状态。当调制解调器的载波消失后，也就进入链路静止状态。

$PPP$协议不仅涵盖了数据链路层，也包含了物理层和网络层。

2. 使用广播信道的数据链路层#

广播信道最大的特点是进行一对多的通信。

局域网使用的信道就是广播信道。

利用广播信道通信时同一时间只允许一台机器发送数据，因此是半双工通信方式。

2.1 局域网的数据链路层#

2.1.1 局域网的优势#

局域网的特点是网络为一个单位所拥有，且地理范围和站点数目均有限。

局域网的主要优势是:

1. 具有广播功能
2. 便于系统的扩展和逐渐演变，各设备位置可以灵活改变
3. 提高系统的可靠性、可用性、生存性。

2.1.2局域网的分类#

局域网可以按照网络拓扑结构分为:

1. 星形网
2. 环形网
3. 总线网

局域网一般在速率不高时采用双绞线($10Mbps$~$10Gbps$)，而更高速的局域网要使用光纤作为媒介。

2.1.3 以太网与局域网#

由于以太网技术在局域网市场中大获成功，因此以太网几乎成了局域网的同义词。

以太网一般使用曼彻斯特编码的信号。

局域网内用户要合理共享信道，方式有2中:

1. 使用信道共享技术，比如时分复用(TDM)、频分复用(FDM)、波分复用(WDM)和码分复用(CDM)。但此种方法代价太高，不适合局域网
2. 使用动态媒体接入控制: 信道并非在用户通信时固定分配给用户，而是时刻都在用户手中
   • 随机接入: 用户在信道上可以随机发送信息，会产生碰撞，于是需要解决碰撞的协议。
   • 受控接入: 主要有令牌形式控制和集中控制的多路探寻(polling)，或称轮询。

随机接入在局域网中使用的非常普遍，而受控接入却很少被使用。

2.1.3.1 以太网的标准#

以太网的由来是曾被认为是传播电磁波介质的以太(Ether)。

一开始的以太网权威标准是$DIX \ Ether \ V2$，之后$IEEE$制定了一个和其差别非常小的$IEEE \ 802.3$标准。

$IEEE \ 802.3$协议中将数据链路层分为$逻辑链路控制层LLC$(Logical Link Control)和$媒体接入控制层MAC(Media \ Access \ Control)$

和物理层相关的部分被放入MAC，对于$LLC$透明。

然而$DIX \ Ether \ V2$中却没有这样划分。

2.1.3.2 适配器#

适配器自身带有存储器和处理器(包括ROM和RAM)。

适配器是计算机和外部通信的接口。

作用主要有:

1. 串并行转换: 适配器和外部电缆/线路传输主要以串行传输的方式进行，而适配器和计算机传输数据主要是以并行传输。
2. 缓存传输的数据: 计算机的速度和外部网络的速度往往不一致，因此建立一个缓冲区。
3. 安装驱动程序: 即插即用的硬性条件：操作系统可以从适配器上找到驱动程序来操作适配器。
4. 能够实现以太网协议。

显然适配器囊括数据链路层的协议之外，也包含了物理层的协议。

并且，适配器的ROM上就存放了该适配器的物理地址。而计算机的**$IP$**地址则处在计算机自己的存储器上。

2.1.4 $CSMA/CD$协议#

2.1.4.1 争用期、发送时延、传播时延之间的关系#

由于同一时间只允许一台计算机发送数据，为了处理碰撞，引入载波监听多点接入/碰撞检测协议$CSMA/CD$(Carrier Sense Multiple Access With Collision Detection)

• 多点接入 : 指明是多台机器以多点接入的方式相连接在一根总线上。
• 载波监听：即检测信道。 不管是发送之前还是发送时，都需要不断检测信道。发送前检测是为了获取发送权，而发送时检测是为了检测碰撞。
• 碰撞检测：“边发送边监听”。当有多个计算机同时发送数据时，信号的波形叠加，变化幅度变大，超过一定阈值时就可判断不止一台机器在发送数据。此时就发生了碰撞。也成为冲突检测。

由于发送时延导致即便是发送前没有其他机器在发送数据，也有可能产生碰撞。

一般认为电磁波在介质传输中的速率是$2*10^5km/s$。因此电磁波在$1km$的信道上产生的传播时延是$5\mu s$。

一般认为以太网点到点传输的最大距离是$5km$。

一般认为以太网的传输速率是$10 Mbit/s$​。

规定帧和帧之间的最小间隔是$9.6\mu s$，即发送一帧后要先等待$9.6 \mu s$才进入到发送下一帧的阶段。目的是使得刚刚收到的数据帧的站点有时间可以接收该缓存，有时间清理。以便接收下一帧。

每一个站最多经过$2\tau$​时间就可以确定是否发生了碰撞。把站能够检测是否发生碰撞的最长时间叫做争用期(碰撞窗口)。

所以一个以太网中所有站点的发送时延都必须大于争用期。而争用期要保证能够检测是否发生碰撞，因此争用期$\ge 2 \tau$​即两倍最大传播时延。

所以:

一般认为以太网的2倍传播时延是$2\tau = 2 \times (5/2e5)s = 50\mu s$，传播速率为$1Mbit/s$。

$$\frac{bits_{min}}{10Mbps} \ge 2\tau = 50\mu s \Rightarrow bits_{min} \ge 500bit$$

由于这个最小比特数最好是2的幂次，所以一般取最小比特数(最小帧长)为$2^9=512bit$​，64字节。

所以取以太网的一般争用期为$51.2\mu s$。

2.1.4.2 处理碰撞措施和截断2进制指数退避算法#

当站点发现信号发生碰撞后:

1. 停止发送数据
2. 继续发送$32/48bit$的人为干扰信号: 让其他所有机器都知道信号发生了碰撞。
3. 执行截断二进制指数退避算法: 推迟随机的一段时间再发送数据，而不是等信道空闲了就立刻发送

截断二进制指数退避算法(truncated binary exponential backoff):

1. 截断二进制指数退避算法常数就为以太网的争用期$2\tau$。
2. 假设这是第$k$重新发送该信号，如果$k>16$，则放弃传输该帧，向上层报告。
3. 取$k'=min(k,10)$
4. 从$[0,2^{k'}-1]$中随机选择一个数$l$，并将$l*2\tau$作为等待时长。

要等待的平均时长会随着发送次数$k$增大而不断增大，也能够减小发生碰撞的概率。

存在某一种情况，类似于操作系统中的饥饿:

有一已经重传很多次的帧和很多重传次数不那么多的帧，有可能重传次数不那么多的帧的等待时长小，一直传，而重传很多次的帧因为一直等待，而发生饥饿。

2.1.5 使用广播信道和$CSMA/CD协议$发送数据的流程#

另外，每当一帧被完全发送以后，一定要把已经发送的一帧保存一下。如果在争用期发生碰撞，还要推迟一段时间再发送该保存的帧。

2.2 以太网信道的利用率#

以太网中收发数据时的等待时间几乎都是$2\tau$或者是$\tau$的整数倍，并且发送一段发送时延为$T_0$的数据占用信道的时间是$T_0+\tau$，所以比值$a$很重要:

以太网将$a$作为参数，$a$越小说明以太网越优秀。当发送数据时延$T_0$一定时，端到端的距离的传播时延$\tau$不能太大，当端到端的传播时延$\tau$一定时，$T_0$不能太小。

考虑信道一直空闲的极限情况，即发送从来不需要等待，那么以太网信道的最大理想利用率就是:

如果$S_{max}$的值都很不理想，那么一般情况下肯定更加糟糕。

一般以太网的实际利用率为$30\%$时就已经处于重载的情况了。

2.3 数据链路层的物理地址: MAC地址#

2.3.1 MAC地址和通信方式#

$MAC$地址是固化在适配器ROM中的物理地址，用来标识一台计算机，是计算机的”名字”。

$MAC$地址占$6$个字节，$48bit$。其中前$3$个字节是$组织唯一标识符OUI$，需要向$IEEE$购买。后$3$个字节可以自由分配。

$MAC$地址第一个字节的最低位是$I/G$位，用来表示该$MAC$地址是单播(只给一个站点发送)$I/G=0$，还是多播(给一个组发送)$I/G=1$.

另外，还考虑到了不向$IEEE$购买$OUI$​的情况:

$MAC$地址第一个字节的最低第二位是$G/L$位，用来表示该$MAC$是否是全球管辖(购买)$G/L=0$，还是个人任意分配$G/L=1$。

个人任意分配则不能保证该$MAC$是全球唯一的。

使用$MAC$通信时主要有3种形式：

1. 单播(一对一)
2. 广播(一对全体)
3. 多播(一对多)，一部分站点

所有适配器至少要能识别前两种通信方式。

当信道上传播的数据的$MAC$目的地址和自己适配器地址不相符的时候，大多都直接$丢弃$，但是如果是工作在混杂模式下，也可以取到这部分发送给其他主机的消息。这种工作方式有好也有坏的地方，$hacker$可以窃听，也可以由网络管理员监听网络流量，管理该局域以太网。

2.3.2 MAC帧的格式#

在以太网中传播的帧的格式有两种: $DIX Ether$ V2和$IEEE 802.3$，对应两种以太网协议。

但是它们非常相似，都是如下格式：

5(6)个字段：

0. 前同步码: 用来时钟同步，前7个字节全是$010101\cdots$，最后一个字节是$101010$$11$

1. 目的$MAC$地址

2. 源$MAC$地址

3. $类型$: 为了兼容不同种上层的网络层协议: $0$x$0800$ 表示是$IP$数据报，而$0$x$8137$表示是$Novell IPX$数据报。

4. 数据字段: $46-1500Byte$

5. $FCS$检测字段: 一般使用$CRC$循环冗余校验码(当传输媒体的误码率是$1e-8$左右时，$MAC$子层可以使得没检测到错误的概率小于$1e-14$)。

由于规定了以太网中帧的长度不能小于$512bit(64Byte)$，因此数据部分内容不能小于$64-18=46Byte$，整个帧长度的范围是$[64,1518]Byte$。

无效帧的可能形式有:

1. 帧长都不是整数个字节
2. $FCS$字段检测出错
3. 帧长不在$[64,1518]$之间。

遇见无效帧，直接丢弃。

为什么不需要帧长度呢？以太网传输使用是曼彻斯特编码，具有自同步特性。所以根据每次时钟周期中间部分的阶跃变化可以区分出每一个比特。只需要从最后一个比特[区分最后一个比特的办法是，最后一个比特后不再发送任何比特流]开始数$4$​个字节就能找到数据的末尾。因此不需要帧长度这一字段。

帧和帧之间存在一定的空隙，$96$比特时间。

但是当数据部分有填充字符时这一办法会失效，这就要求数据链路层上层的网络层要有自己的识别数据长度的手段。

$IEEE \ 802.3$和$DIX \ V2$帧的区别只在类型字段:

$DIX \ V2$帧的类型字段始终是类型

$IEEE \ 802.3$类型字段小于$0$x$0600$时，就表示数据字段的长度。且数据字段必须装入上层的$逻辑链路控制层LLC$的帧$LLC帧$。

2.4 在物理层扩展以太网: 使用集线器的以太网#

集线器是一种工作在物理层的，每个接口只是简单转发比特的器件。主机通过集线器星形连接在一起。

使用集线器的以太网本质上仍然是总线网。因此一段时间还是只允许一台主机发送数据，通过集线器连接在一起的主机仍然要采用CSMA/CD协议。

集线器往往多个(4~8个)堆叠在一起使用。功能都以模块的形式叠加在一起。增加功能模块或者是减少功能模块都可以热插拔。

通过光纤把集线器和站点相连接可以让以太网的范围变大很多很多，这就是在物理层上扩展以太网。然而这种方式的缺点是扩大了冲突域(碰撞域)。

增大碰撞域的原因就在于集线器只会不断转发比特流，因此在一台主机发送数据时，数据会被转发到所有线路中。

如果每台机器，每条线路的吞吐量都是$100Mbit/s$，那么上面的集线器群的吞吐量也是$100Mbit/s$，尽管3个系分开后的吞吐量是$3*100Mbit/s = 300Mbit/s$

另外由于集线器只能转发而没有缓存机制，如果有的线路的吞吐量是$10Mbit/s$，而有的是$100Mbit/s$，整个系统也只能工作在$10Mbit/s$。因为没有处理速度不匹配的机制。

2.5 在数据链路层扩展以太网: 使用交换机的以太网#

最初在数据链路层扩展以太网的是网桥(Bridge)，网桥根据数据帧的MAC地址，查找网桥内部的MAC地址表，进行数据帧的转发或者丢弃(找不到)。

后来**以太网交换机(交换式集线器、第二层交换机)**出现了。

2.5.1 以太网交换机的基本特点#

以太网交换机也有许多不同的种类，有具有第三层特性的第二层交换机，拥有部分网络层的功能，可以对数据报文进行分片和对多播通信量的管理。有多层交换机，可以根据第三层的IP地址对分组进行过滤。

2.5.1.1 并行性、独占传输媒体#

以太网交换机具有多个接口，每个接口和一台主机或者是另一个交换机相连接。以太网交换机具有并行性，因此大多工作在全双工模式。

另外以太网交换机在两台主机进行通信时都是独占传输媒体，完全不碰撞地传输。

独占传输媒体并行传输的好处是带宽变得很大:

每个接口的带宽是$10M bit/s$，一共有$10$个接口，则整个以太网交换机系统的带宽是10*10Mbit/s。

而普通集线器仍然是$10M bit/s$。

2.5.1.2 自学习性#

以太网交换机内部的**$MAC$地址表是通过自主学习算法自动地逐渐建立起来的。因此是一种即插即用**的设备。

每当帧信息传给交换机以后，交换机先查找地址表，查找目标地址是否在表中，如果在则单独转发，如果不在则广播。接着把源地址和对应的端口号写入地址表中。

一般地址表会设置一定的有效时长，过期的项目会被自动地删除，来应对某个端口的主机网卡适配器MAC改变的情况。

但是在有环路的拓扑网络中，自学习性可能会带来兜圈子的问题，因此对于交换机还制定了生成树协议STP，即切断某些线路，使得从一台主机到其他的主机是无环的树形结构。

2.5.1.3 缓存与直通#

交换机一般有缓存帧的功能，即暂时保存帧。当帧的接收方端口非常繁忙时，交换机会保存该帧，等到空闲时再转发。

也有的交换机有直通的功能，不在转发前先把帧全缓存，而是直接查找转发表立即转发到目的$MAC$地址对应端口。此种交换方式基于硬件的交叉矩阵，传播时延非常小。不过，此种方式不进行帧校验，可能会发送错误的帧。

2.5.2 从总线网到星型网#

随着总线上主机设备逐渐变多，总线网的性能逐渐下降。但是基于交换机的星形网效率非常好。因此如今大多数以太网是星型结构。

使用交换机的以太网不会产生冲突，也就不使用$CSMA/CD$协议。不像总线网那样工作在半双工模式，以太交换网工作在全双工模式。但是帧的结构没有改变。

2.6 虚拟局域网VLAN$(Virtual \ Local \ Area\ Network)$#

利用交换机可以很简单地做到VLAN。

定义$2.6.1$ 虚拟局域网VLAN是由一些局域网网段构成的与物理位置无关的**逻辑组。**这些网段往往有某些共同的特性或者需求。每一个VLAN的帧都有标识符，标识该帧来自于何处。

虚拟局域网只是局域网提供的一种服务，而不是真正的新型网络。

虚拟局域网中的每一个成员都可以听到来自该虚拟局域网中另一台主机的广播。但是非该虚拟局域网中的成员听不到。通过限制广播的范围，能够网络不会因为传播过多的广播信息而造成广播风暴。

支持虚拟局域网的方式是在数据帧中插入4个字节的$VLAN$标志。

前两个字节一定是$0$x$8100$，当接收方检测到$0$x$8100$时就知晓该帧是VLAN帧。

接着前$3$位是用户优先级标识符，接着是规范格式指示符(Canonical Format Indicator)，最后的$12$位是$VLAN$标识符，标识该虚拟局域网的VID，唯一标识该以太网帧属于哪一个虚拟局域网。

加入该$4$字节后，以太网帧的最大帧长变为$18 + 1500 + 4 = 1522$字节。

2.7 高速以太网#

$100BASE-T$指的是$100Mbit/s$，Base表示传输的是基带信号，T表示传输的介质是双绞线（F表示是光纤)

$100BASE-F$