查看“差错控制”的源代码


实际通信链路都不是理想的,比特在传输过程中可能会产生差错,1可能会变成0, 0也可能会变成1,这就是比特差错。比特差错是传输差错中的一种。

通常利用编码技术进行差错控制，主要有两类：自动重传请求 ARQ 和前向纠错 FEC。在 ARQ方式中,接收端检测到差错时,就设法通知发送端重发,直到接收到正确的码字为止。在FEC方式中,接收端不但能发现差错,而且能确定比特串的错误位置,从而加以纠正。因此,差错控制又可分为检错编码和纠错编码。

== 检错编码 ==

检错编码都采用冗余编码技术,其核心思想是在有效数据(信息位)被发送前,先按某种关系附加一定的冗余位,构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时,相应的冗余位也随之变化,使得码字遵从不变的规则。接收端根据收到的码字是否仍符合原规则来判断是否出错。常见的检错编码有奇偶校验码和循环冗余码。

=== 奇偶校验码 ===

奇偶校验码是奇校验码和偶校验码的统称，是一种最基本的检错码。它由 n-1 位信息元和1位校验元组成,如果是奇校验码,那么在附加一个校验元后,码长为n的码字中“1”的个数为奇数;如果是偶校验码,那么在附加一个校验元以后,码长为n的码字中“1”的个数为偶数。它只能检测奇数位的出错情况,但并不知道哪些位错了,也不能发现偶数位的出错情况。

=== 循环冗余码 ===

循环冗余码(Cyclic Redundancy Code, CRC)又称多项式码,任何一个由二进制数位串组成的代码都可与一个只含有 0 和 1 两个系数的多项式建立对应关系。

给定一个m bit的帧或报文，发送器生成一个rbit的序列,称为帧检验序列(FCS)。这样所形成的帧将由m+r比特组成。发送方和接收方事先商定一个多项式G(x) (最高位和最低位必须为1),使这个带检验码的帧刚好能被预先确定的多项式G(x)整除。接收方用相同的多项式去除收到的帧,如果无余数，那么认为无差错。

假设一个帧有m位,其对应的多项式为M(x),则计算冗余码的步骤如下:

# 加0。假设G(x)的阶为r,在帧的低位端加上r个0。
# 模2除。利用模2除法，用G(x)对应的数据串去除上一步中计算出的数据串，得到的余数即为冗余码(共r位,前面的0不可省略)。

多项式以2为模运算。按照模2运算规则,加法不进位,减法不借位,它刚好是异或操作。乘除法类似于二进制的运算,只是在做加减法时按模2规则进行。

通过循环冗余码(CRC)的检错技术,数据链路层做到了对帧的无差错接收。也就是说,凡是接收端数据链路层接受的帧,我们都认为这些帧在传输过程中没有产生差错;而接收端丢弃的帧虽然也收到了,但最终因为有差错而被丢弃,即未被接受。

<blockquote>注意：循环冗余码（CRC）是具有纠错功能的，只是数据链路层仅使用了它的检错功能，检测到帧出错则直接丢弃，是为了方便协议的实现。
</blockquote>
== 纠错编码 ==

在数据通信的过程中,解决差错问题的一种方法是在每个要发送的数据块上附加足够的冗余信息,使接收方能够推导出发送方实际送出的应该是什么样的比特串。最常见的纠错编码是海明码,其实现原理是在有效信息位中加入几个校验位形成海明码,并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错位，而且能指出错位的位置，为自动纠错提供依据。

= 流量控制与可靠传输机制 =

<span id="流量控制可靠传输与滑动窗口机制"></span>
== 流量控制、可靠传输与滑动窗口机制 ==

流量控制涉及对链路上的帧的发送速率的控制,以使接收方有足够的缓冲空间来接收每个帧。例如,在面向帧的自动重传请求系统中,当待确认帧的数量增加时,有可能超出缓冲存储空间而造成过载。流量控制的基本方法是由接收方控制发送方发送数据的速率,常见的方式有两种:停止-等待协议和滑动窗口协议。

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

发送方每发送一帧，都要等待接收方的应答信号，之后才能发送下一帧；接收方每接收一帧，都要反馈一个应答信号,表示可接收下一帧,如果接收方不反馈应答信号,那么发送方必须一直等待,每次只允许发送一帧,然后就陷入等待接收方确认信息的过程中,因而传输效率很低。

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

