硕士《计算机网络》(第三章-LLC)

《硕士《计算机网络》(第三章-LLC)》由会员分享，可在线阅读，更多相关《硕士《计算机网络》(第三章-LLC)（44页珍藏版）》请在金锄头文库上搜索。

1、第三章：数据链路层 一、设计问题 二、差错检验和校正：纠错、检错 三、基本数据链路协议：单工、单工停等、有噪单工 四、滑动窗口协议：1位滑窗、后退n幀、选择性重传 五、协议描述和验证：有限状态机、Petri网模型 六、数据链路层示例：HDLC、因特网中的数据链路层 1 硕士生计算机通信网络课程 第三章 数据链路层（LLC） 本章主要研究：两个通信实体的数据链路层之间如何进行可靠、有效的通信。 一、数据链路层设计问题 数据链路层（LLC层）的任务：将物理层提供的原始位流转换成 可供网络层使用的帧流。 要完成的功能： 【1】为网络层提供服务接口 【2】将物理层的比特组成幀（成幀技术） 【3】处理传

2、输差错 【4】调整幀的流速 1。数据链路层为网络层提供的服务 三种基本服务： 【1】无确认的无连接服务 【2】有确认的无连接服务 【3】有确认的面向连接服务 2 P132 图3-1 （a）虚拟通信过程 （b）实际通信过程 P133 图3-2 数据链路协议的作用 2。成幀 四种成幀方法: 【1】 字符计数法：在幀头部使用一个字段标明幀内字符数 【2】含字节填充的分界符法：每一幀以ASCII字符序列DTE STX开头，以DTE STX结束 【3】带位填充的首尾标志法 - “0” 比特插入、删除技术 【4】物理层编码违例法（采取冗余技术） 3。差错控制 协议要求接收方发回特殊的控制幀，作为对接收信息

3、的肯定 或否定的确认 4。流量控制 限制发送方发出数据的数量：协议规则描述了发送方什么时候 发送下一幀，在未获得接收方直接或间接允许之前，禁止发送 幀（第四章有其它流控方法） 3 4 5 二、差错控制和校正 电话系统有三部分：交换机（已数字化，极少出错） 局间干线（已数字化，极少出错） 本地回路（模拟铜双绞线，差错较多） 1。纠错码 两种基本编码策略： 【1】纠错码：在数据块上附加足够的冗余信息，使接收方 可以推测出出错字符 【2】检错码：在数据块上附加冗余位，接收方可检测到出 错，然后要求重发 例：加入奇偶校验位的奇偶位编码（P138） 2。检错码 循环冗余校验码（多项式码，CRC码） P1

4、66 图37 多项式代码校验和的计算 三、基本数据链路协议 【1】模拟程序用TC写成，可到 www.cs.vu.nl/ast/ 中去找 【2】数据链路层和网络层为各自独立的进程，它们通过来回传送消息 进行通信 运行方式： 6 7 【1】物理层、数据链路层在一个处理器内的I/O芯片中 （网卡）运行，网络层在CPU中（主机）运行 【2】可以是单个I/O芯片上同时有三个进程（三个进程分 别属于物理层、数据链路层、网络层） 【3】或者物理层和数据链路层作为过程，为网络层调用 。 一个frame由4个字段组成： kind（类型） seq（序号） ack（确认） info（信息） P169 图39 基本数

5、据链路协议的共同声明（类似C语言） 相当于C程序中的头文件 文件中定义了5种数据结构 8 9 基本数据链路控制协议： 【1】一种无限制的单工协议 【2】一个单工的停等协议 【3】有噪声信道的单工协议 一些假定： 【1】物理层、数据链路层、网络层是各自独立的进程，它们通 过来回传送信息进行通信； 【2】机器A希望用可靠的，可用面向连接的服务方式向机器B发 送一个长的数据流； 【3】机器A准备发送的数据是无限的，不必等待数据产生； 【4】数据链路层接收网络层的一个分组，加上数据链路的帧头 和帧尾，包装成一帧发送 to-physical-layer：发送帧 from-physical-layer：接

