# Two Optimization Algorithms for Name-Resolution Server Placement in Information-Centric Networking
## 4 Proposed Algorithms
### IIT-UP Algorithm  
While studying characteristics of multilayer overlay networks, we found that the topology of the lower-level layer is a subgraph of the higher-level layer network. Because the level is determined by a different latency, once two nodes can communicate with each other in a low-latency level, they can communicate no more than a high-latency upper bound. On the other hand, we found that it is servers in the lower-level layer that occupy the majority of the total count of servers. We took full advantage of these characteristics and proposed the IIT-UP algorithm. This is an algorithm that gives priority to the processing of the lower-level layer network. The topology that contains HMs in the sublayer forms a subgraph of the physical network and becomes the current layer's input. As shown in Figure 3, when dealing with the layer of level \(i\), edges in which latency is higher than the upper bound of this level are deleted, and each pair of nodes is connected if the transmission latency between them is lower than the upper bound. Then, the current layer's HMs are calculated with the minimum number using the relaxation technique of binary integer linear programming. For every node that is not in an HM, its closest HM is found and this node is made to be a member of the corresponding HEA. After this procedure, every HM has several HEA members. The maximum latency among the latencies of HEA members to their HM is found and recorded as an attribute of this HM, marked \(M\Ldot{i}\) (maximum latency). Then, partitioning in the level \(i+1\) layer begins, where the nodes of the level \(i+1\) layer come from \(HM\Ldot{i}\). Accordingly, the principles of addition and deletion edges for every node are constrained by the difference between \(t_{i}\) and \(ML\Ldot{i}\). Iteratively, after finishing partitioning in every layer, the output is the partitioning result containing HEAs and \(S_{HM}\). The specific algorithm is presented in Algorithm 2. ```
0:\(G(V,E,W)\), \(D\)
0:\(S_{HM}\), \(Hs\)
0:Parameters:\(T=\{t_{1},t_{2},\ldots,t_{L}\}\)
1: Initialization: \(HM^{0}=V\)
2: for each \(v\) in \(V\) do
3:\(v.ML\Ldot{i}=0\)
4: for \(i\) from 1 to \(L\) do
5: generate \(G\Big{(}V^{i},E^{i},W^{i}\Big{)}\) where \(V^{i}=HM\Ldot{i}-1\), \(E^{i}=\varnothing\), \(W^{i}=\varnothing\)
6: for each \(v\) in \(V^{i}\) do
7:\(v.\)color = white
8: for each \(u\), \(v\) in \(V^{i}\) that \(u\
eq v\) do
9: if \(d(u,v)<t_{i}-\max\Big{(}u.ML\Ldot{i},v.ML\Ldot{i}\Big{)}\) then
10: add \(e(u,v)\) to \(E^{i}\) and add \(w(u,v)=d(u,v)\) to \(W^{i}\)
11:\(HM\Ldot{i}\) = Choose_HM (\(G^{i}\))
12: for each \(v\) in \(V^{i}\) do
13: if \(v\) in \(HM\Ldot{i}\) then \(v.\)color = black
14: if not \(v.\)color = black then
15: find \(k\) with the minimum \(d(v,\ k)\) in \(HM\Ldot{i}\) and add \(v\) to \(H\Ldot{i}\)
16: add \(H\Ldot{i}\) to \(H\Ldot{i}\)
17: add \(HM\Ldot{i}\) to \(S_{HM}\) and add \(H\Ldot{i}\) to \(H\Ldot{i}\)
18: return \(S_{HM}\), Hs

### Computation of Hierarchical Elastic Areas Manager (HM) in a Single Layer

In IIT-DOWN and IIT-UP, a solution for a single layer network is needed as well. This problem is similar to finding an MDS set of a network. Here, we use the relaxation technique of binary integer linear programming to choose the HMs in the colored graph in the proposed algorithms. The specific algorithm is presented in Algorithm 3. However, other efficient single-layer approximation algorithms can also be applied here, but this is not the focus of the current research.