ВУЗ:
Составители:
Рубрика:
4
Лабораторная работа № 1
Цель работы: оценить связность сети предложенной топологии, определить устойчивость
транспортной сети аппроксимированной одной из базовых топологий.
Теоретические сведения
Ключевой концепцией коммуникационных систем является понятие связности, которая
определяет, насколько легко добраться из одной точки сети в другую. Существует несколько
способов оценки данного параметра. Выбор конкретного способа – это задача маршрутизации.
Вместе с этим, возникает другая проблема: насколько хорошо различные части сети соединены
друг с другом. Существует также проблема надежности. Если узел или звено сети отказывают,
каким образом доставить необходимую информацию в требуемый узел сети.
Различают связность по звеньям и по узлам. Связность по звеньям сети не может
превышать ее минимальной степени, а
связность по узлам не может быть больше, чем связность
по звеньям. Регулярными методами оценки связности сети являются алгоритм Клейтмана и
алгоритм Ивена.
Суть алгоритма Клейтмана (алгоритм № 1)
Шаг 1. Выберите любой узел N
1
.
Шаг 2. Убедитесь, что узловая связность выбранного узла N
1
со всеми другими узлами
равна, по крайней мере, m.
Шаг 3. Удалите узел N
1
и все его связи.
Шаг 4. Выберите второй узел N
2
.
Шаг 5. Убедитесь, что узел N
2
имеет m-1 соединений со всеми другими узлами.
Шаг 6. Удалите узел N
2
и все его связи.
Шаг 7. Выберите третий узел N
3
.
Шаг 8. Убедитесь, что узел N
3
имеет, по крайней мере, m-2 соединений со всеми
другими узлами.
Шаг 9. Повторяйте процедуру, пока не дойдете до узла m, т.е. выберите узел N
m
и
убедитесь, что он соединен, по крайней мере, еще с одним узлом.
Если проверки всех шагов проходят удовлетворительно, то сеть имеет связность, равную,
по крайней мере, m. Если хотя бы в одной точке алгоритма проверка не выполняется, то
связность не равна m.
Суть алгоритма Ивена (алгоритм № 2)
Алгоритм Ивена, проверяющий,
имеет ли сеть узловую связность, равную, по крайней
мере m, выполняется следующим образом.
Шаг 1. Пронумеруйте узлы от 1 до N.
Шаг 2. Сформируйте подмножество из узлов с номерами от 1 до m, где m - искомая
связность.
Шаг 3. Проверьте, что каждый узел в этом подмножестве имеет, по крайней мере, m
маршрутов
с разделенными узлами к каждому из других узлов в этом подмножестве.
Шаг 4. Если предыдущий шаг неуспешен, то связность меньше m. Если шаг успешен, то
перейдите к следующему этапу.
Шаг 5. Для каждого из оставшихся j узлов )( Njm
≤
≤
сформируйте подмножество
узлов
L, содержащие набор, заданный в шаге 1 (размера m), увеличенный на число узлов
из множества
J.
Страницы
- « первая
- ‹ предыдущая
- …
- 2
- 3
- 4
- 5
- 6
- …
- следующая ›
- последняя »
