Полный курс лекций 2009-го года (1130357), страница 35

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

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

Кроме этого, на стороне отправителя надо былопросматривать кадр, чтобы обнаружить недопустимые последовательности.Был предложен иной прием, позволяющий использовать любое число битов на символ и любуюкодировку. Его идея состоит в том, что каждый кадр начинается и заканчивается специальным флагбайтом: 01111110. Чтобы избежать аналогичной последовательности, внутри кадра поступают следующимобразом.

Посылающая сторона, встретив последовательно 5 единиц, обязательно вставит 0. Принимающаясторона, приняв 5 последовательных единиц, обязательно удалит следующий за ними 0. Таким образом,если в передаваемых данных встретится конфигурация флаг-байта, то она будет преобразована вконфигурацию 011111010. Этот метод иллюстрирует рисунок 3-5. Этот метод прозрачен для сетевогоуровня так же, как и метод вставки байтов.Рисунок 3-5. Замена шестой единицы нулемТаким образом, кадр легко может быть распознан по флаг-байту.

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

Например, пусть для передачи одного бита используется два импульса. «1»кодируется как переход «высокое-низкое», «0» - как переход «низкое-высокое». Сочетания «низкоенизкое» или «высокое-высокое» не используются для передачи данных. Их и используют для границкадра. Так делают в стандарте IEEE 802 для ЛВС, который мы рассмотрим позже.На практике используют, как правило, комбинацию этих методов. Например, счетчик символов содним из выше перечисленных.

Тогда, если число символов в кадре совпадает с кодировкой границыкадра, кадр считается переданным правильно.3.1.3. Обнаружение ошибокРешив проблему разбиения на кадры, мы приходим к следующей проблеме: как обеспечить, чтобыкадры попадали на сетевой уровень в надлежащей последовательности? Если для отправляющей сторонывсе равно, в какой последовательности поступают кадры, то этой проблемы нет. Например, если намнужен сервис без уведомления и без соединения.

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

Как быть? Для решения этой проблемы каждому кадру присваиваютпорядковый номер. С помощью этого номера получатель может обнаружить дубли.Итак, таймеры и нумерация кадров - основные средства на канальном уровне, обеспечивающиедоставку каждого кадра до сетевого уровня в единственном экземпляре и в нужном порядке.3.1.4. Управление потокомДругая важная проблема, которую надо решать на канальном уровне - управление потоком.

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

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

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

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

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

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

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

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

Однако, если допустимы тройныеошибки, то 0000000111 может означать 0000000000.Оценим минимальное количество контрольных разрядов, необходимое для исправления одиночныхошибок. Пусть у нас есть код из m бит сообщения и r контрольных бит. Каждое из 2n правильныхсообщений имеет n неправильных кодослов на расстоянии 1. Таким образом, с каждым из 2m кодословсвязано n + 1 кодослов. Так как общее число кодослов - 2n, то (n + 1) 2m £ 2, учитывая, что n = m + r,получаем:(m + r + 1) £ 2rДля заданного m эта формула задает минимальное число контрольных разрядов, необходимых дляисправления единичных ошибок. Этот теоретический предел достижим при использовании метода,предложенного Хеммингом.

Идея его в следующем:§Разряды кодослова нумеруются слева направо, начиная с 1.§Все биты, номера которых являются степенью 2 (1, 2, 4, 8, 16 и т.д.) - контрольные, остальные - битысообщения.§Каждый контрольный бит отвечает за четность группы битов, включая себя. Чтобы определить группубитов, за четность которой отвечает определенный контрольный бит, нужно представить номер позициикаждого бита по степеням двойки.

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

Список файлов лекций