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

Консультант(ы): 

Сомов С. К. (ИПУ РАН, Лаборатория 20)

Ключевые слова: 

Тематика проводимого исследования: 

Управление в социальных сетях и организационных структурах

Приобретаемые знания: 

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

Приобретаемые навыки и умения: 

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

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

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

Тип проекта: 

Практика / научно-исследовательская работа

Период практики: 

3 недели

Краткое описание проекта: 

Рассматривается распределенная система обработки данных, функционирующая на базе компьютерной сети из 20-ти узлов. В 6-ти узлах системы размещены реплики используемого в системе массива данных. Задана топология распределенной системы и распределение реплик по 6 узлам системы. Необходимо заполнить матрицу кратчайших путей между каждым из 20 узлов системы и узлами, в которых размещены реплики. Для каждого узла системы ищется ближайший узел с репликой. Ближайшим к узлу k (k=1,…,20) системы является узел m c репликой данных, путь к которому от узла k имеет наименьшую длину. Необходимо разработать программу поиска для каждого узла системы кратчайших путей K ближайшим узлам с репликами массивов данных. Можно использовать любой известный алгоритм поиска кратчайших путей в графе.

Задания на практику: 

На рисунке представлен граф - топология компьютерной сети, на основе которой работает распределенная система. Узлы пронумерованы, дуги раскрашены их длинами. Реплики массива данных размещены в узлах: 1, 3, 5, 11, 13, 18. Необходимо найти кратчайшие пути для маршрутизации запросов к данным реплик, размещенным в перечисленных узлах.

Результат выполнения проекта: 

Отчет о проделанной работе (или курсовая работа): - описание поставленной задачи, - исходные данные, - описание алгоритма поиска кратчайших путей, - выходные данные: таблица с длинами найденных кратчайших узлов, таблица с перечнем узлов сети, входящими в каждый найденный путь (таблица в MS Word 2010 или *.pdf или Eхel 2010), хорошо комментированный и структурированный код программы.