автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование переноса и поиска данных в децентрализованной распределенной системе, использующей N-k-схему хранения информации

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

о □**

Петров Виктор Анатольевич

МОДЕЛИРОВАНИЕ ПЕРЕНОСА И ПОИСКА ДАННЫХ В ДЕЦЕНТРАЛИЗОВАННОЙ РАСПРЕДЕЛЕННОЙ СИСТЕМЕ, ИСПОЛЬЗУЮЩЕЙ И-&-СХЕМУ ХРАНЕНИЯ ИНФОРМАЦИИ.

Специальность 05.13.18- математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

и - - ^ "1

Москва-2008 1 ' ;

003452844

Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета)

Научный руководитель:

кандидат физико-математических наук ТОРМАСОВ Александр Геннадьевич.

Официальные оппоненты:

доктор физико-математических наук, ст.н.с. РЯЗАНОВ Владимир Васильевич.

кандидат физико-математических наук СИМАКОВ Сергей Сергеевич.

Ведущая организация:

Институт автоматизации проектирования РАН.

заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

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

Защита состоится ¿0

Q СС

2008 года в J

часов на

Автореферат разослан

2008 года.

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

Федько О.С.

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

Актуальность темы.

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

Изучение распределенных систем осложняется высокими затратами на приобретение, установку и изменение параметров их комплектующих. Моделирование сетевых процессов снимает эти сложности. С увеличением количества узлов в распределенной системе моделирование становится практически единственным способом исследования.

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

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

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

Цель работы, задами исследования.

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

Задачи исследования:

• Моделирование поиска файла в децентрализованной распределенной системе, использующей Л'-Л-схему хранения файлов.

• Моделирование миграции виртуальных серверов в децентрализованной распределенной системе, использующей ЛЧ-схему хранения файлов.

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

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

Научная новизна.

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

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

Практическая ценность.

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

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

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

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

Положения, выносимые на защиту:

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

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

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

Публикации и апробация результатов.

По теме диссертации опубликовано 15 работ, в том числе две [12, 15] - в изданиях, рекомендованных ВАК РФ.

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

• XXXIII и XXXIV международные молодежные научные конференции «Гагаринские чтения», Москва, 2007 и 2008 гг.,

• XI Всероссийская научно-практическая конференция «Научное творчество молодежи», Кемерово, 2007 г.,

• ХЬУ1, ХЬУП, ХЬУШ и Х1ЛХ научные конференции МФТИ, - Москва: МФТИ, 2003-2006 гг.,

• V Научно-практическая конференция «Метрологическое обеспечение измерительных систем», Пенза, 2008 г.,

• V Российская научно-техническая конференция «Математическое моделирование и компьютерный инженерный анализ», Екатеринбург, 2008 г.,

• Научные семинары кафедры информатики МФТИ, 2004-2008 гг..

Структура и объем работы

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

Краткое содержание работы.

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

Первая глава

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

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

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

Ни одно из рассмотренных решений напрямую не применимо к децентрализованным распределенным системам с А^Л-схемой хранения данных. Хотя некоторые их элементы были включены (или оказались общими) в предлагаемые решения поставленных в работе задач.

Вторая глава.

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

Имитационная модель.

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

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

• - время пересылки сетевого пакета узлом п,

• - время обработки запроса (на сборку файла) на узле п,

пропускная способность соединения между узлами пит.

• Q„- количество требуемых порций на машине п,

1, если посылка пакета от идо т была успешной,

• г =■>

пт 0, если при посылке пакета от идо т

произошла ошибка(пакет не дошел до т).

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

Для величин и Огп выбрано усеченное нормальное распределение. V^ считается равномерно распределенным на отрезке чтобы подчеркнуть

неустойчивость сети. Максимальная пропускная способность V^ здесь - это физическая характеристика самого пропускного канала.

Остальные параметры при оценке длительности миграции считаются заданными постоянными величинами:

• Структура распределенной системы: множество узлов и схема связей между ними,

• Ту — сетевая задержка (latency) при передаче данных между узлами i и j. Эта задержка фактически определяется физическим расстоянием между узлами, поэтому меняться не может,

• d - глубина поиска (максимальное количество узлов, которое может пройти запрос с поиском),

• М- общее количество узлов в сети.

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

В основном подходе для представления в модели времени передачи данных объема Fno соединению между узлами i и j (обозначим его ®*(V)) с пропускной способностью Vv и задержкой

= f + (1)

У

Пусть теперь узлы / и j не являются соседними. Рассмотрим множество путей из / в j PIJ={Tr:lr = (l0 = i,li,...,lrA,lr= j)}, состоящее из цепочек узлов,

являющихся соседями 1Г. Определим &jj(V) следующим образом:

= (2)

l'er'j к=0

Доказывается, что минимум в (2) достигается на элементе множества Рц.

Пусть он достигается на некоторой цепочке l'r = (1*0,...,!*) (эта цепочка -случайный вектор). Тогда успех/неудачу передачи данных между i и j будет описывать величина

(3)

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

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

®хя-*в\= Е(&1) = const

вгп^ в] =Е(&1) = const (4)

К. = const

• Пересылка пакета всегда успешна:

= 1 V(n,*i) (5)

• Порции файла равномерно разбрасываются по узлам распределенной системы.

