Efficient algorithm to eliminate redundant specific prefixes in forwarding information base using trie

Patent metadata

Field	Value
Publication number	US-12301452-B2
Application number	US-202418415771-A
Country	US
Kind code	B2
Filing date	Jan 18, 2024
Priority date	Mar 27, 2017
Publication date	May 13, 2025
Grant date	May 13, 2025

Abstract

A network element and method for programming a network element that includes detecting an update to a first route in a routing information base (RIB) is disclosed. The method includes locating a first route network prefix associated with the first route within a network prefix trie (NPT); determining that, prior to the update, a first parent network prefix and the first route network prefix were reachable using a pair of different next hops connected to the network element; and determining that, after the update, the first parent network prefix and the first route network prefix are reachable using a first common next hop connected to the network element. The method also includes removing an existing forwarding information base (FIB) entry in the FIB associated with the first route network prefix.

First claim

What is claimed is:

1. A method for programming a network element, comprising:
detecting an update to a first route in a routing information base (RIB) and determining a first route network prefix associated with the first route;
based on the update, determining a first parent network prefix associated with the first route network prefix;
determining that a first parent network prefix and the first route network prefix are reachable using a common next hop connected to the network element;
determining if the creation of a forwarding information base (FIB) entry associated with the first network prefix can be waived by determining if there is at least one entry in the FIB associated with the common next hop or the first parent network prefix; and
based on a determination that the at least one entry in the FIB cannot be waived, creating the FIB entry associated with the first route network prefix in the FIB on the network element.

2. The method of claim 1 , wherein the first parent network prefix is determined using a network prefix data structure.

3. The method of claim 2 , wherein determining that the first parent network prefix associated with the first route network prefix is based on the network prefix data structure.

4. The method of claim 3 , wherein the network prefix data structure is a network prefix trie (NPT).

5. The method of claim 4 , wherein nodal information of the NPT comprises bridging next hop information (BNHI) corresponding to the first route network prefix and the first parent network prefix.

6. The method of claim 3 , wherein the update to the first route is a creation of the first route in the RIB.

7. The method of claim 6 , wherein the first parent network prefix is added to the network prefix data structure in response to the creation of the first route in the RIB.

8. The method of claim 7 , wherein determining if there is at least one entry in the FIB associated with the common next hop or the first parent network prefix comprises determining if the first route network prefix and the first parent network prefix are reachable via a first common next hop connected to the network element using the network prefix data structure.

9. A system, comprising:
a processor; and
a non-transitory computer readable medium, comprising instructions for:
detecting an update to a first route in a routing information base (RIB) and determining a first route network prefix associated with the first route;
based on the update, determining a first parent network prefix associated with the first route network prefix using a network prefix data structure;
determining that a first parent network prefix and the first route network prefix are reachable using a common next hop connected to the network element;
determining if the creation of a forwarding information base (FIB) entry associated with the first network prefix can be waived by determining if there is at least one entry in the FIB associated with the common next hop or the first parent network prefix in the network prefix data structure; and
based on a determination that the at least one entry in the FIB cannot be waived, creating the FIB entry associated with the first route network prefix in the FIB on the network element.

10. The system of claim 9 , wherein the network prefix data structure is a network prefix trie (NPT).

11. The system of claim 10 , wherein nodal information of the NPT comprises bridging next hop information (BNHI) corresponding to the first route network prefix and the first parent network prefix.

12. The system of claim 9 , wherein the update to the first route is a creation of the first route in the RIB.

13. The system of claim 12 , wherein the first parent network prefix is added to the network prefix data structure in response to the creation of the first route in the RIB.

14. The system of claim 13 , wherein determining if there is at least one entry in the FIB associated with the common next hop or the first parent network prefix comprises determining if the first route network prefix and the first parent network prefix are reachable via a first common next hop connected to the network element using the network prefix data structure.

15. A non-transitory computer readable medium, comprising instructions for:
detecting an update to a first route in a routing information base (RIB) and determining a first route network prefix associated with the first route;
based on the update, determining a first parent network prefix associated with the first route network prefix;
determining that a first parent network prefix and the first route network prefix are reachable using a common next hop connected to the network element;
determining if the creation of a forwarding information base (FIB) entry associated with the first network prefix can be waived by determining if there is at least one entry in the FIB associated with the common next hop or the first parent network prefix; and
based on a determination that the at least one entry in the FIB cannot be waived, creating the FIB entry associated with the first route network prefix in the FIB on the network element.

16. The non-transitory computer readable medium of claim 15 , wherein the first parent network prefix is determined using a network prefix data structure and determining that the first parent network prefix associated with the first route network prefix is based on the network prefix data structure.

17. The non-transitory computer readable medium, of claim 16 , wherein the network prefix data structure is a network prefix trie (NPT).

18. The non-transitory computer readable medium of claim 17 , wherein nodal information of the NPT comprises bridging next hop information (BNHI) corresponding to the first route network prefix and the first parent network prefix.

19. The non-transitory computer readable medium of claim 16 , wherein the update to the first route is a creation of the first route in the RIB.

20. The non-transitory computer readable medium of claim 19 , wherein determining if there is at least one entry in the FIB associated with the common next hop or the first parent network prefix comprises determining if the first route network prefix and the first parent network prefix are reachable via a first common next hop connected to the network element using the network prefix data structure.

Assignees

• Arista Networks Inc

Inventors

• Narayanan Kumaran
• Regmi Sudip
• Srinivas Prashant
• KASIVISWANATHAN Venkitraman

Classifications

• H04L45/748

  using longest matching prefix · CPC title

• H04L45/745

  Address table lookup; Address filtering · CPC title

• H04L45/021

  Ensuring consistency of routing table updates, e.g. by using epoch numbers · CPC title

• H04L45/48 Primary

  Routing tree calculation · CPC title