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

ЛГЛДВлЖ НАУК рЕСЕлЕЛИКИ УЗБЕКИСТАН

ндэтко-п?а2юлст?шкоЕ СЙЩИНБННБ "кибернетика"

На права-: руквпзсг:

гссшшаер ту',г,-.:

сшшсащюико-Ш1ГАЩОЬЖЕ ШДЕЖ и ашяпш построения и кссхщззмт распредкпенкм рь^сжтж-ж сете!

Сяец-газзноста С5.12.14. - Сети, узт czzsя г*

распределение информация

A s г о р з g о р а ? диссертанта яз сапсвапкз ученой стехгепк дзиторз технических наук

Tsscsst - ÍS9í

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

Научный консультант: доктор технических- наук, профессор Вашев Т.Д.

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

член-корреспондент АН РУз Еекыуратов Т.Ф. доктор технических наук, профессор Хасанов П.Ф. доктор технических наук Атахагов Р.Ы.

Ведущая организация: Ташкентский электротехнический институт связи Министерства связи . РУз .

Еащнта состоится «М - акмЫ _1894 г. а / 7 чао

на заседании спетртялияированного совета Д 01Б. 12.21 л научно-производственном объединении "Кибернетика" АН РУз по адресу: 700143, г.Ташкент, ул. Ходжаева, 34,НПО "Кибернетика" АН РУв.

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

Автореферат разослан ^¿¿СЫ 1994 г.

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

В.З.Шаисиев

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

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

Сложность и многоплановость задачи оптимизации ИБС и сетей ЭРМ предоставляет исследователям большой простор для поиска новых подходов, методов я средств редания по наилучшему выбору параметров компонентов ШЗ и их алгоритмов функционирования, обеспечивающих объективный компромисс мелду эффективностью и стоимостью системы, В зтом плане с кдует отметить появшаиеся сравнительно новые научные направления по оптимизации п. анализу качественных характеристик сетей связи, динамическому управлении потоками з распределенных информационных системах, разработке моделей систем ц сетей массового обслуживания, формализованному описания п верификации протоколов и сервиса в распределенных и локальных сетях ЭВМ, моделированию каналов связи, исследованию перспективных цифровых сетей интегрального обслуживания (ЦСИО). Тем не менее, несколько в тени остаются вопросы системного рассмотрения проблемы оптимизации ИБС й сетей ЗЕМ, позволншре проводить поиск искомых характеристик во взаимосвязи алгоритмических, структурных и стоимостных показателей системы со стоимостными потерями пользователей, возникающих та-га несовершенства их функционирования. Решение задачи- в такой постановке позволит создавать такие ИБС, в которых сумма затрат на создание их с определенными качественными показателями и остаточные интегральные потери -потребителей информации от яеидеальности достигнутых качественных показателей будет минимальна.

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

- найти решения частных параметрических задач во определению оптимальных алгоритмов и параметров передачи сообщений базовой %ети обмена данными (ВССЩ);

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

Научная новизна результатов исследования состоит «в следущем:

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

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

- формализована и решена задача оптимального распределения потоков между рабочими и терминальными системами РВС с ограниченными ресурсами;

- разработан метод решения еадач оптимального распределения потоков в РВС при неформяпизуемости целевой функции;

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

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

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

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

Направление работы. Диссертационная работа выполнена в процессе проведения фундаментальных и прикладных исследований по темам:

- "Разработка теоретических и методологических основ ' штши-вацни систем передачи- данных в МИГ (1976-1986), УДК 621.391.120, К гос. регистрации 74039599;

- "Системный подход при автоматизированных методах оптимизации систем передали данных". (1981-1985), УДК 621.391.123, N гос.регистрации 81055991;

- "Разработка методологических основ построения и эксплуатации информационно-вычислительных сетей с использованием адаптащг- -онлых фрагментов" (1986-1990), УДК 621.391.133, N гос.регистрации 081600 44166;

- "Создать и ввести в эксплуатацию первую очередь региональной вычислительной подсети •'Средняя Азия" Академсети , {1986-1590), УДК 621.391,задание ГКВТЙ 92.01.01.0?А.

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

Основные научные положения и результаты, вкнсскше на защиту сводятся к следующему:

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

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

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

- методика решения параметрических задач, позволяющая путем имитационного и стохастического моделирования на ЗЕМ определить йарамегры передали данных а ЕСОД при учете реальных помех в кзяа-' дах связи;

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

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

Апробация работы. Основные материалы проведенных исследований а разработок докладывались на VI,VII Всесоюзных конференциях по теории кодирования и передачи информации.(Томск, 1975, Вильнюс, 1978), на IV, X, XV Всесоюзных школах-семинарах по вычислительным сетям (ТашкентД979,Москва, 1985,Ленинград, 1990), Всесоюзной конференции "Техническое и программное обеспечение передачи и телеобработки данных и АСУ" (Рязань, 1985), V - Всесоюзной конференции "Вычислительные сети коммутации пакетов", КОУПАК - 87 (Рига, 1987), Республиканской конференции "Методы управления технической диагностикой и восстановлением работоспособности элементов сетей . связи" (Ташкент, 1988), Всесоюзной научно-технической конференции "Проблемы создании и использования отраслевых информационно-диспетчерских систем на основе компьютеризации и перспективных средств связи" (Москва, 1983), XI Всесоюзном совещании по проблемам управления (7аикент,1989), Международной научной сессии, посвященной Дню радио СССР,"Майская сессия" (Москва, 1990), XI Всесоюзной школы-семинаре го проблемам управления на сетях и узлах связи (Звенигород, 1991).

Публикации.По теме диссертации опубликованы 39 печатных работ, в том числе одна монография- • ----

Объем и структура работы. Диссертация состоит из введения, шести глав, заключения, списка литературы и приложения. Основное содержание излажено на 259 страницах машинописного текста, включает 28 рисунков и 6 таблиц. Список литературы содержит 221 наи-ыенований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность проблемы, формулируется: цель исследования,основные научные положения ж результаты, практическая ценность и степень апробации работы.

Первая глава дигоертациошши работы посвящена систематиниро-

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

Основной проблемой создания ИБС является максимизация эффективности ее функционирования по выбранному критерил. Традиционные методы ассгэйсззззк и формализации задач в основном направлены на создание к проектирование сетей 32М, удовлетворявшее потребности пользователей по все:.; парамэтрал, что означает: вся топология >:-гп - количество и пропускные способности каналов и узлоз, количество и производительностя рабочих систем (HOST - мания) и т.п., определяется из "необходимости". В реглыщ:-; ситуациях упомянутые характеристик!! определяются яг "зсзмотнсстей", т.е. количественные я качественные "характеристик;! компонентов сети конечны /гее задано мгкьзз неабходге-юго/. Поэтому проектирование сетей-ЭВМ необходимо проводить именно с этих позиций, т.к. з этом случае рэ-rasre-e значение, помимо количества и качества материально-технических ресурсов, зашагает оптимальное их использование, етгда компонент выполняет свои фуккцал наилучшем для данного ре-:;:то,'л образом. Данный подход позволяет рационально распределять сгрзн7г»5ннк9 вычислительные и кдамуникацпенные ресурсы' сети путс-м перераспределен!:." файлов пользователей на другие, менее загргаен-илл более мсг^ные H0ST-3EM, естественно, с учетом загрузки л пропускной спсссСеосто к.".налез. маршрутов, подходящи,-: к альтернативным рабочим системам. Так» следует отметить, что практически всегда учитывая верность передававши ¡шфермации, упускается ее прямая связь с качеством каналов, определяемых уровнем помех в них, т.е. зе учитывается вэкаейаэй факт - связь распределения по-ч&х с рази.ной пропускной способа. „таа, которая может привести :-: непрая:гльным сценкам степе ни загрузки кзнадоз и, как следствие, л неправильному распределение потоков и синтезу тапслсппесксй гтруктуры сети. Л, наконец, автономно реаа« оптимизационный задачи, зачзстух незезмояно получить характеристики, удезлетзорягщге как потребности кельгезателез, так и гозмсгености самих арсектд-' рег^дпкоз.

25сС^;-эннзл концеаия системной техника - экономической оптимизация сложных с;'.':тем, предложенная профессорам Вазиевыи Т.А., является "методологическим каркасом", с помогаю которой целесосб-

- в -

рззно осуществлять синтеа любой ш^юриациокиой системы и 10: компонентов. Согласно данной концеЛЦЗП1, обдаз. постановка задачи оптимизации распределенной ВС формулируется слгдукдим образам.

Необходимо определить такую структуру распределенной вычислительной , сети, позволяющую обслуживать информационные потоки при 'минимальной сумме приведенных затрат и потерь во Есех компонентах сети, т.е. минимизировать функционал __ _ 2 _ __ o.ífíJz.ts) - E0i(fi,fe,f3) . (i)

. ___. f t F, . Рг . íjfc F5

где Ci(fi,f2,f3) - стоимость затрат на создание и эксплуатации FBC. Эта компонента однозначно связана с приведенными капитальными и эксплуатационный! расходами и определяется известным зыраже-

с

теи _ _ __

__0i(fi,fe,f3) - wnK(fi,f2,f3) + 9(fi,fE,f3);

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

CzCfi,fE,f3) = Е tCKC(fi,f2,f3) + Coc(fi,f2)f2}b.

3-1

где N - общее число пользователей РВС;

Ckctfl.f2.f3) ~ стоимость потерь 3 - пользователя от задержек я ошибок в коммуникационных системах РВС;

Cpctfl f3> - стоимость потерь j-пользователя ¿;з-га задержки в_рабачих системах РВС;

fl - вектор структурных параметров, однозначно характеризующий топологическую структуру РЗС;

fl- te(A,B),L3, fi£ Fl o G(A,B) - ресурсный граф, отображающий топологию РВС;

Aíai,a2i....,множество версии графз, сопоставляемых центрам коммутации пакетов (ЦКП), к которым подключаются терминальные и рабочие системы (ТС,РС);

B=íbtf' } i. j> - множество ребер графа, сопоставляемых ветвям (каналам) РВС;

