3+数据链路层(新)

1、第三章 数据链路层1第三章 数据链路层1 数据链路是什么？物理层实现了数据链路之间的bit流传输，按bit流进行数据传输存在什么问题？2 如何保证数据链路的可靠？3 我们以后自己设计一个数据链路层，有没有值得借鉴的案例呢?2局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网e.g链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动链路层: 工作环境3链路层: 工作环境局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网链路层应用层运输

2、层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动4链路层: 工作环境两个 物理上连接的 设备:主机-路由器, 路由器-路由器, 主机-主机数据单元: frame（帧）applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframe物理链路数据链路协议接口卡5链路层的服务帧同步帧的可靠传输 什么样的传输是可靠传输？差错控制流量控制链路访问机制（广播式链路）6链路层: 实现通过 “adapter（

3、网卡或适配器）” 实现e.g., PCMCIA 卡, 以太网卡 一般适配器都含有: RAM, DSP 芯片, 主机的总线接口, 和链路接口applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframephys. linkdata linkprotocoladapter card7问题1：帧如何定界（同步）？83.1 数据链路层基本概念成帧的四种方法字符计数法帧不定长，帧头中用一个字符来表示帧内的字符数缺点：计数字段一旦出错，将无法再同步93.1 数据链路层基本概念成帧的四种方法带填充字

4、符的首尾界符法以特定的字符序列为控制字段（起始字符 DLE STX，结束字符DLE ETX）缺点：依赖于字符集（8位字符和ASCII字符），不通用，也无法扩展103.1 数据链路层基本概念形成帧的四种方法带位填充的首尾标记定界法帧的起始和结束都用一个特殊的位串“01111110”，称为标记（flag）“0”比特插入删除技术(参动画)113.1 数据链路层基本概念形成帧的四种方法物理层编码违例法IEEE802协议中：高-低电平对表示“1”，低-高电平对表示“0”。高-高/低-低不表示数据，可以用来做定界符。只适用于在物理媒体的编码策略中采用了冗余技术的网络；优点：无需填充。注意在很多数据链路协议

5、中，使用字符计数法和一种其它方法的组合。12第三章 数据链路层1 数据链路是什么？物理层实现了数据链路之间的bit流传输，按bit流进行数据传输存在什么问题？2 如何保证数据链路的可靠？13问题2：如何保证数据链路的可靠？帧如何出错我们怎么能知道？若出错了怎么办?如何控制数据链路中帧的传输速率和效率？14错误检测：EDC= 错误检测校正（Error Detection and Correction (冗余数据)）位 错误检测不可能达到 100% 可靠! 协议算法可能会忽略了某些错误, 但比例极小 较大的 EDC 字段可以产生较好的检错和纠错效果3.2 差错控制加了它就可能知道？153.2.1

6、差错控制的基本概念目的确保帧可靠且按照正确的顺序传送到接收方能够达到校验或改正下一层数据差错编码技术纠错编码能够校正检测到的错误，开销大，不适合用于网络通信检错编码：检测收到帧的差错，处理方法：提示上层处理或者不处理要求重传错误帧163.2.1 差错控制的基本概念差错出现的特点随机，连续突发计算机网络中处理差错的两种基本策略使用纠错码（海明码）发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。使用检错码（奇偶校验、CRC）发送方在每个数据块中加入必要的冗余信息，使得接收方能够判断接收到的数据是否有错，但不能判断哪里有错。173.2.1 差错控制的基本

7、概念奇偶校验在传送数据的各位之外，再传送1位奇/偶校验位。奇校验所有传送的数位（含字符的各数位和校验位）中，“1”的个数为奇数。偶校验所有传送的数位（含字符的各数位和校验位）中，“1”的个数为偶数。18奇偶校验单比特校验:检测一位错误两维单比特校验:检测和校正单比特错误00193.2.2 海明纠错码海明纠错码的格式码字的编号从左到右，最左边是第一位，其中2的幂数位是检验位，其余是k个数据位(信息元)。海明纠错码格式如下： 20 21 22 23 24 p1 p2 * p3 * * * p4* * * * * * * p5 *-信息元 P-校验位203.2.2 海明纠错码海明码的编码与译码的方法

8、用矩阵乘法求检验位，并且找出错误位。设编码长度为 n = 2r 1，其中r为校验码的位数。数据位长度 k = n r。校验位插入到编码序列的2j-1 (j=1,2,.,r)的位置上；由r(样本)建立一个(2r -1)行 * r列的矩阵。 213.2.2 海明纠错码将编码字写成串形式的一维向量其中，l1 =l2 =lr =1或0(l=0为偶校验，l=1为奇校验)； bij = 1 或 0 223.2.2 海明纠错码例: 按下列步骤将数据(信息)1100进行编码，设校验位为r=3。 解: (1)编码长度 n = 2r 1 = 7 数据位 k = n r = 4 校验位 r = 3 233.2.2

9、海明纠错码 (2)编码过程由矩阵乘法得，p1 = 0 ,p2 = 1, p3 = 1 解得海明码为 0111100243.2.3 循环冗余码(CRC)循环冗余码（CRC）基本思想收发双方约定一个生成多项式G(x)（其最高阶和最低阶系数必须为1），发送方在帧的末尾加上校验序列，使带校验序列的帧的多项式能被G(x)整除；接收方收到后，用G(x)除多项式，若有余数，则传输有错。多项式码将位串看成系数为0或1的多项式如：110001，表示成多项式 x5+x4+1253.2.3 循环冗余码(CRC)循环冗余码（CRC）CRC的计算算法26循环冗余码(CRC)循环冗余码（CRC）常用的CRC生成多项式CR

10、C-12=x12+x11+x3+x2+x+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+1检错能力：CRC-16和CRC-CCITT可以捕捉突发错长度小于16的全部错误、长度为17的突发错的99.998、长度为18以上的突发错的99.997。27差错编码比较结论： 1.CRC检错能力强。 2.是线性码，有良好的结构，易于硬件实现。28在数据后面添加上的冗余码称为帧检验序列 FCS (Frame Check Sequence)。循环冗余检验 CRC 和帧检验序列 FCS并不等同。CRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码。FCS 可以用

11、 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的唯一方法。 3.2.3 循环冗余码(CRC)29差错控制差错控制编码检错码和纠错码差错控制技术差错控制的基本方法：接收方进行差错检测，并向发送方应答，告知是否正确接收。流量控制自动请求重传Automatic Repeat Request （ARQ）停等 ARQGo-back-N ARQ滑动窗口协议 3.3差错控制和流量控制303.3.1 停止等待协议的原理原理发送方发送完一帧数据后，必须等待接收方的确认帧返回，确认数据被正确接收后才能继续发送下一帧。313.3.1 停止等待协议的原理过程从主机取数据上交主机DATA1DATA2结点 A

12、结点 BACKACK323.3.2 单工肯定应答/重传停等协议单工肯定应答/重传停等协议的提出通信信道总是存在误码率，传输过程中难免要出错，造成发送帧或应答帧出错或丢失。frame iACK iframe i+1ACK i+1frame i+2frame i+2ACK i+2frame i+3ACK i+3frame i+3ACK i+3发送方接收方超时超时帧丢失 重发ACK丢失 重发，丢弃重复帧超时frame i+1丢弃重复帧333.3.2 单工肯定应答/重传停等协议问题1：发送帧出错或丢失怎么办？设置计时器，利用超时中断防止因帧丢失所造成的死锁。问题2：应答帧出错或丢失怎么办？设置帧序号，

13、利用序号检查是新帧还是重复帧。问题3：帧序号字段需占用多少位？根据停等协议的定义，表示帧发送序号的字段只需占用一位，因为只需检查前后两帧的顺序是否相同，而不注重各帧的顺序号本身的值是多少。343.3.2 单工肯定应答/重传停等协议例：发送帧本身序号为 0 1 2 3 4 5 6 7 停等协议帧序号为 0 1 0 1 0 1 0 1 同理，帧确认序号也只需占用一位。为便于判断序号的正确性，通常定义帧确认序号(ACK)为期望发送方下次发送的帧序号(SEQ)，表达式为：ACK=SEQ+1(mod 2)353.3.2 单工肯定应答/重传停等协议过程发送方将当前信息帧作为待确认帧保存在缓冲区发送数据的同

14、时起动计时器接收方收到数据后返回一个确认帧若接收方收到的数据有错，则丢弃发送方若在规定时间内没有收到确认帧，则计时器清零，重发缓冲区内的信息帧 363.3.2 单工肯定应答/重传停等协议373.3.3 双工停等协议双工停等协议双工协议在通道的每个方向都有发送帧(数据帧)和应答帧，为了区分它们，需要在帧的控制信息中增加一个帧类型的字段。“背回”(Piggybacking)技术如果某站收到对方的数据后，在给对方发送应答帧的同时，又有数据帧要发往对方，则不必单独发送应答帧，可以在数据帧中增加一个接受顺序号字段(ACK字段)以存放应答信息，于是对方在收到数据帧的同时也得到了应答。383.3.3 双工停

15、等协议背回应答的优点：减少了帧的发送数目能有效地利用通道，且接收站的“帧正确到达”中断次数和接收站的输入缓冲区均可以减少。但是背回应答增加了协议的复杂性。393.3.3 双工停等协议在双工停等协议中：去掉了高层始终有信息发送的假定，使协议接近数据通信的实际情况。但规定发送一帧后要等到应答后才能发送下一个新帧(所谓停等协议)。高层并非始终有信息发送，应答帧何时发送？解决办法：设置ACK计时器403.4 连续ARQ协议连续ARQ又称为Go-Back-N ARQ当出现差错必须重传时，要向回走N个帧，然后开始重传。原理发送端连续发送至发送缓冲区窗口满接收缓冲区窗口大小为1帧，对丢弃帧不确认发送方设置超

16、时，若超时回退若干帧到未被确认帧开始重传接收方从出错帧起丢弃所有后继帧413.4 连续ARQ协议特点发送方需要较大的缓冲区，以便重传减少了等待时间，提高了吞吐量发送帧和接受帧都要进行编号适于信道出错率较少的情况问题信道误码率高时，对损坏帧和非损坏帧的重传非常多，反而降低效率423.4 连续ARQ协议注意的问题接收端按序接收。例如：2号帧出错但收到正确的3号帧仍然丢弃3号帧从2号帧开始重传ACK1表示确认0号帧DATA0，期望下次收到1号帧，依次类推思考实际的连续ARQ利用一个计时器实现N个独立超时计数器的功能，思考这如何实现？433.5 滑动窗口协议采用窗口的原因应对以发送出去但尚未被确认的帧

17、的数目加以限制。要重复循环使用帧的序号，避免无止境的帧序号的增大。发送窗口在发送端。用来对发送方进行流量控制。发送窗口的大小：能够存放的待确认帧的最大数目。接收窗口在接收端。用来指示接收方允许接收的帧的序号。443.5 滑动窗口协议滑动窗口实例：发送窗口=2；接收窗口=1 初态：发送端无数据发出，接受端0号窗口打开准备接收数据发送端发出0号帧，0号窗口被占用；此时接收端尚未收到数据发送端发出1号帧，1号窗口被占用；此时接收端尚未收到数据。发送方停止发送数据。接收端0号帧收到，关闭其0号窗口，打开1号窗口等待接受发送方收到接收端发来的确认后，关闭0号窗口发送方发送2号帧，占用2号窗口，然后暂停发

18、送依次类推循环，达到了限止发送帧的数目，又避免了帧序号重复时的歧义。453.5 滑动窗口协议滑动窗口实例：发送窗口=2；接收窗口=1463.5 滑动窗口协议各种协议规定的缓冲窗口大小停止等待：发送窗口=1，接收窗口=1Go Back n：发送窗口1，接收窗口=1滑动窗口：发送窗口1，接收窗口1 47滑动窗口结论令发送窗口为WT，接收窗口为WR 。发送序号用n个比特表示。结论1：若WR1，则WT2n1例如n=3，（WT）max7结论2：WR2n/2，WT= WR=2n/2例如n=3 ，则WT= WR=4483.6链路和协议有三种类型的 “链路”:点对点 ( e.g. PPP, SLIP)广播式

