F.3 连接两个以上设备

到目前为止，我们只考虑了两个设备通过黑盒网络通信的连接方式。但互连网络真正吸引人的地方，是能够将数百个、甚至数千个设备连接在一起；这一点也使其构建更加困难。为了连接两个以上设备，网络必须具备适当的结构和更多功能。本节继续采用黑盒方法，从概念层面介绍多设备互连所需的附加网络结构与功能。F.4–F.7 节将进一步讨论各项主题的细节。在适用之处，我们会将这些结构与功能，同上一节介绍的网络介质、流量控制及其他基础概念联系起来。本节还按照连接结构，将网络分为共享介质网络与交换介质网络两大类，并加以比较。最后扩展网络性能的表达式，再给出一个例子。

附加的网络结构与功能：拓扑、路由、仲裁和交换

互连两个以上设备的网络，需要通过某种机制，在分组源端与目的端之间建立物理连接，以传送分组并将其投递到正确目的地。这些机制有不同实现方式，不同互连网络领域之间也可能有很大差异。不过，不论属于哪个领域，所涉及的网络结构与功能类型基本相同。

多个设备通过网络互连时，往往不能用专用链路永久建立它们之间的连接。这样做要么限制过强，因为给定源端的所有分组都只能到达同一个目的端，而不能发往其他目的端；要么成本高得难以接受，因为每个源端到每个目的端都需要一条专用链路。下一节将进一步评估这一点。因此，网络通常让不同设备对共享路径；路径如何共享，由网络的连接结构决定，这种结构通常称为网络拓扑。拓扑回答的是一个重要问题：“分组有哪些可能的路径？”这些路径应使分组到达预定目的地。

凡是互连两个以上设备的网络，还需要一种将每个分组投递到正确目的地的机制。相应功能称为路由，可以定义为：计算从分组源端到其目的端的有效路径所需执行的一组操作。路由回答的是：“对分组而言，可能路径中的哪些路径是允许的，即有效的？”同样，目的是使分组到达预定目的地。根据网络的不同，这个功能可以在源端执行，计算整条路径；也可以在中间设备执行，动态计算部分路径；还可以在每个可能的目的设备执行，核实该设备是否就是分组的目标。通常需要扩展图 F.4 中的分组首部，以包含必要的路由信息。

一般而言，网络中的不同设备对会共享路径或路径的一部分，因此分组可能请求共享资源。多个分组同时请求同一资源时，需要用仲裁功能解决冲突。仲裁与流量控制共同回答：“路径何时可以供分组使用？”每次仲裁都会产生一个胜者，并可能有多个败者。败者未获准访问所请求的资源，通常需要缓冲。如前一节所述，可以实现流量控制，以防止缓冲区溢出。胜者获得的资源接通后，形成了可继续前进的路径，它便向目的端推进。这一功能称为交换。交换回答的是：“如何将路径分配给分组？”为了提高已有通信资源的利用率，大多数网络不会一次建立整条端到端路径，而是像 F.5 节将解释的那样，通常逐段建立。

无论网络拓扑采用何种形式，只要连接两个以上设备，除了上一节的基本功能，都必须实现路由、仲裁和交换这三项功能。不过，其复杂度与执行顺序取决于网络拓扑类别，下面将进一步讨论。一般而言，路由、仲裁和交换负责在拓扑提供的可能路径中，建立从源端到目的端的一条有效路径。路径建立后，再用前面介绍的分组传输功能可靠地发送分组，并在相应目的端接收。如果实现了流量控制，它会通过限制发送方来防止缓冲区溢出；流控可以在端到端层次、网络内部链路层次，或两个层次同时实现。

共享介质网络

连接多个设备最简单的方法，是让它们共享网络介质，如图 F.8(a) 的总线。这也是传统的设备互连方式。共享介质可以采用半双工：数据能够沿任一方向传输，但同一设备不能同时发送和接收；也可以采用全双工：数据可沿两个方向传输，同一设备可以同时收发。直到不久之前，多数系统的 I/O 设备通常还共享一条 I/O 总线，早期片上系统（SoC）设计也使用共享总线连接片上部件。最流行的局域网以太网，最初是一条由最多约一百台计算机共享的半双工总线，不过如今也有交换介质版本。

共享总线网络与交换网络的连接结构比较 — 图 F.8 (a) 共享介质网络与 (b) 交换介质网络。以太网最初使用共享介质，如今已有交换式以太网。共享介质网络上的全部节点，必须动态共享一条链路的原始带宽；交换介质网络则可以支持多条链路，提供更高的原始聚合带宽。

图内术语：Node＝节点；Shared-media network＝共享介质网络；Switched-media network＝交换介质网络；Switch fabric＝交换结构。

由于网络介质共享，必须有机制协调并仲裁介质的使用，保证同一时刻只发送一个分组。如果网络设备之间的物理距离很短，可以由中央仲裁器授予发送权限。此时，网络节点可以通过专用控制线连接仲裁器。但对节点很多、分布距离很大的网络，集中仲裁并不现实，因此也采用分布式仲裁；最初的共享介质以太网 LAN 就属于这种情况。

共享介质分布式仲裁的第一步，是“先观察，再行动”。节点首先检查网络，避免在已有分组传输时尝试发送。发送前先监听以避免冲突，称为载波侦听。互连空闲时，节点尝试发送。当然，事先观察并不保证成功，因为另一个节点也可能在同一时刻决定发送。两个节点同时发送，就会发生冲突。假定网络接口能够通过监听，判断线路上的其他数据是否干扰了自己的数据，从而检测到冲突。为发现冲突而进行的监听称为冲突检测，这是分布式仲裁的第二步。

问题还没有完全解决。如果检测到冲突后，网络中的每个节点都等待完全相同的时间，监听确认没有流量，然后再次发送，节点就可能继续同步，一再相互冲突。为避免重复碰撞，分组遭到破坏的每个节点在重发前，都要等待一个随机时间，也称退避。随机化打破了同步。如果继续发生冲突，则重传尝试之间的等待时间按指数增长，以免给网络造成过重负担。

虽然这种方式控制了共享介质上的拥塞，却不能保证公平：发生冲突的节点还在等待时，后来到达的节点可能已经成功发送。如果没有很多节点同时提出大量网络需求，这个简单方法效果很好。但在高利用率下，由于介质共享且缺乏公平保证，性能就会下降。另一种能支持公平性的共享介质分布式仲裁方法，是在节点之间传递令牌。获得令牌的节点得到使用网络的权利。如果令牌在节点间循环传递，仲裁过程就能保证一定程度的公平性。

仲裁结束、某个设备获准访问共享介质之后，交换功能十分直接：该设备只需将自身接入共享介质，就建立了通向每个可能目的端的路径。路由也非常简单，因为所有设备都连接到同一共享介质，都会看到每个分组；每个设备只需检查该分组是否发给自己即可。这种策略还有一个有利的副作用：设备只需发送一次，就能把分组发给共享介质上的所有设备。这种通信方式称为广播；与之相对，单播中的每个分组只发给一个设备。共享介质使向每个设备广播分组十分容易，也便于向一部分设备发送，即组播。

交换介质网络

另一种方式，并不让所有相连节点同时共享整个网络介质，而是在节点共享的若干互不相交部分之间进行切换。这些部分由无源点到点链路及相连的有源交换部件组成；交换部件动态地在不同源端—目的端设备对之间建立通信。这些无源和有源部件共同构成网络交换结构（network switch fabric），也称 network fabric，端节点连接在这个结构上。图 F.8(b) 给出了概念示意。

