¢ | .
`
`¢ FRjanetCERTIFICATE OF MAILING BY "EXPRESS MAIL"
`=f“ - "Express Mail” Mailing Label No. TB812048578US
`Date of Deposit February 1, 1996. I hereby certify that
`this paper or fee is being deposited with sufficient postage with the
`United States Postal Services "Express Mail Post Office to Addressee" service under
`37 CFR 1.10 on the date indicated above and is addressed to Box Patemt
`Application, Assistant Commissioner for Patents , Washington, D.C. 20231
`
`Donna L. Hengst
`
`(Signature ofPerson Mailing Paper or Fee)
`
`;
`
`. @
`
`16/595423
`
`PATENT
`Attorney Docket No. 16326.701
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`UTILITY PATENT
`APPLICATION TRANSMITTAL LETTER
`
`Box Patent Application
`. Assistant Commissioner for Patents
`Washington, D.C. 20231
`
`Sir:
`
`Enclosed forfiling is [x] an original patent application or,
`
`[ ] a continuation-in-part
`
`patent application, by Daniel Joseph Samuel, Marc Peter Kwiatkowski and Jeffrey Jackiel
`
`.
`
`Rothschild for
`
`SERVER-GROUP MESSAGING SYSTEM FOR INTERACTIVE APPLICATIONS.
`
`Also enclosedare:
`
`[x]
`[]
`
`[ ] informal drawing(s);
`_11__ sheet(s) of [X] formal
`a claim for foreign priority under 35 U.S.C. §§ 119 and/or 365 in
`
`[ ] a separate document[] the declaration;
`
`[]
`
`(]
`
`[x]
`
`a certified copy ofthe priority document;
`
`an Associate Power of Attorney;
`
`__1 verified statement claiming small entity status; and
`
`an Assignment document and form PTO-1595.
`[x]
`The declaration of the inventor(s) [x] also is enclosed [ ] will follow.
`
`HAhome\hcc\mpath\70l\apptransmittal
`
`(Page 1 of 2)
`
`Petitioner Valve
`Ex. 1003, Page 1
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 1
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 1
`
`Petitioner Valve
`Ex. 1003, Page 1
`
`

`

`és.
`
`The fee has been calculated as follows:
`
`pare
`NO. a
`
`-Basic Application Fee |g750.00|00
`
`CLAIM
`
`CLAIM:
`
`|_TOTAL APPLICATION FEE DUE
`
`Independent
`Claims
`
`MINUS 3
`
`$78.00=
`
`’ Ifmultipledependentclaimsare presented, addodAniamte00
`
`TotalApplicationFeesssApplication Fee $750.00
`
`If verified statement claiming small entity status is enclosed, subtract
`$375.00
`50% of Total Application Fee
`
`Add Recording Fee of $40.00 if Assignment documentis enclosed
`
`$40.00
`
`:
`
`[]
`[x]
`
`A check in the amount of $____ is enclosed.
`Charge $415.00 to Deposit Account No. 23-2415.
`
`The Commissioneris hereby authorized to charge any fees under 37 C.F.R. §§ 1.16, 1.17
`
`and 1.21 that may be required by this paper, and to credit any overpayment, to Deposit Account
`
`No. 23-2415 (Our Docket No. 16326-701). A duplicate of this paper is enclosed.
`
`Respectfully submitted,
`
`WILSON, SONSINI, GOODRICH & ROSATI
`
`py Adorn
`
`H.C. Chan
`Registration No. 35,477
`
`(Page 2 of 2)
`
`650 Page Mill Road
`Palo Alto, CA 94304-1050
`(415) 493-9300
`Date: Febru
`
`1, 1996 -
`
`H:\home\hcc\mpath\701\apptransmittal
`
`Petitioner Valve
`Ex. 1003, Page 2
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 2
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 2
`
`Petitioner Valve
`Ex. 1003, Page 2
`
`

`

`)
`
`@
`
`|
`
`:
`
`6
`
`18/59:
`
`b/995323
`
`Figure 1
`
`Petitioner Valve
`Ex. 1003, Page 3
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 3
`
`
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 3
`
`Petitioner Valve
`Ex. 1003, Page 3
`
`

`

`18/595323
`
`Host A Sends
`.
`
`Host A Receives
`
`PielPllpEIEIEfefFTOETho
`aldP|
`
`Nuhod
`
`Wwa
`
`NO\o
`
`20 LA]BI
`21
`
`22
`
`Host B Sends
`
`rR}todi3}fswo
`
`tN>
`
`Na
`
`Host C Sends
`
`26
`
`vw~l
`
`ple|PIE!
`
`283 ™ Cc
`
`Host D Sends
`
`wvOod
`
`Ww°o
`
`be _
`
`|
`
`Fa- a m —_4a
`
`_
`
`F= A ;2&
`
`8
`NmJ
`
`woS
`
`X
`
`wv>
`
`31 ™
`
`a]IN
`8 =|P|F ellon:SIE}
`
`vein
`
`NNa P|
`
`Figure 2
`
`Petitioner Valve
`Ex. 1003, Page 4
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 4
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 4
`
`Petitioner Valve
`Ex. 1003, Page 4
`
`

`

`08/995323
`
`36
`
`35
`
`C)
`40 \
`48
`C) 42
`
`37
`
`47
`
`a/
`
`50
`
`49
`
`——
`
`sh
`
`52
`
`“OS
`
`Figure 3
`
`Petitioner Valve
`Ex. 1003, Page 5
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 5
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 5
`
`Petitioner Valve
`Ex. 1003, Page 5
`
`

