`
`CERTIFICATE OF SERVICE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The undersigned hereby certifies that a copy of this REQUEST FOR REEXAMINATION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`UNDER35 U.S.C. §§ 302-307 AND 37 C.F.R. § 1.510 FOR U.S. Patent 5,822,523 together
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`with all exhibits and attachments and supporting documentation on a CD, has been served via
`
`
`
`
`
`
`
`
`
`
`first class mail on June 11, 2010 upon the following:
`
`
`
`
`
`
`
`DANIEL DEVITO
`
`
`
`
`
`
`SKADDEN, ARPS, SLATE, MEAGHER & FLOM LLP
`
`
`
`FOUR TIMES SQUARE
`
`
`
`
`NEW YORKNY 10036
`
`
`
`JORDAN ALTMAN
`
`
`
`
`
`SHEARMAN & STERLING LLP
`
`
`IP DOCKETING
`
`
`
`599 LEXINGTON AVENUE
`
`
`
`
`NEW YORK, NY 10022
`
`
`
`
`
`
`
`
`
`RAJIV P. PATEL, ESQ.
`
`
`
`
`FENWICK & WEST LLP
`
`
`
`TWO PALO ALTO SQUARE
`
`
`
`
`PALO ALTO, CA 94306
`
`
`
`
`
`
`/SonalDash/
`
`
`Sonal Dash
`
`Petitioner Valve Ex. 1005, Page 1
`Petitioner Riot Games,Inc. - Ex. 1005, p. 1
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 1
`
`Petitioner Valve Ex. 1005, Page 1
`
`

`

`PTO/SB/08a (05-07)
`
`
`Approved for use through 09/30/2007. OMB 0651-0031
`
`
`
`
`
`
`
`U.S. Patent and Trademark Office; U.S. DEPARTMENT OF COMMERCE
`
`
`
`
`
`
`
`
`
`Underthe Paperwork Reduction Act of 1995, no persons are required to respondto a collection of information unless it contains a valid OMB control number.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`STATEMENT BY APPLICANT
`
`
`
`
`
`
`
`( Not for submission under 37 CFR 1.99}
`
`
`
`
`
`
`
`
`
`
`
` INFORMATION DISCLOSURE Attorney Docket Number
`
`
`
`
`Application Number
`
`
`Filing Date
`DANIEL J. SAMUEL
`First Named Inventor
`
`
`
`
`
`
`
`
`Art Unit
`
`
`
`Examiner Name
`
`
`
`
`
`
`
`
`
`
`
`8330.003
`
`
`
`
`U.S.PATENTS
`
`
`
`
`Examiner) Cite
`Kind
`Name of Patentee or Applicant Pages,Columns, Lines where
`
`
`
`
`
`
`
`
`
`
`ate
`Relevant Passagesor Relevant
`:
`Initial
`No
`Code"
`of cited Document
`:
`
`
`
`
`
`
`
`
`Figures Appear
`
`Suzuki et al.
`
`
`
`
`
`
`
`Patent Number
`
`
`
`
`Issue Date
`
`
`
`
`
`1
`
`
`
`5736982
`
`
`
`1998-04-07
`
`
`
`
`
`2
`
`
`
`
`
`3
`
`
`
`
`
`4
`
`
`
`
`
`5 I
`
`f you wish to add additional U.S. Patent citation information please click the Add button.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`U.S.P,ATENT APPLICATION PUBLICATIONS
`
`
`
`
`
`
`
`Examiner
`Initial*
`
`
`
`
`
`
`Cite
`No
`
`
`Publication Number
`
`
`
`
`Kind
`
`Code’
`
`
`Publication
`Date
`
`
`
`
`
`
`
`
`Name of Patentee or Applicant
`of cited Document
`
`
`
`
`
`
`
`
`Pages,Columns,Lines where
`
`
`
`Relevant Passages or Relevant
`
`
`Figures Appear
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`lf you wish to add additional U.S. Published Application citation information please click the Add button.
`FOREIGN PATENT DOCUMENTS
`
`
`
`
`
`
`
`EFS Web 2.0.1
`
`
`
`
`
`Petitioner Valve Ex. 1005, Page 2
`Petitioner Riot Games, Inc. - Ex. 1005, p. 2
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 2
`
`Petitioner Valve Ex. 1005, Page 2
`
`

