复习计算机网络——第三章记录（1）

数据链路层

功能：通过一些数据链路层的协议，在不太可靠的物理链路上实现可靠的数据传输。

相关基本概念：

1、结点（node）：网络中的主机（host）和路由器（router）。

2、链路（link）：通信路径上连接相邻结点的通信信道，中间没有任何其他的交换结点。一条链路只是一条通路的一个组成部分。

3、数据链路(data link):要在一根线路上传送数据，除了要有一条物理线路外，还要有一些必要的规程来控制这些数据的传输。将实现这些规程的硬件和软件加到链路上，就构成了数据链路。

4、规程:早期的数据通信协议曾叫作通信规程。因此在数据链路层，规程和协议是同义语。

5、数据链路层协议:定义了一条链路的两个结点间交换的数据单元格式，以及结点发送和接收数据单元的动作。

6、点到点（point to point）通信：在相邻结点间的一条链路上的通信。（数据链路层）

7、端到端（end to end）通信：从源结点（source node）到目的结点（destination node）通信。通信路径（path）可能由多个链路组成.（传输层）

数据链路层为网络层提供三种合理的服务

1、无确认无连接服务。

      （1）误码率很低的线路，错误恢复留给高层。

      （2）实时业务。

      （3） 大部分局域网。

2、有确认无连接服务。

       （1）适用于不可靠的信道，如无线网。

3、有确认有连接服务。

一、成帧方法

成帧的目的：提高传输效率、差错控制。

帧同步：以帧为单位进行传送，指出哪里是帧的开始和结束。

1、字符计数法

方法：在帧头中用一个域来表示整个帧的字符个数。

可能产生的错误：一个帧出错了，本帧及后面的帧都会产生影响，都有可能出错。

2、带字符填充的首尾字符定界法（字节填充的标志字节法）

方法：1、由标志字节分隔的帧。若在二进制数中偶然出现的标志字节前插入一个转义字节（ESC）。

缺点：局限于8位字符和ASCII字符传送。

帧定界符(标志字段)的值:0x7E;

转义字符:“ESC”,其值:0x7D;

当数据中出现帧定界符0x7E时,将其转变为: (0x7D,0x5E);

