II
`US006910069B1
`US006910069B1
`US 6,910,069 B1
`US 6,910,069 B1
`(10) Patent No.:
`(io) Patent No.:
`Jun. 21,2005
`(45) Date of Patent:
`Jun. 21, 2005
`(45) Date of Patent:
`
`of
`
`(12) United States Patent
`(12) United States Patent
`Holt et al.
`Holt et al.
`
`CHANNEL
`(54) JOINING A BROADCAST
`(54) JOINING A BROADCAST CHANNEL
`(US); Virgil
`Inventors: Fred B. Holt, Seattle, WA
`(75)
`(75) Inventors: Fred B. Holt, Seattle, WA (US); Virgil
`E. Bourassa, Bellevue, WA (US)
`E. Bourassa, Bellevue, WA (US)
`2
`2
`-
`-
`e
`(73) Assignee: The Boeing Company, Seattle, WA
`(73) Assignee: * Company, Seattle, WA
`(US)
`
`(*) Notice:
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`term this
`
`the
`Subject to any disclaimer,
`patent is extended or adjusted under 35
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 708 days.
`U.S.C. 154(b) by 708 days.
`(21) Appl. No.: 09/629,570
`(21) Appl. No.: 09/629,570
`22) Filed:
`I. 31, 2000
`Jul. 31, 2000
`(22) Filed:
`Ju
`9
`(22) File
`G06F 15/177
`(51) Int. CI.7
`(51) Int. Cl." .............................................. G06F 15/177
`(52) U.S. Cl. ....................... 709/221; 709/252; 709/243;
`(52) U.S. CI.
`709/221; 709/252; 709/243;
`709/227
`709/227
`709/221, 220,
`(58) Field of Search
`(58) Field of Search ................................. 709/221, 220,
`709/252, 243, 227, 223, 204, 238; 370/225,
`709/252, 243, 227, 223, 204, 238; 370/225,
`260, 400; 455/428
`260, 400; 455/428
`
`12/1997 Mahany
`5,696,903 A
`5,696,903 A 12/1997 Mahany
`3/1998 Spaur et al.
`5,732,074 A
`5,732,074 A 3/1998 Spaur et al.
`370/410
`5,732,086 A *
`3/1998 Liang et al
`5,732,086 A * 3/1998 Liang et al. ................ 370/410
`5,732,219 A
`3/1998 Blumer et al.
`5,732,219 A 3/1998 Blumer et al.
`5,734,865 A
`3/1998 Yu
`5,734,865 A 3/1998 Yu
`5,737,526 A
`4/1998 Periasamy et al.
`5,737,526 A
`4/1998 Periasamy et al.
`5,754,830 A 5/1998 Butts et al.
`5,754,830 A
`5/1998 Butts et al.
`(Continued)
`(Continued)
`OTHER PUBLICATIONS
`OTHER PUBLICATIONS
`Cho et al., “A Flood Routing Method for Data Networks,”
`Cho et al., "A Flood Routing Method for Data Networks,"
`Sep.1997, Proceedings of 1997 International Conference on
`Sep. 1997, Proceedings of 1997
`International
`
`Conference on
`Information, Communications and Signal Processing, vol. 3,
`Information, Communications
`and
`
`Signal Processing, vol. 3,
`1418-1422.*
`pp. 1418–1422.*
`pp.
`Bandyopadhyay et al., “A Flexible Architecture for Multi
`for Bandyopadhyay et al., "A Flexible Architecture Multi-
`
`
`Hop Optical Networks," Oct. 1998, 7th International Con­
`Hop Optical Networks,” Oct. 1998, 7th International Con
`ference on Computer Communications
`and
`Networks,
`ference on Computer Communications and Networks, 1998,
`472-478.*
`pp. 472–478.*
`pp.
`
`Continued
`(Continued)
`(Continued)
`Primary Examiner—Glenton B. Burgess
`Primary Examiner—Glenton B. Burgess
`Assistant Examiner—Bradley Edelman
`Assistant Examiner—Bradley Edelman
`(74) Attorney, Agent, or Firm—Perkins Coie LLP
`(74) Attorney, Agent,
`or Firm—Perkins Coie LLP
`ABSTRACT
`(57)
`ABSTRACT
`(57)
`A technique for adding a participant to a network is pro
`A technique for adding a participant to a network is pro­
`vided. This technique allows for the simultaneous sharing of
`vided. This
`technique
`
`allows for the simultaneous
`sharing
`information among many participants in a network without
`information among many participants
`in a network without
`the placement of a high overhead on the underlying com
`the placement of a high overhead on the underlying com­
`
`munication network. To connect to the broadcast channel, a
`munication network. To connect to the broadcast channel, a
`seeking computer first locates a computer that is fully
`seeking computer first locates a computer that is fully
`connected to the broadcast channel. The seeking computer
`connected to the broadcast channel. The seeking computer
`a connection with a number of the comput­
`then establishes
`then establishes a connection with a number of the comput
`ers that are already connected
`
`to the broadcast channel.
`The
`ers that are already connected to the broadcast channel. The
`technique for adding a participant to a network includes
`technique for adding a participant to a network includes
`identifying a pair of participants that are connected to the
`identifying a pair of participants
`that are connected to the
`network, disconnecting the participants of the identified pair
`network, disconnecting
`the
`participants
`of
`the
`from each other, and connecting each participant of the
`from each other, and connecting each participant of the
`identified pair of participants to the added participant.
`identified pair of participants
`to the added participant.
`
`1998,
`
`of
`
`identified
`
`(56)
`(56)
`
`References Cited
`References Cited
`U.S. PATENT DOCUMENTS
`U.S. PATENT DOCUMENTS
`4,912,656 A
`3/1990 Cain et al.
`4,912,656 A 3/1990 Cain et al.
`5,056,085 A
`10/1991 Vu
`5,056,085 A 10/1991 Vu
`5,058,105 A
`10/1991 Mansour et al.
`5,058,105 A 10/1991 Mansour et al.
`5,079,767 A
`1/1992 Perlman
`5,079,767 A
`1/1992 Perlman
`5,099,235 A *
`3/1992 Crookshanks
`455/13.1
`5,099,235 A * 3/1992 Crookshanks .............. 455/13.1
`5,101,480 A *
`3/1992 Shin et al
`710/317
`5,101,480 A * 3/1992 Shin et al. .................. 710/317
`370/255
`5,117,422 A *
`5/1992 Hauptschein et al.
`5,117,422 A * 5/1992 Hauptschein et al. ....... 370/255
`5,309,437 A
`5/1994 Perlman et al.
`5,309.437 A 5/1994 Perlman et al.
`5,345,558 A
`9/1994 Opher et al.
`5,345,558 A 9/1994 Opher et al.
`5,426,637 A
`6/1995 Derby et al.
`5,426,637 A 6/1995 Derby et al.
`5,459,725 A
`10/1995 Bodner et al.
`5,459,725 A 10/1995 Bodner et al.
`5,471,623 A * 11/1995 Napolitano, Jr.
`709/243
`5,471,623 A * 11/1995 Napolitano, Jr. ............ 709/243
`5,511,168 A
`4/1996 Perlman et al.
`5,511,168 A 4/1996 Perlman et al.
`5,535,199 A
`7/1996 Amri et al.
`5,535,199 A 7/1996 Amri et al.
`5,568,487 A
`10/1996 Sitbon et al.
`5,568,487 A 10/1996 Sitbon et al.
`5,636,371 A
`6/1997 Yu
`5,636,371 A 6/1997 Yu
`5,644,714 A
`7/1997 Kikinis
`5,644,714 A 7/1997 Kikinis
`5,673,265 A
`9/1997 Gupta et al.
`5,673,265 A 9/1997 Gupta et al.
`
`17 Claims, 39 Drawing Sheets
`17 Claims, 39 Drawing Sheets
`
`
`
`Connect request
`
`1101
`.^WwefuUy
`connected portal
`
`1103
`lY
`Dial call in port of portal
`I
`computer
`I
`
`4104
`
`1106
`Send external message
`I
`HQS
`Receive external message
`
`J107
`
`Success
`
`1108
`Set expect holes from
`
`I
`
`1109
`Set diameter from response
`
`1111
`Ready to cooneci
`
`1113
`
`Hangup
`
`^
`
`Return ^
`
`1102
`
`^
`
`Return
`
`J
`
`1112
`Add neighbor
`
`BUNGIE - EXHIBIT 1001
`
`

