Коррекция ошибок при передачи данных 10 класс

Слайд 1

Коррекция ошибок при передаче данных

Слайд 2

Символ Двоичный код Кодовое слово 0 1 2 3 4 5 6 7 8 9 Помехоустойчивый код Хемминга основные понятия – кодовое слово

Слайд 3

Символ Двоичный код Кодовое слово 0 0000 0000 1 0001 0001 2 0010 0010 3 0011 0011 4 0100 0100 5 0101 0101 6 0110 0110 7 0111 0111 8 1000 1000 9 1001 1001 Код Хемминга основные понятия – кодовое слово

Слайд 4

Символ Двоичный код Кодовое слово 0 0000 0000 000 1 0001 0001 111 2 0010 0010 110 3 0011 0011 001 4 0100 0100 101 5 0101 0101 010 6 0110 0110 011 7 0111 0111 100 8 1000 1000 011 9 1001 1001 100 Код Хемминга основные понятия – кодовое слово

Слайд 5

Код Хемминга основные понятия – расстояние между двумя словами (количество несовпадений в цифрах) Символ Двоичный код Кодовое слово 0 0000 0000 000 4 1 0001 0001 111 3 2 0010 0010 110 4 3 0011 0011 001 ? 4 0100 0100 101 ? 5 0101 0101 010 3 6 0110 0110 011 ? 7 0111 0111 100 ? 8 1000 1000 011 4 9 1001 1001 100

Слайд 6

Код Хемминга основные понятия – расстояние между двумя словами (количество несовпадений в цифрах) Символ Двоичный код Кодовое слово 0 0000 0000 000 4 1 0001 0001 111 3 2 0010 0010 110 4 3 0011 0011 001 4 4 0100 0100 101 4 5 0101 0101 010 3 6 0110 0110 011 ? 7 0111 0111 100 ? 8 1000 1000 011 4 9 1001 1001 100

Слайд 7

Код Хемминга основные понятия – расстояние между двумя словами (количество несовпадений в цифрах) Символ Двоичный код Кодовое слово 0 0000 0000 000 4 1 0001 0001 111 3 2 0010 0010 110 4 3 0011 0011 001 4 4 0100 0100 101 4 5 0101 0101 010 3 6 0110 0110 011 4 7 0111 0111 100 7 8 1000 1000 011 4 9 1001 1001 100

Слайд 8

АЛГОРИТМ ПОИСКА ПОМЕХ Разделить полученное сообщение на 7-битовые слова 1000011 1001111 0110010 0100101 Сравниваем каждую группу с кодовым словом из кода Хемминга

Слайд 9

1000011 Если полученное слово совпало с кодовым словом в таблице, то сообщение прошло без ошибок Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 10

1001111 Если в таблице есть слово, расстояние от которого до полученного равно 1, то полученное слово заменяется на ближайшее к нему из таблицы Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 11

0110010 Если в таблице есть слова, расстояние от которого до полученного равно 1, то полученное слово заменяется на ближайшее к нему из таблицы Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 12

0100101 Если полученное слово совпало с кодовым словом в таблице, то сообщение прошло без ошибок Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 13

Следовательно, передано сообщение: 8164. Если в таблице есть слова, расстояние от которого до полученного равно 2, тогда слово исправить нельзя.

Слайд 14

Практическая часть Реализуйте программу Hemming в системе программирования на Паскале (смотрите стр. 93 — 96). Выполните описанные тесты. ДОМАШНЕЕ ЗАДАНИЕ. § 1.5.3

Дисциплина: ТЕХНОЛОГИИ ФИЗИЧЕСКОГО УРОВНЯ
ПЕРЕДАЧИ ДАННЫХ

Занятие №10

Методы обнаружения и коррекции ошибок
при передаче информации в компьютерных сетях.

ПЛАН ЗАНЯТИЯ:

1. Обнаружение и коррекция ошибок

2.  Методы обнаружения ошибок

3.  Методы коррекции ошибок

4.  Вопросы

Обнаружение и коррекция ошибок

Надежную  передачу 
информации  обеспечивают  различные  методы.  Основной

принцип работы протоколов, которые
обеспечивают надежность передачи информации —

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

Такие протоколы
основаны на том, что приемник в состоянии распознать факт искажения информации
в принятом кадре информации.

Еще  одним,  более 
эффективным  подходом,  чем  повторная  передача  пакетов,

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

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

Методы обнаружения ошибок

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

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

вероятности о достоверности принятых данных. В
сетях с коммутацией пакетов такой

единицей  информации  может  быть  PDU 
любого  уровня,  для  определенности  будем

считать, что мы контролируем кадры.

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

или  контрольной  последовательностью 
кадра  (Frame  Check  Sequence,  FCS).

Контрольная  сумма 
вычисляется  как  функция  от  основной  информации,  причем не

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

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

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

передающей  стороной,  делает  вывод о  том, 
что  данные  были  переданы  через  сеть

корректно. 

Рассмотрим 
несколько  распространенных  алгоритмов  вычисления  контрольной

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

ошибки в данных.

Контроль по
паритету.

Контроль по
паритету представляет собой наиболее простой метод контроля

данных. В то же время это наименее мощный
алгоритм контроля, так как с его помощью

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

Метод заключается в
суммировании по модулю 2 всех битов контролируемой информации.

Нетрудно  заметить,  что  для  информации, 
состоящей  из  нечетного  числа  единиц,

контрольная сумма всегда равна 1, а при четном
числе единиц — 0. 

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

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

данных, который пересылается вместе с
контролируемой информацией. При искажении в

процессе пересылки любого одного бита исходных
данных (или контрольного разряда)

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

говорит об ошибке. 

Однако  двойная 
ошибка,  например  110101010,  будет  неверно  принята  за

корректные данные.
Поэтому контроль по паритету применяется к небольшим порциям

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

метода  1/8. 

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

избыточности и невысоких диагностических
возможностей.

Вертикальный и
горизонтальный контроль по паритету

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

модификацию  описанного метода. Его отличие
состоит в том, что исходные данные

рассматриваются  в  виде  матрицы,  строки 
которой  составляют  байты  данных.

Контрольный разряд
подсчитывается отдельно для каждой строки и для каждого столбца

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

обладает еще большей избыточностью. На
практике этот метод сейчас также почти не

применяется при передаче информации по сети.

            Циклический избыточный контроль

Циклический
избыточный контроль (Cyclic Redundancy Check, CRC) является в

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

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

жесткие диски). 

Метод основан на
представлении исходных данных в виде одного многоразрядного

двоичного числа. 

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

одно число, состоящее из 8192 бит. Контрольной
информацией считается  остаток от

деления этого числа на известный делитель R.
Обычно в качестве делителя выбирается

семнадцати- или тридцатитрехразрядное число,
чтобы остаток от деления имел длину 16

разрядов (2 байт) или 32 разряда (4 байт).

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

Если остаток от
деления на R равен нулю, то делается вывод об отсутствии ошибок в полученном
кадре, в противном случае кадр считается искаженным.

Этот  метод 
обладает  более  высокой  вычислительной  сложностью,  но  его

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

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

ошибки в нечетном числе битов.

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

Ethernet размером 1024 байт контрольная
информация длиной 4 байт составляет только

0,4 %.

Методы коррекции ошибок

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

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

коррекцией ошибок  —  (Forward Error Correction, FEC).

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

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

разрешенными. Например, контроль по паритету
делает разрешенными только половину

кодов.

Если мы
контролируем три информационных бита, то разрешенными 4-битными

кодами с дополнением до нечетного количества
единиц будут:

000 1,   001 0,   010 0,   011 1,   100
0,   101 1,   110 1,   111 0

То есть всего 8 кодов из 16 возможных.

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

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

разрешенными комбинациями кода. 

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

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

Для схем контроля
по паритету расстояние Хемминга равно 2.

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

Хемминга, равным N, то
такой код будет в состоянии распознавать (N-1)-кратные
ошибки

и исправлять (N-1)/2-кратные
ошибки. 

Так как коды с
контролем по паритету имеют расстояние Хемминга, равное 2, то

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

Коды Хемминга
эффективно обнаруживают и исправляют изолированные ошибки,

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

корректных битов. 

Однако при
появлении длинной последовательности искаженных битов (пульсации

ошибок) коды Хемминга не работают.

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

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

этом  методе  задействуется  решетчатая 
диаграмма,  то  такие  коды  еще  называют

решетчатыми.

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

Методы  прямой  коррекции  ошибок  особенно 
эффективны  для  технологий

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

данных в случае их искажения. 

Вопросы
:

1.  Что называется контрольной
последовательностью кадра?

2.  Что представляет собой контроль по
паритету?

3.  Что  представляет  собой вертикальный  и 
горизонтальный  контроль  по паритету?

4.  Что представляет собой циклический избыточный
контроль?

5.  Что называется прямой коррекцией ошибок?

6.  Что называется расстоянием Хемминга?

7.  Какие коды называются решетчатыми?

8.  Где используются решетчатые коды?

1.

2.

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

3.

Стратегии исправления ошибок.
Упреждающая коррекция ошибок (также прямая коррекция
ошибок, англ. Forward Error Correction, FEC) — техника
помехоустойчивого кодирования и декодирования, позволяющая
исправлять ошибки методом упреждения. Применяется для
исправления сбоев и ошибок при передаче данных путём
передачи избыточной служебной информации, на основе
которой может быть восстановлено первоначальное содержание.
На практике широко используется в сетях передачи данных в
телекоммуникационных технологиях.

4.

Автоматический запрос повторной передачи
Распространены следующие методы автоматического запроса:
Запрос ARQ с остановками (англ. stop-and-wait ARQ)
Передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных
перед тем, как начать передачу следующего. В случае, если блок данных был принят с ошибкой,
приемник передает отрицательное подтверждение и передатчик повторяет передачу блока. Его
недостатком является низкая скорость из-за высоких накладных расходов на ожидание.
Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)
Передача данных от передатчика к приемнику производится одновременно. В случае ошибки
передача возобновляется, начиная с ошибочного блока (то есть передается ошибочный блок и все
последующие). Осуществляется передача только ошибочно принятых блоков данных.

5.

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

6.

По способу работы с данными коды, исправляющие ошибки, бывают:
Блоковые
Делят информацию на фрагменты постоянной длины и обрабатывают каждый
из них в отдельности. Блоковые коды делятся на:
— Линейные коды общего вида (Коды Хэмминга)
— Линейные циклические коды (Коды CRC, Коды БЧХ)
Свёрточные
Работают с данными как с непрерывным потоком.
Кодирование производится с помощью регистра сдвига
Декодирование производится по алгоритму Витерби

7.

Методы защиты информации при передаче
по каналам
Распространены следующие
методысвязи
автоматического запроса:
Криптогра́фия — наука о методах обеспечения конфиденциальности
(невозможности прочтения информации посторонним), целостности данных
(невозможности незаметного изменения информации), аутентификации
(проверки подлинности авторства или иных свойств объекта), шифрования
(кодировка данных).
Известные криптографические методы защиты информации можно разбить
на два класса:
1) Шифрование — обработка информации путем замены и перемещения букв,
при котором объем данных не меняется
2) Кодирование — сжатие информации с помощью замены отдельных
сочетаний букв, слов или фраз.

8.

Требования алгоритмам шифрования
• Высокий уровень защиты данных против дешифрования и возможной
модификации;
• Защищенность информации должна основываться только на знании ключа
и не зависеть от того, известен алгоритм или нет (правило Киркхоффа)
• Малое изменение исходного текста или ключа должно приводить к
значительному изменению шифрованного текста (эффект «обвала»)
• Область значений ключа должна исключать возможность дешифрования
данных путем перебора значений ключа
• Экономичность реализации алгоритма при достаточном быстродействии
• Стоимость дешифрования данных без знания ключа должна превышать
стоимость данных

9.

Современные алгоритмы
шифрования
Симметричное шифрование
Стандарт ГОСТ 28147-89
Стандарт AES
Асимметричное шифрование
Алгоритм RSA

10.

.
Стеганография
Способ передачи или хранения информации с учётом сохранения
в тайне самого факта такой передачи (хранения).
В отличие от криптографии, которая скрывает содержимое
тайного сообщения, стеганография скрывает сам факт его
существования.

11.

.
Классификация стеганографии
Классическая
Компьютерная
Цифровая

12.

.
Классическая стеганография
• Использование симпатических (невидимых) чернил
• Запись на боковой стороне колоды карт, расположенных в условленном
порядке
• Запись внутри варёного яйца
• «Жаргонные шифры», где слова имеют другое обусловленное значение;
• Геометрическая форма — метод, в котором отправитель старается скрыть
ценную информацию, поместив её в сообщение так, чтобы важные слова
расположились в нужных местах или в узлах пересечения геометрического
рисунка
• Семаграммы — секретные сообщения, в которых в качестве шифра
используются различные знаки, за исключением букв и цифр
• Узелки на нитках

13.

.
Компьютерная стеганография
Использование зарезервированных полей компьютерных форматов файлов (часть
поля расширений, не заполненная информацией о расширении, по умолчанию заполняется
нулями. Соответственно мы можем использовать эту «нулевую» часть для записи своих
данных.)
Недостаток: низкая степень скрытности и малый объём передаваемой информации.
Метод скрытия информации в неиспользуемых местах гибких дисков (информация
записывается в неиспользуемые части диска)
Недостатки: маленькая производительность, передача небольших по объёму сообщений.
Метод использования особых свойств полей форматов, которые не отображаются на
экране основан на специальных «невидимых» полях для получения сносок, указателей. К
примеру, написание чёрным шрифтом на чёрном фоне.
Недостатки: маленькая производительность, небольшой объём передаваемой информации.

14.

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

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

Большая часть протоколов канального уровня выполняет только первую задачу —
обнаружение ошибок, считая, что корректировать ошибки, то есть повторно
передавать данные, содержавшие искаженную информацию, должны протоколы верхних
уровней. Так работают такие популярные протоколы локальных сетей, как Ethernet,
Token Ring, FDDI и другие. Однако существуют протоколы канального уровня, например
LLC2 или LAP-B, которые самостоятельно решают задачу восстановления искаженных
или потерянных кадров.

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

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

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

Методы обнаружения ошибок

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

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

Контроль по паритету представляет собой наиболее простой метод контроля данных. В то же
время это наименее мощный алгоритм контроля, так как с его помощью можно
обнаружить только одиночные ошибки в проверяемых данных. Метод заключается в
суммировании по модулю 2 всех бит контролируемой информации. Например, для
данных 100101011 результатом контрольного суммирования будет значение 1.
Результат суммирования также представляет собой один бит данных, который
пересылается вместе с контролируемой информацией. При искажении при пересылке
любого одного бита исходных данных (или контрольного разряда) результат суммирования
будет отличаться от принятого контрольного разряда, что говорит об ошибке.
Однако двойная ошибка, например 110101010, будет неверно принята за корректные
данные. Поэтому контроль по паритету применяется к небольшим порциям данных,
как правило, к каждому байту, что дает коэффициент избыточности для этого
метода 1/8. Метод редко применяется в вычислительных сетях из-за его большой
избыточности и невысоких диагностических способностей.

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

Циклический избыточный контроль (Cyclic Redundancy Check, CRC) является в настоящее время наиболее
популярным методом контроля в вычислительных сетях (и не только в сетях,
например, этот метод широко применяется при записи данных на диски и дискеты).
Метод основан на рассмотрении исходных данных в виде одного многоразрядного
двоичного числа. Например, кадр стандарта Ethernet, состоящий из 1024 байт,
будет рассматриваться как одно число, состоящее из 8192 бит. В качестве
контрольной информации рассматривается остаток от деления этого числа на
известный делитель R. Обычно в качестве делителя выбирается семнадцати- или тридцати
трехразрядное число, чтобы остаток от деления имел длину 16 разрядов (2 байт)
или 32 разряда (4 байт). При получении кадра данных снова вычисляется остаток
от деления на тот же делитель R, но при этом к данным кадра добавляется и
содержащаяся в нем контрольная сумма. Если остаток от деления на R равен нулю¹ (¹ Существуетнесколько
модифицированная процедура вычисления остатка, приводящая к получению в случае
отсутствия ошибок известного ненулевого остатка, что является более надежным
показателем корректности.), то делается вывод об отсутствии ошибок в полученном
кадре, в противном случае кадр считается искаженным.

Этот метод обладает более высокой вычислительной сложностью, но его
диагностические возможности гораздо выше, чем у методов контроля по паритету.
Метод CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном
числе бит. Метод обладает также невысокой степенью избыточности. Например, для
кадра Ethernet размером в 1024 байт контрольная информация длиной в 4 байт
составляет только 0,4 %.

Методы восстановления искаженных и потерянных кадров

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

Существуют два подхода к организации процесса обмена квитанциями: с
простоями и с организацией «окна».

Метод с простоями (Idle Source) требует, чтобы источник, пославший кадр, ожидал получения квитанции
(положительной или отрицательной) от приемника и только после этого посылал
следующий кадр (или повторял искаженный). Если же квитанция не приходит в
течение тайм-аута, то кадр (или квитанция) считается утерянным и его передача
повторяется. На рис. 2.24, а видно, что в этом случае производительность обмена
данными существенно снижается, — хотя передатчик и мог бы послать следующий
кадр сразу же после отправки предыдущего, он обязан ждать прихода квитанции.
Снижение производительности этого метода коррекции особенно заметно на
низкоскоростных каналах связи, то есть в территориальных сетях.

Рис. 2.24. Методы восстановления искаженных и
потерянных кадров

Второй метод называется методом «скользящего окна» (sliding
window). В этом методе для повышения коэффициента использования линии
источнику разрешается передать некоторое количество кадров в непрерывном
режиме, то есть в максимально возможном для источника темпе, без получения на
эти кадры положительных ответных квитанций. (Далее, где это не искажает
существо рассматриваемого вопроса, положительные квитанции для краткости будут
называться просто «квитанциями».) Количество кадров, которые разрешается
передавать таким образом, называется размером окна. Рисунок 2.24, б
иллюстрирует данный метод для окна размером в W кадров.

В начальный момент, когда еще не послано ни одного кадра, окно определяет
диапазон кадров с номерами от 1 до W включительно. Источник начинает передавать
кадры и получать в ответ квитанции. Для простоты предположим, что квитанции
поступают в той же последовательности, что и кадры, которым они соответствуют.
В момент t₁ при получении первой квитанции К1 окно сдвигается
на одну позицию, определяя новый диапазон от 2 до (W+1).

Процессы отправки кадров и получения квитанций идут достаточно независимо
друг от друга. Рассмотрим произвольный момент времени tn, когда источник
получил квитанцию на кадр с номером n. Окно сдвинулось вправо и определило
диапазон разрешенных к передаче кадров от (n+1) до (W+n). Все множество кадров,
выходящих из источника, можно разделить на перечисленные ниже группы (рис.
2.24, б).

• Кадры с номерами от 1 доп. уже были отправлены и квитанции на них
  получены, то есть они находятся за пределами окна слева.
• Кадры, начиная с номера (п+1) и кончая номером
  (W+n), находятся в пределах окна и
  потому могут быть отправлены не дожидаясь прихода какой-либо квитанции.
  Этот диапазон может быть разделен еще на два поддиапазона:
• кадры с номерами от (n+1) до
  т, которые уже отправлены, но квитанции на них еще не получены;
• кадры с номерами от m до
  (W+n), которые пока не отправлены, хотя запрета на это нет.
• Все кадры с номерами, большими или равными
  (W+n+1), находятся за пределами окна
  справа и поэтому пока не могут быть отправлены.

Перемещение окна вдоль последовательности номеров кадров показано на рис.
2.24, в. Здесь t₀ — исходный момент, t₁ и t_n —
моменты прихода квитанций на первый и n-й кадр соответственно. Каждый раз,
когда приходит квитанция, окно сдвигается влево, но его размер при этом не
меняется и остается равным W. Заметим, что хотя в данном примере размер окна в
процессе передачи остается постоянным, в реальных протоколах (например, TCP)
можно встретить варианты данного алгоритма с изменяющимся размером окна.

Итак, при отправке кадра с номером n источнику разрешается передать еще W-1
кадров до получения квитанции на кадр n, так что в сеть последним уйдет кадр с
номером (W+n-1). Если же за это время квитанция на кадр n так и не пришла, то
процесс передачи приостанавливается, и по истечении некоторого тайм-аута кадр n
(или квитанция на него) считается утерянным, и он передается снова.

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

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

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

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

Метод скользящего окна реализован во многих протоколах: LLC2, LAP-B, X.25,
TCP, Novell NCP Burst Mode.

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

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

Выбор тайм-аута зависит не от надежности сети, а от задержек передачи
кадров сетью.

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

Способы обнаружения и устранения ошибок при передачи данных в сетях.

Ошибки
связаны с искажением бит в кадре или с
потерей кадра. Методы обнаружения ошибок
основаны на передаче в составе кадра
избыточной информации (контрольных
разрядов). Кр вычисляются в передатчике
как функция от информационных разрядов(ир).
Приемник повторно вычисляет кр по тому
же алгоритму и при несовпадении с
полученными кр фиксируется ошибка.
Методы вычисления кр: контроль по
паритету(обнаруживает одиночные и
нечетное количество ошибок – контроль
по четности, по нечетности), вертикальный
и горизонтальный контроль по паритету
(обнаруживается большая часть двойных
ошибок, велика избыточность), контрольная
сумма (передатчик дополняет сумму всех
байт кадра до 0 или FF,
приемник суммирует по модулю равному
разрядности контрольного кода, включая
кр, вероятность обнаружения ошибок
99,6%, уменьшается при увеличении разрядности
кода), циклический контроль(исходные
данные предоставляются многоразрядным
двоичным числом в качестве кр берется
остаток от деления этого числа на
известный делитель, при приеме снова
вычисляется остаток от деления на тот
же делитель, но делятся данные кадры с
полученным кр, если остаток = 0, то ошибки
нет, если не =, то ошибка. Обнаруживаются
одиночные, двойные и ошибки в нечетном
числе бит.)

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

IP
адресация: классы сетей, деление на сети
и подсети, маски подсетей.

В
современных сетях для адресации узлов
одновременно используются аппаратные,
числовые и символьные адреса. Пользователи
адресуют комп-ы с символьными адресами,
которые автоматически заменяются в
сообщениях передаваемых по сети на
числовые адреса. После доставки в сеть
назначения вместо числового адреса
используется аппаратный адрес комп-а.
типы адресов: лок адреса- используются
для доставки сообщений в пределах
подсети, IP
адреса – используются для передачи
пакетов между сетями, DNS-имя
– символьные адреса с их помощью
пользователи адресуют комп-ы.

4
класса IP-адресов:
А(1 сеть 10.0.0.0), В(16 сетей 172.16.0.0-172.31.0.0),
С(255 сетей 192.161.0.0-192.161.255.0).

Ограничение
на IP-адреса
узлов и сетей: 1) ни номер сети, ни номер
узла не равны всем двоичным 0 или 1.
2)127.х.х.х – запрещен для узлов и сетей,
т.к. используется для тестирования
программ и взаимодействия процессов в
пределах 1 комп-а 3)групповой адрес не
содержит ни номера сети, ни номера узла.

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

+
: маска позволяет отказаться от класса
адресов, маска используется в
маршрутизаторе, маска позволяет
администратору структурировать сеть,
т.е. делить ее на подсети не требуя от
поставщика услуг доп адреса, поставщики
услуг могут объединять адресное
пространство лс вводя прификсы, уменьшая
объем маршрутизации.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #