`
`
`
`[19]
`United States Patent
`
`
`5,822,523
`[11] Patent Number:
`
`
`
`[45] Date of Patent: Oct. 13, 1998
`Rothschild et al.
`
`
`
`
`
`
`
`
`
`
`
`||||||||||||l||||||||||||||||||||||||l|||||||||||||||||||||||||||l|||||||||
`
`
`
`
`
`
`
`
`
`
`
`
`U5005822523A
`
`
`SERVER-GROUP MESSAGING SYSTEM FOR
`
`
`
`INTERACTIVE APPLICATIONS
`
`
`
`
`
`
`Inventors: Jeffrey J. Rothschild; Marc P.
`
`
`
`
`
`
`Kwiatkowski, both of Los Gatos;
`
`
`
`
`
`Daniel J. Samuel, Sunnyvale, all of
`
`
`
`
`
`Calif.
`
`
`
`
`Assignee: Mpath Interactive, Inc., Mountain
`
`
`
`
`View, Calif.
`
`
`
`
`
`Appl. No.: 595,323
`
`
`
`Filed:
`Feb. 1, 1996
`
`
`
`
`
`
`Int. Cl.6 ..
`........................ H04H 1/02
`
`
`
`
`US. Cl.
`.. 395/200.17; 395/2001;
`
`
`
`
`
`395/200.09
`Field of Search ............................ 395/2001, 200.01,
`
`
`
`
`
`395/20009, 200.17, 200.05, 793; 370/8513,
`
`
`
`
`60
`
`
`
`
`
`
`
`
`[54]
`
`
`[75]
`
`
`
`[73]
`
`[21]
`
`[22]
`
`[51]
`[52]
`
`[58]
`
`
`
`
`
`
`
`
`
`
`
`
`[56]
`
`
`Primary ExamineriWilliam M. Treat
`
`
`
`Assistant Examiner—Zuni Maung
`
`
`
`Attorney, Agent, or Firm—II.
`(3. Chan; Wison Sonsini
`
`
`
`
`
`
`
`Goodrich & Rosati
`
`
`
`
`
`
`
`
`
`
`
`
`[57]
`
`ABSTRACT
`
`
`
`A method for deploying interactive applications over a
`
`
`
`
`
`
`
`network containing host computers and group messaging
`
`
`
`
`
`
`servers is disclosed. The method operates in 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 to one
`
`
`
`
`
`
`
`
`
`
`
`another in time. Rather than simply forward each 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
`
`
`
`
`
`
`
`
`to reducing the latency in the communications between the
`
`
`
`
`
`
`
`
`
`hosts.
`
`
`6 Claims, 11 Drawing Sheets
`
`
`
`
`
`
`
`References Cited
`
`
`US. PATENT DOCUMENTS
`
`
`
`. 370/60
`4,470,954
`9/1984 Cotton et a1.
`
`
`
`
`
`
`
`370/943
`5,079,767
`1/1992 Perlmali
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`395/200.01
`5,150,464
`9/1992 Sidhu et a1.
`
`
`
`
`
`
`
`
`. 370/60
`5,309,433
`5/1994 Cidon et at.
`
`
`
`
`
`
`
`5,309,437
`. 370/8513
`5/1994 Perlman et al.
`
`
`
`
`
`
`
`5,329,619
`395/20001
`7/1994 Pagé et al.
`
`
`
`
`
`
`
`5,361,256
`......... 370/60
`11/1994 Docringei‘ et a1.
`
`
`
`
`
`
`
`
`
`
`5,475,819
`395/200.01
`12/1995 Miller et al.
`
`
`
`
`
`
`
`5,517,494
`370/60
`5/1996 Green
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FOREIGN PATENT DOCUMENTS
`
`
`European Pat. Off.
`.
`1/1995
`
`
`
`
`4/1995 WIPO .
`
`
`4/1995 WIPO .
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`0637142
`WO 95/10908
`
`WO 95/10911
`
`
`
`
`
`
`95 \
`
`/
`
`100
`
`
`
`
`
`HostASends
`s
`e
`
`
`
`
`
`
`
`
`
`
`Host A Receives
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Host B Sends Host B Receives
`
`101
`S
`G
`B
`P2
`s
`B
`I
`P1
`P3
`P4
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`102
`
`
`Host C Sends
`Host C Receives
`
`
`
`
`
`
`
`s G|P3J
`s|c J
`P11P2|P4|
`c
`
`
`
`
`
`
`
`
`
`
`103
`Host D Sends
`
`Host D Receives
`S
`G
`D
`P4
`S
`D
`K
`P1
`P2
`P3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`I
`97 x
`
`98
`
`
`S9
`
`
`1 DO
`
`
`
`101
`
`
`
`1
`
`103
`
`
`
`
`
`
`
`
`A
`H
`P
`5
`P4
`
`
`
`
`
`
`Group Server Sends
`
`2
`P3
`
`
`
`
`
`
`
`F1
`|
`P3
`P4
`
`
`
`
`
`
`
`
`
`
`[P1
`J
`P2
`P4
`
`
`
`K 1 P1
`P2
`P3
`
`
`
`
`
`
`
`
`
`
`
`
`1
`s
`
`
`1 3
`
`1 s
`
`
`
`G E]
`
`
`
`
`P3 1
`<3
`
`
`G 1 P41
`
`
`
`
`
`5
`s
`s
`
`E
`
`
`1 c |
`
`| D 1
`
`
`
`
` 102?}I
`13
`TL]
`J1 c
`
`
`98f D
`
`Petitioner Valve - Ex. 1001, Page 1
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 1
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 1
`
`Petitioner Valve - Ex. 1001, Page 1
`
`

`

`
`US. Patent
`
`
`
`Oct. 13, 1998
`
`
`
`
`
`Sheet 1 0f 11
`
`
`
`
`
`
`5,822,523
`
`
`
`
`
`0
`
`14
`
`
`
`w
`
`3
`
`
`
`
`
`Figure 1
`
`
`Prior Art
`
`Petitioner Valve - Ex. 1001, Page 2
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 2
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 2
`
`Petitioner Valve - Ex. 1001, Page 2
`
`

`

`
`US. Patent
`
`
`
`Oct. 13, 1998
`
`
`
`
`
`Sheet 2 of 11
`
`
`
`
`
`
`5,822,523
`
`
`
`20
`
`21
`
`22
`
`
`
`
`
`
`
`
`
`
`
`Host A Sends
`
`
`
`
`
`
`
`
`
`"I!
`
`
`
`23
`
`29
`
`
`
`Host A Receives
`
`
`
`
`
`26 an
`
`
`
`
`
`
`
`
`In-
`
`
`23
`
`
`
`
`
`
`
`
`
`20
`
`
`
`
`
`
`
`Host B Receives
`Host B Sends
`
`
`
`
`
`
`
`
`
`
`
`
`
`25 m 30 "I!
`
`
`
`
`
`
`“-3-
`“II-
`
`
`
`
`
`
`
`
`
`21
`26
`Host C Receives
`Host C Sends
`
`
`
`
`
`
`27 n 24 n
`
`
`
`
`
`
`
`
`
`
`28 "I! 31 m
`
`
`
`
`
`
`
`
`"I!
`I”
`
`
`
`
`29
`
`Host D Sends
`
`
`
`
`
`22
`
`Host D Receives
`
`
`
`
`
`
`
`
`
`
`
`30 n 25 u
`
`
`
`
`
`
`
`
`
`31 “II-
`28 II“-
`
`
`
`
`
`
`
`
`um "I!
`
`
`
`
`Figure 2
`
`Prior Art
`
`
`
`Petitioner Valve - Ex. 1001, Page 3
`
`Petitioner Riot Games, Inc. — EX. 1001, p. 3
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 3
`
`Petitioner Valve - Ex. 1001, Page 3
`
`

`

`
`US. Patent
`
`
`
`Oct. 13, 1998
`
`
`
`
`
`Sheet 3 0f11
`
`
`
`
`
`
`5,822,523
`
`
`
`35
`
`
`
`:e
`
`
`
`@
`
`51
`
`
`
`@38
`
`
`
`Figure 3
`
`
`Prior Art
`
`Petitioner Valve - Ex. 1001, Page 4
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 4
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 4
`
`Petitioner Valve - Ex. 1001, Page 4
`
`

`

`
`U.S. Patent
`
`
`
`Oct. 13, 1998
`
`
`
`
`
`Sheet 4 of 11
`
`
`
`
`
`
`5,822,523
`
`
`
`
`
`
`
`
`
`Host A Sends
`
`
`
`
`55a
`
`57,
`
`
`
`
`
`Host A Receives
`
`
`
`
`,6, a“
`
`
`
`
`
`
`
`
`
`
`
`I"
`
`54
`
`55
`
`
`
`
`
`Host 8 Sends
`54b
`
`
`
`
`m 56b
`
`57b
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Host B Receives
`
`
`
`
`
`
`
`um
`
`56
`
`
`
`
`
`
`
`Host C Sends
`
`
`
`
`
`
`
`54C
`
`55,
`
`
`
`
`
`Host C Receives
`
`
`
`
`
`
`
`
`570 I“
`
`
`
`
`I“-
`
`57
`
`Host D Sends
`
`
`
`
`
`54d
`
`Host D Receives
`
`
`
`
`
`
`
`
`
`
`
`“-- 5,,
`
`
`
`
`sad I"
`
`
`
`
`
`
`
`
`
`
`
`
`Figure 4
`
`
`Prior Art
`
`Petitioner Valve - Ex. 1001, Page 5
`
`Petitioner Riot Games, Inc. — EX. 1001, p. 5
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 5
`
`Petitioner Valve - Ex. 1001, Page 5
`
`

`

`
`US. Patent
`
`
`
`Oct. 13, 1998
`
`
`
`
`
`Sheet 5 0f 11
`
`
`
`
`
`
`5,822,523
`
`
`
`58
`
`ea.
`
`69
`
`71
`
`67
`
`
`
`@
`
`75
`
`63
`
`64
`
`72
`
`7O
`
`74
`
`68 .
`
`76
`
`. 77
`
`61
`
`62
`
`m
`
`
`Figure 5
`
`
`
`Petitioner Valve - Ex. 1001, Page 6
`
`Petitioner Riot Games, Inc. — EX. 1001, p. 6
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 6
`
`Petitioner Valve - Ex. 1001, Page 6
`
`

`

`
`US. Patent
`
`
`
`Oct. 13, 1998
`
`
`
`
`
`Sheet 6 0f 11
`
`
`
`
`
`
`5,822,523
`
`
`
`I II
`
`Host A Receives
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Host A Sends
`
`
`
`
`
`
`
`84
`
`95
`
`99
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Host B Receives
`Host B Sends
`87
`
`
`
`
`
`
`
`
`
`
`
`I“- 99 -“II
`
`
`
`
`
`
`99 -I"—
`
`
`
`
`-I"ll
`
`
`
`Host C Sends
`
`
`
`
`
`
`
`
`
`
`
`
`90
`
`91
`
`92
`
`93
`
`
`
`
`
`
`
`
`Host C Receives
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Host D Receives
`Host D Sends
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`n--- 94 mm:
`
`
`
`
`
`95 -Im
`
`
`
`
`--:--
`
`
`80
`Group Server Receives
`91
`
`
`
`
`
`
`
`
`
`
`
`
`IIII IIIIIII
`IIIII
`
`80
`
`81
`
`82
`
`83
`
`84
`
`95
`
`99
`
`97
`
`91
`
`92
`
`99
`
`
`
`Group Server Sends
`
`
`
`
`
`
`
`
`
`
`99 -I“II
`
`
`
`99 -I“—
`
`
`
`99 -“II
`
`
`
`
`
`
`
`
`94 ml!
`
`
`
`
`
`
`95 m“
`
`--“
`
`
`
`
`I III
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`92 I“-
`
`
`
`
`
`99
`
`
`
`
`
`
`
`
`
`Im-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figure 6
`
`
`
`Petitioner Valve - Ex. 1001, Page 7
`
`Petitioner Riot Games, Inc. — EX. 1001, p. 7
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 7
`
`Petitioner Valve - Ex. 1001, Page 7
`
`

`

