Island recovery in a peer-to-peer relay network

This application claims the interests of US Provisional Patent Application No. 60 / 513,098 ("PEER-TO-PEER RELAY NETWORK") filed on October 20, 2003, with reference to the contents of this disclosure. Use here.

In a typical client-server network, each client in the network establishes a connection with a central server. The client requests services and data from the server. A client sends a request to a server to communicate with another client. In general, clients do not establish direct connections with each other. In a client-server network with N clients, each client has one connection to the server and the server has N connections to each client. For example, in a client-server network with six clients, as shown in Figure 31A, each client has one connection to the server and the server has six connections to each client.

<p> In a typical peer-to-peer network (or "P2P network"), each member (or peer) of a peer-to-peer network establishes a connection with each of the other members. Instead of using a central server, members use this direct peer-to-peer connection (for example, as opposed to a typical client-server network in which members interact through the server) to send data directly to other members. Or request data from other members. Generally, each member in the network has the same role in the network, and the members are generally considered equivalent (as network members). In a peer-to-peer network with N peers, each peer has N-1 connections to other peers. For example, in a peer-to-peer network with 6 peers, each peer has 5 connections to other peers, as shown in Figure 31B.</p><p> In some peer-to-peer networks, servers are also used by members for some centralized services such as address discovery (for example, to establish connections to build peer-to-peer networks).</p>

<p> The present invention provides methods and devices for implementing peer-to-peer relays. In one embodiment, an island recovery method in a peer system within a peer-to-peer relay network involves detecting two or more islands with at least one peer system in the peer-to-peer relay network and peers within the first island. It has a step of joining the two detected islands by connecting the system to a peer system in a second island, and the peer systems in different islands are not connected.</p><p> In one embodiment, the server in the peer-to-peer relay network is a means of detecting the presence of two or more islands having at least one peer system in the peer-to-peer relay network, and the peer system in the first island is the second island. It has a means of joining the two detected islands by connecting to a peer system within, and peer systems within different islands are not connected.</p>

The present invention provides methods and devices for implementing peer-to-peer relays. In one embodiment, multiple computer systems are connected to form a peer-to-peer network. Each computer system is connected to another computer system up to a predetermined number. The computer system sends a message to each of the connected systems in order to communicate.

When one computer system receives a message from another computer system, the receiving computer system sends or relays the message to another computer system according to the relay procedure or rules of its peer-to-peer relay network. The message is propagated to all member computer systems throughout the network according to relay rules.

FIG. 1 shows a representation of one embodiment of the peer-to-peer relay network 100. Peer-to-peer relay networks are sometimes referred to as grids. In Figure 1, 10 peer systems 105 to form a peer-to-peer relay network._{A ... J}Groups (also known as "peers") are connected. Each peer system 105 is a network-compatible game console such as the PlayStation 2 (registered trademark) game console sold by Sony Computer Entertainment Inc., and is equipped with a network adapter. The peer system 105 is either directly connected (such as a wired or wireless connection) or indirectly (eg, via a public IP network such as an intranet or the Internet). In one embodiment, the peer system 105 is connected using a UDP connection or a TCP connection. The peer system 105 exchanges data to support a network environment or activity such as a chat environment or online games.

Each peer 105 also has a connection to a central server 110, such as a UDP connection or TCP connection over the Internet (connection to server 110 is not shown in FIG. 1). The server 110 is a server computer system that provides centralized service to the connected peer system 105. In one embodiment, the server provides an address directory for peer systems and keeps track of which peer systems are connected to each other. Other examples of server services include, but are not limited to, authentication, player matching, and peer system address tracking. In some implementations, the server supports multiple independent peer-to-peer relay networks or associated peer-to-peer relay networks, as described below. In one embodiment, the server accommodates multiple environments or worlds that divide or classify clients into environments to properly filter data. In one embodiment, the server is co-pending and has a common assignee, U.S. Patent Application No. 10 / US Patent Application No. 10 / "Multi-User Application" filed in No. "Configuration Switching: Dynamically Changing Between Network Communication Architectures" and US Patent Application No. 10 /. Programming Interface) includes one or more aspects of the server. These disclosures are incorporated herein by reference. In another embodiment, peers do not use a central server (eg, build a grid by direct communication and relay data).

The maximum connection limit for network 100 is 3. The connection limit is set by the server and defines the maximum number of connections each peer 105 can have in the grid. In another embodiment, one peer (eg, the peer establishing the grid) sets the connection cap, or multiple peers negotiate and determine the connection cap. In FIG. 1, the connection limit is 3, and each peer 105 has 3 connections. Peer systems A to J each have three connections to other peers (peer system 105)._AIs also known as Peer System A or Peer A). Network 100 is a three-connection peer-to-peer relay network, so each peer 105 has three connections to other peers.

Peer 105 communicates by broadcasting a message throughout network 100. Peer 105 propagates the message by relaying the received message to the connected peer 105 according to the relay rules of network 100. In this implementation, relay rules stipulate that peer 105 relays messages to each of peers 105 connected to peer 105. To this exception, (i) peer 105 does not relay the message that peer 105 has already relayed, (ii) peer 105 does not return the message to peer 105 that relay peer 105 received the message from. There are two. Also, in one embodiment, the peer 105 does not relay the message to the peer 105 to which the relay peer 105 has already received the message (the relay peer 105 has multiple peers before the relay peer 105 relays the message). For example, when receiving a message from 105). In another embodiment, another rule or additional rule may be used. Relay rules (and other rules) are either specified by the server or preset by the peer system (or its system software). In another embodiment, the rule can be changed dynamically, for example by propagating a message containing the rule update information throughout the grid.

