2. Топология сети передачи данных. Примеры элементарных топологий, основные характеристики. Алгоритмы маршрутизации и методы передачи данных.
- При организации параллельных вычислений в мультикомпьютерах для организации взаимодействия, синхронизации и взаимоисключения параллельно выполняемых процессов используется передача данных между процессорами вычислительной среды. Временные задержки при передаче данных по линиям связи могут оказаться существенными (по сравнению с быстродействием процессоров) и, как результат, коммуникационная трудоемкость алгоритма оказывает существенное влияние на выбор параллельных способов решения задач.
- Примеры топологий сети передачи данных
- Структура линий коммутации между процессорами вычислительной системы (топология сети передачи данных) определяется, как правило, с учетом возможностей эффективной технической реализации. Немаловажную роль при выборе структуры сети играет и анализ интенсивности информационных потоков при параллельном решении наиболее распространенных вычислительных задач.
Топология сети передачи данных – это структура линий коммутации между процессорами вычислительной системы. Топология представляет собой полный граф, в котором передача данных может быть организована между любыми двумя вершинами (процессорами сети). Топология определяется с учетом возможностей эффективной технической реализации на основе анализа интенсивности передачи информационных потоков. К числу типовых топологий обычно относят следующие схемы коммуникации процессоров (см. рисунок). Полный граф (completely-connected graph or clique) – система, в которой между любой парой процессоров существует прямая линия связи, поэтому данная топология обеспечивает минимальные затраты при передаче данных, однако является сложно реализуемой при большом количестве процессоров. Линейка (linear array or farm) – система, в которой все процессоры перенумерованы по порядку и каждый процессор, кроме первого и последнего, имеет линии связи только с двумя соседними (с предыдущим и последующим) процессорами; такая схема является, с одной стороны, просто реализуемой, а с другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных вычислений). 
Кольцо (ring) – данная топология получается из линейки процессоров соединением первого и последнего процессоров линейки. Звезда (star) – система, в которой все процессоры имеют линии связи с некоторым управляющим процессором; данная топология является эффективной, например, при организации централизованных схем параллельных вычислений. Решетка (mesh) – система, в которой граф линий связи образует прямоугольную сетку (обычно двух — или трехмерную); подобная топология может быть достаточно просто реализована и, кроме того, может быть эффективно использована при параллельном выполнении многих численных алгоритмов (например, при реализации методов анализа математических моделей, описываемых дифференциальными уравнениями в частных производных). Гиперкуб (hypercube) – данная топология представляет частный случай структуры решетки, когда по каждой размерности сетки имеется только два процессора; данный вариант организации сети передачи данных достаточно широко распространен в практике и характеризуется следующим рядом отличительных признаков: а) два процессора имеют соединение, если двоичные представления их номеров имеют только одну различающуюся позицию; б) N-мерный гиперкуб может быть разделен на два (N-1)-мерных гиперкуба (всего возможно N различных разбиений); в) кратчайший путь между любыми двумя процессорами имеет длину, совпадающую с количеством различающихся битовых значений в номерах процессоров (данная величина известна как расстояние Хэмминга). Т.к. каждый процессор может принимать участие только в одной операции приема-передачи данных, то параллельно могут выполняться только те коммуникационные операции, в которых взаимодействующие пары процессоров не пересекаются между собой. Характеристики топологии сети В качестве основных характеристик топологии сети передачи данных наиболее широко используется следующий ряд показателей: • Диаметр – показатель, определяемый как максимальное расстояние между двумя процессорами (под расстоянием обычно понимается величина кратчайшего пути между процессорами); данная величина может характеризовать максимально-необходимое время для передачи данных между процессорами, поскольку время передачи обычно прямо пропорционально длине пути; • Связность (connectivity) – показатель, характеризующий наличие разных маршрутов передачи данных между процессорами сети; конкретный вид данного показателя может быть определен, например, как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области; • Ширина бинарного деления (bisection width) – показатель, определяемый как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области одинакового размера; • Стоимость – показатель, который может быть определен, например, как общее количество линий передачи данных в многопроцессорной вычислительной системе. Алгоритмы маршрутизации Очевидно, что временные задержки при передаче данных по каналам связи при взаимодействии процессов влияют на эффективность параллельных вычислений. Алгоритмы маршрутизации определяют путь передачи данных от процессора-источника до процессора получателя сообщения. Алгоритмы маршрутизации должны определять оптимальный, т.е. кратчайший путь передачи данных с использованием детерминированных и адаптивных методов выбора маршрутов (адаптивные алгоритмы определяют пути передачи данных в зависимости от существующей загрузки коммуникационных каналов). К числу наиболее распространенных оптимальных алгоритмов относится класс методов покоординатной маршрутизации (dimension-ordered routing), в которых поиск путей передачи данных осуществляется поочередно для каждой размерности топологии сети коммуникации. Например, для двумерной решетки такой подход приводит к маршрутизации, при которой передача данных сначала выполняется по одному направлению (например, по горизонтали до достижения вертикали процессоров, в которой располагается процессор назначения), а затем данные передаются вдоль другого направления (данная схема известна под названием алгоритма XY-маршрутизации). Для гиперкуба покоординатная схема маршрутизации может состоять, например, в циклической передаче данных процессору, определяемому первой различающейся битовой позицией в номерах процессоров, на котором сообщение располагается в данный момент времени, и на который сообщение должно быть передано. Время передачи данных между процессорами определяет длительность выполнения параллельного алгоритма в многопроцессорной вычислительной системе. Время передачи данных включает: − время начальной подготовки (tн) характеризует длительность подготовки сообщения для передачи, поиска маршрута в сети и т.п.; − время передачи служебных данных (tс) между двумя соседними процессорами (между которыми имеется физический канал передачи данных); к служебным данным может относиться заголовок сообщения, блок данных для обнаружения ошибок передачи и т.п.; − время передачи одного слова данных по одному каналу передачи данных (tк); длительность подобной передачи определяется пропускной способностью сети. Рассмотрим два наиболее распространенных метода передачи данных. Первый – выполняет передачу сообщений как неделимых (атомарных) блоков информации (store-and-forward routing or SFR). В этом случае процессор-отправитель готовит весь объем данных для передачи, определяет процессор, которому следует направить данные, и запускает операцию передачи данных. Процессор-получатель сообщения, осуществляет прием данных, затем, при необходимости приступает к передаче принятого сообщения далее по маршруту. Время передачи данных tпд для сообщения размером m байт по маршруту длиной l определяется выражением 
При достаточно длинных сообщениях временем передачи служебных данных можно пренебречь и выражение может быть записано в более простом виде 
Второй способ — выполняет передачу сообщений в виде блоков информации, в результате чего передача данных может быть сведена к передаче пакетов. В этом случае принимающий процессор может осуществлять пересылку данных по дальнейшему маршруту непосредственно сразу после приема очередного пакета, не дожидаясь завершения приема данных всего сообщения. Время пересылки данных при использовании метода передачи пакетов будет определяться выражением 
В большинстве случаев метод передачи пакетов приводит к более быстрой пересылке данных; кроме того, данный подход снижает потребность в памяти для хранения пересылаемых данных для организации приема-передачи сообщений, а для передачи пакетов могут использоваться одновременно разные коммуникационные каналы. С другой стороны, реализация пакетного метода требует разработки более сложного аппаратного и программного обеспечения сети, может увечить накладные расходы (время подготовки и время передачи служебных данных).
Для продолжения скачивания необходимо пройти капчу:
Виды топологий. Методы доступа к среде передачи данных.
1. Топология – это способ организации связей между взаимодействующими узлами в сети.
Топология – это конфигурация графа, вершинами которого являются компьютеры и другое сетевое оборудование, а ребрами – связи между ними.
— физическая – определяет способ организации физических связей (подключений)
— логическая – описывает маршруты передачи данных по физическим соединениям.
1) полносвязная – каждый связан с каждым
«+» — гарантированное обеспечение связи между всеми устройствами
«-» — громоздкая и неэффективная
2) неполносвязная – в этом случае отдельные физические соединения убираются; требуются промежуточные узлы для передачи данных между всеми устройствами сети – транзитные узлы.
Виды неполносвязной топологии
Ячеистая – удаляем некоторые связи из полносвязной топологии, оставляем связи между устройствами, которые интенсивно обмениваются данными. Характерна для глобальной сети.
Общая шина – все устройства подключены к одному кабелю (коаксиальный)
— низкая надежность – любой дефект кабеля и вся сеть «неработоспособна»
— низкая производительность – в один момент времени может передавать данные только одно устройство
топология сети, все станции которой подсоединены к одному кабелю. Каждая станция принимает сигналы, переданные любой другой станцией, распознает предназначенные ей пакеты и имеет возможность проигнорировать к ней не относящиеся.
Звезда – имеет центральный транзитный узел, через который идет обмен данными между всеми устройствами
«+» — большая надежность по сравнению с общей шиной
«-» — «слабое звено» — это центральный транзитный узел
топология сети, в которой соединения между станциями или узлами сети устанавливаются через концентратор. Концентратор (hub) — функциональное устройство, входящее в состав оборудования узла вычислительной сети, которое обеспечивает передачу данных от большого количества источников по меньшему количеству каналов связи
Иерархическая топология – организует иерархию связей сети
Кольцевая – данные передаются по кольцу, как правило, в одном направлении от одного устройства к другому.
топология сети, все станции которой соединены только с двумя соседними. Все данные в этой сети передаются от одной станции к другой в одном направлении. Каждая станция работает как повторитель. Время отклика в кольце зависит от числа подключенных к нему станций — чем их больше, тем длительнее задержка передаваемых данных. Недостатком является и тот факт, что в случае выхода из строя одной из станций кольцо «разрывается». Однако большинство сетей, основанных на этой топологии, имеют средства автоматического восстановления работоспособности после отказа узла.
Смешанная топология – включает все виды топологий
Tree (network) — «Дерево»: топология сети с более чем двумя оконечными и, по крайней мере, двумя промежуточными узлами (концентраторами). В такой сети между любыми двумя узлами существует только один путь
Метод доступа к среде передачи данных
Определяет, каким образом разделяемый общий ресурс (физическая среда, кабель…) предоставляется узлам сети для осуществления передачи данных.
1.1) множественный доступ с контролем несущей и обнаружением коллизий (CSMA/CD)/ Узлы прослушивают кабель и ожидают, когда можно будет передавать данные (Ethernet)
1.2) множественный доступ с контролем несущей и предотвращением коллизий (CSMA/CA). Каждый узел перед передачей сигнализирует о своем намерении начать передачу данных (Wi-Fi сети).
Метод доступа определяется топологией.
CSMA/CD – общая шина, звезда (на основе Hub`а)
с передачей маркера – кольцевая топология
приоритет запроса – Ethernet сеть 100VG-Any LAN (802.12)