Зміст

МЕТА НАУКОВО-ДОСЛІДНОЇ РОБОТИ

Метою даної роботи є дослідження в області проектування великих розподілених систем. На сьогоднішній день існує безліч розробок у цій області. Ці розробки також стосуються й заснованих на Інтернет технологій.

Алгоритм Дейкстры поиска кратчайшего пути

     Будемо зберігати поточну мінімальну відстань до всіх вершин V (від даної вершини a) і на кожному кроці алгоритму намагатися зменшити ця відстань. Спочатку встановимо відстані до всіх вершин рівним нескінченності, а до вершини а - нулю.

Розглянемо виконання алгоритму на прикладі. Нехай потрібно знайти відстані від 1-й вершини до всіх інших. Кружечками позначені вершини, лініями - шляху між ними ("дуги"). Над дугами позначена їх "ціна" - довжина шляхи. Червоним позначене поточна найкоротша відстань до вершини.

Крок 1

     Ініціалізація. Відстані до всіх вершин графа V = ?. Відстань до а = 0. Жодна вершина графа не оброблена.

Крок 2

     Знаходимо таку вершину (із ще не оброблених), найкоротша відстань до якої мінімально. У нашому випадку це вершина 1. Обходимо всіх її сусідів й, якщо шлях у сусідню вершину через 1 менше поточного мінімального шляху в цю сусідню вершину, те запам'ятовуємо цей новий, більше короткий шлях як поточна найкоротша відстань до сусіда.

Крок 3

     Перший по черзі сусід 1-й вершини - 2-я вершина. Шлях до її через 1-ю вершину дорівнює найкоротшій відстані до 1-й вершини + довжина дуги між 1-й й 2-й вершиною, тобто 0 + 7 = 7. Це менше поточної найкоротшої відстані до 2-й вершини, тому нова відстань до 2-й вершини дорівнює 7.

Кроки 4, 5

     Аналогічну операцію проробляємо із двома іншими сусідами 1-й вершини - 3-й й 6-й.

Крок 6

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

Крок 7

     Практично відбувається повернення до кроку 2. Снову знаходимо "найближчу" неопрацьовану (невикреслену) вершину. Це вершина 2 з поточною найкоротшою відстанню до її = 7.

І знову намагаємося зменшити відстань до всіх сусідів 2-й вершини, намагаючись пройти в них через 2-ю. Сусідами 2-й вершини є 1, 3, 4.

     Перший (один по одному) сусід вершини № 2 - 1-я вершина. Але вона вже оброблена (або викреслена - див. крок 6). Тому з 1-й вершиною нічого не робимо.

Крок 8

     Інший сусід вершини 2 - вершина 4. Якщо йти в неї через 2-ю, то шлях буде = найкоротша відстань до 2-й + відстань між 2-й й 4-й вершинами = 7 + 15 = 22. Раз 22 < ?, установлюємо відстань до вершини № 4 рівним 22.

Крок 9

     Ще один сусід вершини 2 - вершина 3. Якщо йти в неї через 2-ю, то шлях буде = 7 + 10 = 17. Але 17 > уже запом'ятованого раніше відстані до вершини № 3 і рівного 9, тому поточна відстань до 3-й вершини не міняємо.

Крок 10

     Всі сусіди вершини 2 проглянуті, заморожуємо відстань до її й викреслюємо із графа.

Кроки 11 - 15

     По вже "відпрацьованій" схемі повторюємо кроки 2 - 6. Тепер самої "близької" виявляється вершина № 3. Після її "обробки" одержимо такі результати:

Подальші кроки

     Проробляємо те ж саме з вершинами, що залишилися (№ один по одному: 6, 4 й 5).

Завершення виконання алгоритму

     Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видний на останньому малюнку: найкоротший шлях від 1-й вершини до 2-й становить 7, до 3-й - 9, до 4-й - 21, до 5-й - 20, до 6-й - 11 умовних одиниць.

ТЕХНОЛОГІЯ WEB SERVICES

Мережа Інтернет стала загальновизнаним фактором ділового й громадського життя. Широка поширеність і зросла пропускна здатність створюють умови, при яких вигідно вирішувати багато завдань за допомогою інтернет-технологій. Однак Інтернет поєднує в собі багато різних платформ, а інформація втримується в різноманітних джерелах даних. Тому актуально проблему зв'язку таких різнорідних даних, а також створення способу, що дозволяє одержувати їх у вигляді зручному для подальшої обробки. Концепція веб-сервісів (Web Services) покликана вирішити це завдання об'єднання, інтеграції різнорідних систем на основі відкритих стандартів. Дана робота присвячена веб-сервісам, у ній коротко розглянуті основні положення моделі веб-сервісів, а також компоненти цієї моделі й технології, використовувані для їхньої реалізації. Практична частина роботи містить невеликий приклад, що демонструє розробку веб-сервіса й додатків викорстовуючих його. Приклад ґрунтується на реалізації концепції веб-сервісів у рамках Java-технологій. Для розуміння приклада досить базових знань Java. Веб-сервіси є концепцією створення таких додатків, функції яких можна використати за допомогою стандартних протоколів Інтернет. У цей час цю концепцію застосовують і розвивають багато провідних компаній в IT-області. Концепція веб-сервісів реалізується за допомогою ряду технологій, які стандартизовані World Wide Web Consortium (W3C). Взаємозв'язок цих технологій можна умовно представити в такий спосіб.

     Веб-сервіси є одним з варіантів реалізації компонентної архітектури. XML є фундаментом для створення більшості технологій, пов'язаних з веб-сервісами. Для вилученої взаємодії з веб-сервісами використається Simple Object Access Protocol (SOAP) [3]. SOAP забезпечує взаємодія розподілених систем, незалежно від об'єктної моделі, операційної системи або мови програмування. Дані передаються у вигляді особливих XML документів особливого формату. Відповідно до визначення W3C, веб-сервіси це додатка, які доступні по протоколах, які є стандартними для Інтернет. Ні вимоги, щоб веб-сервіси використали якийсь певний транспортний протокол. Специфікація SOAP визначає, яким образом зв'язуються повідомлення SOAP і транспортний протокол. Найбільше часто реалізується передача SOAP повідомлень по протоколі HTTP. Також широко поширене використання як транспортний протокол SMTP, FTP, TCP. Відповідно до визначення W3C, "WSDL - формат XML для опису мережних сервісів як набору кінцевих операцій, що працюють за допомогою повідомлень, що містять документно-ориентовану або процедурно-орієнтовану інформацію" [3]. Документ WSDL повністю описує інтерфейс веб-сервісу із зовнішнім миром. Він надає інформацію про послуги, які можна одержати, скориставшись методами сервісу, і способах звертання до цих методів. Технологія Universal Description, Discovery and Integration (UDDI) припускає ведення реєстру веб-сервісів. Підключившись до цього реєстру, споживач зможе знайти веб-сервіси, які щонайкраще задовольняють його потребам. Технологія UDDI дає можливість пошуку й публікації потрібного сервісу, як людиною, так і програмою-клієнтом. Пошук і публікація в реєстрі надається програмі-клієнтові як набір веб-сервісів реєстру UDDI. Веб-сервіси позиціюються як програмне забезпечення проміжного шару. Використати веб-сервіси можуть як клієнтські додатки, що безпосередньо працюють із користувачем, так й інші додатки (у тому числі й інші веб-сервіси). Веб-сервіси розміщаються на серверах додатків. Розроблювачі концепції веб-сервісів пропонують наступні сценарії застосування веб-сервісів: Веб-сервіси як реалізація логіки додатка (бізнеси-логіки). Тобто, створення нового додатка бізнес-логіка, якого реалізується у веб-сервісі.

Веб-сервіси як засіб інтеграції. Тобто, використання веб-сервіса як способу доступу вилучених клієнтів до внутрішнього ИС компанії, або для організації взаємодії компонента (наприклад, EJB, COM-компонента) з різними вилученими клієнтами.

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

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

4. СТРУКТУРА РОЗПОДІЛЕНОЇ СИСТЕМИ

Структура розподіленої мережі представлена на мал. 4.1. Вона складається із серверної й клієнтської частини. Важливо відзначити, що Web-сервер не працює безпосередньо зі сховищем даних і не реалізує логікові системи. Ці функції зосереджені в Web-сервісі, що пропонує наша система. Всі клієнти, засновані на HTML або WML інтерфейсі, працюють із Web-сервером, у той час як для всіх інших клієнтів наданий Web-сервіс. У такий спосіб навіть внутрішній web-сервер нашої системи є клієнтом для Web-сервісу.

Для вузлів розподіленої системи обрані наступні продукти різних фірм-виробників великих корпоративних систем:

5. БАЗА ДАНИХ

Схема бази даних представлена на малюнку 5.1. Вона описує принцип побудови схеми бази даних на концептуальному рівні. На фізичному рівні буде використанаі СУБД Oracle і відповідно типи даних будуть відповідати тим, які використаються в СУБД. В основному завдяки наступним нововведенням Oracle завоювала в наші дні величезну популярність на ринку СУБД:

Рисунок 5.1 - Cхема даних БД

Рисунок 5.1 - Розділ ринку СУБД для платформи UNIX

Рисунок 5.1 - Розділ ринку СУБД для платформи Windows NT

6. ВИСНОВКИ

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

7. СПИСОК ЛІТЕРАТУРИ

1. Э.Майника, АЛГОРИТМЫ ОПТИМИЗАЦИИ НА СЕТЯХ И ГРАФАХ М.: Мир, 1981,324 стр.

2. А.А.Зыков, ОСНОВЫ ТЕОРИИ ГРАФОВ, НАУКА, 1986, 381 стр.

3. Н.Вирт, АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ, М.: Мир, 1989, 360 стр.

PS:На момент створення цієї сторінки проект знаходиться на етапі розрабобки. Повний текст магістерської роботы буде в 2007 році.