Топология компьютерных сетей

Сети межсоединений можно сравнить с улицами города. Улицы похожи на ка­налы связи. Каждая улица может быть с односторонним и двусторонним движе­нием, она характеризуется определенной «скоростью передачи данных» (имеется в виду ограничение скорости движения) и имеет определенную ширину (число рядов). Перекрестки похожи на коммутаторы. На каждом перекрестке прибываю­щий пакет (пешеход или машина) выбирает, в какой выходной порт (улицу) по­ступить дальше в зависимости от того, каков конечный пункт назначения.

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

Топология [ 4 ]

Топология сети межсоединений определяет, как расположены каналы связи и ком­мутаторы (это, например, может быть кольцо или решетка). Топологии можно изображать в виде графов, в которых дуги соответствуют каналам связи, а узлы — коммутаторам (рис. 7.1). С каждым узлом в сети (или в соответствующем графе) связан определенный ряд каналов связи. Математики называют число каналов степенью узла, инженеры — коэффициентом разветвления. Чем больше степень, тем больше вариантов маршрута и тем выше отказоустойчивость. Если каждый узел содержит к дуг и соединение сделано правильно, то можно построить сеть межсоединений так, чтобы она оставалась полносвязной, даже если к-1 каналов повреждены.

Следующее свойство сети межсоединений — это ее диаметр. Если расстоянием между двумя узлами мы будем считать число дуг, которые нужно пройти, чтобы попасть из одного узла в другой, то диаметром графа будет расстояние между дву­мя узлами, которые расположены дальше всех друг от друга. Диаметр сети опреде­ляет самую большую задержку при передаче пакетов от одного процессора к дру­гому или от процессора к памяти, поскольку каждая пересылка через канал связи занимает определенное количество времени. Чем меньше диаметр, тем выше про­изводительность. Также имеет большое значение среднее расстояние между дву­мя узлами, поскольку от него зависит среднее время передачи пакета.

Еще одно важное свойство сети межсоединений — это ее пропускная способ­ность, то есть количество данных, которое она способна передавать в секунду. Очень важная характеристика — бисекционная пропускная способность. Чтобы вычислить это число, нужно мысленно разделить сеть межсоединений на две рав­ные (с точки зрения числа узлов) несвязанные части путем удаления ряда дуг из графа. Затем нужно вычислить общую пропускную способность дуг, которые мы удалили. Существует множество способов разделения сети межсоединений на две равные части. Бисекционная пропускная способность — минимальная из всех воз­можных. Предположим, что бисекционная пропускная способность составляет 800 бит/с. Тогда если между двумя частями много взаимодействий, то общую про­пускную способность в худшем случае можно сократить до 800 бит/с. По мнению многих разработчиков, бисекционыая пропускная способность — это самая важная характеристика сети межсоединений. Часто основная цель при разработке сети межсоединений — сделать бисекционную пропускную способность максимальной.

Рис. 7,1. [ 4 ] Различные топологии. Жирные точки соответствуют коммутаторам. Процессоры и модули памяти не показаны: звезда {а); полное межсоединение (full interconnect) (б); дерево (s); кольцо (г); решетка (д); двойной тор (е); куб (ж); гиперкуб (з)

Сети межсоединений можно характеризовать по их размерности. Размерность определяется по числу возможных вариантов перехода из исходного пункта в пункт назначения. Если выбора нет (то есть существует только один путь из каждого исходного пункта в каждый конечный пункт), то сеть нульмерная. Если есть два возможных варианта (например, если можно пойти либо направо, либо налево),

то сеть одномерна. Если есть две оси и пакет может направиться направо или налево либо вверх или вниз, то такая сеть двумерна и т. д.

На рис. 7.1 показано несколько топологий. Здесь изображены только кана­лы связи (это линии) и коммутаторы (это точки). Модули памяти и процессоры (они на рисунке не показаны) подсоединяются к коммутаторам через интерфей­сы. На рис. 7.1, а изображена нульмерная конфигурация звезда, где процессоры и модули памяти прикрепляются к внешним узлам, а переключение совершает центральный узел. Такая схема очень проста, но в большой системе центральный коммутатор будет главным критическим параметром, который ограничивает производительность системы. И с точки зрения отказоустойчивости это очень не­удачная разработка, поскольку одна ошибка в центральном коммутаторе может разрушить всю систему.

На рис. 7.1, б изображена другая нульмерная топология — полное межсоеди­нение (full interconnect). Здесь каждый узел непосредственно связан с каждым имеющимся узлом. В такой разработке пропускная способность между двумя сек­циями максимальна, диаметр минимален, а отказоустойчивость очень высока (даже при утрате шести каналов связи система все равно будет полностью взаимосвяза­на). Однако для к узлов требуется к(к-1)/2 каналов, а это совершенно неприемле­мо для больших значений к.

На рис. 7.1, в изображена третья нульмерная топология — дерево. Здесь основ­ная проблема состоит в том, что пропускная способность между секциями равна пропускной способности каналов. Обычно у верхушки дерева наблюдается очень большой поток обмена информации, поэтому верхние узлы становятся препятстви­ем для повышения производительности. Можно разрешить эту проблему, увели­чив пропускную способность верхних каналов. Например, самые нижние каналы будут иметь пропускную способность Ь, следующий уровень — пропускную способ­ность 2Ь, а каждый канал верхнего уровня — пропускную способность 4Ь. Такая схема называется толстым деревом (fat tree). Она применялась в коммерческих мультикомпыотерах Thinking Machines' CM-5.

Кольцо (рис. 7.1, г) — это одномерная топология, поскольку каждый отправ­ленный пакет может пойти направо или налево. Решетка или сетка (рис. 7.1, д) — это двумерная топология, которая применяется ао многих коммерческих систе­мах. Она отличается регулярностью и применима к системам большого размера, а диаметр составляет квадратный корень от числа узлов (то есть при расширении системы диаметр увеличивается незначительно). Двойной тор (рис. 7.1, е) явля­ется разновидностью решетки. Это решетка, у которой соединены края. Она ха­рактеризуется большей отказоустойчивостью и меньшим диаметром, чем обыч­ная решетка, поскольку теперь между двумя противоположными узлами всего два транзитных участка.

Куб (рис. 7.1, ж) — это правильная трехмерная топология. На рисунке изобра­жен куб 2x2x2, но в общем случае он может быть kxkxk. На рис. 7.1, з показан четырехмерный куб, полученный из двух трехмерных кубов, которые связаны меж­ду собой. Можно сделать пятимерный куб, соединив вместе 4 четырехмерных куба. Чтобы получить 6 измерений, нужно продублировать блок из 4 кубов и соединить соответствующие узлы и т. д.; п-мерный куб называется гиперкубом. Эта тополо­гия используется во многих компьютерах параллельного действия, поскольку ее диаметр находится в линейной зависимости от размерности. Другими словами, диаметр — это логарифм по основанию 2 от числа узлов, поэтому 10-мерный гиперкуб имеет 1024 узла, но диаметр равен всего 10, что дает очень незначитель­ные задержки при передаче данных. Отметим, что решетка 32x32, которая также содержит 1024 узла, имеет диаметр 62, что более чем в шесть раз превышает диа­метр гиперкуба. Однако чем меньше диаметр гиперкуба, тем больше разветвление и число каналов (и следовательно, тем выше стоимость). Тем не менее в системах с высокой производительностью чаще всего используется именно гиперкуб.

Коммутация [ 4 ]

Сеть межсоединений состоит из коммутаторов и проводов, соединяющих их. На рисунке 7.2 изображена небольшая сеть межсоединений с четырьмя

Рис. 7.2 [ 4 ] Сеть межсоединений в форме квадратной решетки с четырьмя коммутаторами (здесь показаны только два процессора).

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

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

Существует несколько стратегий переключения. Первая из них — коммутация каналов. Перед тем как послать пакет, весь путь от начального до конечного пунк­та резервируется заранее. Все порты и буферы затребованы заранее, поэтому ко­гда начинается процесс передачи, все необходимые ресурсы гарантированно до­ступны, и биты могут на полной скорости перемещаться от исходного пункта через все коммутаторы к пункту назначения. На рис. 7.2 показана коммутация каналов, где резервируются канал от процессора 1 к процессору 2 (черная жирная стрелка). Здесь резервируются три входных и три выходных порта.

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

Вторая стратегия — коммутация с промежуточным хранением. Здесь не тре­буется предварительного резервирования. Из исходного пункта посылается целый пакет к первому коммутатору, где он хранится целиком. На рис. 7.3, а исходным пунктом является процессор 1, а весь пакет, который направляется в процессор 2, сначала сохраняется внутри коммутатора А. Затем этот пакет перемещается в ком­мутатор С, как показано па рис. 7.3, б. Затем весь пакет целиком перемещается в коммутатор D (рис. 7.3, в). Наконец, пакет доходит до пункта назначения — до процессора 2. Отметим, что никакого предварительного

Рис. 7.3. [ 4 ] Коммутация с промежуточным хранением

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

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

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

И при буферизации на входе, и при буферизации на выходе с каждым портом связано определенное количество буферов. Если места недостаточно для хране­ния всех пакетов, то какие-то пакеты придется выбрасывать. Чтобы разрешить эту проблему, можно использовать общую буферизацию, при которой один буфер­ный пул динамически распределяется по портам по мере необходимости. Однако такая схема требует более сложного управления, чтобы следить за буферами, и позволяет одному занятому соединению захватить все буферы, оставив другие со­единения ни с чем. Кроме того, каждый коммутатор должен вмещать самый боль­шой пакет и даже несколько пакетов максимального размера, а для этого потребу­ется ужесточить требования к памяти и снизить максимальный размер пакета.

Хотя метод коммутации с промежуточным хранением гибок и эффективен, здесь возникает проблема возрастающей задержки при передаче данных по сети межсо­единений. Предположим, что время, необходимое для перемещения пакета по од­ному транзитному участку на рис. 7.3, занимает Т не. Чтобы переместить пакет из процессора 1 в процессор 2, нужно скопировать его 4 раза (в А, в С, в D и в процес­сор 2), и следующее копирование не может начаться, пока не закончится предыду­щее, поэтому задержка по сети составляет 4Т. Чтобы выйти из этой ситуации, нужно разработать гибридную сеть межсоединений, объединяющую в себе коммутацию каналов и коммутацию пакетов. Например, каждый пакет можно разделить на части. Как только первая часть поступила в коммутатор, ее можно сразу направить в следующий коммутатор, даже если оставшиеся части пакета еще не прибыли в этот коммутатор.

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

превратится в коммутацию с промежуточным хранением. При другом типе марш­рутизации, так называемой «wormhole routing» (червоточина), если первый блок не может двигаться дальше, в исходный пункт передается сигнал остановить пе­редачу, и пакет может оборваться, будучи растянутым на два и более коммутато­ров. Когда необходимые ресурсы становятся доступными, пакет может двигаться дальше.

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

Алгоритмы выбора маршрута [ 4 ]

В любой сети межсоединений с размерностью один и выше можно выбирать, по какому пути передавать пакеты от одного узла к другому. Часто существует мно­жество возможных маршрутов. Правило, определяющее, какую последовательность узлов должен пройти пакет при движении от исходного пункта к пункту назначе­ния, называется алгоритмом выбора маршрута.

Хорошие алгоритмы выбора маршрута необходимы, поскольку часто свобод­ными оказываются несколько путей. Хороший алгоритм поможет равномерно рас­пределить нагрузку по каналам связи, чтобы полностью использовать имеющую­ся в наличии пропускную способность. Кроме того, алгоритм выбора маршрута помогает избегать взаимоблокировки в сети межсоединений. Взаимоблокировка возникает в том случае, если при одновременной передаче нескольких пакетов ре­сурсы затребованы таким образом, что ни один из пакетов не может продвигаться дальше и все они блокируются навечно.

