`ACACIATACA
`US005307413A
`
`United States Patent o9
`
`
`
`
`
`5,307,413
`
`
`
`[11] Patent Number:
`
`
`
`
`
`
`Apr. 26, 1994
`Denzer
`[45] Date of Patent:
`
`
`[56]
`
`
`
`
`
`
`
`
`
`
`Systems, Inc. (ICS, Inc.), 1930 E. Marlton Pike, Cherry
`
`
`
`
`
`Hill, N.J. 08003, (4 pages), no date.
`
`
`
`
`
`
`
`
`F. Jay, IEEE Standard Dictionary ofElectrical and Elec-
`
`
`
`
`
`
`tronics Terms, (ANSI/IEEE Std. 100-1984); (IEEE,
`New York, 1984, p. 695, “Protoco!”’).
`
`
`
`
`
`
`
`
`Primary Examiner—Bernarr E. Gregory
`
`
`
`
`
`Attorney, Agent, or Firm-——Weingarten, Schurgin,
`
`
`Gagnebin & Hayes
`
`
`ABSTRACT
`[57]
`
`
`
`
`
`
`A connection specific compression system is selectively
`
`
`
`
`
`
`implemented in connections having the greatest data
`
`
`
`
`
`redundancy and utilizes modularity in implementing
`
`
`
`
`
`data compression in a layered network communication
`
`
`
`
`
`system. A data compression facility is interfaced in the
`
`
`
`
`
`
`
`layered system and intercepts data at a protocol layer
`
`
`
`
`
`
`
`prior to the data being packetized for transmission. A
`system acting as a compression host comprises a data
`
`
`
`
`
`
`
`
`
`
`
`
`
`packet switch driver which intercepts application data
`
`
`
`
`
`
`
`packets passing over layered network interfaces and
`routes selected client application data packets to an
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`associated local compression process which hasan inte-
`
`
`
`
`
`
`
`
`gral network protocol and which compresses the data
`
`
`
`
`
`
`stream in accordance with a selected compression algo-
`
`
`
`
`
`
`
`
`rithm. The compressed data passes through the system
`
`
`
`
`
`
`
`
`network protocol and the packet switch driver subse-
`
`
`
`
`
`
`
`
`
`quently sends the compressed data back into the com-
`munications stream through a network driver. The
`
`
`
`
`
`
`compressed data passes across the network communica-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion channel and is received by a decompression host
`
`
`
`
`having peer compression/decompression capabilities.
`
`
`
`
`
`
`
`The peer compression process decompresses the re-
`
`
`
`
`
`
`ceived data and sendsit, via a second/decompression
`host resident packet switch driver, as though received
`
`
`
`
`
`
`
`
`from the network, into the decompression host system
`
`
`
`
`
`
`
`
`network protocol for connection with an application
`
`
`
`
`
`
`
`Tunning on the second host.
`
`
`
`
`
`
`
`
`
`
`
`Inventor:
`[75]
`
`
`(73] Assignee:
`
`[54] METHOD AND APPARATUS FOR ADDING
`
`
`
`
`
`
`DATA COMPRESSION AND OTHER
`
`
`
`
`SERVICES IN A COMPUTER NETWORK
`
`
`
`
`
`
`
`Philip C. Denzer, Wellesley, Mass.
`Process Software Corporation,
`
`
`
`Framingham, Mass.
`
`
`
`
`
`
`[21] Appl. No.: 733,104
`[22] Filed:
`Jul. 19, 1991
`
`
`
`
`[52]
`Int, C15ecessssesssessssee HO04B 1/66; HO4L 9/00
`
`
`
`
`
`
`[52] U.S. Che caccccccscccsccssssessssssssnssvesseesne 380/49; 380/9;
`
`
`
`
`
`370/109; 375/122
`
`
`[58] Field of Search «0.0... 380/4, 9, 25, 49, 50;
`
`
`
`
`
`
`
`
`395/21, 24, 25; 364/240.8, 242.94-242.96,
`
`
`
`
`
`274.9, 276.6, 940.61-940.62, 940.81, 972.4;
`
`
`
`
`
`373/122; 340/825.8, 825.5; 381/34, 35; 370/109
`
`
`
`
`
`
`References Cited
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`8/1985 McNamaraetal.......... 340/825.5 &
`4,533,948
`
`
`
`
`
`
`4,691,314
`9/1987 Bergins et al. ose 370/94
`
`
`
`
`
`
`5/1988 Friedmanet al.
`.- 375/8
`4,748,638
`
`
`
`
`
`
`5/1989 Larson et al.
`....
`. 340/825.8
`4,833,468
`
`
`
`
`
`
`
`4,972,473 11/1990 Bjiriet al. occu 380/9 X
`
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`Strass, Hermann, “D-A-T-A Compression,” DEC
`
`
`
`
`
`Professional, Feb. 1991, pp. 58-62.
`
`
`
`
`
`Turner, Steven E., ‘Small Is Beautiful: How V.42bis
`
`
`
`
`
`
`
`Cuts Costs,” Data Communications, Dec. 1990, pp.
`
`
`
`
`
`
`
`101-104.
`
`
`
`
`
`
`
`Welch,Terry A., “A Technique for High-Performance
`Data Compression,” Computer Magazine, vol. 17 No. 6
`
`
`
`
`
`
`
`(Jun. 1984), pp. 8-19.
`
`
`
`
`“Sotfware Product Description FCX Version 3.2,”
`
`
`
`
`
`brochure of Innovative Computer Systems, Inc., (ICS),
`
`
`
`
`
`1930 E. Marlton Pike, Cherry Hill, N.J. 08003, pp. 1-4,
`
`
`
`
`
`
`
`
`no date.
`
`
`
`
`
`
`“FCX-pcFCX-File Compression for VAX/VMXand
`MS-DOSSystems,” brochure of Innovative Computer
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`19 Claims, 9 Drawing Sheets
`
`WADE AREA NETHOAK(HAN
`
`Petitioner Valve - Ex. 1014, Page 1
`Petitioner Riot Games,Inc. - Ex. 1014, p. 1
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 1
`
`Petitioner Valve - Ex. 1014, Page 1
`
`

