见微知著-浅析数通交换机之四

前言

交换机是数通行业高速发展的一个缩影。“点石成金”的先驱们不懈的探索，使交换机产业迅猛发展。相比于时下的交换机，早期的产品，无论是性能还是功能都有很大差距，但每个产品的出现都有其时代意义。让我们进入时光隧道，跟随前辈的足迹，去探访垦荒的年代吧。
本文既非工程学术文档，亦非原厂文宣，乃见微知著，温故而知新，文笔粗拙，贻笑大方。

<续前文>

3.3Crossbar交换矩阵

如图所示，Crossbar交换矩阵在数据帧交换期间，在输入端口和输出端口之间创建瞬态连接。实际上是电子开关矩阵在每个可能的输入和输出端口对之间建立连接。矩阵控制逻辑在纳秒时间内，逐帧将给定输入连接到相应的输出，然后断开端口连接，为下一帧交换做准备。由于每个输入端口可以同时连接到某个输出端口，因此Crossbar矩阵的总数据传输能力可以比共享总线大得多，并且实际上随着端口数量的增加而增长。

3.3.1Crossbar 交换矩阵中的组播流程

与共享内存或共享总线架构不同，Crossbar交换矩阵不提供将数据帧从一个输入端口同时传输到多个输出端口的方法。有两种常见的方法来处理Crossbar交换矩阵中的组播流量：多个单播传输：每当一个数据帧需要传输到多个输出端口时，输入端口执行一系列单独的传输，以连接矩阵的每个目的地。就像共享内存架构一样，输入端口维护一个传输端口映射，指示数据帧和输出端口的对应关系。随着交换矩阵仲裁和数据帧传输的进行，每个目的输出端口都会从列表中选中，直到传输端口映射全部为零，之后输入端口可以释放数据帧缓存区。

该方法的优点是，简化了Crossbar交换矩阵的设计。如果组播数据帧作为多个单播进行传输，则无需在交换矩阵中进行任何特殊调整来处理组播流量。缺点是跟踪组播传输过程所需的输入端口复杂性大大增加。

虽然多次传输同一数据帧似乎浪费了交换矩阵的容量，但要考虑到有问题的数据帧会使用所有目的输出端口上的带宽。如果矩阵架构为支持所有端口的容量总和，则当组播帧单独传输到每个输出端口时，它仍然是非阻塞的。由于组播流量产生的数据帧复制，容量过度配置都将减少。该方法仍然可以处理总容量，但排队时延（交换机时延）将增加，以至于组播流量会占到总负荷的很大一部分。

专用组播数据路径：交换机可以提供一个或多个专门用于组播流量的逻辑输出端口。组播端口实际上可以看作是一条共享总线，除了该端口的单播线路外，它还路由到每个输出端口，如下图所示：

当组播流量预计只是提供的总负荷的一小部分，并且交换矩阵本质上是阻塞的或几乎没有多余的容量时，这种方法是有意义的。通过从交换矩阵上的单个端口输出卸载组播流量，可以避免上文谈及的数据帧复制，并将大部分容量专用于单播流量。该方法的缺点是：必须配置每个输出端口，以便从交换矩阵的专用单播输出线路以及从共享组播端口输出接收数据帧。如果组播流量占总负荷的较大部分，则共享组播总线的容量可能会是一个限制因素。

3.3.2Crossbar 交换矩阵实现

实现Crossbar交换矩阵通常有两种方法：

物理矩阵：该矩阵可以通过在一个平面（输入端口）上平行放置导电材料条，并在第二个平面（输出端口）上以直角放置导电材料条来创建。每个输入端口走线通过晶体管开关电路连接到每个输出端口走线，交换矩阵控制逻辑根据输入端口控制器发出的请求以及仲裁器对这些请求的处理来决定哪些晶体管开关是闭合还是打开。

根据交换矩阵支持的数据速率，通常需要为每个端口（输入和输出）使用多个线路跟踪。然后，可以在每个时钟周期传输多个数据位，这会降低给定数据传输速率的时钟速度，其代价是增加了交换矩阵芯片上交换机端口的引脚数。

逻辑矩阵：该矩阵可以通过由仲裁器控制将每个输出端口的信号定义为从输入端口处的信号派生的逻辑功能来创建。即Crossbar交换矩阵可以从标准数字逻辑模块构建。与物理矩阵一样，通过根据多个并行信号定义每个输入和输出，可以降低时钟速度，但代价是增加了交换矩阵接口的引脚数。

