`
`' 4’ mflpmyéanTIFICATE 0F MAILING BY "EXPRESS MAIL"
`‘—-."Express lvlail" Mailing Label No. 13812048578US
`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 Ollice 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, DC. 202:”
`
`Donna L. Hengst
`
`(Sigiature of Person Mailing Paper or Fee)
`
`a
`
`Attorney Docket No. 16326.70]
`
`PATENT
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`UTILITY PATENT
`APPLICATION TRANSMITTAL LETTER
`
`Box Patent Application
`~ Assistant Commissioner for Patents
`
`Washington, DC. 20231
`
`Sir:
`
`Enclosed for filing 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 enclosed are:
`[x]
`‘ L sheet(s) of [X] formal
`
`[ ] informal drawing(s);
`
`[ ]
`
`a claim for foreign priority under 35 U.S.C. §§ 119 and/or 365 in
`
`[ ] a separate document
`
`[ ] the declaration;
`
`a certified copy of the priority document;
`
`an Associate Power of Attorney;
`
`_1 verified statement claiming small entity status; and
`
`[ ]
`
`[ ]
`
`[x]
`
`[x]
`an Assignment document and form PTO-1595.
`The declaration of the inventor(s) [x] also is enclosed [ ] will follow.
`
`H:\home\hcc\mpath\70luppuansmittal
`
`(Page 1 of 2)
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 1
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 1
`
`

`

`v
`
`.
`
`we!
`
`0‘
`
`The fee has been calculated as folloWs:
`
`I
`7/ V'”
`
`O
`
`- Basic A lication Fee
`
`$750.00
`
`--—
`
`TOTAL APPLICATION FEE DUE
`
`Independent
`Claims
`
`3
`
`MINUS 3
`=
`
`$78.00=
`
`' If multi ole deoendent claims are oresented, add $250.00
`
`Total A .lication Fee
`
`If verified statement claiming small entity status is enclosed, subtract
`50% of Total A lication Fee
`
`Add Recordin_ Fee of $40.00 if Assinment document is enclosed
`
`$750.00
`
`$375.00
`
`$40.00
`
`[ ]
`
`[x]
`
`A check in the amount of $_ is enclosed.
`
`Charge $415.00 to Deposit Account No. 23-2415.
`
`The Commissioner is 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
`
`WM
`
`H.C. Chan
`
`Registration No. 35,477
`
`(Page 2 of 2)
`
`,
`650 Page Iinll Road
`Palo Alto, CA 94304-1050
`(415) 493-9300
`Date: Febru
`
`l 1996-
`
`H:\homc\hcc\mpalh\701\appmmiilnl
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 2
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 2
`
`

`

`13
`
`10
`
`Figure 1
`
`
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 3
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 3
`
`

`

`M/595323
`
`Host A Sends
`
`Host A Receives
`
`2°\-I3I31I
`
`21--Iil
`
`22 -III3I
`
`Host B Sends
`
`'23
`
`24
`
`25 Elam
`
`23
`
`26
`
`29
`
`IIHIIHilliii!«h-UN
`
`.
`
`Host B Receives
`
`2° "I3
`
`27 -I3ua
`
`3° mum
`
`Host C Sends
`
`Host C Receives
`
`26
`
`27
`
`-I3I2I
`
`28 \-Iilm
`
`21--III
`
`24 5--
`
`31 \m“
`
`Host D Sends
`
`Host 1) Receives
`
`29
`
`3°
`
`22 -Iillil
`25
`
`31 m-m
`
`23-15]!!!
`
`Figure 2
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 4
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 4
`
`

`

`08/595323
`
`36
`
`37
`
`52
`
`35
`
`46
`
`i
`
`47
`
`49
`
`\_ /
`
`50
`
`-
`
`38
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 5
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 5
`
`

`

`. .
`
`, 08/595323
`
`Host A Sends
`
`Host A Receives
`
`5“\IIIIII
`
`Host B Sends
`
`55 Iii-IE
`
`56"
`
`57b
`
`Host C Sends
`
`Host C Receives
`
`5“ "I!
`
`Host D Sends
`
`57 mum
`
`54d
`
`-I:=Im
`
`5%\1flmfllfll
`56d -nm
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 6
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 6
`
`

`

`.
`
`'
`
`.
`
`08/595323
`
`59
`
`a
`
`,
`
`60
`
`6
`
`76
`
`58
`
`'
`
`as
`
`71
`
`70
`
`74
`
`64
`
`\
`
`66
`
`73
`
`V
`
`61
`
`Figure 5
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 7
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 7
`
`

`

`7
`
`Host A Sends
`
`Host A Receives
`
`O“
`
`03/595323
`
`H H m
`
`35 \n---
`
`86 \n-
`
`8° \"fllil
`
`34 \n---
`
`Host B Sends
`
`Host B Receives
`
`81 \I'Elfl“
`
`87\n
`
`I3!
`
`II
`
`88\E
`
`I3
`
`39 \EE
`
`I.
`
`Host C Sends
`
`Host C Receives
`
`82 \"um
`
`9cm!!—
`
`91 \1!
`
`C“
`
`I3]
`
`I}:
`
`92 \n---
`
`Host D Sends
`
`Host D Receives
`
`83 \ Ian-I2]
`
`m
`
`.mm
`
`HumnnJJJmm—SAAAEccD.-muan
`
`\\\n
`
`:nmmw\
`
`\\n\E
`
`93 \fllfl
`
`-I3l
`
`94 \fllfl
`
`-I1I
`
`95 \“flm
`
`GroupServe-rReceives
`80\-
`GGn
`81 \—
`82\-
`
`83\n
`
`Figure 6
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 8
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 8
`
`

`

`.
`
`‘
`
`‘08/595323
`
`Host A Sends
`Host A Receives
`96 \-n--1°°\-----l2l
`
`Host B Receives
`.
`Host B Sends
`9" \“nm ’101\“---IEI
`
`Host C-Receives
`Host C Sends
`98 \"nm 102\fl--I3]-I2I
`
`‘
`Host D Sends
`Host D Receives
`99 \mn-m 103\m
`
`Group Server Sends
`Mnmmmm 96 \-EIEII3]
`maul-Elma! 97 \nn-m
`a /
`H E
`1°2\m \
`“’3 “MEI-IE 99 l“-
`
`Figure 7
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 9
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 9
`
`

`

`fl.%/595323
`
`
`
`Figure 8
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 10
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 10
`
`

`

`.
`
`.
`
`'
`
`13/595323
`
`123
`
`124
`
`125
`
`126
`
`127
`
`
`
`
`
`T
`
`H ad
`ranspon e er
`
`ULP Msg. Dest.ULP Address Destination
`Type
`Address
`Count Addressl
`
`________
`
`116
`
`117
`
`118
`
`119
`
`Count Address 1 Length 1
`
`
`Message Source ULP
`
`Data
`
`Data 1
`
`........
`
`Figure 9
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 11
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 11
`
`

`

`6
`
`,
`
`o
`
`”8/5953”
`
`Implicit ULP Group Address 0
`
`Application Specific
`State Storage and
`Processing
`
`Host ULP Addxess n Host TLP Address in
`
`
`
`Implicit ULP Group Address 111
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` ULP Sewer Process 0
`
`Host ULP Address at
`
`
`
`
`
`
`Logical ULP Address 0
`Host ULP Address 3
`
`Host ULP Address n
`
`
`
`Logical ULP Address m
`
`
`Host ULP Address 3
`
`
`
`
`
`
`
`
`
`Host ULP Address 11
`
`146
`
`Figure 10
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 12
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 12
`
`

`

`_M/595323
`
`Interactive Application ~-
`
`Host Interface for Upper Level Protocol
`
`
`
`153
`
`154
`
`155
`
`Figure 11
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 13
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 13
`
`

`

`%\
`
`
`-
`
`CERTIFICATE OF MAILING BY "EXPRESS MAIL"
`”Express Mail" Mailing Label No.W
`.
`minimum 1, 1996. Ihmbycertifythnt
`dispaperorfeeisbeingdepositedwdmmeUnitedStates Postal
`Serviccu'EqamMaflPostOffioctoAddrmee‘serficemder
`37 CFR 1.10011111: dateindicatedabove andisaddmssedm:
`Assistant Commissioner for Patents . Washington 110 20231
`M.a
`
`08 59. V23
`
`Attorney Docket No. 16326-701
`
`PATENT
`
`S
`
`VER—GROUP
`
`GING SYSTE
`
`FOR INTERACTIVE ARBLIQATIOES
`
`Inventors: Daniel Joseph Samuel
`Marc Peter Kwiatkowski
`
`Jefi'rey Jackiel Rothschild
`
`FIELD OF THE INVENTION
`
`The present invention relates to computer network systems, and
`
`particularly to server group messaging systems and methods for reducing
`
`message rate and latency.
`
`5
`
`Background of 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 of interactive 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.
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 14
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 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
`
`nodes and links. The nodes are connected in such a way that there exists a path
`
`fi'om 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 fiirther 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. 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 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
`
`messages and their routing fimctions, gateways may perform other filnctions 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 anvinternet. 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
`
`1‘0
`
`15
`
`20
`
`25
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 15
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 15
`
`