`

`
`
`
`Application Number
`
`
`
`Filing Date
`
`
`INFORMATION DISCLOSURE
`First Named Inventor|DANIEL J. SAMUEL
`
`
`
`
`
`
`
`
`
`STATEMENT BY APPLICANT
`
`
`
`
`
`
`
`(Not for submission under 37 CFR 1.99}
`
`
`
`
`
`
`
`
`
`
`
`
`
`Attorney Docket Number 8330.003
`
`
`
`
`
`
`j
`Pages,Columns,Lines
`Nameof Patentee or
`
`
`
`
`
`
`
`
`
`Examiner] Cite|Foreign Document Kind|PublicationCountry |.) itof cited where Relevant 15
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`InitialX|No|Number Code2 j Code4| Date PP Passages or Relevant
`
`
`
`
`
`
`
`
`
`
`
`
`Document
`.
`
`
`
`Figures Appear
`
`
`Examiner Name
`Art Unit
`
`
`
`
`
`
`
`
`
`
`
`
`
`1
`
`
`
`
`
`
`
`
`
`If you wish to add additional Foreign Patent Documentcitation information please click the Add button
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`NON-PATENT LITERATURE DOCUMENTS
`
`
`
`
`Include nameof the author (in CAPITAL LETTERS),title of the article (when appropriate),title of the item
`Examiner| Cite
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Initials*|No (book, magazine,journal, serial, symposium, catalog, etc), date, pages(s)}, volume-issue number(s), TS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`publisher, city and/or country where published.
`
`
`
`
`
`
`
`
`
`
`
`
`
`{
`
`
`
`
`
`
`
`
`
`
`Server2.5pl4.tar.gz (“Server Code”) and BRMH-1.7.tar.gz (“Client Code”)
`
`
`
`
`
`
`
`
`
`(source code dated nolater than August 19941) (“Netrek”)
`
`
`
`
`
`
`
`
`
`
`2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`J, OIKARINEN ET AL. RFC 1459, "Internet Relay Chat Protocol", published May 1993 (“IRC RFC”).
`
`
`
`
`
`
`
`
`3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`R. FRIEDMAN ET AL. "Packing Messagesas a Tool for Boosting the Performance of Total Ordering Protocols", Dept.
`
`
`
`
`
`
`
`
`
`
`of Science of Cornell University, published July 7, 1995 (“Friedman”).
`
`
`
`
`
`
`
`
`4
`
`
`
`DANIEL J. VAN HOOK, JAMES O. CALVIN, MICHAEL K. NEWTON, and DAVID A. FUSCO, “An Approach to DIS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Scaleability,” 11th DIS Workshop, 26-30 Sept. 1994 (“Yan Hook”).
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IEEE 1278-1993 "IEEE Standard for Information Technology- Protocols for Distributed Interactive Simulation
`
`
`
`
`
`
`
`
`
`
`Applications", approved March 18, 1993, and published in 1993 (“DIS”)
`
`
`
`5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`T. A. FUNKHOUSER,“RING: A Client-Server System for Multi-User Virtual Environments,” Association of Computing
`
`
`
`
`
`
`
`
`
`
`
`
`
`Machinery, 1995 Symposium on Interactive 3D Graphics, Monterey CA, April 9-12, 19952 (“RING”).
`
`
`
`
`
`
`
`
`
`
`
`
`
`ANDY MCFADDEN, “The History of Netrek”, published January 1, 1994 (“McFadden”).
`
`
`
`
`
`
`
`
`6
`
`
`
`¢
`
`
`
`
`
`EFS Web2.0.1
`
`
`
`
`
`Petitioner Valve Ex. 1005, Page 3
`Petitioner Riot Games, Inc. - Ex. 1005, p. 3
`
`
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 3
`
`Petitioner Valve Ex. 1005, Page 3
`
`

`

`
`
`Application Number
`
`
`
`
`
`
`Filing Date
`
`
`
`INFORMATION DISCLOSURE First Named Inventor|DANIEL J. SAMUEL
`
`
`
`
`
`
`
`
`
`
`
`STATEMENT BY APPLICANT
`|...
`
`
`
`
`
`
`
`
`
`(Not for submission under 37 CFR 1.99}
`Examiner Name
`
`
`
`
`
`
`
`Attorney Docket Number
`
`
`
`
`
`
`
`
`
`Include copy of this form with next communication to applicant. 1 See Kind Codes of USPTO Patent Documents at www.USPTO.GOV or MPEP 901.04. ? Enteroffice that issued the document, by the two-letter code (WIPO
`
`
`
`8330.003
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`MICHAEL R. MACEDONIA,“Exploiting Reality with Multicast Groups”, published September 1995 (“Macedonia”)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`lf you wish to add additional non-patentliterature document citation information please click the Add button
`EXAMINER SIGNATURE
`
`
`
`
`
`
`
`Examiner Signature
`Date Considered
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`*EXAMINER: Initial if reference considered, whetheror notcitation is in conformance with MPEP 609. Draw line through a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`citation if not in conformance and net considered.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`3 For Japanese patent documents, the indication of the year of the reign of the Emperor must precede the serial numberof the patent document.
`Standard ST.3).
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`4 Kind of document by the appropriate symbols as indicated on the document under WIPO Standard ST.16 if possible. 5 Applicant is to place a check mark hereif
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`English languagetranslation is attached.
`
`
`
`
`
`
`EFS Web 2.0.1
`
`
`
`
`
`Petitioner Valve Ex. 1005, Page 4
`Petitioner Riot Games,Inc. - Ex. 1005, p. 4
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 4
`
`Petitioner Valve Ex. 1005, Page 4
`
`

`

`PAT-A
`
`
`
`Petitioner Valve Ex. 1005, Page 5
`Petitioner Riot Games, Inc. - Ex. 1005, p. 5
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 5
`
`Petitioner Valve Ex. 1005, Page 5
`
`

`

`
`
`United States Patent
`Rothschild et al.
`
`119
`
`[14]
`
`(45)
`
`Patent Number:
`
`Date of Patent:
`
`§,822,523
`Oct. 13, 1998
`
`US005822523A
`
`[54] SERVER-GROUP MESSAGING SYSTEM FOR
`INTERACTIVE APPLICATIONS
`
`[75]
`
`Inventors: Jeffrey J. Rothschild; Marc P.
`Kwiatkowski, both of Los Gatos;
`Danie] J. Samuel, Sunnyvale, al) of
`Calif.
`
`[73] Assignec: Mpath Interactive, Inc., Mountain
`View, Calif.
`
`{21] Appl. No.: $95,323
`[22]
`Filed:
`Feb, 1, 1996
`
`(51)
`Int. CLe
`
`[82] U.S, Cl.
`
`prcsecswsssteserneeee HOH 1/02
`«» 395/200.17; 395/200.1;
`395/200.09
`
`Fleld of Seared ..........:ssstemine 395/200.1, 200.01,
`
`395/200.09,
`200.17, 200.05, 793; 370/85.13,
`60
`
`[58]
`
`[56]
`
`References Cited
`U.S, PATENT DOCUMENTS
`9/1984 Colton et al.
`4,470,954
`
`1/1992 Perlman .
`5,079,767
`|
`9/1992 Sidhu etal
`5,150,464
`...
`5/1994 Cidon et al.
`$309,433
`.
`5/1994 Perlman etal.
`5,309,437
`39$/200.01
`7/1994 Pagé et al.
`......
`5,329,619
`wie 370/60
`11/1994 Doeringer et al.
`5,361,256
`i
`12/1995 Milleret al.
`5,475,819
`sessed
`5/1996 Green ...-..0+
`5,517,494
`FOREIGN PATENT DOCUMENTS
`0637142
`1/1995
`European Pal. Of: .
`WO 95/10808
`4/1995 WIPO
`WO 9S/10911
`4/1995. WIPO.
`
`-
`
`
`
`
`Primary Examiner—William M. ‘Treat
`Assistant Examiner—Zami Maung
`Attorney, Agent, or Firm—H. C. Chan; Wison Sonsini
`Goodrich & Rosati
`
`ABSTRACT
`[57]
`A method for deploying interactive applications over a
`network containing host computers and group messaging
`servers is disclosed. The method operates in 3 conventional
`unicast network architecture comprised of conventional net-
`work links and unicast gateways and routers. The hosts send
`messages containing destination group addresses by unicast
`to the group messaging servers. The group addresses select
`message groups maintained by the group messaging servers.
`For each message group, the group messaging servers also
`maintain a list of all of the hosts that are members of the
`particular group.
`In its most simple implementation, the
`method consists of the group server receiving a message
`from a host containing a destination group address. Using
`the group address, the group messaging server then selects
`a message group which lists all of the host members of the
`group which are the targets of messages to the group. The
`group messaging server then forwards the message to each
`of the target hosts. In an interactive application, many
`Messages will be arriving at the group server close lo one
`anotherin time. Rather than simply forward cach message to
`its targeted hosts, the group messaging server aggregates the
`contents of cach of messages received during a specified
`time period and then sends an aggregated message to the
`targeted hosts. The time period can be defined in a number
`of ways, This method reduces the message traffic between
`hosts in a networked interactive application and contributes
`1 reducing the Istency in the communications between the
`hosts.
`
`6 Claims, 11 Drawing Sheets
`
`Host A Senxts
`
`Host B Sends
`
`Heat C Sends
`etsTsTr}
`
`Cd
`
`c
`
`as
`
`100
`
`101
`
`102
`
`103
`
`Hos! A Recawes
`LSLATH[2[Po]Pa)
`
`Host 8 Recelvas
`
`HoatC Receives
`Cs[et[ei[re[Pa]
`
`Host D Sends
`
`Host D Recewes
`
`ed
`‘Group Server Sends
`Group Sever Receives
`Pa eae o CALSLST]
`retelepy
`is [cy.[eryez]ea)
`Leo[sjcir)
`*- PoTeTeTe]
`a
`
`2
`103
`
`Petitioner Valve Ex. 1005, Page 6
`Petitioner Riot Games,Inc. - Ex. 1005, p. 6
`
`Petitioner Valve Ex. 1005, Page 6
`
`

`

`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 1 of 11
`
`5,822,523
`
`
`
`Figure 1
`Prior Art
`
`Petitioner Valve Ex. 1005, Page 7
`Petitioner Riot Games,Inc. - Ex. 1005, p. 7
`
`Petitioner Valve Ex. 1005, Page 7
`
`

`

`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 2 of 11
`
`5,822,523
`
`20
`
`88
`No |Jol>|>|
`s PA|CY]PA
`
`pA|OYPt|
`
`Host A Sends
`
`Host A Receives
`
`Host B Sends
`23
`Host B Receives
`20
`4
`~LeLAL)
`7~~LALS1]
`wo Loe13
`55.
`SLCPe
`pb|B|PS|
`|B|D|P2|
`
`24
`Host C Receives
`Host C Sends
`26
`5aRPS
`24
`oe
`LoLe1s]
`31
`pc|Db|Po|
`
`nNRNanN
`@®QWNoOoo
`Ebh
`ScDealPa
`crgge
`AOAERAS)
`ja
`Bes)Se[0P|[|¢|D|PS|
`
`Host D Sends
`
`Host D Receives
`
`Figure 2
`Prior Art
`
`Petitioner Valve Ex. 1005, Page 8
`Petitioner Riot Games,Inc. - Ex. 1005, p. 8
`
`Petitioner Valve Ex. 1005, Page 8
`
`

`

`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 3 of 11
`
`5,822,523
`
`
`
`Figure 3
`Prior Art
`
`Petitioner Valve Ex. 1005, Page 9
`Petitioner Riot Games,Inc. - Ex. 1005, p. 9
`
`Petitioner Valve Ex. 1005, Page 9
`
`

`

`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 4 of 11
`
`5,822,523
`
`55a
`
`s a
`
`Host A Sends
`Papers.
`te S|E|P38]
`pO]Ee|Pa|
`
`54
`
`Host A Receives
`
`Host B Receives
`54b
`SMeLet]
`~~.
`676 aec
`PD]E|Pa|
`
`Host B Sends
`PEPeT,
`
`55
`
`54c
`Host C Sends
`ae
`TELETE]
`
`we PB|E|2|
`POPE|Ps|
`
`Host C Receives
`
`56
`
`57
`
`Host D Sends
`foTete]
`
`64d
`..,
`sa
`
`Host D Receives
`“LATETP]
`«LSE12]
`PGEPRe
`
`Figure 4
`Prior Art
`
`Petitioner Valve Ex. 1005, Page 10
`Petitioner Riot Games,Inc. - Ex. 1005, p. 10
`
`Petitioner Valve Ex. 1005, Page 10
`
`

`

`
`
`U.S. Patent
`
`Oct, 13, 1998
`
`Sheet 5 of 11
`
`§,822,523
`
`
`
`Figure 5
`
`Petitioner Valve Ex. 1005, Page 11
`Petitioner Riot Games,Inc. - Ex. 1005, p. 11
`
`Petitioner Valve Ex. 1005, Page 11
`
`

`