In one application of Network 100, Peer 105 is playing a network game. While the game is in progress, peer 105 generates update messages that represent actions or events that peer 105 causes. For example, while running game software on a player's computer system (such as Peer A), the computer system represents in-game actions such as moving or firing used by another player's computer system (eg, the player's). (Update position) Generate update data. For the update to be effective, each peer 105 must receive the update from the peer 105 doing the update. The peer 105 relays the update message throughout the network 100 and propagates the message to each peer 105.

In one example, peer A has updates to send to other peers. Peer A has an update message with update data, an identifier indicating that peer A is the source of the update, and a sequence identifier that distinguishes this message from other messages sent by peer A and provides a relative sequence. create. Peer A sends a message to connected peers B, C, and D of peer A. Peer B transmits the message received from peer A to peers D and E. Peer B receives the message from Peer A, so Peer B does not send the message to Peer A. Similarly, peer C sends a message from peer A to peers G and H, and peer D sends a message from peer A to peers B and G. When peer B receives a message from peer D, peer B recognizes the same message (using the message's identifier), so peer B does not relay the message again. Similarly, peer D does not relay messages received from peer B. Assuming that the connections between peers are substantially the same in terms of the time it takes to transfer a message between peers, in the next set of relays, peer E sends the message from peer B to peer F, Relay to I, peer G relays messages from peer C to peers D, F (or depending on which message first arrives at peer C, relays messages from peer D to peers C, F. Then, peer H relays the message from peer C to peers I and J. At this point, all peers have received the update message from peer A. However, since peers F, I, and J have just received the message, these peers relay the message. Peer F relays the message from peer E to peers G, J (or relays the message from peer G to peers E, J depending on which one arrives first), and peer I from peer E. Relays the message to peers H, J (or relays the message from peer H to peers E, J depending on which one arrives first), and peer J relays the message from peer H to peer F, Relay to I. By this point, all peers have sent or relayed the message. The peer does not relay the same message again, so the message is no longer propagated.

In this way, the message propagates throughout the peer-to-peer network 100. This transmission of updates between the peer systems 105 participating in the game supports the game and the game environment. The peer system 105 can distribute data across the network 100 without using the central server 110 for distribution. In addition, each peer 105 is not directly connected to all of the other peers 105, saving resources. As a result, Grid 100 reduces the network bandwidth requirements of each peer (because it only needs to communicate with a limited number of other clients), while retaining data from any one client. It can be quickly propagated to all other peers in the grid (eg using UDP sockets).

In another embodiment, the number of peer systems included in the peer-to-peer relay network may go up or down, and the network connection limits may differ. Depending on the number of peers, the connection limit, and the rules for establishing a connection, not all connections for all peers may be used, so only one peer (or one) has an available connection. (More) may exist.

In another embodiment, the connection upper limit is variable. In one embodiment, the connection limit is unique to each peer system, in which case some or all peers may have different connection limits, but no peers may have different connection limits. Each peer either sets its own connection limit or is assigned a connection limit by the server. In one example, the connection upper limit of each of peers X and Y is 5, the connection upper limit of peer Z is 4, and the connection upper limit of the remaining peers is 3, respectively. In another embodiment, the connection limit is dynamic. In this case, the server adjusts the peer connection limit, for example based on network performance (for example, if the network traffic is low, the connection limit is set low). In another embodiment, one or more of the peer systems each dynamically adjust their connection caps. In another embodiment, the server dynamically adjusts the connection limits for a particular peer system (eg, adjusts some peers instead of all peers).

FIG. 2 shows a block diagram of an embodiment of message 205. Message 205 is generated by the peer system for transmission to other peers in the peer-to-peer relay network. For example, referring to FIG. 1, if peer A has an update message to send to another peer, peer A composes a message such as message 205. Message 205 contains addressing data 210, source identifier 215, sequence value 220, and payload data 230. Addressing data 210 contains network addressing information for sending message 205 from that peer to another peer. In one embodiment, the addressing data 210 includes the IP address of the sending peer and the IP address of the designated receiving peer. The source identifier 215 identifies the peer that created the message 205. This identifier 215 indicates the origin of the message being transmitted over the network to peers throughout the peer-to-peer relay network. The peer receiving the message 205 can use the source identifier 215 to determine from which peer in the network the message 205 originated. The sequence value 220 identifies a particular message 205 and provides relative sequence information. A peer receiving message 205 can use the sequence value 220 to determine if a particular message has already been received, as well as the sequence or sequence of messages sent by the peer indicated by source identifier 215. Can be decided. Data 230 is the payload data of message 205. For update messages (eg, in games), payload data 230 is the update data used by the receiving peer. Alternative implementations may use different types of messages and may use messages in a different format than those shown in Figure 2 (eg, with different or additional information). For example, publish a message to a member of the grid It may contain a file or part of the file you are trying to do, a frame of data such as a frame of game data, a frame, or part of an audio file. The receiving peer can reconstruct the entire file using the sequence values contained in each of the messages. In another example, the message may include additional identifying information, such as an identifier indicating the grid to which the message belongs, for relaying by peers belonging to multiple grids, for example.

FIG. 3 shows a flowchart 300 of an embodiment in which peers relay messages in a peer-to-peer relay network. Initially, this peer is connected to one or more other peer systems in a peer-to-peer relay network.

At block 305, the peer receives a message from the sending peer through the connection between this peer and the sending peer. This message contains the source identifier, sequence value, and payload data (such as update data), as shown in the message in Figure 2.

At block 310, the peer chooses a connection to relay incoming messages. The peer selects a connection from the peer's available connections according to the relay rules of the peer-to-peer relay network. After applying the relay rule, the peer may have selected some or all of the peer's connections, or none of the connections.

At block 315, the peer relays a message to each of the selected connections. The peer composes a message for each selected connection. The peer uses incoming messages, but updates the addressing information for each message it sends accordingly (eg, change the sender to this peer and the receiver to the receiving peer for a connection). Therefore, the payload data is unchanged. In another embodiment, the peer may add data to the message or modify the data in the message. The peer sends the message it composes to the appropriate recipients.

FIG. 4 shows a flowchart 400 of an embodiment in which peers relay messages according to a set of relay rules in a peer-to-peer relay network. The relay rule used in FIG. 4 is an example of a set of relay rules. In another embodiment, different relay rules or additional relay rules may be used. Initially, the relay peer is connected to N's other peer systems in a peer-to-peer relay network. For example, in the network shown in Figure 1, peer D is connected to three other peers (in this case N = 3). The relay rule of FIG. 4 for relaying a message is as follows. 1. Do not relay the message twice 2. Do not return a message to the sender. 3. Do not relay the message to the originating peer 4. After applying rules 1 and 2, relay the message to peers on the available connections

At block 405, the relay peer receives the message. At block 410, the relay peer determines if the relay peer has previously received this message. The relay peer compares the message identification data with the previously received message data stored by the relay peer. In one embodiment, each peer maintains a received message table of source identifiers and sequence values for received messages. The relay peer obtains the source identifier and sequence value from the received message and compares this information with the data stored in the relay peer's received message table. If the relay peer determines that the relay peer has previously received this received message (for example, if the peer finds an entry in the received message table that remembers the source identifier and sequence value of the received message). , Relay peers do not relay incoming messages. In another embodiment, the relay peer determines if the relay peer has previously relayed the received message.

If the relay peer determines that the relay peer has not previously received this received message, at block 412, the relay peer records that this message has been received. In one embodiment, the relay peer adds an entry for the source identifier and sequence value of the received message to the relay peer's received message table. If this source identifier and sequence value entry already exists in the table, the relay peer does not modify the table.

After recording that this message has been received, at block 415, the relay peer sets the counter. The relay peer uses a counter to check the available connections of the relay peer one by one. In one embodiment, the relay peer sets the integer counter i to 1.

At block 420, the relay peer determines whether the relay peer has received a message from the peer connected to the connection indicated by the counter. The received message contains addressing information indicating the source of the received message. The counter indicates the connection, and thus indicates the connected peer and the addressing information of that peer. For example, peer D in Figure 1 has three connections, where peer D assigns a number to each connection, with connection 1 connected to peer A, connection 2 connected to peer B, and connection 3 connected. Peer G is connected. Therefore, when the counter i is 1, the peer D sends the received message by the peer A by comparing the addressing information (source) of the received message with the addressing information of the peer A stored in the peer D. Find out if it was done. If an incoming message is sent to a relay peer by a peer connected to the connection indicated by the counter, the relay peer does not relay the message to that peer.

If the received message was not sent to the relay peer by a peer connected to the connection indicated by the counter, then in block 422, the relay peer is the peer system from which the peer connected to the connection indicated by the counter originated the received message. Decide if. The received message contains information indicating the peer from which the received message originated (remember the peer that first generated the data in the message, source identifier 215 in Figure 2). If the peer connected to the connection indicated by the counter is the source peer system for incoming messages, the relay peer does not relay the message to that peer.

In block 425, if the incoming message was not sent to the relay peer by a peer connected to the connection indicated by the counter, and the peer connected to the connection indicated by the counter is not the source peer system of the incoming message Relays the message to its connecting peer. The relay peer composes a message for the indicated connection. The relay peer makes a copy of the received message and updates the addressing information accordingly (eg, change the source to the relay peer and the recipient to the peer connected to the indicated connection). Therefore, the payload data is unchanged. The relay peer sends the created message to the connected peer over the indicated connection.

At block 430, the relay peer determines if all connections have been confirmed. The relay peer compares the counter to the number of connections established by the relay peer in the peer-to-peer relay network. For example, the relay peer compares the counter i to the value N (the number of connections held by the relay peer). If the relay peer is checking all connections, the relay peer has completed relaying this received message.

If the relay peer has not finished checking all connections, at block 435 the relay peer increments the counter. For example, the relay peer sets the counter i to i + 1. After incrementing the counter, the relay peer returns to block 420 to determine if the relay peer has received an incoming message from the peer connected to the connection indicated by the incremented counter.

As mentioned above, in another embodiment, different rules or additional rules may be used, or fewer relay rules may be used. In one embodiment, the relay peer returns a message to the source (eg, this allows the source to ensure that the relay peer has not changed the data). In another embodiment, the relay peer does not relay the message to a peer that is indicated to be the originator of the message (eg, indicated by the originator identifier of the message). In another embodiment, the relay peer does not relay the same message to the same connected peer again. In another embodiment, the relay peer selects a subset of the available connections to relay the message, for example, the peer with the shortest response time and the peer with the longest response time. In another embodiment, each peer relays the message to all peers' connected peers according to the hop count stored in the message so that the message is relayed only a certain number of times. In another embodiment, the peer relays the same message a limited number of times (two or more times).

FIG. 5 shows a flowchart 500 of an embodiment for establishing a peer-to-peer relay network. In the initial state, peer systems and servers such as peer A and server 110 in FIG. 1 are deployed. At block 505, the peer system opens a connection to the server. A peer system is trying to connect to a server to establish a peer-to-peer relay network (or grid), which can be referred to as an "established peer." The connection to the server can be a direct network connection or an indirect network connection. In one embodiment, the peer is assigned to, or joins and registers with, a subsection of the space maintained by the server or one of a plurality of worlds or environments. The server authenticates the peer before allowing it to continue the conversation. At block 510, the peer system sends a grid creation request to the server. The grid creation request indicates the peer's identity and that the peer is requesting the server to establish a new peer-to-peer relay network. In one embodiment, the request also includes conditions that the peer requires the server to apply (eg, constraints on joining the grid). In another embodiment, this request indicates a set of connection limits and rules (such as relay rules and connection rules) to use in the grid. At block 515, the server registers a new grid. The server maintains a table or list of data that is tracking an established grid. The server creates a new table for the new grid and adds the requesting peer to this table. At block 520, the server sends a confirmation to the peer that the grid has been established. This confirmation includes any identification or access information that the peer needs to access the grid. In one embodiment, this confirmation includes connection limits and grid rules (such as relay rules).

FIG. 6 shows a flowchart 600 of an embodiment in which a peer is connected to a peer-to-peer relay network. In the initial state, a peer-to-peer relay network is established by peer systems and servers such as peer A and server 110 in FIG.

At block 605, the peer system connects to the server. The peer system is trying to connect to a server to join a peer-to-peer relay network (or grid), and this peer system can be referred to as a "new peer" or "participating peer." The connection to the server can be a direct network connection or an indirect network connection. In one embodiment, the peer is assigned to, or joins and registers with, a subsection of the space maintained by the server or one of a plurality of worlds or environments. The server authenticates the peer before allowing it to continue the conversation.

At block 610, the peer selects a grid from the available grids on the server. In one embodiment, the peer requests a list of available grids and selects from that list. In another embodiment, when a peer connects to the server, the server automatically provides a list of available grids. In one embodiment, the server provides a list of available grids to the worlds registered by the peer. The server may also provide additional information to assist in the selection, such as peers that are already members of each grid. The peer sends the grid selection to the server.

At block 615, the server sends the addresses of peers that are already participating in the selected grid. This address indicates how to communicate with the grid members (eg IP address). The address is for establishing a peer connection with the grid members, not a connection through the server. If the selected grid restricts access and new peers are not allowed to join the selected grid, the server does not provide the peer with an address and suggests that the peer choose another grid. .. In one embodiment, the server provides the connection limits and rules for the selected grid, along with the addresses to the new peers.

At block 620, the new peer sends a join message to each member of the grid. The join message indicates the address of the new peer and that peer is joining the grid. In another embodiment, the new peer sends a connection available message indicating the peer's address and the number of connections available to the peer (this is similar to the case where the peer disconnects, as described below). In another embodiment, the new peer sends a join message to one grid member, and that grid member begins relaying the join message through the grid.

At block 625, the grid members receive the join message and each return a join response to the new peer. The join response indicates whether the responding peer has an available connection. An acknowledgment indicates that the responding peer has an available connection. A negative response indicates that the responding peer does not have an available connection. The responding peer records the new piano address obtained from the join message and uses that address to send the join response. The new peer receives a join response.

At block 630, the new peer selects a grid member to connect to. The new peer uses a set of connection rules to select the peer to connect to. For example, in one embodiment, the new peer selects the peers that sent the acknowledgments in the order in which the new peers received the acknowledgments until the grid's connection limit is reached (eg, if the connection limit is 3, the new peer). Selects the peer that corresponds to the first three acknowledgments received). Different implementations may use different sets of connection rules. The new peer remembers the response time of each of the selected peers. In another embodiment, the new peer remembers the response time of all responses (acknowledged and negative).

After selecting the peer to connect to, the new peer opens a connection to the selected peer in block 635. The new peer sends a connection request to each of the selected peers, and the selected peer confirms the request and opens the connection (unless the connection is unavailable on the selected peer). The connection between peers may be direct or indirect (eg, via a network such as the Internet). In one embodiment, when a peer opens a connection, each peer notifies the server of this connection.

In another embodiment, the server facilitates participation in the grid by forcing one or more connections to be established. The server may close the connection to one peer and open the connection to another specified peer. The server can also cause a peer to close one or more of its peer's connections.

FIG. 7 shows a flowchart 700 of an embodiment in which peers are selected to participate in a peer-to-peer relay network, such as in block 630 of FIG. In the initial state, a new peer has selected a grid and is sending a join message to the member peers of that grid. The new peer is receiving the join response returned by the member peer.

At block 705, the new peer selects the peer that corresponds to the first acknowledgment received. This acknowledgment is received before any other acknowledgment and indicates the fastest available connection. At block 710, the new peer selects the peer that corresponds to the last acknowledgment received. This acknowledgment is received after the other acknowledgments and indicates the slowest available connection. To determine the final response, the new peer either waits for all responses to be received, or waits for a defined period of time, with the last response received during that period as the final response. At block 715, the new peer randomly selects a peer from the remaining acknowledgments until the number of connections selected by the new peer equals the connection limit. Such a selection ensures that fast and slow connections through the grid are evenly distributed.

As mentioned above, different connection rules or additional connection rules may be used in various implementations. In one embodiment, the new peer selects the peer that corresponds to the first acknowledgment and the last acknowledgment, and then (following the first acknowledgment) the peer that corresponds to the acknowledgment in ascending order of response time. Select in order from. In another embodiment, the new peer does not wait and then start selecting peers, but selects peers as soon as a response arrives (eg, leaving one connection for the last acknowledgment received). Keep it). In another embodiment, the new peer uses the response time threshold to select peers (eg, it does not select peers whose response time exceeds a certain tolerance). In another embodiment, the new peer selects peers (using the information provided in the participation response) based on the characteristics of the peer, such as storage capacity, computing speed, access level, or available features.

In one embodiment, the peer system classifies connections according to the selection process used to select the connections. For example, the peer stores information indicating which of the open connections corresponds to the join response received with the shortest response time and the connection corresponding to the join response received with the longest response time. When connections are adjusted for peers that disconnect from the grid and new peers that join the grid, peers can adjust the classification of remembered connections.

In another embodiment, the new peer uses a server that helps open the connection. In one embodiment, the server provides a list of grid members with available connections and the addresses of their member peers. The new peer sends a join message directly to the presented grid members.

If the number of acknowledgments is less than the connection limit, there are surplus connections available for the new peer. In one embodiment, a new peer can force another peer to close an already established connection and open a connection with the new peer.

FIG. 8 shows a flowchart 800 of an embodiment in which a peer is forced to give a connection to a new peer in a peer-to-peer relay network. In the initial state, the new peer has selected the grid and is sending a join message to the member peers of the grid. The new peer is receiving the join response returned by the member peer. However, the new peer still has the connections available after selecting the peer that corresponds to all acknowledgments.

In block 805, the new peer selects the peer that corresponds to the negative response. The new peer uses the same connection rules as the acknowledgment to select the negative response (for example, according to the rule in Figure 7, select the first negative response received). In another aspect, the new peer uses a different set of forced connection rules. A new peer does not select a peer that is already connected to that new peer.

At block 810, the new peer sends a forced connection request to the selected peer. The forced connection request indicates that the new peer has at least one available connection (or a specific number thereof) and that the receiving peer should open a connection with the new peer.

At block 815, the new peer receives the forced connection request and selects the connection to close. The receiving peer uses the connection rule in reverse to select the connection to close. When using response time-based connection rules, the receiving peer uses the response time obtained and stored from the join response (and the connection available response as described below). In one embodiment, the receiving peer selects the last selected peer to select from the randomly selected peers, or selects the peers again at random. In another embodiment, the receiving peer uses another set of forced disconnect rules.

At block 820, the receiving peer closes the selected connection. The receiving peer sends a close message to the peer connected to the selected connection, and the two peers close the connection. The peer connected to the selected connection has an available connection at this stage and sends a connection available message to the grid, as described below.

At block 825, the receiving peer sends a confirmation to the new peer, and the two peers open a new connection. At this stage, the new peer has one less available connection. If the new peer has other connections available, the new peer returns to block 805 and repeats the process of selecting another negative response.

In another embodiment, the new peer does not force another peer to open a connection unless the new peer has at least two available connections. In another aspect, another threshold (such as 3) may be used. In another embodiment, the new peer sends a forced connection message if the number of new peer connections has not reached at least a certain number (minimum number of connections [connection floor]).

In another embodiment, the receiving peer of the forced connection message can reject this (eg, depending on the network load distribution situation). If rejected, the new peer chooses another peer to send a new forced connection message.

In another embodiment, if the new peer has more than one available connection and sends a forced connection message, the new peer indicates that the new peer has two available connections. Include information in this message. When the receiving peer chooses a closed connection, the receiving peer indicates that the new peer has another available connection to the connected peer (remote peer) of the selected connection (as appropriate for the new peer). Include address). When the receiving peer closes the connection with the remote peer, the remote peer sends a connection available message directly to the new peer (unless the new peer is already connected to the remote peer). The new peer opens a new connection with the receiving peer (selected by the new peer) and another new connection with the remote peer (selected by the receiving peer). In this way, the new peer can quickly establish two connections. If the new peer still has two available connections, the new peer may resend a forced connection message indicating that it has two available connections to another selected receiving peer.

