Занятие № 10. “Алгоритмы маршрутизации”
1. Классификация алгоритмов маршрутизации
Под маршрутизацией следует понимать процесс принятия решения о выборе маршрута доставки информации от отправителя к получателю. При этом содержанием способа маршрутизации являются конкретные правила преобразования адресов точек доступа к сети в маршрут, соединяющий эти точки.
К способам маршрутизации предъявляются следующие требования:
1. Корректность (то есть гарантированное определение маршрута при условии его существования, предотвращение зацикливания сообщений, обеспечение равных условий для пользователей с равным статусом).
2. Оптимальность (обеспечение выбора и реализации наилучших маршрутных решений в соответствии с выбранным критерием).
3. Быстродействие (время выбора маршрута должно быть значительно меньше времени передачи пакета в сети).
4. Адаптивность (учет состояния внешней среды и сети связи).
5. Простота реализации (расход сетевых ресурсов должен быть незначительным).
Существует достаточно большое количество классификационных признаков методов маршрутизации: использование адреса получателя сообщения; учет текущей ситуации на сети при определении маршрута; степень централизации управления; используемая для выбора маршрута информация; способ обмена служебной информацией; способы получения информации о состоянии сети и др.
В зависимости от того, как используется адрес получателя сообщения, алгоритмы маршрутизации делятся на безадресные и адресные (или систематические).
При использовании безадресной маршрутизации не требуется знание топологии сети, ее текущего состояния, на центрах коммутации (ЦК) не надо хранить матриц маршрутов (маршрутных таблиц). Безадресная маршрутизация реализуется с помощью алгоритмов случайной маршрутизации или лавинной маршрутизации (алгоритм “волна”).
При случайной безадресной маршрутизации каждый поступивший пакет (сообщение), не предназначенный данному ЦК, отправляется по одному из исходящих направлений в соответствии с заданными вероятностями. Выбор распределения вероятностей может быть как фиксированным, так и адаптивным. В последнем случае распределение вероятностей изменяется на основе результатов предшествующих передач. Кроме того, при выборе исходящего направления могут учитываться длины очередей и прогнозируемое время передачи но каждому направлению.
Разновидностями таких алгоритмов являются алгоритмы, в которых исходящие направления выбираются в некоторой очередности, и алгоритмы, в которых исходящее направление заранее определено.
Таким образом, при случайной маршрутизации сообщение совершает хаотическое движение по сети до тех пор, пока не достигнет узла назначения. При этом, хотя и существует отличная от нуля вероятность доставки сообщения получателю за конечное число переприемов, время передачи может оказаться недопустимо большим. Для ограничения времени пребывания сообщения в системе можно было бы ограничить сверху число его переприемов в центрах коммутации и уничтожать те сообщения, для которых такая граница достигнута. Однако и в этом случае существует отличная от нуля вероятность того, что сообщение вовсе не дойдет до абонента-получателя.
Сущность лавинной (или волновой) безадресной маршрутизации заключается в том, что сообщение, поступившее в ЦК и не предназначенное для него, передается по всем исходящим каналам (направлениям), исключая направление, по которому оно поступило. Таким образом, в каждом ЦК происходит лавинообразное размножение сообщения. Находящиеся в сети копии уже переданного сообщения уничтожаются при достижении определенного числа переприемов, либо при получении ответного сообщения-квитанции.
Основным достоинством безадресных лавинных алгоритмов является независимость от состояния сети, устойчивость к воздействиям на элементы сети.
Однако эти преимущества достигаются ценой значительных перегрузок сети и снижения ее пропускной способности.
В систематических (адресных) алгоритмах маршрутизации для выбора пути установления соединения используется адрес абонента-получателя, который анализируется в каждом транзитном ЦК сети. Для этого в центрах коммутации должна храниться информация, позволяющая установить соответствие адреса вызываемого абонента с исходящим из данного ЦК направлением передачи. Такая информация хранится в виде плана распределения нагрузки.
Основой плана распределения нагрузки при систематических алгоритмах маршрутизации являются маршрутно-адресные таблицы (МАТ) или матрицы маршрутов, создаваемые для каждого центра коммутации сети.
Основная проблема, решаемая при разработке систематических алгоритмов маршрутизации, состоит в формировании для каждого ЦК сети такой таблицы маршрутов, которая обеспечивает наилучшее соответствие характеристик функционирования сети предъявляемым к ней требованиям с учетом реальных текущих условий.
В зависимости от степени учета этих условий все систематические алгоритмы маршрутизации можно разделить на два класса – фиксированные (статические) алгоритмы и адаптивные, или динамические алгоритмы маршрутизации.
Фиксированные (статические) алгоритмы маршрутизации
При фиксированной маршрутизации выбор исходящего направления передачи на каждом ЦК производится без учета состояния сети. Имеющиеся на каждом ЦК сети маршрутно-адресные таблицы в процессе функционирования сети не корректируются. Сами таблицы при этом могут быть построены различными способами.
По числу маршрутов различают фиксированную маршрутизацию с единственным маршрутом и с альтернативными маршрутами (первого, второго и т.д. выбора), последняя подразделяется на стохастическую и с упорядочением маршрутов.
Фиксированная маршрутизация с упорядочением (ранжировкой) маршрутов позволяет обеспечить минимальное время доставки сообщений при низкой загруженности сети. Однако при увеличении нагрузки оптимальность ранжировки нарушается вследствие перегруженности более предпочтительных маршрутов. Этот недостаток частично может быть устранен при использовании стохастических таблиц маршрутов, обеспечивающих более равномерное распределение исходящих потоков по альтернативным путям маршрутам.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
