计算机网络课程(3)市公开课一等奖省赛课微课金奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,计,算,机,网,络,第,3,章,数,据,链,路,层,1,第3章 数据链路层,3.1 数据链路层基本概念,3.2 停顿等候协议,3.3 连续ARQ协议,3.4 选择重传ARQ协议,3.5 面向比特链路控制规程HDLC,3.6 因特网点对点协议PPP,退出,第1页,3.1 数据链路层基本概念,链路,(link)就是一条无源点到点物理线路段，中间没有任何其它交换结点。,数据链路,(data link)则是另一个概念。这是因为当需要在一条线路上传送数据时，除了必须有一条物理线路外，还必须有一些必要通信协议来控制这些数据传输。,也有些人采取另外术语。这就是将链路分为物理链路和逻辑链路。物理链路就是上面所说链路，而逻辑链路就是上面数据链路，是物理链路加上必要通信协议。,第2页,数据链路层主要功效归纳以下：,（1）,链路管理,数据链路建立、维持和释放就叫做,链路管理,。,（2）,帧同时,（3）,流量控制,(flow control),（4）,差错控制,（5）,将数据和控制信息区分开,（6）,透明传输,（7）,寻址,第3页,3.2 停顿等候协议,停顿等候(stop-and-wait)协议是最简单但也是最基本数据链路层协议。,3.2.1 完全理想化数据传输,图4-1所表示简化模型对于一个计算机网络中任意一条链路上数据传输情况都是适用。,第4页,缓冲区：处理数据传输速率不一值矛盾,完全理想化数据传输,假定一：,链路是理想传输信道，所传送任何信息不会出差错也不会丢失。,假定二：,不论发方以多快速率发送数据，收方总是来得及收下，并及时上交主机。,接收缓冲区容量无限大而永远不会溢出；,接收速率与发送速率绝对准确相等。,第5页,3.2.2 含有最简单流量控制数据链路层协议,由接收方控制发送方数据流,，,乃是计算机网络中流量控制一个基本方法,。,第6页,假定,：链路是理想传输信道，即所传送任何数据既不会出差错也不会丢失。,在发送结点,：,1）从主机取一个数据帧；,2）将数据帧送到数据链路层发送缓存；,3）将发送缓存中数据帧发送出去；,4）等候；,5）若收到由接收结点发过来信息(此信息格式与内容可由双方事先约定好)，则从主机取一个新数据帧，然后转到2）。,第7页,在接收结点,：,1）等候；,2）若收到由发送结点发过来数据帧，则将其放入数据链路层接收缓存；,3）将接收缓存中数据帧上交主机；,4）向发送结点发一信息，表示数据帧已经上交给主机；,5）转到1)。,第8页,第9页,3.2.3 实用停顿等候协议,传输数据信道不能确保使所传数据不产生差错，而且还需要对数据发送端进行流量控制。,第10页,可能出现差错有：位犯错、帧丢失、帧重复、帧次序错,图(a)画是数据在传输过程中不出差错情况。,当发觉差错时，结点B就向主机A发送一个否定帧NAK，以表示主机A应该重传出现差错那个数据帧。图(b)画出了主机A重传数据帧。,有时链路上干扰很严重，或因为其它一些原因，结点B收不到结点A发来数据帧。这种情况称为帧丢失，如图(c)所表示,出现死锁现象。,要处理死锁问题，可在结点A发送完一个数据帧时，就开启一个,超时计时器,(timeout timer)。若到了超时计时器所设置重传时间t,out,而仍收不到结点B任何确认帧，则结点A就重传前面所发送这一数据帧，如图(c)和图(d)所表示。,普通可将重传时间选为略大于“从发完数据帧到收到确认帧所需平均时间,”。,第11页,将待传送,m,位数据帧每一位看作一个（,m-1,）阶 多项式,M(x),中各项系数,收发双方共同使用一个,r,阶生成多项式,P(x,）,用,P(x),去除,M(x),得,余数多项式,R(x),该,R(x),对应比特串称为校验和,将,R(x),连接到,M(x),之后即得到含校验和传输编码对应多项式,T(x),。,接收方对所收到,T(x),用,P(x),去除，若能除尽则无差错,，不然为传输犯错。,3.2.4 循环冗余检验CRC,第12页,例：设需传送数据M,=1010001101,，其生成多项式为,P(x)=x,5,+x,4,+x,2,+1,，试求出,CRC,校验码。计算,最终发送出去数据是101000110101110,第13页,3.2.5 停顿等候协议算法,在发送结点,：,（1）从主机取一个数据帧。,（2）V(S)0。发送状态变量初始化,（3）N(S)V(S)；将发送状态变量数值写入发送序号将数据帧送交发送缓存。,（4）将发送缓存中数据帧发送出去。,（5）设置超时计时器。选择适当超时重传时间,t,out,（6）等候。等候以下2个事件中最先出现一个,（7）若收到确认帧ACKn，则：,从主机取一个新数据帧；,V(S)1,V(S)；更新发送状态变量，变为下一个序号 转到(3)。不然,丢弃这个确认帧,转到(6),（8）若超时计时器时间到，则转到(4)。重传数据帧,注意:这里不使用NCK,ACKn表示:第n-1帧已收到,现在期望收第n号帧,第14页,在接收结点,：,（1）V(R)0。接收状态变量初始化，其数值等于欲接收数据帧发送序号,（2）等候。,（3）收到一个数据帧;隐含表示已经过CRC差错检测。若N(S)=V(R)，则执行后续算法(4)；收到发送序号正确数据帧,不然丢弃此数据帧，然后转到(6)。丢弃是重复帧,（4）将收到数据帧中数据部分送交上层。,（5）V(R)1,V(R)。更新接收状态变量，准备接收下一个数据帧,（6）n V(R),发送确认帧 ACK，并转到(2).,第15页,状态变量概念很主要，一定要搞清以下几点：,（1）每发送一个数据帧，都必须将发送状态变量V(S)值(即0或1)写到数据帧发送序号N(S)上。但只有收到一个确认帧ACKn后，才更新发送状态变量V(S)一次(将1变成0或0变成1)并发送新数据帧。,（2）在接收端，每接收到一个数据帧，就要将发送方在数据帧上设置发送序号N(S)与当地接收状态变量V(R)相比较。若二者相等就表明是新数据帧，不然为重复帧,丢弃。但这时仍需发送确认帧ACKn，而接收状态变量V（R）和确认序号n不变，即和已发送确实认帧是一样。,第16页,（3）连续出现相同发送序号数据帧，表明发送端超时重传了，连续出现相同序号确实认帧，表明接收端收到重复帧。,（4）发送端发送完数据帧时，必须在其缓存暂时保留副本。使在出差错时进行重传。只有确认对方已收到这个数据帧时，才能够去除副本,（5）CRC检验器是用硬件完成。它能够自动丢弃犯错帧，对上层来说是感觉不到。因为发送端对犯错数据帧进行重传是自动进行，所以这种差错控制体制常简称为ARQ(Automatic Repeat reQuest)，直译是,自动重传请求,，但意思是,自动请求重传,。,第17页,t,f,-一个数据帧发送时间,t,p,-单向传输时延,t,pr,-对一帧信息处理时间,t,a,-确认帧发送时间,DATA,ACK,DATA,A,B,时间,t,T,t,f,t,out,t,p,t,pr,t,a,t,p,t,pr,3.2.6 停顿等候协议中几个主要时间关系,第18页,设数据帧长度为L,数据发送速率为C,由发送节点到接收节点传输延时为R秒,发送一帧时间:,t,f,=L,/C(秒),单向传输时延:,t,p,=R(秒),设重发时间为：,t,out,=t,p,+t,pr,+t,a,+t,p,+t,pr,因为t,pr,和t,a,t,p,，忽略t,pr,和t,a,t,out,=2t,p,两个发送成功数据帧之间最小时间间隔：,t,T,=t,f,+t,out,=t,f,+2t,p,=,L/C+2R,实际用于发送有效数据时间,最大允许使用时间,=t,f,/t,T,=(L/C)/(L/C+2R)=L/(L+2CR),信息利用率=,DATA,ACK,DATA,A,B,时间,t,T,t,f,t,out,t,p,t,pr,t,a,t,p,t,pr,第19页,例:设卫星信道数据速率C=50kb/s,两个卫星地面站单向传输延时R=0.25秒,数据帧长1Kb,求信道利用率,信道利用率=L/(L+2CR),=1000/(1000+2*50*1000*0.25),=4%,停顿等候协议ARQ,优点:简单,实现轻易,缺点:通信信道利用率低.,所以产生了连续ARQ和选择重传ARQ,第20页,3.3 连续ARQ协议,3.3.1 连续ARQ协议工作原理,发送方连续发送若干数据帧（未收到确认），接收方按序接收，若已发送某帧犯错，则发送方将此帧及其后全部帧重发。又称为回退n 连续重传协议。,因为降低了等候时间，整个通信吞吐量就提升了。,第21页,（1）接收端只按序接收数据帧。（2）结点A在每发送完每一个数据帧时都要设置超时计时器。（3）ACKn表示确认n-1号DATAn-1，并期望下次收到n号帧；,0,1,2,3,4,5,2,3,4,5,6,A,B,DATA,ACK1,ACK2,ACK3,ACK4,犯错,t,f,t,out,时间,送主机,送主机,重传,丢弃,第22页,3.3.2 滑动窗口概念,在使用ARQ协议时，假如发送端一直没有收到对方确实认信息，那么实际上发送端并不能无限制地发送其数据帧。,发送窗口:,0,1,2,3,4,5,6,7,8,1,2,W,T,0,1,2,3,4,5,6,7,8,1,2,0,1,2,3,4,5,6,7,8,1,2,已收到确认,已收到确认,发送窗口,发送窗口用来对发送端进行流量控制,，而发送窗口大小,W,T,就代表,在还没有收到对方确认信息情况下发送端最多能够发送多少个数据帧,。,第23页,发送窗口规则归纳以下：,（1）发送窗口内帧是允许发送帧，而不考虑有没有收到确认。发送窗口右侧全部帧都是不允许发送帧。,（2）每发送完一个帧，允许发送帧数就减1。但发送窗口位置不变。见图(b)已经发送了0号帧，所以允许发送帧数就少了一个，即只有4个。,（3）假如所允许发送5个帧都发送完了，但还没有收到任何确认，那么就不能再发送任何帧了。图(c),（4）,每收到对一个帧确实认，发送窗口就向前(即向右方)滑动一个帧位置,。图d)表示发送端已经收到了0,1和2号帧共3个帧确实认，所以发送窗口能够向前滑动3个帧位置。于是，发送端现在又能够继续发送3个帧(即5 7号帧)。,第24页,在接收端只有当收到数据帧发送序号落入接收窗口内才允许将该数据帧收下,。,接收窗口规则:,（1）只有当收到帧序号与接收窗口一致时才能接收该帧。不然，就丢弃它。,（2）每收到一个序号正确帧，接收窗口就向前(即向右方)滑动一个帧位置。同时向发送端发送对该帧确实认。,接收窗口,第25页,图(a)表明一开始接收窗口处于0号帧处，接收端准备接收0号帧。一旦收到0号帧，接收窗口即向前滑动一个帧位置，准备接收1号帧，同时向发送端发送对0号帧确实认信息。当陆续收到1号至3号帧后，接收窗口位置如图(c)示。,0,1,2,3,4,5,6,7,8,1,2,W,R,0,1,2,3,4,5,6,7,8,1,2,0,1,2,3,4,5,6,7,8,1,2,已收到35号帧,已收到0号帧,准备接收0号帧,准备接收1号帧,准备接收4号帧,第26页,3.4 选择重传ARQ协议,发送方在未收到确认下能够连续发送若干帧，接收方按次序接收，若某帧犯错，则将此帧重传。,只重传出现差错数据帧或定时器超时数据帧。,要求接收方要有更大缓冲区,第27页,发送窗口值W,T,接收窗口值W,R,连续重传协议,2,n,-1,1,选择重传协议,2,n-1,2,n-1,n:帧编号位数（2进制位数）,滑动窗口协议,-连续重传协议,-选择重传协议,第28页,3.5 面向比特链路控制规程HDLC,3.5.1 HDLC概述,数据链路层同时协议,一.面向字符型同时协议(规程),经典代表：IBM二进制同时通讯协议（BSC）数据以字符为单位，帧同时也是以字符作为首尾定界。,二.面向比特型同时协议(规程),IBM：SDLC（同时数据链路规程）,HDLC（高级数据链路规程）,HDLC可适合用于链路两种基本配置，即,非平衡配置与平衡配置,。,非平衡配置特点,是由一个,主站,(primary station)控制整个链路工作。主站发出帧叫做,命令,(command)。受控各站叫做,次站,或,从站,(secondary station)。次站发出帧叫做,响应,(response)。,平衡配置特点,是链路两端两个站都是,复合站,同时含有主站和次占功效,每个复合站都可发出命令和响应,第29页,8,8,8,任意长,16,8,透明传输区间,检验区间,标志,F,帧检验序列,FCS,信息,Info,控制,C,地址,A,标志,F,01111110,01111110,1),标志序列(F),8bit，01111110,2),地址字段(A)全1是广播地址，全0是无效地址,3)控制字段(C),表示各种命令和响应,4)信息字段(I),1000bit，“,零比特填充法,”,5)帧校验序列(FCS),16位CRC校验码 x,16,+x,12,+x,5,+1,3.5.2 HDLC帧结构,1.各字段意义,第30页,HDLC采取,零比特填充法,使一帧中两个F字段之间不会出现6个连续1。,在发送端,，当一串比特流数据还未加上标志字段时，先用硬件或软件扫描整个帧,如发觉有5个连续1，则马上填入一个0。,在接收一个帧时,，先找到F字段以确定一个HDLC帧边界。接着再用硬件对其中比特流进行扫描。每当发觉5个连续1时，就将这5个连续1后一个0删除，以还原成原来比特流,第31页,按照,控制字段前两个比特,取值HDLC帧划分为:,信息帧,、,监督帧,和,无编号帧,，其简称分别是I(Information)、S(Supervisory)和U(Unnumbered)。,第32页,2信息帧,控制字段第1比特为0信息帧。,发送序号N(S),：,当前发送信息帧序号,接收序号N(R)：,该站,所期望收到帧发送序号,。,带有确认意思，表示序号为N(R)-1(mod 8)帧以及在这以前各帧都以正确无误地收妥。,在全双工通信收发双方需各设置两个状态变量V(S)和V(R)，由它们值确定发送序号N(S)和接收序号N(R)。,问询/终止(Poll/Final)比特，P/F比特。,第33页,3监督帧,若控制字段第1 2比特为1 0，则对应帧即为,监督帧,S。监督帧共有四种，取决于第3 4比特值(结构图中标有S二比特)。表中是这四种监督帧名称和功效。,RR帧和RNR帧含有流量控制作用。,第34页,3无编号帧,若控制字段第1 2比特都是1时，这个帧就是,无编号帧,U。无编号,无N(S),N(R),主要起控制作用.,SNRM,：,置通常响应方式。该方式禁止次站发送任何未经邀请帧。,SABM,：,置异步平衡方式。通信双方都处于同等地位，不要轮询就能够发送，因为每个站都是一个复合站。,DISC,：,断连。当一个主站或复合站要关断链路时，它就发送一个,DISC,命令。它所期待回答是,UA,。,UA,：,无编号必定确认。,FRMR,：,帧拒绝。,.,第35页,3.6 因特网点对点协议PPP,全世界使用得最多数据链路层协议是非常简单,点对点协议PPP(Point-to-Point Protocol),因特网服务提供者,ISP是一个能够提供用户拨号入网经营机构。,第36页,PPP不是面向比特而是面向字节，因而,全部PPP帧长度都是整数个字节,。,当PPP用在同时传输链路时，协议要求,采取硬件来完成比特填充,(和HDLC做法一样)。但当PPP用在异步传输时，它就使用一个,特殊字符填充法,。,第37页,PPP由以下三个组件组成,：一个在串行链路上封装数据报方法;一个用于建立、配置和测试数据链路连接链路控制协议 LCP(Link Control Protocol);一个用于建立、配置不一样网络层协议网络控制协议 NCP(Network Control Protocol)。,发送端PPP首先发送LCP帧，以配置和测试数据链路。在LCP建立好数据链路并协调好所选设备后，发送端PPP发送NCP帧，以选择和配置一个或多个网络层协议。当所选网络层协议配置好后，便可将各网络层协议数据包发送到数据链路上。,第38页,现在让我们来考查一个家庭用户呼叫一个Internet服务提供商使一个家庭PC成为一个暂时Internet主机经典过程。,PC首先经过一个MODEM呼叫提供者路由器。在路由器MODEM回了电话并建立了一条物理连接之后，PC在一个或多个PPP帧载荷段中发送一系列,LCP分组,给路由器。这些分组以及对它们响应负责选择要使用PPP参数。一旦在这些问题上达成了一致，就需要发送一系列,NCP分组,来配置网络层。经典地，PC要运行一个TCP/IP协议栈，所以它需要一个IP地址。现在IP地址是短缺，所以通常每个Internet提供商都得到一块地址，然后在每个新连接PC登录期间动态地分配给它一个地址。假如一个提供商拥有n个IP地址，那么他最多能够让n台机器同时登录，但其客户基地总客户数能够是n许多倍。IPNCP就用于做IP地址分配工作。,在通信过程这一点上，PC已经是一台Internet主机了，而且跟经常保持硬连接到网络主机一样，它能够发送和接收IP分组。当用户通信结束时，NCP又被用来拆除网络层连接，并释放IP地址。然后LCP被用来关闭数据链路层连接。最终，计算机告诉MODEM挂起电话，释放物理层连接。,第39页,PPP不提供,可靠传输服务,。,PPP协议之所以不使用序号和确认机制是出于以下几点考虑：,1）若使用可靠数据链路层协议(如HDLC)，开销就要增大。2）在因特网环境下，PPP信息字段放入数据是IP数据报。,数据链路层可靠传输并不能够确保网络层传输也是可靠,。3）PPP协议在帧格式中有帧检验序列FCS字段。,第40页,作 业,作业:3-06 3-16 3-23,2.假定我们要发送信息11001001，而且使用CRC多项式x,3,+1来检错,试求出应该发送出去信息块?,第41页,解答：取信息11001001，附加000，并用1001去除，余数是011 应该发送信息块是11001001011,第42页,