Новосибирский государственный университет

Факультет информационных технологий

ICT SBRAS
А.М.Федотов

Словарь терминов в коллекции "Вычислительные системы"

Древовидная топология

Синонимы: Древовидная топология; Дерево;

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

В древовидной топологии сеть строится по схеме так называемого строго двоичного дерева, где каждый узел более высокого уровня связан с двумя узлами следующего по порядку более низкого уровня. Узел, находящийся на более высоком уровне, принято называть родительским, а два подключенных к нему нижерасположенных узла - дочерними. В свою очередь, каждый дочерний узел выступает в качестве родительского для двух узлов следующего более низкого уровня. Каждый узел связан только с двумя дочерними и одним родительским.
Такую сеть можно охарактеризовать следующими параметрами: D = 2log2 [(N+1)/2]; d = 1 для краевых узлов, d = 2 для корневого узла и d = 3 для остальных узлов; I = N-1; В = 1. Диаметр для двоичного дерева возрастает пропорционально лишь логарифму числа узлов, в то время как степень узла остается постоянной. Сеть с такой топологией хорошо масштабируется. Основной недостаток топологии - малая ширина бисекции, что предполагает ограниченную полосу пропускания.
Топология двоичного дерева была использована в мультипроцессорной системе DADO из 1023 узлов, разработанной в Колумбийском университете.
При больших объемах пересылок между несмежными узлами древовидная топология оказывается недостаточно эффективной, поскольку сообщения должны проходить через один или несколько промежуточных звеньев. Очевидно, что на более высоких уровнях сети вероятность затора из-за недостаточно высокой пропускной способности линий связи выше. Этот недостаток устраняют с помощью топологии, называемой «толстым» деревом.
Идея «толстого» дерева состоит в увеличении пропускной способности коммуникационных линий на прикорневых уровнях сети. С этой целью на верхних уровнях сети родительские и дочерние узлы связывают не одним, а несколькими каналами, причем чем выше уровень, тем больше число каналов. На рисунке это отображено в виде множественных линий между узлами верхних уровней. Топология «толстого» дерева реализована в вычислительной системе СМ-5.

Литература

Основная:

  1. Цилькер Б.Я. Организация ЭВМ и систем : Учебник для вузов / Б.Я. Цилькер, С.А. Орлов. - 2-е изд. - СПб.: Питер, 2011. - 688 с. - ISBN 978-5-49807-862-5.

Ключевые термины (головные):  Статическая топология;   Размер сети;   Число связей;   Диаметр сети;   Степень узла;   Пропускная способность сети;   Задержка сети;   Связность сети;   Ширина бисекции сети;   Полоса бисекции сети;


Контекстный поиск: Задайте образец для поиска:

|Головная| |Преподавание| | Современные проблемы информатики| |Информатика| |Ключевые термины| |Персоны|

Федотов Анатолий Михайлович
[SBRAS]
НГУ
ФИТ НГУ
ИВТ СО РАН
© 1998-2018, Новосибирский государственный университет, Новосибирск
© 1998-2018, Институт вычислительных технологий СО РАН, Новосибирск
© 1998-2018, Федотов А.М.
    Дата последней модификации: 14.08.2013