Методы обнаружения ошибок на канальном уровне основаны на - Oshibku.top - решение и исправление самых разных ошибок

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

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

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

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

6.1. Структура типичного кадра компьютерной
сети.

Информация
в локальных сетях предается отдельными
порциями, называемыми в различных
источниках кадрами, пакетами илиблоками. Использование кадров
связано с тем, что в сети одновременно
может происходить несколько сеансов
связи, т.е. в течении одного и того
интервала времени могут идти два или
больше процессов передачи данных между
абонентами. Кадры (пакеты) собственно
и позволяют разделить во времени сеть
между передающими абонентами и уравнять
в правах доступа всех абонентов и
обеспечить для всех абонентов интегральную
скорость передачи информации. Длина
кадра зависит от типа сети и составляет
от 10 байт – до 10 Кбайт. Важно делить
информацию на кадры и для контроля
правильности передачи информации. Кадры
имеют преимущества пред побайтовой
(8бит) или пословной (16 бит и 32 бита)
передачей, т.к. при этом уменьшается
количество служебной информации и
увеличивается полезная загрузка сети.

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

Типичный
кадр содержит в себе следующие основные
поля:

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

Рис. 6.1. Структура пакета

1,2,3,4 —
образуют начальное управляющее поле,
5 — поле данных, 6,7- конечное управляющее
поле.

Передача
кадров на канальном уровне

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

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

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

Рис 6.2 Пример обмена кадрами при сеансе
связи

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

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

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

6.3.Методы гарантии
доставки кадров информации

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

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

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

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

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

Рис.
6.3 Обмен кадрами и квитанциями при методе
с простоями

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

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

Рис.
6.4 Обмен кадрами квитанциями при методе
скользящего окна

На
рис.6.4. показан метод скользящего окна
для окна размером в W кадров. В начальный
момент, когда еще не послано ни одного
кадра, окно определяет диапазон кадров
с номерами от 1 до W включительно. Источник
начинает передавать кадры и получать
в ответ квитанции. Для простоты
предположим, что квитанции поступают
в той же последовательности, что и кадры,
которым они соответствуют. В определенный
момент t1 при получении первой квитанции
окно сдвигается на одну позицию, определяя
новый диапазон от 2 до (W+1). Процессы
отправки кадров и получения квитанций
идут достаточно независимо друг от
друга. Если допустим, что в произвольный
момент времени tn источник получил
квитанцию на кадр с номером n. Окно
сдвинулось вправо и определило диапазон
разрешенных к передаче кадров от (n+1) до
(W+n). Все множество кадров, выходящих из
источника, можно разделить на перечисленные
ниже группы:

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

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

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

кадры с номерами от m до (W+n) , которые
пока не отправлены, хотя запрета на это
нет.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Однако
двойная ошибка, например 110101010, будет
неверно принята за корректные данные.
Поэтому контроль по паритету применяется
к небольшим порциям данных, как правило,
к каждому байту, что дает коэффициент
избыточности для этого метода 1/8. Метод
редко применяется в вычислительных
сетях из-за его большой избыточности и
невысоких диагностических способностей.

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

Рис.
6.5 Метод вертикального и горизонтального
контроля по паритету

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

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

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

Адресация
пакетов.

Каждый
абонент (узел) локальной сети должен
иметь свой уникальный адрес (идентификатор,
МАС-адрес), чтобы ему можно было адресовать
пакеты.

Существуют
две основные системы присвоения адресам
абонентам:

1.При установке сети каждому абоненту
присваивается аппаратно (с помощью
переключателей на плате адаптера) или
программно. При этом количество разрядов
адреса определяется как 2ⁿ>N_max,
где n — количество разрядов адреса;N_max– максимально возможное число абонентов
сети (Например, n=8, еслиN_max=255,
один адрес используется для адресации
пакетов всем абонентам сети –
широковещательной передачи). Реализован
вArcnet.Достоинства:
простота и малый объем служебной
информации в пакете, а также простота
аппаратуры адаптера, распознающей адрес
пакета. Недостаток: трудоемкость задания
адресов и возможность ошибки (например,
двум абонентам сети может быть присвоен
один и тот же адрес).

2. Разработан международной организацией
IEEE, используется в
большинстве сетей. Уникальный сетевой
адрес присваивается каждому адаптеру
сети еще на этапе его изготовления. Был
выбран 48-битный формат адреса, что
соответствует примерно 280триллионам различных адресов. Чтобы
распределить возможные диапазоны
адресов между многочисленными
изготовителями сетевых адаптеров, была
предложена следующая структура адреса,
которая представлена на рис 6.6

Рис. 6.6.Структура 48-битного
стандартного адреса

Младшие 24разряда кода
адреса называютсяOUA(OrganizationallyUniqueAddress) —
организационно уникальный адрес.
Именно их присваивает производитель
сетевого адаптера. Всего возможно
свыше 1б миллионов
комбинаций.

Следующие 22разряда кода
называютсяOUI(OrganizationallyUniqueIdentifier)
— организационно уникальный
идентификатор.IEEEприсваивает один или несколько
OUIкаждому производителю сетевых
адаптеров. Это позволяет исключить
совпадения адресов адаптеров от разных
производителей. Всего возможно свыше
4миллионов разных OUI.Вместе OUAи OUIназываютсяUAA(UniversallyAdministeredAddress)
—универсально управляемый
адресили IEEE-адрес.

Два старших разряда адреса являются
управляющими и определяют тип адреса,
способ интерпретации остальных
46 разрядов.

Старший бит I/G
(Individual/Group)определяет, индивидуальный это адрес
или групповой. Если он установлен в
0,то мы имеем дело с индивидуальным
адресом, если установлен в
1,то с групповым (многопунктовым
или функциональным) адресом. Пакеты
с групповым адресом получают все
имеющие его сетевые адаптеры, причём
групповой адрес определяется всеми
46младшими разрядами.

