# Two Optimization Algorithms for Name-Resolution Server Placement in Information-Centric Networking
## 4 Proposed Algorithms
### Inter-Layer Information Transfer (IIT)-DOWN Algorithm  
As shown in Figure 2, the main idea of the IIT-DOWN algorithm is as follows. After choosing the HMs from a certain layer network, IIT-DOWN passes the chosen HMs' location information to the lower-level layer and removes the nodes in these locations. The details of this algorithm are as follows: We carry out HEA partitioning from a high latency level to a low latency level. First, we deal with the highest-level layer. All nodes are painted white in \(G\), which means that these nodes are not members of any HEAs yet. Then, the edges with a latency higher than \(t_{i}\), the latency upper bound of this level, are removed. On the other hand, we add an edge between node \(u\) and node \(v\) with \(w(u,\ v)=d(u,v)\), if \(d(u,v)<t_{i}\) holds. Then, we calculate the current layer's HMs with the minimum number and add these nodes to the global HM set, marked as \(S_{HM}\), and all nodes in \(S_{HM}\) are painted black. For every node in white, we find its closest HM from \(S_{HM}\), and make this node a member of the corresponding HEA. The nodes contained in the HEA are marked as H. Then, we undertake lower-level HEA partitioning for every partitioned higher-level HEA. In a lower-level layer, we remove and add edges with the same principle. Then, we remove the nodes that are chosen as HMs in the level higher than the current level and paint their neighboring nodes grey. By now, the current layer's HMs can be calculated using algorithm 3. 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 1.  
```
Input:\(G(V,E,W)\), \(D\) Output:\(S_{HM}\), \(H\)s Parameters:\(T=[t_{1},t_{2},\dots,t_{L}]\)
1: Initialization: \(H^{L+1}=[V]\), \(HM^{L+1}=\varnothing\)
2:for\(i\) from \(L\) to \(1\) do
3: for each \(h\) in \(H^{i+1}\) do
4: generate \(G^{i}(V^{i},E^{i},W^{i})\) where \(V^{i}=h\), \(E^{i}=\varnothing\), \(W^{i}=\varnothing\)
5: for \(v\) in \(V^{i}\) do
6:\(v.\)color = white
7: if \(v\) in \(HM^{i+1}\) then \(v.\)color = black
8: for each \(u\), \(v\) in \(V^{i}\) that \(u\
eq v\) do
9: if \(d(u,\ v)<t_{i}\) then
10: add \(e(u,\ v)\) to \(E^{i}\) and add \(w(u,\ v)=d(u,\ v)\) to \(W^{i}\)
11: for \(v\) in \(HM^{i+1}\) do
12: for \(u\) in \(V^{i}\) do
13: if \(e(u,\ v)\) in \(E^{i}\) and \(u.\)color = white then \(u.\)color = grey
14: remove \(v\) from \(G^{i}\)
15:\(HM^{i}\) = Choose_HM (\(G^{i}\))
16: for each \(v\) in \(V^{i}\) do
17: if \(v\) in \(HM^{i}\) then \(v.\)color = black
18: if not \(v.\)color = black then
19: find \(k\) with the minimum \(d(v,\ k)\) in \(HM^{i}\) and add \(v\) to \(H^{i}_{k}\)
20: add \(H^{i}_{k}\) to \(H^{i}\)
21: add \(HM^{i}\) to \(S_{HM}\) and add \(H^{i}\) to \(H\)s
22: return \(S_{HM}\), \(H\)s
```  
**Algorithm 1**IIT-DOWN  
Figure 2: An example operation in inter-layer information transfer (IIT)-DOWN. Nodes do not change in different layers, but the connections among them may be different. Nodes in black are chosen for the placement of name-resolution servers. Nodes in white represent those that have not been partitioned. The HMs chosen from level \(i\) are removed in level \(i-1\), and grey nodes represent nodes that satisfy the latency constraint from these HMs. There are four HMs in total in this example.