(i,3>í7Mcf'5 ,MCf' '-число ребер fi-взрканта топологии сети;

tIf и It ~ матрица "длин" ветвей сети;

f2 - вектор потоковых параметров, характеризующих- распределение однозначных потоков трафиков по ветвям и HOST - мзаинзм рабочих систем FBC;

f3 - вектор дисциплин обслуживания заявок з РБС, вклачавв^^ дисциплины обслуживания заявок в PC, ТС и коммуникационных системах, и алгоритмов обмена данными в РВС.

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

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

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

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

топологию зо взаимосвязи структур sSqeshtckik и коьзлуеккзциснеых подсетей. Суть предлагаемого подхода сводится к следунцему: кь "пачаазЕОИ гтале регион, дз» которого создается F2C, с учетом ад-ишастраткЕкЪ-ге-огрг^нчесиого разделения разбивается ка зоны, б каждой иг которых г&даэгся: количество тержгглькн;: стакой,рабочих с истей и координаты кх размещения; ггоордпк^ты вогма^-гкх точек рззмецекия ксшукикадокных центров; -5етеяс1аности потоков, поо-тупгипцс: в сеть от отдельны: источников; производительности рабо-чпх скоте«; коэффициенты тяготения к ресурса.! других зон. 2 зонах •зоздаатся абоя&ктекпе подсети, которые- представляет собой звездообразные структура с одной или дзукя вершками, в которш-: рззые-ярзтея ЦКП. Определение структуры подсети s очередной соке производится при учете поэпцш зернины в предыдущей, соседней зоне и т.д. Последовательно выполняя данную операцга формирования структур абонентских подсетей для всех зон, строится односвяг'анкая {остовная) . меизоноаая подсеть, снязыеззе^л кратчайз52.с! путями вериины звездообразных графов з зонах. При 'зтсы, в качестве исходной выбирается гона, сблзда-згзя болыжм коэффициентом тяготения. На следуив^м этапе определяются все висячи* ьераикы остов-юга графа к строится цикл минимально:: стотз-асти (веса), проходящий через эти зврзаны, т.е. строится топология свтк с козфф»чаок~с;/. связанности но ыеньпе двух (ксвС£),котарля ;; принимается за топология начальной структуры.

В работе задача построения тополога: сДонехтской педоеги сведена к поиску Р - иэднаны графа, т.е. к q п+2 ¡г.

i—i ¿-а

где £,i;j - матраца распределений, в которой

Jl, если верякна х, прикреплена, к вершке лх *= [о, в противном случае, и £,ii«l в случае X; является медианной вернияон к = Э - в противном случае;

Си (С) - стоимость аренды канала (2,3), зависят от тарифа, являщегося функцией от длины канала ^ ;

^jCr.u) - вес j - вершины звездообразного графа ш-зоны, от-рзхащий потоковые характеристики терминальных и рабочих систем .

принимает целочисленное значение, которое зависит от внешнего трафика Г:

,'1 , при г», < Г4 ш\! Ь+-1,пря > ЬЛ^ [_Ь=1,2,Э,...

- интенсивность обслуга танин заявок линии (1,3); п.. - число вершил графа 6П, прикрепляемых к 1-ой возможной медианной точка п,.£

Ь® - общее число вершин графа в т-ой зоне; а - числа возможных медианных точек ( в общем случае Б последнем выражении (ги+1) член суммы 2т отражает характеристики многопродуктовога потока и линии между ЦКП. Задача репается с помощью алгоритмов," основанных на методах сужаащихся окрестностей и случайного поиска парякш пробами. В случаях, когда число вариантов тачек размещения ЦКП невелик мсхво использовать кяасспчес-кие переборные алгоритмы. В диссертации на основе проведения вычислительного эксперимента показана эффективность предложенного подхода, заьапсч£щейсн в уменьшении ззтрат, необходимых для построения межзоновой сети.

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

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

Еыбср оптимальных алгоритмов и параметров звена управления передачей данных 5СОД, рещзсцей проблему помехоустойчивой л сзс-евременксй доставки заданных сбьемов инфсрмэх^яа, з классической постановке опирается на формализованное матзмапгееское списание лпоцэсса передачи информации, акличаощее в качестве 'основных элементов, мсдель взаимодействия сигнала и помех (распределение ссл-

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

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

1.Бвод статистики ошибок реального канала или формирование последовательности ошибок по математической модели канала.

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

3. Имитация процесса обмена информационными блоками (кадра!.®) в реальном масштабе времени при использовании одной из процедур обмена данными.

4.Оценка эффективности исследуемого варианта путем поиска оптимальных параметров рассматриваемой системы.

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

Вычисление статистических результатов моделирования и поиск оптимальных параметров рассматриваемой системы передачи данных (ОВД) производится по следующему алгоритму:

- по заданным исходным материалам определяются параметры моделируемой СЦ Д ;

- для выбранного типа и ряда водов вычисляются значения оптимизируемых параметров, которыми могут быть относительная ск'орость при заданной верности, среднее время доставки сообщении (Ьд) определенного объема информации, вероятностно-временные и другие качественные характеристики системы;

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

Анализ вариантов процедур обмена и защиты от ошибок проводился для значент вероятности ошибки на символ Рош=10~а(а=2гБ)» длин кадров (блоков) п = 2Ь (Ь-4-13), хэмминговых расстояний с1»т=3, 5,7с соответствующая! видами образующих полиномов г(х). На рисЛ приведены зависимости среднего времени доставки сообщения от длины передаваемого блока (кадра) п. Оценка влияния степени группирования ошибок сС на выбор длины кадрз производилась о использованием потока ошибок, полученных с помогцья разработанной модели и программы, генерирующей эти потоки с разными вероятностями ошибок и показателями группирования-На рис.2 приведены зависимости оптимальной длины блока По и среднего времени доставки сообщения Ьд от показателя группирования оэибок с( .

Уровень управления информационным каналом а РВС обеспечивает передачу данных между двумя соседними узлами. Архитектура сети состоит из множества таких подсистем, характеристики которых в основном зависят от состояния физических каналов. Помехи и распределения ошибок в каналах связи, гак правило, могут сильно отличаться друг от друга и вследствие этого,найденные по предложенным коделям,оптимальные параметры передачи данных для конкретного канала будут отличаться от оптимумов для других каналов. С другой стороны, практические соображения вынуждают иметь для сети небольшое число типов серийной аппаратуры с нерегулируемыми параметрами. В связи с этим в работе разработан алгоритм определения искомых параметров звена передачи сообщений в ЕСОД.Алгоритм адро-ЗироЕзн в сети, состоящей из десяти узлов. Сообщения длиной [■=1000 на участках сети передавались блоками фиксированной длины и блоками, соответствующими оптимальным длинам.На рис.3 приведены экспериментальные кривые распределения вероятности своевременной доставки сообщения от длины кадра при различных интенсивностях поступлении сообщений Т1-

ал

0.6-

Р =10

{=<000 В = 24005

е.+ %

игл.

511

255

{£?■ 63

Рис.1 Зависимости Ц от длины кадра при различных Рвш

«

83 127 253 51) ЮгЗ Г1

гбш

'5-10

0.1

О.Е

ОЛ

О,*

Ой

0.7

5

4.5.

б)

'5-10

Рис.2 эаоиса-эсойти оппги-хальнси длины (а) и ср. Ъре-хепи достатки (5) от показателе. группирования

ВД

и

3-4

0.5

0.6 С?.

Поиск методов количественного описания и анализа сетей может производиться на основе строгого рассмотрения математических Моделей стохастических процессов в сетях. Разумеется, полученные этими методами результаты полезны для априорных оценок сети и позволяют правильно ориентироваться при разработке других моделей с цельС/ получения более точных данных. В диссертации разработана аналитическая модель, которая,базируясь на ограничения относительно процессов массового обслуживания,позволяет достаточно корректно оценить искомые характеристики сети передачи дзнньсс. В моделзг экспериментальные распределения вероятности доставки блоков в каналах передачи данных с помехами аппроксимируются последовательно-параллельно этапным распределением Эрланга .На основе преобразовать Лапласа-Стильтьеса и уравнений Полячека-Хинчина получены конечные выражения и покапано,что рассмотрение сети на основе схемы, незначительно отличающейся от классической М/М/1 может привести к значительны;-! расхождениям. Исходя из этого делается вывод о целесообразности исследования сетей на основе методов . имитационного моделирования или с использованием более сложных распределе-

на} {№) {155} {П>

Рнс.З. Зависимости вероятности своевременной доставки

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

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

Пусть задана многоузловая распределенная вычислительная сеть

J_I

!_L Л_L

1,5-активные Z-пассивные

Рис. 4 Фрагмент хкогоулжо&аи РВС (s) и представление ее топологии t i и de д&ух типоЪ уъзюЪ (6)

с фиксированной топологией. На рис.4а покззан фрагмент физической структуры РВС.Данный фрагмент сети состоит из трех коммуникационных систем (КС) ( заштрихованный кружок), двух рабочих систем (РС) ( прямоугольники А и Д ) и шести терминальных.систем (ТС) (прямоугольники Е.Ро.Вх.Вг.Г.Е). Функции систем: РС - представле^-кие информационных ресурсов.хранение массивов данных, переработка и попек информации; • КС - управление передачей информации между РС, ТС и т.п. (маршрутизация, коммутация к управление потоком); ТС - потребление информационных ресурсов: управление работой терминалов, подготовка заданий, сопряжение с технологическими процессами.

Представим физическую структуру рассмотренной сети в упрощенном виде, а именно, узел к которому подключены только ТС назовем "пассивным" узлом (ПЛ, а узел к которому помимо ТС подключены и РС - "активным" узлом (АУ). Тогда сеть может быть представлена а виде интегрированных фрагментов (комплексов) (рис.46), т.е. с топологией, содержащей двз типа узлов АУ и ПУ. Рассмотрим характеристики суммарного входного (внешнего) трафика г » Т1+Г2+ТЗ , представляющего собой поток разнородных сообщений -совокупность трафиков трех видов: и - суммарный внешний трафик, состоящий из сообщений, передаваемых от истоков к стокзм (источниками - адресатам) без использования вычислительных средств сети, т.е. без обработки на Е2М сети. Назовем п транзитным трафиком; (гг+тз)" суммарный внешний трафик, состоящий из сообщений, передаваемых от истоков к стокзм с использованием вычислительных средств сети, т.е. с промежуточной обработкой на ЭВМ сети. Назовем гЧ" вычислительным трафиком, который может быть интерпретирован как суша двух трафикав

гЧ-тг+гз ,

где Г2 " суммарный внешний трафик, направляемый на ближайшие "активные" узлы, для обработки на их вычислительных средствах. Назовем Т2~ "вычислительным внешним" трафиком;

тз - суммарный внутренний трафик, возвращаемый в сеть после обработки на активных узлах и направляемый своим стокам . Назовем тз ~ "вычислительным внутренним" трафиком.

Формализация задачи определения оптимальной- процедуры марш-

рутизацни и алгоритма распределения потоков, минимизирующее среднее время пребывания сообщений в сети заключается в следующем. ö ; Представим сеть в- виде неориентированного графа G(M,N) с множеством верпан М = <1,2,... ,гг.>, разбитым на два подмножества Mi « -{l,2,...,mi> я Мг = -Cmi+l,..(Mi,Uz £ !.!) и множеством ребер N - -С (i, j)}. Каждому ребру графа соответствует Fj0(t) -функция распределения вероятностей передачи сообщения по каналу. Для суммарного входного трафика г, его соответствующие интенсив,-ности определяется как:

ы и и м, и, и

vi» - s riia . тг= - Еxza , тз= Е Sr3jl

t-1 J-l 1-1 ¿-1 J-l i-r

Процедура маршрутизации определяется матрицей маршрутных переменных

P-riPtK)ij|b

где - вероятность отправки сообщения иг узла i в у г ел к по

маршруту (i,j). Очевидно, ЕРц «* 1, Р(К)1}>О. Тогда средняя интенсивность полного потока через i-й узел, адресованный j-му углу, будет равна

м (3)

»ii - Гю *■ Е atziPzj , г-1

ги = пи + таи + гзи'г ,

1 - для "активных" узлов (з) г 0 - для "пассивных" углах • где PZi - маршрутная переменная (матрица тяготения), определяющая долю потока Xzt • отправляемого из узла г в узел i на маршруте (1,1).

Средняя интенсивность канального потока по ребру (i,k) равна Ii) Ы (4) (j)

- «ijPifc - (Tij + EstZ1PZ1 )Plk , ш Z_J

где Pin - маршрутная переменная на канале (i,k) маршрута (i,j). Средняя интенсивность потока на входе "активного" угла равна .>

«i - T2j + £ T2iPij •

lr-1

Если считать,что каналы связи и узлы рассматриваемой сети с фиксированной топологией абсолютно надежны и помехоустойчивы, га вход сети поступает стационарнай поток с интенсивность» т = п + Т2 + тз с экспоненциальным распределением моментов поступления сообщений, и если (j=l,Ui) - интенсивность обслуживания в "активных" уздах, то суммарное среднее время пребывания заявки з сети будет равняться

Mi Bi

Т = 1/г S CXij/ifu- \ц) + 1/Г2 2 Е Sjb/(Hib- 2зЬ), (2) t, i&M J-l b-1

где fij - интенсивность обслуживания заявок в (i,j) ребре;

Bj - число HOST - машин в j-м "активном" узле. ¡Задача распределения потоков, решаемзя по разработанной модели (2), представлящая собой выпуклую функцию двух аргументов и £]Ь формулируется в следующем виде: минимизировать выпуклую функции (2) при линейных ограничениях:

f Xij >0; Cjb >0; (ц>Хц ; Hjb >s,b I M (k) M (k)

- E ХЦ + Tik - £ »it (3)

; i-i i-t

Tik = Tlik + T2ik + T3tk Titk, T2ik, T3tk > 0 •

Решение данной задачи в предположении полной стационарности исследуемой системы основывается на теореме: выпуклая функция Ti3-миниыизируется мультгаготокоы Л ={ Хкп> в том и только а том случае, если любая нитка данного мультипотокз есть крзтчайиий. путь в иетрике ||hij||, i,3»l,2,...,N, т.е.

ht, =d7/dxu =fu/r(fii-Aii)z • hj -dT/detj -

Значения hi5, h3 характеризуют степень изменения целевой

- го -

функции Т в результате приращения потока в (1,3) и РС.

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

(в) (в) (в) (г» (г) (г) 2(в'г) - (^1 , \г ....... £1 » «2 ------ бм, ),

где 1-я компонента XIСе) представляет собой полный поток по 1-му каналу на е -й итерации первого этапа (при £}(г,*соп51); 3-я компонента е*(г) представляет собой полный входной поток 3-го "активного" узла на г-й итерации второго этапа. Значения компонент пересчитываштся вз каждой итерации второго этапа. Задача решается,исходя йэ начального вектора г10'0*.являющегося реализуемым, т.е. fi и г,(0'0><и Начальные значения е$10'0) , \\ °1 определяются следующем образом* по заданная весам ребер (каналов) ьычисляшоя кратчайшие пути между узлами. В диссертации разработан оригинальный алгоритм, определения кратчайших путей на графе , работа которого сводится к следующему: заданный граф 6(А,В}, где А* [а*, Зй, ..., а^.З - множество вершин (узлов), В-ЕЬа, Ь2,...,Ьг»1 - множество ребер (кзвзлав), представляется в виде радов,харахтеризуюк^к номера исходящих и входящих вера:», длины медду исходящими и входящаш веражнзш, и ряда,фиксирующего в процессе- поиска текущее состояние к -дуги при вычислении очередного кратчайшего пути грзфз("перекшчзтель")„ Суть поиска заключается в последовательном переводе состояний переключателя из состояния "выключено"- в "включено" при условии, если рассматриваемая дуга ранее ке участвовала в построении пути между узлами. Текущая длина сравнивается с длиной предыдущего варианта и принимается решение заложить результаты текущего варианта или .оставить прежние. В зависшости от решения соответствующие с позиции "переключателя" переводятся в состояние "выключено". Вычисление следующего варианта начинается с возвращения на шаг назад с 3 - узла на 3-1 по ранее определенному пути, (т.е. к предыдущему узлу) и поиска в нем невклязченного переключателя. В случае наличия выключенного переключателя осуществляется построение пути в этой направлении.а в отсутствии- осуществляется шаг назад и т.д.

По вычисленным кратчайшим путям, соглазно матрице тяготе-

ния.напрзвляюгся заявки (нитки потоков) соответствующих внешних трафиков П,Т2»ТЗ на соответствующие "активные" и "пассивнее" узлы. В результате формируются многопродуктовые потоки \it г, . Если они реализуемы, то принимаются га начальные вектора, если не реализуемы - вклячается алгоритм определения реализуемого вектора ' потоков.

Минимизация Т (Xí.Sj) производится на основе модернизированного алгоритма о девиации потоков , суть которого закдачаетсл в следующем:

пусть yíe»r)*z (Xi,£j)(е'г) - реализуемые потоки по ранее определенным кратчайшим путям; вычисляя для каждого i,j значения hi и hj определяем новые кратчайшие пути между углами в метрике ht и h, и формируем потоки по этим кратчайшим путям, т.е. формируем мультипоток Г) =v(Xt, еj )te*rî ; для калдай нитки потоков ГаЬ между парой узлов (а),(Ь) проделаем следующие операции:

1) образуем поток g из потока путем отклонения всего (или части) потока ГаЬ от его пути в потоке "v" к кратчайшему пути в метрике hi, h3;

2) если -реализуемый поток и выполняется неравенство Te<Tv, тогдз "g- = V , иначе осуществляется переход к следующему шагу;

О) если не просмотрены все нитки потоков Таь, то задаются следувщие Гаь и осуществляется переход в 1); если после очередного шага потоки по кратчайшим путям равны потокам по ранее опреде-■ ленным путям, то дальнейшее улучшение распределения потоков невозможно, т.е. g= Z (\i,Sj)íe'n , иначе v=gi! переход к началу алгоритма; аналогичные операции выполняются для трафика активных узлов - s, только при переброске ниток потоков из одного АУ в другое на г-м шаге перес^лтыватся потоки в соответствующее путях. В диссертации в целях рационального распределения потоков на уровне активных.узлов разработан алгоритм распределения трафика с использованием метода случайного поиска с непрерывным покоординатным обучением.

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

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

Представим сеть в виде графа, в котором заданы множество всех входящих потоков:

