Методы управления трафиком в наземно-воздушных сетях связи тема диссертации и автореферата по ВАК РФ 05.13.01, доктор технических наук Войткевич, Константин Леонидович

• Войткевич, Константин Леонидович
• доктор технических наук
• 1998

Оглавление диссертации доктор технических наук Войткевич, Константин Леонидович

Введение

1. Наземно-воздушные сети и методы управления трафиком.

1.1. Архитектура служб ATM, параметры трафика и качества обслуживания.

1.2. Управление потоками и контроль перегрузок в АТМ-сетях.

1.2.1. Функции управления потоком и контроля перегрузок.

1.2.2. Общая характеристика схем и протоколов, реализующих функции управления потоком и контроля перегрузкой.

1.3. Методы маршрутизации виртуальных соединений.

1.4. Управление ABR - трафиком.

1.4.1. Параметры ABR службы.

1.4.2. Обзор методов управления перегрузками ABR-трафика.

1.4.2.1. Протокол быстрого резервирования.

1.4.2.2. Протокол управления скоростью на основе измерения задержки.

1.4.2.3. Обратное точное уведомление о перегрузке.

1.4.2.4. Ранний отброс пакетов.

1.4.2.5. Схемы, основанные на методе кредитов.

1.4.2.6. Схемы, основанные на управлении скоростью.

1.5. Методы управления трафиком в воздушной сети. 74 Выводы.

2. Оптимальная маршрутизация CBR соединений. 87 2.1. Цели алгоритмов маршрутизации. Последовательная, глобальная маршрутизация и их взаимосвязь. 89 2.2: Критерии оптимизации. 91 2.3. Алгоритм последовательной маршрутизации.

2.3.1. Алгоритмы поиска кратчайших путей.

2.3.1.1. Алгоритм Дийкстры.

2.3.1.2. Алгоритм Беллмана-Форда.

2.3.1.3. Алгоритм Флойда.

2.3.1.4. Алгоритм Велмана-Шимбела.

2.3.1.5. Алгоритм Филлера.

2.3.1.6. Модификации алгоритма Дийкстры.

2.3.2. Максминные и минмаксные пути.

2.3.2.1. Модифицированный алгоритм Дийкстры. Минмаксный вариант.

2.3.2.2. Модифицированный алгоритм Дийкстры. Максминный вариант.

2.3.3. Алгоритм с минимальной вероятностью отказа для следующего требования.

2.3.3.1. Постановка задачи.

2.3.3.2. Описание алгоритма.

2.3.3.3. Численный пример.

2.3.4. Алгоритмы выбора пути минимальной стоимости.

2.3.5. Алгоритм минимального приращения стоимости.

2.4. Имитационная модель алгоритмов последовательной маршрутизации. Сравнительный анализ.

2.4.1. Описание алгоритма имитационной модели.

2.4.2. Оценка точности результатов моделирования.

2.4.3. Результаты моделирования последовательной маршрутизации.

2.5. Глобальная маршрутизация.

2.5.1. Краткий обзор современных методов и перспективных подходов в комбинаторной и целочисленной оптимизации.

2.5.2. Алгоритмы нахождения первоначального допустимого решения.

2.5.2.1. «Жадный алгоритм».

2.5.2.2. Итерационный алгоритм Мину.

2.5.3. Алгоритмы глобальной оптимизации.

2.5.3.1. Метод релаксации Лагранжа.

2.5.3.1.1. Субградиентный метод.

2.5.3.1.2. Метод генерации столбцов.

2.5.3.2. Метод переброса потока (МПП).

2.5.3.2.1. Математическая постановка задачи.

2.5.3.2.2. Алгоритм первоначального распределения (АПРМПП).

2.5.3.2.3. Алгоритм варьирования путей (АВПМПП).

2.5.3.3. Алгоритм с минимальным числом «прыжков».

2.5.3.4. Метод вектора спада. (

2.5.3.4.1. Формальное описание алгоритма.

2.5.3.4.2. МВС применительно к задаче глобальной маршрутизации.

2.5.3.5. Алгоритм локального поиска.

2.5.4. Нижние границы целевой функции.

2.5.4.1. Алгоритм вычисления нижней границы для минмаксного критерия методом субградиента.

2.5.4.2. Алгоритм вычисления нижней границы для стоимостного критерия.

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

2.5.5.1. Пошаговое описание алгоритма.

2.5.5.2. Численные результаты.

2.6. Экспериментальные результаты исследования глобальной маршрутизации.

2.6.1. Сравнительный анализ критериев глобальной оптимальной маршрутизации.

2.6.2. Экспериментальные результаты с использованием МПП. 196 2.6.2.1. Оценка сложности и быстродействия МПП.

2.6.3. Экспериментальные результаты с использованием МВС.

2.6.4. Исследование взаимосвязи критериев оптимальной глобальной маршрутизации с вероятностью отказа в соединении.

2.6.4.1. Критерий «максимального порога».

2.6.4.2. Сравнительный анализ критериев «максимального порога»~и «минимальной стоимости».

2.7. Моделирование комбинированного применения методов последовательной маршрутизации и глобальной оптимизации. 235 2.7.1. Экспериментальные результаты.

2.8. Схема реализации централизованной адаптивной маршрутизации. 249 Выводы.

3. Модели систем управления перегрузкой АВЛ трафика с использованием схем регулирования с обратной связью.

3.1. Модель сети.

3.2. Характеристики системы управления перегрузкой с контролем длины очереди при скачкообразном изменении скорости возмущающего трафика.

3.2.1. Релейный закон изменения скорости источника.

3.2.2. Предиктор Смита.

3.3. Характеристики системы управления перегрузкой при линейном изменении скорости возмущающего трафика.

3.4. Управление перегрузкой с использованием комбинированной схемы регулирования скорости с прямой,и обратной связями.

3.5. Характеристики системы управления перегрузкой с контролем скорости. ! 294 Выводы.

4. Управление трафиком в авиационных радиосетях.

4.1. Марковская модель многоканальной системы с синхронным множественным доступом. 305 4.1.1. Стационарные характеристики.

4.2. Методы случайного распределения потоков в радиосетях с параллельными каналами.

4.2.1. Постановка задачи оптимального случайного распределения потоков в многоканальной системе.

4.2.2. Распределение потоков в однородной системе.

4.2.3. Распределение потока по неоднородным каналам.

4.3. Методы случайного распределения информационных потоков в каналах «земля-воздух».

4.4. Методы детерминированного распределения информационных потоков. 338 Выводы.

Введение диссертации (часть автореферата) на тему «Методы управления трафиком в наземно-воздушных сетях связи»

Актуальность темы.

Создание высокоэффективной коммуникационной среды является важнейшей национальной проблемой /1, 129/. Без ее решения невозможно построение информационного общества и внедрение в сферы производства, бизнеса, науки, обороны, образования новейших информационных технологий.

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

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

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

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

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

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

Сеть наземной связи строится как базовая сеть в интересах обеспечения обмена информацией многих ведомств. В настоящее время прослеживается четко выраженная тенденция создания интегрированных сетей связи, где под интеграцией понимается не только ведомственная принадлежность, а главным образом интеграция служб. Сети с интеграцией служб (ISDN) прошли два этапа своего эволюционного развития. На первом этапе развивались узкополосные сети (N-ISDN) с предоставлением абоненту цифровых трактов (2B+D) или (23B+D) со скоростью соответственно 144 Кбит/сек и 1.488 Мбит/сек. В настоящее время идет второй этап, на котором внедряются широкополосные сети с интеграцией услуг (B-ISDN). Развитие современных сетевых технологий, успехи в создании волоконно-оптических линий связи и сверхбольших интегральных схем привели к появлению нового типа транспортировки информации - асинхронного режима переноса (Asynchronous Transfer Mode - ATM). Технология ATM обеспечивает транспортировку всех видов информации в виде пакетов фиксированной длины - ячеек (cell), выделение пользователю необходимого ему ресурса по его требованию, поддержку интерактивных служб, передачу как непрерывного, так и пачечного трафика. Большинство ведущих фирм мира прекращает работы по узкополосным цифровым сетям интегрального обслуживания и сосредотачивает основные усилия на разработке аппаратуры ATM.

Обеспечение требуемого качества обслуживания (QoS) для различных типов трафика a ATM сетях является сложной задачей. Управление трафиком обеспечивает эффективное функционирование сети. Работа по управлению трафиком в ATM сетях в настоящее время интенсивно ведется в рамках нескольких международных организациях, наиболее представительной из которых является ATM Forum.

В соответствии с рекомендациями ATM Forum выделено 5 сервисных категорий трафика, определены их параметры и требования по качеству обслуживания. Наиболее важной является сервисная категория с постоянной битовой скоростью (Constant Bit Rate - CBR). Эта сервисная категория охватывает более 90% всей передаваемой в настоящее время информации и в рамках этой категории могут передаваться остальные 4 сервисные категории. Таким образом управление CBR трафиком сегодня является наиболее актуальной задачей для ATM сетей. ATM сети ориентированы на соединения. Два абонента сети могут начать передачу информации только после того, как они «проинформируют» все промежуточные узлы о своих требованиях по качеству обслуживания и параметрах трафика. Эта процедура аналогична процедуре установления соединения в телефонной сети, однако в ATM сети такое соединение называется виртуальным. Пользователь «заявляет» свои требования по качеству обслуживания и параметры трафика во время установления соединения. Если сеть в состоянии удовлетворить эти требования, она организует соединение и в процессе передачи информации контролирует параметры трафика, чтобы они соответствовали заявленным. Для CBR-соединений пользователь заявляет только один параметр - пиковую скорость (peak cell rate - PCR). Если сеть в состоянии организовать виртуальный канал с требуемой PCR, то соединение организуется, в противном случае требование получает отказ. Важнейшей функцией, выполняемой сетью в процессе организации соединения является поиск маршрута в сети. Вероятность блокировки вызова определяется используемым методом маршрутизации. Одной из задач данного диссертационного исследования является разработка эффективных методов маршрутизации CBR-соединений.

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

В этой связи возникает новая задача контроля перегрузок АВЯ трафика, которая сводится к динамическому перераспределению ресурса сети между пользователями и методам управления скоростью источников.

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

1) Выбор и анализ критериев оптимальной многоскоростной адаптивной маршрутизации СВЯ-соединений.

2) Разработка оптимальных и квазиоптимальных алгоритмов многоскоростной централизованной маршрутизации.

3) Оценка эффективности разработанных алгоритмов и формулировка предложений по их реализации в сетях связи.

4) Разработка методов управления АВЯ-трафика на основе динамических моделей с обратной связью.

5) Выбор и оценка параметров качества управления динамическими системами с запаздыванием.

6) Разработка эффективных комбинированных протоколов множественного доступа с целью управления трафиком в каналах «воздух-земля».

7) Разработка и исследование оптимальных методов использования пространственно-частотно-временного ресурса наземных радиоцентров при передаче информации в направлении «земля-воздух».

Методы исследования.

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

Научная новизна.

Научная новизна работы нашла выражение в следующих полученных результатах:

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

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

3) Поставлены и сформулированы задачи оптимального «глобального» распределения CBR-требований с произвольными величинами PCR в ATM сети по трем критериям оптимальности: критерию минимальной «стоимости», критерию максимума оставшейся пропускной способности линии, критерию минимума максимальной загрузки линии.

4) Получены точные и эвристические алгоритмы решения задачи оптимального «глобального» распределения CBR-требований, гарантирующие нахождение локального оптимума за время на 2-3 порядка меньше, чем известные алгоритмы дискретной оптимизации.

5) Разработана методика оценки нижних границ для задач оптимального распределения потоков на основе двойственной задачи.

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

7) Разработаны модели динамических систем управления перегрузкой АВЯ-трафика, позволяющие рассчитывать вероятности потерь ячеек при различных изменениях возмущающего трафика для разных типов регуляторов.

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

9) Разработан метод оптимального использования частотно-пространственно-временного ресурса передающих радиоцентров при управлении воздушными объектами.

