Network traffic modeling based on the marker basket algorithm

Goryachev Aleksandr Vadimovich PhD in Technical Science Associate Professor, Department of Computer Aided Design, Ulyanov (Lenin) St. Petersburg State Electrotechnical University "LETI" 197376, Rossiya, Sankt-Peterburg, ulitsa Professora Popova, dom 5 avgoryachev@gmail.com Other publications by this author

Novakova Nataliya Evgen'evna PhD in Technical Science Associate Professor, Department of Computer-aided Design, Ulyanov (Lenin) Saint Petersburg State Electrotechnical University "LETI"  197082, Russia, g. Saint Petersburg, ul. Ul. Yakhtennaya, 35 nenovakova@gmail.com Other publications by this author

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

По своей сути практически все существующие в настоящее время сети (в том числе и Интернет) являются интегрированными, т. е. многосервисными ^[1]. Сети выполняют разные функции, состав которых, к тому же, может меняться. Меняются использующие сети приложения, а следовательно, возникают новые требования к сетевому обслуживанию. Естественно, что при создании таких многофукциональных сетей необходимо добиться приемлемого уровня сервиса для каждого приложения – приложения должны разделять используемую ими сеть так, чтобы каждое из них находилось в приемлемых для данного приложения условиях.

Широко распространенные в последнее время сетевые приложения реального времени – такие, как программы для IP-телефонии и видеоконференций – предъявляют еще более жесткие требования к качеству сетевого обслуживания. Использование сетевых ресурсов этими приложениями является нерегулярным, однако для них критичным параметром является постоянство параметров сети. Обработка всего трафика на равных условиях приводит к серьезным проблемам для таких сервисов.

Особого контроля требуют следующие параметры сети:

• пропускная способность сети;

• потери пакетов;

• задержка доставки пакетов;

• варьирование времени задержки доставки («джиттер»);

• ошибки (неверное направление, повреждение пакетов).

Таким образом, управлять сетевыми ресурсами необходимо так, чтобы гарантировать время реакции, пропускную способность и другие параметры сети. Совокупность технологий, призванных добиться этой цели, получила название Quality of Service (далее QoS) – «качество обслуживания». Используя механизмы управления трафиком, механизмы QoS назначают разный приоритет разным приложениям, пользователям или потокам данных так, чтобы добиться приемлемого уровня производительности для каждого потока данных.

Модель QoS мультиплексора. Традиционно маршрутизаторы и другое сетевое оборудование, используемое в локальных сетях и в Интернете, не поддерживали QoS. Ввиду этого оборудование было дешевле, быстрее и позволило Интернету стать популярнее, чем более сложные технологии, поддерживающие QoS (например, X.25). Интернет использовал принцип «best effort», когда все потоки данных имеют одинаковый приоритет. IP-пакеты содержат 4 бита, определяющие тип сервиса, и 3 бита приоритета, которые, однако, всегда игнорировались. Лишь с появлением IP-телефонии и IP-телевидения механизмы QoS стали использоваться шире.

В настоящее время QoS реализуется рядом протоколов, среди которых:

• IP Differentiated services (DiffServ);

• IP Integrated services (IntServ);

• Resource reSerVation Protocol (RSVP);

• Multiprotocol Label Switching (MPLS);

• IEEE 802.1p, IEEE 802.1Q, IEEE 802.11e.

Все эти технологии так или иначе задействуют механизм, называемый «Token Bucket», или маркерная корзина. Token Bucket – это, по сути, фильтр трафика. Концептуально он представляет собой «корзину» с «маркерами» («токенами») (рис. 1). Управление проходящим через маркерную корзину трафиком осуществляется на основании количества токенов в корзине.

Маркерная корзина имеет 2 параметра: размер корзины и скорость поступления токенов в нее ^[4]. Размер определяет максимально возможное число доступных токенов. Число токенов увеличивается с заданной скоростью, и при достижении максимального числа новые токены просто отбрасываются. При прохождении пакета через маркерную корзину число токенов в нем уменьшается на величину, равную размеру пакета. Если количества доступных в данный момент токенов недостаточно для передачи пакета, он либо отбрасывается, либо маркируется специальным образом (пакеты с такой отметкой отбрасываются первыми при перегрузке сети).

Маркерная корзина выполняет различные функции на различных уровнях обеспечения QoS ^[5]. Ее параметры используются для принятия решения о передаче или отклонении потоков данных путем сравнения требуемой и реальной пропускных способностей сети. Приняв поток, маркерная корзина выполняет функции шейпера, регулируя скорость поступления трафика в сеть. Если трафик нестабилен, то требуется постоянная динамическая подстройка параметров.

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

Рис. 1. Маркерная корзина

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

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

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

Для трафика с переменной скоростью определить требуемую пропускную способность гораздо сложнее: средняя скорость таких потоков данных может быть во много раз меньше пиковой. Рассмотрим подробнее моделирование этого вида трафика.

