Составление таблиц маршрутизации в маршрутизаторах

 

Федеральное агентство  железнодорожного транспорта Сибирский государственный  университет путей сообщения Кафедра «Управление эксплуатационной работой»     Курсовой проект   по дисциплине  «Системы и сети передачи данных»
	Руководитель  к.т.н,  доцент Бессон Н.В.     ______________________       (дата  проверки)	Студент гр. ИС-33   _____________ Королев И.Г.         (подпись)   __________________ (дата сдачи на проверку)
Краткая рецензия: ___________________________________________________________________________ ___________________________________________________________________________ ___________________________________________________________________________ ___________________________________________________________________________
__________________________        (оценка по  результатам защиты)		________________________     (подпись преподавателя)
2013 год

 

 

Содержание

 

1. Введение…………………………………………………………………...4
2. Составление таблиц маршрутизации в маршрутизаторах ……………15
3. Заключение………………………………………………………………..25
4. Список использованных источников……………………………………26

 

Введение

Цель данного курсового проекта  познакомиться с основными принципами устройства сетей, их построения и функционирования. Необходимо понять, что нужно для  создания и в последующем нормальной работы сети. А именно какое аппаратное оборудование, программное обеспечение  и среда передачи данных. Ведь для  каждой сети со своими специфическими задачами и особенностями нужен  индивидуальный подход и уникальная разработка.  Также предстоит  изучение самого процесса передачи данных,  что на него влияет, какие могут  быть причины неправильной передачи информации.

 

 Составление таблиц маршрутизации в маршрутизаторах

Сети, объединяемые в интерсеть  на основе IP-протокола, соединяются  между собой сетевыми устройствами, называемыми маршрутизаторами.

Маршрутизатор – это сетевое устройство, которое собирает информацию о топологии межсетевых связей и на ее основе пересылает IP-пакеты в сеть назначения. Маршрутизаторы обычно имеют более одного сетевого интерфейса, каждый из которых обеспечивает передачу данных на основе технологии «локальной сети», к которой он подключен.

Маршрут – последовательность маршрутизаторов, через которые должен пройти пакет.

Таблица маршрутизации - электронная таблица (файл) или база данных, хранящаяся на маршрутизаторе или сетевом компьютере, описывающая соответствие между адресами назначения и интерфейсами, через которые следует отправить пакет данных до следующего маршрутизатора. Является простейшей формой правил маршрутизации.

Таблица маршрутизации обычно содержит:

• адрес сети или узла назначения, либо указание, что маршрут является маршрутом по умолчанию;
• маску сети назначения (для IPv4-сетей маска /32 (255.255.255.255) позволяет указать единичный узел сети);
• шлюз, обозначающий адрес маршрутизатора в сети, на который необходимо отправить пакет, следующий до указанного адреса назначения;
• интерфейс (в зависимости от системы это может быть порядковый номер, GUID или символьное имя устройства);
• метрику - числовой показатель, задающий предпочтительность маршрута. Чем меньше число, тем более предпочтителен маршрут (интуитивно представляется как расстояние);

Виды  алгоритмов маршрутизации 

Алгоритм маршрутизации реализуется  той частью программного обеспечения сетевого уровня, которая отвечает за выбор выходной линии для отправки пришедшего пакета. Если подсеть использует дейтаграммную службу, выбор маршрута для каждого пакета должен производиться заново, так как оптимальный маршрут мог измениться. Если подсеть использует виртуальные каналы, маршрут выбирается только при создании нового виртуального канала. После этого все информационные пакеты следуют по выбранному маршруту. Последний случай иногда называют сеансовой маршрутизацией, так как маршрут остается в силе на протяжении всего сеанса связи с пользователем (например, сеанса регистрации на терминале или передачи файла).

Полезно понимать разницу между  маршрутизацией, при которой системе  приходится делать выбор определенного  маршрута следования, и пересылкой — действием, происходящим при получении  пакета. Можно представить себе маршрутизатор как устройство, в котором функционируют два процесса. Один из них обрабатывает приходящие пакеты и выбирает для них по таблице маршрутизации исходящую линию. Такой процесс называется пересылкой. Второй процесс отвечает за заполнение и обновление таблиц маршрутизации. Именно здесь вступает алгоритм маршрутизации.

