0%

数据链路层

Posted on Edited on In
Symbols count in article: 6.3k Reading time ≈ 21 mins.

数据链路层的功能

数据链路层的主要作用是加强物理层传输的原始比特流的功能，将物理层提供的可能出错的物理连接改造为逻辑上无差错的数据链路

  • 为网络层提供服务
    • 无确认的无连接的服务，不需建立链路连接，不发回确认，不重发丢失帧而交由上层处理。适用于实时通讯或误码率较低的网络，如以太网。
    • 有确认的无连接服务，不需建立链路连接，发回确认，重发丢失帧
    • 有确认的面向连接的服务，建立连接，发回确认，重发丢失帧
    • 有连接就一定要确认，即不存在无确认的面向连接的服务
  • 链路管理
    • 数据链路层连接的建立、维持和释放过程称为链路管理
  • 帧定界、帧同步、透明传输
    • 将一段数据的前后分别加上首部和尾部，就构成了帧。首部和尾部中含有很多控制信息，它们的一个重要作用就是确定帧的界限，即帧定界
    • 帧同步指的是接收方应能从接收到的二进制比特流中区分出帧的起始和结尾
    • 透明传输指不管传输的数据是什么样的比特组合，都应能在链路上传送
  • 流量控制
    • 限制发送方的数据流量，使其发送速率不超过接收方的接收能力
  • 差错控制
    • 位错指帧中的某些位出现了错误，通常采用校验位发现位错，通过自动重传请求（Automatic Repeat reQuest，ARQ）方式来重传出错的帧

组帧

组帧是为了在出错时只重发出错的帧，而不必重发全部数据

字符计数法

在帧头部使用一个计数字段来标明帧内字符数。目的结点的数据链路层收到字节数值时，就知道后面跟随的字节数，从而可以确定帧结束的位置（计数字段提供的字节数包含自身所占的一个字节）

字符填充的首位定界符法

字符填充法使用一些特定的字符来定界一帧的开始（DLE STX）与结束（DLE ETX）。为了使信息位中出现的特殊字符不被误判为帧的首尾定界符，可以在特殊字符前面填充一个转义字符（DLE）来加以区分（转义字符是ASCII码中的控制字符，是一个字符，而不是“D”“L”“E”三个字符的组合）

比特填充的首位标志法

比特填充法允许数据帧包含任意个数的比特，也允许每个字符的编码包含任意个数的比特。它使用一个特定的比特模式，即01111110来标志一帧的开始和结束。为了不使信息位中出现的比特流01111110被误判为帧的首位标志，发送方的数据链路层在信息位中遇到5个连续的”1“时，将自动在其后插入一个“0”；而接收方每收到5个连续的”1“时，自动删除后面紧跟的”0“以恢复信息

违规编码法

在物理层进行比特编码时，通常采用违规编码。例如，曼切斯特编码中“高-高”电平对和“低-低”电平对在数据比特中是违规的（即没有采用），可以借用这些违规编码序列来定界帧的起始和终止。违规编码法不采用任何填充技术

目前较常用的组帧方法是比特填充法和违规编码法

差错控制

传输中的差错都是由噪声造成的，一类是信道所固定的、持续存在的随机热噪声；另一类是由外界特定的短暂原因所造成的冲击噪声，前者可以通过提高信噪比来减少或避免干扰，而后者不可能靠提高信号幅度来避免干扰造成的差错，是产生差错的重要原因。前者也叫随机差错，后者也叫突发差错。

差错控制主要有两类：自动重传请求（ARQ）和前向纠错（Forward Error Correction，FEC）。

在ARQ中，接收端检测出差错时，设法通知发送端重发，直到接收到正确的码字为止。

在FEC中，接收端不但能发现差错，而且能确定二进制数码的错误位置。

因此，差错控制可分为检错编码（Error-Detecting Code）和纠错编码（Error-Correcing Code）

纠错编码

对于码距大于等于2的数据校验码，开始具有纠错的能力。码距越大，检错、纠错的能力就越强，而且检错能力总是大于等于纠错能力

奇偶校验码

它的码距为2，可以检测出技术位错误，但不能确定出错的位置，也不能够检测出偶数位错误。

一位校验位，校验位取0或1使这个码字中“1”的个数为奇数（奇校验）或偶数（偶检验）

循环冗余校验（Cyclic Redundancy Check，CRC）

使用二进制多项式作为除数（多项式表示为二进制数时最高位和最低位必须为1）

  1. 用除数对被除数最高位做模2减法（异或），不借位

  2. 除数右移一位，若余数最高位为1，商1，若余数最高位为0，商0，除数继续右移一位。

  3. 循环直到余数位数小于除数时，该余数为最终余数

循环冗余校验可以发现和纠正一位或多位错（与多项式的选取有关）

海明（汉明）码

设n为有效信息的位数，k为校验位的位数，n位和校验位k应满足${n + k \leqslant 2^k - 1}$

若要检测两位错误，则需要再增加1位校验位，即k+1位

它能发现双比特错，但只能纠正单比特错误

海明码纠错d位，需要码距为2d+1的编码方案；检错d位，则只需码距为d+1

流量控制与可靠传输机制

流量控制、可靠传输与滑动窗口协议

停止-等待流量控制基本原理

发送方每发送一帧，都要等待接收方的应答信号，之后才能发送下一帧

滑动窗口流量控制基本原理

发送窗口的大小$W_T$表示在还未收到对方确认信息的情况下发送方最多还可以发送多少个数据帧。

  1. 接收端收到数据帧之后，将窗口向前移一个位置，并发回确认帧，若收到的数据帧落在接收窗口之外，则一律丢弃。

  2. 发送端每收到一个确认帧，发送窗口就向前滑动一个帧的位置。

滑动窗口的重要特性：

  1. 只有接收窗口向前移动（同时接收方发送了确认帧）时，发送窗口才有可能（只有发送方收到确认帧后才一定）向前滑动

  2. 接收窗口的大小为1时，才保证帧的有序接收

  3. 数据链路层的滑动窗口协议中，窗口的大小在传输过程中是固定的

  4. 发送窗口中的帧编号和接收窗口中的接收帧编号是一一对应的

  5. 窗口帧的编号是重复使用的，例如在2比特对帧编号的情况下，第一传输用了0、1、2这三个编号，下一次发送就使用3、0、1这几个编号。

可靠传输机制

数据链路层的可靠传输通常使用确认和超时重传两种机制来完成。

有些情况为了提高传输效率，将确认捎带在一个回复帧中，称为捎带确认。

数据链路层中流量控制机制和可靠传输机制是交织在一起的

单帧滑动窗口与停止-等待协议

从滑动窗口机制的角度看，停止-等待协议相当于发送窗口和接收窗口大小均为1的滑动窗口协议

停等协议中，除数据帧丢失外，还可能出现以下两种差错：

  1. 到达目的站的帧可能已遭破坏

  2. 数据帧正确而确认帧被破坏，此时接收方已收到正确的数据帧，但发送方收不到确认帧

多帧滑动窗口与回退N帧协议（Go-back N，GBN）

从滑动窗口机制的角度看，停止-等待协议相当于发送窗口大小为n，接收窗口大小为1的滑动窗口协议，可以保证按序接收数据帧。

发送方可以连续发送帧，当接收方检测出失序的信息帧后或者某个帧未被接收方确认接收，则需要重发该帧及该帧之后的窗口中的所有帧。即接收方只允许按顺序接收帧。

源站每发送一帧就要为该帧设置超时计时器，GBN协议还规定接收端不一定每收到一个正确的数据帧就必须立即发回一个确认帧，而可以在连续收到好几个正确的数据帧后，才对最后的一个数据帧发确认消息，对某一数据帧的确认就表明数据帧和此前所有的数据帧均已正确无误的收到。$ACK_n$表示对n号帧的确认，表示接收方已正确收到第n号帧及以前的所有帧。

若采用n比特对帧编号，则其发送窗口的尺寸$W_T$应该满足${1\leqslant{W_T}\leqslant{2^n-1}}$

多帧滑动窗口与选择重传协议（Selective Repeat，SR）

从滑动窗口机制的角度看，停止-等待协议相当于发送窗口大小为n，接收窗口大小为m的滑动窗口协议，一般m=n>1

