Проектування мереж

ЛАБОРАТОРНЫЙ ПРАКТИКУМ на тему: «МЕРЕЖІ ЕОМ І ЗАСОБИ ТЕЛЕКОМУНІКАЦІЙ «.

Методичні вказівки до лабораторним роботам з дисципліни «Розподілені інформаційно-обчислювальні мережі. Лабораторний практикум. /Упорядники: В. Ф. Гузик, В. М. Решетняк, В. Г. Сидоренко, Б.І. Левін (ТРТУ), В.П. Ільїн, В.К. Шмідт, Н. А. Буренев (СПбГЭТУ). — Таганрог, ТРТУ, 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), і = 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. Середнє час затримки сполучення каналі з номером і обчислюється як: де: 1/7m4i0 — середня довжина повідомлення (бит/сообщение), c4i0 — пропускну здатність цього каналу (бит/сек.),.

7l4i0 — інтенсивність потоку повідомлень (сообщений/сек.) у тому канале.

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

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

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

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

де l4j0 — довжина канала,.

V (c4j0) — стала составляющая,.

S (c4j0) — змінна составляющая.

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

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

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

Розрахунок необхідних пропускних здібностей каналів зв’язку виробляється з урахуванням переданих каналами потоків інформації (з інтенсивності потоку від однієї термінала, числа терміналів, середньої довжини повідомлень). Пропускна спроможність каналу поставив у вікні меню «Channel params ». Перебір каналів здійснюється опцією меню «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 із чотирьох. Мізін І.А., Богатирьов В. А., Кулешов О. П. Cети комутації пакетів. М.:Радио і зв’язок, 1986.-408 з п’ятьма. Філліпс Д., Гарсиа-Диас А. Методи аналізу мереж. /Пер. з анг.- М.:Мир, 1984.-496 з 6-ї. Шварц М. Мережі ЕОМ. Аналіз і проектування. М.:Радио і зв’язок, 1981. 336 с.