Зонова мережа зв’язку з комутацією пакетів

Размещено на http://www.allbest.ru/

Курсова робота

Дисципліна: Телекомунікаційні та інформаційні мережі

Зонова мережа зв'язку з комутацією пакетів



Зміст

зв'язок маршрутизація мережа літтл

Вступ

1. Синтез оптимальної топології зонової інформаційної мережі зв'язку

1.1 Використання алгоритму Прима для синтезу найкоротшого дерева

1.2 Використання алгоритму Літтла для синтезу найкоротшого гамільтонового циклу

2. Визначення множин шляхів та їх перерізів методом побудови дерева

3. Аналіз структурної надійності мережі

4. Знаходження множини шляхів при оптимальній маршрутизації в мережі

5. Вибір пропускних здатностей (ВЗП) каналів зонових мереж зв'язку з комутацією пакетів

Висновки

Перелік використаної літератури

Додатки



1. Синтез оптимальної топології зонової інформаційної мережі зв'язку

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

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

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

Крок 4. Вибирається в цьому рядку мінімальний елемент, наприклад, .

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

Кроки 2-3 повторюються доти, поки не буде обране ребро найкоротшого дерева.

Достоїнство алгоритму Прима полягає в простоті реалізації процедури побудови НКД як при обчисленнях ручним способом, так і за допомогою ЕОМ.



1.1 Використання алгоритму Прима для синтезу найкоротшого дерева

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

	Луганськ	Щасте	Алчевськ	Брянка	Стаханов	Первомайськ	Лісічанськ	Северодонецьк	Краснодон	Свердловськ
Луганськ	0	23	44	56	60	69	88	96	49	75
Щастье	23	0	62	73	78	85	84	98	72	98
Алчевськ	44	62	0	14	23	32	72	82	91	117
Брянка	56	73	14	0	9	21	61	71	105	130
Стаханов	60	78	23	9	0	12	62	72	109	130
Первомайськ	69	85	32	21	12	0	40	50	118	149
Лісічанськ	88	84	72	61	62	40	0	10	137	189
Северодонецьк	96	98	82	31	72	50	10	0	145	171
Краснодон	49	72	91	105	109	118	137	145	0	28
Свердловськ	75	98	117	130	130	149	189	171	28	0

Рисунок 1. Матриця відстаней

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

Таблиця 1. 1 крок алгоритма Прима

2	3	4	5	6	7	8	9	10
23	44	56	60	69	88	96	49	75

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

Таблиця 2. 2крок алгоритма Прима

3	4	5	6	7	8	9	10
44	56	60	69	84 (2)	96	49	75

При цьому цифрою 5 у дужках позначені ті значення довжин, що взяті з п'ятого рядка.

Знову вибираємо мінімальний елемент рядка. Діючи аналогічно попередньому, одержуємо новий рядок:

Таблиця 3. 3крок алгоритма Прима

4	5	6	7	8	9	10
14 (3)	23 (3)	32 (3)	73 (3)	82 (3)	49	75

Вибираємо мінімальний елемент рядка. Та шукаємо далі найкоротше дерево.

Таблиця 4. 4крок алгоритма Прима

5	6	7	8	9	10
9 (4)	21 (4)	61 (4)	71 (4)	49	75

Вибираємо мінімальний елемент рядка. Рухаємось по алгоритму далі.

Таблиця 5. 5крок алгоритма Прима

6	7	8	9	10
12 (5)	61 (4)	71 (4)	49	75



Вибираємо мінімальний елемент рядка.

Таблиця 6. 6крок алгоритма Прима

7	8	9	10
40 (6)	71 (4)	49	75

Вибираємо мінімальний елемент рядка.

Таблиця 7. 7крок алгоритма Прима

7	8	10
10 (7)	49	75

Вибираємо мінімальний елемент рядка.

Таблиця 8. 8крок алгоритма Прима

9	10
49	75

Мінімальний елемент рядка.

Таблиця 9. 9крок алгоритма Прима

10
28 (9)

Мінімальний елемент рядка.

Отже, найкоротше дерево буде містити ребразагальною довжиною229 одиниць.

Топологія такої мережі представлена на рис. 2.

Структуру найкоротшого дерева на повнозв`язному графі мережі можна побачити у додатку Б.



Рисунок 2. Структура найкоротшого дерева

1.2 Використання алгоритму Літтла для синтезу найкоротшого гамільтонового циклу

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

Задача синтезу НКГЦ також зветься задачею комівояжера, який, виїжджаючи з деякого пункту, повинний побувати в кожнім з інших пунктів рівно один раз і повернутися у вихідний пункт, проїхавши найменшу сумарну відстань.

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

Алгоритм Літтла, що реалізує метод гілок і границь для рішення цієї задачі, полягає в наступному. Для його роботи вихідними даними є довжини ребер графа між його вершинами, що утворюють матрицю порядку , елемент якої дорівнює довжині ребра між -ю та -ю вершинами, а при відсутності останнього або при йому привласнюється нескінченне значення. Маршрут представляється як безліч з упорядкованих пар вершин: , кожна з який є його ланкою. Довжина маршруту дорівнює сумі відповідних цим ланкам елементів матриці відстаней: . Очевидно, що для будь-якого припустимого маршруту кожен рядок і кожен стовпець матриці містять рівно по одному елементі, що відповідає цьому маршруту. Тому для перебування оптимального (мінімального) маршруту необхідно вибрати рівно один мінімальний елемент у кожнім рядку і кожнім стовпці матриці .

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

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

Побудувавши топологію мережі з використанням алгоритму Прима для знаходження найкоротшого дерева отримали висячі вершини (вершини, які з'єднані тільки з однією вершиною одним ребром): 1, 5, 8. Для цих вершин застосуємо алгоритм Літтла для знаходження найкоротшого гамільтонового циклу (рис. 3).

		0	0	0
	98	?	98	98
=	98	98	?	171
	98	98	171	?

Рисунок 3. Матриця відстаней для висячих вершин

Крок 1. Виконуємо спочатку редукцію рядків поточної матриці відстаней. Для цього в кожнім рядку визначаємо мінімальний елемент і знайдене значення віднімаємо з елементів відповідної рядка. Результати виконання редукції рядків у виді матриці приведені на рис. 4, де додатковий вектор - стовпець містить від'ємники при редукції константи.

Потім виконуємо редукцію стовпців, результати якої у виді матриці приведені на рис. 5, де додатковий вектор - рядок містить від'ємники при редукції константи. Значення елемента, розташованого на перетинанні вектора - стовпця і вектора - рядка , дорівнює сумі всіх констант, що віднімаються =413. Це значення є нижньою границею довжин усіх маршрутів на даному кроці: =413.

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

По скороченій матриці відстаней далі визначаємо мінімальні ненульові значення її рядків і стовпців, що записуємо відповідно у виді вектора - стовпця і вектора - рядка . Матриця разом з цими векторами показана на рис. 4.

		0	0	0		О
	98	?	0	0		?
=	98	0	?	73		73
	98	0	73	?		73
	з	?	73	73

Рисунок 4. Скорочена матриця і значення мінімальних ненульових елементів для 1-го кроку алгоритму

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

Таблиця 10. Вторинні штрафи на 1-м кроці алгоритму

(2,8)	?
(2,10)	73
(8,2)	73
(10,2)	73

Як видно з табл. 10, максимальне значення дорівнює ?. Вибираючи ланку (2,8), можна одержати виграш у відстані, рівний ?.

Отже, модифікована матриця відстаней після викреслювання 2-го рядка і 8-го стовпця, а також заміни елемента на перетинанні 2-го рядка і 8-го стовпця матриці на має вид, приведений на рис. 8.



		?	73
		73	?

Рисунок 5. Поточна матриця відстаней для 2-го кроку алгоритму

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

		0	0		б
	73	?	0		0
	73	0	?		0

Рисунок 6. Скорочена по рядках матриця відстаней на 2-м кроці алгоритму

Потім виконуємо редукцію стовпців, результати якої у виді матриці приведені на рис. 7, де додатковий вектор - рядок містить від'ємники при редукції константи.

		0	0
	73	?	0
=	73	0	?
	В	0	0

Рисунок 7. Скорочена матриця відстаней на 2-м кроці алгоритму

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

Цей оптимальний маршрут є мінімальним гамильтоновим циклом, що зображений на рис. 8.

Рисунок 8. Мінімальний гамільтонів цикл графа

У результаті об'єднання найкоротшого дерева і найкоротшого гамільтонова циклу виходить так називана М-структура (додаток В).

Рисунок 9. М-структура утворена з найкоротшого дерева та найкоротшого гамільтонового циклу



2. Визначення множин шляхів та їх перерізів методом побудови дерева

Для М-структури побудуємо дерево шляхів з вершини 1. Дана вершина є коренем дерева і розміщається на нульовому ярусі. Значення рангу шляху тут R = 0. На першому ярусі (R = 1) розміщаються вершини 2, 5, 8, що мають безпосередній зв'язок з вершиною 1. Далі на другому ярусі від вершини 2 розміщаються вершини, що зв'язані з вершиною 2, а саме 3. Вершина 1 виключається з розгляду, оскільки шлях у вершину 2 пройшов через вершину 1. Від вершини 5 на другому ярусі записується вершина 8, від вершини 8 -- вершина 7, аналогічно записуються вершини на інших ярусах дерева. Максимальне значення ярусу (рангу шляху) дорівнює R_max = N-1 (N - кількість вершин графа).

Дерево шляхів, показано на рис. 10.

Рисунок 10. Дерево множини шляхів

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

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



3. Аналіз структурної надійності мережі

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

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

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

Щоб було легше розраховувати представимо граф у такому вигляді:



Рисунок 11. Початковий граф

При послідовному з'єднанні ребер з коефіцієнтами готовності можна скористатися формулою

, (3.1)

а при паралельному - формулою

. (3.2)

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

Для розрахунку обираємо заданий викладачем коефіцієнт готовності

Знайдемо коефіцієнт готовності між вершинами 8 та 2.

Після спрощення отримаємо такий граф:



K=U

Отримаємо:

/[((U1*U7*U6*U5*U4*U3*U2+U1)-U1*U7*U6*U5*U4*U3*U2*U1)+(U10+U8*U9)-( U10*U8*U9)]-

-[((U1*U7*U6*U5*U4*U3*U2+U1)- U1*U7*U6*U5*U4*U3*U2*U1)*(U10+U8*U9)-( U10*U8*U9)]

/[(U7*U6*U5*U4*U3*U2-U8*U9)*(U7*U6*U5*U4*U3*U2-U8*U9)+U1]-

-[(U7*U6*U5*U4*U3*U2- U8*U9)* (U7*U6*U5*U4*U3*U2-*U8*U9)*U1]

Результуюча надійність зв'язку між пунктами 8 та 10

U11*[(U7*U6*U5*U4*U3*U2- U8*U9)* (U7*U6*U5*U4*U3*U2-

-*U8*U9)+U1]-[(U7*U6*U5*U4*U3*U2- U8*U9)*

*(U7*U6*U5*U4*U3*U2-*U8*U9)*U1]+(1-U11)*

*[((U1*U7*U6*U5*U4*U3*U2+U1)- U1*U7*U6*U5*U4*U3*U2*U1)+

+(U10+U8*U9)-( U10*U8*U9)]-[((U1*U7*U6*U5*U4*U3*U2+U1)-

-U1*U7*U6*U5*U4*U3*U2*U1)*(U10+U8*U9)-( U10*U8*U9)]



4. Знаходження множини шляхів при оптимальній маршрутизації в мережі

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

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

У ході виконання алгоритму Дейкстри кожній вершині привласнюється вага , яка дорівнює довжині найкоротшого шляху від вершини до вершини . При цьому покроковий опис алгоритму має наступний вигляд.

Крок 1. «Позначимо» вершину й привласнимо їй вагу , а ваги інших вершин приймемо рівними деякому максимально можливому значенню.

Крок 2. Приймемо номер вершини .

Крок 3. Для кожної «непозначеної» вершини обчислимо нове значення ваги.

. (4.1)

Крок 4. Перевіримо умову: вага менше його максимально можливого значення. Якщо ця умова виконується, то «позначаємо» вершину з мінімальним значенням і переходимо до кроку 4. У протилежному випадку алгоритм закінчує роботу, оскільки найкоротшого шляху від вершини до вершини в графі даної мережі не існує.

Крок 4. Приймемо номер вершини .

Крок 5. Перевіримо умову: номер вершини . Якщо ця умова виконується, то найкоротший шлях від вершини до вершини знайдений і до нього входять «позначені» вершини. У протилежному випадку переходимо до кроку 3.

Представлений алгоритм можна використовувати для знаходження найкоротших шляхів від деякої фіксованої вершини до всіх інших вершин, якщо на кроці 5 перевіряти, чи є «непозначені» вершини. При відсутності таких вершин алгоритм закінчує роботу. У протилежному випадку переходимо до кроку 3. М-структура для алгоритму Дейкстри показано на рис. 15.

Пропускна здатність по М-структуре

	1	2	3	4	5	6	7	8	9	10
1	0	23	44	0	0	0	0	0	49	0
2		0	0	0	0	0	0	72	0	98
3			0	14	0	0	0	0	0	0
4				0	9	0	0	0	0	0
5					0	12	0	0	0	0
6						0	40	0	0	0
7							0	10	0	0
8								0	0	171
9									0	28
10										0



Рисунок 12. М-структура для алгоритму Дейкстри

Крок 1. , для всіх .

Крок 2. .

Крок 3.

w₂=min{w₁, w₂+l_1,2}=min{?,0+23)=23

w₃=min{w₁, w₃+l_1,3}=min{?,0+44)=44,

w₄=min{w₁, w₄+l_1,4}=min{?,0+?)=?,

w₅=min{w₁, w₅+l_1,5}=min{?,0+?)= ?,

w₆=min{w₁, w₆+l_1,6}=min{?,0+?)=?,

w₇=min{w₁, w₇+l_1,7}=min{?,0+?)=?,

w₈=min{w₁, w₈+l_1,8}=min{?,0+?)= ?

w₉=min{w₁, w₉+l_1,9}=min{?,0+49)= 49,

w₁₀=min{w₁, w₁₀+l_1,10}=min{?,0+?)= ?,

Крок 4. «Позначаємо» вершину V5 та дугу.

Крок 5. .

Крок 6. Визначаємо, що не всі вершини «позначені».

Крок 3.

W₂=min{w₂, w₃+l_2,3}=min{?,44+?)=44

W₃=min{w₂, w₄+l_2,4}=min{?,0+?)=?,

W₄=min{w₂, w₅+l_2,5}=min{?,0+?)= ?,

w₆=min{w₂, w₆+l_2,6}=min{?, 0+?)=?,

w₇=min{w₂, w₇+l_2,7}=min{?,0+?)=?,

w₈=min{w₂, w₈+l_2,8}=min{?,0+98)=121,

w₉=min{w₂, w₉+l_2,9}=min{?,49+?)= 49,

w₁₀=min{w₂, w₁₀+l_2,10}=min(?,0+98)=98

Крок 4. «Позначаємо» вершину V4 та дугу

Крок 5. .

Крок 6. Визначаємо, що не всі вершини «позначені».

Крок 3.

W₂=min{w₃, w₄+l_3,4}=min{?,23+14)=37

w₃=min{w₃, w5+l_3,5}=min{?,0+?)= ?,

w₄=min{w₃, w₆+l_3,6}=min{?,0+?)=?,

w₆=min{w₃, w₇+l_3,7}=min{?, 0+?)=?,

w₇=min{w₃, w₈+l_3,8}=min{?,121+?)=121,

w₈=min{w₃, w₉+l_3,9}=min{?,49+?)=49,

w₁₀=min{w₃, w₁₀+l_3,10}=min{?,98+?)=98

Крок 4. «Позначаємо» вершинуV3 та дугу

Крок 5. .

Крок 6. Визначаємо, що не всі вершини «позначені».

Крок 3.



W₂=min{w₄, w₅+l_4,5}=min{?,0+9)=9

w₃=min{w₄, w₆+l_4,6}=min{?,0+?)= ?,

w₆=min{w₄, w₇+l_4,7}=min{?,0+?)=?,

w₇=min{w₄, w₈+l_4,8}=min{?,121+?)=121,

w₈=min{w₄, w₉+l_4,9}=min{?,49+?)=49,

w₁₀=min{w₄, w₁₀+l_4,10}=min{?,98+?)=98

Крок 4. «Позначаємо» вершинуV6 та дугу

Крок 5.

Крок 6. Визначаємо, що не всі вершини «позначені».

Крок 3.

W₂=min{w₅, w₆+l_5,6}=min{?,0+12)=12

w₃=min{w₅, w₇+l_5,7}=min{?,0+?)= 0 ,

w₆=min{w₅, w₈+l_5,8}=min{?,+?)=?,

w₇=min{w₅, w₉+l_5,9}=min{?,121+?)=121,

w₈=min{w₅, w₁₀+l_5,10}=min{?,98+?)=98,

Крок 4. «Позначаємо» вершинуV2 та дугу.

Крок 5. .

Крок 6. Визначаємо, що не всі вершини «позначені».

Крок 3

w₃=min{w₆, w₇+l_6,7}=min{?,0+40)= 40 ,

w₆=min{w₆, w₇+l_6,8}=min{?,121+?)=121,

w₇=min{w₆, w₇+l_6,.9}=min{?,121+?)=121,

w₈=min{w₆, w₇+l_6,10}=min{?,98+?)=98,

Крок 4. «Позначаємо» вершинуV9 та дугу.

Крок 5. .

Крок 6. Визначаємо, що не всі вершини «позначені».

Крок 3

w₆=min{w₇, w₈+l_7,8}=min{119,121+10)=129,

w₇=min{w₇, w₉+l_7,9}=min{?,49+?)=49,

w₈=min{w₇, w₁₀+l_7,10}=min{?,49+?)=49,

Крок 4. «Позначаємо» вершинуV7 та дугу

Крок 5. .

Крок 6. Визначаємо, що не всі вершини «позначені».

Крок 3.

W₁=min{w₉, w₈+l_9,8}=min{?,129+?)=129,

W₂=min{w₉, w10+l_9,10}=min{98,49+28)=78,

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

w₂: (v₁ ,v₂)=23

w₃: (v₁ ,v₃)=44

w₄: (v₁ ,v₃) ,(v₃ ,v₄)=58

w₅: (v₁,v₃), (v₃,v₄), (v₄,v₅)=67

w₆: (v₁ ,v₃) ,(v₃ ,v₄), (v₄,v₅), (v₅,v₆) =79

w₇: (v₁ ,v₃) ,(v₃ ,v₄), (v₄,v₅), (v₅,v₆), (v₆,v₇)=119

w₈: (v₁ ,v₃) ,(v₃ ,v₄), (v₄,v₅), (v₅,v₆), (v₆,v₇), (v₇,v₈)=129

w₉: (v₁ ,v₉) =49

w₁₀: (v₁ ,v₉)(v₉ ,v₁₀)=78



Рисунок 13. Дерево найкоротших шляхів від вершини - джерела до інших вершин вихідного графа мережі



5. Вибір пропускних здатностей (ВЗП) каналів зонових мереж зв'язку з комутацією пакетів

Крок 1 Постановка задач ВПЗ

Нехай повнозв'язаний граф мережі з комутацією пакетів має вигляд, показаний в додатку А.

Нехай в мережi на 1000 мешканцiв має місце один термінал з інтенсивністю потоків пакетів 20 пакетів/с.Відповідно до кількості мешканців мережних пунктів,отримаємо вектор інтенсивності зовнішніх потоків.

У результаті використання методу М-структура можна отримати комірчасту топологію мережі, яка при з'єднаннях “точка - багатоточка” показана на рисунку у додатку А, а дерево найкоротших шляхів від центрального вузла до інших вузлів мережі за алгоритмом Дейкстри на рисунку 14.

Рисунок 14. Дерево найкоротших шляхів від центрального вузла до інших вузлів мережі за алгоритмом Дейкстри



При цьому сумарна інтенсивність зовнішніх потоків пакетів від центрального до інших вузлів буде.

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

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

Розв'язання у системі математичного програмування Mathcad задачі ВПЗ за критерієм мінімуму середньої затримки пакетів при обмеженні на сумарну пропускну здатність

R	4,356306
E	0,00125
P	0,039063
T	0,019012



c1	13824216		t1	0,000471
c2	4385871		t2	0,000471
c3	5671828		t3	0,000471
c4	8027099		t4	0,000471
c5	7197987		t5	0,000471
c6	4567575		t6	0,000471
c7	3072340		t7	0,000471



Висновки

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

За допомогою алгоритму Прима я синтезував найкоротше дерево мережних пунктів загальною довжиною 322,8 км. У результаті об'єднання найкоротшого дерева і гамільтонового циклу, розрахованого при використанні алгоритму Літтла, отримав так звану М-структуру, для якої виконується умова зв'язності .

В другій частині роботи було побудовано дерево шляхів та були прораховані множини шляхів та перерізи множини шляхів від 1 вершини - джерела до 10 вершини - стоку.

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

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



Перелік використаної літератури

1. Методичні вказівки до курсового проектування з дисципліни "Інформаційні мережі" 2009.

2. Методичні вказівки до курсового проектування з дисципліни "Телекомунікаційні та інформаційні мережі",упорядники: Ю.М. Бідний, О.М. Буханько - Харків: ХНУРЕ, 2011.

3. ,,Теорія графів” Н. Кристовідес, А.Бряндинська. Видання ,,Мир” Москва 1978 р.

4. Коснспект лекцій з предмету "Інформаційні мережі" 2008.

5. Мережа інтернет 2007.



Додаток А

Топологія зонової інформаційної мережі зв`язку



Додаток Б

Найкоротше дерево



Додаток В

Найкоротший гамільтонів цикл



Додаток Г

М-структура

Размещено на Allbest.ru

...