# Weighted Cache Location Problem with Identical Servers

Authors: Hongfa Wang; Wei Ding
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

This paper extends the well-knownp-CLP with one server to p-CLP with m
≥
2 identical servers, denoted by (
p
,
m
)-CLP. We propose the closest server orienting protocol (CSOP), under which every client connects to the closest server to itself via a shortest route on given network. We abbreviate (
p
,
m
)-CLP under CSOP to (
p
,
m
)-CSOP CLP and investigate that (
p
,
m
)-CSOP CLP on a general network is equivalent to that on a forest and further to multiple CLPs on trees. The case of m
=
2 is the focus of this paper. We first devise an improved O
(
p
h
2
+
n
)-time parallel exact algorithm for p-CLP on a tree and then present a parallel exact algorithm with at most O
(
(
4
/
9
)
p
2
n
2
) time in the worst case for (
p
,
2
)-CSOP CLP on a general network. Furthermore, we extend the idea of parallel algorithm to the cases of m
>
2 to obtain a worst-case O
(
(
4
/
9
)
(
n
-
m
)
2
(
(
m
+
p
)
p
/
p
-
1
!
)
)-time exact algorithm. At the end of the paper, we first give an example to illustrate our algorithms and then make a series of numerical experiments to compare the running times of our algorithms.


---

## Body

## 1. Introduction

Caching has become an important tool to improve the network performance efficiency, reducing delays to every client and alleviating the overload on the server [1–4]. Initially, a large amount of studies considered how to optimize cache performance [5–7], cache hierarchies [5], and cooperations among multiple web servers [8, 9]. Subsequently, how to locate caches or proxies optimally in networks to alleviate the server load became more popular [2, 10–13]. The most popular practice in the past is to place caches on the edges of networks, acting as the network browser and proxy or part of cache hierarchies [1, 3–5]. Later, Danzig et al. [2] discovered that the advantage of placing caches on the nodes of networks instead of on the edges of networks is to reduce overall network congestion greatly. In this paper, we only discuss how to place caches on the nodes of networks.The focus of placing caches in networks is how to enhance the effect and efficiency of caching in networks as greatly as possible. This problem can be modeled as thep
-cache location problem (abbreviated to p-CLP or CLP) or p
-proxy problem. Both of their initial models can be reduced to thep
-median problem [14, 15] essentially. Throughout this paper, we let n denote the number of network nodes, let m denote the number of network edges, let p denote the number of caches or proxies, let and h denote the height of tree. Later, Abrams et al. [7] investigated that almost all current cache products contain a transparent operation mode, called atransparent en-route cache (TERC). When using TERCs in networks with one server, all clients connect to server and caches are placed on the routes from clients to server. Heddaya and Mirdad [10] suggested making use of TERCs to balance load due to the manageability of TERC. Further, Krishnan et al. [11] proposed the cache location problem involving TERCs, studied the problem in several special networks, and presented polynomial time exact algorithms. In the rest of this paper, all of CLPs involve TERC.The known algorithms for thep
-proxy problem also apply to p-CLP. For a linear network, Li et al. studied the p-proxy problem and presented an O
(
p
n
2
) time exact algorithm [12]. Later, Woeginger used the Monge property to obtain an improved algorithm with O
(
p
n
) time complexity [16]. For a tree network, Li et al. devised an O
(
p
2
n
3
)-time exact dynamic programming algorithm [13] and Chen et al. presented an improved O
(
n
p
h
)-time algorithm [17]. For a general tree of rings network, Chen et al. showed an O
(
p
n
2
) time exact algorithm [18]. Moreover, a variety of objectives have been considered, such as the overall time, cost, and hop count. Du [19] and Jia et al. [20] studied the proxy problem with read-write operations. In [21], Liu and Yang considered the delay-constrained proxy problem. Given a general network, provided that all clients areintelligent and connect to the server via ashortest route on the network, we claim that p-CLP in this situation is equivalent to p-CLP on the tree and thus is solvable in polynomial time [11, 13, 17] since all the shortest routes between clients and server form a shortest-paths tree rooted at the server node.All past works on CLP considered a single server. This paper is the first one to study CLP with multipleidentical servers. In this model, every client connects to some server via a route and all caches lie on such routes. We further suppose that every client isintelligent; that is, it connects to the closest server to itself via a shortest route. This produces theclosest server orienting protocol (abbreviated to CSOP). Under CSOP, all the shortest routes connecting clients and server form aforest, each component of which is rooted at a server node. Therefore, theCLP with multiple identical servers under CSOP on a general network is equivalent to that on a forest.We abbreviatep-CLP with m identical servers to (
p
,
m
)-CLP and further (
p
,
m
)-CLP under CSOP to (
p
,
m
)-CSOP CLP. In this paper, we first propose an improved parallel exact algorithm for p-CLP on a tree, which reduces O
(
n
p
h
) time of algorithm in [17] to O
(
p
h
2
+
n
). Based on the improved algorithm, we design a parallel exact algorithm for (
p
,
2
)-CSOP CLP on a general network, which takes O
(
p
2
max
⁡
{
h
1
2
,
h
2
2
}
+
(
8
/
3
)
n
p
) time and at most O
(
(
4
/
9
)
p
2
n
2
) time in the worst case. Furthermore, we extend the algorithm idea to (
p
,
m
)-CSOP CLP on a general network and get a parallel exact algorithm, which takes O
(
(
p
·
max
⁡
1
≤
i
≤
m
h
i
2
+
(
8
/
3
)
n
)
(
m
+
p
-
1
p
)
) time and at most O
(
(
4
/
9
)
(
n
-
m
)
2
(
(
m
+
p
)
p
/
(
p
-
1
)
!
)
) time in the worst case.The rest of this paper is organized as follows. In Section2, we define notations used frequently and (
p
,
2
)-CSOP CLP formally. In Section 3, we make some fundamental preliminaries, develop an improved algorithm for p-CLP on a tree, and then devise a parallel exact algorithm for (
p
,
2
)-CSOP CLP based on the improved algorithm. In Section 4, we define (
p
,
m
)-CSOP CLP formally and devise an efficient parallel exact algorithm. In Section 5, we first give an example to illustrate our algorithm and then make a series of numerical experiments to compare the running time of our algorithm. In Section 6, we conclude this paper with some future research topics.


## 2. Problem Description

LetG
=
(
V
,
E
,
w
,
c
) represent a communication network or computer network, where V is thenode set and E is theedge set. Every node represents a processing or switching element and every edge represents a communication link [22]. Every node z
∈
V has a weight w
(
z
)
>
0 representing thedemand amount of z, and every edge e
∈
E has a weight c
(
e
)
>
0 representing thecost per demand. For any pair of nodes x and y, we let [
x
,
y
] denote the edge of G between x and y and let π
(
x
,
y
) denote theshortest path in G connecting x and y. Let c
[
x
,
y
] denote the cost of edge [
x
,
y
], and c
(
x
,
y
) denote the cost of π
(
x
,
y
) which is equal to the sum of all the costs on edges of π
(
x
,
y
). So,
(1)
c
(
x
,
y
)
=
∑
e
∈
π
(
x
,
y
)
c
(
e
)
.Lets
1 and s
2 be twoidentical servers, which are allocated to a pair of nodes of G in advance. Let Γ denote the set of p cache locations. Suppose that CSOP works and each cache is aduplicate of server. Given any set Γ
⊂
V
∖
{
s
1
,
s
2
}, the cost of node z paying for its per demand depends on the locations of Γ
∪
{
s
1
,
s
2
} and is denoted by c
(
z
,
Γ
∪
{
s
1
,
s
2
}
). Thus, the cost of z paying for its overall demand is equal to w
(
z
)
c
(
z
,
Γ
∪
{
s
1
,
s
2
}
). Let f
(
Γ
) denote the total cost of all the nodes paying for their overall demand, that is,
(2)
f
(
Γ
)
=
∑
z
∈
V
‍
w
(
z
)
c
(
z
,
Γ
∪
{
s
1
,
s
2
}
)
.Thep
-cache location problem with two identical servers under CSOP (i.e., (
p
,
2
)-CSOP CLP) aims to find p cache locations in G to minimize the total cost of all the nodes paying for their overall demand. In other words, the aim of (
p
,
2
)-CSOP CLP can be reduced to find an optimal set Γ
* from V
∖
{
s
1
,
s
2
} to minimize the value of f
(
Γ
), that is,
(3)
f
(
Γ
*
)
=
min
⁡
Γ
⊂
V
∖
{
s
1
,
s
2
}
f
(
Γ
)
.


## 3. A Parallel Exact Algorithm for(
p
,
2
)-CSOP CLP

In the scenario of(
p
,
2
)-CSOP CLP, every client knows the location of the closest server to itself and connects to it via a shortest route. If its service request encounters the closest cache on the route, it will get information therein. Otherwise, it get information from the server. Therefore, (
p
,
2
)-CSOP CLP can be viewed as the combination of two CLPs when s
1 and s
2 are predesignated to two locations of network. One is CLP with s
1 as the server and the other is CLP with s
2 as the server.


### 3.1. Preliminaries

Onces
1 and s
2 are fixed at two predesignated locations of G, it is certain that some nodes of G are closer to s
1 and the other nodes are closer to s
2. Let V
(
s
1
) be the set of nodes that are closer to s
1 and V
(
s
2
) be the set of nodes that are closer to s
2. Thus, Lemma 1 follows immediately. Let T
(
s
1
) (resp. T
(
s
2
)) denote thesingle-source shortest paths tree in G with s
1 (resp. s
2) as the origin spanning V
(
s
1
) (resp. V
(
s
2
)). We can use Dijkstra’s algorithm [23] to compute T
(
s
1
) and T
(
s
2
). We can transform T
(
s
1
) (resp. T
(
s
2
)) into a rooted tree with s
1 (resp. s
2) as the root without loss of generality. Furthermore, let T
x
(
s
1
) denote the subtree of T
(
s
1
) rooted at x for any x
∈
V
(
s
1
) and let T
y
(
s
2
) denote the subtree of T
(
s
2
) rooted at y for any y
∈
V
(
s
2
).Lemma 1.
V
=
V
(
s
1
)
⋃
V
(
s
2
).Specifically, we letΠ
[
s
1
,
s
2
] denote the unique path on tree between s
1 and s
2 when G is a tree graph. Let N
(
s
1
) (resp. N
(
s
2
)) be the set of nodes on Π
[
s
1
,
s
2
] which are closer to s
1 (resp. s
2) and let V
x
(
s
1
,
s
2
) be the subset of nodes which reach s
1 and s
2 via x for any node x on Π
[
s
1
,
s
2
]. We investigate that every node in V
x
(
s
1
,
s
2
),  x
∈
N
(
s
1
) belongs to V
(
s
1
) and every node in V
y
(
s
1
,
s
2
),  y
∈
N
(
s
2
) belongs to V
(
s
2
), and vice versa. So, Lemma 2 follows. By Lemmas 1 and 2, we can compute T
(
s
1
) and T
(
s
2
) by applying the depth-first search (DFS) procedure to the tree, which only takes a linear time.Lemma 2.
V
(
s
1
)
=
⋃
x
∈
N
(
s
1
)
‍
V
x
(
s
1
,
s
2
), V
(
s
2
)
=
⋃
y
∈
N
(
s
2
)
‍
V
y
(
s
1
,
s
2
).By Lemma1, we are sure that one cache is placed either in V
(
s
1
) or V
(
s
2
). The set of cache locations in V
(
s
1
) and V
(
s
2
) is denoted by Γ
(
s
1
) and Γ
(
s
2
), respectively; thus, Γ
=
Γ
(
s
1
)
∪
Γ
(
s
2
), Γ
(
s
1
)
=
Γ
∩
V
(
s
1
) and   Γ
(
s
2
)
=
Γ
∩
V
(
s
2
). Under CSOP, every z
∈
V
(
s
1
) connects to s
1 and thus the cost of paying for its overall demand is equal to w
(
z
)
·
c
(
z
,
Γ
(
s
1
)
∪
{
s
1
}
). Similarly, the cost of z
∈
V
(
s
2
) is equal to w
(
z
)
·
c
(
z
,
Γ
(
s
2
)
∪
{
s
2
}
). We can further rewrite (2) as
(4)
f
(
Γ
)
=
f
(
Γ
(
s
1
)
∪
Γ
(
s
2
)
)
=
∑
z
∈
V
(
s
1
)
w
(
z
)
·
c
(
z
,
Γ
(
s
1
)
∪
{
s
1
}
)
+
∑
z
∈
V
(
s
2
)
w
(
z
)
·
c
(
z
,
Γ
(
s
2
)
∪
{
s
2
}
)
.Letp
1 be the number of caches in Γ
(
s
1
) and let p
2 be the number of caches in Γ
(
s
2
). Obviously, p
1
+
p
2
=
p. A combination of Γ
(
s
1
) having p
1 caches and Γ
(
s
2
) having p
2 caches is called acache allocation scheme (abbreviated to CAS), denoted as (
p
1
,
p
2
)-CAS where p
1 and p
2 cannot be exchanged. Clearly, (
p
,
2
)-CSOP CLP contains p
+
1 CASs in total. For any (
p
1
,
p
2
)-CAS, (
p
,
2
)-CSOP CLP is composed of two subproblems, that is, p
1-CLP in T
(
s
1
) and p
2-CLP in T
(
s
2
). Let C
(
G
,
p
) denote the minimum cost of (
p
,
2
)-CSOP CLP in G, and let C
(
T
(
s
1
)
,
p
1
) denote the minimum cost of p
1-CLP in T
(
s
1
) and let C
(
T
(
s
2
)
,
p
2
) denote the minimum cost of p
2-CLP in T
(
s
2
). The cost of (
p
,
2
)-CSOP CLP in G for any given (
p
1
,
p
2
)-CAS is equal to the sum of C
(
T
(
s
1
)
,
p
1
) and C
(
T
(
s
2
)
,
p
2
), and further C
(
G
,
p
) results from the optimal (
p
1
,
p
2
)-CASs; that is,
(5)
C
(
G
,
p
)
=
min
⁡
p
1
+
p
2
=
p
{
C
(
T
(
s
1
)
,
p
1
)
+
C
(
T
(
s
2
)
,
p
2
)
}
.


### 3.2. Preprocessing

In this subsection, we give a new method of transforming an arbitrary rooted tree into a binary tree. LetT be a rooted tree. For any nonleaf node x of  T, the subgraph of T is composed of the edges between x and all its children are called astar of T with center x, denoted by s
t
a
r
(
x
). Let d
(
x
) denote the number of children of x. We process x in the following way:(i)
ifd
(
x
)
=
1, then we add a new child y
′ to x and set both c
[
x
,
y
′
] and w
(
y
′
) to zero;
(ii)
ifd
(
x
)
=
2, then we need no work;
(iii)
ifd
(
x
)
=
k,  k
≥
3 (let all children of x be x
1
,
x
2
,
…
,
x
k), then we delete the edges (
x
,
x
1
)
,
(
x
,
x
2
)
,
…
,
(
x
,
x
k
), add two new nodes y
′ and y
′′ to x, and set w
(
y
′
)
,
c
(
x
,
y
′
) and w
(
y
′′
)
,
c
(
x
,
y
′′
) to zero. For each t
=
1,2
,
…
,
⌈
k
/
2
⌉, we add new edge (
y
′
,
x
t
) and set c
(
y
′
,
x
t
) to c
(
x
,
x
t
). For each t
=
⌈
k
/
2
⌉
+
1
,
…
,
k, we add new edge (
y
′′
,
x
t
) and set c
(
y
′′
,
x
t
) to c
(
x
,
x
t
).We use the above way recursively to process every node ofT
=
(
V
,
E
,
w
,
c
) top-down to obtain a binary tree b
(
T
)
=
(
V
b
,
E
b
,
w
b
,
c
b
). This idea can be described as algorithmBINY. Our way improves that one proposed by Chen et al. [18]. Moreover, we will analyze the performance ofBINY in the following while they provided no analysis of their algorithm [18].Theorem 3.
For eachx of  T with d
(
x
)
=
k
≥
3, the subtree of b
(
T
) derived from transforming s
t
a
r
(
x
) byBINY has a height of O
(
log
⁡
k
) and has 5
k
/
3
-
2 dummy nodes added in the worst case.Proof.
The essence ofBINY processing s
t
a
r
(
x
) is to bisect all the children of x recursively. At the final step, two dummy nodes are added if four nodes are bisected into two groups of two nodes and three dummy nodes are added if three nodes are bisected into one group of two nodes and one group of one node. So,BINY adds the most dummy nodes in the worst case of k
=
3
·
2
t. In this case, the subtree of b
(
T
) derived from transforming s
t
a
r
(
x
) byBINY has a height of t
+
2 and the number of dummy nodes added is 2
(
1
-
2
t
)
/
(
1
-
2
)
+
3
·
2
t
=
5
·
2
t
-
2. In fact, we investigate that the subtree of b
(
T
) derived from a star with k nodes satisfying that 2
t
+
1
+
1
<
k
≤
2
t
+
2 has a height of t
+
2. So, log
⁡
k
≤
t
+
2
<
log
⁡
k
+
1. Therefore, the subtree of b
(
T
) derived from s
t
a
r
(
x
) has a height of O
(
log
⁡
k
). The number of all the dummy nodes added byBINY in the worst case is 5
·
2
t
-
2
=
5
·
2
log
⁡
⁡
(
k
/
3
)
-
2
=
5
k
/
3
-
2.Theorem 4.
BINY can transform T with n nodes into b
(
T
) with a height of at most 2
(
n
-
1
)
/
3, which takes O
(
n
) time and adds at most (
5
/
3
)
n
-
11
/
3 dummy nodes.Proof.
Suppose thatT has K stars and every s
t
a
r
(
x
i
),  1
≤
i
≤
K, has k
i children. Obviously, ∑
i
=
1
K
‍
k
i
=
|
E
|
=
n
-
1. By Theorem 3,BINY adds 5
k
i
/
3
-
2 dummy nodes for every s
t
a
r
(
x
i
) in the worst case of k
i
=
3
·
2
t
i,  t
i
≥
0,  ∀
1
≤
i
≤
K. So, the number of dummy nodes added byBINY is ∑
i
=
1
K
‍
(
5
k
i
/
3
-
2
)
=
(
5
/
3
)
∑
i
=
1
K
‍
k
i
-
2
K
≤
(
5
/
3
)
(
n
-
1
)
-
2
=
(
5
/
3
)
n
-
11
/
3.
Next, we discuss the height ofb
(
T
). We construct a worst-case tree T
Δ consisting of K three-children stars lined one by one. In other words, for every star of T other than the bottom one, two children of the star are leaves of T and the other one is the center of the next star. Clearly, T
Δ satisfies that 3
K
=
n
-
1. Since the subtree of b
(
T
) derived from transforming a three-children star has height of 2, the height of T
Δ is 2
K
=
2
·
(
(
n
-
1
)
/
3
)
=
2
(
n
-
1
)
/
3.
Therefore, we obtain|
V
b
|
=
n
+
(
(
5
/
3
)
n
-
11
/
3
)
=
(
8
/
3
)
n
-
(
11
/
3
) in the worst case and conclude thatBINY spends O
(
n
) time to transform T into b
(
T
).Theorem 5.
CLP in a general treeT is equivalent to CLP in b
(
T
).Proof.
This theorem is equivalent to the proposition that no cache is located at one dummy node in any optimal solution to CLP inb
(
T
). Suppose that a cache is located at a dummy node α in an optimal solution L and α is added by transforming s
t
a
r
(
x
) byBINY. The cost of a new solution L
′ obtained by replacing α with x into L is less than the cost of L. This causes a contradiction.The binary tree obtained by applying Tamir’s algorithm [15] to a general tree T with n nodes has a height of at most n
-
2, while one obtained by applyingBINY to T has a height of at most 2
(
n
-
1
)
/
3. In terms of height of binary tree,BINY is superior to Tamir’s algorithm. This will help to reduce the running time of algorithmSUB  (Algorithm 1) shown in Section 3.3.Algorithm 1:
SUB.
Input: a binary tree B rooted at s;
Output: an optimal solution of p-CLP on B and F
[
s
]
[
s
]
[
p
];
Step  0. Use DFS based algorithm in [24] to traverse B, and record
the parent node of every nodex of B;
Step  1. for  k from 1 up to h  do
Use|
V
(
B
(
k
)
)
| processors to work simultaneously and all
processors do the same work as follows for allx
∈
V
(
B
(
k
)
):
if  x is a leaf node then
UseDFS based algorithm in [24] to compute c
(
x
,
y
) and initialize
F
[
x
]
[
y
]
[
1
]
←
0
,
F
[
x
]
[
y
]
[
0
]
←
w
(
x
)
·
c
(
x
,
y
) for any y
∈
π
(
s
,
x
);
Step  2. for  k from 1 up to h  do
Use|
V
(
B
(
k
)
)
| processors to work simultaneously and all
processors do the same work as follows for allx
∈
V
(
B
(
k
)
):
if  x is a nonleaf node then
for each q from 0 up to p  do
if  0
≤
q
≤
min
⁡
{
p
,
|
V
(
B
x
)
|
}  then
UseDFS based algorithm in [24] to compute c
(
x
,
y
) and
then computeF
[
x
]
[
y
]
[
q
] by (6) for any y
∈
π
(
s
,
x
);


### 3.3. Algorithm for CLP on Trees

By Theorem5, we only need to discuss CLP on binary trees. Let B be a binary tree and s the server (root) node, and let V
(
·
) denote the node set of B or its subtree. For any node x of B, we let B
x denote the subtree of B rooted at x. Let x
l and x
r be the left child and right child of x, respectively, and then let B
x
l (resp. B
x
r) denote the subtree of B
x rooted at x
l (resp. x
r). We use h to denote the height of B and 1,2
,
…
,
h to label the levels of B bottom-up, and we use B
(
k
) to denote the kth level of B. Let F
[
x
]
[
y
]
[
q
] denote the minimum cost of the subproblem of p-CLP on B
x when the closest cache to x on π
(
x
,
s
) is located at y and q caches are placed in B
x. Similar to the idea of solving the p-proxy problem in [18], we propose our way of computing F
[
x
]
[
y
]
[
q
] and giving a new proof, shown in Theorem 6.Theorem 6.
For each nodex of B other than leaves, each node y on π
(
x
,
s
), and each 0
≤
q
≤
min
⁡
{
p
,
|
V
(
B
x
)
|
}, one has
(6)
F
[
x
]
[
y
]
[
q
]
=
min
⁡
{
min
⁡
0
≤
q
l
≤
q
-
1
,
q
r
=
q
-
q
l
-
1
{
F
[
x
l
]
[
x
]
[
q
l
]
+
F
[
x
r
]
[
x
]
[
q
r
]
}
,
min
⁡
0
≤
q
l
≤
q
,
q
r
=
q
-
q
l
{
F
[
x
l
]
[
y
]
[
q
l
]
+
F
[
x
r
]
[
y
]
[
q
r
]
+
w
(
x
)
·
c
(
x
,
y
)
}
.Proof.
For any nodex of B, we need to consider whether a cache is located at x or not when discussing the subproblem of p-CLP on B
x.(1)
If a cache is located atx, then x needs no paying for its overall demand. So, the cost of the subproblem of p-CLP on B
x is equal to the sum of that on B
x
l and that on B
x
r. When the closest cache to x on π
(
s
,
x
) is located at y, we observe that x is the closest cache on π
(
s
,
x
) to x
l and x
r. The possible number q of caches placed in B
x is at most p while at most |
V
(
B
x
)
|. The number q
l of caches in B
x
l plus the number q
r of caches in B
x
r is equal to q
-
1. The key work is to find the optimal (
q
l
,
q
r
)-CAS with q
l
+
q
r
=
q
-
1, from which the cost of the subproblem of p-CLP on B
x results is equal to
(7)
min
⁡
0
≤
q
l
≤
q
-
1
,
q
r
=
q
-
q
l
-
1
{
F
[
x
l
]
[
x
]
[
q
l
]
+
F
[
x
r
]
[
x
]
[
q
r
]
}
.
(2)
If no cache is located atx, then the cost of x paying for its overall demand is w
(
x
)
·
c
(
x
,
y
). So, the cost of the subproblem of p-CLP on B
x is equal to the sum of that on B
x
l and that on B
x
r and the cost of x. When the closest cache to x on π
(
s
,
x
) is located at y, we see that y is also the closest cache on π
(
s
,
x
) to x
l and x
r. As discussed above, q
≤
min
⁡
{
p
,
|
V
(
B
x
)
|
}. The number q
l of caches in B
x
l plus the number q
r of caches in B
x
r is equal to q. The key work is to find the optimal (
q
l
,
q
r
)-CAS with q
l
+
q
r
=
q, from which the cost of the subproblem of p-CLP on B
x results is equal to
(8)
min
⁡
0
≤
q
l
≤
q
,
q
r
=
q
-
q
l
{
F
[
x
l
]
[
y
]
[
q
l
]
+
F
[
x
r
]
[
y
]
[
q
r
]
+
w
(
x
)
·
c
(
x
,
y
)
F
[
x
l
]
[
y
]
[
q
l
]
}
.Obviously, the case ofq
<
0 is forbidden. Let F
[
x
]
[
y
]
[
q
]
=
∞,  ∀
q
<
0 for each node x of B and each node y on π
(
s
,
x
). From the definition of F
[
x
]
[
y
]
[
q
], we know that F
[
s
]
[
s
]
[
p
] is just the minimum cost of p-CLP. Initially, we set F
[
x
]
[
y
]
[
0
]
=
w
(
x
)
·
c
(
x
,
y
) and F
[
x
]
[
y
]
[
1
]
=
0 for each leaf node x of B and each node y on π
(
s
,
x
).We can first use thedepth-first search (DFS) based algorithm in [24] to traverse B, by which we can record the parent node of every node x (thus record π
(
s
,
x
) step by step) and compute the cost of path connecting any node and its ancestor. Based on Theorem 6 and above discussions, we devise a bottom-up dynamic programming algorithm, which can be described as a parallel algorithmSUB by using the techniques in [25].Theorem 7.
Given any binary treeB with n nodes and a height of h,SUB runs in O
(
p
h
2
+
n
) time for computing p-CLP on B.Proof.
Step 0 usesDFS based algorithm in [24] to traverse B, which runs O
(
n
) time. In Step 1, for each level k
=
1,2
,
…
,
h, the processor at every leaf node x
∈
V
(
B
(
k
)
) uses the algorithm in [24] to make initialization for each y
∈
π
(
s
,
x
), which takes O
(
h
) time. So, Step 1 runs at most O
(
h
2
) time. In Step 2, for each level k
=
1,2
,
…
,
h, the processor at every nonleaf node x
∈
V
(
B
(
k
)
) uses the algorithm in [24] to compute c
(
x
,
y
) and then compute F
[
x
]
[
y
]
[
q
] by (6) for every 0
≤
q
≤
min
⁡
{
p
,
|
V
(
B
x
)
|
} and every y
∈
π
(
s
,
x
), which takes at most O
(
p
2
h
) time. So, Step 2 runs at most O
(
p
2
h
2
) time. We can use the method in [15] to infer that the practical running time of Step 2 is O
(
p
h
2
). Therefore,SUB runs in O
(
p
h
2
+
n
) time.


### 3.4. Algorithm for(
p
,
2
)-CSOP CLP on General Graphs

Based on (5) and discussions therein, we can solve (
p
,
2
)-CSOP CLP on a general graph G by first computing C
(
T
(
s
1
)
,
p
1
) in T
(
s
1
) and C
(
T
(
s
2
)
,
p
2
) in T
(
s
2
) for any (
p
1
,
p
2
)-CAS with p
1
+
p
2
=
p and then determining an optimal (
p
1
,
p
2
)-CAS such that the sum of C
(
T
(
s
1
)
,
p
1
) and C
(
T
(
s
2
)
,
p
2
) is minimized. We discover that the output F
[
s
i
]
[
s
i
]
[
p
i
],  i
=
1,2, ofSUB is just the value of C
(
T
(
s
i
)
,
p
i
) when we applySUB to T
(
s
i
). This forms our algorithm for (
p
,
2
)-CSOP CLP on a general graph, described as algorithmGLOB (Algorithm 2).Algorithm 2:
GLOB.
Input: T
(
s
1
) and T
(
s
2
) derived from G
=
(
V
,
E
,
w
,
c
) with s
1 and s
2;
Output: Γ
*;
Step  0. Use BINY to transform T
(
s
1
) into b
(
T
(
s
1
)
) and T
(
s
2
) into b
(
T
(
s
2
)
);
Step  1. Δ
←
∞;
for  p
1 from 0 up to p  do (then p
2
=
p
-
p
1)
ApplySUB to b
(
T
(
s
i
)
)
,
i
=
1,2 to obtain F
[
s
i
]
[
s
i
]
[
p
i
];
C
(
b
(
T
(
s
i
)
)
,
p
i
)
←
F
[
s
i
]
[
s
i
]
[
p
i
];
if  C
(
b
(
T
(
s
1
)
)
,
p
1
)
+
C
(
b
(
T
(
s
2
)
)
,
p
2
)
<
Δ  then
Δ
←
C
(
b
(
T
(
s
1
)
)
,
p
1
)
+
C
(
b
(
T
(
s
2
)
)
,
p
2
);
Γ
*
(
s
1
)
←
Γ
(
s
1
), Γ
*
(
s
2
)
←
Γ
(
s
2
);
Step  2. Γ
*
←
Γ
*
(
s
1
)
∪
Γ
*
(
s
2
);Suppose thatT
(
s
1
) has n
1 nodes and T
(
s
2
) has n
2 nodes. Clearly, n
1
+
n
2
=
n.GLOB usesBINY to transform T
(
s
1
) into b
(
T
(
s
1
)
) and T
(
s
2
) into b
(
T
(
s
2
)
). From Theorem 4, we know that b
(
T
(
s
i
)
),  i
=
1,2, has at most (
8
/
3
)
n
i
-
11
/
3 nodes including at most (
5
/
3
)
n
i
-
11
/
3 dummy nodes and has a height of at most 2
(
n
i
-
1
)
/
3. Let h
i denote the height of b
(
T
(
s
i
)
). For any (
p
1
,
p
2
)-CAS with p
1
+
p
2
=
p,GLOB appliesSUB to p
1-CLP on b
(
T
(
s
1
)
) and p
2-CLP on b
(
T
(
s
2
)
), respectively. It follows from Theorem 7 that the former takes at most O
(
p
1
h
1
2
+
(
8
/
3
)
n
1
) time and the latter takes at most O
(
p
2
h
2
2
+
(
8
/
3
)
n
2
) time. Therefore, the running time ofGLOB is at most
(9)
∑
p
1
=
0
p
‍
O
(
(
p
1
h
1
2
+
8
3
n
1
)
+
(
p
2
h
2
2
+
8
3
n
2
)
)
=
∑
p
1
=
0
p
‍
O
(
p
1
h
1
2
+
8
3
n
1
+
(
p
-
p
1
)
h
2
2
+
8
3
(
n
-
n
1
)
)
≤
O
(
p
2
·
max
⁡
{
h
1
2
,
h
2
2
}
+
8
3
n
p
)
.
Further, we take h
1
≤
2
(
n
1
-
1
)
/
3 and h
2
≤
2
(
n
2
-
1
)
/
3 into the above inequality to obtain that the running time ofGLOB in the worst case is at most
(10)
O
(
p
2
max
⁡
{
4
(
n
1
-
1
)
2
9
,
4
(
n
2
-
1
)
2
9
}
+
8
3
n
p
)
≤
O
(
4
9
p
2
n
2
)
.Theorem 8.
Given an undirected graphG
=
(
V
,
E
,
w
,
c
) with n nodes and two server nodes,GLOB runs in O
(
p
2
max
⁡
{
h
1
2
,
h
2
2
}
+
(
8
/
3
)
n
p
) time for (
p
,
2
)-CSOP CLP on G and runs in at most O
(
(
4
/
9
)
p
2
n
2
) time in the worst case.


## 3.1. Preliminaries

Onces
1 and s
2 are fixed at two predesignated locations of G, it is certain that some nodes of G are closer to s
1 and the other nodes are closer to s
2. Let V
(
s
1
) be the set of nodes that are closer to s
1 and V
(
s
2
) be the set of nodes that are closer to s
2. Thus, Lemma 1 follows immediately. Let T
(
s
1
) (resp. T
(
s
2
)) denote thesingle-source shortest paths tree in G with s
1 (resp. s
2) as the origin spanning V
(
s
1
) (resp. V
(
s
2
)). We can use Dijkstra’s algorithm [23] to compute T
(
s
1
) and T
(
s
2
). We can transform T
(
s
1
) (resp. T
(
s
2
)) into a rooted tree with s
1 (resp. s
2) as the root without loss of generality. Furthermore, let T
x
(
s
1
) denote the subtree of T
(
s
1
) rooted at x for any x
∈
V
(
s
1
) and let T
y
(
s
2
) denote the subtree of T
(
s
2
) rooted at y for any y
∈
V
(
s
2
).Lemma 1.
V
=
V
(
s
1
)
⋃
V
(
s
2
).Specifically, we letΠ
[
s
1
,
s
2
] denote the unique path on tree between s
1 and s
2 when G is a tree graph. Let N
(
s
1
) (resp. N
(
s
2
)) be the set of nodes on Π
[
s
1
,
s
2
] which are closer to s
1 (resp. s
2) and let V
x
(
s
1
,
s
2
) be the subset of nodes which reach s
1 and s
2 via x for any node x on Π
[
s
1
,
s
2
]. We investigate that every node in V
x
(
s
1
,
s
2
),  x
∈
N
(
s
1
) belongs to V
(
s
1
) and every node in V
y
(
s
1
,
s
2
),  y
∈
N
(
s
2
) belongs to V
(
s
2
), and vice versa. So, Lemma 2 follows. By Lemmas 1 and 2, we can compute T
(
s
1
) and T
(
s
2
) by applying the depth-first search (DFS) procedure to the tree, which only takes a linear time.Lemma 2.
V
(
s
1
)
=
⋃
x
∈
N
(
s
1
)
‍
V
x
(
s
1
,
s
2
), V
(
s
2
)
=
⋃
y
∈
N
(
s
2
)
‍
V
y
(
s
1
,
s
2
).By Lemma1, we are sure that one cache is placed either in V
(
s
1
) or V
(
s
2
). The set of cache locations in V
(
s
1
) and V
(
s
2
) is denoted by Γ
(
s
1
) and Γ
(
s
2
), respectively; thus, Γ
=
Γ
(
s
1
)
∪
Γ
(
s
2
), Γ
(
s
1
)
=
Γ
∩
V
(
s
1
) and   Γ
(
s
2
)
=
Γ
∩
V
(
s
2
). Under CSOP, every z
∈
V
(
s
1
) connects to s
1 and thus the cost of paying for its overall demand is equal to w
(
z
)
·
c
(
z
,
Γ
(
s
1
)
∪
{
s
1
}
). Similarly, the cost of z
∈
V
(
s
2
) is equal to w
(
z
)
·
c
(
z
,
Γ
(
s
2
)
∪
{
s
2
}
). We can further rewrite (2) as
(4)
f
(
Γ
)
=
f
(
Γ
(
s
1
)
∪
Γ
(
s
2
)
)
=
∑
z
∈
V
(
s
1
)
w
(
z
)
·
c
(
z
,
Γ
(
s
1
)
∪
{
s
1
}
)
+
∑
z
∈
V
(
s
2
)
w
(
z
)
·
c
(
z
,
Γ
(
s
2
)
∪
{
s
2
}
)
.Letp
1 be the number of caches in Γ
(
s
1
) and let p
2 be the number of caches in Γ
(
s
2
). Obviously, p
1
+
p
2
=
p. A combination of Γ
(
s
1
) having p
1 caches and Γ
(
s
2
) having p
2 caches is called acache allocation scheme (abbreviated to CAS), denoted as (
p
1
,
p
2
)-CAS where p
1 and p
2 cannot be exchanged. Clearly, (
p
,
2
)-CSOP CLP contains p
+
1 CASs in total. For any (
p
1
,
p
2
)-CAS, (
p
,
2
)-CSOP CLP is composed of two subproblems, that is, p
1-CLP in T
(
s
1
) and p
2-CLP in T
(
s
2
). Let C
(
G
,
p
) denote the minimum cost of (
p
,
2
)-CSOP CLP in G, and let C
(
T
(
s
1
)
,
p
1
) denote the minimum cost of p
1-CLP in T
(
s
1
) and let C
(
T
(
s
2
)
,
p
2
) denote the minimum cost of p
2-CLP in T
(
s
2
). The cost of (
p
,
2
)-CSOP CLP in G for any given (
p
1
,
p
2
)-CAS is equal to the sum of C
(
T
(
s
1
)
,
p
1
) and C
(
T
(
s
2
)
,
p
2
), and further C
(
G
,
p
) results from the optimal (
p
1
,
p
2
)-CASs; that is,
(5)
C
(
G
,
p
)
=
min
⁡
p
1
+
p
2
=
p
{
C
(
T
(
s
1
)
,
p
1
)
+
C
(
T
(
s
2
)
,
p
2
)
}
.


## 3.2. Preprocessing

In this subsection, we give a new method of transforming an arbitrary rooted tree into a binary tree. LetT be a rooted tree. For any nonleaf node x of  T, the subgraph of T is composed of the edges between x and all its children are called astar of T with center x, denoted by s
t
a
r
(
x
). Let d
(
x
) denote the number of children of x. We process x in the following way:(i)
ifd
(
x
)
=
1, then we add a new child y
′ to x and set both c
[
x
,
y
′
] and w
(
y
′
) to zero;
(ii)
ifd
(
x
)
=
2, then we need no work;
(iii)
ifd
(
x
)
=
k,  k
≥
3 (let all children of x be x
1
,
x
2
,
…
,
x
k), then we delete the edges (
x
,
x
1
)
,
(
x
,
x
2
)
,
…
,
(
x
,
x
k
), add two new nodes y
′ and y
′′ to x, and set w
(
y
′
)
,
c
(
x
,
y
′
) and w
(
y
′′
)
,
c
(
x
,
y
′′
) to zero. For each t
=
1,2
,
…
,
⌈
k
/
2
⌉, we add new edge (
y
′
,
x
t
) and set c
(
y
′
,
x
t
) to c
(
x
,
x
t
). For each t
=
⌈
k
/
2
⌉
+
1
,
…
,
k, we add new edge (
y
′′
,
x
t
) and set c
(
y
′′
,
x
t
) to c
(
x
,
x
t
).We use the above way recursively to process every node ofT
=
(
V
,
E
,
w
,
c
) top-down to obtain a binary tree b
(
T
)
=
(
V
b
,
E
b
,
w
b
,
c
b
). This idea can be described as algorithmBINY. Our way improves that one proposed by Chen et al. [18]. Moreover, we will analyze the performance ofBINY in the following while they provided no analysis of their algorithm [18].Theorem 3.
For eachx of  T with d
(
x
)
=
k
≥
3, the subtree of b
(
T
) derived from transforming s
t
a
r
(
x
) byBINY has a height of O
(
log
⁡
k
) and has 5
k
/
3
-
2 dummy nodes added in the worst case.Proof.
The essence ofBINY processing s
t
a
r
(
x
) is to bisect all the children of x recursively. At the final step, two dummy nodes are added if four nodes are bisected into two groups of two nodes and three dummy nodes are added if three nodes are bisected into one group of two nodes and one group of one node. So,BINY adds the most dummy nodes in the worst case of k
=
3
·
2
t. In this case, the subtree of b
(
T
) derived from transforming s
t
a
r
(
x
) byBINY has a height of t
+
2 and the number of dummy nodes added is 2
(
1
-
2
t
)
/
(
1
-
2
)
+
3
·
2
t
=
5
·
2
t
-
2. In fact, we investigate that the subtree of b
(
T
) derived from a star with k nodes satisfying that 2
t
+
1
+
1
<
k
≤
2
t
+
2 has a height of t
+
2. So, log
⁡
k
≤
t
+
2
<
log
⁡
k
+
1. Therefore, the subtree of b
(
T
) derived from s
t
a
r
(
x
) has a height of O
(
log
⁡
k
). The number of all the dummy nodes added byBINY in the worst case is 5
·
2
t
-
2
=
5
·
2
log
⁡
⁡
(
k
/
3
)
-
2
=
5
k
/
3
-
2.Theorem 4.
BINY can transform T with n nodes into b
(
T
) with a height of at most 2
(
n
-
1
)
/
3, which takes O
(
n
) time and adds at most (
5
/
3
)
n
-
11
/
3 dummy nodes.Proof.
Suppose thatT has K stars and every s
t
a
r
(
x
i
),  1
≤
i
≤
K, has k
i children. Obviously, ∑
i
=
1
K
‍
k
i
=
|
E
|
=
n
-
1. By Theorem 3,BINY adds 5
k
i
/
3
-
2 dummy nodes for every s
t
a
r
(
x
i
) in the worst case of k
i
=
3
·
2
t
i,  t
i
≥
0,  ∀
1
≤
i
≤
K. So, the number of dummy nodes added byBINY is ∑
i
=
1
K
‍
(
5
k
i
/
3
-
2
)
=
(
5
/
3
)
∑
i
=
1
K
‍
k
i
-
2
K
≤
(
5
/
3
)
(
n
-
1
)
-
2
=
(
5
/
3
)
n
-
11
/
3.
Next, we discuss the height ofb
(
T
). We construct a worst-case tree T
Δ consisting of K three-children stars lined one by one. In other words, for every star of T other than the bottom one, two children of the star are leaves of T and the other one is the center of the next star. Clearly, T
Δ satisfies that 3
K
=
n
-
1. Since the subtree of b
(
T
) derived from transforming a three-children star has height of 2, the height of T
Δ is 2
K
=
2
·
(
(
n
-
1
)
/
3
)
=
2
(
n
-
1
)
/
3.
Therefore, we obtain|
V
b
|
=
n
+
(
(
5
/
3
)
n
-
11
/
3
)
=
(
8
/
3
)
n
-
(
11
/
3
) in the worst case and conclude thatBINY spends O
(
n
) time to transform T into b
(
T
).Theorem 5.
CLP in a general treeT is equivalent to CLP in b
(
T
).Proof.
This theorem is equivalent to the proposition that no cache is located at one dummy node in any optimal solution to CLP inb
(
T
). Suppose that a cache is located at a dummy node α in an optimal solution L and α is added by transforming s
t
a
r
(
x
) byBINY. The cost of a new solution L
′ obtained by replacing α with x into L is less than the cost of L. This causes a contradiction.The binary tree obtained by applying Tamir’s algorithm [15] to a general tree T with n nodes has a height of at most n
-
2, while one obtained by applyingBINY to T has a height of at most 2
(
n
-
1
)
/
3. In terms of height of binary tree,BINY is superior to Tamir’s algorithm. This will help to reduce the running time of algorithmSUB  (Algorithm 1) shown in Section 3.3.Algorithm 1:
SUB.
Input: a binary tree B rooted at s;
Output: an optimal solution of p-CLP on B and F
[
s
]
[
s
]
[
p
];
Step  0. Use DFS based algorithm in [24] to traverse B, and record
the parent node of every nodex of B;
Step  1. for  k from 1 up to h  do
Use|
V
(
B
(
k
)
)
| processors to work simultaneously and all
processors do the same work as follows for allx
∈
V
(
B
(
k
)
):
if  x is a leaf node then
UseDFS based algorithm in [24] to compute c
(
x
,
y
) and initialize
F
[
x
]
[
y
]
[
1
]
←
0
,
F
[
x
]
[
y
]
[
0
]
←
w
(
x
)
·
c
(
x
,
y
) for any y
∈
π
(
s
,
x
);
Step  2. for  k from 1 up to h  do
Use|
V
(
B
(
k
)
)
| processors to work simultaneously and all
processors do the same work as follows for allx
∈
V
(
B
(
k
)
):
if  x is a nonleaf node then
for each q from 0 up to p  do
if  0
≤
q
≤
min
⁡
{
p
,
|
V
(
B
x
)
|
}  then
UseDFS based algorithm in [24] to compute c
(
x
,
y
) and
then computeF
[
x
]
[
y
]
[
q
] by (6) for any y
∈
π
(
s
,
x
);


## 3.3. Algorithm for CLP on Trees

By Theorem5, we only need to discuss CLP on binary trees. Let B be a binary tree and s the server (root) node, and let V
(
·
) denote the node set of B or its subtree. For any node x of B, we let B
x denote the subtree of B rooted at x. Let x
l and x
r be the left child and right child of x, respectively, and then let B
x
l (resp. B
x
r) denote the subtree of B
x rooted at x
l (resp. x
r). We use h to denote the height of B and 1,2
,
…
,
h to label the levels of B bottom-up, and we use B
(
k
) to denote the kth level of B. Let F
[
x
]
[
y
]
[
q
] denote the minimum cost of the subproblem of p-CLP on B
x when the closest cache to x on π
(
x
,
s
) is located at y and q caches are placed in B
x. Similar to the idea of solving the p-proxy problem in [18], we propose our way of computing F
[
x
]
[
y
]
[
q
] and giving a new proof, shown in Theorem 6.Theorem 6.
For each nodex of B other than leaves, each node y on π
(
x
,
s
), and each 0
≤
q
≤
min
⁡
{
p
,
|
V
(
B
x
)
|
}, one has
(6)
F
[
x
]
[
y
]
[
q
]
=
min
⁡
{
min
⁡
0
≤
q
l
≤
q
-
1
,
q
r
=
q
-
q
l
-
1
{
F
[
x
l
]
[
x
]
[
q
l
]
+
F
[
x
r
]
[
x
]
[
q
r
]
}
,
min
⁡
0
≤
q
l
≤
q
,
q
r
=
q
-
q
l
{
F
[
x
l
]
[
y
]
[
q
l
]
+
F
[
x
r
]
[
y
]
[
q
r
]
+
w
(
x
)
·
c
(
x
,
y
)
}
.Proof.
For any nodex of B, we need to consider whether a cache is located at x or not when discussing the subproblem of p-CLP on B
x.(1)
If a cache is located atx, then x needs no paying for its overall demand. So, the cost of the subproblem of p-CLP on B
x is equal to the sum of that on B
x
l and that on B
x
r. When the closest cache to x on π
(
s
,
x
) is located at y, we observe that x is the closest cache on π
(
s
,
x
) to x
l and x
r. The possible number q of caches placed in B
x is at most p while at most |
V
(
B
x
)
|. The number q
l of caches in B
x
l plus the number q
r of caches in B
x
r is equal to q
-
1. The key work is to find the optimal (
q
l
,
q
r
)-CAS with q
l
+
q
r
=
q
-
1, from which the cost of the subproblem of p-CLP on B
x results is equal to
(7)
min
⁡
0
≤
q
l
≤
q
-
1
,
q
r
=
q
-
q
l
-
1
{
F
[
x
l
]
[
x
]
[
q
l
]
+
F
[
x
r
]
[
x
]
[
q
r
]
}
.
(2)
If no cache is located atx, then the cost of x paying for its overall demand is w
(
x
)
·
c
(
x
,
y
). So, the cost of the subproblem of p-CLP on B
x is equal to the sum of that on B
x
l and that on B
x
r and the cost of x. When the closest cache to x on π
(
s
,
x
) is located at y, we see that y is also the closest cache on π
(
s
,
x
) to x
l and x
r. As discussed above, q
≤
min
⁡
{
p
,
|
V
(
B
x
)
|
}. The number q
l of caches in B
x
l plus the number q
r of caches in B
x
r is equal to q. The key work is to find the optimal (
q
l
,
q
r
)-CAS with q
l
+
q
r
=
q, from which the cost of the subproblem of p-CLP on B
x results is equal to
(8)
min
⁡
0
≤
q
l
≤
q
,
q
r
=
q
-
q
l
{
F
[
x
l
]
[
y
]
[
q
l
]
+
F
[
x
r
]
[
y
]
[
q
r
]
+
w
(
x
)
·
c
(
x
,
y
)
F
[
x
l
]
[
y
]
[
q
l
]
}
.Obviously, the case ofq
<
0 is forbidden. Let F
[
x
]
[
y
]
[
q
]
=
∞,  ∀
q
<
0 for each node x of B and each node y on π
(
s
,
x
). From the definition of F
[
x
]
[
y
]
[
q
], we know that F
[
s
]
[
s
]
[
p
] is just the minimum cost of p-CLP. Initially, we set F
[
x
]
[
y
]
[
0
]
=
w
(
x
)
·
c
(
x
,
y
) and F
[
x
]
[
y
]
[
1
]
=
0 for each leaf node x of B and each node y on π
(
s
,
x
).We can first use thedepth-first search (DFS) based algorithm in [24] to traverse B, by which we can record the parent node of every node x (thus record π
(
s
,
x
) step by step) and compute the cost of path connecting any node and its ancestor. Based on Theorem 6 and above discussions, we devise a bottom-up dynamic programming algorithm, which can be described as a parallel algorithmSUB by using the techniques in [25].Theorem 7.
Given any binary treeB with n nodes and a height of h,SUB runs in O
(
p
h
2
+
n
) time for computing p-CLP on B.Proof.
Step 0 usesDFS based algorithm in [24] to traverse B, which runs O
(
n
) time. In Step 1, for each level k
=
1,2
,
…
,
h, the processor at every leaf node x
∈
V
(
B
(
k
)
) uses the algorithm in [24] to make initialization for each y
∈
π
(
s
,
x
), which takes O
(
h
) time. So, Step 1 runs at most O
(
h
2
) time. In Step 2, for each level k
=
1,2
,
…
,
h, the processor at every nonleaf node x
∈
V
(
B
(
k
)
) uses the algorithm in [24] to compute c
(
x
,
y
) and then compute F
[
x
]
[
y
]
[
q
] by (6) for every 0
≤
q
≤
min
⁡
{
p
,
|
V
(
B
x
)
|
} and every y
∈
π
(
s
,
x
), which takes at most O
(
p
2
h
) time. So, Step 2 runs at most O
(
p
2
h
2
) time. We can use the method in [15] to infer that the practical running time of Step 2 is O
(
p
h
2
). Therefore,SUB runs in O
(
p
h
2
+
n
) time.


## 3.4. Algorithm for(
p
,
2
)-CSOP CLP on General Graphs

