КОМПЬЮТЕРНЫЕ СЕТИ Лекция 5 Уровень передачи данных или канальный уровень. Санкт-Петербург, 2012 Александр Масальских

У РОВЕНЬ ПЕРЕДАЧИ ДАННЫХ Уровень передачи данных или канальный уровень (Data link layer) Функции: обеспечение служебного интерфейса для сетевого уровня; обработка ошибок передачи данных; управление потоком данных. Сетевой уровень оперирует пакетами, канальный уровень формирует из пакетов кадры для передачи. Контроль ошибок, контроль потока может происходить и на более верхних уровнях.

У РОВЕНЬ ПЕРЕДАЧИ ДАННЫХ

С ЕРВИСЫ, ПРЕДОСТАВЛЯЕМЫЕ СЕТЕВОМУ УРОВНЮ Сервис без подтверждений, без установки соединения. Просто шлём независимые кадры, не обращая внимания на ошибки. Применяется зачастую в локальных сетях. Сервис с подтверждениями, без установки соединения. Подтверждение доставки кадра (квитанция). Повторная посылка по тайм-ауту. Можно переложить на сетевой уровень, но там пакеты больше

С ЕРВИСЫ, ПРЕДОСТАВЛЯЕМЫЕ СЕТЕВОМУ УРОВНЮ Сервис с подтверждениями, ориентированный на соединения. Первая фаза. Установка соединения, инициализация переменных и счетчиков для слежения за тем, какие кадры уже приняты, а какие ещё нет. Вторая фаза. Передача кадров. Третья фаза. Разрыв соединения, освобождение временных ресурсов.

К АНАЛЬНЫЙ УРОВЕНЬ И ФИЗИЧЕСКИЙ УРОВЕНЬ Физический уровень, предоставляющий интерфейс для канального, фактически принимает поток битов и пытается передать. Возможны ошибки при передаче. Количество принятых бит может отличаться от количества переданных. Задача канального уровня – обнаружить и исправить ошибки. Канальный уровень разбивает поток битов на отдельные кадры. Для каждого кадра подсчитывается контрольная сумма, которая проверяется после передачи. Ошибочный кадр игнорируется или данные о нем передаются отправляющей стороне.

Ф ОРМИРОВАНИЕ КАДРА Задача разбиения потока битов на отдельные кадры не решается простым временным интервалом. Методы маркировки начала и конца кадра: 1. Подсчёт количества символов. 2. Использование сигнальных байтов с символьным заполнением. 3. Использование стартовых и стоповых бит с битовым заполнением. 4. Использование запрещённых сигналов физического уровня.

П ОДСЧЁТ КОЛИЧЕСТВА СИМВОЛОВ При искажении счетчика теряется синхронизация.

И СПОЛЬЗОВАНИЕ СИГНАЛЬНЫХ БАЙТОВ С СИМВОЛЬНЫМ ЗАПОЛНЕНИЕМ ESC – знак переключения кода. Уровень передачи данных убирает ESC перед передачей сетевому уровню.

И СПОЛЬЗОВАНИЕ СТАРТОВЫХ И СТОПОВЫХ БИТОВ С БИТОВЫМ ЗАПОЛНЕНИЕМ Каждый кадр начинается и заканчивается последовательностью Если при передаче в потоке 5 единиц – вставляется 0. Приемник восстанавливает, убирая лишние 0 в потоке.

И СПОЛЬЗОВАНИЕ ЗАПРЕЩЁННЫХ СИГНАЛОВ ФИЗИЧЕСКОГО УРОВНЯ Если бит данных кодируется двумя физическими битами, то используется 2 комбинации уровней (чаще положительный и отрицательны переходы), а 2 оставшихся не используются. Их можно использовать в качестве границ кадров. Если используется избыточное кодирование, некоторые символы можно использовать как служебные, в том числе, и для ограничения кадра.

О БРАБОТКА ОШИБОК И УПРАВЛЕНИЕ ПОТОКОМ Необходимо гарантировать сетевому уровню доставку всех кадров и их порядок. Используются служебные кадры для обратной связи с результатами доставки каждого кадра. Для контроля полной потери используется таймер. Необходима нумерация кадров для предотвращения повторной доставки. Управление потоком: Управление потоком с обратной связью; Управление потоком с ограничением (не применяется на канальном уровне).

О БНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК. К ОРРЕКТИРУЮЩЕЕ КОДИРОВАНИЕ Две стратегии в компьютерных сетях: Коды с исправлением ошибок или корректирующие коды; Коды с обнаружением ошибок или коды с прямым исправлением ошибок. В некоторых сетях целесообразнее повторно запросить кадр, в других (особенно с большим количеством ошибок и малой скоростью) – восстановить исходную информацию, если это возможно.

О БНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК. К ОРРЕКТИРУЮЩЕЕ КОДИРОВАНИЕ Пусть кадр состоит из m битов, и r избыточных (контрольных) битов. Тогда n = m + r полная длина кадра. Набор из n битов называют n- битовым кодовым словом или кодовой комбинацией. Кодовое расстояние в понимании Хэмминга: d = 3

О БНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК. К ОРРЕКТИРУЮЩЕЕ КОДИРОВАНИЕ В большинстве приложений передачи данных все 2 m возможных сообщений допустимы, но при добавлении контрольных битов не все 2 n возможных кодовых слов допустимы. Можно построить полный список всех кодовых слов. Минимальное кодовое расстояние в этом списке называется минимальным кодовым расстоянием кода (или расстоянием всего кода в смысле Хэмминга).

О БНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК. К ОРРЕКТИРУЮЩЕЕ КОДИРОВАНИЕ Способности кода по обнаружению и исправлению ошибок зависят от его минимального кодового расстояния. Для обнаружения k ошибок в одном кодовом слове, необходим код с минимальным кодовым расстоянием k+1. Для исправления k ошибок в кодовом слове требуется код с минимальным расстоянием 2k+1. Простейший пример кода с обнаружением ошибок – бит четности.

О БНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК. К ОРРЕКТИРУЮЩЕЕ КОДИРОВАНИЕ Пусть требуется создать код, способный исправлять одиночные ошибки, состоящий из m информационных и r контрольных бит. Тогда справедливо неравенство: (m+r+1)2 r При заданном m неравенство описывает минимальное требуемое количество r для возможности исправления одиночных ошибок.

О БНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК. К ОД Х ЭММИНГА Биты кодового слова нумеруются последовательно слева, начиная с 1. Биты с номерами, равными степени 2 (1,2,4,8,16,32,…), являются контрольными. Остальные биты заполняются данными. Каждый контрольный бит обеспечивает четность некоторой группы битов, включая себя. Каждый k-й бит будет проверяться контрольными битами, входящими в разложение k по степеням числа 2.

О БНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК. К ОРРЕКТИРУЮЩЕЕ КОДИРОВАНИЕ Обнуляем счетчик, проверяем контрольные биты на четность. Если сумма k-го бита не четна – добавляем к счётчику. Если счётчик равен 0 – кодовое слово цело, иначе, в случае единичной ошибки, счетчик будет содержать номер инвертированного бита. Есть возможность целый блок ошибок. Выписываем k кодовых слов в виде матрицы, передаём по колонкам. Требуется kr проверочных бит. Блок из km бит может выдержать пакет ошибок длиной не более k бит.

О БНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК. К ОРРЕКТИРУЮЩЕЕ КОДИРОВАНИЕ

О БНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК. К ОДЫ С ОБНАРУЖЕНИЕМ ОШИБОК Если к каждому блоку добавлять бит четности, вероятность обнаружения пакета ошибок, будет составлять всего 0,5. Можно увеличить вероятность, рассчитывая биты четности по столбцам матрицы, составленной из блока, который впоследствии передаётся по строкам. Тогда вероятность необнаружения составит 2 -n. Где n – число столбцов. На практике чаще всего используются CRC (Cyclic Redundancy Check – циклический избыточный код), или же полиномиальный код.

Э ЛЕМЕНТАРНЫЕ ПРОТОКОЛЫ ПЕРЕДАЧИ ДАННЫХ Неограниченный симплексный протокол Симплексный протокол с ожиданием Симплексный протокол для зашумленных каналов

