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

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

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

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

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

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

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

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

Раздел 3.3. Простейшие протоколы канала данных

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

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

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

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

Когда кадр поступает к получателю, контрольная сумма вычисляется аппаратно. Если она неверна, то канальному уровню сообщается: event=cksum_err. Если кадр поступил без повреждений, то канальный уровень информируется так: event=frame_arrivel.

На рисунке 3-8 приведены многие структуры, используемые позднее. Там же указаны процедуры, которые используются при построении протоколов.

Рисунок 3-8. Перечень функций, используемых в описании протокола канального уровня

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

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

Процедуры enable_network_layer и disable_network_layer используются в сложных протоколах, когда предполагается, что на сетевом уровне нет пакетов для передачи. Когда канальный уровень разрешит сетевому уровню снова передавать пакеты, сетевой информирует об этом событием event=network_layer_ready. Если канальный уровень выполнил процедуру disable_network_layer, то event=network_layer_ready может и не последовать. Таким способом канальный уровень может управлять потоком от сетевого уровня.

Симплекс-протокол без ограничений.

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

Рисунок 3-9. Симплексный протокол канального уровня

Симплексный старт-стопный протокол.

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

Основная проблема - как предотвратить ситуацию, когда отправитель «заваливает» данными получателя. Если получателю требуется время Δt, чтобы исполнить from_physical_layer плюс to_network_layer, то отправитель должен передавать данные со средней скоростью один кадр в Δt.

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

Рисунок 3-10. Однонаправленный старт-стопный протокол канального уровня

Симплексный протокол для канала с шумом.

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

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

На рисунке 3-11 показана программа для этого варианта протокола.

Рисунок 3-11. Протокол с подтверждением и восстановлением

Билет № 21.

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

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

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

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

Коды с исправлением ошибок.

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

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

В силу того, что избыточные контрольные разряды могут принимать только вполне определенные значения, то не все 2ⁿ кодовых слов возможны. Зная алгоритм установки контрольных разрядов, мы можем вычислить минимальное расстояние по Хеммингу между двумя правильными кодословами.

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

Простым примером кода с обнаружением одной ошибки является код с битом четности. Конструкция его такова: к исходному кодослову добавляется бит четности. Если число единиц в исходном кодослове четно, то значение этого бита - 0. Если нечетно, то - 1. Кодослова с битом четности имеют расстояние Хемминга 2, так как любая ошибка в одном бите породит ошибку четности. Однако, если возможны двойные ошибки, то бит четности проблему не решит.

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

Оценим минимальное количество контрольных разрядов, необходимое для исправления одиночных ошибок. Пусть у нас есть код из m бит сообщения и r контрольных бит. Каждое из 2ⁿ правильных сообщений имеет n неправильных кодослов на расстоянии 1. Таким образом, с каждым из 2^m кодослов связано n+1 кодослов. Так как общее число кодослов - 2ⁿ, то (n+1)2^m≤2, учитывая, что n=m+r, получаем: (m+r+1) ≤ 2^r

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

• Разряды кодослова нумеруются слева направо, начиная с 1.

• Все биты, номера которых являются степенью 2 (1, 2, 4, 8, 16 и т.д.) - контрольные, остальные - биты сообщения.

• Каждый контрольный бит отвечает за четность группы битов, включая себя. Чтобы определить группу битов, за четность которой отвечает определенный контрольный бит, нужно представить номер позиции каждого бита по степеням двойки. Те биты, в номера которых входит степень двойки, равная номеру контрольного бита, и есть искомая группа. Например, 11=1+2+8, 39=1+2+4+32. Таким образом, бит в позиции 11 входит в группу, контролируемую битом в позиции 2.

Получив кодослово, получатель устанавливает специальный счетчик в ноль. Затем он проверят каждый контрольный бит на предмет правильности четности. Если четность нарушена, то порядковый номер этого бита заносится в счетчик. Если после этой проверки счетчик на нуле, то все в порядке. Если нет, то он содержит номер неправильного разряда. Например, если 1, 2, 8 - ошибочные контрольные разряды, то ошибка содержится в 11-м разряде, так как только он связан одновременно с этими контрольными разрядами.

Код Хемминга может исправлять только одиночные ошибки. Однако есть прием, который позволяет распространить идеи Хемминга на случай групповых ошибок. Пусть нам надо передать k кодослов. Расположим их в виде матрицы: одно слово - строка. Обычно передают слово за словом. Но мы поступим иначе, передадим слово длины k из первых разрядов всех слов, затем - вторых, и т.д. После приема всех слов матрица восстанавливается. Если мы хотим обнаруживать групповые ошибки размера k, то в каждой строке восстановленной матрицы будет не более одной ошибки. А с одиночными ошибками код Хемминга справится.

Коды с обнаружением ошибок.

Рассмотрение кодов, обнаруживающих ошибки, начнем с небольшого примера. Пусть у нас есть канал с одиночными ошибками с частотой 10^-6 на бит. Если мы хотим исправлять единичные ошибки при передаче блока в 1000 бит, то нам потребуется 10 контрольных бит ((m+r+1) ≤ 2^rr, где m =1000; (1001+r) ≤ 2^rr, следовательно, r = 10).

При передаче 1 Мбит данных потребуется 10 000 контрольных бит. В то же время для обнаружения единичной ошибки достаточно одного бита четности. Поэтому, если мы применим технику повторной передачи, то на передачу 1000 блоков надо будет потратить 1001 бит дополнительно или с повторной передачей 2002 бит, вместо 10000 бит в случае кода с исправлением ошибки.

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

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