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

Санкт Петербургский Государственный Технический Универсистет

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

ГАГАРИНОВА НАДЕЖДА ЮРЬЕВНА

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

05.13.13. "Вычислительные машины, комплексы, системы и сети"

АВТОРЕФЕРАТ

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

С.Петербург 1994

Работа выполнена в Санкт Петербургском Государственном Техническом Университете на кафедре "Системный анализ и управление*

Научные руководители:

д.т.н. проф. Воронин A.A.

к.т.н. доц. Станкевин Л.А.

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

д.т.н. проф. Черкесов Г.Н.

к.т.н. доц. Кисаржевский В.Ф.

Ведущая организация: Военно-Космическая Академия им. Можайского.

Защита состоится :•??><■ у - ' * 1995 года, в часов на заседании специализированного совета N ЪОбЪ.ЛО^ в Санкт-Петербургском Государственном Техническом университете по адресу: 195251, С.Петербург Политехническая ул. 29.

С диссертацией можно ознакомиться в библиотеке института. Автореферат разослан_ 1994 года.

Ученный секретарь

специализированного совета ,;

д.т.н. проф. < ч ■ Дурандин К.П.

« • Г .-"*"->

/

- 3 -

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

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

Сотрудничество меяду отраслями приводит к тому, что большинство локальных сетей объединяются в глобальные с помощью сетей передачи данных (ГЩ), связывая все большее число пользователей. Отказ в сетях ПД ведет к значительным убытка},!. Поэтому, большое внимание уделяется работам, направленным на улучшение их эффективности функционирования, повьшения их надежности и т.д.

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

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

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

Состояние проблемы и задачи исследования. В настоящее время разработано достаточно много методов и моделей анализа сетей ПД с различными топология}®. Известны работы Верш П., Гадасина

B. А., Захарова Г. П.. Морозова Ю. М., Праневичуса Г. И.. Присязнша

C. П., Рябинина И. А., Ушакова H.A., Филина Б. Н.. Шарейко Л.А., Черкесова Г.Н., Хагина A.A., Huang Т.3.. Mitchell Tony L.. Nil-son Arne A., Shier D.R.. Wang J.P. и др.

В этих работах предлагаются разнообразные методы и модели

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

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

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

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

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

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

4.Разработка общей методики анализа, основанной на комбинированном методе, позволяющей проводить анализ эффективности функционирования сети ПД с учетом структурной и Функциональной организаций сетей.

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

1. Предложен критерий эффективности функционирования сети ПД, учитывающий ее структурную и алгоритмическую надежность.

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

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

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

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

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

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

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

4.Определены области преимущественного использования сетей ПД с различны;,:;! топологиями в зависимости от параметров сети и параметров входных данных.

Реализация в народнем хозяйстве. Результаты диссертации использовались для обоснования работа тестера сети ПД на X. 25 и исследования сети ПД с быстрыми коммутаторами, и внедрены в ОКБ "Радуга" и BKA им. Можайского, о чем имеются соответствующие документы.

Апробация работы. Пакет прикладных программ по анализу структурной надежности и выбору параметров сети ПД демонстрировался на ВДНХ "Здравохранение-90".

Основные полозения диссертационной работы реализованы при выполнении ряда НИР. Теоретические результаты обсувдались и были одобрены на следующих конференциях и семинарах: 1-" Международном учредительном научно-коммерческом симпозиуме "Волокони-ка-90". г.Суздаль, 1990; Всесоюзной конференции "Надежность, живучесть и безопасность автоматизированных комплексов", г.Суздаль. 1991; Всероссийской научно-технической конференции "Транс-

kom-S4", г.С.Петербург, 1994; Научно-технических семинарах ОКБ "Радуга" и BKA им.Нсгайского, 1994; Научно-технических семинарах профессорско-преподавательского состава каф. ТК (САиУ) СПбГТУ, 1992-1994 гг.

Публикации. Основные результаты нашли отражение в 6-ти публикациях [1-6].

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

Объем работа. Диссертационная работа состоит иэ озеленил, четырех глав, заключения. Работа содержит 155 страниц тенета, 28 рисунков, 9 страниц библиографии из 115 наименований.

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

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

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

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

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

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

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

ции и каналах ПЛ. и доставку данных в неискаженном виде по адресу за заданное время при заданной пропускной способности сети и воэмонных эагруз!ш и отказов ее элементов.

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

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

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

рис.1. Обобщенная структурная схема сети ПД.

Выражение для вероятности связности входного и выходного узлов коммутации имеет вид:

Рс " Ро-{Р1-Рог1Р2-Ог-(1 -Цзг-01г) А% + + (1 - Рг-Цг-(1 - 0оП-0]2))-В%] +

+ (1 - РГ<1 - - Оог)'С*3) 0П.!, (1)

где

А| - Р| '<1 - Оо.1' 01-г.(' 01 1,1 > о.:

B, - Р, (1 - Оо,, • - 2.,) • И,; 1 « ЗЛЫ

C, - Р, -<1 - Оо., • 0,-1,|>'в1: А\ - А, - А*!и + (1 - А,)-В*и1:

В*, - В, ■ С* 1 +!; 1 - ЗГ1Г2

С", - С, -А*,41 + (1 - С,) ■ Вм];

О, - Ри (1 - о, 12 + - Рц-(1 -

А*., - А„ •А* им 4 (1 - А,,)- В* 11 +1 ■ J - 2,Т

в*„ - в,. •А* ии + (1 - В,,)- в*, ; 1 » 2Ж-\

А,, " Р») ' (1 - о. .и ' °1) -1.11 ) j - 27к

В,) - ри' (1 " 01 , 1] ) 1 = 2.М-1

?! - показатель надежности 1-го узла коммутации;

Р,)- показатель надежности канала (Щ между 1 и 3 узлами коммутации;

- вероятность связности меаду узлаки коммутации с номерами И и 1к (1-1,N-1). т.е. элементами ниннего уровня; 0,-1-Р, 0„«1-Р„.

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

Для получения кольцевой топологии сети ПД необходимо пред-полоаить РО1=0 (1-2.N-1), Р^нг"0 (1-1.М-3), тем самш полагая, что эти связи в течении всего времени работы сети находятся в неработоспособном состоянии, а 0,-1 при (1-0-1). т.е. пугаем, что элементы низшего уровня не влияют на работоспособность

сети. Тогда, рекуррентное соотноиениэ для оценки вероятности связности сети с кольцевой топологией принимает вид:

Р0 - Рь-{Р1-Р01-[Рг-1-(1 - 1-0,г)-А% +

+ (1-Р2-1- (1-1-012)) •В%]+(1-Р1 • (1-Ооц)) -Р2 -1- (1-1) • С*з) -1 -- Ро"{Р1-РО1-СР2-(1-01Е)-А%+ (1-Р2-(1~й12))-В%]}. где А, - Р, • (1 - 0|-1, |); В, - 0; С, - Р,-(1 - 0|-1.») " А,

А*, - А! -А*1 + 1 ;

С уметом коэффициентов, выражение окончательно перепишем:

Рс " Ро-Р1-Ро1-Рг-Р12-А*3 •

Для получения топологии "петля" примем Р01-О (1-3. (Ы), тогда

Р0 - Р0.{р,-Р01-[Рг-1-(1 - Оог-й1г)-к*3 *

+(1 - Р2• 1 • (1 - 0э2-а12))-в*3] +

+ (1 - Р1-(1 - 001))-Рг-1-(1 - Оог)-С%)-1. где А, - Р, -(1 - 01-2,!' 01-1,1>:

в, - р, -(1 - о,.-!): 1 - ОРТ

с, - р,-(1 - о,-!.!)^,:

• С учетом коэффициентов А, В, С и А*, В*, С*, которые вычисляются по формуле (1) получим окончательное выражение для Р0:

Р0 - Рг^г'р12'А*з + <1 - Р2-Р12>-В*з>:

Для получения шинной топологии сети ГЩ необходимо соединение каждого узла коммутации со всеми остальными узлами сети. Тогда, элемент с нулевым номером в структуре сети ПД в данной случае будет играть роль канала общей шины (моноканал). Для получения рекуррентного выражения для оценки вероятности связности сети ПД с топологией "шина" необходимо, в соответствии с выше сказанным, принять Р,, 1+1-0 (1-1.N-2). Р^ц^-О (1-1,N-3), 0(-1 (1=1,N-1) . Окончательное выражение имеет вид:

Р0 - Ро-Р<н -Ро! 'Р): где 1 * У. 1,¿-1.Н-1.

Для получения древовидной топологии сети ПД необходимо принять Р,, 1 + 1=0 (1=Ок2), Р,11+2=0 (1=1,N-3). В этом случае мы получаем выражение для одной ветви дерева, с помоцьа которого можно определять структурную надеаность (Рв) всех ветвей, а затем вычислять надежность всего дерева. Например, в случае независимости фушецнониропшшя ветвей, надежность всего дерева моано вычислить по следующей формуле:

Рд -1-(1-рв1) (1-рв8) • - • (1-Р.н-1): Р»1-РоР»01:

Рд - структурная надежность сети ПД с топологией "дерево";

Рв1- надежность 1-той ветви дерева, 1=1. N1.

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

На основе разработанного рекуррентного выражения проведено исследование сети ПД с типовыми топологиями и определены области преимущественного использования различных структур в зависимости от ресурса сети ( Л.Т < 0.001; 0.001 < ХТ< 0.01; ХТ >0.01 и числа узлов в сети ПД Ш < 10; 10 < N < 20; Н > 20).

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

Задача анализа структурной надеаности сети ГЩ, кроме оценки эффективности функционирования сети по критерию вероятности связности, включает также выбор параметров сети ПД, обеспечивающих выполнение требования по надежности. Структура сети Б.выбирается исходя из зависимости:

Б - Э' при Р0 = Г(в1п кр) > Мтр,

где 8'- структура сети ПД с новыми выбранными параметрами,

кр - общее число зарезервированных узлов в сети ПД. - требуемый уровень надежности.

Задача выбора параметров сети решена "классическими" алгоритмическими методами - методом динамического программирования

и эвристического поиска. Первый метод позволяет ресать задачу поиском в "ширину". Задача выбора параметров структуры сети ГШ методом динамического программирования роиается следующим образом.

Выбор параметров структуры считается наилучшим, если обеспечивается требуемнй уровень надежности (Р0 < !1Т р) при наимень-пем числе резерппых узлов (кр).

Поиск наилучших параметров структуры получается более эффективным благодаря пошаговому анализу (т. е. анализу поело каз-дого резервирования узла). К каждому узлу коммутации сети ПД поочередно подключается резерв и с помоцьп рекуррентного соотноие-ния (1) определяет вероятность связности сети Рс(1. ^). где 1 -1,кр. ,) - 1, И; N - общее число узлов коммутации в сети ПД.

Далее, выбираем параметры структуры, обеспечивающие наибольшее значение Рс(1,Л). Полученное значение вероятности связности узлов в сети сравнивается с требуемым уровнем надежности: если значение вероятности связности меньше требуемого уровня надежности Нтр. то для полученной системы с одним зарезервированным узлом коммутации повторяются визе перечисленные действия.

Метод эвристического поиска позволяет решать задачу выбора параметров поиском в "глубину", уменьшая при этом сложность решения ( (Н-1)Кр при динамическом программировании и (М-1)г при эвристическом поиске). Супение поиска достигается за счет применения некоторого набора ограничений действий. Таким набором являются эвристические правила, выявленные на основе результатов анализа. Эти эвристические правила позволяют решать задачу достижения требуемого уровня^надеаности путем направленного резервирования. Направление резервирования определяется путем вычисления вкладов.

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

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

1 Nlp 1 154(514) 152(512)

/у 12 153(513) 151(511) 155(515)

у ,14 13 11

" " у г м 2

1 ! 1 Кр 4

рио.2. Граф решений в динамическом программироаании и оври стическом поиске для сети ПД шинной топологии.

автоматизирован путем применения оболочки экспертной системы "Inter Expert". Такой подход позволяет изменять набор правил в диалоговом режиме без изменения всей программы вычислений.

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

РА - PUF'tE,) - F(Ej)) < ¿j при Б, с Е), где Е - мноеество входных данных, определяющих все воэмоа-ные наборы;

F'(Е[) - результат выполнения алгоритма;

F(Et) - точное значение результата выполнения алгоритма;

Л, - приемлемое отклонение результата выполнения алгоритма.

Тогда за отказ алгоритма 0А примем событие, заключающееся в получении ошибочного результата, т.е. результата, не удовлетворяющего некоторому условию:

Од - Р{(Г* (Е,) - Р<Е!)) > Д, при Б, £ Е).

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

Так как алгоритм реализуется в протоколах, а протокол обеспечивается доставкой данных от одного до другого абонента и учитывая, что Б, представляет собой объединение параметров сети (Б) и входных данных (В), предложено оценивать алгоритмическую на-деаность сети ПД вероятностью доставки (Рдо) пакетов по адресу в неискаженном виде за время, не превышающее 1;8"; где Ц" - норма времени доставки,

Ра * Рдо - < 0) при «.В) е Е).

