Equal-cost multi-path (ECMP) routing with resiliency and consistent ordering

A method of operating a network device coupled to one or more next hop devices, the method comprising:

• in response to a link between the network device and the one or more next hop devices being disconnected or established, updating a software forwarding table stored on the network device, the software forwarding table listing next hop devices currently connected to the network device for a given destination prefix;
• in response to updating the software forwarding table, determining whether the updated software forwarding table is at capacity;
• in response to determining that the updated software forwarding table is not at capacity, updating a hardware forwarding table corresponding to the given destination prefix in accordance with a first mode, wherein the hardware forwarding table lists a plurality of next hop devices to which the network device concurrently conveys, via a plurality of links, traffic flows based on the next hop devices listed in the software forwarding table, wherein the first mode takes into account a prior state of the hardware forwarding table to minimize disruption to existing traffic flows for the given destination prefix;
• and
• in response to determining that the updated software forwarding table is at capacity, updating the hardware forwarding table corresponding to the given destination prefix in accordance with a second mode, different than the first mode, that disregards the prior state of the hardware forwarding table to implement a consistent ordering of next hop devices listed in the hardware forwarding table.

A method of operating a network comprising:

• using a first network device to convey data packets to a first destination address corresponding to a given destination prefix;
• using a second network device, parallelly situated with the first network device, to convey data packets to a second destination address corresponding to the given destination prefix;
• subsequent to a link to the first network device being established or disconnected, updating a first hardware forwarding table on the first network device for the given destination prefix in accordance with first and second modes based on whether the first software forwarding table on the first network device for the given destination prefix is at capacity, wherein the first hardware forwarding table lists a first plurality of next hop devices to which the first network device distributes traffic flows via a first plurality of links;
• and
• subsequent to a link to the second network device being established or disconnected, updating a second hardware forwarding table on the second network device for the given destination prefix in accordance with the first and second modes based on whether the second software forwarding table on the second network device for the given destination prefix is at capacity, wherein the second hardware forwarding table lists a second plurality of next hop devices to which the second network device distributes traffic flows via a second plurality of links, wherein:
• the first mode comprises a resilient mode that analyzes previous states of the first and second hardware forwarding tables to minimize disruption to existing traffic flows to destination addresses corresponding the given destination prefix;
• and
• the second mode comprises an ordered mode that disregards the previous states of the first and second hardware forwarding tables so that an order of the first plurality of next hop devices listed in the first hardware forwarding table is consistent with an order of the second plurality of next hop devices listed in the second hardware forwarding table.