Суть алгоритма Ивена (алгоритм № 2)

Алгоритм Ивена, проверяющий, имеет ли сеть узловую связность, равную, по крайней мере m, выполняется следующим образом.

Шаг 1. Пронумеруйте узлы от 1 до N.

Шаг 2. Сформируйте подмножество из узлов с номерами от 1 до m, где m – искомая связность.

Шаг 3. Проверьте, что каждый узел в этом подмножестве имеет, по крайней мере, m маршрутов с разделенными узлами к каждому из других узлов в этом подмножестве.

Шаг 4. Если предыдущий шаг неуспешен, то связность меньше m. Если шаг успешен, то перейдите к следующему этапу.

Шаг 5. Для каждого из оставшихся j узлов (m £ j £ N) сформируйте подмножество

узлов L, содержащие набор, заданный в шаге 1 (размера m), увеличенный на число узлов из множества J.

Шаг 6. Добавьте к сети новый (фиктивный) узел X и соедините его с каждым узлом

множества L. Проверьте, что между узлом X и каждым узлом j существует, по крайней мере, m маршрутов с разделенными узлами. Затем добавьте к множеству L узел j, удаленный из множества J, и продолжите процедуру со следующим узлом j.

Если выполнение всех шагов завершается успехом, сеть имеет связность равную m.

 

При исследовании устойчивости и оптимальности структуры транспортной сети связи произвольной структуры целесообразно аппроксимировать ее какой-либо базовой топологией:

кольцевой структурой, двойной кольцевой структурой или К - связной структурой. Результаты исследований целесообразно свести в таблицы по приведенному образцу.

В таблицах приняты следующие обозначения:

N - число узлов связи;

m - связность узлов связи;

L - средняя длина маршрута сети (определяется на основании эмпирических данных);

r - число звеньев сети (число ребер графа сети).

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

приняв его равным R ₀ =L / r.

Для оценки устойчивости сети вводится коэффициент защиты элементов сети Z.

Значение этого параметра целесообразно изменять в пределах от 0,1 до 0,99, при этом необходимо учитывать, что P_кр (z) £ 1. Опыт эксплуатации транспортных сетей различных базовых топологий показывает, что вероятность выхода сети из строя может быть определена по формуле

 

(1)

а структурная устойчивость может быть определена по формуле

 

В выражении (2) параметр K_n выражает отсутствие готовности транспортной системы к выполнению поставленных задач. Этот параметр может принимать значения в пределах от 0,1 до 0,3.

Параметр t определяет относительную интенсивность восстановления отказов. Целесообразно изменять этот параметр в пределах от 0,5 до 0.95, при этом t = 0,5 характеризует очень низкие показатели по восстановлению системы связи.

Запас структурной устойчивости определяется из условия поражения транспортной сети связи с вероятностью P_n = 0,5, что является наиболее худшим условием.

 

 

ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ

1. По заданному варианту (таблица 1)представить топологию сети и определить предложенным способом связность сети.

2. Вычислить параметр P_кр (Z), изменяя значение Z в пределах от 0,4 до 0,95. Построить график зависимости.

3. Используя самостоятельно выбранные значения P_кр (Z), построить двумерный график Q_{стр.уст.}(K_n, t) и оценить Q для худшего и лучшего значения Q_{стр.уст.}(K_n, t).

4. Сравнить полученные результаты численных исследований для различных топологий транспортное сети связи.

5. Составить отчет о проведенных исследованиях с необходимым табличным и графическим материалом. В отчете должны быть представлены:

- структурная схема сети связи и результаты исследований по оценке связности сети заданной структуры;

- график зависимости P_кр (Z) и результаты расчетов параметра

- выводы по полученным данным расчетов и сравнительным оценкам.

 

Варианты заданий

(оценка связности сети заданной структуры)

Вариант	Топология сети	Способ оценки связности сети
	ABCLEFA, BE, AC, DF	По Клейтону
	ABCLEFA, BE, AC, DF	По Ивену
	ABCDKFA, AK, CF, BF	По Клейтону
	ABCDKFA, AK, CF, BF	По Ивену
	ABCDFA, AC, BF, BD	По Клейтону
	ABCDFA, AC, BF, BD	По Ивену
	ABCDA, AD,CB	По Клейтону
	ABCDA, AD,CB	По Ивену
	ABCDFEA, BE, BF, CA, CE, CF, DA	По Клейтону
	ABCDFEA, BE, BF, CA, CE, CF, DA	По Ивену
	ABCDFEA, BE, CF	По Клейтону
	ABCDFEA, BE, CF	По Ивену
	ABCDFE, AK,BK, CK, DK, FK, EK	По Клейтону
	ABCDFE, AK,BK, CK, DK, FK, EK	По Ивену
	АBCDFEA, CE, BD, AF	По Клейтону

 

Варианты заданий

(оценка структурной устойчивости транспортной сети связи)

Вариант	Структура сетей	N	L (кольцевая)	L (m -связная)
	Кольцевая; 3-связная	9; 20; 40	2.53; 4,76; 9,26	1,63; 3,13; 5,37
	Двойн. кольцевая; 4-связная	7; 23; 45	1,63; 2,7; 3, 09	1,18; 2,8; 4,26
	Кольцевая; 5-связная	9; 17; 38	1.53; 4,26; 6,26	1,83; 4,13; 6,37
	Двойн. кольцевая; 3-связная	8; 22; 39	1,22; 2,6; 3, 5	1,08; 3,8; 5,16
	Кольцевая; 3-связная	9; 23; 40	1.53; 4,46; 9,87	1,53; 2,13; 4,27
	Двойн. кольцевая; 4-связная	9; 20; 45	1,6; 2,79; 3,49	2,18; 3,8; 5,26
	Кольцевая; 5-связная	9; 22; 40	2.53; 5,26; 7,26	1,83; 4,13; 6,37
	Двойн. кольцевая; 3-связная	6; 25; 49	3,72; 2,71; 3, 69	1,08; 3,8; 5,16
	Кольцевая; 6-связная	9; 27; 42	2.53; 4,76; 9,26	1,63; 3,13; 5,37
	Двойн. кольцевая; 3-связная	7; 21; 49	1,63; 2,7; 3, 09	1,18; 2,8; 4,26
	Кольцевая; 4-связная	8; 26; 41	1.53; 4,26; 6,26	1,83; 4,13; 6,37
	Двойн. кольцевая; 3-связная	5; 23; 45	1,22; 2,6; 3, 5	1,08; 3,8; 5,16
	Кольцевая; 3-связная	8; 23; 44	1.53; 4,46; 9,87	1,53; 2,13; 4,27
	Двойн. кольцевая; 4-связная	9; 21; 38	1,6; 2,79; 3,49	2,18; 3,8; 5,26
	Кольцевая; 5-связная	7; 22; 35	2.53; 5,26; 7,26	1,83; 4,13; 6,37

 

Контрольные вопросы

1. Дайте определение транспортной сети связи.

2. Перечислите базовые топологии сетей связи.

3. Дайте определение понятиям «Связность по звеньям», «Связность по узлам», в каком отношении они находятся друг к другу.

4. Суть алгоритма Клейтона для определения связности сети.

5. Суть алгоритма Ивена для определения связности сети.

6. Дайте приеме равномерной m - связной структуры транспортной сети.

7. Что понимается под структурной устойчивостью сети связи?

 

ЛИТЕРАТУРА

1. Сети ЭВМ и телекоммуникации. Методические указания по выполнению лабораторного практикума / А.И. Фролов. Орел, 2006г.

2. Технологии АТМ и FR: сборник лабораторных работ/ сост. А.А. Гладких.-

Ульяновск: УлГУ, 2007. – 19 с.

3.Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. – СПб.: Питер, 2006. - 672с.

4. Сети ЭВМ. Методические указания по выполнению лабораторных работ /Тула, 2005г.