Классификация методов маршрутизации

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

· простые;

· фиксированные;

· адаптивные.

Простые методы маршрутизации

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

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

3. Маршрутизация по предыдущему опыту заключается в автоматическом построении таблицы маршрутизации. Заголовки пакетов, передаваемых в сети с маршрутизацией от источника, кроме адреса получателя АП и адреса отправителя АО содержат специальное поле «расстояние», значение которого в узле-отправителе устанавливается равным 0. В процессе передачи пакета в сети в каждом промежуточном узле значение поля «расстояние» увеличивается на единицу. Таким образом, в каждом узле значение этого поля показывает расстояние, которое прошел пакет от узла-отправителя до этого узла и которое измеряется в количестве промежуточных узлов на пути передачи пакета.

Методы фиксированной маршрутизации

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

· однопутевая, когда таблица маршрутизации содержит для каждого адреса назначения только один маршрут, и пакеты с одним и тем же адресом назначения направляются всегда к одному и тому же узлу;

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

Достоинство: простота реализации.

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

Методы адаптивной маршрутизации

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

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

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

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

Гибридная маршрутизация представляет собой любую комбинацию рассмотренных выше методов маршрутизации. На практике в современных сетях передачи данных реализованы только некоторые из рассмотренных выше методов маршрутизации, причём конкретная реализация в маршрутизаторах разных фирм может быть различной и часто является секретом фирмы-разработчика.

Задачи управления трафиком. Методы управления трафиком на физическом уровне. Способы разделения кадров. Бит-стаффинг. Управление трафиком на канальном уровне. Квитирование. Тайм-аут. Скользящее окно. Управление трафиком на высших уровнях OSI-модели.

Задачи управления трафиком

Необходимость управления трафиком в сети обусловлена следующими особенностями, присущими сетевому трафику современных компьютерных сетей:

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

· наличие различных (дифференцированных) требований к качеству передачи данных разных типов;

· случайный характер и нестационарность сетевого трафика, обусловленные изменением интенсивностей потоков данных в различное время суток и непредсказуемостью характера и темпа работы пользователей в компьютерной сети;

· в свою очередь, нестационарность сетевого трафика может привести к возникновению в компьютерной сети периодов перегрузок и даже к блокировкам.

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

1) обеспечение надежной передачи данных, предполагающей доставку данных абоненту без потерь и без искажения данных (за счет применения механизмов квитирования и тайм-аута);

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

3) малые задержки при передаче по сети сообщений и, прежде всего, мультимедийных (за счет маршрутизации и приоритетов);

4) предотвращение перегрузок и блокировок при передаче данных (за счет приоритетов и ограничения входящего в сеть трафика).

Управление потоком данных реализуется на различных уровнях OSI-модели. Ниже рассматриваются некоторые наиболее типичные методы управления трафиком на первых трёх уровнях, а именно:

· процедура бит-стаффинга, используемая на физическом уровне;

· механизм «скользящего окна», используемый на канальном уровне;

· методы маршрутизации, используемые на сетевом уровне.