Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
DNS and DNS caching 
3.
How to Implement Forward DNS Look Up Cache?
4.
Approach:
5.
 
6.
Explanation of some of the important functions:
6.1.
Creating a Trie and adding new nodes to it.
6.2.
Insert the URLs and their corresponding IP addresses
6.3.
 
6.4.
 
6.5.
 
6.6.
 
6.7.
 
6.8.
 
6.9.
 
6.10.
Search for a URL in the DNS cache and return its IP address
7.
C++ implementation for Forward DNS Look Up Cache
8.
OUTPUT
9.
Complexities
9.1.
Time Complexity
9.2.
Space Complexity
10.
Frequently Asked Questions
11.
Key Takeaways
Last Updated: Mar 27, 2024

Implement Forward DNS Look Up Cache

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:

  1. Map the URLs to their IP addresses.
  2. Find and display the IP address of the inputted URL. 

 

Now, how to achieve the above two tasks? Let's find out.

  1. 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 (.).
  2. 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. 

struct Trie
{
    bool isLeaf;
    char* ipAdd;
    struct Trie *child[CHARS];
};

 

 

 

 

 

 

 

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;
}

 

 

 

 

 

 

 

 

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);
}

 

 

 

 

 

 

 

 

 

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;
}

 

 

C++ implementation for Forward DNS Look Up Cache

The below-mentioned code is a C-based program on how to implement forward DNS look up cache. 

In the code, three dummy URLs and their IP addresses have been hard-coded for making our DNS cache.

 

// C based C++ program on how to implement forward DNS look up cache
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define CHARS 27

#define MAX 100

int getIndex(char c)
{
    return (c == '.') ? 26 : (c - 'a');
}

char getCharFromIndex(int i)
{
    return (i == 26) ? '.' : ('a' + i);
}
  
struct Trie
{
    bool isLeaf;
    char* ipAdd;
    struct Trie *child[CHARS];
};

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;
}

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);
}

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;
}

int main()
{
    char URL[][50] = { "www.google.com", "www.facebook.com",
                      "www.youtube.com", "www.yahoo.com"};
    char ipAdd[][MAX] = { "172.217.166.68", "157.240.218.35",
                          "78.155.223.109", "150.99.125.46"};
    int n = sizeof(URL) / sizeof(URL[0]);
    struct Trie* root = newNode();
  

    for (int i = 0; i<n; i++)
        insert(root, URL[i], ipAdd[i]);
        
    char url1[] = "www.facebook.com"; 
    char *res_ip1 = searchDNSCache(root, url1);
    printf(" Performing Forward look up in the DNS cache ...\n");
    if (res_ip1 != NULL)
        printf(" Forward DNS cache look up Successful ! \n Hostname: %s --> IP address: %s", url1, res_ip1);
    else
        printf("Forward DNS cache look up Unsuccessful ! Hostname not present in DNS cache");
  
   printf("\n\n");

char url2[] = "www.gmail.com"; 
    char *res_ip2 = searchDNSCache(root, url2);
    printf(" Performing Forward look up in the DNS cache ...\n");
    if (res_ip2 != NULL)
        printf(" Forward DNS cache look up Successful ! \n Hostname: %s --> IP address: %s", url2, res_ip2);
    else
        printf(" Forward DNS cache look up Unsuccessful ! Hostname not present in DNS cache.");

    return 0;
}

 

 

OUTPUT

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

Check out this problem - Reverse Nodes In K Group

Frequently Asked Questions

Q1.) How does DNS caching affect the network?

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.

 

Confident enough about tries? Click here Implement Trie to go to our Coding Ninjas Studio and test out your knowledge.

 

 Want to learn more about various Data Structures and Algorithms and which language to choose? Go to How to Get Better at DSA For Beginners? to know more.

 

Previous article
Longest word in dictionary
Next article
Implement Reverse DNS Look Up Cache
Live masterclass