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

УзсковскиЯ ордена Ленина и ордена Октябрьской Револлции Энергетический институт

Р Г о Ои

о о "/. "> " На правах рукописи

КЛИМАЮВ ВЯЧЕСЛАВ ПЕТРОВИЧ

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

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

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

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

О^ ^

Работа выполнена о Московской ордена Ленина и ордена ОктяОрьской Революции энергетическом институте

Офшдаальшю оппонвнти: доктор технических наук.

профессор А. Я. Савельев,

доктор технических наук, профессор Е II Винницкий,

доктор технических наук, профессор А. П. Свиридов.

Вздувая организация: Шучно-исследовательския центр электронной выделительной техники

Завдта состоится " 'О" ССИ^р_1993г. в '° часов

в аудитории С*на заседании специализированного совета Д-053. 1С. 09 в Московском ордена Ленина и ордена Октябрьской Револщим энергетическом институте. С диссертацией момга ознакомиться в библиотеке ИЭИ.

Огзнви в двух экземплярах, заверешп» печатью, просьба направлять по адресу: 106835, ГСП. Москва, Красноказарменная ул. дом 14, Учения совет ЮИ.

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

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

совета Д-053.16.09 к. т. н., доцент ^ " ,Ладыгин

ОБЩАЯ ХАРА1СГЕГШТИ11А РАБОТЫ Актуальность темы. Широкое внедрение но все с<1*эри человеческой деятельности вычислительной техники предопределило кассовый поток во использования непрофессиональными пользователями: инженерами, конструкторами, административно-управленческим аппаратом. Особенно вадаыми в этой сфере стали вопроси коллективного использования вычислительной среди в задачах автоматизированного управления,автоматизированного проектирования, в задачах принятия I» да пил по управлению сдояныш технологическими и административно -хозяйственными сОгогааи!. Срода локальшл: вычислительных сете;! (ЛЕС) !шОо^эо полно отвечает потр«011остнм этой сфери человеческой деятельности и является экономически оправданной для рапения указанию; задач.

К настоящему времени в различных странах мира созданы и находятся в эксплуатации многие десятки типов ЛВС с различиями физическими средами, топологиями, раэборами, алгоритмами работы. Г. созданию ЛЕС приступили более 100 зарубежных фирм, в той числе такие крупные, как 1ВМ и 21бп»пз .

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

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

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

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

соответствии с:

- Целевой комплексной программой ГКНТ СССР N ОЦ. 027.05. Об; заданием Об. Об. А.

- Целевой комплексной программой ГКНТ СССР К 026. КТП 0.80.03.

- Координационным планом НИР АН СССР по ПРОБЛЕМЕ 1.13. "Кибернетика", заданием 1.13.8.2.

Цель и задачи исследований. Теория И практика создания и эксплуатации ЛВС выдвигает проблему разработки методологии анализа вероятностно-временных характеристик (ВВХ) ЛВС составных топологий, включапцих использование элементов межсетевой связи.

Решению этой проблемы посвящэна представляемая диссертация.

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

В диссертации исследуются и разрабатываете» следующие вопросы:

- Методика анализа ВВХ ЛВС элементарных структур (вина, кольцо). Мэтодика включает разработку аналитических математических моделей, учитывающих особенности топологической схемы и методов доступа к передающей среде.

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

- Методика анализа ВВХ ЛВС при наличии приоритетных входных потоков.

- Инструментальные программные средства, реализующие моделирование функционирования ЛВС.

- Оценки применимости разработанной методологии для анализа ВВХ ЛВС.

Эффективность разработанной методологии подтверждаются при анализе ВВХ конкретных ЛВС.

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

Научная новизна диссертации заключается в разработке методологии анализа ВВХ ЛВС составных топологий, обеспечивающей эффек-

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

1. Разработана ютод^л формализации описания Функциональной схеиы ЛВС на языке сетей ¡кассового обслуживания.

2. Разработаны теоретические принципы создания математических моделей ЛБС (как отдельных функциональных элементов , так и их 1сошозици» в виде ЛЕС с эломентарнши, простыми и сложными топологиями) .

