第三章 链路层

1、数据链路层 广域网的链路层：本章 局域网的链路层：在局域网中 (物理物理)链路链路：一条无源的点到点的物理线路，中间没有任何交换节点 基于物理层的协议，可以建立物理线路 （即把多个链路通过接口串联起来），但要能在这条线路上传送数据，还需要赋予物理链路一些基本的功能，可能的功能包括： 链路管理：链路管理： 数据链路的建立、维持和释放 帧同步：帧同步： 在数据链路层的PDU是帧，帧同步的目的就是要在比特流中准确区分一个帧的开始和结束。 流量控制：流量控制： 收发数据的双方收发数据的速率匹配 差错控制：差错控制： 纠正或检测数据帧中的差错 区分数据和控制信息：区分数据和控制信息： 透明传输：透明传输

2、： 寻址：寻址： 物理链路在赋予了这些功能就可实现可靠的数据传输。为实现这些功能，需要一些必要的规程来控制数据的传输，这些规程就是数据链路的协议。 数据链路数据链路：物理链路加上必要的通信规程而形成的逻辑链路。 数据链路层协议数据链路层协议：为在不太可靠的物理链路上建立数据链路从而实现可靠的数据传输而规定的一些规程。 最简单而又最基本的一个数据链路层协议是停止等待停止等待协议协议停止等待协议(stop-and-wait)两机通过一条链路进行通信的简化模型主机AAP主机BBP链路链路层A链路层A缓冲区 一般，数据的传输受到两个因素的影响 (A)信道可靠性 (B)发送和接收能力 理想情况下 (A)

3、信道无差错,不丢失：无需检错重发 (B)接收端向主机交付数据的速率永远不会低于发送端发送数据的速率; 或者缓存无限大 : 无需流量控制 此时无需任何协议 而在一般情况下，上述情况难以保证。 以下先保留假设保留假设A，去掉假设，去掉假设B，此时只需要流量控制，即保证收方的缓冲区不会因为发方发送数据太快来不及向上层交付而导致溢出。 最简单的停止-等待协议进行流量控制 发送方： 1. 从主机取一个数据帧放到缓冲区后发送 2. 等待 3. 若收到接收方的确认信息，转到 1 接收方 1. 等待 2. 若收到发送方发来的数据帧，将其放入接收缓冲区并向上转交 3. 向发送方发送一个确认消息，表示缓冲区已空，

4、可以接收下一个数据 4. 转到 1 这样只需要一个数据帧的缓冲区就可以保证无溢出。停止等待协议data iACKdata i+1发出对刚收到的发出对刚收到的数据帧的应答数据帧的应答发出一帧发出一帧等待，直到收到等待，直到收到ACK才发送下一帧才发送下一帧发送方发送方接收方接收方 去掉假设去掉假设A、 B的一般情况，不仅要流量控制，还要进行差错控制（信道不可靠），几种情况下的处理方式：实用的停止-等待协议: (设缓冲区可以装下一个数据帧) 情况1 情况2 情况3 情况4情况1：正常情况2：数据帧错（但已接收）：解决方案：重发情况3：数据丢失之数据帧丢失 ：导致死锁解决方案：超时重发情况4：数据帧

5、正确，但应答帧丢失，超时重发后，使得该数据帧在接收方收到两次：重复帧 解决方案：使每个数据帧带上不同的发送序号，每发送一个新的帧就把它的发送序号加1，这样，若两个数据帧序号相同，则为重复帧，可丢弃一个。对于每次只发送一个帧的停止等待协议，可以只用两个不同的编号（一个比特）停等协议的算法流程停等协议的算法流程SGet 1st Data from Network LayerV(s) = 0N(s)= V(s)Save Date Frame to BufferSend Buffered Data Frame to Physical LayerStart TimerWait EventReceived

6、 ACKReceived NAKTime OutGet Next Data V(s) = 1-V(s)RV(r) = 0Wait Data FrameReceived Frame, and Test if Error occursCorrectErrorN(s) = V(r) ?Discard FramePass Data toNetwok Layer Send ACKSend NAKSend ACKV(r)= 1-V(r) 教材上的算法教材上的算法在发现出错帧后,收方丢弃并不发NAK,而由发方的超时定时器控制自动重发. 由于发送端对出错的数据进行重发是自动进行的，所以这种差错控制体制又简称为

