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

КИЕВСКИИ

РГ8 ОЛ

ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ

На правах рукописи УДК 681.324

ДИАВАРА МУССА МАМАДУ (Мали)

МЕТОДЫ СИНТЕЗА И АНАЛИЗА СТРУКТУРЫ ГЕТЕРОГЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ ПРЕДПРИЯТИЙ И УЧРЕЖДЕНИЙ

Специальность 05.13.13 — Вычислительные машины,

комплексы, системы и сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

КИЕВ — 1993

КИЕВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ

На правах рукописи

Диавара Мусса Мамаяу (Мали)

УДК 681.324

Методы синтеза и анализа структуры гетерогенных вычислительных сетей предприятий и учреждений

Специальность Сб.13.13 - Вычислительные машины, комплексы.

системы и сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

КИРИ - 199:!

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

комплексов.

Научнь* руководитель - к.т.н., доц. Ю.А. Кулаков

Официальные оппоненты: доктор технических наук, профессор П.П. Зайченко

кандидат технических наук, с. н.с. 0. П. Артеменко

Ведущая организация: институт автоматики АН Украины

Зашита состоиться 13 декабря 1993 г. В 14.30 часов на

заседании специализированного совета Д 068.14.09 Киевского

политехнического института по адресу: 252056, г. Киев, проспект Победы, 37. Корп. 18, ауд.ЗОб.

С диссертацией можно ознакомиться в библиотеке Киевского политехнического института.

Автореферат разослан « » ноября 1993 г.

Ученный секретарь Сптииализиройаннога Сонета

АННОТАЦИЯ

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

Для достижения поставленной цели в работе решается следующие задачи:

- анализ и обобщение моделей производственных предприятий и учреждений!

- разработка и исследование Методов и средств синтеза и анализа структуры гетерогенных сетей управления производством;

-, исследование вопросов эффективности использования стандартов MAP/TOP в интегрированных вычислительных сетях:

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

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

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

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

- методику синтеза оптимальных структур сетей управления производством;

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

- стохастические методы оценки трудоемкости и интенсивности взаимодействия вычислитетельннх процессов в сетях управления производством:

- аналитические методы оценки основных параметров сетей управления производством.

1ШИАН ХАРАКТЕРИСТИКА РАБОТЫ

А к т у << я !■ н о с т ь тем и. 'Л№?ктие<ность функционирования ri)H|).'M''ii!iiix нромишлгмных предприятий и учреждений' в значительной м>'р" . !< |1М1( ИТ ОТ vpi'hll»! иеполкччиння средств вычислитель-

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

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

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

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

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

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

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

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

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

4. На основе анализа взаимодействия абонентских систем ь сетях стандарта IEEE 802.3 предложены пути снижения вероятности етилкно-

вения пакетов.

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

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

Реализация результатов р а 6 о т ы.

Теоретические и прикладные результаты диссертационной работы использованы при проектировании локальной сети фирмы TRADIA INTERNATIONAL (Париж), локальной сети фирмы Intexcom Ltd.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Научном семинаре молодых ученых, Лейпциг, 1992 г., заседаниях кафедры вычислительной техники КГ1И.

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

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

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

В первой главе определяется объект исследования, его организационная структура. Определяется уровень и средства описания модели функционирования локальных сетей, рассматривается вопросы использования стандартов МЛР/ТОР в интегрированных вычислительных сетях.

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

В ТИ'ТЫ'И г лапе рассматривание» попроси определения трудоемкости I'li'iivniuvniiiiux itpotbvM'H в oeiix управлении производством, а

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

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

СОДЕРЖАНИЕ РАБОТЫ

Вычислительные сети относятся к сложным системам обработки информации, .что определяет важность задачи их адекватного информационного описания. В качестве основного элемента при информационном описании вычислительной сети будем использовать такой элемент как "процесс", представляквдй собой целенаправленный акт обработки данных. Процессы, протекаюцие в сетях определяются: Р. - функцией, выполняемой Р. процессом; 0. - точками входа в процесс; э. -множеством связей данного процесса с другцми процессами. Таким образом, некоторый процесс Р^ можно представить в виде функционала Р1 (Р., 0., £ ). Дополнительно каждый процесс Р. характеризуется подмножеством (* ) используемых им ресурсов: /? е я, где: /? = {г4,тг,...,гн) -.множество ресурсов сети.

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

Так при использовании процессами обших сетевых вычислительных ресурсов считается, что процессы Р. и Р не связаны по ресурсам, если выполняется условие: п к = <&.

Отсутствие информационных связей между процесса Р и Р определяется условием: П £ = 0.

Условие подчиненности процессов формулируется следукшим образом: процессы Р. и Р являются неподчиненными друг другу, если выполняется условие: (р * р.) и (Р £ р. ).

Совокупность данных условий определяет несвязность вычислительных процессов и используется в работе на этапе синтеза и анализа структуры вычислительной сети при решении задачи оптимального

размещения процессов по абонентским.системам.

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

- определение топологии каждой локальной зоны;

- выбор наиболее оптимального типа локальной сети для каждой локальной зоны;

- определение типа блоков коммутации и каналов связи между локальными зонами;

- синтез общей структуры вычислительной сети.

Формирование локальных зон в работе представляется как задача

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

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

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

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

Задача декомпозиции сети рассматривается в плане анализа связности графа информационных потоков в сети. Для неориентированных графов необходимое условие связности определяется исходя иэ следующего соотношения; ?

И, ы,

0,5 ■> ■> х ± N -1, где: л/ -число вершин

и О I . ] .

исходного графа, х. . - ребро графа.

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

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

- для прозвольных вершин а^ и а. графа в = <А,Х), входящих в подмножества а. с А и. а с А„ , найти подмножество В, обеспе-чивашее выполнение условий:

1) А4 пв = в;

2) Аг П В = 0:

3) А' П А^ = 0;

4) В и А4 и Аг = А; 4

5)1 В I - минимально.

Выражение, определяющее соотношение между рассматриваемыми подмножествами, описывается следующим образом: в = А - ( А1 и Аг).

