Describing the basic topologies using graphs in order to build a notation of computer networks

Kruchinina Marina Yurievna Researcher, "VELBORN" Ltd.  394066, Voronezh-66, OOO "VELBORN" do vostrebovaniya siblis@ya.ru

Проблемы разработки методологии автоматизированного проектирования топологии информационно-вычислительной сетей и создания систем автоматизированного проектирования (САПР) является актуальной уже на протяжении длительного времени, и ранее ^[3] и сейчас ^[6][2]. В настоящее время помимо существующих технологий для построения сети Интернет существует множество сфер применения (промышленные сети, бортовые сети, научно-исследовательские сети), для которых также существует проблема разработки методологии, технологий и инструментария для проектирования топологий вычислительных сетей, их настройки, обслуживания и контроля. Кроме того, задача построения соответствующей технологии непосредственно связана с развитием новых технических решений, технологий и сфер применения телекоммуникационных сетей. Мы будем неразрывно рассматривать проблематику систем автоматизированного проектирования (САПР) и автоматизированных систем управления (АСУ), так как они затрагивают два периода функционирования телекоммуникационной сети - САПР используется на этапе проектирования сети, АСУ, в свою очередь, на этапе функционирования. Для разработки САПР и АСУ необходимо построение соответствующих математических моделей, описывающих топологию сети.
Существуют попытки разработки математических моделей телекоммуникационной сети^[8][7] и создания графической и символьной нотации ^[2] с применением стандарта XML.

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

Основными топологиями сети являются топология «шина» (bus), топология «звезда» (star) и топология «кольцо» (ring).
Топология «шина» - один из простейших классических способов построения топологии сети. В этом случае каждый абонент может обмениваться телекоммуникационными пакетами напрямую с любым другим абонентом в сети. Среди примеров сетей топологии «шина» можно отметить технологии HPNA, IPTV, PLC ^[13]. Топологию шина используют и сети, использующие радиоканалы КВ, УКВ при условии, что каждая радиостанция равноправная и общение происходит напрямую по радиоканалу между двумя любыми радиостанциями.
Топология «звезда» ^[15] - сетевая топология, в организации которой выступает некий центральный связующий узел-устройство, маршрутизатор или концентратор. К таковым можно отнести и топологию микросоты сотовой сети GSM-связи, где центральным узлом является базовая станция. При организации сети по топологии «звезда» абоненты обмениваются между собой телекоммуникационными пакетами не напрямую, а только через связующий узловой элемент - концентратор, маршрутизатор или базовую станцию. К топологии «звезда» относятся и сети на базе WiFi-точки доступа.
«Пассивная звезда» - сеть объединенная с помощью концентратора. ^[4] В прошлом это была довольно популярная технология, которая используется и поныне. Так в 1998 году локальные вычислительные сети, построенные по топологии «звезда», широко использовалась при внедрении сети в следующих организациях: Воронежская государственная лесотехническая академия; Воронежский государственный технический университет; Воронежский областной медицинский диагностический центр; межвузовская кафедра «Управление в социальной сфере и медицине» на базе Воронежского областного клинического лечебно-диагностического центра; межвузовская кафедра «Медицинские и гуманитарные системы» на базе Воронежского областного клинического лечебно-диагностического центра; Воронежский энергетический техникум; Воронежское областное управление Государственной инспекции безопасности дорожного движения; Муниципальный информационно-вычислительный центр Администрации города Воронежа; Отдел информационных ресурсов города Администрации города Воронежа; школа-лицей № 55. ^[11]
Топология «кольцо» - еще одна классическая топология сети, которая состоит из узлов, каждый из которых связан с двумя соседними. При этом образуемое узлами «кольцо» замкнуто. К классическим топологиям типа «кольцо» можно отнести, например, технологию FDDI ^[12]. Топология «кольцо» используется при построении магистральных линий связи для обеспечения высокой надежности. Также можно построить сеть с топологией «кольцо» при помощью HDSL-модемов. Несмотря на то, что организация связи между двумя HDSL модемами ^[14] относится к топологии «точка-точка», существует возможность, используя на каждом узле связи по два HDSL модема совместно с маршрутизатором, организовать сеть, замкнув все узлы в «кольцо».
Отметим, что организация топологии «кольцо» является более сложной, чем организация сети по типу «шина» или «звезда», так как требует использования алгоритмов маршрутизации и, соответственно, маршрутизаторов.
Топология «кольцо» также используется в оптических сетях ^[9]. В ряде случае применение топологии «шина» или «кольцо» оказываются устаревшим решением. Так в ^[5] утверждается, что широко распространенные сетевые топологии «двойная звезда» и «общая шина» не отвечают основным требованиям сетевой организации, предъявленным к бортовым вычислительным системам перспективных летательных аппаратов, и предлагают решение для построения отказоустойчивой вычислительной системы, основанное на использовании смешанной топологии, совмещающей элементы топологий «полносвязная сеть» и «двойная звезда».