Л

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

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

Задача решается при следующих допущениях:

1. Комплекс аппаратных средств абсолютно наделен;

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

3. Модель потока ошибок в дискретам каналах 1Щ - биноминальная, характеризуемая одним параметром - вероятностью неверного приема единичного элемента, основанная на предположении независимости возникновения ошибок.

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

Анализ трех уровней сети ПД. базирующийся на протоколе X.25 поизводится на основе комбинированного аналитико-иыитационного

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

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

Формализованное описание процесса функционирования сетевого уровня с помощью сетей Петри представлено на рис.3.

рис.3. Формализованное описание процесса функционирования сетевого уровня с помощью сетей Петри.

Канал ПД, согласно модели 031. представляет собой совокупность средств двух нижних уровней: физического и канального. Основной характеристикой его является эффективная скорость передачи, которая зависит от избыточности передаваемых данных и мозет быть минимальной и максимальной т.е. [7]:

где Пк - общее число элементов в кадре;

г - число проверочных элементов,

V - скорость передачи по каналу ПД, бит/с.

ПсЛ - дополнительная служебная информация в кадре,

Р0 - вероятность ояибочного приема единичного элемента.

к

Среднее время доставки данных выражается через параметры '.»одели канала ПД и модели сетевого уровня, т. е.

Тле - Е1! (V, Р0. Пк. г. Пол. киай> к. „

Ъс " ^ ^«вр! + ^оч1),

где к* а и - число каналов ПД, проходимых кадром данных.

^пер1'Т0Ч1 - среднее время передачи и пребывания в очереди передачу кадра по 1 -му каналу ПД, которые определяются как:

» кх „ к!к_.

041 1/ 1/ '

где пк - средняя длина 1садра,

- средняя длина очереди на передачу по каналу, которая равна произведению числа кадров (1,) средней длины (пк). " эффективная скорость передачи канала.

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

^

Тдо - Рг(ц.Р,.!*.Ку). Тдо (Твр, + Т.,).

где Тпр1, Тп| - среднее время пребывания в очереди на обс-ънипаниэ и обслуживания 1 узлом коммутации пакета.

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

где 1п - длина пакета.

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

г„р1 р-^ : и-Шр^.щ^:

р - загрузка компонента сети ПД.

Тл

ер!

*эф

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

/ Ввод / / исходных / / данных /

Генерация первого пакета

X

Определение

раннего

события

реакция на освобождение канала от ПД

1=3

X

реакция на освобождение узла от обра Сотки пакета

X

1=4

1-10-реакция на срабатывание тайм-аута

1=5

X

■11-реакция на

освобождение

сети от обработки пакета

Вычисление вреыеии доставки пакета Тдс

рис. 4.

Обобщенная схема моделирующего алгоритма процесса функционирования сети ПД.

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

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

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

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

Далее, вычисляются времена обслуживания пакета 1-ткм устройством (узлом коммутации или каналом ПД), а также время доставки по приведенным выие формулам.

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

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

- определены, области преимущественного использования сетей ПД в зависимости от загрузки компонент сети ПД (р <0.7. р >0.7). Локальная сеть ПД шинной топологии обеспечивает вероятность доставки пакетов на 2% выше, чем локальная сеть кольцевой топологии

и на 12% вше, чем глобальная сеть ПД при больших загрузках компонентов ( р >1 ).

- показано, что повышение вероятности доставки пакетов может быть достигнуто за счет увеличения числа каналов при их наибольшей загрузке. Введение калдого дополнительного канала увеличивает вероятность доставки на i% , загрузка при этом снижается на 1536. Наименьшее число каналов в сети ПД. обеспечивающее требуемую точность доставки пакетов качественно и в срок, определяется с помощью интерполяционного многочлена Лаграняа.

- определены параметры сети ПД. обеспечивающие наибольшую вероятность доставки пакетов (для кадра 1АРВ г^ - 104В. бит; 1п -1000 бет; Зц, - (0.6 ^ 0.8)д ; Ь0[ - 200 пакетов). Использование сети ПД с этими параметрами позволяет увеличить вероятность доставки до 15% по сравнению с другими параметрами.

- показано, что вероятность доставки пакетов в сети ПД при адаптивной маршрутизации обеспечивается в среднем на 4% вьше, чем при статической маршрутизации.

На основе комбинированного метода анализа алгоритмической надежности сети ПД для ОКБ "Радуга" было сделано обоснование работы тестера. Доказана возмоаность исследования реального узла коммутации тестером, характеристики которого уступают характеристикам объекта диагностирования.

В четвертой главе представлены две методики анализа эффективность функционирования по объединению двух рассмотренных ранее частных критериев. Методика раздельного учета частных критериев предусматривает их объединение в виде произведения вероятностей связности и доставки данных за заданное время. Результаты такого объединения частных критериев эффективности функционирования локальной сети ПД с топологиями "кольцо" представлены на рис.5 в виде графиков Р=ШвТ). Такой подход позволяет получать верхнюю оценку эффективности функционирования сетей ПД.

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

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

шее. Сравнение результатов, полученных на основе комбинирован-юй модели с результатами, полученными с помощью модели Хагина :8], позволяет сделать выводы;

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

- комбинированный метод является корректным и состоятельном.

Рл.(Ро)

р*«(р. )

рис.5. Зависимость частных критериев и эффективности функционирования (Еф) от времени работы локальной сети ПД с топологией "кольцо" при различных а) интенсивностях (л) и б) загрузке (р), где Еф4, Еф1 - результаты раздельного и совместного учета частных критериев.

На основе разработанной комбинированной модели анализа было проведено исследование сети ПД с быстрыми коммутаторами для В1СА к:.!. Ногайского, которое позволило разработать схему переютчения спутникового канала ПД длл уменьшения среднего времени доставки пакетов кезду фиксированной парой абонентов и выявить "узкие" места в сети.

ЗШШЕШ2

Основные результаты проведеншх в диссертационной ра£ -.те исследований состоят в следующем:

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

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

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

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

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

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

ОКБ "Радуга".

7.На основе общей-методики анализа эффективности функционирования проведено исследование сети ПД с быстрыми коммутаторами, входящей в состав системы управления движением транспортных средств, для BKA им,Можайского.

Литература:

1.Воронин A.A., Гагаринова Н.Ю., Станкевич Л.А. Системы управления приводами на технических мышцах.// Труды 1 Меидун. син-позиума "Волоконика-90". Суэдаль-1990.

