. http://www.dcs.warwick.ac.u...
`
`01/29/2002--page 2
`
` f
`
`0
`
`1
`
`2
`
`3
`
`4
`
`5
`
` umC 3Xi5
`6
`7
`8
`9
`10
`
`"WW processing
`
`—— idle
`
`& tranxferingdatanow
`
`And so our problem is how to transfer data such that Producer and Consumer are never idle
`unnecessarily.
`
`First pass at solving the problem
`
`Any solution to this problem must first remove the obstacle of one computer having to wait for
`the other before it can send/receive. We do this by introducing a temporary storage area termed a
`bufler where Producer can send it's data until such time as Consumer is ready to receive it.
`
`send to
`buffer
`———)-~
`
`
` datum stored
`
`. in buffer
`
`
`
`receive from
`buffer
`———-3—
`
`
`
`arrows to tell us
`
`which direction
`
`pointer moves
`
`pointa to tell us
`
`the current state
`
`d the buffer
`
`Now Producer and Consumer can each follow their own algorithm (i.e. sequence of steps) as
`follows, and quite independently of each other.
`
`
`
`Note how we make good use of the buffer's spaces by recycling each one once its contents have
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1079 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1079 of 1442
`
`

`
`3
`
`http://www.dcs.warwick.ae.u...
`
`Ol/29/2002--page 3
`
`been received by Consumer. Well, I guess that might seem like the end of the story.
`Unfortunately the fact that Producer and Consumer can now operate independently of each other
`raises a difficulty often found in distributed systems. If two computers operate independently
`could they accidentally step on each other's toes ?
`
`Second pass at solving the problem
`
`One potential problem with our solution so far is that Producer might try to send a datum when
`the buffer is already full of data still waiting to be received by Consumer. Similarly, Consumer
`might be trying to receive data from an empty buffer, that is, when all the data sent so far by
`Producer has already been received. We have to find a way to prevent Producer sending to a full
`buffer, and of Consumer receiving from an empty buffer. We do this by insisting that Producer
`(resp. Consumer) pause for a moment whenever the buffer is full (resp. empty), which will
`hopefully give time for Consumer (resp. Producer) a chance to make space (resp. make a
`deposit) in the buffer. By adding this extra refinement to the algorithms for Producer and
`Consumer we get the following.
`
`Final pass at solving the problem
`
`But, how do we know when the buffer is full, and when it is empty. This we really do have to
`know in order to prevent the buffer from becoming corrupted. A simple answer would be to keep
`a tally of the number of unread data items currently in the buffer. Starting at zero, the tally is
`incremented by one every time a send is made, and decrcmented by one every time a receive is
`made. Whenever this number is zero the buffer must be empty, and so receiving is not allowed.
`When the number equals the overall number of spaces in the buffer then the latter must be full,
`and so sending is not allowed.
`
`And finally,
`
`This completes the design of our solution, and so it just reamins to code it up in an appropriate
`programming language. If you want to see how that's done come to Warwick and be student in
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1080 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1080 of 1442
`
`

`
`«—o
`
`3
`
`http://www.dcs.warwick.ac.u...
`
`computer science.
`
`O1/29/2002-—pagc 4
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1081 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1081 of 1442
`
`

`
`
`
`27 U.S. Patent Application No.
`
`09/629.042
`
`EXPRE‘.‘5.° “IAIL DD.
`
`Au
`
`04935282US
`
`DISTRIBUTED GAME ENVIRONMENT
`
`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
`
`5
`
`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
`
`L,” filed
`, entitled “BROADCASTING ON A BROADCAST C
`No.
`on July 31, 2000 (Attorney Docket No. 030048004 US); US. Palent Application
`No.
`, entitled “CONTACTING A BROADCAST CHANNEL,” filed on
`
`Pat nt Application
`030048005 US); U.S.
`(Attorney Docket No.
`July 31, 2000
`,
`entifled
`“DISTRIBUTED AUCTION SYSTEM,”
`‘filed
`on
`No.
`(Attorney Docket No.
`030048006 US); U.S.
`Patent Application
`July 31, 2000
`
`No.
`entitled “AN INFORMATION DELIVERY SERVICE,” filed on
`July 31, 2000
`(Attorney Docket No.
`030048007 US); U.S.
`Patlznt Application
`
`No.
`entitled “DISTRIBUTED CONFERENCING SYSITEM,” filed on
`
`10
`
`15
`
`July 31,2000 (Attorney Docket No. 030048008 US); and U.S. gent Application
`
`NT,”
`
`filed on
`
`No.
`
`,
`
`entitled “DISTRIBUTED GAME ENVIRON
`
`20
`
`July 31, 2000 (Attorney Docket No. 030048009 US),
`
`the disclosures of which are
`
`incorporated herein by reference.
`
`TECHNICAL FIELD
`
`The described technology relates generally to a computer network and more
`particularly, to a broadcast channel for a subset of a computers of an underlyling network.
`
`25
`
`BACKGROUND
`
`techniques such
`There are a wide variety of computer network communicatio
`as point-to-point network protocols,
`client/server
`rniddleware, multi asting network
`
`[o3oo4—3eo’r/suoo3'n3.1o7]
`.
`3’0°‘1
`
`-1-
`
`7mm
`
`T
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1082 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1082 of 1442
`
`

`
`protocols, and peer-to-peer middleware. Each of these communications techniques have
`
`their advantages and disadvantages, but none is particularly well suited to
`
`e 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 UND( pipes, TEP/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.
`Fol‘ example, each
`participating process would need to manage its direct connections to all otter participating
`
`processes. Programmers, however, find it very difficult to manage single onnections, 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 informalion. The server
`frmctions 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/sdrver middleware
`systems are not particularly well suited to sharing of information among rriany 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 beirig shared. Such
`polling places a very high overhead on the communications network. Alltematively, each
`client may register a callback with the server, which the server then invokes when new
`infonnation is available to be shared. Such a callback technique presen s a performance
`bottleneck because a single server needs to call back to each clien whenever new
`
`the server) would prevent communications between any of the clients.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`-2-
`
`|03004-8001/SL003733. I07)
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1083 of 1442
`
`'
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1083 of 1442
`
`

`
`protocols tend to place an imacceptable overhead on the underlying netwo . For example,
`
`UDP multicasting would swamp the Internet when trying to locate all pos ible participants.
`
`IP multicasting has other problems that include needing special-purpose '
`
`tructure (e.g.,
`
`routers) to support the sharing of information efliciently.
`
`5
`
`The peer-to-peer middleware communications systems rely n a multicasting
`
`network protocol or a graph of point-to-point network protocols.
`
`S ch peer-to-peer
`
`tniddleware is provided by the T. 120 Internet standard, which is used in uch products as
`
`Data Connection’s D.C.-share and Microsoft’s NetMeeting. These peer-t peer rniddleware
`
`systems rely upon a user to assemble a point-to-point graph of the co
`
`ections used for
`
`10
`
`sharing the information.
`
`Thus,
`
`it
`
`is neither suitable nor desirable to
`
`
`
`se peer-to-peer
`
`middleware systems when more than a small number of participants is des' ed.
`
`In addition,
`
`the underlying architecture of the T. 120 lntemet standard is a tree stmctur , which relies on
`
`the root node of the tree "for reliability of the entire network. That is, each
`
`essage must pass
`
`through the root node in order to be received by all participants.
`
`
`
`15
`
`It would be desirable to have a reliable communications network that
`
`is
`
`suitable for the simultaneous sharing of information among a large numbe of the processes
`
`that are widely distributed.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Figure 1 illustrates a graph that is 4-regular and 4-connected
`broadcast channel.
`
`20
`
`hich represents a
`
`
`
`Figure 2 illustrates a graph representing 20 computers connec d to a broadcast
`
`charmel.
`
`
`
`Figures 3A and 3B illustrate the process of connecting a new omputer Z to the
`
`broadcast channel.
`
`25
`
`Figure 4A illustrates
`
`the broadcast charmel of Figure 1 with an added
`
`computer.
`
`computer.
`
`30
`
`computer.
`
`Figure 4B illustrates the broadcast charmel of Figure 4A with an added
`
`Figure 4C also illustrates the broadcast channel of Figure 4 with an added
`
`[osooa-soon/su)o3733.1o7)
`
`-3-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1084 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1084 of 1442
`
`

`
`Figure 5A illustrates the disconnecting of a computer fr m the broadcast
`
`channel in a planned manner.
`
`Figure 5B illustrates the disconnecting of a computer fr 111
`
`the broadcast
`
`channel in an unplanned manner.
`
`V Figure 5C illustrates the neighbors with empty ports conditio .
`
`Figure 5D illustrates two computers that are not neighbor who now have
`
`empty ports.
`
`regime.
`
`Figure 5E illustrates the neighbors with empty ports condi 'on in the small
`
`
`
`5
`
`15
`
`20
`
`Figure 6 is a block diagram illustrating components of a computer that is
`
`connected to a broadcast charmel.
`
`Figure 7 is a block diagram illustrating the sub-components
`
`f the broadcaster
`
`component in one embodiment.
`
`
`
`Figure 8 is a flow diagram illustrating the processing of the onnect routine in
`one embodiment.
`
`
`
`Figure 9 is a flow diagram illustrating the processing 0
`
`the seek portal
`
`computer routine in one embodiment.
`
`Figure 10 is a flow diagram illustrating the processing of th contact process
`routine in one embodiment.
`
`Figure 11 is a flow diagram illustrating the processing of th ‘coimect 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 c nnection 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
`connection call routine in one embodiment.
`
`30
`
`handle seeking ’
`
`request call routine in one embodiment.
`
`(03004-soon/swo3733.ro7]
`
`-4-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1085 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1085 of 1442
`
`