Входящий трафик определяется вектором: {T(t_k), k=0, 1, 3, …}. По сути, это случайный процесс, наблюдаемый в моменты времени tk. Результатом наблюдения является размер передаваемого пакета или фрейма T(t_k). Интервалы времени [tk–1, tk) можно принять равными и достаточно короткими для того, чтобы максимум один пакет или фрейм мог поступить на вход.

Введем обозначения для характеристик маркерной корзины:

• s – размер корзины;

• r(t_k) – скорость пополнения токенами (число токенов за отрезок времени [tk–1, tk));

• T(t_k) – поступающий на вход трафик.

В начале каждого очередного временного отрезка [t_k–1, t_k) в корзину поступает число токенов r(t_k). Результирующее число токенов в корзине ограничено ее размером s. Далее обрабатывается поступающий на вход трафик T(t_k-1). Таким образом, к моменту времени [t_k–1, t_k) весь входящий трафик обработан и фильтр переходит к следующему состоянию.

Состояние корзины в момент времени t_kопределяется количеством токенов в ней. Обозначим его a(t_k). В каждый промежуток времени [tk–1, tk) этот параметр увеличивается на:

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

где I(δ) – индикаторная функция:

Объем отброшенного на k-м интервале времени трафика равен, очевидно, разности между поступившим на вход и пропущенным трафиками:

Изменение числа токенов в маркерной корзине во времени определяется разностным уравнением:

(1)

Первое слагаемое в правой части (1) определяет число токенов в предыдущий момент времени t_k-1 , второе – число токенов, полученных в данный промежуток времени [t_k–1, t_k) , а последнее – число токенов, потраченных к моменту t_k .

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

Мультиплексор характеризуется, во-первых, максимальной длиной очереди (размером буфера) S, а во-вторых, скоростью R пересылки данных во внешнюю сеть.

Обозначим длину очереди в момент t_k как Q(tk). Значение длины очереди в начале очередного интервала времени [tk–1, tk) равно разности длины очереди в момент tk–1 и части очереди, которая освобождается на этом интервале (т. е. скорости пересылки во внешнюю сеть):

Трафик, поступающий от всех маркерных корзин на вход мультиплексора на интервале времени [t_k–1, t_k) , равен суммарному трафику, пропущенному всеми маркерными корзинами, т. е.

Рис. 2. Модель с n источниками трафика

а объем трафика, который мультиплексор в состоянии обработать, ограничен размером буфера очереди:

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

