计算机网络考研辅导讲座数据链路层上

1、第三讲 数据链路层(上)1第三讲：数据链路层(上)2011年考研大纲考查范围:2大纲考查范围（续） 1. 网桥的概念和基本原理 2. 局域网交换机及其工作原理3知识点归纳 数据链路/逻辑链路 = (物理)链路 + 通信规程（一）数据链路层的功能 1）作用： 将网络层交下来的数据报组装成幀，在两个相邻结点间的链路上传送以幀为单位的数据。接收端进行差错检测，若有错，则丢弃差错幀。然后或者通知对方重传、或者不处理交由上层解决。 2）目的： 在相邻结点间提供透明、无错的数据传输。 3）功能： 组幀(同步、定界、透明传输)、差错控制、重传策略、流量控制、寻址、链路管理等。4知识点归纳5（二） 组帧 把数

2、据封装成帧关键问题：让接收者能够从接收的位流中区分出帧的边界(幀同步)，即帧的开 始和结束。幀同步方法： (1) 字节计数法: 每帧以帧同步标志字节开始，后面紧跟幀长计数 接收方收到幀，知道幀的长度，每接收一个数据字节，计数减1， 直到为0，便是幀尾，幀后跟校验信息。 知识点归纳 (2) 使用字符填充的首尾定界符法 （ 如BSC 协议） 面向字符通信协议，以特定ASCII字符序列表帧首、帧尾及控制字段。 帧头两个同步字符SYN SYN之后，数据字段以DLE STX 开始，DLE ETX 结束，中间数据用“DLE插入删除技术”来实现字符的透明传输。SYNSYNDLESTX透明数据ETX校验DLE

3、6知识点归纳 (3) 使用比特填充的首尾标志法（ 如HDLC 协议） 以特殊的比特组合（如 01111110 同步 序列）标志帧的开始和结束 面向位的通信协议，用“0”比特插入删除技术”来实现字符的透明传输。 例： 插入后： 011011111011000111110010 恢复： (4) 编码违例法 采用违反编码规律的策略标志帧边界。优点：无须另外透明传输方法 如差分Manchester编码中每一位中间不是 便是 。 而 、 则是违法编码，用其在令牌环网的帧中标志帧头、帧 尾，接收方易识别，帧中数据字段也不需另外设计透明传输法。透明数据7知识点归纳（三） 差错控制 检错码(码字只有检错的功能

4、，接收方只能判断数据块有错，但不能确切知道错 误的位置，从而也不能纠正错误)，如奇偶校验码、校验和码、CRC码。 纠错码(码字具有一定的纠错功能，接收方不仅能检出错，还知道错在什么地方, 这时只需将数据位取反即能获得正确的数据)，如海明码。 检错码举例： 奇偶校验码：例 异步数据通信时的偶校验，1(凑成偶数个1)。 校验和码： 例1 路由器中网络层实体对IP信包头做的校验和：IP 数据报首部计算过程 ：8知识点归纳例2传输层实体中对整个UDP数据包(或TCP报文)做的校验和，以UDP为例：10011 153.1900001 8.10410101 171.300001110 00001011 1

5、4.1100000 0 和 1700000 1500000100 00111111 108700000 1300000 1500000 0（检验和初值）01010100 01000101 数据01010 数据01001 数据01000111 00000000 数据和 0（填充）10010110 11101011 求和得出的结果01101 检验和填入 153.19.8.104171.3.14.1112 字节伪首部8 字节UDP 首部 7 字节数据字段填充按二进制反码运算求和将得出的结果求反码： 全 0 17 15 1087 13 15 校验和初值置全 0 数据 数据 数据 数据 数据 数据 数据

6、 全 09知识点归纳循环冗余校验码(CRC): 例以太帧、无线帧、PPP帧尾的4字节CRC校验码。 它们做CRC除法运算时用的生成多项式除数CRC-32为： CRC-32 = x32+x26+x23+x22+x16+x12+ x11+x10+x8+x7+ x5+ x4+ x2+x+1 在发送方做CRC除法运算，计算所得的余数为CRC校验码，它跟在数据后面一起传输到接收方，接收方同样做CRC除法运算，若余数为0，则校验正确。 若帧数据为100100，以4位生成多项式 x3+ x2+1 即位串 1101 为例：10知识点归纳 纠错码举例*： 海明码：例 单工通信时插入数据中的海明码(注意红字P1,

7、 P2, P4, P8)。 解 设A的 ASCII 码为1000001, 由于海明码为 P1P2D3P4D5D6D7P8D9D10D11的形式， 即此处 D3 D5D6D7 D9 D10 D11 = , P1, P2, P4, P8为插入的海明码， 则由式子 P1 = D3+D5+D7+D9+D11，P2 = D3+D6+D7+D10+D11， P4 = D5+D6+D7， P8 = D9+D10+D11 可计算得：P1=0，P2=0，P4=0，P8=1 发送端形成的海明码为 00100001001 若接收方接收错误，收到：00100001011 (D10错误) 则检/纠错过程如下：计算校正因

