`
`BUNGIE — EXHIBIT 1002 Pan 3 of 5
`0595
`
`0595
`
`BUNGIE - EXHIBIT 1002 Part 3 of 5
`
`
`
`
`
`0596
`
`0596
`
`
`
`0597
`
`
`
`0597
`
`
`
`
`
`0598
`
`0598
`
`
`
`
`
`
`
`0599
`
`0599
`
`
`
`'H0~JLeCanmq$;
`POI"
`"
`
`
`
`
`
`0600
`
`0600
`
`
`
`
`
`0601
`
`0601
`
`
`
`
`
`
`
` Bro!) to;
`m .,
`
`
`
`0602
`
`0602
`
`
`
`20
`
`
`
`
`0603
`
`0603
`
`
`
`
`
`0604
`
`0604
`
`
`
`
`
`0605
`
`0605
`
`
`
`
`
`0606
`
`0606
`
`
`
`
`
`0607
`
`0607
`
`
`
`
`
`0608
`
`0608
`
`
`
`
`
`0609
`
`0609
`
`
`
`
`
` ’64 music 3
`
`m7? M— 5
`o ).
`
`
`0610
`
`
`
`0610
`
`
`
`
`
`
`0611
`
`0611
`
`
`
`0612
`
`
`
`W
`
`0612
`
`
`
`U.S. Patent Application No. 09/629,575
`
`EXPRESS MAIL NO. EI’AO4935353US
`
`BROADCASTING ON A BROADCAST CHANNEL
`
`CROSS-REFERENCE TO RELATED APPLICATIONS
`
`.
`
`This application is related to U.S. Patent Application No.
`
`.
`
`entitled “BROADCASTING NETWORK,” filed on July 31, 2000 (Attorney Docket
`
`No. 030048001 US); U.S. Patent Application No.
`
`, entitled “JOINING A
`
`BROADCAST CHANNEL,” filed on July 31, 2000 (Attorney Docket No. 030048002 US);
`
`U.S. Patent Application No.
`
`, “LEAVING A BROADCAST CHANNEL,”
`
`10
`
`15
`
`20
`
`filed on July 31,’ 2000 (Attorney Docket No. 030048003 US); U.S. Patent Application
`
`
`entitled “BROADCASTING ON A BROADCAST CHANNEL,” filed
`
`No.
`
`on July 31, 2000 (Attorney Docket No. 030048004 US); U.S. Patent Application
` No.
`
`entitled “CONTACTING A BROADCAST CHANNEL,” filed on
`
`July 31,2000
`
`(Attorney Docket No.
`
`030048005 US); U.S.
`
`Patent Application
`
`No.
`
`,
`
`entitled
`
`“DISTRIBUTED AUCTION SYSTEM,”
`
`filed
`
`on
`
`July 31, 2000
`
`(Attomey Docket No.
`
`030048006 US); U.S.
`
`Patent Application
`
`No.
`July 31, 2000
`
`, entitled “AN INFORMATION DELIVERY SERVICE,” filed on
`(Attorney Docket No.
`030048007 US); U.S.
`Patent Application
`
`No.
`
`, entitled “DISTRIBUTED CONFERENCING SYSTEM,” filed on
`
`July 31, 2000 (Attorney Docket No. 030048008 US); and U.S. Patent Application
`
`
`entitled “DISTRIBUTED GAME ENVIRONMENT,” filed on
`
`No.
`
`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
`
`[mom—80045190373100]
`
`-l-
`
`751/00
`
`0613
`
`0613
`
`
`
`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 computers 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 connections to all other participating
`
`processes. Programmers, however, find it very difl'rcult 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 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 cormnunications 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'
`
`[osmooalswosmioo]
`
`-2-
`
`7131/00
`
`10
`
`15
`
`20
`
`25
`
`30
`
`0614
`
`0614
`
`
`
`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.
`
`The peer-to-peer middleware commmicafions 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
`
`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
`
`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
`
`10
`
`15
`
`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
`
`computer.
`
`computer.
`
`30
`
`computer.
`
`Figure 4A illustrates the broadcast channel of Figure] with an added
`
`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
`
`[osooa-aooalswoz'nuoo]
`
`-3-
`
`7/31/00
`
`0615
`
`0615
`
`
`
`Figure 5A illustrates the disconnecting of a computer from the broadcast
`
`channel in a planned manner.
`
`Figure SB illustrates the disconnecting of a computer from the broadcast
`
`channel in an unplanned manner.
`
`Figure 5C 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
`
`10
`
`15
`
`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.
`
`20
`
`routine in one embodiment.
`
`Figure 10 is a flow diagram illustrating the processing of the contact process
`
`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.
`
`25
`
`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.
`
`30
`
`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
`
`request call routine in one embodiment.
`
`[03004-8004/SL003'BJ. 100]
`
`~4-
`
`7/31/00
`
`0616
`
`0616
`
`
`
`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.
`
`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
`
`message routine in one embodiment.
`
`15
`
`Figure 24 is a flow diagram illustrating the processing of the distribute
`
`broadcast message routine in one embodiment.
`
`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.
`
`30
`
`Figure 32 is a flow diagram illustrating processing of the handle condition
`check message in one embodiment.
`
`Figure 33 is a flow diagram illustrating processing of the handle condition
`repair statement routine in one embodiment.
`
`panama/31.003733. 100]
`
`-5-
`
`701/00
`
`'0617
`
`0617
`
`
`
`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
`
`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 channel.
`
`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
`
`messages onto and receive messages ofi‘ 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 efi'ectively 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'.e., nodes) through
`
`which the broadcast channel
`
`is implemented.
`
`In one embodiment, each computer is
`
`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
`
`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 channel. 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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`broadcast channel only if all four of the connections to its neighbors fail. The graph used by
`the broadcast technique also has the property that it would take a failure of four computers to
`
`[oaooasoo4/swoa73uool
`
`-6-
`
`7/31/00
`
`0618
`
`0618
`
`
`
`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
`
`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
`
`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 charmel. The diameter of the broadcast channel represented
`
`by Figure l is two. That is, a message sent by any computer would traverse no more than
`
`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 (l-12, 12-
`
`15, 15-18, and 18-3).
`
`The broadcast technique includes (1) the connecting of computers to the
`broadcast channel (i. e., composing the graph), (2) the broadcasting of messages over the
`broadcast charmel
`(i. e., broadcasting through the graph), and (3) the disconnecting of
`computers from the broadcast channel (i. e., decomposing the graph) composing the graph.
`
`10
`
`15
`
`20
`
`25
`
`Composing the Grth
`
`30
`
`To connect to the broadcast channel, the computer seeking the connection first
`locates a computer that is currently fully connected to the broadcast channel and then
`
`(03004-8004/SL003733JOO]
`
`-7-
`
`7/31/00
`
`0619
`
`0619
`
`
`
`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-regular graph.
`
`In such a case, the broadcast channel is considered to
`
`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 die broadcast channel, identifying the neighbors for the connecting
`
`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 channel.
`
`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
`
`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
`
`10
`
`15
`
`20
`
`25
`
`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 2 is
`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
`
`30
`
`'
`
`pairs is broken, and a connection between computer Z and each of computers B, C, D, and E
`
`[03004~8004ISM03733. 1001
`
`-8-
`
`7/31/00
`
`0620 '
`
`0620
`
`
`
`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.
`
`Each
`
`computer
`
`connected
`
`to
`
`the
`
`broadcast
`
`channel
`
`allocates
`
`five
`
`communications ports for communicating with other computers.
`
`Four of the ports are
`
`referred to as “intern ” 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
`
`form the 4-regular and 4-connected graph. The fifih 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
`
`through their external ports. A seeking computer uses external ports when locating a portal
`
`computer.
`
`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
`
`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
`
`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-8004/SL003733. 100]
`
`-9-
`
`7/31/00
`
`10
`
`15
`
`20
`
`25
`
`30
`
`0621
`
`0621
`
`
`
`seeking computer actually commnnicates 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
`
`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
`
`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 l 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 48 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
`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
`smaller overall diameters.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`[MOM—80041810037233.1001
`
`- l 0-
`
`7/31/00
`
`0622
`
`0622
`
`
`
`Broadcastin Throu
`
`the Gra h
`
`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
`
`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 hour each of its four neighbors. Each
`
`computer, however, only sends the first copy of the message that it receives to its neighbors
`
`and disregards subsequently received copies. Thus, the total number of copies of a message
`
`that is sent between the computers is 3N+l, 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 aimessage, 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
`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
`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-8004/SLOO3733JOO]
`-l 1-
`7/31/00
`
`10
`
`15
`
`20
`
`25
`
`30
`
`0623
`
`0623
`
`
`
`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
`
`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
`
`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
`
`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 computer would
`
`process messages 4 and 5 and disregard message 3. Because the already connected computer
`
`queues messages 4 and 5, the newly connected computer will be able to process message 3.
`It is possible that a newly connected computer will receive a set of messages from an
`
`originating computer through one neighbor and then receive another set of message from the
`
`[03004-8004lsw03733JOO]
`
`-12-
`
`7/51/00
`
`10
`
`15
`
`20
`
`25
`
`30
`
`0624
`
`0624
`
`
`
`same originating computer through another neighbor. Ifthe second set of messages contains
`
`a message that is ordered earlier than the messages of the first set received, then the newly
`
`connected computer may ignore that earlier ordered message if the computer already
`
`processed those later ordered messages.
`
`Decomposing the Graph
`
`.
`
`A connected computer disconnects from the broadcast channel either in a
`
`planned or unplanned manner. When a computer disconnects in a planned manner, it sends a
`
`disconnect message to each of its four neighbors. The disconnect message includes a list that
`
`identifies the four neighbors of the disconnecting computer. When a neighbor receives the
`
`disconnect message,
`
`it tries to connect to one of the computers on the list.
`
`In one
`
`embodiment, the first computer in the list will try to connect to the second computer in the
`
`list, and the third computer in the list will try to connect to the fourth computer in the list. If
`
`a computer cannot connect (e. g., the first and second computers are already connected), then
`
`the computers may try connecting in various other combinations.
`
`If connections cannot be
`
`established, each computer broadcasts a message that it needs to establish a connection with
`
`another computer. When a computer with an available internal port receives the message, it
`
`can then establish a connection with the computer that broadcast the message. Figures 5A-
`5D illustrate the disconnecting of a computer from the broadcast channel.
`Figure 5A
`illustrates the disconnecting of a computer from the broadcaSt channel in a planned manner.
`
`When computer H decides to disconnect, it sends its list of neighbors to each of its neighbors
`
`(computers A, E, F and I) and then disconnects from each of its neighbors.
`
`When
`
`computers A and I receive the message they establish a connection between them as
`
`indicated by the dashed line, and similarly for computers E and F.
`
`When a computer disconnects in an unplanned manner, such as resulting from
`
`the neighbors connected to the disconnected computer recognize the
`a power failure,
`disconnection when each attempts to send its next message to the now disconnected
`
`computer. Each former neighbor of the disconnected computer recognizes that it is short one
`
`connection (i.e., it has a hole or empty port). When a connected computer detects that one of
`its neighbors is now disconnected, it broadcasts a port connection request on the broadcast
`channel, which indicates that it has one internal port that needs a connection. The port
`connection request identifies the call-in port of the requesting computer