3. Сире до лен новый подкласс моделей ЛВС (открытые »«ультиплика-тивныо сети массового' обслуживания с динамической мзрпрутной патрицей связей), позволявший описывать ЛВС с адаптивным управление и потокораспределения.

Для введенного подкласса математических моделей определит*

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

- нотод численного ренеты уравнений баланса;

- мэтоди вычисления интегральных ВВХ.

4. Па основе разработанных теоретических принципов уточнены ик»щ«еся и разработаны новые подели ЛВС составных топология :

- матемзтическне модели основных фушздчональши элементов (интеллектуальных терминалов, моноканалов, элементов межсетевого обмена);

- математические модели локальных вычислительных сетей элементарных топологий,учитывающих особенности алгоритмов м-этодов доступа:

- ЛВС с топологиеЯ типа "ШИНА" и свободным методом доступа,

- ЛВС С топологиями типа "ФИЗИЧЕСКАЯ ИИНА" И "«ОИЧЕСКОБ КОЛЬЦО" с маркерным »методом доступа;

- математические модели локальных вычислительных сетей простых топология с использованием элемента межсетевого обмена типа "ПОВТОРИТЕЛЬ", "ПОСТ";

- математические модели ЛВС составных топология, включающие модели ЛВС простых топологий типа "Ш1НА" и "ЗВЕЗДА" с использованием элемента межсетевого обмена типа "ШГ;

- математические модели ЛВС сложных топологий ячеистого типа:

- ЛВС типа "КВАДРАТНАЯ РЕИГГКА";

- ЛВС типа "ТРЕУГОЛЬНАЯ РЕПЕТКА".

5. Разработан диалоговый программный комплекс- "М0Д7ЕТ",

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

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

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

Реализация результатов работы. Предложенная в работа методология разработки аналитических моделей ЛВС составных топологий, а такле математические модели, методы и алгоритмы и инструментальные средства разрабатывались в течение более 10 лет на кафедре Ш ШИ в рамках IMP, выполняемых по тематике, определенной следующими документами:

- Целевой комплексной программой ГКНТ СССР N ОЦ. 027.05. Об; заданием 06. 05. А.

- Целевой комплексной программой ГКНГ СССР М 026. КТП 0.80. 03.

- Координационным планом НИР АН СССР по проблеме 1.13. "Кибернетика", веданном 1.13.8.2. —

Шполнсииио НИР:

• - разработка пакета прикладных программ для реыения задач теории массового обслуживания (НИЕ «ЭИ, гос. per. N 72054349, 1072-1973);

- исследование и разработка комплекса имитационных моделей узлов сетей связи пакета имитационных моделей сетей связи (НИР ИЭИ N 233/81, 1981-1084, ГОС. per. N У84504);

- разработка инвариантного ядра средств учебно-исследовательской САПР «ЭИ (НИР КЭИ N 01830022404, 1981-1985, задание 0. Ц 027. 05. 011 И 0. Ц. 027. 05. 012);

- разработка структуры и математического обеспечения информационно- вычислительной сети комплексной автоматизированной системы предприятия (НИР МЭИ N 69/85, 1985-1987, гос. per. N Г83943);

- моделирование сложных структур и комплексов (НИР МЭИ N 335/ 86, 1906-1989);

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

ЯреДПрИЯТИЯ (ПИР ЮИ и 21338700, 1007-1090, ГОС. per. N У47369);

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

- математический иодом и программное обеспечение для исследования систем локашюго обмона дшшшй» (виадроно в ШЮ Космического приборостроения);

- программна кошшке для моделирования локальной информационно-вычислительной сети специального назначении (внедрено в ПО "Гранит");

- мотоднка аналитического модолнровшшя и программный комплекс для анализа вероятностно-времунш« характеристик локальных вычислительных сотея слояюЯ структуры (шюдроно в 11ГЮ "Адьтаир");

- математические модоля и програшшЯ комплота для аиилизо "Опытного участка компьютеризованного интегрированного производства штампов и проссформ" (в ПО "Тушинский машиностроительный завод").

Фактический экономический э<Мокт по одной работе составляет 50 тыс, рублей в ценах 1080г.

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

Апробация работы.. Результаты исследования, составлящих основное содержание работы, докладывались и обе у лишись на международных конференциях и симпозиумах: "Информатика-90" (Гавана, Куба, 1990г.), "Восьмом Ладународном симпозиум* по проблемам Модульных информационно-вычислительных систем и cvtvA" (Дубна, 1991 г.) на Международной Конкуренции Восток-Запад по ном« информационным технологиям в образовании (МШГГИ Ы.: 199?г.). на "1? Псосош-ном семинаре по вычислительным сетям" (Одесса. 1907г.), ни 13, Н, 15,16 Всесоюзных школах-семинарах по вычислительным сетим (Алма-Ата, 1988г., Минск, 1989г. , >нинград, 1У90Г. , Ринница, 1991г). на ЮЗилуйноЯ научно-технической кинфе^'нции "нли*? информационные И ЭЛОКТрОННЬЮ технологии в ИЧрОДНчМ xol'hfli'tb»' и образовании" (Москва, К'И, 1990rj семинарах кнМр "М, <"лчемс'Техники мэи.

ПО диос»>рт«ции ОПубЛИК-.'В.шо 21 pifvli», bmit/ ц»?но 1г отчетов по т«.'иш ИКР.

Структура и оО'ем диссертация. Диссертация состоит из введения, восьми глав, выводов, списка литература и приложений. Общий объем основного текста включает стр., в том числе 73 рис. и ■50 таблицы. Список литературы состоит из 155 наименований, содтшш гашш Во введении обоснована актуальность проблемы, отмечен вклад ученых в развитие теории и практики в«числителяшс систем и сетей. О^ормулированы доли и задачи исследования, показана научная новизна и практическая ценность полученных результатов, излагается содержание работы.

ГЛАВА 1. ЛОКАЛЬНЫЕ ШЧИСЛСТЕЛЬНЫЕ СЕТИ КАК ОБЪЕКТ

УПРАВЛЕНИЯ ТЕКШЭГИЧЕСКИМИ И ПРОЮЮДСТВЕШйЛИ ПРОЦЕССАМ!! В РЕАЛЫШ МАСШТАБЕ ВРЕМЕШ1 Задачи управления производством, научным экспериментом, транспортными системами, космическими комплексами и др. наиболее элективно реализуются на основе использования технологии распределенных вычислительных систем. В этом случае непрерывное взаимодействие системы управления с внесшими устройствами (датчиками технологических параметров, преобразователями,4исполнительными механизмами), на основе распределенной (децентрализованной) обработки и управления технологическими и производственными процессами естественным образом и наиболее эффективно реализуются в технологии локальных вычислительных сетей (ЛВС).

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

Существенным количественным (¡актором, определяюиим работу ЛЕС в управлении технологическими процессами является большое количество абонентов. Минимальное их значение определяется десятками, а максимальное - сотнями, а порой и тысячами .

Учитывая тот факт, что ЛВС используется для управления в реальном масштабе времени в качестве оценки ее эффективности выбираются вероятностно-временные характеристики (ВВХ).

Рассматриваются характерные особенности исследуемого класса

ЛГС :

- физическая среда и способы передачи данных,

- топология ЛВС,

- о -

- методы совместного использования передающей среди,

- принципы объединения ЛВС.

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

Проведен сравнительный анализ использования различных типов топологий ЛВС.

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

Показано, что основой для реализации принципов объединения ЛГС является семиуровневая модель 0S!. Дается характеристика особенностей использования элементов межсетевого обмена и представлен их сравнительный анализ.

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

Показано, что для решения задач анализа PBX наиболее эффективным является метод математического моделирования.

Исходя из вышесказанного определим задачу диссертации :

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

ГЛАВА 2. ЗЛЕМЕНШ СОРМАЛИЗАЦИИ ОПИСАНИЯ Я МЕТОДЫ АНАЛИЗА ЛЕС

С точки зрения представления функционирования ЛВС как системы управления производственными процессами в реальном изсотаСе времени и оценки ее эффективности на основе вероятностно-в^менных характеристик, ЛВС наиболее естественно и эффективно молет быть представлена моделями сетей массового обслуживания (СеМО).

Общая структура описания СеМО состоит из следующих частей :

1. Описания всех составляющих исследуемой СеМО (S - <s. )i-f7ñ) и их параметров.

2. Описания рабочей нагрузки (распределения ьн-шних потоков требований по элементам Се МО) для каждого "m" - го ьнезиего потока требований (P.j) i.j-ГГЧ

3. Перечня ха{>актеристик, которо* н^обхидиио получить в результате анализа на определенных соотаьляном '">« > ( FEWJ¡bTA?M АНАЛИЗА).

Далее в диссертации д. »»тс я С*.рмгшмо1мнй--- п;-',".'? ..ык-ние

указанных выше составлявших.

Формализованное описание ЛВС как СеМО дает представление о характере класса рассматриваемых элементов сети и уровне их детализации, топологической схеме взаимодействия между элементами и перечне анализируемых характеристик. Оно является основой для декомпозиции и композиции моделей составных топологий ЛВС.

Уровни детализации модели ЛВС Исходя из поставленных задач анализа ВВХ ЛВС и степени предварительной информированности об изучаемом оОгокте (гл. 1), ыояю ЛПС рассматривать как систему, расчлененнуп на четыре следуших уровня (рис.1) :

1-ый уровень стратификации (самый подробный) состоит га набора следующих Функциональных элементов : терминалов, канальных станций, моноканалов.

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

2-ой уровень стратификации учитывает особенности взаимодействия отдельных элементов 1-го уровня в рамках всей ЛВС (элементарные топологии ЛВС) :

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

- физическая шина, детерминированный метод доступа;

- физическое кольцо, случайный метод доступа;

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

Каждая из перечисленных схем ЛВС данного уровня стратификации

штат Оыть представлена в виде модели СеЮ.

3-ий уровень стратификации учитывает взаимодействие нескольких ЛВС элементарных топологий, связанных меаду собой с помосыо "повторителей" и/или "мостов" в единую ЛВС простой топологии ("дерево", "цепочка**, "снеигака", "сетка"...).

^тематической моделью ЛВС данного уровня стратификации является СеЮ.

4-ый уровень стратификации (самый высокий) учитывает взаимодействие любых ЛВС 2-го и 3-го уровня, связанных с помощью "маршрутизаторов" и "алпзов" в единую ЛВС произвольной топологии.

ШтематическоЯ моделью ЛВС данного уровня являются СеЮ.

Пргашцип стратификации ЛВС составных топология позволяет преодолеть трудности анализа ЛВС большой размерности за счет декомпозиции модели ЛЕС на иерархический набор более простых подмоделей, доведя их до уровня представления следущих Функциональных элементов: терминалов, канальных станций, моноканалов. Тем самым создаются условия для определения конечного набора базовых моделей (для рассматриваемого класса ЛВС - это модели элементарных топологий), на основе которых, как из "кирпичей" создаются интегральные ЛВС составных топология.

Проведен сравнительный анализ методов моделирования ЛВС и сделан вывод о том ,что из перечисленных подходов к анализу СеЮ как модели ЛВС составных топологий с адаптивным управлением потокорасп-ределением в данной работе будет использован метод , основанный на применении приближенных аналитических моделей открытых, однолинейных. мультипликативных Се МО с неоднорсдньми классами П^овачий и типами состав ля ек^их систем и с использованием динамических ных матриц вероятностей обмена.

ГЛАВА 3. МЕТОЛИКА РАЗРАБОТКИ АНАЛИТИЧЕСКИХ МОДЕЛЕЙ лв:

В глзпе предстаелена методика рх^р.лГ'ОТки мат.щчткч^ских моделей ЛВС .которая состоит иа двух лтчпов:

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

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

Для задачи анализа ВВХ ЛВС основным связующим элементом между отдельными декомпозиционными элементами являются потоки требований, циркулируют на стыке мааду элементами. Поэтому они и являются ключевыми элементами, свлзыга«з>1Ш1 составляющие на всех уровнях стратификации л являются основой для составления уравнения баланса, как для фрагментов сети, так и для сети в целом.

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

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

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

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

1. Составление уравнений баланса интенсивностей потоков на входе/выходе любых фрагментов сети по схеме стратификации "снизу-вверх".

2. Составление уравнений баланса коэффщиентов нагрузки по всем элементам,входящим в сеть.

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

4. Вычисление основных ВВХ для каждого отдельного элемента

5. Вычисление интегральных ВВХ при взаимодействии двух

любых абонентов ЛВС.

Рассмотрим каждый иэ них более подробно.

Составленио Оалаиса интенсивностей

на входе/выходе любых Фрагментов (узлов) сети

1'.ж сито отмочено еызм. Седа можзт Ошч. подставлена описанием всех составляющих 2-(31), ¡-Г7п и их параметров, а та!сад описанием распределения вногаих потоков требований по элементам Се 10 для какого "пГ-'го типа »легшего потока требований

{р-г;.

где 21 - "Г-ая СЮ свШ,

1Р1]) - матрица нар^утов.

В открытую Се1Ю требования поступают из внешнего источнтсц и поддают ее после завершения обслуживания. Если принять внешня источник за иовыл центр сети н обозначить его индексом "О",то марабут в открытой сети задается стохастической неразложимой маг-рицеП .Г* - <Ри ) , где и ^о - соответственно вероятности поступления в "3.)" элемент сети из источника и вероятность покидания требования сети после окончания обслуживания в "5]"-ом центре (}-1~).

гч

р.. - вероятность того, что требование, уходите из "СГ составля-кт^й. перейдет в "3) "-ую составляоцую сети (1,3-ГГп).

Очевидно, что выполняется следующее равенство п ^ ___

=1.0, г-«,*; ш-^а, Где р.0.

4 " СО

В зависимости от особенностей алгоритма потокораспредрленил

т

стохастическая матрица < Рп ) может быть известна заранее и входить в состав исходной информации.

При управлении потокораспределением возможен и другой вариант. В этом случае вероятности являются зависимыми характеристиками от алгоритма потокораспределения и исходник параметров ^ и , и поэтому маршрутная матрицами ) 1.1-1.п форми-

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

Нескольку для рассмотренных двух вариантов формирования матрицы требуются разные подходы к решению задачи определения распаде Ленин потоков в сети,то появляется необходимость разделения рассматриваемой СеМО на два следуют»» подкласса:

- СеМО !• м..»р1срутн'1й матрицей статических ве роят нс-теП;

- С»'МО с марлрутной м-1Триций динамических Ве[<_.ЯГН(.У:т«*Я.

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

ти.т. е. считается .что значения ЧР1 д априорно заданы. Реально же определение значений параметров <Ри ) для сети с разветвленной топологией требует проведения дополнительных исследований (натурный эксперимент или имитационное моделирование), которые по своей трудоемкости соизмеримы , а иногда и превосходят исходную задачу.

Для определения потоков,циркулируодих в стационарном режиме в открытой СеЮ с маршрутной матрицей статических вероятностей введем коэффициент передачи ¿Т такой,что«^"!/1 "представляет собой общую интенсивность потока требований, поступающих в "БГ'-ий центр сети О-Сп), а суммарная интенсивность всех внешних потоков типа " т ". Очевидно, что <С; Ко складывается из интенсивности поступления требований в "51" центр из внешнего источника Р. Л„ и интенсивностей поступления требований от других центров

Тогда значение удовлетворяет следуицзй системе уравнений

. М _ " Г т Г)*" -

¿г + & «V р/г > г = (1)

для "ш"-го типа потока , т - ТТЛ

Решение уравнения (1) в предположении, что матрица является неразложимой,сущэствует и единственно. т

Из решения уравнения (1) получаем все значения , 1 - 1,п, т -ГТк и тогда можно определить все значения интенсивностей потока требований, поступающих на вход любого " БГ'-го центра сети 1«Г7п:

т г , л? —

Д- =оС4- Ао , I . (2)

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

В связи с этим возникла следующая задача; "Разработать методику анализа СеМО с маршрутной матрицей динамических вероятностей на основе соотношений, которые связывают .в

.единую систему уравнения исходные параметры сети текущие

состояния системы с алгоритмом управления потокораспределения (параметр 0 )".

Такая постановка задачи требует решения следующих вопросов:

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

2. Выбора эффективных методов решения разработанной системы уравнений и его реализация на ЭВМ.

Определим основные подходы к реиению поставленных задач анализа для определенных двух подклассов СеМО.