F.4–F.7 节将更详细地介绍交换结构，进一步揭示交换介质网络黑盒的各个层次。不过，仅从图 F.8(b) 的高层视图，就已经可以看出交换介质网络相对于共享介质网络的潜在带宽优势：其聚合带宽可以高出很多倍，从而有可能获得更高的有效带宽。共享介质在任何时刻最多允许一个节点发送分组，而交换介质网络可能允许全部相连节点同时发送。

与共享介质网络一样，交换介质网络也必须实现前面提到的路由、仲裁和交换三项附加功能。每个分组进入网络时，先进行路由，在拓扑提供的路径中选择通往目的端的一条。分组请求的路径，必须由某个集中式或分布式仲裁器授予；仲裁器解决同一路径资源上的并发请求冲突。请求的资源获准后，网络接通所需连接以建立路径，使分组能够向目的端转发；若未获准，分组通常需要缓冲。交换网络内部通常按路由、仲裁、交换的顺序执行；共享介质网络中的路由则通常最后执行。

共享介质网络与交换介质网络的比较

一般而言，共享介质网络的优势在于成本低；相应的代价是，聚合网络带宽完全不会随互连设备数增加而扩展。此外，还需要全局仲裁机制解决请求冲突，这可能引入另一种瓶颈，进一步限制可扩展性。每增加一个接入共享介质的设备，还会增大导体的寄生电容，从而增加飞行时间中的传播延迟，并可能延长时钟周期。此外，共享介质不断授予不同的请求设备，也使网络分组传输更难流水化。

交换介质网络的主要优势，是所实现的网络资源量随相连设备数量增加，从而提高聚合网络带宽。它允许多对节点同时通信，能够提供远高于共享介质网络的有效带宽；还可以将系统扩展到共享介质无法实现的大规模节点数。不过，如果网络资源按超线性速度增长，这个扩展优势也会成为缺点。若网络成本超线性增长，而有效带宽只随互连设备数次线性增长，那么对许多应用与互连领域而言，这就是低效率的设计。

性能刻画：延迟与有效带宽

上述路由、交换和仲裁功能，为分组传送延迟引入了额外分量，必须计入总分组延迟表达式。假定不存在网络资源竞争，例如网络无负载，则总分组延迟为：

\begin{aligned} \text{延迟}={}&\text{发送开销}+ \left(T_{\mathrm{TotalProp}}+T_R+T_A+T_S\right)\\ &+\frac{\text{分组大小}}{\text{带宽}}+\text{接收开销} \end{aligned}

其中， $T_R$ 、 $T_A$ 、 $T_S$ 分别是分组经历的总路由时间、总仲裁时间与总交换时间，可以通过测量得到，也可以根据更详细的分析计算得到。这些分量与网络链路上的总传播延迟 $T_{\mathrm{TotalProp}}$ 相加，构成分组的总飞行时间。

上式仅给出总分组延迟的下界，因为它没有计入资源竞争可能造成的额外延迟。网络负载很重时，多个分组可能同时请求相同网络资源，形成竞争并降低性能。仲裁失败的分组必须等待在缓冲区中，其等待时间作为竞争延迟增加到分组延迟中；上式没有包含这部分。当网络或其一部分趋于饱和时，竞争延迟可能比零负载、甚至轻负载条件下的整个分组延迟大几个数量级。遗憾的是，当网络负载超过中等水平时，用解析方法计算总分组延迟并不容易。在这种情况下，用详细网络模型的周期精确仿真来测量这些量，是估算分组延迟更好、更准确的方法。不过，上式仍可用于计算最佳情况下的延迟下界。

出于类似原因，有效带宽也不容易精确计算，但适当扩展上一节末尾的模型，可以估算最佳情况下的上界。需要做的是确定整个端到端网络管道最窄的部分，也就是求出互连设备的整个网络中的注入带宽 $BW_{\mathrm{NetworkInjection}}$ 、接收带宽 $BW_{\mathrm{NetworkReception}}$ 和网络带宽 $BW_{\mathrm{Network}}$ 。

