Рубрики

Как реализовать обратный просмотр DNS-кэша?

Обратный поиск DNS использует IP-адрес в Интернете, чтобы найти доменное имя. Например, если вы наберете 74.125.200.106 в браузере, он автоматически перенаправится на google.in.

Как реализовать обратный DNS Look Up кеш? Ниже приведены операции, необходимые из кеша.
1) Добавьте IP-адрес в URL Mapping в кеше.
2) Найти URL для данного IP-адреса.

Одним из решений является использование хеширования .

В этом посте обсуждается решение на основе Trie . Одним из преимуществ решений на основе Trie является то, что в худшем случае верхняя граница равна O (1) для Trie, для хэширования наилучшая возможная средняя сложность по времени составляет O (1). Кроме того, с помощью Trie мы можем реализовать поиск по префиксу (найти все URL для общего префикса IP-адресов).
Общим недостатком Trie является большой объем памяти, это не является серьезной проблемой, так как размер алфавита здесь составляет всего 11. Десять символов необходимы для цифр от 0 до 9 и один для точки ('.').
Идея состоит в том, чтобы хранить IP-адреса в узлах Trie, а в последнем узле мы храним соответствующее доменное имя. Ниже приводится реализация стиля C в C ++.

// Программа на основе C для реализации обратного поиска DNS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

  
// В правильном IP-адресе есть максимум 11 различных символов
#define CHARS 11

  
// Максимальная длина действительного IP-адреса
#define MAX 50

  
// Полезная функция для поиска индекса потомка для данного символа 'c'

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

  
// Полезная функция для поиска символа для заданного дочернего индекса.

char getCharFromIndex(int i) { return (i== 10)? '.' : ('0' + i); }

  
// Trie Node.

struct trieNode

{

    bool isLeaf;

    char *URL;

    struct trieNode *child[CHARS];

};

  
// Функция для создания нового узла Trie.

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;

}

  
// Этот метод вставляет IP-адрес и соответствующий
// доменное имя в Trie. Последний узел в Trie содержит URL.

void insert(struct trieNode *root, char *ipAdd, char *URL)

{

    // Длина IP-адреса

    int len = strlen(ipAdd);

    struct trieNode *pCrawl = root;

  

    // Обход по длине IP-адреса.

    for (int level=0; level<len; level++)

    {

        // Получить индекс дочернего узла из текущего символа

        // в ipAdd []. Индекс должен быть от 0 до 10, где

        // от 0 до 9 используется для цифр и 10 для точки

        int index = getIndex(ipAdd[level]);

  

        // Создать нового ребенка, если он еще не существует

        if (!pCrawl->child[index])

            pCrawl->child[index] = newTrieNode();

  

        // перейти к ребенку

        pCrawl = pCrawl->child[index];

    }

  

    // Ниже необходимо выполнить последний узел.

    // Сохраняем соответствующий URL-адрес IP-адреса в

    // последний узел дерева.

    pCrawl->isLeaf = true;

    pCrawl->URL = new char[strlen(URL) + 1];

    strcpy(pCrawl->URL, URL);

}

  
// Эта функция возвращает URL, если данный IP-адрес присутствует в кеше DNS.
// иначе возвращает NULL

char  *searchDNSCache(struct trieNode *root, char *ipAdd)

{

    // Корневой узел дерева.

    struct trieNode *pCrawl = root;

    int  len = strlen(ipAdd);

  

    // Обход по длине IP-адреса.

    for (int level=0; level<len; level++)

    {

        int index = getIndex(ipAdd[level]);

        if (!pCrawl->child[index])

            return NULL;

        pCrawl = pCrawl->child[index];

    }

  

    // Если мы найдем последний узел для данного ip-адреса, напечатаем URL.

    if (pCrawl!=NULL && pCrawl->isLeaf)

        return pCrawl->URL;

  

    return NULL;

}

  
// Функция драйвера.

int main()

{

    / * Изменить третий IP-адрес для проверки * /

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

  

    // Вставляет все IP-адреса и их соответствующие

    // доменное имя после проверки IP-адреса.

    for (int i=0; i<n; i++)

        insert(root,ipAdd[i],URL[i]);

  

    // Если обратный поиск DNS успешен, выведите домен

    // имя вместе с DNS разрешено.

    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

Выход:

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

Обратите внимание, что приведенная выше реализация Trie предполагает, что данный IP-адрес не содержит символов, отличных от {'0', '1',… .. '9', '.'}. Что если пользователь дает неверный IP-адрес, содержащий некоторые другие символы? Эта проблема может быть решена путем проверки входного IP-адреса перед его вставкой в Trie. Мы можем использовать подход, рассмотренный здесь, для проверки IP-адреса.

Реализация Java приведена ниже:

/ * http://www.geeksforgeeks.org/implement-reverse-dns-look-cache/amp/ * /

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;

    }

}

  
// Этот код предоставлен Akhilesh Singla

Выход:

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

Эта статья предоставлена Кумар Гаутам . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Как реализовать обратный просмотр DNS-кэша?

0.00 (0%) 0 votes