《第3章数据链路层》由会员分享，可在线阅读，更多相关《第3章数据链路层（166页珍藏版）》请在金锄头文库上搜索。
1、Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 1 / 169第第3章章 数据链路层数据链路层v定义和功能定义和功能v数据帧的组成数据帧的组成v可靠性传输可靠性传输v数据链路层示例数据链路层示例御御镰镰贼贼柳柳铺铺筋筋轨轨陨陨疹疹曳曳揽揽消消冤冤蛙蛙饭饭符符粒粒迎迎泽泽亮亮盯盯煮煮燥燥粉粉纠纠哮哮邹邹琳琳段段割割俄俄徒徒第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 2 / 169v为网络层提供一个较好的服务接口为网络层提供一个较好的服务接口
2、v为网络层提供可靠的传输服务为网络层提供可靠的传输服务数据链路层的定义数据链路层的定义数据链路层的上层是网络层，数据链路层数据链路层的上层是网络层，数据链路层将借助于物理层为网络层提供服务将借助于物理层为网络层提供服务数据链路层的协议数据单元（数据链路层的协议数据单元（PDU）是帧）是帧幻幻看看躁躁摩摩垦垦睬睬决决暴暴垣垣吼吼赂赂昼昼强强质质授授访访狠狠窃窃笼笼特特焰焰盼盼龋龋犯犯连连豫豫碰碰绚绚儡儡蓉蓉效效筷筷第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 3 / 169数据链路层的功
3、能数据链路层的功能v数据链路层的任务是把网络层的数字数据组合成帧，并数据链路层的任务是把网络层的数字数据组合成帧，并加上一定的校验码后交物理层加上一定的校验码后交物理层v物理层用不同的信号表示二进制数据位，从而把帧用一物理层用不同的信号表示二进制数据位，从而把帧用一段连续的信号串表示并传送到目的主机段连续的信号串表示并传送到目的主机v目的主机的物理层将信号还原成比特串交数据链路层，目的主机的物理层将信号还原成比特串交数据链路层，井数据链路层确认正确后送到网络层井数据链路层确认正确后送到网络层v数据链路层为源和目的主机的网络层之间提供一条可靠数据链路层为源和目的主机的网络层之间提供一条可靠的数据
4、链路的数据链路笺笺典典夹夹慎慎苦苦颁颁掏掏嫡嫡典典霸霸水水新新性性奠奠粳粳翔翔界界饿饿油油狰狰漫漫黍黍迎迎进进魔魔陋陋拆拆潮潮雨雨蚤蚤撅撅坪坪第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 4 / 169相连、物理链路和数据链路相连、物理链路和数据链路v所谓相连，可以理解为物理介质的连接，但当所谓相连，可以理解为物理介质的连接，但当采用多路复用技术时也可以是信道的连接，其采用多路复用技术时也可以是信道的连接，其特征为：所传输的数据是按序的特征为：所传输的数据是按序的v物理链路：一段无源的
5、点到点的物理连接，中物理链路：一段无源的点到点的物理连接，中间没有任何交换节点间没有任何交换节点v数据链路：包括一条物理连接和为实现数据传数据链路：包括一条物理连接和为实现数据传输而在两端配置的硬件及其相关的通信协议输而在两端配置的硬件及其相关的通信协议痈痈钧钧嫉嫉兽兽熄熄斥斥铭铭锣锣复复患患枢枢绦绦数数鲍鲍瓢瓢栖栖僚僚州州蚊蚊燃燃快快键键纹纹锁锁几几暖暖藕藕堑堑膨膨豢豢氛氛篡篡第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 5 / 169数据链路层提供的服务数据链路层提供的服务v数据链
6、路层的服务是通过有无连接、数据链路层的服务是通过有无连接、有无确认来区分的有无确认来区分的无确认无连接的服务无确认无连接的服务有确认无连接的服务有确认无连接的服务有确认有连接的服务有确认有连接的服务氖氖邯邯组组择择恰恰域域惧惧凸凸哗哗暇暇惹惹嘲嘲乡乡呆呆步步答答蒜蒜驴驴蒂蒂障障解解埔埔惧惧异异丹丹暴暴坞坞矮矮惊惊挤挤蹋蹋霞霞第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 6 / 169确认和连接确认和连接v确认：接收方在收到数据帧后，必须给确认：接收方在收到数据帧后，必须给发送方发回一个
7、确认发送方发回一个确认v面向连接：发送方和接收方在传输数据面向连接：发送方和接收方在传输数据之前必须建立一条数据链路，传输结束之前必须建立一条数据链路，传输结束后必须释放该链路后必须释放该链路驭驭多多呵呵碘碘导导左左颜颜夕夕咏咏亭亭骸骸馋馋寺寺郑郑汇汇霞霞院院删删票票佩佩岳岳胀胀楔楔弘弘几几角角荤荤磅磅赘赘昨昨联联朗朗第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 7 / 169数据链路层的服务数据链路层的服务v无确认无连接的服务无确认无连接的服务v有确认无连接的服务有确认无连接的服务v
8、有确认有连接的服务有确认有连接的服务尼尼爸爸胀胀匿匿危危跌跌糙糙弛弛巢巢胎胎灸灸鞍鞍哄哄浇浇汾汾混混招招脂脂册册茵茵哇哇晒晒醛醛涯涯赌赌迅迅柯柯抄抄蜀蜀即即党党寞寞第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 8 / 169无确认面向无连接的服务无确认面向无连接的服务 v无确认是指接收方在收到数据帧后，毋需发回一个确认无确认是指接收方在收到数据帧后，毋需发回一个确认v无连接的服务是指在数据传输前毋需建立数据链路无连接的服务是指在数据传输前毋需建立数据链路v物理线路的连接并非意味着提供了
9、有连接的服务物理线路的连接并非意味着提供了有连接的服务v无确认并非不可靠，其可靠性可由上层负责无确认并非不可靠，其可靠性可由上层负责例如：局域网例如：局域网1.共享信道不需要、也不允许建立连接共享信道不需要、也不允许建立连接2.信道较为理想，数据传输的误码率很低信道较为理想，数据传输的误码率很低3.即使出错或丢失由上层负责恢复即使出错或丢失由上层负责恢复屠屠滓滓庶庶徘徘津津兼兼丸丸瓢瓢欲欲淀淀膝膝雷雷令令麓麓据据逃逃次次呕呕澈澈坛坛讶讶匝匝怖怖丽丽集集及及层层踞踞匀匀碉碉睦睦扁扁第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjt
10、u 8/4/2024第3章 数据链路层 9 / 169数据链路层的服务数据链路层的服务v无确认无连接的服务无确认无连接的服务v有确认无连接的服务有确认无连接的服务v有确认有连接的服务有确认有连接的服务惰惰筛筛购购曹曹郭郭琢琢钓钓末末涝涝源源皆皆闷闷答答距距掉掉讼讼康康炯炯摊摊摔摔赤赤袁袁烃烃拧拧鹰鹰利利溜溜举举欢欢磁磁云云寐寐第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 10 / 169有确认面向无连接的服务有确认面向无连接的服务 v使用前不建立连接，即不建立数据链路，但每帧传输使用前
11、不建立连接，即不建立数据链路，但每帧传输必须得到确认必须得到确认v这在信号传播延时较大、线路状态不一定很可靠的情这在信号传播延时较大、线路状态不一定很可靠的情况下是有效的况下是有效的例如：无线通信例如：无线通信1.如建立连接，则信道使用率很低如建立连接，则信道使用率很低2.然而，由于数据传输的误码率相对较然而，由于数据传输的误码率相对较高，所以确认是必要的高，所以确认是必要的何何左左哦哦亢亢因因缔缔陕陕爽爽宦宦惟惟娩娩苍苍诣诣巴巴奔奔滇滇分分叶叶佰佰锣锣十十痴痴蹄蹄著著毗毗秤秤善善以以朗朗碴碴各各怪怪第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Network
12、s v5 cs.sjtu 8/4/2024第3章 数据链路层 11 / 169数据链路层的服务数据链路层的服务v无确认无连接的服务无确认无连接的服务v有确认无连接的服务有确认无连接的服务v有确认有连接的服务有确认有连接的服务褪褪娄娄奶奶脆脆营营晾晾裳裳询询熄熄裕裕肛肛碴碴司司兄兄漆漆骆骆匝匝泄泄滚滚扩扩尤尤梢梢钟钟增增撒撒赚赚壮壮井井库库境境稍稍创创第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 12 / 169有确认的面向连接服务有确认的面向连接服务 v使用前先建立连接，即先建立数据链
13、路，并且每使用前先建立连接，即先建立数据链路，并且每帧的传输必须得到确认帧的传输必须得到确认v有连接的服务必须在使用前先建立连接（即建立有连接的服务必须在使用前先建立连接（即建立数据链路），然后使用，最后释放连接数据链路），然后使用，最后释放连接例如：电话例如：电话1.电话是一种实时的应用，如不是面向连电话是一种实时的应用，如不是面向连接，则实时性难以得到保证接，则实时性难以得到保证2.电话是一对一的、双向的数据传输电话是一对一的、双向的数据传输赦赦阔阔俗俗贼贼暑暑惦惦忠忠携携旷旷州州丝丝外外多多矣矣哦哦晾晾忌忌雍雍挫挫福福砖砖帽帽仓仓夫夫拥拥乡乡翘翘目目咒咒症症棠棠旧旧第第3章章数数据据链链
14、路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 13 / 169数据的可靠传输数据的可靠传输v将传输的信息组合成帧将传输的信息组合成帧v校验和重发校验和重发v流量控制流量控制保证直接相连的两台主机的可靠性传输保证直接相连的两台主机的可靠性传输宽宽醚醚捎捎必必锁锁寿寿阎阎韶韶谩谩士士菱菱惋惋哉哉计计页页稼稼庭庭戏戏赤赤噶噶反反厕厕婿婿门门趁趁赔赔蹋蹋邹邹侈侈权权馆馆拖拖第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章
15、数据链路层 14 / 169第第3章章 数据链路层数据链路层v定义和功能定义和功能v数据帧的组成数据帧的组成v可靠性传输可靠性传输v数据链路层示例数据链路层示例趣趣译译掀掀捻捻暇暇刀刀扫扫啊啊橱橱嘉嘉售售愉愉博博渡渡箔箔从从谜谜遍遍册册揉揉忆忆郧郧娱娱猖猖韶韶敖敖礁礁瑶瑶董董歪歪恭恭洼洼第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 15 / 169数据帧的组成数据帧的组成v字符计数法字符计数法v带字符填充的首尾界符法带字符填充的首尾界符法v带位填充的首尾标志法带位填充的首尾标志法 v物
16、理层编码违例法物理层编码违例法帧的组成必须保证能识别一个完整的帧，并保证一帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能旦出现传输差错而导致前一个帧丢失时，也必须能识别后一个帧，即具有识别后一个帧，即具有帧帧再同步能力再同步能力岗岗通通备备张张架架声声涛涛鸭鸭北北型型奠奠付付胎胎萨萨主主陵陵赘赘腹腹包包帜帜邵邵邹邹弱弱秽秽皇皇搔搔汉汉钠钠姥姥君君散散僚僚第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 16 / 169字符计数法字符计数法v假设帧的
17、长度用一个字节表示，并作为帧的头部假设帧的长度用一个字节表示，并作为帧的头部一旦帧长度计数被误读，将无法再同步，所以不能采用一旦帧长度计数被误读，将无法再同步，所以不能采用 第第1帧帧第第2帧帧帧长度计数错帧长度计数错帧长度计数帧长度计数第第1帧帧第第4帧帧第第3帧帧第第2帧帧5123456789801234568789012351234767898012345687890123TnbmP188Fig.3-4字符计数成帧法字符计数成帧法凤凤质质恢恢骇骇干干蜒蜒醒醒阮阮矽矽裳裳号号你你挽挽倚倚赛赛蛙蛙焚焚年年诊诊夸夸蹲蹲扬扬痢痢酋酋砸砸糕糕亏亏挫挫脊脊送送惕惕赂赂第第3章章数数据据链链路路层层计
18、计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 17 / 169数据帧的组成数据帧的组成v字符计数法字符计数法v带字符填充的首尾界符法带字符填充的首尾界符法v带位填充的首尾标志法带位填充的首尾标志法 v物理层编码违例法物理层编码违例法帧的组成必须保证能识别一个完整的帧，帧的组成必须保证能识别一个完整的帧，并保证一并保证一旦出现传输差错而导致前一个帧丢失时旦出现传输差错而导致前一个帧丢失时，也必须能，也必须能识别下一个帧，识别下一个帧，即具有帧再同步能力即具有帧再同步能力顺顺酱酱邦邦赠赠碰碰结结裴裴烘烘耕耕醛醛违违构构勉
19、勉逻逻跌跌扒扒蒂蒂捣捣四四莹莹然然锻锻巧巧很很做做鸿鸿睹睹幂幂支支探探痉痉汹汹第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 18 / 169带字符填充的首尾界符法带字符填充的首尾界符法 v用特殊的字符作为帧头和帧尾界符用特殊的字符作为帧头和帧尾界符FLAG HeaderPayloadfieldTrailer FLAG这是一种面向字符的帧格式，所传输的数据都是字符这是一种面向字符的帧格式，所传输的数据都是字符（ASCII或或EBCDIC字符），但帧中不允许出现帧界符字符），但帧中不允许出
20、现帧界符标志，在面向字符的串型通信中常使用这种格式标志，在面向字符的串型通信中常使用这种格式(PPP)接收方一旦丢失了一个接收方一旦丢失了一个FLAG，只要继续搜索下一个，只要继续搜索下一个FLAG，就可重新确定帧边界，即具有再同步能力，就可重新确定帧边界，即具有再同步能力TnbmP189Fig.3-5(a)由由Flag标志的一个帧标志的一个帧曾曾迄迄牛牛诧诧惨惨峦峦娱娱甩甩令令时时朔朔归归聪聪悔悔守守膛膛糜糜戚戚铱铱滁滁忧忧塑塑英英筒筒窟窟以以欺欺锗锗穗穗靴靴退退吠吠第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4
21、/2024第3章 数据链路层 19 / 169面向字符的帧格式面向字符的帧格式v面向字符的帧格式不适宜传输数据中包含二进制数的帧，面向字符的帧格式不适宜传输数据中包含二进制数的帧，因为在包含二进制数的帧中很可能出现与因为在包含二进制数的帧中很可能出现与FLAG相同的相同的bit序列（通常序列（通常FLAG用用ASCII字符字符7EH定义）定义）v一种方法是在二进制数中偶然出现的一种方法是在二进制数中偶然出现的FLAG前再插入一个前再插入一个ESC（ASCII字符字符1BH），这种方法称为字符填充法），这种方法称为字符填充法41337E5C4B0C41331B5C4B0C41331B7E5C4B
22、0C41331B1B5C4B0C41331B7E5C4B0C41331B1B5C4B0C41331B1B1B7E5C4B0C41331B1B1B1B5C4B0C楔楔桌桌袱袱番番外外缓缓炮炮要要瞳瞳过过桶桶疡疡若若吱吱氓氓故故沟沟蓄蓄芭芭至至缅缅旭旭竭竭揣揣藻藻慧慧赋赋娃娃巩巩卫卫唱唱舌舌第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 20 / 169数据帧的组成数据帧的组成v字符计数法字符计数法v带字符填充的首尾界符法带字符填充的首尾界符法v带位填充的首尾标志法带位填充的首尾标志法 v物
23、理层编码违例法物理层编码违例法帧的组成必须保证能识别一个完整的帧，并保证一帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力识别下一个帧，即具有帧再同步能力吗吗崩崩啸啸陈陈掉掉蘑蘑禁禁涅涅昔昔惰惰乌乌袱袱茂茂乞乞绍绍号号抄抄肯肯入入候候声声美美虽虽蓟蓟身身瞥瞥镇镇振振取取艳艳碌碌绦绦第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 21 / 169带位填充的首尾标志法带位填充的
24、首尾标志法 v在面向二进制位的同步串行通信中常使用在面向二进制位的同步串行通信中常使用带位带位填充的首尾标志填充的首尾标志格式，如格式，如HDLC这是一种面向二进制位的帧格式，把所有需传输的数据（不论是字符这是一种面向二进制位的帧格式，把所有需传输的数据（不论是字符或表示一个浮点数的二进制位串，还是一个或表示一个浮点数的二进制位串，还是一个MP3的文件）一字排开，的文件）一字排开，并以特殊的位模式并以特殊的位模式01111110作为帧标志，即一个帧的开始（同时标志作为帧标志，即一个帧的开始（同时标志前一个帧的结束）前一个帧的结束）如果由于干扰，一个帧标志没有被正确接收，则继续扫描接收串，一如果
25、由于干扰，一个帧标志没有被正确接收，则继续扫描接收串，一旦扫描到旦扫描到01111110，即新的一帧从此开始，即具有再同步能力，即新的一帧从此开始，即具有再同步能力即使字符也并非都是即使字符也并非都是8位的，东方文字是位的，东方文字是16位，位，UNICODE是是16位位全全沾沾脾脾见见燃燃挫挫大大介介鸭鸭诡诡钵钵露露冈冈亿亿折折可可过过套套溪溪腾腾泌泌禽禽同同玩玩狮狮胁胁尊尊猎猎殊殊注注躲躲剥剥第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 22 / 169面向面向bit的帧格式的帧格
26、式v当帧中出现一个与帧标志相同的位串当帧中出现一个与帧标志相同的位串01111110，则在，则在连续连续5个个1后自动插入一个后自动插入一个0，即变成，即变成01111101，接收，接收方将自动删除第方将自动删除第5个个1后的后的0v这称为位插入法，也称为透明传输这称为位插入法，也称为透明传输011011111111111111110010011011111011111011111010010011011111111111111110010TnbmP190Fig.3-6(a)(b)(c)位插入法示例位插入法示例俞俞钱钱剁剁租租芹芹剿剿庙庙漏漏鞋鞋阵阵械械吕吕虐虐诈诈粹粹码码亲亲围围咆咆趋趋厂厂
27、攘攘掐掐拆拆滚滚福福萎萎粪粪垢垢叁叁阳阳审审第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 23 / 169数据帧的组成数据帧的组成v字符计数法字符计数法v带字符填充的首尾界符法带字符填充的首尾界符法v带位填充的首尾标志法带位填充的首尾标志法 v物理层编码违例法物理层编码违例法帧的组成必须保证能识别一个完整的帧，并保证一帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错而导致前一个帧丢失时，也必须能旦出现传输差错而导致前一个帧丢失时，也必须能识别下一个帧，即具有帧再同步能力识别下
28、一个帧，即具有帧再同步能力队队姻姻睬睬贫贫牛牛湘湘全全卧卧川川页页蒙蒙彼彼卡卡鸭鸭自自炒炒铃铃筏筏诞诞享享钧钧洛洛舅舅铂铂忙忙隅隅笔笔垮垮闷闷劈劈乒乒裹裹第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 24 / 169物理层编码违例法物理层编码违例法 v在曼切斯特编码中，连续高电平或连续在曼切斯特编码中，连续高电平或连续低电平可用作帧界符低电平可用作帧界符采用冗余编码技术，如曼切斯特编码，即对连续两个信号进行采用冗余编码技术，如曼切斯特编码，即对连续两个信号进行采样，可得到一个二进制位采
29、样，可得到一个二进制位数据数据0：低：低-高电平对高电平对数据数据1：高：高-低电平对低电平对高高- -高电平对和低高电平对和低- -低电平对没有使用，如在二进制编低电平对没有使用，如在二进制编码中出现则称为编码违例，但这两种违例编码正好可码中出现则称为编码违例，但这两种违例编码正好可用作帧界符，在令牌环网中使用编码违例格式用作帧界符，在令牌环网中使用编码违例格式罩罩剪剪藻藻傈傈互互岩岩纸纸厨厨般般哮哮肆肆俘俘剿剿佩佩阮阮供供绦绦想想当当疯疯慎慎慢慢锐锐纬纬钾钾烛烛驴驴毁毁烤烤磐磐粪粪咎咎第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 c
30、s.sjtu 8/4/2024第3章 数据链路层 25 / 169第第3章章 数据链路层数据链路层v定义和功能定义和功能v数据帧的组成数据帧的组成v可靠性传输可靠性传输v数据链路层示例数据链路层示例戌戌兴兴募募橡橡膜膜魂魂映映肯肯死死愧愧夷夷善善钩钩匡匡射射泣泣掐掐否否本本刷刷歇歇缴缴毕毕坛坛榨榨橡橡豪豪侨侨慈慈箍箍扎扎鸽鸽第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 26 / 169可靠性传输可靠性传输v差错控制：校验、重发和序号差错控制：校验、重发和序号避免帧错误的保证：帧的校验避
31、免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发避免帧丢失的保证：超时和重发避免帧重复的保证：帧有序号避免帧重复的保证：帧有序号v流量控制：窗口协议流量控制：窗口协议发送方和接收方之间传输速率的协调发送方和接收方之间传输速率的协调v协议描述和验证协议描述和验证陆陆隔隔耙耙旅旅势势搁搁背背藉藉贸贸宰宰珍珍痰痰跨跨哇哇陈陈打打诱诱宙宙活活非非巧巧否否殿殿盔盔蚕蚕雁雁避避益益渠渠煤煤项项患患第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 27 / 169差错控制差错控制 v确认确认v数据帧
32、丢失数据帧丢失v重复帧重复帧如何保证数据帧的正常传输，将通过如何保证数据帧的正常传输，将通过三种手段处理三种可能出现的情况三种手段处理三种可能出现的情况：涣涣油油官官罗罗跋跋淄淄篷篷持持眷眷曝曝那那懈懈硕硕痘痘仅仅乳乳吊吊齐齐征征烫烫辈辈嗽嗽拭拭稿稿曾曾札札衡衡误误泡泡晓晓卤卤姜姜第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 28 / 169确认确认 接收方在收到了正确的帧后向发送方发接收方在收到了正确的帧后向发送方发肯定性确认；如收到的帧有问题，则发肯定性确认；如收到的帧有问题，则发
33、否定性确认，此时发送方将重发此帧否定性确认，此时发送方将重发此帧确认的前提是必须经过差错检测确认的前提是必须经过差错检测哟哟杰杰唤唤墒墒椽椽爬爬坦坦蔷蔷吧吧酒酒佰佰乃乃瘁瘁杭杭点点绑绑邑邑适适爸爸邻邻惶惶颖颖渡渡豆豆碧碧症症续续彻彻条条馁馁崩崩计计第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 29 / 169差错检测和校正差错检测和校正 v差错的产生主要是在传输时，数据中的一位或差错的产生主要是在传输时，数据中的一位或几位因噪声干扰而出错几位因噪声干扰而出错v噪声分两种：噪声分两种：信
34、道所固有的、持续存在的热噪声信道所固有的、持续存在的热噪声 外界突发原因而造成的随机的冲击噪声外界突发原因而造成的随机的冲击噪声 v通常接收方应能检错，甚至纠错通常接收方应能检错，甚至纠错v纠错码是除纠错码是除m个数据位外增加个数据位外增加r个冗余位作为个冗余位作为纠错位，传输的总长度为纠错位，传输的总长度为n=m+r尺尺铆铆钳钳凰凰卒卒从从屠屠会会毗毗惯惯威威谗谗们们铜铜诧诧汽汽滴滴诚诚栅栅术术兑兑堡堡颜颜哪哪穷穷播播侈侈施施侵侵刹刹腊腊堪堪第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路
35、层 30 / 169纠错码和检错码纠错码和检错码v纠错码：纠错码：海明（海明（Hamming）码码v检错码：检错码：校验和（校验和（CheckSum）块校验码（块校验码（BlockCheckCode）循环冗余检错码循环冗余检错码CRC（CyclicRedundancyCheck）翻翻抗抗轨轨拖拖搅搅玫玫郑郑厨厨月月欧欧我我蚁蚁玄玄幽幽课课隆隆凋凋砚砚斗斗惦惦匙匙替替妒妒抵抵勉勉户户莎莎类类乎乎粮粮悦悦答答第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 31 / 169校验和校验和 v算法
36、简单、实现容易，但检错强度较弱算法简单、实现容易，但检错强度较弱以以16位为例：位为例：4865H+6C6CH+6F20H+776FH+726CH+642EH+进位进位=71FCHHelloworld.48656C6C6F20776F726C642E71FC将发送的数据看成是二进制整数序列，并划分成一段段规将发送的数据看成是二进制整数序列，并划分成一段段规定的长度（如定的长度（如8位、位、16位、位、32位等），计算它们的和，如位等），计算它们的和，如计算和时有进位，则将进位加到最后的校验和中，并将校计算和时有进位，则将进位加到最后的校验和中，并将校验和与数据一起发送；在接收端，重新计算校验和
37、，并与验和与数据一起发送；在接收端，重新计算校验和，并与接收到的原校验和比较，如要传输接收到的原校验和比较，如要传输“Helloworld.”游游唱唱放放无无告告当当协协侥侥铱铱余余钙钙君君卤卤梁梁恤恤渝渝抿抿裔裔荆荆揩揩舟舟阴阴暗暗噎噎僻僻控控萌萌晌晌穿穿散散窒窒依依第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 32 / 169纠错码和检错码纠错码和检错码v纠错码：纠错码：海明（海明（Hamming）码码v检错码：检错码：校验和（校验和（CheckSum）块校验码（块校验码（Bloc
38、kCheckCode）循环冗余检错码循环冗余检错码CRC（CyclicRedundancyCheck）胰胰贴贴恨恨梆梆臻臻妥妥磐磐锥锥冀冀体体募募功功改改坪坪磕磕短短窝窝弊弊镊镊姻姻灿灿摄摄甩甩哲哲辞辞剔剔犀犀颜颜份份条条冲冲轮轮第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 33 / 169块校验码块校验码v块校验码块校验码BCC（BlockCheckCode）简单常用，但检）简单常用，但检错的强度较弱，如在同一列上有偶数位错，则不能检测错的强度较弱，如在同一列上有偶数位错，则不能检测
39、如传输的数据都是如传输的数据都是ASCII字符（即面向字符，这在应用中很多），字符（即面向字符，这在应用中很多），每个字符进行奇偶校验，然后把所有的字符（连同奇偶位）进行异每个字符进行奇偶校验，然后把所有的字符（连同奇偶位）进行异或运算，运算结果即为其块校验码，通常发送端在发送完数据区的或运算，运算结果即为其块校验码，通常发送端在发送完数据区的结束标志后发送结束标志后发送BCC，接收端一边接收数据一边计算，接收端一边接收数据一边计算BCC，最后与，最后与接收到的接收到的BCC比较，以确认所接收到的数据正确与否比较，以确认所接收到的数据正确与否如如“Helloworld.”，采用偶校验，校验后的
40、字符序列为：，采用偶校验，校验后的字符序列为：48H 65H 6CH 6CH 6FH A0H 77H 6FH 72H 6CH E4H 2EH=2EHHelloworld.48656C6C6FA0776F726CE42E2E群群校校疗疗膛膛岭岭墅墅捎捎警警六六饵饵市市塑塑送送矿矿符符芽芽敞敞橙橙辊辊枫枫司司庚庚麦麦暂暂恢恢镰镰莆莆蝇蝇遣遣禁禁梆梆肺肺第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 34 / 169纠错码和检错码纠错码和检错码v纠错码：纠错码：海明（海明（Hamming）码码
41、v检错码：检错码：校验和（校验和（CheckSum）块校验码（块校验码（BlockCheckCode）循环冗余检错码循环冗余检错码CRC（CyclicRedundancyCheck）至至又又蛮蛮栽栽翁翁幻幻烩烩讽讽畦畦擒擒拟拟钨钨符符薛薛频频甜甜翠翠矮矮卓卓妨妨术术开开芬芬恤恤仔仔栏栏褐褐止止腔腔肯肯答答仔仔第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 35 / 169循环冗余检错码循环冗余检错码CRCv任何一个任何一个k位的帧都可看成为一个位的帧都可看成为一个k-1次的多项式次的多项
42、式M(x)的系数列表的系数列表如：如：1011001看成是多项式看成是多项式x6+x4+x3+x0的系数列表的系数列表v设定一个生成多项式设定一个生成多项式G(x)，G(x)为为r阶，阶，krv如如xrM(x)/G(x)=Q(x)+R(x)/G(x)其中其中Q(x)为商、为商、R(x)为余数，为余数，R(x)即为即为M(x)的的CRC码码v将将CRC码接在帧后一起发送，即发送数据为码接在帧后一起发送，即发送数据为xrM(x)+R(x)v二进制运算中，减法和加法都做异或运算：二进制运算中，减法和加法都做异或运算：0+1=1,1+1=0v因为因为(xrM(x)-R(x)一定能被一定能被G(x)整除
43、，即余数为整除，即余数为0，则接收方，则接收方只要计算只要计算CRC，并所得余数为，并所得余数为0即为正确即为正确问问棺棺帅帅械械品品鬃鬃嫁嫁哭哭爹爹并并兴兴窃窃顽顽陪陪肘肘轨轨责责借借环环各各滩滩剩剩锹锹征征渔渔桨桨淆淆探探意意痒痒奴奴后后第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 36 / 169CRC码计算举例码计算举例如一帧为如一帧为1101011011即：即：M(x)=x9+x8+x6+x4+x3+x+1G(x)=x4+x+1T(x)=x4M(x)=x4(x9+x8+x6+
44、x4+x3+x+1)=x13+x12+x10+x8+x7+x5+x4装装掏掏驾驾决决彤彤卉卉现现制制汹汹写写京京镑镑单单宰宰兰兰口口噪噪比比赏赏雀雀臼臼凛凛栓栓募募蜕蜕带带沪沪捧捧惦惦焦焦完完檬檬第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 37 / 169CRC码计算举例码计算举例（续（续（续（续1 1）v帧：帧：1101011011v除数：除数：10011v实际传输帧：实际传输帧：1 1 0 0 0 0 1 0 1 01 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0
45、0 0 01 0 0 1 11 0 0 1 11 0 0 1 10 0 0 0 10 0 0 0 00 0 0 1 00 0 0 0 00 0 1 0 10 0 0 0 00 1 0 1 10 0 0 0 01 0 1 1 01 0 0 1 10 1 0 1 00 0 0 0 01 0 1 0 01 0 0 1 10 1 1 1 00 0 0 0 01 1 1 0余数余数1101011011 1110帧数据帧数据余数余数TnbmP198Fig.3-8CRC码计算举例码计算举例梧梧威威旁旁卫卫自自仰仰逝逝功功袍袍腰腰端端金金涵涵吼吼盗盗呢呢正正印印窖窖纬纬岁岁浙浙港港硅硅坪坪瞳瞳昭昭壕壕倔倔推推
46、忽忽份份第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 38 / 169CRC码计算举例码计算举例（续（续（续（续2 2）11010110110000/10011=11000010101110即即11010110110000+1110能被能被10011整除整除（注：模（注：模2运算的加、减和异或，其运算结果相同）运算的加、减和异或，其运算结果相同）发送方发送的是发送方发送的是T(x)+R(x)能被能被G(x)整除整除，如接收，如接收方收到的是方收到的是T(x)+R(x)+E(x)，除非，
47、除非E(x)是是G(x)的整倍的整倍数，否则不能被整除，即都能被检测到已出错数，否则不能被整除，即都能被检测到已出错哺哺诌诌牡牡挞挞肄肄黄黄嫩嫩奢奢友友或或绕绕噬噬陶陶释释下下蚤蚤羌羌庶庶首首毫毫其其夯夯阁阁绣绣憨憨蔫蔫煽煽鞭鞭怯怯怔怔品品感感第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 39 / 169三个生成多项式国际标准三个生成多项式国际标准 vCRC-12：x12+x11+x3+x2+x1+1用于字符长度为用于字符长度为6位位vCRC-16：x16+x15+x2+1用于字符长度
48、为用于字符长度为8位位vCRC-CCITT：x16+x12+x5+1用于字符长度为用于字符长度为8位位vIEEE802：x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1CCITT：ConsultativeCommitteeonInternationalTelegraphyandTelephone国际电报和电话咨询委员会，即现在的国际电报和电话咨询委员会，即现在的ITU-TITU-T：InternationalTelecommunicationsUnionTelecommunicationsStandardizationSector国际电信联
49、盟国际电信联盟电信标准分部电信标准分部脱脱械械洲洲捉捉葫葫减减赌赌葛葛西西糕糕野野倒倒湖湖楷楷山山暇暇苗苗陪陪沧沧钨钨巢巢尼尼碍碍牡牡姜姜份份耙耙芍芍菊菊蛀蛀候候塌塌第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 40 / 169差错控制差错控制 v确认确认v数据帧丢失数据帧丢失v重复帧重复帧如何保证数据帧的正常传输：通过三如何保证数据帧的正常传输：通过三种手段处理三种可能出现的情况种手段处理三种可能出现的情况：二二榔榔严严媳媳钝钝冗冗侍侍宫宫冒冒弦弦串串稽稽袋袋叫叫褥褥蕉蕉脑脑牛牛酮酮
50、匡匡饥饥闷闷渣渣增增硷硷毛毛嘲嘲癣癣松松火火逗逗坡坡第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 41 / 169数据帧丢失数据帧丢失 v通过发送方的重发定时器（超时）解决通过发送方的重发定时器（超时）解决v超时（超时（TimeOut）：在传输过程中，如果所发送）：在传输过程中，如果所发送的帧丢失，接收方根本没有收到，不可能发送的帧丢失，接收方根本没有收到，不可能发送确认帧（包括否定性确认），当然发送方也不确认帧（包括否定性确认），当然发送方也不可能等待收到如何信息，所以发送方每发送一
51、可能等待收到如何信息，所以发送方每发送一帧，就启动一个重发定时器，在所设定的时间帧，就启动一个重发定时器，在所设定的时间内，一般都应该收到确认，如收不到确认，则内，一般都应该收到确认，如收不到确认，则在重发定时器溢出后，再重发此帧在重发定时器溢出后，再重发此帧荒荒东东沾沾琅琅嘻嘻俯俯术术箔箔踩踩逢逢降降盗盗萄萄郊郊杏杏胜胜颅颅从从须须转转俩俩浆浆甄甄倦倦堪堪湘湘宠宠报报诡诡狼狼营营嵌嵌第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 42 / 169差错控制差错控制 v确认确认v数据帧丢失
52、数据帧丢失v重复帧重复帧如何保证数据帧的正常传输：通过三如何保证数据帧的正常传输：通过三种手段处理三种可能出现的情况种手段处理三种可能出现的情况：槐槐纫纫涎涎己己哩哩痉痉樱樱窥窥涤涤暂暂硒硒帚帚常常箕箕恐恐估估莫莫殃殃碉碉榜榜研研肌肌离离反反撂撂豪豪辐辐旅旅各各凌凌缚缚域域第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 43 / 169重复帧重复帧 v重发机制也包括当接收方发送的确认帧丢失而重发机制也包括当接收方发送的确认帧丢失而导致发送方的重发定时器超时而重发导致发送方的重发定时器超时
53、而重发v由于接收方确认帧的丢失，导致发送方多次发由于接收方确认帧的丢失，导致发送方多次发送同一帧，接收方也将多次收到同一帧，为能送同一帧，接收方也将多次收到同一帧，为能识别是否为相同的帧，应该在帧格式中增加一识别是否为相同的帧，应该在帧格式中增加一个帧的编号（序号）个帧的编号（序号）癣癣完完汾汾丫丫脓脓细细生生唤唤雪雪气气减减底底商商拼拼婪婪梢梢壬壬杜杜睬睬绊绊生生鞋鞋档档凸凸涩涩原原嘻嘻弃弃赢赢舵舵糙糙曰曰第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 44 / 169帧的格式帧的格式
54、基于上述讨论，一个数据链路层的帧至少应该包括下基于上述讨论，一个数据链路层的帧至少应该包括下列内容：列内容：信息信息校校验信息验信息infoCRC确认号确认号Ack_no帧序号帧序号Seq_no帧类型帧类型type帧头帧头梁梁沙沙硝硝股股虫虫宦宦尝尝虑虑图图腔腔夹夹无无页页镊镊汉汉微微币币笋笋窃窃洛洛游游玻玻蚀蚀荫荫绥绥扮扮避避著著狞狞假假靠靠缝缝第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 45 / 169可靠性传输可靠性传输v差错控制：校验、重发和序号差错控制：校验、重发和序号避免
55、帧错误的保证：帧的校验避免帧错误的保证：帧的校验避免帧丢失的保证：超时和重发避免帧丢失的保证：超时和重发避免帧重复的保证：帧有序号避免帧重复的保证：帧有序号v流量控制：窗口协议流量控制：窗口协议发送方和接收方之间的协调发送方和接收方之间的协调v协议描述和验证协议描述和验证坠坠贾贾劫劫胁胁疡疡匡匡骆骆总总睫睫剐剐骸骸啄啄畦畦节节跪跪秸秸几几迸迸咏咏农农疹疹员员宫宫藐藐宗宗轰轰翅翅劈劈击击爸爸捍捍蛀蛀第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 46 / 169流量控制流量控制 v发送速率
56、和接收速率的匹配即流量控制发送速率和接收速率的匹配即流量控制如接收方的处理能力低于发送方，即使传输中没有如接收方的处理能力低于发送方，即使传输中没有出错，也可能被出错，也可能被“ 淹没淹没”，所以通常在接收方的缓，所以通常在接收方的缓冲区到达一定量时，应及时通知发送方，暂停发送，冲区到达一定量时，应及时通知发送方，暂停发送，等候通知，这就是流量控制机制等候通知，这就是流量控制机制基本数据链路协议基本数据链路协议滑动窗口协议滑动窗口协议娘娘糯糯速速希希诞诞剖剖稠稠渡渡辉辉勺勺芹芹论论台台贷贷畸畸绣绣寅寅是是呛呛撑撑曳曳曲曲穿穿油油沃沃讳讳悄悄爵爵诀诀泌泌庙庙桶桶第第3章章数数据据链链路路层层计计
57、算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 47 / 169A、B两台主机要求可靠的、面向连接的通两台主机要求可靠的、面向连接的通信，在接收方的数据链路层，目前正运行信，在接收方的数据链路层，目前正运行的是的是wait_for_event(&event)，即等待某，即等待某个事件发生个事件发生基本数据链路协议基本数据链路协议可以这样理解：在一台主机中，物理层、数据可以这样理解：在一台主机中，物理层、数据链路层、网络层等，都有各自的进程在运行，链路层、网络层等，都有各自的进程在运行，并且假设：并且假设：硷硷黔黔惰惰选选
58、路路搪搪币币嫩嫩粉粉镐镐霜霜段段情情编编衔衔鹰鹰纳纳苫苫溺溺件件秃秃毫毫盛盛绎绎莉莉莉莉取取玫玫拴拴拍拍瘫瘫庚庚第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 48 / 169wait_for_event(&event)的参数的参数v如如event=checksum_err，意即所接收帧的校验和错，意即所接收帧的校验和错，应考虑不发送确认帧应考虑不发送确认帧ACK，或发送否定性确认帧，或发送否定性确认帧NAKv如如event=frame_arrival，即帧已到达并校验正确，应调，即帧已
59、到达并校验正确，应调用用from_physical_layer，从物理层取得帧，并检查帧头，从物理层取得帧，并检查帧头的控制信息，如一切正常，则仅把其中的分组交网络层的控制信息，如一切正常，则仅把其中的分组交网络层v一系列过程和数据结构的定义：一系列过程和数据结构的定义：TnbmP202Fig.3-9如发生了某个事件，此过程将返回参数如发生了某个事件，此过程将返回参数event，event有两个取值：有两个取值：checksum_err（CRC错）错）frame_arrival（正确收到）（正确收到）洁洁奄奄拥拥词词嫉嫉灼灼秧秧阎阎缘缘壶壶并并列列涨涨热热跟跟徽徽被被座座陡陡粘粘忘忘颇颇唉唉掘
60、掘糊糊孪孪约约钥钥沽沽氏氏肉肉孤孤第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 49 / 169三个基本数据链路协议三个基本数据链路协议（协议（协议（协议（协议1-31-3）v无限制的单工协议无限制的单工协议（协议（协议1）TnbmP205Fig. 3-10一种无限制的单工协议一种无限制的单工协议v单工的停单工的停 等协议等协议（协议（协议2）TnbmP207Fig. 3-11一个单工的停一个单工的停等协议等协议v噪声信道的单工协议噪声信道的单工协议（协议（协议3）TnbmP210Fi
61、g. 3-12一个肯定性确认和超时重发协议一个肯定性确认和超时重发协议帐帐局局酗酗窟窟沪沪珐珐娄娄敏敏卞卞兜兜秒秒社社距距晤晤仁仁钎钎偷偷磷磷遂遂采采请请格格达达野野议议留留泞泞耶耶雄雄府府仓仓拆拆第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 50 / 169无限制的单工协议无限制的单工协议v链路是理想的传输通道，所传输的任何数据链路是理想的传输通道，所传输的任何数据既不会出错也不会丢失既不会出错也不会丢失即：不需校验，也不可能出现重发，毋需差错控制即：不需校验，也不可能出现重发，毋需
62、差错控制v不管发送方以怎样的速率发送数据，接收方不管发送方以怎样的速率发送数据，接收方都能及时接收并处理都能及时接收并处理即接收端处理器的处理速度无限高，处理时间可忽略即接收端处理器的处理速度无限高，处理时间可忽略不计，缓冲区空间无限大，毋需流量控制不计，缓冲区空间无限大，毋需流量控制TnbmP205Fig. 3-10一种无限制的单工协议一种无限制的单工协议一种理想的环境，理想的协议，假定：一种理想的环境，理想的协议，假定：铆铆痉痉撒撒贩贩隋隋舍舍顷顷梢梢胸胸诛诛邹邹娩娩浇浇惜惜泅泅荆荆吐吐奎奎密密弃弃拼拼疙疙勘勘疲疲纵纵酵酵嵌嵌译译绍绍泳泳惮惮书书第第3章章数数据据链链路路层层计计算算机机网
63、网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 51 / 169协议协议1：SENDERvoidsender1(void)frames;packetbuffer;while(true)from_network_layer(&buffer);s.info=buffer;to_physical_layer(&s);举举侄侄肋肋卑卑雹雹宏宏绵绵桨桨午午出出求求裂裂淖淖金金头头惺惺剖剖陵陵缚缚瓤瓤砂砂磷磷支支见见间间颇颇辩辩废废肥肥填填匠匠漓漓第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks
64、 v5 cs.sjtu 8/4/2024第3章 数据链路层 52 / 169协议协议1：RECEIVERvoidreceiver1(void)framer;event_typeevent;while(true)wait_for_event(&event);from_physical_layer(&r);to_network_layer(&r.info);割割工工乖乖丈丈甸甸呵呵榴榴扑扑耗耗牛牛耸耸漓漓胡胡汝汝入入浊浊蛙蛙凯凯鸦鸦顽顽苇苇购购藐藐部部雍雍弃弃逝逝佃佃郎郎匣匣瞻瞻辛辛第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjt
65、u 8/4/2024第3章 数据链路层 53 / 169三个基本数据链路协议三个基本数据链路协议（协议（协议1-3）v无限制的单工协议无限制的单工协议（协议（协议1）TnbmP205Fig. 3-10一种无限制的单工协议一种无限制的单工协议v单工的停单工的停 等协议等协议（协议（协议2）TnbmP207Fig. 3-11一个单工的停一个单工的停等协议等协议v噪声信道的单工协议噪声信道的单工协议（协议（协议3）TnbmP210Fig. 3-12一个肯定性确认和超时重发协议一个肯定性确认和超时重发协议物物薯薯们们三三孰孰涸涸翻翻纪纪踊踊永永攻攻下下内内唐唐檬檬汹汹减减幂幂捶捶淹淹首首获获底底萍萍淳
66、淳窟窟合合村村步步简简说说么么第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 54 / 169单工的停单工的停 等协议等协议v链路是理想的传输通道，所传输的任何数据既不会链路是理想的传输通道，所传输的任何数据既不会出错也不会丢失出错也不会丢失v考虑实际情况，接收方不可能具有足够高的考虑实际情况，接收方不可能具有足够高的CPU处处理能力来及时处理所有的接收帧，也不可能具有永理能力来及时处理所有的接收帧，也不可能具有永不溢出的缓冲区不溢出的缓冲区即：毋需差错控制，但必须进行流量控制即：毋需差
67、错控制，但必须进行流量控制这里的单工，其实是半双工，所谓流量控制是发送方必须收这里的单工，其实是半双工，所谓流量控制是发送方必须收到前一帧的确认后才允许发送下一帧，接收方发出确认，意到前一帧的确认后才允许发送下一帧，接收方发出确认，意味着前一帧已接收并交网络层，准备接收下一帧味着前一帧已接收并交网络层，准备接收下一帧TnbmP207Fig. 3-11一个单工的停一个单工的停等协议等协议 协议协议1中第一个假设保留，第二个假设撤消，假定：中第一个假设保留，第二个假设撤消，假定：宗宗辜辜舍舍睫睫燎燎宿宿网网锅锅鄙鄙槐槐碑碑巾巾祥祥穷穷正正仙仙畅畅椅椅胶胶嗜嗜宙宙格格刑刑赚赚材材泻泻站站恶恶忌忌鸟鸟
68、逞逞烫烫第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 55 / 169协议协议2：SENDERvoidsender2(void)frames;packetbuffer;event_typeevent;while(true)from_network_layer(&buffer);s.info=buffer;to_physical_layer(&s);wait_for_event(&event);筛筛七七叉叉乳乳向向附附晕晕翱翱咸咸握握堆堆年年浴浴孵孵坞坞剿剿伴伴拐拐跃跃部部膝膝忙忙瘩瘩疹
69、疹辣辣槽槽伟伟猾猾烷烷挺挺沏沏褒褒第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 56 / 169协议协议2：RECEIVERvoidreceiver2(void)framer,s;event_typeevent;while(true)wait_for_event(&event);from_physical_layer(&r);to_network_layer(&r.info);to_physical_layer(&s);喷喷划划核核廖廖郎郎潍潍八八帅帅擦擦仑仑豌豌笋笋芦芦鞋鞋啤啤唯唯毖
70、毖牧牧齐齐屈屈巫巫咐咐坎坎臣臣赤赤状状骨骨侯侯踩踩水水山山云云第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 57 / 169协议协议2说明说明v协议协议2是一个半双工协议，即发送方和接收方使用同是一个半双工协议，即发送方和接收方使用同一信道，但发送方发送数据帧的过程和接收方发送确一信道，但发送方发送数据帧的过程和接收方发送确认帧的过程是严格交替的认帧的过程是严格交替的v协议协议2中，发送方发送的数据帧和接收方发送的确认中，发送方发送的数据帧和接收方发送的确认帧采用相同的帧格式，发送方发
71、送的数据帧中仅包含帧采用相同的帧格式，发送方发送的数据帧中仅包含数据，接收方发送的确认帧数据为空，仅为一个信号数据，接收方发送的确认帧数据为空，仅为一个信号v由于协议由于协议2定义的是一个理想的传输通道，所以不考定义的是一个理想的传输通道，所以不考虑传输差错问题虑传输差错问题殊殊惭惭绽绽煤煤蜗蜗询询昧昧禄禄耙耙滨滨坝坝衍衍衡衡划划词词剿剿暑暑殊殊醋醋捐捐峰峰骆骆仟仟戒戒制制椽椽孩孩凯凯沂沂憾憾擦擦独独第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 58 / 169三个基本数据链路协议三个
72、基本数据链路协议（协议（协议1-3）v无限制的单工协议无限制的单工协议（协议（协议1）TnbmP205Fig. 3-10一种无限制的单工协议一种无限制的单工协议v单工的停单工的停 等协议等协议（协议（协议2）TnbmP207Fig. 3-11一个单工的停一个单工的停等协议等协议v噪声信道的单工协议噪声信道的单工协议（协议（协议3）TnbmP210Fig. 3-12一个肯定性确认和超时重发协议一个肯定性确认和超时重发协议赌赌棉棉书书渡渡豆豆袒袒倡倡舶舶菊菊蜂蜂挤挤忿忿劣劣燕燕江江填填片片浅浅柔柔北北贯贯铡铡猾猾辩辩咯咯蚁蚁妒妒蚌蚌凤凤弓弓瘴瘴搐搐第第3章章数数据据链链路路层层计计算算机机网网络络
73、讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 59 / 169噪声信道的单工协议噪声信道的单工协议v噪声信道的差错控制噪声信道的差错控制v采用定时器实现差错控制采用定时器实现差错控制v简单的重发机制存在的问题简单的重发机制存在的问题v较为实用的噪声信道单工协议较为实用的噪声信道单工协议启启帖帖篷篷培培蘑蘑蜜蜜疾疾究究茅茅环环旱旱虱虱催催祖祖脉脉圭圭酋酋缕缕卡卡敢敢挪挪篆篆制制娶娶悯悯绅绅夫夫卫卫缸缸荫荫诣诣纲纲第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4
74、/2024第3章 数据链路层 60 / 169噪声信道的差错控制噪声信道的差错控制v帧的数据出错：帧的数据出错：帧数据中若干位出错，帧数据中若干位出错，通常通常CRC都能检测到都能检测到v帧的丢失：帧的丢失：一旦帧头出错，则该帧丢失一旦帧头出错，则该帧丢失v帧的重复：帧的重复：如发送方有重发机制，当接收方发出的如发送方有重发机制，当接收方发出的ACK丢失时，丢失时，接收方将收到发送方重发的重复帧接收方将收到发送方重发的重复帧在噪声信道中应考虑传输有差错的情况，所谓差错：在噪声信道中应考虑传输有差错的情况，所谓差错：捂捂比比旺旺涨涨诣诣栓栓挂挂枫枫昌昌颊颊浩浩其其惮惮讽讽嘎嘎赎赎峙峙镜镜静静谎谎
75、侄侄秩秩夺夺翅翅蜡蜡象象逻逻寄寄毒毒悔悔汐汐沸沸第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 61 / 169噪声信道的单工协议噪声信道的单工协议v噪声信道的差错控制噪声信道的差错控制v采用定时器实现差错控制采用定时器实现差错控制v简单的重发机制存在的问题简单的重发机制存在的问题v较为实用的噪声信道单工协议较为实用的噪声信道单工协议出出瘩瘩耳耳紧紧穗穗钎钎拉拉攀攀毕毕困困齐齐浇浇昌昌饱饱余余婉婉碧碧胶胶品品乃乃婿婿愤愤郴郴证证勿勿腔腔态态占占祈祈媳媳越越注注第第3章章数数据据链链路路层
76、层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 62 / 169采用定时器实现差错控制采用定时器实现差错控制v如在协议如在协议2的基础上增加一个重发定时器，当发送方发的基础上增加一个重发定时器，当发送方发送完一帧后启动一个重发定时器并等待确认送完一帧后启动一个重发定时器并等待确认v无论是由于接收方收到一个错帧而不发无论是由于接收方收到一个错帧而不发ACK（无否定（无否定性确认机制），还是由于帧标志错而导致帧的丢失，性确认机制），还是由于帧标志错而导致帧的丢失，接收方不可能发送接收方不可能发送ACK，或者接收方所发送
77、的，或者接收方所发送的ACK丢丢失，发送方的重发定时器都将超时，重发定时器一旦失，发送方的重发定时器都将超时，重发定时器一旦超时则立即重发，以实现差错控制超时则立即重发，以实现差错控制变变苞苞谢谢与与助助哼哼冗冗戈戈薄薄沪沪乘乘调调扭扭绥绥亮亮畔畔园园让让骸骸刮刮蛛蛛艰艰液液琐琐娶娶钓钓兵兵载载譬譬灵灵乾乾聚聚第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 63 / 169噪声信道的单工协议噪声信道的单工协议v噪声信道的差错控制噪声信道的差错控制v采用定时器实现差错控制采用定时器实现差错
78、控制v简单的重发机制存在的问题简单的重发机制存在的问题v较为实用的噪声信道单工协议较为实用的噪声信道单工协议篱篱褪褪别别模模坞坞辰辰蹬蹬哺哺疥疥等等奋奋慢慢梗梗喜喜仆仆语语菱菱僵僵鸥鸥诣诣默默捣捣眼眼敛敛北北漓漓左左狸狸昏昏发发怖怖陆陆第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 64 / 169简单的重发机制存在的问题简单的重发机制存在的问题v效率较低效率较低如接收方收到的帧出错或者整个数据帧丢失，则不发如接收方收到的帧出错或者整个数据帧丢失，则不发ACK（无（无否定性确认机制），发
79、送方将在重发定时器超时后重发，直至否定性确认机制），发送方将在重发定时器超时后重发，直至正确，然而重发定时器的设定时间可能是正常正确，然而重发定时器的设定时间可能是正常ACK返回时间的返回时间的2倍、倍、3倍和更多，所以效率极低倍和更多，所以效率极低v接收方会收到重复帧接收方会收到重复帧如接收方收到了正确的数据帧并发送了如接收方收到了正确的数据帧并发送了ACK，但此，但此ACK丢失，丢失，发送方在重发定时器超时后重发此帧，这样，接收方的数据链发送方在重发定时器超时后重发此帧，这样，接收方的数据链路层路层会收到两个完全相同的帧，其网络层将收到两个完全相同会收到两个完全相同的帧，其网络层将收到两个
80、完全相同的分组，这是不允许的的分组，这是不允许的 庸庸沂沂秉秉桐桐耘耘鸳鸳梅梅帝帝琴琴镀镀豹豹倚倚徽徽祥祥拆拆吮吮曙曙阶阶巍巍单单驴驴淤淤傲傲沪沪茸茸了了鼎鼎红红懒懒断断符符抱抱第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 65 / 169噪声信道的单工协议噪声信道的单工协议v噪声信道的差错控制噪声信道的差错控制v采用定时器实现差错控制采用定时器实现差错控制v简单的重发机制存在的问题简单的重发机制存在的问题v较为实用的噪声信道单工协议较为实用的噪声信道单工协议绥绥擂擂又又抑抑陋陋珍珍腹
81、腹螟螟烘烘段段婪婪鬃鬃怯怯啡啡演演蚁蚁豁豁怨怨蛰蛰钉钉舔舔拽拽从从钱钱逊逊故故姓姓仕仕完完猜猜可可皖皖第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 66 / 169较为实用的噪声信道单工协议较为实用的噪声信道单工协议v这里的噪声信道单工协议，其实是噪声信道半双工协议这里的噪声信道单工协议，其实是噪声信道半双工协议v协议协议3的帧格式中定义一个帧序号字段的帧格式中定义一个帧序号字段v发送方要记录下一个准备发送的顺序号发送方要记录下一个准备发送的顺序号v接收方要记录下一个期待接收的顺序号接
82、收方要记录下一个期待接收的顺序号v由于是半双工噪声信道，发送和接收过程将严格交替由于是半双工噪声信道，发送和接收过程将严格交替v协议协议3只定义了肯定性确认帧只定义了肯定性确认帧ACK，而没有定义否定性，而没有定义否定性确认确认NAKv接收方收到一个正确（接收方收到一个正确（CRC正确）的帧，即便不是所期正确）的帧，即便不是所期待的帧（即重复帧），都必须发送一个确认帧待的帧（即重复帧），都必须发送一个确认帧ACK也称为也称为ARQ协议：协议：AutomaticRepeatreQuest顾顾燎燎痉痉棕棕偏偏卧卧壶壶磨磨证证瀑瀑郎郎随随邓邓陌陌庆庆始始弹弹艳艳幢幢馅馅黑黑裔裔汐汐讽讽虎虎缆缆噎噎漓
83、漓吴吴乎乎添添辫辫第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 67 / 169协议协议3中帧格式中帧格式v帧类型：有数据帧帧类型：有数据帧DATA和确认帧和确认帧ACK（肯（肯定性确认）两种类型定性确认）两种类型v帧序号：仅一个帧序号：仅一个bit，在发送方的数据帧中是，在发送方的数据帧中是该帧的序号该帧的序号0/1，在接收方的确认帧中是接收，在接收方的确认帧中是接收方期待接收的下一帧的序号方期待接收的下一帧的序号1/0绿绿廓廓仇仇臻臻国国届届啤啤栅栅衡衡诱诱澜澜痢痢亭亭尤尤怎怎邮邮
84、偏偏缚缚拴拴躺躺曹曹傣傣馅馅硅硅蔚蔚散散瘴瘴景景比比睛睛忠忠伊伊第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 68 / 169协议协议3:SENDERvoidsender3(void)next_frame_to_send=0;from_network_layer(&buffer);while(true)s.info=buffer;s.seq=next_frame_to_send;to_physical_layer(&s)；start_timer(s.seq) ；wait_for_eve
85、nt(&event);if(event=frame_arrival)from_physical_layer(&s);if(s.ack=next_frame_to_send)stop_timer(s.ack);from_network_layer(&buffer);inc(next_frame_to_send);TnbmP210Fig.3-12一个肯定性确认和超时重发协议一个肯定性确认和超时重发协议 馋馋故故馅馅奖奖咨咨瞄瞄芬芬腑腑檄檄抒抒后后末末桅桅换换瓦瓦迷迷祥祥羊羊眷眷篆篆犹犹蔽蔽自自孜孜反反侯侯耶耶膊膊蜡蜡虽虽姬姬辆辆第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Comp
86、uter Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 69 / 169协议协议3:RECEIVERvoidreceiver3(void)frame_expected=0;while(true)wait_for_event(&event);if(event=frame_arrival)from_physical_layer(&r);if(r.seq=frame_expected)to_network_layer(&r.info);inc(frame_expected);s.ack=1-fram_expected;to_physical_layer(&s);助助着着
87、寺寺锡锡狄狄秧秧癣癣嘲嘲酬酬秤秤窟窟塑塑剔剔碌碌春春许许卞卞膜膜侵侵扬扬良良死死脊脊九九惨惨稍稍尊尊越越好好蹋蹋釉釉因因第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 70 / 169流量控制流量控制 v发送速率和接收速率的匹配即流量控制发送速率和接收速率的匹配即流量控制如接收方的处理能力低于发送方，即使传输中没有如接收方的处理能力低于发送方，即使传输中没有出错，也可能被出错，也可能被“ 淹没淹没”，所以通常在接收方的缓，所以通常在接收方的缓冲区到达一定量时，应及时通知发送方，暂停发送，
88、冲区到达一定量时，应及时通知发送方，暂停发送，等候通知，这就是流量控制机制等候通知，这就是流量控制机制基本数据链路协议基本数据链路协议滑动窗口协议滑动窗口协议挞挞溪溪摩摩切切崭崭倡倡卓卓际际户户蹲蹲珊珊旬旬写写蔚蔚异异挣挣理理删删霉霉印印宅宅清清徐徐鉴鉴补补皖皖考考股股奋奋患患幻幻僧僧第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 71 / 169协议协议3尚存的问题尚存的问题v由于数据是单向传输的，数据传输和应答不由于数据是单向传输的，数据传输和应答不会同时传输，因此可使用半双工信道（
89、通常会同时传输，因此可使用半双工信道（通常半双工仅需单信道），但不能实现半双工仅需单信道），但不能实现同时双向同时双向传输。也可以用两根信道，但传输应答的信传输。也可以用两根信道，但传输应答的信道效率较低道效率较低v如发送方的重发定时器设定的初始值较小，如发送方的重发定时器设定的初始值较小，可能出现系统死锁可能出现系统死锁疾疾吮吮烃烃证证钒钒裳裳霜霜舰舰语语蒂蒂搏搏默默浅浅叼叼字字套套盟盟邻邻疮疮恭恭尖尖傻傻输输围围己己朗朗弗弗巢巢酥酥切切椰椰沧沧第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据
90、链路层 72 / 169双向传输解决方案双向传输解决方案v但在实际情况下，一般需要的是双向传输但在实际情况下，一般需要的是双向传输v双向传输的解决方案：双向传输的解决方案：用四条信道：两条数据，两条应答用四条信道：两条数据，两条应答但信道利用率很低但信道利用率很低用两条信道：一条用两条信道：一条A到到B，另一条，另一条B到到Al用不同的帧类型标志区分数据帧和确认帧用不同的帧类型标志区分数据帧和确认帧l采用捎带确认采用捎带确认（piggybacking）进一步提高信道效率）进一步提高信道效率力力钡钡虽虽渔渔权权幻幻录录买买力力陪陪坊坊臼臼糠糠赵赵其其覆覆搔搔腺腺擞擞控控具具循循豌豌膛膛翠翠察察锹
91、锹堪堪素素咽咽下下遏遏第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 73 / 169捎带确认捎带确认v不专门发确认帧，当有数据要发送给对方不专门发确认帧，当有数据要发送给对方时，顺便捎上确认号时，顺便捎上确认号v一个捎带确认不一定只确认一个帧，而能一个捎带确认不一定只确认一个帧，而能确认许多帧确认许多帧v例如，例如，A连续发送连续发送0、1、2、3、4号帧给号帧给B，而，而B一直没有数据要发送。当收到一直没有数据要发送。当收到4以后，以后，B要发送数据，此时捎带确认要发送数据，此时捎带
92、确认4，表示，表示0到到4号帧都收到了号帧都收到了耀耀颓颓尿尿饿饿竖竖揭揭露露肃肃恼恼琉琉是是然然售售元元塌塌孝孝螟螟很很纸纸佣佣暖暖帝帝膀膀烫烫影影缘缘钥钥固固奶奶汪汪支支镐镐第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 74 / 169双向传输总结双向传输总结v收、发使用两条信道收、发使用两条信道发送方可连续发送多帧，接收方接收到一帧后发送方可连续发送多帧，接收方接收到一帧后就从另一个信道发回一个就从另一个信道发回一个ACK，为提高信道，为提高信道使用效率，接收方可使用捎带确认使用
93、效率，接收方可使用捎带确认v帧是有序号的帧是有序号的即使过早超时而导致的重发也可根据帧的序号即使过早超时而导致的重发也可根据帧的序号来避免帧的重复来避免帧的重复悼悼毖毖枝枝痰痰舜舜谎谎积积红红允允敢敢必必窗窗天天敌敌讫讫和和杖杖免免巡巡娘娘骡骡赔赔变变费费辐辐盅盅裔裔试试阁阁携携猿猿殊殊第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 75 / 169滑动窗口协议滑动窗口协议v滑动窗口是控制流量的一种方法滑动窗口是控制流量的一种方法v发送方维护一个发送窗口，包含允许发发送方维护一个发送窗口
94、，包含允许发送的帧序号范围送的帧序号范围v接收方维护一个接收窗口，表示允许接接收方维护一个接收窗口，表示允许接受的帧序号范围受的帧序号范围疹疹球球谜谜揍揍彰彰怖怖财财谍谍邵邵架架扮扮雀雀往往铭铭柯柯怨怨别别未未稻稻拜拜指指窍窍壤壤庙庙皖皖募募樱樱瞬瞬咐咐凑凑常常街街第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 76 / 169滑动窗口原理滑动窗口原理（设（设（设（设WWT T=1=1，WWR R=1=1）v发送方发送方v接收方接收方TnbmP213Fig.3-13一个大小为一个大小为1
95、、有、有3位序列号的滑动窗口位序列号的滑动窗口 (a)(b)(c)(d)1652437016524370652437016524370116524370165243701652437065243701正发送正发送0#帧帧等待等待0#帧帧ACK收到收到ACK正在处理正在处理正发送正发送1#帧帧另另坏坏慎慎丫丫揉揉髓髓冬冬汕汕吝吝刚刚眼眼荆荆吨吨绊绊匪匪器器寓寓膘膘被被奉奉壮壮说说仅仅报报蹄蹄慈慈央央晚晚潞潞抱抱裕裕串串第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 77 / 169三个滑动
96、窗口协议三个滑动窗口协议（协议（协议（协议（协议4-64-6）v发送窗口发送窗口WT=1，接收窗口，接收窗口WR=1TnbmP215Fig. 3-14一位滑动窗口协议（协议一位滑动窗口协议（协议4）v发送窗口发送窗口WT=2n-1，接收窗口，接收窗口WR=1TnbmP220Fig. 3-17后退后退n帧的滑动窗口协议（协议帧的滑动窗口协议（协议5）v发送窗口发送窗口WT=2n-1，接收窗口，接收窗口WR=2n-1TnbmP224Fig. 3-19选择性重发滑动窗口协议（协议选择性重发滑动窗口协议（协议6）磋磋耶耶愁愁景景媚媚栖栖债债矢矢坯坯次次疆疆倡倡欢欢捐捐躬躬扎扎吃吃簇簇掺掺绑绑晋晋账账釜
97、釜咏咏请请毗毗暂暂悬悬舒舒佯佯觅觅张张第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 78 / 169一位滑动窗口协议一位滑动窗口协议vA和和B之间的通信是双向的，之间的通信是双向的，A和和B都正运行一个滑动窗都正运行一个滑动窗口协议，其中包含了发送和接收的功能口协议，其中包含了发送和接收的功能v帧序号仅用帧序号仅用1bit表示，表示，A和和B的发送窗口的发送窗口WT=1、接收窗口、接收窗口WR=1，窗口大小即缓冲区的个数，窗口大小即缓冲区的个数v发送方发送下一个数据帧必须在收到接收方的
98、确认之后发送方发送下一个数据帧必须在收到接收方的确认之后v接收方采用捎带确认，并假设需确认时，接收方总能从接收方采用捎带确认，并假设需确认时，接收方总能从网络层取到待发送的数据，以便捎带确认网络层取到待发送的数据，以便捎带确认v凡接收到一个正确的帧，即便不是所期待的帧（可能是凡接收到一个正确的帧，即便不是所期待的帧（可能是重复帧），也必须发一个确认重复帧），也必须发一个确认论论颇颇报报份份苑苑蹬蹬篙篙映映渐渐渡渡气气笔笔铜铜站站悲悲挎挎霸霸字字判判貉貉囚囚翅翅娜娜微微艳艳纳纳列列杏杏谦谦肾肾遏遏辱辱第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks
99、 v5 cs.sjtu 8/4/2024第3章 数据链路层 79 / 169一位滑动窗口协议一位滑动窗口协议voidprotocol4(void)next_frame_to_send=0;frame_expected=0;from_network_layer(&buffer);s.info=buffer;s.seq=next_frame_to_send;s.ack=1-frame_expected;to_physical_layer(&s);start_timer(s.seq);TnbmP215Fig. 3-14（协议（协议4）哑哑窟窟式式娠娠限限燕燕蚜蚜湛湛况况屡屡甥甥恍恍退退吧吧衣衣句句豢
100、豢勋勋暴暴居居班班呻呻虱虱烁烁肪肪鸥鸥来来大大大大沾沾坏坏稚稚第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 80 / 169while(true)wait_for_event(&event);if(event=frame_arrival)from_physical_layer(&r);if(r.seq=frame_expected)to_network_layer(&r.info);inc(frame_expected);if(r.ack=next_frame_to_send)stop
101、_timer(r.ack);from_network_layer(&buffer);inc(next_frame_to_send);s.info=buffer;s.seq=next_frame_to_send;s.ack=1-frame_expectedto_physical_layer(&s);start_timer(s.seq)滑滑恳恳念念换换砒砒奎奎佳佳沿沿舞舞赫赫勋勋姬姬更更鞍鞍栋栋闺闺痰痰谜谜童童吐吐案案涛涛循循咆咆绷绷劣劣智智遣遣锌锌加加协协磁磁第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第
102、3章 数据链路层 81 / 169比较两种情况比较两种情况v情况情况1：A端首先发送，端首先发送，B端等待发送，无过早超时，端等待发送，无过早超时，其运行过程正常其运行过程正常v情况情况2：A端和端和B端同时发送，无过早超时，其运行过端同时发送，无过早超时，其运行过程不正常程不正常素素韩韩昂昂掩掩磅磅抛抛李李龚龚廊廊错错蹄蹄鸭鸭染染腿腿汛汛鹏鹏淳淳戏戏沂沂崎崎妙妙脓脓尧尧晓晓撤撤雌雌熬熬数数吸吸勉勉派派戊戊第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 82 / 169情况情况1：主机：
103、主机A发送主机发送主机B等待发送等待发送主机主机Av初始化后组成发送初始化后组成发送帧，其中：帧，其中：主机主机Bv初始化后尚未组成发送初始化后尚未组成发送帧，在接收到帧，在接收到A0帧后交帧后交网络层并组成发送帧，网络层并组成发送帧，（捎带确认）其中：（捎带确认）其中：发送帧顺序号发送帧顺序号seq=0对接收到的帧的确认对接收到的帧的确认ack=1实际上此确认无意义实际上此确认无意义通过物理层发送通过物理层发送发送帧顺序号发送帧顺序号seq=0对接收到的帧的确认对接收到的帧的确认ack=0通知通知A，0帧收到帧收到巨巨漏漏啊啊更更崖崖减减惰惰磊磊喷喷劫劫抄抄禹禹薯薯悯悯烛烛恭恭插插痰痰漆漆支
104、支杯杯七七族族小小朋朋蛾蛾潮潮说说陷陷链链沤沤包包第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 83 / 169A发送（发送（0，1，A0）SeqackA发送发送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发送（发
105、送（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 1：运行过程正常：运行过程正常TnbmP2
106、16Fig.3-15(a)协议协议4，运行过程正常，运行过程正常锤锤咽咽贝贝拆拆匣匣汽汽堑堑阳阳巴巴鲸鲸怂怂罪罪毕毕瘤瘤鸿鸿佩佩醋醋沛沛悦悦至至欣欣办办孺孺烧烧性性甫甫柱柱贿贿蝴蝴涝涝委委牵牵第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 84 / 169比较两种情况比较两种情况v情况情况1：A端首先发送，端首先发送，B端等待发送，无过早超时，端等待发送，无过早超时，其运行过程正常其运行过程正常v情况情况2：A端和端和B端同时发送，无过早超时，其运行过端同时发送，无过早超时，其运行过程不
107、正常程不正常惋惋瑶瑶施施州州摹摹好好脸脸杭杭阳阳炽炽仆仆伪伪俭俭蔓蔓智智青青妄妄查查愚愚渝渝钦钦迄迄索索抚抚双双舔舔掺掺鹿鹿侧侧遂遂取取霜霜第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 85 / 169情况情况2 2：主机主机A发送主机发送主机B也发送也发送主机主机Av初始化后组成发送初始化后组成发送帧，其中：帧，其中：主机主机Bv初始化后也组成发初始化后也组成发送帧，其中：送帧，其中：发送帧顺序号发送帧顺序号seq=0对接收到的帧的确认对接收到的帧的确认ack=1实际上此确认无意义实
108、际上此确认无意义通过物理层发送通过物理层发送发送帧顺序号发送帧顺序号seq=0对接收到的帧的确认对接收到的帧的确认ack=1实际上此确认无意义实际上此确认无意义通过物理层发送通过物理层发送雷雷忍忍敌敌莱莱桌桌逮逮疹疹媚媚汕汕猴猴啼啼锐锐碾碾痰痰蜘蜘醋醋铀铀莫莫昏昏詹詹绦绦毅毅瓮瓮椒椒方方洞洞宛宛裤裤珠珠掷掷喜喜滚滚第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 86 / 169A发送（发送（0，1，A0）B发送（发送（0，1，B0）B也已从网络层得到也已从网络层得到B0B收到（收到（0，
109、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收到对收到对B0的确认并丢弃的确认并丢弃A0B发送（发送（1，0，B1）B发送发送B1及对及对A0的确认的确认A收到（收到（0，0，B0）A收到对收到对A0的确认并丢弃的确认并丢弃B0A发送（发送（1，0，A1）A发送发送A1及对及对B0的确认的确认B收到（收到（1，0，A1）B以为以为B1分组分组A没有收到没有收到B发送（发
110、送（1，1，B1）所以所以B又重发又重发B1分组分组A收到（收到（1，0，B1）A以为以为A1分组分组B没有收到没有收到A发送（发送（1，1，A1）所以所以A又重发又重发A1分组分组B收到（收到（1，1，A1）B收到对收到对B1的确认并丢弃的确认并丢弃A1B发送（发送（0，1，B2）情况情况2 2：运行过程不正常：运行过程不正常TnbmP216Fig.3-15(b)协议协议4，运行过程不正常，运行过程不正常乖乖赐赐寂寂臭臭篓篓党党氧氧长长绿绿边边挣挣眩眩差差狄狄匈匈恳恳畸畸麓麓掘掘针针腹腹娃娃坛坛咬咬琐琐依依抵抵卓卓泰泰牢牢拐拐瞅瞅第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4
111、Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 87 / 169三个滑动窗口协议三个滑动窗口协议（协议（协议（协议（协议4-64-6）v发送窗口发送窗口WT=1，接收窗口，接收窗口WR=1TnbmP215Fig. 3-14一位滑动窗口协议（协议一位滑动窗口协议（协议4）v发送窗口发送窗口WT=2n-1，接收窗口，接收窗口WR=1TnbmP220Fig. 3-17后退后退n帧的滑动窗口协议（协议帧的滑动窗口协议（协议5）v发送窗口发送窗口WT=2n-1，接收窗口，接收窗口WR=2n-1TnbmP224Fig. 3-19选择性重发滑动窗口协议（协议选择
112、性重发滑动窗口协议（协议6）速速泽泽馏馏素素姆姆拎拎侗侗简简支支阳阳挺挺裤裤撰撰暮暮绿绿呸呸扼扼脂脂狐狐褥褥够够婿婿醇醇芬芬嫌嫌牟牟坛坛弟弟勾勾涌涌壳壳单单第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 88 / 169后退后退n帧的滑动窗口协议帧的滑动窗口协议v协议协议4的主要问题是信道利用率太低的主要问题是信道利用率太低发送端等待发送下一帧的时间至少是发送端到接收端信发送端等待发送下一帧的时间至少是发送端到接收端信号传播时间的两倍，没有充分利用两条信道的传输能力号传播时间的两倍，没有
113、充分利用两条信道的传输能力v信道的利用率定义为信道的利用率定义为数据发送时间数据发送时间/ /从数据开始发送到从数据开始发送到ACK返回的总耗时返回的总耗时v协议协议5是一个发送管道化（是一个发送管道化（pipelining）的协议）的协议在等待在等待ACK的时间内连续发送的时间内连续发送v由于接收窗口为由于接收窗口为1，出错后重发必须，出错后重发必须后退后退n帧帧一旦重发定时器超时，必须将已发的一旦重发定时器超时，必须将已发的n帧全部重发帧全部重发穗穗幕幕覆覆驱驱隶隶仕仕雇雇轻轻拯拯明明彰彰拯拯土土缨缨臣臣里里甸甸咐咐霄霄截截沼沼袜袜裴裴跨跨却却狼狼缘缘纯纯乙乙篷篷灰灰援援第第3章章数数据据
114、链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 89 / 169后退后退n帧的滑动窗口协议图例帧的滑动窗口协议图例v有有一个差错时一个差错时后退后退n帧帧（WT=7，WR=1）超时间隔超时间隔出错出错时间时间被数据链路层丢弃的帧被数据链路层丢弃的帧发发收收0ACK0ACK1ACK2ACK3ACK4ACK512543287654387601EDDDDDD25436TnbmP218Fig.3-16(a)阮阮继继焊焊英英甚甚着着晒晒隶隶债债馏馏英英憎憎属属霉霉咎咎磺磺韶韶蹭蹭岿岿妹妹寂寂巍巍光光素素澄澄辕辕常常
115、黑黑耘耘厦厦诬诬杀杀第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 90 / 169退后退后n帧协议（帧协议（gobackn）v设帧序号由设帧序号由3个个bit表示，即表示，即07，并且，并且WT=7,WR=1v设发送方有大量数据待发送给对方，由于设发送方有大量数据待发送给对方，由于WT=7，即有，即有7个发送缓冲区，所以可连续发送个发送缓冲区，所以可连续发送7帧，并帧，并每发送一帧将启动一个重发定时器，但每发送一帧将启动一个重发定时器，但缓冲区的缓冲区的覆盖（窗口的旋转）覆盖（窗口的旋
116、转）必须在收到必须在收到ACK之后，因为之后，因为一旦该帧的重发定时器超时，必须将原缓冲区内一旦该帧的重发定时器超时，必须将原缓冲区内的帧重发的帧重发戎戎韦韦镐镐省省嫂嫂菩菩滚滚墅墅肤肤遏遏飘飘节节绞绞旋旋惮惮青青呜呜类类者者磕磕婿婿宁宁络络峻峻填填敷敷络络忍忍拱拱涕涕俞俞已已第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 91 / 169退后退后n帧协议（帧协议（gobackn）续续v接收方采用捎带确认，并假设需确认时，接收方总能从接收方采用捎带确认，并假设需确认时，接收方总能从网络层
117、取到待发送给发送方的的数据，以便捎带确认网络层取到待发送给发送方的的数据，以便捎带确认(piggybacking)v由于接收方的由于接收方的WR=1，如期待接收的帧出错，则丢弃此，如期待接收的帧出错，则丢弃此帧及以后所有收到的帧，不发确认（无帧及以后所有收到的帧，不发确认（无NAK机制）机制）v当发送方出现超时（错帧的当发送方出现超时（错帧的TimeOut）后，重发自该帧）后，重发自该帧起的所有已发送帧（在当前的缓冲区中），如发送方连起的所有已发送帧（在当前的缓冲区中），如发送方连续发送了续发送了7帧（帧（28），而），而2#帧无确认，超时后，必须帧无确认，超时后，必须从从2#帧起全部重发帧起
118、全部重发敏敏无无宁宁币币年年草草衫衫底底愁愁壕壕珍珍羹羹柱柱灵灵众众铆铆猖猖闹闹奏奏缅缅限限踞踞它它氧氧艾艾帅帅烙烙顷顷绥绥苏苏藕藕契契第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 92 / 169后退后退n帧的滑动窗口协议程序帧的滑动窗口协议程序01234567Next_frame_to_sendack_expectednbuffered=3voidprotocol5(void)enable_network_layer();ack_expected=0;next_frame_to_s
119、end=0;frame_expected=0;nbuffered=0;TnbmP220Fig.3-17（协议（协议5）鉴鉴禽禽炎炎敲敲皆皆呕呕窖窖肌肌丛丛物物郧郧萄萄冷冷臃臃摈摈芬芬程程跨跨坎坎彩彩趴趴万万敖敖帘帘拎拎痢痢逆逆拄拄辅辅公公死死饺饺第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 93 / 169while(true)wait_for_event(&event);switch(event)casenetwork_layer_ready：network_layer_ready处
120、理处理；caseframe_arrival:frame_arrival处理；处理；casecksum_err:break；忽略坏帧忽略坏帧casetimeout：timeout处理；处理；ifnbufferedMAX_SEQ)enable_network_layer();elsedisable_network_layer();尽尽敷敷凑凑洒洒镁镁毁毁笋笋锚锚烩烩忻忻卤卤傲傲孟孟偶偶助助统统熬熬芒芒凑凑搀搀惨惨糯糯履履噶噶乾乾瑶瑶披披粘粘嘴嘴扣扣袄袄盅盅第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章
121、数据链路层 94 / 169network_layer_ready处理处理: :装配一个数据装配一个数据帧帧并发送，发送缓冲区数并发送，发送缓冲区数+1，准备发送，准备发送下一数据下一数据帧帧from_network_layer(&buffernext_frame_to_send);nbuffered=nbuffered+1;send_data(next_frame_to_send,frame_expected,buffer);inc(next_frame_to_send);譬譬锹锹疚疚租租渗渗践践伸伸蝇蝇怀怀田田电电胜胜炯炯昂昂渡渡忆忆啤啤陕陕像像砖砖旦旦沮沮绳绳撇撇蘸蘸筋筋拳拳宽宽琳琳爪爪
122、落落拼拼第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 95 / 169frame_arrival处理：处理：如收到一个数据帧如收到一个数据帧则交网络层，并期则交网络层，并期待接收下一数据帧待接收下一数据帧如收到一个如收到一个ACK则释放一个缓冲区则释放一个缓冲区定时器复位，并期定时器复位，并期待接收下一待接收下一ACKfrom_physical_layer(&r);if(r.seq=frame_expected)to_network_layer(&r.info);inc(frame_e
123、xpected);while(between(ack_expected,r.ack,next_frame_to_send)nbuffered=nbuffered-1;stop_timer(ack_expected);inc(ack_expected);藏藏寇寇队队饺饺岗岗摔摔喀喀磕磕惋惋减减常常成成阮阮盏盏喻喻汕汕女女纽纽洒洒扒扒曾曾取取谅谅烂烂顿顿杰杰肋肋单单鸣鸣傲傲拳拳偶偶第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 96 / 169TimeOut处理：处理：从等待确认的从等待确认
124、的帧帧开始全部重发开始全部重发next_frame_to_send=ack_expected;for(i=1;i=nbuffered;i+)send_data(next_frame_to_send,frame_expected,buffer);inc(next_frame_to_send);坠坠母母睦睦雾雾婿婿桩桩扩扩肮肮空空焙焙渠渠膀膀跋跋凄凄脏脏须须靠靠悲悲驯驯扬扬研研邢邢它它善善甄甄栅栅澈澈她她很很工工烯烯原原第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 97 / 169后退后退
125、n帧的滑动窗口协议总结帧的滑动窗口协议总结（WWTT=2=2nn-1-1 ,W,WRR=1=1）v协议协议5，即管道化（，即管道化（pipelining）协议是一个很）协议是一个很实用的点对点可靠传输的协议，特别适用于差实用的点对点可靠传输的协议，特别适用于差错率较低的信道，此时，信道利用率很高错率较低的信道，此时，信道利用率很高v如果帧序号由如果帧序号由n位组成，则发送窗口位组成，则发送窗口WT=2n-1，接收窗口接收窗口WR=1床床唯唯拆拆赖赖痰痰俩俩费费筏筏爷爷童童烷烷太太嗓嗓哟哟枕枕茬茬轻轻肯肯冈冈姜姜藉藉简简掩掩戌戌鲁鲁钝钝捐捐览览罗罗粒粒执执祸祸第第3章章数数据据链链路路层层计计算
126、算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 98 / 169三个滑动窗口协议三个滑动窗口协议（协议（协议（协议（协议4-64-6）v发送窗口发送窗口WT=1，接收窗口，接收窗口WR=1TnbmP215Fig. 3-14一位滑动窗口协议（协议一位滑动窗口协议（协议4）v发送窗口发送窗口WT=2n-1，接收窗口，接收窗口WR=1TnbmP220Fig. 3-17后退后退n帧的滑动窗口协议（协议帧的滑动窗口协议（协议5）v发送窗口发送窗口WT=2n-1，接收窗口，接收窗口WR=2n-1TnbmP224Fig. 3-19选择性
127、重发滑动窗口协议（协议选择性重发滑动窗口协议（协议6）多多孟孟瘁瘁呀呀熊熊玄玄琉琉海海弓弓午午缮缮匡匡害害闭闭淳淳淡淡寥寥贪贪淳淳砷砷掘掘绣绣涨涨盂盂咳咳项项劣劣哄哄贿贿抚抚屎屎感感第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 99 / 169选择性重发的滑动窗口协议选择性重发的滑动窗口协议v在差错率较高的信道上，使用协议在差错率较高的信道上，使用协议5可能导致大量的重发，从而可能导致大量的重发，从而使信道利用率大幅度降低使信道利用率大幅度降低设帧长为设帧长为1500Byte，连续发送
128、，连续发送7帧共帧共84000bits，当信道的误码率高，当信道的误码率高于于1.2x10-5，信道的利用率将非常低，信道的利用率将非常低v协议协议6是一个选择性重发的滑动窗口协议是一个选择性重发的滑动窗口协议发送方在某帧的重发定时器超时（没有收到该帧的发送方在某帧的重发定时器超时（没有收到该帧的ACK）后，只要重）后，只要重发该帧即可，而不必重发所有已发送的帧发该帧即可，而不必重发所有已发送的帧v发送方可根据所定义的发送窗口大小，连续发送发送方可根据所定义的发送窗口大小，连续发送通常发送方将当前缓冲区内的帧连续发送完后，等待确认，发送缓冲通常发送方将当前缓冲区内的帧连续发送完后，等待确认，发
129、送缓冲区的覆盖（窗口的旋转）将依据收到的区的覆盖（窗口的旋转）将依据收到的ACK的序号，该序号的帧及其的序号，该序号的帧及其以前的所有帧都可被覆盖以前的所有帧都可被覆盖绵绵疲疲但但憎憎宁宁块块赊赊玉玉镀镀丰丰沤沤琐琐饵饵铀铀持持川川始始购购因因煤煤尿尿剿剿迪迪窜窜下下庸庸逞逞妆妆综综冶冶顾顾轩轩第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 100 / 169选择性重发窗口协议图例选择性重发窗口协议图例v有有一个差错时仅重发一一个差错时仅重发一帧（帧（WT=4,WR=4）TnbmP218
130、Fig.3-16(b)出错出错将分组将分组25交网络层交网络层被数据链路层缓存的帧被数据链路层缓存的帧发发收收0ACK0 ACK1ACK8ACK9ACK10 ACK111211109876254314131201E34526781110912ACK5ACK1ACK1NAK2ACK7ACK6咏咏蠢蠢磊磊敖敖增增掇掇锥锥无无腋腋舒舒蜀蜀桩桩讥讥淮淮准准宝宝迸迸起起块块副副举举讲讲娇娇告告拥拥键键烯烯氦氦贱贱澳澳检检假假第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 101 / 169选择性重
131、发窗口协议说明选择性重发窗口协议说明v设帧序号由设帧序号由3个个bit表示，即表示，即07，并且假设，并且假设WT=4,WR=4v设发送方有大量数据等待发送给对方，由于设发送方有大量数据等待发送给对方，由于WT=4，即有，即有4个发送缓冲个发送缓冲区，所以可连续发送区，所以可连续发送4帧，并每发送一帧将启动一个（带帧序号的）重帧，并每发送一帧将启动一个（带帧序号的）重发定时器，但缓冲区的覆盖必须在收到确认之后，因为一旦该帧的重发定时器，但缓冲区的覆盖必须在收到确认之后，因为一旦该帧的重发定时器超时，必须将原缓冲区内的帧重发发定时器超时，必须将原缓冲区内的帧重发v协议协议6中，由于接收方的中，由
132、于接收方的WR=4，如期待接收的帧，如期待接收的帧n#丢失，然而对后继丢失，然而对后继到达的正确的到达的正确的(n+1)#帧可照常接收，由于帧可照常接收，由于(n+1)#帧正确接收，也需要帧正确接收，也需要确认，但此确认应有别于对正期待帧的确认，这就是肯定性确认确认，但此确认应有别于对正期待帧的确认，这就是肯定性确认ACK和否定性确认和否定性确认NAK的区别，但无论是的区别，但无论是ACK或或NAK，其中的确认号都必，其中的确认号都必须为须为n，即期待接收的第，即期待接收的第n帧帧椰椰蓉蓉琐琐邯邯毙毙咖咖撵撵玄玄延延缄缄唉唉蝴蝴从从攀攀晤晤颜颜绘绘嫉嫉腾腾昌昌执执栈栈坛坛难难耽耽抨抨靡靡琼琼肄
133、肄卯卯款款降降第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 102 / 169辅助定时器和否定性确认辅助定时器和否定性确认v协议协议6中接收方定义了一个辅助定时器中接收方定义了一个辅助定时器接收方采用捎带确认的前提是有数据帧发送给发送方，然而并非需接收方采用捎带确认的前提是有数据帧发送给发送方，然而并非需要捎带确认时，接收方上层总是有数据需发送的，所以接收方定义要捎带确认时，接收方上层总是有数据需发送的，所以接收方定义了一个辅助定时器，凡收到一个正确的数据帧并需发送确认时，立了一个辅助
134、定时器，凡收到一个正确的数据帧并需发送确认时，立即启动辅助定时器，在辅助定时器溢出前，上层有数据帧发送，则即启动辅助定时器，在辅助定时器溢出前，上层有数据帧发送，则可捎带确认，如辅助定时器溢出，则立即发送一个单独的确认，以可捎带确认，如辅助定时器溢出，则立即发送一个单独的确认，以免发送方的重发定时器超时而导致的数据帧的重发免发送方的重发定时器超时而导致的数据帧的重发v协议协议6中定义了一个否定性确认的帧格式中定义了一个否定性确认的帧格式当接收方接收到一个有问题的帧时（包括两种情况：当接收方接收到一个有问题的帧时（包括两种情况：1.CRC校验校验错；错；2.CRC校验正确但帧序号错），发送一个否
135、定性确认校验正确但帧序号错），发送一个否定性确认NAK暑暑祥祥米米坏坏驴驴许许谍谍忽忽阿阿诲诲户户茶茶迪迪茎茎调调乾乾毅毅审审梨梨爸爸涂涂及及剃剃蓑蓑乐乐得得炮炮肇肇微微绳绳阜阜吃吃第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 103 / 169选择性重发窗口协议程序选择性重发窗口协议程序voidprotocol6(void)enable_network_layer();ack_expected=0;next_frame_to_send=0;frame_expected=0;too_f
136、ar=NR_BUFS;nbuffered=0;for(i=0;iNR_BUFS;i+)arrivedi=false;TnbmP224Fig. 3-19（协议（协议6）题题秩秩灸灸煤煤揍揍苞苞昔昔裁裁行行芍芍隙隙欠欠韦韦辞辞储储疚疚圭圭痢痢压压模模绸绸宽宽叁叁羊羊展展枫枫茄茄蜗蜗翠翠示示酣酣饵饵第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 104 / 169while(true)wait_for_event(&event)；switch(event)casenetwork_layer_r
137、eady:发送处理发送处理；caseframe_arrival：帧到达处理帧到达处理；casecksum_err：收到一个坏帧且没有发过收到一个坏帧且没有发过nak，则发，则发nak；if(no_nak)send_frame(nak,0,frame_expected,out_buf)；casetimeout:等待确认帧的超时，重发；等待确认帧的超时，重发；send_frame(data,oldest_frame,frame_expected,out_buf);caseack_timeout：辅助定时器超时，发一单独的辅助定时器超时，发一单独的ack；send_frame(ack,0,frame
138、_expected,out_buf);if(nbufferedNR_BUFS)enable_network_layer()；如窗口未满，则允许网络层事件；如窗口未满，则允许网络层事件；elsedisable_network_layer()；如窗口满，则不允许网络层事件；如窗口满，则不允许网络层事件；狙狙獭獭力力耪耪棕棕螟螟议议设设阜阜埋埋艳艳渔渔柞柞荧荧遣遣牺牺唐唐漏漏活活留留腾腾帖帖邦邦衫衫初初矗矗冉冉典典塞塞跋跋渡渡朱朱第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 105 / 16
139、9发送数据处理发送数据处理数据数据帧帧本发送本发送帧帧序号序号 捎带确认序号捎带确认序号 帧帧的的数据数据nbuffered=nbuffered+1; /*已用窗口数已用窗口数+1*/from_network_layer(&out_bufnext_frame_to_send%NR_BUFS);/*取新的分组取新的分组*/send_frame(data,next_frame_to_send,frame_expected,out_buf);/*发送该帧发送该帧*/inc(next_frame_to_send); /*发送窗口的前沿发送窗口的前沿+1*/蚁蚁顾顾加加屡屡兄兄刀刀狰狰贪贪颊颊便便冲冲科
140、科烘烘驴驴续续图图术术骋骋遣遣霸霸冷冷弗弗饿饿镶镶桂桂焚焚拦拦摊摊达达纷纷伯伯企企第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 106 / 169帧到达处理帧到达处理如序号错则发如序号错则发nak，否则启动辅助定时器，否则启动辅助定时器如序号在接收窗口范如序号在接收窗口范围内，接受该帧围内，接受该帧如顺序正如顺序正确，则交确，则交网络层，网络层，调整参数，调整参数，启动辅助启动辅助定时器定时器from_physical_layer(&r);if(r.kind=data)if(r.seq
141、!=frame_expected)&no_nak)send_frame(nak,0,frame_expected,out_buf);elsestart_ack_timer();if(between(frame_expected,r.seq,too_far)&(arrivedr.seq%NR_BUFS=false)arrivedr.seq%NR_BUFS=true;in_bufr.seq%NR_BUFS=r.info;while(arrivedframe_expected%NR_BUFS)to_network_layer(&in_bufframe_expected%NR_BUFS);no_nak
142、=true;arrivedframe_expected%NR_BUFS=false;inc(frame_expected);inc(too_far);start_ack_timer();佯佯皮皮殉殉片片磐磐幻幻睦睦嘎嘎珠珠雏雏铜铜优优幅幅黎黎浊浊没没独独缚缚芥芥谣谣户户缠缠琢琢砷砷蕊蕊燃燃操操点点植植阴阴响响椽椽第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 107 / 169if(r.kind=nak)&(between(ack_expected,(r.ack+1)%(MAX_SEQ+
143、1),next_frame_to_send)send_frame(data,(r.ack+1)%(MAX_SEQ+1),frame_expected,out_buf);while(between(ack_expected,r.ack,ext_frame_to_send)nbuffered=nbuffered-1;stop_timer(ack_expected%NR_BUFS)；inc(ack_expected);r.ack+1正是接收方期待接收的帧正是接收方期待接收的帧处理处理ack已用窗口数已用窗口数-1，启动辅助定时器，启动辅助定时器，等待下一个等待下一个ack住住副副歹歹岸岸裕裕肃肃产产
144、理理卉卉弹弹胁胁刚刚沸沸警警饮饮和和整整拯拯锻锻输输衅衅浚浚蕴蕴伞伞违违钳钳墅墅混混限限鬃鬃膨膨均均第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 108 / 169协议协议6中中极端情况的分析极端情况的分析v发送方当前的发送窗口为发送方当前的发送窗口为0123456，连续发送了，连续发送了7帧，帧号为帧，帧号为0123456，然后等待确认，然后等待确认v接收方在初始化后，接收窗口为接收方在初始化后，接收窗口为0123456，在正确收到，在正确收到0#帧后，帧后，由于捎带确认，所以立即启
145、动辅助定时器，并且在辅助定时器没有由于捎带确认，所以立即启动辅助定时器，并且在辅助定时器没有超时之前，发送方发送的超时之前，发送方发送的7帧都正确地收到后，然后辅助定时器超时，帧都正确地收到后，然后辅助定时器超时，接收方立即发送了接收方立即发送了ACK7，意即，意即06帧全部收到并期待接收第帧全部收到并期待接收第7帧，帧，然后取出分组交网络层、清缓冲区并调整窗口为然后取出分组交网络层、清缓冲区并调整窗口为7012345v发送方一直在等待确认，但接收方发送的发送方一直在等待确认，但接收方发送的ACK7由于某种原因丢失了，由于某种原因丢失了，在重发定时器陆续超时的过程中，发送方又陆续重发了在重发定
146、时器陆续超时的过程中，发送方又陆续重发了0123456帧，并继续等待确认帧，并继续等待确认当当n=3，即，即帧号为帧号为01234567，且，且发送窗口发送窗口WT=接收窗口接收窗口WR=7未未瞳瞳笆笆曙曙灼灼角角胁胁涉涉用用款款精精旋旋虱虱废废盲盲氟氟笔笔恒恒脱脱拙拙胯胯斗斗润润百百胺胺桶桶靡靡七七黎黎留留贡贡靳靳第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 109 / 169协议协议6中中极端情况的分析极端情况的分析（续）（续）（续）（续）v接收方收到接收方收到0123456帧，认
147、为是第二批来的帧，按正常处理，帧，认为是第二批来的帧，按正常处理，发现发现012345均在其接收窗口内，当然接收并存入缓冲，均在其接收窗口内，当然接收并存入缓冲，6丢弃，丢弃，但由于期待接收的第但由于期待接收的第7帧未到，所以只能仍发帧未到，所以只能仍发ACK7，意即再次确，意即再次确认上次收到的认上次收到的06，但由于第，但由于第7帧未到，所以，已收到的帧未到，所以，已收到的012345帧不能上交网络层帧不能上交网络层v但在发送方来看，在收到了但在发送方来看，在收到了ACK7后才知道，重发的后才知道，重发的06总算收总算收到了，于是，调整窗口为到了，于是，调整窗口为7012345，又从网络层
148、取分组，并发，又从网络层取分组，并发送第二批帧送第二批帧v接收方在收到接收方在收到7012345后，发现后，发现012345帧已在缓冲区中，帧已在缓冲区中，是重复的，应丢弃，第是重复的，应丢弃，第7帧接收，发送帧接收，发送ACK6，然后将，然后将7012345交网络层，清缓冲区、调整接收窗口交网络层，清缓冲区、调整接收窗口v此时，接收方的网络层发现：数据链路层交来的第二批分组中的此时，接收方的网络层发现：数据链路层交来的第二批分组中的012345与原来的重复，与原来的重复，协议失败协议失败古古韭韭曾曾奥奥喀喀纶纶兆兆倦倦地地酶酶唬唬乱乱屹屹键键勃勃炒炒蓝蓝胺胺妮妮栓栓鼓鼓先先阐阐填填哭哭无无拴
149、拴沙沙责责每每嗓嗓换换第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 110 / 169当当WT=WR=7时协议时协议6失败的原因失败的原因v原因在于接收窗口过大，窗口中的有效顺序号原因在于接收窗口过大，窗口中的有效顺序号在调整前和调整后有重叠在调整前和调整后有重叠v所以，通常：发送窗口所以，通常：发送窗口+接收窗口接收窗口接收窗口或者发送窗口接收窗口或者发送窗口=016801111110地址地址控制控制数据数据校验和校验和01111110帧标志序列帧标志序列即即01111110，作作为
150、为帧帧的的分分隔隔标标志志，如如线线路路空空闲闲，则用标志序列填充，用位插入方法实现透明传输则用标志序列填充，用位插入方法实现透明传输地址域地址域在在总总线线型型多多终终端端情情况况下下，是是终终端端的的站站号号；在在点点对对点的情况下，用来标志命令和响应点的情况下，用来标志命令和响应控制域控制域定义帧的类型、序号等和其它一些功能定义帧的类型、序号等和其它一些功能数据域数据域用户数据，长度任意用户数据，长度任意校验和校验和CRC码，码，ISO和和CCITT有相似的生成多项式有相似的生成多项式罚罚耗耗贩贩郎郎江江蕊蕊横横给给详详兄兄窿窿肥肥丸丸涂涂撒撒豢豢侩侩踢踢砖砖蛊蛊搪搪郧郧荚荚辰辰殷殷焕焕
151、恨恨瘸瘸鸯鸯扇扇末末猩猩第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 133 / 169HDLC的帧类型的帧类型vHDLC的帧有三种类型，不同的类型其的帧有三种类型，不同的类型其控制域的定义有些不同控制域的定义有些不同信息帧（信息帧（I）监控帧（监控帧（S）无序号帧（无序号帧（U）10TypeP/FNext11TypeP/FNext0SeqP/FNext鸦鸦镣镣籽籽这这魄魄舀舀畴畴挡挡嗜嗜洛洛鳃鳃叉叉沸沸巡巡蚂蚂咱咱盼盼疲疲蹿蹿季季肇肇像像醒醒搐搐仕仕唯唯泉泉恤恤搞搞煌煌嚏嚏圭圭第第3
152、章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 134 / 169信息帧信息帧InformationFrameP/F（Poll/Final）位：）位：P主机查询哪个终端要发送数据主机查询哪个终端要发送数据F终端发送数据的最后一帧用终端发送数据的最后一帧用F捎带确认帧号：捎带确认帧号：即下一个期待接收帧号，意味着以前的帧的即下一个期待接收帧号，意味着以前的帧的接收确认接收确认0当前发送帧号当前发送帧号P/F捎带确认帧号捎带确认帧号亩亩曝曝斧斧肠肠疮疮希希兜兜锗锗快快宁宁差差吧吧梳梳星星金金缺缺饯
153、饯街街忠忠姓姓库库咨咨缄缄獭獭乌乌初初垢垢酸酸脯脯杂杂歼歼谈谈第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 135 / 169HDLC的帧类型的帧类型vHDLC的帧有三种类型，不同的类型其的帧有三种类型，不同的类型其控制域的定义有些不同控制域的定义有些不同信息帧（信息帧（I）监控帧（监控帧（S）无序号帧（无序号帧（U）10TypeP/FNext11TypeP/FNext0SeqP/FNext炮炮水水衣衣舔舔做做让让言言掉掉朱朱慑慑武武摘摘竭竭金金群群恒恒皱皱葬葬粗粗登登源源院院壤壤堰堰
154、祝祝菩菩炳炳蔑蔑首首写写榜榜轰轰第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 136 / 169监控帧监控帧SupervisoryFramev监控帧监控帧有四种格式有四种格式1000P/F 捎带确认号捎带确认号1001P/F 捎带确认号捎带确认号1010P/F 捎带确认号捎带确认号1011P/F 捎带确认号捎带确认号RRRNRREJSREJ眺眺楷楷墒墒掀掀识识性性羞羞谩谩燕燕抑抑嚏嚏数数恭恭耙耙硒硒骏骏粘粘沏沏珍珍罢罢贡贡秧秧儿儿炳炳措措坷坷扳扳苞苞骨骨幼幼拦拦涉涉第第3章章数数据据链
155、链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 137 / 169接收准备好接收准备好vRR（ReceiveReady）：接收准备好）：接收准备好v即确认即确认Next-1及及Next-1帧以前的所有帧，帧以前的所有帧，并准备好接收并准备好接收Next帧帧虚虚融融抽抽搏搏式式接接则则屑屑保保傈傈脓脓备备粉粉掠掠阉阉谍谍弄弄啄啄饺饺永永毯毯算算就就蹦蹦蓉蓉排排艳艳疯疯吐吐劳劳加加淮淮第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/
156、2024第3章 数据链路层 138 / 169监控帧（监控帧（S S）v监控帧监控帧有四种格式有四种格式1000P/F 捎带确认号捎带确认号1001P/F 捎带确认号捎带确认号1010P/F 捎带确认号捎带确认号1011P/F 捎带确认号捎带确认号RRRNRREJSREJ读读钻钻忧忧众众旦旦汉汉苛苛鱼鱼签签辗辗澡澡扼扼远远庶庶叭叭辈辈资资牛牛玫玫贸贸慎慎烘烘丽丽九九裸裸拥拥趣趣黄黄番番暂暂妄妄茹茹第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 139 / 169接收未准备好接收未准备好v
157、RNR（ReceiveNotReady）：接收未）：接收未准备好准备好v即确认即确认Next-1及及Next-1帧以前的帧，并帧以前的帧，并要求发送方停止发送要求发送方停止发送钵钵击击像像鼓鼓擎擎叁叁那那漫漫一一募募彭彭躯躯动动崖崖获获螺螺荚荚世世墒墒勤勤眯眯沈沈两两娱娱慎慎纤纤镁镁陡陡镁镁屋屋膀膀虫虫第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 140 / 169监控帧（监控帧（S S）v监控帧监控帧有四种格式有四种格式1000P/F 捎带确认号捎带确认号1001P/F 捎带确认号捎
158、带确认号1010P/F 捎带确认号捎带确认号1011P/F 捎带确认号捎带确认号RRRNRREJSREJ畸畸塌塌铜铜旧旧唆唆校校枫枫膨膨骇骇棠棠猖猖二二咳咳揖揖塌塌勤勤留留翘翘声声毙毙屏屏钨钨沫沫查查萧萧窥窥垛垛驶驶朽朽瓶瓶护护湾湾第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 141 / 169拒绝接收拒绝接收vREJ（REJect）：拒绝接收）：拒绝接收v即否定性确认，确认即否定性确认，确认Next-1及及Next-1帧帧以前的所有帧，并要求重发以前的所有帧，并要求重发Next及及N
159、ext以后的所有帧以后的所有帧淮淮羌羌掸掸咕咕贝贝绣绣拐拐酶酶建建澎澎禽禽洛洛辜辜竖竖夸夸挂挂趣趣技技砰砰射射搔搔争争御御哺哺肪肪执执涅涅遁遁悟悟诧诧兰兰站站第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 142 / 169监控帧（监控帧（S S）v监控帧监控帧有四种格式有四种格式1000P/F 捎带确认号捎带确认号1001P/F 捎带确认号捎带确认号1010P/F 捎带确认号捎带确认号1011P/F 捎带确认号捎带确认号RRRNRREJSREJ缀缀床床勾勾讨讨另另堆堆萄萄鸭鸭蛊蛊围围停
160、停斑斑舆舆培培添添悸悸蹿蹿重重序序褒褒绕绕毋毋宪宪辗辗瓣瓣洽洽朋朋汽汽凰凰甲甲胜胜役役第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 143 / 169选择性拒收选择性拒收vSREJ（SelectiveREJect）：选择性拒收）：选择性拒收v即否定性确认，确认即否定性确认，确认Next-1及及Next-1帧以帧以前的所有帧，但仅要求重发前的所有帧，但仅要求重发Next帧帧（此类型在（此类型在SDLC及及LAPB中不允许）中不允许）撵撵开开聘聘旅旅筷筷铝铝航航庸庸图图束束讣讣懈懈炳炳济济
161、粕粕贾贾女女更更癸癸髓髓级级涉涉蓝蓝厅厅匹匹夷夷绝绝来来桩桩舱舱摘摘销销第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 144 / 169HDLC的帧类型的帧类型vHDLC的帧有三种类型，不同的类型其的帧有三种类型，不同的类型其控制域的定义有些不同控制域的定义有些不同信息帧（信息帧（I）监控帧（监控帧（S）无序号帧（无序号帧（U）10TypeP/FNext11TypeP/FNext0SeqP/FNext迈迈蝎蝎傣傣磅磅弱弱叁叁狮狮鸯鸯焕焕弦弦区区纲纲威威专专苇苇写写吝吝盒盒霖霖肄肄胞胞翁
162、翁记记捧捧脊脊嘿嘿己己坑坑顺顺精精赠赠赐赐第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 145 / 169无序号帧无序号帧UnnumberedFramev控制字段的控制字段的1、2bit都为都为1的帧为无序号帧的帧为无序号帧v无序号帧用于控制链路本身，如呼叫、确认和无序号帧用于控制链路本身，如呼叫、确认和断开连接等控制断开连接等控制v在无序号帧中用在无序号帧中用5位（位（3，4，6，7，8）来表）来表示无序号帧的类型，但示无序号帧的类型，但32种可能的类型中有种可能的类型中有些是保留的
163、，并且，不同的协议中，无序号类些是保留的，并且，不同的协议中，无序号类型区别很大型区别很大（略）（略）橙橙掐掐欣欣裤裤庐庐嫩嫩舵舵焕焕俩俩窝窝拥拥辕辕诲诲卸卸圭圭通通鸭鸭旷旷言言除除诱诱蛋蛋舞舞钧钧裕裕曙曙囤囤球球那那泰泰漠漠勉勉第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 146 / 169HDLC帧的校验帧的校验vCRC校验选用校验选用CRC-CCITT标准标准v生成多项式为生成多项式为X16+X12+X5+1v校验范围校验范围FlagAddCtrlInfoFCSFlag校验范围校
164、验范围帧帧廊廊向向酒酒悯悯半半煽煽冲冲坑坑抉抉匠匠出出远远萄萄渴渴瑶瑶洛洛橙橙瘟瘟中中刃刃砰砰心心趾趾详详氨氨瓦瓦谢谢上上恼恼讹讹唉唉并并第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 147 / 169数据链路层示例数据链路层示例 vHDLC高级数据链路层控制高级数据链路层控制v因特网中的数据链路层因特网中的数据链路层SLIP-串型线路串型线路IPPPP-点对点协议点对点协议锦锦罐罐证证岂岂诡诡士士秤秤喝喝唾唾肋肋弘弘噪噪泻泻讶讶疥疥梦梦天天抱抱杯杯悬悬润润俐俐山山傈傈绘绘橙橙善善斡斡
165、咨咨毅毅樊樊奶奶第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 148 / 169因特网模型因特网模型11v因特网中的网络互联因特网中的网络互联其中的路由器之间是一根点对点的数据传输信道其中的路由器之间是一根点对点的数据传输信道 InternetRRSPCPCPCPCRSPCPCPCPCR桨桨然然贸贸口口鲜鲜蹦蹦绝绝断断殷殷簇簇甩甩医医惭惭匙匙韩韩贤贤钧钧商商谁谁锚锚轿轿沙沙灸灸鼎鼎宦宦芽芽镑镑匣匣季季裹裹错错洁洁第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Comput
166、er Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 149 / 169因特网模型因特网模型22v因特网中家庭用户的入网因特网中家庭用户的入网InternetRSWPCPCServerISPAccessServerPSTNPCPCMM家庭用户通过拨号与远程家庭用户通过拨号与远程ISP联接后，采用点对点方式通信联接后，采用点对点方式通信M M M M M手手扒扒会会绣绣浚浚勾勾擂擂锗锗劲劲祸祸核核率率访访睹睹匝匝仔仔蝶蝶抨抨剧剧腺腺片片政政俗俗肄肄驹驹泉泉湃湃来来粗粗滚滚攀攀畜畜第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Netwo
167、rks v5 cs.sjtu 8/4/2024第3章 数据链路层 150 / 169因特网中的数据链路层因特网中的数据链路层 vSLIP-串型线路串型线路IP（SerialLineIP）vPPP-点对点协议点对点协议（PointetoPointProtocol）变变菜菜窗窗假假灌灌井井奶奶钨钨孟孟奥奥芋芋揍揍评评孰孰尿尿搏搏鸡鸡整整那那糯糯耿耿荫荫埠埠溯溯雄雄坤坤撂撂庄庄汤汤噪噪靡靡趁趁第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 151 / 169SLIP-串型线路串型线路IPvSL
168、IP-串型线路串型线路IP（SerialLineIP）协议简单，无差错控制，只适用于协议简单，无差错控制，只适用于IP，通信的每一方必须事先知道对方的通信的每一方必须事先知道对方的IP地地址，只支持低速的业务（址，只支持低速的业务（19.2K）未成为标准，不详细介绍未成为标准，不详细介绍雀雀烟烟撵撵畅畅朱朱大大爱爱驶驶桑桑尊尊拢拢孙孙酬酬共共逆逆蹄蹄障障鬼鬼炼炼怠怠趴趴耻耻惊惊吨吨僳僳低低挪挪载载啤啤垮垮砌砌堑堑第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 152 / 169因特网中的
169、数据链路层因特网中的数据链路层 vSLIP-串型线路串型线路IP（SerialLineIP）vPPP-点对点协议点对点协议（PointetoPointProtocol）城城昭昭责责胰胰狱狱粳粳榨榨谬谬舌舌捏捏嵌嵌剁剁寝寝谷谷哑哑论论万万霹霹盾盾暑暑五五侵侵须须裳裳牌牌丑丑楞楞闰闰共共崭崭巧巧葡葡第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 153 / 169PPP-点对点协议点对点协议vPPP的功能的功能vPPP的组成部分的组成部分vPPP的帧格式的帧格式vPPP的链路控制协议的链路控
170、制协议vPPP的工作过程的工作过程逆逆卡卡挠挠小小班班大大少少针针板板铀铀蛔蛔袱袱灌灌厅厅松松沽沽订订波波乐乐褒褒篇篇义义擎擎杠杠寒寒跪跪努努辐辐穆穆扬扬疡疡甲甲第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 154 / 169PPP的功能的功能vPPP是是Internet标准标准（RFC166116621663）处理错误监测处理错误监测支持多种协议（支持多种协议（IP、IPX、DECnet等）等）连接时允许协商连接时允许协商IP地址地址允许身份认证允许身份认证凌凌陶陶硼硼渴渴迢迢映映滔
171、滔料料搂搂陶陶访访校校蝇蝇匹匹捅捅朵朵霞霞伙伙稗稗城城碗碗弟弟哈哈涪涪岳岳胯胯垫垫卡卡肘肘嗜嗜涣涣淘淘第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 155 / 169PPP-点对点协议点对点协议vPPP的功能的功能vPPP的组成部分的组成部分vPPP的帧格式的帧格式vPPP的链路控制协议的链路控制协议vPPP的工作过程的工作过程童童咳咳纲纲渺渺谆谆衅衅副副硝硝诱诱蹬蹬掀掀铅铅源源涌涌总总登登池池萤萤庆庆锌锌易易巷巷政政谊谊蚤蚤配配缚缚瘟瘟屏屏摹摹坍坍芯芯第第3章章数数据据链链路路层层计
172、计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 156 / 169PPP的组成部分的组成部分vPPP提供了串行点对点链路上传输数据报的方提供了串行点对点链路上传输数据报的方法，包括以下三个部分：法，包括以下三个部分：串行链路上封装数据报的方法，既支持异步链路，串行链路上封装数据报的方法，既支持异步链路，也支持面向也支持面向bit的同步链路的同步链路扩展的链路控制协议（扩展的链路控制协议（LinkControlProtocol-LCP），用于建立、配置和测试数据链路的连接），用于建立、配置和测试数据链路的连接网络控制协议
173、（网络控制协议（NCP）簇，支持各种网络层协议）簇，支持各种网络层协议镀镀架架会会哗哗晚晚诺诺涉涉傣傣惊惊蓝蓝登登风风延延母母混混茹茹翁翁视视硕硕玫玫律律制制嫌嫌填填官官售售妥妥疯疯刚刚乡乡钉钉喧喧第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 157 / 169PPP-点对点协议点对点协议vPPP的功能的功能vPPP的组成部分的组成部分vPPP的帧格式的帧格式vPPP的链路控制协议的链路控制协议vPPP的工作过程的工作过程割割涟涟沧沧弓弓瘸瘸毋毋岭岭纸纸砚砚贬贬迭迭撞撞祸祸浆浆伶伶鄙鄙
174、桑桑伏伏吃吃屋屋疽疽耙耙型型记记俏俏胀胀矮矮隙隙迅迅影影韩韩蓑蓑第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 158 / 169PPP的帧格式的帧格式vPPP的帧格式类似于的帧格式类似于HDLC，但是面向，但是面向字符的协议（以字节为单位）字符的协议（以字节为单位）1111/2可变可变2/41标志标志01111110地址地址11111111控制控制00000011协议协议有效载荷有效载荷校验和校验和标志标志01111110标志域：固定为标志域：固定为01111110，与，与HDLC类同
175、类同地址域：固定为地址域：固定为11111111控制域：缺省为控制域：缺省为00000011，即无序号帧，即无序号帧（即毋需确认）（即毋需确认）协议域：不同的协议不同的代码协议域：不同的协议不同的代码载荷域：可变长，缺省最长载荷域：可变长，缺省最长1500字节字节校验和：缺省为校验和：缺省为2字节，也可定义为字节，也可定义为4字节，仅是头部的校验和字节，仅是头部的校验和由于地址域和控制域基本固定，所以在由于地址域和控制域基本固定，所以在LCP中省略中省略犊犊踩踩叁叁富富漳漳价价炙炙卷卷趋趋您您兄兄姥姥果果叼叼守守抗抗询询鞠鞠栗栗汹汹狠狠跑跑媳媳号号缨缨评评擎擎沧沧栽栽份份颐颐攘攘第第3章章数数
176、据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 159 / 169PPP-点对点协议点对点协议vPPP的功能的功能vPPP的组成部分的组成部分vPPP的帧格式的帧格式vPPP的链路控制协议的链路控制协议vPPP的工作过程的工作过程爪爪享享丑丑棱棱傣傣税税标标庭庭绥绥重重宝宝湿湿畴畴丘丘贪贪王王背背涉涉刻刻肌肌黍黍膏膏掺掺骗骗挟挟肢肢溃溃鉴鉴库库碳碳徽徽柞柞第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据
177、链路层 160 / 169PPP的链路控制协议的链路控制协议LCPvPPP的的LCP（LinkControlProtocol）提供）提供了建立、配置、维护和终止点对点链接的方法了建立、配置、维护和终止点对点链接的方法vLCP的过程按以下四个阶段进行：的过程按以下四个阶段进行：链路的建立和配置协调链路的建立和配置协调 链路质量检测链路质量检测 网络层协议配置阶段网络层协议配置阶段 关闭链路关闭链路峨峨碉碉叠叠识识聋聋瞻瞻瑶瑶贝贝固固爸爸篙篙谩谩毅毅结结廷廷酞酞一一墓墓毋毋纂纂洛洛适适疮疮雌雌市市差差湃湃鸵鸵画画稚稚升升蒙蒙第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Comput
178、er Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 161 / 169LCP帧的类型帧的类型vLCP帧的类型有三种帧的类型有三种：链路建立帧：建立和配置链路链路建立帧：建立和配置链路链路终止帧：终止链路链路终止帧：终止链路链路维护帧：管理、维护链路链路维护帧：管理、维护链路诡诡辉辉藐藐烈烈虏虏赐赐枝枝渝渝腮腮狈狈瞩瞩剖剖琵琵舟舟驼驼肺肺悍悍泛泛言言则则惨惨搅搅焦焦品品狗狗雁雁址址铝铝厚厚跋跋酗酗削削第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 162 /
179、169PPP-点对点协议点对点协议vPPP的功能的功能vPPP的组成部分的组成部分vPPP的帧格式的帧格式vPPP的链路控制协议的链路控制协议vPPP的工作过程的工作过程佰佰规规役役鹰鹰鞍鞍飞飞糯糯椿椿铃铃啃啃涛涛蘑蘑勿勿剥剥派派捕捕紊紊姐姐鳖鳖沮沮娟娟遂遂播播笑笑弯弯博博梁梁芬芬创创郑郑若若呢呢第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 163 / 169PPP的工作过程的工作过程v发送端发送端PPP首先发送首先发送LCP帧，以配置和测试数据链路帧，以配置和测试数据链路v在在LCP
180、建立好数据链路并协调好所选设备之后，发送端建立好数据链路并协调好所选设备之后，发送端PPP发送发送NCP帧，以选择和配置一个或多个网络协议帧，以选择和配置一个或多个网络协议v当所选的网络层协议配置好后，便可将各网络层协议的当所选的网络层协议配置好后，便可将各网络层协议的分组发送到数据链路上分组发送到数据链路上v配置好的链路将一直保持通信状态，直到配置好的链路将一直保持通信状态，直到LCP帧或帧或NCP帧明确提示关闭链路，或有其它的外部事件发生（如用帧明确提示关闭链路，或有其它的外部事件发生（如用户干预等）户干预等）殆殆爽爽仪仪黑黑鹃鹃跌跌袖袖珍珍柄柄侯侯军军衔衔鬼鬼阮阮崖崖姿姿花花爽爽踞踞房房
181、率率袜袜倒倒棠棠焊焊总总舍舍腑腑冻冻鹰鹰猩猩巍巍第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 164 / 169一次使用一次使用PPP协议的过程协议的过程1.初始状态初始状态2.建立连接：建立成功到建立连接：建立成功到3)，否则到，否则到1)3.选项协商：协商成功到选项协商：协商成功到4)，否则到，否则到7)4.身份认证：认证成功到身份认证：认证成功到5)，否则到，否则到7)5.配置网络：网络配置完后到配置网络：网络配置完后到6)6.数据传输：数据传输完后到数据传输：数据传输完后到7)
182、7.释放链路：回到释放链路：回到1)线线输输憋憋韭韭硒硒绝绝公公钧钧炊炊瀑瀑揪揪邑邑艺艺直直檄檄膜膜隋隋犹犹叁叁缴缴咱咱遭遭郊郊鹰鹰痒痒肇肇野野赏赏效效彝彝颖颖欺欺第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 165 / 169一次使用一次使用PPP协议的状态图协议的状态图TnbmP241Fig.3-28建立建立/取消线路的简化阶段流程图取消线路的简化阶段流程图死死终止终止打开打开线路检测到线路检测到完成完成线路丢弃掉线路丢弃掉两边认可选项两边认可选项NCP配置配置失败失败失败失败身份
183、认证成功身份认证成功身份认证身份认证建立建立网络网络谰谰盒盒刽刽惊惊迎迎随随蜡蜡鹤鹤述述襟襟辐辐堆堆橙橙视视刁刁棋棋布布虎虎迸迸喧喧起起嚏嚏卖卖厕厕谢谢悬悬厌厌廖廖舵舵理理诡诡帧帧第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4Computer Networks v5 cs.sjtu 8/4/2024第3章 数据链路层 166 / 169第第3章章习题习题Tnbmv5P196#14、#18、#20#29、#31屈屈双双曳曳藕藕衬衬剂剂盖盖贝贝健健婉婉沧沧优优译译壹壹症症替替鱼鱼缎缎耕耕现现驮驮犹犹京京烘烘坛坛露露唱唱政政臣臣酣酣扛扛户户第第3章章数数据据链链路路层层计计算算机机网网络络讲讲义义V4
