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

На данной странице представлен каталог программ, включенных в Фонд алгоритмов и программ Сибирского отделения РАН. Полный каталог программ и БД, включенных в Фонд, а также любые выборки по научным центрам, объединенным ученым советам и др. вы можете найти на данной странице.

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).
2012-04-25
Приближенное вычисление вероятности несвязности планарного графа

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

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

Разработанная программа позволяет сократить  вычисления и определить вероятность связности планарного графа по соответствующей матрице смежности двойственного графа, на основе определения асимптотических констант: (D) - размерность минимального разреза и (C) - количество таких разрезов. Алгоритм построения матрицы смежности двойственного графа и поиска соответствующих асимптотических констант описан в работе [1].
Условия эксплуатации :  
1. Расчет связности проводится на основе асимптотических формул, поэтому на входные данные (вероятность отказа ребра) налагаются ограничения -  вероятность отказа ребра должна быть порядка 1/N2, где N - количество вершин в исходном графе.
2. Вводимая матрица смежности должна быть симметричной, по диагонали стоят нули.

Функциональные возможности - разработанная программа позволяет исследовать планарные графы большой размерности (до 1000 вершин).

Инструментальные средства создания - Среда программирования Delphi 7.

[1] Tsitsiashvili G.Sh. Complete calculation of disconnection probability in planar graphs// Reliability: Theory and Applications. 2012. Vol. 1. No 1. P. 154-159.
2012-04-20
Пакет программ квадратичного программирования

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

Область применения - Исследование операций
Используемый алгоритм - метод приведенного градиента с использованием на этапе безусловной минимизации сопряженного градиента.
Алгоритм опубликован в статье: Котельников Е.А. "Применение приведенного градиента в квадратичном программировании". Сиб. журн. вычисл. математики. 2010.-Т.13, № 1.-С. 23-31.
Функциональные возможности - число строк в матрице ограничений не должно превышать 32765.
Инструментальные средства создания - Фортран
2012-04-17
Программный комплекс сетевого планирования и управления ("ПКСПП")

Назначение - Календарное  планирование проектов.

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

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

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

Алгоритм опубликован  в статьях:

  1. Ляхов О.А. Модель календарного планирования проектов с перераспределением нескладируемых ресурсов // Вестник Бурятского государственного университета /  - Улан-Удэ: Изд-во Бурят. госун-та, 2010. - Вып. 9: Математика и информатика. - С.119-124;
  2. Ляхов О.А. Модели передачи заданий в сетевом планировании сложных комплексов работ // IX Международная конференция "Проблемы функционирования информационных сетей": Материалы конференции, Новосибирск, 2006, с.174-179.

 Функциональные возможности -  Пакет рассчитан на следующие максимальные размеры входных данных: 32765 работ в сводной сетевой модели, 128 видов нескладируемых ресурсов, 256 типовых моделей.

   
Инструментальные средства создания - язык Фортран.
2012-01-26
Регистрация радиоизлучения и вариация фона. Radio Registration and Background Monitoring

Назначение - Программа предназначена для считывания данных с АЦП (Аналого-цифровой преобразователь) и визуализации снятых данных.
Область применения - Регистрация вторичных частиц космического происхождения при помощи детекторов ШАЛ (Широких атмосферных ливней) и антенны радиоизлучения.
Функциональные возможности - Работа с АЦП; визуализация вариации фона в реальном времени; сохранение и загрузка файлов; обработка сохраненных файлов; построение дифференциального и интегрального спектров;
В программе реализован алгоритм, разработанный авторами (Петров З. Е., Борщевский Д. С., Петров И. С.),  описание работы программы - в приложенном файле.

Инструментальные средства создания - Borland Delphi 6.0