UNITED STATES PATENT AND TRADEMARK OFFICE
`DOCUMENT CLASSIFICATION BARCODE SHEET
`
`
`
`
` WWW
`
`
`DOC]
`
`CATEGORY:
`
`CLEARED
`
`
`
`ADDRESS
`
`CONTACT IF FOUND:
`
`Petitioner Valve
`EX. 1004’ Page 1
`
`Petitioner Riot Games, Inc. - EX. 1004, p. 1
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 1
`
`Petitioner Valve
`Ex. 1004, Page 1
`
`

`

`iiiiiiiiiiiiiiiililiiiiiii
`
`Please type a sign(+) inside this box
`
`'9 E
`
`PTO/SB/OS (2/98)
`l
`Approved for use through 09/30/2000. 0MB 0651-0032
`Patent and Trademark Office: US. DEPARTMENT OF COMMERCE
`
`
`Under the Pa erwork Reduction Act of 1995, no .crsons are reuired to res 0nd to a collection of information unless it dis sla is a valid OMB control ntunber.
`
`
`Attorney Docket No.
`I 71 9. 0050002
`
`
`
`First Inventor or
`Jeffrey J. ROTHSCHILD
`
`
`
`UTILITY PATENT APPLICATION TRANSMITTAL
`
`Application Identifier
`
`Server-Group Messaging Systemfor Interactive
`(Onlyfor new nonprovtslonal applicationi under 37 CFR § 1.53(b))
`Applications
`
`O
`
`
`
`ester/6i
`
` 0
`
`1. [I
`
`* Fee Transmittal Form (e.g., PTO/SB/17)
`(Submit an original, and a duplicatefarfL’L’ processing)
`
`2.
`
`60
`
`]
`
`6. E] Microfiche Computer Program (Appendix)
`
`7. Nucleotide and/or Amino Acid Sequence Submission (if
`applicable. a” necessary)
`
`3- E]
`
`]
`
`8.
`
`[:1 Assignment Papers (cover sheet & document(s))
`
`E] Power of Attorney
`
`
`
`_.-
`
`Express Mail Label No- _i?'.:
`
`
`Assistant Commissioner for Patents
`In
`
`
`APPLICATION ELEMENTS
`
`ADDRESS TO'
`E
`Box Patent Application
`
`See WEI’ chapter 600 concerning utility patent application contents
`\D
`Washington, DC 20231
`
`
`
`
`
`
`
`[Total Pages
`Specification
`(preflrred arrangement ,satjarili below)
`» Descriptive title of the Invention
`
`
`
`
`comPUtCr Readable Copy
`- Cross References to Relamd Applications
`. Background of the Invention
`
`
`_
`,
`- Brief Summary ofthe Invention
`
`
`13- D Paper Copy (Identlcal to computer copy)
`- BriefDescription ofthe Drawings (iffiled)
`
`
`- Detailed Description
`
`
`.
`.
`.
`.
`.
`- Cl
`
`
`
`c. D Statement verifylng identity of above copies
`_ A5532 ofthc Disclosure
`
` ACCONIPANYING APPLICATION PARTS
`
`3, E Drawings (35 U.S.C. 113)
`[Total Sheets
`1
`
`
`4. [I
`Oath or Declaration
`[Total Pages
`]
`
`
`9. E] 37 CFR 3,73(b) Statement
`(when there is an assignce)
`
`
`a. I] Newly executed (original or copy)
`
`
`
`10.
`1:] English Translation Document (ifapplicable)
`
`
`
`
`
`
`DELETION OF INVENTORg SQ
`
`
`
`Signed statement attached deleting inventor(s)
`named in the prior application, see 37 CFR §§
`
`
`1.63(d)(2) and 1.33(b).
`
`
`
`
`
`5. [j
`Incorporation By Reference (uieuble ifln‘ox 41m checked)
`14- El #1533332??? Statemenfls)
`D :taiflnteinilfils‘estiln :2:
`e
`
`
`
`The entire disclosure ofthe prior application, from which a copy of the oath
`(
`'
`-
`J
`ail; 5:51;(i
`s
`prop r
`
`or declaration is supplied under Box 4b, is considered as being part of the
`
`disclosure of the accompanying application and is hereby incorporated by
`15 E] Certified Copy of Priority Document(s)
`
`reference therein.
`
`
`(iffareign priority is claimed)
`
`16.
`Other:
`37 C.F.R. § l.l36(a)(3) Authorization
`D Other"
`
`
`*NOTE FOR ITEMS 1 a 14 IN ORDER TO Eli ENII'IIED T0 PAYSll/MLL ENTITY FEES. A
`Sll/IALL [mm P 3777Ell/ILWI'IS REQUIRED (37 CFR 33 l 27), EXCEI’TIF ONE FILED INA
`
`PRIOR APPLICATIONIS RELIED UPON (37 CFR §1 28)
`
`
`17.
`If a CONTINUING APPLICATION, check appropriate box, and supply the requisite irifimnalion below and in a preliminary amendment
`
`
`
`b. E] Copy from a prior application (37 CFR 1.63(d)) 0hr
`continuation/di‘vistonal with Box I 7 completed)
`[Note Box 5 below]
`
`i.
`
`E]
`
`ll. E]
`
`Information Disclosure
`Statement (IDS)/PTO-l 449
`
`D Copies of IDS Citations
`
`12. {j PreliminaryAmendmem
`13.
`Return Receipt Postcard (MPEP 503)
`(Should be specifically itemized)
`
`
`Continuation
`El Divisional
`DContinuation-in-Part (CI?) of prior application No: 08/896,797
`
`
`
`Prior application information: Examiner Zarni iMaung
`Group/Art Unit: 2758
`I8. CORRESPONDENCE ADDRESS
`
`
`
`
`
`
`
`_—
`
`
` il(/1>
`
`[:I Customer Number
`vrBarCodeLabel
`
`NAME
`
`............ denigratemetflq:grenadine.midfielders).............
`
`or E Correspondence
`address below
`
`Washington ——_ 20005-3934
`(202)371-2540
`
`
`
`
`
`
`
`_I'[M-’l’/Il_”III-—
`
`Burden Hour Statement
`this form is estimated /takc 0.2 hours to complete. Time will vary depending upon theneeds ofthe individual case. Any comments on theamountofilmc you are required to
`complete this form should be sent to the Chief Information Officer, Patent and Trademark Office, Washington. DC 2023 I. DO NOT SEND FEES OR COMPLETED FORMS TO THIS ADDRESS. SEND
`TO: Assistant Commissioner for Parents, Washington, DC 20231,
`
`
`
`SKGF Rev 6/3/98 mac
`
`Petitioner Valve
`EX. 1004’ Page 2
`
`0050002.sb05
`
`Petitioner Riot Games, Inc. - EX. 1004, p. 2
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 2
`
`Petitioner Valve
`Ex. 1004, Page 2
`
`

`

`rt
`
`-
`3'
`
`is
`'
`
`—
`
`ROBERT GREENE STERNE
`EDWARD .J KESSLER
`JORGE A GOLDSTEIN
`:‘Ju SAMUEL L Fox
`g2 DAVID KS CORNWELL
`8’.” ROBERT W ESMCND
`\p—f;m TRACY-GENE G DURKIN
`\g'
`MICHELE A CIMBALA
`”:8: MICHAEL E RAY
`«’5' ROBERT E SOKOHL
`\fim
`'50—?"
`\DL-gg
`. ’—
`.——-|u
`gr;
`’—
`'_-=.=o
`
`STERNE, KESSLER, GOLDSTEIN 8: Fox P.L.L.C.
`ATTORNEYS AT LAW
`IIOO NEW YORK AVENUE, N.W,SUITE 600
`WASHINGTON, D CI 20005—3934
`
`
`(202) 37I72600
`FACSIMILE (202) 37172540, (202) 371—6566
`
`ERIC K STEFFE
`MICHAEL 0 LEE
`STEVEN R LUDWIG
`JOHN M COVERT”
`LINDA E ALCDRN
`RAz Er FLESHNER
`ROBERT C MILLONIG
`MICHAEL V MESSINGER
`JUDITH U KIM
`TIMOTHY J SHEA, JR
`
`DONALD R MCPHAIL
`PATRICK E GARRETT
`STEPHEN G WHITESIDE
`JEFFREY T HELVEY‘
`HEIDI L KRAUS
`JEFFREY R KURIN
`RAYMOND MILLIEN
`PATRICK D O’BRIEN
`LAWRENCE B BUGAISKY
`CRYSTAL D SAYLES"
`
`EDWARD W YEE
`ALBERT L FERRO*
`DONALD R BANowIT‘
`PETER A JACKMAN
`MOLLY A MCCALL
`TERESA U MEDLER
`JEFFREY S WEAVER
`KRISTIN K VIDOVICH
`ANDREW S ROBERTS“
`KENDRlCK P PATTERSON“
`
`September 28, 1999
`
`DONALD J FEATHERSTONE“
`KAREN R MARKOWICZ“
`GRANT E REEDM
`SUZANNE E ZISKA"
`BRIAN J DEL BUONO”
`VINCENT L CAPUANO’”
`ANDREA J KAMAGE"
`NANCY J DEGEN“
`ROBERT H BENSON"
`OF COUNSEL
`
`'BAR OTHER THAN D C
`“REGISTERED PATENT AGENTS
`
`WRITER’S DIRECTNUMBER.‘
`(202) 789-5 506
`INTERNETADDRESS:
`RMILL!EN@SKGF.COM
`
`
`
`'
`
`Assistant Commissioner for Patents
`
`Washington, DC. 20231
`
`Box Patent Application
`
`Re:
`
`U.S. Continuation Utility Patent Application under 37 C.F.R. § 1.53(b)
`(Based on Appl. No. 08/896,797; Filed: July 18, 1997)
`Appl. No. To be assigned; Filed: September 28, 1999
`For:
`Server-Group Messaging System for Interactive Applications
`Inventors:
`Jeffrey J. ROTHSCHILD, Daniel J. SAMUEL and
`Marc P. KWIATKOWSKI
`17190050002
`
`Our Ref:
`
`Sir:
`
`I
`The following documents are forwarded herewith for appropriate action by the U.S '
`Patent and Trademark Office:
`
`é
`
`I
`
`I‘
`
`1'
`
`l.
`
`2.
`
`PTO Utility Patent Application Transmittal Form (PTO/SB/OS);
`
`U.S. Utility Patent Application entitled:
`
`Server-Group Messaging System for Interactive Applications
`
`and naming as inventors:
`
`Jeffrey J. ROTHSCHILD, Daniel J. SAMUEL and
`Marc P. KWIATKOWSKI
`
`the application consisting of:
`
`Petitioner Valve
`Ex. 1004' Page 3
`
`Petitioner Riot Games, Inc. - EX. 1004, p. 3
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 3
`
`Petitioner Valve
`Ex. 1004, Page 3
`
`

`

`g,—
`
`\-
`
`.
`
`STERNE, KESSLER, GOLDSTEIN 8: Fox P.L.L.c.
`
`Assistant Commissioner for Patents
`
`September 28, 1999
`Page 2
`
`a.
`
`A specification containing:
`
`(i) 55 pages of description prior to the claims;
`(ii) 4 pages of claims (16 claims);
`(iii)
`a one (1) page abstract;
`
`b.
`
`Eleven (11) sheets of drawings: (Figures 1-11);
`
`USPTO Utility Patent Application Transmittal Form PTO/SB/OS;
`
`37 CPR. § 1.136(a)(3) Authorization to Treat a Reply As Incorporating An
`Extension of Time (in duplicate); and
`
`Two (2) return postcards.
`
`3.
`
`4.
`
`5.
`
`It is respectfully requested that, of the two attached postcards, one be stamped with the
`filing date of these documents and returned to our courier, and the other, prepaid postcard, be
`stamped with the filing date and unofficial application number and returned as soon as possible.
`
`This application claims priority to U.S. Application No. 08/896,797, filed July 18,
`1997, now allowed, which is a continuation of U.S. Application No. 08/595,323, filed,
`February 1, 1996, now U.S. Patent No. 5,822,523.
`
`The U.S. Patent and Trademark Office is hereby authorized to charge any fee deficiency,
`or credit any overpayment, to our Deposit Account No. 19-0036. A duplicate copy ofthis letter
`is enclosed.
`
`This patent application is being submitted under 37 GER. § 1. 53(1)) without
`Declaration and withoutfilingfee.
`
`
`
`Respectfully submitted,
`
`STERNE, KESSLER, GOLDSTEIN & Fox P.L.L.C.
`
`0050002.pt0
`
`Raymond Millien
`
`Attorney for Applicants
`Registration No. 43,806
`
`Petitioner Valve
`Ex_ 1004’ Page 4
`
`'
`'
`Petitioner
`
`R' tG
`10
`
`ames
`
`, Inc. - Ex. 1004,
`
`.4
`
`p
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 4
`
`Petitioner Valve
`Ex. 1004, Page 4
`
`

`

`CERTIFICATE OF MAILING BY "WM"
`'EwMafl'MaflingLabdNo. 11112533118115
`DmofDepoanW. Ihatbycem‘fydnt
`fiiipapuorfecisbcingdqnmedwilhlheUnitedSWPon-Il
`quica'Equn‘lPodotfiumAd-tunee'uvicemd:
`37CFR1.10mbedamh¢£uwd-bavemdiad&enedlo:
`mmePm,Wuhingm D.C.2073l
`M};a
`
`
`
`Attorney Docket No. 16326-701
`
`PATENT
`
`SERVER-GROUP NIESSAGING SYSTEM
`FOR INTERACTIVE APPLICATIONS
`
`Inventors: Daniel Joseph Samuel
`Marc Peter Kwiatkowski
`
`Jefli'ey Iacldel 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.
`
`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 301m and 100m.
`
`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 Valve
`EX. 1004’ Page 5
`
`Petitioner Riot Games, Inc. - EX. 1004, p. 5
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 5
`
`Petitioner Valve
`Ex. 1004, Page 5
`
`

`

`.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
`
`5
`
`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. Gateways are computer systems connected to the
`
`12‘I.
`
`
`
`10
`
`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 fimctions in
`
`15
`
`a network. Routers are nodes that are connected to the network by more than
`
`one link and whose sole fimction 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
`
`20
`
`called an intemet. 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 worldmwide network, it is desirable to
`
`create interactive networked applications that bring together many people in a
`
`25
`
`shared, networked, interactive application. Unfortunately, creating such
`
`Petitioner Valve
`EX. 1004’ Page 6
`
`Petitioner Riot Games, Inc. - EX. 1004, p. 6
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 6
`
`Petitioner Valve
`Ex. 1004, Page 6
`
`

`

`-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
`
`5
`
`implemented in software on a PC connected to a network. A rate set by its
`
`internal time base, it would sample the inputs ofthe local user, receive
`
`messages fi'om the network from the PCs ofthe other players and send
`
`messages out to the PCs ofthe other players. A typical rate will be ten time
`
`per second for a time period of lOOms. 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 game that created the illusion of a 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 games that can be played between
`
`15
`
`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 game.
`
`20
`
`The case of a two player game played over a modem is particularly simple.
`
`Ifthe 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
`
`25
`
`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
`
`
`
`Petitioner Valve
`Ex_ 1004’ Page 7
`
`"
`'
`I.-E.1004,
`Petitioner RIOt Games, nc
`X
`
`p
`
`.7
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 7
`
`Petitioner Valve
`Ex. 1004, Page 7
`
`

`

`.4-
`
`each of the other 7 players every time period and will receive 7 messages firom
`
`the other players in the same time period. Ifthe 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
`
`5
`
`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, LANs are only deployed in
`
`commercial applications and cannot be considered for deploying a networked
`
`interactive application to consumer users.
`
`10
`
`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
`
`15
`
`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.
`
`20
`
`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. Iftlhe game uses TCP/IP to send its
`
`25
`
`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.
`
`
`
`
`Petitioner Valve
`EX. 1004’ Page 8
`
`Petitioner Riot Games, Inc. - EX. 1004, p. 8
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 8
`
`Petitioner Valve
`Ex. 1004, Page 8
`
`

`

`-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
`modern by 20%: Ifthe messages are reduced to 20 bytes, just 8 players can be
`
`5
`
`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
`
`10
`
`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 software itself. Latency is
`
`important in an interactive application because it defines the responsiveness of
`
`15
`
`the system. When a player provides a new input on their system, it is desirable
`
`for that input to immediately afi‘ect 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 fi‘om when a player 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 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
`
`25
`
`message quickly, it will not be until 50 ms have passed that the last player of
`
`the seven will have received the message.
`
`
`
`Petitioner Valve
`EX. 1004’ Page 9
`
`Petitioner Riot Games, Inc. - EX. 1004, p. 9
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 9
`
`Petitioner Valve
`Ex. 1004, Page 9
`
`

`

`
`
`
`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
`
`5
`
`protocols, IP corresponds to a layer 3 or Network layer protocol. It provides
`
`services for transmission and routing ofpackets 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. IP also defines
`
`the routing of packets between network links in an inter-network. Gateways
`
`10
`
`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 ofthe 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 ofthe local network links to
`
`15
`
`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
`
`20
`
`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/[P Tutorial”. IP, TCP and UDP are unicast protocols:
`
`packets, streams or datagrams are transmitted from a source to a single
`destination.
`
`25
`
`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 1], 12, 13, 14,
`
`Petitioner Valve
`EX. 1004' Page 10
`
`Petitioner Riot Games, Inc. - EX. 1004, p. 10
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 10
`
`Petitioner Valve
`Ex. 1004, Page 10
`
`

`

`-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 ofthe 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
`
`5
`
`on packet formats that contain a source address, destination address and a
`
`payload. This is representative of commonly used wide area network protocols
`
`such as 11’. There are other components in an actual [P packet, but for sake of
`
`this example, only these items will be considered. Figure 2 shows the example
`
` 10
`
`packets that are sent by the hosts to one another using a conventional unicast
`
`network protocol such as 1?. 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
`
`ofthe 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,
`
`15
`
`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 ofthese
`
`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
`
`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 from every other host that wishes to communicate with it. In an
`
`interactive application, this will happen at a regular and high rate. All ofthe
`
`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 Valve
`EX. 1004’ Page 11
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 11
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 11
`
`Petitioner Valve
`Ex. 1004, Page 11
`
`

`

`-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.
`
`lO
`
`
`15
`
`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 extensions to the IP protocol that enable IP
`
`multicasting. 1P multicasting supports the transmission of a [P 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 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
`
`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 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
`
`25
`
`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 Valve
`
`EX. 1004, Page 12
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 12
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 12
`
`Petitioner Valve
`Ex. 1004, Page 12
`
`

`

`.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
`
`5
`
`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
`
`10
`
`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
`
`15
`
`routers that will be forwarding trafic for that group. RFC-1112 does not
`
`describe how this is to be done. Many difi‘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 ofthese approaches are methods for
`
`propagation of multicast routing information between the multicast routers and
`
`20
`
`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 effects. The process of propagation of group membership information to
`
`all of the relevant routers is not instantaneous. In a large complex network it
`
`25
`
`can even take quite a period oftime depending on the number of routers that
`
`must receive that updated group membership information and how many
`
`
`
`Petitioner Valve
`Ex_ 1004’ Page 13
`
`"
`'
`1.-E.1004,
`Petltloner R10t Games, nc
`X
`
`p
`
`.13
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 13
`
`Petitioner Valve
`Ex. 1004, Page 13
`
`

`

`-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 ofthe algorithm that is used. RFC-1112 mentions this problem and
`
`some ofthe side effects that must be handled by an implementation of a
`
`5
`
`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
`
`10
`
`unwanted datagrams fi'om 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 ofthese changes. Imagine the case where
`
`15
`
`Host Njoins an existing group by sending a join message to its local router.
`
`The group already contains Host M which is a number of router 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 ofHost M has not
`
`yet been informed of the change in group membership and as a result the
`
`20
`
`datagram is not forwarded to one of the particular network links connected to
`
`the local router ofHost 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
`
`datagrarns addressed to the group from Host M until the local router ofM has
`
`its group membership information updated. Other related problems can also
`
`25
`
`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
`
`
`
`Petitioner Valve
`Ex_ 1004’ Page 14
`
`"
`'
`I.-E.1004,
`Petltloner RIOt Games, nc
`X
`
`p
`
`.14
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 14
`
`Petitioner Valve
`Ex. 1004, Page 14
`
`

`

`
`
`-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 suficiently reduce the
`
`message rate between the hosts.
`
`\Vith 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 nwd 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,
`
`15
`
`each host will need to send 9 messages to 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
`
`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 Valve
`EX. 1004’ Page 15
`
`Petitioner Riot Games, Inc. - EX. 1004, p. 15
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 15
`
`Petitioner Valve
`Ex. 1004, Page 15
`
`

`

`
`
`
`-12-
`
`routers is aware of the message group and has the proper routing information.
`
`A network protocol such I? 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
`
`5
`
`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
`
`10
`
`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
`
`15
`
`is then receiv