Method for host selection

0001This invention is related to computer networks and more specifically to selection of a host, for example for peer-to-peer communication among several clients of a computer network.

0002Presently, during game play amongst several clients of a computer network, clients communicate directly with the server. The central server processes data from every client relaying this data to all other clients so that several clients in the network can engage in game play with each other through a central server. The central server's ability to communicate data amongst several clients is limited by bandwidth, and so communication outside of game play data is limited.

0003Aside from game play data, clients may want to communicate other information to each other without having to go through a bandwidth-limited central server. Examples of such communication may include voice over Internet protocol (VoIP), bit torrents, video data, file sharing, and data streaming. By allowing clients to communicate amongst each other without the need of a central server, some of the central server's responsibilities may be offloaded to the clients.

0004A peer-to-peer network is established when a host is determined amongst the numerous clients participating in the P2P network. The host takes the duty of a central server and directs communication amongst clients (hereinafter referred to as peers when referencing non-hosts in a P2P network).

0005It is within this context the embodiments of the present invention arise.

0006Various respective aspects and features of the present invention are defined in the appended claims.

0007Embodiments of the invention will now be described, by way of example only, with reference to the accompanying drawings in which: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIG. 1</figref> is a schematic diagram illustrating a P2P network according to an embodiment of the present invention.</li><li><figref idref="f0002">FIG. 2</figref> is a flow diagram illustrating a method for host selection based on discovered NAT type according to a specific embodiment of the present invention from the client's perspective.</li><li><figref idref="f0003">FIG.3</figref> is a flow diagram illustrating the basic method for host selection based on discovered NAT type from the client's perspective.</li><li><figref idref="f0004">FIG. 4</figref> is a block diagram illustrating an example of a client interface according to an embodiment of the current invention.</li></ul>

0008One problem that arises when trying to establish communication amongst clients through peer-to-peer communication (P2P) is the issue of network address translation (NAT). Most clients connected to the central server are situated behind a NAT. NAT is an Internet standard that enables a local area network (LAN) to use of one set of private IP addresses for internal traffic and a second set of global IP addresses for external traffic. It is therefore desirable for a host in a P2P network to have a favorable NAT profile in order to create an optimal P2P network.

0009Thus, there is need in the art for a method of determining a host with a favorable NAT profile amongst several clients connected to a central server.

0010There are 4 types of NATs available: Full Cone NAT, Restricted Cone NAT, Port Restricted Cone NAT, and Symmetric NAT. A full cone NAT is one where all requests from the same internal IP address and port are mapped to the same external IP address and port. Furthermore, any external host can send a packet to the internal host by sending a packet to the mapped external address.

0011In a restricted cone NAT, all requests from the same internal IP address and port are mapped to the same external IP address and port. Unlike a full cone NAT, an external host (with IP address X) can send a packet to the internal host only if the internal host had previously sent a packet to IP address X.

0012A port restricted NAT is like a restricted cone NAT, but the restriction includes port numbers. Specifically, an external host can send a packet with source IP address X and source port P to the internal host only if the internal host had previously sent a packet from IP address X and port P.

0013In a symmetric NAT, all requests from the same internal IP address and port, to a specific destination IP address and port, are mapped to the same external IP address and port. If the same host sends a packet with the same source address and port, but to a different destination, a different mapping is used. Furthermore, only the external host that receives a packet can send a user data protocol (UDP) packet back to the internal host.

HOST SELECTION BASED ON NAT TYPE

0014<figref idref="f0001">FIG. 1</figref> is a schematic diagram illustrating a P2P network according to an embodiment of the present invention. Client devices <b>105A, 105B, 107,</b> and <b>105D</b> on the network are initially connected to a server <b>101</b> in an external network <b>109.</b> By way of example, the server <b>101</b> may monitor data for game play between clients <b>105A, 105B, 107,</b> and <b>105D</b> connected to the external network <b>109.</b> The clients <b>105A, 105B, 107,</b> and <b>105D</b> may be situated behind corresponding network address translators (NAT) <b>111A, 111B, 111C</b> and <b>111D.</b> Each NAT may be configured according to an Internet standard that enables a local area network (LAN) to use one set of private IP addresses for internal traffic and a second set of global IP addresses for external traffic. Most NATs perform dynamic translation on IP addresses such that external networks have no way of reaching the internal network prior to the internal network initiating communication. However, because the clients <b>105A, 105B, 107,</b> and <b>105D</b> establish server-client relationships, communication between the server <b>101</b> and clients <b>105A, 105B, 107,</b> and <b>105D</b> is not limited by the NATs <b>111A, 111B, 111C</b> and <b>111D.</b>