网络注入带宽可以直接用链路注入带宽 $BW_{\mathrm{LinkInjection}}$ 乘以网络注入链路总数。网络接收带宽也可由 $BW_{\mathrm{LinkReception}}$ 类似求出，但还要乘以一个反映应用流量及其他特征的因子。连接两个以上设备时，在分析流控对接收链路带宽的影响时，不能再假定源端与目的端一一对应。例如，对于具有多对一流量特征的应用，来自不同注入链路的若干分组可能同时到达同一接收链路，导致接收链路竞争。

这种影响可以用平均接收因子 $\sigma$ 表示；它既可以测量，也可以通过详细分析计算，定义为到达接收链路的分组中能够被接受的平均比例或百分比。只有这些分组可以立即投递，因此网络接收带宽按这一因子缩减。这种下降源于应用行为，与网络内部特征无关。最后，网络带宽 $BW_{\mathrm{Network}}$ 则考虑包括竞争在内的内部网络特征。随着后面进一步揭示互连网络黑盒的内部结构，我们将逐步推导其计算表达式。

总体而言，网络端到端交付给应用的有效带宽，由这三部分中的最小者决定：

\begin{aligned} \text{有效带宽} &=\min\left(BW_{\mathrm{NetworkInjection}},BW_{\mathrm{Network}},\sigma\times BW_{\mathrm{NetworkReception}}\right)\\ &=\min\left(N\times BW_{\mathrm{LinkInjection}},BW_{\mathrm{Network}},\sigma\times N\times BW_{\mathrm{LinkReception}}\right) \end{aligned}

下面利用这些表达式，比较 OCN、SAN、LAN、WAN 四个互连领域中，共享介质网络与交换介质网络的延迟和有效带宽。

例题：网络规模扩大时的延迟与有效带宽

当互连节点数 $N$ 从 4 扩大到 1024 时，绘制共享介质与交换介质 OCN、SAN、LAN、WAN 的总分组延迟与有效带宽。假定所有网络链路，包括节点处的注入与接收链路，数据带宽都为 8 Gbps，传送大小为 100 字节的单播分组。共享介质网络共享一条链路，交换介质网络的网络链路数至少等于节点数；两者都忽略内部竞争对延迟与带宽的影响。

端节点的每分组发送与接收开销分别为 $x+0.05\ \mathrm{ns/byte}$ 和 $(4/3)x+0.05\ \mathrm{ns/byte}$ ；OCN、SAN、LAN、WAN 的 $x$ 分别为 0 μs、0.3 μs、3 μs、30 μs，互连距离依次为 0.5 cm、5 m、5000 m、5000 km。此外，假定总路由、仲裁与交换时间为常数或节点数的函数：共享介质网络中， $T_R=2.5$ ns、 $T_A=2.5N$ ns、 $T_S=2.5$ ns；交换介质网络中， $T_R=T_A=T_S=2.5\log_2N$ ns。最后，考虑应用流量与网络结构，假定共享介质网络的平均接收因子 $\sigma=N^{-1}$ ，交换介质网络的平均接收因子为多对数形式 $\sigma=(\log_2N)^{-1/4}$ 。

解答总分组延迟的所有分量都与上一节例题相同，只有飞行时间额外增加了路由、仲裁和交换延迟。共享介质网络增加的延迟总计为 $5+2.5N$ ns；交换介质网络增加的延迟总计为 $7.5\log_2N$ ns。图 F.9 只绘出 OCN 和 SAN 的延迟，因为这两类网络的结果更值得关注。

对 OCN 而言，当节点数量为中等到较大规模时， $T_R$ 、 $T_A$ 、 $T_S$ 的总和占据飞行时间的主要部分，并远大于其他每个延迟分量，共享介质网络尤其如此。由于两种网络的仲裁延迟不同，共享介质的延迟随节点数增加而增长得远比交换介质剧烈。对 SAN 而言，在大多数网络规模下， $T_R$ 、 $T_A$ 、 $T_S$ 都主导飞行时间；但只有当共享介质网络规模很大时，它们才大于其他每个延迟分量。在交换介质网络中，这些分量小于其他延迟分量，却不可忽略。对 LAN 和 WAN 而言，飞行时间由传播延迟主导；正如上一节计算所示，传播延迟又主导其他延迟分量。因此，无论共享介质还是交换介质， $T_R$ 、 $T_A$ 、 $T_S$ 都可忽略。

