Главная » Просмотр файлов » Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU)

Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 72

Файл №1130092 Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU)) 72 страницаЭ. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092) страница 722019-05-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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 и пересылает п~дтверждение. Остальные переходы приведены на рис.

Характеристики

Тип файла
DJVU-файл
Размер
10,09 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее