Adaptive overlay network architecture

Abstract

The adaptive 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 performance criteria with respect to the distribution of one or more segments of a content item, the overlay network topology including a plurality of nodes 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 the following steps:
 (a) generating a node-relaying capacity for each of a plurality of specified nodes;   (b) generating a link-relaying capacity for each of a plurality of specified links interconnecting the specified nodes; and   (c) determining, based at least in part upon the generated node-relaying capacities and link-relaying capacities, whether a prospective overlay network topology satisfies the performance criteria.   
     
     
         2 . The method of  claim 1 , wherein the overlay network topology is a peer-based overlay network topology. 
     
     
         3 . The method of  claim 1 , wherein the node-relaying capacities and link-relaying capacities are predicted based upon a plurality of metrics observed from the distribution of content item segments along one or more prior overlay network topologies. 
     
     
         4 . The method of  claim 1 , wherein the prospective overlay network topology is optimized for the fewest number of collectors. 
     
     
         5 . The method of  claim 1 , wherein the specified nodes are placed in the prospective overlay network topology based on the order of their node-relaying capacities, and the specified links are assigned based upon whether their link-relaying capacities satisfy the performance criteria. 
     
     
         6 . A method for determining an overlay network topology satisfying a set of one or more performance criteria with respect to the distribution of one or more segments of a content item, the overlay network topology including a plurality of nodes 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 system comprising:
 (a) generating a node-relaying capacity for each of a plurality of specified nodes;   (b) generating a link-relaying capacity for each of a plurality of specified links interconnecting the specified nodes; and   (c) determining, based at least in part upon the generated node-relaying capacities and link-relaying capacities, whether a prospective overlay network topology satisfies the performance criteria, wherein the prospective overlay network topology is optimized for the fewest number of collectors.   
     
     
         7 . The method of  claim 6 , wherein the overlay network topology is a peer-based overlay network topology. 
     
     
         8 . The method of  claim 6 , wherein the node-relaying capacities and link-relaying capacities are predicted based upon a plurality of metrics observed from the distribution of content item segments along one or more prior overlay network topologies. 
     
     
         9 . The method of  claim 6 , wherein the specified nodes are placed in the prospective overlay network topology based on the order of their node-relaying capacities, and the specified links are assigned based upon whether their link-relaying capacities satisfy the performance criteria. 
     
     
         10 . A method for determining an overlay network topology satisfying a set of one or more performance criteria with respect to the distribution of one or more segments of a content item, the overlay network topology including a plurality of nodes 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 system comprising:
 (a) generating a node-relaying capacity for each of a plurality of specified nodes;   (b) generating a link-relaying capacity for each of a plurality of specified links interconnecting the specified nodes; and   (c) determining, based at least in part upon the generated node-relaying capacities and link-relaying capacities, whether a prospective overlay network topology satisfies the performance criteria, wherein the prospective overlay network topology is optimized for the fewest number of collectors by placing nodes in the prospective overlay network topology based on the order of their node-relaying capacities, and assigning specified links based upon whether their link-relaying capacities satisfy the performance criteria.   
     
     
         11 . The method of  claim 10 , wherein the overlay network topology is a peer-based overlay network topology. 
     
     
         12 . The method of  claim 10 , wherein the node-relaying capacities and link-relaying capacities are predicted based upon a plurality of metrics observed from the distribution of content item segments along one or more prior overlay network topologies. 
     
     
         13 . The method of  claim 12 , wherein demand-limited observed metrics are excluded from the plurality of observed metrics. 
     
     
         14 . The method of  claim 10 , wherein the prospective overlay network topology is optimized for the fewest number of collectors by analyzing a plurality of n-collector prospective overlay network topologies concurrently. 
     
     
         15 . The method of  claim 10 , wherein the prospective overlay network topology is optimized for the fewest number of collectors by analyzing a plurality of n-collector prospective overlay network topologies consecutively beginning with a single-collector prospective overlay network topology.