数字系统在现代社会中无处不在。数字计算机用于执行各种任务，从模拟物理系统到管理大型数据库再到准备文档。数字通信系统中继电话，视频信号和Internet数据。音频和视频娱乐越来越多地以数字形式交付和处理。最后，从汽车到家用电器的几乎所有产品都是数字控制的。
数字系统由三个基本构建块组成：逻辑，存储器和通信。逻辑可以转换和合并数据，例如，通过执行算术运算或制定决策。内存存储数据供以后检索，并及时移动。通信将数据从一个位置移动到另一位置。本书涉及数字系统的通信组件。特别是，它探讨了用于在数字系统的子系统之间传输数据的互连网络。
如今，大多数数字系统的性能都受到其通信或互连的限制，而不是受其逻辑或内存的限制。在高端系统中，大部分功率用于驱动电线，而大部分时钟周期则花费在电线延迟而不是门延迟上。随着技术的进步，存储器和处理器变得更小，更快且更便宜。但是，光速保持不变。控制系统组件之间互连的引脚密度和布线密度的扩展速率低于组件本身。而且，组件之间的通信频率远远落后于现代处理器的时钟速率。这些因素共同使互连成为未来数字系统成功的关键因素。
随着设计人员努力更有效地利用稀缺的互连带宽，互连网络正在成为现代数字系统的系统级通信问题的近乎通用的解决方案。本来互连网络是为满足多计算机苛刻的通信要求而开发的，它们开始取代总线作为标准的系统级互连。随着设计人员发现路由数据包比路由电缆更快，更经济，它们还取代了专用系统中的专用布线。
在进一步介绍之前，我们将回答有关互连网络的一些基本问题：什么是互连网络？您在哪里找到它们？他们为什么重要？
什么是互连网络？ 如图1.1所示，互连网络是一个在终端之间传输数据的可编程系统。该图显示了连接到网络的六个端子T1至T6。当终端T3希望与终端T5通信时，它将包含该数据的消息发送到网络中，然后网络将消息传递到T5。从某种意义上说，它是可编程的，因为它可以在不同的时间点建立不同的连接。图中的网络可以在一个周期内将消息从T3传递到T5，然后在下一个周期使用相同的资源将消息从T3传递到T1。该网络是一个系统，因为它由许多组件组成：缓冲区，通道，开关和控件一起工作以传递数据。
满足此广泛定义的网络范围广泛。片上网络可以在单个处理器内的存储器阵列，寄存器和算术单元之间传递数据。板级和系统级网络将处理器绑定到内存，或者将输入端口绑定到输出端口。最后，局域网和广域网将企业内或全球范围内的不同系统连接在一起。在本书中，我们将注意力集中在较小的规模上：从芯片级到系统级。已经有许多针对大型网络的优秀著作。但是，在系统级别及以下级别的问题中，信道较短且数据速率非常高，根本不同于大规模，需要不同的解决方案。
您在哪里找到互连网络？ 它们几乎用于所有大型系统，足以连接两个组件。互连网络的最常见应用是在计算机系统和通信交换机中。在计算机系统中，它们将处理器连接到内存，并将输入/输出（I / O）设备连接到I / O控制器。它们将输入端口连接到通信交换机和网络路由器中的输出端口。它们还将传感器和执行器连接到控制系统中的处理器。在系统的两个组件之间传输位的任何地方，都可能找到互连网络。
直到1980年代后期，大多数这些应用程序都通过一个非常简单的互连网络进行服务：多点总线。如果这本书是写的，那可能是一本有关公交车设计的书。我们将第22章专门讨论总线，因为它们在许多应用中仍然很重要。但是今天，所有高性能互连都是通过点对点互连网络而不是总线来执行的，并且历史上每年都有更多基于总线的系统会切换到网络，这是由于性能缩放不均所致。随着处理器性能（以每年50％的速度）和网络带宽的增长，对互连性能的需求也在不断增长。另一方面，电线的获取速度却越来越快。更好的半导体技术无法提高光速和24号铜线的衰减。结果，总线无法满足带宽需求，并且点对点互连网络（其运行速度比总线快并且具有并发性）正在迅速接管。
为什么互连网络很重要？ 因为它们是许多系统性能的限制因素。处理器和内存之间的互连网络在很大程度上决定了计算机系统中的内存延迟和内存带宽这两个关键性能因素。1通信交换机中互连网络（在本文中有时称为交换矩阵）的性能在很大程度上决定了交换机的容量（数据速率和端口数）。因为对互连的需求增长速度超过了底层导线的能力，所以互连已成为大多数系统中的关键瓶颈。
互连网络是专用布线的一种有吸引力的替代方法，因为它们允许稀缺的布线资源由几个低占空比信号共享。在图1.1中，假设每个终端每100个周期需要一次与一个终端进行一个单词的通信，我们可以在每对终端之间提供一个专用的字宽通道，总共需要30个单向通道。但是，每个通道将有99％的时间处于空闲状态。相反，如果我们将6个端子成环连接，则仅需要6个通道。（T1连接到T2，T2连接到T3，依此类推，以从T6到T1的连接结束。）对于环形网络，当考虑到现代存储芯片的大部分访问时间是通信延迟时，这一点尤其正确。通道数量减少了五倍，通道占空比从1％增加到了12.5％。
为了了解互连网络设计的要求，检查它们在数字系统中的使用方式很有用。在本节中，我们研究了互连网络的三种常见用法，并查看了这些应用如何驱动网络需求。具体来说，对于每个应用程序，我们将检查该应用程序如何确定以下网络参数：
1.端子数
2.每个终端的峰值带宽
3.每个终端的平均带宽
4.所需的延迟
5.该消息大小或消息大小的分布
6.预期的流量模式
7.所需的服务质量
8.互连网络所需的可靠性和可用性
我们已经看到，网络中终端或端口的数量与必须连接到网络的组件的数量相对应。除了知道终端的数量之外，设计人员还需要知道终端如何与网络交互。
每个终端将需要一定数量的网络带宽，通常以每秒比特数（bit/s）表示。除非另有说明，否则我们假定终端带宽是对称的，即终端的输入和输出带宽相等。的峰值带宽是最大数据速率，一个终端将来自网络上的短时间段内请求，而平均带宽是平均数据速率，一个终端将需要。如下一节有关处理器-内存互连的设计所示，在设法使互连网络的实现成本最小化时，了解峰值带宽和平均带宽就变得很重要。
除了网络必须接受和传递消息的速率之外，还为网络指定了传递单个消息所需的时间，消息等待时间。虽然理想的网络同时支持高带宽和低延迟，但是这两个参数之间通常存在折衷。例如，支持高带宽的网络往往会使网络资源繁忙，从而经常导致资源争用。当两个或更多消息要使用网络中的相同共享资源时，发生争用。除了一条消息之外，所有消息都必须等待该资源释放，从而增加了消息的等待时间。相反，如果通过减少带宽需求来降低资源利用率，则等待时间也会降低。
消息大小（以位为单位的消息长度）是另一个重要的设计考虑因素。如果消息较小，则与可以在较大消息的长度上摊销开销的情况相比，网络中的开销对性能的影响更大。在许多系统中，有几种可能的消息大小。
来自每个终端的消息如何分布在所有可能的目标终端上，定义了网络的流量模式。例如，每个终端可能以相同的概率向所有其他终端发送消息，这是随机流量模式。相反，如果终端倾向于仅向其他附近的终端发送消息，则基础网络可以利用该空间位置来降低成本。但是，在其他网络中，重要的一点是规范必须适用于任意流量模式。
某些网络还将需要服务质量（QoS）。粗略地说，QoS涉及某种服务策略下资源的公平分配。例如，当多个消息争用网络中的同一资源时，可以通过多种方式解决此争用。可以根据消息等待时间的长短，以先到先得的顺序提供消息。另一种方法优先考虑消息在网络中的使用时间最长。在这些分配策略和其他分配策略之间进行选择是基于网络所需的服务。
最后，互连网络所需的可靠性和可用性会影响设计决策。可靠性是网络正确执行传递消息任务频率的一种度量。在大多数情况下，邮件需要100％的时间传递而不会丢失。要实现100％可靠的网络，可以通过添加专用的硬件来检测和纠正错误，更高级别的软件协议或混合使用这些方法来实现。正如我们将在以下有关数据包交换结构的部分中看到的那样，一小部分消息也可能会被网络丢弃。网络的可用性是网络可用并正常运行的时间的一部分。在Internet路由器中，通常将可用性指定为99.999％-每年少于总停机时间五分钟。提供这种级别的可用性的挑战在于，用于实施网络的组件通常每分钟会发生几次故障。因此，必须将网络设计为能够在继续运行的情况下检测并快速从这些故障中恢复。
图1.2说明了使用互连网络将处理器连接到内存的两种方法。图1.2（a）显示了Dance-Hall的体系结构，其中P个处理器通过互连网络连接到M个存储体。大多数现代机器都使用图1.2（b）所示的集成节点配置，将处理器和内存组合在一个集成节点中。通过这种布置，每个处理器可以通过通信交换机C访问其本地存储器，而无需使用网络。
两种配置对网络的要求均列在表1.1。处理器端口的数量可以是数千个，例如最大配置的Cray T3E中的2176个处理器端口，或者单个处理器的数量可以少至1个。如今，高端服务器中普遍使用64到128个处理器的配置，并且该数量随着时间的增长而增加。对于组合节点配置，这些处理器端口中的每个端口也是一个内存端口。另一方面，在舞厅配置中，内存端口的数量通常比处理器端口的数量大得多。例如，一个高端向量处理器具有32个处理器端口，可请求4,096个存储体。较大的比例可最大程度地提高内存带宽，并减少了两个处理器同时需要访问同一内存条的内存条冲突的可能性。
现代的微处理器每秒执行大约10^9条指令，每条指令可能需要从内存中提取两个64位字（一个用于指令本身，一个用于数据）。如果这些引用之一在高速缓存中未命中，通常会从内存中获取8个字的块。如果我们确实需要每个周期从内存中提取2个字，那么这将需要16Gbytes / s的带宽。幸运的是，所有指令中只有大约三分之一引用了内存中的数据，并且高速缓存可以很好地减少必须实际引用存储体的引用数量。使用典型的高速缓存未命中率，平均带宽要低一个数量级以上，大约为400Mbytes / s。3但是，为了避免由于序列化而增加内存等待时间，大多数处理器仍然需要能够以每条指令一个字的峰值速率从内存系统中获取。如果我们过度限制此峰值带宽，那么突然的内存请求突发将迅速阻塞处理器的网络端口。通过较低带宽的网络端口来压缩此高带宽请求的过程（类似于缓慢耗尽的接收器）被称为序列化，并增加了消息延迟。为了避免在突发请求期间进行序列化，我们需要8Gbytes / s的峰值带宽。
处理器性能对内存延迟非常敏感，因此对传输内存请求和答复的互连网络的延迟非常敏感。在表1.1中，我们列出了100ns的等待时间要求，因为这是没有网络的典型内存系统的基本等待时间。如果我们的网络增加了100ns的延迟，则我们的有效内存延迟将增加一倍。
当加载和存储指令在处理器的高速缓存中丢失时（在集成节点配置中未寻址到本地存储器），它们将转换为读请求和写请求数据包，并通过网络转发到适当的存储体。每个读请求包都包含要读取的内存地址，每个写请求包都包含内存地址和要写入的字或高速缓存行。适当的存储库接收到请求数据包后，它将执行请求的操作并发送相应的读-应答或写-应答分组。
请注意，我们已经开始区分网络中的消息和数据包。消息是从网络客户端（在这种情况下为处理器和内存）到网络的传输单位。在网络接口处，一条消息可以创建一个或多个数据包。这种区分可以简化基础网络，因为大消息可以分为几个较小的数据包，或者不等长消息可以分为固定长度的数据包。因为对于在此处理器内存互连中创建的相对较小的消息，我们假设消息和数据包之间是一一对应的。
读请求和写答复数据包不包含任何数据，但确实存储一个地址。此地址加上网络使用的一些标头和数据包类型信息都适合在64位之内。读-应答和写请求数据包包含相同的64位标头和地址信息，以及512位高速缓存行的内容，从而产生576位数据包。这两种数据包格式如图1.3所示。
与处理器-内存互连的典型情况一样，我们不需要任何特定的QoS。这是因为网络本质上是自我节流的。也就是说，如果网络变得拥塞，则内存请求将需要更长的时间才能完成。由于处理器只能处理有限数量的请求，因此它们将开始空闲，等待答复。由于处理器在空闲时不会创建新请求，因此可以减少网络拥塞，这种稳定行为称为自调节。大多数QoS保证仅在网络拥塞时才影响网络，但自限流往往会避免拥塞，从而使QoS在处理器与内存互连中的用处不大。
此应用程序需要一个内在可靠的网络，且不会丢失数据包。内存请求和回复数据包不能被丢弃。丢弃的请求数据包将导致内存操作永久挂起。至少，这将导致用户程序由于超时而崩溃。最坏的情况是，它可能导致整个系统崩溃。可靠性可以在不可靠的网络上分层，例如，通过使每个网络接口保留每个传输数据包的副本，直到被确认为止，并在数据包丢失时重新传输。（请参阅第21章。）但是，这种方法通常会导致处理器-内存互连的延迟不可接受。根据不同的应用，处理器与内存的互连需要的可用性范围从三个九（99.9％）到五个九（99.999％）。
互连网络还用于计算机系统中，以将I/O设备（例如磁盘驱动器，显示器和网络接口）连接到处理器和/或内存。图1.4显示了一个典型的I/O网络示例，该网络用于将磁盘驱动器阵列（沿图的底部）连接到一组主机适配器。网络以与处理器-内存互连相同的方式运行，但有不同的粒度和时间延迟。
这些差异，尤其是延迟等待时间的增加，使网络设计朝着完全不同的方向发展。
磁盘操作通过传输4 KB或更大的扇区来执行。由于磁盘的旋转等待时间加上重新放置磁头所需的时间，因此扇区访问的等待时间可能会很短。通过从主机适配器发送控制数据包来执行磁盘读取，该控制数据包指定要读取的磁盘地址（设备和扇区）以及作为读取目标的内存块。当磁盘接收到请求时，它将安排磁头移动以读取请求的扇区。磁盘读取请求的扇区后，它将向包含该扇区并指定目标内存块的相应主机适配器发送响应数据包。
高性能I / O互连网络的参数在表1.2中列出。该网络最多可连接64个主机适配器，对于每个主机适配器，可能会有许多物理设备，例如硬盘驱动器。在此示例中，每个主机适配器最多有64个I / O设备，总共4,096个设备。更典型的系统可能将几个主机适配器连接到一百个左右的设备。
磁盘端口的峰均带宽比率很高。当磁盘传输连续的扇区时，它可以以高达200Mbytes / s的速率读取数据。该数字确定表中显示的峰值带宽。更典型地，磁盘必须在扇区之间执行一次磁头移动，平均时间为5ms（或更长），导致每5ms的平均数据速率为一个4 KB扇区，或者小于1 MB / s。由于主机端口各自处理来自64个磁盘端口的聚合流量，因此它们具有较低的峰均带宽比率。
设备端口的峰值带宽和平均带宽之间的巨大差异要求集中的网络拓扑。虽然设计一个网络以同时支持所有设备的峰值带宽就足够了，但最终的网络将非常昂贵。或者，我们可以将网络设计为仅支持平均带宽，但是正如处理器内存互连示例中所讨论的那样，这会引入序列化延迟。峰均带宽之比很高，此序列化等待时间将非常大。一种更有效的方法是将许多设备的请求集中到“聚合”端口。此聚合端口的平均带宽与共享该端口的设备数量成正比。但是，由于各个设备很少向网络请求其峰值带宽，因此，许多设备中有超过两个要求从聚合端口中获取峰值带宽的可能性很小。通过集中精力，我们有效地降低了峰值带宽需求与平均带宽需求之间的比率，从而实现了成本更低的实现，而没有过多的序列化延迟。
像处理器内存网络一样，消息有效负载大小是双峰的，但是在两种模式之间的传播更大。网络承载短消息（32字节）以请求读取操作，确认写操作以及执行磁盘控制。另一方面，读答复和写请求消息需要很长（8 KB）消息。
由于磁盘操作的固有延迟很长（毫秒），并且作为一个单位传输的数据量很大（4 KB），因此网络对延迟的敏感度不是很高。将等待时间增加到10μs会导致性能下降到可以忽略的程度。这种宽松的延迟规范使构建高效的I / O网络比构建延迟非常重要的等效处理器内存网络要简单得多。
用于通过基于集群的并行计算机进行快速消息传递的处理器间通信网络实际上在带宽和粒度方面与I / O网络非常相似，因此将不进行单独讨论。这些网络通常被称为系统区域网络（SAN），它们与I / O网络的主要区别是对消息延迟更敏感，通常需要延迟小于几微秒的网络。
在使用磁盘存储来保存企业关键数据的应用程序中，需要极高的可用性。如果存储网络中断，则业务下跌降落。存储系统的可用性为0.99999（五个九），这并不罕见-每年停机时间不超过五分钟。
互连网络已取代总线和交叉开关，成为通信网络交换机和路由器的交换结构。在此应用程序中，互连网络充当用于大型网络（局域或广域网）的路由器的元素。图1.5显示了此应用程序的示例。线卡阵列可终止大型网络通道（通常是带宽为2.5Gbit / s或10Gbits / s的光纤）。线卡处理每个数据包或信元以确定其目的地，验证其是否符合其服务协议，重写数据包的某些字段并更新统计信息计数器。然后，线卡将每个数据包转发到结构。然后，光纤负责将每个数据包从其源线路卡转发到目标线路卡。在目标端，数据包被排队并安排在输出网络通道上传输。
表1.3显示了用作交换结构的典型互连网络的特性。交换结构要求与处理器内存和I / O网络要求之间的最大区别是其高平均带宽和对服务质量的需求。
交换结构的大数据包大小及其对延迟的不敏感性，简化了网络设计，因为不必高度优化延迟和消息开销。确切的数据包大小取决于网络使用的协议路由器。对于Internet协议（IP），数据包的范围从40字节到64Kb，大多数数据包的长度为40、100或1,500个字节。像我们的其他两个示例一样，数据包分为短控制消息和大数据传输。
网络交换结构不会像处理器内存或I / O互连那样自我节流。每条线卡都可以连续地保持数据包的稳定流，而不管结构中的拥塞情况如何，同时，结构必须为某些类的数据包提供有保证的带宽。为了满足此服务保证，织物必须是无干扰的。也就是说，可能由于瞬时过载而导致发往线路卡a的流量过多，即使发往a的消息和发往a的消息也不会干扰或“窃取”发往另一线路卡b的流量的带宽。b在整个结构中共享资源。对无干扰的需求对网络交换结构的基础实现提出了独特的要求。
可以潜在简化其设计的交换结构的一个有趣方面是，在某些应用程序中，丢弃一小部分数据包（例如，每10 15个数据包中的一个）可能是可以接受的。出于其他原因执行此操作，包括输入光纤上的误码（通常错误率在10到12到10到15范围内）到线卡队列中的溢出。在这些情况下，较高级别的协议通常会处理丢弃的数据包，因此，路由器可以通过丢弃有问题的数据包来处理非常不可能的情况（例如内部误码），只要这些丢弃的速率为由于其他原因，远低于丢包率。这与处理器－内存互连相反，在处理器－内存互连中，单个丢失的数据包可以锁定计算机。
为了满足特定应用的性能规格，如上述的那些技术限制范围内的网络设计者必须努力实现拓扑，路由和流量控制.在前面的章节中，对互连网络的效率的关键来自于通信资源共享代替在每个终端对之间创建专用信道，互连网络是通过由共享信道连接的共享路由器节点的集合来实现的。这些节点的连接模式定义了网络的拓扑。然后，通过在共享信道和节点之间从其源终端到其目标终端进行几次跃点，在终端之间传递消息。良好的拓扑可利用网络封装技术的特性，例如芯片封装上的引脚数或可在不同机柜之间连接的电缆数，以最大化网络带宽。
一旦选择了拓扑，一条消息可能会通过网络到达其目的地的路径可能很多（节点和通道的顺序）。路由确定一条消息实际采用这些可能的路径中的哪一条。路径的良好选择可以最大程度地减小路径的长度（通常以访问的节点或通道数来衡量），同时平衡对网络共享资源的需求。路径的长度显然会影响通过网络的消息的延迟，并且资源的需求或负载是对资源使用频率的度量。如果一种资源过度使用而另一种资源处于闲置状态（称为负载不平衡），则网络正在传递的消息的总带宽会减少。
流控制指示随着时间的流逝，哪些消息可以访问特定的网络资源。随着资源利用率的提高，流量控制的影响变得更加关键，良好的流量控制以最小的延迟转发数据包，并避免了高负载下的资源空闲。
互连网络由一组共享的路由器节点和通道组成，网络的拓扑结构是指这些节点和通道的布置。互连网络的拓扑结构类似于路标。通道（如道路）承载来自一个路由器节点（交叉口）的数据包（如汽车）到另一个。例如，图1.6中所示的网络由16个节点组成，每个节点连接到8个通道，每个邻居1个，每个邻居1个。该特定网络具有环形拓扑。在图中，节点用圆圈表示，每对通道（在每个方向上一个通道）用连接两个节点的线表示。此拓扑也是直接网络，终端与拓扑的16个节点中的每个节点相关联。
良好的拓扑可利用可用封装技术的特性来满足应用程序的带宽和延迟要求开销。对于最大化带宽，拓扑应该饱和分带宽，整个系统的中点的带宽，由底层包装技术提供。
例如，图1.7显示了如何打包图1.6中的网络。四个节点组成的组放置在垂直印刷电路板上。然后，使用底板电路板连接四个电路板，就像将PCI卡插入PC的主板一样。对于此系统，二等分带宽是可以通过此背板传输的最大带宽。假设背板足够宽，可以包含256个信号，每个信号以1Gbit / s的数据速率运行，则二等分总带宽为256Gbits / s。
回到图1.6，恰好有16个单向通道穿过我们拓扑的中点-请记住，图中的线代表两个通道，每个方向一个。饱和256个信号的二等分，每个信道交叉的二等分应该256 / 16 = 16个信号宽。但是，我们还必须考虑到每个节点都将封装在单个IC芯片上的事实。对于此示例，每个芯片仅具有足够的引脚以支持128个信号。由于我们的拓扑需要每个节点总共8个信道的，每个芯片的销约束限制的沟道宽度为128 / 8 = 16个信号。幸运的是，引脚限制所给出的通道宽度与匹配两分频带宽所需的信号数量完全匹配。
相反，请考虑图1.8中所示的16节点环形网络。有4个信道连接到每个节点，以便销约束限制的沟道宽度为128 / 4 = 32个信号。四个通道交叉对分，所以我们想设计这些信道为256 / 4 = 64个信号宽饱和我们的平分，但引脚将通道宽度限制为该宽度的一半。因此，在相同的技术约束下，环形拓扑仅提供环形拓扑的一半带宽。就带宽而言，圆环显然是一个更好的选择，它在系统中点提供每个节点完整的32Gbits / s带宽。
但是，高带宽并不是衡量拓扑性能的唯一方法。假设我们有一个不同的应用程序，在相同的技术约束下，它仅需要16Gbits / s的带宽，而且还需要最小的延迟。此外，假设此应用程序使用了相当长的4,096位数据包。为了实现低等待时间，拓扑必须在对节点之间的平均距离较小的需求与低序列化等待时间之间取得平衡。
节点之间的距离（称为跃点计数）以消息平均到达其目的地必须经过的通道和节点数来度量。减小此距离需要增加节点度（进入和离开每个节点的通道数）。但是，由于每个节点都受到固定的引脚限制，所以增加通道数会导致通道宽度变窄。通过狭窄的通道挤压大数据包会引起序列化延迟。为了了解这种权衡如何影响拓扑选择，我们重新介绍了两个16节点拓扑，但是现在我们重点讨论消息延迟。
首先，为了量化由于跳数引起的等待时间，需要假设一种流量模式。为简单起见，我们使用随机流量，其中每个节点以相等的概率发送到每个其他节点。随机流量下的平均跳数只是节点之间的平均距离。对于我们的环型拓扑，平均距离是2，对于环，平均距离是4。在典型的网络中，每跳的延迟可能是20ns，对应于环的总跳延迟为40ns，环的总跳延迟为80ns。
但是，环的宽通道使它的序列化等待时间低得多。
要在32信号通道上发送4,096位数据包，需要4,096 / 32 = 128个周期的通道。我们的1GHz信令速率对应于1ns的周期，因此环的序列化延迟为128ns。如果我们的网络得到了有效的设计，我们只需支付一次序列化时间，这样就可以使环上每个数据包的平均延迟为80 + 128 = 208ns。对圆环的类似计算产生了256ns的序列化延迟和296ns的总延迟。即使该环具有更大的平均跳数，但物理打包的约束使其对于这些长数据包的等待时间更短。
正如我们在这里看到的，没有一种拓扑对于所有应用程序都是最佳的。不同的拓扑适用于不同的约束和要求。在第3章到第7章中将更详细地讨论拓扑。
网络采用的路由方法确定数据包从源终端节点到目标终端节点所采用的路径。路径是路径的有序集合
图1.9显示了图1.6网络中从节点01到节点22的两条不同路由。在图1.9（a）中，数据包采用维度顺序路由，首先在x维度到到达节点21中路由，然后在y维度到到达节点22中进行路由。这条路由是一条最小路由，因为它是从01到22的最短路径之一。（有6条。）图1.9（b）显示了从00到22的另一条路由。该路由不是最小路由，跳数为5，而不是最小3。
尽管维度顺序路由既简单又最小，但是对于某些流量模式，它可能会导致严重的负载不平衡。例如，考虑在图1.9（a）中添加从节点11到节点20的另一维顺序路由。此路由还使用从节点11到节点21的通道，其负载加倍。通道的负载是终端节点尝试通过该通道发送的平均带宽。将负载归一化到终端扫描到网络的最大速率，此信道的负载为2。在这种情况下，更好的路由算法可以将归一化的信道负载减少到1。由于维度顺序路由在此单个通道上承受了两倍的必要负载，因此在此流量模式下网络的最终带宽将仅为其最大带宽的一半。更一般而言，由于负载不平衡，所有在每个源-目标对之间选择一条固定路径的路由算法（称为确定性路由算法）尤其会受到带宽的影响。在路由算法设计中，这些和其他问题将在第8章到第10章。
当数据包沿其路由前进时，流量控制管理对数据包的资源分配。大多数互连网络中的关键资源是通道和缓冲区。我们已经看到了通道在节点之间传输数据包中的作用。缓冲区是在节点内实现的存储，例如寄存器或存储器，并允许将数据包临时保存在节点上。继续我们的类比：拓扑结构确定路线图，路线选择方法引导汽车，流量控制控制交通信号灯，确定汽车何时可以驶入下一段道路（通道）或何时必须驶入停车场很多（缓冲区）以允许其他车辆通过。
为了实现拓扑和路由方法的性能潜能，流控制策略必须避免资源冲突，而该冲突可能会使通道保持空闲状态。例如，它不应阻塞可以使用空闲信道的数据包，因为它正在等待在繁忙信道上阻塞的数据包所持有的缓冲区，这种情况类似于阻塞要在汽车后方继续行驶的汽车等待交通中断以向左转。该解决方案，流量控制以及在高速公路上，是增加一个（左转）车道分离的资源依赖性，使阻塞的数据包或汽车取得进展，而无需等待。
好的流量控制策略是公平的，并且可以避免死锁。不公平的流量控制策略可能导致数据包无限期地等待，就像汽车试图在没有灯光的繁忙街道上左转弯一样。死锁是当一包数据包互相等待释放资源而无限期地被阻塞时发生的情况，这种情况与我们的路线图类比中的僵局不同。
我们经常通过使用时空图（如图1.10所示）来描述流控制方法。该图显示了（a）存储和转发流量控制和（b）直通流量控制的时空图。在两个图中，水平轴表示时间，垂直轴表示空间。时间以周期表示。通过列出用于发送数据包的通道来显示空间。每个小包分为五个固定大小的碎片。flit（流量控制数字）是流量控制方法识别的最小信息单位。选择一个固定的小尺寸可以简化路由器的设计，而不会为长度不等于长度的整数倍的数据包带来较大的开销。标记为方框的单个数据包的每次传送都通过网络的四个通道发送。在周期中的图表中显示一个框，其中特定的flit正在使用通道的带宽。如图1.10所示，流控制技术的选择会显着影响数据包通过网络的等待时间。
在第12章和第13章中将更详细地描述流控制。在第14章和第15章中将处理与流控制和路由相关的死锁，活锁，树饱和和服务质量问题。
图1.11显示了图1.6网络中16个节点之一的内部的简化视图。缓冲区与四个输入通道的每个通道关联，并且这些缓冲区保存到达的数据块，直到可以为它们分配离开所需的资源为止。一旦可以确保flit在沿其路径的下一个路由器（下游路由器）中留有缓冲空间，就可以开始争夺对纵横开关的访问。可以将交叉开关配置为将路由器的任何输入缓冲区连接到任何输出通道，但是在每个输入最多连接到一个输出且每个输出最多连接到一个输入的约束下。解决对路由器的交叉开关和其他共享资源的所有潜在请求的任务落在分配器上。要前进到下一个路由器，必须为输入缓冲区之一中的flit分配其路由的下一个节点上的缓冲区中的空间，该路由的下一个通道上的带宽，并且必须赢得分配才能穿越交叉开关。路由器体系结构在第16章至第21章中有详细介绍。
互连网络的性能主要由延迟与所提供的流量曲线来描述，如图1.12所示。该图显示了数据包的平均等待时间，即从数据包的第一个比特到达源终端到数据包的最后一个比特到达目的终端的时间，它是所提供流量的函数，每个产生的流量（位/秒）为了绘制特定的延迟vs.提供的流量曲线，还必须指定流量模式（例如随机流量）。
尽管延迟与所提供的流量曲线可以最准确地了解互连网络的最终性能，但它们却是简单，封闭的表达式，通常可以通过离散事件仿真找到。为了指导我们在互连网络的早期设计阶段对折衷的理解，我们在探索拓扑，路由和流量控制之后采用了渐进的网络性能方法。
零负载延迟为通过网络的数据包的平均延迟提供了下限。零负载假设是一个数据包永远不会与其他数据包竞争网络资源。在此假设下，数据包的平均延迟是其串行化延迟加上其商店延迟。例如，请考虑图1.6中所示的torus网络，该数据包的长度为L = 512位，带宽为b = 16Gbits / s的信道，并且流量随机。在这种情况下，串行化等待时间为L / b = 32ns。最低流量的随机可能性最低，并且路由最小，给出的平均跃点数为H min = 2。对于路由器延迟时间t r = 10ns，最小跃点延迟时间为H min t r = 20ns。仅根据网络的拓扑，打包和流量模式，就可以确定通过网络的数据包的平均延迟的下限为32 + 20 = 52ns。
掺入的平均跳数ħ平均所使用的实际路由算法在thenetworkgivesatighterboundonpacketlatencybecause ħ平均≥ħ分钟。最后，由网络使用可以进一步降低在由拓扑和路由给定的界限性能的流控制。例如，如果我们的网络采用存储和转发流控制（图1.10 [a]），则零负载延迟为H avg t r ×L / b而不是H avg t r + L / b 。实际的零负载等待时间T 0包含拓扑约束以及实际的性能，路由和流量控制。这些潜伏时间上越来越紧的界限显示为图1.12中曲线的水平渐近线。
一种类似的方法为网络的吞吐量提供了一组上限。
当每个源向网络提供特定数量的流量时，吞吐量或接受的流量是流量（位/秒）传递到目标终端的速率。对于我们的随机流量示例，一半流量必须穿过网络的两部分。该部分包括16个通道，总带宽为B c = 256Gbits / s。因此，每个节点的流量不能超过2 B c / N或32Gbits / s。此边界假设整个二分路的流量完全平衡。因此，如果出现负载不平衡，则特定的路由算法R不能超出此界限，并且考虑到路由算法R的吞吐量实际上可能会更低。最后，如果我们的由于资源依赖性流控制导致空闲信道，则饱和度可以通过该网络的λ小号可以比结合的显著少ř 。这三个吞吐量限制在图1.12中显示为垂直渐近线。
采取这种渐进的性能方法（由于拓扑，路由和流控制而成功地得出更严格的界限），使我们能够探索所考虑的每个设计决策如何影响性能，而无需使分析复杂化不必要的细节。例如，我们可以看到拓扑选择如何影响延迟，而与路由和流控制无关。相反，尝试同时处理所有性能会使得很难看到任何一种设计选择的效果。
建立完备的绩效模型后，我们将在第23章至第25章中全面考虑绩效。在这些章中，我们讨论了绩效衡量的一些细微问题，介绍了评估绩效的分析方法（基于排队论和概率论），并进行了讨论。仿真方法来测量性能，并给出许多示例测量。
互连网络拥有数十年的悠久历史。网络至少沿着三个并行线程发展：电话交换网络，处理器间通信和处理器-内存互连。
电话交换网络和电话一样长。早期的电话网络是通过机电纵横开关或机电逐步开关建立的。到了20世纪80年代，尽管当时的长途电话交换机完全是电子的和数字的，但大多数本地电话交换机仍是由机电继电器构建的。电话交换的主要发展包括1953年的无阻塞多级Clos网络和1962年的Benesˇ网络。当今，许多大型电话交换机仍是从Clos或类似Clos的网络构建的。
第一个处理器间互连网络是以二维阵列连接的相邻处理器的寄存器之间的连接。1962年的Solomon机器是这种类型的处理器阵列的示例。这些早期的网络不执行路由。因此，处理器必须显式地将通信中继到非邻居，从而导致性能差和编程复杂性高。到1980年代中期，开发了路由器芯片，例如环形路由芯片，可以在无需处理器干预的情况下通过中间节点转发消息。
多年来，处理器间互连网络经历了一系列的拓扑流行，主要是由于封装和其他技术限制所致。早期的机器，如Solomon ，Illiac 和MPP都基于简单的2- D网格或环形网络由于其物理规则性。从1970年代末开始，二进制n立方或超立方网络因其较小的直径而变得流行。出现了许多围绕超立方体网络设计的机器，例如Ametek S14，Cosmic Cube [163]，nCUBE计算机[134,140]和Intel iPSC系列[38，155]。在1980年代中期，事实表明，在实际的包装约束下，低维网络的性能优于超立方体[2，46]，大多数机器返回到2-D或3-D网格或圆环网络。因此，在过去十年中制造的大多数机器已经返回到这些网络，包括J机器[138]，CrayT3D [95]和T3E [162]，英特尔DELTA [117]和Alpha 21364 [131]。如今，相对于消息长度而言，路由器芯片的高引脚带宽促使人们使用节点度更高的网络，例如蝶形和Clos网络。我们可以预期在未来十年内将转向此类网络。
处理器-内存互连网络出现在1960年代后期，当时并行处理器系统合并了对齐网络，以允许任何处理器访问任何存储体而不会给其他处理器带来负担[110]。最小的计算机为此目的使用了交叉开关，而较大的计算机则使用了交叉开关。带有舞厅布置的蝴蝶（或等效）拓扑。在整个1980年代，许多共享内存并行处理器都使用了这种主题的变体。
互连网络演进的三个线程最近合并在一起。自1990年代初以来，处理器内存和处理器间互连网络的设计几乎没有差异。实际上，两者都使用了相同的路由器芯片。Clos和Benes的电话网络的一种变体也以胖树拓扑的形式出现在多处理器网络中[113]。
我们对历史的讨论集中在拓扑上，因为它是网络最可见的属性。当然，路由和流控制方法是与拓扑并行发展的。早期的路由芯片采用简单的确定性路由以及电路交换或存储转发分组交换。后来的路由器采用具有复杂的死锁避免方案和虚拟通道流控制的自适应路由。
在下一章中，我们将从拓扑到逻辑门的简单互连网络的完整说明开始，然后再深入探讨互连网络的“大图”视图。其余各章将详细介绍。它们分为五个主要部分：拓扑，路由，流控制，路由器体系结构和互联网络性能。每个部分都是组织的小工具，每部分的第一章介绍基础知识，而后几章介绍更多涉及的主题。