автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.14, диссертация на тему:Методы, модели и алгоритмы синтеза топологической структуры и управление функционированием компьютерной сети с учетом потребителей информации

• .я ндк ^■'ъгтгжл тзвшшт кдзгчна-;ЯРОшводсгвш:оЕ овъвдзпеиие "кгавшютзса" ,

?Го уЛ

На правах рукописи АВИЛОВ Самаг Рз.монович

УДК 681.324 - 621.391.15

методы, модели и алгоритмы синтеза топологической структуру и упраплееше

ФУНКЦИОНИРОВАНИЕМ КОМПЬЮТЕРНОЙ СЕТИ С УЧЕТОМ ПОТРЕБИТЕЛЕЙ ИНФОРМАЦИИ

Специальность 05.13.14 - Системы обработки информации

и управления

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Ташкент - 1993

РабОха выполнена в орд««а Трудового Красного Знамени Институте кибернетики Научно-производственно!о объединения "Кибернетика" АН РУэ.

Научный руководитель - доктор технических наук, профессор

X. Н. Нигматов.

Официальные оппоненты:

доктор технических наук, проффессор Р. М. Атачанов. - -кандидат технических наук Р. А. Атабеков.

Ведущее предприятие

Ташкентский электротехнический институт связи. . •

Защита состоится

А7_

1996 г. 'в

часов на

заседании Специализированного совета Д 015.12.01 по присуждению ученой степени кандидата технических наук в научно-производственном объединении "Кибернетика" АН РУз по адресу: 700143, г. Ташкент, ул. Ф. Ходжаева, 34, НПО "Кибернетика" АН РУз.

С диссертацией можно ознакомиться в библиотеке Института кибернетики НПО "Кибернетика" АН РУз.

Автореферат разослан

1996 Г.

Ученый секретарь Специализированного совета доктор технических наук, профессор

М. А. Исмошюв

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Особенно актуальным является исследование методов управления процессами обмена информацией, разработки алгоритмов управления этими процессами, вопросы оценки и повышения эффективности сети, как весьма сложной и дорогостоящей системы. Успешность решения этих вопросов во много)! определяется совершенством модели сети -основного инструмента для решения рассматриваемых задач. Совершенство модели зависит в основном от'учета временных параметров моделируемой сети. Решение этой проблемы в сотзетствии с принципами системного подхода должно быть органически связано с решением задач синтеза топологической структуры сети. Анализ рассмотренных работ показал, что в большинстве случаев отсутствует параметр продолжительности процессов, которые .происходят при узрзгле-кии функционированием компьютерной сети.

Из изложенного следует, что проведение исследовал;:;": в эт?:; области весьыз актуально для народного хозяйства..

стоимости и временных показателей.

В число решаемых вадач вошли:

1) исследование методов,., моделей и алгоритмов синтеза топологической структуры вычислительной сети;

2) разработка метода и алгоритмов синтеза топологической структуры компьютерной сети;

3) построение модели процессов управления, передачи и. приема, коммутации пакетов информации и их хранения в буферной памяти;

4) построение модели компьютерной сети,• позволяющей решать задачи управления функционированием компьютерных сетей.

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

Научная новизна-диссертационной работы состоит в следующем:

- разработан метод синтеза топологической структуры компь-' ютерной сети, позволяющий синтезировать сеть для достаточно большого количества абонентов;

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

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

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

При анализе типовой структуры компьютерной подсети определение "узких мест" проектируемой компьютерной сети достигается путем использования ее обобщенной модели.

Разработанные и исследованные в диссертационной работе методы п алгоритмы включены в научно-технический отчет ТНТП Государственного Комитета по науке и технике для их использования в про-

ектах построения и управления функционированием компьютерной сети Республики Узбекистан и рекомендованы для внедрения в коммерческом банке "Тадбпрксрбакк".

Направление работы. Работа выполнена в соответствии с-планом НИР Института кибернетики НПО "Кибернетика" АН РУз со теме "Создать и ввести в действие информационно-вычислительную сеть АН УзССР". (No roc. per. 01910046557, 1931-1993 гг.), по теме "Методология создания перспективных систем передачи информации" (No гос.per. 01.940002823), входящей в задание 1.13.10 "Теория и методы передачи информации в технических системах" программы фундаментальных научных исследований ГКНТ РУз 1Ф "Исследования в области математического анализа, дифференциальных уравнений, алгебры и теории чисел, математической физики, теории вероятностей и математической статистики и дискретных алгоритмов" (1994-1995 гг.).

Апробация результатов.. Основные результаты диссертационной работы доложены и обсуждены на:

- Второй Международной конференции "Системный анализ, моделирование и управление сложными процессами и объектами на базе ЭВМ" (Ташкент, 1992);

- Международной конференции "Интеллектуализация систем управления и обработки информации" (Ташкент, 1994);

- Первой Международной научно-практической конференции "Информатизация республики и новые информационные технологии" (Ташкент, 1994);

- научно-технической конференции "Республиканинг алока тзр-моги ва тизимларини ракаылаштириш" (Ташкент. 1994);

- семинарах, организованных ИК НПО "Кибернетика" АН РУз (Ташкент, 1991-1996).

Публикации. По результатам выполненных исследований опубликовано 8 научных работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав с выводами, заключения, списка использованной литературы, изложенных на 125 страницах машинописного текста; содержит 11 рисунков, 6 таблиц п 3 страницы приложения.

При выполнении настоящей работы непосредственную &екс=г, наряду с яаучнш руководителем, оказывал к.т.н. ,с.н.с. 3LK. Бзб-гкулог.

основное содержание рашш

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

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

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

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

привязки к одному из узлов коммутация абонентов этой группы. Число гбонентоз в каждой группе зависит от количества направлений и пропускной способности узла коммутации. Определяются основные па-растры абонентских линий связи, .'структура межузловых линий связи и их основные характеристики, после чего опредёляется рациональная топологическая структура проектируемой компьютерной сети.

После определения конкретной топологической, структуры сети необходимо проанализировать ее функционирование с помоет ю моделирования процесса обмена данными меяду абонентами. В качестве критерия оценки эффективности управления функционированием сети берется время доведения информации от источника до потребителя с учетом технико-экономических показателей, т.е. стоимостных расходов (затрат) <Са>ка построение сета с учетом,заданных требований ее функционирования и стоимостных потерь от ненадежности, а также от задержки доведения информации {Сп>.Решение этой проблемы должно быть органически связано с решением задачи синтеза топологической структуры сети.

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

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

Задача синтеза топологической структуры компьютерной сети формулируется следующим обрззом. Имеется п абонентов ксыпьвтерноп сети Оп, места расположения которых известны заданы мат-

рицей расстояния между абонентами К-(ги) размера г.хп, где г

>

расстояние между Си и С^ абонентами. Между абонента/и происходит обмен информацией в соответствии с матрицей тяготения Л=Ои) размера пхп, здесь Х^-объем информации, передаваемой от абонента 0.1 к абоненту в единицу времени. Кроме того, имеется функция 3(с,1), определяющая стоимость канала сеяэи емкости с и длины 1.

Известны также следующие характеристики сети: вид функции для вычисления затрат на канал связи абонента - на межузловой канал связи - Бг, на канал связи между зонами - Бз, на узлы коммутации - и на оборудования различного назначения - 35.

Целью решаемой задачи является построение компьютерной сети, обеспечивающей минимизацию следующих критериев:

1. Минимизация суммарной стоимости сети < £СЭ+ЕСП >-->гп1п,

С = 5(51,52,5э,34,35), где 31, Зг, Зэ, 34, Б5 - значения стоимостей перечисленных Еыше функций.

2. Минимизация суммарного времени задержки пакета по кратчайшим маршрутам:

п п

Т = £ 2 Ро Ьа Уц, 1-1 1-1

где Рд з - число углов коммутации между а-ми и з-ми абонентами по самым кратчайшим маршрутам, Чэ- время. задержки пакета а узле коммутации, \>х ] - объем информации между 1 - ми и з - ми абонентами.

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

Таким образом, полученная сеть должна удовлетворять перечисленным ьыше критериям и иметь способность обслужить все потоки, задаваемые матрицей тяготения Л. Поставленная цель достигается в результате корректного решения задач исследования в их определенно:"! последовательное'::! и взаимосвязанности.

. Задача группирования абонентов на зоны формулируется з еле-

