По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
На самом деле, чего только не происходит в компьютерных сетях. Разобраться сложно, а особенно сложно, когда речь заходит об адресации и приеме/передаче данных. Вопрос усложняется тем, что каждый из адресов функционирует на своем уровне модели OSI (Open Systems Interconnection).
Но, не нужно переживать. В этой статье, мы самым простым, но профессиональным языком объясним, что такое Media Access Control, или как сокращенно его называют MAC - адрес.
Этот тип адреса живет на втором (канальном, или Data Link) уровне модели OSI и является главным адресом на этом уровне.Устраивайтесь поудобнее, наливайте "чайковского" - будем разбираться.
Если вы не слышали про модель OSI ранее, то мы очень рекомендуем прочитать сначала статью про OSI, а потом уже приступать к изучению MAC - адреса.
Media Access Control (MAC) Address - я выбираю тебя!
MAC - адрес представляет собой уникальную комбинацию цифр и букв длиной 48 символов. Фактически, это аппаратный номер оборудования (компьютера, сервера, роутера, порта коммутатора, да чего угодно), который, внимание, присваивается сетевой карте устройства еще на фабрике, то есть в момент производства.
Да - да, MAC - адрес устройства это вам не IP - адрес устройства, который можно легко поменять. Этот адрес вшит аппаратно. Хотя, конечно, надо быть честными - как специалисты из Мытищ в гаражных условиях "перебьют" VIN номер автомобиля, так и MAC - адрес можно "перебить".
MAC - адрес еще называют уникальным физическим адресом устройства, помогающим идентифицировать устройство среди миллионов других устройств. В стандарте IEEE 802, канальный (второй, Data Link) уровень модели OSI разделен на два подуровня:
Logical Link Control (LLC) или подуровень управления логической связью
Media Access Control (MAC) или подуровень управления доступом к среде
И как раз, как можно догадаться, MAC - адрес используется на втором подуровне, Media Access Control, который является частью канального уровня модели OSI. А теперь поговорим про то, как выглядит MAC - адрес из из чего он состоит. Берем лист А4 и маркер - начинаем рисовать.
Форма MAC - адреса
"Я нарисоваль!" Вот картинка. Мы правда старались:
Стандартный MAC выглядит примерно вот так: 00-50-B6-5B-CA-6A.
Смотрите: мак - адрес это 12 - значное шестнадцатеричное число, или 6 - байтовое двоичное число. Чаще всего MAC - адрес представляют именно в шестнадцатеричной системе.
На картинки мы изобразили 6 октетов (неких групп), из которых состоит MAC. Каждый из октетов состоит из 2 знаков, итого получается 12 - значное число. Первые 6 цифр (к примеру 00-50-B6) обозначают производителя сетевой карты. Его также называют OUI (Organizational Unique Identifier) - мы отобразили эту часть на картинке выше.
Вот, например, известные MAC OUI популярных вендоров:
CC:46:D6 - Cisco
3C:5A:B4 - Google, Inc.
3C:D9:2B - Hewlett liackard
00:9A:CD - HUAWEI TECHNOLOGIES CO.,LTD
И, собственно, вторые 6 цифр (6 цифр справа) уникальны и идентифицируют NIC (Network Interface Controller). Часто, MAC адреса записывают по-разному: через тире, двоеточие, или точки. Например:
00-50-B6-5B-CA-6A - самая распространенная и привычная для всех форма записи;
00:50:B6:5B:CA:6A - форма записи используется части всего в Linux системах;
005.0b6.5bc.a6a - такой формат записи MAC - адреса используется компанией Cisco.
Как узнать MAC - адрес?
Итак, чтобы узнать MAC - адрес в UNIX/Linux системах, подключитесь по SSH к вашему серверу и дайте команды:
ifconfig -a
ip link list
ip address show
Чтобы узнать MAC - адрес в Windows системах, откройте командную строку машины/сервера. Сделать это можно нажав комбинацию клавиш Win + R, ввести cmd и нажать Enter. Как только откроется консоль, дайте следующие команду:
ipconfig /all
А если вы обладатель Macbook да и вообще OS X устройства (любите посидеть в Starbucks и здорово провести время на заводе "Флакон"), то сделать нужно следующее:
Откройте в Launchliad "Терминал".
Введите команду ifconfig.
В строке ether будет указан MAC-адрес
Возможно, вы уже слышали о термине "wirespeed" раньше. Это то, что отдел маркетинга любит использовать, когда речь заходит о продаже сетевого оборудования. Это означает, что пакеты могут быть переданы без какой-либо заметной задержки. Кстати, для остальной части этой статьи слова "многоуровневый коммутатор" и "маршрутизатор" - это одно и то же. Все, что я объясняю о многоуровневых коммутаторах отныне, также относится и к маршрутизаторам. Давайте посмотрим на разницу между коммутаторами 2уровня и многоуровневыми коммутаторами с точки зрения коммутации:
Вы знаете, что коммутаторы 2 уровня будут переключать только кадры Ethernet в пределах VLAN, и, если мы хотим, мы можем фильтровать трафик на основе уровня 2 (например, с защитой портов). Многоуровневый коммутатор может делать то же самое, но он также способен маршрутизировать между VLAN и фильтровать на уровне 3 или 4 с помощью списков доступа.
Переадресация на уровне 2 основана на конечном MAC-адресе. Наш коммутатор изучает исходные MAC-адреса на входящих кадрах и строит таблицу MAC-адресов. Всякий раз, когда фрейм Ethernet входит в один из наших интерфейсов, мы проверяем таблицу MAC-адресов, чтобы найти конечный MAC-адрес, и отправляем его в правильный интерфейс.
Переадресация на уровне 3 основана на IP-адресе назначения. Переадресация происходит, когда коммутатор получает IP-пакет, где исходный IP-адрес находится в другой подсети, чем конечный IP-адрес.
Когда наш многоуровневый коммутатор получает IP пакет со своим собственным MAC адресом в качестве назначения в заголовке Ethernet есть две возможности:
Если конечный IP-адрес является адресом, настроенным многоуровневом коммутаторе, то IP-пакет был предназначен для этого коммутатора.
Если конечный IP-адрес - это адрес, который не настроен на многоуровневом коммутаторе, то мы должны действовать как шлюз и "маршрутизировать" пакет. Это означает, что нам придется сделать поиск в таблице маршрутизации, чтобы проверить наличие самого полного совпадения. Кроме того, мы должны проверить, разрешен ли IP-пакет, если вы настроили ACL.
В те не далекие времена коммутация производилась на аппаратной скорости, а маршрутизация-на программной. В настоящее время как коммутация, так и маршрутизация выполняются на аппаратной скорости. В оставшейся части этой статьи вы узнаете почему.
Давайте рассмотрим разницу между обработкой кадров Ethernet и IP-пакетов:
Жизнь коммутатора уровня 2 проста
Коммутатор проверит контрольную сумму кадра Ethernet, чтобы убедиться, что он не поврежден или не изменен.
Коммутатор получает кадр Ethernet и добавляет исходный MAC-адрес в таблицу MAC-адресов.
Коммутатор направляет кадр Ethernet к правильному интерфейсу, если он знает конечный MAC-адрес. Если нет,то он будет отброшен (помечен как flood).
Там нет никакого изменения кадра Ethernet!
Теперь давайте посмотрим, что происходит, когда получает IP-пакет многоуровневый коммутатор:
В приведенном выше примере компьютер А посылает IP-пакет к компьютеру В. Обратите внимание, что они находятся в разных подсетях, поэтому нам придется его маршрутизировать. Когда наш многоуровневый коммутатор получит IP-пакет, вот что произойдет:
Коммутатор проверит контрольную сумму кадра Ethernet, чтобы убедиться, что он не поврежден или не изменен.
Коммутатор проверит контрольную сумму IP-пакета, чтобы убедиться, что он не поврежден или не изменен.
Многоуровневый коммутатор проверит таблицу маршрутизации, заметит, что 192.168.20 /24 напрямую подключен, и произойдет следующее:
Проверит таблицу ARP, чтобы увидеть, есть ли сопоставление уровня 2-3 для компьютера B. Если нет сопоставления, многоуровневый коммутатор отправит запрос ARP.
Конечный MAC-адрес изменится с FFF (многоуровневый коммутатор Fa0 / 1) на BBB (компьютер B).
Исходный MAC-адрес изменится с AAA (компьютер A) на GGG (многоуровневый коммутатор Fa0/2).
Поле TTL (time to live) в IP-пакете уменьшится на 1, и из-за этого контрольная сумма IP-заголовка будет пересчитана.
Контрольная сумма фрейма Ethernet должна быть пересчитана заново.
Фрейм Ethernet, несущий IP-пакет, будет отправлен из интерфейса к компьютеру B.
Как вы можете видеть, имеется довольно много шагов, связанных с маршрутизацией IP-пакетов.
Когда мы рассматриваем многоуровневый коммутатор возникает "разделение обязанностей". Мы должны построить таблицу для MAC-адресов, заполнить таблицу маршрутизации, ARP-запросы, проверить, соответствует ли IP-пакет списку доступа и т. д. И нам нужно переслать наши IP-пакеты. Эти задачи разделены между "плоскостью управления" и "плоскостью данных". Ниже приведен пример:
Плоскость управления отвечает за обмен информацией о маршрутизации с использованием протоколов маршрутизации, построение таблицы маршрутизации и таблицы ARP. Плоскость данных отвечает за фактическую пересылку IP-пакетов. Таблица маршрутизации не очень подходит для быстрой переадресации, потому что мы имеем дело с рекурсивной маршрутизацией.
Что такое рекурсивная маршрутизация?
Давайте рассмотрим пример:
В приведенном выше примере у нас есть три маршрутизатора. У R3 есть loopback интерфейс, к которому мы хотим получить доступ из R1. Будем использовать статические маршруты для достижения поставленной цели:
R1(config)#ip route 3.3.3.0 255.255.255.0 192.168.23.3
R1(config)#ip route 192.168.23.0 255.255.255.0 192.168.12.2
Первый статический маршрут предназначен для достижения интерфейса loopback0 R3 и указывает на интерфейс FastEthernet0/0 R3. Второй статический маршрут необходим для достижения сети 192.168.23.0/24.
Всякий раз, когда R1 хочет достичь 3.3.3.0/ 24, мы должны выполнить 3 поиска:
Первый поиск должен проверить запись для 3.3.3.0/24. Он должен быть там и должен быть IP-адрес следующего прыжка-192.168.23.3
Второй поиск относится к 192.168.23.3. Есть запись, и IP-адрес следующего прыжка - 192.168.12.2.
Третий и последний поиск относится к 192.168.12.2. Там имеется вход, и он напрямую подключен.
R1 должен проверить таблицу маршрутизации 3 раза, прежде чем он будет знать, куда отправлять свой трафик. Звучит не очень эффективно, верно? Выполнение нескольких поисков для достижения определенной сети называется рекурсивной маршрутизацией.
Большую часть времени все входящие и исходящие IP-пакеты будут обрабатываться и пересылаться плоскостью данных, но есть некоторые исключения, давайте сначала рассмотрим картинку ниже:
Большая часть IP-пакетов может быть передана плоскостью данных. Однако есть некоторые "специальные" IP-пакеты, которые не могут быть переданы плоскостью данных немедленно, и они отправляются на плоскость управления, вот некоторые примеры:
IP-пакеты, предназначенные для одного из IP-адресов многоуровневый коммутатора.
Трафик протокола маршрутизации, такой как OSPF, EIGRP или BGP.
IP-пакеты, которые имеют некоторые параметры, заданные в IP-заголовке.
IP-пакеты с истекшим сроком действия TTL
Плоскость управления может пересылать исходящие IP-пакеты на плоскость данных или использовать свой собственный механизм пересылки для определения исходящего интерфейса и следующего IP-адреса прыжка. Примером этого является маршрутизация на основе локальной политики.
Наш многоуровневый коммутатор выполняет больше шагов для пересылки пакетов, чем коммутаторы уровня 2, поэтому теоретически он должен работать медленнее, верно?
Одна из причин, по которой многоуровневые коммутаторы могут передавать кадры и пакеты на wirespeed, заключается в том, что в плате данных используется специальное оборудование, называемое ASICs.
Такая информация, как MAC-адреса, таблица маршрутизации или списки доступа, хранится в этих ASIC. Таблицы хранятся в content-addressable memory (Cam) и ternary content addressable memory (TCAM).
Таблица CAM используется для хранения информации уровня 2, например:
Исходный MAC-адрес.
Интерфейс, на котором мы узнали MAC-адрес.
К какой VLAN относится MAC-адрес.
Поиск таблицы происходит быстро! Всякий раз, когда коммутатор получает кадр Ethernet, он будет использовать алгоритм хэширования для создания "ключа" для целевого MAC-адреса + VLAN, и он будет сравнивать этот хэш с уже хэшированной информацией в таблице CAM. Таким образом, он может быстро искать информацию в таблице CAM.
Таблица TCAM используется для хранения информации "более высокого уровня", например:
Списки доступа.
Информацию о качестве обслуживания.
Таблицу маршрутизации.
Таблица TCAM может соответствовать 3 различным значениям:
0 = не просматривать.
1 = сравнивать
X = любое приемлемое значение.
Полезно для поиска, когда нам не нужно точное совпадение. (таблица маршрутизации или ACL, например).
Поскольку существует 3 значения, мы называем его троичным. Так почему же существует 2 типа таблиц?
Когда мы ищем MAC-адрес, нам всегда требуется точное совпадение. Нам нужен точный MAC-адрес, если мы хотим переслать кадр Ethernet. Таблица MAC-адресов хранится в таблице CAM.
Всякий раз, когда нам нужно сопоставить IP-пакет с таблицей маршрутизации или списком доступа, нам не всегда нужно точное соответствие. Например, IP-пакет с адресом назначения 192.168.20.44 будет соответствовать:
192.168.20.44 /32
192.168.20.0 /24
192.168.0.0 /16
По этой причине такая информация, как таблица маршрутизации, хранится в таблице TCAM. Мы можем решить, должны ли совпадать все или некоторые биты.
Пример таблицы TCAM
Если мы хотим сопоставить IP-адрес 192.168.10.22, многоуровневый коммутатор сначала посмотрит, есть ли "самое полное совпадение". Там ничего нет, что соответствовало бы полностью 192.168.10.22/32, поэтому мы продолжим сравнение на не полное соответствие. В этом случае есть запись, которая соответствует 192.168.10.0/24. Приведенный выше пример относится к поиску таблиц маршрутизации, спискам доступа, а также к качеству обслуживания, спискам доступа VLAN и многим другим.
Теперь вы знаете все шаги, которые должен выполнять многоуровневый коммутатор, когда он должен пересылать IP-пакеты, плоскость управления/данных и, что мы используем разные таблицы, хранящиеся в специальном оборудовании, называемом ASIC. Давайте подробнее рассмотрим фактическую "пересылку" IP-пакетов.
Существуют различные методы коммутации для пересылки IP-пакетов. Вот различные варианты коммутации:
Процессорная коммутация:
Все пакеты проверяются процессором, и все решения о пересылке принимаются в программном обеспечении...очень медленно!
Быстрая коммутация (также известное как кеширование маршрутов):
Первый пакет в потоке проверяется процессором; решение о пересылке кэшируется аппаратно для следующих пакетов в том же потоке. Это более быстрый метод.
(CEF) Cisco Express Forwarding (также известный как переключение на основе топологии):
Таблица пересылки, созданная в аппаратном обеспечении заранее. Все пакеты будут коммутироваться с использованием оборудования. Это самый быстрый метод, но есть некоторые ограничения. Многоуровневые коммутаторы и маршрутизаторы используют CEF.
При использовании процессорной коммутации маршрутизатор удалит заголовок каждого кадра Ethernet, ищет IP-адрес назначения в таблице маршрутизации для каждого IP-пакета, а затем пересылает кадр Ethernet с переписанными MAC-адресами и CRC на исходящий интерфейс. Все делается в программном обеспечении, так что это очень трудоемкий процесс.
Быстрая коммутация более эффективна, потому что она будет искать первый IP-пакет, но будет хранить решение о переадресации в кэше быстрой коммутации. Когда маршрутизаторы получают кадры Ethernet, несущие IP-пакеты в том же потоке, он может использовать информацию в кэше, чтобы переслать их к правильному исходящему интерфейсу.
По умолчанию для маршрутизаторов используется CEF (Cisco Express Forwarding):
Bellman-Ford - один из наиболее простых для понимания протоколов, поскольку он обычно реализуется путем сравнения недавно полученной информации о пункте назначения с существующей информацией о том же пункте назначения. Если вновь обнаруженный маршрут лучше, чем известный в настоящее время, маршрут с более высокой стоимостью просто заменяется в списке путей - в соответствии с правилом кратчайшего пути для поиска путей без петель в сети. Таким образом, перебирая всю топологию, можно найти набор кратчайших путей к каждому месту назначения. Рисунок 7 используется для иллюстрации этого процесса.
Примечание. Хотя Bellman-Ford в основном известен своим распределенным вариантом, реализованным в широко распространенных протоколах, таких как Routing Information Protocol (RIP), он изначально был разработан как алгоритм поиска, выполняемый в единой структуре, описывающей топологию узлов и ребер. Беллман-Форд рассматривается здесь как алгоритм.
Алгоритм Bellman-Ford
Bellman-Ford рассчитывает Shortest Path Tree к каждому достижимому пункту назначения в наихудшем случае O (V * E), где V - количество узлов (вершин) в сети, а E - количество каналов (ребер). По сути, это означает, что время, необходимое Bellman-Ford для работы с топологией и вычисления Shortest Path Tree, линейно зависит от количества устройств и каналов. Удвоение количества любого из них удвоит время, необходимое для выполнения. Удвоение обеих одновременно увеличит время работы в 4 раза.
Таким образом, алгоритм Bellman-Ford является умеренно медленным при использовании против более крупных топологий, когда узлы в таблице топологии начинаются в порядке от самого дальнего от корня до ближайшего к корню. Если таблица топологии отсортирована от ближайшего к корню до самого дальнего, Bellman-Ford может завершить работу за O(E), что намного быстрее. В реальном мире трудно обеспечить любой порядок, поэтому фактическое время, необходимое для построения Shortest Path Tree, обычно находится где-то между O(V * E) и O(E).
Bellman-Ford - это greedy алгоритм, предполагающий, что каждый узел в сети, кроме локального, доступен только по бесконечным стоимостям, и заменяющий эти бесконечные стоимости фактическими стоимостями по мере прохождения топологии. Предположение, что все узлы бесконечно удалены, называется ослаблением вычислений, так как он использует приблизительное расстояние для всех неизвестных пунктов назначения в сети, заменяя их реальной стоимостью после ее расчета.
Фактическое время выполнения любого алгоритма, используемого для расчета Shortest Path Tree, обычно ограничивается количеством времени, требуемым для передачи информации об изменениях топологии по сети. Реализации всех этих протоколов, особенно в их распределенной форме, будут содержать ряд оптимизаций, чтобы сократить время их выполнения до уровня, намного меньшего, чем наихудший случай, поэтому, хотя наихудший случай дается в качестве контрольной точки, он часто имеет мало влияющие на производительность каждого алгоритма в реальных развернутых сетях.
Чтобы запустить алгоритм Bellman-Ford в этой топологии, ее необходимо сначала преобразовать в набор векторов и расстояний и сохранить в структуре данных, такой как показано в Таблице 1.
В этой таблице девять записей, потому что в сети девять звеньев (граней). Алгоритмы кратчайшего пути вычисляют однонаправленное дерево (в одном направлении вдоль графа). В сети на рисунке 7 показано, что SPT берет начало в узле 1, а расчет показан удаленным от узла 1, который будет точкой, из которой будут выполняться вычисления. Алгоритм в псевдокоде следующий:
// создаем набор для хранения ответа, по одной записи для каждого узла
// первый слот в результирующей структуре будет представлять узел 1,
// второй узел 2 и т. д.
define route[nodes] {
predecessor // как узел
cost // как целое число
}
// установите для источника (меня) значение 0
// позиция 1 в массиве - это запись исходной точки.
route[1].predecessor = NULL
route[1].cost = 0
// таблица 1, приведенная выше, содержится в массиве под именем topo
// Обходим таблицу вершин (граней) один раз для каждой записи в маршруте
// (результаты) таблица, замены более длинных записей на более короткие
i = nodes
while i > 0 {
j = 1
while j <= nodes { // перебирает каждую строку в топологии
table
source_router = topo[j].s
destination_router = topo[j].d
link_cost = topo[j].cost
if route[source_router].cost == NULL {
source_router_cost = INFINITY
} else {
source_router_cost = route[source_router].cost
}
if route[destination_router].cost == NULL {
destination_router_cost = INFINITY
} else {
destination_router_cost = route[destination_router].cost
}
if source_router_cost + link_cost <= destination_router_cost {
route[destination_router].cost = source_router_cost + link_
cost
route[destination_router].predecessor = source_router
}
j = j + 1 //or j++ depending on what pseudocode this is
representing
}
i = i - 1
}
Этот код обманчиво выглядит сложнее, чем есть на самом деле. Ключевой строкой является сравнение if route [topo [j] .s] .cost + topo [j] .cost route [topo [j] .d] .cost. Полезно сосредоточиться на этой строке в примере. При первом прохождении внешнего цикла (который выполняется один раз для каждой записи в таблице результатов, здесь называется маршрутом):
Для первой строки topo-таблицы:
j равно 1, поэтому topo[j] .s - это узел 6 (F), источник вектора в таблице граней
j равно 1, поэтому topo[j] .d - это узел 7 (G), адресат вектора в таблице граней.
route[6].cost = infinity, topo[1].cost = 1, and route[7].cost = infinity (где infinity - бесконечность)
infinity + 1 == infinity, поэтому условие не выполняется и больше ничего не происходит
Любая запись в topo-таблице с исходной стоимостью infinity даст тот же результат, что и infinity + все, что всегда будет равно infinity. Остальные строки, содержащие источник со стоимостью infinity, будут пропущены.
Для восьмой строки topo-таблицы (восьмая грань):
j равно 8, поэтому topo[j].s - это узел 1 (A), источник вектора в таблице граней
j равно 8, поэтому topo[j].d - это узел 2 (B), место назначения вектора в таблице граней.
route [1].cost = 0, topo[8].cost=2 и route[2].cost = infinity.
0 + 2 = infinity, поэтому условие выполняется
route[2].predecessor установлен на 1, а route [2].cost установлен на 2
Для девятой строки topo -таблицы (девятая грань):
j равно 9, поэтому topo[j].s - это узел 1 (A), источник вектора в таблице граней
j равно 9, поэтому topo[j].d - это узел 3 (C), место назначения вектора в таблице граней.
route[1].cost=0, topo[9].cost=1 и route[3].cost = infinity.
0 + 1 = infinity, поэтому условие выполняется
route[3].predecessor установлен на 1, а route[3].cost установлен на 1
Во втором прогоне внешнего цикла:
Для пятой строки topo-таблицы (пятая грань):
j равно 5, поэтому topo[j].s - это узел 2 (B), источник вектора в таблице граней
j равно 5, поэтому topo[j].d - это узел 6 (F), место назначения вектора в таблице граней.
route[2].cost=2,topo[5].cost=1 и route[6].cost = infinity.
2 + 1 = infinity, поэтому условие выполняется
route[6].predecessor установлен на 2, а route[6].cost установлен на 3
Для шестой строки topo -таблицы (шестая грань):
j равно 6, поэтому topo[j].s равно 2 (B), источник вектора в таблице граней
j равно 6, поэтому topo[j].d равно 5 (E), место назначения вектора в таблице граней
route[2].cost=2, topo[6].cost=2 и route[5].cost = infinity.
2 + 2 = infinity, поэтому условие выполняется
route[5].predecessor установлен на 2, а route[5].cost установлен на 4
Окончание этого прогона показан в Таблице 2.
В третьем прогоне внешнего цикла узел 8 представляет особый интерес, поскольку есть два пути к этому месту назначения. Для второй строки topo -таблицы (вторая грань):
j равно 2, поэтому topo[j].s - это узел 5 (E), источник вектора в таблице граней
j равно 2, поэтому topo[j].d - это узел 8 (H), место назначения вектора в таблице граней
route[5].cost=4, topo[2].cost=1 и route[8].cost = infinity.
4 + 1 = infinity, поэтому условие выполняется
route[8].predecessor установлен на 5, а route[8].cost установлен на 5
Для третьей строки topo -таблицы (третья грань):
j равно 3, поэтому topo[j].s - это узел 4 (D), источник вектора в в таблице граней
j равно 3, поэтому topo[j].d - это узел 8 (H), источник вектора в таблице граней
route[4].cost=2,topo[3].cost=2 и route[8].cost = 5.
2 + 2 = 4, поэтому условие выполняется
route[8].predecessor установлен на 4, а route[8].cost установлен на 4
Интересным моментом в третьем цикле в topo-таблице является то, что запись для грани [5,8] обрабатывается первой, которая устанавливает передатчик 8 (H) на 5 и стоимость на 5. Однако когда обрабатывается следующая строка в таблице topo [4,8], алгоритм обнаруживает более короткий путь к узлу 8 и заменяет существующий. Таблица 2 показывает состояние таблицы маршрутов при каждом проходе через таблицу topo.
В таблице 2 верхняя строка представляет запись в таблице маршрутизации и узел, доступный в сети. Например, A (1) представляет лучший путь к A, B (2) представляет лучший путь к B и т. д. Столбец P представляет предшественника или узел, через который A должен пройти, чтобы достичь указанного пункта назначения. C представляет собой стоимость достижения этого пункта назначения. Рассмотренный пример сети может быть завершен за три цикла, если алгоритм настроен так, чтобы обнаруживать завершение дерева. Псевдокод, как показано, не имеет никакого теста для этого завершения и в любом случае будет выполнять полные 8 циклов (по одному для каждого узла).
Теперь почитайте про алгоритм диффузного обновления DUAL.