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

Наверное, немало пользователей Интернета удивлялись тому, с какой быстротой, скажем, Google дает ответ на запрос. Не последнюю роль в выполнении этой задачи играют маршрутизаторы, которые в состоянии обрабатывать поступающие пакеты с суммарной скоростью более 1 Tbps. Современные маршрутизаторы – весьма сложные устройства. При их разработке используются методы таких математических дисциплин, как теория графов и теория массового обслуживания, новейшие технологии в области коммутации пакетов, параллельных вычислений. Понятно, что их архитектура – тема солидной монографии. Здесь же мы попытаемся лишь весьма конспективно познакомить с нею читателей.

Создание маршрутизатора окутано облаком некоторой таинственности. К примеру, на сайте Cisco Systems и даже в их пособиях для сдачи сертификационных экзаменов можно найти совершенно романтическую историю о том, что в 1984 г. Лен Босак (Len Bosack) и Сэнди Лернер (Sandy Lerner), влюбленная пара из Стэнфордского университета и будущие основатели компании, работали в разных местах университетского городка, и для того чтобы иметь возможность вести личную переписку с помощью компьютеров, которые были подключены к разным сетям, придумали маршрутизатор.

Эта история до сих пор вызывает раздражение у 66-летнего Билла Ягера (William Yeager), разработчика первого маршрутизатора. Вот что он рассказал в одном из интервью.

Маршрутизаторы Cisco (второе поколение)

Проект начался в январе 1980 г., когда руководитель попросил его что-нибудь придумать, чтобы связать отдел теории вычислительных машин, медицинский центр и департамент электротехники. В университетский парк входили мэйнфреймы, системы DEC10, несколько машин Xerox PARC Lisp и файл-серверы Altos (впоследствии к ним добавились DEC VAX, TI Explorers и системы Symbolic). Все это нужно было соединить, потому что люди устали бегать туда и обратно с магнитными лентами.

После некоторых раздумий Билл пришел к выводу, что то, в чем он нуждался для решения этой задачи, было операционной системой, и начал разработку сетевой ОС и программы маршрутизации на PDP11/05. Нужен был очень компактный код и определение разумного числа входных буферов, поскольку это был бездисковый компьютер с всего лишь 56 КВ ОЗУ, так что при ошибке out of memory программа зависала. На надежность и оптимизацию алгоритма маршрутизации пакетов было потрачено все лето. Три последующих месяца ушло на сборку системы, а через шесть – первый маршрутизатор установили в телефонном шкафу в здании, расположенном посередине между медицинским центром и отделом вычислительных машин.

Что касается протоколов, то вначале маршрутизировались только пакеты PUP (Parc Universal Packet) для Xerox PARC и мэйнфреймов. Однако в конце 1981 г. Биллу было сказано сверху, что все вокруг переходят на IP и нужно об этом подумать. Тогда и добавился IP-маршрутизатор, правда, без поддержки протокола разрешения адресов ARP. В этом на тот момент не было особой необходимости, поскольку IP-адрес для пакетов сети Ethernet 3 Mbps состоял всего из двух байтов: один для сети и другой для хоста, адрес хоста являлся также и MAC-адресом. Затем была создана более совершенная модель маршрутизатора на базе платы с процессором Motorola 68000, сконструированной Энди Бехтольшаймом (Andy Bechtolsheim), будущим основателем Sun Microsystems. По-настоящему же серьезная разработка завершилась к 1985 г.

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

Тем временем Лен Босак еженедельно докладывал на семинарах о ходе работ. Было принято решение поддерживать только IP-протокол, и фрагменты кода для других протоколов были удалены. Годом позже модифицированная версия кода Ягера стала стандартом для маршрутизаторов в Стэнфорде.

О Cisco все узнали в 1986 г. Именно тогда компания выпустила на рынок свой первый маршрутизатор, который назывался Advanced Gateway Server. Он базировался на процессоре Motorola 68000 10 MHz, имел 1 MB памяти, восемь слотов для интерфейсных карт, к которым можно было подключить Ethernet, ARPAnet и низкоскоростные последовательные каналы. Первый год производительность составляла 200 пакетов в секунду.

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

В конце концов, Cisco выплатила авторский гонорар в размере 100 тыс. долл., из которых треть пошла университету, треть – отделу и треть – изобретателю. Свою часть Билл Ягер отдал отделу, поскольку считал, что разработка явилась результатом одного большого проекта. Такова история создания маршрутизатора в изложении Билла Ягера.

Однако прежде чем перейти к основной теме, рассмотрим...

...базовые функции IP-маршрутизаторов

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

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

Рис. 1. Обобщенная архитектура IP-маршрутизатора

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

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

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

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

• проверка корректности IP-пакета (номер версии, длина заголовка, вычисление контрольной суммы заголовка);
• разбор IP-адреса и поиск в маршрутной таблице адреса выходного порта;
• корректировка значения TTL (Time-to-Live) во избежание бесконечной циркуляции пакета между сетями;
• вычисление новой контрольной суммы заголовка.

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

Шинные архитектуры

Рис. 2. Традиционная шинная архитектура

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

Рис. 3. Архитектура с кэш-памятью на интерфейсных картах

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

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

Рис. 4. Архитектура с множеством параллельных машин продвижения

Еще одним вариантом разделяемой шины является архитектура с множеством параллельных машин продвижения данных (multiple parallel forwarding engines). Чтобы достичь высоких скоростей обработки, несколько машин соединяются параллельно, как показано на рис. 4. При поступлении пакета на входной интерфейс его IP-заголовок «отрезается» управляющей схемой, дополняется идентификационной меткой и посылается машине продвижения для проверки и маршрутизации. При этом его остаток сохраняется во входном буфере. Машина продвижения определяет выходной порт и посылает модифицированный заголовок пакета и метку соответствующему модулю интерфейса-получателя. Затем он поступает из буфера интерфейса-источника в буфер модуля интерфейса-получателя и передается на выходной канал.

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

Окончание в следующем номере