Второй управляющий бит U/L
(Universal/Local)называется флажком универсального/местного
управления и определяет, как был присвоен
адрес данному сетевому адаптеру. Обычно
он установлен в 0.Установка
бита U/Lв 1означает, что адрес задан не производителем
сетевого адаптера, а организацией,
использующей данную сеть. Это довольно
редкая ситуация.

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

Данной
системы адресов придерживаются, например,
такие популярные сети, как Ethernet,FastEthernet,Token-Ring,FDDI,
100VG-AnyLAN.

Ее
недостатки — высокая сложность аппаратуры
сетевых адаптеров, а также большая
доля служебной информации в передаваемом
пакете (адрес источника и адрес приемника
требуют уже 96 (48+48)битов
пакета, или 12байт).

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

6.6
Методы управления обменом.

6.6.1 Классификация методов управления
обменом.

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

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

Метод
управления -это один из
важнейших параметров сети. Тип метода
управления обменом во многом определяется
особенностями топологии сети.

Методы управления обменом делятся на
две группы:

—
Централизованные методы, при
которых все управление сосредоточенно
в одном месте — центре. Недостатки таких
методов:неустойчивость
к отказам центра, малая гибкость
управления. Достоинство -отсутствие конфликтов.

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

Децентрализованные
методы делятся на:

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

Случайные
методы, которые определяют случайное
чередование передающих абонентов. В
этом случае имеется возможность
конфликтов, но предлагаются способы
их разрешения. Случайные методы
работают хуже, чем детерминированные,
при больших информационных потоках в
сети (при большом графике сети) и не
гарантируют абоненту величину времени
доступа (это интервал между возникновением
желания передавать и получением
возможности передать свой пакет).
Пример случайного метода -стандартный методCSMA/CD(Carrier-SenseMultipleAccesswithCollisionDetection)МНДК/ОК(множественный доступ с контролем
несущей и обнаружением коллизий
(столкновений)).

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

6.6.2 Управление обменом в сети типа
«звезда».

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

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

Управление
обменом централизованное.

Рис. 6.7.Централизованный
метод управления обменом в сетяхтопологией «звезда»

Преимущества:

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

Недостатки:

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

6.6.3.Управление обменом в сети типа
«шина».

Тоже
возможны два решения:

Централизованное
и децентрализованное

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

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

Существует
множество алгоритмов доступа или
сценариев доступа. Рассмотрим некоторые:

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

Децентрализованный временной
приоритетный арбитраж. Основная идея
данного метода состоит в том, чтобы
свести вероятность столкновений к
пренебрежимо малой величине. Предлагается
следующий алгоритм. Сначала все абоненты
следят за состоянием сети. Если она
свободна, то передача начинается сразу
же после возникновения заявки на нее.
Если сеть занята, то сразу же после ее
освобождения все абоненты отсчитывают
свой собственный уникальный временной
интервал, пропорциональный коду сетевого
адреса данного абонента. Таким образом
абонент 0 начинает передачу сразу,
абонент с 1-м адресом через времяt со вторым через время 2tи т.д. Если к концу временного интервала
сеть все еще остается свободной, то
абонент начинает передачу. В противном
случае ждет освобождения сети.

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

Третий метод можно считать развитием
второго и он получил название множественный
доступ с контролем несущей и обнаружением
коллизий (столкновений).(МНДК/ОК
CSMA/CD Carrier-Sense Multiple Access/Collision Detection). Один
из самых популярных, используемый в
сетяхEthernet,FastEthernet. Относится к
децентрализованным случайным (точнее
квазислучайным) методам. Подробнее о
названии метода. В сети работавшей с
1970 года на Гавайских островах, использовался
Радиоканал и установленный на спутнике
ретранслятор – отсюда слово «несущая»
в названии метода. В этой сети был
реализован множественный доступ с
контролем несущей без обнаружения
коллизий. В сетяхEthernet,FastEthernetв
качестве несущей частоты выступает
синхросигнал «подмешиваемый» в
передаваемые данные.

Идея
метода состоит в том , чтобы уравнять в
правах всех абонентов, т.е. чтобы не было
фиксированных приоритетов, и абоненты
не могли надолго заблокировать обмен.
Для этого время задержки вычисляется
каждым абонентом самостоятельно.
Информация передается абонентами
кадрами или пакетами (для МНДК/ОК понятия
кадр и пакет не различаются). Алгоритм
МНДК/ОК можно представить следующим
образом:

Абонент
желающий передавать следит за состоянием
сети (контроль несущей частоты Мачестер
2). Если сеть свободна, то передача
начинается после того, как прошло время,
составляющее межкадровый интервал —
промежуток времени между передаваемыми
пакетами (блок 1, 2).
После
освобождения сети абонент сразу же
начинает передавать и одновременно
после передачи каждого бита контролирует
состояние сети (обнаружение коллизий),
если столкновений не обнаруживается,
то передача доводится до окончания
пакета. В этом случае считается, что
передача прошла успешно.
Если
после передачи какого либо бита
столкновение обнаружено, то передача
пакета прекращается. Абонент усиливает
коллизию передавая 32-битный сигнал
ПРОБКА. Увеличивает значение счетчика
попыток. Максимальное число попыток
не более 16. Если счетчик переполнился,
то считается, сто сеть сильно перегружена,
в ней сильно много коллизий, ситуация
аварийная и обрабатывается на более
высоких уровнях протоколов обмена.
После прекращения неудачной передачи
абонент вычислчет время задержки по
некоторой формуле, где присутствует
генератор случайных чисел. Выдерживает
выбранный промежуток времени и повторяет
попытку(п. 1)
Если
в момент возникновения заявки на
передачу сеть занята, то абонент ждет
освобождения сети.

При
любом случайном методе управления
обменом возникает вопрос о том, какой
должна быть минимальная длительность
пакета, чтобы коллизию обнаружили все
начавшие предавать абоненты. Минимально
допустима длительность пакета в сети
должна составлять Dmin=2L/V,
гдеL– полная длина
сети;V- скорость
распространения сигнала в используемом
кабеле. Это время называют двойным или
круговым временем задержки сигнала в
пути илиPVD(PathDelayValue).Этот временной интервал можно рассматривать
как универсальную меру одновременности
любых событий в сети.

