Components
`
`5
`Figure 6 is a block diagram illustrating components of a ozomputer that is
`connected to a broadcast channel. The above description generally assumeid that there was
`only one broadcast channel and that each computer had only one connection io that broadcast
`channel. More generally, a network of computers may have multiple broladcast channels,
`each computer may be connected to more than one broadcast channel, and each computer
`can have multiple connections to the same broadcast channel. The broadcas charmel is well
`
`5
`
`suited for computer processes (e.g., application programs) that execute coll boratively, such
`
`as network meeting programs. Each computer process can connect to one o more broadcast
`
`10
`
`charmels. The broadcast charmels can be identified by charmel
`
`type ( .g., application
`
`program name) and channel instance that represents separate broadcast charmels for that
`channel type. When a process attempts to connect to a broadcast channel, ii seeks a process
`currently connected to that broadcast charmel that is executing on a portal computer. The
`
`15
`
`20
`
`25
`
`30
`
`‘
`
`seeking process identifies the broadcast charmel by charmel type and charme instance.
`Computer 600 includes multiple application programs 6d] executing as
`separate processes. Each application program interfaces with a broadcasteril component 602
`for each broadcast channel to which it is connected. The broadcaster corhponent may be»
`implement as an object that is instantiated within the process space oil the application
`program. Alternatively, the broadcaster component may execute as a seplgarate process or
`thread from the application program.
`In one embodiment,
`the broadcaster component
`provides functions (e.g., methods of class) that can be invoked by the applifcation programs.
`The primary fimctions provided may include a connect fimction that an appilication program
`invokes passing an indication of the broadcast charmel to which the application program
`wants to connect.
`The application program may provide a callback ’routine that
`the
`broadcaster component invokes to notify the application program that the; connection has
`been completed,
`that is the process enters the fully connected state.
`lfhe broadcaster
`‘ component may also provide an" acquire message function that the application program can
`invoke to retrieve the next message that is broadcast on the broadcast channeil. Alternatively,
`the application program may provide a callback routine (which may be ax virtual function
`provided by the application program) that the broadcaster component invokes to notify the
`application program that a broadcast message has been received.
`Elach broadcaster
`
`component allocates a call-in port using the hashing algorithm. When calls are answered at
`
`[03004-8005/S1fi03733.I0l]
`
`-22-
`
`-,,3,,oo
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 549 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 549 of 1442
`
`

`
`the call-in port, they are transferred to other ports that serve as the exter:nal and internal
`
`ports.
`
`The computers connecting to the broadcast channel may include a central
`processing unit, memory, input devices (e.g., keyboard and pointing device), output devices
`(e.g., display devices), and storage devices (e.g., disk drives). The memiory and storage
`devices are computer-readable medium that may contain computer
`iiistructions that
`implement
`the broadcaster component.
`In addition,
`the data structureis and message
`structures may be stored or transmitted via a signal transmitted on a cqimputer-readable
`media, such as a communications link.
`I
`Figure 7 is a block diagram illustrating the sub-components of the broadcaster
`component in one embodiment. The broadcaster component includes a corinect component
`701, an external dispatcher 702, an internal dispatcher 703 for each internall connection, an
`acquire message component 704 and a broadcast component 712. The application program
`may provide a connect callback component 710 and a receive response coniponent 711 that
`are invoked by the broadcaster component. The application program invoikes the connect
`component to establish a connection to a designated broadcast channeli.
`The connect
`component identifies the external port and installs the external dispatchier for handling
`messages that are received on the external port. The connect component iilnvokes the seek
`
`is connected to the
`portal computer component 705 to identify a portal computer that
`broadcast channel and invokes the connect request component 706 to ask theiportal computer
`(if fully connected) to select neighbor processes for the newly connecting process. The
`external dispatcher receives external messages, identifies the type of message, and invokes
`
`the appropriate handling routine 707. The internal dispatcher receives the internal messages,
`
`5
`
`10
`
`15
`
`20
`
`identifies the type of message, and invokes the appropriate handling routine 708. The
`received broadcast messages are stored in the broadcast message queue 709. The acquire
`
`25
`
`The
`is invoked to retrieve messages from the broadcast queue.
`message component
`broadcast component is invoked by the application program to broadcast inessages in the
`broadcast channel.
`
`The following tables list messages sent by the broadcaster components.
`
`[D3004-8005/SUJOS 733. I01]
`
`-23 -
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 550 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 550 of 1442
`
`

`
`EXTERNAL MESSAGES
`
`Message Type
`seeking_connection_call
`
`connection_request_ca11
`
`edge_proposa1_cal1
`
`port_connection_call
`
`connected_stmt
`
`condition__repair_stmt
`
`Description
`Indicates that a seeking process would like to knhw whether the
`receiving process is fully connected to the broaditast channel
`Indicates that the sending process would like thei receiving
`process to initiate a connection of the sending prfocess to the
`broadcast charmel
`.
`
`edge through
`Indicates that the sending process is proposing
`which the receiving process can connect to the broadcast
`charmel (i. e., edge pinning)
`
`Indicates that the sending process is proposing aiport through
`which the receiving process can connect to the broadcast
`channel
`
`Indicates that the sending process is connected to the broadcast
`charmel
`I
`
`Indicates that the receiving process should discoimect from one
`of its neighbors and connect to one of the processes involved in
`the neighbors with empty port condition
`'
`
`INTERNAL MESSAGES
`
`:
`
`~
`
`_
`
`<
`
`
`
`Description
`Indicates a message that is being broadcast lthrough the
`I broadcast charmel for the application programs
`
`
`
`
`
`Message Type
`broadcast_stmt
`
`connectionJJ0l't__SC8ICh_StlIlt
`
`connection_edge_search_call
`
`
`
`connection_edge_search_resp
`
`d1ameter__estimate_stmt
`
`diameter_reset_sunt
`
`disconnect__stmt
`
`
`
`
`
`
`Indicates that the designated process is looliing for a port
`
`through which it can connect to the broadc st channel
`
`Indicates that the requesting process is loo ' g for an edge
`through which it can connect to the broadc st channel
`
`Indicates whether the edge between this pr cess and the
`sending neighbor has been accepted by the - equesting
`party
`i
`
`Indicates an estimated diameter of the broa cast charmel
`
`
`
`Indicates to reset the estimated diameter to
`diameter
`
`5
`
`dicated
`
`Indicates that the sending neighbor is disconnecting from
`the broadcast channel
`-
`
`
`Indicates that neighbors with empty port co dition have
`
`
`
`
`
`
`[03004-8005/SID03733.l0l]
`
`-24-
`
`5
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 551 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 551 of 1442
`
`

`
`
`been detected
`
`Indicates that the neighbors with empty por:ts have the
`condition_double_check_stmt
`same set of neighbors
`=
`Indicates that the broadcast channel is being shutdown
`
`
`
`
`
`
`shutdown_stmt
`
`
`
`5
`
`.
`Flow Diagrams
`Figures 8-34 are flow diagrams illustrating the processing of the broadcaster
`component in one embodiment. Figure 8 is a flow diagram illustrating the processing of the
`connect routine in one embodiment. This routine is passed a charmel type :(e.g., application
`name) and channel instance (e.g., session identifier), that identifies the brozidcast channel to
`which this process wants to connect. The routine is also passed auxiliarylinforrnation that
`includes the list of portal computers and a connection callback routine. Whein the connection
`is established, the connection callback routine is invoked to notify the application program.
`
`10 When this process invokes this routine, it is in the seeking connection statelt When a portal
`computer is located that is connected and this routine connects to at least ope neighbor, this
`process enters the partially connected state, and when the process eventually’ connects to four
`neighbors, it enters the fully connected state. When in the small regime, a; fully connected
`process may have less than four neighbors.
`In block 801, the routine openls the call-in port
`through which the process is to communicate with other processes when esta;blishing external
`and internal connections. The port is selected as the first available port uising the hashing‘
`algorithm described above.
`In block 802, the routine sets the connect tinie to the current
`time. The connect time is used to identify the instance of the process 11:18! is connected
`through this external port. One process may connect to a broadcast ch ' el of a certain
`
`15
`
`20
`
`25
`
`channel type and channel instance using one call-in port and then disconn cts, and another
`
`process may then connect to that same broadcast charmel using the same cal.-in port. Before
`the other process becomes fully connected, another process may try to cornllmunicate with it
`thinking it is the fully connected old process.
`In such a case, the connect tirrie can be used to
`identify this situation.
`In block 803, the routine invokes the seek portal domputer routine
`passing the channel type and channel instance. The seek portal computer I'O;lltinC attempts to
`locate a portal computer through which this process can connect to the broadcast channel for
`the passed type and instance.
`In decision block 804, if the seek portal corpputer routine is
`
`7/moo
`
`I i4a,
`
`(03004-8005/SLOO3733.lOl]
`
`-25-
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 552 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 552 of 1442
`
`

`
`successful in locating a fully connected process on that portal computer, lthen 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éhess is executing
`was located,
`then this is the first process to fully connect to broadcast !channel and the
`routine continues at block 806, else the routine continues at block 808.
`Ilh block 806, the
`routine invokes the achieve connection routine to change the state of
`process to fully
`connected.
`In block 807, the routine installs the external dispatcher for processing messages
`received through this process’ external port for the passed charmel type and charmel instance.
`When a message is received through that external port, the external dispatcher is invoked.
`The routine then returns.
`In block 808, the routine installs an external dispiatcher.
`In block
`809, the routine invokes the connect request routine to initiate the process of identifying
`neighbors for the seeking computer. The routine then returns.
`Figure 9 is a flow diagram illustrating the processing of ithe seek portal
`computer routine in one embodiment. This routine is passed the channel tiype and charmel
`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 stiarch 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 bloicks 902-911, the
`routine loops selecting each search depth until a process is located.
`In blocki 902, the routine
`selects the next search depth using a port number ordering algorithm.
`In decjiision block 903,
`if all the search depths have already been selected during this execution ofi the loop, that is
`for the currently selected depth, then the routine returns a failure indication; else the routine
`continues at block 904.
`In blocks 904-911, the routine loops selecting eachi portal computer
`and determining whether a process of that portal computer is connected to {or attempting to
`connect to) the broadcast charmel with the passed charmel type and chaniiel instance.
`In
`block 904, the routine selects the next portal computer.
`In decision block 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, thejroutine dials the
`selected portal computer through the port represented by the search depth.
`decision block
`
`907, if the dialing was successful, then the routine continues at block 908,; else the routine
`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 tiype and channel
`
`[O3004-8005/Sb003733. I 0 l]
`
`-26-
`
`5
`
`7/3 "00
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 553 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 553 of 1442
`
`

`
`5
`
`10
`
`is
`
`20
`
`In block 908, the ioutine invokes a
`instance of a process executing on that portal computer.
`contact process routine, which contacts the answering process of the portal computer through
`
`the dialed port and determines whether that process is fully connected 0 the broadcast
`channel.
`In block 909, the routine hangs up on the selected portal computer.
`In decision
`block 910, if the answering process is frilly connected to the broadcast diharmel, then the
`routine returns a success indicator, else the routine continues at block 911.
`block 911, the
`routine invokes the check for external call routine to determine whether anlextemal call has
`been made to this process as a portal computer and processes that call.
`llhe routine then
`loops to block 904 to select the next portal computer.
`Figure 10 is a flow diagram illustrating the processing of the contact process
`routine in one embodiment. This routine determines whether the procesis of the selected
`portal computer that answered the call-in to the selected port
`is fully connected to the
`broadcast charmel.
`In block 1001,
`the routine sends an external message (i. e.,
`seeking__connection_call) to the answering process indicating that a seekingiprocess wants to
`know whether the answering process is fully connected to the broadcast channel.
`In block
`1002, the routine receives the external response message from the answering process.
`In
`decision block 1003,
`if the extemal
`response message is successfully received (i.e.,
`seeking_connection__resp), then the routine continues at block 1004, else
`routine returns.
`Wherever the broadcast component requests to receive an external message: it sets a time out
`period.
`If the external message is not received within that time out period, 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 deadlock 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 as appropriate.
`
`In
`
`25
`
`decision block 1004, if the answering process indicates in its response message that it is fully
`
`connected to the broadcast channel, then the routine continues at block 1005, else the routine
`
`continues at block 1006.
`In block 1005, the routine adds the selected portal computer to a
`list of connected portal computers and then returns.
`In block 1006, thelroutine adds the
`I
`answering process to a list of fellow seeking processes and then returns.
`1
`Figure 11 is a flow diagram illustrating the processing of the connect request
`routine in one embodiment. This routine requests a process of a portal computer that was
`
`30
`
`identified as being fully connected to the broadcast channel to initiate the connection of this
`
`[03004-8005ISLDO3733.l0l]
`
`-27-
`
`7/moo
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 554 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 554 of 1442
`
`

`
`. i»
`
`In decision block 1101, if at least one process of a portal
`process to the broadcast charmel.
`computer was located that is fully connected to the broadcast channel,i
`continues at block 1103, else the routine continues at block 1102. A proiess of the portal
`computer may no longer be in the list if it recently disconnected from the bioadcast channel.
`In one embodiment, a seeking computer may always search its entire searcih depth and find
`multiple portal computers through which it can connect to the broadcast charmel.
`In block
`1102, the routine restarts the process of connecting to the broadcast channel and returns.
`In -
`
`then the routine
`
`5
`
`to
`
`block 1103, the routine dials the process of one of the found portal compiiters through the
`call-in port.
`In decision block 1104, if the dialing is successful, then the rovlitine continues at
`block 1105, else the routine continues at block 1113. The dialing may be unsuccessful if, for
`example, the dialed process recently disconnected from the broadcast cliarmel.
`In block
`1105, the routine sends an external message to the dialed process requesting a connection to
`the broadcast channel (i.e., connection_request_call).
`In block 1106, the roiitine receives the
`response message (i.e., connection_request_resp).
`In decision block 1107:, if the response
`15 message is successfully received, then the routine continues at block ll08lr else the routine
`continues at block 1113.
`In block 1108, the routine sets the expected number of holes (i.e.,
`empty internal connections) for this process based on the received responise. When in the
`large regime, the expected number of holes is zero. When in the small regiine, the expected
`number of holes varies from one to three.
`In block 1109, the routine sets the estimated
`diameter of the broadcast charmel based on the received response.
`In idecisi;bn 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 1112, else the routine continues at block 1113.
`In block
`
`20
`
`25
`
`30
`
`1112,
`
`the routine invokes the add neighbor routine to add the answe ' g process as a
`
`neighbor to this process. This adding of the answering process typicallzjntccurs when the
`
`broadcast channel is in the small regime. When in the large regime, the r
`
`om walk search
`
`for a neighbor is performed.
`
`In block 1113, the routine hangs up the external connection
`
`with the answering process computer and then returns.
`5
`Figure 12 is a flow diagram of the processing of the check ifor external call
`routine in one embodiment. This routine is invoked to identify whether
`fellow seeking
`process is attempting to establish a connection to the broadcast channel thrqlugh this process.
`In block 1201, the routine attempts to answer a call on the call-in port.
`Iii decision block
`1202, if the answer is successful, then the routine continues at block l203,l else the routine
`[03004-8005/SL003733.10l 1
`-28-
`‘
`7,3,,o°
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 555 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 555 of 1442
`
`

`
`In
`In block 1203, the routine receives the external message from the iexternal port.
`returns.
`decision block 1204, if the type of the message indicates that a seeking iirocess is calling
`(i. e., seeking_connection_call), then the routine continues at block 1205,; else the routine
`returns.
`In block 1205, the routine sends an external message (i.e., seeking_Zconnection_resp)
`to the other seeking process indicating that this process is also is seeking
`connection.
`In
`decision block 1206, if the sending of the external message is successful,ithen the routine
`continues at block 1207, else the routine returns.
`In block 1207, the routirie adds the other
`seeking process to a list of fellow seeking processes and then returns. Thisllist may be used
`if this process can find no process that is fully connected to the broadcast clitannel.
`In which
`case,
`this process may check to see if any fellow seeking process wclire successful
`in
`connecting to the broadcast channel. For example, a fellow seeking process! may become the
`first process fully connected to the broadcast charmel.
`Figure 13 is a flow diagram of the processing of the achieve coimnection routine
`in one embodiment. This routine sets the state of this process to fully izonnected to the
`
`5
`
`10
`
`15
`
`broadcast channel and invokes a callback routine to notify the application program that the
`
`the
`In block 1301,
`process is now fully connected to the requested broadcast channel.
`the
`block 1302,
`routine sets the connection state of this process to fully connected.
`routine notifies fellow seeking processes that it is fully connected by sending a connected
`external message to them (i.e., connected_stmt).
`In block 1303, the rolitine invokes the
`connect callback routine to notify the application program and then returns.
`
`the external
`Figure 14 is a flow diagram illustrating the processing Lof
`dispatcher routine in one embodiment. This routine is invoked ‘when
`e external port
`receives a message. This routine retrieves the message, identifies the exterrial message type,
`and invokes the appropriate routine to handle that message. This routine iloops processing
`each message until all the received messages have been handled.
`In block :l140l, 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 blocik 1403, else the
`routine hangs up on the external port in block 1415 and returns.
`In decision block 1403, if
`the message type is for a process seeking a connection (i. e., seeking_connection_call), then
`the routine invokes the handle seeking connection call routine in block 1404, else the routine
`
`In decision block 1405, if the message type is for a connection
`continues at block 1405.
`request call (i.e., connection_request_cal1), then the routine invokes the handle connection
`
`(03004-8005/SL003733.l0l]
`
`-29-
`
`’
`
`,
`
`751,00
`
`20
`
`25
`
`30
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 556 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 556 of 1442
`
`

`
`request can routine in block 1406, else the routine continues at block 1407.
`
`In decision
`
`block 1407, if the message type is edge proposal call (i.e., edge_propos: _call), then the
`routine invokes the handle edge proposal call routine in block 1408, else the routine
`
`continues at block 1409.
`
`In decision block 1409, if the message type is i on connect call
`
`(1. e., port_connect_ca1l), then the routine invokes the handle port connection call routine in
` .1, if the message
`block 1410, else the routine continues at block 1411.
`In decision block 141
`type is a connected statement
`(i.e., connected_stmt),
`the routine invhkes the handle
`connected statement in block 1112, else the routine continues at block 1#12.
`In decision
`block 1412, if the message type is a condition repair statement (i. e., condition_repair_stmt),
`
`then the routine invokes the handle condition repair routine in block 1413 else the routine
`————v
`loops to block 1414 to process the next message. After each handling routine is invoked, the
`routine loops to block 1414.
`In block 1414, the routine hangs up on the tfzxtemal port and
`continues at block 1401 to receive the next message.
`Figure 15 is a flow diagram illustrating the processing of the handle seeking
`connection call routine in one embodiment. This routine is invoked when
`seeking process
`is calling to identify a portal computer through which it can connect to the bioadcast channel.
`
`In decision block 1501, if this process is currently fully connected to the liroadcast channel
`identified in the message, then the routine continues at block 1502, else the ioutine continues
`at block 1503. In block 1502, the routine sets a message to indicate that this process is frilly
`connected to the broadcast channel and continues at block 1505.
`In block ‘[1503, the routine
`sets a message to indicate that this process is not fully connected.
`In block il504, the routine
`adds the identification of the seeking process to a list of fellow seeking jirocesses.
`If this
`In
`process is not fully connected, then it is attempting to connect to the broa Ecast charmel.
`block 1505, the routine sends the external message response (i. e., seeking_i:.onnection_resp)
`to the seeking process and then returns.
`Figure 16 is a flow diagram illustrating processing of the himdle connection
`request call routine in one embodiment. This routine is invoked when thi: calling process
`wants this process to initiate the connection of the process to the broadcaist channel. This
`routine either allows the calling process to establish an internal connection
`this process
`(e.g., if in the small regime) or starts the process of identifying a process to iwhich the calling
`process can connect.
`In decision block 1601, if this process is currently figrlly connected to
`the broadcast charmel, then the routine continues at block 1603, else the routine hangs up on
`[o3oo4—soos/stoo3733.1ou‘
`-3 0-
`751,00
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 557 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 557 of 1442
`
`

`
`5
`
`10
`
`15
`
`the external port in block 1602 and returns.
`
`In block 1603, the routine sets the number of
`
`Injblock 1604, the
`holes that the calling process should expect in the response message.
`routine sets the estimated diameter in the response message.
`In block 1l605,
`the routine
`indicates whether this process is ready to connect to the calling process. This process is
`ready to connect when the number of its holes is greater than zero and the calling process is
`not a neighbor of this process.
`In block 1606, the routine sends to the calling process an
`external message
`that
`is
`responsive
`to
`the
`connection
`requlest
`call
`(i. e.,
`connection_request_resp).
`In block 1607, the routine notes the number of holes that the
`calling process needs to fill as indicated in the request message.
`In decision block 1608, if
`this process is ready to connect to the calling process, then the routine continues at block
`1609, else the routine continues at block 1611.
`In block 1609, the routinei invokes the add
`
`the routine
`In block 1610,
`neighbor routine to add the calling process as a neighbor.
`decrements the number of holes that the calling process needs to fill and ccimtinues at block
`1611.
`In block 1611, the routine hangs up on the external port.
`In decisitin block 1612, if
`this process has no holes or the estimated diameter is greater than one (i'.e., in the large
`regime), then the routine continues at block 1613, else the routine continueés at block 1616.
`In blocks 1613-1615, the routine loops forwarding a request for an edge through which to
`connect to the calling process to the broadcast charmel. One request is forwarded for each
`
`pair of holes of the calling process that needs to be filled.
`
`In decision b ock 1613, if the
`
`20
`
`number of holes of the calling process to be filled is greater than or equal to two, then the
`
`routine continues at block 1614, else the routine continues at block 1616.
`I block 1614, the
`routine invokes the forward connection edge search routine. The invoked ioutine is passed
`to an indication of the calling process and the random walk distance.
`In one iembodiment, the
`distance is twice in the estimated diameter of the broadcast channel.
`lngblock 1614, the
`routine decrements the holes left to fill by two and loops to block 1613.
`decision block
`1616, if there is still a hole to fill, then the routine continues at block 1617; else the routine
`returns.
`In block 1617, the routine invokes the fill hole routine passing thei identification of
`the calling process. The fill hole routine broadcasts a connection port search statement (i. e.,
`connection_port_search_stmt) for a hole of a connected process through which the calling
`process can connect to the broadcast charmel. The routine then retums.
`I
`Figure 17 is a flow diagram illustrating the processing of the add neighbor
`routine in one embodiment. This routine adds the process calling on the elxtemal port as a
`|03004-8005/SL003733. lol 1
`-31-
`1
`7/31/00
`
`25
`
`30
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 558 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 558 of 1442
`
`

`
`In block 1701, the routine identifies the calling process on the
`neighbor to this process.
`external port.
`In block 1702, the routine sets a flag to indicate that the neighbor has not yet
`received the broadcast messages from this process. This flag is used to ensure that there are
`no gaps in the messages initially sent to the new neighbor. The external riort becomes the
`internal port for this connection.
`In decision block 1703, if this process
`in the seeking
`connection state,
`then this process is connecting to its first neighbor and the routine
`continues at block 1704, else the routine continues at block 1705.
`In block I704, the routine
`
`In block I705, the routine
`sets the connection state of this process to partially connected.
`In block l_706, the routine
`adds the calling process to the list of neighbors of this process.
`installs an internal dispatcher for the new neighbor. The internal dispatcher is invoked when
`
`a message is received from that new neighbor through the internal port of that new neighbor.
`In decision block 1707, if this process buffered up messages while not full connected, then
`the routine continues at block 1708, else the routine continues at blocll 1709.‘
`In one
`
`embodiment, a process that is partially connected may buffer the messages that it receives
`
`through an internal connection so that it can send these messages as it connects to new
`neighbors.
`In block 1708, the routine sends the buffered messages to the new neighbor
`through the internal port.
`In decision block 1709, if the number of holesi of this process
`equals the expected number of holes, then this process is fully connectedi and the routine
`continues at block 1710, else the routine continues at block 1711.
`In block 1:710, the routine
`invokes the achieve connected routine to indicate that this process is fully connected.
`In
`decision block 1711,
`if the number of holes for this process is zero,
`then the routine
`continues at block 1712, else the routine retums.
`In block 1712, the roiitine deletes any
`pending edges and then returns. A pending edge is an edge that has been iproposed to this
`
`process for edge pirming, which in this case is no longer needed.
`
`'
`
`Figure 18 is
`a flow diagram illustrating the processing bf the forward
`connection edge search routine in one embodiment. This routine is responiiible for passing
`along a request to connect a requesting process to a randomly selected iieighbor of this
`process through the internal port ‘of the selected neighbor, that is part of the riandom walk.
`In
`decision block 1801, if the forwarding distance remaining is greater
`zero, then the
`routine continues at block 1804, else the routine continues at block 1802.
`decision block
`1802, if the number of neighbors of this process is greater than one,
`tihen the routine
`continues at block 1804, else this broadcast charmel is in the small regime] and the routine
`[o3oo4.soo5/sr.oo3733. 101]
`-32-
`7,3 mm
`
`5
`
`to
`
`15
`
`20
`
`25
`
`30
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 559 of 1442
`
`1
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 559 of 1442
`
`

`
`In decision block 1803, if the requesting process Dis a neighbor of
`continues at block 1803.
`this process, then the routine returns, else the routine continues at block 1804.
`In blocks
`1804-1807,
`the routine loops attempting to send a connection edge seaich call
`internal
`message (i.e., connection_edge_search_call) to a randomly selected neighborgi.
`In block 1804,
`the routine randomly selects a neighbor of this process.
`In