¿Cómo implementar la caché de búsqueda de DNS inversa?

La búsqueda inversa de DNS utiliza una dirección IP de Internet para encontrar un nombre de dominio. Por ejemplo, si escribe 74.125.200.106 en el navegador, se redirige automáticamente a google.in. 
¿Cómo implementar el caché de búsqueda inversa de DNS? Las siguientes son las operaciones necesarias desde el caché:

• Agregue una dirección IP a la asignación de URL en caché.
• Encuentra la URL para una dirección IP determinada.

Una solución es usar Hashing . 
En esta publicación, se analiza una solución basada en Trie . Una ventaja de las soluciones basadas en Trie es que el límite superior del caso más desfavorable es O(1) para Trie; para el hashing, la mejor complejidad de tiempo de caso promedio posible es O(1). Además, con Trie podemos implementar la búsqueda de prefijos (encontrar todas las URL para un prefijo común de direcciones IP). 
La desventaja general de Trie es la gran cantidad de requisitos de memoria, esto no es un problema importante aquí ya que el tamaño del alfabeto es solo 11 aquí. Se necesitan diez caracteres para los dígitos del ‘0’ al ‘9’ y uno para el punto (‘.’). 
La idea es almacenar direcciones IP en Nodes Trie y en el último Node almacenamos el nombre de dominio correspondiente. A continuación se muestra la implementación del estilo C en C++.
 

// C based program to implement reverse DNS lookup
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
// There are atmost 11 different chars in a valid IP address
#define CHARS 11
 
// Maximum length of a valid IP address
#define MAX 50
 
// A utility function to find index of child for a given character 'c'
int getIndex(char c) { return (c == '.')? 10: (c - '0'); }
 
// A utility function to find character for a given child index.
char getCharFromIndex(int i) { return (i== 10)? '.' : ('0' + i); }
 
// Trie Node.
struct trieNode
{
    bool isLeaf;
    char *URL;
    struct trieNode *child[CHARS];
};
 
// Function to create a new trie node.
struct trieNode *newTrieNode(void)
{
    struct trieNode *newNode = new trieNode;
    newNode->isLeaf = false;
    newNode->URL = NULL;
    for (int i=0; i<CHARS; i++)
        newNode->child[i] = NULL;
    return newNode;
}
 
// This method inserts an ip address and the corresponding
// domain name in the trie. The last node in Trie contains the URL.
void insert(struct trieNode *root, char *ipAdd, char *URL)
{
    // Length of the ip address
    int len = strlen(ipAdd);
    struct trieNode *pCrawl = root;
 
    // Traversing over the length of the ip address.
    for (int level=0; level<len; level++)
    {
        // Get index of child node from current character
        // in ipAdd[].  Index must be from 0 to 10 where
        // 0 to 9 is used for digits and 10 for dot
        int index = getIndex(ipAdd[level]);
 
        // Create a new child if not exist already
        if (!pCrawl->child[index])
            pCrawl->child[index] = newTrieNode();
 
        // Move to the child
        pCrawl = pCrawl->child[index];
    }
 
    //Below needs to be carried out for the last node.
    //Save the corresponding URL of the ip address in the
    //last node of trie.
    pCrawl->isLeaf = true;
    pCrawl->URL = new char[strlen(URL) + 1];
    strcpy(pCrawl->URL, URL);
}
 
// This function returns URL if given IP address is present in DNS cache.
// Else returns NULL
char  *searchDNSCache(struct trieNode *root, char *ipAdd)
{
    // Root node of trie.
    struct trieNode *pCrawl = root;
    int  len = strlen(ipAdd);
 
    // Traversal over the length of ip address.
    for (int level=0; level<len; level++)
    {
        int index = getIndex(ipAdd[level]);
        if (!pCrawl->child[index])
            return NULL;
        pCrawl = pCrawl->child[index];
    }
 
    // If we find the last node for a given ip address, print the URL.
    if (pCrawl!=NULL && pCrawl->isLeaf)
        return pCrawl->URL;
 
    return NULL;
}
 
