26 какой уровень обеспечивает обнаружение и исправление ошибок

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

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

Большая
часть протоколов канального уровня
выполняет только первую задачу —
обнаружение ошибок, считая, что
корректировать ошибки, то есть повторно
передавать данные, содержавшие искаженную
информацию, должны протоколы верхних
уровней. Так работают такие популярные
протоколы локальных сетей, как 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 %.

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

Соседние файлы в папке РИС гр.446зс 2015

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

Канальный
уровень (Data Link layer)

Проблемы
передачи по каналу.

Сервис,
предоставляемый сетевому уровню

Разбиение на
кадры

Контроль
ошибок.

Управление
потоком.

Доступ к
среде передачи данных

Проблема
предоставления канала

Статическое
предоставление канала

Динамическое
предоставление канала

Протоколы
множественного доступа

Протоколы
множественного доступа с обнаружением несущей

Бесконфликтные
протоколы

Протоколы
с ограниченным числом конфликтов

Протоколы
с множественным доступом и разделением частот

Этот уровень предназначен для обеспечения взаимодействия сетей на физическом
уровне и контроля за ошибками, которые могут возникнуть. Полученные с
физического уровня данные он упаковывает в кадры данных, проверяет на
целостность, если нужно исправляет ошибки и отправляет на сетевой уровень.
Канальный уровень может взаимодействовать с одним или несколькими физическими
уровнями, контролируя и управляя этим взаимодействием. Спецификация IEEE 802
разделяет этот уровень на 2 подуровня — MAC (Media Access Control) регулирует
доступ к разделяемой физической среде, LLC (Logical Link Control) обеспечивает
обслуживание сетевого уровня. На этом уровне работают коммутаторы, мосты.

 Проблемы передачи по каналу.

Сервис, предоставляемый сетевому уровню

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

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

1. Сервис без уведомления и без соединения.
2. Сервис с уведомлением и без соединения.
3. Сервис с уведомлением и с соединением.

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

Разбиение на кадры

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

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

Так как временные методы ненадежны, то применяются другие. Здесь мы
рассмотрим четыре основных:

1. счетчик символов
2. вставка специальных стартовых и конечных символов
3. вставка стартовых и концевых битов
4. нарушение кодировки на физическом уровне

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

Контроль ошибок.

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

Обнаружение и исправление ошибок

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

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

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

Коды обнаруживающие ошибки- CRC код(Cyclic Redundancy
Code)

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

Управление потоком.

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

Доступ к среде передачи
данных

В средах с множественным доступом ключевым является вопрос: как определить
кому из запросивших отдать канал? Протоколы для определения кто захватит канал
в случае конкуренции относятся к подуровню канального уровня, который
называется МАС — Medium Access Control.

Проблема предоставления канала

Основной вопрос — как распределять единственный канал между
многими конкурирующими пользователями.

Статическое предоставление канала

Как мы уже рассматривали ранее есть два основных подхода к
мультиплексированию нескольких конкурирующих пользователей на одном канале — частотное
разделение (FDM-Frequency Division Multiplexing).Частотное
разделение хорошо работает в условиях, когда число пользователей фиксировано и каждый
порождает плотную загрузку канала. Тогда каждому из них выделяется своя полоса
частот, которую он использует независимо от других. Однако, когда число
пользователей велико или величина переменная, или когда трафик очень не
регулярный,у FDM появляются проблемы.

Те же самые рассуждения можно применить к временному разделению (TDM—Time Division Multiplexing). Таким образом, ни один из известных
статических методов не позволяет эффективно распределять нагрузку.

Динамическое предоставление канала

Протоколы множественного доступа

Чистая ALOHA
Идея чистой ALOHA проста — любой пользователь пытается передать сообщение.
Благодаря тому, что в вещательной среде он всегда имеет обратную связь, то он
видит возникновение конфликта при передаче. Эта обратная связь в среде LAN
происходит практически мгновенно, в системах спутниковой связи задержка составляет
около 270 mсек.

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

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

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

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

Также будем предполагать что вероятность k попыток послать как новые, так и
ранее не прошедшие кадры за время кадра распределена по закону Пуассона со
средним  попыток.
Понятно, что .
При слабой загрузке ( приближенно равно нулю) будет не много
передач, а следовательно и коллизий — G приближенно равно . При высокой загрузке . При любой
нагрузке пропускная способность это — число кадров, которые надо передать,
умноженное на вероятность успешной передачи. Если обозначить  — вероятность успешной
передачи, то .

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

Вероятность появления k кадров на передачу при распределении Пуассона равна

