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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Просмотр таблицы маршрутизации)
 
(не показано 59 промежуточных версий 3 участников)
Строка 1: Строка 1:
== Идея ==
+
==Определения==
[[Файл:Interpolation_search.png|thumb|450px|right|Нахождение разделительного элемента]]
 
Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чём разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше".
 
  
== Алгоритм ==
+
{{Определение
Пусть <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 =  
 +
Таблица маршрутизации {{---}} таблица, состоящая из сетевых маршрутов и предназначенная для определения наилучшего пути передачи сетевого пакета.
 +
}}
  
=== Псевдокод ===
+
{{Определение
<code style = "display: inline-block;">
+
|definition =  
function interpolation_search(x)
+
Сетевой маршрут {{---}} запись таблицы маршрутизации, содержащая в себе адрес сети назначения (destination), маску сети назначения (netmask), шлюз (gateway), интерфейс (interface) и метрику (metric).
  l = 0 // левая граница поиска (будем считать, что элементы массива нумеруются с нуля)
+
}}
  r = n - 1 // правая граница поиска
 
 
  while a[l] <tex> $\le$ <\tex> x and x <tex> $\le$ <\tex> a[r]
 
    m = l + (x - a[l]) / (a[r] - a[l]) * (r - l); // элемент, с которым будем проводить сравнение
 
    if a[m] == x
 
      result = m
 
    if a[m] < x
 
      l = m + 1
 
    else
 
      r = m - 1
 
 
  if a[l] == x
 
    result = l
 
  else
 
    result = -1 // если такого элемента в массиве нет
 
</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>.
+
{| border="1"
 +
|-
 +
!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
 +
|}
  
При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до <tex> O(n) </tex>.
 
  
Эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика). Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями <tex>\log \log n</tex> и <tex>\log n</tex> становится значительной только при очень больших <tex>n</tex>. На практике при поиске в больших файлах оказывается выгодным на ранних стадиях применять интерполяционный поиск, а затем, когда диапазон существенно уменьшится, переходить к двоичному.
+
==Описание компонентов==
 +
{{Определение
 +
|definition =
 +
Адрес сети назначения (Destination) {{---}} собственно, адрес конечного узла пути передачи сетевого пакета.
 +
}}
  
== Литература ==
+
{{Определение
Д.Э. Кнут: [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)]
+
|definition =  
 +
Маска сети назначения (Netmask) {{---}} битовая маска, определяющая, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети.  
 +
В двоичной записи всегда выглядит как множество единиц в начале и нулей в конце.
 +
}}
  
Wikipedia: [http://en.wikipedia.org/wiki/Interpolation_search Interpolation search]
+
===Пример получения адреса сети===
 +
{| 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://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.