Пример тупиковой ситуации в сети с коммутацией каналов приведен на рис. 7.4. Тупиковая ситуация может возникать и в сети с пакетной коммутацией, но ее легче представить графически в сети с коммутацией каналов. Здесь каждый про­цессор пытается послать пакет процессору, находящемуся напротив него по диа­гонали. Каждый из них смог зарезервировать входной и выходной порты своего локального коммутатора, а также один входной порт следующего коммутатора, но он уже не может получить необходимый выходной порт на втором коммутаторе, поэтому он просто ждет, пока не освободится этот порт. Если все четыре процессо­ра начинают этот процесс одновременно, то все они блокируются и сеть зависает.

Алгоритмы выбора маршрута можно разделить на две категории: маршрутиза­ция от источника и распределенная маршрутизация. При маршрутизации от ис­точника источник определяет весь путь по сети заранее. Этот путь выражается списком из номеров портов, которые нужно будет использовать в каждом комму­таторе по пути к пункту назначения. Если путь проходит через к коммутаторов, то первые к байтов в каждом пакете будут содержать к номеров выходных портов, 1 байт на каждый порт. Когда пакет доходит до коммутатора, первый байт отсека­ется и используется для определения выходного порта. Оставшаяся часть пакета затем направляется в соответствующий порт. После каждого транзитного участка пакет становится на 1 байт короче, показывая новый номер порта, который нужно выбрать в следующий раз.

Рис. 7.4. [ 4 ] Тупиковая ситуация в сети с коммутацией каналов

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

Популярным алгоритмом маршрутизации, который применяется для прямо­угольных решеток с любым числом измерений и в котором никогда не возникает тупиковых ситуаций, является пространственная маршрутизация. В соответствии с этим алгоритмом пакет сначала перемещается вдоль оси х до нужной координа­ты, а затем вдоль оси у до нужной координаты и т. д. (в зависимости от количества измерений). Например, чтобы перейти из (3, 7,5) в (6,9,8), пакет сначала должен переместиться из точки х=3 в точку х=6 через (4, 7, 5), (5,7,5) и (6,7, 5). Затем он должен переместиться по оси у через (6,8, 5) и (6,9, 5). Наконец, он должен пере­меститься по оси z в (6, 9, 6), (6, 9, 7) и (6, 9, 8). Такой алгоритм предотвращает тупиковые ситуации.

Коммерческие сети межсоединений [ 4 ]

В этом разделе мы рассмотрим некоторые технологии связи. Наш первый пример — система Ethernet. Существует три версии этой системы: classic Ethernet, fast карта Ethernet

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

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

Третья разработка — Ethernet с использованием коммутаторов. Здесь сетевой концентратор заменен устройством, содержащим высо­коскоростную плату backplane, к которой можно подсоединять канальные карты. Каждая канальная карта принимает одну или несколько сетей Ethernet, и разные карты могут воспринимать разные скорости, поэтому classic, fast и gigabit Ethernet могут быть связаны вместе.

Когда пакет поступает в канальную карту, он временно сохраняется там в буфе­ре, пока канальная карта не отправит запрос и не получит доступ к плате backplane, которая функционирует почти как шина. Если пакет был перемещен в канальную карту, к которой подсоединена целевая машина, он может направляться к этой машине. Если каждая канальная карта содержит только один Ethernet и этот Ethernet имеет только одну машину, конфликтных ситуаций больше не возник­нет, хотя пакет может быть потерян из-за переполнения буфера в канальной карте. Gigabit Ethernet с использованием коммутаторов с одной машиной на Ethernet и высокоскоростной платой backplane имеет потенциальную производительность (по крайней мере, это касается пропускной способности) в 4 раза меньше, чем каналы связи в машине ТЗЕ, но стоит значительно дешевле.