当数据中出现转义符0x7D时,将其转变为:(0x7D,0x5D）；

3、带位填充的首尾标记定界法（比特填充的标志比特）

方法：帧的起始和结束都用一个特殊的位串“01111110”，称为标记(flag), 即 ‘01111110’.

可能存在问题及解决办法：存在01111110的帧，我们规定连续5个1后一定要有一个0，在接收之后去掉即可。

二、差错控制

差错产生的原因：噪声。

可能产生的错误：数据帧出错、数据帧丢失。

目的:使DL（数据链路层）能够向上层提供无差错的服务(链路有干扰)。

基本原理:接收端向发送端发送确认信息(ACK,NAK)。

噪声类型：

1、白噪声: 随机错误，某一码元与前后码元无关的错误，单个出现。

2、冲击噪声:突发错误，某一码元与前后码元有关的错误，成串密集出现。

如何进行差错的检测和纠正呢？

方法：数据之外加冗余编码，分别叫做检错码和纠错码。

检错码: 通过编码检查能自动发现差错

纠错码: 除了能知道出错，还能知道错误发生的位置

检错码：奇偶校验码、CRC编码。

纠错码：纠1位错的海明码。

1、CRC编码

码多项式：将码元序列中的每一位看成是一个多项式的系数，则一个码元序列对应一个多项式，这个多项式被称为该码元序列的多项式。

例子：码元序列：10110

  1   0    1    1   0   

 1x4+0x3+1x2+1x1+0x0   = x4+x2+x1

使用方法：

模2运算

   加法不进位，减法不借位，除法中的减法仍然采用模2运算，可以理解为一种亦或运算，相同为0，不同为1。

例子：加法                          减法

         10011011                     11110000

    ＋ 11001010                    -10100110

         01010001                     01010110

CRC码基本实现原理：

       在要传输的码元序列（帧）后加上校验和（checksum），使带校验和的帧的多项式能被G(x)除尽；收方接收时，用G(x)去除它，若有余数，则传输出错（此处就是检错的原理）。

帧的尾部的校验和的得到方法：

        设G(x)为 r 阶，在帧的末尾加 r 个0，使帧为m + r位，相应多项式为xrM(x)；

        按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串；

具体实现步骤：

1、将要传送的数据位后面加上r个0， xr M(x)。

2、用xr M(x)除以G(x),得到的余数r(x)。

3、用xr M(x)减去余数r(x) ,构成要传输的n位数据T(x)。

感觉文字看比较难理解，例子可以比较直接：

2、纠1位错的海明码 

问：纠1位错，需要多少位冗余位呢？

数据位：m, 冗余位：r;

设一个系统中，编码后的码字位数是 n，则 n=m+r。 

问：纠正单个错需要的冗余位跟数据位的关系是什么？

     （m+r+1）<=2^r

问：什么是海明距离？

海明距离是将一个字符串变换成另外一个字符串所需要替换的字符个数

纠1位错的海明码的基本思想：

 1、校验位和数据位

       (1) 、凡编号为2的乘幂的位是校验位，如1、2、 4、8、16、……

        (2)、其余是数据位，如3、5、6、7、9、……

 2、每一个校验位设置根据：包括自己在内的一些位的集合的奇偶值(奇数或偶数)。

例子：

 问：如何找到每个数据位的校验位 ？

方法：将某一位数据位的编号展开成2的乘幂的和，那么每一项所对应的位即为该数据位的校验位(收方使用)。

数据位编号：1=2^0=1   1号数据位的校验位包括：1

数据位编号：2=2^1=2    2号数据位的校验位包括：2

数据位编号：11 = 2^0 + 2^1 + 2^3 = 1 + 2 + 8                    11号数据位的校验位包括：1，2，8

数据位编号：29 =  2^0 + 2^2 + 2^3 + 2^4 = 1 + 4 + 8 + 16  29号数据位的校验位包括：1，4，8，16

校验位1的检验集合为所有奇数位，1，3，5，7，9，11...

校验位2的检验集合：2、3、6、7、10、11、…

校验位4的检验集合：4、5、6、7、...

校验位8的检验集合：8、9、10、11、…

海明码纠错过程:

1、首先将差错计数器置“0”，counter=0。

2、当海明码数据到达接收端后，接收端逐个检查各个校验位的奇偶性。

3、如发现某一校验位和它所检测的集合的奇偶性不正确，就将该检验位的编号加到差错计数器中。

问：海明码如何纠正突发错误？

1、将连续的k个码字按行排列成矩阵 

2、发送数据时，按列发送，每列k位

3、如果一个突发性错误长度是k位，则在k个码字中，至多只有 一位受到影响，正好可用海明码纠错改位后恢复。

例子：使用奇校验，一个校验集合里的1的个数是奇数

接收到码字为00111000100，校验各校验位：

      第一位：00111000100，校验集合有3个1，

                    0+1+1+0+1+0=3，错。

     校验位1的检验集合为所有奇数位，即：1，3，5，7 , 9 , 11 ，13，15...

      第二位：00111000100，校验集合有1个1，

                   0+1+0+0+0+0=1，错。

     校验位2的检验集合：2、3、6、7、10、11、…

      第四位：00111000100，校验集合有2个1，

                    1+1+0+0=1，对

     校验位4的检验集合：4、5、6、7、12，...

      第八位：00111000100，校验集合有1个1，

                     0+1+0+0=1，错

     校验位8的检验集合：8、9、10、11、…

     累加出错位编号：1+2+8=11 

     可计算得其第11位出错，将该位由0改为1，即纠正得到正确 结果: 00111000101。

三、流量控制

为什么要进行流量控制？

发送者发送数据的能力高于接收者的接收能力，可能导致数据未接收就丢失了。

如何解决流量控制问题，有两个方法：

       1. 基于反馈的流量控制。

       2. 基于速率的流量控制。

四、基本的数据链路层协议

1、无限制的单工协议

使用该协议的两个前提，假设：

假设1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失（差错问题）。

假设2：不管发送方以多快的速率发送数据，收方总是来得及收下,并及时上交主机（流量问题）。

两个假设使数据链路层变成理想的信道，不用处理差错问题和流量问题。此时发方和接收方：

发送方：循环从网络层获得packet(数据包)，封装成frame(帧)之后发送出去。

 接收方：循环从物理层获得frame，取出packet交给网络层。

2、单工停等协议

使用该协议的一个前提，假设：

假设1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失（差错问题）。

该假设使数据链路层不会存在差错问题，但会存在流量不匹配问题。此时发方和接收方要针对该问题做出处理：让接收方提供反馈信息给发送方

发方：每发一帧，停止下来。

收方：每收到一帧，上交网络层，再发一个确认给发方，表示收到。

发方：收到确认，再发下一帧。

3、带噪声的单工协议

无前提假设，数据链路层在传输上可能存在数据出差错、丢失问题和发送方和接受方流量不匹配问题，此时发方和接收方要针对问题做出处理：

处理数据出差错、丢失问题同时进行流量控制的方法：差错控制编码与否认帧(nak)

1、通过CRC，如接收方检测有错，则发NAK（否则ACK）。

2、发送方收到NAK，则重发，直到收到接收方发来的ACK为止。

3、若发送方多次收到NAK，则向上提示出错。

重复帧处理方法：对帧进行编号

1、目的:让接收端能够区分一个帧到底是新帧还是已经处理过的旧帧。

2、对于stop-and-wait协议：一次只发送一个帧，序号只需要1位(0,1)，用于标记当前帧和它的下一个帧。

3、确认帧也要编号。

五、滑动窗口协议

基本思想：

1、发送端:一次连续发送未经确认的的帧是受到发送窗口(sending window)控制的，只有落到发送窗口的帧才是可以发送的。

2、接收端:只有落到接收窗口(receiving window)的帧才是可以接收的。

1、捎带技术

特点：双向通信。

帧通信类别：

A-B数据帧 ,B-A的确认帧

B-A数据帧 ,A-B的确认帧

实现思想：

      一方收到另外一方发来的数据帧之后,不立即回发确认帧给对方,而是等本站有数据要发送给对方时,将给对方确认信息和本站发向对方的数据混合成一个帧传送给对方。

总结：

将A-B的数据帧, A-B的确认帧,混合在一起。

将B-A的数据帧, B-A的确认帧,混合在一起。

存在问题：若一个站点在收到对方的数据帧之后没有数据发送给对方，源站就收不到确认帧，导致超时。

解决办法：设置辅助计时器,在目标端收到数据时,启动辅助计时器,如果在辅助计时器到时,仍然没有反向数据传送,则单独发送确认短帧。

捎带技术优点：

1、较好地利用信道的带宽

2、减少目标端的中断次数。

3、减少单独发送确认帧带来的效率上的降低。

2、发送窗口

窗口最大值的定义：一次可以连续发送而未经对方确认的帧的个数的最大值。

发送缓冲区的个数相当于发送窗口的最大帧的个数(固定值)，发送缓冲区中的帧有两类：

（1）未发送的而落入发送缓冲区的帧，可以连续发送出去；

（2）已经发送出去的等待对方确认的帧,发送缓冲区的帧只有得到确认才能删除，窗口向前移动，设置发送缓冲区的目的是使出错的帧可以重发

发送窗口中的序列号代表：在发送缓冲区中已经发送了但未确认的帧；

只有收到对方的ack，发送窗口和发送缓冲区后沿向前移动，有更新的帧可以落到发送缓冲区中Ws=1停等协议, Ws非常大:连续ARQ协议.

3、接收窗口

接收窗口用于控制，哪些帧可以接收，哪些不可以；

只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下接收窗口向前移动一个，并发一个确认给对方；

若接收到的数据帧落入接收窗口之外，则一律将其丢弃； 

接收窗口Wr=1，则接收端只能顺序接收；否则可以不按顺序接收，但提交给网络层的分组，一定要按照顺序

引入活动窗口协议的目的：使发送和接收两端的窗口按照一定的规律不断向前滑动，正确发送和接收数据。

协议基本思想：

接收窗口向前移动时，发送窗口才能向前移动。

接收窗口的大小是固定的,而发送窗口的大小是变化的。

发送缓冲区的大小是固定的。

4、协议——一比特滑动窗口协议（配合捎带技术使用）

窗口大小：N = 1，发送序号和接收序号的取值范围：0，1；

可进行数据双向传输，信息帧中可含有确认信息（捎带技术）；

信息帧中包括两个序号域：发送序号和接收序号（接受端已经正确收到的帧的序号）。

5、协议——回退n帧协议

基本思想：不是一次发送一个帧,而是一次可以连续发送若干个帧，面对出错时，丢弃,不发确认,让发送方超时重发。

同时对于后续到达的帧分两种情况接收：

1、当Wr＝1时：

      接收方：全部丢弃（drop）, 链路层只按顺序接收帧

      发送方：2号帧超时后,从2号帧开始发送

回退n帧 ( go back n protocol )

2、当Wr>1时：

       接收方:  陆续接收出错帧的后续各帧,但不提交给网络层,直到收                                     

                 到2号帧之后,加上以后存储的各帧,按顺序交给网络层

       发送方： 2号帧超时后,发完2号帧之后,从第6号帧开始

   选择性重传 ( selective repeat )

注：限制最大窗口值w<＝2n-1

总结：