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

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

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

• ^ УДК 621.391.28

Войткевич Константин Леонидович

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

Специальность 05.13.01 Управление в технических системах

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктбра технических наук.

Н.Новгород. 1998 г.

Работа выполнена на научно-производственном предприятии «Полет» г. Н.Новгород.

доктор технических наук, профессор Лазарев Юрий Владимирович (г. Москва);

доктор технических наук, профессор Крылов Владимир Владимирович (г. Н.Новгород);

доктор технических наук, профессор Гергель Виктор Павлович (г. Н.Новгород).

Ведущая организация - государственное предприятие «Воронежский НИИ связи».

диссертационного совета Д063.85.02 в Нижегородском государственном университете по адресу 603600, г. Н.Новгород, ГСП-41, ул. Минина 24.

С диссертацией можно ознакомиться в библиотеке НГТУ.

Официальные оппоненты:

Защита состоится

заседании

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

1998 г.

Ученый секретарь

диссертационного совета

Иванов А.П.

Общая характеристика работы.

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

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

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

Абоненты типа В также требуют выделенных каналов, однако объем трафика существенно меньше. Кроме того эти абоненты являются источниками-потребителями смешанного трафика (речь + данные) в режиме запроса.

Центральной проблемой при организации связи с объектами типов А и В является их постоянная привязка к СОИ как подвижных абонентов.

Абоненты типа С являются абонентами с ярко выраженным пачечным трафиком. Для обеспечения связи с| ними строится сеть с глобальной зоной действия, к которой предъявляются высокие требования по вероятности своевременной доставки и достоверности передаваемой информации.

4

Рнл 1 Rmmíimm-íimo» ню я n «ti OD О О Г»

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

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

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

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

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

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

наиболее представительной из которых является ATM Forum.

I

В соответствии с рекомендациями ATM Forum выделено 5 сервисных категорий трафика, определены их параметры и требования по качеству обслуживания. Наиболее важной является сервисная категория с постоянной битовой скоростью (Constant Bit Rate - CBR). Эта сервисная категория охватывает более 90% всей передаваемой в настоящее время информации и в рамках этой категории могут передаваться остальные 4

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

Т.к. в основе CBR-соединений лежит принцип коммутируемого

I

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

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

¡s

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

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

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

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

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

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

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

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

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

I

земля».

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

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

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

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

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

1. Разработаны новые алгоритмы «последовательной» адаптивной маршрутизации: алгоритм с минимальной вероятностью отказа для следующего требования (МВОСТ), алгоритм «кратчайшего пути с резервированием» (КНР). Доказано, что данные алгоритмы превосходят ранее известные по величине вероятности блокировки вызова во всем диапазоне изменения входной нагрузки для сетей с решетчатой структурой.

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

I V/

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

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

5. Предложен новый класс протоколов множественного доступа со случайным доступом и частотным разделением каналов (РОМА-АЬОНА), область применения которых - распределенные системы передачи данных с подвижными объектами. Разработана марковская модель, позволяющая определить оптимальные значения вероятности «первичного» и

«вторичного» захвата слота, при которых производительность системы

I

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

6. Разработан метод обобщенного множественного доступа в протоколе типа БОМА-ЛЬОНА, при котором вводится дополнительная степень свободы - число каналов для передачи пакета, выбираемое случайным образом. Показано, что для однородной системы существует оптимальное число выбираемых случайным образом каналов, которое уменьшается с увеличением нагрузки.

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

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

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

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

воздушных систем связи.

I

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

связи (ОКР «38» - заместитель главного конструктора); создании и государственных испытаниях системы мобильных командных пунктов («65с28» - заместитель главного конструктора); разработке методов управления трафиком в сети ведомственной принадлежности (ОКР «Лазурь» - главный конструктор); разработке, создании и испытании системы привязки подвижных объектов к наземным сетям связи и управления (ОКР «Взгляд-HI 111-НН» - главный конструктор); разработка системного проекта по развитию ведомственной АСУ и связи (шифр «Синтез» - заместитель главного конструктора);

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

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

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

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

I

Основные результаты работы докладывались и обсуждались на Всероссийских научно-технических конференциях: НПП «Полет» Н.Новгород, 1994 г.; военная академия связи, С.Петербург, 1997 г.; ЛНПО «Красная Заря», г.Ленинград, 1986 г.; ВНИИС, г.Воронеж, 1996 г.; Нижегородский государственный технический университет, г.Н.Новгород, 1997, 1998 гг.; Нижегородский государственный университет,

