数据与计算机通信07 数据链路控制协议

分类:Data Communication, 发布于:2019-04-16 14:05:26, 更新于:2019-04-28 21:24:24。 评论

为了实现必要的控制功能,在物理接口层之上又增加了一个逻辑层,这个逻辑称为数据链路控制(data link control)或数据链路控制协议(data link control protocol)。在使用数据链路控制协议时,系统之间的传输媒体称为数据链路(data link)。

针对两个直接连接的站点之间的数据通信,列出以下要求与目标:

  • 帧同步:数据以数据块(帧)的形式发送,每个帧的开始和结束必须可以辨别。
  • 流量控制:发送站点发送帧的速度不得超过接收站点接纳这些帧的速度。
  • 差错控制:有传输系统引起的比特差错必须纠正。
  • 寻址:传输涉及的两个站点的身份必须指明。
  • 控制信息和数据在同一链路上:接收器必须从传输的数据中辨认出控制信息。
  • 链路管理:持续不断的数据交换的初始化、维持以及终止等工作,需要站点之间大量的协同和合作,因而需要具有管理这些交换的过程。

7.1 流量控制

流量控制是用于确保发送实体发送的数据不会超出接受实体接收数据能力的一种机制。如果没有流量控制,接收器在处理旧数据时,缓存就有可能被新数据填满,甚至溢出。

  • 传输时间(transmission time):站点将一个帧的所有比特送到媒体上所花费的时间,与帧的长度成正比;
  • 传播时间(propagation time):一个比特经过链路从源点到达终点所花费的时间。

7.1.1 停止等待流量控制 (Stop and Wait)

源实体传输一个帧,目的实体在接收到它之后,返回一个对刚刚接收到的帧的确认(ACK),以表明自己愿意接受下一个帧;源点在发送下一个帧之前必须等待,直至接受到这个确认。

终点可以不发送ACK,从而终止数据流。

把大块的数据切分成小数据块传输(fragmentation):

  • 接收方缓存空间有限
  • 大块数据传输容易发生错误
  • 避免一个站点长时间占用传输媒体

为了研究这个问题,首先定义链路的比特长度 $$B = R \times \dfrac{d}{V}$$ 其中$R$时链路的数据率(bps);$d$为链路的长度(距离,m);$V$为传播速率(m/s)。计算结果$B$为以比特为单位的链路长度,即比特流完全占满整个链路时链路上的比特数量。

在比特长度大于帧长度的情况下,就会导致效率严重低下。如果传输时间取单位1,传播时延可以表示为 $$a = \dfrac{t_{prop}}{t_{frame}} = \dfrac{d/V}{L/R} = \dfrac{B}{L}$$ 其中$L$是一个帧当中的比特数(以比特为单位的帧长度)。

问题:什么情况下stop and wait效率较高?

总传输时间: $$T_F = t_{prop} + t_{frame} + t_{proc} + t_{prop}' + t_{ack} + t_{proc}'$$

在模型分析中,我们可以认为处理的时间非常快,且ACK非常短,传输时间可以忽略,则 $$T_F = t_{prop} + t_{frame} + t_{prop}' = 2t_{prop} + t_{frame}$$

传输利用率: $$U = \dfrac{t_{frame}}{T_f} = \dfrac{t_{frame}}{2t_{prop} + t_{frame}} = \dfrac{1}{1 + 2a}$$

  • $a > 1$时,$B > L$,此时链路没有被完全利用;
  • $a < 1$时,$B < L$,线路也没有得到充分利用。

总体来说,当数据率$R$非常高时,或发送方与接收方之间的距离非常远时,停止等待流量控制的线路利用效率不高。

7.1.2 滑动窗口流量控制 (Sliding-window)

利用率不高的根本问题在于一次只允许发送一个帧。如果一次允许传输多个帧,就可以大大提高传输效率。

在滑动窗口流控协议中,接收端为$W$个帧分配了缓存,发送端在没有收到ACK之前可以发送$W$个帧。为了始终掌握哪些帧已经被确认,每个帧都通过一个序号来标识,接收端通过发送一个确认帧来肯定某个帧已经被接收,并告知下一个期望接收到的帧序号(也隐含地表明了接收端已经准备就绪接收以指明序号为首的后$W$个帧)。

(此处插图7.3)

对于$k$比特长的字段,序号范围为$0$$2^k-1$,并且以$2^k$为模编号,如$3$比特长的帧编号为$0, 1, \dots, 7$

(此处插图7.4)

接收方必须只能接纳紧跟在最后一次确认帧之后的$W$个帧。接收方接收到数据后可以发送两种报文:

  • RR $N$ (received ready):已经接收到$N$号之前的帧,准备接收$N+1 \dots N+W$帧。
  • RNR $N$ (received not ready):无法接受更多的帧,切断数据流。此后的某个时刻必须发送一个正常的确认帧来重新启动滑动窗口。

