Входные порты

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

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

В данном случае роль маршрутного процессора исполняет центральный процессор рабочей станции, а входной порт представляет собой просто сетевую интерфейсную карту (например, Ethernet-карту).

ИСТОРИЧЕСКАЯ СПРАВКА—
На момент написания этой книги (февраль 2002) в компании Cisco работают более 30 ООО сотрудников, а капитализация составляет 150 миллиардов долларов. Сегодня эта компания доминирует в производстве Интернет-маршрутизаторов и занимает неплохие позиции в производстве Интернет-телефонии, где она в последние годы конкурирует с такими «гигантами» разработки телефонного оборудования, как Lucent, Alcatel, Northern Telecom и Siemens. Как этой компании удалось занять столь высокое место на рынке изготовителей сетевого и телефонного оборудования? Все началось в 1984 году (всего 18 лет назад) в общежитии Silicon Valley.

Лен Босак и его жена Санди Лернер работали в университете Станфорда, когда у них возникла идея создавать и продавать Интернет-маршрутизаторы научно-исследовательским институтам и университетам. Санди Лернер придумала название компании Cisco (сокращение от Сан-Франциско), кроме того, она разработала логотип компании. Изначально штаб-квартира корпорации располагалась в их комнате в общежитии, а проект финансировался из их собственных сбережений и доходов от работы по совместительству в качестве консультантов. К концу 1986 г. доходы компании Cisco достигли 250 000 долларов в месяц — неплохо для бизнеса, изначально финансировавшегося кредитными картами и не имевшего капитала. К концу 1987 года корпорации Cisco, наконец, удалось привлечь в свой бизнес 2 миллиона долларов от Sequoia Capital в обмен на одну треть акций. За несколько следующих лет корпорация Cisco продолжала расти и захватывать все больший сектор рынка. В то же время отношения между супругами Босак/Лернер и менеджерами Cisco испортились. В 1990 году корпорация Cisco стала открытым акционерным обществом, и в том же году Лернер и Босак ушли из компании.

При наличии таблицы продвижения данных поиск представляет собой относительно простую задачу — мы просто просматриваем таблицу продвижения данных, ища запись, которая лучше всего соответствует сетевому адресу получателя пакета. Если такую запись в таблице найти не удается, для передачи пакета выбирается маршрут по умолчанию. (В подразделе «Адресация в протоколе IPv4» раздела «Интернет-протокол» отмечалось, что лучшим соответствием адресу получателя пакета считается табличная запись с самым длинным сетевым префиксом, совпадающим с адресом получателя пакета.) На практике, однако, все не так просто. Возможно, наиболее важный усложняющий фактор состоит в том, что магистральные маршрутизаторы должны работать на высоких скоростях, выполняя миллионы операций поиска в секунду. В самом деле, желательно, чтобы входной порт мог работать на скорости линии, то есть операция поиска должна выполняться быстрее операции приема пакета во входной порт. В этом случае обработка полученного пакета может быть выполнена прежде, чем завершится операция получения следующего пакета. Чтобы получить представление о необходимой производительности операции поиска, рассмотрим так называемую линию ОС48, передающую данные на скорости 2,5 Гбит/с. При длине пакетов в 256 байт входной порт должен успевать выполнять приблизительно миллион операций поиска в секунду.

Поскольку скорости передачи данных в современных линиях связи очень высокие, линейный поиск в таблице продвижения данных просто невозможен. Более разумный подход заключается в хранении таблицы продвижения данных в виде дерева, каждый уровень которого соответствует одному двоичному разряду адреса получателя. Поиск адреса начинается с вершины дерева. Если первый бит адреса равен нулю, тогда дальнейший поиск ведется по левому поддереву; в противном случае адрес получателя должен находиться в правом поддереве. На каждом шаге просматривается один разряд адреса получателя и выбирается одна ветвь дерева из двух. Таким образом, всю таблицу продвижения данных можно просмотреть за N шагов, где N — количество двоичных разрядов в адресе. (Такой поиск называется двоичным поиском в адресном пространстве размера 2(N).) Однако даже этот метод можно усовершенствовать.

Но даже при N=32 (например, для 32-разрядного IP-адреса) скорость просмотра таблицы методом двоичного поиска недостаточно высока для маршрутизации в современных магистралях. Например, если на каждом шаге работы алгоритма требуется одно обращение к памяти, то при памяти со временем доступа 40 не уровня одного миллиона операций в секунду достичь не удастся. Для увеличения скорости поиска применяются несколько приемов. Один из таких приемов заключается в использовании ассоциативной памяти (Content Addressable Memory, САМ). В маршрутизаторах Cisco 8500 каждый порт оснащен САМ-памятью объемом 64 Кбайт. Другой метод увеличения скорости поиска состоит в том, что недавно полученные записи таблицы продвижения данных хранятся в кэше. В данном методе важен размер кэша.В последние годы были предложены еще более быстрые структуры данных, позволяющие находить записи в таблице за log(JV) шагов, а также новые методы сжатия таблиц продвижения данных. Аппаратный метод оптимизации поиска в таблице, использующий тот факт, что в адресе, как правило, ищутся 24 или меньше значимых разрядов.

Как только алгоритм поиска определяет выходной порт для пакета, этот пакет может быть передан в коммутационный блок. Однако, какТбудет показано далее, пакет может быть временно заблокирован на входе в коммутационный блок (так как коммутационный блок может быть занят другим пакетом). Таким образом, блокированный пакет необходимо поставить в очередь на входном порте, чтобы он мог пройти через коммутационный блок позднее. Более подробно мы рассмотрим вопросы блокировки, обработки очередей и планирования пакетов1 в маршрутизаторе (как на входных, так и на выходных портах) в подразделе «Очереди» данного раздела.