# Data Structure and Management Protocol to Enhance Name Resolving in Named Data Networking
## 3 Proposed Solution
### Proposed Encoded Component Hash Trie (ECHT) Data Structure
#### 3.1.2 ECHT Operations  
Three different operations are supported by the ECHT data structure: (1) insertion, (2) deletion, and (3) lookup. Hereafter, we refer to the NDN name of the producer's domain as entry_key and to the producer's corresponding delivery locations as entry_value. The following subsections discuss the ECHT operations. * **ECHT Insertion and Deletion Operations**  
When an ADD Interest is received via our proposed protocol PNPP, which will be covered in the next section, the new name will be added to the mapping table as in the following steps. The name and the location are extracted and represented in the form of entry key value, where the key is the TLV encoded name in byte format as received from the Interest, and the value is a list of encoded delivery locations. After that, each key and its value are passed to ECHT for processing. The insertion process starts by dividing the key into multiple components, e.g., /om/edu/squ is divided into three components: om, edu, and squ. The first component (e.g., om) is checked against the trie's nodes, starting from the root node. If the component is not found in the trie, it will be added as a new node in the first level with an empty value. This newly created node becomes the root node for the next component, and so on. Once the last component is reached, it will be added with its corresponding past value -if exists-. Each parent node has its own children's keys stored in a hash to speed up the look-up process between keys sharing the same parent. Upon process completion, the corresponding entry_value is returned to the caller. As for the deletion process, the received entry_key is divided into components, the same as in the insert process. The first component is checked against the trie's nodes, starting from the root node. Once the last component is reached, if found, it will be either \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Separate Chaining** &
\begin{tabular}{c} **Open Addressing** \\ **(Linear Probing)** \\ \end{tabular} \\ \hline
**Implementation** & Simple & More computation \\ \hline
**Cache performance** &
\begin{tabular}{c} Worse since keys are stored using a \\ linked list \\ \end{tabular} & Better, since keys are stored in the same table \\ \hline
**Space utilization** & \
\begin{tabular}{c} 1. Waste spaces \\ 2. Extra space for links \\ \end{tabular} &
\begin{tabular}{c} 1. No waste spaces \\ 2. No need for extra spaces \\ \end{tabular} \\ \hline
**Clustering** & \
\begin{tabular}{c} No clustering \\ \end{tabular} &
\begin{tabular}{c} Suffers from clustering \\ \end{tabular} \\ \hline
**Mapping time complexity (worst case)** & \
\begin{tabular}{c} \(O(n)\) \\ \end{tabular} &
\begin{tabular}{c} \(O(n)\) \\ \end{tabular} \\ \hline
**Operations time complexity (worst case)** & \
\begin{tabular}{c} \(O(1+\alpha)\)[19], where \\ \(\alpha=\frac{Number\ of\ keys}{Number\ of\ slots in\ hash\ table}\) \\ \end{tabular} &
\begin{tabular}{c} \(O\left(\frac{1}{1-\alpha}\right)\)[19], where \\ \(\alpha=\frac{Number\ of\ keys}{Number\ of\ slots in\ hash\ table}<1\) \\ \end{tabular} \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Separate chaining vs. open addressing. deleted if it has no children, or the key_value is set to nil if the current node has one child or more to preserve the child nodes. Upon process completion, the corresponding entry_value is returned to the caller. However, it will be nil if all corresponding delivery locations are removed, or the whole node is removed. * **ECHT Lookup Operation**  
ECHT is designed to provide two types of lookups: searching for an exact match and searching for the best component match. In exact match searching, the trie is traversed based on the components of the entry_key. If the last component is found, its value will be returned to the caller; otherwise, nil is returned. Instead of the traditional Longest Prefix Match (LPM) search mechanism, we propose a new search mechanism called Best Component Match (BCM).