Э. Таненбаум - Компьютерные сети. (4-е издание) (PDF) (1130118), страница 68
Текст из файла (страница 68)
Все семь буферов помечаются как свободные.arrived[r.seq % NRJ3UFS] = true; /* пометить буфер как занятыйin_buf[r.seq % NRJ3UFS] = г.info: /* поместить данные в буферwhile (arrived[frame_expected % NR_BUFS]) {/* передать пакет сетевому уровню и сдвинуть окно */to_network_layer(&in_buf[frame_expected % NRJ3UFS]);nojiak = true:arrived[frame_expected % NR_BUFS] = false:получателя */inc(frame_expected): /* передвинуть нижний край окнаinc(too_far); /* передвинуть верхний край окна получателя*/start_ack_timer(); /* запустить вспомогательный таймер наслучай, если потребуется пересылка подтверждения отдельным кадром */}}frame_to_send))if(Cr.kind-nak) && between(ack_expected.(r.ack+l)UMAX_SEQ+l).next_send_frame(data.
(r.ack+1) % (MAX_SEQ + 1). frame_expected. out_buf);while (between(ack_expected. r.ack. next_frame_to_send)) {nbuffered = nbuffered - 1: /* отправить подтверждение вместе синформационным кадром */*,stop timerCack expected % NR_BUFS): /* кадр прибыл в целости /inc(ack_expectid); /* передвинуть нижний край окна отправителя /}break:Отправитель0 12 3 4 5 6 70 12 3 4 5 6 70 12 3 4 5 6 70 12 3 4 5 6 7Получатель0 12 3 4 50 12 3 4 50 12 3 4 5 6 70 12 3 4 5 6 7''— Рис. 3.13. Начальная ситуация при размере окна 7 (а); 7 кадров были посланы и приняты,но не подтверждены (б); начальная ситуация при размере окна 4 (в); ситуация после того,как 4 кадра были отправлены и получены, но не подтверждены (г)Именно в этот момент происходит какое-нибудь бедствие — например, молния ударяет в телефонный столб и стирает все подтверждения.
Отправитель, неДождавшись подтверждений, посылает повторно кадр 0. К сожалению, кадр 0 попадает в новое окно и поэтому принимается получателем (рис. 3.13, б). Получатель снова отправляет подтверждение для кадра 6, поскольку были приняты всекадры с 0 по 6.Отправитель с радостью узнает, что все переданные им кадры успешно достигли адресата, поэтому он тут же передает кадры 7, 0, 1, 2, 3, 4 и 5.
Кадр 7 принимается получателем, и содержащийся в нем пакет передается сетевому уровню.Сразу после этого принимающий уровень передачи данных проверяет наличиекадра 0, обнаруживает его и передает внедренный пакет сетевому уровню. Такимобразом, сетевой уровень получает неверный пакет; это означает, что протоколсо своей задачей не справился.268Глава 3. Уровень передачи данныхПричина неудачи в том, что при сдвиге приемного окна новый интервал допустимых номеров кадров перекрыл старый интервал. Соответственно, присылаемый набор кадров может содержать как новые кадры (если все подтверждениябыли получены), так и повторно высланные старые кадры (если подтверждениябыли потеряны).
У принимающей стороны нет возможности отличить одну ситуацию от другой.Решением данной проблемы является предоставление гарантии того, что в сдвинутом положении окно не перекроет исходное окно. Для этого размер окна недолжен превышать половины от количества порядковых номеров (это показанона рис. 3.13, в и г). Например, если для порядковых номеров используются 4 бита, они должны изменяться в пределах от 0 до 15. В таком случае в любой момент времени только восемь кадров могут быть неподтвержденными. Таким образом, если будут получены кадры с 0 по 7 и будет передвинуто окно для приемакадров с 8 по 15, получатель сможет безошибочно отличить повторную передачу(кадры с 0 по 7) от новых кадров (с 8 по 15).
Поэтому в протоколе 6 применяетсяокно размером (MAX_SEQ + 1 )/2.Возникает новый вопрос: сколько буферов должно быть у получателя? Нипри каких условиях он не должен принимать кадры, номера которых не попадают в окно. Поэтому количество необходимых буферов равно размеру окна, а недиапазону порядковых номеров. В приведенном выше примере для 4-битовыхпорядковых номеров требуется восемь буферов с номерами от 0 до 7. Когда прибывает кадр г, он помещается в буфер г mod 8. Обратите внимание на то, что хотяi и (г + 8), взятые по модулю 8, «соревнуются» за один и тот же буфер, они никогда не оказываются в одном окне одновременно, потому что это привело бы кувеличению размера окна по крайней мере до 9.По этой же причине количество необходимых таймеров также равно числубуферов, а не диапазону порядковых номеров.
Таким образом, удобно связатькаждый таймер со своим буфером. Когда интервал времени истекает, содержимое буфера высылается повторно.В протоколе 5 предполагалось, что загрузка канала довольно высока. Когдаприбывал кадр, он не подтверждался сразу. Вместо этого подтверждение «ехаловерхом» на встречном информационном кадре. Если обратный поток информации был невелик, подтверждения задерживались на довольно большой периодвремени. Если в одном направлении посылалось много информации, а во встречном — вообще ничего, то высылалось только MAX__SEQ пакетов, после чего протокол останавливался.В протоколе 6 эта проблема решена.
По прибытии кадра с данными процедура start_ack_timer запускает вспомогательный таймер. Если таймер сработаетраньше, чем появится кадр с данными для передачи, то будет послан отдельныйкадр с подтверждением. Прерывание от вспомогательного таймера называетсясобытием ack_timeout. При такой организации возможен однонаправленный поток данных, так как отсутствие встречных информационных кадров, на которыхможно было бы отправлять подтверждения, больше не является препятствием.Для этого требуется всего один таймер. При вызове процедуры start_ack_timer,Протоколы скользящего окна269если таймер уже был запущен, его параметры переустанавливаются на отсчетполного интервала времени.Важно, что период времени вспомогательного таймера должен быть существенно короче интервала ожидания подтверждения.
При этом условии подтверждение в ответ на полученный правильный кадр должно приходить прежде, чему отправителя истечет период ожидания и он пошлет этот кадр второй раз.Протокол б использует более эффективную стратегию обработки ошибок, чемпротокол 5. Как только у получателя появляются подозрения, что произошлаошибка, он высылает отправителю отрицательное подтверждение (NAK). Получатель может делать это в двух случаях: если он получил поврежденный кадрили если прибыл кадр с номером, отличным от ожидаемого (возможность потери кадра).
Чтобы избежать передачи нескольких запросов на повторную передачу одного и того же кадра, получатель должен запоминать, был ли уже посланNAK для данного кадра. В протоколе 6 для этой цели применяется переменнаяno_nak, принимающая значение true, если NAK для ожидаемого кадра (с номеромf rame_expected) еще не был послан. Если NAK повреждается или теряется по дороге, в этом нет большой беды, так как у отправителя в конце концов истечет периодожидания положительного подтверждения и он, так или иначе, вышлет недостающий кадр еще раз. Если после того как NAK будет выслан и потерян прибудет не тот кадр, переменной no_nak опять будет присвоено true и будет запущенвспомогательный таймер.
Когда время истечет, будет послано положительноеподтверждение (АСК) для восстановления синхронизации текущих состоянийотправителя и получателя.В некоторых ситуациях время, необходимое для прохождения кадра по каналу,его обработки и отсылки обратно подтверждения, остается практически неизменным. В таких ситуациях отправитель может поставить время ожидания несколькобольше ожидаемого интервала между отправкой кадра и получением подтверждения. Однако если это время меняется в широких пределах, перед отправителемвозникает непростой выбор значения времени ожидания. Если выбрать слишкомкороткий интервал, то увеличится риск ненужных повторных передач, следовательно, снизится производительность канала.
При выборе слишком большогозначения протокол будет тратить много времени на ожидания, что также снизитпропускную способность.В любом случае пропускная способность на что-то тратится. Если встречныйпоток данных нерегулярен, то время прихода подтверждений также будет непостоянным, уменьшаясь при наличии встречного потока и увеличиваясь при егоотсутствии. Переменное время обработки кадров получателем также может вызвать ряд проблем.
Итак, если среднеквадратичное отклонение интервала ожидания подтверждения невелико по сравнению с самим интервалом, то таймер можетбыть установлен довольно «туго» и польза от отрицательных подтверждений(NAK) не очень высока. В противном случае таймер может быть установлен довольно «свободно», и отрицательные подтверждения могут существенно ускорить повторную передачу потерянных или поврежденных кадров.С вопросом тайм-аутов и отрицательных подтверждений тесно связана проблема определения кадра, вызвавшего тайм-аут. В протоколе 5 это всегда кадр270Глава 3. Уровень передачи данныхс номером ack_expected, поскольку он является старшим.
В протоколе 6 нет стольпростого способа определить кадр, интервал ожидания которого истек. Предположим, были переданы кадры с 0 по 4, то есть список неподтвержденных кадроввыглядит так: 01234 (от первого к последнему). Теперь допустим, что у кадра Оистекает интервал ожидания и он передается повторно, затем посылается кадр 5(новый), потом интервал ожидания истекает у кадров 1 и 2, и посылается кадр 6(также новый). В результате список неподтвержденных кадров принимает вид3405126, начиная с самого старого и заканчивая самым новым.
Если весь встречный поток данных потеряется, интервалы ожидания этих семи кадров истекутименно в таком порядке. Чтобы не усложнять и без того непростой пример протокола, мы не показываем подробностей управления таймером. Вместо этого предполагается, что переменной oldest_frame при наступлении тайм-аута присваивается номер кадра, интервал времени которого истек.Верификация протоколовРеальные протоколы и реализующие их программы обычно весьма сложны.
Поэтому множество исследователей посвятили свои труды попыткам применить формальные математические методы для задания и проверки (верификации) протоколов. В следующих разделах мы обсудим некоторые модели и методы. Хотя мыбудем рассматривать их в контексте уровня передачи данных, они применимы и кдругим уровням.Модели конечных автоматовКлючевой концепцией, используемой в моделях протоколов, является модель конечных автоматов. Данный метод рассматривает состояния, в которых находитсяпротокольная машина (то есть отправитель или получатель) в каждый моментвремени. Состояние протокольной машины включает в себя значения всех ее переменных, в том числе и программные счетчики.В большинстве случаев многие состояния можно объединить для анализа вгруппы. Например, рассматривая получателя в протоколе 3, мы можем выделитьиз всех его возможных состояний два самых важных: ожидание кадра 0 и ожидание кадра 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
