北京邮电大学《计算机网络》

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,课件制作人：王小茹,课件制作人：王小茹

18、,预备：滑动窗口技术,发送窗口、接收窗口 上限、下限,课件制作人：王小茹,1.滑动窗口的概念,发送端和接收端分别设定发送窗口和接收窗口 。 发送窗口用来对发送端进行流量控制。 发送窗口的大小 WS 代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。,0,1,2,3,4,5,6,7,0,1,2,发送窗口,WS,不允许发送这些帧,允许发送 5 个帧,(a),课件制作人：王小茹,接收端设置接收窗口,在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。 若接收到的数据帧落在接收窗口之外，则一律将其丢弃。 在GO BACK N 协议中，接收窗口的大小 WR = 1。

19、 只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。 每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。,不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,准备接收 0 号帧,(a),课件制作人：王小茹,滑动窗口的重要特性,只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。 收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。 当发送窗口和接收窗口的大小都等于 1时，就是双工的停止等待协议。,课件制作人：王小茹,窗口的一种表示方法,发送窗口 上限：next_frame_to

20、_send 下限： ack_expected r.ack 接收窗口 Frame_expected s.seq,发送窗口示例,课件制作人：王小茹,接收窗口示例,课件制作人：王小茹,GO BACK N协议实现分析,事件驱动 Network_layer_ready（内部事件） 发送帧（帧序号，确认序号，数据） Frame_arrival （外部事件） 检查帧序号，落在接收窗口内则接收，否则丢弃； 检查确认序号，落在发送窗口内则移动发送窗口，否则不做处理。 Cksum_err （外部事件） 丢弃 timeout （内部事件） 退后n帧重传 计时器处理 启动，发送帧时启动 停止，收到正确确认时停止 超时

21、则产生timeout事件,发送窗口是否滑动的判别函数,between( a, b, c ); between( ack.expected, r.ack, next_frame_to_send );,课件制作人：王小茹,between( a, b, c ); between( ack.expected, r.ack, next_frame_to_send );,a,c,c,a,c,a,发送函数,发送序号ack序号的填写方法 Send(next_frame_to_send, frame_expected, buffer); (seq, ack, frame),课件制作人：王小茹,网络研究中心：王小

22、茹,如何控制发送的数据帧=发送窗口最大值,设立一个nbuffered变量，每次： 发送一个新数据帧，nbuffered+； 判断nbuffered 7; 每收到一个确认ack，nbuffered-,直到为0,课件制作人：王小茹,课件制作人：王小茹,课件制作人：王小茹,课件制作人：王小茹,网络研究中心：王小茹,如何控制重发？,课件制作人：王小茹,如何体现“Go back N”的含义？,课件制作人：王小茹,课件制作人：王小茹,最大发送窗口问题,发送方： 发送A【0，1，2，3，4，5，6，7】,共发出8个数据帧。 接收方：收到后， 捎带确认（0，7，b【0】)，收到了8个数据帧。 发送方： 滑动窗

23、口，发送新的A【0，1，2，3，4，5，6，7】； 该系列帧还没到达接收方 接收方发送：新帧（1，7，b【1】) ？,课件制作人：王小茹,3.4.3 选择重传协议(A Protocol Using Selective Repeat),课件制作人：王小茹,课件制作人：王小茹,对Go Back N的算法改进,去掉了Go Back N中总是有反向数据帧可以捎带回去的假设； 利用start_ack_timer启动一个辅助的定时器，如果在定时器超时之前，没有出现反向的流量，则发送一个单独的确认帧。 使用NAK，加快对错误帧的处理； 加大接收窗口，对于正确帧进行缓存，待收集齐整个窗口的帧后，有序上交网络层

24、。,课件制作人：王小茹,实现,窗口参数 发送窗口下界：Ack_Expected 发送窗口上界：Next_Frame_To_Send 接收窗口下界：Frame_Expected 接收窗口上界：Too_Far,网络研究中心：王小茹,发送流程分析,发送窗口，接收窗口变化,课件制作人：王小茹,接收流程分析：,正确的数据帧到达,课件制作人：王小茹,选择重传与回退N帧协议区别,课件制作人：王小茹,课件制作人：王小茹,P6协议实现分析,事件驱动 Network_layer_ready（内部事件） 发送帧（帧类型，帧序号，确认序号，数据） Frame_arrival （外部事件） 若是数据帧，则检查帧序号，落

25、在接收窗口内则接收，否则丢弃；不等于接收窗口下界还要发NAK 若是NAK，则选择重传； 检查确认序号，落在发送窗口内则移动发送窗口，否则不做处理。,课件制作人：王小茹,Cksum_err （外部事件） 发送NAK timeout （内部事件） 选择重传 Ack_timeout （内部事件） 发送确认帧ACK 计时器处理 启动，发送数据帧时启动 停止，收到正确确认时停止 超时则产生timeout事件,课件制作人：王小茹,Ack计时器处理 启动，收到帧的序号等于接收窗口下界或已经发过NAK时启动 停止，发送帧时停止 超时则产生ack_timeout事件,课件制作人：王小茹,课件制作人：王小茹,选择

26、重传的最大窗口,Ws+Wr =Wr Ws,Wr= 2n -1,课件制作人：王小茹,课件制作人：王小茹,课件制作人：王小茹,停止等待协议中数据帧和确认帧的发送时间关系,A,B,DATA,DATA,ACK,传播时延 tp,处理时间 tpr,确认帧发送时间 ta,传播时延 tp,处理时间 tpr,时间,两个成功发送的 数据帧之间的 最小时间间隔,数据帧的 发送时间,tf,设置的 重传时间,tout,课件制作人：王小茹,小结,可靠传输 通过确认和重传机制 传输层协议，如TCP，也提供可靠传输服务 链路层的可靠传输服务通常用于高误码率的连路上，如无线链路。,课件制作人：王小茹,3.6 数据链路层协议示例

27、,面向位/位填充的协议：HDLC 面向字符/字节填充的协议：PPP,课件制作人：王小茹,3.6.1 数据链路层协议概述,1974年，IBM 公司推出了面向比特的规程SDLC (Synchronous Data Link Control)。 后来 ISO 把 SDLC 修改后称为 HDLC (High-level Data Link Control)，译为高级数据链路控制，作为国际标准ISO 3309。 CCITT 则将 HDLC 再修改后称为链路接入规程 LAP (Link Access Procedure)。不久，HDLC 的新版本又把 LAP 修改为 LAPB，“B”表示平衡型(Balan

28、ced)，所以 LAPB 叫做链路接入规程(平衡型)。,课件制作人：王小茹,课件制作人：王小茹,网络研究中心：王小茹,网络研究中心：王小茹,网络研究中心：王小茹,课件制作人：王小茹,课件制作人：王小茹,网络研究中心：王小茹,网络研究中心：王小茹,网络研究中心：王小茹,网络研究中心：王小茹,网络研究中心：王小茹,网络研究中心：王小茹,课件制作人：王小茹,3.6.2 因特网的点对点协议 PPP,现在全世界使用的最多的数据链路层协议是点对点协议 PPP (Point-to-Point Protocol)。 Internet需要一个点到点协议 PPP 协议，用于完成数据链路层的功能（差错和流量控制）。

29、,课件制作人：王小茹,应用1：用户拨号入网的示意图,路由器,调制解调器,调制解调器,因特网服务提供者(ISP),用户家庭,拨号电话线,使用 TCP/IP 的 PPP 连接,路由选择 进程,至 因 特 网,PC 机,课件制作人：王小茹,PPP encapsulation,应用2： 租用线路上路由器的PPP连接,课件制作人：王小茹,PPP 协议,1992 年制订了 PPP 协议。经过 1993 年和 1994 年的修订，现在的 PPP 协议已成为因特网的正式标准RFC 1661。 PPP协议有三个组成部分 成帧方法：将 网络层数据封装到串行链路的方法。 链路控制协议 LCP (Link Contr

30、ol Protocol)。 网络控制协议 NCP (Network Control Protocol)。,PHYSICAL,LCP,NCP,PPP,IPCP,IPXCP,Others,IP,IPX,Third Layer,PPP Sublayer,课件制作人：王小茹,课件制作人：王小茹,PPP 协议的帧格式,PPP 的帧格式和 HDLC 的相似。 标志字段 F 仍为 0 x7E （符号“0 x”表示后面的字符是用十六进制表示。十六进制的 7E 的二进制表示是 01111110）。 地址字段 A 只置为 0 xFF。地址字段实际上并不起作用。 控制字段 C 通常置为 0 x03。 PPP 是面向字节的，所有的 PPP 帧的长度都是整数字节。,课件制作人：王小茹,PPP 协议的帧格式,PPP 有一个 2 个字节的协议字段。 当协议字段为 0 x0021 时，PPP 帧的信息字段就是IP 数据报。 若为 0 xC021, 则信息字段是 PPP 链路控制数据。 若为 0 x8021，则表示这是网络控制数据。,IP 数据报,1,2,1,1,字节,1,2,不超过 1500 字