Software & Systems

Современная распределенная вычислительная система кластерного типа имеет в своем составе от десятков до тысяч узлов ЭВМ. Связь между узлами в таких системах осуществляется через модули коммутаторов, которые строятся на базе микросхем контроллеров коммутаторов. Каждая такая микросхема имеет, как правило, не более 16 портов. Для создания систем больших размеров коммутаторы необходимо объединять друг с другом, то есть масштабировать. Масштабирование может осуществляться через специальный канал, обычный порт коммутатора либо через группу физических портов, объединенных в логический порт. При группировке портов образуется канал с пропускной способностью, равной суммарной пропускной способности объединенных портов. Такие групповые соединения называются транковыми. Транковое соединение повышает суммарную пропускную способность канала для совокупности пакетов, каждый же отдельный кадр передается по отдельному физическому сетевому порту с производительностью, характеризующей этот порт. Так, для транкового соединения из четырех портов с пропускной способностью 100 Мбит/сек. каждый суммарная пропускная способность соединения равна 400 Мбит/сек., но каждый кадр передается по порту с пропускной способностью 100 Мбит/сек.

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

Масштабируемые, или стековые, коммутаторы могут объединяться друг с другом через канал, ра- ботающий по принципу шины, кольца, либо через специальную дополнительную внешнюю коммутирующую матрицу.

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

Наиболее производительным является соединение через дополнительную внешнюю коммутирующую матрицу. Однако при этом увеличивается количество используемых устройств, что ведет к повышению стоимости разработки системы и снижению ее надежности. Кроме того, производительность падает при многочисленных групповых и широковещательных пересылках, так как каждая такая пересылка блокирует остальные порты матрицы. Еще одним недостатком является неэффективность использования коммутационной матрицы при передаче кадров между портами разной производительности. Например, при передаче трафика между портами с 10 Мбит/сек. на 1000 Мбит/сек. канал коммутационной матрицы будет работать на 10 Мбит/сек., даже если он способен функционировать на 1 Гбит/сек. и выше.

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

Кольцевая архитектура используется, например, в коммуникационных устройствах фирмы Allayer. Архитектура Allayer Rox Bus Architecture [1] позволяет объединять до четырех устройств в кольцо, пропускная способность каждого соединения составляет 2,4 Гбит/сек. (магистраль данных 32-го разряда, работающая на частоте 75 МГц). Канал занимает 51 сигнальную линию в каждом направлении, в сумме 102 сигнальные линии на каждое устройство.

Недостатки кольцевой архитектуры Allayer Rox Bus Architecture в невысокой масштабируемости (она может объединять не более четырех устройств), в большом количестве сигнальных линий, необходимых для создания соединения, в невозможности создавать резервные соединения, которые позволяли бы изолировать разрывы в кольце, а также в невозможности реконфигурировать кольцо, добавлять или удалять устройства из кольца в уже собранной системе.

В предлагаемой микросхеме контроллера коммутатора 1890КП1Я разработан высокопроизводительный канал расширения, позволяющий объединять коммутаторы в кольцевую архитектуру. Канал обладает пропускной способностью 1,6 Гбит/сек. (магистраль данных 32-го разряда, работающая на частоте 50 МГц), занимает 34 сигнальные линии и позволяет объединять в кольцо до 15 устройств. Канал расширения реализует протокол многомаркерного доступа к кольцу. Преимущества использования этого метода в возможности одновременного ведения независимых передач по кольцу и эффективном использовании каналов кольца даже при передаче кадров между портами с разной пропускной способностью.

Основным способом управления доступом к среде в коммуникационных средах, имеющих топологию кольца, является передача доступа при помощи маркера [2]. Лишь одной станции в кольце разрешается осуществлять передачу в один момент времени. Право на захват среды передается от станции к станции при помощи маркера. Управление потоком осуществляется за счет анализа времени обращения маркера по кольцу и введения системы приоритетных передач. Маркерный метод доступа используется, например, в сетях Token Ring [3] и FDDI [4].

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

Предлагаемый протокол доступа к среде с кольцевой топологией является модификацией маркерного метода доступа. Отличие предлагаемого метода от обычного маркерного доступа, используемого, например, в сетях Token Ring и FDDI, заключается в том, что захватывается не среда, а целевые узлы в ней. Захват целевых узлов осуществляется через захват их маркеров, циркулирующих по кольцу (рис. 1). В среде также могут одновременно проходить потоки через один и тот же сегмент. Различные потоки не перемешиваются за счет введения адресной части, которая сопровождает каждый неделимый блок потоков. Введение адресной части вносит постоянную избыточность в циркулирующий по кольцу трафик, введение маркеров узлов – динамическую избыточность в трафик, меняющуюся со временем.

Рис. 1. Принцип многомаркерного метода доступа (M – станции, Мр – маркеры станции

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

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

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

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

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

Между станцией-передатчиком и станцией-приемником управление потоком осуществляется через передачу команд STOP и GO.

В конце передачи передающая станция добавляет контрольный код CRC (Cycling Redundancy Code – циклический избыточный код) для проверки правильности кадра. При обнаружении ошибки или принятии команды отмены передачи принятый кадр уничтожается в приемной станции.

Если кольцо вырождено и две станции объединены по принципу точка–точка, протокол может быть облегчен и маркеры могут не передаваться. О том, что кольцо вырождено, станции узнают на этапе инициализации.

Методика оценки эффективности использования среды

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

Рис. 2. Иллюстрация к определению коэффициента эффективности использования среды

Выведем формулу оценки коэффициента эффективности использования среды для нашего случая. Введем обозначения: S – множество узлов кольца, размерность N; Q – множество сегментов кольца, размерность N; A – множество занятых целевых узлов кольца, размерность M; F – множество потоков в кольце, размерность M; H – матрица принадлежности сегментов из Q потокам из F, размерность N´M; , для любого j элементы hij связаны условием непрерывности потоков:  ; V – множество скоростей потоков v(fi), ; N – количество узлов в кольце; M – текущее количество потоков в кольце; сном – номинальная пропускная способность сегмента; kпост – коэффициент учета постоянной адресной избыточности; ρ – время распространения маркера между двумя соседними сегментами; – время удержания m-м узлом своего маркера; hip – элементы матрицы принадлежности i-го сегмента p-му потоку.

Коэффициент эффективности использования среды можно определить как отношение суммы скоростей потоков, проходящих через кольцо, к максимально возможной сумме скоростей того же числа потоков, проходящих через кольцо:

.

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

Скорость потока можно определить как

,

где kпост – коэффициент, учитывающий постоянную адресную избыточность; kдин – коэффициент, учитывающий динамическую избыточность за счет циркуляции маркеров по кольцу; kcross(fi) – коэффициент, учитывающий взаимные пересечения потоков; cном – номинальная пропускная способность сегмента кольца.

Коэффициент kдин определяется как

,

где  – длительность прохождения m-го маркера через сегмент кольца, равная ;  – период обращения m-го маркера по кольцу.

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

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

.

В результате для коэффициента оценки эффективности использования среды имеем:

.

Рис. 3. Зависимость длительности удержания маркера от времени

Рис. 4. Зависимость коэффициента динамической избыточности от времени

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

На рисунке 3 показана зависимость длительности удержания станцией маркера от времени. На рисунке 4 – зависимость коэффициента учета динамической избыточности от времени. Из графика следует, что, благодаря предложенному механизму понижения избыточности путем удержания маркеров, коэффициент учета динамической избыточности довольно быстро растет и уже через несколько оборотов маркера по кольцу приближается к единице; для больших размеров пакетов им можно пренебречь.

На рисунке 5 приведены значения коэффициента эффективности для различных расположений потоков в кольце с количеством узлов 15. Запись l´q означает, что в кольце l потоков пересекаются максимум с q потоками на одном сегменте. Сплошное заполнение у столбцов показывает эффективность использования среды при одномаркерном методе для тех же количеств потоков (рассчитано с учетом отсутствия адресной избыточности). Видно, что предложенная технология уступает одномаркерной только в случаях, близких к наихудшим взаимным расположениям потоков, когда все потоки в кольце пересекаются. Для кольца с 15 узлами и адресной избыточностью в 25 % максимальная суммарная пропускная способность, достигаемая на данной технологии, превосходит одномаркерную в 11 раз.

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

Преимущества представленной сетевой технологии заключаются в следующем.

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

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

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

Высокая пропускная способность. Представленная технология за счет более полного использования передающей среды обладает высокой пропускной способностью. К примеру, пиковая пропускная способность сети из 10 станций равна 16 Гбит/сек., тогда как для одномаркерного метода эта величина равна 1,8 Гбит/сек.

Рис. 5. Зависимость эффективности использования среды от структуры потоков в кольце

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

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

Метод создания отказоустойчивых колец

Кольцо является критическим ресурсом, отказ которого может привести к выходу из строя всего сегмента, построенного на нем.

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

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

Данный метод заключается в дублировании входных линий. Контроллер канала кольцевого соединения имеет два набора входных линий – основной и резервный. Между соседними устройствами по каналу периодически передаются сигналы целостности канала. В нормальном состоянии контроллер работает по основному набору входных линий. Если детектируется нарушение целостности канала, контроллер переключается на резервный набор входных линий. Таким образом реализуется механизм обнаружения и изолирования сбойных участков в кольце. В зависимости от топологии размещения входных и резервных соединений такой метод позволяет детектировать и изолировать максимальное количество сбойных участков, достигающее половины числа узлов в кольце (рис. 6). При этом за счет того, что дублируется только входное соединение, а выход лишь один, сокращается количество сигнальных выводов контроллера по сравнению с количеством линий, используемых при 100 %-м дублировании каналов.

Рис. 6. Изолирование сбойных участков в кольце при отказе

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

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

Список литературы

1.   Allayer Rox Bus Architecture. Application Brief AB001, Revision 1.1 (http://www.allayer.com/pdf/ab001.pdf).

2.   Столлинг В. Компьютерные системы передачи данных. / Пер. с англ. – М.: Издат. дом «Вильямс», 2002. – 928 с.

3.    Token ring access method and Physical Layer specifications. ANSI/IEEE Std 802.5-1998E.

4.    Information Systems – Fiber Distributed Data Interface (FDDI) – Token Ring Media Access Control (MAC) (formerly ANSI X3.139-1987 (R1997)).

5.    Малашенко Ю.Е., Новикова Н.М. Модели неопределенности в многопользовательских сетях. – М.: Эдиториал УРСС, 1999. – 160 с.

6.    Басакер Р., Саати Т. Конечные графы и сети. / Пер. с англ. – М.: Глав. ред. ФИЗМАТЛИТ, 1973. – 368 с.