- Главная
- Разное
- Образование
- Спорт
- Естествознание
- Природоведение
- Религиоведение
- Французский язык
- Черчение
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, фоны, картинки для презентаций
- Экология
- Экономика
Презентация, доклад на тему Уровень передачи данных или канальный уровень
Содержание
- 1. Уровень передачи данных или канальный уровень
- 2. Уровень передачи данныхУровень передачи данных или канальный
- 3. Уровень передачи данных
- 4. Уровень передачи данных
- 5. Сервисы, предоставляемые сетевому уровнюСервис без подтверждений, без
- 6. Сервисы, предоставляемые сетевому уровнюСервис с подтверждениями, ориентированный
- 7. Канальный уровень и физический уровеньФизический уровень, предоставляющий
- 8. Формирование кадраЗадача разбиения потока битов на отдельные
- 9. Подсчёт количества символовПри искажении счетчика теряется синхронизация.
- 10. Использование сигнальных байтов с символьным заполнениемESC –
- 11. Использование стартовых и стоповых битов с битовым
- 12. Использование запрещённых сигналов физического уровняЕсли бит данных
- 13. Обработка ошибок и управление потокомНеобходимо гарантировать сетевому
- 14. Обнаружение и исправление ошибок. Корректирующее кодированиеДве стратегии
- 15. Обнаружение и исправление ошибок. Корректирующее кодированиеПусть кадр
- 16. Обнаружение и исправление ошибок. Корректирующее кодированиеВ большинстве
- 17. Обнаружение и исправление ошибок. Корректирующее кодированиеСпособности кода
- 18. Обнаружение и исправление ошибок. Корректирующее кодированиеПусть требуется
- 19. Обнаружение и исправление ошибок. Код ХэммингаБиты кодового
- 20. Обнаружение и исправление ошибок. Корректирующее кодированиеОбнуляем счетчик,
- 21. Обнаружение и исправление ошибок. Корректирующее кодирование
- 22. Обнаружение и исправление ошибок. Коды с обнаружением
- 23. Элементарные протоколы передачи данныхНеограниченный симплексный протоколСимплексный протокол с ожиданием Симплексный протокол для зашумленных каналов
- 24. Элементарные протоколы передачи данных. Общие объявления
- 25. Слайд 25
- 26. Элементарные протоколы передачи данных. Неограниченный симплексный протоколДанные
- 27. Слайд 27
- 28. Элементарные протоколы передачи данных. симплексный протокол с
- 29. Слайд 29
- 30. Элементарные протоколы передачи данных. симплексный протокол для
- 31. Слайд 31
- 32. Слайд 32
- 33. Элементарные протоколы передачи данных. Протоколы скользящего окнаДуплексная
- 34. Элементарные протоколы передачи данных. Протоколы скользящего окнаВ
- 35. Элементарные протоколы передачи данных. Протоколы скользящего окнаОкно
- 36. Элементарные протоколы передачи данных. Протоколы скользящего окнаA
- 37. Протокол однобитового скользящего окнаОкно принимающего соответствует кадрам,
- 38. Протокол однобитового скользящего окнаМетод ожидания, т.к. после
- 39. Слайд 39
- 40. Слайд 40
- 41. Слайд 41
- 42. Протоколы с возвратом на nРанее считалось, что
- 43. Протоколы с возвратом на n
- 44. Слайд 44
- 45. Слайд 45
- 46. Слайд 46
- 47. Слайд 47
- 48. Протоколы с выборочным повторомПозволяет более эффективно использовать ресурсы при частых ошибках.
- 49. Слайд 49
- 50. Слайд 50
- 51. Слайд 51
- 52. Слайд 52
- 53. Протоколы с выборочным повторомВозможно перекрытие сдвинутым окном
- 54. Верификация протоколов. Конечные автоматыПротокольная машина – отправитель
- 55. Верификация протоколов. Конечные автоматы(S,M,I,T)S – множество состояний,
- 56. Верификация протоколов. Конечные автоматыПротокол с положительным подтверждением
- 57. Верификация протоколов. Конечные автоматы
- 58. Верификация протоколов. Сети ПетриЧетыре элемента: Позиция –
- 59. Верификация протоколов. Сети Петри
- 60. Верификация протоколов. Сети ПетриГрамматика сети Петри:BD >
- 61. Протокол PPPPoint-to-Point Protocol RFC 1661 1662 1663Позволяет
- 62. Протокол PPP
- 63. Протокол PPP
Уровень передачи данныхУровень передачи данных или канальный уровень (Data link layer)Функции: обеспечение служебного интерфейса для сетевого уровня;обработка ошибок передачи данных;управление потоком данных.Сетевой уровень оперирует пакетами, канальный уровень формирует из пакетов кадры для передачи.Контроль ошибок, контроль потока
Слайд 1КОМПЬЮТЕРНЫЕ СЕТИ
Лекция №5
Уровень передачи данных или канальный уровень.
Воронеж, 2020
Русинова Елена Сергеевна
Слайд 2Уровень передачи данных
Уровень передачи данных или канальный уровень (Data link layer)
Функции:
обеспечение служебного интерфейса для сетевого уровня;
обработка ошибок передачи данных;
управление потоком данных.
Сетевой уровень оперирует пакетами, канальный уровень формирует из пакетов кадры для передачи.
Контроль ошибок, контроль потока может происходить и на более верхних уровнях.
Слайд 5Сервисы, предоставляемые сетевому уровню
Сервис без подтверждений, без установки соединения.
Просто шлём независимые
кадры, не обращая внимания на ошибки.
Применяется зачастую в локальных сетях.
Сервис с подтверждениями, без установки соединения.
Подтверждение доставки кадра (квитанция).
Повторная посылка по тайм-ауту.
Можно переложить на сетевой уровень, но там пакеты больше
Применяется зачастую в локальных сетях.
Сервис с подтверждениями, без установки соединения.
Подтверждение доставки кадра (квитанция).
Повторная посылка по тайм-ауту.
Можно переложить на сетевой уровень, но там пакеты больше
Слайд 6Сервисы, предоставляемые сетевому уровню
Сервис с подтверждениями, ориентированный на соединения.
Первая фаза. Установка
соединения, инициализация переменных и счетчиков для слежения за тем, какие кадры уже приняты, а какие ещё нет.
Вторая фаза. Передача кадров.
Третья фаза. Разрыв соединения, освобождение временных ресурсов.
Вторая фаза. Передача кадров.
Третья фаза. Разрыв соединения, освобождение временных ресурсов.
Слайд 7Канальный уровень и физический уровень
Физический уровень, предоставляющий интерфейс для канального, фактически
принимает поток битов и пытается передать. Возможны ошибки при передаче. Количество принятых бит может отличаться от количества переданных.
Задача канального уровня – обнаружить и исправить ошибки.
Канальный уровень разбивает поток битов на отдельные кадры. Для каждого кадра подсчитывается контрольная сумма, которая проверяется после передачи. Ошибочный кадр игнорируется или данные о нем передаются отправляющей стороне.
Задача канального уровня – обнаружить и исправить ошибки.
Канальный уровень разбивает поток битов на отдельные кадры. Для каждого кадра подсчитывается контрольная сумма, которая проверяется после передачи. Ошибочный кадр игнорируется или данные о нем передаются отправляющей стороне.
Слайд 8Формирование кадра
Задача разбиения потока битов на отдельные кадры не решается простым
временным интервалом.
Методы маркировки начала и конца кадра:
Подсчёт количества символов.
Использование сигнальных байтов с символьным заполнением.
Использование стартовых и стоповых бит с битовым заполнением.
Использование запрещённых сигналов физического уровня.
Методы маркировки начала и конца кадра:
Подсчёт количества символов.
Использование сигнальных байтов с символьным заполнением.
Использование стартовых и стоповых бит с битовым заполнением.
Использование запрещённых сигналов физического уровня.
Слайд 10Использование сигнальных байтов с символьным заполнением
ESC – знак переключения кода. Уровень
передачи данных убирает
ESC перед передачей сетевому уровню.
ESC перед передачей сетевому уровню.
Слайд 11Использование стартовых и стоповых битов с битовым заполнением
Каждый кадр начинается и
заканчивается последовательностью 01111110. Если при передаче в потоке 5 единиц – вставляется 0. Приемник восстанавливает, убирая лишние 0 в потоке.
Слайд 12Использование запрещённых сигналов физического уровня
Если бит данных кодируется двумя физическими битами,
то используется 2 комбинации уровней (чаще положительный и отрицательны переходы), а 2 оставшихся не используются. Их можно использовать в качестве границ кадров.
Если используется избыточное кодирование, некоторые символы можно использовать как служебные, в том числе, и для ограничения кадра.
Если используется избыточное кодирование, некоторые символы можно использовать как служебные, в том числе, и для ограничения кадра.
Слайд 13Обработка ошибок и управление потоком
Необходимо гарантировать сетевому уровню доставку всех кадров
и их порядок.
Используются служебные кадры для обратной связи с результатами доставки каждого кадра.
Для контроля полной потери используется таймер.
Необходима нумерация кадров для предотвращения повторной доставки.
Управление потоком:
Управление потоком с обратной связью;
Управление потоком с ограничением (не применяется на канальном уровне).
Используются служебные кадры для обратной связи с результатами доставки каждого кадра.
Для контроля полной потери используется таймер.
Необходима нумерация кадров для предотвращения повторной доставки.
Управление потоком:
Управление потоком с обратной связью;
Управление потоком с ограничением (не применяется на канальном уровне).
Слайд 14Обнаружение и исправление ошибок. Корректирующее кодирование
Две стратегии в компьютерных сетях:
Коды с
исправлением ошибок или корректирующие коды;
Коды с обнаружением ошибок или коды с прямым исправлением ошибок.
В некоторых сетях целесообразнее повторно запросить кадр, в других (особенно с большим количеством ошибок и малой скоростью) – восстановить исходную информацию, если это возможно.
Коды с обнаружением ошибок или коды с прямым исправлением ошибок.
В некоторых сетях целесообразнее повторно запросить кадр, в других (особенно с большим количеством ошибок и малой скоростью) – восстановить исходную информацию, если это возможно.
Слайд 15Обнаружение и исправление ошибок. Корректирующее кодирование
Пусть кадр состоит из m битов,
и r избыточных (контрольных) битов. Тогда n = m + r полная длина кадра. Набор из n битов называют n-битовым кодовым словом или кодовой комбинацией.
Кодовое расстояние в понимании Хэмминга:
10001001
10110001
00111000
d = 3
Кодовое расстояние в понимании Хэмминга:
10001001
10110001
00111000
d = 3
Слайд 16Обнаружение и исправление ошибок. Корректирующее кодирование
В большинстве приложений передачи данных все
2m возможных сообщений допустимы, но при добавлении контрольных битов не все 2n возможных кодовых слов допустимы.
Можно построить полный список всех кодовых слов.
Минимальное кодовое расстояние в этом списке называется минимальным кодовым расстоянием кода (или расстоянием всего кода в смысле Хэмминга).
Можно построить полный список всех кодовых слов.
Минимальное кодовое расстояние в этом списке называется минимальным кодовым расстоянием кода (или расстоянием всего кода в смысле Хэмминга).
Слайд 17Обнаружение и исправление ошибок. Корректирующее кодирование
Способности кода по обнаружению и исправлению
ошибок зависят от его минимального кодового расстояния. Для обнаружения k ошибок в одном кодовом слове, необходим код с минимальным кодовым расстоянием k+1.
Для исправления k ошибок в кодовом слове требуется код с минимальным расстоянием 2k+1.
Простейший пример кода с обнаружением ошибок – бит четности.
Для исправления k ошибок в кодовом слове требуется код с минимальным расстоянием 2k+1.
Простейший пример кода с обнаружением ошибок – бит четности.
Слайд 18Обнаружение и исправление ошибок. Корректирующее кодирование
Пусть требуется создать код, способный исправлять
одиночные ошибки, состоящий из m информационных и r контрольных бит. Тогда справедливо неравенство:
(m+r+1)≤2r
При заданном m неравенство описывает минимальное требуемое количество r для возможности исправления одиночных ошибок.
(m+r+1)≤2r
При заданном m неравенство описывает минимальное требуемое количество r для возможности исправления одиночных ошибок.
Слайд 19Обнаружение и исправление ошибок. Код Хэмминга
Биты кодового слова нумеруются последовательно слева,
начиная с 1.
Биты с номерами, равными степени 2 (1,2,4,8,16,32,…), являются контрольными.
Остальные биты заполняются данными.
Каждый контрольный бит обеспечивает четность некоторой группы битов, включая себя.
Каждый k-й бит будет проверяться контрольными битами, входящими в разложение k по степеням числа 2.
Биты с номерами, равными степени 2 (1,2,4,8,16,32,…), являются контрольными.
Остальные биты заполняются данными.
Каждый контрольный бит обеспечивает четность некоторой группы битов, включая себя.
Каждый k-й бит будет проверяться контрольными битами, входящими в разложение k по степеням числа 2.
Слайд 20Обнаружение и исправление ошибок. Корректирующее кодирование
Обнуляем счетчик, проверяем контрольные биты на
четность. Если сумма k-го бита не четна – добавляем к счётчику. Если счётчик равен 0 – кодовое слово цело, иначе, в случае единичной ошибки, счетчик будет содержать номер инвертированного бита.
Есть возможность целый блок ошибок. Выписываем k кодовых слов в виде матрицы, передаём по колонкам. Требуется kr проверочных бит. Блок из km бит может выдержать пакет ошибок длиной не более k бит.
Есть возможность целый блок ошибок. Выписываем k кодовых слов в виде матрицы, передаём по колонкам. Требуется kr проверочных бит. Блок из km бит может выдержать пакет ошибок длиной не более k бит.
Слайд 22Обнаружение и исправление ошибок. Коды с обнаружением ошибок
Если к каждому блоку
добавлять бит четности, вероятность обнаружения пакета ошибок, будет составлять всего 0,5. Можно увеличить вероятность, рассчитывая биты четности по столбцам матрицы, составленной из блока, который впоследствии передаётся по строкам. Тогда вероятность необнаружения составит 2-n . Где n – число столбцов.
На практике чаще всего используются CRC (Cyclic Redundancy Check – циклический избыточный код), или же полиномиальный код.
На практике чаще всего используются CRC (Cyclic Redundancy Check – циклический избыточный код), или же полиномиальный код.
Слайд 23Элементарные протоколы передачи данных
Неограниченный симплексный протокол
Симплексный протокол с ожиданием
Симплексный протокол
для зашумленных каналов
Слайд 26Элементарные протоколы передачи данных. Неограниченный симплексный протокол
Данные передаются в одном направлении
Сетевой
уровень на передающей и принимающей стороне в состоянии постоянной готовности
Время обработки равно 0
Размер буфера не ограничен
Канал связи между уровнями передачи данных идеален
Время обработки равно 0
Размер буфера не ограничен
Канал связи между уровнями передачи данных идеален
Слайд 28Элементарные протоколы передачи данных. симплексный протокол с ожиданием
Пусть сетевой уровень не
может моментально обрабатывать данные (получающий уровень передачи данных не имеет неограниченного буферного пространства).
Возможна ситуация, когда отправитель посылает быстрее, чем получатель обрабатывает.
Решение – или жесткое ограничение или обратная связь служебным кадром, разрешающим дальнейшую отправку.
Возможна ситуация, когда отправитель посылает быстрее, чем получатель обрабатывает.
Решение – или жесткое ограничение или обратная связь служебным кадром, разрешающим дальнейшую отправку.
Слайд 30Элементарные протоколы передачи данных. симплексный протокол для зашумленных каналов
Канал не идеален,
кадры могут искажаться и теряться.
Теряться и искажаться могут в том числе и служебные кадры.
Требуется ввести порядковые номера и вести учёт номеров как на передающей, так и на принимающей стороне.
Теряться и искажаться могут в том числе и служебные кадры.
Требуется ввести порядковые номера и вести учёт номеров как на передающей, так и на принимающей стороне.
Слайд 33Элементарные протоколы передачи данных. Протоколы скользящего окна
Дуплексная передача по одному каналу
в обоих направлениях.
Служебные и кадры данных можно различать по полю kind.
Подтверждение можно добавлять к следующему на отправку от сетевого уровня пакету (ack в заголовке кадра). Piggybacking. Требуется таймер.
Служебные и кадры данных можно различать по полю kind.
Подтверждение можно добавлять к следующему на отправку от сетевого уровня пакету (ack в заголовке кадра). Piggybacking. Требуется таймер.
Слайд 34Элементарные протоколы передачи данных. Протоколы скользящего окна
В любой момент времени отправитель
работает с определённым набором порядковых номеров, соответствующих кадрам, которые разрешено посылать. Посылающее окно.
Аналогично получатель работает с принимающим окном.
Окно получателя и отправителя могут иметь разные границы и размеры.
При поступлении от сетевого уровня пакета на отправку ему дается наибольше номер, верхняя граница окна увеличивается
При получении подтверждения, нижняя граница уменьшается
В окне отправителя – кадры, которые отправлены, но нет пока подтверждения.
Аналогично получатель работает с принимающим окном.
Окно получателя и отправителя могут иметь разные границы и размеры.
При поступлении от сетевого уровня пакета на отправку ему дается наибольше номер, верхняя граница окна увеличивается
При получении подтверждения, нижняя граница уменьшается
В окне отправителя – кадры, которые отправлены, но нет пока подтверждения.
Слайд 35Элементарные протоколы передачи данных. Протоколы скользящего окна
Окно принимающего соответствует кадрам, которые
он может принять. Кадр, не попадающий в окно – игнорируется.
Прибывающий кадр с порядковым номером нижней границы предаётся на сетевой уровень. Формируется подтверждение, окно сдвигается на позицию.
Окно единичного размера означает, что уровень передачи принимает кадры только по порядку.
Прибывающий кадр с порядковым номером нижней границы предаётся на сетевой уровень. Формируется подтверждение, окно сдвигается на позицию.
Окно единичного размера означает, что уровень передачи принимает кадры только по порядку.
Слайд 36Элементарные протоколы передачи данных. Протоколы скользящего окна
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.
(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.
Слайд 37Протокол однобитового скользящего окна
Окно принимающего соответствует кадрам, которые он может принять.
Кадр, не попадающий в окно – игнорируется.
Прибывающий кадр с порядковым номером нижней границы предаётся на сетевой уровень. Формируется подтверждение, окно сдвигается на позицию.
Окно единичного размера означает, что уровень передачи принимает кадры только по порядку.
Прибывающий кадр с порядковым номером нижней границы предаётся на сетевой уровень. Формируется подтверждение, окно сдвигается на позицию.
Окно единичного размера означает, что уровень передачи принимает кадры только по порядку.
Слайд 38Протокол однобитового скользящего окна
Метод ожидания, т.к. после посылки кадра отправитель ждет
подтверждения.
next_frame_to_send номер кадра, который отправитель пытается послать.
frame_expected номер кадра, ожидаемого получателем.
Только один уровень передачи данных может начинать передачу.
next_frame_to_send номер кадра, который отправитель пытается послать.
frame_expected номер кадра, ожидаемого получателем.
Только один уровень передачи данных может начинать передачу.
Слайд 42Протоколы с возвратом на n
Ранее считалось, что время на передачу кадра
от отправителя к получателю и на обратную отправку подтверждения было пренебрежимо мало. В случае, если это не так, эффективность очень мала.
Разрешим отправителю слать не 1 кадра а w. Конвейерная обработка.
Возможна ошибка при передаче кадра внутри этого w:
Возврат на n – игнорируем все кадры с номером больше поврежденного.
Выборочный повтор – буферизуем нормальные, как получаем повторно битый – высылаем максимальный ACK. Есть модификации с пересылкой NAK, стимулирующего повторную отправку.
Разрешим отправителю слать не 1 кадра а w. Конвейерная обработка.
Возможна ошибка при передаче кадра внутри этого w:
Возврат на n – игнорируем все кадры с номером больше поврежденного.
Выборочный повтор – буферизуем нормальные, как получаем повторно битый – высылаем максимальный ACK. Есть модификации с пересылкой NAK, стимулирующего повторную отправку.
Слайд 48Протоколы с выборочным повтором
Позволяет более эффективно использовать ресурсы при частых ошибках.
Слайд 53Протоколы с выборочным повтором
Возможно перекрытие сдвинутым окном исходного.
Размер окна должен
не превышать половины от количества порядковых номеров.
Количество буферов у получателя равно размеру окна.
Количество буферов у получателя равно размеру окна.
Слайд 54Верификация протоколов. Конечные автоматы
Протокольная машина – отправитель и получатель. Состояние протокольной
машины – все значения всех её переменных, в том числе и программные счётчики.
Состояние канала определяется его содержимым.
Каждое состояние может быть соединено с другими переходами.
Имея полное описание протокольной машины можно получить двунаправленный граф.
Методы теории графов (транзитивное замыкание) позволяют проводить анализ достижимости.
Состояние канала определяется его содержимым.
Каждое состояние может быть соединено с другими переходами.
Имея полное описание протокольной машины можно получить двунаправленный граф.
Методы теории графов (транзитивное замыкание) позволяют проводить анализ достижимости.
Слайд 55Верификация протоколов. Конечные автоматы
(S,M,I,T)
S – множество состояний, в которых могут находиться
процессы и канал.
M – множество кадров, передающихся по каналу.
I – множество начальных состояний процессов.
T – множество переходов между состояниями.
M – множество кадров, передающихся по каналу.
I – множество начальных состояний процессов.
T – множество переходов между состояниями.
Слайд 56Верификация протоколов. Конечные автоматы
Протокол с положительным подтверждением и повторной передачей.
(S,R,C)
S –
0 или 1, номер кадра, посылаемого отправителем.
R – 0 или 1, номер кадра, ожидаемого получателем.
C – состояние канала. 0 1 A -
T – множество переходов между состояниями.
R – 0 или 1, номер кадра, ожидаемого получателем.
C – состояние канала. 0 1 A -
T – множество переходов между состояниями.
Слайд 58Верификация протоколов. Сети Петри
Четыре элемента:
Позиция – состояние, в котором может
находиться система или её часть.
Маркеры, помещающие состояние системы.
Переходы (каждый переход может иметь входящие и исходящие дуги)
Переход называется разрешенным, если имеется маркер на входящей позиции.
В отличии от автоматов, не составных состояний.
Могут быть представлены в виде грамматики.
Маркеры, помещающие состояние системы.
Переходы (каждый переход может иметь входящие и исходящие дуги)
Переход называется разрешенным, если имеется маркер на входящей позиции.
В отличии от автоматов, не составных состояний.
Могут быть представлены в виде грамматики.
Слайд 60Верификация протоколов. Сети Петри
Грамматика сети Петри:
BD > AC
A > A
AD >
BE
B > B
C >
D >
E >
CF > DF
EG > DG
CG > DF
EF > DG
B > B
C >
D >
E >
CF > DF
EG > DG
CG > DF
EF > DG
Слайд 61Протокол PPP
Point-to-Point Protocol RFC 1661 1662 1663
Позволяет обнаружение ошибок;
Поддерживает несколько протоколов;
Байт-ориентирован;
Методы
PPP:
Метод формирования кадров
Протокол управления каналом (установка канала, тестирование, обмен параметрами). Поддерживает синхронные и асинхронные линии, байт и бит ориентированное кодирование
Выработка параметров для сетевого уровня NCP Network Control Protocol
Метод формирования кадров
Протокол управления каналом (установка канала, тестирование, обмен параметрами). Поддерживает синхронные и асинхронные линии, байт и бит ориентированное кодирование
Выработка параметров для сетевого уровня NCP Network Control Protocol