Состояние мультиплексора определяется длиной его очереди, изменение которой во времени можно выразить разностным уравнением (уравнение является разностным, так как O( t_k ) содержит Q(t_k–1):

Качество предоставляемого сетью обслуживания можно характеризовать рядом параметров [2]. Важной характеристикой является средняя пропускная способность сети. Она равна объему трафика, пропускаемого сетью в единицу времени, т. е.

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

Однако главным показателем качества сетевого обслуживания являются потери пакетов. Как было показано в ^[1], потери пакетов могут возникать как на маркерных корзинах, так и на мультиплексоре. Кроме того, существуют задержки доставки, возникающие из-за ожидания пакетов передачи в очереди мультиплексора.

Целевая функция для оптимизации трафика. Сформируем целевую функцию, учитывающую эти факторы:

(2)

Первое слагаемое в правой части выражения (2) определяет взвешенное значение суммарных потерь трафика на мультиплексоре, второе – взвешенное значение суммарных потерь на всех маркерных корзинах, а последнее – взвешенное значение сумм длин очередей мультиплексора на всем отрезке времени [t₀, t_k ]. Параметры – это веса соответствующих слагаемых.

Целевая функция зависит от управляющего вектора r=(r₁, r₂,...r_n) , определяющего значения скоростей поступления маркеров в маркерные корзины. Задача оптимизации заключается в определении такого значения вектора r, при котором значение Y(r) будет минимальным. Если в системе нет задержек, этот вектор определяется как

где первый параметр определяет входное воздействие на систему в момент t_k , а второй и третий – состояние системы в предыдущий момент времени. Вектор a(t_k-1) определяет состояние всех маркерных корзин:

Если принять во внимание временную задержку передачи и обработки данных, то при том же законе управления F управляющий вектор примет вид

где d₁ , d₂ , d₃ – число интервалов времени, за которое информация доходит до объекта управления. Очевидно, что в этом случае управление осуществляется на основе устаревшей информации и, следовательно, будет гораздо менее эффективным.

Самый простой способ определения параметров маркерных корзин – это нахождение значения r только по входному воздействию, т. е. по трафику, поступающему на маркерные корзины. Если известны статистические характеристики трафика – такие, как среднее, максимальное значения и дисперсия – значение r можно определить, исходя из них.

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

r(t_k)=T_p

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

Второй подход – использование среднего значения трафика:

r(t_k)=KT_m

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

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

Если задержка передачи и обработки данных значительна, то

где d – число отрезков времени, составляющее задержку.

Аналогично, для второй стратегии

Для системы с задержкой:

Размер окна наблюдения зависит от характеристик трафика. Выбор слишком большого размера окна приведет к использованию неактуальной информации о трафике, слишком малого – к недостатку этой информации. Существуют более эффективные способы предсказания трафика (например, ^[3]). Их рассмотрение и реализация выходят за рамки данной статьи.

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

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

(3)

где i=1, 2, ... n. .

Значение зависит от загруженности мультиплексора и определяется разностью размеров буфера очереди и самой очереди в начале соответствующего интервала времени:

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

Результирующее значение скорости пополнения маркерных корзин маркерами определяется настоящими и требуемыми значениями числа маркеров:

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

Если разным пользователям требуется назначить разные приоритеты, то выражение для пропорционального распределения пропускной способности (3) нужно модифицировать следующим образом:

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

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

Пусть d₁, d₂ , d₃ – задержки информации о трафике, маркерных корзинах и мультиплексоре соответственно. Тогда для алгоритма без приоритетов ограничение пропускной способности канала, выделяемой каждому источнику данных, равно:

где, очевидно,

Для алгоритма с приоритетами

Число (предполагаемое) требуемых маркеров

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

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

Дискретность пространства возможных решений сводит задачу к комбинаторной. Кроме того, нахождение точного глобального оптимума не является обязательным условием, в особенности учитывая его вычислительную сложность ^[6]. Таким образом, для данной задачи следует использовать метаэвристические алгоритмы Монте-Карло. В данной статье рассмотрен простой и быстрый алгоритм подъема.

Очевидно, что вероятные решения задачи оптимизации будут представлять собой векторы:

(4)

где k=0, 1, ..., K – индексы временных отрезков, на которых действует данный управляющий вектор;

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

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

Рассмотрим эволюционные алгоритмы, т.е.^[6] алгоритмы, которе основаны на операциях популяции. Они используют такие заимствованные из биологии принципы, как мутация, скрещивание, естественный отбор и выживание наиболее приспособленного для итеративного улучшения множества возможных решений ^[7]. Эволюционные алгоритмы являются метаэвристическими – они итеративно улучшают решение в соответствие с некоторой мерой качества, почти или совсем никак не учитывая сущность объекта, подлежащего оптимизации.

Эволюционные алгоритмы основываются на теории отбора и приспосабливаемости Чарльза Дарвина ^[7], абстрагируясь от биологических процессов и изменяя ее семантику. Так, область поиска эволюционного алгоритма является абстракцией множества всех возможных цепочек ДНК, а ее элементы играют роль генотипов. Поэтому G часто называют геномом, а g – генотипами. И, как любая особь в природе является отражением своего генотипа, так и элементы области возможных решений (фенотипы) являются отражениями генотипов, сформированными отображением генотип-фенотип: x=gp(g). Их приспособленности оцениваются в соответствие с целевой функцией, что направляет «эволюцию» в нужном направлении. Для оптимизации сетевого трафика были использованы 3 алгоритма: генетический алгоритм, алгоритм подъема и алгоритм поиска гармонии ^[7].

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

(5)

т.е. . Для выбранного способа записи генотипа, очевидным решением является изменение случайно выбранных элементов генов путем прибавления или вычитания из них случайным.

Оператор скрещивания предназначен для создания генотипа путем комбинирования двух существующих:

т.е. .

Варианты возможных кроссоверов приведены в ^[7].

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

solution

while not terminationCriterion()

offspring

if cost(offspring) < cost(solution)

solution

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

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

(x1, …, xhms)

for xi’ in x’

if rand(0,1) < hmcr

thenxi’

elsexi’

if rand(0,1) < par

thenxi’

if f(x’) < f(xworst)

thenxworst

В приведенном алгоритме:

• – поддерживаемая популяция решений, также называющаяся Harmony Memory (HM);

• x'– генерируемый на каждом шаге потомок;

• hms (Harmony Memory Size) – размер популяции решений;

• hmcr (Harmony Memory Considering Rate) – частота использования полученных ранее решений;

• par (Pitch Adjust Rate) – частота выбора соседнего значения;

• x^worst – худшее решение в HM.

Для реализации предложенной модели участка сети и разработанных способов ее оптимизации была выбрана платформа Microsoft .NET Framework. Имитационная модель реализована на языке C#.

Результаты моделирования. Типичный результат одного из имитационных экспериментов приведен на рис. 3.

Рис. 3. Результат имитационного эксперимента

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

В экспериментах имитировалось поведение участка сети с двумя источниками трафика и соответствующими им фильтрами token bucket.

Использовались следующие параметры элементов системы:

• параметры целевой функции

• параметры фильтров: размер – 10000, частота поступления токенов – 5000;

• параметры мультиплексора: размер буфера – 15000, частота передачи – 10000;

• фильтры имеют равный приоритет.

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

В генетическом алгоритме применялись генетические операторы инверсии, мутации и одноточечного скрещивания. Размер популяции был выбран равным 25, а число итераций – 50.

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

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

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

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