`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 6 of 11
`
`5,822,523
`
`Host A Receives
`84
`Host A Sends
`80
`
`= {STATATPS
`
`86 LS|A|H|P3|
`PS|ALWPA
`81
`Host B Sends
`87
`
`Host B Receivesi|Bj}s|G[pe|
`
`89}8|!|Ps|
`3.)8|bee)
`82
`Host C Sends
`Host C Receives
`
`
`fets{[elrs} LS|cj]s[Pi]gg
`92|¢|s|Pe|
`ps|cj|pa|
`
`Ivn
`
`83
`Host D Sends
`Host D Receives
`
`POTS{GiPs} a4[|Do|K|Pi|
`95|Oo|K|Pe|
`|S|0|Kk[PS|
`
`B4
`
`Group Server Sends
`
`“CSTRTRTET
`
`80
`
`‘s
`
`Group Server Receives
`
`SfCopaPrt]
`
`is
`
`- 5 9
`
`4
`
`‘ 9
`
`3 Ps|c]u|P4|
`
`
`94 PRSfDy)oRPA|
`
`95 po|Kk|Pe|
`
`|S|Db]Kk[PS|i
`
`Figure 6
`
`Petitioner Valve Ex. 1005, Page 12
`Petitioner Riot Games,Inc. - Ex. 1005, p. 12
`
`Petitioner Valve Ex. 1005, Page 12
`
`

`

`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 7 of 11
`
`5,822,523
`
`
`Host A Sends
`
`
`
`Host A Receives
`
`
`97
`
`
`
`Host B Sends
`
`
`101
`
`Host B Receives
`
`Host D Receives
`
`Host C Receives
`
`400
`
`Group Server Sends
`
`i SEs 7
`
`96
`
`Group Server Receives
`
`~LALSLS1]
`
`pS}Bi!|Pty]Ps|Pe|=|Pe|
`PsfeTy[pi{pe|pa|pc]s|6[Ps|
`102
`98
`=
`Pa
`|§To|k [PsP2|Ps|
`
`103
`
`99
`
`Petitioner Valve Ex. 1005, Page 13
`Petitioner Riot Games,Inc. - Ex. 1005, p. 13
`
`Petitioner Valve Ex. 1005, Page 13
`
`

`

`
`
`U.S. Patent
`
`Oct, 13, 1998
`
`Sheet 8 of 11
`
`5,822,523
`
`
`
`Figure 8
`Prior Art
`
`Petitioner Valve Ex. 1005, Page 14
`Petitioner Riot Games,Inc. - Ex. 1005, p. 14
`
`Petitioner Valve Ex. 1005, Page 14
`
`

`

`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 9 of 11
`
`5,822,523
`
`Transport|ULP Msg.|Dest. ULP|Address|Destination Destination Bavioad
`
`
`
`
`Header Address|Count|Address 1Type Address N Y
`
`
`123
`
`124
`
`125
`
`126
`
`127
`
`128
`
`129
`
`
`
`
`
`
`
`Message|Source ULP} Data Source ULP} Data
`
`116
`
`117
`
`118
`
`119
`
`120
`
`121
`
`122
`
`
`
`
`
`
`
`
`
`
`130
`
`131
`
`132
`
`
`
`
`
`Figure 9
`
`Petitioner Valve Ex. 1005, Page 15
`Petitioner Riot Games,Inc. - Ex. 1005, p. 15
`
`Petitioner Valve Ex. 1005, Page 15
`
`

`

`
`
`U.S. Patent
`
`Oct, 13, 1998
`
`Sheet 10 of 11
`
`5,822,523
`
`Implicit ULP Group Address m
`
`ULP ServerProcess 0
`
`Host ULP Address a
`
`Host ULP Address a
`
`135
`
`
`Group Server Control
`
`
`
`
`
`
`Host ULP Address 0|Host TLP Address 0
`
`Implicit ULP Group Address 0
`
` Host ULP Address n|Host TLP Address n
`
`
`
`ULP Server Process m
`
`
`
`
`
`
`
`
`Host ULP Address n
`
`Host ULP Address n
`
`Host ULP Address a
`
`Logical ULP Address m
`Host ULP Address a
`
`
` Host ULP Address n
`
`Host ULP Address n
`
` Logical ULP Address 0
`
`
`
`
`Figure 10
`
`Petitioner Valve Ex. 1005, Page 16
`Petitioner Riot Games, Inc. - Ex. 1005, p. 16
`
`Petitioner Valve Ex. 1005, Page 16
`
`

`

`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 11 of 11
`
`5,822,523
`
`150
`
`
`
`Interactive Application
`
`Host Interface for Upper Level Protocol
`
`
`
`
`
`
`
`
`
`
`
`
`ULP Address 0|TLP Address 0
`
`ULP Address n|TLP Address n
`
`
`
`
`
`HostInterface for Transport Leve! Protocol
`
`Network Communications Stack
`
`Network Interface
`
`Figure 11
`
`Petitioner Valve Ex. 1005, Page 17
`Petitioner Riot Games,Inc. - Ex. 1005, p. 17
`
`Petitioner Valve Ex. 1005, Page 17
`
`

`

`
`
`5,822,523
`
`paya
`
`25
`
`3»
`
`wehe
`
`40
`
`1
`SERYER-GROUP MESSAGING SYSTEM FOR
`INTERACTIVE APPLICATIONS
`
`2
`consistent between all of ibe PCs, In a game that created the
`illusion of a spatial environment where each player could
`move, the packets could contain information about the new
`positionsof the players as they moved. Todaythere are many
`commercial example of PC games that can be played
`between multiple players on Loca] Area Networks (LANs)
`invention relates to computer network
`The present
`or by two players over dial-up phone lines using modoms.
`systems, and particularly to server group messaging systems
`The network messages sent by such games contaia a wide
`and methods for reducing message rate and latency.
`varity of information specific to the game. This can include
`position and velocity information of the objects in the game
`BACKGROUNDOF THE INVENTION
`along with special actions taken by a player that effect the
`other players in the game.
`‘There are a wide rangeofinteractive applications imple-
`mented on computer sysiems today. All arc characterized by
`The casc of a two player game played over a modem is
`dynamic response te the user. The user provides input to the
`particularly simplc. If the message rate is 10 messages per
`second, cach PC sends 10 messages per second to the other
`computer and the application responds quickly. One popular
`example of interactive applications on personal computers
`PC and receives 10 messages per second, The delay intro-
`(PCs) arc games.In this case, rapid response to the user may
`duced by the modems and phoneline is small and will not
`mean redrawing the screen with a new picture in between 30
`be noticed in most games. Unfortunately, the case of two
`ms and 100 ms. Interactive applications such as games
`playcrs is uninteresting for nctworked interactive applica-
`control the speed of their interaction with the user through
`tions, With the same game played with 8 players on a LAN,
`an internal time base. The application uses this time base to
`the message rate increases, Each PC must send 7 messages,
`derive rates at which the user inputis sampled,the screen is
`one to each of the other 7 players every time period and will
`redrawn and sound is played.
`receive 7 messages from the other players in the same time
`period. If the messaging time period is 100 ms, the total
`As computers have become more powerful and common,
`it has become important to connect them together in net-
`message rate will be 70 messages sent per second and 70
`messages received per second. As can be seen the message
`works. A network is comprised of nodes and links. The
`Tate increases linearly with the oumber of players in the
`nodes are connected in such a way that there exists a path
`from cach node over the links and through the other nodes
`game. The message rates and data rates supparted by popu-
`to each of the other nodes in the network, Each node may be
`lar LANs are high enough to support a large number of
`connected to the network with one or more links. Nodes are
`players at reasonable message sizes. Unfortunately, LANs
`further categorized into hosts, gateways and routers. Hosts
`are only deployed in commercial applications and cannot be
`considered for deploying a networked interactive applica-
`are computer systems that are connected to the network by
`tion lo consumer users.
`one link. They communicate with the other nodes on the
`The wide area networks available today (o consumerusers
`network by sending messages and receiving messages. Gate-
`ways are computer systems connected to the network by
`all musi be accessed through dial-up phone lincs using
`more than one link. They not only communicate with the
`modems, While modem specds have increased rapidly, they
`have now reachedabit rate of 28.8 Kbits/sec which is close
`other nodes as do hosts, but they also forward messages on
`one of their network links to other nodes on their other
`to the limit set by the signal-to-noise ratio of conventional
`network links. This processing of forwarding messages is
`phone lines, Further speed increases are possible with ISDN,
`called routing. In addition to sending and receiving mes-
`but this technology is not ready for mass market usc. Other
`sages and thcir routing functions, gateways may perform
`new wide area networking technologiesare being discussed
`other functions in a network. Routers arc nodes that are
`that would provide much higher bandwidth, but none are
`connected to the network by more than one link and whose
`close to commercial operation. Therefore, in deploying a
`sole function is the forwarding of messages on one network
`networked, interactive application to consumers, il is nec-
`link to the other network links to which it is connected. A
`s essary to do so in a way that operates with existing net-
`network consisting of many network links can be thought of
`working and communications infrastructures.
`as a network of sub-networks with galeways and/or routers
`In the example of the 8 player networked game, consider
`connecting the sub-networks together into whatis called an
`a wide area network implementation where the PCs of cach
`internet. Today the widely known example of a werld wide
`of the players is connected to the network with a 28.8
`internetis the so called “Imernet” which in 1995 has over 10
`Kbit/sec modem. Assume that
`the network used in this
`million computers connected full time world-wide.
`example is the Internet so that all of the network protocols
`With so many computers on a single world-wide network,
`and routing behavior is well defined and understood,If the
`is desirable to create interactive networked applications
`it
`game uses TCP/IP to send its messages between the PCs in
`that bring together many people in a shared, networked,
`the game, the PPP protocol overthe dial-up phone lincs can
`interactive application. Unfortunately, creating such shared
`be advantageously used to compress the TCP/IP beaders.
`networked, interactive applications runs into the limitations
`Even sa, a typical message will be approximately 25 bytes
`ofthe existing network technology.
`in size. Sent
`through the modem, this is 250 bits. The
`As an example, consider a game designed to be deployed
`messages are sent 10 times per second to cach of the other
`PCs in the game and received 10 times per second from the
`over a network whichis to be played by multiple players
`other PCs, This is 35.0 Kbits/sec which exceeds the capa-
`simultaneously. The game could be implemented in software
`bilities of the modem by 20%.Jf the messages are reduced
`ona PC connected to a network. A rate set by ils internal
`to 20 bytes, just 8 players can be supported, bul
`this
`lime base, it would sample the inputs of the local user,
`receive messages from the network from the PCs of the other
`approach clearly cannol support networked interactive
`applications with large numbers of participants. There are
`players and send messages out to the PCs of the other
`other problems beyond just the bandwidth of the network
`players. A typical rate will be ten time per second for a time
`connection. There is the loading on each PC caused by the
`period of 100 ms. The messages sent between the PCs would
`contain information that was needed to keep the game
`high packetrates and there is the lateacy introduced by the
`
`FIELD OF THE INVENTION
`
`50
`
`60
`
`65
`
`Petitioner Valve Ex. 1005, Page 18
`Petitioner Riot Games,Inc. - Ex. 1005, p. 18
`
`Petitioner Valve Ex. 1005, Page 18
`
`

`

