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

• US 9,787,575 B2
• Filed: 05/28/2015
• Issued: 10/10/2017
• 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:
  US14/724,686
• Publication Number:
  US 20160352619A1
• Time in Patent Office: 866 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:

writing a route for a destination Internet Protocol (IP) prefix to a forwarding information base (FIB);

after writing the route, obtaining a plurality of routes and writing the plurality of routes to a routing information base (RIB);

after writing the plurality of routes to the RIB and after an expiration of a timer;

identifying, in the RIB, a set of equal-cost multi-path (ECMP) routes from the plurality of routes for the destination IP prefix;

processing the set of ECMP routes for the destination IP prefix to obtain a set of processed ECMP routes, wherein processing the set of ECMP routes comprises;

selecting one 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; and

updating the FIB of the network device based on the set of processed ECMP routes.

2. The method of claim 1, wherein the plurality of routes is obtained using at least one active border gateway protocol (BGP) session.

3. The method of claim 1, wherein the timer is started when the network device starts receiving routes from a peer network device.

4. The method of claim 1, wherein identifying the set of ECMP routes for the destination IP prefix comprises selecting, in the RIB, routes for the destination IP prefix with a lowest associated cost.

5. The method of claim 4, wherein the routes, selected in the RIB, have identical next hops.

6. A non-transitory computer readable medium comprising instructions, that enable a network device to:

write a route for a destination Internet Protocol (IP) prefix to a forwarding information base (FIB);

after writing the route, obtain a plurality of routes and write the plurality of routes to a routing information base (RIB);

after writing the plurality of routes to the RIB and after an expiration of a timer;

identify, in the RIB, a set of equal-cost multi-path (ECMP) routes from the plurality of routes for the destination IP prefix;

process the set of ECMP routes for the destination IP prefix to obtain a set of processed ECMP routes, wherein the set of ECMP routes are processed by instructions further enabling the network device to;

select one 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; and

update the FIB of the network device based on the set of processed ECMP routes.

7. The non-transitory computer readable medium of claim 6, wherein the plurality of routes is obtained using at least one active border gateway protocol (BGP) session.

8. The non-transitory computer readable medium of claim 6, wherein the timer is started when the network device starts receiving routes from a peer network device.

9. The non-transitory computer readable medium of claim 6, wherein identifying the set of ECMP routes for the destination IP prefix comprises selecting, in the RIB, routes for the destination IP prefix with a lowest associated cost.

10. The non-transitory computer readable medium of claim 9, wherein the routes, selected in the RIB, have identical next hops.

11. 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;

write a route for a destination Internet Protocol (IP) prefix to the FIB;

after writing the route, obtain a plurality of routes and write the plurality of routes to the RIB;

after writing the plurality of routes to the RIB and after an expiration of a timer;

identify, in the RIB, a set of equal-cost multi-path (ECMP) routes from the plurality of routes for the destination IP prefix;

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

select one 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; and

update the FIB based on the set of processed ECMP routes.

12. The network device of claim 11, wherein the processor is further configured to obtain the plurality of routes using at least one active border gateway protocol (BGP) session.

13. The network device of claim 11, wherein the processor is further configured to start the timer when the network device starts receiving routes from a peer network device.

14. The network device of claim 11, wherein the processor is further configured to identify the set of ECMP routes for the destination IP prefix by selecting, in the RIB, routes for the destination IP prefix with a lowest associated cost.

15. The network device of claim 14, wherein the routes, selected in the RIB, have identical next hops.

16. The network device of claim 11, wherein the network device is a router.

17. The network device of claim 11, wherein the network device is a multilayer switch.