8、子S1、S2、S4、S8，方法如下： 由式子 S1 = P1+D3+D5+D7+D9+D11 S2 = P2+D3+D6+D7+D10+D11 S4 = P4+D5+D6+D7 S8 = P8+D9+D10+D11 若计算出的 S1 S2 S4 S8 0， 则无错； 若 S1 S8 不全为 0, 则有错，错误位置在 S S8 S4 S2 S1 处， 由上法计算得： S1=0，S2=1，S4=0，S8=1 S2= S8= 1 检测有错， 错误位置在 S1010 处，即D10处，因此将D10取反即可，纠错完毕* - 选学，参考 11知识点归纳差错控制：前向纠错法（FEC）、反馈差错控制法(自动重发

9、请求ARQ) 前向纠错法(FEC)： 自动纠错，发送端使用纠错码，接收端检出并纠正错，但监督码比较复杂、效率低，一般用于没有反馈信道的单工通信中。 自动重发请求(ARQ)： 使发送方确认接收方是否正确收到了由它发送的数据信息。发送方发送数据帧时附加一定的冗余检错码一并发送，接收方则根据检错码对数据帧进行差错检测，若发现错误，就返回请求重发的应答，发送方收到请求重发的应答后，便重新传送该数据帧。这种差错控制方法就称为自动重发请求法(Automatic Repeat reQuest)，简称ARQ法。12知识点归纳 其中，ARQ法有几种实现方案，停等法和连续ARQ是最基本的两种方案。 停等法(Sto

10、p and Wait) ： 该方案规定发送方每发送一帧后就要停下来等待接收方的确认返回，仅当接收方确认正确接收后再继续发送下一帧 。停等法方案的实现过程如下： 发送方每次仅将当前信息帧作为待确认帧保留在缓冲存储器中； 当发送方开始发送信息帧时，随即启动计时器； 当接收方收到无差错信息帧后，即向发送方返回一个确认帧； 当接收方检测到一个含有差错的信息帧时，便舍弃该帧； 若发送方在规定时间内收到确认帧，即将计时器清零，继而开始下一帧的发送； 若发送方在规定时间内未收到确认帧，即计时器超时，则应重发存于缓冲器中的待确认信息帧。 从以上过程可以看出，停等法方案的收、发送方仅需设置一个帧的缓冲存储空间，

11、便可有效地实现数据重发并确保接收方接收的数据不会重份。停等法方案最主要的优点就是所需的缓冲存储空间最小，因此在链路端使用简单终端的环境中被广泛采用。为防止重复帧造成问题，帧编号0、1循环使用。13知识点归纳 连续ARQ法： 连续ARQ方案是指发送方可以连续发送一系列信息帧，即不用等前一帧被确认便可发送下一帧。这就需要在发送方设置一个较大的缓冲存储空间 ( 称作重发表 )，用以存放若干待确认的信息帧。当发送方得到对某信息帧的确认帧后便可从重发表中将该信息帧删除。所以，连续ARQ方案的链路传输效率大大提高，但相应地需要更大的缓冲存储空间。连续ARQ方案的实现过程如下： 发送方连续发送信息帧而不必等

12、待确认帧返回，每发一帧启动一个计时器； 发送方在重发表中保存所发送的每个帧的备份，重发表按先进先出(FIFO)队列规则操作； 接收方对每一个正确收到的信息帧返回一个确认帧（可以累积确认）；每一个确认帧包含对某一个信息帧的确认序号，随相应的确认帧返回； 当发送方收到相应信息帧的确认后，将相应的计时器清零，从重发表中删除该信息帧的备份； 若发送方在规定时间内未收到确认帧，即发送该帧时对应的计时器超时，便重发该未被确认的信息帧。 整个过程中，发送方某个时刻管理超时控制的计时器数目应等于缓冲器中当时已发但未获确认的帧数目。14 上面连续ARQ过程中如果出现传输差错，如何进一步处理还可以有两种策略，即出

13、错全部重发（ GO-BACK-N，GBN）策略和选择重发（ SELECT REPEAT ，SR）策略。 GO-BACK-N（GBN）即出错全部重发策略的基本原理是，当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了N个帧后，若发现该N帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就不得不重新发送出错帧及其后的N帧。这就是GO-BACK-N(退回N)法名称的由来。因为，对接收方来说，由于这一帧出错，就不能以正常的序号向它的高层递交数据，对其后发送来的N帧也都不能接收因而丢弃它们。GO-BACK-N可能将

14、已正确传送到目的方的帧再重传一遍，这显然是一种浪费。 SELECT REPEAT (SR) 即选择重发策略的基本原理：另一种效率更高的策略是当接收方发现某帧出错后，其后继续送来的正确的帧虽然不能立即递交给接收方的高层，但接收方仍可收下来，存放在一个缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后，就可以与原已存于缓冲区中的其余帧一起按正确的顺序递交高层。知识点归纳15（四） 流量控制与可靠传输机制 掌握流量控制、可靠传输（差错控制+重传机制）与滑动窗口机制的基本原理和方法，重点解析单帧滑动窗口即停止-等待协议，多帧滑动窗口与后退N帧协议（GBN），多帧滑动窗口与选择重传协议

15、（SR），并进行实例化描述。 流量控制涉及链路上字符或帧的发送速率的控制, 以使接收方在接收前有足够的缓冲存储空间来接收每一个字符或帧。例如，在面向字符的“计算机终端”链路中，若远程计算机为许多台终端服务，它就有可能因不能在高峰时按预定速率传输全部字符而暂时过载。同样，在面向帧的自动重发请求系统中，当待确认帧数量增加时，有可能超出缓冲器存储空间，也会造成过载。有两种常用的流量控制方案：XON/XOFF方案和滑动窗口机制。 XON/XOFF方案（如“计算机终端”链路的异步数据通信软件中） XON/XOFF方案中使用一对控制字符来实现流量控制，其中XON采用ASCII字符集中的控制字符DC1(AS

16、CII码11H)，XOFF 采用ASCII字符集中的控制字符DC3(ASCII码13H)。当通信线路上的接收方发生过载时，便向发送方发送一个XOFF字符（类似交通灯“红灯”的作用） ，发送方接收XOFF字符后便暂停发送数据；等接收方处理完缓冲器中的数据、过载恢复后，再向发送方发送一个XON字符（类似交通灯“绿灯”的作用） ，以通知发送方恢复数据发送。在一次数据传输过程中，XOFF、XON的周期可重复多次，但这些操作对用户来说是透明的。知识点归纳16知识点归纳 滑动窗口机制（如网络的发送、接收软件中） 为了提高信道的有效利用率，如前所述采用了不等待确认帧返回就连续发送若干帧的方案。由于允许连续发

17、送多个未被确认的帧 ，帧号就需采用多位二进制数才能区分（一般只取有限位二进制数，到一定时间后就又反复循环，如帧号配3位二进制数，则帧号在07间循环）。由于凡被发出去而尚未被确认的帧都可能出错或丢失而要求重发，这些帧在发送方都要暂时保留，这就要求发送方有较大的发送缓冲区保留这些帧，并把这些可能要重发的帧号存在待重发表中。 接收缓冲区容量也是有限的，如果接收方不能以发送方的发送速率处理接收到的帧，则可能用完缓冲容量而暂时过载。为此，要对发送方可发送的帧的数目加以限制，可以控制发送方的发送窗口和保留在重发表中的待确认帧的数目来解决：如果接收方来不及对新到的帧进行处理，便停发确认信息，此时发送方由于连

18、续发出多帧得不到确认，重发表就会增长，当由于连续发出多帧且得不到确认，导致发送窗口减为0、重发表增长到极限上限值时，发送方就不再能发送新帧，直至再次收到确认信息才行。 发送窗口就是发送端允许连续发送的幀的序号表，发送端可以不等待应答确认而连续发送的最大幀数称为发送窗口的尺寸。重发表是一个连续序号的列表，对应发送方已发送但尚未确认的那些帧。显然，如果发送窗口设置为1，即发送方缓冲能力仅为一个帧，则传输控制方案就回到了停等法方案，此时传输效率很低。故窗口限度应选为使接收方尽量能处理或接受收到的所有帧。当然选择时还必须考虑诸如帧的最大长度、可使用的缓冲存空间以及传输速率等因素。 接收方类似地也有接收

