Исследование процессов маршрутизации
1.4.Расчет пути с минимальным количеством переходов
Преобразуем исходный граф в неориентированный невзвешенный граф.
Рисунок.9 Неориентированный, невзвешенный граф
V2
V1 V3
Произведем поиск кратчайшего пути по алгоритму Дейкстры.
Таблица№3
№ |
L(2) |
Путь |
L(3) |
Путь |
L(4) |
Путь |
L(5) |
Путь |
L(6) |
Путь |
1 |
∞ |
- |
5 |
1-3 |
∞ |
- |
1 |
1-5 |
5 |
1-6 |
2 |
6 12 |
1-5-2 1-6-2 |
5 6 |
1-3 1-5-3 |
11 |
1-3-4 |
1 9 |
1-5 1-3-5 |
5 |
1-6 |
3 |
6 12 17 14 |
1-5-2 1-6-2 1-3-4-2 1-3-5-2 |
5 6 |
1-4-3 1-5-3 |
11 12 14 9 |
1-4 1-6-2-4 1-6-2-4 |
1 9 13 |
1-5 1-3-5 1-6-2-5 |
5 9 |
1-6 1-5-2-6 |
4 |
6 18 |
1-5-2 1-5-3-4-2 |
5 6 18 15 10 |
1-3 1-5-3 1-6-2-5-3 1-6-2-4-3 1-5-2-4-3 |
9 17 |
1-5-2-4 1-3-5-2-4 |
10 20 |
1-6-2-5 1-3-4-2-5 |
1 23 |
1-6 1-3-5-2-6 |
1.5 Выводы
В итоге оба алгоритма поиска кратчайшего пути привели нас к одинаковому результату. Но по алгоритму Беллмана-Форда результата мы достигли быстрее.
Достоинством алгоритма Дейсктры является то, что на каждом шаге мы находим кратчайшее расстояние еще до одной вершины, а по алгоритму Беллмана- Форда кратчайшее расстояние до любой вершины определяется только после прохождения всего алгоритма.
Расчет пути с минимальным количеством переходов привел к другим результатам, так как исходный граф был преобразован в неориентированный невзвешанный граф.
2. Маршрутизация
Цель маршрутизации - доставка пакетов по назначению с максимизацией эффективности. Чаще всего эффективность выражена взвешенной суммой времен доставки сообщений при ограничении снизу на вероятность доставки. Маршрутизация сводится к определению направлений движения пакетов в маршрутизаторах. Выбор одного из возможных в маршрутизаторе направлений зависит от текущей топологии сети (она может меняться хотя бы из-за временного выхода некоторых узлов из строя), длин очередей в узлах коммутации, интенсивности входных потоков и т.п.
2.1 Основы маршрутизации
Алгоритмы маршрутизации можно дифференцировать, основываясь на нескольких ключевых характеристиках. Во-первых, на работу результирующего протокола маршрутизации влияют конкретные задачи, которые решает разработчик алгоритма. Во-вторых, существуют различные типы алгоритмов маршрутизации, и каждый из них по-разному влияет на сеть и ресурсы маршрутизации. И наконец, алгоритмы маршрутизации используют разнообразные показатели, которые влияют на расчет оптимальных маршрутов.
Алгоритмы маршрутизации включают процедуры:
- измерение и оценивание параметров сети;
- принятие решения о рассылке служебной информации;
- расчет таблиц маршрутизации (ТМ);
- реализация принятых маршрутных решений.
В зависимости от того, используется ли при выборе направления информация о состоянии только данного узла или всей сети, различают алгоритмы изолированные и глобальные. Если ТМ реагирует на изменения состояния сети, то алгоритм адаптивный (динамический), иначе фиксированный (статический), а при редких корректировках - квазистатический. В статических маршрутизаторах изменения в ТМ вносит администратор сети.
Простейший алгоритм - изолированный, статический. Алгоритм кратчайшей очереди в отличие от простейшего является адаптивным, пакет посылается по направлению, в котором наименьшая очередь в данном узле. Лавинный алгоритм - многопутевой, основан на рассылке копий пакета по всем направлениям, пакеты сбрасываются, если в данном узле другая копия уже проходила. Очевидно, что лавинный алгоритм обеспечивает надежную доставку, но порождает значительный трафик и потому используется только для отдельных пакетов большой ценности.
Наиболее широко используемые адаптивные протоколы (методы) маршрутизации - RIP (Routing Information Protocol) и OSPF (Open Shortest Path First). Метод RIP иначе называется методом рельефов. Он основан на алгоритме Беллмана-Форда и используется преимущественно на нижних уровнях иерархии сети. В сетях, работающих в соответствии с методом OSPF, информация о любом изменении в сети рассылается лавинообразно.
Другие рефераты на тему «Программирование, компьютеры и кибернетика»:
- Анализ принципов администрирования операционных систем (на примере Windows 2003)
- Расчет и исследование динамических показателей и показателей качества двухконтурных систем автоматического управления
- Моделирование компьютерных сетей
- Мастер функций и мастер диаграмм в табличном процессоре Excel
- Разработка обучающе–тестирующей системы с использованием Интернет–технологий
Поиск рефератов
Последние рефераты раздела
- Основные этапы объектно-ориентированного проектирования
- Основные структуры языка Java
- Основные принципы разработки графического пользовательского интерфейса
- Основы дискретной математики
- Программное обеспечение системы принятия решений адаптивного робота
- Программное обеспечение
- Проблемы сохранности информации в процессе предпринимательской деятельности