# US 10,320,930 B2 · Method and system for providing network caches > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,320,930 B2 - Document ID: US10320930B2 - Status: Granted - Kind: B2 - Application number: 14/928,165 - Filed: 2015-10-30 - Published: 2017-05-04 - Granted: 2019-06-11 - Earliest claimed: 2015-10-30 - Assignees: Huawei Technologies Co., Ltd. - Applicants: Ngoc-Dung Dao; Hamidreza Farmanbar; Xu Li - Inventors: Ngoc-Dung Dao; Hamidreza Farmanbar; Xu Li - Web page: https://patentgrep.com/patent/US10320930B2 ## CPC - H04L 67/568: Storing data temporarily at an intermediate stage, e.g. caching - H04L 43/16: Threshold monitoring - H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) - H04L 43/0852: Delays - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A method and apparatus for deploying a set of network caches in a communication network is provided. A set of network nodes is identified such that, for each of a set of client device locations, and for at least a number c of the set of nodes, output of a coverage cost function is no greater than a threshold. The coverage cost function receives as input a client location and one of the nodes. The set of network caches are then located at the respective set of nodes. The set of network nodes can be selected from plural candidate sets based on a utility criterion. The candidate sets can be generated by successive addition and/or removal of nodes. Information obtained from a Traffic Engineering function can be used to direct selection of the set of nodes. A cache-client association can be generated for directing clients to particular caches. ## Claims ### Claim 1 A method for providing a plurality of network caches in a communication network, the method comprising: obtaining, by a cache placement controller: one or more parameters from a Traffic Engineering function of the communication network; a delay threshold; and a plurality of client device locations, wherein the Traffic Engineering function is operated at a different network node from the cache placement controller and is configured to perform path selection and data rate control for data links between potential cache locations and client devices at the plurality of client device locations, said one or more parameters from the Traffic Engineering function dependent on said path selection and data rate control; determining, by the cache placement controller, a plurality of nodes of the communication network at which to place the plurality of network caches, the determining comprising evaluating and satisfying a content coverage constraint, the content coverage constraint defined based at least in part on the one or more parameters obtained from the Traffic Engineering function; wherein the coverage content constraint limits a maximum delay across the plurality of client device locations by providing a guarantee that the maximum delay will be less than a given amount, and wherein satisfying the content coverage constraint comprises selecting the plurality of nodes such that, for each one of the plurality of client device locations and for a predetermined number c of the plurality of nodes, a corresponding output value of a coverage cost function is less than or equal to the delay threshold, the corresponding output value of the coverage cost function is determined based on a first input indicative of said one of the plurality of client device locations and a second input indicative of a location of one of the plurality of nodes and the coverage cost function is indicative of data propagation delay between locations received as input; and transmitting, by the cache placement controller to one or more other devices in the communication network, one or more instructions specifying the determined plurality of nodes for placement of the plurality of network caches. ### Claim 2 (depends on 1) The method of claim 1, wherein the predetermined number c is equal to one. ### Claim 3 (depends on 1) The method of claim 1, wherein the delay threshold depends at least in part on a type of data content to be held in the plurality of network caches. ### Claim 4 (depends on 1) The method of claim 1, further comprising generating multiple candidate sets of nodes, each candidate set of nodes having more than one node and being a candidate for the determined plurality of nodes, each candidate set of nodes satisfying the content coverage constraint, wherein generating the multiple candidate sets of nodes comprises generating a first one of the candidate sets of nodes, and modifying the first one of the candidate sets of nodes by addition or removal of one or more individual nodes belonging to the first one of the candidate sets of nodes to generate a second one of the candidate sets of nodes, and wherein determining the plurality of nodes comprises selecting one the candidate sets of nodes. ### Claim 5 (depends on 4) The method of claim 4, wherein at least one of the plurality of candidate sets of nodes other than an initial candidate set of nodes is generated by removal of at least one node from a previously generated one of the candidate sets of nodes, wherein said at least one node is selected from a plurality of non-critical nodes, wherein the plurality of non-critical nodes correspond to nodes which are removable while retaining satisfaction of the content coverage constraint. ### Claim 6 (depends on 5) The method of claim 5, wherein said at least one node is selected further based on a service rating indicative of an expected count of client devices, in the plurality of client device locations, which would be served by a cache located at said at least one node. ### Claim 7 (depends on 1) The method of claim 1, wherein determining the plurality of nodes further comprises selecting one of a plurality of candidate sets of nodes based at least in part on a predetermined utility criterion, each of the plurality of candidate sets of nodes satisfying the content coverage constraint and including more than one of the nodes of the communication network. ### Claim 8 (depends on 7) The method of claim 7, wherein the utility criterion is defined based at least partially on one or more of: network characteristics; network topology; network throughput; network load; and cache deployment costs. ### Claim 9 (depends on 7) The method of claim 7, wherein the utility criterion is defined based at least partially on a service rating applied to specified nodes of the plurality of nodes, the service rating indicative of an expected count of client devices, in the plurality of client device locations, which would be served by a cache located at each one of the specified nodes. ### Claim 10 (depends on 1) The method of claim 1, further comprising generating a plurality of cache-client associations, each of the cache-client associations directing a respective client device in one of the plurality of client device locations to use a particular non-zero subset of the plurality of network caches. ### Claim 11 (depends on 1) The method of claim 1, wherein one or both of the delay threshold and the cost coverage function are: generated by the cache placement controller; obtained from the Traffic Engineering function of the communication network, or obtained from a computer memory location accessible by the cache placement controller. ### Claim 12 (depends on 1) The method of claim 1, wherein the predetermined number c is greater than one. ### Claim 13 (depends on 1) The method of claim 1, wherein the coverage cost function is determined based at least in part on the one or more parameters obtained from the Traffic Engineering function. ### Claim 14 A cache placement controller configured to direct provision of a plurality of network caches in a communication network, the cache placement controller comprising a network interface, a microprocessor, and a memory component and configured to: obtain, using the network interface: one or more parameters from a Traffic Engineering function of the communication network; a delay threshold; and a plurality of client device locations, wherein the Traffic Engineering function is operated at a different network node from the cache placement controller and is configured to perform path selection and data rate control for data links between potential cache locations and client devices at the plurality of client device locations, said one or more parameters from the Traffic Engineering function dependent on said path selection and data rate control; determine a plurality of nodes of the communication network at which to place the plurality of network caches, the determining comprising evaluating and satisfying a content coverage constraint, the content coverage constraint defined based at least in part on the one or more parameters obtained from the Traffic Engineering function; wherein the coverage content constraint limits a maximum delay across the plurality of client device locations by providing a guarantee that the maximum delay will be less than a given amount, and wherein satisfying the coverage content constraint comprises selecting the plurality of nodes such that, for each one of the plurality of client device locations and for a predetermined number c of the plurality of nodes, a corresponding output value of a coverage cost function is less than or equal to the delay threshold, the corresponding output value of the coverage cost function is determined based on a first input indicative of said one of the plurality of client device locations and a second input indicative of a location of one of the plurality of nodes and the coverage cost function is indicative of data propagation delay between locations received as input; and provide, using the network interface, instructions for execution by the network to locate the plurality of network caches at the respective plurality of nodes. ### Claim 15 (depends on 14) The cache placement controller of claim 14, wherein the predetermined number c is equal to one. ### Claim 16 (depends on 14) The cache placement controller of claim 14, wherein the delay threshold depends at least in part on a type of data content to be held in the plurality of network caches. ### Claim 17 (depends on 14) The cache placement controller of claim 14, further configured to generate multiple candidate nodes, each candidate set of nodes having more than one node and being a candidate for the determined plurality of nodes, each candidate set of nodes satisfying the content coverage constraint, wherein generating the multiple candidate sets of nodes comprises generating a first one of the candidate sets of nodes, and modifying the first one of the candidate sets of nodes by addition or removal of one or more individual nodes belonging to the first one of the candidate sets of nodes to generate a second one of the candidate sets of nodes, and wherein determining the plurality of nodes comprises selecting one of the candidate sets of nodes. ### Claim 18 (depends on 14) The cache placement controller of claim 14, wherein determining the plurality of nodes further comprises selecting one a plurality of candidate sets of nodes based at least in part on a predetermined utility criterion, each of the plurality of candidate sets of nodes comprising more than one of the nodes of the communication network and each of the plurality of candidate sets of nodes satisfying the content coverage constraint. ### Claim 19 (depends on 14) The cache placement controller of claim 14, further configured to generate a plurality of cache-client associations, each of the cache-client associations directing a respective client device in one of the plurality of client device locations to use a particular non-zero subset of the plurality of network caches. ### Claim 20 (depends on 14) The cache placement controller of claim 14, wherein one or both of the cost threshold and the cost coverage function are: generated by the cache placement controller; obtained from the Traffic Engineering function of the communication network, or obtained from a computer memory location accessible by the cache placement controller. ### Claim 21 (depends on 14) The cache placement controller of claim 14, wherein the predetermined number c is greater than one. ### Claim 22 (depends on 14) The cache placement controller of claim 14, wherein the coverage cost function is determined based at least in part on the one or more parameters obtained from the Traffic Engineering function.