6、收帧 wait-for-event（ Seq_nr: 小整数，帧编号0MAX_SEQ; packet：信息交换单位（网络层）; frame： 信息交换单位（数据链路层） 一个frame由四个字段组成：kind，seq，ack，info kind，seq，ack 包含在控制信息，帧头中； Info字段包含一个分组，传输的是用户数据; kind：识别是否有数据，区别控制帧和数据帧； Seq，ack：序号和确认； 1。一种无限制的单工协议（协议1） 一种不现实的理想协议，也称为“乌托邦” （utopia）协议。 假定： 数据只做单向传输； 传送和接收方的网络层一直处于就绪状态； 处理时间忽略不计，缓

7、冲空间无限大； 数据链路层信道中不存在丢失帧和损坏帧的情况。 P171 图310 11 12 2。一个单工的停等协议（协议2） 发送方发送完后，等对方的一个短回答幀到达后，才 可传下一幀（保证传输的正确性） 如何防止发送过快，使接收过程来不及处理： 如果接收过程需要t的时间来执行from-physical-layer和to- network-layer，则发送过程必须以低于每t时间一帧的 平均速率进行传输； 或者说：如果在接收方的硬件中没有自动的缓冲和排队功能， 那么发送方只有当前一个帧被from-physical-layer取走后才 能传输新的帧，否则新的帧就会把前一个帧覆盖； 要求接收方向

8、发送方提供反馈： 当接收方把一个分组传给本地的网络层后，向发送方返回一个 短帧（确认帧），允许发送方发送下一帧； 发送方在发送完一帧之后，要求等待一段时间，直到该短帧 （确认帧）到达。 P173 图311 一个单工停等协议 13 14 3。有噪声信道的单工协议 有噪声信道：传输过程中可能出错，然后重传 单工协议：只能单向传送（这里是半双工？） 在传输过程中，帧可能被损坏，也可能完全丢失; 初步想法可以加一个计时器。 有无确认帧丢失，重复分组的可能性? 让发送过程在每个待发的帧的头部放一个序号; 序号的取值： 0，1？ 唯一混淆之处是帧的直接前趋和直接后继之间，而不是前 趋和后继之间； 在某一时

9、刻，接收方期待下一个特定的序列号，任何包含 错误的序列号到达帧被作为重复帧而遭到拒绝； 当包含正确序号的帧到达后，就被接收，传给网络层，并 且期待的序列号为当时的序号加1（模2加）； 15 发送超时、过早的情况： 发送方发出一个帧，接收方收到后，发出确认帧； 如确认帧还未到达，发送方已超时； 发送方超时，重发； 发送方确认帧到达，发送下一帧； 发送方又一确认帧到达，再发下一帧； 此时，若刚发送的上一帧丢失； 协议失败。 P176 图312 一个支持重传的肯定、确认协议 * 1。该协议也是单向传送数据 2。发送方送出一帧，启动定时器，等待下述事件发生： （1）一个确认帧正确到达；从网络层取出下一

10、帧，准备发送； （2）一个受损的确认帧到达：重发上一帧； （3）定时器超时、无确认帧到达：重发上一帧。 3。有效帧到达接收方：检查其序列号，若不是重复分组，接受 之传递给网络层生成一个确认。 16 17 四、滑动窗口协议、选择性重传协议 1。滑动窗口协议 主要解决在一个信道上双向传送数据的问题 一种可获得双工数据传输的方法： 使用两条独立的信道，每一 个信道分别用作单工数据传输（传输方向不同），但这样 做反向的带宽基本浪费（用于确认） 一种改进：使用同一条线路进行数据的双向传输。在这种模式 下：从 AB的数据帧和从 B-A的确认帧混在一起， 必须查看到达帧头部分的kind字段加以判断是数据帧还

