Managing state information in a computing environment

• US 8,082,364 B1
• Filed: 03/28/2011
• Issued: 12/20/2011
• Est. Priority Date: 06/10/2002
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Katz, David M., Ferguson, Dennis C.
• Primary Examiner(s): BAYARD, DJENANE M
• Application Number:
  US13/073,753
• Time in Patent Office: 267 Days
• Field of Search: 709/231, 709/232, 709/238, 709/203, 709/245
• US Class Current: 709/238
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A software module operating within a router, such as an operating system, manages state information within a hierarchically ordered and temporally-linked data structure. The software module sends state change messages to other software modules within the router, referred to as consumers, in an order that corresponds to the hierarchical order and the temporal linking. The data structure may comprise a plurality of objects to store state information. The operating system may receive event messages that indicate a change to the state information. The objects may be hierarchically linked in accordance with a hierarchy representing relationships of event messages. The objects may be temporally linked in accordance with the order in which the operating system receives event messages. The operating system may traverse the data structure according to the temporal and hierarchical links to select state change messages to send to a consumer.

Claims

1. A method for managing state information for a router, the method comprising:

receiving, with a first router process executed by a processor of the router, event messages that indicate a change to state information, wherein the state information indicates the state of a plurality of resources of the router;

managing, with the first router process, the state information within a temporally-linked and hierarchically ordered data structure stored within a computer-readable medium, wherein the data structure comprises a plurality of objects that include hierarchical pointers and temporal pointers, and wherein managing the state information comprises storing the state information within the objects, setting the hierarchical pointers to link the objects in accordance with a hierarchy representing relationships of the event messages, and setting the temporal pointers to link the objects in accordance with an order in which the event messages are received; and

communicating, by the first router process, the changes to the state information to a second router process executed by the processor according to the data structure, wherein communicating changes to the state information to the second router process according to the data structure comprises traversing the data structure in an order determined in accordance with the hierarchical pointers and temporal pointers, and delivering state change messages to the second router process in accordance with the order.

2. The method of claim 1, further comprising:

providing a consumer pointer associated with the second router process that points into the data structure; and

traversing the data structure, by the first router process, as a function of the consumer pointer.

3. The method of claim 1, further comprising, by the first router process:

receiving one of the event messages, the event message indicating a change of the state of one of the resources of the router;

determining whether to deliver the second router process a state change message that corresponds to the event message;

storing an indication within one of the objects that corresponds to the one of the resources as a function of the determination;

receiving a request for the state information from the second router process;

determining whether the indication is present in the object; and

delivering the state change message to the second router process as a function of the determination.

4. The method of claim 1, wherein each of the plurality of objects of the data structure corresponds to a respective one of the plurality of resources of the router.

5. The method of claim 1, wherein the plurality of resources of the router comprise a plurality of forwarding engines of the router.

6. The method of claim 1, wherein the plurality of resources of the router comprises:

a plurality of interface cards of the router; and

for each of the plurality of interface cards, one or more logical interfaces,

wherein each of plurality of objects within the data structure is associated with a respective one of the interface cards and the logical interfaces, and

wherein setting the hierarchical pointers to link the objects in accordance with a hierarchy comprises setting the hierarchical pointers to link the objects in accordance with a hierarchy in which each of the interface cards is above its respective one or more logical interfaces.

7. The method of claim 1, wherein the second router process maintains a routing table.

8. A router comprising a processor that executes a first router process and a second router process, wherein the first router process:

receives event messages that indicate a change to state information, wherein the state information indicates the state of a plurality of resources of the router;

manages the state information within a temporally-linked and hierarchically ordered data structure stored within a computer-readable medium, wherein the data structure comprises a plurality of objects that include hierarchical pointers and temporal pointers, and wherein the first router process;

stores the state information within the objects,

sets the hierarchical pointers to link the objects in accordance with a hierarchy representing relationships of the event messages, and

