Книги по разным темам Pages:     | 1 | 2 |

[2],[7](Как вводятся операции сложения и умножения в полях GF(N), будет описано ниже). Все элементы поля можно занумеровать числами от 0 до N-1. Так как файл это последовательность бит, то для N=2n любой файл можно представить в виде последовательности n-битных кусочков, соответственно в виде последовательности элементов P. Кроме того для простых N близких по значению к степеням 2, например (близко к 256=28 ) или 65521 ( близко к 65536=216 ), файл также легко представляется виде последовательности элементов поля P, для этого он представляется в виде последовательности n-битных частей (n-соответствующая степень двойки, так что 2n близко по значению к N) причем, если какая-нибудь из n-битных частей представляет собой число >= N, то из него вычитается N, и оно также становится элементом поля P. В этом случае к преобразованному файлу мы должны приложить номера частей, к которым необходимо прибавить N, чтобы получить исходный файл. При этом можно считать, что размер файла сильно не увеличится, например, в случае равновероятного распределения бит в файле при N=251 преобразование придется производить только для 5/256~2% байтов файла, а при N=65521 - для 0.02% байтов.

Рассмотрим теперь k-мерное пространство векторов L над полем P. Каждый элемент этого пространства - это k элементов поля P. Теперь каждый файл можно представить в виде последовательности векторов из L. (Если количество бит в файле не кратно kn, то дополняем его нулевыми битами до ближайшего числа, делящегося на kn).

Пусть есть файл f, который представляет собой последовательность векторов l1, l2, Е lm из L. И пусть есть набор Е из n векторов из L: Е={е1,e2,Е en}. Причем этот набор такой, что любые k из них образуют базис в L. Тогда каждому вектору еi из E можно поставить в соответствие часть:

(l1,ei), ( l2, ei), Е ( lm, ei), где (lj,ei) - скалярное произведение векторов lj и ei.

Скалярное произведение любых двух векторов из L есть элемент из P. Поэтому размер такого куска равен n бит. Размер же исходного файла равен m*kn бит. Т. е. размер каждой из полученных частей равен mn, то есть 1/ k от размера самого файла.

Электронный журнал ИССЛЕДОВАНО В РОССИИ 360 Пусть у нас есть теперь произвольные k частей из построенного набора. Обозначим вектора, которым соответствуют части, через 1, 2,Е k, а сами части через 1, 2,Е k, По условию набора Е, эти вектора образуют базис в L. Поэтому матрица А размером k x k, строки которой - вектора 1, 2,Е k, имеет обратную, которую мы обозначим через A-1.

Тогда Ali - столбец, состоящий из i-тых элементов всех кусков. Обозначим такой столбец через Si. Т.е. для любого i [1,m] : li = A-1 Si. Таким образом, мы можем из этих частей восстановить исходный файл. (Естественно, к каждой части должна быть приложена информация о порождающем ее векторе + информация об исходной длине файла - для того, чтобы отбросить потом добавленные нулевые байты).

Следует отметить, что при таком способе представления данных, для получения фрагмента файла li нет необходимости прибегать к сборке всего файла. Мы можем собрать только необходимый фрагмент: li = A-1 Si. Размер li составляет kn бит, что при k~5 и n =8,16,32 составляет несколько байт. Таким образом, существует возможность неполного восстановления файла, обусловленная запросом чтения/записи конкретного участка файла (диапазона байт). Это может оказаться существенной для асинхронной работы процессов, взаимодействующих с файловыми системами.

Итак, для решения задачи нам осталось просто указать алгоритм построения набора векторов, любые k из которого образуют базис. Для каждого ненулевого элемента p поля P строим вектор (1,p,p2, Е pk). Таким образом, мы можем построить N-1 вектор.

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

2.3 Варианты реализации алгоритмов сборки/разборки файлов.

В данной секции рассматриваются варианты реализации алгоритмов сборки/разборки в различных GF(N). (N=65521, N=216) на процессоре Celeron 450.

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

Проще всего поле строится для случаев, когда само N является простым числом. В этом случае обычные операции сложения и умножения по модулю N поле. Оценим производительность такого алгоритма при N=65521. В этом случае количество кусков ограничено числом 65520, что достаточно даже для больших распределенных систем, где количество компьютеров исчисляется тысячами. Пусть s - размер файла (в байтах), количество кусков из которых необходимо собирать файл, как и ранее обозначим через k.

