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

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

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

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

' АЛЬСАМАРА Васим

УДК 621.391.28

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

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

Автореферат

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

Москва-1993

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

Научный руководитель - доктор технических наук, профессор ПАДКИЙ B.C.

Официальные оппоненты- доктор технических наук, профессор БИТОВ В. А.

- кандидат технических наук ПУЧКОВ Г.Ю.

Ведущее предприятие - Институт автоматизированных сиотем

(ИАС)

Защита состоится J 1994 г. в "/#» часов

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

С диссертацией можно

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

ознакомиться в библиотеке университета. If 199* г.

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

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

к.т.н., доцент Е.В.Демина

(^X'tiiuA^

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

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

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

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

Цель работы и задачи исс ледов а-

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

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

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

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

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

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

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

1. С использованием аппарата конечных дискретных цепей Маркова разработан метод оценки инцидентных задержек пакетов на 'ребрах сети ПД с КП. Метод использован для оценки пропускных способностей каналов сети ЦД с КП, а также может быть использован для оптимизации структуры сети ПД с КП.

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на:

- научно-технических конференциях профессорско-преподавательского и инженерно-технического состава Московского ордена Трудового Красного Знамени технического университета связи и информатики (1992-1993 г.г.);

- заседаниях кафедры передачи дискретных сообщений и телеграфии Ш7СИ (1991-1993 г.г.).

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

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и приложений. Работа^изложена на 126 страницах машинописного текста, содержит 22 рисунка, 9 таблиц, список литературы содержит 93 наименования.

Основные положения, выносимые на защиту:

- б -

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

- среднесетевая задержка пакетов в сети; -

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

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

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

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

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

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

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

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

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

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

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

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

3. Формирование таблицы маршрутизации для заданного метода маршрутизации на основе таблицы маршрутных весов.

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

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

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

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

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

Бали разработаны два варианта метода оценки инцидентных задержек пакетов на ребрах сети.

I. Инцидентные задержки пакетов на ребрах сети ПД задаются равными, и в этом случае для оценки задержки пакетов на ребрах сети необходимо задавать либо среднесетевое время задержки пакетов - Тер, либо максимальное время задержки пакетов между узлами коммутации - Тмах и матрицу вероятностей блокировок ребер сети -ЗЕТ .

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

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

г = ТсР

^ср ~ л

1-ср

где Тер - среднесетевое время задержки пакета в сети;

- по матрице £ выбирается максимальная без потерь длина траектории пакета в сети - |1тах . тогда

, _ ТТпах

4/1

- 8 -

Приведем расчетные формулы для оценки идеализированной (без потерь) матрицы длин пакетоз^м^кду узлами коммутации сети - L , причем, элементы векторов L занятости при этом в 1-е оголб-

цы матрицы L :

Ñít,= (D,e,)-iN't,Dte') D'^lES'jdg,

lm= r

где n's - число узлов получателей;

¿>¿l> - вектор вероятностей успешного достижения 1-го уз-_ ла-получателя;

- вектор-столбец матрицы переходных вероятностей для £ -го узла-получателя, характеризующий вероятнос-А ти успешного достижения пакетами искомого узла; А/'"- идеализированная фундаментальная матрица для L -го искомого узла коммутации;

фундамзнтальная матрица для ^ -го узла-получателя; 3 - единый вектор-строка. 2. Априорно задается матрица задержек пакетов между корреспондирующими узлами коммутации сети, учитывающая средние длины траекторий пакетов без учета потерь - Т = II t¿j Нп,л , где П - число узлов коммутации сети ПД.

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

Вектор задержек пакетов на узлах сети при поиске i -го узла коммутации определяется следующим образом:

¡ <»-Q«>}.i

r M

где - единичная матрица;

О 111 - подматрица идеализированной (без учета потерь, пакетов) матрицы переходных вероятностей -Р1>',

- Я -

I О

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

Подматрица идеализированной матрицы переходных вероятностей - и ® определяется слвдугацим образом:

где 0'^- подматрица исходной матрицы переходных вероятностей (с учетом потерь пакетов).

Если обозначить инцидентные задержки пакетов на ребрах ¿-го узла коммутации сети через Т (¿), то тогда

гШ'Т(¡ф)-... -га,^)-т(е)1с)