在双向传输中,可以通过捎带(piggybacking)的技术在数据帧中存放确认序号。可以同时发送数据和控制信号并节省通信容量。如果一个站点有确认但没有需要发送的数据,就会独立发送一个确认帧(RR或RNR)。如果一个站点需要发送数据但没有新的确认,就必须重新发送上一次已经发送过的确认;接收端收到后直接忽略这个确认。

滑动窗口的利用率分析: $$U = \begin{cases} 1, & W \geqslant 2a + 1, \\ \dfrac{W}{2a + 1}, & W < 2a + 1. \end{cases}$$

7.2 差错控制

数据以帧序列的形式发送,到达时的顺序与发送的顺序相同,并且每个传输的帧在被接受之前会遭受到任意的不等量时延。另外,我们还承认可能存在一下两种类型的差错:

  • 帧丢失 帧没有到达另一方。
  • 帧损伤 可辨认的帧到达,但部分比特有差错。

最常用的差错控制技术的基础都由下述的部分或全部技术组成的:

  • 差错检测
  • 肯定确认
  • 超时重传
  • 否认与重传

综合起来,这些机制都称为自动重传请求(automatic repeat request, ARQ),有以下三种ARQ已经成为标准:

  • 停止等待ARQ (stop-and-wait ARQ)
  • 返回$N$ ARQ (go-back-N ARQ)
  • 选择拒绝ARQ (selective-reject ARQ)

7.2.1 停止等待ARQ

源点发送一个数据帧,等待确认(ACK)。在终点的确认返回源点之前,源点不能发送其他的数据帧,也不能删除缓存(保持发送帧的拷贝)。

  • 发送端:帧损伤
    • 尝试纠正,或者丢弃该帧;
    • 发送端超时重传;
  • 接收端:ACK损伤
    • 发送端超时重传;
    • 重传后总共收到两份相同编号的帧:为了解决这个问题,可以交替的将帧编号为0和1,返回ACK0/ACK1来确认希望收到的帧。

注意:ACK $i$ 不是收到了第 $i$ 帧,而是希望收到第 $i$ 帧。

7.2.2 返回$N$ ARQ

如果没有出现差错,使用ACK/RR进行确认。否则,发送拒绝(REJ/Negative-ACK)。终点丢弃这个帧以及后续接收到的帧,直到有差错的帧被正确地接收到。因此,当源点接收到一个REJ后,必须重传有差错的帧以及之后所有已经传输过的帧。

  • 帧损伤:接收到的帧是无效的,接收端丢弃该帧和后续帧。
    • 在合理的时间范围内,发送端继续发送$(i + 1)$;而接收端接收到$(i + 1)$后发现顺序不对,于是发送REJ $i$。发送端必须重传$i$以及之后的所有帧。
    • 当发送端的计时器超时,发送端会发送一个RR,RR数据帧中的P比特被置为1,接收端收到后返回RR来表明自己希望接收到的下一帧。发送端收到回应后重新开始传输。
  • RR损伤:
    • 接收端收到第$i$帧并发送RR $(i + 1)$,但它在传输时丢失。发送端可能会接收到下一个帧的RR,并且可能在$i$的计时器超时前到达。
    • 如果计时器超时,发送端会发送RR指令(如帧损伤第二种情况)。此时发送端还会设置另外一个P比特计时器,如果接收端没有响应RR命令,或者相应被损伤,那么P比特计时器会超时。在这种情况下,发送端会重复流程,重新发送RR指令。重试次数超过最大之后如果RR还是没有获得相应,发送端就会启动复位进程。
  • REJ损伤:如果REJ丢失,情况等同于帧损伤的第二种情况。

7.2.3 选择拒绝ARQ

如果使用选择拒绝ARQ,被重传的只有那些接收到否认或者超时的帧,在这种情况下,否认称为SREJ。

  • 接收端需要维护足够大的缓存
  • 发送端和接收端逻辑更为复杂
    • 发送端能够判断并仅发送失序的帧
    • 接受段能够按照正确的顺序重组帧
  • 用于传播时延长的卫星链路
最大的窗口大小是多少?

以3比特长度为例,如果窗口长度为$2^3 = 8$,一个站点发送了帧0并得到返回的RR 1,于是继续发送8个帧并且得到另一个RR 1。这可能意味着8个帧全部都被接受到,而RR 1是累积确认,因此也可能意味着所有8个帧都被损伤或丢失。

对于返回$N$ ARQ,最大窗口长度设置为$2^{k}-1$即可避免上述问题。

而对于选择拒绝ARQ,由于发送窗口和接收窗口之间出现了重叠部分,最大窗口值必须小于序号范围的一半,最大窗口长度为$2^{k-1}$

7.3 高级数据链路控制 (HDLC)

7.3.1 基本特点

为了满足各种应用的需要,HDLC定义了三种类型的站点、两种链路设置以及三种数据传输运行方式。三种站点类型分别如下:

  • 主站:负责控制链路操作。主站发出的帧称为命令。
  • 从站:在主站的控制下工作。由从站发出的帧称为相应。主站为链路上的每一个从站维护一条独立的逻辑链路。
  • 混合站:混合了主站和从站的特点。

