《计算机网络教程》（谢希仁著）PPT电子课件教案-第4章数据链路层.ppt

第四章 数据链路层,本章将介绍： 数据链路层的基本概念； 两个重要的数据链路层流量控制方法：停止等待协议和连续arq协议； 差错控制方法：循环冗余校验； 连续arq协议的实现机制：滑动窗口机制； 数据链路层的具体协议：bsc、hdlc、ppp,4.1数据链路层的基本概念,区分“链路”和“数据链路”的概念。 链路是一条无源的点到点的物理线路段，中间没有任何其他交换结节，又称物理链路。 数据链路是除了有一条物理线路外，还施加了一些必要的通信协议来控制数据的传输。又称逻辑链路。,数据链路层的作用： 在数据链路层协议的控制下，在不太可靠的物理链路上实现相邻结点之间的可靠传输。,时期链路层的主要功能:,1、链路管理 当网络中的两个相邻结点要进行通信时，发送方必须知道接收方是否已经准备就绪。为此，通信双方必须先要交换一些必要的信息，建立一条数据链路，在传输数据时要维持数据链路，传完后要释放数据链路。,帧同步 在数据链路层，数据的传送单位是帧，数据一帧一帧地传送，帧同步是指接收方应当能从接收到的比特流中区分出一帧的开始和结束，不至错位。通过在帧的开始和结束处加帧标志来实现。,3、流量控制 发送方发送数据的速率必须使接收方来得及接收。因此必须控制发送方的速率。,4、差错控制 差错控制广泛采用了编码技术，通过在帧中添加一定的校验位（冗余位）来实现。编码技术有两大类： (1)前向纠错，接收方收到出错的帧后，能自动将其改正过来，但这种方法开销大，编码复杂，在计算机通信中很少采用。如海明码. (2)差错检测，一般是接收方检测到出错的帧后，将其丢弃，然后通知发送方重发。如循环冗余码.,5、将数据和控制信息区分开 数据和控制信息封装在同一帧中，要有一定的措施使接收方能够区分开来。可通过规定帧的格式来实现。,6、透明传输 透明传输指不管所传数据是什么样的比特组合，都能实现正确传输。如当所传数据中出现“帧标志”比特组合时，不能将其误认为是帧标志，而要当成数据，为此，必须采取一定的控制措施。,7、寻址 帧中必须封装有接收方的物理地址（mac地址）。,4.2停止等待协议,停止等待协议是最简单但也是最基本的数据链路层协议。,4.2.1 不需要数据链路层协议的数据传输 两台计算机通过一条数据链路进行通信的简化模型如下：,当同时满足以下两个条件时，不需要数据链路层协议： (1)链路是理想的传输信道，不会出错。 (2)不管发送方以多快的速率发送，接收方都来得及收下，并及时上交主机。 当接收方缓存的容量无限大且发送方的速率永远低于接收方的接收速率时才可能。,4.2.2 具有最简单流量控制的数据链路层协议 保留上述的第一个假设，去掉第二个假设。 为了使接收方的缓存在任何情况下都不会溢出，最简单的方法是发送方每发送一帧就暂停，接收方收到并处理完后通知发送方，发送方才发下一帧。 这种由接收方控制发送方的发送速率是计算机网络中流量控制的基本方法。,具有最简单流量控制的数据链路层协议算法如下： 发送方： (1)从主机取一个数据帧； (2)将数据帧送到数据链路层的发送缓存； (3)将发送缓存中的数据帧发送出去； (4)等待； (5)若收到接收方发来的通知，则从主机取一个新的数据帧，然后转到（2）。,接收方： (1)等待； (2)若收到发送方发来的数据帧，将其送入数据链层的接收缓存； (3)将接收缓存中的数据帧上交主机； (4)向发送结点发送通知，表示已上交主机； (5) 转到（1）。 两种数据传输情况对比图见书p73 图4-2,4.2.3实用的停止等待协议 现在去掉前面的两个假定，讨论实用的数据链路层协议。设主机a 主机b，分以下几种情况讨论： (1)b正确收到，向a发送一个确认帧ack； (2)b检测出帧在传输过程中出错，向a发送一个否认帧nak，通知a重传出错的帧。 (3)a发送的数据帧在传输过程中丢失，或b发送的确帧在传输过程中丢失。会出现什么情况？,方法是给每一帧编号，编号应既能识别出重复帧，又要尽可能短。如何编号最好？ 编号占用一个比特位，0和1交替编号即可，为什么？,发送方“死等”。 解决方法是：a每发送一个数据帧，就启动一个超时计时器，在规定的时间内未收到b的任何应答，应重传该帧，重传时间不能设置过短或过长。 (4) 如果是b发送的确认帧在传输过程中丢失，则超时重传会使b收到两个同样的数据帧，此时应丢弃，但主机b如何识别出一个数据帧是否为重复帧？,4.2.4循环冗余检验（crc） 用来检测帧在传输过程中有没有出错。 crc的工作方法： 在发送端产生一个循环冗余码，附加在信息位后面一起发送到接收端，接收端收到的信息按发送端形成循环冗余码同样的算法进行校验，若有错，需重发。,crc将数据块看成是一个多项式系数系列。 如数据块:110011 对应的多项式:m(x)=x5+x4+x+1 双方约定一个生成多项式，如p(x)=x4+x3+1，其系数系列为：11001 利用两个多项式相除，余数作为校验位，除法过程中所有的减法按模二算法（即异或运算）。,例：数据块m(x)为1010001101 ， 生成多项式p(x)=x5+x4+x2+1，即110101， 求crc,crc的计算过程如下： (1)设约定多项式p(x)为n阶，在数据块m(x)的未尾添加n个0，得到xn m(x)。 (2)用xn m(x)/ p(x)，得到余数r(x)。 (3)用xn m(x)+ r(x)，得crc码。,1 1 0 1 0 1 0 1 1 0q商 110101) 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0xnm 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 r余数 crc码为1 0 1 0 0 0 1 1 0 1 0 1 1 1 0,接收方的处理过程： 接收方用收到的信息，除以生成多项式，若除数为0，则传输中没有出错，否则，出错。 现在国际上有一些标准的约定生成多项式。,停止等待协议的算法如下： 发送方： (1)从主机取一个数据帧； (2)v(s) 0； 发送状态变量初始化 (3)n(s) v(s); 将发送状态变量的数值写入发送序号并 将数据帧送交发送缓存； (4)将发送缓存中的数据帧发送出去； (5)设置超时计时器 (6)等待以下三个事件中最先出现的一个； (7)若收到确认帧ack，则： 从主机取一个新的数据帧； v(s) 1- v(s)；更新发送状态变量，变为下一个序号 转到（3），发送下一帧。 (8)若收到否认帧nck，则转到（4），重传数据帧。 (9)若超时计时器时间到，则转到（4），重传数据帧。,接收方： (1)v(r) 0;接收状态变量初始化，为欲接收的序号 (2)等待； (3)当收到一个数据帧，检查有无传输差错(如用crc)， 若检查正确，则执行后续算法，否则转到(8)。 (4)若n(s)=v(r)，则执行后续算法；(序号正确) 否则丢弃此数据帧，然后转到(7) 为重复帧，发ack (5)将接收缓存中数据帧的数据部分上交主机； (6) v(r) 1- v(r),更新状态变量，准备接收下一帧 (7)发送确认帧，并转到(2)； (8)发送否认帧，并转到(2) 。,tp为传播时延，tf为发送时间，tpr为处理时间，ta为ack的发送时间， tout为重传时间。 当tpr和ta都远小于tp时， tout =2tp 停止等待协议arq的优点是简单，但效率低。,tt,tf,tout,tp,tpr,ta,tp,tpr,4.2.6停止等待协议中几个重要的时间关系,4.3.1连续arq的工作原理 连续arq不是每发一帧就停下来等待确认，而是可以连续发送若干个帧后，才等待确认。 在连续发送的若干个帧中，如果某一帧出错，则其后发送的帧全部丢弃，从出错帧开始重发。,4.3连续arq协议,4.3.2滑动窗口的概念 连续arq中连续发送帧的数量不能太大，因为： (1)出错是重传的帧数较多。 (2)给帧进行编号时，序号要占较多的比特位，增大了开销。 如何控制发送方的发送和接收方的接收？,发送窗口(wt)：在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。用来对发送端进行流量控制。停止等待协议中发送窗口的大小为1。 设发送序号用3个比特来编码，即发送序号可以从0-7，又假定发送窗口wt=5，发送窗口的规则如下： (1)发送窗口内是允许发送的帧，而不考虑有没有收到确认。右侧是不允许发送的帧。,wt,允许发送5个帧,不允许发送的帧,(2)每发送完一帧，允许发送的帧数就减1，但发送窗口的位置不变。如已发送了0号帧。,wt,还允许 发送4个帧,不允许发送的帧,已发送,(3)如果允许发送的5个帧都发送完了，但还没有收到任何确认，就不能再发送了，进入等待状态。,wt,已发送,不允许发送的帧,(4)每收到对一个帧的确认，发送窗口就向前滑动一个位置，如发送方已收到0、1和2号帧的确认。,wt,已发送并已收到确认,不允许发送的帧,已 发送,还允许发送3帧,为了减少开销，接收端可以在连续收到好几个帧后，才对最后一个数据帧发确认信息，或自己有数据要发送时才对以前收到的数据帧加以捎带确认。 对某一数据帧的确认表示该帧及以前所有的数据帧均已正确收到。如上例中接收端可以只发对2号帧的确认，表示2号及0、1号均已正确收到。减少开销。,接收窗口(wr)：接收端允许接收的帧的序号。wr=1，接收窗口的规则如下： (1)只有当收到的数据帧的发送序号落在接收窗口内才允许接收，否则，丢弃。 (2)每收到一个序号正确的帧，接收窗口就向前滑动一个帧的位置。同时可以向发送端发送对该帧的确认。,wr,准备接收0号帧,不允许接收这些帧,wr,准备接收1号帧,不允许接收这些帧,已收到,发送窗口的最大值：当采用3个比特来编号时，可以编出8个不同的序号，发送窗口的最大值是不应为8？,不能为8！,如果发送窗口wt=8，设发送方已发送完0-7号共8个帧。因发送窗口已满，发送暂停，等待确认。 假定这8个帧已正确到达接收端，并且接收端已对这8帧发回确认帧。下面考虑两种不同情况： 第一种情况是：确认帧正确到达了接收端，发送方又发送0-7号共8个新帧。 第二种情况是：确认帧丢失，接收端超时后重传这先前发送的8个旧帧。 接收端第二次收到编号为0-7的8个帧时，无法判定是8个新帧，还是重传的8个旧帧。因为它不知道上次的确认帧是不已丢失。,当用n个比特编号时， wt 2n-1,4.3.3信道利用率与最佳帧长,信道的利用率指扣除控制信息后的数据率与信道容量之比。还受出错重传影响，不可能达到100%，当信道不出错时，其值为数据位/帧长。 最佳帧长 （1）当帧长取得很短时，控制信息所占的比重增大，开销增大，信道利用率降低。 （2）当帧长取得很长时，帧在传输过程中出错的概率增大，重传次数增大，也会使信道利用率降低。 数据帧长的选择与信道的好坏有很大的关系。 当信道质量好时，帧长应该长还是短？ 当信道质量不好时，帧长应该长还是短？,4.4选择重传arq协议,为进一步提高信道利用率，可只重传出错帧或超时帧。必须做到： （1）加大接收窗口，以便先收下发送序号不连续但仍处在接收窗口中的帧。 （2）接收端要设置相当容量的缓存空间，这样不够经济。所以目前应用较少，但目前随着存储器价格的下降，受到更多的重视。 接收窗口的最大值受下式约束： wr 2n/2 因wt +wr 2n,4.5面向比特的链路控制规程hdlc,4.5.1hdlc概述 数据链路控制规程分两大类： （1）面向字符的数据链路控制规程 典型代表有ibm的bsc二进制同步通信规程。 特点：所传数据及控制信息都必须是规定字符集（如ascii码）中的字符,且控制字符很多。 采用停止等待协议，效率低。 （2）面向比特的数据链路控制规程 典型代表有iso的hdlc高级数据链路控制规程。 特点： 所传数据可以是任意的比特流。 采用连续arq，效率高。,ccitt将hdlc修改后称为链路接入规程lap，并作为x.25的数据链路层协议，不久后又将lap改为lapb平衡型链路接入规程。 hdlc可适用于链路的两种基本配置，即平衡配置与非平衡配置。 非平衡配置的特点是站有主站和从站之分，由一个主站控制整个链路的工作，只有主站才能发起向次站的数据传输，而次站只有在主站对它进行轮询时，才能以响应帧的形式回答主站。 平衡配置的特点是站是复合站，同时具有主站和从站的功能，能平等地发起数据传输。,4.5.2 hdlc的帧结构,hdlc的帧结构,比特：8 8 8 可变 16 8,检验区间,透明传输区间,1、各字段的意义,1、标志位f 作用：用来标识帧的开头和结尾。 标志位f为：01111110 透明性处理： 当两个标志位之间碰巧出现了和标志位f一样的比特组合时，接收方会误认为帧结束了。 为了避免出现这种错误，hdlc采用零比特填充法。 发送方在数据连续5个1之后自动插入一个0，这样数据中就不会出现6个连续1。 接收方在数据连续5个1之后自动去0。,例如： 要发送的数据为： 01001111110001010 实际发送的数据为： 010011111010001010 接收方去0： 01001111110001010 采用零比特填充法就可传送任意的比特流。 2、地址字段a 在平衡方式时，填入接收方的地址。全1为广播方式，全0为无效地址，因此，有效地址为254个。 当用户数很多时，可用地址字段的第一个比特表示扩展比特，当该位为1时，表示后面还有地址字段，当为0时，表示这已是最后一个地址字段了。,3、帧检验序列fcs 为crc的校验码。 4、控制字段c 长8位，根据前两位的取值，将hdlc帧分为三大类：信息帧i、监督帧s和无编号帧u。 控制字段的结构如下：,2、信息帧 第一位为0，表示该帧为信息帧。 第24位n(s)为当前发送的信息帧的序号 第68位n(r)为接收序号，即接收方期望收到的帧的序号。 n(r) 带有确认的意思，它表示序号为n(r)-1(mod 8)的帧以及在这之前的各帧都已正确收到。如n(r) 为4，意思是？ 通信的每一方都有一个n(s)和n(r)。,在全双工通信中，收发双方还设置了两个状态变量v(s)和v(r)，由这两个状态变量的值确定发送序号n(s)和接收序号n(r) 的值。 每从主机取一帧新的数据就要将v(s)和v(r) 的值分别写入帧的控制字段n(s)和n(r) 中。 每发完一帧v(s)+1(mod 8)。 当出错重传时，只需从缓存队列中取出已发送过的旧帧，重新发送，帧中的序号n(s)仍为原序号； v(s)不变； 每收到一个无差错的信息帧v(r)+1(mod 8)。 当出错重传时， n(r) 必须与v (r)的当前值一致。,信息帧中设置n(r) 的目的是不必专门为收到的信息帧发送确认帧，可以在本站有信息发送时，将确认信息捎带走。提高信道利用率。 控制字段的第5个比特是探询/终止比特，即p/f。主站发出的命令帧中若将p置为1表示要求对方立即响应。在平衡链路中若将f置1，表示数据发送完毕。 3、监督帧s 第12比特为10。监督帧共有四种，取决于34比特的值。,监督帧不包含数据，不需要发送序号n(s)。 rr和rnr还具有流量控制作用。 4、无编号帧u 第12比特为11，无编号帧不带v(s)和v(r)字段,而用5位，即3、4、6、7、8来表示不同功能的无编号帧，无编号帧主要起控制作用。如要与对方建立