Nets2010 (1131259), страница 22

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

Текст из файла (страница 22)

Рисунок 3-11. Протокол с подтверждением и восстановлением

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

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

В разных средах характер ошибок разный. Ошибки могут быть одиночные, а могут возникать группами, сразу по несколько штук. У групповых ошибок есть свои достоинства и недостатки. Достоинство заключается в следующем. Пусть данные передаются блоками по 1000 бит, а частота ошибки - 10^-3 на бит, т.е. одна на каждые 1000 бит.

Если ошибки изолированные и независимые, то практически каждый блок в среднем будет содержать ошибку. Если же они возникают группами по 100 сразу, то ошибки будут содержать в среднем 1-2 блока из каждых 100. Недостатком групповых ошибок является то, что их труднее обнаруживать и исправлять, чем одиночные.

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

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

Пусть данные занимают m разрядов, и мы добавляем r избыточных, контрольных разрядов. Нам необходимо передать слово длины n = m+r, которое называют n-битовым кодословом. Пусть у нас есть два кодослова - 10001001 и 10110001. С помощью операции EXCLUSIVE OR легко определить число различных разрядов в двух кодословах. В данном случае таких разрядов 3. Количество разных битов в двух кодословах называется расстоянием Хемминга между этими словами. Поэтому, если два кодослова находятся на расстоянии d по Хеммингу, это значит, что надо преобразовать ровно d разрядов, чтобы преобразовать одно кодослово в другое.

В силу того, что избыточные контрольные разряды могут принимать только вполне определенные значения, то не все 2ⁿ кодовых слов возможны. Зная алгоритм установки контрольных разрядов, мы можем вычислить минимальное расстояние по Хеммингу между двумя правильными кодословами.

Способен код исправлять ошибки или только обнаруживать их - зависит от расстояния между кодословами по Хеммингу. Если мы хотим обнаруживать d ошибок, то необходимо, чтобы два кодослова отстояли друг от друга на расстоянии d+1. Тогда, если принятый код отстоит на расстоянии k<d, то принятое кодослово содержит k ошибок. Если мы хотим исправлять d ошибок, то нужно, чтобы кодослова отстояли друг от друга на 2d+1. Поэтому, даже если переданное кодослово содержит d ошибок, оно все равно ближе к правильному кодослову, чем к какому-либо еще, и, таким образом, можно определить исходное слово.

Простым примером кода с обнаружением одной ошибки является код с битом четности. Конструкция его такова: к исходному кодослову добавляется бит четности. Если число единиц в исходном кодослове четно, то значение этого бита - 0. Если нечетно, то - 1. Кодослова с битом четности имеют расстояние Хемминга 2, так как любая ошибка в одном бите породит ошибку четности. Однако, если возможны двойные ошибки, то бит четности проблему не решит.

Для примера кода с исправлением ошибки рассмотрим код, у которого есть только четыре правильных кодослова: 0000000000, 0000011111, 1111100000, 1111111111. Расстояние по Хеммингу у этого кода 5, следовательно, он может исправлять двойные ошибки. Если получатель получит слово 0000000111, то ясно, что исходное слово имело вид 0000011111. Однако, если допустимы тройные ошибки, то 0000000111 может означать 0000000000.

Оценим минимальное количество контрольных разрядов, необходимое для исправления одиночных ошибок. Пусть у нас есть код из m бит сообщения и r контрольных бит. Каждое из 2ⁿ правильных сообщений имеет n неправильных кодослов на расстоянии 1. Таким образом, с каждым из 2^m кодослов связано n+1 кодослов. Так как общее число кодослов - 2ⁿ, то (n+1)2^m≤2, учитывая, что n=m+r, получаем: (m+r+1) ≤ 2^r

Для заданного m эта формула задает минимальное число контрольных разрядов, необходимых для исправления единичных ошибок. Этот теоретический предел достижим при использовании метода, предложенного Хеммингом. Идея его в следующем:

• Разряды кодослова нумеруются слева направо, начиная с 1.

• Все биты, номера которых являются степенью 2 (1, 2, 4, 8, 16 и т.д.) - контрольные, остальные - биты сообщения.

• Каждый контрольный бит отвечает за четность группы битов, включая себя. Чтобы определить группу битов, за четность которой отвечает определенный контрольный бит, нужно представить номер позиции каждого бита по степеням двойки. Те биты, в номера которых входит степень двойки, равная номеру контрольного бита, и есть искомая группа. Например, 11=1+2+8, 39=1+2+4+32. Таким образом, бит в позиции 11 входит в группу, контролируемую битом в позиции 2.

Получив кодослово, получатель устанавливает специальный счетчик в ноль. Затем он проверят каждый контрольный бит на предмет правильности четности. Если четность нарушена, то порядковый номер этого бита заносится в счетчик. Если после этой проверки счетчик на нуле, то все в порядке. Если нет, то он содержит номер неправильного разряда. Например, если 1, 2, 8 - ошибочные контрольные разряды, то ошибка содержится в 11-м разряде, так как только он связан одновременно с этими контрольными разрядами.

Код Хемминга может исправлять только одиночные ошибки. Однако есть прием, который позволяет распространить идеи Хемминга на случай групповых ошибок. Пусть нам надо передать k кодослов. Расположим их в виде матрицы: одно слово - строка. Обычно передают слово за словом. Но мы поступим иначе, передадим слово длины k из первых разрядов всех слов, затем - вторых, и т.д. После приема всех слов матрица восстанавливается. Если мы хотим обнаруживать групповые ошибки размера k, то в каждой строке восстановленной матрицы будет не более одной ошибки. А с одиночными ошибками код Хемминга справится.

Коды с обнаружением ошибок.

Рассмотрение кодов, обнаруживающих ошибки, начнем с небольшого примера. Пусть у нас есть канал с одиночными ошибками с частотой 10^-6 на бит. Если мы хотим исправлять единичные ошибки при передаче блока в 1000 бит, то нам потребуется 10 контрольных бит ((m+r+1) ≤ 2^rr, где m =1000; (1001+r) ≤ 2^rr, следовательно, r = 10).

При передаче 1 Мбит данных потребуется 10 000 контрольных бит. В то же время для обнаружения единичной ошибки достаточно одного бита четности. Поэтому, если мы применим технику повторной передачи, то на передачу 1000 блоков надо будет потратить 1001 бит дополнительно или с повторной передачей 2002 бит, вместо 10000 бит в случае кода с исправлением ошибки.

Применение техники четности «в лоб» в случае групповых ошибок не даст нужного результата. Однако ее можно скорректировать. Пусть нам требуется передать n слов по k бит. Расположим их в виде матрицы n х k. Для каждого столбца вычислим бит четности и разместим его в дополнительной строке. Матрица затем передается по строкам. При получении матрица восстанавливается, и если хоть один бит нарушен, то весь блок передается повторно.

Этот метод позволяет обнаружить групповые ошибки длины n. Против групповых ошибок длины n+1 он бессилен. В общем случае вероятность правильной передачи при длине групповой ошибки n равна 2^-n. Поэтому на практике применяют другую технику, которая называется циклическим избыточным кодом (Cyclic Redundancy Code), или CRC-кодом.

CRC-коды построены на рассмотрении битовой строки как строки коэффициентов полинома. Битовую строку длины k рассматривают как коэффициенты полинома степени k-1. Самый левый бит строки - коэффициент при старшей степени. Например, строка 110001 представляет полином x⁵+x⁴+x⁰.

Использование полиномиальных кодов при передаче заключается в следующем. Отправитель и получатель заранее договариваются о конкретном генераторе полиномов G(x), у которых коэффициенты при старшем члене и при младшем члене должны быть равны 1. Пусть степень G(x) равна r. Для вычисления контрольной суммы блока из m бит должно быть r<m. Идея состоит в том, чтобы добавить контрольную сумму к передаваемому блоку, рассматриваемому как полином М(х), так, чтобы передаваемый блок с контрольной суммой был кратен G(x). Когда получатель получает блок с контрольной суммой, он делит его на G(x). Если есть остаток, то были ошибки при передаче. Полиномиальная арифметика выполняется по модулю 2. Сложение и вычитание происходит без переноса разрядов. Таким образом, обе эти операции эквивалентны EXCLUSIVE OR. Деление выполняется, как обычно в двоичной системе, с той лишь разницей, что вычитание выполняется по модулю два.

Алгоритм вычисления контрольной суммы:

Здесь r - степень G(x).

1. Добавить r нулей в конец блока так, что он содержал m+r разрядов и соответствовал полиному x^r M(x).

2. Разделить по модулю 2 полином x^r M(x) на G(x).

3. Вычесть остаток (длина которого всегда не более r разрядов) из строки, соответствующей x^r M(x), по модулю 2. Результат и есть блок с контрольной суммой (назовем его Т(х)).

Рисунок 3-7 показывает этот алгоритм для блока 1101011011 и G(x) = х⁴+х+1.

Рисунок 3-7. Расчет контрольной суммы для полиномиального кода

Данный метод позволяет обнаруживать одиночные ошибки. Групповые ошибки длины не более r. Нечетное число отдельных ошибок. Существует три международных стандарта на вид G(x):

• CRC-12 = x¹²+x¹¹+x³+x²+x+1

• CRC-16 = x¹⁶+x¹⁵+x²+1

• CRC-CCITT = x¹⁶+x¹²+x⁵+1

CRC-12 используется для передачи символов из 6 разрядов. Два остальных - для 8-разрядных. CRC-16 и CRC-CCITT ловят одиночные, двойные ошибки, групповые ошибки длины не более 16 и нечетное число изолированных ошибок с вероятностью 99,997%.

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

Для передачи в обоих направлениях можно потребовать на физическом уровне двух симплексных каналов. Один для передачи кадров, другой - для передачи подтверждений. Однако использование канала только для подтверждений - довольно дорогое удовольствие. Можно смешивать кадры с данными и кадры с подтверждениями на одном канале. Это, конечно. решение проблемы, но по-прежнему на подтверждения будет тратиться полезная пропускная способность канала.

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

Однако применение этой идеи усложняет протокол. Что делать, если тайм-аут у отправителя на получения подтверждения заканчивается, а с сетевого уровня получателя не поступает запроса на передачу пакета? Поэтому на канальном уровне должен быть фиксированный интервал времени, в течение которого канальный уровень ждет от сетевого попутного кадра. Если до истечения этого срока пакет с сетевого уровня не поступил, то канальный уровень отправляет подтверждение отдельным кадром.

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

Мы уже сталкивались с подобными протоколами (старт-стопный протокол). В них n было равно 1. Обычно n=2^k-1. У получателя и отправителя есть набор последовательных чисел - номеров кадров, которые отправитель может отправить, не ожидая подтверждения каждого. Эти кадры образуют окно отправки. Аналогично, у получателя есть буфер для получения и временного хранения получаемых кадров - окно получения.

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

Характеристики

Список файлов ответов (шпаргалок)