Заметки об архитектуре маршрутизаторов

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

Мультипроцессорная архитектура на базе коммутаторов

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

Рис. 1. Коммутационная архитектура с множеством машин продвижения

Пример мультигигабитового маршрутизатора с коммутационной архитектурой приведен на рис. 1. Его конструкция предусматривает выделенные машины продвижения для IP-пакетов с кэш-памятью в каждой из них. Мультигигабитовый маршрутизатор (МММ) состоит из множества интерфейсных карт (каждая из которых поддерживает один или более сетевых интерфейсов) и машин продвижения, и все это соединяется посредством матричного коммутатора. Интерфейсные карты и машины продвижения размещаются на отдельных платах. Когда пакет поступает на входной интерфейс, его заголовок удаляется и передается через коммутатор на машину продвижения. Остаток пакета сохраняется на входном интерфейсе. Машина продвижения анализирует заголовок и определяет, на какой выходной интерфейс следует отправить пакет, модифицирует заголовок и пересылает его на входной интерфейс. Тот, в свою очередь, объединяет новый заголовок с остатком пакета и передает на выходной интерфейс. Подобно большинству маршрутизаторов, МММ имеет процессор для управления маршрутизацией, обеспечивающий базовые функции управления (такие, как генерация маршрутных таблиц для машин продвижения).

Заголовки пакетов, поступающие в машину продвижения, размещаются в очереди типа «первый пришел – первый вышел» (FIFO) для обработки процессором продвижения. Сам процесс продвижения осуществляется в три стадии.

Первая предусматривает следующие шаги, которые выполняются параллельно:

• подтверждение корректности заголовка дейтаграммы IPv4;
• проверка соответствия протоколу длин пакета и заголовка;
• уточнение, не имеет ли заголовок IPv4 опций;
• вычисление смещения в хэш-таблице в кэш-памяти маршрутов;
• начало загрузки следующего заголовка.

На второй стадии машина продвижения проверяет, есть ли в кэш-памяти искомый маршрут. Если нет, то она выполняет расширенный поиск в соответствующей таблице продвижения. В этом случае процессор ищет в маршрутной таблице нужный маршрут и генерирует его версию для кэширования. Затем машина продвижения проверяет значение поля TTL, обновляет его и контрольную сумму и проверяет, не предназначена ли дейтаграмма непосредственно данному маршрутизатору.

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

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

Коммутационная архитектура с распределенными процессорами

Рис. 2. Базовая распределенная коммутационная архитектура (функциональная диаграмма)

Как видно, повышению быстродействия препятствуют три основных фактора: недостаточные вычислительная мощность, пропускные способности подсистемы памяти и внутренних шин. Для преодоления этих проблем была предложена распределенная архитектура на базе коммутатора с надлежащим образом спроектированными сетевыми интерфейсами. Идея состояла в том, чтобы перенести на них часть работы по продвижению пакетов, разгрузив тем самым ЦП и шину памяти. Ниже описана архитектура, в которой каждый сетевой интерфейс оборудован вычислительным блоком и буферной памятью. Базовая схема маршрутизатора с коммутационной распределенной архитектурой представлена на рис. 2.

Функциональные компоненты (входные, выходные и локальные блоки) обрабатывают входной и выходной трафики. Они реализуют все функции протоколов (плюс QoS). Для того чтобы обеспечить гарантированный уровень QoS, порт может нуждаться в классификации пакетов по предопределенным классам обслуживания. В зависимости от конкретной конструкции маршрутизатора порт может обрабатывать и протоколы канального и сетевого уровней. Конкретные особенности блоков обработки зависят от функциональной декомпозиции и деталей реализации. Сетевые интерфейсы соединяются посредством высокопроизводительного коммутатора, с помощью которого они обмениваются данными и управляющими сообщениями. Для выполнения ряда общих задач может использоваться также ЦП.

Интерфейс, обусловленный средой (Media-Specific Interface – MCI), выполняет все функции физического уровня и в случае протокола IEEE 802 – подуровня управления доступом к среде (MAC). Интерфейс с коммутационной фабрикой отвечает за подготовку пакетов для их передачи через коммутационное поле. Он может присоединить к пакету префикс, содержащий внутреннюю маршрутную метку с адресом порта выхода, приоритетом QoS и удаления.

Рис. 3. Пример функционального разделения в распределенной архитектуре

Рис. 4. Функциональная диаграмма распределенной архитектуры

Процесс обработки протокола IP – наиболее ресурсоемкий в маршрутизации пакетов, и в типичном случае именно он определяет производительность. Распределенная архитектура позволяет выполнить декомпозицию протокола с целью его дальнейшей параллельной обработки, а также отделить задачи, связанные с определением маршрутов в сети, от критических по времени задач обработки IP-заголовков. Пример функционального разделения в распределенной архитектуре приведен на рис. 3.

Высокоуровневая диаграмма маршрутизатора с распределенной архитектурой представлена на рис. 4. Для проведения вычислений интерфейсная карта может содержать либо процессор общего назначения, либо специализированную микросхему (ASIC). Выбор между этими двумя возможностями не столь однозначен – одни разработчики маршрутизаторов говорят, что поскольку спецификация IPv4 не изменяется, то применение ASIC выгоднее для реализации машины продвижения. Они упрощают создание системных плат и способствуют повышению производительности. Другие отмечают, что поскольку Интернет постоянно эволюционирует, это требует модификации программного обеспечения, так что более подходящим будет все же процессор общего назначения.

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

Типичные коммутационные фабрики маршрутизаторов

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

Фактически конструкция всех IP-маршрутизаторов базируется на комбинации следующих основных подходов: разделяемые память и среда, распределенный буферизованный вывод и пространственное разделение (кроссовая коммутационная матрица, crossbar). Для данного входного трафика конструкция коммутационной фабрики должна преследовать цели максимизировать пропускную способность и минимизировать задержки пакетов и их потери. Вдобавок необходимо свести количество буферов к минимуму и добиться простоты реализации.

Разделяемая среда

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

Рис. 5. Коммутационная фабрика на базе разделяемой шины TDM

Другой пример фабрики с разделяемой шиной приведен на рис. 5. Приходящие пакеты в широковещательном режиме распространяются по шине в циклическом порядке. На каждом выходе устанавливается адресный фильтр, который проверяет внутреннюю маршрутную метку каждого пакета для определения, не ему ли он предназначен. При совпадении адресов фильтр пропускает пакеты в выходной буфер. Если маршрутизатор имеет N входных и N выходных портов и каждый из них передает S пакетов в секунду, а пропускная способность шины достаточно высока – по крайней мере, N•S пакетов в секунду, то конфликтов по доступу не будет, и очереди образуются только на выходных портах. В противном случае необходимы буферы и на портах входа.

Такой подход позволяет естественным образом реализовать многоадресные и широковещательные передачи. Однако адресные фильтры и выходные буферы должны работать на скорости разделяемой среды, которая может быть в N раз выше, чем скорость работы портов. А поскольку существуют физические ограничения на скорости шины, адресных фильтров и выходных буферов, то такая архитектура плохо масштабируется по количеству портов и скоростям передачи. Можно увеличивать либо количество портов, либо скорость их работы, но так, чтобы произведение N•S оставалось постоянным.

Разделяемая память

Рис. 6. Коммутационная фабрика на базе разделяемой памяти

Типичная архитектура с разделяемой памятью приведена на рис. 6. Поступающие пакеты преобразуются из последовательного формата в параллельный и затем записываются в двухпортовую память. Заголовки пакетов с внутренними маршрутными метками доставляются в контроллер памяти, который определяет, в каком порядке они будут считываться из памяти. Далее пакеты направляются на соответствующие выходные порты, где вновь преобразуются в последовательный формат.

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

К сожалению, данная архитектура имеет ряд недостатков. Так как пакеты записываются и считываются из памяти одновременно, она должна иметь суммарную пропускную способность, т. е. записывать и считывать пакеты каждые 1/N•S секунд, или в N раз быстрее скорости работы портов. Это ограничивает масштабируемость таких маршрутизаторов. Более того, центральный контроллер памяти должен обрабатывать пакеты с той же скоростью, что и память. Такая задача может быть трудно выполнимой в случае управления множеством классов приоритетов и сложными операциями планирования. Маршрутизаторы с разделяемой памятью имеют единую точку отказа, поскольку добавление еще одной коммутационной фабрики слишком сложно и дорого.

Распределенные выходные буферы

Рис. 7. Распределенный буферизованный выход

В архитектуре, представленной на рис. 7, между всеми возможными парами входных и выходных портов (N2) существуют независимые пути. Входные пакеты в широковещательном режиме поступают по отдельным шинам на все выходы. Адресные фильтры направляют соответствующие пакеты в буфера очередей на выходных портах. В классическом варианте количество буферов равно N2.

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

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

Попытку уйти от степенной зависимости предприняла компания AT&T, предложив так называемый коммутатор с выбыванием (knockout switch) с фиксированным числом буферов (L) на каждом выходном порту. Это решение основано на предположении, что одновременное поступление на выход более чем L пакетов маловероятно. Таким образом, рост количества буферов становился линейным (N∙L), а изменяя величину L, можно регулировать долю потерянных пакетов.

Пространственное разделение

Рис. 8. Коммутационная фабрика на базе кроссовой матрицы

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

Данная архитектура хорошо масштабируется до очень высокой производительности и в то же время создает ряд технических проблем. Одна из них – блокировка первым в очереди (head-of-queue – HOQ), возникающая в том случае, когда пакеты должны быть направлены в разные порты. При этом если порт первого пакета занят, то второй не будет отправлен, даже если его порт свободен. Хорошо известно, что если входной трафик имеет равномерное распределение, то пропускная способность достигает только 58,6%. Более того, показано, что максимальная пропускная способность маршрутизатора на кроссовой матрице монотонно уменьшается с увеличением длины пакетов.

Одним из способов снижения эффекта HOQ является повышение скорости работы кроссовой матрицы. Но если она будет иметь пропускную способность выше, чем каналы, то необходимо также снабжать буферами и выходные порты. В результате получается так называемый комбинированный буферизованный вход–выход (Combined Input Output Buffered – CIOB). Другой способ – изменение структуры очередей во входных буферах. Взамен управления общей очередью FIFO создаются отдельные очереди на каждый выходной порт – виртуальные выходные очереди (Virtual Output Queues – VOQ).

Цель разработчиков маршрутизаторов с такой архитектурой – найти компромисс между минимальной требуемой пропускной способностью и системами CIOB и VOQ.

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

Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365