Далее определим матрицу | Я {, дополнительную к матрице! А |(, .

в виде; ) А | = I - | А Ц. Строки полной подматрицы образуют подмножество, которое обозначим как А1. Столбцы этой подматрицы в свою очередь образуют подмножество, которое обозначим как А,.

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

В работе показано, что минимальное подмножество сочленения образуется при максимально возможных подмножествах А[ и А.,, что соответствует так называемой основной матрице. Рассмотренные свойства позволяют сделать вывод, что полная подматрица, принадлежащая обратной матрице исходного граф} строки которой включает1 'заданную вершину ^ , а ее столбцы содержат вершину а , ■ определяет подмножества' А| й А2 , которые при выполнении определенных в работе условий можно рассматривать как локальные подмножества.

В работе исследуются известные алгоритмы нахождения всех основных подматриц заданной булевой матрицы, основанные и основном

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

I А' | = | \ I и | а2 | при условий ( / и t2, j л j ) или

I А- • I = » А11 и | Аг | при условии ( / л 1г, J и J ).

Здесь т. и j соответственно множество строк и столбцов матрицы | А. |.

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

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

Рассмотрим данный алгоритм.

1. На основе дополнительной матрицы формируются полные

подматрицы I А (1=1,2.....N). Каждая из подматриц представляет

собой единичные значения элементов а исходной дополнительной матрицы.

2. Выбирается первая подматрица | At | с максимальной суммой элементов.

3. Путем попарного объединения• подматрицы | А^| со всеми остальными подматрицами | А Ц, используя условия ( ^ и , j п ^) или ( i п ¡г, j и J2), формируем новые полные подматрицы.

4. Из полученных подматриц выбирается подматрица с максимальным числом элементов.

5. Полученная подматрица аналогичным образом (см.? п.З, 4) соединяется с исходными полными подматрицами.

0. Пункты З-Ь ионторчкпся до тех пор. пока добавление новой

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

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

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

Предлагается следуюпий алгоритм решения данной задачи;

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

2. Определяется подмножество вершин связанных дугами с данной вершиной. '

3.Вершины, входящие в данное подмножество и имеющие'единичнук степень однозначно относятся к данной локальной зоне.

4. Из оставшихся вершин данного подмножества выбирается вершина, имеющая максимальное число дуг, связываших ее с другими вершинаму рассматриваемого подмножества. В случае нескольких вершин, имеюши* равное количество подобных дуг, выбирается вершина с минимальных числом внешних относительно данного подмножества дуг.

5. Дуги выбранной вершины формируют очередную строку V соответствующий ей столбец матрицы смежности.

6. Пункты 3 и 4 выполняются до тех пор, пока не будут выбраш все вершины рассматриваемого.подмножества.

7. Из оставшегося множества вершин выбирается вершина с мак симальной степенью, которая и рассматривается в 'качестве претен дента на центр очередного локального множества.

8. Осуществляется переход к пункту 2 до тех пор, пока не бу дут выбраны все претенденты на локальные центры.

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

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

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

1. Выбирается произвольная висячая вершина, то есть вершина с единичной степенью.

2. Определяется локальный центр для данной вершины.

3.'Для выбранного локального центра-определяется его очередная висячая вершина.

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

5. Выбирается очередная висячая вершина не входящая в ухе выбранное подмножество вершин.

6. Пункты 2-5 выполняются до выбора всех висячих вершин.

Данный алгоритм обеспечивает формирование всех локальных' зон

нижнего структурного уровня сети управления производством.

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

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

Множество н представляется в виде трех подмножеств:

0 * * • ^г••• • • ^п *-подмножество операторов, опреде-ляших выполнение вычислительных функций, типа сложения, умножения и им подобных.

^ . { г , г ,'..., г ) . подмножество операторов, осу-ществляших обращение к внешним вычислительным процессам. Это. подмножество определяют операторы при выполнении которых происходит обращение к передающей среде.

* = { г,. гг..... гп > - подмножество операторов перехода, изменяющих последовательный характер выполнения операторов

подмножеств о и г.

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

При анализе трудоемкости и интенсивности обращения программы к внешним процессам в работе используются формальные схемы Янова. В работе обосновывается корректность представления процесса выполнения программы с помощью стохастических методов, в частности, с помощью модели марковских процессов. Множество состояний марковского процесса в данном случае определяется мощностью подмножества р, каждому элементу которого сопоставляется некоторый элемент ( б. ) множества состояний 6 = { б, , б....., }. Переход из одного сос-

>12 п

Т9ЯНИЯ в другое задается матрицей вероятностей переходов. Данная матрица является стохастической для которой суммы элементов

■п

в каждой 1-ой строке £ р. - 1.

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

(Р1Л-1)в, +Рг>1тг + ... +рп>1шп -1;

Р»,гШ1 ^Рг,г"1)Шг + ••• +Рп.2тп = 0;

Р,.пт, +Р2 ., тг + ••■ ^Рп,п-1)тп "

Размерность данной системы уравнений определяется общим числом операторов программы и, как правило, является достаточно большой, сократить которую предлагается за счет объединения линейных участков программы. Значение величин п^ используется для подсчета среднее число всех состояний в которых пребывает программа в процессе своего выполнения: Т = £ т и среднее время вычисления

ср 1

п

программы: Т - £т. 1. .

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

К>

Q = 2 и. , где i =1,2,...M.

рей

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

Т„ - 7 m. 1. , где t - 1,2,...М.

d " i t .

peo

Число обращений программы к внешним процессам за время ее выполнения определяется формулой--

N =7 m , где i = 1,2,.. .N.

Z " V

ре/

Среднее время обращения программы к внешним процессам за время ее выполнения определяется следующей формулой;

Т7 = 5 и.1., где i =1,2,... N. z i i .

ре/

Используя полученные формулы можно определить интенсивность обращения программы к внешним процессам;

I »Л-

X ---

Ьд

Средне-вероятностное значение ( X* ) интенсивности обращения к передающей среде при решении заданного набора типовых задач в абонентской системе

N

X* = ^ n¡_ \. где я - вектор распределения

i м

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

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

Для локальных сетей с шинной топологией и случайным методом доступа (стандарт IEEE 802.3) при использовании ненастойчивого алгоритма доступа в работе получено следуодее выражение для вычисления среднего числа заявок, ожидающих обслуживание при наличии столкновений и повторной передачи пакетов:

г » п - < 1 - ро)(1 + 1/х .<m + 1 +т{1 + 2е))), Эту формулу следует считать основной при при расчете параметров локальных сетей с множественным доступом с контролем несущей и обнаружением столкновений.

Стандарт IEEE 802.3 обеспечиает выполнение этих требований, так как предполагает начальный межкадровый интервал равный 9,6 мс, а. время окна конфликтов равное 51мкс.

В работе получена достаточно точная оценка числа заявок, ожидаших обслуживания при настойчивом алгоритме доступа: г - п 41 - Р0Х1 + 1/Х .< ш + 1 +т + 2тП-чГЦ) На основе анализа полученных формул при реальных значениях параметров вычислительных сетей в работе делается вывод, что при относительно низкой интенсивности обращения к передающей среде и достаточно длинных сообщениях эффективность ненастойчивого алгоритма выше по сравнению с настойчивым алгоритмом.

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

,. , к X, .

( k ) V-1 1 .1

pi - Z т*— -

j i. j

Здесь: A. j - интенсивность потока заявок на передачу данных между рассматриваемой (i) и всеми остальными (j) оконечными системами;