If a peer system disconnects from another peer system, each of these peers will have an available connection. If one (or both) of these peers are still on the grid (ie, not disconnected from the grid), the peer sends a connect available message to the remaining connected peers of that peer. And relay the message through the grid to all other peers in the grid.

FIG. 9 shows a flowchart 900 of an embodiment of disconnection in a peer-to-peer relay network. Initially, the peer system (disconnected peer) is connected to at least two other peer systems in a peer-to-peer relay network.

At block 905, the cut peer is cut from one of the peers to which the cut peer was originally connected. This disconnection is either a voluntary disconnection at one end or a failure of the connection itself (eg, a failure of part of the path between peers). For example, voluntary disconnection can occur if the connected peer does not respond (as described below) or if the peer is forced to open a connection with a new peer (as described above). In one embodiment, the server may cause the peer to close one or more connections, which may result in a disconnect.

At block 910, the disconnected peer sends a connection availability message to the peer connected to this disconnected peer. The connection available message indicates that the disconnected peer currently has an available connection. In another embodiment, the connection available message indicates the number of connections available to the peer.

At block 915, the peer connected to the disconnected peer relays the connection available message. At block 920, the peer in the grid returns a connection available response to the disconnected member. The connection available response indicates whether the responding peer has an available connection. An acknowledgment indicates that the responding peer has an available connection. A negative response indicates that the responding peer does not have an available connection. The responding peer records the new piano address obtained from the join message and uses that address to send the join response. In another aspect, the responding peer returns a response through the grid, which is relayed to the cut peer. The disconnected peer receives the connection available response.

