автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Инвариантные методы анализа трафика в распределенных системах обработки информации

На правах рукописи

Гаипов Константин Эдуардович

ИНВАРИАНТНЫЕ МЕТОДЫ АНАЛИЗА ТРАФИКА В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ ОБРАБОТКИ ИНФОРМАЦИИ

Специальность 05.13.01- Системный анализ, управление и обработка информации (космические и информационные технологии)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Красноярск-2013

2 4 ОКТ 20(3

005535806

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева» г. Красноярск

Научный руководитель: кандидат технических наук

Пономарев Дмитрии Юрьевич

Официальные оппоненты: Ступина Алена Александровна,

доктор технических наук, профессор, ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева», профессор кафедры системного анализа и исследования операций.

Малинкин Виталий Борисович,

доктор технических наук, профессор, ФГБОУ ВПО «Сибирский государственный университет телекоммуникаций и информатики», профессор кафедры многоканальной связи и оптических систем.

Ведущая организация: ОАО «Научно-производственное предприятие

«Радиосвязь», г. Красноярск.

Защита состоится 15 ноября 2013 г. в 14.00 часов на заседании диссертационного совета Д 212.249.02, созданного на базе ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева» по адресу: 660014, г Красноярск, проспект имени газеты «Красноярский рабочий», 31.

С диссертацией можно ознакомиться в научной библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева.

Автореферат разослан октября 2013 г.

Ученый секретарь

диссертационного совета ''; Кузнецов Александр Алексеевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

На современном этапе технологического и социального развития общества и наряду с процессами всеобщей глобализации обработка и передача информации между различными подсистемами становится неотъемлемой частью любого сложного процесса или системы. Наряду с множеством механизмов качества обслуживания и различной природой трафика, создаваемого различного рода приложениями, совместно с протоколами формирования маршрутов в пакетных сетях, делают анализ и управление современными пакетными сетями обработки информации достаточно сложной задачей. Решению проблем, связанных с планированием трафика, посвящено большое количество работ как зарубежных, так и российских авторов: Д. Бертсекас, Р. Галлагер, JI. Клейнрок, Л. Форд, Д. Фалкерсон, Э. Майника, В.М. Вишневский, Е.А. Кучерявый, Г. Г. Яновский, А. В. Росляков, Г. П. Башарин и др.

Существующие методы анализа и оптимизации распределения трафика в сетях обработки информации основываются или полностью строятся на решении граф-комбинаторных задач различной сложности, к числу которых можно отнести: поиск деревьев минимальной стоимости (алгоритм Дейкстры, Беллмана-Форда), поиск максимального потока и минимального разреза (алгоритм Форда-Фалкерсона), поиск наикратчайших путей (алгоритм Данцига) и т.д. Недостатком существующих методов и алгоритмов анализа является невозможность оценки процессов после изменения структуры связей между элементами распределенной системы, кроме как проведения анализа заново. Низкая адаптивность граф-комбинаторных алгоритмов для анализа и оптимизации процессов при изменении структур делает эти алгоритмы неэффективными в системах управления сетями обработки информации. В связи с этим возникает необходимость в разработке инвариантного метода к анализу сложных систем обработки информации, в качестве которого можно применить тензорный анализ, позволяющий формализовать процедуру описания математической модели распределенных систем обработки информации на основе матричной алгебры. Значительный вклад в развитие тензорного анализа сложных систем внесли работы Г. Крона, М.Н. Петрова, А.Е. Петрова, A.B. Лемешко и др.

Целью работы является повышение коэффициента использования пропускной способности распределенных систем обработки информации.

Основными задачами исследования в диссертационной работе являются:

1 Разработать инвариантный метод анализа трафика для контурных моделей систем обработки информации.

2 Создать инвариантный метод анализа трафика для узловых моделей систем обработки информации.

3 Разработать инвариантный метод анализа трафика для ортогональных моделей систем обработки информации.

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

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

6 Применить полученные методы для анализа распределения трафика в мульти-сервисных сетях обработки информации.

Научная новизна

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

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

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

Практическая значимость работы

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

Методы исследования

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

Основные положения, выносимые на защиту

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

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

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

3 Узловая модель распределенной системы обработки информации для оптимизации трафика обеспечивает оптимальное распределение информационных потоков в распределённых системах обработки информации.

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

Апробация результатов

Основное содержание работы докладывалось и обсуждалось на научно-технической конференции «Инновации в условиях развития информационно-коммуникационных технологий» (Москва, 2007), VI всероссийской научно-практической конференции «Современные информационные технологии в науке, образовании и практике» (Оренбург 2007), научно-технической конференции «Современные проблемы радиоэлектроники» (Красноярск 2008, 2009, 2010, 2011, 2013), XI Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения» (Пенза 2009), международной научно-технической конференции «Современные информационные технологии» (Пенза 2009).

Публикации

По теме диссертации опубликовано 25 работ, в том числе 3 статьи из перечня ВАК. В конце автореферата приведены наиболее значимые работы.

Структура и объем диссертации

Диссертационная работа состоит из введения, четырёх глав, заключения, списка использованных источников и приложений. Основная часть работы содержит 160 страниц, 45 рисунков, 1 таблицы. Список использованных источников включает 85 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава содержит описание современных протоколов пакетных сетей и технологий, как разновидности распределенных систем обработки информации, среди которых протоколы маршрутизации IP, OSPF, BGP, MPLS, RSVP и методов обеспечения QoS. Подчеркнута важность протоколов маршрутизации для

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

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

к22

кп к2\

"ml

Кт2

hn к2п

А

D2 — F2

Рп. fm.

где

п - число источников нагрузки;

т — число каналов связи;

ку — коэффициент указывающий долю трафика, создаваемую /'-м источником, проходящего через канал у;

Д - интенсивность трафика, создаваемая /-м источником;

Fj — интенсивность трафика, проходящая черезу-й канал связи.

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

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

где F - поток, проходящий от узла / к узлу j.

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

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

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

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

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

Во второй главе на основании теории тензорного анализа сложных систем был предложен собственный метод анализа, где в качестве уравнений, описывающих поведение самого простого элемента системы (системы массового обслуживания СМО), было выбрано Я = рр или р = /Л, где р - загрузка СМО, >1 -среднее значение интенсивности поступления пакетов в СМО, ц - интенсивность обслуживания пакетов в СМО, I =1 /ц - среднее время обслуживания одного пакета.

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

матрица интенсивностей обслуживания пакетов в СМО, Т - матрица времени обслуживания.

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

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

Для ортогональной сети с N источниками и М стоками получена зависимость интенсивности прохождения трафика в каждой ветви между контурными и узловыми интенсивностями:

где N — число источников нагрузки;

¿Базисные юнщрные _ КОнтурные интенсивность, создаваемая источником и;

¿¡кпиаые ттые _ у3л0вые интенсивность, создаваемая источником п;

А]1 — матрица линейно-независимых/фундаментальных циклов;

С( — матрица линейно-независимых/фундаментальных разрезов.

В узловом методе анализа реализован метод разложения на базисные компоненты с помощью линейно-независимых разрезов, так называемых, узловых интенсивностей. Правило преобразования связывающее узловые интенсивности примитивной сети и узловые интенсивности исследуемой сети определяется следующим образом:

Л = СЛ, (3)

где Л - узловые интенсивности поступления примитивной сети;

Л - узловые интенсивности поступления исследуемой сети.

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

СГР = Р,

м -1 N I

С/ . л=1

л Базисные контурные д.Базисные узловые

(2)

где Р - узловые загрузки примитивной сети;

Р - узловые загрузки исследуемой сети.

Правило преобразования между тензорами интенсивностей обслуживания:

СМСГ=М,

где М -узловые интенсивности обслуживания примитивной сети;

М - узловые интенсивности обслуживания исследуемой сети.

Получив узловые значения М и Л, матричным методом находим значения элементов Р как М"'Л = Р; загрузки в ветвях исходной сети определяются по формуле Рееши = С'Р, значения интенсивностей поступления пакетов в каждой ветви определяются по формуле: Аветш = МРктвц.

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

С учетом (2) для ортогональной сети связь базисных узловых интенсивностей с интенсивностями в ветвях будет выглядеть как:

, N

Ветви (¡ \ \ 1 1 Базисные \<зловые »=1

Для контурного метода анализа уравнения, связывающие примитивную контурную сеть с исходной сетью, получаются благодаря введению такого понятия, как контурная интенсивность. Это можно объяснить тем, что если для каждого контура исходной сети определить контурную интенсивность, то их количество будет таковым, что линейной комбинацией контурных интенсивностей можно выразить любую интенсивность в ветви исходной сети. Для контурного метода, простейший элемент системы описывается выражением р = ¡Л, в котором / - это среднее время обслуживания одного пакета. Тогда согласно первому постулату обобщения для СеМО можно записать следующее матричное выражение Р = ТА.

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

Л = АА

>

где матрица перехода обозначена за А.

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

9

именно базисные компоненты, обозначим такую матрицу за А'. Такая замена при анализе позволит значительно сократить количество вычислений.

Р = А'ГР (4)

Т = А'тТА' (5)

После определения значения матрицы Т по формуле (5) и значение загрузок Р по формуле (4) найдем контурные интенсивности исходной сети: Л = 7*_1Р, после определения контурных интенсивностей, определяем значения интенсивностей и загрузки в ветвях исходной сети как: Л.^ =ААтнтурные и Р„тт.и - ТАт. _

Для преобразования ортогональной сети с п источниками и т приемниками, где каждый источник связан только с к,<т приемниками (/ё1..и), в контурную сеть необходимо соединить каждый приемник / со своими стоками А/.

С учетом (2) для ортогональной сети связь базисных контурных интенсивностей с интенсивностями в ветвях будет выглядеть как:

N

^Ветви контур _д] дБазисные контурные (10)

л=1

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

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

м к

1=] *=|

