Статья 'Описание базовых топологий с помощью графов в целях построения нотации компьютерных сетей' - журнал 'Кибернетика и программирование' - NotaBene.ru
по
Journal Menu
> Issues > Rubrics > About journal > Authors > About the Journal > Requirements for publication > Council of Editors > Peer-review process > Policy of publication. Aims & Scope. > Article retraction > Ethics > Online First Pre-Publication > Copyright & Licensing Policy > Digital archiving policy > Open Access Policy > Article Processing Charge > Article Identification Policy > Plagiarism check policy
Journals in science databases
About the Journal

MAIN PAGE > Back to contents
Cybernetics and programming
Reference:

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

DOI:

10.7256/2306-4196.2014.2.11380

Received:

17-03-2014


Published:

1-4-2014


Abstract: The subject of the study is to describe the topology of the network by using graph theory. The purpose of the study is to construct the graphic descriptions of a computer network, a mathematical model and notation (language) for storing and processing computer network. All these problems are related and in the study the author focuses on describing the basic topologies "bus", "star", "ring" using graphs for further development and construction of a mathematical model, language notation of mixed network topology using various components. Creating a mathematical model and graphical / symbolic notation of the language is an important step in the task of building a theoretical mathematical apparatus for the creation of computer-aided design and automated control systems for telecommunications networks. The study uses analysis of the existing topology networks, the theory of networks and telecommunication devices, mathematical apparatus of graph theory and the theory of hypergraphs. The problem of constructing computer-aided design of computer networks is relevant since the beginning of the development of computer networks and up to the present time. Invention of new telecommunication technologies and new areas of their application leaves this task up-to-date and requires the development of new approaches. The novelty of the research is in developing methods to describe the classical topology in the context of the task of building a network topology with a complex combination topology. The author describe the classical topologies using graphs, proposes methods for replacements and decomposition. The results can be used in the development of the graph and the symbol models of telecommunication network topology with a complex mixed topology for use in computer-aided design and automated control systems of telecommunication networks. 


Keywords:

binary tree, graph, bus network topology, ring network topology, star network topology, network topology, topology, hypergraph, graph theory, CAD

This article written in Russian. You can find original text of the article here .
Актуальность и проблематика исследования

Проблемы разработки методологии автоматизированного проектирования топологии информационно-вычислительной сетей и создания систем автоматизированного проектирования (САПР) является актуальной уже на протяжении длительного времени, и ранее [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]

Построение графов топологий

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

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

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

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

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

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

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

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

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

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

Выводы

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

References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
Link to this article

You can simply select and copy link from below text field.


Other our sites:
Official Website of NOTA BENE / Aurora Group s.r.o.