(12) United States Patent
`Baber et al.
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US006279041Bl
`US 6,279,041 Bl
`(10) Patent No.:
`(45) Date of Patent:
`*Aug. 21, 2001
`
`SYSTEMS AND COMPUTER
`(54) METHODS,
`PROGRAM PRODUCTS
`FOR
`DIFFERENCING
`DATA COMMUNICATIONS
`USING A MESSAGE QUEUE
`
`(75)
`
`Inventors: Stephen B. Baber, Raleigb; Kathryn
`H. Britton, Chapel Hill; John R. Hind,
`Raleigh; Barron C. Housel,
`III, Chapel
`Hill; Ajamu Akinwunmi Wesley,
`Raleigh, all of NC (US)
`
`(73) Assignee:
`
`Business Machines
`International
`Corporation, Armonk, NY (US)
`
`( * ) Notice:
`
`the term of this
`to any disclaimer,
`Subject
`is extended or adjusted under 35
`patent
`U.S.C. 154(b) by 0 days.
`
`This patent
`claimer.
`
`is subject
`
`to a terminal dis-
`
`(21)
`(22)
`(51)
`(52)
`
`Appl. No.: 09/192,128
`Filed:
`Nov. 13, 1998
`Int. CI?
`U.S. Cl.
`
`G06F 15/16
`709/232; 709/230; 709/231;
`709/247; 370/235
`709/247, 232,
`709/231, 230; 370/235, 229
`
`(58)
`
`Field of Search
`
`(56)
`
`3,177,854
`4,386,416
`4,554,898
`
`References Cited
`U.S. PATENT DOCUMENTS
`4/1965 Gareea.
`5/1983 Giltner et al,
`11/1985 Yamada et al.
`(List continued on next page.)
`FOREIGN PArENT DOCUMENTS
`
`1322607
`95/10805
`97/46939
`
`1/1989 (CA).
`4/1995
`(WO).
`12/1997 (WO).
`
`395/888
`123/188 AA
`
`OTHER PUBLICArIONS
`
`IBM
`to Host File Transfer Restart Method,
`Application
`Technical Disclosure Bulletin, vol. 31, No.5, pp. 409-410
`(Oct. 1988).
`IBM Technical
`Interleaved I/O File Server,
`Synchronous
`Disclosure Bulletin, vol. 32, No. 9B, pp. 91-92 (Feb. 1990).
`
`(List continued on next page.)
`
`Primary Examiner-Moustafa
`M. Meky
`Assistant Examiner-Bradley
`Edelman
`(74) Attorney, Agent, or Firm-Jeanine
`Myers Bigel Sibley & Sajovec
`(57)
`ABSTRACT
`
`S. Ray-Yarletts;
`
`Method, apparatus and program products for increasing the
`performaoce
`of communications
`using differencing data
`communications
`over a message queue supporting asyn-
`chronous communications
`from a variety of applications
`executing on a source device over a shared external com-
`munication link to destination devices are provided. A data
`stream between the source device and the destination device
`is segmented based on the type of the data stream to provide
`a logical segmentation which increases
`the occurrence of
`repeated transmissions of a segment. The segments are then
`placed in the message queue as a message for transport
`to a
`destination computer. Differencing is provided by replacing
`tbe segment with an associated identifier for segments which
`have previously
`been transported
`to provide
`a reduced
`volume of data for transmittal based on recognition and
`replacement of data segments which bave previously been
`transmitted by the source device. The destination device
`receives tbe transmitted reduced segments as messages in a
`receive message queue and reconstructs
`the data stream.
`Synchronization
`between the differencing
`caches of
`the
`devices is oot required as tbe communication
`is asyochro-
`nous through a message queue and, if a reduced segment
`is
`not
`recognized,
`retransmission
`of
`the complete
`segment
`instead of the associated identifier may be requested and the
`source device creates and queues the segment as a message.
`
`60 Claims, 9 Drawing Sheets
`
`
`
`MICROSOFT
`
`EXHIBIT 1017
`
`Page 1 of 24
`
`