`US. Patent
`
`Oct. 13, 1998
`
`Sheet 7 of 11
`
`5,822,523
`
`96
`
`97
`
`98
`
`99
`
`100
`
`
` Host A Sends
`
`
`
`
`
`
`Host 8 Sends
`
`
`Host C Sends
`
`
`
`100
`
`101
`
`102
`
`103
`
`
`
` -----III
`
`Host A Receives
`
`
`Host B Receives
`
`
`
`Host C Receives
`
`
`
`Host D Sends
`Host D Receives
`
`"m
`
`96
`
`Group Server Sends
`
`,0,_P2
`-fl—1
`“mm
`“’2 "m 98
`
`9,
`
`Group Server Receives
`
`I"-
`
`nun:
`
`103 /
`
`99
`
`Figure 7
`
`Petitioner Valve - Ex. 1001, Page 8
`Petitioner Riot Games, Inc. - Ex. 1001, p. 8
`
`Petitioner Valve - Ex. 1001, Page 8
`
`

`

`US. Patent
`
`0a. 13, 1998
`
`Sheet 8 0f 11
`
`5,822,523
`
`
`
`Figure 8
`Prior Art
`
`Petitioner Valve - Ex. 1001, Page 9
`Petitioner Riot Games, Inc. - Ex. 1001, p. 9
`
`Petitioner Valve - Ex. 1001, Page 9
`
`

`

`US. Patent
`
`0m. 13. 1998
`
`Sheet 9 of 11
`
`5,822,523
`
`123
`
`124
`
`125
`
`126
`
`127
`
`128
`
`129
`
`
`
`Destination Pa I
`Transport ULP Msg. DesL ULP Address Destination
`Header
`Type
`Address
`Count
`Address 1 """ Address N
`V °a
`
`
`
`d
`
`116
`
`117
`J
`
`118
`
`119
`
`120
`
`121
`
`122
`
`
`
`Message Source ULP
`Count
`Address 1
`
`Data
`Length 1
`
`Data 1
`
`
`
`Source ULP
`""" Address N
`
`Length N
`
`Data
`
`
`
`
`
`131130 132
`
`
`
`
`
`Figure 9
`
`Petitioner Valve - Ex. 1001, Page 10
`Petitioner Riot Games, Inc. - BX. 100], p. 10
`
`Petitioner Valve - Ex. 1001, Page 10
`
`

`

`
`U.S. Patent
`
`
`
`Oct. 13, 1998
`
`
`
`
`
`Sheet 10 of 11
`
`
`
`
`
`5,822,523
`
`
`
`
`
`1 35
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Implicit ULP Group Address m
`
`
`
`
`
`
`
`
`Network Interface
`
`
`
`
`
`
`
`
`
`
`Group Sewer Control
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Host ULP Address 0 Host TLP Address 0
`
`
`
`
`
`
`
`
`
`
`
`
`Implicit ULP Group Address 0
`
`Application
`
`
`
`Specific State
`
`
`
`
`
`
`
`
`
`Storage and
`
`
`Host ULP Address n Host TLP Address n
`
`Processing
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ULP Server Process m
`
`
`
`
`
`
`
`
`Host ULP Address 3
`
`
`
`
`
`
`
`
`
`
`
`
`
`Host ULP Address n
`
`
`
`
`ULP Server Process 0
`
`
`
`
`
`
`Host ULP Address a
`
`
`
`
`
`
`
`
`
`
`
`
`Host ULP Address n
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Host ULP Address a
`
`
`
`
`
`Logical ULP Address 0
`
`
`
`
`
`
`
`
`
`
`Host ULP Address n
`
`
`
`
`
`
`
`
`
`
`
`Logical ULP Address m
`Host ULP Address a
`
`
`
`
`
`
`Host ULP Address n
`
`
`
`
`
`
`
`Figure 10
`
`
`
`Petitioner Valve - Ex. 1001, Page 11
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 11
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 11
`
`Petitioner Valve - Ex. 1001, Page 11
`
`

`

`
`U.S. Patent
`
`
`
`Oct. 13, 1998
`
`
`
`
`
`Sheet 11 0f 11
`
`
`
`
`
`
`5,822,523
`
`
`
`
`
`
`
`
`
`
`
`
`
`Host Interface for Upper Level Protocol
`
`
`
`
`
`
`
`
`
`
`ULP Address n
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`150
`
`
`
`
`Interactive Application
`
`
`
`
`
`
`
`
`152
`
`
`
`ULP Address 0
`
`
`
`
`TLP Address 0
`
`
`
`
`
`TLP Address n
`
`
`
`
`
`
`
`
`
`
`Host Interface for Transport Level Protocol
`
`
`
`Network Communications Stack
`
`
`
`
`
`Network Interface
`
`
`
`
`153
`
`154
`
`155
`
`
`Figure 1 1
`
`
`
`Petitioner Valve - Ex. 1001, Page 12
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 12
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 12
`
`Petitioner Valve - Ex. 1001, Page 12
`
`

`

