Чернега В., Платтнер Б. Компьютерные сети. Учебное пособие для вузов

Подождите немного. Документ загружается.

Раздел 2. Передача данных в компьютерных сетях

139

правильности приема станцией всех информационных кадров с номерами до

NR–1.

Оставшийся 5-й бит (9-й для расширенного формата) является битом

команды запрос/ответ (P/F), который при размещении в кадре команды ин-

терпретируется как бит ответа F. Бит P/F используется для опроса (P/F=1)

первичной станцией желаемой вторичной станции. Ответ может состоять из

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

P/F=1 для указания последнего кадра в передаваемой последовательности.

Служебные кадры не несут полезной информации, а являются кадрами

команд/ответа и используются для обеспечения управления потоком данных

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

вторичной станциями. Нумерованные S – кадры, содержащие номер пере-

данного NS или принятого NR кадров (Таблица 2.2), применяются первич-

ной станцией для опроса подчиненных станций, либо для посылки квитан-

ции (квитирования) I - кадров, запроса на повторную передачу или времен-

ной приостановки I - кадров. Биты S, расположенные на 3 и 4 позициях об-

ласти управления, определяют команды или ответы (не более 4-х команд

или 4-х ответов).

U - кадры не содержат номера и используются для образования допол-

нительных команд управления звеном передачи данных и дополнительных

ответов и сообщений об ошибках алгоритма. 5 битов могут образовывать 32

дополнительные команды и 32 ответа.

Команды и ответы I- и S- кадров определяются следующим образом:

"Передача информации" – является признаком наличия в I-кадре

информации от источника. Номер NS указывает на порядковый номер пере-

даваемого I-кадра, а номер NR подтверждает все ранее принятые информа-

ционные кадры с номерами до NR–1 включительно;

"Готов к приему" – указывает, что передающая его станция готова к

приему I-кадров;

"Неприем" – используется для запроса повторной передачи всех вхо-

дящих кадров, начиная с NS;

"Не готов к приему" – свидетельствует о том, что станция временно не

может принимать I-кадры;

"Выборочный неприем" – позволяет станции запросить повторную

передачу конкретного кадра с номером NR.

Примером дополнительных команд U-кадра являются коман-

ды/ответы: "Установить расширенный формат", "Некорректный кадр",

"Разъединение" и др.

Информационная область кадра предназначена для размещения дан-

ных, которые могут иметь любую битовую структуру. Длина информацион-

ной области ограничивается предельной длиной кадра, определяемой степе-

Компьютерные сети

140

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

передаваемого сообщения от ошибок. При необходимости информационное

поле блока может быть занято для размещения дополнительных управляю-

щих знаков. Характер информации, расположенной в информационной час-

ти кадра, определяется командой или ответом, которые содержатся в области

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

кратным байту.

Проверочная область кадра содержит контрольную последователь-

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

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

Длина проверочной области в битах равна степени образующего полинома.

Вид образующего полинома Х

+Х

+1. Он стандартизирован рекомен-

дацией международного консультативного комитета по телефонии и теле-

графии (МККТТ).

Работа протокола HDLC заключается в обмене I-, S- и U-кадрами меж-

ду двумя станциями. Она состоит из трех фаз. Сначала одна из сторон зани-

мает канал передачи данных и сигнализирует удаленной станции о запросе

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

которые они будут использовать (задание главной станции, указание 3- или

7-битовых порядковых номеров блоков). Затем наступает фаза обмена дан-

ными и управляющими пакетами для устранения ошибок и управления по-

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

2.5.4. Связь скорости передачи сигналов с полосой пропускания

Знание спектров сигналов, используемых для передачи данных, дина-

мики их изменения при различных видах сигналов, способов и параметров

модуляции, а также переходных процессов в каналах при передаче этих сиг-

налов, позволяет установить соотношения между скоростью передачи и тре-

буемой шириной полосы пропускания используемого канала связи.

На практике нет необходимости (да и возможности) передавать весь

спектр сигнала. Достаточно передать лишь те составляющие, в которых со-

средоточена основная часть энергии (>50%). Так, например, при передаче

“точек” импульсами постоянного тока, основная часть энергии содержится в

двух первых компонентах спектра: постоянной составляющей и первой гар-

монике с частотой f=1/2

, где 

– длительность единичного элемента. Сле-

довательно, минимально необходимая полоса частот канала связи в этом

случае равна

F