通常，物理矩阵可以用更小且不复杂，实现成本更低的交换矩阵来实现。其缺点是电路通常必须定制设计。通常不可能使用用于合成逻辑的传统IC设计工具在芯片中构建物理矩阵。逻辑矩阵的优点是，由于它使用可合成的逻辑，因此在半导体制造过程中变得更加便利，且对专业设计技能的需要更少。

根据时钟速度和矩阵端口接口的宽度，可以创建更大的交换容量。如在100MHz时钟上运行的16端口、16位宽（每个端口16个信号）矩阵具有25.6Gb/s 的有效数据传输能力。这种矩阵适用于大量的百兆端口或相当多的千兆以太网端口。

3.3.3 队头阻塞问题

Crossbar交换矩阵可以提供端口可扩展性极强的高容量交换机矩阵。但它们存在称为”队头阻塞”的系统性问题。设想当多个输入端口必须争夺单个输出端口的可用性时会发生什么情况。如下图所示：

描述了这样一种情况：大量流量发往输出端口9，端口1、2和3都有数据帧排队等待端口9变为可用。假设交换机仲裁算法是公平的，这些数据帧将以有序的方式传输到端口9。交换机容量将均匀分布在具有发往单个目的输出端口的流量的所有输入端口之间。端口4存在问题，其数据帧已排队并等待传输到各个输出端口。但是队列中的第一个数据帧将发送到输出端口9，此时该端口正在经历短期拥塞，由于一次只有一个输入端口能够将数据帧传输到输出端口9，因此每个具有排队等待端口9的数据帧的输入端口都必须等待轮到它。假设采用公平的轮循机制调度，端口4可能必须等待端口1、2和3将各自的数据帧传输到端口9，然后才能卸载其队列顶部的数据帧。同时端口4的输入队列中，在发往端口9的数据帧后面，还有数据帧在等待。这些数据帧针对的是未拥堵的端口，即目的输出端口（图中的端口6、1和3）处于空闲状态并等待流量。但是，端口4无法继续传输这些数据帧，因为前行的数据帧阻止了进度。注意，这种情况不是端口9中的任何设计缺陷造成的，而是必然存在的。存在这样一种瞬态过载情况，即以端口9为目的地的流量暂时超过输出链路的容量。交换机通过随时间推移提供的负荷来解决短期拥塞问题。在该扩展时间内，数据帧必须在交换机内的队列中等待。理想情况下，希望数据帧在输出队列中等待端口9，但需要跨交换矩阵传输数据帧以实现该状态。由于多打一流量模式，交换矩阵容量也遇到暂时性拥塞，因此某些数据帧仍在等待通过交换矩阵的输入队列中。正是这种情况导致了阻塞问题。

队头阻塞会降低交换机的聚合吞吐量。如果某些端口经常遇到短期拥塞（如连接到服务器的端口通常是提供负载的目标），则可以降低完全未拥塞的其他端口的吞吐量。这是一种不可取的情况。没有充分的理由仅仅因为端口1、2和3向端口9发送大量流量而降低端口4和6之间的吞吐量。

3.3.4 解决队头阻塞问题

目前在实际交换机中已经有多种针对队头阻塞问题的解决方案，包括：

队列前瞻

优先级队列

每输出端口输入队列

每种方法在实现的复杂性和消除阻塞效应的有效性方面都有所不同。下文逐一讨论。

3.3.4.1 队列前瞻

最简单的方法就是在输入队列上实现”向前看”。每个输入端口都针对目的输出端口进行仲裁，该端口由其队列顶部的数据帧确定。当多个输入端口争用同一输出端口（如上图中的端口9）时，其中一个输入端口将被授予访问权限，而其他输入端口将被暂时阻止。发生这种情况时，被阻止的输入端口可以向前看其输入队列中的下一数据帧，以查看第二数据帧所需的目的输出端口是否可用。如果是，则端口可以传输第二个数据帧，而不是队头的数据帧。传输后，输入端口可再次对队列头部的数据帧进行仲裁，并在必要时，如果拥塞的输出端口仍然不可用，则重复前瞻算法。

简单的单级队列前瞻功能所需的硬件并不复杂，不会显著增加队列管理逻辑的成本。当然，只有当有一个数据帧阻挡了队列头部时，该机制才有效。如果队列中的第一个数据帧和第二个数据帧都发往拥塞的输出端口，则队列中的所有其他数据帧仍被阻止（如上图中的输入端口1）。但是，两帧都是队头阻止的概率低于只有一帧引起故障的概率。当交换矩阵仲裁器提供了一种发出常备请求的方法时，队列前瞻才最为有效，即请求输出端口并让交换机在输出端口可用时提供通知，而无需输入端口部分执行进一步操作。这样，无论发往拥塞输出端口的流量的时间分布如何，队头的数据帧将始终确保交付。输入端口可以继续处理前瞻帧，直到交换矩阵仲裁器告诉它该拥塞的输出端口已变为可用，从而结束队头块。

3.3.4.2 优先级队列

解决队头阻塞问题的另一种方法是，为每个输入端口配备多个代表不同优先级的队列，如下图所示：

数据帧根据分类引擎确定的优先级放入其中一个输入队列中。输入端口名义上按优先级顺序调度用于交换矩阵仲裁器的数据帧，即高优先级队列中的数据帧相对于低优先级队列中的数据帧获得优先处理。当所有高优先级队列都为空或当前遇到队头阻塞时，将从较低优先级的队列处理数据帧。虽然队头阻塞仍然可能会发生，但至少低优先级数据帧永远不会阻塞优先级较高的数据帧。此外除了优先级排队之外，还可以实现队列前瞻，从而进一步降低阻塞的可能性（特别是对于优先级较高的队列）。

关于优先级输入队列的实现，有以下几点需注意：

可以在任何输入端口上实现优先级队列，而无需考虑此机制是否在其他输入端口上使用。即输入端口具有多个队列并根据优先级分类为交换矩阵仲裁器选择数据帧这一做法，对于交换矩阵或交换机上的其他端口是不可见的。因此，只要事先知道哪些端口会阻塞，则仅在需要时才能产生额外开销。队列优先级可以有效地与仲裁器优先级相结合。如果交换矩阵本身支持多个优先级的仲裁器，则可以将输入队列映射到交换矩阵仲裁器优先级上。

系统提供的优先级或队列数无需与分类引擎解析的优先级数或输出端口上提供的服务类数相同。在输入队列中确定优先级的目的是避免高优先级流量被低优先级流量阻塞。无论输入队列优先级如何，所有数据帧仍将最终进入输出队列，并根据其（端到端）用户优先级进行调度。正如用户优先级映射到输出队列中的可用服务类别一样，用户优先级也映射到可用的输入队列数和/或交换矩阵仲裁器优先级上。

3.3.4.3 每输出端口输入队列

队头阻塞问题的第三个解决方案是为每个可能的输出端口提供一个输入队列，如下图所示：

在接收数据路径准备好在交换矩阵传输数据帧时，它必须知道目的输出端口。端口可以为每个可能的输出端口维护一个单独的输入队列，而不是将所有等待传输的数据帧放入单个输入队列（或一组优先队列）中。调度程序以公平（如轮循机制）的方式从非空队列中选择数据帧。如果目的输出端口可用，则输入端口将通过交换矩阵传输该队列中的第一个帧。如果目的输出端口繁忙，则输入端口将移动到下一个非空队列。该机制完全消除了队头阻塞，因为给定输出端口的不可用，不会阻止流量移动到那些可用的端口，而发往可用端口的数据帧在当前无法传输的数据帧后面等待的场景是不会发生的。

与队列前瞻方案的情况一样，如果交换矩阵仲裁器使用了一种发出暂存请求的方法，即让交换机在以前请求的输出端口可用时提供通知，则每个输出端口排队效果最佳。输入端口可以继续处理未拥塞端口的数据帧，直到交换矩阵仲裁器告诉它该（以前拥塞的）输出端口现在可供使用。还可以将每个输出端口的队列与优先级队列组合在一起。每个输出端口可以由不同优先级的多个队列提供服务。在每个端口的基础上，高优先级数据帧将优先于低优先级数据帧，如上文所述。

这种终极解决方案的价格不仅大大增加了所需输入队列内存总量（无论哪种方式，排队的帧数都相同），而且队列内存数据结构以及用于管理和调度这些队列的硬件的复杂度也相应增长。

在具有大量端口的交换机中，每个输出端口排队系统的成本和复杂性可能会非常高。

3.3.4.4 仲裁矩阵连接

在共享内存体系架构中，尝试写入共享内存或从共享内存中读取的每个端口都必须通过仲裁器来获得内存数据路径的使用权。而一旦获得访问权限，任何输入端口都可以存储发往任何输出端口的数据，并且输出端口可以读取任何输入端口写入的数据。同样，交换机上的输入端口必须经过仲裁器才能将数据发布到共享总线上，但数据传输本身可以发送到任何输出端口（或同时传输到多个输出端口）。共享内存和共享总线体系架构都没有在特定交换机端口对发送或接收数据的权利进行仲裁的做法。

Crossbar交换矩阵会有所不同。根据数据传输的需要，在特定的输入和输出端口之间创建瞬态数据路径。当输入端口希望跨Crossbar交换矩阵传输数据帧时，它必须请求从自身访问特定的目的输出端口。相反，共享内存或共享总线体系架构中的输入端口只需要请求使用公共交换矩阵。

如下图所示：

Crossbar交换矩阵必须提供一种机制：每个输入端口提交对选定输出端口的路径请求，在同一输出端口的多个同时请求之间进行仲裁，作为仲裁的结果授予请求使交换矩阵控制逻辑能够在适当的时间创建所需的路径。

3.3.4.5 仲裁请求类型

在提供大负荷的情况下，仲裁调度必须以有效和公平可控的方式运作。

虽然仲裁逻辑的细节往往高度依赖于产品和实现，但大多数Crossbar交换矩阵仲裁器支持来自输入端口的以下一种或多种类型的架构请求：

即时请求：输入端口可以请求访问特定输出端口以便立即使用。如果目的端口可用，仲裁器将通过向请求输入端口颁发授权来做出响应。否则，授予将被拒绝，仲裁器不会采取进一步行动。输入端口可以自由地在以后对相同或不同的输出端口发出进一步的请求。对于在具有前瞻功能的队列顶部的数据帧发出的第一个请求，立即请求可能适用。如果请求获得批准，输入端口可以传输数据帧并继续到队列中的下一帧。如果请求被拒绝，输入端口可以对同一输出端口发出长期请求，然后立即请求队列中的下一帧（前瞻）。

同步请求：请求输出端口，并等待，直到授予。在此模式下，请求和授予是同步操作。在未完成的请求被授予之前（或由于某些异常情况超时），输入端口不能发出其他请求。同步请求适用于既不包含优先级也不包含前瞻功能的简单输入队列系统。如果设计无法利用额外的端口逻辑复杂性，则无需提供额外的端口逻辑复杂性。

永久请求：请求在所需输出端口可用时通知输入端口。仲裁器为每个输出端口单独维护一个内部常设请求列表。当输出端口可用时，矩阵仲裁器决定授予哪个输入端口访问权限（基于调度算法、优先级等），并通知获胜者可以授予其请求。然后，输入端口可以立即发出或同步请求，知道它将成功。

永久请求适用于支持前瞻、优先级和/或每输出端口排队的更复杂的系统。每当立即请求被拒绝时，输入端口都可以发出一个永久请求，并继续处理发往其他输出端口的数据帧。输入端口将在满足其常备请求时收到通知，并可以在此时采取适当的操作。支持永久请求的功能虽然对输入端口和矩阵仲裁器中的逻辑都带来了更多的复杂度，但可以显著提高交换矩阵的利用率和性能。

3.3.4.6 带内仲裁与带外仲裁

高速、高端口密度Crossbar交换矩阵的实现通常受到将信号移入和移出矩阵芯片所需的大量引脚的限制。为了实现千兆或更高的数据速率，通常必须使用8位或16位宽的接口路径。随着交换矩阵的端口密度增加，交换芯片上的引脚数量可以成百或数千个。除了在矩阵中移动数据所需的引脚外，还需要一种方法在输入端口和交换芯片之间发出仲裁请求和授权。通常有两种方法来实现此目的：

在没有严格引脚限制的交换矩阵上（如端口密度相对较低，或仅支持较低数据速率的交换矩阵），可以简单地为仲裁器添加额外的引脚。每个输入端口都对专用于仲裁功能的信号引脚发出请求，交换芯片可以在类似的专用线路上发出输出端口授权。

当引脚非常稀缺时，通常选择通过用于跨交换矩阵传输数据帧的相同数据路径发出仲裁请求。即输出端口请求被构造为”帧”，被发送到矩阵芯片内的仲裁器。同样，授权命令可以由矩阵仲裁器发出，并通过矩阵数据输出路径发送到相应的端口。作为减少引脚数的交换，增加了端口和矩阵仲裁逻辑的复杂性，必须解析通过矩阵接口传递的信息，以将仲裁请求和授权与数据帧传输分开。通过使用一些数据接口进行仲裁交换来减少可用带宽：在实践中，设计用于带内仲裁信令的交换机必须包含额外的容量来减少这种影响。

<未完待续>

Related Posts