Участник:Shovkoplyas Grigory — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Просмотр таблицы маршрутизации)
 
(не показано 46 промежуточных версий 3 участников)
Строка 1: Строка 1:
−
== Идея ==
+
==Определения==
−
Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чём разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше".
 
  
−
== Алгоритм ==
+
{{Определение
−
Пусть <tex> a </tex> {{---}} отсортированный массив из <tex> n </tex> чисел, <tex> x </tex> {{---}} значение, которое нужно найти. Поиск происходит подобно [[Целочисленный двоичный поиск|двоичному поиску]], но вместо деления области поиска на две примерно равные части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Если известно, что <tex> x </tex> лежит между <tex> a_l </tex> и <tex> a_r </tex>, то следующая проверка выполняется примерно на расстоянии <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex> от <tex> l </tex>.
+
|definition =  
 +
Таблица маршрутизации {{---}} таблица, состоящая из сетевых маршрутов и предназначенная для определения наилучшего пути передачи сетевого пакета.
 +
}}
  
−
Формула для разделительного элемента <tex> m </tex> получается из следующего уравнения: <tex dpi = "170"> \frac{x - a_l}{m - l} = \frac{a_r - a_l}{r - l} </tex> {{---}}
+
{{Определение
−
откуда следует, что <tex> m = l + </tex> <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex>. На рисунке внизу показано, из каких соображений берется такая оценка. Интерполяционный поиск основывается на том, что наш массив представляет из себя что-то наподобии арифметической прогрессии.
+
|definition =  
−
[[Файл:interpolation_search_from_gshark.png|450px|center|Размещение разделительного элемента]]
+
Сетевой маршрут {{---}} запись таблицы маршрутизации, содержащая в себе адрес сети назначения (destination), маску сети назначения (netmask), шлюз (gateway), интерфейс (interface) и метрику (metric).
 +
}}
  
−
== Псевдокод ==
+
===Пример таблицы маршрутизации===
−
<code>
+
{| border="1"
−
'''function''' interpolationSearch(a : '''int[]''', key : '''int''') <font color=green> // a должен быть отсортирован </font>
+
|-
−
  left = 0 <font color=green> // левая граница поиска (будем считать, что элементы массива нумеруются с нуля) </font>
+
!Destination||Netmask||Gateway||Interface||Metric
−
  right = a.length - 1 <font color=green> // правая граница поиска </font>
+
|-
−
+
|0.0.0.0||0.0.0.0||192.168.0.1||192.168.0.100||10
−
  '''while''' a[left] <tex> \leqslant </tex> key '''and''' key <tex> \leqslant </tex> a[right]
+
|-
−
    mid = left + (key - a[left]) / (a[right] - a[left]) * (right - left) <font color=green> // индекс элемента, с которым будем проводить сравнение </font>
+
|127.0.0.0||255.0.0.0||127.0.0.1||127.0.0.1||1
−
    '''if''' a[mid] == key
+
|-
−
      '''return''' mid
+
|192.168.0.0||255.255.255.0||192.168.0.100||192.168.0.100||10
−
    '''if''' a[mid] < key
+
|-
−
      left = mid + 1
+
|192.168.0.100||255.255.255.255||127.0.0.1||127.0.0.1||10
−
    '''else'''
+
|-
−
      right = mid - 1
+
|192.168.0.1||255.255.255.255||192.168.0.100||192.168.0.100||10
−
+
|}
−
  '''if''' a[left] == key
 
−
    '''return''' left
 
−
  '''else'''
 
−
    '''return''' -1 <font color=green>// если такого элемента в массиве нет </font>
 
−
</code>
 
  
−
== Время работы ==
 