Вне зависимости от того, отдельно ли выбираются маршруты для каждого  пакета или же только один раз для соединения, желательно, чтобы алгоритм выбора маршрута обладал определенными свойствами — корректностью, простотой, надежностью, устойчивостью, справедливостью и оптимальностью. Правильность и простота вряд ли требуют комментариев, а вот потребность в надежности не столь очевидна с первого взгляда. Во время работы большой сети постоянно происходят какие-то отказы аппаратуры и изменения топологии. Алгоритм маршрутизации должен уметь справляться с изменениями топологии и трафика без необходимости прекращения всех задач на всех хостах и перезагрузки сети при каждой поломке маршрутизатора.

Алгоритмы выбора маршрута можно разбить  на два основных класса: адаптивные и неадаптивные. Неадаптивные алгоритмы не учитывают при выборе маршрута топологию и текущее состояние сети и не измеряют трафик на линиях. Вместо этого выбор маршрута для каждой пары станций производится заранее, в автономном режиме, и список маршрутов загружается в маршрутизаторы во время загрузки сети. Такая процедура иногда называется статической маршрутизацией.

Адаптивные алгоритмы, напротив, изменяют решение о выборе маршрутов при  изменении топологии и также  часто в зависимости от загруженности  линий. Адаптивные алгоритмы отличаются источниками получения информации (такие источники могут быть, например, локальными, если это соседние маршрутизаторы, либо глобальными, если это вообще все маршрутизаторы сети), моментами изменения маршрутов (например, через определенные равные интервалы времени, при изменении нагрузки или при изменении топологии) и данными, использующимися для оптимизации (расстояние, количество транзитных участков или ожидаемое время пересылки).

 

 

Маршрутизация по вектору расстояний

Современные компьютерные сети обычно используют не статические, а динамические алгоритмы маршрутизации, поскольку статические просто не принимают во внимание текущую нагрузку на сеть. Самой большой популярностью пользуются два метода: маршрутизация по вектору расстояний и маршрутизация с учетом состояния каналов. В этом разделе мы изучим первый, в следующем — второй метод.

Алгоритмы маршрутизации по вектору  расстояний работают, опираясь на таблицы (то есть векторы), поддерживаемые всеми маршрутизаторами и содержащие наилучшие известные пути к каждому из возможных адресатов. Для обновления данных этих таблиц производится обмен информацией с соседними маршрутизаторами.

Алгоритм маршрутизации по вектору  расстояний иногда называют по именам его создателей распределенным алгоритмом Беллмана—Форда (Bellman—Ford) и алгоритмом Форда—Фулкерсона (Ford—Fulkerson), (Bellman, 1957; Ford and Filkerson, 1962). Этот алгоритм изначально применялся в сети ARPANET и в Интернете был известен под названием RIP.

При маршрутизации по вектору расстояний таблицы, с которыми работают и которые  обновляют маршрутизаторы, содержат записи о каждом маршрутизаторе подсети. Каждая запись состоит из двух частей: предпочитаемого номера линии для данного получателя и предполагаемого расстояния или времени прохождения пакета до этого получателя. В качестве единиц измерения может использоваться число транзитных участков, миллисекунды, число пакетов, ожидающих в очереди в данном направлении, или еще что-нибудь подобное.

Предполагается, что маршрутизаторам  известно расстояние до каждого из соседей. Если в качестве единицы измерения используется число транзитных участков, то расстояние равно одному транзитному участку. Если же дистанция измеряется временем задержки, то маршрутизатор может измерить его с помощью специального пакета ECHO (эхо), в который получатель помещает время получения и который отправляет обратно как можно быстрее.

Предположим, что в качестве единицы  измерения используется время задержки, и этот параметр относительно каждого из соседей известен маршрутизатору. Через каждые Т миллисекунды все маршрутизаторы посылают своим соседям список с приблизительными задержками для каждого получателя. Они, разумеется, также получают подобный список от всех своих соседей. Допустим, одна из таких таблиц пришла от соседа X, и в ней указывается, что время распространения от маршрутизатора X до маршрутизатора i равно Х_i Если маршрутизатор знает, что время пересылки до маршрутизатора X равно m, тогда задержка при передаче пакета маршрутизатору i через маршрутизатор X составит X_i + т. Выполнив такие расчеты для всех своих соседей, маршрутизатор может выбрать наилучшие пути и поместить соответствующие записи в новую таблицу. При этом старая таблица в расчетах не используется.

