IIU/it/LII
`
`Please type a plus Sign (+) inside this box
`UTILITY
`PATENT APPLICATION
`TRANSMITTAL
`h
`" I
`r
`r
`de37CFR 1.530
`'orr
`( n y ornonprovrsrona app rca Ions an
`r
`§
`( ))
`0
`APPLICATION ELEMENTS
`See MPEP chapter 600 concerning utility patent application contents.
`
`' {\lf;
`030048002US
`
`PTO/SB/OS (4/98) I4
`0
`95
`P
`E.
`’U
`V?- _
`JOINING A BROADCAST CHANNEL
`07/31/00
`'
`-
`a:
`EL404935398US
`
`Box Patent Application
`(0 I:
`ASS .'
`Assistant Commissioner for Paten'g
`
`Washington, DC. 20231
`
`
`
`5_ El Microfiche Computer Program (Appendix)
`6. Nucleotide and/or Amino Acid Sequence Submission
`Ofapplicable, all necessary)
`
`a I: CommterReadable Copy
`'
`.
`_
`
`b.
`|:) Paper COPY (Identlcal to computer Copy)
`C. E] Statement verifying identity of above copies
`
`Authorization for Extensions & Fee Transmittal
`
`(Submit an original and a duplicate for fee processing)
`2 - Specification
`[Total Pages]
`'
`X {preferred arrangement setforth below)
`
`- Descriptive Title of the Invention
`- Cross References to Related Applications
`
`- Statement Regarding Fed sponsored R & D
`- Reference to Microfiche Appendix
`- Background of the Invention
`
`
`
`
`- Brief Summary of the Invention
`
`- Brief Description of the Drawings (if filed)
`- Detailed Description
`- Claim(s)
`- Abstract of the Disclosure
`
`
`
`9"
`
`4.
`
`
`
`
`
`
`
` 16.
`If a CONTINUING APPLICATION, check appropriate box and supply the requrszte mformanon below and m a prelzmmary amendment
`|:| Continuation I: Divisional
`l:l Continuation—In-Part(ClP)
`otpriorApplication No.:
`
`
`
`
`
`Prior application information: Examiner
`
`For CONTINUATION or DIVISIONAL a
`s on] : The entire disclosure of the prior application, from which an oath or declaration is supplied under Box 4b,
`is conSIdered a part of the disclosure of the accompanying continuation or divisional application and is hereby incorporated by reference.
`The
`incorporation can only be relied upon when a portion has been inadvertently omitted from the submitted application parts.
`I: Claims the benefit of Provisional Application No.
`17. CORRESPONDENCE ADDRESS
`
`Group / Art Unit
`
`
`
`Customer Number 25096 / Barcode
`
`I
`
`IIIIIIIII III
`
`III III
`
`25096
`PATENT .TRADEMARK OFFICE
`
`Respectfully submltted,
`
`TYPED or PRINTED
`t
`I
`
`I
`
`i
`
`SIGNATURE
`
`E
`
`kmA Q =
`
`)
`
`cm
`
`Date
`
`
`Maurice
`'
`‘
`REGISTRATION NO. 33 273
`,\
`’a
`
`v
`I
`_
`
`K’s-s
`
`‘
`
`~
`
`I Om
`E -IEXHIBIT 1002 Pan 1 of 5
`0001
`
`
`
`
`
`
`
`
`
`ACCOMPANYING APPLICATION PARTS
`
`DDEDDDDD
`
`10.
`
`11.
`
`12.
`
`12
`
`’
`_K :5
`
`_\ .U‘
`
`ASSIgnment Papers (cover sheet & document(s))
`
`37 CFR 3.73(b) Statement
`.
`.
`(when there IS an assrgnee)
`
`Power of Attorney
`
`English Translation Document (if applicable)
`
`Information Disclosure
`Statement (IDS)/PTO-1449
`Preliminary Amendment
`
`Return Receipt Postcard
`
`Copies of IDS
`.
`.
`Citations
`
`Small
`Entity
`Statemenfis)
`
`Statement
`filed in prior. application,
`Status 5"” pmper and des're‘I
`
`Certified Copy of Priority Document(s)
`(if foreign priority is claimed)
`9 2‘ co fl
`
`
`
`
`
`
`E
`
`
`
`
`
`application,
`
`Drawing(s) (35usc113)
`
`[Total Sheets]
`
`Oath or Declaration
`
`[Total Pages]
`
`'
`
`a, El Newly executed (original or copy)
`b
`Copy from a prior application (37 CFR 1.63(d))
`(for continuation/divisional with Box 16 completed)
`.
`DELETION OF INVENTOR(S)
`1' I:I Signed statement attached deleting
`inventor(s)
`named
`in
`the
`prior
`see 37 CFR 1.63m” and 1330))
`*NOTE FOR ITEMS 1 & 13.’
`IN ORDER TO BE ENTITLED TO
`
`PAY SMALL ENTITY FEES, A SMALL ENTITY STATEMENT IS
`REQUIRED (37 CFR. § 1.27), EXCEPT IF ONE FILED IN A
`PRIOR APPLICATION IS RELIED UPON 37 CFR. ~ 1.28
`
`
`0001
`
`BUNGIE - EXHIBIT 1002 Part 1 of 5
`
`

