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

МОСКОВСКИЙ ордена ЛЕНИНА и ордена ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

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

ЮАНЬ СЯО ДАНЬ

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

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

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

Москва - 1991 г.

Работа выполнена на кафедре "Вычислительные машины, комплексы, системы и сети" Московского ордена Ленина и ордена Октябрьско* Революции энергетического института.

Научный руководитель - доктор технических наук, профессор ШГуШЖО а. в.

Официальные оппоненты - доктор технических наук, профессор КУЛЕШОВ А. П. "'.-..

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

паршенков а а

Ведущая организация: Всесовеный Научно-технический Информационный Центр

Защита диссертации состоится " 31 " .Л1С1.Л 1991 г. в Л£ час. в аудитории Г" на заседании

специализированного Согета К 053.16.09 Московского Энергетического Института.

Отвыв на автореферат, заверенные печатью, просим присылать по адресу: 105835, ГСП, Москва Е-250, Красноказарменная уд. , д. 14, Ученый Совет МЗИ.

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

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

Ученый секретарь специализированного Совета • К 053.16. 09 к. т. н.

Ас\А 1991 Г.

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

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

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

разрабатываемой распределенной информационной системе, предназначенной для обслуживания Олимпийских Игр 2000 года, которые состоятся в Китайской Народной Республике (условное название ИВС-Олимпиада-2000).

Для этой системы должны Сыть выработаны рекомендации:

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

2) По оптимальному размещению обслуживающих информационных процессов в главных вычислительных машинах системы.

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

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

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

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

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

Апробация р¡.боты - Результаты работы докладывались на научных семинарах кафедры "Вычислительные машины, комплексы, системы и сети" МЗй и !А:хдународного Центра Научной и Технической Информации.

- Б -

Структура и объем работы - Диссертация состоит из введения, четырех глав, заключения, списка литературы на 103 наименования. Общий объем работы 207 страниц, включая 12 рисунков и 59 таблиц.

Автор выносит на защиту:

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

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

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

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

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

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

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

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

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

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

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

- потери времени на ожидание в очередях на передачу;

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

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

- потери времени, связанные с конечностью скорости /реакции в узлах на прибившие сообщения;

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

Велел за Р. Галлагером [ IEEE Trans Comm. C0M-25,1977,Nol,p. 73] приводится математическая постановка проблемы маршрутизации. .

Рассматривается сеть из N узлов, соединенных каналами связи, в которой каждый канал (ik) характеризуется своей пропускной способ-костью Cik(6kt/e). Предполагается, что в сети нет ни потерь, ни

увеличения объема передаваемой информации (например, из-за многоадресной передачи). В узлы сети поступает от абонентов системы внешний поток, распределение которого есть {г1(3)> ( П(з) - количество пакетов, поступающих в секунду от абонентов ¡-ого узла для передачи абонентам .¡-ого угла). В узлах сети определяются таблицы маршрутизации Шк(з)>, показывающие, какая доля полного потока в узле ь адресованного уалу j должна быть направлена по каналу (1к). При атом величины <Ф1к(з)> удовлетворяют условиям:

О < Флф I , £ Ф ((£ф = I , 1; (1)

"Ф.-мл = о , ФиО> = 0.

Третье условие отражает тог факт, что пакеты, достигшие своего адресата, покидают сеть, а последнее - что в сети отсутствуют петлевые каналы.

Обозначим полный поток в узле 1, адресованный узлу ^ РЦ;|), тогда величины Р, г, Фв узлах сети связываются уравнениями баланса

Р1ф = г,ф + г ¿-Гп . (2)

поток в канале Ок)

= £ Р< (]) ф!к(]) . (3)

Критерий качества распределения потоков - средняя задержка сообщений в сети

Рт(Г.ф) ПО))". (4)

Задача маршрутизации заключается в построении таблиц маршрутизации ШкП)} в узлах сети, обеспечивающих минимум средней задержки От для любого данного г