0015In establishing a P2P network in which clients can communicate directly with each other, one client may be established as a host <b>107</b> by which other peers <b>105</b> (clients connected to the P2P network who are not the host) may establish direct connections with each other. By way of example and not by way of limitation, the peers <b>105</b> may be connected in a configuration known as a fully connected grid (FCG). Such a configuration prevents any one peer from being a bottle neck. In embodiments of the present invention, the host <b>107</b> may be determined based on each client's NAT profile. The NATs <b>111A, 111B, 111C</b> and <b>111D</b> may be of one of four different configurations generally referred to as Full Cone NAT, Restricted Cone NAT, Port Restricted Cone NAT, and Symmetric NAT.

0016A full cone NAT is one where all requests from the same internal IP address and port are mapped to the same external IP address and port. Any client can send a packet to the client behind a full cone NAT by sending a packet to the mapped external address for the client.

0017In a 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 a full cone NAT, an external client (with IP address X) can send a packet to the client behind the full cone NAT only if the internal host had previously sent a packet to IP address X.

0018A port restricted NAT is similar to a restricted cone NAT, but the restriction includes port numbers. Specifically, an external client can send a packet with a source IP address X and source port P to the client behind the port restricted NAT only if the client behind the port restricted NAT had previously sent a packet from IP address X and port P.

0019In a symmetric NAT, all requests from the same internal IP address and port, to a specific destination IP address and port, are mapped to the same external IP address and port. If the same host sends a packet with the same source address and port, but to a different destination, a different mapping is used. Furthermore, only the external host that receives a packet can send a UDP packet back to the internal host.

0020Traversal of full cone, restricted cone and port restricted cone NATs is relatively straightforward and somewhat more complicated for symmetric NATs. NAT traversal may be implemented if a client is behind a symmetric NAT, e.g., as described in commonly-assigned <patcit id="pcit0001" dnum="US20070076729A"><text>US Patent Application Publication Number 20070076729</text></patcit>. In particular, the client may perform a port prediction involving construction of a list of predicted transport addresses on the NAT that the client is behind. The client may then send an INVITE message containing the list of predicted transport addresses from the first node to a second client. The client behind the symmetric NAT may then perform a connectivity check with the second node using the predicted transport addresses. Connectivity checks may be performed by e.g., by sending simple traversal of user data protocol (UDP) through NAT (STUN) requests to each predicted transport address, in parallel. When the client behind the symmetric NAT receives these, it sends a STUN response to the second client. If the second client receives the STUN response, it can then begin to send media to that address.

0021There may be NAT types other than the four described above. In some cases it may be possible to traverse such NATs using standard techniques and in other cases the NAT behavior may be so unpredictable or unstable that communication with a client behind such a NAT is unreliable.

0022Because the duty of the host <b>107</b> is to communicate information between other peers <b>105A, 105B,</b> and <b>105D</b> it is essential that the host <b>107</b> be behind a NAT of a type that does not interfere with its ability to communicate. In embodiments where the peers <b>105A, 105B, 105D</b> and the host <b>107</b> are connected in a fully connected grid (FCG) it is particularly desirable to use a host behind a NAT that does not interfere with its ability to communicate in order to provide the highest level of service to the greatest number of peers. There have been cases where a NAT identified as having questionable (unknown) support for P2P has actually performed quite well against the other NAT types in use by the existing peers in the P2P network. By selecting a host <b>107</b> with the most favorable NAT profile, more reliable peer-to-peer communication may be obtained. As used herein, the term P2P communication generally refers to direct communication between client devices connected to a network. Examples of P2P applications include, but are not limited to, the voice over internet protocol (VoIP), bit torrent transmission, video transmission, file sharing, data sharing, and other types of direct data transfer between clients that does not exceed the bandwidth capabilities of an individual client. Once the host <b>107</b> has been established, peers <b>105A, 105B, 105D</b> can communicate with each other by initially transmitting information to the host <b>107</b> which then relays that information to the respective recipient peers <b>105A, 105B, 105D,</b> or they may transmit information directly after using host <b>107</b> to establish this direct communication path.

0023In certain embodiments, clients <b>105A, 105B, 105D,</b> and <b>107</b> may obtain their NAT profile information through a simple traversal of user data protocol (UDP) through NAT (STUN) server <b>103</b> that is associated with the external network <b>109.</b> STUN server <b>103</b> is a lightweight protocol proposed by Internet Engineering Task Force (IETF) that allows an IP enabled client to discover the presence and types of NAT that the client is behind. STUN <b>103</b> works with most NAT types and does not depend on any special behavior of the NAT. The STUN server <b>103</b> acts like a mirror held up to a client <b>105A</b> so that the client <b>105A</b> can see how its local transport address gets mapped to a public transport address. The client <b>105A</b> can also determine the type of the NAT <b>111A</b> that the client <b>105A</b> is behind through communication with the STUN server <b>103.</b>

0024By way of example and not by way of limitation, each client <b>105A, 105B, 107, 105D</b> may use a STUN server <b>103</b> to obtain NAT profile information, that it may then relay that information to the central server <b>101</b> in order for the central server <b>101</b> to determine which client would make the most favorable host <b>107.</b> Likewise, a client <b>105A, 105B, 107, 105D</b> may use a STUN server <b>103</b> to obtain NAT profile information that may then be relayed to all other clients <b>105</b> attempting to communicate through the P2P network in order for the clients <b>105A, 105B, 107, 105D</b> to best determine the host <b>107.</b>

0025<figref idref="f0002">FIG. 2</figref> is a flow chart illustrating the basic method for host selection based on discovered NAT type from a client's perspective. Each client connected to the server <b>101</b> may collect its own NAT profile information for use with the P2P network, as indicated at <b>201.</b> This profile information may include information regarding the type that the client is behind, information regarding whether the NAT supports universal plug and play (UPnP), information regarding whether the NAT exhibits port preservation, and information regarding whether the NAT supports port predictability. As used herein, port preservation means that once an internal IP address mapped to a particular external port it will be consistently mapped to that particular port. As used herein, port predictability means that it is possible to predict the external port to which an internal IP address will be mapped, even if it is not always the same port. For example, the external port number may be consistently incremented with each attempted mapping of the internal IP address.

0026In addition to NAT behavior, each client's profile information may include quality of service (QoS) information. As used herein, the term QoS information, includes information regarding a client device that is related to how well the client device can communicate with other client devices. By way of example, but not by way of limitation, such information may relate to how fast the client can communicate, how reliably the client can communicate, or some combination of both. Particular examples of QoS information include, but are not limited to ping time, bandwidth behavior, latency, geography, IP provider.

0027The profile information for each client may be used to create a priority list amongst all the clients connected to the server in order to best select the host for P2P communication. If there is a tie in priority between potential hosts, ordinal numbers may be assigned to determine which potential host is selected as the actual host. In some embodiments, such ordinal numbers may be assigned by a server as indicated at <b>203,</b> e.g., in the order in which the clients connected to the server. Alternatively, a distributed arbitration algorithm may be used to select a host from amongst two or more equally suitable potential hosts. If the initial host decides to leave the P2P network or is somehow disconnected from the network, this information may be used to select the next host for the P2P network.

0028Once the profile information has been collected by a given client, the NAT profile for that client is shared with other clients that are connected to the server. Profile information includes an expected count of the number of clients connected to the server, in order to determine whether an optimized P2P network has been reached. At this point, each client waits until every other client has submitted their profile information regarding the NAT they are behind as indicated at <b>205.</b> Once all NAT profiles have been submitted by the clients, a determination is made as to whether the client should be a host, peer or if they fail to meet the requirements for either as described at <b>207.</b> This determination may be made based on the profile information obtained for each client described above. For example, by assigning a priority based on a number of factors, a host can be selected from amongst the available clients based on the client having the most favorable profile. The rest of the clients may be assigned as peers or may fail to be recognized as a peer or host based on their profile information. For example, a client behind a non-traversable NAT may not meet the requirements necessary to connect to the network as a peer or host. By way of example and not by way of limitation, the client that is unable to be recognized as a peer or host may update his profile to notify the rest of the P2P network of his status, and the expected count may be decremented to exclude this client from the P2P network.

0029Table 1 illustrates an example of a prioritization scheme that may be used to decide host assignments in a P2P network. By way of example, but not by way of limitation, the prioritization scheme may be broken down into 5 separate distinctions: Active, Likely, Unknown, In Progress, and Inactive. These are listed in host priority order in Table 1. An active tag indicates that a client is a very good candidate for host. A likely tag indicates that a client is a good candidate for host, but priority is still given to a client with an active tag. An unknown tag indicates that the network is unable to decide whether that particular client is a good candidate for host. An in progress tag indicates that the network is still deciding whether the client is a good candidate for host. Lastly, an inactive tag indicates that a client is unable to assume the duties of a host. In the example illustrated in Table 1, the priority tags may be based on 4 separate criteria: NAT type, universal plug and play (UPnP) capability, port preservation, and port predictability. However, several other factors may also be used in determining priority. These factors fall under a client's quality of service profile and may include QoS information including, but not limited to ping time, bandwidth behavior, geography, latency, and IP provider. <tables id="tabl0001" num="0001"><table frame="all"><title>TABLE 1</title><tgroup cols="6"><colspec colnum="1" colname="col1" colwidth="27mm" /><colspec colnum="2" colname="col2" colwidth="27mm" /><colspec colnum="3" colname="col3" colwidth="29mm" /><colspec colnum="4" colname="col4" colwidth="27mm" /><colspec colnum="5" colname="col5" colwidth="28mm" /><colspec colnum="6" colname="col6" colwidth="30mm" /><thead><row><entry valign="top"><b>Prioritization Tag</b></entry><entry valign="top">Active</entry><entry valign="top">Likely (Scenario 1)</entry><entry valign="top">Likely (Scenario 2)</entry><entry valign="top">Unknown</entry><entry valign="top">Inactive</entry></row></thead><tbody><row><entry><b>NAT Type</b></entry><entry>Cone (Full Cone, Restricted Cone, Port Restricted Cone)</entry><entry>Not Cone (Symmetric or anything else)</entry><entry>Symmetric</entry><entry>Symmetric</entry><entry>Not Cone (Symmetric or anything else)</entry></row><row><entry><b>UPnP</b></entry><entry>Doesn't matter</entry><entry>Yes</entry><entry>No</entry><entry>No</entry><entry>No</entry></row><row><entry><b>Port Preservation</b></entry><entry>Doesn't matter</entry><entry>Doesn't matter</entry><entry>Yes</entry><entry>Cannot determine</entry><entry>No</entry></row><row><entry><b>Port Predictability</b></entry><entry>Doesn't matter</entry><entry>Doesn't matter</entry><entry>Yes</entry><entry>Cannot determine</entry><entry>No</entry></row></tbody></tgroup></table></tables>

0030<figref idref="f0003">FIG. 3</figref> is a flow chart illustrating a method for host selection based on discovered NAT type according to a specific embodiment of the present invention from the client's perspective. A client initially obtains profile information about the network address translator (NAT) that it is behind as described at <b>301.</b> This profile information includes information regarding the NAT type, whether the NAT supports universal plug and play (UPnP), whether the NAT supports port preservation, and whether the NAT supports port predictability. In addition to this information, profile information may also include quality of service information including, but not limited to ping time and bandwidth behavior, geography, latency, IP provider, and the like. This information may be used to create a priority amongst several clients in order to determine a host for supporting peer-to-peer (P2P) communication amongst these several different clients. If the initial host decides to leave the P2P network or is somehow disconnected from the network, this information may be used to select the next host for the P2P network.

0031Once the client has obtained the profile information regarding the NAT it is behind, the client then shares this NAT profile with other clients that are connected to the same server as indicated at 303. Not only are these clients now aware of the profile information described above for all other clients, but they are also notified of the expected count of clients currently connected to the server. At this point, each client may wait until every other client has submitted their profile information regarding the NAT they are behind as indicated at <b>305.</b> Once all NAT profiles have been submitted by the clients, a determination is made as to whether the client should be a host, peer or if they fail to meet the requirements for either as indicated at <b>307.</b> This determination may be made based on the profile information obtained for each client described above. By assigning a priority based on a number of factors, a host can be selected amongst the clients based on having the most favorable profile. The rest of the clients may be assigned as peers or may fail to be recognized as a peer or host based on their profile information. For example, a client behind a non-traversable NAT may not meet the requirements necessary to connect to the network as a peer or host. By way of example and not by way of limitation, the client who is unable to be recognized as a peer or host may update his profile to notify the rest of the P2P network of his status, and the expected count may be decremented to exclude this client from the P2P network.

0032The client that is assigned the duty of being a host may then wait for the rest of the clients on the network to connect and also updates their profiles as indicated at <b>309.</b> Once all the clients have connected to the host, the expected count may be checked to determine whether all clients that are connected to the server have connected to the host as indicated at <b>311.</b> If the count is as expected, P2P communication is enabled as indicated at <b>317.</b> If however, the count is less than expected due to one or more clients failing to meet the requirements of being a host or peer, then the count is reduced and the process may begin again at <b>303.</b>

0033If the client is determined to be a peer, it may attempt to connect to the host once the host has been determined as indicated at <b>313.</b> A determination is made as to whether the peer is able to connect to the host or fails to connect to the host as indicated at <b>315.</b> If the client is able to connect to the host, then it waits for all other peers to connect to the host before P2P communication is enabled as described at <b>317.</b> If the client is unable to connect to the host, then the client's profile information is updated and the process begins again at <b>303.</b> Ultimately, if the client is unable to connect to the host on multiple occasions, the count may be decremented leaving that individual client out of the P2P network.

0034If a peer failure occurs while collecting the NAT information, then this may be recorded as a failure and shared with the other peers. It may be assumed that sharing the data or waiting for the data will not fail, e.g., if the communication of this data is done through a reliable communication channel, such as the server <b>101.</b> If the communication to the server <b>101</b> fails at any point during this process then the entire process may be aborted and the remaining clients are notified of this disconnect as specified by the protocol used to communicate with the server <b>101.</b> The remaining clients will no longer be waiting for a response from the disconnected client.

0035Once a host has been identified from among the client devices, the server <b>101</b> may offload one or more functions to the P2P grid managed by the peer designated as the host. Such functions may be assumed by the host and/or any of the peers within the P2P grid. By way of example, but not by way of limitation, the P2P grid maybe a fully connected grid or a star topology where by the all communication goes through the host. The topology of the grid is not strictly relevant to embodiments of this invention. What is relevant is that the primary point of connection (the host) to a P2P grid of any topology is established based on the behavior of a NAT associated with that primary point of connection.

0036A client device <b>400</b> may be configured to implement a method for host determination according to an embodiment of the present invention as shown in <figref idref="f0004">FIG. 4</figref>. By way of example, and without loss of generality, the client device <b>400</b> may be implemented as part of a digital television set, personal computer, video game console, personal digital assistant, mobile or handheld device such as a cellular phone or personal digital assistant, handheld video game device, portable email device and the like, or other digital device.

0037The device <b>400</b> may include a central processing unit (CPU) <b>402</b> and a memory <b>404</b> coupled to the CPU <b>402.</b> The CPU <b>402</b> may be configured to run software applications and, optionally, an operating system. Some embodiments of the present invention may take advantage of certain types of processor architecture in which the CPU <b>402</b> includes a main processor <b>402A</b> and one or more auxiliary processors <b>402B.</b> Each auxiliary processor <b>402B</b> may have its own associated local data storage. One example, among others of such processor architecture is a Cell Processor. An example of Cell Processor architecture is described in detail, e.g., in <nplcit id="ncit0001" npl-type="b"><text>Cell Broadband Engine Architecture, copyright International Business Machines Corporation, Sony Computer Entertainment Incorporated, Toshiba Corporation August 8, 2005 a copy of which may be downloaded at http://cell.scei.co.jp</text></nplcit>/.

0038Referring again to <figref idref="f0004">FIG. 4</figref>, the receiving device <b>400</b> may also include well-known support functions <b>410,</b> such as input/output (I/O) elements <b>411,</b> power supplies (P/S) <b>412,</b> a clock (CLK) <b>413</b> and cache <b>414.</b> The device <b>400</b> may further include a fast data storage device <b>415</b> such as a hard disk drive that provides non-volatile storage for applications and data. The fast storage device <b>415</b> may be used for temporary or long-term storage of files <b>416</b> retrieved from a slower data storage device. By way of example, the storage device <b>415</b> may be a fixed disk drive, removable disk drive, flash memory device, tape drive. Alternatively, the storage device <b>415</b> may be, e.g., a CD-ROM, DVD-ROM, Blu-ray, HD-DVD, UMD, or other optical storage devices. Files <b>416</b> from a slower storage device may be temporarily stored in a faster storage device in a hardware cache for quick loading into the memory <b>404.</b>

0039One or more user input devices <b>420</b> may be used to communicate user inputs from one or more users to the system <b>400.</b> By way of example, one or more of the user input devices <b>420</b> may be coupled to the client device <b>400</b> via the I/O elements <b>411.</b> Examples of suitable input devices <b>420</b> include keyboards, mice, joysticks, touch pads, touch screens, remote control units, light pens, still or video cameras, and/or microphones.

0040The client device <b>400</b> may communicate with one or more other client devices in a peer-to-peer network through a network interface <b>425</b> that facilitates communication via the electronic communications network <b>427.</b> The network interface <b>425</b> may be configured to implement wired or wireless communication over local area networks and wide area networks such as the Internet. The system <b>400</b> may send and receive data and/or requests for files via one or more message packets <b>426</b> over the network <b>427.</b> By way of example and not by way of limitation, the electronic communication network <b>427</b> may be a local area network, wide area network, or personal area network (e.g., blue-tooth) that can communicate between the device <b>400</b> and one or more other client devices.

0041The memory <b>404</b> may store applications and data for use by the CPU <b>402.</b> The memory <b>404</b> may be in the form of an integrated circuit (e.g., RAM, DRAM, ROM, and the like). A computer program <b>401</b> may be stored in the memory <b>404</b> in the form of instructions that can be executed on the processor <b>402.</b>

0042The program <b>401</b> may include instructions that when executed by the processor cause it to implement a method for determining a host from among a group of two or more peer client devices in a peer-to-peer network. By way of example, and without loss of generality, the program <b>401</b> may, upon execution, cause the device <b>400</b> to implement the method <b>200</b> illustrated in <figref idref="f0002">FIG. 2</figref> or the method <b>300</b> illustrated in <figref idref="f0003">FIG. 3</figref>. In particular the program <b>401</b> may cause the device <b>400</b> to a) collect NAT profile information for the device <b>400;</b> b) share the NAT profile information for the device with one or more other client devices <b>400', 400"</b> connected to the network <b>427;</b> c) receive NAT profile information for the one or more other client devices; and d) determine from the NAT profile information for the client device <b>400</b> and the NAT profile information for the one or more other client devices which of the client devices <b>400, 400', 400"</b> to designate as the host.

0043NAT profile information <b>406</b> for the client device <b>400</b> and the other client devices <b>400', 400"</b> may be stored in the memory <b>404</b> for use in determining the host. Each of the client device <b>400, 400'</b> and <b>400"</b> may be behind a corresponding NAT <b>403, 403'</b> and <b>403".</b> The client device <b>400</b> may reside behind a network address translator (NAT) <b>403,</b> which translates an internal IP address for the client device <b>400</b> to a public IP address that is seen by other devices. It is noted that the NAT <b>403</b> is usually not a part of the client device <b>400</b> although some types of client device may include a NAT. Furthermore, embodiments of the present invention may be implemented if any or all of the client devices <b>400, 400', 400"</b> is not behind a NAT at all.

0044The NAT profile information <b>406</b> may include, but is not limited to, information about the type of NAT (if any) that the client device <b>400</b> is behind, the ability of the NAT to engage in universal plug and play (UPnP), the NAT's ability to maintain port preservation, and the NAT's port predictability. The program <b>401</b> may implement selection may be based on the criteria described above, with respect to Table 1. Each of the other client devices <b>400', 400"</b> may be similarly configured and may implement the same host selection process. If all client devices <b>400, 400',</b> and <b>400"</b> use the same program <b>401</b> and the profile information <b>406</b> it is reasonable to expect that they should all make the same host determination.

0045In some situations, it may be desirable for the program <b>401</b> to apply a supplemental arbitration filter based on additional information <b>408,</b> such as quality of service information, to arbitrate a determination the host device from among two or more equally likely candidate devices. Quality of service information may include factors such as the client's ping time, bandwidth behavior, geography, latency, IP provider, etc, and other factors as described above. Such additional information <b>408</b> may also be stored in the memory <b>404.</b>

