Э. Таненбаум, Д. Уэзеролл - Компьютерные сети (1114668), страница 80
Текст из файла (страница 80)
Последние два протокола используют конвейерную передачу множества кадров, чтобы отправитель не блокировался, увеличиваязадержку передачи. Получатель может либо отбрасывать все кадры, за исключениемочередного в последовательности, либо помещать неупорядоченные кадры в буфери отправлять отрицательные подтверждения для более эффективного использованияполосы пропускания. Первая стратегия называется протоколом с возвратом на n,а вторая — протоколом с выборочным повтором.В Интернете в качестве основного протокола линий «точка������������������� ������������������— точка» используется PPP. Он предоставляет сервис без установки соединения и без подтверждения.Для разделения кадров применяются флаговые байты, а для распознавания ошибок —коды CRC. С помощью этого протокола пакеты передаются по множеству типовсоединений, включая каналы SONET в глобальных сетях и ADSL для домашнихподключений.Вопросы 277Вопросы1.
Сообщение верхнего уровня разбито на 10 кадров, у каждого из которых шанс дойти доназначения без повреждений составляет 80 %. Если канальный уровень не обеспечиваетпроверки ошибок, сколько раз в среднем потребуется пересылать все сообщение?2. В протоколе канального уровня используется следующее кодирование символов:A: 01000111; B: 11100011; FLAG: 01111110; ESC: 11100000Как в двоичных кодах будет выглядеть кадр, состоящий из четырех символов —A B ESC FLAG, при использовании каждого из следующих методов кадрирования:1) подсчет байтов;2) флаговые байты с символьным заполнением;3) начальные и конечные флаговые байты с битовым заполнением.3. В потоке данных, для которого применяется алгоритм символьного заполнения, встречаетсяследующий фрагмент данных: A B ESC C ESC FLAG FLAG D.
Каким будет выходной потокпосле заполнения символами?4. Каковы максимальные накладные расходы для алгоритма символьного заполнения?5. Один из ваших однокурсников, большой скряга, предположил, что использовать послеконцевого флагового байта кадра начальный флаговый байт следующего кадра — слишкомрасточительно, вполне можно обойтись флаговым байтом.
Таким образом, можно сэкономить передачу одного байта. Вы согласитесь с ним?6. Каким будет на выходе следующий поток бит после применения битового заполнения науровне передачи данных: 0111101111101111110?7. При каких обстоятельствах протокол без обратной связи (например, с кодом Хэмминга)может быть предпочтительнее протоколов с обратной связью, обсуждаемых в данной главе?8. Для обеспечения большей надежности, нежели та, которую предоставляет единственныйбит четности, в некотором методе обнаружения ошибок один бит четности суммирует всечетные биты, а другой — все нечетные. Каково будет в этом случае расстояние кода поХэммингу?9.
При помощи кода Хэмминга передаются 16-битные сообщения. Сколько контрольных битпотребуется для того, чтобы приемник гарантированно мог обнаруживать и исправлять одиночные битовые ошибки? Как будет выглядеть код для передачи следующего сообщения:1101001100110101? Предполагается, что код Хэмминга использует проверку четных бит.10. Приемник получает 12-битную последовательность в коде Хэмминга, ее шестнадцатеричноезначение равно 0������������������������������������������������������������������xE����������������������������������������������������������������4���������������������������������������������������������������F��������������������������������������������������������������.
Как (в шестнадцатеричном виде) выглядела исходная последовательность? Предполагается, что ошибочным может быть только 1 бит.11. Один из способов обнаружения ошибок заключается в передаче данных в виде блокаиз n рядов по k бит с добавлением битов четности к каждому ряду и каждой строке. Битв нижнем правом углу — это бит четности, проверяющий свою строку и столбец. Будет литакая схема обнаруживать все одиночные ошибки? Двойные ошибки? Тройные ошибки?Докажите на примере, что эта схема не в состоянии обнаруживать некоторые четырехбитные ошибки.12.
Предположим, что данные передаются в блоках размером 1000 бит. Каков максимальныйкоэффициент ошибок, при котором механизм с обнаружением ошибок и повторной передачей (1 бит четности на блок) покажет себя лучше, чем код Хэмминга? Предполагается,что ошибки в битах не зависят друг от друга, а во время повторной передачи ошибок в битахне бывает.278 Глава 3.
Канальный уровень13. В блоке битов из n рядов и k строк используются горизонтальные и вертикальные битычетности для обнаружения ошибок. Какова вероятность того, что инверсия 4 бит не будетобнаружена?14. Используя сверточный кодировщик, показанный на рис. 3.7, покажите выходную последовательность для входной последовательности 10101010 (слева направо) и нулевоговнутреннего состояния.15. Предположим, что сообщение 1001 1100 1010 0011 передается с использованием контрольной суммы для Интернета (4-битное слово). Какова будет контрольная сумма?16. Чему равен остаток от деления x7 + x 5 + 1 на образующий многочлен x 3 + 1?17. Поток бит 10011101 передается с использованием стандартного метода циклического избыточного кода (CRC), описанного в тексте. Образующий многочлен равен x 3 + 1.
Какаябитовая последовательность будет реально передаваться? Предполагается, что третий битслева при передаче инвертировался. Докажите, что эта ошибка будет обнаружена приемником. Приведите пример ошибок в битах передаваемой строки, которые приемникобнаружить не сможет.18. Отправляется 1024-битное сообщение, содержащее 992 бита данных и 32 бита CRC. КодCRC вычисляется с использованием стандартизированного в IEEE 802 многочлена 32 степени. Для каждого из следующих случаев объясните, распознает ли получатель ошибкипередачи сообщения:1) произошла 1-битная ошибка;2) произошли 2 изолированные 1-битные ошибки;3) произошло 18 изолированных 1-битных ошибок;4) произошло 47 изолированных 1-битных ошибок;5) произошла последовательность ошибок длиной 24 бита;6) произошла последовательность ошибок длиной 35 битов.19.
При обсуждении протокола ARQ приводился пример сценария, в котором получательпринимает две копии одного и того же кадра из-за утери кадра подтверждения. Возможноли, что получатель примет несколько копий одного кадра, если ни один из кадров (данныхили подтверждения) утерян не будет?20. Скорость передачи данных в канале составляет 4 Кбит/с, а время распространения сигнала — 20 мс.
При каком размере кадров эффективность протокола с ожиданиями составит,по меньшей мере, 50 % ?21. Возможно ли, что в протоколе 3 отправитель запустит таймер, когда тот уже работает? Еслида, то в какой ситуации? Если нет, то почему?22. Кабель T1 длиной 3000 км используется для передачи 64-байтовых кадров при помощипротокола 5. Если задержка распространения сигнала составляет 6 мкс/км, сколько битследует отвести на порядковые номера кадров?23. Представьте себе протокол скользящего окна, в котором используется так много бит напорядковые номера кадров, что номера никогда не используются дважды. Какое соотношение должно связывать четыре границы окна и размер окна (постоянный и одинаковыйдля отправителя и получателя)?24.
Предположим, что в процедуре between протокола 5 вместо условия a ≤ b < c проверяетсяусловие a ≤ b ≤ c. Как это повлияет на правильность протокола и его эффективность? Поясните свой ответ.25. Когда прибывает информационный кадр, протокол 6 проверяет, отличается ли номер кадраот ожидаемого и равна ли переменная no_nak значению true.
При выполнении обоих условийВопросы 279посылается NAK. В противном случае запускается вспомогательный таймер. Предположим,что в тексте программы пропущен оператор else. Повлияет ли это на правильность работыпротокола?26. Предположим, что из конца текста программы протокола 6 удалены три строки цикла while.Повлияет ли это на правильность работы протокола или же только на его быстродействие?Поясните свой ответ.27. Расстояние от Земли до далекой планеты равно приблизительно 9 × 1010 м.
Если в канале«точка-точка» со скоростью передачи данных 64 Мбит/с для пересылки кадров применяетсяпротокол с остановкой и ожиданием, то каков коэффициент загруженности канала? Предполагается, что размер кадра равен 32 Кбайт, а скорость света равна 3 × 108 м/с.28. В условиях предыдущей задачи используется другой протокол — протокол скользящегоокна. В случае какого размера окна отправителя коэффициент загруженности каналабудет равен 100 %? Время на обработку протокола на отправителе и получателе можно неучитывать.29. В протоколе 6 в программе, обрабатывающей событие прихода кадра frame_arrival, естьраздел, используемый для отрицательных подтверждений (NAK).
Этому участку программы передается управление, когда получаемый кадр является NAK, а также при выполнениидругого условия. Приведите пример сценария, в котором наличие этого условия являетсяважным.30. Протокол 6 применяется на безошибочной линии со скоростью 1 Мбит/с. Максимальныйразмер кадра 1000 бит. Новые пакеты формируются примерно раз в секунду. Интервалтайм-аута установлен на период 10 мс. Если отключить специальный таймер подтверждений, то будут происходить лишние тайм-ауты. Сколько раз в среднем будет передаватьсяодно сообщение?31.
В протоколе 6 значение MAX_SEQ = 2n – 1. Хотя это условие, очевидно, желательно дляэффективного использования битов заголовка, важность его не была показана. Будет липротокол корректно работать, например, при MAX_SEQ = 4?32. Кадры длиной 1000 бит посылаются по спутниковому каналу с пропускной способностью1 Мбит/с и временем прохождения 270 мс. Подтверждения всегда посылаются в информационных кадрах.
Заголовки кадров очень короткие. Используются 3-битовые порядковые номера. Какой будет максимальная эффективность использования канала при применении:• протокола с остановкой и ожиданием;• протокола 5;• протокола 6.33. Рассчитайте, какая часть пропускной способности канала теряется на заголовки и повторные передачи при использовании протокола 6 на сильно загруженном спутниковом каналес пропускной способностью 50 Кбит/с. Кадры данных состоят из 40-битовых заголовкови 3960 бит данных. Время распространения сигнала от Земли до спутника составляет270 мс. Кадры ACK никогда не посылаются.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