г.Н.Новгород, 1994 г., а также международных НТК: «Нечеткая логика, интеллектуальные системы и технологии», г.Владимир, 1997 г.; «Радиолокация, навигация, связь», г.Воронеж, 1998 г.

Публикации.

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

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

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

Содержание работы.

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

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

Для базовой сети обмена информацией, являющейся АТМ-сетью, приведены параметры трафика, определяющие характеристики потока ячеек со стороны источника, параметры качества обслуживания (QoS), предоставляемого сетью, а также правила проверки реальных параметров трафика заявленным.

ATM уровень включает 5 сервисных категорий: постоянная скорость передачи (Constant Bit Rate - CBR); переменная скорость передачи в реальном времени (Real-Time Variable Bit Rate); переменная скорость передачи (Non-Real-Time Variable Bit Rate); неопределенная скорость передачи (Unspesifled Bit Rate - UBR); доступная скорость передачи (Available Bit Rate - ABR).

Для этих сервисных категорий определяются следующие параметры качества обслуживания: дисперсия времени задержки ячейки (Cell Delay Variation - CDV); максимальная задержка ячейки (Max Cell Transfer Delay -CTD); вероятность потери ячейки (Cell Loss Ratio - CLR).

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

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

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

Основной недостаток нестатистического режима - неэффективное использование полосы, когда значительная часть трафика .члллетгя пачечной. При статистическом режиме работы узла скорость исходящей линии может быть меньше, чем сумма пиковых скоростей рхо,г:::;чк}' каналов, но должна быть больше суммы их средних скоростей. В :>то1-режиме потенциальный выигрыш в использовании полосы можег получен ценой возросшей сложности механизмов управления Т|/н<Ь:'//\ которые должны гарантировать, что задержки и потери пакетов ос.гагу в допустимых рамках (ЗоБ.

В настоящее время все функции управления трафиком реализуются двумя категориями методов: превентивными и реактивными.

Превентивные методы предназначены для предоизращсю перегрузки, а реактивные методы восстанавливают работоспссобност.. сети после того, как произошла перегрузка.

Анализ литературы по статистике трафика свидетельствует о ток

I

что подавляющее большинство (более 90%) всей передаваемой настоящее время информации является информация, которая молг.ч

I

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

к процедуре доступа в сеть, которая в значительной степени определяется методами маршрутизации.

Методы маршрутизации развивались параллельно с развитием сетей и в настоящее время имеется достаточно много методов, которые классифицированы по различным признакам

(централизованные/децентрализованные, адаптивные/неадаптивные,

статические, динамические и т.д.). Однако ATM сети имеют свои специфические особенности, которые не позволяют эффективно использовать разработанные методы. К таким особенностям следует отнести: большой диапазон значений запрашиваемой полосы (от десятков килобит до десятков мегабит) для организации виртуальных каналов; огромные скорости трактов (от 155 Мбит/сек и выше); малые значения времени доставки ячеек.

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

Важнейшим направлением, которое активно развивается в настоящее время, является новая концепция передачи пачечного трафика -ABR служба, которая предполагает, что скорость передачи зависит от имеющейся в наличии полосы и может динамически изменяться при изменении состояния сети. Известен целый ряд протоколов управления перегрузками ABR трафика: протокол быстрого резервирования (Fast Reservation Protocol) в двух его разновидностях - FRP/IT и FRP/DT; протокол управления скоростью на основе измерения задержки; обратное

точное уведомление о перегрузке (ВЕЫС); ранний отброс пакетов, а также целый ряд протоколов, основанных на использовании методов «кредитов» (credit-based) и управлении скоростью (rate-based).

Метод «кредитов» заключается в реализации оконного управления потоком на уровне линии и на уровне виртуального канала.

Метод управления скоростью источника основан на использовании петли обратной связи по которой передаются специальные сигнальные RM ячейки.

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

Специфику воздушной связи в направлении «воздух-земля» во многом определяют протоколы множественного доступа (ПМД).

ПМД решают задачи эффективного использования ограниченного ресурса радиоканала некоторым множеством терминалов. По способу управления доступом в радиоканал можно выделить 5 классов ПМД:

1. ПМД с жестким распределением ресурсов. К данному классу следует отнести протоколы TDMA, FDMA, CDMA... Протоколы эффективны при ограниченном числе терминалов с постоянным трафиком.

2. ПМД со случайным доступом (ALOHA, S-ALOHA, CSMA, ВТМА...). Область применения протоколов - системы с большим числом малоактивных терминалов и резко выраженным пачечным трафиком.

