МАРШРУТИЗАЦИЯ В ИНФОРМАЦИОННЫХ СЕТЯХ

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

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

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

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

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

Другая классификация методов маршрутизации основала на том, изменяются ли маршруты в зависимости от интенсивности входных по­токов. В статических (фиксированных) методах маршрутизации путь, используемый парой "отправитель – получатель информации", фикси­рован и не зависит от колебаний графика. Он может меняться только в случае выхода из строя какого-либо узла или линии связи, т.е. при изменении топологии сети. Такой метод маршрутизации может быть рекомендован либо для очень простых сетей, либо когда эффек­тивность работы сети несущественна, т.к. при нем не может быть достигнута большая пропускная способность сети при вариации вход­ного траффика [1].

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

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

Некоторое промежуточное положение между статическими и дина­мическими (адаптивными) методами маршрутизации занимают квазистатические методы [8]. Если в статических методах маршрут каждого сообщения (пакета) известен заранее до его входа в сеть, а в дина­мических методах он заранее не известен, и направление дальнейшей передачи в каждом узле выбирается исходя из текущей информации о состоянии сети, то в квазистатических методах совокупность ло­кальных маршрутных таблиц каждого узла не фиксирована и меняется (хотя и относительно медленно) при изменении интенсивностей вход­ных потоков [2], [4].

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

Рис. 1

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

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