CSNP cache for efficient periodic CSNP in a router

An apparatus comprising:

• at least one processor;
• and
• a non-transitory computer usable medium in communication with the at least one processor, the computer usable medium having stored therein computer readable code for execution and when executed operable to:
• determine a change to a link-state database which stores a plurality of link state entries which are related to a plurality of cache entries in a cache operatively coupled with the link-state database;
• coalesce the plurality of cache entries in response to said change to the link-state database, such that the cache has fewer cache entries after the coalescing;
• update the cache entries in the cache;
• determine that a complete range of possible link-state identifications is not represented in the cache entries;
• add a new invalid entry into the cache;
• and
• set a Protocol Data Unit (PDU) field of the new invalid entry to zero, and set a valid flag of the cache entry to true.

An apparatus comprising:

• at least one processor;
• and
• a non-transitory computer usable medium in communication with the at least one processor, the computer usable medium having stored therein computer readable code for execution and when executed operable to:
• determine a change to a link-state database which stores a plurality of link state entries which are related to a plurality of cache entries in a cache operatively coupled with the link-state database;
• coalesce the plurality of cache entries in response to said change to the link-state database, such that the cache has fewer cache entries after the coalescing;
• update the cache entries in the cache;
• determine that a number of Link-State Packets (LSPs) for a cache entry exceeds a number of possible LSPs for that cache entry;
• and
• subdivide the cache entry into multiple cache entries to accommodate the LSPs.