`
`seeking computer.
`
`If that other seeking computer has searched to a depth. of, for example,
`
`only four, it can skip searching through depths five through eight and
`
`at other seeking
`
`5
`
`computers and a different maximum search depth. In such a situation, it ma be possible that
`
`computer can advance its searching to a depth of nine.
`In one embodiment, each computer may have a differeiixt set of portal
`two disjoint broadcast channels are formed because a seeking computer carilot locate a fully
`connected port computer at a higher depth. Similarly, if the set of por1Tl computers are
`disjoint, then two separate broadcast channels would be formed.
`
`10
`
`Identifl g Neigl_1bors for a Seeking Computer
`
`As described above,
`
`the neighbors of a newly connectirig computer are
`
`preferably selected randomly from the set of currently connected computers One advantage
`
`of the broadcast channel, however,
`
`is that no computer has global
`
`owledge of the
`
`broadcast channel. Rather, each computer has local knowledge of itself
`
`d its neighbors.
`
`15
`
`This limited local knowledge has the advantage that all the connected co puters are peers
`
`(as far as the broadcasting is concerned) and the failure of any one comp ter (actually any
`
`three computers when in the 4-regular and 4-connect fonn) will not ea
`
`c the broadcast
`
`charmel to fail. This local knowledge makes it difiicult for a portal comp ter to randomly
`
`select four neighbors for a seeking computer.
`
`20
`
`To select the four computers, a portal computer sends an edge connection
`
`request message through one of its internal connections that is randornl
`
`selected. The
`
`receiving computer again sends the edge connection request message
`
`
`
`ough one of its
`
`internal connections that is randomly selected. This sending of the message corresponds to a
`
`random walk through the graph that represents the broadcast channel.
`
`25
`
`receiving computer will decide that the message has traveled far enou
`
`Eventually, a
`
`to represent a
`
`
`
`randomly selected computer. That receiving computer will offer the in ma] connection
`
`upon which it received the edge connection request message to the see ' g computer for
`
`edge pinning. Of course, if either of the computers at the end of the ofiered internal
`
`connection are already neighbors of the seeking computer, then the seeking computer carmot
`
`
`30
`
`connect through that internal connection. The computer that decided that the message has
`
`[D3004-8001/SLO03733. non
`
`- 1 9-
`
`7,3 We
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1100 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1100 of 1442
`
`
`
`traveled far enough will detect this condition of already being a neigh or and send the
`
`message to a randomly selected neighbor.
`
`In one embodiment, the distance that the edge connection request message
`
`travels is established by the portal computer to be approximately twi e the estimated
`
`5
`
`diameter of the broadcast channel. The message includes an indication of
`
`e distance that it
`
`is to travel. Each receiving computer decrements that distance to travel b fore sending the
`
`message on. The computer that receives a message with a distance to tra el that is zero is
`
`considered to be the randomly selected computer. If that randomly selected computer cannot
`
`connect to the seeking computer (e.g., because it is already connected to it),
`
`then that
`
`10
`
`randomly selected computer forwards the edge connection request to one of its neighbors
`
`with a new distance to travel.
`
`In one embodiment, the forwarding compute toggles the new
`
`distance to navel between zero and one to help prevent two computers
`
`om sending the
`
`message back and forth between each other.
`
`Because of the local nature of the information maintained
`
`each computer
`
`15
`
`connected to the broadcast channel,
`
`the computers need not generally
`
`e aware of the
`
`diameter of the broadcast charmel.
`
`In one embodiment, each message sent through the
`
`broadcast channel has a distance traveled field. Each computer that fo
`
`ards a message
`
`increments the distance traveled field. Each computer also maintains an e timated diameter
`
`of the broadcast charmel. When a computer receives a message that has tr veled a distance
`
`20
`
`that indicates that the estimated diameter is too small, it updates its estim ed diameter and
`
`broadcasts an estimated diameter message. When a computer receives an e timated diameter
`
`message that indicates a diameter that is larger than its own estimated diam
`
`Iter, it updates its
`
`own estimated diameter. This estimated diameter is used to establish th distance that an
`
`edge connection request message should travel.
`
`25
`
`External Data Representation
`
`The computers connected to the broadcast charmel may int
`
`ally store their
`
`data in different formats. For example, one computer may use 32-bit inte ers, and another
`
`computer may use 64-bit integers. As another example, one computer
`
`ay use ASCII to
`
`represent text and another computer may use Unicode. To allow comm cations between
`
`30
`
`heterogeneous computers, the messages sent over the broadcast channel
`
`ay use the XDR
`
`(“extemal Data Representation”) format.
`
`[O3004-8001/SL003733. I07)
`
`-20-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1101 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1101 of 1442
`
`
`
`The underlying peer-to-peer communications protocol
`
`send multiple
`
`messages in a single message stream. The traditional technique for retrieving messages from
`a stream has been to repeatedly invoke an operating system routine to retrieve the next
`
`message in the stream. The retrieval of each message may require two calls to the operating
`
`5
`
`system: one to retrieve the size of the next message and the other to retrieve the number of
`
`bytes indicated by the retrieved size. Such calls to the operating system an, however, be
`
`very slow in comparison to the invocations of local routines. To overcome
`
`e inefiiciencies
`
`ofsuch repeated calls, the broadcast technique in one embodiment, uses XIfR to identify the
`
`message boundaries in a stream of messages. The broadcast techniq
`ue may request the
`
`10
`
`operating system to provide the next, for example, 1,024 bytes from c stream. The
`
`broadcast technique can then repeatedly invoke the XDR routines to retri ve the messages
`
`and use the success or failure of each invocation to determine whether ano er block of 1,024
`
`bytes needs to be retrieved from the operating system. The invocation of
`
`R routines do
`
`not involve system calls and are thus more efiicient than repeated system c ls.
`
`15
`
`M-Regglar
`
`
`
`In the embodiment described above, each fully connected c mputer has four
`
`internal connections. The broadcast technique can be used with other 11
`
`bers of internal
`
`connections. For example, each computer could have 6, 8, or any even n
`
`ber of internal
`
`connections. As the number of internal connections increase, the diamete of the broadcast
`
`20
`
`charmel tends to decrease, and thus propagation time for a message tends 0 decrease. The
`
`time that it takes to connect a seeking computer to the broadcast chann 1 may, however,
`
`increase as the number of internal connections increases. When the n
`
`connectors is even,
`
`then the broadcast channel can be maintained
`
`
`
`ber of internal
`
`m-regular and
`
`m-connected (in the steady state).
`
`If the number of internal connections i odd, then when
`
`25
`
`e computers will
`the broadcast channel has an odd number of computers connected, one of
`have less than that odd number of internal connections.
`In such a situati n, the broadcast
`
`network is neither m-regular nor m-connected. When the next comput
`
`connects to the
`
`broadcast charmel, it can again become m-regular and m-connected.
`
`us, with an odd
`
`
`number of internal connections, the broadcast channel toggles between he g and not being
`30 m-regular and m-connected.
`
`[03004-8001/SLOO3733.lO7]
`
`-21-
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1102 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1102 of 1442
`
`
`
`Components
`
`Figure 6 is a block diagram illustrating components of a
`
`omputer that is
`
`connected to a broadcast charmel. The above description generally assum d that there was
`
`only one broadcast channel and that each computer had only one connectio to that broadcast
`
`5
`
`channel. More generally, a network of computers may have multiple br adcast channels,
`
`10
`
`15
`
`each computer may be connected to more than one broadcast channel,
`
`d each computer
`
`
`
`can have multiple connections to the same broadcast channel. The broadc t channel is well
`
`suited for computer processes (e.g., application programs) that execute col boratively, such
`
`as network meeting programs. Each computer process can connect to one r more broadcast
`channels. The broadcast charmels can be identified by channel
`type
`e.g., application
`program name) and channel instance that represents separate broadcast hannels for that
`
`charmel type. When a process attempts to connect tova broadcast charmel, t seeks a process
`
`
`
`computer. The
`
`seeking process identifies the broadcast channel by channel type and charm instance.
`
`Computer 600 includes multiple application programs 6 l executing as
`
`separate processes. Each application program interfaces with a broadcaste component 602
`
`for each broadcast channel to which it is connected. The broadcaster co ponent may be
`implement as an object that is instantiated within the process space oi the application
`program. Alternatively, the broadcaster component may execute as a se arate process or
`
`20
`
`thread from the application program.
`
`In one embodiment,
`
`the broad ster component
`
`provides functions (e.g., methods of class) that can be invoked by the app cation programs.
`The primary functions provided may include a connect function that an ap lication program
`invokes passing an indication of the broadcast channel to which the ap lication program
`
`wants to connect.
`
`The application program may provide a callback routine that the
`
`25
`
`broadcaster component invokes to notify the application program that th connection has
`
`been completed,
`
`that
`
`is the process enters the fully connected state. The broadcaster
`
`component may also provide an acquire message function that the applica 'on program can
`invoke to retrieve the next message that is broadcast on the broadcastgcharm 1. Alternatively,
`the application program may provide a callback routine (which may be
`virtual ftmction
`provided by the application program) that the broadcaster component inv kes to notify the
`application program that a broadcast message has been received.
`ach broadcaster
`
`30
`
`component allocates a call-in port using the hashing algorithm. When call are answered at
`
`[O3004-8001/SLO03733.|07]
`
`-22-
`
`-,,,,,¢,o
`
`IPR2016-00726 -ACT|V|S|_0N, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1103 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1103 of 1442
`
`
`
`the call-in port they are transferred to other ports that serve as the exte
`
`l and internal
`
`ports.
`
`_
`
`The computers connecting to the broadcast channel may ' clude a central
`
`processing unit, memory, input devices (e.g., keyboard and pointing devic , output devices
`
`5
`
`(e.g., display devices), and storage devices (e.g., disk drives). The in
`
`cry and storage
`
`devices are computer-readable medium that may contain computer
`
`tructions that
`
`implement
`
`the broadcaster component.
`
`In addition,
`
`the data stmc
`
`s and message
`
`structures may be stored or transmitted via a signal transmitted on a c mputer-readable
`
`media, such as a communications link.
`
`10
`
`Figure 7 is a block diagram illustrating the sub-components
`
`the broadcaster
`
`component in one embodiment. The broadcaster component includes a co
`
`ect component
`
`701, an external dispatcher 702, an internal dispatcher 703 for each intern
`
`connection, an
`
`acquire message component 704 and a broadcast component 712. The ap lication program
`
`may provide a connect callback component 710 and a receive response co ponent 711 that
`
`15
`
`are invoked by the broadcaster component. The application program inv kes the connect
`
`component to establish a connection to a designated broadcast chann .
`
`The connect
`
`component identifies the external port and installs the external dispatc‘ er for handling
`
`messages that are received on the external port. The connect component ' vokes the seek
`
`nnected to the
`
`portal computer component 705 to identify a portal computer that
`
`is
`
`20
`
`broadcast channel and invokes the connect request component 706 to ask th portal computer
`
`(if fully connected) to select neighbor processes for the newly connec' g process. The
`
`external dispatcher receives external messages, identifies the type of mess ge,'and invokes
`
`the appropriate handling routine 707. The internal dispatcher receives the '
`
`temal messages,
`
`identifies the type of message, and invokes the appropriate handling r
`
`tine 708. The
`
`25
`
`received broadcast messages are stored in the broadcast message queue 7 9. The acquire
`
`message component
`
`is invoked to retrieve messages from the broadc st queue.
`
`The
`
`broadcast component is invoked by the‘ application program to broadcast messages in the
`broadcast channel.
`
`A Distributed Game Enviromnent
`
`30
`
`is implemented using broadcast
`In one embodiment, a game environment
`charmels. The game environment is provided by a game application pro
`executing on
`
`[D3004-8001/SLOO3733.lO7]
`
`-23-
`
`7mm
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1104 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1104 of 1442
`
`
`
`each player’s computer that interacts with a broadcaster component. Ea h player joins a
`
`game (e.g., a first person shooter game) by connecting to the broadcast c
`
`el on which the
`
`game is played. Each time a player takes an action in the game a message representing that
`
`action is broadcast on the game’s broadcast charmel.
`
`In addition, a
`
`layer may send
`
`5 messages (e.g., strategy information) to one or more other players bi broadcasting a
`message. When the game application program receives an indication oflan action, either
`
`received on the broadcast channel or generated by the player at this comp er, it updates its
`
`current state of the game. The game may terminate when one of the players reaches a certain
`
`score, defeats all other players, all players leave the game, and so on.
`
`10
`
`To facilitate the creation of games for the game environme t, an application
`
`programming interface (“API”) is provided to assist game developers. The
`
`I may provide
`
`high-level game functions that would be used by most types of first perso shooter games.
`
`For example, the API may include functions for indicating that a player ha moved to a new
`
`position, for shooting in a certain direction, for reporting a score, for anno
`
`cing the arrival
`
`15
`
`and departure of players, for sending a message to another player, and so on
`
`The game environment may provide a game web site throu which players
`
`can view the state of current games and register new games. The game
`
`eb server would
`
`include a mapping between each game and the broadcast channel on which
`
`e game is to be
`
`played. When joining a game, the user would download the broadcaster c mponent and the
`
`20
`
`game application program from the web server.
`
`The user would al 0 download the
`
`description of the game, which may include the graphics for the game. The web server
`
`would also provide the channel type and channel instance associated with
`
`e game and the
`
`identification of the portal computers for the game. The game environment may also have a
`
`game monitor computer that connects to each game, monitors the activity of the game, and
`
`b 25
`
`reports the activity to the web server. With this activity information, th web server can
`
`provide information on the current state (e.g., number of players) of each g
`
`e.
`
`The game environment may also be used for games other
`
`an first person
`
`shooter games. For example, a variation of a society simulation game can be played where
`
`players sign up for different roles.
`
`If a role is unfulfilled or a player '
`
`that role is not
`
`30
`
`playing, then an automated player can take over the role.
`
`The following tables list messages sent by the broadcaster co ponents.
`
`[03004-8001/SLO03733.l07]
`
`-24-
`
`'
`
`-mmo
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1105 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1105 of 1442
`
`
`
`
`
`
`
`EXTERNAL MESSAGES
`
`
`
`
`
`
`Message Type _
`seeking_connection_call
`Indicates that a seeking process would like to a W Whether fhé
`receiving process is fully connected to the broa ast channel
`
`
`
`
`
`Indicates that the sending process would like th receiving
`connection_request_call
`
`process to initiate a connection of the sending p ocess to the
`
`broadcast charmel
`
`
`
`edge_proposal_cal1
`
`
`
`Indicates that the sending process is proposing =
`edge through
`which the receiving process can connect to the n oadcast
`channel (i.e., edge pinning)
`
`
`
`
`
`
` Indicates that the sending process is proposing a port through
`
`port__connection_call
`
`which the receiving process can connect to the b oadcast
`charmel
`
`connected__stmt
`
`Indicates that the sending process is connected «» the broadcast
`channel
`
`condition_repair_stmt
`
`ect fiom one
`Indicates that the receiving process should disco
`of its neighbors and connect to one of the proceses involved in
`the neighbors with empty port condition
`
`
`
`INTERNAL MESSAGES
`
`
`
`
`
`
`
`
`
`connection_edge_search_call
`
`connection edge search resp
`
`diameter_estimate_stmt
`
`diameter_reset_stmt
`
`
`
`disconnect_stmt
`
`condition_check_stmt
`
`Message me -
`broadcast_stmt
`Indicates a message that is being broadcast
`ough the
`broadcast charmel for the application pro 2
`5
`
`
`
`
`
`
`
`
`Indicates thatthe designated process is 1ool'p'ng foraport
`
`through which it can connect to the broadcast charmel
`
`
`Indicates that the requesting process is loo ' g for an edge
`through which it can connect to the broadc t charmel
`
`
`
`
`
`
`
`
`Indicates whether the edge between this pr «- cess and the
`
`sending neighbor has been accepted by the
`equesfing
`
`
`Pan)’
`
`
`Indicates an estimated diameter of the broa cast charmel
`
`Indicates to reset the estimated diameter to '
`diameter
`
`Indicates that the sending neighbor is disco
`the broadcast channel
`
`ecting from
`
`Indicates that neighbors with empty port c-
`
`
`
`
`
`[03004-800l/SU)03733.l07|
`
`-2 5-
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1106 of 1442
`
`7/3|lO0
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1106 of 1442
`
`
`
`
`
` _ been de“=°*ed
`
`
`
`condition_double_check_snnt
`
`Flow»Diag;arns
`
`
`
`Indicates that the neighbors with empty po s have the
`same set of neighbors
`Indicates that the broadcast charmel is bein
`
`Figures 8-34 are flow diagrams illustrating the processing 0
`
`the broadcaster
`
`
`
`
`
`component in one embodiment. Figure 8 is a flow diagram illustrating the rocessing of the
`
`5
`
`connect routine in one embodiment. This routine is passed a channel type e. g., application
`
`name) and channel instance (e.g., session identifier), that identifies the bro dcast channel to
`
`which this process wants to connect. The routine is also passed auxiliary information that
`
`includes the list of portal computers and a connection callback routine. Whn the connection
`
`is established, the connection callback routine is invoked to notify the app ication program.
`
`
`
`10 When this process invokes this routine, it is in the seeking connection state When a portal
`
`computer is located that is connected and this routine connects to at least 0
`
`Le neighbor, this
`process enters the partially connected state, and when the process eventually]connects to four
`frilly connected
`neighbors, it enters the fully connected state. When in the small regime,
`process may have less than four neighbors.
`In block 801, the routine opcnh the call-in port
`through which the process is to communicate with other processes when esliilishing external
`
`and internal connections. The port is selected as the first available port
`
`ing the hashing
`
`algorithm described above.
`
`In block 802, the routine sets the connect
`
`time. The connect time is used to identify the instance of the process
`(D3PL '6
`«E3. 5In
`o:1 O53
`o8 3 E
`OoBCD9. 8 tn 3'o9:a.OQE 0=r
`
`'9.
`
`‘<
`
`channel type and charmel instance using one call-in port and then disconn cts, and another
`
`process may then connect to that same broadcast charmel using the same
`
`the other process becomes fully connected, another process may try to co
`
`5 3.0 §.9
`
`thinking it is the fully connected old process.
`
`In such a case, the connect
`
`'
`
`passing the channel type and channel instance. The seek portal computer to tine attempts to
`
`'
`
`[o3oo4-soon/smo3m.ro71
`
`-26-
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1107 of 1442
`
`15
`
`20
`
`25
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1107 of 1442
`
`
`
`successful in locating a fully connected process on that portal computer, then the routine
`
`continues at block 805, else the routine returns an unsuccessful indication.
`
`decision block
`
`805, if no portal computer other than the portal computer on which the pro ss is executing
`
`was located, then this is the first process to fully connect to broadcast channel and the
`
`5
`
`routine continues at block 806, else the routine continues at block 808.
`
`block 806, the
`
`routine invokes the achieve connection routine to change the state of this process to fully
`
`connected.
`
`In block 807, the routine installs the external dispatcher for pro essing messages
`
`received through this process’ external port for the passed charmel type and harmel instance.
`When a message is received through that external port, the external dispafcher is invoked.
`
`In block
`
`The routine then returns.
`
`In block 808, the routine installs an external dis atcher.
`
`10
`
`809, the routine invokes the connect request routine to initiate the proce s of identifying
`
`neighbors for the seeking computer. The routine then returns.
`
`'
`
`Figure 9 is a flow diagram illustrating the processing of the seek portal
`
`computer routine in one embodiment. This routine is passed the charmel
`
`e and charmel
`
`15
`
`instance of the broadcast channel to which this process wishes to connect. This routine, for
`
`each search depth (e.g., port number), checks the portal computers at that s arch depth.
`
`If a
`
`portal computer is located at that search depth with a process that is fully connected to the
`
`broadcast channel, then the routine returns an indication of success.
`
`In bl ks 902-911, the
`
`routine loops selecting each search depth until a process is located.
`
`In bloc 902, the routine
`
`20
`
`selects the next search depth using a port number ordering algorithm.
`
`In de ision block 903,
`
`
`
`and determining whether a process of that portal computer is connected to or attempting to
`
`25
`
`connect to) the broadcast charmel with the passed charmel type and ch
`
`el instance.
`
`In
`
`block 904, the routine selects the next portal computer.
`
`In decision blo
`
`905, if all the
`
`portal computers have already been selected, then the routine loops to block 902 to select the
`
`next search depth, else the routine continues at block 906.
`
`In block 906, th routine dials the
`
`selected portal computer through the port represented by the search depth.
`907, if the dialing was successful, then the routine continues at block 908 else the routine
`
`decision block
`
`30
`
`loops to block 904 to select the next portal computer. The dialing will be successful if the
`dialed port is the call-in port of the broadcast channel of the passed channel
`[03004-8001/SLOO3733. 107]
`-27-
`
`
`
`IPR2016-00726 -A§T|V|S|0N, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1108 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1108 of 1442
`
`
`
`
`
`instance of a process executing on that portal computer.
`
`In block 908, the outine invokes a
`
`contact process routine, which contacts the answering process of the portal omputer through
`
`the dialed port and determines whether that process is fully connected to the broadcast
`
`channel.
`
`In block 909, the routine hangs up on the selected portal cornp ter.
`
`In decision
`
`5
`
`block 910, if the answering process is fully connected to the broadcast hannel, then the
`
`routine returns a success indicator, else the routine continues at block 911.
`
`In block 911, the
`
`routine invokes the check for external call routine to determine whether an external call has
`
`been made to this process as a portal computer and processes that call.
`
`loops to block 904 to select the next portal computer.
`
`e routine then
`
`
`
`Figure 10 is a flow diagram illustrating the processing of th contact process
`
`routine in one embodiment. This routine determines whether the proces of the selected
`
`portal computer that answered the call-in to the selected port is fully onnected to the
`
`broadcast charmel.
`
`In block 1001,
`
`the routine
`
`sends an extema message (i.e.,
`
`seeking_connection_call) to the answering process indicating that a seeking process wants to
`
`to
`
`:2
`
`S5
`
`§E‘39$
`
`%eaO§-‘-1"n»% H8%2230wego:'6«>33",0asamas "13:'8‘<:30isSo{£2‘£3“£83%90‘3-3“'3gr)«.3
`£0
`response message is successful]
`if the external
`decision block 1003,
`seeking_connection_resp), then the routine continues at block 1004, else
`
`1'0
`
`el.
`
`In block
`
`' g process.
`
`In
`
`received (i. e. ,
`
`routine returns.
`
`
`
`Wherever the broadcast component requests to receive an external message, it sets a time out
`
`20
`
`period.
`
`If the external message is not received within that time out perio
`
`the broadcaster
`
`component checks its own call-in port to see if another process is calling it.
`In particular, the
`dialed process may be calling the dialing process, which may result in a d adlock situation.
`The broadcaster component may repeat the receive request several times.
`If the expected
`message is not received, then the broadcaster component handles the error
`5 appropriate.
`In
`decision block 1004, if the answering process indicates in its response mes ge that it is fully
`connected to the broadcast channel, then the routine continues at block 100 , else the routine
`
`In block 1005, the routine adds the selected po al computer to a
`continues at block 1006.
`list of connected portal computers and then returns.
`In block 1006, the routine adds the
`
`answering process to a list of fellow seeking processes and then returns.
`
`Figure 11 is a flow diagram illustrating the processing of th connect request
`routine in one embodiment. This routine requests a process of a portal c mputer that was
`identified as being fully connected to the broadcast charmel to initiate the
`
`25
`
`30
`
`[osaouzooi/suoo3733.io7|
`
`-28-
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1109 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1109 of 1442
`
`
`
`process to the broadcast channel.
`
`In decision block 1101, if at least one p ocess of a portal
`
`computer was located that is fully connected to the broadcast channel, then the routine
`
`continues at block 1103, else the routine continues at block 1102. A pro ess of the portal
`
`computer may no longer be in the list if it recently disconnected from the b oadcast channel.
`
`5
`
`In one embodiment, a seeking computer may always search its entire sear h depth and find
`
`multiple portal computers through which it can connect to the broadcast
`
`armel.
`
`In block
`
`
`
`1102, the routine restarts the process of connecting to the broadcast charm I and returns.
`
`In
`
`block 1103, the routine dials the process of one of the found portal com ters through the
`
`call-in port.
`
`In decision block 1104, if the dialing is successful, then the ro tine continues at
`
`to
`
`block 1105, else the routine continues at block 1113. The dialing may be
`
`successful if, for
`
`example,
`
`the dialed process recently disconnected from the broadcast c armel.
`
`In block
`
`1105, the routine sends an external message to the dialed process reques '
`
`a connection to
`
`the broadcast channel (i. e., connection__request_call).
`
`ln block I 106, the ro tine receives the
`
`response message (i.e., connection_request_resp).
`
`In decision block 110 , if the response
`
`15 message is successfully received, then the routine continues at block 110 , else the routine
`
`continues at block 1113.
`In block 1108, the routine sets the expected n
`er of holes (i. e.,
`empty internal connections) for this process based on the received respo c. When in the
`
`large regime, the expected number of holes is zero. When in the small re
`
`
`In block ll09, the routine s ts the estimated
`
`e, the expected
`
`number of holes varies from one to three.
`
`20
`
`diameter of the broadcast channel based on the received response.
`
`In decis on block 1111, if
`
`the dialed process is ready to connect to this process as indicated by the r sponse message,
`
`then the routine continues at block lll2, else the routine continues at bloc
`III‘ Ii _N c? ‘'1Eo B5;GU! 9‘0 tn:2.o.
`:15.’."€- Cr9. 3§0 F.‘o ca0.o. 5"to
`
`U1Q(3
`
`5''‘
`
`1113.
`
`In block
`
`g process as a
`
`neighbor to this process. This adding of the answering process typically occurs when the
`broadcast channel is in the small regime. When in the large regime, the r dom walk search
`
`25
`
`for a neighbor is performed.
`
`In block 1113, the routine hangs up the ex emal connection
`
`
`
`with the answering process computer and then returns.
`
`Figure 12 is a flow diagram of the processing of the check for external call
`
`routine in one embodiment. This routine is invoked to identify whether a fellow seeking
`process is attempting to establish a connection to the broadcast charmel thr ugh this process.
`In block 1201, the routine attempts to answer a call on the call-in port.
`1202, if the answer is successful, then the routine continues at block 120
`
`decision block
`
`30
`
`[0300-1-8001!SL003733.l07]
`
`.29.
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1110 of 1442
`
`
`
`, else the routine
`
`‘YB [/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1110 of 1442
`
`
`
`returns.
`
`In block 1203, the routine receives the external message fi’om the |extemal port.
`
`In
`
`decision block 1204, if the type of the message indicates that a seeking process is calling
`(i.e., seeking_connection_ca1l), then the routine continues at block 1205, else the routine
`returns. In block 1205, the routine sends an external message (i.e., seeking_i:onnection_resp)
`connection.
`In
`to the other seeking process indicating that this process is also is seeking
`
`decision block 1206, if the sending of the external message is successful, then the routine
`
`continues at block 1207, else the routine returns.
`
`In block 1207, the rou ' e adds the other
`
`seeking process to a list of fellow seeking processes and then returns. This list may be used
`
`if this process can find no process that is fully connected to the broadcast channel.
`In which
`case,
`this process may check to see if any fellow seeking process
`wjre successful
`in
`
`connecting to the broadcast channel. For example, a fellow seeking proces
`
`may become the
`
`first process fiilly connected to the broadcast charmel.
`
`Figure 13 is a flow diagram of the processing of the achieve cpnnection routine
`ponnected to the
`in one embodiment. This routine sets the state of this process to fully
`program that the
`
`broadcast channel and invokes a callback routine to notify the application
`
`process is now fully connected to the requested broadcast channel.
`
`In
`
`block 1301, the
`
`block 1302,
`
`the
`
`routine sets the connection state of this process to fully connected.
`In
`routine notifies fellow seeking processes that it is fully connected by seniling a connected
`external message to them (i.e., connected_stmt).
`In block 1303, the IOITILIDC invokes the
`Figure 14 is a flow diagram illustrating the processing Lpf the external
`
`20
`
`connect callback routine to notify the application program and then returns.
`
`dispatcher routine in one embodiment. This routine is invoked when
`
`e external port
`
`receives a message. This routine retrieves the message, identifies the exte al message type,
`
`and invokes the appropriate routine to handle that message. This routine loops processing
`
`25
`
`each message until all the received messages have been handled.
`
`In block 1401, the routine
`
`answers (e.g., picks up) the external port and retrieves an external mess ge.
`
`In decision
`
`block 1402, if a message was retrieved, then the routine continues at blo k I403, else the
`
`routine hangs up on the external port in block 1415 and returns.
`
`In decisi n