где ЩА.1к) - среднее число требований в системе обработки информации;

Х1к— интенсивность поступления СМО / от источника к.

Л1к. определяется согласного одному из методов анализа, в результате интенсивность в каждой ветви будет выражена через базисные контурные или узловые

компоненты. Система ограничений примет вид Âlt > 0 для каждой матрицы A„,m„„t и для всех / и к.

В четвертой главе было сделано обобщение различных вариантов применения тензорного метода для анализа сетевых технологий, используемых в системах обработки информации, на трех уровнях модели взаимодействия открытых систем: канальном, сетевом и транспортном, как основных уровней взаимодействия систем обработки информации. В качестве протоколов канального уровня были рассмотрены: HDLC и MPLS; сетевой уровень был представлен двумя протоколами: IP, OSPF; транспортный уровень представлен протоколом TCP. Каждый из этих протоколов накладывает свои ограничения и правила на прохождение трафика через объединенную сеть: одни формируют логические топологии, другие отвечают за восстановления потерянных данных.

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

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

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

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

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

Применяемый ранее математический аппарат подходил только для потоков информации с единым требованием к качеству обслуживания, тогда как в современных сетях обработки информации существуют потоки с разными требованиями к методам обслуживания. Задача будет состоять в следующем, пусть имеется сеть описываемая ориентированным графом б с 5 источниками, Б получателями, и из каждого источника передаются не один вид трафика, а К видов. Введем следующее обозначение Я^, где /' и _/ показывают номер сети источника и номер СМО, через которую проходит соответствующий поток, индекс к указывает класс трафика.

Вектор интенсивностей поступления к-го класса от источника г.

к=\_Кк Кк ■•• ли]

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

л=сл'7

На этом же этапе также учитываем, что сумма интенсивностей поступления в узле равна нулю.

Определить значение интенсивностей обслуживания в исходной сети:

М = СГМС

Определить узловые загрузки сети: Р1.=м-'Л1,

Определить загрузки в ветвях исходной сети:

Р' = р'

к ветви к '

Определить интенсивности поступления в каждой ветви, создаваемые каждым потоком в отдельности: „,„и1и =мр;,„.....,

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

^^ ветви кчасс к ^ | ее теп

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

К

р =м-|Уд

ветви класс к / . ветви класс к

к=1

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

