CN1894928B - Multiple peer-to-peer relay network - Google Patents

Abstract

Methods and apparatus for implementing peer-to-peer relay. In one implementation, a network environment supporting multiple peer-to-peer relay networks includes: a first peer-to-peer relay network including N1 peer systems; and a second peer-to-peer relay network including N2 peer systems; wherein each peer system in said first peer-to-peer relay network is connected to a number of other peer systems in said first peer-to-peer relay network that is less than or equal to a first connection limit, said first connection limit is greater than or equal to 2, said first connection limit is less than or equal to N1-2, each peer system in said first peer-to-peer relay network is configured to relay data to peer systems connected to that peer system according to a first set of one or more relay rules, each peer system in said second peer-to-peer relay network is connected to a number of other peer systems in said second peer-to-peer relay network that is less than or equal to a second connection limit, said second connection limit is greater than or equal to 2, said second connection limit is less than or equal to N2-2, each peer system in said second peer-to-peer relay network is configured to relay data to peer systems connected to that peer system according to a second set of one or more relay rules, and at least one peer system in said first peer-to-peer relay network is also in said second peer-to-peer relay network.

Description

Multiple peer-to-peer relay networks

This application claims the benefit of US Provisional Application 60/513098 ("Peer-to-Peer Relay Network"), filed October 2003, the disclosure of which is incorporated herein by reference.

background

In a typical client server network, each client on the network establishes a connection to a central server. Clients request services and data from servers. To communicate with another client, a client sends a request to a server. Typically, clients do not establish direct connections with each other. In a client server network with N clients, each client has 1 connection to the server, and the server has N corresponding connections to each client. For example, as shown in Figure 31A, in a client server network with 6 clients, each client has 1 connection to the server, and the server has 6 corresponding connections to the clients.

In a typical peer-to-peer network (or "P2P network"), each member (or peer) in the peer-to-peer network establishes a connection to every other member. By using these direct peer-to-peer connections, members send data directly to other members and request data directly from other members, rather than using a centralized server (compared to, for example, a typical client-server network where members interact through a server). In general, each member of a network has similar responsibilities within the network, and members are generally considered equal (as network members). In a peer-to-peer network with N peers, each peer has N-1 connections to other peers. For example, as shown in Figure 3 IB, in a peer-to-peer network with 6 peers, each peer has 5 connections to other peers.

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 for building peer-to-peer networks).

overview

The present invention provides methods and apparatus for implementing peer-to-peer relaying. In one implementation, the network environment supporting multiple peer-to-peer relay networks includes: a first peer-to-peer relay network including N1 peer-to-peer systems; and a second peer-to-peer relay network including N2 peer-to-peer systems; wherein , each peer system in the first peer-to-peer relay network is connected to a number of other peer systems in the first peer-to-peer relay network that are less than or equal to a first connection limit, the first connection limit is greater than or equal to 2, the first connection limit is less than or equal to N1-2, and each peer system in the first peer-to-peer relay network is configured to set, relaying data to peer systems connected to the peer system, each peer system in the second peer-to-peer relay network connected to less than or equal to the second peer-to-peer relay network A plurality of other peer-to-peer systems of two connection limits, said second connection limit being greater than or equal to 2, said second connection limit being less than or equal to N2-2, each peer in said second peer-to-peer relay network The system is configured to relay data to peer systems connected to the peer system and at least one peer in said first peer-to-peer relay network according to a second set of one or more relay rules. The system is also in the second peer-to-peer relay network.

In one implementation, a method of relaying data in a peer-to-peer relay network includes receiving, at a relay peer system, data from a sending peer system connected to the relay peer system in the peer-to-peer relay network ; Select a peer-to-peer relay network corresponding to the received data, wherein the selected peer-to-peer relay network has a corresponding set of one or more relay rules; apply the one or more relay rules a set of rules to select zero or more peer systems to which to relay the data indicated by the set of one or more relay rules; and relay the data to the Any peer system selected by applying said set of one or more relay rules.

In one implementation, a peer-to-peer system in a peer-to-peer relay network includes: for receiving at the relay peer system from a sending peer system connected to the relay peer system in the peer-to-peer relay network data; a tool for selecting a peer-to-peer relay network corresponding to received data, wherein the selected peer-to-peer relay network has a corresponding set of one or more relay rules; for applying the the set of one or more relay rules to select zero or more peer systems to which to relay the data indicated by the set of one or more relay rules a tool; and a tool for relaying said data to any peer system selected by applying said set of one or more relay rules.

Brief description of the drawings

Figure 1 shows a diagram of one implementation of a peer-to-peer relay network.

Figure 2 shows a block diagram of one implementation of the message.

Figure 3 shows a flow diagram of one implementation of peers relaying messages in a peer-to-peer relay network.

4 shows a flow diagram of one implementation of peers relaying messages in a peer-to-peer relay network according to a set of relay rules.

Figure 5 shows a flowchart of one implementation of establishing a peer-to-peer relay network.

Figure 6 shows a flow diagram of one implementation of connecting peers to a peer-to-peer relay network.

Figure 7 shows a flow diagram of one implementation of selecting peers for joining a peer-to-peer relay network.

Figure 8 shows a flow diagram of one implementation of forcing peers to provide connectivity for new peers in a peer-to-peer relay network.

Figure 9 shows a flowchart of one implementation of disconnecting in a peer-to-peer relay network.

Figure 10 shows a flow diagram of one implementation of maintaining a peer-to-peer relay network.

Figures 11-18 illustrate an example implementation for building, tuning and maintaining a grid.

Figure 19 shows a flowchart of one implementation of building a redundancy list in a peer-to-peer relay network.

Figure 20 shows a flowchart of one implementation of updating a redundancy list for a peer to be disconnected in a peer-to-peer relay network.

Figure 21 shows a flowchart of one implementation for relaying messages from peer-to-peer systems belonging to multiple grids.

Figure 22 shows a flow diagram of one implementation for relaying messages in a grid that supports viewers and participants.

Figure 23 shows a flowchart of one implementation for detecting islands in a grid.

Figure 24 shows a flowchart of one implementation for deleting islands in a peer-to-peer relay network.

25 and 26 show examples of detection islands and connection islands.

Figure 27 shows a flowchart of one implementation of detecting fraudulent violations in a peer-to-peer relay network.

Figure 28 shows a flowchart of one implementation for detecting security violations in a peer-to-peer relay network.

Figures 29 and 30 show block diagrams of one implementation of the server and peer-to-peer systems, respectively.

Figures 31A and 31B illustrate typical client server and peer-to-peer architectures.

Detailed description

The present invention provides methods and apparatus for implementing peer-to-peer relaying. In one implementation, multiple computer systems are connected to form a peer-to-peer network. Each computer system is connected to up to a predetermined number of other computer systems. To communicate, computer systems send messages to each connected system. When a computer system receives a message from another computer system, the receiving computer system sends or relays the message to the other computer system according to the relay protocol or rules for the peer-to-peer relay network. Messages propagate throughout the network to all member computer systems according to relay rules.

FIG. 1 shows a diagram of one implementation of a peer-to-peer relay network 100 . A peer-to-peer relay network may also be referred to as a "mesh." In FIG. 1, a set of ten peer systems 105A...J (also referred to as "peers") are connected to form a peer-to-peer relay network. Each peer system 105 is a network-enabled game console, such as the PlayStation 2 ^(TM) game console with network adapter provided by Sony Computer Entertainment Inc. Peer-to-peer systems 105 are connected directly (eg, via a wired or wireless connection) or indirectly (eg, via an intranet or a public IP network such as the Internet). In one implementation, the peer-to-peer system 105 connects using a UDP or TCP connection. Peer-to-peer systems 105 exchange data to support a network environment or activity, such as a chat environment or an online game.

