计算机网络课程PPT(3).ppt

1、第3章 数据链路层,3.1 数据链路层的基本概念 3.2 停止等待协议 3.3 连续ARQ协议 3.4 选择重传ARQ协议 3.5 面向比特的链路控制规程HDLC 3.6 因特网的点对点协议PPP,退出,3.1 数据链路层的基本概念,链路(link)就是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。 数据链路(data link)则是另一个概念。这是因为当需要在一条线路上传送数据时，除了必须有一条物理线路外，还必须有一些必要通信协议来控制这些数据的传输。 也有人采用另外的术语。这就是将链路分为物理链路和逻辑链路。物理链路就是上面所说的链路，而逻辑链路就是上面的数据链路，是物理链路加

2、上必要的通信协议。,数据链路层的主要功能归纳如下： （1）链路管理 数据链路的建立、维持和释放就叫做链路管理。 （2）帧同步 （3）流量控制(flow control) （4）差错控制 （5）将数据和控制信息区分开 （6）透明传输 （7）寻址,3.2 停止等待协议,停止等待(stop-and-wait)协议是最简单但也是最基本的数据链路层协议。 3.2.1 完全理想化的数据传输 图4-1所示的简化模型对于一个计算机网络中任意一条链路上的数据传输情况都是适用的。,缓冲区：解决数据传输速率不一值的矛盾 完全理想化的数据传输 假定一：链路是理想的传输信道，所传送的任何信息不会出差错也不会丢失。 假定

3、二：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。 接收缓冲区的容量无限大而永远不会溢出； 接收速率与发送速率绝对精确相等。,3.2.2 具有最简单流量控制的数据链路层协议 由接收方控制发送方的数据流，乃是计算机网络中流量控制的一个基本方法。,假定：链路是理想的传输信道，即所传送的任何数据既不会出差错也不会丢失。,在发送结点： 1）从主机取一个数据帧； 2）将数据帧送到数据链路层的发送缓存； 3）将发送缓存中的数据帧发送出去； 4）等待； 5）若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到2）。,在接收结点： 1）等

4、待； 2）若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存； 3）将接收缓存中的数据帧上交主机； 4）向发送结点发一信息，表示数据帧已经上交给主机； 5）转到1)。,3.2.3 实用的停止等待协议 传输数据的信道不能保证使所传的数据不产生差错，并且还需要对数据的发送端进行流量控制。,可能出现的差错有：位出错、帧丢失、帧重复、帧顺序错,图 (a)画的是数据在传输过程中不出差错的情况。,当发现差错时，结点B就向主机A发送一个否认帧NAK，以表示主机A应当重传出现差错的那个数据帧。图(b)画出了主机A重传数据帧。,有时链路上的干扰很严重，或由于其他一些原因，结点B收不到结点A发来的数据

