`
`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 Riot Games,Inc. - Ex. 1005, p. 1
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 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 Riot Games, Inc. - Ex. 1005, p. 2
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 2
`
`

`

`
`
`
`Application Number
`
`
`Filing Date
`
`
`INFORMATION DISCLOSURE
`First Named Inventor|DANIEL J. SAMUEL
`
`
`
`
`
`
`
`
`
`STATEMENT BY APPLICANT
`Art Unit
`
`
`
`
`
`
`
`
`
`(Not for submission under 37 CFR 1.99}
`Examiner Name
`
`
`
`
`
`
`
`
`Attorney Docket Number
`
`
`
`8330.003
`
`
`
`
`
`Pages,Columns,Lines
`Nameof Patentee or
`Foreign Document
`
`
`
`
`
`
`
`
`
`Examiner) Cite Numbers Kind|PublicationCountry Applicantofcited where Relevant Ts
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Initial*=|No|“Umber Code2 j Code4| Date PP Passages or Relevant
`
`
`
`
`
`
`
`
`
`
`
`
`Document
`.
`
`
`
`Figures Appear
`
`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”)
`
`
`
`
`{
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`J, OIKARINEN ET AL. RFC 1459, "Internet Relay Chat Protocol", published May 1993 (“IRC RFC”).
`
`
`
`
`
`2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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”).
`
`
`
`
`3
`
`
`
`
`
`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”).
`
`
`
`
`4
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IEEE 1278-1993 "IEEE Standard for Information Technology- Protocols for Distributed Interactive Simulation
`
`
`
`
`
`
`
`
`
`
`
`Applications", approved March 18, 1993, and published in 1993 (“DIS”)
`
`
`
`
`5
`
`
`
`
`
`
`
`
`
`
`
`
`6
`
`
`
`¢
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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”).
`
`
`
`
`
`
`
`
`
`
`EFS Web2.0.1
`
`
`
`
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 3
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 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 Riot Games,Inc. - Ex. 1005, p. 4
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 4
`
`

