Топології мереж Граф як основа побудови комп ютерної мережі (стр. 1 из 5)

Національний університет

«Києво-Могилянська Академія»

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

Топології мереж.

Граф як основа побудови

комп’ютерної мережі.

виконав

студент ІІІ курса

департамента комп’ютерних

технологій

Кравченко Іван

Науковий керівник: Медвєдєв М. Г.

Київ, 1998 рік

Зміст роботи

1. Вступ.

2. Топології комп’ютерних мереж

2.1 Аналіз топологій мереж

2.2 Вибір топології мережі

3. Структурована кабельна система (СКС)

3.1 Загальні відомості про з’єднувальні матеріали

3.2 Реалізація кабельної системи

3.3 Архітектури комп’ютерних мереж

4. Типові реалізації комп’ютерних мереж

4.1 Методи доступу робочих станцій до середовища передачі данних

4.2 Приклад реалізації мережі середнього підприємства.

5. Висновки

6. Додаток 1

7. Додаток 2

8. Додаток 3

9. Використана література

1. Вступ

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

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

2. Топології комп'ютерних мереж

2.1 Аналіз топологій мереж

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

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

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

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

Машини безпосереднього зв'язку подаються у вигляді графу: кожен процесор позначається вершиною графа, зв'язок між процесорами — дугами. Відстань між процесорами P1',P2' визначається як відстань між вершинами у графі: відстанню є таке мінімальне число d, що існує послідовність P1' = P0, P1, P2, ..., Pd = P2', де Pi - сусід Pi+1; два процесори називаються сусідами, якщо вони з'єднані безпосередньо.

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

Степенем процесора називається кількість його сусідів. Степенем машини безпосереднього зв'язку називається максимальний степінь процесора, задіяного у паралельному комплексі. Будь-який комплекс зі степенем k має, як мінімум, діаметр logP/logk -1 (Готліб та Крускал [16]).

Схемою з'єднання будемо називати сполучення декількох процесорів в один комплекс за деякими правилами.

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

Схема повного з'єднання. Малюнок 1. В ній кожен процес пов'язаний з усіма іншими. Її позитивними рисами є те, що діаметр цієї схеми дорівнює 1, а з'єднання будь-яких двох процесорів відбувається за один такт. На практиці мережі повного з'єднання мають свої недоліки. Через велику кількість дроту такі мережі не можуть мати велику кількість процесорів. Кількість зв'язків, необхідних для комутації P процесорів, дорівнює P*(P-1)/2.

Малюнок 1. Малюнок 2

Схема повного з'єднання. Схема з'єднання в коло

для 6 процесорів. для 6 процесорів.

Схема з'єднання в коло. Малюнок 2. Ця архітектура більш реалістична і будується просто. Кількість дроту дорівнює кількості процесорів. Діаметр дорівнює P/2, середня відстань між процесорами дорівнює приблизно P/4. Передача інформації відбувається по колу за чи проти ходу годинникової стрілки при спільній роботі всіх P процесорів. Для обміну даними між будь-якими двома процесами необхідно зробити не більш ніж P-1 такт.

Двовимірна архітектура мережевого з'єднання [20]. Малюнок 3. Діаметр цієї схеми з'єднання дорівнює 2 * (P1/2 - 1) - відстань між протилежними кутовими процесорами мережі. Передача інформації між двома процесами відбувається за O(P1/2) тактів - передача по рядкам та стовпчикам. Більш загальною моделлю є d-вимірна архітектура, діаметр якої дорівнює d*(P1/d-1), передача даних відбувається за O(d*P1/d) тактів. Ця модель широко використовується для розв'язку дифференційних рівнянь (звичайних чи в часткових похідних) та рівнянь математичної фізики.

Малюнок 3. Двовимірна архітектура Малюнок 4. Зірка з 9 процесів.

мережевого з'єднання для 16 процесорів.

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

Малюнок 5. Бінарне дерево розміру 15.

Бінарне дерево. Малюнок 5. Деревоподібна архітектура має найменший діаметр серед всіх існуючих, який дорівнює для бінарного дерева 2lg((P+1)/2) - відстань між двома листами, шлях між якими проходить через корінь. Для k-арних дерев діаметр зменшується зі збільшенням k. Недоліком деревоподібних мереж є те, що обмін даними між процесами відбувається за лінійний час, а процес-корінь є вузьким горлом при передачі інформації.

Багатопроцесорний комп'ютер з паралельною обробкою інформації називається деревовидною машиною (tree machine) [33], якщо його процесори сполучені зв'язками так, що утворюється топологія повного бінарного дерева. Такий комп'ютер має 2d-1 процесорних елементів для деякого d, які розбиті на d рівнів, пронумерованих від 1 до d. Кожний процесор на рівні j, 1ЈjЈd, зв'язаний з єдиним процесором на рівні j-1 (батьком), та з двома процесорами на рівні j+1 (синами). Зв'язки між процесами розташовані таким чином, що безпосередньо обмінюватися інформацією можуть лише батько з сином. Єдиний процесор на першому рівні називається коренем в топології дерева, а процесори на рівні d — листами. Корінь не має батька, а листи не мають синів. На малюнку 15 зображена топологія деревовидної машини з d=4 рівнями, яка містить 24-1 = 15 процесорних елементів.

Схема з'єднання в куб. Малюнок 6. Якщо d - вимірність гіперкуба, то він містить P=2d процесів. Передача даних відбувається за тактів. Кожен процесор сполучається з d сусідами. Діаметр кубічної мережі дорівнює точно logdP. Кожен процесор можна ідентифікувати d-вимірним вектором бітів. Тоді відстань між процесами можна визначити, коректуючи біти їх номерів. Щоб дістатися до протилежних процесорів треба скоректувати бітів - з 00...0 до 11...1.

Малюнок 6.Схема з'єднання в куб розміру 8.

Схема сумішно-обмінного з'єднання (shuffle - exchange). Малюнки 7а.7б. Ця архітектура мережі є однією з найкращих для паралельної обробки інформації: її діаметр приблизно дорівнює 2*lgP, кількість тактів для обміну між двома процесами - 4*lgP-3. Використовується вона в телефонних комунікаціях. Ця схема вирішує проблеми великого діаметра моделі та повільного часу обміну між двома процесами. Кожен процес з'єднується з іншими за правилом, яке визначає функція суміші для P=2*id процесорів:

s(i)= тоді s-1(i)=

Якщо номер процеса i представити у двійковому коді idid-1...i2i1, то функцію суміші можна подати в наступному вигляді:

s(idid-1...i2i1)=id-1id-2...i1id і s-1(idid-1...i2i1)=i1id...i3i2.

Визначивши функцію суміші, запишемо правило за яким з'єднуються процеси в сумішно-обмінній моделі. В ній кожен процес Pi має три сусіди: Pj, де j відрізняється від i останнім бітом у двійковому розкладі, P s(i) та P s-1(i).

Малюнок 7а. Логічна схема сумішного з'єднання.