第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用一、链路层功能一、链路层功能要解决的问题 如何在有差错的线路上，进行无差错传输。ISO关于数据链路层的定义 数据链路层的目的是为了提供功能上和规程上的方法，以便建立、维护和释放网络实体间的数据链路。节点node）：网络中的主机host和路由器router称为节点链路link）：通信路径上连接相邻节点的通信信道称为链路。数据链路层协议定义了一条链路的两个节点间交换的数据单元格式，以及节点发送和接收数据单元的动作。第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用数据链路控制规程 为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。数据链路层协议应提供的最基本功能 数据在链路上的正常传输建立、维护和释放） 数据的定界与同步，也处理透明性问题 差错控制 顺序控制 流量控制第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用为网络层提供三种合理的服务 无确认无连接服务，适用于误码率很低的线路，错误恢复留给高层；实时业务大部分局域网 有确认无连接服务，适用于不可靠的信道，如无线网。 有确认有连接服务第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用二、二、 成帧成帧Framing）将比特流分成离散的帧，标识每个帧的起始与结束，将比特流分成离散的帧，标识每个帧的起始与结束，并计算每个帧的校验和。并计算每个帧的校验和。成帧方法：成帧方法：1） 字符计数法字符计数法在帧头中用一个域来表示整个帧的字符个数在帧头中用一个域来表示整个帧的字符个数缺陷：若计数出错，对本帧和后面的帧有影响。缺陷：若计数出错，对本帧和后面的帧有影响。第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用起始字符起始字符 DLE STX，结束字符，结束字符DLE ETX字符填充字符填充缺陷：局限于缺陷：局限于8位字符和位字符和ASCII字符传送。字符传送。用特殊的字符作为帧头和帧尾 如：DLE STX My name is John DLE ETXDLESTX My name isJoneDLEETX10024D79206E616D65206973204A6F6E651003接收方一旦接收方一旦丢失了失了帧信息，只要信息，只要查找找DLE STXDLE STX就可重新确就可重新确定定帧边界界 如果数据中出如果数据中出现首尾字符，首尾字符，则插入重复的定界符插入重复的定界符2 2） 带字符填充的首尾字符定界法带字符填充的首尾字符定界法第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用3 3） 带位填充的首尾标记定界法带位填充的首尾标记定界法u 帧的起始和的起始和结束都用一个特殊的位串束都用一个特殊的位串“01111110”，称，称为标记(flag)。u 采用采用“0比特插入比特插入删除技除技术插入的比特第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用u 只适用于物理层编码有冗余的网络只适用于物理层编码有冗余的网络u 如：如：802802标准的标准的LANLAN，物理层采用曼彻斯特或，物理层采用曼彻斯特或差分曼彻斯特编码差分曼彻斯特编码 用高用高- -低电平对低电平对/ /低低- -高电平高电平对表示对表示1/01/0，高，高- -高高/ /低低- -低电平对不表示数据，低电平对不表示数据，可以用来做定界符。可以用来做定界符。u留意：在很多数据链路协议中，使用字符计留意：在很多数据链路协议中，使用字符计数法和一种其它方法的组合。数法和一种其它方法的组合。4 4） 物理层编码违例法物理层编码违例法第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用三、三、 差错控制差错控制 一般方法：接收方给发送方一个反馈呼应）。一般方法：接收方给发送方一个反馈呼应）。 出错情况出错情况 帧包括发送帧和响应帧出错；帧包括发送帧和响应帧出错； 帧包括发送帧和响应帧丧失帧包括发送帧和响应帧丧失 通过计时器和序号保证每帧最终交给目的网络通过计时器和序号保证每帧最终交给目的网络层仅一次是数据链路层的一个主要功能。层仅一次是数据链路层的一个主要功能。第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用u 差错出现的特点：随机，连续突发差错出现的特点：随机，连续突发burstburst）u 处理差错的两种基本策略处理差错的两种基本策略u使用纠错码：发送方在每个数据块中加入足够使用纠错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。是否有错，并能纠正错误。u使用检错码：发送方在每个数据块中加入足够使用检错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据的冗余信息，使得接收方能够判断接收到的数据是否有错，但不能判断哪里有错。是否有错，但不能判断哪里有错。第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用l 码字字codeword）：一个）：一个帧包括包括m个数据位，个数据位，r个校个校验位，位，n = m + r，则此此n比特比特单元称元称为n位位码字。字。l 海明距离海明距离Hamming distance）：两个）：两个码字之字之间不同的比特位数目。不同的比特位数目。例：0000000000 与0000011111的海明距离为5如果两个码字的海明距离为d，则需要d个单比特错就可以把一个码字转换成另一个码字；为了检查出d个错单比特错），需要使用海明距离为 d + 1 的编码；为了纠正d个错，需要海明距离为 2d + 1 的编码；1） 纠错码第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用l 最最简单的例子是奇偶校的例子是奇偶校验l 在数据后填加一个奇偶位在数据后填加一个奇偶位parity bit）l例：使用偶校例：使用偶校验（“1的个数的个数为偶数）偶数）l10110101101101011l10110001101100010l奇偶校奇偶校验可以用来可以用来检查单个个错误。第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用使用纠错码传数据，效率低，适用于不可能重传的场合；使用纠错码传数据，效率低，适用于不可能重传的场合；大多数情况采用检错码加重传。大多数情况采用检错码加重传。循环冗余码循环冗余码CRC码，多项式编码）码，多项式编码）如：如：110001，可表示成多项式，可表示成多项式 x5 + x4 + 1生成多项式生成多项式G(x)发方、收方事前商定；发方、收方事前商定；生成多项式的高位和低位必须为生成多项式的高位和低位必须为1生成多项式必须比传输信息对应的多项式短。生成多项式必须比传输信息对应的多项式短。CRC码基本思想码基本思想校验和校验和checksum加在帧尾，使带校验和的帧的多项加在帧尾，使带校验和的帧的多项式能被式能被G(x)除尽；收方接收时，用除尽；收方接收时，用G(x)去除它，若有余数，去除它，若有余数，则传输出错。则传输出错。2） 检错码第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用四个多项式已成为国际标准四个多项式已成为国际标准CRC-12 = x12 + x11 + x3 + x2 + x + 1CRC-16 = x16 + x15 + x2 + 1CRC-CCITT = x16 + x12 + x5 + 1CRC-32硬件实现硬件实现CRC校验校验网卡网卡NICNetwork Interface Card完成完成第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用 流量控制流量控制 基于反馈机制基于反馈机制 流量控制主要在传输层实现流量控制主要在传输层实现1XON/XOFF方案。使用一对控制字符实现流量控制。发生过载时，接收方向发送方发送一个XOFF字符，使之暂停发送；状况消除后，再向发送方发送一个XON字符，使之恢复发送。2滑动窗口。利用接收方缓冲区和发送方缓冲区来实现流量控制。通过限制已发送而尚未确认帧的数量，以实现对发送方的控制。 链路层的流量控制策略链路层的流量控制策略第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用u 工作原理工作原理u 发送的信息帧都有一个序号，从发送的信息帧都有一个序号，从0到某个最大到某个最大值，值，0 2n - 1，一般用，一般用n个二进制位表示；个二进制位表示；u 发送端始终保持一个已发送但尚未确认的帧的发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小认的帧的最小编号。发送窗口大小 = 上界上界 - 下下界，大小可变；界，大小可变；四、滑动窗口四、滑动窗口Sliding Window Protocol协议协议第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用u 工作原理工作原理续）u 发送端每送端每发送一个送一个帧，序号取上界，序号取上界值，上界加，上界加1；每接收到一个正确响；每接收到一个正确响应帧，下界加，下界加1；u 接收端有一个接收窗口，大小固定，但不一定接收端有一个接收窗口，大小固定，但不一定与与发送窗口相同。接收窗口的上界表示允送窗口相同。接收窗口的上界表示允许接收接收的序号最大的的序号最大的帧，下界表示希望接收的，下界表示希望接收的帧；u 接收窗口容接收窗口容纳允允许接收的信息接收的信息帧，落在窗口外，落在窗口外的的帧均被均被丢弃。序号等于下界的弃。序号等于下界的帧被正确接收，被正确接收，并并产生一个响生一个响应帧，上界，上界/下界都加下界都加1。接收窗口。接收窗口大小不大小不变。第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用滑动窗口原理示意图设滑动窗口原理示意图设WT=5，WR=3）(a) (b) (c) (d)01234567012345670123456701234567前沿后沿012345670123456701234567前沿01234567后沿(a) (b) (c) (d)发送方发送方接收方接收方第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用三个常见窗口协议三个常见窗口协议p发送窗口WT=1，接收窗口WR=1p一位滑动窗口协议p发送窗口WT=7，接收窗口WR=1p后退n帧的滑动窗口协议p发送窗口WT=4，接收窗口WR=4p选择性重发滑动窗口协议第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用1停等协议一比特滑动窗口协议） 协议特点 窗口大小：N = 1，发送序号和接收序号的取值范围：0，1； 可进行数据双向传输，信息帧中可含有确认信息piggybacking技术）； 信息帧中包括两个序号域：发送序号和接收序号已经正确收到的帧的序号）p 存在问题p能保证无差错传输，但是基于停等方式；p若双方同时开始发送，则会有一半重复帧；p效率低，传输时间长。第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用A发送（0，1，A0） Seq ackA发送A0，seq=0B收到（0，1，A0）B收到A0B发送（0，0，B0）B发送B0，并确认A0A收到（0，0，B0） A收到B0及对A0的确认A发送（1，0，A1） A发送A1及对B0的确认B收到（1，0，A1） B收到A1及对B0的确认B发送（1，1，B1）B发送B1及对A1的确认A收到（1，1，B1） A收到B1及对A1的确认A发送（0，1，A2） A发送A2及对B1的确认B收到（0，1，A2） B收到A2及对B1的确认B发送（0，0，B2）B发送B2及对A2的确认A收到（0，0，B2） A收到B2及对A2的确认A发送（1，0，A3） A发送A3及对B2的确认B收到（1，0，A3） B收到A3及对B2的确认B发送（1，1，B3）停等协议的情况1：运行过程正常第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用A发送（0，1，A0） B发送（0，1，B0）B也已从网络层得到B0B收到（0，1，A0） B以为B0分组A没有收到B发送（0，0，B0）所以B又重复B0分组A收到（0，1，B0） A以为A0分组B没有收到A发送（0，0，A0） 所以A又重复A0分组B收到（0，0，A0） B收到A0及对B0的确认B发送（1，0，B1）B发送B1及对A0的确认A收到（0，0，B0） A收到B0及对A0的确认A发送（1，0，A1） A发送A1及对B0的确认B收到（1，0，A1） B以为B1分组A没有收到B发送（1，1，B1）所以B又重复B1分组A收到（1，0，B1） A以为A1分组B没有收到A发送（1，1，A1） 所以A又重复A1分组B收到（1，1，A1） B发送（0，1，B2）停等协议的情况2：运行过程不正常第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用2） 连续连续ARQ协议协议p为提高传输效率而设计p停等协议的主要问题是信道利用率太低。发送端的等待时间至少是发送端到接收端传播时间的二倍p信道的利用率为：发送时间/来回时间p管道化pipelining）:在等待确认的时间内继续发送p存在的问题：若信道不可靠，使发送端在意识到数据丢失时，已有大量数据到达接收端第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用 例：卫星信道传输速率50kbps，往返传输延迟500ms，若传1000bit的帧，若使用停等协议，则传输一个帧所需时间为：发送时间 + 数据传输延迟 + 确认传输延迟确认帧很短，可忽略发送时间）= 1000bit / 50kbps + 250ms + 250ms = 520ms 信道利用率 = 20 / 520 4% 对一般情况而言若信道带宽b比特/秒，帧长度L比特，往返传输延迟R秒，则信道利用率为 (L/b) / (L/b + R) = L / (L + Rb) 结论： 传输延迟大，信道带宽高，帧短时，信道利用率低。第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用 解决效率的办法解决效率的办法连续发送多帧后再等待确认，称为流水线技术连续发送多帧后再等待确认，称为流水线技术 带来的问题带来的问题信道误码率高时，对坏帧和非坏帧的重传非常多信道误码率高时，对坏帧和非坏帧的重传非常多 两种常见的连续两种常见的连续ARQARQ方法方法 退后退后n n帧帧go back ngo back n） 接收方从出错帧起丢弃所有后继帧；接收窗口为接收方从出错帧起丢弃所有后继帧；接收窗口为1 1 对于出错率较高的信道，浪费带宽。对于出错率较高的信道，浪费带宽。 选择重传选择重传selective repeatselective repeat） 接收窗口大于接收窗口大于1 1，先暂存出错帧的后继帧；，先暂存出错帧的后继帧； 只重传坏帧；对最高序号的帧进行确认；只重传坏帧；对最高序号的帧进行确认；接收窗口较大时，需较大缓冲区。接收窗口较大时，需较大缓冲区。第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用a) 退后n帧协议发送方有流量控制，为重传设缓冲区；发送窗口大小 = 接收窗口接收窗口 第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用选择性重传协议正常工作的情况发送窗口 = 接收窗口 = (MAX_SEQ + 1) / 2增加了否定性确认NAK，当收到一个坏帧，或收到一个非期望的帧，则发一个NAK帧增加了一个辅助定时器，当收到一个正确的帧，而没有可捎带确认的数据帧，当辅助定时器超时，则立即发送一个ACK帧第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用五、常用的数据链路层协议五、常用的数据链路层协议数据链路层协议分类数据链路层协议分类 面向字符的链路层协议面向字符的链路层协议 ISO的的IS1745，基本型传输控制规程及其扩充部，基本型传输控制规程及其扩充部分分BM和和XBM） IBM的二进制同步通信规程的二进制同步通信规程BSC） DEC的数字数据通信报文协议的数字数据通信报文协议DDCMP） PPP第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用p 面向比特的链路层协议面向比特的链路层协议p IBM的的SNA使用的数据链路协议使用的数据链路协议SDLCSynchronous Data Link Control protocol）；）；p ANSI修改修改SDLC，提出，提出ADCCPAdvanced Data Communication Control Procedure）；）；p ISO修改修改SDLC，提出，提出HDLCHigh-level Data Link Control）；）；p CCITT修改修改HDLC，提出，提出LAPLink Access Procedure作为作为X.25网络接口标准的一部分，网络接口标准的一部分，后来改为后来改为LAPB。第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用1） 高高级数据数据链路控制路控制规程程HDLC 1976年，年，ISO提出提出HDLCHigh-level Data Link Control） HDLC的的组成成帧结构构规程元素程元素规程程类型型 使用使用HDLC的的语法可以定法可以定义多种具有不同操作特多种具有不同操作特点的点的链路路层协议。 HDLC的适用范的适用范围计算机算机 计算机算机计算机算机 终端端终端端 终端端第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用p HDLC的基本操作模式的基本操作模式p 正规响应模式正规响应模式 NRMNormal Response Mode）p适用于点点式和多点式两种非平衡构型。只有当主适用于点点式和多点式两种非平衡构型。只有当主站向次站发出探询后，次站才能获得传输帧的许可。站向次站发出探询后，次站才能获得传输帧的许可。p 异步响应模式异步响应模式 ARMAsynchronous Response Mode）p适用于点点式非平衡构型和主站次站式平衡构型。适用于点点式非平衡构型和主站次站式平衡构型。次站可以随时传输帧，不必等待主站的探询。次站可以随时传输帧，不必等待主站的探询。p 异步平衡模式异步平衡模式 ABMAsynchronous Balanced Mode）p适用于通信双方都是组合站的平衡构型，也采用异步适用于通信双方都是组合站的平衡构型，也采用异步响应，双方具有同等能力。响应，双方具有同等能力。第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用HDLC的帧格式888=016801111110地址控制数据校验和01111110帧标志序列即01111110，作为帧的分隔标志，如线路空闲，则用标志序列填充，用位插入方法实现透明传输地址域在总线型多终端情况下，是终端的站号；在点对点的情况下，用来标志命令和响应控制域定义帧的类型、序号等和其它一些功能数据域用户数据，长度任意校验和CRC码，从地址字段到信息字段 第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用2） 点对点协议点对点协议PPP Internet 中的网络互联其中的路由器R之间是通过点对点来连接的 InternetRRSPCPCPCPCRSPCPCPCPCR第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用普通家庭用户接入InternetInternetRSWPCPCServerISPAccess ServerPSTNPCPCMM远程家庭用户通过拨号与远程家庭用户通过拨号与ISP联接联接 第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用pPPP是Internet标准RFC1661 1662 1663） 处理错误监测处理错误监测 支持多种协议支持多种协议IPIP、IPXIPX、DECnetDECnet等）等） 连接时允许协商连接时允许协商IPIP地址，允许动态分配地址，允许动态分配允许身份认证允许身份认证 提供差错校验提供差错校验以帧为单位发送，而不是原始以帧为单位发送，而不是原始IPIP包；包；第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用p 点到点协议 PPP 包括两部分p 链路控制协议LCPLink Control Protocol）p可使用多种物理层服务：modem，HDLC串线，SDH/SONET等p 网络控制协议NCPNetwork Control Protocol）p可支持多种网络层协议p 帧格式与HDLC相似，区别在于PPP是面向字符的，采用字符填充技术第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用p PPP的帧格式的帧格式 PPP的帧格式类似于HDLC，但是面向字符的协议以字节为单位） 1111/2可变可变2/41标志01111110地址11111111控制00000011协议有效载荷校验和标志01111110标志域：固定为01111110，与HDLC相同 地址域：固定为11111111 控制域：缺省为00000011，即无序号帧即毋需确认）协议域：不同的协议不同的代码 载荷域：可变长，缺省最长1500字节 校验和：缺省为2字节，也可为4字节，仅是头部的校验和 第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用p PPP的工作过程的工作过程发送端PPP首先发送LCP帧，以配置和测试数据链路 在LCP建立好数据链路并协调好所选设备之后，发送端PPP发送NCP帧，以选择和配置一个或多个网络协议 当所选的网络层协议配置好后，便可将各网络层协议的分组发送到数据链路上 配置好的链路将一直保持通信状态，直到LCP帧或NCP帧明确提示关闭链路，或有其它的外部事件发生如用户干预等） 第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用p 一次使用一次使用PPP协议的过程协议的过程 初始状态 建立连接：建立成功到，否则到 选项协商：协商成功到，否则到 身份认证：认证成功到，否则到 配置网络：网络配置完后到 数据传输：数据传输完后到 释放链路：回到 第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用3） 以太网环境的点对点协议以太网环境的点对点协议PPPoE p PPPoE 可通过简单桥接设备连接远端接入设备p 可以利用以太网的共享介质特性连接多个用户主机p 是宽带接入需求的产物 PPPoE报文格式：加入的以太网报文头部PPP报文部分校验部分第三章第三章 数据链路层数据链路层计计算算机机网网络络与与应应用用常用数据链路层协议小结 主要数据链路层协议：主要数据链路层协议：HDLC面向比特和面向比特和PPP面向字符）面向字符） HDLC具有三种站，两种构型，三种操作模式具有三种站，两种构型，三种操作模式 X.25 LAPB是是HDLC的子集的子集 PPP 提供差错校验、支持多种协议、允许动态提供差错校验、支持多种协议、允许动态分配分配IP地址、支持认证地址、支持认证 PPP包括两部分：包括两部分：LCP和和NCP PPP帧没有序号域，不使用滑动窗口技术。帧没有序号域，不使用滑动窗口技术。