`
`
`5,822,523
`
`rw a
`
`20
`
`a
`
`3s
`
`40
`
`4
`3
`3, packet 21 to host 2 and packet 22 to host 4. Host 1 wants
`time needed to send all of the outbound packets. Bach packet
`to send the same data Pl to cach of the other three hosts,
`seni or received by a PC will require some amount of
`therefore the payloadin all three packets is the same. Packet
`processing time. As the packet
`rate increases with the
`20 travels over network links 11, 12, 15 and 18 and through
`numberofplayers in the game,less and Icss of the processor
`routers 5, 6, and 8 to reach host3. In a similar fashion host
`will be available for
`running the game software itself
`3 sends packets 23 to host 1, packet 24 to host 2 and packet
`Latency is importantin an interactive application because it
`25 to host 4, Host 2 and host 4 send packets 26, 27, 28 and
`defines the responsiveness of the system, When a player
`29, 30, 31 respectively 10 the other three hosts. All of these
`provides a new input ontheir system,it is desirable for that
`packets are carried by the unicast network individually from
`input to immediately affect the game on all of the other
`the source host to the destination host. So in this example
`players systems. ‘This is particularly important in any game
`each host must send three packets and receive three packets
`where the game outcome depends on players shooting at
`in order for each host to send its payload to the other three
`targets that are moved by the actions of the other players.
`hosts.
`Latency in this case will be the time from whena player acts
`As can be seen, cach host must send a packel to every
`to move a target to the time thal the target has moved on the
`other host that it wishes to communicate with in an inter-
`screens of the otherplayers in the game. A major portion of
`active application. Further,it receives a packet from every
`this latency will come from the time needed to s¢nd the
`other bost that wishes to communicate with it. In an inter-
`messages to the other seven players in the game. In this
`active application, this will happenal a regular and high rate.
`example the time to send the messagesto the other 7 players
`All of the hosts that wish 1o communicate with one another
`will be approximately 50 ms. While the first player of the
`will need to send packets to cach other eight to ten times per
`seven will receive the message quickly, it will not be until
`second, With four hosts communicating with one another as
`50 ms have passed thal the last player of the seven will have
`received the message.
`in this example, each host will send three messages and
`receive three messages eightlo ten limes per second. As the
`Internet Protocol Multicasting
`As mentioned before,
`the Intcrnet is a widely known
`number of hosts in the application that need to communicate
`with one another grows, the message rate will reach a rate
`example of a wide arca nttwork. The Internct is based on a
`that cannot be supported by conventional dial-up lines, This
`protocol appropriately called the Internet Protocol (IP). In
`makcs unicast transport protocols unsuitable for delivering
`the OSI reference mode! for layers of network protocols, IP
`interactive applications for multiple participants since their
`corresponds to a layer 3 or Network layer protocol. It
`provides services for transmission and routing of packets
`use will result in the problem ofhigh packet rates that grow
`between two nodes in an internct. The addressing model
`with the number of participants.
`Work has been done to aticmpt to extend the IP protocol
`provides a 32 bit address for all nodes in the network and all
`to support multicasting, See RFC-1112 “Host Extensionsfor
`packets carry source and destination addresses.
`IP also
`IP Multicasting”. This document describes a set of exten-
`defines the routing of packets between network links in an
`sions to the IP protoco! that enable IP multicasting. IP
`inter-network. Gateways and routers maintain tables that are
`multicasting supports the transmission ofa IP datagram to a
`used 10 lookup routing information based on the destination
`addresses of the packcts they receive, The routing informa-
`host group by addressing the datagram to a single destina-
`tion address, Multicast addresses arc a subset of the IP
`tion tells the galeway/router whether the destination of the
`address space and identified by class DIP addresses—ithese
`packet is directly reachable on a local network link con-
`are IP addresses with “1110” in the high order 4 bits, The
`nected to the gateway/routerorif not, the address of another
`gateway/router on one of the local network links to which
`host group contains zero or more IP hosts and the IP
`the packet should be forwarded. On topofIP are the layer
`multicasting protocol transmits a multicast dalagrem to all
`members of the group to whichit is addressed, Hosts may
`4 transport protocols TCP and UDP, UDPprovides datagram
`delivery services to applications that does not guarantee
`join and leave groups dynamically and the routing of mul-
`licast datagrams is supported by multicast routers and gatc-
`reliable or in-order delivery of the datagrams. TCP is a
`ways. It
`is proper to describe this general approach to
`connection oriented service to applications thal does provide
`multicast messaging as “distributed multicast messaging”, It
`reliable delivery of a data stream. It handles division of the
`is a distributed technique because the job of message deliv-
`stream into packets and ensuresreliable, in-order delivery.
`Sec the Internet Society RFCs: RFC-791 “Internet
`ery and duplication is distributed throughout the network to
`all of the multicast routers, For distributed multicast mes-
`Protoco]", RFC-793 “Transmission Control Proteco!” and
`REC-1180 “A TCP/P Tutorial".
`IP, TCP and UDP arc
`saging to work in a wide area network, all of the routers
`handling datagrams for multicast hosts must support the
`unicast protocols: packets, streams or dalagrams are trans-
`miued from a source to a single destination.
`routing of multicast datagrams. Such multicast routers must
`As en example, consider FIGS, 1 and 2. FIG. 1 shows a
`be aware of the multicast group membership of all of the
`conveational unicast network with hosts 1, 2,3 and 4 and
`hosts locally connected to the router in order to deliver
`network links 11, 12, 13, 14, 15,16,17, 18 and 19 and routers
`multicast datagrams to local hosts. Multicast routers must
`also be able to forward multicast packets to routers on their
`5,6, 7, 8, 9 and 10. In this example, each host waals to send
`local network links. Multicast routers must also decide to
`a data payload to cach of the other hosts. Host 1 has network
`address A, host 2 has network address C, host 3 has network
`which if any local routers they must forward multicast
`datagrams, When a multicast datagram is received, by a
`address B and host 4 has network address D. Existing
`wo
`network protocols are typically based on packet formats that
`raulticast router, its group address is compared toalist for
`each local multicast router of group addresses, When there
`contain a source address, destination address and a payload.
`This is representative of commonly used wide area network
`is a match, the datagram is then forwarded to that local
`multicast
`router. Therefore,
`the multicast routers in the
`protocols such as IP. There are other componentsin an actual
`IP packet, but for sake of this example,only these items will
`network must maintain an accurate and up to dale list of
`group addresses for which they are to forward datagramsto.
`be considered. FIG. 2 shows the example packets that are
`These lists are updated when hosts join or leave multicast
`sent by the hosts to one another using a conventional unicast
`groups. Hosts do this by sending messages using Internet
`network protocol such as IP. Host 1 send packcts 20, to host
`
`3
`
`aa
`
`Petitioner Valve Ex. 1005, Page 19
`Petitioner Riot Games,Inc. - Ex. 1005, p. 19
`
`Petitioner Valve Ex. 1005, Page 19
`
`

`

`
`
`5,822,523
`
`§
`Group Management Protocol (IGMP) to their immcdiately-
`neighboring oulticast routers. A further attribute of distrib-
`uted multicast messaging is that the roulers mus! propagate
`the group membership information for a particular group
`throughout the networkto all of the other routers that will be
`forwarding traffic for that group. RFC-1112 does not
`describe how this is to be done. Manydifferent approaches
`have been defined for solving this problem that will be
`mentioned later in descriptions of related prior art. Despite
`their differences, all of these approaches are methods for
`propagation of multicast routing information between the
`multicast routers and techniques for routing the multicast
`datagrams in an inter-network supporting distributed multi-
`cast messaging.
`‘The distributed multicast messaging approach has a num-
`ber ofundesirable side effects. The process of propagation of
`group membership information to all of the relevant routers
`is not instantaneous. In a large complex network it can even
`take quite a period of time depending on the number of
`routers that must receive that updated group membership
`information and how many routers the information for the
`group membership update must past through. This process
`can casily take many seconds and cven minutcs depending
`on the specifics of the algorithm that
`is used. RFC-1112
`mentions this problem and someofthe side effects thal must
`be handled by an implementation of a practical routing
`algorithm for multicast messaging. One problem results
`when groups are dynamically created and destroyed. Since
`there is no central authority in the network for assigning
`group addresses, it is easily possible in a distributed nctwork
`for there to be duplication ofgroup address assignment, This
`will result in incorrect datagr