Вычислительная техника и прикладная математика
 Скачать 0.78 Mb.
|
|
S; z = z+1; end; for j=1 to n A do begin A = a z A; z = z+1; end; end; end; где z – глобальный номер атрибутов, K – мно- жество ключевых атрибутов функциональных зависимостей, А – множество открытых атри- бутов, S – множество секретных атрибутов, Random – функция генерации случайных чисел. В итоге получаем набор функциональных зависимостей, параметры которых удовлетво- ряют описанной ранее вероятностной модели. Сходимость алгоритма. Предложенный алгоритм является сходящимся вследствие выполнения условий: 1. Количество n входных атрибутов a A является ограниченным. 2. Так как множество входных атрибутов A=(a 1 , a 2 , …, a n ) ограниченно, то и количество шагов для обработки данного множества явля- ется конечным. Расчёт временной сложности алгоритма. Под элементарной операцией будем понимать шаг алгоритма.Пусть n – количество входных атрибутов, тогда временную сложность алгорит- ма можно рассчитать следующим образом: 1) за (2n + 4) шагов (худший случай) происходит расчёт вероятностей значений пара- метров предметной области, где n - количество входных атрибутов; ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010 49 2) за lшагов происходит создание мно- жества функциональных зависимостей. Каждый такой шаг содержит 6 n операций (худший случай), необходимых для расчёта значений параметров текущей функциональной зависи- мости и заполнения массива по полученным данным: S = 6nl + 2n +4. Временная сложность алгоритма имеет порядок О(nl). Заключение. В качестве результатов проде- ланной работы можно выделить следующие: алгоритм генерации формальных пред- метные областей для проверки алгоритмов построения схем баз данных; доказана сходимость данного алгоритма; рассчитана временная сложность алго- ритма. Библиографический список 1. Баранчиков А. И., Громов А. Ю. Алгоритм построения схемы реляционной базы данных, содер- жащей атрибуты различной степени секретности // Информатика и прикладная математика. Рязанский государственный университет имени С.А. Есенина, 2008. С. 7 - 12. 2. Баранчиков А. И., Громов А. Ю. Алгоритм синтеза реляционной базы данных, учитывающий атрибуты различной степени секретности // Системы управления и информационные технологии, 2009. N3(37). С. 25 – 37. 3. Вентцель Е.С. Теория вероятностей. М.: Высшая школа; изд. 5-е, 1998. 576 с. УДК 621.317.75:519.2 В.П. Корячко, Д.А. Перепелкин, А.И. Перепелкин ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ФУНКЦИОНИРОВАНИЯ КОРПОРАТИВНЫХ СЕТЕЙ ПРИ ДИНАМИЧЕСКИХ ИЗМЕНЕНИЯХ В ИХ СТРУКТУРЕ И НАГРУЗКАХ НА ЛИНИЯХ СВЯЗИ Предложен алгоритм адаптивной ускоренной маршрутизации, повы- шающий эффективность функционирования корпоративных сетей. Ключевые слова: адаптивная ускоренная маршрутизация, динамические изменения, алгоритмы маршрутизации, корпоративные сети. Введение. Цель работы – разработка нового эффективного алгоритма поиска оптимальных маршрутов, повышающего эффективность функ- ционирования корпоративных сетей. Характер- ной тенденцией развития современных корпора- тивных сетей является усложнение функций взаимодействия между их удаленными компо- нентами. Развитие новых сетевых технологий требует обеспечения качественного обслужива- ния современного трафика. Особую роль имеет эффективная маршрутизация пакетов данных в условиях всплеска трафика, локальных пере- грузках и отказов отдельных элементов сети [1]. Ввиду сложности структур современных компьютерных сетей задача маршрутизации не решается в полной мере. В большинстве случаев это связано с маршрутизаторами, не справляю- щимися с поддержанием таблиц маршрутизации и выбором оптимальных маршрутов для данного класса трафика. Поэтому возникает задача ис- следования существующих алгоритмов маршру- тизации с целью улучшения их характеристик или создания новых алгоритмов маршрутизации. Теоретические исследования. В современ- ных корпоративных сетях для продвижения па- кетов по сети используют протоколы, выпол- няющие статическую и адаптивную (динамичес- кую) маршрутизацию. При статической маршрутизации все записи в таблице имеют неизменяемый, статический статус, что подразумевает бесконечный срок их жизни. Записи о маршрутах составляются и вво- дятся в память каждого маршрутизатора вруч- ную администратором сети. При изменении со- стояния сети администратору необходимо сроч- но отразить эти изменения в соответствующих таблицах маршрутизации, иначе может произой- ти их рассогласование, и сеть будет работать некорректно. При адаптивной маршрутизации все изме- нения конфигурации сети автоматически отра- жаются в таблицах маршрутизации благодаря протоколам маршрутизации. Эти протоколы со- бирают информацию о топологии связей в сети, что позволяет им оперативно обрабатывать все текущие изменения. 50 ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010 Протоколы адаптивной маршрутизации бы- вают распределенные и централизованные. При распределенном подходе все маршрути- заторы сети находятся в равных условиях, они вычисляют маршруты и строят собственные таб- лицы маршрутизации, работая в тесной коопера- ции друг с другом, постоянно обмениваясь ин- формацией о конфигурации сети. При централи- зованном подходе в сети существует один выде- ленный маршрутизатор, который собирает всю информацию о топологии и состоянии сети от других маршрутизаторов. На основании этих данных выделенный маршрутизатор строит таб- лицы маршрутизации для всех остальных мар- шрутизаторов сети, а затем распространяет их по сети, чтобы каждый маршрутизатор получил собственную таблицу и в дальнейшем самостоя- тельно принимал решение о продвижении каж- дого пакета [2]. Применяемые сегодня в IP-сетях протоколы маршрутизации относятся к адаптивным распре- деленным протоколам, которые, в свою очередь, делятся на две группы: • дистанционно-векторные алгоритмы (Distance Vector Algorithms, DVA); • алгоритмы состояния связей (Link State Algorithms, LSA). В дистанционно-векторных алгоритмах (DVA) каждый маршрутизатор периодически и широковещательно рассылает по сети вектор, компонентами которого являются расстояния (измеренные в той или иной метрике) от данного маршрутизатора до известных ему сетей. Полу- чив от некоторого соседа вектор расстояний (дистанций) до известных тому сетей, маршру- тизатор наращивает компоненты вектора на ве- личину расстояния от себя до данного соседа. В конце концов, каждый маршрутизатор узнает обо всех имеющихся сетях и о расстояниях до них. Выбор маршрутов к каждой сети осуществ- ляется на основании наименьшего значения мет- рики. Дистанционно-векторные алгоритмы хо- рошо работают только в небольших сетях. В больших сетях они периодически засоряют ли- нии связи интенсивным трафиком, к тому же изменения конфигурации не всегда корректно могут отрабатываться алгоритмом этого типа, так как маршрутизаторы не имеют точного представления о топологии связей в сети, а рас- полагают только косвенной информацией – век- тором расстояний. Дистанционно-векторные ал- горитмы в своей работе используют протоколы RIP, RIP 2, IGRP и EIGRP. Алгоритмы состояния связей (LSA) обеспе- чивают каждый маршрутизатор информацией, достаточной для построения точного графа свя- зей сети. Все маршрутизаторы работают на ос- новании одного и того же графа, что делает про- цесс маршрутизации более устойчивым к изме- нениям конфигурации. Выбор маршрута до не- обходимой сети осуществляется на основании наименьшего значения метрики. Служебный трафик, создаваемый протоколами LSA, гораздо менее интенсивный, чем у протоколов DVA. Протоколами, основанными на алгоритме со- стояния связей, являются протокол IS-IS и про- токол OSPF. Анализ современных алгоритмов маршрути- зации в корпоративных сетях показывает, что дистанционно-векторные алгоритмы используют в своей работе алгоритм Беллмана – Форда, трудоемкость которого составляет O(N 3 ), где N – число маршрутизаторов в корпоративной сети, а алгоритмы состояния связей базируются на алгоритме Дейкстры c трудоемкостью O(N 2 ). При изменении пропускной способности линий связи в представленных алгоритмах про- исходит полный перерасчет таблиц маршрутиза- ции. С увеличением размера корпоративной сети трудоемкость этой операции растет полиноми- нально, что не может не сказаться на производи- тельности всей сети в целом. Разработка новых, более эффективных алгоритмов адаптивной маршрутизации позволяет уменьшить трудоем- кость построения таблиц маршрутизации в кор- поративных сетях. Разработка алгоритма. Для повышения эффективности функционирования корпоратив- ных сетей предложен алгоритм адаптивной ускоренной маршрутизации, который позволяет уменьшить трудоемкость построения таблиц маршрутизации до величины O(N) в условиях динамически изменяющейся структуры сети и нагрузок на линиях связи. Представим корпоративную сеть в виде неориентированного взвешенного связного графа G = (V,E,W), где V – множество вершин, ||V|| = N, Е – множество ребер, ||E|| = M, W – множество весов ребер, показанного на рисунке. Рисунок – Граф G корпоративной сети ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010 51 Пусть на графе G в некоторый момент времени уже решена задача поиска кратчайших путей до всех вершин множества V ŝ =V\v s из начальной вершины v s , т.е. построено дерево кратчайших путей с корнем в вершине v s Обозначим это дерево как Т g . На рисунке жирными линиями обозначено построенное дерево кратчайших путей. Обозначим w i,j – вес ребра, соединяющего вершины v i и v j ; nw i,j – новое значение веса, по- лученное в результате изменения значения мет- рики линии связи. Вершина v j располагается ни- же по иерархии дерева кратчайших путей отно- сительно v i . Обозначим E T множество ребер, ка- ждый элемент которого входит, по крайней ме- ре, в один кратчайший путь из начальной вер- шины, E R – множество остальных ребер. E R E T =E, E R E T = . Обозначим V T – множест- во вершин, до которых найден кратчайший путь из начальной вершины, V R – множество осталь- ных вершин. V R V T =V, V R V T = Будем называть V k – путем R k совокупность подмножества V (Vk) V вершин, через которые проходит кратчайший путь до вершины v k из исходной вершины v s , и подмножества E (Vk) Е ребер, составляющих этот путь. Назовем V k – деревом T k совокупность подмножества V Т (Vk) V, состоящего из всех вершин, кратчайшие пути до которых из исходной вершины содержат вершину v k , и подмножества E Т (Vk) Е ребер, составляющих эти пути после v k при движении от вершины v s Обозначим множество путей до вершины v i из исходной вершины v s через i , где элемент множества i,k i будет множеством не повторяющихся ребер e i,j E, образующих вместе путь, соединяющий v s и v i . Для всех i,k i поставим в соответствие некоторое число, равное сумме весов, входящих в него ребер, т.е. длину пути d i,k D i . На множестве i задан селектор H, возвращающий кратчайший путь из множества i . В том случае, если существуют несколько путей в i с минимальной длиной, то выбирается один из них. Кратчайший путь до вершины v i будем обозначать i =H( i ), оценку длины i – d i Для разработки алгоритма адаптивной ускоренной маршрутизации в корпоративных сетях сформулируем следующие теоремы. Теорема 1. Если nw i,j >w i,j и e i,j E T , то изменению могут подвергнуться кратчайшие пути и оценки их длин для вершин V Т (Vj) Доказательство. Пусть увеличился вес ребра e i,j E T , которое входит, по крайней мере, в один кратчайший путь k , например в k,p Вершины v k , в кратчайшие пути до которых ребро e i,j не входит, будут составлять множество V Т вершин, кратчайшие пути до которых после изменения не изменятся (не изменится после- довательность ребер и величины кратчайших путей). Действительно, пусть существует крат- чайший путь k = k,p до вершины v k , и известно, что ребро e i,j не входит в этот путь. Тогда увеличение веса этого ребра со значения w i,j до nw i,j не изменит маршрута этого пути и не повлияет на его величину d k,p , т.е. k,p и d k,p , поскольку еще до увеличения веса рассмат- риваемого ребра включение этого ребра в кратчайший путь приводило к увеличению длины пути. Все вершины, не вошедшие в множество V Т , будут составлять множество V R Кратчайшие пути до вершин множества v V R станут «недействительными», т.е. невозможно будет без дополнительного расчета сказать, останутся они такими же или кратчайший путь до них не будет включать изменившееся ребро. Теорема доказана. Теорема 2. Если nw i,j < w i,j и e i,j E T , то без изменения останутся кратчайшие пути для вершин множества v V Т (Vj) V (Vi) , а для вершин множества V (Vi) неизменными останутся и оценки длин кратчайших путей. Доказательство. Пусть уменьшился вес ребра e i,j E T , входящего в кратчайший путь k = k,p до вершины v k V. Ребро e i,j после изменения также будет входить в кратчайший путь k до вершины v k . Поскольку вес ребра w i,j изменился, то измениться должны длины всех путей t,r , в которые входит это ребро. Действительно, если ребро e i,j входит в какой–либо кратчайший путь и вес этого ребра уменьшается, то это изменение не потребует изменения кратчайшего пути k,p (последовательности ребер) и длина пути d k,p изменится (уменьшится) на величину изменения веса ребра. Пути s , v s V Т (Vj) V (Vi) станут «недействительными», т. е. невозможно будет без дополнительного расчета сказать, останутся они такими же или кратчайший путь до них будет включать изменившееся ребро. Теорема доказана. Теорема 3. Если nw i,j > w i,j и e i,j E T , то исходное дерево кратчайших путей и оценки длин путей всех вершин не изменятся. Доказательство. Пусть ребро, не входящее ни в один кратчайший путь, увеличивает свой вес w i,j , e i,j E R . Никаких изменений дерева кратчайших путей при этом не происходит. Действительно, пусть ребро e i,j E входит в путь k,p до некоторой вершины v k , который не является кратчайшим для v i , – k,p k . Т.е. 52 ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010 существует такой путь k,t = k , что d k,p > d k,t Тогда после увеличения веса w i,j увеличится оценка длины d k,p и неравенство d k,p > d k,t оста- нется справедливым. Т.е. кратчайший путь и его оценка до вершины v k остается неизменной. Теорема доказана. |