Routing via multiple paths with efficient traffic distribution

A network element, comprising:

• multiple ports, which are configured to connect to a communication network;
• and
• hardware-implemented circuitry, which is configured to:
• assign multiple output ports corresponding to respective different paths via the communication network for routing packets to a given destination-address group;
• hold for the given destination-address group, respective state information for each of multiple sets of hash results, wherein the state information comprises at least an output port that routes packets to the given destination-address group and respective timeout information;
• receive via an input port a packet destined to the given destination-address group;
• calculate a given hash result for the packet and identify a given set of hash results in which the given hash result falls;
• select an output port from among the multiple output ports that were assigned to the given destination-address group, based on the state information corresponding to the identified given set of hash results;
• and
• forward the packet to the given destination-address group via the selected output port.