0046The client device <b>400</b> may further comprise a graphics subsystem <b>430,</b> which may include a graphics processing unit (GPU) <b>435</b> and graphics memory <b>437.</b> The graphics memory <b>437</b> may include a display memory (e.g., a frame buffer) used for storing pixel data for each pixel of an output image. The graphics memory <b>437</b> may be integrated in the same device as the GPU <b>435,</b> connected as a separate device with GPU <b>435,</b> and/or implemented within the memory <b>404.</b> Pixel data may be provided to the graphics memory <b>437</b> directly from the CPU <b>402.</b> Alternatively, the CPU <b>402</b> may provide the GPU <b>435</b> with data and/or instructions defining the desired output images, from which the GPU <b>435</b> may generate the pixel data of one or more output images. The data and/or instructions defining the desired output images may be stored in memory <b>406</b> and/or graphics memory <b>437.</b> In an embodiment, the GPU <b>435</b> may be configured (e.g., by suitable programming or hardware configuration) with 3D rendering capabilities for generating pixel data for output images from instructions and data defining the geometry, lighting, shading, texturing, motion, and/or camera parameters for a scene. The GPU <b>435</b> may further include one or more programmable execution units capable of executing shader programs.

0047The graphics subsystem <b>430</b> may periodically output pixel data for an image from the graphics memory <b>437</b> to be displayed on a video display device <b>450.</b> The video display device <b>450</b> may be any device capable of displaying visual information in response to a signal from the device <b>400,</b> including CRT, LCD, plasma, and OLED displays that can display text, numerals, graphical symbols or images. The digital broadcast receiving device <b>400</b> may provide the display device <b>450</b> with a display driving signal in analog or digital form, depending on the type of display device. In addition, the display <b>450</b> may be complemented by one or more audio speakers that produce audible or otherwise detectable sounds. To facilitate generation of such sounds, the client device <b>400</b> may further include an audio processor <b>455</b> adapted to generate analog or digital audio output from instructions and/or data provided by the CPU <b>402,</b> memory <b>404,</b> and/or storage <b>415.</b>

0048The receiving device <b>400</b> may optionally include a position location device <b>470.</b> Such a device may be based on any suitable technology capable of providing information on the geographic location of a device. Examples of existing technology include global positioning satellite (GPS) technology, inertial guidance technology, and the like. Information from such devices may be used in digital broadcast data applications such as navigation for mobile or hand-held devices.

0049According to certain embodiments, it may be useful to determine a geographic location of the client device <b>400.</b> Certain QoS considerations, such as bandwidth, ping time and latency may be affected by the location of the device. By way of example and not by way of limitation, to facilitate host determination, the position-locating device <b>470</b> may provide geographic location information that the program <b>401</b> may use in determining whether the client device <b>400</b> is a good candidate to be the host for a peer-to-peer service.

0050The components of the device <b>400,</b> including the CPU <b>402,</b> memory <b>404,</b> support functions <b>410,</b> data storage devices <b>415</b> user input devices <b>420,</b> network interface <b>425,</b> graphics unit <b>430,</b> audio processor <b>455</b> and position location device <b>470</b> may be operably connected to each other via one or more data buses <b>460.</b> These components may be implemented in hardware, software or firmware or some combination of two or more of these.

0051Embodiments of the present invention allow for cooperative host determination and host migration in peer-to-peer network situations.

0052Further information is provided in Publication No. <patcit id="pcit0002" dnum="US20090094370A1"><text>US20090094370 A1</text></patcit> , <patcit id="pcit0003" dnum="US049954A"><text>U.S. Patent Application Number 12/049,954</text></patcit>, <patcit id="pcit0004" dnum="US997918P"><text>U.S. Provisional Patent Application Number 60/997,918</text></patcit> and Publication Number <patcit id="pcit0005" dnum="US20070076729A"><text>US20070076729 A</text></patcit>.

0053While the above is a complete description of the preferred embodiment of the present invention, it is possible to use various alternatives, modifications and equivalents. Therefore, the scope of the present invention should be determined not with reference to the above description but should, instead, be determined with reference to the appended claims, along with their full scope of equivalents. Any feature described herein, whether preferred or not, may be combined with any other feature described herein, whether preferred or not. In the claims that follow, <u>the indefinite article "A", or "An"</u> refers to a quantity of one or more of the item following the article, except where expressly stated otherwise.

0054In so far as embodiments of the invention are described with reference to one or more computer software-controlled devices, it will be appreciated that such software and providing media (such as a computer readable storage medium) by which such software is provided are considered to form aspects of the present invention.

0055Other aspects and features of the invention re set out in the following numbered clauses: <ol id="ol0001" compact="compact"><li>1. In a peer, a method for determining which of two or more peers to designate as a host for a service within a peer to peer grid, the method comprising: <ol id="ol0002" compact="compact"><li>a) collecting NAT profile information for the peer;</li><li>b) sharing the NAT profile information for the peer with one or more other peers of the two or more peers;</li><li>c) receiving NAT profile information for the one or more other peers; and</li><li>d) determining from the NAT profile information for the peer and the NAT profile information for the one or more other peers which of the two or more peers to designate as the host.</li></ol></li><li>2. The method of clause 1, wherein b) includes relaying the NAT profile information for the peer to the one or more other peers via a pre-established connection between the peer and the one or more other peers.</li><li>3. The method of clause 2, wherein the pre-established connection includes use of a server for an application common to the two or more peers.</li><li>4. The method of clause 3, wherein the server offloads one or more functions to the peer to peer grid, which is managed by the peer designated as the host.</li><li>5. The method of clause 2, wherein the pre-established connection includes one of the one or more other peers acting as a host.</li><li>6. The method of clause 2, wherein c) includes receiving the NAT profile information for the one or more other peers via the pre-established connection.</li><li>7. The method of clause 1, wherein d) includes assigning priority values to each of the two or more peers based on the NAT profile information for the peer and the NAT profile information for the on one or more other peers and selecting the host based on the priority values.</li><li>8. The method of clause 7 wherein the NAT profile information includes a NAT type for a NAT that the peer is behind, information regarding whether the NAT supports universal plug and play (UPnP), port predictability information for the NAT, and port preservation information for the NAT.</li><li>9. The method of clause 7 wherein the NAT profile information for the one or more other peers includes a NAT type for a NAT that another peer is behind, information regarding whether the NAT supports universal plug and play (UPnP), port predictability information for the NAT, and port preservation information for the NAT.</li><li>10. The method of clause 7, wherein, if two or more of the two or more peers are of equal priority values, d) includes resolving which of the two or more potential hosts of equal priority values to designate as the host.</li><li>11. The method of clause 10, wherein resolving which of the two or more potential hosts of equal priority values to designate as the host includes designating as the host one of the two or more potential hosts of equal priority value having a higher ordinal value, wherein a different ordinal value is assigned to each of the two or more potential hosts.</li><li>12. The method of clause 10, wherein resolving which of the two or more potential hosts of equal priority values to designate as the host includes a distributed arbitration algorithm.</li><li>13. The method of clause 1, further comprising, if the peer is designated as the host, notifying the one or more other peers of the peer's designation as host and waiting for the one or more other peers to connect.</li><li>14. A peer device, comprising: <ul id="ul0002" list-style="none" compact="compact"><li>a computer processor;</li><li>a computer memory coupled to the processor;</li><li>a network interface coupled to the processor, wherein the network interface is configured to facilitate communication between the processor and one or more other peer devices connected in a peer-to-peer grid; and</li><li>a set of computer readable instructions embodied in the memory, wherein the computer-readable instructions are configured to implement a method for determining which of peer device in the peer-to-peer grid to designate as a host for a service within the peer to peer grid, the method comprising: <ol id="ol0003" compact="compact"><li>a) collecting NAT profile information for the peer;</li><li>b) sharing the NAT profile information for the peer with one or more other peers of the two or more peers;</li><li>c) receiving NAT profile information for the one or more other peers; and</li><li>d) determining from the NAT profile information for the peer and the NAT profile information for the one or more other peers which of the two or more peers to designate as the host.</li></ol></li></ul></li><li>15. A computer readable medium having a set of computer readable instructions embodied therein, wherein the computer-readable instructions are configured to implement a method for determining which of two or more peer devices in a peer-to-peer grid to designate as a host for a service within the peer to peer grid, the method comprising the steps set forth in any one of clauses 1 to 13.</li></ol>