Как видно из рисунка 2 в каждом интерфейсе теперь существуют отдельные очереди для каждого класса трафика. Согласно архитектуре дифференциального обслуживания количество классов определяется полем DSCP в заголовке IP или полем CoS в метке MPLS.

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

Основные результаты н выводы

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

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

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

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

5 Определены особенности применения разработанных методов анализа для распределения трафика в сетях обработки информации, использующих следующие протоколы обработки: MPLS, HDLC, IP, OSPF, ТСР.Особенности разработанных методов анализа позволяют повысить коэффициент использования пропускной способности сетей, функционирующих на базе этих протоколов.

Основные публикации по теме диссертации

Публикации из перечня ВАК:

1. Гаипов, К.Э. Программная система для исследования характеристик сетей обработки информации / К. Э. Гаипов, И. Г. Красницкий, Д. Ю. Пономарев // Программные продукты и системы. — 2008. — №4(84). — С. 95-98.

2. Гаипов, К.Э. Исследование возможностей применения тензорного метода анализа для управления информационными потоками в сетях на базе стека

протоколов TCP/IP / К.Э Гаипов, М.Н. Петров, Д.Ю. Пономарев, В.В. Золотухин // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф.Решетнева. - 2008. - №2(19). - С. 65-69.

3. Гаипов, К.Э., Заленская М.К. Применение тензорного метода двойственных сетей для анализа распределённых систем обработки информации [Электронный ресурс] / К.Э. Гаипов, М.К. Заленская // Современные проблемы науки и образования. - 2013. - № 4. Режим доступа: http://\vww.science-education.ru/l 10-9766

Публикации в других сборниках:

4. Гаипов, К.Э. Анализ методов организация управления трафиком в современных сетях / К. Э. Гаипов, Д. Ю. Пономарев // Инновации в условиях развития информационно-коммуникационных технологий: Материалы научно-практической конференции / Под ред. В.Г. Домрачева, С.У. Увайсова; Отв. за вып. A.B. Долматов, H.A. Иванов, Р.И. Увайсов. - М.: МИЭМ, 2007, С. 178180.

5. Гаипов, К.Э.Применение тензорного метода в решении задачи QoS маршрутизации / К. Э. Гаипов, Д. Ю. Пономарев, В.В. Золотухин // Современные информационные технологии в науке, образовании и практике. Материалы VI всероссийской научно-практической конференции (с международным участием). - Оренбург: ИПК ГОУ ОГУ, 2007, с 230-234.

6. Гаипов, К.Э. Исследование методов оптимизации QoS с применением тензорного анализа сетей / К.Э. Гаипов, A.B. Петухова //Современные проблемы радиоэлектроники: Сб. науч. тр. - Красноярск: ИПК СФУ. - 2009. - С. 183186.

7. Гаипов, К.Э. Применение тензорного метода для анализа мультисервисных сетей на базе технологии Ethernet / К.Э. Гаипов, К.А. Пешков // Современные проблемы радиоэлектроники: Сб. науч. тр. - Красноярск: ИПК СФУ. - 2009. -С. 186-189.

8. Гаипов, К.Э. Тензорный подход к решению задач TrafficEngineering в сетях MPLS / К.Э. Гаипов, Д.Ю. Пономарев, О.И. Подойницына, Е.А. Шиянов// Информационно-вычислительные технологии и их приложения: сборник трудов XI Международной научно-технической конференции. - Пенза: РИО ПГСХА. - 2009. - С. 210-215.

9. Гаипов, К.Э. Определение целевой функции для решения задачи оптимального распределения трафика тензорным методом / К.Э. Гаипов, Д.Ю. Пономарев, О.И. Подойницына, Е.А. Шиянов // Современные информационные технологии / Труды Международной научно-технической конференции. -Пенза: Пензенская государственная технологическая академия. - 2009. - №. 10.-С. 89-92.

Ю.Гаипов, К.Э. Применение тензорного метода для задачи маршрутизации в сетях Internet / К.Э. Гаипов, Д.Ю. Пономарев, О.И. Подойницына// Измерение, контроль, информатизация: материалы двенадцатой международной научно-технической конференции / Барнаул: изд-во АлтГТУ, 2011. - С. 255-259.

