用于提供胖树拓扑中的交换机之间的无死锁路由的系统和方法

摘要

一种系统和方法可以支持在中间件机器环境中的多个交换机之间路由数据包，从而通过在中间件机器环境中启用IP over Infiniband(IPoIB)通信来支持基于互联网协议(IP)的管理业务。所述多个交换机可以使用路由算法来对中间件机器环境中的交换机间业务执行路由。然后，可以选择中间件环境中的交换机作为用于不能使用路由算法到达其目的地的交换机间业务的集线器交换机。此外，当经由集线器交换机在源交换机与目的地交换机之间存在路径时，可以更新与集线器交换机相关联的路由表。

说明书

版权声明

本专利文档的公开内容的一部分包含受版权保护的资料。版权所 有人不反对任何人如该专利文档或专利公开内容在专利商标局的专利 文件或记录中所登载的那样对它进行复制再现，但是保留所有其他版 权权利。

技术领域

本发明总体上涉及计算机系统，更特别地，涉及支持中间件机器 环境中的交换机对交换机通信。

背景技术

胖树拓扑用于如今的高性能计算(HPC)集群，并且用于基于 InfiniBand(IB)技术的集群。对于胖树，与大多数其他技术一样， 路由算法对于网络资源的高效率使用是有益的。然而，当涉及交换机 对交换机通信时，现有的路由算法具有限制。没有一种现有的路由算 法支持对于高效率系统管理有益的无死锁、全连接的交换机对交换机 通信。这些大致是本发明的实施例意图解决的领域。

发明内容

本文中描述可以支持在中间件机器环境下的多个交换机之间路由 数据包的系统和方法。中间件机器环境可以通过在中间件机器环境下 启用IP over Infiniband(IPoIB)通信来支持基于互联网协议(IP) 的管理业务。所述多个交换机可以使用路由算法来对中间件机器环境 下的交换机间业务执行路由。然后，可以选择中间件机器环境下的交 换机作为用于使用路由算法不能到达目的地的交换机间业务的集线器 交换机。此外，当经由集线器交换机在源交换机与目的地交换机之间 存在路径时，可以更新与集线器交换机相关联的路由表。

在本发明的示例性实施例中，提供一种用于支持中间件机器环境 下的交换机间业务路由的系统。该系统可以包括多个交换机，其中至 少一个可以包括路由单元、选择单元和更新单元。路由单元可以使用 第一路由算法来对中间件机器环境下的交换机间业务执行路由；选择 单元可以选择中间件机器环境下的交换机作为用于使用第一路由算法 不能到达目的地的交换机间业务的集线器交换机；当经由集线器交换 机在源交换机与目的地交换机之间存在路径时，更新单元可以用于更 新与集线器交换机相关联的路由表。

在实施例中，所述多个交换机可以形成胖树拓扑。选择单元可以 选择胖树拓扑中的叶交换机作为集线器交换机，并且该叶交换机可以 到达胖树拓扑中的多个交换机目的地。在胖树拓扑中，第一路由算法 可以使用向上/向下拐弯(turn)模型来路由交换机间业务。当向上/ 向下拐弯模型失败时，交换机间业务向下/向上拐弯，并且所有向下/ 向上拐弯都被局域化到其中集线器交换机作为子树根节点的单个无死 锁子树，以便防止胖树拓扑中的死锁。

在另一实施例中，所述多个交换机中的所述至少一个还可以包括 迭代单元，其迭代经过胖树拓扑中的多个叶交换机，以便找到可以到 达胖树拓扑中的多个交换机目的地的一个或多个叶交换机。在例子中， 所述多个交换机中的所述至少一个还可以包括检查单元。检查单元可 以检查集线器交换机是否具有兄弟交换机，并且当至目的地交换机的 路径不存在时，检查与所述兄弟相关联的路由表是否包含所述路径。 在例子中，所述多个交换机中的所述至少一个还可以包括路径设置单 元，其用于当所述兄弟交换机存在并且与所述兄弟交换机相关联的路 由表包含到目的地交换机的路径时，在源交换机和子树根交换机上设 置通过所述兄弟交换机到目的地交换机的路径。在另一个例子中，所 述多个交换机中的所述至少一个还可以包括端口设置单元，其用于将 用于目的地交换机的输出端口设置为与用于集线器交换机的输出端口 相同。

附图说明

图1示出当在中间件机器环境下发生死锁时的示例性场景的例 示。

图2示出根据本发明的实施例的提供单核胖树拓扑中的交换机之 间的无死锁路由的例示。

图3示出根据本发明的实施例的提供多核胖树拓扑中的交换机之 间的无死锁路由的例示。

图4例示根据本发明的实施例的用于提供胖树拓扑中的交换机之 间的无死锁路由的示例性流程图。

图5例示根据本发明的交换机的示例性实施例。

具体实施方式

本文中描述可以支持在中间件机器环境下的多个开关之间路由数 据包的系统和方法。中间件机器环境可以通过在中间件机器环境下启 用IP over Infiniband(IPoIB)通信来支持基于互联网协议(IP)的 管理业务。

InfiniBand(IB)网络和子网管理

根据本发明的实施例，IB网络可以被称为子网，其中子网包括使 用交换机和点对点链路互连的一组主机。IB交织结构(fabric)可以 构成一个或多个子网，其中每个子网可以使用路由器互连。使用本地 标识符(LID)来寻址子网内的主机和交换机，并且单个子网限于49151 个LID。

IB子网可以具有至少一个子集管理器(SM)，其负责初始化和 启动网络，包括驻留在子网中的交换机、路由器和主机信道适配器 (HCA)上的所有IB端口的配置。在初始化时，SM从发现状态开始， 在发现状态下，SM对网络进行扫描以发现所有交换机和主机。在发 现状态期间，SM可以发现其他SM，并且可以就谁应是主控SM进行 商议。当发现状态完成时，SM进入主控状态。在主控状态下，SM进 行LID分配、交换机配置、路由表计算和部署以及端口配置。主控状 态一完成，子网就启动并且准备好供使用，并且在子网已经被配置之 后，SM负责监视网络变化。

另外，SM可以负责计算保持所有的源和目的地对之间的全连接、 无死锁和适当负荷均衡的路由表。可以在网络初始化时计算路由表， 并且每当拓扑改变时可以重复该处理以便更新路由表并且确保最佳性 能。

在正常操作期间，SM执行网络的周期性过光扫描(light sweep)， 以检查拓扑改变事件，诸如当链路发生故障时、当装置被添加时、或 者当链路被移除时。如果在过光扫描期间发现改变事件，或者如果SM 接收到通知网络改变的消息(陷阱)，则SM可以根据所发现的改变 来重新配置网络。该重新配置也可以包括在初始化期间使用的步骤。

IB是无损联网技术，其中可以对每一虚拟通道(VL)执行流控 制(flow-control)。VL是同一物理链路上具有独立的缓冲、流控制 和拥塞管理资源的逻辑信道。VL的概念使得可以在物理拓扑上构建 虚拟网络。这些虚拟网络或层可以用于各种目的，诸如高效率路由、 死锁规避、容错性和服务差异化。

胖树路由

根据本发明的实施例，胖树拓扑是分层网络拓扑，例如，均衡的 胖树可以在每一层都具有相等的链路容量。此外，可以通过构建具有 多个根的树(例如可以使用XGFT表示法描述的m端口n树定义或 k-ary n树定义)来实现胖树拓扑。

胖树路由算法可以利用可用网络资源。胖树路由算法可以包括两 个阶段：从源转发数据包的向上阶段、以及当朝向目的地转发数据包 时的向下阶段。这两个阶段之间的过渡发生在最近公共祖先处，最近 公共祖先是可以通过其向下端口到达源和目的地两者的交换机。这样 的路由实现确保无死锁，并且该实现还确保朝向同一目的地的每一个 路径会聚在同一根(顶部)节点处，使得朝向该目的地的所有数据包 在向下方向上遵循单个专用路径。通过具有用于每个目的地的专用向 下路径，有效地去除了向下阶段中的争用(移至向上阶段)，使得用 于不同目的地的数据包在其路径上仅争用一半交换机中的输出端口。 另外，超额预订的胖树中的向下路径不是专用的，可以由几个目的地 共享。

交换机对交换机通信

除了终端节点之间的通信之外，胖树拓扑允许交换机对交换机通 信。当交换机对交换机通信发起很少的业务时，可以忽略交换机对交 换机通信，或者换句话讲，可以认为IB交换机是从路由算法的观点来 讲可以安全地忽略的透明装置。

另一方面，交换机对交换机通信业务可能不总是可以忽略的。在 这些情况下，可以使用前一章节中描述的胖树路由来带有局限性地路 由交换机对交换机通信业务，因为可能需要找到最近公共祖先以发现 任意两个交换机之间的路径，使得可以通过第一可用端口来转发业务。 而且，胖树路由方案不提供不具有最近公共祖先的那些交换机之间的 连接，即，前一章节中描述的胖树路由方案可能不能提供胖树拓扑中 的全连接。

由于各种原因，包括终端节点和交换机两者的胖树拓扑中的全连 接可以是有益的。例如，IB诊断工具依赖于LID路由，并且需要全 连接来进行基本的交织结构管理和监视。此外，诸如用于基准检查 (benchmarking)的perftest之类的高级工具可以利用IPoIB，其依 赖于底层LID路由并且需要全连接。IPoIB是使得可以通过IB网络 运行TCP/IP业务的封装方法。此外，IPoIB也是非InfiniBand知悉 的管理以及像SNMP或SSH之类的监视协议和应用所需要的。因此， 交织结构中的所有交换机之间的全连接可以是有益的，因为交换机能 够产生任意业务，可以像任何其他终端节点那样被访问，并且通常包 含嵌入式SM。

因为诸如缓冲区或信道的网络资源被共享，所以在胖树拓扑中可 能发生死锁。

图1示出当在中间件机器环境下发生死锁时的示例性场景的例 示。如图1所示，中间件机器环境下的胖树拓扑100允许具有两个交 换机对交换机通信对(交换机0对交换机3、以及交换机3对交换机6) 和两个节点对节点通信对(节点B对节点D、以及节点D对节点A) 的混合通信模式。这里，从交换机0到交换机3的业务经由交换机4、 8和5引导，从交换机3到交换机6的业务经由交换机7和9引导。 此外，从节点B到节点D的业务经由交换机8、5、3、7和9引导， 从节点D到节点A的业务经由交换机9、6、0、4和8引导。

如图1中的虚线所示，当以上混合通信模式存在于胖树拓扑100 中时，创建了循环信用依赖(cycle credit dependency)或信用回路101。 此外，当创建循环信用依赖时，死锁可能发生。这不意味着，每当存 在循环信用依赖时，就将总是存在死锁。换句话讲，循环信用依赖的 创建使得死锁发生成为可能。例如，当使用诸如minhop之类的路由 算法时，在具有节点对节点和交换机对交换机业务的3级胖树中，可 能发生死锁。这是因为minhop不能以无死锁的方式求解5个节点的 环或更大的环，并且3级胖树可能包含6节点的环。因此，需要一种 当存在所有交换机之间的交换机对交换机通信时可以提供胖树拓扑中 的无死锁路由的算法。

可以通过使用分割可用物理资源的VL来避免死锁。然而，使用 VL来实现胖树中的死锁避免可能是无效率的，因为附加VL可以用于 其他目的，比如，服务质量(QoS)。

例如，用于IB的LASH算法可以支持全连接和无死锁。LASH 算法使用VL来打破信用回路101，并且提供交织结构中的所有节点 之间的全连接。LASH在分配路径时不利用胖树的性质，因此使得网 络性能可能比普通胖树路由更糟，另外，LASH的路由时间长。DFSSSP 是可以用于支持胖树中的所有交换机对交换机通信的另一路由协议。 然而，DFSSSP不打破非HCA节点之间的信用回路，这意味着交换机 对交换机通信可能不是无死锁的。

因此，当在互连网络中发生死锁时，死锁可以阻止网络的部分或 全部通信。因此，从互连网络的全系统角度来讲，胖树拓扑中所支持 的全连接优选是无死锁的。

单核胖树拓扑中的无死锁路由

根据本发明的实施例，可以支持中间件机器环境下的节点之间的 全连接，并且可以仅使用单个VL来实现整个交织结构的无死锁。

图2示出根据本发明的实施例的提供单核胖树拓扑中的交换机之 间的无死锁路由的例示。如图2所示，中间件机器环境下的单核胖树 拓扑20可以包括多个交换机。此外，中间件机器环境可以包括连接到 胖树拓扑200中的叶交换机202的多个终端节点220，诸如服务器节 点。

向上/向下拐弯模型可以用于提供中间件机器环境下的胖树路由。 例如，交换机A1和A2可以通过借助于X1或X2上升而具有连接性。 另一方面，对于不具有最近公共祖先的交换机(例如，A1和B1)之 间的通信，向上/向下拐弯模型可能是无用的。

根据本发明的实施例，可以利用替代方法来实现不能使用向上/ 向下拐弯模型建立通信的交换机之间的连接。如图2所示，可以在胖 树拓扑200中创建倒置树或子树210(在阴影区域中示出)。子树210 可以具有子树根节点Sn或集线器交换机210，其是胖树拓扑200中的 叶交换机。可以通过胖树拓扑200中的集线器交换机201来建立全连 接。

在子树201内，交换机X1和Y1可以通过子树根Sn201来通信， X1和X2可以通过交换机A1来通信。此外，子树210外部的交换机 可以通过子树210与胖树拓扑200中的其他交换机通信，这导致非最 短(或次优)路径的使用。所述交织结构中不能使用向上/向下拐弯模 型到达另一个交换机的交换机可以首先将数据包发送到子树210。然 后，可以在子树210中传递这些数据包，直到它们到达具有到目的地 交换机的路径的交换机为止。换句话讲，数据包在集线器交换机201 中做出U形拐弯，即，下到上拐弯，接着是朝向目的地的上到下的路 径。中间件机器环境下的子树210可以将所述交织结构中的所有向下/ 向上拐弯都局部化到单个无死锁树。

例如，当接收到在中间件机器环境下将一个或多个数据包从第一 交换机(例如，A1)路由到第二交换机(例如，B2)的请求时，所述 系统可以首先确定与子树根交换机或集线器交换机201相关联的路由 表是否包含到第二交换机B2的路径。如图2中的虚线所示，集线器 交换器201可以经由通过B1、Y1或Y2的路径连接到第二交换机B2。 然后，可以将到第二交换机B2的路径插入到与第一交换机A1相关联 的路由表。另外，在与A1相关联的路由表中，可以将用于交换机A2 的输出端口设置为与用于集线器交换机210的输出端口相同。

倒置子树210的根可以是叶交换机中的任何一个。此外，胖树拓 扑200中的所有交换机可以共同选择用于通信的叶交换机，以实现中 间件机器环境下的无死锁全连接。

根据本发明的实施例，可以通过要求所有的U形拐弯仅发生在子 树210内并且任何上到下拐弯都将引导业务离开子树210来在胖树拓 扑200中实现无死锁。另外，离开子树210的业务可能不能循环回到 子树210中，因为子树210外不允许U形拐弯。

因此，在单核胖树200中，可以总是存在从源交换机连接到集线 器交换机210、以及从集线器交换机201连接到每一个目的地交换机 的路径。此外，用于通过拓扑中的叶交换机实现连接的通信方案不改 变可以使用胖树路由到达彼此的交换机之间的向上到向下路径。

附上了附录A，其提供关于支持中间件机器环境下的交换机之间 的路由、以及整个本公开中所描述的平台的各个方面的更多信息。附 录A中的信息是为了例示的目的而提供的，不应被解释为限制本发明 的所有实施例。

多核胖树拓扑中的无死锁路由

根据本发明的实施例，在复杂的多核胖树或不规则胖树中的两个 交换机之间不总是存在连接。在这些情况下可以利用尽力型 (best-effort)方法来路由交换机对交换机通信。

图3示出根据本发明的实施例的提供多核胖树拓扑中的交换机之 间的无死锁路由的例示。如图3所示，中间件机器环境下的多核胖树 拓扑300可以包括多个交换机。此外，中间件机器环境可以包括连接 到胖树拓扑300中的叶交换机的多个终端节点320，诸如服务器节点。

类似地，可以在胖树拓扑300中创建倒置树或子树310(在阴影 区域中示出)。子树310可以具有子树根节点Sn或集线器交换机310， 其是胖树拓扑300中的叶交换机。与图2不同，子树根交换机或集线 器交换机301可能不具有到所有目的地的路径。

另外，兄弟交换机302可以存在于中间件机器环境中，并且可以 通过水平链路330与子树根交换机Sn或集线器交换机301连接。

