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

`

`
`
`
`
`INFORMATION DISCLOSURE
`
`
`
`STATEMENT BY APPLICANT
`(Not for submission under 37 CFR 1.99)
`
`
`
`
`
`
`
`
`Application Number
`
`
`Filing Date
`
`
`
`First Named Inventor
`DANIEL J. SAMUEL
`
`
`
`
`
`
`
`Art Unit
`
`
`Examiner Name
`
`
`
`
`
`Attorney Docket Number
`
`
`
`
`
`8330.003
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`'
`
`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 Riot Games, Inc. - EX. 1005, p. 3
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 3
`
`

`

`
`
`INFORMATION DISCLOSURE
`
`
`
`STATEMENT BY APPLICANT
`(Not for submission under 37 CFR 1.99)
`
`
`
`
`
`
`
`
`
`Application Number
`
`
`
`Filing Date
`
`
`
`First Named Inventor
`DANIEL J. SAMUEL
`
`
`
`
`
`
`
`
`Art Unit
`
`
`Examiner Name
`
`
`
`8330.003
`Attorney Docket Number
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 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
`
`

`

`
`
`usonsszzszm
`
`[19]
`United States Patent
`5,822,523
`[in Patent Number:
`
`[45] Date of Patent: Oct. 13, 1998
`Rothschild et al.
`
`[54] SERVERvGROUP MESSAGING SYSTEM FOR
`INTERACTIVE APPLICATIONS
`
`[75]
`
`Inventors JeilI'ey .l. Rothschild; More P.
`Kwhthlwlki, both of Los Gums;
`Daniel J. Samuel. Sunnyvtie. all of
`Caltt
`[73] Assignoo; Mpnth Interactive. Inc. Mountain
`View. Calif.
`
`[211 Appl. No: ””23
`_
`”I" 1' 1996
`“1"“
`[22]
`tm. (1° to HMH 1/02
`[51]
`[521 us. or.- arts/200.17; 395mm;
`395mm)
`Field 0f Search ...........~.........m.. 395,101“. 200.01.
`39S/200.09, 20017, 200.05, 793; 370/8513,
`50
`
`[53]
`
`[561
`
`Rehnmees Cited
`”-5- PM DOCUMENTS
`“70.954
`370/50
`9/1934 can” a .1,
`_
`5,079,767
`.o 370/943
`"1992 Perirnntt
`
`5,I50,464
`9/1992 Sim et oi.
`..
`395/2000I
`5.309.433
`5/199‘ 54°“ et at.
`-« 370/60
`
`
`'
`' m
`3
`*
`230233;
`:13: $3333? 0'
`”mill
`”61'2“ “/19“ ”WW et “"
`"""‘ 370/“)
`
`5,475,819
`3950M.0|
`12/1995 Miller et Al
`5 5'7 ‘94
`5/1996 Green _____
`37%|]
`'
`'
`FOREIGN PATEN'l‘ DOCUMENTS
`0637l42
`i/t995 Euopun Pal. Oil. .
`WODSt'imflti
`l/l995 WlPO
`wo 95/t0)ll
`4/1995 wtm i
`
`Primary Examiner—William M. 'l'reat
`Animal Examiner—2am Mating
`Manley, Agent, or Firm—H. C. Chan; Wison Sonsini
`Goodrich & Ronni
`
`[57]
`ABSTRACT
`A method for deploying internetive applications over a
`network conuining host computers and gmup messaging
`servers is diwlosedr The method operates in I conventional
`unicast network architecture comprised of conventional net-
`work links and uniast gntewnys and routers The hosts send
`messages containing destination group addresses by unicust
`to the group misusing servers. The group addresses select
`meme: your» mintamod by the your) manning samu-
`F"! =th "mm ImuP- the IMP Wsint “M's 8'50
`maintain a list of all of the hosts that are members of the
`particular group in its most simple implementation. the
`mtthod mists of the group server receiving 3 mg:
`from a host oontoining a destination group address. Using
`the group address, the group manning server then selects
`a mega group which lists oil at the host members of the
`n which are the
`«so! memgesto the
`u .11»
`Sign: messaging servlzigthcn forwarch the manager: and:
`of the target hosts,
`in an interactive apptication. many
`messages will be arriving at the group server clan: to one
`molhcr in lime. Rather than simply forward each message to
`its targeted hosts. the group messaging server aggreptee the
`time
`riod and then sends an a
`tired [DOES]
`to the
`contents of each of messages received during a specified
`target}; hosts. The time period cagrfi'fdefined in fflwmbet
`.
`of ways. Thts method reduce-m the message trafic between
`hosts in a networked interactive application and contributes
`to reducing the latency in the communications between the
`“a”
`
`6 Chime. 11 Drawing Street:
`
`M
`
`97
`
`I
`
`U
`
`1m
`
`tit-t A Rn-
`Mal A Song
`_flflm nunmmm
`‘01
`
`met I Room-o
`Meet I Iona
`_num an nmmm
`I03
`
`MC m
`Nut 0 Bill
`nunm unnmmm
`1M
`
`Ned D Sella
`_KIEIIZI
`
`that D Home
`"nun-mm
`
`‘m
`Glows-Wm
`U WWW—-
`w, unnmmm ., unnmnut-um
`unnu-
`‘°’ nut-mum “' unnm
`103
`W
`
`Petitioner Riot Games, Inc. — Ex. 1005, p. 6
`
`

`

`
`
`US. Patent
`
`01:1 13,1998
`
`Sheet 1 or 11
`
`5,822,523
`
`
`
`Figure 1
`Prior Art
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 7
`
`

`

`
`
`US. Patent
`
`Oct. 13, 1998
`
`Sheet 2 or 11
`
`5,822,523
`
`Host A Sends
`
`Host A Receives
`
`asi 88H/
`22 "-m 29 -um
`-fllil
`n-m
`
`Host B Receives
`20
`Host B Sends
`23
`24 “-- 2, -nm
`25 n 30
`-I§ll2‘l
`“Ella
`mum
`
`Host C Receives
`21
`Host 0 Sends
`26
`2, “In 24 u-m
`28
`-IEIIEI
`31
`Iii-[2|
`-nm
`u-Iil
`
`Host D Sends
`
`Host D Receives
`
`(JONCIDi, MNGINi
`31 nun!
`28 Eula
`“--
`-IEIIE‘I
`
`FigureZ
`Prior Art
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 8
`
`i
`
`

`

`
`
`US. Patent
`
`0cL13,1998
`
`Sheet 3 or 11
`
`5,822,523
`
`
`
`Figure 3
`Prior Art
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 9
`
`

`

`
`
`US. Patent
`
`Oct. 13,1998
`
`Sheet 4 of 11
`
`5,822,523
`
`54
`
`55
`
`56
`
`57
`
`Host A Sends
`
`-fllil
`
`553
`
`5.5;,
`
`Host A Receives
`
`'
`t B R
`ecelves
`Hos
`54b
`Host B Sends
`-fllil
`“BE 55,,
`57,, -EE
`“I3-
`
`Host C Sends
`
`54c
`
`Host C Receives
`
`57c “Eli!
`Iii-3m
`
`54d
`Host D Sends
`Imam 5%
`56d “lam
`"I:
`
`Host D Receives
`
`Figure 4
`Prior Art
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 10
`
`

`

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

`

`
`
`US. Patent
`
`0;; 13,1993
`
`Sheet 6 of 11
`
`5,822,523
`
`80
`
`Host A Sends
`
`81
`
`82
`
`Host B Sends
`
`Host C Sends
`
`84
`
`as
`
`as
`
`87
`
`as
`
`as
`
`90
`
`Host A Receives
`
`Host 8 Receives
`
`Host C Receives
`
`-“ 91 nun!
`92 “'3
`
`Hum
`
`83
`
`Host D Sends
`
`93
`
`Host D Receives
`
`“an“ 94 nun-
`95 mum
`
`[In-amE
`
`84
`
`Group Sewer Sands
`
`80
`
`Group Server Receives
`
`as n-um 32
`
`e7 n-nm 83
`as unn-
`89 uni-m
`
`90 uni-m
`91
`
`92
`
`93
`94
`
`95
`
`O
`
`c
`
`:—EEEP4
`EEE
`
`Figure 6
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 12
`
`

`

`
`
`US. Patent
`
`Oct. 13,1998
`
`Sheet 7 of 11
`
`5,822,523
`
`
`
`
`Host A Receive:
`
`Host 8 Receives
`
`
`Host A Sends
`
`
`
`
`
`
`Host 8 Sends
`
`Host C Sends
`
`100
`
`101
`
`102
`
`97
`
`98
`
`99
`
`Host 0 Receives
`
`
`
`Host D Receives
`
`103
`
`Group Server Sends
`
`101 nunmmm 9,
`
`96
`
`Grou
`
`p Server Receives
`
`Bun--
`
`“-IZIEI
`
`nun-lam
`
`B
`
`I!
`
`98
`
`99
`
`102
`
`103
`
`Figure 7
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 13
`
`

`

`
`
`US. Patent
`
`0a, 13, 1998
`
`Sheet 8 of 11
`
`5,822,523
`
`
`
`Figure 8
`Prior Art
`
`Petitioner Riot Games, Inc. - EX. 1005, p. 14
`
`

`

`
`
`US. Patent
`
`Oct 13,1998
`
`Sheet 9 0111
`
`5,822,523
`
`123
`
`124
`
`125
`
`126
`
`127
`
`128
`
`129
`
`
`
`
`
`Transport ULP Msg. Dest. ULP Address Destination
`Header
`Type
`Address
`Count
`Address 1
`
`Destination Pa load
`Address N
`y
`
`116
`
`117
`
`118
`
`119
`
`120
`
`121
`
`122
`
`
`
`
`Message
`
`Source ULP
`
`Data
`
`Source ULP
`
`
`
`Data
`mm W
`
`
`
`130
`
`131
`
`132
`
`
`
`Figure 9
`
`
`
`
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 15
`
`

`

`
`
`US. Patent
`
`Oct. 13,1998
`
`Sheet 10 or 11
`
`5,822,523
`
`135
`
`Host ULP Address n Host TLP Address n
`
`Implicit LlP Group Address m
`
`ULP Sewer Process 0
`
`ULP Server Process 111
`
`Hosl ULP Address 3
`
`Host ULP Address 8
`
`
`Group Server Control
`
`
`
`
`
`
`
`
`
`Host ULP Address 0 Host TLP Address 0
`
`
`
`Implicit ULP Grow Address 0
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Host ULP Address 11
`
`
`
`
`Host ULP Address 11
`
`
`
`
`
`Logical ULP Address 0
`Logical ULP Address to
`Host ULP Address 3
`Host ULP Address a
`
`
`
`Host ULP Address n
`Host ULP Address n
`
`
`
`Figure 10
`
`Petitioner Riot Games, Inc. - EX. 1005, p. 16
`
`

`

`
`
`US. Patent
`
`Oct. 13, 1998
`
`Sheet 11 or 11
`
`5,822,523
`
`150
`
`
`
`Interactive Application
`
`
`
`Host Interface for Upper Level Protocol
`
`
`T LP Address 0
`
`
`
`
` TLP Address n
`
`
`ULP Address 0
`
`ULP Address n
`
`
`153
`
`
`
`
`154
`
`155
`
`Host Interface for Transport Level Protocol
`
`Network Communications Stack
`
`Network Interface
`
`Figure 1]
`
`Petitioner Riot Games, Inc. - Ex. 1005, p. 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 culd
`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 muliplc players on Local Area Networks (LANs)
`or by two players over dial-up phone lines using modems.
`The network mes-gee sent by such games contain a wide
`variety of information specific to the game. This can include
`position and velocity information of the objects in the game
`along with special actiom taken by a player that effect the
`other players in the game.
`The case of a two player game played over a modem is
`particularly simple. It the message rate is to manager. per
`second. each PC sends lo 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 case of two
`players is uninteresting {or networked interactive applica-
`liona. With the same game played with 8 players on a IAN,
`the message rate increases Each PCmust send 7 inc-sages.
`one to each of the other 7 players every time perixl and will
`receive 7 messages from the other players in the same time
`periad. If the messaging time period is it!) ms. the total
`message rate will be 70 messagca sent per second and 70
`messages received per second. As can be seen the message
`rate increases linearly with the hunter of players in the
`game. The message rates and data rates supported by popu-
`lar War are high enough to support a large number of
`players at reasonable message sins. Unfortunately, LANs
`are only deployed in commercial applications and cannot be
`considered for deploying a networked interactive Ipplica-
`tion to consumer taunt.
`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 ralo “3.8 KbIls/sec whidt '5 close
`to the limit set by the signal-to-nnise ratio of conventional
`phone lines. Further speed increases are ponihlc with ISDN.
`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
`clog. 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 ncl-
`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 3.8
`Khit/soc modern. Assume that
`the network used in this
`example is the Internet so that all of the network protocols
`and routing behavior '5 well defined and understood. If the
`game uses ‘I‘CP/ll’ to send its messages between the PCs in
`the game. the PPP protocol over the dial-op phone lines can
`be advantageosly uscd to compress the 'I‘CP/IP headers.
`Even so. a ryp'cal message will be approximately 25 bytes
`in size. Sent
`through the modem. this is 750 bits. The
`messages are set! 10 tint: per second to each of the other
`PCs in the game and received 10 times per second from the
`other PCs. This is 35.0 Kbits/scc which exceeds the capa-
`bilities ol the 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 panicipanu. 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 there b the latency introduced by the
`
`IO
`
`15
`
`35
`
`45
`
`55
`
`FIELD OF THE INVENTION
`
`invention relates to computer network
`The present
`syste ms, and particularly to server group messaging systems
`and methods for reducing message rate and latency.
`BACKGROUND OF THE INVENTION
`'lhere are a wide range of interactive applications imple-
`mented on computer systems today. All are characterized by
`dynamic response to the user. The user provide: input to the
`computer and the application rcsponrh quickly. One popular
`example of interactive applications on personal computers
`(PCs) are games. In this case. rapid response to the user may
`mean retkawiog the screen with a new picture in between 30
`rm and 100 ms. Interactive applicatiom such as games
`control the speed of their interaction with the user through
`an internal time base. The application uses 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 powch and common,
`it has become important to connect them together in net-
`wodcs. A network is comprised of nodes and links. The
`nodes are connected 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
`Either 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
`netwmk by sending manages and receiving messages. Gate-
`ways 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 of their network links to other nodes on their other
`network links. This processing of forwarding messages is
`called routing. In addition to sending and receiving mee-
`sagcs and their touting functions, gateways may perform
`other functions in a network. Routers are nodes that are
`connected to the network by more than one link and whose
`sole function '5 the forwarding of manages on one network
`link to the other network links to which it is connected. A
`network consisting of many network links can be thought of
`as a network of sub-networks with gateways and/0r routers
`connecting the suhmetworka together into what is called an
`internet. Way the widely known examph of a world wide
`intemet is the so called “Iuemet” whida in I995 has over 10
`million computers connected full time world-wide.
`With so many computers on a single world-wide network.
`is desirable 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 of the local user.
`receive damages from the network from the PCs oflhe other
`players and send messages out to the PC: of the other
`players. Atypical rate will be ten time per second for I time
`period of 100 ms. The messages sent between the PCs would
`contain Information that was needed to keep the game
`
`Petitioner Riot Games, Inc. - EX. 1005, p- 18
`
`

`

`
`
`5,822,523
`
`3
`time needed to send all otthe outbound packets. Each packet
`sent or received by a PC will require some amount of
`processing time. As the padret
`rate increases with the
`number ofplayers in the game, less and less of the processor
`will be available for
`running the game software itself
`latency is important it an interactive application because it
`defines the responsiveness 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 be the time from when a player acts
`to move a target to the time that the target has moved on the
`screens of the other players 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 tosend 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 outage.
`Internet Protocol Multieesting
`is a widely known
`As mentioned before,
`the Internet
`example of a wide area network The Internet is based on a
`protocol appropriately called the Internet Protocol (11’). In
`the OSI reference model for layers of network protocols. lP
`oorrespontkr to a layer 3 or Network layer protocol. It
`provides services for transmission and routing of packets
`between two nodes in an internet. The addressing model
`provides a 32 bit address [or all nodes in the network and all
`packets carry source and destination addreses I? also
`defines the routing of packets bemen network links in an
`inter—network. Gateways and router-a maintain tables that are
`used to lockup routing int'nm'ratinn based on the destination
`addresses of the packets they receive. The routing informa-
`lion tells the gatewaylrouter whether the destination of the
`packet is directly reachable on a local network link con-
`nected to the gateway/rattler 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 TCI’ and UDP. UDP providm datagram
`delivery services to applications that does not guarantee
`reliable or tit-order delivery of the daugrams. TC? '5 a
`connection oriented service to applications that does provide
`reliable delivery of a data stream. It bandits division of the
`stream 'Itto packets and ensures reliable. in-ordcr delivery.
`See the Internet Society RFCs: RFC-791 “Internet
`Protocol". RFC-793 “Transm’mion Control Protocol" and
`RFC-1180 “A 't‘Cl’flP Tutorial".
`ll’. TCP and UDP are
`unioast protocols: packets. streams or datagranrs are tram-
`mittcd from a source I) a single destination.
`As an example, consider FIGS. 1 and 2. F16. 1 shows a
`conventional unicaat network with hosts 1. 2, 3 and 4 and
`network links 11, 11 13, 14. 15,16,17, 18 and 19 amt routers
`5. 6. 7. B. 9 and 10.1n this exampb.¢lcb host wants to send
`a data payload to each of the other hosts. Host 1 has network
`address/t. host 2 has network address C. host 3 has network
`address B and host 4 has network athlress 1'). Existing
`network protocols are typically bated 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 1?. There are other components in an equal
`tP packet, but for sake of “is example, only these items will
`be considered. FIG. 2 shows the example packets that are
`sent by the hosts to one another using a conventional unicast
`network protocol such as IP. Host 1 send packcta20. 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 then packets '3 the some. Packet
`2. travels over network tirks ll, 12. 15 and 18 and through
`motors 5, 6, and 8 to reach host 3. in I similar fashion host
`3 senck packets 23 to host 1. packet 24 to host 2 and packet
`25m host-1. Host2 and host4send paekesflZT.” and
`29. 30. 31 respectively to the other three hosts. All of these
`packets are carr'ztt by the unioast network individually from
`the source host to the destination host. So in this example
`each host must send thee packets and receive three packets
`it order for each host to send its payload to the other three
`hosts.
`As can be seen, each host must send a packet to every
`other host that it wishes to communicate with in an inter-
`active application. l-‘Irther. it receives a packet from every
`other host that wishes to communicate with it. to an inter-
`active apptlattion. this will happen at a regular and high rate.
`All of the hosts that wish to communicate with one another
`will 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 messages and
`receive three message eight to ten times per second. As the
`number of hosts in the application that need to communicate
`with one another grows. the message rate will reach a rate
`that cannot be auppnrted by conventional dial-up lines. 'this
`makes unicast transport protocols umuitable for delivering
`interactive applications for multiple participants since their
`use will result in the problem of high packet rates that grow
`with the number of partic‘pants.
`Work has been done to attempt to extend the IP protocol
`to support multicasting. See RFC-1112 “Hos Extensions for
`l? Multicasthg". This document describes a set of exten-
`sions to the 1P protocol
`that enable lP mutticaating.
`tP
`mutticasting supports the transmision of a It’datagram to a
`host group by addressing the dstagram to r slngle destina-
`tion address. Mutticast addresses are a snout of the II’
`address space and identified by class Dlt’ «idiom—these
`ate ll’ addresses with “1110” in the high order 4 bits. The
`host group contains mm or more I? hosts and the 1P
`multicesting pmtowt transmits a muttieast datagram to all
`members of the group to which it is addressed. Hosts may
`join and leave groups dynamically and the routing of mut-
`ticast datagrama is supported by muttieast routers and gate-
`ways. lt is proper to describe this general approach to
`multicast trrossaging as “distributed multicast messaging". It
`is a distributed technique because the job of message deliv-
`ery and duplication is d‘atrilmted throughout the network to
`all of the multicut routers. For distributed multicast mes-
`saging to work in a wide area network, all of the routers
`handling datagrants for multicusl hosts must support the
`routing of mutticttst datagrams. Such multicast routers mtrsl
`be aware of the multicaat group membership of all of the
`hosts locally connected to the router in order to deliver
`multicast datagrams to local hosts Muttieast meters must
`also be able to forward multicast packets to routers on their
`local network links. Mutticast routers must also decide to
`which if any local routers they must forward mutticast
`datagrams. When a muhicast datagram is received. by a
`multieast router, its group addrem is compared to a list for
`each local mnlticut router of group addresses. When there
`is a match. the datagram is then forwarded to that local
`multicaat
`router. Therefore.
`the muttieast 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 millions!
`groups. Hosts do this by sending messages using lntemet
`
`m
`
`15
`
`25
`
`It]
`
`‘5
`
`SS
`
`65
`
`Petitioner Riot Games, Inc- - Ex. 1005, p- 19
`
`

`

`
`
`5,822,523
`
`5
`Group Management Protocol (IGMP) to their immediately-
`nerghhoriug multicast routers. A further attribute oi distrau-
`uted mulliaast messaging is that the routers must propagate
`the group membership information for a panicular group
`throughout the network to all of the other routers that will be
`forwarding Iramc tor that group. RFC-1112 does not
`descriae how this is to be done. Many different approaches
`have been defined for solving this problem that will he
`mentioned Inter in descriptions of related prior art. Despite
`their dilferences. all of these approaches are methoch for
`propagation of multlcttst routing information between the
`multicut routers and techniques for rotating the multicast
`datagrarm in an inter-network supporting distributed multi-
`cast messaging.
`11te distributed multieast messaging approach has a num-
`ber ot‘undeairahle side efiects. The process of propagau'on of
`group membership information to all of the relevant routers
`is not instantaneous. In a large cornplett 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 easily take many seconds and even minutes depending
`on the specifics of the algorithm that is used. RFC-1112
`mentions this prrblem and some ofthe side cfl'ccts that rural
`be handled by an implementation of a practical routing
`algorithm for multicast messaging. One problem resuhs
`when groups are dynamically created and destroyed. Since
`there is no central authority in the network for assigning
`group addresses. it iseasily postble in adistributed network
`for there to he duplication ofgroup fldm asipmenl. This
`will remit in incorrect daugram delivery. where hosts will
`receive unwanted datagrama 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 from when a group is created, 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 where Hoar N jolm an
`existing group by sending I! join manage to its ball router.
`The group already contains Host M which is a number of
`router hops away from Hoot N in the network. Shonly after
`Host N has sent it join message, Host M sends a datagram
`to the group, but the local router of Host M has not yet been
`informed of the change in group membership and as a result
`the datagram is not forwarded to one of the particular
`network linlts conncued to the local router of Host M that
`is the only path in the network from that router that ulti-
`mately will reach Host N. The result is that Host N will
`receive no dttagrama addressed to the group from Host M
`until
`the local
`router of M has in group membership
`information updated. Other related problem can also occur.
`When a host leaves a group. messages addressed to the
`gmup will mntinue for some time to be routed to that host
`up to the local router of that host. The local router will know
`at least not to route the datagram onto the local network of
`that host This an still result in a great deal of unnecessary
`datagrsms being carried in a large network when there are
`many active message groups with rapidly changing mem-
`herships.
`Finally. distributed multicast messaging dose not sulfi-
`ciently reduce the message rate between the hosts. With
`distributed multicast messaging, each host need only send
`one message addressed to the mess