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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Просмотр таблицы маршрутизации)
 
(не показано 11 промежуточных версий 2 участников)
Строка 1: Строка 1:
'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободной]] грамматике <tex>G</tex>.
 
 
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex> и слово <tex>w</tex>.<br/>
 
'''Выход:''' <tex>true</tex>, если <tex>w</tex> выводится в <tex>G</tex>; <tex>false</tex> — иначе.
 
 
 
==Определения==
 
==Определения==
{{Определение
 
|definition =
 
Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = w_1 w_2 ... w_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
 
Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>. '''<tex> \cdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex> \cdot \notin \Sigma \cup N</tex>).
 
}}
 
  
 
{{Определение
 
{{Определение
|definition =
+
|definition =  
'''<tex>j</tex>-м списком ситуаций''' <tex>D_j</tex> для входной цепочки <tex>w = w_1 w_2 ... w_n</tex>, где <tex>0 \leqslant j \leqslant n</tex>, называется множество ситуаций <tex>\lbrace [A \rightarrow \alpha \cdot \beta , i] \mid \alpha \Rightarrow^* w_{i+1} ... w_j; \exists \gamma, \delta : S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* w_1...w_i \rbrace</tex>. То есть <tex>\gamma \alpha </tex> выводит часть <tex>w</tex> c первого по <tex>j</tex>-й символ.
+
Таблица маршрутизации {{---}} таблица, состоящая из сетевых маршрутов и предназначенная для определения наилучшего пути передачи сетевого пакета.
}}
 
 
 
{{Лемма
 
|statement = <tex>(\exists \alpha : [S \rightarrow \alpha \cdot, 0] \in D_n) \Leftrightarrow w \in L(G)</tex>.
 
|proof = Поскольку <tex>S \Rightarrow^* \gamma S \delta</tex> (при <tex>\gamma = \delta = \varepsilon</tex>), из определения <tex>D_n</tex> получаем, что <tex>([S \rightarrow \alpha \cdot, 0] \in D_n) \Leftrightarrow (S \Rightarrow \alpha \Rightarrow^* w_1 ... w_n = w)</tex>.
 
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition =
+
|definition =  
Последовательность списков ситуаций <tex>D_0, D_1, .., D_n</tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>.
+
Сетевой маршрут {{---}} запись таблицы маршрутизации, содержащая в себе адрес сети назначения (destination), маску сети назначения (netmask), шлюз (gateway), интерфейс (interface) и метрику (metric).
 
}}
 
}}
  
== Алгоритм Эрли ==
+
===Пример таблицы маршрутизации===
Чтобы воспользоваться леммой, необходимо найти <tex>D_n</tex> для <tex>w</tex>. Алгоритм Эрли является [[Динамическое программирование|динамическим алгоритмом]]: он последовательно строит список разбора, причём при построении <tex>D_j</tex> используются <tex>D_0, \ldots, D_{j}</tex> (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).
+
{| border="1"
 
 
Алгоритм основывается на следующих трёх правилах:
 
# Если <tex>[A \rightarrow \alpha \cdot w_{j} \beta, i] \in D_{j-1}</tex> (где <tex>w_j</tex> — <tex>j</tex>-ый символ строки), то <tex>[A \rightarrow \alpha w_{j} \cdot \beta, i] \in D_j</tex>.
 
# Если <tex>[B \rightarrow \eta \cdot, i] \in D_j</tex> и <tex>[A \rightarrow \alpha \cdot B \beta, k] \in D_i</tex>, то <tex>[A \rightarrow \alpha B \cdot \beta, k] \in D_j</tex>.
 
# Если <tex>[A \rightarrow \alpha \cdot B \beta, i] \in D_{j} </tex> и <tex>(B \rightarrow \eta) \in P </tex>, то <tex>[B \rightarrow \cdot \eta, j] \in D_{j}</tex>.
 
 
 
=== Псевдокод ===
 
Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \rightarrow S)</tex>.
 
 
'''function''' <tex>\mathtt{earley}(G, w)</tex>:
 
  <font color=green>// Инициализация </font>
 
  <tex> D_{0} = \lbrace [S' \rightarrow \cdot S, 0] \rbrace </tex>
 
  '''for''' i = 1 '''to''' len(w) - 1
 
    <tex>D_i</tex> = <tex>\varnothing </tex>
 
  <font color=green>// Вычисление ситуаций </font>
 
  '''for''' j = 0 '''to''' len(w) - 1
 
    <tex>\mathtt{scan}(D, j, G, w)</tex>
 
    '''while''' <tex>D_j</tex> изменяется
 
      <tex>\mathtt{complete}(D, j, G, w)</tex>
 
      <tex>\mathtt{predict}(D, j, G, w)</tex>
 
  <font color=green>// Результат </font>
 
  '''if'''  <tex>[S' \rightarrow S \cdot, 0] \in D_{len(w)} </tex>
 
    '''return''' ''True''
 
  '''else'''
 
    '''return''' ''False''   
 
 
 
<font color=green>// Первое правило </font>
 
'''function''' <tex>\mathtt{scan}(D, j, G, w)</tex>:
 
  '''if''' <tex>j</tex> == <tex>0</tex>
 
    '''return'''
 
  '''for''' <tex>[A \rightarrow \alpha \cdot a \beta, i] \in D_{j - 1} </tex>
 
    '''if''' <tex>a</tex> == <tex>w_{j - 1}</tex>
 
      <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha \cdot a \beta, i]</tex>
 
 
<font color=green>// Второе правило </font>
 
'''function''' <tex>\mathtt{complete}(D, j, G, w)</tex>:
 
  '''for''' <tex>[B \rightarrow \eta \cdot, i] \in D_{j} </tex>
 
    '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, k] \in D_{i} </tex>
 
      <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha B \cdot \beta, k]</tex>
 
 
 
<font color=green>// Третье правило </font>
 
'''function''' <tex>\mathtt{predict}(D, j, G, w)</tex>:
 
  '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, i] \in D_{j} </tex>
 
    '''for''' <tex>(B \rightarrow \eta) \in P </tex>
 
      <tex>D_{j}</tex> <tex>\cup</tex>= <tex>[B \rightarrow \cdot \eta, j]</tex>
 
 
 
==Корректность алгоритма==
 
{{Теорема
 
|statement = Приведенный алгоритм правильно строит все списки ситуаций.
 
То есть алгоритм поддерживает инвариант <tex> [A \rightarrow \alpha \cdot \beta, i] \in D_{j} \Longleftrightarrow \exists \delta \in \Sigma \cup N : ((S' \Rightarrow^* w_0...w_{i-1} A \delta) \wedge A \Rightarrow^* w_i...w_{j-1})</tex>
 
|proof =
 
 
 
 
 
=====<tex>\Longrightarrow</tex>=====
 
Докажем индукцией по исполнению алгоритма.<br/>
 
База {{---}} <tex>[S' \rightarrow \cdot S, 0] \in D_0</tex>. Осталось разобраться, в результате применения какого правила ситуация <tex> [A \rightarrow \alpha \cdot \beta, i] </tex> попала в <tex>D_{j}</tex><br/>
 
 
 
1. Включаем по правилу <tex> \mathtt{scan}</tex>.<br/>
 
Это произошло, если <tex> \alpha = \alpha ' a</tex>, <tex>a = w_{j-1}</tex> и <tex> [A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}</tex>.<br/>
 
По предположению индукции <tex>S' \Rightarrow^* w_0...w_{i-1} A \delta</tex> и <tex>\alpha' \Rightarrow^* w_i...w_{j-2}</tex>,<br/>
 
тогда в силу <tex>a = w_{j-1}</tex> получаем <tex>\alpha = \alpha ' a \Rightarrow^* w_i...w_{j-2}w_{j-1} = w_i...w_{j-1}</tex>.<br/>
 
Таким образом условия: <tex>S' \Rightarrow^* w_0...w_{i-1} A \delta</tex> и <tex>\alpha \Rightarrow^* w_i...w_{j-1}</tex> выполняются.
 
 
 
2. Включаем по правилу <tex> \mathtt{predict}</tex>.<br/>
 
По построению: <tex> \alpha = \varepsilon </tex> и <tex>i=j</tex>, что автоматически влечет второй пункт утверждения.<br/>
 
Кроме того <tex>\exists  i' \le i</tex> и ситуация <tex>[A' \rightarrow \alpha ' \cdot A \delta ', i'] \in D_i</tex>, из чего по предположению индукции следует <tex>S' \Rightarrow^* w_0...w_{i'-1} A' \delta ''</tex>
 
и <tex> \alpha ' \Rightarrow^* w_{i'}...w_{i-1}</tex>.<br/>
 
Получаем, что <tex>S' \Rightarrow^* w_0...w_{i'-1} A' \delta ''</tex>, значит <tex>S \Rightarrow^* w_0...w_{i'-1} \alpha' A \delta' \delta '' </tex>, следовательно <tex> S' \Rightarrow^* w_0...w_{i'-1} w_{i'}...w_{i-1} A \delta' \delta ''
 
</tex>, в итоге <tex> S' \Rightarrow^* w_0...w_{i-1} A \delta</tex>, что нам и требовалось.
 
 
 
3. Включаем по правилу <tex> \mathtt{complete}</tex>.<br/>
 
По построению: <tex> \alpha = \alpha ' A' </tex> и <tex>\exists i', \delta : [A \rightarrow \alpha ' \cdot A' \beta, i] \in D_{i'} \wedge [A' \rightarrow \eta \cdot, i'] \in D_j</tex>.<br/>
 
Cледовательно <tex>\alpha = \alpha ' A' \Rightarrow^* w_i...w_{i'-1} w_{i'}...w_{j} = w_i...w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.
 
 
 
=====<tex>\Longleftarrow</tex>=====
 
В обратную сторону будем доказывать индукцией по суммарной длине вывода  <tex>w_0...w_{i-1} A \delta</tex> из <tex>S'</tex> и  <tex>w_i...w_{j-1}</tex> из <tex>\alpha</tex>. После чего применим
 
индукцию по длине вывода <tex>w_i...w_{j-1}</tex> из <tex>\alpha</tex>.<br/>
 
Рассмотрим три случая последнего символа <tex>\alpha</tex>:
 
 
 
1. <tex>\alpha = \alpha ' a</tex>, тогда <tex>a = w_{j-1}</tex> и <tex>\alpha ' \Rightarrow^* w_i...w_{j-2}</tex>.<br/>
 
По предположению индукции: <tex>[A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}</tex>, а отсюда по правилу <tex> \mathtt{scan}</tex> получаем <tex>[A \rightarrow \alpha ' a \cdot \beta, i] \in D_{j}</tex>.
 
 
 
2. <tex>\alpha = \alpha ' B</tex>, тогда <tex>\exists i' : \alpha ' \Rightarrow^* w_i...w_{i'-1} \wedge B ' \Rightarrow^* w_{i'}...w_{j-1}</tex>.<br/>
 
Тогда имеем <tex>[A \rightarrow \alpha ' a \cdot  \beta, i] \in D_{j}</tex>. Также можно записать <tex>S' \Rightarrow^* w_0...w_{i-1} A \delta</tex>, как <tex>S' \Rightarrow^* w_0...w_{i-1} w_i...w_{i'-1}B \beta \delta</tex>,
 
а также <tex>B \rightarrow \eta \wedge \eta \rightarrow w_{i'}...w_{j-1}<tex>.<br/>
 
Применяя индукцию по второму параметру получим <tex>[B \rightarrow \eta \cdot, i'] \in D_j</tex>, откуда по правилу <tex> \mathtt{complete}</tex> получаем <tex>[A \rightarrow \alpha ' B \cdot \beta, i] \in D_{j}</tex>.
 
 
 
3. <tex>\alpha = \varepsilon </tex>, тогда <tex>i=j</tex>.<br/>
 
Тогда либо <tex>i = 0 \wedge A = S \wedge \delta = \varepsilon</tex>, что доказывает базу индукции,<br/>
 
либо вывод можно записать в виде <tex>S' \Rightarrow^* w_0...w{i'-1}w_{i'}...w{i-1} A \delta ' \delta '' = w_0...w_{i-1} A \delta</tex> для некоторого правила <tex>(A' \rightarrow w_{i'}...w_{i-1} A \delta ') \in P</tex>. <br/>
 
Отсюда по предположению индукции <tex>[A' \rightarrow \cdot w_{i'}...w_{i-1} A \delta ', i'] \in D_{i'}</tex>,
 
что после нескольких применений правила <tex> \mathtt{scan}</tex> приводит к <tex>[A' \rightarrow w_{i'}...w_{i-1} \cdot  A \delta ', i'] \in D_{i}</tex>,
 
после чего по правилу <tex> \mathtt{predict}</tex> получим <tex>[A \rightarrow \cdot \beta, i] \in D_{j}</tex>, что и требовалось.
 
 
 
}}
 
 
 
==Пример==
 
Построим список разбора для строки <tex>w = (a + a)</tex> в грамматике со следующими правилами:
 
* <tex>S \rightarrow T + S</tex>;
 
* <tex>S \rightarrow T </tex>;
 
* <tex>T \rightarrow F * T</tex>;
 
* <tex>T \rightarrow F</tex>;
 
* <tex>F \rightarrow ( S )</tex>;
 
* <tex>F \rightarrow a</tex>.
 
 
 
{|
 
|-
 
|
 
 
 
{| class="wikitable"
 
|-
 
!<tex>I_0</tex>
 
|-
 
|
 
{|
 
 
|-
 
|-
!Ситуация !! Из правила
+
!Destination||Netmask||Gateway||Interface||Metric
 
|-
 
|-
|<tex>[S' \rightarrow \cdot S, 0]</tex> || 0
+
|0.0.0.0||0.0.0.0||192.168.0.1||192.168.0.100||10
 
|-
 
|-
|<tex>[S \rightarrow \cdot T + S, 0]</tex> || 3
+
|127.0.0.0||255.0.0.0||127.0.0.1||127.0.0.1||1
 
|-
 
|-
|<tex>[S \rightarrow \cdot T, 0]</tex> || 3
+
|192.168.0.0||255.255.255.0||192.168.0.100||192.168.0.100||10
 
|-
 
|-
|<tex>[T \rightarrow \cdot F * T, 0]</tex> || 3
+
|192.168.0.100||255.255.255.255||127.0.0.1||127.0.0.1||10
 
|-
 
|-
|<tex>[T \rightarrow \cdot F, 0]</tex> || 3
+
|192.168.0.1||255.255.255.255||192.168.0.100||192.168.0.100||10
|-
 
|<tex>[F \rightarrow \cdot ( S ), 0]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot a, 0]</tex> || 3
 
|}
 
 
|}
 
|}
  
||
 
  
{| class="wikitable"
+
==Описание компонентов==
 +
{{Определение
 +
|definition =
 +
Адрес сети назначения (Destination) {{---}} собственно, адрес конечного узла пути передачи сетевого пакета.
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
Маска сети назначения (Netmask) {{---}} битовая маска, определяющая, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети.
 +
В двоичной записи всегда выглядит как множество единиц в начале и нулей в конце.
 +
}}
 +
 
 +
===Пример получения адреса сети===
 +
{| class="simple" border="1"
 
|-
 
|-
!<tex>I_1</tex>
+
! ||Двоичная запись||Десятичная запись
 
|-
 
|-
|
+
|IP-адрес||<tt>11000000 10101000 00000001 00000010</tt> ||192.168.1.2
{|
 
 
|-
 
|-
!Ситуация !! Из правила
+
|Маска||  <tt>11111111 11111111 11111110 00000000</tt> || 255.255.254.0
 
|-
 
|-
|<tex>[F \rightarrow ( \cdot S ), 0]</tex> || 1
+
|Адрес сети||     <tt>11000000 10101000 00000000 00000000</tt> ||192.168.0.0
|-
 
|<tex>[S \rightarrow \cdot T + S, 1]</tex> || 3
 
|-
 
|<tex>[S \rightarrow \cdot T, 1]</tex> || 3
 
|-
 
|<tex>[T \rightarrow \cdot F * T, 1]</tex> || 3
 
|-
 
|<tex>[T \rightarrow \cdot F, 1]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot ( S ), 1]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot a, 1]</tex> || 3
 
|}
 
 
|}
 
|}
  
||
+
Чтобы вычислить адрес сети, нужно применить логическое ''и'' к адресу и маске.
  
{| class="wikitable"
+
{{Определение
|-
+
|definition =  
!<tex>I_2</tex>
+
Шлюз (Gateaway) {{---}} адрес узла в сети, на который необходимо отправить пакет, следующий до указанного адреса назначения. Шлюзы бывают ''по умолчанию'', тогда значения адреса назначения и маски указываются как 0.0.0.0.
|-
+
}}
|
 
{|
 
|-
 
!Ситуация !! Из правила
 
|-
 
|<tex>[F \rightarrow a \cdot, 1]</tex> || 1
 
|-
 
|<tex>[T \rightarrow F \cdot * T, 1]</tex> || 2
 
|-
 
|<tex>[T \rightarrow F \cdot , 1]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot , 1]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot + S, 1]</tex> || 2
 
|-
 
|<tex>[F \rightarrow ( S \cdot ), 0]</tex> || 2
 
|}
 
|}
 
  
|-
+
{{Определение
|
+
|definition =
 +
Интерфейс (Interface) указывает, какой локальный интерфейс отвечает за достижение шлюза. Например, шлюз 192.168.0.1 (интернет-маршрутизатор) может быть достижим через локальную сетевую карту, адрес которой 192.168.0.100.
 +
}}
  
{| class="wikitable"
+
{{Определение
|-
+
|definition =  
!<tex>I_3</tex>
+
Метрика (Metric) {{---}} числовой показатель, задающий предпочтительность маршрута. Чем меньше число, тем более предпочтителен маршрут. Интуитивно представляется как расстояние (необязательный параметр).
|-
+
}}
|
 
{|
 
|-
 
!Ситуация !! Из правила
 
|-
 
|<tex>[S \rightarrow T + \cdot S, 1]</tex> || 1
 
|-
 
|<tex>[S \rightarrow \cdot T + S, 3]</tex> || 3
 
|-
 
|<tex>[S \rightarrow \cdot T, 3]</tex> || 3
 
|-
 
|<tex>[T \rightarrow \cdot F * T, 3]</tex> || 3
 
|-
 
|<tex>[T \rightarrow \cdot F, 3]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot ( S ), 3]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot a, 3]</tex> || 3
 
|}
 
|}
 
  
||
+
==Принцип действия==
 +
При отправке сетевого пакета, операционная система смотрит, по какому именно маршруту он должен быть отправлен, основываясь на таблице маршрутизации.
 +
Как правило, выбирается наиболее конкретный (т.е. с наиболее длинной сетевой маской) маршрут из тех, которые соответствуют адресу отправителя и имеют наименьшую метрику.
 +
Если ни один из маршрутов не подходит, пакет уничтожается, а его отправителю возвращается ICMP-сообщение ''No route to host''.
  
{| class="wikitable"
+
Внутри каждого пакета есть поле TTL (Time to live) при каждой пересылке значение уменьшается на единицу, и если оно становится нулем, то пакет выбрасывается.
|-
+
ICMP-сообщение в данном случае ''TTL expired in transit''.
!<tex>I_4</tex>
 
|-
 
|
 
{|
 
|-
 
!Ситуация !! Из правила
 
|-
 
|<tex>[F \rightarrow a \cdot , 3]</tex> || 1
 
|-
 
|<tex>[T \rightarrow F \cdot * T, 3]</tex> || 2
 
|-
 
|<tex>[T \rightarrow F \cdot , 3]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot + S, 3]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot , 3]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T + S \cdot , 1]</tex> || 2
 
|-
 
|<tex>[F \rightarrow ( S \cdot ), 0]</tex> || 2
 
|}
 
|}
 
  
||
 
  
{| class="wikitable"
+
==Просмотр таблицы маршрутизации==
|-
+
Ниже приведены команды в разных операционных системах, с помощью которых можно посмотреть таблицу маршрутизации
!<tex>I_5</tex>
 
|-
 
|
 
{|
 
|-
 
!Ситуация !! Из правила
 
|-
 
|<tex>[F \rightarrow ( S )\cdot , 0]</tex> || 1
 
|-
 
|<tex>[T \rightarrow F \cdot * T, 0]</tex> || 2
 
|-
 
|<tex>[T \rightarrow F \cdot , 0]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot + S, 0]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot , 0]</tex> || 2
 
|-
 
|<tex>[S' \rightarrow S \cdot , 0]</tex> || 2
 
|}
 
|}
 
  
|}
+
Windows: '''route print'''
  
Так как <tex>[S' \rightarrow S \cdot , 0] \in I_5</tex>, то <tex>w \in L(G) </tex>.<br>
+
Linux:  '''route -n'''
  
 
==Источники информации==
 
==Источники информации==
 
*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]
 
*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]
 
* Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.
 
* Ахо А., Ульман Д.{{---}} Теория синтак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.