Method and system for programming equal-cost multi-path routes on network devices

• US 10,122,620 B2
• Filed: 09/06/2017
• Issued: 11/06/2018
• Est. Priority Date: 05/28/2015
• Status: Active Grant

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Arista Networks, Inc.
• Inventors: Gattani, Akshay
• Primary Examiner(s): Mered, Habte
• Application Number:
  US15/697,123
• Publication Number:
  US 20170366450A1
• Time in Patent Office: 426 Days
• CPC Class Codes: H04L 41/0813 characterised by the conditions triggering a change of settings
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

A method for configuring a network device. The method includes writing a route for a destination IP prefix to the forwarding information base (FIB), and after writing the route, obtaining a set of routes and Writing the set of routes to a routing information base (RIB). The method further includes, after writing the set of routes to the RIB and after the expiration of a timer: identifying, in the RIB, a set of ECMP routes from the plurality of routes for the destination IP prefix, processing the set of ECMP routes for the destination IP prefix, and updating the FIB of the network device based on set of processed ECMP routes.

Claims

1. A method for configuring a network device, comprising:

setting a defer equal-cost multi-path (ECMP) variable to a first value;

setting a first timer to a user-configurable time value;

setting a routes received variable to zero;

starting the first timer;

receiving a plurality of routes while the first timer performs a countdown of the user-configurable time value to obtain an increased routes received variable;

determining a number of received routes using the increased routes received variable;

determining that the number of received routes exceeds a user-configurable minimum number of routes in order to discover that an active session exists;

determining that the first timer has reached zero;

determining, based on the first timer reaching completing the countdown and the existence of the active session, that a user-configurable minimum number of active sessions is not exceeded;

setting, based on the user-configurable minimum number of active sessions not being exceeded, the defer ECMP variable to a second value;

after setting the defer ECMP variable to the second value, identifying, in a routing information base (RIB) of the network device, a set of ECMP routes from a plurality of routes for a destination IP prefix; and

updating a forwarding information base (FIB) of the network device based on the set of ECMP routes.

2. The method of claim 1, further comprising:

before determining a number of received routes using the increased routes received variable,

determining that a global timer has finished a countdown; and

based on determining that the global timer has finished the countdown, setting the defer ECMP variable to the second value.

3. The method of claim 1, further comprising:

re-setting the defer equal-cost multi-path (ECMP) variable to the first value;

re-setting the first timer to the user-configurable time value;

re-setting the routes received variable to zero;

re-starting the first timer;

receiving a second plurality of routes while the first timer performs a second countdown of the user-configurable time value to obtain a second increased routes received variable;

determining a second number of received routes using the second increased routes received variable;

determining that the second number of received routes exceeds the user-configurable minimum number of routes in order to discover that a plurality of active sessions exist;

determining that the first timer has reached zero;

determining, based on the first timer reaching completing the countdown and the existence of the plurality of active sessions, that the user-configurable minimum number of active sessions is exceeded; and

keeping, based on the user-configurable minimum number of active sessions being exceeded, the defer ECMP variable at the first value.

4. The method of claim 1, wherein the routes received variable tracks the number of routes received within the user-configurable time value.

5. The method of claim 1, further comprising:

before updating the FIB, processing the set of ECMP routes for the destination IP prefix, wherein processing the set of ECMP routes comprises;

selecting a route from the set of ECMP routes for the destination IP prefix as an ECMP head route, and

directing, using pointers, a set of remaining routes from the set of ECMP routes to the ECMP head route.

6. The method of claim 1, wherein the first timer is started when a first update message is received from an established border gateway protocol (BGP) session.

12. The method of claim 2, wherein the first timer is started when a first update message is received from an established border gateway protocol (BGP) session.

7. A non-transitory computer readable medium comprising instructions which, when executed, perform a method for configuring a network device, the method comprising:

setting a defer equal-cost multi-path (ECMP) variable to a first value;

setting a first timer to a user-configurable time value;

setting a routes received variable to zero;

starting the first timer;

receiving a plurality of routes while the first timer performs a countdown of the user-configurable time value to obtain an increased routes received variable;

determining a number of received routes using the increased routes received variable;

determining that the number of received routes exceeds a user-configurable minimum number of routes in order to discover that an active session exists;

determining that the first timer has reached zero;

determining, based on the first timer reaching completing the countdown and the existence of the active session, that a user-configurable minimum number of active sessions is not exceeded;

setting, based on the user-configurable minimum number of active sessions not being exceeded, the defer ECMP variable to a second value;

