Программная реализация алгоритма Single Mixed Metric для решения задач QoS-маршрутизации

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА SINGLE MIXED METRIC ДЛЯ РЕШЕНИЯ ЗАДАЧ QOS-МАРШРУТИЗАЦИИ
Абрамкина Ольга Александровна,
аспирант, Сибирский Государственный Университет Телекоммуникаций и Информатики,
г. Новосибирск, Россия, Ключевые слова: QoS, маршрутизация,
olga_abramkina@mail. ru алгоритм, метрики, огр^чешя
Рассматривается алгоритм поиска кратчайшего пути в условиях многопутевой маршрутизации под названием Single Mixed Metrk. Данный алгоритм основан на комбинировании нескольких метрик в одну весовую функцию и имеет в своей структуре принцип ограничений, что позволяет сузить круг поиска кратчайших путей и решить MCP проблему (Multi-path-constrained problem -многопутевая задача с ограничением). Дан анализ алгоритма в условиях двух ограничений, К=2. Доказан тот факт, что при использовании метрик, независимых друг от друга, теряется часть полезной информации и может произойти ситуация, когда правильно найденный путь не удовлетворяет ограничениям. В результате анализа алгоритма произведена попытка его модификации с целью снижения трудоемкости и повышения точности принятия решений. Для повышения шансов нахождения подходящих оптимальных путей необходимо комбинировать веса пути для влияния их на область поиска. Модифицированный алгоритм Single Mixed Metrk реализован в виде программы на языке С++. Результаты моделирования нового алгоритма Single Mixed Metrk отражают показатели достигнутого качества от количества узлов в сети. Данный алгоритм позволит обеспечить передачу данных надежно, а относительно всей сети можно снизить нагрузку, обеспечить балансировку трафика, повысить отказоустойчивость. Данные показатели можно отнести к показателям качества обслуживания, QoS, и, следовательно, новый алгоритм Single Mixed Metrk является одним из решений задач QoS-маршрутизации.
Для цитирования:
Абрамкина О. А. Программная реализация алгоритма single mixed metric для решения задач QOS-маршрутизации // T-Comm: Телекоммуникации и транспорт. — 2016. — Том 10. — № 3. — С. 39−43.
For citation:
Abramkina О.А. Software implementation of the single mixed metric algorithm for solving QOS-routing. T-Comm. 2016. Vol. 10. No. 3, рр. 39−43. (in Russian)
Введение
Существует множество алгоритмов поиска кратчайшего пути как для однопутевой, так и для многопутевой маршрутизации. Остановимся на анализе алгоритма поиска кратчайшего пути по одной смешенной метрике, под названием Single Mixed Metric (SMM). Данный алгоритм выбран потому, что:
•относится к числу алгоритмов многопутевой маршрутизации-
• имеет в своей структуре принцип ограничения, что позволяет сузить круг поиска кратчайших путей и решить MCP проблему-
• имеет возможность модификации-
• имеет среднюю, относительно алгоритмов, сложность реализации, расширить спектр его использования-
• удовлетворяет требованиям QoS.
В общем случае решение задач QoS-маршрутизации заключается в анализе сети [I], представленной как направленный или ненаправленный граф G=(V, E), где V -множество узлов и Е — множество каналов. Каждый канал {?, 0е Е имеет К аддитивных неотрицательных весов,
тУ ¦& quot- Для К ограничении,
MCP (проблема поиска пути в условиях множества ограничений) проблема заключается в нахождении пути Р от источника S к узлу назначения D таком, что:
IV,
sc.
ш
(I)
Для решения задач QoS-маршрутизации рассмотрим несколько вариантов алгоритма единичной смешенной метрики, представленных ниже.
Анализ алгоритма Single Mixed Metric
с двумя ограничениями
Рассмотрим общие положения алгоритма Single Mixed Metric with Two Constraint (SMM-2C) для случая двух ограничений. Структура алгоритма описывается следующим выражением:
w (& lt-§ = ?jW, О) + d2 (е) ^ ф
где е — канал с двумя различными метриками И'-,(е) и w. ,(e) — t/, и d2 — две константы- и'-(е) — смешанная метрика, поставленная в соответствие каналу е.
Если граф имеет вес, заданный w (e), тогда путь р = (S, u,…, v, D) — есть путь с весом w (e), который можно представить в виде следующего выражения:
(3)
+[с!) (у,?& gt-) + с/2 (V, О)] =
= (Г, [№,(?,")+ …+ муО'-, Л)]+
При использовании алгоритма нахождения кратчайший пути, такого как алгоритм Дейкстры, УУ (р) сводится к минимуму. Параллельные линии на рис. 1 можно описать следующим уравнением:
щ (р)+42м& gt-2(р) = с. (4)
На рис. 1 иллюстрируются данные параллельные линии и видно, как данный метод ищет оптимальный кратчайший путь. Горизонтальная ось сопоставляется с метрикой и^. а вертикальная ось с метрикой. Задача состоит в том, чтобы найти путь Р*, такой что и& gt-,(Р*)<-С, и ы7(Р'-)& lt-Сг-Параметры С, и С, — это константы ограничения, показаны на рис. I пунктирными линиями.
& quot-'-Л/О
существующих что позволит
(я)

(Ь)
wi (p)
Рис. I. Работа алгоритма SMM-2C: (а) оптимальный путь найден- (Ь) — путь не найден
Каждый путь Р между источником S и получателем D имеет веса и *v,(/j). Поэтому каждый путь ассо-
циируется с точками на vi'-,(р) — и-'-,(р) плоскости. На
рисунке I некоторые примеры этих путей представлены черными точками. Ясно, что все точки внутри прямоугольной области являются приемлемыми путями, но оптимальным будет лишь тот, что удовлетворяет ограничениям С и обеспечивающий min & gt-v (p). Рисунок I иллюстрирует ситуацию, когда приемлемый путь лежат близко к оригиналу. Это доказывает тот факт, что при использовании Mixed Metric теряется часть полезной информации и может произойти ситуация, когда правильно найденный путь не удовлетворяет ограничениям. Для повышения шансов нахождения подходящих оптимальных путей необходимо изменять веса пути для влияния их на область поиска. Например, если d] и с/, выбирается на основе соотношения:
A = (5)
?2 С,
тогда до покидания области допустимых путей половина путей будет найдена. Также возможно определить следующий вес для пути:
Щр)=1 JuSfiit+fuiAl'-g (6)

Рис. 2. Использование квадрата смешанной метрики
T-Comm Том 10. #3−2016
Рисунок 2 показывает, как можно отыскать необходимый путь при использовании смешенного веса. Из рисунка 2 ясно, что когда мы испопьзуем возведение в квадрат в вычислении смешанного веса, для алгоритма потребуется больше времени, чтобы оставить области допустимых путей [2].
Таким образом, имеем ситуацию, когда существует больше одного и даже больше двух ограничений К& gt-2. Тогда для K-ограничений в решении задач MCP смешанная единичная метрика Wjfp) будет определяться следующим образом:
W
'-?(P)=Z (ш
(7)
м
где р — это путь, который минимизирует смешанную метрику для заданного Л & gt- 1.
Отсюда вытекает теорема I для решения МСР проблемы с двумя ограничениями при поиске пути либо от узла источника, либо от узла назначения, доказательство которой подробно описано в [3] о том, что существует хотя бы один реальный путь Р* в сети. Из доказательства понятно, что большие значения приводят к более высокой вероятности получения реальных результатов.
Предположим ситуацию, когда пути с и q соединяют узел назначения и узел источника. Путь г — допустимый путь, который удовлетворяет двум ограничениям С1 и С2, а путь q минимизирует смешанную метрику, но он не удовлетворяет ограничениям. Тогда смешанная метрика пути с и q будет иметь вид (8), (9) соответственно:
lV (t) = w](t)/Cl+w2(t)/C2i W (q) = wl (q)/Cx+w2(q)/C2
(8) (9)

