Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 1 of 59 PageID #: 541
`
`Exhibit 2
`
`           
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 2 of 59 PageID #: 542
`
`(12)
`
`United States Patent
`Holt et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,714,966 B1
`*Mar. 30, 2004
`
`US006714966B1
`
`(54) INFORMATION DELIVERY SERVICE
`
`(75) Inventors: Fred B. Holt, Seattle, WA (US); Virgil
`E. Bourassa, Bellevue, WA (US)
`(73) Assignee: The Boeing Company, Seattle, WA
`(Us)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`
`5,734,865 A
`5,737,526 A
`5,754,830 A
`2
`5,790,548 A
`5,790,553 A
`5,799,016 A
`5,802,285 A
`
`3/1998 Yu
`4/1998 Periasamy et al.
`5/1998 B11_tt5 et ah
`gliirner
`8/1998 SistaIliZadeh eta1~
`8/1998 Deaton, Jr. et 81.
`8/1998 Onweller
`9/1998 Hirviniemi
`
`
`
`patent is extended or adjusted under USC_ 154 b b 467 d _
`( ) y
`ays
`_
`_
`_
`_
`_
`T1115 patent is subJect to a terminal d1s-
`claimer.
`
`(21) Appl. No.: 09/629,043
`(22) Filed:
`Jul. 31, 2000
`
`7
`(51) Int. Cl. .............................................. .. G06F 15/16
`
`(52) US. Cl. ..................... .. 709/204; 709/205; 709/203;
`709/243; 463/92
`
`(58) Field of Search ............................... .. 709/204, 205,
`709/227’ 243’ 203; 463/40’ 42
`
`(56)
`
`References Cited
`
`U-S~ PATENT DOCUMENTS
`4,912,656 A
`3/199O Cain et a1_
`5,056,085 A 10/1991 Vu
`5,058,105 A * 10/1991 Mansour et al. .......... .. 370/228
`23079767 A :
`;/ 1992 Pe?manh _
`1
`370/422
`s’éég’jég 2
`2311s; stnililet a‘ """ " 370/2
`5’426’637 A
`6/1995 D e rby et a1 '
`5:459:725 A * 1O/1995 Bodner et ai ____________ __ 370/390
`5,471,623 A * 11/1995 Napolitano, Jr. .......... .. 709/243
`5,535,199 A
`7/1996 Amri et a1,
`5,568,487 A 10/1996 Sitbon etal.
`5,636,371 A
`6/ 1997 Y1_1 _
`_
`5,644,714 A * 7/1997 KlklIllS ..................... .. 709/219
`53673265 A
`9/1997 Gupta et a1‘
`5,696,903 A 12/1997 Mahany
`5,732,074 A
`3/1998 Spauretal.
`5,732,086 A * 3/1998 Liang et al. .............. .. 370/410
`5,732,219 A
`3/1998 Blumer et al.
`
`
`A T 5,864,711 A
`5,867,660 A
`5,867,667 A
`5,870,605 A
`
`Ramanathan . . . . . . . . . . . . . . . . .. 1/1999 Mairs et al.
`
`2/1999 Schmidt et al.
`2/1999 Butman et 81.
`2/1999 Bracho et a1_
`
`(List continued on neXt page.)
`OTHER PUBLICATIONS
`_
`_
`_
`_
`_
`PR Newswire, “Microsoft Boosts Accessibility to Internet
`Gaming Zone with Latest Release,” Apr. 27, 1998, pp. 1ff.*
`PR NeWSWire, “Microsoft Announces Launch Date for
`
`UltraCorPe Its Second Premium Title for the Internet Gam
`111g Z0116,” Ma 27, 1998, pp. 1 ff.*
`Business Wire, “Boeing and Panthesis Complete SWAN
`Transaction,” Jul- 22, 2002, pp. 1ff.*
`(List continued on neXt page.)
`
`_
`_
`_
`Primary Examtner—Dung C. Dmh
`Assistant Examiner—Brad Edelman
`(74) Attorney, Agent, or Firm—Perk1ns Co1e LLP
`
`(57)
`ABSTRACT
`A computer network for providing an information delivery
`service for a plurality of participants over the network is
`disclosed. Each participant has connections to at least three
`neighbor participants. An originating participant sends data
`t0 the Other partlelpahts by sehdlhg the data through eaeh of
`its connections to its neighbor participants. Further, each
`participant sends data that it receives from a neighbor
`participant to its other neighbor participants. The network is
`m_regu1ar Where In is the exact number of neighbor partici_
`pants of each participant and the network is an incomplete
`m h
`g p '
`
`17 Claims, 39 Drawing Sheets
`
`Distribute
`broadcast message
`
`message
`from neighbor
`
`2401
`
`Select next neighbor
`
`All neighbor
`selected
`
`Send internal
`message
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 3 of 59 PageID #: 543
`
`US 6,714,966 B1
`Page 2
`
`US. PATENT DOCUMENTS
`
`2/1999 Mairs et al.
`5,874,960 A
`5/1999 Wilf et al.
`5,899,980 A
`5/1999 Onweller
`5,907,610 A
`5,925,097 A * 7/1999 Gopinath et al. ......... .. 709/200
`5,928,335 A
`7/1999 Morita
`5,935,215 A
`8/1999 Bell et al.
`5,948,054 A
`9/1999 Nielsen
`5,949,975 A
`9/1999 Batty et al.
`5,956,484 A
`9/1999 Rosenberg et al.
`5,970,232 A * 10/1999 Passint et al. ............ .. 709/238
`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,094,676 A
`7/2000 Gray et al.
`6,115,580 A * 9/2000 Chuprun et al. ............. .. 455/1
`
`
`
`6,167,432 A * 12/2000 Jiang ................. .. 6,173,314 B1 * 1/2001 Kurashima et al. ....... .. 709/204
`
`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
`7/2001 Mairs et al.
`6,268,855 B1
`8/2001 Mairs et al.
`6,271,839 B1
`6,272,548 B1 * 8/2001 Cotter et al. .............. .. 709/239
`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 ................... .. 709/238
`6,463,078 B1 * 10/2002 Engstrom et al. .
`370/466
`6,524,189 B1 * 2/2003 Rautila ...................... .. 463/40
`2002/0027896 A1 * 3/2002 Hughes et al. ............ .. 370/342
`
`OTHER PUBLICATIONS
`
`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.*
`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.*
`Komine et al., “A Distributed Restoration Algorithm for
`Multiple—Link and Node Failures of Transport Networks,”
`Dec. 199 Global Telecommunications Conference, 1990,
`and Exhibition, IEEE, vol. 1, pp. 459—463.*
`Peercy et al., “Distributed Algorithms for Shortest—Path,
`Deadlock—Free Routing and Broadcasting in Arbitrarily
`Faulty Hypercubes,” Jun. 1999, 20* International Sympo
`sium of Fault—Tolerant Computing, 1990, pp. 218—225.*
`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).
`US. patent application Ser. No. 09/629,570, Bourassa et al.,
`?led Jul. 31, 2000.
`
`US. patent application Ser. No. 09/629,577, Bourassa et al.,
`?led Jul. 31, 2000.
`US. patent application Ser. No. 09/629,575, Bourassa et al.,
`?led Jul. 31, 2000.
`US. patent application Ser. No. 09/629,572, Bourassa et al.,
`?led Jul. 31, 2000.
`US. patent application Ser. No. 09/629,023, Bourassa et al.,
`?led Jul. 31, 2000.
`US. patent application Ser. No. 09/629,576, Bourassa et al.,
`?led Jul. 31, 2000.
`US. patent application Ser. No. 09/629,024, Bourassa et al.,
`?led Jul. 31, 2000.
`US. patent application Ser. No. 09/629,042, Bourassa et al.,
`?led Jul. 31, 2000.
`Murphy, Patricia, A., “The Next Generation Networking
`Paradigm: Producer/Consumer Model,” Dedicated Systems
`MagaZine—2000 (pp. 26—28).
`The Gamer’s Guide, “First—Person Shooters,” Oct. 20, 1998
`(4 pages).
`The O’Reilly Network, “Gnutella: Alive, Well, and Chang
`ing Fast,” Jan. 25, 2001 (5 pages) http://www.open2p.com/
`lpt/... [Accessed Jan. 29, 2002].
`Oram, Andy, “Gnutella and Freenet Represents True Tech
`nological Innovation,” May 12, 2000 (7 pages) The O’Reily
`Network http://www.oreillynet.com/lpt... [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/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/
`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 Assoicates, 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.
`21—1—12—10), Chapter 12 (pp. 13—1—13—56), Chapter 16
`(pp. 16—1—16—26), Chapter 18 (pp. 18—1—18—52), Chapter
`20 (pp. 20—1—20—22).
`The University of Warwick, Computer Science Open Days,
`“Demonstration on the Problems of Distributed Systems,”
`http://www.dcs.warwick.ac.u... [Accessed Jan. 29, 2002].
`
`* cited by examiner
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 4 of 59 PageID #: 544
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 1 (639
`
`US 6,714,966 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 5 of 59 PageID #: 545
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 2 0f 39
`
`US 6,714,966 B1
`
`NF
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 6 of 59 PageID #: 546
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 3 0f 39
`
`US 6,714,966 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 7 of 59 PageID #: 547
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 4 0f 39
`
`US 6,714,966 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 8 of 59 PageID #: 548
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 5 0f 39
`
`US 6,714,966 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 9 of 59 PageID #: 549
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 6 6f 39
`
`US 6,714,966 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 10 of 59 PageID #: 550
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 7 0f 39
`
`US 6,714,966 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 11 of 59 PageID #: 551
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 8 (639
`
`US 6,714,966 B1
`
`m
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 12 of 59 PageID #: 552
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 9 0f 39
`
`US 6,714,966 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 13 of 59 PageID #: 553
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 10 0f 39
`
`US 6,714,966 B1
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 14 of 59 PageID #: 554
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 11 0f 39
`
`US 6,714,966 B1
`
`E .ME
`
`MR .ME
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 15 of 59 PageID #: 555
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 12 0f 39
`
`US 6,714,966 B1
`
`com
`
`“3D
`
`35%
`
`Now
`
`Pow
`
`now
`
`///H
`
`A
`
`k
`
`w
`
`w 668935
`
`I\S\< 528305
`\\. .Ns
`
`6 .5
`
`Pow
`
`N noggin?
`
`@2855 6:55
`
`096 “E523
`
`
`96:52.. 6:550
`~ conmu=aa<
`35 655:8
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 16 of 59 PageID #: 556
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 16 of 59 Page|D #: 556
`
`S.U
`
`P
`
`0
`
`31
`
`US 6,714,966 B1
`
`.oon
`
`2:
`
`ONuficmiCmN...E_2
`Bnufiamfi.EtonoEm.358$_wmEmxoum82:80
`
`
`
`4«E
`
`NZmm...msong.Wo=EmESoccou
`
`
`
`.mwasHmuovmoem%.0N_L.
`
`9.mo»VB_EB.MwasH6.22;:
`
`253.:
`
`
`8»wasomammofi386%:Hummousogmo::vu<
`uzooom
`
`2mac.H22;:
`
`6.u.E
`
`
`
`
`
`.xofi:3WuBu.won82:50
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 17 of 59 PageID #: 557
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 14 0f 39
`
`US 6,714,966 B1
`
`(Charme1 Type,
`Channel Instance,
`Connect Aux Info)
`
`F 1g. 8
`
`(
`
`Connect
`
`)
`
`Open call in port
`
`801
`
`802
`
`Set connect-time
`
`803
`Seek portal - computer
`(channel type channel
`instance)
`
`Return (false)
`
`806
`
`Achieve connection
`
`807
`
`Install external dispatcher
`
`Contacts
`
`0
`
`Install external dispatcher
`
`809
`
`Connect request
`
`1
`
`Return (true)
`
`)
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 18 of 59 PageID #: 558
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 15 0f 39
`
`US 6,714,966 B1
`
`Seek portal
`computer
`
`Channel Type
`Channel Instance
`
`902
`
`Select next depth
`
`903
`
`All depths selected
`
`Return (failure)
`
`r N
`
`904
`
`Select next portal computer
`
`Fig. 9
`
`All portal computers
`selected
`
`906
`Dial portal computer
`
`Success
`
`Contact process
`
`909
`|
`Hang up selected portal
`computer
`
`911
`Check for external
`call
`
`910
`Selected Portal
`computer connected
`
`Return (success)
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 19 of 59 PageID #: 559
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 16 0f 39
`
`US 6,714,966 B1
`
`Fig. 10
`
`I Contact process )
`
`1001
`Send external message
`
`Receive external message
`
`Success
`
`1 005
`Add as connected portal
`computer
`
`Answering process
`connected
`
`1006
`Add as fellow seeking
`computer
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 20 of 59 PageID #: 560
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 17 0139
`
`US 6,714,966 B1
`
`Fig. 11
`
`Connect request
`
`1101
`Was a fully
`connected portal found
`
`1102
`
`Restart
`
`1 103
`‘
`Dial call in port of portal
`computer
`
`(
`
`Return
`
`I
`
`1 104
`
`Success
`
`N
`
`Y
`
`1105
`
`Send external message
`
`1106
`Receive external message
`
`N / Success
`
`1107
`
`Y
`Set expect holes from
`response
`
`1 109
`Set diameter from response
`
`1 1 1
`Ready to connect
`
`Y
`
`1 1 12
`Add neighbor
`
`1113
`
`N‘
`Han
`
`Return
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 21 of 59 PageID #: 561
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 18 0f 39
`
`US 6,714,966 B1
`
`Check for extema
`
`1 201
`
`F i .
`g
`
`call
`
`Answer
`
`1202
`
`Success
`
`Y
`
`1 203
`Receive external message
`
`ype = = seeking
`connection call
`
`1 205
`Send external message
`
`Add other as fellow seeker
`
`(
`
`Return
`
`>
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 22 of 59 PageID #: 562
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 22 of 59 Page|D #: 562
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 19 of 39
`
`US 6,714,966 B1
`
`Achieve connection
`
`
`
`1301
`
`Connection - state = fially
`connected
`'
`
`Notify fellow seekers
`
`Fig. 13
`
`
`
`
`
`Invoke connect call back
`
`1303
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 23 of 59 PageID #: 563
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 23 of 59 Page|D #: 563
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 20 of 39
`
`US 6,714,966 B1
`
`
`
`
`Handle seeking
`connection call
`
`
`
`Seeking connection call
`
`Connection request call
`
`Edge proposal call
`
`
`Handle port
`connection call Port connect call
`
`Connected statement
`
`
`
`Handle condition
`Condition repair
`statement
`
`repair statement
`
`
`
`External dispatcher
`
`Figs 14
`
`1401
`Pick up and receive
`external message
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 24 of 59 PageID #: 564
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 24 of 59 Page|D #: 564
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 21 of 39
`
`US 6,714,966 B1
`
`
`
`Handle seeking
`connection call
`
`
`
`
`
`Fig. 15
`
`1 502
`
`Set message to indicate
`connected
`
`
`
`1 503
`
`Set message to not
`
`1 504
`
`connected
`
`
`
`Add other as fellow
`seeking process
`
`
`
`Send external message
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 25 of 59 PageID #: 565
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 25 of 59 Page|D #: 565
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 22 of 39
`
`US 6,714,966 B1
`
`andle connection
`request call
`
`1601
`connected
`
`N
`
`_L O) C 03
`
`Set newcomefs
`ho1es_to_expect
`_..x O)C-5
`
`Set diameter estimate in
`
`0.
`
`R
`
`YCSPOUSC
`
`. '
`
`Figa
`
`Set ready in response
`
`0
`
`03 O
`
`Sent external message
`connect request resp.
`1607
`
`Set newcomer's
`holes_to_fill
`
`608
`
`Y
`
`1 609
`
`1610
`
`
`
`161 1
`
`N ‘
`
`Newcomer's
`
`Holes to fill — = Z
`
`
`
`ewcomer's
`
`Y
`
`N Fill hole (requestor) N
`o]eS—tO-‘fin > .
`1
`
`.
`
`1617
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 26 of 59 PageID #: 566
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 26 of 59 Page|D #: 566
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 23 of 39
`
`US 6,714,966 B1
`
`Flg- 1 7
`
`C nnection state1=704
`pgrtially connected
`
`0 Add neighbor
`
`1701
`
`Identifies calling party
`
`\J O- f\J
`
`Sets neighbor to
`messages pending
`
`1703
`1
`“ eekmg Comectio
`
`Y
`
`N
`
`1 705
`
`Add as neighbor
`
`1 706
`Install interal dispatcher
`for new neighbor
`
`1707
`
`
`W Y
`
`
`N 1
`
`709
`
`
`
`1708
`
`O
`
`= =
`
`xpected hole
`
`
`
`Y
`
`Achieve connected
`
`171 1
`
`1712
`
`Y
`
`Purge pending edges
`
`N
`
`N
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 27 of 59 PageID #: 567
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 27 of 59 Page|D #: 567
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 24 of 39
`
`US 6,714,966 B1
`
`Forward connection
`edge search
`
`requestor
`distance remaining
`
`
`
`Fig. 18
`
`
`
`remaining > 0
`
`>1
`
`neighbor =
`
`requestor
`
`Note connection edge
`search call
`
`
`
`All neighbors
`selected
`
`N
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 28 of 59 PageID #: 568
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 28 of 59 Page|D #: 568
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 25 of 39
`
`US 6,714,966 B1
`
`Handle edge
`PV0P°5a1 C311
`
`in message
`out message
`
`Fig. 229
`
`
`create edge (pending)
`
`
`proposed
`neighbors
`pending
`
`N
`
`1 907
`
`Send external message
`
`1 91 1
`
`Send external message
`
`N
`
`1 912
`Holes odd
`
`1913
`
`Y
`
`Y
`
`1
`
`1908
`
`N
`
`1 909
`
`.
`
`1910
`
`I
`
`Add neighbor
`
`I
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 29 of 59 PageID #: 569
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 29 of 59 Page|D #: 569
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 26 of 39
`
`US 6,714,966 B1
`
`
`Handle port
`connection call
`
`Fziga 20
`
`
`
`
`Caller is not
`
`neighbor
`
`Send external message
`(point-connect—resp
`not ok)
`
`
`
`
`
`Send external message
`(point-connect-resp, ok)
`
`
`
`2006
`
`I
`
`Add neighbor
`
`I
`
`2008
`
`
`
`N Connect request l
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 30 of 59 PageID #: 570
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 30 of 59 Page|D #: 570
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 27 of 39
`
`US 6,714,966 B1
`
`Flg' 21
`
`Fill hole
`
`2101
`Initialize internal
`message
`
`
`
`2104
`
`Handle connection
`ports search edit
`
`2103
`
`Distribute internal
`message
`
`Return
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 31 of 59 PageID #: 571
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 31 of 59 Page|D #: 571
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 28 of 39
`
`US 6,714,966 B1
`
`Fig 22
`
`Internal
`
`dispatcher
`
`2201
`
`2202
`
`Assess diameter
`
`
`
`
`originatin
`
`Partially connect?
`
`Type
`= = broadcast
`
`
`
`statement
`
`2005
`
`Handle broadcast
`message
`
`
`
`pending connection bufi'er
`
`Y
`
`Y
`
`2007
`I Hanstlgtgrlgggtown I
`
`I
`
`221 2
`
`
`
`Type
`2205
`
`Y
`= : shutdown
`statement ‘
`
`
`
`
`N
`
`Pending
`connection buffer
`
`
`
`“
`
`N
`
`210
`
`Is
`
`message queue
`empty
`
`Y
`
`Receive response ( )
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 32 of 59 PageID #: 572
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 32 of 59 Page|D #: 572
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 29 of 39
`
`US 6,714,966 B1
`
`-
`
`Ftg. 23
`
`Handle broadcast
`message
`
`
`
`
`2301
`
`Process out of order
`
`message
`
`2302
`
`Distribute broadcast
`
`message
`
`origin .
`from neighbor
`message
`
`Clear out of order info
`
`
`
`
`
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 33 of 59 PageID #: 573
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 33 of 59 Page|D #: 573
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 30 of 39
`
`US 6,714,966 B1
`
`Fig. 24
`
`
`Distribute
`broadcast message
`
`
`
`message
`from neighbor
`
`2401
`
`Select next neighbor
`
`
`
`402
`
` All neighbor
`
`selected
`
`2403
`
`Send internal
`
`message
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 34 of 59 PageID #: 574
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 34 of 59 Page|D #: 574
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 31 of 39
`
`US 6,714,966 B1
`
`Handle connection
`for search
`
`from neighbor
`message
`
`2601
`
`Distribute internal
`
`,FIg- 26
`
`602
`
`N
`
`Y
`
`
`
`603
`
`Is requestor
`a neighbor
`
`
`
`N
`
`2604
`
`I Court neighbor
`
`I
`
`605
`
`
`
`condition check
`messae w/nei hbors
`
`
`
`
`
`2607
`
`Send internal message
`to requestor
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 35 of 59 PageID #: 575
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 35 of 59 Page|D #: 575
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 32 of 39
`
`US 6,714,966 B1
`
`Court neighbor
`
`Prospect
`
`Fig. 27
`
` Isprospect
`
`a neighbor
`
`2702
`
`Dial prospect
`
`703
`
`
`
`Send and receive
`external message
`
`I
`
`Add neighbor
`
`2706
`
`Hang up prospect
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 36 of 59 PageID #: 576
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 36 of 59 Page|D #: 576
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 33 of 39
`
`US 6,714,966 B1
`
`Fig. 28
`
`Handle connection
`edge search call
`801
`
`Not
`my message 11
`holes >= Z
`
`N
`
`from neighbor
`message
`
`Y
`
`2813
`
`
`Message
`N
`from this pt. &&
`
`holes _ _
`
`Y
`
`
`
`2814
`
`I
`
`
`
`B
`
`Fill hole (self)
`
`I
`
`2815
`
`>
`en mtema
`message (from
`neihbor, ack
`
`802
`Forward
`2303
`
`
`Remaining
`connection second
`Y
`
`
`
`distance > O
`edg? (_Tequ?5t0T
`remaining dist -1)
`
`
`
`
`R
`t
`Forward
`_ eques OF
`connection edge
`_
`15 nelghbor 03 edge
`search (requestor,
`
`
`reserve
`0)
`N
`2806
`
`
`
`‘V
`
`
`
`
`
`2807
`
`Send and receive
`external message
`
`808
`
`is edge acceptable N
`
`Reserve edge of from
`
`neighbor
`
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 37 of 59 PageID #: 577
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 37 of 59 Page|D #: 577
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 34 of 39
`
`US 6,714,966 B1
`
`Fig. 29
`
`Handle edge search
`resp.
`
`2901
`Note connection edge
`search response
`
`origin
`from neighbor
`message
`
`902
`
`Edge selected
`
`‘
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 38 of 59 PageID #: 578
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 38 of 59 Page|D #: 578
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 35 of 39
`
`US 6,714,966 B1
`
`Broadcast
`
`message
`
`Fig. 30
`
`3001
`
`my
`
`N
`
`Y
`
`3002
`
`Generate internal
`
`message
`
`3003
`
`Set message sequence
`number
`
`3004
`
`Distribute internal
`
`message
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 39 of 59 PageID #: 579
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 39 of 59 Page|D #: 579
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 36 of 39
`
`US 6,714,966 B1
`
`
`
`.
`Acqunre message
`
`message
`
`Fig. 31
`
`31 01
`
`Pop message queue
`
`
`
`
`
`
`Return true
`
`3102
`
`
`Message
`retrieved
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 40 of 59 PageID #: 580
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 40 of 59 Page|D #: 580
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 37 of 39
`
`US 6,714,966 B1
`
`Handle condition check
`
`Fig. 32
`
`
`
`
`
`Same set of
`
`neighbors
`
`
`
`3205
`ct a neig
`or
`
`'
`C C
`of Sending process
`
`not In neihbor
`3206
`
`Send external message
`to Selected nelghbor
`
`3207
`
`Add neighbor
`
`3203
`.
`.
`Set up message with list
`Of nelghbors
`
`3204
`
`_
`Send internal message
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 41 of 59 PageID #: 581
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 41 of 59 Page|D #: 581
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 38 of 39
`
`US 6,714,966 B1
`
`Handle condition
`repair statement
`
`Ftg. 33
`
`3301
`
`Holes = =
`
`Select a neighbor not
`involved in condition
`
`
`
`
`3303
`
`Remove selected
`neighbor
`
`3304
`
`I
`
`Add neighbor
`
`|
`
`l
`
`Return
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 42 of 59 PageID #: 582
`Case 1:15—cv—OO228—RGA Document 7-2 Filed 03/31/15 Page 42 of 59 Page|D #: 582
`
`U.S. Patent
`
`Mar. 30, 2004
`
`Sheet 39 of 39
`
`US 6,714,966 B1
`
`Handle condition
`
`d
`
`bl
`
`h k
`
`OU C C CC
`
`.
`
`3401
`
`N
`
`Y
`
`
`3402
`
`
`Same set of
`
`
`neighbors
`
`N
`
`3406
`
`Create list of neighbors
`
`3407
`Send internal message
`to-from neighbor
`
`Reset diameter to 1
`
`
`
`3405
`
`Send internal message
`
`Return
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 43 of 59 PageID #: 583
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 43 of 59 Page|D #: 583
`
`US 6,714,966 B1
`
`1
`INFORMATION DELIVERY SERVICE
`
`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,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, the disclosures of which are incor-
`porated 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
`(“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
`
`60
`
`65
`
`2
`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
`
`an added computer.
`FIG. 4B illustrates the broadcast channel of FIG. 4A with
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`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.
`
`FIG. 5D illustrates two computers that are not neighbors
`who now have empty ports.
`FIG. 5E illustrates the neighbors with empty ports con-
`dition in the small regime.
`
`

`
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 44 of 59 PageID #: 584
`Case 1:15-cv-00228-RGA Document 7-2 Filed 03/31/15 Page 44 of 59 Page|D #: 584
`
`US 6,714,966 B1
`
`3
`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