дующей постановке. Известны матрица расстояния Н=(г* ^)'и матрица тяготения абонентов Л. Необходимо сгруппировать абоненты таким обряяпм. чтобы в каг.дей зс::с находилось больше абонентов, расположенных относительно близко друг к другу и обменивающихся информацией между собой. Известны также номер расположения абонентов и количество зон к.'

Математически данная задача сводится к задаче разрезания графа. Сначала абоненты и связь между ними представляемся в виде неориентированного полного графа Б=(Х,и,А), гд~ Х- множество вершин: Х=<Х1>, (1=1+п); и- множество ребер: 1Ы1Н;}}( (1,э=1*п); А -множество весов ребер и графа в: А^-СосСи^)}, (1,з"=1+п).

Вводятся следующие определена .и обозначения: V- множество подмножеств вершин: , (1=1^к); 1- множество подмножеств

ребер, связывающих вершины в подмножествах У^-Сг^}, (1=1+к); Y--множество подмножеств ребер, связывающх вершины из различных подмножеств У{ и V,, (1,з'=>1*к, 1*з""), У«-{уи>,(1,3-1+к, 1*3); к--заданное число подграфов.

Задано отображение

Ч>:Ххи~->Укх1кХУк, (1)

где У^Д^.У^ - к - кратные декартовы произведения. Это отображение определяет разбиение множеств вершин X и ребер и графа Б на множество к троек подмножеств <Ч\,Ъ),Ча'>, (1,з=1+к, > - Функция р представляет собой таблицу, условно названную матрицей структуры разрезанного графа В на заданном к подграфе Бь (1=1-*).

Из определенного (1) требуется найти такие разрезания <Рнач.Ф1. • ■ - ,Фг* графа 6 на к подгрэфов 01, (Ы-к), при которых функционал

Ч[»].ЕЕв(Уи), (2)

1 ^

где В(у1 о) - сумма весов ребер, связывающих вершюы из подграфа и Б;, и функция (2) лежат в пределах

Для решения поставленной задачи предлагается итерационный алгоритм, который осуществляет последовательные переходы от одного разрезания к другому, т.е. 1Рнач_">Ф1"">-■ где -конечное разрезание графа на г-м шаге алгоритма. При этом выполняется условие

.<№?начЗ < О.СФ1] <...< 5С<?ги], (3)

Переход от одного разрезания к другому осуществляется путем реорганизации структуры подграфов, т.е. с помощью переноса вершины иг одного подграфа в другой таким образом, чтобы выполнялось условие (3). Перенос вершины иг одного подграфа в другой, при котором выполняется условие (3), будем называть локальной оптимизацией пары подграфоЕ, Обяая схема алгоритма ямеет следующий вид: первоначально определяется'прой'звольно'е*'разрезание графа Б на заданное число подграфов к. При выборе пары подграфов и вершин ь подграфах вводятся элементы равдомигащга, .т.е. случайности: Пара подграфов (Э^б^) из множества пар, полученных при начальном разрезании, каждый раз выбирается случайно с вероятностью, пропорциональной суммарному весу ребер между подграфа,»! пар:

Рн « е(уи).

Далее происходит локальная оптимизация, т.е. максимизация су;,с,¡арного Беса ребер между подграфа1,и выбранной парк, которая осуществляется следующим образом: в первом (1 - м) подграфе равновероятно выбирается Берлина. Для выбранной вершины подсчитываете сумма васов ребер, связывающих вершину с другими вершинами внутри подграфа (внутренняя связанность), и сумма весов ребер, связывающих вершину с вершинами Еторого подграфа пары (внешняя связанность). Правила.' локальной оптимизации заключаются в том, что перенос вершины из одного подграфа в другой осуществляется, если внешняя связанность вершины меньше, чем внутренняя. Алгоритм продолжает работать до тех пор, пока не будут оптимизированы все пары подграфов. ....

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

обцеизвестнио эвркстическиэ алгоритмы.

Деление абонентов каггдой зоны на группы необходимо для определения группы абокентоз, находящееся сравнительно близко друг к другу и ооменизахяцюсся между собой сравнительно большим потоком информации. Для этого сначала вычисляется внутренний и внешний потоки г,-й зоны: гА п п?, ¡А

Лаивш К = Е 2 к ЛЕНУТ« = Е Е

