《数据链路控制.ppt》由会员分享,可在线阅读,更多相关《数据链路控制.ppt(72页珍藏版)》请在三一文库上搜索。
1、第3章 数据链路层,概述 帧同步和透明传输 差错检验 数据链路控制 HDLC PPP,数据链路层的主要功能: 把可靠性较低的物理信道转变成可靠性较高的逻辑信道,完成物理寻址、网络拓扑结构、连接规则、差错控制、帧的有序传输和流量控制等功能。确保相邻结点间帧(Frame)的正确传送。 协议要解决的问题: 成帧和拆帧 、检错和纠错、 流量控制、信道分配(MAC 介质访问控制子层),3.1 概述,数据链路层使用的信道主要有以下两种类型: 点对点信道。这种信道使用一对一的点对点通信方式。 广播信道。这种信道使用一对多的广播通信方式,因此过程比较复杂。广播信道上连接的主机很多,因此必须使用专用的共享信道协
2、议来协调这些主机的数据发,3.2 帧同步和透明传输,数据链路层的简单模型,相邻节点之间的通讯 物理层之上,网络层之下。,5 4 3 2 1,数据链路层,应用层,运输层,网际层,物理层,Application layer,Transport layer,Internet layer,Data link layer,Physical layer,数据链路层的简单模型,局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3,电话网,局域网,主机 H1 向 H2 发送数据,从层次上来看数据的流动,局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3
3、,电话网,局域网,主机 H1 向 H2 发送数据,链路层,应用层,运输层,网络层,物理层,链路层,应用层,运输层,网络层,物理层,链路层,网络层,物理层,链路层,网络层,物理层,链路层,网络层,物理层,R1,R2,R3,H1,H2,仅从数据链路层观察帧的流动,数据链路层的简单模型( 续),链路(link)是一条无源的点到点的物理线路段,中间没有任何其他的交换结点。 一条链路只是一条通路的一个组成部分。 数据链路(data link) 除了物理线路外,还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上,就构成了数据链路。 现在最常用的方法是使用适配器(即网卡)来实现这些
4、协议的硬件和软件。 一般的适配器都包括了数据链路层和物理层这两层的功能。,使用点对点信道的数据链路层,IP 数据报,1010 0110,帧,取出,数据 链路层,网络层,链路,结点 A,结点 B,物理层,数据 链路层,结点 A,结点 B,(a),(b),发送,接收,链路,IP 数据报,1010 0110,帧,装入,数据链路层传送的是帧,常常在两个对等的数据链路层之间画出一个数字管道,而在这条数字管道上传输的数据单位是帧。 早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层,规程和协议是同义语。,数据链路层像个数字管道,(1) 封装成帧 (2) 透明传输 (3) 差错控制,链
5、路层的三个基本问题,1. 封装成帧,封装成帧(framing)就是在一段数据的前后分别添加首部和尾部,然后就构成了一个帧。确定帧的界限。 首部和尾部的一个重要作用就是进行帧定界。,帧结束,帧首部,IP 数据报,帧的数据部分,帧尾部, MTU,数据链路层的帧长,开始 发送,帧开始,用控制字符进行帧定界的方法举例,SOH,装在帧中的数据部分,帧,帧开始符,帧结束符,发送在前,EOT,2. 透明传输,SOH,EOT,出现了“EOT”,被接收端当作无效帧而丢弃,被接收端 误认为是一个帧,数据部分,EOT,完整的帧,发送 在前,解决透明传输问题,发送端的数据链路层在数据中出现控制字符“SOH”或“EOT
6、”的前面插入一个转义字符“ESC”(其十六进制编码是 1B)。 字节填充(byte stuffing)或字符填充(character stuffing)接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。 如果转义字符也出现数据当中,那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时,就删除其中前面的一个。,SOH,SOH,EOT,SOH,ESC,ESC,EOT,ESC,SOH,ESC,ESC,ESC,SOH,原始数据,EOT,EOT,经过字节填充后发送的数据,字节填充,字节填充,字节填充,字节填充,发送 在前,帧开始符,帧结束符,用字节填充法解决透明传输的问题,S
7、OH,误码率 ER(Pc)= 错误的码数/总的码数 纠错码 (error-correcting code) 检错码 (error-detecting code),反馈重发纠错。,3.3 差 错 校 验,循环冗余校验CRC码 (Cyclic Redundancy Check) 码多项式: C(x) = Cn-1xn-1 + Cn-2xn-2 + + C1x+ C0 由:信息码(k位):码多项式 K(x), (k-1)次; 校验码(r位):码多项式 R(x), (r -1)次; 可得:CRC码(n =k +r 位),码多项式C(x) : C(x) = xr K(x) + R(x),(n -1)次。
8、 只要求得R(x) 即可。,3.3 差 错 校 验,发方由已知的 K(x) 求 R(x) : R(x) = xr K(x) G(x) 的 r 位余数 除法用无借位减 G(x) : 给定的生成多项式 (generator polynomial) 示例 收方校验: 设xr K(x)除以G(x)的商为Q(x),则 xr K(x)= G(x) Q(x)+ R(x) C(x) =xr K(x) + R(x)= G(x) Q(x)+ R(x) +R(x) = G(x) Q(x) -整除,3.3 差 错 校 验,由 K(x) 求 R(x)示例,信息位串: 1011001 生成多项式: 11001 得到余数:
9、 1010,数据链路(data link), 完全理想的数据链路 : (1)不管以何种速度传送出去的数据,目的端都无一丢弃的接收到。 (2) 理想的传输通道,数据没有任何差错传输到目的端。,3.4 链路控制,当数据传输过程中出现发送方的传输能力大于接收方的接收能力就需要流量控制,来限制发送方发出的数据流量,使发送方的发送速率不要超过接收方的接收能力。 流量控制(flow control) 基本思路: 由收方控制发方的数据流量,反馈控制,双向通讯。 流量控制是一个技术问题,见诸于通讯、数据存储、交通、生产流程等。,实际情况1缓冲区有限/处理速度有限,数据在传输的过程中,总会因为受外界干扰或者设计
10、的bug从而导致数据出错,因此接收端收到的数据并非全部正确。 差错表现: 数据帧未到达目的端、数据帧未正确到达目的端。,实际情况2易错信道,实际情况2易错信道,差错控制(error control) (1)差错发现(error detection) (2)正确认(positive acknowledgement,):收到正确帧后,回传确认信息 (3) 超时重发(timeout retransmission) (4)负确认(negative acknowledgement)收到错误帧后,回传信息,要求重发。 自动请求重发ARQ(Automatic Repeat reQuest),为提高数据传输的
11、可靠性,在收发两端实施自动重传机制。即当发送端判断数据未能达到接收端时候,则自动重新发送丢失的数据。 包括:差错检测、定时器、确认、重传等。,自动重传请求ARQ协议,0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7,已成功发出 的数据帧,将发出的数据帧,窗口后沿,窗口前沿,帧序号,发送方 缓冲区,0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7,已正确接收 的数据帧,将收到的数据帧,帧序号,接收方 缓冲区,窗口后沿,窗口前沿,滑动窗口协议,发送窗口控制发送端的流量,接收窗口控制接收,* 基本思想: 发送方发出一个帧后停下来等待接收确认,每收到一个确认前只可发 1 个
12、帧,确认到达后发下 一帧; *目标: 保证每帧都能最终正确到达目的端,流量控制隐含其中。,停等ARQ(stop-and-wait ARQ),并发出现的问题: (1)发出的帧没有到达对方发 (帧丢失) (2)发出的帧没有正确到达对方 (3)回传的确认帧丢失 简单改进: (1)发方发出一帧后启动超时定时器,超时后未收到确认,重发此帧 ; (2)数据帧和确认帧编号(0/1)解决重复帧问题;,停等ARQ(stop-and-wait ARQ),特点: 吞吐量小(单位时间内传输的吞吐量) 传输效率低 易于理解,便于实现,停等ARQ(stop-and-wait ARQ),停等ARQ,基本思想: 1、增加缓冲
13、区,允许发方在没收到一个确认之前可多发送n个数据帧,如果没有收到正确帧的确认帧,则回退到N步,从有正确确认帧的地方开始重传。 2、累积确认(cumulative acknowledgement)机制,在连续收到多个正确的数据帧以后,才发送一个确认帧。,回退-N ARQ(go-back-N ARQ),3、超时重传: 发方发出每个帧后起动一超时定时器,超时未收到确认则重发该帧;若还发出了其后窗口中的其他帧,则超时帧及其后发出的帧全部重传 。 NOTE: 超时时间大小选择受多种因素制约。,回退-N ARQ(go-back-N ARQ),4、限定发送窗口: WT 2n-1 (最大序号) 目的: 充分利
14、用编号字段的bit数 避免重号出现、以防产生二义性,回退-N ARQ(go-back-N ARQ),基本思想: 提高信道的利用率,有选择性地只重传出错的帧,其后正确到达的帧则不再重传. 发送窗口:WT 2n/2(最大序号+1)/2,选择重传ARQ (selective repeat ARQ),实施的其他策略,发送策略 缓冲发送、 立即发送 提交策略 缓冲提交、 立即提交 接收策略 按序接收 、 按窗口接收 重传策略 发送端维持一个曾经发送尚未得到确认的报文的队列。只是重传头一个、成批重传、 单独重传。 确认策略 立即确认、累积确认,3.5 高级数据链路控制规程HDLC,面向比特的链路控制规程H
15、DLC(High level Data Link Control) The HDLC protocol is a general purpose protocol which operates at the data link layer of the OSI reference model. The protocol uses the services of a physical layer, and provides either a best effort or reliable communications path between the transmitter and receiv
16、er (i.e. with acknowledged data transfer). The type of service provided depends upon the HDLC mode which is used.,IBM SDLC,ANSI ADCCP,ISO HDLC,CCITT LAP,SNA网络,美国标准,国际标准,电信标准,LAPB,X.25网,3.5 高级数据链路控制规程HDLC,HDLC的特性 透明传输 可靠性高 传输效率高 灵活性高,HDLC是面向比特协议 采用比特填充技术 根据特定用途选择一个子集,3.5 高级数据链路控制规程HDLC,基本概念 站的类型 主站 从
17、站 组合站,负责控制整个链路的操作。 由主站发出的帧为命令。,在主站的控制下进行操作。 由从站发出的帧为响应。,组合了主站和从站两种特性。,发送命令帧 接收响应帧 管理整个链路,接收来自主站的命令帧 向主站发送响应帧 配合主站参与差错恢复,数据传输、数据流的扩展、差错检测和恢复等,3.5 高级数据链路控制规程HDLC,链路结构 非平衡型 平衡型,由一个主站和若干个从站组成。,由两个组合站组成。,支持全双工和半双工传输。,3.5 高级数据链路控制规程HDLC,操作方式 正常响应 (Normal Response Mode) 异步响应(Asynchronous Response Mode) 异步平
18、衡(Asynchronous Balanced Mode),仅当从站被主站探询之后,才能传输信息帧和有关帧。,从站可不经主站探询就传输信息帧和有关帧。,链路两端的组合站具有同等能力,任何一方可在任何时间发送命令帧和响应帧。,非平衡,非平衡,平衡,3.5 高级数据链路控制规程HDLC,HDLC基本内容 帧格式,全“1”广播地址用于对全部站点的探询,没有格式和内容的限制。长度受缓冲区和差错特性的限制。一般256个字节。,CRC冗余校验不包括Flag和填充的0 生成多项式g(x)=x16+x12+x5+1,全“0”无站地址用于测试数据链路的工作状态,3.5 高级数据链路控制规程HDLC,零比特填充法
19、,数据中某一段比特组合 恰好出现和F字段一样 的情况 发送端在5个连1之后填 入0比特再发送出去 在接受端将5个连一之后 的0比特删除,恢复原样,01001111110001010,会误认为是F字段,010011111010001010,010011111010001010,填入0,在此位置删除0,3.5 高级数据链路控制规程HDLC,对信息帧的应答和命令帧的响应,传递命令和控制信息,控制字段表示命令和响应的类别和功能。,N(S):当前发送帧的编号; N(R):接收方期待的下一帧。 P/F(Poll/Final) :探询/终止位。,分别用在命令和响应帧中。,P位命令帧和F位响应帧总是成对出现。
20、 在给定时间内,只能有一个P=1的帧是未完成的。,3.5 高级数据链路控制规程HDLC,命令和响应,S帧用于链路状态的监视控制。,这类格式为响应帧。,S-帧,确认序号小于N(R)的帧,但请求重发序号从N(R)开始的帧。,后退N协议,通知发送站重发序号为N(R)的帧。,选择重发协议,3.5 高级数据链路控制规程HDLC,3.5 高级数据链路控制规程HDLC,U-帧,主要用于各种无编号的命令和响应。,这些命令和响应用来扩充链路控制功能的种类。,3.5 高级数据链路控制规程HDLC,CONNECT.confirm,DISCONECT.request,DISCONECT.indication,CONN
21、ECT.request,CONNECT.indication,CONNECT.response,SABM,UA,DISC,UA,操作 初始化/断开连接,异步平衡方式,HDLC异步平衡方式,操作 数据传送,I, N(S), N(R),I帧格式:,I, 0, 0,I, 0, 1,I, 1, 1,I, 2, 1,I, 1, 3,I, 3, 2,I, 2,4,I, 3,4,RR,4,重复确认,累计确认,B,A,HDLC异步平衡方式,操作 流量控制,繁忙的站用RNR命令要求对方停止发送I-帧,接收RNR的站通常在一定时间间隔后用带P位的RR命令询问对方的状态。,必须用RR或RNR来响应,B,A,HDLC
22、异步平衡方式,操作 差错处理,I, 3, 0,REJ, 4,I, 4, 0,I, 4, 0,丢失,I, 5, 0,I, 5, 0,I, 6, 0,B,A,B丢弃5号帧,并给A发一个拒绝接受帧 A必须重传4号帧以后的所有帧。,采用REJ的差错恢复,HDLC异步平衡方式,操作 差错处理,B,A,采用超时机制的差错恢复,I, 2, 0,RR, 0, P,RR,4,I, 3, 0,RR, 3,F,I, 3, 0,超时,B丢弃出错帧。 既然有错就无法确认任何事情因为每个字段都值得怀疑,出错,主站A,主站B,主站C,A,B,C,B,RR0,P,B,I00,B,I10,B,I20,B,I30,F,B,RR4
23、,C,RR0,P,C,RR0,F,时间,非平衡方式中P/F比特的使用,异步平衡方式一个更复杂的例子,A,B,B,I00,P,B,I10,B,I20,B,I31,A,RR2,F,B,I42,B,I52,B,I62,B,I72,B,I02,B,I12,A,RR3,F,A,I00,A,I10,P,B,RR2,F,A,I22,A,I34,A,I45,A,I26,P,A,I30,(I,0,0),(I,1,0),(I,2,0),(I,0,_ ),(I,1,_ ),(I,_,_ ),(I,_,_ ),(I,_,_ ),(I,_,_ ),( _,_,_ ),( _,_,_ ),(I,2,_ ),(I,_,_
24、),(I,_,_ ),(I,3, _ ),(I,_,_ ),A,B,站A和站B用一条全双工信道传输数据帧,采用选择重发协议,帧的确认采取“捎带”确认技术。若没有数据帧时可用ACK进行单独确认,用NAK进行否定确认,A有10个、B有4个数据帧(I)要发送。,序号空间占二进制3位。发送和接收窗口从序号0开始。,没有超时和帧丢失。,帧的格式为:帧类型、发送序号、接收序号,若没有发送帧则帧类型为NONE;发送和接收序号如果没有意义则用N标明,(I,0,0),(I,1,0),(I,2,0),(I,0,3 ),(I,1,3 ),(I,3,2 ),(I,4,2 ),(I,5,2 ),(I,6,2 ),( N
25、ONE,N, N ),(NONE ,N, N ),(I,2,7 ),(I,7,3 ),(I,0,3 ),(I,3,1 ),(I,1,4 ),A,B,捎带确认 发送窗口4 序号最大为7,3.6.1 PPP 协议的特点 现在全世界使用得最多的数据链路层协议是点对点协议 PPP (Point-to-Point Protocol)。 用户使用拨号电话线接入因特网时,一般都是使用 PPP 协议。,3.6 点对点协议 PPP,用户到 ISP 的链路使用 PPP 协议,拓扑上是点到点 信道上是多样的 通讯过程涉及到复杂参数的协商,用 户,至因特网,已向因特网管理机构 申请到一批 IP 地址,ISP,接入网,
26、PPP 协议,1. PPP 协议应满足的需求,简单这是首要的要求 封装成帧 透明性 多种网络层协议 多种类型链路 差错检测 检测连接状态 最大传送单元 网络层地址协商 数据压缩协商,2. PPP 协议不需要的功能,纠错 流量控制 序号 多点线路 半双工或单工链路,1992 年制订了 PPP 协议。经过 1993 年和 1994 年的修订,现在的 PPP 协议已成为因特网的正式标准RFC 1661。 PPP 协议有三个组成部分 一个将 IP 数据报封装到串行链路的方法。 链路控制协议 LCP (Link Control Protocol)。 网络控制协议 NCP (Network Control
27、 Protocol)。,3. PPP 协议的组成,标志字段 F = 0x7E (符号“0x”表示后面的字符是用十六进制表示。十六进制的 7E 的二进制表示是 01111110)。 地址字段 A 只置为 0xFF。地址字段实际上并不起作用。 控制字段 C 通常置为 0x03。 PPP 是面向字节的,所有的 PPP 帧的长度都是整数字节。,3.2.2 PPP 协议的帧格式,PPP 有一个 2 个字节的协议字段。 当协议字段为 0x0021 时,PPP 帧的信息字段就是IP 数据报。 若为 0xC021, 则信息字段是 PPP 链路控制数据。 若为 0x8021,则表示这是网络控制数据。,IP 数据
28、报,1,2,1,1,字节,1,2,不超过 1500 字节,PPP 帧,先发送,7E,FF,03,F,A,C,FCS,F,7E,协议,信 息 部 分,首部,尾部,PPP 协议的帧格式,当 PPP 用在同步传输链路时,协议规定采用硬件来完成比特填充(和 HDLC 的做法一样)。 当 PPP 用在异步传输时,就使用一种特殊的字符填充法。,透明传输问题,将信息字段中出现的每一个 0x7E 字节转变成为 2 字节序列(0x7D, 0x5E)。 若信息字段中出现一个 0x7D 的字节, 则将其转变成为 2 字节序列(0x7D, 0x5D)。 若信息字段中出现 ASCII 码的控制字符(即数值小于 0x20
29、 的字符),则在该字符前面要加入一个 0x7D 字节,同时将该字符的编码加以改变。,字符填充,PPP 协议用在 SONET/SDH 链路时,是使用同步传输(一连串的比特连续传送)。这时 PPP 协议采用零比特填充方法来实现透明传输。 在发送端,只要发现有 5 个连续 1,则立即填入一个 0。接收端对帧中的比特流进行扫描。每当发现 5 个连续1时,就把这 5 个连续 1 后的一个 0 删除,,零比特填充,0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0,0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0,0 1 0 0 1 1 1 1 1 0 1 0 0 0
30、 1 0 1 0,信息字段中出现了和 标志字段 F 完全一样 的 8 比特组合,发送端在 5 个连 1 之后 填入 0 比特再发送出去,在接收端把 5 个连 1 之后的 0 比特删除,会被误认为是标志字段 F,发送端填入 0 比特,接收端删除填入的 0 比特,零比特填充,PPP 协议之所以不使用序号和确认机制是出于以下的考虑: 在数据链路层出现差错的概率不大时,使用比较简单的 PPP 协议较为合理。 在因特网环境下,PPP 的信息字段放入的数据是 IP 数据报。数据链路层的可靠传输并不能够保证网络层的传输也是可靠的。 帧检验序列 FCS 字段可保证无差错接受。,不提供使用序号和确认的可靠传输,
31、当用户拨号接入 ISP 时,路由器的调制解调器对拨号做出确认,并建立一条物理连接。 PC 机向路由器发送一系列的 LCP 分组(封装成多个 PPP 帧)。 这些分组及其响应选择一些 PPP 参数,和进行网络层配置,NCP 给新接入的 PC机分配一个临时的 IP 地址,使 PC 机成为因特网上的一个主机。 通信完毕时,NCP 释放网络层连接,收回原来分配出去的 IP 地址。接着,LCP 释放数据链路层连接。最后释放的是物理层的连接。,3.6.2 PPP 协议的工作状态,设备之间无链路,链路静止,链路建立,鉴别,网络层协议,链路打开,链路终止,物理链路,LCP 链路,已鉴别的 LCP 链路,已鉴别的 LCP 链路 和 NCP 链路,物理层连接建立,LCP 配置协商,鉴别成功或无需鉴别,NCP 配置协商,链路故障或 关闭请求,LCP 链路 终止,鉴别失败,LCP 配置 协商失败,3.6.2 PPP 协议的工作状态,PPP 协议的状态表,PPP 协议的FSM,
链接地址:https://www.31doc.com/p-3185919.html