METHOD AND SYSTEM FOR PROGRAMMING EQUAL-COST MULTI-PATH ROUTES ON NETWORK DEVICES

• US 20160352619A1
• Filed: 05/28/2015
• Published: 12/01/2016
• Est. Priority Date: 05/28/2015
• Status: Active Grant

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Arista Networks, Inc.
• Inventors: Gattani, Akshay
• Granted Patent: US 9,787,575 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 IP prefix to the 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 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.

2. The method of claim 1, wherein the plurality of routes are obtained using at least one active 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. The method of claim 1, wherein processing the set of ECMP routes for the destination IP prefix comprises:

selecting one route from the set of ECMP routes for the destination IP prefix as the ECMP head route; and

associating the remaining routes from the set of ECMP routes to the ECMP head route using pointers.

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

write a route for a destination IF prefix to the 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 the expiration of a timer;

identify, in the RIB, a set of ECMP routes from the plurality of routes for the destination IP prefix;

process the set of ECMP routes for the destination IP prefix; and

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

8. The non-transitory computer readable medium of claim 7, wherein the plurality of routes are obtained using at least one active BGP session.

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

10. The non-transitory computer readable medium of claim 7, 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.

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

12. The non-transitory computer readable medium of claim 7, wherein the instructions for processing the set of ECMP routes for the destination IP prefix comprise instructions to:

select one route from the set of ECMP routes for the destination IP prefix as the ECMP head route; and

associate the remaining routes from the set of ECMP routes to the ECMP head route using pointers.

13. A network device comprising:

a routing information base (RIB); and

a forwarding information base (FIB),

wherein the network device writes a route for the destination IP prefix to the forwarding information base (FIB);

wherein the network device, after writing the route, obtains a plurality of routes and writes the plurality of routes to the RIB;

wherein the network device, after writing the plurality of routes to the RIB and after the expiration of a timer;

identifies, in the RIB, a set of ECMP routes from the plurality of routes for the destination IP prefix;

processes the set of ECMP routes for the destination IP prefix;

updates the FIB based on set of processed ECMP routes.

14. The network device of claim 13, wherein the network device obtains the plurality of routes using at least one active BGP session.

15. The network device of claim 13, wherein the network device starts the timer when the network device starts receiving routes from a peer network device.

16. The network device of claim 13, wherein the network device identifies 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.

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

18. The network device of claim 13, wherein the network device processes the set of ECMP routes for the destination IP prefix by:

selecting one route from the set of ECMP routes for the destination IP prefix as the ECMP head route; and

associating the remaining routes from the set of ECMP routes to the ECMP head route using pointers.

19. The network device of claim 13, wherein the network device is a router.

20. The network device of claim 13, wherein the network device is a multilayer switch