在任意时刻,发送方都维持一组连续的允许发送的帧的序号,称为发送窗口;同时接收方也维持一组连续的允许接收帧的序号,称为接收窗口。发送窗口用来对发送方进行流量控制,而发送窗口的大小代表在还未收到对方确认信息的情况下发送方最多还可以发送多少个数据帧。同理,在接收端设置接收窗口是为了控制可以接收哪些数据帧和不可以接收哪些帧。在接收方,只有收到的数据帧的序号落入接收窗口内时,才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。

发送端每收到一个确认帧，发送窗口就向前滑动一个帧的位置，当发送窗口内没有可以发的帧(即窗口内的帧全部是已发送但未收到确认的帧)时,发送方就会停止发送,直到收到接收方发送的确认帧使窗口移动,窗口内有可以发送的帧后,才开始继续发送。

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

滑动窗口有以下重要特性：

<ol style="list-style-type: decimal;">
<li><p>只有接收窗口向前滑动(同时接收方发送了确认帧)时,发送窗口才有可能(只有发送方收到确认帧后才一定)向前滑动。</p></li>
<li><p>从滑动窗口的概念看，停止-等待协议、后退N帧协议和选择重传协议只在发送窗口大小与接收窗口大小上有所差别：</p>
<p>停止-等待协议:发送窗口大小=1,接收窗口大小=1。后退 N 帧协议：发送窗口大小&gt;1，接收窗口大小=1。选择重传协议:发送窗口大小&gt;1,接收窗口大小&gt;1。</p></li>
<li><p>接收窗口的大小为1时,可保证帧的有序接收。</p></li>
<li><p>数据链路层的滑动窗口协议中，窗口的大小在传输过程中是固定的。</p></li></ol>

=== 可靠传输机制 ===

数据链路层的可靠传输通常使用确认和超时重传两种机制来完成。确认是一种无数据的控制帧,这种控制帧使得接收方可以让发送方知道哪些内容被正确接收。有些情况下为了提高传输效率,将确认捎带在一个回复帧中,称为捎带确认。超时重传是指发送方在发送某个数据帧后就开启一个计时器，在一定时间内如果没有得到发送的数据帧的确认帧，那么就重新发送该数据帧，直到发送成功为止。

自动重传请求(Automatic Repeat reQuest, ARQ)通过接收方请求发送方重传出错的数据帧来恢复出错的帧，是通信中用于处理信道所带来差错的方法之一。传统自动重传请求分为三种，即停止-等待(Stop-and-Wait) ARQ、后退N帧(Go-Back-N) ARQ和选择性重传(Selective Repeat)ARQ。后两种协议是滑动窗口技术与请求重发技术的结合,由于窗口尺寸开到足够大时,帧在线路上可以连续地流动,因此又称其为连续ARQ协议。注意,在数据链路层中流量控制机制和可靠传输机制是交织在一起的。

<blockquote>注意：现有的实际有线网络的数据链路层很少采用可靠传输（不同于OSI参考模型的思路)。
</blockquote>
== 单帧滑动窗口与停止-等待协议 ==

在停止-等待协议中，源站发送单个帧后必须等待确认，在目的站的回答到达源站之前，源站不能发送其他的数据帧。从滑动窗口机制的角度看,停止-等待协议相当于发送窗口和接收窗口大小均为1 的滑动窗口协议。

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

到达目的站的帧可能已遭破坏,接收站利用前面讨论的差错检测技术检出后,简单地将该帧丢弃。为了对付这种可能发生的情况,源站装备了计时器。在一个帧发送后,源站等待确认,若在计时器计满时仍未收到确认,就再次发送相同的帧。如此重复,直到该数据帧无错误地到达为止。

另一种可能的差错是数据帧正确而确认帧被破坏，此时接收方已收到正确的数据帧，但发送方收不到确认帧,因此发送方会重传已被接收的数据帧,接收方收到同样的数据帧时会去弃该帧,并重传一个该帧对应的确认帧。发送的帧交替地用0和1来标识,确认帧分别用ACK0和ACK1来表示，收到的确认帧有误时，重传已发送的帧。对于停止-等待协议，由于每发送一个数据帧就停止并等待,因此用1bit来编号就已足够。在停止-等待协议中,若连续出现相同发送序号的数据帧,表明发送端进行了超时重传。连续出现相同序号的确认帧时,表明接收端收到了重复帧。在发送完数据帧时,必须在其发送缓存中保留此数据帧的副本,这样才能在出差错时进行重传。