Э ЛЕМЕНТАРНЫЕ ПРОТОКОЛЫ ПЕРЕДАЧИ ДАННЫХ. О БЩИЕ ОБЪЯВЛЕНИЯ

Э ЛЕМЕНТАРНЫЕ ПРОТОКОЛЫ ПЕРЕДАЧИ ДАННЫХ. Н ЕОГРАНИЧЕННЫЙ СИМПЛЕКСНЫЙ ПРОТОКОЛ Данные передаются в одном направлении Сетевой уровень на передающей и принимающей стороне в состоянии постоянной готовности Время обработки равно 0 Размер буфера не ограничен Канал связи между уровнями передачи данных идеален

Э ЛЕМЕНТАРНЫЕ ПРОТОКОЛЫ ПЕРЕДАЧИ ДАННЫХ. СИМПЛЕКСНЫЙ ПРОТОКОЛ С ОЖИДАНИЕМ Пусть сетевой уровень не может моментально обрабатывать данные (получающий уровень передачи данных не имеет неограниченного буферного пространства). Возможна ситуация, когда отправитель посылает быстрее, чем получатель обрабатывает. Решение – или жесткое ограничение или обратная связь служебным кадром, разрешающим дальнейшую отправку.

Э ЛЕМЕНТАРНЫЕ ПРОТОКОЛЫ ПЕРЕДАЧИ ДАННЫХ. СИМПЛЕКСНЫЙ ПРОТОКОЛ ДЛЯ ЗАШУМЛЕННЫХ КАНАЛОВ Канал не идеален, кадры могут искажаться и теряться. Теряться и искажаться могут в том числе и служебные кадры. Требуется ввести порядковые номера и вести учёт номеров как на передающей, так и на принимающей стороне.

Э ЛЕМЕНТАРНЫЕ ПРОТОКОЛЫ ПЕРЕДАЧИ ДАННЫХ. П РОТОКОЛЫ СКОЛЬЗЯЩЕГО ОКНА Дуплексная передача по одному каналу в обоих направлениях. Служебные и кадры данных можно различать по полю kind. Подтверждение можно добавлять к следующему на отправку от сетевого уровня пакету (ack в заголовке кадра). Piggybacking. Требуется таймер.

Э ЛЕМЕНТАРНЫЕ ПРОТОКОЛЫ ПЕРЕДАЧИ ДАННЫХ. П РОТОКОЛЫ СКОЛЬЗЯЩЕГО ОКНА В любой момент времени отправитель работает с определённым набором порядковых номеров, соответствующих кадрам, которые разрешено посылать. Посылающее окно. Аналогично получатель работает с принимающим окном. Окно получателя и отправителя могут иметь разные границы и размеры. При поступлении от сетевого уровня пакета на отправку ему дается наибольше номер, верхняя граница окна увеличивается При получении подтверждения, нижняя граница уменьшается В окне отправителя – кадры, которые отправлены, но нет пока подтверждения.

Э ЛЕМЕНТАРНЫЕ ПРОТОКОЛЫ ПЕРЕДАЧИ ДАННЫХ. П РОТОКОЛЫ СКОЛЬЗЯЩЕГО ОКНА Окно принимающего соответствует кадрам, которые он может принять. Кадр, не попадающий в окно – игнорируется. Прибывающий кадр с порядковым номером нижней границы предаётся на сетевой уровень. Формируется подтверждение, окно сдвигается на позицию. Окно единичного размера означает, что уровень передачи принимает кадры только по порядку.

Э ЛЕМЕНТАРНЫЕ ПРОТОКОЛЫ ПЕРЕДАЧИ ДАННЫХ. П РОТОКОЛЫ СКОЛЬЗЯЩЕГО ОКНА A sliding window of size 1, with a 3-bit sequence number. (a) Initially. (b) After the first frame has been sent. (c) After the first frame has been received. (d) After the first acknowledgement has been received.

П РОТОКОЛ ОДНОБИТОВОГО СКОЛЬЗЯЩЕГО ОКНА Окно принимающего соответствует кадрам, которые он может принять. Кадр, не попадающий в окно – игнорируется. Прибывающий кадр с порядковым номером нижней границы предаётся на сетевой уровень. Формируется подтверждение, окно сдвигается на позицию. Окно единичного размера означает, что уровень передачи принимает кадры только по порядку.

П РОТОКОЛ ОДНОБИТОВОГО СКОЛЬЗЯЩЕГО ОКНА Метод ожидания, т.к. после посылки кадра отправитель ждет подтверждения. next_frame_to_send номер кадра, который отправитель пытается послать. frame_expected номер кадра, ожидаемого получателем. Только один уровень передачи данных может начинать передачу.

П РОТОКОЛЫ С ВОЗВРАТОМ НА N Ранее считалось, что время на передачу кадра от отправителя к получателю и на обратную отправку подтверждения было пренебрежимо мало. В случае, если это не так, эффективность очень мала. Разрешим отправителю слать не 1 кадра а w. Конвейерная обработка. Возможна ошибка при передаче кадра внутри этого w: Возврат на n – игнорируем все кадры с номером больше поврежденного. Выборочный повтор – буферизуем нормальные, как получаем повторно битый – высылаем максимальный ACK. Есть модификации с пересылкой NAK, стимулирующего повторную отправку.

П РОТОКОЛЫ С ВОЗВРАТОМ НА N

П РОТОКОЛЫ С ВЫБОРОЧНЫМ ПОВТОРОМ Позволяет более эффективно использовать ресурсы при частых ошибках.

П РОТОКОЛЫ С ВЫБОРОЧНЫМ ПОВТОРОМ Возможно перекрытие сдвинутым окном исходного. Размер окна должен не превышать половины от количества порядковых номеров. Количество буферов у получателя равно размеру окна.

В ЕРИФИКАЦИЯ ПРОТОКОЛОВ. К ОНЕЧНЫЕ АВТОМАТЫ Протокольная машина – отправитель и получатель. Состояние протокольной машины – все значения всех её переменных, в том числе и программные счётчики. Состояние канала определяется его содержимым. Каждое состояние может быть соединено с другими переходами. Имея полное описание протокольной машины можно получить двунаправленный граф. Методы теории графов (транзитивное замыкание) позволяют проводить анализ достижимости.

В ЕРИФИКАЦИЯ ПРОТОКОЛОВ. К ОНЕЧНЫЕ АВТОМАТЫ (S,M,I,T) S – множество состояний, в которых могут находиться процессы и канал. M – множество кадров, передающихся по каналу. I – множество начальных состояний процессов. T – множество переходов между состояниями.

В ЕРИФИКАЦИЯ ПРОТОКОЛОВ. К ОНЕЧНЫЕ АВТОМАТЫ Протокол с положительным подтверждением и повторной передачей. (S,R,C) S – 0 или 1, номер кадра, посылаемого отправителем. R – 0 или 1, номер кадра, ожидаемого получателем. C – состояние канала. 0 1 A - T – множество переходов между состояниями.

В ЕРИФИКАЦИЯ ПРОТОКОЛОВ. К ОНЕЧНЫЕ АВТОМАТЫ

В ЕРИФИКАЦИЯ ПРОТОКОЛОВ. С ЕТИ П ЕТРИ Четыре элемента: Позиция – состояние, в котором может находиться система или её часть. Маркеры, помещающие состояние системы. Переходы (каждый переход может иметь входящие и исходящие дуги) Переход называется разрешенным, если имеется маркер на входящей позиции. В отличии от автоматов, не составных состояний. Могут быть представлены в виде грамматики.

В ЕРИФИКАЦИЯ ПРОТОКОЛОВ. С ЕТИ П ЕТРИ

Грамматика сети Петри: 1. BD > AC 2. A > A 3. AD > BE 4. B > B 5. C > 6. D > 7. E > 8. CF > DF 9. EG > DG 10. CG > DF 11. EF > DG

П РОТОКОЛ PPP Point-to-Point Protocol RFC Позволяет обнаружение ошибок; Поддерживает несколько протоколов; Байт-ориентирован; Методы PPP: 1. Метод формирования кадров 2. Протокол управления каналом (установка канала, тестирование, обмен параметрами). Поддерживает синхронные и асинхронные линии, байт и бит ориентированное кодирование 3. Выработка параметров для сетевого уровня NCP Network Control Protocol

П РОТОКОЛ PPP