1-1 .¡-п<+1 1-1 Л-1

ч

Максимальное количество узлов коммутации л,- и зоны определяется Формулой Лтах£ = (ЛанешЗ, + ЛвнутО / Пук. где Пук - пропускная способность узла коммутации. После этого каждая зона разбивается на группы. Для этого применяется подход, использованный в задаче группирования абонентов на зоны.

Далее для каждой группы абонентоз в кагвдой зоне определяется местонахождение узлов коммутации. Принимается что, во-перЕых, узлы коммутации должны находиться рядом с одним из абонентов группы и, во-вторых, присоединение абонентов к узлам коммутации должно иметь звездообразную'структуру. При этом

П1

Е Гл —> ийп;

1-1

здесь Г}расстояние между 3-м и 1-м абонентами, 3- номер абонента, где располагается узел коммутации, щ- количество абонентов 1- й группы абонентов. Для определения этого минимума используются матрица расстояний К и результаты группирования абонентов зоны.

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

п п

Л1 о = Е Е

ч-1 р-1

где П1- количество абонентов 1-й зоны, п^- яаятестго

абонентов о- и зоны.

После этого строится граф 2=(У,Н,В), где У - множество вер~ У={у1 Ц=1'к), соответствующих зонам; Н- множество весов . НЫ^}, (1,л=1>к); В- множество вессз р^бер по расстояния: При определении Ь^ принимается, что местонахсхце-

нием i-й гоны является тот узел коммутации, который имеет сравнительно большой поток информации с зоной j.

Используя вогнутый метод исключения ветвей, получаем несколько вариантов т- связанного графа Z:, Zi, Z2,...,Zl. В этих графах сумма весов ребер k к

В = L Z bij i-l :i-l

лежит в пределах minB < В < mlnB + ЛВ.

После этого строится граф N=(Y,H,A), где А- множество весов ребер по интенсивности штоков. Здесь также, используя вогнутый метод исключения ветвей, определяем т- связанный граф N. В графе N суша весов ребер является максимальной:

к к пах С Е ац. i-l J-l

Для выбора одного из графов Zi, Z2,.- .,Zl определяем сечение этих графов с N и вычисляем степень покрываемости Ti,T2,...,Tl. Еыбирается тот вариант графа Zi, в котором Tj-->max.

Определение связанности узлов коммутации решается аналогично задаче определения связанности зон.

Для каждой задачи разработан конкретный алгоритм и составлен пакет программ на языке TURBO С. Получена топологическая структура для 41 абонентов и предложено несколько вариантов этой топологии, построенной на перспективных информационных технологиях.

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

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

Отсюда и следует основной принцип моделирования топологической структуры компьютерной сети коммутации пакетоЕ, так называв-

- 1-3 -

мая модульность. Еще один используемый" принцип'.-1 наращиваемость, "которая при моделировании сети дает возможность развитию модели, достижением которой является иамриение общей модели компьютерной сети.

Разработка модели компонентов компьютерной сети осуществляется с юмощыо сети Петри с разноцветными маркерами: N = = (Р,Т,й,Р,Н,Р'Д,4,Мо), где Р = -:р> - непустое конечное множество позиций; Т = (Ь>- непустое конечное множество переходов; П -={ы> - непустое конечное множество цветов маркеров; Р:РхТ--И0,1,2,.. Л и Н:ТхР—>-(0,1,2,.. •>- функции инцидентности множества позиций и переходов соответственно; ?' :РхГ-->-С0,1,2,...} - функция состояния, т.е. управления, которое графически можно интерпретировать так называем«; "управлян-щ-ши стрелками". X:(Рхй)хТ-->(0,1)- функции распределения цветоа маркеров по входным позициям переходов сети; <>: Тх(Рх£2) — > <РкЙ)-функция распределения цветов маркеров по выходным позициям переходов сети; Мо:Рхй-->(0,1,2,...>- начатьная маркировка сети. Графически сеть Петри изображается в виде двудольного ориентированного графа, в котором позиции, как правило, обозначаются кружками, а переходы планками. .

разработаны следующие модели компонентов вычислительной сети с помощью аппарата сети Петри:

- типовая подсеть Петри; .

- управление, передача и прием пакетов информации в каналах связи, их хранение в буферной памяти;

- процесс.коммутации пакетов в виртуальной транспортной сети.

На основе этих моделей построена обобщенная модель компьютерной сети. После получения конкретной топологической структуры сети производится анализ эффективности управления #ее функционированием. Основной задачей компьютерной сети является автоматическое доведение пакетов информации до адресатов с выполнением требований, предъявляемых к показателям качества процессов доставки. При этом участвуют все компоненты сети. Для определения характеристик данного процесса разработаны конкретные. модели. Как известно, компьютерная сеть состоит из множества абонентской и ме->узлобой подсетей. Функционирование сети характеризуется ее -элементами в виде подсетей, т.е. абонентской подсетью и одним УК. Для гтой цели разработана обобщенная модель, сети, состоящая из п

н -

абонентов, которые подсоединены к одному УК.

На рис. 1 показана сеть Петри, моделирующая обобщенную структуру компьютерной сети. Запуск переходов ¿1,1» t2. 1,... Дп, 1

процесса генерации и приема одного пакета ннфсрмян:;:::. лг.чэство фишек в позициях Pi.iiP2.li •••Гп,1> опг-"-

честЕО передаваемых пакетов информации, а появление фишки в позициях Р1,14< Pf2.i4i-.-jPn, 14 показывает количество принята: пакетов икфпру.оц-;;, остальные позиции и переходы, участвующие В 1,¡одели, отдаивая» процесс обмена информацией меаду компонентами компьютерной сети. Необход;ядо отметить, что при функционировал;'.';! сети происходят согласованные действия компонентов во взакмссвя-ганнсстц, т.е. тжяе,' которые б нужное время могут вырабатывать управляющие действия для других компонентов. Этот процесс моделируется ПОЗИЦИЯМ.! Р1. 4, Р2, 4. ■ ■-.,Рп.4, Р1.7» Р2.7»---, Рп. 7, Р11,'

1 11 ?? пп

Р4- Р5 I Рб > Рб >---,Рб . Р1, 10, Р2, 10. • • • ,Рп, 10. Р1.1Э,

Р2,13.••■.Рп,13- Процесс коммутации осуществляется с помощью использования маркеров равных цветов, т.е. каждому абоненту присваивается собственные цвета маркеров, по котврым определяется дальнейший маршрут фишки, соответствующий пакету информации.

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

Четвертая глава посвящена оценке эффективности функционирования полученной топологической структура компьютерной сети на основе моделирования на ПЭВМ. .

Для наглядности на рис. 2 представлена модель экспериментальной установки. Позиции в модели'соответствуют следующим назначениям:

Р1,14Р1, 4 ~ передатчик первого абонента, Р1,5*Р1.6 " линии связи для передачи информации первого абонента, Р1.7 - регулятор передатчика первого абонента, ... , Р4,14Р4,4 - передатчик четвертого абонента, р.-1,5. Р4,'в '- линии связи для передачи информации четвертого абонента, Р4,у - регулятор передатчика четвертого абонента, Р1 -'входная буферная память УК, Р11 - регулятор входной буферной памяти УК, Р2+Р4 - коммутатор УК, рд - выходная буферная память УК, рз1 - регулятор коммутатора УК, ра - буфер линии связи конкретного абонента, ре5- - указатель цвета для конкретной линии связи, Р1,8'Р1,ю " линии связи для приема пакетов информации первого абонента, Р1,ц * Р1.14 - приемник первого абонента, ... , Р1,о4Р1,ю - линии связи для приема пакетов >ш-

Р1.11*Р1,14 - приемник четвертого

формации четвертого абонента, абонента.

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

Управление функционированием компьютерной подсети проводи-' лось при различных значениях длительности времени обслуживания пакетов информации в УК, задаваемой через I? - количество тактлв.

На основе полученных результатов построены кривые, представленные на рис. 3, отображающие графики функционально;: зависимости вида 10ь = Г СИ) для различных ситуаций и график зависимости вида С = на основе стоимости базовых компонентов сети.

iб 9

?

е / Н

3 %

I

о

Из графиков продолжительности доставки информации и стоимости сети в зависимости от длительности их обработки в УК следует вывод, что при синтезе топологической структуры выбор вычислительной машины УК, шкодой возможность обработать каждый пакет

и.7" формации за Н

ь тактов времени, является рацноняльним ре-

шением рассматриваемой ксмпвзтернои сет;;.

Программные средства реализованы в опера'и:онной среде МЗ £03

1С, -

КЗ ПЭВМ PC/AT.

В приложении приведены акт на внедрения разработанной методики в коммерческом банке "Тадбиркорбанк" и справка о сдаче программ в "Фонд алгоритмов и программ" АН РУз.

Основные результаты диссертационной работы сводятся к следующему:

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

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

3. Разработан подход к формированию различных вариантов то-пологич компьютерных сетей пакетной коммутации.

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

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

6. Произведена экспериментальная апробация модели типовой структуры компьютерной подсети и выявлено, что при синтезе топологической структуры выбор вычислительной машины УК, позволяющей обработать каждый пакет информации за R = 5 6 тактов времени, явллетея рациональным решением для рассматриваемой типовой компьютерной подсети.

Основные положения диссертационной работы отражены в следу»-щ»и публикациях:

1. Бзбзкулов И. К., Абилов С. Р. Алгоритм деления абонентов на группы привязки их к узлам коммутации // Системный аналге моделирование и управление сложными процессами и обгектами ка базе

