CERTIFICATE OF SERVICE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The undersigned hereby certifies that a copy of this REQUEST FOR REEXAMINATION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`UNDER 35 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 YORK NY 10036
`
`
`
`
`
`
`
`JORDAN ALTMAN
`
`
`SHEARMAN & STERLING LLP
`
`
`
`IP DOCKETING
`
`
`5 99 LEXINGTON AVENUE
`
`
`
`
`
`
`
`NEW YORK, NY 10022
`
`
`
`
`
`
`
`
`
`RAJIV P. PATEL, ESQ.
`FENWICK & WEST LLP
`
`
`
`
`
`
`
`TWO PALO ALTO SQUARE
`
`
`
`
`PALO ALTO, CA 94306
`
`
`
`
`
`
`onal Dash
`
`
`W S
`
`
`
`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
`
`

`

`
`
`Filing Date
`
`
`
`First Named Inventor DANIEL J. SAMUEL
`
`
`
`
`
`
`Art Unit
`
`
`
`Examiner Name
`
`
`
`
`
`Attorney Docket Number
`
`
`
`
`
`8330.003
`
`
`
`
`
`
`
`
`
`
`
`
`PTOJ'SBJ'DBa (05-07)
`
`
`Approved for use through 0980/2007. OMB 0651-0031
`
`
`
`
`
`
`
`U.S. Patent and Trademark Office; U.S. DEPARTMENT OF COMMERCE
`
`
`
`
`
`
`
`
`
`Under the Paperwork Reduction Act of 1995, no persons are required to respond to a collection ofinformation unless it contains a valid OMB control number.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Application Number
`
`
`
`
`
`
`
`
`
`
`
`
`INFORMATION DISCLOSURE
`
`
`
`STATEMENT BY APPLICANT
`
`
`
`
`
`
`
`(Not for submission under 37 CFR 1.99)
`
`
`U.S.PATENTS
`
`
`
`Pages,Cqumns,Lines where
`
`
`
`
`
`
`
`
`
`
`Name Of Patentee or Applicant Relevant Passages or Relevant
`Kmd
`Examiner C'te Patent Number
`
`
`
`
`of Cited Document
`Code1
`.
`Initial
`No
`
`
`
`
`
`
`Figures Appear
`
`
`
`Suzuki et al.
`
`
`
`
`
`
`Issue Date
`
`
`
`
`
`
`1
`
`
`
`5736982
`
`
`
`1998-04-07
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`If you wish to add additional U.S. Patent citation information please click the Add button.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`U.S.PATENT APPLICATION PUBLICATIONS
`
`
`
`
`
`
`Examiner Cite Publication Number
`
`lnitia|*
`No
`
`
`
`
`
`
`Publication
`Kind
`Code1 Date
`
`
`
`
`
`
`
`
`
`Name of Patentee or Applicant
`of cited Document
`
`
`
`
`
`
`Pages,Cqumns,Lines where
`
`
`Relevant Passages or Relevant
`
`
`
`Figures Appear
`
`
`
`
`
`
`
`
`
`If 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
`
`
`
`First Named Inventor
`DANIEL J. SAMUEL
`
`
`
`
`
`
`
`
`
`
`INFORMATION DISCLOSURE
`
`
`
`STATEMENT BY APPLICANT
`(Not for submission under 37 CFR 1.99)
`
`
`
`
`
`
`
`
`
`
`Examiner Name
`
`
`
`
`Attorney Docket Number
`
`
`
`
`
`8330.003
`
`
`
`
`
`Art Unit
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`'
`
`Examiner Cite Foreign eDocument
`
`
`
`No Number
`Initial*
`
`
`
`
`
`Country
`
`
`Code2 i
`
`
`Publication
`Kind
`
`Code4 Date
`
`
`
`
`
`Name of Patentee or
`
`
`
`A licant of cited
`
`
`
`pp
`Document
`
`
`
`
`Pages,Columns,Lines
`where Relevant
`
`
`Passages or Relevant
`
`
`.
`Figures Appear
`
`
`
`
`
`
`
`T5
`
`
`
`
`
`
`
`
`
`1
`
`
`If you wish to add additional Foreign Patent Document citation information please click the Add button
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`NON-PATENT LITERATURE DOCUMENTS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Include name of the author (in CAPITAL LETTERS), title of the article (when appropriate), title of the item
`Examiner Cite
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`T5
`(book, magazine, journal, serial, symposium, catalog, etc), date, pages(s), volume-issue number(s),
`Initials*
`No
`
`
`
`publisher, city and/or country where published.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Server2.5p|4.tar.gz (“Server Code”) and BRMH-‘I .7.tar.gz (”Client Code”)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(source code dated no later than August 19941) ("Netrek")
`
`
`
`1
`
`J. OIKARINEN ET AL. RFC 1459, "Internet Relay Chat Protocol", published May 1993 (“IRC RFC”).
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2
`
`
`
`
`
`
`
`
`
`R. FRIEDMAN ET AL. "Packing Messages as 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 (“Van 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
`
`T. A. FUN KHOUSER, “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”).
`
`
`
`6
`
`
`
`
`
`
`
`
`
`ANDY MCFADDEN, “The History of Netrek”, published January 1, 1994 (“McFadden").
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`7
`
`EFS Web 2.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
`
`

`

`
`
`
`
`MICHAEL R. MACEDONIA. “Exploiting Reality with Multicast Groups”. published September 1995 (“Macedonia”)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`If you wish to add additional non-patent literature document citation information please click the Add button
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EXAMINER SIGNATURE
`
`
`
`Date Considered
`Examiner Signature
`
`
`
`
`
`
`
`
`
`
`*EXAMINER: Initial if reference considered, whether or not citation is in conformance with MPEP 609. Draw line through a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`citation if not in conformance and not considered.
`Include copy of this form with next communication to applicant.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Application Number
`
`
`
`Filing Date
`
`
`
`First Named Inventor
`DANIEL J. SAMUEL
`
`
`
`
`
`
`
`
`Art Unit
`
`
`
`Examiner Name
`
`
`
`
`
`INFORMATION DISCLOSURE
`
`
`
`STATEMENT BY APPLICANT
`(Not for submission under 37 CFR 1.99)
`
`
`
`
`
`
`
`
`
`8330.003
`Attorney Docket Number
`
`
`
`
`
`
`
`
`
`
`
`1 See Kind Codes of USPTO Patent Documents at www.USPTO.GOV or MPEP 901.04. 2 Enter office that issued the document, by the two-letter code (WIPO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Standard ST.3).
`3 For Japanese patent documents, the indication of the year of the reign of the Emperor must precede the serial number of the patent document.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 here if
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`English language translation 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
`
`

`

`
`
`Ulllted States Patent
`[191
`1111 Patent Number:
`5,822,523
`
`Rothschild et aL
`[45] Date of Patent:
`Oct. 13, 1998
`
`USOthA
`
`[54]
`
`SERVER—GROUP MESSAGING SYSTEM FOR
`MERACTIVF. APPLICATIONS
`
`{75]
`
`lnvcntnrx' Jehy .l. Rothschild; Marc P.
`Kwhthtwakl. both of Lns Galas;
`Daniel J. Samuel. Sunnyvale. all of
`C l'L
`“
`[73] Asian”; Mpoth Interactive, Inc. Mountain
`View. Calif.
`
`Primary Examiner—William M. 'l'teat
`Asthma: Examiner—Zuni Maung
`Murray, Agent, or Firm—H. C. Chan; Wison Sonsini
`amid, & Routi
`
`[57]
`
`ABSTRACT
`
`A method for deployitg intereaive applications over a
`network containing host computers and group messaging
`servers is ditclosed. The method operates in a conventional
`unicast network architecture comprised of conventional net-
`work links and unicast gateways and routerx The hosts. send
`mange: containing destination group addresses by unionst
`to the group misusing servers. The group addresses select
`meme: your» uninluncd by the Imp mutating 9mm-
`For each mmage group. the group messaging servers also
`maintain a I'mt of all of tin hosts that are members of the
`partiwlar your}.
`In its most simple implementation. the
`method consists of the group server receiving a mg:
`from a host containing a destination group address. Using
`the group adtiess, the group awning sewer then soled:
`a message group which lists all of the host members of the
`References Cited
`11 which are the
`etsoi mesagesto the
`u .'lhe
`5:11: messaging servlzigthen forwarth the memggt: cad:
`”-5- PATEiT DOCUMENTS
`
`0‘ “I “fit“ how in '0 imemive awliwimr. many
`9/1934 Cotton et al.
`m... 370/60
`4,no,954
`messages will be arriving at the group server elm: to one
`1/1992 Putin-n o
`._.. 370/943
`5,079,767
`another in time. Rather than simply forward each message to
`9/1992 Sidhu et a!
`.. 395000.01
`5,l50,464
`
`its targeted hosts. the group massaging server aggregates the
`5/199‘ C340“ d I|~ ~-
`v-« 379/60
`5.309.433
`
`
`contents of each of mesuges received during a specified
`33233; m3: fine-1:151“
`mil)?
`time period and then sends an aggregated mmge to the
`'
`9
`'
`.....
`"
`
`
`33:33 Wig; misfit"? “'
`.. gm targeted hosts The time period can be defined in a number
`5 5'7 ‘94
`Sll996 Green
`37%“
`of ways. This method reduce; the message trafic belween
`'
`'
`hosts in a networked interactive application and contributes
`FOREIGN PATENT DOCUMENTS
`to reducing the latency in the communications between the
`0637l42
`1/1995 Eflupun PaL on. .
`mm
`W0 9S,'l0908
`4/1995 WIFO
`W0 95/10)“
`4/l995 wtm .
`
`[2]] App]. No; ”$23
`122]
`Filed:
`POI). 1.1996
`
`151]
`int. cu
`
`[52] us. Cl.
`
`HMH 1102
`” 395%.”: 3953““;
`395nm“)
`
`.........~... 395ml]. 2mm.
`Flcld of Search
`395/20039,
`‘17, 200.05, 793; 370/8543,
`60
`
`[58]
`
`[561
`
`6 Clllml; ll Drawhg Sheet:
`
`no
`
`'7
`
`l
`
`U
`
`mo
`
`first A Rn-
`Neil A Sena
`uuum nunmmm
`‘01
`
`flout l lano-
`
`Ibet I Receivi-
`
`I03
`
`MC m
`Nut 0 SM
`nunm unnmmm
`1M
`
`“6. D m
`
`M Dm
`
`IO)
`U
`Gimp San-r Rut-u
`Gimp Bow 3-0
`m “nun-mm ., an:-
`'3
`null-mm u '
`Elli-Elm“ “I!“
`I
`I5]
`”25— ")
`
`Petitioner Valve Ex. 1005, Page 6
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 6
`
`Petitioner Valve Ex. 1005, Page 6
`
`

`

