通信网络第二章_2讲解

《通信网络第二章_2讲解》由会员分享，可在线阅读，更多相关《通信网络第二章_2讲解（96页珍藏版）》请在金锄头文库上搜索。

1、第2章 端到端的传输协议,通信工程学院信息科学研究所,2.2 链路层的差错控制技术,2.2.1 差错检测 2.2.2 ARQ协议 2.2.3 最佳帧长,2.2.1 差错检测(1),链路层差错检测的目的是：如何有效地发现一帧数据比特经过物理信道传输后是否正确。,2.2.1 差错检测(2),常用的检错方法 奇偶校验 循环冗余校验CRC（Cyclic Redundancy Check） 其基本思路是发端按照给定的规则,在K个信息比特后面增加L个按照某种规则计算的校验比特;在接收端对收到的信息比特重新计算L个校验比特。比较接收到的校验比较和本地重新计算的校验比特，如果相同则认为传输无误，否则认为传输有

2、错。,1.奇偶校验码(1),例： 信息序列长K=3，校验序列长L=4。输入信息比特为 S1，S2，S3，校验比特为 C1，C2，C3，C4，校验的规则为,1.奇偶校验码(2),1.奇偶校验码(3),例如：设发送的信息比特为100，经过奇偶校验码生成的校验序列为1110，则发送的信息序列为1001110。,若经过物理信道传输后，接收的序列为1011110，则本地根据收到的信息比特101计算出的校验序列应为0011。显然该序列与接收到的校验序列1110不同，表明接收的信息序列有错。,1.奇偶校验码(4),如果L取1，即 为最简单的单比特的奇偶校验码，它使得生成的码字（信息比特+校验比特）所含“1”

3、的个数为偶数。该码可以发现所有奇数个比特错误，但是不能发现任何偶数个错误。,1.奇偶校验码(5),在实际应用奇偶校验码时，每个码字中K个信息比特可以是输入信息比特流中K个连续的比特，也可以按一定的间隔（如一个字节）取K个比特。为了提高检测错误的能力，可将上述两种取法重复使用。,0101001110110110011101010,L个校验比特,0010011011101 0011101110001 1110000001111 0010011011101 0011101110001 1110000001111,N个比特,CRC校验（1）,CRC（循环冗余校验）是根据输入比特序列 通过下列CRC算法

4、产生L位的校验比特序列,CRC校验（2）,将输入比特序列表示为下列多项式的系数： 式中：D可以看成为一个时延因子，Di 对应比特 Si 所处的位置。,例如：10101100，S(D)=D7+D5+D3+D2,CRC校验（3）,设CRC校验比特的生成多项式为(g(D)=D16+D15+D2+1) 则校验比特对应下列多项式的系数： 式中：Remainder表示取余数。式中的除法与普通的多项式长除相同，其差别是系数是二进制，其运算以模2为基础。,CRC校验（4）,例如， 的商为 余数为,CRC校验（5）,常用的几个L阶CRC生成多项式为： CRC-16（L=16）： CRC-CCITT（L=16）：

5、 CRC-32（L=32）：,CRC校验（3）,设CRC校验比特的生成多项式为(g(D)=D16+D15+D2+1) 则校验比特对应下列多项式的系数： 式中：Remainder表示取余数。式中的除法与普通的多项式长除相同，其差别是系数是二进制，其运算以模2为基础。,CRC校验（6）,例2.1 ：设输入比特序列为（10110111），采用CRC-16生成多项式，求其校验比特序列。,解：输入比特序列可表示为 因为,CRC校验(7),所以,CRC校验(8),由此式可得校验比特序列为：（0000001110110010）。最终形成的经过校验后的发送序列为（10110111000000111011001

6、0）。,在接收端，将接收到的序列 与生成多项式 g(D)相除，并求其余数。如果 则认为接收无误。,CRC校验(9),有两种情况：一是接收的序列正确无误；二是有错，但此时的错误使得接收序列等同于某一个可能的发送序列。后一种情况称为漏检。,2.2.2 ARQ协议(1),前面解决了如何发现传输帧的错误问题，下面要解决当接收端发现传输帧有错如何处理的方法。,出错的最简单处理方法是（收端）自动请求发端重发（ARQ，Automatic Retransmission Request）。即收端收到一帧后，经过CRC检验，如果发现该帧传输有误，则通过反馈信道（该信道可以与前向传输相同，也可以不同）以某种反馈规则

