Mechanism for efficiently synchronizing information over a network

Claim 2

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.

Claim 3

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.

Claim 4

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

Claim 5

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.

Claim 6

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.

Claim 7

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

Claim 8

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

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 14

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.

Claim 15

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

Claim 16

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.

Claim 17

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.

Claim 18

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.

Claim 19

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

Claim 20

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.

Claim 21

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.