[网络协议]【计算机网络】第三部分 数据链路层(11) 数据链路控制

数据链路层的两个主要功能是数据链路控制和介质访问控制。前者，即数据链路控制的功能是用来处理两个邻近节点之间通信，即节点到节点通信的设计和程序，在此章节中阐述这一功能。而后者，数据链路层的第二个功能是介质访问控制，或者说如何共享链路，在【计算机网络】第三部分 数据链路层(12) 多路访问中阐述。

数据链路控制 data link control 的功能包括封装成帧、流量控制和差错控制，以及软件实现的协议，这些协议提供节点之间流畅且可靠的帧传输。在这一章，首先阐述成帧，或者说如何组织物理层所承载的位，然后再阐述流量控制和差错控制。关于差错的检测和纠正的技术已在【计算机网络】第三部分 数据链路层(10) 检错与纠错阐述过了。

我们需要协议来实现数据链路控制。每个协议都是一组规则，需要在软件中实现，并由「在数据链路层上参与数据交换的两个节点」来运行 Each protocol is a set of rules that need to be implemented in software and run by the two nodes involved in data exchange at the data link layer 。这里阐述五个协议：两个用于无噪声（理想的）通道，三个用于有噪声（现实的）通道。第一类的协议并不能真正地实施，它们为理解第二类协议提供了基础。

在阐述了这五个协议后，我们以高级数据链路控制协议为例，展示了如何实际实现面向位的协议 we show how a bit-oriented protocol is actually implemented by using the High-level Data Link Control (HDLC) Protocol as an example 。并阐述一个流行的面向字节的协议，即点对点协议 PPP 。

11.1 成帧

位于物理层的数据传递是指以信号的形式从源端传输到目的端。物理层提供位同步，以保证发送方和接收方能使用「相同的位周期和时序」。

另一方面，数据链路层需将位组合成帧，并使帧与帧之间是可识别的。邮局系统就实践了一种成帧形式：将一份信插入一个信封的简单动作，就将一段信息与另一段信息分离开来。信封就是一种分隔符。另外，既然邮局系统是一种多对多的传输设施，所以每个信封都标明了发送方和接收方的地址。

在数据链路层中，通过添加发送方地址和接收方地址，成帧 frarning 将一条从源端到目的端的报文分离开来，或者将到不同目的端的报文分离开来。目的地址定义了分组要去的地方，而发送方地址帮助接收方确认接收。

尽管整条报文 message 都应该分组为一个帧，但通常却不这么做。一个原因是一个帧会很大，将使得流量和差错控制变得十分低效。当一个巨大的帧承载一条报文时，即使一个字节的错误，也需要重新传递整条报文。

11.1.1 固定长度成帧

帧的大小可以是固定的，也可以是可变的。固定大小成帧 fixed-size frarning 中，不需要定义帧的边界，长度本身就可以用作分隔符。这种成帧类型的一个例子是ATM广域网，它用称为信元 cell 的固定长度帧，在第18章讨论ATM 。

11.1.2 可变长度成帧

这里主要讨论在局域网中盛行的可变长度成帧 variable-size frarning 。在可变长度成帧中，需要一种方法来规定「一个帧的结束」和「下一个帧的开始」。过去主要使用两种方法：面向字符的方式 character-oriented approach 和面向位的方式 bit-oriented approach 。

1. 面向字符协议

在面向字符协议 character-oriented protocol 中，数据用来自诸如ASCII编码系统的 $8$ 位字符传输。头部通常携带源端地址和目的端地址、以及其他控制信息，而尾部携带检错或纠错冗余位，也是 $8$ 位的倍数。为了将一个帧与下一个分离开来，在帧的开始和结束增加了 $8$ 位（ $1$ 字节）的标记 flag 。标记由「与协议相关的特殊字符」组合而成，标明一个帧的开始和结束。图11.1说明了在面向字符协议中帧的格式。

当数据链路层只交换文本时，流行面向字符成帧，标记可以选择文本通信中不使用的任何字符。然而现在，我们传输其他如图片、音频、视频等的信息，标记所使用的任何模式可能是这些信息的一部分，如果接收方恰巧在数据的中段接收到这一模式，它会认为已经到了帧的结束处了。为了解决这个问题，在面向字符成帧中使用了**字节填充** byte-stuffing 策略。

字节填充（或字符填充 character stuffing ）是指，（数据部分中）如果存在与标记相同模式的字符的话，便在帧的数据部分填入一个特殊的字节。数据段被填入一个额外的字节，这个字节通常称为换义字符 escape character, ESC ，有一个预定义的位模式。当接收方遇到换义字符时，便会将它从数据段移走，并仍将下一字符作为数据处理，而不是当作分界的标记。

通过换义字符来进行字节填充，允许标记出现在帧的数据段中，但也产生了另一问题——如果文本包含一个或多个转义字符，后跟一个标志，会发生什么情况？接收方移走了换义字符，但保留了标记，会被错译为帧的末端（？）。为了解决这一问题，作为文本一部分的换义字符，必须能被另一个换义字符标注。换言之，如果换义字符是文本的一部分，那么要增加额外的换义字符，以表明第二个换义字符是文本的一部分。图11.2说明了这一情况。

总的来说，字节填充是当文本中存在一个标记或换义字符（作为文本内容）时，（在其前面）添加一个额外字节（即转义字符）的过程。

面向字符协议在数据通信中产生了另一个问题。如今广泛应用的编码系统，例如Unicode有 $16$ 位和 $32$ 位字符，就会与 $8$ 位字符产生冲突。所以可以说，以下将讨论的面向位协议将是大势所趋。

2. 面向位协议

在面向位协议 bit-oreinted protocol 中，帧的数据段是一个位序列，将由上层翻译成文本、图片、音频、视频等等。然而，除了头部（也可能是尾部）之外，我们仍然需要一个分隔符将帧与帧区分开来。多数协议使用一个特殊的 $8$ 位模式的标记 $01111110$ 作为分隔符来标明帧的开始和结束 ，如图11.3所示。

此标记也会产生与面向字节协议相同的问题。也就是说，当标记的模式出现在数据中时，我们需要一定的信息，告知接收方这并不是帧的结束。我们通过填充一个简单的位（而非一个字节），使得这个模式区别于标记，这个策略就是位填充 bit stuffing 。

在位填充中，当遇到 $1$ 个 $0$ 和 $5$ 个连续的 $1$ ，便增加一个 $0$ 。这个额外填充的位，最终将被接收方移走。注意，无论接下来那个位是什么，额外的位 $0$ 都会添加在一个 $0$ 和五个 $1$ 后面，使得接收方不会误认 $0111110$ 是一个标记，这就保证了标志字段序列 flag field sequence 不会无意地 inadvertently 出现在帧中。

图11.4说明了发送方填充位和接收方移走位的过程。注意，如果在五个 $1$ 后有一个 $0$ ，我们仍然填充一个 $0$ 。这个 $0$ 将会被接收方移走。

这就意味着，如果有类似标记的模式 $01111110$ 出现在数据中，它会变成 $011111010$（填充后），而不会被接收方误认为是一个标记。而真正的标记 $01111110$ 是不会被发送方填充的，故而能被接收方正确地确认。

11.2 流量控制和差错控制

数据通信至少需要两个设备一起工作，一个发送而另一个接收。就算是如此基本的过程，也需要大量的协调来实现互相理解的交换。数据链路层最重要的职能就是流量控制 flow control 和差错控制 error control 。确切地说，这些功能被视为数据链路控制 data link control 。

11.2.1 流量控制

流量控制是数据链路层的一项重要职能，它在接收确认 receiving an acknowledgment 前，协调能被发送的数据数量。在大多数协议中，流量控制是一系列程序，告知发送方在等到来自接收方的确认之前，它能传输多少数据。

任何接收设备处理传入数据的速度都有限，存储传入数据的内存也有限。接收设备必须能够在达到这些限制前，提示发送设备，并要求传输设备发送的帧少一些、或者暂时停止发送。

进入的数据必须经过校验和处理才能使用。这些过程通常比传输速度慢。因此，每个接收设备都有一块存储区，称之为缓冲区 buffer ，存储进入的数据、直到它们被处理。如果缓冲区也装满了，接收方必须能告知发送方停止传输、直到它能够再次接收为止。

11.2.2 差错控制

差错控制包括差错检测和纠正。它使得接收方能够提示发送方「在传输过程中有帧的丢失或破坏」，并协调发送方重新传输这些帧。在数据链路层，术语差错控制通常指差错检测和重传的方法。在数据链路层中，差错控制一般容易实现：在交换的任何时刻检测到一个差错，就要重传这个出错的帧，这个过程称为自动重复请求 automatic repeat request, ARQ 。

11.3 协议

现在来看看数据链路层如何将封装成帧、流量控制和差错控制结合起来，从而实现节点对节点的数据传输。

在软件中，通常使用一种通用程序语言实现协议。为了讨论不受程序语言的影响，对每一协议用伪码进行编写，从而主要关注程序本身、而非研究程序语言的规则细节。

在此讨论的协议与在真实网络中使用的协议是有区别的。此处讨论的协议是单向的，数据帧从一个节点（称之为发送方），传输到另一个节点（称之为接收方）。虽然有些特殊的帧——我们称之为确认 acknowledgment, ACK 和否定确认 negative acknowledgment, NAK 帧，可以反方向流动（为了实现流量控制和差错控制），但数据只能单方向流动。

在现实生活的网络中，数据链路协议是双向实现的：数据可以双向流动。在这些协议中，流量控制和差错控制的信息（诸如 ACK 和 NAK 帧），通过捎带 piggybacking 技术被包含在数据帧中。因为双向协议要比单向协议复杂的多，这里只讨论后者，只要理解了它们，就可以扩展到双向协议了。

11.4 无噪声通道

首先，我们假设有一种不会丢失帧、复制帧或损坏帧的理想通道，然后介绍此类通道的两种协议——第一种协议不使用流量控制，而第二种使用流量控制。当然，两者都不使用差错控制（差错检测和重传），因为，我们假设这种通道是完美的无噪声通道。

11.4.1 最简单的协议（无流量控制和差错控制）

讨论的第一个协议就称为最简单的协议 simplest protocol 而没有其他特定的命名，这个协议没有流量控制和差错控制。与其他将要讨论的协议一样，此协议是单向的，数据帧从发送方到接收方单方向传输。

还假定接收方可以即时处理它所接收的任何帧，而所花费的时间少到可以忽略不计——数据链路层中的接收方可以即时去除帧的头部、并将数据分组传递到它的网络层，而网络层会即时收到分组。换言之，接收方永远不会因进入的帧而超载。

1. 设计

在这种方案中无需流量控制（和差错控制）。发送方站点的数据链路层从网络层获取数据，然后将数据成帧后发送。接收方站点的数据链路层从物理层接收到帧，从帧中取出数据，然后将数据传输到网络层。数据链路层的发送方和接收方，为其网络层提供传输服务。数据链路层使用其物理层提供的服务（例如发信号、多路复用等），进行位的物理传输。图11.6给出了一个设计。

我们需要精心设计数据链路层所使用的程序。发送方站点直到其网络层有数据包要发送时，才发送帧。接收方站点直到有帧到达时，才将数据分组传递给它的网络层。当协议用程序实现时，要介绍协议中的事件 event 概念——发送方的程序不断地运行着，直到有来自网络层的请求才会有行为；接收方的程序也不断地运行着，直到有来自物理层的通知才会有行为。两端的程序都不断地运行，因为它们不知道相关事件何时发生。

2. 算法和分析

算法11.1 在最简协议中发送方站点的算法，给出了发送方的程序。

while (true) {					// 不断重复
	WaitForBvent();				// 当一个事件出现时, 唤醒它
	if (Event(RequestToSend)) {	// 有一个要发送的分组
		GetData();				// 从网络层获取数据
		MakeFrame();			// 将数据封装成帧
		SendFrame();			// 发送帧到物理层, 进行数据传输
	}
}

该算法是一个无限的循环（不断地运行），也就是说当程序一旦启动，第 $2$ 行到第 $7$ 行就会一直重复。该算法是事件驱动型的，也就是说它休眠（第 $2$ 行）直到一个事件唤醒它（第 $3$ 行）。这意味着，第 $2$ 行与第 $3$ 行之间的执行存在不确定的时间段，它们之间存在缺口。当事件（即网络层发出的请求）发生时，第 $4$ 行到第 $6$ 行被执行。然后，程序开始重复循环，它又在第 $2$ 行休眠、直到下一个事件发生时。

为主要过程编写了伪代码，而并没有说明 GetData 、MakeFrame SendFrame 这些模块的细节。GetData() 指从网络层获取数据包，MakeFrame() 在数据包中添加头部和分界的标记形成帧，SendFrame() 则将帧传输到物理层。

算法11.2 在最简协议中接收方站点的算法，给出了接收方站点的程序。

while (true) {							// 不断重复
	WaitForBvent();						// 当一个事件出现时, 唤醒它
	if (Event(ArrivalNotification)) {	// 数据帧到达, 需要接收
		ReceiveFrame();					// 从物理层接收帧
		ExtractData();					// 从帧中提取出数据
		DeliverData();					// 发送数据到网络层
	}
}

除了帧和数据的传输方向是「向上」的以外，该算法和算法11.1的格式相同。此处的事件是数据帧的到达。该事件发生后，通过使用 ReceiveFrame() 语句，数据链路层从物理层获取帧，通过使用 ExtractData() 语句从帧中取出数据，并通过使用 DeliverData() 语句将数据传输到网络层。这里也使用事件驱动型算法，因为该算法无法知晓帧何时会到达。

【例11.1】图11.7例举了一个使用最简协议通信的例子。这个例子非常简单。发送方发送一个帧序列而不用考虑接收方。为了发送三个帧，在发送方站点和接收方站点各发生了三个事件。注意，图中倾斜的长方块表示数据帧，方块的高度定义为「帧中第一位和最后一位传输的时间差」。

11.4.2 停止等待协议（有流量控制，无差错控制）

如果「到达接收方的数据帧的速度」大于「它们能被处理的速度」，帧在使用前必须被存储。通常，接收方没有足够的存储空间，特别是它将接收来自多个源的数据肘。这样将导致帧被丢掉、或者服务被拒绝。为了避免接收方出现帧超负荷，我们要想办法让发送方减缓速度。也就是说接收方必须给发送方反馈信息。

现在讨论的协议称为停止等待协议 stop-and-wait protocol ，因为当发送方发出一个帧后必须停下来，直到接收到来自接收方的确认（可以继续了），然后再发送一个帧。这里，数据帧仍是单向通信的，除了辅助的 ACK 帧（用于确认的简单标记）从另一端传输过来。我们在前面的协议中加入流量控制。

1. 设计

图11.8描述了该过程。将该图与图11.6对比，可以看到前向通道（从发送方到接收方）和反向通道的数据流。在任何时刻，不是在前向通道有一个数据帧，就是在反向通道中有一个 ACK 帧。因此，我们需要一个半双工的链路。

2. 算法和分析

算法11.3 停止-等待协议中发送方算法，是发送方站点的算法。

while (true) {					// 不断重复
	canSend = true;				// 允许发送一个帧
	WaitForBvent();				// 当一个事件出现时, 唤醒它
	if (Event(RequestToSend) and canSend) {	// 有一个要发送的分组, 且能发送时
		GetData();				// 从网络层获取数据
		MakeFrame();			// 将数据封装成帧
		SendFrame();			// 发送帧到物理层, 进行数据传输
		canSend = false;		// 不能发送, 直到接收到来自接收方的确认ACK帧
	}
	WaitForBvent();				// 当一个事件出现时, 唤醒它
	if (Event(ArrivalNotification)) { // 当ACK到达
		ReceiveFrame();			// 接收ACK帧
		canSend = true;
	}
}

这里的 发送方会发生两个事件：来自网络层的请求、或来自物理层的通知。对这些事件的响应必须是交替的 The responses to these events must alternate 。换言之，当发送一个帧后，算法必须忽略另一个网络层的请求，直到该帧被确认。

我们知道两个到达事件 arrival events 不会一个紧接着一个发生，因为该通道是无差错的、且不能复制帧。但是，网络层发送的请求 requests from the network layer 可以一个紧接着一个发生、而中间无需有到达事件的发生。所以，我们要在一定程度上阻止数据帧的即时发送。

虽然有很多方法，但我们使用简单的变量 canSend ，该变量既可以是 true 、也可以是 false 。当一个帧被发送，该变量被设置为 false ，以表示不能发送新的网络请求、直到 canSend 变为 true 。当一个 ACK 帧被接收，canSend 便被设置为正确，以允许下一个帧的发送。

算法11.4 停止等待协议中接收方站点算法，描述了接收方站点的程序。

while (true) {							// 不断重复
	WaitForBvent();						// 当一个事件出现时, 唤醒它
	if (Event(ArrivalNotification)) {	// 数据帧到达, 需要接收
		ReceiveFrame();					// 从物理层接收帧
		ExtractData();					// 从帧中提取出数据
		DeliverData();					// 发送数据到网络层
		SendFrame();					// 发送一个ACK帧
	}
}

除了一处不同外，这个算法与算法11.2十分相似。当数据帧到达后，接收方发送一个 ACK 帧（第 $7$ 行），以确认接收到并允许发送方发送下一个帧。

【例11.2】图11.9列举了一个使用停止-等待协议的例子。这个例子仍然很简单。发送方发送一个帧后要等待接收方的反愤。当 ACK 帧到达后，发送方发送下一个帧。注意，该协议中发送两个帧，涉及了发送方的四个事件和接收方的两个事件。

11.5 有噪声通道

虽然停止-等待协议给出了我们如何在其程序中增加流量控制的概念，但是无噪声通道是不存在的。我们能忽略差错（就想我们时常做的那样），或者，我们需要为我们的协议增加差错控制。这部分，讨论三个使用差错控制的协议。

11.5.1 停止-等待自动重复请求（有流量控制和差错控制）

第一个协议称为停止-等待自动重复请求 Stop-and-Wait Automatic Repeat Request ，是在停止等待协议中增加了一个简单的差错控制机制。下面看看这个协议如何检测并纠正差错。

• 损坏帧 corrupted frames ：为了检测和纠正被损坏的帧，我们需要给数据帧加上冗余的位。当帧到达接收方站点时它被检测，如果它被损坏了，它会被无声地丢弃 silently discarded 。此协议中差错检测由接收方的静音 the silence of the receiver 来证明。
• 对丢失帧 lost frames 的处理远比对损坏帧的处理要难的多。在先前的协议中，我们没有办法标识一个帧，接收到的帧可以是正确的、或者复制的、也可以是无序的。解决的途径是为帧编号。当接收方接收到一个无序的数据帧时，就意味着这些帧或者是丢失的或者是被复制的。

在此协议中，要重发被损坏的帧和丢失的帧，以实现差错纠正。当有差错时，如果接收方没有响应（发送方的计时器超时），那么发送方如何知道要重发哪个帧呢？为了解决这个问题，发送方保留已发送帧的副本，同时它启动一个计时器。如果计时器到时、且没有收到已发送帧的 ACK（即接收方静音），就要重发该帧，保留副本并重启计时器。既然该协议使用停止等待机制，那么只有一个特定帧需要 ACK（注意：只有一个帧，而非一个窗口中的多个帧！），尽管网络中会存在同一个帧的多个副本。

既然一个 ACK 帧同样会被损坏或丢失 corrupted and lost ，它也需要冗余位和一个序列号。此协议中的 ACK 帧有一个序列号字段。此协议中，发送方只要简单的丢弃一个损坏的 ACK 帧、或者忽略一个无序的 ACK 帧。

1. 序列号

正如讨论的那样，此协议要求必须对帧进行编号。这通过使用序列号 sequence number 来完成。数据帧要增加一个字段来容纳帧的序列号。

序列号的排列是一个值得考虑的重要问题。既然我们希望帧的长度越小越好，就要寻找能提供无歧义通信的最小范围。序列号当然是可以循环的，例如，我们决定字段 $m$ 位长，序列号从 $0$ 开始，到 $2^m?1$ ， 再开始重复。

让我们来推出所需序列号的范围。假定我们使用 $x$ 作为一个序列号，（在停止等待自动重复请求这一个协议中）接下来我们只需用 $x+1$ ， 而没有必要用 $x+2$ 。为了加以演示，假定发送方已经发送了序列号为 $x$ 的帧，那么将会发生三种情况。

1. 帧安全到达接收方，接收方发送确认。确认到达发送方，促使发送方发送下一个序列号是 $x+1$ 的帧。
2. 帧安全到达接收方，接收方发送确认，但是确认被损坏或丢失了。在超时后发送方重发帧（编号 $x$）。注意：此处的帧是重复帧，接收方可以确认这一事实，因为它预期帧 $x+1$ 到达但接收到的却是帧 $x$ 。
3. 帧被损坏、或者没有到达接收方时，在超时后发送方重发帧（编号 $x$ ）。注意：此处的帧是无序帧。

我们可以看到有必要使用序列号 $x$ 和 $x+1$ ，因为接收方需要区分情况 $1$ 和情况 $2$ 。但是，没有必要将帧编号为 $x+2$ ：

• 在情况 $1$ 中，帧可以再编号为 $x$ ，因为帧 $x$ 和 $x+1$ 被确认、而且在任何一端都没有歧义。
• 在情况 $2$ 和 $3$ 中，新的帧是 $x+1$ ， 不是 $x+2$ 。

如果只需要 $x$ 和 $x+1$ ， 就可以使 $x=0$ 及 $x+1=1$ 。这就意味着序号是 $0,1,0,1,0$ 等。这就是模 $2$ 运算。即，在停止等待ARQ中，我们使用序列号给帧编号，该序列号基于模 $2$ 运算。

我们还注意到，对发送方而言，情况 $2$ 和 $3$ 是无法区分的，它无法判断是帧被丢失了、还是确认被丢失了，都重发对应帧 $x$ 。但对接收方而言， 接收方可以区分这两种情况：情况 $2$ 中接收方确认了 $x$ 、期待收到 $x+1$ ，只是重发后收到的是 $x$ ；情况 $3$ 中接收方一开始期待收到 $x$ ，重发后收到 $x$ 、并期望收到 $x+1$ 。对这两种情况，无论一开始期待收到的是 $x+1$ 还是 $x$ ，最后都要发送确认号为 $x+1$ 的 ACK 帧，在后面的接收方算法中就明确体现了这一点。

2. 确认号

既然序列号必须既适用于数据帧，也要适用于 ACK 帧，那么我们使用这个约定：确认号总是告知「接收方期待的下一个帧的序列号」 the sequence number of the next frame expected by the receiver 。例如，如果帧 $0$ 安全到达，接收方发送一个带有确认 $1$ 的 ACK 帧（表示下一个期待收到的是帧 $1$ ）。如果帧 $1$ 安全到达，接收方则发送一个带有确认 $0$ 的 ACK 帧（表示下一个期待收到的是帧 $0$）。即，在停止等待ARQ中，确认号总是以模 $2$ 运算，宣布期待收到的下一个帧的编号。

3. 设计

图11.10描述了停止等待ARQ协议的设计，注意：发送方和接收方都只持有大小为 $1$ 的窗口，发送设备保留最后传输的帧的副本、直到接收到该帧的确认。一个数据帧使用一个序列号，一个 ACK 帧使用一个确认号。

发送方有一个控制变量，我们称为 $S_n$（发送方，下一个要发送的帧 sender, next frame to send ），它保存下一个将被发送的帧的序号（$0$ 或 $1$）。接收方有一个控制变量，我们称之为 $R_n$（接收方，期待收到的下一个帧 receiver, next frame expected ），它保存下一个期待收到帧的编号。当一个帧被发送，$S_n$ 值递增（模 $2$ ），如果它是 $0$ ，它会变成 $1$ ，如果是 $1$ 则会变成 $0$ 。当一个帧被接收时，$R_n$ 值递增（模 $2$ ），如果它是 $0$ ，它会变成 $1$ ，如果是 $1$ 则会变成 $0$ 。发送方站点将有三个事件发生，接收方站点发生一个事件。变量 $S_n$ 指向的时隙与已经发送的帧的序列号相匹配，但没有被确认，$R_n$ 指向的时隙与期待收到的帧的序列号相匹配。

4. 算法和分析

算法11.5 停止-等待ARQ协议中发送方站点的算法如下：

Sn = 0;								// 帧0被最先发出
canSend = true;						// 允许发送一个帧,即允许最初请求
while (true) {						// 不断重复
	WaitForBvent();					// 当一个事件出现时, 唤醒它
	if (Event(RequestToSend) and canSend) {	// 有一个要发送的分组, 且能发送时
		GetData();					// 从网络层获取数据
		MakeFrame();				// 将数据封装成帧
		StoreFrame(Sn);				// 保存帧的副本
		SendFrame(Sn);				// 发送帧到物理层, 进行数据传输
		StartTimer();				// 启动计时器
		Sn = Sn + 1;				// 指向next frame to send
		canSend = false;			// 不能发送, 直到接收到来自接收方的确认ACK帧
	}
	WaitForBvent();					// 当一个事件出现时, 唤醒它
	if (Event(ArrivalNotification)) { // 当ACK到达
		ReceiveFrame(ackNo);		// 接收ACK帧
		if (not corrupted and ackNo == Sn) { // 有效ACK帧
			StopTimer();
			PurgeFrame(Sn - 1);		// 不需要的副本(Sn-1需要模2运算)
			canSend = true;			// 发送下一个帧
		}
	}
	if (Event(TimeOut)) {			// 超时
		StartTimer();
		ResendFrame(Sn - 1);		// Resend a copy check, 发送副本检查(Sn-1需要模2运算)
	}
}

我们首先注意到 $S_n$ ，它是下一个将要发送的帧的序列号。该变量只初始化一次（第 $1$ 行），但每次发送一个帧后，它便递增为下一个帧做准备。然而，既然这是模 $2$ 运算，那么序列号就是 $0,1,0,1$ 等。注意：第一个事件的进程 (SendFrame, StoreFrame, PurgeFrame) ，使用 $S_n$ 来定义被发送的帧。我们至少需要一个缓冲区来保存这个帧，直到我们能确认它已被安全接收，StoreFrame(Sn) 指出在帧被发送前，它被保存了，这个副本用来重发一个损坏或者丢失的帧。

我们仍然使用变量 canSend ，在前一个帧安全接收之前、防止网络层提出请求。如果这个帧没有损坏，且 ACK 帧的确认号与「下一个将要发送的帧的序列号」匹配，我们便停掉计时器，并清除保存的数据帧副本。否则，我们只要忽略这个事件，并等待下一个事件发生就行了——每一个帧被发送后，一个计时器开始计时。当计时器超时，帧被重发，且计时器被重置。

算法11.6 停止等待ARQ协议中接收方站点的算法，显示了接收方站点的程序。

Rn = 0;									// 期待收到的下一个帧, next frame expected
while (true) {							// 不断重复
	WaitForBvent();						// 当一个事件出现时, 唤醒它
	if (Event(ArrivalNotification)) {	// 数据帧到达, 需要接收
		ReceiveFrame();					// 从物理层接收帧
		if (corrupted(frame)) Sleep();	// 如果帧损坏, 则接收方静默	
		if (seqNo == Rn) {				// 当帧的序列号是期待收到的那个时, 为有效数据帧
			ExtractData();				// 从帧中提取出数据
			DeliverData();				// 发送数据到网络层
			Rn = Rn + 1;
		}
		SendFrame(Rn);					// 发送一个ACK帧
	}
}

这显然与算法11.4不同。首先，将忽略所有已损坏的到达数据帧，且当帧的序列号是期待收到的那个 $R_n$ 时，帧才被接收，数据才被传输到网络层，$R_n$ 值增加。然而，这里有一个微小的差别：即使数据帧的序列号与下一个期待的帧的序列号不匹配，也会发送一个 ACK 帧给发送方。不过，这个 ACK 只是重新确认前一个 ACK 、而不是确认接收到的帧 reconfirms the previous ACK instead of confirming the frame received 。这样做是因为，接收方认为先前的那个 ACK 可能已经丢失了，接收方正在发送一个副本 the receiver is sending a duplicate frame 。重发的 ACK 可能在时钟超时之前解决问题 The resent ACK may solve the problem before the time-out does it 。

【例11.3】图11.11给出了一个停止等待ARQ协议的例子。帧 $0$ 被发送并被确认。帧 $1$ 丢失了并在超时之后被重发。重发的帧 $1$ 被确认，计时器便停止计时。帧 $0$ 被发送并确认，但是确认丢失了。发送方无法判断是帧被丢失了、还是确认被丢失了，因此超时后，它重发帧 $0$ ，虽然帧 $0$ 己被确认了。

4. 效率

如果我们的通道粗且长的话，那么前部分讨论的停止等待ARQ协议是十分低效的——粗指的是通道有很大的带宽，长指的是往返延迟较长。这两者的乘积称为带宽延迟乘积（时延带宽积） bandwidth-delay product ，正如第3章中讨论的。可以把这种通道看作一根管道，那么带宽延迟乘积就是以位为单位的管道容量。管道总是在那里，如果我们不使用它，那么就是无效的。带宽延迟乘积是一种尺度，用来度量我们在等待来自接收方的消息的同时、所能发送到系统外的位数。

【例11.4】假定，在一个停止等待ARQ系统中，带宽是 $1\text{Mbps}$ ，且一个位往返一次是 $20$ 毫秒。那么带宽延迟乘积是多少？如果系统的数据帧的长度是 $1000$ 位，那么链路的利用率是多少？
解：带宽延迟乘积是 $(1\times 10^6)\times (20\times 10^{?3})=20000$ 位。在数据从发送方到接收方再返回的期间，系统能够发送 $20000$ 位。然而，系统只能发送 $1000$ 位。我们因此说链路的利用率仅有 $\frac{1000}{20000}=5\%$ 。正因为此，如果链路有高带宽或长延迟的话，使用停止等待ARQ协议是对链路能效的一个浪费。

【例11.5】在例11.4中，如果我们拥有一种协议能在停止和担心确认之前发送 $15$ 个帧，那么链路层的利用率是多少？
解：带宽延迟乘积仍然是 $20000$ 位。在一个往返过程中，系统能发送 $15$ 个帧或者 $15000$ 位，这意味着利用率是 $\frac{15000}{20000}=75\%$ 。当然，如果存在损坏的帧，那么利用率就要低很多，因为这些帧要被重发。

5. 流水线操作

在网络或者其他领域中，一项任务通常是在前一项任务结束之前开始的 a task is often begun before the previous task has ended ，这就是流水线操作 pipelining 。在停止等待ARQ协议中不存在流水线操作，因为我们必须等待一个帧到达目的地并被确认后，才能发送下一个帧。然而，流水线操作应用到了下面的两个协议中，因为在我们得到关于前几个帧的消息前，就能发送后几个帧了。如果传输的位的数量是巨大的，考虑到带宽延迟乘积，流水线操作改进了传输的效率。

11.5.2 回退 $N$ 帧自动重发请求（流水线提高效率）

为了提高传输的效率（填满管道），在等待确认时必须传输多个帧。即，在发送方等待确认时，我们需要让多个帧待处理来使通道忙碌。在这一节，我们讨论一个能够达到这个目的的协议，在下一节将讨论另一个。

第一个协议称之为回退 $N$ 帧自动重发请求 Go-Back-N Automatic Repeat Request 。在这个协议中，我们在接收到确认之前可以发送几个帧；我们保留了这些帧的副本，直到收到确认。

1. 序列号

帧在发送站点按序编号。然而，因为我们要让每一个帧的头部中包含序列号，我们需要设置一个限制值。如果一个帧的头部允许序列号有 $m$ 位，序列号的范围就是 $0$ 到 $2^m?1$ 。例如，如果 $m$ 等于 $4$ ，那么序列号只能是 $0$ 到 $15$ 中的数字。当然，我们可以重复序列号。因此，序列号是 $0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7,8,9,10,11,\dots$ 。换言之，在回退 $N$ 帧协议中，序列号是 modulo-2m，这里的 $m$ 是以比特位为单位的序列号字段长度。

2. 滑动窗口

在此协议（和下一个协议）中，滑动窗口 sliding window 是一个抽象的概念，用来定义「发送方和接收方关心的序列号范围」。即，发送方和接收方只需处理可能的序列号部分。发送方关心的序列号范围称为发送滑动窗口 send sliding window ，接收方关心的则称为接收滑动窗口 receive sliding window 。我们将对两者进行讨论。

发送窗口是一个假想的盒子，包含了能传输的数据帧的序列号。在每一个窗口中，一部分序列号定义了已经发送的帧，另一部分定义了能够被发送的帧。窗口的最大尺度是 $2^m?1$ ，原因以后阐述。在这里，我们固定窗口的大小，使之为最大值，但是在以后会看到一些协议有可变的窗口大小。图11.12给出了一个大小为 $15(m=4)$ 的滑动窗口。

该窗口随时将可能的序列号划分为四个部分：

• 第一部分，从最左端到窗口的左墙，定义属于已经被确认的帧的序号 frames that are already acknowledged 。发送方不用担心这些帧，也不用保留它们的副本。
• 第二部分，图11.12a的着色部分，定义了属于已发送、但处于未知状态的帧的序号 frames that are sent and have an unknown status 。发送方必须等待、直到知道这些帧被接收或者被丢失。我们称这些帧为待处理的帧 We call these outstanding frames 。
• 第三部分，图中的空白部分，显示了那些能够被发送的帧的序号范围 frames that can be sent ，但还没有从网络层接收到相对应的数据包。
• 最后，第四部分显示了那些直到窗口滑动才能使用的序号 sequence numbers that cannot be used until the window slides ，正如接下来看到的那样。

发送窗口本身是一个抽象体，三个变量定义了它在任何时候的大小和位置。我们称这些变量为 $S_f$（发送窗口，第一个待处理的帧 the first outstanding frame），$S_n$（发送窗口，下一个要发送的帧），和 $S_{size}$（发送窗口，大小）。变量 $S_f$ 定义了第一个（最先）待处理帧的序号。变量 $S_n$ 定义了分配给下一个将发送帧的序号。最后，变量 $S_{size}$ 定义了窗口的大小，该变量在此协议中是固定的。

图11.12b描述了：当另一端发来的确认到达时，一个发送窗口可以向右滑动一个或者多个时隙。正如不久可以看到的那样，在此协议中，确认是累加的，这意味着一个 ACK 帧可以确认一个以上的帧（发送了多个帧，而多个确认丢失时）。在图11.12b中，帧 $0,1,2$ 已被确认，因此窗口向右滑动了三个时隙。注意 $S_f$ 的值是 $3$ ，因为帧 $3$ 现在是待处理的帧。

接收窗口确保接收到正确的数据帧，并发送正确的确认 the correct data frames are received and that the correct acknowledgments are sent 。接收窗口的大小始终是 $1$ 。接收方总是在等待一个指定帧的到达。任何到达的失序帧都会被丢掉、并要求重发 Any frame arriving out of order is discarded and needs to be resent 。图11.13显示了接收窗口。

接收窗口是一个抽象概念，通过唯一变量 $R_n$ 定义了一个大小为 $1$ 的假想盒子 。当一个正确的帧到达后（且每次只能收到一个帧 a frame is received only one at a time ），接收窗口同样会滑动，但每次只滑动一个时隙。注意：我们只需要一个变量 $R_n$（接收窗口，期待的下一个帧）来定义这个抽象概念。窗口左边的序号属于那些已接收并确认的帧，右边的序号显示了那些不能被接收的帧，任何已收到帧的序号属于这两部分都会被丢弃。只有当一个帧的序号与 $R_n$ 匹配时，才被接收和确认。

3. 计时器

（对于发送方而言）虽然每一个已发送的帧都能有一个计时器，但在我们的协议中我们只用一个计时器。原因是：第一个待处理帧的计时器总是先到时，当这个计时器到时时，我们发送所有的待处理帧。

4. 确认

最简单的情况是，当一个帧安全有序到达时，接收方发送一个肯定的确认（一个帧对一个确认，正常情况）。

此外，如果一个帧被损坏了、或者收到时次序颠倒了，接收方便不响应、并将丢弃所有后来的帧、直到它收到一个它所期待的帧；接收方的不响应，导致发送方站点上未确认帧的计时器到时。这反过来会导致发送方回退 go back ，并从「计时器到时的那个帧」开始重新发送所有帧 resend all frames （这里还是一个帧对一个确认）。

注意，接收方不需要确认每一个收到的帧，它能为多个帧发送一个累积的确认，这出现在接收方收到了多个帧、而发送的多个确认丢失时（多个帧对一个确认，异常情况）。

5. 重发帧

当计时器到时的时候，发送方会重发所有待处理的帧 resends all outstanding frames 。例如，假定发送方已经发送了帧 $6$ ，但是帧 $3$ 的计时器到时了。这就意味着帧 $3$ 没有被确认，发送方就要返回并重发帧 $3,4,5,6$ 。这就是这个协议称之为回退 $N$ 帧自动重发请求协议的原因。

6. 设计

图11.14描述了该协议的设计。正如我们可以看到的，多个帧可以正向传输，多个确认可以反向传输。这个理念与停止等待ARQ协议类似，区别在于发送窗口允许我们传输「与发送窗口中的时隙一样多的帧」 allows us to have as many frames in transition as there are slots in the send window 。

7. 发送窗口大小

我们现在可以阐述，为什么发送窗口的大小必须小于 $2^m$ 了。作为一个示例，我们使 $m=2$ ，这就意味着窗口的大小是 $2^m?1=3$ 。图11.15将一个大小为 $3$ 的窗口和一个大小为 $4$ 的窗口进行比较。

• 如果窗口的大小为 $3$（小于 $2^2$ ）且三个确认被丢失了，帧 $0$ 的计时器到时，那么所有三个帧都要被重发。接收方现在期待的是帧 $3$ ，而不是帧 $0$ ，于是重复帧被正确地舍弃了。对这些重复帧，不会像停止等待ARQ一样每个再发送 ACK 帧，而是在收到期望帧后、发送一个累积的确认帧。在后面的接收方算法中就明确体现了这一点。
• 另一方面，如果窗口的大小是 $4$（等于 $2^2$ ）且所有确认被丢失了，发送方就要重发帧 $0$ 的副本。然而，这次接收方的窗口期待收到帧 $0$ ，于是它接收了帧 $0$ ，不是作为一个丢失帧的副本、而是作为下一周期中的第一个帧，这是一个差错！实际上应该丢弃！
  

总结来说，在回退 $N$ 帧自动重发请求协议中，发送窗口的大小必须小于 $2^m$ ，而接收窗口的大小始终是 $1$ 。

8. 算法和分析

算法11.7 回退 $N$ 帧自动重发请求的发送方算法如下：

Sw = 2^m - 1;						// 发送窗口的大小
Sf = 0;								// 第一个待处理的帧
Sn = 0;								// 下一个要发送的帧; 帧0被最先发出 
while (true) {						// 不断重复
	WaitForBvent();					// 当一个事件出现时, 唤醒它
	if (Event(RequestToSend)) {		// 有一个要发送的分组, 且能发送时
		if (Sn - Sf >= Sw)			// 如果窗口满了
			Sleep();
		GetData();					// 从网络层获取数据
		MakeFrame();				// 将数据封装成帧
		StoreFrame(Sn);				// 保存帧的副本
		SendFrame(Sn);				// 发送帧到物理层, 进行数据传输
		Sn = Sn + 1;				// 指向next frame to send
		if (timer not running)
			StartTimer();			// 启动计时器
	}
	WaitForBvent();					// 当一个事件出现时, 唤醒它
	if (Event(ArrivalNotification)) { // 当ACK到达
		ReceiveFrame(ACK);			// 接收ACK帧
		if (corrupted(ACK)) 		// 如果收到一个损坏的ACK帧, 则忽略它
			Sleep();
		if (ackNo > Sf && ackNo <= Sn) { // 有效ACK帧; 注意ackNo的范围!!!
			StopTimer();
			while (Sf < ackNo) { 	// 此处书上是<=
				PurgeFrame(Sf);		// 不需要的副本(Sf+1需要模2运算) 
				Sf = Sf + 1;	
			}
		}
	}
	if (Event(TimeOut)) {			// 超时
		StartTimer();
		Temp = Sf;
		While (Temp < Sn) {			// 重发所有的待处理帧
			SendFrame(Temp);
			Temp = Temp + 1;
		}
	}
}

该算法先初始化了三个变量。与停止等待ARQ协议不同，这个协议允许来自网络层的多个请求、而不需要其他事件的发生，我们只需要确定窗口并没有满。在我们的算法中，如果窗口满了，请求就会被忽视、而网络层就要再尝试。有一些实现使用了其他的方法，比如激活或者抑制网络层 enabling or disabling the network layer 。

对到达事件的处理远比之前的协议复杂得多。如果我们收到一个损坏的 ACK ，我们就忽略它；如果这个 ackNo（ACK 序号）属于其中一个待处理的帧，我们就停止计时器，用一个循环来清除缓冲区，并将窗口的左墙移到右边。超时事件同样更复杂，我们首先启动一个新的计时器，然后我们重发所有的待处理帧。

算法11.8是在回退 $N$ 帧自动重发请求协议中的接收方算法。

Rn = 0;									// 期待收到的下一个帧, next frame expected
while (true) {							// 不断重复
	WaitForBvent();						// 当一个事件出现时, 唤醒它
	if (Event(ArrivalNotification)) {	// 数据帧到达, 需要接收
		ReceiveFrame();					// 从物理层接收帧
		if (corrupted(frame)) Sleep();	// 如果帧损坏, 则接收方静默	
		if (seqNo == Rn) {				// 当帧的序列号是期待收到的那个时, 为有效数据帧
			ExtractData();				// 从帧中提取出数据
			DeliverData();				// 发送数据到网络层
			Rn = Rn + 1;
			SendACK(Rn);				// 发送一个ACK帧(只这里与停止等待ARQ不同)
		}
	}
}

这个算法是简单的。我们忽略了损坏的帧或者失序的帧。如果一个帧以预期的序列号到达，我们就传送数据，更新 $R_n$ 的值，并发送一个 ACK ，其 ackNo 指明了下一个被期待的帧。

【例11.6】图11.6描述了一个回退 $N$ 帧的例子。这个例子中正向通道是可靠的，而反向通道则不可靠。没有数据帧丢失，但是有一些 ACK 被延迟了并且有一个被丢失了。这个例子还指出了，在确认被延迟或丢失的情况下，累积的确认如何提供帮助。
在初始化后，有 $7$ 个发送方事件。请求事件由来自网络层的数据触发，到达事件由来自物理层的确认触发。这里没有超时事件，因为所有待处理的帧在超时前都被确认了。注意，虽然 ACK2 丢失了，ACK3 能起到 ACK2 和 ACK3 两者的作用。这里有 $4$ 个接收方事件，所有的事件全部由物理层的帧到达触发。

【例11.7】图11.7说明了，如果一个帧丢失了，情况会怎样。帧 $0,1,2,3$ 被发送了，而帧 $1$ 丢失了。接收方收到了帧 $2$ 和 $3$ ，但是它们被舍弃了，因为被收到时它们失序了（被期待的是帧 $1$ ）。发送方没有收到任何与帧 $1,2,3$ 相关的确认。计时器最终到时，发送方再发送所有待处理的帧 $(1,2,3)$ ，因为它不知道哪里出错了。

注意，帧 $1,2,3$ 的重发是对一个单一事件的响应 one single event 。当发送方对这一事件响应时，它不能再接受其他事件的触发——这就意味着，当 ACK2 到达时，发送方仍然在忙着发送帧 $3$ 。物理层必须等待，直到这一事件被完成，而数据链路层重新回到休眠状态。我们画了一条垂线来显示延迟。ACK3 发生了同样的状况，但当 ACK3 到达时，发送方正忙着应答 ACK2 。当 ACK4 到达时，同样的状况又发生了。注意：在第二个计时器到时前，所有待处理的帧已经都被发送了、且计时器停止了。

9. 回退 $N$ 帧ARQ与停止等待ARQ的比较

能发现回退 $N$ 帧ARQ与停止等待ARQ有相同之处。我们可以认为，停止等待ARQ协议实际上是回退 $N$ 帧ARQ协议的一种，即当只有 $2$ 个序列号、而发送窗口的大小为 $1$ 时，即 $m=1,2^m?1=1$ 。在回退 $N$ 帧的ARQ中，条件是模 $2^m$ ，而在停止等待ARQ中，条件是模 $2$ ，即 $m=1,2^m=2$ 。

11.5.3 选择性重复ARQ

回退 $N$ 帧ARQ Go-Back-N ARQ 协议简化了接收方的程序：接收方只持有一个变量，且没有必要缓存失序的帧，它们只是被简单地丢弃。然而，这个协议在有噪声链路中十分低效。在有噪声链路中，一个帧被损坏的可能性更大，这就意味着要重发多个帧，重发占用了带宽并减慢了传输的速度。

对于有噪声链路而言，有另一种机制，可以在一个帧被损坏时不必重发 $N$ 个帧。这个机制就称为选择性重复ARQ Selective Repeat Automatic Repeat Request 。它对有噪声链路更为有效，但是接收方的程序也更复杂。

1. 窗口

选择性重复协议同样使用两个窗口：发送窗口和接收窗口。但是，这些窗口与回退 $N$ 帧协议中的窗口有所不同。首先，窗口的尺度更小，为 $2^{m?1}$ ，原因后面解释。第二，接收窗口与发送窗口的大小一样。发送窗口最大只能是 $2^{m?1}$ ，接收方也一样。例如，如果 $m=4$ ， 序号为 $0～15$ ，但是窗口的大小只能是 $8$（而在回退N帧协议中，它是 $2^m?1=15$ ，不是 $2^m$ 的原因已经讲述过了）。

窗口尺度变小，意味着对管道填充的有效性减少 The smaller window size means less efficiency in filling the pipe ，但事实上副本帧 duplicate frames 会少很多，能使这点得到补偿。该协议使用了与回退 $N$ 帧协议相同的变量。图11.18显示了选择性重复协议中的发送窗口来强调窗口的大小。将其与图11.12进行比较。

在选择性重复协议中的接收窗口，则与回退 $N$ 帧的接收窗口完全不同：

• 首先，选择性重复中，接收窗口的大小和发送窗口的一样，为 $2^{m?1}$ ；回退 $N$ 帧中，接收窗口的大小为 $1$ 。
• 选择性重复协议允许「与接收窗口大小一样多的帧」乱序到达，并被保留、直到有一组有序帧能交付给网络层。因为发送窗口的大小和接收窗口的一样，所有被发送的帧能乱序到达，并被保存、直到它们被传输。然而，我们需要指出的是，接收方从不会将无序的数据分组交付给网络层。

图11.19显示了该协议中的接收窗口。窗口中的着色时隙指的是那些乱序到达的帧，这些帧被交付给网络层前，正等待其相邻帧的到达。

2. 设计

该协议的设计与我们描述的回退 $N$ 帧协议的设计，有一定程度的相似，但是正如图11.20所示，它要复杂的多。

3. 窗口大小

现在能解释，为什么发送窗口和接收窗口的大小最多是 $2^m$ 的一半（不是 $2^m$ ，也不是 $2^m?1$ ）了。举例来说，使 $m=2$ ， 意味着窗口的大小为 $2^m/2$ ，即 $2$ 。图11.21将大小为 $2$ 的窗口与大小为 $3$ 的窗口做了一个比较。

• 如果窗口的大小为 $2$ 、且所有的确认都丢失了，那么当帧 $0$ 的计时器到时时，帧 $0$ 就被重发。然而，接收方的窗口现在期待的是帧 $2$ 而不是帧 $0$ ，那么帧 $0$ 的副本就会被正确地丢弃。
• 如果窗口的大小为 $3$ 、且所有的确认丢失了，发送方发送了一个帧 $0$ 的副本。而这次，接收方窗口期待收到帧 $3,0,1$（它们都是窗口的一部分），所以它接收帧 $0$ ，但帧 $0$ 是下一个周期的第一个帧，而不是一个副本。这明显是一个错误。
  

即，接收方的滑动窗口大小为 $2^{m?1}$ ，接收了 $2^{m?1}$ 个帧后，窗口向后滑动覆盖后面的 $2^{m?1}$ 个位置，这两部分合起来为 $2^m$ ，刚好是序列号的一个变化周期，此时不会造成错误的接收。如果接收方滑动窗口大于 $2^{m?1}$ ，则接收了窗口大小的帧后，向后滑动覆盖又一部分位置，这两部分合起来大于 $2^m$ ，超过了序列号的一个变化周期，如果前一部分中的某些帧丢失确认、超时重传，则会被错误的接收。

4. 算法和分析

算法11.9 发送方选择性重复算法，描述了发送方的程序。

Sw = 2^(m - 1);								// 窗口大小
Sf = 0;										// 第一个待处理的帧编号
Sn = 0;										// 下一个将发送的帧
// (Sf, Sf + Sw - 1)确定了一个发送窗口, (Sf, Sn -1)是已发送、未确认的窗口
while (true) { 								// 不断重复
	WaifForEvent();							// 等待事件发生
	if (Event(RequestToSend)) { 			// 事件: 有包要发送
		if (Sn - Sf >= Sw)        			// 所有包已经发出,Sn指向发送窗口的后一个位置
			Sleep(); 
		GetData();							// 从网络层获取数据
		MakeFrame(Sn); 						// 用当前编号成帧
		StoreFrame(Sn); 					// 存储帧的副本
		SendFrame(Sn); 						// 发送帧
		StartTimer(Sn); 					// 对每个编号的帧设置一个计时器
		Sn = Sn + 1; 						// 发送下一个帧
	}
	if (Event(ArrivalNotification)) { 		// 帧到达
		Receive(frame);						// 接收ACK或NAK
		if (corrupted(frame)) Sleep(); 		// 如果帧损坏
		if (FrameType == NAK) {				// 如果是NAK帧
			if (nakNo between Sf and Sn) {  // 选择性重发
				Resend(nakNo);
				StartTimer(nakNo);
			}
		}
		if (FrameType == ACK) {				// 如果是(累计)ACK帧
			if (ackNo between Sf and Sn) { 	// 有效的ACK帧
				while (Sf < ackNo) {		// 移动窗口左墙
					PurgeFrame(Sf);
					StopTimer(Sf);
					Sf = Sf + 1;
				}
			}
		}
	}
	if (Event(TimeOut(t))) { 				// 计时器超时
		StartTimer(t);
		SendFrame(t);
	}
}	

请求事件的处理与前一协议（只使用一个计时器）相类似，除了每一个帧的发送都启动一个计时器外。这里到达的事件要复杂得多。到达的可能是一个 ACK ，也可能是一个 NAK 。如果一个有效的 NAK 帧到达了，我们只需重发相应的帧；如果一个有效的 ACK 到达了，我们使用一个循环来清除缓冲区，停止相应的计时器，并移动窗口的左墙。此处的超时事件比较简单，只有超时的帧才重发。

算法11.10 接收方选择性重复算法，描述了接收方的程序。

Rn = 0; 									// 下一个将接收的帧
NakSent = false;							// 何时发送Nak, 要求选择性重发
AckNeeded = false;							// 何时发送Ack, 
Repeat(for all slots)						// 窗口中的所有时隙均没有帧到达
	Marked(slot) = false;
while (true) {						 		// 不断重复
	WaitForEvent();
	if (Event(ArrivalNotification)) { 		// 数据帧到达
		Receive(frame);
		if (corrupted(frame) && (not NakSent)) { // 如果收到了一个损坏的帧, 且Nak未发送
			SendNAK(Rn);
			NakSent = true;
			Sleep();						// 接收方保持静默, 等待重发的帧
		}
		if (seqNo <> Rn && (not NakSent)) {	// 如果帧没被损坏、未发送Nak且序列号不等于接收窗口的左端Rn
			SendNAK(Rn);
			NakSent = true;
		} // 书上没有这个括号
			if ((seqNo in window) && (!Marked(seqNo)) { // 序列号在窗口中, 且相应时隙未被标记
				StoreFrame(seqNo);			// 存储该帧
				Marked(seqNo) = true; 		// 并标记该帧为已接收
				while (Marked(Rn)) {		// 如果从Rn开始连续的帧都被标记了
					ExtractData(Rn);		// 从帧中提取出数据
					DeliverData(Rn);		// 发送数据到网络层
					Purge(Rn);
					Rn = Rn + 1;			// 滑动窗口
					AckNeeded = true;		// 要发送ACK
				}
				if (AckNeeded) {			// 如果要发送ACK
					SendACK(Rn);
					AckNeeded = false;		// 发送ACK完成
					NakSent = false;		// 窗口滑动后, 不再需要选择性重发这一段; 下一个又可以发送NAK
				}
			}
		// } // 书上有这个括号
	}
}

此处我们要有更多的初始化。为了不使另一端因为 NAK 而超负荷，我们使用了一个称为 NakSent 的变量。为了明确何时我们需要发送一个 ACK ，我们使用一个名为 AckNeeded 的变量。这两个变量都初始化为 false 。一旦相应的帧到达并被保存了，我们用一系列变量来标记 Marked 接收窗口中的时隙。

• 如果我们收到一个损坏的帧、而 NAK 帧还未被发送，我们就发送一个 NAK 去告知另一方，我们还未收到我们期待的帧。
• 如果帧没被损坏、且序列号在窗口中，我们保存这个帧、并在时隙上做标记。
• 如果从 $R_n$ 开始相邻的帧都被标记了，我们将它们的数据交付给网络层、并滑动窗口。图11.22描述了这一情形（窗口大小有点问题？）。
  

【例11.18】这个例子与例11.3相似，都是一个帧丢失了。它描述了选择性重复在这个情况下如何工作。图11.23描述了这一情形。

一个主要的区别是计时器的数量。这里，每发送或重发一个帧都需要一个计时器，这就意味着计时器也要编号 $(0,1,2,3)$ 。

• 在第一个请求时，帧 $0$ 的计时器启动，并在这个帧的 ACK 达时停止。
• 第二个请求时，帧 $1$ 的计时器启动，当 NAK 到达时再重启，直到最后的 ACK 到达时才最终停止。
• 其他两个计时器在相应的帧发送时启动，而在最后的到达事件发生时停止。

在接收方站点，我们需要分辨帧的接收和向网络层交付帧。在第二次到达发生时，帧 $2$ 到达了并被保存和标记了（着色时隙），但是它不能被交付，因为帧 $1$ 丢失了。下一个到达事件，帧 $3$ 到达了并被保存和标记了，但是仍然没有帧能被交付。只有当最后一个到达事件发生，即帧 $1$ 的副本到达了，帧 $1,2,3$ 才能被交付给网络层。将帧交付给网络层有两个条件：第一，一组连续帧到达；第二，这组帧从窗口的起点开始。在第一个到达事件后，只有一个帧到达，它是从窗口的起点（此时是 $0$ ）开始的。最后一个到达事件后，有三个帧、且第一个是从窗口的起点（此时是 $1$ ）开始的。

另一个重要之处是，在第二个到达事件后，发送了一个 NAK 帧，但在第三个到达事件后没有发送 NAK ，虽然情况看上去一样。原因是：这个协议不想让网络因不必要的 NAK 帧和不必要的重发帧而拥堵。第二个 NAK 帧仍然会是 NAK1 ，以通知发送方再次重新帧 1 ，这已经由第一个 NAK 做过了。被发送的第一个 NAK 被记住（使用 nakSent 变量)，直到帧滑动后才会再次发送 The first NAK sent is remembered (using the nakSent variable) and is not sent again until the frame slides 。每一个窗口位置只发送一个 NAK ，其指明窗口中的第一个时隙 A NAK is sent once for each window position and defines the first slot in the window 。

接下来这点是关于 ACK 的。注意：这里只发送了两个 ACK ——第一个 ACK 只确认了第一个帧，而第二个确认了三个帧。在选择性重复协议中，只有当数据被交付到网络层时才发送 ACK 。如果属于 $n$ 个帧的数据在一次发送中被传输，那么对于所有帧也只发送一个 ACK ，而非多个 If the data belonging to n frames are delivered in one shot, only one ACK is sent for all of them 。

11.5.4 捎带

在这部分讨论的三个协议都是单向的：数据帧只朝一个方向流动，而诸如 ACK 和 NAK 等的控制信息则能反方向传输。在现实生活中，数据帧通常可以双向流动：从节点 $A$ 到节点 $B$ ，或者从节点 $B$ 到节点 $A$ 。这就是说控制信息也要能双向传输。一项称之为捎带技术的运用，提高了双向协议的效率。

当一个帧从 $A$ 到 $B$ 运载数据时，它也能从 $B$ 运载「关于帧到达或丢失的控制信息」，当一个帧从 $B$ 到 $A$ 运载数据时，它也能从 $A$ 运载「关于帧到达或丢失的控制信息」。在图11.24中，描述了使用捎带的回退 $N$ 帧ARQ的设计。

注意，每一个节点都有两个窗口：一个发送窗口和一个接收窗口。两者都需要使用计时器。两者都涉及三个类型的事件：请求、到达和超时。然而，此处的到达事件比较复杂——当一个帧到达时，每一端都要同时处理帧和控制信息。所以必须小心处理到达事件。请求事件只使用每一方的发送窗口，而到达事件既要用到发送窗口、也要用到接收窗口。

关于捎带的另一重要之处是，发送方和接收方要使用同一种算法 both sites must use the same algorithm 。该算法是复杂的，因为它要将两个到达事件合而为一。

11.6 高级数据链路控制

高级数据链路控制 High-level Data Link Control,HDLC 是一种面向位协议 bit-oriented protocol ，用于点对点和多点链路上的通信。它实现了前面讨论的ARQ机制。

11.6.1 配置和传输方式

HDLC提供了在不同的配置中都能使用的两种通用的传输模式：正常响应方式 normal response mode, NRM 和异步平衡方式 asynchronous balanced mode, ABM 。

1. 正常响应方式

在正常响应方式中，站点配置是不平衡的。有一个主站 primary station 和多个从站 secondary station 。主站能发送指令，而从站只能响应。如图11.25所示，NRM能在点到点和多点链路中使用。

2. 异步平衡方式

在异步平衡方式中，配置是平衡的。如图11.26所示，该链路是点到点的，且每个站点既有主站的功能、又有从站的功能（作为对等站点）。这是现在普遍应用的方式。

11.6.2 帧

为了提供支持「上述模式和配置中所有可能选项」所需的灵活性，HDLC定义了三种类型的帧：信息帧 information frames, I-frames 、管理帧 supervisory frames, S-frames 和无编号帧 unnumbered frames, U-frames 。每一种类型的帧，都在不同类型的信息传输中扮演信封的角色——信息帧用来传输用户数据及与用户数据相关的控制信息（捎带）；管理帧只用来传输控制信息；保留无编号帧作为系统管理之用，无编号帧携带的信息用来管理链路自身。

1. 帧的格式

在HDLC中，每个帧都最多可包含六个字段，如图11.27所示：开始标记字段、地址字段、控制字段、信息字段、帧校检序列字段、结束标记字段。在多帧传输中，一个帧的结束标记可以作为下一个帧的开始标记。

2. 字段

现在讨论各个字段，及它们在不同类型的帧中的作用。

• 标记字段：一个HDLC帧的标记字段是 $8$ 位序列，其模式是 $01111110$ ，既可作为一个帧的开始、也可以作为一个帧的结束，为接收方提供同步模式。
• 地址字段：一个HDLC帧的第二个字段包含了从站的地址。如果主站产生帧，它包含着一个"去往"地址；如果从站产生帧，它则包含一个"来自"地址。一个地址字段可能是一个字节、也可能是多个字节，这取决于网络的需求。
  • $1$ 字节可以最多定义 $128$ 个站点（$1$ 个位用于其他目的了）。如果地址字段只有一个字节，最后的 $1$ 位通常是 $1$ 。
  • 更大的网络需要多字节地址字段。如果地址字段多于一个字节，所有的字节除了最后一个字节外都以 $0$ 结束，只有最后一个字节以 $1$ 结束。中间的字节都以 $0$ 结束，是为了提示接收方，会有更多的地址字节到来。
• 控制字段：控制字段是帧的 $1$ 字节或 $2$ 字节段，用于流量控制和差错控制。这个字段中位的解释取决于帧的类型。以后讨论这种字段，以及它在每种类型的帧中的格式。
• 信息字段：信息字段包含了来自网络层的用户数据或者管理信息。不同的网络该字段的长度不同。
• 帧校验序列字段：帧校验序列字段 FCS 是HDLC的差错校验字段。它可以包含 $2$ 到 $4$ 字节的ITU-T CRC。

11.6.3 控制字段

控制字段决定帧的类型及其功能，因此要更详细地阐述这种字段的格式。其格式对于一种类型的帧是特定的，如图11.28所示。

1. 信息帧的控制字段

信息帧被设计用来运载来自网络层的用户数据。另外，它们也能包含流量控制和差错控制信息（捎带）。控制字段的子字段用来定义这些功能：

• 第一个位决定类型。如果控制字段的第一个位是 $0$ ，这就意味着这是一个信息帧。
• 接下来的三个位，称为 $N(S)$ 的，定义帧的序号。注意通过这三个字节，我们能定义的序号是从 $0$ 到 $7$ ，但是在控制字段为 $2$ 字节的扩展格式中，这部分也会大得多。
• 最后的三个位，称为 $N(R)$ ，在使用捎带时与确认号相对应。
• 在 $N(S)$ 和 $N(R)$ 之间的单个位称之为 $P/F$ 位。$P/F$ 虽是一个单个位，但是有双重用途。它只有被设定时（位 $=1$ ）才有意义，意味着轮询或终止——当帧由主站发送到从站时（即地址字段包含接收方的地址），它意味着轮询 poll ；当帧由从站向主站发送时，它意味着（即地址字段包含发送方的地址）终止 final 。

2. 管理帧的控制字段

无论当捎带 piggybacking 是不可能的还是不恰当时（例如，当站点没有自身的数据要发送时，或者站点需要发送一个指令或响应、而不是确认时），管理帧都用来进行流量控制和差错控制。

• 管理帧没有信息字段。如果控制字段的前两个位是 $10$ ，就说明这是一个管理帧。
• 最后三个位，称之为 $N(R)$ ，与确认 ACK 号或否定确认 NAK 号相对应，它取决于管理帧的类型。
• 称为编码的 $2$ 个位用来决定管理帧自身的类型。使用 $2$ 个位，我们能产生 $4$ 种类型的管理帧，如下所述：
  • 准备接收 Receive ready, RR 。如果编码的子字段是 $00$，这就是一个 $RR$ 管理帧。这种帧对一个或一群安全接收的帧加以确认。在这种情况下，$N(R)$ 的值定义了确认号。
  • 不准备接收 Receive not ready, RNR 。如果编码的子字段是 $10$，这就是一个 $RNR$ 管理帧。这是一类有附加功能的 $RR$ 帧，它对一个或一群帧的接收加以确认，并宣布接收方正忙、不能接收更多的帧，它通过要求发送方减速来实现拥塞控制机能。$N(R)$ 的值是确认号。
  • 拒收 Reject, REJ 。如果编码的子字段是 $01$ ，这就是一个 $REJ$ 管理帧。这是一个 $NAK$ 帧，但与适用于选择性重复ARQ协议中的不同。它是一个能在回退N帧ARQ协议中使用的 $NAK$ ，它能在发送方计时到时前，告知发送方最后一个帧丢失或者损坏了，以此来提高程序的效率。$N(R)$ 的值是否定确认号。
  • 选择性拒收 Selective reject, SREJ 。如果编码的子字段是 $11$ ，这就是一个 $SRJ$ 的管理帧。这是一个适用于选择性重复ARQ协议的NAK帧。注意，在HDLC协议中，使用术语选择性拒收而不是选择性重复。$N(R)$ 的值是否定确认序号。

3. 无编号帧的控制字段

无编号帧负责在连接的设备之间交换会话管理和控制信息。与管理帧不同，无编号帧包含一个信息字段，但是这个信息字段是用作系统管理的，而不是用户数据。

虽然与管理帧有相似之处，但无编号帧承载的多数信息包含在控制字段中的编码 code 中。无编号帧编码被分成两部分：在 $P/F$ 位前有一个 $2$ 位的前缀，在 $P/F$ 位后有一个 $3$ 位的后缀。总的而言，这两部分（$5$ 位）共能产生 $32$ 种不同类型的无编号帧。其中常用的一些无编号帧如表11.1所示。

【例11.9 连接/断开】图11.29描述了，如何使用无编号帧来建立连接和断开连接。

• 节点 $A$ 通过一组异步平衡方式 SABM 帧来请求连接，节点 $B$ 通过一个无编号确认 UA 帧给出一个肯定的响应。
• 通过这两个交换，数据能在两个节点之间传输（图中并未显示）。
• 数据传输完毕，节点 $A$ 发送一个断开连接 DISC 帧请求断开连接，节点 $B$ 通过一个无编号确认 UA 帧响应加以确定。
  

【例11.10 无差错捎带】图11.30描述了一个使用捎带的交换：

• 节点 $A$ 通过一个编号为 $0$ 、及紧随其后的编号为 $1$ 的信息帧来开始交换。
• 节点 $B$ 发送自身的一个信息帧，并捎带以上两个帧的确认。节点 $B$ 的第一个信息帧，同样编号为 $0$（$N(S)$ 字段），并在其 $N(R)$ 字段有一个 $2$ ，以此来确认对来自节点 $A$ 的帧 $0$ 和 $1$ 的接收，并提示接下来它等待帧 $2$ 的到达。
• 在从节点 $A$ 接收更多的帧之前，节点 $B$ 传输其第二个和第三个信息帧（编号 $1$ 和 $2$ ) 。它的 $N(R)$ 信息并没有因此变化：$B$ 的帧 $1$ 和 $2$ 提示节点 $B$ 仍然等待节点 $A$ 的帧 $2$ 的到达。
• 节点 $A$ 发送了它所有的数据。因此，它不能在一个信息帧上捎带上确认，故而发送一个管理帧以代之。编码 $RR$ 指明节点 $A$ 仍然处于准备接收状态。$N(R)$ 字段的数字 $3$ 告知 $B$ 帧 $0,1,2$ 已经被接收、且 $A$ 现在正等待的是帧 $3$ 。
  

【例11.11 有差错的捎带】图11.31描述了丢失了一个帧的交换：

• 节点 $B$ 发送了数据帧 $0,1,2$ ，但是帧 $1$ 被丢失了。
• 当节点 $A$ 收到帧 $2$ ，它丢弃了帧 $2$ 并为帧 $1$ 发送了一个拒收 REJ 帧。注意这是一个使用回退 $N$ 帧的协议，因此一个 REJ 帧有着如同 NAK 帧的特殊用途。在这里 NAK 要做两件事：它对帧 $0$ 的接收加以确定，并宣布帧 $1$ 及其后的任何帧都必须重发。
• 收到 REJ 帧后，节点 $B$ 重发了帧 $1$ 和 $2$ 。
• 节点 $A$ 通过发送一个确认号为 $3$ 的 RR 帧（ACK 帧）对接收加以确认。
  

11.7 点到点协议

虽然高级数据链路控制协议是点到点和多点配置都能使用的一个通用协议，但点到点访问最通用的协议还是点到点协议 Point-to-Point Protocol,PPP 。如今，成千上万的因特网用户，需要通过PPP来将他们的家庭电脑，与因特网服务提供商的服务器连接起来。大多数用户都有一个传统的调制解调器；它们通过电话线连接到互联网，这提供了物理层的服务。 但是，为了数据传输的控制和管理，在数据链路层也需要一个点到点协议。到目前为止，PPP是最通用的协议。

PPP提供以下服务：

1. PPP定义了设备间交换的帧的格式。
2. PPP定义了两台设备如何为链路的建立和数据的交换达成一致。
3. PPP定义了网络层数据如何封装到数据链路帧中。
4. PPP定义了两台设备如何互相鉴别。
5. PPP通过支持一系列不同的协议来提供多个网络层服务。
6. PPP提供多链路连接 multiple links 。
7. PPP提供网络地址配置 network address configuration 。当一个家庭用户在与因特网连接需要一个临时地址时尤其有用。

另一方面，为了使PPP尽量简化，有些功能被删除了：

1. PPP不提供流量控制。发送方能一个接着一个地发送帧，而不关心接收方是否超负荷。
2. PPP有一个很简单的差错控制机制。一个CRC字段用来检测差错。如果帧被损坏了，它便被无响应地丢弃；上层协议必须解决这一问题。缺乏差错控制和顺序编号，这可能会导致数据包被乱序接收。
3. 在多点配置中，PPP不提供高级的寻址机制来处理帧 PPP does not provide a sophisticated addressing mechanism to handle frames in a multipoint configuration 。

11.7.1 成帧

PPP是一个面向字节的协议，根据前面讨论的面向字节协议实现成帧。

1. 帧的格式

图11.32显示了一个PPP帧的格式。每个字段的描述如下：

• 标记。一个PPP帧以位模式为 $01111110$ 的一个 $1$ 字节标志开始和结束。虽然这个位模式与在HDLC中使用的相同，但仍然存在一个很大的区别，即：PPP是一个面向字节的协议，而HDLC是一个面向位的协议。这个标记作为字节处理，随后会加以解释。
• 地址。在这个协议中地址字段是常量 $11111111$（广播地址），协商时双方可同意省略这个字节。
• 控制。这个字段被设定为常量 $11000000$（效仿HDLC中的无编号帧）。正如随后会阐述的那样，PPP不提供任何流量控制，关于差错检测方面的差错控制也是有限的。这就意味着，这个字段是根本不需要的，而且在协商肘，双方能达成一致忽略这个字节。
• 协议。这一字段指明数据字段承载着什么：用户数据或者其他信息。下面将简短但详细地阐述这个字段。这个字段默认为 $2$ 个字节，但是双方可以同意只用一个字节。
• 有效载荷字段。这个字段承载着用户数据或其他信息，我们将简短的加以讨论。数据字段是一个字节序列，最大数量的默认值是 $1500$ 字节，但是通过协商这是可以变化的。
  如果标记字节模式 the flag byte pattern 出现在数据字段的话，数据字段需要字节填充（转义）。因为没有字段定义数据字段的大小，如果数据字段的大小小于默认的最大值或者协商的最大值的话，就需要填充 padding 了。
