United States Patent [19]
`Bittinger et al.
`
`[54] DIFFERENCING CLIENT/SERVER
`COMMUNICATION SYSTEM FOR USE
`WITH CGI FORMS
`
`[75] Inventors: Reed Reed Bittinger; Michael Levi
`Fraenkel, both of Raleigh; Barron
`Cornelius Housel III, Chapel Hill;
`David Bruce Lindquist, Raleigh., all of
`NC.
`
`[73] Assignee: International Business Machines
`Corp., Armonk, NY.
`
`[ * ]
`
`Notice:
`
`The term of this patent shall not extend
`beyond the expiration date of Pat. No.
`5,754,774.
`
`[21] Appl. No.: 601,903
`[22]
`Filed:
`Feb. 15, 1996
`
`[51] Int. Cl.6 ...................................................... .. G06F 3/00
`[52] US. Cl. ............................... .. 395/200.33; 395/200.48
`[58] Field of Search ....................... .. 395/200.01, 200.48,
`395/200.47, 200.33, 200
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3/1993 Bordsen et al. ...................... .. 711/152
`5,193,162
`8/1993 Epard et al. .... ..
`.. 345/502
`5,241,625
`5,473,772 12/1995 Halliwell et al. .
`.. 395/712
`5,574,906 11/1996 Morris
`707/1
`5,600,834
`2/1997 Howard
`707/201
`5,611,038
`3/1997 Shaw et a1. ........................... .. 345/302
`
`FOREIGN PATENT DOCUMENTS
`
`0 665 670 A3 1/1995 European Pat. Off. ...... .. H04L 29/06
`
`OTHER PUBLICATIONS
`
`IBM Technical Disclosure Bulletin, Method to Reduce
`Changed Data Sent BetWeen Computer Systems, vol. 35,
`No. 1B, pp. 110—112.
`Austin, et al., File System Caching in Large Point—to—Point
`Networks, Software Engineering Journal, vol. 7, No. 1, pp.
`65—80 (Jan. 1992).
`
`US005859971A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,859,971
`*Jan. 12, 1999
`
`Nelson, et al., Caching in the Sprite Network File System,
`Operating Systems Review, vol. 21, No. 5, pp. 3—4 (1987).
`HuiZinga, et al., TWo—Level Client Caching and Discon
`nected Operation of Notebook Computers in Distributed
`Systems, SIGICE Bulletin, vol. 21, No. 1, pp. 9—14 (Jul.
`1995).
`Abstract, IBM Technical Disclosure Bulletin, Method for
`Transmitting Only Document Change Data, vol. 27, pp.
`844—846 (Jun. 1984).
`International Search Report.
`
`(List continued on next page.)
`
`Primary Examiner—Parshotam S. Lall
`Assistant Examiner—Kenneth R. Coulter
`Attorney, Agent, or Firm—Jerry W. Herndon
`
`[57]
`
`ABSTRACT
`
`A method, apparatus and computer program product for
`reducing the data transmitted over an external communica
`tion link from a ?rst application resident in a ?rst computer
`to a second application resident in a second computer. The
`method, apparatus and computer program product include
`storing a data stream from the ?rst application to be provided
`to the second application in response to a request from the
`second application in a cache resident in the ?rst computer
`to create a server base cache entry and in a cache resident in
`the second computer to create a client base cache entry.
`Requests from the second application are interrogated to
`determine if a client base cache entry corresponding to the
`interrogated request exists and to determine if a server base
`cache entry corresponding to the interrogated request exists.
`The response data stream is intercepted prior to transmission
`of the response on the external communication link and
`compared to the server base cache entry to provide differ
`ence data corresponding to the difference betWeen the inter
`cepted response and the server base cache entry. The dif
`ference data is sent over the external communication link
`and acquired by the second computer Which reconstructs the
`response data stream by combining the client base cache
`entry With the difference data to create a response data
`stream Which is provided to the second application.
`
`48 Claims, 19 Drawing Sheets
`
`ac m resperree
`= can at server
`ese em
`7
`
`No
`
`cerrrpure dmererree
`eerweerr server eeee
`cache emrv lay CGI
`request and response
`rrerrr we/o eemsr
`
`Update server base
`were entry wirrr m'rP
`data of response, sac
`of HTTP news and Null
`me CGI emererree data
`
`creere server nese
`cache emry by storing
`URL or CGI requeer,
`HrrP data or response
`lrom server and
`one 01 rm'P data
`
`Send response re (:51
`01 one of SSI base
`
`dmererroe dare
`
`Petitioner Microsoft Corporation - Ex. 1011, p.1
`
`

`
`5,859,971
`Page 2
`
`OTHER PUBLICATIONS
`
`IBM Sales Brochure G325—3595—00, printed Sep. 1995.
`
`HypterteXt Transfer Protoco1—HTTP/1.0, HTTP Working
`Group, Berners—IJee et a1.—Internet—Draft Basic HTTP.
`IBM Sales Brochure G325—3598—0 printed Sep. 1995.
`
`IBM ARTOur Technical OVerVieW_Re1eaSe 1_
`
`IBM Publication SB14—0110—00, 1995.
`
`Petitioner Microsoft Corporation - Ex. 1011, p.2
`
`

`
`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 1 0f 19
`
`5,859,971
`
`FIG. 1
`
`PRIOR ART
`
`TCP/ IP
`15
`
`Web Browser
`
`Web Server
`
`FIG. 2
`
`_
`
`_ _ _ _
`
`_
`
`_ _
`
`_ _ _ _
`
`_ .
`
`_ 0
`
`_ 0
`
`u m/ |
`
`_ S
`
`5 3
`
`S
`
`_ 0 r
`
`_ e _ S
`_ 2/ m
`_ W
`_ be
`
`_ B
`_ w _ W
`_ w
`
`_ 1/ w
`
`_ 3/ m _ C
`
`_ .llllllllllllllll'
`
`Petitioner Microsoft Corporation - Ex. 1011, p.3
`
`

`
`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 2 0f 19
`
`5,859,971
`
`FIG. 3
`
`100
`/
`
`Receive request from
`web browser
`
`Cache Entry Exist
`for Request
`
`No
`
`Is entry
`Coherent
`?
`
`111
`
`/
`
`V
`
`Send Cache entry
`to Browser as
`HTI'P data stream
`
`112
`\
`Send "Coherency Check"
`request to SS1 including
`Coherency Interval,
`CRC of cache entry
`and HTI'P request
`
`106
`/
`Send Request to Server
`Side Intercept Module
`(SS1) including HTTP
`request, Coherency
`Interval and Null CRC
`
`Petitioner Microsoft Corporation - Ex. 1011, p.4
`
`

`
`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 3 0f 19
`
`5,859,971
`
`160
`/
`Receive Response from
`SSI including Response
`Type, CR0 and Age
`
`FIG. 4
`
`Response
`Type
`‘?
`
`Coherent
`
`166
`/
`Update cache entry by
`updating Store Date
`Time = Current Date
`Time - Age received
`from SSI
`
`167
`\
`
`Receive data stream
`and store
`
`170
`
`Yes
`
`Cache entry exist
`for data stream
`
`171
`
`Delete old
`cache entry
`
`172
`\
`Update Cache with
`received data including
`H'l'l'P data, CRC of HTTP
`data and Store Date
`Time = Current Date
`Time - Received Age
`
`173
`/
`l
`Create Cache Entry
`by storing HTTP data
`received, URL of HTTP
`data, CRC of HTTP data
`and Store Date Time =
`Current Date ‘?me - Age
`
`174
`/
`Send HTTP data of
`Cache Entry to Browser
`as H‘lTP data stream
`
`CD
`
`Petitioner Microsoft Corporation - Ex. 1011, p.5
`
`

`
`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 4 0f 19
`
`5,859,971
`
`Reoelve Request from
`Cllent Slde Intercept
`Module (CSI) Including
`Coherency Interval,
`CRC and HITP data
`
`F IG- 5
`
`126
`
`I
`
`Send HITP
`request to
`server
`
`Send "coherenf'
`response to CSI
`
`137
`/
`Send 'streom"
`response to CS!
`Including CRC of SSI
`entry. Age of SSI entry
`and HTTP data of 88!
`entry
`
`Petitioner Microsoft Corporation - Ex. 1011, p.6
`
`

`
`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 5 0f 19
`
`5,859,971
`
`Recelve response from /
`server and store HTTP
`data stream and
`calculate CRC of H“?
`
`l5]
`/
`r
`Update Store
`Date llme
`= Current
`Date llme
`
`152
`
`Delete stored
`response
`from server
`
`Delete HTTP data of
`server cache entry
`
`154
`/
`Update Server cache
`entry wlth CRC of server
`response, HI'IP data of
`sewer response and Store
`Date llme = Current
`Date llme
`
`146
`
`Create a Sewer Cache
`Entry by storing the CRC
`of recelved HTIP data.
`the HlTP data and the
`Stored Date llme =
`Current Date llme
`
`FIG. 6
`
`156
`/
`Send 'coherent“ response
`wtth Age = 0
`
`l
`
`157
`/
`Send "stream" response
`lncludlng HTlP data recetved
`from sewer, CRC of HTTP
`data and Age = 0
`
`Petitioner Microsoft Corporation - Ex. 1011, p.7
`
`

`
`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 6 0f 19
`
`5,859,971
`
`200
`
`FIG. 7
`
`Receive HiTP request
`from browser
`
`206
`
`Send HTiP
`Request to SSI
`
`No
`
`client base
`cache entry exist
`for CGl request
`
`212
`
`21 1
`
`Set CRC *0 send 1°
`SSI to null
`
`Set CRC to send to SSI
`to CRC of client base cache
`entry for Get request
`
`213
`
`Send CGI request to SSI
`Including HiTP request and
`CRC of client base
`cache entry
`
`V
`
`Petitioner Microsoft Corporation - Ex. 1011, p.8
`
`

`
`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 7 0f 19
`
`5,859,971
`
`267
`/
`Pass HTTP response
`to browser
`
`FIG. 8
`
`260
`/
`Receive response to CGI
`request from SSI including
`response type and CR0
`of server base form
`
`response to a
`CGI request
`'2
`
`Yes
`
`266
`/
`
`Receive response and store
`HTTP data, CGI difference
`data and CR0
`
`270
`
`Yes
`
`a client base
`form exist for
`CGI request
`
`Does
`CRC of client
`orm match CRC of
`server form
`
`Rebase the client bas =
`cache by storing the
`HTTP data received
`from the SSI and
`the CRC received
`from the SSI
`
`271
`/
`Create a client base
`cache entry by storing
`the URL of the CGI
`request, the CRC of
`the HTTP data from
`the SSI and the HTTP
`data from the SSI
`
`277
`/
`r
`Reconstruct the HTTP
`iresponse from the web
`server by merging the
`CGI difference data to ‘
`the client base form
`HTTP data to create
`the HTTP data stream
`278
`r
`/ 1
`Send reconstructed
`response to browser
`as HTTP data stream
`
`Ct}
`
`Petitioner Microsoft Corporation - Ex. 1011, p.9
`
`

`
`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 8 0f 19
`
`5,859,971
`
`Fl G 9
`'
`
`220
`/
`Fieceive CGI request from
`CSI including CFiC of
`client base cache entry
`and HTTP data of request
`
`221
`A
`i
`Send CGI request
`to web server
`
`'
`
`HG‘
`10A
`
`FIG.
`10B
`
`230
`l
`Receive response from
`server and store HTTP
`data, CRC of HTTP
`data and null CGI
`difference data
`
`G _ 1 0 A
`
`request a
`CGI request
`
`236
`j c
`Send HTTP
`response to CSI
`
`Petitioner Microsoft Corporation - Ex. 1011, p.10
`
`

`
`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 9 0f 19
`
`5,859,971
`
`245
`
`(iqggérgfsgggzi
`
`'
`Compute difference
`between server base
`cache entry for CGI
`request and response
`from web server
`
`ls
`server rebasing
`required
`
`7
`Update server base
`cache entry with HTTP
`data of response, CFlC
`of HTTP data and Null
`the CGI difference data
`
`F
`
`1
`
`241
`l
`J
`Create server base
`cache entry by storing
`URL of CGI request,
`HTTP data of response
`from sewer and
`CFlC of HTTP data
`
`l
`
`250
`
`ls
`CRC of SSl =
`CFlC of CSI
`
`Yes
`
`251
`\
`
`l
`
`l
`
`Null
`HTTP data
`
`253
`l j
`HTTP data set
`to received
`HTTP data
`
`252
`/
`Send response to CSl
`of CR6 of SSl base
`cache entry, HTTP a
`data and CGI
`difference data
`
`7
`
`Petitioner Microsoft Corporation - Ex. 1011, p.11
`
`

`
`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 10 0f 19
`
`5,859,971
`
`_
`
`_
`
`,
`
`" _ _ _
`
`u ‘ n _ 6 _
`
`_ } V _ _ A r _
`
`@ m,
`
`
`
`
`
`_.|||.L. l l | I l l a I | l l | I l I 1 1 1 I I ll 1 I l | | ll... t I | I I | | l l l I | | | | | l IIJ
`
`_ >08 08/ n n \ m8 <8/ “
`
`_ / \ u _ \ \ _
`
`_ u _ \ _
`_ _ _ _
`
`n 9 v 18 u n E) i u
`u k {8 u n 61 n ‘ n
`
`
`
`_P ON 3 _ n 8 | 1 Ion, ||||||| | I u
`
`u _ _ \ m8 <9; _
`
`_ 9 ‘ n _ 1 ‘ _
`
`_ _ _
`
`" 2% 0%,, _ mm H \ mam < / n
`
`_ I _
`
`_ 55% mm; 2% 08 / am _ n 60 \ m8 <9; 596% mm; H
`
`_ mm
`
`> _ _ 1 r _
`
`_ 6 _
`
`Petitioner Microsoft Corporation - Ex. 1011, p.12
`
`

`
`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 11 of 19
`
`5,859,971
`
`Petitioner Microsoft Corporation - Ex. 1011, p. 13
`
`Petitioner Microsoft Corporation - Ex. 1011, p.13
`
`

`
`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 12 of 19
`
`5,859,971
`
`N5mommom
`
`<9.G_n_
`
`com
`
`Sm
`
`mom
`
`“me@590
`
`Exoom_m¢._
`
`
`
`Em>mcm6..:m>>
`
`Exoom.3.m:0
`
`<2dz
`
`
`mm?.G_..._
`2.0_u_
`
`
`
`
`
`fixoom.a_%_:s_>3UmummbHmxoomRom
`
`
`
`
`
`
`
`._mE_._._>_8<mEEmxm_cozomccoomc_Eooc_Exoom_m9_uu<umxoomam..83Eo>mor:..m__:35_mo._9._:_.._E9:$20
`
`
`
`
`
`
`
`
`
`
`
`m5
`
`._=:E9:228
`
`HmxoomRm.xmfi
`
`
`
`momcoum>_wom._San.Sm
`
`coEma
`
`umxoomxw_aE_m
`
`
`
`
`
`Hwxoow_mm._m>oEmm_.8._.._:_2xm_aE_mm93.0
`
`
`E.Em>mE2E0...Hmxmuom39Exoom_m_.E_>
`
`mc_Emxm
`
`989.:
`
`_m:t_>252
`
`
`
`Exoow_mmg0_mO.0tflm
`
`
`
`9:._O_.CO_uOC_.d
`
`
`
`Hoxoom_m::_>
`
`
`
`
`
`~IloII!.|.lIo|oIl.II.uuo|uuloIInII.Ilo|uuII-|-.|cal-‘anal:-Ilau'.|uaIlc|uola|-lcl|o|uI|.|C.|.
`
`
`
`
`
`Petitioner Microsoft Corporation - Ex. 1011, p.14
`
`Petitioner Microsoft Corporation - Ex. 1011, p.14
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 13 of 19
`
`5,859,971
`
`
`
`mm:._®_u_
`
`oz
`
`m5
`
`mmm
`
`cozocaam5.8anew
`
`«mm
`
`
`
`9.Emuozone
`
`
`
`
`
`__m._ma._>acgwas:>:>_.um
`
`_.5mum
`
`
`
`_m:t_>v:m_29:_oocmo
`
`.0wC_.._O0w_O
`
`_m:t_>
`
`.mLmxoom
`
`xm_a_.._:Em93.0
`
`
`
`umxoom_m3t_>
`
`
`
`
`
`ucm..m_...mxoomExoomxm_a_._:E
`
`
`
`amxoom_m2xm_aE_m.2Emam_mcm_mUcm
`
`m..m_munew320fixoom_m.:t_>me.
`
`
`
`gmxoomm:_..m_xm
`
`
`
`Em>o_m:t_>
`
`Petitioner Microsoft Corporation - Ex. 1011, p.15
`
`
`
`
`
`a'.I|a|I:Il.|..|ol-null:IlIIIlI!|.'I'I!o!.|.|.l.u|uuulIoI|oluIu|-‘|.|.|.lII.!l.!
`
`
`
`
`
`Petitioner Microsoft Corporation - Ex. 1011, p.15
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 14 of 19
`
`5,859,971
`
`«mm
`
`mmmooi
`
`moacmmo5
`
`._mw>>o50:“
`
`.San\
`
`w>_momm..uw>_mommmsegm
`
`xm_aE_mm_>fiasco.
`
`
`
`
`umxoom_w:t_>
`
`Ew>mm5
`
`
`
`_m3.__>m._o...._m>>
`
`xm_aE_mm5:0Em>o
`
`
`
`Exoom_m:t_>
`
`mum
`
`mmm
`
`own
`
`mam
`
`oc_Emxm_
`
`Em>o9:
`
`
`
`_m:E>m5..=m>>
`
`-E_.._E9:coEm>w
`
`
`
`umxoom_m:t_>xwa
`
`9%9:._nm:_n_..
`
`
`
`ants.a_%_:E
`
`9:Eumsmsc
`
`fixoom
`
`U0>_0O®mEma
`
`
`
`Exoow_m_.E_>xma
`
`_mm9:9.
`
`-_.._:E05m_>am9:2$03699:_._ucmm._
`xm_n__=:Em._2mm._o_.
`
`fixoom_m:t_>
`
`cmBsbmcoo
`
`
`
`._mmmmmmE._o:o__
`
`mmcoamm.
`
`9:228
`
`xm_u=_:E
`
`
`
`Hoxoom_m:t_>
`
`mmmooi
`
`
`
`mmcoqmm:9....
`
`05._mmo_O__
`
`xm_a_=:E
`
`
`
`gmxoow_m:t_>
`
`
`
`am9.:__o>_8om__
`
`._::E9.:m_>mmcoamm.
`
`
`
`Hmxoow_m_.E_>xmfi
`
`omm
`
`9:2m_mo
`
`xm_aE_m
`
`
`
`Bxoom_m::_>
`
`9:..mmo_0_.
`
`xm.aE_m
`
`
`
`amxoom_m::_>
`
`Emu2:..:m:_n___
`
`xm_aE_mme.EUwamz.
`oz.m_>.3305me.9mmcoamm.9:__u:mm__
`
`mawsauoxoom_m:t_>
`
`
`
`
`Hoxoom_m:t_>xm_aE_m
`
`Petitioner Microsoft Corporation - Ex. 1011, p.16
`
`Petitioner Microsoft Corporation - Ex. 1011, p.16
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 15 of 19
`
`5,859,971
`
`9.0_n_
`
`
`
`
`
`Hoxoom_m._..F__>
`
`fimaumm2.:xo_a_=:Em_>«$359.
`
`mmmooi
`
`momEm
`
`_mO__m>_momm__
`
`98
`
`cmSzbmcoo
`
`
`
`._wmmmmmE._o.:m_.
`
`mmcoamm.
`
`9:228
`
`xm_aE_m
`
`
`
`Hmxoom_m:t_>
`
`mmoooi
`
`omcoaww.m5
`
`05_.mwo_O__
`
`xm_aE_m
`
`
`
`umxoom_m:t_>
`
`m:_Emxm_
`
`Em>wm5
`
`_m:t_>m.2.._m>>
`
`xw_aE_m9:coEm>o
`
`
`
`uwxoom_w:t_>
`
`9%9:..cm:_u___
`
`
`
`_m:t_>xm_aE_m
`
`
`
`mama.Exoow
`
`9:Eumsmac
`
`vmzmommEma
`
`9ummauo.m5._n:mm__
`
`
`
`m£m_>Eammme.
`
`
`
`
`
`amxoom_m:t_>xo_aE_m
`
`
`
`aoxoom_m3t_>
`
`._m>._mw$.13Ow
`
`xoaE_mm__2m2o__
`
`
`
`Ezomme.__m>_momm__
`
`9.:m_>mw:oamm._
`
`
`
`
`
`Hmxoom_m:t_>xm_aE_m
`
`Em8mnewmom
`
`EmwBRmmum
`
`
`
`
`
`
`
`Hmxoom_m::_>Hmxoom_m:t_>_m3.__>xw_a_=:E“oxoom_m:t_>xma
`
`9.:228m5__mmo_o..Emum.£__cm:_n_..9omcoamm.9:__ucmm__
`
`
`
`xm_%._:Exw_aE:Em£.:_um:.m:U-E:E9:m_>_.momay
`
`030:oHwxoom
`
`Petitioner Microsoft Corporation - Ex. 1011, p.17
`
`Petitioner Microsoft Corporation - Ex. 1011, p.17
`
`
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 12,1999
`
`Sheet 16 0f 19
`
`5,859,971
`
`FIG. 16-2
`
`420
`
`1
`
`Send
`
`1
`
`427
`/
`
`'
`Add data
`.
`to “dual
`socket queue
`
`1
`
`428
`
`Return
`
`FIG. 16-1
`
`400
`
`Real socket
`needed
`7
`
`No
`
`406
`/
`
`v
`Create
`real socket
`
`l
`
`408
`
`Add real
`socket to
`event list
`
`409
`/
`
`r
`
`Connect virtual
`to real socket
`
`}
`r
`Return
`
`410
`)
`
`1
`
`Petitioner Microsoft Corporation - Ex. 1011, p.18
`
`

`
`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 17 0f 19
`
`5,859,971
`
`FIG. 16-3
`
`430
`
`Receive
`
`Data on
`input queue
`
`Mark socket
`"Closed"
`
`443
`
`Return
`"Closed"
`
`Return
`Nothing
`
`FIG. 16-4
`
`445
`
`data or a "close'
`
`Yes
`
`Wait for
`virtual event
`
`if
`448
`
`Return
`
`Petitioner Microsoft Corporation - Ex. 1011, p.19
`
`

`
`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 18 0f 19
`
`5,859,971
`
`450
`
`Any data
`in queue
`
`Move virtual socket
`data to real buffer
`
`Real Buffer
`full
`
`Yes
`
`Send real
`buffer data
`
`FIG. 17-1
`
`‘Move socket header
`to real buffer
`
`470
`
`Any
`data on other
`queues
`?
`
`Yes
`
`Petitioner Microsoft Corporation - Ex. 1011, p.20
`
`

`
`U.S. Patent
`
`Jan. 12, 1999
`
`Sheet 19 of 19
`
`5,859,971
`
`FIG. 17-2
`
`480
`
`
`
`485
`
`Multiplex
`socket
`
`?
`
`
`
`
`Add "Close" indicator
`
`to socket queue
`
`487
`
`488
`
`490
`
`real socket
`
`Simplex
`socket
`
`
`
`
`
`
`
`
`
`
`Last
`multiplex virtual
`Socket
`?
`
`Close and delete
`rea‘ Socket
`
`k t
`I
`R
`emove ma SOC, 6
`from real event list
`
`492
`
`
`
`
`
`
`
`
`
`Mark the
`
`socket closed
`
`498
`
`496
`
`_
`Start multiplex
`activity timer
`
`Petitioner Microsoft Corporation - Ex. 1011, p.21
`
`Petitioner Microsoft Corporation - Ex. 1011, p.21
`
`

`
`5,859,971
`
`1
`DIFFERENCING CLIENT/SERVER
`COMMUNICATION SYSTEM FOR USE
`WITH CGI FORMS
`
`FIELD OF THE INVENTION
`
`The present invention relates to methods of communicat-
`ing between applications resident on different computers
`such as a web browser and a web server. More particularly
`the present
`invention relates to differencing methods of
`communication over an external communication link
`
`between two computers.
`
`BACKGROUND OF THE INVENTION
`
`The recent publicity and emphasis on the “information
`superhighway” has increased awareness and acceptance of
`the Internet as a mass communication media. This broad
`
`based recognition of the Internet as a viable media for
`communication and interaction across multiple networks has
`also created a large established user base built upon the
`Internet standardized protocols for interaction between com-
`puter networks.
`The paradigm for the Internet is that of a client-server
`relationship where Internet clients (browsers) communicate
`with Internet servers. To provide greater access to the
`Internet the communication protocols and languages utilized
`by the clients and servers have become standardized. These
`protocols include the Hyper-Text Transfer Protocol (HTTP),
`which is the communication protocol used for communica-
`tions between clients and servers, and the Transfer Control
`Protocol/Internet Protocol (TCP/IP) the TCP portion of
`which is the transport specific protocol for communication
`between computers or applications. Also standardized is the
`language in which clients and servers communicate which is
`called Hyper-Text Markup Language (HTML). Because
`these protocols and language are machine independent, and
`utilize a connectionless best-efforts protocol
`to sending
`information, each transaction is fully self contained. Thus,
`for example, each message from a client contains informa-
`tion about the capabilities of the browser and is independent
`of any other communications for the communication to be
`completed. This self-contained nature of the communica-
`tions between a client and a server may be referred to as
`“stateless” communications and increases the amount of
`data which must be transferred between a client and a server
`
`for a given communication.
`In the context of the World Wide Web client/server
`applications the client may be a web browser which acts as
`the user interface. The web browser sends user requests to
`the appropriate web server and formats and displays the
`HTML data returned from the web server. The web browser
`
`also evaluates the HTML data to determine if there are any
`embedded hyper-link statements in the HTML data which
`would require subsequent browser requests which would
`then be initiated by the browser. A web server acts as the
`server for the client and processes the web browsers requests
`and returns the requested response as an HTML data portion
`of a HTTP data stream.
`
`As an example of a typical world wide web communica-
`tion the case of a web browser initiating a request for a
`“home page” from the web server illustrates the basic
`relationship between HTTP, HTML, TCP and the web
`browser and server. When the user of the web browser
`
`the web
`requests information from a specific web site,
`browser initiates communication with the web server by
`sending a “get” request to the web server specifying the
`Universal Resource Locator (URL) of the desired web site
`
`2
`which, for purposes of this example, may be a “home page.”
`The URL acts as the address of the web site and is unique
`throughout the Internet. The web server would then obtain
`and supply the web browser with the HTML data corre-
`sponding to the home page specified by the URL. This
`operation may involve further communications on the Inter-
`net by the Internet web server or the URL may specify the
`server which is in the local network to which the browser is
`attached. The web browser would then evaluate the HTML
`data received as an HTTP data stream from the web server
`
`to see if there were any embedded hyper-links such as an
`icon or an image and, if such a hyper-link exists would
`initiate requests specifying the URL of the hyper-link to
`obtain the specified data. This data would then be incorpo-
`rated into the home page and displayed to the user. As is seen
`in this simple example, a single user input request by a web
`browser may result in multiple additional requests which are
`automatically carried out by the web browser in response to
`the receipt of the HTML data corresponding to the user input
`request.
`The basic communication structure for an Internet based
`
`system is depicted in FIG. 1. In FIG. 1 a web browser 10
`communicates with a web server 20 over a communication
`
`link 15. This communication link is typically a local area
`network connection, wide area network connection, a con-
`nection over telephone lines or a combination thereof. The
`web browser 10 communicates with the web server 20 using
`TCP/IP. For the majority of Internet communications a web
`browser communicates with a web server using the generic
`communication protocol HTTP which is transmitted
`between the web browser and the web server over the
`TCP/IP link between the web browser and the web server.
`The actual data transferred between the web browser 10 and
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`the web server 20 are HTTP data objects (e.g. HTML data)
`as described above. The web server 20 may be a proxy
`which receives web browser communications from a num-
`
`ber of web browsers and routes them to the appropriate
`server.
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`The popularity of the web browser/web server and their
`common information and transport protocols, HTML and
`HTTP, has lead to rapid acceptance of web technology as a
`universal
`interface for network access to information.
`
`Furthermore, because the protocols and language for com-
`munication between web browsers and web servers are
`
`standardized the communication protocols and language
`will be the same whether a user is using Netscape
`Navigator”, NCSA MosaicTM, WebExplorerTM or any other
`web browser as their web browser to access network infor-
`
`the large installed user base for web
`mation. Therefore,
`browsers combined with the connectivity of the Internet and
`the ease of writing web application servers using the HTTP
`defined Common Gateway Interface (CGI)make web tech-
`nology very attractive for a large class of forms-based
`applications.
`At the same time that the Internet was growing in popu-
`larity and acceptance, mobile computing was also increasing
`in popularity. The use of laptops, notebooks, Personal
`Digital/Communication Assistants (PDAs/PCAs) and other
`portable devices has lead to an increase in demands for
`wireless communications. Wireless wide area networks,
`cellular communications and packet radio, however, suffer
`from common limitations if used in a web context. The high
`cost per byte of communications, slow response time, low
`bandwidth and unreliability all hamper use of wireless
`technology for the stateless communication protocol of the
`World Wide Web. Also, because the web protocol is stateless
`the amount of data per request and the number of commu-
`
`Petitioner Microsoft Corporation - Ex. 1011, p.22
`
`Petitioner Microsoft Corporation - Ex. 1011, p.22
`
`

`
`5,859,971
`
`3
`nication requests transferred over the wireless connection
`are larger than would be necessary if the communication
`were not self contained. Thus, combining wireless
`technology, or any low-speed communication technology,
`with web technology seems impractical as the strength of the
`web technology in its universal nature exacerbates the
`weaknesses of the wireless technology.
`OBJECTS AND SUMMARY OF THE
`INVENTION
`
`In view of the above limitations it is one object of the
`present invention to provide a communication system which
`reduces the amount of data to be transferred between appli-
`cations.
`
`invention to
`is an additional object of the present
`It
`provide a communication system which may be used in a
`web browser/server environment.
`invention to be
`It
`is a further object of the present
`compatible with existing communication protocols and lan-
`guages in a low speed or wireless communication system
`without requiring modification of web browser or web
`server applications.
`invention to
`It
`is an additional object of the present
`provide a communication system which reduces the amount
`of communication required between a web browser and a
`web server and thereby enhances performance of the com-
`munication system.
`In view of these and other objects, the present invention
`provides a method of reducing the data transmitted over a
`communication link from a first application resident in a first
`computer and to a second application resident in a second
`computer where the data is transmitted over an external
`communication link from the first computer to the second
`computer. One aspect of the present
`invention includes
`storing a data stream from the first application to be provided
`to the second application in response to a request from the
`second application in a cache resident in the first computer
`to create a server base cache entry. The data stream to be
`provided to the second application in response to a request
`from the second application is also stored in a cache resident
`in the second computer to create a client base cache entry.
`Requests from the second application are evaluated to
`determine if a client base cache entry corresponding to the
`interrogated request exists to provide a client base form.
`Requests from the second application are also interrogated
`to determine if a server base cache entry corresponding to
`the interrogated request exists to provide a server base form.
`The data stream corresponding to the response originated by
`the first application in response to the interrogated request
`from the second application is intercepted prior to transmis-
`sion of the response on the external communication link and
`compared to the server base form to provide difference data
`corresponding to the difference between the intercepted
`response and the server base form. The difference data is
`sent to the second computer over the external communica-
`tion link and the difference data transmitted over the external
`
`communication link sent by the first computer is acquired
`from the external communication link. The response data
`stream corresponding to the communication from the first
`application is reconstructed from the client/server specific
`data stream received over the external communication link
`
`by combining the client base form with the difference data
`received over the external communication link to create a
`
`response data stream corresponding to the intercepted
`response. The reconstructed data stream corresponding to
`the intercepted response is provided to the second applica-
`tion.
`
`4
`In a further aspect of the present invention, the second
`computer determines if the server base form is identical to
`the client base form and the server base form and the
`difference data are transmitted to the second computer over
`the external communication link if the server base form is
`not
`identical
`to the client base form. The intercepted
`response data stream corresponding to the response from the
`first application is then reconstructed by combining the
`server base form received over the external communication
`link with the difference data received over the external
`
`communication link to create a data stream corresponding to
`the intercepted response. The client base form correspond-
`ing to the interrogated request is also updated by storing the
`received server base form as the client base cache entry
`corresponding to the interrogated request.
`In a server rebasing aspect of the present invention, the
`first computer determines if the difference between the
`server base form and the intercepted response is greater than
`a predefined difference threshold. The server base form
`corresponding to the interrogated request
`is updated by
`storing the intercepted response data stream received from
`the first application as the server base cache entry corre-
`sponding to the intercepted request if the difference between
`the server base form and the intercepted response is greater
`than the predefined difference threshold. The comparison
`then utilizes the updated server base form.
`In an alternative embodiment of the present invention, a
`plurality of server base cache entries which correspond to
`the request from the second application are maintained. A
`request from the second application is interrogated to deter-
`mining if a plurality of server base cache entries exist
`corresponding to the request from the second application to
`provide a plurality of server base forms. The first computer
`determines if one of the plurality of server base forms is
`identical to the client base form and utilizes the one of the
`
`plurality of server base forms which is identical to the client
`base form if one of the plurality of server base forms is
`identical to the client base form.
`
`invention
`An additional embodiment of the present
`includes updating the server cache entry with the data stream
`from the first application in response to the request from the
`second application. Aplurality of difference data sets which
`correspond to the request from the second application and
`which represent the differences between successive server
`cache entries are maintained to provide archival difference
`data. Aplurality of CRC entries are also maintained wherein
`each of the plurality of CRC entries is associated with one
`of the plurality of difference data sets and uniquely identify
`the server base form from which the difference data set was
`
`derived. If a plurality of difference data sets and CRCs exist
`corresponding to the request from the second application
`and if one of the plurality of CRCs corresponds to a server
`base form which is identical to the client base form the
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`archival difference data corresponding to the CRC which
`corresponds to the client base form, the successive archival
`difference data sets and the difference data calculated for the
`
`60
`
`65
`
`current server base form and the response from the first
`application are sent to the second computer over the external
`communication link. The response data stream correspond-
`ing to the communication from the first application from the
`data stream received over the external communication link
`
`is reconstructed by successively combining the client base
`form with the difference data received over the external
`
`communication link to create a response data stream corre-
`sponding to the intercepted response. The client cache entry
`corresponding to the request from the second application is
`also updated with the reconstructed data stream.
`
`Petitioner Microsoft Corporation - Ex. 1011, p.23
`
`Petitioner Microsoft Corporation - Ex. 1011, p.23
`
`

`
`5,859,971
`
`5
`In alternative embodiments of the present invention, the
`first application comprises a web server and the second
`application comprises a web browser. Alternatively,
`the
`external communication link comprises a wireless commu-
`nication link. Furthermore, an alternative embodiment
`includes the request from the web browser comprising a CGI
`request.
`As will be appreciated by those of skill in this art, the
`above described aspects of the present invention may also be
`provided as an apparatus or a program product having
`computer-readable program means.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of a typical web browser/web
`server system;
`FIG. 2 is a block diagram of a web browser/web server
`system according to one embodiment of the present inven-
`tion utilizing a client intercept and a server intercept;
`FIG. 3 is a flow diagram depicting operations carried out
`by a client-side intercept module in a preferred embodiment
`of the present invention implementing a coherent caching
`system;
`FIG. 4 is a flow diagram depicting operations carried out
`by a client-side intercept module in a preferred embodiment
`of the present invention implementing a coherent caching
`system;
`FIG. 5 is a flow diagram depicting operations carried out
`by a server-side intercept module in a preferred embodiment
`of the present invention implementing a coherent caching
`system;
`FIG. 6 is a flow diagram depicting operations carried out
`by a server-side intercept module in a preferred embodiment
`of the present invention implementing a coherent caching
`system;
`FIG. 7 is a flow diagram depicting operations carried out
`by a client-side intercept module in a preferred embodiment
`of the present invention implementing a differencing data
`transfer system;
`FIG. 8 is a flow diagram depicting operations carried out
`by a client-side intercept module in a preferred embodiment
`of the present invention implementing a differencing data
`transfer system;
`FIG. 9 is a flow diagram depicting operations carried out
`by a server-side intercept module in