Анализ и синтез сетей ЭВМ автоматизированных систем массового обслуживания (на примере общесоюзной системы бронирования авиабилетов)

• Автор: Талалай, Алексей Исаакович
• Шифр специальности: 05.13.06, 05.13.13
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Москва
• Количество страниц: 162 c. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
Глава I. РАЗРАБОТКА МЕТОДА СИНТЕЗА СТРУКТУРЫ СЕТИ ЭШ. РЕШЕНИЕ ЗАДАЧИ ВЫБОРА ТОПОЛОГИИ,
ПРОПУСКНЫХ СПОСОБНОСТЕЙ И РАСПРЕДЕЛЕНИЯ ПОТОКОВ ДЛЯ СЕТЕЙ ЭШ 1.1. Обзор методов синтеза структуры сетей ЭШ
1.2. Формулировка задачи синтеза структуры сети ЭШ автоматизированной системы массового обслуживания.

Учт требований к двусвязности сети

1.3. Понижение размерности задачи линейного программирования. Переход к задаче частично целочисленного программирования
1.4. Оптимизация распределения потоков информации на сети минимальной стоимости по критерию использования кратчайших маршрутов передачи информации .

1.5. Эвристический подход к синтезу

структуры сетей ЭШ автоматизированных систем массового обслуживания

большой размерности .

Выводы по I главе
Стр.
Глава 2. УПРАВЛЕНИЕ ПОТОКАМИ ПАКЕТОВ В СЕТИ ЭШ
И РАЗРАБОТКА МЕТОДА АНАЛИЗА ХАРАКТЕРИСТИК СЕТИ И АЛГОРИТМА ВЫБОРА ПАРАМЕТРОВ УПРАВЛЕНИЯ
2.1. Использование для моделирования и анализа сетей ЭШ методов теории
сетей массового обслуживания.
2.2. Метода расчта сетей массового обслуживания
2.3. Управление потоками в сетях ЭШ и
модели сетей
2.4. Модель сети ЭШ с межконцевым механизмом управления потоками пакетов 2.5. Метод анализа характеристик сети ЭШ
с виртуальными каналами
2.6. Эвристический алгоритм оптшизации параметров межконцевого механизма
управления потоками в сети ЭШ
Вывода по 2 главе .
Глава 3. ПРАКТИЧЕСКОЕ ПРШЕНЕНИЕ РАЗРАБОТАННЫХ МЕТО
ДОВ ДЕЯ ПРОЕКТИРОВАНИЯ СЕТИ ЭШ ОБЩЕСОЮЗНОЙ СИСТЕМЫ БРОНИРОВАНИЯ АВИАБИЛЕТОВ СИРЕНА2. ВЫБОР ПАРАМЕТРОВ УПРАВЛЕНИЯ ПОТОКАМИ ДЛЯ СЕТИ ЭШ ФРАГМЕНТА АСУ СИРЕНА2 И АНАЛИЗ ХАРАКТЕРИСТИК СЕТИ
3.1. Исходные данные для проектирования
сети ЭШ для системы Сирена2
3.2. Выбор топологической структуры, пропускных способностей и распределение потоков информации для сети ЭШ АСУ
Сирена2 .
3.3. Расчт параметров управления потоками и анализ характеристик сети ЭШ фрагмента АСУ Сирена1
3.4. Имитационное моделирование сети ЭШ
фрагмента АСУ Сирена2.
Выводы по 3 главе .
Глава 4. ПАКЕТ ПРОГРАММ ДЕЯ ПРОЕКТИРОВАНИЯ СЕТИ ЭШ АВТОМАТИЗИРОВАННЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
4.1. Описание пакета программ для проектирования сетей ЭШ автоматизированных
систем массового обслуживания.
4.2. Взаимодействие программ пакета
4.3. Процедура проектирования сети ЭШ
автоматизированной системы массового
обслуживания
Выводы по 4 главе .
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Для отыскания решений задачи РП в сетях с коммутацией пакетов применяются известные алгоритмы выбора путей с наименьшим числом промежуточных узлов , алгоритм девиации потока , алгоритм основанный на декомпозиции транспортной задачи , позволяющий минимизировать среднее время доставки пакета по сети. Для нахождения топологии сети минимальной стоимости известна 5 формулировка задачи ВТПСИ1 в терминах задачи целочисленного линейного программирования, в которой предполагается фиксированная маршрутизация. Чу, О
ти. Наличие большого числа целочисленных переменных вида ,
связи с этим в 5 указана возможность понижения размерности задачи если имеется априорная информация о запрете на использование маршрутами определенных линий связи. Огромные вычислительные трудности точного решения даже частных случаев задачи ВШСРП и невозможность точного решения в общем виде задачи ВТПСРП вынуждают использовать при проектировании сетей связи ЭШ эвристические алгоритмы, позволяющие находить решения близкие к оптимальным. Широкое распространение получил метод вариации ветвей . В основе алгоритма лежит процесс локальных трансформаций, заключающийся в исключениях и добавлениях линий с целью отыскания более предпочтительной топологии. Недостатком метода вариации ветвей является то, что ветви выбираются вообще говоря случайно. Для более эффективного выбора ветвей, предназначенных для исключения или добавления был предложен метод насыщенных сечений . Изучение метода на различных примерах показало , что метод насыщенных сечений позволяет отыскивать решения со значением целевой функции, лучшим чем для решения найденного методом вариации ветвей, а также, что он более эффективен в вычислительном отношении. Важную роль в алгоритме насыщенных сечений играет алгоритм маршрутизации потоков. При маршрутизации потоков,если уровень трафика, который требуется передать, превышает пропускную способность линий сечения, то требуется либо увеличить пропускную способность линий в сечении, либо добавить линии к сечению. Наиболее эффективная линия, добавляемая к сечению определяется различными способами, в том числе методом, получившим название выбор с расстоянием два. Суть метода в выборе линии, для соединения двух узлов, относящихся к разным компонентам сечения и отстоящих от множества линий сечения на расстоянии не менее двух линий. Этот метод позволяет избежать
незначительных улучшений и соединить центры трафика двух компонент сечения. В алгоритме насыщенных сечений производительность сети удерживается в заданных пределах, в то время как значение целевой функции улучшается при выполнении ограничений, предъявляемых сети. Следует отметить, что результат полученный как методом вариации ветвей, так и методом насыщенных сечений зависит от топологической структуры, выбранной в качестве исходной. Выбор в качестве исходной структуры полносвязного графа, как рекомендуется, например, в может сильно увеличить время, необходимое для поиска решения задачи ВТПСРП. Поэтому появились методы проектирования сетей ЭШ, выбирающие в качестве исходной достаточно хорошую структуру сети ЭШ, что дат определенный выигрыш во времени, необходимом для решения задачи на ЭШ. Существуют алгоритмы, учитывающие вид стоимостной функции линий связи, например, вогнутый метод устранения ребер , , решающий задачу ВТПСРП итеративно решая задачи ЕПСРП. Метод ограничен возможностями подходящей аппроксимации стоимостной функции. В последнее время появились алгоритмы синтеза топологии вычислительных сетей, основанные на методе размытых эвристик , применяемые как для локальной оптимизации вычислительных сетей 1, так и для решения общей задачи синтеза топологии вычислительных сетей 2, 3 и дающие возможность находить решения, удовлетворяющие одновременно различным критериям. Следует отметить, что указанные методы не учитывают прямо такие важные факторы, как стохастичность процесса передачи информации, наличие механизмов управления потоками пакетов или сообщений. Эти факторы учитываются только косвенно, использованием соответственно выбранной эффективной пропускной способности линий связи.