`
`
`US. Patent
`
`011 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
`
`

`

`
`
`US. Patent
`
`0m. 13, 1998
`
`Sheet 2 or 11
`
`5,822,523
`
`Host A Sends
`
`Host A Receives
`
`MN-o E E 88E
`22 “In 29
`-flm
`"I!
`n-IZI
`
`23
`Host 8 Sends
`20
`Host B Receives
`24 un- 27 -nm
`25 m 30
`-I§llil
`“Ella
`nun:
`
`Host C Receives
`21
`Host C Sends
`26
`2, “In 24 u-m
`28
`-I2Im 31
`fl-IEI
`-IIIEI
`“-2:
`
`Host D Sends
`
`Host D Receives
`
`b
`
`(JONOEDEi
`31 nun!
`fl-IZI
`
`MNUINi
`28 Bum
`-nlil
`
`FigureZ
`Prior Art
`
`Petitioner Valve Ex. 1005, Page 8
`Petitioner Riot Games, Inc. - Ex. 1005, p. 8
`
`Petitioner Valve Ex. 1005, Page 8
`
`

`

`
`
`US. Patent
`
`Oct. 13, 1998
`
`Sheet 3 or 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
`
`

`

`
`
`US. Patent
`
`0n.13,1993
`
`Sheet 4 of 11
`
`5,822,523
`
`54
`
`55
`
`56
`
`57
`
`Host A Sends
`
`-lalzl
`
`55a
`
`563
`
`Host A Receives
`
`Host B Sends
`IEIBIEI
`
`Host B Receives
`54b
`5% -nm
`57,,
`-lam
`lila-
`
`Host C Sends
`III-am
`
`54c
`
`Host 0 Receives
`
`576 “El?!
`[Elam
`
`Host D Receives
`54d
`Host D Sends
`Isl-am 55d un-
`56d “lam
`-IIII‘I
`
`Figure 4
`Prior Art
`
`Petitioner Valve Ex. 1005, Page 10
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 10
`
`Petitioner Valve Ex. 1005, Page 10
`
`

`

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

`

`
`
`US. Patent
`
`Oct. 13,1998
`
`Sheet r. of 11
`
`5,822,523
`
`80
`
`Host A Sends
`
`84
`
`Host A Receives
`
`as n-um
`as
`
`81
`
`82
`
`Host B Sends
`
`Host C Sends
`
`87
`
`ea
`
`89
`
`90
`
`Host 8 Receives
`
`“III--
`Host C Receives
`
`-u-- 91---Iil
`92 “'3
`
`“III
`
`83
`
`Host D Sends
`
`93
`
`Host D Receives
`
`Baum 94 unn-
`95
`nun:
`
`“Ii-Hm[I
`
`Group Server Receives
`
`80
`31
`82
`
`84
`Group Sewer Sands
`as “-132:
`Eas
`a7 n-um 83
`as ann-
`89
`“Ell-IE!
`so “III-Ill
`91 um
`C
`J
`P2
`92
`
`93
`94
`
`95
`
`(—
`
`C
`
`P4iii
`
`Figure 6
`
`Petitioner Valve Ex. 1005, Page 12
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 12
`
`Petitioner Valve Ex. 1005, Page 12
`
`

`

`
`
`US. Patent
`
`Oct.13,1998
`
`Sheet 7 of 11
`
`5,822,523
`
`
`
`Host A Sends
`
`
`
`97
`
`98
`
`
`
`
`Host 8 Sends
`
`Host C Sends
`
`
`
`
`
`
`
`Host A Receive:
`
`Host 8 Receives
`
`Host 0 Receives
`
`
`
`100
`
`101
`
`102
`
`103
`
`Host D Receives
`
`100
`
`102
`
`103
`
`Group Server Sends
`
`[in-mm
`
`nun-lam
`
`96
`
`9,
`
`98
`
`99
`
`Group Server Receives
`
`n
`
`II
`
`Figure 7
`
`Petitioner Valve Ex. 1005, Page 13
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 13
`
`Petitioner Valve Ex. 1005, Page 13
`
`

`

`
`
`US. Patent
`
`Oct 13, 1998
`
`Sheet 8 or 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
`
`

`

`
`
`US. Patent
`
`Oct 13,1998
`
`Sheet 9 01' 11
`
`5,822,523
`
`123
`
`124
`
`125
`
`126
`
`127
`
`128
`
`129
`
`
`
`
`
`Transpon ULF Msg. Best ULP Address Destination
`Header
`Type
`Address
`Count
`Address 1
`
`Destination Pa load
`Address N
`y
`
`116
`
`117
`
`118
`
`119
`
`120
`
`121
`
`122
`
`
`
`
`Message Some ULP
`
`Data
`
`Source ULP
`
`Data
`
`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 or 11
`
`5,822,523
`
`135
`
`
`Group Sewer Contra!
`
`
`
`
`
`
`
`
`
`
`Host ULP Address 0 Host TLP Address 0
`
`
`
`Inplioit ULP Grow Address 0
`
`
`
`
`
`
`
`
`
`
`
`Host ULP Address n Host TLP Address n
`
`Inplicit LlP Group Address m
`
`ULP Sewer Process 0
`
`ULP Server Process In
`
`Hofl ULP Address 3
`
`
`
`Host ULP Address a
`
`
`
`
`
`Host ULP Address n
`
`Host ULP Address 11
`
`
`
`
`
`Logtcd ULP Adrkess m
`Logical ULP Address 0
`Host ULP Address 3
`Host ULP Address 3
`
`
`
`Host ULP Address 11
`Host ULP Address n
`
`
`
`Figure 10
`
`Petitioner Valve Ex. 1005, Pagé 16
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 16
`
`Petitioner Valve Ex. 1005, Page 16
`
`

`

`
`
`US. Patent
`
`0m. 13, 1998
`
`Sheet 11 or 11
`
`5,822,523
`
`150
`
`
`
`Interactive Application
`
`
`
`Host Interface for Upper Level Protocol
`
`ULP Address 0
`
`
`TLP Address 0
`
` T
`
`
`ULP Address n
`
`LP Address n
`
`
`153
`
`
`
`
`Host Interface for Transport Level Protocol
`
`Network Communications Stack
`
`Network Interface
`
`154
`
`155
`
`Figure I]
`
`Petitioner Valve Ex. 1005, Page 17
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 17
`
`Petitioner Valve Ex. 1005, Page 17
`
`

`

`
`
`I
`SERVER-GROUP MESSAGING SYSTEM FOR
`INTERACTIVE APPLICATIONS
`
`5 322,523
`
`2
`consistent between all of the PCS. in a game that created the
`illusion of a spatial environment where each player amid
`move. the packets could contain information about the new
`positions of the players as they moved. Today there are many
`commercial example of PC games that can he played
`between muliple players on local Area Networks (LANs)
`or by two players over dial-up phone litres using morbms.
`The network manages sent by such games contain a wide
`variety of information specific to the game. This can include
`prisition and velocity information of the objects in the game
`along with special actions taken by a player that effect the
`other players in the game.
`The can of a two player game played over a modem is
`particularly simple. If the message rate is 10 messages per
`second. each PC sends 10 messages per second to the other
`PC and receives 10 messages per second. The delay intro-
`duced by the modems and phone line is small and will not
`he noticed in most games. Unfortunately. the clue of two
`players is uninteresting for networked interactive applica-
`lions. With the name game played with 8 players on a IAN.
`the message rate increases Each PCmust send 7 messages.
`one to each of the other 7 players every time pcrbd and will
`receive 7 messages from the other players in the same time
`perbd. If the messaging time period is 1“) ms. the total
`message rate will be 70 messages sent per second and 70
`messages received per second. As can be seen the usage
`rate increases linearly with the number of players in the
`game. The message rates and data rates supported by popu-
`lar We are high enough to support a large number of
`players at reasonable message sizes. Unfortunately. LAN:
`are only deployed in commercial applications and cannot be
`consideted for deploying a networked interactive applica-
`tion to consumer ours.
`The wide area networks available today to consumer users
`all must be accessed through dial-up phone lines using
`modems. While modem speeds have increased rapidly, they
`have now reached a bit rate (#33 Khils/sec whidft ‘5 close
`to the limit set by the signal-to—mise ratio of conventional
`phone lines. Further speed increaaea are possible with lan,
`but this technology is not ready for mass market use. Other
`new wide area networking technologies are being discussed
`that would provide much higher bandwidth. but none are
`close. to commercial operation. Therefore. in deploying a
`networked. interactive application to consumers, it is nec-
`essary to do so in a way that operates with existing nel-
`working and communications infrastructures.
`In the example of the 8 player networked game, consider
`a wade area network implementation where the PC: of each
`of the players is connected to the network with a ma
`Kbit/scc mmietn. Assume that
`the network used in this
`example is the Internet so that all of the network protocols
`and routing behavior is well defined and understood. if the
`game usesTL‘P/ll' to send its messages between the PCs in
`the game. the PPP protocol over the dial-up phone lines can
`be advantageosly used to compress the 'I‘CPIIP headers.
`Even la. a typical message will be approximately 25 bytes
`in sin. Sent
`through the modem. this is 750 bits. The
`messages are sent 10 limm per second to each of the other
`PCs in the game and received to times per second from the
`other PCs This is 35.0 Kbits/aoe which exceeds the capa-
`bilities oi ll: modem by 20%. if the messages are reduced
`to 20 bytes, just 8 players can be supported. but
`this
`approach clearly cannot support networked interactive
`applications with large numbers of panieipants. There are
`other problems beyond just the bandwidth of the network
`connection. There is the loading on each PC caused by the
`high packet rates and then: is the latency introduced by the
`
`10
`
`15
`
`35
`
`45
`
`55
`
`FIELD OF THE INVENTION
`
`invention relates to computer network
`The present
`systems, and particularly to server group messaging systems
`and methods fior reducing message rate and latency.
`BACKGROUND OF THE INVENTION
`'lhere are a wide range oi interactive applications imple-
`mented on computer systems today. All are characterized by
`dynamic response to the riser. The user provides input to the
`computer and the application rcsponrh quickly. One popular
`example of interactive applications on poisons! computers
`(PCs) are games. In this case. rapid response to the user may
`mean rethawing the screen with a new picture in between 30
`ms and 100 ms.
`interactive applications such as games
`control the speed of their interaction with the user through
`an internal time base. The application lacs this time base to
`derive rates at which the user input is sampled. the screen is
`redrawn and sound is played.
`As computers have become more power‘htl and common,
`it has become important to connect them together in net-
`works. A network is comprised of nodes and links. The
`nodm are conneued it such a way that then: exists a path
`from each node over the links and through the other nodes
`to each of the other nodes in the network. Each node may be
`contracted to the network with one or more links. Nodes are
`further categorized into hosts. gateways and routers. Hoots
`are computer systems that are connected to the network by
`one link. They communicate with the other nodes on the
`networkbysending manages and rocciving messages. Gale-
`waya are computer systems connected to the network by
`more than one link. They not only communicate with the
`other nodes as do hosts. but they also forward messages on
`one or their network links to other nodes on their other
`network links This pmssing of forwarding messages is
`called routing. in addition to sending and receiving mee-
`sagcs and their routing functions, gateways may perform
`other functions in a network. Routers arc nodes that are
`connected to the network by more than one link and whose
`sole function '5 the forwarding of messages on one network
`link to the other network links to which it is comected. A
`network consisting of many network links can be thought of
`as a network of sub-networks with gateways and/0r routers
`connecting the submetworks together into what is called an
`internet. Today the widely known examph of a world wide
`internet in the so called "lntemet" whidt in 1995 has over 10
`million computers connected full time world-wide.
`With so many computers on a single world-wide network.
`is duirahtc to create interactive networked applications
`it
`that bring together many people in a shared, networked,
`interactive application. Unfortunately. creating such shared
`networked. interactive applications runs into the limitations
`of the existing network technology.
`As an example. consider a game dsigned to be deployed
`over a network which is to be played by multiple players
`simultaneously. The game could be implemented in soflware
`on a PC connected to a network. A rate set by its internal
`time base, it would sample the inputs ol the local user.
`receive damages from the network from the PCs ollhe other
`players and send messages out to the PCs of the other
`players. A typical rate will be ten lime per second [or I time
`period of 100 ms. The messages sent between the PCs would
`contain information that was needed to keep the game
`
`Petitioner Valve Ex. 1005, Page 18
`
`Petitioner Riot Games, Inc. - EX. 1005, p. 18
`
`Petitioner Valve Ex. 1005, Page 18
`
`

`

`
`
`5,822,523
`
`3
`time needed to send all ofthe outbound packets. Each packet
`sent or received by a PC will require some amount of
`processing time. As the pedtet
`rate increases with the
`number ofplayers in the game, loss and less of the processor
`will be available for
`running the game software itself
`Latency is important it an interactive application became it
`defines the responlveness of the system. When a player
`provides a new input on their system, it is desirable [or that
`input to immediately affect the game on all of the other
`players systems. This is particularly important in any game
`where the game outcome depends on players shooting at
`targets that are moved by the actions of the other players.
`latency in this case will he the time from when I player acts
`to move a target to the time that the target has moved on the
`screen of the other playets in the game. A major portion of
`this latency will come from the time needed to send the
`messages to the other seven players in the game. In this
`example the time to send the messages to the other 7 players
`will be approximately 50 ms While the first player of the
`seven will receive the message quickly, it will not be until
`50 ms have passed that the last player of the seven will have
`received the memge.
`Internet Protocol Mutticesting
`As mentioned before,
`the Internet is a widely known
`example of a wide area network The lntcmet ‘3 based on a
`protocol appropriately called the Internet Protocol (1P). tn
`the OSI reference model for layers of network protocols. [P
`corresponds to a layer 3 or Network layer protocol. It
`provides services for transmission and routing of packets
`between two nods in an internet. The addressing model
`provides I 32 bit address [or all nodes in the network and all
`packets carry source and destination adchems [P also
`defines the routing of packets hemen network links in an
`inter—network. Gateways and routers maintIin tables that are
`used to lookup routing infnnnatioo based on the destination
`addresses of the packets they receive. The routing informa-
`tion tells the galewaylroutcr whether the destination of the
`packet is directly reachable on I local network link con-
`nected to the gateway/router or if not, the address of another
`gatewayirouter on one of the local network links to which
`the packet should be forwarded. On top of IP are the layer
`4 transport protocols TC? and UDP. UDP provides datagram
`delivery services to applications that does not guarantee
`reliable or ln-order delivery of the dalagrams. TC? is a
`connection oriented service to applications that does provide
`reliable delivery of a data stream. it handles division of the
`stream 'mto paclnets and ensures reliable. in-ordcr delivery.
`See the Internet Society RFCs: RFC-791 “lntemet
`Protocol". RFC-793 “Transm'mion Control Protocol" and
`RFC-1180 "A 'l‘Cl’rlP Tutorial".
`IF. TCP and UDP are
`unicast protocols packets. streams or datagmnts are trans-
`mitted from a source In a single destination
`As an example. consider FIGS. 1 and 2. FIG 1 shows a
`conventional unicast network with hosts 1. 2. 3 and 4 and
`network links 11, 12, 13, 14,15,161], 18 and [9 ant routers
`5. 6. 7. B. 9 and 10.1u this exampburxb host wants to send
`a data payload In each of the other hosts. Host 1 has network
`addressA. host 2 has network address C. host 3 has network
`address B and host 4 has network ath‘lrcss D. Existing
`network protocols are typically based on packet formats that
`contain a source address. destination address and a payload.
`This is representative of commonly used wide area network
`protocols such as 11’. There are other components in an actual
`lP packet, but for sake of this example, only these items will
`he considered. H6. 2 shows the example packets that are
`sent by the hosts to one another using I conventional unicast
`network protocol such as IE Host 1 send packctazo. to host
`
`4
`3. packet 21 to host 2 and packet 22 to host 4. Host I want:
`to send the same data P1 to each of the other three hosts.
`therefore the payload in all three packets 's the same. Packet
`20 travels over network links 11, 12. 15 and 18 and through
`routers 5, 6, and 8 to reach host 3. in I similar fashion host
`3 sends packets 23 to host 1. packet 24 to host 2 and packet
`25m host-t. Head and hostlsend pecket326.27.28 and
`29. 30. 31 respectively to the other three hosts. All of these
`packets are unit] by the unimt network individually from
`the sourur host to the destination host. So in this example
`each host must send the: packets and receive three packets
`in order for each host to send its payload to the other three
`hosts.
`As can be seen. each host must send I packet to every
`other host that it wishes to communicate with in an inter-
`active application. Further. it receives I packet from every
`other host that wishes to communicate with it. in an inter-
`active application. this will happen at I regular and high rate.
`All of the hosts that wish to connnunicatc with one another
`witt need to send packets to each other eight to ten times per
`second. With [our hosts communicating with one another as
`in this example, each host will send three memes and
`receive three naassaws eight to ten times per second. As the
`number of hosts it the application that need to communicate
`with one another grows. the message rate will reach a rate
`that cannot be supported by conventional dial-up lines. 'lhis
`mam unicast transport protocols unsuitable for delivering
`interactive applications for multiple participants since their
`use will remit in the problem of high packet rates that grow
`with the number of partie'pants.
`Work has been done to attempt to extend the IP protocol
`to support multicasting. See RFC-1112 “Hos Extensions for
`IP Multicastitg". This document descn‘ltes a set of exten<
`slim: to the l? protocol
`that enable 1? multicasting. [P
`multicasting supports the transminion of I IPdatagnt-n to a
`host group by addressing the dstagram to a single destina-
`tion address. Multican adtkcasea are a subset of the IP
`address space and identified by class Dll’ addrem-tbese
`are 11’ addresses with “1110” in the high order 4 bits. The
`host group contains urn or more IP hosts and the 1P
`multicasting protocol transmits a multicast datagram to all
`members of the group to which it is addressed. Hosts may
`join and leave groups dynamically and the routing of mul-
`ticast datagram is supported by mullicast routers and gate-
`ways. It
`is proper to describe this generIl approach to
`multicast waging as “distributed multicast messaging”. It
`is a distributed technique because the job of message deliv-
`ery and duplication is distributed throughout the network to
`all of the multicat routers. For distributed mutticast mes-
`saging to work in a wide area network, all of the routers
`handling datagrams for multicasl hosts must support the
`routing of muhicast datagrams. Such multicast routers must
`be aware of the mnlticaat group membership of all of the
`hosts locally connected to the router in order to deliver
`multicut daugrams to local lusts. Multicast rwters must
`also be able to forward multicast packets to routers on their
`local network links. Multicast routers must also docide to
`which if any local routers they must forward multicast
`datagrams. When a multicast datagram is received, by a
`multicast router, its group addrw is compared to a list for
`each local mnlticast router of group addresses. When there
`is a match. the datagram is then forwarded to that local
`multicast
`router. Therefore.
`the multiesst routers in the
`network must maintain an accurate and up to date list of
`group addresses for which they are to forward datagrams to.
`These lists are updated when hosts join or leave mulicaa
`groups. Hosts do this by sending messages using lntemet
`
`10
`
`15
`
`25
`
`45
`
`SS
`
`65
`
`Petitioner Valve Ex. 1005, Page 19
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 19
`
`Petitioner Valve Ex. 1005, Page 19
`
`

`

`
`
`5,822,523
`
`5
`Group Management Protocol (lUMP) to their immediately-
`neigflaoring multicatit routers. A further attribute 0t distrib-
`uted mullicast messaging is that the routers must propagate
`the group membership information for a particular group
`throughout the network to all of the other routers that will be
`forwarding trifle [or that group. RFC-1112 does not
`describe how this is to be done. Many different approaches
`have hwn defined for solving this problem that will he
`mentioned later in descriptions of related prior art. Despite
`their differences. all of them approachu are methndt for
`propagation of multicast routing information between the
`multicast routers and techniques for rattling the multicut
`datagrarm in an inter-network stpporting distributed multi-
`east messaging.
`llte distributed multicaat messaging approach has a num-
`ber ot‘undeeirahle side cfl'ccts. The process of propagation of
`group membership information to all of the relevant routers
`is not instantaneous. In a large complex network H 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 memberdaip update most part through. This procme
`can easily take many seconds and even minutes depending
`on the specifics of the algorithm that
`is used. RFC-1112
`mentions this prt'blem and some ofthe side effects that must
`he handled by an implementation of a practical routing
`algorithm tor multicast messaging. One problem results
`when groups are dynamically created and destroyed. Since
`there is no central authority in the network for amigning
`group addresses. it busily pomible in adhtributcd network
`for there to be duplication ofgroup adtiess asignmenl. This
`will result in incorrect daugram delivery. where hosts will
`receive unwatued datagrams from the duplicate group. This
`requires a method at each host to filter out the unwanted
`datagrants. Another set of problems result from the time
`delay iron! when a group is wanted, destroyed or its mem-
`bership changed to when all of the routers needed to route
`the datagrarm to the member hosts have been informed of
`these changes.
`imagine the case when: Hoar N joim an
`existing group by sending I: join manage to its but router.
`The group already contains Host M which is a number at"
`router hops