Efficient one-to-many content distribution in a peer-to-peer computer network

• US 7,593,333 B2
• Filed: 07/07/2004
• Issued: 09/22/2009
• Est. Priority Date: 07/07/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Jin, Zhang, Cha, Chou, Philip A.
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): CHAN, SAI MING
• Application Number:
  US10/887,406
• Publication Number:
  US 20060007947A1
• Time in Patent Office: 1,903 Days
• Field of Search: 370/432, 370/232, 370/390, 370/468
• US Class Current: 370/232
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/1877 Measures taken prior to transmission
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1076 Resource dissemination mechanisms or network resource keeping policies for optimal resource availability in the overlay network
• CPC Class Codes: H04L 67/108 characterised by resources being split in blocks or fragments
• CPC Class Codes: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/165 Combined use of TCP and UDP protocols; selection criteria therefor

Abstract

A content distribution method and system for distributing content over a peer-to-peer network such that the full potential throughput of the network is achieved. The content distribution method divides the content to be distributed into many small blocks. Each of the content blocks then is assigned to a node, which can be a content-requesting node, a non-content-requesting node or a source node. Content is assigned based on a capacity of the node, where nodes having a larger capacity are assigned a greater number of content blocks and nodes having a smaller capacity are assigned a fewer content blocks. The capacity generally is defined as the upload bandwidth of the node. Redistribution queues are employed to control the throughput of the distribution. This bandwidth control strategy ensures that upload bandwidths of the peer and source nodes are fully utilized even with network anomalies such as packet losses and delivery jitters.

Claims

1. A method for distributing content to a plurality of nodes on a computer network, comprising:

dividing the content into a plurality of blocks;

assigning each block of the plurality of blocks to a single node of the plurality of nodes for redelivery only by the single assigned node in proportion to a capacity of the node such that a node having a larger capacity is assigned more blocks and a node having a smaller capacity is assigned fewer blocks;

sending each of the plurality of blocks from a source node to an assigned node of the source node for redelivery, if the assigned node is not the source node;

redelivering the block by the assigned node to remaining content requesting nodes; and

adjusting a content sending rate, θ

, in a dynamic manner based on a maximum throughput under prevailing conditions by using the equation;

$\mathrm{\theta <br><br>}=\{\begin{array}{cc}{B}_s& \mathrm{if}<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>B_s\le <br><br>B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2},\\ \left(B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2}\right)+\frac{B_s-\left(B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2}\right)}{N_1}& \mathrm{if}<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>B_s\ge <br><br>B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2},\end{array}<br><br><br><br>\mathrm{with}<br><br><br><br>B_{s<br><br><br><br>1}=\frac{N_1}{N_1-1}<br><br><br><br>B_1<br><br><br><br>\mathrm{and}<br><br><br><br>B_{s<br><br><br><br>2}=\frac{N_2}{N_1}<br><br><br><br>B_2,$

where B_S is a bandwidth of the source node, N₁ is a number of content-requesting peer nodes, B₁ is an average bandwidth of the N₁ content-requesting peer nodes, N₂ is a number of non-content requesting peer nodes, B₂ is an average bandwidth of the N₂ non-content requesting peer nodes, B_s1 is an equivalent source node bandwidth when each of the content requesting peer nodes are forwarding data, and B_s2 is an equivalent source node bandwidth when each of the non-content requesting peer nodes are forwarding data.

2. The method as set forth in claim 1, further comprising defining the capacity of the node in terms of a bandwidth of the node.

3. The method as set forth in claim 2, wherein the bandwidth is the upload bandwidth of the node.

4. The method as set forth in claim 1, wherein a size of each of the plurality of blocks is less than a maximum transmission unit (MTU) of the computer network.

5. The method as set forth in claim 4, wherein the content block size is approximately 1 kilobyte.

6. The method as set forth in claim 1, wherein a size of each of the plurality of blocks is a compromise between a granularity of distribution and an overhead required for identifying the blocks.

7. The method as set forth in claim 1, wherein the assigned node is a content requesting peer node that requests a copy of the content.

8. The method as set forth in claim 1, wherein the assigned node is a non-content requesting peer node that does not requests a copy of the content.

9. The method as set forth in claim 1, wherein the assigned node is a source node.

10. The method as set forth in claim 1, further comprising using a bandwidth control strategy to enable dynamic redistribution of blocks based on changes in the capacity of the node.

11. The method as set forth in claim 10, wherein the bandwidth control strategy further comprises employing redistribution queues between each pair of the nodes in the network.

12. The method as set forth in claim 11, further comprising constructing redistribution queues using a transport control protocol (TCP).

13. The method as set forth in claim 12, wherein the redistribution queues are TOP send and receive buffers.

14. The method as set forth in claim 11, further comprising constructing redistribution queues using application buffers implemented on top of a user datagram protocol (UDP).

15. The method as set forth in claim 1, further comprising defining a forward link as a connection between the source node and the assigned node, where the content blocks sent in the connection are to be further redistributed.

16. The method as set forth in claim 1, further comprising defining a delivery link as a connection between the assigned node and another content requesting peer node, where the content blocks sent in the connection are not to be further redistributed.

17. The method as set forth in claim 1, wherein the computer network is a peer-to-peer network.

18. A computer-readable storage medium having stored and encoded thereon computer-executable instructions for performing the computer-implemented method recited in claim 1.

19. A computer-implemented method for delivering content from a source node to a plurality of content-requesting nodes on a computer network, comprising:

splitting the content to be delivered into a plurality of smaller content blocks;

assigning each of the content blocks to a single node for redelivery only by the single assigned node in proportion to a capacity of the single assigned node such that a node having a larger capacity is assigned more blocks and a node having a smaller capacity is assigned fewer blocks;

sending each of the content blocks from the source node to its assigned not, if the assigned node is not the source node;

redistributing the content blocks from the assigned node to the remaining content requesting peer nodes; and

adjusting a content sending rate, θ

, in a dynamic manner based on a maximum throughput under prevailing conditions by using the equation;

$\mathrm{\theta <br><br>}=\{\begin{array}{cc}{B}_s& \mathrm{if}<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>B_s\le <br><br>B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2},\\ \left(B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2}\right)+\frac{B_s-\left(B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2}\right)}{N_1}& \mathrm{if}<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>B_s\ge <br><br>B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2},\end{array}<br><br><br><br>\mathrm{with}<br><br><br><br>B_{s<br><br><br><br>1}=\frac{N_1}{N_1-1}<br><br><br><br>B_1<br><br><br><br>\mathrm{and}<br><br><br><br>B_{s<br><br><br><br>2}=\frac{N_2}{N_1}<br><br><br><br>B_2,$

where B_S is a bandwidth of the source node, N₁ is a number of content-requesting peer nodes, B₁ is an average bandwidth of the N₁ content-requesting peer nodes, N₂ is a number of non-content requesting peer nodes, B₂ is an average bandwidth of the N₂ non-content requesting peer nodes, B_s1 is an equivalent source node bandwidth when each of the content requesting peer nodes are forwarding data, and B_s2 is an equivalent source node bandwidth when each of the non-content requesting peer nodes are forwarding data.

20. The computer-implemented method of claim 19, further comprising employing redistribution queues between nodes of the computer network to effectively manage dynamic changes in the computer network.

21. The computer-implemented method of claim 19, wherein the computer network is a peer-to-peer network.

22. The computer-implemented method of claim 21, wherein the assigned node is the content-requesting peer node.

23. The computer-implemented method of claim 21, wherein the assigned node is non-content-requesting peer node that does not request the content.

24. The computer-implemented method of claim 19, further comprising varying a number of content blocks assigned to the node such that the amount of content being redistributed by a node is variable.

25. The computer-implemented method of claim 24, further comprising varying the number of content blocks assigned to the node based on a capacity of the node.

26. The computer-implemented method of claim 25, further comprising defining the capacity of the node in terms of an upload bandwidth of the node.

27. A computer-readable storage medium having stored and encoded thereon computer-executable instructions for performing the computer-implemented method recited in claim 19.

28. A method for distributing content between nodes in a peer-to-peer computer network, comprising:

separating the content into a number of smaller content blocks;

