Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 1 of 58 PageID #: 716
`
`Exhibit 5
`
`           
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 2 of 58 PageID #: 717
`
`(12) United States Patent
`H0lt et al.
`
`(10) Patent N0.:
`(45) Date 0f Patent:
`
`US 6,910,069 B1
`Jun. 21, 2005
`
`US006910069B1
`
`(54) JOININGA BROADCAST CHANNEL
`
`5,696,903 A 12/1997 Mahany
`5,732,074 A
`3/1998 Spaur et a1.
`
`
`
`Inventors: Fred l3I Holt, Seattle, E_ Bourassa Bellevue WA (Us)
`
`
`
`A * 5,732,219 A
`
`
`
`. . . . . . . . . . . . . . .. Liang Ct 8.1. 3/1998 Blumer et a1.
`
`
`
`’
`’
`-
`_
`-
`(73) Assignee. gflhgBoemg Company, Seattle, WA
`
`5,734,865 A
`5,737,526 A
`5,754,830 A
`
`3/1998 Yu
`4/1998 Periasamy et a1.
`5/1998 Butts et a1‘
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U'S'C' 154(k)) by 708 days‘
`
`(21) Appl- NO? 09/ 629,570
`22 Fl 01:
`1. 31 2000
`(
`)
`1 6
`Ju
`’
`(51) Int. Cl.7 ............................................ .. G06F 15/177
`(52) US. Cl. ..................... .. 709/221; 709/252; 709/243;
`709/227
`(58) Field of Search ............................... .. 709/221, 220,
`709/252, 243, 227, 223, 204, 238; 370/225,
`260, 400; 455/428
`
`(Continued)
`OTHER PUBLICATIONS
`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~*
`Bandyopadhyay et al., “A Flexible Architecture for Multi—
`Hop Optical Networks,” Oct. 1998, 7th International Con
`ferenoe on Computer Communications and Networks, 1998,
`pp- 472—478-*
`
`d
`C t-
`( on me )
`Primary Examiner—Glenton B. Burgess
`Assistant Examiner—Bradley Edelman
`(74) Attorney, Agent, or Firm—Perkins Coie LLP
`(57)
`ABSTRACT
`
`A technique for adding a participant to a network is pro
`vided. This technique allows for the simultaneous sharing of
`information among many participants in a network without
`the placement of a high overhead on the underlying com
`munication network. To connect to the broadcast channel, a
`seeking computer ?rst locates a computer that is fully
`connected to the broadcast channel. The seeking computer
`then establishes a connection with a number of the comput
`ers that are already connected to the broadcast channel. The
`technique for adding a participant to a network includes
`identifying a pair of participants that are connected to the
`network, disconnecting the participants of the identi?ed pair
`from each other, and connecting each participant of the
`identi?ed pair of participants to the added participant.
`
`17 Claims, 39 Drawing Sheets
`
`(56)
`
`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 >>>>>>>>>>>>>>>>J>>
`
`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
`
`Cain et a1.
`
`Mansour et a1.
`Perlman
`Crookshanks ............ .. 455/13.1
`
`Shin et al. ................ .. 710/317
`Hauptschein et a1. ..... .. 370/255
`Perlman et a1.
`Opher et 81.
`Derby et a1.
`Bodner et a1.
`Napolitano, Jr. .......... .. 709/243
`Perlman et a1.
`Amri et a1.
`Sitbon et 81.
`Yu
`Kikinis
`Gupta et a1.
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 3 of 58 PageID #: 718
`
`US 6,910,069 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`OTHER PUBLICATIONS
`
`5,757,795
`5,761,425
`5,764,756
`5,790,548
`5,790,553
`5,799,016
`5,802,285
`5,850,592
`5,864,711
`5,867,660
`5,867,667
`5,870,605
`5,874,960
`5,899,980
`5,907,610
`5,925,097
`5,928,335
`5,935,215
`5,946,316
`5,948,054
`5,949,975
`5,953,318
`5,956,484
`5,970,232
`5,974,043
`5,987,506
`6,003,088
`6,013,107
`6,023,734
`6,029,171
`6,032,188
`6,038,602
`6,047,289
`6,065,063
`6,073,177
`6,094,676
`6,115,580
`6,151,633
`6,167,432
`6,173,314
`6,195,366
`6,199,116
`6,216,177
`6,223,212
`6,243,691
`6,252,884
`6,268,855
`6,269,080
`6,271,839
`6,272,548
`6,285,363
`6,304,928
`6,321,270
`6,353,599
`6,415,270
`6,434,622
`6,463,078
`6,490,247
`6,499,251
`6,505,289
`6,524,189
`6,553,020
`6,603,742
`6,611,872
`6,618,752
`6,701,344
`2002/0027896
`
`5/1998
`6/1998
`6/1998
`8/1998
`8/1998
`8/1998
`9/1998
`12/1998
`1/1999
`2/1999
`2/1999
`2/1999
`2/1999
`5/1999
`5/1999
`7/1999
`7/1999
`8/1999
`8/1999
`9/1999
`9/1999
`9/1999
`9/1999
`10/1999
`10/1999
`11/1999
`12/1999
`1/2000
`2/2000
`2/2000
`2/2000
`3/2000
`4/2000
`5/2000
`6/2000
`7/2000
`9/2000
`11/2000
`12/2000
`1/2001
`2/2001
`3/2001
`4/2001
`4/2001
`6/2001
`6/2001
`7/2001
`7/2001
`8/2001
`8/2001
`9/2001
`10/2001
`11/2001
`3/2002
`7/2002
`8/2002
`10/2002
`12/2002
`12/2002
`1/2003
`2/2003
`4/2003
`8/2003
`8/2003
`9/2003
`3/2004
`3/2002
`
`Schnell
`Miller
`Onweller
`SistaniZadeh et al.
`Deaton, Jr. et al.
`Onweller
`Hirviniemi
`Ramanathan
`Mairs et al.
`Schmidt et al.
`Butman et al.
`Bracho et al.
`Mairs et al.
`Wilf et al.
`Onweller
`Gopinath et al.
`Morita
`Bell et al.
`Chen et al.
`Nielsen
`Batty et al.
`Nattkemper et al.
`Rosenberg et al.
`Passint et al.
`Solomon
`Carter et al.
`Houston et al.
`Blackshear et al.
`Ratcliff et al.
`Smiga et al.
`Mairs et al.
`Ishikawa
`Thorne et al.
`
`Abali ....................... .. 709/242
`Hebel et al.
`Gray et al.
`Chuprun et al.
`Hurst
`Jiang
`Kurashima et al.
`Kayashima
`May et al.
`Mairs et al.
`Batty et al.
`Fisher et al.
`Hunter
`Mairs et al.
`Kumar
`Mairs et al.
`Cotter et al.
`Mairs et al.
`Mairs et al.
`Crawley
`Bi et al.
`Rackson et al.
`Monteiro et al.
`Engstrom et al.
`Gilbert et al. ............ .. 370/222
`Weder
`Han et al. ................... .. 712/11
`Rautila
`Hughes et al. ............ .. 370/347
`Steele et al. .............. .. 370/254
`McCanne
`Moore et al.
`Holt et al.
`Hughes et al.
`
`Hsu, “On Four—Connecting a Triconnected Graph,” Oct.
`1992, Annual Symposium on Foundations of Computer
`Science, 1992, pp. 70—79.*
`Shiokawa et al., “Performance Analysis of 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. 199 IEEE Globecom ’90, ‘Communications: Connect
`ing the Future,’ vol. 1, pp. 459—463.*
`U.S. Appl. No. 09/629,576, ?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
`U.S. Appl. No.
`09/629,572, ?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
`U.S. 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, 2003].
`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).
`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.
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 4 of 58 PageID #: 719
`
`US 6,910,069 B1
`Page 3
`
`The Common Object Request Broker: Architecture and
`Speci?cation, RevieW 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).
`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.htm.
`
`Business Wire, “Boeing Panthesis Complete SWAN Trans
`action,” Jul. 22, 2002, pp 1ff.
`
`PR NeWsWire, “Microsoft Annouces Launch Date for
`UltraCrops, Its Second Premium Title for the Internet Gam
`ing Zone,” Mar. 27, 1998, pp1 ff.
`
`PR NeWsWire, “Microsoft Boosts Accessibility to Internet
`Gaming Zone With Latest Release,” Apr. 27, 1998, pp 1ff.
`
`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.
`
`AZar et al., “Routing Strategies for Fast NetWorks,” May
`1992, INFOCOM ’92 Eleventh Annual Joint Conference of
`the IEEE Computer Communications Societies, vol. 1,
`170—179###.
`
`* cited by examiner
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 5 of 58 PageID #: 720
`
`U.S. Patent
`
`Jun. 21,2005
`
`Sheet 1 0f 39
`
`US 6,910,069 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 6 of 58 PageID #: 721
`
`U.S. Patent
`
`Jun 21 2005
`
`A,
`6
`
`m w
`
`Q
`
`m @ \\\\ ‘ 2
`
`m a 2 S
`
`M, N .ME
`
`m \K“ “VI-l",
`
`wt“
`\\ )/ x h R 1 P/ 2
`
`w ‘ '. NF
`
`
`
`a‘ 1.,
`
`\ ‘?t; _ _‘
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 7 of 58 PageID #: 722
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 3 0f 39
`
`US 6,910,069 B1
`
`mm .ME ‘A. .MR
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 8 of 58 PageID #: 723
`
`U.S. Patent
`
`Jun. 21,2005
`
`Sheet 4 0f 39
`
`US 6,910,069 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 9 of 58 PageID #: 724
`
`U.S. Patent
`
`Jun. 21,2005
`
`Sheet 5 0f 39
`
`US 6,910,069 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 10 of 58 PageID #: 725
`
`U.S. Patent
`
`Jun. 21 2005
`
`Sheet 6 6f 39
`
`US 6,910,069 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 11 of 58 PageID #: 726
`
`U.S. Patent
`
`Jun. 21,2005
`
`Sheet 7 0f 39
`
`US 6,910,069 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 12 of 58 PageID #: 727
`
`U.S. Patent
`
`Jun. 21,2005
`
`Sheet 8 0f 39
`
`US 6,910,069 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 13 of 58 PageID #: 728
`
`U.S. Patent
`
`Jun. 21,2005
`
`Sheet 9 0f 39
`
`US 6,910,069 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 14 of 58 PageID #: 729
`
`U.S. Patent
`
`Jun. 21,2005
`
`Sheet 10 0f 39
`
`US 6,910,069 B1
`
`III
`
`<
`
`E
`“=z ‘N k,
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 15 of 58 PageID #: 730
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 11 0f39
`
`US 6,910,069 B1
`
`E .ME E .5
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 16 of 58 PageID #: 731
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 16 of 58 Page|D #: 731
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 12 of 39
`
`US 6,910,069 B1
`
`600
`
`:3‘
`
`E
`2
`"3
`
`1..
`
`'3,
`3
`an
`
`
`
`Apphcauon1 (channeltype
`
`'8?
`
`:2’
`g
`
`‘OI
`
`-E“
`
`""
`
`'2
`8
`9'-5
`
`
`Application2 (channel
`
`typechannelinstance)
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 17 of 58 PageID #: 73223
`e
`1egaP
`67
`C
`
`E9/31.n.l%00Bm.mH%
`
`90.,a0P189956mS7U
`
`_H1#Bmm
`
`
`
` flP1O%S.aU
`
`mMmm.U9C102Dn.uMugJ%uonosuau2t_aE2xm0nmu6VtCa
`_S»
`
`Soccou
`
`8»
`
`.8550
`
`8030..
`
`NE.
`
`§.uuao.m
`
`X:
`
`E__..co<
`
`ummmmos
`
`on
`
`.ooE.8U
`
`.3;=8
`
`FF
`
`ozooom
`
`umconmo.
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 18 of 58 PageID #: 733
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 14 0f 39
`
`US 6,910,069 B1
`
`(Channei Type,
`Channel Instance,
`Connect Aux Info)
`
`Fig. 8
`
`(
`
`Connect
`
`)
`
`801
`
`802
`
`Open call in pon
`
`Set connect-time
`
`803
`Seek portal - computer
`(channel type channel
`instance)
`
`'
`
`806
`
`Achieve connection
`
`807
`
`Install external dispatcher
`
`Contacts
`
`Install external dispatcher
`
`809
`
`Connect request
`
`1
`
`{
`
`Return (true)
`
`>
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 19 of 58 PageID #: 734
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 15 0f 39
`
`US 6,910,069 B1
`
`<
`
`s°ek P0mil
`compute‘
`'
`
`Select next depth
`
`)
`
`Channel Type
`Channel Instance
`
`902
`
`All depths selected
`
`904
`Select next portal computer
`
`All portal computers
`selected
`
`906
`Dial portal computer
`
`N
`
`907
`
`Y
`
`908
`
`Contact process
`I
`909
`Hang up selected portal
`computer
`
`911
`Check for external
`call
`
`computer connected
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 20 of 58 PageID #: 735
`
`U.S. Patent
`
`Jun. 21,2005
`
`Sheet 16 0f 39
`
`US 6,910,069 B1
`
`( Contact process >
`
`1001
`Send external message
`
`1002
`Receive external message
`
`1 0
`
`1 005
`Add as connected portal
`computer
`
`Answering process
`connected
`
`1 006
`Add as fellow seeking
`computer
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 21 of 58 PageID #: 736
`
`U.S. Patent
`
`Jun. 21,2005
`
`Sheet 17 0f 39
`
`US 6,910,069 B1
`
`1 102
`
`Restart
`
`Return
`
`Fig. 11
`
`Dial call in port of portal
`computer
`
`Success
`
`1105
`Send external message
`l
`1106
`Receive external message
`
`1108
`Set expect holes from
`response
`1 109
`l
`Set diameter ?'om response
`
`1 1 1
`Ready to connect
`
`Y
`
`1 1 12
`Add neighbor
`
`N‘
`Hangup
`
`1113
`
`Return
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 22 of 58 PageID #: 737
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 22 of 58 Page|D #: 737
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 18 of 39
`
`US 6,910,069 B1
`
`heck for extem
`
`call
`
`Fig. 12
`
`1 202
`
`
`
`Receive external message
`
`ype==seeking
`
`connection call
`
`Send external message
`
`
`
`
`
`Add other as fellow seeker
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 23 of 58 PageID #: 738
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 23 of 58 Page|D #: 738
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 19 of 39
`
`US 6,910,069 B1
`
`Achieve connection
`
`
`
`
`
`
`
`
`
`Connection - state - fully
`connected
`
`1301
`
`
`
`Fig. 13
`
`Notify fellow seekers
`
`1303
`
` 1302
`
`
`Invoke connect call back
`
`
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 24 of 58 PageID #: 739
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 24 of 58 Page|D #: 739
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 20 of 39
`
`US 6,910,069 B1
`
`Fig- 14
`
`H dl
`
`rt
`
`Connected statement
`
`Handle connected
`statement
`
`Condition repair
`statemem
`
`Handle condition
`repair statement
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 25 of 58 PageID #: 740
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 25 of 58 Page|D #: 740
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 21 of 39
`
`US 6,910,069 B1
`
`Handle seeking
`connection call
`
`Fig. 15
`
`1 503
`
`I
`
`' d’ ate
`
`Add other as fellow
`seeking process
`
`
`
`1505
`
`Send external message
`
`
`
`
`
`Set message to not
`
`Set
`
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 26 of 58 PageID #: 741
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 26 of 58 Page|D #: 741
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 22 of 39
`
`US 6,910,069 B1
`
`andle connection
`request call
`
`1601
`
`N
`
`Set newcomers
`holes to expect
`
`° '
`
`o‘.__‘
`
`response
`
`C“
`
`nip
`
`Sent extemal message
`
`ho1es_to__fill
`
`. c
`
`608
`
`,
`
`._,o
`
`Return
`
`,
`Flg. 16
`
`|
`
`Add neighbor
`
`' "
`
`|
`
`.
`
`0
`
`
`
`Holes to fiil - =
`
`
`
`
`was to fin) . -YI Fillhole(requester) I
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 27 of 58 PageID #: 742
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 27 of 58 Page|D #: 742
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 23 of 39
`
`US 6,910,069 B1
`
`Add neighbor
`
`I
`
`Identifies calling party
`
`Flg- 1 7
`
`0.
`
`Sets neighbor to
`messages pending
`
`.
`7.03 Y
`Connection__state =
`4.eekmg connecno - pmfiauy connected
`
`N
`
`1705
`
`Add as neighbor
`
`0 .
`Install interal dispatche
`for new neighbor
`
`707
`
`CommW
`
`.0.‘
`
`0:
`
`0
`
`-
`
`I Achieve connected |
`
`
`
`
`1 709
`
` Holes = =
`
`
`- ected hole
`
`N
`
`1711
`
`Purge pending edges
`
`N
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 28 of 58 PageID #: 743
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 28 of 58 Page|D #: 743
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 24 of 39
`
`US 6,910,069 B1
`
`Fig. 18
`
`Forward connection
`
`requester
`
`edge search
`
`distance remaining
`
`
`
`
`
`neighbors
`
`
`
`All neighbors
`selected
`
`YGQUCSIOY
`
`
`
`N
`
`Send intemal message
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 29 of 58 PageID #: 744
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 29 of 58 Page|D #: 744
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 25 of 39
`
`US 6,910,069 B1
`
`Handle edge
`PT°P°Sa1 473“
`
`in message
`out message
`
`Fig. 19
`
`Send external message
`
`N
`
`.
`
`907
`
`1912
`
`1908
`
`V
`
`I
`
`.
`1 . 13
`
`Y
`
`Fm hole
`
`Y
`
`1909
`
`Add edge as pending
`
`g I
`
`1910
`
`11,110,
`
`|
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 30 of 58 PageID #: 745
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 30 of 58 Page|D #: 745
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 26 of 39
`
`US 6,910,069 B1
`
`Handle port
`
`connection call Fig. 20
`
`2003
`
`-
`Can?’ '3 mt
`neighbor
`
`
`
`Send external message
`(point-connect-resp
`not ok)
`
`Send extemal message
`(point-connect-resp, ok)
`
`
`
`
`
`I Connect request I
`
`
`
`2006
`
`I
`
`Add neighbor
`
`I
`
`2008
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 31 of 58 PageID #: 746
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 31 of 58 Page|D #: 746
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 27 of 39
`
`US 6,910,069 B1
`
`Fill hole
`
`
`
`Handle connection
`ports search edit
`
`
`
`2103
`
`Distribute internal
`message
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 32 of 58 PageID #: 747
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 32 of 58 Page|D #: 747
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 28 of 39
`
`US 6,910,069 B1
`
`Fig 22
`
`Internal
`dispatcher
`
`2201
`
`Received internal message
`2202
`
`Assess diameter
`
`203
`
`2203A
`
`
`
`P
`
`anially connected
`
`Type
`= = broadcast
`
`Type
`
`
`
`statement
`
`
`Y
`
`mC5SagC
`
`statement
`
`2005
`
`2007
`
`Y
`
`I
`
`I
`
`pending connection buffer
`
`Y
`
`
`
`
`
`Pending
`connection bufier
`
`..
`“
`
`message queue
`°’“ 22 2
`
`Y
`
`Receive résponse ( )
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 33 of 58 PageID #: 748
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 33 of 58 Page|D #: 748
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 29 of 39
`
`US 6,910,069 B1
`
`_
`03°89‘
`from flBlghbO1'
`message
`
`2304
`
`Clear out of order info
`
`
`
`2302
`
`Distribute broadcast
`
`message
`
`Fig. 23
`
`andle broadcast
`message
`
`
`
`2301
`Process out of order
`
`message
`
`
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 34 of 58 PageID #: 749
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 34 of 58 Page|D #: 749
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 30 0f 39
`
`US 6,910,069 B1
`
`,
`Fig. 24
`
`Distribute
`broadcast message
`
`message
`
`from neighbor 2401
`message
`
`Select next neighbor
`
`All neighbor
`seiected
`
`Send internal
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 35 of 58 PageID #: 750
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 35 of 58 Page|D #: 750
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 31 of 39
`
`US 6,910,069 B1
`
`Handle connection
`for search
`
`from neighbor
`message
`
`2 n
`
`Distribute internal
`
`_F’3- 36
`
`602
`
`N
`
`Y
`
`
`
`603
`
`Is requester
`a neighbor
`
`
`
`2604
`
`” II
`
`05
`
`ncrate
`
`condition check
`mes 2 e wineahbors
`
`
`
`2607
`
`Send internal message
`to requester
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 36 of 58 PageID #: 751
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 36 of 58 Page|D #: 751
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 32 of 39
`
`US 6,910,069 B1
`
`N
`
`
`
`2706
`
`Hang up prospect
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 37 of 58 PageID #: 752
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 37 of 58 Page|D #: 752
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 33 0f 39
`
`US 6,910,069 B1
`
`Handle connection
`fiigB search
`
`Rom neighbor
`mgggage
`
`801
` Not
`my message 1 1
`holes >= 2
`
`
`
`
`connection second
`edge (requester
`
`re " dist-1
`
`
`
`Forward
`
`connection edge
`
`ed
`search (requester,
`0)
`
`‘
`2806
`
`V-V
`V
`
`2807
`
`Send and receive
`external message
`
`808
`
`is edge acceptable N
`
`
`
`2812
`
`Fig. 28
`
`281 3
`
`Message
`
`In this pt. &&
`
`
`3
`
`en mtem
`message (from
`nei bor ack
`
`Nfro
`
`Y
`
`Fillho1e(se1t)
`
`2814
`
`|
`
`2815
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 38 of 58 PageID #: 753
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 38 of 58 Page|D #: 753
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 34 of 39
`
`US 6,910,069 B1
`
`Handle edge search
`T8813.
`
`origin
`from neighbor
`
`Fig. 29
`
`Note connection edge
`search response
`
`Edge selcctcd
`
`904
`
`Y
`
`2908
`
`I
`
`Filiholc (self)
`
`I
`
`
`
`
`
`
`Y
`
`, .
`
`Reserve edge of from
`
`2905
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 39 of 58 PageID #: 754
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 39 of 58 Page|D #: 754
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 35 0f 39
`
`US 6,910,069 B1
`
`
`
` Y
`
`3002
`
`Generate internal
`
`message
`
`3003
`
`Set message sequence
`number
`
`3004
`
`message
`
`Distribute internal
`
`
`
`
`
`
`
`Fig. 30
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 40 of 58 PageID #: 755
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 40 of 58 Page|D #: 755
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 36 0f 39
`
`US 6,910,069 B1
`
`Acquire message
`
`message
`
`Fig. 31
`
`3101
`
`Pop message queue
`
`
`
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 41 of 58 PageID #: 756
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 41 of 58 Page|D #: 756
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 37 0f 39
`
`US 6,910,069 B1
`
`andle condition check
`
`
`
`Fig. 32
`
`
`
`neighbors
`
`
`
`Set up message with list
`of neighbors
`
`3205
`e eat a nea or
`
`of sendmg process
`not In neihbor
`
`
`
`
` 3206
`
`3207
`
`I
`
`Add neighbor
`
`I
`
`
`
`.
`Send mtcmal message
`
`Send external message
`to selected neighbor
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 42 of 58 PageID #: 757
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 42 of 58 Page|D #: 757
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 38 0f 39
`
`US 6,910,069 B1
`
`Handle condition
`
`repair statement
`
`
`
`Select a neighbor not
`involved in condition
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 43 of 58 PageID #: 758
`Case 1:15—cv—OO228—RGA Document 7-5 Filed 03/31/15 Page 43 of 58 Page|D #: 758
`
`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 39 0f 39
`
`US 6,910,069 B1
`
`
`
`Same set of
`
`nmghbors
`
` . | .
`
`Send internal message
`to-from neighbor
`
`
`
`Send internal message
`
`

`
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 44 of 58 PageID #: 759
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 44 of 58 Page|D #: 759
`
`US 6,910,069 B1
`
`1
`JOINING 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; 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; U.S. patent application
`Ser. No. 09/629,575, entitled “BROADCASTING ON A
`BROADCAST CHANNEL,” filed on Jul. 31, 2000; U.S.
`patent application Ser. No. 09/629,572, entitled “CON-
`TACTING A BROADCAST CHANNEL,” filed on Jul. 31,
`2000; U.S. patent application Ser. No. 09/629,023, entitled
`“DISTRIBUTED AUCTION SYSTEM,” filed on Jul. 31,
`2000; U.S. patent application Ser. No. 09/629,043, entitled
`“AN INFORMATION DELIVERY SERVICE,” filed on Jul.
`31, 2000, now U.S. Pat. No. 6,714,966; U.S. patent appli-
`cation Ser. No. 09/629,024, entitled “DISTRIBUTED CON-
`FERENCING SYSTEM,” filed on Jul. 31, 2000; and U.S.
`patent application Ser. No. 09/629,042, entitled “DISTRIB-
`UTED GAME ENVIRONMENT,” filed on Jul. 31, 2000,
`the disclosures of which are incorporated herein by refer-
`ence.
`
`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 callback 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 7-5 Filed 03/31/15 Page 45 of 58 PageID #: 760
`Case 1:15-cv-00228-RGA Document 7-5 Filed 03/31/15 Page 45 of 58 Page|D #: 760
`
`US 6,910,069 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 routin