Вернуться к списку проектов На главную страницу курса

Заказчик

Корзун Дмитрий Жоржевич, доцент, к.ф.-м.н., кафедра Информатики и математического обеспечения. Эл.почта: dkorzun@cs.karelia.ru. Раб.тел.: 711084. 217 кабинет.

Инструктор

Кулаков Кирилл Александрович. Эл.почта: kulakov@cs.karelia.ru. Раб.тел.: 711015. 215 каб.

Аннотация проекта

Данный проект выполняется в рамках развития системы Web-SynDic [1] - web-системы демонстрации, тестирования и экспериментального анализа синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений (НЛДУ). Она позволяет удаленно решать системы НЛДУ специального вида (ассоциированные с формальной грамматикой однородные системы НЛДУ - системы одАНЛДУ). В качестве основного алгоритма решения используется решатель syntactic [2]. Целью проекта является разработка технологии решения задач дискретного математического моделирования сетевых систем (математические модели формулируются в виде систем одНЛДУ и одАНЛДУ) и реализация этой технологии в рамках текущей версии системы Web-SynDic.

Первичные требования

В систему Web-SynDic должен быть добавлен модуль работы с дискретными математическими моделями маршрутизации в P2P-оверлеях.
В систему Web-SynDic должен быть добавлен модуль работы с дискретными математическими моделями структуры нагрузки канала передачи сетевого трафика.
Оба модуля должны иметь сходную логику внутреннего и внешнего устройства и функционировать аналогично уже имеющимся в системе Web-SynDic модулям работы с одиночной системой одАНЛДУ и множеством систем одАНЛДУ.

Предметная область

Системой одНЛДУ называется система линейных уравнений, коэффициенты которой - целые числа, а решения ищутся только в неотрицательных целых. В матричном виде: Ax=0. Если перенести неизвестные с отрицательными коэффициентами в правую часть, то получим систему с неотрицательными целыми коэффициентами: A'x=A"x. Система одАНЛДУ является системой одНЛДУ со специальной левой частью A'. Алгоритмы решения систем одНЛДУ и одАНЛДУ предназначены либо для нахождения некоторого частного ненулевого решения x*, либо для нахождения базисных решений (базис Гильберта).

Рассматриваются следующие сетевые системы: 1) одноранговые оверлейные сети (P2P-оверлеи) и 2) канал передачи трафика. В первом случае, известно, что дискретной математической моделью маршрутизации может выступать система одАНЛДУ, решения которой определяют маршруты. Во втором случае, известна модель структуры нагрузки канала также описываемая системой одАНЛДУ, решения которой определяют логические классы нагрузки.

Таким образом, система Web-SynDic может быть сделана инструментом математического моделирования подобных сетевых систем. Исследователь специфицирует исходные данные для модели (например, топологию P2P-оверлея или объемы переданных через канал данных). По этим данным строится модель в виде системы одАНЛДУ. Последняя решается с помощью уже встроенных в Web-SynDic алгоритмов. Полученные решения интерпретируются с точки зрения исходной задачи и результат визуализируется исследователю.

Ссылки

Сервер системы Web-SynDic.
http://websyndic.cs.karelia.ru/, http://www.cs.karelia.ru/software/index.php.ru.
Корзун Д. Ж. Grammar-Based Algorithms for Solving Certain Classes of Nonnegative Linear Diophantine Systems // Труды международного семинара Finnish Data Processing Week at the University of Petrozavodsk (FDPW'2000): Advances in Methods of Modern Information Technology. Vol. 3. Петрозаводск: Изд-во ПетрГУ, 2001. С. 52-67.

Разработчики

Презентация проекта (PDF)
(локальная копия web-ресурса 18.06.2007)

Кафедра Информатики и Математического Обеспечения