计算机网络原理-第3章.ppt

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