19、(共享线路或介质; e.g, 传统以太网, 无线网, etc.)交换式 (e.g., 交换式以太网, ATM etc)493.6.1点对点的数据链路协议DLC一方发,一方收,一条链路:比广播信道简单的多无需介质访问控制不必进行MAC寻址e.g., 拨号链路, ISDN 线路等常见的点对点DLC协议:SLIP (Serial Line Internet Protocol)PPP (point-to-point 协议)SDLC: Synchronous Data Link Control (SNA的面向比特的数据链路规程)HDLC: High level data link control (高级

20、数据链路控制规程)503.6.2多点访问协议一条共享的通信信道 两个或多个结点可同时发送信号: 相互干扰 在某一时刻只有一个结点可以成功地发送信号 多点访问协议:分布式的算法来决定如何共享信道, 决定工作站何时可以发送注意：有关共享通道的通信（协商）也必须在该通道自身上解决! 我们希望多点访问协议能够解决什么问题: 同步还是异步 了解其他站点的信息 健壮性 (e.g.如何对待信道错误) 性能51点到点数据联络层案例高级数据链路控制规程HDLCPPP(Point-to-Point Protocol)协议。523.6.3 高级数据链路控制规程基本原则面向比特的数据链路层协议(规程）采用位填充法保证

21、数据的透明传输HDLC的组成帧结构规程元素规程类型使用HDLC的语法可以定义多种具有不同操作特点的链路层协议。533.6.3 高级数据链路控制规程HDLC涉及三种类型的站：主站（Primary Station）主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、差错恢复等）；从站（Secondary Station）主要功能是接收命令，发送响应，配合主站完成链路的控制；复合站（Combined Station）同时具有主、从站功能，既发送又接收命令和响应，并负责整个链路的控制。543.6.3 高级数据链路控制规程HDLC链路基本配置类型非平衡配置：点对点工作；多点

22、工作由一个主站控制整个链路的工作。主站发出的帧叫做命令。受控各站叫做次站或从站。从站发出的叫做响应。多点工作时主站与每个从站都有分开的逻辑链路。平衡配置：点对点工作链路上都是复合站，平等发送数据，不需要对方的允许。553.6.3 高级数据链路控制规程原理图命令(B)响应(B)主站A从站B非平衡配置：点-点命令(B/C/D)响应(B)响应(C)响应(D)主站A从站B从站C从站D非平衡配置：点-多点命令(B)命令(A)响应(B)响应(A)复合站A复合站B平衡配置563.6.3 高级数据链路控制规程帧的一般结构573.6.3 高级数据链路控制规程标志字段以0111 1110作为起止的帧边界标记零比特

23、填充法原因避免数据信息字段与标志字段F相同，引起帧边界错误，达到透明传输。采用方法发送端：利用硬件扫描数据信息字段，遇到5个1即添加一个0接受端：硬件扫描到连续5个1，因为发送端扫描填充过0，紧接的必然是0，去掉这个0580 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 00 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 00 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0信息字段中出现了和标志字段 F 完全一样的 8 比特组合发送端在 5 个连 1 之后填入 0 比特再发送出去在接收端把 5 个连 1之后的 0 比特删除会被误认为是标志字段

24、 F 发送端填入 0 比特接收端删除填入的 0 比特零比特填充实例593.6.3 高级数据链路控制规程地址字段非平衡方式写入从站地址，平衡方式写入确认站地址全1地址为广播方式，全0为无效地址，有效地址254个地址字段可扩展603.6.3 高级数据链路控制规程HDLC的三种帧类型信息帧（Information Frame）监督帧（Supervisory Frame）无编号帧（Unnumbered Frame）613.6.3 高级数据链路控制规程三种HDLC帧的控制字段623.6.3 高级数据链路控制规程三种HDLC帧的控制字段序号（Seq）当前发送的信息帧的序号。使用滑动窗口技术，3位序号，发送

25、窗口大小为4。捎带确认（Next）捎带下一个准备接受的帧序号，而不是最后一个已收到的帧序号。探询/结束 P/F位（Poll/Final）命令帧置“P”，响应帧置“F”。有些协议，P/F位用来强迫对方机器立刻发监督帧；多终端系统中，计算机置“P”，允许终端发送数据；终端发向计算机的帧中，最后一个帧置为“F”，其它置为“P”。633.6.3 高级数据链路控制规程三种HDLC帧的控制字段监督帧的类型（Type）643.6.3 高级数据链路控制规程三种HDLC帧的控制字段无编号帧可以用来传控制信息，也可在不可靠无连接服务中传数据；利用3、4、6、7、8共5个bit来表示不同的功能。653.6.3 高级

26、数据链路控制规程半双工“点-点”数据传送虽然HDLC设计为一个全双工协议，但它能用于半双工方式。在基本型半双工协议中，需要分别地确认每个信息报文，但HDLC能给予主站和次站连续发送若干信息帧的机会，然后对一组信息帧确认。这种方式，大大地减少了原先需要的线路周转次数，从而提高了传输效率。663.6.3 高级数据链路控制规程HDLC半双工和基本型半双工“点-点”传输如后页所示几点说明：类型(TYPE)：对于信息使用I帧，对于S帧则使用RR、REJ、RNR或SREJ。P/F指明探询或最后帧是否建立。673.6.3 高级数据链路控制规程683.6.3 高级数据链路控制规程如果发生了差错，例如信息帧I受

27、到干扰而损坏，帧交换顺序如下图所示。主站发送第4个帧时向次站发出探询(P/F=1)，次站响应“RR，1，F”，表示次站已成功地接受了“0”号帧。于是，主站重新发送第1，2，3号帧，并继续发送第4号I帧。693.6.3 高级数据链路控制规程703.6.3 高级数据链路控制规程全双工“点-点”数据传送如果链路、主站和次站具有全双工操作的能力，帧交换可按下图的顺序。71主站从站I,0,0I,1,0I,2,0I,3,0,PRR,1,FI,1,0I,2,0I,3,0,PI,4,0RR,4,FI,5,0I,6,0X 干扰723.6.3 高级数据链路控制规程注意：主站在发送了探询之后仍能继续发送数据。另外，

28、在发送信息帧7以后，发送顺序计数复原为“0”，这个系统在收到确认信息以前所能发送的最大信息帧数目等于4。733.6.4点对点协议PPP现在全世界使用得最多的数据链路层协议是点对点协议 PPP (Point-to-Point Protocol)。用户使用拨号电话线接入因特网时，一般都是使用 PPP 协议。 用户至因特网已向因特网管理机构申请到一批 IP 地址ISP接入网PPP 协议743.6.4 PPP 协议应满足的需求 简单这是首要的要求封装成帧将网络层的分组封装入数据链路层的帧 同时可以承载任意网络协议的网络层数据 (不仅仅是 IP)提供向上分用的能力透明性 在数据字段中，必须能携带任意组合

29、的位流多种网络层协议 多种类型链路 差错检测 , 无需校正检测连接状态 最大传送单元 网络层地址协商 数据压缩协商 753.6.4 PPP 协议不需要的功能纠错 流量控制 序号 ，允许失序递交 多点线路 半双工或单工链路 出错恢复、流量控制、分组重新排序 都被赶到更高层去解决了!763.6.4 PPP 协议的组成1992 年制订了 PPP 协议。经过 1993 年和 1994 年的修订，现在的 PPP 协议已成为因特网的正式标准RFC 1661。 PPP 协议有三个组成部分 一个将 IP 数据报封装到串行链路的方法。链路控制协议 LCP (Link Control Protocol)。网络控制

30、协议 NCP (Network Control Protocol)。 773.6.4 PPP协议帧格式标志字段 F = 0 x7E （符号“0 x”表示后面的字符是用十六进制表示。十六进制的 7E 的二进制表示是 01111110）。地址字段 A 只置为 0 xFF。地址字段实际上并不起作用。控制字段 C 通常置为 0 x03，不起作用。PPP 是面向字节的，所有的 PPP 帧的长度都是整数字节。 783.6.4 PPP协议帧格式PPP 有一个 2 个字节的协议字段。当协议字段为 0 x0021 时，PPP 帧的信息字段就是IP 数据报。若为 0 xC021, 则信息字段是 PPP 链路控制数据。若为 0 x8021，则表示这是网络控制数据。 IP 数据