1 (1131253), страница 20

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Билет № 22.

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

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

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

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

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

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

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

Рисунок 3-12 показывает работу такого протокола для n=1 в форме диаграммы.

Рисунок 3-12. Протокол скользящего окна

Протокол скользящего окна в 1 бит.

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

На рисунке 3-13 показан текст протокола для этого простейшего случая. Как и все, он начинается с определения переменных. Next_frame_to_send указывает, какой кадр посылается. Переменная frame_expected определяет, какой кадр получатель ожидает. Есть только два значения - 0 или 1.

Рисунок 3-13. Протокол скользящего окна в 1 бит

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

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

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

На рисунке 3-14 показан протокол 4. Если у А очень короткий тайм-аут, то все дубликаты кадра пойдут с одним и тем же значением полей seq и ask. Поэтому, получив исправный кадр, В установит значение переменной frame_expected равным 1 и пошлет подтверждение. Все последующие дубликаты будут им отвергнуты, так как он будет ожидать кадра с 1, а не 0.

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

Рисунок 3-14. Два сценария для протокола 4

Протокол с возвратом на n кадров и протокол с выборочным повтором.

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

Эта проблема есть следствие правила, по которому отправитель ждет подтверждения прежде, чем пошлет следующий кадр. Это требование можно ослабить - разрешить отправителю отправлять до w кадров, не дожидаясь их подтверждения. Надлежащим выбором значения w отправитель может заполнить все время, необходимое на отправку кадра и получение его подтверждения. В вышеприведенном примере w должно быть равным, по крайней мере, 26. Это то количество кадров, какое отправитель успеет отправить за 520 мсек., прежде чем придет подтверждение на кадр 0. Таким образом, неподтвержденными будут 25 из 26 кадров, размер окна отправителя будет равным 26 кадров.

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

Есть два приема для решения этих вопросов: откат и выборочный повтор. При откате все кадры, поступившие после поврежденного кадра, сбрасываются и не подтверждаются. Отправитель по тайм-ауту повторно отправляет все кадры, начиная с первого неподтвержденного кадра. Этот подход показан на рисунке 3-15 (а), где размер окна у получателя - 1.

Рисунок 3-15. Влияние ошибки при окне размером 1 (a) и окне большого размера (b)

При выборочном повторе у получателя длина окна такая же, как и у отправителя. Отправитель отмечает неподтвержденный кадр и посылает его еще раз. Получатель не передает на сетевой уровень последовательность пакетов, если в ней есть разрывы (рисунок 3-15 (b)).

Билет № 23.

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

Протокол HDLC (High Level Data Link Control).

Познакомимся с группой давно известных, но по-прежнему широко используемых на практике протоколов. Все они имеют одного предшественника - SDLC (Synchronous Data Link Control) - протокола управления синхронным каналом, предложенного фирмой IBM в рамках архитектуры SNA. ISO модифицировало этот протокол и выпустило под название HDLC - High level Data Link Control. МКТТ модифицировало HDLC для X.25 и выпустило под именем LAP - Link Access Procedure. Позднее он был модифицирован в LAPB.

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

Рисунок 3-16. Типовая структура кадра протокола HDLC

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

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

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

• Поле Checksum - это поле используется для передачи CRC-кода.

Флаговые последовательности 01111110 используются для разделения кадров и постоянно передаются по незанятой линии в ожидании кадра. Существует три вида кадров: Information, Supervisory, Unnumbered. Организация поля Control для этих трех видов кадров показана на рисунке 3-17. Как видно из размера поля Seq, в окне отправителя может находиться до 7 неподтвержденных кадров. Поле Next используется для отправки подтверждения вместе с передаваемым кадром. Подтверждение может быть в форме номера последнего правильно переданного кадра, а может быть в форме первого, еще не переданного кадра. Какой вариант будет использован - зависит от параметров протокола.

Рисунок 3-17. Поле Control для кадров: Information (a), Supervisory (b), Unnumbered (c)

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

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