{ ® > - { Ti.Ii.Hi>. ' (4)

где чп - величина потока;

Н1 - номера вершин истока и стока 1 - потока; N - максимальное число потоков.

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

Для каждого потока Ф заданы п>{1) маршрутов из Ь в Н^ не содержащие циклов. Пусть - множество номеров ребер, входящих в маршрут 1 для входного потока к .Тогдз Ь0т(1.3) - есть расстояние между маршрутами 1 и з, выраженное в количестве различные ребер, входящих в оба маршрута, т.е.

(К)

1т (1.3) + 141 <Ю1 " 21Ч1СК5

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

x - { xi,х2,...,ху у,

где х^ - порядковый номер маршрута для входного потока ,

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

N (К)

КртСа.Ь) - Е Ьр» (1,3 ) , к-1

-где (1,3) - номера маршрутов для потока к в точках а и Ь соответственно.

Для Еда соблюдается свойства , присущие метрике ,т.е.

Нри>0; Крм(а,Ь) * Rpmib.3); Rpm « О,если а»Ь;

Kpraia.b) С Крт(а,с) + Р.рт(с,Ь) , a,b,c X . Работа алгоритма начинается с определения максимального радиуса сферы пространства параметров, внутри которой осуществляется дальнейший поиск. Sa центр сферы прингтется вариант набора маршрутов Xj, вычисленный при условии, что веса ребер данного набора ызршрутов равны их пропускным способностям.Эа макс тиль кии радиус ¡чжгтах принимается максимальное расстояние ме.-вду рассмотренными париантэ/л с исходным, т.е. Rom так - Rpm(xo,xm). Поиск внутри радиуса реализуется следующим образом .

,1. Выбирается вариант х», для которого выполняется условие !j '

Rom > ELpm^Ü,;}) K-l

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

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

Т<» -ET,j<w + ЕГЦ(»

1.4 1* 3 ^

Число испытании гзутра данного радиуса производится до тех, пор пока разность значений не станет меньшей какого-то 3 Т.т.е. (Tj.t * Т(i+ij) ( & Т.Величина Д.Т может определятся находя из условия, характеризующего превышение эффекта от уточнения над стоимостью самого процесса уточнения .

4. Последнее значение Ijtkl считается центром новой сферы, радиус для которой (и для всех последующих) выбирается на основании ряда чисел Фибоначчи. После просмотра всех рзднусоз выбирается выриант xj, обеспечивший min ~ГЕСЮ.

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

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

М W, Bj и

С » Е Ci + Е Е Cjb + Е Chít) . (5) 1-1 J-1 Ь-1 h-1

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

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

Ch(t) - стоимостные потери h - пользователя из-гз несвоевременного обслуживания его заявок в сети за рассматриваемый период времени, (Ch(t) >0).

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

Аппробация алгоритмов производилась для 20-угловой сбаланси- • ровзнной,полнодоступной вычислительной сети,содержащей ? АУ. Нз рис.5,5,7 приведены некоторые результаты, вычислительного эксперимента из которых видно, что системное рассмотрение процедур управления разнотипными потоками позволяет значительно улучшить значение целевой функции в сравнешш- с традиционными метода!,®, основанными на раздельном рассмотрении распределения потоков по кратчайшим путям.

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

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

Известно множество интересных методов и алгоритмов обслужи-

гплТ я-

\J~l-ccnst. Хг'оаг

2,2 '-у, «Ли уж-сояз1

0.35 р.1 р

Рис.5 Зависимости -хини-жума среднего "бремени пребывании заявок тб сети от ее загруженности

¿25 О50 чта £

Рис. 6 ¿ависихости потерь полаоЯсгтелеи от загруженнести сети при различных характеристиках входного трафика

&С. <1

в.

з, б »{Га*.-уа=сгю«£;

^в ел р

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

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

В главе рассматриваются некоторые алгоритмы обслуживания сообщений (пакетов), учитывающие эти ситуации.

Пусть характер изменения функции потерь из-за задержки сообщений (пакетов) представлена в виде

ГСо Л С С(1)« <с(1) Лг^аь (6) 1Ст ,ь> Ьг .

Тогда оптимиззцшэаная задача сводится к отысканию алгоритма обслуживания , минимизирующего выражение

V VI

ЕСи , (7) 1-1 1-1

где V - количество потоков с соответствующими штрзфншп функциями 01(Ь);

- количество поступивших требований 1 - потокз с интенсивностью

выражение (6) кнтерпретируется езедугщза образом: поступившее з- требование 1- потока находится в системе с минимальным (нулевым) ЕТрафом Сси лшь ограниченное время ^ ,' после чего приоритет его обслуживания растет пропорционально росту потерь и к моменту времени достигает своего максимума. После истечения времени Ьг ценность сообщения теряется и отпадает необходимость его дальнейшего обслуживания.

Потоки с такими характеристиками относятся к потокам с динамическими приоритетами и ограниченным временем ожидания.Точное

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

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

Б диссертации приводятся результаты моделирования при использовании вышеописанных дисциплин обслуживания сообщений и их Фрагментов з соответствующих компонентах РВС, которые показывают, что применение предложенных алгоритмов позволяет з области средних нагрузок (рКЗ.З - 0.6) уменьшить суммарные потери на 6 - 12Х, з сравнении с обычной дисциплиной Р1ГО0

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

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

-ве-

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

выбирается вершина с ксг> 2 и в ней определяется наименее загруженное ребро, т.е. ребро у которого да = тах (ни -Дла) ; проверяется условие связности при удалении данного ребра и при его выполнении осуществляется операция "удаление ребра";

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

Асг « с™ } - { » <е ,

где £ > О - заданное" малое положительное число.

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

программного комплекса . В диссертации приводится описание основ построения системы автоматизированного проектирования PRC. На рис.8 показаны некоторые результаты вычислительного эксперимента для случая, когда регион представлен 15 зонами.

ЗАКЛЮЧЕНИЕ

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

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

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

З.Нперзые разработан эффективны:! алгоритм оптимизации РВС,основанный нз идеологзш и технологии создания сложных систем,и поэ-воляпцип проектировать многоузловые сети ЭВМ при совместном учете характеристик топологической структуры, потоковых параметров н параметров дисциплин обслуживания сообщений в компонентах и параметров алгоритма обмена данными в ЕСОд'с разнотипными физическими каналами связи сети общего пользования;

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

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

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

<50'

J5=0.2 J>"=0 .<

350 450 550 Щ

Рис.в Зависимости суммарных приогденниа затрат и потерь лалнааателеи от тоихчсти -затрат на создание Р8С при различных £ и требований на Ъреяя aoz.fцжиоаниа f*»}«/ lt,)ij*{tt} I?«1'

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

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

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

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

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

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

Ic-r-'THc, ; ход? исследования, били решены сгедугез» задачи:

1) разработан алгоритм и реализована зз SSM прэграьаз моделирования источника ошибок с разными значениям: вероятности ошиб-ъг, показателя группирования а генерируемо;: гослгдоззтельности

ОЕйбСК;

2)разработан оригинальный алгоритм декодирования кодового вектора циклического кода, позволяющий значительно сократить время декодирования и рационально использовать память изшккы; :

3) р^арзботея метод и реализована на SSM программ Е$и#сдения кратчшштл пути"! нз грзфе, чккойакньдг кз использовании переключателей. i

