# US 2002/0165981 A1 · Method and apparatus for establishing and sharing a virtual change notification list among a plurality of peer nodes

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2002/0165981 A1
- Document ID: US20020165981A1
- Status: Published application
- Kind: A1
- Application number: 10/104,884
- Filed: 2002-03-21
- Published: 2002-11-07
- Earliest claimed: 2000-06-28
- Assignees: Pluris, Inc.
- Inventors: Erol Basturk; Vivek Menezes
- Web page: https://patentgrep.com/patent/US20020165981A1

## CPC

- H04L 45/58: Association of routers
- G06F 9/542: {Event management; Broadcasting; Multicasting; Notifications}
- G06F 9/546: {Message passing systems or structures, e.g. queues}
- H04L 12/1854: {with non-centralised forwarding system, e.g. chaincast}
- H04L 45/028: Dynamic adaptation of the update intervals, e.g. event-triggered updates
- H04L 45/54: {Organization of routing tables}
- H04L 45/56: {Routing software}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 1

A data structure 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 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.

### Claim 2 (depends on 1)

The data structure 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.

### Claim 3 (depends on 2)

The data structure 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.

### Claim 4 (depends on 1)

The data structure of claim 1 wherein each event object comprises a reference to the next event object in the list.

### Claim 5 (depends on 1)

The data structure 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.

### Claim 6 (depends on 1)

The data structure 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.

### Claim 7

In a data router, a virtual output queue system for propagating route change notifications to individual ones of a finite set of peer routers, the system comprising:
a virtual output queue (VOQ);
a facility for entering and deleting change notifications as event objects in the VOQ; and
an access module for managing access to the queue on behalf of individual ones of the finite set of peer routers, the access module retrieving event objects from the queue and sending the event objects to the router for which access is made.

### Claim 8 (depends on 7)

The system of claim 7 wherein the event objects are each associated with a first reference number indicating the number of peers currently accessing the event object, and, as each peer 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 queue, indicating that all consumers have accessed the event object, that event object is removed from the queue.

### Claim 9 (depends on 7)

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

### Claim 10 (depends on 7)

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

### Claim 11 (depends on 7)

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

### Claim 12

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.

### Claim 13 (depends on 12)

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

### Claim 14 (depends on 13)

The method of claim 13 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.

### Claim 15 (depends on 12)

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

### Claim 16 (depends on 12)

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

### Claim 17 (depends on 12)

The method of claim 12 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.

### Claim 18

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.

### Claim 19 (depends on 18)

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

### Claim 20 (depends on 18)

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

### Claim 21 (depends on 18)

The method of claim 18 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.

### Claim 22

In a multiple-processor data router, a virtual output queue system for propagating route change notifications to individual ones of a finite set of processor-controlled nodes within the router, the system comprising:
a virtual output queue (VOQ);
a facility for entering and deleting change notifications as event objects in the VOQ; and
an access module for managing access to the queue on behalf of individual ones of the finite set of nodes within the router, the access module retrieving event objects from the queue and sending the event objects to the node for which access is made.

### Claim 23 (depends on 22)

The system of claim 22 wherein the event objects are each associated with a first reference number indicating the number of nodes currently accessing the event object, and in that, as each node 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 queue, indicating that all nodes have accessed the event object, that event object is removed from the queue.

### Claim 24 (depends on 22)

The system of claim 22 wherein each event object comprises a reference to the next event object in the queue.

### Claim 25 (depends on 22)

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

### Claim 26 (depends on 22)

The system of claim 22 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.

### Claim 27

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.

### Claim 28 (depends on 27)

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

### Claim 29 (depends on 27)

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

### Claim 30 (depends on 27)

The method of claim 27 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.
