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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Просмотр таблицы маршрутизации)
 
(не показано 12 промежуточных версий 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>.<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>.
 
 
 
}}
 
 
 
==Пример==
 
Построим список разбора для строки <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
 
|-
 
|-
|
+
|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
 
|-
 
|-
|<tex>[S' \rightarrow \cdot S, 0]</tex> || 0
+
|192.168.0.0||255.255.255.0||192.168.0.100||192.168.0.100||10
 
|-
 
|-
|<tex>[S \rightarrow \cdot T + S, 0]</tex> || 3
+
|192.168.0.100||255.255.255.255||127.0.0.1||127.0.0.1||10
 
|-
 
|-
|<tex>[S \rightarrow \cdot T, 0]</tex> || 3
+
|192.168.0.1||255.255.255.255||192.168.0.100||192.168.0.100||10
|-
 
|<tex>[T \rightarrow \cdot F * T, 0]</tex> || 3
 
|-
 
|<tex>[T \rightarrow \cdot F, 0]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot ( S ), 0]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot a, 0]</tex> || 3
 
|}
 
 
|}
 
|}
  
||
 
  
{| class="wikitable"
+
==Описание компонентов==
|-
+
{{Определение
!<tex>I_1</tex>
+
|definition =  
|-
+
Адрес сети назначения (Destination) {{---}} собственно, адрес конечного узла пути передачи сетевого пакета.
|
+
}}
{|
+
 
|-
+
{{Определение
!Ситуация !! Из правила
+
|definition =
|-
+
Маска сети назначения (Netmask) {{---}} битовая маска, определяющая, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети.
|<tex>[F \rightarrow ( \cdot S ), 0]</tex> || 1
+
В двоичной записи всегда выглядит как множество единиц в начале и нулей в конце.
|-
+
}}
|<tex>[S \rightarrow \cdot T + S, 1]</tex> || 3
+
 
|-
+
===Пример получения адреса сети===
|<tex>[S \rightarrow \cdot T, 1]</tex> || 3
+
{| class="simple" border="1"
 
|-
 
|-
|<tex>[T \rightarrow \cdot F * T, 1]</tex> || 3
+
! ||Двоичная запись||Десятичная запись
 
|-
 
|-
|<tex>[T \rightarrow \cdot F, 1]</tex> || 3
+
|IP-адрес||<tt>11000000 10101000 00000001 00000010</tt> ||192.168.1.2
 
|-
 
|-
|<tex>[F \rightarrow \cdot ( S ), 1]</tex> || 3
+
|Маска||  <tt>11111111 11111111 11111110 00000000</tt> || 255.255.254.0
 
|-
 
|-
|<tex>[F \rightarrow \cdot a, 1]</tex> || 3
+
|Адрес сети||    <tt>11000000 10101000 00000000 00000000</tt> ||192.168.0.0
|}
 
 
|}
 
|}
  
||
+
Чтобы вычислить адрес сети, нужно применить логическое ''и'' к адресу и маске.
  
{| 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.