3. ПМД с централизованным управлением (SRMA, SRMA-RAM, Probing...). Данные протоколы предполагают режим работы типа «запрос-ответ», а также резервирование ресурса (полоса, временной слот)

центральной станции по запросу терминала. Основной недостаток протоколов - значительная задержка перед началом передачи, даже в отсутствии конкурирующих терминалов.

4. ПМД с децентрализованным управлением (R-ALOHA, RR, MSAP, RUC). Данная группа протоколов основана на выполнении терминалами общего согласованного алгоритма с целью координации своих действий. Недостатки - те же, что и п.З.

5. Комбинированные протоколы (MSAP-CSMA, URN, S-ALOHA-TDMA). Сюда относятся протоколы, являющиеся комбинацией 2-х или более протоколов, входящих в группы 1-4. Комбинированные протоколы предполагают наличие механизма слежения за трафиком и плавный переход из одного режима в другой с целью адаптации под изменяющийся трафик.

По характеру временных процессов ПМД делятся на синхронные и асинхронные, по типу конкуренции за канал - на конфликтные и бесконфликтные.

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

Проведенный сравнительный анализ ПМД по количеству работающих терминалов, загрузке, относительному времени

распространения сигнала, вероятности искажения пакета из-за ошибок в

I

канале, типу трафика (равномерный/пачечный), длины пакета (постоянная/переменная), а также учет специфики рассматриваемой системы авиационной воздушной связи позволил в качестве ДМД обосновать выбор комбинированного протокола типа FDMA-S-ALOHA с возможностью использования терминалом одновременно нескольких частотных каналов при передаче пакета.

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

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

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

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

I

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

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

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

В результате сравнительного анализа установлено, что разница в эффективности различных алгоритмов увеличивается с увеличением степени связности сети. Лучшими характеристиками обладает алгоритм с минимальной вероятностью отказа для следующего требования, далее идет алгоритм кратчайшего пути с резервированием, причем параметр № можно выбрать оптимальным образом, далее алгоритм минимальной стоимости. Для однородных сетей алгоритм минимальной стоимости выигрывает у алгоритма кратчайшего пути в области малых загрузок, а для неоднородных сетей (с существенно различными пропускными способностями линий) во всей области изменения входных нагрузок. Показано, что оптимальное значение У/ для алгоритма с резервированием полосы лежит в пределах 0.25-0.30.

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

I

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

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

решение в масштабе реального времени для данного класса задач не существует.

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

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

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

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

которого относительная загрузка наиболее загруженной линии будет минимальной.

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

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

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

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

Рис.2.

Зависимость вероятности отказа в соединении (Р,ч) от входной нагрузки

I - последовательная маршрутизация (кратчайшие пути)

II - последовательная маршрутизация («минимальная стоимость»)

III - комбинированная маршрутизация (Тд = 1)

IV - комбинированная маршрутизация (Тд =0.1)

V - комбинированная маршрутизация (Т4 =0.05)

VI - глобальная маршрутизация

На рис.3, приведены зависимости вероятности отказа в соединении от периода проведения глобальной оптимизации с учетом ее длительности (Тор1). Из графиков следует, что для каждого значения Тор, можно найти такой период Т4, при котором вероятность отказа будет минимальной.

0.19 0.18 0.17 0.16 0.15 0.14 0.13 0.12 0.11 0.10

с 7 Т„-Ь.5 7 Т„=0.|

ХТ=5.5 / Т"'

