Equal-cost multi-path (ECMP) routing with resiliency and consistent ordering
A method of operating a network device is provided. The method may include updating a software forwarding table in response to a link between the network device and one or more next hops device being disconnected or connected. The software forwarding table may list next hop devices currently available or connected to the network device for a given destination prefix. The method may include determining whether to update a hardware forwarding table also associated with the given destination prefix depending on whether one or more criteria have been satisfied. The hardware forwarding table may be updated in accordance with a resilient mode or an ordered mode. The resilient mode takes into account history information associated with the hardware forwarding table, whereas the ordered mode does not take into account the history information associated with the hardware forwarding table.
1 . 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, wherein the software forwarding table lists next hop devices currently available to the network device for a given destination prefix; and
in response to updating the software forwarding table, determining whether to update a hardware forwarding table corresponding to the software forwarding table for the given destination prefix in accordance with a resilient mode or an ordered mode, wherein the resilient mode considers a prior state of the hardware forwarding table to evenly distribute traffic flows, via a plurality of links, to next hop devices listed in the hardware forwarding table, and wherein the ordered mode ignores the prior state of the hardware forwarding table.
2 . The method of claim 1 , wherein determining whether to update the hardware forwarding table in accordance with the resilient mode or the ordered mode comprises determining whether the updated software forwarding table is at steady state.
3 . The method of claim 2 , further comprising:
in response to determining that the updated software forwarding table for the given destination prefix is at steady state, updating the hardware forwarding table for the given destination prefix in accordance with the ordered mode.
4 . The method of claim 3 , further comprising:
in response to determining that the updated software forwarding table for the given destination prefix is not at steady state, updating the hardware forwarding table for the given destination prefix in accordance with the resilient mode.
5 . The method of claim 1 , wherein the hardware forwarding table has a fixed size that is larger than a size of the software forwarding table.
6 . The method of claim 1 , wherein determining whether to update the hardware forwarding table in accordance with the resilient mode or the ordered mode comprises determining whether the updated software forwarding table is at a configured capacity and wherein the hardware forwarding table has a fixed size that is equal to a multiple of the configured capacity.
7 . The method of claim 1 , wherein updating the hardware forwarding table in accordance with the resilient mode comprises updating the hardware forwarding table to minimize disruption to existing traffic flows to a destination address corresponding to the given destination prefix.
8 . The method of claim 1 , wherein updating the hardware forwarding table in accordance with the ordered mode comprises updating the hardware forwarding table to implement a consistent ordering of next hop devices listed in the hardware forwarding table as specified by the corresponding software forwarding table.
9 . 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.
10 . 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.
11 . The method of claim 10 , wherein the first and second hardware forwarding tables are updated in accordance with the ordered mode in response to determining that the first and second software forwarding tables are at capacity.
12 . The method of claim 11 , wherein the first and second hardware forwarding tables are updated in accordance with the resilient mode in response to determining that the first and second software forwarding tables are below capacity.