2.Воронин A.A., Гагаринова Н. Ю., Станкевич Л. А. Надежность сетевых систем управлениях). // Тезисы конференции " Напевность, живучесть и безопасность автоматизированных систем ", Суэ-дапь-1991.

3. Воронин А. А., Гагаринова Н. Ю., Станкевич Л. А. Эффективность сетевых систем управления.// Труды СПбГТУ. -1993-N

4.Гагаринова Н.Ю. Эффективность сети передачи данных в автоматизированных системах управления.// Труды Всероссийской на-учно-технич.конференции "Транском-94", С.Петербург-1994.

5.Гагаринова Н.Ю, Использование результатов моделирования для обоснования работы тестера. // Научно-исследоват. отчет, шифр "Развитие" ОКБ "Радуга". -1994.

6.Гагаринова Н. Ю. Исследование сети передачи данных с быстрыми коммутаторами. // Научно-исследовательский отчет BKA им. Мо-аайского, -1994.

7.Чернега B.C.. Василенко В.А., Бондарев В.Н. Расчет и проектирование технических средств обмена и передачи информации. -Н. : Выс. шк. , 1990.

8.Haqin A.A. PeriormaMlity, Reliability and Survivability of Communication Network: System of methods and models ior eva-lution. // The 14 Internetlonal Confer, on Distributed Computing Systems. Poznan, 1994

Подисаио к печати 27.Т2. 9't. Заказ И 695. Тираж ТОО.

Отпечатано не ротапринте ИПЦ СПбГТУ. Санкт-Петербург, Политехническая ул., 29.