`
`
`set eauveorme's
`Woles-to-&y<
`
`©
`woles—toe\\
`
`Souk Ectand
`Wescags
`Pr hee
`i:
`LAAT esp
`
`+
`
`
`
`
` =i|HolFen )
`
`
`
`vy
`
`holes tofIl
`
`BUNGIE - EXHIBIT 1002 Part 3 of 5
`0595
`
`0595
`
`BUNGIE - EXHIBIT 1002 Part 3 of 5
`
`

`

`
`
`0596
`
`0596
`
`

`

`Fic l®
`
`
`
`
`
`0597
`
`0597
`
`

`

`Fig 14
`
`
`
`out mes Sese
`
` unM\essa
`
`0598
`
`0598
`
`

`

`not naig bbe?
`
`
`
` cu\ler i)
`
`
`=—;=Re acer
`
`0599
`
`0599
`
`

`

`
`
`0600
`
`0600
`
`

`

`o3f
`
`.
`
`;
`038 y
`Jagat wees
`
`hotly vO og
`on| type“=
`
`
`SoPande
`
`;
`
`O-
`
`proad cost
`Stetl
`
`'
`
`Po
`HandleBeoodred
`
`Mss
`
`Y
`
`‘
`
`0601
`
`0601
`
`

`

`
`
`
`0602
`
`0602
`
`

`

`2%
`
`Dist buf
`
`
`
`Fe, 2
`
`Broadees\
`Frow Watchbow
`
`
`0603
`
`0603
`
`€
`

`

`
`
`0604
`
`0604
`
`

`

`2\
`
`
`
`0605
`
`0605
`
`

`

`
`
`0606
`
`0606
`
`

`

`
`
`F.l\ HolCeeles
`
`
`0607
`
`0607
`
`

`

`
`
`0608
`
`0608
`
`

`

`
`
`0609
`
`0609
`
`

`

`
`
`
`
`0610
`
`0610
`
`

`

`47
`
`
`
`0611
`
`0611
`
`

`

`
`
`creoke (ist of
`wuighbers
`
`
`
`0612
`
`0612
`
`

`

`U.S. Patent Application No. 09/629,575
`
`EXPRESS MAIL NO, E1404935353uUS
`
`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,”
`filed on July 31,2000 (Attorney Docket No. 030048003 US); U.S. Patent Application
`No.
`entitled “BROADCASTING ON A BROADCAST CHANNEL,”filed
`
`on July 31, 2000 (Attorney Docket No. 030048004 US); U.S. Patent Application
`No.
`entitled “CONTACTING A BROADCAST CHANNEL,”filed on
`
`July 31,2000
`(Attomey 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.
`, entitled “AN INFORMATION DELIVERY SERVICE,” filed on
`July 31, 2000
`(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
`No.
`entitled “DISTRIBUTED GAME ENVIRONMENT,” filed on
`
`July 31, 2000 (Attorney Docket No. 030048009 US),
`the disclosures of which are
`incorporated herein by reference.
`
`20
`
`TECHNICAL FIELD
`
`The described technology relates generally to a computer network and more
`particularly, to a broadcast channel for a subset of a computersof an underlying network.
`
`25
`
`BACKGROUND
`
`There are a wide variety of computer network communications techniques such
`as point-to-poimt network protocols,
`client/server middleware, multicasting network
`
`{03004-8004/S1.003733.100)
`
`-1-
`
`713100
`
`0613
`
`0613
`
`

`

`protocols, and peer-to-peer middleware. Each of these communications techniques have
`their advantages and disadvantages, but noneis 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 mannerto 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 manageits direct connectionsto 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 numberof direct connections that they can support. This
`limits the numberofpossible 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 procedurecalls (“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 otherclient
`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 uponthereliability of the single server. Thus, a failure at a single computer(i.e.,
`the server) would prevent communications between anyoftheclients.
`The multicasting network protocols allow the sending of broadcast messagesto
`multiple recipients of a network. The current implementations of such multicasting network:
`[03004-8004/SL003733.100}
`-2-
`731/00
`
`20
`
`25
`
`30
`
`0614
`
`0614
`
`

`

`protocols tend to place an unacceptable overhead on the underlying network. For example,
`UDP multicasting would swampthe Internet when trying to locate all possible participants.
`IP multicasting has other problems that include needing special-purposeinfrastructure(e.g.,
`routers) to support the sharing of informationefficiently.
`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
`sharing the information.
`Thus,
`it is neither suitable nor desirable to use peer-to-peer
`middleware systems when more than a small numberofparticipants is desired.
`In addition,
`the underlying architecture of the T.120 Internet standardis a tree structure, which relies on
`the root node ofthetree for reliability of the entire network. That is, each message must pass
`through the root nodein orderto 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 numberofthe processes
`that are widely distributed.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Figure 1 illustrates a graph that is 4-regular and 4-connected which represents a
`broadcast channel.
`
`20
`
`Figure 2 illustrates a graph representing 20 computers connected to a broadcast
`
`channel.
`
`Figures 3A and 3Billustrate the process of connecting a new computer Z to the
`broadcast channel.
`
`25
`
`Figure 4A illustrates the broadcast channel of Figure 1 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-8004/SL003733.100}
`
`-3-
`
`7131/00
`
`0615
`
`0615
`
`