Рис. 6
8 Расчет минимальной длительности пакета

Например,
абонент 1закончил свою
передачу, а абоненты 2и
3захотели передавать во время
передачи абонента 1.После
освобождения сети абонент 3узнает об этом событии и начинает свою
передачу через временной интервал
прохождения сигнала по всей длине сети,
то есть через времяL/V,
а абонент2 начнет передавать сразу после
освобождения сети. Пакет от абонента
3дойдет до абонента 2еще через временной интервал
L/Vпосле начала передачи абонентом
3(обратный путь сигнала). К этому
моменту передача пакета абонентом
2ни в коем случае не должна еще
закончиться, иначе абонент
2так и не узнает столкновении
пакетов (о коллизии).

Отдельно стоит остановиться на том, как
сетевые адаптеры распознают коллизию,
то есть столкновение пакетов. Ведь
простое сравнение передаваемой
абонентом информации с той, которая
реально присутствует в сети, возможно
только в случае самого простого кода
NRZ, используемого
довольно редко. При применении кода
Манчестер-2, который обычно подразумевается
в случае метода управления обменомCSMA/CD,
требуется принципиально другой
подход.

Сигнал
в коде Манчестер-2 всегда имеет постоянную
составляющую, равную половине размаха
сигнала (если один из двух уровней
сигнала нулевой). Однако в случае
столкновения двух и более пакетов
(коллизии) это правило выполняться не
будет. Постоянная составляющая
суммарного сигнала в сети будет
обязательно больше или меньше половины
размаха (рис. 6.9).Ведь
пакеты всегда отличаются друг от друга
и к тому же сдвинуты друг относительно
друга во времени. Именно по выходу уровня
постоянной составляющей за установленные
пределы и определяет каждый сетевой
адаптер наличие коллизии в сети.

Рис
6.9 Определение факта коллизии при
использовании кода Манчестер-2

6.6.4Управление обменом в сети типа
«кольцо».

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

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

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

СМ-
свободный маркер; ЗМ- занятый
маркер;ПМ-занятый маркер с подтверрждением;
ПД – пакет данных

Рис.
Маркерный метод управления обменом

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

Алгоритм
управления предполагает следующую
последовательность действий:

А1,
желающий передать ждет свободный маркер
(пакет, помеченный как свободный).
Получив его А1 помечает его как занятый,
добавляя к нему свой пакет и отправляет
полученный блок следующему по кольцу
абоненту.
Каждый
абонент кольца (А1,А2,А3) получив блок
маркер+пакет проверяет ему ли адресован
пакет и если пакет не его отправляют
дальше по кольцу.
Абонент,
распознавший пакет (пусть это будет
А3) принимает пакет и устанавливает в
маркере бит подтверждение и отправляет
посылку маркер + пакет дальше.
Передававший
абонент (А1) получает обратно свою
посылку освобождает маркер и снова
посылает маркер в сеть.

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

Метод
кольцевых сегментов — слотов. Примером
сети, использующий этот метод может
служитьCambridgeRing.
Основное отличие этого метода от
маркерного состоит в том, что нескольким
абонентам разрешена передача одновременно
и в любой момент. Вместо одного маркера
в сети используются несколько так
называемых слотов (от 2 до 8), которые
выполняют туже функцию, что и маркер.
Эти слоты идут довольно часто, временной
интервал между ними невелик и поэтому
информации между ними может уместиться
немного обычно от 8 до 32 байт. При этом
каждый слот может находится в свободном
или занятом состоянии. Алгоритм включает
в себя следующие этапы:

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

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

Основное
преимущество данных методов перед
CSMA/CDсостоит
в гарантированности времени доступа,
величина которого составляет

, гдеN- число абонентов в
сети;

— время доступа абонент;

— время прохождения пакета по кольцу.

Источник

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

8. МЕТОДЫ ПЕРЕДАЧИ ДАННЫХ КАНАЛЬНОГО УРОВНЯ

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

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

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

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

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

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

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

Контроль по паритету представляет собой наиболее простой метод контроля данных. В то же время это наименее мощный алгоритм контроля, так как с его помощью можно обнаружить только одиночные ошибки в проверяемых данных. Метод заключается в суммировании по модулю 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 %.

Общие принципы построения сетей. Физический уровень передачи данных. Технологии локальных сетей. Стек протоколов TCP/IP , страница 22

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

Лекция 7. Обнаружение и коррекция ошибок. Сжатие данных.

7.1. Способы обнаружения и коррекции ошибок.

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

Методы обнаружения и коррекции ошибок включают в себя следующие составляющие:

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

2. Положительное подтверждение приема.

3. Повторная передача после истечения времени ожидания

4. Отрицательное подтверждение приема и повторная передача.

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

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

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

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

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

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

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

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

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

Будем считать для определенности, что при передаче протокольных единиц данных контролируются кадры. В этом случае контрольную сумму называют контрольной последовательностью кадра. (FCS, Frame Check Sequence). Передатчик отправляет контрольную последовательность кадра как часть PDU. Приемник на своей стороне вычисляет FCS по известному алгоритму и сравнивает с переданной контрольной последовательностью. Если FCS передатчика и приемника совпадают, то принимается решение, что передача данных по сети выполнена корректно.

Основными методами контроля данных (обнаружения ошибок) являются следующие:

— контроль по паритету;
— вертикальный и горизонтальный контроль по паритету;
— контроль контрольной суммой;
— контроль циклическим избыточным кодом.

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

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

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

Пример 5.3. Рассмотрим ситуацию нечетного контроля трех информационных бит. В этом случае кодовые слова будут состоять из 4 бит. Разрешенными кодовыми комбинациями будут следующие:

Пробелом отделен контрольный бит. ?

Пример 5.3 иллюстрирует два факта, верных для произвольного количества информационных бит:

1. При контроле по паритету только половина кодовых комбинаций оказывается разрешенной (8 кодов из 16 возможных).
2. Минимальное расстояние кода d_mm = 2, т.е. возможно только обнаруживать битовые ошибки, по нс исправлять их.

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

Бит паритета «р» (горизонтальный контроль) добавляется к каждому передаваемому символу. Бит паритета вертикального контроля рассчитывается для каждой

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

позиции бита в символе. Вертикальные контрольные биты собираются в отдельный контрольный символ (байт).

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

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

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

Вычисление контрольных сумм является одним из самых простых способов контроля кадров (вероятность определения ошибок достигает 99,9%). При постоянной длине контрольного кода с увеличением количества информационных данных в одной PDU вероятность обнаружения ошибок снижается. Метод контрольных сумм применяется для выявления битовых ошибок.

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

Циклический избыточный контроль (Cyclic Redundancy Check, CRC) является популярным методом обнаружения ошибок в СПД и других задачах, где не требуется исправление пакетных ошибок, например, при записи данных на жесткие и оптические носители.

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

Число бит в кадре может быть достаточно большим. Например, стандартный кадр Ethernet имеет длину 1024 байт, т.с. число будет содержать 8096 бит.

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

При практической реализации CRC значения бит представляются в виде многочленов от некоторой фиксированной переменной х. Коэффициентами многочленов являются двоичные числа, которые соответствуют передаваемым битам. Например, блок данных 10011010 представляется в виде многочлена 7-й степени с коэффициентами 1, 0, 0, 1, 1,0, 1,0 соответственно, т.е. х 7 + х 4 + х 2 + х.

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

Деление также выполняется обычным образом, только операция вычитания заменяется сложением по модулю 2:

В циклических кодах разрешенные комбинации имеют два важных с точки зрения реализации свойства:

1. Для разрешенной комбинации циклический побитовый сдвиг приводит к разрешенной комбинации. Именно этот факт и послужил основой для названия метода.
2. Все разрешенные комбинации (в полиномиальном представлении) делятся без остатка на некоторый полином Р(х).

Полином Р(х) называют образующим или порождающим полиномом. Вид образующего полинома определяется желаемой разрядностью остатка и способностью определять ошибки. Число проверочных бит обычно совпадает со степенью порождающего полинома. Младший и старший биты Р(х) должны быть равны 1. Имеются и другие требования к образующему полиному. Некоторые конкретные порождающие полиномы определены в стандартах международных организаций.

Алгоритм построения циклического кода (кодирование передаваемых данных) имеет следующий вид:

1. Передаваемый ^-битовый блок данных умножается на число 2 Г . Данная операция равносильна умножению полинома D(x), соответствующему А:-битовой последовательности, на полином х г . В результате длина битовой последовательности увеличивается на г разрядов, причем эти последние г разрядов (блок FCS) заполнены нулями.
2. Полученная последовательность бит (как информационных, так и проверочных) делится на образующий многочлен Р(х) с остатком Q(x). Количество разрядов остатка на единицу меньше, чем у Р(х).
3. Полученный остаток Q(x) складывается с полиномом D(x)x r . Данная операция равносильна размещению в битах FCS коэффициентов полинома Q(x). Полученная новая битовая последовательность (кадр) Т(х) = D(x)x r +Q(x) и должна быть передана но сети.

Нетрудно видеть, что передаваемый кадр должен делиться на образующий полином без остатка. Действительно, если некоторое число (делимое) делится на делитель с остатком, то при вычитании остатка из делимого полученный результат будет без остатка делиться на делитель. Если, например, разделить в десятичной системе счисления 210 278 на 10 941, то получится остаток 2 399. Если вычесть полученный остаток из делимого (210278), то результат 207879 будет нацело (т.е. без остатка) делиться на 10941.

Пример 5.4. Рассмотрим передачу блока данных 1011101. Этому блоку соответствует полином D(x) = х 6 + х 4 + х 3 + х 2 + 1. Пусть в качестве образующего полинома выбран Р(х) = х 4 4- х 4- 1, которому соответствует число 10011. Количество проверочных бит совпадает со степенью полинома Р(х), т.е. г = 4, последовательность передаваемых данных будет содержать п = 7 4- 4 = 11 бит.

Выполним умножение полинома D(x) на полином х 4 :

что соответствует битовой последовательности 10111010000.

Произведем деление полинома D(x)x 4 на образующий полином:

Остаток от деления D(x)x x на Р(х) равен Q(x) = х 2 + х, что соответствует числовому значению 110, которое и будет размещено в поле проверочных бит (так как их количество г = 4, то будет размещено число ОНО).

Передаче подлежит кадр, который в виде полинома является суммой Т(х) = = D + Q(x) = х 10 И- х 8 + х 7 + х 6 + х л 4- х 2 4- х, что соответствует числовому значению 10111010110.

Осуществим проверку, выполнив деление Т(х) на Р(х):

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

Рассмотренный метод циклического избыточного контроля обладает большей вычислительной сложностью, нежели контроль но паритету и применение контрольных сумм, но имеет гораздо более высокие диагностические возможности. Кодирование CRC позволяет обнаружить все битовые ошибки, все двойные, ошибки нечетной кратности, а также пакетные ошибки. Вероятность нахождения ошибок оценивается в 99,9984%. Избыточность метода считается невысокой. Например, кадр в 1024 бит может иметь контрольные данные размером в 4 бита, что составляет 0,4%.

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

Источник

Data-link layer uses error control techniques to ensure that frames, i.e. bit streams of data, are transmitted from the source to the destination with a certain extent of accuracy.

Errors

When bits are transmitted over the computer network, they are subject to get corrupted due to interference and network problems. The corrupted bits leads to spurious data being received by the destination and are called errors.

Types of Errors

Errors can be of three types, namely single bit errors, multiple bit errors, and burst errors.

Single bit error − In the received frame, only one bit has been corrupted, i.e. either changed from 0 to 1 or from 1 to 0.
Multiple bits error − In the received frame, more than one bits are corrupted.
Burst error − In the received frame, more than one consecutive bits are corrupted.