`

`‘
`
`, %/995323
`
`Host A Sends
`
`Host A Receives
`
`5sa~{pT[pa]
`s4~CaTeTri]
`56a|P3|
`57a TD|EFZa
`
`S4b|PA|
`55 “BT[2|
`56b
`
`Host B Sends
`
`Host B Receives
`
`57b
`
`Host C Sends
`
`HostC Receives
`
`S4o™_ aA|E Pi
`
`56 Lc LE|P3|
`S5c¢ |B|E|P2|
`
`
`57¢ lp|e|P4|
`
`Host D Sends
`
`Host D Receives
`
`
`
`std
`57 ™N_pLE|Pa|
`ssaTe[pa]
`s6d-~{_c_|E|P3|
`
`Figure 4
`
`Petitioner Valve
`Ex. 1003, Page
`
`6
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 6
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 6
`
`Petitioner Valve
`Ex. 1003, Page 6
`
`

`

`®
`
`08/395323
`
`58
`
`69
`
`64
`
`wa
`
`72
`
`S
`S 66
`
`\
`
`59
`
`60
`
`76
`
`:
`
`62
`
`ex)
`
`Figure 5
`
`Petitioner Valve
`Ex. 1003, Page 7
`
`Petitioner Riot Games, Inc. - Ex. 1003, p.7
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 7
`
`Petitioner Valve
`Ex. 1003, Page 7
`
`

`

`6
`
`8/5953293
`
`Host A Sends
`84 —~[_s[a[LH|P2|
`iieece
`8 ~[_s[a Tu|P3|
`86 ~L_s|a tH|
`
`Host A Receives
`
`Host B Receives
`Host B Sends
`Lt|
`81 ~BTs [oa [P2|
`87~Ls|B|
`88 Ls|B|
`|
`89"~Ls_|BI
`
`Host C Sends
`
`Host D Receives
`Host D Sends
`93 “™
`[DjK|
`LS|
`83 ~[p Ts[Gc|pa|
`94
`|DLK|
`LS|
`95 ~Ls|p|K|
`
`a
`
`—a4
`
`arr
`3|x!§ac-{|-II-]}411-
`
`ity
`
`||||]oea4aeE|-
`mrpry
`
`;::
`
`Figure 6
`
`Petitioner Valve
`Ex. 1003, Page 8
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 8
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 8
`
`Petitioner Valve
`Ex. 1003, Page 8
`
`

`

`@
`
`é
`
`8/995323
`
`
`
`9% TalsLa]P1] 1o0™Cs[a||p2|ps|pa|
`
`Host A Sends
`
`Host A Receives
`
`Host B Receives
`;
`Host B Sends
`97 —~TaTs[a|P2|101™Ls[pt[pitps|a|
`
`Host CReceives
`Host C Sends
`
`98% “Celts[Gc {P3] 102s[ct3[pi|p21pa|
`
`Host D Receives
`Host D Sends
`
`9° ~LpTs [a[P| 1033~(_s [bp|K-[Pi|P2|P3|
`
`Group Server Sends
`100™~(“s5TaLHLp2tp3iep4]
`11s|BLileile3[e4s]
`12~TsTclslrilpztps]
`13sTpTklerlp2[e3}]
`
`ag~ gSi
`% ~Latstic]
`“Lg:
`97 >™—_
`™
`* Loisicra)
`
`Figure 7
`
`Petitioner Valve
`Ex. 1003, Page 9
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 9
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 9
`
`Petitioner Valve
`Ex. 1003, Page 9
`
`

`

`_.8/595323
`
`
`
`Figure 8
`
`Petitioner Valve
`Ex. 1003, Page 10
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 10
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 10
`
`Petitioner Valve
`Ex. 1003, Page 10
`
`

`

`® 8 —1/595323
`
`stination
`
`Figure 9
`
`Petitioner Valve
`Ex. 1003, Page 11
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 11
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 11
`
`Petitioner Valve
`Ex. 1003, Page 11
`
`

`

`@
`
`,
`
`6
`
`08/99!
`
`(995323
`
`Implicit ULP Group Address 0||4ootication Specific
`State Storage and
`Processing
`
`Implicit ULP Group Address m
`
`ULP Server Process m
`
`Host ULP Address n
`
`Logical ULP Address 0
`Host ULP Address a
`
`Logical ULP Address m
`Host ULP Address a
`
`Figure 10
`
`Petitioner Valve
`
`
`
`
`
`Ex. 1003, Page 12 ne.-Ex. 1003, p. 12
`
`.
`ws
`Petitioner Riot Games,Inc. - Ex. 1003,
`
`p.
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 12
`
`Petitioner Valve
`Ex. 1003, Page 12
`
`

`

`18/595323
`
`Interactive Application --
`
`Host Interface for Upper Level Protocol
`
`
`
`Figure 11
`
`Petitioner Valve
`Ex. 1003, Page 13
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 13
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 13
`
`Petitioner Valve
`Ex. 1003, Page 13
`
`

`

`(ile
`
`
`.-
`
`CERTIFICATE OF MAILING BY “EXPRESS MAIL”
`"Express Mail" Mailing Label No. TB812048578US
`Date of Deposit February 1, 1996. [hereby certify that
`this paper or fee is being deposited with the United States Postal
`Services "Express Mail Post Office to Addressee" service under
`37 CFR 1.10 on the date indicated above andis addressed to:
`Assistant Commissioner for Patents , Washington, D.C. 20231
`
`B/o9: 123
`
`Benge2Menger
`
`PATENT
`Attorney Docket No. 16326-701
`
`GING SYSTE
`SERVER-GROUP
`FOR INTERACTIVE APPLICATIONS
`
`Inventors: Daniel Joseph Samuel
`Marc Peter Kwiatkowski
`Jeffrey Jackiel Rothschild
`
`FIELD OF THE INVENTION
`
`The present invention relates to computer network systems, and
`
`particularly to server group messaging systems and methodsfor reducing
`
`message rate andlatency.
`
`Backgroundof the Invention
`There are a wide range of interactive applications implemented 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 ofinteractive applications on personal
`
`10
`
`computers (PCs) are games. In this case, rapid response to the user may mean
`
`redrawing the screen with a new picture in between 30ms and 100ms.
`
`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
`
`15
`
`sound is played.
`
`Lv
`
`Petitioner Valve
`Ex. 1003, Page 14
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 14
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 14
`
`Petitioner Valve
`Ex. 1003, Page 14
`
`

`

`
`
`-2-
`
`As computers have become more powerful and common,it has become
`
`important to connect them together in networks. A network is comprised of
`
`nodesand links. The nodes are connected in such a way that there exists a path
`
`from each node overthe links and through the other nodesto each ofthe other
`nodesin the network. Each node may be connectedto the network with one
`or more links. Nodes are further categorized into hosts, gateways and routers.
`
`Hosts are computer systemsthat are connected to the network by onelink.
`
`They communicate with the other nodes on the network by sending messages
`and receiving messages. Gateways 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 oneof their network
`
`links to other nodes ontheir other network links. This processing of
`
`forwarding messagesis called routing. In addition to sending and receiving
`
`messagesandtheir 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 whosesole function is the forwarding of messages on one network
`
`link to the other network links to whichit is connected. A network consisting
`
`of many networklinks can be thought of as a network of sub-networks with
`
`gateways and/or routers connecting the sub-networks together into whatis
`called aninternet. Today the widely known example of a world wide internetis
`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
`
`10
`
`15
`
`20
`
`25
`
`9
`
`Petitioner Valve
`Ex. 1003, Page 15
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 15
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 15
`
`Petitioner Valve
`Ex. 1003, Page 15
`
`

`

`
`
`i
`
`-3-
`
`shared, networked,interactive applications runsinto the limitations of the
`
`existing network technology.
`
`As an example, consider a game designed to be deployed over a network
`
`whichis 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
`
`messagesout to the PCs of the other players. A typical rate will be ten time
`
`per second for a time period of 100ms. The messages sent between the PCs
`
`10
`
`would contain information that was needed to keep the game consistent
`
`between all of the PCs.
`
`In a gamethat createdthe illusion ofa spatial
`
`environment where each player could move, the packets could contain
`information about the new positions ofthe ‘players as they moved. Today there
`are many commercial example of PC gamesthat can be played between
`
`multiple players on Local Area Networks (LANs) or by two players overdial-
`
`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 game.
`
`The case of a two player game played over a modemis particularly simple.
`
`If the messagerate is 10 messages per second, each PC sends 10 messages per
`
`second to the other PC and receives 10 messages per second. The delay
`
`introduced by the modemsand phoneline is small and will not be noticed in
`
`most games. Unfortunately, the case of two playersis uninteresting for
`
`networked interactive applications. With the same gameplayed with 8 players
`on a LAN., the message rate increases. Each PC must send 7 messages, one to
`
`15
`
`20
`
`25
`
`4
`
`Petitioner Valve
`Ex. 1003, Page 16
`
`|
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 16
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 16
`
`Petitioner Valve
`Ex. 1003, Page 16
`
`

`

`co
`
`UU
`
`-4-
`
`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
`
`100ms,the total messagerate will be 70 messages sent per second and 70
`
`messages received per second. As can be seen the message rate increases
`
`linearly with the numberofplayers in the game. The messagerates and data
`
`rates supported by popular LANsare high enough to support a large number of
`
`players at reasonable messagesizes. Unfortunately, LANsare only deployed in
`
`commercial applications and cannot be considered for deploying a networked
`
`interactive application to consumerusers.
`
`The wide area networks available today to consumerusersall must be
`accessedthrough dial-up phonelines using modems. While modem speeds
`have increased rapidly, they have now reacheda bit rate of 28.8 Kbits/sec
`whichis closeto thelimit 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 necessary to do so in a waythat
`
`operates with existing networking and communicationsinfrastructures.
`
`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. Assumethat the network used in
`this exampleis the Internet so that all ofthe network protocols and routing
`behavioris well defined and understood. If the game uses TCP/IP to sendits
`
`15
`
`20
`
`25
`
`messages between the PCsin the game, the PPP protocol over the dial-up
`
`phonelines can be advantageously used to compress the TCP/IP headers.
`
`5
`
`Petitioner Valve
`Ex. 1003, Page 17
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 17
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 17
`
`Petitioner Valve
`Ex. 1003, Page 17
`
`

`

`
`
`5-
`
`Even so, a typical message will be approximately 25 bytes in size. Sent
`
`through the modem,this is 250 bits. The messagesare sent 10 times per
`
`second to each of the other PCsin the game and received 10 times per second
`
`from the other PCs. This is 35.0 Kbits/sec which exceeds the capabilities of the
`
`modem by 20%. If the messages are reduced to 20 bytes, just 8 players can be
`
`supported, but this approach clearly cannot support networkedinteractive
`
`applications with large numbersofparticipants. There are other problems
`beyond just the bandwidth of the network connection. There is the loading on
`
`each PCcausedby the high packet rates and there is the latency introduced by
`
`"10
`
`the time needed to sendall 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 numberof players in the game, less and less of the
`
`processorwill be available for running the gamesoftwareitself. Latency is
`importantin an interactive application because it defines the responsiveness of
`
`15
`
`the system. Whena player provides a new input on their system, it is desirable
`
`for that input to immediately affect the game onall 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. Latencyin this case will be the time from whenaplayer acts to
`
`20
`
`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 messagesto the other seven players in the game. In this
`
`example the time to send the messagesto the other 7 players will be
`
`approximately 50 ms. While the first player of the seven will receive the
`
`25
`
`message quickly, it will not be until 50 ms have passed that the last player of
`
`the seven will have received the message.
`
`\y
`
`Petitioner Valve
`Ex. 1003, Page 18
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 18
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 18
`
`Petitioner Valve
`Ex. 1003, Page 18
`
`

`

`®
`
`@
`
`-6-
`
`Internet Protocol Multicasting
`
`As mentionedbefore, 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 correspondsto a layer 3 or Network layer protocol. It provides
`
`services for transmission and routing of packets between two nodesin an
`
`internet. The addressing model provides a 32 bit addressforall nodesin 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
`
`information tells the gateway/router whether the destination of the packet is
`
`directly reachable on a local network link connected to the gateway/routerorif
`
`not, the address of another gateway/router on oneof the local network links to
`
`which the packet should be forwarded. On top of IP are the layer 4 transport
`
`protocols TCP and UDP. UDPprovides datagram delivery services to
`applications that does not guaranteereliable or in-order delivery of the
`
`datagrams. TCP is a connection oriented service to applications that does
`
`providereliable delivery of a data stream. It handles division of the stream into
`packets and ensuresreliable, in-order delivery. See the Internet Society RFCs:
`
`RFC-791 “Internet Protocol”, RFC-793 “Transmission Control Protocol” and
`
`RFC-1180 “A TCP/IP Tutorial”. IP, TCP and UDPare unicast protocols:
`
`packets, streams or datagramsare transmitted from a source to a single
`
`destination.
`
`As an example, consider Figures 1 and 2. Figure 1 showsa conventional
`
`unicast network with hosts 1, 2, 3 and 4 and network links 11, 12, 13, 14,
`
`10
`
`15
`
`20
`
`25
`
`4
`
`Petitioner Valve
`Ex. 1003, Page 19
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 19
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 19
`
`Petitioner Valve
`Ex. 1003, Page 19
`
`

`

`6
`
`é
`
`-7-
`
`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 payloadto 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 protocolsare 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 componentsin an actual IP packet, but for sake of
`
`this example, only these items will be considered. Figure 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 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 networklinks 11, 12, 15 and 18 and throughrouters 5,
`6, and 8 to reach host 3.
`Ina 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 hostthatit
`wishes to communicate with in an interactive application. Further, it receives a
`
`packet from every other host that wishes to communicate with it. In an
`
`interactive 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
`
`10
`
`15
`
`20
`
`25
`
`8
`
`Petitioner Valve
`Ex. 1003, Page 20
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 20 |
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 20
`
`Petitioner Valve
`Ex. 1003, Page 20
`
`

`

`-8-
`
`one anotheras in this example, each host will send three messages and receive
`three messageseight to ten times per second. As the numberofhosts 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 makesunicast 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 numberofparticipants.
`
`10
`
`15
`
`Work has been done to attempt to extend the IP protocol to support
`
`multicasting. See RFC-1112 “Host Extensions for IP Multicasting.”. This
`documentdescribes a set of extensions to the IP protocol that enable IP
`multicasting. IP multicasting supports the transmission of a IP datagram to a
`host group by addressing the datagram to a single destination address.
`
`- Multicast addresses are a subset of the IP address space and identified by class
`
`D IP addresses- these are IP addresses with “1110” in the high order 4 bits.
`
`The host group contains zero or more IP hosts and the IP multicasting protocol
`
`transmits a multicast datagram to all members of the group to whichitis
`
`addressed. Hosts may join and leave groups dynamically and the routing of
`
`multicast datagramsis supported by multicast routers and gateways. It is
`
`20
`
`proper to describe this general approach to multicast messaging as “distributed
`
`multicast messaging”. It is a distributed technique because the job of message
`
`_
`delivery and duplication is distributed throughout the network to all ofthe
`multicast routers. For distributed multicast messaging to work in a wide area
`
`25
`
`network,all of the routers handling datagrams for multicast hosts must support
`the routing ofmulticast datagrams. Such multicast routers must be aware of
`the multicast group membership ofall of the hosts locally connected to the
`
`Petitioner Valve
`Ex. 1003, Page 21
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 21
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 21
`
`Petitioner Valve
`Ex. 1003, Page 21
`
`

`

`S
`
`-9-
`
`router in order to deliver multicast datagramsto local hosts. Multicast routers
`
`mustalso be able to forward multicast packets to routers on their local network
`
`links. Multicast routers must also decide to whichif any local routers they
`
`must forward multicast datagrams. When a multicast datagram is received, by
`
`a multicast router, its group address is comparedtoalist for each local
`
`multicast router of group addresses. Whenthere 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 upto date list ofgroup addresses
`for which they are to forward datagrams to. Theselists are updated when
`
`hosts join or leave multicast groups. Hosts do this by sending messagesusing
`
`Internet Group ManagementProtocol (IGMP)to their immediately-
`
`neighboring multicast routers. A further attribute of distributed multicast
`
`messaging is that the routers must propagate the group membership
`
`information for a particular group throughout the networkto all of the other
`
`routers that will be forwardingtraffic for that group. RFC-1112 does not
`
`describe howthis is to be done. Many different approaches have been defined
`for solving this problem that will be mentionedlater in descriptions of related
`prior art. Despite their differences, all of these approaches are methods for
`
`10
`
`15
`
`propagation of multicast routing information between the multicast routers and
`
`20
`
`techniques for routing the multicast datagramsin an inter-network supporting
`
`distributed multicast messaging.
`
`Thedistributed multicast messaging approach has a numberof undesirable
`
`side effects. The process of propagation of group membership information to
`
`all of the relevant routers is not instantaneous. In a large complex networkit
`
`25
`
`can even take quite a period of time depending on the numberofrouters that
`
`mustreceive that updated group membership information and how many
`
`[D
`Petitioner Valve
`Ex. 1003, Page 22
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 22
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 22
`
`Petitioner Valve
`Ex. 1003, Page 22
`
`

`

`-10-
`
`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 thé algorithm that is used. RFC-1112 mentions this problem and
`
`someofthe side effects that must be handled by an implementation of a
`
`practical routing algorithm for multicast messaging. One problem results when
`
`groupsare dynamically created anddestroyed. Since there is no central
`
`authority in the network for assigning group addresses,it is easily possible in a
`
`distributed network for there to be duplication of group address assignment.
`
`This will result in incorrect datagram delivery, where hosts will receive
`
`unwanted datagramsfrom the duplicate group. This requires a method at each
`
`host to filter out the unwanted datagrams. Another set of problemsresult from
`
`the time delay from when a groupis created, destroyed or its membership
`
`changed to whenall of the routers needed to route the datagramsto the
`
`member hosts have been informed of these changes. Imagine the case where
`
`Host N joins an existing group by sending a join messageto its local router.
`The group already contains Host M whichis a numberofrouter hops away
`from Host N in the network. Shortly after Host N hassent 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 andasa result the
`
`datagram is not forwarded to one of the particular network links connected to
`
`the local router of Host M that is the only path in the network from that router
`
`that ultimately will reach Host N. The result is that Host N will receive no
`
`datagrams addressed to the group from Host M until the local router of M has
`
`its group membership information updated. Other related problems can also
`
`10
`
`15
`
`20
`
`25
`
`occur. Whena host leaves a group, messages addressed to the group will
`
`continue for some time to be routed to that host up to the local router of that
`
`||
`Petitioner Valve
`Ex. 1003, Page 23
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 23
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 23
`
`Petitioner Valve
`Ex. 1003, Page 23
`
`

`

`@
`
`e
`
`-ll-
`
`host. The local router will know at least not to route the datagram onto the
`
`local network of that host. This can still result in a great deal of unnecessary
`
`datagrams being carried in a large network when there are manyactive
`
`message groups with rapidly changing memberships.
`
`Finally, distributed multicast messaging does not sufficiently reduce the
`
`message rate between the hosts. With distributed multicast messaging, each
`host need only send one message addressed to the message groupin order to
`
`send a messageto all of other hosts in the group. This is an improvement over
`
`conventional unicast messaging where one message would needto be sent to
`each ofthe other hosts in a group. However, distributed multicast messaging
`does nothing to reduce the received messagerate at each of the hosts when
`
`multiple hosts in a group are sending messagesto the group closely spaced in
`
`time. Let us return to the example of a group of ten hosts sending messages
`
`seven times per-second to the group. With conventional unicast messaging,
`each host will need to send 9 messagesto the other hosts, seven times per-
`second and will receive 9 messages, seven times per-second. With distributed
`
`multicast messaging, each host will need to send only one message to the group
`
`containing all of the hosts seven times per-second, but will still receive 9
`
`messages, seven times per-second.It is desirable to further reduce the number
`
`10
`
`15
`
`20
`
`of received messages.
`
`An example ofdistributed multicasting is shown in Figures 3 and 4. Figure
`
`3 showsa network with multicast routers 39, 40, 41, 42, 43 and 44 and hosts
`
`35, 36, 37, 38 and networklinks 45, 46, 47, 48, 49, 50, 51, 52 and 53. The
`four hosts have unicast network addresses A, B, C, D and are also all members
`
`25
`
`of a message group with address E. In advance the message group wascreated
`
`and each ofthe hosts joined the message groupso that each of the multicast
`
`AU
`Petitioner Valve
`Ex. 1003, Page 24
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 24
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 24
`
`Petitioner Valve
`Ex. 1003, Page 24
`
`

`

`
`
`-12-
`
`routers is aware of the message group and has the proper routing information.
`
`A network protocol such IP with multicast extensions is assumed to be used in
`
`this example. Host 35 sends packet 54 with source address A and destination
`
`multicast address E to the entire message group. In the same mannerhost 37
`
`sends packet 55 to the group, host 36 sends packet 56 to the group and host 38
`
`sends packet 57 to the group. As the packets are handled by the multicast
`
`routers they are replicated as necessary in order to deliver them toall the
`
`members of the group. Let us consider how a packets sent by host 35 is
`
`ultimately delivered to the other hosts. Packet 54 is carried over network link
`
`45 to multicast router 39. The router determines from its routing tables that
`
`the multicast packet should be sent onto network links 46 and 47 and
`
`duplicates the packet and sends to both of these network links. The packetis
`
`received by multicast routers 40 and 43. Multicast router 43 sends the packet
`
`onto network link 50 and router 40 sendsits onto links 48 and 49. The packet
`
`is then received at multicast routers 44, 42 and 41. Router 41 sends the packet
`
`over network link 51 whereit is received by host 36. Router 42 sends the
`
`packet over network link 52 to host 37 and router 44 sends the packet over
`
`link 53 to host 38. A similar processis followed for each of the other packets
`
`sent by the hosts to the multicast group E. The final packets received by each
`
`10
`
`15
`
`20
`
`host are shown in Figure 4.
`
`While distributed multicasting does reduce the number of messagesthat
`
`need to be sent by the hosts in a networked interactive application, it has no
`
`effect on the number of messages.that they receive. It has the further
`
`disadvantages of poor behavior when group membershipis rapidly changing
`
`25
`
`and requires a special network infrastructure of multicast routers. It also has
`
`no support for message aggregation and cannot do so since message delivery is
`
`|?
`
`Petitioner Valve
`Ex. 1003, Page 25
`
`Petitioner Riot Games,Inc. - Ex. 1003, p. 25
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 25
`
`Petitioner Valve
`Ex. 1003, Page 25
`
`

`

`-13-
`
`distributed. Distributed multicasting also has no support for messages that
`
`define logical operations between message groups and unicast host addresses.
`
`All of these problems can be understood whenplaced in context of the
`
`design goals for distributed multicast messaging. Distributed multicast
`
`messaging was not designed for interactive applications where groups are
`
`rapidly created, changed and destroyed. Instead it was optimized for
`
`applications where the groups are created, changed and destroyed over
`
`relatively long time spans perhaps measured in many minutes or even hours.
`
`An example would be a video conference whereall the participants agreed to
`connect the conference at a particular time for a conference that might last for
`an hour. Another would be the transmission of an audio or video program
`
`from one host to many receiving hosts, perhaps measured in the thousands