19、窗口，它指示接收方允许接收的幀的序号表，凡落在接收窗口内的幀，接收方都必须处理，落在接收窗口外的幀将被丢弃。接收方每次允许接收的幀数称为接收窗口的尺寸。 17知识点归纳 发送方初始化后，发送窗口等于发送窗口最大尺寸，重发表中待确认帧的数目等于0。每次发送一帧后，发送窗口便减1，同时重发表待确认帧的数目增1，每收到对一个帧的确认信息后，重发表待确认帧的数目便减1，由于得到确认而释放了一个帧的发送缓冲，于是发送窗口便增1。当这样的传送过程进行时，打开的窗口位置一直在滑动，称为滑动窗口(Slidding Window)。当发送方连续发出多帧得不到确认、发送窗口减为0、重发表中待确认帧的数目等于发送窗

20、口最大尺寸时，便停止发送新的帧。 接收方初始化后，接收窗口等于接收窗口最大尺寸。每次收到一帧后，便会占用一帧的接收缓冲容量，接收窗口减1。当接收缓冲里的一帧校验正确、取出交给高层软件并向发送方发出对该帧的确认帧后，便会释放该帧占用的接收缓冲容量，接收窗口便增1。当这样的接收过程进行时，接收窗口位置也一直在滑动。 一般来说，凡是在接收窗口范围内到达的帧，即使它们不按顺序，接收方也应接收下来，此时，接收窗口大于1。而Go-back-N正是接收窗口等于1的一个特例，因为接收方对收到出错帧后收到的后续帧都不接收而丢弃。而选择重发SR发送窗口和接收窗口都大于1，因为接收方收到落在接收窗口范围内的帧时统统

21、接收而不管是否按序接收。停等法则发送窗口和接收窗口都等于1。停等法、Go-back-N及选择重发三种协议的差别仅在于各自窗口尺寸的大小不同而已，已经证明，三者对发送窗口、接收窗口的尺寸有一定的限制要求，如不满足便不能正常工作，它们是： 停等法：发送窗口=1，接收窗口=1； WT = WR = 1 Go-back-N： 发送窗口1，接收窗口=1; WR = 1, 须WT 2n1 选择重发：发送窗口1，接收窗口1； WT = WR时, 须WR 2n-1 如帧序号采用3位二进制编码(n=3)，对于GBN有序接收方式，发送窗口最大尺寸应为23-1=7 ；对于SR无序接收方式，接收窗口最大尺寸最多是23

22、-1=4。18知识点归纳 (停-等协议示例)流量控制： 控制发送方的发送数据量，使得不能超过接收方的接收能力。（接收方使用反馈机制，向发送方应答，报告自己当前的接收情况和能力。接收能力由接收设备的处理速度、接收缓冲的容量等影响）局域网中两种常用的流量控制策略： 停-等协议，滑动窗口协议停-等协议示例：frame 0ACK 1frame 1ACK 0frame 0frame 0ACK 1frame 1ACK 0frame 1ACK 0发送方接收方超时超时帧丢失 重发ACK丢失 重发19知识点归纳（滑动窗口示例1）0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7已成功发出的数据帧将发

23、出的数据帧窗口后沿窗口前沿帧序号发送方缓冲区0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7已正确接收的数据帧将收到的数据帧帧序号接收方缓冲区窗口后沿窗口前沿20知识点归纳（滑动窗口示例2）01234567S01234567R01234567发送0,1,201234567收到0,1,201234567发ACK,n=301234567收到ACK,n=301234567收3,4,发ACK,n=501234567发3,4,5发送窗口初始化为7接收窗口初始化为721知识点归纳（滑动窗口示例3）0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 0

24、 1 2 3 4 5 6 70 1 2 3 4 5 6 7 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 0 1 2 3 4 5 6 70,1,2 ACK33ACK4WT=7WR=74,5,6Whats next

