Reliable broadcast of information in a wide area network

• US 5,086,428 A
• Filed: 06/09/1989
• Issued: 02/04/1992
• Est. Priority Date: 06/09/1989
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Perlman, Radia J., Varghese, George, Lauck, Anthony G.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Ton, Dang
• Application Number:
  US07/364,470
• Time in Patent Office: 970 Days
• Field of Search: 370/94.1, 370/60, 370/61, 370/44.1, 340/825.05
• US Class Current: 370/394
• 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/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 69/00 Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass networks security protocols H04L9/40; wireless communication networks H04W

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.

Claims

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

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

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

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

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

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

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

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

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

10. The method of claim 8, further comprising

causing each node which has originated packets which contain invalid information to subsequently originate a purging packet.

11. The method of claim 10, wherein said invalid information incorrectly indicates a designated router for a group of routers.

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

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

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

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

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

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

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

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

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

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