min

= 1/2

= B/2, (2.30)

Раздел 2. Передача данных в компьютерных сетях

141

где В – скорость модуляции, бод. Анализируя спектры других видов сигна-

лов можно заметить, что через такую полосу всегда пройдет основная часть

энергии этих сигналов. Следовательно, предельная скорость модуляции при

передаче импульсами постоянного тока равна

max

= 2F

эф

(2.31)

где F

эф

– ширина полосы пропускания канала. Эта формула называется

формулой Найквиста.

При передаче модулированных сигналов предельная скорость модуля-

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

F

min

= 1/

= B, а В

max

= F

эф.

(2.32)

Эти же формулы справедливы для ЧМ и ФМ при малых индексах мо-

дуляции m

ЧМ,

ФМ

< 1. Если передача модулируемых сигналов осуществля-

ется с одной боковой полосой, то требуемая ширина полосы канала связи

уменьшится вдвое, т.е.

max

 2F

эф

. (2.33)

2.6. Способы защиты от ошибок на канальном уровне

2.6.1. Общая характеристика способов защиты передаваемых данных

В процессе передачи информации по линиям и каналам связи компью-

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

Кроме того, они дополнительно искажаются за счет неидеальности частот-

ных характеристик тракта передачи. В большой степени задача борьбы с по-

мехами и искажениями в линиях и каналах связи решается в модуляторах и

демодуляторах систем передачи данных путем использования оптимальных

сигналов и схем приема. Однако, несмотря на это, результирующая вероят-

ность ошибки по единичным элементам на выходе демодулятора находится

в пределах 10

–3

…10

–5

. Нижняя граница этого диапазона соответствует циф-

ровым каналам, образованным по коммутируемым линиям городских теле-

фонных сетей, и декаметровым каналам связи. Верхняя граница относится к

каналам, организованным на выделенных (некоммутируемых) линиях и ка-

налах, получаемым за счет уплотнения линий каналообразующей аппарату-

рой с ИКМ. В трактах передачи с использованием оптических линий вероят-

ность ошибки по единичным элементам существенно ниже и находится в

Компьютерные сети

142

пределах 10

–6

…10

–8

. В то же время вероятность ошибки по символам (бай-

там) при передаче данных в компьютерных сетях общего пользования долж-

на быть не хуже 10

–6

, а в некоторых сетях требуется обеспечивать вероят-

ность ошибок по символам не более 10

–8

. Из этого следует, что перед обра-

боткой информации в компьютере верность передачи ее на канальном уров-

не должна быть повышена на 3…5 порядков (от 10

–3

по элементам до 10

–8

по

символам).

Снижение количества ошибок может быть обеспечено за счет улучше-

ния качественных характеристик линий и каналов связи. В настоящее время

происходит процесс замены магистральных проводных линий связи на опто-

волоконные. Однако этот процесс очень трудоемкий, дорогостоящий и про-

должительный во времени. На нижнем уровне сетей еще долго будут оста-

ваться проводные линии связи. А каналы радиосвязи, которые все шире ис-

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

защитить от помех.

Значительного повышения качества связи можно достичь только с по-

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

альными устройствами защиты от ошибок (УЗО), либо программным спо-

собом при обработке данных. Применение УЗО в виде отдельных аппарат-

ных средств характерно для канального уровня сети, где защита от ошибок

программным способом требует значительных затрат машинного времени. В

настоящее время УЗО обычно интегрируется в одной БИС совместно с мо-

дулятором-демодулятором и системой синхронизации.

Методы защиты от ошибок зависят от типа каналов, применяемых для

передачи данных и регламентируются соответствующими протоколами ка-

нального уровня (BSC, HDLC и др.). При симплексных каналах для защиты

информации используется многократное повторение одного и того же бло-

ка (кадра) данных или корректирующие коды, исправляющие ошибки. В

случае дуплексных и полудуплексных каналов защита информации осуще-

ствляется с помощью кодов, обнаруживающих ошибки. Блок, в котором

обнаружены искаженные символы, повторяется после запроса, посылаемого

по постоянно действующему каналу обратной связи (ОС) на передающую

сторону.

При многократной передаче каждая кодовая комбинация (или блок)

передается нечетное количество раз (обычно 3…5), а на приеме производит-

ся сравнение принятых знаков, и решение принимается "голосованием по

большинству" (мажоритарный метод). Выбирая нужное количество повто-