In block 925, the cut peer selects a member to connect from one of the grid members. The cut peer selects the peer to connect to using the connection rule, but the cut peer does not select a peer that is already connected to the cut peer. For example, in one embodiment, the disconnected peer uses the response time of the connection available response and the response time remembered by the peer still connected to the disconnected peer to replenish the lost connection. Select a peer. Different implementations may use different sets of connection rules. The cut peer remembers the response time of the selected peer. In another embodiment, the disconnected peer remembers the response time of all responses (acknowledged and negative responses). In one embodiment, the cut peer does not select from peers whose cut peer has been cut within a certain period of time.

After selecting the peer to connect, in block 930, the disconnected peer opens a connection to the selected peer. The disconnected peer sends a connection request to the selected peer, which confirms the request and opens the connection (unless the connection is unavailable on the selected peer). The connection between peers may be direct or indirect (eg, via a network such as the Internet). In one embodiment, the connected peer sends an update to the server confirming the connection.

Similar to the implementation for joining the grid described above with reference to FIG. 8, in one embodiment, the disconnected peer also attempts to open the connection using the connection available message (eg, all). If the disconnected peer still has an available connection (because the connection available response was a negative response), the disconnected peer may send a forced connection message as described above.

In another embodiment, the disconnected peer uses a server that assists in opening new connections. In one embodiment, the server provides a list of grid members with available connections and the addresses of their member peers. The disconnected peer sends a connect available message directly to the presented grid member.

The peer systems in the grid maintain the grid by polling each other on a regular basis. In one embodiment, the connected peers send messages to each other on a regular basis to confirm the connection and that the connected peer is still functioning.

FIG. 10 shows a flowchart 1000 of an embodiment that maintains a peer-to-peer relay network. In the initial state, multiple peer systems are connected in the grid.

In block 1005, a peer sends a keep message to each peer connected to that peer. The maintenance message is a request to the receiver to provide confirmation that the maintenance message has been received. In one embodiment, the peer sends (or pings) a ping message to each connected peer. At block 1010, the peer evaluates the response received in response to the maintenance message. The peer determines if the response is good. In one embodiment, if a response cannot be received from the connected peer, the peer determines that the peer's connection has failed (either due to the connection or the connected peer). If no response is received by the time limit, the peer determines that the peer's connection has failed. At block 1015, the peer closes the connection of the connection that the peer determines to be failing. The peer sends a connection close request to the connected peer of the failed connection. The peer closes the connection when it receives the confirmation. If the peer is unable to communicate with the connected peer of the failed connection, or does not receive a confirmation within the time limit, the peer closes the connection without confirmation. In another embodiment, the peer waits to close the connection for a predetermined time or for a predetermined number of failures until it is determined that a failure has occurred. In one embodiment, the peer sends an update to the server confirming the closed connection.

When the peer closes the connection, the peer voluntarily disconnects from one or more peers (eg, as described above with reference to FIG. 9) and sends out the appropriate connection availability message.

