北京邮电大学《计算机网络》3.ppt
《北京邮电大学《计算机网络》3.ppt》由会员分享,可在线阅读,更多相关《北京邮电大学《计算机网络》3.ppt(180页珍藏版)》请在三一文库上搜索。
1、Computer Network 计算机网络,北京邮电大学 计算机学院 王小茹,课件制作人:王小茹,THE DATA LINK LAYER 第3章 数据链路层,数据链路的目的:在不可靠物理链路实现无差错、高质量的数据传输。,课件制作人:王小茹,内容提要,3.1 数据链路层的基本功能 3.2 错误检测和纠正 3.3 停止等待协议 3.3.1 完全理想化的数据传输 3.3.2 具有最简单流量控制的数据链路层协议 3.3.3 实用的停止等待协议,课件制作人:王小茹,内容提要,3.4 滑动窗口 协议 3.3.1 1位滑动窗口协议 3.3.2 Go back n滑动窗口协议 3.3.3 选择性重传滑动窗
2、口协议 3.3.4 信道利用率与最佳帧长 3.6 数据链路层协议实例(PPP/HDLC),3.1 数据链路层的基本原理,链路(Link): 一条无源的点到点的物理线路段,中间没有任何其他的交换结点。 数据链路(Data Link) : 协议链路。 在不可靠的物理链路上实现可靠的传输。,课件制作人:王小茹,基本术语,结点(node):网络中的主机(host)和路由器(router)称为结点。 端到端(end to end):从源结点(source node)到目的结点(destination node)的通信称为端到端通信,通信路径(path)可能由多个链路组成。 点到点(point to po
3、int):在相邻结点间的一条链路上的通信称为点到点通信。,课件制作人:王小茹,点到点,端到端,端到端,点到点,课件制作人:王小茹,数据链路层的主要功能,课件制作人:王小茹,课件制作人:王小茹,本章中数据链路层协议的位置,实际数据通路(host1 to host2),虚拟数据通路 (host1 to host2),3.1.1 为网络层提供的服务,无确认无连接的服务 适用于误码率很低的通信信道,或实时通信; 有确认无连接的服务 适用于误码率很高的通信信道,如无线通信; 有确认面向连接的服务 适用于通信要求较高的情况。,课件制作人:王小茹,帧同步/成帧/framing,数据链路层的同步方法,课件制作
4、人:王小茹,课件制作人:王小茹,课件制作人:王小茹,位同步:自同步,物理层编码违例法 只适用于物理层编码有冗余的网络 802 LAN:曼彻斯特编码或差分曼彻斯特编码用high-low pair/low-high pair表示1/0,high-high/low-low不表示数据,可以用来做定界符。,课件制作人:王小茹,课件制作人:王小茹,3.1.2 帧同步/成帧(framing),成帧:将原始的比特流分解成若干离散的“段”中。 常常在两个对等的数据链路层之间画出一个数字管道,而在这条数字管道上传输的数据单位是帧(frame)。,课件制作人:王小茹,课件制作人:王小茹,成帧的方法,字符计数法 带字
5、符填充的首尾字符定界法 带位填充的首尾标记定界法,课件制作人:王小茹,成帧的方法(1),字符计数法 在帧头中用一个域来表示整个帧的字符个数 缺点:若计数出错,对本帧和后面的帧有影响,帧1,帧2,帧3,帧4,帧1,帧2,错误,错误的字符计数,课件制作人:王小茹,成帧的方法(2),带字符填充的首尾字符定界法,课件制作人:王小茹,挑挑毛病!,课件制作人:王小茹,成帧的方法(3),课件制作人:王小茹,总结:帧同步的方法,课件制作人:王小茹,我暂停一下,你思考一个问题?,物理层的同步和数据链路层同步的区别? 那个更“精确”? 实际网络中,使用什么样的帧同步方式?,课件制作人:王小茹,课后思考:,1.帧的
6、长度固定与可变时,帧的同步方法是否相同? 2.SONET帧的帧同步方法? 3.帧同步是否违背了层次化设计原则?,课件制作人:王小茹,3.2 差错检测和纠正,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,差错控制的基本方式,反馈纠错 在接收端能发现差错(检错),但不能确定错码的位置,通过反馈信息请求发送端重发,直到接收端肯定确认为止。 适用于双工通信和非实时通信系统。 前向纠错 在接收端不仅能发现错码(纠错),而且还能确定错码的位置,并纠正错误。 适用于单工通信和实时通信系统。 混合纠错 少量差错在接收端自动纠正,若超出自行纠正能力时,通过反馈信息请求发送端重发。,课件制作人:王小
7、茹,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,热身:计算纠错码的冗余位数,要求:m个信息位,r个冗余位(校验位),纠正单比特错;(m + r = n) 对2m个有效信息中任何一个,有n个与其距离为1的无效码字,因此有:(n + 1) 2m 2n 利用 n = m + r,得到 (m + r + 1) 2r。给定m,利用该式可以得出校正单比特误码的校验位数目的下界 实践一下:4个信息位,需要至少多少个冗余位可用来纠错1比特的编码?,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,课件制作
8、人:王小茹,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,如何纠正突发性错误,课件制作人:王小茹,大家辛苦一小下!,1、2、3、4、5 9、11、12、14、15、16,课件制作人:王小茹,课件制作人:王小茹,3.3 基本数据链路层协议,停止等待协议 Stop and Wait Protocols,课件制作人:王小茹,1.如何设计数据链路层的协议?,课件制作人:王小茹,2.建立一个数据链路层通信模型,假设 物理层、数据链路层和网络层都是独立的进程; 点到点的链路中所有的节点都不会崩溃; 数据链路层使用数据帧(Frame),网络层
9、使用分组(Packet); 数据链路层只处理信道上的事务。,Protocol Definitions p202,Continued ,Some definitions needed in the protocols to follow. These are located in the file protocol.h.,Protocol Definitions (2),Some definitions needed in the protocols to follow. These are located in the file protocol.h.,3.3.1 完全理想化的单工传输协议,数
10、据链路层,主 机 A,缓存,主 机 B,数据链路,AP2,AP1,缓存,发送方,接收方,帧,高层,帧,课件制作人:王小茹,完全理想化的数据传输 所基于的两个假定,课件制作人:王小茹,3.3.2 一个单工的停等协议,现在去掉上述的第二个假定。但是,仍然保留第一个假定: 主机 A 向主机 B传输数据的信道仍然是无差错的理想信道。 然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。,课件制作人:王小茹,简单的停等协议 (A Simplex Stop-and-Wait Protocol),增加约束条件: 接收方不能无休止接收。 解决办法: 发送方:send stop wait
11、接收方: receive ack wait 每收到一个帧后,给发送方回送一个响应。,由收方控制发方的数据流,乃是计算机网络中流量控制的一个基本方法。,课件制作人:王小茹,两种情况的对比(传输均无差错),不需要流量控制,需要流量控制,课件制作人:王小茹,具有最简单流量控制的 数据链路层协议算法,课件制作人:王小茹,具有最简单流量控制的 数据链路层协议算法,课件制作人:王小茹,3.3.3 实用的停止等待协议(ARQ:Automatic Repeat Quest),差错如何控制?,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,帧的首部设计:帧的编号问题,任何一个编号
12、系统的序号所占用的比特数一定是有限的。因此,经过一段时间后,发送序号就会重复。 序号占用的比特数越少,数据传输的额外开销就越小。 序号位的多少取决于是否能够确保接收端不会出现接收重复帧即可。,课件制作人:王小茹,课件制作人:王小茹,实用的停止等待协议,时 间,A,B,送 主 机,ACK,送 主 机,ACK,(a) 流量控制,四种情况,课件制作人:王小茹,课件制作人:王小茹,这个杀手不太冷!,协议在设计上有小瑕疵!,课件制作人:王小茹,课件制作人:王小茹,停止等待协议的算法(2),这里不使用否认帧(实用的数据链路层协议大都是这样的),而且确认帧带有序号 n。,Why?,课件制作人:王小茹,网络研
13、究中心:王小茹,课件制作人:王小茹,停止等待协议 ARQ 的优缺点,优点:比较简单 。 缺点:通信信道的利用率不高,也就是说,信道还远远没有被数据比特填满。 为了克服这一缺点,就产生了另外两种协议,即连续 ARQ (GO BACK N)和选择重传 ARQ。这将在后面进一步讨论。,课件制作人:王小茹,课件制作人:王小茹,3.4 滑动窗口协议,1 bit 滑动窗口协议 Go Back N Protocol Selective Protocol,课件制作人:王小茹,学习目标,捎带确认的原理及产生的原因? 滑动窗口协议的原理和产生的原因? 1 比特滑动窗口协议的算法原理? 回退N帧协议和选择重传协议的
14、算法原理? 发送窗口/接收窗口的大小? 协议的效率如何衡量?,课件制作人:王小茹,预备知识:改进Protocol 3,单工 全双工的改造 两条信道 一条链路; 设备改造成全双工工作模式; 捎带/载答(piggybacking): 数据帧和应答帧在一个信道上传输; 暂时延迟待发确认,以便附加在下一个待发数据帧的技术。优点:充分利用信道带宽,减少帧的数目意味着减少“帧到达”中断; 缺点:复杂。,如何把单工的设备改造成双工的设备?,课件制作人:王小茹,3.4.1 1比特滑动窗口协议 (A One Bit Sliding Window Protocol),协议特点 可进行数据双向传输,信息帧中可含有确
15、认信息(piggybacking技术); 信息帧中包括两个序号域:发送序号和接收序号(已经正确收到的帧的序号) 工作过程,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,课件制作人:王小茹,协议4:问题仍旧相同,能保证无差错传输,但是基于停等方式; 若双方同时开始发送,则会有一半重复帧; 效率低,传输时间长。,信道的效率提高,管道技术,课件制作人:王小茹,假若:没有信道的延迟,如果没有延迟,则发送端等待发送的下一帧的时间 = Tf; 在没有差错的情况下,则发送帧是 Back to Back方式,课件制作人:王小茹,存在延迟: 利用时延带宽积来考虑效率,存在延迟,
16、则发送端每发送完一帧,帧在信道上传输,延迟越大,到达对端的时间越长,就像在一个很长的“管道”中经过; 延迟 “管道”的长度 为了提高效率,应该使得信道充满比特。,课件制作人:王小茹,如何提高信道的传输效率?,例如: 卫星信道传输速率50kbps,往返传输延迟500ms,若传长度为1000bit的帧。 使用协议4,则传输一个帧所需时间为: 发送时间 + 信息信道延迟 + 确认信道延迟(确认帧很短,忽略发送时间)= 1000bit / 50kbps + 250ms + 250ms = 520ms 信道利用率 = 20 / 520 4%,课件制作人:王小茹,IMAGINATION!,发送端一次连续发
17、送26个数据帧; 经历的时间是520ms; 此时刚好第1帧的应答帧回来了! 发送端又可以发送1个新帧了! 流水线诞生了!,课件制作人:王小茹,小结:,一般情况,信道带宽b比特/秒,帧长度L比特,往返传输延迟R秒,则信道利用率为 (L/b) / (L/b + R) = L / (L + Rb) 结论 传输延迟大,信道带宽高,帧短时,信道利用率低。 解决办法 连续发送多帧后再等待确认,称为流水线技术(pipelining)。 带来的问题 信道误码率高时,对损坏帧和非损坏帧的重传非常多,课件制作人:王小茹,3.4.2 使用回退N帧技术的协议,GO BACK N,课件制作人:王小茹,课件制作人:王小茹
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机网络 北京 邮电大学
链接地址:https://www.31doc.com/p-3052386.html