рений Кп, можно обеспечить сколь угодно малую вероятность ошибок, но и

эффективная скорость передачи при этом снижается в Кп раз.

Поток ошибок в канале отличается большой неравномерностью;

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

Раздел 2. Передача данных в компьютерных сетях

143

которых ошибки появляются редко. Кодовые методы исправления ошибок

требуют больших аппаратурных затрат или времени, и поэтому в системах

телеобработки находят относительно редкое применение (в ряде случаев ис-

пользуются коды Хемминга).

Большое распространение для исправления ошибок получили системы

с обратной связью. Системы с ОС, в зависимости от назначения канала об-

ратной связи, делятся на системы с автоматическим запросом повторения

блока при ошибках ARQ (Automatic Repeat reQuest) и системы с информаци-

онной обратной связью (ИОС). В таких системах обратная связь использу-

ется для информирования передатчика о текущем состоянии канала переда-

чи данных и изменения избыточности передачи в зависимости от количества

и характера ошибок.

В системах с автоматическим запросом решение о необходимости по-

вторения информационного блока вырабатывается в приемнике путем ана-

лиза его на отсутствие ошибок. Если ошибки не обнаружены и имеется сво-

бодный буфер для записи блока, то в канал ОС посылается подтверждение

(квитанция) правильности приема, а в противном случае – запрос повторной

передачи ошибочно принятого блока.

В системах с ИОС по каналу обратной связи осуществляется передача

всего принятого информационного блока, который на передающей стороне

сравнивается с переданным. При их совпадении в канал связи поступает сле-

дующий блок, а при обнаружении ошибок в прямой канал посылается ко-

манда "Стирание", и искаженный при передаче блок передается повторно. В

более сложных системах с ИОС по обратному каналу передается не весь

блок, а некоторая комбинация, отражающая характерные признаки принято-

го сообщения. Способ передачи данных с информационной обратной связью

используются в компьютерных сетях относительно редко. Он применяется

преимущественно в упрощенном виде – так называемый "эхоплекс". В соот-

ветствии с этим способом каждый символ, посылаемый компьютером на

удаленный пункт, возвращается по каналу обратной связи в виде "эха".

В системах передачи данных количество повторений одного и того же

блока ограничивается, и при превышении заданного числа повторений сиг-

нализируется аварийное состояние канала связи.

Для обнаружения и исправления ошибок, возникающих при передаче

данных, разработано большое количество различных кодов. Все множество

кодов делится на блочные и непрерывные. В блочных кодах передаваемая

информационная последовательность разбивается на отдельные блоки, кото-

рые кодируются и декодируются независимо друг от друга. В непрерывных

кодах, называемых также сверточными, передаваемая информационная по-

следовательность не разделяется на блоки, а проверочные элементы разме-

щаются в определенном порядке между информационными. Процессы коди-

Компьютерные сети

144

рования и декодирования в сверточных кодах также имеют непрерывный ха-

рактер.

Блочные коды в свою очередь делятся на разделимые и неразделимые.

В разделимых кодах функции элементов, входящих в блок разграничены:

одни разряды являются информационными, а другие – проверочными. Во

всех блоках данного кода информационные и проверочные элементы зани-

мают одни и те же позиции. Разделимые коды обозначают как коды (n,k),

где n – разрядность блока, k – число информационных разрядов в блоке. В

неразделимых кодах деление на информационные и проверочные разряды

отсутствует. К таким кодам относятся коды с постоянным весом.

Корректирующая способность кода зависит от кодового расстояния d,

численно равного минимальному количеству элементов, которыми отлича-

ется любая кодовая комбинация от другой. В общем случае должно соблю-

даться равенство

d=t

+1 ,

где t

и t

– число обнаруживаемых и исправляемых ошибок соответственно,

причем обязательно условие t

 t

.Если код только обнаруживает ошибки,

то d=t

+1, а в случае только исправления – d = 2t

+1. Количество провероч-

ных элементов r корректирующего кода зависит от вида кода, а число ин-

формационных элементов k равно k = n–r. Отношение r/n называют коэф-

фициентом избыточности корректирующего кода.

Ниже будут рассмотрены только несколько видов кодов, которые на-

шли наибольшее применение для защиты информации от ошибок в компью-

терных сетях.

2.6.2. Передача данных с автоматическим запросом

Существует несколько разновидностей систем с автоматическим за-