`

`US 6,910,069 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`OTHER PUBLICATIONS
`
`5/1998 Schnell
`5,757,795 A
`6/1998 Miller
`5,761,425 A
`6/1998 Onweller
`5,764,756 A
`8/1998 Sistanizadeh et al.
`5,790,548 A
`8/1998 Deaton, Jr. et al.
`5,790,553 A
`8/1998 Onweller
`5,799,016 A
`9/1998 Hirviniemi
`5,802,285 A
`12/1998 Ramanathan
`5,850,592 A
`1/1999 Mairs et al.
`5,864,711 A
`2/1999 Schmidt et al.
`5,867,660 A
`2/1999 Butman et al.
`5,867,667 A
`2/1999 Bracho et al.
`5,870,605 A
`2/1999 Mairs et al.
`5,874,960 A
`5/1999 Will et al.
`5,899,980 A
`5/1999 Onweller
`5,907,610 A
`7/1999 Gopinath et al.
`5,925,097 A
`7/1999 Morita
`5,928,335 A
`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 et al.
`5,949,975 A
`9/1999 Nattkemper et al.
`5,953,318 A
`9/1999 Rosenberg et al.
`5,956,484 A
`10/1999 Passint et al.
`5,970,232 A
`10/1999 Solomon
`5,974,043 A
`11/1999 Carter et al.
`5,987,506 A
`12/1999 Houston et al.
`6,003,088 A
`1/2000 Blackshear et al.
`6,013,107 A
`2/2000 Ratcliff et al.
`6,023,734 A
`2/2000 Smiga et al.
`6,029,171 A
`2/2000 Mairs et al.
`6.032.188 A
`3/2000 Ishikawa
`6,038,602 A
`4/2000 Thorne et al.
`6,047,289 A
`5/2000 Abali
`6,065,063 A *
`6/2000 Hebel et al.
`6,073,177 A
`7/2000 Gray et al.
`6,094,676 A
`9/2000 Chupran et al.
`6,115,580 A
`11/2000 Hurst
`6,151,633 A
`12/2000 Jiang
`6,167,432 A
`1/2001 Kurashima et al.
`6,173,314 B1
`2/2001 Kayashima
`6,195,366 B1
`3/2001 May et al.
`6,199,116 B1
`4/2001 Mairs et al.
`6,216,177 B1
`4/2001 Batty et al.
`6,223,212 B1
`6/2001 Fisher et al.
`6,243,691 B1
`6/2001 Hunter
`6,252,884 B1
`7/2001 Mairs et al.
`6,268,855 B1
`7/2001 Kumar
`6,269,080 B1
`8/2001 Mairs et al.
`6,271,839 B1
`8/2001 Cotter et al.
`6,272,548 B1
`9/2001 Mairs et al.
`6,285,363 B1
`10/2001 Mairs et al.
`6,304,928 B1
`11/2001 Crawley
`6,321,270 B1
`3/2002 Bi et al.
`6,353,599 B1
`7/2002 Rackson et al.
`6,415,270 B1
`8/2002 Monteiro et al.
`6,434,622 B1
`10/2002 Engstrom et al.
`6,463,078 B1
`6,490,247 B1 * 12/2002 Gilbert et al. ..
`6,499,251 B2
`12/2002 Weder
`6,505,289 B1 * 1/2003 Han et al
`6.524.189 B1
`2/2003 Rautila
`6,553,020 B1 * 4/2003 Hughes et al. ..
`6,603,742 B1 * 8/2003 Steele et al
`6,611,872 B1
`8/2003 McCanne
`6,618,752 B1
`9/2003 Moore et al.
`6,701,344 B1
`3/2004 Holt et al.
`2002/0027896 Al
`3/2002 Hughes et al.
`
`Hsu, "On Four-Connecting a Triconnected Graph," Oct.
`1992, Annual Symposium on Foundations ol 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, filed Jul. 31, 2000, Bourassa et
`al.
`U.S. Appl. No. 09/629,577, filed Jul. 31, 2000, Bourassa et
`al.
`U.S. Appl. No. 09/629,575, filed Jul. 31, 2000, Bourassa et
`al.
`U.S. Appl. No. 09/629,572, filed Jul. 31, 2000, Bourassa et
`al.
`U.S. Appl. No. 09/629,023, filed Jul. 31, 2000, Bourassa et
`al.
`U.S. Appl. No. 09/629,043, filed Jul. 31, 2000, Bourassa et
`al.
`U.S. Appl. No. 09/629,024, filed Jul. 31, 2000, Bourassa et
`al.
`U.S. Appl. No. 09/629,042, filed 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/
`Ipt/ . . . [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/lpt . . . [Accessed Jan.
`29, 2003],
`Internetworking Technologies Handbook, Chapter 43 (pp.
`43-1^13-16).
`Oram, Andy, "Peer-to-Peer Makes the Internet Interesting
`Again," Sep. 22, 2000 (7 pages) The O'Reilly Network
`http://linux.oreillynet.com/lpt. . . [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/
`rfcl832.html [Accessed Jan. 29, 2002].
`ADatabeam Corporate White Paper, "APrimer 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.eom/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^-7), 1976 American Elsevier
`Publishing Co., Inc., New York, New York.
`Cormen, Thomas, H. et al., Introduction to Algorithms,
`Chapter 5.3 (pp. 84-91), Chapter 12 (pp. 218-243), Chapter
`13 (p. 245), 1990, The MIT Press, Cambridge, Massachu­
`setts, McGraw-Hill Book Company, New York.
`
`709/242
`
`370/222
`
`712/11
`
`370/347
`370/254
`
`

`

`US 6,910,069 B1
`US 6,910,069 B1
`Page 3
`Page 3
`
`The Common Object Request Broker: Architecture and
`The Common Object Request Broker: Architecture and
`Specification, Review 2.6, Dec. 2001, Chapter 12 (pp.
`Specification, Review 2.6, Dec. 2001, Chapter 12 (pp.
`12–1–12–10), Chapter 13 (pp. 13–1–13–56), Chapter 16
`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
`(pp. 16-1-16-26), Chapter 18 (pp. 18-1-18-52), Chapter
`20 (pp. 20–1–20–22).
`20 (pp. 20-1-20-22).
`The University of Warwick, Computer Science Open Days,
`The University of Warwick, Computer Science Open Days,
`"Demonstration on the Problems of Distributed Systems,"
`“Demonstration on the Problems of Distributed Systems,”
`http://www.dcs.warwick.ac.u . . . [Accessed Jan. 29, 2002].
`http://www.dcs.warwick.ac.u . . . [Accessed Jan. 29, 2002].
`Alagar, S. and Venkatesan, S., "Reliable Broadcast in
`Alagar, S. and Venkatesan, S., “Reliable Broadcast in
`Mobile Wireless Networks,” Department of Computer Sci
`Mobile Wireless Networks," Department of Computer Sci­
`ence, University of Texas at Dallas, Military Communica
`ence, University of Texas at Dallas, Military Communica­
`tions Conference, 1995, MILCOM '95 Conference Record,
`tions Conference, 1995, MILCOM '95 Conference Record,
`IEEE San Diego, California, Nov. 5–8, 1995 (pp. 236–240).
`IEEE San Diego, California, Nov. 5-8, 1995 (pp. 236-240).
`International Search Report for The Boeing Company, Inter
`International Search Report for The Boeing Company, Inter-
`national Patent Application No. PCT/US01/24240, Jun. 5,
`national Patent Application No. PCT/US01/24240, Jun. 5,
`2002 (7 pages).
`2002 (7 pages).
`Yavatkar et al., "A reliable Dissemination Protocol for
`Yavatkar et al., “A reliable Dissemination Protocol for
`Interactive Collaborative Applications," Proc. ACM Multi­
`Interactive Collaborative Applications,” Proc. ACM Multi
`media, 1995, p. 333–344; http://citeseer.nj.mec.com/article/
`media, 1995, p. 333-344; http://citeseer.nj.nec.com/article/
`yavatkar'95reliable.htm.
`yavatkar95reliable.htm.
`
`Business Wire, “Boeing Panthesis Complete SWAN Trans
`Business Wire, "Boeing Panthesis Complete SWAN Trans­
`action," Jul. 22, 2002, pp Iff.
`action,” Jul. 22, 2002, pp 1?f.
`PR Newswire, "Microsoft Annouces Launch Date for
`PR Newswire, “Microsoft Annouces Launch Date for
`UltraCrops, Its Second Premium Title for the Internet Gam­
`UltraCrops, Its Second Premium Title for the Internet Gam
`ing Zone," Mar. 27, 1998, ppl ff.
`ing Zone,” Mar. 27, 1998, pp.1 ff.
`PR Newswire, "Microsoft Boosts Accessibility to Internet
`PR Newswire, “Microsoft Boosts Accessibility to Internet
`Gaming Zone with Latest Release," Apr. 27, 1998, pp Iff.
`Gaming Zone with Latest Release,” Apr. 27, 1998, pp 1?f.
`Peercy et al., “Distributed Algorithms for Shortest—Path,
`Peercy et al., "Distributed Algorithms for Shortest-Path,
`Deadlock—Free Routing and Broadcasting in Arbitrarily
`Deadlock-Free Routing and Broadcasting in Arbitrarily
`Faulty Hypercubes,” Jun. 1990, 20th International Sympo
`Faulty Hypercubes," Jun. 1990, 20th International Sympo­
`sium on Fault–Tolerant Computing, 1990, pp—218–225.
`sium on Fault-Tolerant Computing, 1990, pp-218-225.
`Azar et al., “Routing Strategies for Fast Networks,” May
`Azar et al., "Routing Strategies for Fast Networks," May
`1992, INFOCOM '92 Eleventh Annual Joint Conference of
`1992, INFOCOM '92 Eleventh Annual Joint Conference of
`the IEEE Computer Communications Societies, vol. 1,
`the IEEE Computer Communications Societies, vol. 1,
`170-179###.
`170–179;###.
`
`* cited by examiner
`* cited by examiner
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 1 of 39
`Sheet 1 of 39
`
`US 6,910,069 B1
`
`a
`
`
`
`o
`
`03
`
`<
`
`H
`
`UJ
`
`O
`
`u.
`
`&
`
`Jj^
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 2 of 39
`Sheet 2 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`
`
`©
`
`u»
`
`to
`
`I*-
`
`Ol o
`
`o
`
`CJ
`
`CO
`
`at
`
`fa.
`o &
`
`oo
`
`|x.
`
`(O
`
`tn
`
`M
`
`n
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 3 of 39
`Sheet 3 of 39
`
`US 6,910,069 B1
`
`<
`
`<
`
`GQ
`
`O
`
`fsj
`
`AQ
`
`6<)
`
`Q
`
`HI
`
`t
`
`CD
`
`LU
`
`O
`
`D
`
`

`

`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 4 of 39
`
`US 6,910,069 B1
`
`"5
`
`Q
`
`O
`
`CO
`
`<
`
`u-
`
`.
`fSf
`
`
`
`LU
`
`o
`
`H
`
`X
`
`

`

`U.S. Patent
`
`Jun. 21, 2005
`
`Sheet 5 of 39
`
`US 6,910,069 B1
`
`£
`
`
`
`LU
`
`o
`
`CQ
`
`<
`
`cq
`
`LL
`
`O
`
`o
`
`H
`
`X
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 6 of 39
`Sheet 6 of 39
`
`US 6,910,069 B1
`
`
`
`X
`
`Q
`
`O
`
`CD
`
`<
`
`M
`
`>
`
`u.
`
`LU
`
`O
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 7 of 39
`Sheet 7 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`O
`
`
`
`O
`
`m
`
`<
`
`\
`\
`
`H
`
`Hi
`
`\
`\
`\
`\
`
`O
`
`u.
`
`*0
`=&
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 8 of 39
`Sheet 8 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`D
`
`
`
`O
`
`CD
`
`<
`
`/
`/
`
`I
`
`M
`
`X
`
`fiq
`lo
`bjo
`
`u.
`
`LU
`
`(D
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 9 of 39
`Sheet 9 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`Q
`
`
`
`O
`
`CQ
`
`<
`
`H
`
`<0
`
`.tuO
`
`ii-
`
`UJ
`
`o
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 10 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`
`
`O
`
`U
`
`CD
`
`<
`
`M
`
`liJ
`
`I
`I
`I
`I
`
`I
`I
`I
`
`O
`
`II.
`
`be
`pi^
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 11 of 39
`Sheet 11 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`Q
`
`
`
`Q) <
`<
`
`A
`
`•X**
`
`º,
`
`CQ
`
`<
`
`m
`
`*4
`
`O
`O
`
`
`
`Q
`
`o
`
`

`

`W
`0\ \o
`o
`o
`ON
`t*)
`G
`
`US 6,910,069 B1
`
`CZ3 ftr
`
`Sheet 12 Of 39
`
`©
`ls>
`
`c s
`
`d
`
`U.S. Patent
`
`ft =
`&:
`hd
`
`O o
`
`'Jl
`
`Jun. 21, 2005
`
`Fig. 6
`
`9 (814
`
`603
`
`'4
`
`Broadcaster
`
`channel instance)
`
`(channel type
`Application 2
`
`1
`
`602
`
`601
`
`Ports
`User
`
`600
`
`
`
`-T-
`
`Broadcaster
`
`602
`
`1
`
`4
`
`Broadcaster
`
`602
`
`channel instance)
`
`(channel type
`Application I
`
`601
`
`

`

`W
`VO
`O
`o
`0\
`in
`G
`
`US 6,910,069 B1
`
`ftr
`
`Sheet 13 of 39
`
`©
`
`o 'JI
`O
`
`Jun. 21, 2005
`
`c s
`
`d
`
`U.S. Patent
`
`=
`ft
`&:
`hd
`
`Fig. 7
`
`Dispatcher
`Internal
`
`4
`
`703
`
`1
`
`dispatcher
`Internal
`
`703
`
`dispatcher
`External
`
`702
`
`
`
`700
`
`I msg N
`Handle
`
`708
`
`I msg 1
`Handle
`
`708
`
`E msgN
`Handle
`
`707
`
`E msg 1
`Handle
`
`20/.
`
`707
`
`Broadcast
`709
`
`queue
`msg
`
`message
`Acquire
`
`704
`
`Broadcast
`
`712
`
`request
`Connect
`
`90/
`
`706
`
`Q
`
`portal
`Seek
`
`705
`
`109uuOO
`
`Connect
`
`70
`
`O
`
`response
`Receive
`71
`
`call back
`Connect
`
`710
`
`04 ||
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 14 of 39
`Sheet 14 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`(Channel Type,
`(Channel Type,
`Channel Instance,
`Channel Instance,
`Connect Aux Info)
`Connect Aux Info)
`
`Fig. 8
`Fig. 8
`
`Connect ^
`
`Open call in port
`Open call in port
`
`801
`801
`
`802
`802
`
`Set connect-time
`
`803
`803
`Seek portal - computer
`Seek portal - computer
`(channel type channel
`(channel type channel
`instance)
`instance)
`
`804
`804
`
`Success
`
`N
`N
`
`^ Return (false) ^
`
`Y
`Y
`
`805
`Contacts
`
`0
`
`Y
`
`
`
`N
`N
`
`808
`808
`Install external dispatcher
`Install external dispatcher
`
`806
`806
`Achieve connection
`
`|--|
`
`807
`807
`Install external dispatcher
`Install external dispatcher
`
`
`
`809
`809
`
`| Connect request |
`
`Connect request
`
`•
`^ Return (true) ^
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 15 of 39
`Sheet 15 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`
`
`
`
`
`
`
`
`
`
`)
`
`c Seek portal
`
`Seek portal
`computer
`computer
`902
`902
`*
`Select next depth
`Select next depth
`
`Channel Type
`Channel Type
`Channel Instance
`Channel Instance
`
`503
`All depths selected
`All depths selected
`
`Y
`
`^ Return (failure) ^
`Return (failure)
`
`Fig. 9
`Fig. 9
`
`N
`904
`Select next portal computer
`
`105
`All portal computers
`X<^A11 portal computers
`selected
`selected
`
`N
`
`906
`Dial portal computer
`
`507
`
`N
`
`Success
`
`Y
`Y
`
`908
`
`Contact process
`
`909
`Hang up selected portal
`computer
`
`
`
`911
`Check for external
`Check for external
`call
`call
`
`
`
`N
`
`
`
`10
`Selected portal
`Selected portal
`computer connected
`computer connected
`
`
`
`Y
`
`
`
`^Return (success)^
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 16 of 39
`Sheet 16 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`
`
`^Contact process^
`
`
`
`
`
`1001
`1001
`Send external message
`Send external message
`
`
`
`1002
`1002
`Receive external message
`Receive external message
`
`Fig. 10
`Fig. 10
`
`J 003 c
`
`ii
`
`Return
`
`)
`
`Success
`
`Y
`
`
`
`1005
`1005
`Add as connected portal
`Add as connected portal
`computer
`computer
`
`
`
`1004
`Answering process
`X<^^Answering process
`Y
`--
`connected
`connected
`
`1006
`Add as fellow seeking
`Add as fellow seeking
`computer
`computer
`
`N
`N
`
`c Return
`
`)
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 17 of 39
`Sheet 17 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`1102
`
`Restart
`Restart
`
`Return
`
`J
`
`Fig. 11
`Fig. 11
`
`^Connect request^
`Connect request
`
`1101
`Was a folly
`Was a fully
`connected portal foung
`connected portal fount
`
`
`
`
`
`N
`
`Y
`1103
`Dial call in port of portal
`Dial call in port of portal
`computer
`computer
`
`1104
`1 104
`
`N
`N
`
`Success
`
`
`
`Y
`Y
`1105
`1105
`Send external message
`Send external message
`1106
`1 106
`Receive external message
`Receive external message
`
`
`
`1107
`
`Success
`
`N
`
`Y
`1108
`Set expect holes from
`Set expect holes from
`response
`response
`
`1109
`Set diameter from response
`
`
`
`111
`Ready to connect
`Ready to connect
`
`Y
`
`
`
`1 1 1 2
`1 112
`| Add neighbor |
`Add neighbor
`
`1113
`
`Nr
`Hangup
`
`c Return
`
`

`

`US 6,910,069 B1
`US 6,910,069 B1
`
`Fig. 12
`Fig. 12
`
`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 18 of 39
`Sheet 18 of 39
`
`e heck for extern
`5
`
`heck for externa
`call
`call
`
`1201
`
`Answer
`
`1202
`
`Success
`
`2i
`N
`
`Y
`
`1203
`Receive external message
`
`1204
`ype = = seeking
`seeking
`ype is
`connection call
`connection call
`
`N
`
`Y
`
`1205
`Send external message
`Send external message
`
`
`
`
`
`
`
`206
`
`Success
`
`Y
`
`1207
`Add other as fellow seeker
`Add other as fellow seeker
`
`c Return
`
`J
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 19 of 39
`Sheet 19 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`Fig. 13
`Fig. 13
`
`(Achieve connection
`Achieve connection
`
`
`
`
`
`
`
`1301
`1301
`Connection - state • fully
`Connection - state = fully
`connected
`connected
`
`1302
`1302
`Notify fellow seekers
`Notify fellow seekers
`
`1303
`1303
`Invoke connect call back
`Invoke connect call back
`
`
`
`C
`
`Return
`
`)
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 20 of 39
`Sheet 20 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`External dispatcher
`^External dispatcher^
`4r
`
`1401
`Pick up and receive
`Pick up and receive
`external message
`external message
`
`1402
`
`N
`
`Message
`
`Y
`
`1403
`Seeking connection call
`
`Y
`
`N
`
`1405
`Connection request call
`
`Y
`
`N
`
`1407
`Edge proposal call
`
`X
`
`
`
`
`
`
`
`
`
`
`
`
`
`N
`
`1409
`Port connect call
`Port connect call
`
`Y
`
`N
`
`1411
`Connected statement
`Connected Statement
`
`Y
`
`
`
`
`
`
`
`Fig. 14
`Fig. 14
`
`1415
`Hangup
`
`1416
`
`Hangup
`
`Return
`
`c
`
`J
`
`1404
`Handle seeking
`Handle seeking
`connection call
`connection call
`
`1406
`Handle connection
`Handle connection
`request call
`request call
`
`1408
`1408
`Handle edge proposal
`call
`call
`
`|- edge proposal |
`
`1410
`1440
`
`Handle port
`Handle port
`connection call
`connection call
`
`
`
`1412
`Handle connected
`Handle connected
`statement
`State?ment
`
`IN
`1414
`1414
`1413
`1413
`Handle condition |
`Y
`Condition repair
`Handle condition
`Condition repair
`Y
`repair statement
`statement
`State?ment ~ repair statement
`:N
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 21 of 39
`Sheet 21 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`c Handle seeking
`
`Handle seeking
`connection call
`connection call
`
`
`
`1502
`Set message to indicate
`Set message to indicate
`connected
`
`
`
`Y
`
`1501
`Fully connected
`
`N
`
`
`
`Fig. 15
`Fig. 15
`
`1503
`1503
`Set message to not
`Set message to not
`connected
`
`1504
`Add other as fellow
`Add other as fellow
`seeking process
`seeking process
`
`
`
`1505
`1505
`Send external message
`Send external message
`
`c Return
`
`

`

`5
`
`J-
`
`andle connection
`andle connection
`request calf
`request call
`1601
`1601
`N
`Connected -º
`Connected
`j6Q3
`Set newcomer's
`Set newcomer's
`holes_to_expect
`holes_to_expect
`1£Q4
`SQ4
`Set diameter estimate in
`Set diameter estimate in
`response
`response 16C
`160S
`Set ready in response
`Set ready in response
`1SQ6
`º
`Sent external message
`Sent external message
`connect request resp.
`connect request resp.
`1507
`Set newcomer s
`Set newcomer's
`holes to fill
`holes to fill
`608
`608
`
`1SQ2
`CC
`
`Hangup
`
`Return
`Return
`
`j
`
`Fig. 16
`Fig. I6
`
`1609
`50 S3
`| Add neighbor |
`Add neighbor
`1£1Q
`Newcomer's
`holes to fill ~
`
`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 22 of 39
`Sheet 22 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`e
`
`Ready
`
`X
`
`mi
`
`Hang up
`
`1612
`Hole = = 0 or
`diameter > 1
`
`
`
`N
`
`K
`
`1613
`Holes tojEill
`. > =Z
`
`X
`
`im
`Forward connection
`edge search
`ms,
`Holes to fill - = 2
`Holes to fill - =
`mi
`1616
`'Newcomer's
`Y
`Fill hole (requestor)
`Fill hole (requestor)
`Y
`ides to fill >
`Roles_to_fill > ~
`*
`)
`Return
`^
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 23 of 39
`Sheet 23 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`Add neighbor ^
`Add neighbor
`
`IZfil
`Identifies calling party
`1ZQ2
`Sets neighbor to
`Sets neighbor to
`messages pending
`messages pending
`
`Fig. 17
`Fig. 17
`
`<-- Fº:
`
`1ZQ4
`Q4
`-
`Connection state *=
`tate =
`C
`Ct
`partially connected
`
`703
`703
`e
`-
`eeking connect
`NCL
`N
`1705
`1705
`Add as neighbor
`Add as neighbor
`
`1ZQ6
`Qö
`Install interal dispatcher
`Install interal dispatcher
`for new neighbor
`for new neighbor
`
`707
`707
`Connecting buffer^>^-
`Connecting buffer
`
`1708
`O8
`Send interal stream
`
`X
`
`izia
`| Achieve connected
`Achieve connected
`
`
`
`
`
`1709
`1709
`Holes = =
`Holes = =
`pected hole:
`Expected hole
`NU
`N
`
`1112
`Purge pending edges
`Purge pending edges
`- *
`
`1711
`1711
`Hole = = 0
`
`Y
`
`NU
`Return
`
`^
`
`
`
`^
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 24 of 39
`Sheet 24 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`Fig. 18
`Fig. 18
`
`
`
`
`
`
`
`Forward connection
`Forward connection
`edge search
`edge search
`
`0
`
`requestor
`requestor
`distance remaining
`distance remaining
`
`J 801
`Distance
`remaining > 0
`
`Y
`
`N
`
`1802
`#of
`# of
`neighbors
`neighbors
`> 1
`> I
`
`Y
`Y
`
`N
`
`
`
`
`
`•*
`
`1803
`neighbor =
`neighbor =
`requestor
`
`N
`
`1804
`304
`Select random neighbor
`Select random neighbor
`
`requestor j
`c Return
`
`
`
`Y
`
`-*
`
`Return
`
`1805
`Y / /All neighbors
`selected
`selected
`
`N
`N
`
`1806
`Send internal message
`Send internal message
`
`
`
`Y
`
`.1807
`Success
`
`1808
`Note connection edge
`search call
`
`c Return
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 25 of 39
`Sheet 25 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`c
`
`Handle edge
`Handle edge
`proposal call
`proposal call
`
`) in message
`
`in message
`out message
`out message
`
`Fig. 19
`Fig. 19
`
`N
`
`Y
`
`1901
`Holes -
`ling edge of >
`
`rz: ^
`
`Y
`
`1902
`a party
`at end of edges a
`v\neighboi>/'
`N
`1303
`N 190
`create edge (pending)
`create edge (pending)
`
`
`
`
`
`
`
`mi
`Send external message
`Send external message
`
`Y
`
`
`
`1904
`proposed
`proposed
`neighbors
`neighbors
`pending
`pending
`N
`N
`
`-
`
`1907
`Send external message
`
`907
`
`N
`
`J 912
`f 912
`Holes odd
`
`º 1913
`c
`
`Y
`
`Fill hole
`Fifi hole
`
`*•
`
`Return
`
`1913
`|
`
`)
`
`c
`
`)
`
`Return
`
`1908
`J 908
`N
`Success
`
`Y
`* 1909
`1909
`Add edge as pending
`Add edge as pending
`
`1910
`1910
`Add neighbor
`
`c Return
`
`)
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 26 of 39
`Sheet 26 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`Fig. 20
`Fig. 20
`
`
`
`
`
`2007
`
`Hang up
`
`
`
`2008
`2008
`| Connect request |
`Connect request
`
`Q connection ca^)
`
`Handle port
`Handle port
`connection call
`
`2001
`Holes > 0
`
`N
`
`Y
`
`002
`-
`Caller is not
`Caller is not
`neighbor
`neighbor
`
`N
`
`
`
`
`
`Y
`
`2004
`Send external message
`Send external message
`(point-connect-resp, ok)
`(point-connect-resp, ok)
`
`_N
`
`Success
`
`!005
`
`Y
`
`^ Return
`
`2003
`2003
`Send external message
`Send external message
`(point-connect-resp
`(point-connect-resp
`not ok)
`not ok)
`
`C
`
`Return
`
`)
`
`2006
`2006
`Add neighbor
`
`| Add neighbor |
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 27 Of 39
`Sheet 27 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`Fig. 21
`Fig. 21
`
`
`
`
`
`2104
`Handle connection
`Handle connection
`ports search edit
`ports search edit
`
`
`
`)
`
`Fill hole
`Fill hole
`
`2101
`Initialize internal
`Initialize internal
`message
`message
`
`N
`
`102
`Is this
`iarty the request­
`ing P'
`
`Y
`
`( Return
`
`2103
`2103
`Distribute internal
`Distribute internal
`message
`message
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 28 of 39
`Sheet 28 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`c Interna!
`
`Internal
`dispatcher
`dispatcher
`
`3
`
`2201
`22O1
`Received internal message
`Received intenuil message
`2202
`2202
`Assess diameter
`Assess diameter
`
`Fig. 22
`Fig. 22
`
`
`
`
`
`
`
`
`
`-^This^203
`This
`process = =
`process ==
`originating
`^originatina^^
`N
`
`Y
`
`Y
`22Q3B
`Insert message into
`pending connection buffer
`pending connection buffer
`
`Insert ºn is
`
`
`
`2203A
`Partially connected
`Partially connected
`
`
`
`N
`Type
`^^Type^-^204
`== broadcast
`= = broadcast
`statement
`Statement
`
`2005
`2005
`| Handle broadcast
`Handle broadcast
`message
`message
`
`
`
`
`
`^iVpe^JOS
`= = shutdown ^S~>X
`= = shutdown
`^ statement
`Statement
`
`N
`
`2007
`2007
`Handle shutdown
`Handle shutdown
`statement
`Statement
`
`
`
`
`
`
`
`2209
`Achieve connection
`
`Y
`Y
`
`!208
`Pending
`Pending
`connection buffer
`connection buffer
`fall
`N
`
`!210
`Is
`Is
`message queue
`empty
`
`N
`
`
`
`
`
`Laºs;
`message queue tº Hº Receive response ( )
`c Return
`)
`
`2212
`Receive response ( )
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 29 of 39
`Sheet 29 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`Fig. 23
`Fig. 23
`
`ongrn
`origin
`from neighbor
`from neighbor
`message
`mºsº
`
`c
`
`D
`andle broadcast
`andle broadcast
`message
`message
`2ao,
`2301
`Process out of order
`Process out of order
`message
`message
`
`
`
`2302
`2302
`Distribute broadcast
`Distribute broadcast
`message
`message
`
`
`
`
`
`303
`303
`Has a new
`Y
`BS 3 ?lº/
`Y
`neighbor received
`neighbor received
`\jnessages/'
`
`
`
`2304
`2304
`-
`Clear out of order info
`Clear out of order info
`
`messages ~
`N-c Return
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 30 of 39
`Sheet 30 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`º
`jr,.
`F18. 24
`Pig* *4
`
`
`
`
`
`message
`message
`from neighbor
`from neighbor
`
`f Distribute ^
`Distribute
`Vbroadcast message/
`2401
`2401
`Select next neighbor
`Select next neighbor
`
`!402 c
`
`Y
`
`
`
`All neighbor
`All neighbor
`selected
`selected
`
`N
`
`2403
`2403
`Send internal
`Send internal
`message
`message
`
`Return
`
`3
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 31 of 39
`Sheet 31 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`Handle connection
`Handle connection
`for search
`for search
`
`)
`
`2§Q1
`280
`Distribute internal
`Distribute internal
`message
`
`from neighbor
`from neighbor
`message
`message
`
`*: Fig. 26
`Fig. 26
`
`B02
`602
`Holes > 0
`
`N
`N
`
`C
`
`Return
`
`J
`
`Y
`Y
`
`
`
`1603
`603
`Is requestor
`Is requestor
`N
`a neighbor
`a neighbor
`
`2604
`2604
`Court neighbor
`
`*—| canº ||
`
`Return
`
`Y
`
`105
`305
`
`N
`
`Holes = = 1
`
`Y
`2606
`Generate
`Entrate
`condition check
`condition check
`message w/neighbors
`message wheighbors
`
`
`
`2607
`26O7
`Send internal message
`Send internal message
`to requestor
`to requestor
`
`4
`Return
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 32 of 39
`Sheet 32 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`
`
`Fig. 27
`Fig. 27
`
`^ Court neighbor
`
`Prospect
`
`c
`
`Return
`
`3
`
`1701
`Is prospect
`a neighbor
`
`Y
`
`N
`N
`
`2702
`2702
`Dial prospect
`Dial prospect
`
`
`
`703
`
`Holes > 0
`
`N
`
`
`
`Y
`
`2704
`Send and receive
`Send and receive
`external message
`external message
`
`
`
`2705
`Add neighbor
`
`| Add neighbor |
`
`
`
`•*
`
`2706
`2706
`Hang up prospect
`Hang up prospect
`
`c
`
`Return
`
`)
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 21, 2005
`Jun. 21, 2005
`
`Sheet 33 of 39
`Sheet 33 of 39
`
`US 6,910,069 B1
`US 6,910,069 B1
`
`Fig. 28
`Fig. 28
`
`
`
`N
`N
`
`
`
`
`
`A-
`
`2813
`2813
`Message^v
`M