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 пользователь должен получить сообщение об ошибке при передаче. Глава 4. Подуровень управления доступом к среде Многие из протоколов канального уровня, о которых мы говорили в главе 3, рассчитаны на использование широковещательной среды для передачи данных. Они нуждаются в дополнительных механизмах, обеспечивающих эффективное и справедливое распределение канала между несколькими отправителями. Таким протоколам и посвящена эта глава. Главная проблема любой широковещательной сети — кому предоставить канал, если его запрашивают несколько пользователей. К примеру, представьте себе конференц-звонок, в котором принимают участие шесть человек с разных телефонов. Связь организована таким образом, что каждый может слышать всех собеседников и разговаривать с ними. Когда один из них закончит свою речь, весьма вероятно, что сразу двое или трое заговорят одновременно, тем самым создав неловкую ситуацию. При личной встрече это предотвращается внешними средствами. Например, на совещании можно поднять руку и получить разрешение высказаться. Когда доступен лишь один канал, гораздо труднее определить, кому предоставить слово. Для решения этой проблемы разработано множество протоколов. В литературе широковещательные каналы иногда называют каналами с множественным доступом (multiaccess channels) или каналами с произвольным доступом (random access channels). Протоколы, определяющие очередность использования линии, относятся к канальному уровню, точнее, к подуровню управления доступом к среде (MAC, Medium Access Control). MAC особенно важен в локальных сетях (LAN), в частности беспроводных, так как они по своей природе являются широковещательными. Глобальные сети (WAN) включают в себя как двухточечные компоненты (например, прямое подключение), так и компоненты с совместным использованием, осуществляемым с помощью MAC (например, кабельные сети общего доступа, предоставляемые интернет-провайдерами). В данной главе мы в общих чертах обсудим LAN (так как они тесно связаны с каналами множественного доступа), включая некоторые вопросы, которые не относятся к MAC напрямую. Главной темой будет управление каналом. Технически подуровень MAC является нижней частью канального уровня, и логичнее было бы изучить сначала его, а затем протоколы «точка-точка», рассмотренные в главе 3. Но намного легче сначала рассмотреть протоколы с двумя участниками, а потом — с несколькими. По этой причине мы слегка отклонимся от строгого следования снизу вверх по иерархической лестнице при рассмотрении уровней. 4.1. Проблема распределения канала Основная проблема, обсуждаемая в этой главе, — распределение одного широковещательного канала между претендующими на него многочисленными пользователями. Канал может быть частью беспроводного спектра в каком-нибудь регионе, отдельным проводом или оптоволоконным кабелем, к которому присоединено несколько узлов. Это не имеет значения. Во всех случаях он соединяет каждого пользователя со всеми остальными, и любой абонент, полностью нагружающий канал, мешает тем, кто тоже хочет передавать данные. Сначала мы в общих чертах рассмотрим недостатки статических схем распределения канала в случае неравномерного трафика. Затем изложим ключевые предположения, применяемые для моделирования динамических схем. После этого обсудим несколько примеров таких схем. 4.1.1. Статическое распределение канала Традиционный способ распределения канала (например, телефонной линии) между многочисленными конкурирующими пользователями — разделение его пропускной способности с помощью одной из схем мультиплексирования, рассмотренных нами в разделе 2.4.4 (например, FDM). При наличии N пользователей полоса пропускания делится на N диапазонов одинаковой ширины, и каждому пользователю предоставляется один из них. Поскольку при такой схеме у каждого пользователя своя личная частотная полоса, то конфликтов не возникает. При небольшом и постоянном числе абонентов, передающих стабильный поток или большие партии трафика, это простой и эффективный механизм распределения. Аналогичный пример для беспроводной связи — радиостанции FM-диапазона. Каждая станция получает часть FM-полосы и большую часть времени передает по ней свой сигнал. Однако при большом и постоянно меняющемся числе пользователей или неравномерном трафике FDM не обеспечивает достаточно эффективного распределения. Если в какой-то момент отправителей меньше, чем частей спектра, то значительная часть полосы пропускания простаивает. И наоборот, если пользователей больше, то некоторым из них придется отказать в доступе, даже если уже подключенные абоненты почти не используют канал. Предположим, что количество пользователей можно каким-то способом удерживать на постоянном уровне. Но и в этом случае разделение канала на статические подканалы неэффективно. Основная проблема в том, что если какие-то пользователи не передают данные, их часть спектра просто пропадает. При этом они занимают линию, и остальные абоненты не могут ее использовать. Статическое разделение не подходит для большинства компьютерных систем с чрезвычайно неравномерным потоком данных (вполне обычным является отношение пикового трафика к среднему как 1000:1). В результате большая часть каналов будет часто простаивать. Низкую эффективность статического FDM можно увидеть на примере простых вычислений теории массового обслуживания. Для начала подсчитаем среднее время задержки T для отправки фрейма по каналу емкостью C бит/с. Предполагается, что фреймы приходят в случайном порядке со средней скоростью λ фреймов в секунду. Длина фреймов варьируется и в среднем равна 1/μ бит. При таких параметрах скорость обслуживания канала равна μC фреймов в секунду. Теория массового обслуживания говорит о том, что