(12)
`
`United States Patent
`H0lt et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,829,634 B1
`Dec. 7, 2004
`
`US006829634B1
`
`(54) BROADCASTING NETWORK
`
`(75) Inventors: Fred B. Holt, Seattle, WA (US); Virgil
`E_ Bourassa Bellevue WA (Us)
`’
`’
`-
`.
`-
`(73) Assignee. The Boeing Company, Seattle, WA
`(Us)
`
`1/1999 Mairs et 81.
`5,864,711 A
`2/1999 Schmidt et al.
`5,867,660 A
`2/1999 Butman et a1~
`5,867,667 A
`2/1999 Bracho et al.
`5,870,605 A
`2/1999 Mairs e161.
`5,874,960 A
`5/1999 Wilf et al.
`5,899,980 A
`5/1999 Onweller
`5,907,610 A
`7/1999 Morita
`5,928,335 A
`8 1999 B 11
`t
`5935215 A
`92999 Nielseena
`5:948j054 A
`9/1999 Batty et aL
`5,949,975 A
`5,953,318 A * 9/1999 Nattkemper et al. ...... .. 370/236
`5,956,484 A
`9/1999 Rosenberg et al.
`5,974,043 A 10/1999 Solomon
`5,987,506 A 11/1999 Carter et al.
`_
`_
`(List continued on neXt page.)
`
`l.
`
`OTHER PUBLICATIONS
`Alagar, S. and Venkatesan, S., “Reliable Broadcast in
`Mobile Wireless Networks,” Department of Computer Sci
`ence, University of Texas at Dallas,
`Communica
`tions Conference, 1995, MILCOM ’95 Conference Record,
`IEEE San Diego, California, Nov. 5—8, 1995 (pp. 236—240).
`
`(List continued on neXt page.)
`
`P’W’y Examl'7er—H°Sam Alam
`Assistant Examzner—Young N. Won
`(74) Attorney, Agent, or Firm—Perkins Coie LLP
`
`ABSTRACT
`(57)
`A technique for broadcasting data across a network is
`H d An .
`.
`t.
`t. .
`t
`d d t
`t
`th
`prov1~e .
`origma mg par 1c1pan sen s ‘a a o ano er
`participant, WhlCh in turn sends the data that 1trece1ves from
`a neighbor participant to its other neighbor participants.
`Communication in the broadcast network is controlled by a
`contact module that locates the neighbor participants to
`which the seeking participant can be connected and by a join
`module that establishes the connection between the neighbor
`participants and the seeking participant. Data is numbered
`sequentially so that data that is received out of order can be
`queued and rearranged
`'
`
`24 Claims, 39 Drawing Sheets
`
`( 4 ) Notice:
`
`.
`
`.
`
`.
`
`.
`
`.
`
`SubJect' to any disclaimer, the term of this
`patent is extended or adJusted under 35
`U.S.C. 154(b) by 737 days'
`
`(21) Appl. No.. 09/629,576
`.
`
`22 Filed:
`£51; I t C] 7
`
`Jul. 31 2000
`’
`
`G06F 15/16
`
`n .
`
`.
`
`.............................................. ..
`
`(52) US. Cl. ..................... .. 709/204; 709/205; 709/203;
`709/243; 709/201; 709/238; 709/319; 709/225;
`370/236
`
`_
`Fleld of Search ............................... ..
`
`709/238, 319
`
`(56)
`
`References Cited
`
`US. PATENT DOCUMENTS
`4,912,656 A
`3/1990 Cain et al.
`5,056,085 A 10/1991 Vu
`5,309,437 A
`5/1994 Perlman et a1_
`5,426,637 A
`6/1995 Derby et al.
`5,535,199 A
`7/1996 Amri et al.
`55683487 A 10/1996 Sltbon et a1‘
`5,636,371 A
`6/1997 Yu
`5 673 265 A
`9/1997 Gupta et a1‘
`5’696’903 A 12/1997 Mahany
`5:732j074 A
`3/1998 Spam et a1_
`5,732,219 A
`3/1998 Blumer et a1_
`5,734,865 A
`3/1998 Yu
`5,737,526 A
`4/ 1998 Periasamy et al.
`5,754,830 A
`5/1998 Butts et 91-
`57617425 A
`6/1998 M111“
`5,764,756 A
`6/1998 Onweller
`5,790,548 A
`8/1998 SistaniZadeh et al.
`5,790,553 A
`8/1998 Deaton, Jr. et al.
`5,799,016 A
`8/1998 Onweller
`5,802,285 A
`9/1998 Hirviniemi
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 1 of 56
`
`

`
`US 6,829,634 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`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.
`6,199,116 B1
`3/2001 May et al.
`6,216,177 B1
`4/2001 Mairs et al.
`6,223,212 B1
`4/2001 Batty et al.
`6,243,691 B1
`6/2001 Fisher et al.
`6,268,855 B1
`7/2001 Mairs et al.
`6,271,839 B1
`8/2001 Mairs et al.
`6,285,363 B1
`9/2001 Mairs et al.
`6,304,928 B1
`10/2001 Mairs et al.
`6,611,872 B1 * 8/2003 McCanne ................. .. 709/238
`
`OTHER PUBLICATIONS
`
`International Search Report for The Boeing Company, Inter
`national Patent Application No. PCT/US01/24240, Jun. 5,
`2002 (7 pages).
`U.S. patent application Ser. No. 09/629,570, Bourassa et al.,
`?led Jul. 31, 2000.
`U.S. patent application Ser. No. 09/629,577, Bourassa et al.,
`?led Jul. 31, 2000.
`U.S. patent application Ser. No. 09/629,575, Bourassa et al.,
`?led Jul. 31, 2000.
`U.S. patent application Ser. No. 09/629,572, Bourassa et al.,
`?led Jul. 31, 2000.
`U.S. patent application Ser. No. 09/629,023, Bourassa et al.,
`?led Jul. 31, 2000.
`U.S. patent application Ser. No. 09/629,043, Bourassa et al.,
`?led Jul. 31, 2000.
`U.S. patent application Ser. No. 09/629,024, Bourassa et al.,
`?led Jul. 31, 2000.
`U.S. patent application Ser. No. 09/629,042, Bourassa et al.,
`?led 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) http://www.open2p.com/
`1pt/ .
`.
`. [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/1pt .
`.
`. [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/1pt .
`.
`. [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 Microsysterns, Aug. 1995 (20 pages) Internet
`RFC/STD/FYI/BCP Archives http://www.faqs.org/rfcs/
`rfc1832.html [Accessed Jan. 29, 2002].
`ADatabeam Corporate White Paper, “A Primer on the T120
`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://www.hill.com/library/publications/t .
`.
`. [Accessed
`Jan. 29, 2002].
`Bondy, J .A., and Murty, U.S.R., “Graph Theory with Appli
`cations,” Chapters 1—3 (pp. 1—47), 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
`245), 1990, The MIT Press, Cambridge, Massachu
`setts, McGraw—Hill Book Company, New York.
`The Common Object Request Broker: Architecture and
`Speci?cation, Revision 2.6, Dec. 2001, Chapter 12 (pp.
`12—1—12—10), 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 on the Problems of Distributed Systems,”
`http://www.dcs.warwick.ac.u .
`.
`. [Accessed Jan. 29, 2002].
`
`* cited by examiner
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 2 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 1 0f 39
`
`US 6,829,634 B1
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 3 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 2 0f 39
`
`US 6,829,634 B1
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 4 of 56
`
`

`
`U.S. Patent
`
`Dec. 7 2004
`
`Sheet 3 0f 39
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 5 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 4 0f 39
`
`US 6,829,634 B1
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 6 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 5 0f 39
`
`US 6,829,634 B1
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 7 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 6 6f 39
`
`US 6,829,634 B1
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 8 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 7 0m
`
`US 6,829,634 B1
`
`0:
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 9 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 8 m9
`
`US 6,829,634 B1
`
`55
`33
`[3-4
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 10 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 9 0f 39
`
`US 6,829,634 B1
`
`Fig. 5 C
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 11 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 10 0f 39
`
`US 6,829,634 B1
`
`:0
`
`E
`.910
`
`II-
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 12 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 11 0f 39
`
`US 6,829,634 B1
`
`Q
`
`(
`
`‘In
`
`D
`
`<
`
`Q
`5..“
`
`5"!
`21°
`LL
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 13 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 14 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 13 0f 39
`
`US 6,829,634 B1
`
`CON
`
`mom
`
`_
`
`hob
`
`
`
`8:225: iron
`GEEK...“ _ m2: m zoom duo-E00
`
`29;:
`
`NE m3 5N
`
`
`
`203%“. .‘
`
`. “35m
`
`
`. H mac:
`
`Q 0655
`£825 v
`
`Z mm:- m
`
`_ Oh 332m
`
`158-: t K
`
`m2. N aa?em e33
`
`
`1585 won 0mm.“ 0532:
`
`. ms. #2.
`
`NON mom
`
`2. mg m Guava.
`
`oEEE “8560
`
`k .ME
`
`g2
`
`85%2
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 15 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 14 0f 39
`
`US 6,829,634 B1
`
`(Channel Type,
`Channel Instance,
`Connect Aux Info)
`
`Fig. 8
`
`(
`
`Connect
`
`Open call in port
`
`801
`
`802
`
`Set connect-time
`
`803
`Seek portal ~ computer
`(chamel type channel
`instance)
`
`806
`
`Achieve connection
`
`807
`Install external dispatcher
`
`Install external dispatcher
`
`809
`
`Connect request
`
`l
`
`Return (true)
`
`>
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 16 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 15 0f 39
`
`US 6,829,634 B1
`
`Seek Pom!
`°°mputer
`
`Channel Type
`Channel Instance
`
`902
`
`Select next depth
`
`All depths selected
`
`904
`'1 N
`Select next portal computer
`
`Fig. 9
`
`Dial portal computer
`
`907
`
`Y
`
`908
`
`Contact process
`
`909
`I
`Hang up selected portal
`computer
`
`911
`Check for external
`call
`
`1
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 17 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 16 0f 39
`
`US 6,829,634 B1
`
`( Contact process )
`
`1001
`Send external message
`
`1 002
`Receive enema] message
`
`1 0
`
`1005
`Add as connected portal
`computer
`
`1006
`Add as fellow seeking
`computer
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 18 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 17 0f 39
`
`US 6,829,634 B1
`
`Connect request
`
`Dial call in port of portal
`computer
`
`Send external message
`1
`1106
`Receive enema! message
`
`1107
`
`Success
`
`1108
`Y
`Set expect holes from
`response
`1109
`1
`Set diameter from response
`
`1102
`
`1 1 12
`Add neighbor
`J
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 19 of 56
`
`

`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 18 0f 39
`
`US 6,829,634 B1
`
`heck for extem
`call
`
`Answer
`
`1201
`
`Fig. 12
`
`1 202
`
`\
`
`Y
`
`1 203
`Receive external message I
`
`Send external message
`
`‘
`
`206
`
`Y
`
`1 207
`Add other as fellow seeker I
`
`Return
`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 20 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 21 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 22 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 23 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 24 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 25 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 26 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 27 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 28 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 29 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 30 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 31 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 32 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 33 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 34 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 35 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 36 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 37 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 38 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 39 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 40 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 41 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 42 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 43 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 44 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 45 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 46 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 47 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 48 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 49 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 50 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 51 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 52 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 53 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 54 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 55 of 56
`
`

`
`IPR2016-00726-ACTIVISION, EA,
`TAKE-TWO, 2K, ROCKSTAR, Ex. 1012, p. 56 of 56