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

Patent metadata

Field	Value
Publication number	US-11601364-B2
Application number	US-202017115592-A
Country	US
Kind code	B2
Filing date	Dec 8, 2020
Priority date	Mar 27, 2017
Publication date	Mar 7, 2023
Grant date	Mar 7, 2023

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 locating a first route network prefix associated with the first route;
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;
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; and
in response to the determination that the first parent network prefix and the first route network prefix are reachable using the first common next hop after the update, removing an existing forwarding information base (FIB) entry in the FIB associated with the first route network prefix.

2. The method of claim 1 , wherein determining that the first parent network prefix and the first route network prefix were reachable using the pair of different next hops connected to the network element comprises:
obtaining existing bridging next hop information (EBNHI) corresponding to the first route network prefix prior to the update;
obtaining parent bridging next hop information (PBNHI) corresponding to the first parent network prefix; and
determining that the EBNHI does not match the PBNHI,
wherein the EBNHI is associated with one of the next hops of the pair of different next hops, and wherein the PBNHI is associated with the other next hop of the first pair of different next hops.

3. The method of claim 1 , wherein determining that the first parent network prefix and the first route network prefix are reachable using the first common next hop connected to the network element comprises:
obtaining new bridging next hop information (NBNHI) corresponding to the first route network prefix after the update; and
determining that the NBNHI matches the PBNHI,
wherein the NBNHI is associated with the first common next hop, and wherein the first common next hop is one of the first pair of different next hops.

4. The method of claim 1 , further comprising:
identifying, based on the locating, a child network prefix for the first route network prefix using a network prefix trie (NPT);
determining that, prior to the update, the child network prefix and the first route network prefix were reachable using a second pair of different next hops connected to the network element;
determining that, after the update, the child network prefix and the first route network prefix are reachable using a second common next hop connected to the network element; and
removing a second existing FIB entry in the FIB associated with the child network prefix.

5. The method of claim 4 , wherein identifying the child network prefix comprises:
accessing trie nodal information associated with the first route network prefix;
obtaining a child reference from the trie nodal information; and
identifying the child network prefix using the child reference.

6. The method of claim 1 , further comprising:
detecting that a second route is removed from the RIB on the network element;
identifying a second route network prefix associated with the second route;
obtaining route bridging next hop information (RBNHI) corresponding to the second route network prefix;
identifying a second parent network prefix for the second route network prefix;
obtaining a second PBNHI corresponding to the second parent network prefix;
determining that the RBNHI does not match the second PBNHI;
removing a third existing FIB entry in the FIB associated with the second route network prefix.

7. The method of claim 6 , further comprising:
identifying, based on the locating, a second child network prefix for the first route network prefix using the NPT;
obtaining child bridging next hop information (CBNHI) associated with the second child network prefix;
based on a determination that the CBNHI matches the second PBNHI and the CBNHI does not match the RBNHI, removing a fourth existing FIB entry in the FIB associated with the second child network prefix.

8. The method of claim 1 , wherein determining the first parent network prefix comprises:
accessing trie nodal information associated with the first route network prefix;
obtaining a parent reference from the trie nodal information; and
identifying the first parent network prefix using the parent reference.

9. The method of claim 8 , wherein the trie nodal information comprises bridging next hop information (BNHI) corresponding to the first route network prefix and the parent reference.

10. The method of claim 9 , wherein the trie nodal information further comprises at least one child reference.

11. A network element, comprising:
a processor;
a data plane comprising a forwarding information base (FIB); and
a control plane comprising a routing information base (RIB) and a FIB Compressor operatively connected to the RIB and the FIB, and when the FIB Compressor executes on the processor, the FIB Compressor performs a method, the method comprises:
detecting an update to a first route in a routing information base (RIB) and locating a first route network prefix associated with the first route;

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;
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; and
in response to the determination that the first parent network prefix and the first route network prefix are reachable using the first common next hop after the update removing an existing forwarding information base (FIB) entry in the FIB associated with the first route network prefix.

12. The network element of claim 11 , wherein determining that the first parent network prefix and the first route network prefix were reachable using the pair of different next hops connected to the network element comprises:
obtaining existing bridging next hop information (EBNHI) corresponding to the first route network prefix prior to the update;
obtaining parent bridging next hop information (PBNHI) corresponding to the first parent network prefix; and
determining that the EBNHI does not match the PBNHI,
wherein the EBNHI is associated with one of the next hop of the pair of different next hops, and wherein the PBNHI is associated with the other next hop of the first pair of different next hops.

13. The network element of claim 11 , wherein determining that the first parent network prefix and the first route network prefix are reachable using the first common next hop connected to the network element comprises:
obtaining new bridging next hop information (NBNHI) corresponding to the first route network prefix after the update; and
determining that the NBNHI matches the PBNHI,
wherein the NBNHI is associated with the first common next hop, and wherein the first common next hop is one of the first pair of different next hops.

14. The network element of claim 11 , further comprising:
identifying, based on the locating, a child network prefix for the first route network prefix using a network prefix trie (NPT);
determining that, prior to the update, the child network prefix and the first route network prefix were reachable using a second pair of different next hops connected to the network element;
determining that, after the update, the child network prefix and the first route

Assignees

• Arista Networks Inc

Inventors

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

Classifications

• H04L45/745

  Address table lookup; Address filtering · CPC title

• H04L45/48 Primary

  Routing tree calculation · CPC title

• H04L45/021

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

• H04L45/748

  using longest matching prefix · CPC title