вычислительные сети

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

Рис. 2 Процедура передачи данных. 1 - задержка подключения, 2 - распространение сигнала, 3 - сигнал подтверждения о создании физического соединения, 4 - общее время коммутации, 5 - передача информации, 6 - разъединение канала. Отп - отправитель, П - получатель, УКК -узел коммутации канала.

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

Рис. 3 Узел коммутации сообщений

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

Рис. 4 Процедура передачи данных при коммутации сообщений и коммутации пакетов. П - пакет, 1 - задержка подключения, 2 - время передачи информации между смежными узлами, 3 - общее время

В узлах коммутации пакетов реализовано три нижних уровня ЭМВОС, на которых используются три типа протокольных блоков данных: пакет, кадр и последовательность бит.

На рис.5 показана последовательность преобразования блоков данных и передача их по сети коммутации.

Рис. 5

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

5.4 Маршрутизация

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

Простая маршрутизация реализуется без учета топологии сети и отличается низкой ффективностью.

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

К простой маршрутизации относятся случайная, лавинная и по предыдущему опыту.

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

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

Рис.1 Лавинная маршрутизация.

Х - уничтожение пакета на входе, ti - направление маршрутизации

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

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

Среди доступных путей выбираем минимальный (D1,3), и вычисляем пути, ведущие из вершины А1 во все смежные с А3. Это осуществляется за счет добавления к величине пути D1,3 длины соответствующей дуги. Полученные значения путей заносятся в таблицу маршрутов. Если в какую-то из вершин путь был ранее определен, то фиксируется его минимальное значение. После первого шага длина пути L1,5 = 4, а после второго

(L1,3 + L3,5) = 1 + 2 = 3.

В общем случае правило обновления маршрутов определяется на основании условия

[1]:

Lk,m – длина дуги, между текущей и расчетной (m-ой) вершинами.

На третьем шаге формируется маршрут D1,6: (L1,3 + L3,5 + L5,6) = 5.

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

5.5 Защита информации от ошибок

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

Рис. 1

Вкачестве ячеек памяти используются D - триггеры. На вход D подается сообщение

ввиде сигнала, например 100. На вход С - последовательность синхросигналов. - соответственно прямой и обратный выходы. Прямые выходы D - триггера подключены к

Рис. 2. Временная диаграмма работы регистра сдвига

Если на вход D продается сигнал 1, то поступающий на вход С синхросигнал переключает триггер, и на выходе регистра формируется код 100. Второй синхросигнал опять переключает триггеры и сигнал единицы поступает в ячейку 2. На выходе регистра - 010.

Третий синхросигнал опять переключает триггер, на выходе которого - 001. Подключим к выходам регистра Q1 и Q2 сумматор по модулю два (рис. 3). Выход сумматора по модулю два подключим как обратную связь к входу D регистра.

Рис. 3. Схема регистра сдвига и сумматора по модулю два

Рассмотрим совместную работу регистра сдвига и сумматора по модулю два (таблица 2).

Таблица 2.

Первый синхросигнал переключает первый триггер и на выходах регистра Q0-2 появляется сигнал 100. Одновременно сигналы логических 0 с выходов Q1-2 поступают на вход сумматора по модулю два, на выходе которого формируется сигнал логического 0, этот сигнал поступает на вход регистра. На втором такте, на входе регистра - 0, на выходах Q0-2 - последовательность 010. Сигнал логической 1 поступает на вход сумматора, на выходе которого тоже формируется сигнал логической 1 и передается на вход регистра. На третьем такте, на входе регистра - 1, на выходах Q0-2 последовательность 101. На сумматор по модулю два поступают сигналы 0 и 1 соответственно с выходов регистра Q1 и Q2. На выходе сумматора сигнал - 1, поступающий на вход регистра. На четвертом такте на выходах Q0-2 последовательность 110. На выходе сумматора по модулю два - 1. И на последнем такте, пятом, на всех выходах регистра устанавливаются значения логических 1.

Построение схем умножителя и делителя для заданного полинома:

P(x)=A0X0+ A1X1+ …+ An-2Xn-2+ An-1Xn-1 (1.6)

осуществляется по следующим правилам:

•а) Построение делителя (рис. 4, a). Число ячеек памяти равно n-1, отсутствует ячейка для члена со старшей степенью. Сумматор по модулю два ставится перед ячейкой. Операция деления осуществляется с помощью обратной связи.

•б) Построение умножителя (рис. 4, б). Число ячеек равно n-1, отсутствует ячейка для члена со старшей степенью. Сумматор по модулю два ставится после ячейки. Сигнал поступает одновременно с входа в ячейки и на сумматор по модулю два, что обеспечивает операцию умножения.

Рис. 4

Например, для полинома P(x)=X4+X3+1 схемы делителя и умножителя выглядят, как показано на рисунке 5. Если в полиноме значение разряда равно 0, то сумматор по модулю два перед ячейкой не ставится.

Рис. 5

Схема кодера, реализующего построение циклического кода представлена на рисунке 6. Так как первая операция при построении CRC-кода - умножение, то расположение ячеек и сумматоров, как у умножителя. Кодер состоит из четырех ячеек памяти и двух сумматоров по модулю два, расположенных после ячеек Х2 и Х3 и ключа К1.

Рис. 6

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

G(x)= 1*Х6+1*Х5+0*Х4+1*Х3+0*Х2+1*Х1+0*Х0

или

G(x)= 1*Х6+1*Х5+1*Х3+1*Х

2.Число передаваемых символов m=7. Определим количество контрольных символов по формуле (1.1):

k=E[log2[(7+1)+ E[log2(7+1)]]]=Е[log2(8+3)]=4

Следовательно, общее число символов в передаваемой кодовой комбинации F(x) равно n=7+4=11. В качестве образующего полинома выберем P(x)=X4+X3+1.

3.Умножим передаваемую кодовую комбинацию G(x) на множитель Х4:

Q(x)=G(x)*Х4=(Х6+Х5+Х3+Х)*Х4=Х10+Х9+Х7+Х5

4.Выполним деление полученного полинома Q(x) на образующий полином Р(х):

Остаток от деления R(x)=X+1. 5.Циклический код будет иметь вид:

F(x)= Q(x)+R(x)=Х10+Х9+Х7+Х5+X+1, или 11010100011.

Процесс создания CRC - кода по схеме кодера приведен в таблице 3. Первоначально значения в ячейках памяти установлены в 0. Ключ К1 находится в положении 1 (замкнут). Кодовая комбинация последовательно поступает на вход сумматора С1, установленного

после ячейки Х3. На вход сумматора С2, установленного после ячейки Х2 поступают сигналы из ячейки Х2 и с выхода сумматора С1. Суммированные сигналы в сумматоре С2 поступают на вход ячейки Х3 . На восьмом такте работы схемы ключ К1 переходит в положение 2 (размыкается) и происходит создание контрольных символов.

Таблица 3.