2 Защита инф-ии на канальном уровне

Введение

Цель лабораторной работы - исследование способов защиты от ошибок в системе передачи данных (СПД) на канальном уровне стека протоколов OSI коммуникационных систем.
Канальный уровень, обеспечивает необходимую достоверность передачи информации, которая характеризуется степенью соответствия принятого сообщения переданному. На этом уровне происходят такие операции как формирование кадра, вычисление контрольной последовательности кадра, контроль ошибок в принятом кадре. В состав каждого кадра вводятся избыточные разряды, которые вычисляются по определенному алгоритму. Принятый кадр анализируется на соответствие правилу кодирования, и в случае нарушения правила принимающая сторона передает сообщение об этом на передающую сторону. Следует отметить, что канальные протоколы некоторых скоростных сетей не исправляют ошибки. Эту задачу решают протоколы верхних уровней стека OSI.
Вероятность возникновения ошибки p в канале является основной характеристикой физического уровня СПД. Эта величина равна отношению числа ошибочно принятых бит к общему количеству переданных за определенное время и зависит от уровня помех, вида модуляции, правила принятых решений и других условий. В аналоговых каналах, например, она находится в пределах 10-310-5, что недопустимо для системы передачи данных. С помощью протоколов канального уровня вероятность ошибки может быть уменьшена на несколько порядков. Системы передачи данных используют каналы без обратной связи и каналы с обратной связью.
В канале без обратной связи передатчик не получает сведений о результатах передачи. Кадр может быть потерян, искажен ошибками. Передача очередного кадра зависит лишь от темпа передачи. Принимающая сторона на основе анализа состояния кадра может принять правильное решение и исправить некоторые ошибки (если они были). Однако, нет гарантии что любые ошибки будут исправлены. Канал без обратной связи применим, например, для передачи оцифрованной речи, цифрового изображения, в командных системах управления.
В канале с обратной связью передатчик получает сведения о состоянии кадра, принятого другой стороной. Поэтому передающая сторона может принять решение о повторной передаче искаженных кадров с целью обеспечения правильного приема.
Скорость передачи информации будет зависеть от уровня помех в канале и алгоритма работы протокола канала. Протоколы каналов с обратной связью реализуют различные дисциплины повторной передачи искаженных кадров.
В лабораторной работе выполняется моделирование на ЭВМ протоколов канального уровня. Основной параметр физического уровня СПД - вероятность ошибки бита p вводится в программу моделирования канала и изменяется в широких пределах с целью исследования эффективности различных кодов, алгоритмов декодирования и протоколов управления передачей информации.

1. Канал без обратной связи

Защита информации от ошибок происходит за счет внесения избыточности в передаваемые кадры. Кадры можно рассматривать как кодовые комбинации корректирующего циклического кода. В лабораторной работе используются следующие генераторные многочлены циклических кодов:
g0 = 1
g1 = 1+x
g2 = 1+x+x6
g3 = 1+x2+x6+x7
g4 = 1+x3+x4+x5+x8+x10+x12
g5 = 1+x+x3+x6+x8+x9+x10+x11+x12+x13
g6 = 1+x+x2+x3+x6+x7+x9+x15+x16+x17+x18

Примечание.
Одночлен g0 формирует код без избыточности, который не
обеспечивает защиту от ошибок.

Число бит n в кадре (размер кадра) всегда равно 63. Количество информационных (k) и контрольных (n-k) разрядов зависит от генераторного многочлена циклического кода. В таблице 1 представлены параметры, циклических кодов полученных с помощью перечисленных выше генераторных многочленов.
Таблица 1
Номер многочлена
0
1
2
3
4
5
6

Минимальное кодовое
расстояние, d
1
2
3
4
5
6
7

Число информационных
разрядов k
63
62
57
56
51
50
45

Число контрольных
разрядов n-k
0
1
6
7
12
13
18


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

Режим обнаружения ошибок
В этом режиме кодовое расстояние d и максимальное число ошибок t, гарантированно обнаруживаемых на принимающей стороне, связаны зависимостью: t = d - 1 (1)
Вероятность правильного приема кадра Q вычисляется по формуле:
Q = (1 - p)n, (2)
где р - вероятность ошибочного приема одного бита,
n - число разрядов в кадре.
Вероятность ошибочного приема кадра Po можно оценить с помощью приближенной формулы:
13 EMBED Equation.3 1415 (3)
где t - максимальное число обнаруживаемых ошибок.
Формула (3) оценивает вероятность появления ошибок, совпадающих по структуре с комбинациями циклического кода. В таких случаях остаток от деления на генераторный многочлен равен нулю, и ошибки не будут обнаружены.
Вероятность стирания кадра Рs вычисляется по формуле:
Рs = 1 – Q - Po (4)
В таблице 2 приведены параметры исследуемых кодов для режима обнаружения ошибок.
Таблица 2
Номер многочлена
0
1
2
3
4
5
6

Кодовое расстояние
1
2
3
4
5
6
7

Количество обнаруживаемых ошибок
0
1
1,2
1,2,3
1,2,3,4
1,2,3,
4,5
1,2,3,
4,5,6

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

Режим обнаружения и исправления ошибок
После деления принятого кадра на генераторный многочлен принимающая сторона анализирует остаток от деления. Если остаток соответствует одиночной ошибке (или для некоторых кодов - двойной), то ошибка (ошибки) исправляется. При других вариантах остатка происходит стирание кадра (ошибки только обнаруживаются).
Максимальные числа гарантированно исправляемых и обнаруживаемых ошибок связаны с кодовым расстоянием зависимостью:
( + t = d - 1, (5)
где ( - число исправляемых ошибок,
t - число обнаруживаемых ошибок.
Формула (5) справедлива, если выполняется условие: t>(.
В таблице 3 приведены параметры исследуемых кодов в режиме исправления и обнаружения.
Таблица 3
Номер многочлена
0
1
2
3
4
5
6

Число исправляемых ошибок
0
0
0
1
1
1,2
1,2

Число обнаруживаемых ошибок
0
1
2
2
2,3
3
3,4


Например, код, полученный с помощью четвертого многочлена, исправляет одиночную ошибку в кадре, а две или три ошибки будут обнаружены но не исправлены.
Следует отметить, что могут быть обнаружены также ошибки, число которых превышает значение параметра t, так как любое искажение кадра в канале, вызывающее нарушение правила кодирования, всегда будет обнаружено по наличию ненулевого остатка от деления на генераторный многочлен. Многочлены 0,1,2 не позволяют реализовать режим обнаружения и исправления ошибок.
Вероятность правильного приема кадра:
13 EMBED Equation.3 1415 (6)
где ( - максимальное число исправляемых ошибок,
Вероятность ошибочного приема кадра:
13 EMBED Equation.3 1415 (7)
Вероятность стирания кадра:
Рs = 1 – Q - Po (8)

Режим исправления ошибок
В таблице 4 приведены параметры исследуемых кодов в режиме исправления ошибок. Максимальное число исправляемых ошибок определяется как целое из выражения:
( = int((d – 1)/2) (9)
Таблица 4
Номер многочлена
0
1
2
3
4
5
6

Число исправляемых ошибок
0
0
1
1
1,2
1,2
1,2,3


Вероятность правильного приема кадра вычисляется как сумма вероятностей появления не более ( ошибок:
13 EMBED Equation.3 1415, (10)
где ( - максимальное количество исправляемых ошибок.
Вероятность ошибочного приема кадра:
Po = 1 – Q (11)
В режиме исправления ошибок принимающая сторона использует остаток от деления для определения места ошибки (ошибок). Ошибки будут исправлены, если существует однозначное соответствие между остатком и расположением ошибок в кадре.
В действительности такое не всегда выполняется, т.к. число различных остатков обычно меньше числа вариантов ошибок в кадре. Один и тот же остаток может быть как от одиночной ошибки, так и от нескольких ошибок в кадре. Решение об исправлении принимается обычно в пользу варианта одиночной ошибки.
При таком правиле принятия решения возникают ситуации, когда происходит не исправление, а размножение ошибок. Кадр будет принят правильно, если число ошибок в нем не превышает максимального значения (. В других случаях кадр будет принят с размноженными ошибками.
Состояние стирания кадра в данном режиме отсутствует!



Канал с обратной связью

В системе передачи данных с обратной связью источник и приемник информации связаны прямым, и обратным каналами. По прямому каналу передается основная информация, а по обратному - служебная, обеспечивающая заданную надежность передачи данных. Оба канала образуют информационный канал с обратной связью.
Существуют два основных алгоритма, позволяющие источнику установить правильность передачи информации:
эхоконтроль (информационная обратная связь);
автоматический запрос на повторение (решающая обратная связь).
Эхоконтроль используется редко, т.к. требует ретрансляции на передающую сторону принятой информации в полном объеме. Передатчик информации сравнивает каждый переданный кадр с принятым по обратному каналу. При несовпадении кадров передатчик посылает сигнал стирания переданного ранее кадра, затем - повторяет кадр.
Автоматический запрос на повторение предполагает использование обратного канала для передачи небольшого сообщения о состоянии принятого кадра. Передающая сторона отправляет кадр, в который вносится избыточность в соответствии с правилами формирования корректирующего кода (в данном случае циклического кода).
Принимающая сторона выполняет деление принятого кадра на генераторный многочлен кода и анализ остатка от деления. Если остаток равен нулю (в некоторых протоколах определенному числу), то считается, что ошибок в кадре нет. В остальных случаях по обратному каналу отправляется сообщение, которое информирует передатчик о наличии ошибок в принятом кадре.
Каждый правильно принятый кадр может быть подтвержден специальным кадром, либо подтверждение может быть вставлено в управляющее поле информационных кадров, переносящих данные в обратном направлении. Существуют два вида сигналов подтверждения: положительное (АСК) и отрицательное (NACK). Чтобы организовать процедуру передачи информации кадры должны сохраняться в накопителе передающей стороны до получения сигнала подтверждения.
В протоколах предусмотрены три основных способа обработки ответов на положительные и отрицательные подтверждения:
стандартный или передача с остановкой и ожиданием (SAW - Stop And Wait), часто называемый блочным методом передачи;
с возвращением на N кадров (GDB - Go Back N), называемый потоковым методом передачи;
выборочного (селективного) повторения (SR - Selective Repeat), называемый методом с адресным переспросом.
Кратко рассмотрим принцип работы перечисленных способов организации передачи информации с использованием переспроса.

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

Передающая
сторона Время Повторная
ожидания передача

1 2 2 3



ACK NACK ACK ACK




1 2 3

Принимающая сторона Ошибка

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

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

Передающая сторона Повторная передача

1 2 3 4 5 6 7 3 4 5 6 7 8 9



ACK ACK
ACK ACK ACK ACK
NACK ACK
ACK ACK

1 2 ошиб 4 5 6 7 3 4 5 6 7 8
ка
стираемые кадры (h) Принимающая сторона
Рис. 2. Передача кадров согласно процедуре GBN

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

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



Повторная передача
Передающая сторона

1 2 3 4 5 6 7 3 8 9 10 11 12 13




ACK ACK ACK ACK ACK ACK ACK ACK ACK
NACK





1 2 ка 4 5 6 7 3 8 9 10 11

Принимающая сторона

Рис. 3. Передача кадров согласно процедуре SR


Расчет параметров СПД с обратной связью

Процедура SAW.
Для оценки эффективной скорости передачи информации V в канале с обратной связью можно применить формулу:
13 EMBED Equation.3 1415(бит/с), (12)
где к - число информационных разрядов,
n - общее число разрядов в кадре,
Tw - время ожидания сигнала подтверждения ,
B - пропускная способность прямого канала ,
Ps - вероятность обнаружения ошибок в принятом кадре.

Вероятность правильного приема кадра в канале с обратной связью:
13 EMBED Equation.3 1415 , (13)
где Q - вероятность правильного приема кадра в канале без обратной связи,
Ps - вероятность стирания кадра в канале без обратной связи с учетом режима декодирования.

Вероятность ошибочного приема кадра в канале с обратной связью:
13 EMBED Equation.3 1415, (14)
где Ро - вероятность ошибочного приема кадра в канале без обратной связи.
Анализируя формулу (12), можно оценить влияние параметров канала и кадра на скорость передачи. Прежде всего на скорость влияет время ожидания сигнала подтверждения Tw, которое в основном состоит из следующих слагаемых:
времени передачи сигнала обратной связи;
времени распространения сигнала в прямом и обратном направлениях;
времени приема и обработки кадра.
При расчете скорости передачи V следует брать параметры n и к из таблицы 1, принимая во внимание выбранный генераторный многочлен. Вероятность стирания кадра Ps зависит от выбранного многочлена и режима декодирования.
Пропускная способность B в формуле (12) равна количеству битов, которое может передать в секунду прямой канал при отсутствии помех. В расчетах следует брать B = 1200 бит/с.

Процедура GBN.
Помехоустойчивость СПД в этом режиме можно оценить с помощью приведенных выше формул (13) и (14). Однако эффективная скорость передачи информации будет отличаться от скорости передачи в режиме SAW.
Во-первых, передача информации идет непрерывно без ожидания прихода сигнала подтверждения .
Во-вторых, при повторении передается не только кадр, требующий повторения, но и некоторое количество кадров принятых ранее без ошибок.
Если первое увеличивает скорость передачи по сравнению с протоколом SAW, то второе - уменьшает.
Формула для расчета эффективной скорости передачи в режиме GBN имеет вид: 13 EMBED Equation.3 1415, (15)
где h - количество кадров, участвующих при повторной передаче.

Процедура SR.
Вероятности правильного и ошибочного приема кадра можно оценить, используя приведенные выше формулы (13), (14).
Эффективная скорость в канале рассчитывается по формуле:
13 EMBED Equation.3 1415 . (16)
Анализируя формулы (12), (15), (16), можно сделать заключение, что процедура SR обеспечивает при равных условиях наибольшую скорость передачи.

Экспериментальная часть

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

Исследование канала без обратной связи

В канале без обратной связи исследуется зависимость вероятностей правильного Q, ошибочного Po и стертого состояния Ps кадра от выбранного генераторного многочлена циклического кода, режима декодирования и вероятности ошибки в канале p.
Рекомендуется следующая последовательность выполнения работы:
1. Выбрать в меню алгоритм без обратной связи.
2. Установить режим обнаружения ошибок и модельное время 40000c.
3. Выбрать первый генераторный многочлен.
4.Выполнить моделирование при указанных в таблице 5 вероятностях ошибки в канале. Результаты записать в таблицу.
5. Выбрать в меню третий многочлен и выполнить пункт 4.
6. Выбрать в меню пятый многочлен и выполнить пункт 4
7. Установить режим обнаружения и исправления ошибок и выполнить пункты 3,4,5,6.
8. Установить режим исправления ошибок и выполнить пункты 3,4,5,6.
Таблица 5
p
0.016
0.008
0.004
0.002
0.001

Q






Po






Ps







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



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

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

Процедура SAW .
Выбрать в меню процедуру с остановкой и ожиданием (SAW).
Установить режим обнаружения ошибок.
Выбрать первый генераторный многочлен. и установить время ожидания сигнала подтверждения 0.160 с.
Провести исследование работы канала при вероятностях ошибки p, указанных в таблице 6. Результаты моделирования записать в таблицу.
Выбрать третий многочлен и выполнить пункт 4.
Выбрать в меню пятый многочлен и выполнить пункт 4.
Установить режим обнаружения и исправления ошибок и выполнить пункты 3,4,5,6.
Установить время ожидания сигнала подтверждения 0.060с, вероятность ошибки в канале p = 0.008, выбрать любой из многочленов и выполнить моделирование. Записать значение скорости V.
Повторить пункт 8 при времени ожидания сигнала подтверждения 0.320c.
Таблица 6
p
0.016
0.008
0.004
0.002
0.001

Qос






Poс






V







Процедура GBN
1.Установить процедуру передачи с возвратом на N кадров (GBN). Время ожидания сигнала подтверждения выбрать 0.160 c.
2. Выполнить все пункты, начиная с пункта 2, указанные выше при исследовании процедуры SAW.

Процедура SR.
1. Установить в меню режим селективного повторения SR.
2. Выполнить все пункты, начиная с пункта 2, указанные выше при исследовании процедуры SAW.




Требования к отчету по лабораторной работе

Результаты моделирования следует представить в виде таблиц и графиков с необходимыми комментариями. Графики должны отражать следующие зависимости:
Зависимость вероятностей Po, Ps, Q в канале без обратной связи от вероятности ошибки p, выбранного кода, режима декодирования.
Зависимость вероятностей Poc, Qoc в канале с обратной связью от вероятности ошибки p, выбранного кода, режима декодирования.
Зависимость эффективной скорости передачи от алгоритма работы канала (SAW, GBN, SR).
Зависимость скорости передачи от времени ожидания сигнала подтверждения .
При построении графиков рекомендуется применять логарифмический масштаб для вероятностей ошибок (p, Po, Ps, Poc).
Выполнить расчеты СПД по формулам (исходные данные для расчета брать такими же, какие использованы при моделировании). Отметить степень соответствия расчетных и экспериментальных результатов моделирования. Подготовить ответы на контрольные вопросы.

Контрольные вопросы
Каким образом происходит защита информации на канальном уровне?
В чем принципиальное различие алгоритмов SAW, GBN, SR?
Как влияет на вероятности Q, Po, Ps выбор генераторного многочлена циклического кода?
Как влияет на вероятности Q, Po, Ps режим декодирования?
Как влияет на эффективную скорость передачи информации в канале с обратной связью режим декодирования?
Какой из алгоритмов, при одинаковых условиях, обеспечивает наибольшую скорость передачи информации?
Как влияет время ожидания сигнала подтверждения на скорость передачи информации?


Библиографический список
1. Галкин В.А., Григорьев Ю.А. Телекоммуникации и сети: Учеб. Пособие для вузов. М.:МГТУ им. Н.Э.Баумана, 2003.608 с.
2. Лагутенко О.И. Модемы. Справочник пользователя: СП-б.: Лань.,1997.368 с.










13PAGE 15


13PAGE 141115





Приложенные файлы

  • doc 26447983
    Размер файла: 169 kB Загрузок: 0

Добавить комментарий