点击查看第一章
点击查看第三章

第2章

Computer Networking Problems and Solutions: An Innovative Approach to Building Resilient, Modern Networks

数据传输中的问题与解决方案

学习目标
阅读完本章，读者应该能够：

• 理解数据列集的概念、各种不同的列集选项，以及各选项之间的权衡
• 在数据列集的上下文中理解字典、语法和元数据的概念
• 理解固定长度字段、类型长度值和共享数据字典等概念
• 理解差错检测与纠错之间的区别
• 理解数据传输中差错检测的基本概念
• 理解寻址与多路复用之间的关系
• 理解组播（又称多播）和选播背后的基本原理
• 理解流量控制的机制，包括基于窗口的流量控制

如果传输协议会做梦，它们会梦到应用程序吗？应该会梦到，因为网络的主要目的就是支持应用程序。网络对应用程序提供的主要支持就是把数据从一个进程（或处理器）转移到另一个进程（或处理器）。但是，数据是如何通过电缆、空气或光缆传输的呢？
也许可以从一个更熟悉的例子开始：人类语言。本书作者使用了排版格式、语言和词汇，使读者能够阅读和理解文字所呈现的信息。语言需要克服什么样的问题才能使交流、写作和阅读成为可能呢？
思想必须以一种允许接收者检索的形式被捕捉。在人类语言中，信息被包装成单词、句子、段落、章节和书籍。这样划分的每一层级都蕴含一些信息单元和组织系统。例如，声音或思想被封装成字母或符号，然后字母或符号组合成单词，单词组合成句子，等等。句子遵循一种特殊的语法形式，这样就可以从这些符号中解读出意义。这种将思想和信息编码成格式化的符号，允许读者（接收者）检索初始意义的过程，本书称之为数据列集（marshaling）。
列集被定义为将一组符号与特定意义联系起来的过程。元数据，即描述数据的数据，帮助你理解如何从数据流中解读出信息来。
在传输或接收中必须有一些管理差错的方法。假设你有一只喜欢玩球的宠物狗。有一天球从篮子里掉了出来，弹到了街上。狗追逐着，似乎正朝着迎面驶来的汽车跑去。此时，你会怎么做？也许你会喊“停下！”，然后是“别过去！”，或者是“别动！”。你会用几个导致相同行为（即让狗在跑到街上之前停住）的命令确保它能够正确地接收到，并且明白这条信息。你希望通过大声喊出多条信息来确保它没有误解你让它做的事情。
这实际上是一种形式的纠错（error correction）。在人类语言中存在着许多纠错。例如这句英文：“yu cn prbbly stll rd ths sntnce”，人类语言会忽略包含信息的细节，因此，一些遗漏的字母不会导致整个消息的丢失。这种“忽略细节”可以看作前向纠错的一种形式。然而，这并不是人类语言中唯一的纠错形式。人类语言也包含提问，通过提出疑问可以核实、验证或获取之前通过语言“传输”而缺失的信息内容或上下文。
使用空气声波作为单一媒介，在更大的人群中一定有办法与一个人或一小群人交谈。在一个人满为患的房间里，与其中一个人交谈是很平常的事情。人类语言已经建立在各种情形下处理这个问题的很多方法，比如直呼某人的名字，或者面对面说话时提高音量，以确保对面的人能够听到（换句话说，语言沟通可以是定向的）。与人群中的一个人或者特定一部分人讲话的这种能力就是多路复用（multiplexing）。
最后，必须能够控制对话的流程。对于一本书来说，这是一件简单的事情；作者分段写成文本，然后将其汇集成册，读者可以用不同的速度阅读或重复阅读。
可能没有人认为一本书会是一种“流量控制”的形式。其实，把想法付诸书面形式是一种有效的“流量控制”方式，即把发送者的速度（写作速度）与接收者的速度（阅读速度）分离开。口语中还有其他形式的流量控制，比如停顿“嗯”，或者在听众的眼神中看到迷茫困惑的时候（听众可能没有跟上说话者的推理线），甚至是一些暗示说话者应该放慢语速的肢体语言。
总之，成功的通信系统需要解决四个问题：

• 数据列集，把想法转换成接收方能够读懂的语法和符号。
• 管理差错，将想法从发送方正确地发送到接收方。
• 多路复用，允许公共传输介质或基础设施应用于大量不同发送方和接收方之间的对话。
• 流量控制，或者是具备这样的能力：在发送方发送更多信息之前，确保之前信息已经被接收方接收和处理。

下面将详细讨论这些问题以及在每个问题空间中的一些可用解决方案。

2.1　数字语法和数据列集

考虑一下读者阅读本书的过程。类比物理载体，读者检查一组印在纸上的墨水标记。这些标记代表某些符号（或者，如果你正在听这本书，即在白噪声背景下的某些声音），然后将它解释为字母。这些字母反过来可以通过空格和布局的规则组成单词，而单词通过标点符号和空格可以形成句子。
在这个过程的每一个阶段都有几种相互作用的东西：

• 可以施加信号的物理载体。这种以物理载体来表示信息的原理基于克劳德·香农（Claude Shannon）的信息论，不在本书的讨论范围之内；“拓展阅读”将为感兴趣的读者提供进一步的阅读资料。
• 将物理符号转换成第一层逻辑内容中信息单元的符号表示。当解释符号时，读者需要两样东西：字典，它描述了对应于某个物理状态所有可能的逻辑符号范围；语法，它描述了如何确定哪个逻辑符号与这个物理状态的实例相关联。这两样东西结合起来可以被描述为一种协议。
• 一种将符号转换成单词、将单词转换成句子的方法。同样，这里也包括两个组件：字典和语法。它们也可以被描述为一些协议。

随着向“协议栈上层”移动，从物理载体到字母，再到单词、句子等，字典将变得不那么重要，而语法（它允许你将上下文转换成意义）将变得更加重要。但这两个东西存在于协议栈的每一层的读/听过程中。字典和语法被认为是两种不同形式的元数据，可以用它们将物理表征转换成句子、思想、论点等。

2.1.1　数字语法和字典

人类语言和数字语言之间并没有太大的差别，比如读者现在正在阅读的就是人类语言。然而，数字语言并不被称为一种语言，它被称为一种协议。更正式地说：
协议就是将一种信息转换成另一种信息的字典和语法（元数据）。
当然，协议不能只在一个方向上工作，它既可以用于信息编码，也可以用于信息解码。语言可能是每天遇到的最常见的协议形式，但是也有许多其他形式的协议，比如交通标志，烤面包机、计算机和移动设备上的用户界面，以及每一种人类语言。
假如正在开发一个协议，这意味着主要工作将是开发一套字典和一套语法，有两种优化方法可供选择：

• 资源效率。有多少资源用于任意特定信息的编码？数据本身包含的元数据越多，编码的效率就越高—但是更多的信息解码工作也将依赖于字典。使用非常少的元数据（信号）编码大量信息的协议通常被认为是简洁的。
• 灵活性。在现实世界中，事情一直在变化。协议必须以某种设计形式来适应变化，希望这种形式不需要在“国旗日”（Flag Day）升级协议。

元数据权衡是在网络工程中发现的许多权衡之一：要么包含更多的元数据，允许协议更好地处理未来的需求；要么包含更少的元数据，从而使协议更加高效和简洁。一个很好的经验法则（也是本书多次提及的）就是：如果没有发现权衡，那么说明你观察得不够仔细（或者是不够用心）。

国旗日是什么？

如果需要把安装并运行在大量计算机上的协议升级到新版本，或者切换到不同的协议，那么你有三种选择。
首先，可以设计一个允许新旧版本重叠的协议（或多个协议），或者是这些协议可以在同一网络上同时运行。这种方案有时被称为“午夜航船”：新旧协议（或相同协议的不同版本）独立运行，互不干扰。
其次，可以选择特定的某一天（也可以是某一段时间，在某些情况下甚至是毫秒级）把旧协议切换到新协议。这一天就叫作“国旗日”。这个术语是如何与这个协议切换事件关联在一起的呢？在1966年，运行Multics（操作系统）的系统都需要从一个字符集定义切换到另一个字符集定义，如用ASCII 1967代替ASCII 1965。Multics系统管理员选择了一个假期，这样将有一整天的时间来替换软件，并保证系统在变更后的第一个工作日正常运行。他们选择的日子是1966年6月14日的美国国旗日。从此，“国旗日”这个术语永远与“要求系统中的每个主机（几乎）同时重启以确保正确运行”的系统变更关联起来了。

最著名的“国旗日”是在1983年，当时整个互联网从网络控制程序（Network Control Pro-gram，NCP）传输协议切换到传输控制协议（Transmission Control Protocol，TCP）。两个协议的切换过程需要一个互联网工程任务组（Internet Engineering Task Force，IETF）的RFC文档来描述和协调，这个文档就是RFC801。
最后，可以设计这样一个协议：协议的一个版本就可以包含相同信息的多个版本，每个版本的信息格式都不同。发送方可以用任意一种格式发送，接收方能够以任意一种格式解释数据。当所有系统都升级到新版本软件时，旧的编码方式可以被替换。这一机制严重依赖RFC760中的一项原则：
一般来说，在发送方的行为中，实现方式必须是保守的；而在接收方的行为中，实现方式可以是自由的。也就是说，发送方必须谨慎地发送格式正确的数据报，而接收方必须接收它能够解释的任何数据报（例如，不反对意义明确的技术错误）。

协议中的字典即面向符号和操作的数字模式表。也许最常用的数字字典是字符编码。表2-1复制了Unicode字符编码字典的部分内容。

表2-1　部分Unicode字符编码表

根据表2-1，假想计算机正在“阅读”一个字符串数组。如果数组中的数字是0023，那么计算机将打印（处理）为数字6；如果数组中的数字是0024，则打印数字7；如此等等。这个编码表，或者说是字典，把特定数字与字母表中的特定字符关联起来，就像字典把一个词与其一系列的含义关联起来。
计算机如何区分香蕉的价格和香蕉名字本身的字母（banana）呢？答案是通过信息的上下文。例如，香蕉的价格和名字可以存储为一个字符串或一系列字母；字符串变量类型可以提供元数据或上下文，表示这块特定内存位置的值应该作为字母来处理，而不是数字值。该元数据（由计算机安排）提供了协议的语法。
在网络协议中，字典通常表示为数据包所包含的任意特定字段，而语法通常表示为数据包的构建方式，或者是数据包的哪些位置包含哪些字段。
多种方法可用于构建字典和基本（一级）语法，以下几节将会讨论这些方法。

2.1.2　固定长度字段

固定长度字段（fixed length field）是最容易解释的字典机制。固定长度字段是指协议定义一组字段（field），包括每个字段的数据类型，以及每个字段的大小。这些信息被“合并”到协议定义中，每个实现都必须服从这些协议规范，从而实现互操作。图2-1说明了固定长度字段编码在OSPF协议（RFC2328）中的使用。

图2-1　OSPF协议规范中的固定长度字段定义

图2-1上方的一行数字表示数据包格式中的单个比特，每一行包含32位信息。比如第一行的第一个8位字段表示版本号，第二个8位字段总是5，后面的16位字段表示数据包长度。每一个字段在协议规范中都会被进一步详细定义，比如字段承载的信息，以及这些信息是如何编码的。例如：

• 版本号字段编码为无符号整数。这就是元数据，表示这个数据包所使用的字典和语法。如果需要变更数据包格式，则可以增加版本号，使得发送方和接收方在对数据包进行信息编码和解码时使用正确的字典和语法。
• 数字5表示该协议的数据包类型。这是字典的一部分，在标准文档的其他位置定义，因此在这个示例中它是作为一个固定值插入的。这个特殊的数据包是链路状态确认数据包（Link State Acknowledgment Packet）。
• 数据包长度被编码为一个无符号整数，表示完整数据包中包含八位组的数量。这使得数据包大小可以根据所需携带信息的多少而变化。

固定长度字段的格式有几个优点。首先，对不同的数据包来说，数据包内任何一片信息的位置都是相同的。这意味着可以很容易地优化信息编解码的代码（根据数据包格式设计的代码）。例如，处理固定长度数据包格式的一种常见方法是在内存中创建一个与包格式完全匹配的数据结构；当从网络上读取数据包时，数据包可以被简单地复制到这个数据结构中，然后就可以通过操作数据结构直接读取数据包中的字段。
固定长度的协议格式往往比较简洁。对数据进行编解码所需的元数据信息以协议规范的形式“在协议之外”传输。数据包本身只包含值，而不包含有关值的任何信息。另一方面，固定长度格式可能会浪费大量空间，因为总要缓存一些字段，使得数据包保持相同的长度。例如，十进制数字1可以用一个二进制数字表示（1位），而4则需要3个二进制数字（3位）；如果一个固定长度的字段必须能够表示0到4之间的任何数字，那么它至少需要3位长。这样当表示较小的十进制数时，其中的两位会被“浪费”。
为了提高处理速度，协议字段的大小需要与通用处理器的内存边界对齐。固定长度格式也往往因此而浪费空间。例如，字段所需数值是从0到3，即使它只需要两位来表示所有可能值，为了获得更快的内存处理，该字段也可能被编码为8位字段（一个完整的八位组），以确保后面的字段总是与八位组的边界对齐。
灵活性是固定长度编码的问题所在。如果某个字段在原始规范中定义为8位的值（单个八位组），则没有简单的方法来修改该字段的长度以支持新的需求。在固定长度编码方案中，解决这个问题的主要方法是通过版本号。如果字段的长度必须更改（无论是变大还是变小），则版本号将需要变更以支持新字段长度的数据包格式。这使得协议实现可以使用旧格式，直到网络中的所有设备都被升级到支持新格式。一旦所有设备都升级，整个系统就可以切换到新的格式。

2.1.3　类型长度值

类型长度值（Type Length Value，TLV）格式是另外一个广泛使用的关于数据列集问题的解决方案。图2-2显示了一个中间系统到中间系统（Intermediate System to Intermediate System，IS-IS）的路由协议示例。

图2-2　IS-IS系统中的一个TLV格式示例

在图2-2中，数据包由报头和一组类型长度值构成。报头通常是固定长度，每个类型长度值都基于各自的类型码进行格式化。在图中，显示了两种类型长度值（在IS-IS中有许多其他类型，这里的两个仅用于举例说明）。第一个类型是135，它携带IPv4信息。这种类型有几个字段，其中一些是固定长度，比如metric（度量）字段。然而，其他的则是可变长度，如prefix（前缀）字段，该字段的长度取决于类型长度值中的其他字段值，例如，对于prefix字段，其prefix length字段决定了prefix字段的长度。还有一些子TLV，它们的格式类似，并带有与IPv4相关的信息。236类型与135类型类似，但236类型携带的是IPv6，而不是IPv4信息。
从本质上讲，类型长度值可以看作由更大数据包传输的一套完整的自包含信息。类型长度值由三部分组成：

• 类型码：描述数据的格式。
• 长度：描述数据的总长度。
• 值或数据本身。

基于类型长度值的格式不像固定长度格式那样简洁，因为数据包本身需要携带更多的元数据。数据携带的类型和长度提供了在字典中查找格式信息的位置，以及要使用的语法信息（每个字段的格式等）。类型长度值格式牺牲简洁性，以换取不需要在网络上传输额外元数据，这种权衡获得了以下能力：不需要对设备进行升级就可以改变协议所携带的信息格式，或者允许某些实现选择不支持所有可能的类型长度值。
在网络协议中，类型长度值通常被认为是一种非常灵活的数据列集方式，这个概念几乎无处不在。

2.1.4　共享对象字典

固定长度字段的一个主要问题是字段定义的固定性。如果想要修改一个固定长度字段的协议，需要增加版本号并修改数据包；或者必须创建一个新的数据包类型，并为字段设置不同的编码。TLV格式通过数据传输中自包含元数据的方式解决了这一问题，付出的代价是携带更多的信息且降低了简洁性。共享编译字典试图通过将字典放在共享文件（或库）而不是规范中来解决这个问题。图2-3说明了这个过程。

图2-3　共享编译字典

在图2-3中，流程从开发人员构建数据结构开始，这个数据结构列集了一些特定的数据，然后通过网络传输。一旦数据结构已经建立，它就被编译成一个函数，或者复制到库函数中（1），然后复制到接收方（2）。接收方使用这个库来编写一个应用程序以处理这些数据（3）。对于发送方，原始数据通过格式编码（4），再通过网络协议发送给接收方（5），接收方使用数据格式的共享副本（6）来解码数据，并把解码后的信息传递给接收方的应用程序（7）。
这种系统结合了类型长度值模型的灵活性和固定字段协议的紧凑性。虽然字段是固定长度的，但是字段定义允许快速、灵活的更新（当列集的格式需要变更时）。只要共享库与使用数据的应用程序分离，就可以通过发布原始数据结构的新版本来更改字典和语法。
如果需要分发新版本的数据结构，是否还需要国旗日呢？不需要。如果数据结构中包含一个版本号，那么接收方可以把接收到的数据与正确的数据结构相匹配，系统可以同时存在多个版本的数据结构。一旦不存在使用旧数据格式的发送方，旧的结构就可以安全地在整个系统中丢弃了。
注意：gRPC是一个共享编译库列集系统的例子，详细内容可参见“拓展阅读”部分的参考资料。
注意：固定格式和TLV系统依赖于开发人员对规范的阅读，并且以共享语法和字典的形式编写代码，而本节所述的共享数据结构系统依赖于以其他某种方式分发的共享字典。有许多不同的方法可以做到，例如，一个新版本的软件可以分发给所有的发送方和接收方，或者以某种形式的分布式数据库来确保所有发送方和接收方都收到更新后的数据字典，或者应用程序中专门管理列集数据的部分可以是分布式的，并且与生成和使用数据的应用程序搭配。这种类型的系统在初始会话设置时发送共享字典。所有这些方法都是可行的，其细节超出了本书的讨论范围。

2.2　差错

世界上没有完美的数据传输介质。如果传输介质是共享的，比如射频（RF），就有可能会发生干扰，甚至是数据报冲突。这是不止一个发送方试图同时传输信息的情形，其结果是一个不能被预期接收方所理解的歪曲信息。即使是一种专用介质，如点对点的海底光缆，也会因电缆退化或端点事件而出现错误，甚至是一些看似不正常的事件，如太阳耀斑引起的辐射，进而会干扰通过光缆传输的数据。
网络传输必须解决的两个关键问题是：

• 如何检测数据传输中的错误？
• 对于数据传输中的错误，网络应该如何处理？

下面几小节将讨论这些问题的一些可能答案。

2.2.1　差错检测

无论是传输介质发生故障，还是传输路径上交换设备的内存出现损坏，或者是其他什么原因，处理差错的第一步都是对差错进行检测。当然，问题是当接收方检测接收到的数据时，没有任何参照物可用于比较，以便发现差错。
奇偶校验是最简单的检测机制，有两个互补的奇偶校验算法。对于偶校验，每个数据块都会添加一个附加的位。如果数据块中位数总和是偶数，也就是说数据块中有偶数个1，那么附加的位将被设置为0。这保持了数据块的偶校验状态。如果1的位数总和是奇数，则附加的位被设为1，它将整个块设置为偶校验状态。奇校验使用相同的位附加策略，但它要求数据块具有奇数校验位（奇数个1）。
作为一个例子，计算以下4字节的偶校验和奇校验：

只要简单地数一下数字，就会发现这些数据中有14个1和18个0。为了提供使用奇偶校验的差错检测，可以向数据中添加一位，使新增加的位总数要么为偶数（偶校验），要么为奇数（奇校验）。例如，如果想在本例中添加一个偶校验位，则附加位应该设置为0，这是因为1的数量已经是一个偶数了。将附加的奇偶校验位设为0不会再增加1，因此不会改变1的总数是偶数还是奇数。对于偶校验，最终的比特集合是：

另一方面，如果想在这组比特上添加一个奇校验位，需要使附加的奇偶校验位为1，所以现在有15个1而不是14个1。对于奇校验，最终的比特集合是：

为了检查数据在传输过程中是否被损坏或更改，接收方只需注意是否使用了偶校验或奇校验，使用加法计算一下“1”的数量，并丢弃奇偶校验位。如果“1”的数量与使用的奇偶校验（奇数或偶数）不匹配，就说明数据被破坏了；否则，数据似乎与最初传输的数据相同。
当然，这个新的附加位是随着原始数据一起传输的。如果奇偶校验位本身被破坏了，怎么办？这还是可以工作的。假设使用偶校验，并且发送方发送：

然而，接收方收到：

奇偶校验位本身已经从0翻转到了1。接收方将计算“1”的个数，确定有15个；因为正在使用偶校验，即使它没有出错，收到的数据也会被标记为有差错。奇偶校验对失败可能过于敏感，但在进行差错检测时，宁求稳妥。
奇偶校验有一个问题：它只能在传输信号中检测到一位的翻转。例如，使用偶校验，并且发送方发送：

然而，接收方收到：

接收方将计算“1”的数量，为12；由于系统使用偶校验，接收方将假定数据是正确的并正常处理。然而，用粗体标出的两个部分都被损坏了。在任何组合中有偶数位被修改时，奇偶校验不能检测到变化；只有当更改涉及奇数位时，奇偶校验才能检测到数据的变化。
循环冗余校验（Cyclic Redundancy Check，CRC）可以通过在整个数据集上使用循环除法（而不是加法），一次一小块，来检测在数据传输中更大范围的数据改变。研究一个例子是理解CRC如何计算的最好方法。CRC计算以一个多项式开始，如图2-4所示。
对如图2-4所示的三项多项式x3+x2+1，展开以包括所有项—包括系数为0的项（因此无论x的值是多少，都不影响计算的结果）。然后四个系数作为二进制计算器，它将被用来计算CRC。

图2-4 一个用来计算CRC的多项式

为了执行CRC，从原始的二进制数据集开始，并添加三个额外的位（因为原始多项式没有系数，有三个项，因此被称为3位CRC校验），如下所示：

这3位需要确保原始数据中的所有位都包含在CRC中。当CRC在原始数据中从左到右移动时，只有在填充位包含的情况下，原始数据中的最后一位才会被包含。现在从左4位开始（因为4个系数表示为4位），使用异或（XOR）操作将最左边位与CRC位进行比较，并保存结果，如下所示：

注意：如果两个二进制数字相同，则它们的异或结果为0，否则为1。
被称为除数的校验位一位一位地往右边移动（这里可以跳过一些步骤），重复操作，直至到达数字的末尾：

CRC在最后的三位中，这三位最初是填充位—这是在原始数据和原始填充之间移动相除的“余数”。对于接收方来说，通过CRC位（在本例中为101）和使用原始的除数来确定数据是否被更改很简单，如下所示：


如果数据没有更改，则此操作的结果将始终为0。如果改变了一位，结果将不会是0，如下所示：

CRC似乎是一个复杂的操作，但它发挥了计算机的长处—有限长度的二进制运算。如果CRC的长度与普通处理器中标准的寄存器相同，比如8位，计算CRC将是一个相当简单和快速的过程。CRC校验具有抗多位变化的优点，不像之前描述的奇偶校验。

2.2.2　纠错

然而，检测差错只能解决问题的一半。一旦检测到差错，传输系统该怎么办？本质上有三种选择。
传输系统可以简单地把数据丢弃。在这种情况下，传输实际上是将处理错误的责任转移到更高级别的协议或者应用程序本身。由于一些应用程序可能需要一个没有错误的完整数据集（比如一个文件传输系统，或者一笔金融交易），它们可能会有一些方法来发现丢失的数据并重传。不关心少量数据丢失（比如语音流）的应用程序可以简单地忽略丢失的数据，在接收方重新构造信息，并尽可能地提供丢失的信息。
传输系统可以向发送方发出错误信号，并让发送方决定如何处理这些信息（一般来说，错误数据将被重新传输）。
传输系统可以在原始传输中包含足够的信息并确定错误发生在哪里，并试图纠正它，而不是丢弃数据。这称为前向纠错（Forward Error Correction，FEC）。汉明码（Hamming code）是最早出现也是最容易解释的FEC机制之一。最好用例子来说明汉明码，如表2-2所示。

表2-2　汉明码的解释

在表2-2中：

