Mechanism for efficiently synchronizing information over a network

• US 5,742,820 A
• Filed: 07/06/1995
• Issued: 04/21/1998
• Est. Priority Date: 07/06/1995
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Perlman, Radia J., Castagnoli, Neal D.
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US08/499,029
• Time in Patent Office: 1,020 Days
• Field of Search: 395/610, 395/617, 395/200.03, 395/200.09
• US Class Current: 707/610
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols

Abstract

A novel mechanism efficiently synchronizes the contents of databases stored on nodes of a computer network to-ensure that those contents are consistent. The mechanism comprises a database identifier generated by a node of the computer network and distributed to other receiving nodes coupled to the network. The database identifier is uniquely representative of the contents of the distributing node'"'"'s database and the receiving nodes compare this unique identifier with their own generated database identifiers to determine if the identifiers, and thus their databases, are consistent and synchronized.

Claims

1. A mechanism for efficiently synchronizing the contents of databases stored on nodes of a computer network, the mechanism comprising:

a database identifier generated by each node of the computer network from the contents of a database associated with each node;

node distribution means for distributing a database identifier to a receiving node of the network; and

node comparison means for comparing a database identifier with the distributed database identifier to determine if the identifiers, and thus the databases, are synchronized.

2. The mechanism of claim 1 wherein the database identifier is uniquely representative of a complete sequence numbers packet pertaining to the contents of a link state packet database of the distributing node.

3. The mechanism of claim 2 wherein the nodes are routers and wherein the distributing node is a designated router.

4. The mechanism of claim 1 wherein the database identifier is generated by a technique for producing a fixed length value whose contents are unique with high probability and whose contents are further substantially less than those of the database.

5. The mechanism of claim 4 wherein the technique comprises a cryptographic message digest algorithm configured to transform the contents of the database into a unique, fixed-length digest.

6. The mechanism of claim 4 wherein the technique comprises cyclic redundancy checking.

7. The mechanism of claim 4 wherein the technique comprises sequence number generation.

8. An arrangement for efficiently synchronizing the contents of databases stored on routers of a computer network, the arrangement comprising:

a designated router coupled to the network and configured to generate a first database identifier from the contents of a first database associated with the designated router, the first database identifier uniquely representative of the contents of the first database; and

at least one other router of the network configured to generate a second database identifier from the contents of a second database associated with the other router, the second database identifier uniquely representative of the contents of the second database,

wherein the designated router periodically distributes the first database identifier to the other router which compares the first database identifier with the second database identifier to determine whether the database identifiers, and thus the first and second databases, are consistent.

9. The arrangement of claim 8 wherein the database identifiers are uniquely representative of complete sequence numbers packets (CSNP) pertaining to the contents of link state packet databases and wherein the designated router generates the first database identifier from the CSNP and periodically broadcasts the first database identifier, rather than the CSNP itself, to the other router.

10. A method for efficiently synchronizing the contents of databases stored on nodes of a computer network, the method comprising the steps of:

generating a first database identifer from the contents of a first database associated with a designated node coupled to the network, the first database identifier uniquely representative of the contents of the first database;

calculating second database identifiers from the contents of second databases associated with a plurality of other routers coupled to the network, the second database identifiers uniquely representative of the contents of the second databases;

periodically broadcasting the first database identifier to the other routers over the network; and

processing the first database identifier at the other routers to determine whether there are any discrepancies between the first and second databases.

11. The method of claim 10 wherein the step of generating comprises the step of generating the first database identifier that is uniquely representative of a complete sequence numbers packet (CSNP) pertaining to the contents of a link state packet database associated with the designated router.

12. The method of claim 11 wherein the step of processing comprises the step of comparing the second database identifier with the first database identifier.

13. The method of claim 12 wherein the step of comparing comprises the step of, if the second database identifier matches the first database identifier, storing the first database identifier at the other routers.

14. The method of claim 12 wherein the step of comparing comprises the step of, if the second database identifier does not match the first database identifier, requesting the CSNP from the designated router.

15. The method of claim 11 further comprising the steps of:

generating third database identifiers, each of which is uniquely representative of a fragment of the CSNP pertaining to the contents of a LSP database associated with the designated router; and

calculating fourth database identifiers, each of which is uniquely representative of a fragment of the CSNP pertaining to the contents of a LSP database associated with each other router.

16. The method of claim 15 wherein the step of processing comprises the step of comparing the second database identifier with the first database identifier.

17. The method of claim 16 wherein the step of comparing comprises the step of, if the second database identifier matches the first database identifier, storing the first database identifier at the other routers.

18. The method of claim 16 wherein the step of comparing comprises the step of, if the second database identifier does not match the first database identifier, comparing a particular third database identifier with a corresponding fourth database identifier to resolve any discrepancies.