Path resolution for hierarchical load distribution

Abstract

Network devices perform multiple stage path resolution. The path resolution may be ECMP resolution. Any particular stage of the multiple stage path resolution may be skipped under certain conditions. Further, the network device facilitate redistribution of traffic when a next hop goes down in a fast, efficient manner, and without reassigning traffic that was going to other unaffected next hops, using multiple stage ECMP resolution.

What is claimed is:  
     
       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.