输入队列交换机调度算法的双向图匹配表示法

"基于输入交换队列的双向图匹配调度算法的协议模型表示 (2005年)" 本文主要探讨了在高速交换机和路由器领域中，如何处理基于定长分组（信元）的双向图匹配输入队列交换机的调度算法。作者鄂大伟提出了一种统一的符号表示和描述方法，旨在解决输入队列调度策略的复杂性，尤其是输入队列中的冲突问题。 输入队列技术因其简单的交换结构和较低的内部交换速度需求而被广泛应用。然而，它也面临挑战，如输入队列中的头部阻塞（HOL）现象，这在单播和均匀业务流量条件下限制了交换机的吞吐率至58.6%。多播交换机受HOL阻塞影响更大，因为一个信元可能需要输出到多个端口，导致更低的吞吐率。 为了改善这种情况，研究者们已经提出了一些输入队列调度算法，例如采用虚拟输出队列（VOQ）技术，可以实现100%的吞吐率，从而推动了输入队列交换机研究的进步。在这些基于双向匹配图的调度算法中，匹配过程通常被视作一个协议过程。然而，不同的算法有着各自的描述方式，缺乏统一的符号化表示，这给算法的性能分析和实现带来了困难。 为此，作者提出了一种双向图匹配算法的状态信息符号表示模型，该模型能够清晰地展示算法的匹配迭代过程，简化了描述，为算法的编程实现和性能仿真分析提供了便利。具体来说，这种模型将输入/输出端的匹配过程结构化，使得分析和理解算法变得更加直观。 双向图（bipartite graph）是这种调度算法的核心概念，它是由两个节点集合构成的图，其中的边仅连接不同集合的节点。在交换机的上下文中，一个集合代表输入端口，另一个集合代表输出端口，边则表示潜在的匹配。调度算法的目标是在每个时隙中找到一个无冲突的匹配，以最大化吞吐量和效率。 这项工作为输入队列交换机的调度算法提供了一种标准化的表示方法，有助于优化调度策略，减少冲突，并提升网络性能。通过这种协议模型表示，研究者可以更方便地比较、分析和实现不同的匹配算法，进一步推动交换技术的发展。