По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
Многоуровневый коммутатор будет использовать информацию из таблиц, которые созданы (плоскость управления) для построения аппаратных таблиц. Он будет использовать таблицу маршрутизации для построения FIB (информационной базы пересылки) и таблицу ARP для построения таблицы смежности. Это самый быстрый способ переключения, потому что теперь у нас есть вся информация уровня 2 и 3, необходимая для пересылки аппаратных пакетов IP.
Давайте посмотрим на информационную таблицу о пересылке и таблицу смежности на некоторых маршрутизаторах.
Будем использовать ту же топологию, что и ранее. 3 роутера и R3 имеет интерфейс loopback0. Будем использовать статические маршруты для полного подключения:
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
R2(config)#ip route 3.3.3.0 255.255.255.0 192.168.23.3
R3(config)#ip route 192.168.12.0 255.255.255.0 192.168.23.2
Это статические маршруты, которые мы будем использовать. Теперь посмотрим на таблицу маршрутизации и FIB:
show ip cef показывает нам таблицу FIB. Вы можете видеть, что есть довольно много вещей в таблице FIB. Ниже даны разъяснения по некоторым из записей:
0.0.0.0/0 - это для интерфейса null0. Когда мы получим IP-пакеты, соответствующие этому правилу, то оно будет отброшено.
0.0.0.0 /32 - это для всех-нулевых передач. Забудьте об этом, так как мы больше не используем его.
3.3.3.0 /24 - это запись для интерфейса loopback0 R3. Обратите внимание, что следующий переход - это 192.168.12.2, а не 192.168.23.3, как в таблице маршрутизации!
192.168.12.0/24 - это наша непосредственно подключенная сеть.
192.168.12.0/32 зарезервировано для точного сетевого адреса.
192.168.12.1/32 - это IP-адрес на интерфейсе FastEthernet 0/0.
192.168.12.2/32 - это IP-адрес на интерфейсе FastEthernet 0/0 R2.
192.168.12.255/32 - это широковещательный адрес для сети 192.168.12.0/24.
224.0.0.0/4 - соответствует всему многоадресному трафику. Он будет удален, если поддержка многоадресной рассылки отключена глобально.
224.0.0.0/24 - соответствует всему многоадресному трафику, зарезервированному для трафика управления локальной сетью (например, OSPF, EIGRP).
255.255.255.255/32 - широковещательный адрес для подсети.
Давайте подробно рассмотрим запись для network 3.3.3.0/24:
Номер версии говорит нам, как часто эта запись CEF обновлялась с момента создания таблицы. Мы видим, что для достижения 3.3.3.0/24 нам нужно перейти к 192.168.23.3 и что требуется рекурсивный поиск. Следующий прыжок-192.168.12.2. Он также говорит, что это valid cached adjacency (допустимая кэшированная смежность). Существует целый ряд различных смежностей:
Null adjacency: используется для отправки пакетов в интерфейс null0.
Drop adjacency: это для пакетов, которые не могут быть переданы из-за ошибок инкапсуляции, маршрутов, которые не могут быть разрешены, или протоколов, которые не поддерживаются.
Discard adjacency: это относится к пакетам, которые должны быть отброшены из-за списка доступа или другой политики.
Punt adjacency: используется для пакетов, которые отправляются на плоскость управления для обработки.
Пакеты, которые не пересылаются CEF, обрабатываются процессором. Если у вас есть много таких пакетов, то вы можете увидеть проблемы с производительностью.
Вы можете видеть, сколько пакетов было обработано процессором:
Вы можете использовать команду show cef not-cef-switched, чтобы проверить это. Количество пакетов указано по причине:
No_adj: смежность не является полной..
No_encap: Информация об ARP является неполной.
Unsupp’ted: пакет имеет функции, которые не поддерживаются.
Redirect: Перенаправление ICMP.
Receive: Это пакеты, предназначенные для IP-адреса, настроенного на интерфейсе уровня 3, пакеты, предназначенные для нашего маршрутизатора.
Options: В заголовке пакета есть параметры IP-адреса.
Access: ошибка сравнения со списком доступа
Frag: ошибка фрагментации пакетов
Мы также можем взглянуть на таблицу смежности, в которой хранится информация уровня 2 для каждой записи:
Вы можете использовать команду show adjacency summary, чтобы быстро посмотреть, сколько у нас есть смежностей. Смежность - это отображение от уровня 2 до уровня 3 и происходит из таблицы ARP.
R1#show adjacency
Protocol Interface Address
IP FastEthernet0/0 192.168.12.2(9)
R1 имеет только один интерфейс, который подключен к R2. Вы можете увидеть запись для ip 192.168.12.2, который является интерфейсом FastEthernet 0/0 R2. Давайте увеличим масштаб этой записи:
Мы видим там запись для 192.168.12.2 и там написано:
CC011D800000CC001D8000000800
Что означает это число? Это MAC-адреса, которые нам нужны, и Ethertype ... давайте разберем поподробнее его:
CC011D800000 - это MAC-адрес интерфейса R2 FastEthernet0 / 0
CC001D800000 - это MAC-адрес интерфейса R1 FastEthernet0/0.
0800 - это Ethertype. 0x800 означает IPv4.
Благодаря таблицам FIB и смежности у нас есть вся информация уровня 2 и 3, которая нам требуется для перезаписи и пересылки пакетов. Имейте в виду, что перед фактической пересылкой пакета мы сначала должны переписать информацию заголовка:
Исходный MAC-адрес.
Конечный MAC-адрес.
Контрольная сумма кадров Ethernet.
TTL IP-пакета.
Контрольная сумма IP-пакетов.
Как только это будет сделано, мы сможем переслать пакет. Теперь у вас есть представление о том, что такое CEF и как обрабатываются пакеты.
Возникает вопрос, а в чем разница между маршрутизаторами и коммутаторами, поскольку многоуровневый коммутатор может маршрутизировать, а маршрутизатор может выполнять коммутацию.
Различие между устройствамистанвится все меньше, но коммутаторы обычно используют только Ethernet. Если вы покупаете Cisco Catalyst 3560 или 3750, то у вас будут только интерфейсы Ethernet. У них есть ASICs, поэтому коммутация кадров может выполняться со скоростью линии связи. С другой стороны, маршрутизаторы имеют другие интерфейсы, такие как последовательные каналы связи, беспроводные сети, и они могут быть модернизированы модулями для VPN, VoIP и т. д. Вы не сможете настроить такие вещи, как NAT/PAT на (маленьком) коммутаторе. Однако грань между ними становится все тоньше
Маршрутизаторы используются для маршрутизации, коммутаторы уровня 2-для коммутации, но многоуровневые коммутаторы могут выполнять комбинацию того и другого. Возможно, ваш коммутатор выполняет 80% коммутации и 20% маршрутизации или наоборот. TCAM можно "запрограммировать" на использование оптимальных ресурсов с помощью шаблонов SDM.
SDM (Switching Database Manager) используется на коммутаторах Cisco Catalyst для управления использованием памяти TCAM. Например, коммутатор, который используется только для коммутации, не требует никакой памяти для хранения информации о маршрутизации IPv4. С другой стороны, коммутатору, который используется только в качестве маршрутизатора, не потребуется много памяти для хранения MAC-адресов.
SDM предлагает ряд шаблонов, которые мы можем использовать на нашем коммутаторе, вот пример коммутатора Cisco Catalyst 3560:
Выше вы можете видеть, что текущий шаблон является "desktop default", и вы можете видеть, сколько памяти он резервирует для различных элементов. Вот пример других шаблонов:
Вот шаблоны SDM для коммутатора. Мы можем изменить шаблон с помощью команды sdm prefer:
Вы должны перезагрузить устройство прежде, чем он вступит в силу:
SW1#reload
Теперь давайте еще раз проверим шаблон:
По сравнению с шаблоном "desktop default" мы теперь имеем двойное хранилище для одноадресных MAC-адресов. Однако для маршрутов IPv4 ничего не зарезервировано.
Это хорошая идея, чтобы установить шаблон SDM, для того чтобы соответствовать необходимому использованию вашего коммутатора. Если вы делаете как коммутацию, так и маршрутизацию и не уверены в том, какой шаблон выбрать, то вы можете посмотреть на текущее использование TCAM, вот как это сделать:
На данном рисунке многое не отображено, но вы можете видеть, как заполняется TCAM в данный момент. Теперь вам есть что сравнить с шаблонами SDM.
Графовые базы данных (Graph databases) – это нереляционные системы (NoSQL), которые определяют корреляции между сложно взаимосвязанными сущностями. Такая структура позволяет обойти ограничения реляционных БД и уделяет больше внимания отношениям между данными.
Графовая база данных позволяет аккуратно определять взаимосвязи и дает ответы на сложные вопросы о том, как точки данных соотносятся друг с другом.
В данной статье объясняется, что такое графовые базы данных, и как они работают. Но для начала можно быстро познакомиться с другими видами NoSQL.
Что такое графовая база данных?
Графовая база данных – это нереляционный тип баз данных, основанный на топографической структуре сети. Идея этой БД восходит к математической теории графов. Графы представляют наборы данных в виде узлов, ребер и свойств.
Узлы, или точки (nodes) – это экземпляры или сущности данных; ими является любой объект, который вы планируете отслеживать. Например, люди, заказчики, подразделения и т.д.
Ребра, или линии (edges) – это важнейшие концепции в графовых БД. Они отображают взаимосвязь между узлами. Эти связи имеют направление и могут быть одно- или двунаправленными.
Свойства (properties) содержат описательную информацию, связанную с узлами. В некоторых случаях свойства бывают и у ребер.
Узлы с пояснительными свойствами создают взаимосвязи, представленные через ребра.
Графовые БД предлагают концептуальное представление данных, тесно связанных с реальным миром. Моделировать сложные связи гораздо проще, поскольку отношениям между точками данных уделяется такое же внимание, как и самим данным.
Сравнение графовых и реляционных баз данных
Графовые БД не создавались для замены реляционных БД. Стандартом отрасли на текущий момент считаются реляционные БД. Но перед этим важно понять, что может предложить та или иная разновидность систем.
Реляционные базы данных обеспечивают структурированный подход к данным, а графовые БД считают более гибкими и ориентированы на быстрое понимание взаимосвязей между данными.
Графовые и реляционные БД имеют свою область применения. Сложные взаимосвязи лучше реализовать через графовые БД, поскольку их возможности превосходят традиционные реляционные СУБД. При создании моделей баз данных в реляционных системах MySQL или PostgreSQL требуется тщательное планирование, а в графовых используется более естественный и гибкий подход к данным.
В таблице ниже приведены ключевые отличия между графовыми и реляционными БД:
Тип
Графовые БД
Реляционные БД
Формат
Узлы и ребра со свойствами
Таблицы со строками и столбцами
Связи
Представлены в виде ребер между узлами
Создаются с помощью внешних ключей между таблицами
Гибкость
Гибкие
Жестко заданные
Сложные запросы
Быстрые и отзывчивые
Необходимы сложные соединения
Варианты использования
Системы с взаимосвязанными зависимостями
Системы с транзакциями и более простыми отношениями
Как работают графовые базы данных?
Графовые базы данных одинаково относятся к данным и взаимосвязям между ними. Связанные узлы физически связываются, и эта связь рассматривается как часть данных.
При таком моделировании данных вы можете запрашивать взаимосвязи также, как и сами данные. Вместо вычисления и запросов на подключение, графовые БД считывают взаимосвязи напрямую из хранилища.
По гибкости, производительности и адаптивности графовые БД близки к другим нереляционным моделям данных. В них, как и в других нереляционных БД, отсутствуют схемы, что делает данную модель гибкой и легко изменяемой.
Примеры использования графовых баз данных
Есть много примеров, когда графовые БД превосходят все прочие методы моделирования данных. Среди таких примеров можно выделить:
Рекомендательные сервисы в режиме реального времени. Динамичные рекомендации по продуктам и электронным товарам улучшают пользовательский опыт и максимизируют прибыль. Из известных компаний можно упомянуть Netflix, eBay и Walmart.
Управление основными данными. Привязка всех данных к одной общей точке обеспечивает постоянство и точность данных. Управление основными данными крайне важно для крупномасштабных компаний мирового уровня.
GDPR и соблюдение нормативных требований. С графами гораздо проще управлять безопасностью и отслеживать перемещение данных. Базы данных снижают вероятность утечки информации и обеспечивают большую согласованность при удалении данных, чем повышается общее доверие к конфиденциальной информации.
Управление цифровыми ресурсами. Объем цифрового контента просто огромен и постоянно растет. Графовые БД предлагают масштабируемую и простую модель данных, позволяющую отслеживать цифровые ресурсы: документы, расчеты, контракты и т.д.
Контекстно-зависимые сервисы. Графы помогают в предоставлении сервисов, приближенных к актуальным характеристиками мира. Будь то предупреждения о стихийных бедствиях, информация о пробках или рекомендации по товарам для конкретного местоположения, – графовые базы данных предлагают логическое решение для реальных обстоятельств.
Выявление мошенничества. Поиск подозрительных закономерностей и раскрытие мошеннических платежных схем выполняется в режиме реального времени. Выявление и изоляция частей графа позволяет быстрее обнаружить мошенническое поведение.
Семантический поиск. Обработка естественного языка бывает неоднозначной. Семантический поиск помогает определить значение ключевых слов и выдает более подходящие варианты, которые, в свою очередь проще отобразить с помощью графовых БД.
Сетевое управление. Сети – это не что иное, как связанные графы. Графовые БД снижают время, необходимое для оповещения сетевого администратора о проблемах в сети.
Маршрутизация. Информация передается по сети за счет поиска оптимальных маршрутов, и это делает графовые БД идеальным вариантом для маршрутизации.
Какие есть известные графовые базы данных?
С ростом больших данных и аналитики в соцсетях популярность графовых БД возрастает. Моделирование графов поддерживает множество многомодельных БД. Кроме того, доступно много нативных графовых БД.
JanusGraph
JanusGraph – это распределенная, масштабируемая система графовых БД с открытым кодом и широким набором возможностей по интеграции и аналитике больших данных. Ниже приведен перечень основных функций JanusGraph:
Поддержка ACID-транзакций с возможностью одновременного обслуживания тысяч пользователей
Несколько вариантов хранения графических данных, включая Cassandra и HBase
Встроенный сложный поиск, а также дополнительная (опциональная) поддержка Elasticsearch
Полная интеграция Apache Spark для расширенной аналитики данных
JanusGraph использует полный по Тьюрингу язык запросов для обхода графов
Neo4j
Neo4j (Network Exploration and Optimization 4 Java, что переводится как «исследование сети и оптимизация для Java») – это графовая база данных, написанная на Java с нативным хранением и обработкой графов. Основные возможности:
Масштабируемость БД за счет разделения данных на части – сегменты
Высокая доступность благодаря непрерывному резервному копированию и последовательным обновлениям
Высокий уровень безопасности: несколько экземпляров баз данных можно разделить, оставив их на одном выделенном сервере
Neo4j использует Cypher – язык запросов для графовых БД, который очень удобен для программирования
DGraph
DGraph (Distributed graph, что переводится как «распределенный граф») – это распределенная система графовых БД с открытым исходным кодом и хорошей масштабируемостью. Вот несколько интересных возможностей DGraph:
Горизонтальная масштабируемость для работы в реальной среде с ACID-транзакциями
DGraph – это свободно распространяемая система с поддержкой множества открытых стандартов
Язык запросов – GraphQL, который был разработан для API
DataStax Enterprise Graph
DataStax Enterprise Graph – это распределенная графовая БД на базе Cassandra. Она оптимизирована под предприятия. Несколько функций:
DataStax обеспечивает постоянную доступность для корпоративных нужд
База данных легко интегрируется с автономной платформой Apache Spark
Полная интеграция аналитики и поиска в реальном времени
Масштабируемость за счет наличия нескольких центров обработки данных
Поддержка Gremlin и CQL для запросов
Плюсы и минусы графовых баз данных
В каждом типе баз данных есть свои плюсы и минусы. Именно поэтому так важно понимать отличия между моделями и доступные возможности для решения конкретных проблем. Графовые БД – это развивающаяся технология с целями, отличными от других типов БД.
Плюсы
Вот несколько плюсов графовых баз данных:
Гибкая и адаптивная структура
Четкое представление взаимосвязей между сущностями
Запросы выводят результаты в реальном времени. Скорость зависит от количества связей
Минусы
Ниже перечислены основные минусы системы:
Отсутствует стандартизированный язык запросов. Язык зависит от используемой платформы
Графы не подходят для систем на основе транзакций
Небольшая база пользователей; при возникновении проблема сложно получить поддержку
Заключение
Графовые базы данных – это отличный подход для анализа сложных отношений между объектами данных. Быстрота запросов и результаты в режиме реального времени хорошо вписываются в требования современных и стремительно растущих исследований данных. Графы – это развивающаяся технология, которую ждет еще много улучшений.
В предыдущих лекциях обсуждалось правило кратчайшего пути и два алгоритма (или, возможно, системы) для поиска путей без петель через сеть. Существует широкий спектр таких систем—их слишком много, чтобы охватить их в отведенное время для изучения, - но для сетевых администраторв важно быть знакомыми хотя бы с некоторыми из этих систем. В этих лекциях сначала рассматривается алгоритм поиска кратчайшего пути Дейкстры, вектор пути и два различных алгоритма непересекающихся путей: Suurballe и Maximally Redundant Trees (MRTs). Наконец, в этих лекциях будет рассмотрена еще одна проблема, которую должны решить управляющие плоскости: обеспечение двусторонней связи через сеть.
Алгоритм Дейкстры Shortest Path First.
Алгоритм Дейкстры Shortest Path First (SPF), возможно, является наиболее широко известной и понятной системой для обнаружения Loop-Free путей в сети. Он используется двумя широко распространенными протоколами маршрутизации и во многих других повседневных системах, таких как программное обеспечение, предназначенное для поиска кратчайшего пути через дорожную сеть или для обнаружения соединений и паттернов соединений в социальных сетях.
Алгоритм Дейкстры в псевдокоде использует две структуры данных. Первый - это предварительный список или TENT; этот список содержит набор узлов, рассматриваемых для включения в дерево кратчайшего пути (Shortest Path Tree). Второй - PATH; этот список содержит набор узлов (а следовательно, и каналы), которые находятся в дереве кратчайшего пути.
01 move "me" to the TENT
02 while TENT is not empty {
03 sort TENT
04 selected == first node on TENT
05 if selected is in PATH {
06 *do nothing*
07 }
08 else {
09 add selected to PATH
10 for each node connected to selected in TOPO
11 v = find node in TENT
12 if (!v)
13 move node to TENT
14 else if node.cost < v.cost
15 replace v with node on TENT
16 else
17 remove node from TOPO
18 }
19 }
Как всегда, алгоритм менее сложен, чем кажется на первый взгляд; ключом является сортировка двух списков и порядок, в котором узлы обрабатываются вне списка TENT. Вот несколько примечаний к псевдокоду перед рассмотрением примера:
Процесс начинается с копии базы данных топологии, называемой здесь TOPO; это будет яснее в примере, но это просто структура, содержащая исходные узлы, целевые узлы и стоимость связи между ними.
TENT - это список узлов, которые можно условно считать кратчайшим путем к любому конкретному узлу.
PATH - это дерево кратчайшего пути (SPT), структура, содержащая loop-free путь к каждому узлу и следующий переход от «меня» к этому узлу.
Первым важным моментом в этом алгоритме является сохранение только узлов, уже каким-то образом связанных с узлом в списке PATH в TENT; это означает, что кратчайший путь в TENT - это следующий кратчайший путь в сети.
Второй важный момент в этом алгоритме - это сравнение между любыми существующими узлами TENT, которые подключаются к одному и тому же узлу; это, в сочетании с сортировкой TENT и отделением TENT от PATH, выполняет правило кратчайшего пути.
Имея в виду эти моменты, рисунки с 1 по 9 используются для иллюстрации работы алгоритма SPF Дейкстры.
На каждой из следующих иллюстраций вместе с сопроводительным описанием показан один шаг алгоритма SPF в этой сети, начиная с рисунка 2.
В точке, показанной на рисунке 2, A был перемещен из TOPO в TENT, а затем в PATH. Стоимость исходного узла всегда равна 0; эта линия включена для начала расчета SPF. Это представляет строки с 01 по 09 в псевдокоде, показанном ранее. На рисунке 3 показан второй этап расчета SPF.
На рисунке 3 каждый узел, подключенный к A, был перемещен из TOPO в TENT; это строки с 10 по 17 в псевдокоде, показанном ранее. Когда этот шаг начался, в TENT была только A, поэтому в TENT нет существующих узлов, которые могли бы вызвать какие-либо сравнения метрик. Теперь TENT отсортирован, и выполнение продолжается со строки 03 в псевдокоде. Рисунок 4 демонстрирует это.
На рисунке 4 один из двух путей с кратчайшей стоимостью - к B и F, каждый со стоимостью 1 - был выбран и перемещен в PATH (строки 05–09 в псевдокоде, показанном ранее). Когда B перемещается из TENT в PATH, любые узлы с началом B в TOPO перемещаются в TENT (строки 10-17 в псевдокоде). Обратите внимание, что C еще не был в TENT, прежде чем он был задействован посредством перехода B к PATH, поэтому сравнение показателей не выполняется. Стоимость для C - это сумма стоимости его предшественника в PATH (который равен B со стоимостью 1) и связи между двумя узлами; следовательно, C добавляется к TENT со стоимостью 2. TENT сортируется (строка 3 псевдокода), поэтому процесс готов к повторному запуску. На рисунке 5 показан следующий шаг в этом процессе.
На рисунке 5 был выбран кратчайший путь к TENT, и F переместился от TENT к PATH. Между F и E существует связь (показанная на предыдущих иллюстрациях как [E, F]), но путь через F к E имеет ту же стоимость, что и путь [A, E], поэтому эта линия не добавляется в TENT. Скорее он остается неактивным, поскольку не рассматривается для включения в SPT, и удаляется из TOPO. На рисунке 6 показан следующий шаг в процессе, который переместит один из путей метрики 2 в PATH.
Примечание. Большинство реальных реализаций поддерживают перенос нескольких путей с одинаковой стоимостью из TENT в PATH, поэтому они могут пересылать трафик по всем каналам с одинаковой метрикой. Это называется многолучевым распространением с равной стоимостью или ECMP. Для этого есть несколько различных способов, но они в этих лекциях не рассматриваются.
На рисунке 6 путь к C через B со стоимостью 2 был перемещен в PATH, а путь к D через [A, B, C, D] перемещен в TENT. Однако при перемещении этого пути к TENT строка 11 в псевдокоде находит существующий путь к D в TENT, путь [A, D], со стоимостью 5. Метрика нового пути, 3, ниже чем метрика существующего пути, 5, поэтому путь [A, D] удаляется из TENT, когда добавляется путь [A, B, C, D] (строка 15 в псевдокоде). На рисунке 7 показан следующий шаг, на котором линия оставшейся стоимости 2 перемещается из TENT в PATH.
На рисунке 7 путь к E стоимостью 2 был перемещен из TENT в PATH. G был перемещен в TENT стоимостью 4 (сумма [A, E] и [E, G]). Другой сосед E, F, исследуется, но он уже находится в PATH, поэтому не рассматривается для включения в TENT. На рисунке 8 показан следующий шаг, который перемещает D в PATH.
На рисунке 8 D общей стоимостью 3 перемещен из TENT в PATH. Это учитывает соседа D, G, последнюю запись в TOPO, для TENT. Однако уже существует путь к G с общей стоимостью 4 через [A, E, G], поэтому строка 14 в псевдокоде завершается ошибкой, и путь [D, G] удаляется из TOPO. Это последний SPT.
Основная трудность в понимании алгоритма Дейкстры заключается в том, что правило кратчайшего пути не выполняется в одном месте (или на одном маршрутизаторе), как это происходит с Bellman-Ford или Diffusing Update Algorithm (DUAL). Кратчайший путь (по-видимому) проверяется только при перемещении узлов из TOPO в TENT - но на самом деле сортировка самого TENT выполняет другую часть правила кратчайшего пути, и проверка по PATH для существующих узлов составляет еще один шаг в процесс, делающий процесс трехступенчатым:
Если путь к узлу длиннее, чем любой из TENT, то путь к TENT является более коротким путем по всей сети.
Путь, который поднялся к вершине TENT через сортировку, является самым коротким к этому узлу в сети.
Если путь перемещается к PATH от вершины TENT, это кратчайший путь к этому узлу в сети, и любые другие записи в TOPO к этому узлу следует отбросить.
При наличии базового алгоритма полезно рассмотреть некоторые оптимизации и расчет Loop-Free Alternates (LFAs) и remote Loop-Free Alternates (rLFAs).
Частичный и инкрементный SPF
Нет особой причины, по которой весь SPT должен перестраиваться каждый раз, когда происходит изменение топологии сети или информации о доступности. Рассмотрим рисунок 9 для объяснения.
Предположим, G теряет связь с 2001: db8: 3e8: 100 :: / 64. Устройству A не требуется пересчитывать свой путь к любому из узлов сети. Доступный пункт назначения - это просто лист дерева, даже если это набор хостов, подключенных к одному проводу (например, Ethernet). Нет причин пересчитывать весь SPT, когда один лист (или любой набор листьев) отключается от сети. В этом случае только лист (IP-адрес Интернет-протокола или доступный пункт назначения) должен быть удален из сети (или, скорее, пункт назначения может быть удален из базы данных без каких-либо изменений в сети). Это частичный пересчет SPT.
Предположим, что канал [C, E] не работает. Что делает А в этом случае? Опять же, топология C, B и D не изменилась, поэтому у A нет причин пересчитывать все дерево. В этом случае A может удалить все дерево за пределами E. Чтобы вычислить только измененную часть графа, выполните следующие действия:
Удалите отказавший узел и все узлы, которые нужно достичь через точку E.
Пересчитайте дерево только от предшественника C (в данном случае A), чтобы определить, есть ли альтернативные пути для достижения узлов, ранее доступных через E до того, как канал [C, E] не доступен.
Это называется инкрементным SPF.
Расчет LFA и rLFA.
Bellman-Ford не вычисляет ни соседей ниже по потоку, ни LFA, и, похоже, не располагает необходимой для этого информацией. DUAL по умолчанию вычисляет нисходящих соседей и использует их во время конвергенции. А как насчет протоколов на основе Дейкстры (и, соответственно, аналогичных алгоритмов SPF)? На рисунке 10 показан простой механизм, который эти протоколы могут использовать для поиска LFA и соседних узлов ниже по потоку.
Определение нисходящего соседа - это такое, при котором стоимость достижения соседом пункта назначения меньше, чем локальная стоимость достижения пункта назначения. С точки зрения А:
A знает местную стоимость проезда к месту назначения на основе SPT, созданного с помощью SPF Дейкстры.
A знает стоимость B и C, чтобы добраться до места назначения, вычитая стоимость каналов [A, B] и [A, C] из рассчитанной на местном уровне стоимости.
Следовательно, A может сравнивать локальную стоимость со стоимостью от каждого соседа, чтобы определить, находится ли какой-либо сосед в нисходящем направлении по отношению к любому конкретному месту назначения. Определение LFA:
Если затраты соседа для «меня» плюс затраты соседа на достижение пункта назначения ниже, чем местные затраты, соседом является LFA.
Вернее, учитывая:
NC - это стоимость соседа до пункта назначения.
BC - это стоимость соседа для меня.
LC - местная стоимость до места назначения.
Если NC + BC меньше LC, то соседом является LFA. В этом случае A знает стоимость каналов [B, A] и [C, A] с точки зрения соседа (она будет содержаться в таблице топологии, хотя не используется при вычислении SPT с использованием алгоритма Дейкстры). Таким образом, LFA и нисходящие соседи требуют очень небольшой дополнительной работы для расчета, но как насчет удаленных LFA? Модель P/Q Space обеспечивает простейший способ для алгоритмов на основе Дейкстры вычисления соседних узлов и LFA. Рисунок 11 используется для иллюстрации изнутри P/Q Space.
Определение пространства P - это набор узлов, доступных с одного конца защищенного соединения, а определение пространства Q - это набор узлов, достижимых без пересечения защищенного канала. Это должно предложить довольно простой способ вычисления этих двух пространств с помощью Дейкстры:
Рассчитайте SPT с точки зрения устройства, подключенного к одному концу линии связи; удалить линию связи без пересчета SPT. Остальные узлы доступны с этого конца линии.
На рисунке 11 E может:
Вычислите пространство Q, удалив линию [E, D] из копии локального SPT и всех узлов, для достижения которых E использует D.
Вычислите пространство P, вычислив SPT с точки зрения D (используя D в качестве корня дерева), удалив линию [D, E], а затем все узлы, для достижения которых D использует E.
Найдите ближайший узел, достижимый как из E, так и из D, с удаленной линией [E, D].
SPF Дейкстры - это универсальный, широко используемый алгоритм для вычисления Shortest Path Trees через сеть.