I am sure many of you must have heard of the term IP address and wonder what it is? It is a set of numbers separated by dots in a specific format that helps you connect to a website. IP address stands for Internet Protocol address. When we type an IP address in our browser and press enter, we go to the corresponding website. For example, if we type 74.125.200.106 in our browser and hit enter, we will be automatically taken to google.in. This is no magic at all; in fact, we are simply searching for our IP in the DNS cache and returning the corresponding URL. This technique where we enter an IP address and get the URL is known as Reverse DNS look up.
Now you might wonder what the term DNS cache means. It is a sort of storage where the IP addresses of various domains and their URLs are stored so that we can search for an IP address and get the URL.
This article covers the topic of how to Implement Reverse DNS Look Up Cache; if you want, you can check how to Implement Forward DNS Look Up Cache here
How to Implement Reverse DNS Look Up Cache?
In this article, we are going to discuss how to implement Reverse DNS Look Up Cache. As explained earlier, the process of searching for a URL by inputting an IP address is known as Reverse DNS Look Up. Similar to what we did in the Forward DNS Look Up blog, we will store the IP addresses and their corresponding URLs in Tries. In our code, we store the URLs at the leaf nodes of corresponding IP addresses; thus, to get a URL, we simply traverse the Trie and search for the IP address and return the URL if it is present.
Either Hashmaps or Tries can do the task of storing the IP addresses and URLs. 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 Reverse DNS look up cache.
Approach
According to our problem, we have to perform two primary operations:
Create a DNS cache by storing the IP addresses along with their URLs.
Try to get the URL of a site by entering and searching the IP address.
Generally, an IP address consists of numbers [0 to 9] separated by dots. This makes things easier because the nodes of our Trie will consist of a combination of 11 characters only - [0 to 9] and dot (‘.’). The approach in this article creates a Trie that stores the IP addresses as nodes and their corresponding URLs as the leaf node. So without any further ado, let’s hop into our solution of how to implement Reverse DNS Look Up cache.
Explanation of some of the important functions:
Creating the Trie and adding new nodes.
We create a struct named ‘trieNode’ which will be our Trie for DNS cache.
Inserting the IP addresses and their URLs in our DNS cache.
This function takes the root node, the char array of IP addresses, and the char array of URLs as function arguments. The main use of this function is to insert an IP address and the corresponding URL in the Trie. The last node in the Trie contains the URL.
void insert(struct Trie* root, char *ipAdd, char *URL)
{
int len = strlen(ipAdd);
struct Trie* pCrawl = root;
for (int level=0; level<len; level++)
{
int index = getIndex(ipAdd[level]);
if (!pCrawl->child[index])
pCrawl->child[index] = newNode();
pCrawl = pCrawl->child[index];
}
pCrawl->isLeaf = true;
pCrawl->URL = new char[strlen(URL) + 1];
strcpy(pCrawl->URL, URL);
}
You can also try this code with Online C++ Compiler
Searching for a specific IP address in our DNS cache and returning the URL.
This function takes the root node and the IP address that has to be found in the DNS cache as function arguments. It returns the URL of that IP address; thus, it has the return type as char. We perform a simple search operation in our Trie to find the given IP address in our DNS cache. If found, we return the corresponding URL; else, we return NULL. The below-mentioned code snippet shows the searchDNSCache() function.
char* searchDNSCache(struct Trie* root, char *ipAdd)
{
struct Trie* pCrawl = root;
int len = strlen(ipAdd);
for (int level=0; level<len; level++)
{
int index = getIndex(ipAdd[level]);
if (!pCrawl->child[index])
return NULL;
pCrawl = pCrawl->child[index];
}
if (pCrawl!=NULL && pCrawl->isLeaf)
return pCrawl->URL;
return NULL;
}
You can also try this code with Online C++ Compiler
In the above code, we search for two IP addresses in our DNS cache. The one which exists gave us the proper URL corresponding to that IP address. The other IP address, which was not present in our DNS cache, gave an appropriate error message.
Performing Reverse look up in the DNS cache ... Reverse DNS look up cache Successful ! IP address: 157.240.218.35 --> Hostname: www.facebook.com
Performing Reverse look up in the DNS cache ... Reverse DNS look up cache unsuccessful ! IP address not present in DNS cache
Complexities
Time Complexity
In the above implementation, we use Tries to store the IP addresses and their corresponding URLs. To do so we traverse the whole IP address once. Thus time complexity is:
T(n) = O(n),
where n is the length of the IP address 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.) When we search for a URL by typing its IP address or vice-versa in a DNS cache, it is known as DNS look up cache. It is of two types - Forward look up and Reverse look up. This article is primarily concerned with how to Implement Reverse DNS Look Up Cache.
Key Takeaways
This article covers many aspects related to DNS caching. To summarize, we have learned about DNS caching in brief and how to Implement Reverse DNS Look Up Cache with the help of suitable explanations and code snippets.
117+ registered 