《计算机网络原理-第3章.ppt》由会员分享，可在线阅读，更多相关《计算机网络原理-第3章.ppt（84页珍藏版）》请在金锄头文库上搜索。
1、计算机网络原理计算机网络原理The Principles of Computer Networking第第3章章 数据链路层数据链路层第第3章章 数据链路层数据链路层本章重点q停止等待协议和连续停止等待协议和连续ARQ协议协议q面向比特的链路控制规程面向比特的链路控制规程HDLCqInternet中的数据链路层协议中的数据链路层协议3.1 数据链路层的基本概念数据链路层的基本概念电话网电话网局域网局域网局域网局域网广域网广域网主机主机H1路由器路由器R1路由器路由器R2路由器路由器R3主机主机H2(a) 主机主机H1向向H2发送数据发送数据(b) 从层次上看数据的流动从层次上看数据的流动图图3
2、-1 数据链路层的地位数据链路层的地位物理层物理层 链路层链路层网络层网络层 运输层运输层 应用层应用层 物理层物理层链路层链路层网络层网络层物理层物理层链路层链路层网络层网络层物理层物理层链路层链路层网络层网络层物理层物理层链路层链路层网络层网络层运输层运输层应用层应用层链路层链路层 链路层链路层链路层链路层链路层链路层链路层链路层H1H2数据链路层的协议数据单元数据链路层的协议数据单元 帧帧q数据链路层的任务：数据链路层的任务：把网络层交下来的数据发送到链路上，以及把接把网络层交下来的数据发送到链路上，以及把接收的收的帧中的数据取出并上交给网络层。帧中的数据取出并上交给网络层。在因特网中，
3、网络层的数据单元就是在因特网中，网络层的数据单元就是IP数据报数据报(包包)IP数据报数据报帧帧10100 0110IP数据报数据报帧帧10100 0110装入装入取出取出链路链路帧帧帧帧帧帧网络层网络层数据链路层数据链路层物理层物理层数据链路层数据链路层结点结点A(a) 只有三层的简化模型只有三层的简化模型(b) 只有数据链路层只有数据链路层图图3-2 数据链路层的通信模型数据链路层的通信模型3.1.1 数据链路层的简单模型数据链路层的简单模型3.1.2 链路和数据链路链路和数据链路q链链路路：所所谓谓链链路路(link)就就是是一一条条无无源源的的点点到到点点的的物物理线路段，中间没有任何
4、其他的交换结点。理线路段，中间没有任何其他的交换结点。q数数据据链链路路：实实现现两两个个相相邻邻结结点点通通信信时时，所所执执行行协协议议(规规程程，procedure)的的硬硬件件和和软软件件及及链链路路，就就构构成成了数据链路了数据链路(data link)。q另另一一种种术术语语:将将链链路路分分为为物物理理链链路路和和逻逻辑辑链链路路。物物理理链链路路就就是是上上面面所所说说的的链链路路，而而逻逻辑辑链链路路就就是是上上面面的的数据链路，是物理链路加上必要的通信协议。数据链路，是物理链路加上必要的通信协议。链路与数据链路的差别链路与数据链路的差别链路是链路是物理链路物理链路，而数据链
5、路是，而数据链路是逻辑链路逻辑链路。采采用用复复用用技技术术时时，一一条条链链路路上上可可以以有有多多条条数数据链路。据链路。链链路路不不可可靠靠（可可能能出出现现差差错错），而而数数据据链链路路是可靠的（出现差错后可纠正）。是可靠的（出现差错后可纠正）。链链路路连连接接的的生生存存期期是是结结点点开开机机到到结结点点关关机机时时止止；而而数数据据链链路路连连接接的的生生存存期期是是从从通通信信开开始始到通信结束时止。到通信结束时止。数据链路层的主要功能数据链路层的主要功能q数据链路层最重要的作用：数据链路层最重要的作用： 通通过过一一些些数数据据链链路路层层协协议议(即即链链路路控控制制规规
6、程程)，在在不太可靠的物理链路上实现可靠的数据传输。不太可靠的物理链路上实现可靠的数据传输。1.链路管理链路管理数据链路的建立、维持和释放就叫做链路管理。数据链路的建立、维持和释放就叫做链路管理。2.帧同步帧同步 帧帧同同步步指指的的是是收收方方如如何何从从收收到到的的比比特特流流中中准准确确地地区分出一帧的开始和结束。区分出一帧的开始和结束。3.流量控制流量控制控制发方发送数据的速率。控制发方发送数据的速率。4.差错控制差错控制差错出现的特点：随机，连续突发（差错出现的特点：随机，连续突发（burst）前前向向纠纠错错，即即收收方方收收到到有有差差错错的的数数据据帧帧时时，能能够够自自动动将
7、将差差错错改改正正过过来来。这这种种方方法法的的开开销销较较大大，不适合于计算机通信。不适合于计算机通信。检检错错重重发发，即即收收方方可可以以检检测测出出收收到到的的帧帧中中有有差差错错(但但并并不不知知道道是是哪哪几几个个比比特特错错了了)。于于是是就就让让发发方方重重复复发发送送这这一一帧帧，直直到到收收方方正正确确收收到到这这一一帧为止帧为止。计算机通信中最常用的。计算机通信中最常用的。为为了了防防止止发发送送方方等等待待收收方方应应答答时时出出现现等等待待死死锁锁，还还将将提提供供超超时时控控制制机机制制。重重发发帧帧后后，为为了了收收方方收到重复帧，通常为帧给定一个帧序号。收到重复
8、帧，通常为帧给定一个帧序号。5.区分数据和控制信息区分数据和控制信息6.透明传输透明传输7.寻址寻址 在在多多点点连连接接的的情情况况下下，必必须须保保证证每每一一帧帧都都能能送送到到正正确确的的目目的的站站。收收方方也也应应当当知知道道发发方方是是哪一个站。哪一个站。3.2 三个基本问题三个基本问题数据链路层协议有多种数据链路层协议有多种, 但三个基本问但三个基本问题是相同的题是相同的:1)帧定界帧定界2)透明传输透明传输3)差错控制差错控制3.2.1 帧定界帧定界q数据链路层将来自物理层的比特流划分成一数据链路层将来自物理层的比特流划分成一个个的单元，这个单元称为个个的单元，这个单元称为帧
9、帧(Frame)(Frame)。 q帧定界帧定界(framing)即确定帧的边界即确定帧的边界.q出错时，只将有错的帧重传，而不必传全部出错时，只将有错的帧重传，而不必传全部的数据重发。从而提高了数据传输效率。的数据重发。从而提高了数据传输效率。q每个帧分为每个帧分为帧头、信息、校验和帧尾帧头、信息、校验和帧尾几个部几个部分组成。分组成。qMTU-最大传输单元最大传输单元IP数据报数据报帧首部帧首部帧的数据部分帧的数据部分帧帧尾部尾部帧帧开始开始帧帧结束结束从这里开始发送从这里开始发送=MTU数据链路层的帧长数据链路层的帧长图图3-3 用帧首部和帧尾部进行帧定界用帧首部和帧尾部进行帧定界帧定界
10、方法帧定界方法q用控制字符进行帧定界用控制字符进行帧定界SOH作为帧的开始，作为帧的开始，SOH的的ASCII码值为码值为01EOT作为帧的结束，作为帧的结束，EOT的的ASCII码值为码值为04SOH装在帧中的数据部分装在帧中的数据部分EOT指出帧的开始指出帧的开始指出帧的结束指出帧的结束帧帧发送在前发送在前图图3-4 用控制字符进行帧定界的方法举例用控制字符进行帧定界的方法举例3.2.2 透明传输透明传输SOHEOT完整的帧完整的帧EOT数据部分数据部分数据中碰巧出现一个与数据中碰巧出现一个与控制字符控制字符”EOT”相同的字符相同的字符被接收端错误地被接收端错误地当作是一个帧当作是一个帧
11、由于找不到控制字符由于找不到控制字符”SOH”,被接收端当作无效帧而丢弃被接收端当作无效帧而丢弃图图3-5 数据部分恰好出现和数据部分恰好出现和EOT一样的代码一样的代码使用转义符对使用转义符对帧边界进行转换帧边界进行转换q字节插入（字节插入（byte stuffing）qESC的的ASCII码为码为0x1B，称为转义符。，称为转义符。数据中出现的控制字符数据中出现的控制字符经字节插入后发送时的字符经字节插入后发送时的字符SOHESC xEOTESC yESCESC z用字节插入法解决透明传输的问题用字节插入法解决透明传输的问题原始数据原始数据SOHEOTESCEOTESCSOHSOHEOTE
12、SCzESCyESCzESCx经过字节插入后发送的数据经过字节插入后发送的数据另一种实现透明传输的方法另一种实现透明传输的方法 比特插入，将在比特插入，将在3.5.2小节介绍小节介绍图图3-6 用字节插入法解决透明传输的问题用字节插入法解决透明传输的问题3.2.3 差错检测差错检测q产生差错的原因：产生差错的原因：1.信道的电气特性引起信号幅度、频率、相位的信道的电气特性引起信号幅度、频率、相位的畸变；畸变；2.信号反射；信号反射；3.串扰；串扰；4.闪电、大功率电机的启停等。闪电、大功率电机的启停等。q线路传输差错是不可避免的，但要尽量减小线路传输差错是不可避免的，但要尽量减小其影响。其影响
13、。差错检测差错检测q差错检验编码都是采用冗余编码技术，核心差错检验编码都是采用冗余编码技术，核心思想是有效数据（信息位）在被发送前，先思想是有效数据（信息位）在被发送前，先按照某种关系附加上一定的冗余位，构成一按照某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送。个符合某一规则的码字后再发送。q其中要发送的有效数据变化时，相应的冗余其中要发送的有效数据变化时，相应的冗余位也随之变化，使得码字遵从不变的规则。位也随之变化，使得码字遵从不变的规则。在接收端收到码字后，判断它是否仍然符合在接收端收到码字后，判断它是否仍然符合原规则，若不符合原规则，就可以判定传输原规则，若不符合原规则，
14、就可以判定传输过程有错。过程有错。冗余编码冗余编码q冗余位的编码冗余位的编码:纠错码纠错码发现并纠正错误发现并纠正错误;检错码检错码仅发现错误。仅发现错误。q使用纠错码传数据，效率低，适用于不可能使用纠错码传数据，效率低，适用于不可能重传的场合；大多数情况采用检错码加重传。重传的场合；大多数情况采用检错码加重传。q常用的检错码：常用的检错码：奇偶校验和奇偶校验和CRC循环冗余码，计算机通信中主要循环冗余码，计算机通信中主要使用使用CRC循环循环冗冗余码。余码。(1) 奇偶校验（奇偶校验（Parity Checking）q在原始数据字节的最高位增加一个附加比特位，使在原始数据字节的最高位增加一个
15、附加比特位，使结果中结果中1的个数为奇数的个数为奇数(奇校验奇校验)或偶数或偶数(偶校验偶校验)。增。增加的位称为奇偶校验位。加的位称为奇偶校验位。 例：原始数据例：原始数据=1100010，采用偶校验。，采用偶校验。 则增加校验位后的数据为则增加校验位后的数据为11100010若接收方收到的字节奇偶结果不正确，就可以知道若接收方收到的字节奇偶结果不正确，就可以知道传输中发生了错误。传输中发生了错误。奇偶校验只能检测出奇数个比特位错，对偶数个比奇偶校验只能检测出奇数个比特位错，对偶数个比特位错则无能为力。特位错则无能为力。(2) 循环冗余码循环冗余码（CRC-Cyclic Redundancy
16、 Code）q循环冗余码（循环冗余码（CRC码，也称多项式编码）码，也称多项式编码）q简单例子：简单例子：待发送的数据待发送的数据M=101001(共共k bit，k=6).在数据在数据M的后面添加供查错检测用的的后面添加供查错检测用的n bit冗余冗余码一起发送码一起发送(k+n个个bit)，即，即:101001xxxx虽然增加了虽然增加了n个个bit，但可以进行差错检测。但可以进行差错检测。K位数据位数据n位冗余码位冗余码循环冗余码的计算循环冗余码的计算q先用先用二进制的模二进制的模2运算进行运算进行2n乘乘M的运算。的运算。M* 2n 相当于在后面添加相当于在后面添加n个个0，得到，得到
17、k+n bitq得到的得到的(k+n)bit的数除以收发双方事先约定的的数除以收发双方事先约定的长度为长度为(n+1)bit的数的数P，得出商是得出商是Q而余数是而余数是R(n bit)。q这个余数这个余数R就作为就作为冗余码添加在数据冗余码添加在数据M的后面发的后面发送出去。送出去。q这种为了进行差错检错而添加的冗余码常成为这种为了进行差错检错而添加的冗余码常成为帧检验序列帧检验序列FCS(Frame Check Sequence)。q设设n=3，除数除数P=1101M=101001M* 2n =101001000101001000/1101的商的商Q=110101，余数余数R=001 最后
18、发送的数据为：最后发送的数据为：101001001循环冗余码循环冗余码CRC与与帧检验序列帧检验序列FCSqCRC是一种检错方法是一种检错方法qFCS是添加在数据后面的是添加在数据后面的冗余码，它可以冗余码，它可以用用CRC，但也可以不用但也可以不用CRC这种检错方法。这种检错方法。q在接受端对接收到的在接受端对接收到的帧进行帧进行CRC检验。把收检验。把收到的帧除以同样的到的帧除以同样的P(模模2运算运算)，得到余数，得到余数R。如果数据在传输过程中没有出现差错，则得如果数据在传输过程中没有出现差错，则得到的余数显然应为到的余数显然应为0。若数据在传输过程中出。若数据在传输过程中出现误码，则
19、得不出余数为现误码，则得不出余数为0的结果。或者更严的结果。或者更严格地讲，这时得出余数为格地讲，这时得出余数为0的概率极小。的概率极小。CRC检验检验q用用多项式来表示多项式来表示CRC检检验过程，使用多项式相验过程，使用多项式相应的系数来表示上述二应的系数来表示上述二进制数字中的进制数字中的1和和0qP(X)=X3+X2+1P=1101P(X)称为称为生成多项式生成多项式CRC多项式国际标准多项式国际标准qCRC-16=X16+X15+X2+1qCRC-CCITT=X16+X12+X5+1qCRC-32=X32+X26+X23+X22+X16+ X12+X11+X10+X8+X7+X5+X
20、4+X2+X+1q发送端的发送端的FCS生成和接收端的生成和接收端的CRC检验都是用检验都是用硬件完成的。硬件完成的。qCRC差错检测只能做到无差错接受。要保证可差错检测只能做到无差错接受。要保证可靠传输，必须再加上靠传输，必须再加上确认确认和和重传重传机制。机制。3.3 停止等待协议停止等待协议q停停止止等等待待(stop-and-wait)协协议议是是最最简简单单但但也也是最基本的数据链路层协议。是最基本的数据链路层协议。q很很多多有有关关协协议议的的基基本本概概念念都都可可以以从从这这个个协协议议中学习到。中学习到。q可分三种情况讨论：可分三种情况讨论：不需要数据链路层协议的数据传输不需
21、要数据链路层协议的数据传输具有最简单流量控制的数据链路层协议具有最简单流量控制的数据链路层协议实用的停止等待协议。实用的停止等待协议。1、无约束单工协议、无约束单工协议（An Unrestricted Simplex Protocol）q工作在理想情况，几个前提：工作在理想情况，几个前提：单工传输单工传输发送方无休止工作（要发送的信息无限多）发送方无休止工作（要发送的信息无限多）接收方无休止工作（缓冲区无限大）接收方无休止工作（缓冲区无限大）通信线路（信道）不损坏或丢失信息帧通信线路（信道）不损坏或丢失信息帧q工作过程工作过程发送程序发送程序:取数据，构成帧，发送帧；取数据，构成帧，发送帧；接
22、收程序：等待，接收帧，送数据给高层接收程序：等待，接收帧，送数据给高层2 、单工停等协议、单工停等协议（A Simplex Stop-and-Wait Protocol）q增加约束条件：接收方不能无休止接收。（接收缓增加约束条件：接收方不能无休止接收。（接收缓冲区并非无限大）冲区并非无限大）q解决办法：接收方每收到一个帧后，给发送方回送解决办法：接收方每收到一个帧后，给发送方回送一个响应。一个响应。q工作过程工作过程发送程序：取数据，成帧，发送帧，等待响应帧；发送程序：取数据，成帧，发送帧，等待响应帧；接收程序：等待，接收帧，送数据给高层，回送接收程序：等待，接收帧，送数据给高层，回送响应帧。
23、响应帧。3、有噪声信道的单工协议、有噪声信道的单工协议（A Simplex Protocol for a Noisy Channel）q增加约束条件：信道（线路）有差错，信息帧可增加约束条件：信道（线路）有差错，信息帧可能损坏或丢失。能损坏或丢失。q解决办法：出错重传。解决办法：出错重传。q带来的问题：带来的问题：什么时候重传什么时候重传 定时定时响应帧损坏怎么办（重复帧）响应帧损坏怎么办（重复帧） 发送帧头中放入序发送帧头中放入序号号为了使帧头精简，序号取多少位为了使帧头精简，序号取多少位 1位位q发方在发下一个帧之前等待一个肯定确认的协议发方在发下一个帧之前等待一个肯定确认的协议叫做叫做P
24、AR（Positive Acknowledgement with Retransmission）或）或ARQ（Automatic Repeat reQuest）DATA0DATA1DATA0ACK1ACK0ACK1AB时时间间发送发送停止停止等待等待发送发送发送发送停止停止等待等待停止停止等待等待发交上层发交上层发送确认发送确认发交上层发交上层发交上层发交上层发送确认发送确认发送确认发送确认DATA0DATA0DATA1ACK1ACK1AB丢弃丢弃出错帧出错帧发交上层发交上层发交上层发交上层发送确认发送确认发送确认发送确认DATA0DATA0DATA1ACK1ACK1ACK0AB发交上层发交上
25、层发送确认发送确认丢弃丢弃重复帧重复帧发交上层发交上层发送确认发送确认发送确认发送确认超时超时重传重传出错出错tout出错出错tout超时超时重传重传(a) 正常情况正常情况(b) 数据帧出错数据帧出错(c) 确认帧出错确认帧出错图图3-8 停止等待协议的工作原理停止等待协议的工作原理4、实用、实用停止等待协议的基本原理停止等待协议的基本原理q前提：实际信道不满足理想化数据传输的假定前提：实际信道不满足理想化数据传输的假定q流量控制方法：等待发送流量控制方法：等待发送q差错控制：发送方数据帧中加入校验码（差错控制：发送方数据帧中加入校验码（CRC），），由接收方检查；若出错，返回由接收方检查；
26、若出错，返回NAK；发送方收到发送方收到NAK后重发。后重发。q帧丢失处理：超时定时器；以序号标识数据帧帧丢失处理：超时定时器；以序号标识数据帧 q优点：简单优点：简单q缺点：缺点： 信道利用率信道利用率低低3.3.2 停止等待协议的算法停止等待协议的算法q为为了了对对上上面面所所述述的的停停止止等等待待协协议议有有一一个个完完整整而而准准确确的的理理解解，下下面面给给出出此此协协议议的的算算法法，如如下图所示。下图所示。 从主机取一个数据帧从主机取一个数据帧在发送结点在发送结点V(S)0发送状态变量初始化发送状态变量初始化N(S)V(S)将发送状态变量的数值写入发送序号将发送状态变量的数值写
27、入发送序号将数据帧送交发送缓冲区将数据帧送交发送缓冲区将发送缓冲区中的数据帧发送出去将发送缓冲区中的数据帧发送出去选择适当的超时重发时间选择适当的超时重发时间 ，设置超时定时器，设置超时定时器等待以下等待以下3个事件中最先出现的一个个事件中最先出现的一个收到确认帧收到确认帧ACK从主机取一个新的数据帧从主机取一个新的数据帧V(S)1-V(S)更新发送状态变量，变为下一个序号更新发送状态变量，变为下一个序号收到否认帧收到否认帧NAK若超时定时器时间到若超时定时器时间到接收结点接收结点接收状态变量初始化：接收状态变量初始化：V(R)0等待等待收到一个数据帧有无差错收到一个数据帧有无差错无无有有N(
28、S)V(R) 收到发送序号正确的数据帧收到发送序号正确的数据帧？是是将收到的数据帧中的数据部分送交主机将收到的数据帧中的数据部分送交主机V(R)1-V(R)更新接收状态变量，准备接收下一个数据帧更新接收状态变量，准备接收下一个数据帧发送确认帧发送确认帧ACK发送否认帧发送否认帧NAK否否丢弃此数据帧丢弃此数据帧说明说明q在在收收发发两两端端各各设设置置一一个个本本地地状状态态变变量量(仅仅占占1个个比比特特)。同时注意：。同时注意：(1)每每发发送送一一个个数数据据帧帧，都都必必须须将将发发送送状状态态变变量量V(S)的的值值(0或或1)写写到到数数据据帧帧的的发发送送序序号号N(S)上上。但
29、但只只有有收收到到一一个个确确认认帧帧ACK后后，才才更更新新发发送送状状态态变变量量V(S)一一次次(将将1变变成成0或或0变成变成1)并发送新的数据帧。并发送新的数据帧。(2)在在接接收收端端，每每接接收收到到一一个个数数据据帧帧，就就要要将将发发方方在在数数据据帧帧上上设设置置的的发发送送序序号号N(S)与与本本地地的的接接收收状状态态变变量量V(R)相相比较。若二者相等就表明是新的数据帧，否则为重复帧。比较。若二者相等就表明是新的数据帧，否则为重复帧。(3)在接收端，若收到一个重复帧，则丢弃之在接收端，若收到一个重复帧，则丢弃之(即即不做任何处理不做任何处理)，且接收状态变量不变，但此
30、时，且接收状态变量不变，但此时仍须向发送端发送一个确认帧仍须向发送端发送一个确认帧ACK。(4)发发送送端端在在发发送送完完数数据据帧帧时时，必必须须在在其其发发送送缓缓冲冲区区中中保保留留此此数数据据帧帧的的副副本本。只只有有在在收收到到对对方方发发来的确认帧来的确认帧ACKACK时，方可清除此副本。时，方可清除此副本。3.3.3 停止等待协议的重传时间停止等待协议的重传时间q数据帧发送时间数据帧发送时间tf是数据帧的长度是数据帧的长度lf(bit)与数与数据的发送速率据的发送速率C(bit/s)之比，即：之比，即：lf tf =Cq发送时间也就是数据帧的发送时间也就是数据帧的发送时延发送时
31、延。数据帧的数据帧的发送时间发送时间tf设置的设置的重传时间重传时间touttT两个成功发送的两个成功发送的数据帧之间的数据帧之间的最小时间间隔最小时间间隔传播时延传播时延tp处理时间处理时间tpr时间时间确认帧发送时间确认帧发送时间ta传播时延传播时延tp处理时间处理时间tprDATA0DATA1ACK1ABq重传时间重传时间tout = tp + tpr + ta + tp + tpr重传重传时间时间q重传时间：重传时间：tout = tp + tpr + ta + tp + tpr假设假设tpr和和ta都远小于传播时延，则：都远小于传播时延，则：tout = 2 tpq成功发送两个数据帧
32、的最小时间间隔成功发送两个数据帧的最小时间间隔tT 为：为： tT = tf + tout = tf + 2 tp如如果果发发生生差差错错，则则成成功功发发送送1个个数数据据帧帧所所需需的的时间显然要超过时间显然要超过tT 。最大吞吐量最大吞吐量q最大吞吐量最大吞吐量max=1/tav=(1-p)/tTp为数据帧出现差错的概率为数据帧出现差错的概率q实际吞量实际吞量(1-p)/tTq用用tf进行归一化，得出归一化吞吐量进行归一化，得出归一化吞吐量= ttf11q由由于于发发送送端端对对出出错错的的数数据据帧帧进进行行重重发发是是自自动动进进行行的的，所所以以这这种种差差错错控控制制体体制制常常
33、简简称称为为ARQ(Automatic ARQ(Automatic Repeat Repeat reQuestreQuest) )，自自动动请请求求重发（传）。重发（传）。q停止等待协议停止等待协议ARQARQ的优点是：比较简单的优点是：比较简单q缺点是：通信信道的利用率不高缺点是：通信信道的利用率不高。q为为了了克克服服这这一一缺缺点点，就就产产生生了了另另外外两两种种协协议议，即连续即连续ARQARQ和选择重传和选择重传ARQARQ。 3.4 连续连续ARQ协议协议3.4.1 3.4.1 连续连续ARQARQ协议的工作原理协议的工作原理q在发送完一个数据帧后，不是在发送完一个数据帧后，不是
34、停下来等待确停下来等待确认帧认帧，而是可以，而是可以连续再发送若干个数据帧连续再发送若干个数据帧。如果这时收到了接收端发来的确认帧，那么如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。由于还可以接着发送数据帧。由于减少了等待时减少了等待时间间，整个通信的吞吐量就提高了。，整个通信的吞吐量就提高了。01234523456DATAACK0ACK1送主机送主机出出错错ACK2ACK3tftouttouttouttout重传重传送主机送主机AB丢弃丢弃时间时间 要注意两点：要注意两点：（1）接收端只按序接收数据帧。）接收端只按序接收数据帧。（2）结点）结点A在每发送完每一个数据帧时都要设置
35、超时计时器。在每发送完每一个数据帧时都要设置超时计时器。连续连续ARQ协议的优缺点协议的优缺点q优点优点连续发送数据帧，提高了信道的利用率。连续发送数据帧，提高了信道的利用率。q缺点缺点在重传时必须把原来已传送正确的数据帧进行重在重传时必须把原来已传送正确的数据帧进行重传（仅因为这些数据帧的前面有一个数据帧出了传（仅因为这些数据帧的前面有一个数据帧出了错），这种做法又使传送效率降低。错），这种做法又使传送效率降低。q由此可见，若传输信道的传输质量很差因而由此可见，若传输信道的传输质量很差因而误码率较大时，连续误码率较大时，连续ARQ协议不一定优于停协议不一定优于停止等待协议。止等待协议。q在使
36、用连续在使用连续ARQ协议，有下面两个问题要解协议，有下面两个问题要解决：决：当未被确认的数据帧的数目太多时，只要有一帧当未被确认的数据帧的数目太多时，只要有一帧出了差错，就要有很多的数据帧需要重传，这必出了差错，就要有很多的数据帧需要重传，这必然要白白花费较多的时间，因而增大开销。然要白白花费较多的时间，因而增大开销。为了对所发送出去大大量数据帧进行编号，每个为了对所发送出去大大量数据帧进行编号，每个数据帧的发送序号也要占用较多的比特数，这样数据帧的发送序号也要占用较多的比特数，这样又增加了一些不必要的开销。又增加了一些不必要的开销。3.4.2 3.4.2 滑动窗口的概念滑动窗口的概念q发送
37、窗口用来对发送端进行流量控制发送窗口用来对发送端进行流量控制，而发，而发送窗口的大小送窗口的大小WT 就代表就代表在还没有收到对方确在还没有收到对方确认信息的情况下发送端最多可以发送多少个认信息的情况下发送端最多可以发送多少个数据帧数据帧。q设发送序号用设发送序号用3 3比特来编码，即从比特来编码，即从0 0到到7 7共共8 8个个不同的序号。不同的序号。q设发送窗口设发送窗口WT=5012345670120123456701201234567012WT发送窗口发送窗口允许发送允许发送5个帧个帧不允许发送这些帧不允许发送这些帧WT01234567012WT允许发送允许发送4个帧个帧不允许发送这
38、些帧不允许发送这些帧已发送已发送已发送已发送不允许发送这些帧不允许发送这些帧WT已发送已发送并已收到确认并已收到确认已发送已发送还允许发送还允许发送3个帧个帧不允许发送这些帧不允许发送这些帧(a) 允许发送允许发送04号号共共5个帧个帧(b) 允许发送允许发送14号号共共4个帧个帧(c) 不允许发送任何帧不允许发送任何帧(d) 允许发送允许发送57号号共共3个帧个帧发送窗口的规则发送窗口的规则q（1）发发送送窗窗口口内内的的帧帧是是允允许许发发送送的的帧帧，而而不不考考虑虑有有没没有有收收到到确确认认。发发送送窗窗口口右右侧侧所所有有的的帧帧都都是是不不允允许许发送的帧。图发送的帧。图 (a)
39、说明了这一情况。说明了这一情况。q（2）每每发发送送完完一一个个帧帧，允允许许发发送送的的帧帧数数就就减减1。但但发发送送窗窗口口的的位位置置不不变变。图图(b)说说明明已已经经发发送送了了0号号帧帧，因此允许发送的帧数就少了一个，即只有因此允许发送的帧数就少了一个，即只有4个。个。q（3）如如果果所所允允许许发发送送的的5个个帧帧都都发发送送完完了了，但但还还没没有有收收到到任任何何确确认认，那那么么就就不不能能再再发发送送任任何何帧帧了了。图图(c)表示这种情况。这时，发送端就进入等待状态。表示这种情况。这时，发送端就进入等待状态。q（4）每收到对一个帧的确认，发送窗口就向前(即向右方)滑
40、动一个帧的位置。图 (d)表示发送端已经收到了0, 1和2号帧共3个帧的确认，因此发送窗口可以向前滑动3个帧的位置。于是，发送端现在又可以继续发送3个帧(即5 7号帧)。接收窗口的规则q在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。q（1）只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。q（2）每收到一个序号正确的帧，接收窗口就向前(即向右方)滑动一个帧的位置。同时向发送端发送对该帧的确认。q图 (a)表明一开始接收窗口处于0号帧处，接收端准备接收0号帧。一旦收到0号帧，接收窗口即向前滑动一个帧的位置(图(b)，准备接收1号帧，同时向发送端发送对0号
41、帧的确认信息。当陆续收到1号至3号帧后，接收窗口的位置应图 (c)所示。qARQ中当用n个比特进行编码时，若接收窗口的大小为1，则发送窗口的的数值 WT=2n-1qARQ信道利用率：在没有误差时 U=ld/(ld+lh)=13.4.4 选择重传选择重传ARQ协议协议q为进一步提高信道的利用率，可设法只重为进一步提高信道的利用率，可设法只重传出现差错的数据帧或者是计时器超时的传出现差错的数据帧或者是计时器超时的数据帧。数据帧。q接收窗口的约束：接收窗口的约束： WR=2n/23.5 点对点协议点对点协议PPPq点对点协议点对点协议PPP (Point-to-Point Protocol)是目前使
42、用得最广泛的数据链路层协议。是目前使用得最广泛的数据链路层协议。q下图是用户拨号入网的示意图。下图是用户拨号入网的示意图。因特网服务因特网服务提供提供者者ISP是一个能够提供用户拨号入网的经是一个能够提供用户拨号入网的经营机构。营机构。qPPP协议是协议是IETF在在1992年制定的，经过年制定的，经过1993年和年和1994年的修订，现在的年的修订，现在的PPP协议已成为协议已成为因特网的正式标准因特网的正式标准RFC 1661。调制解调器调制解调器调制解调器调制解调器拨号电话线拨号电话线路由器路由器至因特网至因特网用户用户PC机机因特网服务提供商因特网服务提供商ISP市话交换机市话交换机图
43、图3-13 PC机用拨号方式入网机用拨号方式入网1. PPP协议应满足的需求协议应满足的需求q(1) 简单简单q(2) 封装成帧封装成帧q(3) 透明性透明性q(4) 多种网络层协议多种网络层协议q(5) 多种类型链路多种类型链路q(6) 差错检测差错检测q(7) 连接的活跃度连接的活跃度q(8) 最大传送单元最大传送单元q(9) 网络地址协商网络地址协商q(10) 数据压缩协商数据压缩协商qPPP协协议议之之所所以以不不使使用用序序号号和和确确认认机机制制是是出出于于以以下的几点考虑：下的几点考虑：q（1）若若使使用用可可靠靠的的数数据据链链路路层层协协议议，开开销销就就要要增大。增大。q（
44、2）在在因因特特网网环环境境下下，PPP的的信信息息字字段段放放入入的的数数据据是是IP数数据据报报。数数据据链链路路层层的的可可靠靠传传输输并并不不能能够保证网络层的传输也是可靠的够保证网络层的传输也是可靠的。q（3）PPP协协议议在在帧帧格格式式中中有有帧帧检检验验序序列列FCS字字段。段。q为为了了克克服服SLIP的的这这些些缺缺点点，1992年年制制定定了了PPP协议。协议。PPP协议有如下三个组成部分：协议有如下三个组成部分：q（1）一一个个将将IP数数据据报报封封装装到到串串行行链链路路的的方方法法。PPP既既支支持持异异步步链链路路(无无奇奇偶偶检检验验的的8比比特特数数据据)，
45、也也支支持持面面向向比比特特的的同同步步链链路路。IP数数据据报报在在PPP帧帧中中就就是是其其信信息息部部分分。这这个个信信息息部部分分的的长长度度受受最最大大接接收收单单元元MRU (Maximum Receive Unit)的限制。的限制。MRU的默认值是的默认值是1500字节。字节。q（2）一个用来建立、配置和测试数据链路连）一个用来建立、配置和测试数据链路连接的接的链路控制协议链路控制协议LCP (Link Control Protocol)。通信的双方可协商一些选项。在通信的双方可协商一些选项。在RFC 1661中定义了中定义了11种类型的种类型的LCP分组。分组。q（3）一套）一
46、套网络控制协议网络控制协议NCP (Network Control Protocol)，其中的每一个协议支持其中的每一个协议支持不同的网络层协议，如不同的网络层协议，如IP、OSI的网络层、的网络层、DECnet以及以及AppleTalk等。等。3.5.2 PPP协议的帧格式协议的帧格式qPPP的帧格式如图所示。的帧格式如图所示。PPP不是面向比特不是面向比特而是面向字节的，因而而是面向字节的，因而所有的所有的PPPPPP帧的长度帧的长度都是整数个字节都是整数个字节。1. 各字段的意义各字段的意义qPPP帧的首部和尾部分别为帧的首部和尾部分别为4个和个和2个字段。个字段。q首部的第一和尾部的第
47、二个字节都是标志字段首部的第一和尾部的第二个字节都是标志字段F(Flag)，规定为，规定为0x7E (01111110)。标志字段表示一个帧的开始或结束。连续两个标志标志字段表示一个帧的开始或结束。连续两个标志表示空帧。表示空帧。q首部中的地址字段首部中的地址字段 A规定为规定为0xFF，控制字段，控制字段C规定规定为为0x03。qPPP首部的第四个字段是首部的第四个字段是2字节的协议字段，字节的协议字段， 指明指明PPP帧的信息字段。帧的信息字段。0x0021表示表示IP数据报；数据报；0xC021表示表示PPP链路控制协议链路控制协议LCP的数据；的数据；0x8021表示这是网络层的控制数
48、据。表示这是网络层的控制数据。1. 各字段的意义各字段的意义q信息字段的长度是可变的，不超过信息字段的长度是可变的，不超过1500字节。字节。q尾部中的第一字段（尾部中的第一字段（2字节）是使用字节）是使用CRC的帧的帧检验序列检验序列FCS。2. 字节填充字节填充q当信息字段中出现和标志字段一样的比特当信息字段中出现和标志字段一样的比特(0x7E)组合时，就必须设法处理。组合时，就必须设法处理。q当当PPP使用异步传输时，它把转义符定义为使用异步传输时，它把转义符定义为0x7D，并使用字节填充，具体做法如下：，并使用字节填充，具体做法如下：把信息字段中的把信息字段中的0x7E转变成转变成2个
49、字节序列个字节序列(0x7D,0x5E)把信息字段中的把信息字段中的0x7D转变成转变成2个字节序列个字节序列(0x7D,0x5D)在信息字段中的在信息字段中的ASCII码控制字符前加一个码控制字符前加一个0x7D，同时将控制字符的编码加以改变，如同时将控制字符的编码加以改变，如0x03(ETX)就就要变成要变成0x31，具体规则见，具体规则见RFC1662。3. 零比特填充零比特填充qPPP采用同步传输时，采用零比特填充方法采用同步传输时，采用零比特填充方法实现透明传输。实现透明传输。q具体方法：具体方法：在发送端，先扫描整个信息字段，只要发现有在发送端，先扫描整个信息字段，只要发现有5个连
50、续的个连续的1，则立即填入一个，则立即填入一个0。这样，信息字段。这样，信息字段中就不会出现中就不会出现6个连续的个连续的1。接收端在收到一个帧时，先找到标志字段接收端在收到一个帧时，先找到标志字段F以确以确定帧边界。接着扫描其中的比特流，每当发现定帧边界。接着扫描其中的比特流，每当发现5个连续的个连续的1时，就把这时，就把这5个连续的个连续的1后面的一个后面的一个0删删除。这样就能还原原来的信息比特流。除。这样就能还原原来的信息比特流。3.5.3 PPP协议的工作状态协议的工作状态q当用户拨号接入当用户拨号接入ISP时，时，ISP的的Modem对拨号做出对拨号做出确认，并建立一条物理连接。确
51、认，并建立一条物理连接。q用户用户PC机向机向ISP的路由器发送一系列的的路由器发送一系列的LCP分组分组（封装成多个（封装成多个PPP帧）。这些分组及其响应选择了帧）。这些分组及其响应选择了将要使用的一些将要使用的一些PPP参数。参数。q接着就进行网络层配置，接着就进行网络层配置，NCP给新接入的用户给新接入的用户PC机机分配一个临时的分配一个临时的IP地址，这样用户地址，这样用户PC机就成为因特机就成为因特网上的一个主机。网上的一个主机。q当用户通信完毕时，当用户通信完毕时，NCP释放网络层连接，收回原释放网络层连接，收回原来分配的来分配的IP地址。接着，地址。接着，LCP释放数据链路层连
52、接。释放数据链路层连接。最后释放的是物理层的连接。最后释放的是物理层的连接。qPPP是是一一个个适适用用于于MODEM、HDLC位位串串行行线线路路、SONET和和其其它它物物理理层层的的多多协协议议成成帧帧机机制制。它它支支持持错错误误检检测测、选选项项协协商商、头头部部压压缩缩和（可选的）使用和（可选的）使用HDLC成帧的可靠传输。成帧的可靠传输。q 随随着着技技术术的的进进步步，通通信信信信道道的的可可靠靠性性比比过过去去已已经经有有了了非非常常大大的的改改进进，没没有有必必要要在在数数据据链链路路层层使使用用很很复复杂杂的的协协议议来来实实现现可可靠靠传传输输。不不可可靠靠的的PPP协
53、协议议现现已已成成为为数数据据链链路路层层的的主主流流协协议议，而而可可靠靠传传输输的的由由运运输输层层的的TCP协协议议完完成。成。3.6 HDLC协议协议q1 1、HDLCHDLC概述概述qHDLCHDLC可可适适用用于于链链路路的的两两种种基基本本配配置置，即即非非平平衡衡配置与平衡配置配置与平衡配置。q非非平平衡衡配配置置的的特特点点是是由由一一个个主主站站(primary (primary station)station)控控制制整整个个链链路路的的工工作作。主主站站发发出出的的帧帧叫叫做做命命令令(command)(command)。受受控控的的各各站站叫叫做做次次站站或或从从站站
54、(secondary (secondary station)station)。次次站站发发出出的的帧帧叫叫做做响响应应(response)(response)。在在多多点点链链路路中中，主主站站与与每每一一个个次次站站之之间间都都有有一一个个分分开开的逻辑链路。的逻辑链路。检验区间透明传输区间2 2、HDLC HDLC 的帧结构的帧结构n数据链路层的数据传送是以帧为单位的。一个帧的结构具有固定的格式，如下图所示。各字段的意义nA）标志字段8bit,为7EH：01111110q零零比比特特填填充充法法使使一一帧帧中中两两个个F F字字段段之之间间不不会会出出现现6 6个个连续连续1 1。q在在发
55、发送送端端，当当一一串串比比特特流流数数据据尚尚未未加加上上标标志志字字段段时时，先先用用硬硬件件扫扫描描整整个个帧帧。只只要要发发现现有有5 5个个连连续续1 1，则则立立即即填填入入一一个个0 0。因因此此经经过过这这种种零零比比特特填填充充后后的的数数据据，就可以保证在数据中不会出现就可以保证在数据中不会出现6 6个连续个连续1 1。q在在接接收收一一个个帧帧时时，先先找找到到F F字字段段以以确确定定一一个个HDLCHDLC帧帧的的边边界界。接接着着再再用用硬硬件件对对其其中中的的比比特特流流进进行行扫扫描描。每每当当发发现现5 5个个连连续续1 1时时，就就将将这这5 5个个连连续续
56、1 1后后的的一一个个0 0删除，以还原成原来的比特流，如图所示。删除，以还原成原来的比特流，如图所示。零比特填充法零比特填充法B）地址字段地址字段q8bit，全，全1为广播地址，全为广播地址，全0无效地址。可用无效地址。可用于一对多点通信。于一对多点通信。C）控制字段控制字段q8bit，将，将HDLC帧分为三类：帧分为三类：信息帧信息帧、监督帧监督帧和和无编号帧无编号帧，其简称分别是，其简称分别是I (Information)、S (Supervisory)和和U (Unnumbered)。下图下图是对应于这是对应于这3种帧的控制字段以及控制字段中种帧的控制字段以及控制字段中的各比特的作用。
57、的各比特的作用。q用用于于数数据据传传输输，还还可可以以同同时时用用来来对对已已收收到到的数据进行确认和执行轮询等功能。的数据进行确认和执行轮询等功能。q若若控控制制字字段段的的第第1比比特特为为0，则则该该帧帧为为信信息息帧帧。比比特特2 4为为发发送送序序号号N(S)，而而比比特特6 8为为接接收收序序号号N(R)。N(S)表表示示当当前前发发送送的的信信息息帧帧的的序序号号，而而N(R)表表示示这这个个站站所所期期望收到的帧的发送序号望收到的帧的发送序号。信息帧信息帧监督帧监督帧q用用于于数数据据流流控控制制，帧帧本本身身不不包包含含数数据据，但但可可执执行行对对信信息息帧帧确确认认、请
58、请求求重重发发信信息息帧帧和和请请求求暂停发送信息帧等功能。暂停发送信息帧等功能。q若若控控制制字字段段的的第第1 2比比特特为为1 0，则则对对应应的的帧帧即即为为监监督督帧帧S。监监督督帧帧共共有有四四种种，取取决决于于第第3 4比比特特的的值值(图图中中标标有有S的的二二比比特特)。下下表表是是这四种监督帧的名称和功能。这四种监督帧的名称和功能。q主主要要用用于于控控制制链链路路本本身身，它它不不使使用用发发送送或或接接收帧序号。某些无编号帧可以包含数据。收帧序号。某些无编号帧可以包含数据。q若若控控制制字字段段的的第第1 2比比特特都都是是1时时，这这个个帧帧就是就是无编号无编号帧帧U。无编号帧无编号帧帧校验序列帧校验序列q16bit，生生成成多多项项式式采采用用CRC-CCITT，检检验验范范围围从从地地址址字字段段的的第第1个个比比特特开开始始到到信信息息字字段段的最后的最后1个比特止。个比特止。作业作业q第三版第三版P67 3-09 3-11q第四版第四版P973-093-11