7、通知发端重复上述过程，直到收端收到正确的帧为止。对反馈规则和重传规则的设计，要保证整个自动重传协议的正确性和有效性。,2.2.2 ARQ协议(2),为了研究ARQ协议，我们对物理比特管道（物理链路）作如下假定：,（1）在物理信道上传输的帧到达接收端前被时延了一个任意可变的时间；,（2）帧在传输过程中可能会丢失，也可能出错；,（3）帧到达的顺序与发送的顺序相同。,2.2.2 ARQ协议(3),有四种不同形式的ARQ重传协议 停等式ARQ 返回n-ARQ 选择重发式ARQ 并行等待式ARQ,1.停等式ARQ（1）,停等式ARQ（Stop-and-Wait ARQ）的基本思想是在开始下一帧传送以前，

8、必须确保当前帧已被正确接收。,1.停等式ARQ（1）,假定A发，B收。具体的传送过程如下：A发送一帧后，B如果接收正确，则B向A返回一个肯定的应答（ACK）；B如果接收错误，则B向A返回一个否定应签（NAK）。A必须在收到B的正确ACK后，方可发送下一帧。如果A发送一帧后（并给定时器设置一个初值），在一个规定的时间内（定时器溢出），没有收到对方的ACK，则重发该帧；如果收到了NAK，也要重发该帧。,1.停等式ARQ（2）,由于A到B之间的双向链路都可能出错，上述协议能否正常工作？或者说如何保证该协议能够正确工作呢？,基本的方法是在传输的帧中增加发送序号（SN）和接收序号（RN） 。,接收序号（

9、RN）通常用接收端希望接收的下一个发送帧的序号（SN）(也可以是下一帧的第一个字节的编号。),1.停等式ARQ（3）,由于A到B之间的双向链路都可能出错，保证该协议能够正确工作的基本方法是：在传输的帧中增加发送序号（SN）和接收序号（RN） 。,无发送序号情况,无接收序号情况,A无法区分该ACK是对那个分组的应答,等待式ARQ协议的严格描述（1）,假定A向B发送分组（AB），节点A的发送算法如下：,（1）置SN=0。,（2）如果从高层接收到一个分组，则将SN指配给该分组；如果没有高层分组，则等待。,（3）将发送序号为SN的分组装入的物理帧中发送给接收节点B。,（4）如果从B接收的RNSN，则将

10、SN加1，返回（2）。如果在规定的有限长时间内，没有从B接收到RNSN的帧（应答），则返回（3）进行重传。,等待式ARQ协议的严格描述（2）,节点B的接收算法如下：,（1）置RN=0。,（2）无论何时从A正确接收一个SN=RN的帧，将该帧中的分组送给高层，并将RN加1。,（3）在接收到该分组后的一个规定的有限长时间内，将RN放入一帧的RN域中发给A。返回（2）。,等待式ARQ协议性能评估,算法（协议）的正确性 算法（协议）的有效性,等待式算法（协议）的正确性,所谓算法的正确性是指算法始终能够正常工作，正确接收输入的数据和状态，产生正确的动作和正确的输出结果。,对于不同的算法，其正确性有不同的描

11、述。对于停等式ARQ协议而言，所谓“该算法是正确的”是指：A能够始终不断地从高层接收数据分组，B能够始终按照发端的顺序向B的高层呈送接收到的分组，既不重复，也不丢失。,等待式算法的正确性证明,算法的正确性证明可分为两部分：一是稳妥性（Safety），即算法决不会产生不正确的结果（在这里是指提交给上层分组的顺序不对）；二是活动性（Liveness），即算法会永远不停地产生结果（不会产生死循环，一旦进入死循环，将不会进行进一步的处理），在这里指在A节点能够不停地接收高层的分组，在B节点能够不停地将这些分组呈送给高层。,等待式ARQ协议稳妥性证明,在停等式ARQ中，稳妥性是很明显的。在算法开始时，S

