Малюнок 7б. Модель комп'ютера сумішно-обмінного з'єднання розміру 8.
Малюнок 8. Модель комп'ютера сумішно-зсувного з'єднання розміру 8
Схема з'єднання метеликом [5] (butterfly network). Малюнок 9а. Метелик з N входами подається графом з рівнів, кожен з яких містить N вершин. j-та вершина на i-ому рівні позначається j1j2...jlogN,i, де j1j2...jlogN - бінарне подання числа j і вона з'єднується з вершинами j1j2...jlogN,i+1 та j1j2...jiji+2...jlogN,i+1 на рівні i+1. На нульовому рівні розташовані вхідні вершини, на рівні logN — вершини виходу. Шлях, який проходять дані з будь-якого входу на будь-який вихід визначається однозначно за номером виходу і його довжина дорівнює . З будь-якої вершини виходять дві дуги: нагору(0) та вниз(1). Наприклад, якщо виходом буде вершина 101, то з якого б входу ми не пішли, підемо вниз, вгору, вниз і обов'язково потрапимо у вихід 101. На малюнку 9б зображена схема метелика з випадковим з'єднанням вершин першого рівня. Його зв'язки повністю співпадають зі зв'язками стандартного метелика окрім першого рівня. З кожної вершини першого рівня виходить дві дуги в будь-які вершини другого рівня, одна з останніх повинна знаходитися в верхній половині, друга - в нижній.
Малюнок 9а. Схема з'єднання Малюнок 9б. Метелик з випадковим
метеликом для 32 процесів. з'єднанням першого рівня.
Схема метелика належить до великого класа розчеплених багатостанових мереж (splitter multistage interconnection networks). Перемикачі на кожному рівні розчепленої мережі можна розбити на блоки. Всі перемикачі рівня 0 належать одному блоку. На рівні 1 існує два блоки - один складається з верхніх N/2 прцесів, другий - з нижніх N/2 процесів. Взагалі, на рівні кількість блоків дорівнює 2i, розмір кожного з яких дорівнює N/2i. Кожний блок на рівні i з'єднується з двома блоками на рівні i+1 - Bhigh та Blow, відповідно верхній та нижній блоки. Розгалуження блоку на два і називається розчепленням. Розчеплена мережа має складність d, якщо будь-яка вершина, яка не є вхідною, має 2d вхідних ребер, а з будь-якої вершини, яка не є виходом, виходить d верхніх та d нижніх ребер. Схеми метелика,які наведено на малюнках 9а та 9б, є розчепленими мережами складності 1. В розчеплених мережах існує лише один шлях між вхідною та вихідною вершиною.
Мережа вулиць Манхетена [31] (Manhattan Street Network) (Малюнок 10) є двовимірна прямокутна мережа безпосереднього з'єднання, яка складається з N=m*n процесів, кожен з яких має ідентифікаційний номер (a,b), де 0ЈaЈm-1, 0ЈbЈn-1. Вершина (a,b) сполучається зв'язками з вершинами (x,b) та (a,y) наступним чином: (x,b) = {(a+/-1) mod m, b}, +/- коли b парне/непарне та (a,y)={a, (b+/-1) mod n}, +/- коли a парне/непарне. Напрямок з'єднань цієї мережі співпадає з напрямком руху по вулицям Манхетена. Діаметр мережі дорівнює N1/2+1, середня довжина шляхів між двома вершинами — (N3/2/2+N-4)/(N-1) [31].
HR4-мережа [34], або торовидна мережа, виглядає як і мережа вулиць Манхетена за винятком того, що її зв'язки двонаправлені. Її діаметр дорівнює N1/2, середня довжина шляхів — N3/2/(2*N-2) [31].
Малюнок 10. Мережа вулиць Манхетена розміру 4*4.
Малюнок 11а. Незгорнута Малюнок 11б. Згорнута
шестикутна мережа розміру 3. шестикутна мережа розміру 3.
Зірчатий граф. Мережа, топологією якої є зірчатий граф, представлена у [35] і зображена на малюнку 12. Ця топологія є однією з найпривабливіших при розробці архітектур симетричних мереж завдяки невеликому діаметру, малій степені вершин, симетрії, та великій надійності при передачі даних. Основними напрямками робіт є вивчення топологічних властивостей зірчатого графу, питань надійності та стійкості до відмов, розробка алгоритмів [35].
Малюнок 12. Зірчатий граф S4.
Зірчатий граф розміру n, який позначається Sn, представляє собою симетричний граф степеню n-1, який має n! вершин. Кожна вершина має свій власний ідентифікаційний номер, який представляється кортежем з n елементів — перестановкою множини {1,2,...,n}. Дві вершини з'єднані зв'язком i, якщо номер однієї вершини можна буде отримати з номера другої вершини перестановкою першої (лівої) та i-тої цифри, де 1<iЈn.
Гама мережа [38] розміру N=2n складається з n+1 станів, кожний стан має N перемикачів. Кожний перемикач в проміжному стані має тип 3*3, в першому стані — 1*3, в останньому — 3*1. N входів та N виходів занумеровані від 0 до N-1 як показано на малюнку. Стани занумеровані від 0 до n зліва направо. j-ий перемикач стану k з'єднується з трьома перемикачами стану k+1 відповідно до функцій: fBk(j) = j + 2k(modN), fUk(j) = j - 2k(modN), fSk(j) = j. Ці функції визначають відповідно нижній, верхній та прямий зв'язок. Гама мережа розміру 8 подана на малюнку 13.
Омега мережа [39] розміру N=2m або N*N складається з m=log2N однакових станів і має N входів та виходів. Кожний стан містить N/2 перемикачів типу 2*2. Кожний зв'язок має свій номер, який подається у двійковому коді. На малюнку 4 зображено омега мережу розміру 8*8.
Шлях між довільними входом та виходом може бути поданий парою (s,d) де s=s0s1...sm-1 — двійкова адреса входу, d=d0d1...dm-1 — двійкова адреса виходу. Шлях однозначно визначається послідовністю s0s1...sm-1d0d1...dm-1, яку будемо називати кодом шляху. m-бітовим вікном Wi в позиції i будемо називати послідовність з m бітів яка починається з i-ої позиції в коді шляху. Тоді вікно Wi визначає шлях повідомлення що передається на i-ому стані. Наприклад для передачі інформаційного пакету з 100 в 011 код шдяху буде 100011, вікна: W0=100, W1=000, W2=001, W3=011.
Малюнок 13. Гама мережа розміру 8.
Малюнок 14. Омега мережа.
2.2 Вибір топології мережі
На практиці найпоширенішого використання дістали комп’ютерни мережі, які будуються на основі топологій типу шина, зірка та кільце. Це пов’язано зтим, що при реалізації мереж в офісах та на підприємствах вимоги до продуктивності, надійності та захищеності цих структур суттєво відрізняються від вимог до мереж військового або наукового профілю. В доданку 3 приведено порівняльний аналіз декількох найпоширеніших топологій стосовно реалізації автоматизованої системи керування озброєнням військового корабля. А нижче буде розглянуто властивості трьох основних типів топологій а також можливості їх фізичної реалізації.
При використанні шинної топології (доданок 1) всі комп’ютери під’єднуються до одного загального кабеля, на кінцях якого встановлюються кінцеві резистори (термінатори). У випадку, коли один з під’єднаних комп’ютерів не працює, це загалом не впливає на роботу мережі; у випадку, коли порушується цілістність кабеля або з’єднувального пристрою на будь-якій ділянці мережі, то вся мережа стає працювати. В зв’язку з тим, що тут використовується один загальний кабель, мережні методи взаємодії пропонують розподілену (Shared) в одному часовому проміжку обробку всіх запитів на з’єднання та передачу інформації від всіх комп’ютерів. В ситуації, коли кількість під’єднаних до мережі машин збільшується, час обробки кожного запиту збільшується, а сумарна продуктивність мережі сильно зменшується.
В топології типу зірка кожний комп’ютер під’єднується до особливого пристрою, що називається концентратор (hab), який розмножує та передає сигнал по всіх під’єднаних до нього кабелях. Аналогічно до шинної топології, цей варіант схильний до зменшення продуктивності при збільшенні кількості комп’ютерів в мережі.
Для збільшення продуктивності мережі та підтримки постійної швидкості обміну для всіх з’єднань водночас замість концентратора треба використовувати комутатор(Switch), який організовує віртуальні канали для кожного з’єднання між вузлами мережі. В цій топології несправність в одному з кабелів призведе до припинення роботи лише одного комп’ютера, але не всієї мережі. При відмові концентратора або комутатора всі під’єднані до нього комп’ютери будуть від’єднані від мережі.
В кільцевій топології всі комп’ютери з’єднано замкненим в кільце кабелем. Комп’ютер, що «бажає» передати інформацію, посилає спеціальний маркер із своїми данними. В цьому маркері також міститься адреса відправника та одержувача. Комп’ютер-одержувач, прочитавши його, посилає цей же маркер назад, щоб підтвердити одержання, а відправник , в свою чергу, одержує його і передає наступному в кільці комп’ютеру, щоб і він мав можливість передати свої данні. Такий метод взаємодії визначає більш низький темп зменшення сумарної продуктивності мережі порівняно з шинною топологією, але при несправності в будь-якій ділянці кабеля вся мережа перестає функціонувати.