Но при большом количестве канальных карт обычная плата backplane не смо­жет справляться с такой нагрузкой, поэтому необходимо подсоединить несколько машин к каждой сети Ethernet, вследствие чего опять возникнут конфликтные ситуации. Однако с точки зрения соотношения цены и производительности сеть на основе gigabit Ethernet с использованием коммутаторов — серьезный конку­рент на компьютерном рынке.

Следующая технология связи, которую мы рассмотрим, — это ATM (Asynch­ronous Transfer Mode — асинхронный режим передачи). Технология ATM была разработана международным консорциумом телефонных компаний в качестве за­мены существующей телефонной системы на новую, полностью цифровую. Ос­новная идея проекта состояла в том, чтобы каждый телефон и каждый компьютер в мире связать с помощью безошибочного цифрового битового капала со скорос­тью передачи данных 155 Мбит/с (позднее 622 Мбит/с). Но осуществить это на практике оказалось не так просто. Тем не менее многие компании сейчас выпуска­ют съемные платы для персональных компьютеров со скоростью передачи данных 155 Мбит/с или 622 Мбит/с. Вторая скорость, ОС-12, хорошо подходит для муль-тикомиьютеров.

Провод или стекловолокно, отходящее от платы ATM, переходит в переключа­тель ATM — устройство, похожее на коммутатор Ethernet. В него тоже поступают пакеты и сохраняются в буфере в канальных картах, а затем поступают в исходя­щую канальную карту для передачи в пункт назначения. Однако у Ethernet и ATM есть существенные различия.

Во-первых, поскольку ATM была разработана для замещения телефонной сис­темы, она представляет собой сеть с маршрутизацией информации. Перед отправ­кой пакета в пункт назначения исходная машина должна установить виртуальную цепь от исходного пункта через один или несколько коммутаторов ATM в конечный пункт. На рис. 7.5. показаны две виртуальные цепи. В сети Ethernet, напротив, нет никаких виртуальных цепей. Поскольку установка виртуальной цепи занимает некоторое количество времени, каждая машина в мультикомпьютере должна уста­навливать виртуальную цепь со всеми другими машинами при запуске и использо­вать их при работе. Пакеты, отправленные по виртуальной цепи, всегда будут дос­тавлены в правильном порядке, но буферы канальных карт могут переполняться, как и в сети Ethernet с коммутаторами, поэтому доставка не гарантируется.

Рис. 7.5. [ 4 ] 16 процессоров, связанных четырьмя переключателями ATM. (Пунктиром показаны две виртуальные цепи (канала))

Во-вторых, Ethernet может передавать целые пакеты (до 1500 байтов данных) одним блоком. В ATM все пакеты разбиваются на ячейки по 53 байта. Пять из этих байтов — это поля заголовка, которые сообщают, какой виртуальной цепи принадлежит ячейка, что это за ячейка, каков ее приоритет, а также некоторые другие сведения. Полезная нагрузка составляет 48 байтов. Разбиение пакетов на ячейки и их компоновку в конце пути совершает аппаратное обеспечение.

Наш третий пример — сеть Myrinet — съемная плата, которая производится одной калифорнийской компанией и пользуется популярностью у разработчиков систем COW [18]. Здесь используется та же модель, что и в Ethernet и ATM, где каждая съемная плата подсоединяется к коммутатору, а коммутаторы могут со­единяться в любой топологии. Каналы связи сети Myrinet дуплексные, они пере­дают информацию со скоростью 1,28 Гбит/с в обоих направлениях. Размер паке­тов неограничен, а каждый коммутатор представляет собой полное пересечение, что дает малое время ожидания и высокую пропускную способность.

Myrinet пользуется популярностью у разработчиков систем COW, поскольку платы в этой сети содержат программируемый процессор и большое ОЗУ. Хотя Myrinet появилась со своей стандартной операционной системой, многие иссле­довательские группы уже разработали свои собственные операционные систе­мы. У них появились дополнительные функции и повысилась производительность. Из типичных особенностей можно назвать защиту, управление потоком, надежное широковещание и мультивещание, а также возмож­ность запускать часть кода прикладной программы на плате.

Не нашли, что искали? Воспользуйтесь поиском: