12.9.5.4. Багатоярусні блокуючі комутуючі мереж

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

Існує цілий ряд багатоярусних комутуючих комунікаційних мереж. Структура ши­роко розповсюджених топологій мереж "Баньян" та "Омега" для N=8 показана відпо­відно на рис. 12.38 а та на рис. 12.38 B. Вона містить в кожному з log₂Nярусів по N/2КЕ і N каналів зв'язку. Якщо кожен КЕ виконує перемикання прямо і навхрест, то така комунікаційна мережа може виконати 2^N/2IogNперестановок, що істотно менше за N!пе­рестановок, можливих в неблокуючій мережі. Проте ті перестановки, які вона виконує, є найбільш використовуваними в багатопроцесорних системах. Потрібно відзначити, що в даній КММ є можливість її розділення на комунікаційні мережі меншого розміру шляхом включення на передачу прямо КЕ в тих ярусах, що стоять перед цими комуніка­ційними мережами.

460

У топології "Баньян" (рис. 12.38 а) між кожним входом і виходом існує лише один шлях. Мережа NxN(N= 2^m)складається з Nm/2комутуючих елементів. Для керування мережею пакет, що передається, містить в своєму заголовку трирозрядний двійковий но­мер вузла призначення. Дана мережа належить до мереж з самомаршрутизацією, оскіль­ки адреса пункту призначення не тільки визначає маршрут повідомлення до потрібно­го вузла, але і використовується для керування проходженням повідомлення по цьому маршруту. Кожен КЕ, до якого потрапляє пакет, проглядає один біт адреси і, залежно від його значення, направляє повідомлення на вихід 1 або 2. Стан КЕ першого ярусу мережі (лівий стовпець КЕ) визначається старшим бітом адреси вузла призначення. Середнім ярусом (другий стовпець) управляє середній біт адреси, а третім ярусом (правий стов­пець) - молодший біт. Якщо значення біта рівне 0, то повідомлення пропускається через верхній вихід КЕ, а при одиничному значенні - через нижній. На рисунку показаний маршрут повідомлення з вхідного вузла 2 (010) до вихідного вузла 5 (101).

Топологія "Омега" є підкласом топології "Баньян". Ці топології досить популярні че­рез те, що комутація забезпечується простими КЕ, що працюють з однаковою швид­кістю, а повідомлення передаються паралельно. Крім того, великі мережі можуть бути побудовані з мереж меншого розміру.