Method and apparatus for establishing and sharing a virtual change notification list among a plurality of peer nodes

• US 6,938,095 B2
• Filed: 03/21/2002
• Issued: 08/30/2005
• Est. Priority Date: 06/28/2000
• Status: Expired due to Term

• Current Assignee: Parity Networks LLC
• Original Assignee: Pluris, Inc
• Inventors: Basturk, Erol, Menezes, Vivek
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): NGUYEN, THU HA T
• Application Number:
  US10/104,884
• Publication Number:
  US 20020165981A1
• Time in Patent Office: 1,258 Days
• Field of Search: 709/201, 709/224, 709/238, 709/239, 709/242, 705/9, 370/351, 370/395.31, 710/10, 710/15, 710/220, 710/62, 710/65, 710/72
• US Class Current: 709/238
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/56 Routing software
• CPC Class Codes: H04L 45/58 Association of routers

Abstract

A data structure has a list of event objects, one or more producers creating the event objects for the list, and a finite set of consumers accessing the object list. The structure is characterized in that the event objects are each associated with a first reference number indicating the number of consumers currently accessing the event object, and in that, as each consumer completes access the reference number is decremented, and when the reference number for an event object is zero, and the event object is at the head of the list, indicating that all consumers have accessed the object, that event object is removed from the list. A use of the structure for propagating route changes to nodes in a multiple-processor router, and to peer routers in a network is also taught.

Claims

1. A data routing software structure on a computer comprising:

a list of event objects;

one or more producers creating the event objects for the list; and

a finite set of consumers accessing the object list;

characterized in that the event objects are each associated with a reference number indicating a number of the consumers currently accessing the event object, and in that, as each consumer completes access the reference number is decremented, and when the reference number for an event object is zero, and the event object is at the head of the list, indicating that all consumers have accessed the object, that event object is removed from the list.

2. The data routing software structure on the computer of claim 1 wherein the event objects created represent changes in a data base, and the information associated with each is a statement of the change.

3. The data routing software structure on the computer of claim 2 wherein the data base is a routing information base for a portion of a data packet network, and the information associated with each event object is a route change.

4. The data routing software structure on the computer of claim 1 wherein each event object comprises a reference to the next event object in the list.

5. The data routing software structure on the computer of claim 1 wherein each event object comprises a reference to the next event to be processed by a consumer processing a current event object.

6. The data routing software structure on the computer of claim 1 having a second reference number associated with each event object, initially indicating the number of consumers to access the event object, the number decremented as each consumer accesses the event object.

7. A method for propagating event objects to a finite set of consumers, comprising the steps of:

(a) placing the event objects one-at-a-time in a first-in-first-out queue;

(b) associating a number with each specific event object in the list, the number indicating the number of consumers in the set currently accessing the specific event object; and

(c) decrementing the number associated in step (b) with each event object by one each time a consumer finishes access to that event object, such that, when the number is zero for an event object, and the event object is at the head of the queue, that object has been accessed for all consumers requiring access, and may be removed from the queue.

8. The method of claim 7 wherein the event objects created represent changes in a data base, and the information associated with each is a statement of the change.

9. The method of claim 8 wherein the data base is a routing information base for a portion of a data packet network, and the information associated with each event object is a route change.

10. The method of claim 7 wherein each event object comprises a reference to the next event object in the queue.

11. The method of claim 7 wherein each event object comprises a reference to the next event to be processed by a consumer processing a current event object.

12. The method of claim 7 having a second reference number associated with each event object, initially indicating the number of consumers to access the event object, the number decremented as each consumer accesses the event object.

13. A method for propagating route changes to a finite set of peer routers, comprising the steps of:

(a) placing the route changes as event objects one-at-a-time in a first-in-first-out queue;

(b) associating a number with each specific event object in the queue, the number indicating the number of peers in the set currently accessing the specific event object; and

(c) decrementing the number associated in step (b) with each event object by one each time a peer finishes access to that event object, such that, when the number is zero for an event object, and the event object is at the head of the queue, that object has been accessed for all peers requiring access, and may be removed from the queue.

14. The method of claim 13 wherein each event object comprises a reference to the next event object in the queue.

15. The method of claim 13 wherein each event object comprises a reference to the next event to be processed by a peer processing a current event object.

16. The method of claim 13 having a second reference number associated with each event object, initially indicating the number of peers to access the event object, the number decremented as each peer accesses the event object.

17. A method for propagating route changes to a finite set of processor-controlled peer nodes in a multiple-processor router, comprising the steps of:

(a) placing the route changes as event objects one-at-a-time in a first-in-first-out queue;

(b) associating a number with each specific event object in the queue, the number indicating the number of nodes in the set currently accessing the specific event object; and

(c) decrementing the number associated in step (b) with each event object by one each time a node finishes access to that event object, such that, when the number is zero for an event object, and the event object is at the head of the queue, that object has been accessed for all nodes requiring access, and may be removed from the queue.

18. The method of claim 17 wherein each event object comprises a reference to the next event object in the queue.

19. The method of claim 17 wherein each event object comprises a reference to the next event to be processed by a node processing a current event object.

20. The method of claim 17 having a second reference number associated with each event object, initially indicating the number of nodes to access the event object, the number decremented as each node accesses the event object.