在一个例子中，第一交换机(例如，B2)可以请求在中间件机器 环境下将一个或多个数据包路由到第二交换机(例如，B3)。子树根 交换机301不具有连接到B3的路径，因为B3位于仅经由水平链路与 其他节点连接的单独胖树中。

所述系统可以首先检查子树根交换机301是否具有其路由表包含 到B3的路径的兄弟交换机302。然后，所述系统可以在第一交换机 B2和子树根交换机301上设置通过所述兄弟交换机302到第二交换机 B3的路径。结果，所述系统可以被配置为例如经由Y1或Y2、B1、 子树根节点301及其兄弟节点302来将从交换机B2发起的数据包路 由到交换机B3(用虚线示出)。

SFTREE算法

根据本发明的实施例，可以使用路由算法(即，SFTREE算法) 来实现交换机之间的无死锁全连接。SFTREE算法可以包括两个步骤： 第一步，发现子树的根Sn，其可以是叶交换机之一；以及第二步，执 行交换机对交换机路由。

下面的算法1包括用于找到子树的根并且建立子树的伪码。

算法1遍历拓扑中的所有叶交换机，并且对于每个叶交换机，检 查在其路由表中是否将任何交换机目的地地址标记为不可到达。如果 路由表中的所有交换机目的地都被标记为可到达，则将第一个遇到的 叶交换机选择为子树根交换机。此外，在胖树中可以存在和具有全连 接的叶交换机一样多的可能的子树。这些叶交换机中仅一个可以被选 择为子树根，并且仅可以有一个根在这个特定叶交换机中的子树。

下面的算法2包括用于执行胖树拓扑中的交换机对交换机路由的 伪码。

当交换机对交换机路由函数被调用时，如算法2中的行1所示， 第一步是确定子树根(sw_root)的路由表是否包含到目的地交换机(sw_dst) 的路径。如果包含，则将到目的地交换机的路径插入到源交换机(sw_src) 的路由表中，并且用于目的地交换机的输出端口与用于到子树根的路 径的输出端口相同(行2-6)。因为对于每一个交换机调用交换机对 交换机路由函数，所以最后，到每个不可到达的目的地交换机的所有 路径都将会聚到子树。换句话讲，对于所有不可到达的目的地交换机， 所选子树根是新目标。向下/向上拐弯将在位于子树中的第一可能交换 机处发生，该交换机可以是具有到源交换机和目的地交换机两者的向 上路径的交换机。

算法2的第二部分(行7-24)解决复杂的多核或不规则胖树的情 况，其中，利用尽力型方法，并且子树根不具有到所有目的地的路径。 另一方面，在单核胖树中可以跳过算法2的这个第二部分，因为可以 总是存在从源交换机到子树根的路径，并且子树根可以具有到每一个 目的地交换机的路径。

算法2检查子树根是否具有它们如图3中所示的那样通过水平链 路连接到的直接邻居(行7)。接着，算法2检查该邻居(也称为兄 弟)是否具有到目的地交换机的路径(行8)。如果兄弟存在并且该 兄弟具有到目的地交换机的路径，则在子树根和始发源交换机上都设 置通过兄弟交换机到目的地交换机的路径(行9-19)。换句话讲，用 于不可到达的目的地交换机的目标仍可以是子树根，并且子树根可以 经由其兄弟交换机将数据包转发给目的地交换机。

如果前两个步骤都没有从函数返回真值，则SFTREE算法可能未 能找到两个交换机之间的路径。例如，对于由于多个链路失败或节点 之间的非常不规则的连接而不推荐运行胖树路由的拓扑，这可能发生。 这样的拓扑的例子可以是以非对称方式彼此连接(例如，从较大的树 的几个中间级的交换机到较小的树上的根)的不同大小的两个胖树。 通过使用OpenSM中的各种命令行参数，可以迫使在这些拓扑上运行 胖树路由。SFTREE算法可以给予不仅就性能而言、而且还就连接而 言次优的路由。

根据本发明的实施例，OpenSM使得每一个路径可以用到目的地 的跳数标记。胖树路由算法可以使用树中的交换机等级来计算跳数。 此外，可以使用主路由函数中的简单计数器来进行计数。当交换机对 交换机路由完全独立于通过胖树算法进行的主路由时，这些计数方案 对于可能的z字形路径(即，不遵循最短跳跃路径的路径)可能是不 可靠的。