此外，为了超时重发和判定重复帧的需要，发送方和接收方都须设置一个帧缓冲区。发送端只有在收到对方发来的确认帧ACK时,方可清除此副本。

停止-等待协议通信信道的利用率很低。为了克服这一缺点，就产生了另外两种协议，即后退N帧协议和选择重传协议。

<span id="多帧滑动窗口与后退n帧协议gbn"></span>
== 多帧滑动窗口与后退N帧协议(GBN) ==

在后退N帧式ARQ中,发送方无须在收到上一个帧的ACK后才能开始发送下一帧,而是可以连续发送帧。当接收方检测出失序的信息帧后,要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧;或者当发送方发送了N个帧后,若发现该N个帧的前一个帧在计时器超时后仍未返回其确认信息,则该帧被判为出错或丢失,此时发送方就不得不重传该出错帧及随后的N个帧。换句话说，接收方只允许按顺序接收帧。

源站向目的站发送数据帧。当源站发完 0号帧后，可以继续发送后续的1号帧、2号帧等。源站每发送完一帧就要为该帧设置超时计时器。由于连续发送了许多帧,所以确认帧必须要指明是对哪一帧进行确认。为了减少开销,GBN协议还规定接收端不一定每收到一个正确的数据帧就必须立即发回一个确认帧,而可以在连续收到好几个正确的数据帧后,才对最后一个数据帧发确认信息,或者可在自己有数据要发送时才将对以前正确收到的帧加以捎带确认。这就是说,对某一数据帧的确认就表明该数据帧和此前所有的数据帧均已正确无误地收到,称为累积确认。

ACKn表示对第n号帧的确认,表示接收方已正确收到第n号帧及以前的所有帧,下一次期望收到第n+1号帧(也可能是第0号帧)。接收端只按序接收数据帧。虽然在有差错的2号帧之后接着又收到了正确的6个数据帧,但接收端都必须将这些帧丢弃。接收端虽然丢弃了这些不按序的无差错帧,但应重复发送已发送的最后一个确认帧ACK1 (这是为了防止已发送的确认帧ACK1丢失)。

后退 N帧协议的接收窗口为 1，可以保证按序接收数据帧。若采用n比特对帧编号，则其为送窗口的尺寸所应满足1&lt;肝≤2”-1。若发送窗口的尺寸大于2”-1，则会造成接收方无法分院新帧和旧帧。

后退N帧协议一方面因连续发送数据帧而提高了信道的利用率,另一方面在重传时又必须把原来已传送正确的数据帧进行重传(仅因这些数据帧的前面有一个数据幢出了错),这种做法又使传送效率降低。由此可见,若信道的传输质量很差导致误码率较大时,后退N帧协议不一定优于停止-等待协议。

<span id="多帧滑动窗口与选择重传协议sr"></span>
== 多帧滑动窗口与选择重传协议（SR) ==

为进一步提高信道的利用率,可设法只重传出现差错的数据帧或计时器超时的数据帧,但此时必须加大接收窗口，以便先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。这就是选择重传ARQ协议。

在选择重传协议中,每个发送缓冲区对应一个计时器,当计时器超时时,缓冲区的帧就会重传。另外,该协议使用了比上述其他协议更有效的差错处理策略,即一旦接收方怀疑帧出错,就会发一个否定帧NAK给发送方,要求发送方对NAK中指定的帧进行重传。

选择重传协议的接收窗口尺寸WR和发送窗口尺寸Wr都大于1，一次可以发送或接收多个帧。在选择重传协议中，接收窗口和发送窗口的大小通常是相同的(选择重传协议是对单帧进行确认，所以发送窗口大于接收窗口会导致溢出,发送窗口小于接收窗口没有意义),且最大值都为序号范围的一半，若采用n比特对帧编号，则需要满足WTmax=WRmax=2(n-1)。因为如果不满足该条件，即窗口大小大于序号范围一半,当一个或多个确认帧丢失时,发送方就会超时重传之前的数据帧,但接收方无法分辨是新的数据帧还是重传的数据帧。

选择重传协议可以避免重复传送那些本已正确到达接收端的数据帧，但在接收端要设置具有相当容量的缓冲区来暂存那些未按序正确收到的帧。接收端不能接收窗口下界以下或窗口上界以上的序号的帧,因此所需缓冲区的数目等于窗口的大小,而不是序号数目。