автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Иерархическая система управления распределенными информационными ресурсами

Федеральное агентство по образованию Тверской государственный технический университет

\

- г,

I

[а правах рукописи

Карельская Катерина Александровна

Иерархическая система управления распределенными информационными ресурсами

Специальность 05.13.01 Системный анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Тверь 2006

Работа выполнена в Тверском государственном техническом университете

Научный руководитель: Д-т.н., профессор Григорьев В.А.

Официальные оппоненты Дл-н., профессор, Тихомиров В.А.

К.т.н., профессор Чернышов О.Л. Ведущая организация: ЗАО НИИ «Центрпрограммсистем», г.Тверь

Защита состоится « 9 » июня 2006 г. в 14.00 на заседании диссертационного совета Д 212.262.04 в Тверском государственном техническом университете по адресу: 170026, г. Тверь, наб. Аф. Никитина, 22 (Ц-212).

С диссертацией можно ознакомиться в библиотеке Тверского государственного технического университета.

Автореферат разослан «__»_2006 г.

Ученый секретарь диссертационного совета

Михно В.Н.

XOOGA

3

1. Общая характеристика работы

Актуальность, цель, общая задача исследования.

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

Система распределенных баз данных в сетях ЭВМ представляет собой одну из наиболее прогрессивных форм организации средств вычислительной техники. Проектирование и реализация систем распределенных баз данных предполагает доступ пользователя ко всей информации, хранящейся в узлах распределенной системы. Одной из задач, возникающих при создании и эксплуатации распределенных систем обработки данных (СОД), является размещение данных по узлам компьютерной сети.

В работах Аббасова A.M., Зиновьева Э.В., Клименко С.А. приводится модель задачи размещения баз данных и их копий в сети ЭВМ по критерию минимума суммарного потока между базами и их пользователями с ограничением на степень риска нарушения целостности базы данных. Модель сведена к задаче дискретного программирования с псевдобулевыми переменными. Приведенные модели позволяют определить минимальный уровень дублирования информации.

В работах Янбыха Г.Ф., Бобера В.И., Бокоева Т.И. приведена формализованная постановка и алгоритм решения задачи рационализации размещения программ и файлов в компьютерной сети, выбора производительности вычислительного комплекса, пропускной способности каналов. Задачу можно классифицировать как задачу линейного программирования, с линейными ограничениями и булевыми переменными. Элементы компьютерной сети описываются моделью систем массового обслуживания.

В работах Цегелика Г.Г. представлены результаты оптимальной организации вычислительной сети и поиска информации в ней, построены модели сетей базовой топологии, решены задачи размещения и хранения фиксированного числа копий каждого файла.

Проведенный обзор работ показал, что основной задачей является рациональное распределение данных по узлам компьютерной сети для обеспечения эффективной обработки запросов пользователей. Существующие решения не позволяют строить модели распределения файлов по узлам вычислительной сети с произвольной топологией, часто в них учитываются трудповьшолпимые ограничения, построение моделей рассмотрено для частных случаев топологии компьютерной сети.

Областью настоящего исследования является разработка критериев и моделей описания и оценки эффективности решения задач обработки распределенной информации, а также разработка программною

£ & 5

= m О о

обеспечения систем обработки данных.

Предметом (объектом) исследования является распределенная система обработки данных.

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

Для реализации цели исследований в диссертационной работе поставлены следующие задачи:

1. Разработка на основе соответствующих моделей уровней иерархии методики синтеза алгоритмов управления распределенными информационными ресурсами;

2. Разработка комплекса алгоритмов для решения задачи размещения информациошшх ресурсов;

3. Решение задачи размещения информационных ресурсов по заданной совокупности критериев: среднему объему пересылаемых данных, общей стоимости трафика, общему времени для обслуживания запросов;

4 Проведение экспериментальных исследований для оценки качества предложенных критерия и алгоритмов и сравнительной оценки их с существующими подходами;

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

Методы исследования. При решении поставленных задач использовались теории графов, сетей и языков программирования, методы теории вероятностей, аппарат математической статистики, теория математического моделирования.

Основными результатами работы, обладающими научной новизной, являются:

- решение задачи рационального распределения файлов по узлам компьютерной сети по критериям: среднему объему пересылаемых данных, общей стоимости трафика, общему времени для обслуживания запросов;

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

Основные результаты, выносимые на защиту:

- обобщенный критерий эффективности размещения файлов данных по узлам компьютерной сети;

- модифицированный алгоритм размещения файлов;

- статистические оценки результатов экспериментальных исследований по сравнительному анализу классического и модифицироватюго алгоритмов размещения данных.

Научная значимость полученных резулыатов исследования заключается в шм, что при решении задачи распределения информационных

ресурсов предложен новый подход и методика рационального размещения файлов по узлам распределенной компьютерной системы с использованием модифицированного алгоритма.

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

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

Обоснованность научных положений, выводов и рекомендаций базируется на:

- использовании основных принципов системного подхода и теории вероятностей при решении научной задачи;

- учете современных представлений о проблеме распределения информации в системах обработки данных, принципах и методах разработки систем управления распределенными БД;

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

Апробация. Основные теоретические положения и практические результаты работы докладывались на II Российско-Украинском симпозиуме, г.Пенза, 2002; III Международной научно-практической конференции, г.Пенза, 2003; Всероссийской научно-практической конференции, г.Пенза, 2004; IX Международной открытой научной конференции, г.Воронеж, 2004; XVI Международной научно-технической конференции, г.Пенза, 2005.

Внедрение. Результаты диссертационной работы внедрены в Опытно-конструкторском бюро автоматики (ОКБА). Методические и теоретические результаты работы использованы в учебных курсах кафедры ЭВМ ПТУ,

Публикации. По теме диссертации опубликовано 7 печатных работ, из них 5 научных статей, тезисы к 2 докладам на научных Всероссийских и международных конференциях.

Струк1ура и объем работы. Диссертационная работа состоит из введения, четырех разделов, заключения и содержит 107 страниц основного текста и 27 иллюстраций. Список источников содержит 83 наименования.

2. Содержание работы

Во введении обосновывается актуальность, цели, научная новизна и практическая значимость диссертационной работы. Сформулированы основные направления исследований и положения, выносимые на защиту.

В первой главе проведен анализ современных систем обработки распределенной информации, рассмо грена архитектура распределенных БД,

рассмотрены подходы, выявлены проблемы проектирования распределенных баз данных.

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

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

Одним из возможных решений указанной задачи является создание математического и программного обеспечения модели размещения файлов, в основе которого лежит минимизация среднего времени пересылаемых по линиям связи данных, общей стоимости трафика, порожденного функционированием системы, общего времени обслуживания запросов, для чего необходимо введение некоторого обобщенного критерия качества.

Во второй главе дан обзор оценок эффективности, рассмотрены идеология обработки запросов в распределенных БД, представлены критерии оценки рациональности размещения информации по узлам иерархической компьютерной сети.

Компьютерную сеть можно рассматривать как совокупность ресурсов различного типа. Это, прежде всего, вычислительные мощности, каналы связи, память и т.д.

Схема обработки запросов состоит в следующем: запрос, инициированный на узле сети, поступает на входную очередь соответствующего узла. Про1рамма обработки обрабатывает запросы в порядке их поступления. Если запрашиваемые данные содержатся в локальной базе данных узла, на который поступил запрос, то запрос обрабатывается и выводится результат. Если запрашиваемые данные расположены на другом узле сети, го запрос пересылается на нужный узел сети, где он обрабатывается и результат пересылается в первоначальный узел. Порядок обслуживания запросов в узлах не влияет на объем пересылаемых данных по каналам связи и поэтому не рассматривается. Для определения типа запроса (локально или удаленно обслуживаемый) используются специальные справочники, содержащиеся в локальной базе узла, инициирующего запрос.

Из схемы обработки запросов в системе следует, что в процессе обслуживания в течение каждой единицы времени по каналам связи пересылается некоторый объем данных. Общее значение этого объема зависит от распределения файлов по локальным базам данных. Соотве гс гвенно, чем меньше средний объем пересылаемых данных но каналам сети за единицу времени, тем выше скорооь обработки запросов.

В настоящее время для наиболее рациональной организации рабогы распределенных систем обработки данных необходимо оценивать информационные, временные и денежные затраты на ее поддержание в

работоспособном состоянии. Таким образом, для систем распределенной обработки данных возможно определить несколько различных критериев, каждый из которых служит для определения степени рациональности размещения информации по узлам распределенной системы:

• средний объем пересылаемых по линиям связи данных при выполнении запроса:

а)