• 12位空间中所有为2的幂次方位（1、2、4、8等）和第一位作为奇偶校验位。
• 使用FEC保护的8位数字（10110011）已在剩余的空间上分布。
• 将每个奇偶校验位设为0，然后通过计算二进制位数字与奇偶校验位的位设置相同的位置中“1”的数量，来计算每一个奇偶校验位的奇偶性。具体地说：
• P1在位数中设置了极右位（即最右位为1），在奇偶校验计算中也包含了编号空间中设置了极右位的其他位元组（请参阅表中的第二行，可查找设置了极右位数字的所有位位置）。它们在P1行中用一个“X”来表示。“1”的总数是奇数（3），所以P1位被设为1（这个例子使用偶校验）。
• P2设置了右边的第二位，在编号空间中设置了右边第二位的位都被包含在奇偶校验中，如表中P2行中的“X”所示。“1”的总数是偶数（4），所以P2位被设为0。
• P4设置了右边的第三位，所以其他在其位置编号中设置了第三位的位如P3行中的“X”所示。在标记的列中有奇数个1，所以P4奇偶校验位设置为1。

为了确定是否存在已经更改了的任何信息，接收方可以按照与发送方计算的相同方式检查奇偶校验位，任何集合中1的总数应该是偶数（包括奇偶校验位）。如果其中一个数据位被翻转，接收方就永远不会发现奇偶校验错误，因为数据中的每一位都被多个奇偶校验位所覆盖。为了发现哪个数据位是不正确的，接收方将错误的奇偶校验位进行相加，结果就是被翻转位的位置。例如，如果位置9，也就是第五个数据位被翻转，那么奇偶位P1和P8都是错误的。在这种情况下，8+1=9，所以位置9中的位是错误的，翻转它即可修正数据。如果只有一个奇偶校验位出错，如P1或P8，那么它就是被翻转的奇偶校验位，而数据本身是正确的。
虽然汉明码很巧妙，但是仍有很多的翻转模式无法被检测到。一个更现代的编码，如Reed-Solomon，可以检测和修正更大范围的错误条件，同时只向数据流中添加很少的附加信息。
注意：在通信世界中有大量不同种类的CRC校验和纠错码。CRC校验根据检查使用的比特数量（填充的比特数量，或者更确切地说是多项式的长度）来分类，甚至在某些情况下，根据特定的应用程序来分类。例如，通用串行总线使用5位CRC（CRC-5-USB）；全球移动通信系统（GSM）是一种广泛应用的蜂窝电话标准，使用CRC-3-GSM；码分多址（Code Division Multi-Access，CDMA）是另一种广泛使用的蜂窝电话标准，采用CRC-6-CDMA2000A、CRC-6-CDMA2000B和CRC-30；一些车域网络（Car Area Network，CAN）用来连接汽车的各种部件，使用CRC-17-CAN和CRC-21-CAN。这些不同的CRC函数中有些不是单个函数，而是一个函数类或函数族，其中包含许多不同的代码和选项。

2.3　多路复用

假设你走进一个房间，大声喊道“乔！”，你的朋友乔转过身，开始与你谈论政治和宗教（当然，在任何有礼貌的谈话中，这两个话题都是禁忌话题）。即使在许多人同时使用媒介（传播声音的空气）进行对话时，你也可以使用相同媒介与某人对话，这样的一种能力在网络工程中就是多路复用。更正式的表述为：
多路复用即允许连接到网络的多个实体通过共享网络进行通信。
为什么在这里使用实体而不是主机呢？回到“与乔对话”的例子中，想象一下你和乔交流的方式是通过他的一个十几岁的孩子，而这个孩子只会使用文字（从不说话）。事实上，乔是一个有几百到几千人的家族中的一部分，这个家族的所有交流都必须通过这个少年。家族的每个人都同时进行多个对话，有时候与同一个人聊不同话题。这个可怜的孩子必须很快地书写，并且在他的脑子里保留很多信息，比如“乔和玛丽有四次对话”，并且必须把每一次对话的信息完全隔开。这更接近于网络中多路复用的工作原理。考虑：

• 可能有数百万（或数十亿）台主机连接到一个网络，所有主机共享同一个物理网络，彼此通信。
• 每台主机实际上包含许多个应用程序，可能是数百个，每一个应用程序都可以与连接到网络的任何其他主机上的数百个应用程序进行通信。
• 实际上，每一个应用程序都可以与运行在网络中的其他主机上的任何其他应用程序进行多次通信。
  如果这听起来有点复杂，那是因为它本身就很复杂。本节需要回答的问题是：

如何有效地在计算机网络上进行多路复用？
下面将讨论在这个领域中最常用的解决方案，以及与这个基本问题有关的一些有趣问题，如多播和选播。

2.3.1　设备与应用程序的寻址

计算机网络使用一系列层级结构组织的地址来解决这些问题。如图2-5所示。

图2-5　网络中多个层级实体之间的寻址

在图2-5中，展示了四个层级的地址：

• 在物理链路层，有接口地址，允许两个设备独立地寻址一个特定设备。
• 在主机级别，有主机地址，允许两台主机直接寻址特定主机。
• 在进程级别，有端口号，与主机地址相结合，允许两个进程寻址特定设备上的特定进程。
• 在会话级别，用源端口、目的端口、源地址和目的地址的组合唯一标识特定会话或数据流。

这个图和解释看起来很简洁。但是在现实生活中，事情要复杂得多。在最广泛部署的寻址方案—IP协议中，没有主机级别地址。相反，每个接口都有逻辑和物理地址。
注意：IP地址和IP寻址将在第5章详细讨论。
多路复用和多路复用标识符（地址）在网络中按层级结构进行堆叠。
注意：将层间两种地址关联起来的机制将在第6章详细讨论。
但是，在某些情况下，希望将流量一次发送给多个主机。在这些情况下可选择多播和选播。下面将讨论这两种特殊的寻址方式。

物理链路域、广播域和故障域

当考虑广播域和物理连接性的概念时，图2-5所示的简洁模型将更加复杂。一些媒体类型（特别是以太网，在第4章将给予更详细的介绍）被设计成使得连接到相同物理链路的每个设备都能接收传输到物理媒介的每个数据包，而连接到物理线路的物理接口只是忽略未寻址到本地址的数据包。然而，在现代网络中，以太网的物理连接很少允许每个设备接收其他设备的数据包；相反，在网络的中间有一个交换机，它阻止未被指定到特定设备的数据包在连接到该主机的物理线路上传输。
然而，在这些协议中，存在为数据包预留的显式地址。这些数据包要么在没有交换机的情况下被传输到应该接收所有数据包的主机上，要么被所有主机接收和处理。通常，这些地址都是全0或者全1地址。这种协议被称为广播。任何接收并处理广播包的设备，都被称为发送方的广播域。传统上，广播域的概念与故障域密切相关，因为网络故障一旦影响广播域中的一个设备，通常会影响广播域中的每个设备（有关故障域的更多信息，请参见第23章）。

如果发现这些让人困惑，不要惊讶，因为事实上这本身就令人相当困惑。广播和广播域的基本概念仍然存在，且对于理解网络的运行仍然很重要，但是在某些情况下，该术语的含义可以改变，甚至变得不适用。在考虑任何情况时都要小心，以确保真正理解了这些广播域的真正含义，以及具体的技术如何影响物理连接、寻址和广播域之间的关系。

2.3.2　多播

注意：以下简短的解释无法真正地对构建多播树的整个解决方案做出公正的判断，请参阅本章末尾的“拓展阅读”，以了解该领域的更多内容。
如果你有一个如图2-6所示的网络，需要A把同样的内容分配给G、H、M和N，你会怎么做呢？

图2-6 多播示例

可以生成4个副本，通过正常的单播转发将一个数据流发送给每个接收方，或者可以将流量发送到网络知道如何复制数据流的单个地址，这样所有4台主机都会收到一个副本。后一种选择称为多播，即使用单个地址将流量传输到多个接收方。在多播中需要解决的关键问题是在流量通过网络时转发和复制流量，从而对数据流感兴趣的每个接收方都将收到一个副本。
注意：对从多播源接收一组数据包感兴趣的一组设备称为一个多播组。这可能有点令人困惑，因为用于描述多播流的地址在某些情况下也被称为多播组。这两种用途实际上是可以互换的，因为对接收特定多播数据包感兴趣的设备集合将加入多播组，这实际上意味着侦听一个特定的多播地址。
注意：如果多播流量是双向的，这个问题就更难解决了。例如，假设在图2-6所示的网络中每台主机（除了N）都需要构建一个多播组，并且传输到多播组地址的任何多播都被传送给多播组中的每台主机。
多播需要解决的关键问题可分为两个问题：

• 如何发现哪些设备想要接收一份被传送到多播组的传输副本？
• 如何确定网络中哪些设备应该复制流量，以及它们应该在哪个接口上发送副本？

一种可能的解决方案是使用本地请求来构建一棵树，通过该树可以在网络中转发多播流量。在协议无关多播（PIM）中，这种系统的一个例子是稀疏模式。在这个过程中，每个设备向它感兴趣的多播流发送一个连接消息，这些连接在网络中逆流传递，直到到达发送方（通过多播流发送数据包的主机）为止。图2-7用于说明此过程。

图2-7 稀疏模式的传播

在图2-7中：
1）A将一些流量发送到多播组（地址），称之为Z。
2）N希望收到Z的副本，因此向它的上游路由器D发送一个请求（连接），以获取该流量的副本。
3）D没有这个流量的源，因此向它所连接的路由器发送一个请求，以获取该流量的副本。在这种情况下，D发送请求的唯一路由器为B。
在每一跳上，接收请求的路由器把接收到请求的接口放到它的出站接口列表（Outbound Interface List，OIL）中，并开始转发其他接口上接收的特定多播组的流量。通过这种方式，可以构建从接收方到流量发起者的路径，这被称为反向路径树。
用于发现哪个主机对接收特定多播组流量感兴趣的方案是通过某种注册服务器实现的。每个想要接收数据流副本的主机都可以通过服务器注册它的请求。主机可以通过多种方式发现注册服务器的存在，包括：

• 像域名一样处理多播组地址，通过查询多播组地址查找注册服务器的地址。
• 建立和维护一个列表或映射，将多播组映射到本地表中的服务器。
• 使用某种形式的散列算法根据多播组地址计算注册服务器。

注册可以由服务器路径上的设备来追踪，或者，一旦知道了接收方和发送方，服务器就可以向路径上适当的设备发信号，表明这些设备应该为复制和转发数据包配置哪些端口。

2.3.3　选播

多路复用解决方案面对的另一个问题是能够使用单个地址在多台主机上实现特定的服务实例。如图2-8所示。

图2-8 一个选播的例子

在图2-8中，需要设计某个服务S，以提高其性能。为了实现这个目标，已经创建了服务的第二个副本，两个副本分别命名为S1和S2。服务的两个副本在两台服务器（M和N）上运行。选播需要解决的问题是：
如何将客户端定向到服务的最优实例？
解决这个问题的一种方法是将所有客户端引导到一个设备上，并让负载均衡器根据客户端的拓扑位置、每台服务器的负载和其他因素将流量分配给服务器。然而，这个解决方案并不总是理想的。例如，如果负载均衡器无法处理那些想要访问服务副本的客户端生成的所有连接请求，该怎么办呢？为了让负载均衡器跟踪各个服务副本的健康状况，将向网络添加哪些类型的复杂性呢？
注意：第7章将讨论负载均衡。
选播通过为服务的每个副本分配相同的地址来解决这个问题。在图2-8所示的网络中，M和N将使用相同的地址来提供对S1和S2的可达性。M和N将使用不同的地址，以对其他服务和设备本身通告可达性。
H和K（在M和N之外的第一跳路由器）将在网络上通告这个相同的地址。当C和D接收到相同目的地的两条路径时，它们将根据度量标准选择最近的路由。在这种情况下，如果每一个链路在同一个网络中配置相同的度量，那么C将负责安排直接来自A的流量，服务地址指向M。另一方面，D将负责安排直接来自B的流量，指定服务地址为N。如果两个实例的服务是相同的距离，将发生什么呢?路由器将使用本地散列算法选择两条路径中的一条。
注意：请参阅第7章以了解关于等价多路径交换的更多信息，以及如何使用散列以确保流中的每个数据包使用相同的路径。即使是在互联网上，对于使用任何有状态协议的选播解决方案来说，路由都是足够稳定的。
选播通常用于大规模的服务，这些服务必须提供大量服务器以支持单个服务。有以下几个例子：

• 大多数大型域名服务（DNS）系统服务器实际上是一组可以通过选播地址访问的服务器。
• 许多大型的基于Web的服务，特别是社交媒体和搜索，在许多边缘设备上实现了单个服务。
• 内容缓存服务在分发信息和提供信息服务的时候经常使用选播。

只要设计正确，选播就能够提供有效的负载均衡以及最佳的服务性能。

2.4　流量控制

