计算机网络：数据链路层

第三章数据链路层13.1数据链路层基本概念

3.1.1数据链路层概述数据链路层的最基本功能是将物理层提供的原始传送比特流可能出错的物理连接改造成为逻辑上无差错的数据链路。链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。一条链路只是一条通路的一个组成部分。数据链路(datalink)除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。2数据链路层像个数字管道常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧(frame)。物理层传送比特流，物理传输媒体传送的是信号早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。结点结点帧帧343.1.2数据链路层功能数据链路层中位于第二层，它在物理层提供服务的基础上向网络层提供服务。数据链路层可以在物理链路上提供可靠的数据传输服务。数据链路层的信息传送机制是利用物理层提供的物理通路，首先在相邻节点之间建立数据链路，然后把将要传送的数据组装成帧，并加入应答、差错控制、流量控制信息，使有差错的物理线路变成无差错的数据链路，从而为网络层提供可靠的信息。5数据链路层的主要功能(1)帧同步(帧定界)(2)差错控制：1.前向纠错2.差错检测(3)流量控制滑动窗口协议集帧确认、流量控制、差错控制于一身，得到广泛应用。(4)链路管理(5)寻址(6)将数据和控制信息区分开(7)透明传输：透明传输是指数据都应当能够在链路上传送，不管所传送的数据是什么样的比特组合。63.2帧与成帧引入帧机制是为了实现相邻结点之间的可靠传输以及提高数据传输的效率。当发现接收到的某一个（或几个）比特出错时，可以只对相应的帧进行特殊处理（如请求重发等），而不需要对其他未出错的帧进行这种处理；如果发现某一帧被丢失，也只需请求发送方重传所丢失的帧，这样就大大提高了数据处理和传输的效率。引入帧机制后，发送方的数据链路层必须提供从网络层接收的分组（Packet）封装成帧的功能，即为来自上层的分组加上必要的帧头和帧尾部分，通常称此为成帧(Framing)而接收方数据链路层则必须提供将帧重新拆装成分组的拆帧功能，即去掉发送端数据链路层所加的帧头和帧尾部分，从中分离出网络层所需的分组。73.2.1帧的基本格式不同的数据链路层协议给出的帧格式基本相同通常数据字段之前的所有字段被统称为帧头部分，而数据字段之后的所有字段被称为帧尾部分。83.2.2成帧与拆帧成帧是将上一层的传输单元（分组）加上帧头和帧尾，组装成数据链路层的传输单元——帧的过程。发送端的数据链路层接收到网络层的发送请求之后，从网络层与数据链路层之间的接口处取下待发送的分组，并封装成帧，然后经过其下层物理层送入传输信道，这样不断地将帧送入传输信道就形成了连续的比特流。拆帧是将对方物理层传送来的比特流信息除去帧头和帧尾，还原为分组的过程。接收端的数据链路层从来自其物理层的比特流中识别出每一个的独立帧，然后利用帧中的FCS字段对每一个帧进行校验，判断是否有错误。如果没有错误，就对帧实施拆封，并将其中的数据部分即分组通过数据链路层与网络层之间的接口上交给网络层，从而完成了相邻节点的数据链路层拆帧的任务。93.2.3帧的定界帧定界就是标识帧的开始与结束。帧定界有四种常见的方法：(1)字符计数法。这种方法是在帧头部中使用一个字符计数字段来标明帧内字符数。例如，发送序列“5

ABCDE4

UVWX

7

1234458”表示一共有三个帧，三个帧的长度分别为5字节、4字节和7字节。但是这种方法很容易出现定界错误。假如计数值出现传输差错，接收端收到的序列为“5ABCDE6UVWX71234458”时，则接收端会将第二帧解释为“6UVWX71”，从而导致因发收双方对帧大小和内容理解不一致而出错。10(2)带字符填充的首尾界符法。这种方法是在每一帧的开头加上ASCII字符“DLE

STX”，在帧末尾加上ASCII字符“DLEETX”。例如，假设待发送的数据是ADLECB，则在数据链路层封装的帧为：

DLESTXADLECBDLEETX

如果发送方在数据帧中遇到帧头或者帧尾字符，就采用字符填充法来处理。例如，数据帧有DLE字符，就在其前面加一个DLE。

DLESTXADLE

DLECBDLEETX11如果接收方在接收到的数据帧中遇到单个DLE，就断定是帧边界；若遇到成对出现的DLE，则认为是数据，并去掉前面的一个DLE。

这种方法的缺点是当需要发送的数据中包含很多的DLE字符时，帧中会出现大量冗余DLE。12(3)带位填充的首尾标志法（零比特填充法）。这种方法是用一个特殊的位模式“01111110”作为帧边界。数据中可能包含“01111110”数据，如何判断？采用零比特填充法使一帧中两个边界字段之间的数据不会出现6个连续1。在发送端，当一串比特流数据中有5个连续1时，就立即填入一个0。如此保证数据部分不会出现6个连续的1在接收帧时，先找到边界字段以确定帧的边界。接着再对比特流进行扫描。每当发现5个连续1时，就将其后的一个0删除，以还原成原来的比特流。13零比特填充法14(4)物理层编码违例法物理层编码违例法就是利用物理层信息编码中未用的电信号来作为帧的边界。例如，用曼彻斯特编码，在传输之前，将数据位1编码成高－低电平对，数据位0编码成低－高电平对。那么高－高电平、低－低电平就可以用作帧的边界。153.3差错检测和纠错方法

