1、计计 算算 机机 网网 络络 COMPUTER NETWORKS第第5章章 数据链路层数据链路层5.1 5.1 基本概念基本概念n链路：一条无源的点到点的物理线路段。链路：一条无源的点到点的物理线路段。n数据链路：链路数据链路：链路+规程（控制数据传输）。规程（控制数据传输）。n数据链路层的作用：数据链路层的作用：通过一些数据链路层协议（即链路控制规通过一些数据链路层协议（即链路控制规程），在不太可靠的物理链路上实现可靠程），在不太可靠的物理链路上实现可靠的数据传输。的数据传输。学习重点学习重点:两台机器之间实现可靠、有效的两台机器之间实现可靠、有效的通信而涉及到的一些算法。通信而涉及到的一些
2、算法。n数据链路层的主要功能：数据链路层的主要功能：链路管理链路管理：数据链路的建立、维持和释放；：数据链路的建立、维持和释放；帧同步帧同步：收方能从收到的比特流中区分一帧开始和结束的：收方能从收到的比特流中区分一帧开始和结束的地方；地方；流量控制流量控制：发方发送数据的速率必须使收方来得及接收；：发方发送数据的速率必须使收方来得及接收；差错控制差错控制：收方收到有差错的数据帧时，能检错重传或纠：收方收到有差错的数据帧时，能检错重传或纠错；错；透明传输透明传输：不管所传数据是什么样的比特组合，收方都能：不管所传数据是什么样的比特组合，收方都能正确接收。并能正确接收。并能将数据与控制信息分开；将
3、数据与控制信息分开；寻址寻址：保证每一帧都能发送到目的站。：保证每一帧都能发送到目的站。设计要点设计要点；1）向网络层提供一个定义良好的服务接口）向网络层提供一个定义良好的服务接口 2）处理传输错误）处理传输错误 3）调节数据流，确保慢速的接收方不会被除快）调节数据流，确保慢速的接收方不会被除快速的发送方淹没。速的发送方淹没。5.1.2 5.1.2 为网络层提供的服务为网络层提供的服务最主要的服务是将数据从源机器的网络层传输到目最主要的服务是将数据从源机器的网络层传输到目标机器的网络层标机器的网络层.无确认的无连接的服务无确认的无连接的服务：(P56)(P56)适用于误码率很低的通信信道；或语
4、音通信；适用于误码率很低的通信信道；或语音通信；有确认的无连接的服务有确认的无连接的服务：适用于误码率很高的通信信道；如无线通信；适用于误码率很高的通信信道；如无线通信；有确认的面向连接的服务有确认的面向连接的服务：适用于通信要求较高（可靠性、实时性）的情况适用于通信要求较高（可靠性、实时性）的情况5.1.35.1.3成帧方法成帧方法字符计数法字符计数法：在帧头部指明帧内字符数。在帧头部指明帧内字符数。问题：由于传输差错导致计数值被问题：由于传输差错导致计数值被“篡改篡改”；字符填充首尾界符法：字符填充首尾界符法：以以ASCII字符字符DLE和和STX作为帧的头部，作为帧的头部，DLE和和ET
5、X作为帧的尾部（作为帧的尾部（DLE10H、STX02H、ETX 03H）技术：如何避免二进制数据可能与帧的头尾标志技术：如何避免二进制数据可能与帧的头尾标志相同？相同？发送方在数据中遇到发送方在数据中遇到DLE时，自动在其前后插入时，自动在其前后插入一个一个DLE;接收方在数据中遇到单个接收方在数据中遇到单个DLE时时,可确定帧界可确定帧界;遇遇到到2个个DLE时，自动删除一个时，自动删除一个DLE。位填充首尾标志法：以一个特定的字节信息作为帧的头尾标志；如01111110；为了避免与原始数据比特组合相同，发送方在数据中遇到5个连续的1时，自动在其后插入一个0；接收方在数据中遇到5个连续的1
6、后面跟着一个0，自动将此0删除。5.1.4 差错控制差错控制差错产生的原因主要由通信信道的噪声引起，差错产生的原因主要由通信信道的噪声引起，通信信道噪声分为二种：通信信道噪声分为二种：（1）热噪声：由传输介质导体的电子热运）热噪声：由传输介质导体的电子热运动产生。幅度较小，是产生随机差错的主动产生。幅度较小，是产生随机差错的主要根源；要根源；（2）冲击噪声：由外界电磁干扰产生，幅）冲击噪声：由外界电磁干扰产生，幅度较大，是产生突发差错的主要根源。度较大，是产生突发差错的主要根源。其中冲击噪声是引起差错的主要原因。其中冲击噪声是引起差错的主要原因。n差错评价指标如下：差错评价指标如下：n（1）误
7、码率：）误码率：错传的码元数与所传输码元总数错传的码元数与所传输码元总数之比。之比。n PeNe/Nn其中，其中，N 传输的码元总数，传输的码元总数，Ne 错传的的码错传的的码元数。元数。n（2）误比特率：）误比特率：n错传的比特数与所传输总比特数之比。错传的比特数与所传输总比特数之比。n在二进制码元时，误比特率误码率。在二进制码元时，误比特率误码率。n差错控制的基本方式如下：差错控制的基本方式如下：n（1）反馈纠错）反馈纠错n 在接收端能发现差错，但不能确定错码的位置，通在接收端能发现差错，但不能确定错码的位置，通过反馈信息请求发送端重发，直到接收端肯定确认为止。过反馈信息请求发送端重发，直
8、到接收端肯定确认为止。n 适用于双工通信和非实时通信系统。适用于双工通信和非实时通信系统。n（2）前向纠错）前向纠错n在接收端不仅能发现错码，而且还能确定错码的位置，在接收端不仅能发现错码，而且还能确定错码的位置，并纠正错误。并纠正错误。n适用于单工通信和实时通信系统。适用于单工通信和实时通信系统。n（3）混合纠错）混合纠错n少量差错在接收端自动纠正，若超出自行纠正能力时，少量差错在接收端自动纠正，若超出自行纠正能力时，通过反馈信息请求发送端重发。通过反馈信息请求发送端重发。5.1.5流控制流控制u基于反馈的流控制基于反馈的流控制u基于速率的流控制基于速率的流控制5.2 错误检测和纠正错误检测
9、和纠正码字的检错与纠错能力码字的检错与纠错能力码字码字(n位位)数据码数据码(m位位)+冗余码冗余码(r位位)。海明距离：两个码字之间对应码元位的不同海明距离：两个码字之间对应码元位的不同码元的个数。码元的个数。码字编码的海明距离码字编码的海明距离对于一种码字编码，在这个码字集合中，可对于一种码字编码，在这个码字集合中，可得到所有任意两个码字的海明距离，得到所有任意两个码字的海明距离，其中其中最小的海明距离称为该码字编码的海明距最小的海明距离称为该码字编码的海明距离离d。n定理定理1：如果：如果d2t+1,则该编码可则该编码可纠正纠正任何任何t个个(或或t个以下个以下)的错误。的错误。n定理定
10、理2：如果：如果de+1,则该编码可则该编码可检测检测出出任何任何e个个(或或e个以下个以下)的错误。的错误。一般情况下，冗余位越多一般情况下，冗余位越多(即即r越大越大)，检错，检错纠错能力越强，但相应的编码效率也随之纠错能力越强，但相应的编码效率也随之降低了。降低了。示例：偶校验的检错与纠错能力示例：偶校验的检错与纠错能力例：例：对于偶校验（对于偶校验（使每个码字中都有偶数个使每个码字中都有偶数个1）数）数据码为据码为2位（有用数据为位（有用数据为00、01、10、11）冗余）冗余码为码为1位（偶校验位）位（偶校验位）有用数据经过偶校验编码，其码字集合：有用数据经过偶校验编码，其码字集合：
11、000、011、101、110；该编码的海明距离该编码的海明距离d=2，根据根据定理定理1，该编码不能纠正任何错误该编码不能纠正任何错误(t0)。D=2t+1D=2t+1根据根据定理定理2，该编码可检测出任何该编码可检测出任何1个错误个错误(e1)。D=e+1D=e+1奇校验的检错能力与偶校验一样。奇校验的检错能力与偶校验一样。误码控制编码的分类误码控制编码的分类按冗余码的控制功能分按冗余码的控制功能分:纠错码纠错码：在接收端能发现并自动纠正差：在接收端能发现并自动纠正差错。叫前向纠错错。叫前向纠错纠错检错的常用方法纠错检错的常用方法海明码海明码：可纠错和检错，实现复杂，效：可纠错和检错，实现
12、复杂，效率低。率低。奇偶校验码奇偶校验码：方法简单，检错能力差。：方法简单，检错能力差。循环冗余编码循环冗余编码(CRC)：实现容易，检错：实现容易，检错能力强，广泛使用。能力强，广泛使用。5.2.15.2.1纠错码：海明码纠错码：海明码海明在海明在1950年提出的可纠正年提出的可纠正一位错一位错的编码方法。的编码方法。用用r个校验位构造出个校验位构造出r个校验关系式来指示一位错码的个校验关系式来指示一位错码的n(=m+r)种可能位置及表示无差错。种可能位置及表示无差错。n码字排列：从最左边位开始依次编号码字排列：从最左边位开始依次编号(1、2、n);r个校验位：在个校验位：在2k的位置的位置
13、(1、2、4、8、);m个数据位：在其余位个数据位：在其余位(3、5、6、7、9、)。r的确定：的确定：r2rm+1;（r2 n1=m+r+1）例如：例如：4个信息位个信息位D1D2D3D4，3个校验位个校验位P1P2P3。5.2.25.2.2检错码：循环冗余码检错码：循环冗余码CRC码码n特点：特点：实现容易，检错能力强，广泛使用。实现容易，检错能力强，广泛使用。常结合常结合反馈重传法反馈重传法来保证信息的可靠传输。来保证信息的可靠传输。n码字组成：码字组成：例：若数据码例：若数据码110011，可表示为：可表示为：M(x)=1x5+1x4+0 x3+0 x2+1x+1即：即：M(x)=x5
14、+x4+x+1。生成多项式生成多项式G(x)：G(x)=grxr+.+gixi+.+g1x+g0其中其中,gi=0或或1,ri0,gr 0,g0 0,共共r+1位位G(x)被通信双方事先共同选定使用：被通信双方事先共同选定使用：发送端：通过发送端：通过G(x)生成校验码；生成校验码；接收端：通过接收端：通过G(x)校验接收的码字。校验接收的码字。对于多项式的运算：采用模对于多项式的运算：采用模2计算（加法不进位，减法不借位）；计算（加法不进位，减法不借位）；加减法是一样的。加减法是一样的。模模2计算即是异或运算。计算即是异或运算。循环冗余检验的原理循环冗余检验的原理 n在数据链路层传送的帧中，
15、广泛使用了循在数据链路层传送的帧中，广泛使用了循环冗余检验环冗余检验 CRC 的检错技术。的检错技术。n在发送端，先把数据划分为组。假定每组在发送端，先把数据划分为组。假定每组 k 个比特。个比特。n假设待传送的一组数据假设待传送的一组数据 M=101001（现在（现在 k=6）。我们在）。我们在 M 的后面再添的后面再添加供差错检测用的加供差错检测用的 n 位冗余码一起发送。位冗余码一起发送。冗余码的计算冗余码的计算 n用二进制的模用二进制的模 2 运算进行运算进行 2n 乘乘 M 的运算，的运算，这相当于在这相当于在 M 后面添加后面添加 n 个个 0。n得到的得到的(k+n)位的数除以位
16、的数除以事先选定好事先选定好的长度为的长度为(n+1)位的除数位的除数 P，得出商，得出商是是 Q 而余数是而余数是 R，余数，余数 R 比除数比除数 P 少少1 位，即位，即 R 是是 n 位。位。冗余码的计算举例冗余码的计算举例 n现在现在 k=6,M=101001。n除数除数 P=1101，则，则 n=3,n被除数是被除数是 2nM=101001000。110101 Q(商)P(除数)1101 101001000 2nM(被除数)1101 1110 1101 0111 0000 1110 1101 0110 0000 1100 1101 001 R(余数)，作为 FCS 循环冗余检验的原
17、理说明循环冗余检验的原理说明 n模模 2 运算的结果是：商运算的结果是：商 Q=110101，余数余数 R=001。n把余数把余数 R 作为冗余码添加在数据作为冗余码添加在数据 M 的后的后面发送出去。发送的数据是：面发送出去。发送的数据是：2nM+R 即：即：101001001，共，共(k+n)位。位。检测出差错检测出差错n接收方对接收到的数据除以同样的除数接收方对接收到的数据除以同样的除数,只要得只要得出的余数出的余数 R 不为不为 0，就表示检测到了差错。，就表示检测到了差错。n但这种检测方法并不能确定究竟是哪一个或哪几但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。个比特出
18、现了差错。n一旦检测出差错，就丢弃这个出现差错的帧。一旦检测出差错，就丢弃这个出现差错的帧。n只要经过严格的挑选，并使用位数足够多的除数只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。，那么出现检测不到的差错的概率就很小很小。1 数据链路(即逻辑链路)与链路(即物理链路)有何区别?“电路接通了”与”数据链路接通了”的区别何在?n答：数据链路与链路的区别在于数据链路出链路外，还必须答：数据链路与链路的区别在于数据链路出链路外，还必须有一些必要的规程来控制数据的传输，因此，数据链路比链有一些必要的规程来控制数据的传输，因此，数据链路比链路多了实现通信规程所需
19、要的硬件和软件。路多了实现通信规程所需要的硬件和软件。n“电路接通了电路接通了”表示链路两端的结点交换机已经开机，物理表示链路两端的结点交换机已经开机，物理连接已经能够传送比特流了，但是，数据传输并不可靠，在连接已经能够传送比特流了，但是，数据传输并不可靠，在物理连接基础上，再建立数据链路连接，才是物理连接基础上，再建立数据链路连接，才是“数据链路接数据链路接通了通了”，此后，由于数据链路连接具有检测、确认和重传功，此后，由于数据链路连接具有检测、确认和重传功能，才使不太可靠的物理链路变成可靠的数据链路，进行可能，才使不太可靠的物理链路变成可靠的数据链路，进行可靠的数据传输当数据链路断开连接时
20、，物理电路连接不一定靠的数据传输当数据链路断开连接时，物理电路连接不一定跟着断开连接。跟着断开连接。2 为了进行差错控制为了进行差错控制,必须对传送的数据进行校验必须对传送的数据进行校验.在局在局域网中广泛使用的校验方法是域网中广泛使用的校验方法是_(1)_,CRC-16标准标准规定生成多项式为规定生成多项式为G(x)=x16+X15+x2+1,它产生的它产生的校验码是校验码是_(2)_位位,接收端发现错误后采取的措施是接收端发现错误后采取的措施是_(3)_.如果如果CRC的生成多项式是的生成多项式是G(x)=x4+x+1,信息码字是信息码字是10110,由计算出来的由计算出来的CRC校验码是
21、校验码是_(4)_.(1)A 奇偶检验奇偶检验 B 海明码海明码 C格雷码格雷码 D 循环冗余校验循环冗余校验(2)A 2 B 4 C 16 D 32(3)A 自动纠错自动纠错 B 报告上层协议报告上层协议 C 自动请求重发自动请求重发 D 重重新生成原始数据新生成原始数据(4)A 0100 B1010 C 0111 D 1111书上作业练习书上作业练习:P845-41 要发送的数据为1101011011。采用CRC的生成多项式是P（X）=X4+X+1。试求应添加在数据后面的余数。数据在传输过程中最后一个1变成了0，问接收端能否发现？若数据在传输过程中最后两个1都变成了0，问接收端能否发现？采
22、用CRC检验后，数据链路层的传输是否就变成了可靠的传输？n答：作二进制除法，答：作二进制除法，1101011011 0000 10011 得余数得余数1110，添加的，添加的检验序列是检验序列是1110.n 作二进制除法，两种错误均可发现作二进制除法，两种错误均可发现n仅仅采用了仅仅采用了CRC检验，缺重传机制，数据检验，缺重传机制，数据链路层的传输还不是可靠的传输。链路层的传输还不是可靠的传输。本课重点本课重点n掌握掌握CRC冗余校验码的计算冗余校验码的计算.5.3 5.3 基本数据链路协议基本数据链路协议数据链路协议主要考虑的问题：数据链路协议主要考虑的问题：避免所传送的数据可能出现差错和
23、丢失；避免所传送的数据可能出现差错和丢失；使发方发送数据的速率适应收方的接收能力。使发方发送数据的速率适应收方的接收能力。理想化的数据传输理想化的数据传输假设假设1：所传送的数据即不会出现差错和也：所传送的数据即不会出现差错和也不会丢失；不考虑差错控制问题）不会丢失；不考虑差错控制问题）假设假设2：接收端的数据接收速率足够快，有：接收端的数据接收速率足够快，有能力接收发送端的数据发送率。能力接收发送端的数据发送率。（不考虑流量控制问题）（不考虑流量控制问题）在理想化的条件下，数据链路在理想化的条件下，数据链路层不需要：层不需要：差错控制协议；差错控制协议；流量控制协议；流量控制协议；就可保证数
24、据的正确传输。就可保证数据的正确传输。实用的停止等待协议（实用的停止等待协议（ARQ）去掉假设去掉假设1 1；去掉假设；去掉假设2 2。考虑差错控制问题考虑差错控制问题差错控制协议；差错控制协议；考虑流量控制问题考虑流量控制问题流量控制协议；流量控制协议；n初步协议：初步协议：发送端发送数据帧后，等待接收端的应答帧；发送端发送数据帧后，等待接收端的应答帧；接收端收到数据帧后，通过接收端收到数据帧后，通过CRC校验校验(一般用硬一般用硬件检验件检验)，如果无差错，回送一个，如果无差错，回送一个确认帧确认帧ACKACK，否，否则，回送一个则，回送一个否认帧否认帧NAKNAK。发送端收到应答帧，发送
25、端收到应答帧，n如果是如果是ACKACK，发送下一数据帧，发送下一数据帧，n如果是如果是NAKNAK，重发数据帧。，重发数据帧。死锁现象死锁现象：当出现帧丢失时，发送端永当出现帧丢失时，发送端永远等待下去。远等待下去。如何解决？如何解决？解决方法：解决方法：发送端设立一个超时计时器，发送端设立一个超时计时器，发送完一个数据帧时，就启动它；发送完一个数据帧时，就启动它；如果在规定时间如果在规定时间tout内得不到应答内得不到应答帧，就判定为超时，重传数据帧。帧，就判定为超时，重传数据帧。Tout也称重传时间也称重传时间重复帧差错：重复帧差错：若应答帧丢失，按照超若应答帧丢失，按照超时重发方法，接
26、收端将收到时重发方法，接收端将收到重复帧，如何解决？重复帧，如何解决？解决方法：解决方法：给每个数据帧附加不同的发送序给每个数据帧附加不同的发送序号号Ns，如果接收端收到相同序，如果接收端收到相同序号的数据帧号的数据帧,则丢弃则丢弃,并回送一并回送一个个ACKACK。发送序号需要多少位发送序号需要多少位?n 对于对于ARQ协议，发送序号有协议，发送序号有0和和1即可即可(只需只需1个个bit);n每发一个新的数据帧，发送序号就和上次发送的每发一个新的数据帧，发送序号就和上次发送的不一样，不一样，n重发的数据帧发送序号不变。重发的数据帧发送序号不变。ARQ协议：协议：重传时间重传时间tout的选
27、择的选择n若若Tout 太长，浪费时间，太长，浪费时间，n若若Tout 太短，过早重传数据，产生太短，过早重传数据，产生“额外额外”应应答帧。答帧。n如何解决？如何解决？n提示：在确认帧提示：在确认帧ACK和否认帧和否认帧NAK中附加序中附加序号。号。停止等待协议的信道利用率停止等待协议的信道利用率连续连续ARQ协议协议n目的：目的：提高信道利用率。提高信道利用率。n方法：方法：n发送端发送完一个数据帧后，不停下来等待应答发送端发送完一个数据帧后，不停下来等待应答n帧，而是连续再发送数据帧。当收到否认帧帧，而是连续再发送数据帧。当收到否认帧NAK时，时，n再控制重发。再控制重发。n实现要求：实
28、现要求：n数据帧需附加发送序号信息。否认帧附加出错的数据帧需附加发送序号信息。否认帧附加出错的n数据帧发送序号。数据帧发送序号。n常用协议：常用协议：n回退回退N帧帧ARQ协议（协议（go back n）n选择重发选择重发ARQ协议（协议（selective repeat）回退回退N帧帧ARQ协议（协议（go back n）n方式方式1：n反馈否认帧反馈否认帧NAK（含出错的数据帧发送序号）。（含出错的数据帧发送序号）。再从出错的数据帧开始重传。再从出错的数据帧开始重传。n要求：发送端要求有一个能存储要求：发送端要求有一个能存储N个数据帧的缓个数据帧的缓冲区。冲区。n接收端只需能存储一个数据帧
29、的缓冲。接收端只需能存储一个数据帧的缓冲。n 方式方式2：n不反馈否认帧不反馈否认帧NAK。发送端采用超时机制。发送端采用超时机制。n发送端每发送一个数据帧就启动该帧计时器，发送端每发送一个数据帧就启动该帧计时器，当收到确认帧后，计时器复位；如果直到超当收到确认帧后，计时器复位；如果直到超时还没有收到确认帧，则重发该数据帧及后时还没有收到确认帧，则重发该数据帧及后继的帧。继的帧。选择重发选择重发ARQ协议协议（selective repeat）n目的：目的：进一步提高信道利用率。进一步提高信道利用率。n方法：只重传出现差错的数据帧或者超时的数据方法：只重传出现差错的数据帧或者超时的数据帧。帧。
30、n要求：在接收端要设置具有相当容量的缓存空间。要求：在接收端要设置具有相当容量的缓存空间。选择重发选择重发ARQ协议工作原理示协议工作原理示意图意图5.4 5.4 滑滑动窗口协议动窗口协议（Sliding Windows protocol）n当未被确认的数据帧数目太多时；只要有一帧出错，当未被确认的数据帧数目太多时；只要有一帧出错，就有很多数据帧需要重传，因而增大开销。就有很多数据帧需要重传，因而增大开销。n为了对发送出去的大量未被确认的数据帧进行编号，为了对发送出去的大量未被确认的数据帧进行编号，每个数据帧的发送序号也要占用较多的比特数，因而又每个数据帧的发送序号也要占用较多的比特数，因而又
31、增大了开销。增大了开销。n对于连续对于连续ARQ协议，采用了发送端不等待确认帧返回就协议，采用了发送端不等待确认帧返回就可连续发送帧，存在问题：可连续发送帧，存在问题：n滑动窗口协议滑动窗口协议：n对发送端已发送出去但未被确认的帧的数目加以限制。对发送端已发送出去但未被确认的帧的数目加以限制。n在发送端和接收端分别设置在发送端和接收端分别设置发送窗口发送窗口和和接收窗口接收窗口。发送窗口发送窗口（在发送端（在发送端）n目的：用来对发送端进行流量控制。目的：用来对发送端进行流量控制。n发送窗口尺寸发送窗口尺寸Ws：在还没有收到应答帧的情况下，：在还没有收到应答帧的情况下，n发送端最多可以连续发送
32、数据帧的个数。发送端最多可以连续发送数据帧的个数。n发送序号：发送序号：n一般采用一般采用n位位bit进行编号（进行编号（02n-1）。）。n若若n=3；则用；则用3位位bit进行编号（进行编号（07）。）。n发送端只能连续发送窗口内的数据帧；发送端只能连续发送窗口内的数据帧；n每收到一个确认帧后，发送窗口的前、后沿顺每收到一个确认帧后，发送窗口的前、后沿顺时针旋转一个号，并可以一个发送新的数据帧。时针旋转一个号，并可以一个发送新的数据帧。n若未应答帧的数目等于发送窗口尺寸时，便停若未应答帧的数目等于发送窗口尺寸时，便停止发送新的数据帧。止发送新的数据帧。接收窗口接收窗口（在接收端）（在接收端
33、）n目的：用来控制可以接收哪些数据帧而不可以接目的：用来控制可以接收哪些数据帧而不可以接收哪些帧。收哪些帧。n接收窗口接收窗口Wr：只有当收到的数据帧的发送序号：只有当收到的数据帧的发送序号落入接收窗口内，才允许将该数据帧收下；否则，落入接收窗口内，才允许将该数据帧收下；否则，丢弃。丢弃。n如果如果Wr=1，意味着只能按顺序接收数据帧。，意味着只能按顺序接收数据帧。n如果如果Wr较大，有可能会出现数据帧的失序。较大，有可能会出现数据帧的失序。n差错情况差错情况：设：设Wr=1；n 若收到若收到0号数据帧，接收窗口顺时针旋转一号数据帧，接收窗口顺时针旋转一个号，个号，n并发出并发出0号确认帧；准
34、备接收号确认帧；准备接收1号数据帧。号数据帧。n此时，如果收到的不是此时，如果收到的不是1号数据帧，而是号数据帧，而是0号数号数据帧，表明发出据帧，表明发出0号确认帧发送端没有收到，因号确认帧发送端没有收到，因此再发送一次此再发送一次0号确认帧，此时收到的号确认帧，此时收到的0号数据号数据帧必须丢弃，否则发生重复。帧必须丢弃，否则发生重复。n 若是若是2号数据帧，表明发送端发出的号数据帧，表明发送端发出的1号数据号数据帧丢失，因此发送帧丢失，因此发送1号否认帧，让对方重新发送号否认帧，让对方重新发送1号数据帧。号数据帧。应答帧丢失情况应答帧丢失情况应答帧被应答帧被“篡改篡改”情况情况:ACKN
35、AK重叠问题重叠问题n在接收前后，接收窗口范围内的有效序号出现在接收前后，接收窗口范围内的有效序号出现重叠。重叠。避免重叠问题避免重叠问题n为了避免重叠问题，接收窗口尺寸为了避免重叠问题，接收窗口尺寸Wr2n/2。发送窗口的最大尺寸值发送窗口的最大尺寸值累积确认方法累积确认方法n 接收端在连续接收若干个正确的数据帧接收端在连续接收若干个正确的数据帧以后，对最后一个数据帧发回确认帧。以后，对最后一个数据帧发回确认帧。窗口控制协议的信道利用率窗口控制协议的信道利用率窗口控制协议的信道利用率n设：单程传输时延Td，数据帧发送时间Tf，n数据传输率C，数据帧长度L，窗口尺寸Wsn在正常传输情况下，忽略
36、应答帧长度和处理时间：依据信道利用率进行窗口尺寸的选择依据信道利用率进行窗口尺寸的选择n优化原则：优化原则：n 发送端收到窗口中第一个已发数据帧的确发送端收到窗口中第一个已发数据帧的确认时，正好发完窗口中的最后一个数据帧。认时，正好发完窗口中的最后一个数据帧。nWs大于上述选择，则大于上述选择，则Cr=100%，但浪费缓，但浪费缓冲区；冲区；nWs小于上述选择，则小于上述选择，则Cr=2a+1,N近近似等于似等于2a+1,则则n当当W=2a+1,由上面知由上面知a=2.35n故故w=2X2.35+1=5.7n取取w=6121aE12aWEn3)nP一般比较小一般比较小,在分母看作为在分母看作为
37、0,故得故得:n由于由于w=4,2a+1=5.7,为小窗口为小窗口,nW=w(1-p)/2a+1=4X(1-0.01)/5.7=0.69)12()1)(12()1()12(11aWnppapWaWnppPE)12()12()1()12(1aWapWaWPE5.5 协议协议n1.协议开发过程协议的形式描述协议的形式描述n描述方法：n有限状态机n 采用状态流程图进行描述。n事件状态表n 采用表格进行描述。n结构化程序n 采用程序代码进行描述。nPetri网模型n 采用状态流程图进行描述。有限状态机模型有限状态机模型FSMnFSM协议描述方法也称状态转移图。n特点：易懂、易理解和易于实现。n组成：状
38、态圆和有向弧。Petri网模型网模型n德国德国C.A.Petrit提出提出(1962,博士论文博士论文)。n4个基本元素：个基本元素：n位置：系统可能处于的状态；用圆圈表示。位置：系统可能处于的状态；用圆圈表示。n转换：改变状态；用线段表示。转换：改变状态；用线段表示。n有向弧：位置与转换之间的相互依赖关系；有向弧：位置与转换之间的相互依赖关系；用弧线表示。用弧线表示。n标记：系统当前处于的状态；在圆圈中用标记：系统当前处于的状态；在圆圈中用黑点表示。黑点表示。数据链路层示例数据链路层示例n分类：高级数据链路控制高级数据链路控制HDLCn1976年，年，ISO提出提出HDLC（High-lev
39、el Data Link Control）n适用范围：适用范围：n计算机计算机计算机、计算机计算机、计算机终端、终端终端、终端终端终端n三种类型的站：三种类型的站：n 主站：主要功能是发送命令（包括数据），接收主站：主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、响应，负责整个链路的控制（如系统的初始、流控、n 差错恢复等）；差错恢复等）；n 次站：主要功能是接收命令，发送响应，配合主次站：主要功能是接收命令，发送响应，配合主站完成链路的控制；站完成链路的控制；n复合站：同时具有主、次站功能，既发送又接收命复合站：同时具有主、次站功能，既发送又接收命令和响应，
40、并负责整个链路的控制。令和响应，并负责整个链路的控制。HDLC的链路构型n非平衡配置非平衡配置n 主站控制整个链路工作。主站控制整个链路工作。主站主站发出的帧叫发出的帧叫命令；命令；次站次站发出的帧叫响应。发出的帧叫响应。n 适合把智能和半智能的终端连接到计算机。适合把智能和半智能的终端连接到计算机。HDLC的链路构型的链路构型n平衡配置平衡配置n 复合站复合站具有主站和次站的功能。地位具有主站和次站的功能。地位平等。平等。n 适合于计算机和计算机之间的连接适合于计算机和计算机之间的连接HDLC的基本操作模式的基本操作模式n正规响应模式正规响应模式NRMNRM：n 适用于点适用于点点式和多点式
41、两种非平衡构型。点式和多点式两种非平衡构型。只有当主站向次站发出探询后，次站才能获得只有当主站向次站发出探询后，次站才能获得传输帧的许可。传输帧的许可。n异步响应模式异步响应模式ARMARM：n 适用于点适用于点点式非平衡构型和主站点式非平衡构型和主站次站式次站式平衡构型。次站可以随时传输帧，不必等待主平衡构型。次站可以随时传输帧，不必等待主站的探询。站的探询。n异步平衡模式异步平衡模式ABMABM：n 适用于通信双方都是复合站的平衡构型，也适用于通信双方都是复合站的平衡构型，也采用异步响应，双方具有同等能力。采用异步响应，双方具有同等能力。HDLC的帧结构的帧结构n帧标志（帧标志（FlagF
42、lag）n定界符为定界符为011111107EH（零比特填充法）。（零比特填充法）。n地址域（地址域（AddressAddress）n多终端线路，用来区分终端；多终端线路，用来区分终端；n点到点线路，有时用来区分命令和响应。点到点线路，有时用来区分命令和响应。n 若是接收该帧的站的地址，则该帧是命令帧；若是接收该帧的站的地址，则该帧是命令帧；n 若是发送该帧的站的地址，则该帧是响应帧。若是发送该帧的站的地址，则该帧是响应帧。HDLC的帧结构的帧结构n有效地址为有效地址为254个（通常为个（通常为8位，可扩展到位，可扩展到16位）位）n 全全1的的8位地址表示广播（所有次站接收）；位地址表示广播
43、（所有次站接收）；n 全全0的的8位地址是无效地址。位地址是无效地址。n控制域（控制域（Control）n标识帧的类型和功能，使对方站执行特定的操作。标识帧的类型和功能，使对方站执行特定的操作。n 信息帧（信息帧（Information帧）；帧）；n 管理帧（管理帧（Supervisory帧）；帧）；n 无序号帧（无序号帧（Unnumbered帧）。帧）。HDLC的帧结构的帧结构n数据域（数据域（Data）n任意比特串或字符串（有上限）任意比特串或字符串（有上限）n校验和（校验和（Checksum）n循环冗余校验（循环冗余校验（CRC）n生成多项式：生成多项式：控制域的格式控制域的格式nSeq
44、发送序号发送序号n 使用滑动窗口技术，使用滑动窗口技术，3位序号，发送窗口位序号，发送窗口Ws=7；nNext捎带确认捎带确认n 接收站期望收到的帧序号，而不是最后一个已接收站期望收到的帧序号，而不是最后一个已收到的帧序号；收到的帧序号；控制域的格式控制域的格式nP/F询问询问/终止终止n 命令帧置命令帧置P位，表示要求对方立即发送响应；位，表示要求对方立即发送响应；n 响应帧置响应帧置F位，表示要发送的数据已经发送完毕。位，表示要发送的数据已经发送完毕。n 注：最后一个帧注：最后一个帧P/F位置为位置为“F”，其它置为，其它置为“P”。n 有些协议，有些协议，P/F位用来强迫对方机器立刻发控
45、制帧；位用来强迫对方机器立刻发控制帧；nType类型类型n“Type0”表示确认帧；表示确认帧；“Type1”表示否定帧。表示否定帧。n“Type2”表示接收未准备好；表示接收未准备好；“Type3”表示选择拒表示选择拒绝。绝。n无序号帧无序号帧n 可以用来传控制信息，也可在不可靠无连接服务可以用来传控制信息，也可在不可靠无连接服务n中传数据。中传数据。n尽管尽管HDLC被广泛地被使用了被广泛地被使用了,但它还不够完美但它还不够完美,这就是这就是网络网络.因特网的点对点协议因特网的点对点协议PPPn1992年，年，PPP:Point-to-Point Protocoln应用：应用：拨号方式入网
46、拨号方式入网n 专线方式入网专线方式入网PPP的组成的组成nInternet 需要一个点到点协议需要一个点到点协议,它有多种用途它有多种用途,其中包括传送从路由器到路由器之间的流量其中包括传送从路由器到路由器之间的流量,以及以及从家庭用户到从家庭用户到ISP之间的流量之间的流量.nPPP处理错误检测处理错误检测,支持多个协议支持多个协议,允许在连接时允许在连接时刻协商刻协商IP地址地址,允许身份认证允许身份认证.nPPP提供了三类功能提供了三类功能:(P201)n成帧方法（面向比特和面向字符）成帧方法（面向比特和面向字符）n链路控制协议链路控制协议LCPn网络控制协议网络控制协议NCPPPP的
47、帧结构的字段描述的帧结构的字段描述n帧标志（帧标志（FlagFlag）n定界符为定界符为011111107EH。n 在同步链路传输时：采用零比特填充法；在同步链路传输时：采用零比特填充法；n 在异步链路传输时：采用字符填充法。在异步链路传输时：采用字符填充法。n 若数据字段出现一个若数据字段出现一个7EH，变为，变为7DH和和5EH；n 若数据字段出现一个若数据字段出现一个7DH，变为，变为7DH和和5DH；n 若数据字段出现若数据字段出现ASCII码的控制字符码的控制字符(小于小于20Hn 的字符的字符)，则在该字符前插入一个，则在该字符前插入一个7DH。n地址域（地址域（AddressAd
48、dress）n 始终为始终为FFH。实际上，不需要地址。实际上，不需要地址。PPP的帧结构的字段描述的帧结构的字段描述n控制域控制域（Control）n 一般为一般为03H，表示是无序号帧。，表示是无序号帧。n协议域协议域（Protocol）n 若为若为C021H，则数据字段是，则数据字段是PPP链路控制链路控制数据；数据；n 若为若为8021H，则数据字段是，则数据字段是PPP网络控制网络控制数据。数据。n净荷域净荷域:最大不超过最大不超过15001500字节字节PPP的通信过程的通信过程n当用户拨号接入当用户拨号接入ISP，n 路由器的路由器的modem对拨号做出确认，对拨号做出确认，n
49、建立一条物理连接；建立一条物理连接；n PC机发送机发送LCP分组（分组（PPP参数）参数）n 路由器进行网络层配置，路由器进行网络层配置，n NCP给给PC机一个临时机一个临时IP地址；地址；n当用户挂机时，当用户挂机时，n NCP释放网络层连接，释放网络层连接，n 收回原来分配出去的收回原来分配出去的IP地址；地址；n LCP释放数据链路层连接，释放数据链路层连接，n 最后，释放物理层连接。最后，释放物理层连接。本章小结本章小结u数据链路层的任务数据链路层的任务u 检错与纠错检错与纠错u滑动窗口协议滑动窗口协议uHDLC与与PPP协议协议u相应协议的软件程序实现相应协议的软件程序实现作业作业n5-41n5-42