Результаты исследований были использованы при проектировании сквозной автоматизированной системы учета и движения трудовых ресурсов /система "Занятость"/, создании аппаратуры передачи данных на микропроцессорной основе по КВ-каналам, проектировании структуры первой очереди РВПС "Средняя Азия" Академсети и разработке технического задания на создание республиканской сети передачи данных.

В приложении излагаются вопросы практического применения разработанных моделей и алгоритмов синтеза и анализа сетей ЭВМ при создании автоматизированной система "Занятость", приводятся акты о внедрении результатов и справки о сдаче программных средств в ведомственный фонд алгоритмов и программ Академии Наук Республики Узбекистан.

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

1. Валиев I.A..Нишанбаев Т. К оптимизации параметров системы с решающей обратной связью." Вопросы кибернетики" ИК с ВЦ АН УзССР, вып.71,.Ташкент, 1974, C.19Q-198 (Соискателем разработан алгоритм оптимизационной-модели)... .'.

2. Валиев Т.Д..Нишанбаев Т. Методика определения параметров системы передач!! данйых с решающей обратной связью путем моделирования на 3BU. В тр. YI - Всесоюзной конференции по теории кодирования и передачи информации. Москва - Томск, 1975, С. 25-30 (Соискателем разработана модель процессов кодирования., декодирования и процедур обмена данными).

3. Нишанбаев Т. Оптимизация системы с решающей обратной связью путем моделирования на ЭВМ. "Вопросы кибернетики", ИК с ЕЦ АН УзССР, вып.75, Ташкент, 1975,С. 143-148

4. Валйев Т.А. .Лоссккй И.О..Нишанбаев Т. Оценка эффективности использования методики раздельного дублирования с учетом весов разрядов в системах с РОС. "Вопросы кибернетики" ИК с ВЦ АН УзССР,вып.73,Ташкент, 1974, С.177-190 ( Соискателей получено выражение для расчета вероятности ошибки).

5. Валиев Т.А.»Нишанбаев Т. К определению оптимальных параметров систем передачи данных в сетях. "Вопросы кибернетики" Ж с ВЦ АН Уз ССР, Ташкент, вып.84, 1976, С. 114-119. ( Соискателем разработан алгоритм моделирования).

5. Нишанбаев Т. Моделирование потока ошибок с разными пока-

вателями группирования."Вопросы кибернетики", ИК с ВЦ АН УзССР, вып.77, Тапкент,1975, С.151-157.

7. Валиев Т.А..Нивэнбаев Т..Раджзбоз С.С. К проблеме комплексной оптимизации параметров сигнала и сообщения в СПД. "Известил" АН УзССР, серия технических наук, М 5, Ташкент, 1982, С.7-10 (Соискателем разработан алгоритм оптимизации).

8. Валкев Т.А..Нишанбаев Т., Мусаев М.Т. Алгоритм управления потоками сообщений с нелинейной характеристикой. В тр. Всесоюзной конференции "Техническое и программное обеспечение передачи и телеобработки данных в ИВС и АСУ". Рязань,1985 С.36-38 (Соискателем разработан алгоритм управления обслуживанием потоков сообщений).

• 9. Лосскпй И.О.„Нишанбаев Т. Исследование на ЗЕМ методики раздельного дублирования с учетом весов разрядов в системах передачи информации с реиэощей обратной связью. "Вопросы кибернетики" ИК с ВЦ АН УзССР,Ташкент, вып.74, 1974, С. 193-205 (Соискателем разработан алгоритм моделирования комбинированной системы).

10. Валиев I.A..Нишанбаев Т.,Умаров В.К, Оценка эффективности систем передачи данных с обратной связью в дуплексном режиме на ЭВМ. В тр.УП- Всесоюзной конференции по теории кодирования и передачи информации, ч. IY, Москва-Вильнюс.1979, 0.46-Ь'З (Соискателем разработаны алгоритм моделирования и программа).

11. Валиев Т.А., Низанбаев Т.,Раджа5ов С.С. Определение оптимальных параметров решающих устройств в СПД. В тр. IY-Бсесоюз-ной пк.-семинаре по вычислительным сетям. Часть 3,М-Ташкент. 1979. С. 12-15 ( Соискателем разработана модедО фунгазганпрозания решающих устройств СПа). 5

iE. Нишанбаев Т. Методика определения оптимальных параметров систем передачи данных с решающей обратной сзязьгигутем моделирования на ЭШ. Авт. кзнд.дисс., Таакент,197Б, 32 стр.

13. Нказнбаев Т. Определение йа ЭШ влияния' параметров. канала на оптимальную длину кодовой комбинации в системах с переспросом. "Вопросы кибернетики" Ж с ВЦ АН УзССР, вып. 86, Ташкент, 1976, С.90-97.

14. Валиев Т.А. .Нишайбаев Т..Рэджабов С.С. Моделирование помех для оптимизации параметров сигнала и сообщений. "Вопросы кибернетики", Ж с ВЦ АН УэССР, Ташкент,вып.104, 1979, С.12-16 (Соискателем разработан алгоритм моделирования помех ).

15. Валиев Г.А.,Кншзнбзев Т., Лосский И.О. Оптимизация информационно - вычислительных систем методами имитационного моделирования на ЭВМ. Ташкент, "ФАН", 1991, 157 стр. ( Соискателю принадлежат материалы глав 3,4,5).

16. Лоссгеш И.О., Н;шанбаев Т. Эффективность метода раздельного дублирования по статистике ошибок реального канала. "Вопросы кибернетики" Ж с ВЦ АН Уз ССР, выл .'92, Ташкент, 197?, С. 118-123 { Соискателем разработан алгоритм моделирования ).

17. Нкззкбгез Т. К проблеме моделирования источник ошибок на ЭВМ. "Вопросы кибернетики", ИК с ВЦ АН УзССР, вып.102, Ташкент, 197S, С.123-140.

18. Кишанбзев Т. К вопросу моделирования дуплексной адресной системы перс-дач;:. "Еопроса кибернетик!:" ИК с ВЦ АН УзССР, Еып.110, Ташкент, 1980, С.112-118.

19. Лсссжп: И. 0. .Нипанбаез Т. Анализ результатов моделирования на ЭВМ СПД с дифференцированной защитой от ошибок. "Вопросы кибернетики", ИК с ВЦ АН УзССР, вып.114. Ташкент, 1380, С.115-120 v Соискателю принадлежит разработка алгоритме и программы моделирования) .

20. Лосский И.О. .Нгашбаев Т. .Методика опенки погрешности даровой информации при передаче по каналам с памятью. "Вопросы каберне-тики", ИК с ВЦ АН УэССР, вып. 117, Ташкент, 1S82, С. 133-127 ( Соискателю принадлежит разработка модели передачи цифровой информации по каналам с памятью).

21. Ниианбаев Т. Анализ временных характеристик сетей передачи данных с виртуальными каналами. В тр. У- Всесоюзной конференция "Вычислительные сети коммутации пакетов", KGMTÎAK - 87, Рига, том 1,1937,0.172-175.

22. Нишанбзев Т., Лосский И.О..Убайдуллаев O.P. Учет надежности к помехоустойчивости в сетевых модемах. В тр. десятой Всесоюзной шк.-семинаре по вычислительным сетям, М. ,Г385, С.36-41 (Соискателем разработана математическая модель помех).