Рт С Г, Ф.(п; =minpT(r. ,' (5)

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

В реальных сетях ri(j) являются случайными быстроменяющимися величинами. Информация об изменении входных потоков, а также очередей на каналах удаленных узлов распространяется по сети со скоростью, имеющей тот же порядок величины, что и информация пользователей. Поэтому реальные сети действуют в условиях запаздывания маршрутной информации, которое тем больше, чем дальше данный центр находится от места изменения состояния сети. Таким образом, вместо реальных потоков fik и задержек. Tik центры маршрутизации используют более или менее адекватное представление о них. Например, при оценке состояния очередей их мгновенными значениями:

fiK(t) =?■ Síi<(t- m/MAt),

Здесь fik(t) - оценка ("образ") штока в канале (¡k) в момент времени t,

диаметр сети в числе передач, го - число передач служебного пакета, необходимое чтобы доставить информацию о состоянии канала (tk) в центр марш-| рутизации ( при этом состояние своих собственных каналов ' | (пИЭ) каддый центр знает совершенно точно ), ■ ¿t т предельная величина запаздывания маршрутной информации.

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

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

Для системы 0лимпиады-2000 средняя длина пакета составляет 1 - 200 байт, все каналы имеют одинаковую пропускную способность С - 9600 бит/сек. Отсюда время передачи пакета Тп - 0.167 сек. которое принимается за единицу измерения задержек в сети. В дальнейшем все результаты приводятся в этом масштабе времени.

ДЛя исследования проблем маршрутизации и управления потоком в системе Олимпиада-2000 была разработана имитационная модель, которая решает задачу статистического распределения по сети потоков информации, поступающих изЕне от пользователей сети к обслуживающим процессам и обратно. В модель закладывается описание топологии сети, пропускных способностей каналов, число и расположение обслуживающих информационных процессов. Программа моделирует поступление пакетов в узлах сети в соответствии с заданным распределением вероятности. В ходе экспериментов поток полагался многомерным пу-ассоновским потоком. Случайные величины <П(])> характеризуются местом поступления пакетов в сеть 1 и адресом назначения ;) .

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

Рис. 1. Общая схема информационной сети 0лшлпиаца-2000.

генерация характеристик сати

генерация следующего события

норыуГ

ВНОВЬ ноступик-'лй Б сеть пакет, регистрация его характеристик

з_

ттунзптнну,

регистрация изменения состояния* узла при поступления . транзитного пакета

выбор выходного какала £ соответствии с адресом узла и.язиачгния процадуро£ 1/.ар;арутй з ацн::

оегистр&шгя времени доставил пакета, екчисл о н л е с т а т1. ю тлче с ки>;

есллчнн

пакет поступает на пе-оепачу оегпстиздпя характеристик поосдата

пакет стадится в очередь на леоодячу в соответствии с с дяс151ШШ!!по{1 обслужванта

Рис. 2. йиок-схог/а модели.

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

Б процессе моделирования вычислялись следующие характеристики сети:

- О:-число пакетов, прошедших через канал ] за время наблюдения;

- средняя задержка на .¡-ом канале

Т» ' (7)

( - задержка пакета о* при прохождении канала );

- относительное среднеквадратичное отклонение

(8)

& -//Я 2 (Н -л/.

Приводится число пакетов, находившихся в системе на момент окончания испытаний, а также среднее время доставки пакетов

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

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

%i(t) fint - m/p^t).

Наконец, алгоритм АЗ также действует в реальных условиях ко-1 нечной скорости распространения маршрутной информации, но оценивает состояние очередей по усредненным значниям:

flK lt) = J¡K (f - fíi/rf&t) >

(9)

fmt) —i/pJ?fiK(t-x) h .

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

Из натурных экспериментов на макете системы 0лимлиада-2000 известно, что максимальное запаздывание маршрутной информации составляет д t - 10 единиц.

Исследование этих алгоритмов показывает, что наилучшие результаты при таком запаздывании имеет алгоритм АЗ с величиной D - 5 ед. (см. таблицу)

¡ I ! АЗ !