OCN 与 SAN 中共享介质和交换介质网络的延迟随节点数量变化 — 图 F.9 OCN 与 SAN 中延迟随互连节点数变化的半对数图。由于发送、接收开销和传播延迟较小，路由、仲裁和交换对这两个领域的网络延迟影响更大，节点数量很多时尤其如此。

图内横轴为节点数 $N$ ，纵轴为延迟（ns）；shared＝共享介质，switched＝交换介质。

图 F.10 给出了四个网络领域中有效带宽随互连节点数的变化。所有共享介质网络的有效带宽都不会随规模增长，因为所有接收链路在同一时刻最多接收一个单播分组；除 OCN 外，这一带宽还进一步受各网络接收开销的限制。所有交换介质网络的有效带宽都随节点数增加而提高，但会按平均接收因子缩减；除 OCN 外，接收开销还会进一步限制有效带宽。

四种网络领域中共享介质和交换介质的有效带宽随节点数量变化 — 图 F.10 四种网络领域中有效带宽随互连节点数变化的半对数图。随着网络节点数增加，各个互连领域中共享介质与交换介质网络之间的有效带宽差距显著扩大。对本例给定的参数，只有交换式片上网络能够获得等于聚合带宽的有效带宽。

图内横轴为节点数 $N$ ，纵轴为有效带宽（Gbit/s）；各条曲线分别表示 OCN、SAN、LAN、WAN 的交换介质与共享介质网络。

译注： 原图注称交换式 OCN 可达到聚合带宽，但题设给定的接收因子为 $\sigma=(\log_2N)^{-1/4}<1$ ，按本节公式，有效带宽还会受到这一因子的限制。例如 $N=1024$ 时， $\sigma\approx0.5623$ ，有效带宽上限约为 $8N\sigma=4606.8$ Gbit/s，低于 $8N=8192$ Gbit/s 的聚合注入带宽，也与图中曲线相符。原图注的这句话与题设及曲线不一致。

既然优势如此明显，为什么以前没有一直采用交换网络？早期计算机慢得多，共享网络介质对性能影响不大。此外，早期 LAN 和 WAN 的交换机占据多块大型电路板，体积接近整台计算机。随着 Moore 定律推动技术发展，交换机尺寸显著缩小，系统对高性能通信的需求也大幅提高。交换网络使通信能够像处理器和主存一样，受益于硅技术的快速进步。电信公司的交换设备曾经有大型机那么大，如今却已有单芯片交换机，甚至整个片上交换网络。因此，当前技术与应用的发展趋势都倾向于交换网络。正如单芯片处理器使处理器在许多出人意料的场合取代逻辑电路一样，单芯片交换机和片上交换网络也正在多个应用领域中取代共享介质网络，即总线。例如，交换网络 PCI Express（PCIe）于 2005 年被引入，用于取代个人计算机主板上传统的 PCI-X 总线。

前一例还强调了优化 OCN 和 SAN 的路由、仲裁与交换功能的重要性。特别是在这两个领域，互连距离与开销通常小到足以使延迟和有效带宽对这些功能的实现质量更加敏感，网络规模越大越是如此。因此，这些领域通常主要采用更快的硬件方案。在 LAN 和 WAN 中，由于性能主要取决于其他因素，较慢但更灵活的软件实现就足够了。对于 OCN 和 SAN，交换介质网络的拓扑设计，也会显著影响实际性能能有多接近延迟下界和有效带宽上界。

接下来的三节将讨论交换网络中的这些重要问题，下一节首先介绍拓扑。