СЕКЦИЯ «ИНФОРМАТИКА И МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ»

КОМПЛЕКСНЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ГРАФА ТОПОЛОГИИ КАНАЛЬНОГО УРОВНЯ ЛОКАЛЬНОГО ПОСТАВЩИКА СЕТЕВЫХ УСЛУГ

А. А. Андреев, студ. 3 курса

Научный руководитель – к. т. н., доцент Ю. А. Богоявленский

ИКТ-инфраструктура современных локальных поставщиков сетевых услуг (далее Сеть) стремительно развивается. Растет масштаб Сетей, увеличивается их сложность, широкое применение находят различные средства высокоуровневой организации сетевого пространства, такие как виртуальные локальные сети (далее VLAN). Если в недалеком прошлом типичной картиной для предприятий было объединение в Сеть нескольких десятков компьютеров, то в наше время Сети в несколько тысяч рабочих станций далеко не редкость. Усложнение, в свою очередь, всегда влечет за собой потребность в новых методах управления и необходимость новых специализированных средствах анализа.

Множество задач сетевого управления, такие как моделирование нагрузки на каналы связи, учет использования сетевых ресурсов, локализация неисправностей, требуют для своего решения наличия графа Сети [3] – информации об аппаратных элементах инфраструктуры лПСУ и их связях. Такой граф также является хорошим средством документирования Сети. Очевидно, что задача его построения, легко решаемая вручную в маленьких сетях, является нетривиальной для крупных лПСУ.

На кафедре информатики и математического обеспечения Петрозаводского государственного университета разрабатывается экспериментальная платформа для исследования моделей и методов управления сетями Nest [1], основными возможностями которой являются автоматизированное построение графа Сети, его визуализация и моделирование на нем потоков данных. В Nest строится объектный граф модели SON [2], которая описывает структуру локального поставщика сетевых услуг на трех уровнях: пространственном (Spatial), организационном

(Organizational) и сетевом (Network).

Существующая в Nest подсистема NesTopo, реализующая построение графа Сети, учитывает только устройства и связи сетевого уровня по модели OSI. Однако такое представление скрывает большое количество деталей, необходимых для решения задач сетевого управления в Сетях рассматриваемого нами масштаба. Поэтому была поставлена задача отразить в графе Сети устройства канального уровня, а также

145

учесть существующее в исследуемой Сети разбиение на виртуальные подсети, реализованное по стандарту IEEE 802.1Q.

Основной проблемой при создании методов построения графа канального уровня является отсутствие специализированных источников информации, которые поддерживались бы всеми сетевыми устройствами. Существующие в данный момент протоколы, связанные с исследованием канального уровня, являются либо проприетарными решениями (например Cisco Discovery Protocol, далее CDP), либо появились сравнительно недавно и поэтому недостаточно широко распространены (на-

пример Link Layer Discovery Protocol, далее LLDP).

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

Исследователями [4] был разработан алгоритм построения графа на основе информации из адресных таблиц фильтрации (Address Forwarding Tables, далее AFT). Основными недостатками данного метода являются сравнительно высокая алгоритмическая сложность (кубическая от числа сетевых устройств), высокая зависимость результата от полноты входных данных, а также возможность построить только граф сети, представляющий собой дерево, в котором отсутствуют некоторые связи.

Работа [5] предлагает способ построения графа канального уровня на основе информации, которая появляется в ходе работы протокола остовного дерева (IEEE 802.1D Spanning Tree Protocol, далее STP). Не-

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

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

Основная концепция используемого в Nest подхода к построению графа Сети заключается в следующем: сетевые устройства опрашиваются с помощью простого протокола сетевого управления (Simple Network Management Protocol, далее SNMP) с целью получения из баз данных управляемой информации (Management Information Bases, далее

146

MIB) этих устройств информации об их соседях и способах соединения с ними.

Алгоритм построения графа канального уровня сети, предлагаемый в этом исследовании, использует информацию протоколов STP и CDP (с возможностью внедрения использования дополнительных источников). Приоритет при этом отдается информации STP, так как этот прот о- кол является общепринятым стандартом и так или иначе реализован во всех современных сетевых устройствах. Информация о принадлежности к VLAN получается из доступных параметров конфигурации устройств.