`

`EXPRESS MAIL NO. EL404935398US
`
`JOINING A BROADCAST CHANNEL
`
`CROSS-REFERENCE TO RELATED APPLICATIONS
`
`This application is related to US. Patent Application No.
`
`,
`
`entitled “BROADCASTING NETWORK,” filed on July 31, 2000 (Attorney Docket
`
`5
`
`No. 030048001 US); US. Patent Application No.
`
`, entitled “JOINING A
`
`BROADCAST CHANNEL,” filed on July 31, 2000 (Attorney Docket No. 030048002 US);
`
`US. Patent Application No.
`
`, “LEAVING A BROADCAST CHANNEL,”
`
`filed on July 31, 2000 (Attorney Docket No. 030048003 US); US. Patent Application
`
`
`entitled “BROADCASTING ON A BROADCAST CHANNEL,” filed
`
`No.
`
`on July 31, 2000 (Attorney Docket No. 030048004 US); US. Patent Application
`
`No.
`
`entitled “CONTACTING A BROADCAST CHANNEL,” filed on
`
`July 31, 2000
`
`(Attorney Docket No.
`
`030048005 US); US.
`
`Patent Application
`
`No.
`
`,
`
`entitled
`
`“DISTRIBUTED AUCTION SYSTEM,”
`
`filed
`
`on
`
`July 31,2000
`
`(Attorney Docket No.
`
`030048006 US); US.
`
`Patent Application
`
`No.
`
`, entitled “AN INFORMATION DELIVERY SERVICE,” filed on
`
`July31,2000
`
`(Attorney Docket No.
`
`030048007 US); US.
`
`Patent Application
`
`No.
`
`, entitled “DISTRIBUTED CONFERENCING SYSTEM,” filed on
`
`
`
`and US. Patent Application
`
`July 31,2000 (Attorney Docket No. 030048008 US);
`
`
`No.
`
`entitled “DISTRIBUTED GAME ENVIRONMENT,”
`
`filed on
`
`20
`
`July 31, 2000 (Attorney Docket No. 030048009 US),
`
`the disclosures of which are
`
`incorporated herein by reference.
`
`TECHNICAL FIELD
`
`The described technology relates generally to a computer network and more
`
`particularly, to a broadcast channel for a subset of a computers of an underlying network.
`
`25
`
`BACKGROUND
`
`There are a wide variety of computer network communications techniques such
`as point-to-point network protocols,
`client/server middleware, multicasting network
`
`[03004-8002/SL003733.099]
`
`-1-
`
`7/31/00
`
`0002
`
`0002
`
`

`

`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
`
`5
`
`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 computers to communicate via point-to-point connections. The
`
`interconnection of all participants using point-to-point connections, while theoretically
`
`10
`
`possible, does not scale well as a number of participants grows.
`
`For example, each
`
`
`
`participating process would need to manage its direct connections 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 (“RFC”), database servers,
`
`and the common object request broker architecture (“CORBA”). Client/server middleware
`
`systems are not particularly 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
`
`25
`
`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.,
`
`30
`
`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
`
`[03004-8002/81003733099]
`
`-2-
`
`7/31/00
`
`0003
`
`0003
`
`