С С
(П)
Алгоритм маршрутизации на основе ^^(р) найдет путь q при условии:
(12)
Теорема 2 верна для случая двух ограничений, при увеличении количества ограничений, например, К& gt-3, сни-
жается результат выполнения теоремы, т. е качество. Для повышения качества используем модифицированный алгоритм с мультиограничениями, при котором веса пути с множеством ограничений описаны следующим образом:
[ ^
А,(Р) = ±


С,
(13)
С
/
%
-Мл (Р)
(14)
Тогда для решения МСР-задач для случая с двумя ограничениями, алгоритм маршрутизации, основанный на Л/(р), находит несуществующий путь q принадлежит пр котором допустимый путь (принадлежит ж, существует при условии ???(О*Мл (я)А
Доказательство теоремы заключается в том, что если путь I — допустимый существующий путь, то он удовлетворяет следующим двум ограничениям:
Шм (10)
С, с2
С другой стороны, путь q не существует и, основываясь на теореме I в случае двух ограничений, только одно из них будет удовлетворено. Следовательно, имеем выражение:
В существующих алгоритмах маршрутизация вес для пути р базируется только на значении //, (р) ¦ Для улучшения показателей качества поиска кратчайшего пути предлагается [4] использовать совместно с /. ^(р) и параметр веса AA (p). Следовательно, новая смешанная единичная метрика (New Single Mixed Metric) будет определяться следующим образом:
СА (р) = мЛР)[ЬЛР) + г]'- (15)
где? — константа, которая лежит в пределах 0 & lt-? & lt- 1.
При использовании веса G-(p) как New Single Mixed
Metric учитываются веса fJ,(p) и Д ¦(/& gt-). Постоянный коэффициент, типа е позволяет? л, (р) оказывать непосредственное воздействие на область поиска решения. Кроме того, результат принимаемый во
внимание, имеет большие значения и от-
дельности и, следовательно, больше увеличивает значение
Константа? достигает подходящего (лучшего)
Ц& gt- (р)
значения для учета влияния в зависимости от разме-
ра сети и ее веса.
Программная реализация алгоритма
Single Mixed Metric
По вышеизложенному алгоритму написана программ на языке С++.
Работа алгоритма заключается в постоянной оценке функции-индикатора G для каждой последующей выбранной вершины и выбора среди них такой вершины, которая будет иметь наилучшие показатели. Функция G представляет собой произведение двух функций м и Д, причем константой е регулируется воздействие каждой из них на конечную функцию.
После завершения работы алгоритма результат выдает наилучший путь, но он может не являться решением, если не удовлетворяет заданным ограничениям. В этом случае это означает, что решения не существует. В программной реализации алгоритма NSMM используются следующие основные обозначения:
• SRC — source, исходная вершина-
• DEST — destination, конечная вершина-
• Lj (U, V) — j-ый вес между вершинами U и V-
¦ Wj[V] - j-ый вес выбранного пути, между вершинами источника SRC и V-
• m (V) — среднее значение функции Wj[V] среди всех значений j-
• Д — функция, соответствует значению A (V) для текущего пути р-
¦ PREVIOUS — поле значения переменной для каждой вершины для неявного создания пути р-
• PERMANENT — поле индикации уже пройденных вершин и исключения зацикливания при работе программы.
На каждом шаге алгоритма добавляется к уже найденному пути ещё одна вершина, и так до вершины назначения, тем самым увеличивается размер пути р. Сначала p={vs}, далее p={vs, vi} и так далее, в завершении будет найден общий путь p={vs, vi,…, vd}. На каждом шаге работы алгоритма определяются текущие значения переменных Wj[V], m& lt-V), Д (V).
Для оценки максимально возможных показателей качества для заданных характеристик и ограничений испопьзу-ется функция Woo (p):
Wco (p)=max{w I (р)/С I.., wk (p)/Ck}, (16)
Для нахождения функции w (p) (для k=2) при р — {S, u,…, v, D} используется формула (3). Вид программы представлен на рис. 3.
7 '-МиЙ1 tomtr. wrf QoS Routing Lhlruj «Nn* Simjtr Munt Mclric
ДОв tjat ЬЛ IrpJ CtfdlVl
JJ3JJCJ
МиЫя vi mrrfit Г
SOUHCE WSljWfTlO»: EPS UMDA
GvwttHtbxa
и
Fr
1
Ш
t01112
F f F
F F 1
F F I
F T 1
T F F
1 F T
F T F
f T 1 r T F
5 161 718 IS 20 21 22
|ft
& quot-F73 r m
-RESULTS-
СГМ7ЛМ
epj-tssr& quot-
Ii
Рис. 3. Вид программы, реализующей алгоритм New Single Mixed Metric
Главное окно программы состоит из следующих пунктов:
• Graphics — графическое представление результатов работы реализованного алгоритма. На графиках изображаются три зависимости показателей достигнутого качества от количества узлов в сети: Мах — максимально доступное качество, Mixed, I — качество достигнутое при работе алгоритма, EPS-0,4 — качество достигнутое при работе алгоритма при значении константы $ = 0,4 (рис. 4) —
• About — вывод окна информации о программе-
• Exit — выход из программы-
• Input constraints — ввод параметров и ограничений-
• Random Links — выбор типа связи между узлами (при наличии галочки в данном поле — связи являются слу-
чайными, при отсутствии — ввод связей производится вручную. Сеть связей представлена в виде матрицы, где на пересечении i-ой строки и j-oro стопбца стоит значение Т (True) в том случае если существует связь между i-ой и j-ой вершиной (i, j) и значение F (False) если связь отсутствует) —
• Number of Nodes — количество узлов моделируемой сети, 2& lt-N<-50-
• Number of weights — количество весов (К) для каждой связи, 2& lt-К<-20-
• Source — исходная вершина-
• Destination — конечная вершина-
• EPS — значение константы, с, 0& lt-е<-1-
• LAMDA — значения к, [& lt->-. <-4-
• Generate network — генерация сети, удовлетворяющей введенным параметрам-
• Start Algorithm — запуска алгоритма для сгенерированной ранее сети-
• Results — результаты работы программы: сгенерированные значения ограничений О, найденный оптимальный путь, веса данного пути wi (p) и значение функции м (р).
15 20 25 30 35 40 & lt-15 50
Generale
Close
Рис. 4. Зависимость показателей достигнутого качества от количества узлов в сети
Заключение
Рассмотрен и программно реализован алгоритм Single Mixed Metric, который позволяет решить задачу поиска кратчайших путей на графе. Решая данную задачу с двумя ограничениями, пришли к выводу, что скорость принятия решений и нахождение кратчайшего пути зависит от количества данных ограничений и методики их комбинирования.
Литература
1. Wong Z. Crowcroft ]., 1996, '-Quality-of-service routing for supporting muttimedia applications'-, IEEE Journal on Selected Area Communications, voU4, pp. 1228−1234.
2. Khadivi P., Samavi Sh, Todd Т.О., 2004. Multi-Constraint QoS Routing Using New Single Mixed Metrics'-, IEEE Communications, vol. 4, pp. 2042−2046.
3. Korkmaz Т., Krunz M, 2001, '-Multi-constrained optimal path selection& quot-, Proceedings of INFOCOM, vol. 2, pp. 834−843.
4. Chen S., Nahsted K., (998, '-An overview of quality of service routing for next-generation high-speed network: problems and solutions'-. IEEE Network, vol. 12, no 6, pp, 64−79.
5. Пышкин E.B. Структуры данных и алгоритмы: реализация на C/C++, — СПб.: ФТК СПБГПУ. 2009, — 200 с.
SOFTWARE IMPLEMENTATION OF THE SINGLE MIXED METRIC ALGORITHM
FOR SOLVING QOS-ROUTING
Olga Abramkina,
Siberian State University Of Telecommunications And Information Sciences, Novosibirsk, aspirant,
olga_abramkina@mail. ru
Abstract
Considered an algorithm for finding the shortest path in a multipath routing called Single Mixed Metris. This algorithm is based on a combination of multiple metrics in a single weighting function and has in its structure the principle of limitation, which allows narrow down the search for the shortest paths and solve of MCP-problem (Multi-path-constrained problem — multipath problems with constraints). The paper analyzes the algorithm under two constraints, K = 2. It proved that when using the metrics, independent of each other, lose some useful information and can occur a situation where the correctly found path does not satisfy the constraints. The analysis Algorithm modifications attempted to reduce complexity and improve the accuracy of decision. To increase the chances of finding appropriate path to best combine the necessary weight for path to influence them in the search area. Modified algorithm Single Mixed Metris realized in the form of a program in C ++. The simulation results of the new algorithm Single Mixed Metris reflect performance achieved quality on the number of nodes in the network. This algorithm will ensure the reliable transmission of data, and with respect to the entire network, you can reduce the load balancing to ensure traffic to increase reliability. These index can be attributed to the indicators of quality of service, QoS, and, consequently, a new algorithm Single Mixed Metris is one of the solutions of the QoS-routing.
Keywords: QoS, routing, algorithm, metrics, constraints. References
1. Wang Z., Crowcroft J., 1996, '-Quality-of-service routing for supporting multimedia applications'-, IEEE Journal on Selected Area Communications, vol. 14, pp. 1228−1234.
2. Khadivi P., Samavi Sh., Todd T.D., 2004, '-Multi-Constraint QoS Routing Using New Single Mixed Metrics'-, IEEE Communications, vol.4. pp. 2042−2046.
3. Korkmaz T., Krunz M., 2001, '-Multi-constrained optimal path selection'-, Proceedings of INFOCOM, vol. 2, pp. 834−843.
4. Chen S., Nahsted K., 1998, '-An overview of quality of service routing for next-generation high-speed network: problems and solutions'-, IEEE Network, vol. 12, no 6, pp. 64−79.
5. Pyshkin E.V., Data Structures and Algorithms: implementation in C/C ++, St. Petersburg: Institute of Computer Science and Technology, 2009, 200 p. (in Russian)

ПоказатьСвернуть
Заполнить форму текущей работой