lt . - длина линии связи между рассматриваемой (i) и всеми остальными (3) оконечными системами. Значение Р. определяется на всем множестве оконечных систем, входящих в данную локальную сеть. В качестве претендента на расположение системы MAP/TOP. выбирается та абонентская система у которой значение величины Р будет максимальным, тем самим обеспечивается минимальное число возможных столкновений пакетов. Более того, величина Р(, являясь функцией квадрата расстояний между або-

нентскими системами, позволяет оценить минимальную задержку повторной передачи при заданном допустимом числе столкновений.

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

Для локальных сетей с шинной топологией и маркерным методом доступа (стандарт IEEE 802.4) рассматриваются ее основные вероят-ностно-временые характеристики, а именно: среднее время доступа абонентских систем к передашей среде; максимальную гарантированную задержку доступа

Время распространения маркера по кольцу ( Т» ) в общем случае определяется формулой:

т- - 2 U +2Ч.-, ) +с-

1=1 i «о

где: - т. - время передачи маркера между соседними абонентскими системами;

d.- время передачи J-го пакета данных i-ой абонентской системой:

С - время, затрачиваемое на передачу управлять кадров за N передач маркера;

Lt-количество пакетов, передаваемых абонентской системой за сеанс обмена;

В большинстве случаев в рамках локальной сети величину т. можно считать постоянной, с учетом этого приведенное выше выражение принимает следуший вид:

N L.

Т = Т + J . + С.

m . к ш " I . J

V =1 j =0

где: тк = N-т^ - время передачи маркера по логическому кольцу.

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

Одним из определяющих параметров для сетей данного типа является гарантированная задержка доступа (Td) абонентских систем к

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

— L »1, то есть каждая абонентская система за сеанс обмена передает по одному пакету;

— d. ( < D- время передачи (длина) пакетов ограничено величиной D;

—т -т - const, условие соблюдается при однородной передающей среде, что свойственно локальным вычислительным сетям.

С учетом этого получено следующее выражение для определения максимальной гарантированной задержки доступа: Т « X + С + N-D

в к

На основе анализа . протоколов канального уровня можно

утверждать, что величина параметра С не превышает 0,1 от N х т. С

учетом этого рассмотренное выражение принимает следующий вид: TJ

d

» N(1,1t + D). В данном случае реальное значение времени распространения маркера по кольцу (Тг) лежит в пределах: N( 1,1т + l)s Tr< N( 1, 1т + D).

Среднее значение ( Тср ) передачи маркера по логическому определяется соотношением:

к L.

Tcp = IK ZdiJ

i * 1 j =1

Соответственно:

К L

Т - Т + J р . у d . + С.

m k ¿j t , j

i ~ 1 J =0

Для локальных сетей с кольцевой топологией и маркерным приоритетным методом доступа (стандарт IEEE 802.5) минимальное время задержки ( Т ) доступа той же абонентской системе в этом случае определяется соотношением:

N

Т . q • 7 S ,

ml n i

I 1

где: q - длина кадра данных, а Я - < iopi» п. перилами

информации между i и i .i 'абонентскими 0И';ТИ*|МИ, иьлмчамцаи к» от

собственно скорость передачи информации по линиям связи, так и задержку в абонентских системах. Для однородной локальной сети: Т . -q-S-N. Гарантированное время: Td - q-SN + t-(N-I), где- т - время передачи маркера между смежными системами.

В приложении к работе приводится программа вычисления задержки в локальных вычислительных сетях стандартов IEEE 802.3, IEEE 802.4 и IEEE 802.5, позволяющая определить тип сети, обеспечивающий при конкретных условиях минимальную задержку доступа.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

6.Разработаны алгоритмы и программы определения интенсивности обращения абонентских систем к передайся среде, являющееся со-

'ставной частью системы синтеза локальных вычислительных сетей.

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

8. Предложен способ определения оптимального расположения файл-сервера в сетях стандарта IEEE 802.3 или системы MAP-ЕРА для сетей MAP/TOP.

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

.допустимого времени доступа к ней.

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

1.Диавара М.М. Алгоритм декомпозиции сети управления предприятием / Сб. Studentenkenntnlsse, N2, Leipzig, 1993

2 Диавара М.М. Применение протоколов нижнего уровня в сетях MAP/TOP / Сб Wlssencshaftllcher Studentenzirkel, N3, Leipzig, 1993

РАБОТЫ, ОПУБЛИКОВАННЫЕ ПО ТЕМЕ ДИССЕРТАЦИИ

Автор