//Driver function.
int main()
{
    /* Change third ipAddress for validation */
    char ipAdd[][MAX] = {"107.108.11.123", "107.109.123.255",
                         "74.125.200.106"};
    char URL[][50] = {"www.samsung.com", "www.samsung.net",
                      "www.google.in"};
    int n = sizeof(ipAdd)/sizeof(ipAdd[0]);
    struct trieNode *root = newTrieNode();
 
    // Inserts all the ip address and their corresponding
    // domain name after ip address validation.
    for (int i=0; i<n; i++)
        insert(root,ipAdd[i],URL[i]);
 
    // If reverse DNS look up succeeds print the domain
    // name along with DNS resolved.
    char ip[] = "107.108.11.123";
    char *res_url = searchDNSCache(root, ip);
    if (res_url != NULL)
        printf("Reverse DNS look up resolved in cache:\n%s --> %s",
                ip, res_url);
    else
        printf("Reverse DNS look up not resolved in cache ");
    return 0;
}

Reverse DNS look up resolved in cache:
107.108.11.123 --> www.samsung.com

Producción: 

Reverse DNS look up resolved in cache:
107.108.11.123 --> www.samsung.com

Tenga en cuenta que la implementación anterior de Trie asume que la dirección IP dada no contiene caracteres que no sean {‘0’, ‘1’,….. ‘9’, ‘.’}. ¿Qué sucede si un usuario proporciona una dirección IP no válida que contiene otros caracteres? Este problema se puede resolver validando la dirección IP de entrada antes de insertarla en Trie. Podemos usar el enfoque discutido aquí para la validación de direcciones IP.
La implementación de Java se da a continuación: 
 

/* https://www.geeksforgeeks.org/implement-reverse-dns-look-cache/ */
import java.util.HashMap;
import java.util.Map;
 
public class ReverseDNSLookup
{
    public void insert(TrieNode node, String[] ipAdd, String[] urls)
    {
        for(int i=0;i<ipAdd.length;i++)
            this.insertUtil(node, ipAdd[i], urls[i], 0);
    }
 
    public void insertUtil(TrieNode node, String ipAddr, String url, int pos)
    {
        TrieNode temp = null;
        if(node.child.containsKey(ipAddr.charAt(pos)))
        {
            temp = node.child.get(ipAddr.charAt(pos));
        }
        else
        {
            temp = new TrieNode();
            node.child.put(ipAddr.charAt(pos), temp);
        }
        if(pos==ipAddr.length()-1)
        {
            temp.url = url;
            return;
        }
        this.insertUtil(temp, ipAddr, url, pos+1);
    }
 
    public String search(TrieNode node, String ipAddr, int pos)
    {
        TrieNode temp = null;
        if(pos==ipAddr.length()-1)   
        {
            temp = node.child.get(ipAddr.charAt(pos));
            if(temp!=null)
                return temp.url;
        }
        if(node.child.containsKey(ipAddr.charAt(pos)))
        {   
            temp = node.child.get(ipAddr.charAt(pos));
            return this.search(temp, ipAddr, pos+1);       
        }
        return "No url associated/Invalid IP address";
    }
 
    public static void main(String []args)
    {
        ReverseDNSLookup r = new ReverseDNSLookup();
        String[] ipAdd = {"107.108.11.123",
                                  "107.109.123.255", "74.125.200.106"};
        String[] urls = {"www.samsung.com",
                         "www.samsung.net", "www.google.in"};
 
        TrieNode root = new TrieNode();
        r.insert(root, ipAdd, urls);
        //System.out.println(root);
        System.out.println("74.125.200.106 : "+
                                r.search(root, "74.125.200.106", 0));
        System.out.println("107.109.123.245 : "+
                                r.search(root, "107.109.123.245", 0));
    }
}
 
class TrieNode
{
    Map<Character, TrieNode> child;
    String url;
 
    TrieNode()
    {
        this.child = new HashMap<>();
    }
 
    public String toString()
    {
        return child.toString()+" : "+url;
    }
}
 
// This code is contributed by Akhilesh Singla

<script>
 
class TrieNode
{
    constructor()
    {
        this.child = new Map();
    }
    toString()
    {
        return this.child.toString()+" : "+url;
    }
}
 
function insert(node,ipAdd,urls)
{
    for(let i = 0; i < ipAdd.length; i++)
            this.insertUtil(node, ipAdd[i], urls[i], 0);
}
 
function insertUtil(node, ipAddr,url,pos)
{
    let temp = null;
        if(node.child.has(ipAddr[pos]))
        {
            temp = node.child.get(ipAddr[pos]);
        }
        else
        {
            temp = new TrieNode();
            node.child.set(ipAddr[pos], temp);
        }
        if(pos==ipAddr.length-1)
        {
            temp.url = url;
            return;
        }
        this.insertUtil(temp, ipAddr, url, pos+1);
}
 
function search(node,ipAddr, pos)
{
    let temp = null;
        if(pos==ipAddr.length-1)  
        {
            temp = node.child.get(ipAddr[pos]);
            if(temp!=null)
                return temp.url;
        }
        if(node.child.has(ipAddr[pos]))
        {  
            temp = node.child.get(ipAddr[pos]);
            return this.search(temp, ipAddr, pos+1);      
        }
        return "No url associated/Invalid IP address";
}
 
let ipAdd = ["107.108.11.123","107.109.123.255", "74.125.200.106"];
let urls = ["www.samsung.com",
                 "www.samsung.net", "www.google.in"];
 
let root = new TrieNode();
insert(root, ipAdd, urls);
//System.out.println(root);
document.write("74.125.200.106 : "+
                   search(root, "74.125.200.106", 0)+"<br>");
document.write("107.109.123.245 : "+
                   search(root, "107.109.123.245", 0)+"<br>");
 
// This code is contributed by patel2127
</script>

74.125.200.106 : www.google.in
107.109.123.245 : No url associated/Invalid IP address

Implementación de Python3: 
 

# Trie Node
class TrieNode:
    def __init__(self):
        self.child = [None] * 11
        self.url = None
        self.is_end = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
     
    def getIndex(self, c):
        # For the . (dot) in IP address, we'll use the 10th index in child list
        return 10 if c == '.' else int(c)
     
    def insert(self, ip, domain):
        cur = self.root
        n = len(ip)
         
        for level in range(n):
            # We'll use the digits of IP address to form the trie structure
            idx = self.getIndex(ip[level])
             
            if cur.child[idx] is None:
                # Create a new trie node if not available for a particular digit
                # and assign to the respective index
                cur.child[idx] = TrieNode()
                 
            cur = cur.child[idx]
         
        # At the end, we'll map the domain name and mark the end node
        cur.url = domain
        cur.is_end = True
     
    def search_domain(self, ip):
        cur = self.root
        n = len(ip)
         
        # Traverse through the trie structure with all digits in ip address
        for level in range(n):
            idx = self.getIndex(ip[level])
            if cur.child[idx] is None:
                return "Domain name not found"
             
            cur = cur.child[idx]
         
        # Returns the url when all the digits in ip found
        if cur and cur.url:
            return cur.url
         
        return "Domain name not found"
 
# Driver Code
ip = ["107.108.11.123", "107.109.123.255", "74.125.200.106"]
domain = ["www.samsung.com", "www.samsung.net", "www.google.co.in"]
 
trie = Trie()
for idx in range(len(ip)):
    trie.insert(ip[idx], domain[idx])
 
print(trie.search_domain("107.109.123.255"))
print(trie.search_domain("107.109.123.245"))
 
# This code is contributed by Abhilash Pujari

www.samsung.net
Domain name not found

Este artículo es una contribución de Kumar Gautam . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.