Компьютерные сети. 6-е изд.

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

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 %? Время на обработку протокола на стороне отправителя и получателя можно не учитывать.

40. Допустим, в коде протокола 6 из оператора switch будет удален случай, соответствующий возникновению ошибок в контрольной сумме. Как это изменение скажется на работе протокола?

41. В протоколе 6 код для frame_arrival содержит раздел, используемый для отрицательных подтверждений (NAK). Этому участку программы передается управление, когда получаемый фрейм представляет собой NAK и выполняется другое условие. Приведите пример сценария, в котором наличие этого условия является важным.

42. Протокол 6 применяется на свободной от ошибок линии со скоростью 1 Мбит/с. Максимальный размер фрейма 1000 бит. Новые пакеты формируются примерно один раз в секунду. Интервал тайм-аута установлен на период 10 мс. Если отключить специальный таймер подтверждений, то будут происходить лишние тайм-ауты. Сколько раз в среднем будет передаваться одно сообщение?

43. В протоколе 6 значение MAX_SEQ = 2n – 1. Разумеется, это желательное условие для эффективного использования битов заголовка, но его необходимость не доказана. Будет ли протокол корректно работать, например, при MAX_SEQ = 4?

44. Фреймы длиной 1000 бит посылаются по спутниковому каналу с пропускной способностью 1 Мбит/с и временем прохождения 270 мс. Подтверждения всегда вкладываются во фреймы данных. Заголовки фреймов очень короткие. Используются 3-битные порядковые номера. Какой будет максимальная эффективность использования канала при применении:

1) протокола с остановкой и ожиданием;

2) протокола 5;

3) протокола 6?

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

46. Предположим, безошибочный спутниковый канал с пропускной способностью 64 Кбит/c используется для пересылки 512-байтных фреймов данных в одном направлении с очень короткими подтверждениями, идущими в обратном направлении. Какова будет максимальная скорость передачи данных при размере окна, равном 1, 7, 15 и 127? Время распространения сигнала от Земли до спутника — 270 мс.

47. Кабель длиной в 100 км работает на скорости T1. Скорость распространения сигнала равна 2/3 от скорости света в вакууме. Сколько битов помещается в кабеле?

48. Назовите хотя бы одну причину, по которой в протоколе PPP применяется байт-стаффинг вместо бит-стаффинга (это предотвращает ошибку синхронизации фреймов из-за случайно встретившегося в поле данных флагового байта).

49. Каковы минимальные накладные расходы при пересылке IP-пакета по протоколу PPP? Учитывайте только накладные расходы самого PPP, а не заголовки IP. Каковы максимальные накладные расходы?

50. Следующий поток данных пересылается с помощью PPP по сетям SONET: ESC FLAG FLAG ESC. Какая последовательность байтов пересылается в качестве пользовательских данных? Напишите свой ответ в виде байтовых последовательностей, каждая из которых состоит из восьми единиц или нулей. ESC можно представить с помощью битовой последовательности 01111101, а FLAG — с помощью битовой последовательности 01111110.

51. IP-пакет длиной 100 байт передается по абонентскому шлейфу с использованием стека протоколов ADSL. Сколько ячеек ATM будет передано? Кратко опишите их содержимое.

52. Цель данного упражнения — реализация механизма обнаружения ошибок с помощью стандартного алгоритма циклического избыточного кода (CRC), описанного в тексте. Напишите две программы: генератор (generator) и верификатор (verifier). Программа-генератор считывает со стандартного устройства ввода n-битовое сообщение из нулей и единиц, представленных в виде строки ASCII-текста. Вторая строка является k-битовым многочленом (также в ASCII). На устройстве вывода мы получаем текст из n + k нулей и единиц, представляющий собой сообщение, подлежащее пересылке. Затем выводится многочлен — в том же виде, в каком он был считан. Программа-верификатор считывает результат работы генератора и выводит сообщение, в котором обозначено, корректен ли данный результат. После этого напишите программу alter, вносящую сбой, а именно инвертирующую только один бит первой строки в зависимости от аргумента (например, порядкового номера бита, предполагая, что слева располагается бит с номером 1). Все остальные данные передаются без изменений. Набрав

generator

пользователь должен увидеть сообщение о том, что данные переданы корректно. Набрав

generator

пользователь должен получить сообщение об ошибке при передаче.