MODIFIED BELLMAN-FORD ALGORITHM WITH FORMING THE SHORTEST AND FALLBACK PATHS AND ITS APPLICATION FOR TELECOMMUNICATION NETWORK STABILITY IMPROVEMENT

Full Text

Задача маршрутизации в сетях телекоммуникационных систем (ТКС) является одной из приоритетных, так как ее решение напрямую влияет на устойчивое функционирование системы. Устойчивость современных ТКС напрямую зависит от времени восстановления их работоспособности после воздействия дестабилизирующих факторов (ДФ) и имеет особую актуальность для систем связи специального назначения [1]. Повышение устойчивости ТКС в условиях влияния ДФ за счет использования топологических структур с высокой избыточностью и повышения эффективности протоколов маршрутизации является актуальной прикладной задачей [2-11]. Однако в указанных работах не рассматриваются временные параметры реакции протокола маршрутизации на отказ в сети, не детализируются процессы реконфигурации маршрутов, а основное внимание уделяется топологическим аспектам устойчивости сетей. Анализ известных работ по снижению времени восстановления работоспособности ИТКС после воздействия ДФ, представленный в работе [12], показал, что существующие способы обеспечения устойчивости ТКС не позволяют гарантировать заданное время восстановления ее работоспособности. Например, недостатком способов, основанных на заблаговременном и постоянном резервировании каналов связи (КС), реализуемых в технологиях SDH, OTH, PDH является то, что они требуют дополнительной пропускной способности сети. В технологии IP/MPLS и ATM способы резервирования виртуальных соединений основаны на перераспределении пропускной способности сети, что требует дополнительного времени на перемаршрутизацию путей виртуальных соединений для восстановления работоспособности ТКС. В [12] было показано, что существующие протоколы маршрутизации основаны на поглощающих алгоритмах поиска кратчайших путей (алгоритм Дейкстры, Беллмана-Форда и др.). Это приводит к тому, что результатом использования этих алгоритмов является древовидная топология наложенной сети, по которой ведется передача трафика в ТКС. При отказах, такая древовидная топология утрачивает связность и требуется повторное применение алгоритма поиска путей, что увеличивает время восстановления работоспособности ТКС после отказа, и в конечном итоге - снижает ее устойчивость. В работах [13-] для повышения устойчивости ТКС предложен новый способ снижения времени восстановления работоспособности сети, после отказов ее элементов. Этот способ ориентирован на применение в протоколах маршрутизации основанных на алгоритме Дейкстры, которые используются в IP-сетях и сетях IP/MPLS. Данный способ основан на модификации известного алгоритма Дейкстры в следующих направлениях: - использование входящих в узлы ребер, не принадлежащих кратчайшим путям, для построения резервных путей к этим узлам; - одновременно с формированием сети кратчайших путей, сформировать сеть резервных путей, которые используются при отказах элементов ТКС; - при отказах элементов сети кратчайших путей, осуществляется переход на резервный путь с наименьшим весом, элементы которого сохранили работоспособность. Однако решение, предложенное в [13-15], актуально только для протоколов маршрутизации основанных на алгоритме Дейкстры. Вместе с тем, существует большое количество протоколов маршрутизации, основанных на алгоритме Беллмана-Форда. К ним относятся протоколы RIP, BGP, EBGP, IBGP, IGRP, EIGRP. Для этих протоколов также является актуальной разработка способа уменьшения времени восстановления работоспособности ТКС, после воздействия ДФ. В связи с этим, предлагается взять за основу направления модернизации протоколов поиска кратчайших путей, предложенные в [13-15], и применить их к алгоритму Беллмана-Форда [16]. Задачей данной работы является модификация алгоритма Беллмана-Форда, которая позволит одновременно с поиском кратчайших путей сформировать резервные пути к узлам сети. Это позволяет в протоколах маршрутизации, основанных на алгоритме Беллмана-Форда, таких как RIP, BGP, EBGP, IBGP, IGRP, EIGRP: - обеспечить использование топологической избыточности ТКС с целью повышения устойчивости ее функционирования при отказах элементов сети; - обеспечить снижение времени реакции ТКС на отказы в сети за счет включения в таблицу маршрутизации информации о резервных путях и минимизации времени перехода к использованию этих путей при отказах. Задача повышения устойчивости ТКС Устойчивость относится к одним из основных свойств ТКС. Целью работы является повышение устойчивости ТКС по показателю вероятности устойчивости информационного направления PУ [1]: (1) где Kг - коэффициент готовности информационного направления связи; Рсв - вероятность выживания информационного направления в результате влияния ДФ; Pпор - вероятность поражения элемента информационного направления ТКС с учетом реализуемых организационно-технических мер защиты. Покажем, что при допущении о том, что если вероятность поражения Рпор элемента информационного направления ТКС соответствует отказу канала связи, то добавление в таблицу маршрутизации дополнительных резервных путей повышает устойчивость ТКС по показателю (1). Коэффициент готовности Kг в (1) является параметром, учитывающим временные показатели устойчивости. В соответствии с работой [1] Kг определяется наработкой на отказ ТО и временем восстановления ТВ, которое состоит из: времени диагностики отказа Тдиагн; времени ожидания восстановления связи (удержания конфигурации сети) Тож; времени уведомления узла, ответственного за изменение конфигурации ТКС, Тувед; длительности реконфигурации ТКС, резервирования маршрутов информационных потоков и сигнализации Tрек; времени переключения информационных потоков с активного на резервные пути Tперекл: (2) Введение резервных маршрутов позволяет после диагностики отказа, не ожидая восстановления связи (Тож = 0), без уведомления управляющего узла (Тувед = 0), сразу же (Трек = 0) переключить информационные потоки на резервные информационные направления. При этом уведомление узла, ответственного за маршрутизацию в ТКС, предлагается осуществлять после переключения информационных потоков на резервные пути. Вероятность выживания одного маршрута Pсв 1 на информационном направлении из n каналов в выражении (1) будет определяться вероятностями поражения отдельных каналов связи Pпор v, v = 1…n, в составе маршрута: (3) Вероятность выживания одного основного и k резервных маршрутов (состоящих, соответственно, из nосн, n1, n2, …, nk каналов), будет определяться выражением (4) Поскольку для любого v-го канала Pпор v ≤ 1, то для любой сети Pсв 1 ≤ Pсв 1+k. Равенство в этом выражении будет иметь место при k = 1. Вероятность устойчивости PУ 1 для информационного направления в ТКС при использовании алгоритма, формирующего единственный кратчайший маршрут из n каналов, определим как (5) Вероятность устойчивости PУ 1+k для информационного направления из 1 + k маршрутов при использовании алгоритма, формирующего основной кратчайший маршрут из n каналов и k резервных маршрутов, примет вид [1]: Следовательно, при переходе от алгоритма, формирующего только один маршрут, к алгоритму, формирующему основной кратчайший маршрут из n каналов и k резервных маршрутов, происходит увеличение устойчивости для одного и того же информационного направления по показателю вероятности его устойчивости. При использовании подхода, основанного на внедрении алгоритма поиска кратчайших и резервных путей, устойчивость сети, вычисленная в соответствии с выражением (1), повышается за счет одновременного повышения показателей KГ и РВ. Выигрыш в повышении устойчивости, выраженный в процентах, составит: (7) Таким образом, для количественной оценки достижения цели повышения устойчивости ТКС будем использовать показатель устойчивости - среднесетевая вероятность связности информационного направления. А для оценки прироста эффективности по указанному показателю при переходе к использованию модифицированного алгоритма Беллмана-Форда - выражение (7). Общий подход к модификации алгоритма Беллмана-Форда В ходе модификации алгоритма Беллмана-Форда в него дополнительно вносятся изменения, направленные на расширение его функциональности, связанной с формированием резервных путей. Основой, предлагаемой модификации алгоритма Беллмана-Форда, являются следующие положения. 1. При достижении очередной вершины, запоминается предшествующая ей вершина, как потенциальный элемент будущего резервного пути к этой вершине (рис. 1). Рис. 1. Запись потенциальных элементов будущего резервного пути к вершине 2. При следующем шаге функционирования алгоритма, достигнутая очередная вершина проверяется как потенциальный элемент резервного пути для всех уже достигнутых вершин. Если она является потенциальным элементом резервного пути, формируется резервный путь к ранее достигнутой вершине через только что достигнутую (рис. 2). Сравнение [B, C, D] и [B, D] приводит к выводу, что резервные пути к А лежат через В и D. Рис. 2. Формирование резервного пути к вершине 3. Если к ранее достигнутой вершине уже были сформированы резервные пути, и она участвует в создании нового резервного пути к очередной вершине, то к очередной вершине формируется множество резервных путей с включением в них всех возможных вариантов резервных путей, сформированных ранее. Причем если в резервный путь входит сама очередная вершина, то такой путь, во избежание циклов, в резервные не включается. 4. Все резервные пути к вершинам сети упорядочиваются в соответствии с минимизацией весов и вносятся в таблицу маршрутизации наряду с кратчайшим путем (рис. 3). При отказе элементов кратчайшего пути для передачи выбирается резервный путь с минимальным суммарным весом, не содержащий отказавшие элементы. Основной путь Вес Резервный путь Вес U→A 1 U→E→D→A 4 U→K→B→A 6 U→E→K→B→A 8 Рис. 3. Пример построенных резервных путей к вершине А Модифицированный алгоритм Беллмана-Форда Схема модифицированного алгоритма Беллмана-Форда приведена на рис. 4. Для формализации стандартного алгоритма Беллмана-Форда введены следующие обозначения: G(U, V) - ориентированный граф сети; U = {Ui}, i = 1 … n - множество вершин графа G; n - количество вершин в графе; U1 - начальная вершина, от которой прокладываются пути к остальным вершинам; V(Ui, Uj) - веса ребер, соединяющих произвольные i-ую и j-ую вершины; i = 1 … n; j = 1 … n - переменные, счетчики вершин; D = {d} - множество кратчайших расстояний до вершин от начальной вершины; L = {lj}, j = 1 … n - множество кратчайших путей, которое по окончании работы алгоритма содержит кратчайшие пути к каждой вершине, при этом l i= Uj - вершина, через которую достигнута вершина Ui. Кроме того, введены дополнительные обозначения, которые используются для модификации алгоритма Беллмана-Форда в направлении расширения его функциональности: поиска кратчайших и резервных путей: R = {r} - множество вершин потенциальных резервных путей, в это множество вносятся достигнутые вершины, смежные рассматриваемой, в дальнейшем, элементы множества используются при нахождении резервных путей; C = {c} - множество весов ребер потенциальных резервных путей, в это множество вносятся веса ребер, исходящих из вершин, вносимых в множество R и входящих в рассматриваемую вершину; Z={z} - множество резервных путей в вершины, сформированные в результате проведения логических операций над входящими в него элементами и элементами множеств R и L; S = {s} - множество весов резервных путей к вершинам, это множество содержит веса путей из множества Z и используется для ранжировки резервных путей при выводе результатов работы алгоритма. К новым элементам модифицированного алгоритма Беллмана-Форда относятся блоки 7; 8; 17-22; 24. В блоках 7, 8 реализуется формирование элементов множества вершин R к текущей рассматриваемой вершине за счет использования первого положения по модификации алгоритма. Далее, в блоках 17-22, путем пересечения элементов множества R и L, а также множества Z, осуществляется формирование элементов множества Z с учетом второго положения по модификации алгоритма. В блоке 24 осуществляется ранжирование резервных путей, находящихся в множестве Z по сумме весов, входящих в их состав ребер, которые в свою очередь находятся в множестве S. Пример формирования резервного пути к вершине Рассмотрим пример функционирования модифицированного алгоритма Беллмана-Форда при решении задачи формирования кратчайших и резервных путей для сети, представленной на рис. 5, и заданной матрицей связности V. Рис. 5. К примеру функционирования модифицированного алгоритма Беллмана-Форда На начальном шаге (см. пример на рис. 5) представлен исходный граф и задана матрица V весов ребер для графа сети, а также значения элементов множеств L, R, C, D, Z, S, которые задаются в блоках 1-4 алгоритма (см. рис. 4). Рис. 4. Схема модифицированного алгоритма Беллмана-Форда На шаге 1 (при i = 1, j = 1 … n) достигаются вершины U2, U3, U4 (для которых расстояние от U1 удовлетворяют условию di ≠ ∞). При этом в элементы r2, r3, r4 множества потенциальных резервных путей R вносится смежная этим вершинам вершина U1. Одновременно в элементы с21, с31, с41 множества C вносятся веса ребер, соединяющих вершину U1 с достигнутыми вершинами U2, U3, U4 (с21 = 5, с31 = 2, с41 = 3) (блок 8 на схеме рис. 4). Значения множеств алгоритма на 1 шаге представлены в таблице 1. По аналогии с первым шагом, выполняются последующие шаги цикла (блоки 5-10 на рис. 4). Таблица 1. Значение множеств алгоритма на шаге 1 После завершения поиска кратчайших путей (блоки 5-10 на рис. 4) будут получены: L - множество кратчайших путей из вершины U1 к вершинам U2…U6; D - множество расстояний этих кратчайших путей; R - множество вершин, через которые могут быть построены потенциальные резервные пути; С - множество весов ребер, инцидентных рассматриваемой вершине. Значение элементов множеств алгоритма представлено в таблице 2. Работа модифицированного алгоритма Беллмана-Форда продолжается в блоках 13-22. Здесь производится проверка на наличие отрицательного цикла (блоки 14-16 рис. 4), формируются резервные пути к вершинам U2…U6 из вершины U1 (блоки 13, 17-22 на рис. 4). Рассмотрим работу модифицированного алгоритма Беллмана-Форда в блоках 13-24 на примере формирования резервных путей для вершины U2. Элемент множества r2 R содержит вершины U1 и U3, имеющие инцидентные вершине U2 ребра, с весами c21 = 5, c23 = 2. На данном шаге алгоритма прямой путь из вершины U1 является резервным z3 = {U1 → U2} с весом s2 = {5}, а кратчайший путь U1 → U3 → U2 имеет минимальный суммарный вес d2 = 4. Кроме U1, вершиной, через которую может быть построен резервный путь в U2, является вершина U3. Она достижима по кратчайшему пути U1 → U3, и через вершины потенциальных путей, лежащих через U1 и U5. В ходе дальнейшей работы алгоритма (цикл из блоков 13-22 на рис. 4), в резервные пути к вершине U2 добавляются резервные пути из элемента z3 - U1 → U4 → U5 → U3 и U1 → U4 → U6 → U5 → U3 идущие в U2 через вершину U3 (см. рис. 6). Эти резервные пути имеют соответственные веса c23 + s3 = 2 + 6 = 8, c23 + s3 = 2 + 10 = 12. Резервный путь в U3 через U5 z3 = {U1 → U2 → U5 → U3} не добавляется, так как он уже содержит вершину U2 (блок 18 на рис. 4). Таблица 2. Значения множеств алгоритма при полностью выполненном цикле в блоках 5-10 Таким образом, окончательные значения элементов множеств Z и S для U2 примут вид: z3 = {U1 → U2, U1 → U4 → U5 → U3, U1 → U4 → U6 → U5 → U3} и s2 = {5, 8, 12}. Рис. 6. Резервные маршруты к вершине U2 После формирования резервных путей, они ранжируются по весу. При поражении ДФ какого-либо элемента кратчайшего пути выбирается резервный путь с минимальным весом, который не содержит в своем составе пораженного элемента. Итоговые значения множеств L, R, C, D, Z, S в рассматриваемом примере приведены в таблице 3. На ней же показана схема формирования резервных путей и вычисление их веса для вершины U2, рассмотренная выше. Оценка повышения устойчивости маршрутизации в ТКС при использовании модифицированного алгоритма Беллмана-Форда Приняв допущение о заданном уровне вероятности поражения Рпор элемента информационного направления ТКС (как результат комплексного воздействия всех ДФ) и его эквивалентности отказу канала связи, покажем, что наличие в таблице маршрутизации кратчайшего и резервных путей значительно повышает устойчивость ТКС при маршрутизации трафика по заданным информационным направлениям. Выражение для устойчивости информационного направления из 1+k маршрутов (где 1 основной и k - резервные), при использовании маршрутизации на основе модифицированного алгоритма Беллмана-Форда, имеет вид (5). Оценка выигрыша по показателю Pсв, без учета временных затрат на восстановление работоспособности ТКС, произведена по формуле (8). Таблица 3. Схема формирования резервных путей из вершины U1 в вершину U2 В таблице 4 приведены значения вероятности связности информационных направлений для сети, приведенной на рис. 5 рассчитанные по формулам (4) и (5), при значении вероятности связности каждого из каналов сети Pпор v=0,1, v=1…9. Анализ значений, представленных в таблице 4, показывает, что в результате использования модифицированного алгоритма Беллмана-Форда, прирост устойчивости сети по показателю среднесетевая вероятность устойчивости информационного направления связи составил 11%. При этом есть основания утверждать, что при увеличении топологической сложности сети, количество резервных путей будет увеличиваться, и в связи с этим будет возрастать выигрыш в повышении устойчивости. Таблица 4. Значение устойчивости направлений связи и для сети в целом для примера на рис. 5 Инф. направление Алг. Беллмана-Форда Мод. алг. Беллмана-Форда Выигрыш Рсв n Рсв 1+k U1→U2 0,81 0,9973 23% U1→U3 0,9 0,9975 10% U1→U4 0,9 0,9 - U1→U5 0,81 0,9939 22% U1→U6 0,81 0,81 - В среднем по сети 0,846 0,93974 11% Заключение В работе представлен модифицированный алгоритм Беллмана-Форда с формированием кратчайших и резервных путей, который предназначен для повышения устойчивости ТКС. Повышение устойчивости происходит за счет использования топологической избыточности имеющейся сети, а также за счет снижения временных затрат, требующихся для перехода на резервные пути. Достигаемый уровень повышения устойчивости ТКС при применении представленного алгоритма прямо пропорционален топологической сложности сети и ее размеру. В отличие от [2-11], где повышение устойчивости ведется за счет использования топологических структур с высокой избыточностью и за счет повышения эффективности протоколов маршрутизации, предложенный модифицированный алгоритм Беллмана-Форда позволяет для уже имеющейся топологии сети сформировать множества как кратчайших, так и резервных путей. Это не только повышает топологическую избыточность сети без введения дополнительных каналов, но и позволяет осуществить переход на резервные маршруты сразу же после отказа, без необходимости повторной работы алгоритма поиска кратчайших путей. Наиболее близким аналогом является [13], где рассмотрена модификация алгоритма Дейкстры. Представленный в ней подход, был взят за основу при модификации алгоритма Беллмана-Форда. Представленный алгоритм может быть использован для совершенствования протоколов маршрутизации RIP, BGP, EBGP, IBGP, IGRP, EIGRP в целях обеспечения заданного уровня устойчивости ТКС, функционирующих на основе стека протоколов TCP/IP и IP-MPLS в условиях воздействия дестабилизирующих факторов на элементы сети.

About the authors

Sergey Ivanovich Makarenko

A.F. Mozhaisky Military Space Academy

Email: mak-serg@yandex.ru

Mikhail Nikolaevich Kvasov

A.F. Mozhaisky Military Space Academy

Email: kvasov_mn@mail.ru

References

Supplementary files