просом повторной передачи ARQ: системы ARQ с ожиданием подтвержде-

ния; системы ARQ с непрерывной передачей и системы с выборочным (се-

лективным) запросом. В русскоязычной литературе системы с автоматиче-

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

Самыми простыми и достаточно распространенными в компьютерных сетях

являются системы ARQ с ожиданием подтверждения (ARQ-О). Структурная

схема системы ARQ-О изображена на рисунке 2.34.

Кодовая n-разрядная комбинация, поступающая от источника инфор-

мации (ИИ), через логическую схему ИЛИ, записывается в буферный нако-

питель (БН), кодируется помехоустойчивым кодом в кодере (К) и с помо-

щью передатчика (Пд) выдается в прямой канал связи (ПКС). Затем источ-

Раздел 2. Передача данных в компьютерных сетях

145

ник информации ИИ останавливается, и передача данных прекращается до

приема сигнала подтверждения АСК (Acknowledgement).

На удаленной станции поступающее сообщение регистрируется при-

емным устройством (Пм), декодируется в блоке Дк, заносится в БН и при от-

сутствии в нем ошибок выдается потребителю информации (ПИ), а по кана-

лу обратной связи (КОС) передается сигнал подтверждения правильности

приема АСК. При обнаружении ошибки Дк посылает через передатчик кана-

ла ОС сигнал повторного запроса искаженного блока NAK (Negative

Acknowledgement), а принятая комбинация, находящаяся в БН приемника,

стирается.

На передающей стороне приемник сигналов обратной связи, приняв

запрос NAK, формирует управляющий сигнал, который открывает ключ

(Кл), и блок, находящийся в БН передатчика, повторно поступает в ПКС.

Одновременно передаваемый блок вновь запоминается в накопителе БН. В

случае приема сигнала подтверждения Кл остается закрытым, и от ИИ за-

прашивается новый блок данных, который параллельно с кодированием и

передачей в ПКС заносится в БН на место предыдущего.

При трансформации сигналов запроса NAK в подтверждение АСК под

действием помех в канале ОС, возможно пропадание блока, а при обратном

преобразовании АСК в NAK один и тот же блок передается дважды, т.е.

имеет место так называемая "вставка" блока (кадр-дубликат). Для уменьше-

ния вероятности выпадения или вставки используют циклическую нумера-

цию блоков, а на приемной стороне контролируют очередность их поступле-

ния. При нарушении очередности предыдущий блок запрашивается вновь.

Достоинством систем ARQ-O является их простота, а недостатком –

потери времени на ожидание сигнала подтверждения или запроса. Такие

системы целесообразно применять в полудуплексных каналах ПД, когда по-

Рисунок 2.34 – Структурная схема системы передачи данных с автоматическим

запросом ARQ-О

Компьютерные сети

146

сле завершения передачи блока устройство переключается в режим приема

сигнала по каналу ОС, и время ожидания частично совпадает со временем

переключения направления передачи.

Более высокую эффективную скорость передачи информации по кана-

лам связи обеспечивают системы ARQ с непрерывной передачей (ARQ-НП).

Для реализации этого алгоритма требуется полнодуплексное соединение. В

таких системах закодированные помехоустойчивым кодом блоки данных по-

ступают непрерывно в ПКС без ожидания сигнала подтверждения. Макси-

мальное количество блоков W , которое можно передать без подтверждения

их приема, называют шириной окна. Одновременно идет запись информа-

ции в буферный накопитель. При обнаружении ошибки в информационном

блоке приемник передает по каналу ОС сигнал запроса NAK и блокирует за-

пись в приемный накопитель последующих W – 1 блоков, что предотвращает

возможность нарушения очередности выдачи блоков потребителю информа-

ции.

Передающая сторона, получив сигнал запроса NAK, прекращает пода-

чу в ПКС новых сообщений и повторяет из БН все комбинации, начиная с

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

ся по времени поступления сигнала NAK.

Современные канальные протоколы предусматривают семикадровые

окна. Это означает, что ООД может посылать семь блоков без получения от-

ветного подтверждения. Для предотвращения вставок и дублирования бло-

ков по причинам, указанным выше, применяют циклическую нумерацию

блоков по модулю W + 1.

С целью уменьшения объема информации, передаваемой при запросах,

разработаны системы ARQ и адресным переспросом (ARQ-АП), отличия ко-

торых состоит в том, что по обратному каналу передается сигнал запроса с

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

