Моделирование и оптимизация распределенных вычислительных систем

• Автор: Пятаева, Елена Владимировна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Нижний Новгород
• Количество страниц: 166 с. : ил.

Оглавление
Введение

1. Обзор методов моделирования и оптимизации распределенной вычислительной системы

1.1. Обзор методов моделирования

1.2. Особенности современных распределенных вычислительных систем

2. Оптимизация структуры распределенной . вычислительной системы

2.1. Моделирование распределенной вычислительной системы

2.2. Формализация задачи оптимизации распределенной вычислительной системы

2.3. Обзор методов оптимизации распределенной вычислительной системы

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

3.1. Разработка методики решения задачи с помощью метода декомпозиции

3.2. Разработка методики решения подзадач
3.3. Разработка методики решения координационной задачи
3.4. Синтез алгоритма решения задачи
4. Практическая реализация алгоритма
4.1. Анализ влияния параметров разработанного алгоритма декомпозиции на эффективность проектирования распределенной вычислительной системы
4.2. Анализ эффективности метода декомпозиции
4.3. Описание тестовой задачи Выводы
Заключение Список литературы Приложение 1.
Краткое описание программы Приложение 2.
Список терминов Приложение 3.
Сведения о внедрении результатов диссертационной работы
ВВЕДЕНИЕ
Актуальность


Топологию сети, которая описывается квадратной матрицей Х элементы которой х’/у равны числу каналов связи между коммутационными панелями и устройствами; множеством векторов X, элементы которых равны числу каналов связи между абонентами и коммутационными панелями этажа . Описание кабелей. Описание коммутационных устройств. Описание коммутационных панелей. В п. Скр)1/х‘ +Ц(с'к +с1? Гихц+^с? В П. Определен вид поставленной задачи оптимального преобразования локальной сети - нелинейная целочисленная задача условной оптимизации. Сделан вывод о том, что размерность задачи оптимального преобразования локальных вычислительных сетей может изменяться от нескольких десятков до нескольких десятков тысяч узлов, следовательно, применение стандартных методов оптимизации невозможно. Произведен краткий обзор методов математического программирования. В главе 3 разрабатывается алгоритм оптимального проектирования структуры локальной вычислительной сети. В п. Метод декомпозиции состоит из нескольких этапов. Первый - разбиение всей системы на подсистемы по территориальному признаку. Все узлы сети, которые принадлежат одному этажу, объединяются в одну подсистему. Предложенный способ разбиения учитывается в математической постановке задачи, и предназначен для избавления от большой разреженности матриц, описывающих соединение узлов сети. Для каждой полученной подсистемы решается задача оптимизации. Данный способ разбиения гарантирует отсутствие необходимости многократного возвращения к решению подзадач. Для решения задач соединения абонентов и коммутационных панелей, расположенных на одном этаже, в соответствии с требованиями структурированных кабельных систем, применяется адаптированный метод построения минимального дерева. Из всего множества узлов подсистемы выбирается узел - коммутационная панель. Далее для всех дуг подсети рассчитывается вес. Для расчета информационных потоков сети применяется алгоритм статистического мультиплексирования потоков в условиях самоподобия трафика. Рассматриваемый трафик Р представляет суперпозицию пакетов, генерируемых различными источниками в определенный момент времени Ут. В условиях начальной неопределенности, количество источников м, являющимися активными на данный момент времени независимы и распределены по закону Пуассона. Время генерации пакетов и их количество независимы от количества источников и моментов времени. Рассчитанное количество кабелей сравнивается с реальным, уже существующим количеством. Последовательно к коммутационной панели подсоединяются дуги наименьшего веса. Хі - рассчитанное количество кабелей, . В противном случае, необходимо удалить старые кабели и проложить кабели нового типа. По рассчитанному количеству кабелей, подключаемых к коммутационной панели, определяется ее тип из подмножества коммутационных панелей, существующих на данный момент времени. Если данное подмножество оказывается пустым, то тип коммутационных панелей определяется из базы данных. Следующий этап решения задачи оптимального преобразования сети -решение координационной задачи. КУ) и коммутационные устройства между собой. Для решения координационной задачи применяется генетический алгоритм, который представляет собой модель размножения живых организмов. На первом шаге, исследуемая система представляется в виде хромосом а^ш(а а2/,,. Хромосомы состоят из генов. Для кодирования данных задачи в хромосому предложено использовать следующее правило: гены хромосомы соответствуют значениям матрицы X' в следующем порядке с учетом этажности здания: ген Д- - количество кабелей соединяющих ГКП 1 -КУ^ где /, j - номера этажей, / Фу; у/; - количество кабелей соединяющих КУ -КУ;, где /,у - номера этажей,, / фу. Для кодирования используются специально разработанные хэш-функции. Так как хромосома представляет собой две независимые части У? Для решения задачи оптимального проектирования распределенных вычислительных систем применяются операторы скрещивания и оператор мутации. При этом мутация происходит в заранее строго определенных пределах - новое значение гена не может быть больше некоторого значения, определяемых правилами генерации начальных популяций хромосом.