ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ» Кафедра Мультисервисных сетей и информационной безопасности Н.В. Киреева, М.А. Буранова Моделирование сети Ethernet Методические указания к выполнению лабораторной работы Самара, 2015 УДК БКК Рекомендовано к изданию методическим советом ПГУТИ, Протокол № 18 ,от 02.04.2015 г. Рецензент: Доцент кафедры МСИБ, к.т.н. <...> Моделирование сети Ethernet: методические указания к выполнению лабораторной работы / Н.В. Киреева, М. <...> Методические указания «Моделирование сети Ethernet» содержат необходимую информацию для написания лабораторных работ, разработано в соответствии с ФГОС ВПО по направлению подготовки специальностей 11.03.02, 10.05.02 и предназначено для выполнения лабораторных работ студентами. ©, Киреева Н.В., Буранова М.А., 2015 2 1. <...> Цель работы Исследовать методы маршрутизации в компьютерных сетях, провести моделирование сети Ethernet и рассчитать характеристики сети. <...> Находит кратчайшее расстояние от одной из вершин графа до всех остальных. <...> Алгоритм работает только для графов без рёбер отрицательного веса. <...> Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. <...> Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. <...> 1) Инициализация Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. <...> Это отражает то, что расстояния от a до других вершин пока неизвестны. <...> 2) Шаг алгоритма Если все вершины посещены, алгоритм завершается. <...> В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. <...> Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. <...> Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. <...> Для каждого соседа <...>
Моделирование_сети_Ethernet_Методические_указания_к_выполнению_лабораторных_работ.pdf
УДК
БКК
Рекомендовано к изданию методическим советом ПГУТИ,
Протокол № 18 ,от 02.04.2015 г.
Рецензент:
Доцент кафедры МСИБ, к.т.н. В.В. Пугин
Киреева, Н.В. Буранова М.А.
Моделирование сети Ethernet: методические указания к выполнению лабораторной работы / Н.В.
Киреева, М.А Буранова. - Самара: ПГУТИ, 2015. – 28с.
Методические указания «Моделирование сети Ethernet» содержат необходимую информацию для
написания лабораторных работ, разработано в соответствии с ФГОС ВПО по направлению
подготовки специальностей 11.03.02, 10.05.02 и предназначено для выполнения лабораторных
работ студентами.
©, Киреева Н.В., Буранова М.А., 2015
2
Стр.2
1. Цель работы
Исследовать методы маршрутизации в компьютерных сетях, провести
моделирование сети Ethernet и рассчитать характеристики сети.
2. Общие понятия
Алгори́ тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах,
изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит
кратчайшее расстояние от одной из вершин графа до всех остальных.
Алгоритм работает только для графов без рёбер отрицательного веса.
Алгоритм широко применяется в программировании и технологиях,
например, его использует протокол OSPF для устранения кольцевых
маршрутов.
Каждой вершине из V сопоставим метку — минимальное известное
расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом
шаге он «посещает» одну вершину и пытается уменьшать метки. Работа
алгоритма завершается, когда все вершины посещены.
1) Инициализация
Метка самой вершины a полагается равной 0, метки остальных вершин
— бесконечности. Это отражает то, что расстояния от a до других вершин
пока неизвестны. Все вершины графа помечаются как непосещённые.
2) Шаг алгоритма
Если все вершины посещены, алгоритм завершается. В противном
случае, из ещё не посещённых вершин выбирается вершина u, имеющая
минимальную метку. Мы рассматриваем всевозможные маршруты, в
которых u является предпоследним пунктом. Вершины, в которые ведут
рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u,
кроме отмеченных как посещённые, рассмотрим новую длину пути, равную
сумме значений текущей метки u и длины ребра, соединяющего u с этим
соседом. Если полученное значение длины меньше значения метки соседа,
заменим значение метки полученным значением длины. Рассмотрев всех
соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
3
Стр.3