Error Control

Error control can be done in two ways

Error detection − Error detection involves checking whether any error has occurred or not. The number of error bits and the type of error does not matter.
Error correction − Error correction involves ascertaining the exact number of bits that has been corrupted and the location of the corrupted bits.

For both error detection and error correction, the sender needs to send some additional bits along with the data bits. The receiver performs necessary checks based upon the additional redundant bits. If it finds that the data is free from errors, it removes the redundant bits before passing the message to the upper layers.

Error Detection Techniques

There are three main techniques for detecting errors in frames: Parity Check, Checksum, and Cyclic Redundancy Check (CRC).

Parity Check

The parity check is done by adding an extra bit, called parity bit to the data to make a number of 1s either even in case of even parity or odd in case of odd parity.

While creating a frame, the sender counts the number of 1s in it and adds the parity bit in the following way

In case of even parity: If a number of 1s is even then parity bit value is 0. If the number of 1s is odd then parity bit value is 1.
In case of odd parity: If a number of 1s is odd then parity bit value is 0. If a number of 1s is even then parity bit value is 1.

On receiving a frame, the receiver counts the number of 1s in it. In case of even parity check, if the count of 1s is even, the frame is accepted, otherwise, it is rejected. A similar rule is adopted for odd parity check.

The parity check is suitable for single bit error detection only.

Checksum

In this error detection scheme, the following procedure is applied

Data is divided into fixed sized frames or segments.
The sender adds the segments using 1’s complement arithmetic to get the sum. It then complements the sum to get the checksum and sends it along with the data frames.
The receiver adds the incoming segments along with the checksum using 1’s complement arithmetic to get the sum and then complements it.
If the result is zero, the received frames are accepted; otherwise, they are discarded.

Cyclic Redundancy Check (CRC)

Cyclic Redundancy Check (CRC) involves binary division of the data bits being sent by a predetermined divisor agreed upon by the communicating system. The divisor is generated using polynomials.

Here, the sender performs binary division of the data segment by the divisor. It then appends the remainder called CRC bits to the end of the data segment. This makes the resulting data unit exactly divisible by the divisor.
The receiver divides the incoming data unit by the divisor. If there is no remainder, the data unit is assumed to be correct and is accepted. Otherwise, it is understood that the data is corrupted and is therefore rejected.

Error Correction Techniques

Error correction techniques find out the exact number of bits that have been corrupted and as well as their locations. There are two principle ways

Backward Error Correction (Retransmission) − If the receiver detects an error in the incoming frame, it requests the sender to retransmit the frame. It is a relatively simple technique. But it can be efficiently used only where retransmitting is not expensive as in fiber optics and the time for retransmission is low relative to the requirements of the application.
Forward Error Correction − If the receiver detects some error in the incoming frame, it executes error-correcting code that generates the actual frame. This saves bandwidth required for retransmission. It is inevitable in real-time systems. However, if there are too many errors, the frames need to be retransmitted.

The four main error correction codes are

Hamming Codes
Binary Convolution Code
Reed – Solomon Code
Low-Density Parity-Check Code

Related Articles
Error control in Data Link Layer
Hamming code for single error correction, double error detection
What is the Error Control in the Data Link Layer?
Framing in Data Link Layer
Network Data Link Layer
Design Issues in Data Link Layer
Flow control in Data Link Layer
Data Link Layer Design Issues
The Data Link Layer Frame and Frame Fields
General Data Link Layer Frame Structure
What is Data Link Layer Switching?
What is the data link layer?
What is a Data Link Layer?
Cisco Discovery Protocol(CDP) and Link Layer Dicovery Protocol(LLDP) in Data Link
Feedback-based flow control in data link layer

Kickstart Your Career

Get certified by completing the course

Get Started

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.1. Структура типичного кадра компьютерной
сети.

Типичный
кадр содержит в себе следующие основные
поля:

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

Рис. 6.1. Структура пакета

1,2,3,4 —
образуют начальное управляющее поле,
5 — поле данных, 6,7- конечное управляющее
поле.

Передача
кадров на канальном уровне

Рис 6.2 Пример обмена кадрами при сеансе
связи

6.3.Методы гарантии
доставки кадров информации

Рис.
6.3 Обмен кадрами и квитанциями при методе
с простоями

Рис.
6.4 Обмен кадрами квитанциями при методе
скользящего окна

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

кадры с номерами от m до (W+n) , которые
пока не отправлены, хотя запрета на это
нет.

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

Рис.
6.5 Метод вертикального и горизонтального
контроля по паритету

Адресация
пакетов.

Существуют
две основные системы присвоения адресам
абонентам:

Рис. 6.6.Структура 48-битного
стандартного адреса

Данной
системы адресов придерживаются, например,
такие популярные сети, как Ethernet,FastEthernet,Token-Ring,FDDI,
100VG-AnyLAN.

6.6
Методы управления обменом.

6.6.1 Классификация методов управления
обменом.

Методы управления обменом делятся на
две группы:

Децентрализованные
методы делятся на:

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

6.6.2 Управление обменом в сети типа
«звезда».

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

Управление
обменом централизованное.

Рис. 6.7.Централизованный
метод управления обменом в сетяхтопологией «звезда»

Преимущества:

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

Недостатки:

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

6.6.3.Управление обменом в сети типа
«шина».

Тоже
возможны два решения:

Централизованное
и децентрализованное

Существует
множество алгоритмов доступа или
сценариев доступа. Рассмотрим некоторые:

Абонент
желающий передавать следит за состоянием
сети (контроль несущей частоты Мачестер
2). Если сеть свободна, то передача
начинается после того, как прошло время,
составляющее межкадровый интервал —
промежуток времени между передаваемыми
пакетами (блок 1, 2).
После
освобождения сети абонент сразу же
начинает передавать и одновременно
после передачи каждого бита контролирует
состояние сети (обнаружение коллизий),
если столкновений не обнаруживается,
то передача доводится до окончания
пакета. В этом случае считается, что
передача прошла успешно.
Если
после передачи какого либо бита
столкновение обнаружено, то передача
пакета прекращается. Абонент усиливает
коллизию передавая 32-битный сигнал
ПРОБКА. Увеличивает значение счетчика
попыток. Максимальное число попыток
не более 16. Если счетчик переполнился,
то считается, сто сеть сильно перегружена,
в ней сильно много коллизий, ситуация
аварийная и обрабатывается на более
высоких уровнях протоколов обмена.
После прекращения неудачной передачи
абонент вычислчет время задержки по
некоторой формуле, где присутствует
генератор случайных чисел. Выдерживает
выбранный промежуток времени и повторяет
попытку(п. 1)
Если
в момент возникновения заявки на
передачу сеть занята, то абонент ждет
освобождения сети.

Рис. 6
8 Расчет минимальной длительности пакета

Рис
6.9 Определение факта коллизии при
использовании кода Манчестер-2

6.6.4Управление обменом в сети типа
«кольцо».

СМ-
свободный маркер; ЗМ- занятый
маркер;ПМ-занятый маркер с подтверрждением;
ПД – пакет данных

Рис.
Маркерный метод управления обменом

Алгоритм
управления предполагает следующую
последовательность действий:

А1,
желающий передать ждет свободный маркер
(пакет, помеченный как свободный).
Получив его А1 помечает его как занятый,
добавляя к нему свой пакет и отправляет
полученный блок следующему по кольцу
абоненту.
Каждый
абонент кольца (А1,А2,А3) получив блок
маркер+пакет проверяет ему ли адресован
пакет и если пакет не его отправляют
дальше по кольцу.
Абонент,
распознавший пакет (пусть это будет
А3) принимает пакет и устанавливает в
маркере бит подтверждение и отправляет
посылку маркер + пакет дальше.
Передававший
абонент (А1) получает обратно свою
посылку освобождает маркер и снова
посылает маркер в сеть.

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

, гдеN- число абонентов в
сети;

— время доступа абонент;

— время прохождения пакета по кольцу.

Обнаружение ошибок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

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

Способы борьбы с ошибками

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

В системах связи возможны несколько стратегий борьбы с ошибками:

обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется в основном на канальном и транспортном уровнях;
обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
исправление ошибок (forward error correction) применяется на физическом уровне.

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

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

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

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

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

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

Блоковые коды

Пусть кодируемая информация делится на фрагменты длиной бит, которые преобразуются в кодовые слова длиной бит. Тогда соответствующий блоковый код обычно обозначают . При этом число ${displaystyle R={frac {k}{n}}}$ называется скоростью кода.

Если исходные бит код оставляет неизменными, и добавляет проверочных, такой код называется систематическим, иначе несистематическим.

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

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

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

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

Линейные коды общего вида

Линейный блоковый код — такой код, что множество его кодовых слов образует -мерное линейное подпространство (назовём его ) в -мерном линейном пространстве, изоморфное пространству -битных векторов.

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

Пусть ${displaystyle C^{perp }}$ — ортогональное подпространство по отношению к , а — матрица, задающая базис этого подпространства. Тогда для любого вектора справедливо:

${displaystyle {overrightarrow {v}}H^{T}={overrightarrow {0}}.}$

Минимальное расстояние и корректирующая способность

Основная статья: Расстояние Хемминга

Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами и называется количество отличных бит на соответствующих позициях, ${displaystyle d_{H}({overrightarrow {u}},;{overrightarrow {v}})=sum _{s}{|u^{(s)}-v^{(s)}|}}$ , что равно числу «единиц» в векторе .

Минимальное расстояние Хемминга ${displaystyle d_{min }=min _{uneq v}d_{H}({overrightarrow {u}},;{overrightarrow {v}})}$ является важной характеристикой линейного блокового кода. Она показывает насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — корректирующую способность:

${displaystyle t=leftlfloor {frac {d_{min }-1}{2}}rightrfloor }$

, округляем «вниз», так чтобы ${displaystyle 2t<d_{min }}$

Корректирующая способность определяет, сколько ошибок передачи кода (типа ) можно гарантированно исправить. То есть вокруг каждого кода имеем -окрестность ${displaystyle A_{t}}$ , которая состоит из всех возможных вариантов передачи кода с числом ошибок () не более . Никакие две окрестности двух любых кодов не пересекаются друг с другом, так как расстояние между кодами (то есть центрами этих окрестностей) всегда больше двух их радиусов ${displaystyle d_{H}(A,;B)geqslant d_{min }>2t}$ .

Таким образом получив искажённый код из ${displaystyle A_{t}}$ декодер принимает решение, что был исходный код , исправляя тем самым не более ошибок.

Поясним на примере. Предположим, что есть два кодовых слова и , расстояние Хемминга между ними равно 3. Если было передано слово , и канал внёс ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову , чем к любому другому, и в частности к . Но если каналом были внесены ошибки в двух битах (в которых отличалось от ) то результат ошибочной передачи окажется ближе к , чем , и декодер примет решение что передавалось слово .

Коды Хемминга

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

${displaystyle {overrightarrow {s}}={overrightarrow {r}}H^{T}}$

, где

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

Общий метод декодирования линейных кодов

Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова ${displaystyle {overrightarrow {r}}_{i}}$ соответствует наиболее вероятное переданное слово ${displaystyle {overrightarrow {u}}_{i}}$ . Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора ${displaystyle {overrightarrow {r}}_{i}}$ вычисляется синдром ${displaystyle {overrightarrow {s}}_{i}={overrightarrow {r}}_{i}H^{T}}$ . Поскольку ${displaystyle {overrightarrow {r}}_{i}={overrightarrow {v}}_{i}+{overrightarrow {e}}_{i}}$ , где ${displaystyle {overrightarrow {v}}_{i}}$ — кодовое слово, а ${displaystyle {overrightarrow {e}}_{i}}$ — вектор ошибки, то ${displaystyle {overrightarrow {s}}_{i}={overrightarrow {e}}_{i}H^{T}}$ . Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

Линейные циклические коды

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

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

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово ${displaystyle {overrightarrow {v}}=(v_{0},;v_{1},;ldots ,;v_{n-1})}$ представляется в виде полинома ${displaystyle v(x)=v_{0}+v_{1}x+ldots +v_{n-1}x^{n-1}}$ . При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на по модулю ${displaystyle x^{n}-1}$ .

В дальнейшем, если не указано иное, мы будем считать, что циклический код является двоичным, то есть ${displaystyle v_{0},;v_{1},;ldots }$ могут принимать значения 0 или 1.

Порождающий (генераторный) полином

Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему полиному . Порождающий полином является делителем ${displaystyle x^{n}-1}$ .

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

Коды CRC

Коды CRC (cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деления ${displaystyle x^{n-k}u(x)}$ на . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид полинома задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

название кода	степень	полином
CRC-12	12	${displaystyle x^{12}+x^{11}+x^{3}+x^{2}+x+1}$
CRC-16	16	${displaystyle x^{16}+x^{15}+x^{2}+1}$
CRC-CCITT	16	${displaystyle x^{16}+x^{12}+x^{5}+1}$
CRC-32	32	${displaystyle x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1}$

Коды БЧХ

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

Математически полинома на множители в поле Галуа.

Коды коррекции ошибок Рида — Соломона

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

Математически коды Рида — Соломона являются кодами БЧХ.

Преимущества и недостатки блоковых кодов

Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.

Свёрточные коды

Файл:ECC NASA standard coder.png

Свёрточный кодер ()

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

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

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

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

Преимущества и недостатки свёрточных кодов

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

Каскадное кодирование. Итеративное декодирование

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

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

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

Оценка эффективности кодов

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

Граница Хемминга и совершенные коды

Основная статья: Граница Хэмминга

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

${displaystyle sum _{i=0}^{t}{n choose i}leqslant 2^{n-k}.}$

Коды, удовлетворяющие этой границе с равенством, называются совершенными. К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида — Соломона) не являются совершенными.

Энергетический выигрыш

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

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

Применение кодов, исправляющих ошибки

Коды, исправляющие ошибки, применяются:

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

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

Автоматический запрос повторной передачи

Системы с автоматическим запросом повторной передачи (ARQ — Automatic Repeat reQuest) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

Запрос ARQ с остановками (stop-and-wait ARQ)

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

Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)

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

Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)

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

См. также

Цифровая связь
Линейный код
Циклический код
Код Боуза — Чоудхури — Хоквингема
Код Рида — Соломона
LDPC
Свёрточный код
Турбо-код

Литература

Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005. — ISBN 5-94836-035-0

Ссылки

Имеется викиучебник по теме:
Обнаружение и исправление ошибок

Помехоустойчивое кодирование (11 ноября 2001). — реферат по проблеме кодирования сообщений с исправлением ошибок. Проверено 25 декабря 2006.

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Обнаружение и исправление ошибок. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.1. Структура типичного кадра компьютерной
сети.

Типичный
кадр содержит в себе следующие основные
поля:

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

Рис. 6.1. Структура пакета

1,2,3,4 —
образуют начальное управляющее поле,
5 — поле данных, 6,7- конечное управляющее
поле.

Передача
кадров на канальном уровне

Рис 6.2 Пример обмена кадрами при сеансе
связи

6.3.Методы гарантии
доставки кадров информации

Рис.
6.3 Обмен кадрами и квитанциями при методе
с простоями

Рис.
6.4 Обмен кадрами квитанциями при методе
скользящего окна

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

кадры с номерами от m до (W+n) , которые
пока не отправлены, хотя запрета на это
нет.

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

Рис.
6.5 Метод вертикального и горизонтального
контроля по паритету

Адресация
пакетов.

Существуют
две основные системы присвоения адресам
абонентам:

Рис. 6.6.Структура 48-битного
стандартного адреса

Данной
системы адресов придерживаются, например,
такие популярные сети, как Ethernet,FastEthernet,Token-Ring,FDDI,
100VG-AnyLAN.

6.6
Методы управления обменом.

6.6.1 Классификация методов управления
обменом.

Методы управления обменом делятся на
две группы:

Децентрализованные
методы делятся на:

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

6.6.2 Управление обменом в сети типа
«звезда».

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

Управление
обменом централизованное.

Рис. 6.7.Централизованный
метод управления обменом в сетяхтопологией «звезда»

Преимущества:

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

Недостатки:

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

6.6.3.Управление обменом в сети типа
«шина».

Тоже
возможны два решения:

Централизованное
и децентрализованное

Существует
множество алгоритмов доступа или
сценариев доступа. Рассмотрим некоторые:

Абонент
желающий передавать следит за состоянием
сети (контроль несущей частоты Мачестер
2). Если сеть свободна, то передача
начинается после того, как прошло время,
составляющее межкадровый интервал —
промежуток времени между передаваемыми
пакетами (блок 1, 2).
После
освобождения сети абонент сразу же
начинает передавать и одновременно
после передачи каждого бита контролирует
состояние сети (обнаружение коллизий),
если столкновений не обнаруживается,
то передача доводится до окончания
пакета. В этом случае считается, что
передача прошла успешно.
Если
после передачи какого либо бита
столкновение обнаружено, то передача
пакета прекращается. Абонент усиливает
коллизию передавая 32-битный сигнал
ПРОБКА. Увеличивает значение счетчика
попыток. Максимальное число попыток
не более 16. Если счетчик переполнился,
то считается, сто сеть сильно перегружена,
в ней сильно много коллизий, ситуация
аварийная и обрабатывается на более
высоких уровнях протоколов обмена.
После прекращения неудачной передачи
абонент вычислчет время задержки по
некоторой формуле, где присутствует
генератор случайных чисел. Выдерживает
выбранный промежуток времени и повторяет
попытку(п. 1)
Если
в момент возникновения заявки на
передачу сеть занята, то абонент ждет
освобождения сети.

