Корпоративные сети →Теория

Распределение изменений топологии сети

Вторая часть

Февраль 10, 2021 Мерион Нетворкс

14 минут чтения

Первая часть тут

Как только изменение в топологии сети было обнаружено, оно должно быть каким-то образом распределено по всем устройствам, участвующим в плоскости управления. Каждый элемент в топологии сети может быть описан как:

• Канал или граница, включая узлы или достижимые места назначения, прикрепленные к этому каналу.
• Устройство или узел, включая узлы, каналы и доступные места назначения, подключенные к этому устройству.

Этот довольно ограниченный набор терминов может быть помещен в таблицу или базу данных, часто называемую таблицей топологии или базой данных топологии. Таким образом, вопрос о распределении изменений в топологии сети на все устройства, участвующие в плоскости управления, можно описать как процесс распределения изменений в определенных строках в этой таблице или базе данных по всей сети.

Способ, которым информация распространяется по сети, конечно, зависит от конструкции протокола, но обычно используются три вида распространения: поэтапное (hop-by-hop) распространение, лавинное (flooded) распространение и централизованное (centralized) хранилище некоторого вида.

Лавинное (flooded) распространение.

При лавинной рассылке каждое устройство, участвующее в плоскости управления, получает и сохраняет копию каждой части информации о топологии сети и доступных местах назначения. Хотя существует несколько способов синхронизации базы данных или таблицы, в плоскостях управления обычно используется только один: репликация на уровне записи. Рисунок 6 иллюстрирует это.

На рисунке 6 каждое устройство будет рассылать известную ему информацию ближайшим соседям, которые затем повторно рассылают информацию своим ближайшим соседу. Например, A знает две специфические вещи о топологии сети: как достичь 2001: db8: 3e8: 100 :: / 64 и как достичь B. A передает эту информацию в B, который, в свою очередь, передает эту информацию в C. Каждое устройство в сети в конечном итоге получает копию всей доступной топологической информации; A, B и C имеют синхронизированные базы данных топологии (или таблицы).

На рисунке 6 связь C с D показана как элемент в базе данных. Не все плоскости управления будут включать эту информацию. Вместо этого C может просто включать подключение к диапазону адресов 2001: db8: 3e8: 102 :: / 64 (или подсети), который содержит адрес D.

Примечание. В более крупных сетях невозможно уместить все описание подключений устройства в один пакет размером с MTU, и для обеспечения актуальности информации о подключении необходимо регулярно задерживать время ожидания и повторно загружать данные.

Интересная проблема возникает в механизмах распространения Flooding рассылки, которые могут вызывать временные петли маршрутизации, называемые microloops. Рисунок 7 демонстрирует эту ситуацию. На рисунке 7, предположим, что канал [E, D] не работает. Рассмотрим следующую цепочку событий, включая примерное время для каждого события:

• Старт: A использует E, чтобы добраться до D; C использует D, чтобы добраться до E.
• 100 мс: E и D обнаруживают сбой связи.
• 500 мс: E и D рассылают информацию об изменении топологии на C и A.
• 750 мс: C и A получают обновленную информацию о топологии.
• 1000 мс: E и D пересчитывают свои лучшие пути; E выбирает A как лучший путь для достижения D, D выбирает C как лучший путь для достижения E.
• 1,250 мс: лавинная рассылка A и C информации об изменении топологии на B.
• 1400 мс: A и C пересчитывают свои лучшие пути; A выбирает B для достижения D, C выбирает B для достижения E.
• 1500 мс: B получает обновленную информацию о топологии.
• 2,000 мс: B пересчитывает свои лучшие пути; он выбирает C, чтобы достичь D, и A, чтобы достичь E.

Хотя время и порядок могут незначительно отличаться в каждой конкретной сети, порядок обнаружения, объявления и повторных вычислений почти всегда будет следовать аналогичной схеме. В этом примере между этапами 5 и 7 образуется микропетля; в течение 400 мс, A использует E для достижения D, а E использует A для достижения D. Любой трафик, входящий в кольцо в A или D в течение времени между пересчетом E лучшего пути к D и пересчетом A лучшего пути к D будет петлей. Одним из решений этой проблемы является предварительное вычисление альтернативных вариантов без петель или удаленных альтернатив без петель.

Hop by Hop

При поэтапном распределении каждое устройство вычисляет локальный лучший путь и отправляет только лучший путь своим соседям. Рисунок 8 демонстрирует это.

На рисунке 8 каждое устройство объявляет информацию о том, что может достигнуть каждого из своих соседей. D, например, объявляет о достижимости для E, а B объявляет о доступности для C, D и E для A. Интересно рассмотреть, что происходит, когда A объявляет о своей доступности для E через канал на вершине сети. Как только E получит эту информацию, у него будет два пути к B, например: один через D и один через A. Таким же образом у A будет два пути к B: один напрямую к B, а другой через E. Любой из алгоритмов кратчайшего пути, рассмотренные в предыдущих статьях, могут определить, какой из этих путей использовать, но возможно ли формирование микропетель с помощью лавинного механизма распределения?

Рассмотрим:

1. E выбирает путь через A, чтобы добраться до B.
2. Канал [A, B] не работает.
3. A обнаруживает этот сбой и переключается на путь через E.
4. Затем A объявляет этот новый путь к E.
5. E получает информацию об измененной топологии и вычисляет новый лучший путь через D.

В промежутке между шагами 3 и 5 А будет указывать на Е как на свой лучший путь к В, в то время как Е будет указывать на А как на свой лучший путь к В—микропетля. Большинство распределительных систем hop-by-hop решают эту проблему с помощью split horizon или poison reverse.

Определены они следующим образом:

1. Правило split horizon гласит: устройство не должно объявлять о доступности к пункту назначения, который он использует для достижения пункта назначения.
2. Правило poison reverse гласит: устройство должно объявлять пункты назначения по отношению к соседнему устройству, которое оно использует, чтобы достичь пункта назначения с бесконечной метрикой.

Если разделение горизонта (split horizon) реализованный на рисунке 8, E не будет объявлять о достижимости для B, поскольку он использует путь через A для достижения B. В качестве альтернативы E может отравить путь к B через A, что приведет к тому, что A не будет иметь пути через E к B.

Централизованное Хранилище.

В централизованной системе каждое сетевое устройство сообщает информацию об изменениях топологии и достижимости контроллеру или, скорее, некоторому набору автономных служб и устройств, действующих в качестве контроллера. В то время как централизация часто вызывает идею единого устройства (или виртуального устройства), которому передается вся информация и который передает правильную информацию для пересылки всем устройствам обработки пакетов в сети, это чрезмерное упрощение того, что на самом деле означает централизованная плоскость управления. Рисунок 9 демонстрирует это.

На рисунке 9, когда канл между D и F не работает:

1. D и F сообщают об изменении топологии контроллеру Y.
2. Y пересылает эту информацию другому контроллеру X.
3. Y вычисляет лучший путь к каждому месту назначения без канала [D, F] и отправляет его каждому затронутому устройству в сети.
4. Каждое устройство устанавливает эту новую информацию о пересылке в свою локальную таблицу.

Конкретный пример шага 3 - Y вычисляет следующий лучший путь к E без канала [D, F] и отправляет его D для установки в его локальной таблице пересылки. Могут ли микропетли образовываться в централизованной плоскости управления?

• Базы данных в X и Y должны быть синхронизированы, чтобы оба контроллера вычисляли одинаковые пути без петель в сети
• Синхронизация этих баз данных повлечет за собой те же проблемы и (возможно) использование тех же решений, что и решения, обсуждавшиеся до сих пор в этой статье.
• Подключенным устройствам потребуется некоторое время, чтобы обнаружить изменение топологии и сообщить об этом контроллеру.
• Контроллеру потребуется некоторое время, чтобы вычислить новые пути без петель.
• Контроллеру потребуется некоторое время, чтобы уведомить затронутые устройства о новых путях без петель в сети.

Во время временных интервалов, описанных здесь, сеть все еще может образовывать микропетли. Централизованная плоскость управления чаще всего переводится в плоскость управления не запущенными устройствами переадресации трафика. Хотя они могут казаться радикально разными, централизованные плоскости управления на самом деле используют многие из тех же механизмов для распределения топологии и достижимости, а также те же алгоритмы для вычисления безцикловых путей через сеть, что и распределенные плоскости управления.

Плоскости сегментирования и управления.

Одна интересная идея для уменьшения состояния, переносимого на любое отдельное устройство, независимо от того, используется ли распределенная или централизованная плоскость управления, заключается в сегментировании информации в таблице топологии (или базе данных). Сегментация-это разделение информации в одной таблице на основе некоторого свойства самих данных и хранение каждого полученного фрагмента или фрагмента базы данных на отдельном устройстве. Рисунок 10 демонстрирует это.

В сети на рисунке 10 предположим, что оба контроллера, X и Y, имеют информацию о топологии для всех узлов (устройств) и ребер (каналов) в сети. Однако для масштабирования размера сети доступные места назначения были разделены на два контроллера. Существует множество возможных схем сегментирования - все, что может разделить базу данных (или таблицу) на части примерно одинакового размера, будет работать. Часто используется хеш, так как хеши можно быстро изменить на каждом устройстве, где хранится сегмент, чтобы сбалансировать размеры сегментов.

В этом случае предположим, что схема сегментирования немного проще: это диапазон IP-адресов. В частности, на рисунке представлены два диапазона IP-адресов: 2001: db8: 3e8: 100 :: / 60, который содержит от 100 :: / 64 до 10f :: / 64; и 2001: db8: 3e8: 110 :: / 60, который содержит от 110 :: / 64 до 11f :: / 64. Каждый из этих диапазонов адресов разделен на один контроллер; X будет содержать информацию о 2001: db8: 3e8: 100 :: / 60, а Y будет содержать информацию о 2001: db8: 3e8: 110 :: / 64. Не имеет значения, где эти доступные пункты назначения подключены к сети. Например, информация о том, что 2001: db8: 3e8: 102 :: / 64 подключен к F, будет храниться в контроллере X, а информация о том, что 2001: db8: 3e8: 110 :: / 64 подключен к A, будет храниться на контроллере Y. Чтобы получить информацию о доступности для 2001: db8: 3e8: 102 :: / 64, Y потребуется получить информацию о том, где этот пункт назначения соединен с X. Это будет менее эффективно с точки зрения вычисления кратчайших путей, но он будет более эффективным с точки зрения хранения информации, необходимой для вычисления кратчайших путей. Фактически, возможно, если информация хранится правильно (а не тривиальным способом, используемым в этом примере), чтобы несколько устройств вычислили разные части кратчайшего пути, а затем обменивались только результирующим деревом друг с другом. Это распределяет не только хранилище, но и обработку.

Существует несколько способов, с помощью которых информация о плоскости управления может быть разделена, сохранена и, когда вычисления выполняются через нее, чтобы найти набор путей без петель через сеть.

Согласованность, доступность и возможность разделения.

Во всех трех системах распределения, обсуждаемых в этой статье, - лавинной, поэтапной и централизованных хранилищ - возникает проблема микропетель. Протоколы, реализующие эти методы, имеют различные системы, такие как разделение горизонта и альтернативы без петель, чтобы обходить эти микропетли, или они позволяют микропетлям появляться, предполагая, что последствия будут небольшими для сети. Существует ли объединяющая теория или модель, которая позволит инженерам понять проблемы, связанные с распределением данных по сети, и различные сопутствующие компромиссы?

Есть: теорема CAP.

В 2000 году Эрик Брюер, занимаясь как теоретическими, так и практическими исследованиями, постулировал, что распределенная база данных обладает тремя качествами: Согласованностью, Доступностью и устойчивость к разделению (Consistency, Accessibility Partition tolerance-CAP). Между этими тремя качествами всегда есть компромисс, так что вы можете выбрать два из трех в любой структуре системы. Эта гипотеза, позже доказанная математически, теперь известна как теорема CAP. Эти три термина определяются как:

• Согласованность: Каждый считыватель видит согласованное представление содержимого базы данных. Если какое-то устройство С записывает данные в базу данных за несколько мгновений до того, как два других устройства, А и В, прочитают данные из базы данных, оба считывателя получат одну и ту же информацию. Другими словами, нет никакой задержки между записью базы данных и тем, что оба считывателя, А и В, могут прочитать только что записанную информацию.
• Доступность: каждый считыватель имеет доступ к базе данных при необходимости (почти в реальном времени). Ответ на чтение может быть отложен, но каждое чтение будет получать ответ. Другими словами, каждый считыватель всегда имеет доступ к базе данных. Не существует времени, в течение которого считыватель получил бы ответ «сейчас вы не можете запросить эту базу данных».
• Устойчивость к разделению: возможность копирования или разделения базы данных на несколько устройств.

Проще изучить теорему CAP в небольшой сети. Для этого используется рисунок 11.

Предположим, что A содержит единственную копию базы данных, к которой должны иметь доступ как C, так и D. Предположим, что C записывает некоторую информацию в базу данных, а затем сразу же после, C и D считывают одну и ту же информацию. Единственная обработка, которая должна быть, чтобы убедиться, что C и D получают одну и ту же информацию, - это A. Теперь реплицируйте базу данных, чтобы была копия на E и еще одна копия на F. Теперь предположим, что K записывает в реплику на E, а L читает из реплики на F. Что же будет?

• F может вернуть текущее значение, даже если это не то же самое значение, что только что записал К. Это означает, что база данных возвращает непоследовательный ответ, поэтому согласованность была принесена в жертву разделению базы данных.
• Если две базы данных синхронизированы, ответ, конечно, в конечном итоге одинаковым, но потребуется некоторое время, чтобы упаковать изменение (упорядочить данные), передать его в F и интегрировать изменение в локальную копию F. F может заблокировать базу данных или определенную часть базы данных, пока выполняется синхронизация. В этом случае, когда L читает данные, он может получить ответ, что запись заблокирована. В этом случае доступность теряется, но сохраняется согласованность и разбиение базы данных.
• Если две базы данных объединены, то согласованность и доступность могут быть сохранены за счет разделения.

Невозможно решить эту проблему, чтобы все три качества были сохранены, из-за времени, необходимого для синхронизации информации между двумя копиями базы данных. Та же проблема актуальна и для сегментированной базы данных.

Как это применимо к плоскости управления? В распределенной плоскости управления база данных, из которой плоскость управления черпает информацию для расчета путей без петель, разделена по всей сети. Кроме того, база данных доступна для чтения локально в любое время для расчета путей без петель. Учитывая разделение и доступность, необходимые для распределенной базы данных, используемой в плоскости управления, следует ожидать, что непротиворечивость пострадает - и это действительно так, что приводит к микропетлям во время конвергенции. Централизованная плоскость управления не «решает» эту проблему. Централизованная плоскость управления, работающая на одном устройстве, всегда будет согласованной, но не всегда будет доступной, а отсутствие разделения будет представлять проблему для устойчивости сети.