第五章 数据链路控制及其协议 - 华北水利水电学院.ppt

第五章数据链路控制及其协议,,主要内容,5.1定义和功能5.1.1定义5.1.2为网络层提供服务5.1.3成帧5.1.4差错控制5.1.5流量控制5.2错误检测和纠正5.2.1纠错码5.2.2检错码5.3基本的数据链路层协议5.3.1无约束单工协议5.3.2单工停等协议5.3.3有噪声信道的单工协议,,5.4滑动窗口协议5.4.1一比特滑动窗口协议5.4.2退后n帧协议5.4.3选择重传协议5.5协议说明与验证5.5.1通信协议中的形式化描述技术5.5.2有限状态机模型5.5.3Petri网模型5.6常用的数据链路层协议5.6.1高级数据链路控制规程HDLC5.6.2X.25的链路层协议LAPB5.6.3Internet数据链路层协议5.6.4ATM数据链路层协议,5.1定义和功能（1）,5.1.1定义要解决的问题如何在有差错的线路上，进行无差错传输。ISO关于数据链路层的定义数据链路层的目的是为了提供功能上和规程上的方法，以便建立、维护和释放网络实体间的数据链路。结点（node）网络中的主机（host）和路由器（router）称为结点链路（link）通信路径上连接相邻结点的通信信道称为链路。数据链路层协议定义了一条链路的两个结点间交换的数据单元格式，以及结点发送和接收数据单元的动作。,5.1定义和功能（2）,端到端（endtoend）与点到点（pointtopoint）从源结点（sourcenode）到目的结点（destinationnode）的通信称为端到端通信，通信路径（path）可能由多个链路组成。在相邻结点间的一条链路上的通信称为点到点通信。虚拟数据通路，实际数据通路Fig.3-1,5.1定义和功能（2）,数据链路控制规程为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。数据链路层协议应提供的最基本功能数据在数据链路上的正常传输（建立、维护和释放）定界与同步，也处理透明性问题差错控制顺序控制流量控制,5.1定义和功能（3）,5.1.2为网络层提供服务为网络层提供三种合理的服务无确认无连接服务，适用于误码率很低的线路，错误恢复留给高层；实时业务大部分局域网有确认无连接服务，适用于不可靠的信道，如无线网。有确认有连接服务,5.1定义和功能（4）,5.1.3成帧（Framing）将比特流分成离散的帧，并计算每个帧的校验和。成帧方法字符计数法在帧头中用一个域来表示整个帧的字符个数缺点若计数出错，对本帧和后面的帧有影响。Fig.3-3带字符填充的首尾字符定界法起始字符DLESTX，结束字符DLEETX字符填充Fig.3-4缺点局限于8位字符和ASCII字符传送。,5.1定义和功能（5）,带位填充的首尾标记定界法帧的起始和结束都用一个特殊的位串“01111110”，称为标记flag“0”比特插入删除技术Fig.3-5物理层编码违例法只适用于物理层编码有冗余的网络802LANManchesterencodingorDifferentialManchesterencoding用high-lowpair/low-highpair表示1/0，high-high/low-low不表示数据，可以用来做定界符。注意在很多数据链路协议中，使用字符计数法和一种其它方法的组合。,5.1定义和功能（6）,5.1.4差错控制一般方法接收方给发送方一个反馈（响应）。出错情况帧（包括发送帧和响应帧）出错；帧（包括发送帧和响应帧）丢失通过计时器和序号保证每帧最终交给目的网络层仅一次是数据链路层的一个主要功能。5.1.5流量控制基于反馈机制流量控制主要在传输层实现,5.2错误检测和纠正（1）,差错出现的特点随机，连续突发（burst）处理差错的两种基本策略使用纠错码发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。使用检错码发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，但不能判断哪里有错。5.2.1纠错码码字（codeword）一个帧包括m个数据位，r个校验位，nmr，则此n比特单元称为n位码字。海明距离（Hammingdistance）两个码字之间不同的比特位数目。,5.2错误检测和纠正（2）,例0000000000与0000011111的海明距离为5如果两个码字的海明距离为d，则需要d个单比特错就可以把一个码字转换成另一个码字；为了检查出d个错（单比特错），需要使用海明距离为d1的编码；为了纠正d个错，需要使用海明距离为2d1的编码；最简单的例子是奇偶校验，在数据后填加一个奇偶位（paritybit）例使用偶校验（“1”的个数为偶数）1011010110110101110110001101100010奇偶校验可以用来检查单个错误。,5.2错误检测和纠正（3）,设计纠错码要求m个信息位，r个校验位，纠正单比特错；对2m个有效信息中任何一个，有n个与其距离为1的无效码字，因此有n12m2n利用nmr，得到mr12r给定m，利用该式可以得出校正单比特误码的校验位数目的下界海明码码位从左边开始编号，从“1”开始；位号为2的幂的位是校验位，其余是信息位；每个校验位使得包括自己在内的一些位的奇偶值为偶数（或奇数）。为看清数据位k对哪些校验位有影响，将k写成2的幂的和。例11128,5.2错误检测和纠正（4）,海明码工作过程每个码字到来前，接收方计数器清零；接收方检查每个校验位kk1,2,4的奇偶值是否正确；若第k位奇偶值不对，计数器加k；所有校验位检查完后，若计数器值为0，则码字有效；若计数器值为m，则第m位出错。若校验位1、2、8出错，则第11位变反。Fig.3-6使用海明码纠正突发错误可采用k个码字（nmr）组成kn矩阵，按列发送，接收方恢复成kn矩阵kr个校验位，km个数据位，可纠正最多为k个的突发性连续比特错。,12345678910111111122222444888,5.2错误检测和纠正（5）,5.2.2检错码使用纠错码传数据，效率低，适用于不可能重传的场合；大多数情况采用检错码加重传。循环冗余码（CRC码，多项式编码）110001，表示成多项式x5x41生成多项式Gx发方、收方事前商定；生成多项式的高位和低位必须为1生成多项式必须比传输信息对应的多项式短。CRC码基本思想校验和（checksum）加在帧尾，使带校验和的帧的多项式能被Gx除尽；收方接收时，用Gx去除它，若有余数，则传输出错。,5.2错误检测和纠正（6）,校验和计算算法设Gx为r阶，在帧的末尾加r个0，使帧为mr位，相应多项式为xrMx；按模2除法用对应于Gx的位串去除对应于xrMx的位串；按模2减法从对应于xrMx的位串中减去余数（等于或小于r位），结果就是要传送的带校验和的多项式Tx。Fig.3-7CRC的检错能力发送Tx；接收TxEx；余数TxEx/Gx0余数Ex/Gx若余数Ex/Gx0，则差错不能发现；否则，可以发现。,5.2错误检测和纠正（7）,如果只有单比特错，即Exxi，而Gx中至少有两项，余数Ex/Gx0，所以可以查出单比特错；如果发生两个孤立单比特错，即Exxixjxjxi-j1，假定Gx不能被x整除，那么能够发现两个比特错的充分条件是xk1不能被Gx整除ki-j；如果有奇数个比特错，即Ex包括奇数个项，Gx选x1的倍数就能查出奇数个比特错；具有r个校验位的多项式能检查出所有长度r的突发性差错。长度为k的突发性连续差错（并不表示有k个单比特错）可表示为xixk-11，若Gx包括x0项，且k-1小于Gx的阶，则余数Ex/Gx0;如果突发差错长度为r1，当且仅当突发差错和Gx一样时，余数Ex/Gx0，概率为1/2r-1;长度大于r1的突发差错或几个较短的突发差错发生后，坏帧被接收的概率为1/2r。,5.2错误检测和纠正（8）,四个多项式已成为国际标准CRC-12x12x11x3x2x1CRC-16x16x15x21CRC-CCITTx16x12x51CRC-32硬件实现CRC校验网卡NIC（NetworkInterfaceCard）,5.3基本的数据链路层协议（1）,5.3.1无约束单工协议（AnUnrestrictedSimplexProtocol）工作在理想情况，几个前提单工传输发送方无休止工作（要发送的信息无限多）接收方无休止工作（缓冲区无限大）通信线路（信道）不损坏或丢失信息帧工作过程发送程序取数据，构成帧，发送帧；接收程序等待，接收帧，送数据给高层Fig.3-9,5.3基本的数据链路层协议（2）,5.3.2单工停等协议（ASimplexStop-and-WaitProtocol）增加约束条件接收方不能无休止接收。解决办法接收方每收到一个帧后，给发送方回送一个响应。工作过程发送程序取数据，成帧，发送帧，等待响应帧；接收程序等待，接收帧，送数据给高层，回送响应帧。Fig.3-10,5.3基本的数据链路层协议（3）,5.3.3有噪声信道的单工协议（ASimplexProtocolforaNoisyChannel）增加约束条件信道（线路）有差错，信息帧可能损坏或丢失。解决办法出错重传。带来的问题什么时候重传定时响应帧损坏怎么办（重复帧）发送帧头中放入序号为了使帧头精简，序号取多少位1位发方在发下一个帧之前等待一个肯定确认的协议叫做PAR（PositiveAcknowledgementwithRetransmission）或ARQ（AutomaticRepeatreQuest）,5.3基本的数据链路层协议（4）,工作过程Fig.3-11注意协议3的漏洞由于确认帧中没有序号，超时时间不能太短，否则协议失败。因此假设协议3的发送和接收严格交替进行。Fig.3-11（与教材不同）的实现是正确的，确认帧有序号,发送,接收,,,,,,0,0,1,ACK,ACK,,5.4滑动窗口协议（1）,单工全双工捎带/载答（piggybacking）暂时延迟待发确认，以便附加在下一个待发数据帧的技术。优点充分利用信道带宽，减少帧的数目意味着减少“帧到达”中断；带来的问题复杂。本节的三个协议统称滑动窗口协议，都能在实际（非理想）环境下正常工作，区别仅在于效率、复杂性和对缓冲区的要求。,5.4滑动窗口协议（2）,滑动窗口协议（SlidingWindowProtocol）工作原理发送的信息帧都有一个序号，从0到某个最大值，02n-1，一般用n个二进制位表示；发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小上界-下界，大小可变；发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1；接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧；接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。Fig.3-12,5.4滑动窗口协议（3）,5.4.1一比特滑动窗口协议（AOneBitSlidingWindowProtocol）协议特点窗口大小N1，发送序号和接收序号的取值范围0，1；可进行数据双向传输，信息帧中可含有确认信息（piggybacking技术）；信息帧中包括两个序号域发送序号和接收序号（已经正确收到的帧的序号）工作过程Fig.3-13,5.4滑动窗口协议（4）,存在问题能保证无差错传输，但是基于停等方式；若双方同时开始发送，则会有一半重复帧；Fig.3-14（书上图有误）效率低，传输时间长。,5.4滑动窗口协议（5）,5.4.2退后n帧协议（AProtocolUsingGoBackn）为提高传输效率而设计例卫星信道传输速率50kbps，往返传输延迟500ms，若传1000bit的帧，使用协议4，则传输一个帧所需时间为发送时间信息信道延迟确认信道延迟（确认帧很短，忽略发送时间）1000bit/50kbps250ms250ms520ms信道利用率20/5204一般情况信道带宽b比特/秒，帧长度L比特，往返传输延迟R秒，则信道利用率为L/b/L/bRL/LRb结论传输延迟大，信道带宽高，帧短时，信道利用率低。,5.4滑动窗口协议（6）,解决办法连续发送多帧后再等待确认，称为流水线技术（pipelining）。带来的问题信道误码率高时，对损坏帧和非损坏帧的重传非常多两种基本方法退后n帧（gobackn）接收方从出错帧起丢弃所有后继帧；接收窗口为1；对于出错率较高的信道，浪费带宽。Fig.3-15a,5.4滑动窗口协议（7）,选择重传（selectiverepeat）接收窗口大于1，先暂存出错帧的后继帧；只重传坏帧；对最高序号的帧进行确认；接收窗口较大时，需较大缓冲区。Fig.3-15b注意Fig.3-15b中可能出现的错误,5.4滑动窗口协议（8）,退后n帧协议发送方有流量控制，为重传设缓冲；发送窗口未满，EnableNetworkLayer发送窗口满，DisableNetworkLayer发送窗口大小基本操作模式基本帧种类12种任选功能得到协议,5.6常用的数据链路层协议（12）,5.6.2X.25的链路层协议LAPBX.25协议分组级，PLP帧级，X.25LAP（LinkAccessProcedure），X.25LAPB（Balanced）物理级，X.21“X.25协议规程使用HDLC规程的原理和术语”X.25LAPHDLC非平衡规程帧的基本清单任选功能2、8、12，也可组成主站次站式平衡规程。X.25LAPBHDLC组合站平衡规程帧的基本清单任选功能2、8、11、12。因此，X.25LAP、LAPB是HDLC的子集。,5.6常用的数据链路层协议（13）,X.25的帧格式与HDLC完全相同X.25链路级的命令和响应,5.6常用的数据链路层协议（14）,X.25LAPB的各种检错和纠错措施a帧格式上采用CRC校验，只检错，不纠错，丢弃出错帧；b设立超时机制，计时器超时重传，重传N次，则向上层协议报告。超时机制用来检错，重传用来纠错。c帧序号若接收方发现帧序号错，就发拒绝帧给发送方，发送方重传，既检错也纠错。d采用P/F位来进行校验指示发送置为P的命令帧，等待置为F的响应帧，能及时发现远程数据站是否收到命令帧。规程规定a必须使用；b,c,d组合使用。,5.6常用的数据链路层协议（15）,5.6.3Internet数据链路层协议点到点通信的两种主要情形路由器到路由器（router-routerleasedlineconnection）通过modem拨号上网，连到路由器或接入服务器（AccessServer）（dial-uphost-routerconnection）,5.6常用的数据链路层协议（16）,SLIPSerialLineIP1984年，RickAdams提出，RFC1055，发送原始IP包，用一个标记字节来定界，采用字符填充技术；新版本提供TCP和IP头压缩技术，RFC1144存在的问题不提供差错校验只支持IPIP地址不能动态分配不提供认证多种版本并存，互连困难,5.6常用的数据链路层协议（17）,点到点协议PPPPoint-to-PointProtocolRFC1661，RFC1662，RFC1663与SLIP相比，PPP有很大的提高，提供差错校验、支持多种协议、允许动态分配IP地址、支持认证等。以帧为单位发送，而不是原始IP包；包括两部分链路控制协议LCP（LinkControlProtocol）可使用多种物理层服务modem，HDLC串线，SDH/SONET等网络控制协议NCP（NetworkControlProtocol）可支持多种网络层协议帧格式与HDLC相似，区别在于PPP是面向字符的，采用字符填充技术,5.6常用的数据链路层协议（18）,标记域01111110，字符填充；地址域11111111控制域缺省值为00000011，表示无序号帧，不提供使用序号和确认的可靠传输；不可靠线路上，也可使用有序号的可靠传输。协议域指示净负荷中是何种包，缺省大小为2个字节。净负荷域变长，缺省为1500字节；校验和域2或4个字节总结PPP具有多协议成帧机制，可以在modem,HDLCbit-seriallines,SDH/SONET等物理层上运行，支持差错检测、选项协商和包头压缩功能，并具有利用HDLC帧进行可靠传输的可选功能。,5.6常用的数据链路层协议（19）,PPP链路up/down过程（简单状态图）,5.6常用的数据链路层协议（20）,LCP用来在ESTABLISH状态协商数据链路协议选项，并不关心选项内容，而是提供一种协商机制，并且提供检测链路质量的方法。RFC1661定义了11种LCP帧类型,小结,介绍三种主要数据链路层协议HDLC、LAPB（面向比特）和PPP（面向字符）HDLC具有三种站，两种构型，三种操作模式X.25LAPB是HDLC的子集PPP提供差错校验、支持多种协议、允许动态分配IP地址、支持认证PPP包括两部分LCP和NCPPPP帧没有序号域，不使用滑动窗口技术。,