IIIIIIIIHIIIIIIIIIIIIIIII
`[18005742820A
`
`[19;
`United States Patent
`[11} Patent Number:
`5,742,820
`
`[45] Date of Patent: Apr. 21, 1998
`Perlman et a1.
`
`
`
`[54]
`
`[75]
`
`[73]
`
`[21]
`
`['21]
`
`[51]
`[52]
`
`[53]
`
`[55]
`
`MECHANISM FOR EFFICIENTLY
`SYNCHRON'IZIING INFORMATION OVER A
`NETWORK
`
`Inventors: Radix .1. Pullman. Acton. Mass; Neal
`D. Castagnoli. Morgan Hill. Califi
`
`Assignee: Novell, Inc. Orem. Utah
`
`App]. No; 499,029
`Filed:
`Jul. 6. 1995
`
`Int. Cl.“ ..................................................... GM]? 17130
`[1.5. CI. ..
`.
`3951617139516l0: 395000.03:
`
`3951200.09
`3951610. 611'.
`395R00.D3. 200.09
`
`Field of Search
`
`References Cited
`
`US. Pm’ DOCUMENTS
`
`
`31951600
`'HI992 Tirfling elal. .................
`5,129,032
`395nm
`9.1993 Dauuet ..........
`5249263
`
`.. “0.160
`5265.092 ””993 Suflaway er a].
`
`[”994 Howard: .........
`393W
`5.2?6.8?i
`5.280.498
`“”94 Twat ill.
`3T5”
`
`[3:995 Squibb ,H 395mm
`5.419.554
`FOREIGN PATENT DOCUMENTS
`
`0 348 331 12”ng Elm PaL 03..
`0443' T25 A2
`9fl991
`European Pat. OE.
`.
`
`OTHER PLIBUCATIONS
`
`Ramabadran er at. "A Tutor-in] on CRC Computations".
`IEEE Micro. vol. 8. No. 4. Aug. 1988. pp. 6245.
`
`Radia Perlman. Intercunnections Bridges and Routers. Add-
`Eon-Wesleyr Professional Computing Series. Jul. 1992. pp.
`242—245 and 212-275.
`
`Computer Communications Review. 21 (1991} Ian. No. I.
`New York. US. Inter Domain Policy Routing: Overview of
`Architecture and Protocols. Deborah Estin et 31.. pp. 71-79.
`
`Primry Examiner—Paul R. Lint:
`Ammc}; Agent. or Firm—Cesnri and McKennn
`
`[57]
`
`ABSTRACT
`
`A novel mechanism elfieiently 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 representa—
`tive of the contents of the dislfibuting node‘s database and
`the receiving nodes compare this unique identifiu with their
`own generated database identifiers to determine if the
`identifiers. and thus their databases. are consistent and
`synchronized.
`
`18 Claims, IS Drawing Sheets
`
`
`
`
`HELLO MESSAGE
`
`OFIIGINATOFI
`
`
`
`
`
` LOW-LEVEL IDENTIFIER c 72§
`
`HIGH-LEVEL IDENTIFIER 7_Q1
`
`LOW-LEVEL IDENTIFIER 3 125a
`
`LOW-LEVEL IDENTIFIER b 7251:
`
`c
`
`E 700
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 1 of 12
`Page 1 of 12
`
`IPR2012-00026
`EXHIBIT 1003
`IPR2013-00109
`
`MICROSOFT
`MICROSOFT
`Dem. EX. 103 1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`

`

`

`

`

`

`US. Patent
`
`Apr. 21, 1993
`
`Sheet 4 of 6
`
`5,742,820
`
`ADDRESS RANGE
`
`aa -CC— r545“
`SEQUENCE NUMBERS
`
`
`data items
`
`
`
`ADDRESS RANGE
`
`dd - ff 5 450b
`
`
`
`data items
`
`SEQUENCE NUMBERS
`
`ADDRESS RANGE
`
`data items
`
`SEQUENCE NUMBERS
`
`4500
`xx - 22 5
`
`FIG. 48
`
`Page 5 of 12
`Page 5 of 12
`
`

`

`US. Patent
`
`Apr. 21, 1993
`
`Sheet 5 of 6
`
`5,742,820
`
`
`
`620C:
`
`
`
`
`
`
`
`LOW-LEVEL IDENTIFIER 6259
`
`FIG. BB
`
`Page 6 of 12
`Page 6 of 12
`
`

`

`US. Patent
`
`Apr. 21, 1998
`
`Sheet 6 of 6
`
`5,742,820
`
`E 700
`
`HELLO MESSAGE
`
`OR IGI NATOH
`
`
`
`
`
`
`
`
`
`
`
`HIGH-LEVEL IDENTIFIER Z__Q1
`
`LOW-LEVEL IDENTIFIER a 1253
`
`LOW-LEVEL IDENTIFIER b 725b
`
`LOW-LEVEL IDENTIFIER c Zgiq
`
`FIG. 7
`
`Page 7 of 12
`Page 7 of 12
`
`

`

`5.742. 820
`
`l
`MECHANISM FOR EFFICIENTLY
`SYNCHRONIZING INFORMATION OVER A
`NETWORK
`
`FIELD OF THE INVENTION
`
`It)
`
`15
`
`35
`
`45
`
`SS
`
`This invention relates generally to computer networks
`and. more particularly. to efficient synchronization of infor-
`mation across a computer network
`BACKGROUND OF THE INVENTION
`
`A computer network. is a geographically distributed col-
`lection of interconnected communication links for transport-
`ing data between nodes. such as computers. A plurality of
`computer networks may be timber interconnected by inter-
`mediate nodes. or routers to extend the efiective "size" of
`the networks. Many types of computer networks are
`available. with the types ranging from local area networks
`(LANs) to wide area networks. A LAN. for example. is a
`limited area network that typically consists ofa transmission
`medium. such as coaxial cable or twisted pair. for intercon-
`necting nodes. These nodes typically communicate by
`exchanging discrete “packets" of data according to tie—
`defined protocols. In this context. a protocol consists of a set
`of rules defining how flte nodes interact with each other.
`In order to reduce design complexity. most networks are
`unsuited as a series of hardware and software levels or
`“layers" within each node. These layers Internet to format
`data for transfer between. e.g.. a source node and a desti-
`nation node communicating over the network. Specifically.
`predetermined sertdoes are preformed on the data as it
`passes through each layer and the layers communicate with
`each other by means of the predefined protocols. This
`layered design permits each layer to offer selected services
`to other layers using a standardized interface that shields
`those layers from the details of actual implementation of the
`services.
`In an anempt to standardize network architecnrres. Le.
`the sets of layers 1:! protocols used within a network. a
`generalized model has been proposed by the International
`Standards Organization (130}. The model. called the Open
`Systems Interconnection (05]) reference modeL is directed
`to the interconnection of systems that are "open" for com-
`munication with other systems. The proposed 051 model has
`seven layers which are tenured.
`in ascending interfacing
`order. the pltysiml. data link. network. transport. session.
`presentation. and application layers. These layers are
`arranged to form a ‘protocol stack" in eadt node of the
`network.
`
`FIG. 1 illustrates a sdteinatic block diagram of prior art
`protocol stacks 115 and 1‘75 used to transmit darn between
`a source node 110 and a destination node 150. respectively.
`of a computer network 100. Each protocol stack is manned
`according to the OS! seven-layer model: accordingly. each
`stack comprises a collection of protocols. one per layer. As
`can be seen. the protocol stacks 125 and 175 are physically
`connected tirrough a communications channel 100 at the
`physical layers [14 and 164. For ease of description. the
`protocol stock 125 will be described.
`Broadly stated. the physical layer 124 transmits a raw data
`bit stream over a communication channel ran. while the data
`link layer 122 manipulates the bit steam and transforms it
`into a datastream that appears free of transmission more
`This latter task is accomplished by dividing the transmitted
`data into frames and transmitting the frames sequentially.
`accompanied with error correcting mechanisms for detect-
`ing or correcting errors. The network layer 120 routes data
`
`2
`packets from the solace node to the destination node by
`selecting one of many alternative paths through the physical
`network. The transport layer 118 accepts the datastream
`from the session layer 116. apportions it into smaller units (if
`necessary]. passes the smaller units to the network laya 128
`and provides appropriate mechanisms to ensure that all the
`units arrive correctly at the destination.
`The session layer 116 establishes data transfer “sessions"
`bettveen software princesses on the source and destination
`nodes. along with management of such sessions in an
`orderly fashion. That is. a session not only allows ordinary
`data transport between the nodes. but
`it also povides
`enhanced «wines in some applications. The [resentation
`layer 114 performs fienuenllyqoquested functions relating
`to the presentation of transmitted data. including encoding
`of data into standard formats. while the application layer 112
`contains a variety of protocols that are commonly needed by
`processes executing on the nodes.
`Data transmission over the network 100 therefore consists
`of generating data in. e.g.. a sending process 104 executing
`on the source node 11.. passing that data to the application
`layer 113 and dowa tltrough the layers of the protocol stack
`125. where the data are sequentially fca'mattcd as a packet
`for delivery onto the channel 130 as bits. 'I'hose packet bits
`are then transmitted to the protocol stack 175 of the desti-
`nation node 150. W‘hfl'fl they are passed up that stack to a
`receiving moose 174. Data flow is schematically illustrated
`by solid arrows.
`Although actual data transmission occurs vertically
`through the stackseach layeris programmed asthough such
`transmission were horizontal. That is. each layer in the
`sotn'ec node 100 is programmed to transmit data to its
`corresponding layer in the destination node 150. as sche»
`matically shown by dotted arrows. To achieve this effect.
`each layer of the protocol stack 125 in the solace node 110
`typically adds information (in the form of a header field} to
`the data packet generated by the sending process as the
`packet descends the slack. At the destination node 150. the
`various headers are stripped of onc-by—one as the packet
`propagates up the layers of stack 115 until it arrives at the
`receiving process.
`As noted. a significant function of each layer in the 081
`model is to provide services to the other layers. 'Dwo types
`of services ofiered by the layers are “connection-oriented"
`and “cooneettonless” network servlces. In a connection-
`oriented service. the source node establishes a connection
`with a destination node and. after sending a packet. terrai-
`nates the connection. The overhead associated with estab-
`lishing the connection may be unattractive for nodes requir—
`ing eliicicnt communication performance. For this case. a
`fully connectionless service is desirable where each trans-
`mitted packet carries the full address of its destination
`though the network.
`The connectionless aetwcxk serfioe is generally imple-
`mented by a network layer protocol. an aspect of which
`involves the routing of packets from the source node to the
`destination node. In particular. this aspect of the network
`layer concerns the algorithms and protocols used by renters
`when cooperating to calculate paths through a network
`topology. Arouting algorithm is that portion of the network
`layer software responsible for determining an output com—
`munication link over which an incoming packet should be
`o'anstnined; a popular type of network layer rou ting protocol
`is a link state routing protocol.
`According to this protocol. each router constructs a link
`slate packet (LSPJ comprising information. such as a list of
`
`Page 8 of 12
`Page 8 of 12
`
`

`

`5 342.820
`
`3
`to
`"neighboring" nodes adjacent to the router. sufiicient
`generate a complete map ofthe topology of the moved. The
`LSP is then forwarded to all other routers of the network.
`2.3.. a plurality of interconnectedLANs. Each of mess Odter
`routers stores only the most recently received [SP from the
`forwarding router in its 1.5? database. Armed with updated
`maps. these otherrouters may compute routes to destination
`nodes. An example of a distributed link state routing pro-
`tocol
`is the intermediate system to intermediate system
`(IS-IS) protocol defined by 150.
`Since the computed routes are dependent upon the infor~
`mation stored in the LSP databases of the routers. it
`is
`essential that
`these databases are synchronized to ensure
`their contents are consistent and coherent. A known tech—
`nique for closely synchronizing LSP databases is to have one
`node periodically summarize the state of its database.
`According to this technique. which is implemented by the
`IS-—IS protocol. a single router on each LAN of the network
`is elected a designated router (DR) and the DR periodically
`transmits a complete sequence numbers packet (CSN'P) to
`all other routers on the LAN. The CSNP consists of iden-
`tifications of all LSP data items in the database. along with
`sequence numbers for these items. The routers that receive
`the CSNI’ compare it with the contents of their databases to
`determine whether their information is current.
`For example. if the sequence number of an LSP listed in
`the CSNP is greater. i.c.. more recent. than the sequence
`number for that L5? stored in the database of a receiving
`router. that router may request the more recent information
`pertaining to the LSP from the DR. 0n the other hand. if an
`ISP stored in the database of a receiving router has a
`sequence number that is greater than the sequence number
`for that LSP listed in the CSNP. the DR has transmitted
`"stale“ information regarding that 1.8!". In response to this
`discovery. the receiving router transmits the more recent
`information associated with the L5? to the DR. which
`updates its database. Of course. if the contents of the CSNP
`are consistent with the contents of the receiving routers
`databases. no further action is required.
`In order to characterize an entire LSP database. the (‘51th
`may be very large. thereby requiring apportionment of the
`CSN'P into smaller packet fragments for transmission over
`the W5. Each packet fragment characterizes a contiguous
`portion of the database and each is processed independently
`by the receiving renters: this enables comparison of the
`CSNP items with each item of each romer‘s 1.8? database.
`over the W5 consumes significant bandwidth while pro
`cessing oft he additional individual packets consumes sub
`stanlial mounts of computational resumes in the routers.
`Therefore. it is among the objects of the present invention
`to reduce the bandwidth consumed by transmission of
`database summary information packets over a computer
`network.
`Another object of the present invention is to minimize
`computational resources within routers needed to process
`received database summary information packets.
`SLMMARY OF THE INVENTION
`
`10
`
`15
`
`25
`
`35
`
`45
`
`e invention comprises a race msm or -‘ctenly
`synchronizing the contents of databases stored on nodes of
`a computer network to ensure that those contents are con-
`sistent. Generally. the mechanism comprises a database
`identifier generated by a node of the computer netwmk and
`distributed to other receiving nodes coupled to the network.
`The database identifiu is uniquely representative of the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ing nodes compare this unique identifier with their own
`generated database identifiers to determine if the identifiers
`and thus their databases. are consistent and synchronized.
`In the illustrative embodiment desm'bed herein. the iden-
`tifier is uniquely representative of a complete sequence
`numbers packet (CSNP) pertaining to the contents of a link
`state packet (LSP) database of the distributing node. eg. a
`designated router. Specifically. the designated router gener-
`ates the database identifla from the entire CSN'P and pct-L
`odically la‘oadcasts that
`identifier. rather than the CSN‘P
`itself. to the receiving nodes. Le. routers. on the network.
`finch as a local area network (LAN). The database identifier
`is preferably generated from a cryptographic message digest
`algorithm configured to transform the contents of the CSNP
`into a unique. fixed—length digest "signature“ whose con—
`tents are substantially less than those of the CSNP:
`accordingly. h'ansmission of the database identifier in lieu of
`the C514? optimizes both the use of computational resources
`within the receiving routers and bandwidth on the LAN.
`Upon receiving the database identifier. the routers process
`that identifier to determine whether any discrepancies arise
`and if so. those routers may request copies of the entire
`CSN'F. That is. each receiving router initially calculates an
`identifier based on the contents of its [SP database and then
`compares the calculated identifier with the database identi-
`fier received from the designated router. A receiving router
`whose calculated database identifier conforms to the
`received database identifier need only store that latter iden-
`Lifter of the CSNP. 1f the calarlnted identifier is difierent. the
`receiving router may request the CSNP to resolve any
`dilIerences in its database. Significantly.
`the designated
`router transmits the mental CSN'P only in response to a
`change in the database or a request from another router.
`in the event a plurality of smaller packet fragments are
`needed for transmitting the CSN’P over the LAN. the des-
`ignated router preferably computes an identifier for each
`CSNP fragment. In an alternate embodiment of the
`invention. a hierarchical arrangement provides a single.
`higislevel database identifier for the entire CSN'P and a
`plurality of Iow~level database identifiers for these indi—
`vidual CSNP fragments. Here. the high-level identifier is
`periodically broadcast by the designated router and if a
`discrepancy is found at a particular router. that router may
`request a list of the low-level identifiers in order to isolate
`the discrepancy in the database.
`the hierarchical
`In a related alternate embodiment.
`arrangement is modified to provide a tWo~stage operation
`arrangement at the receiving routers. Specifically. the high-
`level and low-level identifiers are bundled within a “hello"
`message Ihat is periodically broadcast by the designated
`router to the receiving routers. According to the first opera-
`tiou stage. each receiving router calmlatcs an identifier-
`based on the entirety of its database. compares that identifier-
`with the received higb~level identifitn' and. if they match.
`ignores the remaindu' of the message. On the other hand. if
`the identifiers are dissimilar. the receiving router proceeds to
`the second stage. which specifies computing identifiers for
`particular fragments of the database. These latter identifiers
`are thereafter compared with the appropriate low-level iden—
`tifiers to identify the inconsistent database fragments.
`Advantageously.
`the inventive embodiments described
`above do not require extensive use of computational
`resources in the receiving routers unless there are inconsis—
`tencies in the databases. In other words.
`the invenlion
`conserves proeessing resources by potentially eliminating
`
`Page 9 of 12
`Page 9 of 12
`
`
`
`%
`
`!
`
`
`
`
`
`
`
`
`
`
`
`
`$
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`bandwidth
`
`Solution
`
`reduces
`
`usage
`
`
`
`"
`
`
`
`
`
`
`
`
`#
`
`
`
`
`
`#
`!
`
`
`
`
`
`
`
`
`
`
`&
`
`
`
`
`
`

`

`5.742.820
`
`5
`the need to labor through identifier calculations and com-
`pm‘isons for each database fragment. Moreover.
`these
`approaches are flexible in that the number of hierarchical
`layers. database fragments and low-leVel
`identifiers are
`selectable.
`
`BRIEF DESCRIPTION OF THE DRAWGS
`
`The above and further advantages of the invention may be
`hertz understood by referring to tire following description in
`conjunction with the accompanying drawings. in which like
`references indicate similar elements. and in which:
`FIG. 1 is a schematic block diagram of Prior art protocol
`stacks used to transmit data between nodes of a computer
`network:
`FIG. 2 is a block diagram of a network system including
`a collection of computer nerwcrks connected to a plurality of
`nodes:
`FIG. 3 is a schematic diagram of a conventional link state
`packet {LSP} used in accordance with a network layer
`routing protocol:
`FIGS.
`that—48 are schematic diagrams of complete
`sequence nurrtbers packets used in accordance with a net-
`work layer protocol:
`FIG. 5 is a schematic diagram illustrating an illustrative
`embodiment of a message containing a novel database
`identifier mechanism according to the present invention:
`FIGS.
`tiA—tiB are schematic diagrams of alternate
`embodiments of messages containing high—level and low-
`level database identifiers in accordance with the invention;
`and
`
`FIG. 7 is a schematic diagram of yet another alternate
`embodiment of a message containing various level database
`identifiers in accordance with the invention.
`
`DETABED DESCRIPTION OF ILLUSTRKIIVE
`EMBODIMENT
`
`FIG. 2 is a block diagram of a network system 200
`comprising a collection of computer networks connected to
`a plurality of nodes. The nodes are typically general-purpose
`computers comprising source nodes 81—36. destination node
`D and intermediate nodes Rl—Rh. Each node typically
`comprises a central processing unit (CPU) 2.2. a memory
`unit 204 and at least one network adapter 206 interconnected
`by a system bus 210. The memory unit 204 may comprise
`storage locations typically composed of random access
`memory (RAM) devices. which are addressable by the CPU
`EIZ and network adapter 206. An operating system. portions
`of which are typically resident in memory and executed by
`CPU. fitncu‘onaLly organizes the node by. inter alia. invoking
`network operations in support of processes executing in the
`CPU.
`The computer networks included within System 200 are
`local area networks (LANs) 1—2 interconnected by interme-
`diate node Rd. which is preferably a router. Communication
`among the nodes coupled to the W5 is typically eflected
`by exchanging discrete data "packets“ among the nodes.
`Router R4 facilitates the flow of these data packets through-
`out the system by routing the packets to the proper receiving
`nodes.
`In general. when a source node transmits a packet over
`LAN 1. the packet is sent to all nodes on that LAN. Ifthe
`intended recipient of the packet is connected to LAN 2. the
`packet is routed through router R4 onto but 2. Typically.
`the packet contains two destination addresses: the address of
`the final destination node and the address of the next node
`
`IO
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`6
`along the route. The final destination address remains con-
`stant as the packet n'avtn'ses the networks. while the next
`destination address dranges as the packet moves from node
`to node along the route throuyi the networks.
`to
`Specifimlly. when source node 51 sends a packet
`destination node D. i.e.. the final destination address. the
`patict is transmitted onto LAN 1 with a next destination
`address specifying the address of router R4. Address infor—
`mation embedded in the packet. which is processed by the
`higher-layer software of the protocol stack 250. identifies the
`final destination of the packet as node D. Based on this
`information. RA determines that the next node is the final
`destination node D and transmits the packet over LAN 1 to
`node D.
`
`A key function of a router is determining the next node to
`which the packet is sent: this rctuting function is preferably
`perfumed by network layer 160 of a protocol stack 250
`Within each node. This aspect of the network layer concerns
`the algorithms and protocols used by routers when cooper-
`rating to calculate paths through a network topology. The
`routers typically execute roofing algorithm to decide over
`which communication links incoming packets should be
`transmitted: a type of network layer routing protocol corn—
`monly employed by routers is a link state routing protocol
`According to this protocol. each router constructs a link
`state packet (LSP) containing infonnation needed to gener-
`ate a complete map of the topology of the network. FIG. 3
`depicts a schematic diagram of the [SP 300 era-uprising.
`inter alia. a source field 302 that indicates the particular
`source node generating the LSP. a sequence number field
`304 for storing the sequence number of the LSP and a
`neighbors field 306 containing a list of "neighbors". i.e..
`nodes adjacent to the source node. The sequence numbfl is
`preferably a monotonically inu'easing value that functions
`as a counter to uniquely identify the LSP.
`Each router forwards its LSP 300 to all othu routers
`coupled to the network and each of the other routers stores
`only the most recently received LSP in a LSP database
`organized in each of their memories 204 (FIG. 2). Armed
`with an updated set of ISPs. each rotner may execute
`predetermined algorithms to compute routes to destination
`nodes. An exarnple of a distributed link state routing pro-
`tocol
`is the intermediate system to intermediate system
`(13—48] protocol.
`Since the computed routes are dependent upon the infor-
`mation stored in the LSP databases of the routa's.
`it
`is
`essential that these databases are synchronized to ensure
`their contents are consistent. Aknown technique for closely
`synchronizing LSP databases involves designating a single
`router on the network as a designated router that periodically
`n‘ansrnlts a conqflete sequence numbers packet tCSN'P) to
`all other routers on the network. FIG. 4A is a schematic
`diagram of a CSNP 400 comprising a list of identifications
`of LSP data items 410 in the designated router’s database.
`along with sequence numbus m for these items.
`The routers that receive the CSNPM compare it with:the
`contents of their databases to determine whether their infor-
`mation is ctn'rent. That is. the routers compare each sequence
`number of the items listed in the CSNP with the sequence
`number of corresponding data items of their databases to
`determine if they are equal. If they are not. the greater. i.c..
`more recent. data item as indicated by the sequence number
`is provided to the router having the less recent item.
`In order to characterize an entire LSP database. the CSNP‘
`may be very large. thereby requiring apportionment of the
`CSNP into smaller packet fragments for transmission over
`
`Page 10 of 12
`Page 10 of 12
`
`

`

`5 342.820
`
`8
`that latter identifier of the CSN'P. If the calculated identifier
`is ditto-eat. the receiving router may request the entire CSN‘P
`from the designated router R4 to resolve any difiercnces in
`its database. Significantly. Rd transmits the actual CSNP
`only in response to a change in its database or in response
`to a request from another router.
`In the event a plurality of smaller packet fragments
`45m are needed for transmitting the CSN'P400 over the
`LANS 1-2. the designated router preferably computes an
`identifier for each CSN'P fragment. In an alternate embodi-
`ment of the invention. a hierarchical arrangement provides
`a single. higIMevcl database identifier Its the entire CSN'P
`and a plurality of low—level database identifiers for thes:
`individual CSNP fragments. Referring to FIGS. 6A and. SB.
`the high—level identifier 610 is contained within a bigh~level
`hello message 600 that is periodically broadcast by the
`designated router R4. If a discrepancy between identifiers is
`discovered by a router. that router may request a partimrlar
`low-level
`identifier disc-c- stored in low-level messages
`flue-e. respectively: each identifier 62504 corresponds to
`an appropriate CSNP fragment dsna—c.
`the hierarchical
`la a related alternate embodiment.
`arrangement is finther modified to provide a taro-stage
`operation arrangement at the receiving routers Rl-R3 and
`125-116. Specifically. the high—level and low—level identifiers
`are bundled within the same hello message that is periodi-
`cally broadcast by the designated router. R4 to the other
`routers. FIG. 7 is a schematic diagram of a hello message
`700 containing the various level identifiers. such as high-
`level identifier Til and low-level identifiers 72512—1:
`
`According to the first operation stage of the arrangement.
`each receiving router mlculates an identifier based on the
`entirety of its database. compares that identifier with the
`received high—level identifier 71' and. if they match. ignores
`the remainder of the message 700. On the Other hand. if the
`identifiers are dissimilar. the receiving router proceeds to the
`second stage. which specifies computations of identifiers for
`particular fragments of the database. These latter identifiers
`are thereafter compared with the appropriate low-level iden-
`tifiers 725a—c to identify the inconsistent database. frag-
`ments.
`
`10
`
`IS
`
`45
`
`.
`
`6
`
`
`
`Search for
`
`
`(
`
`
`matching
`identifiers
`
`
`
`#
`
`
`
`
`
`#
`
`
`
`
`
`
`
`
`
`%
`
`
`)
`
`%
`
`
`
`
`
`
`
`)
`
`&
`
`
`
`
`
`
`
`
`
`
`
`
`(
`
`
`
`
`#
`
`
`
`
`
`
`
`
`
`#
`
`
`
`
`
`
`
`
`7
`the network. FIG. 43 depicts schematic diagrams of CSN'P
`fragments 4500-0. each of which comprises a list of
`sequence numbers tied to an address range of LSP data
`items. Each packet fragment 45m preferably Chmctefi
`lens a contiguous portion of the database. e.g.. addresses
`xx—zz. and each is processed independently by the receiving
`routers. However. as routed. transmission of these additional
`smaller packet fragments 45th-c- over the network con—
`sumes significant bandwidth. while processing of the addi-
`tional individual packets consumes substantial amounts of
`computational resources in the routers.
`In accordance with the invention. a mechanism is pro—
`vided for efficiently synchronizing the contents of databases
`stored on nodes of a computer network to ensure that those
`contents are consistent Specifically. the mechanism coma
`prises a database identifier generated by a node of lhe
`computer network and distributed to other nodes eoupled to
`the oemork. According to the invention. the database iden-
`tifier is uniquely representative of the contents of the node‘s
`database and the. other nodes compare this unique identifier
`with their own generated database identifiers to determine if
`the identifiers. and thus their databases. are consistent.
`In the illustrative embodiment. the database identifier is
`uniquely representative of the CSNP. Referring also to FIG.
`2. the node (13.3.. a designated router which. for purposes of
`description. is router Rd) generntm the database identifier
`for the entire CSNP 400 and periodically broadcast that
`identifier: rather than the CSN‘P itself. to olha' nodes leg.
`routers) Rl—RJ and RS—Rfi coupled to LANs 1—2 by way of.
`e.g.. a “hello" message. FIG. 5 is a schematic diagram of a
`hello message packet 500 containing. inter alia. information
`such as the novel database identifier 510 of the invention and
`the source identification (orginawr) 502 of the message. i.e..
`the designated router Rd.
`Preferably. the database identifier 510 is generated from a
`cryptographic message digest algorithm executed by the
`CPU 202 and configured to transform the CSNP into a
`unique. fixed-length digest “signauue” whose contents are
`substantially less than those of the CSNP. It should be noted.
`however. that the identifier 510 may be generated by other
`techniques. such as cyclic redundancy checking or sequence
`number generation by the CPU. The underlying requirement
`One advantage of the invention is that extensive use of
`of such techniques is that they must be capable of producing
`computational resotnoes in the receiving routers is not
`unique values with high probability.
`required unless there are inconsistencies in the databases. In
`In the illustrative emborhment. the contents of the data-
`other words. the invention conserves processing resotn'ees
`base identifier field may comprise a 64 or 128 bit length of
`by potentially eliminating the need to labor through identi—
`the message. although any concise signature of relatively
`fier calculations and comparisons for each database frag-
`ment. In addition. the invention is flexible in that the number
`modest fixed length would suffice. A significant aspect of the
`invention is that the routers need only eaarnine and compare
`of hierarchical
`layers. database fragments and low-level
`identifiers are selectable.
`the contents of these fixed length fields to ascertain the
`---
`flush-alive
`-
`-
`:
`coherency of their databases. Accordingly. transmission of
`
`Not limited
`the database identifier in lieu of the CSNPoptlmizes both the
`embodiments for implementing a mechanism that efficiently
`use of computational resumes within the other routers and
`
`synchronizes the LSP databases of routers coupled to a
`to routers
`bandwidth on the network.
`LAN. it is to be understood that various other adaptations
`
`Upon receiving the database identifer. the routers Rl—R3
`and modifications may be made within the spirit and scope
`and RS-Rfi process that identifier to determine whether any
`of the invention. For example. the mechanism described
`herein ma
`be used in an
`of distributed 5 stem
`discrepancies arise and if so.
`those routers may request
`copies of the entire CSNP from the designated router Rd.
`Editing eificient synchronization of the contents of data—
`That is. each receiving router initially calculates an identifier
`figs stored on nodes of a cm network. In the case of
`based on the contents of its LSP database and then compares
`such distributed systems. a designated node of the computer
`the calculated identifier with the database identifier received
`network generates the database identifier and distributes that
`from the designated router. Of course. the routers Ill-RB and
`identifier to other nodes coupled to the network. According
`RS-RG calculate their identifiers according to the same
`to the invention. the database identifier is uniquely repre-
`algorithm or technique used by router R4.
`sentative oi the contents of the designated node‘s database
`A receiving router whose calculated database identifie.r
`and the receiving nodes generate their own database iden-
`conforms to the rccaived database identifier need only store
`lifiers from the contents of their databases so that they may
`
` e
`!
`
`
`
`'
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 11 of 12
`Page 11 of