алгоритм I Al ¡ А2 !-----------------------------------!

i D-3 i D-5 i D-7 1 D-10 D-20 I

среднее ¡lililí I

время ! 2.91 I 6. 45 I 5.34 I 4.92 ¡ 5.21 ! 5.71 1 6. Об I доставки I I I I I i I I

( Входная нагрузка R - Y ri(j) - l/(3Tn).

Вторая задача, решаемая в рамках третьей главы - выбор размещения информационных баз данных в ГВЫ сети.

Конечным процессом .системы 0лимпиада-2000 является автоматизированный банк данных спортивной информации, который должен быстро обслуживать пользователей системы. В силу конструктивных особенностей сети основная часть запросов пользователей (свыше 80%) поступает через узел STRATUS ХА-2000 . Если обслуживающий' процесс размешается только в одной ГВМ, задержки на обслуживание могут быть неоправданно велики. С другой стороны, размещение одной базы данных во Есех ГВМ сети может приводить к нерациональному расходу ее ресурсов. В связи с этим возникает задача о выборе числа дублей одной базы данных и их размещении в ГВМ сети.

Такая постановка задачи требует включения в рассмотрение .как базовую сеть, так и подсеть ГВМ. Еа рис.3 приведена эквивалентная схема сети в условиях,. когда адресатом назначения является одна база данных, размещенная во всех ГШ сети. Узлы, непосредственно соединенные с узлом назначения (БД), отображают локальных пользователей в данном узле коммутации^ которые могут обращаться к БД, минуя сеть. Пакеты, как локальных, так и удаленных пользователей ставятся в одну очередь, что соответствует равноправию обеих категорий пользователей. Вместе с тем, если пакеты локальных пользователей встречают очень большую очередь к БД в данном узле, они могут быть перенаправлены в другие узлы с тем, чтобы уменьшить время обслуживания запросов пользователей.

Эксперимент по моделированию потоков в сети с учетом конечного' прикладного процесса проводился в условиях, когда в узел Б (STRATUS ХА-2000) поступало 807» нагрузки, а в остальные 5 узлов -по 4X; весь поток был адресован узлу 13 (БД). Результаты экспериментов показывают, что некоторые ГШ в узлах (2 и 6) обслуживают существенно меньше запросов пользователей, чем другие. Исходя из этого было предложено снять в ГВМ этих узлов базу данных. Повторный просчет в условиях, когда БД находилась во всех ГВМ, кроме уз-, лов 2 и 6, показал, что в этом случае задержка в сети возрастает примерно на 10Х, что является вполне приемлемой платой га освобождение ресурсов этих ГВМ для других эадач.

Рис. 3. Эквивалентная топология сети.

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

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

чтобы характерная аадержа пакетов не превосходила 'заданной вели* *

чины Эт , От > Бт(0).

При этом возникает задача ограничения входных потоков в узлах сети: необходимо построить такую процедуру управления потоком, которая в случае перегрузки Бт(гО) > От* обеспечивала бы ноЕое распределение потоков г*, чтобы выполнялось

о =6 г!<л г! Ф . (10)

|рг(г") = Ог| < £ . (11)

и пропущенный поток был максимальным:

тх , (.12)

и

( £ - точность решения задачи).

Если Эт(гО) < От и в сети нет абонентов, потоки которых были ограничены на предыдущих шагах алгоритма, никакого воздействия на поток оказываться не должно ( г» - г* ).

Если От(гО) < йт , но в сети существуют ограничения на некоторые потоки, эти ограничения следует частично или полностью отменить, установив о сети новый поток г отвечающий условию

П (]) < г! Ф < Г; ф + * . (13)

и условиям (11)-(12). Здесь Ы - предельная величина, на которую абоненту разрешается увеличить свой поток за один шаг процедуры управления.

Решение задачи (10)-(12):

гГ1*0„) - 0, (и» М1;

' I пЪ --П(]). Си)«/ ш.

Ш - < (и),, , ш - ГГк >: т\т[и) >0,

>- и и >-..... >- ,

V (и) Ф Ю, г1(3) > 0: >- ИЗ .

-1 к-1

к: 0 <- Ы^л(гО)[2Г Ы„1л(гО) - Вт(гО) + От*] <- гГЛ:*). ' т-1

