Топология k-ичного п-куба

Название топологии означает, что в ней реализуется куб, имеющий и измерений, причем каждое измерение содержит k узлов (N =kn) Каждому узлу назначен n-разрядный номер в системе счисления с основанием к, и он связан с узлом, номер которого отличается только в одной цифре и только на единицу. k-ичный n-куб может быть построен путем объединения к экземпляров k-ичных (n - 1) кубов в кольцо.

Многие ранее рассмотренные топологии представляют собой варианты топологии k-ичного n-куба:

- k-ичный 1-куб- кольцо;

- k-ичный 2-куб - двумерный тор;

- k-ичный 3-куб - трехмерный тор;

- 4-ичный 2-куб - плоская решетка 4x4;

- 2-ичный n-куб - гиперкуб.

Доказано, что эффективность топологии, а также ее масштабируемость улучшаются с ростом значения к и уменьшением количества измерений п.

Динамические топологии

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

Если входы и выходы сети коммутирующих элементов разделены, сеть называют двусторонней (two-sided). При совмещенных входах и выходах сеть является односторонней (one-sided).

Обычно ключи в динамических CMC группируются в так называемые ступени коммутации. В зависимости от того, сколько ступеней коммутации содержит сеть, она может быть одноступенчатой или многоступенчатой. Наличие более чем одной ступени коммутации позволяет обеспечить множественность путей между любыми парами входов и выходов.

Блокирующие и неблокирующие многоуровневые сети

Минимальным требованием к сети с коммутацией является поддержка соединения любого входа с любым выходом. Для этого в сети с п входами и п выходами система ключей обязана предоставить п \ вариантов коммутации входов и выходов

(перестановок - permutations). Проблема усложняется, когда сеть должна обеспечивать одновременную передачу данных между многими парами терминальных узлов (multicast), причем так, чтобы не возникали конфликты (блокировки) из-за передачи данных через одни и те же коммутирующие элементы в одно и то же время. Подобные топологии должны поддерживать n" перестановок. С этих позиций все топологии CMC с коммутацией разделяются на три типа: неблокирующие, неблокирующие с реконфигурацией и блокирующие.

В неблокирующих сетях обеспечивается соединение между любыми парами входных и выходных терминалов без перенастройки коммутирующих элементов сети, В рамках этой группы различают сети строго неблокирующие (strictly non-blocking) и неблокирующие в широком смысле (wide sense non-blocking), В строго неблокирующих сетях возникновение блокировок принципиально невозможно в силу примененной топологии. К таким относятся матричная сеть и сеть Клоша. Неблокирующими в широком смысле называют топологии, в которых конфликты при любых соединениях не возникают только при соблюдении определенного алгоритма маршрутизации.

В неблокирующих сетях с реконфигурацией также возможна реализация соединения между произвольными входными и выходными терминалами, но для этого необходимо изменить настройку коммутаторов сети и маршрут связи между соединенными терминалами. Примерами таких сетей служат сети Бенеша, Бэтчера, «Мемфис» и др.

В блокирующих сетях, если какое-либо соединение уже установлено, это может стать причиной невозможности установления других соединений. К блокирующим относятся сети «Баньяна, «Омега», n-куб и др.