11.Гаипов, К.Э. Применение тензорного метода анализа для параметрической оптимизации телекоммуникационных сетей / К.Э. Гаипов, М.А. Шаян// Современные проблемы радиоэлектроники: Сб. науч. тр. - Красноярск: ИПК СФУ. - 2010. - С. 347-352.

12.Гаипов К.Э. Система динамической оптимизации параметров качества обслуживания в инфокоммуникационных сетях / К.Э. Гаипов, Е.В. Дранишников, A.C. Сидоренко // Современные проблемы радиоэлектроники: Сб. науч. тр. -Красноярск: ИПК СФУ. - 2011. - С. 539-544.

13.Гаипов, К.Э. Решение задачи управления трафиком в сетях MPLS /К.Э. Гаипов, Т.О. Пудалев, В.Ю. Сторожук. // Современные проблемы радиоэлектроники: Сб. науч. тр. - Красноярск: ИПК СФУ. - 2013. - С. 409-414.

Гаипов Константин Эдуардович Инвариантные методы анализа трафика в распределенных системах обработки информации Автореферат

Сдано в набор 14 октября 2013 г. Подписано в печать 20 октября 2013 г. Бумага офс. 80 гр./м2 Печать цифровая Тираж 100 экз. Отпечатано в типографии «Абажур» Красноярск, ул. Копылова, 76

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева»

На правах рукописи

04201364373

Гаипов Константин Эдуардович

Инвариантные методы анализа трафика в распределенных системах

обработки информации

Специальность 05.13.01- Системный анализ, управление и обработка информации (космические и информационные технологии)

Диссертация на соискание ученой степени кандидата технических наук

научный руководитель ^ канд. техн. наук Пономарев Д.Ю.

Красноярск 2013

Оглавление

Введение...........................................................................................................................4

Глава 1. Протоколы и методы управления трафиком в IP/MPLS сетях....................8

1.1 Маршрутизация в сетях на базе протокола IP........................................................8

1.2 Динамическая маршрутизация в сетях IP на базе протокола OSPF....................9

1.3 Динамическая маршрутизация в сетях IP на базе протокола BGP....................14

1.3.1 Применение протокола BGP для инжиниринга трафика.................................16

1.4 Технологии MPLS и GMPLS..................................................................................18

1.5 Методы обеспечения механизмов QoS в сетях IP...............................................22

1.6 Архитектура интегрированного обслуживания...................................................24

1.7 Архитектура дифференцированного обслуживания...........................................26

1.8 Алгоритм Token Bucket..........................................................................................32

1.9 Механизмы борьбы с перегрузками в узлах сети................................................33

1.10 Дисциплины обслуживания очередей.................................................................37

1.11 Методы анализа сетей...........................................................................................45

1.11.1 Анализ сложных систем с помощью тензорного подхода.............................48

Вывод..............................................................................................................................53

Глава 2. Применение тензорного анализа для распределенных систем обработки информации...................................................................................................................56

2.1 Типы сетей и базисы...............................................................................................63

2.1.1 Ортогональные сети.............................................................................................63

2.1.1.1 Ортогональная сеть с одним истоком и п стоками........................................63

2.1.1.2 Ортогональная сеть с N истоками и Мстоками.............................................68

2.1.2 Узловые и контурные сети..................................................................................69

2.2 Узловой метод анализа...........................................................................................70

2.2.1 Приведение ортогональных сетей к узловому виду.........................................72

2.3 Контурный метод анализа......................................................................................74

2.3.1 Приведение ортогональных сетей к контурному виду....................................77

2.4. Методы получения матриц циклов и разрезов....................................................78

Вывод..............................................................................................................................79

Глава 3. Применение тензорного метода для оптимального распределения трафика...........................................................................................................................81

3.1 Применение контурного метода анализа для оптимизации трафика в СеМО . 82

3.2 Применение узлового метода анализа для оптимизации трафика в СеМО......89

3.3 Применение метода линейно-независимых цепей для оптимизации трафика в СеМО..............................................................................................................................91

3.4 Применение тензорного анализа для оптимизации СеМО с произвольным числом входов и выходов.............................................................................................94