По сравнению с рассмотренными выше работами, алгоритм, предлагаемый в данном исследовании, предоставляет более высокий уровень автоматизации. В связи c используемой концепцией построения графа он требует от пользователя в качестве входных данных только один с е- тевой адрес произвольного сетевого устройства, с которого планируется начать обход и данные авторизации на устройствах, если необходимо. Алгоритмы, разработанные ранее, требуют сразу весь объем данных для построения.

Данные о работе протокола STP предлагается брать из BRIDGE-MIB, таблицы dot1dStpPortTable: физические адреса соседних устройств и номера их портов могут быть извлечены из полей dot1dStpPortDesignatedBridge и dot1dStpPortDesignatedPort соответст-

венно. Таблицы трансляции, которые требуются для определения сетевого адреса устройства, можно найти в таблице ipNetToMediaTable базы IP-MIB или, для устаревших моделей, в таблице atTable из RFC1213MIB. Кэш протокола CDP находится в CISCO -CDP-MIB, в таблице cdpCacheTable. Он содержит, в числе прочего, сетевые адреса соседей и имена их портов. Данные о принадлежности к VLAN портов устройства доступны из широкого ряда источников, в числе которых таблицы dot1qPortVlanTable из Q-BRIDGE-MIB, vlanTrunkPortTable из CISCO- VTP-MIB и ifStackTable из IF-MIB. Таблицы коммутации, с помощью которых можно установить наличие хостов, подключенных к устройствам, можно найти в таблице dot1dTpFdbTable базы BRIDGE-MIB.

Алгоритм автоматизированного построения графа топологии канального уровня:

1.Обратиться к сетевому устройству.

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

3.Получить таблицы трансляции и коммутации и таблицы протоко-

лов STP, CDP.

147

4.Для всех интерфейсов канального уровня устройства, для которых еще не была установлена связь с соседом, повторять шаги 5-9:

5.Определить физический адрес соседнего устройства и порт, через который оно соединено с текущим, по таблице dot1dStp.

6.Определить сетевой адрес соседнего устройства по таблицам трансляции.

7.Если сетевой адрес определить не удалось – отложить обработку текущего порта, перейти к следующему порту.

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

9.Применить алгоритм к соседнему устройству, если оно поддерживает SNMP.

10.Для всех интерфейсов канального уровня, для которых еще не была установлена связь и обработка которых не была отложена, повторять шаги 11–13:

11.Определить сетевой адрес и имя соответствующего порта соседнего устройства по таблице cdpCacheTable.

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

13.Применить алгоритм к соседнему устройству, если оно поддерживает SNMP.

14.Для всех интерфейсов канального уровня, для которых еще не была установлена связь и обработка которых не была отложена, повторять шаги 15-16:

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

16.Создать объект, представляющий взаимодействующее устройство на графе и связать с текущим

17.Получить информацию о принадлежности канальных интерфей-

сов к VLAN.

18.Создать объекты, представляющие интерфейсы VLAN, и связать их с объектами, представляющими соответствующие канальные интерфейсы.

19.Для всех VLAN, которым принадлежат порты устройства, повторять шаги 20-22:

20.Установить, принадлежит ли хотя бы один порт какого-либо уже обработанного соседнего устройства к VLAN с тем же номером.

148

21.Если не принадлежит – создать объект, представляющий на графе широковещательный домен, образованный данной VLAN. Связать новообразованный домен и соответствующий VLAN-интерфейс.

22.Если принадлежит – связать соответствующие широковещательный домен соседнего устройства и VLAN-интерфейс текущего.

23.Для всех отложенных на постобработку портов применить алгоритм начиная с шага 5.

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

25.Объединить все широковещательные домены, которые имеют хотя бы один общий виртуальный интерфейс.

Представленный в работе алгоритм был реализован на базе подсистемы NesTopo платформы Nest. Из особенностей реализации стоит выделить несколько моментов. Для более эффективного использования таблиц трансляции для определения сетевых адресов устройств, в случае если адрес не был определен с первой попытки, проводится поиск среди MAC-адресов устройств с отброшенным последним байтом. Такой прием можно применить потому, что многие крупные компании (включая Cisco) используют внутреннюю адресацию среди портов, а именно между портами одного устройства в адресах будет отличаться только один байт.

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

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

снабором интерфейсов и подключенных к ним хостов.

Результатом моей работы является алгоритм автоматизированного построения графа канального уровня Сети, а также способ отражения на нем VLAN. Реализация данного алгоритма в Nest содержит 932 строки кода, 146 из которых – комментарии. В подсистему NesTopo было добавлено 10 классов, а 12 существовавших ранее подверглись измене-

149