Weighted Cache Location Problem with Identical Servers

Abstract EN

This paper extends the well-known p -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.