−
Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный. Если ключи распределены случайным образом, то за один шаг алгоритм уменьшает количество проверяемых элементов с <tex> n </tex> до <tex> \sqrt n </tex>. То есть, после <tex>k</tex>-ого шага количество проверяемых элементов уменьшается до <tex dpi = 170>n^{\frac{1}{2^k}}</tex>. Значит, остаётся проверить только 2 элемента (и закончить на этом поиск), когда <tex dpi = 150>\frac{1}{2^k} = \log_{n}2 = \frac{1}{\log_{2}n} </tex>. Из этого вытекает, что количество шагов, а значит, и время работы составляет <tex>O(\log \log n)</tex>.
 
  
−
При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до <tex> O(n) </tex>.
+
==Описание компонентов==
 +
{{Определение
 +
|definition =
 +
Адрес сети назначения (Destination) {{---}} собственно, адрес конечного узла пути передачи сетевого пакета.
 +
}}
  
−
Эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика). Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями <tex>\log \log n</tex> и <tex>\log n</tex> становится значительной только при очень больших <tex>n</tex>. На практике при поиске в больших файлах оказывается выгодным на ранних стадиях применять интерполяционный поиск, а затем, когда диапазон существенно уменьшится, переходить к двоичному.
+
{{Определение
 +
|definition =
 +
Маска сети назначения (Netmask) {{---}} битовая маска, определяющая, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети.
 +
В двоичной записи всегда выглядит как множество единиц в начале и нулей в конце.
 +
}}
  
−
== Литература ==
+
===Пример получения адреса сети===
−
Д.Э. Кнут: [http://books.google.com/books?id=92rW-nktlbgC&pg=PA452&lpg=PA453&ots=jChsP2sutg&dq=%D0%BA%D0%BD%D1%83%D1%82+%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D1%8F%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9+%D0%BF%D0%BE%D0%B8%D1%81%D0%BA&hl=ru&ie=windows-1251&output=html Искусство программирования (том 3)]
+
{| class="simple" border="1"
 +
|-
 +
! ||Двоичная запись||Десятичная запись
 +
|-
 +
|IP-адрес||<tt>11000000 10101000 00000001 00000010</tt> ||192.168.1.2
 +
|-
 +
|Маска||  <tt>11111111 11111111 11111110 00000000</tt> || 255.255.254.0
 +
|-
 +
|Адрес сети||    <tt>11000000 10101000 00000000 00000000</tt> ||192.168.0.0
 +
|}
  
−
Wikipedia: [http://en.wikipedia.org/wiki/Interpolation_search Interpolation search]
+
Чтобы вычислить адрес сети, нужно применить логическое ''и'' к адресу и маске.
  
−
Wikipedia: [http://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Интерполирующий поиск]
+
{{Определение
 +
|definition =
 +
Шлюз (Gateaway) {{---}} адрес узла в сети, на который необходимо отправить пакет, следующий до указанного адреса назначения. Шлюзы бывают ''по умолчанию'', тогда значения адреса назначения и маски указываются как 0.0.0.0.
 +
}}
  
−
[[Категория: Дискретная математика и алгоритмы]]
+
{{Определение
−
[[Категория: Алгоритмы поиска]]
+
|definition =
 +
Интерфейс (Interface) указывает, какой локальный интерфейс отвечает за достижение шлюза. Например, шлюз 192.168.0.1 (интернет-маршрутизатор) может быть достижим через локальную сетевую карту, адрес которой 192.168.0.100.
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
Метрика (Metric) {{---}} числовой показатель, задающий предпочтительность маршрута. Чем меньше число, тем более предпочтителен маршрут. Интуитивно представляется как расстояние (необязательный параметр).
 +
}}
 +
 
 +
==Принцип действия==
 +
При отправке сетевого пакета, операционная система смотрит, по какому именно маршруту он должен быть отправлен, основываясь на таблице маршрутизации.
 +
Как правило, выбирается наиболее конкретный (т.е. с наиболее длинной сетевой маской) маршрут из тех, которые соответствуют адресу отправителя и имеют наименьшую метрику.
 +
Если ни один из маршрутов не подходит, пакет уничтожается, а его отправителю возвращается ICMP-сообщение ''No route to host''.
 +
 
 +
Внутри каждого пакета есть поле TTL (Time to live) при каждой пересылке значение уменьшается на единицу, и если оно становится нулем, то пакет выбрасывается.
 +
ICMP-сообщение в данном случае ''TTL expired in transit''.
 +
 
 +
 
 +
==Просмотр таблицы маршрутизации==
 +
Ниже приведены команды в разных операционных системах, с помощью которых можно посмотреть таблицу маршрутизации
 +
 
 +
Windows: '''route print'''
 +
 
 +
Linux:  '''route -n'''
 +
 
 +
==Источники информации==
 +
*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]
 +
* Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Алгоритмы разбора]]

Текущая версия на 04:28, 2 января 2017

Определения

Определение:
Таблица маршрутизации — таблица, состоящая из сетевых маршрутов и предназначенная для определения наилучшего пути передачи сетевого пакета.


Определение:
Сетевой маршрут — запись таблицы маршрутизации, содержащая в себе адрес сети назначения (destination), маску сети назначения (netmask), шлюз (gateway), интерфейс (interface) и метрику (metric).


Пример таблицы маршрутизации

Destination Netmask Gateway Interface Metric
0.0.0.0 0.0.0.0 192.168.0.1 192.168.0.100 10
127.0.0.0 255.0.0.0 127.0.0.1 127.0.0.1 1
192.168.0.0 255.255.255.0 192.168.0.100 192.168.0.100 10
192.168.0.100 255.255.255.255 127.0.0.1 127.0.0.1 10
192.168.0.1 255.255.255.255 192.168.0.100 192.168.0.100 10


Описание компонентов

Определение:
Адрес сети назначения (Destination) — собственно, адрес конечного узла пути передачи сетевого пакета.


Определение:
Маска сети назначения (Netmask) — битовая маска, определяющая, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. В двоичной записи всегда выглядит как множество единиц в начале и нулей в конце.


Пример получения адреса сети

Двоичная запись Десятичная запись
IP-адрес 11000000 10101000 00000001 00000010 192.168.1.2
Маска 11111111 11111111 11111110 00000000 255.255.254.0
Адрес сети 11000000 10101000 00000000 00000000 192.168.0.0

Чтобы вычислить адрес сети, нужно применить логическое и к адресу и маске.


Определение:
Шлюз (Gateaway) — адрес узла в сети, на который необходимо отправить пакет, следующий до указанного адреса назначения. Шлюзы бывают по умолчанию, тогда значения адреса назначения и маски указываются как 0.0.0.0.


Определение:
Интерфейс (Interface) указывает, какой локальный интерфейс отвечает за достижение шлюза. Например, шлюз 192.168.0.1 (интернет-маршрутизатор) может быть достижим через локальную сетевую карту, адрес которой 192.168.0.100.


Определение:
Метрика (Metric) — числовой показатель, задающий предпочтительность маршрута. Чем меньше число, тем более предпочтителен маршрут. Интуитивно представляется как расстояние (необязательный параметр).


Принцип действия

При отправке сетевого пакета, операционная система смотрит, по какому именно маршруту он должен быть отправлен, основываясь на таблице маршрутизации. Как правило, выбирается наиболее конкретный (т.е. с наиболее длинной сетевой маской) маршрут из тех, которые соответствуют адресу отправителя и имеют наименьшую метрику. Если ни один из маршрутов не подходит, пакет уничтожается, а его отправителю возвращается ICMP-сообщение No route to host.

Внутри каждого пакета есть поле TTL (Time to live) при каждой пересылке значение уменьшается на единицу, и если оно становится нулем, то пакет выбрасывается. ICMP-сообщение в данном случае TTL expired in transit.


Просмотр таблицы маршрутизации

Ниже приведены команды в разных операционных системах, с помощью которых можно посмотреть таблицу маршрутизации

Windows: route print

Linux: route -n

Источники информации

  • Алексей Сорокин — Алгоритм Эрли
  • Ахо А., Ульман Д.— Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.:«Мир», 1978. С. 358 — 364.
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shovkoplyas_Grigory&oldid=58514»