# Two Optimization Algorithms for Name-Resolution Server Placement in Information-Centric Networking
## 3 System Model and Problem Statement  
We modeled the placement problem of name-resolution servers in multilayer overlay networks with an undirected graph \(G(V,E,W)\). \(V=\{v_{1},v_{2},\ldots,v_{N}\}\) is the set of nodes in the physical network, including all network entities with the potential to place name-resolution servers. \(N\) is the total count of network entities. \(E\) is the set of edges, and edge \(e(u,\ v)\) belongs to \(E\) if node \(u\) and node \(v\) can communicate with each other without going through any other nodes in \(V\). \(W\) is the weight set of \(E\), and the weight \(w(u,\ v)\) is the one-way transmission latency between node \(u\) and node \(v\). We used a matrix \(D\) to denote the one-way transmission latencies for all pairs of nodes in \(G\), where \(d(u,\ v)\) represents the shortest path latency between node \(u\) and node \(v\). \(T=\{t_{1},t_{2},\ldots,t_{L}\}\) is a set that consists of upper bounds of each layer's constraint latencies, and \(L\) is the count of different latency scenarios. It is noteworthy that when it comes to the secure name-resolution scenarios, authentication and encryption processes may take some time. In these scenarios, upper bounds in \(T\) should be calculated by subtracting corresponding process time. For all \(0\leq i<j\leq L\), \(t_{i}<t_{j}\) holds, which means that higher-level HEAs have higher latency upper bounds. \(T\) is usually determined by application scenarios in the network. The detailed notations and descriptions used in this paper are summarized in Table 1.  
In this model, we can describe our optimization objective and the constraints of multilayer overlay networks more accurately with exact formulas. For a layer in level \(i\) with a latency upper bound of \(t_{i}\), we assume that \(G\) is divided into several HEAs. We record the count of HEAs as \(M^{i}\). Nodes and edges in each HEA form a subgraph \(G_{m}^{i}\big{(}V_{m}^{i},E_{m}^{i},W_{m}^{i}\big{)}\) of \(G\), \(m=1,2,\ldots,M^{i}\). \(HEA_{m}^{i}\) represents the cluster of \(G_{m}^{i}\), and \(HM_{m}^{i}\) represents the cluster head of \(HEA_{m}^{i}\). For all nodes \(v\) in \(V\), if node \(v\) is chosen as \(HM_{m}^{i}\), we record \(x_{v}^{i}=1\), otherwise, \(x_{v}^{i}=0\). In our model, different overlay layers can choose the same physical node for server placement, so we let the costs of deployment of the highest level represent the \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Description** \\ \hline \(V\) & the set of nodes that have the potential to place servers \\ \(N\) & the total count of nodes in \(V\) \\ \(E\) & the set of links directly connect between nodes \\ \(W\) & the set of one-way transmission latencies of links \\ \(D\) & \(N\times N\) matrix, the shortest path latencies between every pair of nodes in \(V\) \\ \(e(u,\ v)\) & the link between node \(u\) and node \(v\) \\ \(w(u,\ v)\) & the one-way transmission latencies of link \(e(u,\ v)\) \\ \(d(u,\ v)\) & the shortest path latency between node \(u\) and node \(v\) \\ \(T\) & the set of upper bounds of each level layer’s constraint latencies \\ \(L\) & the count of layer levels \\ \(i\) & the index of a level \\ \(M^{i}\) & the count of HEAs in level \(i\) \\ \(m\) & the index of HEA \\ \(HEA_{m}^{i}\) & the m-th cluster in level \(i\) \\ \(HM_{m}^{i}\) & the cluster head of the m-th HEA in level \(i\) \\ \(H_{m}^{i}\) & the cluster member set of the m-th HEA in level \(i\) \\ \(x_{v}^{i}\) & binary variable, equal to 1 if node \(v\) is chosen as an HM in level \(i\) \\ \(y_{v}^{i}\) & binary variable, equal to 0 if node \(v\) is chosen as HM in the level higher than \(i\) \\ \(\alpha^{i}\) & the costs of deploying a server at level \(i\) \\ \(S_{HM}\) & the global set of HM \\ \(ML^{i}\) & the attribute of a HM to record the maximum latency in its HEA \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of notation. costs of this physical server. If node \(v\) has been chosen as an HM in the level higher than \(i\), we record \(y_{v}^{i}=0\), otherwise, \(y_{v}^{i}=1\).