В интернете в качестве основного протокола линий «точка-точка» используется 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 бит с добавлением битов четности к каждому ряду и каждой строке. Бит в нижнем правом углу — это бит четности, проверяющий свою строку и столбец. Будет ли такая схема выявлять все одиночные ошибки? Двойные? Тройные? Докажите на примере, что эта схема не в состоянии обнаруживать некоторые четырехбитные ошибки.
17. Сколько ошибок можно обнаружить и исправить в предыдущей задаче?
18. Составьте формулу для вычисления минимального количества избыточных битов r, добавляемых в сообщение m с целью исправления всех одиночных и двойных ошибок.
19. Принимая во внимание ответ на предыдущий вопрос, объясните популярность сложных вероятностных механизмов исправления ошибок, таких как рассмотренные в данной главе сверточные коды и коды LDPC.
20. Предположим, что данные передаются в блоках размером 1000 бит. Каков максимальный коэффициент ошибок, при котором механизм с обнаружением ошибок и повторной передачей (1 бит четности на блок) покажет себя лучше, чем код Хэмминга? Предполагается, что ошибки в битах не зависят друг от друга, а во время повторной передачи они не возникают.
21. В блоке битов из n строк и k столбцов используются горизонтальные и вертикальные биты четности для обнаружения ошибок. Какова вероятность того, что инверсия 4 бит не будет обнаружена?
22. Предположим, что сообщение 1001 1100 1010 0011 передается с использованием контрольной суммы для интернета (4-битное слово). Какова будет контрольная сумма?
23. Чему равен остаток от деления x7 + x5 + 1 на образующий многочлен x3 + 1?
24. Поток битов 10011101 передается с использованием стандартного метода циклического избыточного кода (CRC), описанного в данной главе. Образующий многочлен равен x3 + 1. Какая битовая последовательность будет реально передаваться? Предполагается, что третий бит слева при передаче инвертировался. Докажите, что эта ошибка будет обнаружена приемником. Приведите пример ошибок в битах передаваемой строки, которые приемник обнаружить не сможет.
25. Поток битов 11100110 передается с использованием стандартного метода циклического избыточного кода (CRC), описанного в этой главе. Образующий многочлен равен x4 + x3 + 1. Какая битовая последовательность будет реально передаваться? Предполагается, что третий бит слева при передаче инвертировался. Докажите, что эта ошибка будет обнаружена приемником. Приведите пример ошибок в битах передаваемой строки, которые приемник обнаружить не сможет.
26. Протоколы канального уровня всегда размещают код CRC в трейлере, а не в заголовке. Почему?
27. При обсуждении протокола ARQ приводился пример сценария, в котором получатель принимает две копии одного и того же фрейма из-за потери подтверждения. Возможно ли, что получатель примет несколько копий одного фрейма, если ни один из фреймов (данных или подтверждения) утерян не будет?
28. Скорость передачи данных в канале составляет 4 Кбит/с, а время распространения сигнала — 20 мс. При каком размере фреймов эффективность протокола с остановкой и ожиданием составит по меньшей мере 50 %?
29. Протоколы A и B различаются только размером посылающего окна. Протокол A использует окно передачи размером 20 фреймов. B представляет собой протокол с остановкой и ожиданием. Эти протоколы используются в двух одинаковых каналах. Если A обеспечивает почти 100%-ю эффективность использования пропускной способности, то каков этот показатель у B?
30. Протокол с остановкой и ожиданием обеспечивает 25%-ю эффективность использования пропускной способности, передавая 900-битные фреймы по каналу с задержкой односторонней передачи 50 мс. Чему равна пропускная способность этого канала в битах в секунду?
31. Протокол с остановкой и ожиданием обеспечивает 60%-ю эффективность использования пропускной способности, передавая 300-битные фреймы по каналу, пропускная способность которого равна 50 Кбит/с. Чему равна задержка односторонней передачи у этого канала?
32. Протокол с остановкой и ожиданием передает 800-битные фреймы по каналу с задержкой односторонней передачи 8 мс и с пропускной способностью 1200 Кбит/с. Какова при этом эффективность использования пропускной способности?
33. Протокол «раздвижного окна» использует 1000-битные фреймы и фиксированный размер посылающего окна, равный 3. Он обеспечивает почти 100%-ю эффективность использования пропускной способности канала, которая равна 250 Кбит/с. Вы решили использовать этот протокол в более мощном канале. У него такая же величина задержки, а пропускная способность в два раза больше. Какую эффективность использования пропускной способности обеспечит данный протокол в новом канале?
34. Возможно ли, что в протоколе 3 отправитель запустит таймер, когда тот уже работает? Если да, то в какой ситуации? Если нет, то почему?
35. Кабель T1 длиной 3000 км используется для передачи 64-байтных фреймов при помощи протокола 5. Если задержка распространения сигнала составляет 6 мкс/км, сколько битов следует выделить для порядковых номеров фреймов?
36. Представьте себе протокол «раздвижного окна», в котором так много битов на порядковые номера фреймов, что номера никогда не используются дважды. Какое соотношение должно связывать четыре границы окна и его размер (постоянный и одинаковый для отправителя и получателя)?
37. Когда прибывает фрейм данных, протокол 6 проверяет, отличается ли его номер от ожидаемого и равна ли переменная no_nak значению true. При выполнении обоих условий посылается NAK. В противном случае запускается вспомогательный таймер. Предположим, что в тексте программы пропущен оператор else. Повлияет ли это на правильность работы протокола?
38. Предположим, что из конца текста программы протокола 6 удалены три строки цикла while. Повлияет ли это на правильность работы протокола или же только на его быстродействие? Обоснуйте ваш ответ.
39. Допустим, в условиях предыдущей задачи используется другой протокол — протокол «раздвижного окна». При каком размере окна отправителя коэффициент загруженности канала будет равен 100 %? Время на обработку протокола на стороне отправителя и получателя можно не учитывать.