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




Скачать 65.33 Kb.
НазваниеМодель оптимального размещения информационных ресурсов в неоднородной компьютерной сети
Дата публикации06.03.2013
Размер65.33 Kb.
ТипДокументы
litcey.ru > Информатика > Документы
Модель оптимального размещения информационных

ресурсов в неоднородной компьютерной сети
Зарецкий К.А., к. ф.-м. н., доцент (СибГУТИ, г. Новосибирск)

Мейкшан В.И., д. т. н., профессор (СибУПК, г. Новосибирск)
В последнее время, в связи с интенсивным развитием средств вычислительной техники, широкое распространение получили компьютерные сети с распределенной обработкой информации [1–3]. В такой сети организуется распределенная база данных (РБД) и пользователи имеют доступ ко всему множеству информационных файлов, хранящихся в узлах вычислительной сети. Каждый файл может быть представлен в нескольких копиях, которые размещаются в различных узлах компьютерной сети. При обслуживании запросов на поиск информации в файлах базы данных возможно ожидание в течение некоторого времени, что обусловлено ограниченной производительностью вычислительных ресурсов.

Известен ряд математических моделей для оптимального распределения копий информационных файлов в локальной компьютерной сети [2,3]. В различных вариантах формулировки однокритериальной оптимизационной задачи условием оптимальности служит минимальное значение одного из следующих параметров, которые характеризуют эффективность хранения и поиска информации в распределенной системе: общее время на обслуживание всех запросов, поступивших в систему за единицу времени; среднее время ожидания начала обработки запроса на поиск информации; средний объем данных, пересылаемых между узлами сети за единицу времени в процессе обработки запросов; общая стоимость сетевого трафика, порожденного функционированием вычислительной системы в единицу времени.

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

В работе [3] локальная компьютерная сеть с шинной топологией рассматривается как совокупность нескольких (по числу файлов разного вида) многоприборных систем массового обслуживания (СМО). Роль приборов в отдельной СМО играют копии соответствующего файла, причем такие системы являются пересекающимися, т.к. в каждом узле сети предполагается возможным совместное хранение разных файлов, а также одновременное и независимое выполнение нескольких запросов к разным файлам. Запрос на поиск информации в некотором файле становится в очередь, если все имеющиеся копии требуемого файла (т.е. все приборы соответствующей СМО) заняты для обработки ранее поступивших запросов.

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

Для краткого изложения более общей математической модели при переменном числе копий файлов введем следующие обозначения: ^ V — число узлов в компьютерной сети (число обслуживающих приборов в составе СМО); n — число независимых информационных файлов; j — интенсивность потока запросов к файлам j-го вида; =— суммарная интенсивность запросов на поиск информации в файлах РБД; X — матрица размещения копий информационных файлов в узлах в компьютерной сети; элементы этой матрицы (xij) принимают следующие значения: xij=1, если в i-м узле сети (i=) имеется копия файла j-го вида (j=), и xij=0 в противном случае; Ci ={j: xij =1} — множество файлов, копии которых имеются в i-м узле сети; hij — среднее время обработки в i-м узле сети запроса на поиск информации в файле j-го вида.

В произвольный момент времени текущие состояния всех узлов сети, как элементов СМО, характеризуются вектором A=(1, 2, …, V). Здесь i =0 означает, что i-й узел сети свободен, а i1 соответствует занятому состоянию i-го узла, причем значение i равно номеру файла, в котором происходит поиск информации. В состоянии A множество свободных узлов сети, в один из которых может быть направлен поступивший запрос на поиск информации в файле j-го вида, будем обозначать через Bj(A)={jCi: i =0}.

Функционирование рассматриваемой системы обработки данных описывается марковским процессом с состояниями (A, k), где k — длина очереди запросов, причем k=0, если Bj(A) для всех j=, и k0 при Bj(A)= хотя бы для одного значения j. Из состояния (A, k) возможны следующие переходы в соседние с ним состояния.

1) При поступлении запроса на поиск информации в файле j-го вида и при условии Bj(A) (имеется свободный узел сети, доступный этому запросу) с вероятностью 1/Bj(A) происходит переход в одно из состояний (A+jei, k), где iBj(A), а через ei обозначен V-мерный вектор, у которого i-я компонента равна 1, а все остальные компоненты нулевые. Если же Bj(A)=, то с вероятностью 1 система переходит в состояние (A, k+1).

2) Если i>0, то при освобождении i-го узла сети с вероятностью ik в очереди присутствует хотя бы один запрос на поиск информации в файлах из множества Ci и происходит переход в состояние (A+(j– i)ei, k–1), где jCi соответствует ближайшему в очереди запросу, который поступает на обслуживание в данный узел. С вероятностью 'ik =1– ik в очереди нет запросов к файлам, которые размещены в памяти i-го узла, и система переходит в состояние (A–iei, k), т.е. освободившийся узел не будет занят ожидающим запросом.

Стационарные вероятности состояний рассматриваемого марковского процесса обозначим через P(A, k) и в соответствии с перечисленными переходами для определения этих вероятностей можно записать систему линейных алгебраических уравнений. Найденные значения позволяют вычислить вероятностно-временные характеристики, оценивающие эффективность выполнения системой требуемых функций. В частности, для многопользовательских систем обработки информации и управления одним из основных показателей является время выдачи ответа на запрос: Tотв= Tож+Tобр, где Tож — время ожидания начала обслуживания запроса; Tобр — время обработки запроса. Для описанной математической модели среднее значение по отношению ко всем запросам определяется по формуле

Tож = kP(A, k).

Для увеличения производительности децентрализованной системы управления требуется оптимальным образом разместить копии информационных файлов в РБД с целью минимизации времени нахождения в очереди запросов на поиск информации. В математическом виде соответствующая оптимизационная задача формулируется следующим образом: Tож = f(X)  min при ограничениях

xij{0, 1} (i=; j=); xij1 (j=); Lj xij Mi (i=),

где Mi — объем памяти в i-м узле (i=); Lj — размер файла j-го вида (j=). Полученная задача может быть решена известными методами целочисленного математического программирования.
Литература

  1. Теоретические основы проектирования оптимальных структур распределенных баз данных/Кульба В.В., Ковалевский С.С., Косяченко С.А., Сиротюк В.О.; Рос. акад. наук. Ин-т пробл. упр. — М.: Синтег, 1999. — 660 с.

  2. Цегелик Г.Г. Системы распределенных баз данных. — Львов: Свит, 1990. — 168 с.

  3. Колесников Д.Г. Оптимизация распределения информационных файлов в сетях ЭВМ с параллельной обработкой/Автореферат дис. на соиск. … канд. техн. наук. — Ростов-на Дону: ДГТУ, 1999. — 23 с.

  4. Зарецкий К.А., Мейкшан В.И. Анализ качества функционирования неоднородных многомашинных систем обработки информации при ограниченной доступности вычислительных средств//Второй региональный семинар «Распределенная обработка информа­ции». — Новосибирск, 1987.

  5. Зарецкий К.А., Мейкшан В.И. Расчет неоднородных неполнодоступных систем массового обслуживания с ожиданием//Системное моделирование-13/Сборник трудов. — Новосибирск: ВЦ СО АН СССР, 1988. — С.12-24.

Похожие:

Модель оптимального размещения информационных ресурсов в неоднородной компьютерной сети iconИ мир действительно изменился с приходом глобальной компьютерной...
Человек, участвующий в компьютерной сети, должен тратить значительное количество времени и собственных усилий на защиту от разнообразных...
Модель оптимального размещения информационных ресурсов в неоднородной компьютерной сети iconПрограмма на 2013/14 уч год по курсу «Исследование операций»
Метод динамического программирования на примере распределительной задачи. Модель размещения капитала, верхняя оценка оптимума, свойство...
Модель оптимального размещения информационных ресурсов в неоднородной компьютерной сети iconО концепции индексации информационных ресурсов сети Интернет
Настоящая статья посвящена обсуждению путей повышения эффективности поисковых средств сети Интернет. В ней делается попытка обобщить...
Модель оптимального размещения информационных ресурсов в неоднородной компьютерной сети iconОтдел краеведческих информационных ресурсов
Котышева Н. Н., методист отдела краеведческих информационных ресурсов Кемеровской онб им. В. Д. Федорова
Модель оптимального размещения информационных ресурсов в неоднородной компьютерной сети iconВопрос: Реализация приоритетного национального проекта «Образование»...
Предлагает ли Ваше ведомство включить в проект нового базового федерального закона об образовании положения о создании и поддержке...
Модель оптимального размещения информационных ресурсов в неоднородной компьютерной сети iconОпросный лист для составления коммерческого предложения на приобретение
Для расчета оптимального размещения оборудования просим приложить схему размещения зданий и привязку к местности с размерами
Модель оптимального размещения информационных ресурсов в неоднородной компьютерной сети iconПрограмма прикладного социологического исследования на тему: Изучение...
Проблема исследования: Недостаток информации о факторах, влияющих на развитие всемирной компьютерной сети Internet в Москве и мнении...
Модель оптимального размещения информационных ресурсов в неоднородной компьютерной сети iconОтделение краеведческих информационных ресурсов Экологические проблемы
Кемеровской области 2008: информационное издание. Вып. 5-6 / гук кемеровская областная научная библиотека им. В. Д. Федорова; отделение...
Модель оптимального размещения информационных ресурсов в неоднородной компьютерной сети iconШвейцарское видение информационных систем предприятия (ИС)
Ис в Швейцарии. Мы подчеркнем разницу между компьютерной системой и ис. Также мы рассмотрим концепции стратегии ис и ее управления....
Модель оптимального размещения информационных ресурсов в неоднородной компьютерной сети iconПоложение о локальной вычислительной сети образовательного учреждения Общие положения
Лвс представляет собой организационно-технологический комплекс, созданный для реализации взаимодействия вычислительных и информационных...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
litcey.ru
Главная страница