Each peer 105 also has a connection to a central server 110, such as a UDP or TCP connection over the Internet (the connection to the server 110 is not shown in Figure 1). Server 110 is a server computer system that provides centralized services for connected peer systems 105 . In one implementation, the server provides an address directory of peer systems and tracks connections between peer systems. Examples of other server services include, but are not limited to: verification, player matching, and tracking of peer system addresses. As described below, in some implementations, a server may support multiple independent or related peer-to-peer relay networks. In one implementation, the server supports multiple environments or worlds, partitioning or grouping clients into environments and filtering data appropriately. In one implementation, the server includes one or more aspects of the server described in the following co-pending and commonly assigned U.S. patent application: U.S. Patent Application 10/___ filed by ___ (“Configuration Switching: Network Communication Architecture Between Dynamically Changing (Configuration Switching: Dynamically Changing Between Network Communication Architectures)") and US Patent Application 10/___ ("Multi-User Application Programming Interface (Multi-User Application Programming Interface)") filed by ___, these applications The disclosure is incorporated herein by reference. In another implementation, the peers do not use a centralized server (eg, build the grid and relay data by direct communication).

Network 100 has connection limit 3. The connection limit is set by the server and defines the maximum number of connections each peer 105 is allowed to have in the mesh. In another implementation, one peer (eg, the meshing peer) sets the connection limit, or multiple peers negotiate the connection limit. In Figure 1, the connection limit is 3, and each peer 105 has 3 connections. Peer systems A-J each have 3 connections to other peers (peer system 105A is also referred to as peer system A or peer A). Network 100 is a 3-connection peer-to-peer relay network, so each peer 105 has 3 connections to other peers.

These peers 105 communicate by broadcasting messages throughout the network 100 . These peers 105 propagate messages by relaying received messages to connected peers 105 according to the relay rules of the network 100 . In this implementation, the relay rules state that peer 105 relays messages to every peer 105 connected to peer 105, with two exceptions: (i) peer 105 does not relay the pair A peer 105 has relayed the message, and (ii) the peer 105 does not relay the message back to the peer 105 from which the relaying peer 105 received the message. In one implementation, the peer 105 also does not relay the message to a peer 105 from which the relaying peer 105 has received the message (e.g., when the relaying peer 105 is on the relaying peer When the message is received from multiple peers 105 before the peer 105 relays the message). In other implementations, different or additional rules may be used. Relay rules (and other rules) are established by the server, or preset in the peer-to-peer system (or its system software). In another implementation, rules can be modified dynamically, such as by propagating messages with rule updates throughout the grid.

In one application of the network 100, the peers 105 are playing a network game. During the course of the game, a peer 105 generates update messages reflecting actions or events caused by the peer 105 . For example, during execution of game software on a player's computer system (e.g., peer A), the computer system generates update data representing in-game actions, such as moves or shots (e.g., update player's position). For the update to take effect, each peer 105 needs to receive an update from the updating peer 105 . These peers 105 relay the update message throughout the network 100 to propagate the message to each peer 105 .

