Path resolution for hierarchical load distribution

• US 9,270,601 B2
• Filed: 09/12/2013
• Issued: 02/23/2016
• 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: Lin, Meg Pei, Agarwal, Puneet, Leshem, Liav
• Primary Examiner(s): Wilson, Robert
• Application Number:
  US14/025,114
• Publication Number:
  US 20140293786A1
• Time in Patent Office: 894 Days
• US Class Current: 1/1
• 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:

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.

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

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.