举个不太恰当的例子，还记得你的姑婆（或者远房表妹）吗？她说话特别快，你根本听不懂她在说些什么。一些计算机程序也会因为太快而让人不懂。如图2-9所示。
在图2-9中：

• 在T1时刻，发送方正在发送大约4个数据包，接收方一次处理3个数据包。接收方有一个容量为5的数据包缓冲区来存储未处理的信息，缓冲区中已有2个数据包。
• 在T2时刻，发送方发送了4个数据包，接收方处理了3个数据包，接收方的缓冲区现有3个数据包。
• 在T3时刻，发送方发送了4个数据包，接收方处理了3个数据包，接收方的缓冲区现有4个数据包。
• 在T4时刻，发送方发送了4个数据包，接收方处理了3个数据包，接收方的缓冲区现有5个数据包。

发送方发送的下一个数据包将被接收方丢弃，因为在接收方处理数据包时，接收缓冲区已经没有存储空间了。这里需要的是某种反馈回路，以告诉发送方降低发送数据包的速度，如图2-10所示。
这种反馈回路要求接收方和发送方之间存在隐式或显式的信令通知。其中，隐式信令部署更广泛。在隐式信令中，发送方将基于对数据流的一些观察，认为数据包没有被接收。例如，接收方会确认随后数据包的接收，或者接收方只是不确认某个特定数据包的接收，或者接收方在很长一段时间内（基于网络条件）不发送任何消息。在显式信令中，接收方以某种方式直接通知发送方一个特定的数据包没有收到。

图2-9　缓冲区溢出的例子

图2-10　控制数据包流量的一个反馈回路

2.4.1　窗口机制

窗口机制和隐式信令组合在一起，是目前在实际网络中应用最广泛的流量控制机制。窗口机制主要包括以下内容：
1）发送方将一些信息发送给接收方。
2）在确定信息是否被正确接收之前，发送方等待。
3）如果接收方在特定时间内确认数据收到，则发送方发送新信息。
4）如果在特定时间内没有收到接收方的确认消息，则发送方重传信息。
隐式信令通常与滑动窗口一起使用，只是不确认数据包的接收。有时会使用显式信令，如接收方知道它已经丢弃一个数据包、接收到的数据包有错误、接收到的数据乱序或者数据由于某种原因被损坏。图2-11展示了最简单的窗口协议方案—单个数据包窗口。
在单数据包窗口（有时也称为ping pong）中，发送方只在接收方确认上一个数据包收到后才发送下一个数据包（如图2-11中的“ack”所示）。如果数据包未收到，接收方不会确认。发送数据包时，发送方设置一个计时器，通常称为重传定时器；一旦这个定时器被唤醒（或到期），发送方就假设接收方没有收到数据包并重传该数据包。

图2-11 单个数据包窗口机制

发送方要等多久？这个问题的答案有很多，但本质上有两种，一种是发送方可以等待一个固定的时间，另一种是它可以根据以前的传输和网络条件推断出的信息来设置定时器。一个简单（且朴素）的方案是：

• 测量数据包发送和接收确认之间的时间长度，称为往返时间（RTT，通常用小写字母rtt表示）。
• 将重传定时器设置为这个数字，再加上少量的缓冲时间，以涵盖rtt在多个传输过程中的变化。

注意：关于计算重传定时器的各种方法的更多信息请参考第5章。
接收方也可能会收到相同信息的两份副本：
1）发送方A发送一个数据包并设置它的重传定时器。
2）B收到数据包，可能出现以下情况：
a）由于内存不足、处理器利用率过高或其他原因，无法确认数据包的接收。
b）接收方发送一个确认，但确认消息被网络设备丢弃。
3）重传定时器超时，所以发送者会重传数据包的另一个副本。
4）B收到相同信息的第二个副本。
接收方如何检测重复数据呢？一种似乎可行的方法是，接收方比较接收到的数据包，看看是否有重复的信息。但这种方法并不总是可行的，也许发送方就是要发送两次相同的信息。检测重复信息的常用方法是在传输的数据包中包含某种序列号。发送方在构建每个数据包时给出一个唯一的序列号，如果接收方收到两个相同序列号的数据包，则认为数据是重复的，并丢弃重复的数据。
对于一个大小为1的窗口或者一个ping pong，每一组数据传输都需要经历一个发送方和接收方之间的往返，这通常会导致非常慢的传输速率。如果把网络看作端到端的铁路轨道，每一个小数据包都是一节火车车厢，最有效的轨道使用方式和具有最快传输速度的情况就是轨道总是跑满火车的时候。但是，对于网络来说，这在物理上是不可能的。因为网络是由许多发送方和接收方共用的，并且总是存在一些网络环境因素，从而阻止网络利用率达到100%。这里存在一个平衡，即一次发送更多数据包的高效和高速率与一次发送较少数据包（例如只发送一个）的多路复用和“安全”之间的平衡。如果可以用某种方式计算一个正确的平衡点，那么一个固定窗口大小的流控方案就可以很好地发挥作用。图2-12说明了这种方案。

图2-12　一个固定窗口的流控示例

在图2-12中，假设窗口大小固定为3个数据包：

• 在T1、T2、T3时刻，发送方A发送数据包；在发送这3个数据包时，A不需要等待B的任何确认消息，因为窗口大小固定为3。
• 在T4时刻，接收方B确认这三个数据包，并允许A传输下一个数据包。
• 在T5时刻，B确认这个新的数据包，即使它只有一个数据包。B不需要等到A发送了3个数据包才确认一个数据包。这个确认使A有足够的预算再发送3个数据包。
• 在T5、T6和T7时刻，A发送3个数据包，填充窗口。现在必须等到B确认这三个数据包才能发送更多的信息。
• 在T8时刻，B确认收到这三个包。

在窗口大小大于1的窗口方案中，接收方有4种确认方式：

• 肯定确认：接收方单独确认每个数据包的接收情况。例如，如果接收到序列号1、3、4和5，接收方就会确认收到了这些特定的数据包。发送方注意到哪些序列号没有被确认，就可以推断接收方没有收到该数据包。
• 否定确认：接收方对推断为丢失或者收到时被损坏的数据包发送一个否定确认。例如，如果接收到序列号1、3、4和5，接收方推断出序列号2的数据包丢失，就对该数据包发送一个否定确认。
• 选择性确认：这本质上是肯定确认和否定确认的组合。接收方对接收到的每一个信息序列都发送肯定或否定的确认。
• 累积确认：对所接收序列号的确认意味着已接收所有较之低的序列号的信息。例如，如果确认序列号10，则意味着收到了包含序列号1～9的信息，以及序列号10的信息。

