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

Сетевые службы и межсетевое взаимодействие

Задачи сетевого протокола

Глобальные, территориальные, корпоративные сети создаются для передачи данных между конечными станциями, входящими в состав разных локальных сетей. Здесь и далее в этом разделе термин «локальная сеть» будет использоваться для обозначения совокупности узлов, обмен данными между которыми может быть обеспечен протоколами и устройствами физического и канального уровней (т.е. совокупность узлов, для которых широковещательный трафик канального уровня является общим). Локальные сети, даже коммутируемые, плохо масштабируются, поскольку при увеличении числа станций уровень широковещательного трафика в них и MAC-таблицы коммутаторов становятся слишком большими. Поэтому, взаимодействие хостов, принадлежащих разным локальным сетям, требует устройств межсетевой связи (шлюзы, маршрутизаторы), ограничивающих распространение широковещательного трафика границами локальных сетей. В свою очередь, сохранение на приемлемом уровне трудоемкости поиска конкретного узла в объединенной сети требует системы их адресации не на основе физических адресов, а на основе неких логических сущностей, представляющих определенную совокупность физических устройств. Механизмы, обеспечивающие передачу трафика между узлами такой объединенной сети, реализуются протоколами межсетевой связи (сетевого уровня стека).

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

 


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

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

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

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

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

· логическая адресация хостов и их совокупностей,

· определение маршрута передачи пакета в объединенной сети,

· продвижение пакета по выбранному маршруту с заданным качеством доставки,

· управление интенсивностью межсетевых потоков с целью предотвращения перегрузок.

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

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

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

1. передача пакетов без предварительного установления соединения с надежностью «как получится» (дейтаграммный сервис, best efforts service) и

2. передача с предварительным установлением соединения и с гарантированной надежностью доставки (сервис виртуального канала).

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

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

Сетевой уровень должен также выполнять свою часть работы по предупреждению перегрузок сети. Для этого в него включаются механизмы мониторинга потоков и управления их интенсивностью. Эти механизмы будут более сложными в протоколах сети, которая должна не только передавать блоки данных, но и гарантировать определенный уровень качества их доставки (надежность, скорость передачи, задержку доставки).

Задача маршрутизации

Объединенную сеть можно представить набором локальных сетей, коммутирующих устройств (маршрутизаторов) и линий передачи, связывающих эти устройства. Каждый маршрутизатор имеет, как минимум, два интерфейса, по одному в каждой из связываемых локальных сетей. Обычно, в объединенной сети существуют множество путей между любой парой парциальных сетей. Так, в примере, приведенном на рис. 5.2., между сетями 1 и 4можно указать, в частности, следующие маршруты: М1-М3-М6, М1- М4- М5- М6, М1- М2- М5- М6.

 

 
 
Рис. 5.2 Пример многосвязной объединенной сети

 


Множественность маршрутов, повышая отказоустойчивость сетевой среды, ставит вопрос о выборе «наилучшего» из них. Оптимальность маршрута определяется в смысле минимума «расстояния» между конечными сетями (узлами). Такое определение выдвигает на первый план проблему метрики, используемой для вычисления расстояния. Если оно измеряется количеством переходов, необходимых для прохождения пути от узла А к узлу B, то оптимальным в данном примере будет маршрут М1-М3-М6. В условиях же когда необходимо обеспечить минимальное время передачи пакета (для этого потребуется информация о задержке передачи пакета на каждом из интерфейсов маршрутизаторов), наилучшим может оказаться другой маршрут, например М1-М2-М5-М6. Возможна постановка задачи выбора маршрута и по критерию максимизации пропускной способности соединения в условиях различных пропускных способностей каналов, формирующих путь между конечными узлами сети. Таким образом, алгоритмы маршрутизации должны решать свою задачу в смысле достижения минимума целевой функции, выбранной при проектировании маршрута. При этом, они должны:

1. вычислять наилучший маршрут за приемлемое время (сходимость);

2. обладать достаточной адаптивностью к изменениям топологии сети и к состоянию ее каналов связи;

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

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

Таблицы маршрутизации

Результат вычисления маршрута сохраняется в специальной таблице. Конкретное содержание информации о маршруте, содержащееся в ней, определяется типом сетевого сервиса. При реализации сервиса виртуальных каналов в таблице маршрутизации указывается входной и выходной идентификаторы виртуального канала (virtual circuit identifier, VCI), а также - номера портов (входного и выходного), которые на данном устройстве поддерживают существование этого виртуального канала. В дейтаграммных сетях каждая запись в таблице маршрутизации определяет логический адрес сети (или узла) назначения, адрес следующего узла на маршруте, «длину» маршрута и идентификатор выходного порта, через который пакет отправляется в сеть назначения.

Таблица 5.3.а соответствует сети рис. 5.2., в которой поддерживается сервис виртуального канала; она отражает существование трех соединений: «А-М1-М3-М6-B», «А-М1-М3-М4-М5-D» и «C-М2-М4-М3-М6-B». При их построении предполагалось, что линии работают в дуплексном режиме и идентификаторы соединений одинаковы при передаче пакетов в обоих направлениях.

 


Каждый сквозной виртуальный канал формируется совокупностью виртуальных каналов между парами маршрутизаторов. При этом, значения идентификаторов VCI являются локальными, т.е. идентификатор канала может изменяться в каждом узле коммутации. В рассматриваемом примере для первого виртуального канала идентификатор VCI=1 первым маршрутизатором преобразуется в VCI=2, который, в свою очередь, маршрутизатором 3 будет заменен на VCI=7 и маршрутизатором 6 – на VCI=8. Использование локальной нумерации виртуальных каналов дает два преимущества. Прежде всего, это позволяет поддерживать в сети большее число виртуальных каналов при неизменной (обычно – 2 байта) длине поля, отводимого для записи идентификатора VCI. Во-вторых, при локальной нумерации поиск в таблице маршрутизации существенно проще, ибо в ней будут представлены идентификаторы только тех каналов, которые действительно поддерживаются этим узлом в текущий момент времени. В случае же глобальной нумерации виртуальных каналов при назначении идентификатора канала на каждом узле необходимо было бы прежде убедиться в том, что данный идентификатор не используется нигде на других устройствах – весьма трудоемкая задача для больших сетей.

Наличие зафиксированного в таблицах маршрутизации виртуального канала позволяет одинаково решать задачу продвижения пакетов потока. Так, например, любой пакет, имеющий VCI=6 и прибывший от хоста С в узел 2, передается на выходной порт, связанный с узлом 4, а значение идентификатора виртуального канала, которому далее будет принадлежать этот пакет, становится равным 3. В узле 4 этот пакет будет передан на порт, связывающий узлы 4-5, и получит VCI=5. Наконец, в узле 5 этот пакет будет передан на порт, к которому подключена сеть 6 (узел D), и в нее он попадет со значением идентификатора VCI=2. Заметим, что объем информации, на основе которой принимается решение о передаче пакета, т.е. размер поля VCI, заметно меньше размера поля сетевого адреса, что сокращает накладные расходы протокола и ускоряет операцию поиска требуемой записи в таблице.

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

 
 

 


Если в качестве целевой функции принять число переходов до сети назначения, то таблицы маршрутизации в узлах сети рис. 5.2 будут иметь вид, приведенный на рис. 5.3.б (номера портов маршрутизаторов и значения маршрутных метрик в этих таблицах опущены). Пусть пакет, адресованный в сеть 6 (узел D), которая непосредственно присоединена к узлу 5, прибывает на узел 1. В соответствии с его таблицей маршрутизации, этот пакет будет далее направлен узлу 2, далее – к узлу 5 и в сеть, которой принадлежит узел D.

Таблица каждого узла должна содержать записи маршрутов ко всем локальным сетям объединенной сети, которых может быть много и, следовательно, поиск требуемой записи может занимать относительно много времени. Поля адресов, которые содержит каждая запись, имеют размер не менее 4 байт, что также заметно больше размера поля VCI. Эти два обстоятельства увеличивают трудоемкость маршрутизации в дейтаграммных сетях.

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

Для классификации методов маршрутизации можно предложить несколько критериев. Так, одним из них является локализация вычисления маршрутов в объединенной сети. При централизованной маршрутизации оптимальные пути между сетями вычисляются в центре управления на основании получаемой им информации о топологии объединенной сети. Рассчитанные таблицы маршрутизации периодически рассылаются всем маршрутизаторам. Централизованная маршрутизация приемлема для относительно небольших сетей, поскольку вычислительная мощность ее узла управления и скорость получения им информации о состоянии сети должны быть достаточно высокими. Децентрализованная маршрутизация, когда соответствующий алгоритм выполняется на каждом узле сети, менее требовательна к вычислительным ресурсам, но при этом необходимо определенное взаимодействие между узлами для получения информации, необходимой им для вычисления наилучших путей к отдельным сетям. Такие алгоритмы лучше масштабируемы, чем централизованные, но часто дают лишь локально оптимальные результаты (поскольку нередко удовлетворяются информацией о топологии ближайшего окружения, а не всей сети), а в определенных ситуациях могут вырабатывать неприемлемые маршруты. Так, например, маршрутизатор А вычислил лучший путь к узлу С через узел В (рис. 5.4.), после чего линия BC вышла из стоя; маршрутизатор Впервымузнает об этом и вычислит маршрут к С через А. Очевидно, что пока узел А не получит информацию о неработоспособности линии BC, все пакеты к узлу C он будет продолжать отправлять к B; последний же переопределил маршрут к узлу С через узел A,следовательно, возникнет петля. Рассмотренная ситуация отражает переходное состояние сети, но если его длительность будет велика, то возникновение заторов избежать не удастся.

 

 
 

 

 


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

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

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

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

В алгоритмах «состояния канала» (link state routing) каждый маршрутизатор передает через все свои интерфейсы информацию о состоянии каналов, которыми он соединен с соседями, о сетях, непосредственно подключенных к его интерфейсам и к интерфейсам соседей. В конце концов, все маршрутизаторы получают информацию о существующих узлах, каналах связи и парциальных сетях объединенной сети. На основании этой информации каждый маршрутизатор строит граф сети и в автономном режиме вычисляет наилучший, в определенном смысле, маршрут от себя до всех парциальных сетей. Отметим, что протоколы, базирующиеся на таких алгоритмах, лучше масштабируемы, ибо предполагают обмен информацией только об изменениях состояния каналов, следовательно, генерируют меньший объем служебного трафика; они обладают еще несколькими преимуществами, которые будут рассмотрены при анализе конкретных реализаций протоколов.