Formal definitions and the Algorithms

The transformation of the placement problem to the set cover problem assumes that we are given a set of networks and their interconnections, as well as a specific routing policy that allows us to compute an end-to-end path for every pair of nodes in the networks. Typically, shortest path routing algorithm is used in intra-domain routing and for inter-domain traffic, packet flows are routed towards the nearest peering point between two networks (also called the ``hot-potato'' routing). With this routing policy, we can compute a routing table for each node $n_i$ and the cost of each routing path $c(n_i, n_j)$, which is the sum of the hop distances along the path. For each node $n_i$, we compute a set $S$ which includes all the nodes reachable from $n_i$ within the routing cost of $C$. This is to say that if a server is placed at the location of node $n_i$, then all the nodes within this set can be serviced by this server. If $n_i$ has co-location nodes, then the set $S$ also includes all nodes reachable from each of these co-location nodes within the cost of $C$. By varying the criteria of including a node in a set, for example varying the cost $C$ changes the service range of a server, we can explore different placement policies while using the same algorithms to find a solution for the set cover problem.

Let $S_1, S_2, \ldots, S_m$ be all the sets computed. The LP formulation of the set cover problem is:

$$\mbox{Objective:} \mbox{minimize } {\displaystyle \sum_{j=1}^{j=m} x_j}$$ (1)

$$\mbox{Subject to:} {\displaystyle \sum_{j=1}^{j=m} a_{ij} x_j \geq 1} \mbox{\hspace{4ex}for } i = 1 \ldots n$$ (2)

$$x_j \in \{0, 1\}$$

where $x_j$ is the selection variable of $S_j$, $a_{ij}$ is 1 if $n_i \in S_j$ and 0 otherwise.

A variation of the problem is to allow one primary and one backup server to cover each node. A backup server can cover twice the distance of the primary server. Let $T_1, T_2, \ldots, T_m$ be all the backup sets, and $b_{ij} = 1$ if $n_i \in T_j$ and 0 otherwise. The objective here is still to minimize the number of selected sets but with the additional constraints of:

$$\sum_{j=1}^{j=m} b_{ij}x_j \geq 2 \mbox{\hspace{4ex}for } i = 1 \ldots n$$ (3)

Since all nodes in the primary set are also in the backup set centered at the same server, $b_{ij} = 1$ if $a_{ij} = 1$; but we can not have a primary server also service the same node as the backup server -- the constraint in (5.3) ensures the selection of a different server as the backup.