In one example, peer A has updates to send to other peers. Peer A constructs an update message, which includes update data, an identifier identifying peer A as an update source, and a sequence identifier to distinguish this message from other messages sent by peer A, and provide a relative sequence. Peer A sends a message to its connected peers: B, C, D. Peer B sends the message received from peer A to peers D and E. Peer B does not send the message to peer A because peer B received the message from 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, since peer B recognizes that it is the same message (by using the message's identifier), peer B no longer relays the message. Similarly, peer D does not relay messages received from peer B. Assuming that the connections between peers are essentially the same in terms of the amount of time it takes to transmit messages between peers, then in the next set of hops, peer E transmits a message from peer B to peer F and I, peer G relays a message from peer C to peers D and F (depending on which message arrives at peer C first, or relays a message from peer D to peer peers C and F), and peer H relays messages from peer C to peers I and J. At this point, each peer has received the update message from peer A. However, peers F, I and J have just received the message, so these peers will relay the message. Peer F relays messages from peer E to peers G and J (or relays messages from peer G to peers E and J, whichever comes first), for Peer I relays messages from peer E to peers H and J (or from peer H to peers E and J, whichever comes first), and to peers Peer J relays the message from peer H to peers F and I. Up to this point, all peers have sent or relayed the message once. Since these peers will not relay the same message again, the propagation of this message ends.

In this way, the message is propagated throughout the peer-to-peer network 100 . This dissemination of update information among peer systems 105 participating in the game supports the game and the game environment. These peer-to-peer systems 105 can distribute data throughout the network 100 without using a centralized server 110 for distribution. Additionally, each peer 105 is not directly connected to other peers 105, thereby saving resources. Thus, grid 100 limits each peer's network bandwidth requirements (since it only needs to communicate with a limited number of other clients), while allowing data from any single client to propagate quickly to other peers in the grid ( For example, by using UDP sockets).

In other implementations, the peer-to-peer relay network includes more or fewer peer systems, and the network has different connection limits. Depending on the number of peers, the connection limit, and the rules used to establish connections, not all peers can have all their connections filled, and therefore there may be one (or more) peers with available connections .

In another implementation, the connection limit can be different. In one implementation, the connection limit is specific to each peer system, with some, all or none of the peers having different connection limits. Each peer sets its connection limit, or the server specifies the connection limit. In one example, peers X and Y each have a connection limit of 5, and peer Z has a connection limit of 4, and the remaining peers each have a connection limit of 3. In another implementation, the connection limit is dynamic. In this case, the server adjusts the peer's connection limit, such as based on network performance (eg, when network traffic is low, the connection limit is low). In another implementation, one or more peer systems each dynamically adjust their respective connection limits. Alternatively, the server dynamically adjusts the connection limit for specific peer systems (eg, some but not all).

FIG. 2 shows a block diagram of one implementation of message 205 . Message 205 is constructed by the peer-to-peer system to send to other peers in the peer-to-peer relay network. For example, referring to FIG. 1 , peer A constructs a message such as message 205 when peer A has an update message to send to other peers. Message 205 includes: addressing data 210 , origin identifier 215 , sequence value 220 and payload data 230 . Addressing data 210 includes network addressing information to send message 205 from the peer to another peer. In one implementation, addressing data 210 includes the IP address of the sending peer and the IP address of the intended receiving peer. Origin identifier 215 identifies the peer that constructed message 205 . This identifier 215 indicates to peers throughout the peer-to-peer relay network the origin of messages propagating through the network. By using origin identifier 215, a peer receiving message 205 can determine from which peer in the network message 205 originated. An order value 220 identifies a particular message 205 and provides relative order information. Using order value 220 , a peer receiving message 205 can determine whether a particular message has been received, and can determine the order or sequence of messages sent from the peer indicated by origin identifier 215 . Data 230 is the payload data of message 205 . For update messages (eg, in a game), payload data 230 is the update data to be used by the receiving peer. In alternative implementations, different types of messages may be used, and messages may be formatted differently (eg, include different or additional information) than the messages shown in FIG. 2 . For example, a message may include a file or a portion of a file or a frame of data, such as a frame of game data or an audio file frame or portion thereof published to grid members. The receiving peer can reconstruct the entire file using the sequential values included in each message. In another example, the message includes additional identification information, such as an identifier indicating the grid to which the message belongs, for relaying by peers belonging to multiple grids.

FIG. 3 shows a flowchart 300 of one implementation of peers relaying messages in a peer-to-peer relay network. Initially, peers connect to one or more other peer systems in the peer-to-peer relay network.

The peer receives a message from the sending peer over the connection between the peer and the sending peer, block 305 . The message includes an origin identifier, sequence value, and payload data (eg, update data), the same as the message shown in FIG. 2 .

The peer selects a connection to relay the received message to, block 310 . A peer selects a connection from the peer's available connections according to the relay rules used for the peer-to-peer relay network. After applying the relay rules, the peer may select some of the peer's connections, none of the peer's connections, or all of the peer's connections.

The peer relays the message to each selected connection, block 315 . Peers build messages for each selected connection. For each message to send, the peer uses the received message, but updates the addressing information as appropriate (e.g. changing the sender to the peer and the receiver to the receiving peer for the connection ). Accordingly, the payload data remains unchanged. In another implementation, peers may also add data to the message or change data in the message. The peer sends the constructed message to the appropriate recipient.

FIG. 4 illustrates a flowchart 400 of one implementation of peers relaying messages in a peer-to-peer relay network according to a set of relay rules. The relay rules used in Figure 4 are an example of a set of relay rules. Other implementations may use different or additional relay rules. Initially, a relay peer is connected to N other peer systems in the peer-to-peer relay network. For example, in the network shown in Figure 1, peer D is connected to 3 other peers (and thus N=3 in this case). The relay rules for relaying messages in Figure 4 are:

1. Do not relay messages twice

2. Do not relay the message back to the sender

3. Do not relay the message to the originating peer

4. After applying rules 1 and 2, relay messages to peers on available connections

The relay peer receives the message, block 405. The relaying peer determines whether the message has been received by the relaying peer, block 410 . The relaying peer compares the message's identification data with data stored by the relaying peer for already received messages. In one implementation, each peer maintains a table of received messages consisting of origin identifiers and sequence values of received messages. The relaying peer retrieves the origin identifier and sequence value from the received message and compares this information with data stored in the relaying peer's received messages table. If the relaying peer determines that the relaying peer has previously received this received message (e.g., the peer finds an entry in the received message table that stores the origin identifier and sequence value of the received message), then the relaying peer Peers do not relay received messages. In another implementation, the relaying peer checks to determine if the relaying peer has previously relayed the received message.

If the relaying peer determines that the relaying peer has not previously received the message, the relaying peer records that the message was received, block 412 . In one implementation, the relaying peer adds an entry for the received message's origin identifier and sequence value to the relaying peer's received message table. If the table already has an entry for this origin identifier and sequence value, the relaying peer does not alter the table.

After recording that the message has been received, the relaying peer sets a counter, block 415 . The relaying peer uses the counter to step through each available connection to the relaying peer. In one implementation, the relaying peer sets the integer counter i to one.

The relaying peer determines whether the relaying peer has received a message from a peer connected to the connection indicated by the counter, block 420 . The received message includes addressing information indicating the sender of the received message. The counter indicates the connection and thus the connected peer and the addressing information of the peer. For example, peer D in Figure 1 has 3 connections, and peer D assigns numbers to each connection: peer A connects to connection 1, peer B connects to connection 2, and peer G connects to connection 3. Therefore, when the counter i is 1, peer D checks whether the received message is Sent by peer A. If the received message was sent to the relaying peer by a peer connected to the connection indicated by the counter, the relaying peer does not relay the message to this peer.

If the received message is not sent to the relaying peer by the peer connected to the connection indicated by the counter, the relaying peer determines whether the peer connected to the connection indicated by the counter is the origin of the received message peer-to-peer system, block 422. The received message includes information indicating the peer that was the origin of the received message (the peer that originally generated the data of the message, calling again the origin identifier 215 of FIG. 2 ). If the peer connected to the connection indicated by the counter is the originating peer of the received message, the relaying peer does not relay the message to that peer.

If the received message is not sent to the relaying peer by the peer connected to the connection indicated by the counter, and the peer connected to the connection indicated by the counter is not the originating peer system of the received message, then the relay The peer relays the message to the connected peer, block 425 . The relay peer builds the message for the connection shown. The relaying peer copies the received message and updates the addressing information as appropriate (eg, changing the sender to the relaying peer and changing the receiver to the connected peer connected to the indicated connection). Accordingly, the payload data remains unchanged. The relaying peer sends the constructed message to the connected peer over the indicated connection.

The relaying peer determines whether all connections have been checked, block 430 . The relaying peer compares the counter with the number of connections established by the relaying peer in the peer-to-peer relaying network. For example, the relay peer compares a counter i with the value of N (the number of connections maintained by the relay peer). If the relaying peer has checked all connections, the relaying peer completes the relaying of this received message.

If the relaying peer has not checked all connections, the relaying peer increments a counter, block 435 . For example, the relaying peer sets the counter i to i+1. After incrementing the counter, the relaying peer determines whether the relaying peer has received a received message from the peer connected to the connection indicated by the incremented counter, returning to block 420 .

As noted above, in other implementations, different, additional, or fewer relay rules may also be used. In one implementation, the relaying peer does relay the message back to the sender (eg, so the sender can confirm that the relaying peer did not change the data). In another implementation, the relaying peer does not relay the message to the peer indicated as the origin of the message (eg, as indicated by the message's origin identifier). In another implementation, the relaying peer does not relay the same message to the same connected peer again. In another implementation, the relaying peer selects a subset of available connections to relay messages, such as selecting peers with the lowest and highest response times. In another implementation, each peer relays the message to all peers' connected peers according to the hop count stored in the message, so that the message will only be relayed a certain number of times. In another implementation, peers relay the same message a limited number of times (more than once).

FIG. 5 shows a flowchart 500 of one implementation of establishing a peer-to-peer relay network. Initially, peer-to-peer systems and servers are deployed, such as peer A and server 110 in FIG. 1 . The peer-to-peer system opens a connection to the server, block 505. Peer-to-peer systems connect to servers to establish a peer-to-peer relay network (or grid), and may be referred to as "peering". The connection to the server can be a direct or indirect network connection. In one implementation, a peer is assigned to or joins and registers in one of several worlds or environments maintained by a small space or server. The server authenticates the peer before allowing the peer to interact further. The peer system submits a create grid request to the server, block 510 . The create mesh request indicates the identification information of the peer and the peer requests the server to establish a new peer-to-peer relay network. In one implementation, the request also includes conditions that the peer requests the server to apply (eg, restrictions on joining the grid). In another implementation, the request indicates the set of connection restrictions and rules (eg, relay rules and connection rules) used in the grid. The server registers the new grid, block 515. The server maintains a data table or list that keeps track of the established grids. The server creates a new table for the new grid and adds the requesting peer to the table. The server sends confirmation to the peer that the grid has been established, block 520 . The acknowledgment includes any identification or access information required for the peer to access the mesh. In one implementation, validation includes connection restrictions and rules (eg, relay rules) for the grid.

FIG. 6 shows a flowchart 600 of one implementation of connecting peers to a peer-to-peer relay network. Initially, a peer-to-peer relay network has been established by peers and servers, such as peer A and server 110 in FIG. 1 .

The peer system connects to the server, block 505. Peer systems connect to a server to join a peer-to-peer relay network (or grid), and may be referred to as "new peers" or "joining peers." The connection to the server can be a direct or indirect network connection. In one implementation, a peer is assigned to or joins and registers in a fraction of a space or one of a number of worlds or environments maintained by a server. The server authenticates the peer before allowing the peer to interact further.

The peer selects a grid from available grids at the server, block 610 . In one implementation, a peer requests a list of available grids and selects from the list. In another implementation, the server automatically provides a list of available grids when a peer connects to the server. In one implementation, the server provides a list of available grids for the world in which the peer is registered. The server may also provide additional information to aid selection (eg, which peers are already members of each grid). Peers submit grid selections to the server.

The server sends the addresses of peers that have joined the selected grid, block 615 . The address indicates how to communicate with the grid member (eg, IP address). Addresses are used to establish peer-to-peer connections with mesh members, not connections through servers. If the selected grid restricts access and does not allow new peers to join the selected grid, the server does not offer the address to the peer and is willing to let the peer choose a different grid. In one implementation, the server provides the selected mesh's connection-limiting rules along with the address to the new peer.

The new peer sends a join message to each grid member, block 620 . The join message indicates the address of the new peer and that the peer is new to the grid. In another implementation, the new peer sends a connection available message indicating the address of the peer and the number of connections available to the peer (similar to when a peer loses connection, as described below). In another implementation, the new peer sends a join message to one mesh member, and the mesh member begins relaying the join message through the mesh.

The grid members receive the join message, and each member sends a join response back to the new peer, block 625 . A join response indicates whether the responding peer has an available connection. A positive response indicates that the responding peer has an available connection. A negative response indicates that the responding peer has no connections available. The responding peer records the address of the new peer in the join message and uses that address to send the join response. The new peer receives the join response.

The new peer selects which of the mesh members to connect to, block 630 . The new peer uses the set of connection rules to select a peer for the connection. For example, in one implementation, the new peer selects a number of peers up to the mesh's connection limit from the peers that sent positive responses in the order that the new peers received positive responses (e.g., for the connection Restriction 3, the new peer selects the peer corresponding to the first three positive responses received). Different implementations may use different sets of connection rules. The new peer stores the response time of each selected peer. In another implementation, the new peer stores the response times of all responses (both positive and negative).

After selecting a peer for the connection, the new peer opens a connection to the selected peer, block 635 . The new peer sends a connection request to each of the selected peers, and the selected peers acknowledge the request, thereby opening the connection (unless the connection has become unavailable for the selected peers). Connections between peers can be direct or indirect (eg, across a network such as the Internet). In one implementation, when a peer opens a connection, each peer notifies the server of the connection.

In another implementation, the server facilitates joining the grid by forcing one or more connections. The server can cause one peer to close the connection and open a connection to another indicated peer. The server may also cause the peer to close one or more of its connections.

FIG. 7 illustrates a flowchart 700 of one implementation of selecting a peer to join a peer-to-peer relay network, such as in block 630 of FIG. 6 . Initially, the new peer has chosen the grid and sends a join message to the peers that are members of that grid. The new peer has received the join response returned from the member peer.

The new peer selects the peer corresponding to the first positive response received, block 705 . This positive response is received before other responses and indicates the fastest available connection. A new peer selection corresponds to the peer that last received a positive response, block 710 . This positive response is received after the other responses and represents the slowest connection available. To determine which response is last, the new peer waits until all responses have been received, or waits for a specified period, and then declares the last received within that period to be last. The new peer randomly selects a peer from the remaining positive responses until the new peer has selected a number of peers equal to the connection limit, block 715 . These choices support an even distribution of fast and slow connections across the mesh.

As noted above, in various implementations, different or additional connection rules may be used. In one implementation, the new peer selects the first and last positive response peers, and then selects the peers corresponding to positive responses in increasing order of response time (after first). In another implementation, new peers elect peers when responses arrive (eg, to reserve a space for the last positive response received), rather than waiting to begin peer election. In another implementation, new peers use a response time threshold to select peers (eg, peers with response times exceeding a certain limit are not selected). In another implementation, the new peer selects a peer based on the peer's characteristics (using information provided in the join response), such as storage capacity, processing speed, access level, or available functionality.

In one implementation, the peer-to-peer system classifies those connections according to a selection process used to select those connections. For example, the peer stores information indicating which open connection corresponds to the received join response with the lowest response time and which open connection corresponds to the received join response with the highest response time. As connections are adjusted for peer disconnects and new peers joining the mesh, peers may adjust the stored connection classifications.

In another implementation, the new peer uses the server to help open the connection. In one implementation, the server provides a list of grid members with available connections and the addresses of those member peers. The new peer sends a join message directly to the indicated mesh member.

If the positive response is less than the connection limit, the new peer will have connections remaining available. In one implementation, the new peer can force the other peer to close the established connection and open a connection with the new peer.

FIG. 8 shows a flowchart 800 of one implementation of forcing peers to provide connectivity for new peers in a peer-to-peer relay network. Initially, the new peer has chosen the grid and sends a join message to the peers that are members of that grid. The new peer has received the join response returned from the member peer. However, after a peer is selected for all positive responses, the new peer still has an available connection.

The new peer selects the peer corresponding to the negative response, block 805 . The new peer selects a negative response using the same connection rules used for positive responses (eg, the negative response received first according to the rules of Figure 7). Alternatively, the new peer uses a different set of mandatory connection rules. The new peer does not choose a peer to which the new peer is already connected.

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

The new peer receives the forced connection request and selects a connection to close, block 815 . Instead the receiving peer uses connection rules to choose which connections to close. For connection rules based on response time, the receiving peer uses the stored response time of the Join response (and the Connection Available response described below). In one implementation, to choose between randomly selected peers, the receiving peer selects the last selected peer, or again randomly selects a peer. In another implementation, the receiving peer uses a different set of enforced disconnection rules.

The receiving peer closes the selected connection, block 820 . The receiving peer sends a close message to peers connected to the selected connection, and both peers close the connection. Peers connected to the selected connection now have a connection available and thus issue a connection available message to the grid as described below.

The receiving peer sends an acknowledgment to the new peer, and the two peers open a new connection, block 825 . The new peer now has one less available connection. If the new peer has more available connections, the new peer repeats the process, returning to block 805 to select another negative response.

In another implementation, the new peer does not force the other peer to open a connection unless the new peer has at least two connections available. Alternatively, a different threshold (eg, 3) can be used. In another implementation, the new peer sends a force connection message when the new peer does not have at least a certain number of connections (connection cardinality).

In another implementation, the recipient peer of the force connect message may choose to decline (eg, subject to network load balancing). When rejected, the new peer chooses to send a new force-connect message to the other peer.

In another implementation, if the new peer has two or more available connections, and sends a force connection message, the new peer includes information in the message indicating that the new peer has two available connections. When the receiving peer has selected a connection to close, the receiving peer indicates to the connected peer of the selected connection (the remote peer) that another connection is available for the new peer (and includes address of the new peer). After the receiving peer has closed the connection to 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). This way, the new peer can quickly establish two connections. If the new peer still has two other available connections, the new peer may again send a force connection message indicating the two available connections to another selected receiving peer.

Each of these peers then has a connection available when a peer system disconnects from another peer system. If one (or both) of these peers is still in the mesh (i.e., not disconnected from the mesh), the peer sends a connection available message to the peer's remaining connected peers to Relays through the mesh to all other peers in the mesh.

FIG. 9 shows a flowchart 900 of one implementation of disconnecting in a peer-to-peer relay network. Initially, a peer system (a disconnected peer) is connected to at least two other peer systems in a peer-to-peer relay network.

The disconnected peer becomes disconnected from one of the peers to which the disconnected peer was originally connected, block 905 . Disconnection can occur due to voluntary disconnection by either end or a failure in the connection itself (eg, failure of part of the path between peers). Voluntary disconnection can occur, for example, when a peer determines that a connected peer is in an unresponsive state (as described below), or when a peer is forced to open a connection with a new peer (as described above) . In one implementation, the server may cause the peer to close one or more connections, resulting in a corresponding disconnect.

The disconnected peer sends a connection available message to remaining peers connected to the disconnected peer, block 910 . A connection available message indicates that a disconnected peer now has a connection available. In another implementation, the connection available message indicates the number of available connections that the peer has.

The peer connected to the disconnected peer relays the connection available message, block 915 . The peer in the mesh sends a connection available response back to the disconnected member, block 920 . A connection available response indicates whether the responding peer has a connection available. A positive response indicates that the responding peer has an available connection. A negative response indicates that the responding peer has no connections available. The responding peer records the address of the new peer in the join message and uses that address to send the join response. Alternatively, the responding peer sends the response back through the mesh to relay to the disconnected peer. A disconnected peer receives a connection available response.

The disconnected peer selects one of the mesh members to connect to, block 925 . A disconnected peer uses connection rules to choose a peer for a connection, but a disconnected peer does not choose a peer to which the disconnected peer is already connected. For example, in one implementation, the disconnected peer uses the response time of the connection-available response and the stored response times of peers still connected to the disconnected peer to select a connection to replace the lost connection. peers. Different implementations may use different sets of connection rules. The disconnected peer stores the response time of the selected peer. In another implementation, the disconnected peer stores the response times of all responses (both positive and negative). In one implementation, a disconnected peer does not select a peer from which the disconnected peer has disconnected within a certain period of time.

After selecting a peer for the connection, the disconnected peer opens a connection to the selected peer, block 930 . The disconnected peer sends a connection request to the selected peer, and the selected peer acknowledges the request, thereby opening the connection (unless the connection has become unavailable to the selected peer). Connections between peers can be direct or indirect (eg, across a network such as the Internet). In one implementation, the connected peers send an update to the server, confirming the connection.

Similar to the implementation described above with reference to Figure 8 joining the mesh, in one implementation, if a disconnected peer still has an available connection after attempting to open a connection using a connection available message (e.g., because all connection available responses were negative ), then the disconnected peer can issue a force connect message as described above.

In another implementation, a disconnected peer uses a server to help open a new connection. In one implementation, the server provides a list of mesh members with available connections and the addresses of those member peers. A disconnected peer sends a connection available message directly to the indicated mesh member.

Peer systems in the grid maintain the grid by periodically polling each other. In one implementation, connected peers periodically send messages to each other to confirm the connection and that the connected peers are still up and running.

Figure 10 shows a flowchart 1000 of one implementation of maintaining a peer-to-peer relay network. Initially, multiple peer systems are connected in a grid.

The peer sends a maintenance message to each peer connected to the peer, block 1005 . A maintenance message is a request for the receiver to provide confirmation of receipt of the maintenance message. In one implementation, the peers send Ping messages to each connected peer. The peer evaluates the received response to the maintenance message, block 1010 . The peer determines whether the response is satisfactory. In one implementation, if no response is received from the connected peer, the peer determines that the peer's connection has failed (either due to the connection or due to the connected peer). If no response is received before the time limit expires, the peer determines that the peer's connection has expired. The peer closes the connection, block 1015, of any connection it determines has failed. The peer sends a close connection request to the connected peer on the dead connection. When the peer receives the acknowledgment, the peer closes the connection. If a peer cannot communicate with a connected peer on a stale connection, or does not receive an acknowledgment within the time limit, the peer closes the connection without acknowledgment. In another implementation, the peers wait to close the connection until the connection has been indicated as dead for a period of time or multiple times. In one implementation, the peer sends an update to the server, acknowledging any closed connections.

If a peer has closed any connections, the peer voluntarily disconnects from one or more peers and issues an appropriate connection available message (eg, as described above with reference to Figure 9).

In another implementation, the peer evaluates the failed connection using the server. For example, when a peer determines that the connection has failed, the peer sends a request to the server for assistance. The server sends a message to the peer at the other end of the failed connection to confirm whether the peer is down or the connection is down. The server then notifies the peers to help open new connections or adjust the network as appropriate.

Figures 11-18 illustrate an example of one implementation for building, tuning and maintaining a grid.

In FIG. 11, a peer-to-peer system _1105A (peer A) has established a peer-to-peer relay network (mesh) 1100 using a server 1110 (the connection between peer A and server 1110 is not shown). The connection limit for this mesh is 3, therefore, peer A has 3 available connections. In FIG. 12 , a second peer system _1105B (peer B) has joined the 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 a connection.

In FIG. 13 , two other peer systems _1105C and _1105D (Peer C and Peer D) have joined the grid 1100 . Each of the four mesh member peers AD has established 3 connections with other peers in the mesh 1100 . A new peer system _1105E (Peer E) joins the grid. However, when peer E sends join messages to other peers, since each peer AD already has the maximum number of connections allowed by the connection limit of grid 1100, all join responses are negative. In Figure 14, peer E has forcefully opened the connection. Peer E chooses peer B from the negative responses (e.g., because peer E received a response from peer B first), and sends a force connect message to peer B. Peer B chooses peer D to close the connection, and closes the connection with peer D. Peer B confirms the connection with peer E, and peers B and E open a new connection. When peer B closes the connection to peer D, peer D has a connection available. Peer D sends a connection available message to peers A and C, and these peers relay the message throughout mesh 1100 . Peers A, B and C do not have an available connection, so a negative response is sent to peer D. Peer E has two available connections and sends a positive response to peer D. Peer D opens a connection with peer E. Peer E still has an available connection and therefore issues a connection available message. However, all responses were negative. Peer E has two established connections and only one connection available, so peer E does not force another connection to be opened.

In FIG. 15 , peer A disconnects from grid 1100 . Peer A is connected to each of peers B, C and D. When peer A disconnects, peers B, C and D each have available connections. Peers B, C, and D send a connection available message, and peers B, C, D, and E each send a positive response. After evaluating the response to the connection available response and eliminating the already existing connected peers, as shown in Figure 16, peers B-E establish a connection. Each of peers B-E now has 3 connections.

In Figure 17, 3 new peer systems _1105F , _1105G , and _1105H (peers F, G, and H) have joined mesh 1100 and established a connection. As part of the regular activity of maintaining the grid, peers BH each send Ping messages to their connected peers. For example, peer B pings peers D, E, and G periodically. Peer D does not provide a satisfactory response to Peer B to Peer B's Ping message (eg, the response from Peer D is too slow, or does not reach Peer B). In Figure 18, peer B has closed the connection with peer D. When peer B closes the connection, peer B and peer D have connections available. Peers B and D send out connection available messages to relay through mesh 1100 . Peer B receives positive responses from peers G and D. Peer B is already connected to peer G, so peer G will not be selected for a new connection. Peer B has just disconnected from peer D due to a dead connection, so peer D will not be selected for a new connection. Peer B has not opened a new connection (Peer B has two open connections and only one available connection, so, peer B does not try to force a connection, but in another implementation, peer B may force a connection) . Peer D receives positive responses from peers B and G. Peer B has just disconnected from peer D due to a dead connection, so peer D will not choose peer B for a new connection (or peer B will reject the new connection request). Peer D selects peer G and opens a connection to peer G.

In the example shown in Figures 11-18, the peers of grid 1100 open and close connections to build and tune the grid without relying on server 1110 to manage connections (though server 1110 does help provide new peers with the grid's address of the current member peer).

redundant list

In one implementation, peers in the mesh reduce redundant message traffic by avoiding sending messages that are determined to be redundant based on the current path in the mesh.

In this implementation, each peer in the peer-to-peer relay network stores a redundancy list. A peer's redundancy list indicates other peers to which the peer will not send messages originating from the specified peer. Accordingly, each entry in the redundancy list indicates an origin peer and a destination peer (connected to the relay peer). When a peer receives a message indicating an originating peer that is in the peer's redundancy list, the peer will not relay the message to the peer(s) already indicated by the corresponding entry in the redundancy list. Connect peers. In another implementation, the peer can toggle the redundancy list functionality on and off (eg, at the server's request, such as after determining that a security issue has arisen).

FIG. 19 shows a flowchart 1900 of one implementation of building a redundancy list in a peer-to-peer relay network. Initially, multiple peer systems are connected to form a peer-to-peer relay network. A receiving peer is connected to at least two other peers.

The receiving peer receives redundant messages from connected peers, block 1905 . Redundant messages are redundant because the receiving peer has already received the same message. The receiving peer uses the information in the received message to identify redundant messages as identical. As noted above, in some implementations, each peer maintains a list of received messages to avoid relaying the same message twice. The receiving peer can also use this list to identify redundant messages.

The receiving peer constructs a redundancy update message, block 1910 . The receiving peer includes in the redundancy update message information identifying the origin of the message and information identifying the receiving peer. For example, the receiving peer retrieves the origin identifier from the redundant message (eg, recalling the message shown in Figure 2) and stores the origin identifier in the redundant update message.

The receiving peer sends a redundancy update message to the sender of the redundancy message, block 1915 . The redundant message includes address information of the sender of the redundant message in its address information.

The sender of the redundancy message receives the redundancy update message and updates the sender's redundancy list, block 1920 . The sender retrieves from the redundancy update message information identifying the origin of the redundant message and the recipient (receiving peer) of the redundant message. The sender will add to the sender's redundancy list an entry indicating that the sender should not send messages originating from the indicated origin to the receiving peer.

For example, referring to grid 100 shown in FIG. 1, peer B receives a message originating from peer C from each of peers A, D, and E. As shown in FIG. Assuming that peer B first receives a message originating from peer C from peer A, the messages originating from peer C received from peers D and E are redundant messages. Peer B constructs a redundancy update message to send to peers D and E indicating peer C as origin and peer B as recipient. Peer B sends a redundancy update message to peer D. Peer D updates its redundancy list to instruct peer D not to relay messages originating from peer C to peer B. Peer E receives similar redundancy update messages from peer B and also updates its redundancy list in a similar manner.

As peers connect to and disconnect from the grid, the paths between clients change, so the redundancy list becomes inaccurate. Accordingly, when a peer is disconnected from the grid, the remaining peers update the redundancy list.

FIG. 20 shows a flowchart 2000 of one implementation for updating a redundancy list for a peer to be disconnected in a peer-to-peer relay network. Initially, multiple peer systems are connected to form a peer-to-peer relay network. A peer to be disconnected is connected to at least two other peers.

The peer to be disconnected is disconnected from the grid, block 2005 . Peers that were previously connected to the peer being disconnected are now disconnected peers. Each disconnected peer follows the same process below.

The disconnected peer constructs a clear redundant message, block 2010 . Clear redundant messages indicate information identifying disconnected peers. The disconnected peer sends a clear redundancy message to peers still connected to the disconnected peer, block 2015 . The peer receiving the clear redundancy message from the disconnected peer updates its redundancy list, block 2020 . A peer receiving a clear redundancy message deletes entries in the peer's redundancy list that affect relaying of messages to disconnected peers indicated by the clear redundancy message.

Returning to the example described above with reference to Figures 1 and 19, peer D has an entry in its redundancy list indicating that peer D should not relay messages originating from peer C to peer B . If Peer A disconnects from the mesh, Peer B recognizes Peer A's disconnect and constructs a Clear Redundancy message. Peer B sends a clear redundancy message to peers D and E. Peer D receives the clear redundancy message from peer B and clears peer D's redundancy list indicating that peer D should not relay messages originating from peer C to peer B entry. Accordingly, the next time peer D receives a message originating from peer C, peer D will relay the message to peer B again. Peer E updates its redundancy list in a similar manner.

multiple grids

In one implementation, a peer-to-peer system may belong to multiple peer-to-peer relay networks. Each grid can be related or independent. Connections established from each mesh can be independent. Accordingly, in one mesh, peers can be connected to one peer, while in another mesh the two peers are not connected (even if both peers are in both meshes ). In one implementation, if two peers are connected in both meshes, the two peers use a single connection. A message includes information indicating the grid to which the message belongs. The peers relay the received message according to the connection established for the message corresponding to the indicated mesh.

In one implementation, members of a peer-to-peer relay network may create subnetworks within the peer-to-peer relay network. In this case, each member of the subnetwork is also a member of the larger grid. For example, a peer-to-peer relay network includes all players in the game as a peer-to-peer system, and each team (including a subset of the total players) has a sub-network of the peer-to-peer system (eg, for private communication within the game). In this way, peers can establish a multi-channel environment to distribute and receive data as needed.

In another implementation, the peer-to-peer relay networks are independent, but share one or more member peer-to-peer systems. For example, one set of peers may set up a grid to support a lobby or chat environment, and another set of peers including at least one peer from the first set may set up a grid to support a particular game. In another example, a group of peers form a team (organization) grid, and some of them join or create other grids to play games.

For example, in an online environment, all peers in the environment are connected to a single master grid. The main grid is used for general announcements and general services. Peers create, join and leave additional smaller meshes to access online services such as chat rooms or games. Peers can use the main grid to communicate, such as when a new peer wants to join the grid (instead of using a server), until a smaller grid is established. Since all control messages can be broadcast over the main grid, each peer can independently maintain a list of available grids and a list of active peers in each grid. In one implementation, the peers do not use a centralized server.

Figure 21 shows a flowchart 2100 of one implementation for relaying messages from peer systems belonging to multiple grids. Initially, multiple peer systems are connected to form two peer-to-peer relay networks. A relay peer is a member of both meshes and has corresponding connection and relay rules for each mesh.

The relay peer receives the message, block 2105. The message includes a grid identifier indicating the grid to which the message belongs.

The relaying peer selects the mesh indicated by the received message, block 2110. Each mesh has a corresponding set of connections and a corresponding set of relay rules. By selecting the mesh, the relaying peer selects the set of connections to use and the set of relaying rules to use for relaying received messages.

The relaying peer selects a connection according to the selected grid and corresponding relaying rules, block 2115. Using the relaying rules of the selected grid, the relaying peer selects any appropriate connection for relaying the received message.

The relaying peer sends the received message to the selected peer, block 2120. Before relaying the message, the relaying peer adjusts the received message for each selected peer, such as by updating the address information of the received message to indicate that the received message is to be relayed from the relaying peer to the selected peer. peers.

audience

In one implementation, peers in the grid are classified as participants or spectators. Participant peers generate new messages to be relayed throughout the mesh. Spectator peers do not generate new messages and act as pass-through nodes in the mesh. Both participants and spectators relay messages to their connected peers according to the mesh's relay rules. In some applications, there may be many viewers for each participant. In one implementation with multiple participants, each participant has a connection to at least one other participant.

In one example, a group of participants plays an online game while spectators watch (observe data without changing game data). The number of viewers may be large (eg, thousands). Other examples include performance (eg, music), lectures, and teaching. In some applications, the load on the server for distribution does not always increase with the number of viewers, since the peers handle the distribution by relaying data.

In one implementation, when a peer joins the grid, the peer joins the grid either as a participant or as a spectator. If a peer joins the mesh as a spectator, the peer has no right to create new messages, nor to send new messages into the mesh to be relayed throughout the mesh. If a viewer generates a new message and sends the new message to a peer connected to the viewer, the peer receiving the new message from the viewer will not forward or relay the received message. In one implementation, some or all of the viewers may form another related grid as participants (eg, discussing a game being viewed in a first grid).

Figure 22 shows a flowchart 2200 of one implementation for relaying messages in a grid that supports viewers and participants. Initially, multiple peer-to-peer systems are connected to form a peer-to-peer relay network that supports participants and spectators. Each peer system stores a list of peers that are participants. In one implementation, participant peers periodically broadcast messages indicating which peers are participants. In another implementation, the server helps identify participants.

The relay peer receives the message, block 2205. The message includes an origin identifier indicating the peer that created the message.

The relay peer confirms that the origin of the received message is the participant peer, block 2210. Relay peers store a list of participant peers. The relay peer compares the peer identified as the origin of the received message to the list of participant peers. If the originating peer of the received message is not a participant (ie, is a viewer), the relaying peer does not relay the received message.

If the originating peer of the received message is a participant, the relaying peer selects a connection according to the relaying rules of the network stack, block 2215 . Using the relay rules, the relaying peer chooses any suitable connection for relaying the received message.

The relaying peer sends the received message to the selected peer, block 2220. Before relaying the message, the relaying peer adjusts the received message for each selected peer, such as by updating the address information of the received message to indicate that the received message is to be relayed from the relaying peer to the selected peer. peers.

In another implementation, the audience is not in the same grid as the participants. The audience forms a parallel audience grid linked to the participant grid. Spectators receive data from participants and relay data in the spectator grid. Links between meshes may be provided by servers or gateways, or through connections between selected peers from each mesh.

In another implementation, the viewer may be a conditional viewer. Conditional viewers can request permission to generate data to be relayed throughout the grid. If the viewer is authorized, the viewer can send a message (eg, the message includes an authorization token) that the peers in the grid will relay. Permissions may be granted by the server, by selected peers acting as mediators, or by the participant(s). For example, in a teaching environment, the participant is the lecturer, and the audience can request permission to ask questions, which will be relayed to all peers.

island recovery

In one implementation, servers and peers in the peer-to-peer relay network support adjusting connections in the mesh to avoid or recover from island formation. Isolated groups of peers in a mesh are called islands. Islands may form in the mesh when multiple peers disconnect at substantially the same time. During the disconnection process described above, the remaining peers send messages indicating available connections, however, in the event of multiple concurrent disconnections, the remaining peers may form isolated groups in the mesh. A peer on one island cannot send a message to a peer on another island because there is no peer-to-peer connection between the islands. The server detects island formation and interacts with peers to remove islands.

FIG. 23 shows a flowchart 2300 of one implementation for detecting islands in a grid. Initially, multiple peer systems are connected to form a peer-to-peer relay network or mesh. As peers open and close connections or become disconnected, the peers notify the grid's servers of the changed connections. This way, the server keeps track of all connections in the grid. The server also maintains an ordered list of peers in the grid.

The server sets the island counter, block 2305. The island counter indicates the number of islands. In one implementation, the server sets the counter i to one.

The server selects a starting peer, block 2310. When the island counter is 1, the server selects the first peer in the ordered list of peers as the initial peer. When the island counter is greater than 1, the server selects the most recently found unmarked peer as the starting peer (described below).

The server marks each peer connected to the originating peer as belonging to the same island as the originating peer, block 2315 . The server marks peers connected directly to the originating peer and indirectly connected to the originating peer through other peers (e.g., progressing from the originating peer to connected peers to those connected to peers of connected peers and so on). The server marks the peer with the current value of the island counter to indicate which island the peer belongs to.

After marking all peers connected to the originating peer, the server determines whether there are unmarked peers in the grid, block 2320 . In one implementation, the server proceeds through the ordered list of peers, searching for unmarked peers.

If the server finds an unmarked peer, the server increments the island counter, block 2325. 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 found unmarked peer as the starting peer.

If the server finds no unmarked peers, the server determines the number of detected islands, block 2330. The server has incremented the island counter for each detected island, so the island counter represents the number of detected islands. If the island counter is equal to 1, then a single island was found and, therefore, the grid was not divided into multiple islands. If the island counter is greater than 1, multiple islands were found and the grid is divided into multiple islands.

Figure 24 shows a flowchart 2400 of one implementation for deleting an island in a peer-to-peer relay network. Initially, multiple peer systems are connected in a peer-to-peer relay network or mesh. The mesh has been split into two peer islands, where peers in one island have no connection path to peers in the other island. The server detects these two islands, as by using the process shown in FIG. 23 .

The server selects peers from each island, block 2405. The server may select the first island peer and the second island peer in various ways. In one implementation, the server selects a peer with an available connection. In another implementation, the server randomly selects peers from the island.

If the first island peer does not have an available connection, the server sends a close connection message to the first island peer to close the connection, block 2410 . The first island peer receives the message from the server and selects the connection to close in the same way that the peer selects the connection to close when receiving the force connection message as described above. The first island peer closes the connection, so has a connection available.

The server sends a start force connection message to the first island peer, block 2415. The Start Forced Connection message includes the address of the second island peer. The first island peer receives the message from the server and sends a force connect message to the second island peer.

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

The first island peer sends an open connection request to the second island peer, and the two peers open the connection, block 2425 . Once the connection is made, the two islands are connected to form a single island. The peer confirms the connection by sending an update to the server. If it is detected as described above that there are still additional islands, the server returns to block 2405 to connect the other two of the remaining islands.

25 and 26 show examples of detection islands and connection islands. In FIG. 25 , grid 2500 , similar to grid 1100 in FIG. 11 , is split into two islands due to the simultaneous disconnection of peers C, G, and F. The first island includes peers A, B, D and E. The second island includes peers H, I and J. In Figure 26, the server has caused peer D to open a connection to peer I, thereby connecting the two islands.

Safety

In one implementation, the peer-to-peer relay network supports detection and recovery of fraud violations or security violations or both. Fraud violations involve the manipulation of data to alter the outcome of the processing of online activities, such as affecting the playing of a game. A security breach involves unauthorized data or improper use of data to compromise the grid or cause the grid to fail.

Figure 27 shows a flowchart 2700 of one implementation for detecting fraudulent violations in a peer-to-peer relay network. Initially, multiple peer systems are connected to form a peer-to-peer relay network or mesh.

The peer receives messages from each peer it is connected to, block 2705. As mentioned above, peers in the mesh relay messages throughout the mesh. A peer will receive the same message (same content data, but possibly different address information) over each of its connections with other peers. For example, if a peer has 3 open connections, the peer receives the same message three times from three corresponding peers. The peers identify the messages as the same message using information in the message indicating the origin and order value, such as origin identifier 215 and order value 220 as shown in message 205 of FIG. 2 . The same message from different peers will have the same origin and order information.

The peers compare the messages received from each connected peer, block 2710. The peers compare the data portions of the messages, such as data 230 shown in message 205 of FIG. 2 . The peer determines whether the data portion of the message is different for any received message. In one implementation, a peer determines that a fraud violation has occurred if the data portion of a message received from one connected peer differs from the data portion of the same message received from other connected peers. The peers also determine that the one peer that sent the message with different data is responsible for the fraud violation. Alternatively, peers use different techniques to detect fraudulent violations or identify peers responsible for fraudulent violations. When appropriate, peers do not relay messages with different data parts.

If a fraud violation occurred, the peer sends a fraud alert, block 2715. A fraud alert indicates that a fraud violation occurred and the peer responsible for the fraud violation. Peers send fraud alerts to connected peers to relay alerts throughout the mesh. In another implementation, the peer sends the fraud alert to the server for appropriate handling.

When a peer receives a fraud alert, the peer takes steps to recover from the violation, block 2720. Peers take steps to prevent rogue peers from continuing to affect grid activity. In one implementation, peers ignore messages from rogue peers. In another implementation, the peer forces the rogue peer to disconnect from the grid. Peers also take steps to remediate the effects of messages including different data, such as by sending out replacement messages with correct data as indicated by the data used in other messages to identify fraudulent messages. Alternatively, one of the peers estimates the correct data and relays the correct data throughout the network. In another implementation, the peer responds to the fraud alert by notifying the server. In this case, the server resolves the fraud violation, such as by disconnecting the peer responsible for the fraud violation.

In another implementation, when a peer sends a message, the recipient relays the message back to the sending peer. The sending peer keeps a copy of the sent message. When the sending peer receives a message back from the receiver, the sending peer compares the data of the sent message with the data of the received message. Peers detect fraudulent violations by looking for differences. The peer determines that the recipient modified the message and issues a fraud alert. In one implementation, recovery or remedial action (eg, tracked by the server) is not taken against the rogue peer until multiple violations are reported. In another implementation, this loopback check for fraud is the first layer for detecting fraud, followed by a more complex process once a possible problem is identified.

In another implementation, the peer detects fraudulent violations by comparing data in received messages with a set of predicted data generated by the peer. If the peer determines that the data in the received message differs from the data generated by the peer, the peer determines that the sender of the received message is responsible for the fraud violation and issues an alert.

In the example of detecting a fraudulent violation in 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 as identical by comparing the origin identifier with the sequence value. If peer B detects that a message from peer A has a different data part, peer B issues a fraud alert identifying peer A as fraudulent. Peer B sends a fraud alert to peers D and E (and optionally to peer A). Peers relay the fraud alert until all peers have received the alert. In response to the prompt, the peer will ignore all further messages from peer A. Therefore, peers B, C and D will no longer relay messages from peer A.

Figure 28 shows a flowchart 2800 of one implementation for detecting security violations in a peer-to-peer relay network. Initially, multiple peer systems are connected to form a peer-to-peer relay network or mesh.

The peer receives a message from one of its connected peers, block 2805. The peers analyze the message and detect security violations, block 2810. The peer determines that the message is a security violation by identifying that the message is invalid or includes invalid data. In another implementation, a peer determines that a message is a security violation by analyzing how the message was sent to the peer. For example, if a message is sent to a peer as one of a large number of repetitions of the same message (eg, as in a denial of service attack), the peer recognizes the message as a security violation. In one implementation, the message is sent as a series of packets, and the peer detects a security violation at a level below the full message, such as at the packet level. The peer also determines that the sender of the message with the security violation is responsible for the security violation. Alternatively, peers use different techniques to detect security breaches or identify peers responsible for fraudulent breaches. Peers do not relay messages or data with security violations.

If a security violation has occurred, the peer sends a security alert, block 2815. A security alert indicates that a security violation occurred and the peer responsible for the security violation. Peers send security hints to connected peers to relay hints throughout the mesh. In another implementation, the peer sends the security reminder to the server for appropriate handling.

When the peer receives the security prompt, the peer takes appropriate action to recover from the violation, block 2820 . Peers take steps to prevent a peer violating grid security from continuing to affect or compromise the grid. In one implementation, peers ignore messages from peers responsible for the security violation. In another implementation, the peer forces the peer responsible for the security violation to disconnect from the grid. The peers also take appropriate steps to repair any damage caused by the security breach. In another implementation, the peer responds to the security prompt by notifying the server. In this case, the server resolves the security violation, such as by disconnecting the peer responsible for the security violation, and takes steps to repair any damage caused to the grid.

Figures 29 and 30 show block diagrams of one implementation of the server 2905 and the peer-to-peer system 3005, respectively. In other implementations, the server or peer includes fewer components than shown in FIGS. 29 and 30 , or includes different or additional components.

The server 2905 operates as described above and includes components that provide the functionality described above, including for building the grid 2910, adding peers 2915, connecting peers 2920, disconnecting peers 2925, maintaining the grid 2930, storing and generating Grid data (e.g. connections, members, connection limits) and rules (e.g. relay rules, connection rules) 2935, manage multiple realms 2940, manage and help with redundancy lists 2940, manage multiple grids 2950, Manage spectators and participants in the grid 2955, handle island detection and recovery 2960, manage and resolve fraud and security breaches 2965, and server's central services 2970 (e.g., network communication and addressing, player matchmaking, chat functionality, data backup, etc. )s component.

The peer-to-peer system 3005 operates as described above and includes components that provide the functionality described above, including for establishing a grid 3010, joining a grid 3015, connecting a peer 3020, disconnecting a peer 3025, maintaining the grid 3030, Store and generate grid data (e.g., connections, members, connection limits) and rules (e.g., relay rules, join rules) 3035, build, update and use redundancy lists 3040, operate in multiple grids 3045, pass and operate as spectators and participants in the grid 3050, handle island detection and recovery 3055, manage, detect and resolve fraud and security breaches 3060, and peer-to-peer system services 3065 (e.g., network communication and addressing, player matching, chat functions, data backup, etc.).

Various implementations of peer-to-peer relay networks provide desired benefits. Grids are useful in several network applications, including massively multiplayer computer online games. An online gaming application is just one example of a larger group of web applications that have one thing in common: sharing and maintaining a common data set. When a dataset is updated on one peer, the information is sent to other groups of peers and relayed throughout the mesh, so each peer will have the updated dataset. A relay mesh allows connected peers with limited network bandwidth to exchange data between them without going through a central server. This network can be used to exchange game data, other game related information, media files, streaming audio or streaming video.

For example, in one implementation, peers use a grid for file distribution. Peers in the grid publish the file (either as one message or split into multiple messages) by sending the file to peers connected to the publisher, and member peers throughout the grid relay the file to all members. In this way, all members of the grid can receive published files without using a server and without using a direct connection from the publishing peer to each peer. In various implementations, any type of file may be published. Files can be data, media, or executable software applications. Examples of files published through the grid include, but are not limited to: streaming media (e.g., audio and/or video), media files, replay data from games or other applications, maps, announcements, messages, application data, and modules (e.g. , maps, templates, structures, sounds).

Various implementations of the invention are realized in electronic hardware, computer software, or a combination of these technologies. Most implementations include one or more computer programs executed by programmable computers. For example, in one implementation, each peer-to-peer system and server includes one or more computers executing software for implementing the functionality of the peer-to-peer relay network. Typically, each computer includes one or more processors, one or more data storage components (e.g., volatile or nonvolatile memory modules, and permanent optical and magnetic storage devices such as hard and floppy disk drives, CD-ROM drive and tape drive), one or more input devices (such as a mouse and keyboard), and one or more output devices (such as a display console and a printer).

A computer program consists of executable code which is usually stored on a permanent storage medium and then copied into memory at runtime. The processor executes code by fetching program instructions from memory in a prescribed order. When executing program code, a computer receives data from input and/or storage devices, performs operations on the data and then provides the resulting data to output and/or storage devices.

Various illustrative implementations of the invention are described. However, those skilled in the art will appreciate that additional implementations are possible and within the scope of the invention. For example, while the above description describes several implementations of peer-to-peer relay networks discussed in the context of supporting gaming applications, other applications are possible, such as file sharing or other data distribution applications.

Therefore, the present invention is not limited to those implementations described above.

Claims (18)

1. support a plurality of peer-to-peer relay network of networks for one kind, comprising:

Main peer-to-peer relay network; Said main peer-to-peer relay network comprises all peer systems in said a plurality of peer-to-peer relay network; Said main peer-to-peer relay network has sub-network in said main peer-to-peer relay network; Wherein, each peer system of sub-network also is the member of said main peer-to-peer relay network;

The first peer-to-peer relay network that comprises a plurality of first peer systems, said a plurality of first peer systems are first sub-networks of said main peer-to-peer relay network, and the said first peer-to-peer relay network comprises the first particular peer system and the second particular peer system; And

The second peer-to-peer relay network that comprises a plurality of second peer systems, said a plurality of second peer systems are second sub-networks of said main peer-to-peer relay network, and the said second peer-to-peer relay network comprises said first particular peer system and the said second particular peer system,

Wherein, In the said first peer-to-peer relay network, the said first particular peer system has to the connection of the said second particular peer system, and in the said second peer-to-peer relay network; The connection that the said first particular peer system does not arrive the said second particular peer system

Wherein, the message that the peer-to-peer from the said first peer-to-peer relay network is addressed to another peer-to-peer in the said first peer-to-peer relay network is the private communication that only is relayed to the peer-to-peer in the said first peer-to-peer relay network, and

Wherein, be relayed to all peer-to-peers in the said main peer-to-peer relay network setting up the message that the peer-to-peer from the said first peer-to-peer relay network before said first sub-network is addressed to the peer-to-peer in the said main peer-to-peer relay network.

2. a plurality of peer-to-peer relay network of networks of support as claimed in claim 1 also comprise:

Be connected to the server of each peer system.

3. a plurality of peer-to-peer relay network of networks of support as claimed in claim 1, wherein:

Peer system in the said first peer-to-peer relay network is represented the player in the game on line.

4. a plurality of peer-to-peer relay network of networks of support as claimed in claim 3, wherein:

Peer system in the said first peer-to-peer relay network is illustrated in the player of same team in the said game on line.

5. a plurality of peer-to-peer relay network of networks of support as claimed in claim 1, wherein:

The data of relaying are network service datas in the said first peer-to-peer relay network.

6. a plurality of peer-to-peer relay network of networks of support as claimed in claim 1, wherein:

The data of relaying are the data that are used for online environment in the said first peer-to-peer relay network.

7. a plurality of peer-to-peer relay network of networks of support as claimed in claim 6, wherein:

The data of relaying are the data that are used for the hall environment in the said first peer-to-peer relay network.

8. a plurality of peer-to-peer relay network of networks of support as claimed in claim 7, wherein:

The data of relaying are the data that are used for environment chatroom, said hall in the said first peer-to-peer relay network.

9. a plurality of peer-to-peer relay network of networks of support as claimed in claim 6, wherein:

The data of relaying are the data that are used for game on line in the said first peer-to-peer relay network.

10. a plurality of peer-to-peer relay network of networks of support as claimed in claim 1 also comprise:

Another peer-to-peer relay network that comprises a plurality of peer systems;

Wherein, each peer system in said another peer-to-peer relay network is connected to a plurality of other peer systems that are less than or equal to the 3rd connection restriction in said another peer-to-peer relay network,

And

Wherein, in said another peer-to-peer relay network at least one peer system also in the said first peer-to-peer relay network.

11. a plurality of peer-to-peer relay network of networks of support as claimed in claim 10, wherein:

All peer systems in said another peer-to-peer relay network are not all in the said first peer-to-peer relay network.

12. a plurality of peer-to-peer relay network of networks of support as claimed in claim 1, wherein:

At least one peer system is the game console of launching network.

13. a plurality of peer-to-peer relay network of networks of support as claimed in claim 1, wherein:

At least two peer systems connect through the internet.

14. the method for a relay data in the peer-to-peer relay network comprises:

Foundation comprises the main peer-to-peer relay network of all peer systems in the said peer-to-peer relay network; Said main peer-to-peer relay network has sub-network in said main peer-to-peer relay network; Wherein, each peer system of sub-network also is the member of said main peer-to-peer relay network;

Foundation comprises the first peer-to-peer relay network of a plurality of first peer systems, and said a plurality of first peer systems are first sub-networks of said main peer-to-peer relay network, and the said first peer-to-peer relay network comprises the first particular peer system and the second particular peer system;

Foundation comprises the second peer-to-peer relay network of a plurality of second peer systems; Said a plurality of second peer system is second sub-network of said main peer-to-peer relay network; The said second peer-to-peer relay network comprises said first particular peer system and the said second particular peer system

Wherein, In the said first peer-to-peer relay network, the said first particular peer system has to the connection of the said second particular peer system, and in the said second peer-to-peer relay network; The connection that the said first particular peer system does not arrive the said second particular peer system

Wherein, the message that the peer-to-peer from the said first peer-to-peer relay network is addressed to another peer-to-peer in the said first peer-to-peer relay network is the private communication that only is relayed to the peer-to-peer in the said first peer-to-peer relay network, and

Wherein, be relayed to all peer-to-peers in the said main peer-to-peer relay network setting up the message that the peer-to-peer from the said first peer-to-peer relay network before said first sub-network is addressed to the peer-to-peer in the said main peer-to-peer relay network.

15. method as claimed in claim 14, wherein:

For each the peer-to-peer relay network under the said peer system, the corresponding corresponding set that connects restriction and form of said peer system storage by one or more relaying rule,

The maximum quantity of other peer system that connection restriction qualification permission peer system is connected in this peer-to-peer relay network, and

How the set regulation peer system of being made up of one or more relaying rule is relayed to other peer system that is connected to this peer system in this peer-to-peer relay network with data.

16. the peer system in the peer-to-peer relay network comprises:

Be used for setting up the parts of the main peer-to-peer relay network of all peer systems that comprise said peer-to-peer relay network; Said main peer-to-peer relay network has sub-network in said main peer-to-peer relay network; Wherein, each peer system of sub-network also is the member of said main peer-to-peer relay network;

Be used to set up the parts of the first peer-to-peer relay network that comprises a plurality of first peer systems; Said a plurality of first peer system is first sub-network of said main peer-to-peer relay network, and the said first peer-to-peer relay network comprises the first particular peer system and the second particular peer system; And

Be used to set up the parts of the second peer-to-peer relay network that comprises a plurality of second peer systems; Said a plurality of second peer system is second sub-network of said main peer-to-peer relay network; The said second peer-to-peer relay network comprises said first particular peer system and the said second particular peer system

Wherein, In the said first peer-to-peer relay network, the said first particular peer system has to the connection of the said second particular peer system, and in the said second peer-to-peer relay network; The connection that the said first particular peer system does not arrive the said second particular peer system

Wherein, the message that the peer-to-peer from the said first peer-to-peer relay network is addressed to another peer-to-peer in the said first peer-to-peer relay network is the private communication that only is relayed to the peer-to-peer in the said first peer-to-peer relay network, and

Wherein, be relayed to all peer-to-peers in the said main peer-to-peer relay network setting up the message that the peer-to-peer from the said first peer-to-peer relay network before said first sub-network is addressed to the peer-to-peer in the said main peer-to-peer relay network.

17. peer system as claimed in claim 16, wherein:

Said peer system in two or more peer-to-peer relay networks, and

For each the peer-to-peer relay network under the said peer system, said peer system has by one or more corresponding set that connects to form to other peer system.

18. peer system as claimed in claim 16, wherein:

For each the peer-to-peer relay network under the said peer system, the corresponding corresponding set that connects restriction and form of said peer system storage by one or more relaying rule,

The maximum quantity of other peer system that connection restriction qualification permission peer system is connected in this peer-to-peer relay network, and

How the set regulation peer system of being made up of one or more relaying rule is relayed to other peer system that is connected to this peer system in this peer-to-peer relay network with data.

Images