23. Кишанбзев Т. Анализ временных характеристик сетей передачи дачных с невдеалышми физичесгаа-и каналами. "Вопросы кибернетики"'ИК с ВЦ АН УзССР, ныл.123,Ташкент,1S85,С.43-47.

24. Ниианбаав Т. К задаче оптимизации времени пребывания га-явок г сетях ЭВМ. "Известия " АН УгССР, серая технических наук, И

1983, С.3-5.

25. Низанба-53 Т. Оргзшззцпя приоритетного обслуживания заявок яа узлах сети пакетной гамаутацик. В тр. Республиканской конференции "Методы управления технической диагностикой и восстановлением работоспособности элементов се. ;й оалзи. Часть П, Тзсквнт, 1"ЭЭ, С.4-5.

25. Кетакбаез Т.. Лзсский H.G. Алгоритм сктамааяогс распределила потоков в сетях 3S.U с учетом производительности исмпьвте-роз. Б тр.Всесоюзной научно-технической конференции " Проблема создания к использования отраслегчх цкформакнонно-днспетчерскгк систем на основе компьютеризации и перспективных средств связи". "Радио и связь", М., 1S8£, С. 59-101 (Соискателя пркчадле.чат постановка задачи и разработка алгоритма)

2?. Кпзакбсев Т., Лосскпй Tl.Q. К анализу с*тей обмена данными с фкгхческима кокала:;:, "йзвестга" «К УгССР, серия технических наук , Л 2. 1589, С. 14-36, (Соискагегэ принадлежат постановка задачи п разработка иатеиаткчесиой мод мл).

2°. йсчкбаев Т. Субовткмаганкй метсд управления распределенном тт'тсгс-з в сетях SSM при случайном законе обслуживания их в лере-гч;* гаяных. й тр. X! ¡-Всессазнзго со:-дания по проб...... ."т.ттлен^л. Тезисы лск-тад-., 15'3'S. С.

;?. т. ,Досская И.О. У.ггод построения сягпмагьнах

: -:г.Г"-*• .т-н--:---: в:-.*гтсглт(.-льккх сетей, р тр. Международной научной '-генной к Лз: рзлио ССС? ..¿¿¡окая сессия", М. ,1550 "т--.:т -V пс .rsBxeas галзчЕ неслезовгл-ж--4,.

" Т. f/.етсд спглязажя т«-рргторк&зных растреде-

--~:;,т.-пгге.-:гнах тетей с згронэтекн-а» ресурсами. 2 тр. .'-.-г.'. .л:.- .'емнноре пт сетям. 4.1, Мсок-

TS?C, 0.110-115.

PI. Нкганбзеа Т. Метод построения X - связанной топологии Г.ат пргд:• ;еняой вычислительной сети. 3 тр.УЬВсесоазной пк.-семинар? но проблемам управления на сетях и узлах езязи, под рук. проф. Р.Г.Лзгеренз, Москва-Эзеангород, 1SS0, С.69-72.

32. Киаалбаев Т..Лосский И.О., Худаиберганоз R.K. Алгоритм оптимального распределения потоков з сетях SSM с учетом производительности компьютеров. Алгоритмы и информационные исследования,

- SG -

моделирование и проектирование (сб.научных трудов), зьш.72, Науч-но-изд. совет АН УзССР, 1990, С. 137-147 (Соискателем поставлена задача исследования и состазлен алгоритм ).

33. Нишнбаев Т. .Мелибзева Г. Определение оптимальных параметров звена управления информационным каналов виртуального соединения вычислительной сети. Алгоритмы. Система автоматизации управления организационно-техническими комплексам. Ташкент, 1991,вып.74,С.34-40.

34. Нстанбаев Т. Синтез структуры распределенных сетей ЭВМ на основе методологии системной техника-экономической оптимизации информационных систем. "Вопросы кибернетики", ИК с ЕЦ НПО "Кибернетика" АН УзССР, вып.144.Ташкент, 1991, С. 138-145.

35. Чугреев O.G. .Ншанбаев Т. .Абдурахманов Ф.П. Моделирование регулируемого маркерного доступа в интегральных локальных сетях. "Вопросы кибернетики", вып.143, Ташкент,1990, С.64-78. fСоискателем произведен.анализ результатов модели).

26. Якубова М.З., Нишанбаез Т. Анализ моделей источника ошибок Попозз-Турина и уточненной путем моделирования ошибок в телефонных канатах. "Вопросы кибернетики",- ИК с ВЦ АН УзССР, вып.62, Ташкент, 1973, С. 95-106 (Соискателем определены параметры модели канала)

37. Еалнев Т.А., Кадыров У.С.,Нишанбаев Т. Исследование целесообразности повышения помехоустойчивости высокоскоростных модемов при передаче данных по КБ-каналам. Отчет ИК с ВЦ, 19S0, 82 стр.(Соискателем составлены алгоритмы моделирования систем с ОС)

38. Нишанбаев Т. Исследование эффективности системы.с решающей обратной связью в сочетании с методом посимвольного накопления. "Вопросы кибернетики", ИК с ВЦ АН УзССР,вып.'бЭ, 1976, С Л17-125.

39. Нишанбаев Т. Алгоритм распределения трафика по вычислительным средствам распределенной сети ЭВМ, "Вопроси кибернетики", вып.142, Ташкент, 1990, С.34-39.

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

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

Дпссертацкяда техшж-ж^гисодзш концеццкяга ассслакиб, тарьрк, структурага зга булган дисоблаш тармоздаринкнг архктектурасини сзмараго згриантларини тазлзш за тигкмлп синтез килиига янгича ёндосяз такллф этилгая. Опиагаллагткрпз мезони !\нлиб тарыо^ни курис учун кетган харзхатлзр за уни гзкомз^ллгЕтирзцмзгзклкги на-тижаскда кстеьмолчи зиенлари йигиндискни ыпнкмаллзетиркз г^збул гршткган.

Birp математик маезда допрасида барча муаммолар комплексини еч:ш: ута мураккзблззги туфайли илмий зшда масалани бос?рга,'.а-босьрг-1 ечиз тартпби кабул кплинган.Ву усул кзтта улчамга зга булган ма-салан»: бпр'неча кичик увязали мгоалздарга ажратз'.б, упарки мзьлум Сир кетма-кетликда ечип юдсонини беради.^ззвд зтклгаа услубга ен-дозган хелда диссертацияяянг .тегнлли бобларвда адохндз х^здз бутун тармст; учун аазкданзётган парадетрларкп здймзтлзркни излал злгср;™л.'лзри,усулл^зи за моделлари нратилггз.

Мзсзлзни ечип абонентлзр за коммуникацией тзрмоклзрнпкг тополог;?: структурасини тузил билан боплзазди.У ¡у/йидагзг-сз тзезпрлз-кади:г,ис0йл£л: тзрмоги барпо этилаётг^ ?;удуд бир кочтз мннтака-ларгз ахрас::,-гди.Мингзугалзрдз абонент хпеоблзл тармз?:: ярстилз-ди.Ву мзезла граф кззаргасинилг F- медпаняни пглаг: мзеалзеи зео-сигз ечшггя. Кейингп мянта,$здагк тоиологиееп аазаугргт , елдонги мкнгзкалзги Р-- медизканинг зззиятиеи хнеобга олгзн хелда амзлга опирпзади. Абонент тармок структураларини мзьлуц бир тарп:5дз, кетмз-кет пзгаиззтарш натиласида коммуникацией тармо^нинг бир борлачли топологпяси курилади.У энг îyjci-^з йуллар билан влдуз ку-риниддзги графлзрнинг чу^у-тарини боглазда.Боглззгич минтаз^з си-фатида тортилззз коэффициента к?тта булган шгата^а тзнлзб олина-дк.Сукгра негизли графнинг барча осилкб ;-;рлган 4ynjçmap» ата-ущ-нади ва улар "кичкк зззнли цикл"адгоритми ёрдзкида б1гр-бкрлари билан улзлзди. Катижзда коммуникацией тзрмогаинг богли^лиги икки-

дан кам булмзган -опологияси тузЕладн.йшда хкссблзп эксперимент« асссидз бу услубзвнг самарадоряиги курсатилгал.

Тузилгзз-з топологзхядз ^аналязонинг уткззиззз !д С СО к П Л ТIП-131 ЗНИКг лаш.мзрзрутлаа вз тгсзс! трафиклзрш! (якш абокентлзршнг ахборЬт-ларинзг) коммуникзцкон тар-ик ор.нзли терылнзл тизимлар уртасидз вз терминал тнзпмлар бплзн ззсзчз: тизпмл&р уртзсидз уззтилзднгак orça*-лзрга булзнизпнп гугаобга оягак г.олда онимларкинг опгс-иал тзирта-тиен ашк-ззщ иэсзгалзри еч^лади.Вутун тармок ôjinrea узаип тизим-ларишшг парамэтрларн ва алгоритылари реал каналлардаги хатодкк-лар огаыини ЗХ>4гз кззритиб.жарзёкларни имитация галет fr/ли билан анякзавади. Тармокда тазабларнинг уртача булиш вактиаи миннмаслаа-тирувчп алгсрпт:,: ез усул ¡слаб чикилган.Тзрмокнинг ипчи тизнмлари уртзсида ;-;;:соблаа тапк?1 трафикиаинг такркмлаз алгоритмы такпиф з^шинган.Еу алгорлтмлар комб;п:Зтор!5ка, грзфда. знг "гупсз>а зг/лазлрнз' тошс, тасодз:ф:ш пзлзнип ва имитзцнон моделла-пгирип: усулларидан фойдэланган халдз тузилган.

2а!',т давомкда приоритет» узгарувчи талзблзр oîç-Mirra тзрмоз компокектларнда хизмат курсзтззп учук иахсус алгоритмлгр иелаб чн-цилган, уларникг самзрэдор,чигзг ЭХМдз мэделязатирзс: кули бклан курсатилган.

Нпш&б чщг'.гзг. моделлзр 'га алгоритмлар асоскда тзрмок стате-гзшпзг • комплекс алгоритма тузялгак.унда нзланяетгзн ТХТ струкгу-расглш топил техиолсгг.ясп ^/рсатилгзн.Алгоритмдз вазиятга кзраб "едрр&л кири73й2", "inr-în тиэпшинг кушилчз ыахсулдорлпгинп кирк-тшг'У'амалга олприладиггн оууаяи издан", "гаррани авдб tseesb" проц?дуралзри игааталади ва тармог^пш? отрукхурасз KQiasyHicts^H вз кег-:и тигп.'.Щгрдз талабларга хкзмзт курсатиа ищраёнинк модоллзе-тиргл йуак бизаа анга^анзди. Диссертацняда талримловчи хисоблап: тар;.:01¥1арини лошзхзлзггни автомзтлаатирш прквцтлзрк кедтиркдгзн.

Иловада кшлаб чикилгая алгоритм вз мод&аларнинг аызди1>тда,яг-ни "Занятость" автоматлалггкрплган икксрмзцион-:;лссбдащ тигимки тузипдз кшлагзшяпзгяинг нзтикаларк кэятирклган. Шунинглек тадкирт нагяхагарлодг жорга": зтшшшк ту;>ригидагп расмзш хугазглар вз дзс-турпй восятзлйрни Республика Сзклар Академиасининг фондига тогиа-рилганлют: тугриспдзгн мзгл\а:отлзр келткрилггп.

Annotation

It was suggested the new approach to systematical synthesis and choice of effective variants computing- network distributed structural architecture based on techical-economical conseption of informational systems optimization.

Because of the complexity all the comprehensive problem solution on the base of single mathematical problem,it was accepted stagery procedure solution allowing to transféré from the problems of a large volume to the cortsequency of small sized problems.

It was suggested single criteria to all networks and uie solution of separate subpromlems as the netvork in the whole.

The problem solution begins with topologic structure bclding as a customers and communication subnetwork and it can lead to the following! region for what bomputing net is built 3nd divided Into sones what customers subnetwork is created in.Subnetwork topology building leads to the problem of search P-median graphes subnetworks topology definition in the next zone is existed taking into account F-tnedian position at the next zones.Consequently executing the procedure of the structure formation of customers subnetwork is built single-communication subnetwork connecting the summits of star form graphes.One can choose the sourse of the zone possessing with a large number of coefficient of gravitation. Further we candifine suspended summits of the graphe, body while connecting them by "the cycle of the minimal weigh" is built the network of the topology not less than two.It was shown the effeciency of given approach based on computer experiments.

The problems of throughput abilities of channels (sh) routhing intergraphics flows distribution taking into account their crushing into message stream served in computing systems and in given systems between terminals through communication subnetwork.There has been developed optimization models of data exchange what is si lowing1 the imitation during' the data exchange process in output of real streams of the error what can define the al gorythms aid paramétrés transferencesystem on the whole in network.

Have been developed al gorythms and methods minimizing ths

average time of the claims in the network,also was offered algo-rythm of computing" traffic distribution on .working systems of network.There has been developed algorythm allowing consequence use the methods of decreasing spheres and accidental search and imitation modelling and all these above mentioned problems discuss the problems of stream distribution in nonformality of the optimisation function.'The algorythms and programmes oriented to the streams of requests with changing the priority of time have fcesn uSVelupeu, what can define the regimes of the management serving them in the network; component.

On the base of developed, models and algorythms is composed complex algorythm of network synthesis in which the searcch of technology of distributed computer network leads to the following: on the base of given source data topology is defined as an initial structure of network.The problems of throughput methods and external traffic distribution „on working-and terminal systems of the network have been solved.Depending on the situation the procedures of "input rib","input of additional efficiency of "□.».(distributed network)","the search of realizable stream" and "extvaction of rib" are executed.The structure of the network can be defined by modelling of the processes of service communicatlo-nal quiry.The structure what we have gat can minimize expentures to the creation of the network failure costs of the users because of imperfect components of the f UnCt.i0nxng.in5 rSSuit.3 Gt GuitpU-ting experiments and description of the principles of distributed computing network design automation are given in the dissertation.

The results of practical implementation of developed algorythms and electronic, computer of syntheses and analyses of the electronic computer network in creation of information computing systems distribution for "Zanyatost",are giyen in the application act of implementation of programme means into fund of algorythns Academy of Sciences Republic of Uzbekiston.