sets the temporal pointers to link the objects in accordance with an order in which the event messages are received; and

communicates the changes to the state information to a second router process executed by the processor according to the data structure, wherein the first router process;

traverses the data structure in an order determined in accordance with the hierarchical pointers and temporal pointers, and

delivers state change messages to the second router process in accordance with the order.

9. The router of claim 8, wherein the first router process:

provides a consumer pointer associated with the second router process that points into the data structure; and

traverses the data structure as a function of the consumer pointer.

10. The router of claim 8, wherein the first router process:

receives one of the event messages, the event message indicating a change of the state of one of the resources of the router;

determines whether to deliver the second router process a state change message that corresponds to the event message;

stores an indication within one of the objects that corresponds to the one of the resources as a function of the determination;

receives a request for the state information from the second router process;

determines whether the indication is present in the object; and

delivers the state change message to the second router process as a function of the determination.

11. The router of claim 8, wherein each of the plurality of objects of the data structure corresponds to a respective one of the plurality of resources of the router.

12. The router of claim 8, wherein the plurality of resources of the router comprise a plurality of forwarding engines of the router.

13. The router of claim 8, wherein the plurality of resources of the router comprises:

a plurality of interface cards of the router; and

for each of the plurality of interface cards, one or more logical interfaces,

wherein each of plurality of objects within the data structure is associated with a respective one of the interface cards and the logical interfaces, and

wherein the first router process sets the hierarchical pointers to link the objects in accordance with a hierarchy in which each of the interface cards is above its respective one or more logical interfaces.

14. The router of claim 8, wherein the second router process maintains a routing table.

15. A non-transitory computer-readable medium comprising instructions to cause a first router process executing on a processor of a router to:

receive event messages that indicate a change to state information, wherein the state information indicates the state of a plurality of resources of the router;

manage the state information within a temporally-linked and hierarchically ordered data structure, wherein the data structure comprises a plurality of objects that include hierarchical pointers and temporal pointers, and wherein the first router process;

stores the state information within the objects,

sets the hierarchical pointers to link the objects in accordance with a hierarchy representing relationships of the event messages, and

sets the temporal pointers to link the objects in accordance with an order in which the event messages are received; and

communicate the changes to the state information to a second router process executed by the processor according to the data structure, wherein the first router process;

traverses the data structure in an order determined in accordance with the hierarchical pointers and temporal pointers, and

delivers state change messages to the second router process in accordance with the order.

16. The non-transitory computer-readable medium of claim 15, wherein instructions comprise instructions that cause the first router process to:

provide a consumer pointer associated with the second router process that points into the data structure; and

traverse the data structure as a function of the consumer pointer.

17. The non-transitory computer-readable medium of claim 15, wherein the instructions comprise instructions that cause the first router process to:

receive one of the event messages, the event message indicating a change of the state of one of the resources of the router;

determine whether to deliver the second router process a state change message that corresponds to the event message;

store an indication within one of the objects that corresponds to the one of the resources as a function of the determination;

receive a request for the state information from the second router process;

determine whether the indication is present in the object; and

deliver the state change message to the second router process as a function of the determination.

18. The non-transitory computer-readable medium of claim 15, wherein the instructions that cause the first router process to receive event messages that indicate a change to state information, wherein the state information indicates the state of a plurality of resources of the router comprise instructions that cause the first router process to receive event messages that indicate a change to state information, wherein the state information indicates the state of a plurality of forwarding engines of the router.

19. The non-transitory computer-readable medium of claim 15, wherein the plurality of resources of the router comprises:

a plurality of interface cards of the router; and

for each of the plurality of interface cards, one or more logical interfaces,

wherein each of plurality of objects within the data structure is associated with a respective one of the interface cards and the logical interfaces, and

wherein instructions comprises instructions that cause the first router process to set the hierarchical pointers to link the objects in accordance with a hierarchy in which each of the interface cards is above its respective one or more logical interfaces.