接收端每个发送缓冲区对应一个计时器，当计时器超时时，只用重发该帧。另外SR使用了更有效的差错处理策略，即一旦接收方怀疑帧出错，就会发一个否定帧NAK给发送方，要求发送方对NAK中指定的帧进行重传。

若使用n比特对帧编号，接收窗口$W_R$ + 发送窗口$W_T$ $\leqslant 2^n$，且接收窗口$W_R$不应该超过发送窗口$W_T$（否则无意义），即$W_R \leqslant 2^{n-1}$，接收窗口为最大值时，$W_Tmax = W_Rmax = 2^{n-1}$，一般情况下，在SR中，接收窗口的大小和发送窗口的大小是相同的。

接收端需要使用缓冲区，暂存未按序正确收到的帧，接收端不能接受窗口外的帧，因此所需缓冲的数目等于窗口的大小，而不是序号数目。

信道利用率和信道吞吐率

信道的效率也称信道利用率，指发送方在一个发送周期的时间内，有效发送数据所需要的时间站整个发送周期的比率，可以为100%

信道吞吐率=信道利用率 $\times$ 发送发的发送速率

介质访问控制

介质访问的主要任务是，为使用介质的每个结点隔离来自同一信道上其它结点所传送的信号，以协调活动结点的传输。

信道划分介质访问控制（静态划分信道）

多路复用是实现信道划分介质访问控制的途径。多路复用技术可把多个信道的信息整合到一个复用的信道中，在接收端把收到的信息分离出来并传送到对应的输出信道

345d5a21edbfeb0013de3f03c9b0ee6d.jpeg

实际上就是把广播通道转变为点对点通道。

频分多路复用（FDM，Frequency Division Mutiplexing）

将多路基带信号调制到不同频率载波上，在叠加形成一个复合信道的多路复用技术。

每个子信道分配的带宽可不相同，但他们的总和必须不超过信道的总带宽。在实际应用中，为了防止子信道之间的干扰，相邻信道之间需要加入“保护频带”

时分多路复用（TDM，Time Division Mutiplexing）

将一条物理信道按时间分为若干时间片，轮流的分配给多个信号使用，每个时间片由复用的一个信号占用。

统计时分多路复用（STDM，Statistical Time Division Multiplexing，又称异步时分多路复用），它不固定分配时隙，而按需动态的分配时隙，当终端有数据传送时，才会分配到时间片。

波分多路复用（WDM，Wave Division Mutiplexing）

波分多路复用即光的频分多路复用，它在一根光纤中传输多种不同波长（频率）的光信号

码分多路复用（CDM，Code Division Multiplexing）

码分多路复用是采用不同的编码来区分各路原始信号的一种复用方式。它既共享信道的频率，又共享时间

码分多址（CDMA，Code Division Multiple Access，CDMA）是码分复用的一种方式。它将每个比特时间被分成m个更短的时间槽，称为“码片”，通常每比特有64或128个码片。每个站点分配唯一的m位代码或码片序列，站点发送1时，站点发送码片序列；发送0时，站点发送码片序列的反码。

定义向量的规格化内积：${S·T = \frac{1}{m}\sum_{i=0}^mS_iT_i}$，S,T为向量，${S_i}$ $T_i$表示向量的元素

例如A站和B站共享一条物理信道发送信息给C站，A站点的码片序列为00011011，则A站点发送00011011就表示发送比特1，发送11100100就表示发送比特0。将码片中的0写为-1，将1写为+1，A站的码片序列就是-1-1-1+1+1-1+1+1。

B站的码片序列需要和A站的码片序列相互正交（规格化内积为0，-1和1表示的情况下），所以在这个例子中可以选择B站的码片序列为-1-1+1-1+1+1+1-1（不止这一种）。当A站发送1（-1 1 -1 +1 +1 -1 +1 +1），B站发送0（+1 +1 -1 +1 -1 -1 -1 +1）时，两个信号在信道上叠加，即$A_1-B_0$得（0 0 -2 2 0 -2 0 -2）。数据发送到C站后，C站将收到的结果于A站的码片进行规格化内积，如果结果为1，表示A站发送的是1，如果结果是-1，表示结果为0。同理相获得B站的信息主要和B站的码片做规格化内积即可。