поэтому вероятность, что появится 0 кадров равна . За двойное время кадра среднее
число кадров будет , отсюда

,

а так как,
то

.

Рис.3.1 Зависимость производительности канала от
предлагаемого трафика для систем ALOHA

Зависимость между нагрузкой и пропускной способность показана на Рис.3.1. максимальная
пропускная способность достигается при при , что составляет примерно 18%. Результат не
очень вдохновляющий.

Слотированная ALOHA.
В 1972 году Робертс предложил модификацию чистой ALOHA. Все время разделяют на
слоты — один кадр на слот. Ясно, что это требует синхронизации. Одна станция
должна испускать сигнал начала очередного слота. Поскольку передачу теперь
можно начинать не в любой момент, а только по специальному сигналу, то время на
обнаружение коллизии сокращается в двое. Отсюда

.

Как видно из рис. 1 максимум пропускной способности слотированной ALOHA
наступает при ,
где , т.е.
около 0,37, что в двое больше чем у чистой ALOHA.

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

Среднее ожидаемое число повторных передач будет

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

Протоколы множественного доступа с обнаружением несущей

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

Протоколы, которые реализую именно эту идею — определить есть ли передача и
действовать соответствующе, называются протоколами с обнаружением несущей
CSMA (Carrier Sense Multiply Access).

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

Другой вариант CSMA — не настойчивый CSMA протокол. Основное отличие
его от предыдущего в том, что готовая к передаче станция не опрашивает
постоянно канал, в ожидании когда он освободиться, а делает это через случайные
отрезки времени. Это несколько увеличивает задержку при передаче, но общая
эффективность возрастает.

И ,наконец, CSMA настойчивый протокол уровня р. Он
применяется к слотированным каналам. Когда станция готова к передаче она
опрашивает канал, если он свободен, то она с вероятностью р передает свой кадр
и с вероятностью q=1-p ждет следующего слота. Так она действует пока не
передаст кадр. Если произошла коллизия вовремя передачи, она ожидает случайный
интервал времени и опрашивает канал опять. Если при опросе канала он оказался
занят, станция ждет начала следующего слота и весь алгоритм повторяется.
На рисунке показана пропускная способность в зависимости от нагрузки.

CSMA с обнаружением коллизий
Настойчивые и ненастойчивые CSMA протоколы несомненно есть улучшение ALOHA,
т.к. они начинают передачу только проверив состояние канала. Другим улучшением,
которое можно сделать, — станции должны уметь определять коллизии как можно
раньше, а не по окончании отправки кадра. Это экономит время и пропускную
способность канала. Такой протокол, известный как CSMA/CD — Carrier Sense
Multiply Access with Collision Detection , широко используется в локальных
сетях.

 Бесконфликтные протоколы

Bit-Map протокол
Идея этого метода показана на рисунке:

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

Адресный счетчик
В этом методе каждая станция, желающая передать выставляет свой адрес бит за
битом, начиная со старшего разряда. Эти разряды подвергаются логическому
сложению. Если станция выставила на очередном шаге 0, а результат логического
сложения — 1, то она должна ждать и в текущих состязаниях участия не принимает.
Этот метод проиллюстрирован на рисунке левее. Эффективность этого метода d/(d +
log₂N)

Протоколы с ограниченным числом конфликтов

Существую протоколы, объединяющие в себе свойства 2 предыдущих групп. Эти
протоколы называются протоколы с ограниченным числом конфликтов.

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

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

Адаптивный древовидный протокол.

 На рисунке показано как эта процедура протокола применяется к станциями.
Станции — листья. За слот 0 борются все станции. Если какая-то победила —
хорошо. Если нет, то за слот 1 борются только станции поддерева с корнем в
вершине 2. Если какая-то победила, то следующий слот резервируется для станций
поддерева 3. Если был конфликт, то за следующий слот борются станции поддерева
4 и т.д.

Протоколы с множественным доступом и разделением
частот       

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

 

 

Курс лекций по сетевым технологиям. Часть I 1

Уровни модели OSI

Прикладной уровень

   Виды сервиса прикладного уровня

   Функции управления сетями на прикладном уровне

Уровень представления данных

Сеансовый уровень

Транспортный уровень

Сетевой уровень

Канальный уровень

   Контроль ошибок на канальном уровне

   Основные протоколы канального уровня

Физический уровень

Подведем краткие итоги

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

Уровни модели OSI

В настоящее время общепринятой является семиуровневая модель архитектуры открытых
систем (Open System Interconnection). В этой модели рассматриваются:

• Уровень 1. Физический уровень (управление физическим каналом).
• Уровень 2. Канальный уровень (управление информационным каналом).
• Уровень 3. Сетевой уровень (управление сетью).
• Уровень 4. Транспортный уровень (управление передачей).
• Уровень 5. Сеансовый уровень (управление сеансом).
• Уровень 6. Представительный уровень (управление представлением).
• Уровень 7. Прикладной уровень (управление сервисом).

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

Прикладной уровень

В модели OSI прикладная программа, которой нужно выполнить конкретную задачу
(например, обновить базу данных на компьютере В), посылает конкретные данные
в виде дейтаграммы на прикладной уровень. Одна из основных «обязанностей» этого
уровня — определить, как следует обрабатывать запрос прикладной программы, иными
словами — какой вид должен принять данный запрос. Если в запросе прикладной
программы определен, например, дистанционный ввод заданий, то это потребует
работы нескольких программ, которые будут собирать информацию, организовывать
ее, обрабатывать и посылать по соответствующему адресу. Еще одна важная функция
прикладного уровня — электронная почта.

Виды сервиса прикладного уровня

Прикладной уровень содержит несколько так называемых общих элементов прикладного
сервиса (ACSE — Application Common Service Elements) и специальных элементов
прикладного сервиса (SASE — Specific Application Service Elements). Сервисы
ACSE предоставляются прикладным процессам во всех системах. Они включают, например,
требование определенных параметров качества сервиса.

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

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

Специальные элементы прикладного сервиса (SASE) обеспечивают сервис для конкретных
прикладных программ, таких как программы пересылки файлов и эмуляции терминалов.
Если, например, прикладной программе необходимо переслать файлы, то обязательно
будет использован протокол передачи, доступа и управления файлами (FTAM — File
Transfer, Access and Management), являющийся одним из ключевых протоколов прикладного
уровня.

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

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

На разных этапах разработки находятся еще несколько SASE: обработка транзакций
(trunks actions), электронный обмен данными (EDI — Electronic Data Interchange),
передача и обработка заданий (JTM — Job Transfer and Manipulation). Разработка
стандарта OSI на EDI, в частности, очень важна для пользователей ЛВС. Например,
на рабочей станции ЛВС можно составить заказ на покупку и передать эту информацию
по сети непосредственно изготовителю или продавцу, где данные будут автоматически
внесены в счет-фактуру. Можно проверять и автоматически корректировать инвентаризационные
ведомости, можно заключать договора на поставку товаров — и все это без бумаг
и волокиты.

Функции управления сетями на прикладном уровне

По мере усложнения информационных сетей вопрос административного управления
ими приобретает все большее значение. Поскольку сейчас любые системы передачи
информации позволяют обрабатывать и передавать также и речевые данные, а локальные
сети все теснее связываются с глобальными сетями и мэйнфреймами, то все очевиднее
необходимость в разработке эффективного метода организации этой информации и
управления ею. Фирма IBM в качестве решения предложила свои системы NetView
и NetView/PC, a Hewlett-Packard вышла на рынок с пакетом прикладных программ
OpenView.

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

Уровень представления данных

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

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

Важность уровня представления данных заключается в том, что в основу его работы
положена единая для всех уровней модели OSI система обозначений для описания
абстрактного синтаксиса — ASN.1. Эта система служит для описания структуры файлов.
На прикладном уровне система ASN.1 применяется и для выполнения всех операций
пересылки файлов, и при работе с виртуальным терминалом. Использование этой
системы позволяет также решить одну из важнейших проблем, возникающих при управлении
крупными сетями, — проблему шифрования данных. Шифрование данных с помощью ASN.1
можно выполнять на уровне представления данных; разработка стандарта OSI для
этого уровня окажет значительное влияние на обеспечение межмашинной связи.

Сеансовый уровень

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

Сеансовый уровень отвечает за такие серьезные вопросы, как режим передачи и
установка точек синхронизации. Иными словами, на этом уровне определяется, какой
будет передача между двумя прикладными процессами: полудуплексной (процессы
будут передавать и принимать данные по очереди) или дуплексной (процессы будут
передавать и принимать данные одновременно). В полудуплексном режиме сеансовый
уровень выдает тому процессу, который первым начинает передачу, маркер данных.
Когда второму процессу приходит время отвечать, маркер данных передается ему.
Сеансовый уровень, таким образом, разрешает передачу только той стороне, которая
обладает маркером данных.

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

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

Сеансовый уровень, кроме того, отвечает за детали, связанные с упорядоченным
(«плавным») завершением соединения в конце сеанса. Могут возникнуть и ситуации,
когда требуется безусловное («резкое») завершение. Это необходимо в тех случаях,
когда одна из сторон прекращает обмен и отказывается с этого момента принимать
данные.

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

