Введение к работе
Актуальность работы. С развитием научно-технического про-гресса растет объем передаваемой информации в различных сферах производства и паучноГ; деятельности. Это требует создания высокопроизводительных, отказоустойчива систем обработки и передачи данных, позволяющих: сократить затрати на обработку информации, обеспечить требуемое качество обслуживания, предотвратить неэффективное распределение и использование вычислитель них ресурсов. К таким системам могут бить отнесены 'распределенные вычислительные системы массового обслуживания, предназначенные для распределения ресурсов и выдачи информации различным пользователям.
Технической основой таких систем являются сети ЭБМ, в ко
торых одним из основных элементов является сеть передачи дан
ных (СЕД). Для этих сетей характерны повышенные требования к
реактивности и надежности. Эффективность функционирования и
стоимость таких сетей существенно зависят от правильного вы
бора параметров, методов передачи информации и топологичес
кой структуры. Решение этих задач связано с трудностями из-
за нестационарносги и большой размерности, поэтому необходи
ма разработка соответствующего математического аппарата, ко
торый в законченном виде должен составлять единую систему про
ектирования. '
.; настоящему времени разработано и исслодовано большое чи-со методов и алгоритмов, посвященных реыгчии различных задач проектирования СПД (ьыбор топологичосной структуры СПД,^ш5ор пропускных способностей и распределение потоков, анализ буферной памяти, управление потоком и т.п.). Аналка этих работ показывает, чю задача определении оптимальных маршрутов пореда-чг информации в СЩ (задача маршрутизации) занимает одно из
центральных мест среди таких задач, так -как на результатах решения этой задачи базируются методы оценки различных показателей эффективности СПД. Существующие алгоритмы решения задачи выбора оптимальных маршрутов не в полной мере отражают особенности реальных сетевых протоколов, что является чрезвычайно важным при проектировании СПД. Б связи с этим разработка и исследование алгоритмов маршрутизации при проектировании вычислительных сетей массового обслуживания является актуальной задачей.
Цель работы заключается в разработке новых алгоритмов маршрутизации в ОВД, позволяющих определить:
оптимальные виртуальные маршруты передачи информационные
потоков;
' '' .
времена доставки сообщений между каждой парой узлов с учетом многопакегпости передаваемой инфордации, разнородных каналов связи, различных критериев эффективности.
Основные задачи диссертации, определяемые поставленной целью, состоят в следующем:.
Разработка и исследование метода расчета оптимальных альтернативных маршрутов и интегральных характеристик сети пакетной коммутации;
Разработка ^аналитических подходов для отыскания нижней оценки среднего времени задержки сообщений в сети передачи данных; о
Разработка метода исследования интегральных характеристик сети с учетом многопакетности пе; одаваемой информации по альтернатив ним наргарутам;
Исследование поведения сети и ее топологической структуры в зависимости от нагруЗки, при использовании различных стратегий маршрутизации;
Разработка алгоритма выбора пропускной способности и альтернативных маршрутов для отыскания оптимальной стратегии последовательного во времени повышения производительности в развивающейся СПД;
Исследование и сравнение стратегий развития сети (без реконфигурации на каждом этапе и о реконфигурацией) при различных методах маршрутизации.
Методы исследования. Основные результаты диссертационной работы получены с использованием методов теории сетей массового обслуживания, теории вероятностей, теории графов, оптимизации потоков в сетях.
Научная новизна работы, заключается в создании новых алгоритмов топологической оптимизации и распределения потоков в сети, которые имеют более высокую эффективность по сравнению с известными алгоритмами решения данной задачи.
.Новыми научными результатами являются:
алгоритм альтернативной маршрутизации, базирующийся на алгоритме отклонения потоков и обеспечивающий нахождение виртуальных маршрутов и времени доставки сообщений меиду любыми парами узлов;
метод отыскания шиной сценки среднего времени досгалки сообщений;
аналитический метод расчета среднего времени доставки :.:ногопакетннх сообщения при использовании альтернативної! маршрутизации;
- б -
- применение метола альтернативной маршрутизации в сочоу; ний с комбинаторным алгоритмом топологического синтеза сех<;.
Практическая ценность. Разработанные в диссертации метод.! и алгоритмы позволяют существенно сократить сроки и позисщі, качество проектирования СПД в различных отраслях народного хозяйства. Полученные результаты могут быть использованы в процессе эксплуатации реальных сетей, позволяют повысить каг честзо функционирования сети при минимальных затратах ресурс сов, а такке определить оптимальную стратегию развития сети.
Достоверность научных результатов и практических рекоыенп даций подтверндастся необходимыми математическими выкладками, многократными сравнительными расчетами, согласованностью с экспериментальными данными.
Реализация результатов работы. Научные и практические результаты диссертации использованы при проектировании, внедрении и развитии Общесоюзной системы управления продажей билетов и броіїированием мест на внутренних авиалиниях "Сирена-2", разработанной в соответствии с программой работ по решению научно-технической проблемы 0.80.09, утвержденной Постановлением ГКНТ и Госплана СССР от 8.12.1981г. К» 49Г/244 (прилоае-нис К; 6*0 и по совместному приказу Минприбора СССР и МГА СССР !,? 96/182 от 8.07.1982г.
Методика оптимального повышения производительности сети в процессе эксплуатации, разработанная в диссертации, была использована в ГВЦ ГА при подготовке системы "Сирена-2" к летней навигации 19о9г.
Апробация работи. Основные полоаешш диссертационной работы доклздшались и обсуждались на 4-П и 5-і! всесоюзных ико-лпх-сомнк^&х по распределенным автоматизированным системам
массового обслуживания (Кутаиси, 1987; Москва, 1988); на 5-м Всесоюзном семинаре "Распределенные информационно-управляющие системы" (Саратов, 1988); на 11-м Всесоюзном совещании по проблемам управления (Москва, 1988).
Публикации. По теме диссертации опубликовано 6 печатных работ.
Структура ,и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения,изложенных на стр., двух приложений на стр., содержит рисунков,
таблиц. Список литературы имеет наименований. "