Method and apparatus for locating caches in a network to optimize performance

Claim 1

A method of determining locations for k caches in a network wherein a network configuration is defined by a plurality of network connections, a plurality of nodes, and a plurality of servers and clients and wherein network performance is determined by the interrelation therebetween and thereamong, wherein the locations determined for k caches optimizes performance of a network cost parameter which is dependent upon the network configuration, said method comprising the steps of: (a) selecting a placement parameter l that is greater than 0; (b) assigning l caches to l arbitrary nodes in the network; (c) selecting l caches to remove from the network; (d) assigning l+1 caches to every possible location in the network; (e) computing and recording network performance data on the network cost parameter for each location of said step (d) and for each selection of l caches of said step (c); (f) determining a location where the network performance data on the network cost parameter computed and recorded in said step (e) is optimized; (g) assigning l+1 caches to the location determined in said step (f); and (h) repeating said steps (c) through (g) for k−l iterations.

Claim 2

A method of determining locations for k caches in a network wherein a network configuration is defined by a plurality of network connections, a plurality of nodes, and a plurality of servers and clients and wherein network performance is determined by the interrelation therebetween and thereamong, wherein the locations determined for k caches optimizes performance of a network cost parameter which is dependent upon the network configuration, said method comprising the steps of: (a) selecting a placement parameter l that is greater than 0; (b) assigning l caches to l arbitrary nodes in the network; (c) selecting l caches to remove from the network; (d) assigning l+1 caches to every possible location in the network; (e) computing and recording network performance data on the network cost parameter for each location of said step (d) and for each selection of l caches of said step (c); (f) determining a location where the network performance data on the network cost parameter computed and recorded in said step (e) is optimized; (g) assigning l+1 caches to the location determined in said step (f); and (h) repeating said steps (c) through (g) for k−l iterations.

Claim 6

A method of determining a location for each of a plurality of caches in a single server network, said method comprising the steps of computing an optimal cost C(i, {tilde over (k)}, s) using a dynamic programming algorithm, where i is a node, {tilde over (k)} is the number of optimally placed caches, and s is the distance between node i and a next cache in the network, and determining an optimal location for installation of each of the plurality of caches for network traffic for the single server based on the computed optimal cost, wherein the network has a predetermined number of nodes and a predetermined number of caches located within the network, said step of computing an optimal cost C(i, {tilde over (k)}, s) using a dynamic programming algorithm comprising the steps of: (a) selecting a network cost parameter; (b) where no cache is located at node i, determining an optimal location for caches in the network by solving the following equation for each node i having children i L , and i R , for each cache, {tilde over (k)} and for each distance s: min 0 ≤ k ′ ≤ k   ( C   ( i L , k ′ , s + 1 ) + C   ( i R , k ~ - k ′ , s + 1 ) + ( s + 1 )   ( F   ( i L , k ′ , s + 1 ) + ( F   ( i R , k ~ - k ′ , s + 1 ) ) + s   f s , i ) ; and (c ) where a cache is located at node i, determining an optimal location for caches in the network by solving the following equation for each node i having children i L , and i R , for each cache k and for each distance s: min 0 ≤ k ′ ≤ ( k - 1 )    ( C   ( i L , k ′ , s ) + C   ( i R , k ~ - s - k ′ , s ) + F   ( i L , k ′ , s + 1 ) + ( F   ( i R , k ~ - k ′ , s + 1 ) ) where C(i, {tilde over (k)}, s) is an optimal cost of a subtree rooted at node i with {tilde over (k)} optimally placed caches, where the next cache in the network is located at a distance s from node i, F(i, {tilde over (k)}, s) is a flow associated with optimal cost C(i, {tilde over (k)}, s) which is the sum of demands in the subtree rooted at node i that do not pass through a cache in the optimal solution of C(i, {tilde over (k)}, s), C is the cost parameter, i L is a child of node i located to the left of node i, i R is a child of node i located to the right of node i, k is a cache budget and 0≦k′≦{tilde over (k)}≦k, s is a distance from node i to the next cache in the network moving away from the server and 0≦s ≦h, where h is the height of the tree, and f s,i is a flow requested by node i from the server.

Claim 7

A method of determining a location for each of a plurality of caches in a single server network, said method comprising the steps of computing an optimal cost C(i, {tilde over (k)}, s) using a dynamic programming algorithm, where i is a node, {tilde over (k)} is the number of optimally placed caches, and s is the distance between node i and a next cache in the network, and determining an optimal location for installation of each of the plurality of caches for network traffic for the single server based on the computed optimal cost, wherein the network has a predetermined number of nodes and a predetermined number of caches located within the network, said step of computing an optimal cost C(i, {tilde over (k)}, s) using a dynamic programming algorithm comprising the steps of: (a) selecting a network cost parameter; (b) where no cache is located at node i, determining an optimal location for caches in the network by solving the following equation for each node i having children i L , and i R , for each cache, {tilde over (k)} and for each distance s: min 0 ≤ k ′ ≤ k   ( C   ( i L , k ′ , s + 1 ) + C   ( i R , k ~ - k ′ , s + 1 ) + ( s + 1 )   ( F   ( i L , k ′ , s + 1 ) + ( F   ( i R , k ~ - k ′ , s + 1 ) ) + s   f s , i ) ; and (c ) where a cache is located at node i, determining an optimal location for caches in the network by solving the following equation for each node i having children i L , and i R , for each cache k and for each distance s: min 0 ≤ k ′ ≤ ( k - 1 )    ( C   ( i L , k ′ , s ) + C   ( i R , k ~ - s - k ′ , s ) + F   ( i L , k ′ , s + 1 ) + ( F   ( i R , k ~ - k ′ , s + 1 ) ) where C(i, {tilde over (k)}, s) is an optimal cost of a subtree rooted at node i with {tilde over (k)} optimally placed caches, where the next cache in the network is located at a distance s from node i, F(i, {tilde over (k)}, s) is a flow associated with optimal cost C(i, {tilde over (k)}, s) which is the sum of demands in the subtree rooted at node i that do not pass through a cache in the optimal solution of C(i, {tilde over (k)}, s), C is the cost parameter, i L is a child of node i located to the left of node i, i R is a child of node i located to the right of node i, k is a cache budget and 0≦k′≦{tilde over (k)}≦k, s is a distance from node i to the next cache in the network moving away from the server and 0≦s ≦h, where h is the height of the tree, and f s,i is a flow requested by node i from the server.