7、：ARQ（自动请求重发(Automatic Repeat reQuest)）frame iACK iframe I+1ACKi+1frame i+2frame i+2ACK i+2frame i+3ACK i+3frame i+3ACK i+3发送方发送方接收方接收方超时超时超时超时帧丢失帧丢失 重发重发ACK丢失丢失 重发，重发，丢失重复帧丢失重复帧协议的效率评价： 定量分析（吞吐量分析：单位时间内成功发送的数据量） 模型建立： 忽略处理时间tpr和确认帧发送时间ta，则有， 在连续发送情况下，若不发生错误，成功传送一幀需要的时间为， poutfTtttttf2若应答幀不出错，发送幀丢失和出

8、错的概率为p，重发次数不限，则有正确传送一幀需要的平均时间为， 11)1 (iTTiTavpttippttpouttt2prpaprpouttttttt 重传时间 （数据帧发送完毕后若经过这样长的时间没有收到确认帧就重传这一帧）故链路最大吞吐量为，Tavtpt11max设发端幀到达率为，则应有， maxTtp1定义归一化吞吐量， = 11)1 (maxPttpttTfff这里， 为归一化时间,显然， 1 fTttARQ评价：简单易行 通信信道的利用率不高改进：连续ARQ, 选择重传ARQ连续ARQ协议 基本原理 在发送完一个数据帧后，不是象ARQ中那样等待应答帧后再发，而是可以连续发送若干个数

9、据帧（见下页图） 但接收端口只按顺序接收数据帧，一旦中间有一个帧出错，则在其后发送的帧要全部重发。 问题：等待时间和重传时间的权衡，在未收到应答时，一次连续发送多少数据帧为好： 开窗口的宽度：滑动窗口协议 （特殊：ARQ=1,等待多，重传少) 一般情况下，窗口宽度与信道的关系： 如果信道的延迟大，则等待时间长，多开窗为宜 如果信道的噪声大，则易出错，易导致重传，少开窗为宜连续ARQ协议的工作原理 连续ARQ又称为 GO-BACK-N ARQ，意思是当出现差错必须重传时，要向回走N个帧，然后再开始重传。数据帧出错数据帧丢失设误幀率为p，则有，1)1(iTifavtipPttpptf1)1(1 这

10、里fTtt连续ARQ吞吐量分析故最大吞吐量为，)1(111maxptptfav归一化吞吐量：pptf) 1(11可见，当等于1时，停止等待ARQ与连续ARQ性能相同。结论：对于远程传输， ，连续ARQ具有明显的优越性。也就是说信道的延迟大，连续ARQ比ARQ效率要高。 fTtt滑动窗口概念滑动窗口概念 前提：在连续前提：在连续ARQ协议中，必须对可以连续发出的最多帧数协议中，必须对可以连续发出的最多帧数（已已发出但未确认的帧）作限制发出但未确认的帧）作限制 原则：循环重复使用有限的帧序号原则：循环重复使用有限的帧序号 流量控制：流量控制： 发送窗口：其大小发送窗口：其大小WT表示在收到对方确认

11、的信息之前，可表示在收到对方确认的信息之前，可以连续发出的最多数据帧数（只有序号在窗口内的帧才可以以连续发出的最多数据帧数（只有序号在窗口内的帧才可以发送）发送） 接收窗口：其大小接收窗口：其大小WR可以连续接收的最多数据帧数（只有可以连续接收的最多数据帧数（只有序号在窗口内的帧才可以接收，否则丢弃）序号在窗口内的帧才可以接收，否则丢弃） 接收窗口驱动发送窗口的转动接收窗口驱动发送窗口的转动发送窗口的最值：发送窗口的最值：n个比特编号，接收窗口大小为个比特编号，接收窗口大小为1时，时， 发送窗口发送窗口WT最大最大2n - 1 WT = 5WR = 1发出帧发出帧0, 100001111422

12、223333444555566667777HHHHHHTT发出帧发出帧2，接收到接收到ACK0滑动窗口示例滑动窗口示例接收到帧接收到帧0，发出发出ACK0初始状态初始状态0011223344556677T初始状态初始状态TTT接收到帧接收到帧1发出发出ACK1WT = 5WR = 10011223344556677H发出帧发出帧3, 4滑动窗口示例滑动窗口示例HHHHH01234567012345670123456701234567帧帧1的定时器超时，的定时器超时，重发帧重发帧1接收到接收到ACK1接收到帧接收到帧3,还没有收到帧还没有收到帧2接收到重传接收到重传的帧的帧1接收到帧接收到帧2T

13、TTTTTT滑动窗口协议已成功发出已成功发出的数据帧的数据帧将发出的数据帧将发出的数据帧窗口后沿窗口后沿窗口前沿窗口前沿帧序号帧序号发送方发送方缓冲区缓冲区已正确接收已正确接收的数据帧的数据帧将收到的数据帧将收到的数据帧帧序号帧序号接收方接收方缓冲区缓冲区窗口后沿窗口后沿窗口前沿窗口前沿滑动窗口示例信道利用率和最佳幀长（1）信道利用率 CDU这里， 为有效数据率， 是信道容量。（2）幀长对信道利用率的影响 过长，误幀率高，信道利用率下降； 过短，幀开销大，信道利用率下降。DC（3）最佳幀长计算令幀长为 ，幀头长为 ，用户数据长度为 ，则最大数据率为，flhldl)1(1 )1 (maxptlp

14、lDfdd将 代入上式，得，CllCltdhff)1(1)()1(pllClpDdhd故有，)1(1)()1 (plllPCDUdhd)1(11ppllldhd令 ， 解出 ，即可求出最佳幀长。0dlUdl选择重传ARQ协议 在连续ARQ中，一旦中间有一个帧出错，则在其后接收到的帧全部丢失，要发送端全部重发，为此的改进： 在选择重传ARQ中，接收端把后面接收到的数据帧暂存在接收端的缓存中，等待前面那个出错的数据帧重传后，再接收确认缓存中的数据，减少了重传的数据帧。 上述的ARQ系列主要针对流量控制以便充分利用信道，同时保证数据传输的正确。 那么如何能实现ARQ协议功能（如何在数据单元加上相应的

15、控制信息） 此外，还有一些其他的链路层控制任务：建立、保持和释放连接等高级数据链路控制(HDLC)早期规定在链路上所传送的数据必须由一些规定的字符集组成（如ASCII码），控制信息也只能用其中的几个来描述，这被称为面向字符的协议，缺点： 只对数据部分进行差错控制，可靠性差 依赖于字符集，不易扩展70年代后，出现面向比特的协议 IBM SNA的 SDLC（同步数据链路控制 ） ANSI 的ADDCP（先进的数据通信控制规程） ISO 的HDLC （高级数据链路控制） CCITT的LAP（链路接入规程） X.25采用LAPB（链路接入规程 - 平衡型 ）链路配置 概念： 主站：发送命令帧、负责控制

16、链路 从站（次站）：接收命令帧，向主站发送响应帧，并配合主站 复合站（组合站）：同时具有主站和从站功能。 两种基本配置：(见下页图示) 非平衡配置 点 - 点工作 多点工作 平衡配置 点 - 点工作命令命令(B)响应响应(B)主站主站A从站从站B非平衡配置：点非平衡配置：点-点点命令命令(B/C/D)响应响应(B)响应响应(C)响应响应(D)主站主站A从站从站B从站从站C从站从站D非平衡配置：点非平衡配置：点-多点多点命令命令(A)响应响应(B)响应响应(A)复合站复合站A复合站复合站B平衡配置平衡配置命令命令(B)数据传送方式 对于非平衡配置： 正常响应方式(NRM)： 数据传输由主站发起，

17、从站只能响应主站的轮询 异步响应方式(ARM)： 从站可以主动发送数据，但链路管理由主站负责 对于平衡配置： 异步平衡方式(ABM)： 任一复合站都可以发起数据传输数据传输模式 非平衡式： 正常响应模式（NRM）主 从CCRR 异步响应模式（ARM）RCCR平衡式 异步平衡模式（ABM）CRCRHDLC的帧结构帧是数据链路层协议的数据单元*信息字段的头尾各加上24bit的控制信息， 就构成了完整的一帧FInfoCAFFCS8 位位16 0888校验区间透明传输区间HDLC帧结构F (flaq) ：固定格式- 01111110 - 带来的问题是什么？ 作用 - 帧同步；A (address) ：

18、表示谁的地址？- 因帧类型与应用而异；C (control) ：表示帧的类型、帧的编号、命令与控制信息；I (information) ：网络层数据，编码可以是任意的，长度可变， max 256B;CRC(checksum) ：校验A,C,I字段的数据； G(X)= X16+X12+X5+1 ( CRC-16 )FACFCRCI8bit8n8N168I各字段说明标志字段F：头尾各8位“01111110”标记帧的首尾边界以实现帧同步零比特填充(连续五个1后填0)以实现透明传输(透明传输区间) 地址字段A：非平衡方式，填入从站地址平衡方式，填入响应站地址 控制字段C：标记帧类型，并附加控制信息信息

19、帧：若控制字段的第1比特为0，传送的是数据信息监督帧：若控制字段的第1-2比特为10，传送的是确认等控制信息无编号帧：若控制字段的第1-2比特为11，建立和释放链路的信息等 帧检验序列FCS：采用CRC-CCITT16， G(x) = x16 + x12 + x5 + 1地址字端（A） 响应站地址； 全1为广播地址； 全0为无效地址。 地址端扩充：0 0 1 C帧类型及控制字段的意义：FACFCRCI8bit8n8N168b7b6b5b4b3b2b1b0I帧S帧U帧01 01 1N(S)SMP/FP/FP/FN(R)N(R)MI帧类型：I帧 ：信息帧； N(S) - 发送帧的顺序号； N(R)

20、 -接收帧的顺序号； P/F= Poll / Final ， P=1 - 询问，F=1 - 响应； P与F成对出现；S帧 ：监控帧； S = 2bit，监控功能位； S = 00，RR (receive ready) S = 10, RNR (receive not ready) S = 01, REJ (reject) S = 11, SREJ (select reject)U帧 ：无编号帧； 用于实现数据链路控制功能； 监督帧的类型监督帧的类型 S = 00 RR（Receive Ready）, 准备接收下一帧，准备接收下一帧， 确认确认N(R)-1及以前的各帧及以前的各帧 10 RNR（

21、Receive Not Ready）, 暂停暂停接收下一帧，接收下一帧， 确认确认N(R)-1及以前的各帧及以前的各帧 01 REJ（Reject）, 否认自否认自N(R)开始的帧开始的帧 确认确认N(R)-1及以前的各帧及以前的各帧 11 SREJ (Selective Reject), 只否认只否认N(R)帧帧 确认确认N(R)-1及以前的各帧及以前的各帧连续连续ARQ选择重传选择重传ARQP/F位的意义（询问位的意义（询问/终止）终止）= 0 无意义无意义= 1 非平衡配置非平衡配置 正常响应方式正常响应方式 主站主站 S/I 帧帧 P=1 （命令）（命令） S/I 帧帧 （响应）（响应

22、）I中中F=1，表示最后一个数据帧，表示最后一个数据帧S中中F=1，表示此时没有数据要发送，表示此时没有数据要发送从站从站NRM异步响应方式异步响应方式ARM平衡配置平衡配置 异步平衡方式异步平衡方式 ABM P=1 （询问）（询问）F=1 （回答本站状态）（回答本站状态）命令方命令方响应方响应方3）P/F 在非平衡方式中：轮询/最终BCAAB,CB RR.0.PB I.0 0B I 1 0B I 2 0B I 3 0 FB RR 4C RR 0 PC RR 0 F在平衡式中：问/答B I 2 0B I 3 1B RR2 FB I 0 0 PB I 1 0A I 0 0A I 1 0A I 2 2无编号帧，定义了无编号帧，定义了15种，起