Method for Topology Independent Path Determination in Infiniband Subnets

Disclosed is a method that uses algorithms and data structures for computing the optimal path between any two end-points, regardless of the topology of the Subnet. Benefits include a simplified implementation of load balancing or other sophisticated route selection algorithms.

Background

An Infiniband Architecture Network, known as a Subnet, relies on a special member of the subnet to act as a Subnet Manager (SM). On behalf of the subnet, the SM assigns Link Identifier (LID) values and configures the Switch Forwarding Table (SFT) for every switch on the Subnet.

A LID acts as the link address of a given port on the Subnet, akin to an Ethernet MAC address.  Infiniband packets move through the subnet from a source LID to a destination LID. Furthermore, the Infiniband Architecture supports multiple paths through the Subnet for a given pair of ports. A port occupies a range of LID values, with one LID per redundant path. Multiple paths allow for some degree of fault tolerance. If one path becomes inoperable, traffic may be diverted to an alternate path.

An SFT specifies the switch port used to route a packet with a given destination LID. Every Infiniband switch contains one SFT. As a packet moves through a Subnet, each switch in turn uses its own SFT to lookup the appropriate output port for the packet. For the purposes of the disclosed method, each intervening switch in the path between two end-points is considered a hop. Since each switch in a path exacts a performance penalty, paths with fewer hops are generally preferable to those with more hops.

The Subnet Manager has responsibility for programming the SFT in each switch with a route for every LID value in the subnet. Efficiently determining optimal routes through a Subnet of arbitrary topology is not trivial. This route determination problem does not arise in traditional networks such as Ethernet, which uses a “single spanning tree” concept to eliminate redundant routes. In contrast, Infiniband Subnets can be designed with up to 128 different routes between a given pair of ports (see Figure 1).

General Description

The disclosed method provides the algorithms and data structures for computing the optimal path between any two ports, regardless of the topology of the Subnet. The disclosed method is embodied by the following provisions:

1. Subnet Object
2. LID Matrix Object
3. LID Matrix Algorithm

The output of the disclosed method is the optimized SFT for each switch in the Subnet.

Provision 1:  Subnet Object

The disclosed method presupposes a data structure known as a Subnet Object. The Subnet Object models the physical composition and topology of the Subnet.  By following internal linkages in the Subnet Object, the disclosed method may determine the composition and physical interconnectedness of the subnet The construction and precise format of the Subnet Object are outside the scope of this disclosure. The Infiniband standar...