`Ti
`| 03004800208
`Ta
`JOINING A BROADCAST CHANNEL
`Express Mail Label No.
`EL404935398US
`
`
`Box Patent Application
`
`ADDRE.SS TO:
`Assistant Commissioner for Patenty
`
`Washington, D.C. 20231
`
`
`
`5. [| Microfiche Computer Program (Appendix)
`6. Nucleotide and/or Amino Acid Sequence Submission
`
`
`(ifapplicable, alf necessary)
`a [| Computer-Readable Copy
`
`
`a
`
`
`b. [| Paper Copy(identical to computer copy)
`
`
`[ Statement verifying identity of above copies
`
`
`
`
`
`ACCOMPANYING APPLICATION PARTS
`
`
`
`
`
`00/T¢/L0
`
`Pleasetypeaplussign (+)insidethisbox
`UTILITY
`PATENT APPLICATION
`TRANSMITTAL
`a
`(Onlyfornonprovisionalapplications under37 CFR § 1.53(b))
`°
`APPLICATION ELEMENTS
`SeeMPEP chapter 600 concemingutility patent application contents.
`
`
`Authorization for Extensions & Fee Transmittal
`4.
`(Submit an original and a duplicate for fee processing)
`2 x Specification
`[Total Pages]
`.
`X (preferred arrangementsetforth 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(iffiled)
`- Detailed Description
`- Claim(s)
`- Abstract of the Disclosure
`
`Drawing(s) (35 usc 113)
`
`[Total Sheets]
`
`
`
`
`13.
`
`4.
`
`Oath or Declaration
`[Total Pages]
`[| Newly executed (original or copy)
`Copy from a prior application (37 CFR 1.63(d))
`(for continuation/divisional with Box 16 completed)
`
`b
`
`‘
`
`[
`
`
`
`
`
`
`
`PTO/SB/05 (4/98) A
`
`nis
`
`07/31/00
`
`Assignment Papers (cover sheet & document(s)
`
`37 CFR 3.73(b) Statement
`.
`;
`(whenthere is an assignee)
`
`Powerof Attorney
`
`English Translation Document(if applicable)
`
`Information Disclosure
`Statement (IDS)/PTO-1 449
`
`Copies of IDS
`aes
`Citations
`
`10.
`
`11,
`
`14.MIOKLIOOO
`
`
`
`
`
`Preliminary Amendment
`
`
`
`
`12.
`Return Receipt Postcard
`
`
`
`[| DELETION OF INVENTOR(S) Small—Entity42 semen filed in pao application,
`
`
`Signed statementattached deleting
`Statement(s)
`ats Stil proper and
`desire
`Inventor(s)
`named
`in
`the
`prior
`see 37 CFR1.63(4)(2) and 1.33(b)
`Certified Copy of Priority Document(s)
`
`(if foreign priority is claimed)
`
`“NOTE FOR ITEMS 1 & 13:
`IN ORDER TO BE ENTITLED TO
`0
`
`PAY SMALL ENTITY FEES, A SMALL ENTITY STATEMENTIS
`
`
`REQUIRED (37 C.F.R. § 1.27), EXCEPT IF ONE FILED IN A
`
`
`PRIOR APPLICATION IS RELIED UPON (37 C.F.R.
`§ 1.28).
`
`
`
`16,
`fa CONTINUING APPLICATION,check appropriate box and supply the requisite information below and ina preliminary amendment
`of prior Application No.:
`[| Continuation [| Divisional [| Continuation-In-Part (CIP)
`
`
`Prior application information: Examiner
`Group / Art Unit
`
`
`
`For CONTINUATIONor DIVISIONALapps only: 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.
`|| Claims the benefit of Provisional Application No.
`
`
`17, CORRESPONDENCE ADDRESS
`Customer Number 25096 / Barcode
`Mit
`
`,
`
`application,
`
`Other:
`
`AMM
`
`25096
`PATENT -TRADEMARK OFFICE
`
`Respectfully submutted,
`TYPED or PRINTED
`SIGNATURE
`
`
`Maurice
`iti
`REGISTRATION NO. 33,273
`)ts
`e @.
`BUN IE -‘EXHIBIT 1002 Part 1 of 5
`
`0001
`
`0001
`
`BUNGIE - EXHIBIT 1002 Part 1 of 5
`
`
`
`EXPRESS MATL NO. EL404935398US
`
`JOINING 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);
`US. 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
`(Attorney Docket No.
`030048005 US); U.S.
`Patent Application
`No.
`,
`entitled
`“DISTRIBUTED AUCTION SYSTEM,”
`filed
`on
`July 31,2000
`(Attorney 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.
`
`5
`
`20
`
`
`
`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/8L003733.099]
`
`-l-
`
`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
`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 manage its 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 number of direct connections that they can support. This
`limits the numberof 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 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 manyparticipants.
`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
`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 any of the clients.
`The multicasting network protocols allow the sending of broadcast messagesto
`multiple recipients of a network. The current implementations of such multicasting network
`[03004-8002/SL003733.099]
`-2-
`7/31/00
`
`5
`
`10
`
`
`
`25
`
`30
`
`0003
`
`0003
`
`
`
`5
`
`10
`
`protocols tend to place an unacceptable overhead on the underlying network. For example,
`UDP multicasting would swampthe Internet whentrying to locate all possible participants.
`IP multicasting has other problems that include needing special-purpose infrastructure(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 number ofparticipants is desired.
`In addition,
`the underlying architecture of the T.120 Internet standard is a tree structure, which relies on
`the root node ofthe tree forreliability 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 numberof the processes
`
`=
`
`that are widely distributed.
`
`=:
`
`
`= 20
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Figure | illustrates a graph that is 4-regular and 4-connected which represents a
`broadcast channel.
`
`Figure 2 illustrates a graph representing 20 computers connected to a broadcast
`
`channel.
`
`Figures 3A and 3Billustrate the process of connecting a new computerZ 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-8002/SL003733.099]
`
`-3-
`
`7/31/00
`
`0004
`
`0004
`
`
`
`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 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
`
`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 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
`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.
`
`5
`
`10
`
`
`
`== 20
`
`=
`
`25
`
`Figure 13 is a flow diagram of the processing of the achieve comnection 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.
`
`30
`
`Figure 16 is a flow diagram illustrating processing of the handle connection
`requestcall 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.
`Figure 19 is a flow diagram illustrating the processing of the handle edge
`proposalcall routine.
`
`5
`
`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 ofthefill hole routine in
`one embodiment.
`
`10
`
`
`
`Figure 22 is a flow diagram illustrating the processing ofthe 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 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
`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.
`Figure 30 is a flow diagram illustrating the processing of the broadcast routine
`in one embodiment.
`
`25
`
`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.
`
`30
`
`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 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
`
`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-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 computerthat 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 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 channel only if all four of the connections to its neighbors fail. The graph used by
`the broadcast technique also hasthe property that it would take a failure of four computersto
`
`[03004-8002/8L003733.099]
`
`~6-
`
`7/31/00
`
`0007
`
`
`
`Ls
`
` =
`
`= 20
`
`25
`
`30
`
`
`
`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
`the broadcast channel. Each of the nine nodes A-I represents a computerthat 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.¢., 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
`
`5
`
`10
`
` by Figure 1 is two. That is, a message sent by any computer would traverse no more than
`
`computer F. The distance between computers A and B is two because there is no direct
`connection between computers A and B, but computerFis directly connected to computerB.
`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 ofthe distances between the computers
`is the “diameter” of broadcast channel. The diameter of the broadcast channel represented
`
`== 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).
`
`25
`
`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.¢., broadcasting through the graph), and (3) the disconnecting of
`computers from the broadcast channel(i.e., decomposing the graph) composing the graph.
`
`Composing the Graph
`
`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-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 assumesthat 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 ina “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 computerlocates 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 ofthese four computers then
`cooperates with the seeking computer to effect the connecting of the seeking computerto the
`broadcast channel. A computerthat 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.”
`
`5
`
`10
`
` 5
`
`25
`
`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 brokenso 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
`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 twopairs that are
`identified as the neighbors for the new computer Z. The connections between eachofthese
`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 “internal” ports because they are the ports through which the messagesofthe
`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-connected 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
`through their external ports. A seeking computer uses external ports when locating a portal
`
` computer.
`
` applications(e.g., port 80 for HTTP messages). The remainder of the ports are user ports
`
`the computer
`technique establishes
`the broadcast
`In one embodiment,
`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
`
`In one embodiment, a set of port numbers can be reserved
`that are available to any process.
`for use by the computer connected to the broadcast channel.
`In an alternative embodiment,
`
`Each computer
`the port numbers used are dynamically identified by 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 computerthat is
`connected to the broadcast channel can receive non-broadcast messages through its external
`port. A seeking computertries “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 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
`
`25
`
`30
`
`[03004-8002/SL003733.099]
`
`-9-
`
`7/31/00
`
`0010
`
`0010
`
`
`
`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 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 numberofa 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 connectionto 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 channelis still two.
`Figure 4B illustrates the broadcast channel of Figure 4A with an added computer.
`
`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 also illustrates
`the broadcast channelof 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 computerin 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.
`
` Computer K was connected to the broadcast channel by edge pinning edges E-J and B-C to
`
`5
`
`10
`
`25
`
`30
`
`i
`
`[03004-8002/SL003733.099]
`
`~10-
`
`7/31/00
`
`0011
`
`0011
`
`
`
`Broadcasting Through the Graph
`
`As described above, each computerthat 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 from each of its four neighbors. Each
`computer, however, only sends thefirst copy of the messagethat 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 becausethere 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. Thefirst message may have to 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
`message to reach the receiving computerbeforethe first message.
`Whenthe broadcast channelis 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 messagesuntil
`all earlier ordered messages are received.
`If, however, the broadcast channel is not in a
`[03004-8002/SL003733.099]
`-l1-
`7/31/00
`
`5
`
`10
`
` Fi
`
`25
`
`30
`
`0012
`
`0012
`
`
`
`5
`
`10
`
`In particular, a computer may connect to the
`then problems can occur.
`steady state,
`broadcast channel after the second messagehas already been received and forwarded on by
`its new neighbors. When a new neighbor eventually receives thefirst message, it sends the
`message to the newly connected computer. Thus, the newly connected computerwill receive
`the first message, but will not receive the second message. If the newly connected computer
`needsto process the messagesin order, it would wait indefinitely for the second message.
`One solution 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 ofthe 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. 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
`
`In another embodiment, each computer may
`simply forward each message asit is received.
`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 thenreceive
`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 weresentto the
`newly connected computer before message 3, then the newly connected computer would
`process messages 4 and 5 and disregard message 3. Becausethe 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 anotherset of message from the
`[03004-8002/SL003733.099]
`-12-
`7/31/00
`
`30
`
`0013
`
`0013
`
`
`
`same originating computer through anotherneighbo