Транспортный уровень

Транспортный уровень имеет большое значение для пользователей компьютерных
сетей, поскольку именно он определяет качество сервиса, которое необходимо обеспечить
посредством сетевого уровня. Для того чтобы лучше понять функции транспортного
уровня, представим его как аналогию набора специальных услуг, которые местное
почтовое отделение предоставляет клиентам за дополнительную плату. Например,
заплатив некоторую сумму, клиент может получить квитанцию о том, что письмо
доставлено по указанному им адресу. Можно заказать срочную доставку, если клиент
желает, чтобы его посылка пришла, к примеру, в Бостон на следующий день. Плату
за эти дополнительные высококачественные услуги почтовое ведомство США взимает
с клиентов деньгами, а для пользователя сети, работающего с OSI-coвместимыми
аппаратными и программными средствами, эта плата выражается в дополнительных
битах, необходимых для предоставления информации о статусе возможных дополнительных
услуг.

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

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

Транспортный уровень, тем не менее, предоставляет программистам возможность
писать программы для прикладного уровня в самых различных сетях, не обращая
внимания на то, надежна ли передача по этим сетям или нет. Некоторые называют
три верхних уровня модели OSI «пользователями транспортного уровня», а четыре
нижних — «поставщиками транспортного уровня».

Существует пять классов сервиса транспортного протокола:

Класс 0, известный как телекс, представляет собой сервис с самым низким качеством.
В этом классе сервиса предусматривается, что управление потоком данных осуществляет
сетевой уровень (под транспортным уровнем). Транспортный уровень разрывает соединение,
когда аналогичную операцию выполняет сетевой уровень. Сервис класса 1 был разработан
CCITT для стандарта Х.25 на сети с коммутацией пакетов. Он обеспечивает передачу
срочных данных, однако управление потоком все равно осуществляется на сетевом
уровне.

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

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

Класс 4 предполагает, что сетевому уровню присуща надежность, поэтому он предлагает
обнаружение и устранение ошибок.

Сетевой уровень

На сетевом уровне осуществляется сетевая маршрутизация. Этот уровень — ключ
к пониманию того, как функционируют шлюзы к мэйнфреймам IBM и другим компьютерным
системам. Протоколы верхних уровней модели OSI выдают запросы на передачу пакетов
из одной компьютерной системы в другую, а задача сетевого уровня состоит в практической
реализации механизма этой передачи.

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

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

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

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

Как уже упоминалось выше, транспортный и сетевой уровни в значительной степени
дублируют друг друга, особенно в плане функций управления потоком данных и контроля
ошибок. Главная причина подобного дублирования заключается в том, что существует
два варианта связи — с установлением соединения (connection-orientied) и без
установления соединения (connectionless). Эти варианты связи базируются на разных
предположениях относительно надежности сети.

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

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

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

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

Канальный уровень

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

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

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

Контроль ошибок на канальном уровне

Для выполнения этой функции на канальном уровне применяется метод автоматического
запроса повторной передачи (ARQ — Automatic Repeat Request). В зависимости от
типа протокола, который работает на канальном уровне, для контроля ошибок используется
одна из трех разновидностей этого метода. ARQ с остановкой и ожиданием — это
метод, при котором компьютер передает кадр информации, а затем ожидает получение
кода подтверждения приема (АСК — acknowledgment), который показывает, что кадр
принят правильно. Если выявлена ошибка, то принимающая станция передаст код
неподтверждения приема (NAK — negative acknowledgment) и передающая станция
повторяет передачу.

При использовании метода непрерывного ARQ с возвратом на N станция принимает
несколько кадров (в зависимости от используемого протокола), а затем отвечает
выдачей АСК или NAK с указанием кадра, который содержит ошибку. Если станция
передала один за другим семь кадров и в четвертом кадре выявлена ошибка, то
передающая станция ответит на NAK повторной передачей кадров с 4-го по 7-й.

Метод непрерывного ARQ с избирательным повторением представляет собой модификацию
предыдущего варианта ARQ. Принимающая станция записывает все получаемые кадры
по порядку в специальный буфер, а затем отвечает, что такой-то кадр (скажем,
номер 4) содержит ошибку. Сохраняя все остальные кадры в буфере, принимающая
станция передает NAK. Передающая станция повторно передает только кадр, содержавший
ошибку (то есть номер 4). Принимающая станция вновь собирает пакеты в нужном
порядке (с 1-го по 7-й) и обрабатывает информацию.