第三种窗口机制称为滑动窗口流控机制。这种机制非常类似于一个固定窗口的流控机制，除了窗口的大小不是固定的。在滑动窗口流控机制中，当网络条件发生变化时，发送方可以动态地修改窗口大小。接收方不知道窗口大小，只知道发送方传输了数据包，并且接收方不时地使用前面描述的一个确认机制来确认其中部分或全部数据包。
除了其他窗口机制中已经考虑的一些问题外，滑动窗口机制增加了一个更有趣的问题：窗口应该设置为多大合适呢？一个简单的解决方案是计算rtt，并将窗口大小设置为rtt的倍数。目前已经提出了很多更复杂的解决方案，其中一些方案将在第5章讨论。

2.4.2　协商比特率

另一种解决方案是发送方、接收方和网络为任意一个特定数据流协商一个比特率。这种方案更多地用在电路交换而不是分组交换中。设计者为许多不同的网络技术设计了大量可能的比特率。也许“最完整的比特率集合”用在了异步传输模式（ATM）上—从最近的“网络历史博物馆”中可以找到ATM网络，因为ATM很少在生产网络中部署。ATM比特率为：

• 固定比特率（Constant Bit Rate，CBR）：发送方将以恒定的速率发送数据包（或信息），因此，网络可以围绕这个恒定的带宽负载进行规划，并且接收方也可以围绕这个恒定的比特率进行规划。这个比特率通常用于在发送方和接收方之间需要时间同步的应用程序。
• 可变比特率（Variable Bit Rate，VBR）：发送方将以可变速率传输流量。这个速率通常根据其他一些信息（有助于网络和接收方资源规划的数据流信息）调整，包括：
• 峰值速率，发送方计划每秒发送数据包数量的最大值。
• 持续速率，发送方计划传输的正常速率。
• 最大突发速率，发送方在很短的时间内试图发送数据包的最大数量。
• 可用比特率（Available Bit Rate，ABR）：发送方根据网络容量以尽力而为的方式传输流量，它使用其他形式的流控机制，如滑动窗口技术，以防止缓冲区溢出，并调整传输流量以适配可用的带宽。

2.5　总结思考

“在网络中传输数据”是理解整个网络工程问题空间范围的基础。本章从这个基础开始，通过对人类语言空间的思考，揭示了四种特定问题，并提出了若干高层次的解决方案。

• 对于数据列集，讨论了固定长度和基于TLV的系统，以及元数据、字典和语法的概念。
• 为了管理差错，讨论了两种方法以检测差错—奇偶校验和CRC，并讨论了一种纠错方法，即汉明码。
• 为允许多个发送方和接收方使用相同的物理介质，讨论了多路复用中的几个概念，包括多播和选播。
• 为防止缓冲区溢出，探索了几种类型的窗口机制，并定义了协商比特率。

就像在书中所遇到的许多其他领域一样，传输的世界也可以成为一个完整的专业。然而，了解基本知识对于每个网络工程师来说都是非常重要的。下一章将考虑一些模型，这些模型将数据传输（通常与转发或数据平面关联）放到了更大的场景中。第4章和第5章将考虑几个不同的传输协议示例，将本章和下一章中的概念应用到实际案例中。

2.6　拓展阅读

部分拓展阅读资源可帮助解答本章的研究问题。

2.7　复习题

1.虽然TLV几乎总是比一个固定长度的字段需要更多的空间来承载一段信息，但是在某些情况下，固定长度字段不如TLV的效率高。传输IPv6地址是TLV比固定长度字段更有效的一个具体实例。请描述这是为什么。比较路由协议中携带IPv4地址和IPv6地址的方式有助于理解答案，特别是检查IPv4地址在OSPF版本2中的传输方式，并与在BGP中使用相同地址的方式进行比较。
2.考虑以下数据类型，并确定是使用固定长度字段还是TLV，以及为什么。
a）时间和日期。
b）一个人的全名。
c）温度读数。
d）建筑的面积。
e）一系列音频或视频剪辑。
f）分成若干部分（如段落和章节）的一本书。
g）地址中的省份和城市。
h）地址中的房屋编号或邮政编码。
3.简述比特误码率（Bit Error Rate，BER）与在传输数据流中检测或修复差错所需的信息量之间的关系，并解释说明。
4.在某些情况下，在接收时通过发送方的足够信息来纠正数据更有意义（如使用汉明码）；而在另一些情况下，发现差错并扔掉数据更有意义。这些条件不仅仅涉及链路类型或者应用程序，而是两者的结合。什么样的链路特性，再加上怎样的应用程序特征，会建议使用FEC呢？哪些会建议使用差错检测并结合数据重传呢？最好先考虑特定应用程序和特定的链路类型，然后再泛化。
5.一个奇偶校验能检测多少位的翻转变化呢？
6.隐式和显式信令具有不同的特性或者不同的权衡。对于差错检测或纠错，请至少描述每一种信令形式的一个正面作用和一个负面作用。
7.在大规模部署选播时，可以将来自单个流的数据包分发给多个接收方。对于这个问题，有两种通用的解决方案。第一种方法是如果一个数据包出现这种传递错误，接收方将强制发送方重置它的状态。另一种方法是以允许状态包含在单个事务中的方式限制发送方和接收方之间的接口。后一种解决方案的形式称为原子事务，通常在RESTful接口中实现。考虑这两种可能的解决方案，并描述各种应用程序（通过给出可能更适合其中一种解决方案的具体示例）。
8.你是否经常考虑元数据的字典和语法形式？为什么？
9.找到另外三种不涉及数据格式的元数据，这些元数据以一种可能对攻击者有用的方式描述数据，这种方式有助于攻击者了解特定的流程，比如在两个账户之间转移资金。对于元数据的定义是否存在特定的限制，或者更准确地说，在旁观者眼中元数据是怎样的呢？
10.考虑本章末尾所解释的协商比特率。在分组交换网络中是否真的可以提供一个恒定的比特率？答案是否取决于网络条件？如果是这样的话，什么条件会影响这个问题的答案呢？