2.6.3. Блочное кодирование

В компьютерных сетях для защиты информации от ошибок из блоч-

ных кодов наиболее широко используются коды с проверкой по паритету,

коды Хемминга и циклические коды.

Коды с проверкой на четность/нечетность (по паритету) являются

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

ошибки. Они образуются добавлением к передаваемой комбинации, состоя-

щей из k информационных элементов безизбыточного кода, одного кон-

трольного бита так, чтобы общее количество единиц в передаваемой комби-

нации было четным или нечетным. Если контрольный бит выбран так, что

Раздел 2. Передача данных в компьютерных сетях

147

результат суммирования четный, то имеет место положительный паритет

(even parity); если при добавлении контрольного бита результат будет нечет-

ным, то отрицательный паритет (odd parity). В итоге общее количество битов

в передаваемой комбинации n = k +1. На приемной стороне производят про-

верку поступающей последовательности на четность (либо нечетность). При

четном (нечетном) числе единиц предполагается, что ошибок нет, и потреби-

телю выдаются k информационных битов, а контрольный элемент отбрасы-

вается.

Вероятность обнаруживаемых ошибок на четность (нечетность) n –

разрядной кодовой комбинации Р

кк

зависит от длины кодовой комбинации n

и вероятности ошибочного приема единичных элементов P

кк

 C

(1–P

)

n–2

где C

– число сочетаний из n по m; C

= n! / (m!(n–m)!).

Итеративные коды являются разновидностью кодов с проверкой на

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

кодами (rectangular code). Они характеризуется наличием двух или более

систем проверок внутри каждой кодовой комбинации. Итеративный код

строится следующим образом. Из элементов передаваемого блока формиру-

ется прямоугольная матрица, состоящая из М строк и N столбцов. Затем к

каждой строке и каждому столбцу прибавляются биты паритета, что в ре-

зультате дает матрицу размером (M+1)×(N+1)

...

....................................

...

1321

77737271

22232221

11131211













nn

qqqqq

raaaa

где a

(i=1..7; j=1,2,..,n) – информационные биты; q

,.., q

– проверочные

биты знаков, образующие первую совокупность проверок; r

(i=1..7) – кон-

трольные элементы, которые являются суммой по модулю 2 всех элементов

строки; q

n+1

– контрольный элемент проверочных битов знаков. Каждый знак

нужно передавать последовательно, начиная с первого бита, а

1,j

и кончая

восьмым проверочным q

Приведенный итеративный код является простейшим кодом этого

класса с кодовым расстоянием d=4. Он обнаруживает ошибки кратности до 3

и все ошибки нечетной кратности, а также любой пакет ошибок длиной S+1,

Компьютерные сети

148

где S – длина строки матрицы кода. Основным недостатком итеративных ко-

дов, использующих проверки на четность по столбцам и строкам, является

высокая избыточность – около 15%. Однако декодирование и кодирование

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

жестких требованиях по достоверности передачи данных применяется ите-

ративный код с тремя проверками. Причем, третья дополнительная проверка

на четность осуществляется по диагоналям матрицы.

Код Хэмминга – один из наиболее эффективных кодов, позволяющий

исправлять одиночные ошибки. Кодовое расстояние d=3. Этот код образует-

ся дополнением информационной части передаваемого блока, состоящей из

k битов, r проверочными элементами. При выборе длины передаваемого

блока n и количества проверочных элементов r руководствуются неравен-

ством



n+1.

Учитывая, что r = n–k , неравенство может быть представлено в виде



/ (n+1) , (2.34)

где n и k принимают только целые значения. Неравенство является исход-

ным для определения длины кодовой комбинации по заданному числу k.

Первый проверочный бит П

кода Хэмминга образуется суммировани-

ем по модулю 2 всех нечетных элементов блока, начиная с первого, т.е.

=а

 а

… . (2.35)

Результат проверки П

определяет второй разряд проверочной комби-

нации (синдрома ошибки). Он вычисляется суммированием тех элементов

блока, номера которых соответствуют n–разрядным двоичным числам,

имеющим единицу во втором разряде,

= а

 а

… . (2.36)

Третья проверка П

охватывает разряды, номера которых соответству-

ют n - разрядным двоичным числам, имеющим единицу в третьем разряде.

=а

 а

… . (2.37)

Аналогичным образом находятся разряды, охватываемые четвертой,

пятой и т.д. проверками