Основные протоколы канального уровня

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

Физический уровень

Физический уровень модели OSI наименее противоречивый, поскольку включает международные
стандарты на аппаратуру, уже вошедшие в обиход. По сути дела, единственная реальная
проблема на этом уровне заключается в том, как ISO собирается учитывать вновь
разрабатываемые стандарты на аппаратуру. Методы передачи данных становятся все
более скоростными, появляются новые интерфейсы с дополнительными функциями контроля
ошибок. В связи с этим возникает вопрос: будут ли добавлены к модели OSI новые
стандарты или же физический уровень останется без изменений? Суд еще не вынес
свой вердикт, поэтому предсказать реакцию ISO сейчас не представляется возможным.

Для физического уровня определен очень подробный список рекомендованных к употреблению
соединителей. Здесь упомянуты, к примеру, 25-контактные разъемы для интерфейсов
RS-232C, 34-контактные разъемы для широкополосных модемов спецификации V.35
CCITT и 15-контактные разъемы для интерфейсов общедоступных сетей передачи данных,
определенных в рекомендациях CCITT Х.20, Х.21, Х.22 и т.д. Кроме того, регламентируются
допустимые электрические характеристики, в частности RS-232C, RS-449, RS-410
и V.35 CCITT.

Физический уровень может обеспечивать как асинхронную (последовательную) передачу,
которая используется для многих персональных компьютеров и в некоторых недорогих
ЛВС, так и синхронный режим, который применяется для некоторых мэйнфреймов и
мини-компьютеров.

Поскольку подкомитеты ISO и IEEE последние несколько лет работают в тесном
контакте, не удивительно, что во многих стандартах на ЛВС используются определения,
предложенные на физическом уровне модели OSI. На базе физического уровня различные
подкомитеты IEEE разрабатывают подробные описания реального физического оборудования,
которое передает сетевую информацию в виде электрических сигналов: требования
к применяемым кабельным системам, разъемам и соединителям.

На физическом уровне модели OSI определяются такие важнейшие компоненты сети,
как тип коаксиального кабеля для одноканальной передачи при скорости 10 Мбит/с.
Сюда включено принятое в стандарте IEEE 802.3 определение более тонкого коаксиального
кабеля cheapenet. К физическому уровню будет добавлено и включенное в стандарт
IEEE 802.3 определение одноканальной передачи данных по кабелю на витых парах
со скоростью 10 Мбит/с.

К средствам, определенным на физическом уровне, также относятся волоконно-оптические
кабели и витые пары, применяемые в самых различных ЛВС. В некоторых сетях, например
стандарта Token Ring Network фирмы IBM, используются неэкранированные витые
пары, а в сетях других типов — экранированные. Упомянутым подкомитетом, кроме
того, были разработаны спецификации различных типов коаксиальных кабелей для
широкополосных ЛВС различных типов.

На физическом уровне модели OSI должна быть определена и схема кодирования,
которой компьютер пользуется для представления двоичных значений с целью их
передачи по каналу связи. В стандарте Ethernet, как и во многих других локальных
сетях, используется манчестерское кодирование. В манчестерском кодировании отрицательное
напряжение в течение первой половины такта передачи с переходом на положительное
напряжение во втором полутакте означает единицу, а положительное напряжение
с переходом на отрицательное — нуль. Таким образом, в каждом такте передачи
имеется переход с отрицательного на положительное напряжение, или наоборот.

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

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

Подведем краткие итоги

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

Стек протоколов — это группа протоколов, упорядоченных в виде уровней для реализации
коммуникационного процесса. Каждый уровень модели OSI имеет собственный связанный
с ним протокол. Если для осуществления процесса коммуникаций необходимо более
одного протокола, то протоколы группируются в стек. Примером стека протоколов
является TCP/IP — стек, широко применяемый в ОС UNIX и в Internet.

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

Для обеспечения взаимодействия двух компьютеров на каждом из них должен выполняться
один и тот же стек протоколов. Каждый уровень стека протоколов на компьютере
взаимодействует со своим эквивалентом на другой машине. Выполняя одинаковый
стек протоколов, компьютеры могут иметь различные операционные системы. Например,
машина DOS, выполняющая стек TCP/IP, может взаимодействовать с ПК Macintosh,
где также функционирует TCP/IP.2

КомпьютерПресс 2’2000

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

Определения

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

История

Современное развитие коды исправления ошибок зачисляется на Ричард Хэмминг в 1947 г.^[1] Описание Код Хэмминга появился в Клод Шеннон с Математическая теория коммуникации^[2] и был быстро обобщен Марсель Дж. Э. Голей.^[3]