Практическая значимость работы.

Основные научные выводы и рекомендации работы имеют важное практическое значение при проектировании и эксплуатации наземно-воздушных систем связи.

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

- разработке автоматизированной системы связи с самолетами гражданской авиации (ОКР «Аэрофлот»), бортовых и наземных комплексов связи (ОКР «Цифра-ГА»);

- разработке и государственных испытаниях методов управления информационными потоками в автоматизированной системе связи (ОКР «38» - заместитель главного конструктора);

- создании и государственных испытаниях системы мобильных командных пунктов (ОКР «65с28» - заместитель главного конструктора);

- разработке сети передачи данных ведомственной принадлежности и методов управления трафиком (ОКР «Лазурь» - главный конструктор);

- разработке, создании и испытании образца системы привязки подвижных объектов к наземным сетям связи и управления (ОКР «Взгляд-НПП-НН» - главный конструктор);

- разработка системного проекта по развитию ведомственной АСУ и связи (шифр «Синтез» - заместитель главного конструктора);

Кроме того, автор являлся руководителем совместного российско-французского научного проекта (корпорация Thomson-CSF) по методам управления трафика и контроля перегрузок в ATM сетях, а также ряда НИР, выполненных в НЛП «Полет» по техническим заданиям заказчиков различных ведомств.

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

Апробация работы.

Основные результаты работы докладывались и обсуждались на Всероссийских научно-технических конференциях:

НПП «Полет» Н.Новгород, 1994 г.

Военйая академия связи, С.Петербург, 1997 г.

ЛНПО «Красная Заря», г.Ленинград, 1986 г.

ВНИИС, г.Воронеж, 1996 г.

Нижегородский государственный технический университет, г.Н.Новгород, 1997, 1998 гг.

Нижегородский государственный университет, г.Н.Новгород, 1994 г. а также международных НТК:

Нечеткая логика, интеллектуальные системы и технологии», г.Владимир, 1997 г.

Радиолокация, навигация, связь», г.Воронеж, 1998 г.

Публикации.

По основным материалам диссертации опубликовано 58 научных работ. Кроме того, некоторые результаты и выводы диссертационной работы вошли в конспект лекций по математическим методам исследования сетей связи и управления трафиком, читаемыми автором на факультете вычислительной математики и кибернетики Нижегородского государственного университета (кафедра «Теория управления») и факультете информационных систем и технологий Нижегородского государственного технического университета (кафедра «Теория телекоммуникаций»).

Структура и объем работы.

Диссертация состоит из введения, четырех глав, заключения, списка литературы и 2 приложений. Диссертация содержит 371 страницу, из них 91 страница рисунки и таблицы. Список литературы насчитывает 140 наименований.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Войткевич, Константин Леонидович

Выводы.

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

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

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

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

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

5. Поставлена задача оптимального случайного распределения потоков в каналах с упорядоченным доступом (каналы «земля-воздух»). В качестве целевой функции используется вероятность своевременной доставки, либо среднее время доставки пакета. Задача сформулирована в виде задачи нелинейного программирования.

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

6. Разработаны методы детерминированного распределения информационных потоков в авиационных радиосетях. Методы основаны на решении сформулированных задач нелинейного программирования методом «ветвей и границ».

Заключение

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

- поставлена задача оптимальной глобальной маршрутизации в виде задачи нелинейного целочисленного программирования;

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

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

- рассмотрены схемы управления перегрузкой с регулированием скорости источника по величине отклонения длины очереди от порогового значения. Предложенные модели динамической системы управления перегрузкой позволяют рассчитывать потери ячеек АВЯ трафика при любом изменении предоставляемой пропускной способности;

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

- рассмотрены системы управления перегрузкой АВЯ трафика с обратной связью по отклонению от предоставляемой пропускной способности. Получены аналитические выражения для величины потерь ячеек;

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

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

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

- результаты диссертационной работы внедрены и использованы в ОКР «Аэрофлот», «Цифра-ГА», «Лазурь», «65с28», «38», «Взгляд-НПП».