Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 1 of 190 PageID #: 42494
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 1 of 190 PagelD #: 42494
`
`EXHIBIT 63
`EXHIBIT 63
`
`
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 2 of 190 PageID #: 42495
`eeeelNTTTT
`
`US006829634B1
`
`(12) United States Patent
`US 6,829,634 Bl
`(10) Patent No.:
`
`(45) Date of Patent: Dec. 7, 2004
`Holt et al.
`
`5,864,711 A
`5,867,660 A
`5,867,667 A
`5,870,605 A
`5,874,960 A
`5,899,980 A
`5,907,610 A
`5,928,335 A
`5,935,215 A
`5,948,054 A
`5,949,975 A
`5,953,318 A *
`5,956,464 A
`5,974,043 A
`5,987,506 A
`
`1/1999 Mairs et al.
`2/1999 Schmidt et al.
`2/1999 Butman etal.
`2/1999 Brachoet al.
`2/1999 Mairs et al.
`§/1999 Wilfet al.
`5/1999 Onweller
`7/1999 Morita
`8/1999 Bell et al.
`9/1999 Nielsen
`9/1999 Battyet al.
`9/1999 Nattkemper et al.
`9/1999 Rosenberg et al.
`10/1999 Solomon
`11/1999 Carter et al.
`
`(List continued on next page.)
`OTHER PUBLICATIONS
`
`......... 370/236
`
`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 °*95 Conference Record,
`IEEE San Diego, California, Nov. 5-8, 1995 (pp. 236-240).
`
`(List continued on next page.)
`
`Primary Examiner—Hosain Alam
`Assistant Examiner—Young N. Won
`(74) Attorney, Agent, or Firm—Perkins Coie LLP
`
`(57)
`
`ABSTRACT
`
`A technique for broadcasting data across a network is
`provided. An originating participant sends data to another
`participant, whichin turn sends the data that it receives 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 connectedandby ajoin
`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
`
`(54)
`
`(75)
`
`(73)
`
`BROADCASTING NETWORK
`
`Inventors: Fred B. Holt, Seattle, WA (US); Virgil
`E. Bourassa, Bellevue, WA (US)
`
`Assignee: The Boeing Company, Seattle, WA
`(US)
`
`Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 737 days.
`
`Appl. No.: 09/629,576
`
`Filed:
`
`Jul. 31, 2000
`
`Int. C17oe GO6F 15/16
`ULS. Ch. oo... 709/204; 709/205; 709/203;
`709/243; 709/201; 709/238; 709/319; 709/225;
`370/236
`Field of Search 0... eee 709/106, 201,
`709/238, 319
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`
`
`3/1990 Cain ct al.
`10/1991 Vu
`5/1994 Perlman et al.
`6/1995 Derbyet al.
`7/1996 Amiri et al.
`10/1996 Sitbon et al.
`6/1997 Yu
`9/1997 Guptaet al.
`12/1997 Mahany
`3/1998 Spaur et al.
`3/1998 Blumer et al.
`3/1998 Yu
`4/1998 Periasamy etal.
`5/1998 Butts et al.
`6/1998 Miller
`6/1998 Onweller
`8/1998 Sistanizadeh et al.
`8/1998 Deaton, Jr. et al.
`8/1998 Onweller
`9/1998 Hirviniemi
`
`4,912,656 A
`5,056,085 A
`5,309,437 A
`5,426,637 A
`5,535,199 A
`5,568,487 A
`5,636,371 A
`5,673,205 A
`5,696,903 A
`5,732,074 A
`5,732,219 A
`5,734,865 A
`5,737,526 A
`5,754,830 A
`5,761,425 A
`5,764,756 A
`5,790,548 A
`5,790,553
`5,799,016
`5,802,285
`
`AAA
`
`
`
`AB-AB 001086
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 3 of 190 PageID #: 42496
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 3 of 190 PagelD #: 42496
`
`US 6,829,634 BI
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`
`
`The O’Reilly Network, “Gnutella: Alive, Well, and Chang-
`ing Fast,” Jan. 25, 2001 (5 pages) hittp://www.open2p.com/
`12/1999 Tlouston et al.
`6,003,088 A
`ipt/.. . [Accessed Jan. 29, 2002].
`1/2000 Blackshearet al.
`6,013,107 A
`Oram, Andy, “Gnutella and Freenet Represents True Tech-
`2/2000 Ratcliff et al.
`6,023,734 A
`nological Innovation,” May 12, 2000 (7 pages) The O’Reilly
`2/2000 Smigaet al.
`6,029,171 A
`2/2000 Mairs et al.
`6,032,188 A
`Network http://www.oreillynet.com/Ipt .
`.
`. [Accessed Jan.
`3/2000 Ishikawa
`6,038,602 A
`29, 2002].
`A
`4/2000 Thorne et al.
`6,047,289
`>
`Internetworking Technologies Handbook, Chapter 43 (pp.
`7/2000 Grayet al.
`6,094,676
`43-1-13-16).
`3/2001 Mayet al.
`6,199,116 BL
`4/2001 Mairs etal.
`6,216,177 Bl
`Oram, Andy, “Peer-to-Peer Makes the Internet Interesting
`4/2001 Batty et al.
`6,223,212 Bl
`Again,” Sep. 22, 2000 (7 pages) The O’Reilly Network
`6/2001 Fisher et al.
`6,243,691 Bl
`http://linux.oreillynet.com/1pt .
`.
`. [Accessed Jan. 29, 2002].
`7/2001 Mairs ctal.
`6,268,855 Bl
`Monte, Richard, “The Random Walk for Dummies,’MIT
`8/2001 Mairs etal.
`6,271,839 Bl
`Undergraduate Journal of Mathematics (pp. 143-148).
`9/2001 Mairs et al.
`6,285,363 Bl
`10/2001 Mairs etal.
`6,304,928 Bl
`Srinivasan, R., “XDR: External Data Representation Stan-
`teeeeessee 709/238
`8/2003 McCanne........
`6,611,872 Bl *
`dard,” Sun Microsystems, Aug. 1995 (20 pages) Internet
`RFC/STD/FYIV/BCP Archives_http://www.faqs.org/rfcs/
`OTHER PUBLICATIONS
`rfc1832.html [Accessed Jan. 29, 2002].
`ADatabeam Corporate White Paper, “A Primer on the T.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://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 (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.
`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.des.warwick.ac.u .
`.
`. [Accessed Jan. 29, 2002].
`
`
`
`International Search Report for The Boeing Company,Inter-
`national Patent Application No. PCT/US01/24240, Jun. 5,
`2002 (7 pages).
`US. patent application Ser. No. 09/629,570, Bourassa et al.,
`filed Jul. 31, 2000.
`US. 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.
`US. patent application Ser. No. 09/629,023, Bourassa et al.,
`filed Jul. 31, 2000.
`US. patent application Ser. No. 09/629,043, Bourassa et al.,
`filed Jul. 31, 2000.
`US. patent application Ser. No. 09/629,024, Bourassa et al.,
`filed Jul. 31, 2000.
`US. patent application Ser. No. 09/629,042, 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).
`
`
`
`* cited by examiner
`
`AB-AB 001087
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 4 of 190 PageID #: 42497
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 4 of 190 PagelD #: 42497
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 1 of 39
`
`US 6,829,634 B1
`
`a
`
`<
`
`Prey
`
`ube
`
`AB-AB 001088
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 5 of 190 PageID #: 42498
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 5 of 190 PagelD #: 42498
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 2 of 39
`
`US 6,829,634 B1
`
`
`
`AB-AB 001089
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 6 of 190 PageID #: 42499
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 6 of 190 PagelD #: 42499
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 3 of 39
`
`US 6,829,634 B1
`
`3B
`ig.
`
`Fig.3A
`
`AB-AB 001090
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 7 of 190 PageID #: 42500
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 7 of 190 PagelD #: 42500
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 4 of 39
`
`US 6,829,634 B1
`
`
`
`AB-AB 001091
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 8 of 190 PageID #: 42501
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 8 of 190 PagelD #: 42501
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 5 of 39
`
`US 6,829,634 B1
`
`rig.4B
`
`F
`
`AB-AB 001092
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 9 of 190 PageID #: 42502
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 9 of 190 PagelD #: 42502
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 6 of 39
`
`US 6,829,634 B1
`
`<x
`
`a
`
`X
`3p
`Ry
`
`LL
`
`AB-AB 001093
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 10 of 190 PageID #: 42503
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 10 of 190 PagelD #: 42503
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 7 of 39
`
`US 6,829,634 B1
`
`
`
`AB-AB 001094
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 11 of 190 PageID #: 42504
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 11 of 190 PagelD #: 42504
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 8 of 39
`
`US 6,829,634 B1
`
`ig.5B
`
`AB-AB 001095
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 12 of 190 PageID #: 42505
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 12 of 190 PagelD #: 42505
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 9 of 39
`
`US 6,829,634 B1
`
`B
`
`5C
`ig.
`
`AB-AB 001096
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 13 of 190 PageID #: 42506
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 13 of 190 PagelD #: 42506
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 10 of 39
`
`US 6,829,634 B1
`
`oO
`
`<
`
`m
`be
`
`u.
`
`AB-AB 001097
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 14 of 190 PageID #: 42507
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 14 of 190 PagelD #: 42507
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 11 of 39
`
`US 6,829,634 B1
`
`AB-AB 001098
`
`Ry
`wy
`x
`
`a S
`
`e
`he
`
`<
`
`mo
`
`<
`
`a
`
`oO
`
`Q
`
`QO
`
`oO
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 15 of 190 PageID #: 42508
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 15 of 190 PagelD #: 42508
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 12 of 39
`
`US 6,829,634 B1
`
`a4)
`
`
`Application2(channel
`
`typechannelinstance)
`
`ig.6
`
`AB-AB 001099
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 16 of 190 PageID #: 42509
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 16 of 190 PagelD #: 42509
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 13 of 39
`
`US 6,829,634 B1
`
`
`
`AB-AB 001100
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 17 of 190 PageID #: 42510
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 17 of 190 PagelD #: 42510
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 14 of 39
`
`US 6,829,634 B1
`
`core
`Channel Instance,
`Connect Aux Info)
`
`Fig. 8
`
`Open call in port
`
`801
`
`802
`
`Set connect-time
`
`803
`Seek portal - computer
`(channel type channel
`instance)
`
`804
`
`Y
`
`806
`
`807
`
`[|
`
`
`|comer|
`
`ae ie
`
`Install external dispatcher
`
`AB-AB 001101
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 18 of 190 PageID #: 42511
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 18 of 190 PagelD #: 42511
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 15 of 39
`
`US 6,829,634 B1
`
`
`
`
`All portal computers
`selected
`
`5
`
`Check for external
`call
`
`
`
`AB-AB 001102
`
`
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 19 of 190 PageID #: 42512
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 19 of 190 PagelD #: 42512
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 16 of 39
`
`US 6,829,634 B1
`
`1001
`
`Send external message
`
`Fig. 10
`
`
`
`
`
`
`
`1002
`
`A
`
`AB-AB 001103
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 20 of 190 PageID #: 42513
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 20 of 190 PagelD #: 42513
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 17 of 39
`
`US 6,829,634 B1 Ready to connect
`
`N
`
`1113
`
`AB-AB 001104
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 21 of 190 PageID #: 42514
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 21 of 190 PagelD #: 42514
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 18 of 39
`
`US 6,829,634 B1
`
`heck for exte:
`call
`
`1201
`
`
`
`
`Fig. 12
`
`AB-AB 001105
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 22 of 190 PageID #: 42515
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 22 of 190 PagelD #: 42515
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 19 of 39
`
`US 6,829,634 B1
`
`1301
`Connection - state = fully
`
`1302
`
`Notify fellow seekers
`
`connected
`
`
`
`
`
`
`Invoke connect call back
`
`
`
`Fig. 13
`
`AB-AB 001106
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 23 of 190 PageID #: 42516
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 23 of 190 PagelD #: 42516
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 20 of 39
`
`US 6,829,634 B1
`
`
`
`
`Handle connection
`request call
`
`Port connect call
`
`
`
`Connected statement
`
`Handle connected
`Statement
`
`
`
`ondition repair
`Handle condition
`
`
`
`
`statement 7 repalrstatement 5
`
`
`
`AB-AB 001107
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 24 of 190 PageID #: 42517
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 24 of 190 PagelD #: 42517
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 21 of 39
`
`US 6,829,634 B1
`
`
`
`
`
`Add other as fellow
`seeking process
`
`1504
`
`AB-AB 001108
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 25 of 190 PageID #: 42518
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 25 of 190 PagelD #: 42518
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 22 of 39
`
`US 6,829,634 B1
`
`50
`
`F;ig. 16
`
`andle connection.
`request call
`
`1601
`
`J Uy
`
`Set n
`holes_to_expect
`
`DU4
`Set diameter estimate in
`response
`
`50
`Set ready in response
`
`OU
`Sent external message
`connect request resp,
`
`0
`
`Set newcomer’
`holesto fill
`
`$
`
`608
`
`|
`
`Add neighbor
`
`a
`
`i
`
`
`
`>=Z
`
`
`
`
`
`
`holes_tofill > 9
`
`Holes to fill - = Z
`
`| Fill hole (requestor) i
`
`AB-AB 001109
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 26 of 190 PageID #: 42519
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 26 of 190 PagelD #: 42519
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 23 of 39
`
`US 6,829,634 B1
`
`Add neighbor
`
`Identifies calling party
`
`Fig. I 7
`
`Sets neighbor to
`messages pending
`
`connectioy
`
`Y
`
`4
`
`Connection_state =
`ertially
`connected
`
`Add as neighbor
`
`UO
`Install interal dispatcher
`for new neighbor
`
`Ur
`
`)
`
`AB-AB 001110
`
`\
`
`Cg>wo
`
` Holes = =
`pected holes
`
`N
`
`707
`
`1711
`
`Purge pending edgeswo
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 27 of 190 PageID #: 42520
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 27 of 190 PagelD #: 42520
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 24 of 39
`
`US 6,829,634 B1
`
`
`
`Fig. 18
`
`Forward connection
`edge search
`
`requestor
`distance remaining
`
`
`
`XY
`
`801
`
`0
`
`
` # of
`neighbors
`>I
`
`
`
`
`
`
`
`
`
`
`
`
`
`mart .
`requestor
`
`tA
`
`Note connection edge
`
`search cal)
`
`
`AB-AB 001111
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 28 of 190 PageID #: 42521
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 28 of 190 PagelD #: 42521
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 25 of 39
`
`US 6,829,634 B1
`
`Handle edge
`proposal call
`
`in message
`
`out message
`
`Send external message
`
`N
`
`,3)
`
`Send external message
`
`1912
`1908
`BeetCReum
`
`c
`
`ry
`
`o
`
`[ame
`
`a
`
`Aadedge uspending
`
`|
`
`Addneighbor
`
`910
`
`|
`
`AB-AB 001112
`
`

`

`
`001
`
`
`
`
`
`Caller is not
`neighbor
`
`200
`Send external message
`(point-connect-resp
`not ok)
`
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 29 of 190 PageID #: 42522
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 29 of 190 PagelD #: 42522
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 26 of 39
`
`US 6,829,634 B1
`
`Fig. 20
`
`Holes > 0
`
` [comesieqet|
`
`
`
`AB-AB 001113
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 30 of 190 PageID #: 42523
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 30 of 190 PagelD #: 42523
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 27 of 39
`
`US 6,829,634 B1
`
`Fill hole
`| portssearchedit
` Distribute internal
`
`message
`
`AB-AB 001114
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 31 of 190 PageID #: 42524
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 31 of 190 PagelD #: 42524
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 28 of 39
`
`US 6,829,634 B1
`
`(aipacer_)
`
`dispatcher
`
`2201
`
`Fig. 2
`
`UZ
`
`= = shutdown
`
`statement
`
`y
`
`:
`Pending
`connection buffer
`
`08
`
`Achieve connection
`
`N
`
`message queue
`
`N
`
`aaydt
`
`AB-AB 001115
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 32 of 190 PageID #: 42525
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 32 of 190 PagelD #: 42525
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 29 of 39
`
`US 6,829,634 B1
`
`Fig. 23
`
`
`
`
`Clear out of order info
`
`4
`
`AB-AB 001116
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 33 of 190 PageID #: 42526
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 33 of 190 PagelD #: 42526
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 30 of 39
`
`US 6,829,634 B1
`
`Fig. 24
`
`message
`
`2401
`
`Select next neighbor
`
`from neighbor
`
`
`AB-AB 001117
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 34 of 190 PageID #: 42527
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 34 of 190 PagelD #: 42527
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 31 of 39
`
`US 6,829,634 B1
`
`Handle connection
`for search
`
`from neighbor
`message
`
`2601
`
`Distribute internal
`message
`
`.
`
`Fip. 26
`
`B02<>
`
`enerate
`condition check
`message w/neighbors
`
`Y
`
`2607
`
`Send internal message
`to requestor
`
`AB-AB 001118
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 35 of 190 PageID #: 42528
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 35 of 190 PagelD #: 42528
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 32 of 39
`
`US 6,829,634 B1
`
`Dial prospect
`
`703
`
`N
`
`Holes > 0
`
`Send and receive
`external message
`
`
`
`
`|
`
`
`
`
`
`
`Add neighbor
`
`[
`
`106
`
`Hang up prospect
`
`
`
`
`AB-AB 001119
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 36 of 190 PageID #: 42529
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 36 of 190 PagelD #: 42529
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 33 of 39
`
`US 6,829,634 B1
`
`|
`
`>
`
`2614
`
`2815
`
`end interna
`
`neighbor, ack
`
`|
`Fillhole (self)
`message(from |
`
` ¥
`external message
`
`
`
`od
`
`)
`
`
`2806
`é
`
`2807
`
`Send and receive
`
`AB-AB 001120
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 37 of 190 PageID #: 42530
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 37 of 190 PagelD #: 42530
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 34 of 39
`
`US 6,829,634 B1
`
`Note connection edge
`search response
`
`905
`
`[esa|
`
`
`
`
`
`
`
`906
`
`Y
`
`2908
`
`ol
`(Fats)
`
`AB-AB 001121
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 38 of 190 PageID #: 42531
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 38 of 190 PagelD #: 42531
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 35 of 39
`
`US 6,829,634 B1
`
`
`
`AB-AB 001122
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 39 of 190 PageID #: 42532
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 39 of 190 PagelD #: 42532
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 36 of 39
`
`US 6,829,634 B1
`
`Fig. 3i
`
`3101
`
`Pop message queue
`
`message
`
`
`AB-AB 001123
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 40 of 190 PageID #: 42533
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 40 of 190 PagelD #: 42533
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 37 of 39
`
`US 6,829,634 B1
`
`d external message
`
`AB-AB 001124
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 41 of 190 PageID #: 42534
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 41 of 190 PagelD #: 42534
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 38 of 39
`
`US 6,829,634 B1
`
`Handle condition
`repair statement
`
` Select a neighbornot
`
`involved in condition
`
`AB-AB 001125
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 42 of 190 PageID #: 42535
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 42 of 190 PagelD #: 42535
`
`U.S. Patent
`
`Dee. 7, 2004
`
`Sheet 39 of 39
`
`US 6,829,634 B1
`
`Handle condition
`double check
`
` Fig. 34
`
`
`
`3401
`
`Holes == 1
`
`AB-AB 001126
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 43 of 190 PageID #: 42536
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 43 of 190 PagelD #: 42536
`
`US 6,829,634 Bl
`
`1
`BROADCASTING NETWORK
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is related to 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
`CHANNEL,” filed on Jul. 31, 2000 currently patented. U.S.
`patent application Ser. No. 09/629,575, entitled “BROAD-
`CASTING ON A BROADCAST CHANNEL,” filed on Jul.
`31, 2000; U.S. patent application Ser. No. 09/629,572,
`entitled “CONTACTING 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 now under appeal. U.S.
`patent application Ser. No. 09/629,043, entitled “AN
`INFORMATION DELIVERY SERVICE,” filed on Jul. 31,
`2000 currently patented; U.S. patent application Ser. No.
`09/629,024, entitled “DISTRIBUTED CONFERENCING
`SYSTEM,” filed on Jul. 31, 2000; and U.S. patent applica-
`tion Ser. No. 09/629,042,entitled “DISTRIBUTED GAME
`ENVIRONMENT,” filed on Jul. 31, 2000 currently
`patented, the disclosures of which are incorporated herein by
`reference.
`
`19
`
`,
`
`
`
`TECHNICAL FIELD
`
`The described technology relates generally to a computer
`network and more particularly, to a broadcast channel for a
`subset of a computers of an underlying network.
`
`30
`
`BACKGROUND
`
`There are a wide varicty of computcr nctwork communi-
`cations techniques such as point-to-point network protocols,
`client/server middleware, multicasting network protocols,
`and peer-to-peer middleware. Each of these communications
`techniques have their advantages and disadvantages, but
`noneis particularly well suited to the simultaneous sharing
`of information among computers that are widely distributed.
`lor 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, allow processes 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 number of participants grows. For example, each
`participating process would need to manageits direct con-
`nections to all other participating processes. Programmers,
`however,find it 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 of possible participants in the sharing
`of information.
`
`The client/server middleware systems provide a server
`that coordinates the communications between the various
`chents whoare sharing the information. ‘lhe server functions
`as a central authority for controlling access to shared
`resourees. Examples of clicnt/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-
`
`4)
`
`45
`
`50
`
`60
`
`65
`
`2
`ticularly well suited to sharing of information among many
`participants. In particular, when a client stores information
`to be shared at the server, cach other clicnt 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. Alternatively, each client 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 newinformation 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 (i.e., the server) would prevent communications
`between anyofthe 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 overhead on the under-
`lying network. For example, UDP multicasting would
`swampthe 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 information efficiently.
`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
`usedin 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 ofpartici-
`pants is desired. In addition, the underlying architecture of
`the T.120 Internet standardis a tree structure, which relies on
`the root node of the tree for reliability of the entire network.
`That is, each message must pass through the root node in
`order to be received by all participants.
`It 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.
`SUMMARYOF THE INVENTION
`
`Embodiments of the invention deal with a non-routing
`table based method for broadcasting messages in a network.
`More specifically, a network in which each participanthas at
`least
`three neighbor participants broadcasts data through
`each of its connections to neighbor participants, which in
`turn send the data that it receives to its other neighbor
`participants. The data is numbered sequentially so that data
`that is received out of order can be queued and rearranged.
`Communication within the broadcast channel
`is con-
`trolled by a contact module and by a join module. The
`contact module locates a portal computer and requests the
`located portal computer to provide an indication of neighbor
`participants to which the participant can be connected. The
`join module receives the indication of the neighbor partici-
`pants and establishes a connection between the seeking
`participant and each of the indicated neighbor participants.
`Each participant in the network is connected to neighbor
`participants, and the participants and connections between
`them form an m-regular graph, where m is greater than 2. In
`addition, when a participant receives data from a neighbor
`participant,
`it sends the data to its other neighbor partici-
`pants.
`
`AB-AB 001127
`
`