5、帧。这种情况称为帧丢失，如图 (c)所示,出现死锁现象。 要解决死锁问题，可在结点A发送完一个数据帧时，就启动一个超时计时器(timeout timer)。若到了超时计时器所设置的重传时间tout而仍收不到结点B的任何确认帧，则结点A就重传前面所发送的这一数据帧，如图(c)和图(d)所示。一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。,将待传送m位的数据帧的每一位看作一个（m-1）阶 多项式M(x)中各项的系数 收发双方共同使用一个r阶的生成多项式P(x） 用P(x)去除M(x)得余数多项式R(x) 该R(x)对应的比特串称为校验和 将R(x)连接到M(x)之后即得到含

6、校验和的传输编码对应的多项式T(x)。 接收方对所收到的T(x)用P(x)去除，若能除尽则无差错，否则为传输出错。,3.2.4 循环冗余检验CRC,例：设需传送的数据M=1010001101，其生成多项式为P(x)=x5+x4+x2+1，试求出CRC校验码。计算,最后发送出去的数据是101000110101110,3.2.5 停止等待协议的算法 在发送结点： （1）从主机取一个数据帧。 （2）V(S)0。 发送状态变量初始化 （3）N(S)V(S)；将发送状态变量的数值写入发送序号将数据帧送交发送缓存。 （4）将发送缓存中的数据帧发送出去。 （5）设置超时计时器。选择适当的超时重传时间tout

7、 （6）等待。等待以下2个事件中最先出现的一个 （7）若收到确认帧ACKn，则： 从主机取一个新的数据帧； V(S)1 V(S)；更新发送状态变量，变为下一个序号 转到(3)。否则,丢弃这个确认帧,转到(6) （8）若超时计时器时间到，则转到(4)。重传数据帧,注意:这里不使用NCK,ACKn表示:第n-1帧已收到,现在期望收第n号帧,在接收结点： （1）V(R)0。 接收状态变量初始化，其数值等于欲接收的数据帧的发送序号 （2）等待。 （3）收到一个数据帧;隐含表示已通过CRC差错检测。 若N(S) = V(R)，则执行后续算法(4)；收到发送序号正确的数据帧 否则丢弃此数据帧，然后转到(6

8、)。丢弃的是重复帧 （4）将收到的数据帧中的数据部分送交上层。 （5）V(R)1 V(R)。 更新接收状态变量，准备接收下一个数据帧 （6）n V(R) 发送确认帧 ACK，并转到(2).,状态变量的概念很重要，一定要弄清以下几点： （1）每发送一个数据帧，都必须将发送状态变量V(S)的值(即0或1)写到数据帧的发送序号N(S)上。但只有收到一个确认帧ACKn后，才更新发送状态变量V(S)一次(将1变成0或0变成1)并发送新的数据帧。 （2）在接收端，每接收到一个数据帧，就要将发送方在数据帧上设置的发送序号N(S)与本地的接收状态变量V(R) 相比较。若二者相等就表明是新的数据帧，否则为重复帧

9、,丢弃。但这时仍需发送确认帧ACKn，而接收状态变量V（R）和确认序号n不变，即和已发送的确认帧是一样的。,（3）连续出现相同发送序号的数据帧，表明发送端超时重传了，连续出现相同序号的确认帧，表明接收端收到重复帧。 （4）发送端发送完数据帧时，必须在其缓存暂时保留副本。使在出差错时进行重传。只有确认对方已收到这个数据帧时，才可以清除副本 （5）CRC检验器是用硬件完成的。它能够自动丢弃出错帧，对上层来说是感觉不到的。由于发送端对出错的数据帧进行重传是自动进行的，所以这种差错控制体制常简称为ARQ (Automatic Repeat reQuest)，直译是自动重传请求，但意思是自动请求重传。,

10、tf -一个数据帧的发送时间 tp -单向的传播时延 tpr-对一帧信息的处理时间 ta -确认帧的发送时间,3.2.6 停止等待协议中的几个重要时间关系,设数据帧长度为L, 数据发送速率为C, 由发送节点到接收节点的传播延时为R秒发送一帧的时间: tf =L /C (秒)单向的传播时延: tp =R(秒) 设重发时间为：tout= tp + tpr + ta + tp + tpr 由于tpr 和ta tp ，忽略tpr 和ta tout= 2tp 两个发送成功的数据帧之间的最小时间间隔： tT = tf + tout = tf + 2tp = L/C + 2R 实际用于发送有效数据的时间 最

11、大允许使用的时间 = tf / tT =(L/C)/(L/C+2R)=L/(L+2CR),信息利用率=,例:设卫星信道数据速率C=50kb/s,两个卫星地面站单向传播延时R=0.25秒,数据帧长1Kb,求信道利用率 信道利用率=L/(L+2CR) =1000/(1000+2*50*1000*0.25) =4%,停止等待协议ARQ 优点:简单,实现容易 缺点:通信信道的利用率低. 因此产生了连续ARQ和选择重传ARQ,3.3 连续ARQ协议,3.3.1 连续ARQ协议的工作原理 发送方连续发送若干数据帧（未收到确认），接收方按序接收，若已发送的某帧出错，则发送方将此帧及其后所有帧重发。又称为回退

12、n 的连续重传协议。 由于减少了等待时间，整个通信的吞吐量就提高了。,（1）接收端只按序接收数据帧。（2）结点A在每发送完每一个数据帧时都要设置超时计时器。（3）ACKn表示确认n-1号DATAn-1，并期望下次收到n号帧；,3.3.2 滑动窗口的概念,在使用ARQ协议时，如果发送端一直没有收到对方的确认信息，那么实际上发送端并不能无限制地发送其数据帧。 发送窗口:,发送窗口用来对发送端进行流量控制，而发送窗口的大小WT就代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。,发送窗口的规则归纳如下： （1）发送窗口内的帧是允许发送的帧，而不考虑有没有收到确认。发送窗口右侧所有的

13、帧都是不允许发送的帧。 （2）每发送完一个帧，允许发送的帧数就减1。但发送窗口的位置不变。见图 (b)已经发送了0号帧，因此允许发送的帧数就少了一个，即只有4个。 （3）如果所允许发送的5个帧都发送完了，但还没有收到任何确认，那么就不能再发送任何帧了。图 (c) （4）每收到对一个帧的确认，发送窗口就向前(即向右方)滑动一个帧的位置。图 (d)表示发送端已经收到了0, 1和2号帧共3个帧的确认，因此发送窗口可以向前滑动3个帧的位置。于是，发送端现在又可以继续发送3个帧(即5 7号帧)。,在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。 接收窗口的规则: （1）只有当收到

14、的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。 （2）每收到一个序号正确的帧，接收窗口就向前(即向右方)滑动一个帧的位置。同时向发送端发送对该帧的确认。,接收窗口,图 (a)表明一开始接收窗口处于0号帧处，接收端准备接收0号帧。一旦收到0号帧，接收窗口即向前滑动一个帧的位置，准备接收1号帧，同时向发送端发送对0号帧的确认信息。当陆续收到1号至3号帧后，接收窗口的位置如图(c)示。,3.4 选择重传ARQ协议,发送方在未收到确认下可以连续发送若干帧，接收方按顺序接收，若某帧出错，则将此帧重传。 只重传出现差错的数据帧或定时器超时的数据帧。 要求接收方要有更大的缓冲区,n:帧编号的位数（

15、2进制位数）,滑动窗口协议 - 连续重传协议 - 选择重传协议,3.5 面向比特的链路控制规程HDLC,3.5.1 HDLC概述 数据链路层的同步协议 一. 面向字符型的同步协议 (规程)典型代表：IBM的二进制同步通讯协议（BSC）数据以字符为单位，帧同步也是以字符作为首尾定界。 二. 面向比特型的同步协议(规程)IBM：SDLC（同步数据链路规程）HDLC（高级数据链路规程） HDLC可适用于链路的两种基本配置，即非平衡配置与平衡配置。非平衡配置的特点是由一个主站(primary station)控制整个链路的工作。主站发出的帧叫做命令(command)。受控的各站叫做次站或从站(seco

16、ndary station)。次站发出的帧叫做响应(response)。平衡配置的特点是链路两端的两个站都是复合站,同时具有主站和次占的功能, 每个复合站都可发出命令和响应,1) 标志序列(F) 8bit ，01111110 2) 地址字段(A) 全1是广播地址，全0是无效地址 3) 控制字段(C) 表示各种命令和响应 4) 信息字段(I) 10002000bit ，“零比特填充法” 5) 帧校验序列(FCS) 16位CRC校验码 x16+x12+x5+1,3.5.2 HDLC的帧结构 1. 各字段的意义,HDLC采用零比特填充法使一帧中两个F字段之间不会出现6个连续1。 在发送端，当一串比特

17、流数据尚未加上标志字段时，先用硬件或软件扫描整个帧,如发现有5个连续1，则立即填入一个0。 在接收一个帧时，先找到F字段以确定一个HDLC帧的边界。接着再用硬件对其中的比特流进行扫描。每当发现5个连续1时，就将这5个连续1后的一个0删除，以还原成原来的比特流,按照控制字段前两个比特取值HDLC帧划分为: 信息帧、监督帧和无编号帧，其简称分别是I (Information)、S (Supervisory)和U (Unnumbered)。,2信息帧 控制字段第1比特为0信息帧。 发送序号N(S)：当前发送的信息帧的序号 接收序号N(R)：该站所期望收到的帧的发送序号。 带有确认的意思，表示序号为N

18、(R)-1(mod 8)的帧以及在这以前的各帧都以正确无误地收妥。 在全双工通信的收发双方需各设置两个状态变量V(S)和V(R)，由它们的值确定发送序号N(S)和接收序号N(R)。 询问/终止(Poll/Final)比特，P/F比特。,3监督帧 若控制字段的第1 2比特为1 0，则对应的帧即为监督帧S。监督帧共有四种，取决于第3 4比特的值(结构图中标有S的二比特)。表中是这四种监督帧的名称和功能。,RR帧和RNR帧具有流量控制的作用。,3无编号帧 若控制字段的第1 2比特都是1时，这个帧就是无编号帧U。无编号,无N(S),N(R),主要起控制作用. SNRM：置通常响应方式。该方式禁止次站发

19、送任何未经邀请的帧。 SABM：置异步平衡方式。通信双方都处于同等的地位，不要轮询就可以发送，因为每个站都是一个复合站。 DISC：断连。当一个主站或复合站要关断链路时，它就发送一个DISC命令。它所期待的回答是UA。 UA：无编号肯定确认。 FRMR：帧拒绝。 .,3.6 因特网的点对点协议PPP,全世界使用得最多的数据链路层协议是非常简单的点对点协议PPP (Point-to-Point Protocol) 因特网服务提供者ISP是一个能够提供用户拨号入网的经营机构。,PPP不是面向比特而是面向字节的，因而所有的PPP帧的长度都是整数个字节。,当PPP用在同步传输链路时，协议规定采用硬件来

20、完成比特填充(和HDLC的做法一样)。但当PPP用在异步传输时，它就使用一种特殊的字符填充法。,PPP由以下三个组件组成：一种在串行链路上封装数据报的方法;一个用于建立、配置和测试数据链路连接的链路控制协议 LCP (Link Control Protocol);一个用于建立、配置不同网络层协议的网络控制协议 NCP (Network Control Protocol)。 发送端PPP首先发送LCP帧，以配置和测试数据链路。在LCP建立好数据链路并协调好所选设备后，发送端PPP发送NCP帧，以选择和配置一个或多个网络层协议。当所选的网络层协议配置好后，便可将各网络层协议的数据包发送到数据链路上。,现在让我们来考察一个家庭用户呼叫一个Internet服务提供商使一个家庭PC成为一个暂时的Internet主机的典型过程。 PC首先通过一个MODEM呼叫提供者的路由器。在路由器的MODEM回了电话并建立了一条物理连接之后，PC在一个或多个PPP帧的载荷段中