Главная страница
Навигация по странице:

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

  • 3. Топология перекрестной коммутации (“кроссбар”)

  • 4. Коммутирующие элементы сетей с динамической топологией

  • 6. Топология «Омега»

  • 10. Топология двоичной n-кубической сети с косвенными связям

  • 11. Топология базовой линии

  • АВС Лекция 6. Тема. Динамические топологии смс


    НазваниеТема. Динамические топологии смс
    АнкорАВС Лекция 6.doc
    Дата04.05.2017
    Размер351 Kb.
    Формат файлаdoc
    Имя файлаАВС Лекция 6.doc
    ТипЛекция
    #1932

    Лекция 6.

    Тема. Динамические топологии СМС.

    План лекции:

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

    2. Шинная топология

    3. Топология перекрестной коммутации (“кроссбар”)

    4. Коммутирующие элементы сетей с динамической топологией

    5. Топология “Баньян”

    6. Топология “Омега”

    7. Топология “Дельта”

    8. Топология Бенеша

    9. Топология Клоша

    10. Топология двоичной n-кубической сети с косвенными связями

    11. Топология базовой линии


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

    Сеть называется двусторонней (two sided), если входы и выходы сети коммутирующих элементов разделены. При совмещенных входах и выходах сеть является односторонней (one-sided). Ключи в динамических СМС группируют- ся в ступени коммутации. В зависимости от их количества сети делятся на одноступенчатые и многоступенчатые. Наличие нескольких ступеней комму-тации позволяет обеспечить множественность путей между любыми парами входов и выходов.
    1. Блокирующие и неблокирующие многоуровневые сети
    Минимальным требованием к сети с коммутацией является поддержка соединения любого входа с любым выходом. Для этого в сети с n входами и n выходами система ключей обязана предоставить n! вариантов коммутации входов и выходов (перестановок – permutations). Проблема усложняется, когда сеть должна обеспечивать одновременную передачу данных между многими парами терминальных узлов (multicast), причем так, чтобы не возникали конфликты (блокировки) из-за передачи данных через одни и те же коммутирующие элементы в одно и то же время. Подобные топологии должны поддерживать nn перестановок. С этих позиций все топологии СМС с коммутацией делятся на три типа: неблокирующие, неблокирующие с реконфигурацией и блокирующие.

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

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

    В блокирующих сетях, если какое-либо соединение уже установлено, это может стать причиной невозможности установления других соединений. К блокирующим относятся сети «Баньян», «Омега», n-куб и др.
    2. Шинная топология
    Сети с шинной архитектурой – наиболее простой и дешевый вид дина- мических сетей. При одношинной топологии, показанной на рис. 6.1, а,все уз- лы имеют порядок 1 (d = 1) и подключены к одной совместно используемой шине. В каждый момент времени обмен сообщениями может вести только одна пара узлов, то есть на период передачи сообщения шину можно рассматривать как сеть, состоящую из двух узлов, в силу чего ее диаметр всегда равен 1 (D = 1). Ширина бисекции (В) также равна единице, поскольку топология до- пускает одновременную передачу только одного сообщения. Одношинная кон- фигурация полезна, когда число узлов невелико, то есть когда трафик шины мал по сравнению с ее пропускной способностью. Одношинная архитектура ис-пользуется для объединения нескольких узлов в группу (кластер), после чего из таких кластеров образуют сеть на базе других видов топологии.


    Рис. 6.1. Шинная топология: а – с одной шиной; б – со многими шинами
    Многошинная топология предполагает наличие n независимых шин и подключение узлов к каждой из этих шин (рис. 6.1, б), что позволяет вести одновременную пересылку сообщений между n парами узлов. Такая топология вполне пригодна для высокопроизводительных ВС. Диаметр сети по-прежнему равен 1, в то время как пропускная способность возрастает пропорционально числу шин. По сравнению с одношинной архитектурой управление сетью с несколькими шинами сложнее из-за необходимости предотвращения конфлик-тов, возникающих, когда в парах узлов, обменивающихся по разным шинам, присутствует общий узел. Кроме того, с увеличением порядка узлов сложнее становится их техническая реализация.

    3. Топология перекрестной коммутации (“кроссбар”)
    Топология перекрестной коммутации мультипроцессорной системы (cross-bar switch system) на основе матричного (координатного) коммутатора представ-ляет собой классический пример одноступенчатой динамической сети. Кроссбар n×m (рис. 6.2) представляет собой коммутатор, способный соединить nвходных и m выходных терминальных узлов с уровнем параллелизма, равным min(n, m). Главное достоинство рассматриваемой топологии состоит в том, что сеть полу-чается неблокирующей и обеспечивает меньшую задержку в передаче сообще-ний по сравнению с другими топологиями, поскольку любой путь содержит только один ключ. Тем не менее, из-за того, что число ключей в сети равно n×m, использование кроссбара в больших сетях становится непрактичным, хотя это достаточно хороший выбор для малых сетей. Для больших неблокирующих се- тей можно предложить иные топологии, требующие существенно меньшего ко-личества ключей.

    Рис. 6.2. Матричный коммутатор n × m
    В случае n=m имеем «полный кроссбар». Полный кроссбар на n входов и n выходов содержит n2ключей. Диаметр сети равен 1, ширина бисекции – n/2. Этот вариант часто используется в сетях с древовидной топологией для объеди-нения узлов нижнего уровня, роль которых играют небольшие группы (кластеры) процессоров и модулей памяти.

    Современные коммерчески доступные матричные коммутаторы способны соединять до 256 устройств. Топология используется для организации соедине-ний в некоторых серийно выпускаемых вычислительных системах, например в Fujitsu VPP 500 224 × 224.
    4. Коммутирующие элементы сетей с динамической топологией
    По типу коммутирующих элементов, применяемых в ступенях коммута- ции сетей с многоступенчатой топологией, различают:

    • сети на основе перекрестной коммутации;

    • сети на основе базового коммутирующего элемента.

    В сетях, относящихся к первой группе, в качестве базового коммутирую-щего элемента используется кроссбар m. Для второй категории роль комму-тирующего элемента играет «полный кроссбар» 2×2. Потенциально такой ком-мутатор управляется четырехразрядным двоичным кодом и обеспечивает 16 ва-риантов коммутации, из которых полезными можно считать 12. На практике обычно используются только четыре возможных состояния кроссбара 2×2, ко- торые определяются двухразрядным управляющим кодом (рис. 6.3). Подобный кроссбар называется базовым коммутирующим элементом (БКЭ) или β-элемен-



    Рис. 6.3. Состояния β-элемента
    том. Первые два состояния БКЭ являются основными: в них входная инфор- мация может транслироваться на выходы прямо либо перекрестно. Два следую-щих состояния предназначены для широковещательного режима, когда сообще-ние от одного узла одновременно транслируется на все подключенные к нему прочие узлы. Широковещательный режим используется редко. Сигналы на пе- реключение БКЭ в определенное состояние могут формироваться устройством управления сетью. В более сложном варианте БКЭ эти сигналы формируются внутри самого β-элемента, исходя из адресов пунктов назначения, содержащих- ся во входных сообщениях. Структура β-элемента показана на рис. 6.4.



    Рис. 6.4. Структура β-элемента
    Выбор в пользу того или иного варианта коммутации входных сообщений (пакетов) осуществляется схемой логики принятия решения β-элемента. Конкрет-ный вид коммутации реализуется сдвоенным мультиплексором, управляемым с выхода защелки, где хранится результат работы схемы логики принятия реше-ния. Элементы задержки обеспечивают синхронизацию процессов принятия ре-шения и пересылки пакетов с входов на выходы.

    Сложность β-элемента находится в зависимости от логики принятия ре- шения. В ряде архитектур БКЭ их состояние определяется только битом актив-ности пакета. В иных архитектурах используются адреса источника и получа- теля данных, хранящиеся в заголовке пакета, что может потребовать поддер- жания в БКЭ специальных таблиц. Тем не менее во всех своих вариантах β-элементы достаточно просты, что позволяет реализовать их на базе интеграль- ных микросхем.
    5. Топология “Баньян”
    Данный вид сети получил свое название из-за того, что его схема напо-минает воздушные корни дерева баньян (индийской смоковницы). В топологии «Баньян» между каждой входной и выходной линиями существует только один путь. Сеть n × n ( n = 2m ) состоит из mn/2 базовых коммутирующих элементов.

    Сеть «Баньян» 4×4 по топологии совпадает с сетью «Баттерфляй». На рис. 6.5 показана сеть «Баньян» 8×8. Передаваемый пакет в своем заголовке со-держит трехразрядный двоичный номер узла назначения. Данная сеть относится к сетям с самомаршрутизацией ( self-routing ), поскольку адрес пункта назна-



    Рис. 6.5. Топология типа «Баньян»
    чения не только определяет маршрут сообщения к нужному узлу, но и ис-пользуется для управления прохождением сообщения по этому маршруту. Каж-дый БКЭ, куда попадает пакет, просматривает один бит адреса и в зависимости от его значения направляет сообщение на выход 1 или 2. Состояние β-элемен- тов первой ступени сети (левый столбец БКЭ) определяется старшим битом ад-реса узла назначения. Средней ступенью (второй столбец) управляет средний бит адреса, а третьей ступенью (правый столбец) – младший бит. Если значение бита равно 0, то сообщение пропускается через верхний выход БКЭ, а при единичном значении – через нижний. На рисунке показан маршрут сообщения с входного узла 2 (0102) к выходному узлу 5 (1012). Адрес узла назначения содержится в заголовке сообщения.

    Топология «Баньян» весьма популярна из-за того, что коммутация обес-печивается простыми БКЭ, работающими с одинаковой скоростью, сообщения передаются параллельно. Кроме того, большие сети могут быть построены из стандартных модулей меньшего размера.
    6. Топология «Омега»



    Сеть с топологией «Омега» является подклассом «баньян»-сетей и пред-ставляет собой многоуровневую структуру, где смежные уровни связаны между собой согласно функции идеального тасования. Сеть n×n, где n=2m, состоит из mуровней БКЭ при общем числе БКЭ – mn/2. Количество соединений, обеспечи-ваемых сетью «Омега», равно nn/ 2, что гораздо меньше, чем n!, то есть топология «Омега» является блокирующей. Так, при n=8 процент комбинаций, возможных в сети «Омега», по отношению к потенциально допустимому числу комбина- ций составляет или 10,16%.



    Рис. 6.6. Сеть с топологией «Омега»
    Рассмотрим порядок установки β-элементов сети для соединения входно- го и выходного терминальных узлов, двоичное n-разрядное представление но-меров которых есть соответственно (anan-1a1) и (bnbn-1b1). Состояние, в кото-рое переключается БКЭ на i-ой ступени, определяется с помощью операции сложения по модулю 2 значений i-го бита в адресах входного и выходного терминальных узлов. Если , то БКЭ, расположенный на i-ой ступени сети, обеспечивает прямую связь входа с выходом, а при – перекрест-ное соединение. На рис. 6.6 показан процесс прохождения сообщения по сети «Омега» 8×8 от входного терминала 2 (0102) к выходному терминалу 6 (1102). Таким образом, если в сообщении присутствуют адреса источника и получате- ля сообщений, то сеть может функционировать в режиме самомаршрутизации.
    7. Топология «Дельта»
    Важный подкласс «баньян»-сетей образуют сети «Дельта», предложенные Пателом в 1981 году. В них основание системы счисления при адресации узлов для маршрутизации может отличаться от 2. Сеть соединяет anвходов с bn вы-ходами посредством n ступеней кроссбаров a×b (в сетях с такими топологиями, как «Омега», «базовая линия» и «косвенный» n-куб, используется двоичная сис-тема счисления, то есть a=2 и b=2 ). Адрес получателя задается в заголовке




    Рис. 6.7. Структура сети «Дельта»: а – по базе 4; б – с дополнительной ступенью
    сообщения числом в системе счисления с основанием b, а для прохождения со-общения по сети организуется самомаршрутизация. Каждая цифра адреса имеет значение в диапазоне от 0 до b–1 и выбирает один из b выходов коммутирую-щего элемента типа кроссбар a×b. Пример сети «Дельта» показан на рис. 6.7.

    В отличие от сети «Омега» входы не подвергаются тасованию. Это не влияет на алгоритм маршрутизации, поскольку важен не адрес источника, а ад- рес получателя. На рис. 6.7, а связь между ступенями соответствует идеальному тасованию – коммутаторы соединены так, что для связи любого входа с любым выходом образуется единственный путь, причем пути для любой пары равны по длине. В сеть «Дельта» могут быть введены и дополнительные ступени (рис. 6.7, б), чтобы обеспечить более чем один маршрут от входа к выходу.
    8. Топология Бенеша
    В топологии «Баньян» между каждым входным и выходным терминалом



    Рис. 6.8. Топология Бенеша: а – 4×4; б – 8×8
    существует только один путь. С добавлением к такой сети дополнительной

    ступени БКЭ число возможных маршрутов удваивается. Дополнительные пути позволяют изменять трафик сообщения с целью устранения конфликтов. При добавлении к сети «Баньян» (m–1)-го уровня, где n=2m, получаем топологию Бенеша (рис. 6.8). В сети Бенеша n×n число ступеней определяется выражени- ем 2m–1, а число БКЭ равно .

    Сеть Бенеша с n входами и n выходами имеет симметричную структуру, в каждой половине которой (верхней и нижней) между входными и выходными БКЭ расположена такая же сеть Бенеша, но с n/2 входами и n/2 выходами.

    Данная топология относится к типу неблокирующих сетей с реконфигу- рацией.
    9. Топология Клоша
    В 1953 году Клош показал, что многоступенчатая сеть на основе элемен- тов типа кроссбар, содержащая не менее трех ступеней, может обладать харак- теристиками неблокирующей сети.



    Рис. 6.9. Трехступенчатая сеть с топологией Клоша
    Сеть Клоша с тремя ступенями, показанная на рис. 6.9, содержит r1 кросс-баров во входной ступени, m кроссбаров в промежуточной ступени и r2 кросс-баров в выходной ступени. У каждого коммутатора входной ступени есть n1 входов и mвыходов – по одному выходу на каждый кроссбар промежуточной ступени. Коммутаторы промежуточной ступени имеют r1 входов по числу кросс-баров входной ступени и r2 выходов, что соответствует количеству переклю-чателей в выходной ступени сети. Выходная ступень сети строится из кросс- баров с m входами и n2 выходами. Таким образом, числа n1, n2, r1, r2 и m пол-ностью определяют сеть. Число входов сети N= r1n1, а выходов – M= r2n2.

    Связи внутри составного коммутатора организованы по следующим пра- вилам:

    • k-й выход i-го входного коммутатора соединен с i-м входом k-го проме- жуточного коммутатора;

    • k-й вход j-го выходного коммутатора соединен с j-м выходом k-го проме-жуточного коммутатора.

    Каждый модуль первой и третьей ступеней сети соединен с каждым мо-дулем второй ее ступени.

    Хотя в рассматриваемой топологии обеспечивается путь от любого входа к любому выходу, ответ на вопрос, будет ли сеть неблокирующей, зависит от числа промежуточных звеньев. Клош доказал, что подобная сеть является не-блокирующей, если количество кроссбаров в промежуточной ступени m удов-летворяет условию: m= n1+ n2 1. Если n1 = n2, то матричные переключатели в промежуточной ступени представляют собой «полный кроссбар» и критерий неблокируемости приобретает вид: m= 2n 1. При условии m= n2 сеть Клоша можно отнести к неблокирующим сетям с реконфигурацией. Во всех остальных случаях данная топология становится блокирующей.

    Вычислительные системы, в которых соединения реализованы согласно топологии Клоша, выпускают многие фирмы, в частности, Fujitsu (FETEX-150), Nippon Electric Company (АТОМ), Hitachi. Частный случай сети Клоша при n1 = r1 = r2 = n2 называется сетью «Мемфис». Топология «Мемфис» нашла приме-нение в вычислительной системе GF-11 фирмы IBM.
    10. Топология двоичной n-кубической сети с косвенными связям
    На рис. 6.10 показана косвенная двоичная n-кубическая сеть 8×8.



    Рис. 6.10. Топология двоичной n-кубической сети

    Здесь ступени коммутации связаны по топологии «Баттерфляй», а на по-следней ступени используется функция идеального тасования. Фактически сеть представляет собой обращенную матрицу сети «Омега». В этом можно убедить-ся, если соответствующим образом поменять местами БКЭ в каждом уровне сети «Омега», за исключением первого и последнего.
    11. Топология базовой линии
    Данный вид сети представляет собой многоступенчатую топологию, где в качестве коммутаторов служат β-элементы (рис. 6.11). Топология обеспечи- вает очень удобный алгоритм самомаршрутизации, в котором последователь- ные ступени коммутаторов управляются последовательными битами адреса по-лучателя. Каждая ступень сети на принципе базовой линии делит возможный диапазон маршрутов пополам. Старший бит адреса назначения управляет пер- вой ступенью. При нулевом значении этого бита сообщения с любого из вхо- дов поступят на вторую ступень сети с верхних выходов БКЭ первой ступени, то есть они смогут прийти только на верхнюю половину выходов с номерами 000 011, а при единичном значении бита – на нижнюю половину выходов с номерами 100 111. Второй бит адреса назначения управляет коммутаторами второй ступени, которая делит половину выходов, выбранную первой ступе- нью, также пополам. Процесс повторяется на последующих ступенях до тех пор, пока младший бит адреса назначения на последней ступени не выберет нужный выход сети. Таким образом, сеть на 8 входов требует наличия трех ступеней коммутации, сеть на 16 входов – 4 ступеней и т. д.


    Рис. 6.11 . Топология базовой линии
    Как видно из рисунка, сеть с топологией базовой линии совпадает с первыми m (n= 2m) уровнями сети Бенеша на n входов и n выходов. Если к последнему уровню этой сети добавить сеть с инверсной перестановкой битов, то получим так называемую R-сеть. Сеть с инверсной перестановкой битов имеет фиксированные связи входного терминала (amam-1a1) с выходным тер-миналом (a1a2am)и фактически представляет собой косвенную двоичную n-кубическую сеть.
    Контрольные вопросы


          1. Дайте сравнительную характеристику блокирующих и неблокирующих многоуровневых сетей.

          2. Проведите сравнительный анализ одношинной и многошинной топологий динамических сетей, акцентируя их сильные и слабые стороны.

          3. Сравните популярные разновидности «баньян»-сетей: «Омега», «Дельта». Можно ли причислить к этому классу сети Бенеша, и если можно, то почему?

          4. Дайте развернутое объяснение отличий топологии Клоша от «баньян»-сетей. Можно ли найти у них сходные черты, и если можно, то какие?

          5. С какой топологией сходна организация двоичной n-кубической сети с косвенными связями? Ответ обоснуйте, приведя конкретный пример.

          6. Охарактеризуйте смысл топологии на принципе базовой линии. Изобра- зите структуру соответствующей сети на 20 входов.






    написать администратору сайта