`

`U.S. Patent
`
`
`
`
`Apr. 26, 1994
`
`
`
`
`
`Sheet 1 of 9
`
`
`5,307,413
`
`
`
`HOST B
`HOST A
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SESSION
`
`
`
`
`
`
`
`NETWORK
`NETWORK
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`message
`
`
`
`
`
`packets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5
`
`3
`
`
`
`
`
`
`
`
`OS! MODEL
`
`
`
`
`Fig. 1
`
`
`(PRIOR ART]
`
`Petitioner Valve - Ex. 1014, Page 2
`Petitioner Riot Games,Inc. - Ex. 1014, p. 2
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 2
`
`Petitioner Valve - Ex. 1014, Page 2
`
`

`

`U.S. Patent
`
`
`
`Apr. 26, 1994
`
`
`
`
`Sheet 2 of 9
`
`
`5,307,413
`
`
`
`
`
`
`
`
`
`
`OS!
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PHYSICAL
`
`
`
`
`
`
`
`
`
`
`TCPAP
`
`
`
`PROCESS
`
`
`
`
`
`HOST-TO
`
`HOST
`(TCP)
`
`
`
`INTERNET (IP
`
`
`NETWORK
`
`
`ACCESS —>
`
`
`
`
`Fig. Ia
`
`
`(PRIOR ART)
`
`
`
`Petitioner Valve - Ex. 1014, Page 3
`Petitioner Riot Games,Inc. - Ex. 1014, p. 3
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 3
`
`Petitioner Valve - Ex. 1014, Page 3
`
`

`

`U.S. Patent
`
`
`
`
`Apr. 26, 1994
`
`
`
`
`
`Sheet 3 of 9
`
`
`5,307,413
`
`
`
`
`
`DATA
`
`
`
`
`TCP
`HEADER
`
`DATA
`
`
`
`TOP PACKET
`
`
`
`
`IP PACKET
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(LLCPDU)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`LLC PROTOCOL DATA UNIT
`
`
`
`
`
`
`MEDIA|ADDRESS/
`
`
`
`
`
`
`
`
`
`
`ACCESS
`|CONTROL
`
`
`
`
`
`
`CONTROL|HEADERS
`
`
`
`
`
`HEADER
`
`
`TCP/IP PACKETIZATION
`
`
`
`
`Fig, 2
`
`
`(PRIOR ART)
`
`Petitioner Valve - Ex. 1014, Page 4
`Petitioner Riot Games,Inc. - Ex. 1014, p. 4
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 4
`
`Petitioner Valve - Ex. 1014, Page 4
`
`

`

`U.S. Patent
`
`
`
`Apr. 26, 1994
`
`
`
`
`Sheet 4 of 9
`
`
`5,307,413
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`WIDE AREA NETWORK(WAN)
`
`
`
`
`Fig. 3
`
`
`(PRIOR ABT)
`
`Petitioner Valve - Ex. 1014, Page 5
`Petitioner Riot Games,Inc. - Ex. 1014, p. 5
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 5
`
`Petitioner Valve - Ex. 1014, Page 5
`
`

`

`U.S. Patent
`
`Apr. 26, 1994
`
`Sheet 5 of 9
`
`5,307,413
`
`NV
`
`ININID
`
`
`
`(NV)MHOMILINWHYJOM
`
`Petitioner Valve - Ex. 1014, Page 6
`Petitioner Riot Games,Inc. - Ex. 1014, p. 6
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 6
`
`Petitioner Valve - Ex. 1014, Page 6
`
`

`

`U.S. Patent
`
`
`
`Apr. 26, 1994
`
`
`
`
`Sheet 6 of9
`
`
`5,307,413
`
`
`
`24
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`COMPRESSION PROCESS (SERVICE MODULE) APPLICATION
`
`
`
`PROCESS
`
`
`
`
`
`
`
`
`
`NETWORKINTERFACE
`
`
`
`DRIVER
`
`28
`
`
`
`
`
`
`
`
`WIDE AREA NETWORK(WAN)
`
`
`
`Fig. 4a
`
`
`Petitioner Valve - Ex. 1014, Page 7
`Petitioner Riot Games,Inc. - Ex. 1014, p. 7
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 7
`
`Petitioner Valve - Ex. 1014, Page 7
`
`

`

`U.S. Patent
`
`
`|
`
`
`Apr. 26, 1994
`
`
`
`
`Sheet 7 of 9
`
`
`
`
`5,307,413
`
`
`
`
`
`
`
`RECEIVE AND
`
`
`EXAMINE DATA
`
`
`PACKET
`
`
`
`
`SHOULD
`
`
`DATA PACKET
`
`
`
`BE DIVERTED
`
`
`FOR COMPRESSION?
`
`
`
`
`
`
`
`
`
`
`
`
`
`DIVERT DATA
`PASS DATA PACKET
`
`
`
`PACKET TO
`
`THROUGH TO NETWORK
`
`
`
`
`
`COMPRESSION PROCESS
`
`
`FOR TRANSMISSION
`
`
`
`
`
`
`Fig. 5
`
`Petitioner Valve - Ex. 1014, Page 8
`Petitioner Riot Games,Inc. - Ex. 1014, p. 8
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 8
`
`Petitioner Valve - Ex. 1014, Page 8
`
`

`

`U.S. Patent
`
`
`
`Apr. 26, 1994
`
`
`
`
`Sheet 8 of 9
`
`
`5,307,413
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CONTROL
`
`
`MODULE
`
`
`
` COMPRESSION/
`
`
`DECOMPRESSION
`
`
`MODULE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` COMPRESSION
`
`
`
`
`
` PACKET SWITCH
`
`
`
`
`
`
`DRIVER INTERFACE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fig. 6
`
`Petitioner Valve - Ex. 1014, Page 9
`Petitioner Riot Games,Inc. - Ex. 1014, p. 9
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 9
`
`Petitioner Valve - Ex. 1014, Page 9
`
`

`

`U.S. Patent
`
`
`
`
`Apr. 26, 1994
`
`
`
`
`
`Sheet 9 of 9
`
`
`5,307,413
`
`
`
`54
`
`IN
`
`Sh
`
`co
`
`S
`
`Hee
`
`xS
`
`&
`
`DECOMPRESSION
`
`
`
`|_|
`
`2
`
`XN
`
`&
`&
`
`bs
`8
`
`:2za W
`
`
`
`ITHCOMPRESSION
`
`
`
` Sy
`
`
`
`bs
`21S
`
`Ly
`
`aE
`
`| N
`
`ES
`
`Petitioner Valve - Ex. 1014, Page 10
`Petitioner Riot Games,Inc. - Ex. 1014, p. 10
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 10
`
`Petitioner Valve - Ex. 1014, Page 10
`
`

`

`1
`
`
`METHOD AND APPARATUSFOR ADDING DATA
`
`
`
`
`
`
`COMPRESSION AND OTHER SERVICESIN A
`
`
`
`
`COMPUTER NETWORK
`
`
`
`5,307,413
`
`10
`
`
`
`FIELD OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`The present invention relates to data compression
`
`
`
`
`
`
`and in particular to data compression in the context of
`
`
`networked computers.
`BACKGROUNDOF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`Systems are known which provide for connectivity in
`
`
`
`
`
`
`and among networks of computerized equipment. Such
`
`
`
`
`
`
`systems, ideally, must accommodate a proliferation of
`different network interfaces and hardware, as nosingle
`
`
`
`
`
`
`
`
`
`“standard”is adopted universally.
`
`
`
`
`
`
`In order to permit computer systems to communi-
`cate,
`regardless of connection method or vendor-
`
`
`
`
`
`
`
`
`
`
`
`
`specific hardware implementation, or to permit differ-
`ent networks to communicate or be “internetworked”,
`
`
`
`
`
`
`
`
`
`
`modularized/layered solutions have been proposed for
`
`
`
`
`
`
`the problems associated with interconnectivity. Layer-
`
`
`
`
`
`
`
`ing divides the task of interconnection and communica-
`
`
`
`
`
`
`
`
`tion into pieces (layers), wherein each layer solves a
`
`
`
`
`
`
`piece of the problem or provides a particular function
`
`
`
`
`
`
`
`andis interfaced to adjacent layers. Each of the layersis
`responsible for providing a service to ensure that the
`
`
`
`
`
`
`
`
`
`
`
`
`
`communication is properly effected. Examples of some
`
`
`
`
`
`
`
`
`services provided by the various layers are error detec-
`tion, error recovery and routing among many commu-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`nication paths. All the layers in conjunction present the
`overall communication solution. Experience has shown
`
`
`
`
`
`
`
`
`
`
`
`
`
`that modularizing in layers with well defined functional
`interfaces, divides and effectively reduces the complex-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ity of the connectivity problem and leads to a more
`flexible and extensible solution.
`
`
`
`
`A model for describing the layers in a network has
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`been posited by the International Standards Organiza-
`tion (ISO). The ISO open systems interconnection
`
`
`
`
`
`
`
`(OSD) modelis a seven-layer model, illustrated in FIG.
`
`
`
`
`
`
`1, which provides a standard for describing a network
`
`
`
`
`
`
`
`and facilitating computer communications. OSI and
`
`
`
`
`
`
`other layered computer network communications stan-
`
`
`
`
`
`
`dards are discussed in detail in Unix Network Program-
`
`
`
`
`
`
`
`
`
`
`
`
`
`ming by W. Richard Stevens, and Handbook of Comput-
`
`
`
`
`
`er-Communication Standards by William Stallings,
`
`
`
`
`
`
`
`which are incorporated herein by reference. The OSI
`model defines the layers and units of information that
`
`
`
`
`
`
`
`
`
`pass along a network.Asillustrated, data from an appli-
`
`
`
`
`
`
`
`cation or process running on a first host (HOST A)
`
`
`
`
`
`
`
`
`moves down the model network layers to a Physical
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`layer. The Physical layer defines the physical connec-
`tion which transmits raw bits across a communication
`
`
`
`
`
`
`
`channel to another host (HOST B) and up correspond-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ing layers to a process running thereon. OSI, while
`defining a model or framework in which standards and
`
`
`
`
`
`
`protocols can be developed at each layer, allows for a
`
`
`
`
`
`
`
`
`
`
`
`
`
`flexible approach for implementation of the model.
`
`
`
`
`
`
`Layered protocols and interfaces therebetween have
`been defined, which provide specifications for commu-
`
`
`
`
`
`
`
`nication between a process or program being executed
`
`
`
`
`
`
`on one computer’s operating system and another pro-
`
`
`
`
`
`
`
`
`cess running on another computer. Transmission Con-
`
`
`
`
`
`
`tro] Protocol/Internet Protocol (TCP/IP) are two pro-
`
`
`
`
`
`
`
`tocols that are part of a protocol suite or family of pro-
`
`
`
`
`
`
`
`
`tocols layered and designed to connect computer sys-
`
`
`
`
`
`
`
`tems that use different operating systems and network
`
`
`
`
`
`
`
`
`technologies. TCP/IP, which provides a commonset of
`
`
`
`
`
`
`
`
`2
`protocols for invocation on dissimilar interconnected
`
`
`
`
`
`
`systems,is illustrated and mapped in FIG. Ja to analo-
`
`
`
`
`
`
`
`
`
`
`
`gous layers of the OSI model.
`TCP/IP is a four layer protocol suite which facili-
`
`
`
`
`
`
`
`tates the interconnection of two or more computer
`
`
`
`
`
`
`
`systems on the sameordifferent networks and in certain
`
`
`
`
`
`
`
`networks, such as the Internet,
`is a requirement for
`
`
`
`
`
`
`
`
`
`
`
`
`
`interoperability. The four layers, comprise two inde-
`pendent protocols: TCP which can be used to access
`
`
`
`
`
`
`
`applications on other systems within a single network;
`
`
`
`
`
`
`and IP which permits identification of source and desti-
`
`
`
`
`
`
`
`nation addresses for communication between systems
`
`
`
`
`
`
`on different networks.
`
`
`
`Asillustrated in FIG. 2, application or process data
`
`
`
`
`
`
`communicated via TCP/IPis “packetized” as it passes
`
`
`
`
`
`
`
`
`
`
`
`
`
`down layers through the protocol suite. The original
`processdata first has an information block called a TCP
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Headerprefatorily appended thereto in a TCP layer, to
`form a TCP packet. The TCP Header contains informa-
`
`
`
`
`
`
`
`
`tion to assure that the data travels from point to point
`
`
`
`
`
`
`
`
`
`
`reliably without picking up errors or getting lost. An IP
`
`
`
`
`
`
`
`
`
`
`
`
`
`layer repacketizes the TCP packet into an IP packet, by
`adding an IP Header which contains information
`
`
`
`
`
`
`
`needed to get the packet to a destination node. The IP
`
`
`
`
`
`
`
`
`
`
`
`
`
`packet is further packetized, such as in ANSI/IEEE
`802 local area network protocol, with an additional
`
`
`
`
`
`
`
`
`Logical Link Control (LLC) address header and a con-
`
`
`
`
`
`
`
`
`trol header at an LLClayer, to form an LLC Protocol
`
`
`
`
`
`
`
`Data Unit (LLCPDU). The LLCPDUis “framed”for
`
`
`
`
`
`
`
`transmission by addition of a Media Access Control
`
`
`
`
`
`
`
`Header and Trailer, to form a MAC Frame for commn-
`
`
`
`
`
`
`
`nication between two TCP/IPfacilities.
`
`
`
`
`
`It is apparent that a considerable amount of “bag-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`gage”, in the form of headers andtrailer, is added to
`data which is transmitted between facilities using a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`layered protocol suite, such as TCP/IP and other OSI
`modelled families. Many additional bits are added at the
`
`
`
`
`
`
`
`
`various layers and must be processed for ultimate trans-
`
`
`
`
`
`
`
`
`mission across a communication channel at the physical
`
`
`
`
`
`
`layer. At its destination, the transmitted frame must be
`
`
`
`
`
`
`
`
`
`
`
`
`unpacketized according to embeddedinstructions and
`
`
`
`
`
`
`
`
`passed upward through the layered protocols to its
`receiving application or process.
`
`
`
`
`
`
`
`
`
`
`Aside from the significant processing overhead asso-
`
`
`
`
`
`
`
`
`ciated with packetizing data for network and internet-
`work transmission, data itself may be redundant, such
`
`
`
`
`
`
`
`that real costs are associated with putting data andall its
`
`
`
`
`
`
`
`
`
`
`protocol suite baggage across the communication chan-
`
`
`
`
`
`
`
`nel.
`
`Where the communication channel is integral to a
`
`
`
`
`
`
`wide area network (WAN) the impact of redundant
`
`
`
`
`
`
`
`data and protocol suite baggage on transmission costs
`
`
`
`
`
`
`
`can be measured in dollars. WANlinks, such as dial-up
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`phonelines, typically have relatively low, fixed upper
`limit data transmission rates and are billed based on
`
`
`
`
`
`
`
`
`
`connect time, packet count or bandwidth use. Thus, the
`
`
`
`
`
`
`
`
`extensive packetization and resultant bits that must be
`
`
`
`
`
`
`
`transmitted increase connecttime and dollar cost. Addi-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tionally, the numerous appended bits significantly in-
`crease the possibility of transmission errors onless reli-
`
`
`
`
`
`
`
`able lines. Where WANlinks, such as analog leased
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`lines, and Dataphone Digital Services (DDS)are used,
`monthly or annual subscription fees recur and to a great
`
`
`
`
`
`
`
`extent are consumedbytraffic comprising the transmis-
`
`
`
`
`
`
`
`sion of redundant bits and protocol attributable header
`
`
`
`
`
`
`
`and trailer information.
`
`
`
`
`
`
`
`
`
`
`40
`
`60
`
`
`
`
`
`Petitioner Valve - Ex. 1014, Page 11
`Petitioner Riot Games,Inc. - Ex. 1014, p. 11
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 11
`
`Petitioner Valve - Ex. 1014, Page 11
`
`

`

`5,307,413
`
`_ 0
`
`20
`
`
`
`
`
`3
`Compression schemes and apparatus are known
`
`
`
`
`
`
`which reduce the quantity of bits that must be transmit-
`
`
`
`
`
`
`
`
`ted across the communication channel. However, data
`
`
`
`
`
`
`
`compressing modems,such as disclosed in U.S. Pat. No.
`
`
`
`
`
`
`
`4,748,639, compress data streams after packetization for
`
`
`
`
`
`
`
`transmission over the communication channel. Signifi-
`
`
`
`
`
`
`cant additional hardware is required, in the form of a
`
`
`
`
`
`
`compression modem and a decompression modem. The
`
`
`
`
`
`additional hardware, whichtranslates into significantly
`
`
`
`
`
`
`
`
`
`
`
`
`
`increased system cost,
`requires frequency tables to
`recodify and decodify or decompress characters in a
`
`
`
`
`
`
`data stream in accordance with a compressed character
`
`
`
`
`
`
`code. Such a compression schemeis not host resident,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`does not take advantage of the modular/layered struc-
`ture of the network communication system and lacks
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`theflexibility to reduce the numberof packets and head-
`ers generated in the transmission of a particular data
`
`
`
`
`
`
`
`
`
`
`
`
`
`stream. Further, because compression modemsservice
`multiple connections and data that may come from one
`
`
`
`
`
`
`
`
`
`or more systems, redundancy of data tends to be ran-
`
`
`
`
`
`
`
`
`
`
`
`
`
`dom.It is appreciated that randomly redundant data is
`more difficult to compress.
`
`
`
`Network bridge productsare available that also have
`
`
`
`
`
`
`
`
`data compression facilities. However, much like com-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`pression modems, bridges do not provide host resident
`
`
`
`
`
`
`
`end-to-end compression facilities. Bridges also do not
`have the capability to reduce packet count. Like com-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`pression modems, bridge products are not connection
`specific and must process data from various connections
`
`
`
`
`
`
`
`
`which tend to provide data that is randomly redundant.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Thus data compression with bridge products may not
`
`
`
`
`achieve optimal compressionratios.
`
`
`
`
`
`
`Host resident compression is available with applica-
`
`
`
`
`
`
`tion programsthat incorporate compression algorithms.
`However, such programstypically retrievea file from a
`
`
`
`
`
`
`
`massstorage device such as disk storage, processthefile
`
`
`
`
`
`
`
`
`
`and return it to the disk. The processedfile must then be
`
`
`
`
`
`
`
`
`
`
`retrieved from the disk to be shipped through the net-
`
`
`
`
`
`
`
`
`work layers for transmission. In addition to the signifi-
`
`
`
`
`
`
`
`
`cant additional overhead required for the disk storage
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and retrieval, such compression applications require
`that process data be effectively compiled as a com-
`
`
`
`
`
`
`
`pressed datafile and recompiled or decompressed at a
`
`
`
`
`
`
`
`
`
`
`
`
`destination facility. Such compression and decompres-
`
`
`
`
`
`
`
`
`sion significantly delays the availability of data sub-
`jected to this process of data transmission. Such decom-
`
`
`
`
`
`
`
`pression programs,although hostresident, are typically
`
`
`
`
`
`
`
`not integrated with particular applications and must be
`
`
`
`
`
`
`
`invoked so that they are not transparent to the user.
`
`
`
`
`
`
`
`
`SUMMARYOF THE INVENTION
`
`
`
`The present invention is a connection specific com--
`
`
`
`
`
`
`
`
`
`
`
`pression system which is selectively implemented in
`
`
`
`
`
`
`
`connections having the greatest data redundancy and
`
`
`
`
`
`
`takes advantage of modularity in implementing data
`compression in a layered network communication sys-
`
`
`
`
`
`tem. A data compression facility is interfaced in the
`
`
`
`
`
`
`
`
`layered system and intercepts data at a protocol layer
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`prior to the data being packetized for transmission.
`Therefore, fewer packets need to be created and fewer
`
`
`
`
`
`
`
`headersand trailers need to be generated to transmit the
`
`
`
`
`
`
`
`
`
`compressed data.
`According to the invention, a system acting as a com-
`
`
`
`
`
`
`
`
`
`
`
`
`
`pression host comprises a data packet switch driver
`
`
`
`
`
`
`which intercepts application data packets passing
`
`
`
`
`
`
`
`through layered network interfaces, prior to further
`packetization. When the system is acting as a compres-
`
`
`
`
`
`sion host and transmitting data to an application on a
`
`
`
`
`
`
`
`
`
`
`4
`
`
`
`
`
`
`
`the data packet switch
`second/decompression host,
`driver establishes a connection between a client applica-
`
`
`
`
`
`
`tion on the compression host and a system network
`
`
`
`
`
`
`
`
`protocol kernel interface (commonly called a socket)
`
`
`
`
`
`
`and routesselected client application data packets to an
`
`
`
`
`
`
`
`associated local compression process which has an inte-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`gral network protocol. The data packets selected for
`compression are delivered to the compression process
`
`
`
`
`
`
`which opens a second connection to the system net-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`work protocol interface and compresses the data stream
`
`
`
`
`
`
`in accordance with a selected compression algorithm.
`
`
`
`
`
`
`
`
`The compressed data passes through the system net-
`
`
`
`
`
`
`
`
`work protocol and the packet switch driver subse-
`quently sends the compressed data back into the com-
`
`
`
`
`
`
`
`
`
`munications stream through a network driver. The
`
`
`
`
`
`
`compressed data passes across the network communica-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion channel andis received by the decompression host
`
`
`
`
`having compression/decompression capabilities
`ac-
`
`
`
`cording to the invention.
`
`
`
`
`
`
`The decompression host receives the compressed
`data through its network interface and delivers it to a
`
`
`
`
`
`
`
`
`
`
`
`
`
`peer compression process having its own complimen-
`
`
`
`
`
`
`
`tary integral network protocol. The peer compression
`process decompresses the received data and sendsit, via
`
`
`
`
`
`
`
`
`a second/decompression host resident packet switch
`
`
`
`
`
`
`driver, as though received from the network, into the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`decompression host system network protocol for con-
`nection with an application running on the second host.
`
`
`
`
`
`
`
`In another embodiment, a host system having data
`
`
`
`
`
`
`
`compression according to the invention is used as a
`
`
`
`
`
`gateway to process transmissions of systems not having
`
`
`
`
`
`
`compression according to the invention, which are
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`destined for another host having compression accord-
`
`
`
`ing to the invention.
`Features of the invention include end-to-end en-
`
`
`
`
`
`
`
`hanced data transmission having data compression that
`
`
`
`
`
`
`
`is transparent to the user effected between atleast two
`
`
`
`
`
`
`
`
`hosts. Reduction in data and number of packets trans-
`
`
`
`
`
`
`
`mitted across the communication channel
`improves
`
`
`
`
`
`
`Wide Area Network performance and response time
`
`
`
`
`
`
`
`while traffic is reduced to effectively increase WAN
`
`
`
`
`
`
`bandwidth. Compression according to the invention
`
`
`
`
`
`
`can be used with various network interfaces supported
`
`
`
`
`
`
`
`by the host because it operates independently of the
`
`
`
`
`
`
`
`
`network physical
`layer. Bridges and routers on the
`
`
`
`
`
`
`
`
`network will not affect, or be affected by, transmission
`
`
`
`
`
`
`
`
`of data serviced according to the invention.
`
`
`
`
`
`
`
`
`
`
`
`
`A compression managementfacility permits system
`manager invocation and definition of a configuration
`
`
`
`
`
`
`file of paths or connectionsin the network, which are to
`
`
`
`
`
`
`be compressed. Parameters can be set and displayed
`
`
`
`
`
`
`
`
`relating to data to be selected for compression.Statistics
`
`
`
`
`
`
`can be compiled and logged, to track: number of pack-
`
`
`
`
`
`
`
`ets sent and received; number of connectionsserviced;
`
`
`
`
`
`
`
`number of connections open; compression ratio; and
`
`
`
`
`
`
`
`
`
`
`
`compression paths and interfaces in use.
`DESCRIPTION OF THE DRAWING
`
`
`
`The invention will be more fully understood from the
`
`
`
`
`
`
`
`
`
`
`
`
`following detailed description taken in conjunction
`
`
`
`
`
`with the accompanying drawing in which:
`
`
`
`
`
`FIG. 1 is a diagrammatic view of an Open Systems
`Interconnection (OSI) model accordingto thepriorart;
`
`
`
`
`
`
`
`FIG.12 is a diagrammatic view of the OSI model of
`
`
`
`
`
`
`FIG. 1 compared to a Transmission Control Protocol-
`
`
`
`
`
`/Internet Protocol (TCP/IP) model according to the
`
`
`
`
`
`
`
`
`prior art;
`
`
`
`
`40
`
`
`
`
`
`60
`
`
`
`
`
`Petitioner Valve - Ex. 1014, Page 12
`Petitioner Riot Games,Inc. - Ex. 1014, p. 12
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 12
`
`Petitioner Valve - Ex. 1014, Page 12
`
`

`

`5,307,413
`
`
`
`20
`
`
`
`
`
`
`
`
`5
`
`
`
`
`
`FIG. 2 is a diagrammatic view of data packetized in
`accordance with the TCP/IP model of FIG. 1a,
`
`
`
`
`
`
`
`FIG. 3 is a block diagram ofan illustrative TCP/IP
`
`
`
`
`
`connection from a first host to a second host across a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Wide Area Network, according to the prior art, with-
`
`
`
`out data compression;
`FIG. 4 is a block diagram of a two host end-to-end
`
`
`
`
`
`
`
`
`
`
`
`
`connection having compression according to the inven-
`
`
`
`tion in a TCP/IP implementation;
`FIG.4¢ is a block diagram of a host having compres-
`
`
`
`
`
`
`sion according to the invention in a TCP/IP implemen-
`
`
`
`
`
`
`tation;
`
`FIG.5 is a flow chart of functions of a packet switch
`
`
`
`
`
`
`driver of FIG. 4a;
`
`
`
`
`
`
`
`
`FIG.6 is a block diagram of a compression process of
`FIG. 4a; and
`
`
`
`FIG. 7 is a block diagram of a system having com-
`
`
`
`
`
`
`pression according to the invention implemented as a
`
`
`
`
`
`gateway.
`
`
`
`
`6
`paths, established via the management utility 26 and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`maintained by the compression process 24 discussed
`
`
`
`
`
`
`
`hereinafter. The packet switch driver 22 compares the
`
`
`
`
`
`
`
`
`data packet address appended in the TCP/IP layers and
`determines if the data packet should be routed for com-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`pression. If the packet switch driver 22 determines that
`
`
`
`
`
`
`
`
`
`the data packet should not be compressed, that data
`
`
`
`
`
`
`
`packet is passed through to the network driver 28 to
`continue untouched in the communication stream. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`selected data packets,
`in accordance with addresses
`listed in a configurationfile established via the manage-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ment utility 26, are switched to the local compression
`process 24.
`
`
`
`
`
`
`
`
`Packets intercepted by the packet switch driver 22
`
`
`
`
`
`
`for compression are passed through a compression
`
`
`
`
`
`
`process-packet switch driver interface 32 (FIG. 6) and
`received by internal TCP/IP layers 30 that are func-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tionally interrelated with the compression process 24,
`
`
`
`
`
`
`
`
`
`and not part of the host TCP/IP 12 running under the
`
`
`
`
`
`
`
`operating system. The compression process 24,illus-
`DETAILED DESCRIPTION
`
`
`trated in FIGS. 4a and 6, functioning with the internal
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`‘TCP/IPlayers 30, performs TCP/IP input processing
`
`
`
`
`
`
`interconnection of two computers
`A host-to-host
`which assures the reliability of the data stream in the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`having TCP/IP network capabilities for communicat-
`
`
`
`
`
`
`
`
`ing across a Wide Area Network,asillustrated in FIG.
`packets received from the packet switch driver 22.
`
`
`
`
`
`
`
`3, provides a suitable environment for discussion of the
`
`
`
`
`A compression/decompression module 34 represents
`
`
`
`
`
`
`
`a service module which is modularly integrated with
`present invention. Without compression, such an inter-
`
`
`
`
`
`
`
`
`
`
`
`
`
`the internal TCP/IP layers 30 and communicates with
`
`
`
`
`
`
`
`
`
`
`
`
`
`connection comprises an application 10 running under
`
`
`
`
`
`
`
`
`
`
`an operating system onafirst system, Host A, which the host TCP/IP 12 for transmitting data on the net-
`
`
`
`
`
`
`
`transfers data to a socket or interface of a TCP/IP
`
`
`
`
`work. The compression/decompression module/34
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`protocol stack 12 comprising two layers, TCP and IP,
`comprises a general purpose compression/decompres-
`
`
`
`
`
`
`of the four layers of a TCP/IP protocolsuite for packe-
`
`
`
`
`
`
`
`
`
`sion algorithm, which is interfaced to permit different
`
`
`
`
`
`compression methods to be easily integrated. A com-
`tizing the data for transmission, as discussed hereinbe-
`
`
`
`
`
`
`
`fore. Fully TCP/IP packetized “datagrams”are deliv-
`
`
`
`
`
`
`
`pression/decompression module 34, in one example,is
`
`
`
`
`
`ered to a network interface driver, which effects further
`an implementation of a Lempel-Ziv algorithm for se-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`packetization, framing and transmission of the data on
`
`
`
`
`
`
`
`quential data compression, which is deselectable or
`the WAN medium. A network interface driver at the
`
`
`
`
`
`modularly removable to permit selection of an alterna-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tive algorithm knownin the art, such as an LZW com-
`receiving host, Host B, strips and passes the datagrams,
`
`
`
`
`
`
`
`
`
`
`
`
`
`including the data, to a Host B TCP/IP kernel where
`pression implementation or Huffman encoding. Data
`
`
`
`
`
`
`
`
`the data is de-packetized and a connection is accepted
`received by the compression process from the packet
`
`
`
`
`
`
`
`
`
`
`
`
`
`and made to an application or process running thereon
`switch driver 22 is compressed for transmission by the
`
`
`
`
`
`
`
`
`
`
`
`
`which reads the data.
`compression/decompression module 34 in accordance
`
`
`
`
`
`
`
`
`
`
`
`Referring nowto FIG. 4, a system 20 having TCP/IP
`with the selected algorithm.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`A compression control module 36 in the compression
`capabilities and data compression according to the in-
`vention comprisesa first host, Host A, having a packet
`process 24, in conjunction with a management module
`
`
`
`
`
`
`
`
`
`
`
`
`
`45
`switch driver 22 installed between the host TCP/IP
`38 that is a compression process resident portion of the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`kernel 12 which receives data from the application or
`managementutility 26, effect two phases in communica-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`process 10, and a network interface driver 28 that ef-
`tion of compressed data from the compression process
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`24 to a remote compression process 40 (FIG.4), within
`
`
`
`
`
`
`
`fects a lower layer of packetization, framing and trans-
`
`
`
`
`
`
`remote Host B.
`mission of the data on the WAN. The packet switch
`
`
`
`
`
`
`
`
`
`
`
`
`driver 22 communicates with a local compression pro-
`
`
`
`
`
`A first phase in communication of compressed data
`
`
`
`
`
`
`cess 24, whichis itself in communication with the host
`between compression processes involves the negotia-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`TCP/IP kernel 12 and functions as described hereinaf-
`tion of connections.Ifit is determined by the switch 22
`
`
`
`
`
`
`
`
`
`
`
`
`ter. A management utility 26 oversees and facilitates
`that a request to connect to a remote application re-
`
`
`
`
`
`
`
`
`
`
`
`
`