Рисунок 12 – Подсеть (а); полученные от А, I, H и K векторы и новая таблица маршрутов для J (б)

Процесс обновления таблицы проиллюстрирован на рисунке 12. Слева показана подсеть (рисунок 12, а). Первые четыре столбца на рисунок 12, б показывают векторы задержек, полученные маршрутизатором J от своих соседей. Маршрутизатор А считает, что время пересылки от него до маршрутизатора В равно 12 мс, 25 мс — до маршрутизатора С, 40 мс — до D и т. д. Предположим, что маршрутизатор J измерил или оценил задержки до своих соседей А,I,Н и К как 8,10, 12 и 6 мс соответственно.

Теперь рассмотрим, как J рассчитывает свой новый маршрут к маршрутизатору G. Он знает, что задержка до А составляет 8 мс, а A думает, что от него до G данные дойдут за 18 мс. Таким образом, J знает, что если он станет отправлять пакеты для G через А, то задержка составит 26 мс. Аналогично он вычисляет значения задержек для маршрутов от него до G, проходящих через остальных его соседей (I, H и К), и получает соответственно 41 (31 + 10), 18 (6 + 12) и 37 (31 + 6). Лучшим значением является 18, поэтому именно оно помещается в таблицу в запись для получателя G. Вместе с числом 18 туда же помещается обозначение линии, по которой проходит самый короткий маршрут до G, то есть H. Данный метод повторяется для всех остальных адресатов, и при этом получается новая таблица, показанная в виде правого столбца на рисунке.

Маршрутизация с учетом состояния линий

Маршрутизация на основе векторов расстояний использовалась в сети ARPANET вплоть до 1979 года, когда ее сменил алгоритм маршрутизации с учетом состояния линий. Отказаться от прежнего алгоритма пришлось по двум причинам. Во - первых, старый алгоритм при выборе пути не учитывал пропускную способность линий. Пока все линии имели пропускную способность 56 Кбит/с, в учете пропускной способности не было необходимости. Однако стали появляться линии со скоростью 230 Кбит/с, а затем и 1,544 Мбит/с, и не принимать во внимание пропускную способность стало невозможно. Конечно, можно было ввести пропускную способность в качестве множителя для единицы измерения, но имелась еще и другая проблема, заключавшаяся в том, что алгоритм слишком долго приходил к устойчивому состоянию (проблема счета до бесконечности). Поэтому он был заменен полностью новым алгоритмом, который сейчас называется маршрутизацией с учетом состояния линий. Варианты этого алгоритма широко применяются в наши дни.

В основе алгоритма лежит простая  идея, ее можно изложить в пяти требованиях к маршрутизатору. Каждый маршрутизатор должен:

• Обнаруживать своих соседей и узнавать их сетевые адреса.
• Измерять задержку или стоимость связи с каждым из своих соседей.
• Создавать пакет, содержащий всю собранную информацию.
• Посылать этот пакет всем маршрутизаторам.
• Вычислять кратчайший путь ко всем маршрутизаторам.

В результате каждому маршрутизатору высылаются полная топология и все  измеренные значения задержек. После  этого для обнаружения кратчайшего  пути к каждому маршрутизатору может  применяться алгоритм Дейкстры. Далее рассмотрим каждый из этих пяти этапов более подробно.

Знакомство  с соседями

Когда маршрутизатор загружается, его первая задача состоит в получении  информации о своих соседях. Он достигает этой цели, посылая специальный пакет HELLO по всем двухточечным линиям. При этом маршрутизатор на другом конце линии должен послать ответ, сообщая информацию о себе. Имена маршрутизаторов должны быть совершенно уникальными, поскольку, если удаленный маршрутизатор слышит, что три маршрутизатора являются соседями маршрутизатора F, не должно возникать разночтений по поводу того, один и тот же маршрутизатор F имеется в виду или нет.

Когда два или более маршрутизаторов  объединены в локальную сеть, ситуация несколько усложняется. На рисунке 13, а изображена ЛВС, к которой напрямую подключены три маршрутизатора — А, С и F. Каждый из них, как показано на рисунке, соединен также с одним или несколькими дополнительными маршрутизаторами.