Based on (5) and discussions therein, we can solve (
p
,
2
)-CSOP CLP on a general graph G by first computing C
(
T
(
s
1
)
,
p
1
) in T
(
s
1
) and C
(
T
(
s
2
)
,
p
2
) in T
(
s
2
) for any (
p
1
,
p
2
)-CAS with p
1
+
p
2
=
p and then determining an optimal (
p
1
,
p
2
)-CAS such that the sum of C
(
T
(
s
1
)
,
p
1
) and C
(
T
(
s
2
)
,
p
2
) is minimized. We discover that the output F
[
s
i
]
[
s
i
]
[
p
i
],  i
=
1,2, ofSUB is just the value of C
(
T
(
s
i
)
,
p
i
) when we applySUB to T
(
s
i
). This forms our algorithm for (
p
,
2
)-CSOP CLP on a general graph, described as algorithmGLOB (Algorithm 2).Algorithm 2:
GLOB.
Input: T
(
s
1
) and T
(
s
2
) derived from G
=
(
V
,
E
,
w
,
c
) with s
1 and s
2;
Output: Γ
*;
Step  0. Use BINY to transform T
(
s
1
) into b
(
T
(
s
1
)
) and T
(
s
2
) into b
(
T
(
s
2
)
);
Step  1. Δ
←
∞;
for  p
1 from 0 up to p  do (then p
2
=
p
-
p
1)
ApplySUB to b
(
T
(
s
i
)
)
,
i
=
1,2 to obtain F
[
s
i
]
[
s
i
]
[
p
i
];
C
(
b
(
T
(
s
i
)
)
,
p
i
)
←
F
[
s
i
]
[
s
i
]
[
p
i
];
if  C
(
b
(
T
(
s
1
)
)
,
p
1
)
+
C
(
b
(
T
(
s
2
)
)
,
p
2
)
<
Δ  then
Δ
←
C
(
b
(
T
(
s
1
)
)
,
p
1
)
+
C
(
b
(
T
(
s
2
)
)
,
p
2
);
Γ
*
(
s
1
)
←
Γ
(
s
1
), Γ
*
(
s
2
)
←
Γ
(
s
2
);
Step  2. Γ
*
←
Γ
*
(
s
1
)
∪
Γ
*
(
s
2
);Suppose thatT
(
s
1
) has n
1 nodes and T
(
s
2
) has n
2 nodes. Clearly, n
1
+
n
2
=
n.GLOB usesBINY to transform T
(
s
1
) into b
(
T
(
s
1
)
) and T
(
s
2
) into b
(
T
(
s
2
)
). From Theorem 4, we know that b
(
T
(
s
i
)
),  i
=
1,2, has at most (
8
/
3
)
n
i
-
11
/
3 nodes including at most (
5
/
3
)
n
i
-
11
/
3 dummy nodes and has a height of at most 2
(
n
i
-
1
)
/
3. Let h
i denote the height of b
(
T
(
s
i
)
). For any (
p
1
,
p
2
)-CAS with p
1
+
p
2
=
p,GLOB appliesSUB to p
1-CLP on b
(
T
(
s
1
)
) and p
2-CLP on b
(
T
(
s
2
)
), respectively. It follows from Theorem 7 that the former takes at most O
(
p
1
h
1
2
+
(
8
/
3
)
n
1
) time and the latter takes at most O
(
p
2
h
2
2
+
(
8
/
3
)
n
2
) time. Therefore, the running time ofGLOB is at most
(9)
∑
p
1
=
0
p
‍
O
(
(
p
1
h
1
2
+
8
3
n
1
)
+
(
p
2
h
2
2
+
8
3
n
2
)
)
=
∑
p
1
=
0
p
‍
O
(
p
1
h
1
2
+
8
3
n
1
+
(
p
-
p
1
)
h
2
2
+
8
3
(
n
-
n
1
)
)
≤
O
(
p
2
·
max
⁡
{
h
1
2
,
h
2
2
}
+
8
3
n
p
)
.
Further, we take h
1
≤
2
(
n
1
-
1
)
/
3 and h
2
≤
2
(
n
2
-
1
)
/
3 into the above inequality to obtain that the running time ofGLOB in the worst case is at most
(10)
O
(
p
2
max
⁡
{
4
(
n
1
-
1
)
2
9
,
4
(
n
2
-
1
)
2
9
}
+
8
3
n
p
)
≤
O
(
4
9
p
2
n
2
)
.Theorem 8.
Given an undirected graphG
=
(
V
,
E
,
w
,
c
) with n nodes and two server nodes,GLOB runs in O
(
p
2
max
⁡
{
h
1
2
,
h
2
2
}
+
(
8
/
3
)
n
p
) time for (
p
,
2
)-CSOP CLP on G and runs in at most O
(
(
4
/
9
)
p
2
n
2
) time in the worst case.


## 4. Generalization

In this section, we discuss thep
-cache location problem with
m
identical servers under CSOP (abbreviated to (
p
,
m
)-CSOP CLP) on an undirected graph G
=
(
V
,
E
,
w
,
c
). Let S
=
{
s
1
,
…
,
s
m
} be a collection of m identical servers. Given any set Ω
⊂
V
∖
S, we let c
(
z
,
Ω
∪
S
) denote the cost of node z paying for its per demand and let f
(
Ω
) denote the total cost of all the nodes paying for their overall demand; that is, f
(
Ω
)
=
∑
z
∈
V
‍
w
(
z
)
c
(
z
,
Ω
∪
S
). The aim of (
p
,
m
)-CSOP CLP is to find p cache locations in G to minimize the total cost of all the nodes paying for their overall demand. In essence, (
p
,
m
)-CSOP CLP aims to find an optimal set Ω
* to minimize the value of f
(
Ω
); that is, f
(
Ω
*
)
=
min
⁡
Ω
⊂
V
∖
S
f
(
Ω
).In(
p
,
m
)-CSOP CLP, every client connects to the closest server to itself via a shortest route and gets information from the closest cache on the route or server. Let V
(
s
i
)
,
1
≤
i
≤
m be the subset of nodes of G to which s
i is the closest server. Let T
(
s
i
)
,
1
≤
i
≤
m denote the single-source shortest paths tree in G with s
i as origin spanning V
(
s
i
) and let Ω
(
s
i
) denote the subset of caches placed in T
(
s
i
). Hence, we can rewrite f
(
Ω
) to be
(11)
f
(
Ω
)
=
f
(
⋃
i
=
1
m
‍
Ω
(
s
i
)
)
=
∑
i
=
1
m
∑
z
∈
T
(
s
i
)
w
(
z
)
·
c
(
z
,
Ω
(
s
i
)
∪
{
s
i
}
)
.Letp
i be the number of caches in Ω
(
s
i
). Let p
→
=
(
p
1
,
p
2
,
…
,
p
m
) with ∑
i
=
1
m
‍
p
i
=
p. Such a combination of Ω
(
s
i
)
,
1
≤
i
≤
m having p
i caches is denoted as p
→-CAS. Thus, (
p
,
m
)-CSOP CLP consists of m CLPs when m servers are placed at m predesignated locations of G. For any p
→-CAS, (
p
,
m
)-CSOP CLP consists of m subproblems; that is, p
i-CLP in T
(
s
i
)
,
1
≤
i
≤
m. Let C
(
G
,
p
) denote the minimum cost of (
p
,
m
)-CSOP CLP on G and let C
(
T
(
s
i
)
,
p
i
),  1
≤
i
≤
m denote the minimum cost of p
i-CLP in T
(
s
i
). Therefore,
(12)
C
(
G
,
p
)
=
min
⁡
∀
(
p
1
,
…
,
p
m
)
∑
i
=
1
m
C
(
T
(
s
i
)
,
p
i
)
.Based on (12), for any p
→-CAS with ∑
i
=
1
m
‍
p
i
=
p, we can solve (
p
,
m
)-CSOP CLP on G by first computing C
(
T
(
s
i
)
,
p
i
) in T
(
s
i
) for every 1
≤
i
≤
m and then determining an optimal p
→-CAS such that the sum of C
(
T
(
s
i
)
,
p
i
),  1
≤
i
≤
m, is minimized. This idea can be described as algorithmEXTD.Lemma 9.
The number ofp
→-CASs in (
p
,
m
)-CSOP CLP is (
m
+
p
-
1
p
).Proof.
The problem of allocatingp caches to m distinct subtrees can be reduced to the model of putting p same balls into m distinct boxes. We first draw p
+
m
-
1 dots one by one in a line and then select p dots to place balls and the other m
-
1 dots to place baffles. The line is partitioned into m sections (boxes) by these m
-
1 baffles together with two immaterial baffles at two ends of the line. There are (
m
+
p
-
1
m
-
1
) ways in all to partition the line into m boxes. Every way of partitioning the line produces a p
→-CAS. Therefore, (
p
,
m
)-CSOP CLP contains (
m
+
p
-
1
p
)
p
→-CASs.For anyp
→-CAS with ∑
i
=
1
m
‍
p
i
=
p, the combination of Theorems 7 and 4 yields that the running time ofEXTD solving all p
i-CLP in T
(
s
i
)
,
1
≤
i
≤
m, is
(13)
∑
i
=
1
m
O
(
p
i
h
i
2
+
8
3
n
i
)
=
O
(
∑
i
=
1
m
p
i
h
i
2
+
8
3
∑
i
=
1
m
n
i
)
≤
O
(
p
·
max
⁡
1
≤
i
≤
m
h
i
2
·
+
8
3
n
)
.
By Lemma 9, we conclude that the running time ofEXTD is
(14)
∑
∀
(
p
1
,
…
,
p
m
)
∑
i
=
1
m
O
(
p
i
h
i
2
+
8
3
n
i
)
≤
O
(
(
p
·
max
⁡
1
≤
i
≤
m
h
i
2
+
8
3
n
)
(
m
+
p
-
1
p
)
)
.
From h
i
≤
2
(
n
i
-
1
)
/
3,  n
i
≤
n
+
1
-
m for every 1
≤
i
≤
m, we get
(15)
max
⁡
1
≤
i
≤
m
h
i
2
≤
max
⁡
1
≤
i
≤
m
(
2
(
n
i
-
1
)
3
)
2
≤
4
9
(
n
-
m
)
2
.
Obviously, we have
(16)
(
m
+
p
-
1
p
)
=
(
m
+
p
-
1
)
!
p
!
(
m
-
1
)
!
≤
(
m
+
p
)
p
p
!
.
We take (15) and (16) into (14) to obtain that the running time ofEXTD in the worst case is at most O
(
(
4
/
9
)
(
n
-
m
)
2
(
(
m
+
p
)
p
/
(
p
-
1
)
!
)
).Theorem 10.
Given an undirected graphG
=
(
V
,
E
,
w
,
c
) with n nodes and m servers,EXTD runs in O
(
m
p
(
p
·
max
⁡
1
≤
i
≤
m
h
i
2
+
(
8
/
3
)
n
)
) time for (
p
,
m
)-CSOP CLP on G and runs in at most O
(
(
4
/
9
)
(
n
-
m
)
2
(
(
m
+
p
)
p
/
(
p
-
1
)
!
)
) time in the worst case.


## 5. Numerical Experiments

### 5.1. An Illustrative Example

In this subsection, we first give an example to illustrate our algorithmGLOB for computing (
p
,
2
)-CSOP CLP. Considering that (
p
,
2
)-CSOP CLP on a general network can be reduced to that on a corresponding tree network, we select a tree network as our example for ease of illustration, shown in Figure 1. The example tree T has 25 client nodes labelled by u
1
,
u
2
,
…
,
u
25 and two server nodes labelled by s
1 and s
2. The number w
k,  1
≤
k
≤
25, on client node u
k represents the demand account of u
k, and the number on every edge represents the cost of one node paying for its per demand. For instance, the demand account of u
5 is 0.76, and the total cost of u
5 paying for its overall demand is 1.55
×
0.76
=
1.1780.Figure 1
An example tree network.First, we make preparation works. The unique pathΠ
[
s
1
,
s
2
] of T connecting s
1 and s
2 is s
1
u
14
u
18
u
19
u
15
s
2. It is easy to see that u
14 and u
18 are closer to s
1 than s
2 while u
19 and u
15 are closer to s
2 than s
1. Thus, N
(
s
1
)
=
{
s
1
,
u
14
,
u
18
} and N
(
s
1
)
=
{
u
19
,
u
15
,
s
2
}. Based on Lemma 2, we use theDFS based approach to obtain T
(
s
1
) and T
(
s
2
), shown in the left subfigure of Figure 2 and the left subfigure of Figure 3, respectively. Both the heights of T
(
s
1
) and T
(
s
2
) are three. We applyBINY to transform T
(
s
1
) into a binary tree b
(
T
(
s
1
)
) shown in the right subfigure of Figure 2, where eight dummy nodes added byBINY are labelled by d
1
,
d
2
,
…
,
d
8. Similarly, we obtain b
(
T
(
s
2
)
) shown in the right subfigure of Figure 3, where nine dummy nodes are labelled by d
1
,
d
2
,
…
,
d
9. All the dummy nodes have a weight of zero and all the edges between a dummy node and its parent node have a weight of zero. Both the height of T
(
s
1
) and T
(
s
2
) are five.Figure 2
Illustration forT
(
s
1
) and b
(
T
(
s
1
)
).Figure 3
Illustration forT
(
s
2
) and b
(
T
(
s
2
)
).Next, we useGLOB to solve (
p
,
2
)-CSOP CLP on T. Set p
=
4 and p
=
5 as examples. For any (
p
1
,
p
2
)-CAS with p
1
+
p
2
=
4,GLOB computes the minimum cost C
(
T
(
s
1
)
,
p
1
) of p
1-CLP in T
(
s
1
) and the set Γ
1
*
(
s
1
) of cache locations and the minimum cost C
(
T
(
s
2
)
,
p
2
) of p
2-CLP in T
(
s
2
) and Γ
1
*
(
s
2
). The data are listed in Table 1. Clearly, the optimal value C
(
T
,
4
) of (
4,2
)-CSOP CLP on T is 33.2950, and thus the optimal set Γ
1
* of cache locations is {
u
8
,
u
17
,
u
18
,
u
20
}. Similarly, the data output byGLOB for any (
p
1
,
p
2
)-CAS with p
1
+
p
2
=
5 are listed in Table 2. Clearly, the optimal value C
(
T
,
5
) of (
5,2
)-CSOP CLP on T is 27.7770, and thus the optimal set Γ
2
* is {
u
5
,
u
8
,
u
17
,
u
18
,
u
20
}.Table 1
Major data output byGLOB for (
4,2
)-CSOP CLP on T.
p
1
Γ
1
*
(
s
1
)
C
(
T
(
s
1
)
,
p
1
)
p
2
Γ
2
*
(
s
2
)
C
(
T
(
s
2
)
,
p
2
)
Total cost
0
37.2100
4
u
3
,
u
8
,
u
15
,
u
20
8.5600
45.7700
1
u
17
27.3100
3
u
8
,
u
15
,
u
20
10.6600
37.9700
2
u
17
,
u
18
19.9150
2
u
8
,
u
20
13.3800
33.2950
3
u
5
,
u
17
,
u
18
14.3970
1
u
8
19.0350
33.4320
4
u
5
,
u
13
,
u
17
,
u
18
12.4170
0
30.1050
42.5220Table 2
Major data output byGLOB for (
5,2
)-CSOP CLP on T.
p
1
Γ
1
*
(
s
1
)
C
(
T
(
s
1
)
,
p
1
)
p
2
Γ
2
*
(
s
2
)
C
(
T
(
s
2
)
,
p
2
)
total cost
0
37.2100
5
u
3
,
u
4
,
u
8
,
u
15
,
u
20
6.7400
43.9500
1
u
17
27.3100
4
u
3
,
u
8
,
u
15
,
u
20
8.5600
35.8700
2
u
17
,
u
18
19.9150
3
u
8
,
u
15
,
u
20
10.6600
30.5750
3
u
5
,
u
17
,
u
18
14.3970
2
u
8
,
u
20
13.3800
27.7770
4
u
5
,
u
13
,
u
17
,
u
18
12.4170
1
u
8
19.0350
31.4520
5
u
1
,
u
5
,
u
13
,
u
17
,
u
18
10.5895
0
30.1050
40.6945


### 5.2. Comparison of Running Times

In this subsection, we make a large number of numerical experiments to compare the running times of our algorithmGLOB andEXTD, respectively. In view of the fact that (
p
,
m
)-CSOP CLP with m
≥
2 on a general graph can be reduced to multiple CLPs on binary trees, we select a series ofcomplete binary trees as examples for ease of comparison. All the binary trees are generated randomly and have almost same number of nodes. We build a centralized parallel computer system (i.e., a star network with one central computer and five parallel computers) by connecting six identical PCs equipped with 2 GB RAM and Intel core i5 CPU using a Windows 7 operating system. Our numerical experiments were carried out on this computer system.For(
p
,
2
)-CSOP CLP, we consider different inputs of n and p:  n
=
100,102,104
,
…
,
200 and 2
≤
p
≤
20. All the binary trees we select have odd nodes. Given n
=
200 and p
=
20, there are 100 different combinations of n
1 and n
2; that is, n
1
=
1,3
,
5
,
…
,
199 and n
2
=
200
-
n
1. All the running times ofGLOB for 100 combinations are depicted in Figure 4(a). Given any combination of n and p, we record the average running time of 100 combinations. In Figure 4(b), all the average times for the combinations of n and fixed p are depicted, for any given p
=
5,10,15,20. In Figure 4(c), all the average times for the combinations of p and fixed n are depicted, for any given n
=
100,120,140,160,180,200. In Figure 4(d), all the average times for the combinations of n and p are depicted.Compare the running times ofGLOB for n
=
100,102,104
,
…
,
200 and 2
≤
p
≤
20.
(a)
The number of nodes in subtreeT(s
1)
(b)
The number of nodes:n
=
100,102
,
…
,
200
(c)
The number of caches:p
=
2,3
,
4
,
…
,
20
(d)For(
p
,
m
)-CSOP CLP, we are given n
=
200 or 201 and consider different inputs of m and p:  2
≤
m
≤
5 and 2
≤
p
≤
20. All the binary trees we select have odd nodes. Given m
=
5 and p
=
20, there are 10626 different CAS’s. All the running times ofEXTD for 10626 CAS’s are depicted in Figure 5(a). Given any combination of m and p, we record the average running time of 10626 CAS’s. In Figure 5(b), all the average times for the combinations of m and fixed p are depicted, for any given p
=
5,10,15,20. In Figure 4(c), all the average times for the combinations of p and fixed m are depicted, for any m
=
2,3
,
4,5. In Figure 5(d), all the average times for the combinations of m and p are depicted.Compare the running times ofEXTD for m
=
2,3
,
4,5 and 2
≤
p
≤
20 and fixed n
=
200 or 201.
(a)
Cache allocation schemes
(b)
The number of servers:m
=
2,3
,
4,5
(c)
The number of caches:p
=
2,3
,
4
,
…
,
20
(d)Next, we present the running times ofEXTD for different inputs of n. Given m
=
5, we consider six different combinations of p
=
20,22,24,26,28,30 and fixed m
=
5. In Figure 6(a), all the average times for n
=
205
+
30
×
(
i
-
1
),  1
≤
i
≤
5, are depicted. Also, we depict all the average times for the combinations of n and p in Figure 6(b). Note that every complete binary tree has 41
+
6
×
(
i
-
1
) nodes. Given p
=
30, we consider four different combinations of m
=
2,3
,
4,5 and fixed p
=
30. In Figure 6(c), all the average times for exactly or approximately n
=
205
+
30
×
(
i
-
1
),  1
≤
i
≤
5 are depicted. In Figure 6(d), all the average times for the combinations of n and m are depicted.Compare the running times ofEXTD for n
=
205
+
30
×
(
i
-
1
)
,
1
≤
i
≤
5 and m
=
2,3
,
4,5 and p
=
20,22,24,26,28,30.
(a)
The number of nodes:n
=
205
+
30
(
i
-
1
), i
=
1,2
,
3,4
,
5
(b)
(c)
The number of nodes:n
=
205
+
30
(
i
-
1
), i
=
1,2
,
3,4
,
5
(d)


## 5.1. An Illustrative Example

In this subsection, we first give an example to illustrate our algorithmGLOB for computing (
p
,
2
)-CSOP CLP. Considering that (
p
,
2
)-CSOP CLP on a general network can be reduced to that on a corresponding tree network, we select a tree network as our example for ease of illustration, shown in Figure 1. The example tree T has 25 client nodes labelled by u
1
,
u
2
,
…
,
u
25 and two server nodes labelled by s
1 and s
2. The number w
k,  1
≤
k
≤
25, on client node u
k represents the demand account of u
k, and the number on every edge represents the cost of one node paying for its per demand. For instance, the demand account of u
5 is 0.76, and the total cost of u
5 paying for its overall demand is 1.55
×
0.76
=
1.1780.Figure 1
An example tree network.First, we make preparation works. The unique pathΠ
[
s
1
,
s
2
] of T connecting s
1 and s
2 is s
1
u
14
u
18
u
19
u
15
s
2. It is easy to see that u
14 and u
18 are closer to s
1 than s
2 while u
19 and u
15 are closer to s
2 than s
1. Thus, N
(
s
1
)
=
{
s
1
,
u
14
,
u
18
} and N
(
s
1
)
=
{
u
19
,
u
15
,
s
2
}. Based on Lemma 2, we use theDFS based approach to obtain T
(
s
1
) and T
(
s
2
), shown in the left subfigure of Figure 2 and the left subfigure of Figure 3, respectively. Both the heights of T
(
s
1
) and T
(
s
2
) are three. We applyBINY to transform T
(
s
1
) into a binary tree b
(
T
(
s
1
)
) shown in the right subfigure of Figure 2, where eight dummy nodes added byBINY are labelled by d
1
,
d
2
,
…
,
d
8. Similarly, we obtain b
(
T
(
s
2
)
) shown in the right subfigure of Figure 3, where nine dummy nodes are labelled by d
1
,
d
2
,
…
,
d
9. All the dummy nodes have a weight of zero and all the edges between a dummy node and its parent node have a weight of zero. Both the height of T
(
s
1
) and T
(
s
2
) are five.Figure 2
Illustration forT
(
s
1
) and b
(
T
(
s
1
)
).Figure 3
Illustration forT
(
s
2
) and b
(
T
(
s
2
)
).Next, we useGLOB to solve (
p
,
2
)-CSOP CLP on T. Set p
=
4 and p
=
5 as examples. For any (
p
1
,
p
2
)-CAS with p
1
+
p
2
=
4,GLOB computes the minimum cost C
(
T
(
s
1
)
,
p
1
) of p
1-CLP in T
(
s
1
) and the set Γ
1
*
(
s
1
) of cache locations and the minimum cost C
(
T
(
s
2
)
,
p
2
) of p
2-CLP in T
(
s
2
) and Γ
1
*
(
s
2
). The data are listed in Table 1. Clearly, the optimal value C
(
T
,
4
) of (
4,2
)-CSOP CLP on T is 33.2950, and thus the optimal set Γ
1
* of cache locations is {
u
8
,
u
17
,
u
18
,
u
20
}. Similarly, the data output byGLOB for any (
p
1
,
p
2
)-CAS with p
1
+
p
2
=
5 are listed in Table 2. Clearly, the optimal value C
(
T
,
5
) of (
5,2
)-CSOP CLP on T is 27.7770, and thus the optimal set Γ
2
* is {
u
5
,
u
8
,
u
17
,
u
18
,
u
20
}.Table 1
Major data output byGLOB for (
4,2
)-CSOP CLP on T.
p
1
Γ
1
*
(
s
1
)
C
(
T
(
s
1
)
,
p
1
)
p
2
Γ
2
*
(
s
2
)
C
(
T
(
s
2
)
,
p
2
)
Total cost
0
37.2100
4
u
3
,
u
8
,
u
15
,
u
20
8.5600
45.7700
1
u
17
27.3100
3
u
8
,
u
15
,
u
20
10.6600
37.9700
2
u
17
,
u
18
19.9150
2
u
8
,
u
20
13.3800
33.2950
3
u
5
,
u
17
,
u
18
14.3970
1
u
8
19.0350
33.4320
4
u
5
,
u
13
,
u
17
,
u
18
12.4170
0
30.1050
42.5220Table 2
Major data output byGLOB for (
5,2
)-CSOP CLP on T.
p
1
Γ
1
*
(
s
1
)
C
(
T
(
s
1
)
,
p
1
)
p
2
Γ
2
*
(
s
2
)
C
(
T
(
s
2
)
,
p
2
)
total cost
0
37.2100
5
u
3
,
u
4
,
u
8
,
u
15
,
u
20
6.7400
43.9500
1
u
17
27.3100
4
u
3
,
u
8
,
u
15
,
u
20
8.5600
35.8700
2
u
17
,
u
18
19.9150
3
u
8
,
u
15
,
u
20
10.6600
30.5750
3
u
5
,
u
17
,
u
18
14.3970
2
u
8
,
u
20
13.3800
27.7770
4
u
5
,
u
13
,
u
17
,
u
18
12.4170
1
u
8
19.0350
31.4520
5
u
1
,
u
5
,
u
13
,
u
17
,
u
18
10.5895
0
30.1050
40.6945


## 5.2. Comparison of Running Times

In this subsection, we make a large number of numerical experiments to compare the running times of our algorithmGLOB andEXTD, respectively. In view of the fact that (
p
,
m
)-CSOP CLP with m
≥
2 on a general graph can be reduced to multiple CLPs on binary trees, we select a series ofcomplete binary trees as examples for ease of comparison. All the binary trees are generated randomly and have almost same number of nodes. We build a centralized parallel computer system (i.e., a star network with one central computer and five parallel computers) by connecting six identical PCs equipped with 2 GB RAM and Intel core i5 CPU using a Windows 7 operating system. Our numerical experiments were carried out on this computer system.For(
p
,
2
)-CSOP CLP, we consider different inputs of n and p:  n
=
100,102,104
,
…
,
200 and 2
≤
p
≤
20. All the binary trees we select have odd nodes. Given n
=
200 and p
=
20, there are 100 different combinations of n
1 and n
2; that is, n
1
=
1,3
,
5
,
…
,
199 and n
2
=
200
-
n
1. All the running times ofGLOB for 100 combinations are depicted in Figure 4(a). Given any combination of n and p, we record the average running time of 100 combinations. In Figure 4(b), all the average times for the combinations of n and fixed p are depicted, for any given p
=
5,10,15,20. In Figure 4(c), all the average times for the combinations of p and fixed n are depicted, for any given n
=
100,120,140,160,180,200. In Figure 4(d), all the average times for the combinations of n and p are depicted.Compare the running times ofGLOB for n
=
100,102,104
,
…
,
200 and 2
≤
p
≤
20.
(a)
The number of nodes in subtreeT(s
1)
(b)
The number of nodes:n
=
100,102
,
…
,
200
(c)
The number of caches:p
=
2,3
,
4
,
…
,
20
(d)For(
p
,
m
)-CSOP CLP, we are given n
=
200 or 201 and consider different inputs of m and p:  2
≤
m
≤
5 and 2
≤
p
≤
20. All the binary trees we select have odd nodes. Given m
=
5 and p
=
20, there are 10626 different CAS’s. All the running times ofEXTD for 10626 CAS’s are depicted in Figure 5(a). Given any combination of m and p, we record the average running time of 10626 CAS’s. In Figure 5(b), all the average times for the combinations of m and fixed p are depicted, for any given p
=
5,10,15,20. In Figure 4(c), all the average times for the combinations of p and fixed m are depicted, for any m
=
2,3
,
4,5. In Figure 5(d), all the average times for the combinations of m and p are depicted.Compare the running times ofEXTD for m
=
2,3
,
4,5 and 2
≤
p
≤
20 and fixed n
=
200 or 201.
(a)
Cache allocation schemes
(b)
The number of servers:m
=
2,3
,
4,5
(c)
The number of caches:p
=
2,3
,
4
,
…
,
20
(d)Next, we present the running times ofEXTD for different inputs of n. Given m
=
5, we consider six different combinations of p
=
20,22,24,26,28,30 and fixed m
=
5. In Figure 6(a), all the average times for n
=
205
+
30
×
(
i
-
1
),  1
≤
i
≤
5, are depicted. Also, we depict all the average times for the combinations of n and p in Figure 6(b). Note that every complete binary tree has 41
+
6
×
(
i
-
1
) nodes. Given p
=
30, we consider four different combinations of m
=
2,3
,
4,5 and fixed p
=
30. In Figure 6(c), all the average times for exactly or approximately n
=
205
+
30
×
(
i
-
1
),  1
≤
i
≤
5 are depicted. In Figure 6(d), all the average times for the combinations of n and m are depicted.Compare the running times ofEXTD for n
=
205
+
30
×
(
i
-
1
)
,
1
≤
i
≤
5 and m
=
2,3
,
4,5 and p
=
20,22,24,26,28,30.
(a)
The number of nodes:n
=
205
+
30
(
i
-
1
), i
=
1,2
,
3,4
,
5
(b)
(c)
The number of nodes:n
=
205
+
30
(
i
-
1
), i
=
1,2
,
3,4
,
5
(d)


## 6. Conclusions

In this paper, we presented an efficient algorithmGLOB for (
p
,
2
)-CSOP CLP andEXTD for (
p
,
m
)-CSOP CLP based on a fast parallel algorithm for CLP, respectively.GLOB runs in a polynomial time whileEXTD applies to the cases of not too large p and m in general. Fortunately, both m and p are not so large in practice that the running time ofEXTD becomes intolerable with n increasing fast. Therefore, we think thatEXTD will have extensive applications.Every cache involved in this paper is identical to server; that is, every cache has the same contents as server. However, a cache sometimes only contains one part of contents. Suppose that every cache containsρ
% contents of server. Under CSOP, each node connects to the closest server to itself via a shortest route. On average, each node has ρ
% demand provided by the closest cache on the route and (
1
-
ρ
)% demand provided by the server. Hence, the cost of node z paying for its overall demand is equal to ρ
%
·
c
(
z
,
Ω
(
s
i
)
∪
{
s
i
}
)
+
(
1
-
ρ
%
)
·
c
(
z
,
s
i
). Let g
(
Ω
) denote the total cost of all the nodes paying for their overall demand. We have
(17)
g
(
Ω
)
=
g
(
⋃
i
=
1
m
Ω
(
s
i
)
)
=
∑
i
=
1
m
∑
z
∈
T
(
s
i
)
w
(
z
)
(
+
(
1
-
ρ
%
)
·
c
(
z
,
s
i
)
ρ
%
·
c
(
z
,
Ω
(
s
i
)
∪
{
s
i
}
)
+
(
1
-
ρ
%
)
·
c
(
z
,
s
i
)
)
.
This version of (
p
,
m
)-CSOP CLP aims to find an optimal set Ω
* such that g
(
Ω
) is minimized. The problem remains as one future research topic.



---

*Source: 586146-2014-08-24.xml*