Коммутаторы и маршрутизаторы. Методы коммутации

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

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

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

Узлы коммутации осуществляют один из трех возможных видов коммутации при передаче данных:

- коммутацию каналов;

- коммутацию сообщений;

- коммутацию пакетов.

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

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

Основные достоинства метода:

- возможность работы и в диалоговом режиме, и в реальном масштабе времени;

- обеспечение полной прозрачности канала.

 

Применяется метод коммутации каналов чаще всего при дуплексной передаче аудиоинформации (обычная телефонная связь – типичный пример).

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

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

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

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

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

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

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

 

 

Тесты к теме 6.4

 

6.4.1. У стройства коммутации, выполняющие коммутацию на основе иерархических сетевых адресов, называются

а) маршрутизаторами; # б) серверами; в) адаптерами.

6.4.2. При коммутации каналов

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

пунктами отправления и назначения не устанавливается.

 

6.4.3. При коммутации пакетов

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

 

6.4.4. К логическим видам коммутации относятся

а) коммутация сообщений и пакетов; # б) коммутация каналов и сообщений; в) коммутация каналов и пакетов.

 

Методы маршрутизации

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

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

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

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

1. Простая маршрутизация при выборе дальнейшего пути для сообщения (пакета) учитывает лишь статическое априорное состояние сети, ее текущее состояние – загрузка и изменение топология из-за отказов – не учитывается. Одно из направлений простой маршрутизации – лавинное отправление сообщения сразу по всем свободным каналам. Недостатки такой маршрутизации очевидно.

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

(route table), определяющей кратчайшие пути и время доставки информации до пункта назначения. Эта маршрутизация используется в сетях с установившейся топологией.

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

В большинстве сетей с коммутацией пакетов для выполнения функций по выбору

маршрутов применяется в различных формах выбор кратчайших путей.

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

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

Алгоритм A был предложен Дейкстрой. Алгоритм B имеет форму Форда-Фалкерсона.

Опишем алгоритм A. Рассмотрим сеть, состоящую из шести узлов. Пусть l (i, j) – стоимость линии, соединяющей узлы i и j (если линия, соединяющая узел i с узлом j, отсутствует, то полагаем l (i, j) = ∞): l (1, 2) = 2, l (1, 3) = 5, l (1, 4) = 5, l (1, 5) = ∞, l (1,6) = ∞,

l (2, 1) = 2, l (2, 3) =3, l (2, 4) = 2, l (2, 5) = ∞, l (2, 6) = ∞, l (3, 1) = 5, l (3, 2) =3, l (3, 4) = 3,

l (3, 5) = 1, l (3, 6) = 5, l (4, 1) = 5, l (4, 2) = 2, l (4, 3) = 3, l (4, 5) = 1, l (4, 6) = ∞, l (5, 1) = ∞,

l (5,2) = ∞, l (5,3) =1, l (5,4)=1, l (5, 6) = 2.

Обозначим через D (v) расстояние (сумму весов линий вдоль данного пути) от источника 1 до узла v. Пусть l (i, j) – заданная стоимость пути между узлами i и j. Алгоритм состоит из двух частей: начального шага и итераций, повторяющихся до завершения алгоритма.

1. Начальный шаг. Устанавливаем N = {1}. Для каждого узла v,принадлежащего множеству N, устанавливаем D (v) = l (1, v). Расстояние до узлов, не соединенных с узлом 1, принимаем равным ∞.

2. Каждый последующий шаг. Находим не принадлежащий множеству N узел w, для которого D (w) минимально и включаем w в множество N. Затем обновляем значения D (w) для всех остальных узлов, принадлежащих N путем вычисления

 

D (v) =min [ D (v), D (w)+ l (w, v)].

 

Шаг 2 повторяется, пока в множество N не войдут все узлы.

Применение алгоритма Aк рассматриваемой сети характеризуется последовательными шагами, описанными в таблице 1. Полужирным курсивом в столбцах обозначены минимальные значения D (w) на каждом шаге (при равных расстояниях выбор производится случайным образом). После каждого шага соответствующий узел w добавляется к N. Затем величины D (v) обновляются. Например, после начального шага во время шага 1 к множеству N добавляется узел 4, имеющий минимальное значение D (4)=1. На шаге 2 в N включается узел 5 при D (5)=2, и т.д. После шага 5 все узлы оказываются включенными в множество N, и алгоритм завершается.

 

Таблица 1. Применение алгоритма A к сети

 

 

Шаг	N	D (2)	D (3)	D (4)	D (5)	D (6)
Начальный	{1} {1,4} {1,4,5} {1,2,4,5} {1,2,3,4,5} {1,2,3,4,5,6}	2	3	1 1 1	∞	∞ ∞

 

 

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

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

Дадим описание алгоритма Каждый узел v имеет метку (n, D (v)), где D (v) представляет текущую величину кратчайшего расстояния до получателя, а n – номер следующего узла по текущему рассчитанному кратчайшему пути.

1. Начальный шаг. Если узел назначения – узел 1, то устанавливаем D (1)=0 и отмечаем все остальные узлы (∙, ∞).

2. Отметка кратчайшего расстояния для всех узлов. Для каждого узла v > 1 выполняется следующее: обновляется путем использования текущего значения D (w) для каждого соседнего узла w и вычисления D (w) + l (w, v) с последующим выполнением операции

D (v) = min [ D (w), D (w)+ l (w, v)].

 

Метка v обновляется путем замены n номером смежного узла, что минимизирует только что приведенное выражение, и путем замены D (v) вновь полученным значением. Операция повторяется для каждого узла, пока не прекратятся дальнейшие изменения. Тогда алгоритм завершается, и во всех узлах фиксируются метки как об их кратчайших расстояниях от узла 1, так и до следующего соседнего узла по кратчайшему пути.

Рассмотрим применение алгоритма на примере описанной выше сети. Обращаясь ко второй части алгоритма и применяя ее в циклическом порядке для узлов 2 – 6, находим, что алгоритм завершается после двух циклов. Эти циклы и полученные в результате метки в конце каждое цикла, приводятся в таблице 2 (любой другой порядок обхода узлов приводит к тому же самому окончательному результату).

 

Таблица 2. Алгоритм B

 

 

Шаг	Метки, узел →
Начальный		(∙, ∞) (1, 2) (1, 2)	(∙, ∞) (1, 5) (5, 3)	(∙, ∞) (1, 1) (1, 1)	(∙, ∞) (4, 2) (4, 2)	(∙, ∞) (5, 4) (5, 4)

 

Таким образом, в цикле 1 нужно отметить, что узел 2 является ближайшим к его соседу 1. Его результирующая новая стоимость равна D (v) = D (1) + l (1, 2) = 2. Следовательно, метка, как это указано, имеет вид (1,2). Переходя к узлу 3, приходим к необходимости выбора стоимостей между D (2) + l (2, 3)=5 и D (1) + l (1, 3)=5. Выбирая произвольно

D (1) + l (1, 3), получим (1,5), что показано в таблице (при другом выборе получится то же самое). В цикле 2 узел 3 имеет теперь пять соседних узлов с конечными значениями D (w), между которыми нужно произвести выбор. Минимальное значение D (w) + l (w, 3) равно

D (5) + l (5, 3)=3, и метка узла 3, как показано, меняется на (5, 3). Другие узлы не меняют своих меток, и алгоритм завершается. Дерево кратчайших путей может быть получено обходом меток каждого узла. В результате, узел 2 соединяется с узлом 1, узел 3 – с узлом 5, узел 4 – с узлом 1, узел 5 – с узлом 4 и узел 6 – с узлом 5. Иначе, таблица маршрутов или значение следующего узла в каждом узле по направлению к узлу 1 является первым числом каждой двузначной метки. Для получения полной таблицы маршрутов в каждом узле алгоритм B должен быть повторен для каждого узла, применяемого в качестве узла назначения.

 

Тесты к теме 6.5

 

6.5.1. Простая маршрутизация

а) не учитывает загрузку сети и изменение топологии из-за отказов; #

б) учитывает только изменение топологии сети; в) учитывает и изменение нагрузки, и изменение топологии сети.

 

6.5.2. Фиксированная маршрутизация

а) учитывает только изменение топологии сети; # б) не учитывает загрузку сети и изменение топологии из-за отказов; в) учитывает и изменение нагрузки, и изменение топологии сети.

6.5.3. Адаптивная маршрутизация

а) учитывает и изменение нагрузки, и изменение топологии сети;# б) не учитывает загрузку сети и изменение топологии из-за отказов; в) учитывает только изменение топологии сети

.

6.5.4. Наименее эффективной является

а) простая маршрутизация; # б) фиксированная маршрутизация; в) адаптивная маршрутизация.

 

Упражнение 6.5.1. Примените алгоритм Дейкстры к сети, состоящей из шести узлов

(l (i, j) – стоимость линии, соединяющей узлы i и j): l (1, 2) = 3, l (1, 3) = 4, l (1, 4) = ¥,

l (1, 5) = 2, l (1,6) = 4, l (2, 1) = 1, l (2, 3) =¥, l (2, 4) = 2, l (2, 5) = ∞, l (2, 6) = ∞, l (3, 1) = 5, l (3, 2) =3, l (3, 4) = 3, l (3, 5) = 4, l (3, 6) = 3, l (4, 1) = 7, l (4, 2) = 1, l (4,3) = ∞, l (4, 5) = 3, l (4, 6) = 2, l (5, 1) = 2, l (5,2) = ∞, l (5,3) =3, l (5,4)=4, l (5, 6) = 2.

Упражнение 6.5.2. Примените алгоритм Форда–Фалкерсона к сети, состоящей из шести узлов: l (1, 2) = 2, l (1, 3) = 5, l (1, 4) =6, l (1, 5) = 1, l (1,6) = ¥, l (2, 1) = 1, l (2, 3) =7, l (2, 4) = 2, l (2, 5) = 1, l (2, 6) = ∞, l (3, 1) = 2, l (3, 2) =4, l (3, 4) = 2, l (3, 5) = 3, l (3, 6) = 2, l (4, 1) = ¥, l (4, 2) = 3, l (4,3) = 2, l (4, 5) = 4, l (4, 6) = 1, l (5, 1) = ¥, l (5,2) = 4, l (5,3) =1, l (5,4)=4,

l (5, 6) = 3.