Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 1 of 59 PageID #: 326
`
`Exhibit 6
`
`           
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 2 of 59 PageID #: 327
`
`(12) United States Patent
`Bourassa et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,920,497 B1
`Jul. 19, 2005
`
`US006920497B1
`
`(54)
`(75)
`
`(73)
`
`CONTACTING A BROADCAST CHANNEL
`
`Inventors: Virgil E. Bourassa, Bellevue, WA
`(US); Fred B. Holt, Seattle, WA (US)
`
`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 750 days.
`
`(21)
`(22)
`
`(51)
`(52)
`(58)
`
`(56)
`
`Appl. No.: 09/629,572
`Filed:
`Jul. 31, 2000
`
`Int. Cl.7 .............................................. .. G06F 15/16
`
`US. Cl.
`
`..
`
`Field of Search ............................... .. 709/249, 250,
`709/227, 370/389, 392, 463, 710/62
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,912,656
`5,056,085
`5,058,105
`5,079,767
`5,099,235
`5,101,480
`5,117,422
`5,309,437
`5,345,558
`5,426,637
`5,459,725
`5,471,623
`5,511,168
`5,535,199
`5,568,487
`5,636,371
`5,644,714
`5,673,265
`5,696,903
`5,732,074
`5,732,086
`5,732,219
`5,734,865
`
`3/1990
`10/1991
`10/1991
`1/1992
`3/1992
`3/1992
`5/1992
`5/1994
`9/1994
`6/1995
`10/1995
`11/1995
`4/1996
`7/1996
`10/1996
`6/1997
`7/1997
`9/1997
`12/1997
`3/1998
`3/1998
`3/1998
`3/1998
`
`Cain et a1.
`Vu
`Mansour et a1.
`Perlman
`Crookshanks
`Shin
`Hauptschein
`Perlman et a1.
`Opher
`Derby et a1.
`Bodner et a1.
`Napolitano
`Perlman
`Amri et a1.
`Sitbon et 81.
`Yu
`Kikinis
`Gupta et al.
`Mahany
`Spaur et a1.
`Liang
`Blumer et 81.
`Yu
`
`4/1998 Periasamy et al.
`5,737,526 A
`5/1998 Butts et 81.
`5,754,830 A
`5,757,795 A * 5/1998 Schnell ..................... .. 370/392
`5,761,425 A
`6/1998 Miller
`5,764,756 A
`6/1998 OnWeller
`5,790,548 A
`8/1998 SistaniZadeh et 81.
`5,790,553 A
`8/1998 Deaton, Jr. et 81.
`5,799,016 A
`8/1998 OnWeller
`5,802,285 A
`9/1998 Hirviniemi
`5,850,592 A 12/1998 Ramanathan
`5,864,711 A
`1/1999 Mairs et al.
`5,867,660 A
`2/1999 Schmidt et 81.
`5,867,667 A
`2/1999 Butman et 81.
`5,870,605 A
`2/1999 Bracho et 81.
`5,874,960 A
`2/1999 Mairs et al.
`5,883,894 A * 3/1999 Patel et al. ............... .. 370/438
`5,899,980 A
`5/1999 Wilfet 81.
`5,907,610 A
`5/1999 OnWeller
`5,925,097 A
`7/1999 Gopinath et 81.
`5,928,335 A
`7/1999 Morita
`(Continued)
`OTHER PUBLICATIONS
`
`Bandyopadhyay et al., “A Flexible Architecture for Multi
`Hop Optical Networks,” Oct. 1998, 7th International Con
`ference on Computer Communications and Networks, 1998,
`pp. 472—478.
`
`(Continued)
`Primary Examiner—Bradley Edelman
`(74) Attorney, Agent, or Firm—Perkins Coie LLP
`(57)
`ABSTRACT
`
`A method of connecting to a network through a portal
`computer. A seeking computer dials the communications
`ports of a portal computer until it locates a call-in port. A
`port ordering algorithm is used to identify the call-in port.
`Communications ports selected by the port ordering algo
`rithm may be re-ordered. The seeking computer uses the
`selected call-in port to request that the portal computer
`coordinate the connection of the seeking computer to the
`network.
`
`16 Claims, 39 Drawing Sheets
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 3 of 59 PageID #: 328
`
`US 6,920,497 B1
`Page 2
`
`US. PATENT DOCUMENTS
`
`8/1999 Bell et al.
`5,935,215 A
`8/1999 Chen et al.
`5,946,316 A
`9/1999 Nielsen
`5,948,054 A
`9/1999 Batty
`5,949,975 A
`9/1999 Rosenberg et al.
`5,956,484 A
`5,970,232 A 10/1999 Passint et al.
`5,974,043 A 10/1999 Solomon
`5,987,506 A 11/1999 Carter et 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,065,063 A
`5/2000 Abali
`6,073,177 A
`6/2000 Hebel et al.
`6,094,676 A
`7/2000 Gray et al.
`6,115,580 A
`9/2000 Chuprun et al.
`6,151,633 A 11/2000 Hurst
`6,167,432
`12/2000 Jiang
`A
`6,173,314 B1
`1/2001 Kurashima et al.
`6,195,366 B1 * 2/2001 Kayashima et al. ...... .. 370/475
`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,252,884 B1
`6/2001 Hunter
`6,268,855 B1
`7/2001 Mairs et al.
`6,269,080 B1
`7/2001 Kumar
`6,271,839 B1
`8/2001 Mairs et al.
`6,272,548 B1
`8/2001 Cotter et al.
`6,285,363 B1
`9/2001 Mairs et al.
`6,304,928 B1
`10/2001 Mairs et al.
`6,321,270 B1
`11/2001 Crawley
`6,353,599 B1
`3/2002 Bi et al.
`6,415,270 B1
`7/2002 Rackson
`6,421,735 B1 * 7/2002 Jung et al. ................ .. 709/250
`6,434,622 B1
`8/2002 Monteiro
`6,449,251 B1 * 9/2002 Awadallah et al. ....... .. 370/229
`6,449,601 B1
`9/2002 Friedland
`6,463,078 B1
`10/2002 Engstrom et al.
`6,490,247 B1
`12/2002 Gilbert
`6,505,289 B1
`1/2003 Han
`6,524,189 B1
`2/2003 Rautila
`6,553,020 B1
`4/2003 Hughes
`6,603,742 B1
`8/2003 Steele
`6,618,752 B1
`9/2003 Moore et al.
`6,701,344 B1
`3/2004 Holt
`2002/0027896 A1
`3/2002 Hughes et al.
`
`OTHER PUBLICATIONS
`
`Hsu, “On—Four—Connecting a Triconnected Graph,” Oct.
`1992, Annual Symposium on Foundations of Computer
`Science, 1992, pp. 70—79.
`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.
`Shiokawa et al., “Performance Analysis on Network Con
`nective Probability of Multihop Network Under Correlated
`Breakage,” Jun. 1996, 1996 IEEE International Conference
`on Communications, vol. 3, pp. 1581—1585.
`Komine et al., “A Distributed Restoration Algorithm for
`Multiple—Link and Node Failures of Transport Networks,”
`Dec. 1999, IEEE Globecom ’90, Communicaitons: Com
`mecting the Future, vol. 1, pp. 459—463.
`
`Peercy et al., “Distributed Algorithms for Shortest—Path,
`Deadlock—Free Routing and Broadcasting in Arbitrarily
`Faulty Hypercubes,” Jun. 1990, 20th International Sympo
`sium on Fault—Tolerant Computing, 1990, pp—218—225.
`Yavatkar et al., “A reliable Dissemination Protocol for
`Interactive Collaborative Applications,” Proc. ACM Multi
`media, 1995, p. 333—344; http://citeseer.nj.nec.com/article/
`yavatkar95reliable.htlm.
`PR Newswire, “Microsoft Boosts Accessibility to Internet
`Gaming Zone with Latest Release,” Apr. 27, 1998, pp lff.
`PR Newswire, “Microsoft Annouces Launch Date for Ultra
`Corps, Its Second Premium Title for the Internet Gaming
`Zone,” Mar. 27, 1998, pp 1 ff.
`Business Wire, “Boeing Panthesis Complete SWAN Trans
`action,” Jul. 22, 2002, pp lff.
`AZar, et al., “Routing Strategies for Fast Networks,” May
`1992 INFOCOM ’92, Eleventh Annual Joint Conference of
`the IEEE Computer and Communications Societies, vol. 1.,
`pp 170—179.
`U.S. Appl. No. 09/629,570, ?led Jul. 31, 2000, Bourassa et
`al.
`US. Appl. No. 09/629,577, ?led Jul. 31, 2000, Bourassa et
`al.
`US. Appl. No. 09/629,575, ?led Jul. 31, 2000, Bourassa et
`al.
`US. Appl. No. 09/629,576, ?led Jul. 31, 2000, Bourassa et
`al.
`US. Appl. No. 09/629,023, ?led Jul. 31, 2000, Bourassa et
`al.
`US. Appl. No. 09/629,043, ?led Jul. 31, 2000, Bourassa et
`al.
`US. Appl. No. 09/629,024, ?led Jul. 31, 2000, Bourassa et
`al.
`US. Appl. No. 09/629,042, ?led Jul. 31, 2000, Bourassa et
`al.
`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 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 T120
`Series Standards,” Copyright 1995 (pp. 1—16).
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 4 of 59 PageID #: 329
`
`US 6,920,497 B1
`Page 3
`
`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].
`
`Alagar, S. and Venkatesan, S., “Reliable Broadcast in
`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).
`
`International Search Report for The Boeing Company, Inter
`national Patent Application No. PCT/US01/24240, Jun. 5,
`2002 (7 pages).
`
`* cited by examiner
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 5 of 59 PageID #: 330
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 1 0f 39
`
`US 6,920,497 B1
`
`1»
`
`/ b
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 6 of 59 PageID #: 331
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 2 m9
`
`US 6,920,497 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 7 of 59 PageID #: 332
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 3 0f 39
`
`US 6,920,497 B1
`
`m
`
`o
`
`<
`
`<
`
`N
`
`53
`5’
`
`m
`
`o
`
`m
`
`o
`
`a
`
`3,
`£5
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 8 of 59 PageID #: 333
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 4 0f 39
`
`US 6,920,497 B1
`
`41 i
`1547
`
`v» .S
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 9 of 59 PageID #: 334
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 5 0f 39
`
`US 6,920,497 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 10 of 59 PageID #: 335
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 6 0f 39
`
`US 6,920,497 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 11 of 59 PageID #: 336
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 7 0f 39
`
`US 6,920,497 B1
`
`,1;
`
`‘Y
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 12 of 59 PageID #: 337
`
`U.S. Patent
`
`Jul. 19, 2005
`
`Sheet 8 m9
`
`US 6,920,497 B1
`
`0
`
`U
`
`4
`
`I
`
`/
`
`ig. 5B
`
`/
`/
`
`I
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 13 of 59 PageID #: 338
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 9 0f 39
`
`US 6,920,497 B1
`
`m
`
`<
`
`U
`“v:
`£9
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 14 of 59 PageID #: 339
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 10 0f 39
`
`US 6,920,497 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 15 of 59 PageID #: 340
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 11 0f 39
`
`US 6,920,497 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 16 of 59 PageID #: 341
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 16 of 59 Page|D #: 341
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 12 of 39
`
`US 6,920,497 B1
`
`ig.6
`
`:3?
`5-3“:
`375.5
`
`<.,§
`
`
`Application2(channel
`
`typechamclinstance)
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 17 of 59 PageID #: 342
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 13 0f 39
`
`US 6,920,497 B1
`
`mom
`
`3:8:
`
`.2332“.
`
`
`
`mob Po»
`
`itch
`xoum 80580
`
`was
`
`82:30
`
`33:8
`
`m 2.
`
`3339mm
`
`80580
`
`105 =3
`
`
`
`mom vow
`
`25.6
`$323.5 2334
`$8 $.88...
`
`0x08“
`
`0883b
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 18 of 59 PageID #: 343
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 14 0f 39
`
`US 6,920,497 B1
`
`(CW6! Type,
`Channel Instance,
`Connect Aux Info)
`
`Fig. 8
`
`(
`
`Connect
`
`)
`
`Open call in port
`
`801
`
`BQZ.
`
`Set connect-time
`
`803
`Seek portal - computer
`(channel type channel
`instance)
`
`Contacts
`= =
`0
`
`_
`
`Return (false)
`
`805
`
`Achieve connection
`
`B07
`
`Install external dispatcher
`
`Install enema] d'spatcher
`
`809
`
`Connect request
`
`(
`
`Return (true)
`
`>
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 19 of 59 PageID #: 344
`
`U.S. Patent
`
`Jul. 19, 2005
`
`Sheet 15 0f 39
`
`US 6,920,497 B1
`
`Seek portal
`computer
`
`Channel Type
`Channel instance
`
`'
`Select next depth
`
`902
`
`All depths selected
`
`904
`N
`Select next penal compute:
`
`05
`All portal computers
`selected
`
`Dial portal computer
`
`907
`
`Y
`
`908
`
`Contact process
`
`909
`Hang up selected portal
`computer
`
`911
`Check for external
`call
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 20 of 59 PageID #: 345
`
`U.S. Patent
`
`Jul. 19, 2005
`
`Sheet 16 0f 39
`
`US 6,920,497 B1
`
`( Contact process )
`
`1001
`Send external message
`
`100;
`Receive external message
`
`Fig. 10
`
`1 005
`Add as connected portal
`computer
`
`Answering process
`connected
`
`1006
`Add as fellow seeking
`computer
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 21 of 59 PageID #: 346
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 17 0f 39
`
`US 6,920,497 B1
`
`Connect request
`
`Dial call‘in port of portal
`computer
`
`1 104
`
`Success
`
`N
`
`1105
`Y
`Send external message
`
`1 106
`Receive external message
`
`11.8.
`Y
`§et expect holes from
`response
`
`1 129
`Set diameter from response
`
`111
`Ready to connect
`
`1 1 12
`Add neighbor
`
`N‘
`Hangup
`
`11127
`
`{
`
`Return
`
`1
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 22 of 59 PageID #: 347
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 22 of 59 Page|D #: 347
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 18 of 39
`
`US 6,920,497 B1
`
`.
`
`' hack for exte
`
`call
`
`Fig. 12
`
`
`
`
`
`
`
`connection call
`
`K
`
`
`
`@
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 23 of 59 PageID #: 348
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 23 of 59 Page|D #: 348
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 19 of 39
`
`US 6,920,497 B1
`
`
`
`
`
`
`
`
`
`1 301
`Connection - state = fully
`connected
`
`
`
`Fig. 13
`
`
`
`1 302
`
`Notify fellow seekers
`
`1 303
`
`Invoke connect call back
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 24 of 59 PageID #: 349
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 24 of 59 Page|D #: 349
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 20 of 39
`
`US 6,920,497 B1
`
`External dispatcher
`
`Fig. 14
`
`
`
`1 404
`
`Handle seekinII
`
`
`
`Seeking connection can
`
`
`Connected statement
`
`
`statement ‘ repairstatement I
`
`1406
`
`Handle connection
`request call
`
`1 408
`
`Handle edge proposal
`call
`
`1410
`
`Handle port
`connection call
`
`Handle connected
`statement
`
`ondition repair
`
`Handle condition
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 25 of 59 PageID #: 350
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 25 of 59 Page|D #: 350
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 21 of 39
`
`US 6,920,497 B1
`
`
`
`Handle eeeking
`connecuon call
`
`1501
`
`Fully connected
`
`
`
`Set message to indicate
`connected
`
`
`
`1505
`
`Send external message
`
`
`
`1 504
`
`Add other as fellow
`seeking process
`
` Fig. 15
`
`Set message to not
`connected
`
`1503
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 26 of 59 PageID #: 351
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 26 of 59 Page|D #: 351
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 22 of 39
`
`US 6,920,497 B1
`
`ndle connection
`request call
`
`1601
`
`_ ,
`
`9)
`Set newcomer’: W
`holes_to__expect
`
`3.57
`Set diameter estimate in
`
`response
`
`-J
`Set ready in response
`
`.3‘.
`Sent external message
`connect request resp.
`. a
`
`Set newcomer’:
`hoIes_to_61l
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 27 of 59 PageID #: 352
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 27 of 59 Page|D #: 352
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 23 of 39
`
`US 6,920,497 B1
`
`Add neighbor
`
`I
`
`Identifies calling party
`
`Fig. I 7
`
`I
`
`Sets neighbor to
`messages pending
`
`703 Y
`
`_ '-'_N
`
`C
`
`,
`
`I:
`
`I
`
`50
`
`Add as neighbor
`
`CA0
`Install interal dispatcher
`for new neighbor
`
`707
`
`W Y
`
`N 1
`
`
`
`
`709
` Holes = 3
`xpected 1101 ‘—~
`
`
`
`
`‘’ II
`
`N
`
`1711
`Hole - - 0
`
`Y
`
`N
`
`Purge pending edges
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 28 of 59 PageID #: 353
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 28 of 59 Page|D #: 353
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 24 of 39
`
`US 6,920,497 B1
`
`Forward connection
`358° 33”“
`
`requester
`distance remaining
`
`Fig. 18
`
`
`
`neighbor S
`
`requester
`
`
`
`1 08
`
`Note connection edge
`search call
`
`18 -
`
`Select random neighbor
`
`
`
`All neighbors
`selected
`
`N
`
`1 806
`
`Send internal message
`
`
`
`1807
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 29 of 59 PageID #: 354
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 29 of 59 Page|D #: 354
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 25 of 39
`
`US 6,920,497 B1
`
`Handle edge
`P'°P°5‘1 °3“
`
`in message
`out message
`
`Fig. 19
`
`
`
`Send external message
`
`1912
`Holes odd
`
`N
`
`Y
`
`.
`
`ll Add edge as pending
`
`w ll
`
`1910
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 30 of 59 PageID #: 355
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 30 of 59 Page|D #: 355
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 26 of 39
`
`US 6,920,497 B1
`
`Handle port
`connection call
`
`Fig. 20
`
`2001
`
`'
`
`Holes > 0
`
`N
`
`910
`
`Szand. eittemal message
`pom -connechres
`not 01:)
`P
`
`Cane, is not
`-
`"eight"
`
`Y
`
`, 04
`
`Send external message
`(point-connect-resp, ok) .
`
`
`
`2006
`
`'
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 31 of 59 PageID #: 356
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 31 of 59 Page|D #: 356
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 27 of 39
`
`US 6,920,497 B1
`
`Distnbute internal
`
`message
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 32 of 59 PageID #: 357
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 32 of 59 Page|D #: 357
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 28 of 39
`
`US 6,920,497 B1
`
`Internal
`dispatcher
`
`2201
`
`Fig. 22
`
`2
`
`
`= = broadcast
`
`
`statement
`
`2005
`
`I Handle broadcast
`
`"‘°‘-“B9
`
`Insenme
`
`Partially co
`
`pending connecuon buffer
`
`Y
`
`2007
`
`Handle shutdown
`
`‘ statement I
`
`Pending
`connection buffer
`
`
`"N I
`
`12
`
`Receive response ( )
`
`
`
`Y
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 33 of 59 PageID #: 358
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 33 of 59 Page|D #: 358
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 29 of 39
`
`US 6,920,497 B1
`
`Fig. 23
`
`
`
`2 die broadcast
`message
`
`
`2301
`
`075891
`from neighbor
`message
`
`Process out of order
`
`message
`
`
`
`
`
`2302
`
`Dism'bute'broadcast
`
`massage
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 34 of 59 PageID #: 359
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 34 of 59 Page|D #: 359
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 30 of 39
`
`US 6,920,497 B1
`
`1738- 24
`
`Distribute
`
`
`
`2401
`
`31355389
`
`from neighbor
`
`
`
`Select next neighbor
`
`
`
`2403
`
`
`
`Send internal
`
`message
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 35 of 59 PageID #: 360
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 35 of 59 Page|D #: 360
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 31 of 39
`
`US 6,920,497 B1
`
`Handle connection
`£0!’ search
`
`from neighbor
`mgssagg
`
`2601
`
`Distribute imemal
`
`n-g.26
`
`02
`
`Y
`
`” @
`
`
`
`~ Is requestor
`a neighbor
`
`N
`
`OJ.‘
`
`.ll
`
`
`
`nerate
`condmon check
`messaew/nei u 9
`
`2607
`
`Send intemal message
`to requester
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 36 of 59 PageID #: 361
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 36 of 59 Page|D #: 361
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 32 of 39
`
`US 6,920,497 B1
`
`Court neighbor
`
`Pmspect
`
` N
`
`Fig. 27
`
`2702
`
`Dial prospect
`
`703
`
`N
`
`
`
`U
`
`9.:
`
`Send and receive
`external message
`
`U
`
`Add neighbor
`
`2706
`
`Hang up prospect
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 37 of 59 PageID #: 362
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 37 of 59 Page|D #: 362
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 33 of 39
`
`US 6,920,497 B1
`
`edge search call
`
`"°‘” "°“‘*“’°'
`message
`
`
`
`801
`
`my message 1 1
`
`holes >= Z
`
`Not
`
`
`connection second
`edge (requester
`
`remamm disc -1
`
`.
`
`
`
`
`
`Message
`from this pt. &&
`oles = = 1
`
`
`
`y
`
`2314
`
`
`
`|
`I
`Fill hole(self)
`2815
`‘
`' Intern»
`message (from '
`
`5‘
`
`nei ; her an}:
`
`
`
`
`
`connection ge
`
`r or edge
`search (requester,
`0)
`"°5°“’°d
`
`
`
`I
`
`V‘!
`
`806
`
`2807
`
`Send and receive
`external message
`
`808
`
`is edge acceptable N
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 38 of 59 PageID #: 363
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 38 of 59 Page|D #: 363
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 34 of 39
`
`US 6,920,497 B1
`
`Handle edge search
`7959-
`
`6 ,
`Note connection edge
`
`
`
`origin
`from neighbor
`message
`
`
`
`_
`Flg. 29
`
`
`
`search response Reserve edge offrom
`
`neighbor
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 39 of 59 PageID #: 364
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 39 of 59 Page|D #: 364
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 35 of 39
`
`US 6,920,497 B1
`
`message
`
`Fig. 30
`
`001
`
`Any neighbors
`
`
`
`
`
`Y
`
`3002
`
`Generate internal
`
`message
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 40 of 59 PageID #: 365
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 40 of 59 Page|D #: 365
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 36 of 39
`
`US 6,920,497 B1
`
`message
`
`Fig. 31
`
`3101
`
`Pop message queue
`
`
`
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 41 of 59 PageID #: 366
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 41 of 59 Page|D #: 366
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 37 of 39
`
`US 6,920,497 B1
`
`
`
`Set up message with list
`of neighbors
`
`' eat _a mug - -
`of sendmg process
`not
`nei bor
`
`'
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 42 of 59 PageID #: 367
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 42 of 59 Page|D #: 367
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 38 of 39
`
`US 6,920,497 B1
`
`
`
`
` _Select a neighbor not
`Involved in condition
`
`Remove selected
`neighbor
`
`Hanqle condition
`repair statement
`
`'
`
`
`
`Fig. 33
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 43 of 59 PageID #: 368
`Case 1:15—cv—OO228—RGA Document 1-6 Filed 03/11/15 Page 43 of 59 Page|D #: 368
`
`U.S. Patent
`
`Jul. 19,2005
`
`Sheet 39 of 39
`
`US 6,920,497 B1
`
`
`
`Handle condition
`double check
`
`
`
`3401
`
`Holes == == 1
`
`N
`
`Fig. 34
`
`Same
`
`| -
`
`Holes == = O
`
`
`
`
`
`to-from neighbor
`
`. . .
`
`
`
`
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 44 of 59 PageID #: 369
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 44 of 59 Page|D #: 369
`
`US 6,920,497 B1
`
`1
`CONTACTING A BROADCAST CHANNEL
`
`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, now U.S. Pat. No.
`6,829,634; U.S. patent application Ser. No. 09/629,570,
`entitled “JOINING A BROADCASTING CHANNEL,”
`filed on Jul. 31, 2000; U.S. patent application Ser. No.
`09/629,577, entitled “LEAVING A BROADCAST
`CHANNEL,” filed on Jul. 31, 2000, now U.S. Pat. No.
`6,732,147; 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,023, entitled “DISTRIBUTED AUCTION
`SYSTEM,” filed on Jul. 31, 2000; U.S. patent application
`Ser. No. 09/629,043, entitled “AN INFORMATION DELIV-
`ERY SERVICE,” filed on Jul. 31, 2000, now U.S. Pat. No.
`6,714,966; U.S. patent application Ser. No. 09/629,024,
`entitled “DISTRIBUTED CONFERENCING SYSTEM,”
`filed on Jul. 31, 2000; and U.S. patent application Ser. No.
`09/629,042, entitled “DISTRIBUTED GAME
`ENVIRONMENT,” filed on Jul. 31, 2000, now U.S. Pat. No.
`6,701,344, the disclosures of which are incorporated herein
`by 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
`
`There are a wide variety of computer network 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
`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 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-
`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 manage its 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
`
`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
`
`2
`
`(“CORBA”). Client/server middleware systems are not par-
`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
`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 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
`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-
`tocols tend to place an unacceptable overhead on 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 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
`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 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.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`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
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`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. 5C illustrates the neighbors with empty ports con-
`dition.
`
`60
`
`65
`
`FIG. 5D illustrates two computers that are not neighbors
`who now have empty ports.
`
`

`
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 45 of 59 PageID #: 370
`Case 1:15-cv-00228-RGA Document 1-6 Filed 03/11/15 Page 45 of 59 Page|D #: 370
`
`US 6,920,497 B1
`
`3
`FIG. 5E illustrates the neighbors with empty ports con-
`dition in the small regime.
`FIG. 5F illustrates 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 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
`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. 15 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.
`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
`embodiment.
`
`FIG. 27 is a flow diagram illustrating the processing of the
`court neighbor routine in one embodiment.
`FIG. 28 is a flow diagram il