3.5 Применение узлового метода для оптимизации и анализа СеМО с произвольным числом входов и выходов...................................................................97

3.6 Применение контурного метода для оптимизации и анализа СеМО с произвольным числом входов и выходов.................................................................106

3.7 Применение метода линейно-независимых цепей для оптимизации и анализа СеМО с произвольным числом входов и выходов..................................................107

3.8 Применение тензорного метода для определения линейной целевой функции .......................................................................................................................................112

3.9 Физическое моделирование.................................................................................116

Вывод............................................................................................................................120

Глава 4. Применение тензорного метода для инжиниринга трафика в сетях на базе стека протоколов TCP/IP............................................................................................121

4.1 Особенности распределения трафика в пакетных сетях...................................121

4.2 Применение тензорного метода в сетях IP на базе протокола OSPF..............124

4.3 Применение тензорного метода для учета потерь при обслуживании...........130

4.4 Применение тензорного метода для анализа протоколов HDLC и TCP.........132

4.5 Применение тензорного метода для анализа трафика в мультисервисных сетях .......................................................................................................................................139

Вывод............................................................................................................................143

Заключение..................................................................................................................145

Список сокращений....................................................................................................150

Список литературы.....................................................................................................153

Введение

Актуальность темы

На современном этапе технологического и социального развития общества и наряду с процессами всеобщей глобализации обработка и передача информации между различными подсистемами становится неотъемлемой частью любого сложного процесса или системы. Наряду с множеством механизмов качества обслуживания и различной природой трафика, создаваемого различного рода приложениями, совместно с протоколами формирования маршрутов в пакетных сетях, делают анализ и управление современными пакетными сетями обработки информации достаточно сложной задачей. Решению проблем, связанных с планированием трафика, посвящено большое количество работ как зарубежных, так и российских авторов: Д. Бертсекас, Р. Галлагер, Л. Клейнрок, Л. Форд, Д. Фалькернсон, Э. Майника, В.М. Вишневский, Е.А. Кучерявый, Г. Г. Яновский, А. В. Росляков, Г. П. Башарин и др.

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

систем обработки информации на основе матричной алгебры. Значительный вклад в развитие тензорного анализа сложных систем внесли работы Г. Крона, М.Н. Петрова, А.Е. Петрова, A.B. Лемешко и др.

Целью работы является повышение коэффициента использования пропускной способности распределенных систем обработки информации.

Основными задачами исследования в диссертационной работе являются:

1 Разработать инвариантный метод анализа трафика для контурных моделей систем обработки информации.

2 Создать инвариантный метод анализа трафика для узловых моделей систем обработки информации.

3 Разработать инвариантный метод анализа трафика для ортогональных моделей систем обработки информации.

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

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

6 Применить полученные методы для анализа распределения трафика в мульти-сервисных сетях обработки информации.

Научная новизна

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

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

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

Практическая значимость работы

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

Методы исследования

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

Основные положения, выносимые на защиту

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

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

3 Узловая модель распределенной системы обработки информации для оптимизации трафика обеспечивает оптимальное распределение информационных потоков в распределённых системах обработки информации.

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

Апробация результатов

Основное содержание работы докладывалось и обсуждалось на научно-технической конференции «Инновации в условиях развития информационно-коммуникационных технологий» (Москва, 2007), VI всероссийской научно-практической конференции «Современные информационные технологии в науке, образовании и практике» (Оренбург 2007), научно-технической конференции «Современные проблемы радиоэлектроники» (Красноярск 2008, 2009, 2010, 2011, 2013), XI Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения» (Пенза 2009), международной научно-технической конференции «Современные информационные технологии» (Пенза 2009).

Глава 1. Протоколы и методы управления трафиком в IP/MPLS сетях

1.1 Маршрутизация в сетях на базе протокола IP

Протокол IP (Internet Protocol - протокол межсетевого взаимодействия) описанный в [1-11], один из основных протоколов межсетевого взаимодействия, который широко используется для маршрутизации трафика, как в локальных, так и глобальных сетях. Основным устройством в сетях IP являются устройства третьего уровня, такие как: маршрутизаторы и многоуровневые коммутаторы.

