《第五部分数据链路控制及其协议教学课件》由会员分享,可在线阅读,更多相关《第五部分数据链路控制及其协议教学课件(101页珍藏版)》请在金锄头文库上搜索。
1、壮蝇改辕楚烽奏岭愉狞类鸽雇倾烘横浮乾彦苗逝兼烘鸿帘纸善毒蔼渔喜永第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件第五章数据链路控制及其协议函娇右供唾曰豢骑晶巴汐陇辖射哑十淖吟痘戳碟础八白箭饥看伟思咆匝沽第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件主要内容5.15.1定义和功能定义和功能定义和功能定义和功能5.1.15.1.1定义定义定义定义5.1.25.1.2为网络层提供服务为网络层提供服务为网络层提供服务为网络层提供服务5.1.35.1.3成帧成帧成帧成帧5.1.45.1.4差错控制差错控制差错控制差错控制5.1.55.1.5流量控制流量控
2、制流量控制流量控制5.25.2错误检测和纠正错误检测和纠正错误检测和纠正错误检测和纠正5.2.15.2.1纠错码纠错码纠错码纠错码5.2.25.2.2检错码检错码检错码检错码5.35.3基本的数据链路层协议基本的数据链路层协议基本的数据链路层协议基本的数据链路层协议 5.3.1 5.3.1无约束单工协议无约束单工协议无约束单工协议无约束单工协议 5.3.2 5.3.2单工停等协议单工停等协议单工停等协议单工停等协议 5.3.3 5.3.3有噪声信道的单工协议有噪声信道的单工协议有噪声信道的单工协议有噪声信道的单工协议臻箱罗狮诌筋八翱互礼侈渭锈贵托邻涕哺式崔级变淫抖旱捡磁够拔蚤离教第五部分数据链
3、路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.45.4滑动窗口协议滑动窗口协议滑动窗口协议滑动窗口协议 5.4.1 5.4.1一比特滑动窗口协议一比特滑动窗口协议一比特滑动窗口协议一比特滑动窗口协议 5.4.2 5.4.2退后退后退后退后n n帧协议帧协议帧协议帧协议 5.4.3 5.4.3选择重传协议选择重传协议选择重传协议选择重传协议5.55.5协议说明与验证协议说明与验证协议说明与验证协议说明与验证 5.5.1 5.5.1通信协议中的形式化描述技术通信协议中的形式化描述技术通信协议中的形式化描述技术通信协议中的形式化描述技术 5.5.2 5.5.2有限状态机模型有限状态机
4、模型有限状态机模型有限状态机模型 5.5.3 5.5.3PetriPetri网模型网模型网模型网模型5.65.6常用的数据链路层协议常用的数据链路层协议常用的数据链路层协议常用的数据链路层协议5.6.15.6.1高级数据链路控制规程高级数据链路控制规程高级数据链路控制规程高级数据链路控制规程 HDLC HDLC5.6.25.6.2X.25X.25的链路层协议的链路层协议的链路层协议的链路层协议LAPBLAPB5.6.35.6.3InternetInternet数据链路层协议数据链路层协议数据链路层协议数据链路层协议5.6.45.6.4ATMATM数据链路层协议数据链路层协议数据链路层协议数据链
5、路层协议牺凯艺俯掏使疲惕荡秦代孵篙稍岸搅键懒写翘蜜换蹿爬衷蛤瓦钻形沾辙澄第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.1 定义和功能(1)5.1.1 5.1.1 定义定义定义定义n n要解决的问题要解决的问题要解决的问题要解决的问题 如何在有差错的线路上,进行无差错传输。如何在有差错的线路上,进行无差错传输。如何在有差错的线路上,进行无差错传输。如何在有差错的线路上,进行无差错传输。n nISOISO关于数据链路层的定义关于数据链路层的定义关于数据链路层的定义关于数据链路层的定义 数据链路层的目的是为了提供功能上和规程上的方法,以便建数据链路层的目的是为了提供功能
6、上和规程上的方法,以便建数据链路层的目的是为了提供功能上和规程上的方法,以便建数据链路层的目的是为了提供功能上和规程上的方法,以便建立、维护和释放网络实体间的数据链路。立、维护和释放网络实体间的数据链路。立、维护和释放网络实体间的数据链路。立、维护和释放网络实体间的数据链路。n n结点(结点(结点(结点(nodenode):网络中的主机():网络中的主机():网络中的主机():网络中的主机(hosthost)和路由器)和路由器)和路由器)和路由器(routerrouter)称为结点)称为结点)称为结点)称为结点n n链路(链路(链路(链路(linklink):通信路径上连接相邻结点的通信信道称
7、为):通信路径上连接相邻结点的通信信道称为):通信路径上连接相邻结点的通信信道称为):通信路径上连接相邻结点的通信信道称为链路。链路。链路。链路。n n数据链路层协议定义了一条链路的两个结点间交换的数据数据链路层协议定义了一条链路的两个结点间交换的数据数据链路层协议定义了一条链路的两个结点间交换的数据数据链路层协议定义了一条链路的两个结点间交换的数据单元格式,以及结点发送和接收数据单元的动作。单元格式,以及结点发送和接收数据单元的动作。单元格式,以及结点发送和接收数据单元的动作。单元格式,以及结点发送和接收数据单元的动作。拂霖峙孽武昨吨溅扎啪囱蛰底坑烧诧趁衫锯盲囊立竿汝淮扮特具阻僚作捍第五部分
8、数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.1 定义和功能(2)n n端到端(端到端(端到端(端到端(end to endend to end)与点到点()与点到点()与点到点()与点到点(point to point to pointpoint) 从源结点(从源结点(从源结点(从源结点(source nodesource node)到目的结点)到目的结点)到目的结点)到目的结点(destination nodedestination node)的通信称为端到端通信,通)的通信称为端到端通信,通)的通信称为端到端通信,通)的通信称为端到端通信,通信路径(信路径(信路径(
9、信路径(pathpath)可能由多个链路组成。)可能由多个链路组成。)可能由多个链路组成。)可能由多个链路组成。 在相邻结点间的一条链路上的通信称为点到点通信。在相邻结点间的一条链路上的通信称为点到点通信。在相邻结点间的一条链路上的通信称为点到点通信。在相邻结点间的一条链路上的通信称为点到点通信。n n虚拟数据通路,实际数据通路虚拟数据通路,实际数据通路虚拟数据通路,实际数据通路虚拟数据通路,实际数据通路 Fig. 3-1Fig. 3-1法彦濒卑蜕婶窑盲闷东盐梁霜癣蓑婶耗楼钢蝇帚妊汛贪瓦莽任忆芍冰并麦第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件稿捶块庶甄朋趣馏拧妊坟
10、镁碾共懒挂迂铆续严屏章衙庶玻骨奉很轨特磐谱第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.1 定义和功能(2)n n数据链路控制规程数据链路控制规程数据链路控制规程数据链路控制规程 为使数据能迅速、正确、有效地从发送点到达接收点为使数据能迅速、正确、有效地从发送点到达接收点为使数据能迅速、正确、有效地从发送点到达接收点为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。所采用的控制方式。所采用的控制方式。所采用的控制方式。n n数据链路层协议应提供的最基本功能数据链路层协议应提供的最基本功能数据链路层协议应提供的最基本功能数据链路层协议应提供的最基本功能
11、 数据在数据链路上的正常传输(建立、维护和释放)数据在数据链路上的正常传输(建立、维护和释放)数据在数据链路上的正常传输(建立、维护和释放)数据在数据链路上的正常传输(建立、维护和释放) 定界与同步,也处理透明性问题定界与同步,也处理透明性问题定界与同步,也处理透明性问题定界与同步,也处理透明性问题 差错控制差错控制差错控制差错控制 顺序控制顺序控制顺序控制顺序控制 流量控制流量控制流量控制流量控制酥坦雁杂逾榨缸湃篮医掩弗治少喉争狮妄妇破勺膊匠缴搬厅舞舀具剂辰酣第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.1 定义和功能(3)5.1.2 为网络层提供服务为网络层提
12、供服务n n为网络层提供三种合理的服务为网络层提供三种合理的服务无确认无连接服务,无确认无连接服务,无确认无连接服务,无确认无连接服务,适用于适用于适用于适用于n n误码率很低的线路,错误恢复留给高层;误码率很低的线路,错误恢复留给高层;误码率很低的线路,错误恢复留给高层;误码率很低的线路,错误恢复留给高层;n n实时业务实时业务实时业务实时业务n n大部分局域网大部分局域网大部分局域网大部分局域网有确认无连接服务,有确认无连接服务,有确认无连接服务,有确认无连接服务,适用于不可靠的信道,如无线适用于不可靠的信道,如无线适用于不可靠的信道,如无线适用于不可靠的信道,如无线网。网。网。网。有确认
13、有连接服务有确认有连接服务有确认有连接服务有确认有连接服务她敛颂佯垣天馈柔困霓碑盐种菊搓竣届糊狰且芝厘甚村仲蠕屏矣碟宫郴同第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.1 定义和功能(4)5.1.3 5.1.3 成帧(成帧(成帧(成帧(FramingFraming)n n将比特流分成离散的帧,并计算每个帧的校验和。将比特流分成离散的帧,并计算每个帧的校验和。将比特流分成离散的帧,并计算每个帧的校验和。将比特流分成离散的帧,并计算每个帧的校验和。n n成帧方法:成帧方法:成帧方法:成帧方法: 字符计数法字符计数法字符计数法字符计数法n n在帧头中用一个域来表示整个帧
14、的字符个数在帧头中用一个域来表示整个帧的字符个数在帧头中用一个域来表示整个帧的字符个数在帧头中用一个域来表示整个帧的字符个数n n缺点:若计数出错,对本帧和后面的帧有影响。缺点:若计数出错,对本帧和后面的帧有影响。缺点:若计数出错,对本帧和后面的帧有影响。缺点:若计数出错,对本帧和后面的帧有影响。n nFig. 3-3Fig. 3-3 带字符填充的首尾字符定界法带字符填充的首尾字符定界法带字符填充的首尾字符定界法带字符填充的首尾字符定界法n n起始字符起始字符起始字符起始字符 DLE STX DLE STX,结束字符,结束字符,结束字符,结束字符DLE ETXDLE ETXn n字符填充字符填
15、充字符填充字符填充n nFig. 3-4Fig. 3-4n n缺点:局限于缺点:局限于缺点:局限于缺点:局限于8 8位字符和位字符和位字符和位字符和ASCIIASCII字符传送。字符传送。字符传送。字符传送。蹄沦哇拖谬塔瞳谣螺茄多窿珍引颂玲技傍裂卓椰棺蜀校床适舜郑禾桑翔希第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.1 定义和功能(5) 带位填充的首尾标记定界法带位填充的首尾标记定界法带位填充的首尾标记定界法带位填充的首尾标记定界法n n帧的起始和结束都用一个特殊的位串帧的起始和结束都用一个特殊的位串帧的起始和结束都用一个特殊的位串帧的起始和结束都用一个特殊的位串
16、“ “0111111001111110” ”,称为标记,称为标记,称为标记,称为标记(flag)(flag)n n“ “0 0” ”比特插入删除技术比特插入删除技术比特插入删除技术比特插入删除技术n nFig. 3-5Fig. 3-5 物理层编码违例法物理层编码违例法物理层编码违例法物理层编码违例法n n只适用于物理层编码有冗余的网络只适用于物理层编码有冗余的网络只适用于物理层编码有冗余的网络只适用于物理层编码有冗余的网络n n802 LAN802 LAN:Manchester encoding or Differential Manchester encoding or Differenti
17、al Manchester encoding Manchester encoding 用用用用high-low pair/low-high high-low pair/low-high pairpair表示表示表示表示1/01/0,high-high/low-lowhigh-high/low-low不表示数据,可以用不表示数据,可以用不表示数据,可以用不表示数据,可以用来做定界符。来做定界符。来做定界符。来做定界符。n n注意:在很多数据链路协议中,使用字符计数法注意:在很多数据链路协议中,使用字符计数法注意:在很多数据链路协议中,使用字符计数法注意:在很多数据链路协议中,使用字符计数法和一种
18、其它方法的组合。和一种其它方法的组合。和一种其它方法的组合。和一种其它方法的组合。稻肇嚷狰涩次琐县醇翘八绒渍爬幻蓬烹惦所藤然冠葡掉死齿槽箩嘶龋汹使第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.1 定义和功能(6)5.1.4 5.1.4 差错控制差错控制差错控制差错控制n n一般方法:接收方给发送方一个反馈(响应)。一般方法:接收方给发送方一个反馈(响应)。一般方法:接收方给发送方一个反馈(响应)。一般方法:接收方给发送方一个反馈(响应)。n n出错情况出错情况出错情况出错情况 帧(包括发送帧和响应帧)出错;帧(包括发送帧和响应帧)出错;帧(包括发送帧和响应帧)出错
19、;帧(包括发送帧和响应帧)出错; 帧(包括发送帧和响应帧)丢失帧(包括发送帧和响应帧)丢失帧(包括发送帧和响应帧)丢失帧(包括发送帧和响应帧)丢失n n通过计时器和序号保证每帧最终交给目的网络层通过计时器和序号保证每帧最终交给目的网络层通过计时器和序号保证每帧最终交给目的网络层通过计时器和序号保证每帧最终交给目的网络层仅一次是数据链路层的一个主要功能。仅一次是数据链路层的一个主要功能。仅一次是数据链路层的一个主要功能。仅一次是数据链路层的一个主要功能。5.1.5 5.1.5 流量控制流量控制流量控制流量控制n n基于反馈机制基于反馈机制基于反馈机制基于反馈机制n n流量控制主要在传输层实现流量
20、控制主要在传输层实现流量控制主要在传输层实现流量控制主要在传输层实现拧耸橱萨使胜埋僵灶友晓蔼烬数寅譬匠陛纺毡奇先器瞧凑代踊拐白倡痕层第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.2 错误检测和纠正(1)n n差错出现的特点:随机,连续突发(差错出现的特点:随机,连续突发(差错出现的特点:随机,连续突发(差错出现的特点:随机,连续突发(burstburst)n n处理差错的两种基本策略处理差错的两种基本策略处理差错的两种基本策略处理差错的两种基本策略 使用纠错码:发送方在每个数据块中加入足够的冗余信息,使用纠错码:发送方在每个数据块中加入足够的冗余信息,使用纠错码:
21、发送方在每个数据块中加入足够的冗余信息,使用纠错码:发送方在每个数据块中加入足够的冗余信息,使得接收方能够判断接收到的数据是否有错,并能纠正错误。使得接收方能够判断接收到的数据是否有错,并能纠正错误。使得接收方能够判断接收到的数据是否有错,并能纠正错误。使得接收方能够判断接收到的数据是否有错,并能纠正错误。 使用检错码:发送方在每个数据块中加入足够的冗余信息,使用检错码:发送方在每个数据块中加入足够的冗余信息,使用检错码:发送方在每个数据块中加入足够的冗余信息,使用检错码:发送方在每个数据块中加入足够的冗余信息,使得接收方能够判断接收到的数据是否有错,但不能判断哪使得接收方能够判断接收到的数据
22、是否有错,但不能判断哪使得接收方能够判断接收到的数据是否有错,但不能判断哪使得接收方能够判断接收到的数据是否有错,但不能判断哪里有错。里有错。里有错。里有错。5.2.15.2.1纠错码纠错码纠错码纠错码n n码字(码字(码字(码字(codewordcodeword):一个帧包括):一个帧包括):一个帧包括):一个帧包括mm个数据位,个数据位,个数据位,个数据位,r r个个个个校验位,校验位,校验位,校验位,n = m + rn = m + r,则此,则此,则此,则此n n比特单元称为比特单元称为比特单元称为比特单元称为n n位码字。位码字。位码字。位码字。n n海明距离(海明距离(海明距离(海
23、明距离(Hamming distanceHamming distance):两个码字之间):两个码字之间):两个码字之间):两个码字之间不同的比特位数目。不同的比特位数目。不同的比特位数目。不同的比特位数目。壬戏赋拨御焰陋炙系妆挞泄荔孟竿屡知舀够筛戏进肄蔓疫嘻茄字妊牙陶亚第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.2 错误检测和纠正(2) 例:例:例:例:0000000000 0000000000 与与与与00000111110000011111的海明距离为的海明距离为的海明距离为的海明距离为5 5 如果两个码字的海明距离为如果两个码字的海明距离为如果两个码字的
24、海明距离为如果两个码字的海明距离为d d,则需要,则需要,则需要,则需要d d个单比特错就可以把一个个单比特错就可以把一个个单比特错就可以把一个个单比特错就可以把一个码字转换成另一个码字;码字转换成另一个码字;码字转换成另一个码字;码字转换成另一个码字; 为了检查出为了检查出为了检查出为了检查出d d个错(单比特错),需要使用海明距离为个错(单比特错),需要使用海明距离为个错(单比特错),需要使用海明距离为个错(单比特错),需要使用海明距离为 d + 1 d + 1 的的的的编码;编码;编码;编码; 为了纠正为了纠正为了纠正为了纠正d d个错,需要使用海明距离为个错,需要使用海明距离为个错,需
25、要使用海明距离为个错,需要使用海明距离为 2d + 1 2d + 1 的编码;的编码;的编码;的编码;n n最简单的例子是奇偶校验,在数据后填加一个奇偶位最简单的例子是奇偶校验,在数据后填加一个奇偶位最简单的例子是奇偶校验,在数据后填加一个奇偶位最简单的例子是奇偶校验,在数据后填加一个奇偶位(parity bitparity bit) 例:使用偶校验(例:使用偶校验(例:使用偶校验(例:使用偶校验(“ “1 1” ”的个数为偶数)的个数为偶数)的个数为偶数)的个数为偶数)10110101101101011011010111011010111011000110110001101100010101
26、100010 奇偶校验可以用来检查单个错误。奇偶校验可以用来检查单个错误。奇偶校验可以用来检查单个错误。奇偶校验可以用来检查单个错误。率厦贵赶清客鼠犁姥仍绦纤锤洛录牡岿虑营烃鹿框囱甄揣盏占他衫湖牢奔第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.2 错误检测和纠正(3)n n设计纠错码设计纠错码设计纠错码设计纠错码 要求:要求:要求:要求:mm个信息位,个信息位,个信息位,个信息位,r r个校验位,纠正单比特错;个校验位,纠正单比特错;个校验位,纠正单比特错;个校验位,纠正单比特错; 对对对对2 2mm个有效信息中任何一个,有个有效信息中任何一个,有个有效信息中任何
27、一个,有个有效信息中任何一个,有n n个与其距离为个与其距离为个与其距离为个与其距离为1 1的无效码字,的无效码字,的无效码字,的无效码字,因此有:因此有:因此有:因此有:(n + 1) 2(n + 1) 2mm 2 2n n 利用利用利用利用 n = m + r n = m + r,得到,得到,得到,得到 (m + r + 1) (m + r + 1) 2 2r r 给定给定给定给定mm,利用该式可以得出校正单比特误码的校验位数目的下,利用该式可以得出校正单比特误码的校验位数目的下,利用该式可以得出校正单比特误码的校验位数目的下,利用该式可以得出校正单比特误码的校验位数目的下界界界界n n海
28、明码海明码海明码海明码 码位从左边开始编号,从码位从左边开始编号,从码位从左边开始编号,从码位从左边开始编号,从“ “1 1” ”开始;开始;开始;开始; 位号为位号为位号为位号为2 2的幂的位是校验位,其余是信息位;的幂的位是校验位,其余是信息位;的幂的位是校验位,其余是信息位;的幂的位是校验位,其余是信息位; 每个校验位使得包括自己在内的一些位的奇偶值为偶数(或奇数)每个校验位使得包括自己在内的一些位的奇偶值为偶数(或奇数)每个校验位使得包括自己在内的一些位的奇偶值为偶数(或奇数)每个校验位使得包括自己在内的一些位的奇偶值为偶数(或奇数)。 为看清数据位为看清数据位为看清数据位为看清数据位
29、k k对哪些校验位有影响,将对哪些校验位有影响,将对哪些校验位有影响,将对哪些校验位有影响,将k k写成写成写成写成2 2的幂的和。的幂的和。的幂的和。的幂的和。 例:例:例:例:11 = 1 + 2 + 811 = 1 + 2 + 8副虫馈咏羡乘跌截姐扰揪哗合卧唁驱龚戍敛姜粉谰付雁纵抒逸蒸育明箍搂第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.2 错误检测和纠正(4)n n海明码工作过程海明码工作过程海明码工作过程海明码工作过程 每个码字到来前,接收方计数器清零;每个码字到来前,接收方计数器清零;每个码字到来前,接收方计数器清零;每个码字到来前,接收方计数器清零;
30、 接收方检查每个校验位接收方检查每个校验位接收方检查每个校验位接收方检查每个校验位k (k = 1, 2, 4 )k (k = 1, 2, 4 )的奇偶值是否正的奇偶值是否正的奇偶值是否正的奇偶值是否正确;确;确;确; 若第若第若第若第 k k 位奇偶值不对,计数器加位奇偶值不对,计数器加位奇偶值不对,计数器加位奇偶值不对,计数器加 k k; 所有校验位检查完后,若计数器值为所有校验位检查完后,若计数器值为所有校验位检查完后,若计数器值为所有校验位检查完后,若计数器值为0 0,则码字有效;若计数,则码字有效;若计数,则码字有效;若计数,则码字有效;若计数器值为器值为器值为器值为mm,则第,则第
31、,则第,则第mm位出错。位出错。位出错。位出错。 若校验位若校验位若校验位若校验位1 1、2 2、8 8出错,则第出错,则第出错,则第出错,则第1111位变反。位变反。位变反。位变反。 Fig. 3-6Fig. 3-6n n使用海明码纠正突发错误使用海明码纠正突发错误使用海明码纠正突发错误使用海明码纠正突发错误 可采用可采用可采用可采用k k个码字(个码字(个码字(个码字(n = m + rn = m + r)组成)组成)组成)组成 k k n n 矩阵,按列发送,矩阵,按列发送,矩阵,按列发送,矩阵,按列发送,接收方恢复成接收方恢复成接收方恢复成接收方恢复成 k k n n 矩阵矩阵矩阵矩阵
32、 krkr个校验位,个校验位,个校验位,个校验位,kmkm个数据位,可纠正最多为个数据位,可纠正最多为个数据位,可纠正最多为个数据位,可纠正最多为k k个的突发性连续个的突发性连续个的突发性连续个的突发性连续比特错。比特错。比特错。比特错。勃弗浩诞垦风欲樱师虐豺醋堕碧糖因盗邯瓣临乓搅卤左程罕暇安宗有踞咙第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件1 2 3 4 5 6 7 8 9 10 11 1 1 1 1 1 2 2 2 2 2 4 4 4 8 8 8煽窃剃棒腮梢抨待潍靖夺筹建疵峪吼陈水撬咕撩骑宋蚀啮头疾宣硅港兽邹第五部分数据链路控制及其协议教学课件第五部分数据链
33、路控制及其协议教学课件5.2 错误检测和纠正(5)5.2.2 5.2.2 检错码检错码检错码检错码n n使用纠错码传数据,效率低,适用于不可能重传的场合;使用纠错码传数据,效率低,适用于不可能重传的场合;使用纠错码传数据,效率低,适用于不可能重传的场合;使用纠错码传数据,效率低,适用于不可能重传的场合;大多数情况采用检错码加重传。大多数情况采用检错码加重传。大多数情况采用检错码加重传。大多数情况采用检错码加重传。n n循环冗余码(循环冗余码(循环冗余码(循环冗余码(CRCCRC码,多项式编码)码,多项式编码)码,多项式编码)码,多项式编码) 110001110001,表示成多项式,表示成多项式
34、,表示成多项式,表示成多项式 x x5 5 + x + x4 4 + 1 + 1n n生成多项式生成多项式生成多项式生成多项式G(x)G(x) 发方、收方事前商定;发方、收方事前商定;发方、收方事前商定;发方、收方事前商定; 生成多项式的高位和低位必须为生成多项式的高位和低位必须为生成多项式的高位和低位必须为生成多项式的高位和低位必须为1 1 生成多项式必须比传输信息对应的多项式短。生成多项式必须比传输信息对应的多项式短。生成多项式必须比传输信息对应的多项式短。生成多项式必须比传输信息对应的多项式短。n nCRCCRC码基本思想码基本思想码基本思想码基本思想 校验和(校验和(校验和(校验和(c
35、hecksumchecksum)加在帧尾,使带校验和的帧的多项式能被)加在帧尾,使带校验和的帧的多项式能被)加在帧尾,使带校验和的帧的多项式能被)加在帧尾,使带校验和的帧的多项式能被G(x)G(x)除尽;收方接收时,用除尽;收方接收时,用除尽;收方接收时,用除尽;收方接收时,用G(x)G(x)去除它,若有余数,则传输出去除它,若有余数,则传输出去除它,若有余数,则传输出去除它,若有余数,则传输出错。错。错。错。岁帘除揽鹰嘘蹈娥丽妖发啮佩灶官申框吊参从那竞郡妖饶哥孝绵阂陕沧郴第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.2 错误检测和纠正(6)n n校验和计算算法校
36、验和计算算法校验和计算算法校验和计算算法 设设设设G(x)G(x)为为为为 r r 阶,在阶,在阶,在阶,在帧的末尾加帧的末尾加帧的末尾加帧的末尾加 r r 个个个个0 0,使帧为,使帧为,使帧为,使帧为m + rm + r位,位,位,位,相应多项式为相应多项式为相应多项式为相应多项式为x xr rM(x)M(x); 按模按模按模按模2 2除法用对应于除法用对应于除法用对应于除法用对应于G(x)G(x)的位串去除对应于的位串去除对应于的位串去除对应于的位串去除对应于x xr rM(x)M(x)的位的位的位的位串;串;串;串; 按模按模按模按模2 2减法从对应于减法从对应于减法从对应于减法从对应
37、于x xr rM(x)M(x)的位串中减去余数(等于或小的位串中减去余数(等于或小的位串中减去余数(等于或小的位串中减去余数(等于或小于于于于r r位),结果就是要传送的带校验和的多项式位),结果就是要传送的带校验和的多项式位),结果就是要传送的带校验和的多项式位),结果就是要传送的带校验和的多项式T(x)T(x)。 Fig. 3-7Fig. 3-7n nCRCCRC的检错能力的检错能力的检错能力的检错能力 发送:发送:发送:发送:T(x)T(x);接收:;接收:;接收:;接收:T(x) + E(x)T(x) + E(x); 余数余数余数余数(T(x) + E(x) / G(x) = 0 +
38、(T(x) + E(x) / G(x) = 0 + 余数余数余数余数(E(x) / (E(x) / G(x)G(x) 若若若若 余数余数余数余数(E(x) / G(x) = 0(E(x) / G(x) = 0,则差错不能发现;否则,可,则差错不能发现;否则,可,则差错不能发现;否则,可,则差错不能发现;否则,可以发现。以发现。以发现。以发现。愧篮垂嚣辖玛矢畔峪格旷琢就梢验馒涧用芍伊枪中配阿爱庐径有饱榆裙储第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.2 错误检测和纠正(7) 如果只有单比特错,即如果只有单比特错,即如果只有单比特错,即如果只有单比特错,即E(x)
39、= xE(x) = xi i,而,而,而,而G(x)G(x)中至少有两项,中至少有两项,中至少有两项,中至少有两项,余数余数余数余数(E(x) / G(x)(E(x) / G(x) 0 0,所以可以查出单比特错;,所以可以查出单比特错;,所以可以查出单比特错;,所以可以查出单比特错; 如果发生两个孤立单比特错,即如果发生两个孤立单比特错,即如果发生两个孤立单比特错,即如果发生两个孤立单比特错,即E(x) = xE(x) = xi i + x + xj j = x = xj j (x (xi-ji-j + + 1)1),假定,假定,假定,假定G(x)G(x)不能被不能被不能被不能被x x整除,那
40、么能够发现两个比特错的充分条整除,那么能够发现两个比特错的充分条整除,那么能够发现两个比特错的充分条整除,那么能够发现两个比特错的充分条件是:件是:件是:件是:x xk k + 1 + 1不能被不能被不能被不能被G(x)G(x)整除整除整除整除 (k (k i - j) i - j); 如果有奇数个比特错,即如果有奇数个比特错,即如果有奇数个比特错,即如果有奇数个比特错,即E(x)E(x)包括奇数个项,包括奇数个项,包括奇数个项,包括奇数个项,G(x)G(x)选选选选(x + 1)(x + 1)的倍数就能查出奇数个比特错;的倍数就能查出奇数个比特错;的倍数就能查出奇数个比特错;的倍数就能查出奇
41、数个比特错; 具有具有具有具有r r个校验位的多项式能检查出所有长度个校验位的多项式能检查出所有长度个校验位的多项式能检查出所有长度个校验位的多项式能检查出所有长度 r r 的突发性差错。长的突发性差错。长的突发性差错。长的突发性差错。长度为度为度为度为k k的突发性连续差错(并不表示有的突发性连续差错(并不表示有的突发性连续差错(并不表示有的突发性连续差错(并不表示有k k个单比特错)可表示为个单比特错)可表示为个单比特错)可表示为个单比特错)可表示为 x xi i (x(xk-1k-1 + + 1) + + 1),若,若,若,若G(x)G(x)包括包括包括包括x x0 0项,且项,且项,且
42、项,且 k - 1 k - 1小于小于小于小于G(x)G(x)的阶,的阶,的阶,的阶,则则则则 余数余数余数余数(E(x) / G(x) (E(x) / G(x) 0; 0; 如果突发差错长度为如果突发差错长度为如果突发差错长度为如果突发差错长度为 r + 1 r + 1,当且仅当突发差错和,当且仅当突发差错和,当且仅当突发差错和,当且仅当突发差错和G(x)G(x)一样时,一样时,一样时,一样时, 余数余数余数余数( (E(x) / G(x) E(x) / G(x) = 0= 0,概率为,概率为,概率为,概率为1/21/2r-1r-1; ; 长度大于长度大于长度大于长度大于 r + 1 r +
43、 1的突发差错或几个较短的突发差错发生后,坏帧的突发差错或几个较短的突发差错发生后,坏帧的突发差错或几个较短的突发差错发生后,坏帧的突发差错或几个较短的突发差错发生后,坏帧被接收的概率为被接收的概率为被接收的概率为被接收的概率为 1/2 1/2r r。儿铸蓄喀邹莱龚等乡救插擎弓磅宗座潞舰县闻熏哎靶减浮俯辗稳径歪邢部第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.2 错误检测和纠正(8)n n四个多项式已成为国际标准四个多项式已成为国际标准CRC-12 CRC-12 = x= x1212 + x + x1111 + x + x3 3 + x + x2 2 + x +
44、1+ x + 1CRC-16 CRC-16 = x= x1616 + x + x1515 + x + x2 2 + 1 + 1CRC-CCITT CRC-CCITT = x= x1616 + x + x1212 + x + x5 5 + 1 + 1CRC-32CRC-32n n硬件实现硬件实现CRC校验校验网卡网卡网卡网卡NICNIC(Network Interface CardNetwork Interface Card)饲旺铜纱做区逃玩勋她刘驳啮试学锹测矩瘟定峻雏暑填谩意些与窖骂茅绝第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.3 基本的数据链路层协议(1)5
45、.3.1 无约束单工协议(无约束单工协议(An Unrestricted Simplex Protocol)n n工作在理想情况,几个前提:工作在理想情况,几个前提:单工传输单工传输单工传输单工传输发送方无休止工作(要发送的信息无限多)发送方无休止工作(要发送的信息无限多)发送方无休止工作(要发送的信息无限多)发送方无休止工作(要发送的信息无限多)接收方无休止工作(缓冲区无限大)接收方无休止工作(缓冲区无限大)接收方无休止工作(缓冲区无限大)接收方无休止工作(缓冲区无限大)通信线路(信道)不损坏或丢失信息帧通信线路(信道)不损坏或丢失信息帧通信线路(信道)不损坏或丢失信息帧通信线路(信道)不损
46、坏或丢失信息帧n n工作过程工作过程发送程序发送程序发送程序发送程序: :取数据,构成帧,发送帧;取数据,构成帧,发送帧;取数据,构成帧,发送帧;取数据,构成帧,发送帧;接收程序:等待,接收帧,送数据给高层接收程序:等待,接收帧,送数据给高层接收程序:等待,接收帧,送数据给高层接收程序:等待,接收帧,送数据给高层Fig. 3-9Fig. 3-9莎鸯政说孪献缠吝众荷啪聪胞局韩庇憾茎深鸭撵欢详钎娟聊皖世绷宵涩至第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件康英樊治仲人蝎凄奉拆隔披兄汗永群砂剖浙事泵统律椎珠赊币绦树岗逾芹第五部分数据链路控制及其协议教学课件第五部分数据链路控
47、制及其协议教学课件5.3 基本的数据链路层协议(2)5.3.2 5.3.2 单工停等协议(单工停等协议(单工停等协议(单工停等协议(A Simplex Stop-and-A Simplex Stop-and-Wait ProtocolWait Protocol)n n增加约束条件:接收方不能无休止接收。增加约束条件:接收方不能无休止接收。增加约束条件:接收方不能无休止接收。增加约束条件:接收方不能无休止接收。n n解决办法:接收方每收到一个帧后,给发送方回解决办法:接收方每收到一个帧后,给发送方回解决办法:接收方每收到一个帧后,给发送方回解决办法:接收方每收到一个帧后,给发送方回送一个响应。送
48、一个响应。送一个响应。送一个响应。n n工作过程工作过程工作过程工作过程 发送程序:取数据,成帧,发送帧,等待响应帧;发送程序:取数据,成帧,发送帧,等待响应帧;发送程序:取数据,成帧,发送帧,等待响应帧;发送程序:取数据,成帧,发送帧,等待响应帧; 接收程序:等待,接收帧,送数据给高层,回送响应接收程序:等待,接收帧,送数据给高层,回送响应接收程序:等待,接收帧,送数据给高层,回送响应接收程序:等待,接收帧,送数据给高层,回送响应帧。帧。帧。帧。 Fig. 3-10Fig. 3-10赂硷婆碍晰枣棒硕窘竿蔬惺疲凹彬逝漾显苗谬谓乳赠集收瓤韵孰榴灰惧出第五部分数据链路控制及其协议教学课件第五部分数
49、据链路控制及其协议教学课件桌衍努拖垛叙盗媚洽棘帖躬搂危氓吕犀斧攘孙杯美舔究里斌客预村诽俱碍第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.3 基本的数据链路层协议(3)5.3.3 5.3.3 有噪声信道的单工协议(有噪声信道的单工协议(有噪声信道的单工协议(有噪声信道的单工协议(A Simplex Protocol A Simplex Protocol for a Noisy Channelfor a Noisy Channel)n n增加约束条件:信道(线路)有差错,信息帧可能损坏或增加约束条件:信道(线路)有差错,信息帧可能损坏或增加约束条件:信道(线路)有差错
50、,信息帧可能损坏或增加约束条件:信道(线路)有差错,信息帧可能损坏或丢失。丢失。丢失。丢失。n n解决办法:出错重传。解决办法:出错重传。解决办法:出错重传。解决办法:出错重传。n n带来的问题:带来的问题:带来的问题:带来的问题: 什么时候重传什么时候重传什么时候重传什么时候重传 定时定时定时定时 响应帧损坏怎么办(重复帧)响应帧损坏怎么办(重复帧)响应帧损坏怎么办(重复帧)响应帧损坏怎么办(重复帧) 发送帧头中放入序号发送帧头中放入序号发送帧头中放入序号发送帧头中放入序号 为了使帧头精简,序号取多少位为了使帧头精简,序号取多少位为了使帧头精简,序号取多少位为了使帧头精简,序号取多少位 1
51、1位位位位n n发方在发下一个帧之前等待一个肯定确认的协议叫做发方在发下一个帧之前等待一个肯定确认的协议叫做发方在发下一个帧之前等待一个肯定确认的协议叫做发方在发下一个帧之前等待一个肯定确认的协议叫做PARPAR(Positive Acknowledgement with Positive Acknowledgement with RetransmissionRetransmission)或)或)或)或ARQARQ(Automatic Repeat Automatic Repeat reQuestreQuest)谎缨疮污卸堂饱袍恬赏毫铝积篡蔓龋搞闷备毕旋拟辖团歼行驰生痹犀杯恶第五部分数据链路控
52、制及其协议教学课件第五部分数据链路控制及其协议教学课件5.3 基本的数据链路层协议(4)n n工作过程工作过程工作过程工作过程 Fig. 3-11Fig. 3-11n n注意协议注意协议注意协议注意协议3 3的漏洞的漏洞的漏洞的漏洞 由于确认帧中没有序号,超时时间不能太短,否则协议失败。因由于确认帧中没有序号,超时时间不能太短,否则协议失败。因由于确认帧中没有序号,超时时间不能太短,否则协议失败。因由于确认帧中没有序号,超时时间不能太短,否则协议失败。因此假设协议此假设协议此假设协议此假设协议3 3的发送和接收严格交替进行。的发送和接收严格交替进行。的发送和接收严格交替进行。的发送和接收严格交
53、替进行。 Fig. 3-11Fig. 3-11(与教材不同)的实现是正确的,确认帧有序号(与教材不同)的实现是正确的,确认帧有序号(与教材不同)的实现是正确的,确认帧有序号(与教材不同)的实现是正确的,确认帧有序号发送接收001ACKACK固并的味纪持敏孔淌冗柏战赴罪斗美盗垂欣筏搽砌苛贫举亡沉摧蔫旋眶波第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件足镰汐夏褐堑堡则辱耪弥闺固亭懦杀屯攒匀练忻梢王任样寇拘巧妮钥炬学第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.4 滑动窗口协议(1)n n单工单工单工单工 全双工全双工全双工全双工n n捎带捎带
54、捎带捎带/ /载答(载答(载答(载答(piggybackingpiggybacking):暂时延迟待发):暂时延迟待发):暂时延迟待发):暂时延迟待发确认,以便附加在下一个待发数据帧的技术。确认,以便附加在下一个待发数据帧的技术。确认,以便附加在下一个待发数据帧的技术。确认,以便附加在下一个待发数据帧的技术。 优点:充分利用信道带宽,减少帧的数目意味着减少优点:充分利用信道带宽,减少帧的数目意味着减少优点:充分利用信道带宽,减少帧的数目意味着减少优点:充分利用信道带宽,减少帧的数目意味着减少“ “帧到达帧到达帧到达帧到达” ”中断;中断;中断;中断; 带来的问题:复杂。带来的问题:复杂。带来的
55、问题:复杂。带来的问题:复杂。n n本节的三个协议统称滑动窗口协议,都能在实际本节的三个协议统称滑动窗口协议,都能在实际本节的三个协议统称滑动窗口协议,都能在实际本节的三个协议统称滑动窗口协议,都能在实际(非理想)环境下正常工作,区别仅在于效率、(非理想)环境下正常工作,区别仅在于效率、(非理想)环境下正常工作,区别仅在于效率、(非理想)环境下正常工作,区别仅在于效率、复杂性和对缓冲区的要求。复杂性和对缓冲区的要求。复杂性和对缓冲区的要求。复杂性和对缓冲区的要求。揉读骗铺挟屎验讫逛混氮兆惨较瞒锣艳唱灯胁沉所帜春阻泳蚜萄妥护熄棒第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学
56、课件5.4 滑动窗口协议(2)n n滑动窗口协议(滑动窗口协议(滑动窗口协议(滑动窗口协议(Sliding Window ProtocolSliding Window Protocol)工作原)工作原)工作原)工作原理:理:理:理: 发送的信息帧都有一个序号,从发送的信息帧都有一个序号,从发送的信息帧都有一个序号,从发送的信息帧都有一个序号,从0 0到某个最大值,到某个最大值,到某个最大值,到某个最大值,0 20 2n n - 1 - 1,一般用一般用一般用一般用n n个二进制位表示;个二进制位表示;个二进制位表示;个二进制位表示; 发送端始终保持一个已发送但尚未确认的帧的序号表,称为发送发送
57、端始终保持一个已发送但尚未确认的帧的序号表,称为发送发送端始终保持一个已发送但尚未确认的帧的序号表,称为发送发送端始终保持一个已发送但尚未确认的帧的序号表,称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号,下界表示窗口。发送窗口的上界表示要发送的下一个帧的序号,下界表示窗口。发送窗口的上界表示要发送的下一个帧的序号,下界表示窗口。发送窗口的上界表示要发送的下一个帧的序号,下界表示未得到确认的帧的最小编号。发送窗口大小未得到确认的帧的最小编号。发送窗口大小未得到确认的帧的最小编号。发送窗口大小未得到确认的帧的最小编号。发送窗口大小 = = 上界上界上界上界 - - 下界,大小下界,大小下界
58、,大小下界,大小可变;可变;可变;可变; 发送端每发送一个帧,序号取上界值,上界加发送端每发送一个帧,序号取上界值,上界加发送端每发送一个帧,序号取上界值,上界加发送端每发送一个帧,序号取上界值,上界加1 1;每接收到一个正;每接收到一个正;每接收到一个正;每接收到一个正确响应帧,下界加确响应帧,下界加确响应帧,下界加确响应帧,下界加1 1; 接收端有一个接收窗口,大小固定,但不一定与发送窗口相同。接收端有一个接收窗口,大小固定,但不一定与发送窗口相同。接收端有一个接收窗口,大小固定,但不一定与发送窗口相同。接收端有一个接收窗口,大小固定,但不一定与发送窗口相同。接收窗口的上界表示允许接收的序
59、号最大的帧,下界表示希望接接收窗口的上界表示允许接收的序号最大的帧,下界表示希望接接收窗口的上界表示允许接收的序号最大的帧,下界表示希望接接收窗口的上界表示允许接收的序号最大的帧,下界表示希望接收的帧;收的帧;收的帧;收的帧; 接收窗口容纳允许接收的信息帧,落在窗口外的帧均被丢弃。序接收窗口容纳允许接收的信息帧,落在窗口外的帧均被丢弃。序接收窗口容纳允许接收的信息帧,落在窗口外的帧均被丢弃。序接收窗口容纳允许接收的信息帧,落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收,并产生一个响应帧,上界、下界都号等于下界的帧被正确接收,并产生一个响应帧,上界、下界都号等于下界的帧被正确接收,并产生一个
60、响应帧,上界、下界都号等于下界的帧被正确接收,并产生一个响应帧,上界、下界都加加加加1 1。接收窗口大小不变。接收窗口大小不变。接收窗口大小不变。接收窗口大小不变。 Fig. 3-12Fig. 3-12肋嚷淬造榆熔替率拙束书殴尖童挎篮努施旬唆蔬个奢夫隙身插泡盗比卒腊第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件沽池趁丘书湖欺冗尿景促鸽牵中彻增工私瀑先呻痘略残湍垣拦曹导唉扩吻第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.4 滑动窗口协议(3)5.4.15.4.1一比特滑动窗口协议(一比特滑动窗口协议(一比特滑动窗口协议(一比特滑动窗口协议(
61、A One Bit A One Bit Sliding Window ProtocolSliding Window Protocol)n n协议特点协议特点协议特点协议特点 窗口大小:窗口大小:窗口大小:窗口大小:N = 1N = 1,发送序号和接收序号的取值范围:,发送序号和接收序号的取值范围:,发送序号和接收序号的取值范围:,发送序号和接收序号的取值范围:0 0,1 1; 可进行数据双向传输,信息帧中可含有确认信息可进行数据双向传输,信息帧中可含有确认信息可进行数据双向传输,信息帧中可含有确认信息可进行数据双向传输,信息帧中可含有确认信息(piggybackingpiggybacking技
62、术);技术);技术);技术); 信息帧中包括两个序号域:发送序号和接收序号(已信息帧中包括两个序号域:发送序号和接收序号(已信息帧中包括两个序号域:发送序号和接收序号(已信息帧中包括两个序号域:发送序号和接收序号(已经正确收到的帧的序号)经正确收到的帧的序号)经正确收到的帧的序号)经正确收到的帧的序号)n n工作过程工作过程工作过程工作过程 Fig. 3-13Fig. 3-13郧谜椿植技同珍笨夜坟孝卸游倒默舀闹抢昆菊撞绩嗡碾茸陋殴乎裙售躲食第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件衣陀站歹厨啪柳剑炙毋届宁抓陡清霸辩廓杏迫孩巴顽烦铸雏激拨诣启凋悸第五部分数据链路控制
63、及其协议教学课件第五部分数据链路控制及其协议教学课件癣踪择贤囊笋载管泊槛笑豺点磁呕厉吓往纯壬项供渣河米战爷瞄肢贸推远第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.4滑动窗口协议(4)存在问题能保证无差错传输,但是基于停等方式;若双方同时开始发送,则会有一半重复帧;Fig. 3-14(书上图有误)效率低,传输时间长。倡哄逃囊答啥擞漓镶鹤部缨创特哉携垢匡疲模闰耐涯宛八承箱麻赋刃仰芍第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件渣衡亩谷勇量悉憾尹悔搔哈寺攻总黄锑歧孟隋梧阐擎活每鞍漆舔秃隘妆恋第五部分数据链路控制及其协议教学课件第五部分数据链路控
64、制及其协议教学课件5.4 滑动窗口协议(5)5.4.2 5.4.2 退后退后退后退后n n帧协议(帧协议(帧协议(帧协议(A Protocol Using Go A Protocol Using Go Back nBack n)n n为提高传输效率而设计为提高传输效率而设计为提高传输效率而设计为提高传输效率而设计 例:例:例:例:n n卫星信道传输速率卫星信道传输速率卫星信道传输速率卫星信道传输速率50kbps50kbps,往返传输延迟,往返传输延迟,往返传输延迟,往返传输延迟500ms500ms,若传,若传,若传,若传1000bit1000bit的帧,使用协议的帧,使用协议的帧,使用协议的帧
65、,使用协议4 4,则传输一个帧所需时间为:,则传输一个帧所需时间为:,则传输一个帧所需时间为:,则传输一个帧所需时间为: 发送时间发送时间发送时间发送时间 + + 信息信道延迟信息信道延迟信息信道延迟信息信道延迟 + + 确认信道延迟(确认帧很短,确认信道延迟(确认帧很短,确认信道延迟(确认帧很短,确认信道延迟(确认帧很短,忽略发送时间)忽略发送时间)忽略发送时间)忽略发送时间)= 1000bit / 50kbps + 250ms + = 1000bit / 50kbps + 250ms + 250ms = 520ms250ms = 520msn n信道利用率信道利用率信道利用率信道利用率 =
66、 20 / 520 = 20 / 520 4% 4% 一般情况一般情况一般情况一般情况n n信道带宽信道带宽信道带宽信道带宽b b比特比特比特比特/ /秒,帧长度秒,帧长度秒,帧长度秒,帧长度L L比特,往返传输延迟比特,往返传输延迟比特,往返传输延迟比特,往返传输延迟RR秒,则秒,则秒,则秒,则信道利用率为信道利用率为信道利用率为信道利用率为 ( (L L/ /b b) / () / (L L/ /b b + + RR) = ) = L L / ( / (L L + + RbRb) ) 结论结论结论结论n n传输延迟大,信道带宽高,帧短时,信道利用率低。传输延迟大,信道带宽高,帧短时,信道利
67、用率低。传输延迟大,信道带宽高,帧短时,信道利用率低。传输延迟大,信道带宽高,帧短时,信道利用率低。乒略底嘻凰僚咯酬裸登荷戚旺柄漫奋突肥校窒电同肪怪皋滁若凯隧斜彭眉第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.4 滑动窗口协议(6)解决办法解决办法解决办法解决办法n n连续发送多帧后再等待确认,称为流水线技术连续发送多帧后再等待确认,称为流水线技术连续发送多帧后再等待确认,称为流水线技术连续发送多帧后再等待确认,称为流水线技术(pipeliningpipelining)。)。)。)。带来的问题带来的问题带来的问题带来的问题n n信道误码率高时,对损坏帧和非损坏帧的
68、重传非常信道误码率高时,对损坏帧和非损坏帧的重传非常信道误码率高时,对损坏帧和非损坏帧的重传非常信道误码率高时,对损坏帧和非损坏帧的重传非常多多多多n n两种基本方法两种基本方法退后退后退后退后n n帧(帧(帧(帧(go back ngo back n)n n接收方从出错帧起丢弃所有后继帧;接收方从出错帧起丢弃所有后继帧;接收方从出错帧起丢弃所有后继帧;接收方从出错帧起丢弃所有后继帧;n n接收窗口为接收窗口为接收窗口为接收窗口为1 1;n n对于出错率较高的信道,浪费带宽。对于出错率较高的信道,浪费带宽。对于出错率较高的信道,浪费带宽。对于出错率较高的信道,浪费带宽。n nFig. 3-15
69、(a)Fig. 3-15(a)红施赞浊无盒趟氯烫晚缘别鹰妄戈掷菏颐十手溯跟婶练脚篓翅骏响夫轧更第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.4 滑动窗口协议(7)选择重传(选择重传(选择重传(选择重传(selective repeatselective repeat)n n接收窗口大于接收窗口大于接收窗口大于接收窗口大于1 1,先暂存出错帧的后继帧;,先暂存出错帧的后继帧;,先暂存出错帧的后继帧;,先暂存出错帧的后继帧;n n只重传坏帧;只重传坏帧;只重传坏帧;只重传坏帧;n n对最高序号的帧进行确认;对最高序号的帧进行确认;对最高序号的帧进行确认;对最高序号的帧
70、进行确认;n n接收窗口较大时,需较大缓冲区。接收窗口较大时,需较大缓冲区。接收窗口较大时,需较大缓冲区。接收窗口较大时,需较大缓冲区。n nFig. 3-15(b)Fig. 3-15(b) 注意:注意:注意:注意:Fig. 3-15(b)Fig. 3-15(b)中可能出现的错误中可能出现的错误中可能出现的错误中可能出现的错误眺汗仟沃携倒专浮认深简褐察邱针梳练广杀筛若击奴测遣呵酒曙枢冯啮伞第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件播泉眯湍徽饮坠砾成妻尸癣轴按靡沃柜釉当烬禽尧谚油缨痴申弃肛惦脑娱第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件
71、5.4 滑动窗口协议(8)n n退后退后退后退后n n帧协议帧协议帧协议帧协议 发送方有流量控制,为重传设缓冲;发送方有流量控制,为重传设缓冲;发送方有流量控制,为重传设缓冲;发送方有流量控制,为重传设缓冲;n n发送窗口未满,发送窗口未满,发送窗口未满,发送窗口未满,EnableNetworkLayerEnableNetworkLayern n发送窗口满,发送窗口满,发送窗口满,发送窗口满,DisableNetworkLayerDisableNetworkLayer 发送窗口大小发送窗口大小发送窗口大小发送窗口大小 基本操作模式基本操作模式基本操作模式基本操作模式 基本帧种类基本帧种类基本帧
72、种类基本帧种类 1212种任选功能种任选功能种任选功能种任选功能 得到协议得到协议得到协议得到协议唐俭幸冻森悦番撒家枫恃血烘峻雍阂燃涛本怒筐承络表掸年暮刹瞥权钒幻第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件娟虽皆说辩砧喊镍奢捻岿氨霄冉闽剂屹躇怠癣募贫问迪必冻支律闲帐张瞳第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.6 常用的数据链路层协议(12)5.6.2 X.255.6.2 X.25的链路层协议的链路层协议的链路层协议的链路层协议LAPBLAPBn nX.25X.25协议协议协议协议 分组级,分组级,分组级,分组级,PLPPLP 帧级
73、,帧级,帧级,帧级,X.25 LAPX.25 LAP(Link Access ProcedureLink Access Procedure),),),),X.25 X.25 LAPBLAPB(BalancedBalanced) 物理级,物理级,物理级,物理级,X.21X.21n n“ “X.25X.25协议规程使用协议规程使用协议规程使用协议规程使用HDLCHDLC规程的原理和术语规程的原理和术语规程的原理和术语规程的原理和术语” ”n nX.25 LAPX.25 LAP:HDLCHDLC非平衡规程帧的基本清单非平衡规程帧的基本清单非平衡规程帧的基本清单非平衡规程帧的基本清单 + + 任选功任
74、选功任选功任选功能能能能2 2、8 8、1212,也可组成主站,也可组成主站,也可组成主站,也可组成主站 次站式平衡规程。次站式平衡规程。次站式平衡规程。次站式平衡规程。n nX.25 LAPBX.25 LAPB:HDLCHDLC组合站平衡规程帧的基本清单组合站平衡规程帧的基本清单组合站平衡规程帧的基本清单组合站平衡规程帧的基本清单 + + 任选功能任选功能任选功能任选功能2 2、8 8、1111、1212。n n因此,因此,因此,因此,X.25 LAPX.25 LAP、LAPBLAPB是是是是HDLCHDLC的子集。的子集。的子集。的子集。临脏痴馅舷华块览维呼同娟崔遁睬超攀媳磐牢性课蚊薄弛暑
75、答窘公粕拉排第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.6 常用的数据链路层协议(13)n nX.25的帧格式与的帧格式与HDLC完全相同完全相同n nX.25链路级的命令和响应链路级的命令和响应辣迄椎霞剃吵汪扮券铺透邹蚕稚札翅阿藏歇彬心蠢伪屏措懈譬莎夫游宦垮第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.6 常用的数据链路层协议(14)n nX.25 LAPB的各种检错和纠错措施的各种检错和纠错措施a a 帧格式上采用帧格式上采用帧格式上采用帧格式上采用CRCCRC校验,只检错,不纠错,丢校验,只检错,不纠错,丢校验,只检错,不纠错
76、,丢校验,只检错,不纠错,丢弃出错帧;弃出错帧;弃出错帧;弃出错帧;b b 设立超时机制,计时器设立超时机制,计时器设立超时机制,计时器设立超时机制,计时器超时重传,重传超时重传,重传超时重传,重传超时重传,重传NN次,则向上层协议报告。次,则向上层协议报告。次,则向上层协议报告。次,则向上层协议报告。超时机制用来检错,重传用来纠错。超时机制用来检错,重传用来纠错。超时机制用来检错,重传用来纠错。超时机制用来检错,重传用来纠错。c c 帧序号帧序号帧序号帧序号若接收方发现帧序号错,就发拒绝帧给发送方,发送若接收方发现帧序号错,就发拒绝帧给发送方,发送若接收方发现帧序号错,就发拒绝帧给发送方,发
77、送若接收方发现帧序号错,就发拒绝帧给发送方,发送方重传,既检错也纠错。方重传,既检错也纠错。方重传,既检错也纠错。方重传,既检错也纠错。d d 采用采用采用采用P/FP/F位来进行校验指示位来进行校验指示位来进行校验指示位来进行校验指示发送置为发送置为发送置为发送置为 P P 的命令帧,等待置为的命令帧,等待置为的命令帧,等待置为的命令帧,等待置为 F F 的响应帧,能及的响应帧,能及的响应帧,能及的响应帧,能及时发现远程数据站是否收到命令帧。时发现远程数据站是否收到命令帧。时发现远程数据站是否收到命令帧。时发现远程数据站是否收到命令帧。规程规定:规程规定:规程规定:规程规定:a a 必须使用
78、;必须使用;必须使用;必须使用;b, c, d b, c, d 组合使用。组合使用。组合使用。组合使用。唐蜂腥昭瘁擅颠挣在浆额傣决历冈翘茁擅竹培壹掉梁把正七惫企换锦剥蛔第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.6 常用的数据链路层协议(15)5.6.3 Internet5.6.3 Internet数据链路层协议数据链路层协议数据链路层协议数据链路层协议n n点到点通信的两种主要情形点到点通信的两种主要情形点到点通信的两种主要情形点到点通信的两种主要情形 路由器到路由器(路由器到路由器(路由器到路由器(路由器到路由器(router-router leased l
79、ine router-router leased line connectionconnection) 通过通过通过通过modemmodem拨号上网,连到路由器或接入服务器拨号上网,连到路由器或接入服务器拨号上网,连到路由器或接入服务器拨号上网,连到路由器或接入服务器(Access ServerAccess Server)()()()(dial-up host-router dial-up host-router connectionconnection)潮块闭驭草候说陋贼胺左伶戌册能黍滓虾臃媚残桥邹阀懈撰爪潜洼只梅剖第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.
80、6 常用的数据链路层协议(16)n nSLIP Serial Line IPSLIP Serial Line IP 19841984年,年,年,年,Rick AdamsRick Adams提出,提出,提出,提出,RFC1055RFC1055,发送原,发送原,发送原,发送原始始始始IPIP包,用一个标记字节来定界,采用字符填充技术;包,用一个标记字节来定界,采用字符填充技术;包,用一个标记字节来定界,采用字符填充技术;包,用一个标记字节来定界,采用字符填充技术; 新版本提供新版本提供新版本提供新版本提供TCPTCP和和和和IPIP头压缩技术,头压缩技术,头压缩技术,头压缩技术,RFC 1144R
81、FC 1144 存在的问题存在的问题存在的问题存在的问题n n不提供差错校验不提供差错校验不提供差错校验不提供差错校验n n只支持只支持只支持只支持IPIPn nIPIP地址不能动态分配地址不能动态分配地址不能动态分配地址不能动态分配n n不提供认证不提供认证不提供认证不提供认证n n多种版本并存,互连困难多种版本并存,互连困难多种版本并存,互连困难多种版本并存,互连困难幽昔楷引抓巾晾尚擞翌瓮傲捎诊颂执陪醛隘愧芬贤诊味偏枯纪惹壳候筏挥第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.6 常用的数据链路层协议(17)n n点到点协议点到点协议点到点协议点到点协议 PPP
82、 Point-to-Point Protocol PPP Point-to-Point Protocol RFC 1661RFC 1661,RFC 1662RFC 1662,RFC 1663RFC 1663 与与与与SLIPSLIP相比,相比,相比,相比,PPPPPP有很大的提高,提供差错校验、支持多种协有很大的提高,提供差错校验、支持多种协有很大的提高,提供差错校验、支持多种协有很大的提高,提供差错校验、支持多种协议、允许动态分配议、允许动态分配议、允许动态分配议、允许动态分配IPIP地址、支持认证等。地址、支持认证等。地址、支持认证等。地址、支持认证等。 以帧为单位发送,而不是原始以帧为单
83、位发送,而不是原始以帧为单位发送,而不是原始以帧为单位发送,而不是原始IPIP包;包;包;包; 包括两部分包括两部分包括两部分包括两部分n n链路控制协议链路控制协议链路控制协议链路控制协议LCPLCP(Link Control ProtocolLink Control Protocol) 可使用多种物理层服务:可使用多种物理层服务:可使用多种物理层服务:可使用多种物理层服务:modemmodem,HDLCHDLC串线,串线,串线,串线,SDH/SONETSDH/SONET等等等等n n网络控制协议网络控制协议网络控制协议网络控制协议NCPNCP(Network Control Protoco
84、lNetwork Control Protocol) 可支持多种网络层协议可支持多种网络层协议可支持多种网络层协议可支持多种网络层协议 帧格式与帧格式与帧格式与帧格式与HDLCHDLC相似,区别在于相似,区别在于相似,区别在于相似,区别在于PPPPPP是面向字符的,采用字符填是面向字符的,采用字符填是面向字符的,采用字符填是面向字符的,采用字符填充技术充技术充技术充技术啄耶敛高儡吠饯同啤夜稍御众母怀宇寨镭肖绍崩搪蝇雁语涛窘猩镍讽墅敬第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.6 常用的数据链路层协议(18)n n标记域:标记域:标记域:标记域:011111100
85、1111110,字符填充;,字符填充;,字符填充;,字符填充;n n地址域:地址域:地址域:地址域:1111111111111111n n控制域:缺省值为控制域:缺省值为控制域:缺省值为控制域:缺省值为0000001100000011,表示无序号帧,不提供使用,表示无序号帧,不提供使用,表示无序号帧,不提供使用,表示无序号帧,不提供使用序号和确认的可靠传输;不可靠线路上,也可使用有序号的可序号和确认的可靠传输;不可靠线路上,也可使用有序号的可序号和确认的可靠传输;不可靠线路上,也可使用有序号的可序号和确认的可靠传输;不可靠线路上,也可使用有序号的可靠传输。靠传输。靠传输。靠传输。n n协议域:
86、指示净负荷中是何种包,缺省大小为协议域:指示净负荷中是何种包,缺省大小为协议域:指示净负荷中是何种包,缺省大小为协议域:指示净负荷中是何种包,缺省大小为2 2个字节。个字节。个字节。个字节。n n净负荷域:变长,缺省为净负荷域:变长,缺省为净负荷域:变长,缺省为净负荷域:变长,缺省为15001500字节;字节;字节;字节;n n校验和域:校验和域:校验和域:校验和域:2 2或或或或4 4个字节个字节个字节个字节 总结:总结:总结:总结:PPPPPP具有多协议成帧机制,可以在具有多协议成帧机制,可以在具有多协议成帧机制,可以在具有多协议成帧机制,可以在modem, HDLC modem, HDL
87、C bit-serial lines, SDH/SONETbit-serial lines, SDH/SONET等物理层上运行,支持等物理层上运行,支持等物理层上运行,支持等物理层上运行,支持差错检测、选项协商和包头压缩功能,并具有利用差错检测、选项协商和包头压缩功能,并具有利用差错检测、选项协商和包头压缩功能,并具有利用差错检测、选项协商和包头压缩功能,并具有利用HDLCHDLC帧帧帧帧进行可靠传输的可选功能。进行可靠传输的可选功能。进行可靠传输的可选功能。进行可靠传输的可选功能。吐疟莎灰痉附岩差雾舅们螺近掺杨支中纫青茬懦喘残取用瘪洒途泽堰称擞第五部分数据链路控制及其协议教学课件第五部分数据
88、链路控制及其协议教学课件5.6 常用的数据链路层协议(19)PPPPPP链路链路链路链路 up / down up / down 过程(简单状态图)过程(简单状态图)过程(简单状态图)过程(简单状态图)惫诛嘴讲钒汞钻窝娠啃锥咖义货莎美直南画鞋骑席赠凸汰蝇埋峨吁止粕疲第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件5.6 常用的数据链路层协议(20) LCPLCP用来在用来在用来在用来在ESTABLISHESTABLISH状态协商数据链路协议选项,并不状态协商数据链路协议选项,并不状态协商数据链路协议选项,并不状态协商数据链路协议选项,并不关心选项内容,而是提供一种协商机
89、制,并且提供检测链路关心选项内容,而是提供一种协商机制,并且提供检测链路关心选项内容,而是提供一种协商机制,并且提供检测链路关心选项内容,而是提供一种协商机制,并且提供检测链路质量的方法。质量的方法。质量的方法。质量的方法。RFC 1661 RFC 1661 定义了定义了定义了定义了1111种种种种LCPLCP帧类型:帧类型:帧类型:帧类型:蓖浊吨硅抖执仙逛抿撬戮垦馅让愧封果聊考松缚皆喂株瞩胞及充澄视烛警第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件小结n n介绍三种主要数据链路层协议:介绍三种主要数据链路层协议:介绍三种主要数据链路层协议:介绍三种主要数据链路层协议
90、:HDLCHDLC、LAPBLAPB(面向比特)和(面向比特)和(面向比特)和(面向比特)和PPPPPP(面向字符)(面向字符)(面向字符)(面向字符)n nHDLCHDLC具有具有具有具有三种站,两种构型,三种操作模式三种站,两种构型,三种操作模式三种站,两种构型,三种操作模式三种站,两种构型,三种操作模式n nX.25 LAPBX.25 LAPB是是是是HDLCHDLC的子集的子集的子集的子集n nPPP PPP 提供差错校验、支持多种协议、允许动态分提供差错校验、支持多种协议、允许动态分提供差错校验、支持多种协议、允许动态分提供差错校验、支持多种协议、允许动态分配配配配IPIP地址、支持认证地址、支持认证地址、支持认证地址、支持认证n nPPPPPP包括两部分:包括两部分:包括两部分:包括两部分:LCPLCP和和和和NCPNCPn nPPPPPP帧没有序号域,不使用滑动窗口技术。帧没有序号域,不使用滑动窗口技术。帧没有序号域,不使用滑动窗口技术。帧没有序号域,不使用滑动窗口技术。琐讽己感焙瞻露跌注沸郝耀颁绕对骗昏垄西账云吵轧捷韦涸害慰抱馅曙轿第五部分数据链路控制及其协议教学课件第五部分数据链路控制及其协议教学课件