`

`protocols tend to place an unacceptable overhead on the underlying network. For example,
`
`UDP multicasting would swamp the Internet when trying to locate all possible participants.
`
`IP multicasting has other problems that include needing special-purpose infrastructure (e. g.,
`
`routers) to support the sharing of information efficiently.
`
`5
`
`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
`
`middleware 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
`
`10
`
`sharing the information.
`
`Thus,
`
`it is neither suitable nor desirable to use peer-to-peer
`
`middleware systems when more than a small number of participants 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
`
` suitable for the simultaneous sharing of information among a large number of the processes
`
`through the root node in order to be received by all participants.
`
`It would be desirable to have a reliable communications network that
`
`is
`
`that are widely distributed.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`Figure 1 illustrates a graph that is 4-regular and 4-connected which represents a
`
`20
`
`broadcast channel.
`
`Figure 2 illustrates a graph representing 20 computers connected to a broadcast
`
`channel.
`
`Figures 3A and 3B illustrate the process of connecting a new computer Z to the
`
`broadcast channel.
`
`25
`
`Figure 4A illustrates the broadcast channel of Figurel with an added
`
`computer.
`
`computer.
`
`30
`
`computer.
`
`Figure 4B illustrates the broadcast channel of Figure 4A with an added
`
`Figure 4C also illustrates the broadcast channel of Figure 4A with an added
`
`[03004-8002/SL003733 .099]
`
`-3 -
`
`7/31/00
`
`0004
`
`0004
`
`

`

`Figure 5A illustrates the disconnecting of a computer from the broadcast
`
`charmel in a planned manner.
`
`Figure 5B illustrates the disconnecting of a computer from the broadcast
`
`channel in an unplanned manner.
`
`Figure SC illustrates the neighbors with empty ports condition.
`
`Figure 5D illustrates two computers that are not neighbors who now have
`
`empty ports.
`
`regime.
`
`Figure 5E illustrates the neighbors with empty ports condition in the small
`
`Figure 5F illustrates the situation of Figure 5E when in the large regime.
`
`Figure 6 is a block diagram illustrating components of a computer that is
`
`connected to a broadcast channel.
`
`Figure 7 is a block diagram illustrating the sub-components of the broadcaster
`
`component in one embodiment.
`
`Figure 8 is a flow diagram illustrating the processing of the connect routine in
`
`one embodiment.
`
`Figure 9 is a flow diagram illustrating the processing of the seek portal
`
`computer routine in one embodiment.
`
`Figure 10 is a flow diagram illustrating the processing of the contact process
`
`5
`
`10
`
`
`
`20
`
`routine in one embodiment.
`
`Figure 11 is a flow diagram illustrating the processing of the connect request
`
`routine in one embodiment.
`
`Figure 12 is a flow diagram of the processing of the check for external call
`
`routine in one embodiment.
`
`Figure 13 is a flow diagram of the processing of the achieve connection routine
`
`in one embodiment.
`
`Figure 14 is a flow diagram illustrating the processing of the external
`
`dispatcher routine in one embodiment.
`
`Figure 15 is a flow diagram illustrating the processing of the handle seeking
`
`connection call routine in one embodiment.
`
`Figure 16 is a flow diagram illustrating processing of the handle connection
`
`25
`
`30
`
`request call routine in one embodiment.
`
`[03004-8002/SL003733.099]
`
`-4-
`
`7/31/00
`
`0005
`
`0005
`
`

`

`Figure 17 is a flow diagram illustrating the processing of the add neighbor
`
`routine in one embodiment.
`
`Figure 18 is a flow diagram illustrating the processing of the forward
`
`connection edge search routine in one embodiment.
`
`5
`
`Figure 19 is a flow diagram illustrating the processing of the handle edge
`
`proposal call routine.
`
`Figure 20 is a flow diagram illustrating the processing of the handle port
`
`connection call routine in one embodiment.
`
`Figure 21 is a flow diagram illustrating the processing of the fill hole routine in
`
`10
`
`one embodiment.
`
`Figure 22 is a flow diagram illustrating the processing of the internal dispatcher
`
`routine in one embodiment.
`
`Figure 23 is a flow diagram illustrating the processing of the handle broadcast
`
` broadcast message routine in one embodiment.
`
`message routine in one embodiment.
`
`Figure 24 is a flow diagram illustrating the processing of the distribute
`
`
`
`Figure 26 is a flow diagram illustrating the processing of the handle connection
`port search statement routine in one embodiment.
`
`Figure 27 is a flow diagram illustrating the processing of the court neighbor
`
`20
`
`routine in one embodiment.
`
`Figure 28 is a flow diagram illustrating the processing of the handle connection
`
`edge search call routine in one embodiment.
`
`Figure 29 is a flow diagram illustrating the processing of the handle connection
`
`edge search response routine in one embodiment.
`
`25
`
`Figure 30 is a flow diagram illustrating the processing of the broadcast routine
`
`in one embodiment.
`
`Figure 31 is a flow diagram illustrating the processing of the acquire message
`
`routine in one embodiment.
`
`Figure 32 is a flow diagram illustrating processing of the handle condition
`
`30
`
`check message in one embodiment.
`
`Figure 33 is a flow diagram illustrating processing of the handle condition
`
`repair statement routine in one embodiment.
`
`[03004-8002/SL003733.099]
`
`-5-
`
`7/31/00
`
`0006
`
`0006
`
`