Вступление

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

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

Если характеристики канала не могут быть определены или сильно варьируются, схему обнаружения ошибок можно комбинировать с системой для повторных передач ошибочных данных. Это известно как автоматический повторный запрос (ARQ), и наиболее часто используется в Интернете. Альтернативный подход к контролю ошибок: гибридный автоматический запрос на повторение (HARQ), который представляет собой комбинацию ARQ и кодирования с исправлением ошибок.

Виды исправления ошибок

Есть три основных типа исправления ошибок.^[4]

Автоматический повторный запрос (ARQ)

Автоматический повторный запрос (ARQ) — это метод контроля ошибок для передачи данных, который использует коды обнаружения ошибок, сообщения подтверждения и / или отрицательного подтверждения, и таймауты для достижения надежной передачи данных. An подтверждение это сообщение, отправленное получателем, чтобы указать, что он правильно получил кадр данных.

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

Есть три типа протоколов ARQ. Остановка и ожидание ARQ, Go-Back-N ARQ, и Селективный повторный ARQ.

ARQ подходит, если канал связи имеет изменяющийся или неизвестный емкость, например, в Интернете. Однако ARQ требует наличия задний канал, приводит к возможному увеличению задержка из-за повторных передач и требует обслуживания буферов и таймеров для повторных передач, что в случае перегрузка сети может вызвать нагрузку на сервер и общую пропускную способность сети.^[5]

Например, ARQ используется на коротковолновых радиоканалах в виде ARQ-E, или в сочетании с мультиплексированием как ARQ-M.

Прямое исправление ошибок

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

Коды с исправлением ошибок обычно различают между сверточные коды и блочные коды:

• Сверточные коды обрабатываются побитно. Они особенно подходят для аппаратной реализации, а Декодер Витерби позволяет оптимальное декодирование.
• Коды блокировки обрабатываются на блок за блоком основание. Ранние примеры блочных кодов: коды повторения, Коды Хэмминга и многомерные коды проверки на четность. За ними последовал ряд эффективных кодов, Коды Рида – Соломона являются наиболее заметными из-за их широкого распространения в настоящее время. Турбо коды и коды с низкой плотностью проверки четности (LDPC) — относительно новые конструкции, которые могут обеспечить почти оптимальная эффективность.

Теорема Шеннона является важной теоремой для прямого исправления ошибок и описывает максимальную скорость передачи информации при котором возможна надежная связь по каналу с определенной вероятностью ошибки или соотношение сигнал шум (SNR). Этот строгий верхний предел выражается в терминах пропускная способность канала. В частности, теорема утверждает, что существуют такие коды, что с увеличением длины кодирования вероятность ошибки на дискретный канал без памяти можно сделать сколь угодно малым при условии, что кодовая скорость меньше пропускной способности канала. Кодовая скорость определяется как доля к / п из k исходные символы и п закодированные символы.

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

Гибридные схемы

Гибридный ARQ представляет собой комбинацию ARQ и прямого исправления ошибок. Есть два основных подхода:^[5]

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

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

Схемы обнаружения ошибок

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

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

Кодирование минимального расстояния

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

Коды повторения

А код повторения представляет собой схему кодирования, которая повторяет биты по каналу для достижения безошибочной связи. Учитывая поток данных, которые необходимо передать, данные разделяются на блоки битов. Каждый блок передается определенное количество раз. Например, чтобы отправить битовую комбинацию «1011», четырехбитовый блок можно повторить три раза, таким образом получая «1011 1011 1011». Если этот двенадцатибитовый шаблон был получен как «1010 1011 1011» — где первый блок не похож на два других, — произошла ошибка.

Код повторения очень неэффективен и может быть подвержен проблемам, если ошибка возникает в одном и том же месте для каждой группы (например, «1010 1010 1010» в предыдущем примере будет обнаружено как правильное). Преимущество кодов повторения состоит в том, что они чрезвычайно просты и фактически используются в некоторых передачах номера станций.^[6][7]

Бит четности

А бит четности — это бит, который добавляется к группе исходных битов, чтобы гарантировать, что количество установленных битов (то есть битов со значением 1) в результате будет четным или нечетным. Это очень простая схема, которую можно использовать для обнаружения одного или любого другого нечетного числа (т. Е. Трех, пяти и т. Д.) Ошибок в выводе. Четное число перевернутых битов сделает бит четности правильным, даже если данные ошибочны.

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

Контрольная сумма

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

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

Циклическая проверка избыточности

А циклическая проверка избыточности (CRC) небезопасный хеш-функция предназначен для обнаружения случайных изменений цифровых данных в компьютерных сетях. Он не подходит для обнаружения злонамеренно внесенных ошибок. Характеризуется спецификацией порождающий полином, который используется как делитель в полиномиальное деление в столбик через конечное поле, принимая входные данные как дивиденд. В остаток становится результатом.

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

Бит четности можно рассматривать как 1-битную CRC особого случая.

Криптографическая хеш-функция

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

Код исправления ошибок

Для обнаружения ошибок можно использовать любой код исправления ошибок. Код с минимум Расстояние Хэмминга, d, может обнаруживать до d — 1 ошибка в кодовом слове. Использование кодов с коррекцией ошибок на основе минимального расстояния для обнаружения ошибок может быть подходящим, если требуется строгое ограничение на минимальное количество обнаруживаемых ошибок.

Коды с минимальным расстоянием Хэмминга d = 2 являются вырожденными случаями кодов с исправлением ошибок и могут использоваться для обнаружения одиночных ошибок. Бит четности является примером кода обнаружения одиночной ошибки.

Приложения

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

Приложения, в которых передатчик сразу же забывает информацию, как только она отправляется (например, большинство телекамер), не могут использовать ARQ; они должны использовать FEC, потому что при возникновении ошибки исходные данные больше не доступны.

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

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

Техника обеспечения надежности и контроля также использует теорию кодов с исправлением ошибок.^[8]

Интернет

В типичном TCP / IP стек, контроль ошибок выполняется на нескольких уровнях:

• Каждый Кадр Ethernet использует CRC-32 обнаружение ошибок. Кадры с обнаруженными ошибками отбрасываются аппаратурой приемника.
• В IPv4 заголовок содержит контрольная сумма защита содержимого заголовка. Пакеты с неверными контрольными суммами сбрасываются в сети или на приемнике.
• Контрольная сумма не указана в IPv6 заголовок, чтобы минимизировать затраты на обработку в сетевая маршрутизация и потому что текущий уровень связи предполагается, что технология обеспечивает достаточное обнаружение ошибок (см. также RFC 3819 ).
• UDP имеет необязательную контрольную сумму, покрывающую полезную нагрузку и адресную информацию в заголовках UDP и IP. Пакеты с неверными контрольными суммами отбрасываются Сетевой стек. Контрольная сумма не является обязательной для IPv4 и требуется для IPv6. Если этот параметр опущен, предполагается, что уровень канала передачи данных обеспечивает желаемый уровень защиты от ошибок.
• TCP предоставляет контрольную сумму для защиты полезной нагрузки и адресной информации в заголовках TCP и IP. Пакеты с неверными контрольными суммами отбрасываются сетевым стеком и в конечном итоге повторно передаются с использованием ARQ либо явно (например, через тройной удар ) или неявно из-за тайм-аут.

Телекоммуникации в дальнем космосе

Разработка кодов исправления ошибок была тесно связана с историей полетов в дальний космос из-за чрезмерного ослабления мощности сигнала на межпланетных расстояниях и ограниченной доступной мощности на борту космических зондов. В то время как ранние миссии отправляли свои данные в незашифрованном виде, начиная с 1968 года, цифровое исправление ошибок было реализовано в форме (субоптимально декодированные) сверточные коды и Коды Рида – Маллера.^[9] Код Рида-Мюллера хорошо подходил к шуму, которому подвергался космический корабль (приблизительно соответствуя кривая колокола ), и был реализован для космического корабля Mariner и использовался в миссиях с 1969 по 1977 год.

В Вояджер 1 и Вояджер 2 миссии, начатые в 1977 году, были предназначены для доставки цветных изображений и научной информации из Юпитер и Сатурн.^[10] Это привело к повышенным требованиям к кодированию, и, таким образом, космический аппарат поддерживался (оптимально Витерби-декодированный ) сверточные коды, которые могут быть соединенный с внешним Код Голая (24,12,8). Корабль «Вояджер-2» дополнительно поддерживал реализацию Код Рида – Соломона. Конкатенированный код Рида – Соломона – Витерби (RSV) позволил произвести очень мощную коррекцию ошибок и позволил космическому аппарату совершить длительный путь к Уран и Нептун. После модернизации системы ECC в 1989 году оба корабля использовали кодирование V2 RSV.

В Консультативный комитет по системам космических данных в настоящее время рекомендует использовать коды исправления ошибок с производительностью, как минимум, аналогичной коду Voyager 2 RSV. Составные коды все больше теряют популярность в космических миссиях и заменяются более мощными кодами, такими как Турбо коды или же Коды LDPC.

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

Спутниковое вещание

Спрос на спутник транспондер пропускная способность продолжает расти, чему способствует желание предоставлять телевидение (включая новые каналы и телевидение высокой четкости ) и данные IP. Доступность транспондеров и ограничения полосы пропускания ограничили этот рост. Емкость транспондера определяется выбранным модуляция схема и доля мощности, потребляемой ТЭК.

Хранилище данных

Коды обнаружения и исправления ошибок часто используются для повышения надежности носителей данных.^[11] «Трек паритета» присутствовал на первом хранение данных на магнитной ленте в 1951 г. «Оптимальный прямоугольный код», использованный в групповая кодированная запись ленты не только обнаруживают, но и исправляют однобитовые ошибки. Немного форматы файлов, особенно форматы архивов, включить контрольную сумму (чаще всего CRC32 ) для обнаружения повреждения и усечения и может использовать избыточность и / или файлы четности для восстановления частей поврежденных данных. Коды Рида-Соломона используются в компакт-диски для исправления ошибок, вызванных царапинами.

Современные жесткие диски используют коды CRC для обнаружения и коды Рида – Соломона для исправления незначительных ошибок при чтении секторов, а также для восстановления данных из «испорченных» секторов и сохранения этих данных в резервных секторах.^[12] RAID системы используют различные методы исправления ошибок для исправления ошибок, когда жесткий диск полностью выходит из строя. Файловые системы, такие как ZFS или же Btrfs, а также некоторые RAID внедрения, поддержка очистка данных и повторное обновление, которое позволяет обнаруживать и (надеюсь) восстанавливать плохие блоки перед их использованием.^[13] Восстановленные данные могут быть перезаписаны точно в том же физическом месте, чтобы освободить блоки в другом месте на том же оборудовании, или данные могут быть перезаписаны на заменяющее оборудование.

Память с исправлением ошибок

DRAM память может обеспечить более надежную защиту от мягкие ошибки полагаясь на коды исправления ошибок.^[14] Такой исправляющая память, известный как ECC или же EDAC-защищенный память, особенно желательна для критически важных приложений, таких как научные вычисления, финансы, медицина и т. д., а также для приложений дальнего космоса из-за увеличения радиация в космосе.

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

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

Помимо оборудования, обеспечивающего функции, необходимые для работы памяти ECC, операционные системы обычно содержат соответствующие средства отчетности, которые используются для предоставления уведомлений о прозрачном восстановлении мягких ошибок. Увеличение количества мягких ошибок может указывать на то, что DIMM модуль нуждается в замене, и такая обратная связь не была бы легко доступна без соответствующих возможностей отчетности. Одним из примеров является Ядро Linux с EDAC подсистема (ранее известная как Bluesmoke), который собирает данные от компонентов компьютерной системы с включенной функцией проверки ошибок; Помимо сбора и отправки отчетов о событиях, связанных с памятью ECC, он также поддерживает другие ошибки контрольной суммы, в том числе обнаруженные на Шина PCI.^[16][17][18]

Некоторые системы также поддерживают очистка памяти.

Смотрите также

• Код Бергера
• Пакетный код исправления ошибок
• Плевать будильник
• Память ECC, тип компьютерного хранилища данных
• Запрещенный ввод
• Адаптация ссылки
• Список алгоритмов обнаружения и исправления ошибок
• Список кодов исправления ошибок
• Список хеш-функций
• Надежность (компьютерные сети)

Рекомендации

дальнейшее чтение

• Шу Линь; Дэниел Дж. Костелло-младший (1983). Кодирование с контролем ошибок: основы и приложения. Prentice Hall. ISBN  0-13-283796-X.

внешняя ссылка

• Он-лайн учебник: теория информации, выводы и алгоритмы обучения, к Дэвид Дж. К. Маккей, содержит главы, посвященные элементарным кодам, исправляющим ошибки; о теоретических пределах исправления ошибок; и на последних современных кодах исправления ошибок, в том числе коды с низкой плотностью проверки четности, турбокоды, и коды фонтанов.
• Вычислить параметры линейных кодов — интерактивный интерфейс для генерации и вычисления параметров (например, минимальное расстояние, радиус покрытия ) из линейные коды исправления ошибок.
• Страница ECC
• SoftECC: система проверки целостности программной памяти
• Настраиваемая программная библиотека обнаружения и исправления ошибок DRAM для HPC
• Обнаружение и исправление скрытых искажений данных для крупномасштабных высокопроизводительных вычислений