Исследование процессов маршрутизации - Программирование, компьютеры и кибернетика курсовая работа
Главная
Программирование, компьютеры и кибернетика
Исследование процессов маршрутизации
Использование понятий из теории графов при разработке сетей и алгоритмов маршрутизации. Построение матрицы смежности и взвешенного ориентировочного графа. Результаты работы алгоритмов Дейкстры и Беллмана-Форда. Протоколы обмена маршрутной информацией.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Федеральное агентство железнодорожного транспорта
Уральский государственный университет путей сообщения
Кафедра Автоматики, телемеханики и связи на ж. д. транспорте
по дисциплине: "Передача дискретной информации"
на тему: "Исследование процессов маршрутизации"
1. Алгоритм поиска кратчайшего пути
7. Протоколы обмена маршрутной информацией
1. Алгоритмы поиска кратчайшего пути
Компьютерные сети, как правило, представляются в виде графов, при этом коммутаторы и маршрутизаторы сетей являются узлами графа, а линии связи представляют собой ребра графа. Ряд понятий из теории графов оказываются полезными при разработке сетей и алгоритмов маршрутизации.
Граф состоит из объектов двух типов: вершин (vertices) или узлов (nodes) и ребер (edges) или связей (links), при этом каждое ребро графа определяется как неупорядоченная пара вершин. При изображении графов вершины представляются точками или кружками, а ребра -- линиями, соединяющими вершины. Величина графа характеризуется количеством вершин |V|, называемым порядком (order) графа, а число ребер называется размером (size) графа. Граф также часто представляется в виде матрицы смежности (adjacency matrix). Вершины нумеруются произвольным образом от 1 до |V|.
Два ребра, инцидентные одной и той же паре вершин, называются параллельными (parallel). Ребро, инцидентное всего одной вершине, называется петлей (loop). Граф, в котором отсутствуют петли и параллельные ребра, называется простым графом (simple graph).
Ориентированный граф (digraph) состоит из множества вершин V и множества ребер, при этом каждое ребро определяется как упорядоченная пара вершин. Вершины ориентированных графов также обозначаются точками или кружками, а ребра -- стрелками, соединяющими вершины. Как правило, в ориентированных графах допускается наличие параллельных ребер при условии, что параллельные ребра ориентированы в противоположном направлении. Такие ориентированные графы хорошо подходят для представления компьютерных сетей, в которых каждое ребро обозначает поток данных в одном направлении между узлами сети.
Сеть с коммутацией пакетов (или сеть ретрансляции кадров, или сеть ATM) но рассматривать как ориентированный граф, в котором каждая вершина соответствует узлу коммутации пакетов, а линии связи между узлами соответствует пара параллельных ребер, по каждому из которых данные передаются в одном направлении. В такой сети для передачи пакета от узла-источника узлу-получателя по разным линиям через несколько коммутаторов пакетов требуется принять решение о выборе маршрута. Эта задача эквивалентна поиску пути в графе. Если два маршрутизатора напрямую соединены к одной и той же локальной или глобальной сети, тогда это двусторонне соединение соответствует паре параллельных ребер, соединяющих соответствующие вершины. Если к сети напрямую присоединены более двух маршрутизаторов, тогда эта сеть представляется в виде множества пар параллельных ребер, каждая из которых соединяет два маршрутизатора. В объединенной сети для передачи IP-дейтаграммы от маршрутизатора-источника к маршрутизатору-приемнику по разным линиям через разные сети и маршрутизаторы пакетов требуется принять решение о выборе маршрута. Если выбирается маршрут с минимальным количеством ретрансляционных участков (хопов), тогда каждому ребру, соответствующему ретрансляционному участку, назначается единичный вес. Эта задача соответствует поиску кратчайшего пути в обычном (не взвешенном) графе. Но чаще всего каждому ретрансляционному участку в соответствие ставится определенная величина, называемая стоимостью (cost) передачи. Эта величина может быть обратно пропорциональной пропускной способности линии, прямо пропорциональной текущей нагрузке на эту линию или представлять собой некую комбинацию подобных параметров. Стоимость использования ретрансляционного участка может быть разной в разных направлениях. Например, это справедливо в случае, если стоимость использования ретрансляционного участка пропорциональна длине очереди дейтаграмм, ждущих передачи. В теории графов задаче нахождения пути с наименьшей стоимостью соответствует задача поиска пути с наименьшей длиной во взвешенном ориентированном графе.
Рисунок 2.1 - Взвешенный ориентировочный граф
Алгоритм находит кратчайшие пути от данной вершины-источника до всех остальных вершин, перебирая пути в порядке увеличения их длин. Работа алгоритма проходит поэтапно. К k-му шагу алгоритм находит k кратчайших (с наименьшей стоимостью) путей к k вершинам, ближайшим к вершине-источнику. Эти вершины образуют множество Т. На шаге (k + 1) к множеству Т добавляется вершина, ближайшая к вершине-источнику среди вершин, не входящих во множество Т. При добавлении каждой новой вершины к множеству Т определяется путь к ней от источника. Дерево -- связующее дерево для вершин, принадлежащих множеству Т, включая ребра, входящие в пути с наименьшей стоимостью от вершины s до каждой вершины множества Т. Введем обозначения: N - множество вершин сети; s - вершина-источник; Т - множество вершин, уже обработанных алгоритмом; L(n) - минимальная стоимость пути от вершины s до вершины п, известного на данный момент алгоритму (по завершении работы алгоритма это минимальная стоимость пути от вершины s до вершины п). Алгоритм состоит из трех шагов. Шаги 2 и 3 повторяются до тех пор, пока множество T не совпадет с множеством N. Это значит, что шаги 2 и 3 повторяются, пока для всех вершин сети не будут найдены окончательные пути.
Т = Дерево = {s}, то есть множество исследованных вершин состоит пока что только из вершины-источника. Стоимости начальных путей к соседним вершинам представляют собой просто стоимости линий связи.
Найти следующую вершину, не принадлежащую множеству T и имеющую путь от вершины s с минимальной стоимостью, и включить эту вершину во множество T и в Дерево. Кроме того, к дереву добавляется ребро, инцидентное этой вершине и вершине множества T, входящей в путь с минимальной стоимостью. То есть находим вершину x Т такую, что
Добавить вершину х к множеству T и к дереву; добавить к дереву ребро, инцидентное вершине х, составляющее компонент пути L(x) с минимальной стоимостью - последний ретрансляционный участок пути.
3. Обновить путь с минимальной стоимостью.
L(n) = min[L(n), L(x) + w(x, п)] для всех пТ.
Если последняя величина минимальна, то с этого момента путь от вершины до вершины п представляет собой конкатенацию пути от вершины s до вершины х и пути от вершины х до вершины п. Алгоритм завершает работу, когда все вершины добавлены к множеству Т.
Таблица 1 - Результаты работы алгоритма Дейкстры для заданного графа
Рисунок 3 - Применение алгоритма Дейкстры к графу, представленному на рис. 2.1
Алгоритмы маршрутизации можно дифференцировать, основываясь на нескольких ключевых характеристиках. Во-первых, на работу результирующего протокола маршрутизации влияют конкретные задачи, которые решает разработчик алгоритма. Во-вторых, существуют различные типы алгоритмов маршрутизации, и каждый из них по-разному влияет на сеть и ресурсы маршрутизации. И наконец, алгоритмы маршрутизации используют разнообразные показатели, которые влияют на расчет оптимальных маршрутов.
Цели разработки алгоритмов маршрутизации
При разработке алгоритмов маршрутизации часто преследуют одну или несколько из перечисленных ниже целей:
2. Простота и низкие непроизводительные затраты
Оптимальность, вероятно, является самой общей целью разработки. Она характеризует способность алгоритма маршрутизации выбирать "наилучший" маршрут. Наилучший маршрут зависит от показателей и от "веса" этих показателей, используемых при проведении расчета.
2. Простота и низкие непроизводительные затраты
Алгоритмы маршрутизации разрабатываются как можно более простыми. Другими словами, алгоритм маршрутизации должен эффективно обеспечивать свои функциональные возможности, с минимальными затратами программного обеспечения и коэффициентом использования. Особенно важна эффективность в том случае, когда программа, реализующая алгоритм маршрутизации, должна работать в компьютере с ограниченными физическими ресурсами.
Алгоритмы маршрутизации должны обладать живучестью. Другими словами, они должны четко функционировать в случае неординарных или непредвиденных обстоятельств, таких как отказы аппаратуры, условия высокой нагрузки и некорректные реализации. Т.к. роутеры расположены в узловых точках сети, их отказ может вызвать значительные проблемы.
Алгоритмы маршрутизации должны быстро сходиться. Сходимость - это процесс соглашения между всеми роутерами по оптимальным маршрутам. Когда какое-нибудь событие в сети приводит к тому, что маршруты или отвергаются, или становятся доступными, роутеры рассылают сообщения об обновлении маршрутизации.
К типам алгоритмов маршрутизации относят:
2. одномаршрутный или многомаршрутный;
3. одноуровневый или иерархический;
4. с интеллектом в главной вычислительной машине или в роутере;
6. алгоритм состояния канала или вектора расстояний.
Рассмотрим подробнее каждый тип алгоритма маршрутизации.
1. Статические или динамические алгоритмы
Распределение статических таблиц маршрутизации устанавливается администратором сети до начала маршрутизации. Алгоритмы, использующие статические маршруты, просты для разработки и хорошо работают в окружениях, где трафик сети относительно предсказуем, а схема сети проста. Статические системы маршрутизации не могут реагировать на изменения в сети.
Динамические алгоритмы маршрутизации подстраиваются к изменяющимся обстоятельствам сети в масштабе реального времени. Если в сообщении указывается, что имело место изменение сети, программы маршрутизации пересчитывают маршруты и рассылают новые сообщения о корректировке маршрутизации.
2. Одномаршрутные или многомаршрутные алгоритмы
Некоторые сложные протоколы маршрутизации обеспечивают множество маршрутов к одному и тому же пункту назначения; одномаршрутные алгоритмы не могут делать этого.
3. Одноуровневые или иерархические алгоритмы
В одноуровневой системе маршрутизации все роутеры равны по отношению друг к другу. В иерархической системе маршрутизации некоторые роутеры формируют то, что составляет основу маршрутизации.
4. Алгоритмы с интеллектом в главной вычислительной машине или в роутере
Алгоритмы с интеллектом в главной вычислительной машине предполагают, что конечный узел источника определяет весь маршрут. В системах маршрутизации от источника роутеры действуют просто как устройства хранения и пересылки пакета, без всяких раздумий отсылая его к следующей остановке.
Другие алгоритмы предполагают, что главные вычислительные машины ничего не знают о маршрутах. При использовании этих алгоритмов роутеры определяют маршрут через объединенную сеть, базируясь на своих собственных расчетах - это алгоритмы с интеллектом в роутере.
5. Внутридоменные или междоменные алгоритмы
Некоторые алгоритмы маршрутизации действуют только в пределах доменов; другие - как в пределах доменов, так и между ними.
6. Алгоритмы состояния канала или вектора расстояния
Алгоритмы состояния канала направляют потоки маршрутной информации во все узлы объединенной сети. Однако каждый роутер посылает только ту часть маршрутной таблицы, которая описывает состояние его собственных каналов. Алгоритмы вектора расстояния (известные также как алгоритмы Беллмана-Форда) требуют от каждого роутера посылки всей или части своей маршрутной таблицы, но только своим соседям.
К основным показателям алгоритмов (метрики) относят:
Некоторые протоколы маршрутизации позволяют администраторам сети назначать произвольные цены на каждый канал сети. В этом случае длиной тракта является сумма расходов, связанных с каждым каналом, который был траверсирован.
Надежность, в контексте алгоритмов маршрутизации, относится к надежности каждого канала сети.
Под задержкой маршрутизации обычно понимают отрезок времени, необходимый для передвижения пакета от источника до пункта назначения через объединенную сеть.
Полоса пропускания является оценкой максимально достижимой пропускной способности канала.
7. Протокол обмена маршрутной информацией
Все протоколы обмена маршрутной информацией стекаTCP/IP относятся к классу адаптивных протоколов, которые в свою очередь делятся на две группы, каждая из которых связана с одним из следующих типов алгоритмов:
· дистанционно-векторный алгоритм (Distance Vector Algorithms, DVA),
· алгоритм состояния связей (Link State Algorithms, LSA).
В алгоритмах дистанционно-векторного типа каждый маршрутизатор периодически и широковещательно рассылает по сети вектор расстояний от себя до всех известных ему сетей. Под расстоянием обычно понимается число промежуточных маршрутизаторов через которые пакет должен пройти прежде, чем попадет в соответствующую сеть. Может использоваться и другая метрика, учитывающая не только число перевалочных пунктов, но и время прохождения пакетов по связи между соседними маршрутизаторами. Получив вектор от соседнего маршрутизатора, каждый маршрутизатор добавляет к нему информацию об известных ему других сетях, о которых он узнал непосредственно(если они подключены к его портам) или из аналогичных объявлений других маршрутизаторов, а затем снова рассылает новое значение вектора по сети. В конце-концов, каждый маршрутизатор узнает информацию об имеющихся в интерсети сетях и о расстоянии до них через соседние маршрутизаторы.
Наиболее распространенным протоколом, основанным на дистанционно-векторном алгоритме, является протокол RIP.
Алгоритмы состояния связей обеспечивают каждый маршрутизатор информацией, достаточной для построения точного графа связей сети. Все маршрутизаторы работают на основании одинаковых графов, что делает процесс маршрутизации более устойчивым к изменениям конфигурации. Широковещательная рассылка используется здесь только при изменениях состояния связей, что происходит в надежных сетях не так часто.
Протоколом, основанным на алгоритме состояния связей, в стеке TCP/IP является протокол OSPF.
· ответ (response) - рассылка вектора расстояний;
· запрос (request) - маршрутизатор (например, после своей загрузки) запрашивает у соседей их маршрутные таблицы или данные об определенном маршруте.
Через определенное время модуль RIP производит "сборку мусора" - удаляет из таблицы маршрутов все сети, расстояние до которых бесконечно. При получении сообщения типа "ответ" для каждого содержащегося в нем элемента вектора расстояний модуль RIP выполняет следующие действия:
· проверяет корректность адреса сети и маски, указанных в сообщении;
· проверяет, не превышает ли метрика (расстояние до сети) бесконечности;
· некорректный элемент игнорируется;
· если метрика меньше бесконечности, она увеличивается на 1;
· производится поиск сети, указанной в рассматриваемом элементе вектора расстояний, в таблице маршрутов;
· если запись о такой сети в таблице маршрутов отсутствует и метрика в полученном элементе вектора меньше бесконечности, сеть вносится в таблицу маршрутов с указанной метрикой; в поле "Следующий маршрутизатор" заносится адрес маршрутизатора, приславшего сообщение; запускается таймер для этой записи в таблице;
· если искомая запись присутствует в таблице с метрикой больше, чем объявленная в полученном векторе, в таблицу вносятся новые метрики и, соответственно, адрес следующего маршрутизатора;
· если искомая запись присутствует в таблице и отправителем полученного вектора был маршрутизатор, указанный в поле "Следующий маршрутизатор" этой записи, то таймер для этой записи перезапускается; более того, если при этом метрика в таблице отличается от метрики в полученном векторе расстояний, в таблицу вносится значение метрики из полученного вектора;
· во всех прочих случаях рассматриваемый элемент вектора расстояний игнорируется.
Сообщения типа "ответ" рассылаются модулем RIP каждые 30 с по широковещательному адресу; рассылка "ответа" может происходить также вне графика, если маршрутная таблица была изменена (triggered response). Стандарт требует, чтобы triggered response рассылался не немедленно после изменения таблицы маршрутов, а через случайный интервал длительностью от 1 до 5 с. Эта мера позволяет несколько снизить нагрузку на сеть.
При получении сообщения типа "запрос" с адресом 0.0.0.0 маршрутизатор рассылает в соответствующую сеть обычное сообщение типа ответ. При получении запроса с любым другим значением в поле "IP Address" посылается ответ, содержащий информацию об указанных сетях. Такой ответ посылается на адрес запросившего маршрутизатора (не широковещательно).
1. Столлингс В. Современные компьютерные сети. - 2003
2. RFC 1058. Routing Information Protocol
Понятие и классификация алгоритмов маршрутизации. Основное определение теории графов. Анализ и разработка алгоритмов Дейкстры и Флойда на языке программирования C# для определения наилучшего пути пакетов, передаваемых через сеть. Их сравнительный анализ. курсовая работа [1,2 M], добавлен 16.05.2015
Цель маршрутизации - доставка пакетов по назначению с максимизацией эффективности. Построение алгоритмов поиска кратчайшего пути маршрутизации, расчёт пути с минимальным количеством переходов. Характеристики протокола RIP и построение маршрутных таблиц. курсовая работа [74,1 K], добавлен 26.08.2010
Разработка и использование протокола маршрутизации RIP в небольших и сравнительно однородных сетях. Причины неустойчивой работы по протоколу, их устранение. Применения протокола Hello для обнаружения соседей и установления с ними отношений смежности. курсовая работа [264,0 K], добавлен 06.06.2009
Описание систем управления процессами маршрутизации пакетов, передаваемых через компьютерную сеть. Изучение методов теории выбора кратчайших путей. Разработка программы маршрутизации данных и определение кратчайших путей их маршрутов методом Дейкстры. курсовая работа [495,7 K], добавлен 24.06.2013
Корректность определения кратчайших путей в графе и рёбра отрицательной длины. Анализ алгоритмов Дейкстры, Беллмана-Форда, Флойда-Уоршелла. Вычисление кратчайших расстояний между всеми парами вершин графа. Топологическая сортировка ориентированного графа. презентация [449,3 K], добавлен 19.10.2014
Анализ проблемы обеспечения информационной безопасности при работе в сетях; обоснование необходимости разработки алгоритмов безопасной маршрутизации пакетов сообщений в глобальной информационной сети. Алгоритмизация задач безопасной маршрутизации пакетов. дипломная работа [1,0 M], добавлен 21.12.2012
Задача о кратчайшем пути как одна из важнейших классических задач теории графов. Общий обзор трех наиболее популярных алгоритмов для решения задачи о кратчайшем пути. Написание программы, которая реализует алгоритм Дейкстры и алгоритм Форда-Беллмана. курсовая работа [2,1 M], добавлен 23.06.2014
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2021
Исследование процессов маршрутизации курсовая работа. Программирование, компьютеры и кибернетика.
Сочинение По Стихотворению Про Ивана Простакова
Сочинение Об Удмуртии 4 Класс
Ответ на вопрос по теме Классификация ассортимента одежды из тканей
Реферат по теме Искусственное прерывание беременности
Реферат: Определенный интеграл. Скачать бесплатно и без регистрации
Дипломная работа: Кафе с русской кухней на 100 мест в Одинцово Московской области
Реферат: Elemental Imagery In Jane Eyre Essay Research
Дипломная работа по теме Правовое регулирование совершения электронных сделок
План Сочинения По Картине Масленица
Реферат: Common Sense And The Self-Refutation Of Skepticism
Реферат по теме Оценка работы персонала
Реферат по теме Природа детства и предмет детской психологии
Курсовая работа по теме Создание информационной системы ведения учебной документации в учебном заведении
Варианты Цыбулько Сочинения
Курсовая работа: Особенности размещения городов и городского населения. Скачать бесплатно и без регистрации
Реферат: Частная собственность в России с правовой позиции. Скачать бесплатно и без регистрации
Дипломная работа по теме Modern English Word-Formation
Реферат: Сравнительный анализ переходных процессов в литовской республике в 1917-1922 и 1989-1991 гг.
Реферат На Тему Монетаризм Как Финансовая Школа
Сочинение На Тему Экономические Функции Домашнего Хозяйства
Пролежни. Причины. Профилактика. Лечение - Медицина презентация
Физико-химические процессы, происходящие при механической и тепловой обработке продуктов. Их роль в формировании качества блюд - Кулинария и продукты питания дипломная работа
Городецкая золотная вышивка - Культура и искусство презентация