CSNP cache for efficient periodic CSNP in a router

• US 7,742,437 B2
• Filed: 11/15/2005
• Issued: 06/22/2010
• Est. Priority Date: 11/15/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Yeung, Derek Man-Kit, Hopps, Christian, Li, Anthony, Venugopal, Nair
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): Rutkowski; Jeffrey M
• Application Number:
  US11/280,950
• Publication Number:
  US 20060227790A1
• Time in Patent Office: 1,680 Days
• Field of Search: 370/254, 370/255, 370/235, 370/236, 370/252, 370/351, 370/363, 370/400, 370/429, 370/338, 370/352, 370/389, 370/390, 714/13, 709/238, 709/216, 707200-206, 455/456.1
• US Class Current: 370/255
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/60 Router architectures

Abstract

A networking device such as a router may include, in one embodiment, a database storing a plurality of link state entries, and a cache operatively coupled with the database, the cache storing entries relating to the link state entries of the database. The networking device may also include a module for sending, over a network, packets including link state data, the module operatively coupled with the cache. In one example, the module accesses the cache to create one or more packets including link state data. Embodiments of the invention may be used for forming CSNP packets (complete sequence number packets) without the need for having to repeatedly walking a link state database in order to form the CNSP packets.

Claims

1. A networking device for use in a network, the network device comprising:

a link-state database storing a plurality of link state entries;

a cache, operatively coupled with the link-state database, the cache storing entries relating to the link state entries of the link-state database; and

at least one processor operatively coupled with the cache to;

determine a change to 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.

2. The networking device of claim 1, wherein the link state entries are derived from link state packets received by the networking device.

3. The networking device of claim 1, wherein the networking device has multiple interfaces.

4. The networking device of claim 1, wherein the entries stored in the cache include a list of link state headers.

5. The networking device of claim 1, wherein the entries stored in the cache include data which identifies one or more link states.

6. The networking device of claim 1, wherein entries stored in the cache are arranged in an tree data structure.

7. The networking device of claim 1, wherein entries stored in the cache are arranged in a link-list data structure.

8. The networking device of claim 1, wherein the networking device is a router.

9. The apparatus of claim 1, wherein the at least one processor is further to access the cache to create one or more packets including link state data, and to send the one or more packets over the network.

10. The networking device of claim 9, further comprising:

a timer for providing a periodic interval that controls transmission of the network packets including link state data.

11. The networking device of claim 10, wherein when the timer expires, the at least one processor access the cache to create the one or more packets including link state data.

12. The networking device of claim 9, wherein the packets are CSNP packets.

13. 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.

14. The apparatus of claim 13, in which the computer readable code, when executed, is further operable to:

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.

15. The apparatus of claim 13, in which the computer readable code, when executed, is further operable to:

determine that the cache entries include three Complete Sequence Number Protocol Data Units (CSNP) code entries organized as a tree; and

coalesce the three CSNP code entries by removing one of the three CSNP code entries as a left hand neighbor from the tree.

16. The apparatus of claim 15, in which the computer readable code, when executed, is operable to coalesce the three CSNP code entries by removing one of the three CSNP code entries as a right hand neighbor from the tree.

17. 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.

18. The apparatus of claim 17, in which the computer readable code, when executed, is operable to coalesce three CSNP code entries by removing one of the three CSNP code entries as a right hand neighbor from the tree.