assigning each of the content blocks only to a single node for redelivery only by the single assigned node in proportion to a capacity of the single assigned node such that a node having a larger capacity is assigned more blocks and a node having a smaller capacity is assigned fewer blocks;

employing redistribution queues between the nodes;

reassigning the content blocks using the redistribution queues such that any changes in the upload bandwidth of the assigned node results in a change to the number of blocks assigned to that node for redistribution; and

adjusting a content sending rate, θ

, in a dynamic manner based on a maximum throughput under prevailing conditions by using the equation;

$\mathrm{\theta <br><br>}=\{\begin{array}{cc}{B}_s& \mathrm{if}<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>B_s\le <br><br>B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2},\\ \left(B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2}\right)+\frac{B_s-\left(B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2}\right)}{N_1}& \mathrm{if}<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>B_s\ge <br><br>B_{s<br><br><br><br>1}+B_{s<br><br><br><br>2},\end{array}<br><br><br><br>\mathrm{with}<br><br><br><br>B_{s<br><br><br><br>1}=\frac{N_1}{N_1-1}<br><br><br><br>B_1<br><br><br><br>\mathrm{and}<br><br><br><br>B_{s<br><br><br><br>2}=\frac{N_2}{N_1}<br><br><br><br>B_2,$

where B_S is a bandwidth of the source node, N₁ is a number of content-requesting peer nodes, B₁ is an average bandwidth of the N₁ content-requesting peer nodes, N₂ is a number of non-content requesting peer nodes, B₂ is an average bandwidth of the N₂ non-content requesting peer nodes, B_s1 is an equivalent source node bandwidth when each of the content requesting peer nodes are forwarding data, and B_s2 is an equivalent source node bandwidth when each of the non-content requesting peer nodes are forwarding data.

29. The method of claim 28, wherein the redistribution queues are transport control protocol (TCP) send and receive buffers.

30. The method of claim 28, further comprising generating the redistribution queues using application buffers implemented on top of a user datagram protocol (UDP).

31. The method of claim 28, further comprising defining a forward link as a connection between nodes having content blocks to be further redistributed.

32. The method of claim 31, further comprising:

removing one content block from an incoming forward link and defining it as the current content block; and

copying the current content block onto outgoing delivery links of all content-requesting peer nodes.

33. The method of claims 32, further comprising waiting to remove another content block from the incoming forward link until the current content block has been copied to each of the outgoing delivery links.

34. The method of claim 31, further comprising defining a delivery link as a connection between nodes having content blocks not to be further redistributed.

35. The method of claim 34, further comprising:

determining that an arriving content block was sent by one of;

(a) a content-requesting node;

(b) a non-content-requesting node; and

removing the arriving content block from the delivery link as soon as the block arrives.

36. The method of claim 34, further comprising:

determining that an arriving content block was sent by a source node; and

removing arriving content blocks from the delivery link only when a receiving buffer length of the forward link from the source node is greater than a threshold value.

37. The method of claim 34, further comprising:

determining whether there is space available for a content block in the forward link from the source node to the content-requesting node;

placing the content block into a buffer to be sent to a corresponding content-requesting node; and

redistributing the content block to other content-requesting peer nodes through corresponding delivery links.

38. The method of claim 37, further comprising:

determining that no space is available for a content block in the forward link from the source node to the content-requesting node;

determining whether space is available in forward links to the non-content-requesting peer nodes; and

if space is available, placing the content block into a buffer to be sent to a corresponding non content-requesting node; and

redistributing the content block to other content-requesting peer nodes through corresponding delivery links.

39. The method of claim 38, further comprising:

determining that no space is available for a content block in the forward link from the source node to the content-requesting and non-content-requesting node;

determining whether space is available in all delivery links from the source node to all the content-requesting peer nodes; and

if space is available, placing the content block into buffers of all delivery links from the source node to all the content-requesting peer nodes.

40. The method of claim 39, further comprising:

determining that no space is available for a content block in the forward link from the source node to the content-requesting and non-content-requesting node and no space is available in any of the delivery link from the source node to a content-requesting peer nodes; and

if no space is available, waiting for a short while and then retrying.