第3 章 数据链路层 数据链路层属于计算机网络的低层,数据链路层有两种截然不同的信道。第一种类 型链路层信道是广播信道。这种信道使用一对多的广播通信方式,同一信道上连接的主 机很多,需要使用专用的介质访问控制协议来协调传输和避免“碰撞”,局域网中常用这种 信道。第二种类型链路层信道是点对点信道。这种信道使用一对一的点对点通信方式。 如两台路由器之间的通信链路或一个住宅的拨号调制解调器与一个ISP路由器之间的通 信链路。协调点对点信道的访问是很容易的,但也存在一些重要问题,如组帧、可靠数据 传输、差错检测和流量控制等。 如图3.1所示,在两台主机通过互联网通信时,从源主机H1 开始,经过一系列路由器 (R1、R2、R3),到目的主机H2 结束。所经过的网络可以是多种,如电话网、局域网和广域 网。该通信路径由一系列通信链路组成。从协议的层次看,主机H1 和H2 有完整的协议 层次,路由器的协议栈只有下面三层。数据进入路由器后先从物理层上到网络层,在网络 层的转发表中找到下一条的地址后,再下到物理层转发数据。 图3.1 数据链路层 当我们研究数据链路层的问题时,很多情况下可以从各结点协议栈的数据链路层水 平方向来着眼,如图3.2所示。当主机H1 向H2 发送数据时,我们可以想象数据是在数 据链路层从左向右水平传送,即通过这样的四段链路:H1 链路层→R1 链路层、R1 链路 层→R2 链路层、R2 链路层→R3 链路层和R3 链路层→H2 链路层。 协议数据单元如何通过各段链路? 在单段链路上,网络层的“分组”如何被封装成数 据链路层的“帧”? 数据链路层协议能够提供可靠地传输吗? 在整个通信路径上不同的链 第 3 章　数据链路层 89 图3.只考虑数据在数据链路层流动 2 路是采用的相同的链路层协议吗? 这类重要问题我们就在这一章来回答。 3.数据链路层的基本概念 1 3.1.1 数据链路和帧 先来学习一些术语。为方便讨论,我们把主机和路由器统称为结点,我们将不关心一 个结点是主机还是路由器。我们把沿着通信路径连接相邻结点的通信信道称为链路,有 人将其称为物理链路。链路的中间没有任何其他的交换结点。两个主机通信时,通信路 径上要经过许多独立的链路。当在一条通信路径上传输数据时,除了要有物理链路外,还 必须要有通信协议来控制这些数据的传输。把实现数据传输协议的硬件和软件加到链路 上,就构成了数据链路,有人将其称为逻辑链路。网络适配器就是实现这些协议的硬件和 软件。一般的适配器包含了数据链路层和物理层这两层的功能。链路层协议交换的数据 单元称为帧(rame )。 f 所有的数据链路层的基本功能都是将数据帧通过单条链路从一个结点移动到相邻结 点,如图3.但具体细节依赖于该链路上应用的具体数据链路层协议。链路层协议 3所示, 包括以太网、IEEE802.令牌环和PPP 等。链路层的一个重要特点是在通 11 无线局域网、 信路径的不同链路上可能由不同的链路层协议来处理。例如在第一段链路上可能由 PPP 来处理,在最后一段链路上可能由以太网来处理,在中间的链路上由广域网链路层 协议来处理。需要着重注意的是,不同的数据链路层协议的提供功能是不同的。例如一 个数据链路层协议可能提供可靠的交付,另一个数据链路层协议可能不提供可靠的交付。 图3.帧在数据链路层一条链路上移动 3 3.1.2 数据链路层基本问题 数据链路层可能提供的服务包括:组帧、差错控制、流量控制、可靠传输和介质访问 控制。 90 计算机网络教程 1.组帧 在网络层分组在链路上传输前,链路层协议用数据链路层的帧将其封装。一个帧由 数据字段和首部字段组成,网络层的分组就插在数据字段中。一个帧可能包含尾部字段, 我们把首部字段和尾部字段合并起来称为首部字段。接收端在收到物理层上交的比特流 后,能根据首部字段的标记, 如图3. 从收到的比特流中识别帧的开始和结束,4所示。帧 的结构由数据链路层协议规定。 图3.组帧 4 数据链路层的主要工作是添加一个帧头部和帧尾部,不同的数据链路层协议可能格 式不同,但是基本的格式都是相似的,5所示。 如图3. 图3.帧格式 5 这里的数据部分,一般有一个最大程度,我们称为最大传输单元(Maximum TransmisionUnit,MTU),是指一种通信协议的某一层上面所能通过的最大数据包大小 (以字节为单位),对于时下大多数使用以太网的局域网来说,最大传输单元的值是1500 字节。这里要说的是,当数据是由可打印的ASCI 码组成的文件时,可以使用特殊的帧 定字符来标明一个帧的开始和结束。比如使用SOH(Strae-x01和EOT atOfHedr)0(n)04来表示,这样数据链路层就可以识别出帧的开始和结束。 EndOfTransmisio-0x 如果我们提供任何数据输入,数据链路层都可以成功传递,那么称之为透明传输,即 数据链路层的功能对于网络层和上层是透明的。比如文本字符数据输入,SOH和EOT 都可以很好地工作,因为二者没有交集。但是对于二进制数据输入来说,就有可能在数据 中出现0x01和0x04,导致帧意外地中断和丢弃。因此,我们需要一种机制来处理这种情 况,最经典、最常用的就是字节填充或字符填充的方式。比如在SOH和EOT的前面分 别插入一个转义字符ESC-0x1B,在接收端的数据链路层在将数据送往网络层之前删除 这个插入的转义字符,这就称为字节填充。 第 3 章　数据链路层 91 图3.字节填充法实现透明传输 6 2. 差错控制 设计数据链路层的主要目的就是要将有差错的物理线路改进成无差错的数据链路, 因此,差错控制功能是数据链路层中一个非常重要的基本功能,也是确保数据通信正常进 行的基本前提。目前,数据链路层所采取的差错控制方法主要包括差错检测技术、差错纠 正技术,以及数据帧重传技术等。 数据链路层的许多协议提供检测是否存在差错的机制。这是通过在帧中设置差错检 测冗余位,让接收结点对收到的帧进行差错检测来完成的。链路层的差错检测通常很复 杂,并且通过硬件来实现。 差错纠正不仅能检测是否帧中出现了差错,而且能够判断帧中的差错出现在哪里并 纠正这些错误。一些协议如ATM 只为分组的首部提供链路层差错纠正。 3. 流量控制 由于链路的每一结点具有有限的帧缓存,接收结点在某个时间段收到帧的速率比其 处理的速度快,没有流量控制,接收方的缓存会溢出,帧会丢失。链路层协议提供流量控 制机制,当接收方来不及处理发送方发送的数据时,及时控制发送方发送数据的速率,旨 在使收发方协调一致。 4. 可靠传输 当数据链路层提供可靠传输服务时,它保证将网络层的分组无差错地通过数据链路 层。OSI 的观点是必须把数据链路层做成是可靠传输的。前面讲过,传输层的协议TCP 也提供可靠的传输服务。和传输层的可靠传输服务类似,链路层的可靠传输是通过确认 和重传来获得的。现在通信线路的质量已经大大提高了,通信链路不好引起差错的概率 已经大大降低。低差错率的链路,包括光纤、双绞线和同轴电缆,链路层的可靠传输被认 为是不必要的开销。为了提高通信效率,许多有线的链路层协议不提供可靠的交付, Internet广泛使用的数据链路层不提供可靠的服务。数据链路层可靠的传输服务常用于 容易产生高差错率的链路,如无线链路。 5. 介质访问控制 介质访问控制协议定义了帧在链路上传输的规则。对于在链路的一端有一个发送 方、另一端有一个接收方的点对点链路,介质访问控制协议比较简单,甚至不存在。对于 92 计算机网络教程 多个结点共享单个广播链路,就是被称为多址访问的问题,介质访问控制协议用来协调多 个结点的帧传输。 数据链路层提供的许多服务和传输层提供的服务非常相似。例如数据链路层和传输 层都能提供可靠交付。尽管这两层用于提供可靠交付的机制相似,这两个可靠交付服务 却是不同的。传输层协议在端到端的基础上为两个进程之间提供可靠交付;而可靠的链 路层协议在一条链路相连的两个结点之间提供可靠的交付服务。同样地,数据链路层和 传输层都能提供流量控制和差错检测,传输层协议中的流量控制是在端到端的基础上提 供的,而链路层协议是在结点对相邻结点基础上提供的。 6.链路管理 数据链路层的“链路管理”功能包括数据链路的建立、链路的维持和释放三个主要方 面。当网络中的两个结点要进行通信时,数据的发送方必须知道接收方是否已处在准备 接收的状态。为此,通信双方必须先要交换一些必要的信息,以建立一条基本的数据链 路。在传输数据时,要维持数据链路;而在通信完毕时,要释放数据链路。大多数广域网 的通信子网的数据链路层均采用有确认面向连接的服务,源计算机和目标计算机在传输 数据前需要先建立一个连接,而且该连接上发送的每一帧也都要被编号,以确保帧传输的 内容与顺序的正确性,为此,数据链路层除了可保证每一帧都会被接收方收到之外,还可 保证每一帧都只会被按正常顺序接收到一次。 7.MAC寻址 MAC寻址是数据链路层中的MAC子层的一项主要功能。在以太网中,介质访问控 制(MediaAcesControl,MAC)地址被烧录到每个以太网网卡中作为通信结点数据链 路层的唯一标识,而在多点连接的网络通信中,数据链路层必须要保证让每一帧都能准确 地送到正确的接收方,且接收方也应当知道发送方到底是哪一个结点,为此,数据链路层 必须要能够通过采用MAC地址来进行寻址。 3.差错控制技术 2 差错控制指的是在数据通信过程中能发现或纠正差错,把差错限制在尽可能小的允 许范围内的技术和方法。 信号在物理信道中传输时,线路本身电器特性造成的随机噪声、信号幅度的衰减、频 率和相位的畸变、电器信号在线路上产生反射造成的回音效应、相邻线路间的串扰以及各 种外界因素(如大气中的闪电、开关的跳火、外界强电流磁场的变化、电源的波动等)都会 造成信号的失真。在数据通信中,将会使接收端收到的二进制数位和发送端实际发送的 二进制数位不一致,从而造成由“0”变成“1”或由“1”变成“0”的差错。 通信信道的噪声分为两类:热噪声和冲击噪声。其中,热噪声是信道固有的、持续存 在的随机热噪声,它引起的差错是随机差错;冲击噪声是由外界特定的短暂原因所造成的 噪声,它引起的差错是突发差错,引起突发差错的位长称为突发长度。在通信过程中产生 的传输差错,是由热噪声的随机差错与冲击噪声的突发差错共同构成的。数据通信的差 错程度通常是以“误码率”来定义的,它是指二进制比特在数据传输系统中被传错的概率, 93 第 3 章　数据链路层 它在数值上近似等于Pe=Ne/ N 。其中, N 为传输的二进制比特总数,Ne 为被传错的比 特数。 最常用的差错控制方法是差错控制编码。数据信息位( k 位)在向信道发送之前,先 按照某种关系附加上一定的冗余位( n 位), 构成一个码字后再发送,这个过程称为差错控 制编码过程。编码效率就是 k 除以(k+n)的值。接收端收到该码字后,检查信息位和附 加的冗余位之间的关系,以检查传输过程中是否有差错发生,这个过程称为检验过程。 差错控制编码可分为检错码和纠错码。检错码是能自动发现差错的编码;纠错码是 不仅能发现差错而且能自动纠正差错的编码。 差错控制方法分两类,一类是自动请求重发ARQ,另一类是前向纠错FEC 。在ARQ 方式中,当接收端发现差错时,就设法通知发送端重发,直到收到正确的码字为止。ARQ 方式只使用检错码。在FEC 方式中,接收端不但能发现差错,而且能确定二进制码元发 生错误的位置,从而加以纠正。FEC 方式必须使用纠错码。 3.2.1 检错 目前在数据链路层广泛使用了循环冗余检验(CyclicRedundancyCheck,CRC)的检 错编码。循环冗余检验编码也称为多项式编码,因为能把比特串看作是系数为0和1的 一个多项式,对比特串的操作被解释为多项式算术。 在发送端要发送的 k 比特的数据 M ,发送结点要把数据 M 发送给接收结点。发送 方和接收方首先要协商一个n+1 比特生成码P,称为生成多项式P(x)。要求P(x)的 最高有效位的比特(最左边)是1。 对于一个给定的数据 M ,发送方要选择 n 位的附加比特 R 即冗余码(冗余码常称为 帧检验序列FCS), 附加在 M 后面,使得产生的k+ n 比特的数据一起发送到接收端。在 所要发送的数据后面增加 n 位冗余码,虽然增大了数据传输的开销,但却可以进行差错 检测,往往是很值得的。 这 n 位的冗余码 R 是如何得出的呢? 是用模2运算(在加法中不进位,在减法中不 借位。这意味着加法和减法是相同的,而且等价于操作数的按位异或(XOR)运算), 相当 于在 M 后面添加 n 个0。得到(位的数除以发送方和接收方协商好的n+1 位除数 P,得出的商是 Q 余数是R( k+ 比 nP) 少一位)。 n 位 , 【例3-1】已知:信息码M110011,信息多项式 M (x)=x5+x4+x+1 。 生成码P1101,生成多项式P(=n=3) 。 求:冗余码和码字。 x)x3+x2+1( 【解】(1)被除数是信息码 M 后添加n=3个0,即110011000 。 (2)除数是 P 即1101 。 (3)用模2运算(7所示)。由计算结果知冗余码是001, 如图3.码字就是110011001 。 在接收端把收到的数据以帧为单位进行CRC 检验。用CRC 进行差错检验的过程很 简单:接收方用 P 去除接收到的k+ n 位比特。如果余数为0,则认为正确而被收下得到 信息码;如果余数为非0,则接收方认为发生错误,就丢弃该帧,请求对方重发。 【例3-2】已知:接收码字1100111001,多项式T(x)=x9+x8+x5+x4+x3+1 。 94 计算机网络教程 图3.求冗余码的例子 7 生成码P11001,生成多项式P(x)=x4+x3+1(4)。 n= 求:码字的正确性。若正确,则指出冗余码和信息码。 【解】(1)用码字除以生成码,余数为0, 8所示, 如图3.所以码字正确。 图3.求码字正确性的例子 8 (2)因n=4,所以冗余码是:1001,信息码是:110011 。 现在广泛使用的生成多项式P(x)有如下几种: CRC-16=x16+x15+x2+1 CRC16-CCITT=x16+x12+x5+1 CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 CRC 码不能100% 地发现错误,余数为0时可能发生差错。一般生产多项式阶数越 高,检错能力越强。凡是接收方数据链路层接受的帧,我们都能以非常接近于1的概率认 为这些帧在传输过程中没有产生差错。通常都这样近似地认为:凡是接收方数据链路层 接受的帧均无差错。 在数据链路层,发送端帧检验序列FCS 的生成和接收端CRC 检验都是用硬件完成 的,处理很迅速,因此不会延误数据的传输。 CRC 码不可以自动纠错,要做到可靠传输,必须加上确认和重传机制。 95 第 3 章　数据链路层 采用检错码技术虽然能够检测出帧在传输过程中是否发生了错误,但由于在检测到 错误发生之后,需要发送方重传整个帧,故检错码技术仅适用于光纤等具有高可靠性的信 道上,而不适合于错误发生很频繁的无线信道上,这是因为在错误发生很频繁的信道上, 即便重传也还是很可能出错的,因此难以有效保证帧的正确传送。在无线信道上,最好的 办法是使用纠错码(ErorCorectingCode)技术,通过在每一个发送的数据帧中包含足 够的冗余信息(校验位),让接收方在收到该数据帧后不但可以检测出其中是否发生了错 误,而且一旦发现出错,还可以还原出原始的帧内容,不需要依靠重传来解决问题。 3.2.2 纠错 采用纠错码进行差错控制时,接收端不仅能发现差错,而且知道出错码元的位置,从 而自动进行纠正。这种方式称为前向纠错(ForwardErorCorection,FEC )。海明码就 是一种纠错码。 发送方进行海明码编码,所需步骤如下: (1)确定最小的校验位数k。 (2)原有信息和 k 个校验位一起编成长为m+ k 位的新码字———海明码。选择 k 校 验位(0或1)以满足必要的奇偶条件。 接收方对收到的码字进行译码,所需步骤如下: (1)接收端对所接收的信息作所需的 k 个奇偶检查。 (2)如果所有的奇偶检查结果均为正确的,则认为信息无错误。如果发现有一个或 多个错了,则错误的位由这些检查的结果来唯一地确定。 1.校验位的位数 推求海明码时的一项基本考虑是确定所需最少的校验位数k。考虑长度为 m 位的 信息,若附加了 k 个校验位,则所发送的总长度为m+k。在接收器中要进行 k 个奇偶检 查,每个检查结果或是真或是伪。这个奇偶检查的结果可以表示成一个 k 位的二进字, 它可以确定最多2k 种不同状态。这些状态中必有一个其所有奇偶测试都是真的,它便是 判定信息正确的条件。于是剩下的(2k -1)种状态,可以用来判定误码的位置。于是导 出下一关系: k 2-1≥ m + k (3-1) 2.码字格式 从理论上讲,校验位可放在任何位置,但习惯上校验位被安排在1、2、4、8、…的位置上。 表3.1列出了m=4,3时,信息位和校验位的分布情况。 k= 表3.海明码中校验位和信息位的定位 1 码字位置B1 B2 B3 B4 B5 B6 B7 校验位 x x x 信息位 x x x x 复合码字P1 P2 D1 P3 D2 D3 D4 96 计算机网络教程 3. 各校验位的确定 k 个校验位是通过对m+ k 位复合码字进行奇偶校验而确定的。 其中:P1 位负责校验海明码的第1、3、5、7、…(P1、D1、D2、D4、…) 位(包括P1 自 己,检验1位,跳过1位)。 P2 负责校验海明码的第2、3、6、7、…(P2、D1、D3、D4、…) 位(包括P2 自己,检验2 位,跳过2位)。 P3 负责校验海明码的第4、5、6、7、…(P3、D2、D3、D4、…) 位(包括P3 自己,检验4 位,跳过4位)。 对m=4,3,偶校验的例子,只要进行三次偶性测试。这些测试(以A、B、 C 表示) k= 在表3. 2所示各位的位置上进行。 表3.奇偶校验位置 2 奇偶条件 码字位置 B1 B2 B3 B4 B5 B6 B7 A x x x B x x x x C P1 P2 D1 P3 D2 D3 D4 因此可得到三个校验方程及确定校验位的三个公式: A =B1..B3..B5..B7=0得P1=D1..D2..D4 (3-2) B =B2..B3..B6..B7=0得P2=D1..D3..D4 (3-3) C=B4..B5..B6..B7=0得P3=D2..D3..D4 (3-4) 明码。 例如四位信息码为1001,利用这三个公式可求得三个校验位P1、P2、P3 值和海 三个校验位:P1=0;P2=0;P3P= 11 P 。 21P3001 海明码:0011001 。 上面是发送方的处理 。 4. 接收方译码 在接收方,也可根据这三个校验方程对接收到的信息进行同样的奇偶测试: A =B1..B3..B5..B7=0 (3-5) B =B2..B3..B6..B7=0 (3-6) C=B4..B5..B6..B7=0 (3-7) 若三个校验方程都成立即方程式右边都等于0,则说明没有错。若不成立即方程式 右边不等于0,说明有错。从三个方程式右边的值,可以判断哪一位出错。例如,如果第3 位数字反了,则C=0(此方程没有B3),A=B=1(这两个方程有B3)。可构成二进制数 CBA,以 A 为最低有效位,则错误位置就可简单地用二进制数CBA=011 指出。 同样,若三个方程式右边的值为001,说明第一位出错。若三个方程式右边的值为 第 3 章　数据链路层 97 100,说明第四位出错。 例如,接收码字为0110111 经测试A=1;B=0;C=1。说明第五位有错,则只须将第 五位变反,就可还原成正确的数码0110011 。 海明码能够检测出两位同时出错,或者能检测出一位出错并能自动给出错位的正 确值。 3.流量控制技术 3 在本节,我们介绍一般意义上的可靠数据传输问题。可靠数据传输可以在数据链路 层实现,也可在传输层和应用层实现。一般性的问题对网络来说更为重要。 OSI 的观点是必须把数据链路层做成是可靠传输的。因此在CRC 检错的基础上,增 加了流量控制、确认和重传机制。采取适当的措施限制发送速率,避免由于接收方来不及 接收而造成数据丢失。接收方收到正确的帧就要向发送方发送确认。发送端在一定期限 内没有收到对方的确认,就认为出现了差错,因而就进行重传,直到收到对方的确认为止。 但现在通信线路的质量已经大大提高了,由于通信链路不好引起差错的概率已经大大降 低。为了提高通信效率,nent广泛使用的数据链路层不提供可靠的服务。数据链路 Itre 层可靠的传输服务常用于容易产生高差错率的链路,如无线链路。 3.3.1 流量控制与滑动窗口 当发送数据的速率高于接收数据的速率时,必须采取适当的措施限制发送速率,否则 会由于来不及接收而造成数据丢失。流量控制就是让发送方的发送速率不要太快,要让 接收方来得及接收。在本节,我们介绍如何用滑动窗口机制来达到流量控制的目的。 尽管流量控制可以用多种方式实现,但通常的方式是使用两个缓冲区:一个位于发 送方,另一个位于接收方。缓冲区是一组内存单元,它可以在发送端和接收端存储分组。 这样的缓冲区又称为窗口,在发送端和接收端分别设置发送窗口和接收窗口。 通常,数据链路层采用基于确认的流量控制机制来进行流量控制。在该方法中,一般 是通过定义一些良好的规则,这些规则规定了发送方什么时候可以发送下一帧。通常,由 接收方给发送方回送信息,告诉发送方被允许发送多少数据,而在没有得到接收方许可之 前,禁止发送方向接收方发送数据帧。基于确认的流量控制机制包括停止—等待技术、基 于回退 N 帧(GoBackN )技术的机制与基于选择性重传(SelectiveRepeat)技术的机制, 这些机制统称为滑动窗口机制(SlidingWindowMechanism )。此外,除了利用滑动窗口 机制来进行流量控制之外,为了进一步提高数据传输效率,数据链路层通常还采用捎带确 认、发送窗口与接收窗口等设计思想与技术。 (1)捎带确认:在收发双方在进行通信时,为了提高信道的利用率,将利用捎带确认 的方法进行数据帧的确认。其原理如下。当一方收到一帧A,如果其网络层有一个新的 分组到来要发送给对方,则通过在其数据帧的头部设置的ack域中捎带对A的确认,然 后再将该数据帧发送给对方(而不单独发送确认帧给对方,从而节约了网络带宽)。否则, 若在一定的时间周期内其网络层都没有新的分组到来,则发送一个单独的确认帧给对方。 98 计算机网络教程 (2)发送窗口:是指发送方维持的一组序列号,分别对应于发送方允许它发送的帧, 或它已发送但仍未被确认的帧。由于当前发送窗口内的帧最终可能在传输过程中丢失或 被破坏,因此,发送方需要用缓存区保存好这些帧以备重传。若发送窗口的大小为n,则 发送方需要 n 个缓存区来存放未被确认的帧。若发送窗口达到最大尺寸,则发送方的链 路层需要强制关闭其网络层,直到有一个缓存区空闲出来为止。 (3)接收窗口:是指接收方维持的一组序列号,分别对应于一组接收方允许接收的 帧。任何落在接收窗口外面的帧都将被接收方无条件丢弃。当一个新到的帧的序列号等 于接收窗口的下界时,接收方会把该新到帧以及接收窗口(即接收方缓存区)中原来保存 的其后续各帧依次传递给网络层,并生成一个确认帧给发送方,然后将接收窗口前移。 发送窗口和接收窗口统称为滑动窗口。 1. 发送窗口的规则 发送窗口用来对发送端进行流量控制。发送窗口是发送方用来保存允许发送和已发 送但尚未经确认的数据分组。发送窗口的大小 W T 代表在还没有收到对方确认信息的情 况下发送端最多可以发送多少个分组。图3. 9表示了发送窗口的规则。 图3.发送窗口的规则 9 (1)发送窗口内的分组是允许发送的分组(如图3.a), 发送窗口大小为5)。 9( 第 3 章　数据链路层 99 (2)每发送完一个分组,允许发送的分组数减1,但发送窗口的位置、大小不变(如图 3.b))。9( (3)若所允许发送的分组都发送完了,但还没有收到任何确认,发送方就不能再发 送,进入等待状态( 9( 如图3.c))。 (4)发送方收到对方对一个分组的确认信息后,将发送窗口向前滑动一个分组的位 置(如图3.d), 9(依次收到3个确认分组)。 (5)发送方设置一个超时计时器,当超时计时器满且未收到应答,则重发分组。 2. 接收窗口的规则 接收窗口是为了控制可以接收的数据分组的范围。接收窗口是接收方用来保存已正 确接收但尚未交给上层的分组。接收窗口的规则如下: (1)只有当收到的分组序号落入接收窗口内才允许收下,否则丢弃它。 (2)当接收方接收一个序号正确的分组,接收窗口向前滑动,并向发送端发送对该分 组的确认。 只有在接收窗口向前滑动时(与此同时也发送了确认), 发送窗口才有可能向前滑动。 收发两端的窗口按照以上规律不断地向前滑动,因此这种协议又称为滑动窗口协议。使 用滑动窗口机制,由接收方控制发送方的数据流,实现了流量控制。同时采用有效的确认 重传机制,向高层提供可靠传输的服务。 下面的停止—等待协议、回退 N 帧协议和选择重传协议三个协议都实现了流量控 制,是保证数据可靠传输常采用的协议。 3.3.2 停止—等待协议 停止—等待协议(Stop-and-Wait-Protocol), 发送方和接收方都使用大小为1的滑动 窗口。停止—等待协议(也称为停-等协议)的规则是:发送方每发送一个分组后就要停 下来等待接收方的确认返回,仅当接收方正确接收,并返回确认分组ACK,发送方接收到 确认分组后,才可以发送下一分组, 10(所示。 如图3.a) 图3.停止—等待协议 10 接收方收到一个数据分组,通过差错检测发现数据是错误的,接收方向发送方发送一 100 计算机网络教程 如图3.b)。 由于链路干扰或其他原因,在发送方发送的数据分组或接收方发送的确认分组ACK 丢失的情况下,发送方没有收到确认分组,到了超时计时器所设置的重传时间,发送方会 重传该分组,如图3.和图3.d)。 个否认分组NAK,发送方收到否认分组后重传出错分组, 10( 10(c) 10( 3.3.3 回退 N 帧协议 为了提高传输效率,当发送端等待确认时,可以传输多个分组。换言之,当发送端等 待确认时,我们需要让不止一个分组处于未完成状态,以此确保信道忙碌。回退 N 帧协 议(Go-back- N ,GBN)也称为连续自动重传请求(AutomaticRepeatRequest,ARQ)协 议,可以看成是发送窗口大于1,接收窗口等于1的滑动窗口协议。该协议的规则如下: (1)在发送完一个数据帧后,不是停下来等待确认帧,而是可以连续再发送若干个数 据帧。由于减少了等待时间,整个通信的吞吐量就提高了。 (2)如果这时收到了接收端发来的确认帧,那么还可以接着发送数据帧。 (3)如果发送方发送了前五个帧,而中间的第三个帧丢失了。这时接收方只能对前 两个帧发出确认。发送方无法知道后面三个帧的下落,而只好把后面的三个帧都再重传 一次。这就称为Go-back- N (回退 N ), 表示需要再退回来重传已发送过的 N 个帧,如 图3. 11 所示。 图3.后退 N 帧协议 11 接收端只按序号顺序接收数据帧。虽然在有差错的2号帧之后接着又收到了正确的 三个数据帧,但接收端都必须将这些帧丢弃,因为在这些帧前面有一个2号帧还没有收 到。虽然丢弃了这些不按序的无差错帧,但应重复发送已发送过的最后一个确认帧(防止 确认帧丢失)。在图3.并期望下次收到1号分 11 中ACK1 表示确认0号分组DATA0, 组;ACK2 表示确认1号分组DATA1,并期望下次收到2号分组,依此类推。 结点A在每发送完一个数据帧时都要设置该分组的超时计时器。如果在所设置的 超时时间内收到确认帧,就立即将超时计时器清零。但若在所设置的超时时间到了而未 第 3 章　数据链路层 101 收到确认分组,就要重传相应的数据帧(仍需重新设置超时计时器)。 在等不到2号分组的确认而重传2号数据帧时,虽然结点A已经发完了4号分组, 但仍必须向回走,将2号帧及其以后的各帧全部进行重传。这就是回退 N 帧协议,意思 是当出现差错必须重传时,要向回走 N 个帧,然后再开始重传。 在回退 N 帧协议中,接收窗口的大小 W R=如图3. 1, 12 所示。只有当收到的帧的序 号与接收窗口一致时才能接收该帧(如图3.DATA1), 否则就丢弃它( 图3.11 中的DATA3 、DATA4 、DATA5 )。 11 中的DATA0 、如 图3.接收窗口为1的情况 12 3.3.4 选择重传协议 回退 N 帧协议简化了接收方的进程。接收方只记录一个变量,没有必要缓冲时序分 组;它们被简单地丢弃。然而,如果下层网络层丢失很多分组,那么这个协议就是低效的。 每当一个分组丢失或被破坏,发送方要重新发送所有未完成分组,即使有些时序分组已经 被完全完整地接收了。如果网络层由于网络拥塞丢失了很多分组,那么重发所有这些未 完成分组将会使得拥塞更严重,最终更多的分组丢失。 选择重传协议(Selective-RepeatProtocol)已经被设计出来,正如其名,支持选择性重 发分组,即那些确实丢失的分组。在选择重传协议中,发送窗口大于1,接收窗口大于1。 选择重传协议规则是加大接收窗口,先收下发送序号不连续但仍处在接收窗口中的那些 数据分组。等到所缺序号的数据分组收到后再一并送交主机。 选择重传协议可避免重复传送那些本来已经正确到达接收端的数据分组,但我们付 出的代价是在接收端要设置具有相当容量的缓存空间。 3.点到点信道的数据链路层 4 广域网一般最多包括OSI 参考模型的下三层,网络层提供的服务有虚电路和数据报 服务,数据链路层协议有PPP 、HDLC 和帧中继等,PPP 协议占有绝对优势。 102 计算机网络教程 现在我们讨论点对点链路的数据链路层协议,即点对点协议(Point-to-Point Protocol,PPP )。这种链路提供全双工操作,并按照顺序传递数据包。设计目的主要是用 来通过拨号或专线方式建立点对点连接发送数据,使其成为各种主机、网桥和路由器之间 简单连接的一种共通的解决方案。使用拨号电话线接入It采用PPP协议,如图3. nterne13 所示。 图3.13 用户采用PPP协议接入Internet PPP协议是Inent工程任务组(nentEngnigTsocIETF) treItreiernakFre,推出的一 种适用于点到点连接的数据链路控制协议,是一种正式的Internet数据链路层协议标准, 该协议在RFC1661 、RFC1662和RFC1663中进行了描述。PPP协议有三个组成部分: 组帧即一个将IP数据报封装到串行链路的方法;一个用来建立、维护和拆除数据链路连 接的链路控制协议(LinkControlProtocol,LCP);一套网络控制协议(NetworkControl Protocol,NCP)族,PPP允许多个网络协议共用一个链路,网络控制协议(NCP)负责连接 PPP(第二层)和网络协议(第三层)。对于所使用的每个网络层协议,PPP都分别使用独 ( 立的NCP来连接。例如,IP使用IP控制协议(IPX使用NolIPX控制协议 IPXCP )。 IPCP),ve 3.4.1 功能 (1)PPP具有动态分配IP地址的能力,允许在连接时刻协商IP地址。 (2)PPP支持多种网络协议,比如TCP/IP 、NetBEUI 、NWLINK等。 (3)PPP协议只检错不纠错。 (4)PPP具有身份验证功能。 (5)PPP可以用于多种类型的物理介质上,包括串口线、电话线、移动电话和光纤(例 如SDH),PPP也用于Internet接入。 3.4.2 PPP 帧填充方式 1.帧格式各字段的含义 PPP协议的帧格式如图3. 14所示。 标志字段F为0x7E(符号“0x”表示后面的字符是用十六进制表示。十六进制的7E 的二进制表示是01111110),每个PPP帧都是以01111110的1字节标志字段来作为开始 和结束。 第 3 章　数据链路层 103 图3. 14 PPP 的帧格式 地址字段A只置为0xFF,地址字段实际上并不起作用。 控制字段C通常置为0x03,表明这是一个无序号帧,即意味着:在默认方式下,PPP 并没有采用序号和确认来实现可靠的传输。 PPP是面向字节的,所有的PPP帧的长度都是整数字节。 PPP有一个2字节的协议字段:当协议字段为0x0021时,PPP帧的信息字段就是 IP数据报。若为0xC021,则信息字段是PPP链路控制数据。若为0x8021,则表示这是 网络控制数据。 信息字段的长度是可变的,不超过1500字节。 2.比特填充 当PPP用在同步传输链路时,协议规定通常采用硬件来完成比特填充,采用零比特 填充实现透明传输。 采用零比特填充法使信息字段不会出现6个连续1。在发送端,当一串比特流数据 中有5个连续1时,就立即填入一个0。在接收帧时,每当发现5个连续1时,就将其后 的一个0删除,以还原成原来的比特流。 例如,比特流“011111011111110…”的输出位流模式为“01111100111110110…”,当接 收方收到“01111100111110110…”时,则自动删除连续5个输入位“1”后的位“0,(”) 即将输 入流还原成“011111011111110…” 。 3.字符填充 当PPP用在异步传输时,就使用一种特殊的字符填充法。字符填充法是将信息字段 中出现的每一个0x7E字节转变成为2字节序列(0x7D;0x5E )。若信息字段中出现一个 0x7D的字节;则将其转变成为2字节序列(0x7D;0x5D )。若信息字段中出现ASCI 码 的控制字符(即数值小于0x20的字符),则在该字符前面要加入一个0x7D字节,同时将 该字符的编码加以改变。 PPP协议之所以不使用序号和确认机制是出于以下的考虑:在数据链路层出现差错 的概率不大时,使用比较简单的PPP协议较为合理;在Internet环境下,PPP的信息字段 放入的数据是IP数据报。数据链路层的可靠传输并不能够保证网络层的传输也是可靠 的;帧检验序列FCS字段可保证无差错接受。 3.4.3 身份认证模式 有两种身份认证模式:一种是PAP,一种是CHAP 。相对来说PAP的认证方式安全 性没有CHAP高。PAP在传输pasword是明文的,而CHAP在传输过程中不传输密 104 计算机网络教程 码,取代密码的是hash(哈希值)。PAP 认证是通过两次握手实现的,而CHAP 则是通过 三次握手实现的。PAP 认证是被叫提出连接请求,主叫响应。而CHAP 则是主叫发出 请求,被叫回复一个数据包,这个包里面有主叫发送的随机的哈希值,主叫在数据库中确 认无误后发送一个连接成功的数据包连接。 3.4.4 PPP 的工作过程 PPP 协议的工作过程如下。 (1)当用户拨号接入ISP 后,就建立了一条从用户PC 到ISP 的物理连接。 (2)这时用户PC 向ISP 发送一系列的LCP 分组(封装成多个PPP 帧), 以便建立 LCP 连接。这些分组及其响应选择了将要使用的一些PPP 参数。 (3)协商结束后就进入鉴别状态。若通信的双方鉴别身份成功,则进入网络层协议 状态。 (4)接着还要进行网络层配置,NCP 给新接入的用户PC 分配一个临时的IP 地址。 这样,用户PC 就成为Internet上的一个有IP 地址的主机了。 (5)当用户通信完毕时,NCP 释放网络层连接,收回原来分配出去的IP 地址。接着, LCP 释放数据链路层连接。最后释放的是物理层的连接。 注:PPP 链路的起始和终止状态永远是“链路静止”(LinkDead)状态,这时在PC 和 ISP 的路由器之间并不存在物理层的连接。 图3.到 15 的右边方框是对PPP 协议的几个状态的说明。从设备之间无链路开始, 先建立物理链路,再建立链路控制协议LCP 链路。经过鉴别后再建立网络控制协议 NCP 链路,然后才能交换数据。由此可见,PPP 协议已不是纯粹的数据链路层的协议,它 还包含了物理层和网络层的内容。 图3. 15 PPP 协议的工作流程和工作状态 第 3 章　数据链路层 105 3.广播信道的数据链路层 5 广播信道使用一对多的广播通信方式,同一信道上连接的主机很多。以太网起源于 20世纪70年代,是目前使用最为广泛的局域网。 3.5.1 局域网概述 目前,全球范围内局域网(LocalAreaNetwork,LAN)的数量远超广域网。局域网已 经从低速向高速,从共享式向交换式,从半双工式向全双工式发展与进步。通常把局域网 定义为:在较小的地理范围内,局域网主要利用通信线路将办公室、企业、校园、小区等较 小区域内的计算机、网络通信设备等连接在一起,配以接口和高层软件,进行高速数据传 输和软硬件资源共享的系统。 1.局域网的特点 局域网的特点主要有以下几点: (1)通常为一个单位拥有,地理范围有限,站点数量有限。 (2)所有的站点共享较高的总带宽。 (3)较高的时延和较低的误码率。 (4)支持几种传输介质,包括双绞线、同轴电缆、光纤和无线介质等。 (5)拓扑结构简单,主要有总线型、环型、星型结构等。 2.局域网的体系结构 由于局域网大多采用共享信道,当通信局限于一个局域网内部时,任意两个结点之间 都有唯一的链路,即网络层的功能可由链路层来完成,所以局域网中不单独设立网络层。 IEEE802提出的局域网参考模型(LAN/RM)如图3. 16所示。 图3.I参考模型的对应关系 16 IEEE802参考模型与OS 与OSI参考模型相比,局域网的参考模型就只相当于OSI的最低两层。为了使数据 链路层能更好地适应多种局域网标准, IEEE802委员会就将局域网的数据链路层拆成逻 辑链路控制LLC(LogicalLinkControl)子层和媒体接入控制MAC(MediumAces 106 计算机网络教程 Control)子层两个子层,与接入到传输媒体有关的内容都放在MAC 子层,而LLC 子层 则与传输媒体无关,不管采用何种协议的局域网对LLC 子层来说都是透明的。由于 TCP/IP 体系经常使用的局域网是DIXEthernetV2 而不是IEEE802. 3标准中的几种 局域网,因此现在IEEE802 委员会制定的逻辑链路控制子层LLC( 2标准) 即IEEE802. 的作用已经不大了。很多厂商生产的适配器上就仅装有MAC 协议而没有LLC 协议。 3.5.2 以太网 以太网(Ethernet)指的是由Xerox公司创建并由Xerox、Intel和DEC 公司联合开发 的基带局域网规范。1982 年12 月,3标准, IEEE 公布了与以太网规范兼容的IEEE802. 它们的出现标志着以太网技术标准的起步,为符合国际标准、具有高度互通性的以太网产 品的面世奠定了基础。 通常我们所说的以太网主要是指以下三种不同的局域网技术。 (1)10Mb/s以太网,又称为标准以太网、传统以太网。采用同轴电缆作为网络媒 体,传输速率达到10Mb/s。 (2)100Mb/s以太网,又称为快速以太网。采用双绞线作为网络媒体,传输速率达 到100Mb/s。 (3)1000Mb/s以太网,又称为千兆以太网。采用光缆或双绞线作为网络媒体,传输 速率达到1000Mb/s。 以太网跨越数据链路层和物理层,有许多不同的以太网标准,它们有不同的速率 (2Mb/s、10Mb/s、100Mb/s、1Gb/s、10Gb/s)、不同的物理层媒体,但它们有共同的MAC 协议和帧格式。 由于以太网结构简单、组网容易、建网成本低、扩充方便,一出现就受到业界的普遍欢 迎而迅速发展起来,在很大程度上逐步取代了其他局域网标准。如当时比较流行的令牌 环、FDDI 和ARCNET 都逐渐被以太网淘汰。目前以太网成为局域网技术的主流技术。 1. 以太网工作原理 以太网是一种以总线方式连接、广播式传输的网络,所有站点通过共享总线实现数据 传输,一个站发出的数据帧,所有的站都能收到,这种工作方式带来了冲突问题,需要采用 相应的介质访问控制方式解决。以太网采用带有冲突检测的载波侦听多路访问(CSMA/ CD)协议实现介质访问控制,在IEEE802 标准中,3标准。以太 以太网标准为IEEE802. 网结构示意图如图3. 17 所示。 10Base-5以太网与10Base-2以太网缺点很多,因此在1990 年,IEEE 发布了新的以 太网标准,这就是10Base-T以太网。10Base-T以太网有两项革命性的改进,一是用双绞 线代替同轴电缆,二是用星型拓扑结构代替总线型拓扑结构,这在以太网的发展史上有里 程碑性的意义。经此改进,以太网安装简单、设备价格低廉、故障易于定位,为以太网战胜 其他局域网奠定了牢固的基础。“10”与“Base”的含义与“10Base-5以(”) 太网相同,“T”表示 传输介质使用双绞线。 10Base-T以太网的传输媒介质使用3类非屏蔽双绞线,更好的双绞线当然也可以。 与同轴电缆与T型头相比,双绞线与RJ-45 头的价格低廉,连接简单;同轴电缆中只有一 第 3 章　数据链路层 107 图3.以太网结构示意图 17 个电回路,不能进行全双工通信,而双绞线里面有8根电线,两根构成发送电回路,另两根 构成接收电回路,可以全双工通信。10Base-T以太网中每根双绞线最长为100m,再长时 信号衰减严重,可能无法正确接收, 18 所示。 如图3. 图3.aeT 18 10Bs 以太网通常使用专门的网络接口卡或通过系统主电路板上的电路实现。以太网使用 收发器与网络媒体进行连接。收发器可以完成多种物理层功能,其中包括对网络碰撞进 行检测。收发器可以作为独立的设备通过电缆与终端站连接,也可以直接被集成到终端 站的网卡中。 以太网采用广播机制,所有与网络连接的工作站都可以看到网络上传递的数据。通 过查看包含在帧中的目标地址,确定是否进行接收或放弃。如果证明数据确实是发给自 己的,工作站将会接收数据并传递给高层协议进行处理。 作为一种基于竞争机制的网络环境,以太网允许任何一台网络设备在网络空闲时发 送信息。因为没有任何集中式的管理措施,所以很有可能出现多台工作站同时检测到网 络处于空闲状态,进而同时向网络发送数据的情况。这时,发出的信息会相互碰撞而导致 损坏。工作站必须等待一段时间之后,重新发送数据。补偿算法用来决定发生碰撞后,工 作站应当在何时重新发送数据帧。 2. 以太网标准 1982 年2月,3规范,s以太网的标准。 IEEE 推出了IEEE802.这是最早的10Mb/ 1995 年3月,3u规范,s的速率运行 IEEE 通过了IEEE802.这是一个关于以100Mb/ 的快速以太网的规范。