Принципы коммутации пакетов

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

Операция обработки данных сама по себе проста и состоит из следующих этапов;

• • Этап 1. Пакет приходит в интерфейс.

  • Этап 2. Определяется адрес получателя пакета и сравнивается со списком известных получателей.

  • Этап 3. Если найдено совпадение, пакет пересылается в соответствующий интерфейс.

  • Этап 4. Если совпадение с соответствующим списком не найдено, то пакет игнорируется.

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

В связи с постоянным увеличением размеров и количества маршрутизируемых сетей естественным является непрерывная модернизация и улучшение методов коммутации операционной системой. В первой версии операционной системы IOS использовался только один метод коммутации пакетов, который называется программной коммутацией (process switching).

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

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

Ниже перечислены все методы коммутации пакетов, включенные в операционную систему Cisco IOS версии 12.0 (Cisco IOS Release 12.0).

• • Программная коммутация.

  • Быстрая коммутация (Fast switching).

  • Автономная коммутация (Autonomous switching).

  • Процесс коммутации корпорации Silicon (Silicon switching engine switching, SSE switching).

  • Оптимальная коммутация (Optimum switching).

  • Распределенная быстрая коммутация (Distributed fast switching).

  • Экспресс-пересылка корпорации Cisco (Cisco Express Forwarding, CEF).

  • Распределенная экспресс-пересылка корпорации Cisco (Distributed Cisco Express Forwarding).

Ниже будут описаны детали четырех из перечисленных выше методов:

• 1. программной коммутации,

  2. быстрой коммутации,

  3. оптимальной коммутации,

  4. экспресс-коммутации корпорации Cisco.

*** Автономная коммутация и процесс коммутации корпорации Silicon являются платформозависимыми методами и в данное время не распространены в сети, поэтому не рассматриваются.

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

Несмотря на то что для иллюстрации методов коммутации используются примеры, основанные на маршрутизации протокола IP (Internet Protocol, протокол Internet), большинство из них можно применить и к другим сетевым протоколам, таким как протокол межсетевого пакетного обмена IPX (Internetwork Packet Exchange protocol) и туннельный протокол (bridging).

Хотя для разных протоколов используются различные структуры данных (например, разделен кэш для протоколов IP и IPX при использовании метода быстрой коммутации), но их содержание однотипно и коммутация происходит идентично для каждого протокола. https://habrahabr.ru/company

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

Процесс ip_input начинает выполняться в том случае, когда хотя бы один пакет по падает во входящую очередь (третий этап). По окончании работы процесса ip_input (четвертый этап) начинается операция пересылки пакета. На этом этапе проводятся все проверки и выбирается направление пересылки входящего пакета. В рассмотренном примере ip_input просматривает таблицу маршрутизации на наличие маршрута к получателю IP-пакета. Если маршрут найден, то по записи в таблице маршрутизации определяется адрес следующей точки перехода (следующего маршрутизатора на пути к получателю пакета). Затем из таблицы протокола ARP (Address Resolution Protocol) определяется информация, необходимая для формирования нового заголовка MAC (Media Access Control), для пересылки пакета к следующей точке перехода. Процесс ip_input формирует новый заголовок MAC и записывает его поверх старого во входящем пакете, после чего он помещается в очередь для отправки через выходной сетевой интерфейс (этап пятый).

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

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

Недостатки программной коммутации

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

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

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

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

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

• • Доступность. Доступен ли получатель? Если доступен, то каков IP-адрес следующей точки перехода на пути к получателю пакета? Необходимая информация хранится в таблице маршрутов (также называемой forwarding table — таблицей пересылки).

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

  • МАС-заголовок. Какой заголовок MAC необходимо прописать в пакете для правильной адресации к следующей точке перехода? МАС-заголовок хранится в ARP-таблице протокола IP или другой таблице соответствия МАС-адресов, как, например, в карте маршрутов протокола Frame Relay (Frame Relay map table).

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

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

Итак, каким образом система IOS позволяет организовать меньшие таблицы для поиска и добиться с их помощью увеличения производительности? Ответ — быстрый кэш (Fast Cache).

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

На втором этапе аппаратная часть интерфейса посылает прерывание центральному процессору, информируя его о том, что пришедший пакет находится в буфере ввода-вывода. Обработчик прерываний операционной системы IOS проверяет заголовок пакета и убеждается, что это пакет протокола IP. Затем, вместо помещения пакета, как это делалось раньше, в очередь для процесса ip_input, обработчик прерываний проверяет быстрый кэш на наличие в нем записи адреса устройства-получателя. При наличии записи в кэше обработчик прерываний считывает МАС-заголовок в таблице и помешает его в пакет. Из записи в кэше также определяется указатель для соответствующего выходного интерфейса. Третий этап демонстрирует чтение записи из кэша и переписывание МАС-адреса пакета.

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

При обработке прерывания все процессы в системе останавливаются до завершения работы обработчика прерываний

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

Данный пример только иллюстрирует, как работает механизм быстрой коммутации. Обратите внимание на то, что процесс ip_input не принимает участия в коммутации пакета; фактически ни один отложенный процесс при работе метода быстрой коммутации не влияет на сам процесс коммутации до тех пор, пока существует запись в кэше. При использовании быстрого кэша система IOS выполняет всю последовательность коммутации пакета в течение очень короткого периода одного прерывания - ! Кэширование позволяет разделить ресурсоемкую операцию выбора маршрута с относительно легкой процедурой пересылки пакета. Итак, метод быстрой коммутации вводит понятие “маршрутизировать однажды, пересылать — много раз”.

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

Метод использования механизма программной коммутации для заполнения быстрого кэша работает хорошо при определенных условиях: сеть должна быть стабильной с небольшими изменениями в маршрутизации, поток данных в основном идет между небольшим количеством получателей. Эти условия справедливы в большинстве случаев. В некоторых ситуациях, как, например, для "Backbon Internet"(совокупность быстрых каналов и ибслуживающих их маршрутиризаторов, объединяющих крупные узлы сети), они нарушаются. В случае магистрального канала возрастает количество “промахов” кэша (ситуация, когда для пакета не найдена запись в кэше), и как результат — большее количество пакетов коммутируется методом программной коммутации. Также возможна ситуация, приводящая к очистке кэша, когда старые записи в кэше переписываются новыми из-за отсутствия свободного места в кэше для всех необходимых записей.

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

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

Этот узел не подключен напрямую к маршрутизатору А, следовательно, необходимо снова просматривать таблицу маршрутизации для определения следующей точки перехода. Маршрутизатор А определяет, что 1Р-адрес 10.1.2.2 доступен через устройство с адресом 10.1.1.2, которое, в свою очередь, подключено к маршрутизатору напрямую.

Маршрутизатор А теперь будет посылать все данные, предназначенные для получателя с адресом 10.1.3.38, через устройство 10.1.1.2.

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

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

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

• • Для точки перехода изменилась, была удалена или устарела запись в ARP-таблице.

  • Префикс в таблице маршрутизации изменился или был удален.

  • Изменился адрес следующей точки перехода в таблице маршрутизации.

Удаление старых записей кэша

Операционная система IOS периодически удаляет некоторые записи из кэша. Небольшое количество записей аннулируется каждую минуту во избежание излишнего увеличения размеров кэша и повторной синхронизации кэша с таблицами маршрутизации и МAC-адресов. При наличии свободной памяти более чем 200 Кбайт процесс, отвечающий за очистку кэша (cache ager process), случайным образом аннулирует одну двадцатую всех записей. Если же свободной памяти осталось меньше 200 Кбайт, то указанный процесс начинает более агрессивно удалять записи: одна пятая всех записей кэша аннулируется каждую минуту.

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

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

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

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

Экспресс-продвижение Cisco Express Forwarding — CEF

http://xgu.ru/wiki/Cisco_Express_Forwarding

Экспресс-пересылка корпорации Cisco (Cisco Express Forwarding — CEF) — это наиболее современный и быстрый метод коммутации, реализованный в операционной системе IOS. Изначально он был разработан для того, чтобы преодолеть основные недостатки метода быстрой коммутации. Возвращаясь к описанию метода быстрой коммутации, обратим внимание на его основные недостатки, которые перечислены ниже:

• • Недостаточная поддержка перекрывающихся записей кэша.

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

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

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

Большинство из этих недостатков не создают проблем в корпоративных сетях среднего размера, потому что маршруты изменяются достаточно редко и таблица маршрутизации не очень велика. Однако существует область, в которой перечисленные ограничения приводят к появлению проблем, а именно: Backbon Internet и магистральные каналы.

Маршрутизаторы, работающие на Backbon internet, поддерживают огромные таблицы маршрутизации (порядка 56000 маршрутов на начало 1999 года), и количество маршрутов постоянно увеличивается. Некоторые маршрутизаторы на backbon содержат более 100000 записей в таблице маршрутизации. Кроме того, таблица маршрутизации постоянно изменяется, что приводит к частому аннулированию записей кэша. На практике записи аннулируются с такой скоростью, что значительная часть трафика, проходящая через некоторые Internet-маршрутизаторы, использует метод программной коммутации. Протокол CEF разработан специально для повышения производительности маршрутизаторов в таких условиях.

Метод коммутации CEF тестировался в крупномасштабном сетевом окружении Internet. Провайдеры услуг Internet получили серию специальных образов системы IOS (прозванных “дегенеративными” образами системы IOS для провайдеров услуг Internet, или ISP Geeks images) с реализацией метода коммутации CEF для наблюдения за работой метода в экстремальных условиях. Разработанная технология показала свою жизнеспособность в условиях большой нагрузки lnternet-backbon и вскоре была встроена в операционную систему Cisco IOS, и, кроме того, стала методом коммутации, используемым по умолчанию в системе Cisco IOS версии 12.0. На текущий момент это — единственный метод коммутации, доступный на некоторых платформах, в частности в маршрутизаторах серии Cisco 12000 и коммутаторах серии Catalyst 8500.

Существует несколько типов записей для поля Address, которые можно увидеть при выполнении команды show adjacency (они перечислены ниже):

• • Кэшированная связь (cached adjacency). Для записи предопределен МАС-заголовок для следующей точки перехода на пути к получателю.

  • Запись отправки (punt). Пакет, адресованный этому адресу, для коммутации должен пройти по указанному пути.

  • Запись хост-маршрут (host-route). Данный получатель напрямую подсоединен к маршрутизатору.

  • Аннулированная запись (drop). Пакет, адресованный указанному получателю, игнорируется.

  • Неполная запись (incomplete). Не определен МАС-заголовок для данного адреса; обычно это означает, что отсутствует запись в кэше для данного адреса или ее невозможно создать (как, например, при неправильной конфигурации сети у получателя).

  • Незаполненная запись (glean). Данный получатель напрямую подключен к маршрутизатору, но для него не создан МАС-заголовок; необходимо послать запрос протокола ARP для создания заголовка.

Метод CEF и его преимущества

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

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

Разделение информации о доступности интерфейса и МАС-заголовке на две структуры дает еше одно дополнительное преимущество — таблицы, используемые при коммутации пакетов, напрямую связаны с теми ресурсами данных, из которых они создаются. Следовательно, не требуется выполнять процедуру удаления устаревших записей (aging ptbcess).

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

Балансировка нагрузки и CEF

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

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