`
`Figure 17 is a flow diagram illustrating the processing of ihe add neighbor
`
`routine in one embodiment.
`
`Figure 18 is a flow diagram illustrating the processing of the forward
`
`connection edge search routine in one embodiment.
`
`5
`
`Figure 19 is a flow diagram illustrating the processing of the handle edge
`
`proposal call routine.
`
`Figure 20 is a flow diagram illustrating the processing 0 the handle port
`
`connection call routine in one embodiment.
`
`Figure 21 is a flow diagram illustrating the processing of the
`
`11 hole routine in
`
`10
`
`one embodiment.
`
`Figure 22 is a flow diagram illustrating the processing of the ' temal 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
`
`f the distribute
`
`broadcast message routine in one embodiment.
`
`Figure 26 is a flow diagram illustrating the processing of the andle connection
`
`port search statement routine in one embodiment.
`
`Figure 27 is a flow diagram illustrating the processing of
`routine in one embodiment.
`
`e court neighbor
`A
`
`20
`
`Figure 28 is a flow diagram illustrating the processing of the andle connection
`
`edge search call routine in one embodiment.
`
`Figure 29 is a flow diagram illustrating the processing of the andle connection
`
`edge search response routine in one embodiment.
`
`25
`
`Figure 30 is a flow diagram illustrating the processing of the
`in one embodiment.
`
`roadcast routine
`
`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
`check message in one embodiment.
`
`30
`
`andle condition
`
`Figure 33 is a flow diagram illustrating processing of the
`repair statement routine in one embodiment.
`
`andle condition
`
`[osoouooi/si.oo3733.1o71
`
`-5-
`
`751,00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1086 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1086 of 1442
`
`

`
`Figure 34 is a flow diagram illustrating the processing of the handle condition
`
`double check roufine.
`
`DETAILED DESCRIPTION
`
`A broadcast technique in which a broadcast channel overlay a point-to-point
`
`5
`
`communications network is provided. The broadcasting of a message 0 er the broadcast
`
`channel
`
`is eflectively a multicast to those computers of the network
`
`at are currently
`
`connected to the broadcast channel.
`
`In one embodiment, the broadcast tec
`
`
`'que provides a
`
`logical broadcast charmel to which host computers through their executing processes can be
`
`connected.
`
`Each computer that
`
`is connected to the broadcast chann 1 can broadcast
`
`10 messages onto and receive messages off of the broadcast charmel. Each computer that is
`
`connected to the broadcast charmel receives all messages that are broa
`
`ast while it is
`
`connected. The logical broadcast charmel
`
`is implemented using an un erlying network
`
`system (e.g., the lntemet) that allows each computer connected to the un erlying network
`
`system to send messages to‘ each other connected computer using each co puter’s address.
`Thus, the broadcast technique eflectively provides a broadcast channel us’ g an underlying
`
`15
`
`network system that sends messages on a point-to-point basis.
`
`
`
`The broadcast technique overlays the underlying network sys em 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, e ch computer is
`
`20
`
`connected to four other computers, referred to as neighbors.
`
`(Actually, a rocess executing
`
`on a computer is connected to four other processes executing on
`
`
`
`s or four other
`
`computers.) To broadcast a message, the originating computer sends the m ssage to each of
`
`its neighbors using its point-to-point connections. Each computer that rec ives the message
`
`then sends the message to its three other neighbors using the point-to-poin connections.
`
`
`In
`
`25
`
`this way, the message is propagated to each computer using the underlying etwork to effect
`the broadcasting of the message to each computer over a logical broadcast hannel. A graph
`in which each node is connected to four other nodes is referred to as a 4-re
`ar graph. The
`
`[o3oo4-soot/swo3733.|o71
`
`-5-
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1087 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1087 of 1442
`
`

`
`divide the graph into disjoint sub-graphs, that is two separate broadcas charmels. This
`
`property is referred to as being 4-connected. Thus, the graph is both 4-regular and 4-
`
`
`
`connected.
`
`Figure 1 illustrates a graph that is 4-regular and 4-connected which represents
`
`5
`
`the broadcast channel. Each of the nine nodes A-I represents a computer
`
`
`
`the broadcast channel, and each of the edges represents an “edge” connec ‘on between two
`
`computers of the broadcast charmel. The time it takes to broadcast a message to each
`
`computer on the broadcast charmel depends on the speed of the connec ons between the
`
`computers and the number of connections between the originating comput r and each other
`
`10
`
`computer on the broadcast channel. The miniminn number of connectio s that a message
`
`would need to traverse between each pair of computers is the “dis
`
`ee” between the
`
`computers (i.e., the shortest path between the two nodes of the graph).
`
`
`
`or example, the
`
`distance between computers A and F is one because computer A is dire tly connected to
`
`computer F. The distance between computers A and B is two because
`
`ere is no direct
`
`15
`
`connection between computers A and B, but computer F is directly connect d to computer B.
`
`Thus, a message originating at computer A would be sent directly to com uter F, and then
`
`sent from computer F to computer B. The maximum of the distances betw en the computers
`
`20
`
`particular, the shortest path between computers 1 and 3 contains four conn ctions (1-12, 12-
`
`15, 15-18, and 18-3).
`
`The broadcast
`
`technique includes (1) the connecting of omputers to the
`
`25
`
`broadcast channel (i.e., composing the graph), (2) the broadcasting of
`
`essages over the
`
`broadcast channel
`
`(i.e., broadcasting through the graph), and (3) the disconnecting of
`
`computers from the broadcast charmel (i. e., decomposing the graph) compo ing the graph.
`
`Composing the Graph
`
`connection first
`To connect to the broadcast channel, the computer seeking
`locates a computer that is currently fully connected to the broadcast hannel and then
`
`30
`
`[o3oo4—soo1/stno3733.1o7]
`
`.7.
`
`-,,-_.,,oo
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1088 of 1442
`'
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1088 of 1442
`
`

