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

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

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

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

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

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

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

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

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

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

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

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

Кадры, начиная с номера (п+1) и кончая номером (W+n), находятся в пределах окна и потому могут быть отправлены, не дожидаясь прихода какой-либо квитанции.

Этот диапазон может быть разделен еще на два поддиапазона:

· кадры с номерами от (п+1) до m, которые уже отправлены, но квитанции на них еще не получены;

· кадры с номерами от m до (W+n), которые пока не отправлены, хотя запрета на это нет. Все кадры с номерами, большими или равными (W+n+1), находятся за пределами окна справа и поэтому пока не могут быть отправлены.

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

Компрессия данных

Компрессия (сжатие) данных применяется для сокращения времени их передачи. Так как на компрессию данных передающая сторона тратит дополнительное время, к которому нужно еще прибавить аналогичные затраты времени на декомпрессию этих данных принимающей стороной, то выгоды от сокращения времени на передачу сжатых данных обычно бывают заметны только для низкоскоростных каналов. Для современной аппаратуры этот порог скорости составляет около 64 Кбит/с. Рассмотрим некоторые из общих алгоритмов компрессии данных.

1 Десятичная упаковка. Когда данные состоят только из чисел, значительную экономию можно получить путем уменьшения количества используемых на цифру бит с 7 до 4, используя простое двоичное кодирование десятичных цифр вместо кода ASCII.

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

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

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

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

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

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

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

Например, если при неравномерном кодировании для наиболее часто встречающегося символа «Р» выбран код 1, состоящий из одного бита, то значение 0 однобитного кода будет запрещенным. Иначе мы сможем закодировать только два символа.

Для другого часто встречающегося символа «О» можно использовать код 01, а код 00 оставить как запрещенный.

Тогда для символа «А» можно выбрать код 001, для символа «П» – код 0001 и т. п.

Одним из наиболее распространенных алгоритмов, на основе которых строятся неравномерные коды, является алгоритм Хафмана, позволяющий строить коды автоматически, на основании известных частот символов.

Существуют адаптивные модификации метода Хафмана, которые позволяют строить дерево кодов «на ходу», по мере поступления данных от источника.

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

В таких случаях говорят, что протокол обеспечивает коэффициент сжатия 1:4 или 1:8.

Существуют стандартные протоколы компрессии, например V.42bis, а также большое количество нестандартных, фирменных протоколов.

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