Правила распределения трафика (маршрутизация) записаны в таблицах маршрутизации, данное правило можно сформулировать, следующим образом: на IP адрес назначения, находящийся в заголовке пакета IP, накладываются маски сетей, записанных в таблице маршрутизации, в результате наложения маски сети на IP адрес получателя, получается префикс сети назначения, которому соответствует определенный выходной интерфейс маршрутизатора или IP адрес следующего транзитного перехода. В случае если в таблице маршрутизации после наложения маски на IP адрес получателя два и более префикса, то адрес следующего перехода выбирается тот, которому соответствует более длинная маска. Основным достоинством IP адресации является ее иерархичность, что позволяет сокращать маршрутные записи в маршрутизаторах, на основе записей CIDR (classless interdomain routing - бесклассовая междоменная маршрутизация).

Маршрутизация в сети Internet основана, как на статических маршрутных записях, так и на основе динамически составляемых маршрутных записей, с помощью протоколов маршрутизации. Статическая маршрутизация применяется в небольших сетях, где все маршрутные записи можно указать вручную. Динамическая маршрутизация применяется там, где ручная настройка затруднительна. При этом динамическую маршрутизацию классифицируют, как маршрутизацию внутри автономной системы (Interior Gateway Protocol (ЮР) -протоколы внутреннего шлюза) и маршрутизацию между автономными системами (Exterior Gateway Protocol (EGP)). Основной интерес из протоколов

серии ЮР представляет собой протокол OSPF (Open Shortest Path First -наикратчайший маршрут выбирается первым) [12,13], а из протоколов EGP -BGPv4 (Border Gateway Protocol version 4 - протокол граничного шлюза версии 4) [14,15]. Таким образом, маршрутизация в сети Internet является двухуровневой, вначале происходит поиск наикратчайшего маршрута между маршрутизаторами внутри автономной системы до граничного маршрутизатора, а затем происходит поиск оптимального маршрута между автономными системами. Выбор именно этих двух протоколов обусловлен тем, что они рекомендованы комитетом IETF (Internet Engineering Task Force - инженерная группа по развитию интернета) [16], как основные протоколы маршрутизации в сети Internet.

1.2 Динамическая маршрутизация в сетях IP на базе протокола OSPF

Протокол OSPF один из самых распространенных протоколов внутреннего шлюза в сети Internet. Основная версия протокола, получившая наибольшее распространение в сетях IP, описана в рекомендации [12]. В качестве алгоритма поиска наикратчайшего маршрута, принят алгоритм Дейкстры, а в качестве метрик приняты значения обратные пропускной способности, согласно RFC 2328

о

метрика определяется как отношение 10 к пропускной способности канала связи.

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

Стандартная область - все остальные области называются стандартными. С целью сокращения рассылки анонсов, и как следствие уменьшение нагрузки на процессор маршрутизатора, рекомендуемая топология для протокола OSPF имеет вид «ромашки», состоящая из опорной области в центре и тупиковых областей, соединенных с опорной областью [12,13].

Также спецификация протокола OSPF определяет несколько типов маршрутизаторов: граничный маршрутизатор области (ABR - Area Border Router), данный маршрутизатор находится на границе двух и более областей и имеет интерфейсы в каждой области; граничный маршрутизатор автономной системы (ASBR - Autonomous System Border Router) - данный тип маршрутизаторов объединяет одну из областей OSPF с другой автономной системой или с областью, где функционирует другой протокол маршрутизации.

Принцип работы протокола OSPF следующий: вначале соседние маршрутизаторы обмениваются приветственными сообщениями для определения идентификаторов маршрутизаторов, номерами и типами областей, в которой находятся маршрутизаторы, масок и IP адресов интерфейсов; если основные параметры в приветственных сообщениях протокола OSPF совпадают у двух маршрутизаторов, то они вступают в отношения соседства, затем часть соседних маршрутизатров переходит в отношение смежности, только смежные маршрутизаторы имеют право обмениваться маршрутной информацией. Затем идет обмен сообщениями о состоянии каналов, в которых каждый маршрутизатор указывает маршруты до известных ему сетей и граничных маршрутизаторов. По завершению обмена сообщени