Размер одной части будет s/k. Операция обращения матрицы выполняется один раз и не зависит от s ( состоит из ~k3 операций умножения и сложения), поэтому на оценку производительности не влияет. На сборку файла уйдет s/2k - кратное выполнение операции A-1 Si. На выполнение такой операции уйдет k2 операций умножения и сложения в поле Галуа, что представляет собой k2 операций обычного сложения и обычного умножения и 2k2 операции % (вычисление остатка от деление на N). При этом, используя тот факт, что регистры в процессоре Celeron 32-битные и k < N<216 (то есть сумма k двухбайтных чисел есть число < 232), операцию % можно выполнять не при каждом сложении, а один раз после суммирования произведений строки и столбца. Тогда всего количество операций % будет k2 + k. В итоге получим - sk/2 операций сложения и умножения, и sk/2+s/2 операций %. Учитывая, что по данным Intel [4] для процессора Celeron - имеем:

Электронный журнал ИССЛЕДОВАНО В РОССИИ 361 Операция Число тактов на выполнение Сложение Умножение % (целочисленное деление) и положив, s = 1 000 000 (мегабайт), а k=5, получим, что на сборку 1 МБ уйдет 171 000 тактов. То есть для Celeron 450 получаем скорость ~ 3МБ/сек. Тестовая программа, написанная на Visual C++ 5.0 подтверждает данный результат.

Рассмотрим теперь поля Галуа для N=2n. Стандартное представление такого поля многочлены степени не выше n-1, коэффициенты которых - элементы поля GF(2) остатков от деления на 2 (то есть 0 или 1). Для того, чтобы задать такой многочлен, нужно задать n коэффициентов (0 или 1 - то есть битов) при хn-1, хn-2,Еx, 1. То есть каждый n-битный элемент задает такой многочлен. Сложение и умножение таких многочленов происходит по остатку при делении на произвольный неразложимый многочлен степени n над полем GF(2). Выбор такого многочлена p(x) обусловлен исключительно удобством реализации алгоритма Эвклида для вычисления остатка от деления на него. Таким образом, сложение таких многочленов - это просто операция XOR над соответствующими n-битными элементами. Умножение же можно разложить на два этапа: первый - это последовательность сдвигов и XOR-ов (фактически обычное умножение в котором, сложение заменено операцией XOR), а второй - поиск остатка от деления получившегося после первого этапа многочлена, в общем случае степени 2n-2, на многочлен p(x). Второй этап также реализуется последовательностью сдвигов и XOR. Деление прелагается реализовать как операцию обратную умножению - для каждого числа заранее вычисляется обратный элемент, и деление на число заменяется умножением на число обратное делителю.

При n=16 для реализации операции умножения в GF на компьютере с 32-битными регистрами хватает просто регистровых операций сдвигов и XOR-ов и для реализации алгоритма Эвклида все равно сколько и каких коэффициентов в неразложимом многочлене нулевые, поэтому выбор неразложимого многочлена был произволен - нами был выбран х16+ х5+ х3 + x 1. Такая реализация (что называется в лоб) арифметических + операций, для n=16 на процессоре Celeron 450 при k=5 показывает производительность 0.8 МБ/сек, что является достаточно низким показателем, поэтому авторы предлагают другую реализацию операций умножения и деления.

Используем, тот факт, что в GF(N) существует генератор p, то есть все элементы являются степенью pGF(N). Таким образом, GF(N)={0,p,p2,Е,pN-2,pN-1=1}. В нашем GF(216) генератором является число 3 (многочлен x+1). Вычислим все пары (a,i), такие что a=pi. Сохраним эти пары в две таблицы: log-отсортированную по a, и alog отсортированную по i. То есть : log [pi] = i, alog [i] = pi. Размер каждой из двух таблиц равен 128 КБ. Поэтому имеем для любых элементов a,b из GF(216):

ab = alog[(log[a] + log[b] ) mod (216 - 1)] и a/b = alog[(log[a] - log[b] ) mod (216 - 1)], причем, (log[a] + log[b] ) mod (216 - 1) = log[a] + log[b], если log[a] + log[b] < 216 - 1, и ( log[a] + log[b] ) mod (216 - 1) = log[a] + log[b] - (216 - 1), если Электронный журнал ИССЛЕДОВАНО В РОССИИ 362 log[a] + log[b] >= 216 - 1, а также ( log[a] - log[b] ) mod (216 - 1) = log[a] - log[b], если log[a] - log[b] >= 0, и (log[a] + log[b] ) mod (216 - 1) = log[a] + log[b] + (216 - 1), если log[a] + log[b] < 0.

Поэтому операция mod (216 - 1) заменяется на операцию сравнения и сложения (вычитания). Таким образом, умножение сводится к сложению, а деление к вычитанию.

Такая реализация на том же процессоре Celeron 450 и k=5 дает скорость сборки ~ МБ/сек, что уже позволяет использовать данную реализацию в локальных сетях. Кроме того, результаты можно улучшить путем использования ММХ технологии для одновременного вычисления нескольких арифметических операций.

2.4 Анализ эффективности использования модели.

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

Рассмотрим сначала стандартную скорость ситуацию. Обозначим через V скорость передачи данных в сети (в сети Internet максимальная скорость передачи данных ~1.МБ/сек). Пусть U - скорость канала между клиентским компьютером и хостом, через который он осуществляет соединение с Интернет (см. рис. 2).

Будем рассматривать ситуацию, когда каждый канал в сети используется одновременно N пользователями, это означает, скорость канала в сети понижается до V/N. Будем считать, что U V/N, поэтому скорость получения данных Vэ в нагруженной сети будет: Vэ = V/N.

Исследуем теперь нашу модель в тех же условиях (см. рис. 3). Скорость канала в сети также понижается до V/N, однако k частей файла одновременно поступают на хост клиентского компьютера. Скорость получения данных на хост, таким образом, будет Vх = Электронный журнал ИССЛЕДОВАНО В РОССИИ 363 kV/N. Так как мы предполагаем, что U V/N, то скорость получения данных определяется скоростью получения данных хостом и скоростью сборки файла Vc. Итак, скорость равна:

Vэ = 1/(1/Vх+1/Vc) = 1/(N/kV+1/Vc) = kVVc / (kV+NVc).

Пусть Vc = V, тогда Vэ = kV/(k+N)kV/N=kVэ, так как N k. То есть при существенной загрузке сети, в предлагаемой модели скорость получения данных в k раз выше, чем в стандартных условиях. На рис. 4,5 приведены графики зависимости производительностей двух систем от загрузки сети при. k=5 а = 0.5;В статье приведены реализации, которые при k=5, обеспечивают 0.5; 2, 6. Таким образом, независимо от выбора предлагаемых реализаций, в случае существенной загрузки скорость получения данных будет в 5 раз выше, чем в обычных условиях, однако от выбора реализации зависит, производительность системы в условиях незагруженной сети. В этом случае, чем выше Vc, тем лучше производительность системы.

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

Рассмотрены несколько реализаций модели при N=216, 65521.

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

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

итература:

1. D. Patterson, G. Gibson, R. Katz. A Case for Redundant Arrays of Inexpensive Disks (RAID). / University of California. Berkeley 1987. Ч 26 p.

2. Б. Ван дер Варден. Алгебра. Ч М.: Наука. 1979. Ч 648 с.

3. E. Win, A. Bosselaers, S. Vanderberghe, P. Gersem, J. Vandewalle. A Fast Software Implementation for Arithmetic Operations in GF(2n). / Katholieke Universiteit Leuven. 1997. Ч 12 p.

4. Intel Architecture Software Developer's Manual Электронный журнал ИССЛЕДОВАНО В РОССИИ 364 5. A. Stallings. Data and Computer Communications. Sixth Edition. Ч New Jersey: Prentice Hall. 1999.

Ч 810 p.

6. J. Adamek. Foundations of Coding. Ч Wiley: Interscience. 1991. Ч 336 p.

7. A. Курош. Курс высшей алгебры. Ч М.: Наука. 1975. Ч 431 с.

8. V. Hamann. Making Internet Servers Fault-Tolerant - A Comprehensive Overview. / Материалы конференции УInterner-Россия 96Ф. Ч 7 p.

9. H. Kameda, J. Li, C. Kim, Y. Zhang. Optimal Load Balancing in Distributed Computer Systems (Telecommunication Networks and Computer Systems). Ч Berlin: Springer Verlag. 1996. Ч 251 p.

10. W. Richard Stevens. TCP/IP Illustrated vol. 1Ц3. Ч Addison: Wesley Pub Co. 1994. Ч 2078 p.

11. D. Libertone, M. Brain. Windows NT Cluster Server Guidebook. Ч New Jersey: Prentice Hall. 1998.

Ч 280 p.

12. A. Shamir. How to share a secret. - Communications of the ACM // vol. 24. 1979. Ч pp. 612 - 613.

13. G. Blakley. Safeguarding cryptographic keys. - Proceeding of AFIPS // vol. 48. 1979. Ч pp. 313 - 317.

Pages:     | 1 | 2 |    Книги по разным темам