12、N=0，RN=0，节点B等待RN=0的帧，因而仅会有SN=0帧中的分组送上高层。由于RN是将要接收的下一个帧的序号，接收到一个新的帧后RN加1，这样重发帧的序号小于RN，因而其中的分组不可能送给高层。所以，节点B能按顺序将分组呈现给高层。,等待式ARQ算法活动性证明（1）,为了考察该算法的活动性，假定A在 t1时刻开始发送给定的分组i，B在 t2时刻正确接收到该分组，A在 t3时刻正确接收到B的应答。显然，如果 t2，则表示B收不到A的分组；如果 t3，则表示A收不到B的应答。因而，要证明该算法的活动性就要证明,等待式ARQ算法活动性证明（2）,为了证明该协议的正确性，我们假定： 所有错误的分

13、组都能被CRC检出； 一个分组能够被正确接收的概率为 q，q0。,等待式ARQ算法活动性证明（3）,令 t时刻的RN和SN为RN(t)和SN(t)，显然它们是时间t的非降函数。由于SN(t)是t时刻以前，从B接收到的最大请求序号，所以SN(t) RN(t) 。由于分组 i在t1时刻开始第一次传输（A在 t1以前从未传送过分组 i），则根据稳妥性（算法不会产生不正确的结果）有 RN(t1)i，又因为 SN(t1)i，所以有,等待式ARQ算法活动性证明(4),又根据假定：在 时， 时， 。利用 RN(t)和SN(t) 的非降特性和SN(t) RN(t) ，则有 。,等待式ARQ算法活动性证明(5)

14、,根据算法，A将会重复发送分组 i，其重发的间隔是有限的。又由于分组被成功接收的概率 q0，因而分组 i会在有限次传输后被正确接收。也就是说，从 t1至 t2的间隔是有限的。,由于A不停地以有限长的间隔发送分组 i，这将导致节点B以有限的间隔发送应答（包括RN的分组）。由于B成功传输的概率 q0，所以应答在有限的时间内到达A，即 t3是有限的。证毕,等待式ARQ算法,在前面的讨论中，假定SN和RN是随时间任意增加的。这样就需要很大的比特域来表示发送序号。但实际上是不需要的，可以采用一个整数的模值（mod N）来表示，如SN mod 8, SN mod 128等。很容易看出对于停等式ARQ，取模

15、2就足够了。,等待式ARQ算法有效性(1),算法的有效性可以从三个主要方面来表述：一是吞吐量（或通过量），二是链路的利用率，三是分组延迟。,所谓吞吐量就是在给定的物理信道和输入分组流的条件下，接收端能够呈送给高层的分组速率（分组/秒或比特/秒）。,所谓链路的利用率就是指物理层（比特管道）的传输容量中用于有效分组传输所占的比例。在信道中，如果被等待、重传和其它不必要的传输所占的比例越少，则说明信道利用率越高。,分组延迟是指链路层从发端收到高层的分组开始到收端将该分组呈送给高层为止所需的时间。,等待式ARQ算法有效性(2),设数据帧是固定帧长； 其传输时间为 TD秒； 物理信道的传播时延为 Tp秒

16、； 则在忽略算法的处理时延的情况下，一帧的传输周期为：,等待式ARQ算法有效性(2),设任意一个数据帧平均需要发送 NT次，则该帧平均一共需要NT个传输周期； 物理链路的最大平均利用率为：物理层（比特管道）的传输容量中用于有效分组传输所占的比例。,又假定数据帧的误帧率为 应答帧因长度很短，其出错的可能性可以忽略， 则一个数据帧发送i次成功的概率为,等待式ARQ算法有效性(3),令 ， 忽略应答帧的传输时间 则有,等待式ARQ算法有效性(4),链路的最大平均利用率为：,停等式ARQ算法有效性(5),停等式ARQ的最大平均吞吐量为（接收端能够呈送给高层的分组速率（分组/秒或比特/秒）,等待式ARQ算法有效性(6),停待式ARQ的平均分组延迟为： 链路层从发端收到高层的分组开始到收端将该分组呈送给高层为止所需的时间。