Method and system for managing data transmission between devices behind network address translators (NATs)

• US 8,788,706 B2
• Filed: 02/27/2006
• Issued: 07/22/2014
• Est. Priority Date: 02/27/2006
• Status: Active Grant

• Current Assignee: NBC Universal Media LLC (Comcast Corporation)
• Original Assignee: Vudu Incorporated (Comcast Corporation)
• Inventors: Ganesan, Prasanna
• Primary Examiner(s): Choudhury, Azizul
• Assistant Examiner(s): NAJEE-ULLAH, TARIQ S
• Application Number:
  US11/364,641
• Publication Number:
  US 20090024762A1
• Time in Patent Office: 3,067 Days
• Field of Search: 709/245
• US Class Current: 709/245
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
• CPC Class Codes: H04L 65/612 for unicast

Abstract

Techniques for managing direct communication between two devices are disclosed. Each of the device is behind a network address translator. According to one embodiment, a server, in responding to a request from a requesting device for needed data, is configured to determine some of devices in service to be candidates from a database, where the database has many entries, each of the entries pertaining to one of the devices. The candidates are determined in accordance with at least compatibility of respective network address translators with a network address translator of the requesting device. Among the candidates, the server then designates a finalist that is preferably not designated to be a supplying device more often than it should be on average. The server then notifies either the requesting device or the supplying device so that the requesting device can get the needed data directly from the supplying device.

Claims

1. A method, to be performed by a processor, for facilitating peer-to-peer communications between a plurality of devices coupled to a network, the method comprising:

receiving a request for a data item from a first device, of the plurality of devices, wherein a first network address translator is associated with the first device;

identifying a set of devices, in the plurality of devices, each having at least a portion of the requested data item, wherein one or more network address translators are associated with the set of devices;

prioritizing the set of devices based on a compatibility of the first network address translator with each of the one or more network address translators, wherein devices associated with more compatible network address translators are given a higher priority than devices associated with less compatible network address translators, wherein prioritizing the set of devices based on the compatibility of the first network address translator with each of the one or more network address translators comprises

if (a) one or more network address translators (NATs) of the one or more NATs is a symmetric NAT and has an average previous designation frequency that does not exceed an allowable designation frequency, then designating as a second device a device of the set of devices associated with at least one of the one or more NATs satisfying (a);

if a NAT of the one or more NATs is not found to satisfy (a), then if (b) one or more network address translators (NATs) of the one or more NATs is a Port-restricted NAT and has an average previous designation frequency that does not exceed the allowable designation frequency, then designating as a second device a device of the set of devices associated with at least one of the one or more NATs satisfying (b); and

if a NAT of the one or more NATs is not found to satisfy (a) and (b), then designating as the second device a device of the set of devices associated with a NAT that is one of a Full-cone NAT and a restricted cone NAT and that has an average previous designation frequency that does not exceed the allowable designation frequency;

designating a second device, of the set of devices, to supply data to the first device based, at least in part, on the prioritization; and

enabling the first device to receive data pertaining to the requested data item from the second device.

2. The method as recited in claim 1 wherein designating a second device comprises designating the second device based on:

(i) a compatibility of the first network address translator with a network address translator associated with the second device, and (ii) a number of times the second device has been designated to supply data to one or more of the plurality of devices.

3. The method as recited in claim 1, further comprising storing information pertaining to the plurality of devices in a database, the information identifying at least a network address translator associated with each of the plurality of devices.

4. The method as recited in claim 3, further comprising:

receiving a probing message from a newly added device in the plurality of devices;

determining a network address translator associated with the newly added device; and

updating the database to include information pertaining to the newly added device.

5. The method as recited in claim 4, wherein the request includes an instruction to receive data pertaining to the data item from two or more devices.

6. The method as recited in claim 5, further comprising designating a third device, of the set of devices, to supply data to the second device, the third device being designated based on:

(i) a compatibility of the first network address translator with a network address translator associated with the third device, and (ii) a number of times the third device has been designated to supply data to one or more of the plurality of devices.

7. The method as recited in claim 6, further comprising enabling the first device to initiate a data transfer with at least one of the second or third devices.

8. The method as recited in claim 6, wherein each of the second and third devices includes one or more locally stored segments pertaining to the requested data item, wherein the one or more locally stored segments in each of the second and third devices are non-consecutive.

9. The method as recited in claim 6, further comprising enabling at least one of the third and fourth devices to initiate a data transfer with the second device.

10. The method as recited in claim 8, wherein the second and third devices are configured to supply data from the respective segments, concurrently, to the first device.

11. The method as recited in claim 10, wherein enabling the first device to receive data pertaining to the requested data item from the second device comprises:

enabling the first device to receive data from the second and third devices concurrently; and

multiplexing the received data on the first device to recover the requested data item.

12. A method, to be performed by a processor, for initiating peer-to-peer communications between a first device and a plurality of devices coupled to a network, the method comprising:

transmitting a request for a data item to a second device coupled to the network, wherein the second device is configured to;

(i) identify a set of devices, in the plurality of devices, each having at least a portion of the requested data item, and (ii) prioritize the set of devices based on a compatibility of a first network address translator, associated with the first devices, with one or more network address translators, associated with the set of devices; and

receiving data pertaining to the requested data item from a third device, of the set of devices, wherein the third device is designated to supply data to the first device based, at least in part, on the prioritization;

wherein the second device is configured prioritize the set of devices based on the compatibility of the first network address translator with each of the one or more network address translators by