在交换机对交换机路由期间可以使用用于跳跃计算的递推函数， 例如get_path_length(行17)。该函数可以在构成路径的一系列交换 机上迭代，并且当该函数到达具有朝向目的地的适当跳数的节点时， 该函数可以将该跳数写入到路径上的交换机的路由表中。

另外，可以以子网管理器节点(子网管理器运行于其上的终端节 点)不连接到被标记为子树根的交换机这样的方式来选择子树根。因 此，可以将交换机对交换机业务拉离子网管理器，因此不在关键位置 造成瓶颈。

图4例示根据本发明的实施例的用于提供胖树拓扑中的交换机之 间的无死锁路由的示例性流程图。如图4中所示，在步骤401，中间 件机器环境可以使用路由算法对中间件机器环境下的交换机间业务执 行路由。然后，在步骤402，中间件机器环境可以选择中间件机器环 境下的交换机作为集线器交换机以用于不能使用路由算法到达目的地 的交换机间业务。此外，在步骤403，当经由集线器交换机在源交换 机与目的地交换机之间存在路径时，中间件机器环境可以更新与集线 器交换机相关联的路由表。

图5例示根据本发明的交换机的示例性实施例，该交换机可以包 括在上述支持中间件机器环境下的交换机间业务路由并且包括多个交 换机的系统中的任何系统中。参照图5，示例性交换机10可以包括根 据如上所述的本发明的原理配置的路由单元11、选择单元13和更新 单元14。可以用硬件、软件或硬件和软件的组合来实现交换机10的 功能单元(包括但不限于单元11、13和14)以实现本发明的原理。 本领域的技术人员理解，图5中所示的功能块均可以组合或分离为实 现如上所述的本发明的原理的子单元。因此，本文中的描述可以支持 本文中描述的功能块的任何可能的组合或分离或进一步定义。

路由单元11可以使用如上所述的第一路由算法来对中间件机器 环境下的交换机间业务执行路由。选择单元13可以选择中间件机器环 境下的交换机作为用于不能使用第一路由算法到达目的地的交换机间 业务的集线器交换机。当经由集线器交换机在源交换机与目的地交换 机之间存在路径时，更新单元14可以更新与集线器交换机相关联的路 由表。

在示例性实施例中，所述系统的所述多个交换机形成胖树拓扑。 选择单元13可以选择胖树拓扑中的叶交换机作为集线器交换机，并且 该叶交换机可以到达胖树拓扑中的多个交换机目的地。第一路由算法 可以使用上/下拐弯模型来在胖树拓扑中路由交换机间业务。当上/下 拐弯模型失败时，交换机间业务做出下/上拐弯，并且所有下/上拐弯 都被局部化到其中集线器交换机作为子树根节点的单个无死锁子树， 以便防止胖树拓扑中的死锁。

在示例性实施例中，交换机10可以可选地包括迭代单元12，其 用于迭代经过胖树拓扑中的多个叶交换机，以便找到可以到达胖树拓 扑中的多个交换机目的地的一个或多个叶交换机。因此，选择单元13 可以从所述一个或多个叶交换机选择集线器交换机。

在示例性实施例中，交换机10还可以包括检查单元15。检查单 元15可以检查集线器交换机是否具有兄弟交换机，并且当到目的地交 换机的路径不存在时，检查与兄弟相关联的路由表是否包含该路径。

在示例性实施例中，交换机10还可以包括路径设置单元16。当 兄弟交换机存在并且与兄弟交换机相关联的路由表包含到目的地交换 机的路径时，路径设置单元16可以在源交换机和目的地交换机上设置 通过兄弟交换机到目的地交换机的路径。

在示例性实施例中，交换机10还可以包括端口设置单元17，其 用于将用于目的地交换机的输出端口设置为与用于集线器交换机的输 出端口相同。

可以使用包括根据本公开的教导编程的一个或多个处理器、存储 器和/或计算机可读存储介质的一个或多个常规的通用或专用数字计 算机、计算装置、机器或微处理器来方便地实现本发明。如对于软件 领域的技术人员将显而易见的，熟练的程序员可以基于本公开的教导 容易地准备适当的软件编码。

在一些实施例中，本发明包括一种计算机程序产品，其是其上/ 其中存储可以用于将计算机编程为执行本发明的任何处理的指令的存 储介质或计算机可读介质。存储介质可以包括，但不限于，任何类型 的盘(包括软盘、光学盘、DVD、CD-ROM、微驱动器和磁光盘)、 ROM、EPROM、EEPROM、DRAM、VRAM、闪存装置、磁卡或光 学卡、纳米系统(包括分子记忆IC)、或适合于存储指令和/或数据 的任何类型的介质或装置。

已经为了例示和描述的目的提供了前面对本发明的描述。并非意 图是穷举的或者使本发明限于所公开的精确形式。许多修改和变型对 于本领域的从业人员将是显而易见的。变型可以包括所公开的特征和/ 或元件的任何组合。为了最好地说明本发明的原理及其实际应用，选 择并描述了实施例，从而使得本领域的技术人员能够针对各个实施例、 在适合于所设想的特定用途的各种修改的情况下理解本发明。意图是 本发明的范围由权利要求书及其等同形式限定。

附录A

下面是说明SFTREE算法无死锁的证明。该证明还包含相关术语 的示例性定义。

定义1.交换机s_n意指等级为n的交换机。根交换机具有等级n＝0。

定义2.向下信道意指s_n-1与s_n之间的链路，其中业务从s_n-1流到 s_n。向上信道意指s_n与s_n-1之间的链路，其中业务从s_n流到s_n-1。

定义3.路径被定义为由信道连接的一系列交换机。它以源交换机 开始，以目的地交换机结束。

定义4.U形拐弯是向下信道之后为向上信道的拐弯。

定义5.当占有信道c_i的数据包请求使用信道c_j时，信道c_i与c_j之间的信道依赖发生。

定义6.信道依赖曲线图G＝(V,E)是有向图，其中顶点V是网络 N的信道，边缘E是使得存在从c_i与c_j的(信道)依赖的信道对(c_i, c_j)。

定义7.子树意指胖树内的会聚到单个叶交换机s的逻辑倒置树结 构，所述单个叶交换机s是该子树的单个根。子树从其根扩展，并且 其叶是胖树中的所有顶级交换机。任何向上到向下的拐弯都将离开子 树结构。

以下定理声明路由函数的无死锁的充分条件。

定理1.当且仅当在信道依赖曲线图G中不存在循环时，用于网 络N的确定性路由函数R才是无死锁的。

接下来，可以提供SFTREE算法的无死锁定理所遵循的引理。

引理8.在胖树内存在至少一个子树，该子树仅使用在该子树内的 U形拐弯来允许交换机对交换机的全连接。

证明.在胖树中，从任何叶，可以使用向上/向下路径或水平兄弟路 径到达所述交织结构中的任何其他节点(包括所有交换机)。这是因为 每一个终端节点可以与每一个其他终端节点通信，并且因为终端节点 直接连接到叶交换机，所以得出结论，叶交换机能够到达拓扑中的任 何其他节点。因此，如果它不包含链路故障，则任何叶交换机可以充 当子树的根。

引理9.在不引入死锁的情况下，在单个子树内可以存在无限个U 形拐弯。

证明.子树是逻辑树结构，并且在它内可以发生两种类型的拐弯： U形拐弯(即，向下拐到向上的拐弯)、以及普通的向上拐到向下的 拐弯。U形拐弯不能发生在子树(以及胖树)中的顶部交换机处，因 为这些交换机不具有输出向上端口。根据定义7，任何向上拐到向下 的拐弯都将离开子树。

因为子树是不具有任何循环的连接图，所以它本身是无死锁的。 任何死锁必须涉及子树外部的U形拐弯，因为U形拐弯之后为离开子 树的向上拐到向下的拐弯。当做出起源于子树中的向上/向下拐弯并且 仅跟随到达目的地的向下信道时，经过该拐弯的所有业务都将离开子 树。这样的依赖性可能永不再次进入子树，并且可能永不到达任何其 他U形拐弯，所以，不能形成任何循环。

定理2.使用子树方法的SFTREE算法是无死锁的。

证明.按照引理8和引理9，仅当在子树外部存在U形拐弯时， 胖树中的死锁才可能发生。由于SFTREE算法的其中所有U形拐弯都 在子树内发生的设计，这样的情况不能发生。离开子树的业务将不循 环回到该子树，因为一旦它离开子树，它就仅通过向下信道被转发给 目的地，并且它被消耗，因此，在拓扑中将不会发生循环信用依赖。