`
`5,121,479
`5,261,089
`5,269,017
`5,276,876
`5,282,207
`5,319,773
`5,319,774
`5,371,886
`5,426,645
`5,428,771
`5,432,926
`5,446,904
`5,469,503
`5,500,890
`5,539,736
`5,546,582
`5,551,043
`5,561,797
`5,581,704
`5,581,753
`5,592,512
`5,594,910
`5,611,038
`5,613,060
`5,666,399
`5,682,514
`5,706,435
`5,724,581
`5,734,898
`5,751,719
`5,754,774
`5,758,072
`5,758,174
`5,765,004
`5,768,538
`
`6/1992
`11/1993
`12/1993
`1/1994
`1/1994
`6/1994
`6/1994
`12/1994
`6/1995
`6/1995
`7/1995
`8/1995
`11/1995
`3/1996
`7/1996
`8/1996
`8/1996
`10/1996
`12/1996
`12/1996
`1/1997
`1/1997
`3/1997
`3/1997
`9/1997
`10/1997
`1/1998
`3/1998
`3/1998
`5/1998
`5/1998
`5/1998
`5/1998
`6/1998
`6/1998
`
`O'Brien
`Coleman et al.
`Hayden et aJ.
`Coleman et al.
`Jurkevich et al....
`Britton et al.
`Ainsworth et al.
`Britton et al.
`Haskin
`Daniels et al.
`.
`Citron et al.
`Belt et al.
`....
`Butensky et al.
`Rogge et al.
`Johnson et aJ.
`Brockmeyer
`et al.
`Crump et al.
`Gilles et al.
`Barbara et al.
`Terry et al.
`..
`Spiess.
`.
`Filepp et al.
`..
`Shaw et al.
`Britton et al.
`Bales et al.
`..
`Yohe et al.
`Barabara et al.
`Kozakura
`He
`Chen et aJ.
`Bittinger et al.
`Filepp et al.
`Crump ct aJ.
`Foster et al.
`Badovinatz
`
`.
`
`.
`et al.
`
`U.S. PATENT DOCUMENTS
`
`....
`
`US 6,279,041 Bl
`Page 2
`
`395/250
`395/600
`395/575
`395/650
`.... 370/110.1
`395/575
`395/575
`395/600
`370/118
`395/575
`395/575
`395/750
`379/265
`379/91
`370/60
`395/650
`395/750
`395/600
`711/141
`711/141
`
`.. 395/800.28
`....... 395/806
`395/182.13
`379/419
`711/118
`711/141
`707/202
`707/203
`370/473
`395/200.33
`395/200.5
`395/750.05
`395/750.05
`395/200.78
`
`5,781,908
`5,787,470
`5,802,267
`5,813,032
`5,832,508
`5,878,213
`5,909,569
`6,003,087
`6,035,324
`6,073,173
`6,148,340
`
`7/1998
`7/1998
`9/1998
`9/1998
`11/1998
`*
`3/1999
`*
`6/1999
`* 12/1999
`*
`3/2000
`*
`6/2000
`* 11/2000
`
`Williams et al.
`DeSimone et al.
`Shirakihara
`et al.
`Bhargava et al.
`Sherman et al.
`Bittinger et al.
`I[] et al.
`Housel,
`Housel,
`III et al.
`Chang et al.
`Bittinger et al.
`Bittinger et al.
`
`.
`
`OTHER
`
`PUBLICATIONS
`
`........... 707/104
`
`.. 395/182.13
`
`.
`
`709/203
`703/21
`709/229
`709/203
`709/224
`709/224
`
`Checkpoint/Restart
`File Transmission
`Client/Server-based
`IBM Technical Disclosure Bulletin, vol. 38, No.
`Protocol,
`09, pp. 191-193
`(Sep.
`1995).
`Protocols
`Commit
`Combining
`Presumed
`Abort Two-Phase
`IBM Technical Dis-
`with SNA's
`Last Agent Optimization;
`closure Bulletin, vol. 34, No.7B,
`pp. 334-338
`(Dec.
`1991).
`Efficient Commit
`Protocol
`for Shared Nothing Architectures
`IBM Technical Disclosure
`Using
`Common
`Log
`Server,
`Bulletin, vol. 36, No. 12, pp. 65-66
`(Dec.
`1993).
`Jacob
`Ziv, Abraham
`Lempel;
`Compression
`of
`IEEE.
`Sequences
`via Variable-Rate
`Coding,
`9178.
`Transactions on Information Theory, vol. 1-24, No.5,
`Jacob
`Ziv, Abraham
`Lempel;
`A Universal
`Algorithm
`IEEE Transactions on Infor-
`Sequential
`Data Compression,
`mation Theory, pp. 337-343, May
`1977.
`IBM Technical Disclosure Bulletin,
`Emulatioo
`Data Stream,
`vol. 33, Aug.
`1990, pp. 221-223.
`iBM Technical Dis-
`Two-Phase
`Commit Resyochronizatioo,
`closure Bulletin, vol. 39, No. 01, pp. 79--80 (Jan.
`1996).
`
`Individual
`
`• cited by examiner
`
`Page 2 of 24
`
`.
`
`

