Patent ID: 8730965

Claim:
A method of routing data packets in an interconnection network, the method comprising: receiving a data packet on an input port of a routing device in the interconnection network; inspecting a destination field of a packet header of the data packet to determine a destination host; using the destination field to index into memory; generating a first field and a second field using the destination field indexed into the memory, the first field being a route type identifying a type of route for the data packet and the second field being an output port grouping, the output port grouping identifying a plurality of output port candidates; arbitrating among the plurality of output port candidates using the route type and heuristic information to select one of the plurality of output port candidates; and routing the data packet using the selected output port candidate; wherein the output port grouping includes a first grouping representing a primary set of output port candidates from the plurality of output port candidates, and a second grouping representing a secondary set of output port candidates from the plurality of output port candidates; wherein the route type is one of a random route type, an adaptive route type and a deterministic route type; and wherein if the route type is the random route type, arbitrating among the plurality of output port candidates including pseudo-randomly choosing from among the primary or secondary sets of output port candidates.