Network and method for delivering content while minimizing congestion costs by jointly optimizing forwarding and caching strategies
Embodiments include a unified framework for minimizing congestion-dependent network cost by jointly optimizing forwarding and caching strategies that account for link congestion between neighboring nodes. As caching variables are integer-constrained, the resulting optimization problem is a non-deterministic polynomial time (NP)-hard problem. Embodiments relax the optimization problem, where caching variables are real-valued. Embodiments include optimality conditions for the relaxed problem. Embodiments include an adaptive and distributed joint forwarding and caching method, based on a conditional gradient method. Embodiments elegantly yield feasible routing variables and integer caching variables at each iteration, and can be implemented in a distributed manner with low complexity and overhead. Over a wide range of network topologies, simulation results show that embodiments have significantly better delay performance in the low to moderate request rate regions. Furthermore, embodiments complement each other in delivering superior delay performance across the range of request arrival rates, compared to existing methods.
1. A content delivery network, comprising:
nodes communicatively coupled to neighboring nodes via respective links, each node configured to cache a unit of content and send a content request to an upstream neighboring node to request the unit of content if not cached,
a given node among the nodes configured to calculate (i) marginal cost of caching the unit of content, and (ii) marginal cost of forwarding the content request to at least one neighboring node, the marginal cost of the forwarding the content request and the marginal cost of the caching the unit of content both being dependent on both link congestion between the given node and the at least one neighboring node and link congestion on links of an upstream path of nodes toward and including a source node, the source node guaranteed to have the unit of content available, each node along the upstream path being configured to perform a respective calculation of the cost and to report same to its downstream neighboring node making the content request, the given node configured to direct content of the unit of content for delivery to a destination node.
2. The content delivery network of claim 1 , further comprising using the marginal cost of the forwarding of the content request to update variables of the caching and the forwarding by solving a linear program with a gradient, each iteration of the linear program resulting in an integer value.
3. The content delivery network of claim 1 , wherein the unit of content comprises data units or chunks thereof of equal size.
4. The content delivery network of claim 1 , wherein the total arrival rate of requests at the given node for the unit of content includes content requests from outside of the network and content requests from within the network.
5. The content delivery network of claim 1 , further comprising calculating cache scores from a product of a total arrival rate of requests at the given node for the unit of content and corresponding marginal costs of forwarding the requests; and
further comprising determining whether to cache a unit of content at the given node based on its corresponding cache score.
6. The content delivery network of claim 5 , wherein determining whether to cache the unit of content is performed based upon a ranking of highest values of the cache scores associated with respective units of content.
7. The content delivery network of claim 5 , wherein a rate of arrival of requests for the unit of content changes over time, and wherein each node adapts to the changes by (i) making a decision to cache the unit of content based upon the cache scores, and (ii) making a decision to forward the requests for the unit of content based upon the marginal forwarding cost.
8. A computer-implemented method for delivering content in a network, the computer-implemented method comprising:
by each node, communicatively coupled to neighboring nodes via respective links in the network, caching a unit of content and sending a content request to an upstream neighboring node to request the unit of content if not cached,
by a given node among the nodes, calculating (i) marginal cost of caching the unit of content, and (ii) marginal cost of forwarding the content request to at least one neighboring node, the marginal cost of the forwarding the content request and the marginal cost of the caching the unit of content both being dependent on both link congestion between the given node and the at least one neighboring node and link congestion on links of an upstream path of nodes toward and including a source node, the source node guaranteed to have the unit of content available, each node along the upstream path performing a respective calculation of the cost and reporting same to its downstream neighboring node making the content request, the given node directing content of the unit of content for delivery to a destination node.
9. The method of claim 8 , further comprising using the marginal cost of the forwarding of the content request to update variables of the caching and the forwarding by solving a linear program with a gradient, each iteration of the linear program resulting in an integer value.
10. The method of claim 8 , wherein the unit of content comprises data units or chunks thereof of equal size.
11. The method of claim 8 , wherein the total arrival rate of requests at the given node for the unit of content includes content requests from outside of the network and content requests from within the network.
12. The method of claim 8 , further comprising calculating cache scores from a product of a total arrival rate of requests at the given node for the unit of content and corresponding marginal costs of forwarding the requests; and
further comprising determining whether to cache a unit of content at the given node based on its corresponding cache score.
13. The method of claim 12 , wherein determining whether to cache the unit of content is performed based upon a ranking of highest values of the cache scores associated with respective units of content.
14. The method of claim 12 , wherein a rate of arrival of requests for the unit of content changes over time, and wherein each node adapts to the changes by (i) making a decision to cache the unit of content based upon the cache scores, and (ii) making a decision to forward the requests for the unit of content based upon the marginal forwarding cost.
15. A network node communicatively coupled to neighboring nodes via respective links, the network node configured to cache a unit of content and send a content request to an upstream neighboring node to request the unit of content if not cached at the network node, the network node comprising:
a network interface; and
a processor configured to calculate (i) marginal cost of caching the unit of content, and (ii) marginal cost of forwarding the content request to at least one neighboring node, the marginal cost of the forwarding the content request and the marginal cost of the caching the unit of content both being dependent on both link congestion between the network node and the at least one neighboring node and link congestion on links of an upstream path of nodes toward and including a source node, the source node guaranteed to have the unit of content available, each node along the upstream path being configured to perform a respective calculation of the cost and to report same to its downstream neighboring node making the content request, the processor configured to direct content of the unit of content for delivery to a destination node via the network interface.
16. The network node of claim 15 , wherein the processor is further configured to use the marginal cost of the forwarding of the content request to update variables of the caching and the forwarding by solving a linear program with a gradient, each iteration of the linear program resulting in an integer value.
17. The network node of claim 15 , wherein the unit of content comprises data units or chunks thereof of equal size.
18. The network node of claim 15 , wherein the total arrival rate of requests at the network node for the unit of content includes content requests from outside of the network and content requests from within the network.
19. The network node of claim 15 , wherein the processor is further configured to calculate cache scores from a product of a total arrival rate of requests at the network node for the unit of content and corresponding marginal costs of forwarding the requests;
and wherein the processor is further configured to determine whether to cache a unit of content at the network node based on its corresponding cache score.
20. The network node of claim 19 , wherein the processor, in determining whether to cache the unit of content, is further configured to perform a ranking of highest values of the cache scores associated with respective units of content and cache the unit of content based on the ranking.
21. The network node of claim 19 , wherein a rate of arrival of requests for the unit of content changes over time, and wherein the processor adapts the network node to the changes by (i) making a decision to cache the unit of content based upon the cache scores, and (ii) making a decision to forward the requests for the unit of content based upon the marginal forwarding cost.
22. A computer program product including a non-transitory computer-readable medium having processor-executable instructions stored thereon, the instructions, when loaded and executed by a processor, cause a node in a network, the node communicatively coupled to neighboring nodes in the network via respective links, to:
cache a unit of content and send a content request to an upstream neighboring node to request the unit of content if not cached; and
calculate (i) marginal cost of caching the unit of content, and (ii) marginal cost of forwarding the content request to at least one neighboring node, the marginal cost of forwarding the content request and the marginal cost of caching the unit of content both being dependent on both link congestion between the given node and the at least one neighboring node and link congestion on links of an upstream path of nodes toward and including a source node, the source node guaranteed to have the unit of content available, each node along the upstream path performing a respective calculation of the cost and reporting same to its downstream neighboring node making the content request, the given node directing content of the unit of content for delivery to a destination node.