Next Hop Computation Functions for Equal Cost Multi-Path Packet Switching Networks

A system for forwarding packets on paths through a packet switching network, each packet having a destination address and a flow identifier, the packet switching network having a plurality of substantially equal cost paths between at least one pair of nodes, each substantially equal cost path having a corresponding candidate output port at each node on the substantially equal cost path, the system comprising:

• at least one processor;
• at least one network interface operable to couple the processor to the packet switching network;
• and
• at least one memory operable to store instructions for execution by the at least one processor, the instructions being executable for packets having a destination address having multiple equal costs paths diverging at a node:
• to select candidate output ports at the node by mapping the flow identifier of each packet to one of the candidate output ports for the destination address of the packet, the mapping comprising a first function that is essentially unique to the node such that, for all possible flow identifiers, the function produces a value that is different from values produced by corresponding functions at most or all other network nodes for the same flow identifier, and
• where an output set of the function is larger than the number of candidate output ports, the mapping further comprises a compression function which maps the output set of the first function into a set limited to the candidate output ports.