计算机网络-数据链路层.

课件制作人：谢希仁计算机网络第3章数据链路层课件制作人：谢希仁第3章数据链路层*3.1数据链路层的基本概念*3.2停止等待协议3.2.1完全理想化的数据传输3.2.2具有最简单流量控制的数据链路层协议3.2.3实用的停止等待协议3.2.4循环冗余检验的原理3.2.5停止等待协议的算法3.2.6停止等待协议的定量分析课件制作人：谢希仁第3章数据链路层（续）*3.3连续ARQ协议3.3.1连续ARQ协议的工作原理3.3.2连续ARQ协议的吞吐量3.3.3滑动窗口的概念3.3.4信道利用率与最佳帧长3.4选择重传ARQ协议课件制作人：谢希仁第3章数据链路层（续）*3.5面向比特的链路层协议HDLC3.5.1HDLC协议概述3.5.2HDLC的帧结构*3.6因特网的点对点协议PPP3.6.1PPP协议的工作原理3.6.2PPP协议的帧格式3.6.3PPP协议的工作状态课件制作人：谢希仁3.1数据链路层的基本概念链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。一条链路只是一条通路的一个组成部分。数据链路(datalink)除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。课件制作人：谢希仁数据链路层像个数字管道常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。结点结点帧帧课件制作人：谢希仁数据链路层的主要功能(1)链路管理(2)帧定界(3)流量控制(4)差错控制(5)将数据和控制信息区分开(6)透明传输(7)寻址课件制作人：谢希仁3.2停止等待协议先研究一下数据链路层的模型。课件制作人：谢希仁数据链路层的简化模型局域网广域网主机H1主机H2路由器R1路由器R2路由器R3电话网局域网主机H1向H2发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动课件制作人：谢希仁数据链路层的简化模(续）局域网广域网主机H1主机H2路由器R1路由器R2路由器R3电话网局域网主机H1向H2发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动课件制作人：谢希仁3.2.1完全理想化的数据传输数据链路层主机A缓存主机B数据链路AP2AP1缓存发送方接收方帧高层帧课件制作人：谢希仁完全理想化的数据传输所基于的两个假定假定1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定2：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。课件制作人：谢希仁3.2.2具有最简单流量控制的数据链路层协议现在去掉上述的第二个假定。但是，仍然保留第一个假定，即主机A向主机B传输数据的信道仍然是无差错的理想信道。然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。由收方控制发方的数据流，乃是计算机网络中流量控制的一个基本方法。课件制作人：谢希仁具有最简单流量控制的数据链路层协议算法在发送结点：(1)从主机取一个数据帧。(2)将数据帧送到数据链路层的发送缓存。(3)将发送缓存中的数据帧发送出去。(4)等待。(5)若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到(2)。课件制作人：谢希仁具有最简单流量控制的数据链路层协议算法（续）在接收结点：(1)等待。(2)若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。(3)将接收缓存中的数据帧上交主机。(4)向发送结点发一信息，表示数据帧已经上交给主机。(5)转到(1)。课件制作人：谢希仁两种情况的对比（传输均无差错）AB送主机B送主机B送主机B送主机BAB送主机B送主机B时间不需要流量控制需要流量控制课件制作人：谢希仁3.2.3实用的停止等待协议时间AB送主机送主机(a)正常情况AB送主机(c)数据帧丢失重传tout丢失！AB送主机丢弃(d)确认帧丢失重传tout丢失！AB送主机(b)数据帧出错重传出错四种情况课件制作人：谢希仁超时计时器的作用结点A发送完一个数据帧时，就启动一个超时计时器(timeouttimer)。计时器又称为定时器。若到了超时计时器所设置的重传时间tout而仍收不到结点B的任何确认帧，则结点A就重传前面所发送的这一数据帧。一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。课件制作人：谢希仁解决重复帧的问题使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加1。若结点B收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机B。但此时结点B还必须向A发送确认帧ACK，因为B已经知道A还没有收到上一次发过去的确认帧ACK。课件制作人：谢希仁帧的编号问题任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。序号占用的比特数越少，数据传输的额外开销就越小。对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。一个比特可表示0和1两种不同的序号。课件制作人：谢希仁帧的发送序号数据帧中的发送序号N(S)以0和1交替的方式出现在数据帧中。每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。课件制作人：谢希仁可靠传输虽然物理层在传输比特时会出现差错，但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可以提供可靠传输的服务。课件制作人：谢希仁3.2.4循环冗余检验的原理在数据链路层传送的帧中，广泛使用了循环冗余检验CRC的检错技术。假设待传送的数据M=1010001101（共kbit）。我们在M的后面再添加供差错检测用的nbit冗余码一起发送。课件制作人：谢希仁冗余码的计算用二进制的模2运算进行2n乘M的运算，这相当于在M后面添加n个0。得到的(k+n)bit的数除以事先选定好的长度为(n+1)bit的数P，得出商是Q而余数是R，余数R比除数P至少要少1个比特。课件制作人：谢希仁冗余码的计算举例设n=5,P=110101，模2运算的结果是：商Q=1101010110，余数R=01110。将余数R作为冗余码添加在数据M的后面发送出去，即发送的数据是101000110101110，或2nM+R。课件制作人：谢希仁1101010110←Q商除数P→110101101000110100000←2nM被除数11010111101111010111101011010111111011010110110011010111001011010101110←R余数循环冗余检验的原理说明课件制作人：谢希仁帧检验序列FCS在数据后面添加上的冗余码称为帧检验序列FCS(FrameCheckSequence)。循环冗余检验CRC和帧检验序列FCS并不等同。CRC是一种常用的检错方法，而FCS是添加在数据后面的冗余码。FCS可以用CRC这种方法得出，但CRC并非用来获得FCS的惟一方法。课件制作人：谢希仁检测出差错只要得出的余数R不为0，就表示检测到了差错。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。课件制作人：谢希仁应当注意仅用循环冗余检验CRC差错检测技术只能做到无差错接受(accept)。“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。也就是说：“凡是接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。课件制作人：谢希仁3.2.5停止等待协议的算法这里不使用否认帧（实用的数据链路层协议大都是这样的），而且确认帧带有序号n。按照习惯的表示法，ACKn表示“第n–1号帧已经收到，现在期望接收第n号帧”。ACK1表示“0号帧已收到，现在期望接收的下一帧是1号帧”；ACK0表示“1号帧已收到，现在期望接收的下一帧是0号帧”。课件制作人：谢希仁在发送结点(1)从主机取一个数据帧，送交发送缓存。(2)V(S)←0。(3)N(S)←V(S)。(4)将发送缓存中的数据帧发送出去。(5)设置超时计时器。(6)等待。{等待以下(7)和(8)这两个事件中最先出现的一个}(7)收到确认帧ACKn，若n=1–V(s)，则：从主机取一个新的数据帧，放入发送缓存；V(S)←[1V(S)]，转到(3)。否则，丢弃这个确认帧，转到(6)。(8)若超时计时器时间到，则转到(4)。课件制作人：谢希仁在接收结点(1)V(R)←0。(2)等待。(3)收到一个数据帧；若N(S)=V(R)，则执行(4)；否则丢弃此数据帧，然后转到(6)。(4)将收到的数据帧中的数据部分送交上层软件（也就是数据链路层模型中的主机）。(5)V(R)←[1V(R)]。(6)n←V(R)；发送确认帧ACKn，转到(2)。课件制作人：谢希仁停止等待协议的要点只有收到序号正确的确认帧ACKn后，才更新发送状态变量V(S)一次，并发送新的数据帧。接收端接收到数据帧时，就要将发送序号N(S)与本地的接收状态变量V(R)相比较。若二者相等就表明是新的数据帧，就收下，并发送确认。否则为重复帧，就必须丢弃。但这时仍须向发送端发送确认帧ACKn，而接收状态变量V(R)和确认序号n都不变。课件制作人：谢希仁停止等待协议的要点（续）连续出现相同发送序号的数据帧，表明发送端进行了超时重传。连续出现相同序号的确认帧，表明接收端收到了重复帧。发送端在发送完数据帧时，必须在其发送缓存中暂时保留这个数据帧的副本。这样才能在出差错时进行重传。只有确认对方已经收到这个数据帧时，才可以清除这个副本。课件制作人：谢希仁停止等待协议的要点（续）实用的CRC检验器都是用硬件完成的。CRC检验器能够自动丢弃检测到的出错帧。因此所谓的“丢弃出错帧”，对上层软件或用户来说都是感觉不到的。发送端对出错的数据帧进行重传是自动进行的，因而这种差错控制体制常简称为ARQ(AutomaticRepeatreQuest)，直译是自动重传请求，但意思是自动请求重传。课件制作人：谢希仁3.2.6停止等待协议的定量分析设tf是一个数据帧的发送时间，且数据帧的长度是固定不变的。显然，数据帧的发送时间tf是数据帧的长度lf(bit)与数据的发送速率C(bit/s)之比，即tf=lf/C=lf/C(s)（3-1）发送时间tf也就是数据帧的发送时延。数据帧沿链路传到结点B还要经历一个传播时延tp。结点B收到数据帧要花费时间进行处理，此时间称为处理时间tpr，发送确认帧ACK的发送时间为ta。课件制作人：谢希仁停止等待协议中数据帧和确认帧的发送时间关系ABDATADATAACK传播时延tp处理时间tpr确认帧发送时间ta传播时延tp处理时间tprtT时间两个成功发送的数据帧之间的最小时间间隔数据帧的发送时间tf设置的重传时间tout课件制作人：谢希仁重传时间重传时间的作用是：数据帧发送完毕后若经过了这样长的时间还没有收到确认帧，就重传这个数据帧。为方便起见，我们设重传时间为tout=t