`IlllllllllllllllllllllllllllllllIllllllllllllllIlllllllllllllll|l|Illllllll
`US005307413A
`
`
`
`
`
`
`[19]
`United States Patent
`
`
`
`5,307,413
`[11] Patent Number:
`
`
`
`
`Denzer Apr. 26, 1994
`
`
`
`
`[45] Date of Patent:
`
`[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.
`
`
`
`Inventor:
`[75]
`
`
`[73] Assignee:
`
`
`
`[56]
`
`
`[21] Appl. No.: 733,104
`
`
`
`
`[22] Filed:
`Jul. 19,1991
`
`
`
`
`[51]
`Int. Cl.5 .......................... H04B 1/66;H04L 9/00
`
`
`
`
`
`
`[52]
`11.5.01. .......................................... 380/49; 380/9;
`
`
`
`
`
`370/109; 375/122
`
`
`[58] Field of Search ..................... 380/4, 9, 25,49, 50,
`
`
`
`
`
`
`
`
`395/21, 24, 25; 364/2408, 24294—24296,
`
`
`
`
`
`274.9, 276.6, 94061—94062, 940.81, 972.4;
`
`
`
`
`
`375/122; 340/825.8, 825.5; 381/34, 35; 370/109
`
`
`
`
`
`
`References Cited
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`8/1985 McNamara et a1.
`......... 340/8255 X
`4,533,948
`
`
`
`
`
`
`9/1987 Bergins et a1.
`..... 370/94
`4,691,314
`
`
`
`
`
`
`5/1988 Friedman et al.
`375/8
`4,748,638
`
`
`
`
`
`
`
`5/1989 Larson et a].
`. 340/8258
`4,833,468
`
`
`
`
`
`
`
`4,972,473 11/1990 Ejiri et al. ........................... 380/9 X
`
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`“D-A—T—A Compression,” DEC
`Strass, Hermann,
`
`
`
`
`
`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, NJ. 08003, pp. 1—4,
`
`
`
`
`
`
`
`
`no date.
`
`
`“FCX-chCX—File Compression for VAX/VMX and
`
`
`
`
`MS—DOS Systems,” brochure of Innovative Computer
`
`
`
`
`
`
`
`
`
`
`Systems, Inc. (ICS, Inc.), 1930 E. Marlton Pike, Cherry
`
`
`
`
`
`
`
`
`Hill, NJ. 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, “Protocol”).
`
`
`
`
`
`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 has an 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 sends it, 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
`
`
`
`
`
`
`
`running on the second host.
`
`
`
`
`
`19 Claims, 9 Drawing Sheets
`
`
`
`
`
`
`
`
`mmmnwn
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 1
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 1
`
`

`

`
`
`
`
`
`
`3
`
`
`
`
`
`
`
`US. Patent
`
`
`
`
`Apr. 26, 1994
`
`
`
`
`
`Sheet 1 of 9
`
`
`
`5,307,413
`
`
`
`
`
`
`
`
`
`HOSTA
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`NETWORK
`
`
`
`
`
`‘
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`08! MODEL
`
`
`
`HOST B
`
`
`
`
`
`
`
`
`
`
`
`NETWORK
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`packets
`
`
`
`
`
`
`
`
`Fig. 1
`
`
`(PRIOR ART)
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 2
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 2
`
`

`

