Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 72
Текст из файла (страница 72)
Если в одном направлении посылалось много информации, а во встречном — вообще ничего, то высылалось только МАХ БЕЯ пакетов, после чего протокол останавливался. В протоколе 6 эта проблема решена. По прибытии кадра с данными процелура а1агг ас1 1твег запускает вспомогательный таймер. Если таймер сработает раньше, чем появится кадр с данными для передачи, то будет послан отдельный кадр с полтверждением.
Прерывание от вспомогательного таймера называется событием ась 11ееоо1. При такой организации возможен однонаправленный поток данных, так как отсутствие встречных информационных кадров, на которых можно было бы отправлять подтверждения, больше не является препятствием. Для этого требуется всего один таймер. При вызове процедуры згагг асл п(тег, Протоколы скользящего окна 269 если таймер уже был запущен, его параметры переустанавливаются на отсчет полного интервала времени. Важно, что период времени вспомогательного таймера должен быть существенно короче интервала ожидания подтверждения. При этом условии подтверждение в ответ на полученный правильный кадр должно приходить прежде, чем у отправителя истечет период ожидания н он пошлет этот кадр второй раз, Протокол 6 использует более эффективную стратегию обработки ошибок, чем протокол 5.
Как только у получателя появляются подозрения, что произошла ошибка, он высылает отправителю отрицательное подтверждение (г(АК). Получатель может делать это в двух случаях: если он получил поврежденный кадр или если прибыл кадр с номером, отличным от ожидаемого (возможность потери кадра). Чтобы избежать передачи нескольких запросов на повторную передачу одного и того же кадра, получатель должен запоминать, был ли уже послан МАК для данного кадра.
В протоколе 6 для этой цели применяется переменная ло пзк, принимающая значение ггзе, если МАК для ожидаемого кадра (с нолшром тгаае ехрес~е0) еще не был послан. Если МАК повреждается или теряется по дороге, в этом нет большой беды, так как у отправителя в конце концов истечет период ожидания положительного подтверждения и он, так нли иначе, вышлет недостающий кадр еще раз. Если после того как МАК будет выслан и потерян прибудет не тот кадр, переменной по пзк опять будет присвоено ~гзе и будет запущен вспомогательный таймер. Когда время истечет, будет послано положительное подтверждение (АСК) для восстановления синхронизации текущих состояний отправителя и получателя, В некоторых ситуациях время, необходимое для прохождения кадра по каналу, его обработки и отсылки обратно подтверждения, остается практически неизменным.
В таких ситуациях отправитель может поставить время ожидания несколько больше ожидаемого интервала между отправкой кадра и получением подтверждения. Однако если это время меняется в широких пределах, перед отправителем возникает непростой выбор значения времени ожидания. Если выбрать слишком короткий интервал, то увеличится риск ненужных повторных передач, следовательно, снизится производительность канала. При выборе слишком большого значения протокол будет тратить много времени на ожидания, что также снизит пропускную способность.
В любом случае пропускная способность на что-то тратится. Если встречный поток данных нерегулярен, то время прихода подтверждений также будет непостоянным, уменьшаясь при наличии встречного потока и увеличиваясь при его отсутствии. Переменное время обработки кадров получателем также может вызвать ряд проблем. Итак, если среднеквадратичное отклонение интервала ожидания подтверждения невелико по сравнению с самим интервалом, то таймер может быть установлен довольно «тугое и польза от отрицательных подтверждений (МАК) не очень высока.
В противном случае таймер может быть установлен довольно «свободно», и отрицательные подтверждения могут существенно ускорить повторную передачу потерянных или поврежденных кадров. С вопросом тайм-аутов и отрицательных подтверждений тесно связана проблема определения кадра, вызвавшего тайм-аут. В протоколе 5 это всегда кадр 270 Глава 3. Уровень передачи данных с номером эс1 ехрес1ед, поскольку он является старшим. В протоколе 6 нет столь простого способа определить кадр, интервал ожидания которого истек, Предположим, были переданы кадры с 0 по 4, то есть список неподтвержденных кадров выглядит так: 01234 (от первого к последнему). Теперь допустим, что у кадра 0 истекает интервал ожидания и он передается повторно, затем посылается кадр 5 (новый), потом интервал ожидания истекает у кадров 1 и 2, и посылается кадр 6 (также новый).
В результате список неподтвержденных кадров принимает вид 3405126, начиная с самого старого и заканчивая самым новым. Если весь встречный поток данных потеряется, интервалы ожидания этих семи кадров истекут именно в таком порядке. Чтобы не усложнять и без того непростой пример протокола, мы не показываем подробностей управления таймером. Вместо этого предполагается, что переменной о14ез1 ггэае при наступлении тайм-аута присваивается номер кадра, интервал времени которого истек.
Верификация протоколов Реальные протоколы н реализующие их программы обычно весьма сложны. Поэтому множество исследователей посвятили свои труды попыткам применить формальные математические методы для задания и проверки (верификации) протоколов. В следующих разделах мы обсудим некоторые модели и методы.
Хотя мы будем рассматривать их в контексте уровня передачи данных, они применимы и к другим уровням. Модели конечных автоматов Ключевой концепцией, используемой в моделях протоколов, является модель конечных автоматов. Данный метод рассматривает состояния, в которых находится протокольная машина (то есть отправитель или получатель) в каждый момент времени. Состояние протокольной машины включает в себя значения всех ее переменных, в том числе и программные счетчики.
В большинстве случаев многие состояния можно объединить для анализа в группы. Например, рассматривая получателя в протоколе 3, мы можем выделить из всех его возможных состояний два самых важных; ожидание кадра 0 и ожидание кадра 1. Все остальные состояния могут рассматриваться как временные, промежуточные между этими двумя. Обычно выбираются состояния, соответствующие ожидаемым событиям (это соответствует вызову процедуры нэ11(ечепг) в наших примерах протоколов).
Состояние протокольной машины полностью опРеделяется состоянием ее переменных. Количество состояний равно 2", где л— количество битов, необходимых для описания всех переменных, вместе взятых. Состояние всей системы представляет собой комбинацию всех состояний двух протокольных машин и состояний канала, Состояние канала определяется его содержимым. При использовании протокола 3 у канала может быть четыре возможных состояния: кадр 0 или кадр 1, перемещающийся от отправителя к получателю, калр подтверждения, двигающийся в противоположном направлении, илн Верификация протоколов 271 пустой канал. Если отправитель и получатель могут находиться в двух различных состояниях, то вся система будет иметь ) 6 различных состояний.
Следует сказать несколько слон о состоянии канала. Концепция кадра, находящегося в канале, конечно, является абстракцией. Имеется в виду, что кадр частично передан, частично принят, но егце не обработан получателем. Кадр остается чв канале» до тех пор, пока протокольная машина не выполнит процедуру (гоа рпуз1са1 1зуег и не обработает его. Каждое состояние может быть соединено с другими состояниями несколькими (О или больше) переходами.
Переходы всегда соответствуют каким-либо событиям. Для протокольной машины переход происходит, когда прибывает новый кадр, истекает время ожидания какого-либо таймера, происходит прерывание и т. д, Для канала обычными событиями являются следующие: помещение протокольной машиной в канал нового кадра, доставка кадра протокольной машине или потеря кадра вследствие всплеска шума. Имея полное описание протокольной машины и характеристик канала, можно нарисовать направленный граф, изображающий все состояния в виде узлов, а переходы — в виде направленных дуг. Одно особое состояние обозначается как начальное.
Оно соответствует состоянию системы в момент ее запуска или состоянию, близкому к нему. Из начального состояния можно попасть во многие (вероятно, даже во все) другие состояния с помощью серии переходов. Применяя хорошо известные методы теории графов (например, вычисляя транзитивное замыкание графа), можно определить, какие из состояний достижимы, а какие нет. Такой метод называется анализом достижимости (Ып и др., 1987).
Данный анализ может быть полезен для определения правильности протокола. Формально модель протокола машины конечных состояний можно рассматривать как набор цх четырех множеств (5, М, 1, Т), где 5 — множество состояний, в которых могут находиться процессы и канал; М вЂ” множество кадров, передаю- шихся по каналу; 1 — множество начальных состояний процессов; 7' — множество переходов между состояниями. В начальный момент времени все процессы находятся в исходном состоянии.
Затем начинают происходить события — например, появляются кадры, которые нужно передать по каналу, или срабатывает таймер. Каждое событие может переключить один из процессов или канал в новое состояние. Тщательно нумеруя все возможные предшественники каждого состояния, можно построить лерево достижимости и проанализировать протокол.
Анализ достижимости может применяться для обнаружения разнообразных ошибок спецификации протокола. Например, если какой-либо кадр может оказаться в таком состоянии, в котором конечный автомат не сможет определить, какое действие следует предпринять, зто означает, что спецификация ошибочна (неполнота протокола). Если имеется ряд состояний, из которых нет выхода (то есть никакие кадры больше не смогут передаваться), это также означает ошибку спецификации (тупик). Менее серьезной ошибкой спецификации протокола является описание обработки события в состоянии, в котором это событие не может произойти (лишний переход). Могут быть обнаружены и другие ошибки.
272 Глава 3. Уровень передачи данных В качестве примера конечного автомата рассмотрим рис. 3.14, а. Этот граф соответствует протоколу 3, описанному ранее, — у каждой протокольной машины может быть два состояния, а у канала — четыре состояния. Итого возможны 10 состояний, некоторые из которых недоступны из начального состояния.
Недостижимые состояния не показаны на рисунке. Для упрощения также опущены ситуации с ошибками контрольных сумм. Каждое состояние помечено тремя символами: 5ЛС, где 5 является 0 илп 1 и соответствует номеру кадра, который пытается послать отправитель; Д также может быть равно 0 или 1 и означает номер кадра, ожидаемого получателем, а С может принимать значения О, 1, А или пусто (-), в соответствии с состоянием канала. В данном примере было выбрано исходное состояние (000). То есть отправитель только что послал кадр О, получатель ожидает кадра О, и кадр 0 находится в канале. Кедр Кадр принят передан (кадр потерян) о Подтверждение Подтверждение 1 1 Подтверждение Подтверждение 0 0 Подтверждение 1 Подтверждение (тайм-аут) о (тайм-аут) 1 Сетевому уровню Кто Переход управляет г Да Получатель Отправитель Получатель Отправитель Получатель Получатель Отправитель Отправитель Да Нет Нет РИО.
3.14. ДИаГраММа СОСтсяНИй дпя ПрстОКОЛа 3 (а); ПЕрЕХОдЫ (о) На рис. 3.14 показаны девять типов переходов. Переход 0 заключается в потере каналом содержимого, Переход 1 состоит в том, что канал успешно доставляет пакет 0 получателю, при этом получатель передает пакет 0 своему се- Верификация протоколов 273 тевому уровню, изменяет свое состояние на ожидание кадра 1 и пересылает п~дтверждение. Остальные переходы приведены на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