11、是 确认帧。 另一种改进：当一个数据帧到达后，接收过程不是立即发送一个 独立的控制帧，而是维持等待，直到其网络层想起发送下 一个分组，“确认”被附加到即将发送的数据帧上，这种技 术称为“捎带技术”。. 捎带技术可以有效利用信道的带宽 捎带技术也带来了单独确认帧所没有的复杂性。即数据链路层 等待多长时间才能把捎带确认帧发出去？如果等待时间过 18 长，造成发送方计时器超时，也就违背了确认的意义。 可采用等待一个固定的毫秒数，在这个时间范围内，新 的分组到来则采用捎带技术，否则以单独分组的形式发出确认帧。 滑动窗口协议的关键在于：任何时刻发送过程都保持着一组序列 号，对应于允许发送的帧。这些帧称作

12、在发送窗口 （sending window）之内。相类似的，接收过程也维持一 个接收窗口（receive window），对应于一组允许接收的 帧。 这一节所介绍的三个协议（1位滑窗，回退n帧，选择性重传）都 属于滑动窗口协议，区别在于效率、复杂性及对缓冲区 的需求不同 发送窗口中的序号表示：已发送了的、但尚未得到确认的帧。 窗口宽度：分别代表可以发送或接收的帧的数目。 在发送窗口内的当前帧最终有可能在传输中丢失或损失，所以发 送过程必须把所有的这些帧保存在内存中，以备重传。 如果最大的窗口大小为n时，发送过程需要n个缓冲区来保存未确 19 认的帧。如果一旦窗口达到最大帧，发送过程的数据链 路

13、层必须强制关闭网络层，直到有一个缓冲区空出来为 止。 滑动窗口协议（发送方） 60 1 2 3 4 5 6770 1 2 3 4 5 Frames may be transmitted Frames already transmitted Last Frame Transmitted 虚线框内为要 发送帧的序列 号 箭尾向右为将要 被确认的帧序列 号 Frame Sequence Number Frame Sequence Number 60 1 2 3 4 5 6770 1 2 3 4 5 20 滑动窗口协议（接收方） 60 1 2 3 4 5 6770 1 2 3 4 5 Frames m

14、ay be received Frames already received Last Frame acknowledged 虚线框内为将被 接收帧的序列号 箭头向右为将被 确认的帧序列号 Frame Sequence Number Frame Sequence Number 21 滑动窗口举例 22 23 一个一位滑动窗口协议 分析非正常情况：A-B 发送0号帧 B-A 发送0号帧 假定A向B发送了一帧，但是A的超时时间过短，A也许重复地超时 重发，发送一系列同样的帧，都是seq=0，ack=1；当有一 个有效的帧到达B时，此帧就被接收了，frame- expected=1，这样所有的重传帧

15、都会被拒绝，而且由于所 有的重发帧ack=1，而B仍然在等待帧0的确认，B就不能从 网络层取得一个新的分组。每一个被拒绝的帧到达后，B 都向A发送一个包含seq=0的帧。其中有一帧到达A后使A 开始发送一个分组，丢失帧的任何情况不会造成协议失 败。 24 一个1位滑动窗口协议 正常双方同时发送的情况 (seq, ack, packet number) 非双方同时发送 包的情况 25 数据链路层的错误处理： 错误情况：在发送的帧流中的一帧丢失或损坏 要求：数据链路层按次序把分组交给网络层 错误处理方法有两种： 退后n帧（go back n ） 选择性重传（selective repeat）: 2。使用后退n幀的协议（管道化技术） 以前的协议中,都假设帧的传输时间和确认帧的回传时间 忽略不计； 但实际上这种假设是不可能的，实际过长的往返时间会大 大的影响信道利用率。 信道利用率低的原因： 发送方必须等待确认 如果放开这个限制，连续发送多帧，在发完这些帧之后， 响应帧正好返回，这样大大的提高了信道利用 率。这一技术被称作管道化（pipelining） 26 特点：