`
`
`establishes a connection with four of the computers that are already onnected to the
`broadcast channel. (This assumes that there are at least four computers alre dy connected to
`
`the broadcast channel. When there are fewer than five computers connect d, the broadcast
`
`channel carmot be a 4-regular graph.
`
`In such a case, the broadcast charme is considered to
`
`5
`
`be in a “small regime.” The broadcast technique for the small regime is d scribed below in
`
`detail. When five or more computers are connected, the broadcast channe is considered to
`
`
`
`be in the “large regime.” This description assumes that the broadcast ch
`
`el is in the large
`
`regime, unless specified otherwise.) Thus,
`
`the process of connecting o the broadcast
`
`charmel includes locating the broadcast channel, identifying the neighbors f r the connecting
`
`10
`
`computer, and then connecting to each identified neighbor. Each compute is aware of one
`
`or more “portal computers” through which that computer may locate the b oadcast channel.
`A seeking computer locates the broadcast channel by contacting the portal omputers until it
`
`
`
`finds one that is currently fully connected to the broadcast channel.
`
`e found portal
`
`computer then directs the identifying of four computers (i.e., to be the s king computer-’s
`
`15
`
`neighbors) to which the seeking computer is to connect. Each of these fo
`
`computers then
`
`cooperates with the seeking computer to effect the connecting of the seekin computer to the
`
`broadcast channel. A computer that has started the process of locating a po al computer, but
`
`does not yet have a neighbor, is in the “seeking connection state.” A
`
`
`
`connected to at least one neighbor, but not yet four neighbors, is in the “p
`
`‘ally connected
`
`20
`
`state.” A computer that is currently, or has been, previously connected to our neighbors is
`
`in the “fully connected state.”
`
`
`
`Since the broadcast channel
`
`is a 4-regular graph, each
`
`f the identified
`
`computers is already connected to four computers.
`Thus, some co
`computers need to be broken so that the seeking computer can connect to f
`
`
`one embodiment, the broadcast technique identifies two pairs of computers
`
`at are currently
`
`ections between
`computers. In
`
`connected to each other. Each of these pairs of computers breaks the co
`
`ection between
`
`them, and then each of the four computers (two from each pair) come 5 to the seeking
`
`computer. Figures 3A and 3B illustrate the process of a new computer 2 onnecting to the
`
`broadcast channel.
`
`
`
`connected. The pairs of computers B and E and computers C and D are the
`0 pairs that are
`
`Figure 3A illustrates the broadcast channel befor
`
`computer Z is
`
`25
`
`30
`
`identified as the neighbors for the new computer Z. The connections betw en each of these
`
`pairs is broken, and a connection between computer Z and each of compute s B, C, D, and E
`
`[O3004-8001/SU)03733.l07]
`
`-8-
`
`1/3 1/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1089 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1089 of 1442
`
`