`
`-....l
`=" 1..1
`J1
`
`e'
`
`I-"
`Cd
`-"
`
`~I
`
`1.0b
`
`10
`..•
`....
`
`e.
`
`=- ~~...
`
`[JJ
`
`...
`
`~=~Nr
`-Noo.
`
`""" re=
`
`""""
`
`~~ ~~ "
`
`52
`
`50
`
`+r-r-
`Rules
`Type
`ASCII
`
`Object
`
`CombineFramework
`
`MessageQueue
`
`ExpandingObject
`
`ScanSegmentObject
`
`54
`
`46
`
`48
`
`44
`
`42
`
`FIG.2
`
`40
`
`I
`
`Network
`
`22
`
`/
`
`EmittingObject
`
`ReducingObject
`
`MessageQueue
`
`30
`
`28
`
`---r-
`Rules
`Type
`Mime
`
`Object
`
`SegmentFramework
`
`36
`
`34
`
`32
`FIG.1
`
`~
`
`20
`
`26
`
`Page 3 of 24
`
`Network
`
`22-,
`
`

`
`u.s. Patent
`
`Aug. 21, 2001
`
`Sheet 2 of 9
`
`US 6,279,041 Bl
`
`FIG. 3
`100
`
`Intercept Data Stream
`
`Segment Data Stream
`
`102
`
`114
`
`Update Differencing
`Cache and Index
`
`104
`
`Queue Segment
`Transport
`
`for
`
`for
`Mark Segment
`Retransmission
`
`Yes
`
`120
`
`Reduce Segment
`
`Emit Segment
`
`Dequeue Segment
`
`110
`
`11
`
`Page 4 of 24
`
`

`
`u.s. Patent
`
`Aug. 21, 2001
`
`Sheet 3 of 9
`FIG. 4
`
`US 6,279,041 Bl
`
`Object Segment
`
`100
`
`Receive Data Stream
`
`-------------------------~
`152
`
`102
`
`,,,,,,,,,,,,,,,,
`
`I I,,
`
`Determine Type of
`Data Stream
`
`Invoke Appropriate
`Segmentation Object
`for Type
`
`in Data
`Place Segment
`Message Queue
`
`158
`
`154
`
`156
`
`-----------------------------
`
`Yes
`
`Yes
`
`Page 5 of 24
`
`

`
`u.s. Patent
`
`Sheet 4 of 9
`Aug. 21, 2001
`FIG. 5
`
`US 6,279,041 Bl
`
`I
`I
`
`:
`:
`
`V
`
`I
`
`108
`
`Page 6 of 24
`
`,----------------------------
`:
`:
`:
`
`Reduce Object
`-----------------------------,
`172
`
`Read Message From
`Queue
`
`o
`I
`
`I
`
`174
`
`Compute Data
`Signature
`
`180
`
`----
`
`110
`
`Replace Segment with
`Identifier as Reduced
`Segment
`
`Emit Reduced
`Segment
`
`I I I I I I I I I I IL
`
`

`
`US 6,279,041 Bl
`
`u.s. Patent
`
`Sheet 5 of 9
`Aug. 21, 2001
`FIG. 6
`
`Receive Object
`
`200
`
`Scan in Message From
`Buffer
`
`No
`
`202
`
`206
`
`Request Retransmission
`
`204
`No
`In LRU and Diff. >------------'
`Index?
`
`Yes
`
`Retrieve Segment
`
`Place Segment in Input
`Queue
`
`Combine Segment into
`Object
`
`Dequeue Segment and
`Update LRU and
`Differencing Index
`
`208
`
`210
`
`212
`
`214
`
`Page 7 of 24
`
`

`
`u.s. Patent
`
`Aug. 21, 2001
`
`Sheet 6 of 9
`
`US 6,279,041 Bl
`
`Segment Object
`
`258
`
`FIG. 7
`
`252
`
`262
`
`Queue Initial Request
`
`Message Queue
`
`256
`
`Data Send Module
`
`Network-,
`
`264
`
`266
`
`22
`
`Page 8 of 24
`
`

`
`u.s. Patent
`
`Aug. 21, 2001
`
`Sheet 7 of 9
`
`US 6,279,041 Bl
`
`File Transmit
`
`Receive Transmit
`Request
`
`FIG. 8
`
`270
`
`272
`
`Yes
`
`274
`
`Identify Segments
`276L---------~--------~
`
`Write to File Cache
`with Version Number
`
`278
`
`Create Segment Index
`with Identifier, Offset
`and Length
`
`280
`
`No
`
`286
`
`284
`
`Transfer File without
`Differencing
`
`Transfer File with
`Differencing
`
`Page 9 of 24
`
`

`
`u.s. Patent
`
`Aug. 21, 2001
`
`Sheet 8 of 9
`
`US 6,279,041 Bl
`
`FIG. 9
`
`308
`
`to
`Emit Segment
`Transmit Buffer
`
`Initialize Segment
`Counter
`
`Determine Next
`Segment of File
`
`No
`
`ID as Reduced
`Emit
`Segment
`to Transmit
`Buffer
`
`Increment Segment
`Counter
`
`300
`
`302
`
`306
`
`310
`
`Buffer Full or EOF?
`
`No
`
`Yes
`
`314
`
`Update Offset and Xmit
`Buffer
`
`Page 10 of 24
`
`

`
`u.s. Patent
`
`Aug. 21, 2001
`
`Sheet 9 of 9
`
`US 6,279,041 Bl
`
`FIG. 10
`322
`
`Receive Buffer
`
`Determine State of
`Target File
`
`Receive Next Segment
`From Buffer
`
`324
`
`326
`
`No
`
`Expand Segment From
`Cache
`
`332
`
`to
`Write Segment
`Target File Xn at
`Current Offset
`
`334
`
`336
`
`Update Index for
`Target File
`
`increment Offset by
`Segment Length
`
`No
`
`340
`
`Update State of Target
`File/EOF
`
`Page 11 of 24
`
`

`
`US 6,279,041 B1
`
`1
`SYSTEMS AND COMPUTER
`METHODS,
`PROGRAM PRODUCTS
`FOR
`DIFFERENCING
`DATA COMMUNICATIONS
`USING A MESSAGE QUEUE
`
`FIELD OF THE INVENTION
`The present invention relates to communications between
`devices over a network. More particularly,
`the present
`invention relates to communications
`over a low-speed or
`wireless communication link between two computers using
`a message
`queue.
`
`20
`
`25
`
`BACKGROUND OF THE INVENTION
`Traditional mainframe computer configurations provided
`for user interface to tbe computer
`through computer
`termi-
`nals wbich were directly connected by wires to ports of
`controllers connected by channels
`to tbe mainframe com-
`puter. As computing technology has evolved, processing
`power has typically evolved from a central processing center
`with a number of relatively low-processing power terminals
`to a distributed
`environment
`of networked
`processors.
`Examples of this shift
`in processing include local or wide
`area networks wbicb interconnect
`individual work stations
`where each workstation has substantial
`independent pro-
`cessing capabilities. This shift may he further seen in the
`popularity of the Internet which interconnects many proces-
`sors and networks of processors through devices such as, for
`example,
`routers.
`At the same time that processing power was becoming
`more distributed tbere was also an increase in tbe popularity
`of mobile computing. The use of laptops, notebooks, Per-
`sonal Digital/Communication Assistants (PDAs/PCAs) and
`other portable devices has led to an increase in demands for
`wireless communications. Wireless communication allows a 35
`user freedom to move witbin the wireless environment wbile
`remaining
`"connected"
`to a network. Furthermore,
`a wire-
`less connection to a network allows a portable processor
`user the convenience of connecting to a network without
`having to plug into a docking station or use some other
`method
`of "hardwiring"
`to a network. However, wireless
`wide area networks, cellular communications
`and packet
`radio, suffer from common limitations such as the higb cost
`per byte of communications,
`slow response time, low band-
`width and unreliability wbich all bamper use of wireless
`tecbnology.
`Even outside of the portable processing arena wireless
`communications have seen an increase in popularity. Thus,
`as a result of infrastructure limitations, cost or convenience,
`it is hecoming more frequent
`tbat a network linking two 50
`devices wishing to communicate may include a low through-
`put component
`such as a wireless network link.
`Communications between devices such as computers are
`typically disadvantaged particularly on lower
`through-put
`network legs, sucb as wireless legs (or highly congested legs
`which are effectively bandwidth limited), where bandwidth
`limitations
`result
`in slower
`response time for communica-
`tions between tbe computers.
`In the extreme, protocol
`tim-
`eouts may even cause transmission
`errors and resulting
`retransmissions
`or even inability of
`the communication
`system to operate. Thus, utilizing wireless technology, or
`any low-speed communication technology, for data commu-
`nication between applications executing on computers exac-
`erbates the weaknesses of the wireless technology.
`Communications
`are further complicated wbere a plural-
`ity of applications executing on a computer perform opera-
`tions requiring transmission of data streams over a sbared
`
`2
`link, on occasion with
`to an external communication
`port
`It is known to provide
`interruptions
`in session connections.
`for this shared access using asynchronous message queuing
`systems sucb as International Business Machine Corpora-
`tion's Message Queuing Series ("MQSeries"), Telecommu-
`nications Access Method ("TCAM"), or Information Man-
`agement Systems
`("IMS"), which enable applications
`to
`queue data for transport (transmission)
`to a partner destina-
`tion computer device on an external communication
`link
`10 sucb as a network. Using asyncbronous message queuing,
`the external connection between the source computer and
`the destination computer
`typically does not bave to exist at
`tbe time of submission of a data stream message for trans-
`mission and tbe source or sending device is not required to
`for a response
`from the destination
`15 syncbronously wait
`device.
`In other words,
`the transmitting application hands
`over responsibility for the message to the transport queuing
`application which takes on responsibility
`for eventually
`delivering the queued message. In general, any data object,
`including messages,
`files,
`images, containers, etc., can be
`transported using a message queuing system.
`The message queue transport application reads messages
`from the queue and sends them to the destination devices
`over
`the network. The communication
`protocol between
`transmitting
`and receiving message queues provides
`for
`assumption of responsibility over a transmitted message by
`tbe receiving device. The source message queue transport
`application typically then frees the queue space occupied by
`a message once confirmation is received that the receiving
`30 device bas assumed responsibility for the message.
`OBJECTS AND SUMMARY OF THE
`INVENTION
`it is one object of the
`In view of tbe above limitations,
`present
`invention to provide for improved performance for
`data communications
`in a low-speed communication envi-
`ronment such as wireless communications.
`It is a further object of the present
`invention to support
`sucb communications where tbe communicating
`applica-
`tions may be only intermittently connected.
`invention to
`It
`is an additional object of
`the present
`support sucb communications wbere the external commu-
`nication link used for communication is shared by different
`applications.
`invention
`the present
`In view of these and otber objects,
`provides methods, systems and computer program products
`supporting differencing data communications using a mes-
`sage queue supporting asynchronous communications
`from
`a variety of applications executing on a source device over
`a shared external communication link to destination devices.
`At least one segment of a data stream between the applica-
`tion on the source device and an application on the desti-
`nation device occurs over an external communication link.
`The present
`invention provides increased communications
`performance by combining data stream differencing with
`asychronous message transmission control using a message
`queue. The data stream is segmented based on the type of the
`data stream to provide
`a logical
`segmentation which
`increases
`the occurrence of
`repeated transmissions
`of a
`segment. Each segment
`is then placed in the message queue
`as a message for transport
`to a destination computer. Dif-
`ferencing is provided by replacing tbe segment with an
`associated identifier
`for segments which have previously
`been transported to provide a reduced volume of data for
`transmittal based on recognition and replacement of data
`segments which have previously been transmitted by the
`source device.
`
`40
`
`45
`
`55
`
`60
`
`65
`
`Page 12 of 24
`
`

`
`US 6,279,041 B1
`
`10
`
`25
`
`40
`
`50
`
`55
`
`60
`
`3
`TIle intercept system on the receiving end at the destina-
`tion computer
`receives the transmitted reduced segments as
`messages, expands
`the reduced segments
`and writes
`the
`expanded segments to a receive message queue. Segments
`are read from tbe receive message queue and combined to
`form the reconstructed data stream. The reconstructed data
`stream is then provided to the target application on the
`destination computer. By providing protocol conversion at
`both ends of the external communication link, the applica-
`tions may continue to operate without any need to recognize
`the protocol differencing conversion provided by the present
`invention. Furthermore,
`synchronization
`is not
`required
`between the devices as the message queue provides asyn-
`chronous communications
`and, if a reduced segment
`is not
`recognized,
`retransmission of the complete segment using 15
`the segment
`identifier may be requested and the source
`device creates and queues the segment as a message.
`In one embodiment of the present
`invention, a method is
`provided for differencing
`data communications
`using a
`message queue. A data stream having an associated type is 20
`intercepted (received) from a host application prior to trans-
`mission of the data stream through the message queue on an
`external communication link to a destination computer. The
`data stream is segmented based on the associated type to
`provide a plurality of segments. Message identifiers associ-
`ated with the plurality of segments are then placed into the
`message queue. The transport system then selects one of the
`plurality of segments from the message queue for transport
`and determines if the selected segment has previously been
`transported. The selected segment is reduced to a differenced
`communication format based upon whether it has previously
`been transported to provide a reduced segment and emitted.
`After verifying that the differenced communication format
`of
`tbe reduced segment was known to the destination
`computer,
`the selected segment
`is dcqueucd and placed in a 35
`differencing cache if it has not previously been transported.
`The message
`identifiers
`associated with the plurality of
`segments may be the associated segments
`themselves or
`tbey may be pointers to a location in memory where asso-
`ciated segments can be found.
`the system
`invention,
`In one embodiment of the present
`determines
`if the segment has previously been transported
`and plaecd in the differencing cache by first calculating an
`identifier for the selected segment such as a data signature
`based on the content of the segment (e.g. a eRC). Based on 45
`the calculated
`identifier,
`the system determines
`if
`the
`selected segment corresponds
`to a segment
`saved in the
`differencing cache. Dequeuing a message operations may
`include placing the identifier of the selected segment
`in a
`differencing index and the system determines if the segment
`has previously been transported by determining if tbe iden-
`tifier of the selected segment
`is in tbe differencing index. A
`pointer may also be placed in the differencing index enabling
`tbe selected segment
`to be located in the differencing cache.
`The differencing index is preferably associated with a least
`recently used list and a least
`recently used segment
`is
`removed from the differencing cache and tbe differencing
`index if the differencing cache exceeds a size criteria. In one
`embodiment of tbe present
`invention,
`reducing a segment
`includes replacing the selected segment with tbe identifier
`associated witb tbe selected segment
`to provide tbe reduced
`segment
`if the selected segment has previously been emitted
`and providing tbe selected segment as the reduced segment
`if the selected segment has not previously been emitted.
`the 65
`In a further embodiment
`of the present
`invention,
`message queue receives messages from a plurality of data
`streams and a synchronously emits (transmits)
`the messages
`
`30
`
`4
`on the external communication link. The messages may be
`emitted in a first
`in first out sequence from the message
`queue and the message queue may have an associated
`maximum message size.
`invention, a mes-
`In another embodiment of the present
`sage is received from the destination computer
`indicating
`whether the destination computer had a segment
`in memory
`corresponding to the emitted identifier. The selected seg-
`ment rather than the identifier associated with the selected
`segment is emitted if the received message indicates that the
`destination computer did not have a segment
`in memory
`corresponding to the emitted identifier.
`In a further embodiment of the segmenting operations of
`the present
`invention, an associated type of the data stream
`is determined. A rule set is selected for segmenting the data
`stream based on the determined type and tbe selected rule set
`is applied to segment the data stream. The associated type of
`the data stream may be determined based on the data stream.
`In one embodiment,
`the associated type is a MIME type.
`In anotber aspect of the present
`invention,
`the destination
`computer
`receives the emitted reduced segment and recon-
`structs
`the selected segment
`from the received reduced
`segment. The reconstructed selected segment
`is placed in a
`received message queue. The data stream is then recon-
`structed responsive
`to the received message queue. The
`destination computer determines
`if the reduced segment
`contains
`the selected segment
`and then determines
`if a
`segment associated with the reduced segment
`is available to
`tbe destination computer
`if the reduced segment does not
`contain tbe selected segment. Tbe reduced segment
`is
`replaced witb the segment
`associated witb the reduced
`segment
`if available. Otherwise, a message is emitted to tbe
`device from which the reduced segment
`is received request-
`ing transmission of the selected segment
`if tbe segment
`associated with the reduced segment
`is not available. Data
`stream reconstruction
`may
`include
`integrating
`segments
`from the received message queue into objects. The recon-
`structed
`selected segment may be dequeued
`from the
`received message queue after providing tbe reconstructed
`selected segment
`to the reconstructing step. The destination
`computer may provide a differencing index and differencing
`cacbe in a manner analogous to tbat described for the source
`computer.
`invention, a method is
`In a further aspect of the present
`provided for transferring a file from a source computer
`to a
`destination computer using a message queue. A current
`version of the file is copied to a file cache responsive to a file
`transfer
`request and file segments are defined associated
`witb the current version. The source computer determines if
`previous versions of the file having associated file segments
`are available to tbe source computer and if the destination
`computer bas one of
`the previous versions of
`tbe file
`available. A first
`file segment of
`tbe current version is
`compared with the associated file segments of the previous
`version and a message identifier for the first file segment
`is
`placed in the message queue to request
`transfer of the first
`file segment
`if no matching associated file segments of the
`previous
`version are located. Otherwise,
`a match indication
`is placed in the message queue for transfer
`if a matching
`associated file segment
`is located.
`In aile embodiment of the file transfer aspects of the
`present
`invention, an identifier is calculated for eacb of tbe
`file segments associated with the current version and tbe
`calculated identifiers are placed in a segmenting index. The
`calculated identifiers are compared to a reference identifier
`based on one of tbe associated file segments of the previous
`
`Page 13 of 24
`
`

`
`US 6,279,041 B1
`
`5
`version and comparison operations continue until either a
`match is located or all the associated file segments have been
`tested. Comparing operations
`are preferably repeated for
`eacb of
`tbe file segments of
`tbe current version to be
`transferrred.
`In one embodiment, an identifier is calculated
`for each of the file segments associated witb the current
`version. A segment
`length for eacb of the file segments is
`also calculated and placed in the segmenting index associ-
`ated with tbe calculated identifiers.
`In a further embodiment of tbe file transfer aspects of the
`present
`invention, an identification of the previous version
`of
`the file is transmitted to the destination computer. A
`message
`is then received from the destination computer
`containing an indication of whether tbe previous version of
`tbe file is available to the destination computer. Furthermore,
`when a plurality of previous versions are available to the
`source computer,
`the identifications of the plurality of pre-
`vious versions are transmitted to the destination computer
`and the message received from the destination computer
`contains an indication of one of the plurality of previous
`versions of the file which is available to the destination
`computer. This one of the previous version is then used for
`comparing operations to provide a differenced communica-
`tion file transfer to the destination computer.
`As will be appreciated by those of skill in this art, while
`the the above described aspects of the present invention have
`primarily been discussed as a methods,
`they may also be
`provided as systems or as computer program products.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of a communication system for
`differencing data communications
`from the source device
`perspective according to an embodiment of
`the present
`invention;
`FIG. 2 is a block diagram of a communication system for
`differencing on-going data communications
`from a destina-
`tion device perspective according to one embodiment of the
`present
`invention;
`FIG. 3 is a flow chart illustrating operations carried out by
`a source device according to an embodiment of the present
`invention;
`FIG. 4 is a flow cbart illustrating operations carried out by
`a source device for segmenting a data stream according to an
`embodiment of the present
`invention;
`FIG. 5 is a flow cbart illustrating operations carried out by
`a source device for
`reducing segments
`according to an
`embodiment of the present
`invention;
`FIG. 6 is a flow cbart illustrating operations carried out by
`a destination side device according to an embodiment of tbe
`present
`invention;
`system
`FIG. 7 is a block diagram of a communication
`according to a file transfer aspect of the present
`invention;
`FIG. 8 is a flow cbart illustrating operations carried out by
`a source device according to an embodiment of the file
`transfer aspect of the present
`invention;
`FIG. 9 is a flow cbart illustrating operations carried out by
`in segmenting a file according
`a source device
`to an embodi-
`ment of the file transfer aspect of the present
`invention;
`FIG. 10 is a flow cbart illustrating operations carried out
`by a destination device according to an embodiment of tbe
`file transfer aspect of tbe present
`invention.
`DETAILED DESCRIPTION OF Tl-lE
`PREFERRED EMBODIMENTS
`The present
`invention now will be described more fully
`hereinafter witb reference to the accompanying drawings,
`in
`
`6
`which preferred embodiments of the invention are shown.
`Tbis invention may, however, be embodied in many different
`forms and should not be construed as limited to the embodi-
`ments set forth berein; rather,
`these embodiments
`are pro-
`vided so that this disclosure will be tborougb and complete,
`and will fully convey the scope of the invention to those
`skilled in the art. Like numbers
`refer
`to like elements
`throughout. As will be appreciated by one of skill in the art,
`tbe present
`invention may be embodied as methods, devices
`10 (systems) or computer program products. Accordingly,
`the
`present
`invention may take the form of an entirely hardware
`embodiment,
`an entirely
`software
`embodiment
`or an
`embodiment combining software and bardware aspects.
`An embodiment of the present
`invention will now be
`15 described with reference to tbe block diagram illustrations of
`FIG. 1 and FIG. 2 wbicb show tbe source and destination
`device respectively. Referring first to FIG. 1, a data source
`application 20 executing on a source device such as a
`computer generates a data stream to be communicated over
`20 an external communication link sucb as a network 22. The
`stream from source 20 is provided to segment object 24.
`Segment object 24 includes a segment framework object 26
`as well as a variety of segmenting rule objects for different
`types of data streams including the illustrated ASCII type
`25 object 28 and otber MIME type object 30. A variety of
`different
`type objects may be provided for different appli-
`cations
`sucb as terminal emulators,
`e-mail applications,
`word processors, etc., eacb of wbich is configured to inter-
`face and communicate witb segment framework object 26 to
`30 provide segment processing by segment object 24 based on
`the associated data type of an incoming data stream. The
`associated type of the receive data stream in one embodi-
`ment of the present
`invention is determined based on the
`contents of tbe data stream itseIf.
`The output of segment object 24 is provided to message
`queue 32 for transport. Message queue 32 is preferably an
`asynchronous message queuing system such as those known
`to those of skill in tbe art with operations of message queue
`32 being modified as will be described herein according to
`tbe teacbings of the present
`invention to provide for differ-
`enced data communications. An example of a message
`queue based transport
`system is described in U.S. patent
`application Ser. No. 09/191,637 entitled "Methods, Systems
`and Computer Program Products
`for Synchronization
`of
`45 Queue to Queue Communications" whicb is incorporated
`herein by reference in its entirety, still pending.
`It is to be
`understood that message queue 32 is a queue associated with
`an output port or node connection to network 22 which may
`support message based transmissions
`for a variety of differ-
`50 ent data source applications 20 executing on tbe source
`computer. Wbile operations will be described for a single
`data stream feeding message queue 32 for ease of under-
`standing the present invention,
`it is to be understood that the
`operations described herein may be duplicated for additional
`55 data streams and all of tbe separate data streams may share
`a common message queue 32 which may provide the capa-
`bility for proper delivery of messages at
`the source and
`destination device from different
`source and destination
`applications
`using known techniques
`for asynchronous
`transport using message queues. Accordingly,
`these aspects
`of message queue 32 will not be further described herein
`except
`to the extent
`they relate to or are modified according
`to the teachings of the present
`invention.
`invention applies
`As will be described herein,
`the present
`65 data stream differencing to tbe data stream to reduce the
`volume of data transmitted over an external communication
`link, such as a low-bandwidth wireless
`link. Data stream
`
`60
`
`35
`
`40
`
`Page 14 of 24
`
`

`
`US 6,279,041 B1
`
`20
`
`25
`
`30
`
`7
`differencing is described in u.s. patent application Ser. No.
`08/852,586 which is incorporated herein by reference in its
`entirety. A data reduction technique is also described for use
`in client-server
`application
`environments,
`such as the
`Internet,
`in U.S. Pat. No. 5,754,774. These approaches use
`knowledge of tbe structure of tbe data stream to segment
`the
`data stream and maintain synchronized caches at the source
`and destination devices
`to allow previously
`transmitted
`segments
`in the data stream to be replaced by identifiers
`allowing the receiving device to rebuild the complete data 10
`stream from its cache of previously received segments.
`However, these approaches geoerally require syncbroniza-
`tion between the devices and are directed to processing of a
`data stream between actively connected devices allowing
`synchronous communication.
`Messages in message queue 32 are successively passed to 15
`reducing object 34 for differencing the data stream coming
`out of message queue 32 according to tbe teacbings of the
`present
`invention. Wbile for tbe embodiments
`described
`herein,
`the reducing object 34 is illustrated as operating on
`output messages from message queue 32 it is to be under-
`stood that the benefits of the present invention may similarly
`be obtained by providing a reducing object operating on the
`output of segment object 24 and entering reduced data
`stream segments