по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > О журнале > Требования к статьям > Редакция и редакционный совет > Порядок рецензирования статей > Рецензирование за 24 часа – как это возможно? > Политика издания > Ретракция статей > Этические принципы > Политика открытого доступа > Оплата за публикации в открытом доступе > Публикация за 72 часа: что это? > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала

Публикация за 72 часа - теперь это реальность!
При необходимости издательство предоставляет авторам услугу сверхсрочной полноценной публикации. Уже через 72 часа статья появляется в числе опубликованных на сайте издательства с DOI и номерами страниц.
По первому требованию предоставляем все подтверждающие публикацию документы!
ГЛАВНАЯ > Вернуться к содержанию
Кибернетика и программирование
Правильная ссылка на статью:

Описание базовых топологий с помощью графов в целях построения нотации компьютерных сетей
Кручинина Марина Юрьевна

научный сотрудник, ООО "ВЭЛБОРН"

394066, Воронеж-66, ООО "ВЭЛБОРН" до востребования

Kruchinina Marina Yurievna

Researcher, "VELBORN" Ltd. 

394066, Voronezh-66, OOO "VELBORN" do vostrebovaniya

siblis@ya.ru

Аннотация.

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

Ключевые слова: бинарное дерево, граф, топология шина, топология кольцо, топология звезда, сетевая топология, топология сети, гиперграф, теория графов, САПР

УДК:

004.722:519.179

DOI:

10.7256/2306-4196.2014.2.11380

Дата направления в редакцию:

12-03-2014


Дата рецензирования:

13-03-2014


Дата публикации:

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

Актуальность и проблематика исследования

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

Библиография
1.
Вишняков А.В., Зотов С.В., Кручинин С.В., Кручинина М.Ю. Опыт разработки архитектуры программного обеспечения САПР вычислительных сетей // Теория и техника радиосвязи. Воронеж. – 2013.-№1. – С. 98-104.
2.
Вишняков А.В., Кручинин С.В., Кручинина М.Ю. Язык описания топологии вычислительных сетей NTDL // Известия Волгоградского государственного технического университета. 2012. №15. С. 126-129.
3.
Гузик В.Ф., Решетняк В.Н., Сидоренко В.Г., Мееров А.С., Шек М.Г. Проблемы автоматизированного проектирования топологии информационно-вычислительной сетей // Известия Южного федерального университета. Технические науки. 1995. Т. 1. № 1. С. 67.
4.
Игнатюк В.А., Сторожок Е.А. Оптимизация доступа в локальных сетях Ethernet // Территория новых возможностей. Вестник Владивостокского государственного университета экономики и сервиса. 2010. № 3. С. 161-165.
5.
Книга Е.В., Жаринов И.О. Принципы построения комбинированной топологии сети для перспективных бортовых вычислительных сетей //Научно-технический вестник информационных технологий, механики и оптики. 2013. № 6 С. 92-98.
6.
Кручинин С.В., Зотов С.В., Вишняков А.В. К вопросу выбора между специализированностью и универсальностью в проектировании САПР (на примере САПР систем связи) // Известия Волгоградского государственного технического университета. 2012. Т. 4. № 13. С. 177-180.
7.
Кручинин С.В. Математическая модель контролируемых устройств // Известия Волгоградского государственного технического университета. 2013. Т. 17. № 14 (117). С. 19-20.
8.
Кузнецов А.М. Математическая модель мультиграфа телекоммуникационной сети и иерархия классов // Научно-исследовательские публикации. Воронеж. 2013. № 1. С. 87-93.
9.
Румянцев К.Е., Хайров И.Е., Новиков В.В. Распределение секретного ключа в оптических сетях с кольцевой топологией методами квантовой криптографии // Известия Южного федерального университета. Технические науки. 2004. Т. 43. № 8. С. 133-136.
10.
Фокина Н.П., Тананко И.Е. Метод управления маршрутизация в сетях массового обслуживания с переменной топологией //Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2013. Т. 13. № 2-2. С. 82-88.
11.
Фролов В.Н. Создание региональной сети компьютерных телекоммуникаций для науки и высшей школы. отчет о НИР № 96-07-89537 (Российский фонд фундаментальных исследований).
12.
Bernhard Albert and Anura P. Jayasumana (1994). FDDI and FDDI-II: architecture, protocols, and performance. Artech House. ISBN 9780890066331.
13.
Blackburn J. L., ed. (1976). Applied Protective Relaying. Newark, N.J.: Westinghouse Electric Corp., Relay-Instrument Division.
14.
Joseph W. Lechleider (August 1991). High Bit Rate Digital Subscriber Lines: A Review of HDSL Progress. IEEE Journal on Selected Areas in Communications 9 (6): 769–784. doi:10.1109/49.93088.
15.
Roberts Lawrence G., Wessler Barry D. (1970), Computer network development to achieve resource sharing, AFIPS '70 (Spring): Proceedings of the May 5–7, 1970, spring joint computer conference, New York, NY, USA: ACM, pp. 543–549, doi:10.1145/1476936.1477020.
16.
Гришенцев А.Ю., Коробейников А.Г. Постановка задачи оптимизации распределённых вычислительных систем // Программные системы и вычислительные методы. - 2013. - 4. - C. 370 - 375. DOI: 10.7256/2305-6061.2013.4.10548.
17.
Новакова Н.Е., Горячев А.В., Горячев А.А. Концепция управления проектами в САПР // Программные системы и вычислительные методы. - 2013. - 3. - C. 257 - 263. DOI: 10.7256/2305-6061.2013.3.10546.
References (transliterated)
1.
Vishnyakov A.V., Zotov S.V., Kruchinin S.V., Kruchinina M.Yu. Opyt razrabotki arkhitektury programmnogo obespecheniya SAPR vychislitel'nykh setei // Teoriya i tekhnika radiosvyazi. Voronezh. – 2013.-№1. – S. 98-104.
2.
Vishnyakov A.V., Kruchinin S.V., Kruchinina M.Yu. Yazyk opisaniya topologii vychislitel'nykh setei NTDL // Izvestiya Volgogradskogo gosudarstvennogo tekhnicheskogo universiteta. 2012. №15. S. 126-129.
3.
Guzik V.F., Reshetnyak V.N., Sidorenko V.G., Meerov A.S., Shek M.G. Problemy avtomatizirovannogo proektirovaniya topologii informatsionno-vychislitel'noi setei // Izvestiya Yuzhnogo federal'nogo universiteta. Tekhnicheskie nauki. 1995. T. 1. № 1. S. 67.
4.
Ignatyuk V.A., Storozhok E.A. Optimizatsiya dostupa v lokal'nykh setyakh Ethernet // Territoriya novykh vozmozhnostei. Vestnik Vladivostokskogo gosudarstvennogo universiteta ekonomiki i servisa. 2010. № 3. S. 161-165.
5.
Kniga E.V., Zharinov I.O. Printsipy postroeniya kombinirovannoi topologii seti dlya perspektivnykh bortovykh vychislitel'nykh setei //Nauchno-tekhnicheskii vestnik informatsionnykh tekhnologii, mekhaniki i optiki. 2013. № 6 S. 92-98.
6.
Kruchinin S.V., Zotov S.V., Vishnyakov A.V. K voprosu vybora mezhdu spetsializirovannost'yu i universal'nost'yu v proektirovanii SAPR (na primere SAPR sistem svyazi) // Izvestiya Volgogradskogo gosudarstvennogo tekhnicheskogo universiteta. 2012. T. 4. № 13. S. 177-180.
7.
Kruchinin S.V. Matematicheskaya model' kontroliruemykh ustroistv // Izvestiya Volgogradskogo gosudarstvennogo tekhnicheskogo universiteta. 2013. T. 17. № 14 (117). S. 19-20.
8.
Kuznetsov A.M. Matematicheskaya model' mul'tigrafa telekommunikatsionnoi seti i ierarkhiya klassov // Nauchno-issledovatel'skie publikatsii. Voronezh. 2013. № 1. S. 87-93.
9.
Rumyantsev K.E., Khairov I.E., Novikov V.V. Raspredelenie sekretnogo klyucha v opticheskikh setyakh s kol'tsevoi topologiei metodami kvantovoi kriptografii // Izvestiya Yuzhnogo federal'nogo universiteta. Tekhnicheskie nauki. 2004. T. 43. № 8. S. 133-136.
10.
Fokina N.P., Tananko I.E. Metod upravleniya marshrutizatsiya v setyakh massovogo obsluzhivaniya s peremennoi topologiei //Izvestiya Saratovskogo universiteta. Novaya seriya. Seriya: Matematika. Mekhanika. Informatika. 2013. T. 13. № 2-2. S. 82-88.
11.
Frolov V.N. Sozdanie regional'noi seti komp'yuternykh telekommunikatsii dlya nauki i vysshei shkoly. otchet o NIR № 96-07-89537 (Rossiiskii fond fundamental'nykh issledovanii).
12.
Bernhard Albert and Anura P. Jayasumana (1994). FDDI and FDDI-II: architecture, protocols, and performance. Artech House. ISBN 9780890066331.
13.
Blackburn J. L., ed. (1976). Applied Protective Relaying. Newark, N.J.: Westinghouse Electric Corp., Relay-Instrument Division.
14.
Joseph W. Lechleider (August 1991). High Bit Rate Digital Subscriber Lines: A Review of HDSL Progress. IEEE Journal on Selected Areas in Communications 9 (6): 769–784. doi:10.1109/49.93088.
15.
Roberts Lawrence G., Wessler Barry D. (1970), Computer network development to achieve resource sharing, AFIPS '70 (Spring): Proceedings of the May 5–7, 1970, spring joint computer conference, New York, NY, USA: ACM, pp. 543–549, doi:10.1145/1476936.1477020.
16.
Grishentsev A.Yu., Korobeinikov A.G. Postanovka zadachi optimizatsii raspredelennykh vychislitel'nykh sistem // Programmnye sistemy i vychislitel'nye metody. - 2013. - 4. - C. 370 - 375. DOI: 10.7256/2305-6061.2013.4.10548.
17.
Novakova N.E., Goryachev A.V., Goryachev A.A. Kontseptsiya upravleniya proektami v SAPR // Programmnye sistemy i vychislitel'nye metody. - 2013. - 3. - C. 257 - 263. DOI: 10.7256/2305-6061.2013.3.10546.
Ссылка на эту статью

Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также попробовать найти похожие статьи


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.
Сайт исторического журнала "History Illustrated"