ЭВМ. Тезисы докладов Второй Международной конференции "Системный анализ - 92". - Ташкент, 1992. - С. 5?. '{Соискателя принадлежит описание программ деления абонентов на группы).

2. Абилов С. Р. Алгоритм имитационного моделирования функционирования компонентов сети ЭЕМ //Алгоритмы,- Ташкент, 1996.-Вып.81.-'С. 47-52.

3. Абилов С. Р. Алгоритм,. определения местоположения .узлов коммутации при построении сети ЭВМ // Республикачинг алока тармо-ги ва' тизимларини ракзмлаштириш. Илмий - техпикавий конференции. Тезис докладлари.- Токкент, 1994. - Б. £7.

4. Абилов С. Р. Алгоритм определения межузловой сети связи в сетях коммутации пакетов //Информатизация Республики и новые информационные технологии. Первая Международная конференция,- Ташкент, 1994. - С. 47.

5. Бабакулов И. К., Абилов С. Р. Определение оптимального количества узлов коммутации при синтезе топологической структуры сети ЭВМ // Интеллектуализация систем управления и обработки информации. Тезисы до:-ладов Международной конференции. - Ташкент, 1994. - С. 218. (Соискателю принадлежит описание программ определения оптимального количества узлов коммутации).

6. Абилов С.Р. Моделирование процесса коммутации пакетов в виртуальной транспортной сети //Еопросы моделирования и информатизации экономии!. - Тапкент, 1996.- Вып. 13,- С. 128-133.

7. Нигматов Х.Н., Бабакулов И. К., Абилов С.Р. Разработка метода синтеза топологической структуры вычислительной сети ЭВМ //Узбекский журнал "Проблемы энергетики и информатики". - Ташкент, 1996,- N 3,- С. 3-8. (Соискателю принадлежит разработка алгоритма синтеза топологической структуры компьютерной сети).

8. Нигматов Х.Н., Абилов O.P. Моделирование процесса обмена информацией в компьютерной сети на базе сетей Петри //Вопросы кибернетики. - Ташкент, 1996. - Вып. 154. - С. 16-20. (Соискателю принадлежит разработка модели компонентов компьютерной сети).

АХЕОРОТДАК СЮЙДАЛАНУЕЧИЛАРНИ ЭДСОБГА ОЛГАН ДОЛДА КОМПЬЮТЕР ТАРЫСРИ ТСПОЛОГИК СТРУКТУРА»! СИНТЕЗ!! ВА ФАОЛИЯТИНИ БОЩАРИШ УСЛУЕИ, МОДЕЛИ ВА АЛГОРИТМЛАРИ

АЕИЛОВ Самат Рахмонович

Мазк?р диссертация ишида ахборотни пакетлар к$ринишида ж^-на-тадиган компьютер тармочларининг тазушли ва синтезу, фг.олпятини бош^ариш масалала'ри тад^ич чилинди. Катта жойларга м?лжалланган, абонектлари етарлича катта мивдорда болтан компьютер тармош топологик структура«! сиктезп ва унинг фзолиятини боикариш услуби, умумлашган холдаги тармок, з;ацда унинг компонентлари моделлари ва уларнинг иш фаолиятлари алгоритмлари ишлаб чикилди.

