Разработки СО РАН - каталоги программ и БД

Поиск по каталогам:

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

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

Постановка задачи. Есть 2 машины и множество работ. Каждая работа сначала выполняется на первой машине, а после этого может выполнятся на второй машине. Во время выполнения работы на первой машине происходит загрузка работы в буфер. После выполнения работы на второй машине, она удаляется из буфера. Размер буфера ограничен, поэтому нельзя просто выполнить работы на первой, а затем на второй машине.  Необходимо найти порядок выполнения работ, чтобы выполнить все работы за минимальное время.

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

Алгоритм опубликован в следующей работе: Кононова П.А. Нижние и верхние оценки длины оптимального расписания презентаций медиа-объектов. Дискретный анализ и исследование операций 2012, Т 19, N 1 стр 59-73 
2012-06-13
Программная система ТОПАС для отображения параллельных программ на архитектуру вычислительных систем

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

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

Используемый алгоритм - Программная система основана на новых алгоритмах оптимизации, включая алгоритм эволюционных вычислений, генетический алгоритм и нейронные алгоритмы. Алгоритмы и описание системы опубликованы в монографии:  Монахов О. Г.,  Монахова Э. А. Параллельные системы с распределенной памятью: управление ресурсами и заданиями. Новосибирск: Изд-во ИВМиМГ СО РАН, 2001.  168с.

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



Инструментальные средства создания - Java, Eclipse

В приложении приведен пример визуализации работы программы.
2012-06-09
Программа, иллюстрирующая аналитические преобразования в методе интегрирования по частям

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

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

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

Рассматриваются интегралы сложной функции вида:  ∫ P(x)Q(x) dx, где P(x) = ax+b    (a, b - коэффициенты, автоматически генерируемые в условии задачи), P(x) - непрерывно дифференцируемые функции от x. Функция Q(x) принимает вид одной из трех функций: Q(x) = sin(kx), Q(x) = cos(kx), Q(x) = ekx, где k - коэффициент, автоматически генерируемый в условии задачи. Функции P, Q имеют непрерывную производную на всём множестве определения. 

Алгоритм описан в статье: Яриков В.В. Тренажер по нахождению первообразной сложной функции для интеграла вида P(x)Q(x) // Международный журнал «Образовательные технологии и общество» – 2011. – т.14, № 4, – С. 368–376.

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

Инструментальные средства создания – Java 6, среда Eclipse.
2012-06-08
Программа синтеза оптимальных циркулянтных сетей

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

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

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

Алгоритм опубликован в монографии:  Монахов О. Г.,  Монахова Э. А. Параллельные системы с распределенной памятью: структуры и организация взаимодействий. Новосибирск: Изд-во СО РАН, 2000.  242с.

Функциональные возможности - Программа позволяет синтезировать циркулянтные сети со степенью вершин до 20 и с числом вершин до 240 тысяч.



Инструментальные средства создания - Язык: C. ОС: Windows, Linux, Unix

В приложении приведен пример работы программы.
2012-06-04
XNS - eXtended Network Simulator - программный симулятор процессов управления качеством сервиса в беспроводных сетях стандарта IEEE 802.16 (WiMax)

Назначение      Программная система eXtended Network Simulator (XNS) предназначена для тестирования работы алгоритмов обеспечения качества сервиса - QoS (Quality of Service) в сетях широкополосного беспроводного доступа (ШБД).

Область применения    Система может применяться для тестирования модулей планировщиков QoS сети стандарта IEEE 802.16d (WiMax) в диапазоне рабочих нагрузок от 0 до 100% от максимальной пропускной способности (бит/с), предоставляемой радиоканалом. При этом физический уровень не моделируется. Обмен данными по радиоканалу заменен обменом по сети Ethernet.

Используемый алгоритм [1, 2]:

  1. Пользователь запускает систему, используя стартовый сценарий.
  2. Симулятор считывает из файла XML необходимые для работы параметры.
  3. Стартовый сценарий запускает на машине-сервере приемник сетевых пакетов и регистраторы трафика (серверную часть генератора IP-трафика Iperf).
  4. Модуль "Драйвер" системы XNS  производит непрерывное чтение сетевых пакетов из виртуального сетевого интерфейса TUN/TAP и размещает пакеты в очередях данных. В случае варианта виртуального интерфейса TUN из интерфейса считываются (и могут быть записаны) сформированные по правилам протокола TCP/IP датаграммы, то есть с IP-заголовком и полем полезной нагрузки. В случае варианта TAP из виртуального интерфейса считываются ethernet-пакеты с MAC-заголовком и полем полезной нагрузки, представляющим собой IP-пакет. В настоящей версии симулятор работает только с вариантом виртуального интерфейса TUN.
  5. Стартовый сценарий запускает несколько экземпляров клиентской части генератора сетевого трафика Iperf, которые генерируют IP-пакеты c заданными размером и интенсивностью и записывают их в виртуальный сетевой интерфейс TUN/TAP.
  6. Контроллер периодически запускает модуль планировщика QoS, который на основе заказанных параметров качества, а также заданных параметров радиоканала и информации о заполненности очередей, формирует карты заполнения кадра WiMax (DL-MAP и UL-MAP (Downlink-MAP и Uplink-MAP)). Карты содержат указания о том, сколько данных и из каких очередей должно быть отправлено в данном кадре. В настоящей версии симулятор позволяет имитировать передачу данных только в направлении Downlink (от базовой станции к абонентским).
  7. Карты кадра передаются в модуль "Драйвер".
  8. Драйвер производит разбор полученных карт и на их основе формирует единый сетевой пакет, содержащий служебные сообщения, а также данные из очередей драйвера (сгенерированные генератором трафика). Полученный единый сетевой пакет является моделью сетевого кадра (фрейма) стандарта IEEE 802.16d (WiMax). В случае превышения размера в 65535 байт (максимально допустимый для датаграмм TCP/IP) фрейм может быть разделен на несколько последовательно отправляемых пакетов.
  9. Модель фрейма в виде сетевого пакета передается по реальному сетевому интерфейсу  Ethernet на машину-сервер.
  10. На машине-сервере приемник сетевых пакетов осуществляет разбор модели фрейма с целью разделения служебных сообщений и пакетов данных. Выделенные пакеты данных в виде IP-датаграмм записываются в виртуальный сетевой интерфейс TUN/TAP.
  11. Регистраторы трафика считывают пакеты из виртуального сетевого интерфейса, и, по окончании приема пакетов, формируют журнальный файл, содержащий статистическую информацию о принятых сетевых пакетах: общее количество переданных  пакетов, их суммарный размер, средняя пропускная способность, количество потерянных пакетов, количество пакетов отброшенных по тайм-ауту и т.д.
  12. Регистраторы трафика (серверная часть) формируют ответные сообщения, содержащие статистику принятого трафика. Ответные сообщения в виде IP-пакетов записываются в виртуальный сетевой интерфейс.
  13. Приемник сетевых пакетов осуществляет чтение IP-пакета со статистическими данными из виртуального интерфейса и отправляет его в по реальному сетевому интерфейсу Ethernet на машину-клиент.
  14. На машине-клиенте модуль "Драйвер" принимает и записывает ответные сообщения  в виртуальный интерфейс.
  15. На основе полученных  ответных сообщений со статистическими данными экземпляры клиентской части генераторов трафика формируют файлы журналов и выключаются.
  16. Симулятор, отработав заданное время, останавливается.
  17. Стартовый сценарий останавливает на машине-сервере регистраторы трафика и приемник сетевых пакетов.

 Таким образом, сетевой трафик, генерируемый клиентской частью Iperf, пропускается через модуль "Драйвер" симулятора XNS, затем доставляется на машину-сервер по TCP-туннелю (поверх сегмента сети Ethernet) в виде сетевых пакетов, моделирующих на логическом уровне фрейм WiMax. На машине-сервере приемник пакетов "распаковывает" модель фрейма, извлекает сгенерированные на клиенте IP-пакеты и передает их через виртуальный интерфейс серверной части генератора трафика Iperf. Серверная часть Iperf накапливает статистику и формирует пакет, отсылаемый обратно на машину-клиент, где расположен симулятор и клиентская часть Iperf. Обратная связь не затрагивает алгоритмы обеспечения QoS.

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

Выбор виртуального сетевого интерфейса TUN/TAP продиктован основным требованием: продемонстрировать работу алгоритмов обеспечения QoS в условиях, приближенных к реальным, и измерить объективными средствами качество работы алгоритмов.

Использование виртуального сетевого интерфейса избавляет от необходимости создания сетевых драйверов (в терминах ОС Линукс) и позволяет тестировать работу алгоритмов обеспечения QoS на примере любых сетевых приложений, ориентированных на стек TCP/IP.

Литература:

1. Бойченко И.В., Бортников Е.В., Немеров А.А. Программный симулятор процессов управления качеством сервиса в беспроводных сетях стандарта IEEE 802.16 // Журнал "Доклады Томского государственного университета систем управления и радиоэлектроники" № 1 (23), часть 1, 2011 год. ISSN 1818-0442 (полнотекстовая версия http://www.tusur.ru/filearchive/reports-magazine/2011-23-1/143.pdf)

2. Boichenko I.V., Bortnikov E.V. Linux-Based Test-Bed for Testing of QoS Subsystems in Broadband Wireless Networks [Электронный документ]. - Режим доступа: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=6... , для зарегистрированных пользователей.

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

Пользовательский интерфейс: консольный (командная строка)

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

Количество абонентских станций: до 22
Общее количество потоков данных (сервисных потоков) в системе: до 45
Типы сервисных потоков: Best Effort (BE), Unsolicited Grant Service (UGS)
Типы модуляций: BPSK, QPSK 1/2, QPSK 3/4, 16-QAM 1/2, 64-QAM 2/3, 64-QAM 3/4 .   

Система выполняет следующие функции:

  1. Задание параметров базовой станции.
  2. Задание сервисных потоков и соединений массивом одного типа в статическом режиме, то есть при инициализации базовой и абонентских станций.
  3. Задание карты модуляций для каждой абонентской станции в статическом режиме.
  4. Моделирование наполнения очередей для каждого соединения (абстрагирование пользовательских данных от вышестоящего уровня) на базовой и абонентской станциях.
  5. Моделирование отправки данных по радиоинтерфейсу на базовую и абонентскую станции, то есть моделирование работы драйвера физического уровня без учета фрагментации пакетов.
  6. Формирование карт DL-MAP и UL-MAP планировщиком QoS по запросу симулятора, для каждого следующего фрейма, с учетом параметров QoS, карты модуляций и загруженности очередей.
  7. Ведение журнала событий отдельных сущностей базовой станции, абонентской станции и симулятора, в целом.
  8. Мониторинг производительности сети (пропускная способность в течение определенного времени, % использования канала)

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

Информацию этого отчета можно представить в виде таблицы:

result table

DL - направление вещания - Down Link - от базовой станции к абонентским.

Во второй строке заголовка показано количество запускаемых потоков данных. Для каждого количество потоков запускается генератор тафика с полосой, составляющей   50%   75%   100%   от максимально возможной полосы при данной модуляции.

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

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

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

 Инструментальные средства создания    Язык программирования: С/С++. Код компилируется компиляторами коллекции GCC (GNU Compiler Collection – Коллекция компиляторов GNU) версии 3.4.1. Модуль QoS поставляется в виде динамической библиотеки (расширение файла - .so).