Двумерный роутер: дизайн и применение

Двумерный роутер: дизайн и  применение

Автореферат

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

С добавлением нового измерения  таблица маршрутизации экспонициально растет. Теоретически, место хранения увеличивается с О(N) (целевых префиксов) до О(N²). При использовании этого метода не возможно соответствовать TCAM (общий телекоммуникационный метод доступа). В нашей работе мы предлагаем новую структуру таблицы маршрутизации, в которой используется разделения ТСАМ и СРАМ, где в итоге мы получаем скорость первого и гибкость второго. Сначала мы разрабатываем схемы главная задача которых – поддержание корректности (обратная совместимость). Во вторых – алгоритмы для сжатия ТСАМ и хранения СРАМ. Кроме этого разрабатываем алгоритмы уменьшения перезаписи памяти во время операции обновления. Наш проект не использует новых аппаратных средств и оценка результата может быть практичен для ISPs и CERNET2.

Введение

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

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

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

Использование Cisco ACL (список управления доступом) означает, что таблица маршрутизации меняется {место назначения}à{действие} до {место назначения, исходный адресс}à{действие}. Пусть N число префиксов назначения, M – число исходных префиксов. В наихудшем случае количество входных данных ТСАМ будет О(NxM). Данное изменение увеличивает размерность на порядок. В результате ТСАМ не может содержать записи такого масштаба.

Мы разработали новую  таблицу маршрутизацию которую  назвали FIST ( FIB Structure for TwoD-IP). Суть метода разделение ТСАМ и СРАМ. СРАМ имеет большый объем памяти и потребляет меньше в 100 раз и в 10 раз дешевле. Этот метод уменьшает сложность от O(NxM) до O(N+M).

Работа в фоновом режиме

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

Стандартная структура FIB на рисунке 2а.

Большинство классификаций  реализовано на программной основе: линейный поиск древовидный поиск. Последний использует три структуры для уменьшения пространства поиска и нахождения единственного решения.

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