`030048002Us
`
`
`
`PTO/SB/05 (4/98) /4
`°
`Vir'1E.Bourassa
`’“*=
`'
`._
`JOINING A BROADCAST CHANNEL
`"¥'é<
`EL404935398US
`ow
`Box Patent Application
`
`Assistant Commissioner for Patenlg
`Washington, DC. 20231
`
`6 07/31/00
`
`
`
`
`
`
`
`
`
`Please type a plus sign (+) inside this box
`Q
`UTILITY
`3
`3
`S “’ PATENT APPLICATION
`
`
`C
`E 5,
`TRANSIVIITTAL
`
`(O
`Z
`' niy for nonprovisional applications under 37 CFR § 1.53(b))
`
`ESS _'
`A
` Authorization for Extensions & Fee Transmittal
`
`5_ El Microfiche Computer Program (Appendix)
`(Submit an original and a duplicate for fee processing)
`
`6. Nucleotide andlor Amino Acid Sequence Submission
`2 - Specification
`[Total Pages]
`'
`X {preferredarrangementsetforth below)
`0)‘applicable, all necessary)
`
`- Descriptive Title of the Invention
`a B Compute,_Readab|e Copy
`- Cross References to Related Applications
`'
`_
`_
`
`- Statement Regarding Fed sponsored R & D
`b. E) Paper COPY (identical to Computer COPY)
`- Reference to Microfiche Appendix
`0'
`:1 Statement verifying identity of above copies
`- Background of the Invention
`
`- Brief Summary of the Invention
`
`- Brief Description of the Drawings (if filed)
`- Detailed Description
`- CIaim(5)
`.
`- Abstract of the Disclosure
`
`X
`
`Drawin 5 35U5C,13
`9
`(
`)
`
`l
`
`Total Sheets
`
`l
`
`39
`
`Oath or Declaration
`
`application,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`3.
`
`4.
`
`
`
`
`
`
`
`[Total Pages] :I 10.
`
`a. El Newly executed (original or copy)
`b D Copy from a prior application (37 CFR 1.63(d))
`'
`(for continuation/divisional with Box 16 completed)
`1 B DELETION OFlNVENTOR(S)
`'
`Signed statement attached deleting
`inventor(s)
`named
`in
`the
`prior
`
`
`see 37 CFR 1.63(d)(2) and 1.33(b)
`
`*NOTE FOR ITEMS 1 & 13.’
`IN ORDER TO BE ENTITLED TO
`PAY SMALL ENTITY FEES, A SMALL ENTITY STATEMENT IS
`REQUIRED (37 C.F.R. § 1.27), EXCEPT IF ONE FILED IN A
`PRIOR APPLICATION IS RELIED UPON 37 C.F.R.
`1.28 .
`
`
`
`16,
`If a CONTINUING APPLICATION, check appropriate box and supply the requisite information below and in a preliminary amendment
`
`|::| Continuation I: Divisional
`l:l Continuation-In-Part (CIP)
`of prior Application No.:
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ACCOMPANYING APPLICATION PARTS
`
`7.
`
`8'
`
`g_
`
`Assignment Papers (cover sheet & document(s))
`
`37 CFR 373(b) Statement
`.-
`.
`(when thereis an assigneei
`
`P
`
`ower O
`
`fAtt
`
`omey
`
`English Translation Document
`
`if a
`
`Iicable
`
`Dmammmmm
`
`11.
`
`12.
`
`12
`
`’
`
`'"f°’”‘a“°" DI5°'°3“’e
`Statement (IDS)/PTO-1449
`Preliminary Amendment
`
`Return Receipt Postcard
`
`°9pI_e5 °f "33
`Citations
`
`Entity
`Small
`5t3Iem9nt(S)
`
`‘” d";‘°’. a§P"°a“°”-
`§fle’“°t'.‘|'l “'°°'
`a”ss' pmperan
`es”
`
`Certified Copy of Priority Document(s)
`(if foreign priority is claimed)
`9 3" CD -5
`
`
`
`
`
`
`_\ .0‘
`
`
`
`
`
`
`Prior application infonnation: Examiner
`
`For CONTINUATION or DIVISIONAL a
`s on] : The entire disclosure of the prior application, from which an oath or declaration is supplied under Box 4b,
`is considered a part of the disclosure of the accompanying continuation or divisional application and is hereby incorporated by reference. The
`incorporation can only be relied upon when a portion has been inadvertently omitted from the submitted application parts.
`
`Cl Claims the benefit of Provisional Application No.
`17. CORRESPONDENCE ADDRESS
`
`Group / Art Unit
`
`Customer Number 25096 / Barcode
`
`llllllllllllllllllllllllll
`
`PATEg_‘fiAE)E|fiRK6OFFlCE
`
`.
`
`Respectfully submitted,
`
`'5"""”'T
`
`
`
`Ex‘ 1 1
`(Part 1)
`
`TYPED or PRINTED
`I
`
`E
`
`r
`
`Maurice
`"
`
`'
`
`‘
`
`5
`
`.
`.
`gkgiei
`)
`{Q34/c Q =
`I
`I
`SIGNATURE
`|PR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`
`REGISTRATION NO. 33 273
`-
`
`Ex. 1102, p.
`
`1 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1 of 1442
`
`
`
`EXPRESS MAIL NO. EL404935398US
`
`JOINING A BROADCAST CHANNEL
`
`CROSS—REFERENCE TO RELATED APPLICATIONS
`
`This application is related to U.S. Patent Application No.
`
`,
`
`entitled “BROADCASTING NETWORK,” filed on July 31, 2000 (Attorney Docket
`
`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
`
`
`entitled “BROADCASTING ON A BROADCAST CHANNEL,” filed
`
`No.
`
`on July 31, 2000 (Attorney Docket No. 030048004 US); U.S. Patent Application
`
`No.
`
`entitled “CONTACTING A BROADCAST CHANNEL,” filed on
`
`July 31, 2000
`No,
`
`Patent Application
`030048005 US); U.S.
`(Attorney Docket No.
`,
`entitled
`“DISTRIBUTED AUCTION SYSTEM,”
`filed
`on
`
`
`
`July 31, 2000
`
`(Attorney Docket No.
`
`030048006 US); U.S.
`
`Patent Application
`
`No.
`
`, entitled “AN INFORMATION DELIVERY SERVICE,” filed on
`
`July 31, 2000
`
`(Attorney Docket No.
`
`030048007 US); U.S.
`
`Patent Application
`
`No.
`
`, entitled “DISTRIBUTED CONFERENCING SYSTEM,” filed on
`
`and U.S. Patent Application
`July 31, 2000 (Attorney Docket No. 030048008 US);
`
`No.
`entitled “DISTRIBUTED GAME ENVIRONMENT,”
`filed on
`
`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 underlying network.
`
`25
`
`BACKGROUND
`
`There are a wide variety of computer network communications techniques such
`as point-to-point network protocols,
`client/server middleware, multicasting network
`
`[03004-8002/SLOO3733.099]
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 2 of 1442
`
`-1-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 2 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 the simultaneous
`
`sharing of information among computers that are widely distributed.
`
`For example,
`
`collaborative processing applications, such as a network meeting programs, have a need to
`
`5
`
`distribute information in a timely manner to all participants who may be geographically
`
`distributed.
`
`The point-to-point network protocols, such as UNIX pipes, TCP/IP, and UDP,
`
`allow processes on different computers to communicate via point-to-point connections. The
`
`interconnection of all participants using point-to-point connections, while theoretically
`
`10
`
`possible, does not scale well as a number of participants grows.
`
`For example, each
`
`
`
`participating process would need to manage its direct connections to all other participating
`
`processes. Programmers, however, find it very difficult to manage single connections, and
`
`management of multiple connections is much more complex.
`
`In addition, participating
`
`processes may be limited to the number of direct connections that they can support. This
`
`limits the 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 information. The server
`
`functions 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/server middleware
`
`systems are not particularly well suited to sharing of information among many participants.
`
`In particular, when a client stores information to be shared at the server, each other client
`
`would need to poll the server to determine that new information is being shared. Such
`
`polling places a very high overhead on the communications network. Alternatively, each
`
`25
`
`client may register a callback with the server, which the server then invokes when new
`
`information is available to be shared. Such a callback technique presents a performance
`
`bottleneck because a single server needs to call back to each client whenever new
`
`information is to be shared.
`
`In addition, the reliability of the entire sharing of information
`
`depends upon the reliability of the single server. Thus, a failure at a single computer (i. e.,
`
`30
`
`the server) would prevent communications between any of the clients.
`
`The multicasting network protocols allow the sending of broadcast messages to
`
`multiple recipients of a network. The current implementations of such multicasting network
`
`[D3004-8002/SI.;O03733.099]
`
`-2-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 3 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 3 of 1442
`
`
`
`protocols tend to place an unacceptable overhead on the underlying network. For example,
`
`UDP multicasting would swamp the Internet when trying to locate all possible participants.
`
`IP multicasting has other problems that include needing special-purpose infrastructure (e. g.,
`
`routers) to support the sharing of information efficiently.
`
`5
`
`The peer-to-peer middleware communications systems rely on a multicasting
`
`network protocol or a graph of point-to-point network protocols.
`
`Such peer-to-peer
`
`middleware is provided by the T.l20 Internet standard, which is used in such products as
`
`Data Connection’s D.C.-share and Microsoft’s NetMeeting. These peer-to-peer middleware
`
`systems rely upon a user to assemble a point-to-point graph of the connections used for
`
`10
`
`sharing the information.
`
`Thus,
`
`it is neither suitable nor desirable to use peer-to-peer
`
`middleware systems when more than a small number of participants is desired.
`
`In addition,
`
`the underlying architecture of the T. 120 Internet standard is a tree structure, which relies on
`
`the root node of the tree for reliability of the entire network. That is, each message must pass
`
` suitable for the simultaneous sharing of information among a large number of the processes
`
`through the root node in order to be received by all participants.
`
`It would be desirable to have a reliable communications network that is
`
`
`
`that are widely distributed.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Figure 1 illustrates a graph that is 4-regular and 4-connected which represents a
`
`broadcast channel.
`
`Figure 2 illustrates a graph representing 20 computers connected to a broadcast
`
`charmel.
`
`Figures 3A and 3B illustrate the process of connecting a new computer Z to the
`
`broadcast charmel.
`
`25
`
`Figure 4A illustrates the broadcast channel of Figurel with an added
`
`computer.
`
`computer.
`
`30
`
`computer.
`
`Figure 4B illustrates the broadcast channel of Figure 4A with an added
`
`Figure 4C also illustrates the broadcast charmel of Figure 4A with an added
`
`[03004-8002/SL003733 .099]
`
`-3 -
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 4 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 4 of 1442
`
`
`
`Figure 5A illustrates the disconnecting of a computer from the broadcast
`
`charmel in a planned manner.
`
`Figure 5B illustrates the disconnecting of a computer from the broadcast
`
`charmel in an unplarmed manner.
`
`Figure SC illustrates the neighbors with empty ports condition.
`
`Figure 5D illustrates two computers that are not neighbors who now have
`
`empty ports.
`
`regime.
`
`Figure 5E illustrates the neighbors with empty ports condition in the small
`
`
`
`25
`
`30
`
`Figure 5F illustrates the situation of Figure 5E when in the large regime.
`
`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 of the broadcaster
`
`component in one embodiment.
`
`Figure 8 is a flow diagram illustrating the processing of the connect routine in
`
`one embodiment.
`
`Figure 9 is a flow diagram illustrating the processing of the seek portal
`
`computer routine in one embodiment.
`
`Figure 10 is a flow diagram illustrating the processing of the contact process
`
`routine in one embodiment.
`
`Figure 11 is a flow diagram illustrating the processing of the connect request
`
`routine in one embodiment.
`
`Figure 12 is a flow diagram of the processing of the check for external call
`
`routine in one embodiment.
`
`Figure 13 is a flow diagram of the processing of the achieve connection routine
`
`in one embodiment.
`
`Figure 14 is a flow diagram illustrating the processing of the external
`
`dispatcher routine in one embodiment.
`
`Figure 15 is a flow diagram illustrating the processing of the handle seeking
`
`connection call routine in one embodiment.
`
`Figure 16 is a flow diagram illustrating processing of the handle connection
`
`request call routine in one embodiment.
`
`[03004-8002/SLO03733.099]
`
`-4-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 5 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 5 of 1442
`
`
`
`Figure 17 is a flow diagram illustrating the processing of the add neighbor
`
`routine in one embodiment.
`
`Figure 18 is a flow diagram illustrating the processing of the forward
`
`connection edge search routine in one embodiment.
`
`Figure 19 is a flow diagram illustrating the processing of the handle edge
`
`proposal call routine.
`
`Figure 20 is a flow diagram illustrating the processing of the handle port
`
`connection call routine in one embodiment.
`
`Figure 21 is a flow diagram illustrating the processing of the fill hole routine in
`
`one embodiment.
`
`Figure 22 is a flow diagram illustrating the processing of the internal dispatcher
`
`routine in one embodiment.
`
`Figure 23 is a flow diagram illustrating the processing of the handle broadcast
`
`message routine in one embodiment.
`
`Figure 24 is a flow diagram illustrating the processing of the distribute
`
`broadcast message routine in one embodiment.
`
`Figure 26 is a flow diagram illustrating the processing of the handle connection
`
`port search statement routine ir1 one embodiment.
`
`Figure 27 is a flow diagram illustrating the processing of the court neighbor
`
`routine in one embodiment.
`
`Figure 28 is a flow diagram illustrating the processing of the handle connection
`
`edge search call routine in one embodiment.
`
`Figure 29 is a flow diagram illustrating the processing of the handle connection
`
`edge search response routine in one embodiment.
`
`Figure 30 is a flow diagram illustrating the processing of the broadcast routine
`
`in one embodiment.
`
`Figure 31 is a flow diagram illustrating the processing of the acquire message
`
`routine in one embodiment.
`
`Figure 32 is a flow diagram illustrating processing of the handle condition
`
`check message in one embodiment.
`
`Figure 33 is a flow diagram illustrating processing of the handle condition
`
`repair statement routine in one embodiment.
`
`[O3004-8002/SL003733.099]
`
`-5-
`
`7/31/00
`
`
`
`25
`
`30
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 6 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 6 of 1442
`
`
`
`Figure 34 is a flow diagram illustrating the processing of the handle condition
`
`double check routine.
`
`DETAILED DESCRIPTION
`
`A broadcast technique in which a broadcast channel overlays a point-to-point
`
`5
`
`communications network is provided. The broadcasting of a message over the broadcast
`
`charmel is effectively a multicast to those computers of the network that are currently
`
`connected to the broadcast charmel.
`
`In one embodiment, the broadcast technique provides a
`
`logical broadcast charmel to which host computers through their executing processes can be
`
`connected.
`
`Each computer that
`
`is connected to the broadcast charmel can broadcast
`
`10 messages onto and receive messages off of the broadcast channel. Each computer that is
`
`connected to the broadcast charmel receives all messages that are broadcast while it is
`
`connected. The logical broadcast charmel is implemented using an underlying network
`
`system (e. g., the Internet) that allows each computer connected to the underlying network
`
`system to send messages to each other connected computer using each computer’s address.
`
` Thus, the broadcast technique effectively provides a broadcast channel using an underlying
`
`
`network system that sends messages on a point-to-point basis.
`The broadcast technique overlays the underlying network system with a graph
`
`of point-to-point connections (i. e., edges) between host computers (i. e., nodes) through
`
`which the broadcast channel
`
`is implemented.
`
`In one embodiment, each computer is
`
`20
`
`connected to four other computers, referred to as neighbors.
`
`(Actually, a process executing
`
`on a computer is connected to four other processes executing on this or four other
`
`computers.) To broadcast a message, the originating computer sends the message to each of
`
`its neighbors using its point-to-point connections. Each computer that receives the message
`
`then sends the message to its three other neighbors using the point-to-point connections.
`
`In
`
`25
`
`this way, the message is propagated to each computer using the underlying network to effect
`
`the broadcasting of the message to each computer over a logical broadcast channel. A graph
`
`in which each node is connected to four other nodes is referred to as a 4-regular graph. The
`
`use of a 4-regular graph means that a computer would become disconnected from the
`
`broadcast channel only if all four of the connections to its neighbors fail. The graph used by
`
`30
`
`the broadcast technique also has the property that it would take a failure of four computers to
`
`[03004-8002/SL003733.099]
`
`-6-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 7 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 7 of 1442
`
`
`
`divide the graph into disjoint sub-graphs, that is two separate broadcast channels. This
`
`property is referred to as being 4-connected. Thus, the graph is both 4-regular and 4-
`
`connected.
`
`Figure 1 illustrates a graph that is 4-regular and 4-connected which represents
`
`5
`
`the broadcast channel. Each of the nine nodes A-I represents a computer that is connected to
`
`the broadcast channel, and each of the edges represents an “edge” connection between two
`
`computers of the broadcast channel. The time it takes to broadcast a message to each
`
`computer on the broadcast charmel depends on the speed of the connections between the
`
`computers and the number of connections between the originating computer and each other
`
`10
`
`computer on the broadcast channel. The minimum number of connections that a message
`
`would need to traverse between each pair of computers is the “distance” between the
`
`computers (i.e., the shortest path between the two nodes of the graph). For example, the
`
`distance between computers A and F is one because computerA is directly connected to
`
`computer F. The distance between computers A and B is two because there is no direct
`
`connection between computers A and B, but computer F is directly connected to computer B.
`
`Thus, a message originating at computer A would be sent directly to computer F, and then
`
`sent from computer F to computer B. The maximum of the distances between the computers
`
`is the “diameter” of broadcast charmel. The diameter of the broadcast channel represented
`
`by Figure 1 is two. That is, a message sent by any computer would traverse no more than
`
`two connections to reach every other computer. Figure 2 illustrates a graph representing 20
`
`computers connected to a broadcast channel. The diameter of this broadcast channel is 4.
`
`In
`
`particular, the shortest path between computers 1 and 3 contains four connections (1-12, 12-
`
`
`
`15, 15-18, and 18-3).
`
`The broadcast technique includes (1) the connecting of computers to the
`
`25
`
`broadcast channel (i. e., composing the graph), (2) the broadcasting of messages over the
`
`broadcast channel
`
`(i. e., broadcasting through the graph), and (3) the disconnecting of
`
`computers from the broadcast charmel (z'.e., decomposing the graph) composing the graph.
`
`Composing the Graph
`
`To connect to the broadcast channel, the computer seeking the connection first
`
`30
`
`locates a computer that is currently fully connected to the broadcast charmel and then
`
`[03004-8002/SLOO3733 .099]
`
`-7-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 8 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 8 of 1442
`
`
`
`establishes a connection with four of the computers that are already connected to the
`
`broadcast charmel.
`
`(This assumes that there are at least four computers already connected to
`
`the broadcast charmel. When there are fewer than five computers connected, the broadcast
`
`channel cannot be a 4-regular graph.
`
`In such a case, the broadcast channel is considered to
`
`be in a “small regime.” The broadcast technique for the small regime is described below ir1
`
`detail. When five or more computers are connected, the broadcast channel is considered to
`
`be in the “large regime.” This description assumes that the broadcast channel is in the large
`
`regime, unless specified otherwise.) Thus,
`
`the process of connecting to the broadcast
`
`charmel includes locating the broadcast channel, identifying the neighbors for the connecting
`
`computer, and then connecting to each identified neighbor. Each computer is aware of one
`
`or more “portal computers” through which that computer may locate the broadcast charmel.
`
`A seeking computer locates the broadcast channel by contacting the portal computers until it
`
`finds one that is currently fully connected to the broadcast channel. The found portal
`
`computer then directs the identifying of four computers (i. e., to be the seeking computer’s
`
`neighbors) to which the seeking computer is to connect. Each of these four computers then
`
`cooperates with the seeking computer to effect the connecting of the seeking computer to the
`
`broadcast channel. A computer that has started the process of locating a portal computer, but
`
`does not yet have a neighbor, is in the “seeking connection state.” A computer that is
`
`connected to at least one neighbor, but not yet four neighbors, is in the “partially connected
`
`state.” A computer that is currently, or has been, previously connected to four neighbors is
`
`in the “fully connected state.”
`
`
`
`Since the broadcast charmel
`
`is a 4-regular graph, each of the identified
`
`computers is already connected to four computers.
`
`Thus, some connections between
`
`25
`
`30
`
`computers need to be broken so that the seeking computer can connect to four computers.
`
`In
`
`one embodiment, the broadcast technique identifies two pairs of computers that are currently
`
`connected to each other. Each of these pairs of computers breaks the connection between
`
`them, and then each of the four computers (two from each pair) connects to the seeking
`
`computer. Figures 3A and 3B illustrate the process of a new computer Z connecting to the
`
`broadcast channel.
`
`Figure 3A illustrates the broadcast channel before computer Z is
`
`connected. The pairs of computers B and E and computers C and D are the two pairs that are
`
`identified as the neighbors for the new computer Z. The connections between each of these
`
`pairs is broken, and a connection between computer Z and each of computers B, C, D, and E
`
`[03004-8002/SLOO3733.099]
`
`-8-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 9 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 9 of 1442
`
`
`
`is established as indicated by Figure 3B. The process of breaking the connection between
`
`two neighbors and reconnecting each of the former neighbors to another computer is referred
`
`to as “edge pinning” as the edge between two nodes may be considered to be stretched and
`
`pinned to a new node.
`
`5
`
`Each
`
`computer
`
`connected to
`
`the
`
`broadcast
`
`charmel
`
`allocates
`
`five
`
`communications ports for communicating with other computers.
`
`Four of the ports are
`
`referred to as “intema ” ports because they are the ports through which the messages of the
`
`broadcast charmels are sent. The connections between internal ports of neighbors are
`
`referred to as “internal” connections. Thus, the internal connections of the broadcast charmel
`
`10
`
`form the 4—regular and 4-connected graph. The fifth port is referred to as an “extemal” port
`
`because it is used for sending non-broadcast messages between two computers. Neighbors
`
`can send non-broadcast messages either through their internal ports of their connection or
`
` computer.
`
`through their external ports. A seeking computer uses external ports when locating a portal
`
`
`
`In one embodiment,
`
`the broadcast
`
`technique establishes
`
`the computer
`
`connections using the TCP/IP communications protocol, which is a point—to-point protocol,
`
`as the underlying network. The TCP/IP protocol provides for reliable and ordered delivery
`
`of messages between computers. The TCP/IP protocol provides each computer with a “port
`
`space” that is shared among all the processes that may execute on that computer. The ports
`
`are identified by numbers from 0 to 65,535. The first 2056 ports are reserved for specific
`
`applications (e. g., port 80 for HTTP messages). The remainder of the ports are user ports
`
`that are available to any process.
`
`In one embodiment, a set of port numbers can be reserved
`
`for use by the computer connected to the broadcast charmel.
`
`In an alternative 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 call-in port is used
`
`to establish connections with the external port and the internal ports. Each computer that is
`
`connected to the broadcast channel can receive non-broadcast messages through its external
`
`port. A seeking computer tries “dialing” the port numbers of the portal computers until a
`
`portal computer “answers,” a call on its call-in port. A portal computer answers when it is
`
`30
`
`connected to or attempting to connect to the broadcast charmel and its call-in port is dialed.
`
`(In this description, a telephone metaphor is used to describe the connections.) When a
`
`computer receives a call on its call-in port, it transfers the call to another port. Thus, the
`
`[03004-8002/SL003733.099]
`
`-9-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 10 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 10 of 1442
`
`
`
`seeking computer actually communicates through that transfer-to port, which 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 port to request the
`
`portal computer to assist in connecting the seeking computer to the broadcast channel. The
`
`5
`
`seeking computer could identify the call-in port number of a portal computer by successively
`
`dialing each port in port number order. As discussed below in detail, the broadcast technique
`
`uses a hashing algorithm to select the port number order, which may result in improved
`
`performance.
`
`A seeking computer could connect to the broadcast channel by 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 the neighbors for
`
`the seeking computer is that the diameter of the broadcast channel may increase when each
`
`seeking computer uses the same found portal computer and establishes a connection to the
`
`broadcast charmel directly through that found portal computer. Conceptually,
`
`the graph
`
`becomes elongated in the direction of where the new nodes are added. Figures 4A—4C
`
`illustrate that possible problem. Figure 4A illustrates the broadcast channel of Figure 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 charmel is still two.
`
`Figure 4B illustrates the broadcast channel of Figure 4A with an added computer.
`
`Computer K was connected to the broadcast charmel by edge pinning edges E-J and B-C to
`computer K. The diameter of this broadcast channel is three, because the shortest path from
`computer G to computer K is through edges G-A, A-E, and E-K. Figure 4C also illustrates
`
`the broadcast charmel of Figure 4A with an added computer. Computer K was connected to
`
`the broadcast channel by edge pinning edges D-G and E-J to computer K. The diameter of
`
`25
`
`this broadcast charmel is, however, still two. Thus, the selection of neighbors impacts the
`
`diameter of the broadcast channel. To help minimize the diameter, the broadcast technique
`
`uses a random selection technique to identify the four neighbors of a computer in the seeking
`
`connection state. The random selection technique tends to distribute the connections to new
`
`seeking computers throughout the computers of the broadcast channel which may result in
`
`30
`
`smaller overall diameters.
`
`[o3oo4-8002/sL0o3733.099]
`
`—lO-
`
`7/31/oo
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 11 of1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 11 of 1442
`
`
`
`Broadcasting Througl_i the Graph
`
`As described above, each computer that is connected to the broadcast charmel
`
`can broadcast messages onto the broadcast channel and does receive all messages that are
`
`broadcast on the broadcast charmel. The computer that originates a message to be broadcast
`
`5
`
`sends that message to each of its four neighbors using the internal connections. When a
`
`computer receives a broadcast message from a neighbor, it sends the message to its three
`
`other neighbors. Each computer on the broadcast chaimel, except the originating computer,
`
`will thus receive a copy of each broadcast message from each of its four neighbors. Each
`
`computer, however, only sends the first copy of the message that it receives to its neighbors
`
`10
`
`and disregards subsequently received copies. Thus, the total number of copies of a message
`
`that is sent between the computers is 3N+1, where N is the number of computers connected
`
`to the broadcast channel. Each computer sends three copies of the message, except for the
`
`
`
`originating computer, which sends four copies of the message.
`
`The redundancy of the message sending helps to ensure the overall reliability
`
`of the broadcast chaimel.
`
`Since each computer has four connections to the broadcast
`
`channel, if one computer fails during the broadcast of a message, its neighbors have three
`
`other connections through which they will receive copies of the broadcast message. Also, if
`
`the internal connection between two computers is slow, each computer has three other
`
`connections through which it may receive a copy of each message sooner.
`
`Each computer
`
`that originates a message numbers
`
`its own messages
`
`sequentially. Because of the dynamic nature of the broadcast channel and because there are
`
`many possible connection paths between computers, the messages may be received out of
`
`order. For example, the distance between an originating computer and a certain receiving
`
`computer may be four. After sending the first message,
`
`the originating computer and
`
`25
`
`receiving computer may become neighbors and thus the distance between them changes to
`
`one. The first message may have to travel a distance of four to reach the receiving computer.
`
`The second message only has to travel a distance of one. Thus, it is possible for the second
`
`message to reach the receiving computer before the first message.
`
`When the broadcast chaimel is in a steady state (i. e., no computers connecting
`
`30
`
`or disconnecting from the broadcast channel), out-of-order messages are not a problem
`
`because each computer will eventually receive both messages and can queue messages until
`
`all earlier ordered messages are received.
`
`If, however, the broadcast chaimel is not in a
`
`[03004-8002/SL003733.099]
`
`-l 1-
`
`7/31/00
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 12 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 12 of 1442
`
`
`
`steady state,
`
`then problems can occur.
`
`In particular, a computer may 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 message, it sends the
`
`message to the newly connected computer. Thus, the newly connected computer will receive
`
`5
`
`the first message, but will not receive the second message. If the newly connected computer
`
`needs to process the messages in order, it would wait indefinitely for the second message.
`
`One solution to this problem is to have each computer queue all the messages
`
`that it receives until it can send them in their proper order to its neighbors. This solution,
`
`however, may tend to slow down the propagation of messages through the computers of the
`
`10
`
`bro