• Представления других величин оставим неизменными: случайная величина (¿п и константы г и й, а также длительности двух этапов

миграции Тв, Ти и объемы К,, Г? и

Пусть в распределенной системе М узлов. Расположение порций

Ф,

определяется в модели случайным вектором Ф" =

где компоненты {Ф,}^,

одинаково распределенные случайные величины, принимающие значения 1 ,...,М

с равной вероятностью ( —). Значение величины Ф, означает номер узла, на

М

котором лежит 1-я порция файла. Определим конкретнее вероятностное пространство вектора ФА :

• Множество элементарных исходов О - всевозможные векторы с целыми компонентами из [1 ,М].

• Алгебра событий - все подмножества О.

• Вероятностная мера - функция, определенная классическим образом. Третья глава.

В третьей главе на основании описанных выше моделей решается задача о прогнозировании длительности поиска в распределенной системе, использующей М-Л-схему при хранении.

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

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

Ускорение поиска достигается изменениями параметров самой системы: ее структуры, схемы хранения. Направления этих изменений определяются результатами процедуры предварительного прогнозирования длительности поиска.

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

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

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

2. В окрестности поиска есть к необходимых порций. Тогда процедура может закончиться досрочно, когда до центрального узла дойдет информация о к-й порции. Длительность досрочного завершения обозначим через Тк sl¡„,.

Полный обход.

Пусть процедура поиска глубины d запускается на узле ve. Время полного обхода выразим через величину y(TTL,ri)~ время ожидания сообщения о завершении операции на узле п с момента рассылки своим соседям запроса с TTL-характеристикой равной TTL:

у( 0,и) = 0, (6)

y(TTL,n) = mm{TTL-T, max{03. +6>2 + (&\ + y(TTL-l,n))x

x[H(TTL - TTL(n)))] + в\п}} где N(n) - множество соседей узла и, а Н(х) - модифицированная функция Хевисайда:

Г1,еслидг > О

Я(х)Н . (8)

[О, если х < О Тогда длительность полного обхода ТЫ1 = y(d, w).

Досрочное завершение.

Обозначим время, за которое запрос дойдет до узла и от центрального, S(n): SM = 0; S{ri) = min {б(п) + 0] + <93J (9)

леЛЧл) " ""

Пусть nrM = {ni,n1,...,nr{n)) — маршрут пакета от центрального узла до п, который и реализует это самое минимальное время S(n). Обозначим через Д («) время отсылки ответа от узла п центральному узлу по маршруту иг(л) до i-го узла маршрута:

<*,<» = 0; 4(л) = А+,(и)+<5^ +0„^),/=г(/1),г(«)-1,...,о (Ю)

Обозначим через G подмножество узлов из окрестности поиска, содержащих искомые порции. То есть, G = {n\Qn>0}. Рассмотрим множество чисел Л + Л = {t(h) = S(h) + Ä(h)\heG). Упорядочим его элементы так, чтобы всегда выполнялось: /, < . Тогда:

И+и | i И+и|

'о+ S (t,+rt,)-H{k - Y,Qj +1), если X Q, > к

j' о i-» U1;

2 • MaxTime , иначе.

Общее время поиска:

Т = Tk_sUse¡ + (ТЫ1 - Tk ¡hsJ- Н (Tl sllsts - MaxTime) (12)

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

продемонстрирована на распределенной системе из 20-ти узлов (рис. 1). Параметры //-¿-схемы: Л' = 10Д = 5. Глубина поиска <1 = 3.

На рис. 2 представлены графики функций распределения длительности поиска при выборе узлов под номером 20 и 5 в качестве центральных. Данная совокупность параметров, например, гарантирует, что время поиска файла на узле №20 с вероятностью 0.8 не будет превышать 3 сек., а на узле №5 - примерно 1380 мск.

Четвертая глава.

В четвертой главе решается м

задача о длительности поиска в /. С18

распределенной системе с

регулярной структурой в условиях 8 '/н

точечной загруженности. Она решается с помощью двух п _ ,„

описанных во второй главе о— д 4 - ©

моделей. Разъясним используемые понятия, саму задачу и путь решения.

Регулярность структуры.

Регулярной назовем

распределенную систему, каждый узел которой соединен ровно с / соседями. В данной работе все примеры были выполнены для / = 4, т.е. для графов в виде прямоугольной (квадратной)

Вероятность

.©V

,'11

Рис.1. Структура распределенной системы

1

08............ .....

06' 04 02

Время.

0 ЗВ 1033 1300 20ВЗ аи зло ЗН) М«

Вероятность

0806' 04: 02)

Время.

в»"ая>' ¿го авп"зао"«ск Центоальный узел = 5.

Центральный узел = 20.

Рис. 2. Функция распределения длительности поиска.

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

При такой структуре, например, нетрудно посчитать количество узлов, достигаемых из центрального ровно за г шагов Ц: £) =4/, а также количество

Перенумеруем все узлы распределенной системы: 1,2,...,А/. Пусть дан набор узлов с актуальной информацией: <р'2,Л> где У/',/^ < М. Каждому такому узлу соответствует количество запросов к нему, растущее со временем:

(0 = <*,•/

(14)

Требуется найти среднего значения

зависимость 45*1й длительности поиска, как случайной величины, от 4

3.51

Средняя длительность поиска, мс яшш теоретическая

имитационная

70

ТО 20 30 40 50 60 70 80 9СГГО)

С, с

Рис. 4. Изменение средней длительности поиска со временем, вычисленное по разным молелям

Процент успеха, %_____________________

времени T(t).

Результаты.

