Method for host selection based on discovered nat type

[Cross-reference of related applications] This application relates to US Patent Application No. 12 / 049,954 by the same applicant entitled "Systems and Methods for Seamless Host Migration" by Mark Resta Jacob et al., Filed on the same day as this application. The entire content is incorporated here by reference. This application is also related to US Provisional Patent Application No. 60 / 997,918, entitled "Systems and Methods for Seamless Host Migration," filed October 5, 2007, the disclosure of which is incorporated herein by reference. ..

This application is related to US Patent Application Gazette No. 20070076729, entitled "Peer-to-Peer Communication Through Symmetric Network Address Translators" by Yutaka Takeda et al., Filed October 4, 2005, with reference to its entire contents. Incorporate here.

[Technical field] The present invention relates to a computer network, and more particularly to determining a host for peer-to-peer communication between clients of the computer network.

Currently, while playing a game between clients on a computer network, the clients communicate directly with the server. The central server processes data from any client and relays this data to all other clients. This allows clients on the network to engage with each other in gameplay through a central server. The ability of the central server to communicate data between clients is limited by bandwidth. Therefore, communication outside the gameplay is restricted.

<p> Apart from gameplay data, clients may also want to communicate with each other without going through a bandwidth-limited central server. Examples of such communications include voice over Internet protocol (VoIP), bit torrents, video data, file sharing, and data streaming. By allowing clients to communicate with each other without the need for a central server, some of the central server's responsibilities can be offloaded to the client.</p><p> A peer-to-peer network is built when a host is determined from a large number of clients participating in a P2P network. The host takes on the task of a central server and manages communication between clients (hereinafter referred to as peers when referring to non-host clients in a P2P network).</p><p> Embodiments of the present invention have been considered in this context.</p>

<p> One aspect of the invention is a method in one peer for determining which of two or more peers should be designated as a host for services in a peer-to-peer grid. This method includes a) collecting NAT profile information for the one peer, and b) sharing NAT profile information for the one peer with one or more of the two or more peers. c) From the step of receiving the NAT profile information for the one or more other peers and d) the NAT profile information for the one peer and the NAT profile information for the one or more other peers, the two or more peers. Includes a step to determine which of the above is designated as the host.</p>

<figref num="1">It is the schematic which illustrates the P2P network which concerns on embodiment of this invention.</figref><figref num="2">It is a flowchart explaining a method of selecting a host based on a discovered NAT type from the viewpoint of a client.</figref><figref num="3">It is a flowchart explaining the basic method of host selection based on the discovered NAT type from the viewpoint of the client.</figref><figref num="4">It is the schematic explaining an example of the client interface which concerns on embodiment of this invention.</figref>

[introduction] One problem that arises when trying to build communication between clients through peer-to-peer (P2P) communication is the problem of network address translation (NAT). Clients connected to the central server are usually located behind NAT. By using NAT, a local area network (LAN) uses a set of private IP addresses (first set) for internal traffic and a set of global IP addresses (second set) for external traffic. It will be possible to use it. Therefore, it is desirable for hosts in the P2P network to have a preferred NAT profile in order to generate the optimal P2P network.

For this reason, there is a technical need for a way to determine which host has the desired NAT profile from among the clients connected to the central server.

The following four NAT types are available. Full cone NAT, restricted cone NAT, port restricted cone NAT, and symmetric NAT. Full-cone NAT maps all requests from the same internal IP address and port to the same external IP address and port. In addition, any external host can send a packet to an internal host by sending the packet to a mapped external address.

With restricted cone NAT, all requests from the same internal IP address and port are mapped to the same external IP address and port. However, unlike full-cone NAT, an external host (with IP address X) can send packets to an internal host only if the internal host has previously sent packets to that IP address X. Be done.

Port-restricted cone NAT is similar to restricted-cone NAT, but the restrictions include the port number. Specifically, an external client can send a packet with a source IP address X and a source port P to an internal host because the internal host has previously sent a packet from that IP address X and port P. Only in cases.

Symmetric NAT maps all requests from the same internal IP address and port to a particular destination IP address and port to the same external IP address and port. If the same host sends packets with the same source address and port but different destinations, different mappings will be used. In addition, only the external host that receives the packet can send the UDP packet back to the internal host.

[Host selection based on NAT type] FIG. 1 is a schematic diagram illustrating a P2P network according to an embodiment of the present invention. Client devices 105A, 105B, 107, and 105D on the network are initially connected to server 101 on the external network 109. As an example, server 101 may monitor gameplay data exchanged between clients 105A, 105B, 107, and 105D connected to external network 109. Clients 105A, 105B, 107, and 105D have corresponding NAT (network addresses). translator) 111A, 111B, 111C, and 111D are placed after. Each NAT is configured according to Internet standards, where the local area network (LAN) uses a set of private IP addresses (first set) for internal traffic and a global IP address for external traffic. Allows you to use a set of (second set). Most NATs dynamically translate IP addresses, so there is no way for the external network to reach the internal network before the internal network begins communicating. However, because clients 105A, 105B, 107, and 105D build a server-client relationship, communication between server 101 and clients 105A, 105B, 107, and 105D is restricted by NAT111A, 111B, 111C, and 111D. There is nothing.

When building a P2P network where clients can communicate directly with each other, one client is built as host 107, and through host 107, the other peer 105 (clients connected to the P2P network, not hosts) You can build a direct connection to each other. As an example, but not limited to, peers 105 may be connected to each other in a configuration known as a fully connected grid (FCG). Such a configuration can prevent any one peer from becoming a bottleneck. In embodiments of the present invention, the host 107 can be determined based on the NAT profile of each client. NAT111A, 111B, 111C, and 111D may be one of four different configurations commonly referred to as full cone NAT, restricted cone NAT, port restricted cone NAT, and symmetric NAT.

Full-cone NAT maps all requests from the same internal IP address and port to the same external IP address and port. Any client can send a packet to that client by sending the packet to an external address for the client located behind the full-cone NAT.

With restricted cone NAT, all requests from the same internal IP address and port are mapped to the same external IP address and port. However, unlike full-cone NAT, an external client (with IP address X) can send a packet to a client behind full-cone NAT because the internal host previously sent a packet to that IP address X. Only if there is.

Port-restricted cone NAT is similar to restricted-cone NAT, but the restrictions include the port number. Specifically, an external client can send a packet with source IP address X and source port P to a client behind a port-restricted cone NAT by a client behind the port-restricted cone NAT. Only if you have previously sent packets from that IP address X and port P.

Symmetric NAT maps all requests from the same internal IP address and port to a particular destination IP address and port to the same external IP address and port. If the same host sends packets with the same source address and port but different destinations, different mappings will be used. In addition, only the external host that receives the packet can send the UDP packet back to the internal host.

Traversal of full cone, restricted cone, and port restricted cone NAT is relatively easy, but the passage of symmetric NAT is somewhat complicated. NAT passage when the client is after the symmetric NAT is described, for example, in US Patent Application Publication No. 20070076729, which the applicants have in common. In particular, the client may perform port prediction. Port prediction involves generating a list of predicted transport addresses for a NAT that has a client in the latter part. The client behind the symmetric NAT then performs a connectivity check with the second node using the predicted transport address. Connectivity check is STUN (simple traversal of user data protocol (UDP) through) Performed by sending NAT) requests in parallel to each predicted transport address. When the client behind Symmetric NAT receives this request, it sends a STUN response to a second client. If the second client receives the STUN response, the second client can start sending media to that address.

NAT types other than the above four may be provided. In some cases, standard techniques can be used to pass such NAT. In other cases, communication with clients behind such NAT may be unreliable because the behavior of NAT is unpredictable or unstable.

Since the mission of host 107 is to communicate information between other peers 105A, 105B, and 105D, it is important that host 107 is behind a type of NAT that does not interfere with communication capabilities. .. In an embodiment in which peers 105A, 105B, 105D and host 107 are joined by a fully connected grid (FCG), the communication capability is not disturbed so that the highest level of service can be provided to the maximum number of peers. It is especially preferable to utilize the host behind NAT. In reality, NAT with questionable (unknown) support for P2P may work well compared to other NAT types used by existing peers in P2P networks. By selecting the host 107 having the most preferable NAT profile, more reliable peer-to-peer communication can be realized. Here, the term P2P communication refers to direct communication between client devices connected to a network. Examples of P2P applications are not limited to those listed here, but for example, VoIP (voice over internet). Some are protocol, bit torrent transfers, video transfers, file shares, data shares, and other types of direct data transfers between clients that do not exceed the bandwidth capacity of individual clients. Once host 107 is established, peers 105A, 105B, and 105D communicate with each other by first transferring information to host 107, and host 107 relaying that information to peers 105A, 105B, and 105D at their respective recipients. be able to. Alternatively, these peers may transfer information directly after utilizing host 107 to establish this direct communication path.

In certain embodiments, clients 105A, 105B, 105D, and 107 may obtain NAT profile information using STUN associated with external network 109. STUN Server 103 is a lightweight protocol proposed by the IETF that allows IP-enabled clients to discover the presence and type of NAT in front of them. STUN103 works with most NAT types and does not depend on any particular NAT behavior. The STUN server 103 acts like a mirror leaning against client 105A, which allows client 105A to see how its local transport address maps to the public transport address. Client 105A can also determine the type of NAT111A in front of client 105A through communication with STUN server 103.

As an example, although not limited to the examples given here, each client 105A, 105B, 107, 105D may acquire NAT profile information using a STUN server and relay the information to the central server 101. This allows the central server 101 to determine which client could be the most preferred host 107. Similarly, one of the clients 105A, 105B, 107, 105D uses the STUN server 103 to obtain the other NAT profile information and relays that information to the other client 105 trying to communicate over the P2P network. You may. This allows clients 105A, 105B, 107 and 105D to optimally determine host 107.

FIG. 2 is a flowchart illustrating the basic method of selecting a host based on the discovered NAT type from the client's point of view. As shown in step 201, each client connected to server 101 collects its own NAT profile information for use in the P2P network. This profile information includes information about the type of NAT in front of the client, whether the NAT supports UPnP (universal plug and play), and whether the NAT offers port protection. , And information about whether the NAT supports port predictability. Here, port protection means that an internal IP address once mapped to a specific external port is consistently mapped to that specific port. Port predictability here means that the external port to which the internal IP address is mapped can be predicted, even if it is not always the same port. For example, the external port may be incremented consistently with each attempt to map the internal IP address.

In addition to NAT behavior, each client's profile information also includes quality of service (QoS) information. The term QoS information here includes information about a client and how well the client device can communicate with other client devices. As an example, but not limited to those listed here, such information can be used to determine how fast the client can communicate, whether the client can communicate so reliably, or theirs. It's about both. Specific examples of QoS information include, but are not limited to, ping times, bandwidth behavior, latency, geography, IP providers, and so on.

The profile information for each client can also be used to create a priority list among all clients connected to the server. This makes it possible to optimally select a host for P2P communication. If the priorities among the potential hosts are the same, ordinal numbers may be set to determine which potential host is selected as the real host. In certain embodiments, such ordinals may be assigned by the server in step 203. For example, in the order in which clients are connected to the server. Alternatively, a distributed arbitration algorithm may be used to select one of two or more equally suitable potential hosts. If the first host decides to leave the P2P network, or if the P2P network is disconnected for any reason, this information is used to select the next host for the P2P network.

Once profile information is collected by a given client, the NAT profile for that client is shared with other clients connected to the server. The profile information includes the expected number of clients connected to the server. This is used to determine if optimal P2P has been reached. At this point, each client waits for all other clients to submit profile information about the NAT in front of them, as shown in step 205. Once all NAT profiles have been submitted by the client, the client determines whether it can host, peer, or meet the requirements to be either, as shown in step 207. This decision is made based on the profile information acquired for each of the clients described above. For example, by assigning priorities based on many factors, a host can be selected from among the available clients based on the client with the most favorable profile. The rest of the clients are assigned to peers or are not recognized as peers or hosts based on their profile information. For example, a client behind a NAT that is not passable does not meet the requirements to connect to the network as a peer or host. As an example, but not limited to the examples described here, a client that cannot be recognized as a peer or host updates its profile, notifies the rest of the P2P network of its status, and from the P2P network. The expected count may be decremented so that this client is excluded.

