ABSTRACT
Consider an undirected network G = (V ,E), where V = {1, . . . , n} is the node set, E = {(i, j)} is the edge set, and (i, j) ≡ (j, i). All network users require a critical service that is provided by network servers in a distributed manner. The cost of deploying and maintaining a server at node i is given as ci. For the successful operation of the network, each node must have access to at least one server. However, both nodes and edges of the network are subject to failure with known probabilities. Let r(i, j) be the reliability of edge (i, j) ∈ E and ri be the reliability of node i ∈ V . When edge (i, j) fails, the communication between nodes i and j is interrupted if it cannot be rerouted through an alternative path. When a node fails, all of its incident edges become inoperative. Therefore, if a server node fails, the server located on this node becomes unreachable by all users. The reliable network server assignment (RSA) problem is defined as determining a deployment of servers to maximize a measure of service availability as follows:
max z = R({s1, . . . , sn},G) n∑
i=1 cisi ≤ C
si ∈ {0, 1}
where si is the binary server assignment decision variable indicating whether a server is assigned to node i(si = 1) or not (si = 0), and R() is a measure of service availability.
