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

Patent metadata

Field	Value
Publication number	US-10892986-B2
Application number	US-201715470417-A
Country	US
Kind code	B2
Filing date	Mar 27, 2017
Priority date	Mar 27, 2017
Publication date	Jan 12, 2021
Grant date	Jan 12, 2021

Abstract

In general, the invention relates to a method for programming a network element. The method includes detecting an addition of a first route in a routing information base (RIB) on the network element, adding, in response to detecting the addition, a first route network prefix associated with the first route to a network prefix trie (NPT), identifying, based on the adding, a first parent network prefix for the first route network prefix using the NPT, making a first determination that the first route network prefix and the first parent network prefix are reachable via a first common next hop connected to the network element, and waiving, based on the first determination, a creation of a forwarding information base (FIB) entry associated with the first route network prefix in a FIB on the network element.

First claim

What is claimed is:

1. A method for programming a network element, comprising:
detecting an addition of a first route in a routing information base (RIB) on the network element, and adding a first route network prefix associated with the first route to a network prefix trie (NPT), wherein the NPT is maintained within the network element;
identifying, based on the adding, a first parent network prefix for the first route network prefix using the NPT;
making a first determination that the first route network prefix and the first parent network prefix are reachable via a first common next hop connected to the network element;
waiving, based on the first determination, a creation of a forwarding information base (FIB) entry associated with the first route network prefix in the FIB on the network element;
detecting an update to a second route in the RIB and locating a second route network prefix associated with the second route within the NPT;
making a second determination that, prior to the update, a second parent network prefix and the second route network prefix were reachable using a pair of different next hops connected to the network element;
making a third determination, based on the second determination, that, after the update, the second parent network prefix and the second route network prefix are reachable using a second common next hop connected to the network element; and
removing, based on the third determination, an existing FIB entry in the FIB associated with the second route network prefix.

2. The method of claim 1 , wherein adding the first route network prefix to the NPT is based at least on a network prefix size associated with the first route network prefix.

3. The method of claim 1 , wherein identifying 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.

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

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

6. The method of claim 1 , wherein making the first determination comprises:
obtaining route bridging next hop information (RBNHI) corresponding to the first route network prefix;
obtaining parent bridging next hop information (PBNHI) corresponding to the first parent network prefix; and
determining that the RBNHI matches the PBNHI.

7. The method of claim 6 , wherein the RBNHI comprises a media access control (MAC) address associated with the first common next hop and a network interface identifier associated with a network interface on the network element connected to the first common next hop.

8. The method of claim 1 , wherein making the second determination comprises:
obtaining existing bridging next hop information (EBNHI) corresponding to the second route network prefix prior to the update;
obtaining parent bridging next hop information (PBNHI) corresponding to the second parent network prefix; and
determining that the EBNHI does not match the PBNHI,
wherein the EBNHI is associated with a first next hop of the pair of different next hops, wherein the PBNHI is associated with a second next hop of the first pair of different next hops.

9. The method of claim 8 , wherein making the third determination comprises:
obtaining new bridging next hop information (NBNHI) corresponding to the second route network prefix after the update; and
determining that the NBNHI matches the PBNHI,
wherein the NBNHI is associated with the second common next hop, wherein the second common next hop is the second next hop of the first pair of different next hops.

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

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

12. 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 addition of a first route in the RIB, and adding a first route network prefix associated with the first route to a network prefix trie (NPT), wherein the NPT is maintained within the network element;
identifying, based on the adding, a first parent network prefix for the first route network prefix using the NPT;
making a first determination that the first route network prefix and the first parent network prefix are reachable via a first common next hop connected to the network element;
waiving, based on the first determination, a creation of a FIB entry associated with the first route network prefix in the FIB,
detecting an update to a second route in the RIB, and locating a second route network prefix associated with the second route within the NPT;
making a second determination that, prior to the update, a second parent network prefix and the second route network prefix were reachable using a first pair of different next hops connected to the network element;
making a third determination, based on the second determination, that, after the update, the second parent network prefix and the second route network prefix are reachable using a second common next hop connected to the network element; and
removing, based on the third determination, a first existing FIB entry in the FIB associated with the second route network prefix.

13. The network element of claim 12 , wherein the data plane further comprises a plurality of network interfaces, wherein the first common next hop is connected to the network element through a first network interface of the plurality of network interfaces.

14. The network element of claim 12 , wherein the method further comprises:
identifying, based on the locating, a child network prefix for the second route network prefix using the NPT;
making a fourth determination that, prior to the update, the child network prefix and the second route network prefix were reachable using a second pair of different next hops connected to the network element;
making a fifth determination, based on the fourth determination, that, after the update, the child network prefix and the second route network prefix are reachable using a third common next hop connected to the network element; and
removing, based on the fifth determination, a second existing FIB entry in the FIB associated with the child network prefi

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/748

  using longest matching prefix · CPC title

• H04L45/021

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