здесь - 1лз - расстояние ыевду узлами 1 и з в метрике задержек.

Решение задачи (11)-(13):

л п* (з„) - г1„(Зя) + , (и)Ле

I гГо) - пи). (и)^ Ж.

М2 - < (и)Л , ш - Г7к>:

И1и -< '< ..... -< И*)* ,

У (и) 4 ма из >-ц^.

-1 . к-1 к: 0 <- ИЛ3Л.(гО)[ Ст - ВДгО) - 2Г Ы^з^СгО + *)] <пИ.

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

Построена процедура управления потоком, реализующая решения задач (10)-(12) и (11)-13). Эта процедура действует на основе усредненных значений гЦ^О. Для того, чтобы система могла реагировать на мгновенные перегрузки в узлах сети, она должна быть дополнена локальной процедурой управления потоком. В качестве такой процедуры рассматривается "буферный" алгоритм управления потоком, который ставит доступ новых пакетов зависимость от уровня заполнения буферов. При уровне заполнения больше заданном величины Ш, новые пакеты в этом узле не принимаются, а транзитные продолжают приниматься, пока в буфере есть свободное место. При этом возникает задача выбора уровня заполнения: если уровень заполнения сделать большим, то возрастает опасность возникновения перегрузки в узле, а при малой величине уровня заполнения снижается пропускная способность сети. Задача выбора эффективного уровня заполнения буфера исследовалась методами имитационного моделирования. Было получено, что для параметров алгоритма управления, , характерных, для системы 0лнмпиада-2000 ( диапазон нагрузок й - 1/(зТп), з - 2. О, 2.2, 2. 4, емкость буфера 25 пакетов ) эффективный уровень заполнения равен 20 пакетов. Результаты моделирования работы системы с алгоритмами маршрутизации А1, А2 и АЗ при буферном алгоритме управления приведены на рис.4. Как следует из графиков, алгоритм АЗ показывает вполне удовлетворительные результаты и потому может быть рекомендован для информационной системы Олимпиада-2000.

(секз1 10

1.0

Pi:c. 4a.

M -С -

'. w-

N{

Je w за

го lo

1.2

1.4

1.6

1.8

2.0

2.2

Ср&дда*» Iowa пор' T п;л рлз-тачанх ялгор::т.''оа кар::;зут пргт'.л. С Al, А2, A3 5

S^ßc /V ,

средняя дг.:!пп пек- тр..

пропускная способность гг-:\с.гл. С 5::т/с>

полная поток е сот::. ír.nv../c}

И = р / с?»Р > ( О

1.0

Рис. 46

э .

- Р.

1.2. 1.4 1.6 1.8 2.0 2.4

, Згш^сгл'зеть нгпр:'!штнх пакетов Д/

от нагрузка в сети S -- поток пр:::щтю: cstlg таклтов. ■ -'еогок пвррипятавс сеть :' пагчтов.

ЗАКЛЮЧЕНИЕ

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

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

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

4. Поставлена и решена задача оптимального управления входными потоками в квазистационарных условиях. Сформулирована централизованная версия оптимального алгоритма^управления входными потоками, учитывающая распределение транзитных потоков в сети. Исследована процедура "буферного" управления входными потоками, в которой доступ в сеть ноеых пакетов ставится в зависимость от заполнения буфера в узле. Выбран оптимальный уровень заполнения буфера транзитными пакетами, обеспечивающий .наивысшую пропускную способность сети 0лимпиада-2000 при заданной предельной средней задери« сообщений в сети в указанном диапазоне нагрузок.

п л _ •Ав/Р

«хтыт^^шп 3|кп ез у- Гтгп.цтио.

Т1- н>| м-ш, Крагцоказлрченн |Н. 13