In another embodiment, the peer uses the server to evaluate the failed connection. For example, if the peer determines that the connection has failed, the peer sends a request to the server for help. The server sends a message to the peer at the other end of the failed connection to determine if the peer has failed or the connection has failed. The server then notifies the peer to facilitate opening new connections or adjusting the network as appropriate.

Figures 11-18 show an example of an embodiment that builds, adjusts, and maintains a grid.

In Figure 11, the peer system 1105_A(Peer A) uses server 1110 to establish a peer-to-peer relay network (grid) 1100 (connection between peer A and server 1110 is not shown). Peer A has three available connections because the connection limit for this grid is three. In Figure 12, the second peer system 1105_B(Peer B) is participating in Grid 1100. When peer B joins, peer B sends a join message to peer A, and peer A sends a positive join response to peer B. Peer A and Peer B open the connection.

In Figure 13, two more peer systems 1105_C,1105_D(Peer C and Peer D) are already participating in Grid 1100. Each of the four grid member peers A through D establishes three connections with the other peers in the grid 1100. New peer system 1105_E(Peer E) joins the grid. However, even if peer E sends a join message to other peers, each peer A ~ D has already reached the maximum number of connections allowed by the connection limit of grid 1100, so all join responses are negative. .. In Figure 14, peer E is forcing the connection to open. Peer E selects peer B from the negative responses (for example, because peer E first receives peer B's response) and sends a forced connection message to peer B. Peer B selects peer D to close the connection and closes the connection with peer D. Peer B confirms the connection with Peer E, and Peer B and E open a new connection. When peer B closes the connection with peer D, peer D will have an available connection. Peer D sends a connection available message to peers A and C, which relays this message throughout the grid 1100. Peers A, B, and C do not have an available connection and therefore send a negative response to peer D. Peer E has two connections available and sends an acknowledgment to Peer D. Peer D opens a connection with Peer E. Peer E still has an available connection and sends a connection available message. However, all responses are negative responses. Peer E has two established connections and only one available, so Peer E does not force another connection to open.

In FIG. 15, peer A disconnects from grid 1100. Peer A was connected to peers B, C, and D, respectively. When peer A disconnects, peers B, C, and D each have an available connection. Peers B, C, and D send a connection availability message, and peers B, C, D, and E each send an acknowledgment. Peers B to E evaluate the response to the connection available response, exclude the peers of the existing connection, and then establish the connection as shown in FIG. Each of peers B through E has three connections at this stage.

In Figure 17, three new peer systems 1105_F,1105_G,1105_H(Peers F, G, H) have joined the grid 1100 and have established a connection. Peers B to H each send a ping message to the peers connected to them as part of their regular activities to maintain the grid. For example, peer B pings peers D, E, G on a regular basis. Peer D does not respond well to Peer B in response to Peer B's ping message (for example, the response from Peer D is too slow or the response does not reach Peer B). In FIG. 18, peer B closes the connection of peer D. When peer B closes the connection, peer B and peer D will have an available connection. Peers B, D send a connection available message, which is relayed through the grid 1100. Peer B receives an acknowledgment from peers G and D. Peer B does not select peer G for the new connection because it is already connected to peer G. Peer B does not select Peer D for the new connection because it has just disconnected from Peer D due to a failed connection. Peer B does not open new connections (Peer B has two open connections and only one available, so Peer B tries to force a connection to be established. No, but in another embodiment peer B may do this). Peer D receives an acknowledgment from peers B and G. Peer D does not select Peer B for the new connection (or Peer B rejects the new connection request) because Peer B has just disconnected from Peer D due to a failed connection. Peer D selects peer G and opens a connection with peer G.

In the example shown in Figures 11-18, the peers in grid 1100 create and tune the grid by opening and closing connections without relying on server 1110 to manage connections (but server 1110). , Helping provide new peers with the addresses of the current member peers of the grid).

Redundancy list In one embodiment, peers in the grid reduce the traffic of redundant messages by avoiding sending messages that are determined to be redundant based on the current route in the grid.

In this implementation, each peer in the peer-to-peer relay network remembers a redundant list. The peer's verbose list specifies other peers that this peer does not send messages originating from the specified peer. Therefore, each entry in the redundant list specifies a source peer and a destination peer (connected to the relay peer). If a peer receives a message indicating an outgoing peer that is in the peer's redundant list, the peer does not relay the message to the connected peer indicated by the corresponding entry in the redundant list. In another embodiment, the peer can turn the redundant list feature on and off (at the request of the server, for example, after it turns out that a security issue has occurred).

FIG. 19 shows a flowchart 1900 of an embodiment that creates a redundant list in a peer-to-peer relay network. In the initial state, a plurality of peer systems are connected to form a peer-to-peer relay network. The receiving peer is connected to at least two other peers.

In block 1905, the receiving peer receives a redundant message from the connected peer. This redundant message is redundant because the receiving peer has already received the same message. The receiving peer uses the information in the received message to identify the redundant message as identical. As mentioned earlier, in some implementations each peer maintains a list of received messages so that it does not relay the same message twice. The receiving peer can also use this list to identify redundant messages.

At block 1910, the receiving peer creates a redundant update message. The receiving peer includes information that identifies the origin of the message and information that identifies the receiving peer in the redundant update message. For example, the receiving peer obtains the source identifier from the redundant message (for example, recall the message shown in FIG. 2) and stores this source identifier in the redundant update message.

At block 1915, the receiving peer sends a redundant update message to the source of the redundant message. The redundant message includes the address information of the source of the redundant message in the address information.

In block 1920, the source of the redundant message receives the redundant update message and updates the redundant list of sources. The source obtains information from the redundant update message that identifies the source of the redundant message and the receiver (receiver peer) of the redundant message. The source adds an entry to the source redundancy list that specifies that the source should not send messages originating from the specified origin to the receiving peer.

For example, referring to the grid 100 shown in FIG. 1, peer B receives a message originating from peer C from each of peers A, D, and E. Assuming that peer B first receives a message originating from peer C from peer A, the messages received from peer C as the source and from peers D and E are redundant messages. Peer B creates a redundant update message to be sent to peers D and E, specifying peer C as the source and peer B as the receiver. Peer B sends a redundant update message to Peer D. Peer D updates its verbose list to indicate that Peer D does not relay messages originating from Peer C to Peer B. Peer E receives a similar redundant update message from peer B and updates its redundant list in the same way.

As peers connect to or disconnect from the grid, the paths between clients change, which can lead to inaccurate redundant lists. Therefore, when a peer disconnects from the grid, the remaining peers update the redundant list.

FIG. 20 shows a flowchart 2000 of an embodiment that updates a redundant list for disconnected peers in a peer-to-peer relay network. In the initial state, a plurality of peer systems are connected to form a peer-to-peer relay network. The peer trying to disconnect is connected to at least two other peers.

In block 2005, the disconnect peer disconnects from the grid. The peer previously connected to this cutting peer becomes the cut peer at this point. Each of the peers to be cut undergoes the same process as described below.

In block 2010, the disconnected peer creates a deredundant message. The deredundancy message indicates information that identifies the peer to be disconnected. In block 2015, the disconnected peer sends a deredundancy message to peers that are still connected to the disconnected peer. In block 2020, the peer that receives the deredundancy message from the disconnected peer updates its redundancy list. The peer that receives the de-redundancy message removes the entry in the peer's redundancy list and changes the relay of the message to the disconnected peer specified by the de-redundancy message.

