Інформаційну систему вважаємо замкнутою (усі запити обслуговуються), а зміст файлів фрагментованим настільки, що звертання до інших файлів не має перетинань з інформацією, використовуваною цими файлами у власних інтересах. У цих умовах потрібно здійснити реплікацію так, щоб у системі перетворених файлів виконувалася умова:

Алгоритм реплікації файлів і упорядкування бази даних інформаційної системи зводиться до виконання наступних етапів:

За статистичними даними будується граф повного інформаційного обміну між файлами мережі. Виконується розмітка графа. Виділяються підграфи на множині вершин, що ототожнюються з файлами кожного з вузлів (зоряні графи).

На підграфах формуються матриці звертань Аn, Am файлів вузла S1 до інших вузлів виду:

,

.

Виконується транспонування матриці Am і обчислення матриці

Аn - Am Т .

4. Виконується лінійна операція, що завершує процес реплікації

.

Приведемо приклад, що ілюструє приведену методику.

Нехай в двох вузлах S1 та S2 розміщено по три фрагменти файлів так, що .

Статистичні оцінки звертань:

Q1 = 110, q1 = 30, q2 = 40, q3 = 40;

Q2 = 80, q4 = 20, q5 = 40, q6 = 20;

n1 =10, n2 = 20, n3 = 25, n4 =15, n5 =20, n6 =10;

m14 =10, m15 =5, m16 = 5, m24 = 15, m26 =5, m34 = m35 = m36 = 5;

m41 = 5, m51 = 5, m52 = 10, m53 = 5, m62 = 5, m63 = 5.

Граф інформаційного обміну між файлами обох вузлів зображений на рис.5. Вершини графа пронумеровані відповідно до індексації файлів, дуги позначені числом звертань. Виділені підграфи зображені на рис.6.

Складемо матриці звертань:

, .

Так проводяться два підготовчих етапи реплікаціі .

Далі знаходимо:

, .

У результаті цих дій виконана часткова реплікація вихідних файлів. На графах рис.6 це виражається у ліквідації зустрічних дуг, в інформаційному плані – у переадресації фрагментів інформації з одних вузлів мережі на інші. Наприклад, файл 1 перетвориться у файл , файл 2 у і т.д. так, що в результаті перетворень одержимо спрощені графи (рис.7) з односпрямованими дугами.

З графів, побудованих на рис.7, бачимо, що реформовані файли , , не обслуговують 10, 15 і 5 запити.

Рис. 5. Граф інформаційного обміну між файлами

Рис. 6. Індивідуальні графи

Рис. 7. Індивідуальні графи

Аналогічним чином, реформовані файли , , не обслуговують 5, 10 і 5 запити. Так на перетворених файлах у 30 випадках йде переадресація з S1 до S2, у 10 випадках з S2 до S1.

Порівнюючи число переадресацій на первинних файлах (80) з отриманим числом (40) на реформованих файлах, бачимо істотне їх зменшення.

Четвертий етап реплікації файлів можна здійснити двома способами:

дублюванням файлу на вузлі S1 і переадресацією фрагментованої інформації з файлу до файлу і з файлу до файлу ;

тільки переадресацією інформації.

Очевидно, що перший варіант не адекватний лінійному перетворенню і змінює загальну кількість файлів. У цьому варіанті реформовані файли будуть такими:

,

.

В другому варіанті одержимо замість вихідних файлів:

1 = (1, (6,4)), 2= (2 ,(4)), 3= (3 ,(4)) S1,

4 , 5 = (5, 2), 6 S2.

Граф повного інформаційного обміну (рис.5) на цьому етапі перетвориться в безліч ізольованих вершин так, що поставлена умова виявляється виконаною. Запропонована методика допускає узагальнення для системи з довільним кінцевим числом вузлів Si, у якій вибіркові середні можуть розглядатися як невипадкові функції часу.

2.2. Метод розподілу інформації за вузлами обчислювальної мережі

Постановка задачі. В процесі функціонування КІАС запити користувачів розділяють спільні ресурси мережі: обчислювальні потужності, канали зв’язку, бази даних тощо. Як наслідок, під час виконання запиту користувача час повного виконання запиту перевищує мінімальний час повного виконання запиту у випадку, коли б цей запит міг використовувати всі ресурси системи в монопольному режимі, тобто виникають затримки, спричинені спільним використанням ресурсів мережі. Отже необхідно розробити метод оптимального розподілу інформаційних ресурсів серед вузлів розподілених обчислювальних мереж. Визначено два критерії, на підставі яких розв'язується ця задача: мінімізація загального часу обробки запиту та мінімізація кількості звертань до інших вузлів при обробці запиту.

Використання сучасними організаціями технології “клієнт-сервер” робить актуальною проблему доступу до віддалених баз даних і комбінування інформації з двох чи більше фізично розділених вузлів ІС. Основний недолік технології фізичного розподілу даних – високі вимоги до швидкості і надійності їх передачі. У цьому випадку технологія тиражування (replication) даних дає можливість представити кожну базу даних у виді локальної за рахунок локального розміщення даних, необхідних для виконання запиту, у даному вузлі.

Однією з найбільш важливих під час проектування та адміністрування розподілених комп’ютерних ІС є задача оптимального розподілу інформаційних ресурсів, яку ми розглядаємо як задачу розподілу файлів серед вузлів обчислювальних мереж. При реалізації задачі прийняття рішень про передачу пакетів даних важлива обчислювальна простота алгоритмів і малі об’єми потоків службової інформації, якою необхідно обмінюватись між вузлами мережі для забезпечення роботи алгоритмів.

В процесі функціонування КІАС запити користувачів розділяють спільні ресурси мережі: обчислювальні потужності, канали зв’язку, бази даних тощо. Як наслідок, під час виконання запиту певного користувача час повного виконання запиту, як звичайно, перевищує мінімальний час повного виконання запиту у випадку, коли б цей запит міг використовувати всі ресурси системи в монопольному режимі, тобто виникають затримки, спричинені спільним використанням ресурсів мережі. Крім того, при переповненні буферів каналів зв’язку чи надмірній завантаженості обчислювальних потужностей деякі запити можуть бути взагалі не оброблені. Середній час виконання запитів користувачів визначає якість обслуговування мережі.

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