І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах icon

І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах




Скачати 90.65 Kb.
НазваІ. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах
Дата17.08.2012
Розмір90.65 Kb.
ТипЗадача



В існик НАУ. 2004. №1

УДК 004.71(045)

І.А. Жуков, д-р техн. наук

О.П. Мартинова

МЕТОД ПОБУДОВИ ПАРАЛЕЛЬНИХ СТРУКТУР
ДЛЯ ПОШУКУ АЛЬТЕРНАТИВНИХ МАРШРУТІВ У КОМП’ЮТЕРНИХ МЕРЕЖАХ


Інститут інформатики НАУ, e-mail: iit@nau.edu.ua

Розглянуто методи розв’язання задач одношляхової й альтернативної маршрутизації, оцінки часу розв’язання задачі альтернативної маршрутизації відомими алгоритмами на обчислю-вальних машинах і паралельних обчислювальних структурах. Запропоновано системо-аналоговий метод побудови паралельних структур пошуку альтернативних маршрутів у комп’ютерних мережах.
^

Постановка проблеми


Розвиток інформаційних технологій пов’я-заний з широким використанням сучасних комп’ютерних мереж [1–3].

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

Задача передачі інформації в комп’ютерній мережі пов’язана зі зростаючою потребою в передачі й обробці мультимедійної інформації.

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

Реалізація альтернативної маршрутизації вимагає багаторазового розв’язання задачі про найкоротші шляхи на графі-мережі [2–5], що, у свою чергу, призводить до істотного збільшення часу розв’язання задачі альтернативної маршрутизації, оскільки оцінка часу розв’язання задачі альтернативної маршрутизації відомими алгоритмами на обчислювальних машинах зростає пропорційно О(N3), де N – кількість пристроїв комп’ю-терної мережі [2].

Ефективним способом зниження часу розв’язання задачі альтернативної маршрутизації є розробка паралельних обчислювальних засобів для пошуку альтернативних маршрутів у комп’ютерних мережах. У зв’язку з цим актуальною є задача розробки паралельних структур для пошуку безлічі найкоротших шляхів у комп’ютерній мережі.
^

Аналіз останніх досліджень і публікацій


Найкоротші шляхи обробки інформації у комп’ютерній мережі досліджують переважно у двох напрямах [2–9].

Перший напрям, пов’язаний з розробкою ефек- тивних алгоритмів пошуку на обчислювальних машинах найкоротших шляхів у мережах передачі даних, обмежений оцінкою обчислювальної складності алгоритмів О(N3) [2].

Другий напрям, пов’язаний з побудовою паралельних апаратних засобів розв’язання задач про найкоротші шляхи, недостатньо розвинений для випадку альтернативної маршрутизації, коли потрібно знайти безліч альтернативних маршрутів передачі даних [5–9]. Цей напрям пер-спективний, оскільки час розв’язання задачі про найкоротші шляхи на паралельних обчислю-вальних засобах має оцінку О(N) [5].

Метою статті є дослідження можливих шляхів розробки паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах.

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

Перший метод послідовно використовує відомі паралельні обчислювальні засоби розв’я-зання задачі одношляхової маршрутизації.

Послідовний пошук усіх найкоротших шляхів між вузлом-джерелом даних і вузлом-адресатом на паралельних обчислювальних структурах
збільшує час розв’язання задачі альтернативної маршрутизації в К разів (К – кількість альтернативних маршрутів).

Оскільки паралельні обчислювальні засоби розв’язання задачі про найкоротший шлях мають оцінку часу розв’язання О(N), то загальний час пошуку К маршрутів у комп’ютерній мережі
збільшиться в К разів Але при цьому лінійний характер залежності часу розв’язання задачі марш-рутизації від складності комп’ютерної мережі зберігається.

Якщо альтернативних маршрутів декілька (К=23), то такий метод досить ефективний, оскільки більш ніж у два рази збільшує припустиме навантаження в комп’ютерній мережі [2].

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

У комп’ютерних мережах, які мають десятки – сотні пристроїв ^ N, час розв’язання задачі альтернативної маршрутизації на паралельних обчислювальних структурах має кращу оцінку О(N) у порівнянні з оцінкою часу розв’язання цієї задачі на обчислювальних машинах, яка дорівнює О(N3).

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



Рис. 1. Фрагмент моделі комп’ютерної мережі

у вигляді графа:

МВ – модель вузлів; МГ – модель гілок

Моделі вузлів з’єднані парою моделей гілок, які спрямовані назустріч, оскільки передача даних між вузлами комп’ютерної мережі може здійснюватися в протилежних напрямах з різними характеристиками пропускної здатності каналів передачі даних.

Паралельні структури для моделювання процесу передачі даних у комп’ютерній мережі можуть бути побудовані на основі цифрових моделей і алгоритмів розв’язання задачі про найко-ротший шлях [5].

Відомі паралельні структури розв’язують задачу одношляхової маршрутизації в комп’ю-терній мережі.

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

Другий метод побудови обчислювальних засобів реалізує паралельний спосіб пошуку аль-тернативних маршрутів у комп’ютерній мережі.

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

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

Системоаналогова обчислювальна структура реалізує паралельну систему К цифрових аналогів (ЦА) задачі про найкоротший шлях на графі (рис. 2).



Рис. 2. Системоаналогова обчислювальна структура


Система ^ К цифрових аналогів поєднується в системоаналогову модель альтернативної маршрутизації так, щоб К – шляхова маршрутизація в системі К ЦА задачі про найкоротші шляхи не містила в знайдених шляхах загальних елементів модельованого графа у вигляді загальних дуг чи гілок.

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

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

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

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

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

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

Керування у системоаналоговій структурі реалізується на локальному і системному рівнях.

Локальні ПК1 – ПКN здійснюють керування обчислювальним процесом відповідно в кожному ЦА1 – ЦАN.

Під дією локальних керувань кожен ЦА розв’язує задачу альтернативної маршрутизації в комп’ютерній мережі.

Паралельне розв’язання задач альтернативної маршрутизації в ЦА може викликати порушення умови відсутності загальних елементів (дуг чи гілок) модельованого графа комп’ютерної мережі.

Задача вирішення конфліктів між різними найкоротшими шляхами покладена на загальний ПК, який здійснює вибір з безлічі альтернативних маршрутів, генерованих ЦА1 – ЦАN, потрібної кількості паралельних маршрутів, що не мають загальних елементів у модельованому графі комп’ютерної мережі.

Метод системоаналогової побудови системи ^ К ЦА забезпечує оцінку часу розв’язання задачі К шляхової маршрутизації О(N), що в К разів менше, ніж оцінка К О(N) для послідовного методу багаторазового розв’язання задачі одношляхової маршрутизації.

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

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

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

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

Висновки


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

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

^ Список літератури

1. Городиський В.Б., Жуков І.А., Кадніков В.Т. Інтегрована обчислювальна мережа системи «Сирена-2.3» – високі інформаційні технології в області телекомунікацій і мереж передачі даних // Вісн. НАУ. – 2002. – № 1. – С. 11–17.

2. Вишневский В.М. Теоретические основы про-ектирования компьютерных сетей. – М.: Техно-сфера, 2003. – 512 с.

3. Таненбаум Э. Компьютерные сети. – С.Пб.: Питер, 2002. – 848 с.

4. Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Минск: Новое знание, 2003. – 424 с.

5. Васильев В.В., Баранов В.Л. Моделирование задач оптимизации и дифференциальных игр. – К.: Наук. думка, 1989. – 296 с.

6. А. с. 1837314 СССР, МКИ G 06 F 15/20. Устройство для решения задач на графах / А.Г. Додонов, В.П. Приймачук, А.В. Самков, В.А. Чадюк, А.М. Щетинин. – № 4844779/24; Заявлено 27.06.90; Опубл. 30.08.93. Бюл. № 32. – 10 с.

7. А. с. 1817102 СССР, МКИ G 06 F 15/20. Устрой-ство для определения кратчайшего пути на графе / Д.О. Дробахин, Ю.Е. Кудрявцев, А.Г. Шевчик. – 4787521/24; Заявлено 30.01.90; Опубл. 23.05.93. Бюл. № 19. – 6 с.

8. А. с. 1832310 СССР, МКИ G 06 F 15/419, 15/20. Устройство для решения задач на графах /
С.В. Листровой, В.Я. Певнев, С.А. Ильин, М.Л. Ди- кий, Я.В. Боровик. – № 4786697/24; Заявлено 30.01.90; Опубл. 07.08.93. Бюл. № 29. – 8 с.

9. А. с. 1832309 СССР, МКИ G 06 F 15/419. Устройство для решения задач на графах / А.Ю. Лапин. – № 4781238/24; Заявлено 09.11.89; Опубл. 07.08.93. Бюл. № 29. – 4 с.

10. Баранов В.Л., Баранов Г.Л. Системоаналоговое и квазианалоговое моделирование // Элект-ронное моделирование. – 1994. – № 4. – С. 9 – 16.

Стаття надійшла до редакції 11.03.04.

И.А. Жуков, О.П. Мартынова

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

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


I.A. Zhukov, O.P. Martynova

The method of the parallel structure construction for the searching of the alternative routes at the computer’s networks

The method of solutions of the problem of the single route and alternative routing were considered. Time estimation of the solution of the problem of alternative routing by the popular algorithms on the computer and on the parallel calculative structures was cited as an example. The analogue of the system of parallel structure construction of the searching of alternative routes in computer’s networks was proposed.

Схожі:

І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах iconГосударственный стандарт союза сср конструкции и изделия железобетонные радиационный метод определения толщины защитного слоя бетона, размеров и расположения
Л. Г. Родэ, канд техн наук; В. А. Клевцов, д-р техн наук; Ю. К. Матвеев; И. С. Лифанов; В. А. Воробьев, д-р техн наук; Н. В. Михайлова,...
І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах iconПрограма фахового вступного випробування з «Комп’ютерних наук»
«Комп’ютерних наук» для зарахування на навчання для перепідготовки спеціалістів за спеціальністю 05010101 «Інформаційні управляючі...
І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах iconПро Науково-навчальний центр комп’ютерних наук Нова редакція. Версія 01 Загальні положення
Науково-навчальний центр комп’ютерних наук (далі ннц) є структурним підрозділом кафедри комп’ютерних наук Сумського державного університету...
І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах iconМіжнародна науково-технічна конференція, присвячена 80-річчю Дніпропетровської області та 90-річчю
В. а д-р техн наук, проф.; Перегудов В. В., д-р техн наук, проф.; Рудь Ю. С., д-р техн наук, проф.; Сидоренко В. Д., д-р техн наук,...
І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах iconМоделювання розповсюдження вірусів в комп’ютерних мережах засобами пакету gpss
Мережеві віруси для свого розповсюдження використовують протоколи, або команди комп'ютерних мереж, а також електронні пошти. Існують...
І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах iconФормат опису модуля
Знати основи методології web програмування для відображення та пересилання інформації в комп’ютерних мережах
І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах iconФормат опису модуля
Знати основи методології проектування програмного забезпечення для опрацювання та пересилання інформації в комп’ютерних мережах
І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах iconОсновні напрямки робіт в рамках проекту 530601-tempus-1-2012-1-pltempus-smhes на кафедрі комп’ютерних наук СумДУ
Створення та розвиток навчальних центрів провідних іт – підприємств регіону на базі кафедри комп’ютерних наук
І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах iconРозпорядження " 14 " 11 20 11 р. №184 /роз м. Київ Про поселення студентів факультету комп’ютерних наук до гуртожитку
На підставі витягу з протоколу засідання комісії з поселення факультету комп’ютерних наук Національного авіаційного університету
І. А. Жуков, д-р техн наук О. П. Мартинова метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах iconРозпорядження " 14 " 1 1 20 1 1р. №185/роз м. Київ Про поселення студентів факультету комп’ютерних наук до гуртожитку
На підставі витягу з протоколу засідання комісії з поселення факультету комп’ютерних наук Національного авіаційного університету
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи