Do you think IIT Guwahati certified course can help you in your career?
Introduction
When we type a web address or URL (Uniform Resource Locator) into a web browser, like “www.google.com” our computer needs to turn that URL into an IP (Internet Protocol) address so that it can communicate with that web server and deliver the web page to you. This is called a Forward Look Up because we are turning a hostname into an IP address. There’s also a concept of Reverse Look Up, which does the opposite: take in an IP address and turn it into a hostname. This article covers only Forward DNS Look Up; if you want, you can check the Reverse DNS Look Up here
DNS and DNS caching
Managed Services Providers or MSPs frequently come across the term Domain Name System or DNS. It is a distributed server network that acts as a directory by cataloging domain names and their corresponding Internet Protocol or IP addresses. A DNS cache can be considered local storage containing records of a computer's query history, including recent website visits.
The primary work of a DNS is to translate the human-understandable verbal nomenclature into numerical naming and transmissions that are understandable by computers/machines. With the help of DNS caching, we can do this task. DNS caching expedites the DNS lookup process to resolve a domain name more quickly to an IP address when the OS has visited a web page before.
This article will walk through the topic of how to implement Forward DNS Look Up Cache. Adequate explanations and examples have been provided in this article for the ease of every reader.
How to Implement Forward DNS Look Up Cache?
In this article, we’ll talk about how to Implement Forward DNS Look Up Cache. As explained earlier, the process of searching an IP address by using a URL is known as Forward DNS Look Up. We have done so by storing the various URLs along with their corresponding IP addresses in Tries. Since the IP addresses are at the leaf node, we simply traverse the trie, find the URL and return the corresponding IP address.
Either Hashmaps or Tries can do the task of storing the URLs and IP addresses. The solution in this article is done using Tries because the worst-case upper bound for a Trie is O(1),while for hashmaps,the best possible average case complexity is O(1). The only drawback of Tries is the space complexity as it takes up a considerable amount of space.
Prerequisite: The implementation in this article is done with the help of Tries Data Structure. It is highly recommended to study Tries before proceeding. You can do so by reading this highly informative blog: Using Trie in Data Structures.
Hopefully, you are now well-versed with Tries; if not, please go through the recommended blog once more. Let’s now proceed to the main topic - how to implement Forward DNS look up cache.
Approach:
According to our problem, we have to perform the following two major actions:
Map the URLs to their IP addresses.
Find and display the IP address of the inputted URL.
Now, how to achieve the above two tasks? Let's find out.
Since every URL consists of lowercase alphabets and a dot separator, we assume that there can be a maximum of 27 children for each trie node, which are - 26 alphabets [a to z] and a dot (.).
While entering a URL, even if we skip the “www.” part, we can successfully go to that site. For example, “www.google.com” and “google.com” will take us to the same web page without any error. Handling the “www.” part is a bit complicated, so for simplicity, the implementation given in this article stores the URLs along with the “www.” part.
The main idea is to store the URLs in Trie nodes and the corresponding IP addresses in the last or leaf node.
Explanation of some of the important functions:
Creating a Trie and adding new nodes to it.
We define a struct named ‘trieNode’ which will be our main Trie.
For adding a new node to our Trie, we first change a current leaf node to a normal node and then add a new node. This is shown in the following code snippet.
struct Trie* newNode(void)
{
struct Trie* newNode = new Trie;
newNode->isLeaf = false;
newNode->ipAdd = NULL;
for (int i = 0; i<CHARS; i++)
newNode->child[i] = NULL;
return newNode;
}
You can also try this code with Online C++ Compiler
Insert the URLs and their corresponding IP addresses
In order to insert the URLs and their IP addresses into the trie, we call the insert() function. It takes the root node pointer, the char array of URLs, and the char array of IP addresses as function arguments. It performs a regular trie insertion where each URL is connected to the root node, and the leaf nodes of each URL contain their respective IP address. Since we don’t have to return any value, we keep the return type as void. The following code snippet shows how to do so.
void insert(struct Trie* root, char* URL, char* ipAdd)
{
int len = strlen(URL);
struct Trie* pCrawl = root;
for (int level = 0; level<len; level++)
{
int index = getIndex(URL[level]);
if (!pCrawl->child[index])
pCrawl->child[index] = newNode();
pCrawl = pCrawl->child[index];
}
pCrawl->isLeaf = true;
pCrawl->ipAdd = new char[strlen(ipAdd) + 1];
strcpy(pCrawl->ipAdd, ipAdd);
}
You can also try this code with Online C++ Compiler
Search for a URL in the DNS cache and return its IP address
For searching a URL in our DNS cache, we call the searchDNSCache() function. This function takes the root node pointer, and the URL to be searched as the arguments and returns the node containing the IP address. We perform a normal search in our Trie to find the required URL. If the URL is present in our DNS cache, then we return the IP address; else, we return NULL.
char* searchDNSCache(struct Trie* root, char* URL)
{
struct Trie* pCrawl = root;
int len = strlen(URL);
for (int level = 0; level<len; level++)
{
int index = getIndex(URL[level]);
if (!pCrawl->child[index])
return NULL;
pCrawl = pCrawl->child[index];
}
if (pCrawl != NULL && pCrawl->isLeaf)
return pCrawl->ipAdd;
return NULL;
}
You can also try this code with Online C++ Compiler
In the above code, we have searched for “www.facebook.com” and “www.gmail.com”. One of them is present in our DNS cache, and the other is not. Thus the first test case gives a successful DNS cache search and displays the IP address, while the second test case returns NULL from the searchDNSCache() and shows the appropriate failure message.
Performing Forward look up in the DNS cache ... Forward DNS cache look up Successful ! Hostname: www.facebook.com --> IP address: 157.240.218.35
Performing Forward look up in the DNS cache ... Forward DNS cache look up Unsuccessful ! Hostname not present in DNS cache.
Complexities
Time Complexity
In the above implementation, we use Tries to store the URLs and their corresponding IP addresses. To do so we traverse the whole URL once. Thus time complexity is:
T(n) = O(n),
where n is the length of the URL to be inserted.
Space Complexity
In the above implementation, we store all the IP addresses and their corresponding URLs in Tries. Thus,
Space complexity = O(RN),
where R is the number of entries and N is the number of characters
Ans.) The DNS cache helps streamline the DNS lookup process; it helps resolve a domain name linking to an IP address in a few seconds. But DNS caching is risky as it can compromise network security and web page access if not appropriately handled. Thus the MSPs must understand the dangers of caching and know how to resolve them.
Q2.) What is a Trie?
Ans.) A trie is a data structure that root node which is the starting point. All the data is stored in the form of nodes. Each data has an endpoint that marks the end of a particular data. Due to this concept, Tries can handle overlapping data easily. To know more about tries, do read Using Trie in Data Structures.
Key Takeaways
This article covers many aspects related to DNS caching. We first learn the meaning and use of DNS caching, the types of DNS loop up cache methods, how to implement forward DNS look up cache using trie data structure along with a fully explained code.
134+ registered 
