В настоящее время, в связи с повсеместным внедрением, ростом и объединением вычислительных сетей стали актуальными задачи повышения их производительности. С ростом числа пользователей и увеличением объема обрабатываемой и передаваемой в сетях информации все чаще возникают проблемы, обусловленные высоким уровнем загруженности узлов и каналов связи. Соответственно, усложняется и поиск оптимальных путей в сети для быстрой доставки запросов пользователей сети, т.е. усложняется задача маршрутизации. Наращивание мощности используемого оборудования, использование новых каналов связи с более высокой пропускной способностью требует соответствующих финансовых затрат и не всегда приносит ожидаемые результаты. Поэтому важно обеспечение более высокой производительности за счет эффективного использования вычислительных сетей путем решения задач оптимального выбора маршрута.
Маршрутизация пакетов в сети занимает одно из важных мест в управлении сетью. Под маршрутизацией обычно понимают доставку пакетов из одного узла сети в другой, максимизируя при этом производительность сети. Задачу маршрутизации в сети решают специальные устройства маршрутизаторы. Алгоритм маршрутизации это часть программного обеспечения маршрутизатора, отвечающая за выбор выходной линии, на которую поступивший пакет должен быть передан. Выбор одного из возможных в маршрутизаторе направлений зависит от текущей топологии сети, длин очередей в узлах коммутации и т.п.
В виду сложности структур современных компьютерных сетей, задача маршрутизации не решается в полной мере. В большинстве случаев это связано с маршрутизаторами [1], не справляющимися с поддержанием таблиц маршрутизации и выбором оптимальных маршрутов для данного класса трафика. Поэтому возникает задача исследования существующих алгоритмов маршрутизации с целью улучшения их характеристик или создания новых алгоритмов маршрутизации.
В данной статье описаны различные виды алгоритмов маршрутизации. Большинство алгоритмов уже используются для решения задачи маршрутизации в сетях. Однако эти алгоритмы не всегда соответствуют выдвигающимся к ним требованиям.
Общая постановка задачи маршрутизации. Маршрутизация может быть представлена в следующем виде. Пусть дан направленный взвешенный граф G=(V,E), в котором каждый узел из множества V представляет собой устройство, обрабатывающее и передающее данные, а каждое ребро из множества E является линией связи. Основной задачей алгоритмов маршрутизации является передача данных из узла источника в узел приемник, максимизируя при этом производительность сети. При моделировании алгоритмов маршрутизации возникают две проблемы, затрудняющие процесс создания системы. Во-первых, поток данных не является статическим, вовторых, он имеет стохастический характер.
Алгоритмы маршрутизации должны выполнять следующие функции:
- сбор, организация и распределение информации о созданном пользователем трафике и состояниях сети;
- использование собранной информации для создания подходящих маршрутов, максимизирующих производительность объектов;
- направление трафика пользователя по выбранному маршруту.
Способ реализации описанных трех функции зависит от технологии передачи и коммутации пакетов, положенной в основу сети, и от особенностей других взаимодействующих уровней приложений. Отправка трафика пользователя может происходить с использованием двух базовых операций сети: коммутация каналов и коммутация пакетов (которые также связанные с понятиями ориентированный и неориентированный на соединение). При коммутации каналов на стадии установки соединения ищутся и резервируются ресурсы сети, которые впоследствии будут предоставлены каждой новой сессии. В этом случае, все пакеты данных, принадлежащие одной и той же сессии, будут направлены по одному и тому же пути. От маршрутизаторов требуется хранение информации об активной сессии. При коммутации пакетов нет стадии резервирования, информация о состоянии не хранится на маршрутизаторах, и пакеты данных могут отправляться по разным путям. В каждом промежуточном узле принимается самостоятельное решение о выборе выходной линии, по которой будет отправлен пакет данных в узел приемник.
Маршрутизация также играет важную роль в обслуживании коммуникационных сетей. При правильно организованной маршрутизации можно оптимизировать такие важные показатели производительности сети как пропускная способность и задержка пакетов.
Основные характеристики задачи маршрутизации
Существуют две основные характеристики, на которые существенное влияние оказывает алгоритм маршрутизации пропускная способность (количество обслуживания) и средняя задержка пакета (качество обслуживания). Маршрутизация считается хорошей, если ей удается увеличить пропускную способность и уменьшить среднюю задержку пакета.
Маршрутизация взаимодействует с управлением потоками в определении характеристик посредством механизма обратной связи, представленном на рис. 1.
Рис. 1. Взаимодействие между маршрутизацией и управлением потока с помощью механизма обратной связи
Величины задержки пакетов и пропускной способности зависят от решений, принятых алгоритмом маршрутизации. Однако на пропускную способность в большей степени влияет алгоритм управления потоками. Такие алгоритмы обычно действуют на основе поддержания баланса между пропускной способностью и средней задержкой [1]. Поэтому, если алгоритму маршрутизации удается более успешно поддерживать малую задержку, то алгоритм управления потоками разрешает принимать сеть больше трафика. Хотя точный баланс между задержкой и пропускной способностью устанавливается алгоритмом управления потоками, хорошая маршрутизация в условиях большого предлагаемого трафика дает предпочтительную кривую задержки пропускная способность, по которой действует алгоритм управления потоками (см. рис. 2).
Рис. 2. Кривые зависимости задержки от пропускной способности для хорошей и плохой маршрутизации
На стадии проектирования сети передачи данных и в процессе ее развития важной задачей является выбор алгоритма маршрутизации. Алгоритм маршрутизации используется для определения наилучшего пути и является основой любого протокола маршрутизации.
В настоящее время известно много алгоритмов, решающих проблемы проектирования сетей передачи данных.
Проектировщик выбирает алгоритм маршрутизации по критерию оптимальности. Оптимальность включает в себе следующие свойства:
- Простота – алгоритмы маршрутизации должны быть как можно более простыми;
- Надежность – алгоритм маршрутизации должен уметь справляться с изменениями сети без необходимости прекращения всех задач на всех хостах и перезагрузки сети при выходе из строя аппаратуры;
- Стабильность и устойчивость – алгоритмы маршрутизации должны четко функционировать в случае неординарных и непредвиденных обстоятельств, таких, как отказы аппаратуры, высокие уровни загруженности узлов и каналов связи;
- Быстрая сходимость – под этим свойством понимаем процесс соглашения между оптимальным маршрутом и всеми маршрутизаторами. Когда какое-нибудь событие в сети приводит к тому, что маршруты или отвергаются, или становятся доступными, маршрутизаторы рассылают сообщения об обновлении маршрутизации. Это сообщения пронизывает сети, стимулируя пересчет оптимальных маршрутов и, в конечном итоге, вынуждая всех маршрутизаторов принять определенный маршрут. Алгоритмы маршрутизации при низкой сходимости могут привести к образованию петель маршрутизации или выходам из строя сети;
- Гибкость – алгоритмы маршрутизации должны быстро и точно адаптироваться к разнобразным обстоятельствам в сети;
- Справедливость – алгоритмы маршрутизации должны равномерно распределять трафики, это поможет снизить среднее время задержки в сети.
Алгоритмы маршрутизации можно классифицировать следующим образом [2]:
- централизованные и распределенные;
- статические и динамические (адаптивные).
В зависимости от места осуществлении выбора маршрута, алгоритмы разделяют на централизованные и распределенные. В централизованных алгоритмах главное управляющее устройство отвечает за обновление таблиц маршрутизации всех узлов и/ или принимает каждое решение о маршрутизации. Централизованные алгоритмы могут быть использованы только в частных случая и для малых сетей. В общем, задержки необходимые для сбора информации о состоянии сети и для трансляции запроса на обновление данных делает такие алгоритмы неприменимыми на практике. Более того, централизованные системы не являются отказоустойчивыми. В данной работе рассматривается только распределенная маршрутизация, разделяющая вычисление маршрутов между узлами сети, которые обмениваются необходимой информацией.
Статическая маршрутизация проста в проектировании и хорошо работает в случаях, когда перемещение потоков данных в сети предсказуемо, а сама сеть имеет простую структуру. Так как системы со статической маршрутизацией не могут реагировать на изменения в сетевой топологии, их не используют в больших сетях. Статическая маршрутизация при выборе маршрута не учитывает топологию и текущее состояние сети и не измеряет трафик на линиях. Этот путь обычно выбирается как кратчайший, относительно выбранного стоимостного критерия, и может быть изменен только за счет поврежденных линий связи или узлов. Выбор маршрута производится заранее, в автономном режиме, и список маршрутов загружается в маршрутизаторы во время загрузки сети. Сетевой администратор самостоятельно заполняет таблицы маршрутизации, и она изменяется только при внесении изменения сетевым администратором. Так как изменения в топологии сети не влияют на маршруты, и алгоритм маршрутизации не адаптируется на разные состоянии сети, поэтому этот алгоритм также называют неадаптивным. В больших сетях эффективнее использовать динамическую маршрутизацию.
Адаптивные маршруты, в принципе, более привлекательны, так как они могут адаптировать способ маршрутизации к временным и к пространственным изменениям трафика. В отличие от статической, динамическая маршрутизация обладает способностью адаптироваться к разнообразным изменениям в сети. Адаптация осуществляется на основании анализа сообщений, поступающих от маршрутизаторов об изменениях в сети. Если в сообщении указывается на произошедшее в сети изменение, то программное обеспечение, осуществляющее маршрутизацию, заново вычисляет оптимальные маршруты и рассылает сообщения об изменениях на все маршрутизаторы сети. Эти сообщения рассылаются по сети, и маршрутизаторы заново пересчитают значения в таблице маршрутизации.
Как недостаток такого подхода выделяют то, что слишком частые изменения в сети могут стать причиной колебаний в выбранных путях. Это обстоятельство, в свою очередь, может привести к созданию циклических путей, а также к большим отклонениям в выполнении алгоритма. К тому же адаптивная маршрутизация может привести к противоречивым ситуациям, которые могут возникнуть при выходе из строя узлов, линий связи или при изменении локальной топологии. Однако все эти проблемы устойчивости более характерны для сетей неориентированных на соединение.
Вместе с динамической маршрутизацией может быть использована и статическая.
Другой способ классификации алгоритмов маршрутизации имеет вид [2]:
- минимальная маршрутизация и неминимальная маршрутизация;
- оптимальная маршрутизация и маршрутизация, определяющая кратчайший путь.
Минимальные маршруты позволяют пакетам выбирать только пути с минимальной стоимостью, в то время как неминимальные алгоритмы позволяют делать выбор между всеми доступными путями, используя при этом некоторые эвристические стратегии.
Оптимальная маршрутизация имеет доступ ко всей сети и ко всем ее объектам для оптимизации функции всех отдельных потоков линий связи (обычно эта функция является суммой стоимостей путей назначенных в соответствии со средними задержками пакетов).
Маршрутизация, определяющая кратчайшие пути, объективно определяет кратчайший путь (минимальную стоимость) между двумя узлами. Учитывая содержание в таблицах маршрутизации различной информации, алгоритмы нахождения кратчайших путей могут быть поделены на два класса: дистанционно-векторные и алгоритмы состояния связи.
Оптимальная маршрутизация является статической и требует знания всех характеристик трафика. Алгоритмы нахождения кратчайших путей более гибкие, они не требуют априорных знаний о моделях трафика и, на данный момент, наиболее распространены среди алгоритмов маршрутизации.
В своей работе мы рассматриваем модель централизованной сети, которая используется для решения следующих двух важных проблем: выбора схемы соединения терминалов с концентратом и выбора схемы соединения концентратов с центральным обрабатывающим устройством.
Обе указанные проблемы, связанные с маршрутизацией выбором схем соединения для терминалов и концентратов по существу одинаковы. Некоторые различия возникают только в связи с тем, что эти устройства находятся на различных уровнях иерархии сети. В обоих случаях стремятся минимизировать стоимость линий связи в сети при наличии некоторых ограничений. Очевидно, в данном случае также необходимо учитывать ограничение на время задержки, которые не должно превышать заданной величины, и ограничение, связанное с требованием определенного уровня надежности сети. Учет требований к надежности сети может быть осуществлен несколькими способами. Первый состоит в обеспечении альтернативного пути передачи сообщения для любого узла сети (двусвязность). Другой способ, характерный для сетей с многоточечными соединениями, заключается в том, что при отказе любой из линий передачи данных количество отключаемых терминалов и концентратов не должно превышать определенной величины. Ограничение на время задержки при проектировании сети минимальной стоимости непосредственно учесть сложно, поэтому вместо данного ограничения вводятся ограничения на потоки. Поток в любом определенном направлении не должно превышать заданную максимальную величину. Это, конечно, ограничивает максимальное время задержки для каждого направления сети.
ЛИТЕРАТУРА
- Столлингс В. Современные компьютерные сети. СПб: Питер, 2003.
- Таненбаум Э. Компьютерные сети. - СПб.: Питер, 2003.
- Бертсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. М.: Мир, 1989.
- Амато В. Основы организации сетей Cisco, том 2. М., 2004.