after setting the defer ECMP variable to the second value, identifying, in a routing information base (RIB) of the network device, a set of ECMP routes from a plurality of routes for a destination IP prefix; and

updating a forwarding information base (FIB) of the network device based on the set of ECMP routes.

8. The non-transitory computer readable medium of claim 7, wherein the method performed by execution of the instructions further comprises:

before determining a number of received routes using the increased routes received variable,

determining that a global timer has finished a countdown; and

based on determining that the global timer has finished the countdown, setting the defer ECMP variable to the second value.

9. The non-transitory computer readable medium of claim 7, wherein the method performed by execution of the instructions further comprises:

re-setting the defer equal-cost multi-path (ECMP) variable to the first value;

re-setting the first timer to the user-configurable time value;

re-setting the routes received variable to zero;

re-starting the first timer;

receiving a second plurality of routes while the first timer performs a second countdown of the user-configurable time value to obtain a second increased routes received variable;

determining a second number of received routes using the second increased routes received variable;

determining that the second number of received routes exceeds the user-configurable minimum number of routes in order to discover that a plurality of active sessions exist;

determining that the first timer has reached zero;

determining, based on the first timer reaching completing the countdown and the existence of the plurality of active sessions, that the user-configurable minimum number of active sessions is exceeded; and

keeping, based on the user-configurable minimum number of active sessions being exceeded, the defer ECMP variable at the first value.

10. The non-transitory computer readable medium of claim 7, wherein the routes received variable tracks the number of routes received within the user-configurable time value.

11. The non-transitory computer readable medium of claim 7, wherein the method performed by execution of the instructions further comprises:

processing the set of ECMP routes for the destination IP prefix, wherein processing the set of ECMP routes comprises;

before updating the FIB, selecting a route from the set of ECMP routes for the destination IP prefix as an ECMP head route,

directing, using pointers, a set of remaining routes from the set of ECMP routes to the ECMP head route.

13. A network device, comprising:

a routing information base (RIB);

a forwarding information base (FIB); and

a processor coupled to memory and operatively connected to the RIB and the FIB, and configured to;

set a defer equal-cost multi-path (ECMP) variable to a first value;

set a first timer to a user-configurable time value;

set a routes received variable to zero;

start the first timer;

receive a plurality of routes while the first timer performs a countdown of the user-configurable time value to obtain an increased routes received variable;

determine a number of received routes using the increased routes received variable;

determine that the number of received routes exceeds a user-configurable minimum number of routes in order to discover that an active session exists;

determine that the first timer has reached zero;

determine, based on the first timer reaching completing the countdown and the existence of the active session, that a user-configurable minimum number of active sessions is not exceeded;

set, based on the user-configurable minimum number of active sessions not being exceeded, the defer ECMP variable to a second value;

after setting the defer ECMP variable to the second value, identify in the RIB a set of ECMP routes from a plurality of routes for a destination IP prefix; and

update the FIB based on the set of ECMP routes.

14. The network device of claim 13, wherein the processor is further configured to:

before determining a number of received routes using the increased routes received variable,

determine that a global timer has finished a countdown; and

set, based on determining that the global timer has finished the countdown, the defer ECMP variable to the second value.

15. The network device of claim 13, wherein the processor is further configured to:

re-set the defer equal-cost multi-path (ECMP) variable to the first value;

re-set the first timer to the user-configurable time value;

re-set the routes received variable to zero;

re-start the first timer;

receive a second plurality of routes while the first timer performs a second countdown of the user-configurable time value to obtain a second increased routes received variable;

determine a second number of received routes using the second increased routes received variable;

determine that the second number of received routes exceeds the user-configurable minimum number of routes in order to discover that a plurality of active sessions exist;

determine that the first timer has reached zero;

determine, based on the first timer reaching completing the countdown and the existence of the plurality of active sessions, that the user-configurable minimum number of active sessions is exceeded;

keep, based on the user-configurable minimum number of active sessions being exceeded, the defer ECMP variable to at the first value.

16. The network device of claim 13, wherein the routes received variable tracks the number of routes received within the user-configurable time value.

17. The network device of claim 13, wherein the processor is further configured to:

process the set of ECMP routes for the destination IP prefix, wherein, to process the set of ECMP routes, the processor is further configured to;

before updating the FIB, select a route from the set of ECMP routes for the destination IP prefix as an ECMP head route, and

direct, using pointers, a set of remaining routes from the set of ECMP routes to the ECMP head route.