3.3.1差错产生的原因差错是指接收端收到的数据与发送端实际发出的数据出现不一致的现象。差错的产生主要是因为在通信线路上有噪声干扰。对差错的处理有两种处理策略：前向纠错或简称为纠错(forwarderrorcorrection)差错检测(errordetecting)163.3.2奇偶校验奇偶校验是在原数据位后附加一个校验位，将其值置为“0”或“1”，使附加在该位后的整个数据码中“1”的个数成为奇数或偶数。使用奇数个“1”进行校验的方案被称为奇校验。对应于偶数个“1”的校验方案被称为偶校验。奇偶校验有三种使用方式，即水平奇偶校验垂直奇偶校验水平垂直奇偶校验。17水平奇偶校验码是指在面向字符的数据传输中，在每个字符的7位信息码后附加一个校验位“0”或“1”18垂直奇偶校验垂直奇偶校验是将所发送的若干个字符组成字符组或字符块，形式上相当于是一个矩阵，每行为一个字符，每列为所有字符对应的相同位。在这一组字符的未尾即最后一行附加一个校验字符，该校验字符中的第i位分别对应组中所有字符第i位的校验位。19水平垂直奇偶校验方法203.3.3海明码海明码(HammingCode)编码的关键是使用多余的奇偶校验位来识别一位错误。假设信息码共有n

位，海明码共有h

位，那么总共的码长为n+h

位。为能检测出n+h

位编码中其中一位的错误，海明码必须能够表示至少n+h+1

种状态，其中n+h

种表示n+h位编码中有一位错误，另外还需要1种来表示整个编码正确无误。则海明码的长度需要满足下列关系：2h>=n+h+1以4位信息位为例，由可以看出需要的海明码长度为3。

21码字(CodeWord)按如下方法1、把所有2的幂次方的数据位标记为奇偶校验位(编号为1,2,4,8,16,32,64等的位置)2、其他数据位用于待编码数据.(编号为3,5,6,7,9,10,11,12,13,14,15,17等的位置)3、每个奇偶校验位的值代表了码字中部分数据位的奇偶性，其所在位置决定了要校验和跳过的比特位顺序。位置1：校验1位，跳过1位，校验1位，跳过1位(1,3,5,7,9,11,13,15,…)位置2：校验2位，跳过2位，校验2位，跳过2位(2,3,6,7,10,11,14,15,…)位置4：校验4位，跳过4位，校验4位，跳过4位(4,5,6,7,12,13,14,15,20,21,22,23,…)位置8：校验8位，跳过8位，校验8位，跳过8位(8~15,24~31,40~47,…)22则4位信息码时，海明码的位置为20，21，22。即H1,H2,H423已知：信息码为：“11001100”(k=8)。求：海明码码字解：(1)把冗余码A、B、C、…，顺序插入信息码中，得海明码

码字:“A

B1C100D11

0

0”

码位:123456789101112

其中A,B,C,D分别插于2k位(k=0,1,2,3)。码位分别为1,2,4,8。24(2)冗余码A,B,C,D的线性码位是：(相当于监督关系式)

A->1,3,5,7,9,11；

B->2,3,6,7,10,11；

C->4,5,6,7,12；(注5=4+1；6=4+2；7=4+2+1；12=8+4)D->8,9,10,11,12。(3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：码字:“A

B1C100D11

0

0”

A=∑(0,1,1,0,1,0)=1

B=∑(0,1,0,0,1,0)=0

C=∑(0,1,0,0,0)

=1

D=∑(0,1,1,0,0)

=0(4)最终编码为:"101110001100"

25例已知：接收的码字为：“100110001100”(k=8)

求：发送端的信息码。解：1)设错误累加器(err)初值=0

2)求出冗余码的偶校验和，并按码位累加到err中：

A=∑(1,0,1,0,1,0)=1

err=err+20=1

B=∑(0,0,0,0,1,0)=1

err=err+21=3

C=∑(1,1,0,0,0)

=0

err=err+0=3

D=∑(0,1,1,0,0)

=0

err=err+0=3

由err≠0可知接收码字有错，

26

3)码字的错误位置就是错误累加器(err)的值3。

4)纠错--对码字的第3位值取反得正确码字：

"101110001100"

5)把位于2k位的冗余码删除得信息码："11001100"273.3.4循环冗余检验的原理在数据链路层传送的帧中，广泛使用了循环冗余检验CRC的检错技术。假设待传送的数据M=1010001101（共kbit）。我们在M的后面再添加供差错检测用的nbit

冗余码一起发送。28冗余码的计算选定生成多项式，其对应(n+1)bit的数Px5+x4+x2+x0对应

P=110101用二进制的模

2

运算进行2n乘M的运算，这相当于在M后面添加n个0。得到的(k+n)bit的数除以事先选定好的长度为(n+1)bit的数P，得出商是Q而余数是R，余数R比除数P至少要少1个比特。29

1101010110

←

Q

商

除数

P→

110101101000110100000

←

2nM被除数

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余数30设

n=5,P=110101，模2运算的结果是：商Q=1101010110，余数R=01110。(R为5bit)将余数R作为冗余码添加在数据M的后面发送出去，即发送的数据是101000110101110，或者说2nM+R。31检测出差错只要得出的余数R不为0，就表示检测到了差错。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。32三个生成多项式国际标准

CRC-12：x12+x11+x3+x2+x1+1用于字符长度为6位CRC-16：x16+x15+x2+1用于字符长度为8位CRC-CCITT：x16+x12+x5+1用于字符长度为8位CRC-32：x32+x26+x23+x22+x16+x12+x11+x10+x8 +x7+x5+x4+x2+x1+133练习(1)已知：信息码:110011信息多项式:K(X)=X5+X4+X+1

生成码:11001

生成多项式:G(X)=X4+X3+1(r=4)

求：循环冗余码和码字。(2)已知：接收码字:1100111001多项式:T(X)=X9+X8+X5+X4+X3+1

生成码:

11001

生成多项式:G(X)=X4+X3+1(r=4)

求：码字的正确性。若正确，则指出冗余码和信息码。

34已知：信息码:110011信息多项式:K(X)=X5+X4+X+1

生成码:11001

生成多项式:G(X)=X4+X3+1(r=4)

求：循环冗余码和码字。

解：1)(X5+X4+X+1)*X4的积是X9+X8+X5+X4

对应的码是1100110000。

2)由计算结果知冗余码是1001，码字就是1100111001。

100001←Q(X)

G(x)→11001)1100110000←F(X)*Xr

11001，

10000

11001

1001←R(X)(冗余码)35(2)已知：接收码字:1100111001多项式:T(X)=X9+X8+X5+X4+X3+1

生成码:

11001

生成多项式:G(X)=X4+X3+1(r=4)

求：码字的正确性。若正确，则指出冗余码和信息码。

解：1)用字码除以生成码，余数为0，所以码字正确。

100001←Q(X)

G(x)→11001)1100111001←F(X)*Xr＋R(x)

11001，

11001

11001

0←S(X)(余数)

2)因r=4，所以冗余码是：11001，信息码是:110011363.4数据链路协议

3.4.1停止等待协议停止等待协议是实现可靠传输的一个简单的协议可靠传输

无差错、按序、无丢失、无重复的数据传输完全理想化的数据传输所基于的两个假定假定1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定2：不管发送方以多快的速率发送数据，接收方总是来得及收下，并及时上交主机这个假定就相当于认为：接收端接收并向主机交付数据的速率永远不会低于发送端发送数据的速率。37具有最简单流量控制的数据链路层协议现在去掉上述的第二个假定。但是，仍然保留第一个假定，即主机A向主机B传输数据的信道仍然是无差错无丢失的理想信道。然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。由收方控制发方的数据流，乃是计算机网络中流量控制的一个基本方法。38具有最简单流量控制的

数据链路层协议算法(发送方)在发送结点：(1)从主机取一个数据帧(给网络层的数据报加上控制信息构成数据帧)。(2)将数据帧送到数据链路层的发送缓存。(3)将发送缓存中的数据帧发送出去。(4)等待。(5)若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到(2)。39具有最简单流量控制的

数据链路层协议算法(接收方)在接收结点：(1)等待。(2)若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。(3)将接收缓存中的数据帧上交主机。(4)向发送结点发一信息，表示数据帧已经上交给主机。(5)转到(1)。40两种情况的对比（传输均无差错）ABDATADATADATADATA送主机B送主机B送主机B送主机BABDATA送主机BDATA送主机B时间不需要流量控制需要流量控制413.4.3实用的停止等待协议建立在不可靠信道上的可靠数据传输：可靠数据传输是建立在ARQ(Automatic

RepeatreQuest–自动重复请求)协议之上的。ARQ协议的3种功能：错误检测接收方反馈发送方重传42时间ABDATA0送主机ACKDATA1送主机ACK(a)正常情况ABDATA0DATA0送主机ACK(c)数据帧丢失重传tout丢失！ABDATA0送主机ACKDATA0丢弃ACK(d)确认帧丢失重传tout丢失！ABDATA0NAKDATA0送主机ACK(b)数据帧出错重传出错43停止等待协议可靠传输机制的工作原理发送方等待接收方发送的确认帧实现流量控制，防止因接收方缓冲区溢出造成的帧丢失。接收方使用循环冗余校验和发送否认帧，发送方重传，实现了差错控制超时重传解决帧丢失的问题帧序号的使用解决帧重复的问题可靠传输机制：确认、校验、顺序号、超时/重传44错误1：数据帧出错等待下层调用收到一个有比特错误的数据帧，则向发送方发送NAK收到一个正确的数据帧，则向发送方发送ACK接收方发送方等待上层调用等待ACK或NAK向接收方发送一帧收到否认帧NAK向接收方重传该帧收到确认帧ACK45无比特差错时发送方与接收方的配合收到确认帧ACK收到否认帧NAK向接收方重传该帧发送方等待上层调用等待ACK或NCK向接收方发送一帧收到一个有帧比特错误的数据帧，则向发送方发送NAK等待下层调用收到一个正确的数据帧，则向发送方发送ACK接收方46数据帧比特差错向接收方发送一帧收到否认帧NAK向接收方重传该帧收到一个有帧比特错误的数据帧，则向发送方发送NAK发送方等待上层调用等待ACK或NCK收到确认帧ACK等待下层调用收到一个正确的数据帧，则向发送方发送ACK接收方47错误2：数据帧丢失向接收方发送一帧启动超时计时器发送方等待上层调用等待ACK或NAK收到否认帧NAK向接收方重传该帧收到确认帧ACK超时则重传该帧等待下层调用收到一个有帧比特错误的数据帧，则向发送方发送NAK收到一个正确的数据帧，则向发送方发送ACK接收方48超时计时器的作用结点A发送完一个数据帧时，就启动一个超时计时器(timeouttimer)。计时器又称为定时器。若到了超时计时器所设置的重传时间tout而仍收不到结点B的任何确认帧，则结点A就重传前面所发送的这一数据帧。一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。49简单的重传出现的问题发送方sendpkt(超时)resendpktrecvACKsendpkt接收方recv

pktsendACKrecv

pkt?(新的帧还是重发的帧？)50错误3：重复帧或者确认帧丢失发送方收不到确认帧，却无法判断是数据帧丢失，RTT太大、还是确认帧丢失等原因。唯一能做的就是重传数据，由此可能造成重复帧。问题接收方无法知道当前收到的帧是新的帧还是重传的上一个帧。发送方收到ACK(NAK)时如何知道这是接收方对最近一帧的确认还是延迟到达的对以前的帧的确认呢？51解决重复帧的问题使每一个数据帧带上不同的发送序号(顺序号)。每发送一个新的数据帧就把它的发送序号加1。若结点B收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧。但此时结点B还必须向A发送确认帧ACK，因为B已经知道A可能没有收到上一次发过去的确认帧ACK。补充：接收方为了表明是对哪个数据帧的确认，给确认帧ACK以编号。52帧的编号问题任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。序号占用的比特数越少，数据传输的额外开销就越小。

对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。一个比特可表示0和1两种不同的序号。数据帧中的发送序号N(S)以0和1交替的方式出现在数据帧中。每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。53发送方等待上层调用等待上层调用等待ACK0等待ACK1发送pkt0启动计时器收到ACK0超时则重发pkt0启动计时器收到ACK1发送pkt1启动计时器收到ACK1收到ACK0超时则重发pkt1启动计时器54按照习惯的表示法，ACKn

表示“第

n–1

号帧已经收到，现在期望接收第

n

号帧”。ACK1表示“0

号帧已收到，现在期望接收的下一帧是

1

号帧”；ACK0

表示“1

号帧已收到，现在期望接收的下一帧是0号帧”。55接收方等待pkt0等待pkt1

收到pkt1则发送ACK0

收到pkt0则发送ACK1

收到pkt0则发送ACK1收到pkt1则发送ACK056可靠传输虽然物理层在传输比特时会出现差错，但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可以提供可靠传输的服务。57停止等待协议的算法这里不使用否认帧（实用的数据链路层协议大都是这样的），而且确认帧带有序号n。按照习惯的表示法，ACKn

表示“第

n–1

号帧已经收到，现在期望接收第

n

号帧”。ACK1表示“0

号帧已收到，现在期望接收的下一帧是

1

号帧”；ACK0

表示“1

号帧已收到，现在期望接收的下一帧是0号帧”。58在发送结点(1)从主机取一个数据帧，送交发送缓存。(2)V(S)←0。(3)N(S)←V(S)。(4)将发送缓存中的数据帧发送出去。(5)设置超时计时器。(6)等待。{等待以下(7)和(8)这两个事件中最先出现的一个}(7)收到确认帧ACKn，若n=1–V(s)，则：从主机取一个新的数据帧，放入发送缓存；

V(S)←[1

V(S)]，转到(3)。否则，丢弃这个确认帧，转到(6)。(8)若超时计时器时间到，则转到(4)。59在接收结点(1)V(R)←0。(2)等待。(3)收到一个数据帧；若N(S)=V(R)，则执行(4)；否则丢弃此数据帧，然后转到(6)。(4)将收到的数据帧中的数据部分送交上层软件（也就是数据链路层模型中的主机）。(5)V(R)←[1

V(R)]。(6)n←V(R)；发送确认帧ACKn，转到(2)。60停止等待协议的要点只有收到序号正确的确认帧

ACKn

后，才更新发送状态变量

V(S)一次，并发送新的数据帧。接收端接收到数据帧时，就要将发送序号

N(S)

与本地的接收状态变量

V(R)

相比较。若二者相等就表明是新的数据帧，就收下，并发送确认。否则为重复帧，就必须丢弃。但这时仍须向发送端发送确认帧

ACKn，而接收状态变量

V(R)

和确认序号

n

都不变。

连续出现相同发送序号的数据帧，表明发送端进行了超时重传。连续出现相同序号的确认帧，表明接收端收到了重复帧。61发送端在发送完数据帧时，必须在其发送缓存中暂时保留这个数据帧的副本。这样才能在出差错时进行重传。只有确认对方已经收到这个数据帧时，才可以清除这个副本。发送端对出错的数据帧进行重传是自动进行的，因而这种差错控制体制常简称为ARQ(AutomaticRepeatreQuest)，直译是自动重传请求，但意思是自动请求重传。停止等待协议即停止等待ARQ协议。62停止等待协议中数据帧和

确认帧的发送时间关系ABDATADATAACK传播时延tp处理时间tpr确认帧发送时间ta传播时延tp处理时间tprtT时间两个成功发送的数据帧之间的最小时间间隔数据帧的发送时间tf设置的重传时间tout63停止等待协议的优缺点优点：比较简单。缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。为了克服这一缺点，就产生了另外两种协议，即连续ARQ和选择重传ARQ。643.4.2回退N帧协议

1.连续ARQ协议的工作原理

在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。由于减少了等待时间，整个通信的吞吐量就提高了。65连续ARQ协议的工作原理DATA0DATA1DATA2DATA3DATA4DATA5重传DATA2重传DATA3ACK1ACK2ACK1确认DATA0ACK2确认DATA1DATA2出错，丢弃DATA3不按序，丢弃，重传ACK2DATA4不按序，丢弃，重传ACK2DATA5不按序，丢弃，重传ACK2ACK3ACK3确认DATA2ACK4确认DATA3ACK4重传DATA5重传DATA4超时重传时间ABtout送交主机送交主机…??ACK2ACK2ACK266需要注意：(1)接收端只按序接收数据帧。虽然在有差错的2号帧之后接着又收到了正确的3个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个2号帧还没有收到。虽然丢弃了这些不按序的无差错帧，但应重复发送已发送过的最后一个确认帧（防止确认帧丢失）。(2)ACK1表示确认0号帧DATA0，并期望下次收到1号帧；ACK2表示确认1号帧DATA1，并期望下次收到2号帧。依此类推。67(3)结点A在每发送完一个数据帧时都要设置该帧的超时计时器。如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。在等不到2号帧的确认而重传2号数据帧时，虽然结点A已经发完了5号帧，但仍必须向回走，将2号帧及其以后的各帧全部进行重传。连续ARQ

又称为Go-back-NARQ，意思是当出现差错必须重传时，要向回走N个帧，然后再开始重传。

连续ARQ协议又称为GBN协议。68滑动窗口的概念在使用连续ARQ协议时，如果发送端一直没有受到对方的确认信息，那么实际上发送端并不能无限制的发送其数据。这是因为？当未被确认的数据帧的数目太多时，只要有一帧出了差错，就要有很多的数据帧需要重传，这必然浪费很多时间。另外为了对所发送的大量数据帧进行编号，每个数据帧的发送序号也要占用较多的比特数，这样又增加了一些不必要的开销。因此，在连续ARQ协议中必须将已发送出去、但未被确认的数据帧的数目加以限制。6901234567012发送窗口WT不允许发送这些帧允许发送5个帧(a)01234567012不允许发送这些帧还允许发送4个帧WT已发送(b)01234567012不允许发送这些帧WT已发送(c)01234567012不允许发送这些帧还允许发送

3个帧WT已发送已发送并已收到确认(d)70发送端的发送窗口：还没有收到对方确认信息的情况下发送端可以连续发送的数据帧的序号范围。发送窗口的大小

WT

代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。发送窗口用来对发送端进行流量控制。停止等待ARQ协议可以看成发送窗口大小为1的连续ARQ协议的特例。71接收端可以连续收到好几个正确的帧以后才发一个确认(累积确认)，或者在自己要发送数据时捎带确认信息。接收端的接收窗口：决定可以接收的数据帧的序号范围。接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。在连续ARQ协议中，接收窗口的大小WR=1。只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。每收到一个序号正确的帧，接收窗口就向前(即向右方)滑动一个帧的位置。同时发送对该帧的确认。接收端设置接收窗口72不允许接收这些帧01234567012WR准备接收0号帧(a)不允许接收这些帧01234567012WR准备接收

1号帧已收到(b)不允许接收这些帧01234567012WR准备接收4号帧已收到(c)73滑动窗口的重要特性只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。收发两端的窗口按照以上规律不断地向前滑动，因此这种协议(GBN协议)又称为滑动窗口协议。当发送窗口和接收窗口的大小都等于1时，就是停止等待协议。当用n个比特进行编号时，若接收窗口的大小为1，则只有在发送窗口的大小WT

2n1时，连续ARQ协议才能正确运行。例如，当采用3bit编码时，发送窗口的最大值是7而不是8。74可靠的数据传输提供的技术校验顺序号确认超时/重传753.4.2选择性重传协议（SelectiveRepeat）接收窗口>1可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。选择重传ARQ协议可避免重复传送那些本来已经正确到达接收端的数据帧。但我们付出的代价是在接收端要设置具有相当容量的缓存空间。对于选择重传ARQ协议，若用n

比特进行编号，则接收窗口的最大值受下式的约束

WR

2n/2

76773.5数据链路层协议实例

3.5.1高级数据链路控制HDLC高级数据链路控制（规程）（HighLevelDataLinkControl，HDLC）是一个在同步网上传输数据、面向比特的数据链路层协议，它是由国际标准化组织（ISO）制订的。面向字符在链路上传输的数据必须是特定字符集的字符组成的，链路上的控制信息也必须是一个字符集中若干指定的控制字符构成的。面向比特链路上能够传输任意比特组合的数据78面向字符和面向比特79标志字段F(Flag)为6个连续1加上两边各一个0共8bit(0x7E)。在接收端只要找到标志字段就可确定一个帧的位置。地址字段A是8bit。帧检验序列FCS字段共16bit。所检验的范围是从地址字段的第一个比特起，到信息字段的最末一个比特为止。80零比特的填充与删除数据中某一段比特组合恰好出现和F字段一样的情况01001111110001010会被误认为是F字段发送端在5个连1之后填入0比特再发送出去填入0比特010011111010001010在接收端将5个连1之后的0比特删除，恢复原样在此位置删除填入的0比特01001111101000101081透明传输采用零比特填充法就可传送任意组合的比特流，或者说，就可实现数据链路层的透明传输。当连续传输两个帧时，前一个帧的结束标志字段F可以兼作后一帧的起始标志字段。当暂时没有信息传送时，可以连续发送标志字段，使收端可以一直和发端保持同步。82信息帧：第1比特为0；N(S)发送序号；N(R)确认号；探询/终止P/F(Poll/Final)比特。主站发出的帧的P比特置为1表示要求对方立即发送响应，对方确认的帧中若将F比特置为1则表示要发送的数据发送完毕。83监督帧：四种，取决于3~4比特的值无编号帧：没有编号，用5bit(3,4,6,7,8)来表示不同功能的无编号帧。84HDLC连接建立、数据传输和连接拆除853.5.2PPP协议现在全世界使用得最多的数据链路层协议是点对点协议

PPP(Point-to-PointProtocol)。用户使用拨号电话线接入因特网时，一般都使用PPP协议。86PPP协议1992年制订了PPP协议。经过1993年和1994年的修订，现在的PPP协议已成为因特网的正式标准[RFC1661]。PPP协议有三个组成部分一个将IP数据报封装到串行链路的方法。链路控制协议LCP(LinkControlProtocol)。网络控制协议NCP(NetworkControlProtocol)。PPP的帧格式和HDLC的相似。标志字段

F

仍为0x7E（符号“0x”表示后面的字符是用十六进制表示。十六进制的

7E

的二进制表示是01111110）。地址字段

A

只置为0xFF。地址字段实际上并不起作用。控制字段

C

通常置为0x03。PPP是面向字节的，所有的PPP

帧的长度都是整数字节。87PPP协议的帧格式88字符填充法将信息字段中出现的每一个0x7E字节转变成为2字节序列(0x7D,0x5E)。若信息字段中出现一个0x7D的字节,则将其转变成为2字节序列(0x7D,0x5D)。若信息字段中出现ASCII码的控制字符（即数值小于0x20的字符），则在该字符前面要加入一个0x7D字节，同时将该字符的编码加以改变。89不使用序号和确认，不提供可靠传输PPP协议之所以不使用序号和确认机制是出于以下的考虑：在数据链路层出现差错的概率不大时，使用比较简单的PPP协议较为合理。在因特网环境下，PPP的信息字段放入的数据是IP数据报。数据链路层的可靠传输并不能够保证网络层的传输也是可靠的。帧检验序列FCS字段可保证无差错接受。90PPP协议的工作状态当用户拨号接入ISP时，路由器的调制解调器对拨号做出确认，并建立一条物理连接。PC机向路由器发送一系列的LCP分组（封装成多个PPP帧）。这些分组及其响应选择一些PPP参数，接着进行网络层配置，NCP给新接入的PC机分配一个临时的IP地址，使PC机成为因特网上的一个主机。通信完毕时，NCP释放网络层连接，收回原来分配出去的IP地址。接着，LCP释放数据链路层连接。最后释放的是物理层的连接。91923.6数据链路层的设备

3.6.1网桥扩展网络的距离或范围，而且可提高网络的性能、可靠性和安全性。网桥工作在数据链路层，具体说是工作在OSI模型中数据链路层的MAC子层。它将两个局域网（LAN）连起来，根据MAC地址（物理地址）来转发帧。网桥具有过滤帧的功能。当网桥收到一个帧时，并不是向所有的端口转发此帧，而是先检查此帧的目的MAC地址，然后再确定将该帧转发到哪一个端口。931网桥的工作原理94网桥处理帧和建立转发表的算法95网桥应当按照以下算法

处理收到的帧和建立转发表(1)从端口x收到无差错的帧（如有差错即丢弃），在转发表中查找目的站MAC地址。(2)如有，则查找出到此MAC地址应当走的端口d，然后进行(3)，否则转到(5)。(3)如到这个MAC地址去的端口d=x，则丢弃此帧（因为这表示不需要经过网桥进行转发）。否则从端口d转发此帧。(4)转到(6)。(5)向网桥除x以外的所有端口转发此帧（这样做可保证找到目的站）。(6)如源站不在转发表中，则将源站MAC地址加入到转发表，登记该帧进入网桥的端口号，设置计时器。然后转到(8)。如源站在转发表中，则执行(7)。(7)更新计时器。(8)等待新的数据帧。转到(1)。962网桥的分类网桥通常有透明网桥和源路由选择网桥两大类。透明网桥：简单的讲，使用这种网桥，不需要改动硬件和软件，无需设置地址开关，无需装入路由表或参数。只须插入电缆就可以，现有LAN的运行完全不受网桥的任何影响。“透明”是指局域网上的站点并不知道所发送的帧将经过哪几个网桥，因为网桥对各站来说是看不见的。透明网桥采用的算法是逆向学习法(backwardlearning)。网桥按混杂的方式工作，故它能看见所连接的任一LAN上传送的帧。查看源地址即可知道在哪个LAN上可访问哪台机器，于是在散列表中添上一项。97透明网桥使用了支撑树算法这是为了避免产生转发的帧在网络中不断地兜圈子。局域网2局域网1网桥2网桥1

AFF2④F1③不停地兜圈子①②A发出的帧⑤网桥1转发的帧⑥网桥2转发的帧网络资源白白消耗了98透明网桥容易安装，但网络资源的利用不充分。源路由(sourceroute)网桥在发送帧时将详细的路由信息放在帧的首部中。源站以广播方式向欲通信的目的站发送一个发现帧，每个发现帧都记录所经过的路由。发现帧到达目的站时就沿各自的路由返回源站。源站在得知这些路由后，从所有可能的路由中选择出一个最佳路由。凡从该源站向该目的站发送的帧的首部，都必须携带源站所确定的这一路由信息。99特点透明网桥源路由网桥有无连接无连接面向连接透明性完全透明不透明配置方式自动手动路由次优优化学习逆向学习发现帧复杂性在网桥在主机100网桥在转发表中登记以下三个信息站地址：登记收到的帧的源MAC地址。端口：登记收到的帧进入该网桥的端口号。时间：登记收到的帧进入该网桥的时间。转发表中的MAC地址是根据源MAC地址写入的，但在进行转发时是将此MAC地址当作目的地址。如果网桥现在能够从端口x收到从源地址A发来的帧，那么以后就可以从端口x将帧转发到目的地址A。1013网桥的优缺点(与中继器相比)网桥的存储和转发功能与中继器相比有优点也有缺点，其优点是：（1）使用网桥进行互连克服了物理限制，这意味着构成LAN的数据站总数和网段数很容易扩充。（2）网桥纳入存储和转发功能可使其适应于连接使用不同MAC协议的两个LAN。因而构成一个不同LAN混连在一起的混合网络环境。（3）网桥的中继功能仅仅依赖于MAC帧的地址，因而对高层协议完全透明。（4）网桥将一个较大的LAN分成段，有利于改善可靠性、可用性和安全性。102网桥的主要缺点是：由于网桥在执行转发前先接收帧并进行缓冲，与中继器相比会引入更多时延。由于网桥不提供流量控制功能，因此在流量较大时有可能使其过载，从而造成帧的丢失。网桥的优点多于缺点正是其广泛使用的原因1033.6.2交换机与网桥一样，交换机按每一个包中的MAC地址相对简单地决策信息转发。与网桥不同的是交换机转发延迟很小，操作接近单个局域网性能，远远超过了普通桥接互联网络之间的转发性能。交换机本质上是多接口的网桥。利用专门设计的集成电路可使交换机以线路速率在所有的端口并行转发信息，提供了比传统桥接器高得多的操作性能。104交换机的基本原理所谓“交换”实际上就是指转发数据帧（Frame）。在数据通信中，所有的交换设备（即交换机）执行两个基本的操作：（1）交换数据帧，将从输入介质上收到的数据帧转发至相应的输出介质；交换机根据数据帧的MAC（MediaAccessControl）地址（即物理地址）进行数据帧的转发操作。交换机转发数据帧时，遵循以下规则：①如果数据帧的目的MAC地址是广播地址或者组播地址，则向交换机所有端口转发（除数据帧来的端口）。②如果数据帧的目的地址是单播地址，但是这个地址并不在交换机的地址表中，那么也会向所有的端口转发（除数据帧来的端口）。105③如果数据帧的目的地址在交换机的地址表中，那么就根据地址表转发到相应的端口。④如果数据帧的目的地址与数据帧的源地址在一个网段上，它就会丢弃这个数据帧，交换也就不会发生。（2）维护交换操作，构造和维护交换地址表。1063种交换技术（1）端口交换。这种交换技术最早出现在插槽式的集线器中，是基于OSI第一层上完成的，具有灵活性和负载平衡能力等优点。如果配置得当，那么还可以在一定程度进行容错错，但没有改变共享传输介质的特点，自而未能称之为真正的交换。（2）帧交换帧交换是目前应用最广的局域网交换技术，它通过对传统传输媒介进行微分段，提供并行传输的机制，以减小冲突域，获得高的带宽。107（3）信元交换ATM采用固定长度53个字节的信元交换，由于长度固定，因而便于用硬件实现。ATM采用专用的非差别连接，并行运行，可以通过一个交换机同时建立多个结点，但并不会影响每个结点之间的通信能力。ATM还容许在源结点和目标结点建立多个虚拟链接，以保障足够的带宽和容错能力。ATM采用了统计时分电路进行复用，因而能大大提高通道的利用率。108交换机与网桥的异同点交换机与网桥相同，是一种多端口设备。交换机和网桥的不同在于：交换机端口数较多；交换机的数据传输效较高。109直通交换和存储转发交换直通交换：当接收到一个帧的目的地址（MAC地址）后马上决定转发的目的端口，并开始转发，而不必等待接收到一个帧的全部字节后再进行转发。相对存储转发技术而言，降低了传输延迟，但在传输过程中不能进行校验，同时也可能传递广播风暴。存储转发交换：从功能上讲，就是网桥所使用的技术，等到全部数据都接收后再进行处理，包括校验、转发等。相对于直通技术而言，传输延迟较大。一些交换机可以同时使用上述两种技术。当网络误码率较低时采用直通技术，当网络误码率较高时则采用存储转发技术。这种交换机被称为自适应交换机。1103.7异步传输方式ATM

1概念ATM（AsynchronousTransferMode,异步传输方式）是一项先进和实用的通信技术，它采用固定大小报文分组动态地分配带宽。数据压缩、编码和传输是异步进行的。ATM也被称为“快速报文分组”。三网在传输内容上的不同需求与特点：语音、视频、数字；数据网络发送数据时，由于发送数据的终端数量不同，会产生不固定的延迟；现有数据网络分组长度不适合传输语音信号。ATM选择固定长度的短信元(cell)作为信息传输的单位，有利于宽带高速交换。信元长度为53字节，其首部（可简称为信头）为5字节。111“异步”的含义SDH传送的同步比特流被划分为一个个固定时间长度的帧（请注意，这是时分复用的时间帧，而不是数据链路层的帧）。当用户的ATM信元需要传送时，就可插入到SDH的一个帧中。同步时分复用异步时分复用如果用户有很多信元要发送，就可以接续不断地发送出去。只要SDH的帧有空位置就可以将这些信元插入进来。ATM采用异步时分复用的方式将来自不同信息源的信息汇集到一起，信元信头中的虚通道标识符/虚通路标识符（VPI/VCI）作为地址标记，网络根据信头中的标记识别和转发信元。1122ATM层次参考模型图ATM协议参考模型共三层，大体上与OSI的最低两层相当物理层物理媒体相关(PhysicalMediumDependent，PMD)子层负责在物理媒体上正确传输和接收比特流。它完成只和媒体相关的功能，如线路编码和解码、比特定时以及光电转换等。113传输汇聚子层

(TransmissionConvergenceSublayer)TC

子层实现信元流和比特流的转换，包括速率适配（空闲信元的插入）、信元定界与同步、传输帧的产生与恢复等。在发送时，TC子层将ATM层交下来的信元流转换成比特流，再交给下面的PMD子层。在接收时，TC子层将PMD子层交上来的比特流转换成信元流，标记出每一个信元的开始和结束，并交给ATM层。TC子层的存在使得ATM层实现了与下面的传输媒体完全无关。典型的TC子层就是SONET/SDH。114ATM信元流

装入一个STM-1帧的例子一个STM-1帧共有270*9=2430Byte115ATM

层的功能信元的复用与分用信元首部的产生与提取流量控制信元的VPI/VCI转换（就是将一个入信元的VPI/VCI转换成新的数值）116ATM

层

虚通路VC、虚通道VP一个虚通路VC是在两个或两个以上的端点之间的一个运送ATM信元的通信通路。一个虚通道VP包含有许多相同端点的虚通路VC，而这许多VC都使用同一个VPI。117