Для открытой СеМО с маршрутной матрицей динамических вероятностей .система уравнений (1) преобразуется к следующему виду:

<з>

где 8 - параметр, определяющий алгоритм потокораспреде-ления в сети,

Л*~{Л-} - вектор, определи кадий всю совокупность потоков ^^ требований , поступающих на вход узла "31 ",

" вектор,определяющий параметры обслуживания 4 ^ требований всех классов потоков,проходящих

I через узел ",1-Пп.

Для решения уравнений (1) и (3) может быть использован метод Зейделя , который эффективен как для системы линейных (1),так и нелинейных (3) уравнений. Итерационный процесс метода Зейделя для уравнений (1) и (3) сходится поскольку выполняются условия нормировки вероятностей

Ри - 1.0 .

И ^огда в общем виде получим следующее уравнение:

Далее составляется уравнения баланса для определения коэффициента нагрузки и среднего времени обработки для требований лгОого класса на "1*'-м узле (1-1,п) для двух вариантов входящих потоков требований для "Iй-го узла:

- многомерный бееприоритетный поток требований,

- шюгошрньШ приоритетно поток треОоышшй. Па следующем этапо вычисляются интегральные ВЕХ для заданных марсрутов связи (обработки) между лхСыми двумя абонентами.

Лля вычисления интегральных ВВХ используются характеристики, иодучеишю для каддого 21 узла сети.

Определение интегральных характеристик, по ьоамохтм шрыру-там двикеиия пакетов, связывавдих двух любых абонентов ( М - Л^ , I у з) сводится к вычислению ВВХ для конечного числа комбинаций из следуй®«: двух топологичосга« колструк-цнЛ:

1. !Ьследовательная обработка заявок на коночном числе элементов сети (рис.2 ).

2. Параллельные альтернативы обработку рис. 3 ) с определенным! значениями вероятностей выбора заданной альтернатив«.

Рис.

г

М Л

жОЕ1

Р«с. 3

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

Глава 4. ГЛЗТ'АГОТКЛ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ СУШЩИОШГОЕАНИЯ ИГГЕЛДЕКТУАЛЫЮГО ТЕРМИНАЛА И ЛВС ЭЛЕМЕНТ АПШ

топология

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

- интеллектуального терминала как составной части ЛВС,

- ЛВС с топологией типа "¡вина" и свободным методом доступа,

- ЛК с маркерным методом доступом я топологиями типа "вина " и "кольцо".

Интеллектуальный терминал представ/.:!'?? собой персональную ЗЕЧ, включающую осноьнь-е компоненты классической фен-неймановской архитектуры: микропроцессор, память, внутреннею общую иину (О'Л), ввод - вывод. Однопроцессорная ГЖ.! использует единую магистраль, по которой передаются данные, команды и сигналы управления. Интеллектуальный терминал как составная часть ЛВС выполняет следующие Сужении:

- ресение задач, не требующих выхода в сеть (режим использования интеллектуального терминала как автономной НЗЕЗА;

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

Причем, решение конкретной задачи реализуете^ по замкнутому маршруту

"ККП - 01Л - ОЗУ - ОЫ - »ДОГ N раз. где

N - среднее число операций, необходимых для рвения данной задачи.

Учитывая данные особенности функционирования интеллектуального терминала, определим общее среднее время обработки ьадачи:

Тс«« ~ ТГсО Г (2 -г у ,

где Т*оэу - Сиднее в;>емя сбращения в (.■ЗУ;

Т си - среднее время обмена I1 СИ;

'ТГмкл - с^дн^е время м»:к лнеиия '.дн- Я о;|>-[>с;ии ь мик^про-

Инее: ре ,

""С са - I ;»-дя-->' ь; с мл ..■гр.^'итк'.: п-ио-г.» в ..ежм си:?»;*-.

Поскольку входной поток задач на обработку неоднороден (т.е. решаются разного типа задачи), то общая схема обработки требований преобразуется в модель массового обслуживания WG/1 с многомерным входным потоком и соответствующими характеристиками обработки TJîlu • вычисляемыми по формуле (5) для каждого "К"-го типа задачи.

Далее разрабатываются математические модели лес элементарных топологий: "ШИНЫ" и"КОЛЬЦА".

В основе разработки математических моделей указанных ЛВС лежит методика, изложенная в гл.2.

Типовая функциональная схема ЛВС представлена на рис. 4 , где основными элементами сети являются интеллектуальные терминалы и моноканал.

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

В зависимости от особенностей использования ЛВС и возможностей сетевой операционной системы ИТ могут выполнять функции:

- рабочих станций,

- серверов ( файл-сервер, принт-сервер),

- совмещать функции рабочих станций и серверов.

В зависимости от характера функций, выполняемых ИТ , формируется принцип генерации и распределения потоков в сети, который на уровне схемы ( рис. 4) представлен алгоритмом маршрутизации.

Тогда функциональная схема ЛВС (рис.4) преобразуется в следующие модели массового обслуживания (рис.5,6).

Представленные на рис. 5,6 модели СеЮ, в соответствии с условиями, определенными в гл. 3., относятся к классу мультипликативных открытых сетей массового обслуживания. Исходя из этих предположений и будут формироваться модели рассматриваемых ЛВС.

Математическая модель ЛВС с топологией типа "шина" и свободным ( случайным) методом доступа при одномерном входном потоке.

Основные параметры модели массового обслуживания (рис. 5) определены следующим образом:

1-1 R - интенсивность требований, поступающих на обработку от 1-го абонента,

JM, 1*1,R - интенсивность обработки требований в ОШ,

J.ba - интенсивность обработки требований в моноканале, зависит от структуры пакета, пересылаемого по моноканалу,

1 /jArZ - интервал времени об!>аОотки заявки в моноканале при

Л:,

иг.

V V

V

Л/о— 4 Ï-*

К-г

г) 4-

СМО;

А 1

а*

оп.

л

a;

МК

ш it

Р«с. А

С МО,

я

л^г-Л-

оп.

1

on tip

Ht

СМО

Mhl

' ! ми on KV

—

Рм'с. 5

■____v_____>

CM0K 6

возникноввнии конфликтов (зависит от метода доступа).

Характеристики обработки,. представленных СЫОх-СЮ^, могут быть определены на основе моделей массового обслуживания типа ц/й/1, м/Е/1, й/в/1.

Рассматривается математическая модель взаимодействия сетевых адаптеров интеллектуальных терминалов с моноканалом ЛВС.

Саза обработки СМОмк сети отражают работу моноканала со свободным методом доступа.

Предлагаемая в работе математическая модель позволяет аналитически связать все исходи!» составляйте алгоритма метода доступа С5МА/С0 со следующими показателями эффективности:

сц~ средним временем обработки пакета в моноканале с учетом Бремени передачи пакета и обнаружения конфликта,

' сРеДН1!М временем ожидания обслуживания пакета в моноканале, ТГегсуи" средним интервалом времени отсрочки для произвольного пакета сообщений,

~ТоЬпаи~ средним временем пребывания пакета в зоне моноканала от момента его активизации до момента завершения передачи («шальной станции адресуемого абонента,

Рим - вероятностью возникновения конфликта в моноканале,

Рпег - вероятностью потери пакета за счет возникновения конфликтов

в зоне моноканала.

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

В результате проведенных исследований были получены следувдие соотношения: _ м

СН-вероятность наличия пакета в "Г'-ой канальной станции, ожидающего освобождения моноканала

У»! »=/ '

где

? 1 - Л '¿г-и и з

V - коэффициент вариации времени обслуживания

_ Х/у О !/> (^-А^) , 7 - А>

'-отс.р- р С -—г~75- ~ -С -—5—-

1 ~ Л • ион 7 ион

11 ^¿¿м/ '

7Г - суммарная задержка кругового обхода канальных станция.

у-ч _ 'С

^ПОТ ~ г^ион »

Па основе мотодики вычисления интегральных ВВХ, роэрпботышюа в гл. 3, получены интегральные ЕНХ для ЛВС с то пологие л типа "ИЯ'ЛЛ" и свободным методом доступа для двух схем взаимодействия:

- с использованием централизованного сервера.

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

Далее в главе разрабатывается математическая модель £ункщ;о__ нирования ЛВС с маркерным методом доступа, учитывзкицш весь комплекс обработки пакета;

"абонент А1 - интеллектуальный терминал ИТ 1 - моноканал ПК

- интеллектуальный терминал >ГГ] - абонент А; " или " абонент А1

- интеллектуальный терминал ИТ 1 - моноканал МК - СЕгЕЕР - моноканал Ш - интеллектуальный терминал ИТ] - абонент А]" (рис. 5.6).

Для расчета ВЕХ ЛВС данного типа используется методика, представленная в гл. 3 , ориентированная на применение СоЮ с статической маршрутной матрицей вероятностей.

Обработка каждого пакета реализ>втся в зависимости от способа управления потокораспределением по трехфазной схеме (рис.6) или по пятифазной схеме обработки (рис. 5).

В результате проведенных исследований для маркерного метода доступа была разработана модель взаимодействия канальной станции с моноканалом. В частности получено соотн-'иенне для рычис*»»!!* среднего времени обслуживания пикета в мс искрим»:

• « ¿ А 1 Té; ,

Qc =

_

«= Te-

6 - сроднее врем$: передачи маркера,

Q¿- вероятность наличия пакета в "Г'-ой канальной станции,ожидающего передачи маркера,

То » b/V , где Ь- длина пакета,

V - скорость передачи информации.

Для вычисления интегральных ВКХ для ЛВС с маркерным методом доступа используется методика, изложенная ранее в гл. 3.

Далее в главе проанализированы основные источники погрешностей математических моделей ЛВС.

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

и

Г' d J

Рассматривается анализ погрешности, которая вносится этим потоком. Для этого в качестве эталона используем модель массового обслуживания 6/М/1 .

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

Модель СМО типа G/M/1 может быть разделена на два непересекающихся класса моделей:

- модель с эрланговским распределением интервала времени между поступающими требованиями (Ег/М/1)..

- модель с гиперэкспоненциальным распределением интервала времени между поступахэдлми требованиями Нг/М/1).

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

скорроктщювать, реализуя следующее соотношение:

Далее показано, что при использовании гипорэкепоненциалыюй эталонной модели, значения абсолютной погроиности (рис.8) зависят от козф^иционта вариации "С" и и могут бить скорректированы заменой Р на G^ .

Далее в главе приводится описание разработанного программного комплекса, реализующего модели функционирования ЛВС со свободным и маркерным методами доступа, предусмотренные соответственно протоколами 1EEE-8Q2. 3 и IEEE-802. 4 , IEEE-802. 5 .

Программный комплекс включает ядро ( аналитическая модель ) и сервисные средства .

Программное обеспеченно комплекса имеет модульную структуру и содержит группы модулей, которые обеспечивает выполнение следувдгх Функций:

- иерархически организованную систему меню для выбора режимов работы комплекса (СИМ);

- таблицы для ввода исходных данных моделирования (ТИД);

- управление логикой функционирования комплекса (УФК) ( включаххций ядро комплекса);

- таблицы результатов для вывода ВВХ, полученных в результате работы комплекса (TP);

- графическое оформление некоторых групп ВЕХ (ГРОР).

Все программные модули комплекса реализованы на языке программирования "С" в интегрированной среде Turto-C 2.0 для персональных ЭВМ IBM PC/AT.

Обч-ем системы около 3500 операторов изыкашС.*

Объем загрузочного Файла программного комплекса около 179 Кбайт.

Время вычисления для одного варианта моделирования в зависимости от количества рассматриваемых абонентских узлов ЛВС составляет от 0,1 до 2 секунд.

Глава 5. АНАЛЯЗ РШОТНОСТНО-ВРЕШЗШ ХАРАКТШ10ТИК ЛВС ЭЛЕМЕНТАРНЫХ ТОГАПОГИЙ

Исследовались ЛВС. в которых использованы следуивде методы доступа в моноканал:

- CJMA.'CD (протокол 1ЕЕЕ-1'02. ?) ЛВС "Еи»пк«Г.

- маркерный метод доступа по '•U33C" (автокод 1Ш'-802. 4) ЛВС "Аг ."net -st аг".

Фрищиеиа-тьхаа trsnQ /7ВС „¿tht Out С ní»iосЪм дкгуа CSMA/сЛ

У: А,с

Рхс. 9 .

Исходя из реального наличия технических средств вычислительной техники на Московском областном предприятии оптовой торговли, исследовались два варианта ЛВС:

- ЛВС с топологией типа "ШИПА" на основе технологии "Ethernet" с использованием адаптера "LAN Ethernet card".

- ЛВС с топологией типа "ЗВЕЗДА" на основе использования элементов сети "Arcnet" с адаптером "Anet 1 - star".

Топология рассматриваемой ЛВС представлена на рис. 9.

Из анализа результатов также следует, что из рассматриваемых вариантов ЛВС "Arcnet", приемлемы лишь те, у которых число абонентов не превышает 64. В этом случае среднее время ожидания освобождения терминала ЛВС составляет около 80 секунд, что является допустимым условием для решаемых на ЛВС задачах.

Далее в главе проводится сравнительный анализ методов доступа к моноканалу в ЛВС с элементарными топологиями.

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

Из рис. 10 видно, что для свободных методов доступа параметр R является главной характеристикой. В классе свободных методов доступа наиболее совершенным является метод доступа CSMA/CD, который имеет значение R < 0,078.

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

Далее в работе решается задача реконструкции ЛВС. При решении задачи реконструкции используются результаты моделирования, представленные на рис. 10,и.

Глава б. АНАЛИЗ ВЕРОЯТНОСТНО - ВРЕМЕННЫХ ХАРАКТЕРИСТИК ЛВС ПРОСТЫХ ТОПОЛОГИЯ

