第5章数据链连接

1、计算机网络第第5 5章章 数据链连接数据链连接 第第5章章 数据链连接数据链连接 5.1 链路配置和控制链路配置和控制5.2 流量控制流量控制 5.3 差错控制差错控制5.4 HDLC协议协议计算机网络第第5 5章章 数据链连接数据链连接5.1 链路配置和控制链路配置和控制 由两个直接相连的站组成的数据链路叫点对点链路。 如果一条线路上连接了两个以上的站则叫多点链路。 计算机和多个终端通信, 可以连接成点对点链路, 也可以连接成多点链路, 如图5.1所示。 在多点链路配置中, 各个终端分时地使用通信线路向计算机发送数据或从计算机接收数据, 从而节省了硬件费用。 计算机网络第第5 5章章 数据链

2、连接数据链连接图 5.1 点对点链路和多点链路 (a) 点对点链路; (b) 多点链路 计算机网络第第5 5章章 数据链连接数据链连接 图 5.2画出了询问过程的时序关系。 主站首先发出一个简短的询问消息(Poll), 次站如果没有数据要发送, 则以否定应答(NAK)来响应(图 5.2(a)。 整个过程需要的时间为: 图中的t1-t0=t5-t4为传播延迟 t2-t1为发送询问消息的时间； t3-t2为次站处理询问消息的时间 t4-t3为发送否定应答的时间。50NTtt计算机网络第第5 5章章 数据链连接数据链连接 如果次站在收到询问消息时正好有数据要发送, 可立即发送数据, 主站接收完数据并

3、校验正确后给予肯定应答(图 5.2(b)。 显然这个过程所用的时间TD比前一个过程增加了传送和校验数据的时间。 如果主站轮流对每个次站询问一遍, 有的次站发送了数据, 有的次站没有发送数据, 则轮询周期为TC: TC=nTN+kTD 这个式子表示共有n个次站, 其中k个次站和主站发生了数据交换。计算机网络第第5 5章章 数据链连接数据链连接 图 5.2 询问时序 (a) 次站不发送数据 (b) 次站发送数据 计算机网络第第5 5章章 数据链连接数据链连接 一种更为灵活的轮询办法是给予各个次站不同的优先级, 在每个轮询周期中对优先级高的次站多询问几次, 这样可以应付各个次站的处理速度或重要性不同

4、的复杂情况。 图5.3画出了选择过程的时序关系。 从图中可以看出, 数据传送过程由四个阶段组成: T1为主站发送选择信号(SEL)和次站处理选择信号的时间 T2为次站发送应答信号和主站处理应答信号的时间 T3为主站发送数据和次站接收校验的时间 T4为次站把对数据的应答发送回主站的时间。 计算机网络第第5 5章章 数据链连接数据链连接 图 5.3 选择时序 计算机网络第第5 5章章 数据链连接数据链连接 图 5.4 快速选择时序 计算机网络第第5 5章章 数据链连接数据链连接5.2 流量控制流量控制 5.2.1 停等协议 由于传输延迟的影响, 应用停等协议进行流控时, 在某些情况下线路带宽的利用

5、率不会很高, 许多时间都用在等待应答信号上了。 下面对停等协议的效率进行分析。 假设在半双工的点对点链路上, 站S1向站S2发送n个数据帧, S1每发出一个帧就等待S2送回的应答信号。 设一个帧从S1到达S2的时间为 计算机网络第第5 5章章 数据链连接数据链连接 TF=tp+tf 其中, tp为传播延迟, tf为发送一帧的时间(称一帧时)。 另外应答信号(ACK)从S2到达S1要经过一个传播延迟时间tp。 由于应答信号很短, 发送应答信号的时间可以忽略, 所以完成一帧传输和应答的时间间隔为 TFA=TF+TA=(tp+tf)+tp=2tp+tf 按照图5.5, 传送完全部n帧的时间为 TD=

6、nTFA=n(2tp+tf) 其中实际用于数据帧传输的时间为ntf, 于是线路的利用率为计算机网络第第5 5章章 数据链连接数据链连接(2)2121ffpfpfnttEnttttEa定义a=tp/tf, 则 (5.1) (5.2) 计算机网络第第5 5章章 数据链连接数据链连接 图 5.5 停等协议的效率 计算机网络第第5 5章章 数据链连接数据链连接 对a进行一些分析。 由于a是线路传播延迟和一帧时的比, 故在线路长度一定和帧长固定的情况下a是常数, 这是链路上传送数据帧的典型情况。 又由于线路传播延迟是线路长度d和信号传播速度v的比, 而一帧时是帧长L和数据速率R的比, 因而有/d vRd

7、 vaL RL(5.3) 计算机网络第第5 5章章 数据链连接数据链连接 (5.3)式的分子Rd/v的单位为比特, 其物理意义是线路上能容纳的最大比特数, 亦即线路的比特长度, 它是由线路的物理特性决定的。 因而a可理解为线路比特长和帧长的比, 或者说按帧计数的线路长度。 进一步说明参数a对协议效率的影响。 通常卫星信道的传播延迟是270 ms, 数据速率是64 kb/s, 帧长是4 000 bit。 因而对于卫星链路可得: a=64270/4 000=4.321 根据(5.2)式, 卫星链路的利用率为 1110.1042124.3219.64Ea计算机网络第第5 5章章 数据链连接数据链连接

8、 最后我们考查一下利用Modem在话音信道上进行数据传输的情况, 话音信道典型的数据速率R是9 600 b/s, 仍然取v=2108 m/s, L=500 bit。 如果传输距离d是100 m, 则689600 1009.6 1012 10500a计算机网络第第5 5章章 数据链连接数据链连接 5.2.2 滑动窗口协议 简单停等协议的主要问题是链路上只有一个帧在传送, 当链路的帧计数长度a 大于1时, 许多线路带宽都浪费了。 下面讨论的滑动窗口协议可以克服这个缺点。 滑动窗口协议的主要思想是允许连续发送多个帧而无需等待应答。 图5.6可以形象地说明滑动窗口的机理。 这里, 我们假定帧编号字段为

9、3位, 帧编号取值范围为07, 窗口最大为W=7。 计算机网络第第5 5章章 数据链连接数据链连接 图 5.6 滑动窗口的表示 (a) 发送器窗口 (b) 接收器窗口 计算机网络第第5 5章章 数据链连接数据链连接 考虑(5.2)式我们立即会得到线路的利用率 图 5.8画出了在不同窗口尺寸下线路利用率和a值的函数关系。 W=1相当于上一小节的停等协议, W=7适用于局域网和电信网络的情况, W=127可用于卫星信道。 21WEa(5.4) 计算机网络第第5 5章章 数据链连接数据链连接图 5.7 滑动窗口协议的时间关系 (a) W2a+1 (b) W2a+1 计算机网络第第5 5章章 数据链连

10、接数据链连接图 5.8 协议效率和窗口尺寸的关系 计算机网络第第5 5章章 数据链连接数据链连接5.3 差错控制差错控制 通常应付传输差错的办法如下:(1) 肯定应答。 (2) 否定应答重发。 (3) 超时重发。 可以有三种形式的ARQ技术:(1) 停等ARQ(2) 后退N帧ARQ(3) 选择性ARQ。 计算机网络第第5 5章章 数据链连接数据链连接 5.3.1 自动请求重发(ARQ)技术 1. 停等ARQ协议 停等ARQ是停等流控技术和自动请求重发技术的结合。 根据停等ARQ协议, 发送站发出一个帧后必须等待应答信号, 收到肯定应答信号ACK后继续发下一个帧 收到否定应答信号NAK后重发该帧

11、 在一定的时间间隔内没有收到应答信号也必须重传该帧。 计算机网络第第5 5章章 数据链连接数据链连接 图 5.9 停等ARQ协议 计算机网络第第5 5章章 数据链连接数据链连接 2. 后退N帧ARQ协议 我们可以设想用下面的方案实现后退N帧ARQ协议: (1) 发送站按照窗口中的帧编号顺序地连续发送帧。 (2) 接收站的窗口大小为1。 (3) 如果发送站收到关于其窗口中的某个帧的否定应答信号, 无论当时已发送到哪个帧, 都退回到出错帧重发该帧及其后续帧。 (4) 如果发送站发出的某个帧丢失了, 或是应答信号(ACK或NAK)丢失了, 则发送站的计时器会发现这种情况, 这时也要后退N帧重发。 计

12、算机网络第第5 5章章 数据链连接数据链连接 若考虑这种积累作用, 则以上的方案还需要进一步补充如下: (1) 在第1步中发送器的窗口可能一次向前推进几个格子。 (2) 在第 4步中发送器的定时器定时必须长一些, 使得在2a+1个帧时内虽然没有收到肯定应答信号, 但是还可以考虑后边来到应答信号, 不要过早地就认为某个帧丢失了而后退重发。 计算机网络第第5 5章章 数据链连接数据链连接 (3) 再一次强调在全双工双向通信中, 应答信号可以由反方向传送的数据帧“捎带”送回, 这种机制进一步减小了通信开销, 然而也带来了一定的问题。 计算机网络第第5 5章章 数据链连接数据链连接 3. 选择性ARQ

13、协议 图 5.10画出了两种连续ARQ协议的例, 图 5.10(a)是在全双工线路上应用后退N帧ARQ协议时帧的流动情况。 其中第 2帧出错, 随后的3, 4, 5帧被丢弃。 计算机网络第第5 5章章 数据链连接数据链连接 图 5.10 连续ARQ协议的例 (a) 后退N帧ARQ协议 (b) 选择性ARQ协议 计算机网络第第5 5章章 数据链连接数据链连接 若假设帧编号为3位, 发送和接收窗口大小都是7, 考虑下面的情况: (1) 发送窗口和接收窗口中的帧编号都是 0 到 6 (2) 发送站发出0到6号帧, 但尚未得到肯定应答, 窗口不能向前滑动 (3) 接收站正确地收到了0至6号帧, 发出了

14、肯定应答ACK7(注意, 这个应答信号表示0至6号帧已收到, 下面期望收到7号及其以后的帧), 因而接收窗口向前滑动, 新的窗口中的帧编号为7, 0, 1, 2, 3, 4, 5计算机网络第第5 5章章 数据链连接数据链连接 (4) ACK7丢失, 发送站定时器超时, 重发0号帧 (5) 接收站收到0号帧同并看到该帧编号落在接收窗口内, 以为是新的0号帧而保存起来。 认为7号帧丢失了(其实发送站从未发出过), 并继续接收重复发来的1, 2, 3, 4, 5, 号帧。 计算机网络第第5 5章章 数据链连接数据链连接 5.3.2 协议性能分析 回忆(5.1)式, 当没有错误时, 停等协议的效率为

15、因而上式的分母乘以传输的次数就得到停等ARQ协议的效率。 类似于(5.2)式, 我们有2fpftEtt1(21)rENa(5.5) 计算机网络第第5 5章章 数据链连接数据链连接 其中, Nr表示一个帧重传的次数, 为了对Nr给出一个数量的表示, 我们假设帧出错的概率为P。 为简单计, 我们再假设应答信号(ACK和NAK)不会出错, 则经过i次尝试才能成功地传送一帧的概率为Pi-1(1-P)。 于是有 111(1)1iriNiPPP(5.6) 因而(5.5)式变为121PEa(5.7) 计算机网络第第5 5章章 数据链连接数据链连接 如果假定一个帧选择性地重传Nr次, 我们得到选择性ARQ协议

16、的最大效率为12121(21)rrWaNEWWaNa(5.8) 以(5.6)式代入得121(1)2121PWaEWPWaa(5.9) (5.10) 计算机网络第第5 5章章 数据链连接数据链连接 下面推导后退N帧ARQ协议的协率。 在这种协议下, 当纠正一个出错(或丢失)帧时要重传N帧, 而且可能要纠正多次才能成功, 因而有11( )(1)iriNf t PP(5.11) 其中的f(i)为第i次纠错重传时传输的帧数, 有( )1(1)(1)if iiNNN 计算机网络第第5 5章章 数据链连接数据链连接 这个式子表示若第i次重传成功, 则传输的总帧数为最先传输的一帧加上以后每次后退重传的N帧。

17、 把f(i)代入(5.11), 得1111112(1)(1)(1)(1)(1)11(1)(1)(1)1(1)1111iriiiiiNPNNi PPNPP NiPPNP NPPNPNPNPP 计算机网络第第5 5章章 数据链连接数据链连接 把Nr的值代入(5.8)式, 得到后退N帧ARQ的协议的最大效率为1211121211PWaPNPEWPWaaPNP 若考虑到当W2a+1时, N近似等于2a+1, 则有12112PEWaaP(5.12) 当W2a+1时, N=W, 故有(1)21(21)(1)WPEWaaPWP(5.13) 计算机网络第第5 5章章 数据链连接数据链连接5.4 HDLC协议协

18、议 5.4.1 HDLC的概念 三种类型的站是: (1) 主站: 对链路进行控制, 主站发出的帧叫命令。 (2) 从站: 在主站控制下进行操作, 从站发出的帧叫响应。 主站为线路上的每个从站维持一条逻辑链路。 (3) 复合站: 具有主站和从站的双重功能。 计算机网络第第5 5章章 数据链连接数据链连接两种链路配置是:(1) 不平衡配置: 适用于点对点和多点线路。 (2) 平衡配置: 仅用于点对点线路。 计算机网络第第5 5章章 数据链连接数据链连接 三种数据传输方式是: (1) 正常响应方式(NRM): 适用于不平衡配置, 只有主站能启动数据传输, 从站仅当收到主站的询问命令时才能发送数据。

19、(2) 异步平衡方式(ABM): 适用于平衡配置, 任何一个复合站都无需取得另一个复合站的允许就可启动数据传输。 (3) 异步响应方式(ARM): 适用于不平衡配置, 从站无需取得主站的明确指示就可以启动数据传输, 主站的责任只是对线路进行管理。计算机网络第第5 5章章 数据链连接数据链连接 5.4.2 HDLC帧结构 HDLC用具有统一结构的帧进行同步传输, 图5.11画出了HDLC的帧结构。 由图可以看出, HDLC帧由6个域组成。 以两端的标志域(F)作为帧的边界, 在信息域(INFO)前面的三个域(F, A, C)叫做帧头, 信息域后面的两个域(FCS和F)叫做帧尾, 信息域中包含了要

20、传输的数据。 下面对HDLC帧的各个域分别予以解释。 计算机网络第第5 5章章 数据链连接数据链连接 图 5.11 HDLC帧结构 计算机网络第第5 5章章 数据链连接数据链连接 1. 标志域F HDLC用一种特殊的位模式01111110作为标志以确定帧的边界。 同一个标志既可以作为前一帧的结束, 也可以作为后一帧的开始。 链路上所有的站都在不断地探索标志模式, 一旦得到一个标志就开始接收帧。 在接收帧的过程中如果发现一个标志, 则认为该帧结束了。 计算机网络第第5 5章章 数据链连接数据链连接 2. 地址域A 地址域用于标识从站的地址。 虽然在点对点链路中不需要地址, 但是为了帧格式的统一,

21、 也保留了地址域。 地址通常是8位长, 然而经过协商之后, 也可以采用更长的扩展地址。 扩展的地址域表示在图 5.12中, 可以看出它是8位组的整数倍。 计算机网络第第5 5章章 数据链连接数据链连接图 5.12 HDLC扩展地址域 计算机网络第第5 5章章 数据链连接数据链连接 3. 控制域C HDLC定义了三种帧, 可根据控制域的格式区分之。 信息帧(I帧)装载着要传送的数据, 此外还捎带着流量控制和差错控制的信号。 管理帧(S帧)用于提供实现ARQ的控制信息, 当不使用捎带机制时用管理帧控制传输过程。 无编号帧提供各种链路控制功能。 控制域第1位或前两位用于区别三种不同格式的帧, 如图5

22、.13所示。 计算机网络第第5 5章章 数据链连接数据链连接 图 5.13 控制域格式 (a) 基本控制域 (b) 扩展控制域 计算机网络第第5 5章章 数据链连接数据链连接 4. 信息域INFO 只有I帧和某些无编号帧含有信息域。 这个域可含有表示用户数据的任何比特序列, 其长度没有规定, 但具体的实现往往限定了帧的最大长度。 5. 帧校验和域FCS FCS域中含有除标志域之外的所有其他域的校验序列。 通常使用16 bit的CRC-CCITT标准产生校验序列, 有时也使用CRC-32产生32位的校验序列。计算机网络第第5 5章章 数据链连接数据链连接 5.4.3 HDLC帧类型 1. 信息帧(I帧) 信息帧除承载用户数据之外还包含有该帧的编号N(S), 以及捎带的肯定应答信号N(R)。 肯定应答信号其实就是期望接收的下一个帧的编号。 2. 管理帧 管理帧用于进行流量和差错控制, 当没有足够多的信息帧捎带管理命令/响应时, 要发送专门的管理帧来实现控制。 由表 5-1看出, 有4