`
`is established as indicated by Figure 3B. The process of breaking the cofmection between
`two neighbors and reconnecting each of the former neighbors to another co puter is referred
`
`to as “edge pinning” as the edge between two nodes may be considered t 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 “intemal” ports because they are the ports through which th messages of the
`
`broadcast channels are sent. The connections between internal ports
`
`f neighbors are
`
`referred to as “internal” connections. Thus, the internal connections of the roadcast channel
`
`10
`
`form the 4-regular and 4-connected graph. The fifth port is referred to as
`
`“extemal” port
`
`because it is used for sending non-broadcast messages between two comp ters. Neighbors
`
`can send non-broadcast messages either through their internal ports of th ir connection or
`
`through their external ports. A seeking computer uses external ports wh
`
`locating a portal
`
`
`
`computer.
`
`15
`
`In one embodiment,
`
`the broadcast
`
`technique establish s
`
`the computer
`
`space" that is shared among all the processes that may execute on that conTputer. The ports
`are identified by numbers from 0 to 65,535. The first 2056 ports are res rved for specific
`
`20
`
`applications (e.g., port 80 for HTTP messages). The remainder of the p
`
`that are available to any process.
`
`In one embodiment, a set of port numbe
`
`can be reserved
`
`for use by the computer connected to the broadcast charmel.
`
`In an altem ’ve embodiment,
`
`the port numbers used are dynamically identified by each computer.
`
`Each computer
`
`25
`
`dynamically identifies an available port to be used as its call-in port. This c l-in port is used
`
`to establish connections with the external port and the internal ports. Eac computer that is
`
`connected to the broadcast channel can receive non-broadcast messages
`
`ough its external
`
`port. A seeking computer tries “dialing” the port numbers of the portal omputers until a
`
`portal computer “answers,” a call on its call-in port. A portal computer
`
`swers when it is
`
`30
`
`connected to or attempting to connect to the broadcast channel and its call in port is dialed.
`(In this description, a telephone metaphor is used to describe the come tions.) When a
`
`computer receives a call on its call-in port, it transfers the call to anothe port. Thus, the
`
`[03004-8001/Sl.003733.lO7]
`
`-9-
`
`7mm
`
`
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1090 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1090 of 1442
`
`

`
`
`
`seeking computer actually communicates through that transfer-to port, whi h 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 p rt to request the
`
`portal computer to assist in connecting the seeking computer to the broadc st channel. The
`
`s
`
`seeking computer could identify the call-in port number of a portal comput
`
`by successively
`
`dialing each port in port number order. As discussed below in detail, the b adcast technique
`
`uses a hashing algorithm to select the port number order, which may r ult in improved
`
`performance.
`
`
`
`A seeking computer could connect to the broadcast channel y connecting to
`
`10
`
`computers either directly connected to the found portal computer or directly connected to one
`
`of its neighbors. A possible problem with such a scheme for identifying
`
`
`e neighbors for
`
`the seeking computer is that the diameter of the broadcast channel may in rease when each
`
`seeking computer uses the same found portal computer and establishes a onnection to the
`
`broadcast charmel directly through that found portal computer. Concep
`
`
`
`15
`
`becomes elongated in the direction of where the new nodes are added. Figures 4A-4C
`
`illustrate that possible problem. Figure 4A illustrates the broadcast channe of Figure 1 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 ch
`
`el
`
`is still
`
`two.
`
`Figure 4B illustrates
`
`the broadcast channel of Figure 4A with an
`
`dded computer.
`
`20
`
`Computer K was connected to the broadcast charmel by edge pinning edge E-J and B-C to
`
`computer K. The diameter of this broadcast channel is three, because the s oitest path from
`
`computer G to computer K is through edges G-A, A-E, and E-K. Figure C also illustrates
`
`25
`
`this broadcast charmel is, however, still two. Thus, the selection of nei
`
`30
`
`smaller overall diameters.
`
`[03004-800!/SlD03733.l07]
`
`-10-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1091 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1091 of 1442
`
`

`
`Broadcastin 'I'hrou
`
`the Gra h
`
`As described above, each computer that is connected to the roadcast channel
`
`can broadcast messages onto the broadcast channel and does receive all
`
`essages that are
`
`broadcast on the broadcast charmel. The computer that originates a messa e to be broadcast
`
`sends that message to each of its four neighbors using the internal conn ctions. When a
`
`computer receives a broadcast message from a neighbor, it sends the m sage to its three
`
`other neighbors. Each computer on the broadcast channel, except the ori ‘ ating 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 receiv s to its neighbors
`
`and disregards subsequently received copies. Thus, the total number of co ies of a message
`
`that is sent between the computers is 3N+l, where N is the number of co puters connected
`
`to the broadcast channel. Each computer sends three copies of the messa e, 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
`
`
`
`20
`
`25
`
`30
`
`[03004-8001/SU)03733.I0'l]
`
`-1 1-
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1092 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1092 of 1442
`
`

`
`
`
`steady state,
`
`then problems can occur.
`
`In particular, a computer ma
`
`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 mes age, it sends the
`
`message to the newly connected computer. Thus, the newly connected com uter will receive
`
`5
`
`the first message, but will not receive the second message. If the newly co
`
`ected computer
`
`needs to process the messages in order, it would wait indefinitely for the se ond message.
`
`One solution to this problem is to have each computer queue all the messages
`B-3 :: F3(125W
`FL :: E U!(D-.:aa. %B E. S-GV:
`O-2:TD*1 9:2.-‘-3 Ko =.V) ::(U“Ec-O"1
`
`This solution,
`
`'9.
`
`however, may tend to slow down the propagation of messages through the computers of the
`
`10
`
`broadcast channel. Another solution that may have less impact on the pro agation speed is
`
`to queue messages only at computers who are neighbors of the newly co
`
`ected computers.
`
`
`already connected neighbor would only forward messages from each origin ting computer
`
`15
`
`the newly connected computer when it can ensure that no gaps in the m ssages from that
`
`In one embodiment, the already connec d neighbor may
`originating computer will occur.
`track the highest sequence number of the messages already received and f
`arded 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
`
`20
`
`numbered messages have been received from all originating computers,
`
`then the already
`
`connected computer can treat the newly connected computer as its 0th r neighbors and
`
`simply forward each message as it is received.
`
`In another embodiment, ea h computer may
`
`queue messages and only forwards to the newly connected computer thos messages as the
`gaps are filled in. For example, a computer might receive messages 4 and
`and then receive
`
`25 message 3. In such a case, the already connected computer would forward ueue messages 4
`
`30
`
`queues messages 4 and 5, the newly connected computer will be able to p cess message 3.
`
`
`
`103004-soon/su>o3733.|o71
`
`-1 2-
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1093 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1093 of 1442
`
`

`
`
`
`same originating computer through another neighbor. If the second set of
`
`a message that is ordered earlier than the messages of the first set receive
`
`essages contains
`
`then the newly
`
`connected computer may ignore that earlier ordered message if the c mputer already
`
`processed those later ordered messages.
`
`5
`
`Decomposing the Graph
`
`A connected computer disconnects from the broadcast ch
`
`planned or unplanned manner. When a computer disconnects in a planned
`
`el either in a
`
`anner, it sends a
`
`disconnect message to each of its four neighbors. The disconnect message i eludes a list that
`
`identifies the four neighbors of the disconnecting computer. When a nei
`
`10
`
`disconnect message,
`
`it
`
`tries to connect
`
`to one of the computers on
`
`a computer carmot connect (e.g., the first and second computers are already connected), then
`
`the computers may try connecting in various other combinations.
`
`If conn ctions carmot be
`
`is
`
`established, each computer broadcasts a message that it needs to establish a connection with
`another computer. When a computer with an available intemal port receivds the message, it
`can then establish a connection with the computer that broadcast the messdge. Figures 5A-
`5D illustrate the disconnecting of a computer fi'om the broadcast ch
`el.
`Figure 5A
`aaltlarmed manner.
`
`illustrates the disconnecting of a computer from the broadcast channel in
`
`20 When computer H decides to disconnect, it sends its list of neighbors to eac of its neighbors
`
`(computers A, E, F and I) and then disconnects from each of its ne ghbors. When
`
`computers A and I receive the message they establish a connection b tween them as
`
`indicated by the dashed line, and similarly for computers E and F.
`
`25
`
`30
`
`resulting from
`When a computer disconnects in an unplanned manner, such
`a power failure,
`the neighbors connected to the disconnected comput r recognize the
`disconnection when e