`
`
`US. Patent
`
`Apr. 26, 1994
`
`
`
`
`Sheet 2 of9
`
`
`5,307,413
`
`
`
`
`03'
`
`TCP/IP
`
`
`
`
`APPLICATION
`
`ERESENTAITON
`
`
`
`PHYSICAL
`
`
`SESSION
`
`TRANSPORT
`
`
`
`NBWOHK
`
`
`
`DATA UNK
`
`
`
`
`
`
`
`E
`
`
`
`PROCESS
`
`
`
`.
`
`
`
`HOST-TO
`
`HOST
`
`
`FOP}
`
`'
`
`
`INTERNET (1P)
`
`
`
`
`
`
`
`NE'IWOFI’K
`
`ACCESS
`
`
`Fig. 1a
`
`
`(PRIOR AHU
`
`
`
`Petitioner Riot Games, Inc. - EX. 1014, p. 3
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 3
`
`

`

`US. Patent
`
`
`
`
`Apr. 26, 1994
`
`
`
`
`
`Sheet 3 of 9
`
`
`5,307,413
`
`
`
`
`
`DATA
`
`
`
`TOP
`
`HEADER
`
`DATA
`
`
`
`
`TCP PACKET
`
`
`
`’P PACKET
`
`
`
`
`
`
`
`[F
`
`HEADER
`
`
`TOP
`
`HEADER
`
`
`
`[F
`ADDRESS/
`
`
`CONTROL
`
`
`HEADERS HEADER
`
`
`
`TOP
`
`
`
`HEADER
`
`
`
`‘
`
`
`LLC PROTOCOL DATA UNIT
`
`
`(LLCPDU)
`
`
`
`
`
`MEDIA
`
`
`
`ERREDL
`
`E
`
`(MAC FRAME
`
`
`
`
`
`
`
`
`
`
`w
`3mm“ ”WORD:
`
`
`
`
`
`CONTROL Hams HEADER
`
`HEADER
`
`
`
`
`HEADER
`
`
`
`
`
`
`TCP/IP PACKERZARDN
`
`
`
`
`Fzg. 2
`
`
`(PRIOR ARR
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 4
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 4
`
`

`

`
`
`US. Patent
`
`
`
`
`Apr. 26, 1994
`
`
`Sheet 4 of9
`
`5,307,413
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`WIDE AREA NEIWORK (WAN)
`
`
`
`
`Fig. 3
`
`
`(PRIOR ART)
`
`Petitioner Riot Games, Inc. - EX. 1014, p. 5
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 5
`
`

`

`US. Patent
`
`Apr. 26, 1994
`
`Sheet 5 of 9
`
`5,307,413
`
`zgébcmzoo
`
`5:
`
`ldzmmx 55‘:
`
`EmEmu fizz:
`
`IEEImzmmz
`
`mEE.
`
`$3x55525%was)
`
`20=<m2wmzou
`
`5m
`
`Petitioner Riot Games, Inc. - EX. 1014, p. 6
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 6
`
`
`
`
`
`

`

`
`
`US. Patent
`
`
`
`
`Apr. 26, 1994
`
`
`Sheet 6 of 9
`
`5,307,413
`
`
`
`24
`
`
`
`
`COMPRESSION PROCESS (SEWICE MODULE)
`
`
`
`PROCESS
`
`
`
`
`
`10
`
`
`
`
`
` ADPUCAHON
`
`
`
`
`
`
`
`
`
`
`NETWORK lM'E-TEACE
`
`
`DRIVER
`
`
`28
`
`
`
`
`
`
`
`
`WIDE AREA NEIWOHK (MN)
`
`
`
`
`Fig. 4a
`
`Petitioner Riot Games, Inc. - EX. 1014, p. 7
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 7
`
`

`

`US. Patent
`
`
`*
`
`
`Apr. 26, 1994
`
`
`
`
`Sheet 7 of9
`
`
`
`
`5,307,413
`
`
`
`
`
`
`RECEIVE AND
`
`
`9(AMINE DATA
`
`
`
`PACKET
`
`
`
`
`
`
`SHOULD
`
`
`DATA PACKET
`
`YES
`‘
`
`
`
`BE DIVERTED
`
`
`
`FOR COMPRESSION?
`
`
`
`
`
`
`
`
`
`
`
`DIVERT DATA
`PASS DATA PACKET
`
`
`
`PACKE TO
`THROUGH TO NEIWORK
`
`
`
`
`
`
`COMPRESSION PROCESS
`FOR TRANSMISSION
`
`
`
`
`
`
`Fig. 5
`
`Petitioner Riot Games, Inc. - EX. 1014, p. 8
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 8
`
`

`

`US. Patent
`
`
`
`Apr. 26, 1994
`
`
`
`
`Sheet 8 of 9
`
`
`5,307,413
`
`
`
`24
`
`42 COMPRESSION
`
`
`
`
`
`
`
`
`
`
`
`
`
`CONTROL
`
`
`MODULE
`
`
` COMPRESSION/
`
`
`DECOMPRESSION
`
`
`
`MODULE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` PACKET SWITCH
`
`
`DRIVE? INTEHEQCE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fig. 6
`
`Petitioner Riot Games, Inc. - EX. 1014, p. 9
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 9
`
`

`

`US. Patent
`
`
`
`
`Apr. 26, 1994
`
`
`
`
`
`Sheet 9 of 9
`
`
`5,307,413
`
`
`
`DECOMPHESSION I
`
`
`54
`
`
`WHHCOMPRESSION
`
`
`
`E 3 E E
`
`
` 59
`
`
`- $3“
`
`I %
`
`§
`
`I‘
`
`a);
`
`'9
`
`8
`
`a
`g
`
`3-3
`
`I
`
`I
`
`I
`
`a
`a?
`
`ag
`
`t:
`
`5%
`
`94
`
`E
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 10
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 10
`
`

`

`1
`
`5,307,413
`
`
`METHOD AND APPARATUS FOR ADDING DATA
`
`
`
`
`
`
`COMPRESSION AND OTHER SERVICES IN A
`
`
`
`
`COMPUTER NETWORK
`
`
`FIELD OF THE INVENTION
`
`
`
`The present invention relates to data compression
`
`
`
`
`
`
`
`and in particular to data compression in the context of
`
`
`
`
`
`
`networked computers.
`
`
`BACKGROUND OF 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 no single
`
`
`
`
`
`
`“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 “intemetworked”,
`
`
`
`
`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
`
`
`
`
`
`
`and is interfaced to adjacent layers. Each of the layers is
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`(OSI) model is 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. As illustrated, 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-
`
`
`
`
`
`
`trol Protocol/Internet Protocol (TCP/1P) 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/1P, which provides a common set of
`
`
`
`
`
`
`
`2
`
`protocols for invocation on dissimilar interconnected
`
`
`
`
`
`
`systems, is illustrated and mapped in FIG. In to analo-
`
`
`
`
`
`
`gous layers of the 081 model.
`
`
`
`
`
`TCP/1P is a four layer protocol suite which facili-
`
`
`
`
`
`
`
`tates the interconnection of two or more computer
`
`
`
`
`
`
`
`systems on the same or different networks and in certain
`
`
`
`
`
`
`
`networks, such as the Internet,
`is a requirement for
`
`
`
`
`
`
`
`
`
`
`
`
`
`interoperability. The four layers, comprise two inde-
`pendent protocols: TCI’ 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.
`
`
`
`As illustrated in FIG. 2, application or process data
`
`
`
`
`
`
`communicated via TCP/1P is “packetized” as it passes
`
`
`
`
`
`down layers through the protocol suite. The original
`
`
`
`
`
`
`
`
`process data first has an information block called a TCP
`
`
`
`
`
`
`
`
`Header prefatorily 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 LLC layer, to form an LLC Protocol
`
`
`
`
`
`
`
`Data Unit (LLCPDU). The LLCPDU is “framed” for
`
`
`
`
`
`
`
`transmission by addition of a Media Access Control
`
`
`
`
`
`
`
`Header and Trailer, to form a MAC Frame for commu-
`
`
`
`
`
`
`
`nication between two TCP/1P facilities.
`
`
`
`
`
`It is apparent that a considerable amount of “bag-
`
`
`
`
`
`
`
`gage”, in the form of headers and trailer,
`is added to
`
`
`
`
`
`
`
`
`data which is transmitted between facilities using a
`
`
`
`
`
`
`layered protocol suite, such as TCP/1P 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 embedded instructions 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 and all 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. WAN links, such as dial-up
`
`
`
`
`
`
`phone lines, 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 connect time and dollar cost. Addi-
`
`
`
`
`
`
`
`
`tionally, the numerous appended bits significantly in-
`
`
`
`
`
`
`crease the possibility of transmission errors on less reli-
`
`
`
`
`
`
`
`able lines. Where WAN links, such as analog leased
`
`
`
`
`
`
`
`
`lines, and Dataphone Digital Services (DDS) are used,
`
`
`
`
`
`
`
`monthly or annual subscription fees recur and to a great
`
`
`
`
`
`
`
`extent are consumed by traffic comprising the transmis-
`
`
`
`
`
`
`
`sion of redundant bits and protocol attributable header
`
`
`
`
`
`
`
`and trailer information.
`
`
`
`
`10
`
`
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`
`
`
`
`
`
`45
`
`50
`
`55
`
`65
`
`
`
`
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 11
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 11
`
`

`

`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 US. 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 modern. The
`
`
`
`
`
`additional hardware, which translates 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 scheme is not host resident,
`
`
`
`
`
`
`
`does not take advantage of the modular/layered struc-
`
`
`
`
`
`
`
`ture of the network communication system and lacks
`
`
`
`
`
`
`
`
`the flexibility to reduce the number of packets and head-
`
`
`
`
`
`
`
`
`ers generated in the transmission of a particular data
`
`
`
`
`
`
`
`stream. Further, because compression modems service
`
`
`
`
`
`
`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 products are 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
`
`
`
`
`
`
`
`
`‘30
`which tend to provide data that is randomly redundant.
`
`
`
`
`
`
`
`Thus data compression with bridge products may not
`
`
`
`
`
`
`
`
`achieve optimal compression ratios.
`
`
`
`
`Host resident compression is available with applica~
`
`
`
`
`
`
`
`
`
`
`
`
`tion programs that incorporate compression algorithms.
`However, such programs typically retrieve a file from a
`
`
`
`
`
`
`
`mass storage device such as disk storage, process the file
`
`
`
`
`
`
`
`
`
`and return it to the disk. The processed file 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 data file 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 host resident, are typically
`
`
`
`
`
`
`
`not integrated with particular applications and must be
`
`
`
`
`
`
`
`invoked so that they are not transparent to the user.
`
`
`
`
`
`
`
`
`SUMMARY OF 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
`
`
`
`
`
`
`
`headers and 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
`
`
`
`
`
`
`
`
`
`10
`
`15
`
`20
`
`
`25
`
`
`35
`
`45
`
`
`
`
`
`55
`
`65
`
`
`
`
`
`5,307,413
`
`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 routes selected 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 and is 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 sends it, 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 at least 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 management facility permits system
`manager invocation and definition of a configuration
`
`
`
`
`
`
`file of paths or connections in 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 connections serviced;
`
`
`
`
`
`
`
`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 (05]) model according to the prior art;
`
`
`
`
`
`
`
`FIG. 10 is a diagrammatic view of the 051 model of
`
`
`
`
`
`
`FIG. 1 compared to a Transmission Control Protocol-
`
`
`
`
`
`/Intemet Protocol (TCP/IP) model according to the
`
`
`
`
`
`
`prior art;
`
`
`
`
`
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 12
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 12
`
`

`

`5
`
`FIG. 2 is a diagrammatic view of data packetized in
`
`
`
`
`
`accordance with the TCP/IP model of FIG. la;
`
`
`
`
`
`
`
`FIG. 3 is a block diagram of an 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. 4a 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.
`
`
`5,307,413
`
`10
`
`15
`
`
`
`20
`
`
`
`
`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 configuration file 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-
`
`
`
`
`
`
`
`trated in FIGS. 40 and 6, functioning with the internal
`
`
`
`
`
`
`
`'TCP/IP layers 30, performs TCP/IP input processing
`
`
`
`
`
`
`
`which assures the reliability of the data stream in the
`
`
`
`
`
`
`
`
`
`packets received from the packet switch driver 22.
`
`
`
`
`
`
`
`
`A compression/decompression module 34 represents
`
`
`
`
`a service module which is modularly integrated with
`
`
`
`
`
`
`
`the internal TCP/IP layers 30 and communicates with
`
`
`
`
`
`
`
`the host TCP/IP 12 for transmitting data on the net-
`
`
`
`
`
`
`
`
`
`work. The compression/decompression module/34
`
`
`
`
`comprises a general purpose compression/decompres-
`
`
`
`
`sion algorithm, which is interfaced to permit different
`
`
`
`
`
`
`compression methods to be easily integrated. A com—
`
`
`
`
`
`pression/decompression module 34, in one example, is
`
`
`
`
`
`an implementation of a Lempel-Ziv algorithm for se-
`
`
`
`
`
`quential data compression, which is deselectable or
`
`
`
`
`
`
`modularly removable to permit selection of an alterna-
`
`
`
`
`
`tive algorithm known in the art, such as an LZW com-
`
`
`
`
`
`
`
`pression implementation or Huffman encoding. Data
`
`
`
`
`
`
`received by the compression process from the packet
`
`
`
`
`
`
`
`switch driver 22 is compressed for transmission by the
`
`
`
`
`
`
`compression/decompression module 34 in accordance
`
`
`
`with the selected algorithm.
`
`
`
`
`A compression control module 36 in the compression
`
`
`
`
`
`
`process 24, in conjunction with a management module
`
`
`
`
`
`
`38 that is a compression process resident portion of the
`
`
`
`
`
`
`
`management utility 26, effect two phases in communica-
`
`
`
`
`
`
`
`tion of compressed data from the compression process
`
`
`
`
`
`
`
`24 to a remote compression process 40 (FIG. 4), within
`
`
`
`
`
`
`remote Host B.
`
`
`A first phase in communication of compressed data
`
`
`
`
`
`between compression processes involves the negotia-
`
`
`
`
`
`
`tion of connections. If it is determined by the switch 22
`
`
`
`
`
`
`that a request to connect to a remote application re-
`
`
`
`
`
`
`
`quires invocation of data compression, the local com-
`
`
`
`
`
`
`
`pression process 24 that receives the diverted data de-
`
`
`
`
`
`
`
`termines if a connection needs to be made to the remote
`
`
`
`
`
`
`compression process 40 at the specified destination in-
`
`
`
`
`
`ternet address. A connection table (not shown) within
`
`
`
`
`
`
`
`the local compression process maintains the status of
`
`
`
`
`
`
`
`
`TCP/IP connections made or being attempted between
`
`
`
`
`
`
`local and remote internet address/port pairs. The local
`
`
`
`
`
`
`
`
`compression process 24 attempts to connect to the re-
`
`
`
`
`
`mote compression process 40 intemet address specified
`
`
`
`
`
`
`in the local application’s connection request. If the local
`
`
`
`
`
`
`
`
`compression process 24 does not have sufficient re-
`
`
`
`
`
`
`
`
`sources or resources available, such as free memory, an
`
`
`
`
`
`
`unused connection and/or does not support the selected
`
`
`
`
`
`
`
`
`algorithm, the attempt is aborted and the connection
`
`
`
`
`
`
`
`
`25
`
`
`
`35
`
`
`
`
`
`
`
`50
`
`
`
`55
`
`
`
`
`
`
`
`65
`
`Petitioner Riot Games, Inc. - Ex. 1014, p. 13
`
`DETAILED DESCRIPTION
`
`
`interconnection of two computers
`A host-to-host
`
`
`
`
`
`
`having TCP/IP network capabilities for communicat-
`
`
`
`
`
`
`ing across a Wide Area Network, as illustrated in FIG.
`
`
`
`
`
`
`
`3, provides a suitable environment for discussion of the
`
`
`
`
`
`
`
`present invention. Without compression, such an inter-
`
`
`
`
`
`
`connection comprises an application 10 running under
`
`
`
`
`
`
`an operating system on a first system, Host A, which
`
`
`
`
`
`
`
`transfers data to a socket or interface of a TCP/IP
`
`
`
`
`
`
`
`
`30
`protocol stack 12 comprising two layers, TCP and IP,
`
`
`
`
`
`
`
`
`of the four layers of a TCP/IP protocol suite for packe-
`
`
`
`
`
`
`
`
`
`tizing the data for transmission, as discussed hereinbe-
`
`
`
`
`
`
`
`fore. Fully TCP/IP packetized “datagrams” are deliv-
`
`
`
`
`
`
`
`ered to a network interface driver, which effects further
`
`
`
`
`
`
`
`packetization, framing and transmission of the data on
`
`
`
`
`
`
`
`the WAN medium. A network interface driver at the
`
`
`
`
`
`
`
`receiving host, Host B, strips and passes the datagrams,
`
`
`
`
`
`
`
`
`including the data, to a Host B TCP/IP kernel where
`
`
`
`
`
`
`
`
`the data is de-packetized and a connection is accepted
`
`
`
`
`
`
`and made to an application or process running thereon
`
`
`
`
`
`
`which reads the data.
`
`
`
`
`Referring now to FIG. 4, a system 20 having TCP/IP
`
`
`
`
`
`
`capabilities and data compression according to the in-
`
`
`
`
`
`