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

МИНИСТЕРСТВО СВЯЗИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Московский ордена Трудового фасного Знамени технический университет связи и информатики

На правах рукописи Данилов Алексей Николаевич

УДК 621.391.28

ИССЛЕДОВАНИЕ И РАЗРАБОТКА. МЕТОДА ФОНДИРОВАНИЯ ПЛАНА РАСПРЕДЕЛЕНИЯ ИНФОРМАЦИИ НА СЕТЯХ ПЕРЕДАЧИ ДАННЫХ С КОММУТАЦИЕЙ ПАКЕТОВ

Специальность 05.12.14 - Сети, узлы связи и распределение

информации

Автореферат

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

Москва 1992

Работа выполнена на кафедре "Передача дискретных сообщений и телеграфия" Московского ордена Трудового Красного Знамени технического университета связи и информатики

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

профессор Гладкий B.C. Официальные оппоненты - доктор технических наук,

профессор Умрихин Ю.Д. - кандидат технических наук Пучков ГЛЭ.

Ведущее предприятие - институт проблем передачи информации /ИШ/ АН РФ

Защита состоится " ^D " ^^лХ^г^п issjjr. в ->-0 час. на заседании специализированного совета к 118.06.02 по присуждению ученой степени кандидата технических наук в Московском ордена Трудового Красного Знамени техническом университете связи и информатики по адресу: 105855 ГСП Москва,ул. Авиамотор' ная,д. 8-а

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

Автореферат разослан " " IS92 г.

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

к.т.н.,допент у^лС^ Е.З.Ремвна

РОССИИ 1 ,----------

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

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

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

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

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

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

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

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

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

2) модификация численного метода оценки вероятностно-временных характеристик функционирования сетей ЦД с КП с учетом до-тока повторных пакетов и надежности элементов сети;

3) разработка алгоритма оценки требуемых пропускных способностей линий связи сетей ЦЦ с КП для заданных требований абонентов по вероятности и времени задержки пакетов;

4) оптимизация вычислительного процесса решения систем линейных алгебраических уравнений, используемых при оценке сетевых характеристик и пропускных способностей линий связи сете;!

ПД с КП;

5) сопоставительный анализ последовательных методов маршрутизации по вероятностно-временным характеристикам функционирования сети ПД с КП;

6) разработка метода маршрутизации для сетей ЦД с КП с учетом требований абонентов по времени задержки пакетов.

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

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

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

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

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

3. Модифицирован численный метод оценки вероятностно-временных характеристик функционирования сетей ЦЦ с КП, основанный

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

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

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

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

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

сетей ПД с KU реализованы в виде шкета прикладных программ для ЕС ЭВМ, предназначенных для анализа и синтеза сетей ПД с КП.

Реализация результатов. Основные результаты, полученные в диссертационной работе, включены в восемь научно-исследовательских отчетов МТЛЗй и чспользованы: в разработках НМИССУ при решении задачи численного анализа процессов маршрутизации на сети ПД, а также в учебном процессе кафедры "Передача дискретных сообщений и телеграфия" МТУСй при дипломном проектировании.

Были приняты в Государственный фонд алгоритмов и программ следующие программы:

1. Программа проверки сети на связность способом "свертки" (per. Л508850000756, 1985);

2. Программа оценки структурной надежности сетей связи (per. №50870001283, 1987);

3. Программа оценки характеристик функционирования сетей связи с коммутацией пакетов с учетом надежности и живучести элементов сети (per. ШЖ0000320, 1991).

А пр о о а ц и я работы. Основные положения диссертационной работы докладывались и обсуждались на отраслевом научно-техническом семинаре "Проблемы, методы и опыт создания автоматизированных систем управления связью" (Москва, I9S7 г.), XL У Всесоюзной научной сессия ВНТО РЗС им. А.С.Попова, посвященной Дню радио (Москва, 19Э0 г.), Xi УН научной сессии ВНТО РОС им. А.С.Попова, посвященной Дню радио (Москва, 1992 г.), научно-технических конференциях профессорско-преподавательского состава, научных, инженерных работников и аспирантов Московского ордена Трудового Красного Знамени технического университета связи и информатики (Москва, 1985 - 1987 Sit., I9S9 г., 1992 г.).

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

Структура и объем работы, диссертация состоит из введения(четырех глав, заключения и приложений. Работа изложена на 125 страницах.машинописного текста, содержит 39 рисунков, 5 таблиц, список литературы содержит 122 наименования.

Основные положения, выносимые на

защиту.

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

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

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

за счет учета потока повторных пакетов и надежности элементов Сети.

4. Разработанные модификации вычислительного процесса при решении систем линейных алгебраических уравнений, используемых для оценки пропускных способностей и вероятностно-временных характеристик Функционирования сетей ЦД с КП, позволяют сократить затраты машинного времени (на 70 и 40?) и повысить точность расчетов на 7С и 505» для метода простых итераций и итерационно-вероятностного |.;етода соответственно по сравнению с первоначальны:^ вариантами.

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

соджжи РАБОТА

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

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

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

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

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

Разработанный в данной главе метод нормирования плана распределения информации дает возможность оптимизировать план по среднесетевому времени задержки пакетов на сети 11Д с 1ш при централизованном управлении сетью с учетом инцидентных задержек на ребрах сети, нормирование таблиц маршрутизации для каждого узла коммутации осуществляется маршрутным центром. Процедура построения таблиц маршрутизации (Т.Л) состоит из трех этапов: I) на основе информации об инцидентных весах ребер сети производится расчет таблицы весов кратчайших путей иБли); 2) формирование таблицы маршрутных весов (ЬЛЗ) с использованием Т31и1 и матрицы инцидентных весов (..КЗ); 3) построение Т.Л на базе Т..13 дая заданного метода маршрутизации.

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

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

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

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

Зо второй главе диссертации модифицирован численный метод оценки вероятностно-временных характеристик (ЗБХ) функционирования сетей ПД с lui, основанный на использовании аппарата конечных дискретных цепей „:аркоза. Оценка 32Х необходима для реализации метода формирования плана распределения информации, предложенного в первой главе диссертации (при оценке инцидентных задержек на ребрах) и сопоставительного анализа ¡методов маршрутизации с целью выбора оптимального метода по совокупности параметров (времени задержки, вероятности доставки па-

Э

лчтов, вероятности циклообразования и др.).

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

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

Более совершенными и свободными от этого недостатка являются методы, основывающиеся на использовании марковских цепе*, п ним относятся методы с использованием теории массового обслуживания и методы, использующиэ аппарат конечных дискретных цепей Маркова (1СЗД-Л). Применительно к задаче оцеьки ЗЗХ функционирования сетей ЦЦ наиболее предпочтительно использование аппарата

К недостаткам данного метода можно отнести отсутствие учета потока повторных пакетов (Л) и таких параметров с£.ти,как на-двлшость элементов сетг, псзю;.;у в данной главе ипгцстазлсна кода»икац«5л метода оценки 2ЛХ ¿ункционароьаьля сете« 13Д с с использование;.; аппарата .уУ,.1., устраняющая указанниз выше недостатки .

При оценке численным методом, использующим аппарат КДЦЛ, времен задержек мевду УК сети и искомым УК необходимо определять инцидентные задержки на ребрах и вероятности направления ¡1 блоками управления Уй. сети пру поиске ./л в буфера ребер (матрица . л

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

- следующим образом: , , Л

¿^^ормпрует^л на базе подматрицы ..^и -

Л зектора Г® лектор Г*- вектор вероятностей успешного достижения а искомого ¿"К .

¿^представляет собо.1 квадратную латрлцу размерностью . Номера строк и столбцов матрицы соотвзтствует_нсмв-раг.: Уд сети ид. о столбец заносятся элементы вектора , причем диагональные I/, (■ )-л элемент равен единице, истальные

стобцы матрицы fl получаются из подматрицы исходной ш!В . С-я строка - единичная.

Необходимая дуй расчетов матрица Р^получается в конечном счете из матрицы Р1'^ ту тем трансформации в прямоугольную матрицу размерностью М'Ъ . Данная трансформация производится в соответствии со структурой сети (берутся только ненулевые элементы) .

tí диссертации введена новая сетевая характеристика - дис-персдл оценки длины траектории до попадания II в искомый J&e , позволяющая оценить влияние потерь II на длину траектории, опре-деляемой.по числу переприемов. Дисперсия оценки длины траектории П - Z/9 определяется следующим обоазом:

. 3/*

где /У®- фундаментальная матрица идеализированной цепи Маркова; 1®- единичная подматрица i.-ИГЗ ; Z - оценка средней длины траектории^ II (по числу перопривмов).

А концептуальной модели сети ПД с tul, принятое в диссертационной работе, рассматривается процедура повторной передачи ;i от Ул-источника. Яри данной процедуре повторно/ передачи И свод-ство независимости при похождении 11 по сети сохраняется, то есть не играет рола, из какого предыдущего в какой последующий УК поступил ¡I в процессе поиска искомого /К. лак показано во второй главе диссертации, поток повторных 11 можно аппроксимировать пуассоновскйм распределением. .Матрица интлтпвностеи потоков П (входного и повторного) между /К сети ЦЦ - определяется-следующим образом:

Á'(U) *AM+¿A{¿l(j) _ • —

&А(Ц)°А(чУШ), ¿'i* > J=í'ns>

где N¡ - размерность сети, А*ИпЩ - матрица интенсивно-стей входных потоков П ,S'*l¡V{ilj)tif,/si - матрица вероятности потерь í; между парами УК сети.

о данной главе предлагается оценизать матрицу интенсивно-степ входных потоков П на ребрах сети !1Д А*с учетом потока повторных II л надежности ребер сети, ¿актор надежности учитывается при нормировании -жШ для каждого искомого jjig . Приведем расчетные '.юрмуды: _ .

> к)

где Лн - вектор интенсивностеи поступления П, адресованных на сети :ЦД; Л"''- фундаментальная матрица (дая искомого ); /V} - число УК-получателей; число УК-источников.

В данной главе приведен алгоритм оценки требуемых пропускных способностей линии связи (ЛС) сетей ЦД с К11 для заданных качественных показателей работы сети, таких, как вероятности потерь и времена задержек П. В основу данного алгоритма положена математическая модель сети 1Щ, используемая при сценке сетевых ВВХ, го есть модель сети ОД с К11 представлена в виде разомкнутой однородной экспоненциальной сети массового обслуживания с одноканальными трактами передачи (ЛС). Поток повторных 11 не учитывается. Требования абонентов по потерям и времени до-отавки П задаются в исходных данных в виде матриц вероятностей блокировок 77" и инцидентных задержек н? ребрах сети Т.

Для решения указанной задачи необходимо решить совокупность систем линейных алгебраических уравнений. Основными эга-пами_решения являются: I) формирование совокупности МШ (¿**А) ; 2) оценка матрицы интенсивностей входных потоков П на ребрах сети ЦД • А*. Оценка пропускных способностей ЛС сети ЦЦ с КП будет при этом определяться следующим образом:

где 1/р - средняя длина П.

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

Для функционирования двухпараметрических методов маршрутизации необходимо знание чисел кратчайших маршрутов (<Ш).

В диссертации предложен"ййтод-получения 'Ш без построения деревьев кратчайших маршрутов для сетей произвольной структуры. №.1 определяется при помощи ТйШ и матрицы кратчайших путей (ЫКЦ), содержащей номера УК, составляющих х;ратчайшие пути. Жа строится в процессе формирования-ТМП и не предполагает получения деревьев кратчайших путей.

Третья глава диссертации посвящена оптимизации

вычислительного процесса оценки пропускных способностей ЛС и ВВХ функционирования сетей 11Д с КН.

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

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

Для уменьшения редкозаполненностп матриц коэффициентов СЛАУ., • используемых при решении задач оценки пропускных способностей ЛС и БВХ функционирования сетей ЦЦ с КП, в третьей главе разработаны модификсции вычислительных процессов при реше- -нпи СЛАУ методом простых итераций и итерационно-вероятностным методом.

Рассмотрим модификацию вычислительного процесса для итерационно-вероятностного метода. Представим матрицу коэффициентов СЛАУ ( (подматрица ШШ А®) размерностью ) в виде двух матриц

Операции суммирования строк и перемножения матриц и векторов сводятся в данном случае к операциям над ненулевыми элементами матриц и векторов, что.позволяет существенно уменьшить количество операций при■обращении матрицы и решении СЛАУ. Число операций при использовании указанных матриц ¿р^У случае вероятностного обращения матриц пропорционально' где заданное число статистических испытаний, а Уп - число ненулевых элементов по строке матрицы ). При исполь-'

зовании последовательнчх методов маршрутизации Лп Кро-

ме этого, достигается определенный эффект и при перемножении матриц и векторов при непосредственном решении СЛАУ итерационно-вероятностным методом.

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

•ад»

13

шения числа обращении к датчику равномернораспределенных случайных чисел (при построений трассы). При модификации вычисита-тельного процесса решения СЛАУ методом простых итераций чену-лввне элементы матрицы коэффициентов СЛАУ_ ( / - £? ^ ) задействованы при определении вектора невязки Г1К) в операции умножения матрицы коэффициентов СЛАУ на оценку вектора неизвестных

Итерационный процесс решения СЛАУ можэт быть представлен в виде: х^'Х^+Г^'О

ГМ*{-{1'(2Ге>)ХМ,

где - вектор свободных членов.

Б данной глава проведен сопоставительный анализ методов решения' СЛАУ - -Гаусса, простых итераций и итерационно-вероятностного с модификацией и без модификации вычислительного процесса по затратам машинного Бремени и точности расчетов при оценке вектора средних дайн траекторий П от всех УК сети к искомому УК3.

В результате анализа численных методов решения СЛАУ, используемых для оценки пропускных способностей ЛС и ВЗХ функционирования сетей ПД с КП, можно сделать вывод, что наиболее предпочтительным в нашем случае методом решения СЛАУ является метод простых итераций с модификацией вычислительного процесса. Однако метод простых итераций имеет ограниченную область сходимости. Ввиду этого для сетей ПД размерностью свыше 15 УК целесообразно использовать комбинацию методов простых итераций, итерационно-вероятностного и Гаусса с модификациями вычислительного процесса.

Процесс решения СЛАУ будет при этом выглядеть следующий образом. Вначале СЛАУ решается методом простых итераций. В случае невозможности получения решения с заданной точностью переходам к итерационно-вероятностному методу, ¿ели итерационно-вероятностный метод тадае не сходится, то тогда используем метод Гаусса. Модификации вычислительного процесса позволяют сократить затрата машинного времени - на 40: и 70% и повысить точность расчетов - на 50 и 70% для методов итерационно-вероятностного и простых итераций соответственно.

в четвертой главе диссертации проведено исследование метода формирования плана распределения инфорыа-

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

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

1) сроднесетевой длине траектории Л;

2) среднесетевой дисперсии длин траекторий II;

3) среднесетевой вероятности потерь 11;

4) среднесетевой вероятности доставки II;

5) среднесетевой вероятности циклообразования;

6) среднесетевому времени задержки П;

7) максима."ьной длине траектории П в сети;

8) максимальному времени задержки II между УК сети;

9) суммарной интенсивности потоков Д на ребрах сети ЦЦ;

10) среднесетевой инцидентной задержке на ребрах сети;

11) среднесетевому коэффициенту использования ребер сети;

12) среднесетевой вероятности блокировки ребра сети.

Для расчета сетевых характеристик была выбрана ячеистая

сеть ЦД размерностью 15 УК.

Как показал анализ, предлагаемый метод формирования плана распределения информации дает выигрыш по сравнению с методом формирования плана по минимуму числа переприемов по таким ВЗХ, как среднесетевое и максимальное время задержки 3 для нагрузок 47 - 94 КБит/се% при различных тяготениях в среднем от 3% до 24%.

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

В данной главе предложен метод маршрутизации, обеспечивающий требуемое врзмя доставки 11 в сети ЦД с КП Т • Разработанный метод маршрутизации целесообразно применять при централизованном управлении сетью. В основу данного метода положена математическая модель сети, используемая при оценке ВВХ функционирования сетей ЦЦ с КП, подробно описанная во второй главе. Ребро сети рассматривается как СМО типа И/М/1/Я . Разрабатываемый метод маршрутизации может быть отнесен в зависимости от наличия путей

2-го, 3-го и др. выбора к градиентным или диффузным методам маршрутизации .

На основании матрицы времени задержки Г и матрицы .срат-чайших путей, построенной по минимуму числа переприемов, получаем допустимые потоки на ребрах сети для выбранных путей передачи информации, причем коэффициенты таблиц маршрутизации, отличнче от 1 (при наличиии более одного кратчайшего пути для передачи П между УК сети), нам неизвестны и определяются в ходе решения полученных уравнений и неравенств баланса потоков на ребрах. Если система уравнении и неравенств не имеет решения, то тогда пере-_ ходим к кратчайшим путям второго выбора, которые используются затем вместе с путями первого выбора и алгоритм повторяется, в результате данных расчетов получаем план распределения информации со стохастическими коэффициентами таблиц маршрутизации, учитывающий время задержки между УК сети ЦД с КП.

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

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

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

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

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

3. Разработана модификация численного метода оценки ШЗА функционирования сетей ЛД с КП, использующего аппарат КДЦИ, позволяющая в отличие от прототипа:

1) учитывать поток повторных П и надежность элементов сети;

2) рассчитывать вероятности направления Л блоками управления УК сети при поиске УК-получателя;

3) производить оценку интенсивностеи входных потоков на ребрах сети ЯД с учетом потока повторных П и надежности ребер.

4. Разработана новая характеристика функционирования сети ЦЦ с КП - дисперсия длины траектории П, позволяющая производить оценку влияния потерь II на длину траектории П в сети ПД.

5. Разработана процедура расчета ЧйД для двухпараметричес-кзх методов маршрутизации, позволяющая определять 4КгЛ без построения дерева кратчайших путей. Данная процедура может быть использована для сетей ЦЦ различных структур.

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

7. Разработаны модификации вычислительного процесса при решении СМУ, получаемых при оценке ВВХ и пропускных способностей Ж сетей ПД с КП, позволяющие сократить затраты машинного времени в среднем на 70 и Л0% и повысить точность расчетов в среднем на 70 и 50$ для метода( простых итераций и итерационно-вероятностного метода соответственно. Наилучшие результаты в области его сходимости по точности расчетов и затратам машинного времени показал метод простых итераций с модификацией вычислительного процесса.

ь. а результате сопоставительного анализа методов маршрутизации по комплексу ШЗХ функционирования ячеистом сети ПД с КП размерностью 15 УК наилучшим из исследованных оказался градиент-

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

9. Исследования показали, что для ячеистой сети ПД с KJ размерностью 15 УК разработанный метод формирования плана распределения информации дает .'Лучшие результаты в среднем на 3 -г4% по максимальному л среднесетевому времени задержки II по сравнению с методом построения плана с учетом числа переприемов при интенсивностях входных потоков И до 47 - 94 КБит/сек, для равномерных, центростремительных и смешанных тяготений.

10. Разработанный метод маршрутизации учитывает в отличие от существующих методов маршрутизации требования абонентов по времени задержки II между УК сети ЦД с КП. Рекомендуется использовать данный метод при централизованном управлении сетью.

СПИСОК ОПУБЛИКО^АШШ РАБОТ НО Tilto ДйСС15РТАЦ№1 1. АЛ7оритм и программа проверки сети на связность способом "свертки". Государственный oAJI per. :s50b850U00756, 1985. Соав. Новиков С.Н.

2. Программа оценки структурной надежности сетей связи. Государственный ¿>АП per. J5508700UI¿83, 1987. Соав. Гладкий B.C., Новиков С.Н.

3. О некоторых методах повышения точности и скорости решения задачи численного анализа процессов маршрутизации на сетях ПД больших размерностей // Применение микропроцессорное и вычислительной техники в устройствах и системах связи / .Лоск, электротехн. ин-т связи. - ..и: 1987. - Деп. в .да -'йнформсвязь" ;ЯГ66, 19ь7.

4. К вопросу об использовании аппарата конечные дискретных цепей 'Ларкова для расчета пропускной способности сети связи с И // ¿летоды автоматизированного проектирования устройств, систем и сетей связи / ..¡оск. электротехн. ин-т связи. - ..¡.: 1987,-Деп. в ЦН'ГЛ "Ян^ормсвязь" J.H3U4, 19ЬЬ.

6. летод распределения потоков информации на сетях ЦД с с учетом требовании абонентов // ¿U Всесоюзная научная сессия, посвященная Дню радио. Тез. докл. - .л.: Радио и связь, J.991

а о р

j. • о • l< . ю «

6.Программа оценки характеристик функционирования сете:-! связи с коммутацией пакетов с учетом надежности и живучести srv-