Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 1 of 351 PageID #: 40333
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 1 of 351 PagelD #: 40333
`
`(cid:40)(cid:59)(cid:43)(cid:44)(cid:37)(cid:44)(cid:55)(cid:3)(cid:20)(cid:19)(cid:21)
`A 2H S SSAC SSLARBE A IL
`
`
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 2 of 351 PageID #: 40334
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 2 of 351 PagelD #: 40334
`
`az United States Patent
`Holt et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,701,344 B1
`*Mar. 2, 2004
`
`US006701344B1
`
`(64) DISTRIBUTED GAME ENVIRONMENT
`
`(75)
`
`Inventors: Fred B. Holt, Seattle, WA (US); Virgil
`E. Bourassa, Bellevue, WA (US)
`(73) Assignee: us) Company, Seattle, WA
`(*) Notice:
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 417 days.
`
`This patent is subject to a terminal dis-
`elaimer.
`
`(21) Appl. No.: 09/629,042
`(22) Filed:
`Jul. 31, 2000
`
`
`(51)
`
`Int. Cl’...
`
`.
`sreeneeenees GO6F 15/16
`(82) ULS. Ch oe 709/204; 709/205; 709/203;
`709/243, 463/42
`
`5,734,865 A
`3/1998 Yu
`5,737,526 A
`4/1998 Periasamyet al.
`3,754,830 A
`5/1998 Butts ef al.
`5,761,425 A
`6/1998 Miller
`5,764,756 A
`6/1998 Onweller
`(List continued on next page.)
`OTHER PUBLICATIONS
`
`PR Newswire, “Microsoft Boosts Accessibility to Internet
`Gaming Zone with Latest Release,” Apr. 27, 1998, pp. LE.*
`PR Newswire, “Microsoft Announces Launch Date for
`UltraCorps, Tis Second Premium Title for the Internet Gam-
`ing Zone,” Ma 27, 1998, pp. LIE*
`Business Wire, “Boeing and Panthesis Complete SWAN
`Transaction,” Jul. 22, 2002, pp. HE.*
`(List continued on next page.)
`Primary Examiner—Dung C. Dinh
`Assistant Examiner—Bradley Edelman
`(7A) Attorney, Agent, ar Firm—Perkins Coie LLP
`(57)
`ABSTRACT
`
`Abroadcast technique in which a broadcast channel overlays
`a point-to-point communications network is provided. The
`broadcasting of a message over the broadcast. channel is
`effectively a multicast to those computers of the network that
`are currently connected to the broadcast channel. In one
`embodiment,
`the broadcast
`technique provides a logical
`broadcast channel to which host computers through their
`executing processes can be connected. Each computerthat is
`connected to the broadcast channel can broadcast messages
`onto and receive messages off of
`the broadcast channel.
`Each computer that is connected to the broadcast channel
`receives all messages that are broadcast while it is con-
`nected. The logical broadcast channel is implemented using
`an underlying network system(e¢.g., the Internet) that allows
`each computer connectedto the underlying network system
`to send messages to each other connected computer using
`each computer's address. Thus,
`the broadcast
`technique
`effectively provides a broadcast channel using anunderlying
`network system that sends messages on a point-to-point
`basis.
`
`19 Claims, 39 Drawing Sheets
`
`(58) Field of Search 0.0.0... 709/204, 205,
`709/227, 243, 203; 463/40, 42
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`oyoot we etal.
`soscons ‘
`*
`
`tne
`y
`weg
`ane
`ee ‘ * 099 pour tals ~ yous
`
`5/{992 Hauptscheinet al.
`....... 370/255
`5.117.422 A *
`5,309,437 A
`5/1994 Perlmanetal.
`
`5,426,637 A
`6/1995 Derbyetal.
`
`§,459,725 A * 10/1995 Bodner et al. 0...
`. 370/390
`5,471,623 A * W/1995 Napolitano, Je... 709/243
`5,535,199 A
`7/1996 Amatietal.
`oe A 0joss Sithon et al.
`5.644.714 A * T1997 Kikinis ccccccccecsccccccee 700/219
`5.673.265 A
`9/1997 Guptaet al.
`5,696,903 A
`12/1997 Mahany
`5,732,074 A
`3/1998 Spaur et al.
`5,732,086 A *
`3/1998 Liang etal... 370/410
`8,732,219 A
`3/1998 Blumeret al.
`
`
`
`Distribute
`broadcast message
`
`message
`from neighbor
`
`
`
`
`
`
`
`All neighbor
`selected
`
`2403
`
`Send internal
`message
`
`AB-AB 000001
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 3 of 351 PageID #: 40335
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 3 of 351 PagelD #: 40335
`
`US 6,701,344 BI
`Page 2
`
`
`
`U.S. PATENT DOCUMENTS
`
`8/1998 Sistanizadchetal.
`5,790,548 A
`8/1998 Deaton, Jr. et al.
`5,790,353 A
`8/1998 Onweller
`5,799,016 A
`9/1998 Hirviniemi
`5,802,285 A
`5,850,592 A * 12/1998 Ramanathan...4535/7
`5,864,711 A
`1/1909 Mairs et al.
`5,867,660 A
`2/1999 Schmidt et al.
`5,867,667 A
`2/1999 Butman etal,
`5,870,505 A
`2/1999 Brachoet al.
`5,874,060 A
`2/1999 Mairs etal.
`5,899,980 A
`5/1999 Wilf et al.
`§,907,610 A
`5/1999 Onweller
`
`5,925,097 A *
`7/1999 Gopinath et al. 0.40... 709/200
`$928,335 A
`7/1999 Morita
`5,935,218 A
`8/1999 Bell et al.
`5,948,054 A
`4/1999 Nielsen
`5,949,975 A
`9/1999 Batty etal.
`5,956,484 A
`9/1999 Rosenberg etal.
`5,970,232 A * 10/1999 Passint et al. 709/238
`5,974,043 A
`10/1999 Solomon
`5,987,506 A
`11/1999 Carteret al.
`6,003,088 A
`12/1999 Houston et al.
`6,013,107 A
`1/2000 Blackshear et al.
`6,023,734 A
`2/2000 Ratcliff et al.
`6,029,171 A
`2/2000 Smiga et al,
`6,032,188 A
`2/2000 Mairs et al.
`6,038,602 A
`3/2000 Ishikawa
`6,047,289 A
`4/2000 Thorne et al.
`6,094,676 A
`7/2000 Gray et al.
`
`9/2000 Chuprunet al.
`...
`6,115,580 A *
`. 709/204
`6,167,432 A * 12/2000 Jiang .....
`
`
`teers 700/204
`1/2001 Kurashimaet al.
`6,173,314 Bi *
`3/2001 May et al.
`6,199,116 BL
`6,216,177 BL
`4/2001 Maits et al.
`6,223,212 Bi
`4/2001 Batty et al.
`6,243,691 BL
`6/2001 Fisher et al.
`6,268,855 Bi
`F2001 Mairs et al.
`6,271,839 BL
`8/2001 Mairs et al.
`6,272,548 Bi *
`8/2001 Cotter et alo 709/239
`6,285,363 Bl
`9/2001 Mairs et al.
`6,304,928 BL
`10/2001 Mairs ct al.
`
`wee 709/238
`6,321,270 Bl
`* 11/2001 Crawley...
`» 370/466
`6,463,078 Bl * 10/2002 Engstromet al.
`
`-- 463/40
`6,524,189 BL *
`2/2003 Rautila .........
`vee 370/342
`
`...
`2002/0027896 Al *
`3/2002 Hughes et al.
`OTHER PUBLICATIONS
`
`Azar et al., “Routing Strategies for Fast Networks,” May
`1992, INFOCOM 792, Eleventh Annual Joint Conference of
`he JEEE Computer and Communications Societies, vol. 1,
`170-179.*
`Cho et al., “A Flood Routing Method for Data Networks,”
`Sep. 1997, Proceedings of 1997 International Conference on
`Information, Communications, and Signal Processing, vol.
`3, pp. 1418-1422."
`Komine et al., “A Distributed Restoration Algorithm for
`Multiple-Link and Node Failures of Transport Networks,”
`Dec. 199 Global Telecommunications Confercace, 1990,
`and Exhibition, TEEE, vol. 1, pp. 459-463.*
`Peercy et al, “Distributed Algorithms for Shortest—Path,
`Deadlock-Free Routing and Broadcasting in Arbitrarily
`aulty Hypercubes,” Jun. 1990, 20” International Sympo-
`sium on Fault-Tolerant Computing, 1990, pp. 218~225.*
`US.patent application Ser. No. 09/629,570, Bourassact al.,
`filed Jul. 31, 2000.
`U.S. patent application Ser. No. 09/629,577, Bourassa et al.,
`filed Jul. 31, 2000.
`
`
`
`USS. patent application Ser. No. 09/629,575, Bourassa et al,
`filed Jul. 31, 2000.
`US. patent application Ser. No. 09/629,572, Bourassa et al.,
`filed Jul. 31, 2000.
`U.S. patent application Ser, No. 09/629,023, Bourassa et al.,
`filed Jul, 31, 2000,
`US. patent application Scr, No. 09/629,043, Bourassact al,
`filed Jul. 31, 2000.
`US. patent application Ser. No. 09/629,024, Bourassaet al.,
`filed Jul. 31, 2000.
`US. patent application Ser. No. 09/629,576, Bourassa et al.,
`filed Jul. 31, 2000.
`Murphy, Patricia, A., “The Next Generation Networking
`Paradigm: Producer/Consumer Model,” Dedicated Systems
`Magazine—2000(pp. 26-28).
`The Gamer’s Guide, “First-Person Shooters,” Oct. 20, 1998
`(4 pages).
`The O’Reilly Network, “Gnutella: Alive, Well, and Chang-
`ing Fast,” Jan. 25, 2001 (5 pages) hitp://www.open2p.com/
`Ipt... [Accessed Jan. 29, 2002].
`Oram, Andy, “Gnutella and Freenet Represents True Tech-
`nological Innovation,” May 12, 2000 (7 pages) The O’Reilly
`Network http://www.oreillynet.com/Ipt...
`[Accessed Jan.
`29, 2002],
`Internetworking Technologies Handbook, Chapter 43 (pp.
`43-1-43-16).
`Oram, Andy, “Peer-to~Peer Makes the Internet Interesting
`Again,” Sep. 22, 2000 (7 pages) The O’Reilly Network
`http://linux.oreillynet.com/Ipt... [Accessed Jan. 29, 2002].
`Monte, Richard, “The Random Walk for Dummies,”MIT
`Undergraduate Journal of Mathematics (pp. 143-148).
`Srinivasan, R., “XDR: External Data Representation Stan-
`dard,” Sun Microsystems, Aug. 1995 (20 pages) Internet
`RFC/STD/FYI/BCP
`Archives
`http://www.fags,.org/
`rfc1832.htmi [Accessed Jan. 29, 2002].
`A. Databeam Corporate White Paper, “A Printer on the
`7.120 Series Standards,” Copyright 1995 (pp. 1-16).
`Kessler, Gary, C., “An Overview of TCP/IP Protocols and
`the Internet,” Apr. 23, 1999 (23 pages) Hill Associates, Inc.
`http:/Avww.hill.com/library/publications/... [Accessed Jan.
`29, 2002].
`Bondy, J.A., and Murty, U.S.R., “Graph Theory with Appli-
`cations,” Chapter 1-3 (pp. 147), 1976 American Elsevier
`Publishing Co., Inc., New York, New York.
`Cormen, Thomas H. et al., Introduction to Algorithms,
`Chapter 5.3 (pp. 84-91), Chapter 12 (pp. 218-243), Chapter
`13 (p. 245), 1990, The MIT Press, Cambridge, Massachu-
`setts, McGraw-Hill Book Company, New York.
`The Common Object Request Broker: Architecture and
`Specification, Revision 2.6, Dec. 2001, Chapter 12 (pp.
`121-1210), Chapter 13 (pp. 13-1-13-56), Chapter 16(pp.
`16-1-16-26), Chapter 18 (pp. 18-1-18-52), Chapter 20
`(pp. 20-1-20-22).
`The University of Warwick, Computer Science Open Days,
`“Demonstration of the Problems of Distributed Systems,”
`http:/Avww.des.warwick.ac.u... [Accessed Jan. 29, 2002].
`in
`Alagar, S. and Venkatesan, S., “Reliable Broadcast
`Mobile Wireless Networks,” Department of Computer Sci-
`ence, University of Texas at Dallas, Military Communica-
`tions Conference, 1995, MILCOM 795 Conference Record,
`IEEE San Dicgo, California, Nov. 5-8, 1995 (pp. 236-240).
`International Search Report for The Boeing Company,Inter-
`national Patent Application No PCT/US01/24240, Jun. 5,
`2002 (7 pages).
`* cited by examiner
`
`AB-AB 000002
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 4 of 351 PageID #: 40336
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 4 of 351 PagelD #: 40336
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 1 of 39
`
`US 6,701,344 BL
`
`m
`
`<
`
`Poy
`Loo
`
`AB-AB 000003
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 5 of 351 PageID #: 40337
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 5 of 351 PagelD #: 40337
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 2 of 39
`
`US 6,701,344 BL
`
`
`
`AB-AB 000004
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 6 of 351 PageID #: 40338
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 6 of 351 PagelD #: 40338
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 3 of 39
`
`US 6,701,344 BL
`
`m0
`
`O
`
`AB-AB 000005
`
`RQ
`or
`
`22
`
`N
`
`2
`
`©
`
`AQ
`
`os
`220
`
`<q
`
`<
`
`Ww
`
`am
`
`Lu
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 7 of 351 PageID #: 40339
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 7 of 351 PagelD #: 40339
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 4 of 39
`
`US 6,701,344 BL
`
`ig.4A
`
`AB-AB 000006
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 8 of 351 PageID #: 40340
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 8 of 351 PagelD #: 40340
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 5 of 39
`
`US 6,701,344 BL
`
`AB-AB 000007
`
`~
`
`.A
`
`Lu
`
`t
`
`oo
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 9 of 351 PageID #: 40341
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 9 of 351 PagelD #: 40341
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 6 of 39
`
`US 6,701,344 BL
`
`Fig.4C
`
`AB-AB 000008
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 10 of 351 PageID #: 40342
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 10 of 351 PagelD #: 40342
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 7 of 39
`
`US 6,701,344 BL
`
`AB-AB 000009
`
`<w
`
`e
`bb
`
`WL
`
`”
`
`<
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 11 of 351 PageID #: 40343
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 11 of 351 PagelD #: 40343
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 8 of 39
`
`US 6,701,344 BL
`
`
`
`AB-AB 000010
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 12 of 351 PageID #: 40344
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 12 of 351 PagelD #: 40344
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 9 of 39
`
`US 6,701,344 BL
`
`AB-AB 000011
`
`DQ
`wy
`
`°0
`
`Lin
`
`us
`
`oO
`
`Qa
`
`oO
`
`m
`
`<
`
`H
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 13 of 351 PageID #: 40345
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 13 of 351 PagelD #: 40345
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 10 of 39
`
`US 6,701,344 BL
`
`a
`
`<
`
`2
`bin
`Ry
`
`ce
`
`AB-AB 000012
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 14 of 351 PageID #: 40346
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 14 of 351 PagelD #: 40346
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 11 of 39
`
`US 6,701,344 BL
`
`Ry
`
`w £
`
`0
`nay
`
`AB-AB 000013
`
`2 £
`
`0
`
`Q
`
`oO
`
`a
`
`Oo
`
`<
`
`ma
`
`<
`
`ao
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 15 of 351 PageID #: 40347
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 15 of 351 PagelD #: 40347
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 12 of 39
`
`US 6,701,344 BL
`
`Broadcaster
`
`og=3
`
`—
`~o &
`a &&5628a 2
`3G OS
`2 5.
`ageQe
`
`
`Application2{channel
`
`typechannelinstance)
`
`Fig.6
`
`AB-AB 000014
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 16 of 351 PageID #: 40348
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 16 of 351 PagelD #: 40348
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 13 of 39
`
`US 6,701,344 BL
`
`fewer
`
`soyoqedsip
`
`Ord
`
`902yoouuo7)
`
`
`
`
`
`yor|fe5
`
`cOL 002
`
`[euro]
`
`
`
`aumnboy9AINN9Y
`
`
`
`odessoutgsuodsal
`
`bd
`
`yeuu0)
`
`ysanbes
`
`fEL
`
`yszoproig
`
`ZLSh
`
`AB-AB 000015
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 17 of 351 PageID #: 40349
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 17 of 351 PagelD #: 40349
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 14 of 39
`
`US 6,701,344 BL
`
`Channel Instance,
`Connect Aux Info)
`
`Fig. §
`
`Opencall in port
`
`801
`
`802
`
`803
`Seek portal - computer
`(channel type channel
`instance)
`
`
`
`804<a>N Return(false)
`
`Y
`
`805
`Contacts
`
`¥
`
`806
`
`Achieve connection
`
`0
`
`N
`
`808
`
`Install external dispatcher
`
`809
`
`Connect request
`
`ct
`
`
`
`807
`
`Install external dispatcher
`
`AB-AB 000016
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 18 of 351 PageID #: 40350
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 18 of 351 PagelD #: 40350
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 15 of 39
`
`US 6,701,344 BL
`
`Seek portal
`computer
`
`Channel Type
`Channel Instance
`
`
`
`
`
`902
`
`Select next depth
`
`
`
`
`
`
`All portal computers
`selected
`
` Selected portal
`
`
`
`computer connected
`
`Return (success)
`
`AB-AB 000017
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 19 of 351 PageID #: 40351
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 19 of 351 PagelD #: 40351
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 16 of 39
`
`US 6,701,344 BL
`
`Contact process
`
`
`
`
`
`Send external message
`
`
`
`Fig. 10
`
`1002
`
`Add as connected portal
`computer
`
`AB-AB 000018
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 20 of 351 PageID #: 40352
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 20 of 351 PagelD #: 40352
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 17 of 39
`
`US 6,701,344 BL
`
`Fig. 11
`
`Connect request
`
`
`
`1101
`
`
`Wasa fully
`
`connected portal found
`
`
`N
`
`1102
`
`Restart
`
`Dial call in port of portal
`computer
`
`1104
`
`¥
`
`1405
`
`Send external message
`
`1106
`
`Receive external message
`
`Na
`Ntl
`
`1107
`
`1108
`Y
`Set expect holes from
`response
`
`1109
`
`Set diameter from response
`
`
`
`Readytoconnect a||Addneighbor||
`
`
`
`
`
`Nt
`
`111
`
`1112
`
`1113
`
`AB-AB 000019
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 21 of 351 PageID #: 40353
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 21 of 351 PagelD #: 40353
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 18 of 39
`
`US 6,701,344 BL
`
`heck for externa
`
`ca—‘
`1201
`
`Answer
`
`Fig. 12
`S
`
`
`
`1202er
`
`
`
`Receive external message
`
` ype = = seeking
`
`connectioncall
`
`Y
`
`1205
`
`Send external message
`
`\ 1
`
`206
`
`207
`
`Add other as fellow seeker
`
`Return
`
`AB-AB 000020
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 22 of 351 PageID #: 40354
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 22 of 351 PagelD #: 40354
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 19 of 39
`
`US 6,701,344 BL
`
`Achieve connection
`
`
`
`1301
`Connection - state = fully
`connected
`
`1302
`
`Notify fellow seekers
`
`
`
`
`
`
`Fig. 13
`
`AB-AB 000021
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 23 of 351 PageID #: 40355
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 23 of 351 PagelD #: 40355
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 20of 39
`
`US 6,701,344 BL
`
`Fig. 1
`
`
`1401
`Pick up and receive
`
`1415
`
`1402
`
`1416
`
`Message
`
`N
`
`Hang up
`
`1404
`Handle seeking
`
`
`
`
`1406
`
`Handle connection
`requestcall
`
`1408
`
`Handle edge proposal
`call
`
`Handle port
`connection call
`
`connection call
`
`
`Port connect call
`
`Handleconnected ;
`statement ~ repairstatement |
`
`Connected statement
`
`statement
`
`
`Condition repair
`
`
`Handle condition
`
`AB-AB 000022
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 24 of 351 PageID #: 40356
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 24 of 351 PagelD #: 40356
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 21 of 39
`
`US 6,701,344 BL
`
`Handle seeking
`connection call
`
`
`
`
`connected
`
`
`
`
`
`Set message to indicate
`
`1505
`
`Send external message
`
`Fig. 15
`
`1504
`Add other as fellow
`seeking process
`
`AB-AB 000023
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 25 of 351 PageID #: 40357
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 25 of 351 PagelD #: 40357
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 22 of 39
`
`US 6,701,344 BL
`
`andle connection
`requestcall
`
`1601
`
`N
`
`60
`
`1603
`
`Set newcomer's
`holes_to_expect
`1604
`Set diameter estimate in
`response
`508
`Set ready in response
`
`2) 06
`Sent external message
`connect request resp.
`4607
`
`Set newcomer's
`holesto_fill
`608
`
`Ready
`
`1611
`
`Ne
`Hang up
`
`Return
`
`.
`
`Fig. 16
`
`i
`
`Add neighbor
`
`Newcomer's
`holes_to_fill --
`
`1609
`i
`
`1610
`
`ole = = 0 or
`
`diameter > 1
`1612
`
`
`
`
`—i Fillhole(requestor) i
`
`1615
`
`Holesto fill - = Z
`
`617
`
`AB-AB 000024
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 26 of 351 PageID #: 40358
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 26 of 351 PagelD #: 40358
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 23 of 39
`
`US 6,701,344 BL
`
`Add neighbor
`
`1701
`
`Identifies calling party
`
`1702
`Sets neighbor to
`messages pending
`
`EFig. 17
`
`.
`
`;
`
`yY
`
`onnection_state =
`
`703
`a
`.
`1704
`<Seeking connectio | partiallyconnected
`
`Nk
`
`1705
`Add as neighbor
`
`1706
`Install interal dispatcher
`for new neighbor
`
`
`
`1707
`
`1708
`
`
`
`WO
`
`
`
`
`4709
`
`Holes = =
`expected hole
`
`Y
`
`Nk
`
`1711
`
`171
`Purge pending edges
`
`Y
`
`ala
`
`AB-AB 000025
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 27 of 351 PageID #: 40359
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 27 of 351 PagelD #: 40359
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 24 of 39
`
`US 6,701,344 BL
`
`Forward connection
`edge search
`
`requestor
`distance remaining
`
`Fig. 18
`
`
`
`
`
`
`
`neighbors
`>)
`
`neighbor =
`requestor
`
`it
`
`1808
`
`Note connection edge
`search call
`
`selected
`
`N
`
`Send internal message
`
`4807
`
`¥
`
`AB-AB 000026
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 28 of 351 PageID #: 40360
`Page 28 of 351 PagelD #: 40360
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 25 of 39
`
`US 6,701,344 BL
`
`Handle edge
`proposalcall
`
`in message
`out message
`
`Fig. 19
`
`
`
`N
`
`4903
`
`create edge (pending)
`
`
`
`
`proposed
`
`
`neighbors
`1914
`pending
`
`N
`
`Send external message
`
`1907
`
`Send external message
`
`1912
`Holes odd
`
`N
`
`1908
`
`N
`
`Y
`
`1913
`4909
`Fill holil Add edgeaspending
`
`Y
`
`.
`
`|
`
`Add neighbor
`
`1910
`
`;
`
`AB-AB 000027
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 29 of 351 PageID #: 40361
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 29 of 351 PagelD #: 40361
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 26 of 39
`
`US 6,701,344 BL
`
`Handle port
`
`
`
`
`
`
`
`
`connection call
`neighbor
`(point-connect-resp, ok)
`
`
`Send external message
`
` Caller is not
`(point-connect-resp
`
`not ok)
`
`
`Send external message
`
`
`
`2006
`
`/
`
`2008
`
`|
`Addneighbor
`/ Connectrequest |
`
`
`AB-AB 000028
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 30 of 351 PageID #: 40362
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 30 of 351 PagelD #: 40362
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 27 of 39
`
`US 6,701,344 BL
`
`
`
`
`Handle connection
`ports search edit
`
`Fill hole
`
`Return
`
`AB-AB 000029
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 31 of 351 PageID #: 40363
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 31 of 351 PagelD #: 40363
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 28 of 39
`
`US 6,701,344 BL
`
`Fig. 33
`
`Internal
`dispatcher
`
`2201
`Received internal message
`2202
`
`Assess diameter
`
`
`This
`
`process = =
`
`
`
`
`
`Type
`= = broadcast
`
`
`Insert message into
`pending connection buffer
`
`2007
`:
`Handle shutdown
`
`Y
`
`
`2206
`a Type
`
`== shutdown
`statement TO statement |
`
`Nie
`
`connection bufferLz,
`
`
`
`Y
`
`Pending
`
`
`
`message queue
`
`YR
`
`Receive response (
`
`)
`
`AB-AB 000030
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 32 of 351 PageID #: 40364
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 32 of 351 PagelD #: 40364
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 29 of 39
`
`US 6,701,344 BL
`
`Handle broadcast
`message
`
`message
`
`origin
`from neighbor
`
`Fig. 23
`
`
`
`AB-AB 000031
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 33 of 351 PageID #: 40365
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 33 of 351 PagelD #: 40365
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 30 of 39
`
`US 6,701,344 BL
`
`.
`Fig. 24
`
`Distribute
`broadcast message
`
`message
`
`from neighbor
`
`All neighbor
`
`selected
`
`
`
`2403
`
`Send internal
`message
`
`AB-AB 000032
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 34 of 351 PageID #: 40366
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 34 of 351 PagelD #: 40366
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 31 of 39
`
`US 6,701,344 BL
`
`Handle connection
`for search
`
`from neighbor
`message
`
`.
`Fig. 26
`
`2604
`
`| Courtneighbor
`
`I
`
`2601
`
`Distribute internal
`
`602
`
`Y
`
`
`603
`
`
`Is requestor
`a neighbor
`
`
`N
`
`605
`
`enerate
`condition check
`message w/neighbors
`
`
`
`AB-AB 000033
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 35 of 351 PageID #: 40367
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 35 of 351 PagelD #: 40367
`
`U.S. Patent
`
`Mar. 2, 2004
`
`Sheet 32 of 39
`
`US 6,701,344 BL
`
`Court neighbor
`
`Prospect
`
`Fig. 27
`
`04
`
` Is prospect
`
`a neighbor
`
`N
`
`2702
`
`Dial prospect
`
`703
`
`N
`
`
`
`
`|
`
`Send and receive
`external message
`
`I
`
`Addneighbor
`
`2706
`
`Hangup prospect
`
`AB-AB 000034
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 36 of 351 PageID #: 40368
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 36 of 351 PagelD #: 40368
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 33 of 39
`
`US 6,701,344 BL
`
`Handle connection
`edge search call
`
`from neighbor
`message
`
`
`801
` Not
`
`
`my message 11
`
`holes >= Z
`
`
`
`
`Fill hole (self}
`
`2815
`
`-
`end interna
`message (from
`neighbor, ack
`
`
`
`
`connection second
`Remaining
`distance > 0
`edge (requestor
`
`remaining dist -1)
`
`
`
`
`
`connection edge
`
`search (requestor,
`
`
`0G
`
`2806
`
`W
`
`2807
`
`Send and receive
`
`external message
`
`AB-AB 000035
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 37 of 351 PageID #: 40369
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 37 of 351 PagelD #: 40369
`
`U.S. Patent
`
`Fig. 29
`
`Mar.2, 2004
`
`Sheet 34 of 39
`
`US 6,701,344 BL
`
`from neighbor message
`
`Handle edge search
`
`origin
`
`AB-AB 000036
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 38 of 351 PageID #: 40370
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 38 of 351 PagelD #: 40370
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 35 of 39
`
`US 6,701,344 BL
`
`Fig. 30
`
`message
`
`
`
`
`Generate internal
`message
`
`Set message sequence
`
`AB-AB 000037
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 39 of 351 PageID #: 40371
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 39 of 351 PagelD #: 40371
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 36 of 39
`
`US 6,701,344 BL
`
`Acquire message
`
`message
`
`
`
`
`
`Message
`retrieved
`
`
`
`
`Return false
`
`
`
`Return true
`
`AB-AB 000038
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 40 of 351 PageID #: 40372
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 40 of 351 PagelD #: 40372
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 37 of 39
`
`US 6,701,344 BL
`
`‘Handle condition check
`
`
`
` Sameset of
`
`neighbors
`
`3205
`
`elect a neighbor
`
`Set up message withlist
`of sending process
`
`of neighbors
`not my neighbor
`
`
`
`to selected neighbor
`
`Send internal message
`
`Send external message
`
`
`
`AB-AB 000039
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 41 of 351 PageID #: 40373
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 41 of 351 PagelD #: 40373
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 38 of 39
`
`US 6,701,344 BL
`
`Handle condition
`
`repair statement
`
`Fig, 33
`
`
`
`
` Select a neighbor not
`
`involved in condition
`
`Removeselected
`neighbor
`
`AB-AB 000040
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 42 of 351 PageID #: 40374
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 42 of 351 PagelD #: 40374
`
`U.S. Patent
`
`Mar.2, 2004
`
`Sheet 39 of 39
`
`US 6,701,344 BL
`
`ae
`Handle condition
`
`Fig. 34
`
`double check
`neighbors
`
`
`
` Sameset of
`
`
`Send internal message.
`to-from neighbor
`
`Send internal message
`
`AB-AB 000041
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 43 of 351 PageID #: 40375
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 43 of 351 PagelD #: 40375
`
`US 6,701,344 B1
`
`1
`DISTRIBUTED GAME ENVIRONMENT
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`
`
`This application is related to U.S. patent application Ser.
`No. 09/629,576, entitled “BROADCASTING
`NETWORK,”filed on Jul. 31, 2000; U.S. patent application
`Ser. No, 09/629,570, entitled “JOINING A BROADCAST
`CHANNEL,”filed on Jul. 31, 2000; U.S. patent application ,
`Ser. No. 09/629,577, “LEAVING A BROADCAST
`CHANNET.,”filed on Jul. 31, 2000; U.S. patent application
`Ser. No. 09/629,575, entitled “BROADCASTING ON A
`BROADCAST CHANNEL,” filed on Jul. 31, 2000; U.S.
`patent application Ser. No. 09/629,572, entitled “CON-
`TACTING A BROADCAST CHANNEL,” filed on Jul. 31,
`2000; U.S. patent application Ser. No. 09/629,023, entitled
`“DISTRIBUTED AUCTION SYSTEM,”filed on Jul. 31,
`2000; U.S. patent application Ser. No. 09/629,043, entitled
`“AN INFORMATION DELIVERYSERVICE,”filed on Jul.
`31, 2000; and U.S. patent application Ser. No. 09/629,024,
`entitled “DISTRIBUTED CONFERENCING SYSTEM,”
`filed on Jul. 31, 2600, the disclosures of which are incor-
`porated herein by reference.
`TECHNICAL FIELD
`
`3S
`
`‘The described technologyrelates generally to a computer
`network and more particularly, to a broadcast channelfor a
`subset of a computers of an underlying network.
`BACKGROUND
`
`There are a wide variety of computer network communi-
`cations techniques such as point-to-point network protocols,
`client/server middleware, multicasting network protocols,
`andpeer-to-peer middleware. Each of these communications
`techniques have their advantages and disadvantages, but
`none is particularly well suited to the simultaneous sharing
`of information among computers that are widely distributed.
`For example, collaborative processing applications, such as
`a network meeting programs, have a need to distribute
`information in a timely mannerto all participants who may
`be geographically distributed.
`The point-to-point network protocols, such as UNIX
`pipes, TCP/IP, and UDP, allowprocesses on different com-
`puters to communicate via point-to-point connections. The
`interconnection of all participants using point-to-point
`connections, while theoretically possible, does not scale well
`as a oumber of participants grows. For example, each
`participating process would need to manage its direct con-
`nections to all other participating processes. Programmers,
`however,findit very difficult to manage single connections,
`and management of multiple connections is much more
`complex. In addition, participating processes may be limited
`to the number of direct connections that they can support.
`This limits the number ofpossible participants in the sharing
`of information.
`
`The client/server middleware systems provide a server
`that coordinates the communications between the various
`clients who are sharing the information. The server functions
`as a central authority for controlling access to shared
`resources. Examples of client/server middleware systems
`include remote procedure calls (“RPC”), database servers,
`and the common object
`request broker architecture
`(CORBA). Client/Server middleware systems are not par-
`ticularly well suited to sharing of information among many
`participants. Io particular, when a client stores information
`
`iA
`
`a
`
`maon
`s
`
`D>a
`
`2
`to be shared at the server, each other client would need to
`poll the server to determine that new information is being
`shared. Such polling places a very high overhead on the
`communications network. Altcrnativcly, cach clicnt may
`register a callback with the server, which the server then
`invokes when new information is available to be shared.
`Such a callback technique presents a performance bottleneck
`because a single server needs to call back to each client
`whenever new information is to be shared. In addition, the
`reliability of the entire sharing of information depends upon
`the reliability of the single server. Thus, a failure at a single
`computer (.e., the server) would prevent communications
`between anyof the clients.
`The multicasting network protocols allow the sending of
`broadcast messages to multiple recipients of a network. The
`current implementations of such multicasting network pro-
`tocols tend to place an unacceptable overheadon the under-
`lying network. For example, UDP multicasting would
`swamp the Internet when trying to locate all possible par-
`ticipants. IP multicasting has other problems that include
`needing special-purpose infrastructure (e.g., routers) to sup-
`port the sharing of informationefficiently.
`The peer-to-peer middleware communications systems
`rely on a multicasting network protocol or a graph of
`point-to-point network protocols. Such peer-to-peer middle-
`ware is provided by the T.120 Internet standard, which is
`used in such products as Data Connection’s D.C.-share and
`Microsoft’s NetMeeting. These peer-to-peer middleware
`systems rely upon a user to assemble a point-to-point graph
`of the connections used for sharing the information. Thus,it
`is neither suitable nor desirable to use peer-to-peer middle-
`ware systems when more than a small number of partici-
`pants is desired. In addition, the underlving architecture of
`the T.120 Internet standard is a tree structure, which relies on
`the root node of the tree for reliability of the entire network.
`That is, cach message must pass through the root node in
`order to be received byall participants.
`Tt would be desirable to have a reliable communications
`network that is suitable for the simultaneous sharing of
`information among a large number of the processes that are
`widely distributed.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`VIG. 1 illustrates a graph that is 4-regular and 4-connected
`which represents a broadcast channel.
`FIG, 2 illustrates a graph representing 20 computers
`connected fo a broadcast channel.
`FIGS. 3A and 3B illustrate the process of connecting a
`new computer Z to the broadcast channel.
`FIG, 4Aillustrates the broadcast channel of FIG. 1 with
`an added computer.
`FIG.4B illustrates the broadcast channel of FIG. 4A with
`an added computer.
`FIG. 4C also illustrates the broadcast channel of FIG. 4A
`with an added computer.
`FIG.5A illustrates the disconnecting of a computer from
`the broadcast channel in a planned manner.
`FIG. SB illustrates the disconnecting of a computer from
`the broadcast channel in an unplanned manner.
`FIG. SCillustrates the neighbors with empty ports con-
`dition.
`FIG. 3D illustrates two computers that are not neighbors
`who now have empty ports.
`FIG. 5E illustrates the neighbors with empty ports con-
`dition in the small regime.
`
`
`
`AB-AB 000042
`
`

`

`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 44 of 351 PageID #: 40376
`Case 1:16-cv-00454-RGA Document 475-1 Filed 04/24/18 Page 44 of 351 PagelD #: 40376
`
`US 6,701,344 B1
`
`4
`DETAILED DESCRIPTION
`
`technique in which a broadcast channel
`A broadcast
`overlays a point-to-point communications nctwork is pro-
`vided. The broadcasting of a message over the broadcast
`channelis effectively a multicast to those computers of the
`network that are currently connected to the broadcast chan-
`nel. In one embodiment, the broadcast technique provides a
`logical broadcast channel to which host computers through
`their executin