Returning to the example above with reference to Figures 1 and 19, peer D has an entry in its redundant list that specifies that messages originating from peer C should not be relayed to peer B. There is. When peer A disconnects from the grid, peer B recognizes peer A's disconnect and creates a deredundancy message. Peer B sends a deredundancy message to peers D and E. Peer D receives a deredundancy message from Peer B and specifies in Peer D's redundancy list that Peer D should not relay messages originating from Peer C to Peer B. Cancel the entry. Therefore, the next time peer D receives a message originating from peer C, peer D will relay the message back to peer B. Peer E updates its verbose list as well.

Multiple grids In one embodiment, the peer system can belong to multiple peer-to-peer relay networks. Each grid can be related or independent. The connections established according to each grid can be independent. Therefore, a peer may be connected to one peer in one grid, but not in another grid (even if both of the two peers are in both grids). In one embodiment, if two peers are connected in two grids, the peer uses one connection. The message contains information that indicates the grid to which the message belongs. The peer relays the incoming message according to the connections established for the specified grid of incoming messages.

In one embodiment, members of a peer-to-peer relay network can create subnetworks within the peer-to-peer relay network. In this case, each member in the subnetwork is also a member of a large grid. For example, a peer-to-peer relay network has all players in the game as a peer system, and each team (including a subset of all players) is a subnet of the peer system (for example, for dedicated communication in the game). Has. In this way, peers can establish a multi-channel environment for suitably delivering and receiving data.

In another embodiment, the peer-to-peer relay network is independent but shares one or more member peer systems. For example, a group of peers establishes a grid to accommodate a lobby or chat environment, and another group of peers, including at least one peer belonging to this first group, to accommodate a particular game. A grid can be established. In another example, a group of peers form a grid for a clan (organization), and some of those peers join or create another grid to play the game. ..

For example, in an online environment, all peers in this environment are connected to one main grid. The main grid is used for general announcements and general services. Peers create, join, or leave additional small grids to access online services such as chat rooms and games. Peers can use the main grid to communicate (without using a server) before establishing a smaller grid, such as when a new peer wants to join the grid. Since all control messages can be broadcast through the main grid, all peers can independently maintain a list of available grids and a list of active peers in each grid. In one embodiment, the peer does not use a central server.

FIG. 21 shows a flowchart 2100 of an embodiment that relays messages from peer systems belonging to a plurality of grids. In the initial state, multiple peer systems are connected to form two peer-to-peer relay networks. Relay peers are members of both grids and have their own connections and relay rules for each grid.

At block 2105, the relay peer receives the message. This message contains a grid identifier that indicates the grid to which the message belongs.

At block 2110, the relay peer selects the grid specified by the incoming message. Each grid has its own set of connections and its own set of relay rules. The relay peer selects the set of connections to use for relaying incoming messages and the set of relay rules to use by selecting the grid.

At block 2115, the relay peer selects a connection according to the selected grid and its corresponding relay rules. The relay peer uses the relay rules of the selected grid to select any suitable connection for relaying incoming messages.

At block 2120, the relay peer sends an incoming message to the selected peer. The relay peer coordinates the incoming message for each selected peer before relaying the message. At this time, for example, the address information of the received message is updated to indicate that the received message is about to be relayed to the peer selected from the relay peer.

audience In one embodiment, the peers in the grid are divided into participants or spectators. Participant peers generate a new message to relay across the grid. The spectator peer does not generate a new message and acts as a transit node in the grid. Both participants and spectators relay messages to their connected peers according to the grid's relay rules. In some applications, there can be a large number of spectators for each participant. In one embodiment having multiple participants, each participant has at least one connection to another participant.

In one example, while a group of participants is playing an online game, the audience watches it (observes the data without changing the data in the game). The number of spectators can be very large (thousands, etc.). Other examples include performance (such as music), speech and education. In some applications, peers process the distribution by relaying data, so increasing the number of spectators does not necessarily increase the server load required for distribution.

In one embodiment, when a peer joins the grid, the peer joins the grid as a participant or spectator. If a peer joins the grid as an spectator, the peer is not allowed to compose new messages or send new messages to the grid to relay them throughout the grid. If the spectator generates a new message and sends the new message to the peer connected to the spectator, the peer that receives the new message from the spectator does not forward or relay the received message. In one embodiment, some or all of the spectators may form another relevant grid as participants (eg, to discuss the game they are observing in the first grid).

FIG. 22 shows a flowchart 2200 of an embodiment that relays messages in a grid that corresponds to spectators and participants. In the initial state, a plurality of peer systems are connected to form a peer-to-peer relay network corresponding to participants and spectators.

Each peer system remembers a list of peers who are participants. In one embodiment, the participant peer periodically broadcasts a message indicating which peer is the participant. In another embodiment, the server assists in identifying participants.

At block 2205, the relay peer receives the message. This message contains a source identifier that indicates the peer that created this message.

At block 2210, the relay peer verifies that the source of the incoming message is the participant peer. The relay peer remembers the list of participant peers. The relay peer compares the peer identified as the source of the incoming message with the list of participant peers. If the source peer of the incoming message is not a participant (ie, an audience), the relay peer will not relay the received message.

If the source peer of the incoming message is a participant, at block 2215, the relay peer chooses a connection according to the relay rules of the grid. The relay peer uses relay rules to select any suitable connection for relaying incoming messages.

At block 2220, the relay peer sends an incoming message to the selected peer. The relay peer coordinates the incoming message for each selected peer before relaying the message. At this time, for example, the address information of the received message is updated to indicate that the received message is about to be relayed to the peer selected from the relay peer.

In another embodiment, the spectators are not on the same grid as the participants. The spectators are linked to the participant grid, forming a parallel spectator grid. The spectator receives the data from the participants and relays the data in the spectator grid. Links between grids can be provided by servers or gateways, or by connections between peers selected from each grid.

In another embodiment, the spectator can be a conditional spectator. Conditional spectators can request authority to generate data that is relayed throughout the grid. If the spectator is authorized, the spectator can send a message relayed by the peer in the grid (for example, the message contains a permission flag). This privilege may be granted by the server, by the peer selected as the mediator, or by the participants (one or more). For example, in an educational environment, participants are instructors and spectators may request authority to ask questions that are relayed to all peers.

Island restoration In one embodiment, servers and peers in a peer-to-peer relay network accommodate coordination of connections in the grid to avoid or recover from island formation. A group of isolated peers in the grid is called an island. When multiple peers cut at about the same time, islands may form in the grid. In the disconnect process described above, the remaining peers send a message indicating the available connections, but if multiple disconnects occur at the same time, the remaining peers may form an isolated group in the grid. is there. A peer within one island cannot send a message to a peer within another island because there is no peer-to-peer connection between the islands. The server detects the formation of the island and interacts with the peer to remove the island.

FIG. 23 shows a flowchart 2300 of an embodiment that detects islands in the grid. In the initial state, multiple peer systems are connected to form a peer-to-peer relay network or grid. When a peer opens and closes a connection, or disconnects, the peer notifies the grid's servers of changes to this connection. In this way, the server keeps track of all connections in the grid. The server also maintains an ordered list of peers in the grid.

At block 2305, the server sets the island counter. The island counter represents the number of islands. In one embodiment, the server sets the counter i to 1.

At block 2310, the server selects the starting peer. If the island counter is 1, the server selects the first peer in the ordered list of peers as the starting peer. If the island counter is greater than 1, the server chooses the most recently discovered unmarked peer (more on this later) as the starting peer.

At block 2315, the server marks each of the peers connected to the starting peer as belonging to the same island as the starting peer. The server marks a peer that is directly connected to the starting peer and a peer that is indirectly connected to the starting peer through another peer (eg, from the starting peer to the connected peer, to this connected peer). Proceed with ... to the connected peer). The server marks the peer by the current value of the island counter to indicate the island to which the peer belongs.

After marking all the peers connected to the starting peer, at block 2320, the server determines if there are any unmarked peers left in the grid. In one embodiment, the server sequentially processes the ordered list of peers to search for unmarked peers.

If the server finds an unmarked peer, at block 2325, the server increments the island counter. The server increments the island counter to indicate that additional islands have been detected. After incrementing the island counter, the server returns to block 2310 and uses the unmarked peer found as the starting peer.

If the server cannot find an unmarked peer, at block 233, the server calculates the number of islands found. The island counter increments the island counter each time an island is detected, so the island counter represents the number of islands detected. If the island counter is 1, only one island has been found, so the grid is not divided into multiple islands. If the island counter is greater than 1, multiple islands have been found and the grid is divided into islands.

FIG. 24 shows a flowchart 2400 of an embodiment of island removal in a peer-to-peer relay network. Initially, multiple peer systems are connected in a peer-to-peer relay network or grid. The grid is divided into islands of two peers, with a peer in one island having no connection route to a peer in the other island. The server detects these two islands, for example by using the process shown in Figure 23.

At block 2405, the server selects a peer from each island. The server can select a peer on the first island and a peer on the second island in various ways. In one embodiment, the server selects peers with available connections. In another embodiment, the server randomly selects peers from the island.

If the peer on the first island does not have an available connection, at block 2410, the server sends a connection close message to the peer on the first island to close the connection. The peer on the first island receives the message from the server and, as described above, chooses the connection to close, similar to the case where the peer chooses the connection to close when it receives the forced connection message. The peer on the first island closes the connection and has an available connection.

At block 2415, the server sends a forced connection start message to the peers on the first island. The forced connection start message contains the address of the peer on the second island. The peer on the first island receives this message from the server and sends a forced connection message to the peer on the second island.

At block 2420, the peer on the second island receives a forced connection message from the peer on the first island, selects the connection to close, and closes the selected connection. The peer on the second island selects the connection to close in the same way as described above for the recipient of the forced connection message. If the peer on the second island has an available connection before closing the connection, the peer on the second island does not close its connection.

At block 2425, the peer on the first island sends a connection open request to the peer on the second island, and the two peers open the connection. Once the connection is opened, the islands are combined to form an island. The peer sends an update to the server confirming this connection. As detected above, if there are more islands left, the server returns to block 2405 and connects two or more of the remaining islands.

Figures 25 and 26 show examples of island detection and binding. In FIG. 25, a grid 2500 similar to the grid 1100 in FIG. 11 is divided into two islands because peers C, G, and F cut at the same time. The first island contains peers A, B, D and E. The first island contains peers H, I, J. In FIG. 26, the server opens a connection with peer I to peer D, joining the two islands.

Security In one embodiment, the peer-to-peer relay network addresses the detection of fraud and / or security breaches, and recovery from them. In a fraudulent violation, for example, data is manipulated to change the progress of the game, and the result of processing online activities is changed. Security breaches use malicious or improper data to damage the grid or cause the grid to fail.

FIG. 27 shows a flowchart 2700 of an embodiment for detecting fraudulent violations in a peer-to-peer relay network. In the initial state, multiple peer systems are connected to form a peer-to-peer relay network or grid.

At block 2705, the peer receives a message from each of its connected peers. As mentioned earlier, peers in the grid relay messages throughout the grid. The peer receives the same message (the content data is the same, but the address information may be different) over each connection with the other peers. For example, if a peer has three open connections, this peer receives the same message three times from the three peers. Peers use information in the message that indicates the source and sequence value, such as the source identifier 215 and sequence value 220 shown in message 205 in Figure 2, to identify the message as identical. The same message received from different peers has the same source and sequence information.

At block 2710, the peer compares the messages received from each of the connected peers. The peer compares the data portion of the message, such as the data 230 shown in message 205 in FIG. The peer determines if any of the received messages differ in the data portion of the message. In one embodiment, if the data portion of a message received from one connected peer is different from the data portion of the same message received from another connected peer, the peer determines that a fraud breach has occurred. The peer determines that the peer that sent the message with different data is the cause of the fraud breach. In another aspect, peers use different techniques to detect fraudulent breaches or identify the peer responsible for the fraudulent breach. As appropriate, peers do not relay messages with different data parts.

In the event of a fraud breach, at block 2715, the peer sends a fraud warning. The fraud warning indicates that a fraudulent breach has occurred and the peer responsible for the fraudulent breach. The peer sends a fraud alert to the connected peer, relaying the alert throughout the grid. In another embodiment, the peer sends a fraud alert to the server for appropriate action.

In block 2720, when a peer receives a fraud warning, the peer takes remedial action against the breach. Peers take steps to prevent cheating peers from continuing to influence the activities of the grid. In one embodiment, the peer ignores messages from the cheating peer. In another embodiment, the peer forces the cheating peer to disconnect from the grid. Peers also take steps to remedy the effects of messages containing different data, such as sending alternative messages with the correct data indicated by the data in other messages used to identify fraudulent messages. and so on. In another aspect, one of the peers estimates the correct data and relays this correct data throughout the grid. In another embodiment, the peer responds to fraud alerts by notifying the server. In this case, the server deals with the fraudulent breach, for example by disconnecting the peer that is causing the fraudulent breach.

In another embodiment, when a peer sends a message, the recipient returns the message to the sending peer. The sending peer keeps a copy of the outgoing message. When the sending peer receives the message returned from the receiver, the sending peer compares the data in the outgoing message with the data in the received message. The peer discovers the difference and detects a fraudulent breach. The peer determines that the receiver has modified the message and issues a fraud warning. In one embodiment, no remedial or corrective action is taken against the cheating peer until multiple breaches are reported (which is, for example, tracked by a server). In another embodiment, this send-back check to detect fraud is the first layer of fraud detection, and once a potential problem has been identified, it involves more complex steps. Be done.

In another embodiment, the peer detects a fraudulent breach by comparing the data in the received message with a set of predictive data generated by the peer. If the peer determines that the data in the received message is different from what the peer generated, the peer determines that the source of the received message is the cause of the fraudulent breach and issues a warning.

In the example of detecting a fraudulent violation on the grid 100 shown in FIG. 1, peer B receives the same message from each of peers A, D, and E. Peer B identifies the messages to be the same by comparing the source identifier and the sequence value. If peer B detects that the message from peer A has different data parts, peer B sends a fraud warning indicating that peer A is a fraud peer. Peer B sends a fraud warning to peers D and E (and optionally to peer A). The peer relays the fraud warning until all peers receive the warning. In response to this warning, the peer ignores all subsequent messages from peer A. As a result, peers B, C, and D no longer relay messages from peer A.

FIG. 28 shows a flowchart 2800 of an embodiment for detecting a security breach in a peer-to-peer relay network. In the initial state, multiple peer systems are connected to form a peer-to-peer relay network or grid.

At block 2805, the peer receives a message from one of its connected peers. At block 2810, the peer parses this message to detect a security breach. The peer recognizes that the message is invalid or contains invalid data and determines that the message is a security breach. In another embodiment, the peer determines that the message is a security breach by analyzing how the message was sent to that peer. For example, if a message is sent as one of the same messages sent over and over again (for example, as seen in a out-of-service attack), the peer recognizes the message as a security breach. In one embodiment, the message is sent as a series of packets and the peer detects a security breach at a lower level than the entire message (such as the packet level). The peer also determines that the source of the security breach message is the source of the security breach. In another aspect, peers use different techniques to detect security breaches or identify the causative peer of a fraudulent breach. Peers do not relay security breach messages or data.

