Алгоритм связующего дерева

Алгоритм связующего дерева
Merge-arrow.svg
 Необходимо перенести содержимое этой статьи в статью «STP».
Вы можете помочь проекту, объединив статьи.
В случае необходимости обсуждения целесообразности объединения, замените этот шаблон на шаблон {{к объединению}} и добавьте соответствующую запись на странице Википедия: К объединению. Пожалуйста, также проверьте историю правок.

Алгоритм связующего дерева — алгоритм, применяемый для построения топологии пересылки пакетов, исключающей зацикливание. Сетевой мост (коммутатор) использует алгоритм связующего дерева (spanning tree algorithm, STA), разработанный институтом IEEE.[источник не указан 174 дня] Если в сети с мостовыми подключениями (в сегменте сети из коммутаторов) имеется несколько путей, могут образоваться циклические маршруты, и следование простым правилам пересылки данных через мост (коммутатор) приведет к тому, что один и тот же пакет будет бесконечно передаваться с одного моста на другой (передаваться по кольцу из коммутаторов). Алгоритм связующего дерева позволяет по мере необходимости автоматически отключать передачу через мост в отдельных портах (блокировать порты коммутатора), чтобы предотвратить зацикливание в топологии маршрутов пересылки пакетов. Для использования алгоритма связующего дерева в сетевом мосте никакой дополнительной настройки не требуется. [1]

Протокол STP

Основная статья: STP

Алгоритм связующего дерева является основой протокола STP (Spanning Tree Protocol), динамически отключающего избыточные связи в сети стандарта Ethernet (для образования древовидной топологии). STP стандартизован IEEE и поддерживается многими моделями управляемых коммутаторов, в частности, включен по умолчанию на всех коммутаторах Cisco.

Суть работы протокола заключается в том, что поддерживающие его коммутаторы сети Ethernet обмениваются друг с другом информацией «о себе». На основании определённых условий (обычно в соответствии с настройками) один из коммутаторов выбирается «корневым» (или «root»), после чего все остальные коммутаторы по алгоритму связующего дерева выбирают для работы порты, «ближайшие» к «корневому» коммутатору (учитывается количество посредников и скорость линий). Все прочие сетевые порты, ведущие к «корневому» коммутатору, блокируются. Таким образом образуется несвязное дерево с корнем в выбранном коммутаторе.

В коммутаторах Cisco с поддержкой VLAN протокол STP по умолчанию выполняется независимо для каждой виртуальной сети.

Кроме STP, в коммутаторах могут применяться другие методики обнаружения и устранения петель — например, сравнением таблиц коммутации (списков MAC-адресов) разных портов, или сравнением контрольных сумм проходящих пакетов (совпадение указывает на одинаковые пакеты, которые появляются из-за петель). По сравнению с описанными методами, случайным образом (или основываясь на каких-то догадках) блокирующими «дублирующие» порты, протокол STP обеспечивает древовидную структуру всего сегмента, при любом количестве резервных линий между произвольными коммутаторами, поддерживающими STP.

  1. ↑ Сетевой мост
Компьютерная сеть

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "Алгоритм связующего дерева" в других словарях:

  • Дистанционно-векторный алгоритм маршрутизации — Алгоритмы маршрутизации применяются для определения оптимального пути пакетов от источника к приёмнику и являются основой любого протокола маршрутизации. Для формулирования алгоритмов маршрутизации сеть рассматривается как граф. При этом… …   Википедия

  • Алгоритмы маршрутизации — Для улучшения этой статьи желательно?: Исправить статью согласно стилистическим правилам Википедии. Перевести текст с иностранного языка на русский …   Википедия

  • Суффиксное дерево — Суффиксное дерево  бор, содержащий все суффиксы некоторой строки (и только их). Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w|  длина строки w. Содержание 1 Основные определения и описание структуры …   Википедия

  • АВЛ-дерево — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей. АВЛ дерево сбалансированное по в …   Википедия

  • Декартово дерево — Декартово дерево  это двоичное дерево, в узлах которого хранятся: ссылки на правое и левое поддерево; ссылка на родительский узел (необязательно); ключи и , которые являются двоичным деревом поиска по ключу и двоичной кучей по ключу ; а… …   Википедия

  • R-дерево — (англ. R trees)  древовидная структура данных (дерево), предложенная в 1984 году Антонином Гуттманом. Оно подобно B дереву, но …   Википедия

  • Двоичное дерево поиска — Тип Дерево Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(h) O(n) Вставка O(h) O(n) Удаление O(h) O(n) где h высота дерева …   Википедия

  • K-мерное дерево — Тип Многомерное дерево Двоичное дерево поиска Изобретено в 1975 году Изобретено Джон Бентли Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(n) Вставка O(log n) O(n) Удаление O …   Википедия

  • Красно-чёрное дерево — Тип дерево поиска Изобретено в 1972 году Изобретено Рудольф Байер Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(log n) Вставка O(log n) O(log n) Удаление O(log n) O(log n) Красно чёрное… …   Википедия

  • Двоичное разбиение пространства — BSP дерево  это структура данных, используемая в трехмерной графике. Аббревиатура BSP означает Binary Space Partition  двоичное разбиение пространства. BSP дерево используется для эффективного выполнения следующих операций: Сортировки… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»