Представленные модели были "" проверены на конкретном примере. Для расчетов была выбрана 1.5 распределенная система из 121 узла, { организованных в виде квадратной решетки. Параметры схемы хранения файлов: N = 50, к = 25. На трех узлах с номерами 6, 33 и 89 была размещена информация, актуальность которой повышалась со временем по закону R(t) = a,t, где а, =200, 500 и 300, соответственно. Шаг по времени, с которым пересчитывались средние 60i значения длительности поиска, равен 50 1 сек. Среднее время передачи данных между соседними узлами без учета 40 загруженности равно 5000 мс. 30

Графики получившихся

зависимостей средней длительности 20 поиска от времени представлены на ю рис. 4. Видно хорошее совпадение графиков разных моделей при ' небольшом росте загруженности (для этого вероятность успеха пересылки данных между соседними узлами в имитационной модели была взята равной 1 для всех соединений). Начиная с некоторого момента (/«30 с.) на имитационной кривой начинает сказываться рост неудачно завершившихся процедур поиска: при некотором критическом уровне загруженности ответы присылаются узлам после истечения соответствующих таймаутов и, поэтому, игнорируются. В этом можно убеждает график на рис. 5, также рассчитанный при имитационном моделировании. Лавинообразное падение вероятности успешного завершения процесса поиска также начинается примерно с 30 секунд.

"10 2 0 30 40 50 60 ТЬ 80" 50 100

с

Рис.5. Процент успешного завершения процесса поиска.

Во второй модели таймауты не учитываются, поэтому она дает строго возрастающую прямую.

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

Пятая глава.

Базовые термины.

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

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

Два этапа миграции.

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

Собрать на новой машине его слепок по последний момент времени /,с.

Скопировать с прежней машины на новую файл с разницей состояний виртуального сервера в моменты t' и /.

Имитационное моделирование.

Обозначим искомую длительность миграции через Тм, а длительности копирования на новую машину базовой части виртуального сервера из сети и файла с разностью состояний (эти этапы миграции описаны в разделе «Два этапа миграции») Тв и TD, соответственно (индексы от слов Base - базовый и Difference - разница). Тогда

'Г' ------(Т Т 1 /1 СЛ

1и -тал1'в>'о/> V—;

Найдем функцию распределения Тв - (*). Благодаря постоянству 6>|,6>„2 и У„т длительность сборки порций базовой части Тв здесь может принимать только

дискретные значения, равные 7), = (К ) + 02+б„3Д—), где п = 1,...,М, а с -

к

целевой узел миграции.

Перенумеруем М узлов распределенной системы по возрастанию Тп: Г1<Тг<...<Т1<...<Тм, и сгруппируем рядом стоящие узлы с одинаковыми Т„ в отдельные множества £¡,...,(2,, г<М:

Ь'Щ-Ъ . (20)

V/ = 1..А/ - 1,у/, е й, У/2 е й+1:7; < гл Тогда вероятность для длительности сборки порций базовой части Тв принять значение Т], Р{ТВ = Т]} , будет равна вероятности найти последнюю из необходимых, к-ю порцию файла на одном из узлов из множеств <21I'., соответственно.

Итак, в новой модели Тв - случайная величина, принимающая дискретный ряд значений Т> с вероятностями Р{ТВ = Т1}. Их совокупность и представляет собой распределение Тв.

I

Обозначим через Б, область поиска, покрываемую за Т/. Б, ' = .

1

Пусть также, для общности, £)О = 8О=0 (пустое множество). Рассмотрим набор событий:

к-\

А1 =|^)({5 содержится] порций}^| ^содержит > к-]порций}) (21)

Приведем ряд утверждений относительно Д, доказанных в диссертации. Утв.1. Все события А1,А2,...,АГ- независимы. Утв.2. Ах и Аг и... и Аг = О.

Утв.З. Длительность сборки порций базовой части Тв может быть равна Т в том и только том случае, если в | содержатся у < к -1 порций искомого файла и 2 содержит не менее к-] порций, то есть, идентичны события: {Тв = 7^} = А1 . Уте. 4. Вероятности Р(А1) определяются формулами

(22)

м М м

пъфф^^к - (23)

2 < / < г — 1

tо м м

Итак, утверждения 1-3 позволяют нам искать Р(А,) вместо Р{ТВ = T¡}, а утверждение 4 дает численные выражения для них. Кратчайшие времена достижения узлов <9.3n(F) вычислим по алгоритму Дейкстры. Распределение длительности миграции Тм полностью определяется формулами (19), (22) - (24).

Результаты.

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

1,2i

0.4

0.35

0.3

0.25

0.2

0.15

0 1

?!

0.05 ¡г

ti

0 Г*

Теоретическая модель Имитационная модель

"0.5

Длительность миграции, мс

i

0.S 0.6 0.4 0.2 0

Вероятность

Имитационная модель Теоретическая модель

Длительность миграции, мс[

I 1.5 2 "15 " " у' .3.5 "О 0.5 1 1.5 2 2.5 3 Рис. 6. Распределение длительности миграции виртуального сервера.

.3.5

0.7 Вероятность

0 6

05

0.4

03 Имитационная модель \

0.2 Теоретическая модель 1 \ i >

0.1 1----- ■

0 /Й к

5 хЮ46

1

0.9 0.8 0.7 0.6 0.5' 0.4 0.3 0.2 0.1 0

Вероятность

Теоретическая модель Имитационная модель

0

'тт 2 3 4 5 . _4 б

Длительность миграции, мс хЮ

Дли I сльность миграции, мс

Рис. 7. Распределение длительности миграции при постоянной пропускной способности в имитационной плотности вероятности различимо разделено на три группы. Первая (до 2,2-104мс) соответствует расположению к порций базовой части на узле 5 и его ближайших соседях (узлах 3, 4, 10, 11). Вторая (3,5-104 -4,0-10" мс), самая

вероятная, - расположению к порций на соседях «второго порядка» узла 5 (узлах 1,2, 7, 8, 13, 15, 16). Третья (более 5,3-Ю4 мс) - на самых дальних узлах.

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

j/max

графики, но с постоянной пропускной способностью V:J = 9 . Нетрудно

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

Шестая глава.

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

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

• Pj(t) - количество тактов процессора, требуемых заданием j в момент /,

• Dj(t) - объем запросов задания j к диску в момент t,

• Mj(i) - объем запросов задания j к оперативной памяти в момент t,

а также:

• V — объемом необходимых данных.

Считаем известными типы всех задач, планируемых к запуску на двух выбранных машинах сети: i и /.

Модель вычислительного узла.

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

a) Диск компьютера представляем устройством, обрабатывающим запросы с некоторой постоянной скоростью D0 - объемом запросов, обрабатываемых в единицу времени. Запросы, которые не успевают быть обработанными, становятся в одну общую очередь.

b) Модель работы процессора ничем не отличается от работы диска: это устройство с постоянной скоростью обработки запросов Р0 - количеством операций, выполняемых в единицу времени.

c) Такую же модель выберем и для оперативной памяти. Представим его устройством, обрабатывающим запросы со скоростью М0.

Заметим, что явление сброса страниц оперативной памяти на диск (так называемый своп памяти) учитывается в функции £>,(/).

Предположения и допущения.

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

• Не учитывается взаимодействие задачи с внешними устройствами, кроме диска, памяти и процессора. Учет всех возможных устройств просто невозможен. Хотя бы потому, что постоянно появляются новые. Поэтому мы выделили основные.

• Постоянство скорости обработки запросов устройствами, (линейная зависимость количества обрабатываемых данных от объема входных). В реальности это не совсем верно. Обычно запросы к устройству буферизуются и отсылаются пакетами фиксированного размера. Для диска в ОС Windows 2003, например, этот размер составляет 64 КБ. Однако учет этих особенностей требует доскональных знаний о размере каждого посылаемого заданием запроса. Сложность их получения и учета практически исключает этот путь. К тому же непостоянство скорости обработки будет нивелироваться при больших объемах запрашиваемых данных.

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

• Выполняющиеся на машинах задания считаем равноприоритетными. Предположение сделано для удобства расчетов. Оно позволяет упростить модель: общая очередь запросов к устройствам согласуется с реальностью только при этом допущении. В общем случае это была бы очередь с приоритетами.

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

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

На машине / выбрано задание. Необходимо определить, ускорит ли ее выполнение перенос на машину /.

Решение.

Общая схема.

Перенос задания на другую машину ускорит его выполнение, если T\t0)>T^VJ) + T'(t0 + T^VJ)), где:

• T'(t0) - длительность выполнения j-го задания на машине i, если оно начнется в момент времени t0,

• T'JiVj) - длительность переноса данных объема К по сетевому каналу между компьютерами i и /.

Длительность выполнения T'(t0) разобьем на постоянную и переменную составляющие:

Г(/0) = 72+ДГ(О (25)

Здесь Т0' - время выполнения нашего задания на «пустой» i-й машине, без других выполняющихся заданий, а А7"'(/0) - задержка выполнения у'-го задания, связанная с одновременным выполнением других. Последняя часть определяется количеством и типами выполняющихся заданий. Только она зависит от начального момента запуска j-го задания.

Сетевые расходы.

Длительность передачи данных объемом V между узлами i и / будем

вычислять в рамках стандартной модели, где каждое сетевое соединение характеризуется двумя параметрами - пропускной способностью V и физической задержкой (латентностью) т'1:

= (26)

Если узлы i и / не являются непосредственными соседями, и путь от / к I содержит несколько физических каналов с различными параметрами V?, то

V'1 = min V!'. t '

Задержка.

Суммарную задержку, связанную с одновременным выполнением других заданий в момент / > /0, AT'(t0,t), разобьем на три части по типу вызывающих ее устройств:

□Г(*0,0 =D7>(/0,/) -Л -1С (/„,/), (27)

где DTf.(taj) - процессорная

_ „ . . f Объем запросов

задержка, О TD (/„,/) - дисковая | щ

задержка и □ TM(t0,t) - задержка оперативной памяти. Поскольку модель работы всех трех устройств одинаковые, то выпишем полученный в работе результат в виде OTx(t0,t), X e{P,D,M}:

Пусть X(t) = ^X'(t) -

i

суммарный объем запросов к устройству X для рассматриваемой машины (рис. 8),

t

Ix(t) = J[^(i) - Xoys, a ix(t) = arg min/д. (i). Тогда объем очереди к устройству X

XY0 ^ .

t'a t'h

Рис.8. Объем запросов к ресурсу одной машины

в момент / равен К(/) = тах{ | [Л'(5)-Л'0]Л,0}) а задержка для /-го отрезка

процессорной активностиу'-й задачи на ['„»'Л:

1 * А= ТГ[^(С)- тах{К(/Г)- "С. -'Г'Ш + |(Х(5)- тт{Х(*),*„})<&] (28) о

Задержка в момент времени I:

I АГ, (/:,/;). (29)

Постоянный член.

Для вычисления Г0' - времени выполнения рассматриваемого задания на «пустой» г'-й машине, без других выполняющихся заданий (постоянного члена (25)) предлагается два способа. Первый - простой и очень трудоемкий: измерить потребление ресурсов заданиями каждого типа на всех компьютерах сети. Этот способ даст самые точные результаты и при небольших вычислительных сетях вполне оправдан. Второй: измерить графики потребления на одной модельной машине. Пересчитывать эти функции для любой машины исходя из данных о ее аппаратном обеспечении (объемы памяти и диска, скорости доступа к ним и быстродействие процессора).

С реализацией первого способа вопросов возникнуть не должно. Остановимся на втором. Утверждения, приводимые ниже, доказаны в работе.

Сначала предъявим требования к модельной машине. Пусть (Р'0,О1,М'0) - ее характеристики, а ( Р*(/),£*(/), Л/'(/)) - функции потребления ее ресурсов рассматриваемым заданием.

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

Перейдем к пересчету функций потребления ресурсов, считая далее утверждение 5 выполненным. Рассмотрим функции:

/,(г) = )р'т,1м (г) = |м'(0<Й,/о(г) = . (30)

'о 'о

Вектор /(г) = (/Дг),/м(г),/0(г)) - суммарный объем ресурсов, потребленный к моменту г. Поскольку /Дг) фактически показывает номер выполняемой на момент г инструкции, то точка /(г) определяет, какое суммарное количество

«т)

Кт).-

Цх)

Ш

Рис.9. Кривая потребленных ресурсов

запросов к памяти и диску потребовалось заданию в момент выполнения инструкции 1Р{т).

Утв. 6. Кривая 7(г) инвариантна относительно смены машины выполнения.

Утв. 7. Если мы знаем вид инвариантной кривой 7(г) и одну из функций потребления рассматриваемым заданием ресурсов некоторой вычислительной машины P(t), M(t) или D(t), то можем восстановить остальные.

Утв. 8. Рассмотрим некоторую машину вычислительной сети с параметрами Р0, М0 и D0. Пусть на отрезке [ta,tb] справедливо: P'(t)> Р0, M\t)>M0 и £>'(/) > D0. Тогда на этой машине:

• Отрезок [ta,tb\ перейдет в [ta,tb],ib >tb в том смысле, что часть задания, выполненная на модельной машине в течение [/я,/6], на данной машине выполнится в течение [ta,tl]. Конец отрезка tb равен:

• Если максимум в (31) равен первому члену, то на отрезке [ta,tb] P(t) = Р0,

если второй, то M(f) = М0, если третий - D(t) = D0. Процедура пересчета функций потребления P(t), M(t) и D(t) некоторого компьютера вычислительной сети из известных функций P'(t), M'{t) и D'(t) модельной машины описана в диссертации.

В заключении описываются основные результаты и выводы работы.

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

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

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

О /

(31)

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

4. Предложена математическая модель миграции виртуального сервера в децентрализованной распределенной системе, использующей N-k-схему хранения данных, на основании которой получены оценки длительности миграции.

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

Список публикаций по теме диссертации.

1. Петров В.А. Транзакционная модель изменений в распределенном хранилище. // Совр. проблемы фундаментальных и прикладных наук. Управление и прикладная математика: Труды XLVI научной конференции. / МФТИ - М.: Долгопрудный, 2003. - С. 50.

2. Петров В.А. Расчет времени поиска файла в распределенной системе, использующей N-k-схшу при хранении. // Совр. проблемы фундаментальных и прикладных наук. Управление и прикладная математика: Труды XLVII научной конференции. / МФТИ - М.: Долгопрудный, 2004. - С. 53.

3. Петров В.А., Тормасов А.Г. Расчет времени поиска файла в распределенной системе, использующей N-k-схему при хранении. // Процессы и методы обработки информации, - М. МФТИ, 2005. - С. 68-76.

4. Петров В.А. Доставка информации пользователю в распределенных системах. // Совр. проблемы фундаментальных и прикладных наук. Управление и прикладная математика: Труды XLVIII научной конференции. / МФТИ - М.: Долгопрудный, 2005. - С. 43.

5. Петров В.А., Тормасов А.Г. Доставка информации пользователю в распределенных системах // Проблемы выч. математики, мат. моделирования и информатики, сборник научных трудов, - М.: МЗ Пресс, 2006, С. 156-194.

6. Петров В.А. Особенности поиска в распределенной системе с регулярной структурой // Совр. проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLIX научной конференции. / МФТИ - М.: Долгопрудный, 2006. - С. 56-57.

7. Петров В.А., Тормасов А.Г. Влияние пропускной способности соединений на длительность поиска в регулярных графах // Моделирование процессов обработки информации, сборник научных трудов - М.: МФТИ, 2007. - С. 260-271.

8. Петров В.А., Луковников В.В., Кобец А.Л., Влияние пропускной способности соединений на длительность поиска в регулярных распределённых системах // Научное творчество молодежи. Часть IV. Материалы XI Всероссийской

научно-практической конференции. - Кемерово: Кемеровский гос. универ-т,

2007.-С. 10-11.

9. Петров В.А. Влияние пропускной способности соединений на длительность поиска в регулярных распределённых системах // ХХХ1П Международная молодежная научная конференция Гагаринские чтения, секция Информационные системы и прикладные информационные технологии в социально-экономической сфере - Москва: Московский авиационный технологический институт, 2007. - С. 246-247.

Ю.Петров В.А., Тормасов А.Г. Функции потребления ресурсов заданием на различных компьютерах вычислительной сети // XXXIV Международная молодежная научная конференция Гагаринские чтения, секция Информационные системы и прикладные информационные технологии в социально-экономической сфере - Москва: Московский авиационный технологический институт, 2008. - С. 232.

П.Петров В.А., Тормасов А.Г. Перенос задания в вычислительной системе // Моделирование и обработка информации, сборник научных трудов - М.: МФТИ, 2008. - С. 207-216.

12.Петров В.А., Тормасов АХ. Длительность поиска в распределенной системе с регулярной структурой в условиях точечной загруженности // Информационные технологии, - М.: Новые технологии, 2008. - № 8. - С. 714.

13.Петров В.А. Тормасов А.Г. Измерение длительности миграции виртуальных серверов в распределенной системе // Труды V научно-практической конференции Метрологическое обеспечение измерительных систем, Пенза,

2008.-С. 32-42.

14.Петров В.А. Тормасов А.Г. Длительность миграции виртуальных серверов в распределенной системе // материалы 5-ой Российской научно-технической конференции "Математическое моделирование и компьютерный инженерный анализ", Екатериинбург, специальный выпуск "Вестник УГТУ-УПИ", УГТУ-УПИ, 2008. - С. 65-70.

15.Петров В.А., Тормасов А.Г., Миркин А.Л. Длительность миграции виртуальных серверов в распределенной системе // Вестник НГУ. Серия: Информационные Технологии. - 2008 - Т.6, вып. 3. - С. 38-57.

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

и

Петров Виктор Анатольевич

МОДЕЛИРОВАНИЕ ПЕРЕНОСА И ПОИСКА ДАННЫХ В ДЕЦЕНТРАЛИЗОВАННОЙ РАСПРЕДЕЛЕННОЙ СИСТЕМЕ, ИСПОЛЬЗУЮЩЕЙ Ы-к-СХЕЫУ ХРАНЕНИЯ ИНФОРМАЦИИ.

Автореферат

Подписано в печать 16.10.2008 Формат 60x90/16. Уел печ л 1.0. Тираж 80 экз. Заказ No 570. Московский физико-технический институт (государственный университет)

Печать на аппарате Rex-Rotaiy Сору Printer 1280. НИЧ МФТИ.

141700, г Долгопрудный Московской обл, Институтский пер, 9, тел.: (095) 4088430, факс (095) 5766582

Введение.

1. Актуальность темы.

2. Цель работы, задачи исследования.

3. Научная новизна.

4. Практическая ценность.

5. Краткое содержание работы.

I. Обзоры существующих систем.

1. Системы хранения данных.

Google File System (GFS).

Pastry.

Beehive.

2. Системы доставки информации.

Akamai.

Border Gateway Protocol (BGP).

Выбор ближайшего веб-сервера.

3. Методики моделирования.

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

Моделирование распределенных систем с помощью сетей Петри.

И. Модели распределенной системы.

1. Круг рассматриваемых систем.

Предпосылки.

Схема хранения файлов.

2. Имитационная модель.

Обозначения.

Передача данных.

Усеченное нормальное распределение.

3. Теоретическая модель.

III. Прогнозирование длительности поиска.

1. Процедура получения файла.

Обоснование выбора.

Описание процедуры.

2. Постановка задачи.

3. Вывод времени поиска.

1. Обозначения.

2. Время поиска.

4. Особенности практического использования выведенного.

1. Метод расчета.■.

2. Выбор начальных параметров.

5. Пример использования.

1. Условия расчета.

2. Представление результатов.

3. Результаты.

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

1. Базовые понятия. a) Регулярность структуры. b) Точечная загруженность.

2. Математическая постановка.

3. Имитационное моделирование.

4. Теоретическая оценка.

5. Результаты.

V. Длительность миграции.

1. Задача о миграции.

Базовые термины.

Два этапа миграции.

Математическая постановка.

2. Оценка длительности миграции.

Имитационная.

Теоретическая.

3. Сложность алгоритмов.

Имитационного.

Теоретического.

4. Пример.

Выбор распределений.

Распределенная система.

Результаты.

VI. Перенос задания в вычислительной системе.

1. Задача о переносе.

Актуальность задачи.

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

Модель компьютера.

Предположения и допущения.

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

Общая схема.84

Сетевые расходы.85

Вычисление задержки.85

Функции потребления ресурсов. Вычисление постоянного члена.92

Заключение.97

Список использованных источников.99

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

Введение.

1. Актуальность темы.

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

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

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

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

Приведем в заключение основные результаты и выводы работы:

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

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

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

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

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

1. Хасин М.А. Модель распределенного хранилища в глобальной сети. //

2. Работа на соискание степени кандидата физико-математических наук. -М.: МФТИ, 2001 -93 с.

3. Чернова Н.И. Теория вероятностей: Курс лекций, pdf. (http ://www.nsu.Ri/mmf/tvims/chernova/tv/portr.pdf).

4. Гнеденко Б.В. Курс теории вероятностей, М.: Наука, 1988 - 448 с.

5. Rowstron, P. Druschel Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems, pdfj (http://research.microsoft.com/~antr/PAST/pastry.pdf).

6. Pastry, html. (http://en.wikipedia.org/wiki/Pastry %28DHT%29).

7. Ramasubramanian V., Sirer E. G. Beehive: 0(1) Lookup Performance for Power-Law Query Distributions in Peer-to-Peer Overlays, pdf. (http .7/www.cs. Cornell. edu/People/egs/papers/beehive .pdf).

8. Ghemawat S., Gobioff H., Leung S.T. The Google File System, pdf. (http://labs.google.com/papers/gfs-sosp2003.pdf).

9. Strickland, Jonathan, How the Google File System Works, HowStuffWorks.com, 2008, html. (http://communication.howstuffworks.coi'n/google-file-system.htm).

10. Google File System, http://en.wikipedia.org/wiki/GoogleFileSystem.

11. A Distributed Infrastructure for e-Business Real Benefits, Measurable Returns. - Akamai White Paper, October 2001, html., (www.akamai.com).

12. Ratul Mahajan, Akamai, html. (http://research.microsoft.com/-ratu1/akairiai.html).

13. Border Gateway Protocol, html. (http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito doc/bgp.htm#l 020583 )•

14. BGP4 Case Studies/Tutorial, Sam Halabi, cisco Systems, html. (http://www.ittc.ku.edu/EECS/EECS 800.ira/bgp tutorial4).

15. BGP • Fundamentals, html. (http://www.riverstonenet.coin/support/bgp/fimdaiTientals').

16. Yair Amir, AlecPeterson, David Show, Seamlessly selecting the best copy from Internet-wide replicated web-servers, Johns Hopkins University, html. (http://citeseerx. ist.psu.edu/viewdoc/summ ary?doi=l 0.1.1.40.6523).

17. Google Dance The Index Update of the Google Search Engine, html. fhttp://dance.efactory.de/).

18. Yair Amir and Ciprian Tutu. From total order to database replication. Proceedings of the International Conference on Distributed Computing Systems, Johns Hopkins University, November 2001, html. (www.cnds.jhu.edu./publications).

19. C.C. Бежитский, E.C. Семенкин Эволюционные алгоритмы для автоматизации проектирования распределенных систем обработкиинформации и управления, doc. (raai.org/resurs/papers/kii-2006/seminar/Bezhitskiy.doc).

20. Беэюитский С.С. Выбор оптимальной , структуры аппаратно-программного комплекса системы управления движением автомобильного транспорта, // Вестник университетского комплекса: Сб. научных трудов Вып. 6 (20). - Красноярск: ВСФ РГУИП, НИИ СУВПТ, 2005.

21. Семенкин Е.С., В.Л. Лебедев Методы обобщенного адаптивного поиска для синтеза систем управления сложными системами. М.: МАКС Пресс, 2002.

22. И. А. Ломазова Вложенные сети Петри и моделирование распределенных систем, pdf. (http://www.botik.ru/PSI/disk 20/e-book/e-book/l-4/02-Lomazo va-Vlozhennve-seti-p-337.pdf).

23. И.Котов В. Е. Сети Петри, — М: Наука, 1984 160с.

24. Smith Е. Principles of high-level net theory. // Lectures on Petri Nets: Advances in Petri Nets Lecture Notes in Computer Science. M: Springer Berlin / Heidelberg, 1998, pp. 174-210, html. (http://www.springerlink.eom/content/78125201814583v8).

25. Pinheiro E. Truly-Transparent Checkpointing of Parallel Applications // Federal University of Rio de Janeiro, UFRJ., 2002., ps. (ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/IlR-5755.ps.gzy

26. OpenVZ, html. (httpy/openvz.orgl.

27. Xen, html. (http://www.xen.org),

28. VMware, Inc. html. (http://www.vmware.com).

29. The Sprite Operating System., html. (http://www.eecs.berkelev.edu/Research/Proiects/CS/sprite/sprite.html').

30. Петров В.А. Доставка информации пользователю в распределенных системах. // Совр. проблемы фундаментальных и прикладных наук. Управление и прикладная математика: Труды XL VIII научной конференции. / МФТИ М.: Долгопрудный, 2005. - С. 43.

31. Петров В.А., Тормасов А.Г. Доставка информации пользователю в распределенных системах // Проблемы выч. математики, мат. моделирования и информатики, сборник научных трудов, М.: МЗ Пресс, 2006, С. 156-194.

32. АО.Петров В.А., Тормасов А.Г. Перенос задания в вычислительной системе // Моделирование и обработка информации, сборник научных трудов -М.: МФТИ, 2008. С. 207-216.

33. Петров В.А., Тормасов А.Г. Миркин A.JI. Длительность миграции виртуальных серверов в распределенной системе // Вестник НГУ. Серия: Информационные Технологии. 2008 - Т.6, вып. 3. - С. 38-57.

34. Lustre documentation, pdf. fhttp://wiki.lustre.org/index.php?title^LustreDocumentationy

35. Lustre: A Scalable, High-Performance File System, white paper, http://www.sun.com/servers/hpc/docs/lustrefilesvstem wp.pdf.

36. Peter Druschel, Antony Rowstron, PAST: A large-scale, persistent peer-to-peer storage utility, Rice University, Houston, USA, pdf. (http://frazer.rice.edu/epit/documents/peter/PAST-hotos.pdf).

37. Antony Rowstron, Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Microsoft Research, pdf. (http://research.microsoft.com/~antr/PAST/past-sosp.pdf).

38. A. Rowstron, A-M. Kermarrec, M. Castro and P. Druschel. SCRIBE: The design of a large-scale event notification infrastructure, London, November 2001, pdf. (http://research.microsoft.com/~antr/PAST/scribe.pdf).

39. Castro, M. B. Jones, A-M. Kermarrec, A. Rowstron, M. Theimer, H. Wang and A. Wolman, An Evaluation of Scalable Application-level Multicast Built Using Peer-to-peer overlays, 2003, pdf. rhttp://research.microsoft.com/~antr/P AST/in focom-compare.pdf).

40. B. Y. Zhao, J. D. Kubiatowicz, A. D. Joseph. Tapestry: An infrastructure for fault-resilient wide-area location and routing, Berkeley, April 2001, pdf.http://oceanstore.cs.berkeley.edu/publications/papers/pdf/tapestrysigcomm tr.pdf).

41. Xiaofeng Ren and David Liu, Smart Routing in the Tapestry Routing/Location Infrastructure, pdf. (http://www.cs.berkeley.edu/-kubitron/coiirses/cs252-FOO/proiects/reports/proiectlO report.pdf).

42. Zhao, B.Y.; Ling Huang; Stribling, J.; Rhea, S.C.; Joseph, A.D.; Kubiatowicz, J.D. Tapestry: a resilient global-scale overlay for service deployment 11 Selected Areas in Communications, IEEE Journal on Volume 22, Issue 1, Jan. 2004 Page(s): 41-53.

43. Beehive implementation, html. (http://www.usenix.org/events/nsdi04/tecli/full papers/ramasubramanian/ram asubramanian html/node7 .html).

44. V.Ramasubramanian, E.G. Sirer Beehive: Achieving 0(1) Lookup. Performance in P2P Overlays for. Zipf-like Query Distributions, pdf. (https://research.microsoft.com/users/rama/Beehive/beehive(nsdi).talk.pdf).

45. Stoica, R. Morris, D. Karger, M. Frans Kaashoek, H. Balakrishnan Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, pdf. (http://pdos.csail.mit.edU/papers/chord:sigcomm01/chord sigcomm.pdf).

46. Chord project, html. (http://pdos.csail.mit.edu/chord/\

47. J. Kubiatowicz, D. Bindel, P. Eaton, Y. Chen, D. Geels, R. Gummadi, S. Rhea, W. Weimer, C. Wells, H. Weatherspoon, B. Zhao Oceanstore: An architecture for globalscale persistent store. // Proceedings of ACM ASPLC)S'2000, Cambridge, MA, November 2000.

48. S. Rhea, C. Wells, P. Eaton, D. Geels, B. Zhao, H. Weatherspoon, J. Kubiatowicz. Maintenance-free global storage in OceanStore. // Submission to IEEE Internet Computing, 2001.

49. The OceanStore Project, html. fhttp://oceanstore.cs.berkelev.eduA

50. S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker A scalable content-addressable network. // Proceedings of ACM SIGCOMM'Ol, San Diego, CA, Aug. 2001.

51. P. Fraigniaud, P. Gauron, The Content-Addressable Network D2B, 2003, pdf.fhttp://citeseer.ist.psu.edu/cache/papers/cs/30136/http:zSzzSzwww.lri.frzSz~pierrezSzPOSTSCRIPTSzSzTech-Report1349.pdfyfraigniaud03contentaddressable.pdf).

52. Vedran Kordic Petri Net: Theory and Applications. M.: I-Tech Education and Publishing, 2008.-534 c.

53. Clarke, O. Sandberg, T. W. Hong, B. Wiley Freenet: A Distributed Anonymous Information Storage and Retrieval System, pdfj Qittp://www.cl.cam.ac.uky~twh25/academic/papers/icsi-revised.pdf).

54. The Free Network Project, html. (http://freenetproiect.orR/).68./. Clarke, T. Hong, S. Miller, O. Sandberg, B. Wiley Protecting free expression online with freenet. // IEEE Internet Computing, 6:40-49, 2002.

55. Ian Clarke, Freenet's Next Generation Routing Protocol, July 2003, html. fhttp: //freenetpro i ect. or g/n grouting, html).

56. E. Adar, B. Huberman, Free riding on gnutella, October 2000, pdf. fhttp://www.hpl.hp.com/researcli/idl/papers/gnutella/gnutella.pdf).

57. Clip2, "Gnutella measurement project," May 2001. html. (littp ://www. clip2. com/).

58. R. Anderson. The Eternity service. // Proceedings of PRAGOCRYPT'96, pages 242-252. CTU Publishing House, 1996. Prague, Czech Republic.

59. Brown. Eternity service design. html.,http://www.cvpherspace.org/eternitv-design.htmlY

60. Farsite Project, html. (http://research.microsoft.com/farsite/).

61. J. R. Douceur, A. Adya, J. Benaloh, W. J. Bolosky, G. Yuval; Proceedings of the 18th ACS AC, December 2002, pdf. (http://research.microsoft.com/farsite/ACSAC2002.pdf).

62. SQ.B.Pawlowski, C.Juszczak, P.Staubach, C. Smith, D.Lebel, D.Hitz. NFS version 3 design and implementation. //Proceedings of the Summer USENIX Conference, pages 137-152, June 1994.

63. Network File System, html.http://www.redhat.com/docs/manuals/linux/RHL-9-Manual/ref-guide/ch-nfs.html).

64. InterMezzo, 2003, html. fhttp.V/www.inter-mezzo.org).

65. Bill von Hagen, Using the InterMezzo Distributed Filesystem. Getting Connected in a Disconnected World html. (http ://www. linuxplanet. com/linuxplanet/reports/4368/1 /).

66. Coda File System, html. (http://www.coda.cs.emu.edu/).

67. Peter J. Braam, The Coda Distributed File System, Carnegie Mellon University, html. (http://www.coda.cs.cmu.edu/lipaper/li.htmn.

68. Peter J. Braam, Coda Authentication and Protection, html. ditto ://www. coda, cs. emu, edu/ doc/html/sec. html).87A. Tanenbaum, Distributed Operation Systems, M: Prentice Hall, 1995.

69. Ван Стеен Маартен Распределенные системы. Принципы и парадигмы -М: Питер, 2003.-880 с.89.7". Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы: построение и анализ -М.: Москва, 2004 960 с.

70. Кудрявцев Л.Д. Курс математического анализа М. Наука, 1981, т.1,2.

71. Laszlo Lovasz, Computation Complexity. pdf. fhttp://www.cs.bu.edu/~gacs/papers/lovasz-notes.pdf).