ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.12.2023
Просмотров: 54
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
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
остается неизменной.
Теорема доказана.
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
остается неизменной.
Теорема доказана.
1 2 3 4 5 6
Теорема 4. Если nw
i,j
< w
i,j
и e
i,j
E
T
, то без изменения останутся кратчайшие пути и оценки их длин для вершин множества V
(Vi)
Доказательство. Пусть уменьшился вес ребра e
i,j
E
R
, которое не входит ни в один кратчайший путь. Допустим, что это ребро входит в путь
i,k
i
и
j,p
j
. Если изменившееся ребро e
i,j
не уменьшает оценок обеих инцидентных ему вершин v
i
и v
j
, т.е. d
i,k
d
i
и d
j,p
d
j
, дерево кратчайших путей не изменится.
Действительно, рассматриваемое ребро оказывает влияние, прежде всего на инцидентные ему вершины множества V. Если включение ребра e
i,j
в дерево не уменьшает оценок пути d
i
, d
j
, то такое включение только увеличит оценки вершин. Т.к. существовавшие до изменения пути до этих вершин имели меньшую длину, то данное ребро не включается в дерево кратчайших путей. Если включение этого ребра приводит к уменьшению оценки какой-либо из инцидентных вершин, например
v
i
, то эта оценка d
i,k
будет оценкой кратчайшего пути до вершины v
i
, и ребро e
i,j
войдет в искомое дерево кратчайших путей. Это происходит в силу того, что после изменения не существует иного кратчайшего пути
i
до вершины v
i
, кроме пути
i,k
, содержащего ребро
e
i,j
Этот кратчайший путь
i,k
не будет существовать, если не будет кратчайших путей до всех промежуточных вершин v
p
V
(Vi)
этого пути.
Кратчайшие пути до остальных вершин графа станут «недействительными», т. е. невозможно будет сказать, останутся они такими же или кратчайший путь до них будет включать изменившееся ребро. Теорема доказана.
Теорема 5. Если nw
i,j
> w
i,j
и e
i,j
E
T
и
nw
i,j
> nw
i,j
t
(точки вхождения в дерево), то изменению могут подвергнуться кратчайшие пути и оценки их длин для вершин V
Т
(Vj)
и новые кратчайшие пути к этим вершинам будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.
Доказательство. Пусть увеличился вес ребра e
i,j
E
T
, которое входит, по крайней мере, в один кратчайший путь
k
, например в
k,p
Согласно теореме 1 вершины v
k
, в кратчайшие пути до которых ребро e
i,j
не входит, будут составлять множество V
Т
вершин, кратчайшие пути до которых после изменения не изменятся
(не изменится последовательность ребер и величины кратчайших путей). Для вершин V
Т
(Vj)
среди парных переходов соответствующих этим вершинам будут находиться ребра, имеющие минимальную длину пути к этим вершинам.
Теорема доказана.
Следствие. При увеличении веса ребра, входящего в дерево кратчайших путей для вершин V
Т
(Vj)
, маршрутная степень которых больше двух, новые кратчайшие пути будут проходить через ребра, состоящие в отношении парного перехода к ребрам, входящим в исходный граф.
Теорема 6. Если nw
i,j
< w
i,j
и e
i,j
E
T
и новое значение nw
i,j
< nw
i,j
t
(точки вхождения в дерево), то новые кратчайшие пути к вершинам множества v
V
Т
(Vj)
V
(Vi)
будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.
Доказательство. Пусть уменьшился вес ребра e
i,j
E
R
, которое не входит ни в один кратчайший путь. Согласно с теоремой 4 без изменения останутся кратчайшие пути и оценки их длин для вершин множества V
(Vi)
. Т.к nw
i,j
<
nw
i,j
, то включение этого ребра приводит к уменьшению оценки какой-либо из инцидент- ных вершин, например v
i
, и эта оценка d
i,k
будет оценкой кратчайшего пути до вершины v
i
, и ребро e
i,j
войдет в искомое дерево кратчайших путей. Это происходит в силу того, что после изменения не существует иного кратчайшего пути
i
до вершины v
i
, кроме пути
i,k
, содержащего ребро e
i,j
. Этот кратчайший путь
i,k
не будет существовать, если не будет кратчайших путей до всех промежуточных вершин v
p
V
(Vi)
этого пути. Теорема доказана.
Следствие. При уменьшении веса ребра, не входящего в дерево кратчайших путей для вершин V
Т
(Vj)
V
(Vi)
, маршрутная степень которых больше двух, новые кратчайшие пути будут проходить через ребра, состоящие в отношении парного перехода к ребрам, вхо- дящим в исходный граф.
Использование доказанных выше теорем позволяет разработать алгоритм, уменьшающий размерность задачи поиска кратчайших путей в условиях, когда пропускная способность линий связи и структура сети динамически меняется.
Каждую вершину в алгоритме будет описывать структура данных VERTEX. Данная структура содержит индекс, равный индексу соответствующей вершины v
i
; указатель на родительскую вершину v i
.p (для корневой вершины он будет содержать null v i
.p=null), оценку длины оптимального маршрута v i
.d и массив указателей на потомков по иерархии v i
.c j
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
53
(для вершин–листьев он пустой). Полученное в процессе работы алгоритма дерево T будет представлять собой массив объектов типа
VERTEX. Вершина v i
, i = 1..||V||, T.vs – начальная вершина. Каждое ребро графа G описывается структурой, которая определяется весом ребра e i
.w и указателями на инцидентные вершины e i
.v1, e i
.v2.
Для поиска оптимальных маршрутов будем применять алгоритм Дейкстры.
//Алгоритм Дейкстры. T – структура данных дерева оптимальных маршрутов, V – множество вершин графа, vs – начальная вершина.
DeicstraAlg(T,V,vs)
1.
Initialize(V,vs)
2.
Q.add(V,vs)
3.
Пока Q
4. vm = Extract-Min(Q);
5.
T.add(vm);
6.
Для всех инцидентных vm ребер vk
7.
Если d[vm.i]>d[vk.i]+w(vk,vm) то
8. d[vm.i] = d[vk.i] + w(vk,vm);
9. p[vm.i] = vk;
Конец Если
Конец Для
Конец Пока
Конец
В приведенной процедуре используется функция Extract – Min, возвращающая объект с минимальным ключом. Реализация данной функции и ее трудоемкость зависят от способа определения списка (очереди). Алгоритм вычис- ляет значения массивов d и p оценок длин оптимальных маршрутов и указателей на роди- тельские таблицы соответственно. Полученные массивы необходимо сохранить.
// Процедура сохранения массивов
SaveAr(v,i)
1.
Если i=0 то
2. v.d1:=d;
3. v.p1:=p;
Иначе
4. v.d2:=d;
5. v.p2:=p;
Конец Если
Конец
Для ребер, участвующих в построении опти- мальных маршрутов, является целесообразным проводить расчет для инцидентных вершин, лежащих ниже по иерархии.
// Процедура нахождения деревьев оптимальных маршрутов для всех вершин графа
GetSPT(T,V,vs)
1.
Q.Add(vs)
2.
Пока Q
3. v:=Q.Get
4.
Для всех v.ci
5.
Q.Add(v.ci.v2)
Конец Для
6.
Если v<>vs то
7. e:=E(v,v.p)
8. tw:=e.w;
9. e.w:=0;
10.
DeicstraAlg(T,V,v)
11.
SaveAr(v,0)
12. e.w:=M
13.
DeicstraAlg(T,V,v)
14.
SaveAr(v,1)
Конец Если
Конец Пока
Конец
В приведенной процедуре М – число, принятое за максимальное в данной системе.
Процедура нахождения деревьев оптимальных маршрутов для графа обходит все вершины графа с формированием списков парных пере- ходов для каждой вершины.
От дерева оптимальных маршрутов из заданной вершины легко перейти к списку парных переходов. Оценки длин оптимальных маршрутов в данном случае будут соответст- вовать приращениям потенциала этой вершины.
При поиске оптимального маршрута особой обработки, как было сказано выше, заслуживает вариант уменьшения веса ребра, не входящего в оптимальный маршрут. В этом случае необхо- димо предварительно проверить вершины, лежа- щие выше по иерархии.
// Процедура проверки на включение в поддере- во вершины v вершин, лежащих выше по иерар- хии относительно вершины v
TestUp(v)
1. v2:=v.P
2.
Пока v2.d>v.d+E(v,v2)
3. v2.d:= v.d+E(v,v2)
4.
Для всех v2.Ci
5.
Если v2.Ci<>v то
6. v2.Ci.d:=v2.d+E(v2,v2.Ci)
Конец Если
Конец Для
7. v:=v2;
8. v2:=v2.P;
Конец Пока
Конец
Для проверки срабатывания парного пере- хода используется условие целесообразности включения ребра в дерево. Отдельно обраба- тываются случаи увеличения и уменьшения оценки длины оптимального маршрута.
// Процедура обработки изменения веса ребра будет выглядеть следующим образом:
PathPT(e,nw)
54
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
1. v1=e.v1 2. v2=e.v2 3.
Если v1.d>e.v2 то
4. v1=e.v2 5. v2=e.v1
Конец Если
6.
Если nw>e.w то
7. dt:=v2.d2 8. pt:=v2.p2 9.
Если not e.InTree то
10.
TestUp(v2)
Конец Если
Иначе
11. dt:=v2.d
12. pt:=v2.p
Конец Если
13.
Q.Add(vs)
14.
Пока Q
15. v:=Q.Get
16.
Для всех v.ci
17.
Q.Add(v.ci.v2)
Конец Для
18.
Если v<>vs то
19. Если v.p.d+E(v.p,v).w>pt[v.i].d+E(pt[v.i],v) то
20. v.p:= pt[v.i]
21. v.d:= pt[v.i].d+E(pt[v.i],v)
Конец Если
Конец Если
Конец Пока
Конец
Рассмотрим работу алгоритма адаптивной ускоренной маршрутизации. Укрупненная схема алгоритма имеет следующий вид.
Шаг 1. Для вершины, являющейся листом дере- ва, производится поиск всех парных переходов без ограничений. Эти списки для удобства дальнейшей работы привязываются к вершине, инцидентной рассматриваемому ребру и распо- ложенной ниже по иерархии.
Шаг 2. Если вершина не является листом дерева, то вычисляются парные переходы для этой вершины и выбираются лучшие значения потен- циалов парных переходов для потомков верши- ны и собственных парных переходов. Подобная процедура выполняется для формирования спис- ков парных переходов в случае увеличения и уменьшения веса ребра.
Шаг 3. Для каждой вершины формируется пол- ный список парных переходов. Число элементов в каждом их этих списков не превышает коли- чества вершин графа. Такое решение позволяет отказаться от предварительной сортировки по- тенциалов или приращений для парных пере- ходов без значительного усложнения алгоритма обработки изменения.
Шаг 4. Для каждой вершины формируется пол- ный список возможных маршрутов, проходящий через ребра, состоящие в отношении парного перехода, включая и ребра, входящие в дерево кратчайших путей.
Шаг 5. Анализируя полученную используемым протоколом маршрутизации информацию, опре- делить, произошло ли изменение метрики для какого-либо ребра: а) если да, то перейти к шагу 6; б) иначе - к шагу 5.
Шаг 6. Используя список парных переходов, определить, требуется ли сделать парный пере- ход: а) если да, то перейти к шагу 7; б) иначе – к шагу 9.
Шаг 7. Для каждой вершины, у которой в список возможных маршрутов входит ребро с изменив- шейся метрикой, определить путь минимальной длины и поместить его в дерево кратчайших путей, тем самым, построив новое дерево кратчайших путей на графе.
Шаг 8. а) передать пакеты по доступным эквивалентным маршрутам; б) установить флаг передачи.
Шаг 9. Пересчитать точки вхождения в дерево и переформировать список маршрутов замены для каждой изменившейся вершины.
Шаг 10. Перейти к шагу 5.
Работа составных частей алгоритма основы- вается на использовании доказанных выше теорем, следовательно, можно сделать вывод о корректности работы всего алгоритма в целом.
Проведем анализ сложности алгоритма адаптивной ускоренной маршрутизации, для чего найдем верхнюю и нижнюю оценки его трудоемкости. Для этого определим оценки для процедур, составляющих алгоритм. Для всех процедур было найдено количество повторений каждого шага и стоимость для верхней и нижней оценок трудоемкости. Трудоемкость модифици- рованного алгоритма Дейкстры составляет:
(N
2
log
2
N).
Результаты анализа трудоемкости остальных процедур сведены в таблицах 1 – 3.
Таблица 1 – Трудоемкость процедуры SaveAr
Верхняя оценка трудоемкости процедуры
SaveAr:
= 1 + 1 + 1 = 3, а нижняя оценка:
= 1 + 1 + 1 = 3.
№ шага п/п
(N)
(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
0 1
3 1
1 0
1 4
0 1
1 1
5 0
1 1
1
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
55
Таблица 2 – Трудоемкость процедуры GetSPT
Верхняя оценка трудоемкости процедуры
GetSPT:
= 15N + 2N
2
log
2
N + 1,
а нижняя оценка:
= 15N + 2N
2
log
2
N + 1.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости по- строения дерева кратчайших путей и получения дополнительной информации:
(N
2
log
2
N) и нижнюю оценку:
(N
2
log
2
N).
Тогда трудоемкость процедуры PathPT запи- шется следующим образом:
Верхняя оценка трудоемкости процедуры
PathPT:
= 10 + 5N + 3(N - 1) + 6N + 2 = 14N + 9, а нижняя оценка:
=8 + 5N + N – 1 = 6N + 7
Таким образом, удается рассчитать дерево кратчайших путей за линейное время в худшем случаи. Такой результат удается получить путем использования дополнительной информации о парных переходах.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости:
(N)
и нижнюю оценку:
(N).
Таким образом, разработанный алгоритм адаптивной ускоренной маршрутизации позво- ляет повысить эффективность функциониро- вания корпоративных сетей.
Таблица 3 – Трудоемкость процедуры PathPT
Заключение. Разработка алгоритма адап- тивной ускоренной маршрутизации позволяет повысить эффективность функционирования корпоративных сетей за счет уменьшения трудоемкости построения таблиц маршрути- зации до величины порядка O(N) в условиях динамически изменяющейся структуры корпора- тивной сети и характеристик линий связи.
Библиографический список
1. Куракин Д.В. Маршрутизаторы для глобаль- ных телекоммуникационных сетей и реализуемые в них алгоритмы // Информационные технологии.–
1996. №2.
2. Олифер В.Г., Олифер Н.А. Основы компью- терных сетей – СПб.: Питер, 2009. – 352 с.
№ шага п/п
(N)
(N)
Число повто- рений
Цена
Число повто- рений
Цена
1 1
1 1
1 2
N
1
N
1 3
N
1
N
1 4
N
1
N
1 5
N
1
N
1 6
N
1
N
1 7
N
1
N
1 8
N
1
N
1 9
N
1
N
1 10
N
Nlog
2
N
N
Nlog
2
N
11
N
3
N
3 12
N
1
N
1 13
N
Nlog
2
N
N
Nlog
2
N
14
N
3
N
3
№ шага п/п
(N)
(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
1 1
3 1
1 1
1 4
1 1
0 1
5 1
1 0
1 6
1 1
1 1
7 1
1 0
1 8
1 1
0 1
9 1
1 1
1 10 1
6N+2 0
1 11 0
1 1
1 12 0
1 1
1 13 1
1 1
1 14
N
1
N
1 15
N
1
N
1 16
N
1
N
1 17
N
1
N
1 18
N
1
N
1 19
N-1 1
N-1 1
20
N-1 1
0 1
21
N-1 1
0 1
56
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
УДК 519.718
В.В. Тарасов, Н.В. Елкина
К ЗАДАЧЕ КОНТРОЛЯ ВХОДНОЙ ИНФОРМАЦИИ НА СХЕМАХ
ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ С ЗАДЕРЖКАМИ
Рассмотрена задача контроля входной информации на схемах из функ-
циональных элементов в базисе
z
,
,
&,
, где
z – тождественная функция
с задержками.
Ключевые слова: функции алгебры логики с задержками, надежность и
контроль, схемотехника.
Введение. В исследованиях [1-5] по теории функций алгебры логики (ФАЛ) с задержками основной задачей являлось изучение методов синтеза вычислительных устройств на предмет быстродействия. Цель статьи: рассмотрение задачи контроля входной информации на схемах из функциональных элементов в базисе
,
&,
с добавлением к базису элемента, реализующего тождественную функцию
z с задержками, диф- ференцированными по входу. Пусть t – момент времени подачи сигнала (нуля или единицы) на вход элемента
z , тогда на выходе этот сигнал появляется в момент времени
t
, где
1
при подаче на вход нуля и
2
при подаче на вход единицы. Положим для определенности
2 1
. Под ФАЛ с задержками будем понимать пару функций
n
n
x
x
x
x
f
,...,
,
,...,
1 1
, где при одновременной подаче значений переменных
1 1
x
, …,
n
n
x
на входы ФАЛ
n
x
x
f
,...,
1
на выходе получаем значение
n
f
,...,
1
с временной внутренней задержкой
0
,...,
1
n
,
R
. ФАЛ с задержками
n
x
x
f
,
,...,
1
n
x
x ,...,
1
существенно зависит от переменной
i
x , если существует пара соседних наборов по переменной
i
x :
n
i
i
,...,
,
0
,
,...,
1 1
1
и
n
i
i
,...,
,
1
,
,...,
1 1
1
такие, что
f
f
либо
, в противном случае переменная
i
x называется фиктивной.
При добавлении или изъятии фиктивных переменных у ФАЛ с задержками получив- шиеся функции не считаются равными.
Причиной этого служит следующий важный пример. Рассмотрим схему
y
x
S
,
(см. рисунок
1), реализующую функцию
x
, где вход
y
является фиктивным с традиционно функ- циональной точки зрения.
&
x
y
1 2 3 4 5 6
Теорема 4. Если nw
i,j
< w
i,j
и e
i,j
E
T
, то без изменения останутся кратчайшие пути и оценки их длин для вершин множества V
(Vi)
Доказательство. Пусть уменьшился вес ребра e
i,j
E
R
, которое не входит ни в один кратчайший путь. Допустим, что это ребро входит в путь
i,k
i
и
j,p
j
. Если изменившееся ребро e
i,j
не уменьшает оценок обеих инцидентных ему вершин v
i
и v
j
, т.е. d
i,k
d
i
и d
j,p
d
j
, дерево кратчайших путей не изменится.
Действительно, рассматриваемое ребро оказывает влияние, прежде всего на инцидентные ему вершины множества V. Если включение ребра e
i,j
в дерево не уменьшает оценок пути d
i
, d
j
, то такое включение только увеличит оценки вершин. Т.к. существовавшие до изменения пути до этих вершин имели меньшую длину, то данное ребро не включается в дерево кратчайших путей. Если включение этого ребра приводит к уменьшению оценки какой-либо из инцидентных вершин, например
v
i
, то эта оценка d
i,k
будет оценкой кратчайшего пути до вершины v
i
, и ребро e
i,j
войдет в искомое дерево кратчайших путей. Это происходит в силу того, что после изменения не существует иного кратчайшего пути
i
до вершины v
i
, кроме пути
i,k
, содержащего ребро
e
i,j
Этот кратчайший путь
i,k
не будет существовать, если не будет кратчайших путей до всех промежуточных вершин v
p
V
(Vi)
этого пути.
Кратчайшие пути до остальных вершин графа станут «недействительными», т. е. невозможно будет сказать, останутся они такими же или кратчайший путь до них будет включать изменившееся ребро. Теорема доказана.
Теорема 5. Если nw
i,j
> w
i,j
и e
i,j
E
T
и
nw
i,j
> nw
i,j
t
(точки вхождения в дерево), то изменению могут подвергнуться кратчайшие пути и оценки их длин для вершин V
Т
(Vj)
и новые кратчайшие пути к этим вершинам будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.
Доказательство. Пусть увеличился вес ребра e
i,j
E
T
, которое входит, по крайней мере, в один кратчайший путь
k
, например в
k,p
Согласно теореме 1 вершины v
k
, в кратчайшие пути до которых ребро e
i,j
не входит, будут составлять множество V
Т
вершин, кратчайшие пути до которых после изменения не изменятся
(не изменится последовательность ребер и величины кратчайших путей). Для вершин V
Т
(Vj)
среди парных переходов соответствующих этим вершинам будут находиться ребра, имеющие минимальную длину пути к этим вершинам.
Теорема доказана.
Следствие. При увеличении веса ребра, входящего в дерево кратчайших путей для вершин V
Т
(Vj)
, маршрутная степень которых больше двух, новые кратчайшие пути будут проходить через ребра, состоящие в отношении парного перехода к ребрам, входящим в исходный граф.
Теорема 6. Если nw
i,j
< w
i,j
и e
i,j
E
T
и новое значение nw
i,j
< nw
i,j
t
(точки вхождения в дерево), то новые кратчайшие пути к вершинам множества v
V
Т
(Vj)
V
(Vi)
будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.
Доказательство. Пусть уменьшился вес ребра e
i,j
E
R
, которое не входит ни в один кратчайший путь. Согласно с теоремой 4 без изменения останутся кратчайшие пути и оценки их длин для вершин множества V
(Vi)
. Т.к nw
i,j
<
nw
i,j
, то включение этого ребра приводит к уменьшению оценки какой-либо из инцидент- ных вершин, например v
i
, и эта оценка d
i,k
будет оценкой кратчайшего пути до вершины v
i
, и ребро e
i,j
войдет в искомое дерево кратчайших путей. Это происходит в силу того, что после изменения не существует иного кратчайшего пути
i
до вершины v
i
, кроме пути
i,k
, содержащего ребро e
i,j
. Этот кратчайший путь
i,k
не будет существовать, если не будет кратчайших путей до всех промежуточных вершин v
p
V
(Vi)
этого пути. Теорема доказана.
Следствие. При уменьшении веса ребра, не входящего в дерево кратчайших путей для вершин V
Т
(Vj)
V
(Vi)
, маршрутная степень которых больше двух, новые кратчайшие пути будут проходить через ребра, состоящие в отношении парного перехода к ребрам, вхо- дящим в исходный граф.
Использование доказанных выше теорем позволяет разработать алгоритм, уменьшающий размерность задачи поиска кратчайших путей в условиях, когда пропускная способность линий связи и структура сети динамически меняется.
Каждую вершину в алгоритме будет описывать структура данных VERTEX. Данная структура содержит индекс, равный индексу соответствующей вершины v
i
; указатель на родительскую вершину v i
.p (для корневой вершины он будет содержать null v i
.p=null), оценку длины оптимального маршрута v i
.d и массив указателей на потомков по иерархии v i
.c j
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
53
(для вершин–листьев он пустой). Полученное в процессе работы алгоритма дерево T будет представлять собой массив объектов типа
VERTEX. Вершина v i
, i = 1..||V||, T.vs – начальная вершина. Каждое ребро графа G описывается структурой, которая определяется весом ребра e i
.w и указателями на инцидентные вершины e i
.v1, e i
.v2.
Для поиска оптимальных маршрутов будем применять алгоритм Дейкстры.
//Алгоритм Дейкстры. T – структура данных дерева оптимальных маршрутов, V – множество вершин графа, vs – начальная вершина.
DeicstraAlg(T,V,vs)
1.
Initialize(V,vs)
2.
Q.add(V,vs)
3.
Пока Q
4. vm = Extract-Min(Q);
5.
T.add(vm);
6.
Для всех инцидентных vm ребер vk
7.
Если d[vm.i]>d[vk.i]+w(vk,vm) то
8. d[vm.i] = d[vk.i] + w(vk,vm);
9. p[vm.i] = vk;
Конец Если
Конец Для
Конец Пока
Конец
В приведенной процедуре используется функция Extract – Min, возвращающая объект с минимальным ключом. Реализация данной функции и ее трудоемкость зависят от способа определения списка (очереди). Алгоритм вычис- ляет значения массивов d и p оценок длин оптимальных маршрутов и указателей на роди- тельские таблицы соответственно. Полученные массивы необходимо сохранить.
// Процедура сохранения массивов
SaveAr(v,i)
1.
Если i=0 то
2. v.d1:=d;
3. v.p1:=p;
Иначе
4. v.d2:=d;
5. v.p2:=p;
Конец Если
Конец
Для ребер, участвующих в построении опти- мальных маршрутов, является целесообразным проводить расчет для инцидентных вершин, лежащих ниже по иерархии.
// Процедура нахождения деревьев оптимальных маршрутов для всех вершин графа
GetSPT(T,V,vs)
1.
Q.Add(vs)
2.
Пока Q
3. v:=Q.Get
4.
Для всех v.ci
5.
Q.Add(v.ci.v2)
Конец Для
6.
Если v<>vs то
7. e:=E(v,v.p)
8. tw:=e.w;
9. e.w:=0;
10.
DeicstraAlg(T,V,v)
11.
SaveAr(v,0)
12. e.w:=M
13.
DeicstraAlg(T,V,v)
14.
SaveAr(v,1)
Конец Если
Конец Пока
Конец
В приведенной процедуре М – число, принятое за максимальное в данной системе.
Процедура нахождения деревьев оптимальных маршрутов для графа обходит все вершины графа с формированием списков парных пере- ходов для каждой вершины.
От дерева оптимальных маршрутов из заданной вершины легко перейти к списку парных переходов. Оценки длин оптимальных маршрутов в данном случае будут соответст- вовать приращениям потенциала этой вершины.
При поиске оптимального маршрута особой обработки, как было сказано выше, заслуживает вариант уменьшения веса ребра, не входящего в оптимальный маршрут. В этом случае необхо- димо предварительно проверить вершины, лежа- щие выше по иерархии.
// Процедура проверки на включение в поддере- во вершины v вершин, лежащих выше по иерар- хии относительно вершины v
TestUp(v)
1. v2:=v.P
2.
Пока v2.d>v.d+E(v,v2)
3. v2.d:= v.d+E(v,v2)
4.
Для всех v2.Ci
5.
Если v2.Ci<>v то
6. v2.Ci.d:=v2.d+E(v2,v2.Ci)
Конец Если
Конец Для
7. v:=v2;
8. v2:=v2.P;
Конец Пока
Конец
Для проверки срабатывания парного пере- хода используется условие целесообразности включения ребра в дерево. Отдельно обраба- тываются случаи увеличения и уменьшения оценки длины оптимального маршрута.
// Процедура обработки изменения веса ребра будет выглядеть следующим образом:
PathPT(e,nw)
54
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
1. v1=e.v1 2. v2=e.v2 3.
Если v1.d>e.v2 то
4. v1=e.v2 5. v2=e.v1
Конец Если
6.
Если nw>e.w то
7. dt:=v2.d2 8. pt:=v2.p2 9.
Если not e.InTree то
10.
TestUp(v2)
Конец Если
Иначе
11. dt:=v2.d
12. pt:=v2.p
Конец Если
13.
Q.Add(vs)
14.
Пока Q
15. v:=Q.Get
16.
Для всех v.ci
17.
Q.Add(v.ci.v2)
Конец Для
18.
Если v<>vs то
19. Если v.p.d+E(v.p,v).w>pt[v.i].d+E(pt[v.i],v) то
20. v.p:= pt[v.i]
21. v.d:= pt[v.i].d+E(pt[v.i],v)
Конец Если
Конец Если
Конец Пока
Конец
Рассмотрим работу алгоритма адаптивной ускоренной маршрутизации. Укрупненная схема алгоритма имеет следующий вид.
Шаг 1. Для вершины, являющейся листом дере- ва, производится поиск всех парных переходов без ограничений. Эти списки для удобства дальнейшей работы привязываются к вершине, инцидентной рассматриваемому ребру и распо- ложенной ниже по иерархии.
Шаг 2. Если вершина не является листом дерева, то вычисляются парные переходы для этой вершины и выбираются лучшие значения потен- циалов парных переходов для потомков верши- ны и собственных парных переходов. Подобная процедура выполняется для формирования спис- ков парных переходов в случае увеличения и уменьшения веса ребра.
Шаг 3. Для каждой вершины формируется пол- ный список парных переходов. Число элементов в каждом их этих списков не превышает коли- чества вершин графа. Такое решение позволяет отказаться от предварительной сортировки по- тенциалов или приращений для парных пере- ходов без значительного усложнения алгоритма обработки изменения.
Шаг 4. Для каждой вершины формируется пол- ный список возможных маршрутов, проходящий через ребра, состоящие в отношении парного перехода, включая и ребра, входящие в дерево кратчайших путей.
Шаг 5. Анализируя полученную используемым протоколом маршрутизации информацию, опре- делить, произошло ли изменение метрики для какого-либо ребра: а) если да, то перейти к шагу 6; б) иначе - к шагу 5.
Шаг 6. Используя список парных переходов, определить, требуется ли сделать парный пере- ход: а) если да, то перейти к шагу 7; б) иначе – к шагу 9.
Шаг 7. Для каждой вершины, у которой в список возможных маршрутов входит ребро с изменив- шейся метрикой, определить путь минимальной длины и поместить его в дерево кратчайших путей, тем самым, построив новое дерево кратчайших путей на графе.
Шаг 8. а) передать пакеты по доступным эквивалентным маршрутам; б) установить флаг передачи.
Шаг 9. Пересчитать точки вхождения в дерево и переформировать список маршрутов замены для каждой изменившейся вершины.
Шаг 10. Перейти к шагу 5.
Работа составных частей алгоритма основы- вается на использовании доказанных выше теорем, следовательно, можно сделать вывод о корректности работы всего алгоритма в целом.
Проведем анализ сложности алгоритма адаптивной ускоренной маршрутизации, для чего найдем верхнюю и нижнюю оценки его трудоемкости. Для этого определим оценки для процедур, составляющих алгоритм. Для всех процедур было найдено количество повторений каждого шага и стоимость для верхней и нижней оценок трудоемкости. Трудоемкость модифици- рованного алгоритма Дейкстры составляет:
(N
2
log
2
N).
Результаты анализа трудоемкости остальных процедур сведены в таблицах 1 – 3.
Таблица 1 – Трудоемкость процедуры SaveAr
Верхняя оценка трудоемкости процедуры
SaveAr:
= 1 + 1 + 1 = 3, а нижняя оценка:
= 1 + 1 + 1 = 3.
№ шага п/п
(N)
(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
0 1
3 1
1 0
1 4
0 1
1 1
5 0
1 1
1
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
55
Таблица 2 – Трудоемкость процедуры GetSPT
Верхняя оценка трудоемкости процедуры
GetSPT:
= 15N + 2N
2
log
2
N + 1,
а нижняя оценка:
= 15N + 2N
2
log
2
N + 1.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости по- строения дерева кратчайших путей и получения дополнительной информации:
(N
2
log
2
N) и нижнюю оценку:
(N
2
log
2
N).
Тогда трудоемкость процедуры PathPT запи- шется следующим образом:
Верхняя оценка трудоемкости процедуры
PathPT:
= 10 + 5N + 3(N - 1) + 6N + 2 = 14N + 9, а нижняя оценка:
=8 + 5N + N – 1 = 6N + 7
Таким образом, удается рассчитать дерево кратчайших путей за линейное время в худшем случаи. Такой результат удается получить путем использования дополнительной информации о парных переходах.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости:
(N)
и нижнюю оценку:
(N).
Таким образом, разработанный алгоритм адаптивной ускоренной маршрутизации позво- ляет повысить эффективность функциониро- вания корпоративных сетей.
Таблица 3 – Трудоемкость процедуры PathPT
Заключение. Разработка алгоритма адап- тивной ускоренной маршрутизации позволяет повысить эффективность функционирования корпоративных сетей за счет уменьшения трудоемкости построения таблиц маршрути- зации до величины порядка O(N) в условиях динамически изменяющейся структуры корпора- тивной сети и характеристик линий связи.
Библиографический список
1. Куракин Д.В. Маршрутизаторы для глобаль- ных телекоммуникационных сетей и реализуемые в них алгоритмы // Информационные технологии.–
1996. №2.
2. Олифер В.Г., Олифер Н.А. Основы компью- терных сетей – СПб.: Питер, 2009. – 352 с.
№ шага п/п
(N)
(N)
Число повто- рений
Цена
Число повто- рений
Цена
1 1
1 1
1 2
N
1
N
1 3
N
1
N
1 4
N
1
N
1 5
N
1
N
1 6
N
1
N
1 7
N
1
N
1 8
N
1
N
1 9
N
1
N
1 10
N
Nlog
2
N
N
Nlog
2
N
11
N
3
N
3 12
N
1
N
1 13
N
Nlog
2
N
N
Nlog
2
N
14
N
3
N
3
№ шага п/п
(N)
(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
1 1
3 1
1 1
1 4
1 1
0 1
5 1
1 0
1 6
1 1
1 1
7 1
1 0
1 8
1 1
0 1
9 1
1 1
1 10 1
6N+2 0
1 11 0
1 1
1 12 0
1 1
1 13 1
1 1
1 14
N
1
N
1 15
N
1
N
1 16
N
1
N
1 17
N
1
N
1 18
N
1
N
1 19
N-1 1
N-1 1
20
N-1 1
0 1
21
N-1 1
0 1
56
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
УДК 519.718
В.В. Тарасов, Н.В. Елкина
К ЗАДАЧЕ КОНТРОЛЯ ВХОДНОЙ ИНФОРМАЦИИ НА СХЕМАХ
ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ С ЗАДЕРЖКАМИ
Рассмотрена задача контроля входной информации на схемах из функ-
циональных элементов в базисе
z
,
,
&,
, где
z – тождественная функция
с задержками.
Ключевые слова: функции алгебры логики с задержками, надежность и
контроль, схемотехника.
Введение. В исследованиях [1-5] по теории функций алгебры логики (ФАЛ) с задержками основной задачей являлось изучение методов синтеза вычислительных устройств на предмет быстродействия. Цель статьи: рассмотрение задачи контроля входной информации на схемах из функциональных элементов в базисе
,
&,
с добавлением к базису элемента, реализующего тождественную функцию
z с задержками, диф- ференцированными по входу. Пусть t – момент времени подачи сигнала (нуля или единицы) на вход элемента
z , тогда на выходе этот сигнал появляется в момент времени
t
, где
1
при подаче на вход нуля и
2
при подаче на вход единицы. Положим для определенности
2 1
. Под ФАЛ с задержками будем понимать пару функций
n
n
x
x
x
x
f
,...,
,
,...,
1 1
, где при одновременной подаче значений переменных
1 1
x
, …,
n
n
x
на входы ФАЛ
n
x
x
f
,...,
1
на выходе получаем значение
n
f
,...,
1
с временной внутренней задержкой
0
,...,
1
n
,
R
. ФАЛ с задержками
n
x
x
f
,
,...,
1
n
x
x ,...,
1
существенно зависит от переменной
i
x , если существует пара соседних наборов по переменной
i
x :
n
i
i
,...,
,
0
,
,...,
1 1
1
и
n
i
i
,...,
,
1
,
,...,
1 1
1
такие, что
f
f
либо
, в противном случае переменная
i
x называется фиктивной.
При добавлении или изъятии фиктивных переменных у ФАЛ с задержками получив- шиеся функции не считаются равными.
Причиной этого служит следующий важный пример. Рассмотрим схему
y
x
S
,
(см. рисунок
1), реализующую функцию
x
, где вход
y
является фиктивным с традиционно функ- циональной точки зрения.
&
x
y
1 2 3 4 5 6
Теорема 4. Если nw
i,j
< w
i,j
и e
i,j
E
T
, то без изменения останутся кратчайшие пути и оценки их длин для вершин множества V
(Vi)
Доказательство. Пусть уменьшился вес ребра e
i,j
E
R
, которое не входит ни в один кратчайший путь. Допустим, что это ребро входит в путь
i,k
i
и
j,p
j
. Если изменившееся ребро e
i,j
не уменьшает оценок обеих инцидентных ему вершин v
i
и v
j
, т.е. d
i,k
d
i
и d
j,p
d
j
, дерево кратчайших путей не изменится.
Действительно, рассматриваемое ребро оказывает влияние, прежде всего на инцидентные ему вершины множества V. Если включение ребра e
i,j
в дерево не уменьшает оценок пути d
i
, d
j
, то такое включение только увеличит оценки вершин. Т.к. существовавшие до изменения пути до этих вершин имели меньшую длину, то данное ребро не включается в дерево кратчайших путей. Если включение этого ребра приводит к уменьшению оценки какой-либо из инцидентных вершин, например
v
i
, то эта оценка d
i,k
будет оценкой кратчайшего пути до вершины v
i
, и ребро e
i,j
войдет в искомое дерево кратчайших путей. Это происходит в силу того, что после изменения не существует иного кратчайшего пути
i
до вершины v
i
, кроме пути
i,k
, содержащего ребро
e
i,j
Этот кратчайший путь
i,k
не будет существовать, если не будет кратчайших путей до всех промежуточных вершин v
p
V
(Vi)
этого пути.
Кратчайшие пути до остальных вершин графа станут «недействительными», т. е. невозможно будет сказать, останутся они такими же или кратчайший путь до них будет включать изменившееся ребро. Теорема доказана.
Теорема 5. Если nw
i,j
> w
i,j
и e
i,j
E
T
и
nw
i,j
> nw
i,j
t
(точки вхождения в дерево), то изменению могут подвергнуться кратчайшие пути и оценки их длин для вершин V
Т
(Vj)
и новые кратчайшие пути к этим вершинам будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.
Доказательство. Пусть увеличился вес ребра e
i,j
E
T
, которое входит, по крайней мере, в один кратчайший путь
k
, например в
k,p
Согласно теореме 1 вершины v
k
, в кратчайшие пути до которых ребро e
i,j
не входит, будут составлять множество V
Т
вершин, кратчайшие пути до которых после изменения не изменятся
(не изменится последовательность ребер и величины кратчайших путей). Для вершин V
Т
(Vj)
среди парных переходов соответствующих этим вершинам будут находиться ребра, имеющие минимальную длину пути к этим вершинам.
Теорема доказана.
Следствие. При увеличении веса ребра, входящего в дерево кратчайших путей для вершин V
Т
(Vj)
, маршрутная степень которых больше двух, новые кратчайшие пути будут проходить через ребра, состоящие в отношении парного перехода к ребрам, входящим в исходный граф.
Теорема 6. Если nw
i,j
< w
i,j
и e
i,j
E
T
и новое значение nw
i,j
< nw
i,j
t
(точки вхождения в дерево), то новые кратчайшие пути к вершинам множества v
V
Т
(Vj)
V
(Vi)
будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.
Доказательство. Пусть уменьшился вес ребра e
i,j
E
R
, которое не входит ни в один кратчайший путь. Согласно с теоремой 4 без изменения останутся кратчайшие пути и оценки их длин для вершин множества V
(Vi)
. Т.к nw
i,j
<
nw
i,j
, то включение этого ребра приводит к уменьшению оценки какой-либо из инцидент- ных вершин, например v
i
, и эта оценка d
i,k
будет оценкой кратчайшего пути до вершины v
i
, и ребро e
i,j
войдет в искомое дерево кратчайших путей. Это происходит в силу того, что после изменения не существует иного кратчайшего пути
i
до вершины v
i
, кроме пути
i,k
, содержащего ребро e
i,j
. Этот кратчайший путь
i,k
не будет существовать, если не будет кратчайших путей до всех промежуточных вершин v
p
V
(Vi)
этого пути. Теорема доказана.
Следствие. При уменьшении веса ребра, не входящего в дерево кратчайших путей для вершин V
Т
(Vj)
V
(Vi)
, маршрутная степень которых больше двух, новые кратчайшие пути будут проходить через ребра, состоящие в отношении парного перехода к ребрам, вхо- дящим в исходный граф.
Использование доказанных выше теорем позволяет разработать алгоритм, уменьшающий размерность задачи поиска кратчайших путей в условиях, когда пропускная способность линий связи и структура сети динамически меняется.
Каждую вершину в алгоритме будет описывать структура данных VERTEX. Данная структура содержит индекс, равный индексу соответствующей вершины v
i
; указатель на родительскую вершину v i
.p (для корневой вершины он будет содержать null v i
.p=null), оценку длины оптимального маршрута v i
.d и массив указателей на потомков по иерархии v i
.c j
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
53
(для вершин–листьев он пустой). Полученное в процессе работы алгоритма дерево T будет представлять собой массив объектов типа
VERTEX. Вершина v i
, i = 1..||V||, T.vs – начальная вершина. Каждое ребро графа G описывается структурой, которая определяется весом ребра e i
.w и указателями на инцидентные вершины e i
.v1, e i
.v2.
Для поиска оптимальных маршрутов будем применять алгоритм Дейкстры.
//Алгоритм Дейкстры. T – структура данных дерева оптимальных маршрутов, V – множество вершин графа, vs – начальная вершина.
DeicstraAlg(T,V,vs)
1.
Initialize(V,vs)
2.
Q.add(V,vs)
3.
Пока Q
4. vm = Extract-Min(Q);
5.
T.add(vm);
6.
Для всех инцидентных vm ребер vk
7.
Если d[vm.i]>d[vk.i]+w(vk,vm) то
8. d[vm.i] = d[vk.i] + w(vk,vm);
9. p[vm.i] = vk;
Конец Если
Конец Для
Конец Пока
Конец
В приведенной процедуре используется функция Extract – Min, возвращающая объект с минимальным ключом. Реализация данной функции и ее трудоемкость зависят от способа определения списка (очереди). Алгоритм вычис- ляет значения массивов d и p оценок длин оптимальных маршрутов и указателей на роди- тельские таблицы соответственно. Полученные массивы необходимо сохранить.
// Процедура сохранения массивов
SaveAr(v,i)
1.
Если i=0 то
2. v.d1:=d;
3. v.p1:=p;
Иначе
4. v.d2:=d;
5. v.p2:=p;
Конец Если
Конец
Для ребер, участвующих в построении опти- мальных маршрутов, является целесообразным проводить расчет для инцидентных вершин, лежащих ниже по иерархии.
// Процедура нахождения деревьев оптимальных маршрутов для всех вершин графа
GetSPT(T,V,vs)
1.
Q.Add(vs)
2.
Пока Q
3. v:=Q.Get
4.
Для всех v.ci
5.
Q.Add(v.ci.v2)
Конец Для
6.
Если v<>vs то
7. e:=E(v,v.p)
8. tw:=e.w;
9. e.w:=0;
10.
DeicstraAlg(T,V,v)
11.
SaveAr(v,0)
12. e.w:=M
13.
DeicstraAlg(T,V,v)
14.
SaveAr(v,1)
Конец Если
Конец Пока
Конец
В приведенной процедуре М – число, принятое за максимальное в данной системе.
Процедура нахождения деревьев оптимальных маршрутов для графа обходит все вершины графа с формированием списков парных пере- ходов для каждой вершины.
От дерева оптимальных маршрутов из заданной вершины легко перейти к списку парных переходов. Оценки длин оптимальных маршрутов в данном случае будут соответст- вовать приращениям потенциала этой вершины.
При поиске оптимального маршрута особой обработки, как было сказано выше, заслуживает вариант уменьшения веса ребра, не входящего в оптимальный маршрут. В этом случае необхо- димо предварительно проверить вершины, лежа- щие выше по иерархии.
// Процедура проверки на включение в поддере- во вершины v вершин, лежащих выше по иерар- хии относительно вершины v
TestUp(v)
1. v2:=v.P
2.
Пока v2.d>v.d+E(v,v2)
3. v2.d:= v.d+E(v,v2)
4.
Для всех v2.Ci
5.
Если v2.Ci<>v то
6. v2.Ci.d:=v2.d+E(v2,v2.Ci)
Конец Если
Конец Для
7. v:=v2;
8. v2:=v2.P;
Конец Пока
Конец
Для проверки срабатывания парного пере- хода используется условие целесообразности включения ребра в дерево. Отдельно обраба- тываются случаи увеличения и уменьшения оценки длины оптимального маршрута.
// Процедура обработки изменения веса ребра будет выглядеть следующим образом:
PathPT(e,nw)
54
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
1. v1=e.v1 2. v2=e.v2 3.
Если v1.d>e.v2 то
4. v1=e.v2 5. v2=e.v1
Конец Если
6.
Если nw>e.w то
7. dt:=v2.d2 8. pt:=v2.p2 9.
Если not e.InTree то
10.
TestUp(v2)
Конец Если
Иначе
11. dt:=v2.d
12. pt:=v2.p
Конец Если
13.
Q.Add(vs)
14.
Пока Q
15. v:=Q.Get
16.
Для всех v.ci
17.
Q.Add(v.ci.v2)
Конец Для
18.
Если v<>vs то
19. Если v.p.d+E(v.p,v).w>pt[v.i].d+E(pt[v.i],v) то
20. v.p:= pt[v.i]
21. v.d:= pt[v.i].d+E(pt[v.i],v)
Конец Если
Конец Если
Конец Пока
Конец
Рассмотрим работу алгоритма адаптивной ускоренной маршрутизации. Укрупненная схема алгоритма имеет следующий вид.
Шаг 1. Для вершины, являющейся листом дере- ва, производится поиск всех парных переходов без ограничений. Эти списки для удобства дальнейшей работы привязываются к вершине, инцидентной рассматриваемому ребру и распо- ложенной ниже по иерархии.
Шаг 2. Если вершина не является листом дерева, то вычисляются парные переходы для этой вершины и выбираются лучшие значения потен- циалов парных переходов для потомков верши- ны и собственных парных переходов. Подобная процедура выполняется для формирования спис- ков парных переходов в случае увеличения и уменьшения веса ребра.
Шаг 3. Для каждой вершины формируется пол- ный список парных переходов. Число элементов в каждом их этих списков не превышает коли- чества вершин графа. Такое решение позволяет отказаться от предварительной сортировки по- тенциалов или приращений для парных пере- ходов без значительного усложнения алгоритма обработки изменения.
Шаг 4. Для каждой вершины формируется пол- ный список возможных маршрутов, проходящий через ребра, состоящие в отношении парного перехода, включая и ребра, входящие в дерево кратчайших путей.
Шаг 5. Анализируя полученную используемым протоколом маршрутизации информацию, опре- делить, произошло ли изменение метрики для какого-либо ребра: а) если да, то перейти к шагу 6; б) иначе - к шагу 5.
Шаг 6. Используя список парных переходов, определить, требуется ли сделать парный пере- ход: а) если да, то перейти к шагу 7; б) иначе – к шагу 9.
Шаг 7. Для каждой вершины, у которой в список возможных маршрутов входит ребро с изменив- шейся метрикой, определить путь минимальной длины и поместить его в дерево кратчайших путей, тем самым, построив новое дерево кратчайших путей на графе.
Шаг 8. а) передать пакеты по доступным эквивалентным маршрутам; б) установить флаг передачи.
Шаг 9. Пересчитать точки вхождения в дерево и переформировать список маршрутов замены для каждой изменившейся вершины.
Шаг 10. Перейти к шагу 5.
Работа составных частей алгоритма основы- вается на использовании доказанных выше теорем, следовательно, можно сделать вывод о корректности работы всего алгоритма в целом.
Проведем анализ сложности алгоритма адаптивной ускоренной маршрутизации, для чего найдем верхнюю и нижнюю оценки его трудоемкости. Для этого определим оценки для процедур, составляющих алгоритм. Для всех процедур было найдено количество повторений каждого шага и стоимость для верхней и нижней оценок трудоемкости. Трудоемкость модифици- рованного алгоритма Дейкстры составляет:
(N
2
log
2
N).
Результаты анализа трудоемкости остальных процедур сведены в таблицах 1 – 3.
Таблица 1 – Трудоемкость процедуры SaveAr
Верхняя оценка трудоемкости процедуры
SaveAr:
= 1 + 1 + 1 = 3, а нижняя оценка:
= 1 + 1 + 1 = 3.
№ шага п/п
(N)
(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
0 1
3 1
1 0
1 4
0 1
1 1
5 0
1 1
1
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
55
Таблица 2 – Трудоемкость процедуры GetSPT
Верхняя оценка трудоемкости процедуры
GetSPT:
= 15N + 2N
2
log
2
N + 1,
а нижняя оценка:
= 15N + 2N
2
log
2
N + 1.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости по- строения дерева кратчайших путей и получения дополнительной информации:
(N
2
log
2
N) и нижнюю оценку:
(N
2
log
2
N).
Тогда трудоемкость процедуры PathPT запи- шется следующим образом:
Верхняя оценка трудоемкости процедуры
PathPT:
= 10 + 5N + 3(N - 1) + 6N + 2 = 14N + 9, а нижняя оценка:
=8 + 5N + N – 1 = 6N + 7
Таким образом, удается рассчитать дерево кратчайших путей за линейное время в худшем случаи. Такой результат удается получить путем использования дополнительной информации о парных переходах.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости:
(N)
и нижнюю оценку:
(N).
Таким образом, разработанный алгоритм адаптивной ускоренной маршрутизации позво- ляет повысить эффективность функциониро- вания корпоративных сетей.
Таблица 3 – Трудоемкость процедуры PathPT
Заключение. Разработка алгоритма адап- тивной ускоренной маршрутизации позволяет повысить эффективность функционирования корпоративных сетей за счет уменьшения трудоемкости построения таблиц маршрути- зации до величины порядка O(N) в условиях динамически изменяющейся структуры корпора- тивной сети и характеристик линий связи.
Библиографический список
1. Куракин Д.В. Маршрутизаторы для глобаль- ных телекоммуникационных сетей и реализуемые в них алгоритмы // Информационные технологии.–
1996. №2.
2. Олифер В.Г., Олифер Н.А. Основы компью- терных сетей – СПб.: Питер, 2009. – 352 с.
№ шага п/п
(N)
(N)
Число повто- рений
Цена
Число повто- рений
Цена
1 1
1 1
1 2
N
1
N
1 3
N
1
N
1 4
N
1
N
1 5
N
1
N
1 6
N
1
N
1 7
N
1
N
1 8
N
1
N
1 9
N
1
N
1 10
N
Nlog
2
N
N
Nlog
2
N
11
N
3
N
3 12
N
1
N
1 13
N
Nlog
2
N
N
Nlog
2
N
14
N
3
N
3
№ шага п/п
(N)
(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
1 1
3 1
1 1
1 4
1 1
0 1
5 1
1 0
1 6
1 1
1 1
7 1
1 0
1 8
1 1
0 1
9 1
1 1
1 10 1
6N+2 0
1 11 0
1 1
1 12 0
1 1
1 13 1
1 1
1 14
N
1
N
1 15
N
1
N
1 16
N
1
N
1 17
N
1
N
1 18
N
1
N
1 19
N-1 1
N-1 1
20
N-1 1
0 1
21
N-1 1
0 1
56
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
УДК 519.718
В.В. Тарасов, Н.В. Елкина
К ЗАДАЧЕ КОНТРОЛЯ ВХОДНОЙ ИНФОРМАЦИИ НА СХЕМАХ
ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ С ЗАДЕРЖКАМИ
Рассмотрена задача контроля входной информации на схемах из функ-
циональных элементов в базисе
z
,
,
&,
, где
z – тождественная функция
с задержками.
Ключевые слова: функции алгебры логики с задержками, надежность и
контроль, схемотехника.
Введение. В исследованиях [1-5] по теории функций алгебры логики (ФАЛ) с задержками основной задачей являлось изучение методов синтеза вычислительных устройств на предмет быстродействия. Цель статьи: рассмотрение задачи контроля входной информации на схемах из функциональных элементов в базисе
,
&,
с добавлением к базису элемента, реализующего тождественную функцию
z с задержками, диф- ференцированными по входу. Пусть t – момент времени подачи сигнала (нуля или единицы) на вход элемента
z , тогда на выходе этот сигнал появляется в момент времени
t
, где
1
при подаче на вход нуля и
2
при подаче на вход единицы. Положим для определенности
2 1
. Под ФАЛ с задержками будем понимать пару функций
n
n
x
x
x
x
f
,...,
,
,...,
1 1
, где при одновременной подаче значений переменных
1 1
x
, …,
n
n
x
на входы ФАЛ
n
x
x
f
,...,
1
на выходе получаем значение
n
f
,...,
1
с временной внутренней задержкой
0
,...,
1
n
,
R
. ФАЛ с задержками
n
x
x
f
,
,...,
1
n
x
x ,...,
1
существенно зависит от переменной
i
x , если существует пара соседних наборов по переменной
i
x :
n
i
i
,...,
,
0
,
,...,
1 1
1
и
n
i
i
,...,
,
1
,
,...,
1 1
1
такие, что
f
f
либо
, в противном случае переменная
i
x называется фиктивной.
При добавлении или изъятии фиктивных переменных у ФАЛ с задержками получив- шиеся функции не считаются равными.
Причиной этого служит следующий важный пример. Рассмотрим схему
y
x
S
,
(см. рисунок
1), реализующую функцию
x
, где вход
y
является фиктивным с традиционно функ- циональной точки зрения.
&
x
y
1 2 3 4 5 6
Теорема 4. Если nw
i,j
< w
i,j
и e
i,j
E
T
, то без изменения останутся кратчайшие пути и оценки их длин для вершин множества V
(Vi)
Доказательство. Пусть уменьшился вес ребра e
i,j
E
R
, которое не входит ни в один кратчайший путь. Допустим, что это ребро входит в путь
i,k
i
и
j,p
j
. Если изменившееся ребро e
i,j
не уменьшает оценок обеих инцидентных ему вершин v
i
и v
j
, т.е. d
i,k
d
i
и d
j,p
d
j
, дерево кратчайших путей не изменится.
Действительно, рассматриваемое ребро оказывает влияние, прежде всего на инцидентные ему вершины множества V. Если включение ребра e
i,j
в дерево не уменьшает оценок пути d
i
, d
j
, то такое включение только увеличит оценки вершин. Т.к. существовавшие до изменения пути до этих вершин имели меньшую длину, то данное ребро не включается в дерево кратчайших путей. Если включение этого ребра приводит к уменьшению оценки какой-либо из инцидентных вершин, например
v
i
, то эта оценка d
i,k
будет оценкой кратчайшего пути до вершины v
i
, и ребро e
i,j
войдет в искомое дерево кратчайших путей. Это происходит в силу того, что после изменения не существует иного кратчайшего пути
i
до вершины v
i
, кроме пути
i,k
, содержащего ребро
e
i,j
Этот кратчайший путь
i,k
не будет существовать, если не будет кратчайших путей до всех промежуточных вершин v
p
V
(Vi)
этого пути.
Кратчайшие пути до остальных вершин графа станут «недействительными», т. е. невозможно будет сказать, останутся они такими же или кратчайший путь до них будет включать изменившееся ребро. Теорема доказана.
Теорема 5. Если nw
i,j
> w
i,j
и e
i,j
E
T
и
nw
i,j
> nw
i,j
t
(точки вхождения в дерево), то изменению могут подвергнуться кратчайшие пути и оценки их длин для вершин V
Т
(Vj)
и новые кратчайшие пути к этим вершинам будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.
Доказательство. Пусть увеличился вес ребра e
i,j
E
T
, которое входит, по крайней мере, в один кратчайший путь
k
, например в
k,p
Согласно теореме 1 вершины v
k
, в кратчайшие пути до которых ребро e
i,j
не входит, будут составлять множество V
Т
вершин, кратчайшие пути до которых после изменения не изменятся
(не изменится последовательность ребер и величины кратчайших путей). Для вершин V
Т
(Vj)
среди парных переходов соответствующих этим вершинам будут находиться ребра, имеющие минимальную длину пути к этим вершинам.
Теорема доказана.
Следствие. При увеличении веса ребра, входящего в дерево кратчайших путей для вершин V
Т
(Vj)
, маршрутная степень которых больше двух, новые кратчайшие пути будут проходить через ребра, состоящие в отношении парного перехода к ребрам, входящим в исходный граф.
Теорема 6. Если nw
i,j
< w
i,j
и e
i,j
E
T
и новое значение nw
i,j
< nw
i,j
t
(точки вхождения в дерево), то новые кратчайшие пути к вершинам множества v
V
Т
(Vj)
V
(Vi)
будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.
Доказательство. Пусть уменьшился вес ребра e
i,j
E
R
, которое не входит ни в один кратчайший путь. Согласно с теоремой 4 без изменения останутся кратчайшие пути и оценки их длин для вершин множества V
(Vi)
. Т.к nw
i,j
<
nw
i,j
, то включение этого ребра приводит к уменьшению оценки какой-либо из инцидент- ных вершин, например v
i
, и эта оценка d
i,k
будет оценкой кратчайшего пути до вершины v
i
, и ребро e
i,j
войдет в искомое дерево кратчайших путей. Это происходит в силу того, что после изменения не существует иного кратчайшего пути
i
до вершины v
i
, кроме пути
i,k
, содержащего ребро e
i,j
. Этот кратчайший путь
i,k
не будет существовать, если не будет кратчайших путей до всех промежуточных вершин v
p
V
(Vi)
этого пути. Теорема доказана.
Следствие. При уменьшении веса ребра, не входящего в дерево кратчайших путей для вершин V
Т
(Vj)
V
(Vi)
, маршрутная степень которых больше двух, новые кратчайшие пути будут проходить через ребра, состоящие в отношении парного перехода к ребрам, вхо- дящим в исходный граф.
Использование доказанных выше теорем позволяет разработать алгоритм, уменьшающий размерность задачи поиска кратчайших путей в условиях, когда пропускная способность линий связи и структура сети динамически меняется.
Каждую вершину в алгоритме будет описывать структура данных VERTEX. Данная структура содержит индекс, равный индексу соответствующей вершины v
i
; указатель на родительскую вершину v i
.p (для корневой вершины он будет содержать null v i
.p=null), оценку длины оптимального маршрута v i
.d и массив указателей на потомков по иерархии v i
.c j
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
53
(для вершин–листьев он пустой). Полученное в процессе работы алгоритма дерево T будет представлять собой массив объектов типа
VERTEX. Вершина v i
, i = 1..||V||, T.vs – начальная вершина. Каждое ребро графа G описывается структурой, которая определяется весом ребра e i
.w и указателями на инцидентные вершины e i
.v1, e i
.v2.
Для поиска оптимальных маршрутов будем применять алгоритм Дейкстры.
//Алгоритм Дейкстры. T – структура данных дерева оптимальных маршрутов, V – множество вершин графа, vs – начальная вершина.
DeicstraAlg(T,V,vs)
1.
Initialize(V,vs)
2.
Q.add(V,vs)
3.
Пока Q
4. vm = Extract-Min(Q);
5.
T.add(vm);
6.
Для всех инцидентных vm ребер vk
7.
Если d[vm.i]>d[vk.i]+w(vk,vm) то
8. d[vm.i] = d[vk.i] + w(vk,vm);
9. p[vm.i] = vk;
Конец Если
Конец Для
Конец Пока
Конец
В приведенной процедуре используется функция Extract – Min, возвращающая объект с минимальным ключом. Реализация данной функции и ее трудоемкость зависят от способа определения списка (очереди). Алгоритм вычис- ляет значения массивов d и p оценок длин оптимальных маршрутов и указателей на роди- тельские таблицы соответственно. Полученные массивы необходимо сохранить.
// Процедура сохранения массивов
SaveAr(v,i)
1.
Если i=0 то
2. v.d1:=d;
3. v.p1:=p;
Иначе
4. v.d2:=d;
5. v.p2:=p;
Конец Если
Конец
Для ребер, участвующих в построении опти- мальных маршрутов, является целесообразным проводить расчет для инцидентных вершин, лежащих ниже по иерархии.
// Процедура нахождения деревьев оптимальных маршрутов для всех вершин графа
GetSPT(T,V,vs)
1.
Q.Add(vs)
2.
Пока Q
3. v:=Q.Get
4.
Для всех v.ci
5.
Q.Add(v.ci.v2)
Конец Для
6.
Если v<>vs то
7. e:=E(v,v.p)
8. tw:=e.w;
9. e.w:=0;
10.
DeicstraAlg(T,V,v)
11.
SaveAr(v,0)
12. e.w:=M
13.
DeicstraAlg(T,V,v)
14.
SaveAr(v,1)
Конец Если
Конец Пока
Конец
В приведенной процедуре М – число, принятое за максимальное в данной системе.
Процедура нахождения деревьев оптимальных маршрутов для графа обходит все вершины графа с формированием списков парных пере- ходов для каждой вершины.
От дерева оптимальных маршрутов из заданной вершины легко перейти к списку парных переходов. Оценки длин оптимальных маршрутов в данном случае будут соответст- вовать приращениям потенциала этой вершины.
При поиске оптимального маршрута особой обработки, как было сказано выше, заслуживает вариант уменьшения веса ребра, не входящего в оптимальный маршрут. В этом случае необхо- димо предварительно проверить вершины, лежа- щие выше по иерархии.
// Процедура проверки на включение в поддере- во вершины v вершин, лежащих выше по иерар- хии относительно вершины v
TestUp(v)
1. v2:=v.P
2.
Пока v2.d>v.d+E(v,v2)
3. v2.d:= v.d+E(v,v2)
4.
Для всех v2.Ci
5.
Если v2.Ci<>v то
6. v2.Ci.d:=v2.d+E(v2,v2.Ci)
Конец Если
Конец Для
7. v:=v2;
8. v2:=v2.P;
Конец Пока
Конец
Для проверки срабатывания парного пере- хода используется условие целесообразности включения ребра в дерево. Отдельно обраба- тываются случаи увеличения и уменьшения оценки длины оптимального маршрута.
// Процедура обработки изменения веса ребра будет выглядеть следующим образом:
PathPT(e,nw)
54
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
1. v1=e.v1 2. v2=e.v2 3.
Если v1.d>e.v2 то
4. v1=e.v2 5. v2=e.v1
Конец Если
6.
Если nw>e.w то
7. dt:=v2.d2 8. pt:=v2.p2 9.
Если not e.InTree то
10.
TestUp(v2)
Конец Если
Иначе
11. dt:=v2.d
12. pt:=v2.p
Конец Если
13.
Q.Add(vs)
14.
Пока Q
15. v:=Q.Get
16.
Для всех v.ci
17.
Q.Add(v.ci.v2)
Конец Для
18.
Если v<>vs то
19. Если v.p.d+E(v.p,v).w>pt[v.i].d+E(pt[v.i],v) то
20. v.p:= pt[v.i]
21. v.d:= pt[v.i].d+E(pt[v.i],v)
Конец Если
Конец Если
Конец Пока
Конец
Рассмотрим работу алгоритма адаптивной ускоренной маршрутизации. Укрупненная схема алгоритма имеет следующий вид.
Шаг 1. Для вершины, являющейся листом дере- ва, производится поиск всех парных переходов без ограничений. Эти списки для удобства дальнейшей работы привязываются к вершине, инцидентной рассматриваемому ребру и распо- ложенной ниже по иерархии.
Шаг 2. Если вершина не является листом дерева, то вычисляются парные переходы для этой вершины и выбираются лучшие значения потен- циалов парных переходов для потомков верши- ны и собственных парных переходов. Подобная процедура выполняется для формирования спис- ков парных переходов в случае увеличения и уменьшения веса ребра.
Шаг 3. Для каждой вершины формируется пол- ный список парных переходов. Число элементов в каждом их этих списков не превышает коли- чества вершин графа. Такое решение позволяет отказаться от предварительной сортировки по- тенциалов или приращений для парных пере- ходов без значительного усложнения алгоритма обработки изменения.
Шаг 4. Для каждой вершины формируется пол- ный список возможных маршрутов, проходящий через ребра, состоящие в отношении парного перехода, включая и ребра, входящие в дерево кратчайших путей.
Шаг 5. Анализируя полученную используемым протоколом маршрутизации информацию, опре- делить, произошло ли изменение метрики для какого-либо ребра: а) если да, то перейти к шагу 6; б) иначе - к шагу 5.
Шаг 6. Используя список парных переходов, определить, требуется ли сделать парный пере- ход: а) если да, то перейти к шагу 7; б) иначе – к шагу 9.
Шаг 7. Для каждой вершины, у которой в список возможных маршрутов входит ребро с изменив- шейся метрикой, определить путь минимальной длины и поместить его в дерево кратчайших путей, тем самым, построив новое дерево кратчайших путей на графе.
Шаг 8. а) передать пакеты по доступным эквивалентным маршрутам; б) установить флаг передачи.
Шаг 9. Пересчитать точки вхождения в дерево и переформировать список маршрутов замены для каждой изменившейся вершины.
Шаг 10. Перейти к шагу 5.
Работа составных частей алгоритма основы- вается на использовании доказанных выше теорем, следовательно, можно сделать вывод о корректности работы всего алгоритма в целом.
Проведем анализ сложности алгоритма адаптивной ускоренной маршрутизации, для чего найдем верхнюю и нижнюю оценки его трудоемкости. Для этого определим оценки для процедур, составляющих алгоритм. Для всех процедур было найдено количество повторений каждого шага и стоимость для верхней и нижней оценок трудоемкости. Трудоемкость модифици- рованного алгоритма Дейкстры составляет:
(N
2
log
2
N).
Результаты анализа трудоемкости остальных процедур сведены в таблицах 1 – 3.
Таблица 1 – Трудоемкость процедуры SaveAr
Верхняя оценка трудоемкости процедуры
SaveAr:
= 1 + 1 + 1 = 3, а нижняя оценка:
= 1 + 1 + 1 = 3.
№ шага п/п
(N)
(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
0 1
3 1
1 0
1 4
0 1
1 1
5 0
1 1
1
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
55
Таблица 2 – Трудоемкость процедуры GetSPT
Верхняя оценка трудоемкости процедуры
GetSPT:
= 15N + 2N
2
log
2
N + 1,
а нижняя оценка:
= 15N + 2N
2
log
2
N + 1.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости по- строения дерева кратчайших путей и получения дополнительной информации:
(N
2
log
2
N) и нижнюю оценку:
(N
2
log
2
N).
Тогда трудоемкость процедуры PathPT запи- шется следующим образом:
Верхняя оценка трудоемкости процедуры
PathPT:
= 10 + 5N + 3(N - 1) + 6N + 2 = 14N + 9, а нижняя оценка:
=8 + 5N + N – 1 = 6N + 7
Таким образом, удается рассчитать дерево кратчайших путей за линейное время в худшем случаи. Такой результат удается получить путем использования дополнительной информации о парных переходах.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости:
(N)
и нижнюю оценку:
(N).
Таким образом, разработанный алгоритм адаптивной ускоренной маршрутизации позво- ляет повысить эффективность функциониро- вания корпоративных сетей.
Таблица 3 – Трудоемкость процедуры PathPT
Заключение. Разработка алгоритма адап- тивной ускоренной маршрутизации позволяет повысить эффективность функционирования корпоративных сетей за счет уменьшения трудоемкости построения таблиц маршрути- зации до величины порядка O(N) в условиях динамически изменяющейся структуры корпора- тивной сети и характеристик линий связи.
Библиографический список
1. Куракин Д.В. Маршрутизаторы для глобаль- ных телекоммуникационных сетей и реализуемые в них алгоритмы // Информационные технологии.–
1996. №2.
2. Олифер В.Г., Олифер Н.А. Основы компью- терных сетей – СПб.: Питер, 2009. – 352 с.
№ шага п/п
(N)
(N)
Число повто- рений
Цена
Число повто- рений
Цена
1 1
1 1
1 2
N
1
N
1 3
N
1
N
1 4
N
1
N
1 5
N
1
N
1 6
N
1
N
1 7
N
1
N
1 8
N
1
N
1 9
N
1
N
1 10
N
Nlog
2
N
N
Nlog
2
N
11
N
3
N
3 12
N
1
N
1 13
N
Nlog
2
N
N
Nlog
2
N
14
N
3
N
3
№ шага п/п
(N)
(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
1 1
3 1
1 1
1 4
1 1
0 1
5 1
1 0
1 6
1 1
1 1
7 1
1 0
1 8
1 1
0 1
9 1
1 1
1 10 1
6N+2 0
1 11 0
1 1
1 12 0
1 1
1 13 1
1 1
1 14
N
1
N
1 15
N
1
N
1 16
N
1
N
1 17
N
1
N
1 18
N
1
N
1 19
N-1 1
N-1 1
20
N-1 1
0 1
21
N-1 1
0 1
56
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
УДК 519.718
В.В. Тарасов, Н.В. Елкина
К ЗАДАЧЕ КОНТРОЛЯ ВХОДНОЙ ИНФОРМАЦИИ НА СХЕМАХ
ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ С ЗАДЕРЖКАМИ
Рассмотрена задача контроля входной информации на схемах из функ-
циональных элементов в базисе
z
,
,
&,
, где
z – тождественная функция
с задержками.
Ключевые слова: функции алгебры логики с задержками, надежность и
контроль, схемотехника.
Введение. В исследованиях [1-5] по теории функций алгебры логики (ФАЛ) с задержками основной задачей являлось изучение методов синтеза вычислительных устройств на предмет быстродействия. Цель статьи: рассмотрение задачи контроля входной информации на схемах из функциональных элементов в базисе
,
&,
с добавлением к базису элемента, реализующего тождественную функцию
z с задержками, диф- ференцированными по входу. Пусть t – момент времени подачи сигнала (нуля или единицы) на вход элемента
z , тогда на выходе этот сигнал появляется в момент времени
t
, где
1
при подаче на вход нуля и
2
при подаче на вход единицы. Положим для определенности
2 1
. Под ФАЛ с задержками будем понимать пару функций
n
n
x
x
x
x
f
,...,
,
,...,
1 1
, где при одновременной подаче значений переменных
1 1
x
, …,
n
n
x
на входы ФАЛ
n
x
x
f
,...,
1
на выходе получаем значение
n
f
,...,
1
с временной внутренней задержкой
0
,...,
1
n
,
R
. ФАЛ с задержками
n
x
x
f
,
,...,
1
n
x
x ,...,
1
существенно зависит от переменной
i
x , если существует пара соседних наборов по переменной
i
x :
n
i
i
,...,
,
0
,
,...,
1 1
1
и
n
i
i
,...,
,
1
,
,...,
1 1
1
такие, что
f
f
либо
, в противном случае переменная
i
x называется фиктивной.
При добавлении или изъятии фиктивных переменных у ФАЛ с задержками получив- шиеся функции не считаются равными.
Причиной этого служит следующий важный пример. Рассмотрим схему
y
x
S
,
(см. рисунок
1), реализующую функцию
x
, где вход
y
является фиктивным с традиционно функ- циональной точки зрения.
&
x
y
1 2 3 4 5 6
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
53
(для вершин–листьев он пустой). Полученное в процессе работы алгоритма дерево T будет представлять собой массив объектов типа
VERTEX. Вершина v i
, i = 1..||V||, T.vs – начальная вершина. Каждое ребро графа G описывается структурой, которая определяется весом ребра e i
.w и указателями на инцидентные вершины e i
.v1, e i
.v2.
Для поиска оптимальных маршрутов будем применять алгоритм Дейкстры.
//Алгоритм Дейкстры. T – структура данных дерева оптимальных маршрутов, V – множество вершин графа, vs – начальная вершина.
DeicstraAlg(T,V,vs)
1.
Initialize(V,vs)
2.
Q.add(V,vs)
3.
Пока Q
4. vm = Extract-Min(Q);
5.
T.add(vm);
6.
Для всех инцидентных vm ребер vk
7.
Если d[vm.i]>d[vk.i]+w(vk,vm) то
8. d[vm.i] = d[vk.i] + w(vk,vm);
9. p[vm.i] = vk;
Конец Если
Конец Для
Конец Пока
Конец
В приведенной процедуре используется функция Extract – Min, возвращающая объект с минимальным ключом. Реализация данной функции и ее трудоемкость зависят от способа определения списка (очереди). Алгоритм вычис- ляет значения массивов d и p оценок длин оптимальных маршрутов и указателей на роди- тельские таблицы соответственно. Полученные массивы необходимо сохранить.
// Процедура сохранения массивов
SaveAr(v,i)
1.
Если i=0 то
2. v.d1:=d;
3. v.p1:=p;
Иначе
4. v.d2:=d;
5. v.p2:=p;
Конец Если
Конец
Для ребер, участвующих в построении опти- мальных маршрутов, является целесообразным проводить расчет для инцидентных вершин, лежащих ниже по иерархии.
// Процедура нахождения деревьев оптимальных маршрутов для всех вершин графа
GetSPT(T,V,vs)
1.
Q.Add(vs)
2.
Пока Q
3. v:=Q.Get
4.
Для всех v.ci
5.
Q.Add(v.ci.v2)
Конец Для
6.
Если v<>vs то
7. e:=E(v,v.p)
8. tw:=e.w;
9. e.w:=0;
10.
DeicstraAlg(T,V,v)
11.
SaveAr(v,0)
12. e.w:=M
13.
DeicstraAlg(T,V,v)
14.
SaveAr(v,1)
Конец Если
Конец Пока
Конец
В приведенной процедуре М – число, принятое за максимальное в данной системе.
Процедура нахождения деревьев оптимальных маршрутов для графа обходит все вершины графа с формированием списков парных пере- ходов для каждой вершины.
От дерева оптимальных маршрутов из заданной вершины легко перейти к списку парных переходов. Оценки длин оптимальных маршрутов в данном случае будут соответст- вовать приращениям потенциала этой вершины.
При поиске оптимального маршрута особой обработки, как было сказано выше, заслуживает вариант уменьшения веса ребра, не входящего в оптимальный маршрут. В этом случае необхо- димо предварительно проверить вершины, лежа- щие выше по иерархии.
// Процедура проверки на включение в поддере- во вершины v вершин, лежащих выше по иерар- хии относительно вершины v
TestUp(v)
1. v2:=v.P
2.
Пока v2.d>v.d+E(v,v2)
3. v2.d:= v.d+E(v,v2)
4.
Для всех v2.Ci
5.
Если v2.Ci<>v то
6. v2.Ci.d:=v2.d+E(v2,v2.Ci)
Конец Если
Конец Для
7. v:=v2;
8. v2:=v2.P;
Конец Пока
Конец
Для проверки срабатывания парного пере- хода используется условие целесообразности включения ребра в дерево. Отдельно обраба- тываются случаи увеличения и уменьшения оценки длины оптимального маршрута.
// Процедура обработки изменения веса ребра будет выглядеть следующим образом:
PathPT(e,nw)
54
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
1. v1=e.v1 2. v2=e.v2 3.
Если v1.d>e.v2 то
4. v1=e.v2 5. v2=e.v1
Конец Если
6.
Если nw>e.w то
7. dt:=v2.d2 8. pt:=v2.p2 9.
Если not e.InTree то
10.
TestUp(v2)
Конец Если
Иначе
11. dt:=v2.d
12. pt:=v2.p
Конец Если
13.
Q.Add(vs)
14.
Пока Q
15. v:=Q.Get
16.
Для всех v.ci
17.
Q.Add(v.ci.v2)
Конец Для
18.
Если v<>vs то
19. Если v.p.d+E(v.p,v).w>pt[v.i].d+E(pt[v.i],v) то
20. v.p:= pt[v.i]
21. v.d:= pt[v.i].d+E(pt[v.i],v)
Конец Если
Конец Если
Конец Пока
Конец
Рассмотрим работу алгоритма адаптивной ускоренной маршрутизации. Укрупненная схема алгоритма имеет следующий вид.
Шаг 1. Для вершины, являющейся листом дере- ва, производится поиск всех парных переходов без ограничений. Эти списки для удобства дальнейшей работы привязываются к вершине, инцидентной рассматриваемому ребру и распо- ложенной ниже по иерархии.
Шаг 2. Если вершина не является листом дерева, то вычисляются парные переходы для этой вершины и выбираются лучшие значения потен- циалов парных переходов для потомков верши- ны и собственных парных переходов. Подобная процедура выполняется для формирования спис- ков парных переходов в случае увеличения и уменьшения веса ребра.
Шаг 3. Для каждой вершины формируется пол- ный список парных переходов. Число элементов в каждом их этих списков не превышает коли- чества вершин графа. Такое решение позволяет отказаться от предварительной сортировки по- тенциалов или приращений для парных пере- ходов без значительного усложнения алгоритма обработки изменения.
Шаг 4. Для каждой вершины формируется пол- ный список возможных маршрутов, проходящий через ребра, состоящие в отношении парного перехода, включая и ребра, входящие в дерево кратчайших путей.
Шаг 5. Анализируя полученную используемым протоколом маршрутизации информацию, опре- делить, произошло ли изменение метрики для какого-либо ребра: а) если да, то перейти к шагу 6; б) иначе - к шагу 5.
Шаг 6. Используя список парных переходов, определить, требуется ли сделать парный пере- ход: а) если да, то перейти к шагу 7; б) иначе – к шагу 9.
Шаг 7. Для каждой вершины, у которой в список возможных маршрутов входит ребро с изменив- шейся метрикой, определить путь минимальной длины и поместить его в дерево кратчайших путей, тем самым, построив новое дерево кратчайших путей на графе.
Шаг 8. а) передать пакеты по доступным эквивалентным маршрутам; б) установить флаг передачи.
Шаг 9. Пересчитать точки вхождения в дерево и переформировать список маршрутов замены для каждой изменившейся вершины.
Шаг 10. Перейти к шагу 5.
Работа составных частей алгоритма основы- вается на использовании доказанных выше теорем, следовательно, можно сделать вывод о корректности работы всего алгоритма в целом.
Проведем анализ сложности алгоритма адаптивной ускоренной маршрутизации, для чего найдем верхнюю и нижнюю оценки его трудоемкости. Для этого определим оценки для процедур, составляющих алгоритм. Для всех процедур было найдено количество повторений каждого шага и стоимость для верхней и нижней оценок трудоемкости. Трудоемкость модифици- рованного алгоритма Дейкстры составляет:
(N
2
log
2
N).
Результаты анализа трудоемкости остальных процедур сведены в таблицах 1 – 3.
Таблица 1 – Трудоемкость процедуры SaveAr
Верхняя оценка трудоемкости процедуры
SaveAr:
= 1 + 1 + 1 = 3, а нижняя оценка:
= 1 + 1 + 1 = 3.
№ шага п/п
(N)
(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
0 1
3 1
1 0
1 4
0 1
1 1
5 0
1 1
1
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
55
Таблица 2 – Трудоемкость процедуры GetSPT
Верхняя оценка трудоемкости процедуры
GetSPT:
= 15N + 2N
2
log
2
N + 1,
а нижняя оценка:
= 15N + 2N
2
log
2
N + 1.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости по- строения дерева кратчайших путей и получения дополнительной информации:
(N
2
log
2
N) и нижнюю оценку:
(N
2
log
2
N).
Тогда трудоемкость процедуры PathPT запи- шется следующим образом:
Верхняя оценка трудоемкости процедуры
PathPT:
= 10 + 5N + 3(N - 1) + 6N + 2 = 14N + 9, а нижняя оценка:
=8 + 5N + N – 1 = 6N + 7
Таким образом, удается рассчитать дерево кратчайших путей за линейное время в худшем случаи. Такой результат удается получить путем использования дополнительной информации о парных переходах.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости:
(N)
и нижнюю оценку:
(N).
Таким образом, разработанный алгоритм адаптивной ускоренной маршрутизации позво- ляет повысить эффективность функциониро- вания корпоративных сетей.
Таблица 3 – Трудоемкость процедуры PathPT
Заключение. Разработка алгоритма адап- тивной ускоренной маршрутизации позволяет повысить эффективность функционирования корпоративных сетей за счет уменьшения трудоемкости построения таблиц маршрути- зации до величины порядка O(N) в условиях динамически изменяющейся структуры корпора- тивной сети и характеристик линий связи.
Библиографический список
1. Куракин Д.В. Маршрутизаторы для глобаль- ных телекоммуникационных сетей и реализуемые в них алгоритмы // Информационные технологии.–
1996. №2.
2. Олифер В.Г., Олифер Н.А. Основы компью- терных сетей – СПб.: Питер, 2009. – 352 с.
№ шага п/п
(N)
(N)
Число повто- рений
Цена
Число повто- рений
Цена
1 1
1 1
1 2
N
1
N
1 3
N
1
N
1 4
N
1
N
1 5
N
1
N
1 6
N
1
N
1 7
N
1
N
1 8
N
1
N
1 9
N
1
N
1 10
N
Nlog
2
N
N
Nlog
2
N
11
N
3
N
3 12
N
1
N
1 13
N
Nlog
2
N
N
Nlog
2
N
14
N
3
N
3
№ шага п/п
(N)
(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
1 1
3 1
1 1
1 4
1 1
0 1
5 1
1 0
1 6
1 1
1 1
7 1
1 0
1 8
1 1
0 1
9 1
1 1
1 10 1
6N+2 0
1 11 0
1 1
1 12 0
1 1
1 13 1
1 1
1 14
N
1
N
1 15
N
1
N
1 16
N
1
N
1 17
N
1
N
1 18
N
1
N
1 19
N-1 1
N-1 1
20
N-1 1
0 1
21
N-1 1
0 1
56
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
УДК 519.718
В.В. Тарасов, Н.В. Елкина
К ЗАДАЧЕ КОНТРОЛЯ ВХОДНОЙ ИНФОРМАЦИИ НА СХЕМАХ
ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ С ЗАДЕРЖКАМИ
Рассмотрена задача контроля входной информации на схемах из функ-
циональных элементов в базисе
z
,
,
&,
, где
z – тождественная функция
с задержками.
Ключевые слова: функции алгебры логики с задержками, надежность и
контроль, схемотехника.
Введение. В исследованиях [1-5] по теории функций алгебры логики (ФАЛ) с задержками основной задачей являлось изучение методов синтеза вычислительных устройств на предмет быстродействия. Цель статьи: рассмотрение задачи контроля входной информации на схемах из функциональных элементов в базисе
,
&,
с добавлением к базису элемента, реализующего тождественную функцию
z с задержками, диф- ференцированными по входу. Пусть t – момент времени подачи сигнала (нуля или единицы) на вход элемента
z , тогда на выходе этот сигнал появляется в момент времени
t
, где
1
при подаче на вход нуля и
2
при подаче на вход единицы. Положим для определенности
2 1
. Под ФАЛ с задержками будем понимать пару функций
n
n
x
x
x
x
f
,...,
,
,...,
1 1
, где при одновременной подаче значений переменных
1 1
x
, …,
n
n
x
на входы ФАЛ
n
x
x
f
,...,
1
на выходе получаем значение
n
f
,...,
1
с временной внутренней задержкой
0
,...,
1
n
,
R
. ФАЛ с задержками
n
x
x
f
,
,...,
1
n
x
x ,...,
1
существенно зависит от переменной
i
x , если существует пара соседних наборов по переменной
i
x :
n
i
i
,...,
,
0
,
,...,
1 1
1
и
n
i
i
,...,
,
1
,
,...,
1 1
1
такие, что
f
f
либо
, в противном случае переменная
i
x называется фиктивной.
При добавлении или изъятии фиктивных переменных у ФАЛ с задержками получив- шиеся функции не считаются равными.
Причиной этого служит следующий важный пример. Рассмотрим схему
y
x
S
,
(см. рисунок
1), реализующую функцию
x
, где вход
y
является фиктивным с традиционно функ- циональной точки зрения.
&
x
y
1 2 3 4 5 6