`

`Figure 34 is a flow diagram illustrating the processing of the handle condition
`
`double check routine.
`
`DETAILED DESCRIPTION
`
`A broadcast technique in which a broadcast channel overlays a point—to—point
`
`5
`
`communications network is provided. The broadcasting of a message over the broadcast
`
`channel is effectively a multicast to those computers of the network that are currently
`
`connected to the broadcast charmel.
`
`In one embodiment, the broadcast technique provides a
`
`logical broadcast channel to which host computers through their executing processes can be
`
`connected.
`
`Each computer that
`
`is connected to the broadcast channel can broadcast
`
`10 messages onto and receive messages off of the broadcast channel. Each computer that is
`
`
`
`
`
`connected to the broadcast channel receives all messages that are broadcast while it is
`
`connected. The logical broadcast channel is implemented using an underlying network
`
`system (e.g., the Internet) that allows each computer connected to the underlying network
`
`system to send messages to each other connected computer using each computer’s address.
`
`Thus, the broadcast technique effectively provides a broadcast channel using an underlying
`
`network system that sends messages on a point-to-point basis.
`
`The broadcast technique overlays the underlying network system with a graph
`
`of point-to-point connections (i. e., edges) between host computers (1'. 6., nodes) through
`
`which the broadcast channel
`
`is implemented.
`
`In one embodiment, each computer is
`
`20
`
`connected to four other computers, referred to as neighbors.
`
`(Actually, a process executing
`
`on a computer is connected to four other processes executing on this or four other
`
`computers.) To broadcast a message, the originating computer sends the message to each of
`
`its neighbors using its point-to-point connections. Each computer that receives the message
`
`then sends the message to its three other neighbors using the point-to-point connections.
`
`In
`
`25
`
`this way, the message is propagated to each computer using the underlying network to effect
`
`the broadcasting of the message to each computer over a logical broadcast charmel. A graph
`
`in which each node is connected to four other nodes is referred to as a 4-regular graph. The
`
`use of a 4-regular graph means that a computer would become disconnected from the
`
`broadcast channel only if all four of the connections to its neighbors fail. The graph used by
`
`30
`
`the broadcast technique also has the property that it would take a failure of four computers to
`
`
`
`[03004-8002/SL003733.099]
`
`-6-
`
`7/31/00
`
`0007
`
`0007
`
`

`

`divide the graph into disjoint sub-graphs, that is two separate broadcast channels. This
`
`property is referred to as being 4-connected. Thus, the graph is both 4-regular and 4-
`
`connected.
`
`Figure 1 illustrates a graph that is 4-regular and 4-connected which represents
`
`5
`
`the broadcast channel. Each of the nine nodes A-I represents a computer that is connected to
`
`the broadcast channel, and each of the edges represents an “edge” connection between two
`
`computers of the broadcast channel. The time it takes to broadcast a message to each
`
`computer on the broadcast channel depends on the speed of the connections between the
`
`computers and the number of connections between the originating computer and each other
`
`10
`
`computer on the broadcast channel. The minimum number of connections that a message
`
`would need to traverse between each pair of computers is the “distance” between the
`
`computers (i.e., the shortest path between the two nodes of the graph). For example, the
`
`distance between computers A and F is one because computerA is directly connected to
`
`computer F. The distance between computers A and B is two because there is no direct
`
`connection between computers A and B, but computer F is directly connected to computer B.
`
`Thus, a message originating at computer A would be sent directly to computer F, and then
`
`sent from computer F to computer B. The maximum of the distances between the computers
`
`is the “diameter” of broadcast channel. The diameter of the broadcast channel represented
`
`by Figure 1 is two. That is, a message sent by any computer would traverse no more than
`
`
`
`20
`
`two connections to reach every other computer. Figure 2 illustrates a graph representing 20
`
`computers connected to a broadcast channel. The diameter of this broadcast channel is 4. In
`
`particular, the shortest path between computers 1 and 3 contains four connections (1-12, 12-
`
`15, 15-18, and 18-3).
`
`The broadcast technique includes (1) the connecting of computers to the
`
`25
`
`broadcast channel (i. e., composing the graph), (2) the broadcasting of messages over the
`
`broadcast channel (i.e., broadcasting through the graph), and (3) the disconnecting of
`
`computers from the broadcast charmel (1'. e., decomposing the graph) composing the graph.
`
`Composing the Graph
`
`To connect to the broadcast channel, the computer seeking the connection first
`
`30
`
`locates a computer that is currently fully connected to the broadcast channel and then
`
`[03004-8002/SL003733 .099]
`
`-7-
`
`7/31/00
`
`0008
`
`0008
`
`

`

`establishes a connection with four of the computers that are already connected to the
`
`broadcast channel.
`
`(This assumes that there are at least four computers already connected to
`
`the broadcast channel. When there are fewer than five computers connected, the broadcast
`
`channel cannot be a 4-regu1ar graph.
`
`In such a case, the broadcast channel is considered to
`
`5
`
`be in a “small regime.” The broadcast technique for the small regime is described below in
`
`detail. When five or more computers are connected, the broadcast channel is considered to
`
`be in the “large regime.” This description assumes that the broadcast channel is in the large
`
`regime, unless specified otherwise.) Thus,
`
`the process of connecting to the broadcast
`
`channel includes locating the broadcast channel, identifying the neighbors for the connecting
`
`10
`
`computer, and then connecting to each identified neighbor. Each computer is aware of one
`
`or more “portal computers” through which that computer may locate the broadcast charmel.
`
`A seeking computer locates the broadcast channel by contacting the portal computers until it
`
`finds one that is currently fully connected to the broadcast channel. The found portal
`
`computer then directs the identifying of four computers (i.e., to be the seeking computer’s
`
`neighbors) to which the seeking computer is to connect. Each of these four computers then
`
`cooperates with the seeking computer to effect the connecting of the seeking computer to the
`
`broadcast channel. A computer that has started the process of locating a portal computer, but
`
`does not yet have a neighbor, is in the “seeking connection state.” A computer that is
`
`connected to at least one neighbor, but not yet four neighbors, is in the “partially connected
`
`state.” A computer that is currently, or has been, previously connected to four neighbors is
`
`
`
`in the “fully connected state.”
`
`Since the broadcast channel
`
`is a 4-regular graph, each of the identified
`
`computers is already connected to four computers.
`
`Thus, some connections between
`
`computers need to be broken so that the seeking computer can connect to four computers. In
`
`25
`
`one embodiment, the broadcast technique identifies two pairs of computers that are currently
`
`connected to each other. Each of these pairs of computers breaks the connection between
`
`them, and then each of the four computers (two from each pair) connects to the seeking
`
`computer. Figures 3A and 3B illustrate the process of a new computer Z connecting to the
`
`broadcast channel.
`
`Figure 3A illustrates the broadcast channel before computer Z is
`
`30
`
`connected. The pairs of computers B and E and computers C and D are the two pairs that are
`
`identified as the neighbors for the new computer Z. The connections between each of these
`
`pairs is broken, and a connection between computer Z and each of computers B, C, D, and E
`
`[03004-8002/SL003733.099]
`
`-8-
`
`7/31/00
`
`0009
`
`0009
`
`

`

`is established as indicated by Figure 3B. The process of breaking the connection between
`
`two neighbors and reconnecting each of the former neighbors to another computer is referred
`
`to as “edge pinning” as the edge between two nodes may be considered to be stretched and
`
`pinned to a new node.
`
`5
`
`Each
`
`computer
`
`connected to
`
`the
`
`broadcast
`
`channel
`
`allocates
`
`five
`
`communications ports for communicating with other computers. Four of the ports are
`
`referred to as “interna ” ports because they are the ports through which the messages of the
`
`broadcast channels are sent. The connections between internal ports of neighbors are
`
`referred to as “internal” connections. Thus, the internal connections of the broadcast channel
`
`10
`
`form the 4-regular and 4-c0nnected graph. The fifth port is referred to as an “external” port
`
`because it is used for sending non-broadcast messages between two computers. Neighbors
`
`can send non-broadcast messages either through their internal ports of their connection or
`
` computer.
`
`through their external ports. A seeking computer uses external ports when locating a portal
`
`
`
`In one embodiment,
`
`the broadcast
`
`technique establishes
`
`the computer
`
`connections using the TCP/IP communications protocol, which is a point-to-point protocol,
`
`as the underlying network. The TCP/IP protocol provides for reliable and ordered delivery
`
`of messages between computers. The TCP/IP protocol provides each computer with a “port
`
`space” that is shared among all the processes that may execute on that computer. The ports
`
`are identified by numbers from 0 to 65,535. The first 2056 ports are reserved for specific
`
`applications (e. g, port 80 for HTTP messages). The remainder of the ports are user ports
`
`that are available to any process.
`
`In one embodiment, a set of port numbers can be reserved
`
`for use by the computer connected to the broadcast channel.
`
`In an alternative embodiment,
`
`the port numbers used are dynamically identified by each computer.
`
`Each computer
`
`25
`
`dynamically identifies an available port to be used as its call-in port. This call-in port is used
`
`to establish connections with the external port and the internal ports. Each computer that is
`
`connected to the broadcast channel can receive non-broadcast messages through its external
`
`port. A seeking computer tries “dialing” the port numbers of the portal computers until a
`
`portal computer “answers,” a call on its call-in port. A portal computer answers when it is
`
`30
`
`connected to or attempting to connect to the broadcast channel and its call-in port is dialed.
`
`(In this description, a telephone metaphor is used to describe the connections.) When a
`
`computer receives a call on its call-in port, it transfers the call to another port. Thus, the
`
`[03004-8002/SL003733.099]
`
`-9-
`
`7/31/00
`
`0010
`
`0010
`
`

`

`seeking computer actually communicates through that transfer-to port, which is the external
`
`port. The call is transferred so that other computers can place calls to that computer via the
`
`call-in port. The seeking computer then communicates via that external port to request the
`
`portal computer to assist in connecting the seeking computer to the broadcast channel. The
`
`5
`
`seeking computer could identify the call-in port number of a portal computer by successively
`
`dialing each port in port number order. As discussed below in detail, the broadcast technique
`
`uses a hashing algorithm to select the port number order, which may result in improved
`
`performance.
`
`A seeking computer could connect to the broadcast channel by connecting to
`
`10
`
`computers either directly connected to the found portal computer or directly connected to one
`
`
`
`of its neighbors. A possible problem with such a scheme for identifying the neighbors for
`
`the seeking computer is that the diameter of the broadcast channel may increase when each
`
`seeking computer uses the same found portal computer and establishes a connection to the
`
`broadcast channel directly through that found portal computer. Conceptually,
`
`the graph
`
`becomes elongated in the direction of where the new nodes are added. Figures 4A—4C
`
`illustrate that possible problem. Figure 4A illustrates the broadcast channel of Figure 1 with
`
`an added computer. Computer J was connected to the broadcast channel by edge pinning
`
`edges OD and E-H to computer J. The diameter of this broadcast channel is still two.
`
`Figure 4B illustrates the broadcast channel of Figure 4A with an added computer.
`
`Computer K was connected to the broadcast channel by edge pinning edges E-J and B-C to
`
`computer K. The diameter of this broadcast channel is three, because the shortest path from
`
`computer G to computer K is through edges G—A, A-E, and E-K. Figure 4C also illustrates
`
`the broadcast channel of Figure 4A with an added computer. Computer K was connected to
`
`the broadcast channel by edge pinning edges D-G and E-J to computer K. The diameter of
`
`25
`
`this broadcast channel is, however, still two. Thus, the selection of neighbors impacts the
`
`diameter of the broadcast channel. To help minimize the diameter, the broadcast technique
`
`uses a random selection technique to identify the four neighbors of a computer in the seeking
`
`connection state. The random selection technique tends to distribute the connections to new
`
`seeking computers throughout the computers of the broadcast channel which may result in
`
`30
`
`smaller overall diameters.
`
`[03004-8002/SL003733.099]
`
`—10-
`
`7/31/00
`
`0011
`
`0011
`
`

`

`Broadcasting Throqu the Graph
`
`As described above, each computer that is connected to the broadcast channel
`
`can broadcast messages onto the broadcast channel and does receive all messages that are
`
`broadcast on the broadcast channel. The computer that originates a message to be broadcast
`
`5
`
`sends that message to each of its four neighbors using the internal connections. When a
`
`computer receives a broadcast message from a neighbor, it sends the message to its three
`
`other neighbors. Each computer on the broadcast channel, except the originating computer,
`
`will thus receive a copy of each broadcast message from each of its four neighbors. Each
`
`computer, however, only sends the first copy of the message that it receives to its neighbors
`
`10
`
`and disregards subsequently received copies. Thus, the total number of copies of a message
`
`that is sent between the computers is 3N+1, where N is the number of computers connected
`
`to the broadcast channel. Each computer sends three copies of the message, except for the
`
`
`
`originating computer, which sends four copies of the message.
`
`The redundancy of the message sending helps to ensure the overall reliability
`
`of the broadcast channel.
`
`Since each computer has four connections to the broadcast
`
`channel, if one computer fails during the broadcast of a message, its neighbors have three
`
`other connections through which they will receive copies of the broadcast message. Also, if
`
`the internal connection between two computers is slow, each computer has three other
`
`connections through which it may receive a copy of each message sooner.
`
`Each computer
`
`that originates a message numbers
`
`its own messages
`
`sequentially. Because of the dynamic nature of the broadcast channel and because there are
`
`many possible connection paths between computers, the messages may be received out of
`
`order. For example, the distance between an originating computer and a certain receiving
`
`computer may be four. After sending the first message,
`
`the originating computer and
`
`25
`
`receiving computer may become neighbors and thus the distance between them changes to
`
`one. The first message may have to travel a distance of four to reach the receiving computer.
`
`The second message only has to travel a distance of one. Thus, it is possible for the second
`
`message to reach the receiving computer before the first message.
`
`When the broadcast channel is in a steady state (i. e., no computers connecting
`
`30
`
`or disconnecting from the broadcast channel), out-of-order messages are not a problem
`
`because each computer will eventually receive both messages and can queue messages until
`
`all earlier ordered messages are received.
`
`If, however, the broadcast channel is not in a
`
`[03004-8002/SL003733.099]
`
`-1 1-
`
`7/31/00
`
`0012
`
`0012
`
`

`

`steady state,
`
`then problems can occur.
`
`In particular, a computer may connect to the
`
`broadcast channel after the second message has already been received and forwarded on by
`
`its new neighbors. When a new neighbor eventually receives the first message, it sends the
`
`message to the newly connected computer. Thus, the newly connected computer will receive
`
`5
`
`the first message, but will not receive the second message. If the newly connected computer
`
`needs to process the messages in order, it would wait indefinitely for the second message.
`
`One solution to this problem is to have each computer queue all the messages
`
`that it receives until it can send them in their proper order to its neighbors. This solution,
`
`however, may tend to slow down the propagation of messages through the computers of the
`
`10
`
`broadcast charmel. Another solution that may have less impact on the propagation speed is
`
`
`
`to queue messages only at computers who are neighbors of the newly connected computers.
`
`Each already connected neighbor would forward messages as it receives them to its other
`
`neighbors who are not newly connected, but not to the newly connected neighbor. The
`
`already connected neighbor would only forward messages from each originating computer to
`
`the newly connected computer when it can ensure that no gaps in the messages from that
`
`originating computer will occur.
`
`In one embodiment, the already connected neighbor may
`
`track the highest sequence number of the messages already received and forwarded on from
`
`each originating computer. The already connected computer will send only higher numbered
`
`messages from the originating computers to the newly connected computer. Once all lower
`
`numbered messages have been received from all originating computers, then the already
`
`connected computer can treat the newly connected computer as its other neighbors and
`
`simply forward each message as it is received.
`
`In another embodiment, each computer may
`
`queue messages and only forwards to the newly connected computer those messages as the
`
`gaps are filled in. For example, a computer might receive messages 4 and 5 and then receive
`
`25 message 3. In such a case, the already connected computer would forward queue messages 4
`
`and 5. When message 3 is finally received,
`
`the already connected computer will send
`
`messages 3, 4, and 5 to the newly connected computer. If messages 4 and 5 were sent to the
`
`newly connected computer before message 3, then the newly connected compu