ЛВС простых топологий содержат в своем состав© две и более элементарные ЛВС, которые связаны между собой с помощь специальных устройств - ретрансляторов (усилителей , повторителей ) . ЛВС данного класса имеют единый протокол канального взаимодействия и являются "прозрачными" для любых его абонентов, ретрансляторы в ЛВС с простой топологией, как правило, выполняют Функции приема и буферизации пакета.

К числу таких сетей можно отнести одну из разновидностей ЛВС "Ai-ciiet" (адаптер Amt 1С bus), которая исследовалась как рабочий

-2.7-

KT

5 *ucpf>Q\n.

Пг

' I

( 1 __Z °"eppci3H.

MKX №]~<]/4l0

CZl

ïïfW] a «

H Г —A a

0=

MKi

ЦТ

ИТ

=0 ,

ИТ

дии

срр

азм.

Л ЛЛЛ

А>« А* Ли

Л I - ûfoHfHr ■ П, tflí - noó гори re rte, MX; • MOnOKQna/1,

А/Г- ингйпптгтуаллныи re[>nu»Qi.

Рис. Функциональная сьено

ABC „AtchQÍ'c ма-ïoèoHàocruna С&'МА/СГ)

шфилмт проекта ЛЛС. 4ункциональная cxeua рассштрииааиай ЛС представлена на рис. 12 .

Дли рассматриваемой Л1Ю определены исходнш дашш-j моделирования.

Используя {>азраЭотаинуи методику "декомпозиции - ¡сс^тозп-ции"( гл. 2) и результаты анализа функциональной схош рассматриваемой ЛЕС, щюдлагаетсн расчленить функциональную схему ЛВС (рис.12) на три фрагмента с элементарными топологиями (1,2,3).

Математическая модель ЛВС элементарной топологии в свои очередь расчлоняотся на модель интеллектуального терминала н юдоль моноканала Таким образом, для исследуемой в данном раздело ЛЕС ми ишен три уровня стратификации и для каадого из рассматриваемых У1ювней можно определить необходимый набор ВВХ.

Следующим этапом является композиция составлящих моделэй в одну общую модель ЛВС.

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

На основе исходных данных и разработанных математически моделей была произведена настройка программного комплекса "ШЛСЕТ" и проведено моделирование. Получены результаты моделирования и дани рекомендации по более эффективной эксплуатации ЛЮ.

Глава 7. АНАЛИЗ ВЕГОЯПЮСТ НО-ВРЕМЕННЫХ ХАРАКТЕРИСТИК ЛВС СЛОЖНЫХ ТОПОЛОГИЙ

В данной главе представлен анализ ВВХ интегрированной ЛВС в рахках исследований, проводимых по проекту "Опытный участок компьютерного интегрированного производства штампов и прессфсрм" для ПО "ТМЗ".

Постановка задачи исследования

ЗАДАНЫ

- топология исследуемой ЛВС(рис. 13).

- алгоритм потокораспределения пакетов в сети,

- исходные данные по интенсивностям входных потоков требований на обслуживание сетью,

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

ТРЕКУЕТСЯ:

tf^ífí?!« ши Ht fît "lUfrul" г тнитини i К !Î1

P*c. /3.

- разработать аналитические модели для анализа ЕВХ ЛВС,

- разработать программу реализации моделирования.

- провести моделирование и проанализировать его результаты.

Рассматриваемая ЛВС расчленяется на следующие три фрагмента:

- фрагмент 1 - ЛВС типа "Е^пвгпеС" с шинной структурой;

- Фрагмент 2 - ЛВС типа "дерево" на основе процессора телеобработки данных (ПТД);

- Фрагмент 3 - ЛВС типа "дерево" на основе ЭВМ ЕС-1043, объединяющая с помощью мультиплексорных каналов всех абонентов исследуемой ЛВС.

Обмен информацией между любыми абонентами сети осуществляется иерархически через, общие области памяти. Общие области памяти располагаются в ЗШ ЕС-1046 (используется как интегральный файловый сервер) и в файловом сервере, входящей в состав фрагмента 1 ЛВС "ЕИ-.еггиЯ".

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

Для каждого из указанных Фрагментов на соответствующем уровне стратификации разработаны математические модели Се МО и по всем схемам взаимодействия определены интегральные ВВХ

На основе разработанных математических моделей и их реализации в программном комплексе "МЭДСЕТ" был проведен анализ ВВХ рассматриваемой ЛВС и выявлены узкие места в структуре сети. Даны рекомендации по их устранению

Глава В. АНАЛИЗ ВЕРОЯТНОСТНО-ВРЕМЕННЫХ ХАРАКТЕРИСТИК ЛЕС С ЯЧЕИСТОЙ ТОПОЛОГИЕЙ

В данной главе представлен анализ вероятностно-временных и топологических характеристик системы локального обмена данными (СЛОД) специального назначения, проведенный для НПО Космического приборостроения.

Особенности объекта моделирования и его основных элементов

Обгектом исследования является сеть локального обмена данными {СЛОЮ "РЕШЕТКА" с двумя различными топологиями (рис.14 и 15). СЛОД должна быть построена на ба^е волоконно-оптической линии связи (ЮЛС). СЛОД "РЕЯЕТКА" предназначена для создания объектов управления специального'назначения. построенных на принципе распределенной обработки информации. Связь между абонентами в СЛОД реализуется по принципу "каждый с каждым".

Длина ЮЛС до П00 м. , расстояние между абонентами до 300 м.

Модули сопряжения выполняют функции "ПОСТА".

Для СЛОД "КВАДРАТНАЯ.РЕШЕТКА" (Рис.14) используется следую-гзчЛ алгоритм потокораспределения:

1. Абопент А13 связывается с абонентом Ак1 (А13 Ак1) через один единственный моноканал при следующих условиях:

а) 1-к, l-l.ro при 3^1 используется МК1 или

б) ]-1, 1,к-1.т при 1/к используется >ЖЗ,

2. Для всех остальных случаев взаимодействие между абонентами (Л13-»Ак1 Ык 3*1 при 1.3.к. 1-Т7пО, алгоритм потокораспределения реализуется следупцим образом:

- если в хюмент возникновения требования от абонента Л13 на выгод в сеть один из взаимно ортогональных моноканалов (МК1 или ЫКЗ) свободен, то свободный моноканал включается в маршрут связи;

- если в момент возникновения требования от абонента А1з на выход в сеть оба моноканала (МК1 и МХЗ) свободны, то включается в марврут связи любой из взаимно ортогональных моноканалов с равной вероятностью,

- если я момент возникновения требования от абонента А1] на выход в сеть оба взаимно ортогональных моноканала (ШИ и МКз) заняты, то требование от абонента А13 ожидает освобождения одного из них и принимает участие в соперничестве за овладение им вместе с требованиями других абонентов, находящимися в аналогичных ситуациях.

Для СЛОД "ТРЕУГОЛЬНАЯ РЕШЕТКА" (рис.15) используется следу*>-вцЛ алгоритм потокораспределения:

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

А Ц —■ А иС Таблица .

1 вар. 2 вар. 3 вар. 4 вар.

к-3 1-3 к-1 1-1 ТУ.Т\—

Ка V Ь*1 71м

л е>

ми, мкх

А.,

I—0-0

I-

ф-ф

»—О \—О

-ф

Лм J

б в

Л hl-) л

■(М

<>-о

А,«

)-1 ж,

)—i ml

Ink-

*П1 -irr)

( >-ф-—INK

A

m-i

'nrn r

— I M/in,

mc,

MU:

Рчс. /4

л,

-О -О

-О

im

►Фт-

-1Ж, I AÍ/Í»

-фф^ЧЛЖ,

Ii t

-1 МКм-t

Рис. /5

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

2. Для Есех остальных случаев, алгоритм взаимодействия между абонентами (Aij Akl, гдо i/j, i/k. j/1, k/-l, j/k. 1/1.) реализуется слчкуш'м обргмом:

- если, в момент возникновения требования от абонента Al j на выход п сеть один из моноканалов (ИК1, IKj) свободой, то он (свободный) включается в марирут связи;

- если в' момент возникновения требования-от абонента Aij на шход з сеть оба мэпокянала (МП1 н ICtj) свободны, то вкл^чаетсн и маршрут связи любой из них с равной вероятностью;

- если n момент возникновения требования на выход в сеть от абонента Aij оба моноканала (MKi и MKJ) заняты, то требование ожидает освобождение первого на них и принимает участие в соперничество за овладение ям вместе с требованиями других абонентов, находящимися в аналогичных ситуациях.

Предложенные в рассматриваем!« ЛВС алгоритмы иотокараспреде-леикя относятся к классу адоптивных алгоритмов и будут [хюлн.-юишш на основ»? модели СоЮ с марврутной матрицей динамических :-ероят-ностеЯ ( »«толика разработана в гл. 3).

Постановка задачи исследования и подход к разработке математической модели ЛВС

Для ЛВС с заданными свойствами

ТРЕБУЕТСЯ:

- разработать аналитические модели для анализа ВВХ ЛВС при однородных и приоритетных входящих потоках требований,

- разработать программу реализации моделирования,

- провести модельные эксперименты,

- провести анализ вероятностно-временных и топологических характеристик для ЛВС двух вариантов топологий!риг. 14,15).

Разработка математической модели ЛВС типУКВАДРАТНАН ШСТКА" и "ТРЕУГОЛЬНАЯ РЕЖГКА"г.ри одномерном и мкогом..-;.ном потоках TgeOopaHitg от абонентов

Составлены уравнения 'планеа интенсивностей оттзкев и коэвф!

цментов нагруеки для "»"го горизонтального и Т'-го вертикального моноканалов, которые представлены в следующим виде;

Л; = ,

Л/ -Л^+Л^+Л^ , ьдс

Д . = Мг '""р^—а.,,

м ¡»I

-ют?, V* -¿у- г-р;-^

«♦у

р^ р^ *ряг - Ри +рчг ,

^ Рл Ь

мои; ,

П.,- - ^1-1 Я (1.0,;) г-,г

* »и ^

СЬрJI¡(1рглн) ' .

. M*J « ¿¡/Jil,

имгонеипность ofpaatQHU* 4 CQ7U aSOHQHTQ

pi - интенсивность обработки пакета в "Г'-м моноканале, Jjj - интенсивность обработки пакета в "j"-m моноканале , ytcc - интенсивность обнаружения и ликвидации Конфликта в моноканале.

Спродолони основные соотносит« для вичислс-иин AtJ и Си,у' модуля сопряжения, а также интегральные ВВХ , определявшие взаимодействие двух любых абонентов сети для двух рассматриваемых топологических схем. Аналогичные • модели разработаны при наличии многоприоритетных входных потоков на абонентских пунктах ЛВС.

Представлены интегральные ВВХ в виде плотностей распределения вероятностей времени доставки информации от абонента.Atj к абоненту Ш для "R"-ro приоритетного потока требований.

На основе совокупности разработанных моделей для ЛВС типа "КВАДРАТНАЯ РЕШЕТКА" и "ТРЕУГОЛЬНАЯ РЕНЕТКА" реализовано программное обеспечение (язык "С" 1БМ PC/AT) и проведено моделирование.

Результаты моделирования показали высокие эксплутационные характеристики разработанной системы. Время моделирования для ЛВС с числом абонентов 256 не превышало 7 минут при выполнении программы на IBM PC/AT с тактовой частотой процессора 10 Мгц.

На основе результатов модельных экспериментов был проведен анализ ВЕХ разрабатываемых ЛВС, который позволил определить максимально допустимые значения интенеишюстей потеков требикжий абонентов при заданных ограничениях на вероятн:сть щ.^чга^шм вр^м-ни доставки пакетов от абонента A)j к абоненту АК1.

п р

С- Прибидениаа стоимость

СцС * С м К

-не

л/

"СП ¿ ti б i to 12 Vi /6 16 20 22 24 Рис. 16

1.0 OA 0.6 OA 0.2 0.0

L

i 2 3 ^ 5 0 Г Í Рис. 17

Далее в главе представлены исследования по сравнительному анализу топологических параметров двух типов ЛВС: "КВАДРАТНАЯ РБ-ПВТКА"- "ТРЕУГОЛЬНАЯ РЕШЕТКА". Определены понятия приведенной стоимости и живучести рассматриваемых ЛВС, на основе которых проведен сравнительный анализ их топологических особенностей.

№ основе предложенных критериев приведенной стоимости и "живучести" проведен сравнительный анализ двух топологий ЛВС (рис. 18.17), на основе которого даются рекомендации по выору предпочтительного варианта.

ВЫВОДЫ ПО РАБОТЕ

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

Рассматриваемый класс ЛВС обладает следующими особенностями:

- содержит больше число абонентов;

- обладает сложной топологией;

- содержит элементы межсетевого обмена;

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

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

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

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

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

4. На основе разработанных теоретических принципов получены:

- математические модели основных функциональных элементов ЛВС (интеллектуальных терминалов, моноканалов, элементов межсетевого обмена);

- математические модели локальных вычислительных сетей элементарных топологий;

- математические модели локальных вычислительных сетей простых топологий;.

- математические модели ЛВС составных топологий;

- математические модели ЛВС составной топологии ячеистого типа.

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

теоретическую основу анализа ВЕХ ЛВС исследуемого класса.

б. разработан диалоговый программный комплекс "МОДСЕТ", обеспечивающий проведение модельных экспериментов для рассматриваемых в работе типов ЛВС. Модули комплекса реализованы на языка программирования "С" в интегрированной среде ТигЬо-С 2.0 для персональных ЭВМ типа 1ЬШ рс/АТ. Результаты моделирования могут быть представлены в табличной и графической Формах.

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

