US5086428A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Reliable broadcast of information in a wide area network
Assignee: Hewlett Packard Development Co LP
•
Filing: 1989-06-09
•
Granted: 1992-02-04
•
Expires: 2009-06-09
Abstract
Abstract A method and apparatus for creating and managing databases in routers of a routing network. The databases store link state packets, each packet being originated by nodes in the network, and transmitted to other nodes through the network. Each packet contains data identifying its originating node, a sequence number in a linear space indicating its place in the sequence of packets generated by its originating node, and an age value indicating the time remaining before it expires. The contents of the databases are updated by newly received packets. In addition, the nodes themselves are reset if the packets currently in the network have later sequence numbers than new packets. Also, a mechanism is provided to purge the databases of packets from a given router by issuing a purging packet.
Inventors
- 👤 Radia J. Perlman
- 👤 George Varghese
- 👤 Anthony G. Lauck
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 10:01
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/34; H04L45/00; H04L45/02; H04L45/03; H04L45/20; H04L47/28; H04L47/283; H04L69/00
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
122 words
A method for aging and purging from storage in each node of a distributed system of nodes, packets which expire over time, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising causing each node to regularly modify the data is each said packet stored therein to indicate that less time remains before each said packet expires than the time that remained before said data was modified, and causing each node, when a given packet has expired, to wait a purge time approximately equal to the time necessary for a packet to propagate through said distributed system, and then erase said given packet.
Claim 2
Independent Claim
122 words
A method for aging and purging from storage in each node of a distributed system of nodes, packets which expire over time, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising causing each node to regularly modify the data is each said packet stored therein to indicate that less time remains before each said packet expires than the time that remained before said data was modified, and causing each node, when a given packet has expired, to wait a purge time approximately equal to the time necessary for a packet to propagate through said distributed system, and then erase said given packet.
Claim 3
Dependent Claim
60 words
The method of claim 1 further comprising causing each node which receives a transmitted packet which has the same originating node, and the same sequence number, as a packet previously stored in the receiving node, where said transmitted packet includes data indicating said transmitted packet is expired, to modify said stored packet to indicate that said stored packet is expired.
Claim 4
Dependent Claim
49 words
The method of claim 2 further comprising causing each node which receives a transmitted packet to modify the data indicating the time remaining before said transmitted packet expires to indicate that less time remains before said transmitted packet expires than the time that remained before said data was modified.
Claim 5
Dependent Claim
26 words
The method of claim 2, wherein said nodes are routers, said distributed system of nodes is a routing network, and said packets are link state packets.
Claim 6
Dependent Claim
49 words
The method of claim 1 further comprising causing each node which receives a transmitted packet to modify the data indicating the time remaining before said transmitted packet expires to indicate that less time remains before said transmitted packet expires than the time that remained before said data was modified.
Claim 7
Dependent Claim
26 words
The method of claim 5, wherein said nodes are routers, said distributed system of nodes is a routing network, and said packets are link state packets.
Claim 8
Independent Claim
98 words
A method for purging, from storage in each node of a distributed system of nodes, packets originated from a given node, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising transmitting to at least one node of said system a purging packet, said purging packet identifying its originating node as said given node, having a sequence number latest in the sequence of packets originated from said given node, and including data indicating that said purging packet is expired.
Claim 9
Independent Claim
98 words
A method for purging, from storage in each node of a distributed system of nodes, packets originated from a given node, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising transmitting to at least one node of said system a purging packet, said purging packet identifying its originating node as said given node, having a sequence number latest in the sequence of packets originated from said given node, and including data indicating that said purging packet is expired.
Claim 10
Dependent Claim
26 words
The method of claim 7, wherein said nodes are routers, said distributed system of nodes is a routing network, and said packets are link state packets.
Claim 11
Dependent Claim
25 words
The method of claim 8, further comprising causing each node which originates a packet having the maximum sequence number to subsequently originate a purging packet.
Claim 12
Dependent Claim
24 words
The method of claim 8, further comprising causing each node which has originated packets which contain invalid information to subsequently originate a purging packet.
Claim 13
Dependent Claim
19 words
The method of claim 10, wherein said invalid information incorrectly indicates a designated router for a group of routers.
Claim 14
Dependent Claim
146 words
A controller circuit for maintaining a database storing link state packets, each said packet comprising a sequence number in a linear space, data identifying its originating controller circuit, and data indicating the time remaining until said packet expires, comprising communications circuitry connecting said controller circuit to at least another controller circuit for receiving transmitted packets and sending stored packets, and a computing circuit for managing said database, said computing circuit being programmed to: regularly modify the data in each said packet stored in said database to indicate that less time remains before each said packet expires than the time that remained before said data was modified, and when a given packet has expired, wait a purge time approximately equal to the time necessary for a packet to propagate to all other controller circuits which communicate packets to said controller circuit, and then erase said given packet.
Claim 15
Dependent Claim
146 words
A controller circuit for maintaining a database storing link state packets, each said packet comprising a sequence number in a linear space, data identifying its originating controller circuit, and data indicating the time remaining until said packet expires, comprising communications circuitry connecting said controller circuit to at least another controller circuit for receiving transmitted packets and sending stored packets, and a computing circuit for managing said database, said computing circuit being programmed to: regularly modify the data in each said packet stored in said database to indicate that less time remains before each said packet expires than the time that remained before said data was modified, and when a given packet has expired, wait a purge time approximately equal to the time necessary for a packet to propagate to all other controller circuits which communicate packets to said controller circuit, and then erase said given packet.
Claim 16
Dependent Claim
52 words
The controller circuit of claim 12, wherein said computing circuit is further programmed to modify a stored packet to indicate that it is expired if said transmitted packet has the same originating node as said stored packet and the same sequence number as said stored packet, and said transmitted packet is expired.
Claim 17
Dependent Claim
42 words
The controller circuit of claim 13, wherein said computing circuit is further programmed to modify each transmitted packet received by said router to indicate that less time remains before said packet expires than the time that remained before said data was modified.
Claim 18
Dependent Claim
126 words
A controller circuit for maintaining a database storing link state packets, each said packet comprising a sequence number in a linear space, data identifying its originating controller circuit, and data indicating the time remaining until said packet expires, comprising communications circuitry connecting said controller circuit to at least another controller circuit for receiving transmitted packets and sending stored packets, and a computing circuit for managing said database, said computing circuit being programmed to: purge said network of all packets originated by said controller circuit by transmitting a purging packet, said purging packet identifying its originating controller circuit as said controller circuit, having a sequence number latest in the sequence of packets originated from said controller circuit, and including data indicating that said purging packet is expired.
Claim 19
Dependent Claim
126 words
A controller circuit for maintaining a database storing link state packets, each said packet comprising a sequence number in a linear space, data identifying its originating controller circuit, and data indicating the time remaining until said packet expires, comprising communications circuitry connecting said controller circuit to at least another controller circuit for receiving transmitted packets and sending stored packets, and a computing circuit for managing said database, said computing circuit being programmed to: purge said network of all packets originated by said controller circuit by transmitting a purging packet, said purging packet identifying its originating controller circuit as said controller circuit, having a sequence number latest in the sequence of packets originated from said controller circuit, and including data indicating that said purging packet is expired.
Claim 20
Dependent Claim
32 words
The controller circuit of claim 15, wherein said computing circuit is further programmed to purge said network if said router originates a packet having the maximum sequence number in said linear space.
Claim 21
Dependent Claim
26 words
The controller circuit of claim 16, wherein said computing circuit is further programmed to purge said network if said router has originated packets containing invalid information.
Claim 22
Independent Claim
201 words
A method for aging and purging from storage in each node of a distributed system of nodes, packets which expire over time, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising causing each node to regularly modify the data in each said packet stored therein to indicate that less time remains before each said packet expires than the time that remained before said data was modified, causing each node which receives a transmitted packet to modify the data indicating the time remaining before said transmitted packet expires to indicate that less time remains before said transmitted packet expires than the time that remained before said data was modified, causing each node, when a packet has expired, to wait a given purge time and then erase the packet, and causing each node which receives a transmitted packet which has the same originating node, and the same sequence number, as a packet previously stored in the receiving node, where said transmitted packet includes data indicating said transmitted packet is expired, to modify said stored packet to indicate that said stored packet is expired.
Claim 23
Independent Claim
201 words
A method for aging and purging from storage in each node of a distributed system of nodes, packets which expire over time, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising causing each node to regularly modify the data in each said packet stored therein to indicate that less time remains before each said packet expires than the time that remained before said data was modified, causing each node which receives a transmitted packet to modify the data indicating the time remaining before said transmitted packet expires to indicate that less time remains before said transmitted packet expires than the time that remained before said data was modified, causing each node, when a packet has expired, to wait a given purge time and then erase the packet, and causing each node which receives a transmitted packet which has the same originating node, and the same sequence number, as a packet previously stored in the receiving node, where said transmitted packet includes data indicating said transmitted packet is expired, to modify said stored packet to indicate that said stored packet is expired.
Claim 24
Independent Claim
150 words
A method for aging and purging from storage in each node of a distributed system of nodes, packets which expire over time, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising causing each node to regularly modify the data in each said packet stored therein to indicate that less time remains before each said packet expires than the time that remained before said data was modified, transmitting to at least one node of said system a purging packet, said purging packet identifying its originating node, having a sequence number latest in the sequence of packets originated from said originating node, and including data indicating that said purging packet is expired, and causing each node, when a packet has expired, to wait a given purge time and then erase the packet.
Claim 25
Independent Claim
150 words
A method for aging and purging from storage in each node of a distributed system of nodes, packets which expire over time, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising causing each node to regularly modify the data in each said packet stored therein to indicate that less time remains before each said packet expires than the time that remained before said data was modified, transmitting to at least one node of said system a purging packet, said purging packet identifying its originating node, having a sequence number latest in the sequence of packets originated from said originating node, and including data indicating that said purging packet is expired, and causing each node, when a packet has expired, to wait a given purge time and then erase the packet.
Claim 26
Independent Claim
119 words
A method for purging from storage in each node of a distributed system of nodes, packets originated from a given node, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising causing each node which has originated a packet having the maximum sequence number or which contains invalid information to subsequently originate a purging packet, said purging packet identifying its originating node, having a sequence number latest in the sequence of packets originated from said originating node, and including data indicating that said purging packet is expired, and transmitting said purging packet to at least one node of said system.
Claim 27
Independent Claim
119 words
A method for purging from storage in each node of a distributed system of nodes, packets originated from a given node, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising causing each node which has originated a packet having the maximum sequence number or which contains invalid information to subsequently originate a purging packet, said purging packet identifying its originating node, having a sequence number latest in the sequence of packets originated from said originating node, and including data indicating that said purging packet is expired, and transmitting said purging packet to at least one node of said system.
Claim 28
Independent Claim
152 words
A method for aging and purging from storage in each node of a distributed system of nodes, packets which expire over time, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising causing each node to regularly modify the data in each said packet stored therein to indicate that less time remains before each said packet expires than the time that remained before said data was modified, causing each node to erase from storage any packet which has expired, and causing each node which receives a transmitted packet which has the same originating node, and the same sequence number, as a packet previously stored in the receiving node, where said transmitted packet includes data indicating said transmitted packet is expired, to modify said stored packet to indicate that said stored packet is expired.
Claim 29
Independent Claim
152 words
A method for aging and purging from storage in each node of a distributed system of nodes, packets which expire over time, each said packet comprising a sequence number in a linear space, data identifying its originating node, and data indicating the time remaining until said packet expires, the method comprising causing each node to regularly modify the data in each said packet stored therein to indicate that less time remains before each said packet expires than the time that remained before said data was modified, causing each node to erase from storage any packet which has expired, and causing each node which receives a transmitted packet which has the same originating node, and the same sequence number, as a packet previously stored in the receiving node, where said transmitted packet includes data indicating said transmitted packet is expired, to modify said stored packet to indicate that said stored packet is expired.
References Cited (Backward Citations)
US4466060A
Cited
US4534024A
Cited
US4607363A
Cited
US4617657A
Cited
US4742511A
Cited
US4706080A
Cited
US4825206A
Cited
US4679189A
Cited
US4740954A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-02-03 | 1995-08-05 | 1996-02-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-02-03 | 1999-08-05 | 2000-02-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-02-03 | 2003-08-05 | 2004-02-04 | $7700.00 | Window Closed / Lapsed |