РАЗДЕЛ 2
РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ МНОГОПУТЕВОЙ МАРШРУТИЗАЦИИ С ОБЕСПЕЧЕНИЕМ
ГАРАНТИРОВАННОГО КАЧЕСТВА ОБСЛУЖИВАНИЯ ОДНОВРЕМЕННО ПО НЕСКОЛЬКИМ ПОКАЗАТЕЛЯМ
В соответствии с проведенным анализом требований к перспективным
технологическим решениям в области QoS ИТ ключевым моментом является реализация
многопутевой маршрутизации с возможностью обеспечения гарантированного качества
обслуживания информационного трафика одновременно по нескольким временным,
скоростным показателям, а также по показателям надежности (рис.1.8).
Необходимость в этом вызвана несовершенством существующих моделей, заложенных в
современные протоколы маршрутизации. Как следствие из этого возникла задача
разработки такой математической модели, использование которой позволит
реализовать многопутевую доставку данных, при этом объединив в рамках этой же
модели требования к разнородным показателям QoS ИТ. При этом важно, чтобы
разрабатываемая математическая модель маршрутизации имела низкую вычислительную
сложность, обеспечивала быструю сходимость и минимальные объемы создаваемого
служебного трафика.
2.1. Выбор и описание базовой модели многопутевой маршрутизации
Как показали результаты проведенного анализа основных подходов к
математическому моделированию и решению задач многопутевой маршрутизации,
наиболее распространенными из них являются графовые (графокомбинаторные) и
потоковые модели. Причем стоит отметить, что потоковые модели позволяют
одновременно с расчетом множества искомых путей формализовать решение задачи
распределения трафиков пользователей по этим путям. Кроме этого при
использовании потоковых моделей основное внимание уделяется изучению
особенностей структуры сети, что играет главную роль в повышении эффективности
вычислительных алгоритмов.
В некоторых случаях решение потоковых задач удобнее осуществлять сетевыми
методами [11,27] в терминах распределения потока на графах. Также анализ
показал, что, во-первых, потоковое моделирование по сравнению с комбинаторными
методами расчета графовых моделей ТКС позволяет получить теоретические
результаты и вычислительные алгоритмы, в которых более полно производится учет
параметров ИТ при решении задач обеспечения QoS, во-вторых, потоковые модели в
отличие от комбинаторных алгоритмов более адаптированы под решение
многополюсных и (или) многопродуктовых задач, что связано с одновременным
расчетом множества путей в сети.
Выбор базовой модели для решения задачи многопутевой маршрутизации должен
производиться исходя из следующих аспектов: во-первых, базовая модель должна
учитывать вероятностно-временные параметры сети и их взаимосвязь, во-вторых,
модель должна учитывать возможность обеспечения гарантий QoS ИТ по временным
показателям и показателям надежности, и в третьих, модель должна быть
достаточно информативна и поддерживать возможность дальнейшего
усовершенствования.
Наиболее успешной из всех проанализированных потоковых моделей МПМ является
модель, предложенная Галлагером [7,60,26,28,57]. Ввиду ориентации модели
Галлагера на формализацию процессов маршрутизации статического или
квазистатического трафика в работах [19, 40, 71] предложено развитие данной
модели и ее адаптация под требования концепции TE, но без учета условий QoS. В
свою очередь она достаточно хорошо апробирована и послужила фундаментом многим
более результативным моделям МПМ, тем самым способствуя реализации принципов,
заложенных в концепции TE и Load-Balance Routing. Кроме этого модель Галлагера
легко адаптируется под возможные структурные изменения сети и, соответственно,
может стать основой для протоколов, ориентированных на использование в ТКС
уровня WAN. В настоящей работе модель Галлагера будет выбрана в роли базовой с
дальнейшим расширением ее функциональных возможностей путем введения
ограничений на качество обслуживания по скоростным и вероятностно-временным
показателям QoS ИТ.
При описании ТКС математическая модель должна включать в себя структурный и
функциональный аспекты. В соответствии с сетевыми методами решения потоковых
задач достаточно удобно представить структурную модель сети в терминах
распределения потока на графах. Такое представление ТКС обладает большой
степенью простоты и наглядности. Таким образом, структурная модель ТКС будет
представлена взвешенным ориентированным графом , множество вершин которого
составляют сетевые узлы, а – множество дуг, моделирующих тракты передачи данных
между узлами сети, мощность которых равна (рис.2.1). В качестве весовых
коэффициентов отдельно взятой дуги может выступать, например, пропускная
способность моделируемого тракта передачи (1/с).
Рис.2.1. Графовая модель ТКС
Следующим этапом построения математической модели является ее функциональное
описание. Для этого необходимо при разработке математических моделей
многопутевой маршрутизации с обеспечением гарантированного QoS учесть
разнообразные ограничения, накладываемые на ТКС и показатели качества
обслуживания ИТ.
Базовая модель, предложенная Галлагером, предполагает выполнение следующих 2
групп ограничений. К первой группе относится условие сохранения потока
; , (2.1)
где – интенсивность полного потока в узле i, определяемая как сумма полного
входного потока и потока, поступающего на -й узел от смежных узлов-соседей для
-го узла, (1/с);
– маршрутная переменная, численно характеризующая долю потока , протекающего из
узла по тракту ;
– интенсивность входного потока трафика, поступающего в сеть через -й узел и
адресованного -му узлу, (1/с);
– интенсивнос
- Київ+380960830922