Организация обмена сообщениями с сетях ЭВМ

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

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

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

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

     Фиксированная маршрутизация.

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

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

      Адаптивная  маршрутизация.

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

     Сама идея о сети, в которой в любой момент времени доступна маршрутная информация о состоянии всей сети в целом, является привлекательной. Фирма Plessey Telecommunications Research Ltd выполнила на имитационной модели исследование метода маршрутизации, в котором каждый узел, принимающий решение о выборе маршрута, располагал полной информацией о текущем состоянии сети. Этот эксперимент дал неожиданный результат. Оказалось, что средние задержки в сети с маршрутными директивами, получаемыми от «идеального наблюдателя», были лишь немногим меньше задержек в сети с фиксированной маршрутизацией. Хотя эта «идеальная маршрутизация» осуществляется на основании самой свежей информации о состоянии сети, изменения в распределении трафика приводят проблемам. Маршруты, бывшие оптимальными в момент принятия решения, становятся лишь приближенно оптимальными, прежде чем пакеты, достигнут своего назначения. Может оказаться, что несколько узлов, обнаружив, что какой-то из участков слабо нагружен, направят свои потоки через этот участок и тем самым создадут в нем перегрузку. Недостатком маршрутизации «идеального наблюдателя» является ее неспособность учитывать будущие события.

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

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

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

     Локальная адаптивная маршрутизация.

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

     Алгоритм  деления нагрузки похож по своим свойствам на алгоритм Фульца. В каждый узел заранее загружаются таблицы маршрутизации, указывающие кротчайшие пути до узлов назначения. Эти маршруты считались основными. Если существует второй маршрут с таким же количеством промежуточных узлов, но с большей фактической длиной, то этот путь назывался вторичным маршрутом категории A. Если между некоторой парой узлов существует маршрут с большим на единицу числом трактов, он назывался вторичным маршрутом категории B. Если некоторую пару узлов не соединяют вторичные маршруты категорий A и B, то вторичные пути вообще не определяются. Всем типам маршрутов присваивается вес: 5 —основному маршруту, 2 — вторичному маршруту категории A и 1 — вторичному маршруту категории B. Следующим шагом является установление зависимости между весами и длинами очередей пакетов, ожидающих передачи по каждому тракту. Длина очереди ограничивалась, а вес каждой очереди определялся числом свободных мест в ней. Этот вес складывался с весом маршрута, и, таким образом, каждый маршрут получал свой обобщенный вес, по которому осуществлялся выбор маршрута для заданного пакета.

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

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

     Распределённая адаптивная маршрутизация.

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

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

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