Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 1 of 174 PageID #: 215
`Case 1:16-cv-00454-RGA Document1-2 Filed 06/17/16 Page 1 of 174 PagelD #: 215
`
`
`
`EXHIBIT 4
`EXHIBIT 4
`
`
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 2 of 174 PageID #: 216
`111111
`1111111111111111111111111111111111111111111111111111111111111
`US006829634Bl
`
`(12) United States Patent
`Holt et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,829,634 Bl
`Dec. 7, 2004
`
`(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)
`
`( *) 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:
`
`Jul. 31, 2000
`
`Int. Cl? ................................................ G06F 15/16
`(51)
`(52) U.S. Cl. ....................... 709/204; 709/205; 709/203;
`709/243; 709/201; 709/238; 709/319; 709/225;
`370/236
`(58) Field of Search ................................. 709/106, 201,
`709/238, 319
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`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,265 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 A
`5,799,016 A
`5,802,285 A
`
`3/1990 Cain eta!.
`10/1991 Vu
`5/1994 Perlman et a!.
`6/1995 Derby eta!.
`7/1996 Amri eta!.
`10/1996 Sitbon eta!.
`6/1997 Yu
`9/1997 Gupta eta!.
`12/1997 Mahany
`3/1998 Spaur eta!.
`3/1998 Blumer eta!.
`3/1998 Yu
`4/1998 Periasamy et a!.
`5/1998 Butts eta!.
`6/1998 Miller
`6/1998 Onweller
`8/1998 Sistanizadeh et a!.
`8/1998 Deaton, Jr. et a!.
`8/1998 Onweller
`9/1998 Hirviniemi
`
`1!1999 Mairs eta!.
`5,864,711 A
`2/1999 Schmidt et a!.
`5,867,660 A
`2/1999 Butman eta!.
`5,867,667 A
`2/1999 Bracho eta!.
`5,870,605 A
`2/1999 Mairs eta!.
`5,874,960 A
`5/1999 Wilf eta!.
`5,899,980 A
`5/1999 Onweller
`5,907,610 A
`7/1999 Morita
`5,928,335 A
`8/1999 Bell eta!.
`5,935,215 A
`9/1999 Nielsen
`5,948,054 A
`9/1999 Batty eta!.
`5,949,975 A
`5,953,318 A * 9/1999 Nattkemper et a!. ........ 370/236
`5,956,484 A
`9/1999 Rosenberg et a!.
`5,974,043 A
`10/1999 Solomon
`5,987,506 A
`11/1999 Carteret a!.
`
`(List continued on next page.)
`
`OTHER PUBLICATIONS
`
`Alagar, S. and Venkatesan, S., "Reliable Broadcast in
`Mobile Wireless Networks," Department of Computer Sci(cid:173)
`ence, University of Texas at Dallas, Military Communica(cid:173)
`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, which in 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 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
`
`A
`
`8
`
`H
`
`D
`
`F
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 3 of 174 PageID #: 217
`
`US 6,829,634 Bl
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`6,003,088 A
`6,013,107 A
`6,023,734 A
`6,029,171 A
`6,032,188 A
`6,038,602 A
`6,047,289 A
`6,094,676 A
`6,199,116 B1
`6,216,177 B1
`6,223,212 B1
`6,243,691 B1
`6,268,855 B1
`6,271,839 B1
`6,285,363 B1
`6,304,928 B1
`6,611,872 B1 *
`
`12/1999
`1!2000
`2/2000
`2/2000
`2/2000
`3/2000
`4/2000
`7/2000
`3/2001
`4/2001
`4/2001
`6/2001
`7/2001
`8/2001
`9/2001
`10/2001
`8/2003
`
`Houston et a!.
`Blackshear et a!.
`Ratcliff et a!.
`Smiga eta!.
`Mairs eta!.
`Ishikawa
`Thorne eta!.
`Gray eta!.
`May eta!.
`Mairs eta!.
`Batty eta!.
`Fisher eta!.
`Mairs eta!.
`Mairs eta!.
`Mairs eta!.
`Mairs eta!.
`McCanne ................... 709/238
`
`01HER PUBLICATIONS
`
`International Search Report for The Boeing Company, Inter(cid:173)
`national Patent Application No. PCT/US01/24240, Jun. 5,
`2002 (7 pages).
`U.S. patent application Ser. No. 09/629,570, Bourassa et al.,
`filed Jul. 31, 2000.
`U.S. patent application Ser. No. 09/629,577, Bourassa et al.,
`filed Jul. 31, 2000.
`U.S. patent application Ser. No. 09/629,575, Bourassa et al.,
`filed Jul. 31, 2000.
`U.S. 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.
`U.S. patent application Ser. No. 09/629,043, Bourassa et al.,
`filed Jul. 31, 2000.
`U.S. patent application Ser. No. 09/629,024, Bourassa et al.,
`filed Jul. 31, 2000.
`U.S. 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).
`
`The O'Reilly Network, "Gnutella: Alive, Well, and Chang(cid:173)
`ing Fast," Jan. 25, 2001 (5 pages) http://www.open2p.com/
`1pt/ ... [Accessed Jan. 29, 2002].
`Oram, Andy, "Gnutella and Freenet Represents True Tech(cid:173)
`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(cid:173)
`dard," Sun Microsystems, 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 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(cid:173)
`cations," Chapters 1-3 (pp. 1-47), 1976 American Elsevier
`Publishing Co., Inc., New York, New York.
`Carmen, 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(cid:173)
`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.dcs.warwick.ac.u ... [Accessed Jan. 29, 2002].
`
`* cited by examiner
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 4 of 174 PageID #: 218
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 1 of 39
`
`US 6,829,634 Bl
`
`0
`
`co
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 5 of 174 PageID #: 219
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 2 of 39
`
`US 6,829,634 Bl
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 6 of 174 PageID #: 220
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 3 of 39
`
`US 6,829,634 Bl
`
`m
`
`o
`
`w
`
`m
`
`w
`
`0
`
`c
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 7 of 174 PageID #: 221
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 4 of 39
`
`US 6,829,634 Bl
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 8 of 174 PageID #: 222
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 5 of 39
`
`US 6,829,634 Bl
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 9 of 174 PageID #: 223
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 6 of 39
`
`US 6,829,634 Bl
`
`u..
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 10 of 174 PageID #: 224
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 7 of 39
`
`US 6,829,634 Bl
`
`0
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 11 of 174 PageID #: 225
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 8 of 39
`
`US 6,829,634 Bl
`
`0
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 12 of 174 PageID #: 226
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 9 of 39
`
`US 6,829,634 Bl
`
`0
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 13 of 174 PageID #: 227
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 10 of 39
`
`US 6,829,634 Bl
`
`0
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 14 of 174 PageID #: 228
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 11 of 39
`
`US 6,829,634 Bl
`
`•
`
`-~ ~
`
`(J
`
`0
`
`0
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 15 of 174 PageID #: 229
`
`600
`
`User
`Ports
`
`601
`
`602
`
`Application I
`(channel type
`channel instance)
`
`I
`
`!Broadcaster
`
`•
`•
`•
`
`601
`
`Application 2
`(channel type
`channel instance)
`
`603
`
`Fig. 6
`
`d •
`\Jl
`•
`~
`~ ......
`~ = ......
`
`~
`~
`!"l
`~-..J
`
`N c c
`
`~
`
`'JJ. =(cid:173)~
`~ .....
`'"""' N
`0 ......,
`~
`'0
`
`e
`rJ'l
`-..a-..
`00
`N
`-..\/:;
`~
`~
`~
`1--"
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 16 of 174 PageID #: 230
`
`0
`
`710
`
`Connect
`call back
`
`k
`al
`
`701
`
`Connect
`
`§ 705
`~
`l::j
`
`712
`
`Broadcast
`
`0
`B
`
`709
`Broadcast
`msg
`queue
`
`Q
`t:::J
`
`707
`
`Handle N
`
`E msg J
`
`707
`
`Handle
`EmssN
`
`708
`
`Handle
`Imsg 1
`
`. • .
`
`Fig. 7
`
`700
`
`702
`mal
`1
`Exte
`dispatcher.
`
`zo~
`Internal
`dispatcher!
`I
`
`I
`
`703
`
`d •
`\Jl
`•
`~
`~ ......
`~ = ......
`
`~
`~
`!"l
`~-..J
`
`N c c
`
`~
`
`'JJ. =(cid:173)~
`
`~
`'"""' ~
`0 ......,
`~
`'0
`
`e
`
`rJ'l
`0'1
`Oo
`N
`\0
`~
`~
`~
`1--"
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 17 of 174 PageID #: 231
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 14 of 39
`
`US 6,829,634 Bl
`
`(Channel Type,
`Channel Instance,
`Connect Awe Info)
`
`Open call in port
`
`802
`
`Fig. 8
`
`Set connect-time
`
`803
`Seek portal - computer
`( clwmeJ type channel
`instance)
`
`Return (false)
`
`y
`
`Achieve COJIDection
`
`806
`
`807
`Install external dispatcher
`
`BOB
`
`Install external dispatcher
`
`809
`
`Connect request
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 18 of 174 PageID #: 232
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 15 of 39
`
`US 6,829,634 Bl
`
`Seek portal
`computer
`
`Channel Type
`Channel Instance
`
`902
`
`Select next depth
`
`Return (failure)
`
`Select next portal computer
`
`Fig. 9
`
`y
`
`N
`
`Contact process
`
`909
`Hang up selected portal
`computer
`
`911
`Check for external
`call
`
`N
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 19 of 174 PageID #: 233
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 16 of 39
`
`US 6,829,634 Bl
`
`Send external message
`
`Fig. 10
`
`1002
`Receive external message
`
`1005
`Add as connected portal
`computer
`
`.------........
`
`1006
`Add as fellow seeking
`computer
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 20 of 174 PageID #: 234
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 17 of 39
`
`US 6,829,634 Bl
`
`Fig. 11
`
`1105
`Send external message
`
`1106
`Receive external message
`
`N
`
`1108
`Set expect holes from
`response
`
`1109
`Set diameter from response
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 21 of 174 PageID #: 235
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 18 of 39
`
`US 6,829,634 Bl
`
`heck for extern
`call
`
`1201
`
`Answer
`
`Fig.l2
`
`y
`
`Receive external message
`
`N
`
`y
`
`1205
`Send external message
`
`y
`
`1207
`Add other as fellow seeker
`
`Return
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 22 of 174 PageID #: 236
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 19 of 39
`
`US 6,829,634 Bl
`
`Fig. 13
`
`Achieve connection
`
`1301
`Connection - state • fully
`connected
`
`1302
`Notify fellow seekers
`
`1303
`Invoke connect call back
`
`Return
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 23 of 174 PageID #: 237
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 20 of 39
`
`US 6,829,634 Bl
`
`Fig. 14
`
`1416
`
`Hang up
`
`1404
`Handle seeking
`COJUlectiOD call
`
`1406
`Handle connection
`request call
`
`1408
`Handle edge proposal
`call
`
`1410
`
`Handle port
`connection call
`
`1412
`Handle connected
`statement
`
`1414
`Handle condition
`repair statement
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 24 of 174 PageID #: 238
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 21 of 39
`
`US 6,829,634 Bl
`
`1502
`Set message to indicate
`connected
`
`y
`
`Fig. IS
`
`N
`
`1503
`Set message to not
`connected
`
`1504
`Add other u fellow
`seeking process
`
`1505
`
`Send external message
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 25 of 174 PageID #: 239
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 22 of 39
`
`US 6,829,634 Bl
`
`Fig.16
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 26 of 174 PageID #: 240
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 23 of 39
`
`US 6,829,634 Bl
`
`.Sets neighbor to
`messages pending
`
`Fig. 17
`
`CoMection state =
`partially connected
`
`Send interal stream
`
`Achieve connected
`
`Purge pending edges
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 27 of 174 PageID #: 241
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 24 of 39
`
`US 6,829,634 Bl
`
`Forward connection
`edge search
`
`requestor
`distance remaining
`
`Fig.18
`
`~N---1 Select random neighbor
`
`y
`
`Return
`
`y
`
`Send internal message
`
`1808
`Note connection edge
`search caD
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 28 of 174 PageID #: 242
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 25 of 39
`
`US 6,829,634 Bl
`
`in message
`out message
`
`Fig.19
`
`N
`
`y
`
`y
`
`create edge (pending)
`
`1
`
`Send external message
`
`Send external message
`
`Return
`
`Fill hole
`
`Add edge as pending
`
`1910
`
`Add neighbor
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 29 of 174 PageID #: 243
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 26 of 39
`
`US 6,829,634 Bl
`
`Fig. 20
`
`20
`Send external message
`~---1 (point-connect-resp
`not ok)
`
`Send external message
`(point-connect-resp, ok)
`
`N
`
`y
`
`2007
`
`Hang up
`
`2006
`
`Add neighbor
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 30 of 174 PageID #: 244
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 27 of 39
`
`US 6,829,634 Bl
`
`Fig. 21
`
`Initialize internal
`message
`
`N
`
`2104
`Handle connection
`ports search edit
`
`Distribute internal
`message
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 31 of 174 PageID #: 245
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 28 of 39
`
`US 6,829,634 Bl
`
`Fig. 22
`
`y
`
`Insert message into
`pending connection buffer
`
`Handle broadcast
`message
`
`2007
`Handle shutdown
`statement
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 32 of 174 PageID #: 246
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 29 of 39
`
`US 6,829,634 Bl
`
`Fig. 23
`
`origin
`from neighbor
`message
`
`Process out of order
`message
`
`2302
`Distribute broadcast
`message
`
`Y
`
`Clear out of order info
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 33 of 174 PageID #: 247
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 30 of 39
`
`US 6,829,634 Bl
`
`Fig. 24
`
`message
`from neighbor
`
`Select next neighbor
`
`Return
`
`2403
`Send internal
`message
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 34 of 174 PageID #: 248
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 31 of 39
`
`US 6,829,634 Bl
`
`Handle coiUlection
`for search
`
`from neighbor
`message
`
`2601
`Distribute internal
`message
`
`Fig. 26
`
`Return
`
`2604
`
`Court neighbor
`
`2606
`
`2607
`Send internal message
`to requestor
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 35 of 174 PageID #: 249
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 32 of 39
`
`US 6,829,634 Bl
`
`Court neighbor
`
`Prospect
`
`Fig. 27
`
`N
`
`2702
`
`Dial prospect
`
`N
`
`y
`
`2704
`Send and receive
`external message
`
`2705
`
`Add nciahbor
`
`2706
`
`Hang up prospect
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 36 of 174 PageID #: 250
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 33 of 39
`
`US 6,829,634 Bl
`
`Fig. 28
`
`from neighbor
`message
`
`Fill hole (self)
`
`2805
`
`Forward
`conneetion edge
`search (requestor,
`0)
`
`Dial requestor
`
`2807
`Send and receive
`external message
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 37 of 174 PageID #: 251
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 34 of 39
`
`US 6,829,634 Bl
`
`Fig. 29
`
`Handle edge search
`resp.
`
`Note connection edge
`search response
`
`origin
`from neighbor
`message
`
`Reserve edge of from
`neighbor
`
`Remove from neighbor
`
`2905
`Court neighbor
`
`y
`
`N
`
`2908
`Fill hole (self)
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 38 of 174 PageID #: 252
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 35 of 39
`
`US 6,829,634 Bl
`
`Broadcast
`
`Fig. 30
`
`Return
`
`y
`
`3002
`Generate internal
`message
`
`3003
`Set message sequence
`number
`
`3004
`Distribute internal
`message
`
`Return
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 39 of 174 PageID #: 253
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 36 of 39
`
`US 6,829,634 Bl
`
`message
`
`Return false
`
`Fig. 31
`
`3101
`
`Pop message queue
`
`y
`
`Return true
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 40 of 174 PageID #: 254
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 37 of 39
`
`US 6,829,634 Bl
`
`Fig. 32
`
`Return
`
`3203
`Set up message with list
`of neighbors
`
`3204
`
`Send internal message
`
`Send external message
`to selected neighbor
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 41 of 174 PageID #: 255
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 38 of 39
`
`US 6,829,634 Bl
`
`Fig. 33
`
`Handle condition
`repair statement
`
`N
`
`y
`
`3302
`Select a neighbor not
`involved in condition
`
`3303
`Remove selected
`neighbor
`
`3304
`
`Add neighbor
`
`Return
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 42 of 174 PageID #: 256
`
`U.S. Patent
`
`Dec. 7, 2004
`
`Sheet 39 of 39
`
`US 6,829,634 Bl
`
`Fig. 34
`
`Create list of neighbors
`
`3407
`Send internal message
`to-from neighbor
`
`Reset diameter to 1
`
`3405
`Send intemaJ message
`
`Return
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 43 of 174 PageID #: 257
`
`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(cid:173)
`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(cid:173)
`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 25
`reference.
`
`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.
`
`BACKGROUND
`
`2
`ticularly well suited to sharing of information among many
`participants. In particular, when a client stores information
`to be shared at the server, each other client would need to
`poll the server to determine that new information is being
`5 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
`10 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 (i.e., the server) would prevent communications
`15 between any of 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(cid:173)
`tocols tend to place an unacceptable overhead on the under-
`20 lying network. For example, UDP multicasting would
`swamp the Internet when trying to locate all possible par(cid:173)
`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(cid:173)
`ware is provided by the T.120 Internet standard, which is
`used in such products as Data Connection's D.C.-share and
`30 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(cid:173)
`ware systems when more than a small number of partici-
`35 pants is desired. In addition, the underlying 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, 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.
`
`There are a wide variety of computer network communi(cid:173)
`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
`none is particularly well suited to the simultaneous sharing 40
`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 manner to 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(cid:173)
`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 50
`as a number of participants grows. For example, each
`participating process would need to manage its direct con(cid:173)
`nections to all other participating processes. Programmers,
`however, find it very difficult to manage single connections,
`and management of multiple connections is much more 55
`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 60
`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
`("COREA"). Client/server middleware systems are not par-
`
`45
`
`SUMMARY OF 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 participant has 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
`65 addition, when a participant receives data from a neighbor
`participant, it sends the data to its other neighbor partici(cid:173)
`pants.
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 44 of 174 PageID #: 258
`
`US 6,829,634 Bl
`
`3
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`10
`
`FIG. 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 to a broadcast channel.
`FIGS. 3A and 3B illustrate the process of connecting a
`new computer Z to the broadcast channel.
`FIG. 4A illustrates 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. SA 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. SC illustrates the neighbors with empty ports con(cid:173)
`dition.
`FIG. SD illustrates two computers that are not neighbors
`who now have empty ports.
`FIG. SE illustrates the neighbors with empty ports con- 25
`dition in the small regime.
`FIG. SF illustrates the situation of FIG. SE 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 illustrating the sub-components
`of the broadcaster component in one embodiment.
`FIG. 8 is a flow diagram illustrating the processing of the
`connect routine in one embodiment.
`FIG. 9 is a flow diagram illustrating the processing of the
`seek 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 40
`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.
`FIG. 13 is a flow diagram of the processing of the achieve
`connection routine in one embodiment.
`FIG. 14 is a flow diagram illustrating the processing of the
`external dispatcher routine in one embodiment.
`FIG. 1S is a flow diagram illustrating the processing of the
`handle seeking connection call routine in one embodiment.
`FIG. 16 is a flow diagram illustrating processing of the
`handle connection request call routine in one embodiment.
`FIG. 17 is a flow diagram illustrating the processing of the
`add neighbor routine in one embodiment.
`FIG. 18 is a flow diagram illustrating the processing of the
`forward connection edge search routine in one embodiment.
`FIG. 19 is a flow diagram illustrating the processing of the
`handle edge proposal call routine.
`FIG. 20 is a flow diagram illustrating the processing of the
`handle port connection call routine in one embodiment.
`FIG. 21 is a flow diagram illustrating the processing of the
`fill hole routine in one embodiment.
`FIG. 22 is a flow diagram illustrating the processing of the
`internal dispatcher routine in one embodiment.
`FIG. 23 is a flow diagram illustrating the processing of the
`handle broadcast message routine in one embodiment.
`
`4
`FIG. 24 is a flow diagram illustrating the processing of the
`distribute broadcast message routine in one embodiment.
`FIG. 26 is a flow diagram illustrating the processing of the
`handle connection port search statement routine in one
`5 embodiment.
`FIG. 27 is a flow diagram illustrating the processing of the
`court neighbor routine in one embodiment.
`FIG. 28 is a flow diagram illustrating the processing of the
`handle connection edge search call routine in one embodi(cid:173)
`ment.
`FIG. 29 is a flow diagram illustrating the processing of the
`handle connection edge search response routine in one
`embodiment.
`FIG. 30 is a flow diagram illustrating the processing of the
`broadcast routine in one embodiment.
`FIG. 31 is a flow diagram illustrating the processing of the
`acquire message routine in one embodiment.
`FIG. 32 is a flow diagram illustrating processing of the
`20 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(cid:173)
`ment.
`FIG. 34 is a flow diagram illustrating the processing of the
`handle condition double check routine.
`
`15
`
`DETAILED DESCRIPTION
`
`A broadcast technique in which a broadcast channel
`30 overlays a point-to-point communications network is pro(cid:173)
`vided. 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 chan(cid:173)
`nel. In one embodiment, the broadcast technique provides a
`35 logical broadcast channel to which host computers through
`their executing processes can be connected. Each computer
`that 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
`connected. The logical broadcast channel is implemented
`using an underlying network system (e.g., the Internet) that
`allows each computer connected to the underlying network
`system to send messages to each other connected computer
`45 using each computer's address. Thus, the broadcast tech(cid:173)
`nique effectively provides a broadcast channel using an
`underlying network system that sends messages on a point(cid:173)
`to-point basis.
`The broadcast technique overlays the underlying network
`50 system with a graph of point-to-point connections (i.e.,
`edges) between host computers (i.e., nodes) through which
`the broadcast channel is implemented. In one embodiment,
`each computer is connected to four other computers, referred
`to as neighbors. (Actually, a process executing on a com-
`55 puter is connected to four other processes executing on this
`or four other computers.) To broadcast a message, the
`originating computer sends the message to each of its
`neighbors using its point-to-point connections. Each com(cid:173)
`puter that receives the message then sends the message to its
`60 three other neighbors using the point-to-point connections.
`In this way, the message is propagated to each computer
`using the underlying network to effect the broadcasting of
`the message to each computer over a logical broadcast
`channel. A graph in which each node is connected to four
`65 other nodes is referred to as a 4-regular graph. The use of a
`4-regular graph means that a computer would become
`disconnected from the broadcast channel only if all four of
`
`

`

`Case 1:16-cv-00454-RGA Document 1-2 Filed 06/17/16 Page 45 of 174 PageID #: 259
`
`US 6,829,634 Bl
`
`s
`
`5
`the connections to its neighbors fail. The graph used by the
`broadcast technique also has the property that it would take
`a failure of four computers to divide the graph into disjoint
`sub-graphs, that is two separate broadcast channels. This
`property is referred to as being 4-connected. Thus, the graph
`is both 4-regu