Table 1 describes an example of a prioritization scheme that can be used to determine host allocation in a P2P network. As an example, but not limited to, prioritization schemes can be divided into five separate compartments. There are five: active, possible, unknown, ongoing, and inactive. These are listed in Table 1 in order of host priority. The "active" tag indicates that the client is a very good candidate for hosting. The "possible" tag indicates that the client is a good candidate for the host, but the client with the active tag takes precedence. The "unknown" tag indicates that the network cannot determine if that particular client is a good candidate for a host. The "in progress" tag indicates that the network is still deciding whether the client is a good candidate for a host. Finally, the "inactive" tag indicates that the client cannot take on the host's duties. In the example shown in Table 1, priority tags are based on four criteria. There are four types: NAT type, UPnP function, port protection, and port predictability. However, some other factors may be used in determining priorities. These factors fall within the client's quality of service profile and may include QoS information including, but not limited to, ping time, bandwidth behavior, geography, latency, and IP providers.

<tables num="1"><img file="JP2010244509A_D0001.tif" /></tables>

FIG. 3 is a flowchart illustrating a method of host selection based on the discovered NAT type according to a particular embodiment of the present invention from the client's point of view. As shown in step 301, the client first gets profile information about the NAT in front of it. This profile information includes information about the NAT type, whether NAT supports UPnP, whether NAT supports port protection, and whether NAT supports port reservability. In addition to this information, the profile information may include QoS information including, but not limited to, ping time, bandwidth behavior, geography, latency, and IP provider. This information is used to prioritize between these several different clients to determine which host to support P2P communication. If the first host decides to leave the P2P network or is disconnected from the network for some reason, this information can be used to select the next host for the P2P network.

Once the client gets profile information about the NAT in front of it, the client shares this NAT profile with other clients connected to the same server, as shown in step 303. These clients are now informed not only about the profile information mentioned above for all other clients, but also about the expected count value of the clients currently connected to the server. At this point, each client waits for all other clients to provide their profile information about the NAT in front of them, as shown in step 305. Once all NAT profiles have been submitted by the client, the client determines whether it can host, peer, or meet the requirements to be either, as shown in step 307. This decision is made based on the profile information acquired for each of the clients described above. By assigning priorities based on many factors, it is possible to select a host from among clients based on the client with the most favorable profile. The rest of the clients are assigned to peers or are not recognized as peers or hosts based on their profile information. For example, a client behind a NAT that is not passable does not meet the requirements to connect to the network as a peer or host. As an example, but not limited to the examples described here, a client that cannot be recognized as a peer or host updates its profile, notifies the rest of the P2P network of its status, and from the P2P network. The expected count may be decremented so that this client is excluded.

The client assigned the host mission waits for the remaining clients on the network to connect and updates the profile, as shown in step 309. Once all clients have connected to the host, check the expected count to determine if all clients connected to the server have connected to the host, as shown in step 311. If the count is as expected, P2P communication is possible, as shown in step 317. However, if the count is less than expected because one or more clients did not meet the requirements to become a host or peer, the count is decremented and processing starts again at 303.

If the client decides to be a peer, the client attempts to connect to that host after it has been determined, as shown in step 313. As shown in step 315, it is determined whether the peer can connect to the host or not. If the client can connect to the host, the client waits for all other peers to connect to the host before P2P communication is possible, as shown in step 317. If the client cannot connect to the host, the client's profile information is updated and the process begins again at step 303. Eventually, if the client fails to connect to the host multiple times, the count is decremented and the client leaves the P2P network.

If a peer fails to become a peer while collecting NAT information, this is recorded as a failure and shared with other peers. You may assume that data sharing and waiting for data will not fail. For example, if this data communication is made through a reliable communication channel such as server 101, such an assumption holds. If communication with the server 101 fails at some point in this process, the entire process is aborted and the rest of the clients are notified that the connection has been lost. This notification is identified by the protocol used to communicate with the server 101. The rest of the clients no longer wait for a response from the disconnected client.

Once a host is identified from among client devices, Server 101 offloads one or more features to the P2P grid managed by the peer appointed to that host. The host and / or any peer in the P2P grid undertakes such functionality. As an example, but not limited to this, the P2P grid may be a fully coupled grid or star topology in which all communication goes through the host. The grid topology is not strictly relevant to the embodiments of the present invention. Relevant is that the key points (hosts) of communication to the P2P grid of any topology are built on the NAT behavior associated with that key point of communication.

As shown in FIG. 4, the client device 400 is configured to implement the host determination method according to the embodiment of the present invention. As an example, without compromising generality, the client device 400 is a mobile or handheld device such as a digital television set, personal computer, video game machine, personal digital information device, mobile phone or personal digital device, handheld video game machine. Implemented as part of a portable e-mail device, or other digital device.

The device 400 includes a central processing unit (CPU) 402 and a memory 404 connected to the CPU 402. The CPU 402 is configured to run software applications and optionally an operating system. One embodiment of the invention utilizes a type of processor architecture in which the CPU 402 includes a main processor 402A and one or more auxiliary processors 402B. Each auxiliary processor 402B now has its own associated local data storage. An example of such a processor architecture is a cell processor. An example of a cell processor architecture is described in detail in "Cell Broadband Engine Architecture". It is copyrighted by IBM, Sony Computer Entertainment, and Toshiba on August 8, 2005, and a copy can be downloaded from http://cell.scei.co.jp/. The whole is incorporated here by reference.

With reference to FIG. 4 again, the receiving device 400 is also equipped with known support functions 410 such as input / output (I / O) device 411, power supply (P / S) 412, clock (CLK) 413 and cache 414. May be good. The device 400 may further include a high speed data storage device 415, such as a hard disk drive, which provides non-volatile storage for applications and data. As an example, the storage device 415 may be a fixed disk drive, a removable disk drive, a flash memory device, or a tape drive. Alternatively, the storage device 415 may be, for example, a CD-ROM, DVD-ROM, Blu-ray (trademark or registered trademark), HD-DVD, UMD, or other optical storage device. The file 416 from the slower storage device may be temporarily stored in the faster storage device and used as a hardware cache for fast loading into memory 404.

One or more user input devices 420 may be used to convey user input from one or more users to the system 400. For example, one or more user input devices 420 may be connected to the client device 400 via the input / output device 411. Examples of suitable input devices 420 include keyboards, mice, joysticks, touchpads, touch screens, remote control units, light pens, still / video cameras, and / or microphones.

The client device 400 can communicate with other client devices in the peer-to-peer network through network interface 425, which aids in communication over the electronic communication network 427. Network interface 425 may be configured to implement wired or wireless communication over local area networks and wide area networks such as the Internet. System 400 can use one or more message packets 426 on network 427 to send and receive requests for data and / or files. As an example, but not limited to, the electronic communication network 427 is a local area network, wide area network, or personal area network (eg, Bluetooth®) that allows the device 400 and other clients to communicate between berths. Alternatively, it may be a registered trademark)).

The memory 404 stores the applications and data used by the CPU 402. The memory 404 may be in the form of an integrated circuit (eg, RAM, DRAM, ROM, etc.). The computer program 401 is stored in memory 404 in the form of instructions that can be executed by processor 402.

Program 401, when executed by the processor, includes instructions that cause the processor to implement a method for determining a host from a group of two or more peer-to-peer device devices in a peer-to-peer network. As an example, without loss of generality, program 401 may have device 400 implement method 200 illustrated in FIG. 2 or method 300 illustrated in FIG. 3 at run time. In particular, program 401 may cause device 400 to do the following: a) Collect NAT profile information for device 400, b) Share NAT profile information for that device with one or more other client devices 400', 400'' connected to network 427, c) One or more others Receives NAT profile information for the client device of d) From the NAT profile information for the client device 400 and the NAT profile information for one or more other client devices, any of the client devices 400, 400', 400'' Decide if you want to specify it as a host.

NAT profile information 406 for client device 400 and other client devices 400', 400'' is stored in memory 404 and used when determining the host. Each of the client devices 400, 400', 400'' is behind the corresponding NAT403, 403', 403''. The client device 400 is located behind the NAT403, which translates the internal IP address for the client 400 into a public IP address that can be seen by other devices. While some types of client devices may contain NAT, NAT403 is usually not part of client device 400. Moreover, embodiments of the present invention cannot be implemented unless any or all of the client devices 400, 400', 400'' are behind NAT.