для любого В , где п^ - ранг ¿-го узла коммутации сети ПД.

Меняя номера узлов-получателей и произведя вышеприведенные расчеты, получаем матрицу инцидентных задержек пакетов на ребрах сети ПД с КП -Г = // Нп.ъ , где

П$ - максимальна! ранг узлов коммутации сети.

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

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

- 1.0 -

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

С г-const;

Л* = {г(Т, А"'); Я • const, i-Tj\;

^--UCK'W")-

Я"-/, (Л, /О; Л -const;

f« S/"); Ът={ь(М11\Р">}; 4W= ir (N'f\ Pltt);

1">Ч, ГЛП;

fiw={3(N">);

■ a.

Ur, P">);

где

N = (1-0Г' ;

ч

С - матрица пропускных способностей каналов;

Г - матрица инцидентных задержек пакетов на ребрах се- ти ДД с КП;

Л* - матрица суммарных интенсивностей поступления пакетов на ребра сети ЦД с КП; - матрица вероятностей блокировок ребер сети;

Л'"- матрица пропускных интенсивностей пакетов, адресованных I -ку узду коммутации;

Л'че>- вектор интенсивностей поступления пакетов, адресованных £-му узлу коммутации, на узлы сети;

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

А/фундаментальная матрица для искомого i.-vo. узла коммутации;

Л - матрица интенсивностей входных потоков пакетов в се-

_ ' ти ПД с Ш;

t'e>- вектор задержек пакетов между узлами сети и искомым

_ t -м узлом;

Т^- вектор задержек пакетов на узлах сети при поиске искомого £ -го узла;

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

- вектор вероятностей успешного достижения искомого t -го узла;

v Ш

L - вектор средних длин траекторий пакетов при поиске искомого £ -го узла;

h - вектор вероятностей цшслообразований пакетов при поиске искомого £ -го узла;

А - матрица весов ребер сети ПД с КП:

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

О -tQ"l Q'1!,., 0й'!..., О'"'} - совокупность подматриц матриц

переходных вероятностей.

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

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

- среднесетевая длина траектории пакета - L$ ;

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

ла коммутации - р'дос;

- среднесетевая вероятность потерь пакетов - ¿> ср;

- среднесетевое время задержки пакетов в сети ПД - Тер;

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

- суммарная интенсивность поступления пакетов на ребра сети

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

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

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

Были приняты следующие обозначения:

а/ для градиентного равновероятного метода маршрутизации; I - равномерные тяготения; 3 - центростремительные тяготения; 5 -центробежные тяготения;

б/ для градиентно-диффузного метода маршрутизации: 2 - равномерные тяготения; 6 - центробежные тяготения.

Как показал анализ, градиентно-диффузный метод маршрутизации дает значительный выигрыш (в среднем на несколько порядков) по вероятности потерь пакетов во всем рассматриваемом диапазоне нагрузки. Требуемые пропускные способности каналов сети при градиентном равновероятном и градиентно-диффузном методах маршрутизации практически не отличаются друг от друга (разница 1-2%). Градиентно-диффузный метод маршрутизации хоть и незначительно (на 2-3$), но превосходит градиентный равновероятный метод по среднесетевому времени задержки пакетов. Минимальная загрузка сети и требуемые при этом пропускные способности каналов были получены для равномерного взаимного тяготения узлов коммутации,

от вероятностей блокировок ребер-сети - Я" для различных тяготений

Рис. 2. Зависимость среднесетевого времени задержки .—Тгр от инцидентных задержек на ребрах - "С" для различных тяготений

з,о

1.* 1,0 а*

Смак г (О* Вит/сек

1 ///; -------Н-Д

¡¡¡г 1 к ч'

//

/У' //// ///

Г Пк /} С (!

/// // //г

Л /У, / /г

■

80

160

320

640

1280. А г-

сек

Рис. 3. Зависимость максимальной пропускной способности

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

а .

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

- все инцидентные задержки на ребрах сети равны между собой;

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

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

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

СПИСОК ОПУЖИКОВАШШ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

I. Метод оценки инцидентных задержек пакетов на ребрах сети ПД с КП //Обработка сигналов в системах связи /Сб. науч. тр. учеб. ин-тов связи. - ЛЭИС. - С.-Пб; 1992. - С. 57-60, соавт. Данилов А.Н.