码分多路复用技术主要用于无线通信系统，特别是移动通信系统

随机访问介质访问控制（动态划分信道）

其核心思想是胜利者通过争用获得信道，从而获得信息的发送权。因此随机访问介质控制协议又称争用型协议

采用随机访问控制机制，各结点之间的通信就即不共享时间，也不共享空间。实质上也是将广播信道转化为点到点的通信。

纯ALOHA协议

当网络中的任何一个站点需要发送数据时，可以不进行任何检测就发送数据。如果在一段时间内未收到确认，那么站点就认为传输过程中发生了冲突。发送站点需要等待一段时间后再发送数据，直至发送成功。

纯ALOHA系统采用的重传策略是让各站等待一段随机的时间，然后进行重传。纯ALOHA网络的最大吞吐量为0.184

时隙ALOHA协议

它将所有各站在时间上同步起来，并将时间划分为一段段等长的时隙（Slot），规定只能在每个时隙开始才能发送一个帧。时隙ALOHA的最大吞吐量为0.368

CSMA（Carrier Sense Multiple Access，载波侦听多路访问）协议

1-坚持CSMA

一个结点要发送数据时，首先侦听信道，如果信道空闲，那么立即发送数据。如果信道忙，那么等待，同时继续侦听直至信道空闲。如果发生冲突，那么随机等待一段时间后，再重新开始侦听信道。

非坚持CSMA

如果信道空闲，那么立即发送数据；如果信道忙，则放弃监听，等待一个随机的时间后再重复上述过程。

非坚持CSMA降低了多个结点等待信道空闲后同时发送数据导致冲突的概率，但也会增加数据在网络中的平均延迟。

P-坚持CSMA

如果信道忙，那么等待下一个时隙在侦听，如果信道空闲，那么以概率p发送数据，以1-p的概率推迟到下一个时隙；如果在下一个时隙信道仍然空闲，那个仍然以概率p发送数据，以概率1-p推迟到下一个时隙。一直持续这个过程知道发送成功或者检测到信道忙，若是后者，则等待一个随机的时间后重新开始侦听。

三种CSMA协议比较

信道状态 1-坚持 非坚持 p-坚持
空闲 立即发送数据 立即发送数据 以概率p发送数据，以概率1-p推迟到下一个时隙
忙 继续坚持侦听信道 放弃侦听，等待一个随机的时间后再侦听 持续侦听，等待下一个时隙再侦听
发生冲突 随机等待一段时间后再开始侦听 随机等待一个随机的时间后重新开始侦听

CSMA/CD（Carrier Sense Multiple Access With Collision Detection，载波侦听多路访问/碰撞检测）协议

其流程可概括为先听后发，边听边发（区别于CSMA协议），冲突停发，随机重发：

  1. 适配器侦听信道，如果信道空闲，则开始传输该帧，如果适配器侦听到信道忙，那么它将等待直至侦听到没有信号能量，然后开始传输该帧。

  2. 在传输过程中，适配器检测到其它适配器的信号能量，如果检测到来自其它适配器的信号能量并且自己没有传输完该帧，则停止该帧的传输，取而代之传输一个48比特的拥塞信号。

  3. 在传输拥塞信号后，适配器采用截断二进制指数退避算法等待一段时间，后返回步骤1。

CSMA/CD中的站点不能同时发送和接收，因此采用CSMA/CD协议的以太网不太可能进行全双工通信，而只能进行半双工通信。

把以太网端到端（最远两端）往返时间称为争用期（又称冲突窗口或碰撞窗口）2815a283496c61f654f8dfed86cabe0c.jpeg

CSMA/CA中帧的传输时延至少要两倍于信号在线路中的传播时延，所以CSMA/CD总线网中的所有数据帧都必须要大于一个最小帧长，任何站点收到帧长小于最小帧长的帧时，就把它当做无效帧立即丢弃。最小帧长 = 总线传播时延 $\times$ 数据传输率 $\times$ 2。

例如，以太网规定最小帧长为64B，如果前64B未发生冲突，那么后续数据也就不会发生冲突（表示以成功抢占信道）。如果数据小于64B，那么就需要在MAC子层中在数据字段后面加入一个整数字节的填充字段。以保证以太网的MAC帧的长度不小于64B。

二进制指数退避（动态退避）算法

  1. 确定基本退避时间，一般取两倍的争用期时间。

  2. 定义参数k，它等于重传次数，但k不超过10，即k=min[重传次数，10]

  3. 从离散的整数集合[0, 1, 2, 3, … , $2^k-1$]中随机取出一个数r，重传所需要退避的时间就是r倍的基本退避时间

4.当重传达16次仍不能成功时，认为此帧永远无法正确发出，抛弃此帧并向高层报告出错

CSMA/CA（Carrier Sense Multiple Access With Collision Avoidance，载波侦听多路访问/碰撞避免）

碰撞避免并不是指协议可以完全避免碰撞，而是指协议的设计要尽量降低碰撞发生的概率。

CSMA/CA也采用二进制指数退避算法。即使信道从忙变为空闲时，任何一个站要发送数据帧时，不仅都须等待一个时间间隔，而且还要进入争用期窗口。并计算随机退避时间以便在此试图接入信道，而且仅当检测到信道空闲并且这个数据帧是要发送的第一数据帧时，才不使用退避算法。

CSMA/CA还采用预约信道，ACK帧，RTS/CTS帧等三种机制来实现碰撞避免：

  1. 预约信道，发送方在发送数据的同时向其它站点通知自己传输数据需要的时间长度，以便让其它站点在这段时间内不发送数据，从而避免碰撞。

  2. ACK帧，所有站点在正确接收到发给自己的数据帧（除广播帧和组播帧）后，都需要向发送方发回一个ACK帧。发送方在规定时间内如果未收到ACK帧，那么认为发送失败，此时进行该数据帧的重发，直到收到ACK帧或达到规定重发次数为止。

  3. RTS/CTS帧(Request To Send/Clear To Send，请求发送/清除发送)。可选的碰撞避免机制，主要用于解决无线网络中的隐蔽站的问题。

CSMA/CD与CSMA/CA的区别

  1. CSMA/CD可以检测冲突，但无法避免；CSMA/CA发送包的同时不能检测信道上有无冲突（就是因为无法检测冲突，所以自己的站点不能判断一个帧是否发送成功，所以要使用ACK）

  2. 传输介质不同，CSMA/CD用于总线以太网，CSMA/CA用于无线局域网。

  3. 检测信道空闲的方法不同。

  4. 在本结点处有(无)冲突，并不意味着在在接收点处就有(无)冲突。（两种协议都是）

CSMA/CD与CSMA/CA总结

CSMA/CA协议的基本思想是在发送数据时先广播告知其他结点，让其他结点在某段时间内不要发送数据，以免出现碰撞。CSMA/CD协议的基本思想是发送前侦听，边发送边侦听，一旦出现碰撞马上停止发送。

轮询访问介质控制协议：令牌传递协议

在轮询访问中，通过一个集中控制的监控站，以循环方式轮询每个结点，在决定信道的分配。当某个结点使用信道时，其他结点都不能使用信道。典型的轮询访问控制协议是令牌传递协议，它主要用于令牌环形局域网中。

令牌传递协议中，一个令牌在各结点间以某个固定次序交换（在环上单向传输）。令牌是由一组特殊的比特组合而成的帧。当环上的一个站希望传送帧时，必须等待令牌。一旦收到令牌，站点便可启动发送帧。帧在环上传送时，不管该帧是否是发送给本站点的，所有站点都进行转发，直到该帧发回它的始发站，并由该始发站撤销该帧。帧的目的站除转发帧外，应针对该帧维持一个副本，通过在帧的尾部设置“相应比特”来指示已收到此副本。站点在发送完一帧后，应立即释放令牌，以便让其他站使用。

因为令牌只有一个，所以不会发生冲突。

轮询介质访问控制非常适合负载很高的广播信道。因为对于负载很高的信道采用随机介质访问控制，发生冲突的概率会很大。

轮询介质访问既不共享时间，也不共享空间。