Критерии маршрутизации сети | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 23 ноября, печатный экземпляр отправим 27 ноября.

Опубликовать статью в журнале

Автор:

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №2 (188) январь 2018 г.

Дата публикации: 13.01.2018

Статья просмотрена: 165 раз

Библиографическое описание:

Хайитова И. И. Критерии маршрутизации сети // Молодой ученый. — 2018. — №2. — С. 6-8. — URL https://moluch.ru/archive/188/47802/ (дата обращения: 12.11.2019).



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

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

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

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

Второй подход к решению многокритериальных задач заключается в построении множества эффективных оценок, чтобы по ним восстановит Парето-оптимальное решение. Пусть M — множество эффективных оценок в некоторой l критериальной задаче Z. Линейное упорядочение множества M именуется лексикографическим, если для некоторой перестановки {i1, i2, …, il} чисел 1, 2,…, L выполняется условие: в случаях, когда произвольная оценка а следует в упорядочении раньше оценки в, то либо i1-я координата оценки а больше i1-й координаты оценки в, либо i1-я, i2-я, …, ik-я координаты этих оценок соответственно совпадают, а ik+1-я координата оценки а больше ik+1 й координаты оценки в (здесь k Є {1, 2,…, L — 1}). Оценка m из M называется крайней, если в лексикографическом упорядочении, соответствующем некоторой перестановке {i1, i2, …, iL} чисел 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.
Основные термины (генерируются автоматически): решение, задача, координата оценки, критерий, многокритериальная задача, оценка, процесс решения, путь, суммарная длина маршрута.


Похожие статьи

О системе критериального оценивания в обучении...

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

На наш взгляд, критериальная система оценивания в будущем, исключит неудовлетворительные оценки.

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

Многокритериальная динамическая задача с экспертными...

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

Динамическая адаптация эвристического алгоритма для задачи...

Решением классической задачи транспортной маршрутизации является множество маршрутов, которые начинаются и заканчиваются в депо

Разрешимость транспортной задачи по критерию времени. Многокритериальная динамическая задача с экспертными оценками.

Решение многокритериальных задач линейного...

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

Анализ существующих методов решения транспортной...

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

Анализ существующих подходов к оценке эффективности инновационного проекта в нефтегазовой отрасли.

Модели многокритериальных задач

Многокритериальная задача о раскраске на предфрактальных графах имеет широкий

В общей постановке она представляет собой процесс распределения некоторого конечного

Применение этого подхода для решения реальных задач, по-видимому, малоэффективно.

Алгоритм многокритериальной оценки технологий заготовки...

Сравнительная многокритериальная оценка производилась методом формализации...

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

Определение оценочных критериев

Решение транспортных задач с применением программирования...

- сбалансированная транспортная задача, в случае, если количество произведенной продукции равно суммарной потребности в ней

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

Похожие статьи

О системе критериального оценивания в обучении...

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

На наш взгляд, критериальная система оценивания в будущем, исключит неудовлетворительные оценки.

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

Многокритериальная динамическая задача с экспертными...

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

Динамическая адаптация эвристического алгоритма для задачи...

Решением классической задачи транспортной маршрутизации является множество маршрутов, которые начинаются и заканчиваются в депо

Разрешимость транспортной задачи по критерию времени. Многокритериальная динамическая задача с экспертными оценками.

Решение многокритериальных задач линейного...

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

Анализ существующих методов решения транспортной...

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

Анализ существующих подходов к оценке эффективности инновационного проекта в нефтегазовой отрасли.

Модели многокритериальных задач

Многокритериальная задача о раскраске на предфрактальных графах имеет широкий

В общей постановке она представляет собой процесс распределения некоторого конечного

Применение этого подхода для решения реальных задач, по-видимому, малоэффективно.

Алгоритм многокритериальной оценки технологий заготовки...

Сравнительная многокритериальная оценка производилась методом формализации...

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

Определение оценочных критериев

Решение транспортных задач с применением программирования...

- сбалансированная транспортная задача, в случае, если количество произведенной продукции равно суммарной потребности в ней

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

Задать вопрос