Path Resolution for Hierarchical Load Distribution

• US 20140293786A1
• Filed: 09/12/2013
• Published: 10/02/2014
• Est. Priority Date: 04/01/2013
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Agarwal, Puneet, Lin, Meg Pei, Leshem, Liav
• Granted Patent: US 9,270,601 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop

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.

Claims

1. A method comprising:

in a network device;

providing 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 a first stage comprises providing a first stage of equal cost multi-path resolution.

3. The method of claim 2, where:

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

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

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

6. 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.

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

receiving an ECMP group pointer in the output.

8. The method of claim 7, further comprising:

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

9. The method of claim 6, further comprising:

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

10. A network device comprising:

a processor; and

a memory in communication with the processor, the memory comprising path resolution instructions configured 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.

11. The network device of claim 10, where:

the routing output comprises an identifier of a next hop.

12. The network device of claim 10, where:

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

13. The network device of claim 10, where:

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

14. The network device of claim 13, where:

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

15. The network device of claim 10, where the instructions are configure to:

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

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

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

17. The network device of claim 15, 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.

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

19. A network device comprising:

a first path resolution stage 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 ECMP group table;

a second path resolution stage configured to receive a path resolution output from the first path resolution stage, the second path resolution stage 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.

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

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

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