Systems and methods for optimized route caching

Abstract

A method for optimized route caching includes comparing a destination address of a network packet to a first set of prefixes in a routing cache, and comparing the destination address to a second set of prefixes in a full routing table when a longest matching prefix for the destination address is not found in the routing cache. The method further includes copying the longest matching prefix and a set of sub-prefixes of the longest matching prefix from the full routing table to the routing cache, and forwarding the network packet.

What is claimed is: 
     
       1. A system, comprising:
 a memory that stores instructions; 
 a processor that executes the instructions to perform operations, the operations comprising:
 merging a plurality of contiguous sub-prefixes of a longest matching prefix of a network packet into a super-prefix when the plurality of contiguous sub-prefixes have a same output port and different downstream routes; 
 causing the plurality of contiguous sub-prefixes to be separated in a full routing table when the plurality of contiguous sub-prefixes have a same next hop and the different downstream routes; 
 evicting a shortest sub-prefix of a subset of the plurality of contiguous sub-prefixes when multiple sub-prefixes of the subset match eviction criteria, when the shortest sub-prefix has been used a smallest number of times in comparison to other sub-prefixes of the subset, and when the shortest sub-prefix has a last used time that is older than the other sub-prefixes of the subset; and 
 forwarding the network packet. 
 
 
     
     
       2. The system of  claim 1 , wherein the operations further comprise inserting the super-prefix into a routing cache. 
     
     
       3. The system of  claim 1 , wherein the operations further comprise copying, when the longest matching prefix is found in the full routing table and not found in a routing cache, the longest matching prefix to the routing cache. 
     
     
       4. The system of  claim 1 , wherein the operations further comprise receiving the network packet. 
     
     
       5. The system of  claim 1 , wherein the operations further comprise forwarding the network packet to an intermediary when the longest matching prefix is not found in a routing cache. 
     
     
       6. The system of  claim 1 , wherein the operations further comprise comparing a destination address of the network packet to a set of prefixes in the full routing table. 
     
     
       7. The system of  claim 1 , wherein the operations further comprise updating a routing cache when the longest matching prefix is found in the routing cache. 
     
     
       8. The system of  claim 1 , wherein the operations further comprise evicting, when a routing cache is full, a shortest prefix from the routing cache. 
     
     
       9. The system of  claim 1 , wherein the operations further comprise directing incoming traffic to an interface based on a preferred route associated with the longest matching prefix. 
     
     
       10. The system of  claim 1 , wherein the operations further comprise placing the network packet in a queue when the longest matching prefix is not found in a routing cache. 
     
     
       11. The system of  claim 1 , wherein the operations further comprise forwarding the network packet to a next hop. 
     
     
       12. The system of  claim 1 , wherein the operations further comprise copying, from the full routing table to a routing cache, a sub-prefix of the longest matching prefix, wherein the sub-prefix is a special-purpose prefix.