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

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.