Содержание к диссертации
Введение 4
1. Обзор методов моделирования и оптимизации распределенной вычислительной системы 17
1.1. Обзор методов моделирования 17
1.2. Особенности современных распределенных вычислительных систем 21
Выводы 43
2. Оптимизация структуры распределенной вычислительной системы , 44
2.1. Моделирование распределенной вычислительной системы 44
2.2. Формализация задачи оптимизации распределенной вычислительной системы 58
2.3. Обзор методов оптимизации распределенной вычислительной системы 67
Выводы 74
3. Синтез алгоритма структурной оптимизации распределенной вычислительной системы 75
3.1. Разработка методики решения задачи с помощью метода декомпозиции 75
3.2. Разработка методики решения подзадач 85
3.3. Разработка методики решения координационной задачи 89
3.4. Синтез алгоритма решения задачи 101
Выводы 104
4. Практическая реализация алгоритма 105
4.1. Анализ влияния параметров разработанного алгоритма декомпозиции на эффективность проектирования распределенной вычислительной системы 105
4.2. Анализ эффективности метода декомпозиции 121
4.3. Описание тестовой задачи 124
Выводы 138
Заключение 139
Список литературы 140
Приложение 1. Краткое описание программы 150
Приложение 2. Список терминов 156
Приложение 3. Сведения о внедрении результатов диссертационной работы 158
Введение к работе
Актуальность темы. Внедрение вычислительной техники в процессы организации и управления предприятиями произошло в середине 20 века. Вслед за появлением первых компьютеров, ориентированных на выполнение специфических задач, компьютерные технологии стали быстро развиваться. Уже в 70 годах появившиеся мини-компьютеры, занимавшие в отличие от предыдущего поколения небольшую площадь, привели к появлению концепции распределения компьютерных ресурсов по предприятию. Однако, компьютеры продолжали работать автономно, не предоставляя пользователям возможности распараллеливания вычислений и совместного использования ресурсов. С течением времени требования предприятий увеличились, и стали появляться первые локальные вычислительные сети. Сети организовывались в зависимости от потребностей и возможности пользователей в количестве соединенных между собой абонентов. При этом кабели, соединявшие устройства сети прокладывались поверх предыдущих, не обеспечивая безопасность системы, ни открытости архитектуры. Повреждение кабельной проводки приводило к прокладыванию новых кабелей поверх предыдущих, либо к удалению неполадок, сопровождавшихся повреждением действующей линии связи. Постепенное увеличение количества абонентов сети приводило к тому, что по мере возникновения потребностей и средств сети расширялись эмпирическими способами. В настоящее время практически в каждой организации существует локальная сеть, позволяющая быстро и качественно обрабатывать и транслировать информацию. Технологии, состоящие из большого количества компонент, связных между собой, способных передавать и обрабатывать данные называются распределенными вычислительными системами. Особенностью распределенных вычислительных систем является то, что для пользователя незаметно наличие многочисленного оборудования для передачи данных. Многие организации заинтересованы в возможности преобразования существующих у них на данный момент локальных сетей таким образом, чтобы обеспечить требуемый уровень защиты кабельной проводки, обеспечить необходимую скорость передачи данных. Развитие технологий распределенных вычислительных систем идет в нескольких направлениях. Во-первых, исследуют возможности мэйнфрэймов, то есть больших компьютеров, занимающих огромную площадь (до нескольких зданий), которые представляют собой многотерминальные системы с разделением времени. С другой стороны появилась тенденция к уменьшению размеров компьютеров, совместно с развитием беспроводных технологий передачи данных. Прогнозируется создание «карманных» компьютеров, которые всегда будут иметь доступ к сети. Однако, на данный момент времени существование огромного количества локальных сетей на предприятиях и организациях по всему миру, говорит об остроте проблемы проектирования распределенных вычислительных систем. Важным аспектом данной проблемы является вопрос модернизации сети, так как на многих предприятиях уже существуют локальные сети, возникшие в результате стихийного увеличения абонентов сети.
Целю работы является моделирование и оптимизация распределенных вычислительных систем для оптимизации структуры при заданных ограничениях на ее технические характеристики.
Состояние рассматриваемых вопросов. Проблемой оптимизации распределенных вычислительных систем занимались многие российские и зарубежные ученые: Янбых Г.Ф., Зайченко Ю.П., Вишневский В.М., Мартин Д.Ж., Глушаков В.М., Гурвиц М., Закер К., Казаков СВ., Кульгин М.В., Олифер В.Г. и др. Тем не менее, задача оптимального проектирования и модернизации распределенных вычислительных систем достаточно подробно не изучалась и для ее решения в настоящее время применяются эмпирические методы. Основной недостаток существующих методов состоит в том, что модернизация спроектированных систем практически невозможна, или осуществляется с большим трудом частичной заменой дорогостоящего оборудования. С другой стороны, существующие методы решения задач оптимизации распределенных вычислительных систем ориентированы на решение задач определенной размерности, следовательно, не подходят для решения задачи оптимизации распределенных вычислительных систем, так как размерность сетей может изменяться от десятков абонентов до нескольких тысяч.
Задачи работы:
1. Формализация задачи оптимального проектирования распределенных вычислительных систем.
2. Разработка алгоритма решения задачи оптимального проектирования распределенных вычислительных систем.
3. Применение разработанного алгоритма оптимизации структуры системы для оптимального преобразования распределенных вычислительных систем.
4. Нахождение минимальной по стоимости структуры распределенной вычислительной системы исходя из требований возможности ее преобразования.
Основные положения, выносимые на защиту:
1. Математическая модель распределенной вычислительной системы позволяет осуществить ее структурную оптимизацию.
2. Алгоритм оптимизации структуры вычислительной системы, основанный на методе декомпозиции, позволяет находить квазиоптимальную по стоимости структуру системы любой размерности.
3. Алгоритм оптимизации структуры вычислительной системы, основанный на методе декомпозиции, уменьшает время решения задачи на 60-80% по сравнению с существующими способами оптимизации.
Научная новизна диссертационной работы состоит в следующем: 1. Сформулирована и формализована задача оптимального проектирования структуры распределенной вычислительной системы на примере локальной вычислительной сети здания. Критериями оптимизации являются стоимость создания или время задержки передачи информации.
2. Применен метод декомпозиции для решения задачи оптимального проектирования структуры распределенной вычислительной системы.
3. Разработанный метод разбиения задачи оптимального проектирования распределенной вычислительной системы на независимые подзадачи имеет существенно большую эффективность по сравнению с существующими методами разбиения.
4. Разработано решение координационной задачи с использованием генетического алгоритма.
Практическая ценность.
1. Предложенный метод позволяет сокращать затраты на создание новой локальной сети здания на 75%, и время задержки передачи данных на 70% по сравнению с существующими методами оптимизации при размерности здания более 2 этажей.
2. При оптимизации структуры сети, расположенной на одном этаже, находится оптимальная по стоимости или производительности сеть.
3. Предложенный метод позволяет преобразовывать локальные сети здания, сокращая затраты на 85% по сравнению с адаптированными к задаче преобразования структуры сети методами.
4. Созданный пакет программ позволяет автоматизировать расчет параметров сети.
Методы исследования. Для изучения и решения поставленных задач использовались элементы теории моделирования, теории множеств, методы математического программирования, теории графов, теории телетрафика, теории надежности.
Сведения о внедрении Результаты диссертационной работы были внедрены в следующих организациях: ФГУП «Завод Электромаш», ЗАО «Нижегородская металлургическая компания», а так же внедрены в учебный процесс НГТУ, что подтверждается актами о внедрении (Приложение 3).
Публикации результатов диссертации были произведены в 14 работах, из них одна статья, материалы трех конференций, десять тезисов докладов, две публикации в сборниках на английской языке.
Апробация результатов диссертации. Были сделаны доклады на 14 конференциях, из них 5 региональных, 3 Всероссийских, 6 международных. По результатам работы награждена следующими Дипломами (Приложение 3):
1. Диплом 3 Всероссийской молодежной научно-технической конференции «Будущее технической науки», Н.Новгород;
2. Диплом 9 Международной научно-практической конференции «Современные техника и технологии», Томск;
3. Диплом конгресса 5 International Congress of the Asia-Pacific region countries, Vladivostok;
4. Диплом № 966 лауреата стипендии академика Г.А. Разуваева;
5. Диплом стипендии правительства Российской Федерации.. Структура и объем работы. Работа состоит из введения, четырех глав,
заключения, списка литературы и трех приложений. Общий объем работы без приложений составляет 149 страниц текста, 36 иллюстраций. Список литературы включает 109 наименований отечественных и зарубежных авторов.
Во введении обоснована актуальность темы диссертации, сформулированы ее цель, практическая значимость, научная новизна и основные положения, выносимые на защиту.
Глава 1 посвящена обзору методов моделирования и определению особенностей современных распределенных вычислительных систем. В качестве метода моделирования выбрано имитационное моделирование (на примере моделирования локальной вычислительной сети здания). В главе выделены основные этапы проектирования систем, определены их характерные особенности. Описаны основные топологии распределенных вычислительных систем. Кратко описываются наиболее распространенные сетевые технологии, используемые при проектировании локальных сетей здания в настоящее время - Ethernet, FDDI, ATM, Token Ring. Приводятся основные характеристики
кабельной системы. Описаны три типа информационных носителей, которые используются при создании локальных сетей: волоконно-оптические кабели, медные кабели, беспроводные носители. Выделены основные характеристики информационных носителей. Определены типы коммутационных устройств, которые используются в локальных сетях - коммутаторы и маршрутизаторы различных уровней.
В главе 2 производится формализация задачи оптимального проектирования распределенной вычислительной системы. Приведен сравнительный анализ экономической эффективности проектирования новых сетей, преобразования сетей и удаления сетей по временным и экономическим параметрам. В данной главе отмечается отсутствие алгоритмов решения задач преобразования сети.
Рассмотрены три основных критерия эффективности локальных сетей здания - производительность, надежность и стоимость. В качестве критерия оптимизации в зависимости от специфики решаемой задачи предлагается взять критерий стоимости, т.е. наименьших затрат на создание локальной вычислительной сети, или критерий производительности (времени задержки передачи данных). Определены способы расчета количества кабеля. Рассмотрены виды трафика, передаваемого по локальным сетям. Приведен метод расчета трафика.
С учетом особенности сетей здания и их основных критериев функционирования, в п. 2.2. сформулирована задача оптимального проектирования структуры сети. Структура представляется в виде ненаправленного смешанного раскрашенного графа с четырьмя типами вершин (абонентов сети, коммутационных устройств, горизонтальных коммутационных панелей и вертикальных коммутационных панелей). Закрашенные вершины и дуги представляют собой компоненты сети, существующие на данный момент времени.
Все параметры, описывающие локальные сети разбиваются на два множества - описывающие каналы связи и узлы сети. Множество узлов сети разбиваются на три подмножества - абоненты, коммутационные панели, коммутационные устройства. Абоненты (А) характеризуются предполагаемой интенсивностью информационного обмена/, скоростью передачи данных q, зависящей от выбранной сетевой технологии A = (f,q). Коммутационные панели Кр характеризуются моделью ркР, количеством портов пкр, стоимостью скр коммутационной панели ркр типа Кр =(pRP,nKp,cRp ).Коммутационные устройства К характеризуются моделью рк, количеством портов пк, размером коммутационной таблицы Ак, скоростью передачи данных v#, временем задержки tic, алгоритмом маршрутизации, стоимостью Сщ коммутационного устройства рк типа К = (рк, пк, AK,v ,t ,ср). Параметры, задаваемые при проектировании сети можно разбить на три группы:
1. Параметры, являющиеся характеристиками узлов сети. К этим параметрам относятся число узлов сети п; предполагаемая интенсивность информационных потоков между узлами сети (матрица тяготения), записываемая в виде квадратной симметричной матрицы F; скорости передачи, поддерживаемые каждым абонентом; количество этажей здания; описание существующих узлов сети.
2. Характеристики сетевых каналов связи. Этими параметрами являются скорость передачи информации q{; длины каналов связи между узлами сети, записываемые в виде нескольких векторов U = (L ],L 2,...,L J, соответствующих каналам связи между абонентами этажей и коммутационным панелям этажей; длины каналов связи между коммутационными панелями и устройствами, записываемых виде квадратной симметричной матрицы L.
3. Параметр, характеризующий существующие компоненты сети. Представляется в виде двух матриц - матрицы существования узлов сети G, элементы которой представляют собой описание узлов, если они существуют, и квадратной симметричной матрицы существования кабелей в сети R, элементы которой представляют собой описания существующих каналов связи и их количество. В процессе преобразования структуры сети требуется определить:
1. Топологию сети, которая описывается квадратной матрицей Х\ элементы которой x ij равны числу каналов связи между коммутационными панелями и устройствами; множеством векторов X, элементы которых равны числу каналов связи между абонентами и коммутационными панелями этажа.
2. Описание кабелей.
3. Описание коммутационных устройств.
4. Описание коммутационных панелей.
В п. 2.2 задаются ограничения на параметры задачи и определяется целевая функции для задачи оптимизации по критерию стоимости
/=1/=1 /=iy=/ /=i /=i
и для задачи оптимизации по критерию производительности (времени задержки передачи данных)
/=1 ,-=1 /=1 ,=1 /=/+1
где X - число каналов связи между коммутационной панелью и абонентами
этажа і,
X - число каналов связи между коммутационными панелями и устройствами,
С - стоимость кабеля,
L - длина кабеля между коммутационными панелями и устройствами,
L - длина кабеля между коммутационной панелью и абонентами этажа
Ср- стоимость коммутационного устройства,
СКр - стоимость коммутационной панели,
су - стоимость установки коммутационного оборудования,
Г- время задержки передачи данных в коммутационных устройствах,
І- время задержки передачи данных в кабелях.
В П. 2.3. проведен анализ существующих методов оптимизации распределенных вычислительных систем. Определен вид поставленной задачи оптимального преобразования локальной сети - нелинейная целочисленная задача условной оптимизации. Сделан вывод о том, что размерность задачи оптимального преобразования локальных вычислительных сетей может изменяться от нескольких десятков до нескольких десятков тысяч узлов, следовательно, применение стандартных методов оптимизации невозможно. Произведен краткий обзор методов математического программирования.
В главе 3 разрабатывается алгоритм оптимального проектирования структуры локальной вычислительной сети. В п.3.1 на основе метода декомпозиции разрабатывается алгоритм решения задачи оптимального проектирования сети. Метод декомпозиции состоит из нескольких этапов. Первый - разбиение всей системы на подсистемы по территориальному признаку. Все узлы сети, которые принадлежат одному этажу, объединяются в одну подсистему. Предложенный способ разбиения учитывается в математической постановке задачи, и предназначен для избавления от большой разреженности матриц, описывающих соединение узлов сети. Для каждой полученной подсистемы решается задача оптимизации. Данный способ разбиения гарантирует отсутствие необходимости многократного возвращения к решению подзадач.
Для решения задач соединения абонентов и коммутационных панелей, расположенных на одном этаже, в соответствии с требованиями структурированных кабельных систем, применяется адаптированный метод построения минимального дерева. Из всего множества узлов подсистемы выбирается узел - коммутационная панель. Далее для всех дуг подсети рассчитывается вес. В качестве веса дуги, соединяющей выбранную вершину с коммутационной панелью этажа, используется стоимость полученного кабельного канала в задаче оптимизации по критерию стоимости и производительность при оптимизации по критерию производительности, зависящие от информационных потоков всей сети. Для расчета информационных потоков сети применяется алгоритм статистического мультиплексирования потоков в условиях самоподобия трафика. Рассматриваемый трафик F представляет суперпозицию пакетов, генерируемых различными источниками в определенный момент времени VT. В условиях начальной неопределенности, количество источников w, являющимися активными на данный момент времени независимы и распределены по закону Пуассона. Время генерации пакетов и их количество независимы от количества источников и моментов времени. Рассчитанное количество кабелей сравнивается с реальным, уже существующим количеством. Последовательно к коммутационной панели подсоединяются дуги наименьшего веса. Значение целевой функции для подзадач рассчитывается по следующей формуле в задаче
оптимизации по критерию стоимости XS(C +/)//Лу , при решении задачи
/=1./=1
ОПТИМИЗаЦИИ ПО Критерию ПрОИЗВОДИТеЛЬНОСТИ, ПО формуле 2_/,t jXj ,
i=\j=\J
Для расчета количества кабелей применяется следующая формула xR — xt — ri,
где Xj - рассчитанное количество кабелей, л;д - количество кабелей, которое существует на данный момент, при условии что xt HXR- кабели одного типа. В противном случае, необходимо удалить старые кабели и проложить кабели нового типа. По рассчитанному количеству кабелей, подключаемых к коммутационной панели, определяется ее тип из подмножества коммутационных панелей, существующих на данный момент времени. Если данное подмножество оказывается пустым, то тип коммутационных панелей определяется из базы данных.
Следующий этап решения задачи оптимального преобразования сети -решение координационной задачи. Задача координации в случае модернизации локальной вычислительной сети представляется следующим образом: необходимо соединить горизонтальные коммутационные панели (ГКП) с
коммутационными устройствами (КУ) и коммутационные устройства между собой. Для решения координационной задачи применяется генетический алгоритм, который представляет собой модель размножения живых организмов. На первом шаге, исследуемая система представляется в виде хромосом а{.=( а1 І а\,..., Д). Хромосомы состоят из генов. Для кодирования данных задачи в хромосому предложено использовать следующее правило: гены хромосомы соответствуют значениям матрицы X в следующем порядке с учетом этажности здания: ген fij - количество кабелей соединяющих ГКП ; -КУ,-, где /, j - номера этажей, і Ф]; у/}- - количество кабелей соединяющих КУ І -КУ j, где /, j - номера этажей,, / Ф]. Для кодирования используются специально разработанные хэш-функции. Генерация начальной популяции хромосом производится случайным образом в пределах, определенных следующими правилами: количество соединений горизонтальной коммутационной панели с коммутационными устройствами других этажей не должна превышать количества абонентов, расположенных на данном этаже 2_ Р v - п"\ і количество соединений одного коммутационного устройства с другими не должно превышать количества этажей 0 Г р.. z . Обратное преобразование j хромосомы осуществляется с помощью разработанных формул. Длина хромосомы зависит от количества этажей и определяется формулой г ц = z(z -1) + ] (z - k). Для работы алгоритма используются традиционные операторы генетического алгоритма. Так как хромосома представляет собой две независимые части fi и у/, то применять операторы генетического алгоритма можно ко всей хромосоме и к первой и второй ее части независимо. Для решения задачи оптимального проектирования распределенных вычислительных систем применяются операторы скрещивания и оператор мутации. При этом мутация происходит в заранее строго определенных пределах - новое значение гена не может быть больше некоторого значения, определяемых правилами генерации начальных популяций хромосом.
Рассмотрены варианты отбора хромосом для операций генетического алгоритма. Определены критерии останова работы генетического алгоритма. После работы генетического алгоритма из конечной популяции выбирается та особь, которая дает минимальное значение целевой функции.
В главе 4 анализируется эффективность работы полученного алгоритма. П.4.1 посвящен анализу влияния параметров на эффективность проектирования локальной вычислительной сети здания. Определены параметры, влияющие на эффективность работы алгоритма.
При определении метода выбора родительской пары исследовалось несколько схем: случайный выбор, селективный, инбридинг, аутбридинг, сочетание инбридинга и аутбридинга. Наиболее хорошие результаты показало совместное применение инбридинга и аутбридинга. Данная схема выбора приводила к получению достаточно хороших решений за короткое время работы алгоритма.
В качестве метода отбора хромосом в новое поколение предлагается использование параллельного элитного метода, который заключается в следующем: одновременно генерируются несколько популяций хромосом, которые развиваются независимо друг от друга. Через (z-І) поколений происходит скрещивание между популяциями. Это позволяет избежать быстрой сходимости алгоритма. Проведенные эксперименты показали что применение данного метода отбора хромосом эффективнее других на 0,6-0,9.
Вероятности проведения операций мутации и скрещивания так же влияют на производительность алгоритма. Проведенные исследования показали, что наиболее эффективными являются вероятности мутации 0,6 - 0,8 и скрещивания 0,9-1.
Показано, что применение оператора скрещивания ко всей хромосоме влечет за собой стадии «ремонта» хромосом, а следовательно, увеличивает время поиска решения. Это связано с тем, что первая и вторая части хромосомы отвечают за разные параметры системы. Применение оператора мутации не связано с делением хромосомы на разные части, так как мутация одного гена происходит в заранее определенных условиями задачи пределах.
П.4.2 посвящен сравнительному анализу разработанного метода декомпозиции и существующих методов математического программирования -метода простого перебора и генетического алгоритма. Так как возможности метода полного перебора ограничены размерностью задачи, то опыты проводились на сетях с количеством узлов до 10, расположенным на одном этаже здания. Полученные решения эквивалентны решениям, полученным в результате работы метода полного перебора вариантов. Это связано с тем, что модифицированный метод поиска минимального дерева, использованный для организации соединения абонентов этажа дает оптимальные результаты для задач, сравнительно небольшой размерности. Небольшая размерность оптимизируемых сетей достигается применением метода декомпозиции. Размерность полученных в результате разбиения подсетей не достигает 300 узлов. Для оценки работы алгоритма на больших сетях использовался генетический алгоритм. Сравнение проводилось на сетях с количеством узлов от 400 до 1000, расположенных на разных этажах здания. Как показали эксперименты, эффективность метода декомпозиции направленного на решение задачи проектирования новой сети не хуже, чем у генетического алгоритма. Однако, метод декомпозиции решения ищет существенно быстрее. При преобразовании сети здания, найденные решения с помощью метода декомпозиции лучше решений, полученных генетическим алгоритмом.
П. 4.3. посвящен описанию тестового примера преобразования гипотетической сети пятиэтажного здания. Алгоритм оптимизации структуры сети эффективнее проектирования структуры сети эмпирическим методом на 85%.
