Критерии маршрутизации сети

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

Ключевые слова: маршрутизация, оптимизация, метод, алгоритм маршрутизации, сети.

Реальные жизненные ситуации порождают очень сложные задачи с большим количеством условий и ограничений, так возникают многокритериальные задачи маршрутизации [1, 2]. В зависимости от применения различных критериев и наложения дополнительных условий они могут иметь совершенно разные постановки. Например, во многих задачах маршрутизации задано ограничение посещения каждого города только единожды. Сняв данное ограничение, получим новые постановки задач, требующие других подходов к решению. По-разному можно сформулировать задачи, варьируя критерии. Так, в задаче коммивояжера оба критерия можно задать минимизируемыми, а можно первый — минимизируемым, а второй — минимаксным. При рассмотрении задачи с двумя коммивояжерами возможны следующие постановки: первый критерий — это суммарная длина маршрута 1го коммивояжера; второй критерий — суммарная длина маршрута 2го коммивояжера. Здесь можем сформулировать задачи, где оба критерия минимизируемы; первый — минимизируемый, а второй — минимаксный (минимизируется максимальный из пошаговых платежей); оба критерия минимаксны и т. д. Аналогично получаем и различные постановки задач инкассации. Допустим, мы имеем одного инкассатора. Тогда в качестве первого критерия можем взять суммарную длину пройденного им маршрута, а вторым — общее количество «деньго-километров» в его пути (характеристику безопасности маршрута). Имея двух инкассаторов, получаем бикритериальную задачу инкассации, где первым критерием считаем общее количество «деньго-километров» в пути 1го инкассатора, а вторым критерием — общее количество «деньго-километров» в пути 2го инкассатора и т. д. Итак, изменяя ограничения и критерии, мы получаем различные постановки многокритериальных задач. Проблемы оптимизации маршрутизации в сети можно определить так: для заданных структур сетей и матриц спроса трафика [3, 4] требуется отыскать такое решение по тому, чтобы маршрутизировался трафик, при котором получится оптимальное QoS в сети. Важной особенностью многих проблем, возникающих в процессах принятия решений в системах планирования, управления и проектирования, является наличие нескольких показателей, по которым решения оцениваются. Рассмотренные в предыдущих разделах модели и методы в таких случаях оказываются недостаточными. В последние десятилетия значительное внимание уделяется изучению дискретных оптимизационных задач в многокритериальных постановках. При этом возникают вопросы, какие решения следует считать целесообразными (оптимально-компромиссными) и как эти решения строить. Существует ряд подходов к решению многокритериальных задач, строятся соответствующие алгоритмы. Отметим, что по имеющейся исходной информации единственное целесообразное решение многокритериальной задачи определить, как правило, невозможно. Поэтому в процессах решения многокритериальных задач существенную роль играет лицо, принимающее решения (ЛПР). Именно ЛПР определяет тип решающей процедуры и при необходимости назначает ее параметры. В случае, если найдено многоэлементное множество оптимально-компромиссных решений, ЛПР осуществляет выбор одного из них. Когда маршрутизация [2], базируется на пункте назначения пакетов, маршрутизатором идет определение выходного интерфейса, чтобы потом пересылать пакеты, основываясь на значениях метрик, которыми количественным образом идет описание дистанции до места назначения. В основном, идет присвоение отдельной аддитивной метрики каждому из каналов, потом применяют алгоритм, позволяющий определить кратчайший путь, чтобы найти оптимальные маршруты среди всех узлов сети (говорят об однометрической маршрутизации). Часто в метриках каналов указывают физический смысл, например, “задержки” или “стоимость”, но при этом их значения можно использовать впрямую для того, чтобы оптимизировать маршрутизацию, не рассматривая никакой физический смысл. То есть, на основе задания соответствующих значений метрик каналов, есть возможности косвенным образом действовать на схемы маршрутизации и, таким образом, проводить их оптимизацию.

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

Второй подход к решению многокритериальных задач заключается в построении множества эффективных оценок, чтобы по ним восстановит Парето-оптимальное решение. Пусть M — множество эффективных оценок в некоторой l критериальной задаче Z. Линейное упорядочение множества M именуется лексикографическим, если для некоторой перестановки {i₁, i₂, …, i_l} чисел 1, 2,…, L выполняется условие: в случаях, когда произвольная оценка а следует в упорядочении раньше оценки в, то либо i₁-я координата оценки а больше i1-й координаты оценки в, либо i₁-я, i₂-я, …, i_k-я координаты этих оценок соответственно совпадают, а ik+1-я координата оценки а больше i_k+1 й координаты оценки в (здесь k Є {1, 2,…, L — 1}). Оценка m из M называется крайней, если в лексикографическом упорядочении, соответствующем некоторой перестановке {i₁, i₂, …, i_L} чисел 1, 2, …, L, эта оценка стоит первой. Крайними решениями многокритериальной задачи Z будем называть решения, порождающие крайние оценки. Отметим, что для любой задачи многокритериальной дискретной оптимизации любая крайняя оценка может быть получена путем решения однокритериальной задачи, получаемой из исходной путем линейной свертки критериев с соответствующим образом подобранными коэффициентами.

Литература:

1. Агафонов А. М., Кравцова О. А., Аксенова Н. В. Применение имитационного моделирования при анализе компьютерной сети / Вестник Воронежского института высоких технологий. 2016. № 3 (18). С. 62–65.
2. Данилова А. В., Юрочкин А. Г. Разработка локальной компьютерной сети предприятия / Вестник Воронежского института высоких технологий. 2016. № 2 (17). С. 66–69.
3. Данилова А. В., Юрочкин А. Г., Шадымова О. В. Методы измерения нагрузки сети / Вестник Воронежского института высоких технологий. 2016. № 2 (17). С. 73–76.
4. Сергеев А. В., Бешер Х. И., Кузнецов В. В. Проблемы обнаружения и исправления ошибок в линиях связи / Вестник Воронежского института высоких технологий. 2016. № 4 (19). С. 22–24.