In block 2815, the peer sends a security alert if a security breach has occurred. Security warnings indicate that a security breach has occurred and the peer that is causing the security breach. The peer sends a security alert to the connected peer, relaying the alert throughout the grid. In another embodiment, the peer sends a security warning to the server for appropriate action.

At block 2820, when a peer receives a security warning, the peer takes steps to recover from the breach. The peer takes steps to prevent the infringing peer from continuing to affect or damage the grid. In one embodiment, the peer ignores the message from the peer that is causing the security breach. In another embodiment, the peer forces the peer that is causing the security breach to disconnect from the grid. The peer will take appropriate steps to recover from the damage caused by the security breach. In another embodiment, the peer responds to security alerts by notifying the server. In this case, the server addresses the security breach by, for example, disconnecting the peer causing the breach and taking steps to correct the damage caused to the grid.

Figures 29 and 30 show block diagrams of one embodiment of server 2905 and peer system 3005, respectively. In another embodiment, the server or peer may have fewer components than shown in FIGS. 29,30, but may include different or additional components.

The server 2905 operates as described above and has components for providing the above-mentioned functions. This component includes grid establishment 2910, peer addition 2915, peer connection 2920, peer disconnection 2925, grid maintenance 2930, grid data (connections, members, connection limits, etc.) and rules (relay rules, connections). (Rules, etc.) Memory and Generation 2935, Multiple World Management 2940, Redundant List Management and Support 2940, Multiple Grid Management 2950, Participant and Audience Management in Grid 2955, Island Detection and Recovery Processing 2960 , Managing fraud and security breaches and dealing with them 2965, and central server services 2970 (eg network communication and addressing, player matching, chat mechanisms, data back up, etc.) is there.

The peer system 3005 operates as described above and has components for providing the above-mentioned functions. This component includes grid establishment 3010, grid join 3015, peer connection 3020, peer disconnection 3025, grid maintenance 3030, grid data (connections, members, connection limits, etc.) and rules (relay rules, connections). (Rules, etc.) storage and generation 3035, redundant list creation, update and use 3040, behavior on multiple grids 3045, behavior with participants and spectators on the grid and behavior as these 3050, island detection and recovery processing 3055 , Management of fraud and security breaches, detection and response to them 3060, peer system services 3065 (eg network communication and addressing, player matching, chat mechanism, data back up, etc.) There is.

Various implementations of peer-to-peer relay networks provide desirable benefits. Grids can be very useful in many network applications, such as online giant multiplayer computer games. Online gaming applications are just one example of a large group of network applications that share one thing in common: they share and maintain one common dataset. When a dataset is updated on one peer, this information is sent to a group of other peers and relayed throughout the grid so that each peer has an updated dataset. Relay grids allow connected peers to exchange data with each other with limited network bandwidth without going through a central server (for data distribution). This network can be used to exchange game data, other game-related information, media files, streaming audio or streaming video.

For example, in one embodiment, the peer uses a grid for file publishing. Peers in the grid publish files (split into one message or multiple messages) by sending files to peers connected to this publisher, and grid member peers file files throughout the grid. To all members. In this way, all members of the grid can receive the published file without using a server and without using a direct connection from the publisher to all peers. Any kind of file can be published in various implementations. The file can be data, media or an executable software application. Examples of files published through the grid include streaming media (such as audio and / or video), media files, playback data for games or other applications, maps, announcements, messages, application data and modules (maps). , Templates, textures, audio, etc.), but not limited to these.

Various implementations of the present invention are realized as electronic hardware, computer software, or a combination of these technologies. Most implementations include one or more computer programs run by a programmable computer. For example, in one embodiment, each peer system and server has one or more computers running software that implements the functionality of a peer-to-peer relay network. In general, each computer has one or more processors and one or more data storage elements (eg, volatile or non-volatile memory modules, and hard disk drives, floppy disk drives, CD-ROM drives, magnetic tape drives, etc.). It has a permanent optical and magnetic storage device, one or more input devices (eg, mouse, keyboard), and one or more output devices (eg, display console, printer).

Computer programs are usually stored in persistent storage media and then contain executable code that is copied to memory at run time. The processor executes this code by retrieving executable instructions from memory in a predetermined order. When executing program code, the computer receives data from the input device and / or storage device, performs processing on the data, and sends the obtained data to the output device and / or storage device.

Various implementations for the purpose of explaining the present invention have been described. However, those skilled in the art will appreciate that other implementations are possible and are within the scope of the present invention. For example, the above description describes some implementations of peer-to-peer relay networks with examples corresponding to gaming applications, but other applications such as file sharing and any other data distribution application are also possible.

Therefore, the present invention is not limited to these embodiments described above.

<figref num="1">Explanatory drawing of an embodiment of a peer-to-peer relay network.</figref><figref num="2">A block diagram of an embodiment of a message.</figref><figref num="3">A flowchart of an embodiment in which peers relay messages in a peer-to-peer relay network.</figref><figref num="4">A flowchart of an embodiment in a peer-to-peer relay network in which peers relay messages according to a set of relay rules.</figref><figref num="5">A flowchart of an embodiment for establishing a peer-to-peer relay network.</figref><figref num="6">A flowchart of an embodiment in which a peer is connected to a peer-to-peer relay network.</figref><figref num="7">A flowchart of an embodiment of selecting peers to participate in a peer-to-peer relay network.</figref><figref num="8">A flowchart of an embodiment in which a peer is forced to give a connection to a new peer in a peer-to-peer relay network.</figref><figref num="9">The flowchart of one embodiment of disconnection in a peer-to-peer relay network.</figref><figref num="10">A flowchart of an embodiment that maintains a peer-to-peer relay network.</figref><figref num="11">An explanatory diagram of an embodiment that builds, adjusts, and maintains a grid.</figref><figref num="12">An explanatory diagram of an embodiment that builds, adjusts, and maintains a grid.</figref><figref num="13">An explanatory diagram of an embodiment that builds, adjusts, and maintains a grid.</figref><figref num="14">An explanatory diagram of an embodiment that builds, adjusts, and maintains a grid.</figref><figref num="15">An explanatory diagram of an embodiment that builds, adjusts, and maintains a grid.</figref><figref num="16">An explanatory diagram of an embodiment that builds, adjusts, and maintains a grid.</figref><figref num="17">An explanatory diagram of an embodiment that builds, adjusts, and maintains a grid.</figref><figref num="18">An explanatory diagram of an embodiment that builds, adjusts, and maintains a grid.</figref><figref num="19">A flowchart of an embodiment that creates a redundant list in a peer-to-peer relay network.</figref><figref num="20">A flowchart of an embodiment that updates a redundant list for disconnected peers in a peer-to-peer relay network.</figref><figref num="21">A flowchart of an embodiment that relays messages from peer systems that belong to a plurality of grids.</figref><figref num="22">A flowchart of an embodiment that relays messages on a grid that corresponds to spectators and participants.</figref><figref num="23">A flowchart of an embodiment that detects islands in the grid.</figref><figref num="24">A flowchart of an embodiment of removing islands in a peer-to-peer relay network.</figref><figref num="25">Explanatory diagram of island detection and binding.</figref><figref num="26">Explanatory diagram of island detection and binding.</figref><figref num="27">A flowchart of an embodiment for detecting a fraudulent violation in a peer-to-peer relay network.</figref><figref num="28">A flowchart of an embodiment for detecting a security breach in a peer-to-peer relay network.</figref><figref num="29">A block diagram of a server embodiment.</figref><figref num="30">A block diagram of an embodiment of a peer system.</figref><figref num="31A">Schematic diagram of a typical client-server and peer-to-peer architecture.</figref><figref num="31B">Schematic diagram of a typical client-server and peer-to-peer architecture.</figref>