Лабораторний практикумпо темі:
"МЕРЕЖІ ЕОМ І ЗАСОБИ ТЕЛЕКОМУНІКАЦІЙ"

Методичні вказівки до лабораторних робіт з дисципліни
"Розподілені інформаційно-обчислювальні мережі. Лабораторний практикум.
/Укладачі: В. Ф. Гузик, Н. В. Решетняк, В. Г. Сидоренко, Б. І. Левін
(ТРТУ), В.П. Ільїн, В.К. Шмідт, Н.А. Буріння (СПбГЕТУ). - Таганрог, ТРТУ,
1995. - ___с.

Пропоновані методичні вказівки призначені для студентівспеціальності 22.01-22.04. Чи включають в себе загальні методичні вказівкипо роботі з програмним лабораторним комплексом NET_LAB, на якомуреалізовані лабораторні роботи, а також описи лабораторних робіт,присвячених методам аналізу та синтезу структур інформаційнихобчислювальних мереж.

1. ОСНОВНІ ВИЗНАЧЕННЯ І ПІДХОДИ ДО ВИБОРУ СТРУКТУРИ

ГЛОБАЛЬНОЇ інформаційно-обчислювальної мережі

Структура глобальної інформаційно-обчислювальної мережі (ГІВС) --топологія - сукупність пунктів (терміналів, вузлів комутації і т.п.) із'єднують їх ліній або каналів зв'язку. Вона показує потенційніможливості мережі з доставки інформації між окремими пунктами цієїмережі. Як моде -чи структури мережі найбільш часто використовуються Графова моделі. Граф G (A, B)має безліч вершин a4ij7eA0, що відповідають пунктам мережі, ібезліч дуг (ребер) b4ij7e0B - ліній зв'язку між a4i0 і a4j0. Кожнійвершині може приписувати деякий набір чисел: пропускна спроможність вузла c4i0, вартість вузла s4i0 і т.п. Кожне ребро може мати вагу ввигляді набору чисел: довжини лінії l4ij0, пропускної здатності c4ij0,вартості s4ij0 і т.п.

Для запису структури мережі і кількісних оцінок її елементіввикористовують наступні матриці:

1. Матриця зв'язності (суміжності) G = 7220g4ij7220, де g4ij0 = 1, якщоє ребро, що зв'язує вершину a4i0 з вершиною a4j0, і g4ij0 = 0, якщоребро відсутній.

2. Матриця довжин ребер (каналів зв'язку) L = 7220l4ij7220, де l4ij --відстань від пункту a4i0 до пункту a4j0.

3. Матриця пропускних здібностей (ємностей) ребер
С = 7220с4ij7220, де с4ij0 - Максимальна кількість біт у секунду, що можебути пропущено по ребру b4ij0.

4. Матриця вартості S = 7220s4ij7220, де s4ij0 - вартість ребра міжпунктами a4i0 ді a4j0 ..

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

Путь7 m4st0 з вузла a4s0 у вузол a4t0 - впорядкованапослідовність ребер, що починається в a4s 0і що закінчується в a4t0, нещо проходить двічі через один і тот4 0же узел.4 0Путь4, 0 намічений длядоставки повідомлень між заданою парою вузлів, називається м а р ш р у т ом, а процес встановлення таких маршрутів --м а р ш р у т и з а ц і є ю. Р а н г о м шляху називається число ребер,утворюють даний шлях.

Пропускна здатність шляху визначається найбільш вузьким місцем --мінімальною пропускною здатністю ребер, що утворюють шлях. З в я з н о с ть ю мережі називається мінімальне число незалежних шляхів між будь -парою вузлів. С е ч е н н е мережі - неізбиточная сукупність ребер,які треба вилучити з мережі, щоб порушилася її зв'язність. Перерізами
7s4st 0по відношенню до вузлів a4s0 і a4t0 називаються такі перетину, прияких ці вузливиявляються в різних підмережі. Пропускна здатність перерізу визначаєтьсяяк сума пропускних здібностей ребер, що входять в дане розтин.

Вимоги до переданим потоків повідомлень в більшості випадківзадаються у вигляді матриці тяжіння (вимог на передачу потоківінформації) 7F0 = 722f4ij7220, де 7f4ij7 0 - середня інтенсивність потоку звузла a4i0 у вузол a4j0.

Для ГІВС характерне використання широкого діапазону класівструктур з різною кількістю вузлів і ліній зв'язку, які в загальномувипадку неоднорідні і мають велику кількість різноманітних параметрів.
Існуючі та проектуються інформаційні мережі в більшості випадківє багаторівневими. Якправило, така мережа складається з магістральної децентралізованоїрозподіленої мережі верхнього рівня (горизонтальна мережа) іцентралізованих низових мереж (вертикальні) в нижньому рівні. Структурамережі кожного рівня може володіти своєю внутрішньою ієрархією. Складнаструктура мережі може бути розділена на більш прості структури.
Найпростішими структурами є наступні: з паралельним,послідовним і радіальним (зіркоподібних) з'єднанням елементів.
Всі інші структури можуть бути отримані шляхом комбінації найпростішихструктур.

Централізовані ГІВС характеризуються наявністю безлічі абонентськихпунктів (терміналів), довільно розташованих на деякій площі ікерованих з одного центру обробки інформації мережі (центру комутації).
Абонентські пункти пов'язані з центром мережі за допомогою каналів зв'язку.
Найпростішими структурами централізованої мережі є радіальна
(зіркоподібна) і послідовна (цепочечная). Зіркоподібна структурамає в загальному випадку більш протяжні лінії зв'язку, а, отже, ідорожчі. У мережі з цепочечной структурою сумарна довжина ліній зв'язкуменше, однак така мережа менш надійна, тому що відмова однієї лінії зв'язкуможе призвести до порушення зв'язку для багатьох абонентів. ГІВС деревоподібнійструктури є комбінацією найпростіших централізованих мереж,що дозволяє трохи підвищити надійність мережі в порівнянні з цепочечноймережею без значного збільшення протяжності мережі.

При підвищенні вимог до надійності і при переході до інтенсивнонавантаженим лініях зв'язку (що найбільш характерно для магістральнихмереж) застосовуються складні комбіновані (розподілені) структури мережі
(від структури типу "кільце" до повно-структури). При синтезі такихструктур вимогидо надійності задаються зазвичай у вигляді вимоги k-зв'язності. Число лінійзв'язку, їх довжина і пропускні спроможності значною мірою визначаютьвартість всієї мережі. Для радіальної і послідовною (цепочечной)структури мережі число ліній зв'язку N4c0 = N-1, для кільцевої N4c0 = N, дляповно-N4c0 = N770 (N-1)/2, де N - загальна кількість пунктів мережі.
Повнозв'язна структура є найбільш надійною і живучою, але найменшекономічною. Із збільшенням розмірності мережі, а, отже, і ззбільшенням обсягів інформації доцільний перехід до ієрархічниммереж. На нижніх рівнях ієрархії підвищення ефективності використанняліній зв'язку досягається застосуванням концентраторів.

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

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

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

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

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

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

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

Вимоги до переданим потоків повідомлень в більшості випадківзадаються у вигляді матриці вимог на передачу потоків (трафіку)
7F0 = 722f4ij7220, де 7f4ij7 0 - середня інтенсивність потоку з вузла a4i0,призначеного вузла a4j0. Вартості обладнання мережі повинні бути заданідля всіх потенційних ліній зв'язку в залежності від їх пропускноїздатності с4i0: s4i0 (с4i0), i = 1, 2, ..., m, де s4i0 (с4i0) --вартість i-ої лінії зв'язку при її пропускної здатності с4i0; m - число ліній зв'язку.

Безліч ліній зв'язку, відповідне можливої топології, позначимо
B. Число ліній зв'язку при N вузлах може доходити до N770 (N-1)/2, якщодопустима будь-який зв'язок між вузлами.

Обозначім7 L0 = (7l410, 7l420 ,..., 7l4m0) - вектор середньої величинипотоку через лінії зв'язку при оптимальних маршрутах потоків повідомлень, 7l4i0
- Середній потік повідомлень (інформації) у i-лінії. Такий вектор 7L0називається багатопродуктових потоком. Він є результатом підсумовуванняоднопродуктових потоків:де 7l0 - потік від вузла a4j0 до вузла a4k0, що направляється

5i0 по i-й лінії зв'язку.

Матриця 7F0 і спосіб вибору шляхів передачі інформації
(маршрутів) однозначно визначають вектор 7L0.

Позначимо також C = (c410, c420 ,..., c4m0) - вектор пропускнихздібностей ліній зв'язку, T - середня величина затримки передачі, [T] --максимально допустима величина середньої затримки. Тоді завдання виборутопології ГІВС може бути сформульована так:

- задані розташування джерел та одержувачів інформації мережі,матриця вимог на передачу потоків Ф, функції витрат s4i0 (с4i0) длявсіх потенційних ліній зв'язку; m

- потрібно мінімізувати S (B, C) = 7S0 s4i0 (с4i0) 5,0 5i = 1де B - безліч ліній зв'язку потужністю m, відповідних можливоїтопології, за умов 7L, 0C, 7 0T7, 0 [T]. Під потужністю будеморозуміти число реальних (проводових) ліній зв'язку в каналі зв'язку.

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

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

2. ПРИЗНАЧЕННЯ І ТЕХНІЧНА РЕАЛІЗАЦІЯ ПРОГРАМНОГО

Лабораторний комплекс NET_LAB

У ході виконання лабораторних робіт для полегшення етапупроектування структури ГІВС використовується програмний лабораторнийкомплекс (ПЛК) NET_LAB.

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

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

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

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

Комплекс призначений для виконання на комп'ютерах в класі IBMсумісних машин і має здатність самонастроювання під архітектуру.
Персональні дані кожного користувача зберігаються в захищеній базіданих.

Вимоги до технічних засобів: IBM PC/XT/AT, MS DOS не нижче 3.0, відео-адаптер VGA (EGA, Hercules, SVGA, MDA). Обсяг комплексу: 127
Кбайт.

Програмний комплекс розроблений на кафедрі Вт ТРТУ за програмою
"Перспективні інформаційні технології" (підпрограма "Інформатика")
Державного Комітету Російської Федерації з вищої освіти.

4. ОРГАНІЗАЦІЯ ГЛОБАЛЬНИХ МЕРЕЖ в рамках стандарту ISO

4.1. Вступна лабораторна робота.

OSI - багаторівнева організація глобальних мереж

5. ПРОЕКТУВАННЯ ГЛОБАЛЬНИХ МЕРЕЖ

5.1. Лабораторна робота N 1.

Синтез глобальної мережі радіальної структури

Мета роботи

Ознайомлення з методами аналізу та синтезу централізованихінформаційних мереж.

Вихідні дані та завдання до роботи

задані місця розташування джерел інформації, інтенсивностізапитів до центру обробки інформації. Кожен вузол-концентраторобслуговує повідомлення терміналів, пов'язаних з ним (в гуртку кожногоміста виводиться число терміналів). Будемо вважати, що всі терміналигенерують однаковий потік повідомлень. Інтенсивність і середня довжинаповідомлень одного терміналу виводиться у вікні "Terminal params".

Необхідно оптимізувати структуру мережі (ввести місцецентрального вузла та пропускні спроможності ліній зв'язку). При виборіцентрального вузла мережі використовувати алгоритм "центр мас". Критерійоптимізації задається викладачем.

Вихідні дані генеруються ПЛК NET_LAB індивідуально для кожногостудента (або бригади) і виводяться на екран.

Теоретичне введення до роботи

Розглянемо алгоритм побудови інформаційної мережі зіркоподібнійструктури - "центр мас". Вихідними даними є:

- безліч місць розташування на заданій території абонентськихпунктів А (i), де i = 1 ,..., N;

- матриця пропускних спроможностей каналів зв'язку
С = 7220с4ij7220;

- матриця вартості ліній зв'язку S = 7220s4ij7220.

При побудові мережі абонентські пункти підключаються доконцентраторів, або безпосередньо до єдиного центру мережі. Напершому етапі завдання спрощується шляхом групування абонентських пунктів ізаміни кожної групи терміналів еквівалентним вузлом, розташованим в центрімас і мають вагу, пропорційний кількості абонентських пунктіввгрупі. При цьому вага нового центру мас W = W4i0 + W4j0, де W4i0 і W4j0 --відповідно ваги вузлів A4i0 і A4j0. В якості ваги будь-якого вузла можевикористовуватися кількість терміналів або сумарний потік повідомлень,створюваний цим вузлом до всіх інших вузлів мережі. Координати новогоцентру мас обчислюються як де X4i0, X4i0, X4j0, Y4j0 - декартових чи географічні координативузлів мережі A4i0 і A4j0 відповідно.

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

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

У лабораторній роботі процес побудови мережі починається з другогоетапи. При цьому число абонентських пунктів, приєднаних до вузла -концентратора, зазначено в гуртку кожного міста. Інтенсивність і середнядовжина повідомлень одного терміналу виводиться у вікні "Terminal params".

Як модель каналу інформаційної мережі прийнята система масовогообслуговування М/М/1. Середній час затримки повідомлення в каналі з номером iобчислюється як: де: 1/7m4i0 - середня довжина повідомлення (біт/повідомлення), c4i0 - пропускна здатність цього каналу (біт/сек .),

7l4i0 - інтенсивність потоку повідомлень (повідомлень/сек.) в цьому каналі.

Очевидно, що навантаження на канал повинна бути менше його пропускноїздібності.

Середній час затримки для всієї мережі обчислюється як: де 7l4ij0 - інтенсивність обміну між i-м і j-м вузлом мережі, n - число вузлів в мережі.

Вартість каналу залежить від пропускної спроможності і довжини, і можебути представлена як

S4j0 = V (c4j0) + S (c4j0) 770l4j0,

де l4j0 - довжина каналу,

V (c4j0) - постійна складова ,

S (c4j0) - змінна складова.

Вартість мережі визначається як сума всіх S4j0.
Порядок виконання роботи

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

На першому етапі на основі алгоритму "центр мас" з урахуванням числатерміналів в кожному пункті проектованої мережі (вказано в гуртку,відповідному пункту (місту) мережі) і відстаней між пунктамивизначається місце розташування центру мережі. Центр мережі вибирається у вікні меню
"Set net center". На екрані центр мережі позначений квадратом.

Розрахунок необхідних пропускних спроможностей каналів зв'язку провадитьсяз урахуванням переданих по каналах потоків інформації (виходячи зінтенсивності потоку від одного терміналу, числа терміналів, середньої довжиниповідомлень). Пропускна здатність каналу задається у вікні меню "Channelparams ". Перебір каналів здійснюється опцією меню" Select channel ".
Обраний канал позначено темним квадратом, параметри каналу відображаються ввікні Channel status.

Для порівняння на екран (вікно Network status) виводяться значеннявартості і затримки поточного варіанту мережі та подоптімального машинного.
У вікні "Optimum" відображається ступінь близькості поточного варіанту мережімашинному. Приклад синтезу централізованої інформаційної мережі наведенона рис. 4.
Контрольні питання до роботи

1. Дати можливі математичні постановки задачі синтезуцентралізованої інформаційної мережі.

2. Яка модель каналу зв'язку використана при розрахунку затримки?

3. Пояснити роботу алгоритму "центр мас".

4. Які параметри впливають на вартість лінії зв'язку?

5. Які спрощення і обмеження використані при синтезі структуримережі?
Зміст звіту

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

5.2. Лабораторна робота N 2.

Синтез глобальної мережі деревоподібній структури .......... 20
Мета роботи

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

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

Критерій оптимізації та алгоритм синтезу задається викладачем.

Вихідні дані генеруються ПЛК NET_LAB індивідуально для кожногостудента (або бригади) і виводяться на екран.
Теоретичне введення до роботи

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

Розглянемо наступні евристичні алгоритми побудовиінформаційних мереж деревоподібній структури: алгоритм Прима, алгоритм
Краскала, алгоритм Єжи-Вільямса.

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

Крок 0. Кожному вузлу приписується вага W4i0. При цьому W410 = 0
(центральний вузол), всі інші W4i0 рівні нескінченності, i> 1. Витрати
Т4ij0 визначаються наступним чином: S4ij0-W4i0, де S4ij0 -вартість підключення пункту A4i0 до пункту A4j0. Спочатку всі Т4ij0рівні нескінченності, крім T41j0.

Крок 1. Знайти мінімальне значення T4ij0 для вузлів, які ще невключені в мережу.

Крок 2. Перевірка обмежень за пропускної спроможності каналів зв'язку.
Якщо обмеження виконуються перейти до кроку 3, інакше повернутися до кроку
1.

Крок 3. Додати лінію (i, j), встановити W4j0 = 0, змінити вихідніумови і заново обчислити всі Т4ij0. Назад до кроку 1.
Алгоритм Краскала

Крок 1. Вибирається лінія (i, j) з найменшою вартістю.

Крок 2. Перевірка обмежень по пропускній здатності і відсутностіциклів.

Крок 3. Додати лінію (i, j).

Алгоритм повторюється до тих пір, поки всі вузли не будуть включені вмережу.
Алгоритм Єжи-Вільямса

Крок 0. Обчислення всіх параметрів витрат 7t4ij0 = s4ij0-s4i10 для всіхi, j> 1, де s4ij0 відповідний елемент матриці вартості.

Крок 1. Вибрати мінімальну 7t4ij0.

Крок 2. Перевірка обмежень. Якщо обмеження виконуються, то перейтидо кроку 3. Якщо ні, то покласти 7t4ij0 рівним нескінченності і повернутися докроці 1.

Крок 3. Додати лінію (i, j), змінити початкові умови (врахуватипотоки), повернутися до кроку 1.

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

Використання евристичних алгоритмів є компромісом міжпрагненням покращити якість мережі та обсягом обчислень.
Порядок виконання роботи

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

Розташування центру обробки мережі визначається на основі алгоритму
"Центр мас" (див. лабораторну роботу N 1) або задається викладачем.

На основі одного з евристичних алгоритмів (задаєтьсявикладачем) студент, використовуючи опцію меню "create/delete channel"створює бажану конфігурацію мережі, що досягається шляхом вибору дій
"створити/видалити канал" і інцідентних каналу вершин.

Розрахунок необхідних пропускних спроможностей каналів зв'язку провадитьсяз урахуванням переданих по каналах потоків інформації. Пропускназдатність каналу задається у вікні "Channel params". Перебір каналівздійснюється опцією меню "Select channel". Обраний канал позначенийтемним квадратом, параметри каналу відображаються у вікні Channel status.

Для порівняння на екран (вікно "Network status") виводяться значеннявартості і затримки поточного варіанту мережі та подоптімального. У вікні
"Optimum" відображається ступінь близькості поточного робочого варіанту мережі дооптимального. Якщо мережа незамкнута і має петлі, то видається повідомлення пропомилку.
Контрольні питання до роботи

1. Дати математичну постановку задачі синтезу інформаційної мережідеревоподібній структури.

2. Як розраховується затримка в деревоподібній мережі?

3. Пояснити роботу використовуваних алгоритмів.

4. Які моделі та обмеження були використані при проектуваннімережі деревоподібній структури?

5. Які параметри впливають на вартість мережі?
Зміст звіту

Математична постановка задачі. Короткий опис методики,що використовується при синтезі структури інформаційної мережі. Вихідні дані.
Отримана в результаті синтезу структура мережі. Таблиці пропускнихздібностей і завантаження каналів зв'язку. Вартість мережі, затримки в мережі.

5.3. Лабораторна робота N 3.
Синтез глобальної розподіленої мережі
Мета роботи

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

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

Необхідно оптимізувати структуру мережі (вибрати лінії зв'язку та їхпропускні спроможності).

Вихідні дані генеруються індивідуально для кожного студента
(або бригади) програмним комплексом NET_LAB і виводяться на екран.
Алгоритми оптимізації, які необхідно використовувати, і критерійоптимізації вказуються викладачем.
Теоретичне введення до роботи

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

При вирішенні задачі оптимізації необхідно мати залежність затримки
Т від параметрів мережі. У роботах Л. Клейнрок показано, що якщо що входять докожен вузол потоки розподілені по пуассонівської закону та незалежні, адовжини повідомлень розподілені експоненціально, то середній час затримкипакетів умережі, с, де n-число дуг топології, 7l4i0-інтенсивність потоку в i-йлінії зв'язку, c4i0-пропускна здатність i-ої лінії зв'язку, n-число лінійзв'язку, 7g0-сумарний вхідний трафік мережі.

Розглянемо деякі евристичні алгоритми синтезу структуррозподілених інформаційних мереж.
Метод "насичення перетину" (НС)

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

Алгоритм НС "намагається" втримати продуктивність мережі в певнихмежах при ітеративному зниження загальної вартості ліній і дотриманніобмежень на пропускні спроможності, затримку і надійність мережі. Якщо
N410 і N420 - число вузлів у кожному з компонентів, розділених безліччюгілок перетину, до --число гілок в перетині, і трафік рівномірно розподілений між вузлами, товерхня межа пропускної здатності (продуктивності) мережі можнаотримати у вигляді:
Алгоритм НС починає роботу з топології типу "дерево" або іншоїслабосвязанной топології і включає наступні кроки.

Крок 1. Визначити оптимальні потоки в гілках (рішення завдання РП).
Цей крок - маршрутизація - виконується після кожної модифікації топологіїмережі для генерації нових потоків у гілках.

Крок 2. Знайти насичене розтин. Ця процедура здійснюється на кожномукроці маршрутизації.

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

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

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

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

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

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

Застосовується в тих випадках, коли дискретні вартості можуть бути здостатньою підставою апроксимувати увігнутими кривими. Цей методявляє собою ітеративну форму рішення задачі ВПС і РП. Використовуєтьсятой факт, що гілки можуть бути усунені, і, отже, будуть внесенітопологічнізміни по мірі виконання алгоритму, що вирішує задачу ВПС і РП вбезперервної формі. Таке усунення гілок (каналів передачі) відбуваєтьсятому, що вартість мережі D є увігнутою по потоках функцією.
Тому цей ітеративний алгоритм називають також увігнутим методомусунення ребер (ВМУР).

Подоптімальний алгоритм УВ працює таким чином.

Крок 1. Вибрати вихідну топологію, яка в більшостівипадків доцільна повнозв'язна топологія або близька до неї.

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

Крок 3. Виконати алгоритм ВПС і РП. Якщо при будь-якій ітераціїпорушується обмеження зв'язності, тобто при усуненні неекономічною лініїпорушується умова k-зв'язності, то припинити оптимізацію і перейти до кроку
4. В іншому випадку провести алгоритм ВПС і РП до кінця (він заснований наалгоритмі ОП) і після цього перейти до кроку 4.

Крок 4. Діскретізіровать безперервні пропускні спообності,отримані за допомогою подоптімального рішення задачі ВПС і РП. Наприклад,безперервна пропускна здатність може бути округлені до найближчогодопустимого дискретного значення такого, що для нього продовжуєвиконуватися умова T 7,0 [T]. При цьому, мабуть, зміниться повнавартість мережі D.

Крок 5. Провести остаточну оптимізацію потоку застосуванням алгоритму
ВП і, якщо буде потрібно, навіть підстроюванням пропускних здібностей іпотоків.

Крок 6. Повторити кроки 3 - 5 для ряду реалізованих початкових потоків здопомогою випадкового вибору вихідних довжин з потоками, які направляються занайкоротших маршрутах.

Крок 7. Повторити кроки 1 - 6 для ряду початкових топологій.

При проектуванні структури розподіленої мережі обмеження нанадійність зазвичай формулюються у тер?? Інах зв'язності вузлів.
Порядок виконання роботи

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

Використовуючи опцію меню "Create/delete chanel" студент створюєнеобхідну вихідну структуру мережі. Потім, використовуючи опцію "Edit path",визначаються шляхи доставки інформації, тобто проводиться розподілпотоків. У даному режимі включені в мережу канали зв'язку відображаються наекрані пунктирними лініями, а включені в маршрут - суцільними. Опцією
"Select city" обирається місто, для якого будується маршрутна мережа (наекранівін відзначається прямокутником), потім, використовуючи опцію "Select channel",включаються (або виключаються) канали з маршрутів даного міста, прицьому використовуються параметри "Create path" і "Delete path".

опцією "Go back" проводиться повернення в основне меню.После виборувсіх маршрутів здійснюється підстроювання параметрів каналів зв'язку (опція
"Channel params ").

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

1. Дати математичну постановку задачі синтезу розподіленої мережі.

2. Як розраховується затримка в розподіленої мережі?

3. Які моделі та обмеження прийняті при синтезі структуриінформаційної мережі?

4. На які приватні задачі декомпозіруется спільне завдання синтезуструктури розподіленої інформаційної мережі?

5. Пояснити роботу використовуваних евристичних алгоритмів.
Зміст звіту

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

СПИСОК ЛІТЕРАТУРИ
1. Рухман Е.Л., Ільїн В.П., Смирнов М.І. Синтез топологічних структурінформаційних мереж. Л.: ЛЕТІ, 1987 .- 80 с.
2. Жожікашвілі В.А., Вишневський В.М. Мережі масового обслуговування.
Теорія та застосування до мереж ЕОМ. М.: Радіо і зв'язок, 1988.-190 с.
3. Зайченко Ю.П., Гонта Ю.В. Структурна оптимізація мереж ЕОМ.
К.: Технiка, 1986.-168 с.
4. Мізін І.А., Богатирьов В.А., Кулешов А.П. Мережі комутації пакетів.
М.: Радіо і зв'язок, 1986.-408 с.
5. Філіпс Д., Гарсіа-Діас А. Методи аналізу мереж./Пер. с англ .-
М.: Світ, 1984.-496 с.
6. Шварц М. Мережі ЕОМ. Аналіз і проектування. М.: Радіо і зв'язок, 1981 .-
336 с.