System and method for assigning requests in a content distribution network

Patent metadata

Field	Value
Publication number	US-9098464-B2
Application number	US-201314094192-A
Country	US
Kind code	B2
Filing date	Dec 2, 2013
Priority date	Dec 5, 2008
Publication date	Aug 4, 2015
Grant date	Aug 4, 2015

Abstract

A method includes receiving demand information from edge routers, estimating an optimal request distribution based on the demand information using a bicriteria approximation algorithm, wherein initial programming states for the estimation are specified by (u, F, D, F S , D S , F exp , Fimp), where u is a current node, F is a vector representing an available facility for large capacity, D is a vector representing an outsourced large client, F S is an amount of cache server capacity offered to small clients, D S is a total demand of outsourced small clients, F exp is an index of a cache server being exported from a subtree, and F imp is an index of another cache server of another subtree that is being utilized, and providing each of the edge routers with anycast route information for the cache servers.

First claim

What is claimed is:

1. A system for assigning requests in a content distribution network, the system comprising:
a memory that stores instructions;
a process that executes the instructions to perform operations, the operations comprising:
estimating, by using a bicriteria approximation algorithm, an optimal request distribution based on demand information received from an edge router, wherein initial programming states for the optimal request distribution are specified by (u, F, D, F S , D S , F exp , F imp ), where u is a current node, F is a vector representing an available facility for large capacity, D is a vector representing an outsourced large client, F S is an amount of cache server capacity offered to small clients, D S is a total demand of outsourced small clients, F exp is an index of a first cache server being exported from a first subtree, and F imp is an index of second cache server of a second subtree, wherein the first and second cache servers are from a plurality of cache servers; and

providing the edge router with route information for the plurality of cache servers, wherein, based on the optimal request distribution, content is provided to a client system in response to requests made by the client system.

2. The system of claim 1 , wherein the operations further comprise receiving the demand information from the edge router.

3. The system of claim 1 , wherein the operations further comprise providing the edge router with an anycast address when providing the edge router with the route information.

4. The system of claim 1 , wherein the operations further comprise receiving server capacity information for the plurality of cache servers.

5. The system of claim 4 , wherein the operations further comprise estimating the optimal request distribution based on the server capacity information for the plurality of cache servers.

6. The system of claim 1 , wherein the operations further comprise assigning the requests to the plurality of cache servers based on the optimal request distribution.

7. The system of claim 1 , wherein the operations further comprise rounding the demand information, and wherein the operations further comprise estimation the optimal request distribution based on rounding the demand information.

8. The system of claim 1 , wherein the operations further comprise assigning the edge router to a subset of the plurality of cache servers based on recursively determining assignments from a root node.

9. A method for assigning requests in a content distribution network, the method comprising:
dividing, based on demand information, a plurality of edge routers into edge routers with large demands and edge routers with small demands;
combining, by utilizing instructions from memory that are executed by a processor, a subset of the edge routers with the small demands into a large demand router;
recursively assigning a cache server to an edge router of the plurality of edge routers;
determining route information for the cache server based on the edge router assigned to the cache server; and
providing the route information to the edge router assigned to the cache server.

10. The method of claim 9 , further comprising receiving the demand information from the plurality of edge routers.

11. The method of claim 9 , further comprising providing the edge router with an anycast address when providing the edge router with the route information.

12. The method of claim 9 , further comprising receiving server capacity information for the cache server.

13. The method of claim 12 , further comprising estimating an optimal request distribution based on the server capacity information for the cache server.

14. The method of claim 13 , further comprising assigning a request for content to the cache server based on the optimal request distribution.

15. The method of claim 9 , further comprising rounding the demand information, and further comprising estimating an optimal request distribution based on rounding the demand information.

16. A computer-readable device comprising instructions, which when loaded and executed by a processor of the device, cause the processor to perform operations, the operations comprising:
estimating, by using a bicriteria approximation algorithm, an optimal request distribution based on demand information received from an edge router, wherein initial programming states for the optimal request distribution are specified by (u, F, D, F S , D S , F exp , F imp ), where u is a current node, F is a vector representing an available facility for large capacity, D is a vector representing an outsourced large client, F S is an amount of cache server capacity offered to small clients, D S is a total demand of outsourced small clients, F exp is an index of a first cache server being exported from a first subtree, and F imp is an index of second cache server of a second subtree, wherein the first and second cache servers are from a plurality of cache servers; and
providing the edge router with route information for the plurality of cache servers, wherein, based on the optimal request distribution, content is provided to a client system in response to requests made by the client system.

17. The computer-readable device of claim 16 , wherein the operations further comprise providing the edge router with an anycast address when providing the edge router with the route information.

18. The computer-readable device of claim 16 , wherein the operations further comprise receiving server capacity information for the plurality of cache servers.

19. The computer-readable device of claim 18 , wherein the operations further comprise estimating the optimal request distribution based on the server capacity information for the plurality of cache servers.

20. The computer-readable device of claim 16 , wherein the operations further comprise assigning the requests to the plurality of cache servers based on the optimal request distribution.

Assignees

• At & T Ip Ii Lp

Inventors

• Hajiaghayi Mohammad Taghi
• Bateni Mohammad Hossein

Classifications

• G06F15/173 Primary

  using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake · CPC title

• H04L67/2842

  Electricity · mapped topic

• H04L67/288 Primary

  Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level · CPC title

• H04L67/568

  Storing data temporarily at an intermediate stage, e.g. caching · CPC title