Path resolution for hierarchical load distribution

1. A method comprising:

providing, for a first layer of an overly network, a first stage of path resolution for forwarding a packet toward a destination; and

providing a second stage of path resolution following the first stage; and

receiving in the second stage an intermediate path resolution output from the first stage, the first stage and second stage configured to sequentially determine a next hop for the packet.

2. The method of claim 1 , where:

providing the first stage comprises providing a first stage of equal cost multi-path resolution.

3. The method of claim 2 , where:

providing the second stage comprises providing a second stage of equal cost multi-path resolution.

4. The method of claim 1 , where the second stage executes path resolution for a second layer of the overlay network.

5. The method of claim 1 , where providing a first stage comprises:

providing an equal cost multi-path (ECMP) group table and an ECMP member table configured to generate the output.

6. The method of claim 5 , where receiving comprises:

receiving an ECMP group pointer in the output.

7. The method of claim 6 , further comprising:

executing path resolution in the second stage by choosing among members of an ECMP group referenced by the ECMP group pointer.

8. The method of claim 5 , further comprising:

providing a load balancing mode selection signal operable to select among multiple options for generating an offset into the ECMP member table.

9. A network device comprising:

a processor; and

a memory in communication with the processor, the memory comprising path resolution instructions that, when executed by the processor, cause the processor to:

determine to execute a multiple stage next hop resolution for a received packet;

initiate the multiple stage next hop resolution by determining, in a first stage, a first group of members;

output a selected member from among the first group of members to a second stage, where the selected member comprises a reference to a second group of members in the second stage; and

determine a routing output from among the second group of members.

10. The network device of claim 9 , where:

the routing output comprises an identifier of a next hop.

11. The network device of claim 9 , where:

the routing output comprises a reference to a third group of members in a third stage subsequent to second stage.

12. The network device of claim 9 , where:

the first group of members corresponds to a first network layer.

13. The network device of claim 12 , where:

the second group of members corresponds to a second network layer running underneath the first network layer.

14. The network device of claim 9 , where the instructions, when executed, further cause the processor to:

determine the selected member from a member table entry in a member table.

15. The network device of claim 14 , where the member table entry comprises:

a protection group pointer to information that specifies whether the selected member is down.

16. The network device of claim 14 , where the member table entry comprises:

a fallback group identifier of a fallback group from which to continue next hop resolution in the second stage.

17. The network device of claim 14 , where the second group of members comprises multiple entries for a specific next hop according to a relative weighting of the specific next hop.

18. A network device comprising:

first path resolution stage circuitry comprising:

a first stage equal cost multiple path (ECMP) group table identifying a first ECMP group; and

a first stage ECMP member table comprising:

a first member entry comprising a pointer to a different ECMP group table other than the first stage ECMP group table;

second path resolution stage circuitry configured to receive a path resolution output from the first path resolution stage, the second path resolution stage circuitry comprising:

a second stage equal cost multiple path (ECMP) group table identifying a second ECMP group; and

a second stage ECMP member table comprising:

multiple entries for a first next hop in the second ECMP group that implement a first weighting for the first next hop; and

multiple entries for a second next hop in the second ECMP group that implement a second weighting for the second next hop.

19. The network device of claim 18 , further comprising:

load balancing circuitry configured to determine how an offset into the second member table is determined from among multiple options; and

output selection signal circuitry configured to determine whether path resolution ends at the first stage or at the second stage.

20. The network device of claim 12 , where the first layer comprises a layer of an overlay network.