- интегрированной локальной информационно-вычислительной сети специального назначения (проект "КИОМЦ" ПО "ГРАЮТ");

- интегрированной вычислительной сети предприятия (НТО "АЛЬТ АИР");

- опытного участ^ка компьютеризированного интегрированного производства штампов и прессформ ( ПО "Тушинский машиностроительный завод);

- системы локального обмена данными ячеистой топологии на базе волоконно-оптической линии связи (НПО "Космического приборостроения).

Основные результаты диссертации опубликованы в сдедуюких работах:

1. Климанов ЕП. Разработка математических моделей и анализ эффективности вычислительных систем Учебное пособие. НЭК. Н: 1000. 106 с.

2. Климанов В. П .Гаспарян А. Г. Многоканальная локальна* вычислительная сеть типа "РЕШЕТКА" и ее аналитическая модель. Сб. Трудов АН СССР. Издульные ин^рмационио-вычислительные системы и сети М. : 1902. с.-171-178.

Я Климанов Я П. , Порховник В. А. О вычислении распределения

безусловных вероятностей числа заявок в многоприоритетной системе кассового обслуживания с абсолютным приоритетом обслуживания. АВТ. 1074. 2. -70-73 с.

4. Климанов В. П., ГЬрховник В. А. О некоторых вопросах анализа однородных показательных сетей массового обслуживания. Труды МЭИ .вып. 1вз, )¿ , 1974 с. 104-112.

5 . Климанов Е П. Оценка адекватности имитационной модели узла распределенной вычислительной сети. -Йошкар-Ола.: В сб. Математическое и программное обеспечение САПР сетевых систем. НзрГУ, 1985. -22-28 С.

6. Климанов В. П., Гаспарян А. Г. Многоканальная локальная вычислительная сеть типа "РЕШЕТКА" и ее аналитическая модель. В сб. "Вопросы кибернетики" 1С КЛ "Кибернетика" АН СССР 1991. -76-64 с.

7. Климанов В. П., Батуркин Е. С. Порховник В А. и др. Проблемно-ориентированный язык программирования для решения задач теории массового обслуживания. М.: Труды МЭИ, выпуск 221, 1975. с. 33-58.

8. Климанов В. П. Математическая модель распределения нагрузи! в многоканальной лекальной вычислительной сети матричного типа. Четырнадцатая всесоюзная школа-семинар по вычислительным сетям, 4.1,11: -минск. 1969, с. 216-220.

9. Гаспарян А. Г., Климанов ЕИ Диалоговая система проектирования узлов распределенных вычислительных сетей. Труды 13-ой всесоюзной школы-семинара по вычислительным сетям. -М.: -АЛМА-АТА.: НС КП -кибернетика" АН СССР, 1988. т. 3. -44-48 с.

10. Климанов В. П. Методика проектирования узла распределен ной вычислительной сети с минимальной стоимостью. Труды 12-го всесоюзного семинара по вычислительным сетям. М.: -Одееет, ПС КП "Кибернетика" АН СССР, 1987. т. 1. -64-68 с.

11. Климанов В. П. Математическая модель распределения нагрузки в моноканальной локальной сети 3BW со случайным доступом. Труды четырнадцатой всесоюзной ¡meoлы-семинара по вычислительным сетям, -U.: -Минск, НС КЛ "Кибернетика" АН СССР, 19S9. т. 3. -59-63 с.

12. Климанов В. П.. Гаспарян А. Г. Программная система анализа моноканальных вычислительных сетей на основе аналитического моде• лирования. Труды 15-ой всесоюзной школы-семинара по вычислительным сетям, -М.: -Л: НС КП "Кибернетика" АН СССР. ЖЮ. т. 3. с. 1У! -196

13. Климанов -В. IL Унифицированная сипт>-ма прстраммир-р.шии для решения задач теории массового обслуживания. Тез. д.-кл.чдов Всесошного научно-технического совещания "Автомат и.тирелмшше

системы управления непрерывными технологическими процессами в химии, нефтехимии, металлургии и энергетике" М. : 187а с.-107-109

14. Кайманов а П. Анализ вероятностно-временных характеристик многоканальной локальной вычислительной сети матричного типа Труды 15-ой всесоюзной школы-семинара по вычислительным сетям. к: -Л: 1090. т.1. -208-213 с.

15. Климанов В. П., ЗяОлова IL П. Математические модели для анализа вероятностно-временных характеристик систем локального обмена данных с конфигурацией типа "РЕШЕТКА". Труды юбилейной научно-технической конференции "Новые информационные и электронные технологии в народном хозяйстве и образовании. МЭИ, 11: 1990. секция 2.

16. Климанов Е П., Гаспарян А. Г. Многоканальная локальн ы вычислительная сеть типа "РЕШЕТКА" и ее аналитическая модель. Тезисы докладов Восьмого Международного симпозиума по проблемам Модульных информационно-вычислительных систем и сетей. Дубна. : АН СССР, 1991. -52 с.

17. Климанов Е П. Математическая модель распределения нагрузки многоканальной локальной вычислительной сети с топологией типа треугольная решетка. Труды 1б-ой всесоюзной школы-симинара по вычислительным сетям. -М.: -Винница.: НС КП "Кибернетика" АН ОХР, 1991. т. 1. -122-126 с.

18. Климанов Е П. Анализ вероятностно-временных характеристик многоканальной локальной вычислительной сети с топологией типа треугольная решетка. Труды 1б-ой всесоюзной школы-семинара но вычислительным сетям. -U. : -Винница.: Ш КП "Кибернетика" All OTP, 1991. T. 1. -117-121 с.

19. Kllmanov V. P. ,Gasparya» A.G. Conpulor-Aided Laboratory Praoticum for Analysis of Probability- Tin» Caracterlôtic-ô of local Area Networks on the Basis of Analltlc Simulât юг, of Learn 1 lie Environment. Abstracts. East- West Cjnrerence on En»>r¿n>tf Computer Technologies in Education. ICST1, M. : 1992. p. 87-ил.

20. Климанов E П., Гаспарян А. Г. Автоматизированный лабортч> ный практикум для анализа вероятностно-временных хар>актеристик локальных вычислительных систем на основе аналитического моделирования учебной среды. Тезисы Конференции Восток-Запад по новым информационным технологиям в образовании. МЦНТИ М. : 1992. с. УУ-100.

21. Климанов Е П. Анализ топологических особенностей двух типов многоканальной ЛВС: "КВАДРАТНАЯ РЕШЕТКА" -"ТРЕУГОЛЬНАЯ РИИЕТ-КА". Труды 17 -ой Международной школы-семинар;* по вычислит. льн14м сетям.-U. :-АЛМА-АТА. : В.' КП "Кибернетика" К>ссийск...й ЛИ. !му:>

С. ЮГ-107, •• - ....., ~

: - V S •■■ К с ¡J