`

`PAT-A
`
`
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 5
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 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;
`Daniel J. Samuel, Sunnyvale, ali of
`Calif.
`
`[73] Assignee: Mpath Interactive, Inc., Mountain
`View, Calif.
`
`{21] Appl. No.: $95,323
`[22]
`Filed:
`Feb, 1, 1996
`[51]
`Uinte CLS a
`esnennnnmncnnevencnnenee HOH 1/02
`[52] US. Ch. caccssssssecssssssscnnmeens 395/200,17; 395/200, 1;
`395/200.09
`Fleld of Seared ..........ussts+ 395/200,1, 200.01,
`395/200.09, 200.17, 200.05, 793; 370/85.13,
`6
`
`[58]
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`370/60
`9/1984 Cottonet al.
`.
`4,470,954
`woes 370/943
`1/1992 Perlman...
`5,079,767
`
`..
`395/200.01
`9/1992 Sidhu etal,
`5,150,464
` $/1994 Ciden et al.
`~~ 370/60
`§,309,433
`
`5/1994 Perlman etal.
`=» 370/85.13
`5,309,437
`....
`39$/200.01
`7/1994 Pagé et al.
`5,329,619
`11/1994 Doeringer et al.
`eevee STOO
`5,361,256
`12/1995
`Mi
`.
`5,475,819
`5/1996 G
`5,517,494
`FOREIGN PATENT DOCUMENTS
`0637142
`1/1995
`European Pal. Of: .
`WO 95/10808
`4/1995 WIPO
`WO 95/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 operatesin a 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 each 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
`1o reducing the Istency in the communications between the
`hosts.
`
`6 Claims, 11 Drawing Sheets
`
`Hoat A Sends
`Host A Recmvwes
`LATSTGTP]
`LSLATH[p2|Po]Pa)
`hd
`101
`
`6
`
`100
`
`Host 8 Receives
`Host B Sends
`
`LaTsToTre] Lsis Ti[Ps|3 TPs|
`8
`102
`
`Heat C Sends
`YeTsTsTr
`
`HoatC Receives
`Csfet)[ei[re[ra]
`
`@
`
`403
`
`Host D Recewes
`Host D Sends
`
`LOTSTG{Pal LS[oTKk [ri [reps|
`
`‘90
`Group Server Sends
`*
`Group Sewer Receives:
`or Le o CALSLeT]
`Petelepy
`is [coyyTPTp27]a) Le[siclr]
`
`%
`*~ro[Tslel]
`103
`oo
`
`Petitioner Riot Games,Inc. - Ex. 1005, p. 6
`
`

`

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

`

`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 2 of 11
`
`5,822,523
`
`20
`
`Host A Sends
`
`Host A Receives
`
`88
`,
`
`29 PA|cf]Pt
`No
`pA|OYPt|
`
`Jol>|[>|
`
`Host B Sends
`23
`20
`Host B Receives
`oy~TALELP
`
`24 PBLA|Pe|
`oo
`LeLe,
`og
`—~L2LO1]
`PD|B|PS|
`|B|D|P2|
`
`Host C Sends
`26
`» CEALP]
`24
`oe—LOLe3]
`31
`Pc|O|PS|
`
`Host C Receives
`
`24
`
`nNNDoanN
`@®Qoo
`» tors]=gg “TeToT
`
`
`|D[|c|PA||¢[|D|PS|
`
`Host D Sends
`
`Host D Receives
`
`Figure 2
`Prior Art
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 8
`
`|
`
`

`

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

`

`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 4 of 11
`
`5,822,523
`
`55a
`Host A Sends
`C.
`LETT]
`67a|c|E|P38|
`POLE|Pa|
`
`Host A Receives
`
`54
`
`Host B Receives
`54b
`Host B Sends
`55
`
`PBLEe|P2|S6p PATE]Pt|
`67 pc|E|Ps|
`
`PD]E|Pa|
`
`54c
`Host C Sends
`gn
`eTETR]
`
`57c PBTE|P2|
`Poy Ee|Pa|
`
`Host C Receives
`
`56
`
`64d
`gg,
`seg L&ETP
`pc[TE|PS|
`
`Host D Receives
`
`57
`
`Host D Sends
`STETP]
`
`Figure 4
`Prior Art
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 10
`
`

`

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

`

`
`
`U.S. Patent
`
`Oct. 13, 1998
`
`Sheet 6 of 11
`
`5,822,523
`
`80
`84
`Host A Sends
`Host A Receives
`
`
`pA}STSTP) |S|A}H|P2|45
`
`86 |S[A|H|PS|
`|STATH|Pe|
`81
`Host B Sends
`gg
`pRBYS|S[P2]
`89}BB]!|Ps|
`|S)8|!|P|
`82
`Host C Sends
`Host C Receives
`og
`pc[s{otra}
`pc|)[Pt
`92|¢|3|Pe|
`Pstc}s[ea|
`83
`Host D Sends
`Host D Receives
`
`pots{TGPt a4|D|K|Pi|
`95|D|K|P2|
`|S|0|K|PS|
`
`Host B ReceivesMhml
`
`B4
`
`~
`
`Group Server Sends
`
`\CSTATETPE]
`
`80
`
`ee
`
`Group Server Receives
`
`28
`
`A 9
`
`0
`
`|B]!|PA|:94
`|S|Oo|K|PS|i
`
`c{J
`
`22
`
`93 fs{[c]ys|Pa)
`94|s|D|}K|Pt|
`95 Po|kK{Pe|
`
`
`Figure 6
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 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
`
`96
`
`101 OEEE] 97 ~LA_LS|&|Pt|
`
`
`
`Group Server Sends
`
`Group Server Receives
`
`pS]Bi!|Pt]Ps|Pa|FB |S[Ss||2|
`ee pc]s|6|Ps|
`102
`98
`fs[To|k[Pi[P2|Ps|po}s|sc|
`|Pa|
`
`103
`
`99
`
`Petitioner Riot Games,Inc. - Ex. 1005, p. 13
`
`

`

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

`

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

`

`
`
`U.S. Patent
`
`Oct, 13, 1998
`
`Sheet 10 of 11
`
`5,822,523
`
`Host ULP Address n|Host TLP Address n
`Implicit ULP Group Address m
`
`135
`
`
`Group Server Control
`
`
`
`
`
`
`
`Host ULP Address 0|Host TLP Address 0
`Implicit ULP Group Address 0
`
`
`
`
`
`
`
`
`
`ULP Server Process 0
`
`Host ULP Address a
`
`
`
`Host ULP Address n
`
`ULP Server Process m
`
`
`Host ULP Address a
`
`
`
`
`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 Riot Games,Inc. - Ex. 1005, p. 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
`
`153
`
`154
`
`155
`
`Figure 11
`
`Petitioner Riot Games,Inc. - Ex. 1005, p. 17
`
`

`

`
`
`5,822,523
`
`ma
`
`25
`
`3»
`
`wetm
`
`40
`
`1
`SERVER-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. Today there are many
`commercial cxample 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 modems.
`sysiems, and particularly to server group messaging systems
`The network messages sent by such games contain a wide
`and methods for reducing message rate and latency.
`variety 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 range ofinteractive applications imple-
`mented on computer systems today, All arc characterized by
`The casc of a two player game played over a modem is
`dynamic response to the user. The user provides input to the
`particularly simple. If the message rate is 10 messages per
`second, each 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 oftheir 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 lime 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 ofthe 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
`rate 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 supported by popu-
`to each ofthe other nodes in the network, Each node may be
`lar LANsare high enough to support a large number of
`connected to the network wilh 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
`network by sending messages and receiving messages. Gale-
`The wide area networks available today to consumerusers
`ways are computer systems connecied to the network by
`all musi be accessed through dial-up phone lines using
`more than onc link. They not only communicate with the
`modems, While modem speeds have increased rapidly, hey
`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 marketusc. 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
`5 essary to do so in a way thal 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 gateways 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 each
`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 lines can
`interactive application. Unfortunately, creating such shared
`be advantageously used to compress the TCP/IP beaders.
`networked,interactive applications rons into the limitations
`Even sa, a typical message will be approximately 25 bytes
`of the 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 limes per second from the
`over a network which is 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%.If 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, but
`this
`time 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 beyondjust 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 Riot Games, Inc. - Ex. 1005, p. 18
`
`

`

`
`
`5,822,523
`
`he a
`
`20
`
`3”
`
`3s
`
`>wu
`
`4
`3
`time needed to send all of the outbound packets. Rach packet
`3, packet 21 to host 2 and packet 22 to host 4. Host 1 wants
`to send the same data P1 to each 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 host 3. 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 to the other three hosts. All of these
`provides a new input ontheir system,il is desirable for that
`input to immediately affect the game on all of the other
`packets are carried by the unicast network individually from
`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 playeracts
`As can be seen, cach host must send a packel to every
`to move a target to the time that the target has moved on the
`other host that it wishes to communicate with in an inter-
`screens ofthe otherplayers in the game. A major portion of
`active application. Further, il receives a packct 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 happen at a regular and high rate.
`example the time to send the messagesto the other 7 players
`All of the hosts that wish to 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 reecive the message quickly, it will not be until
`second, With four hosts communicating with one another as
`50 ms have passed that the last player of the seven will have
`received the message.
`in this example, each host will send three messages and
`receive three messages eight lo ten limes per second. As the
`Internet Protocol Multicasting
`is a widely known
`As mentioned before,
`the Intcrnet
`number of hosts in the application that need to communicate
`example of a wide arca network. The Internct is based on a
`with one another grows, the message rate will reach a rate
`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
`corresponds to a layer 3 or Network layer protocol. It
`interactive applications for multiple participants since their
`use will result in the problem of high packet rates that grow
`provides services for transmission and routing of packets
`between two nodes in an internct. The addressing model
`with the number of participants.
`Work has been done to attcmpt 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 Extensions for
`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 protocol
`that enable IP multicasting. IP
`inter-network. Gateways and routers maintain tables that are
`multicasting supports the transmission of a IP datagram to a
`used to lookup routing information based on the destination
`host group by addressing the datagram to a single destina-
`addresses of the packets they receive, The routing informa-
`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—these
`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 topof IP are the layer
`multicasting protocol transmits a multicast datagram to all
`members of the group to which it 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 ensures reliable, 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
`RFC-1180 “A TCPAP Tutorial”.
`IP, TCP and UDP are
`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-
`mitted 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 waats 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
`taulticast router, its group address is compared toalist for
`each local multicsst 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
`sentby the hosts to one another using a conventionalunicas!
`These lists are updated when hosts join or leave multicast
`groups. Hosts do this by sending messages using Internet
`network protocolsuch as IP, Host 1 send packcts 20,to host
`
`30
`
`aa
`
`Petitioner Riot Games,Inc. - Ex. 1005, p. 19
`
`

`

`
`
`5,822,523
`
`5
`Group Management Protocol (IGMP) to their immcdiately-
`neighboring multicast routers. A further attribute of distrib-
`uted multicast messaging is that the roulers mus! propagate
`the group membership information for a particular group
`throughoutthe 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 thesc 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 datagram delivery, where hosts will
`Teceive unwanted datagrams from the duplicate group. This
`requires a method al cach host to filter out the unwanted
`datagrams. Another set of problems resuli from the time
`delay from when a group is created, destroyed or its mem-
`bership changed to when all of the routers needed to route
`the datagrams to the memberhosts have been informed of
`these changes, Imagine the case where Host N joins an
`existing group by sending a join message toits local router.
`The group already contains Host M which is a number of
`router hops away from Host N in the network. Shortly after
`Host N has sent it join message, Host M sends a datagram
`to the group, but the local router of Host M has notyet been
`informed of the change in group membership and as a result
`the datagram is not forwarded to one of the particular
`network links connected to the local router of Host M that
`is the enly path in the network from that router that ulti-
`mately will reach Host N. The resull is that Host N will
`reccive no datagrams addressed to the group from Host M
`uatil
`the local
`router of M has its group membership
`information updated. Otherrelated problems can also occur.
`When