if (a) one or more network address translators (NATs) of the one or more NATs is a symmetric NAT and has an average previous designation frequency that does not exceed an allowable designation frequency, then designating as a second device a device of the set of devices associated with at least one of the one or more NATs satisfying (a);

if a NAT of the one or more NATs is not found to satisfy (a), then if (b) one or more network address translators (NATs) of the one or more NATs is a Port-restricted NAT and has an average previous designation frequency that does not exceed the allowable designation frequency, then designating as a second device a device of the set of devices associated with at least one of the one or more NATs satisfying (b); and

if a NAT of the one or more NATs is not found to satisfy (a) and (b), then designating as the second device a device of the set of devices associated with a NAT that is one of a Full-cone NAT and a restricted cone NAT and that has an average previous designation frequency that does not exceed the allowable designation frequency.

13. The method as recited in claim 12, wherein the third device is designated based on:

(i) a compatibility of the first network address translator with a network address translator associated with the third device, and (ii) a number of times the third device has been designated to supply data to one or more of the plurality of devices.

14. The method as recited in claim 12, wherein the request includes an instruction to receive data pertaining to the data item from two or more devices.

15. The method as recited in claim 14, further comprising receiving data pertaining to the requested data item from a fourth device, of the set of devices, the fourth devices, the fourth device being designated, at least in part, on the prioritization.

16. The method as recited in claim 15, further comprising receiving a message from the second device, the method including information for enabling the first device to initiate a data transfer with at least one of the third or fourth devices.

17. The method as recited in claim 16, wherein each of the third and fourth devices includes one or more locally stored segments pertaining to the requested data item, wherein the one or more locally stored segments in each of the third and fourth devices are non-consecutive.

18. The method as recited in claim 17, wherein receiving data pertaining to the requested data item comprises receiving data from the respective segments of the third and fourth devices, concurrently.

19. The method as recited in claim 18, further comprising multiplexing the received data to recover the requested data item.

20. A system for managing peer-to-peer communications between a plurality of devices coupled to a network, the system comprising:

a first device, of the plurality of devices, to transmit a request for a data item, wherein a first network address translator is associated with the first device;

a second device, coupled to the network, to receive the request from the first device, the second device being configured to;

(i) identify a set of devices, in the plurality of devices, each having at least a portion of the requested data item, and (ii) prioritize the set of devices based on a compatibility of the first network address translator with one or more network address translators associated with the set of devices such that a priority associated with a device of the set of devices decreases with a degree of compatibility of the network address translator thereof with other network address translators;

a third device, of the set of devices, designated to supply data to the first device, the third device being designated based, at least in part, on (i) the prioritization and (ii) a number of times the third device has been designated to supply data to one or more of the plurality of devices; and

wherein the second device enables the first device to receive data pertaining to the requested data item from the third device;

wherein the second device is configured prioritize the set of devices based on the compatibility of the first network address translator with each of the one or more network address translators by

if (a) one or more network address translators (NATs) of the one or more NATs is a symmetric NAT and has an average previous designation frequency that does not exceed an allowable designation frequency, then designating as a second device a device of the set of devices associated with at least one of the one or more NATs satisfying (a);

if a NAT of the one or more NATs is not found to satisfy (a), then if (b) one or more network address translators (NATs) of the one or more NATs is a Port-restricted NAT and has an average previous designation frequency that does not exceed the allowable designation frequency, then designating as a second device a device of the set of devices associated with at least one of the one or more NATs satisfying (b); and

if a NAT of the one or more NATs is not found to satisfy (a) and (b), then designating as the second device a device of the set of devices associated with a NAT that is one of a Full-cone NAT and a restricted cone NAT and that has an average previous designation frequency that does not exceed the allowable designation frequency.

21. The system recited in claim 20, further comprising a fourth device, of the set of devices designated to supply data to the first device, wherein each of the third and fourth devices includes one or more locally stored segments pertaining to the requested data item.

22. The system as recited in claim 21, wherein the one or more locally stored segments in each of the third and fourth devices are non-consecutive , and wherein the third and fourth devices are non-consecutive, and wherein the third and fourth devices are configured to supply data from the respective segments, concurrently, to the first device.

23. A non-transitory computer readable medium on which instructions are stored that, when executed by one or more processors, cause the one or more processors to perform steps comprising:

receiving a request for data item from a first device, of a plurality of devices coupled to a network, wherein a first network address translator is associated with the first device;

identifying a set of devices, in the plurality of devices, each having at least a portion of the requested data item, wherein one or more network address translators are associated with the set of devices;

prioritizing the set of devices based on a compatibility of the first network address translator with each of the one or more network address translators, wherein devices associated with more compatible network address translators are given a higher priority than devices associated with less compatible network address translators, wherein prioritizing the set of devices based on the compatibility of the first network address translator with each of the one or more network address translators comprises

if (a) one or more network address translators (NATs) of the one or more NATs is a symmetric NAT and has an average previous designation frequency that does not exceed an allowable designation frequency, then designating as a second device a device of the set of devices associated with at least one of the one or more NATs satisfying (a);

if a NAT of the one or more NATs is not found to satisfy (a), then if (b) one or more network address translators (NATs) of the one or more NATs is a Port-restricted NAT and has an average previous designation frequency that does not exceed the allowable designation frequency, then designating as a second device a device of the set of devices associated with at least one of the one or more NATs satisfying (b); and

if a NAT of the one or more NATs is not found to satisfy (a) and (b), then designating as the second device a device of the set of devices associated with a NAT that is one of a Full-cone NAT and a restricted cone NAT and that has an average previous designation frequency that does not exceed the allowable designation frequency;

enabling the first device to receive data pertaining to the requested data item from the second device.