NAT profile information 406 maintains information about the type of NAT behind (if any) the client device 400 behind it, the ability of that NAT to engage in UPnP, and port protection, but not limited to those listed here. Includes the ability of NAT to do, and the port predictability of NAT. Program 401 implements the selection based on the above criteria for Table 1. Other client devices 400', 400'' are configured in the same way and implement the same host selection process. If all client devices 400, 400', 400'' use the same program 401 and profile information 406, it makes sense to expect them to make the same host decision.

In some situations, program 401 applies an auxiliary arbitration filter based on additional information 408, such as quality of service (QoS) information, and hosts the host device from among two or more equally promising candidate devices. It is desirable to mediate the decision to choose. The quality of service information may include factors such as client ping time, bandwidth behavior, geography, latency, IP provider, and other factors mentioned above. Such additional information 408 can also be stored in the memory 404.

The client device 400 further includes a graphics subsystem 430 with a graphics processing unit (GPU) 435 and graphics memory 437. The graphics memory 437 includes a display memory (eg, a frame buffer) used to store pixel data for each pixel of the output image. The graphics memory 437 may be integrated in the same device as the GPU 435, may be coupled to the GPU 435 as a separate device, or may be implemented in the memory 404. Pixel data is provided directly from CPU 402 to graphics memory 437. Alternatively, the CPU 402 provides the GPU 435 with data and instructions that determine the desired output image. GPU435 uses it to generate pixel data for the output image. Data and instructions that determine the desired output image are stored in memory 406 and graphics memory 437. In certain embodiments, the GPU435 is configured with, for example, appropriate programming or hardware configuration, an instruction that defines geometry, lighting, shading, texturing, motion, and / or camera parameters for the scene. It has a 3D rendering function to generate pixel data for the output image from the data. GPU435 also includes a programmable execution unit capable of executing shader programs.

The graphics subsystem 430 periodically outputs pixel data for an image from the graphics memory 437 that should be displayed on the video display device 450. The video display device 450 is any device capable of displaying visual information in response to a signal from the device 400 and is a CRT, LCD, plasma, and OLED display capable of displaying text, numbers, graphical symbols, or images. including. The digital broadcast receiving device 400 provides the display device 450 with an analog or digital signal depending on the type of display device. In addition, the display 450 may be reinforced with audio speakers that produce audible or detectable sound. To facilitate the generation of such sounds, the client device 400 is suitable for generating analog or digital audio output from the instructions and / or data provided by the CPU 402, memory 404, and / or storage 415. It also includes an audio processor 455.

The receiving device 400 may optionally include a location display device 470. Such devices are based on any suitable technique capable of providing information about the geographical location of the device. Examples of existing technologies include GPS technology and inertial guidance technology. Information from such devices is used in digital broadcast data applications such as navigation for mobile or handheld devices.

According to one embodiment, it is useful to determine the geographic location of the client device 400. QoS considerations such as bandwidth, ping time, and latency can be affected by device location. As an example, but not limited to this, the location display device 470 provides geographic location information to facilitate host determination, and program 401 uses that information to allow the client device 400 to peer-to-peer. You may decide if you are a good candidate to host the service.

The components of device 400, including CPU 402, memory 404, support function 410, data storage device 415, user input device 420, network interface 425, graphics unit 430, audio processor 455, and location display device 470, make up the data bus 460. They are functionally connected to each other via. These components are implemented in hardware, software or firmware, or a combination of two or more of them.

Embodiments of the present invention allow coordinated host determination and host migration in the context of peer-to-peer networks.

Although preferred embodiments of the present invention have been described in full, various alternatives, variants and equivalents can be used. Therefore, the scope of the present invention is not determined with reference to the above description, but should be determined by claim, and includes the entire range of equivalents. Any of the features described herein may be combined with other features, whether preferred or not. Unless expressly stated in the claims, each item is in quantity of one or more. Unless explicitly stated in the claims using a phrase such as "means for", the claims shall not be construed as including the limitation of means plus function.