Predictive overlay network architecture
The predictive overlay network architecture of the present invention improves the performance of applications distributing digital content among nodes of an underlying network such as the Internet by establishing and reconfiguring overlay network topologies over which associated content items are distributed. The present invention addresses not only frequently changing network congestion, but also interdependencies among nodes and links of prospective overlay network topologies. The present invention provides a prediction engine that monitors metrics and predicts the relay capacity of individual nodes and links (as well as demand of destination nodes) over time to reflect the extent to which the relaying of content among the nodes of an overlay network will be impacted by (current or future) underlying network congestion. The present invention further provides a topology selector that addresses node and link interdependencies while redistributing excess capacity to determine an overlay network topology that satisfies application-specific performance criteria.
1. A method for determining an overlay network topology that satisfies a set of one or more application-specific performance criteria with respect to the distribution of one or more segments of a content item along the overlay network, the overlay network topology including a plurality of nodes of the overlay network and a plurality of links, each link logically interconnecting a pair of the plurality of nodes to facilitate the distribution of the one or more segments between the pair of nodes along that link, the method comprising:
(a) periodically processing a plurality of metrics during successive time periods, each metric reflecting, for each time period, an attribute associated with the nodes or links of a current overlay network topology employed during that time period, to generate processed metrics that reflect node-relaying attributes and link-relaying attributes of the current overlay network topology;
(b) predicting, based upon the processed metrics associated with nodes and links of a prospective overlay network topology, the node-relaying capacity and link-relaying capacity of those nodes and links;
(c) determining, based at least in part upon the predicted node-relaying capacity and link-relaying capacity of those nodes and links, whether the prospective overlay network topology satisfies the performance criteria.
2. The method of claim 1 , wherein the steps of determining the node-relaying capacity and determining the link-relaying capacity comprise excluding capacity-limited observations.
3. The method of claim 1 , wherein processing the plurality of metrics comprises filtering to exclude demand-limited observations, and wherein the processed metrics exclude demand-limited observations.
4. The method of claim 1 , further comprising determining an optimal overlay network topology based on the set of one or more application-specific performance criteria.
5. A method for reconfiguring overlay network topologies over which content items are distributed, wherein each overlay network topology includes a plurality of network nodes and a plurality of links interconnecting the plurality of network nodes; the method comprising the following steps:
(a) generating a plurality of metrics with respect to a current overlay network topology;
(b) filtering the plurality of metrics to exclude demand-limited observations;
(c) generating, based upon the filtered plurality of metrics, a plurality of predictions regarding a set of specified nodes and links;
(d) identifying a prospective overlay network topology based upon the plurality of predictions;
(e) generating viewer indicator predictions indicating whether each network node will be part of the prospective overlay network topology; and
(f) generating session duration predictions indicating the duration of time during which those network nodes that will be part of the prospective overlay network topology will remain part of the prospective overlay network topology.
6. The method of claim 5 , wherein the prospective overlay network topology satisfies performance criteria representing one or more constraints on the performance of the specified nodes and links.
7. The method of claim 5 , wherein each overlay network topology is a peer-based overlay network topology.
8. The method of claim 5 , wherein the plurality of predictions include predictions of the node-relaying capacity of the specified nodes and the link-relaying capacity of the specified links.
9. The method of claim 5 , wherein the plurality of metrics include node metrics, link metrics and a timestamp during which the node metrics and link metrics were obtained.
10. The method of claim 5 , wherein the steps of determining the node-relaying capacity and determining the link-relaying capacity comprise excluding capacity-limited observations.
11. The method of claim 5 , further comprising generating an optimal overlay network topology that satisfies the performance criteria.
12. An adaptive topology server having a processor and a memory that reconfigures overlay network topologies over which content items are distributed, wherein each overlay network topology includes a plurality of network nodes and a plurality of links interconnecting the plurality of network nodes; the adaptive topology server comprising:
(a) a metrics processor that generates a plurality of metrics with respect to a current overlay network topology, wherein the plurality of metrics exclude demand-limited observations, and wherein the plurality of metrics generated by the metrics processor includes node metrics, link metrics and a timestamp during which the node metrics and link metrics were obtained;
(b) a prediction engine that generates, based upon the plurality of metrics, a plurality of predictions regarding a set of specified nodes and links; and
(c) a topology selector that obtains from the prediction engine a plurality of predictions with respect to the set of specified nodes and links and identifies a prospective overlay network topology based upon the plurality of predictions, wherein the topology selector identifies a prospective overlay network topology that satisfies performance criteria representing one or more performance constraints.
13. The adaptive topology server of claim 12 , wherein each overlay network topology is a peer-based overlay network topology.
14. The adaptive topology server of claim 12 , wherein the prediction engine generates viewer indicator predictions indicating whether each network node will be part of the prospective overlay network topology.
15. The adaptive topology server of claim 12 , wherein the prediction engine generates session duration predictions indicating the duration of time during which those network nodes that will be part of the prospective overlay network topology will remain part of the prospective overlay network topology.
16. The adaptive topology server of claim 12 , wherein the prediction engine generates the node-relaying capacity of the specified nodes and the link-relaying capacity of the specified links.
17. The adaptive topology server of claim 12 , wherein the topology determines an optimal overlay network topology based on the set of one or more application-specific performance criteria.
18. The adaptive topology server of claim 12 , wherein the steps of determining the node-relaying capacity and determining the link-relaying capacity comprise excluding capacity-limited observations.