`

`
`
`-3-
`
`shared, networked, interactive applications runs into the limitations of the
`
`existing network technology.
`
`As an example, consider a game designed to be deployed over a network
`
`which is to be played by multiple players simultaneously. The game could be
`implemented in sofiware 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 lOOms. The messages sent between the PCs
`
`would contain information that was needed to keep the game 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 efiect the other players in the game.
`
`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
`
`introduced 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 applications. With the same game played with 8 players
`
`on a LAN, the message rate increases. Each PC must send 7 messages, one to
`
`1'0
`
`15
`
`20
`
`25
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 16
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 16
`
`

`

`'
`
`v
`
`-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 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 popular LANs are high enough to support a large number of
`
`players at reasonable message sizes. Unfortunately, LAN5 are only deployed in
`
`commercial applications and cannot be considered for deploying a networked
`
`interactive application to consumer users.
`
`The wide area networks available today to consumer users all must be
`
`accessed'through dial-up phone lines using modems. While modem speeds
`
`have increased rapidly, they have now reached a bit rate 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 necessary to do so in a way that
`
`operates with existing networking 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 ofthe network protocols and routing
`
`behavior is well defined and understood. Ifthe game 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/[P headers.
`
`15
`
`20
`
`25
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 17
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 17
`
`

`

`
`
`-5-
`
`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 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 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 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 sofiware 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.
`
`10
`
`15
`
`20
`
`25
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 18
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 18
`
`

`

`Q
`
`Q
`
`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 08] 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
`
`intemet. The addressing model provides a 32 bit address for all nodes in the
`
`network and all packets carry source and destination addresses. 1P 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/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 [P 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 TCP/IP Tutorial”. 1P, TCP and UDP are unicast protocols:
`
`packets, streams or datagrams are transmitted from a source to a single
`
`destination.
`
`As an example, consider Figures 1 and 2. Figure 1 shows a conventional
`
`unicast network with hosts 1, 2, 3 and 4 and network links 11, 12, 13, 14,
`
`10
`
`15
`
`20
`
`25
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 19
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 19
`
`

`

`6
`
`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 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 1P 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 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
`
`10
`
`15
`
`20
`
`three hosts.
`
`As can be seen, each host must send a packet to every other host that it
`
`wishes to communicate with in an interactive application. Further, it receives a
`
`packet fi'om 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
`
`25
`
`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
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 20 7
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 20
`
`

`

`-3-
`
`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.
`
`10
`
`15
`
`20
`
`25
`
`Work has been done to attempt to extend the IP protocol to support
`
`multicasting. See RFC—1 112 “Host Extensions for IP Multicasting.”. This
`
`document describes a set of extensions to the IP protocol that enable [P
`
`multicasting. IP multicasting supports the transmission of a 11’ 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 1P multicasting protocol
`
`transmits a multicast datagram to all members of the group to which it is
`
`addressed. Hosts may join and leave groups dynamically and the routing of
`
`multicast datagrams is supported by multicast routers and gateways. It is
`
`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 of the
`
`multicast routers. For distributed multicast messaging 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
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 21
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 21
`
`

`

