03 数据链路层
第三章 数据链路层¶
统计信息：字数 19781 阅读40分钟
https://www.bilibili.com/video/BV1c4411d7jb?p=21
P21 3.1 数据链路层概述¶
数据链路层地位：位于物理层之上，为网络层提供服务。
-
链路：一个结点和另一个相邻结点之间的物理线路（中间没有其他的结点）
-
数据链路：物理链路+软件硬件+通信协议。数据链路层以帧为单位传输和处理数据。
主要问题：封装成帧、差错检测、可靠传输。
- 封装成帧：数据链路层交付给网络层的协议数据单元就是帧，数据字段添加帧头和帧尾的过程就是封装成帧。数据字段就是向上层交付的协议数据单元。
- 差错检测：在帧尾部有一个检错码。收到帧后，根据特定算法，判断帧数据是否存在误码。
- 可靠传输：误码不能完全避免。如果能实现发送方发送什么有效内容，接收方可以获取这部分内容，就称为可靠传输。
使用广播信道的数据链路层：共享式以太网协议 CSMA/CD（全双工通信，需要处理数据碰撞），802.11局域网协议 CSMA/CA 分别对应有线网和无线网协议。
P22 3.2 封装成帧¶
封装成帧：数据链路层给上层的协议数据单元，添加帧头和帧尾，使得成为帧。帧头和帧尾的作用是判断帧的边界（帧头帧尾是边界的标志，从物理层传递的比特流中，解析出一个个帧）。
帧分为 以太网 MAC 帧和 PPP 帧，数据格式不同。
MAC 帧：有源地址和目的地址，发送前，物理层需要加一个前导码，作为帧开始的标志。前导码后面就是 MAC 帧。不同帧之间间隔96比特的发送时间。
透明传输：数据链路层对上层传输的数据没有任何限制（内容和大小都不限制）好像数据链路层不存在，所以称为透明传输。
发送帧之前，对数据部分进行扫描。如果数据字段一部分，和帧头或者帧尾相同（统称帧定界符），首先在数据中添加转义符号。这样接收方根据根据转义符号先处理，就可以分离数据载荷部分。如果是面向字节的链路，那么就添加字节的转义符；如果是面向比特的链路，就添加比特的转义符。
例题中：高级数据链路控制协议 HDLC 采用帧头和帧为中的标志字段作为帧定界符，值是 01111110。使用这个协议编码后，需要对数据中连续的5个1，后面增加0，进行转义。这样，接收方判断6个联系的1，就是帧定界符。
帧数据部分尽量大（有效数据和帧定界符的比例才能增加，提高传输效率），同时考虑差错控制，所以规定一个帧数据部分最大长度：最大传送单元 MTU。
P23 3.3 差错检测¶
- 比特差错：传输过程中01产生差错
- 误码率：错误的比特的百分比
- 差错检测码（FCS）：检测传输过程中是否产生了比特差错。MAC 帧的FCS是四字节，PPP帧的FCS是2字节。
差错检测方法：
-
奇偶校验（添加一个0或者1，使得全部的数据中0或者1的个数是奇数或者偶数）优点操作简单。缺点：无法处理误码是双数的情况。实际不使用这个检测方法。
-
循环冗余校验（CRC）：收发双方约定一个多项式，然后把数据进行多项式计算，把余数作为差错校验码发送。接收方收到数据后，也使用这个公式计算，对比两个的余数是否相同，判断数据传输是否有误。常用的有 CRC-16 = x^16，CRC 32 等。
差错检测说明：检错码只能发现错误，不能定位错误，无法纠正错误。如果想纠正错误，需要更多信息，开销比较大。CRC 有比较好的检错能力，计算较复杂，容易使用硬件实现，广泛应用于数据链路层。
对于错误，可以采用重传方式纠正错误（可靠连接）；或者直接丢弃错误的帧（不可靠连接），这个取决于上层需要的是可靠服务还是不可靠服务。
P24 3.4.1 可靠传输的基本概念¶
不可靠传输：仅丢弃误码的帧；
可靠传输：发送端发送什么，接收端就收到什么。
有线链路误码率较低，为了减小开销，不在数据链路层做处理，并不要求向上层提供可靠传输服务。即使出现误码，可靠传输的问题由上层应用处理。
无线链路容易收到干扰，误码率比较高，所以必须向上层提供可靠传输服务。
分组丢失，分组失序，分组重复这些传输错误，会出现在上层服务。所以可靠传输服务不仅局限于数据链路层，其他各层均可选择可靠传输。
主要使用下面三种机制，实现可靠传输。下面三个传输方式的原理，可以应用到计算机网络体系中各层协议中。
P25 3.4.2 可靠传输的实现机制 — 停止-等待协议（SW）¶
停止等待协议：stop and wait
发送方发送数据后，不能直接删除这个数据。需要等待接收方返回已经成功接收的消息，然后发送方才能删除数据。如果始终没有接收到接收方的信息，那么就触发超时重传。这样，传输过程中出现误码，或者分组未被接收时，都可以再次正确获取数据。
超时重传时间，略大于平均往返时间（数据链路层RTT较好计算，运输层非常复杂）
为避免分组重复，需要给每个分组带上序号。每次发送一个数据分组，就停止等待，只需保证新的数据分组和上一次的数据分组序号不同即可。使用一个比特编号就足够了。
注意：接收端收到数据分组后，如果有误码，将其丢弃，等待发送方的超时重传。如果是误码率较高的点对点链路，为了尽快超时重传，可以发出 NAK 分组。
停止等待协议的信道利用率：U = Td / (Td + RTT + Ta)
Td 发送方：数据分组发送时间
RTT 往返时间
Ta 接收方：确认分组的发送时间（很小）
所以，当 Td / RTT 越大（数据传输量越大，或者往返时间越短），信道利用率越高
如果 RTT 较大（卫星链路），信道利用率非常低；如果超时重传，U 还要降低。
P26 3.4.3 可靠传输的实现机制 — 回退N帧协议（GBN）¶
回退N帧协议，也成为滑动窗口协议
停止等待协议的信道利用率很低，所以提出了回退N帧协议（流水线传输）Go-Back-N
设置一个发送窗口（滑动窗口），只要在窗口内的分组，就可以发送。这样一次可以发送 N 个分组。接收方不需要对分组进行逐一确认，只需要在收到分组后，对按序到底的最后一个分组确认（这部分已经收到，可以删除了，ACKn 表示 N 之前全部数据分组都正常接收）。或者接收方在自己有分组发送时（全双工），对已接收无误码的分组，进行捎带确认。
如果某个分组出现差错，接收方的 ACKn 会重复发送，发送方就知道出现了差错，不需要等超时计时器就可以立即重传。具体收到几个 ACKn 根据具体情况决定。如果第N个出现重传，那么后面已发送的分组，都需要重传。
如果线路通信质量不好，GBN 协议的信道利用率并不比 SW 协议高。
发送窗口的尺寸（例如5），不能超过分组的序号（例如0-8，超过8后，分组序号再从0开始）。如果超过（10），那么可能同时接收到1，出现错误。
P27 3.4.4 可靠传输的实现机制 — 选择重传协议（SR）¶
回退N帧协议中，接收窗口尺寸是1，接收方只能接收按序到达的正确分组。如果某个分组误码，会造成后续多个数据分组，不能被接收方接收并丢弃，发送方也需要对这部分数据分组超时重传，信道利用率降低
选择重传协议，接收窗口的尺寸是N，这样可以先收下失序到达且无误码，并且序号在接收窗口中的数据分组，等全部分组到达后，一起交给上层（selective request）
为了使发送方仅重传出错的分组，接收方不是累计确认，而是对每一个正确接收到的数据分组，每一个进行确认。
接收方的接收窗口尺寸，需要小于发送方的发送窗口（如果等于1，就是停止等待协议；如果大于发送窗口，那么没有意义，浪费内存）。
接收方接收到按序到达的数据分组后，窗口向前滑动。
P28 3.5 点对点协议PPP¶
点对点协议PPP，是数据链路层使用最广泛的点对点协议，具体分成三部分：
- 下层的链路通知协议 LCP，负责建立配置测试数据链路的连接（对接物理层，例如面向比特或字节的链路）
- 中间的封装成帧（对各种数据报的封装）
- 上层的 NCPs ，支持不同的网络层协议（IP，IPX 等协议）
所以合成为 PPP 协议
协议的帧格式
- 首部：定界符；地址；控制；协议（数据部分交给什么协议处理）
- 数据：如果内部有特殊字符（和定界符冲突），需要转义
- 尾部：帧检验序列（FCS，接收方收到PPP帧后，使用CRC校验，如果正确，收下这个帧；如果不正确，丢弃这个帧；使用PPP数协议向上不提供可靠传输——在运输层处理）；定界符
接收方先反变换（处理转义字符）
透明传输：面向比特的同步链路，采用插入比特0的比特填充法
P29 3.6.1 媒体接入控制的基本概念¶
媒体接入控制解决的问题：协调多个发动和接收主机，对一个共享媒体的占用（MAC medium access control），以及发生冲突后，如何尽快回复通信。
可以分为静态划分信道（不灵活，突发性数据信道利用率很低，无线网络物理层使用，不在数据链路层中使用）、动态接入控制（共享式以太网）。
随着技术发展，有限网络，点对点链路和链路层交换机的交换式局域网，取代了共享式局域网（已经不使用静态接入控制）。无线局域网中还使用共享媒体技术。
下面三小节详述
P30 3.6.2 媒体接入控制 — 静态划分信道¶
信道复用：一条信道中传输多路用户的信号（信道媒体的传输容量，需要大于多条单一信道的总通信量）在发送段实现了信道复用，接收端实现信道分用。
复用：
- 频分复用（FDM，使用不同的频率隔离信道）；
- 时分复用（TDM， 使用不同的时序复用信道）；
- 波分复用（WDM，光缆中不同波长的光信号）；
- 码分复用（CDM，每一个比特时间划分成64或者128个码片，每一个主机使用唯一的码片序列，不能相同，必须正交，如果发送1就是这个码片，如果发送0就是码片的补码；接收方根据不同的码片，得到不同的主机发送的信息，然后进行解码转码就可以获取比特流）
P31 3.6.3 随机接入 — CSMA/CD协议¶
CSMA/CD 协议：
载波监听（CS）先听后说，每个主机发送前，先检测总线上是否忙；如果96比特时间不忙，发送这个帧；如果忙，等待直到总线不忙再发送
多址接入（MA）多个主机连接在一条总线上，竞争使用总线
碰撞检测（CD）：边听边说，主机发送数据时，也要监听是否发生碰撞。如果发生碰撞，停止一段时间后再次发送
强化碰撞：如果一个发送端检测到发生了碰撞，自己立刻停止发送，同时再发送一个碰撞信号，以便其他的站点检测到碰撞的发生。
碰撞窗口（争用总线的时期）以太网端到端的RTT时延2t（最多经过2t时间，就可以检测到是否发生了碰撞）主机需要经过碰撞窗口时间后，才能知道这次发送不会发生碰撞。
以太网中发送帧的主机越多，时延越大，发生碰撞的概率增加。共享式以太网不能连接太多的主机，总线不能太长。
最小帧长：确保主机在帧发送完成之前，就检测到帧发送过程中，是否产生了碰撞。（以太网规定最小帧长是64字节）接收方收到的帧中，凡是长度小于64 字节的帧，都是碰撞造成的无效帧。
信道利用率：和信道长度成反比，和帧长度成正比。
帧接收端流程：检测帧长度大于最短帧长；检测目的MAC地址和接收方的地址是否相同（或者是广播帧）；使用CRC检查帧判断是否误码
习题：CSMA-CD协议中，边发送帧，边检测是否冲突；适应于有线网络；根据网络跨度（RTT）和数据传输速率限制最小帧长。当RTT趋近于0，信道利用与趋近于100%。
P32 3.6.4 随机接入— CSMA/CA协议¶
无线局域网使用 CSMA-CA 协议（CA 碰撞避免）
为什么无线网不能使用CD碰撞检测协议？因为无线信号容易被干扰，接收强度远小于发送强度。如果在无线网卡实现CD，对硬件要求很高。同时，无线局域网可能存在隐蔽站问题（ABC并不能完全信号覆盖，所以碰撞检测意义不大）
802.11 无线局域网：无线信道误码率较高（数据链路层实现了确认机制，停止等待协议）增加了碰撞避免功能（CA）具体使用DCF算法实现。
所有站点，必须在持续检测到信道空闲一段时间后（IFS，帧间间隔），才能发送帧。帧分为高优先级和低优先级，高优先级的IFS较短，优先发送。
退避算法：信道由忙，变成闲，经过DIFS时间后，还要经过一段随机事件，才能使用信道（避免一个站点长时间占用信道）或者数据重传
三个名词
- mac 地址：数据链路层，以太网中MAC子层使用的地址（物理地址）
- ip 地址：网络层中，TCP/IP 体系中，使用的地址
- ARP 协议：网络层，通过IP地址获取到主机的MAC地址的协议
P33 3.7 MAC地址¶
使用点对点信道的数据链路层，不需要使用地址
使用广播信道的数据链路层，需要使用地址（MAC地址），来区分各主机。每个主机发送的帧中，需要携带发送主机和接收主机的地址。这个地址被固定在网卡中，是固定只读的，所以也成为硬件地址或者物理地址。——和物理层无关
例如 TP-LINK 网卡中，使用 EEPROM 芯片存储MAC地址，使用REALTEK 芯片实现以太网的数据链路层和物理层。
MAC 地址是网络中每一个接口的唯一标识，并不是每一个设备的标识（交换机和路由器可能有多个接口，拥有多个MAC地址）
格式：不同操作系统的网卡不一样（Windows，Android，MacOS）
存在的问题：固定的MAC地址可能会造成信息监听（中情局通过MAC地址定位用户并监视）现在有动态MAC地址，防止定位等问题。
P34 3.7 IP地址¶
包括网络编号和主机编号（通过子网掩码标识）网络编号用来标识因特网上的网络，主机编号用来处理同一网络的不同主机（或者路由器）
简介：数据包转发过程中，IP 地址始终不变，MAC 地址会不断变化。IP 地址表示接收方的地址，MAC 地址表示下一个节点的地址。在网络层传输过程中，路由器等处理网络层的 IP 数据报转发，MAC地址寻找等。
P35 3.7 ARP协议¶
ARP 地址解析协议：通过IP地址获取MAC地址
在一个子网中，每一个主机有一个 IP-MAC地址的字典缓存表。发送帧时会查表发送。也会在子网中，广播自己的IP地址和MAC地址。
因为IP地址和MAC地址并不是固定对应的，所以需要动态获取（默认两分钟）
ARP 协议只能在一段链路或者一个网络中使用
P36 3.8 集线器与交换机的区别¶
HUB 和 Switch
1、总线型以太网（总线+同轴电缆，已经淘汰）
2、星型以太网（多个主机使用双绞线+集线器连接，已经淘汰）在逻辑上和总线相同，各主机共享使用总线，使用CSMA-CD 协议。集线器只工作在物理层，仅转发比特，不进行碰撞检测。——集线器可以看做总线。集线器有少量容错能力和管理能力（一个主机的网卡出现故障，不断发送帧，集线器检测到，可以自动断开这个连线，不会影响整个以太网）
3、交换机：当规模较大时，碰撞增加，使用交换机可避免（忽略ARP过程）交换机有多个接口，每个接口连接主机或者另一个交换机，全双工方式。工作在物理层和数据链路层，收到帧后，在交换表中，查找到目的MAC地址对应的接口号，然后进行转发。
交换机可以实现存储转发（先检查错误并缓存到交换机）和直接转发（不会检查错误，直接转发）
对于广播域的情况，集线器和交换机都可以扩大广播域。集线器同时扩大了冲突域，交换机不会扩大冲突域（隔离碰撞域）。
P37 3.9 交换机自学习和转发帧的流程¶
交换机刚启动时，帧交换表是空的，随着各主机的通信，通过自学习算法，自动建立起帧交换表。
未建立帧交换表前，在交换机内部实现洪泛转发；逐步建立起交换表后，就可以实现直接转发。如果交换机知道帧有错误，就将其丢弃。
每一个对应关系都有有效时间，到期后自动删除（MAC地址和交换机接口的对应关系不是永久性的），可能交换机的接口改接了另一个主机，或者主机更换了网卡。
P38 3.10 以太网交换机的生成树协议STP¶
在网络中，为了避免某个网络故障，造成整体网络故障，通常要设置冗余链路，提高以太网的可靠性。
冗余的线路会形成多条连接，形成网络环路，可能带来广播风暴（消耗网络资源）主机收到重复的帧（消耗主机的资源）交换机的帧交换表震荡。
使用STP协议（生成树协议），可以增加冗余，提高网络可靠性，又可以避免网络环路的各种问题。
- 不管交换机实际采用怎么物理连接，逻辑上，交换机会自动计算并构建一个没有环路的网络（树形网络），物理上的冗余不会通信。
- 这个生成树拓扑可以连通整个网络
- 如果首次连接交换机，或者网络变化（故障），交换机可以重新计算生成树
STP 的算法不属于课程基本内容
P39 3.11.1 虚拟局域网VLAN概述¶
使用一个或者多个交换机，构建的交换式以太网，所有站点是一个广播域。可能带来：广播风暴；管理困难；安全问题等。
TCP/IP 中很多协议会使用广播（ARP，RIP，DHCP），所以需要处理广播问题
解决方法：路由器可以分割广播域
虚拟局域网：将物理层属于一个局域网的设备，在逻辑上划分成不同的局域网（逻辑组有某些共同的需求等）可以在不同的虚拟局域网中广播信号
P40 3.11.2 虚拟局域网VLAN的实现机制¶
使用 802.1Q帧实现，在 MAC 帧的基础上，增加了 VLAN 标记字段（标记了以太网帧属于哪一个VLAN，取值是1~4094）
802.1Q帧时交换机处理的，不是用户主机处理的。
交换机收到普通的以太网帧后，会插入VLAN标记转换成 802.1Q帧（打标签）。交换机转发802.1Q帧时，可能删除VLAN标记，转换成普通帧（去标签）。
交换机的端口类型不同（不同企业端口不同，华为思科）（Access端口用于交换机和用户主机的互连，Trunk 端口）交换机之间的端口设置成 Trunk 类型，Hybrid 端口都可以。
Hybrid 端口处理方法：如果帧的VID存在端口的去标签列表中，就去标签后转发。如果不存在列表中，直接转发。