Содержание к диссертации
Введение
1. Особенности управления в интегральных сетях АСУ 12
1.1. Характеристика информационных потоков и технических средств ИС, особенности управления обменом информацией 12
1.2. Задача управления обменом информацией в ИС 22
1.3. постановка задачи исследования методов управления обменом информацией и методика ее решения 33
Выводы по главе I 44
2. Модели обмена информацией в ИС 45
2.1. Построение обобщенной модели обмена информацией в ИС 45
2.2. Выбор критерия оценки эффективности алгоритмов управления обменом информацией в ИС 56
2.3. Модель обмена информацией в ИС с фиксированной маршрутизацией 64
2.4. Модель обмена информацией в ИС с адаптивной маршрутизацией ". 91
Выводы по главе 2 109
3. Разработка методов и алгоритмов управления обменом информацией в ИС 112
3.1. Разработка метода и алгоритмов выделения зон управления 112
3.2. Разработка метода и алгоритмов адаптивной внутризоновой маршрутизации с гарантированными показателями качества путей передачи 124
3.3. Разработка алгоритмов ограничения интенсивности информационных потоков 141
Выгоды по главе 3 149
4. Экспериментальное исследование алгоритмов управления обменом информацией в ИС 151
4.1. Постановка задачи экспериментального исследования 151
4.2. Разработка алгоритмов машинной имитации обмена информацией в ИС 161
4.3. Анализ результатов имитационного моделирования 173
Выводы по главе 4 184
Заключение 185
Литература 187
- Характеристика информационных потоков и технических средств ИС, особенности управления обменом информацией
- Построение обобщенной модели обмена информацией в ИС
- Разработка метода и алгоритмов адаптивной внутризоновой маршрутизации с гарантированными показателями качества путей передачи
- Разработка алгоритмов машинной имитации обмена информацией в ИС
Введение к работе
Развитие народного хозяйства за последние годы привело к усилению взаимосвязи всех его составных частей, что в свою очередь обострило проблемы управления социалистической экономикой. Как указано в документах декабрьского (1983 г.) Пленума Центрального Комитета КПСС: "Ныне назрел вопрос о разработке программы комплексного совершенствования всего механизма управления, который должен полностью отвечать экономике развитого социализма и характеру решаемых задач" [ij. Для оперативного и эффективного управления объектами народного хозяйства и всем народным хозяйством в целом становится необходимым использование экономико-математических методов, невозможное без применения средств вычислительной техники и автоматизированных систем управления (Д&О различных уровней. Рост промышленного потенциала вызывает увеличение объема информации, необходимой для качественного управления, поэтому разработка и внедрение АСУ, средств и систем сбора, передачи и обработки информации в соответствии с решениями ШІ съезда КПСС [2], декабрьского (1983 r.)[lj и февральского (,1984 г.)[3) Пленумов ЦК КПСС идут быстрыми темпами. Наиболее эффективное управление объектами народного хозяйства достигается при использовании интегрированных АСУ (МАСУ) [4,5], объединяющих Е единую систему организационно-экономические системы с отраслевые АСУ, АСУ предприятиями) и АСУ технологическими процессами. Функционирование таких систем требует достоверной и своевременной передачи больших объемов самой разнообразной информации: речи, оперативных и диалоговых данных, информационных массивов, изображений.
Существующие информационно-вычислительные сети (ИВС) АСУ ориентированы в основном на передачу данных[б,?] и не удовлетворяют требованиям МАСУ по этой причине возникла необходимость Е создании интегральных сетей (ИС) АСУ. Основной особенностью ИС, отличающей их от существующих ИВС, является разнообразие видов информации, передаваемой и обрабатываемой в сети в единой цифровой форме. Технически создание ИС стало возможным благодаря появлению цифровых систем передачи информации, систем импулъ-сно-временной коммутации и микропроцессорных наборов, позволяющих реализовать узлы коммутации (УК) высокой производительности. Эффективное функционирование различных подсистем и звеньев ИАСУ и наиболее полное использование ресурсов ИС можно обеспечить создав систему управления сетью, реализующую адаптивное по отношению к изменяющимся внешним условиям управление информаци-к онными потоками и ресурсами ИС. Частью этой задачи является раз-/ раб,отка методов управления обменом информацией, под которыми понимаются методы адаптивной маршрутизации и ограничения интенсивности информационных потоков.
Вопросам исследования и разработки систем управления ИВС в условиях ИАСУ и, в частности, методам управления обменом информацией посвящен целый ряд работ как советских, так и зарубежных ученых. Среди них можно выделить работы Б.Е.Аксенова, А.В.Бут-рименко, А.П.Кулешова, В.Г.Лазарева, И.А.Мизина, Н.Я.Паршенко-ва, С.И.Самойленко, Б.Я.Советова, Э.А.Якубайтиса, Р.Галлагера, М.Герлы, Дж.грубера, Х.Иносэ, С.йонева, Ф.Камуна, Л.Клейнрока, Дк. Мак Куиллана, Г.Рудина, М.Шварца и других. Опубликованные работы относятся в основном к ИВС, ориентированным только на передачу данных, и не в полной мере учитывают особенности информационных потоков и технической базы ИС. Новые результаты в этой области могут быть связаны с детальным анализом опыта уже функционирующих сетей и с усовершенствованием на его базе суще - 7 ствующих алгоритмов управления, с созданием моделей обмена информацией, учитывающих особенности ИС, с разработкой на их основе новых методов управления обменом информацией.
Основной целью диссертационной работы является разработка моделей обмена информацией в ИС, ориентированных на использование в ЙАСУ, исследование эффективности методов управления обменом информацией в ИС, разработка и исследование алгоритмов маршрутизации и ограничения интенсивности потоков.
В соответствии с этой целью в диссертационной работе поставлены и решены следующие задачи.
1. Построение обобщенной модели обмена информацией в ИС, на базе которой строятся частные модели для оценки показателей качества передачи информации в ИС с фиксированной и адаптивной маршрутизацией.
2. Разработка аналитических моделей обмена информацией в ИС с фиксированной и адаптивной маршрутизацией, оценка с использованием разработанных моделей показателей качества передачи информации в ИС.
3. Разработка метода и алгоритмов выделения зон управления в ИС, позволяющих решить задачу управления обменом информацией
в сетях большой размерности, а также метода и алгоритмов адаптивной внутризоновой маршрутизации и алгоритмов ограничения интенсивности потоков, обеспечивающих эффективное управление обменом информацией в зонах различной топологической структуры.
4. Использование результатов, полученных в диссертационной
работе, при создании Единой информационно-вычислительной сети
коллективного пользования, разрабатываемой во Всесоюзном научно исследовательском институте электроизмерительных прибороЕ, и интегральных цифровых сетей связи с коммутацией пакетов, разрабатываемых в ЛНПО "Красная Заря".
Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений.
В первой главе рассматриваются особенности информационных потоков, топологической структуры и технических средств ЙС, определяются задачи системы управления интегральной сетью, формулируются особенности управления обменом информацией. Проводится обзор состояния задачи управления обменом информацией и приводится классификация методов управления обменом информацией, на основании которых делаются выводы об актуальности разработки моделей и алгоритмов управления обменом информацией для ИС, а также о том, что управление обменом должно быть адаптивным и что метод управления должен сочетать в себе методы маршрутизации и ограничения интенсивности информационных потоков. Дается общая постановка задачи системного проектирования ИС, выделяются частные задачи проектирования и предлагается методика системного проектирования ЙС, предусматривающая итерационное решение частных задач на каждом из топологических уровней сети. В рамках методики формулируется задача выбора методов и разработки алгоритмов управления обменом информацией и проводится ее декомпозиция на подзадачи выделения зон управления и построения внутризоновых алгоритмов управления.
Вторая глава посвящена разработке моделей обмена информацией в ЙС и их анализу. На основе аппарата теории множеств, теории асинхронных конечных автоматов, а также концепций архитектуры открытых систем, рекомендованной Международной организацией стандартов, предложена обобщенная модель обмена информацией в ИС, на базе которой становится возможным построить частіше модели, представляющие собой детальные описания некоторых компонентов
- 9 обобщенной модели и позволяющие оценить показатели качества передачи информации. Выбран критерий оценки эффективности алгоритмов управления обменом информацией в ИС, позволяющий в условиях гибридной и адаптивной коммутации на базе единого подхода проводить анализ различных методов маршрутизации и ограничения интенсивности потоков и учитывающий как производительность сети, так и показатели качества передачи информации. На основе обобщенной модели разработана аналитическая модель обмена информацией в ИС с фиксированной маршрутизацией, с помощью которой проводится оценка средней вероятности блокировки коммутируемой единицы информации, среднего времени задержи сообщения в сети и дисперсии времени задержки сообщения в условиях реализации в ИС методов гибридной и адаптивной коммутации. В модели использованы представление узла коммутации в виде двухфазной системы массового обслуживания (СМО) и непрерывная аппроксимация загрузки линий связи в режиме коммутации каналов. На базе понятия логической линии проведен сравнительный анализ увеличения средней вероятности блокировки коммутируемой единицы информации при использовании в ИС различных методов ограничения интенсивности потоков. Разработана аналитическая модель обмена информацией в ИС с адаптивной маршрутизацией, позволяющая оценить эффективность различных методов маршрутизации по косвенным показателям. Получены выражения для среднего времени доведения служебных сообщений и средней дополнительной задержки С за счет служебного трафика) пользовательских сообщений в симметричных сетях и в симметричных сетях с централизацией.
В третьей главе на основании анализа модели обмена информацией в ИС с адаптивной маршрутизацией делаются выводы о том, что в централизованных сетях наиболее эффективны централизованные методы маршрутизации, в распределенных - децентрализованные, при увеличении размерности сети необходимо выделение зон управления и введение зоновой рассылки служебной информации. Предлагается метод выделения зон управления в ИС, суть которого состоит Е том, что при выделении зон минимизируется суммарный вес межзоновых связей, выраженный через интенсивность транзитного трафика по каналу связи, а максимально допустимая размерность зоны управления определяется ее топологической структурой. Разработаны последовательный и итерационный алгоритмы, реализующие предложенный метод выделения зон управления; показано, что лучшие результаты получаются при использовании итерационного алгоритма. На основе анализа моделей, построенных в главе 2, предложен метод адаптивной внутризоновой маршрутизации с гарантированными показателями качества путей передачи. Суть метода состоит в том, что коммутируемые единицы информации направляются по путям, имеющим гарантированные показатели качества передачи и максимизирующим производительность ИС. Разработаны алгоритмы, реализующие предложенный метод маршрутизации, и алгоритмы ограничения интенсивности информационных потоков. Использование разработанных алгоритмов позволяет обеспечить эффективное управление обменом информацией в зонах управления различной топологической структуры с различными параметрами внутри- и межзонового трафика, каналов связи и УК.
В четвертой главе ставится задача экспериментального исследования алгоритмов управления обменом информацией в ИС. Формулируются цели экспериментального исследования, обосновывается применение языка PL/i для реализации алгоритмов имитационного исследования. На основании результатов экспериментов показано, что в большей части диапазона загрузок ИС с фиксированной маршрутизацией результаты аналитических расчетов, выполненных по формулам, полученным в главе 2, отличаются от результатов имитационного моделирования на 10 - 15%, что является вполне удовлетворительным на этапе проектирования ИС. Показано, что применение разработанных в главе 3 алгоритмов адаптивной маршрутизации и ограничения интенсивности потоков обеспечивает эффективное управление обменом информацией в ИС, повышение производительности сети по сравнению с методом фиксированной маршрутизации составляет в среднем 12 - 17%.
Исследования и разработки, выполненные в диссертационной работе, внедрены при создании Единой информационно-вычислительной сети коллективного пользования ВНИИЭП. Кроме того, основные результаты, полученные в работе, нашли применение в научно-исследовательских работах кафедры Автоматизированных систем обработки информации и управления ЛЭТИ им. В.И.Ульянова Стенина; и внедрены в ЛНПО "Красная Заря" при создании интегральных цифровых сетей связи с коммутацией пакетов.
Автор считает своим приятным долгом выразить глубокую благодарность за советы и замечания, высказанные при обсуждении диссертационной работы, своему научному руководителю д.т.н. профессору Советову Б.Я., а также к.т.н. доценту кафедры Автоматизированных систем обработки информации и управления Яковлеву С.А.
Характеристика информационных потоков и технических средств ИС, особенности управления обменом информацией
Интегрированная АСУ представляет собой сложную человеко-машинную систему, в которой сочетаются машинная обработка информации и автоматизация принятия решений с деятельностью человека, выступающего в роли оператора, руководителя, экспертаЫ. Под ИС ИАСУ будем понимать систему, которая объединяет многочисленных пользователей ИАСУ и обеспечивает передачу разнообразной информации между этими пользователями в единой цифровой форме. В качестве пользователя может выступать и ЭВМ, осуществляющая обработку информации.
Основной целью создания и задачей функционирования ИС является автоматическая доставка информации пользователю і иногда с обработкой) в соответствии с заданными показателями качества. Интегральная сеть должна быть построена таким образом, чтобы каждому пользователю было гарантировано, что[8,9]: - сообщения этого пользователя будут доставлены по назначению, - время, затраченное на доставку сообщений и дисперсия (либо среднеквадратическое отклонение) времени доставки не превзойдут заранее обусловленных значений, - вероятности искажения сообщений не превзойдут допустимых. Под сообщением будем понимать [ю] конечную последовательность данных, формируемую для передачи и имеющую законченное смысловое значение (под данными здесь понимается любая цифровая последовательность, в том числе и речь в цифровой форме). Основной особенностью НС, отличающей их от существующих ЙВС, является разнообразие видов информации, передаваемой и обрабатываемой в сети в единой цифровой форме. В перспективе развития интегральных сетей это могут быть речь, оперативные и диалоговые данные, файлы данных, факсимильная информация, черно-белые и цветные телевизионные сигналы и др. Однако на начальном этапе создания ИС ввиду отсутствия соответствующей технической базы ограничимся рассмотрением четырех видов информации: речи, оперативных данных, диалоговых данных и файлов данных. Речь представляет собой поток чередующихся интервалов активностей и пауз. Основные особенности, которые необходимо учитывать при передаче речи - обеспечение малой задержки активности при задержках более 600 мс разговор сильно затрудняется из-за психологических особенностей человеческого общения; и малого среднеквадратического отклонения времени задержки активности (.этот показатель еще более важен, чем задержка, критическое значение его примерно 200 мс). В то же время из-за особенностей разговора и избыточности речь малочувствительна к шумам, допустимыми являются потери до нескольких процентов речевой информации [i i]. Оперативные данные представляют собой небольшие цифровые потоки критичные к задержкам и к шумам. Оперативные данные могут быть как пользовательскими, так и порождаться самой сетью для ее управления. Диалоговые данные включают относительно короткие сообщения с допустимыми задержками большими, чем у оперативных данных, но также критичные к шумам. Файлы данных представляют собой, длинные сообщения с большими допустимыми задержками, но требующие высокой верности передачи. Доля каждого вида информационного потока в общем потоке информации в сети и ее отдельных участках может меняться в течение Бремени и в больших пределах. Для обеспечения эффективного функционирования ИАОУ необходимо предусмотреть возможность передачи каждого из рассмотренных видов информации с различными уровнями приоритета. В качестве примера рассмотрим 3 приоритета: - абсолютный, который позволяет передавать информацию немедленно по кратчайшему пути, - высокий, назначаемый, как правило, информации, которую необходимо передавать в реальном масштабе времени. При передаче сообщения, имеющие высокий приоритет, не прерываются за исключением случая, когда они препятствуют передаче сообщений с абсолютным приоритетом, - низкий, назначаемый информации, которая может прерываться сообщениями, передаваемыми с высоким и абсолютным приоритетом. Б состав ИС входят пункты сети, каналы связи ДОв), соединяющие пункты, и система управления сетью. Под пунктами сети будем понимать: а) терминалы, представляющие собой любой источник (,прием ник) цифровой информации - цифровой телефон, абонентский пункт, аппаратуру передачи данных, ЭВМ различной производительности и назначения и др., б) концентраторы, осуществляющие преобразование сигналов терминалов в стандартную форму для передачи по базовой сети ИС (определение базовой сети будет дано ниже); в) узлы коммутации, осуществляющие распределение сообщений по каналам базовой сети, В дальнейшем будем рассматривать ИС с фиксированным расположением пунктов и КСв сети. Пункты и КСв образуют топологическую структуру МС. G точки зрения топологической структуры, параметров и принципов обмена информацией в интегральной сети можно выделить две подсети - терминальную tабонентскую) сеть и базовую (магистральную) сеть[7,12,13]. Терминальная сеть включает в себя терминалы, концентраторы, КСв, соединяющие терминалы с концентраторами и терминалы и концентраторы с УК, а также систему управления терминальной сетью. Базовая сеть включает в себя УК и КСв, их соединяющие, а также систему управления базовой сетью. В дальнейшем будем рассматривать только базовую сеть и управление обменом информацией в ней, термин ИС будем употреблять далее, подразумевая под ним именно базовую сеть. Топологическая структура базовой сети ИС представляет собой совокупность УК и каналов связи, их соединяющих. Б настоящее Еремя в базовых сетях информационно-вычислительных сетей используется ряд топологических структур, на основе которых могут быть построены интегральные сети: звездообразная, кольцевая, распределенная и т.д.[і4,І5]. С учетом большой размерности ЙС ЙАСУ наиболее целесообразными для них являются иерархические радиально-кольцевые структурьі[іб]. В этом случае топологическая структура ИС включает в себя ряд топологических уровней, каждый из которых представляет собой подсеть, построенную по своим собственным топологическим правилам l7].
Построение обобщенной модели обмена информацией в ИС
Системный подход к решению задачи управления обменом информацией в ИС требует построения наиболее общего математического описания процесса функционирования ИС, на базе которого можно будет, применив конкретные математические методы, разработать оптимальные алгоритмы управления сетью. Такое описание можно выполнить на основе теоретико-множественного подхода(89 J.
В соответствии с концепциями архитектуры открытых систем [2б] во всех уровнях каждой открытой системы ИС выделяются логические объекты, каждый из которых выполняет локальный комплекс функций, взаимосвязанных общей целью. Любой логический объект может быть охарактеризован множеством моментов времени Т , в которые рассматривается его функционирование, множеством входных сигналов X , множеством выходных сигналов V , множеством внутренних состояний Z , операторами переходов G и выходов Н . Особенностью алгоритмов управления ИС является наличие таймаутов, т.е. в некоторых внутренних состояниях рассматриваемого логического объекта в определенные моменты времени новое внутреннее состояние и выходной сигнал могут вырабатываться без поступления сигнала на вход объекта. Поэтому в число аргументов операторов G и Н должен быть введен параметр времени - t . Функционирование объекта может быть описано схемой асинхронного конечного автомата [90]: шествующий рассматриваемому (.т.е. (t-)e T&.(t-) t ).
Будем считать, что множествам X и V принадлежат и пустые сигналы - Хр и Ujt , соответственно, означающие отсутствие сигнала на входе или выходе объекта в момент времени t . Рассмотрим более подробно функциональную схему логического объекта К -го уровня 1-й открытой системы (,рис. 2.1). При этом, не снижая общности, можно считать, что на каждом уровне системы выделен единственный логический объект. Для упрощения обозначений здесь и в дальнейшем будет опускать индексы L и К , если они не являются необходимыми. Множество входных сигналов X объекта представляет собой множество векторов вида х (г) = & Таким образом, мы представили множество X в виде прямого произведения трех множеств: Х множество входных сигналов от объекта (к і) -го уровня; Х5 - множество входных сигналов от объектов к -го уровня; Хц- множество входных сигналов от объекта (К + 4)-го уровня эти сигналы для рассматриваемого объекта являются управляющими;. Аналогично представим множество выходных сигналов U в виде: U = UcxUs х U t где [/_ множество выходных сигналов в объект (-4)-VQ уровня ;для объекта (к- )-?о уровня эти сигналы ЯЕЛЯЮТСЯ управляющими;; U& - множество выходных сигналов в объекты К-го уровня; Щ - множество выходных сигналов Рассмотрим теперь более подробно состав множеств входных и выходных сигналов. В соответствии с моделью архитектуры открытых систем обмен информацией между логическими объектами одного уровня осуществляется с помощью протокольных блоков данных, а между логическими объектами соседних уровней - с помощью интерфейсных блоков данных. Обозначим Y - множество протокольных блоков данных К-го уровня: Y VXsL- У sc . Улементы множест-ва I представляют собой векторы: ys(} aif- Qej,t) , где j. -идентификатор типа блока, &І - &е-, - параметры смогут отсутствовать), 7Г - текст. В отличие от параметров конкретные значения текста для объекта К-го уровня не имеют значения, принимается во внимание лишь ряд ограничений (.длина и т.п.). Идентификатор, параметры и текст могут быть представлены в виде двоичных векторов. Таким образом где J, -ЯІ, .... , Mej , Т - области определения для соответствующих элементов вектора У . В качестве примера может быть рассмотрено множество пакетов в протоколе сетевого уровня ИС, построенном на базе стандартного протокола Х.25/з[9Ґ]. В этом случае элементами вектора у являются: \- идентификатор типа пакета, а - главный идентификатор формата, 2- номер группы логических каналов, j -номер логического канала и т.д. Обозначим К Х К - Сі - множество интерфейсных блоков данных, направляемых от уровня К к уровню (К + 4) ; п - ,,ттск HViK) множество интерфейсных блоков данных, направляемых от уровня ( + / к уровню К , Элементы с и с имеют структуру, аналогичную структуре элементов у , т.е. Элемент множества внутренних состояний 2 представляет собой вектор ї- ( tt,- ,dL), где с/ - с/ , -параметры состояния объекта, каждый из которых может быть представлен в виде двоичного вектора. На основе выражений (2.1) можно вывести соотношения, описывающие алгоритм функционирования отдельных открытых систем ИС или групп таких систем на основе известных алгоритмов функционирования составляющих их логических объектов. Рассмотрим подсистему, объединяющую объекты канального и физического уровней УК ИС (рис.2.2). В данном случае - v ие и V\n - л е. . Множество входных сигналов этой подсистемы состоит из: Xt, - множество управляющих блоков от сетевого уровня; As - множество олоков данных, поступающих от объектов уровня 2 (по установившейся терминологии эти блоки называются кадрами); Xs - множество блоков данных, поступающих от объектов уровня I , например, циклов системы ИКМ-30.
Разработка метода и алгоритмов адаптивной внутризоновой маршрутизации с гарантированными показателями качества путей передачи
К достоинствам последовательного алгоритма относится его простота, за счет которой можно получить результат при небольших затратах машинного времени, однако в общем случае данный алгоритм может привести к неоптимальным результатам. Лучшие результаты могут быть получены при разбиении сети на зоны с использованием итерационных алгоритмов [из]. Суть их состоит в том, что сначала находится (например с помощью описанного выше алгоритма) некоторое исходное разбиение графа G = ! » /, G ej. Затем вычисляется величина, на которую изменится вес разбиения V" при обмене вершинами (или группами вершин) между двумя под-графами i и «j . Если вес разбиения уменьшится, то вершины (группы вершин) меняются местами. Процесс продолжается до тех пор, пока не будут выполнены все возможные перестановки. В алгоритме, разработанном в данном параграфе, производится обмен единичными вершинами.
Основная идея разработанного метода маршрутизации состоит в том, что коммутируемые единицы информации направляются по путям, имеющим гарантированные показатели качества передачи %i %i и максимизирующим производительность сети, выраженную через среднюю вероятность блокировки коммутируемой единицы информации. Реализация метода в ИС возможна благодаря применению высокоскоростных цифровых каналов связи и многопроцессорных специализированных УК, построенных на базе микропроцессорной техники, за счет чего становится возможным получить достаточно высокое качество передачи информации (, 2.3). Вычисление значе-ний г и уі в реальной сети производится на основе их оценок, получаемых в каждом УК для каждого исходящего направления. Оценки, в свою очередь, могут быть рассчитаны, например, усреднением соответствующих показателей по всем коммутируемым единицам информации, обработанным в УК в течение некоторого временного интервала.
С целью повышения производительности сети метод маршрутизации должен допускать ряд градаций качества передачи, т.е. в нагруженной сети может допускаться менее качественная передача информации, чем при работе сети в условиях малой загрузки. Представляется целесообразным ограничиться тремя градациями для показателей і в зависимости от потери ценности информации при передаче через РІС Назовем режим работы сети, при котором обеспечивается удовлетворение условий yiyi для информации всех видов, ре жимом работы с малой загрузкой, а режим работы сети, при КОТО хотя бы для некоторых видов информации, режимом работы с большой загрузкой. Выбор маршрута для коммутируемой единицы информации в УК производится в соответствии с маршрутной таблицей QМТ) Корректировка маршрутных таблиц при использовании предлагаемого метода маршрутизации осуществляется в несколько этапов рис. 3.6). I. Определяется режим работы сети. Если 0 F pd счи_ таем, что сеть работает с малой загрузкой и переходит к п. 2. Если пс Р , считаем, что сеть работает с большой загрузкой и переходим к п. 3. Здесь Р обозначена оценка средней вероятности блокировки коммутируемой единицы информации. в перестановке групп вершин. Тексты программ на языке ФОРТРАН-ІУ, реализующих разработанные алгоритмы, приведены в приложении 2. Исследование алгоритмов было проведено на ряде топологических структур сетей, сгенерированных случайным образом. Результаты исследования в зависимости от числа узлов в сети М и средней связности сети = М /М , где М - число КСв, приведены на рис. 3.2 - 3.4-, На рисунках обозначены: I - зависимости веса разбиения от числа узлов в сети при распределении узлов по зонам случайным образом: П - зависимости, соответствующие последовательному алгоритму разбиения; Ш - зависимости, соответствующие итерационному алгоритму разбиения. На рис. 3.5 приведены зависимости относительного уменьшения веса разбиения при использовании разработанных алгоритмов от числа узлов сети. Значение -А вычисляется по формуле, Д -(VC-VL)/ Vc , где V"c - вес разбиения при случайном распределении узлов по зонам, V - вес разбиения при использовании одного из алгоритмов разбиения (последовательного).
Разработка алгоритмов машинной имитации обмена информацией в ИС
Эти алгоритмы достаточно универсальны и хорошо исследованы, например в работахJII9, I20], поэтому в данном параграфе будут разработаны лишь алгоритмы ограничения интенсивности информационных потоков при доступе к ИС. При этом, учитывая многоуровневый характер управления обменом информацией в ИС ограничение интенсивности потоков может выполняться при доступе к УК зоны К -го уровня со стороны УК зон (к ) -го или (к ) -го уровня (ограничение интенсивности потока при доступе к зоне К -го уровня - 0ИДЗх ) и при доступе к УК зоны К -го уровня со стороны УК этой же зоны (ограничение интенсивности при доступе к УК - 0ЙДУКк ). Последовательность выполнения алгоритмов ограничения интенсивности потока при обмене информацией менду УК і- и УК показана на рис. 3.9.
Анализ зависимостей О, - К // г с) при различных методах ограничения интенсивности потоков ( 2.3) показывает, что при больших значениях интенсивности потока сообщений, поступающих в логическую линию, лучшие результаты (меньшие значения величины перегрузки линии CL ) получаются при использовании локальных методов управления. Кроме того, локальное управление позволяет контролировать большее число параметров логической линии. В связи с этим в данном параграфе рассмотрены вопросы разработки алгоритмов локального управления.
Рассмотрим конкретный реализованный в ИС режим коммутации. Разделим весь поток коммутируемых единиц информации, поступающих УК, на классы следующим образом: класс "I" (с=/ ) присвоим коммутируемым единицам информации, поступающим в ИС в данном УК; класс "2" (С=.2 ) присвоим транзитным коммутируемым единицам информации, требующим передачи в УК зоны управления вышестоящего уровня; класс "3" (С-з ) присвоим транзитным коммутируемым единицам информации, которые необходимо передать в УК той не зоны управления, где находится данный УК; класс "4" (С-4 ) присвоим коммутируемым единицам информации, которые необходимо передать в УК зоны управления нижестоящего уровня,
Разработанные в данном параграфе алгоритмы ограничения интенсивности потоков основаны на таком выделении буферов в УК, при котором наибольший приоритет отдается трафику более высоких классов, что при большой загрузке сети позволяет обслужить в первую очередь коммутируемые единицы информации уже занявшие ресурсы ИС. Под буфером здесь понимается для режима КК номер канального временного интервала, выделенного для установления соединения, для режима ВК - блок памяти УК, предназначенный для хранения пакетов "Данные" виртуального соединения в пределах величины окна[91], для режима ДГ (КС) - блок памяти УК, предназначенный для хранения дейтаграммы (сообщения).
Обозначим ьх - допустимое (пороговое) число буферов, которое могут занять в данном УК коммутируемые единицы информации класса с , предназначенные для передачи по исходящей линии К. Учитывая вышеописанный принцип выделения буферов, име-ет место неравенство иК ик L н 1-к.
Ниже приводится описание алгоритма ограничения интенсивности потока, подобного традиционным для базовых сетей ИБО алгоритмам, ограничивающим ввод собственных пакетов УК в сеть при превышении загрузки памяти УК выше некоторого порога. Алгоритм может использоваться в любом реализованном з ИС режиме коммутации и состоит из следующих шагов. I. Определить класс коммутируемой единицы информации С. 2. Выбрать исходящую линию К в соответствии с маршрутной таблицей. 3. Если число коммутируемых единиц информации в буфере ли-нии к - ск меньше порога: z к -ь к , то коммутируемая единица информации принимается к обслуживанию, т.е. за ней закрепляется соответствующий буфер. Если условие Ск LK не выполняется, то коммутируемая единица информации получает отказ в обслуживании. Данный алгоритм достаточно прост в реализации, однако в определенных условиях работы сети, например, при быстром нарастании интенсивности потока коммутируемых единиц информации высших классов в данном УК, ограничений, введенных им, может оказаться недостаточно. С целью более быстрого и эффективного ограничения интенсив-ностей потоков Е ИС разработан более сложный алгоритм с обменом информацией о перегрузке между смежными УК. Основная идея алгоритма состоит в том, что при достижении числом собственных коммутируемых единиц информации в буфере линии К УК і порогового значения L к. і всем соседним УК J , связанным с УК каналами, передается сообщение о блокировке УК - СБЛЦ і ). После чего в УК собственные коммутируемые единицы информации, которые должны были направляться в УК I, блокируются {либо направляются по обходному пути). При уменьшении величины ьк ниже порогового значения Есем УКj передаются сообщения о снятии блокировки УК -КБЖ(, I ). Алгоритм состоит из двух частей. При поступлении в УК коммутируемой единицы информации выполняются следующие действия. 1. Определяется класс коммутируемой единицы информации с. 2. Выбирается исходящая линия К в соответствии с маршрут- ном таблицей. 3. Если поступила собственная коммутируемая единица информации, т.е. с-/ , то перейти к п. 5, иначе перейти к п. 4. 4. Если число коммутируемых единиц информации в буфере линии К не больше порога к , то перейти к п. 6, иначе перейти к п. 9. 5. Если tK LK и линия К не блокирована, то перейти к п. б, иначе перейти к п. 9. 6. Принять коммутируемую единицу информации к обслуживанию. 7. Увеличить счетчик числа коммутируемых единиц информации в буфере линии К на единицу: ц ск . 8. Если линия К блокирована, то закончить; если нет, то послать сообщение о блокировке СБЛК ( і ) и закончить. 9. Блокировать коммутируемую единицу информации и закончить. По окончании обслуживания в УК і коммутируемой единицы ин формации выполняются следующие действия.