两种链路设置如下:

  • 非平衡设置:由一个主站以及一个或多个从站组成,支持全双工或半双工传输。
  • 平衡设置:由两个混合站组成,支持全双工或半双工传输。

三种数据传送方式如下:

  • 正常响应方式(NRM):用于非平衡设置。主站能够发起到从站的数据传输,而从站只有在接收到主站的命令时才能传输数据。
  • 异步平衡方式(ABM):用于平衡设置。两个混合站都能够发起数据传输,不需要取得对方混合站的许可。
  • 异步响应方式(ARM):用于非平衡设置。在主站没有明确允许的情况下,从站能够发起传输。但主站仍然对线路全权负责,包括初始化、差错恢复以及链路的逻辑断开。

NRM用于多点线路,就是多个终端连接到一台主计算机上,主计算机对每台中断进行轮询并采集数据。NRM有时也用于点对点的链路,特别是当计算机通过链路连接到一台终端或者其他外设时。ABM是这三种方式中使用最广泛的一种,由于没有用于轮询的额外开销,所以它较有效的利用了全双工点对点链路。ARM很少被使用,它应用于从站需要发起传输的某些特殊场合。

7.3.2 帧结构

HDLC使用的是同步传输,所有的传输均为帧形式,且独立的帧格式就能够完全满足各种类型的数据和控制交换。

帧包括多个字段,信息字段前的统称为首部(header),信息字段之后的统称为尾部(trailer):

  • 标志:8bit
  • 地址:8bit可扩展
  • 控制:8/16bit
  • 信息:变长
  • FCS:16/32bit
  • 标志:8bit

帧分为三种:

  • I:信息
  • S:监控(只有S不可以传输数据)
  • U:无编号帧

标志字段与比特填充

标志字段以01111110模式在帧的两端起定界作用,但01111110可能在帧中间出现,因而破坏同步。为了避免这种情况,需要使用一种称为比特填充(bit stuffing)的处理过程:每出现5个1之后发送器就会插入一个附加的0。接收方检测到起始标志后,一旦有5个1的模式出现,就会检查第6个比特。

  • 如果第6个比特是0,那么该比特就会被删除;
  • 如果第6个比特是1,且第7个比特是0,那么这一组合是标志字段;
  • 如果第6、第7比特都是1,那么发送方指明此时应该处于异常终止状态。

使用比特填充后,在帧的数据字段中可以插入任意的比特序列,这种性质称为数据透明性(data transparency)。

地址字段

地址字段表示出了传输或者准备接受这个帧的从站。点对点的链路不需要这个字段,但是为了统一,所有的帧都含有这个字段。八位组地址11111111被解释为所有站点的地址,它让主站能够广播一个帧,使得所有从站都能收到。

控制字段

信息帧(I帧)携带的是向用户(使用HDLC且位于HDLC之上的逻辑层)传输的数据。另外,因使用ARQ机制而在信息帧中还捎带了流量控制和差错控制数据。监控帧(S帧)在未使用捎带技术时提供了ARQ机制。无编号帧(U帧)提供了增补的链路控制功能。

所有的控制字段格式中都包含了一个轮询/结束(P/F)比特。

  • 在命令帧中指P比特,如果设置为1,就是向对等实体请求(轮询)一个响应帧;
  • 在响应帧中指F比特,如果设置为1,就表示发送的这个响应帧是对一个请求命令的回应。

信息字段

只有I帧和某些U帧才具有信息字段。这个字段可以含有任意的比特序列,但必须由整数个八位组组成。信息字段的长度不固定,最大可达系统设置的最大值。

帧检验序列字段

FCS通常使用16bit的CRC-CCITT码。(见6.3节)

7.3.3 运行方式

HDLC的运行方式包括在两个站点之间交换I帧、S帧、U帧。

HDLC的运行涉及三个阶段:首先,双方中有一方要初始化数据链路,使帧能以有序的方式进行交换。初始化之后,双方交换用户数据和控制信息,并且实施流量控制和差错控制。最后,双方中由乙方要发出信号来终止运行。

初始化

任何一方都能够通过6个置位方式命令之一请求初始化。此命令有以下三个目的:

  1. 通知对方请求初始化;
  2. 指出请求的是哪种方式(三种之一);
  3. 指出使用的是3bit还是7bit的序号。

如果另一方接收这个请求,那么它的HDLC模块向发起方返回一个无编号确认(UA)帧。如果这个请求被拒绝,那么它发送一个拆链方式(DM)帧。

数据传送

当初始化被请求并被接受后,就会建立起一个逻辑连接。双方都可以通过I帧开始发送用户数据,帧的序号从0开始。S帧也可以用于流量控制和差错控制。

拆链

连接中的任何一方的HDLC模块都可以启动拆链操作,可能是由于模块本身因为某种错误而引起的中断,也可能是高层用户的请求。HDLC通过发送一个拆链(DISC)帧宣布连接终止。对方必须用一个UA帧回答,表示接受拆链,并通知其第三层用户该连接已经终止。所有未被确认的I帧都可能丢失,而这些帧的恢复工作则由高层负责。

评论