第3章数据链路层 链路和数据链路意义不同,前者是指一条无源的点对点的物理线路段,中间没有任何 其他的交换节点,有时也称为“物理链路”。 在一条线路上传送数据时,除了必须有一条物理线路外,还必须有一些必要的规程控 制这些数据的传输。将实现这些规程的硬件和软件加到链路上,就构成了数据链路。当 采用复用技术时,一条链路上可以有多条数据链路。 数据链路层位于第2层,其传输原理如图3-1所示。主机A的数据从应用层出发,向 下到数据链路层,以帧的方式发送到下一个节点(路由器1), 再经过路由器2和路由器3 两个节点,达到目的主机B,期间将经过局域网和广域网等不同的网络,主机A和主机B 连接到网络可能采用电话网或局域网等接入方式。当然,从实际传输上看,是经过物理层 由通信线路到达邻近节点的。 图3-1 数据链路层传输原理示意 3.数据链路层的功能 1 3.1 为网络层提供服务 1. 数据链路层的基本任务是将源机器中来自网络层的数据传输到目的机器的网络层, 所提供的基本服务有以下三种。 (1)无确认的无连接服务。不需要建立链路连接,每个帧上都携带目的地址,形成独 50 立的帧。接收方对收到的帧不进行确认。如果由于线路噪声而造成帧丢失,数据链路层 不负责重发,留待上层完成。因此,其主要适用于误码率低、实时性要求较高的传输环境, 如局域网。 (2)有确认的无连接服务。这是在上述服务中引入了确认功能。每收到一个帧,接 收方都要发回确认信号。如果发送方在规定的时间内没有收到确认信号,则该帧就需要 重新发送。这类服务适用于可靠性不高的信道,如无线通信系统。 (3)有确认的面向连接服务。具有连接建立、数据传输和连接释放的三个阶段。所 有的帧都有序号,每一帧都有确认信号。大多数广域网的通信子网的数据链路层采用这 种服务。 3.2 组帧 1. 来自网络层的数据加上首部和尾部后,以帧为单位向下传输。这样,在接收端即使在 物理层传输中出现了错误,也只需要将有错的帧重发,而不必将全部数据重新发送,从而 提高了效率。为了明确一个帧的开始和结束,就需要加上一定的标志,实现帧同步或帧定 界,如图3-2所示。图3-2中,MTU 是最大传输单元,是帧的数据部分长度的上限。帧的 长度等于数据部分加上帧首部和帧尾部的长度。 图3-2 帧的结构模型 3.3 差错控制 1. 当一帧到达目的地时,需要校验其正确性。这需要通过差错控制码产生的校验和确 定,首先在发送端计算后连同数据一起发送,在接收端进行检错处理。如果是正确的,则 数据部分向网络层传送;否则进行丢弃处理。 3.4 流量控制 1. 流量控制是解决发送能力大于接收能力的问题,如果接收方来不及接收,则会有许多 帧丢失。流量控制实际上是控制发送方的数据流量,使其发送速率不超过接收方所能处 理的程度。 【例3-1】在数据链路层应根据什么原则确定应当使用面向连接服务还是无连接 服务? 解析:在设计硬件时就能够确定。例如,若采用拨号电路,则数据链路层将使用面向 连接服务;但若使用以太网,则数据链路层使用的是无连接服务。 3.组帧技术 2 组帧技术,也称为帧同步技术。有不同的组帧方式,可以是以字节为单位组成帧的各 部分字段,称为面向字节的组帧方式;也可以是以任意比特组合成帧的,称为面向比特的 组帧方式。下面介绍四种组帧方法。 3.1 字节计数法 2. 这种帧同步方法是一种面向字节的同步规程,是利用帧首部中的一个域指定该帧中 的字节数,其原理如图3-3所示。 图3-3 字节计数法示例 图3-3标识了4个数据帧的帧格式,它们的大小依次为5B 、5B 、8B 、8B 。接收方可以 通过对该特殊字符的识别从比特流中区分出帧的起始,并获知该帧的数据字节数,从而可 以确定帧的终止位置。 这种方法最大的问题在于如果标识帧大小的字段出错,即失去了帧边界划分的依据, 将造成灾难性的后果。如第2帧中的计数字节由5变为7,则接收方就会失去帧同步的 可能,从而不可能再找到下一帧正确的起始位置。由于第2帧的校验和出现了错误,所以 即使接收方给发送方请求重传都无济于事。因此,这种字节计数法目前已很少使用。 3.2 字符填充法 2. 该同步方法是用一些特定的字符作为一个帧的开始和结束标志,同时也采用某些特 定的字符作为传输过程中用到的控制字符。在过去,开始和结束字节并不相同,但在最近 几年,绝大多数协议倾向于使用相同的字节,称为标志字节,如图3-4(a)中的FLAG 所 示。因此,接收方如果丢失了同步,也只需要搜索标志字节就能找到当前帧的结束位置。 两个连续的标志字节代表了当前帧的结束和下一帧的开始。 如果标志字节出现在数据中,则发送方在该字节前插入一个特殊的转义字节(ESC); 接收方在删除该ESC 字节后才将数据送交给网络层,这就是字节填充技术。进一步地, 如果ESC 字节也出现在数据中,则采用同样的处理方式,在其前面插入一个ESC 。在 图3-4(b)中,给出了4种不同的原始字符序列及其填充结果。 这种方法依赖于8位字符模式,对其他类型的字符码并不适用。例如,UNICODE 使 用16 位字符。所以需要开发新的技术,以便允许任意长度的字符。 52 图3-4 字符填充法示例 3.3 零比特填充法 2. 这是以一组特定的比特模式(01111110)标志一帧的开始和结束,它允许任意长度的 位码,也允许每个字符有任意长度的位。在发送方的数据链路层,每当数据中遇到5个连 续的比特1时,会自动在其输出位流中填充一个比特0。在接收方的数据链路层中,每当 数据中收到5个连续的1且其后是0时,会自动删除该0比特。其工作原理如图3-5所 示,如果要传输的数据帧为01101111111101111110010,则采用零比特填充后,在网络中 传送时表示为0110111110111011111010010 。 图3-5 零比特填充法示例 零比特填充帧同步方式很容易由硬件实现,性能优于字符填充方式。所有面向比特 的同步控制协议采用统一的帧格式,不论是数据还是单独的控制信息均以帧为单位传送, 其典型代表是HDLC 协议。 3.4 违例编码法 2. 在物理层采用特定的比特编码方法时采用。例如,曼彻斯特编码方法是将数据比特 0编码成“高-低”电平对,将数据比特1编码成“低-高”电平对,而“高-高”电平对和“低 低”电平对在数据比特中是违例的,可以借用这些违例编码序列界定帧的开始和结束,局 域网IEEE802 标准中就采用了这种方法。违例编码法不需要任何填充技术,便能实现 数据的透明性,但它只适于采用冗余编码的特殊编码环境。 由于字节计数法中计数字段的脆弱性及字符填充实现上的复杂性和不兼容性,目前 较普遍使用的帧同步法是零比特填充法和违例编码法。 【例3-2】数据链路协议中使用了下面的字符编码。 A:01000111;B:11100011;FLAG:01111110;ESC:11100000 为了传输一个包含4个字符的帧:ABESCFLAG,请给出当使用下面的成帧方法 时所对应的位序列(用二进制表达)。 (1)字节计数。 (2)包含字节填充的标志字节。 (3)包含零比特填充的开始和结束标志 。 解析 : (1)有4个字符和1个标识符,二进制表示为00000101 。按照字符计数,这5个字符 应表示为 0000010101000111111000111110000001111110 (2)首尾各加上一个FLAG 标志一帧的开始和结束,再考虑字节填充法,则结果为 FLAGABESCESCESCFLAGFLAG,对应的二进制编码为 0111111001000111111000111110000011100000111000000111111001111110 (3)采用特定的比特模式(01111110)标志一帧的开始和结束,再考虑零比特填充法, 得到结果为 011111100100011111010001111100000001111101001111110 3.差错控制 3 理想的通信系统在现实中是不存在的,信息传输过程中总会出现差错。差错控制是 指采用编码技术,在通信过程中发现并检测差错,或对差错进行纠正,从而将差错控制在 尽可能小的范围内。能检测差错的编码称为检错码,如奇偶校验码、循环冗余校验码以及 校验和;能检测并纠正错误的编码称为纠错码,如汉明码。纠错码的实现过程复杂,在一 般的通信场合不适宜采用;检错码的实现较为容易,能够通过重传机制获得正确的帧,因 此在网络中广泛使用。 3.奇偶校验码 3.1 奇偶校验码是最常见的一种检错码,主要用于以字符为传输单位的通信系统中。其 工作原理很简单,即在原始数据字节的最高位或最低位增加一位,作为奇偶校验位,以保 证所传输的每个字符中1的个数为奇数(奇校验)或偶数(偶校验)。 国际标准规定:在同步传输中使用奇校验,而在异步传输中使用偶校验。 奇偶校验只能检测出奇数个位发生的错误,校验能力低,不适用于块数据的传输,需 要采用垂直水平奇偶校验码(也称为纵横奇偶校验或方阵码), 其工作原理如图3-6所示。 54 图3-6 方阵校验码应用示例 图3-6中有一组由3行7列的数据组成的块,每行的最右位是水平奇偶校验位,每列 的最低位是垂直奇偶校验位。由于增加了纵向的校验,所以其检错能力得到了提高,能够 检测出所有3位或3位以下的错误、奇数个错和大部分偶数个错,可以使误码率下降到原 误码率的百分之一到万分之一。 该方阵码的另一个特点是可以纠正部分差错。如图3-6(b)所示,发现第2行和第 5列的奇偶校验出错,则可以判定当前位置的数据位发生了传输错误,将之取反即可纠正 差错。 3.循环冗余校验码 3.2 循环冗余校验(CyclicRedundancyCheck,CRC)编码是局域网和广域网的数据链路 层通信中使用最多也是最有效的检错方式。其基本思想是在数据后面添加一组与数据相 关的冗余码,冗余码的位数越多,检错能力越强,但传输的额外开销也越大。 CRC 码又称为多项式码,任何一个由二进制数位串组成的代码都可以和一个只含有 0和1两个系数的多项式建立一一对应的关系,例如,代码1011011 对应的多项式为x6+ x4+x3+x+1 。 k 位要发送的信息位可对应于一个k-1次多项式 M ( r 位冗余位对 x), 应于一个r-1次多项式R(x)。由 k 位信息位后面加上 r 位冗余位组成的n=k+ r 位的 编码即为CRC 码,对应于一个n-1次多项式F(x)=xrM (x)..R()。 由信息位产生冗余位的编码过程,就是已知 M (x)求R(x)的过程(x) 。在CRC 码中,可 以通过找到一个特定的 r 次多项式G(x)实现,用G(x)除以xrM (x)得到的余式就是 R(x)。 在接收方,校验的方法是用生成的多项式G(x)除以接收到的xrM (x)..R(x), 若不 能整除,则表明传输中出错,但无法指明错误位置。 注意,这里的加法和除法都基于模2运算,其特点是不考虑进位和借位的运算,相当 于异或运算。 【例3-3】假设要发送的数据为101110,采用CRC 的生成多项式是G(x)=x3+1, 请问: (1)冗余码和发送的码字分别是什么? (2)若收到的数据序列是100010011,请判断是否有错 ? 解析:已知发送的信息 M =101110,生成多项式对应的除数G=1001 。 (1)经过除法运算,如图3-7所示,得到冗余码为 R =011,所以发送的码字 是101110011 。 图3-7CRC 计算示例 (2)如图3-8所示,用除数 G 除以收到的数据序列100010011,得到的结果是101,不 是全零。所以,收到的数据序列有错。 图3-8CRC 校验接收的数据 需要注意的是,余数为0并不能断定传输中一定无错。在某些非常特殊的位差错组 合下,CRC 完全有可能使余数为0,所以其检错率并非100% 。经过精心设计和实际检 验,目前国际上已被标准化的生成多项式G(x)主要见如下。 CRC-8:x8+x2+x+1 CRC-12:x12+x11+x3+x2+x+1 CRC-16:x16+x15+x2+1 CRC_CCITT:x16+x12+x5+1 CRC-32:x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 它们在实际通信中得到广泛的应用,如CRC-8被用于ATM 信元头差错校验中, CRC-16 被用于二进制同步传输规程中,CRCCCITT 被用于HDLC 通信规程中,CRC-32 被 用于IEEE802.信中。(_) 3以太网的数据链路层通 除了以上两种差错校验方法外,还有校验和校验方法。校验和的校验过程计算简单,但 其校验差错的能力远不如CRC 高。用CRC 检测方法无论是生成校验码还是进行差错检测 计算都比较复杂,在数据链路层一般都是使用硬件技术生成校验码和实现数据校验操作。 因此,CRC 技术常用在数据链路层,而校验和技术一般用在链路层之上的高层。另外,设置 高层校验也是为了避免因数据链路层漏检或硬件设备及软件系统异常而误收错误分组。 56 3.汉明码 3.3 汉明码由RichardHamming于1950年提出,是一种纠错码。其指导思想是,在被校 验的数据中,增加几位校验位。当某一数据位出错时,引起几位校验位的值改变,不同代 码位出错,得到不同的校验结果(即非法编码)。这样,不仅可发现错误,还能知道错误的 位置,进而达到纠正错误的目的。 它是利用在信息位为 k 位,增加 r 位冗余位,构成一个n=k+ r 位的码字,然后用 r 个监督关系式产生的 r 个校正因子区分无错和在码字中的 n 个不同位置的一位错。它必 须满足关系式2r ≥k+r+1或2r ≥n+1 。 汉明码的编码效率为R=k/( k 为信息位位数, k+r)( r 为增加冗余位位数)。 1.码距 码距是编码系统中两个任意合法码之间的最少二进制位数的差异。可见,ASCI 的 码距为1,奇偶校验码的码距为2。码距公式为 L-1= D + C (3-1) 式(3-1)中, L 为码距; D 是可检测的错误位数; C 为可纠正的错误位数。若能在数据码 中增加几个校验位,将数据代码的码距均匀拉开,把每个二进制位分配在几个奇偶校验组 中,则当某位出错后,会引起几个校验位的值的变化,这样不仅能查错,还能纠错。 为了检测出 d 个比特的错误,需要使用汉明距离为d+1的编码。例如:数据后加 奇偶校验位,编码后的汉明距离为2,能检测1b的错误。 为了纠正 d 个比特的错误,必须用汉明距离为2d+1的编码。例如:一个编码集只 有4个有效码字:000000,000111,111000,111111 。 其汉明距离为3。 如果接收端收到码字010111时,判断是由哪个码字错来的? 以上4个码字分别错 4、1、5和2,最有可能(概率最大)是第2个:d=1。 2.有效信息位与校验位的关系 校验的位数与有效信息位的位数有关。若被校数据是 k 位、校验位是 r 位,校验位共 有2r 个状态。在这2r 个状态中,应有 k 个状态表示 k 个数据位中是哪位出错。考虑到 校验位本身也可能出错,因此有 r 个状态分别表示不同校验位出错,另外还有一个状态表 示被校数据位和校验位都不出错。因此,为查出每位错,必须满足: 2r ≥k+r+1 (3-2) 例如:当r=4时,2r 取4 即 ; 16≥k+5 。于是, r 取5。 最小为5。 4≥k+4+1, k 最大为11, 因此,当被校数据为8位时,被校数据为16位时 , 3.编码规则 若被校数据为D8D7D6D5D4D3D2D1,校验位取4位P1 、P2 、P3 、P4,形成汉明 码H12H11H10H9H8H7H6H5H4H3H2H1 。 规则1:规定校验位Pi放在汉明位号为2i-1的位置上,则P1在H1位、P2在H2 位、P3在H4位、P4在H8位,其余的用信息数据从高到低插入。传送的数据流为 D8D7D6D5P4D4D3D2P3D1P2P1 。 4. 确定校验位的取值 规则2:被校数据位的汉明位号等于校验该数据位的各校验位汉明位号之和。另外, 校验位不需要再被校验。 各数据位与校验位的关系: D1 放在H3 上,由P2P1 校验,满足3=2+1 。 D2 放在H5 上,由P3P1 校验,满足5=4+1(P3 的汉明位号是4)。 D3 放在H6 上,由P3P2 校验,满足6=4+2 。 D4 放在H7 上,由P3P2P1 校验,满足7=4+2+1 。 D5 放在H9 上,由P4P1 校验,满足9=8+1 。 D6 放在H10 上,由P4P2 校验,满足10=8+2 。 D7 放在H11 上,由P4P2P1 校验,满足11=8+2+1 。 D8 放在H12 上,由P4P3 校验,满足12=8+4 。 注意:上述安排的目的是希望校验的结果能正确反映出错位的位号。 若用偶校验则可得到各位校验位的值: P1:D1,D2,D4,D5,D7→P1=D1..D2..D4..D5..D7 P2:D1,D3,D4,D6,D7→P2=D1..D3..D4..D6..D7 P3:D2,D3,D4,D8→P3=D2..D3..D4..D8 P4:D5,D6,D7,D8→P4=D5..D6..D7..D8 若数据D=10100110(D8—D1), 则有 : P1=D1..D2..D4..D5..D7=0..1..0..0..0= 1 P2=D1..D3..D4..D6..D7=0..1..0..1..0= 0 P3=D2..D3..D4..D8=1..1..0..1=1 P4=D5..D6..D7..D8=0..1..0..1=0 5. 汉明校验值 C1=P1..D1..D2..D4..D5..D7=1..1=0 C2=P2..D1..D3..D4..D6..D7=0..0=0 C3=P3..D2..D3..D4..D8=1..1=0 C4=P4..D5..D6..D7..D8=0..0=0 6. 校验结论 (1)若汉明校验值为全0,即C4C3C2C1=0000,表示数据传送无错。 (2)若汉明校验值1位出错,则校验位出错 。 当C4C3C2C1=0001 时,H1 出错,即校验位P1 出错 。 当C4C3C2C1=0010 时,H2 出错,即校验位P2 出错 。 当C4C3C2C1=0100 时,H4 出错,即校验位P3 出错 。 当C4C3C2C1=1000 时,H8 出错,即校验位P4 出错 。 (3)若汉明校验值中有2位或2位以上出错,则是被校验数据位出错。C4C3C2C1 58 的编码就是出错位的汉明位号。 C4C3C2C1=0011(汉明位号3),H3 出错,即数据位D1 出错。 C4C3C2C1=0101(汉明位号5),H5 出错,即数据位D2 出错。 C4C3C2C1=0110(汉明位号6),H6 出错,即数据位D3 出错。 C4C3C2C1=0111(汉明位号7),H7 出错,即数据位D4 出错。 C4C3C2C1=1001(汉明位号9),H9 出错,即数据位D5 出错。 C4C3C2C1=1010(汉明位号10),H10 出错,即数据位D6 出错。 C4C3C2C1=1011(汉明位号11),H11 出错,即数据位D7 出错。 C4C3C2C1=1100(汉明位号12),H12 出错,即数据位D8 出错。 按上述方法进行汉明码编码后,假设接收到的码字是101100111001,该如何校验和 纠错呢? 已知接收的汉明码共12 位,从中分离出校验位,得P1=1、P2=0、P3=1、P4=0,数 据位D8 到D1 的排列为10110110 。 接着通过译码公式求解校验结果: C1=P1..D1..D2..D4..D5..D7=1..0..1..0..1..0=1 C2=P2..D1..D3..D4..D6..D7=0..0..1..0..1..0=0 C3=P3..D2..D3..D4..D8=1..1..1..0..1=0 C4=P4..D5..D6..D7..D8=0..1..1..0..1=1 则有C4C3C2C1=1001,结果非0,说明接收的码字有错,且汉明位号9出错,即数据 位D5 出错。 因此,正确的数据是:10100110 。 3.流量控制 4 在链路的两个站点之间建立了链路连接后,就进入了数据传输阶段。为了保证数据 传输的正确性和完整性,必须建立一套通信协议。 流量控制用于协调链路中发送方和接收方之间的数据流量,以保证双方的数据发送 和接收达到平衡。当来不及接收时,就必须及时控制发送方的发送速率。流量控制可以 有效地防止由于网络中瞬间的大量数据对网络带来的冲击,保障用户的网络运行。 流量控制不仅可以在数据链路层上实现,在其他高层,如网络层和传输层上也有相应 的控制机制。不同功能层的流量控制对象是不同的,数据链路层上控制的是网络中相邻 节点之间的数据传输过程,网络层上控制的是网络源节点和目的节点之间的数据传输,而 传输层上控制的是网络中不同节点内发送进程和接收进程之间的数据传输过程。 目前,通信节点之间常用的流量控制技术有停止-等待方式(简称为停等方式)和滑动 窗口方式,分别对应有停止-等待协议(简称为停等协议)和滑动窗口协议,后者又包括了 后退 N 帧协议和选择重传协议。 3.1 停等协议 4. 停等协议是最简单的流量控制协议。在数据传输之前,发送方已将上层发来的分组 装配成帧,分为数据帧和确认帧。每当发送完一个数据帧,就主动停止,等待接收方的确 认。如果收到的是肯定应答,则接着发送下一个帧;如果收到否定应答或在规定的时间内 没有收到任何应答,则重发该帧。停等协议的工作流程如图3-9所示。 图3-9 停等协议的工作流程 接收方获得帧后,先计算其校验和,实现差错检测。进一步地,如果正确的帧是接收 方所期望的,则给发送方返回确认帧,并上交分组给网络层;否则丢弃该帧,继续等待,或 者发回一个否定帧(对于选择重传协议)。 为了说明停等协议的具体原理,下面分别讨论几种可能的数据传输现象,如图3-10 所示。 1. 无差错的理想情况 如图3-10(a)所示,指主机A到主机B的传输信道没有差错。接收方的缓存只需要 装下一个数据帧,收发双方能够实现良好的传输同步。 实际的传输信道是不理想的,差错不可避免,可能出现数据错误或丢失情况。 2. 数据帧传输出错情况 如图3-10(b)所示,主机A向主机B发送一个数据帧DATA0,但在传输中出现了差 错。如果该帧的结构仍然完整,则接收方能够识别此帧,并进行差错校验。一旦判断其是 有差错的数据帧,则丢弃该帧,并向对方发回一个否定的帧(NegativeAcknowledgement, NAK), 要求对方对NAK 中指定的帧进行重传。 60 图3-10 在链路上传输帧的情况 3. 数据帧丢失情况 如图3-10(c)所示,主机A发往主机B的数据帧在传输中丢失,使主机B始终处于等 待状态。此时,主机A也在一直等待确认的到来,就会出现死锁现象。为了解决这个问 题,需要引入定时器,设置重发时间Tot。每当一个数据帧发出之后,就立即启动一个定时器。如果定时器超时后仍然没有收到(u) 主机B的应答,则重发该帧,这种方法称为超时 重发。如果连续多次重传都出现差错,超过了一定次数(如16 次), 则停止发送,向上一级 报告故障情况。 4. 确认帧丢失情况 如图3-10(d)所示,确认帧在传输中丢失。主机A因为收不到该确认帧,执行超时重 发。结果是主机B收到了一个重复帧。为了分清是新帧还是重复帧,需要对每个帧设置 序号,以示区别。因此,如果两个序号相同,就认为是重复帧。 可见,使用以上方法可以避免帧的重复和丢失,实现了一定的差错控制功能。而接收 方控制发送确认帧ACK 的时间(不超过重发时间), 还完成了流量控制功能。 停等协议的优点是控制比较简单,但由于一次只能发送一帧,在信号传播过程中发送 方必须处于等待状态,这对于短信道来说是合适的。对于长信道而言,效率很低。下面分 析停等协议的传输效率,具体过程如图3-11 所示。 假设在传输过程中没有数据帧的差错发生,则总时延为 图3-11 停等协议的信道利用率计算示意 T =tp+tf+tp1+ta+tp+tp(3-3) 进一步地,假设计算机对数据帧的确认帧(r) 的处理时间可以(r) 相对忽略不计。同时,(2) 由于 确认帧比数据帧小得多,其传输时延也忽略,则有 T ≈tf+2tp (3-4) 在无差错的数据链路中,数据传输效率 U 表示为 U= tf3 tf+2tp (5) 可见,如果在一个总时延内能够连续发送多个数据帧,就会使传输效率成倍增加。 【例3-4】已知信道速率为8kb/s,传播时延为20ms,确认帧长度和处理时间均可忽 略。如果采用停等协议,请问帧长是多少才能使信道利用率至少达到50%? 解析:已知tp=20ms 。设帧长为L(b), 则有:tf=(L/8)ms 。由式(3-5)可得 U= tf ≥50% tf+2tp 当tf≥40ms 时,不等式成立。因此,帧长L≥320b 。 4.滑动窗口机制 3.2 滑动窗口机制是网络中控制流量最常用的技术方案,发送方不必等待接收方的应答 就可以连续发送数据帧,但对发送方在收到确认帧之前可以发送的数据帧数目加以限制。 如果希望发送方停止发送数据,就停止发送确认信息,使发送方发送缓冲区中未被确认的 62 数据帧很快达到极限而停止发送新的数据帧,直到再次收到接收方的确认帧。 所有帧都进行统一编号,既要正确区分不同的帧,又要减少控制开销,提高传输效率。 如果用 n 比特表示帧的序号,则帧的序号范围是0~(2n -1)。例如,在传播时延较小的 链路上,通常设置n=3,序号空间为0~7,共8个序号,称为“模8”编码。待发送完序号 为0~7的帧后,下一帧又从0开始。而在传播时延较大的链路上,如卫星链路上,通常使 用n=7的编码方案,序号空间为0~127,共128 个序号,称为“模128”编码。 1. 发送窗口 发送缓冲区由两部分组成:一是已经发送出去、但未接收到确认的数据帧,保留这部 分的目的是预备其中某些帧需要重发;二是还未被发送的数据帧,也是发送方能够继续发 送的数据帧。 发送方把未得到确认而允许连续发送的一组帧的序号集合称为发送窗口,即允许发 送的帧的序号表。 图3-12 是发送窗口的滑动控制示意图,帧的序号范围是0~7。 图3-12 发送窗口的控制过程 发送方未得到确认而允许连续发送的帧的最大数目称为发送窗口尺寸。发送方每发 送一个新帧,都要先检查该帧序号是否落在发送窗口内。发送方最早发送但还未收到确 认的帧序号,称为发送窗口的后沿;发送窗口后沿加上窗口尺寸再减1,称为发送窗口的 前沿,表示发送方在收到确认前最后允许发送的帧序号。如图3-12(a)所示的窗口尺寸为 5,后沿为0,则前沿为0+5-1=4。 发送方每发送一个新的数据帧,窗口的后沿就向前滑动一个序号,窗口尺寸减1,即 可以连续发送的帧数减1。而当发送窗口尺寸为0时,窗口关闭。如图3-12(b)所示,窗 口尺寸由5减小到4;而在图3-12(c)中,窗口尺寸为0,不可发送。 在收到了发送窗口后沿所对应的帧的确认应答后,就将发送窗口前沿向前滑动一个 序号,且窗口尺寸加1,表示可以继续发送的帧数加1,并从发送缓冲区中将已确认的数据 帧的副本删除。如图3-12(d)所示,窗口尺寸变为3,可以发送3个新的数据帧。 因此,接收方就可以通过发送确认帧控制发送窗口的滑动,从而达到流量控制的目的。 2. 接收窗口 同样,在接收方将允许接收的一组帧的序号集合称为接收窗口,即允许接收的帧的序号 表。接收方最多允许接收的帧数目称为接收窗口尺寸。接收窗口的上下界分别称为接收窗 口的前沿和后沿。如图3-13 所示,接收窗口尺寸为1。图3-13(b)中的前沿和后沿都是1。 图3-13 接收窗口的控制过程 接收方每收到一帧,都要判断该帧是否落在接收窗口之内。如果帧的序号正好等于 接收窗口的后沿,且经过检验正确,则将该帧的数据部分上交给网络层,并向发送方返回 一个确认帧,同时使接收窗口向前滑动一个序号。 如果收到的帧序号落在接收窗口之外,则直接丢弃该帧,不进行其他处理。 如果收到的帧序号落在接收窗口但不等于接收窗口后沿,则该帧经过检验正确后,暂 时保留在接收缓冲区中。然后,继续等待序号为接收窗口后沿的帧,直到正确地收到后, 才将其连同先前保留在接收缓冲区中的帧按顺序送交上层,并发出应答,同时向前滑动接 收窗口。 下面,以饼图方式表示滑动窗口协议的基本原理,其发送窗口尺寸为2、接收窗口尺 寸为1,如图3-14 所示,从初态开始,展示了从发送0号帧到接收1号确认帧的窗口滑动 过程。从中可以清晰地看到,在发送进行中,无论是发送窗口还是接收窗口,其位置都一 直在顺时针转动。 在滑动窗口机制中,既要发挥流量控制的作用,又要尽可能地提高传输信道的利用 率。如果发送窗口太小,则会造成传输信道的浪费;但如果发送窗口太大,又起不到流量 控制的作用。理想的情况是,当刚刚发完发送窗口中允许发送的最后一帧时,就收到了窗 64 图3-14 滑动窗口协议的滑动示意 口中最先发送帧的确认。这样,发送窗口向前滑动,又可以继续发送;同时,信道的利用率 几乎没有浪费。 在发送窗口大于1的滑动窗口协议中,如果传输中出现差错,协议则会自动要求发送 端重传出错的数据帧,这种滑动窗口控制机制称为自动重传请求(AutomaticRepeat reQuest,ARQ), 或称为自动请求重传。 4.后退 N 帧协议 3.3 后退 N 帧协议也称为连续ARQ 协议,是指发送方可以连续发送多个数据帧,而接 收方只能按顺序接收指定序号的帧。如果该帧被正确接收,则接收窗口向前滑动一帧,并 开始接收下一帧。但是,如果某个发送的数据帧出错或丢失,接收方无法接收到该帧,则 其后到达的 N 帧也都只能丢弃。所以,等到发送方定时器超时,就必须重发这一帧及其 后面的所有帧,因此称这种协议为后退 N 帧(Go-Back-N)协议,简称为GBN 协议。 图3-15 是后退 N 帧协议的示意图,当2号数据帧出错并被丢弃后,后面到达的3~8 号帧都被丢弃,也不发应答。等到发送方超时后,从第2帧开始全部重发直到确认后,才 能继续发送新的数据帧。可见,本协议一方面因为能够连续发送多个数据帧而提高了效 率,另一方面却因为后退 N 帧的重传方式而降低了效率。所以,如果信道的传输质量很 差且误码率较大时,后退 N 帧协议不一定优于停等协议。 【例3-5】对于后退 N 帧协议,其接收窗口尺寸固定为1,即 W R=1。若用 n 个比特 对数据帧进行编码,试证明:只有当发送窗口尺寸 W T≤2n -1时,本协议才能正确运行。 证明:为讨论方便,取n=3,则数据帧的序号范围为0~7,最大窗口尺寸为8。 采用反证法,令 W T=8,即发送窗口尺寸为8时的协议工作情况。 考虑以下极端状态下的传输过程(如图3-16 所示)。 图3-15 后退 N 帧协议 图3-16 后退 N 帧协议的发送窗口尺寸问题 (1)初始状态,接收窗口位于0号时,发送方开始发送0~7号的数据帧。 (2)接收方在正确收到了0~7号共8个帧后,立即上交到网络层,返回对所有帧的 确认后,窗口滑动到0号,并准备接收新一轮的0~7号数据帧。 (3)所有的应答帧都丢失。 (4)发送方超时,重发0~7号数据帧。 (5)接收方按顺序滑动,先后收到0~7号数据帧,并错误地将其当作新的数据帧送 交网络层,于是协议失效。 因此,发送窗口尺寸必须小于8,即 W T<8 。 那么, W T=7时协议能否正确运行呢? 再次考虑上述极端状态的传输过程。 66 (1)初始状态,接收窗口位于0号时,发送方开始发送0~6号的数据帧。 (2)接收方在正确收到了0~6号共7个帧后,立即上交到网络层,返回对所有帧的 确认后,窗口滑动到7号,并准备接收新一轮的7号和0~5号数据帧。 (3)所有的应答帧都丢失。 (4)发送方超时,重发0~6号数据帧。 (5)接收方先后收到0~6号重发的数据帧,由于不是期待的7号,所以直接丢弃,然 后重新发送对0~6号帧的应答,表示希望接收序号从7开始的帧。 (6)发送方收到应答后,发送序号为7号和0~5号的新数据帧。这样就保证了协议 的正常实现。 因此,有 W T≤7 成立。证毕。 3.4 选择重传协议 4. 在后退 N 帧协议的重发方案中,可能将已经正确传送到目的方的帧再次重发,这显 然是一种浪费。另一种效率更高的策略是,当接收方发现某帧出错后,其后继续送来的正 确帧虽然不能立即递交给接收方的高层,但接收方仍可收下来并存放在一个缓冲区中。 同时,要求发送方只重传出错的数据帧或者定时器超时的数据帧。一旦收到正确的重传 数据帧后,就可以与原来已存于缓冲区中的其余帧一并按正确的顺序递交高层。这就是 选择重传(SelectiveRepeat)协议,简称为SP 协议。 选择重传协议的工作原理如图3-17 所示,其发送窗口尺寸和接收窗口尺寸都大于1。 接收方收到出错的2号帧后,立即丢弃该帧并返回一个否认帧NAK2,要求发送方选择重 发2号帧。随后正确接收的3~4号数据帧被保存在缓冲区中。在接收到正确的2号数 据帧后,将2~4号数据帧一起提交给高层,且返回ACK4 。 图3-17 选择重传协议的工作原理 选择重传协议具有两个明显的特点。 (1)采用累计确认技术。接收方收到了连续且正确的数据帧后,为了节省链路带宽 资源,并不对每一个数据帧返回确认,而是只返回对最高序号的帧进行确认。发送方收到 这个确认帧号后,认为该帧号之前的其他帧都已经被正确接收。 (2)否认帧。在收到的数据帧经校验计算发现有错后,接收方会返回一个否定帧,以 便通知发送方重发该帧。这样,发送方如果收到了否认帧,则可以在定时器的超时到来之 前,就能够立即重发数据帧。 显然,选择重传协议减少了浪费,但要求接收方有足够大的缓冲区空间,这在许多情 况下是不够经济的,因此,该协议目前还没有后退 N 帧协议使用得广泛。随着存储技术 的发展,选择重传协议应该会得到重视,如在传输层的TCP 协议中,就使用了类似选择重 传的传输控制方法。 在选择重传协议中,发送窗口尺寸和接收窗口尺寸往往相同,其最大窗口尺寸为2n-1 n 为帧的编码序号)。( 【例3-6】假设帧的序号长度为3位,发送窗口尺寸和接收窗口尺寸都是2,采用选 择重传协议发送数据帧。请画出由初始状态出发,下列事件依次发生时的发送窗口和接 收窗口示意图:发送帧0、发送帧1、接收帧0、接收确认帧0、发送帧2、接收帧2、重发帧 1、接收帧1、接收确认帧2。 解析:采用饼图描述这个过程,如图3-18 所示。 图3-18 选择重传协议的滑动窗口控制示例 3.高级数据链路控制(HDLC)协议 5 数据链路层协议基本可以分为两类:面向字符型和面向比特型。面向字符型协议出 现得最早,其特点是利用已经定义好的一种字符编码的一个子集执行通信控制功能,典型 的有IBM 公司的BSC 协议。但是,这类协议具有明显的缺点,一是使用不同字符集的计 算机无法利用该协议进行通信;二是控制字符的编码不能出现在用户数据中;三是控制功 能的扩展性差,每增加一项功能就需要添加和定义相应的控制字符。而面向比特型协议 可以克服这些缺点。尽管如此,目前面向字符型的点到点协议(Point-to-PointProtocol, 68 PPP)在Internet中仍然得到了广泛的应用。 1974年,Syttrrhtcue, IBM公司推出了著名的系统网络体系结构(semNewokAcietrSNA),用于IBM公司的大型机(ES/9000和S/390等)和中型机(AS/400)之间的联网。 SNA中的数据链路层协议采用了面向比特的SDLC(SynchronousDataLinkControl)协 议。面向比特指帧首部中的控制信息是由比特组合而成,而不是由几种特殊的控制字符 而定,因此,控制信息可以具有很多功能,使SDLC协议能够满足不同用户的需求。 此后,ISO把SDLC修改为高级数据链路控制HDLC(High-levelDataLink Control),作为国际标准ISO3309 。相应地,我国的国家标准原为GB7496,现已被GB/T 7421—2008代替,于2009年1月1日起实施。原CCITT则将HDLC再修改后并称为链 路接入规程(LikAsPrcedrLAP), 25建议书的一部分。不久,HDLC nceoue,并作为X. 的新版本又把LAP修改为LAPB,称为链路接入规程(平衡型)。 下面详细介绍HDLC的特点、帧结构和帧类型。 3.1 HDLC的基本特点 5. HDLC定义了三种类型的站,两种配置和三种数据传输模式。 1.站 三种类型的站分别是主站、从站和复合站。主站负责控制链路的操作,其发出的帧称 为命令帧。从站受控于主站,向主站发出响应帧。复合站是指具有主站和从站的双重功 能,可以发出命令帧和响应帧。 2.两种配置 两种配置包括平衡配置和非平衡配置。在平衡配置中,每一端都是复合站,所以这种 配置只能工作于点对点方式中。而非平衡配置可用于点到点链路或多点链路,由一个主 站和一个从站或多个从站组成。 3.三种数据传输模式 (1)正常响应模式(NRM),属于非平衡配置,主站向从站传输数据,从站进行响应。 但是,从站只有在收到主站的许可后,才能响应。 (2)异步平衡模式(ABM),属于平衡配置,每个复合站都可以发送、接收命令/响 应帧。 (3)异步响应模式(ARM),属于非平衡配置,从站在没有接收到主站的允许时就可 以发起数据传输,但主站仍负责全程的初始化和差错恢复等工作。 3.2 HDLC的帧结构 5. 所有面向比特的协议都使用如图3-19所示的帧结构。 1.标志字段 F 每帧的首尾都采用01111110(0x7E)作为边界。当连续传输一些帧时,前帧的结束标 志F可以兼作为下一帧的起始标志。在组帧方式中,HDLC规定采用3.3节介绍的比 2.