`

`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 44 of 190 PageID #: 42537
`Case 1:16-cv-00453-RGA Document 492-1 Filed 03/07/18 Page 44 of 190 PagelD #: 42537
`
`US 6,829,634 Bl
`
`
`
`4
`FIG, 24is a flowdiagram illustrating the processing of the
`distribute broadcast message routine in one embodiment.
`FIG, 26 is a flowdiagram illustrating the processing of the
`handle connection port search statement
`routine in one
`embodiment.
`
`FIG. 27 is a flowdiagram illustrating the processing of the
`court neighbor routine in one embodiment.
`FIG, 28 is a flowdiagram illustrating the processing of the
`handle connection edge search cal] routine in one embodi-
`ment.
`
`FIG. 29 is a flowdiagram illustrating the processing of the
`handle connection edge search response routine in one
`embodiment.
`
`FIG. 30 is a flowdiagram illustrating the processing of the
`broadcast routine in one embodiment.
`
`FIG. 31 is a flowdiagram illustrating the processing of the
`acquire message routine in one embodiment.
`FIG. 32 is a flow diagram illustrating processing of the
`handle condition check message in one embodiment.
`FIG. 33 is a flow diagram illustrating processing of the
`handle condition repair statement routine in one embodi-
`ment.
`
`3
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 illustrates a graph that is 4-regular and 4-connected
`channel.
`which represents a broadcast
`h representing 20 computers
`FIG. 2 illustrates a grap
`connected to a broadcast channel.
`FIGS. 3A and 3B illustrat e the process of connecting a
`new computer Z to the broadcast channel.
`FIG. 4A illustrates the bro
`adcast 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. 5B illustrates the disconnecting of a computer from
`the broadcast channel in an unplanned manner.
`FIG. 5Cillustrates the neighbors with empty ports con-
`dition.
`
`FIG, 5D 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.
`FIG. 5Fillustrates the situation of FIG. 5E when in the
`large regime.
`FIG. 6 is a block diagram illustrating components of a
`computer that is connected to a broadcast channel.
`FIG. 7 is a block diagram 1 llustrating the sub-components
`of the broadcaster component in one embodiment.
`FIG. 8 is a flow diagram illustrating the processing ofthe
`connect routine in one embodiment.
`
`5
`
`15
`
`2
`
`ba A
`
`ta a
`
`35ta
`
`FIG. 9 is a flow diagram illustrating the processing ofthe
`seck portal computer routine in one embodiment.
`FIG, 10 is a flow diagram illustrating the processing of the
`contact process routine in one embodiment.
`FIG, 11 is a flow diagram illustrating the processing of the
`connect request routine in one embodiment.
`FIG. 12 is a flow diagram of the processing of the check
`for external call routine in one embodiment.
`
`4)
`
`FIG. 13 is a flow diagram of the processing ofthe achieve
`connection routine in one embodiment.
`
`45
`
`50
`
`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
`connected. 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 cach other connected computer
`using each computer’s address. Thus, the broadcast tech-
`nique effectively provides a broadcast channel using an
`FIG. 141saflow diagram illustrating the processing of the
`underlying network system that sends messages on a point-
`external dispatcher routine in one embodiment.
`to-point basis.
`FIG. 15 is a flow diagram illustrating the processing of the
`The broadcast technique overlays the underlying network
`handle seeking connection call routine in one embodiment.
`system with a graph of point-to-point connections (ie.,
`FIG. 16 is a flow diagramillustrating processing of the
`edges) between host computers(i.e., nodes) through which
`handle connection request call routine in one embodiment.
`the broadcast channel is implemented. In one embodiment,
`each computer is connectedto four other computers, referred
`FIG, 17 isa flow diagram il
`lustrating the processing of the
`embodiment.
`to as neighbors. (Actually, a process executing on a com-
`add neighbor routine in one
`puter is connected to four other processes executing on this
`FIG. 18 isa flow diagram i
`or
`four other computers.) To broadcast
`a message,
`the
`forward connection edge search routine in one embodiment.
`originating computer sends the message to each ofits
`FIG, 19 isa flow diagram illustrating the processing of the
`neighbors using its point-to-point connections. Each com-
`handle edge proposal call routine.
`puter that receives the message then sends the messagetoits
`FIG, 20 is a flow diagram illustrating the processing of the
`three other neighbors using the point-to-point connections.
`handle port connection call routine in one embodiment.
`In this way, the message is propagated to each computer
`FIG, 21 isa flow diagram il
`lustrating the processing of the
`using the underlying network to effect the broadcasting of
`fill hole routine in one emba
`diment.
`the message to each computer over a logical broadcast
`channel. A graph in which cach node is connected to four
`other nodes is referred to as a 4-regular grap