Длительность соединения=1 / { 7

______—

Рис.3.

Зависимость вероятности отказа в соединении Ргч от периода оптимизации Т при разных значениях длительности процедуры глобальной оптимизации

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

- разница между суммой длин всех путей при текущем состоянии сети и суммой длин 82, получаемой при глобальном распределении Б,> А;

- разница между длиной пути для какого-либо соединения Ь„ существующего в данный момент и кратчайшим путем для данного соединения Ь2, Ь, - Ь2 > Д;

- разница между загрузкой наиболее загруженной линии И, при текущем распределении и глобальном ¥2, Б, - Е, > Д.

В конце главы приведена схема реализации процедуры комбинированной адаптивной централизованной многоскоростной

о

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

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

В каждом узле сети, через который проходит ABR виртуальный канал ведутся отдельные очереди по каждому каналу. Модель управления представляет из себя динамическую систему регулирования с замкнутой петлей обратной связи и с запаздыванием в управлении (рис.4.) Длина очереди, ассоциированная с виртуальным каналом, представляет собой интеграл по времени (0,t) разницы между скоростью поступающих в очередь ячеек u(t) и скоростью ухода ячеек из очереди d(t):

x(t)=/[u(t'-T)-d(t')]dt'

о

где т - полная задержка распространения сигнала по петле обратной

связи.

Рис.4.

Динамическая система управления

Величина d(t) является возмущением и от ее значения целиком зависит поведение системы, х„ является заданным порогом очереди. Так при появлении приоритетного трафика, либо активизации нового виртуального канала величина d(t) уменьшается, наоборот, при освобождении ресурсов линии d(t) возрастает, т.к. при циклической дисциплине обслуживания очередей частота обращения к рассматриваемой очереди возрастает.

Приведенная динамическая модель описывается уравнениями:

^=u(t-T)-d(t)

1

u(t) = K[x0(t)-x(t)]

Регулируемой величиной является скорость источника u(t). Цель заключается в выборе такого закона регулирования при котором минимизируется вероятность потерь ячеек при ограничении снизу на коэффициент использования линии.

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

На рис.5, приведены графики зависимости длины очереди x(t), скорости источника u(t), скорости ухода ячеек из очереди d(t) и скорости

dx

изменения длины очереди — при начальных условиях: х(0)=0, d(t)=al(t),

dt

где a=const, l(t) - единичная ступенчатая функция.

Рис.5.

Графики зависимости длины очереди, скорости изменения длины очереди и скорости источника при релейном законе управления и постоянной скорости возмущения

(с!(0=а=сопз1).

Как видно из рис.5., в системе устанавливаются колебания с

-Т- и0Т ~ А I

периодом Т = —*—- и амплитудои Ат„ = хт„ - хтш. 1

а(и0-а)

Очевидно, что если хтах = хь (хь - выделенный объем буфера для данного виртуального канала) и хт1П = 0, то это соответствует оптимальному режиму работы, когда нет потерь и пропускная способность канала используется полностью.

Далее исследуется случай, когда в момент t0 d(t) скачком уменьшается на величину а,. В этом случае очередь начинает расти быстрее, т.к. источник в течении т секунд работает с прежней скоростью. Показано, что если xb = хт„, то возникают потери ячеек, величина которых оценивается, как

nL = xmM-t(a-a,)-x^ + x0 где х'п„ - новый (уменьшенный) размер буфера. Далее, при выборе

(х' -х')

нового значения скорости источника uj, =——-—+ а-а, система

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

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

Для уменьшения вероятности потерь и недоиспользования канала в переходный период предложен закон регулирования скоростью, когда скорость источника и принимает два значения - и, и и2, причем u,»u2. В начальный момент, когда очередь начинает расти, скорость источника устанавливается и,. При достижении некоторого порога х„ (хп<х0) скорость источника устанавливается равной и2, что приводит к очень медленному росту очереди. В этом алгоритме величина хтах выбирается меньше, чем размер буфера хь.

Исследована система регулирования с предиктором Смита. Предиктор предсказывает длину очереди в лрмент (t+т), зная ее значение в

I'

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

В результате решения исходной системы дифференциальных уравнений при начальных условиях х0(1)= Хо1(1), с1(1)=а1(Ч), х(0)=0 получены зависимости длины очереди и скорости источника от времени.

Если после завершения переходных процессов происходит скачок скорости ухода ячеек <¿(1) и порогового значения буфера Хо, т.е. ё(1) = а1(1)-а,1(1-10), х0(0 = х01(1)-х,1(Х-10), то в результате решения уравнений с начальными условиями, соответствующими стационарному состоянию системы получены аналитические выражения для х(Ч) и и(1),

причем при I со, и(1)-»а-а,, х(4) х0 - х, - -——+ а,т (рис.6.).

к

Необходимым условием отсутствия потерь в установившемся

режиме является условие -—— >ат, т.е. установившаяся длина очереди

к

меньше значения нового порога х„ — х,.

Отсутствие потерь в переходном режиме определяется условием

а,т>^-х,. Если это условие не выполняется, то в переходном режиме

будут потери, величина которых пь равна разности между максимальным значением длины очереди в момент 1, + т и новым порогом х0 - х,:

При 1->оо, и(1)-»а, х(0->х0- —

к

а

п, = х.---над

I. . к ,

Эти результаты можно обобщить на п скачков:

<1(1) = а1(1)-£ак 1(1-0

х„ (1) = х01(1)1(1-0

к=|

и(0 = а-£ак, х(О = х0 -

к

а

/1

» I ч«

Рис.6.

Графики зависимости длины очереди, скорости изменения длины очереди и скорости источника от времени для динамической модели регулирования с предиктором Смита при скачке скорости ухода и объема буфера.

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

В системах управления перегрузкой с использованием регулятора скорости источника по длине очереди х((:) при линейном изменении величины возмущающего трафика (1(0, поведение скорости источника как функции времени зависит от соотношения между величиной времени 1„

I;

1 определяющего скорость изменения <1(0 и величиной ^ определяющей время достижения скоростью и(0 своего минимального значения.

Рис.7. Рис.8.

Зависимость u(t), dx/dt, x(t) при t, < tm Зависимость u(t), dx/dt, x(t) при t, > tm

f k2x t 1

При t^t], что равносильно условию lnl 1 ч--—j > kt,, скорость

источника u(t) всегда будет больше предоставляемой скорости d(t). Очередь будет в этом случае расти вплоть до выхода в установившийся режим (рис.7.). |

( k2x t ^

При tm<t, или ln^l н--—J < kt,, скорость источника u(t) изменяется

от максимального значения, большего, чем d(t), до значения, меньшего d(t), при этом минимальное значение достигается в момент времени tm, когда u(tm)>d(tra). Это приводит к немонотонной зависимости длины очереди x(t) от t, приводя сначала к росту очереди x(t) до максимального

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

Улучшение качества регулирования с точки зрения уменьшения потерь ячеек можно достичь, используя измерение возмущения (1(0 для компенсации возможных отклонений х(1) с помощью предложенной комбинированной схемы регулирования скорости с прямой связью по возмущению с!(1) и обратной связью по отклонению выхода х(1) от порога

Хо(1).

Прямая связь является регулируемой с параметром Р, т.е. с!*(1)= рсОД, 0<р<1. При Р=0 система переходит в предиктор Смита, при Р=1 в качестве прямой обратной связи используется полная величина скорости ухода ячеек из очереди.

Задавая начальные условия в виде: (1(1)=а1(1), х0(1)=х01(1), х(0)=0, получено решение для и(1) и х(0:

и(1) = кх0е-кЧ(1-р)а(1-е-и)

На рис.9, приведены зависимости и(с) и х(1) при различных значениях р.

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

Рис.9.

Зависимости и(!), для комбинированного регулятора

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

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

В четвертой главе рассматриваются методы управления трафиком в авиационных радиосетях.

Центральной проблемой для каналов «воздух-земля» является разработка эффективных протоколов множественного доступа. В качестве ПМД, в наибольшей степени удовлетворяющий специфике задачи предложен комбинированный протокол РБМА-АЬОНА.

Для построения марковской модели системы предполагается, что есть N каналов с частотным разделением. Каждый канал сегментирован таким образом, что длина сегмента равна длительности передачи пакета. Данным частотно-временным ресурсом пользуются М терминалов, которые конкурируют за слоты в каждом частотном канале. Доступ терминала к любому слоту в любом канале является случайным, причем выбор частотного канала производится равновероятно с вероятностью 1/И, а вероятность выбора временного сегмента (слота) зависит от состояния терминала, который имеет буфер для хранения одного пакета. Новый пакет генерируется внутренним источником терминала только тогда, когда буфер пуст, причем вероятность генерации нового пакета подчиняется геометрическому распределению с параметром Р0. Сгенерированный пакет передается немедленно. В канале возможны искажения пакета за счет конфликтов с другими терминалами (структурные искажения), а также за счет шумов в канале (информационные искажения - с вероятностью Рии). Если пакет терминала подвергается искажениям, терминал переходит в состояние «блокировки», в котором для передачи «заблокированного» пакета он выбирает канал с вероятностью и слот с вероятностью Рг.

Для описанного процесса построена цепь Маркова и найдены

г

переходные вероятности Ркт для числа «заблокированных» терминалов. В результате получены стационарные характеристики системы:

стационарные вероятности числа заблокированных терминалов Г^, определяемые из уравнений:

м м

1пкры = пт, £пк = 1,

|с»0 1.0

М

среднее число «заблокированных» терминалов п0 = ]Г кПк, стационарная

к=0

производительность 80, определяемая как среднее число успешно переданных пакетов в течении слота, а также стационарная удельная задержка г5ал = п0/80.

Из полученных зависимостей Тмл(Р0,Рг), 80(Р0,РГ), представленных на рис. 10,11. видно, что кривые для задержки и производительности имеют ярко выраженный экстремальный характер, т.е. существуют такие значения параметров Р0 и Рг (при заданном значении Рии), при которых производительность максимальна, а задержка - минимальна. При увеличении Р0 максимум Б0 смещается в область меньших значений Рг. При этом с увеличением вероятности искажения пакета Ри„ производительность падает, а задержка увеличивается.

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

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

N=10 _~

О 0.01 0.03 0.05 0.07 0.09 0.11 0.13 0.15

Рис.10.

Зависимость производительности 80(Р0,РГ) и задержки ^(Р0,РГ) для синхронной многоканальной системы

АШНА(Рни = 0.1).

О 0.01 0.03 0.05 0.07 0.09 0.11 0.13 0.15

Рис.11.

Зависимость производительности S„(P0,Pr) и задержки t3JP0,PJ для синхронной многоканальной системы ALOHA (Рик = 0.4).

Аналитическое решение задачи приводится для частных случаев. 1. Однородная система. Предполагается, что все каналы идентичны с точки зрения скорости и вероятности информационных искажений, а терминалы образуют общий входной поток с интенсивностью X. Тогда для Р5 справедливо:

1-

ХТу

где ©„ - вероятность выбора для передачи п каналов (п = 1 N) Т - длительность слота.

Графики зависимости Р5 от числа используемых параллельных каналов к приведены на рис.12.

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

Рис.12.

Зависимость вероятности доставки от числа параллельных каналов (N=10).

2. Неоднородная система.

Параметры каналов заданы в виде матриц скоростей и вероятностей искажений пакета ЦЛГ], |РИЯ ||, 1 = Входной поток - пуассоновский с параметром X. Необходимо найти такие вероятности выбора каналов

Рв(1), 1 = 1 -н N, при которых обеспечивается максимальная вероятность

I

успешной передачи.

Получена система уравнений: I

I

где - неопределенный множитель Лагранжа.

Если Рви = Рии = const, то

N

).'Т = const, ]Г А.'

■=|

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

Аналитическое решение возможно еще в 2-х случаях: а) Х.Т « 1 (малые нагрузки). В этом случае

ь-i-

X =-U - 2Т

2Т> 2(1-рни)т;^- 1

'2(1-рии,)1;

б) ХТ » 1 (большие нагрузки).

Оптимальное распределение получается, если для (N-1) каналов выполняется А.,1] = 1, ¡= 1н-М-1, а весь оставшийся трафик направлен в «худший» канал], определяемый из условия: шт|(1-Рии )/Т,|, I = 1 N.

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

Задача оптимального случайного распределения потоков в каналах «земля-воздух» сформулирована в виде:

м Тк <0

= (3(,)->тах ■-1 А.

о(">о(|)

, ^ ^-доп

где W - вероятность своевременной доставки произвольного пакета; <3(|) - вероятность своевременной доставки для ¡-го терминала; -

допустимая вероятность своевременной доставки для ¡-го терминала; -интенсивность потока для ьго терминала; X - общий входной трафик.

Другая возможная постановка задачи - минимизация потерь при ограничении на среднюю задержку доведенных пакетов:

где XV - вероятность доведения пакета; - среднее время доставки для 1-го терминала; Т'о'п' - среднее допустимое время доставки для 1*-го терминала; Р^, Р^ - вероятность доведения и заданная допустимая вероятность доведения до ¡-го терминала соответственно.

Получены аналитические выражения для вероятности доставки и вероятности своевременной доставки в общем случае. Точное решение найдено для случая однородной системы, для которой вероятность своевременной доставки имеет вид:

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

На рис.13. приведены зависимости вероятности своевременной доставки от числа используемых параллельных каналов. '

м ТО)

\У= У —Р(!) ->тах

X—< у^ до»

р(') > р(0

лов доп

Рис.13.

Зависимость <3(п) для каналов «земля-воздух».

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

Рассмотрены методы «детерминированного,» распределения потоков

г

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

набор каналов. Эти методы применимы как для каналов «земля-воздух», так и «воздух-земля».

Дается постановка задачи оптимального «детерминированного» распределения потоков в многоканальных системах в виде задачи целочисленного программирования.

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

Основные результаты работы и выводы.

1. Разработаны 2 новых алгоритма последовательной маршрутизации CBR-соединений в ATM сетях: алгоритм с минимальной вероятностью отказа для следующего требования (MB ОСТ) и алгоритм «кратчайшего пути» с резервированием (КПР).

Приведен сравнительный анализ этих, а также ранее известных алгоритмов («кратчайшего пути» (КП), пути «минимальной стоимости» (ПМС), пути с «минимальным приращением стоимости»(МПС), maxmin пути, minmax пути) по критерию вероятности отказа в соединении при

различных значениях входной нагрузки для сетей решетчатой структуры (15-20 узлов).

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

Лучшими характеристиками обладают алгоритмы МВОСТ и КПР, далее следуют алгоритмы КП, ПМС, МП С, тахтш, тттах.

2. Алгоритм КП может быть улучшен за счет резервирования полосы. Показано, что существует оптимальное значение резервируемой полосы («25%), при котором вероятность блокировки минимальна. Эффект, получаемый от резервирования прямо пропорционален связности сети и обратно пропорционален входной нагрузке.

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

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

затрат и точности вычисления в зависимости от размеров сети.

г

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

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

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

7. Разработаны модели динамической системы управления перегрузкой АВЯ трафика с регулятором релейного типа и с использованием предиктора Смита. Проведена оценка потерь ячеек для случая скачкообразного изменения предоставляемой пропускной способности. Потери ячеек можно разделить на две части: первая часть определяется скачкообразным уменьшением величины предоставляемого буфера и сохраняется даже в отсутствии запаздывания в управлении (т=0), вторая часть связана с переходными процессами в системе и обращается в ноль при т->0.

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

I'

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

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

10. Предложены системы управления перегрузкой АВЯ трафика с обратной связью по отклонению от предоставляемой пропускной способности. Если в регуляторе использовать в качестве задаваемой величины полную пропускную способность С0, это приводит к появлению потерь ячеек в установившемся состоянии. Для избежания этого, необходимо в регуляторе использовать только часть полной пропускной

способности, т.е. рС0. Величина (1-р)С0 наряду с величиной задержки т

*

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

11. Разработана марковская модель многоканальной системы с синхронным множественным доступом РБМА-АЬОНА. Получены аналитические выражения для вероятностей перехода, а также стационарных характеристик системы - среднего числа заблокированных терминалов, производительности и задержки пакета.

12. Предложен обобщенный метод доступа в системе ЕБМА-АЬОНА. Получено аналитическое выражение для вероятности доставки произвольного пакета. Для однородной системы найдены зависимости вероятности доставки от числа используемых параллельных каналов, общего трафика, вероятности искажения пакета в радиоканале. Результаты свидетельствуют, что для конкретного набора внешних параметров всегда

можно найти оптимальное число параллельных каналов, при котором

I

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

13. Решена задача распределения входного потока по неоднородным каналам в системе РОМА-АЬОНА, когда терминалу разрешен выбор единственного канала. Найдены аналитические выражения для долей

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

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

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

Основные публикации.

1. Войткевич К.Л., Пейсаховская И.М. Бортовое приемо-передающее устройство связи. А/с № 226703, приоритет от 03.12.84 г.

2. Захаров Г.П., Войткевич К.Л., Храмов Н.И. Модель синхронной многоканальной системы связи с множественным доступом. «Техника средств связи», сер. Техника проводной связи, 1985 г. вып. 8.

3. Захаров Г.П., Войткевич К.Л., Храмов Н.И. Протоколы множественного доступа в радиосетях передачи данных. «Техника средств связи», сер. Техника проводной связи, 1985 г. вып. 8.

4. Войткевич K.JI., Скрипилева Н.А. Алгоритм оптимального распределения информационных потоков в радиосети с ненадежными каналами. «Техника средств связи». Сер. Техника проводной связи. 1986 г., вып. 4.

5. Войткевич К.Л., Шалаев В.А. Организационно-технические методы повышения помехозащищенности систем авиационной дальней связи. Сб. «Интегральные сервисные системы связи с коммутацией пакетов», Ленинград, 1986 г.

6. Войткевич К.Л., Пейсаховская И.М. Система связи подвижных абонентов. А/с № 277477, приоритет от 02.03.87 г.

7. Войткевич К.Л., Скрипилева Н.А. Метод распределения информации в многоканальных радиосетях передачи данных. «Техника средств связи». Сер. Техника радиосвязи. 1989 г., вып. 2.

8. Войткевич К.Л., Скрипилева Н.А. Оценка ВВХ доставки информации при взаимодействии подвижного терминала со стационарной сетью ПД. «Техника средств связи». Сер. Техника радиосвязи. 1990 г., вып. 9.

9. Voitkevich К., Mihailov V., Hvostov Е. ATM-networks and protocols, B-ISDN architecture. NPP «Polyot», N.Novgorod, 1995.

10. Войткевич К.Л., Зудкова И.В., Скрипилева Н.А. Математические модели оптимального распределения трафика a ATM сетях. Сб. докл. Всероссийской НТК «Направления развития систем и средств радиосвязи». Воронеж, 1996 г.

11. Войткевич К.Л., Хвостов Е.Г. Применение метода проекции градиента к задаче оптимальной маршрутизации в сетях передачи данных. Сб. докл. Всероссийской НТК «Направления развития систем и средств радиосвязи». Воронеж, 1996 г.

12. Войткевич К.Л., Скрипилева Н.А. Методы управления потоком и контроля перегрузок в сетях связи. «Телекоммуникационные технологии»

1996 г. №2

13. Voitkevich К., Mihailov V., Zudkova I., Skripilyova N. Optimal routing of multirate channels. NPP «Polyot», N.Novgorod, 1996.

14. Войткевич K.JI., Гусев Д.Ю. Структура бортового интегрированного комплекса. Сб. докл. НТК ФРТК НГТУ, Н.Новгород, 1997 г.

15. Войткевич K.JL, Сауткин В.Е. Алгоритм маршрутизации CBR соединений в ATM сетях. Сб. докл. Международной НТК «Нечеткая логика, интеллектуальные системы и технологии». Владимир, 1997 г.

16. Сауткин В.Е., Войткевич К.Л., Чопенко А.Б. Характеристики систем управления перегрузкой ABR трафика с использованием схем регулирования с обратной связью. Сб. докл. Международной НТК «Нечеткая логика, интеллектуальные системы и технологии». Владимир,

1997 г.

17. Войткевич К.Л. Региональный проект информатизации крупного региона страны. «Проблемы информатизации», 1997 г., вып. 3.

18. Voitkevich К., Alekseev V., Skripilyova N., Zudkova I., Sautkin V. Algorithms of CBR routing. Simulation results. Performances of CBR traffic overload control system with use of regulation circuits with a feed-back.NPP «Polyot», N.Novgorod, 1997.

19. Сауткин B.E., Войткевич К. Л., Чопенко А.Б. Анализ характеристик систем управления перегрузкой трафика с переменной скоростью в сетях с асинхронным режимом доставки информации. Сб. докл. НТК ВАС «Актуальные проблемы развития систем военной связи ВС РФ в новых геополитических, оперативно-тактических и экономических условиях». С. Петербург, 1998 г.

20. Войткевич К.Л., Сауткин В.Е. Сравнительный анализ методов маршрутизации соединений с постоянной скоростью в сетях в сетях с асинхронным режимом доставки информации. Сб. докл. НТК ВАС «Актуальные проблемы развития систем военной связи ВС РФ в новых геополитических, оперативно-тактических и экономических условиях». С. Петербург, 1998 г.

21. Войткевич К.Л., Сауткин В.Е. Сравнительный анализ критериев маршрутизации CBR-соединений. Сб. докл. 4-й международной НТК «Радиолокация, навигация, связь». Воронеж, 1998 г.

22. Сауткин В.Е., Войткевич К.Л., Чопенко A.B. Анализ систем управления перегрузкой трафика в сетях с изменяющейся пропускной способностью. Сб. докл. 4-й международной НТК «Радиолокация, навигация, связь». Воронеж, 1998 г.

23. Войткевич К.Л. Комбинированный протокол множественного доступа FDMA-ALOHA. Сб. докл. 4-й международной НТК «Радиолокация, навигация, связь». Воронеж, 1998 г.

24. Войткевич К.Л., Сауткин В.Е. Оптимальная маршрутизация в пакетных сетях. Потоковые модели. Учебно-методическое пособие. ННГУ, 1998 г.

25. Войткевич К.Л., Кривицкий A.A. Построение самолетного комплекса связи с использованием принципов и оборудования ATM. Сб. докл. НТК ФИСТ НГТУ, Н.Новгород, 1998 г.

1

26. Войткевич К.Л., Сауткин В.Е. Моделирование речевого обмена в интегрально-цифровой сети связи. Учебно-методическое пособие. ННГУ, 1998 г.

27. Войткевич К.Л., Сауткин В.Е. Моделирование обмена данными в интегрально-цифровой сети связи. Учебно-методическое пособие. ННГУ, 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», «Взгляд-НПП».