Отдельно также следует упомянуть сети массового обслуживания с переменной топологией, которые характеризуются случайными или детерминированными изменениями связей между системами обслуживания. ^[10]

Как самую простую в организации топологию сети можно отметить топологию «шина» без использования повторителей. «Шина» может быть представлена в виде гиперграфа, такое отображение является интуитивно-понятным. Но представление сети в виде графа может сильно отличаться от привычного схематического изображения топологии сети. Так отображение всех связностей узлов в сети с топологией «шина» будет образовывать полный граф K_n - регулярный граф степени n-1, состоящий из n вершин и n(n-1)/2 ребер. Иной вариант - представление в виде двоичного дерева, но это чревато введением множества вершин, которые несут только визуальный смысл. Если в топологии n узлов, то двоичное дерево будет содержать 2n вершин и 2n-1 ребер. Каждый узел топологии будет концевой вершиной, а узлы ветвления нести только графический смысл. Представление в виде древовидного графа имеет смысл только для визуального изображения сети и с точки зрения анализа и обработки сети уступает представлению в виде полного графа.

Топология «звезда» может быть представлена в виде графа-звезды S_k, где k - количество узлов сети, за исключением центрального узла. Граф S_k содержит k+1 вершин. Граф топологии типа «пассивная звезда» также сводим к простому графу, если соединить все k вершин дугами, отмечающими возможность обмена телекоммуникационными пакетами и исключить вершину, отображающую центральный узел (концентратор).

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

Рассмотрим алгоритм преобразования графов для единообразного представления топологии сети.

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

Рассмотрим граф S_k для топологии «звезда». Он содержит k+1 вершин. Выделим k вершин первого класса и построим для них граф связности. Результат - граф K_k. Отметим что этот граф будет изоморфен графу связности K_n при n=k для топологии шина. Физический смысл такого преобразования заключается в том, что сеть из n устройств может быть связана как топологией «шина», так и топологией «звезда», а изоморфность графа связности означает, что возожность связи между двумя любыми абонентами, как в том, так и в другом случае, идентичны.

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

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

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

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

Итак, мы рассмотрели способы отображения телекоммуникационных топологий «шина», «звезда» и «кольцо» с помощью графов, не прибегая к теории гиперграфов. Были предложены алгоритмы преобразований графов (метод замен и процесс декомпозиции) и показано, что любая из вышеуказанных топологий может быть представлена в виде графа-звезды. Использование подобного преобразования позволяет продолжить создание математического аппарата описания топологий сети, начатого в статьях [1-2; 7-8], уже с учетом положений, полученных в данной работе, и может использоваться в построении моделей сложной сети, состоящей из множества подсетей. Создание математического аппарата, включающего описания телекоммуникационной модели в виде множеств и графов позволит качественно улучшить методологию разработки редакторов топологий телекоммуникационных сетей, систем автоматизированного проектирования, систем автоматизированного управления и мониторинга телекоммуникационных сетей.