# Two Optimization Algorithms for Name-Resolution Server Placement in Information-Centric Networking
## 4 Proposed Algorithms
### IIT-UP Algorithm
```
Input:\(G(V,E,W)\) Output:\(H\)Ms
1: Initialization: \(\mathit{Vars}=\varnothing\)
2: for each \(v\) in \(V\) do
3: add a variable \(x_{v}\) to \(\mathit{Vars}\), \(x_{v}\in[0,1]\)
4: for each \(v\) in \(V\) do
5: if \(v.\)color = white then
6: add constraint \(x_{v}+\sum_{u:\ v\in E}x_{u}\geq 1\)
7: minimize \(\sum_{u:\ v\in V}x_{v}\) as optimize objective
8: do optimize
9: for each \(x_{v}\) in \(\mathit{Vars}\) do
10: if \(x_{v}>0\) then add \(v\) to \(H\)Ms
11: return \(H\)Ms
```

**Algorithm 3**Choose_HM

## 5 Evaluation and Discussion

### Simulation Network

For comparison's sake, we reproduced several existing algorithms and applied them to the placement problem of name resolution in multilayer overlay networks. The comparison algorithms were as follows:

* LHP: this algorithm was described in [23], and it is a heuristic graph-partitioning algorithm. It divides a physical network into one or more connected subgraphs with the latency level constrained from high to low. It chooses name-resolution nodes with the maximum degree and finds nodes they cover. Partitioning for each layer is achieved one by one;
* MDSM: this is the algorithm that was used to analyze the upper bound of MDS in multilayer networks in [51]. It is an algorithm that removes the neighboring nodes of higher-level dominators before solving the current level layer's MDS. The original MDSM does not satisfy the latency constraints in multilayer overlay networks. We extended the MDSM appropriately to adapt to the problem;
* Random allocate (RA): in this algorithm, the HM is chosen randomly, and users are allocated to an HEA, depending on which HM is closest to them. Figure 3: An example operation in IIT-UP. The network of each layer is solved in order from low to high. The HMs in the level \(i\) layer constitute the topology of the level \(i+1\) layer. We generated random graphs that follow the Barabasi-Albert (BA) scale-free model. It is a typical power-law degree distribution network that is widely used to simulate real network topology [53]. These networks' node sizes are from 100 to 2000, and the average degree is 2. According to [54], the end-to-end latency of the current internet is in the magnitude of ten milliseconds. Thus, we randomly set the weight of each edge from 0 to 10 ms. Considering the different latency requirements of major application scenarios in 5G-IoT, we chose \(T=\{\)10 ms, 25 ms, 50 ms\(\}\) as the upper bounds of the one-way transmission latency [55]. These bounds cannot represent all of the latency demands but are already able to evaluate the differences among these algorithms objectively. When it came to solving the HM choosing problem in a single layer, we used the Solving Constraint Integer Programs (SCIP) solver. It is currently one of the fastest non-commercial solvers for mixed integer programming and mixed integer non-linear programming [56]. The settings of the experiment are also shown in Table 2.

Figure 4 shows the network scenario of simulation experiments. The network topology consists of edge nodes such as base station and access point. Mobile edge computing in 5G technology makes it possible to deploy name-resolution servers at the edge of the network. The expected server placement result is also shown in the figure. The network is divided into three layers, corresponding to different upper bounds of name-resolution latency. At each layer, several edge nodes are selected to place name-resolution servers to provide deterministic resolution services. The experiment environment was created and run in Python 3.6 on a PC with an Intel Core (TM) i7-9750H CPU and 16 GB of RAM. For each network node size, we exp \begin{table}
\begin{tabular}{c c} \hline \hline
**Parameter** & **Value** \\ \hline Number of nodes & 100–2000 \\ Average degree & 2 \\ \(L\) & 3 \\ \(T\) (ms) & 10, 25, 50 \\ Latency scope (ms) & (0, 10] \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Evaluation setting. Figure 4: The network scenario of simulation experiments.