Классификация пакетного трафика

Материал из b4wiki
Перейти к: навигация, поиск

Содержание


Что есть "классификация пакетного трафика" и почему она заслуживает внимания?

Дело в том, что если бы маршрутизаторы занимались исключительно перенаправлением IP датаграмм, используя только IP адреса, то необходимости в изучении данного вопроса не было бы. Однако, современные пакетные сети становятся все "умнее" и требуются все более утонченные подходы при предоставлении услуг пользователям. Сейчас перед сетевыми устройствами стоит задача не просто доставить данные по принципу "best-effort", но и обеспечить вполне определенные параметры качества предоставляемой услуги. Это означает, что необходимо как-то дифференцировать сетевой трафик, чтобы можно было предоставлять дифференцированные услуги. Процесс классификации пакетного трафика как раз и заключается в определении того подмножества к которому пренадлежит классифицируемый фрейм, чтобы основаваясь на результате классификации выполнить определенное действие с пакетом. Таким действием может быть перенаправление, перенаправление с определенным приоритетом, фильтрация (актуально для firewall'ов), обновление статистики биллинговой системы и др. Задача классификации пакетного трафика не является тривиальной и требует применения специальных алгоритмов, которые характеризуются следующими параметрами:

  1. Быстродействие. К примеру, в 10G Ethernet в сетевое устройство может поступить около 15-ти миллионов пакетов в секунду (пакеты минимального размера). Соответственно, в идеальном случае, алгоритм должен быть способен обрабатывать 100% поступающего трафика при максимальной нагрузке.
  2. Используемые ресурсы. Очевидно, что классификация любой сложности может быть реализована если мы не ограничены в используемых ресурсах и их быстродействии. Однако, это является идеальным допущением, недостижимым в реальных системах.
  3. Быстрое обновление системы при изменении правил классификации и объем вносимых изменений. Здесь может быть два варианта: инкрементальная модификация (небольшое изменение) при добавлении новых правил или необходимость пересчета и обновления всех структур данных, которые участвуют в процессе классификации. Кроме того, важной является способность системы сохранять работоспособность в процессе обновления конфигурации.
  4. Масштабируемость в отношении количества полей заголовка пакета, которые используются для классфикации.
  5. Гибкость в задании правил классификации

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

Основные термины:

Поток (flow): потоком будем называть некоторое подмножество пакетов. Задача классификации сводится к определению того потока, к которому пренадлежит данный пакет. Поток формализован посредством правила (rule).

Правило (rule): каждое правило определяет поток к которому может пренадлежать пакет основываясь на некотором критерии, относящемуся к заголовку пакета.

Классификатор (classifier): совокупность (таблица) правил.

Каждое правило классификатора имеет d компонентов (d - количество полей заголовка по которым классифицируется пакет). R[i] - это i-тый компонент правила R, который является некоторым выражением применяемым к i-тому полю заголовка пакета. Говорят, что пакет P удовлетворяет правилу R если для всех i i-тое поле заголовка пакета P удовлетворяет выражению R[i].

Абстрактное выражение R[i] на практике является парой маска/адрес либо диапазоном/префиксом (конкретное значение считаем диапазоном с совпадающим началом и концом).

Примеры (для поля IP адреса):

  1. Адрес/маска : 192.168.1.144/255.255.255.248
    Данное выражение охватывает непрерывный диапазон адресов 192.168.1.144 - 192.168.1.151. Непрерывный диапазон - это частный случай, возникающий при использовании спецификации "адрес/маска". Данный пример интересен еще и тем, что маска имеет вид "111...1000...0", т.е. все значащие биты (1) расположены левее незначащих (0) и маска, таким образом, является непрерывной (конечно, в общем случае этого может и не быть). Поэтому мы можем заменить пару адрес/маска на один префикс, который в двоичном виде выглядит так: 11000000.10101000.00000001.10010***; где символ "*" означает произвольное значение. Т.е. с помощью префиксов мы можем задавать диапазоны длиной 2^t, где t = Wf - Wp = 32 - 29 = 3 ; Wf - количество бит в поле заголовка; Wp - количество бит в префиксе
  2. Диапазон: 192.168.1.144 - 192.168.1.151
  3. Конкретное значение: 192.168.1.149

Важным моментом является взаимозаменяемость способов задания что показано в нашем примере. Один диапазон мы задали тремя разными способами: парой адрес/маска, префиксом и непосредственно диапазоном. В более общем случае, любой диапазон может быть преобразован в совокупность префиксов и конкретных значений поля. Рассмотрим пример подобного преобразования для поля длиной 4 бита:
Диапазон -> Префикс
[4,7] -> 01**
[3,8] -> 0011, 01**, 1000
[1,14] -> 0001, 001*, 01**, 10**, 110*, 1110

В худшем случае W-битовый диапазон преобразуется в 2(W-1)префиксов.

Задача классификации с точки зрения вычислительной геометрии

Рассмотрим менее абстрактный пример классификатора. Предположим, что классификация выполняется на основе двух полей пакета(d=2). Соответственно, каждое правило классификатора будет содержать два компонента: 1-й задает выражение для первого поля, второй задает выражение для второго поля пекета. Т.е., выражаясь математическим языком, из всего множества значений данного поля, мы выделяем некоторое подмножество. В нашем примере мы имеем дело с двумерным пространством: каждое измерение является множеством значений соответствующего поля. Когда мы задаем правила (определяем классификатор), то тем самым на этой плоскости (плоскость, т.к. пространство двумерное) мы задаем вполне конкретные области - прямоугольники. Каждый входящий пакет, а точнее пара полей, на основе которых выполняется классификация, содержит в себе пару координат и является просто точкой на нашей плоскости.

Т.е. задача классификации представляется поиском той области (прямоугольные области определены классификатором), в которую попадает точка (координаты точки определяются полями заголовка). Это будет справедливо для любого количества полей в заголовке - только пространство будет содержать не 2 измерения (как в этом примере), а будет d-мерным, где d-количество классифицируемых полей в заголовке. Pc ex0.png Pc ex1.png

В примере (взят из статьи "Algorithms for packet classification" Pankaj Gupta & Nick Mckeown) один и тот-же классификатор задан в табличном виде и в виде плоскости с прямоугольными областями. Пакет с полями P(011, 110) попадает под правило R5.

Личные инструменты
Пространства имён

Варианты
Действия
разработки
технологии
разное
Инструменты