《用于路由数据的交换装置、使用此装置的计算机互连网络与路由方法》由会员分享，可在线阅读，更多相关《用于路由数据的交换装置、使用此装置的计算机互连网络与路由方法（3页珍藏版）》请在金锄头文库上搜索。
1、用于路由数据的交换装置、使用此装置的计算机互连网络与路由方法专利名称：用于路由数据的交换装置、使用此装置的计算机互连网络与路由方法技术领域：本发明涉及用于在一计算机互连网络中路由数据的方法与系统的领域。具体地，本发明涉及一种具有用于将数据包从输入端口路由至输出端口的优化电路的交换装置(switching device)。背景技术：人们知道诸如单级包交换节点(single-stage packet switching node)的交换装置。这种节点具有给定的、固有的实现复杂度。即，在N端口包交换中，存在导致二次复杂度(quadratic complexity)的N对N连接问题。虽然存在许多不同交
2、换架构(例如，输入排队的、输出排队的、组合的输入与输出排队的、共享的存储器等)，但此复杂度以某种方式在所有这些架构中显露其自身。 此复杂度本质上起源于无阻塞需求，此需求要求任何一对一通讯模式(排列(permutation)可被路由而没有冲突。只有通过放宽此需求，即通过允许甚至在来自/去往不同端口的通信间发生冲突，才可降低该复杂度。这导致阻塞交换架构，所述架构通常基于共享媒体(诸如总线)或基于多级安排。这种方法的缺点为，由于例如基于总线的实现的物理限制可达到的总呑吐量是受限的。大部分现有的单级交换节点实现可满足非阻塞要求，S卩，它们提供了以全容量从任何输入端口发送至任何输出端口的能力。在基于交叉
3、开关(crossbar)的架构(其可以是缓冲的或无缓冲的)的特定情况中，这意味着交换节点包括N2个交叉点(crosspoint)。此外，在缓冲的交叉开关架构的情况中，每一交叉点包括一缓冲器，该缓冲器的大小允许在全来回(full round-trip)上的全链路利用。在许多情况，可明白，大量此缓冲容量将在大多数时候未使用，这代表了宝贵资源的浪费。发明内容根据第一方面，本发明实现为一交换装置，该交换装置适于连接一计算机互连网络的部分，其具有N个输入端口与M个输出端口，其中M优选地等于N，该装置适于经由直接交叉点路由数据包，所述直接交叉点被配置为根据计算机互连网络的连接需要，允许N个输入端口的每一个
4、只与输出端口的子集m 具体实施例方式本发明提出基于稀疏填充的交叉开关结构来减少冗余的交换装置。换句话说，交叉点被配置为允许在该交换器(switch)的N个输入端口只与输出端口的子集m 6有较低的复杂度。例如，对于N=32而言，只需保留约80%的交叉点。增加N允许相对于全连接而言渐近接近 75%交叉点。其次，在实施例中，旁路可以如下方式发挥功能当包到达交换器输入时，输入接口检查包的目的地是否是填充的交叉点。如果是，该包便会立即被路由至该目的地交叉点。否则，包不能够直接路由至其目的地列，且因此必须通过旁路被路由。该输入接口从可用旁路中选择一个，并将包路由至对应交叉点。优选地，每一旁路列有自己的调度
5、器(scheduler)。旁路调度器从其本身的列选择一包，且经由其回环将包路由至对应的旁路行APuy并路由至对应于包的目的地端口的特定交叉点。每一输出调度器调度来自旁路交叉点以及在其列中的一般交叉点的包。可考虑许多调度方法。此外，应注意，如果没有可用的旁路，包可能不得不被丢弃(例如，在有缓冲交叉开关的情况下)。如所述的，主要实施旁路以允许全连接性，S卩，每一端口可到达每一其他端口。应明白，旁路可能不适合具有严格的性能需求的连接。诸如上述的旁路典型地具有两个性能缺点首先，存在延时不利，因为采用旁路的每一包在离开交换器前会被存储和读取两次(在有缓冲交叉开关中)；其次，采用旁路的流全部共享有限的一组
6、交叉点，且访问有限的内部带宽，该带宽在设计上比连接的端口的可能最大总呑吐量小(得多)。例如，在图5中，从“向上”侧输入流向“向上”侧输出流动的所有流量的最大总呑吐量限制于单一回环路径的带宽，因此在最坏情况下，受影响流的呑吐量仅为25%(即，当每一输入以100%负载发送至一未填充的交叉点时)。仍可通过增加更多旁路改善此限制。如进一步描述的，交叉点移除模式不需要如图5所示般规则；稀疏性可根据计算机互连网络的连接需要，采取任何形状、对称(参见例如图6的示例性实施例)或不对称(图7)。此外，旁路行与列可显著地从所示出的模式改变。尤其应注意，严格地说，对于分别连接至所有列/行的行X或列y，不需要添加旁路
7、交叉点/&。同样地，在只有一个直接交叉点(由于特定的连接需要)要被移除的时候，可能实际上最好保持此交叉点，而不是添加对应旁路所需的两个交叉点。因此，可考虑对图5-7的相应变体。此方法可以直接方式而一般化至任何拓扑与任何路由方案；鉴于这些，可直接地确定对于任何交换器哪些回转从未被采用，且相应地除去交叉点。此外，通过添加多个额外行与列(未在图显示)可提高旁路容量。注意，严格地说，如果某些回转从未被采用，甚至不需要用于这些回转的旁路。然而，实现它对于测试/诊断目的仍可能有用。 而且，该方法也可一般化为考虑预期空间流量分布的特征。在一些包交换的应用中，在交换节点上观察到的流量模式可为高度非均匀
8、的，意味着流过一给定输入端口的流量在一组输出端口上是不平均地分布，及/或通过不同输入端口流入的流量呈现不同分布模式。对于一给定交换器而言，预期只有非常小流量的所有连接可映射到一共享的旁路。例如，HPC应用经常呈现非常特定的通信模式，其中，例如，多数通信在直接邻居之间发生。在这方面，根据本发明的方法可在实施例中包括确定网络的连接需要的初始步骤，例如，所述连接需要取决于数据包到达交换器端口的预期密度。其次，这转而允许根据确定的连接需要，优化交换器配置(即，用于要在网络中使用的一个或多个交换器的优化交叉点结构，以及可能地，这些交换器如何可被安排在网络中)。所属技术领域的技术人员知道，本发明可以实现为
9、系统、方法或计算机程序产品。因此，本公开可以具体实现为以下形式，即可以是完全的硬件、也可以是完全的软件(包括固件、驻留软件、微代码等)，还可以是硬件和软件结合的形式，本文一般称为“电路”、“模块”或“系统”。此外，在一些实施例中，本发明还可以实现为在一个或多个计算机可读介质中的计算机程序产品的形式，该计算机可读介质中包含计算机可读的程序代码。可以采用一个或多个计算机可读的介质的任意组合。计算机可读介质可以是计算机可读信号介质或者计算机可读存储介质。计算机可读存储介质例如可以是一但不限于电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。计算机可读存储介质的更具体的例子(非
10、穷举的列表)包括具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPR0M或闪存)、光纤、便携式紧凑磁盘只读存储器(CD-ROM)、光存储器件、磁存储器件、或者上述的任意合适的组合。在本文件中，计算机可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括但不限于一电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可
11、以是计算机可读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括一但不限于一无线、电线、光缆、RF等等，或者上述的任意合适的组合。可以以一种或多种程序设计语言或其组合来编写用于执行本发明操作的计算机程序代码，所述程序设计语言包括面向对象的程序设计语言一诸如Java、Smalltalk、C+，还包括常规的过程式程序设计语言一诸如”C”语言或类似的程序设计语言。该程序代码可有利地整个在一个或多个端节点或最低层交换器Slij (例如，特别是用于以太网网络)上执
12、行。它还可部分在一端节点或一最低层交换器且部分在一远程节点或交换器(例如，较高层交换器)、或整个在一个或多个较高层交换器上执行，如果架构允许的话。可考虑不同类型的网络。如已知的，除了网络功能性之外，这种交换器可仅视为计算机。在这方面，每一交换器能以硬件实现。但是，它能以能用计算机的一个或多个处理器执行的程序实现。能用计算机与处理器就本身而言是已知的。应了解，用于本发明的方面的任何操作可通过计算机程序指令(例如，经由互连网络的交换装置的交叉点路由数据的程序指令)实现。这种指令可例如被提供给通用计算机、节点或交换器、专用交换器、或其他可编程数据处理装置的处理器以产生一机器，使得经由交换器或其他可编
13、程数据处理装置的处理器执行的指令可创建用于实施上述功能/动作的装置。这些计算机程序指令也可存储在计算机可读取介质中，其可使交换器、计算机、其他可编程数据处理装置、或其他装置以特定方式运作，从而在计算机可读取介质中存储的指令可产生一产品，其包括实施在流程图及/或方块图的方块中所指定功能/动作的指令。计算机程序指令也可能加载到计算机、其他可编程数据处理设备、或其他装置，以使一系列操作步骤在计算机、其他可编程设备或其他装置上执行，以产生一计算机实现的过程，从而在计算机或其他可编程设备上执行的指令可提供用于实现所指定功能/动作的程序。虽然本发明已参照某些实施例描述，但所属领域的技术人士应明白，可在不脱
14、离本发明的范围的情况进行各种不同变更，且可由等价物所取代。此外，可进行许多修改以使特定情况或材料适于本发明的教示而不脱离其范围。因此，本发明旨在并非限制在公开的特定实施例，而是本发明包括落在后附权利要求的范围内的所有实施例。例如，如果多数通信发生在直接邻居间，那么直接交叉点可被配置为仅允许对应于第一邻居的通信端口之间的直接连接。此外，虽然本发明本质上假设双向端口(且因此，正方形交换器)以用于例示，但仍然可考虑应用到具有不平衡输入对输出端口的非正方形交换器。例如，至少一些交换器可包括N个输入端口与M个输出端口，其中N古M。这样的装置可适应于通过直接交叉点来路由数据包，所述直接交叉点被配置为根据计
15、算机互连网络的连接需要，允许在N个输入端口的每一个仅与输出端口的子集m 权利要求1.一种适于连接计算机互连网络(100)的部分的交换装置(Si，p，具有N个输入端口(Ia-Ih)与M个输出端口(Oa-Oh),其中M优选地等于N，该装置适于经由直接交叉点(CPX,y)路由数据包，根据该计算机互连网络的连接需要，所述直接交叉点被配置为允许在所述N个输入端口中的每一个仅与输出端口的子集m 全文摘要本发明涉及适于连接一计算机互连网络的部分的交换装置(Si，j)，该交换装置具有N个输入端口(Ia-Ih)与N个输出端口(Oa-Oh)，该装置适于经由直接交叉点(CPx，y)路由数据包，所述直接交叉点被配置为根据该计算机互连网络的连接需要，允许在N个输入端口中的每一个仅与输出端口的子集mN之间的直接连接。优选地，该交换装置还包括额外电路(L)与额外交叉点(APx，L,APL，y)，其被配置为使得该交换装置的至少一些输入端口可通过该额外电路间接连接至该交换装置的至少一些输出端口。本发明还涉及互连网络和用于路由数据的方法。