`1
`
`SERVER-GROUP MESSAGING SYSTEM FOR
`
`
`
`INTERACTIVE APPLICATIONS
`
`
`
`
`
`
`
`
`
`
`
`FIELD OF TIIE INVENTION
`
`
`
`
`invention relates to computer network
`The present
`
`
`
`
`
`
`systems, and particularly to server group messaging systems
`
`
`
`
`
`
`
`and methods for reducing message rate and latency.
`
`
`
`
`
`
`
`
`BACKGROUND OF THE INVENTION
`
`
`
`
`There are a wide range of interactive applications irnple—
`
`
`
`
`
`
`
`
`mented on computer systems today. All are characterized by
`
`
`
`
`
`
`
`
`
`dynamic response to the user. The user provides input to the
`
`
`
`
`
`
`
`
`
`
`
`computer and the application responds quickly. One popular
`
`
`
`
`
`
`
`
`example of interactive applications on personal computers
`
`
`
`
`
`
`
`(PCs) are games. In this case, rapid response to the user may
`
`
`
`
`
`
`
`
`
`
`
`
`mean redrawing 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 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 powerful and common,
`
`
`
`
`
`
`
`it has become important to connect them together in net-
`
`
`
`
`
`
`
`
`
`works. A network is comprised of nodes and links. The
`
`
`
`
`
`
`
`
`
`
`nodes are connected in such a way that there 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
`
`
`
`
`
`
`
`
`
`
`
`
`
`connected to the network with one or more links. Nodes are
`
`
`
`
`
`
`
`
`
`
`
`further categorized into hosts, gateways and routers. Hosts
`
`
`
`
`
`
`
`
`are computer systems that are connected to the network by
`
`
`
`
`
`
`
`
`
`
`one link. They communicate with the other nodes on the
`
`
`
`
`
`
`
`
`
`
`network by sending messages 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 mes-
`
`
`
`
`
`
`
`
`sages and their routing 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 is the forwarding of messages 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/or routers
`
`
`
`
`
`
`
`
`
`connecting the sub—networks together into what is called an
`
`
`
`
`
`
`
`
`
`internet. Today the widely known example of a world wide
`
`
`
`
`
`
`
`
`
`internet is the so called “Internet” which in 1995 has over 10
`
`
`
`
`
`
`
`
`
`
`
`
`million computers connected full time world-wide.
`
`
`
`
`
`
`With so many computers on a single world —wide network,
`
`
`
`
`
`
`
`it is desirable to create interactive networked applications
`
`
`
`
`
`
`
`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 garlic designed to be deployed
`
`
`
`
`
`
`
`
`
`
`over a network which is to be played by multiple players
`
`
`
`
`
`
`
`
`
`
`
`simultaneously. The game could be implemented in software
`
`
`
`
`
`
`
`
`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 messages from the network from the PCs of the other
`
`
`
`
`
`
`
`
`
`
`
`players and send messages out
`to the PCs of the other
`
`
`
`
`
`
`
`
`
`
`
`players. A typical rate will be ten time per second for a time
`
`
`
`
`
`
`
`
`
`
`
`
`
`period of 100 ms. The messages sent between the PCs would
`
`
`
`
`
`
`
`
`
`
`
`contain information that was needed to keep the game
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`10
`
`
`
`15
`
`
`
`
`
`
`
`30
`
`
`
`35
`
`
`
`4O
`
`
`
`45
`
`
`50
`
`55
`
`
`
`
`
`60
`
`
`
`65
`
`
`5,822,523
`
`
`
`
`
`
`
`2
`
`consistent between all of the 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
`
`
`
`
`
`
`
`
`
`positions of the players as they moved. Today there are many
`
`
`
`
`
`
`
`
`
`
`
`commercial example of PC games that can be played
`
`
`
`
`
`
`
`
`
`between multiple players on Local Area Networks (LANs)
`
`
`
`
`
`
`
`
`or by two players over dial—up phone lines using modems.
`
`
`
`
`
`
`
`
`
`
`The network messages 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 actions taken by a player that effect the
`
`
`
`
`
`
`
`
`
`
`
`other players in the garlic.
`
`
`
`
`
`The case 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
`
`
`
`
`
`
`
`
`
`
`
`
`be noticed in most games. Unfortunately, the case of two
`
`
`
`
`
`
`
`
`
`
`players is uninteresting for networked interactive applica—
`
`
`
`
`
`
`tions. With the same game played with 8 players on a LAN,
`
`
`
`
`
`
`
`
`
`
`
`
`the message rate increases. Each PC must send 7 messages,
`
`
`
`
`
`
`
`
`
`
`one to each of the other 7 players every time period and will
`
`
`
`
`
`
`
`
`
`
`
`
`
`receive 7 messages from the other players in the same time
`
`
`
`
`
`
`
`
`
`
`
`period. If the messaging time period is 100 ms, the total
`
`
`
`
`
`
`
`
`
`
`
`message rate will be 70 messages sent per second and 70
`
`
`
`
`
`
`
`
`
`
`
`messages received per second. As can be seen the message
`
`
`
`
`
`
`
`
`
`
`rate increases linearly with the number of players in the
`
`
`
`
`
`
`
`
`
`
`game. The message rates and data rates supported by popu—
`
`
`
`
`
`
`
`
`
`lar LANs are high enough to support a large number of
`
`
`
`
`
`
`
`
`
`
`
`players at reasonable message sizes. Unfortunately, LANs
`
`
`
`
`
`
`
`are only deployed in commercial applications and cannot be
`
`
`
`
`
`
`
`
`
`considered for deploying a networked interactive applica-
`
`
`
`
`
`
`tion to consumer users.
`
`
`
`
`The wide area networks available today to consumer users
`
`
`
`
`
`
`
`
`
`all must be accessed through dial—up phone lines using
`
`
`
`
`
`
`
`
`
`modems. While modern speeds have increased rapidly, they
`
`
`
`
`
`
`
`
`have now reached a bit rate of 28.8 Kbits/sec which is close
`
`
`
`
`
`
`
`
`
`
`
`to the limit set by the signal-to-noise ratio of conventional
`
`
`
`
`
`
`
`
`
`
`phone lines. Further speed increases are possible 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
`
`
`
`
`
`
`
`
`
`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 net—
`
`
`
`
`
`
`
`
`
`
`
`working and communications infrastructures.
`
`
`
`
`In the example of the 8 player networked game, consider
`
`
`
`
`
`
`
`
`
`
`a wide area network implementation where the PCs of each
`
`
`
`
`
`
`
`
`
`
`of the players is connected to the network with a 28.8
`
`
`
`
`
`
`
`
`
`
`
`Kbit/sec modem. 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
`
`
`
`
`
`
`
`
`
`
`garlic uses TCP/IP to send its messages between the PCs in
`
`
`
`
`
`
`
`
`
`
`
`the game, the PPP protocol over the dial—up phone lines can
`
`
`
`
`
`
`
`
`
`
`
`be advantageously used to compress the TCP/IP headers.
`
`
`
`
`
`
`
`
`Even so, a typical message will be approximately 25 bytes
`
`
`
`
`
`
`
`
`
`
`in size. Sent
`through the modem,
`this is 250 bits. The
`
`
`
`
`
`
`
`
`
`
`
`messages are sent 10 times 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/sec which exceeds the capa-
`
`
`
`
`
`
`
`
`
`bilities of the modem by 20%. If the messages are reduced
`
`
`
`
`
`
`
`
`
`
`
`this
`to 20 bytes, just 8 players can be supported, but
`
`
`
`
`
`
`
`
`
`
`
`approach clearly cannot support networked interactive
`
`
`
`
`
`
`applications with large numbers of participants. 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 is the latency introduced by the
`
`
`
`
`
`
`
`
`
`
`
`
`Petitioner Valve - Ex. 1001, Page 13
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 13
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 13
`
`Petitioner Valve - Ex. 1001, Page 13
`
`

`

`
`
`5,822,523
`
`3
`
`time needed to send all of the outbound packets. Each packet
`
`
`
`
`
`
`
`
`
`
`
`sent or received by a PC will require some amount of
`
`
`
`
`
`
`
`
`
`
`
`processing time. As the packet
`rate increases with the
`
`
`
`
`
`
`
`
`
`number of players in the game, less and less of the processor
`
`
`
`
`
`
`
`
`
`
`
`
`will be available for running the game software itself
`
`
`
`
`
`
`
`
`
`Latency is important in an interactive application because it
`
`
`
`
`
`
`
`
`
`defines the responsiveness of the system. When a player
`
`
`
`
`
`
`
`
`
`provides a new input on their system, it is desirable for 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 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 message.
`
`
`
`Internet Protocol Multicasting
`
`
`
`As mentioned before,
`the Internet is a widely known
`
`
`
`
`
`
`
`
`
`example of a wide area network. The Internet is based on a
`
`
`
`
`
`
`
`
`
`
`
`protocol appropriately called the Internet Protocol (IP). In
`
`
`
`
`
`
`
`
`the OSI reference model for layers of network protocols, IP
`
`
`
`
`
`
`
`
`
`
`corresponds 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 for all nodes in the network and all
`
`
`
`
`
`
`
`
`
`
`
`
`packets carry source and destination addresses.
`IP also
`
`
`
`
`
`
`
`
`defines the routing of packets between network links in an
`
`
`
`
`
`
`
`
`
`
`inter-network. Gateways and routers maintain tables that are
`
`
`
`
`
`
`
`
`used to lookup routing information based on the destination
`
`
`
`
`
`
`
`
`
`addresses of the packets they receive. The routing informa-
`
`
`
`
`
`
`
`
`tion tells the gateway/router whether the destination of the
`
`
`
`
`
`
`
`
`packet is directly reachable on a local network link con—
`
`
`
`
`
`
`
`
`
`nected to the gateway/router or if not, the address of another
`
`
`
`
`
`
`
`
`
`
`
`
`gateway/router on one of the local network links to which
`
`
`
`
`
`
`
`
`
`
`the packet should be forwarded. On top of IP are the layer
`
`
`
`
`
`
`
`
`
`
`
`
`4 transport protocols TCP and UDP. UDP provides datagram
`
`
`
`
`
`
`
`
`
`delivery services to applications that does not guarantee
`
`
`
`
`
`
`
`
`reliable or in-order delivery of the datagrams. TCP is a
`
`
`
`
`
`
`
`
`
`
`connection oriented service to applications that does provide
`
`
`
`
`
`
`
`
`reliable delivery of a data stream. It handles division of the
`
`
`
`
`
`
`
`
`
`
`stream into packets and ensures reliable, in—order delivery.
`
`
`
`
`
`
`
`
`See the Internet Society RFCs: RFC—791 “Internet
`
`
`
`
`
`
`
`Protocol”, RFC—793 “Transmission Control Protocol” and
`
`
`
`
`
`
`RFC-1180 “A 'l‘Cl’/ll’ Tutorial".
`11’, TCP and UDP are
`
`
`
`
`
`
`
`
`
`unicast protocols: packets, streams or datagrams are trans-
`
`
`
`
`
`
`
`mitted from a source to 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,16,17, 18 and 19 and routers
`
`
`
`
`
`
`
`
`
`
`
`
`5, 6, 7, 8, 9 and 10. In this example, each host wants to send
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a data payload to each of the other hosts. Host 1 has network
`
`
`
`
`
`
`
`
`
`
`
`
`
`address A, host 2 has network address C, host 3 has network
`
`
`
`
`
`
`
`
`
`
`address B and host 4 has network address 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 IP. There are other components in an actual
`
`
`
`
`
`
`
`
`
`
`
`IP packet, but for sake of this 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 packets 20, to host
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5
`
`
`
`10
`
`
`
`15
`
`
`
`
`
`
`
`30
`
`
`
`35
`
`4O
`
`
`
`
`
`45
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`
`
`
`
`
`
`4
`
`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,
`
`
`
`
`
`
`
`
`
`
`
`
`
`therefore the payload in all three packets is 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 a similar fashion host
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`3 sends packets 23 to host 1, packet 24 to host 2 and packet
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`25 to host 4. Host 2 and host 4 send packets 26, 27, 28 and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`29, 30, 31 respectively to the other three hosts. All of these
`
`
`
`
`
`
`
`
`
`
`
`
`packets are carried by the unicast network individually from
`
`
`
`
`
`
`
`
`
`the source host to the destination host. So in this example
`
`
`
`
`
`
`
`
`
`
`
`each host must send three 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 a packet to every
`
`
`
`
`
`
`
`
`
`
`
`other host that it wishes to communicate with in an inter-
`
`
`
`
`
`
`
`
`
`
`active application. Further, it receives a packet from every
`
`
`
`
`
`
`
`
`other host that wishes to communicate with it. In an inter—
`
`
`
`
`
`
`
`
`
`
`active application, 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 four hosts communicating with one another as
`
`
`
`
`
`
`
`
`
`in this example, each host will send three messages and
`
`
`
`
`
`
`
`
`
`
`receive three messages 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 supported by conventional dial-up lines. This
`
`
`
`
`
`
`
`
`
`makes unicast transport protocols unsuitable 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 participants.
`
`
`
`
`
`Work has been done to attempt to extend the IP protocol
`
`
`
`
`
`
`
`
`
`
`
`to support multicasting. See RFC—1112 “Host Extensions for
`
`
`
`
`
`
`
`
`IP Multicasting”. This document describes a set of exteri—
`
`
`
`
`
`
`
`
`sions to the IP protocol
`that enable IP multicasting. IP
`
`
`
`
`
`
`
`
`
`multicasting supports the transmission of a ll’ datagram to a
`
`
`
`
`
`
`
`
`host group by addressing the datagram to a single destina-
`
`
`
`
`
`
`
`
`
`tion address. Multicast addresses are a subset of the IP
`
`
`
`
`
`
`
`
`
`
`address space and identified by class DIP addressesithese
`
`
`
`
`
`
`
`
`are IP addresses with “1110” in the high order 4 bits. The
`
`
`
`
`
`
`
`
`
`
`
`
`host group contains zero or more 11’ hosts and the 11’
`
`
`
`
`
`
`
`
`
`
`
`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 datagrams is supported by multicast routers and gate-
`
`
`
`
`
`
`
`
`ways.
`is proper to describe this general approach to
`lt
`
`
`
`
`
`
`
`
`
`
`multicast messaging 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 multicast routers. For distributed multicast mes—
`
`
`
`
`
`
`
`
`saging to work in a wide area network, all of the routers
`
`
`
`
`
`
`
`
`
`
`
`
`handling datagrams for multicast hosts must support the
`
`
`
`
`
`
`
`
`routing of multicast datagrams. Such multicast routers must
`
`
`
`
`
`
`
`
`be aware of the multicast group membership of all of the
`
`
`
`
`
`
`
`
`
`
`
`hosts locally connected to the router in order to deliver
`
`
`
`
`
`
`
`
`
`
`multicast datagrams to local hosts. Multicast routers must
`
`
`
`
`
`
`
`
`also be able to forward multicast packets to routers on their
`
`
`
`
`
`
`
`
`
`
`
`local network links. Multicast routers must also decide to
`
`
`
`
`
`
`
`
`
`which if any local routers they must forward multicast
`
`
`
`
`
`
`
`
`
`datagrams. When a multicast datagram is received, by a
`
`
`
`
`
`
`
`
`
`multicast router, its group address is compared to a list for
`
`
`
`
`
`
`
`
`
`
`
`each local multicast router of group addresses. When there
`
`
`
`
`
`
`
`
`
`is a match, the datagram is then forwarded to that local
`
`
`
`
`
`
`
`
`
`
`
`multicast router. Therefore,
`the multicast 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 multicast
`
`
`
`
`
`
`
`
`
`
`groups. Hosts do this by sending messages using Internet
`
`
`
`
`
`
`
`
`
`
`Petitioner Valve - Ex. 1001, Page 14
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 14
`
`Petitioner Riot Games, Inc. - Ex. 1001, p. 14
`
`Petitioner Valve - Ex. 1001, Page 14
`
`

`

`
`
`5,822,523
`
`5
`
`Group Management Protocol (IGMP) to their immediately—
`
`
`
`
`
`
`neighboring multicast routers. A further attribute of distrib—
`
`
`
`
`
`
`
`uted multicast 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 traffic for
`that group. RFC—l l l 2 does not
`
`
`
`
`
`
`
`
`describ