`9
`
`-9-
`
`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 Group Management Protocol (IGMP) to their immediately-
`
`neighboring multicast routers. A fiirther attribute of distributed 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 traflic for that group. RFC-1112 does not
`
`describe how this is to be done. Many difl‘erent approaches have been defined
`for solving this problem that will be mentioned later in descriptions of related
`
`prior art. Despite their difi‘erences, all of these approaches are methods for
`
`propagation of multicast routing information between the multicast routers and
`
`techniques for routing the multicast datagrams in an inter-network supporting
`
`distributed multicast messaging.
`
`The distributed multicast messaging approach has a number of undesirable
`
`side efi‘ects. The process of propagation of group membership information to
`
`all of the relevant routers is not instantaneous. In a large complex network it
`
`can even take quite a period of time depending on the number of routers that
`
`must receive that updated group membership information and how many
`
`10
`
`15
`
`20
`
`25
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 22
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 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 the algorithm that is used. RFC-1112 mentions this problem and
`
`some of the side efi‘ects that must be handled by an implementation of a
`
`practical routing algorithm for multicast messaging. One problem results when
`
`groups are dynamically created and destroyed. Since there is no central
`
`authority in the network for assigning group addresses, it is easily possible in a
`
`distributed network for there to be duplication of group address assignment.
`
`This will result in incorrect datagram delivery, where hosts will receive
`
`unwanted datagrams from the duplicate group. This requires a method at each
`
`host to filter out the unwanted datagrams. Another set of problems result from
`
`the time delay from when a group is created, destroyed or its membership
`
`changed to when all of the routers needed to route the datagrams to the
`
`member hosts have been informed of these changes. Imagine the case where
`
`Host N joins an existing group by sending a join message to its local router.
`The group already contains Host M which is a number ofrouter hops away
`
`from Host N in the network. Shortly after Host N has sent it join message,
`
`Host M sends a datagram to the group, but the local router of Host M has 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 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
`
`occur. When a 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
`
`10
`
`15
`
`20
`
`25
`
`J
`
`l
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 23
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 23
`
`

`

`O
`
`O
`
`-11-
`
`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 many active
`
`message groups with rapidly changing memberships.
`
`5
`
`Finally, distributed multicast messaging does not sufliciently reduce the
`
`message rate between the hosts. With distributed multicast messaging, each
`
`host need only send one message addressed to the message group in order to
`
`send a message to all of other hosts in the group. This is an improvement over
`
`conventional unicast messaging where one message would need to be sent to
`
`10
`
`each of the other hosts in a group. However, distributed multicast messaging
`
`does nothing to reduce the received message rate at each of the hosts when
`
`multiple hosts in a group are sending messages to 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 messages to the other hosts, seven times per-
`
`15
`
`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
`
`20
`
`of received messages.
`
`An example of distributed multicasting is shown in Figures 3 and 4. Figure
`
`3 shows a network with multicast routers 39, 40, 41, 42, 43 and 44 and hosts
`
`35, 36, 37, 38 and network links 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 was created
`
`and each of the hosts joined the message group so that each of the multicast
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 24
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 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 manner host 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 to all 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 packet is
`
`received by multicast routers 40 and 43. Multicast router 43 sends the packet
`
`onto network link 50 and router 40 sends its 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 where it 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 process is followed for each of the other packets
`
`sent by the hosts to the multicast group E. The final packets received by each
`
`host are shown in Figure 4.
`
`While distributed multicasting does reduce the number of messages that
`
`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 membership is rapidly changing
`
`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
`
`10
`
`15
`
`20
`
`25
`
`Petitioner Riot Games, Inc. - EX. 1003, p. 25
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 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 when placed 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 where all 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 or
`
`even millions. The multicast group would exist for the duration of the
`
`audio/video program. Host members would join and leave dynamically, but in
`
`this application it would be acceptable for there to be a significant time lag
`
`from joining or leaving before the connection was established or broken.
`
`While IP and multicast extensions to [P are based on the routing of packets,
`
`another form of wide area networking technology called Asynchronous
`
`Transfer Mode (ATM) is based on switching fixed sized cells through switches.
`
`Unlike [P which supports both datagram and connection oriented services,
`
`ATM is fundamentally connection oriented. An ATM network consists of
`
`ATM switches interconnected by point-to-point links. The host systems are
`
`connected to the leaves of the network. Before any communication can occur
`
`between the hosts through the network, a virtual circuit must be setup across
`
`the network. Two forms of communication can be supported by an ATM
`
`network. Bi-directional point-to-point between two hosts and point-to-
`
`10
`
`15
`
`20
`
`25
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 26
`
`Petitioner Riot Games, Inc. - Ex. 1003, p. 26
`
`

`

`9"
`
`9
`
`-14-
`
`multipoint in one direction from one host to multiple hosts. ATM, however,
`
`does not directly support any form of multicasting. There are a number of
`
`proposals for layering multicasting on top of ATM. One approach is called a
`
`multicast server, shown in Figure 8. Host systems 112, 113, 114, 115 setup
`
`point—to—point connections 106, 107,108 and 1