25、?待重发表发送窗口滑动发送窗口接收窗口滑动释放接收窗口接收窗口初始化为 7发送窗口初始化为 7释放22知识点归纳（出错全部重发，Go-back-N ） 若发送方发出连续的若干幀后，收到对其中某一帧的否认帧，则从该帧及该幀开始的后续帧全部重发。 接收方只按序接收数据帧。虽然在有差错的帧之后接着又收到后续正确的数据帧，但都将其丢弃，因为不是所需的帧号。 优点：连续发送提高了信道利用率 缺点：导致某些对方已正确接收的帧也重传，因此降低了发送效率 出错全部重发时，若幀序号为n位， 接收窗口WR=1，须发送窗口 WT 2n1 误码率较低时，连续ARQ优于停等协议；反之则不一定。23WT2n-1时正常,

26、WT2n-1时出错发送窗口大小受限说明 ( 若接收方ack丢失时举例 )WT=2n1, WR=1 (n2)WT2n1 ,WR=124知识点归纳（出错选择重发，SR ） 若发送方发出连续的若干幀后，收到对其中某一帧的否认帧，只重传该出错幀或定时器超时的数据帧。 接收方的接收窗口 WR 1 ，会接收和暂存所有落在在接收窗口范围内的数据帧，即使帧序号在出错帧之后也收。 优点： 避免重传已正确传送的帧，提高了信道利用率。 缺点： 在接收端需要占用一定容量的缓存。 出错选择重发时，设幀序号为n位， WT = WR时, 须接收窗口的尺寸 WR 2n -125WR2n-1时正常, WR2n-1时出错 设n=

27、2，接收窗口WR =22-1 =2时，且发送窗口WT= WR = 2( 若接收方ack丢失时举例 )26知识点归纳（五）介质访问控制 动态分配(异步时分多路复用) 仅当有数据发时, 才占信道发数据随机访问 (争用) -负载较轻时控制访问-负载较重时轮转 (每个站轮流获 得发送机会)预约 (各站先声明有数据 要发送, 然后按预 约顺序发送)信道分配 策略 静态分配(将频带或时间片等 固定分给各站点) -站点少且固定， 数据量大时频分多路复用同步时分多路复用波分多路复用码分多路复用27知识点归纳 随机访问的介质访问控制。 主要有ALOHA随机争用协议 ( 纯ALOHA 和时隙ALOHA)、CSMA

28、协议（先听后说）以及非坚持型算法，1-坚持型算法和p-坚持型算法、CSMA/CD协议，以及CSMA/CA协议，重点要掌握CSMA/CD带有碰撞（冲突）检测的载波监听多路访问控制方法。ALOHACSMACSMA/CD 增加“发送前先监听，忙时则不发”改进改进1-坚持CSMA增加“一旦检测到冲突，立即停止发送”ALOHA、S-ALOHA1-坚持CSMA、非坚持CSMA、p-坚持CSMAEthernet28具有冲突检测的载波监听多路访问 CSMA/CD： 工作原理：某站点要发送数据帧前，先监听信道，若信道空闲, 则立即发送数据 帧，若信道忙，则坚持一直监听到信道空闲，然后立即发送数据帧， 发送数据帧

29、的同时，边发送边监听(在冲突检测窗口的2时间内，其 中2为最远的两个端点间一来一回传输的时间), 若在此期间监听到 冲突，立即停止发送，并发送Jam干扰信号串到网上通知全网站点以 强化冲突，使各冲突的站点马上停止发送，使信道很快空闲下来，然 后按截断的二进制指数退避算法延迟一段随机时间，再监听信道尝试 发送。 1-坚持CSMA, 再加上CD (冲突检测)。 冲突检测方法： （1） 比较接收到的信号电压的大小 或（2） 检测曼彻斯特编码的过零点 或（3） 比较接收到的信号与刚发出的信号 退避算法：为截断的二进制指数退避算法，来决定重发时延：从 0, 1, 2, ., 2k-1 中随机取一个数r，重发时延 = r (2)，其中 k = min 重发次数，10 知识点归纳（ CSMA/CD ）29知识点归纳(CSMA/CD工作流程)介质忙？载波监听冲突窗口内检 测到冲突？发送完？发送JamN16?YesNoNoYes 发送成功Yes 发送失败No 二进制指数退避， 延迟一随机时间NoYes发送帧 冲突次数N+30知识点归纳（ CSMA/CA ）802.11 CSMA 发送站： 如监听到信道空闲, 经DIFS/PIFS/SIFS 时间后则发送整个幀（发送时不用冲突检测） 如果监听到信道忙，则到不忙时，经DIFS/PIFS/SIFS 时间后