• 帧校验序列。帧校验序列是简单的 $2$ 到 $4$ 字节标准CRC。

2. 字节填充

正如之前讨论的那样，PPP和HDLC的帧格式的结尾有相似之处，但是前者是面向字节的协议，这点完全区别于后者。作为一个面向字节的协议，PPP的标记是一个字节，而且只要它出现在帧的数据部分，就需要被转义。转义字节是 $01111101$ ，表明每次类似标记模式的字节出现在数据部分，都要填充这个额外的字节来告知接收方「接下来的字节并不是标记」。

11.7.2 传输阶段

一个PPP连接可以通过转换阶段图 transition phase diagram 来说明（见图11.33）。

• 闲置 Dead 。在闲置阶段，链路没有被使用。没有活动的载体（在物理层）且线路是静默的。
• 建立 Establish 。当一个节点开始通信，连接就进入这个阶段。在这个阶段，双方就选项进行协商。如果协商成功，系统就进入鉴别阶段（如果鉴别是需要的话）或者直接进入联网阶段。稍后将讨论链路控制协议数据包 link control protocol packet ，用于此目的。此处交换了一些数据包。
• 鉴别 Authenticate 。鉴别阶段是可选的。两个节点在建立阶段，就可以决定是否跳过该阶段。然而，如果它们决定使用鉴别，它们会发送一些鉴别信息分组，以后会加以讨论。如果结果是成功的，连接进入联网阶段，否则，它将进入终止阶段。
• 联网 Network 。在联网阶段，将进行网络层协议的协商。因为PPP在网络层是支持多协议的，故PPP规定在网络层的数据进行交换之前，节点双方必须达成一个网络协定 a network layer agreement 。如果一个节点在网络层同时运行多个协议的话，接收方需要知道哪个协议用来接收数据。
• 打开 Open 。在打开阶段，将进行数据传输。当一个连接到了这个阶段，数据分组的交换就可以开始了。在这个阶段，连接将持续、直到其中一个终端希望终止这次连接为止。
• 终止 Terminate 。在终止阶段，终止连接。两端交换一些分组，以消除和关闭链路。
  

11.7.3 多路复用

虽然PPP是一项数据链路层协议，但PPP也使用其他一组协议来建立链路，对涉及的参与者加以鉴别，并承载网络层数据 establish the link, authenticate the parties involved, and carry the network layer data 。定义了三组协议使得PPP更为强大：链路控制协议 LCP 、两个鉴别协议 AP 和多个网络控制协议 NCP 。

任何时刻，一个PPP信息分组都能在它的数据字段中，携带来自这些协议的数据，如图11.34所示。注意，图中有一个链路控制协议、两个鉴别协议和多个网络控制协议。数据也可能来自不同的网络层。

1. 链路控制协议

链路控制协议 Link Control Protocol, LCP 的职责是建立、维系、确认并终止链路。它还提供协商机制来设置两个端点 endpoint 间的选项。在链路建立之前，链路的两个端点必须就选项达成一个协定。见图11.35。

所有的LCP分组，都位于PPP帧的有效载荷字段中，该PPP帧的协议字段，被设定为十六进制的 $0xC021$ 。

• 编码字段决定了LCP分组的类型。如表11.2所示，共有 $11$ 种类型的信息分组。
  
  分组可以分为三类：

  • 第一类，包括前四种分组类型，用于建立阶段的链路配置。
  • 第二类，包括类型 $5$ 和 $6$ ，在终止阶段用于链路终止。
  • 后五种分组用于链路监控和调试。

• ID字段包含一个将请求和应答相匹配的值 The ID field holds a value that matches a request with a reply 。一个端点将一个值插入这个字段，这个值便被复制到应答分组 reply packet 中。

• 长度字段决定了整个LCP分组的长度。

• 为了满足某些LCP分组的需求，信息字段包含诸如选项等信息。

在两个端点之间有许多能被协商的选项。选项插入配置分组的信息字段。这种情况下，信息字段被分为三段：选项类型，选项长度和选项数据。表11.3列示了其中最常用的一些选项。

2. 鉴别协议

在PPP中鉴别具有很重要的作用，因为PPP被设计用于拨号链路中，这就使得用户身份的鉴别十分必要。鉴别 Authentication 意味着，使一个需要访问一系列资源的用户的身份合法化 validating the identity of a user who needs to access a set of resources 。PPP有两种鉴别协议：口令鉴别协议和查询握手鉴别协议。注意这两种协议用于鉴别阶段。

(1) PAP

口令鉴别协议 Password Authentication Protocol, PAP 是一个两步骤的简单鉴别过程。

1. 需要访问系统的用户，发送一个鉴别身份（通常是用户名）和一个口令 password 。
2. 系统检测身份和口令的合法性，并选择接收连接或拒绝连接。

当一个PPP帧承载PAP分组时，协议字段的值是 $0xC023$。图11.36显示了PAP使用的三种类型的分组，以及它们如何交换。这三个 PAP分组分别是鉴别-请求，鉴别-确认和鉴别-不确认 authenticate-request, authenticate-ack, and authenticate-nak 。第一个分组被用户用来发送用户名和口令。系统用第二个分组来表示准许访问。系统用第三个分组来表示拒绝访问。

(2) CHAP

查询握手鉴别协议 Challenge Handshake Authentication Protocol, CHAP 是一个三步握手鉴别协议，比PAP更具安全性。在这种方式下，口令是保密的，它从未被发送到网上 。

1. 系统发送给用户一个包含查询值（通常是一些字节）的查询分组 challenge packet containing a challenge value 。
2. 用户应用一项预定义功能，根据查询值和用户自身的口令 the challenge value and the user's own password 产生一个结果。用户将结果放入一个响应分组，发送给系统。
3. 系统同样操作。它应用同样的功能，使用户的口令（系统已知的）和查询值产生一个结果。如果这个结果与响应分组中发送的结果相同，访问被允许。否则，访问被拒绝。

CHAP比PAP安全得多，特别是当系统不断地更换查询值时。甚至当入侵者得知查询值和结果时，口令始终是保密的（？）。图11.37显示了分组及其如何被使用。

CHAP分组以十六进制的协议值 $0xC223$ 封装在一个PPP帧中。有四种CHAP分组：查询、响应、成功或失败。第一种分组被系统用来发送查询值。第二种分组被用户用来返回计算结果。系统用第三种分组来表示准许访问，而用第四种分组来表示拒绝访问。

3. 网络控制协议

PPP是一个多网络层的协议，它能使用因特网限定的协议，如OSI 、Xerox 、DECnet 、AppleTalk 、Novel等来运载网络层数据分组。为了做到这一点，PPP为每一个网络协议，都界定了一个特定的网络控制协议 PPP has defined a specific Network Control Protocol for each network protocol 。例如， 互联网络协议控制协议配置「用来承载IP数据分组的链路」configures the link for carryingIP data packets ；Xerox CP配置用来承载Xerox协议数据分组的链路等。注意，没有一个网络控制协议承载网络层数据，它们仅仅是在网络层为进入的数据配置链路。

(1) IPCP

互联网络协议控制协议 Internet Protocol Control Protocol,IPCP 是一种网络控制协议。这个协议配置「用于承载因特网中IP分组的链路」。IPCP对我们而言有特殊的重要性。图11.3.8显示了一个IPCP分组的格式。注意协议字段的值是十六进制的 $0x8021$ 。

IPCP定义了七个分组，通过不同编码值加以区分，如表11.4所示。

(2) 其他协议

还有针对其他网络层协议的NCP协议。OSI的网络层控制协议的协议字段值是 $0x8023$ ；Xerox NS IDP控制协议的协议字段值是 $0x8025$ ，诸如此类等。其他协议的编码值和分组的格式与表11.4所示的相同。

4. 来自网络层的数据

当由一个NCP协议完成网络层确认后，用户可以交换来自网络层的数据分组。再次重申，不同的网络层有不同的协议字段。例如，如果PPP运载来自IP网络层的数据，字段值就是 $0x0021$（注意这个值最右边的三个数字跟IPCP的相同）。如果PPP运载来自OSI网络层的数据，协议字段值就是 $0x0023$ ，等等。图11.39显示了IP帧的格式。

11.7.4 多链路PPP

PPP最初是为了单通道点到点的物理链路设计的。在单个点到点链路中多通道 multiple channels 的实用性，促使了多链路PPP Multilink PPP 的发展。在这种情况下，一个PPP逻辑帧被分割成多个实际的PPP帧，逻辑帧的一段由一个实际PPP帧的有效载荷字段所承载，如图11.40所示。为了显示一个实际PPP帧正承载一个PPP逻辑帧的一段，协议字段被设置为 $0x003d$ 。这个新发展带来了复杂性。举例来说，必须在实际PPP帧上增加一系列数字，以说明这部分在逻辑帧中的位置。

【例11.12】让我们来看一下，一个网络层分组通过PPP连接传输的各个阶段。图11.41描述了这些步骤。

为了简化，我们假定数据从用户端向系统端单向运动（例如通过ISP发送一封邮件）。

• 前两个帧用作链路的建立。我们选择了两个选项（并没有显示在图中）；
• 使用PAP来鉴别并隐匿地址控制字段 suppressing the address control fields ，帧 $3$ 和帧 $4$ 用来鉴别。
• 帧 $5$ 和帧 $6$ 使用IPCP建立了网络层连接。
• 接下来的几个帧显示了封装在PPP帧的一些IP分组。系统（接收方）已经运行了一些网络层协议，但是它知道进入的数据必须交付给IP协议，因为在数据传输前使用的NCP协议是IPCP。
• 数据传输之后，用户终止了数据链路连接，这被系统所确认。当然，如果想要运行另一个NCP协议的话，用户和系统也可以选择终止网络控制协议IPCP，而维持数据链路层的运行。

这个例子是微不足道的，但是它指出了LCP、AP和NCP分组的相似之处。它同样描述了协议字段值和特定协议的编码数字。