计算机网络：3数据链路层
数据链路层
- 概述
- 封装成帧和透明传输
- 帧
- 透明传输（填充字节或比特）
- 差错检测
- 奇偶校验
- 循环冗余校验CRC Cyclic Redundancy Check
- 可靠传输
- 停止-等待协议
- 回退n帧协议（滑动窗口协议）
- 选择重传协议
- 点对点协议PPP
- 共享式以太网
- 网络适配器：网卡
- MAC 媒体接入控制（Medium Access Control）
- CSMA/CD 载波监听多址接入/碰撞检测
- 退避算法：截断二进制指数退避
- 集线器
- 在物理层扩展以太网：转发器、调制解调器
- 在数据链路层扩展以太网：网桥
- 透明网桥的自学习
- 透明网桥的生成树协议STP
- 交换式以太网（交换机）
- 以太网的MAC帧格式
- 虚拟局域网VLAN
- IEEE 802.1Q帧
- 交换机的接口类型：access,trunk,hybrid
- 以太网的发展
- 100BASE-T以太网
- 吉比特以太网=千兆以太网
- 10吉比特以太网=万兆以太网
- 40/100吉比特以太网=四万兆/十万兆以太网
- 802.11无线局域网 WLAN
- 有固定基础设施
- 无固定基础设施
- CSMA/CA 载波监听多址接入/碰撞避免（Carrier Sense Multiple Access/Collision Avoidance）
- 退避算法
- MAC帧
概述
链路（Link) 是指从一个节点到相邻节点的一段物理线路（有线或无线），而中间没有任何其他的交换节点。
数据链路（Data Link）是基于链路的。当在一条链路上传送数据时，除需要链路本身，还需要一些必要的通信协议来控制这些数据的传输，把实现这些协议的硬件和软件加到链路上，就构成了数据链路。
计算机中的网络适配器（俗称网卡）和其相应的软件驱动程序就实现了这些协议。一般的网络适配器都包含了物理层和数据链路层这两层的功能。
**帧（Frame）**是数据链路层对等实体之间在水平方向进行逻辑通信的协议数据单元PDU。
封装成帧和透明传输
帧
FCS是检错码。
不可靠传输服务：收到有误码的帧，直接丢弃，其他什么也不做；未收到发送方发送的帧，也不进行任何处理。
可靠传输服务：实现发送方发送什么，接收方最终都能正确收到。
封装成帧是指数据链路层给上层交付下来的协议数据单元PDU添加一个首部和一个尾部，使之成为帧。帧的首部和尾部中包含有一些重要的控制信息。帧首部和尾部的作用之一就是帧定界。
接收方的数据链路层如何从物理层交付上来的比特流中提取出一个个的帧？
并不是每一种数据链路层协议的帧都包含有帧定界标志。PPP就有，MAC就没有，所以MAC加了八字节的前导码（包括7字节的前同步码和1字节的帧开始定界符）,并且增加了96bit的帧间间隔。
为了提高数据链路层传输帧的效率，应当使帧的数据载荷的长度尽可能地大于首部和尾部的长度。
考虑到对缓存空间的需求以及差错控制等诸多因素，每一种数据链路层协议都规定了帧的数据载荷的长度上限，即最大传送单元（Maximum Transfer Unit，MTU）。例如，以太网的MTU为1500个字节。
透明传输（填充字节或比特）
- 面向字节的物理链路使用字节填充的方法实现透明传输。
- 面向比特的物理链路使用比特填充的方法实现透明传输。
HDLC为了实现“透明传输”，采用“零比特填充法”，即每五个连续比特1后面插入一个比特0。
差错检测
在一段时间内，传输错误的比特数量占所传输比特总数的比率称为误码率（Bit Error Rate，BER）。
使用差错检测技术来检测数据在传输过程中是否产生了比特差错，是数据链路层所要解决的重要问题之一。
奇偶校验
奇校验是在待发送的数据后面添加1个校验位，使得添加该校验位后的整个数据中比特1的个数为奇数。
偶校验是在待发送的数据后面添加1个校验位，使得添加该校验位后的整个数据中比特1的个数为偶数。
只能检验出奇数个错误的情况
循环冗余校验CRC Cyclic Redundancy Check
收发双方约定好一个生成多项式G(X)。
可靠传输
一般情况下，有线链路的误码率比较低。为了减小开销，并不要求数据链路层向其上层提供可靠传输服务。即使出现了误码，可靠传输的问题由其上层处理。
无线链路易受干扰，误码率比较高，因此要求数据链路层必须向其上层提供可靠传输服务。
可靠传输服务并不局限于数据链路层，其他各层均可选择实现可靠传输。
停止-等待协议
一般可将超时重传时间RTO设置为略大于收发双方的平均往返时间RTT。
使用超时重传机制后，就可以不使用否认机制了，这样可使协议实现起来更加简单。但是，如果点对点链路的误码率较高，使用否认机制可以使发送方在超时计时器超时前就尽快重传。
为了让接收方能够判断所收到的数据分组是否是重复的，需要给数据分组编号。由于停止-等待协议的特性，只需1个比特编序号即可，即序号0和序号1。
为了让发送方能够判断所收到的确认分组是否是重复的，需要给确认分组编号，所用比特数量与数据分组所用比特数量一样。(数据链路层一般不会出现确认分组迟到的情况，因此在数据链路层实现停止-等待协议可以不用给确认分组编号。)
给超时计时器设置的超时重传时间RTO应当仔细选择，一般将RTO设置为略大于收发双方的平均往返时间RTT。(在数据链路层，点对点的往返时间RTT比较固定，RTO就比较好设定。在运输层，由于端到端往返时间非常不确定，设置合适的超时重传时间RTO有时并不容易。)
停止-等待协议属于自动请求重传（Automatic Repeat reQuest，ARQ）协议。即重传的请求是发送方自动进行的，而不是接收方请求发送方重传某个误码的数据分组。
停止-等待协议的信道利用率
回退n帧协议（滑动窗口协议）
（采用流水线传输可以显著提高信道利用率）
不过，在使用流水线传输方式时，发送方不能无限制地连续发送数据分组，否则可能会导致网络中的路由器或接收方来不及处理这些数据分组，进而导致数据分组的丢失，这实际上是对网络资源的浪费。
回退N帧协议采用流水线传输方式，并且利用发送窗口来限制发送方连续发送数据分组的数量，这属于连续ARQ协议。
回退N帧协议的接收方采用累积确认方式。
接收方不必对收到的每一个数据分组都发送一个确认分组，而是可以在收到几个序号连续的数据分组后，对按序到达的最后一个数据分组发送确认分组。
确认分组ACKn表明序号为n及之前的所有数据分组都已正确接收。
发送方收到确认信号后，从确认信号之后超时的第一个分组开始重传，因此称为回退n帧
发送窗口大小必须-1，因为如果000要重发，不知道是上一次的000还是下一次新的000
选择重传协议
为了使发送方仅重传出现差错的数据分组，接收方不再采用累积确认，而需要对每一个正确接收的数据分组进行逐一确认。
R是接收窗口，r是发送窗口
点对点协议PPP
点对点协议（Point-to-Point Protocol，PPP）是目前使用最广泛的点对点数据链路层协议。
使用PPP的数据链路层，向上提供的是不可靠数据传输服务。共享式以太网
以太网（Ethernet）以曾经被假想的电磁波传播介质——以太（Ether）来命名。
以太网最初采用无源电缆（不包含电源线）作为共享总线来传输帧，属于基带总线局域网，传输速率为2.94Mb/s。
以太网目前已经从传统的共享式以太网发展到交换式以太网，传输速率已经从10Mb/s提高到100Mb/s、1Gb/s甚至10Gb/s。
我们会首先介绍最早流行的传输速率为10Mb/s的共享式以太网的相关知识。
网络适配器：网卡
网卡在你的设备里
在计算机内部，网卡与CPU之间的通信，一般是通过计算机主板上的I/O总线以并行传输方式进行。
网卡与外部以太网（局域网）之间的通信，一般是通过传输媒体（同轴电缆、双绞线电缆、光纤）以串行方式进行的。
网卡除要实现物理层和数据链路层功能，其另外一个重要功能就是要进行并行传输和串行传输的转换。由于网络的传输速率和计算机内部总线上的传输速率并不相同，因此在网卡的核心芯片中都会包含用于缓存数据的存储器。
在确保网卡硬件正确的情况下，为了使网卡正常工作，还必须要在计算机的操作系统中为网卡安装相应的设备驱动程序。驱动程序负责驱动网卡发送和接收帧。
MAC 媒体接入控制（Medium Access Control）
MAC地址一般被固化在网卡的电可擦可编程只读存储器EEPROM中，因此MAC地址也被称为硬件地址。
MAC地址有时也被称为物理地址。
MAC地址是对网络上各接口的唯一标识，而不是对网络上各设备的唯一标识。
CSMA/CD 载波监听多址接入/碰撞检测
为了解决各站点争用总线的问题，共享总线以太网使用了一种专用协议CSMA/CD，它是载波监听多址接入/碰撞检测（Carrier Sense Multiple Access Collision Detection）的英文缩写词。
检测到碰撞，停止发送，退避随机时间
强化碰撞：发送帧的站点一旦检测到碰撞，除了立即停止发送帧外，还要再继续发送32比特或48比特的人为干扰信号（Jamming Signal），以便有足够多的碰撞信号使所有站点都能检测出碰撞。
在使用CSMA/CD协议时，由于正在发送帧的站点必须“边发送帧边检测碰撞”，因此站点不可能同时进行发送和接收，也就是不可能进行全双工通信，而只能进行半双工通信（双向交替通信）。
站点从发送帧开始，最多经过时长𝟐𝝉 （即𝜹→𝟎）就可检测出所发送的帧是否遭遇了碰撞。因此，共享总线以太网的端到端往返时间𝟐𝝉被称为争用期（Contention Period）或碰撞窗口（Collision Window），它是一个非常重要的参数。
很显然，总线的长度越长（单程端到端传播时延越大），网络中站点数量越多，发生碰撞的概率就越大。
为了确保共享总线以太网上的每一个站点在发送完一个完整的帧之前，能够检测出是否产生了碰撞，帧的发送时延就不能少于共享总线以太网端到端的往返时间，即一个争用期𝟐𝝉。
对于𝟏𝟎𝑴𝒃/𝒔的共享总线以太网，其争用期𝟐𝝉 的值规定为𝟓𝟏.𝟐𝝁s，因此其最小帧长为𝟓𝟏𝟐𝒃，即𝟔𝟒𝑩。
由于发送帧的站点边发送帧边检测碰撞，一旦检测到碰撞就立即中止帧的发送，此时已发送的数据量一定小于𝟔𝟒𝑩。因此，接收站点收到长度小于𝟔𝟒𝑩的帧，就可判定这是一个遭遇了碰撞而异常中止的无效帧，将其丢弃即可。
一般来说，帧的数据载荷的长度应远大于帧首部和尾部的总长度，这样可以提高帧的传输效率。
然而，如果不限制数据载荷的长度上限，就可能使得帧的长度太长，这会带来一些问题。总线一直被占用，也不好。
退避算法：截断二进制指数退避
共享总线以太网中的各站点采用截断二进制指数退避（Truncated Binary Exponential Backoff）算法来选择退避的随机时间。
如果连续多次发送碰撞，就表明可能有较多的站点参与竞争信道。但使用上述退避算法可使重传需要推迟的平均时间随重传次数而增大（即动态退避），因而减小产生碰撞的概率。当重传达16次仍不能成功时，就表明同时打算发送帧的站点太多，以至于连续产生碰撞，此时应放弃重传并向高层报告。
集线器
早期的传统以太网是使用粗同轴电缆的共享总线以太网，后来发展到使用价格相对便宜的细同轴电缆。
当初认为这种连接方法既简单又可靠，因为在那个时代普遍认为有源器件不可靠，而无源的电缆线才是最可靠的。
然而，实践证明这种使用无源电缆线和大量机械接口的总线型以太网并不像人们想象的那么可靠。
在使用细同轴电缆的共享总线以太网之后，以太网发展出来了一种使用大规模集成电路来替代总线、并且可靠性非常高的设备，叫作集线器（Hub）。站点连接到集线器的传输媒体也转而使用更便宜、更灵活的双绞线电缆。
使用集线器的以太网虽然物理拓扑是星型的，但在逻辑上仍然是一个总线网。总线上的各站点共享总线资源，使用的还是CSMA/CD协议。
集线器只工作在物理层，它的每个接口仅简单地转发比特，并不进行碰撞检测。碰撞检测的任务由各站点中的网卡负责。
集线器一般都有少量的容错能力和网络管理功能。例如，若网络中某个站点的网卡出现了故障而不停地发送帧，集线器可以检测到这个问题，在内部断开与出故障网卡的连线，使整个以太网能正常工作。
IEEE于1990年制定了10BASE-T星型以太网的标准802.3i，这种以太网是局域网发展史上的一座非常重要的里程碑，它为以太网在局域网中的统治地位奠定了牢固的基础。
10BASE-T以太网的通信距离较短，每个站点到集线器的距离不能超过100m。
IEEE 802.3以太网还可使用光纤作为传输媒体，相应的标准为10BASE-F，“F”表示光纤。光纤主要用作集线器之间的远程连接。
在物理层扩展以太网：转发器、调制解调器
扩展共享式以太网的覆盖范围和站点数量
共享总线以太网中两站点之间的距离不能太远，否则它们之间所传输的信号就会衰减到使CSMA/CD协议无法正常工作。
在早期广泛使用粗同轴电缆或细同轴电缆共享总线以太网时，为了提高网络的地理覆盖范围，常用的是工作在物理层的转发器。
随着使用双绞线和集线器的10BASE-T星型以太网成为以太网的主流类型，扩展网络覆盖范围就很少使用转发器了。
10BASE-T星型以太网中每个站点到集线器的距离不能超过100m，因此两站点间的通信距离最大不能超过200m。
在数据链路层扩展以太网：网桥
透明网桥的自学习
透明网桥（Transparent Bridge）通过自学习算法建立转发表。
透明网桥中的“透明”，是指以太网中的各站点并不知道自己所发送的帧将会经过哪些网桥的转发，最终到达目的站点。也就是说，以太网中的各网桥对于各站点而言是看不见的。
透明网桥的标准是IEEE 802.1D，它通过一种自学习算法基于以太网中各站点间的相互通信逐步建立起自己的转发表。
透明网桥的生成树协议STP
交换式以太网（交换机）
仅使用交换机（而不使用集线器）的以太网就是交换式以太网。
以太网交换机（以下简称交换机）本质上就是一个多接口的网桥
当交换机的接口与计算机或交换机连接时，可以工作在全双工方式，并能在自身内部同时连通多对接口，使每一对相互通信的计算机都能像独占传输媒体那样，无碰撞地传输数据，这样就不需要使用CSMA/CD协议了。
当交换机的接口连接的是集线器时，该接口就只能使用CSMA/CD协议并只能工作在半双工方式。
一般的交换机都采用“存储转发”方式，为了减小交换机的转发时延，某些交换机采用了直通（Cut-Through）交换方式。
采用直通交换方式的交换机，在接收帧的同时就立即按帧的目的MAC地址决定该帧的转发接口，然后通过其内部基于硬件的交叉矩阵进行转发，而不必把整个帧先缓存后再进行处理。
直通交换的时延非常小。
直通交换不检查差错就直接将帧转发出去，有可能会将一些无效帧转发给其他主机。
集线器与交换机的对比：
以太网的MAC帧格式
类型：其值用来指明数据载荷中的内容是由上一层的哪个协议封装的，以便将收到的MAC帧的数据载荷上交给上一层的这个协议。
虚拟局域网VLAN
巨大的广播域会带来一系列问题。
虚拟局域网（Virtual Local Area Network，VLAN）是一种将局域网内的站点划分成与物理位置无关的逻辑组的技术，一个逻辑组就是一个VLAN，VLAN中的各站点具有某些共同的应用需求。
属于同一VLAN的站点之间可以直接进行通信，而不同VLAN中的站点之间不能直接通信。
网络管理员可对局域网中的各交换机进行配置来建立多个逻辑上独立的VLAN。
连接在同一交换机上的多个站点可以属于不同的VLAN，而属于同一VLAN的多个站点可以连接在不同的交换机上。
虚拟局域网VLAN并不是一种新型网络，它只是局域网能够提供给用户的一种服务。
IEEE 802.1Q帧
交换机的接口类型：access,trunk,hybrid
如果不划分VLAN，那么以太网最大帧长度为1518字节，最小帧长度为64字节。如果划分VLAN，采用802.1q封装，802.1q的TAG长度为4字节，所以此时以太网最大帧长度为1522字节，最小帧长度为68字节。
以太网的发展
100BASE-T以太网
是指在双绞线上传输基带信号的速率为100Mb/s的以太网，也称为快速以太网（Fast Ethernet）。
吉比特以太网=千兆以太网
吉比特以太网也称为千兆以太网（Gigabit Ethernet）。1998年，千兆以太网的标准802.3z成为正式标准。
10吉比特以太网=万兆以太网
万兆以太网交换机常作为千兆以太网的汇聚层交换机，与千兆以太网交换机相连，还可以连接对传输速率要求极高的视频服务器、文件服务器等设备。
40/100吉比特以太网=四万兆/十万兆以太网
802.11无线局域网 WLAN
有固定基础设施
无固定基础设施
802.11无线局域网的ad hoc模式允许网络中的各站点在其通信范围内直接通信，也就是支持站点间的单跳通信，而标准中并没有包括多跳路由功能。因此，802.11无线局域网的ad hoc模式应用较少。
802.11无线网卡一般会被做成多模的，以便能适应多种不同的物理层标准，例如支持802.11b/g/n。
CSMA/CA 载波监听多址接入/碰撞避免（Carrier Sense Multiple Access/Collision Avoidance）
CSMA/CA协议仍然采用CSMA/CD协议中的CSMA，以“先听后说”的方式来减少碰撞的发生，但是将“碰撞检测CD”改为了“碰撞避免CA”。
尽管CA表示碰撞避免，但并不能避免所有的碰撞，而是尽量减少碰撞发生的概率。
802.11无线局域网不采用“碰撞检测CD”的原因如下：
❶ 由于无线信道的传输环境复杂且信号强度的动态范围非常大，在802.11无线网卡上接收到的信号强度一般都远远小于发送信号的强度，信号强度甚至相差百万倍。因此，如果要在802.11无线网卡上实现碰撞检测，对硬件的要求非常高。
❷ 即使能够在硬件上实现碰撞检测功能，但由于无线电波传播的特殊性（存在隐蔽站问题），还会出现无法检测到碰撞的情况，因此实现碰撞检测并没有意义。
CSMA/CA协议：
等待DIFS间隔是考虑到可能有其他的站有高优先级的帧要发送。
短帧间间隔（Short Interframe Space，SIFS）的长度为28𝝁𝒔，它是最短的帧间间隔，用来分隔开属于一次对话的各帧。一个站点应当能够在这段时间内从发送方式切换到接收方式。使用SIFS的帧类型有ACK帧、CTS帧等。
由于无线信道的误码率较高，CSMA/CA协议还需要使用停止-等待的确认机制来实现可靠传输，这与使用CSMA/CD协议的共享式以太网不同。
当某个站要发送数据帧时，仅在这种情况下才不使用退避算法：检测到信道空闲，并且该数据帧不是成功发送完上一个数据帧之后立即连续发送的数据帧。除此之外的以下情况，都必须使用退避算法：
❶ 在发送帧之前检测到信道处于忙态
❷ 在每一次重传一个帧时
❸ 在每一次成功发送帧后要连续发送下一个帧时
退避算法
为了进一步降低发生碰撞的概率，802.11无线局域网允许源站对信道进行预约。
CTS（Clear To Send）帧是短的响应控制帧，它也包括本次通信所需的持续时间（从RTS帧中将此持续时间复制到CTS帧中）。
若RTS帧发生碰撞，源站就不可能收到CTS帧，源站会执行退避算法重传RTS帧。
使用RTS帧和CTS帧进行信道预约会带来额外的开销。但由于RTS帧和CTS帧都很短，发生碰撞的概率、碰撞产生的开销以及本身的开销都很小。对于一般的数据帧，其发送时延往往远大于传播时延（因为是局域网），碰撞的概率很大，且一旦发生碰撞而导致数据帧重发，则浪费的时间就很多，因此用很小的代价对信道进行预约往往是值得的。
尽管如此，802.11无线局域网仍为用户提供了以下三种选择：
由于RTS帧和CTS帧都会携带通信需要持续的时间，这与之前介绍过的数据帧可以携带通信所需持续时间的虚拟载波监听机制是一样的，因此使用RTS帧和CTS帧进行信道预约，也属于虚拟载波监听机制。
利用虚拟载波监听机制，站点只要监听到数据帧、RTS帧或CTS帧中的任何一个，就能知道信道将被占用的持续时间，而不需要真正监听到信道上的信号，因此虚拟载波监听机制能减少隐蔽站带来的碰撞问题。
DIFS:128us
SIFS:28us
MAC帧
持续期：用于实现CSMA/CA的虚拟载波监听和信道预约机制。在数据帧、RTS帧和CTS帧中用该字段指出将要持续占用信道的时长。
控制序号：用来实现802.11的可靠传输，对数据帧进行编号。
地址1-4：取决于帧控制字段中的“去往DS”（到分配系统）和“来自DS”（分配系统）这两个字段的值。
