0?
`gm
`Egg
`5%;
`~$E§
`“g re
`g3
`
`\
`
`PATENT
`-
`,
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`c, g :
`Rag
`ATTY DOCKET NO: 5577-116
`“-2 g:
`DATE: November 13, 1998
`55:2: 3
`aim-HE:
`UTILITY PATENT APPLICATION TRANSMITTAL LETTER E3 E:
`AND FEE TRANSMITTAL FORM (37 CFR 1.5303))
`"‘ +-
`
`BOX PATENT APPLICATION
`Assistant Commissioner for Patents
`
`Washington, DC 20231
`
`Sir:
`
`
`
`Transmitted herewith for filing under 37 CFR 1.53(b) is:
`E a patent application
`.
`D a Continuation D a Divisional E] a Continuation-in-Part (CIP)
`of prior application no.:
`; filed
`El A Small Entity Statement(s) was filed in the prior application; Status still proper and desired.
`
`Inventor(s) or Application Identifier:
`Stephen B. Baber; Kathryn H. Britton; John R. Hind;
`Barron C. House], 111 and Ajamu Akinwunmi Wesley
`
`Entitled: METHODS, SYSTEMS AND COMPUTER PROGRAM PRODUCTS FOR
`DIFFERENCING DATA COMMUNICATIONS USING A MESSAGE QUEUE
`
`Enclosed are:
`
`Application Transmittal Letter and Fee Transmittal Form (A duplicate is enclosedforfee processing)
`1.
`2. g 39 pages of Specification (including 28 claims)
`3.
`9 sheets of Formal Drawings (35 USC 113)
`4
`.
`IX] Oath or Declaration
`a.
`newly executed {original or copy)
`13. E} copy from prior application (37 CFR 1.63 (d) G‘br continuation/divisionaD [Note Box 5 Below]
`c. D DELETION 0F INVENTOR! S! {Signedstalement deleting fnventor(s) named in the prior duplication)
`
`5. El Incorporation By Reference (useable 1fbox 4b is checkeaD
`The entire disclosure of the prior application, fi‘om which a copy of the oath or declaration'Is supplied under Box 4b, is
`considered as being part of the disclosure of the accompanying application andIs hereby incorporated by reference
`therein.
`
`wen?
`
`[:I Microfiche Computer Program (Appendix)
`g Assignment papers (cover sheet(s) and decanter/1:69))
`|:| Small Entity Statement(s)
`|:] Information Disclosure Statement, PTO-1449, and references cited
`10. D Preliminary Amendment (Please enter all claim amendments prior to calculating theflmgfee)
`11. [:| English Translation Document
`12. El Certified Copy of
`Application No.
`
`Page 1 of 55
`Page 1 of 55
`
`Page 1 of2
`
`EXHIBIT 1018
`
`; Filed
`
`'
`
`'
`
`MICROSOFT
`MICROSOFT
`
`EXHIBIT 1018
`
`

`

`13. D Sequence Listing! Sequence Listing Diskette
`a. 0 computer
`readable copy
`b. 0 paper copy
`c. 0 statement
`14. D An Associate Power of Attorney
`in support
`15.lZJ Return Receipt Postcard (MPEP 503) (Should be specifically itemized)
`16.0 Other:
`The fee has been calculated as shown below'
`Column 1
`Column 2
`No. Extra
`No. Filed
`
`8
`1
`
`If the difference in CoL I is less than zero, Enter "0" in Col. 2
`
`Small Entity
`Rate
`Fee
`$395.00
`x l l = $
`x41 = $
`+ 135 = $
`Total $
`
`Large Entity
`Rate
`Fee
`$790.00
`x 22 = $176.00
`x 82 = $82.00
`+270 = $.
`Total $1048.00
`
`BASIC FEE
`28- 20 =
`TOTAL CLAIMS
`INDEP CLAIMS
`4 - 3 =
`TI MULTIPLE Dependent Claims Presented
`'0 A check in the amount of$
`o A check in the amount of $
`
`to cover the filing fee is enclosed.
`is enclosed to cover the filing fee, PLUS the Assignment Recordation
`
`fee ($40.00).
`lZJ Please charge my Deposit Account No. 09-0461 in the amount of $1088.00 to cover the filing fee, PLUS
`the Assignment Recordation fee ($40.00).
`lZJ The Commissioner is hereby authorized to credit overpayments or charge the following fees associated
`with this communication to Deposit Account No. 09-0461.
`a.
`lZJ Additional filing fees under 37 CFR 1.16 for presentation of extra claims.
`b.
`lZJ Additional patent application processing fees under 37 CFR 1.17.
`
`RltQ:;PW
`
`Robert W, Glaru
`Registration No. 36,811
`
`Correspondence Address:
`USPTO Customer Number: 20792
`Myers Bigel Sibley & Sajovec, P.A.
`Post Office Box 37428
`Raleigh, NC 27627
`Tel (919) 854-1400
`Fax (919) 854-1401
`
`CERTIFICATE OF EXPRESS MAILING
`
`Express Mail Label No. EL085941554US
`Date of Deposit: November
`13, 1998
`is being deposited with the United States Postal Service "Express Mail Post Office to
`I hereby certify that this correspondence
`service under 37 CFR 1.10 on the date indicated above and is addressed to Box Patent Application, Assistant Commissioner
`Addressee"
`Patents, washingtopDC
`2~
`
`llttckJt
`
`,ffi:
`
`For
`
`Michele P. McMahan
`Date of Signature November
`
`13, 1998
`
`Page 2 of 55
`
`Page 2 of2
`
`

`

`METHODS, SYSTEMS AND COMPUTER PROGRAM
`PRODUCTS FOR DIFFERENCING DATA COMMUNICATIONS
`USING A MESSAGE QUEUE
`
`Abstract
`
`of the
`
`Invention
`
`Method, apparatus and program products
`
`for increasing the performance
`
`of
`
`communications
`
`using differencing data communications
`
`over a message queue
`
`supporting asynchronous
`
`communications
`
`from a variety of applications
`
`executing
`
`5
`
`on a source device over a shared external communication
`
`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
`
`10
`
`transport
`
`to a destination computer. Differencing
`
`is provided by replacing the
`
`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. The destination device receives the transmitted
`
`15
`
`reduced segments as messages
`
`in a receive message queue and reconstructs
`
`the
`
`data stream.
`
`Synchronization
`
`between the differencing
`
`caches of the devices is
`
`:~
`
`not required as the communication
`
`is asynchronous
`
`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
`
`20
`
`and queues the segment as a message.
`
`Page 3 of 55
`
`39
`
`

`

`Attorney Docket No.: 5577-116
`
`METHODS, SYSTEMS AND COMPUTER 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
`
`5
`
`low-speed or wireless communication
`
`link between two computers using a
`
`message queue.
`
`Background of the Invention
`Traditional mainframe
`computer configurations
`provided for user interface
`
`10
`
`to the computer
`
`through computer
`
`terminals which were directly connected by
`
`wires to ports of controllers
`
`connected by channels
`
`to the mainframe
`
`computer. 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
`
`15
`
`shift
`
`in processing include local or wide area networks which interconnect
`
`individual work stations where each workstation has substantial
`
`independent
`
`processing capabilities.
`
`This shift may be further seen in the popularity of the
`
`Internet which interconnects many processors
`
`and networks of processors
`
`through
`
`devices such as, for example,
`
`routers.
`
`At the same time that processing power was becoming more distributed
`
`there was also an increase in the popularity of mobile computing.
`
`The use of
`
`laptops, notebooks, Personal Digital/Communication
`
`Assistants
`
`(PDAsIPCAs)
`
`and
`
`20
`
`Page 4 of 55
`
`

`

`other portable devices has led to an increase in demands
`
`for wireless
`
`communications. Wireless communication
`
`allows a user freedom to move within
`
`the wireless environment while remaining "connected"
`
`to a network.
`
`Furthermore,
`
`a wireless connection to a network allows a portable processor user the
`
`5
`
`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 high cost per byte of communications,
`
`slow
`
`response time,
`
`low bandwidth and unreliability which all hamper use of wireless
`
`10
`
`technology.
`
`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 becoming more frequent
`
`that a network linking two
`
`devices wishing to communicate may include a low through-put
`
`component
`
`such
`
`15
`
`as a wireless network link.
`
`Communications
`
`between devices
`
`such as computers
`
`are typically
`
`disadvantaged
`
`particularly on lower through-put
`
`network legs, such as wireless
`
`legs (or highly congested legs which are effectively bandwidth limited), where
`
`bandwidth limitations
`
`result
`
`in slower
`
`response time for communications
`
`between
`
`20
`
`the computers.
`
`In the extreme, protocol
`
`time outs 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 communication
`
`between applications
`
`executing on computers
`
`exacerbates
`
`the weaknesses of the wireless technology.
`
`25
`
`Communications
`
`are further complicated where a plurality of applications
`
`executing on a computer perform operations
`
`requiring transmission
`
`of data streams
`
`over a shared port to an external communication
`
`link, on occasion with
`
`interruptions
`
`in session connections.
`
`It is known to provide for this shared access
`
`using asynchronous message queuing systems such as International Business
`
`30
`
`Machine Corporation's Message Queuing Series ("MQSeries"),
`
`Telecommunications
`
`Access Method ("TCAM"), or Information Management
`
`Page 5 of 55
`
`/)
`
`2
`
`

`

`Systems ("IMS"), which enable
`
`applications
`
`to queue data for transport
`
`(transmission)
`
`to a partner destination computer device on an external
`
`communication
`
`link such as a network. Using asynchronous message queuing,
`
`the
`
`external connection between the source computer and the destination computer
`
`5
`
`typically does not have to exist at the time of submission of a data stream message
`
`for transmission
`
`and the source or sending device is not required to synchronously
`
`wait for a response from the destination 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
`
`10
`
`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 the 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
`
`device has assumed responsibility
`
`for the message.
`
`Objects and Summary of the Invention
`it is one object of the present
`In view of the above limitations,
`
`invention to
`
`provide for improved performance
`
`for data communications
`
`in a low-speed
`
`communication
`
`environment
`
`such as wireless communications.
`
`It is a further object of the present
`
`invention to support such
`
`communications where the communicating
`
`applications may be only intermittently
`
`connected.
`
`It is an additional object of the present
`
`invention to support such
`
`communications where the external communication
`
`link used for communication
`
`is
`
`shared by different applications.
`
`In view of these and other objects,
`
`the present
`
`invention provides methods,
`
`systems and computer program products
`
`supporting differencing data
`
`15
`
`20
`
`25
`
`30
`
`Page 6 of 55
`
`1/
`
`3
`
`

`

`5
`
`10
`
`15
`
`20
`
`25
`
`communications
`
`using a message 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 ofa data stream
`
`between the application on the source device and an application on the destination
`
`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. Differencing
`
`is provided by
`
`replacing the 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.
`
`The intercept
`
`system on the receiving end at the destination 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 the 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 applications 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 asynchronous
`
`communications
`
`and, if a
`
`reduced segment
`
`is not recognized,
`
`retransmission
`
`of the complete segment using
`
`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
`
`30
`
`differencing data communications
`
`using a message queue. A data stream having
`
`an associated type is intercepted (received)
`
`from a host application prior to
`
`Page 7 of 55
`
`4
`
`

`

`transmission
`
`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 associated with the plurality of segments are then plaeed 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
`
`computer,
`
`the selected segment
`
`format of the reduced segment was known to the destination
`cache if it
`
`is dequeued and placed in a differencing
`
`has not previously been transported.
`
`The message identifiers
`
`associated with the
`
`plurality of segments may be the associated segments themselves
`
`or they may be
`
`pointers
`
`to a location in memory where associated segments can be found.
`
`In one embodiment
`
`of the present
`
`invention,
`
`the system 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 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 the identifier of the selected segment
`
`is in the differencing index. A pointer may
`
`also be placed in the differencing index enabling the 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 the differencing index if the differencing cache exceeds a
`
`size criteria.
`
`In one embodiment
`
`of the present
`
`invention,
`
`reducing a segment
`
`includes replacing the selected segment with the identifier associated with the
`
`5
`
`10
`
`15
`
`20
`
`25
`
`w r
`
`-s
`
`"lll.:'
`
`~£S;
`'J~~
`~''::
`?rl~
`
`'.........
`
`~i
`~~
`~J
`~1
`=..-
`
`30
`
`selected segment
`
`to provide the reduced segment
`
`if the selected segment has
`
`Page 8 of 55
`
`5
`
`

`

`previously been emitted and providing the selected segment as the reduced
`
`segment
`
`if the selected segment has not previously been emitted.
`
`In a further embodiment
`
`of the present
`
`invention,
`
`the message queue
`
`receives messages
`
`from a plurality of data streams and asynchronously
`
`emits
`
`5
`
`(transmits)
`
`the messages 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.
`
`In another embodiment
`
`of the present
`
`invention,
`
`a message is received from
`
`the destination computer
`
`indicating whether
`
`the destination computer had a
`
`10
`
`segment
`
`in memory corresponding
`
`to the emitted identifier. The selected segment
`
`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
`
`15
`
`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 the
`
`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 another aspect of the present
`
`invention,
`
`the destination computer
`
`receives the emitted reduced segment and reconstructs
`
`the selected segment
`
`from
`
`the received reduced segment. The reconstructed
`
`selected segment
`
`is placed in a
`
`received message queue. The data stream is then reconstructed
`
`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 the destination computer
`
`if the reduced
`
`segment does not contain the selected segment. The reduced segment
`
`is replaced
`
`with the segment associated with the reduced segment
`
`message is emitted to the device from which the reduced segment
`
`if available. Otherwise,
`is received
`
`a
`
`requesting transmission
`
`of the selected segment
`
`if the segment associated with the
`
`reduced segment
`
`is not available. Data stream reconstruction may include
`
`20
`
`25
`
`30
`
`Page 9 of 55
`
`6
`
`

`

`integrating segments
`
`from the received message queue into objects. The
`
`reconstructed
`
`selected segment may be de queued from the received message queue
`
`after providing the reconstructed
`
`selected segment
`
`to the reconstructing
`
`step. The
`
`destination computer may provide a differencing
`
`index and differencing
`
`cache in a
`
`5
`
`manner analogous
`
`to that described for the source computer.
`
`In a further aspect of the present
`
`invention,
`
`a method is 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 with the current
`
`10
`
`version. The source computer determines
`
`if previous versions of the file having
`
`associated file segments are available to the source computer and if the destination
`
`computer has one of the previous versions of the file available. A first file segment
`
`of the 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 one embodiment
`identifier
`is calculated for each of the file segments associated with the current
`
`of the file transfer aspects of the present
`
`invention,
`
`an
`
`version and the calculated identifiers
`
`are placed in a segmenting index. The
`
`calculated identifiers
`
`are compared to a reference identifier based on one of the
`
`associated file segments of the previous 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 each of the file
`In one embodiment,
`is calculated for each of the file segments associated with the current
`
`segments of the current version to be transferrred.
`
`an
`
`identifier
`
`15
`
`20
`
`25
`
`30
`
`version. A segment
`
`length for each of the file segments is also calculated and
`
`placed in the segmenting index associated with the calculated identifiers.
`In a further embodiment of the file transfer aspects of the present
`
`invention,
`
`an identification
`
`of the previous version of the file is transmitted to the destination
`
`Page 10 of 55
`
`\/
`
`7
`
`

`

`computer. A messsage is then received from the destination computer containing
`
`an indication of whether
`
`the previous version of the 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 previous
`
`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
`
`communication
`
`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
`
`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
`communications
`from the source device perspective
`
`according to an embodiment
`
`data
`
`invention;
`of the present
`./
`FIG. 2 is a block diagram of a communication
`going data communications
`from a destination device perspective
`
`system for differencing on-
`
`according to one
`
`of tlJ..l!present invention;
`embodiment
`FIG. 3{a
`
`flow chart
`
`illustrating operations
`
`carried out by a source device
`
`of the present
`according to an?bOdiment
`FIG. <fis a flow chart illustrating
`
`invention;
`
`operations carried out by a source device
`
`stream according to an embodiment
`for segmentin~ata
`FIG. 5 is a flow chart illustrating operations
`
`..,(?
`
`of the present
`
`invention;
`
`carried out by a source device
`
`5
`
`10
`
`15
`
`20
`
`25
`
`for reducing segl1lerlts according to an embodiment
`FIG. 6rsa
`
`illustrating operations
`
`flow chart
`
`of the present
`
`invention;
`
`carried out by a destination
`
`to an embodiment of the present
`side device acrg
`FIG. 7 is a block diagram of a communication
`
`invention;
`
`system according to a file
`
`30
`
`transfer aspect of the present
`
`invention;
`
`Page 11 of 55
`
`/
`
`8
`
`

`

`.>
`FIG. 8 is a flow chart illustrating operations
`
`carried out by a source device
`
`of the file transfer aspect of the present
`according to a~bodiment
`FIG. 9 is a flow chart illustrating operations
`
`carried out by a source device
`
`invention;
`
`5
`
`10
`
`in segmenting a file according to an embodiment
`
`of the file transfer aspect of the
`
`present
`
`inventi~"
`FIG. 10 is a flow chart
`
`illustrating operations
`
`carried out by a destination
`
`device according to an embodiment
`
`of the file transfer aspect of the present
`
`invention.
`
`Detailed Description
`
`of The Preferred
`
`Embodiments
`
`The present
`
`invention now will be described more fully hereinafter with
`
`reference to the accompanying
`
`drawings,
`
`in which preferred embodiments
`
`of the
`
`invention are shown. This invention may, however, be embodied in many different
`
`forms and should not be construed as limited to the embodiments
`
`set forth herein;
`
`15
`
`rather,
`
`these embodiments
`
`are provided so that this disclosure will be thorough 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, the present
`
`invention may be embodied as methods, devices
`
`(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 hardware aspects.
`
`invention will now be described with
`of the present
`An embodiment
`reference to the block diagram illustrations of FIG. 1 and FIG. 2 which show the
`Referring first to FIG.-l, a data source
`source and destination device respectively.
`application 20 executing on a source device such as a computer generates a data
`stream to be communicated
`over an external communication
`link such 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
`types of data streams including the illustrated ASCII type
`objects for different
`object 28 and other MIME type object 30. A variety of different
`
`type objects may
`
`be provided for different applications
`
`such as terminal emulators,
`
`e-mail
`
`20
`
`25
`
`30
`
`Page 12 of 55
`
`9
`
`

`

`applications, word processors,
`
`etc., each of which is configured to interface and
`
`communicate with segment
`
`framework object 26 to 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 embodiment
`
`of the present
`
`5
`
`invention is determined based on the contents of the data stream itself.
`
`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 the art with operations of message
`
`queue 32 being modified as will be described herein according to the teachings of
`
`10
`
`the present
`
`invention to provide for differenced data communications.
`
`An example
`
`of a message queue based transport
`
`Application No,0'\ \'\\) ~~~e)
`
`system is described in United States Patent
`SSTY til)
`
`entitled "Methods,
`
`docket Ii~ef
`
`of Queue to Qu~:.J_
`Systems and Computer Program Products for Synchronization
`hich i
`...
`fi
`.J.rl:iIII~I'1
`..
`"
`dh
`in b
`ommunications w ic
`C
`IS incorporate
`erein
`y re erence III Its entirety,
`t IS to
`)(
`be understood that message queue 32 is a queue associated With an output port or
`
`~~(O\
`15
`
`node connection to network 22 which may support message based transmissions
`
`for a variety of different data source applications 20 executing on the source
`
`computer. While operations will be described for a single data stream feeding
`
`message queue 32 for ease of understanding
`
`the present
`
`invention.,
`
`it is to be
`
`understood that the operations described herein may be duplicated for additional
`
`data streams and all of the separate data streams may share a common message
`
`queue 32 which may provide the capability 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.
`
`As will be described herein,
`
`the present
`
`invention applies data stream
`
`differencing to the data stream to reduce the volume of data transmitted over an
`
`link, such as a low-bandwidth Wireless link, Data stream
`external communication
`differencing is described in United States Patent Application No. 08/852,586
`
`20
`
`25
`
`30
`
`Page 13 of 55
`
`10
`
`/1
`
`

`

`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 United States Patent No. 5,754,774. These approaches use
`
`knowledge
`
`of the structure ofthe 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 stream from its cache of
`
`previously received segments. However,
`
`these approaches generally require
`
`synchronization
`
`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 reducing object
`
`34 for differencing the data stream corning out of message queue 32 according to
`
`the teachings of the present
`
`invention, While for the embodiments
`
`described
`
`herein,
`
`the reducing object 34 is illustrated as operating on output messages
`
`from
`
`message queue 32 it is to be understood 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
`
`into message
`
`queue 32 for transport, The reduced segments from reducing object 34 are, in turn,
`
`provided to an emitting object 36 for emitting (transmission)
`
`over network 22. As
`
`is generally known to those of skill in the art, an emitting object 36 in an
`
`asynchronous message queuing systems such as those suited for use with the
`
`present
`
`invention typically buffers a plurality of messages
`
`(segments)
`
`in a
`
`transmission
`
`buffer before transmitting
`
`the buffer contents over network 22. The
`
`size of the transmission
`
`buffer may, for example, be defmed by a network protocol
`
`specifying a packet size for transmissions
`
`over the communication
`
`network 22.
`
`Referring now to FIG. 2, a receive side system according to the teachings
`
`of the present
`
`invention will now be described. A scan segment object 40 receives
`
`a transmitted buffer containing messages
`
`transporting a data stream in a reduced
`
`segment
`
`format
`
`from network 22. As will be described further
`
`in reference to the
`
`flow charts herein,
`
`the scan segment object 40 outputs received segments
`
`to
`
`expanding object 42, The received reduced segments may contain the segment
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`Page 14 of 55
`
`11
`
`i 'J
`
`

`

`5
`
`10
`
`15
`
`20
`
`(i.e., the data) or an identifier ofthe segment. Expanding object 42 determines
`
`whether a received segment contains an identifier or the segment
`
`itself.
`
`If the
`
`segment contains an identifier, expanding object 42 determines whether
`
`the
`
`associated segment
`
`is available at the destination device and provides
`
`the expanded
`
`segment
`
`to message queue 44. Where the segment
`
`itself is received,
`
`the segment
`
`is
`
`directly passed to message queue 44 by expanding object 42.
`
`If a segment
`
`identifier
`
`is detected by expanding object 42 and the full segment
`
`is not available, a
`
`request
`
`for retransmission will be generated by expanding object 42 as will be
`
`described further herein. Messages
`
`from receive message queue 44 are in turn
`
`passed to combine object 46 in the illustrated embodiment. Combine object 46,
`
`like segment object 24 includes a combine framework object 48 and may include a
`
`plurality of type objects providing rules for combining associated types such as the
`
`illustrated ASCII
`
`type object 50 and MIME type object 52 which customize
`
`the
`
`combination
`
`operations of combine framework object 48 to reconstruct
`
`the data
`
`stream. The data stream from combine object 46 is then provided to data
`
`destination application 54.
`
`Operations
`
`for a source device for an embodiment of the present
`
`invention
`
`will now be described with reference to FIGs. 3-5. With reference to FIG. 3, at
`
`block 100 a data stream from a da