litceysel.ru
добавить свой файл
1


МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ЭЛЕКТРОНИКИ И

МАТЕМАТИКИ

Кафедра Информационно-коммуникационных технологий


Отчёт по практике


на тему: «Разработка аппаратно-программного комплекса

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


Студент: Черняк А.Ю.


Руководитель проекта: Леохин Ю.Л.

Москва 2011 г

Аннотация


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

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


Содержание


1 Введение 4

2 Обзорно-аналитическая часть 6

2.1 Обзор технологических решений для отладки алгоритмов обслуживания очередей в узлах коммуникации 6

2.2. Постановка задачи проектирования и формирование требований 10

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

3.1. Общая архитектура комплекса 15

3.2. Структура аппаратных средств комплекса 18

3.3. Структура программных средств комплекса 22

3.4. Алгоритм функционирования системы комплексной динамической отладки и испытания 25

1 Введение


Актуальность. Развитие информационных сетей и объемов обмена информацией в современных корпоративных системах ведёт к усложнению конфигурации сетей и управления потоками информации. Новые поколения приложений, используемых в бизнесе, становятся всё более мультимедийными, увеличивая нагрузку на корпоративные сети. В этих условиях, как показывает анализ моделей интегрированного и дифференцированного сервисов (IntServ; DiffServ), общими важными элементами управления корпоративных сетей являются механизмы обслуживания очередей. Поэтому правильный выбор и настройка алгоритмов обслуживания очередей в узлах коммуникации, оценка возможной длины очередей в узлах коммутации и маршрутизации позволяют оценить параметры качества обслуживания при известных (или наиболее вероятных) характеристиках трафика сети. Поведение очередей представляет собой вероятностный процесс, на который влияет совокупность факторов, особенно при сложных алгоритмах обработки очередей, использующих приоритеты или взвешенное обслуживание разных потоков.


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

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

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

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

- сформирование требований к аппаратно-программному комплексу;

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

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

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

Публикации. Результаты дипломной работы отражены в ­­­­_______ опубликованных печатных работах.

2 Обзорно-аналитическая часть




2.1 Обзор технологических решений для отладки алгоритмов обслуживания очередей в узлах коммуникации



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

Сети коммутации пакетов без установления соединения широко используются для поддержки интегрального обслуживания в единой среде разнородных информаций (данные, речь, видео и т.д.). В них пакеты разнородной информации разделены на два класса – важные и обычные [1]. Основными признаками для осуществления такой классификации являются требования по вероятности потери пакетов (Cell Loss Probability – CLP) и их задержки (Cell Transfer Delay - CTD). Исходя из этого, в качестве базовой модели сети коммуникации пакетов зачастую выбирается одноканальная двух потоковая система массового обслуживания с конечным общим буфером для ожидания в очереди.


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

– пространственные (Space Priorities - SP) ;

- временные приоритеты (Time Priorities - TP) [5].

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

Модели приоритетного обслуживания разнотипных пакетов в узлах сети коммуникации пакетов были исследованы в работах [6, 7]. При этом в работе [6] исследованы классические схемы приоритетного обслуживания, в то время как в работе [7] рассмотрены более сложные модели с множественными приоритетами.

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

Другой подход к моделированию управления потоками пакетов информации в сети изложен в работах [17, 18]. В локальных компьютерных сетях разрыв логических соединений ими рассматривается как следствие либо переполнения промежуточных буферов, либо неисправности физического соединения. Индикатором разрыва соединения является увеличение объема выходной очереди и ее возможное переполнение, если время перекоммуникации виртуального соединения превышает определенное пороговое значение.

Средствами для предотвращения потерь кадров при кратковременном многократном превышении среднего значения интенсивности трафика служат буфер большого объема и политика управления очередями [12, 13, 14]. Каждый процессорный модуль порта обычно имеет свою буферную память для хранения данных. Буфер предназначен для сглаживания кратковременных пульсаций трафика, поскольку даже если трафик хорошо сбалансирован и производительность процессоров портов, а также других обрабатывающих элементов коммутатора, достаточна для передачи средних значений трафика, то это не гарантирует, что их производительности хватит при очень больших пиковых значениях нагрузок. Чем больше объем этой памяти, тем менее вероятны потери данных при перегрузках, хотя при несбалансированности средних значений трафика буфер все равно рано или поздно переполнится. Хорошо, когда эту буферную память можно перераспределять между несколькими портами, так как одновременные перегрузки по нескольким портам маловероятны. Например, трафик может в течение нескольких десятков миллисекунд поступать одновременно на все входы коммутатора, не давая ему возможности передавать принимаемые кадры на выходные порты. В силу случайного характера рассматриваемых событий передачи трафика их статистическое моделирование должно отражать возможность появления подобных резких отклонений.


В настоящее время существует несколько основных классов моделей самоподобного трафика [16 - 19].

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

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

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

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

В работе [18] показано, что длина очередей в буфере узла канала определяется тремя основными параметрами:

- интенсивностью трафика Х;

- параметром Фано F (отношение дисперсии числа событий на временном интервале к математическому ожиданию этой величины);

- показателем Херста Н.

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


Модель трафика, предложенная в работе [18] представляет собой самоподобный случайный процесс с дискретным временем, основой которого является фрактальный гауссовский шум, полученный для заданного значения показателя Херста. Входными параметрами модели являются оценки интенсивности, параметра Фано и показателя Херста входного трафика. Временную реализацию модельного трафика предложено искать в виде Y = bekX, где Х – реализация фрактального гауссовского шума, построенного методом последовательных случайных сложений; b, k – параметры, зависящие от интенсивности и параметра Фано входного трафика.

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

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

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

В работах [19 - 22] показано, что наиболее трудоемким и сложным этапом отладки управляющих программ является комплексная динамическая отладка (КДО). На этом этапе обнаруживаются и устраняются наибольший процент системных ошибок (по некоторым данным [23] до 30%).

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

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

2.2. Постановка задачи проектирования и формирование требований


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

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

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


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

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

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

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

1) имитировать работу сети по заданным параметрам нагрузки трафика, количеству узлов коммуникации;

2) регистрировать и вычислять следующие параметры в коммуникационном узле:

- время поступления пакета в узел,

- время трансляции пакета узлом в сеть,

- время задержки пакета в узле,

- изменение задержки,

- количество потерянных пакетов,

- изменение длин очередей и их текущих значений.

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

Решение поставленных задач должно выполняться комплексно.


Определим требования к комплексу, которыми должен он удовлетворять.

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

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

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

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

Следующая степень информативности — это количественная информация о временных характеристиках информационного трафика через узлы коммуникации.

• Адекватность модели определяется идентичностью поведения в СМО, т.е. сходство зависимостей длины очереди и вероятности потерь от коэффициента загрузки системы.

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


• Доступность и открытость (как продукта, так и платформы, на которой он работает). Хороший плюс для такого рода систем — это открытый исходный код (Open Source) и свободное распространение. Это свойство позволяет с наименьшими трудовыми затратами реализовывать изначально не предусмотренные возможности. Также, приветствуется банальная бесплатность программного продукта.

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

Вывод по разделу

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

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

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




3.1. Общая архитектура комплекса



Предлагается следующая архитектура системы отладки и испытания, и состав программных средств комплекса, представленная на рис. 3.1.





Рис. 3.1. Архитектура комплекса отладки и испытания и состав программного обеспечения

В состав системы входят следующие компоненты:


  • компьютер разработчика;

  • имитатор сетевого узла;

  • ловушка событий;

  • синхронизатор процессов имитации;

  • ПО системы отладки и испытания.

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

В отличие от известных методов реализации КДО [28, 29] преимущество предлагаемого заключается в том, что за счет введения аппаратно-программной имитации сетевого узла и средств сопряжения сокращается объем программного обеспечения системы КДО. Это позволяет использовать стартстопный режим в резидентных средствах отладки. Введение аппаратно-программной имитации минимизирует также влияние средств отладки на функционирование отлаживаемого ПО. Искажения реального времени, связанные с прерываниями отлаживаемого ПО для выполнения программ моделирования и обработки результатов, в каждом конкретном случае могут быть точно вычислены. Появляется также возможность реализации смешанного моделирования, когда часть моделирующих устройств заменяется реальными, работающими в различных режимах обмена информацией.

Для моделирования сетевого узла выбран информационно-подобный способ имитации, обеспечивающий значительный выигрыш в используемых ресурсах [30, 31, 32].

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

Останов "реального" времени осуществляется по событиям, к которым относятся:

- "запрос на обслуживание очереди",


- "выдача управляющего воздействия",

- "чтение состояния очереди".

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

3.2. Структура аппаратных средств комплекса


Структурная схема аппаратных средств системы КДО представлена на рис. 3.2. В её состав входят:

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

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

Кроме того, в состав комплекса входят:

- таймер РВ;

- схема управления генератором и таймером РВ;

- программируемый генератор частоты;

- диспетчер очередей (ДО);

- ловушка событий (ЛС).





Рис.3.2. Структура аппаратных средств системы комплексной динамической отладки и испытания

Блок таймеров включает два таймера и схему переключения таймеров. В таймер 1 программно заносится модельное время поступление пакета в очередь. По истечении этого времени выставляется запрос (ЗПР) диспетчеру очередей; схема переключения таймеров запрещает подачу тактовых импульсов (ТИ) на вход таймера 1 и разрешает подачу ТИ на вход таймера 2, в котором накапливается время ожидания пакета в очереди на обслуживание.


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

Схема подключения ВУ запрещает подачу ТИ на вход таймера 1 при поступлении информации от реального ВУ и отключает схему подключения таймеров (СП). Эта информация заносится в БВВ; выполнение ОПО прерывается, и содержимое БВВ сохраняется в стеке вместе с меткой времени ее поступления.

Если реальный узел отсутствует и его имитирует очередь, то отсутствует сигнал запрета ТИ, и на таймер 1 поступают ТИ.

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

Схема управления генератором и таймером РВ состоит из триггера-флажка F, который управляется подпрограммой синхронизации процессов имитации. Если флаг установлен, то ТИ от генератора частоты Г поступают на входы таймера РВ и таймеров 1 и 2 всех каналов.

Диспетчер очередей имеет n линий запроса на прерывание (n - число очередей). Линии запросов на прерывание возбуждаются только в том случае, когда обнулится содержимое таймера 1 i-ой очереди. В зависимости от заданного режима диспетчеризации ДО принимает решение о подключении i-ой очереди к компьютеру разработчика. ДО управляется подпрограммой обслуживания очередей.

В качестве ДО можно использовать, например, блок циклических приоритетов, входящий в состав устройств, описанных в [33, 34], или БИС КР580ВН59 с программируемой логикой.

Ловушка событий прерывает каждый раз функционирование ОПО при обращении к БУВ и БВВ и по запросу на обслуживание очереди. ЛС вырабатывает сигнал запроса на прерывание (ЗПР) при одновременном появлении на ее входе сигналов: чтение ввода/вывода или запись ввода/вывода; сигнала выбора дешифратора каналов; сигнала останова с прямого выхода F или сигнала ЗПР от ДО. В состав ЛС входит дешифратор кода прерывания, который в ответ на сигнал разрешения прерывания от процессора вырабатывает код однобайтовой команды повторного старта RST, содержащей адрес перехода к подпрограмме обработки соответствующего события.


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


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

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

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

  4. Искажения "реального" времени незначительны. Причем в каждом конкретном случае они могут быть учтены.



3.3. Структура программных средств комплекса


В состав программного обеспечения системы отладки и испытания входят обслуживающие, моделирующие и обрабатывающие программы, представленные на рис. 3.3.





Рис.3.3. Структура программных средств комплекса отладки и испытания


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

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

Программа синхронизации процессов имитации предназначена для пуска и останова "реального" времени путем разрешения или запрета подачи тактовых импульсов на входы таймеров 1 и 2 очередей и вход таймера РВ.

Программа обслуживания очередей осуществляет диспетчеризацию очередей по заданному алгоритму обслуживания в соответствии с имеющимися статистическими данными о работе системы. Возможно программирование ДО на следующие алгоритмы обслуживания очередей:


алгоритм «Первый вошел – Первый вышел» (FIFO - First In First Out);

алгоритм “Круговое обслуживание” (RR - Round Robin);

алгоритм “Круговое обслуживание с дефицитом”(DPR - Deficit Round Robin) [225];

алгоритмы обслуживания очередей с приоритетами (PFQ - packet-by-packet fair queuing) [22, 73];

модифицированный алгоритм PS (PPS или PQ - Priority Processor sharing или Priority) [234];

алгоритм “Взвешенное Круговое обслуживание” (WRR - Weighed Round Robin) [218];

алгоритм “Модифицированное круговое обслуживание с дефицитом” (MDRR - Modified Deficit Round Robin) [194];

алгоритм GPS (Generalized Processor sharing) [222, 223];

алгоритм взвешенного равномерного обслуживания WFQ (Weighed Fair Queuing) [208, 209,];

алгоритм WF2Q [202, 222, 227, 228];

алгоритм WF2Q+[202];

алгоритм VC (Virtual Clock) [73, 235];

алгоритм LFVC (Leap Forward Virtual Clock) [229];

алгоритм SCFQ (Self-clocked Fair Queuing - SCFQ) [214].

Из приведенного списка алгоритмов обслуживания очередей достаточно использовать три алгоритма: FIFO, PFQ и WFQ.

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

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

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

равномерное распределение;

треугольное распределение;

нормальное распределение;

экспоненциальное распределение;


распределение Пуассона;

распределение Эрланга.

Генерировались пакеты следующего формата: 1 – номер пакета в потоке (последовательности), 2- номер потока (последовательности), 3- приоритет пакета, 4 – длина пакета в единицах (рис.3.4)


1

2

3

4


Рис.3.4. Формат пакета


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

Классификатор состояний делит все множество управляющих воздействий, вырабатываемых ОПО, на два класса – допустимых и недопустимых. Классификационные правила строятся с помощью алгоритма обучения. Состав и функции классификатора состояний подробно описаны в работе [25].

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


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

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

- выбирается частота тактовых импульсов;

- задаются количество очередей и алгоритмы обслуживания очередей;

- параметры имитации и режим обработки ошибок.

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


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

1. Алгоритм программы обработки события "выдача управляющего воздействия".




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


Прерывание выполнения ОПО произойдет после того, как ОПО запишет в БУВ код управляющего воздействия (значение выходной переменной). Программа обработки данного события сразу же передает управление модулю синхронизации процессов имитации, который запретит подачу ТИ на входы таймеров 1 и 2 всех очередей и на вход таймера РВ; таким образом, произойдет останов "реального" времени. Далее будет вызвана программа сбора и обработки статистики очередей. Классификатор состояний определит, произошла ошибка по управлению или нет. Если произошла ошибка по управлению, то в зависимости от выбранного режима обработки ошибки на этапе инициализации управление будет передано монитору системы отладки и испытания, если задан режим интерактивной обработки ошибки, или ошибка будет сохранена в базе данных 1 вместе с другой информацией, если задан режим буферирования ошибки. Обычно применяются два режима одновременно. После анализа ошибки в режиме интерактивной обработки на основе данных, хранящихся в базах данных 1 и 2, разработчик принимает решение о необходимости дальнейшего проведения КДО. Внесение изменений в разрабатываемое ПО и исправление ошибки целесообразно выполнять с помощью кросс-средств на этапе статистической отладки. Если принято решение о необходимости дальнейшего проведения КДО, то управление будет передано модулю синхронизации процессов имитации, который запустит генератор ТИ, т.е. включит "реальный" масштаб времени. Далее управление будет передано ОПО.

2. Алгоритм работы программы обработки события "чтение состояния i-ой очереди".


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

3. Алгоритм работы программы обработки события "запрос на обслуживания i-ой очереди".

Данное событие произойдет только в том случае, когда ДО инициирует сигнал запроса на прерывание ЗПР. Останов "реального" времени, сбор и обработка статистики выполняются аналогично рассмотренным выше алгоритмам работы программ обработки событий. Программа обслуживания очередей в зависимости от времени ожидания пакетов в очереди, которое накапливается в таймерах 2, примет решение о необходимости изменения параметров алгоритма обслуживания очередей. Затем программой имитации сетевого узла будет определен следующий интервал поступления пакетов в очередь и сформировано входное воздействие, которые будут записаны соответственно в таймер 1 и в БВВ i-ой очереди. Модуль синхронизации процессов имитации запустит "реальное" время и управление будет передано реальной подпрограмме обслуживания запроса на прерывание i–ой очереди.