Distributed flow mechanism for peer-to-peer streaming
View Patent ↗The invention concerns a method for flow control in a peer-to-peer live streaming communication network comprising a plurality of nodes characterized in that the rate at which a node sends information to another node increases proportionally to the quantity of information present at node which has not yet reached node and decreases proportionally to a value attached to the link connecting node to node.
1. A method of distributing content to a first node in a peer-to-peer live streaming communication network from a group of neighboring nodes for the first node, wherein the network comprises a plurality of nodes that includes the first node and the neighboring nodes for the first node, wherein each neighboring node is configured to store a respective quantity of said content for distribution to the first node, the method comprising:
determining a usefulness value for each node in the group of neighboring nodes, wherein the usefulness value corresponding to a particular neighboring node in the group is directly proportional to the respective quantity of said content for distribution to the first node that is stored at the particular neighboring node and that has not yet been received by the first node from any neighboring node;
determining a cost value for each link defined between the first node and each neighboring node from the group of neighboring nodes, wherein the cost value for each respective link is determined based upon one or more of: an observed packet round trip time on the corresponding link, a packet loss rate on the corresponding link, an explicit congestion notification mark defined the an IETF ECN (Internet Engineering Task Force—Explicit Congestion Notification) Standard, and a constant value defined for the peer-to-peer network; and
adapting, for each particular neighboring node in the group of neighboring nodes for the first node, a data rate for the link between the first node and a particular neighboring node in said group to be optimal based on a difference between the usefulness value for the particular neighboring node and the cost value for the link between the particular neighboring node and the first node, wherein the difference is realized by:
increasing the data rate for said link based on a higher usefulness value being determined for the particular neighboring node and correspondingly decreasing the data rate for said link based on a lower usefulness value being determined for the particular neighboring node; and
decreasing the data rate for said link based on a higher cost value being determined for said link and increasing the data rate for said link based on a lower cost value being determined for said link.
2. The method of claim 1 , further including using Random Linear Network Coding, and wherein the respective quantity of content stored in a neighboring node which has not yet been received by the first node is expressed as a difference between a rank of a matrix obtained by merging a matrix of coefficients of the first node with a matrix of coefficients of the particular neighboring node of the group and the number of linearly independent coefficients at the first node.
3. The method as defined in claim 2 , wherein the content is divided into a plurality of N chunks and wherein each neighboring node receives a random linear combination of the N chunks of content, where N is an integer representing a number of said neighboring nodes for the first node.
4. The method of claim 1 , further including estimating the respective quantity of content stored in a neighboring at a particular neighboring node of the group based on limited signaling exchanges between the first node and the particular neighboring node.
5. The method of claim 1 , further including, at a second node of said plurality of nodes, receiving a list of active nodes in the network, and providing information about neighboring nodes to a further node that is being added to the network.
6. The method defined in claim 1 , wherein the constant value defined for the peer-to-peer network represents a weight for the particular link, said weight being inversely proportional to a desirability evidenced for utilizing the link for distributing said content.
7. The method defined in claim 1 , wherein said method is performed by the first node.
8. The method defined in claim 1 , wherein said method is performed by a node from said plurality of nodes other than the first node.
9. The method defined in claim 1 , wherein said content is divided into one of: a plurality of packets or a plurality of chunks.
10. The method defined in claim 1 , wherein said determining the cost value for each link is determined based upon a combination of: the observed packet round trip time on the corresponding link, the packet loss rate on the corresponding link, the explicit congestion notification mark defined the an IETF ECN Standard, and the constant value defined for the peer-to-peer network.
11. A method of distributing content to a first node in a peer-to-peer live streaming communication network from a group of neighboring nodes for the first node, wherein the network comprises a plurality of nodes that includes the first node and the neighboring nodes for the first node, wherein each neighboring node is configured to store a respective quantity of said content for distribution to the first node, the method comprising:
determining a usefulness value for each node in the group of neighboring nodes, wherein the usefulness value corresponding to a particular neighboring node in the group is directly proportional to the respective quantity of said content for distribution to the first node that is stored at the particular neighboring node and that has not yet been received by the first node from any neighboring node;
determining a cost value for each link defined between the first node and each neighboring node from the group of neighboring nodes, wherein the cost value for each respective link is determined based upon one or more of: an observed packet round trip time on the corresponding link, a packet loss rate on the corresponding link, an explicit congestion notification mark defined the an IETF ECN (Internet Engineering Task Force—Explicit Congestion Notification) Standard, and a constant value defined for the peer-to-peer network; and
adapting, for each particular neighboring node in the group of neighboring nodes for the first node, a data rate for the link between the first node and a particular neighboring node in said group to be optimal based on a difference between the usefulness value for the particular neighboring node and the cost value for the link between the particular neighboring node and the first node, wherein the difference is realized by:
increasing the data rate for said link connecting the particular neighboring node to the first node proportionally with the usefulness value determined for the particular neighboring node; and
decreasing the data rate for said link connecting the particular neighboring node to the first node proportionally with the cost value determined for the link associated with the particular neighboring node.
12. The method of claim 11 , further including using Random Linear Network Coding, and wherein the respective quantity of content stored in a neighboring node which has not yet been received by the first node is expressed as a difference between a rank of a matrix obtained by merging a matrix of coefficients of the first node with a matrix of coefficients of the particular neighboring node of the group and the number of linearly independent coefficients at the first node.
13. The method as defined in claim 12 , wherein the content is divided into a plurality of N chunks and wherein each neighboring node receives a random linear combination of the N chunks of content, where N is an integer representing a number of said neighboring nodes for the first node.
14. The method of claim 11 , further including estimating the respective quantity of content stored in a neighboring at a particular neighboring node of the group based on limited signaling exchanges between the first node and the particular neighboring node.
15. The method of claim 11 , further including, at a second node of said plurality of nodes, receiving a list of active nodes in the network, and providing information about neighboring nodes to a further node that is being added to the network.
16. The method defined in claim 11 , wherein the constant value defined for the peer-to-peer network represents a weight for the particular link, said weight being inversely proportional to a desirability evidenced for utilizing the link for distributing said content.
17. The method defined in claim 11 , wherein said method is performed by the first node.
18. The method defined in claim 11 , wherein said method is performed by a node from said plurality of nodes other than the first node.
19. The method defined in claim 11 , wherein said content is divided into one of: a plurality of packets or a plurality of chunks.
20. The method defined in claim 11 , wherein said determining the cost value for each link is determined based upon a combination of: the observed packet round trip time on the corresponding link, the packet loss rate on the corresponding link, the explicit congestion notification mark defined the an IETF ECN Standard, and the constant value defined for the peer-to-peer network.
21. A node in a peer-to-peer live streaming communication network for distributing content to a first node from a group of neighboring nodes for the first node, wherein the network comprises a plurality of nodes that includes the node, the first node, and the neighboring nodes for the first node, wherein said node is one of the first node and the neighboring nodes for the first node, wherein each neighboring node is configured to store a respective quantity of said content for distribution to the first node, said node comprising a memory and a processor coupled to said memory, the processor configured for:
determining a usefulness value for each node in the group of neighboring nodes, wherein the usefulness value corresponding to a particular neighboring node in the group is directly proportional to the respective quantity of said content for distribution to the first node that is stored at the particular neighboring node and that has not yet been received by the first node from any neighboring node;
determining a cost value for each link defined between the first node and each neighboring node from the group of neighboring nodes, wherein the cost value for each respective link is determined based upon one or more of: an observed packet round trip time on the corresponding link, a packet loss rate on the corresponding link, an explicit congestion notification mark defined the an IETF ECN (Internet Engineering Task Force—Explicit Congestion Notification) Standard, and a constant value defined for the peer-to-peer network; and
adapting, for each particular neighboring node in the group of neighboring nodes for the first node, a data rate for the link between the first node and a particular neighboring node in said group to be optimal based on a difference between the usefulness value for the particular neighboring node and the cost value for the link between the particular neighboring node and the first node, wherein the difference is realized by:
increasing the data rate for said link connecting the particular neighboring node to the first node proportionally with the usefulness value determined for the particular neighboring node; and
decreasing the data rate for said link connecting the particular neighboring node to the first node proportionally with the cost value determined for the link associated with the particular neighboring node.