Диссертация ишида бир катер муз?им илмий натижа Еа хулосалар олинди.

Мукитнинг географик жойлашишини х;исобга олган холда, етарлича катта мивдордаги абонентлардан ташкил топган компьютер тармори топологик структура«! синтези услубини яратишда графлар, композиция ва декомпозиция усулларидан фойдаланилди. Бацолаш мезони си-фатида ахборотдан фойдаланувчилар к^рсаткичларкни /.исобга -олган >;олда, тармокнинг умумий нархини ва ахборот пакетларининг чиз^а йуналишлари б^йича манзилга етиб боришига кетадиган умумий вак.ти-ни мияималлаштириш к^бул цилинган. Яратилган услуб асосида олин-ган тармок,нинг топологик етруктурасидаги алоца каналининг бандли-гпни ошириш ва тармоц умумйй нархини минималлаштириш ман;еадида мавжуд технологияларни хисобга олган здалда к,уркладиган компьютер тармоги топологик структурасининг бир нечта вариантлари таклиф кплинган.

Компьютер тарморининг танлаб олинган топологик структураси-«эги -из фзолиятини боавдриш ва самарадорлигини ба>;олаш мачсадида, тармок фаолиятида иштирок зтувчи барча компонентларнинг >;амда гзр^юшг укушзаган х,олдаги моделлари ишлаб чгадощи. Кэмлыстер тярмогиЕинг па фаолияти вак(тга нисбатан параллел "ечади ва бу жа-ув4клгрк;; моделлактирПш учун Петри тар),¡отдан фойдаланилди.

УягСу нгтпхаларга ассслакиб яратилган алгоритмлар ва дастур-

ко:.: :.-експ "Тадбпр':орбанк" тпжорат Саакига келгусидаги тармок» сснггвдзги излзряга тадбик кплиш учун топширидди.

METHODS, MODELS AND ALGORITHMS OF COMPUTER. NETWORKING

TOPOLOGICAL STRUCTURE SYNTHESIS AND CONTROL GFERAT-IGN '.'.'IT!!. DUE REGARD OF INFORMATION Cl.IFMJS

ABILOV Samat Rakhrnanovich ''

This thesis work dealt with the packet switched computer networking- research and it has been invlstigated designed the method of topological structure of global computer networking synthesis in a large amount of clients.

In order to analyze networking function it has been developed the method of computer networking components. It has also been developed generalized model of computer networking on the base of above mentioned models.

We have got scire important scientific results.

The methods of graphs theorig; been used for - topological structure dosiginng1 in a large amount of clients caking into account their geographical implacement. The methods of decomposition aid aggregation have been used to simplify synthesis procedure aid decline limitations for amount.

It's offered the criteria of the minimization of networking total cost and total time of pacages delay on the shortest routine taking1 into account clients amount.

After getting- concrete topological structure on developed method, the other variants of computer networking1 topological structures have been offered to growth communication line loading1 and minimize netVorking total cost using up - to - date information technology.

The networking components models and it's generalized models have been developed to analyze computer networking1 function in given topological structure.

Petri network has been used in modelling of computer networking1 what gives a chance to model paralell processing.

Developed and researched methods, algorithms arid program packages have been recommended to be used in comr.srcial tank "Tadbirkorba-)k'.

ЕОСМЛХОИЛГЛ ТО П и Ш Р11Л л H ■ ■ Л. БОСИШГЛ РУХСЛТ ЭТИЛДИ^Ж^Ь Й- K.OF03 Ы1ЧИМИ С0.ХЙ1 I/1G. Оч'СКГ 130СМЛ УСУДП. ДЛЛОНИ /} О ПУСХД. БУЮРТМД t<i

УЗ Г> ФА < KI ШНР1 ItiTIf KA» IIIIMG СИГА КАРАШЛП Kl iWIPllU'íUKA UUCTU VWllllIUir БОСМАХОИЛСПДЛ

ЧОП дшлгдн. 700Ш. ТОШКЕПТ. <t>. ХТЖАЕВ. КГЧЛСИ 34 УП.