目前实用的IB路由算法Opensm中采用的算法.docVIP

目前实用的IB路由算法：Opensm中采用的算法 Infiniband使用oblivious destination-based distributed路由机制。每个交换芯片维持一个查找表（随机或者线性转发表），定义了哪个端口转发到哪个目的端结点。在初始构造路由表或者拓扑变化时，子网管理SM探索/发现拓扑，计算每个交换芯片的转发表，并将其上载到交换芯片。在目前的实现中OpenSM采用5种不同的路由算法MINHOP，UPDOWN，FTREE，DOR和LASH，另外还支持基于路由文件的定制路由转发机制。 MINHOP：找出所有端结点之间的最小路径，并平衡每个交换芯片本地的每条链路上的路由数量（在最小路径约束条件下进行平衡）。但是，这种方法通常会在交换芯片buffer之间形成环路相关性，进而可能导致网络死锁，在文献Deadlock-free message routing in multiprocessor interconnection networks中详细讨论了这种缓冲区相关的环路死锁。 UPDN：使用Up*/Down*路由算法，在文献Autonet: a high-speed, self-configuring local area network using point-to-point links中首次提出这种Up*/Down*路由算法。该算法的基础是MINHOP算法，同时限制网络中的可选路径数量达到避免circular buffer dependencies。在文献Effective strategy to compute forwarding tables for InfiniBand networks中详细讨论了这种方法。 FTREE实现了一种优化fat-tree网络的路由机制，算法实现方法来源于文献Optimized InfiniBand Fat-tree Routing for Shift All-To-All Communication Patterns。这种方法也会导致死锁问题，并且其网络结构被限定为fat-tree结构。 DOR（Dimension Order Routing）路由方法沿着k-ary n-cube网络的维度进行路由来确定最小路径，并且也会产生路由环路问题。算法来源于文献A large scale, homogeneous, fully distributed parallel machine。 LASH路由方法的基础是DOR算法，同时使用VL（Virtual Lanes）来打破多个通道间的环路相关。 对于每个算法的详细描述，我们参考opensm文档如下： 在Voltaire SM中实现的所有路由算法都保证从任何源端到目的LID的路径都尽可能短，SM会选择具有最小流量的路径。 MINHOP 使用 可用于所有网络拓扑，不能避免credit-loop-deadlock，但最快 基本思想 为每个host对计算最短路径 负载平衡器：通过均分流经每个端口的路径的数量，平衡每个交换机的输出端口上的负载重量。可随意剔除某些指定端口 优化 如果LMC0,在每个目的端口分组中：仅使用minhop端口，优先使用那些没有包含到目的GUID路由的那些端口。否则，使用那些到不同下一结点GUID的端口，否则像没有LMC那样的计算路由总数。 Voltaire交换机的实现，当子网内的一对结点间存在多条路径时，子网管理器SM会计算和辨别这些端结点间的多条极小化（最端）路径，从中选择一条路径并相应地对fabric进行处理（比如作状态统计，拥塞避免等负载平衡处理）。但是，为了更好地利用网络带宽，子网管理器SM会平衡这些路由选择，以便在网络中所有端结点间的所有可达路径上做到通信流量的尽可能均衡。 UPDN 使用 可用于所有网络拓扑，可避免credit-loop-deadlock，慢。会在root周围产生热点 基本思想 --在子网中指定/分配root，可自动检测或手工设定。如果不能获得root，则降级为MinHop --从root开始，构建有哪些信誉好的足球投注网站树 --对每对结点 ，找到其首先走的最短路径，“到根”而后“离开根”，如果有多条到根的路径端口，则沿边缘走，选择较低的GUID。 --MinHop方式的负载均衡。 --所有root的rank都是0，root之间没通信，通常，指SPINE上的多个交换芯片间无通信。 --这意味着，SM必须位于叶交换机上。 --GUID的替换会引起非确定性的路由。 优化 --避免热点的功能增强，学术界2004，而OpenSM中没有实现：在每个layer上选择一个层次，root之间的距离最大化。每个通信流的路由放在单个layer内。热点在网络中均匀分配。 基于生成树的无死锁路由算法的一个不足是对于具