`

`Figure 5A illustrates the disconnecting of a computer from the broadcast
`channel in a planned manner.
`Figure 5B illustrates the disconnecting of a computer from the broadcast
`channel in an unplanned manner.
`Figure SCillustrates 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 SE whenin the large regime.
`Figure 6 is a block diagram illustrating components of a computer that is
`connected to a broadcastchannel.
`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 connectroutine 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
`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 ofthe 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
`connectioncall routine in one embodiment.
`Figure 16 is a flow diagram illustrating processing of the handle connection
`request call routine in one embodiment.
`
`[03004-8004/SL003733.100)
`
`-4-
`
`7131/00
`
`20
`
`25
`
`30
`
`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
`connectioncall routine in one embodiment.
`
`Figure 21 is a flow diagram illustrating the processingofthefill hole routine in
`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.
`Figure 24 is a flow diagram illustrating the processing of the distribute
`broadcast messageroutine in one embodiment.
`Figure 26 is a flow diagram illustrating the processing of the handle connection
`port search statementroutine in one embodiment.
`Figure 27 is a flow diagram illustrating the processing of the court neighbor
`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 responseroutine in one embodiment.
`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
`check message in one embodiment.
`Figure 33 is a flow diagram illustrating processing of the handle condition
`repair statementroutine in one embodiment.
`
`(03004-8004/SL003733.100]
`
`-5-
`
`7131100
`
`20
`
`25
`
`30
`
`“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 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 channelusing an underlying
`network system that sends messages on a point-to-pointbasis.
`The broadcast technique overlays the underlying network system with a graph
`of point-to-point connections(i.e., edges) between host computers (i.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 messageto its three other neighbors using the point-to-point connections.
`In
`this way, the message is propagated to each computerusing 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 nodesis referred to as a 4-regular graph. The
`use of a 4-regular graph means that a computer would become disconnected from the
`broadcast channelonly if all four of the connections toits neighbors fail. The graph used by
`the broadcast technique also has the property that it would take a failure of four computers to
`
`(03004-8004/SL003733.100]
`
`-6-
`
`7/31/00
`
`20
`
`25
`
`30
`
`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 whichrepresents
`the broadcast channel. Eachof the nine nodes A-I represents a computerthat is connectedto
`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.¢., the shortest path between the two nodes of the graph). For example, the
`distance between computers A and F is one because computer A 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 computerF is directly connected to computer B.
`Thus, a message originating at computer A wouldbesent directly to computer F, and then
`sent from computer F to computer B. The maximum ofthe 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
`two connections to reach every other computer. Figure 2 illustrates a graph representing 20
`computers connected to a broadcast channel. The diameterof 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
`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 channel (i.e., decomposingthe graph) composingthe graph.
`
`Composing the Graph
`
`20
`
`25
`
`To connect to the broadcast channel, the computer seeking the connectionfirst
`locates a computer that is currently fully connected to the broadcast channel and then
`
`30
`
`(03004-8004/SL003733.100]
`
`-7-
`
`7/3100
`
`0619
`
`0619
`
`

`

`establishes a connection with four of the computers that are already connected to the
`broadcast channel. (This assumes thatthere 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 assumesthat the broadcast channelis 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
`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 channelby contacting the portal computers untilit
`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 computerto the
`broadcast channel. A computer that hasstarted the process of locating a portal computer, but
`does not yet have a neighbor,
`is in the “seeking connection state.” A computer that is
`connectedto 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 connectedstate.”
`is a 4-regular graph, each of the identified
`Since the broadcast channel
`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 computersthat 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 andDare the two pairs that are
`_
`identified as the neighbors for the new computer Z. The connections between each ofthese
`pairs is broken, and a connection between computer Z and each of computers B, C, D, and E
`{03004-8004/SL003733.100}
`-8-
`7/31/00
`
`25
`
`15
`
`20
`
`0620 ©
`
`0620
`
`

`

`is established as indicated by Figure 3B. The process of breaking the connection between
`two neighbors and reconnecting eachofthe former neighbors to another computeris 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
`
`Four of the ports are
`communications ports for communicating with other computers.
`referred to as “internal” 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. Thefifth 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.
`
`the computer
`technique establishes
`the broadcast
`embodiment,
`In one
`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 amongall 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 asits call-in port. This call-in port is used
`to establish connections with the external port and the internal ports. Each computerthatis
`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 whenit is
`connected to or attempting to connect to the broadcast channel andits call-in port is dialed.
`(In this description, a telephone metaphoris 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-
`7131/00
`
`20
`
`25
`
`30
`
`0621
`
`0621
`
`

`

`seeking computer actually communicates through that transfer-to port, which is the external
`port. Thecall is transferred so that other computers can place calls to that computervia the
`call-in port. The seeking computer then communicates via that external port to request the
`portal computerto assist in connecting the seeking computer to the broadcast channel. The
`seeking computer could identify the call-in port numberof 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 mayresult in improved
`performance
`
`A seeking computer could connect to the broadcast channel by connecting to
`computers either directly connected to the found portal computerordirectly 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 | with
`an added computer. Computer J was connected to the broadcast channel by edge pinning
`edges C-D 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 channelis three, because the shortest path from
`computer G to computer K is through edges G-A, A-E, and E-K. Figure 4C alsoillustrates
`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 minimizethe diameter, the broadcast technique
`uses a random selection techniqueto 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.
`
`20
`
`25
`
`30
`
`{03004-8004/SL003733.100}
`
`-10-
`
`7731/00
`
`0622
`
`0622
`
`

`

`Broadcasting Through 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 computerthat originates a message to be broadcast
`sends that message to each ofits four neighbors using the internal connections. When a
`computer receives a broadcast message from a neighbor, it sends the messageto 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
`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 whichit 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 bereceived 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 haveto travel a distance of four to reach the receiving computer.
`The second messageonly hasto travel a distance of one. Thus,it is possible for the second
`messageto reach the receiving computerbeforethefirst message.
`Whenthe broadcast channelis in a steadystate (i.¢., no computers connecting
`or disconnecting from the broadcast channel), out-of-order messages are not a problem
`because each computerwill eventually receive both messages and can queue messagesuntil
`all earlier ordered messagesare received.
`If, however, the broadcast channel
`is not in a
`[03004-8004/SL003733.100)
`-ll-
`7/31/00
`
`20
`
`25
`
`30
`
`0623
`
`0623
`
`

`

`to the
`In particular, a computer may connect
`then problems can occur.
`steady state,
`broadcast channelafter 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 messagesin order, it would wait indefinitely for the second message.
`Onesolution to this problem is to have each computer queueall 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 channel. Another solution that may have less impact on the propagation speed is
`to queue messages only at computers whoare 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 computerto
`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 computerwill send only higher numbered
`messages from the originating computers to the newly connected computer. Onceall 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 messageas it is received.
`In another embodiment, each computer may
`queue messages and only forwards to the newly connected computer those messages as the
`gapsare filled in. For example, a computer might receive messages 4 and 5 andthen 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 weresent 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 computerwill be able to process message 3.
`It is possible that a newly connected computer will receive a set of messages from an
`onginating computer through one neighbor and thenreceive anotherset of message from the
`[03004-8004/SL003733.100]
`-12-
`7731/00
`
`10
`
`15
`
`20
`
`25
`
`30
`
`0624
`
`0624
`
`

`

`sameoriginating computer through another neighbor. If the 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 thoselater 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 messageto eachofits four neighbors. The disconnect messageincludesa list that
`identifies the four neighbors of the disconnecting computer. When a neighborreceives 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 computerin the
`list, and the third computer in thelist will try to connect to the fourth computerin thelist. 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 messagethat 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-
`SD 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 computerH decides to disconnect, it sendsits list of neighbors to each ofits neighbors
`(computers A, E, F and I) and then disconnects from each ofits neighbors. When
`computers A and I receive the message they establish a connection between them as
`indicated by the dashedline, and similarly for computers E andF.
`When a computer disconnects in an unplanned manner, such as resulting from
`a power failure,
`the neighbors connected to the disconnected computer recognize the
`disconnection when each attempts to send its next message to the now disconnected
`computer. Each former neighborof the disconnected computer recognizesthatit 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 requestidentifies the call-in port of the requesting computer. When a connected
`
`{03004-8004/SL003733.100]
`
`-13-
`
`7731/00
`
`20
`
`25
`
`30
`
`0625
`
`0625
`
`

`

`computer that is also short a connection receives the connection request, it communicates
`with the requesting computer through its external port to establish a connection b