Л 1-1 у=1

• общая стоимость трафика, порожденного функционированием распределенной системы в течение единицы времени:

С = тЯу(ав+рХ(1-хХ, (2)

1=1 }=\5-\

• общее время, необходимое для обслуживания запросов, поступающих в систему за единицу времени:

Т + у

1-1 7=11=1

где в (1,2,3) п- число узлов сети распределенной БД (РБД); ш - число независимых файлов РБД; 5 - число типов запросов; К, -}-й узел сети; Ь\ - 1-й файл РБД;

А,, - интенсивность запросов к файлу Р„ инициированных в узле К,; Д - средняя интенсивность входного потока сообщений в коммутаторе данных;

а„ -- объем запроса к файлу У7,, инициированного в узле К,; Д - объем запрашиваемых данных при выполнении запроса к файлу Р„ поступившего на терминал узла К^

Хц - матрица распределения файлов РБД по узлам сети, определяемая

как:

1*1, если файл ^ находится в узле К л [О, в противном случае, при г -1 ,т и ] = \ ,п

- время обработки в узле К, запроса к файлу У7,, поступившего из

узла К,;

Т!,Ч! - время, необходимое для пересылки из узла К, в узел К, запроса к файлу 0, э =1,2,...«);

- время, необходимое для пересылки из узла К, в узел К, ответа на запрос к файлу Р, 0, .у =1,2,...и);

г„, - стоимость передачи единицы информации из узла К, в узел К„ где (Г»=0, 5=1,2,...«).

Однако существуют офаничения, которые необходимо учитывать:

- каждый файл распределенной системы может находиться только в одном из узлов сети:

где 1 = 1,т

у=1

- объем памяти для размещения файлов в узле ограничен значением Ь,-

т ,

£ V- <Ь}, где ] = \п

(5)

I, - объем х-го файла распределенной БД; - объем памяти узла К,, предназначенный для размещения файлов; - общее время обслуживания запросов в узле К5 не должно превышать время, выделенное для обработки всех запросов в узле К„ поступивших в течение единицы времени:

т п -

где 5 = 1>" (6)

М 7=1

- время обработки в узле К$ запроса к файлу /г„ поступившего из

узла К,,

^ -- время, выделенное для обработки всех запросов в узле К„ поступивших в течение единицы времени;

При рассмотрении реальной распределенной системы обработки данных более объективен комплексный подход. Для этого можно использовать обобщенный критерий эффективности, представляющий собой произведение частных критериев, в которое каждый из них входит с некоторым весовым коэффициентом:

УСТ УСТ'

где V, С, Т - значения соответствующих критериев для конкретных размещений файлов по узлам распределенной системы;

V,,, Со, Та — значения соответствующих критериев для оптимальных (квазиоптимальных) размещений файлов по узлам распределенной системы (при тех же исходных данных).

Таким образом, необходимо определить значения переменных х„, которые удовлетворяют условиям (4,5,6) и обращают в минимум целевую функцию:

Ш = \-{IV} (8)

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

л

классического и модифицированного алгоритмов при помощи аппарата математической статистики.

Для решения поставленных задач используется алгоритм, который состоит из двух последовательных этапов:

1. На первом этапе формируется матрица начального размещения файлов по узлам вычислительной сети, оптимальная с точки зрения заданного критерия, причем на данном этапе не учитываются ограничительные условия. Т.е. для каждого файла распределенной БД определяется тот узел сети, в котором его местонахождение оптимально с точки зрения заданного критерия. При такой формулировке, полученное размещение файлов будет оптимальным, поскольку не учитываются условия ограничения;

2. На втором этапе проводится поверка соблюдения заданных ограничений и производится процесс переразмещения файлов, если для начального размещения существует хотя бы один узел сети, где заданные ограничения не выполняются. Т.е. используется многоитерационный подход, на каждом шаге которого осуществляется перераспределение файла из переполненного узла таким образом, чтобы сю перемещение привело к минимальному увеличению значения кршерия Выполнение перераспределения производится до тех пор, пока не будет найдено размещение, удовлетворяющее условиям ограничения, или не будет иринято решение о невозможности нахождения ткого размещения. Матрица размещения файлов распределенной БД по узлам

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

II, если файл Р^ находится в узле К у; О, в противном случае при I = 1,т и ] — 1 ,п

Первая ступень модификации.

1. Для всех 7 = 1 ,п проверяется выполнение условий ограничения. Если эти условия для всех ] выполняются, то на этом работа алгоритма заканчивается. Распределение X является оптимальным. Если для некоторого индекса ] = г условия ограничения не выполняются, то формируется не только вектор признаков Р = {рх, рг, рп\ где

Р, =(/ = 1,и) (Р, = 1 - признак закрытости]-го узла для дальнейшего переразмещения в него файлов), но и вектор признаков м Щ, где тя, =0 (/= 1,от) (т, = 1 - признак

лп х12 ... х1л

Х =

х21 х12 ... х2п

Хт\ Хт2 ■■■ Хтп_

неперемещаемости 1-го файла). В процессе работы алгоритма, если некоторый узел К, переполнен, то происходит перераспределение файлов из этого узла. Файлы Г„ оставшиеся в узле К, после перераспределения, считаются неперемещаемыми и соответствующим им элементам т, матрицы М, присваивается значение 1, В отличие от классического метода, узел К, считается закрытым для перераспределения (соответствующему элементу р, вектора Р присваивается значение 1) только в том случае, когда все файлы данного узла ненерсмещаемые и оставшегося объема памяти Ь/ не хватает для размещения ни одного из оставшихся перемещаемых файлов.

2. Перераспределение файлов из переполненного узла Кг. Для каждого г, для которого хи = 1 и т1 Ф1, находим где минимум берется по

тем индексам г * г, для которых р} = 0. Пусть 1ШП

Гогда находим ГП1П V ) , где минимум берется по индексам /, для

]

которых Х[г

= 1 и От,* 1. Пусть -(^г).

Тогда в

!

матрице X полагаем х1г = 0, х,и -1. Это означает, что файл Г, из узла Кг перераспределен в узел Кф Такому перераспределению соответствует минимальное увеличение значения целевой функции.

3. Для ]~г проверяется выполнение условий ограничения. Если эти условия не выполняются, то возврат к пункту 2. Если условия выполняются, то: 1) элементам т, вектора М, соответствующим файлам, оставшимся в узле К„ присваивается значение 1; 2) для узла К, проверяется условие Л/ < ¿„ г де Ь, берется по тем индексам /', для которых т, ^ 1 (т.е. оставшейся в узле К, памяти не хватает для размещения ни одного из неперемещаемых файлов) и если это условие выполняется, элементу р, вектора Р присваивается значение 1 и переход к пункту 4.

4. Для всех индексов /, для которых р, -0, проверяем выполнение условий ограничения. Если для всех таких индексов у условия выполняются, то на этом работа алгоритма заканчивается. Распределение X принимается за ошимальное. Если для некоторого индекса ] - г условия ограничения не выполняются, то переход к пункту 2.

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

Вторая ступень модификации

Для повышения качества разрабатываемого алгоритма в случае, когда процесс работы алгоритма завершается аварийно (т.е. первая ступень модификации алгоритма не размещает файлы: для какого-либо х-го файла не

хватило места в процессе переразмещения), применяется вторая сгупень модификации алгоритма:

1. Выявляется "проблемный" i-й файл, для которого не хватило места ни в одном из узлов в процессе переразмещения;

2. Значения векторов признаков МяРустанавливаются в 0;

3. Повторно выполняется процедура определения матрицы начального размещения;

4. Проводится анализ возможности размещения i-го файла: производится последовательный перебор узлов в порядке нарастания/убывания значения целевой функции (по отношению к /му файлу), проверяя выполнения условий ограничения для этого узла. Первый же узел, где выполняются условия ограничения, признается годным для размещения i-го файла, после чего файл становится неперемещаемым (элементу т, вектора М присваивается значение 1);

5. Повторно выполняется процедура переразмещения.

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

Третья ступень модификации

Анализ работы второй ступени модификации алгоритма позволил сделать вывод о том, что "проблемный" i-й файл, для которого не хватило места ни в одном из узлов в процессе переразмещения, является, как правило, одним из самых больших файлов в общем количестве данных (/,, -> max). Это наблюдение и легло в основу идеи третьей ступени модификации разрабатываемого алгоритма (аналогом данной ступени модификации может считаться алгоритм последовательного размещения элементов в радиоэлектронике). Из предварительно размещенных файлов выбирается тот, который имеет максимальный размер. Этот файл располагается поочередно в каждом узле, и подсчитывается значение выбранного критерия, в результате чего определяется оптимальное размещение этого файла (с учетом условий ограничений). Затем выбирается следующий по размеру файл, и все повторяется в том же порядке. Выполнение алгоритма заканчивается, когда все файлы размещены по узлам сети или выявляется принципиальная невозможность такого размещения.

Результатом серии экспериментов является количество удачно завершившихся попыток размещения для каждого из значений коэффициента

дефицита ресурса по каждому алгоритму. На основании полученных

числовых значений построены зависимости, представленные на рис. 1. Анализ графика показывает, что: 1) вероятность размещения данных модифицированным алгоритмом значительно раньше становится отличной от нуля, следовательно, модифицированный алгоритм обеспечивает размещение

данных при более жестких начальных условиях, чем классический алгоритм; 2) при увеличении значения (при уменьшении дефицита начальных

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

1 00 1,06 1,10 1 15 1 20 1,25 1 30 1,35 1 40 1,45 1,50 1,55 1,60 1,65 1,70 1,75 1,80 1,85 1,90 1.95 показатель дефицита ресурса

Рис.1 Оценка вероятности размещения файлов при дефиците ресурсов

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

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

Для наглядного графического отражения соотношения величин математических ожиданий целевой функции рассматриваемых алгоритмов необходимо применить метод "штрафов", принцип действия которого заключается в следующем: значение исследуемого параметра для каждого алюритма размещения "штрафуется" (увеличивается) на определенную,

рассчитываемую каждый раз величину. В данном случае для каждой серии экспериментов М{б}=Лф}+ 7/ , где г] - величина "штрафа" за неразмещен-

показатель дефицита ресурса

Рис.2 Оценка математического ожидания целевой функции при дефиците ресурсов

ные данные, которая определяется следующим образом: 1] -100(1- р), где р -вероятность размещения данных для конкретной серии экспериментов. Таким образом, чем больше неудачных попыток размещения допускает алгоритм, тем большим "штрафом" он "наказывается". Максимальный штраф в данном случае получается при р=-0 (ни она одном из наборов входных параметров серии экспериментов попытка размещения не оказалась успешной) и его величина равна т] = 100.

После применения метода "штрафов" график можно представить в виде графика на рис. 3. Теперь совершенно очевидно, что модифицированный метод не только начинает раньше работать, но и дает лучшие результаты размещения. Чем более стабильным становится размещение классического алгоршма, 1ем ближе сходятся графики штрафованных математических ожиданий модифицированного и классического алгоритмов. И еще очевиднее становится то, что при продолжении графиков в область увеличения значении К,^ они совпадут друг с другом, поскольку при отсутствии дефицита ресурсов классический алгоритм размещае1 данные так же успешно, как и модифицированный (величина штрафа снижается и в какой-то момент становится нулевой) а при одинаковой вероятности размещения оба алгоритма дают одинаковые результаты.

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

зрения построим зависимость вероятности размещения данных от дисперсии разброса размеров файлов.

0,00 --,-1-,---1-,-,-

1,00 1,10 1,20 1,30 1,40 1,50 1,60 1 70 1,80 1,90 2 00 показатель дефицита ресурса

Рис.3 Оценка математического ожидания целевой функции при использовании метода штрафов

Для построения графика на рис.4 для каждого значения дисперсии разброса размеров файлов проводится серия из 100 вычислительных экспериментов, результатом которой является количество удачно завершившихся попыток размещения для каждого из алгоритмов. Все эксперименты проводятся при значении коэффициента дефицита ресурса

Анализ зависимостей показывает' при малых значениях дисперсии разброса размеров файлов оба алгоритма работают практически одинаково (действительно, когда файлы имеют почти одинаковые размеры, то перемещение их из узла в узел приносит мало пользы и практически все зависит от распределения свободного места между узлами); при увеличении значения дисперсии разброса размеров файлов появляются явные различия в работе алгоритмов: разработанный модифицированный алгоритм начинает давать лучшие результаты, а классический алгоритм приобретает тенденцию к небольшому, но все-таки ухудшению результатов работы. И, не смотря на то, что у классического алгоритма наблюдается большая стабильность результатов, разработанный модифицированный алгоритм показывает лучшее качество работы.

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

Кдеф= 1 3

рес

0% 5% 10% 15% 20% 25% 30% 35% 40% 45% 50% 55% 60% 65% 70% 75% 80% 85% 90% 95%

Рис.4 Оценка вероятности размещения файлов при разбросе значений размеров файлов

В четвертой главе отражено применение разработанного алгоритма размещения файлов по узлам распределенной системы в системах обработки гидроакустических данных (СОГД).

СОГД состоит (рис.5) из базового информационно-вычислительного комплекса (БИВК), удаленных от него ЛВС и выносных частей с различными [ комплексами гидроакустических антенн (ВЧ). Выносная часть располагается

в водном пространстве, ЛВС - на береговой линии. Связь между ВЧ и ЛВС осуществляется через оптоволоконный кабель и устройства сопряжения с ЭВМ. В качестве береговой ЛВС и ВЧ может использоваться система МЭСГЛС, «Рациональность - СГ» или другая аналогичная система.

Базовый информационно-вычислительный комплекс представляет собой ЛВС, территориально удаленную на достаточно большое расстояние от береговых ЛВС, расположенную в крупном городе. Па береговых ЛВС проводится первичная обработка гидроакустических данных, поступающих от антенн. ЬИВК производит вторичную и дальнейшую обработку этих данных. Связь между береговыми ЛВС и БИВК осуществляется по высокоскоростному спутниковому каналу.

В рассмотренном примере в системе обработки гидроакустических данных требовалось распределить 50 файлов по 38 узлам. Вначале было найдено некоторое исходное распределение файлов по узлам информационной системы, затем рациональное распределение файлов по разработанному модифицированному алгоритму, используя в качестве критерия рациональности общее временя обработки сообщений. При исходном размещении общее время обработки сообщений составило 167 е., а при размещении по модифицированному алгоритму - 94 с.

Рис.5 Обобщенная схема системы обработки гидроакустических данных Матрица размещения файлов выглядит следующим образом (рис.6):

-Т1 ш ш ш ш -я -И тк ■ Ш к ■ ш ш ш ш ¡и 11 ШШЫй! ■ Й м ш т а ^ЫШУ м ы ■ ы я ш ■ ш М ш И ш ш т ш ■ ш Й

■ ■ ■

и

II — Г"

■ с с и

^Шц —

Г"

Г с Г"

ь и. с с и г

г и г [I с

С с С Ё

г г- — Р— [I Ь"

Г

^ I- 1 Г" Г" с п

Е

□ г™

с □

г □

■

И

Ш

И

»

■ _1

1 □

Ц

й

— — п

Л — 1 Р I

о 3 ч п

п — I п ™ ™ ч _

г г: Г"

и ГИ

П — гг —1 —

_1 и □ □ I] п "1 J □

_ Р -1 г] И п

о

— И ц

г —

— —

— —

_ _ —

Рис 6 Матрица размещения файлов по узлам информационной системы

Проведенная оценка практической эффективности разработанного алгоритма на конкрешом примере ЛВС показала, что размещение, найденное модифицированным алгоритмом по критерию общего времени обработки сообщений, на 43.7% эффективнее исходного.

3. Основные результаты работы

1. Проанализирован ряд существующих алгоритмов решения задачи рационального размещения файлов по узлам распределенной системы обработки данных. Рассмотрена вычислительная сеть с произвольной топологаей; в качестве стратегии распределения данных выбрана смешанная стратегия. Рассмотрен многокритериальный подход к решению задачи.

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

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

4. Разработана программа, реализующая алгоритм.

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

6. Разработанный алгоритм реализован в системах обработки гидроакустических данных.

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

Публикации по теме диссертации

1. Попов A.B., Карельская К.А., Зайцева Н.Ю. Основные аспекты оценки эффективности обработки распределенной информации. Сборник материалов II Российско-Украинского симпозиума. - Пенза: Приволжский Дом знаний, 2002, с.333-335.

2. Карельская К.А., Попов A.B. Оценка качества размещения файлов по узлам распределенной вычислительной сети. Сборник материалов Ш Международной научно-практической конференции. - Пенза: Приволжский Дом знаний, 2003, с.101-103.

3 Карельская К.А., Попов A.B., Цветкова Ю.В. Выбор алгоритма размещения файлов по узлам сети. Сборник материалов Всероссийской научно-

практической конференции. - Пенза: Приволжский Дом знаний, 2004, с.205-208.

4. Карельская К.А., Попов A.B., Цветкова Ю.В. Надежность распределенных баз данных. Сборник трудов по итогам IX Международной открытой научной конференции. Вып.9. - Воронеж: Издательство «Научная книга», 2004, с.357-358.

5. Карельская К.А. Статистическая обработка результатов экспериментов при проектировании распределенных систем. Сборник статей XIV Международной научно-технической конференции. — Пенза: Приволжский Дом знаний, 2004, с.386-387.

6. Карельская К.А. Исследование модифицированного алгоритма размещения файлов по узлам сети. Сборник статей XVI Международной научно-технической конференции. - Пенза: Приволжский Дом знаний, 2005, с.419-421.

7 Карельская К.А. Однокритериальная оценка модифицированного алгоритма размещения информации по узлам сети. Сб. науч. статей. Вестник ТГТУ № 8. - Тверь, 2006.

Подписано в печать 2.05.06

Физ. печ. л. 1,25 Тираж 100 экз. Заказ ¥ 88

Типография ТГТУ

ZOQGpi

a&74

ВВЕДЕНИЕ.

ГЛАВА 1 АНАЛИЗ ПРОБЛЕМНОЙ ОБЛАСТИ И ПОСТАНОВКА ЗАДАЧИ ДИССЕРТАЦИИ.

1.1 Актуальность проблемы.

1.2 Архитектура распределенных СУБД.

1.3 Анализ принципов построения распределенных баз данных.

1.4 Проблемы проектирования распределенных баз данных.

1.5 Основы проектирования распределенной базы данных.

1.6 Обзор состояния области исследований.

1.7 постановка задачи.

ГЛАВА 2 РАЗРАБОТКА И ВЫБОР АППАРАТА ДЛЯ

ИССЛЕДОВАТЕЛЬСКОЙ ЧАСТИ.

2.1 Обзор оценок эффективности.

2.2 Идеология обработки запросов в РБД.

2.3 Общие понятия и термины, необходимые для описания распределенной системы обработки информации.

2.4 Критерии оценки рациональности размещения файлов распределенной системы по узлам сети

2.5 Выводы по главе.

ГЛАВА 3 РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМА

РАЗМЕЩЕНИЯ.

3.1 Разработка алгоритма размещения файлов распределенной системы по узлам сети.

3.2 Исследование разработанного алгоритма.

3.3. Выводы по главе.

ГЛАВА 4 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ.

4.1 Применение разработанного алгоритма в системах обработки гидроакустических данных.

4.2 Практическая эффективность разработанного алгоритма.

4.3 Выводы по главе.

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

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

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

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

Основными задачами в данной области являются:

- Рациональное распределение файлов РБД по узлам вычислительной сети;

- Рациональный выбор внешних запоминающих устройств для хранения файлов в каждом узле;

- Рациональная организация хранения и поиска информации на внешних запоминающих устройствах в каждом узле.

Основой большинства работ, посвященных первой задаче, является теория очередей. Поэтому для решения задач размещения получаются или достаточно сложные модели, точных методов реализации которых не существует, или учитываются нереальные ограничения. Для сложных топологических структур сети достаточно трудно построить реальные модели на основе теории очередей. Кроме того, существующие алгоритмы размещения данных дают недостаточно высокие результаты работы в жестких условиях - при дефиците каких-либо ресурсов. В связи с этим рассмотрен другой подход к решению задачи, в основе которого лежит минимизация среднего времени пересылаемых по линиям связи данных, общей стоимости трафика, порожденного функционированием системы, общего времени обслуживания запросов. При этом предложена и методика реализации построенных моделей, и алгоритм, адаптированный под ужесточенные исходные данные. Эти результаты рассмотрены в главах 2, 3 настоящей работы.

43 Выводы по главе

В данной главе:

Обоснована практическая применимость разработанного алгоритма рационального размещения файлов по узлам вычислительной сети в системах обработки гидроакустических данных (СОГД) при охране морских рубежей.

Описаны этапы функционирования СОГД, определена область применения алгоритма рационального размещения файлов, а также обоснована необходимость применения разработанного алгоритма при решении конкретных задач.

Проведена оценка практической эффективности разработанного алгоритма. Для этого рассмотрен конкретный пример ЛВС; описана методика формирования матриц исходных данных. Сравнивались значения критерия качества при исходном размещении (которое было произведено из соображений целесообразности равномерной загруженности всех узлов) и при размещении, найденном разработанным алгоритмом. Оказалось, что размещение, найденное разработанным алгоритмом по критерию общего времени обработки сообщений, на 43,7% эффективнее исходного.

Заключение

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

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

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

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

Разработанный алгоритм реализован в системах обработки гидроакустических данных.

1. Тиори Т., Фрай Дж. Проектирование структур баз данных М.: Мир, 1985 г.

2. Гаврилов А.В. Автоматизированные банки данных и знаний. -Новосибирск, 1988 г.

3. Дейт К. Введение в системы баз данных. М: Наука, 1980 г.

4. Калиниченко JI.A., Косторомина О.Е., Хитрова О.Н. Концепция построения систем управления распределенными базами данных // Прикладная информатика-М.: Финансы и статистика, 1984 г. Вып. 1(6) с. 6-48.

5. Мартин Дж. Вычислительные сети и распределенная обработка данных: программное обеспечение, методы и архитектура: Пер. с англ. В 2 вып. М.: Финансы и статистика. Вып. 1 - 1985 г. , 256 с. Вып. 2 - 1986 г., 296 с.

6. Мартин Дж. Организация баз данных в вычислительных системах: Пер. с англ. -М.: Финансы и статистика, 1982 г., 662 с.

7. Мартин Дж. Системный анализ передачи данных: Пер. с англ. М.: Мир, 1975 г.

8. Моделирование и управление в распределенных вычислительных сетях: Сборник научных трудов Киев: Наук, думка, 1989 г.

9. Цегелик Г.Г. Системы распределенных баз данных. Киев: Наук, думка, 1990 г.

10. Цегелик Г.Г. Организация и поиск информации в базах данных. -Львов: Вища шк. Изд-во Львов, ун-та, 1987 г.

11. Аббасов A.M. Оптимизация размещения информационной базы с копиями в сети ЭВМ // Автоматика и вычислительная техника, 1988 г. №4, с. 71-75.

12. Зиновьев Э.В., Клименко С.А. Декомпозиционный метод оптимального размещения информационных ресурсов в сетях ЭВМ с зональнойструктурой//Автоматика и вычислительная техника, 1987 г., № 6, с.54-60.

13. Янбых Г.Ф. Оптимизация размещения вычислительных комплексов, программ и файлов в сети ЭВМ // Автоматика и вычислительная техника, 1984 г., № 5, с. 14-20.

14. Янбых Г.Ф., Бобер В.И., Бокоев Т.И. Оптимизация размещения файлов и каналов передачи файлов в сети ЭВМ // Автоматика и вычислительная техника, 1984 г., № 4, с. 25-29.

15. Сергиенко И.В., Каспицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наук, думка, 1981 г.

16. Корбут А.А., Финкельштейн Ю.Ю. Приближенные методы дискретного программирования. Изв. АН СССР Техн. Кибернетика, 1983 г., №1, с. 165-176.

17. Покровский А.Н. Обзор алгоритмов компоновки, размещения модулей и трассировки печатного монтажа при конструировании радиоэлектронной аппаратуры. Вопросы радиоэлектроники. Сер. общетехн., 1967 г., вып. 14, с. 38-42.

18. Абрайтис Л.Б., Шейнаускас Р.И., Жилевичюс В.А. Автоматизация проектирования ЭВМ. Советское радио, 1978 г.

19. Баранов С.И., Журавина Л.Н., Скляров В.А. Автоматизация проектирования ЦВМ. Минск: Высшая школа, 1981 г.

20. Батанов Л.А. Автоматизация проектирования цифровых вычислительных систем. М.:, 1978 г.

21. Антре Ш. Структурный подход к организации баз данных. М.: Финансы и статистика, 1983.

22. Бойченко Е.В., Кальфа В.А., Овчинников В.В. Локальные вычислительные сети. М.: Радио и связь, 1985.

23. Большаков В.Д. Теория ошибок наблюдений: Учебник для вузов. — 2-е изд., перераб. и доп. -М.: Недра, 1983.

24. Вентцель Е.С. Исследование операций: задачи, принципы, методология. 2-е изд., стер. - М.: Наука. Гл. ред. физ.-мат. лит., 1988 -208 с.

25. Вентцель Е.С. Исследование операций. М.: Советское радио, 1972.

26. Давыдов Э.Г. Исследование операций. М.:Высш. школа, 1990 - 383 с.

27. Еремин И.И. Противоречивые модели оптимального планирования. -М.: Наука. Гл. ред. физ.-мат. лит., 1988 г. 160 с.

28. Золотников Н.И. Эволюция систем автоматизированной обработки данных. Проблемы техники и АСУ, Л., 1984.

29. Инмон У., Фридман Л. Методология экспертной оценки проектных решений для систем с базами данных. Пер. с англ. М.: Финансы и статистика, 1986 г. - 280 с.

30. Исследование операций: В 2-х томах. Пер. с англ./ Под ред. Дж. Моудера, С. Элмаграби М.: Мир, 1981.

31. Йенсен П., Барнес Д. Потоковое программирование. Пер. с англ. М.: Радио и связь, 1984.

32. Кофман А., Анри-Лабодер А. Методы и модели исследования операций. Целочисленное программирование. Пер. с фр. — М.:Мир,1977.

33. Лорин Г.Р. Распределенные вычислительные системы. Пер. с англ. -М.: Радио и связь, 1984 296 с.

34. Овчаров Л.А., Селетков С.Н. Автоматизированные банки данных. М.: Финансы и статистика, 1982.

35. Плескунин В.И., Воронина Е.Д. Теоретические основы организации и анализа выборочных данных в эксперименте. Л.: Изд-во Ленингр. университета, 1979.

36. Полищук Ю.М., Хон В.Б. Теория автоматизированных банков информации. -М.: Высш. школа, 1989.

37. Полланд Дж. Справочник по вычислительным методам статистики./ Пер. с англ. B.C. Занадворова. Под ред. и с предисл. Е.М. Четыркина. -М.: Финансы и статистика, 1982.

38. Сергиенко И.В., Каспицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наук, думка, 1981.

39. Тониев К.С., Цвиркун А.Д. Оптимизация распределения вычислительных работ и баз данных в сети ЭВМ // Автоматика и телемеханика, 1983, № 12, с. 122-133.

40. Хаббард Дж. Автоматизированное проектирование баз данных. М.: Мир, 1985.

41. Chu W.W. Optimal file allocation in a computer network. Computer Communication networks. Englwood Cliffs, N.F., Pentice-Hall. Inc., 1973, p.82-94.

42. Янбых Г.Ф., Столяров Б.А. Оптимизация информационно-вычислительных сетей. М: Радио и связь, 1987 - 230 с.

43. Еремин И.И. Введение в теорию линейного и выпуклого программирования: Учебное пособие для вузов. М.: Наука, 1976.

44. Еремин И.И., Мазуров В.Д. Вопросы оптимизации и распознавания образов: Методическое пособие Свердловск: Средне-Уральское кн. изд., 1979-61 с.

45. Берзин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем. Под ред. Е.В.Золотова. М.: Сов. радио, 1974.

46. Чохонелидзе А.Н. Проектирование специального программного обеспечения АСУ. Тверь: ТвеПИ, 1993.

47. Вагнер Г. Основы исследования операций. М.: Мир, 1972.

48. Зуховицкий С.И., Авдеев Л.И. Линейное и выпуклое программирование. -М.: Наука, 1964.

49. Нагао Макото и др. Структуры и базы данных./ М.Нагао, Т.Катаяма, С.Уэмура; пер. с яп. В.Ю.Акифьева-М.: Мир, 1986.

50. Мартынов Ю.М. и др. Математическое обеспечение сетей передачи данных. -М.: Радио и связь, 1986.

51. Кокорева Л.В., Малашинин И.И. Проектирование банков данных. М.: Наука, 1984.

52. Никитин А.И. и др. Глобальное непротиворечивое состояние распределенных баз данных./ А.И.Никитин, А.А.Алиев, С.В.Гостилова; АН УССР. Ин-т кибернетики им. В.М.Глушкова. Киев, 1988.

53. Когаловский М.Р. Технология баз данных на персональных ЭВМ. М.: Финансы и статистика, 1992.

54. Системы управления базами данных. Вопросы разработки. Опыт применения. / НПО Центрпрограммсистем; сост. Майорова Р.И. — Калинин, 1986.

55. Конноли Т. Базы данных: проектирование, реализация и сопровождение DataBase Systems: Пер. с англ. - М. и др.: Вильяме, 2000.

56. Мейер Давид. Теория реляционных баз данных./ Пер. с англ. М.К.Валиева и др. -М.: Мир, 1987.

57. Motzkin D. An optimal data allocation model for distributed databases // Math, and Comput. Modell. 1988. Vol. 11. P. 920-925.

58. Wah W. File placement on distributed computer systems // Computer. 1984. №1.

59. Yoshida M., Mizumathi K., Wakino A. Time and cost evaluation schemes of multiple copies of data in distributed database Systems // IEEE Trans. Software Eng. 1985. №9.

60. Yu C.T., Siu M. K., Lam K., Chen C.H. Adaptive file allocation in star computer network // IEEE Trans. Software Eng. 1985. №9.

61. Dutta A. Modelling of multiple copy updates for file allocation in distributed database // Int. J. Comput. and Inf. Sci, 1985. №1.

62. Петров Ю.К. JAM инструментальное средство разработки приложений в информационных системах архитектуры "клиент/сервер", построенных на базе РСУБД. "СУБД", 1995, №3.

63. Флорес И. Структуры и управление данными. М.: Финансы и статистика, 1982, - 318 с.

64. Египко В.М., Акимов А.П., Горин Ф.Н. Процедуры и методы проектирования автоматизированных систем в научных исследованиях. -М.: Наука, 1978.- 175с.

65. Ларионов A.M., Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы и сети. Л.: ЛИАП, 1987. - 285с

66. Советов Б.Я., Яковлев С.А. Моделирование систем. М.: Высшая школа, 1989. -80с.

67. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1978. -400с.

68. Шеннон Р. Имитационное моделирование систем искусство и наука: Пер. с англ. - М.: Мир, 1978.-418 с.

69. Мерхофф Э. Средства моделирования структур баз данных. // Computer World Moskow. 1995. № 12. с. 42-46, 62.

70. Ульман Дж. Основы систем баз данных. — М.: Финансы и статистика, 1983.

71. Цикритзис Д., Лоховски Ф. Модели данных. — М.: Финансы и статистика, 1985.

72. Юдицкий С.А., Кутанов А.Т. Технология проектирования архитектуры информационно-управляющих систем. М.: ИПУ, 1993.

73. Агафонов В.Н. Типы и абстракция данных в языках программирования //Данные в языках программирования.-М.: Мир, 1982. с 237-265.

74. Буч Г. Объектно-ориентированное программирование с примерами применения. М.: Конкорд, 1992. - 312с.

75. Mullin М. Object oriented Program Design With Examples in С++. Addison Wesley, 1990. 303p.

76. Страуструп Б. Язык программирования Си++. М.: Радио и связь, 1991.-352с.

77. От Си к Си++. /Е.И.Козелл, Л.М.Романовская, Г.В.Русс и др. М.: Финансы и статистика, 1993. -272с.

78. Дьюхарст С., Старк К. Программирование на Си++. Киев: ДиоСофт, 1993.-272с.

79. Рогаткин Д. MFC 2.0: шаг к совершенству // SoftReview -Компьютерное обозрение №1, 1994, с. 43-44.

80. Michael J. Voung. Mastering Microsoft VISUAL С++ Programming. -SYBEX: 1993, 980p.

81. Каменева M.C. Системный подход к проектированию сложных систем. // Журнал д-ра Добба. 1993. № 1. с. 9-14.

82. Гилула М.М. Множественная модель данных в информационных системах. — М.: Наука, 1992.

83. Финкелынтейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. - 295 с.