Чтение онлайн

27 Его также иногда называют подуровнем физической среды (Physical Media Dependent, PMD).

3.6. Резюме

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

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

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

Мы рассмотрели ряд протоколов, обеспечивающих надежную работу канального уровня за счет подтверждений и повторной передачи или, если взять более реалистичный пример, за счет запросов ARQ (Automatic Repeat reQuest). Начав с обсуждения идеальной среды передачи, где отсутствуют ошибки, и идеального приемника, который может обработать входящий поток любого размера, мы познакомились с управлением потоком, затем с контролем ошибок с помощью порядковых номеров и, наконец, с алгоритмом с остановкой и ожиданием. Затем мы перешли к алгоритму «раздвижного окна», позволяющему обмениваться данными в двух направлениях, и узнали о концепции вложенного подтверждения. Последние два протокола используют конвейерную передачу множества фреймов, чтобы отправитель не блокировался, увеличивая задержку передачи. Получатель может либо отбрасывать все фреймы, за исключением очередного в последовательности, либо помещать неупорядоченные фреймы в буфер и отправлять отрицательные подтверждения для более эффективного использования полосы пропускания. Первая стратегия называется протоколом с возвратом к n, а вторая — протоколом с выборочным повтором.

В интернете в качестве основного протокола линий «точка-точка» используется PPP. Он предоставляет службу без установки соединения и без подтверждения. Для разделения фреймов применяются флаговые байты, а для распо­знавания ошибок — коды CRC. С помощью этого протокола пакеты передаются по множеству типов соединений, включая каналы SONET в глобальных сетях и ADSL для домашних подключений. Для предоставления доступа в интернет по имеющейся сети кабельного телевидения используется протокол DOCSIS.

Вопросы и задачи

1. В сети Ethernet для разделения фреймов используется преамбула в сочетании со счетчиком байтов. Что произойдет, если пользователь попытается отправить данные, содержащие такую преамбулу?

2. В потоке данных, для которого применяется алгоритм байт-стаффинга, встречается следующий фрагмент данных: A B ESC C ESC FLAG FLAG D. Каким будет выходной поток после выполнения алгоритма?

3. Каковы максимальные накладные расходы для алгоритма байт-стаф­финга?

4. Вы принимаете следующий фрагмент данных: 0110 0111 1100 1111 0111 1101. При этом известно, что протокол использует бит-стаффинг. Как будут выглядеть эти данные после удаления вставленных битов?

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

6. Сообщение верхнего уровня разбито на 10 фреймов, у каждого из которых шанс дойти до назначения без повреждений составляет 80 %. Если канальный уровень не обеспечивает контроль ошибок, сколько раз в среднем потребуется пересылать все сообщение?

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

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

9. Заметив, что используемая вами служба обмена мгновенными сообщениями не обеспечивает обнаружения ошибок, вы решили сами реализовать простейший механизм их выявления путем двукратной отправки каждого сообщения. Какими при этом будут расстояние Хэмминга и кодовая норма? Насколько эффективен этот способ в сравнении с использованием бита четности?

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

11. 8-битный байт с двоичным значением 10101111 необходимо закодировать, используя код Хэмминга с четным количеством единиц. Как будет выглядеть двоичное значение после кодирования?

12. 8-битный байт с двоичным значением 10011010 необходимо закодировать, используя код Хэмминга с нечетным количеством единиц. Как будет выглядеть двоичное значение после кодирования?

13. Приемник получает 12-битный код Хэмминга с контролем четности, шестнадцатеричное значение которого равно 0xB4D. Как (в шестнадцатеричном виде) выглядела исходная последовательность? Предполагается, что ошибочным может быть только 1 бит.

14. У кодов Хэмминга расстояние равно 3, что позволяет с их помощью исправлять одиночные ошибки или выявлять двойные. Можно ли применять их для одновременного выполнения обеих задач? Обоснуйте свою точку зрения. Сколько ошибок может быть исправлено, если расстояние Хэмминга равно n? А сколько обнаружено?

15. Имеется протокол, в котором на каждые 16 байт данных сообщения добавляется 1 байт избыточных данных. Может ли этот протокол использовать код Хэмминга для исправления одиночных ошибок?

16. Один из способов обнаружения ошибок заключается в передаче данных в виде блока из n рядов по k бит с добавлением битов четности к каждому ряду и каждой строке. Бит в нижнем правом углу — это бит четности, проверяющий свою строку и столбец. Будет ли такая схема выявлять все одиночные ошибки? Двойные? Тройные? Докажите на примере, что эта схема не в состоянии обнаруживать некоторые четырехбитные ошибки.