Рис. 6
8 Расчет минимальной длительности пакета

Рис
6.9 Определение факта коллизии при
использовании кода Манчестер-2

6.6.4Управление обменом в сети типа
«кольцо».

СМ-
свободный маркер; ЗМ- занятый
маркер;ПМ-занятый маркер с подтверрждением;
ПД – пакет данных

Рис.
Маркерный метод управления обменом

Алгоритм
управления предполагает следующую
последовательность действий:

А1,
желающий передать ждет свободный маркер
(пакет, помеченный как свободный).
Получив его А1 помечает его как занятый,
добавляя к нему свой пакет и отправляет
полученный блок следующему по кольцу
абоненту.
Каждый
абонент кольца (А1,А2,А3) получив блок
маркер+пакет проверяет ему ли адресован
пакет и если пакет не его отправляют
дальше по кольцу.
Абонент,
распознавший пакет (пусть это будет
А3) принимает пакет и устанавливает в
маркере бит подтверждение и отправляет
посылку маркер + пакет дальше.
Передававший
абонент (А1) получает обратно свою
посылку освобождает маркер и снова
посылает маркер в сеть.

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

, гдеN- число абонентов в
сети;

— время доступа абонент;

— время прохождения пакета по кольцу.

Способы борьбы с ошибками

В системах связи возможны несколько стратегий борьбы с ошибками:

обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется в основном на канальном и транспортном уровнях;
обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
исправление ошибок (forward error correction) применяется на физическом уровне.

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

Блоковые коды

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

Линейные коды общего вида

${displaystyle {overrightarrow {v}}H^{T}={overrightarrow {0}}.}$

Минимальное расстояние и корректирующая способность

Основная статья: Расстояние Хемминга

${displaystyle t=leftlfloor {frac {d_{min }-1}{2}}rightrfloor }$

, округляем «вниз», так чтобы ${displaystyle 2t<d_{min }}$

Коды Хемминга

${displaystyle {overrightarrow {s}}={overrightarrow {r}}H^{T}}$

, где

Общий метод декодирования линейных кодов

Линейные циклические коды

Порождающий (генераторный) полином

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

Коды CRC

Таким образом, вид полинома задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

название кода	степень	полином
CRC-12	12	${displaystyle x^{12}+x^{11}+x^{3}+x^{2}+x+1}$
CRC-16	16	${displaystyle x^{16}+x^{15}+x^{2}+1}$
CRC-CCITT	16	${displaystyle x^{16}+x^{12}+x^{5}+1}$
CRC-32	32	${displaystyle x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1}$

Коды БЧХ

Математически полинома на множители в поле Галуа.

Коды коррекции ошибок Рида — Соломона

Математически коды Рида — Соломона являются кодами БЧХ.

Преимущества и недостатки блоковых кодов

Свёрточные коды

Файл:ECC NASA standard coder.png

Свёрточный кодер ()

Преимущества и недостатки свёрточных кодов

Каскадное кодирование. Итеративное декодирование

Оценка эффективности кодов

Граница Хемминга и совершенные коды

Основная статья: Граница Хэмминга

${displaystyle sum _{i=0}^{t}{n choose i}leqslant 2^{n-k}.}$

Энергетический выигрыш

Применение кодов, исправляющих ошибки

Коды, исправляющие ошибки, применяются:

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

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

Автоматический запрос повторной передачи

Запрос ARQ с остановками (stop-and-wait ARQ)

Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)

Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)

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

См. также

Цифровая связь
Линейный код
Циклический код
Код Боуза — Чоудхури — Хоквингема
Код Рида — Соломона
LDPC
Свёрточный код
Турбо-код

Литература

Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005. — ISBN 5-94836-035-0

Ссылки

Имеется викиучебник по теме:
Обнаружение и исправление ошибок

Помехоустойчивое кодирование (11 ноября 2001). — реферат по проблеме кодирования сообщений с исправлением ошибок. Проверено 25 декабря 2006.

Источник

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

Общие принципы построения сетей. Физический уровень передачи данных. Технологии локальных сетей. Стек протоколов TCP/IP , страница 22

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

Errors

Types of Errors

Error Control

Error Detection Techniques

Parity Check

Checksum

Cyclic Redundancy Check (CRC)

Error Correction Techniques

Kickstart Your Career

Способы борьбы с ошибками

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

Блоковые коды

Линейные коды общего вида

Минимальное расстояние и корректирующая способность

Коды Хемминга

Общий метод декодирования линейных кодов

Линейные циклические коды

Порождающий (генераторный) полином

Коды CRC

Коды БЧХ

Коды коррекции ошибок Рида — Соломона

Преимущества и недостатки блоковых кодов

Свёрточные коды

Преимущества и недостатки свёрточных кодов

Каскадное кодирование. Итеративное декодирование

Оценка эффективности кодов

Граница Хемминга и совершенные коды

Энергетический выигрыш

Применение кодов, исправляющих ошибки

Автоматический запрос повторной передачи

Запрос ARQ с остановками (stop-and-wait ARQ)

Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)

Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)

См. также

Литература

Ссылки

Способы борьбы с ошибками

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

Блоковые коды

Линейные коды общего вида

Минимальное расстояние и корректирующая способность

Коды Хемминга

Общий метод декодирования линейных кодов

Линейные циклические коды

Порождающий (генераторный) полином

Коды CRC

Коды БЧХ

Коды коррекции ошибок Рида — Соломона

Преимущества и недостатки блоковых кодов

Свёрточные коды

Преимущества и недостатки свёрточных кодов

Каскадное кодирование. Итеративное декодирование

Оценка эффективности кодов

Граница Хемминга и совершенные коды

Энергетический выигрыш

Применение кодов, исправляющих ошибки

Автоматический запрос повторной передачи

Запрос ARQ с остановками (stop-and-wait ARQ)

Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)

Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)

См. также

Литература

Ссылки

Интересное по теме: