UNITED STATES PATENT AND TRADEMARK OFFICE
`DOCUMENTCLASSIFICATION BARCODE SHEET
`
` AAU
`
`
`
`ooo
`
`CATEGORY:
`
`CLEARED
`
`
`
`ADDRESS
`CONTACTIF FOUND:
`
`Petitioner Valve
`Ex. 1004, Page 1
`
`7
`Petitioner Riot Games,Inc. - Ex. 1004, p. 1
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 1
`
`Petitioner Valve
`Ex. 1004, Page 1
`
`

`

`Please type a sign(+) inside this box
`
`> is
`
`66/92/60:
`
`
`
`o
`
`wage
`
`2. [Total Pages_60BY Specification ] applicable, all necessary)
`
`
`
`
`
`
`
`
`b. [] Copy from a prior application (37 CFR 1.63(d)) (for
`continuation/divisional with Bex 17 completed)
`[Note Box 5 below]
`
`i.
`
`(1
`
`11. [] Information Disclosure
`Statement (IDS)/PTO-1449
`
`(1 Copies of IDS Citations
`
`
`
`PTO/SB/05 (2/98)
`|
`Approved for use through 09/30/2000. OMB 0651-0032
`Patent and Trademark Office: U.S. DEPARTMENT OF COMMERCE
`
`
`Underthe Paperwork Reduction Act of 1995, no persons are required to respond to a collection of information uniessit displays a valid OMB contro] number.
`
`
`Attorney Docket No.
`1719.0050002
`
`
`
`First Inventor or
`
`Jeffrey J. ROTHSCHILD
`
`
`UTILITY PATENT APPLICATION TRANSMITTAL
`.
`Arve
`
`
`Application Identifier
`
`Server-Group Messaging Systemfor Interactive
`(Onlyfor new nonprovisional applications under 37 CFR § 1 33(b)
`Applications
`
`Express Mail Label No Tea
`—
`
`
`
`Assistant Commissioner for Patents
`w
`
`
`ao
`APPLICATION ELEMENTS
`ADDRESS TO"
`Box Patent Application
`~
`
`See MPEP chapter 600 concerning utility patent application contents
`Washington, DC 20231
`w
`
`
`
`1. £])
`* Fee Transmittal Form (e.g., PTO/SB/17)
`6. [J Microfiche Computer Program (Appendix)
`
`
`(Submit an original, and a duplicateforfee processing)
`7. Nucleotide and/or Amino Acid Sequence Submission (if
`
`
`
`
`
`
`(preferred arrangementsetforth below)
`- Descriptivetitle of the Invention
`
`
`a. Oo Computer Readable Copy
`- Cross References to Related Applications
`
`
`~ Backgroundofthe Invention
`
`
`.
`.
`- Brief Summary ofthe Snventtan
`
`
`b. Oo Paper Copy (identical to computer copy)
`- BriefDescription ofthe Drawings(iffiled)
`
`
`+ Detailed Description
`
`
`.
`eo:
`:
`:
`~ Ch
`
`
`c.[]
`Statementverifying identity of above copies
`: Sims) ofthe Disclosure
`
`
` ACCOMPANYING APPLICATION PARTS
`
`Drawings (35 U.S.C. 113)
`
`
`11{Total Sheets ]
`
`
`Oath or Declaration
`{Total Pages
`]
`8. [) AssignmentPapers (cover sheet & document(s))
`
`
`9. [] 37 CFR 3,73(b) Statement
`(L] Powerof Attorney
`
`
`(when thereis an assignee)
`a. [ Newly executed(original or copy)
`
`
`
`
`
`10. [] English Translation Document(ifapplicable)
`
`
`
`
`DELETION OF INVENTOR(S)
`12. [] Preliminary Amendment
`Signed statementattached deleting inventor(s)
`
`
`
`13.
`Return Receipt Postcard (MPEP 503)
`namedin the prior application, see 37 CFR §§
`
`
`1.63(d)(2) and 1.33¢b).
`(Should be specifically itemized)
`
`
`([] Statementfiled in prior
`[[] *Small Entity Statement(s)
`14,
`
` 5.0 Incorporation By Reference (useuble ifBox 4b is checked)
`application, Status still proper
`(PTO/SB/09-12)
`
`
`and desired
`Theentire disclosure ofthe prior application, from which a copy of the oath
`
`
`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
`[] Certified Copy ofPriority Document(s)
`reference therein.
`
`
`(ifforeign priority is claimed)
`
`Other:
`37 C.F.R. § 1.136(a)\(3) Authorization
`
`Oo Other’
`
`*NOTE FOR ITEMS 1 & I4 IN ORDER 10 Bit ENTITLED TO PAYSMALL ENTITY FEES, A
`SMALL ENTITYSTATEMENTIS REQUIRED (37 C.F.R& 1 27), EXCEPTIF ONE FILED INA
`
`PRIOR APPLICATIONIS RELIED UPON(37 C F.R. $1 28)
`
`
`If a CONTINUINGAPPLICATION,check appropriate box, and supplythe requisite information below and in a preliminary amendment
` 17.
`
`
`16,
`
`
`OContinuation-in-Part (CIP) of prior application No: 08/896,797
`O Divisionat
`Continuation
`
`
`
`Prior application information: Examiner Zarnit Maung
`Group/Art Unit: 2758
`
`
`
`
`
`
`
`
`NAMEOCee
`
`
`
`foay____|Washingon«STATE«[cope[20005036
`
`
`
`
`18. CORRESPONDENCE ADDRESS
`
`? or BQ Correspondence
`}
`[] Customer Number
`or Bar Code Label i(InsertCustomerNo.orAttachbarcodelabelhere)3 address below
`STERNE, KESSLER, GOLDSTEIN & FOX P.L.L.C.
`
`
`
`3
`
`
`
`
`ianaToReIt[GgepillWi(deefeofFY
`
`
`Burden Hour Statement:
`this form is estimatedfo take 0.2 hours ta complete. Time will vary depending uponthe needsofthe individual case. Any comments on the amount oftime you are required to
`completethis form shouldbesent to the Chief Information Officer, Patent and Trademark Office, Washington, DC 20231. DO NOT SEND FEES OR COMPLETED FORMSTO THIS ADDRESS. SEND
`TO: Assistant Commissioner for Patents, Washington, DC 20231.
`
`
`
`
`
`
`
`SKGF Rev6/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
`
`

`

`-_
`
`-
`¥
`
`7
`
`ROBERT GREENE STERNE
`EDWARD J KESSLER
`JorGe A GOLDSTEIN
`=o SAMUEL L FOX
`== Davip KS CORNWELL
`on ROBERT W ESMOND
`ND een 19 TRACY-GENE G DURKIN
`— ae MICHELE A CIMBALA
`Bho EE GC Michael B Ray
`oS: ROSERT E SOKOHL
`—
`0 Se -
`Ww aaa
`le]
`=o——
`. =—
`=
`
`STERNE, KESSLER, GOLDSTEIN & Fox P.L.L.C.
`ATTORNEYS AT LAW
`1100 NEW YORK AVENUE, N.W, SUITE GOO
`WASHINGTON, DC. 20005-3934
`
`
`(202) 371-2600
`FACSIMILE (202) 371-2540, (202) 371-6566
`
`Ertc K STEFFE
`MicHseL Q LEE
`STEVEN R LUDWIG
`JOHN M COVERT*
`LINDA E ALCORN
`Raz £&. FLESHNER
`ROBERT C MILLONIG
`MICHAEL V MESSINGER
`Jupitw U KIM
`TimoTHY J SHEA, JR
`
`Donatp R MCPHAIL
`PATRICK E GARRETT
`STEPHEN G WHITESIDE
`JerrRey T HELVEY*
`Hep! L Kraus
`JerrrRey R KURIN
`RAYMOND MILLIEN
`Patrick 2 O’BRIEN
`LAWRENCE B Bucalsky
`CrysTat D SAYLES*
`
`EDWARD W YEE
`ALBERT L FERRO*
`Donato R BANowIT*
`Peter A JACKMAN
`MOLLY A MCCALL
`TERESA U MEDLER
`JEFFREY S WEAVER
`KRISTIN K VIDOVICH
`ANDREW S ROBERTS”
`KENDRICK P PATTERSON*
`
`September 28, 1999
`
`DONALD J FEATHERSTONE**
`KaREN R MARKOWICZ**
`GRANT E Reept*
`SUZANNE E ZiSka**
`Brian J DeL Buono**
`VINCENT L CaAPUANO**
`ANDREA J KAMAGE**
`
`NANCY J DEGEN**
`RoBERT H BENSON*
`OF COUNSEL
`
`*BaAR OTHER THAN DC
`**REGISTERED PATENT AGENTS
`
`.
`’
`WRITER’S DIRECT NUMBER:
`(202) 789-5506
`INTERNETADDRESS:
`RMILLIEN@SKGF.COM
`
`
`
`.
`
`.
`
`Assistant Commissioner for Patents
`Washington, D.C. 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
`Server-Group Messaging System for Interactive Applications
`For:
`Inventors:
`Jeffrey J. ROTHSCHILD,Daniel J. SAMUEL and
`Mare P. KWIATKOWSKI
`1719.0050002
`
`Our Ref:
`
`Sir:
`
`| yoy
`
`The following documents are forwarded herewith for appropriate action by the U.S. 7 :
`Patent and Trademark Office:
`pS S hi
`1.
`PTO Utility Patent Application Transmittal Form (PTO/SB/05);
`; S :
`
`2.
`
`U.S. Utility Patent Application entitled:
`
`Server-Group Messaging System for Interactive Applications
`a
`and namingas inventors:
`
`Jeffrey J. ROTHSCHILD,Daniel J. SAMUEL and
`Mare P. KWIATKOWSKI
`the application consistingof:
`
`poBN Po
`ON |
`a oy 4
`BO;
`{
`4
`
`po
`: oy
`: .
`|
`-
`
`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
`
`€
`

`

`oo
`
`x
`
`STERNE, KESSLER, GOLDSTEIN & 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) pageabstract;
`
`
`
`b.
`
`Eleven (11) sheets of drawings: (Figures 1-11);
`
`USPTO Utility Patent Application Transmittal Form PTO/SB/05;
`
`37 C.F.R. § 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 ofthese documents and returned to our courier, and the other, prepaid postcard, be
`stamped with the filing date and unofficial application numberand returned as soon as possible.
`
`This application claimspriority to U.S. Application No. 08/896,797, filed July 18,
`1997, now allowed, whichis 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 copyofthis letter
`is enclosed.
`
`This patent application is being submitted under 37 C.E_R. § 1.53(b) without
`Declaration and withoutfilingfee.
`
`Respectfully submitted,
`
`STERNE, KESSLER, GOLDSTEIN & FOX P.L.L.C.
`
`0050002.pto
`
`Raymond Millien
`Attorney for Applicants
`Registration No. 43,806
`
`Petitioner Valve
`Ex. 1004, Page 4
`
`Petitioner
`itt
`
`Riot
`Riot G
`
`Games
`
`, Inc. - Ex. 1004,
`
`p. 4
`
`p
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 4
`
`Petitioner Valve
`Ex. 1004, Page 4
`
`

`

`CERTIFICATE OF MAILING BY "EXPRESS MAIL"
`“Express Mail” Mailing Labei No. TBs
`
`37CFR 1. 10 om the date indicated above and is ackiressed to:
`Assistant Commissioner for Patenta , Waahingion, D.C. 20231
`wearin
`
`
`
`PATENT
`Attorney Docket No. 16326-701
`
`SERVER-GROUP MESSAGING SYSTEM
`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 methods for reducing
`
`message rate and latency.
`
`Background of the Invention
`
`There are a wide rangeofinteractive 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 exampleofinteractive 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 gamescontrol the speed oftheir interaction
`with the user through an internal time base. The application usesthis 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 togetherin networks. A network is comprised of
`nodes andlinks. The nodes are connected in such a waythatthere exists a path
`from each nodeover the links and through the other nodesto each of the other
`
`5
`
`nodes in the network. Each node may be connected to the network with one
`
`4
`
`or morelinks. Nodesare 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 onelink. They not only communicate with the other
`nodesas do hosts, but they also forward messages on one oftheir network
`links to other nodes on their other network links. This processing of
`forwarding messagesis called routing. In addition to sending and receiving
`messages and their routing functions, gateways may perform otherfunctions 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 networklinks to whichit 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 whatis
`
`called an internet. 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
`
`
`
`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 thelimitations ofthe
`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 byits
`internal time base, it would sample the inputs ofthe local user, receive
`messages from 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 100ms. The messages sent between the PCs
`would contain information that was needed to keep the gameconsistent
`between all ofthe PCs. In a gamethat createdtheillusion 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 twoplayers overdial-
`up phonelines using modems. The network messages sent by such games
`contain a widevariety 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 playerthat effect the other players in the game.
`The case of a two player game played over a modemis 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 modemsand phoneline 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 gameplayed with 8 players
`on a LAN,the message rate increases. Each PC must send 7 messages, one to
`
`5
`
`10
`
`15
`
`20
`
`25
`
`Petitioner Valve
`Ex. 1004, Page 7
`
`Petitioner Riot Games,
`iti
`
`Inc
`x
`Inc. - Ex. 1004,
`
`p
`
`p. 7
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 7
`
`Petitioner Valve
`Ex. 1004, Page 7
`
`

`

`accessed through dial-up phonelines using modems. While modem speeds
`have increased rapidly, they have now reachedabit rate of 28.8 Kbits/sec
`which is close to the limit set by the signal-to-noise ratio of conventional phone
`
`
`
`
`4.
`
`each ofthe other 7 players every time period and will receive 7 messages from
`
`the other players in the same time period. If the messaging time periodis
`
`100ms, the total message rate will be 70 messages sent per second and 70
`
`messages received per second. As can be seen the messagerate increases
`
`5
`
`linearly with the numberofplayers in the game. The message rates and data
`rates supported by popular LANsare high enough to support a large number of
`players at reasonable message sizes. Unfortunately, LANsare 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 consumerusers all must be
`
`15
`
`20
`
`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 exampleofthe 8 player networked game, consider a wide area
`network implementation where the PCs of eachof the players is connected to
`the network with a 28.8 Kbit/sec modem. Assumethat the network used in
`
`this example is the Internetso that all of the network protocols and routing
`behavior is well defined and understood. If the game uses TCP/IP to sendits
`
`25
`
`messages between the PCsin the game, the PPP protocol overthe dial-up
`
`phonelines 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 PCsin the game and received 10 times per second
`
`5
`
`from the other PCs. This is 35.0 Kbits/sec which exceeds the capabilities ofthe
`modem by 20%. Ifthe messages are reduced to 20 bytes, just 8 players can be
`supported, but this approach clearly cannot support networked interactive
`
`applications with large numbersofparticipants. There are other problems
`beyondjust the bandwidth of the network connection. There is the loading on
`each PC caused by the high packet rates and thereis 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 numberofplayers in the game, less and less of the
`processorwill be available for running the game softwareitself. Latency is
`importantin an interactive application because it defines the responsiveness of
`the system. Whena player provides a new input on their system, it is desirable
`
`for that input to immediately affect the gameonall of the other players
`
`systems. This is particularly important in any game where the game outcome
`
`dependson players shootingat targets that are moved by the actions ofthe
`
`other players. Latency in this case will be the time from whena player acts to
`
`movea target to the timethat the target has moved on the screensofthe other
`players in the game. A major portion ofthis 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
`message quickly, it will not be until 50 ms have passed that the last player of
`
`the seven will have received the message.
`
`15
`
`20
`
`25
`
`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
`
`

`

`-6-
`
`Internet Protocol Multicasting
`As mentioned before, the Internet is a widely known example of a wide
`area network. TheInternetis based on a protocol appropriately called the
`Internet Protocol (IP). In the OSI reference modelfor layers of network
`protocols, IP correspondsto a layer 3 or Network layer protocol. It provides
`services for transmission and routing ofpackets between two nodesin an
`internet. The addressing model provides a 32 bit address for all nodesin the
`network and all packets carry source and destination addresses. IP also defines
`the routing ofpackets between networklinks in an inter-network. Gateways
`and routers maintain tables that are used to lookup routing information based
`on the destination addresses ofthe packets they receive. The routing
`informationtells the gateway/router whetherthe destination ofthe packet is
`directly reachable on a local network link connected to the gateway/routerorif
`not, the address of another gateway/router on one ofthe local network links to
`which the packet should be forwarded. On top ofIP are the layer 4 transport
`protocols TCP and UDP. UDPprovides datagram delivery services to
`applications that does not guarantee reliable or in-order delivery ofthe
`datagrams. TCP is a connection oriented service to applications that does
`providereliable delivery of a data stream. It handles division ofthe stream into
`packets and ensuresreliable, in-order delivery. See the Internet Society RFCs:
`REC-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 networklinks 11, 12, 13, 14,
`
`10
`
`
`20
`
`25
`
`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 eachofthe 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 componentsin an actual IP packet, but for sake of
`this example, only these items will be considered. Figure 2 showsthe 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 host3, 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,
`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 networkindividually from the source host to
`the destination host. So in this example each host must send three packets and
`receive three packets in order for each host to send its payload to the other
`
`three hosts.
`As can be seen, each host must send a packet to every other host thatit
`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
`hosts that wish to communicate with one anotherwill need to send packets to
`each other eight to ten times per second. With four hosts communicating with
`
` 10
`
`
`
`
`
`
`5
`
`15
`
`20
`
`25
`
`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
`
`

`

`
`
`
`-8-
`
`one anotherasin 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.
`
`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 ofthe IP address space and identified by class
`D IP addresses - these are IP addresses with “1110” in the high order4 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 whichit 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 duplicationis distributed throughout the networkto all ofthe
`multicast routers. For distributed multicast messaging to work in a wide area
`network, all ofthe routers handling datagramsfor multicast hosts must support
`the routing of multicast datagrams. Such multicast routers must be aware of
`the multicast group membership ofall ofthe hosts locally connected to the
`
`5
`.
`
`10
`
`15
`
`20
`
`25
`
`Petitioner Valve
`Ex. 1004, Page 12
`
`a
`Petitioner Riot Games, Inc. - Ex. 1004, p. 12
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 12
`
`Petitioner Valve
`Ex. 1004, Page 12
`
`

`

`-9-
`
` 10
`
`15
`
`router in order to deliver multicast datagramsto 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 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 ofgroup 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 up to datelist 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 messages using
`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 network to all of the other
`routers that will be forwardingtraffic for that group. RFC-1112 does not
`describe how this is to be done. Manydifferent approaches have been defined
`for solving this problem that will be mentioned later in descriptions ofrelated
`prior art. Despite their differences,all ofthese approaches are methods for
`propagation of multicast routing information between the multicast routers and
`techniquesfor routing the multicast datagrams in an inter-network supporting
`distributed multicast messaging.
`The distributed 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
`can even take quite a period oftime depending on the numberofroutersthat
`must receive that updated group membership information and how many
`
`20
`
`25
`
`Petitioner Valve
`Ex. 1004, Page 13
`
`Petitioner Riot Games,Inc. - Ex. 1004, 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 mentionsthis problem and
`someofthe side effects that must be handled by an implementation ofa
`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 ofgroup address assignment.
`This will result in incorrect datagram delivery, where hosts will receive
`unwanted datagramsfrom the duplicate group. This requires a method at each
`hostto filter out the unwanted datagrams. Anotherset ofproblemsresult from
`the time delay from whena groupis created, destroyed orits membership
`changed to whenall of the routers needed to route the datagramsto the
`member hosts have been informed ofthese changes. Imagine the case where
`Host N joins an existing group by sending ajoin messageto its local router.
`The group already contains Host M which is a numberofrouter hops away
`from Host N in the network. Shortly after Host N has sentit join message,
`Host M sends a datagram to the group,but the local router ofHost M has not
`yet been informed ofthe change in group membership and as a result the
`datagram is not forwarded to oneofthe particular network links connected to
`the local router ofHost M thatis 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 ofM has
`its group membership information updated. Other related problems can also
`occur. When a hostleaves a group, messages addressed to the group will
`continue for some time to be routed to that host up to the local router ofthat
`
` 10
`
`15
`
`20
`
`25
`
`Petitioner Valve
`Ex. 1004, Page 14
`
`Petitioner Riot Games,Inc. - Ex. 1004, p. 14
`
`Petitioner Riot Games, Inc. - Ex. 1004, p. 14
`
`Petitioner Valve
`Ex. 1004, Page 14
`
`

`

`
`
`all-
`
`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
`
`datagramsbeingcarried in a large network when there are many active
`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 group in order to
`send a messageto all of other hosts in the group. This is an improvement over
`conventional unicast messaging where one message would need to be sent to
`each ofthe other hosts in a group. However, distributed multicast messaging
`does nothing to reduce the received messagerate at each ofthe hosts when
`multiple hosts in a group are sending messages to the groupclosely spaced in
`time. Let us return to the example of a group of ten hosts sending messages
`seven times per-secondto the group. With conventional unicast messaging,
`each host will need to send 9 messages to the other hosts, seven timesper-
`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
`of received messages.
`An exampleofdistributed 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 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
`of a message group with address E. In advance the message group was created
`and each ofthe hosts joined the message group so that each ofthe multicast
`
`10
`
`20
`
`25
`
`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 properrouting 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 host38
`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
`membersofthe group. Let us consider how a packetssent 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 fromits routing tables that
`
`the multicast packet should be sent onto networklinks 46 and 47 and
`duplicates the packet and sends to both ofthese 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 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 process is followed for each ofthe 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 h