48684 (Разработка структурной схемы маршрутизатора), страница 5

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

Ниже рассмотрим различные способы выбора исходящих трактов передачи сообщений (ТПС).

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

• градиентный;

• диффузный;

• градиентно – диффузный.

Градиентный метод состоит в том, что в каждом транзитном узле в процессе выбора исходящего ТПС участвуют не все исходящие тракты, а лишь наиболее предпочтительные. Если в одном из УК исходящие ТПС, участвующие в выборе не доступны раздельно, то данной заявки на формирование маршрута даётся отказ. В результате градиентного выбора маршрут будет формироваться вдоль геометрического направления.

Реализация градиентных алгоритмов выбора исходящих ТПС позволяет организовать кратчайший маршрут.

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

Градиентно – диффузный метод является комбинацией первых двух методов. В свою очередь процедура выбора исходящего ТПС в каждом УК может быть детерминирована и вероятностна.

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

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

В алгоритмах маршрутизации используется много различных показателей. Сложные алгоритмы маршрутизации при выборе маршрута могут базироваться на множестве показателей, комбинируя их таким образом, что в результате получается один отдельный (гибридный) показатель[9]. Ниже перечислены показатели, которые используются в алгоритмах маршрутизации:

1. Длина маршрута;

2. Надежность;

3. Задержка;

4. Ширина полосы пропускания;

5. Нагрузка;

6. Стоимость связи.

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

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

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

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

При разработке алгоритмов маршрутизации часто преследуют одну или несколько из перечисленных ниже целей:

1 Оптимальность;

2 Простота и низкие непроизводительные затраты;

3 Живучесть и стабильность;

4 Быстрая сходимость;

5 Гибкость.

Оптимальность, характеризует способность алгоритма маршрутизации выбирать наилучший маршрут. Оптимальный маршрут зависит от показателей, используемых при проведении расчета.

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

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

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

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

3.3 Область применения маршрутизаторов

По области применения маршрутизаторы делятся на несколько классов:

• Магистральные маршрутизаторы. Предназначены для построения центральной сети. Это мощные устройства способные обрабатывать миллионы пакетов с секунду и имеющих большое количество интерфейсов локальной и глобальной сети. Большое внимание в этих моделях уделяется надёжности и отказоустойчивости маршрутизатора, которое достигается за счёт системы терморегуляции, избыточных источников питания, а также симметричного мультиплексирования. Примерами магистральных маршрутизаторов служат маршрутизаторы Backbone Concentrator Node, Cisco 7500, Cisco 12000[3].

• Маршрутизаторы региональных отделений – соединяют региональные отделения между собой и с центральной сетью. Такой маршрутизатор представляет собой версию упрощённого магистрального маршрутизатора. Поддерживает интерфейс локальных и глобальных сетей мене скоростных. Примерами маршрутизаторов региональных отделений служат маршрутизаторы BLN, ASN, Cisco 3600, Cisco 2500[3].

• Маршрутизаторы удалённого офиса могут поддерживать работу по коммутируемой телефонной линии в качестве резервной связи для выделенного канала. Примерами маршрутизаторов удалённых офисов, являбтся наиболее типичные представители – Nautika, Cisco 1600, Office Connect, Pipeline[7].

• Маршрутизаторы локальных сетей предназначены для разделения крупных локальных сетей на подсети. Основные требования предъявляемые к ним: высокая скорость машрутизации, так как в такой конфигурации отсутствуют низкоскоростные поры, такие как модельные или цифровые порты.

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

2. 4. Логический метод маршрутизации

Логический метод маршрутизации относится к статическим алгоритмам. Распределение статических таблиц маршрутизации устанавливается администратором заранее и прописывается вручную. В таблицах хранится информация о том, на какой интерфейс отправить пакет с соответствующей адресной информацией. Информация в таблицах не меняется, если только администратор сети не изменит её.

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

В каждом транзитном узле УК(X_i,Y_j), начиная с узла источника, производится анализ адреса узла получателя в сопоставлении его с собственным. В результате вычисляется геометрическое направление из данного узла на УП.

Данные вычисления можно провести заблаговременно и держать в оперативной памяти узла.

Логический метод относится к алгоритмам, которые определяют оптимальный путь доставки информации, основываясь на данных о расстоянии между узлами, а не о пропускной способности сети на данном участке, то соответственно он не может учитывать возможности по ранее забракованным участкам сети из-за загруженности или неисправности [12].

Алгоритм прост для разработки и хорошо работает в окружения, где трафик сети относительно предсказуем, а схема сети относительно проста.

3. 5. Структурная схема маршрутизатора, реализующего логический метод формирования

Рассмотрим процесс нахождения оптимального пути на магистральной сети между узлом получателя и отправителем при условии:

• число узлов на сети около ста;

• структура сети не иерархичная;

• алгоритм нахождения оптимального пути – логический;

В i-м ТПС передается служебная и пользовательская информация.

В фильтре происходит выделение различной служебной информации такой как посылка отказа; посылка на установление соединения; посылка отбоя. В каждом маршрутизаторе содержится таблица соответствия между адресом маршрутизатора на сети и адресом маршрутизатора в единой системе координат. Логический метод маршрутизации относится к статическому, поэтому данные в таблицу заносятся администратором сети. Данный метод маршрутизации не учитывает состояние каналов связи между узлами на сети, а при нахождение маршрута учитывает оптимальное расстояние между узлами. Таблицу соответствия можно разбить на три части. В первой части содержится информация о адресе данного маршрутизатора в обеих системах адресации, адрес в координатной сетке обозначим как ( , ). Значение адрес смежных с данным узлом маршрутизатором – ( ). Адреса удаленных узлов в координатной сетке – ( ). Производится анализ искомого адреса ( ) с собственным адресом маршрутизатора ( , ), В случае если = , , то запрашиваемый адрес находится в пределах сети данного маршрутизатора. В случае если , , то производится дальнейший анализ = , анализируется, – не является ли искомый узел смежным с данным маршрутизатором. Если данное условие не выполняется, то есть = , то искомый узел является удаленным, поэтому необходимо найти исходящий тракт максимально близкий к геометрическому направлению:

;

далее определяем к смежным узлам:

,

при этом необходимо учитывать: