Рубрики

Как реализовать кэш прямого просмотра DNS?

Мы обсудили реализацию обратного DNS Look Up Cache . Forward DNS lookup получает IP-адрес для данного доменного имени, набранного в веб-браузере.

Кеш должен выполнять следующие операции:
1. Добавьте сопоставление с URL на IP-адрес
2. Найти IP-адрес для данного URL.

Есть несколько изменений по сравнению с кэшем обратного просмотра DNS, который мы должны включить.
1. Вместо точек [0-9] и (.) Нам нужно позаботиться о точках [AZ], [az] и (.). Поскольку большая часть доменного имени содержит только строчные символы, мы можем предположить, что для каждого узла trie будет [az] и (.) 27 дочерних элементов.

2. Когда мы набираем www.google.in и google.in, браузер выводит нас на ту же страницу. Итак, нам нужно добавить доменное имя в trie для слов после www (.). Аналогично, при поиске доменного имени соответствующего IP-адреса удалите www (.), Если пользователь его предоставил.

Это оставлено как упражнение, и для простоты мы позаботились о www. также.

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

Ниже приводится реализация стиля C в C ++.

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

  
// В допустимом URL есть максимум 27 различных символов
// при условии, что URL состоит из [az] и (.)
#define CHARS 27

  
// Максимальная длина действительного URL
#define MAX 100

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

int getIndex(char c)

{

    return (c == '.') ? 26 : (c - 'a');

}

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

char getCharFromIndex(int i)

{

    return (i == 26) ? '.' : ('a' + i);

}

  
// Trie Node.

struct trieNode

{

    bool isLeaf;

    char *ipAdd;

    struct trieNode *child[CHARS];

};

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

struct trieNode *newTrieNode(void)

{

    struct trieNode *newNode = new trieNode;

    newNode->isLeaf = false;

    newNode->ipAdd = NULL;

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

        newNode->child[i] = NULL;

    return newNode;

}

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

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

{

    // Длина URL

    int len = strlen(URL);

    struct trieNode *pCrawl = root;

  

    // Обход по длине URL.

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

    {

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

        // в URL [] индекс должен быть от 0 до 26, где

        // от 0 до 25 используется для алфавитов и 26 для точки

        int index = getIndex(URL[level]);

  

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

        if (!pCrawl->child[index])

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

  

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

        pCrawl = pCrawl->child[index];

    }

  

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

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

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

    pCrawl->isLeaf = true;

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

    strcpy(pCrawl->ipAdd, ipAdd);

}

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

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

{

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

    struct trieNode *pCrawl = root;

    int  len = strlen(URL);

  

    // Обход по длине URL.

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

    {

        int index = getIndex(URL[level]);

        if (!pCrawl->child[index])

            return NULL;

        pCrawl = pCrawl->child[index];

    }

  

    // Если мы найдем последний узел для данного IP-адреса,

    // распечатать IP-адрес.

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

        return pCrawl->ipAdd;

  

    return NULL;

}

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

int main()

{

    char URL[][50] = { "www.samsung.com", "www.samsung.net",

                       "www.google.in"

                     };

    char ipAdd[][MAX] = { "107.108.11.123", "107.109.123.255",

                          "74.125.200.106"

                        };

    int n = sizeof(URL) / sizeof(URL[0]);

    struct trieNode *root = newTrieNode();

  

    // Вставляем все доменные имена и соответствующие им

    // айпи адрес

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

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

  

    // Если поиск в DNS успешно завершен, выведите URL-адрес

    // с разрешенным IP-адресом.

    char url[] = "www.samsung.com";

    char *res_ip = searchDNSCache(root, url);

    if (res_ip != NULL)

        printf("Forward DNS look up resolved in cache:\n%s --> %s",

               url, res_ip);

    else

        printf("Forward DNS look up not resolved in cache ");

  

    return 0;

}

Выход:

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

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

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

Как реализовать кэш прямого просмотра DNS?

0.00 (0%) 0 votes