Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 71
Текст из файла (страница 71)
Данные таймеров могут храниться в программе в виде связанного списка, каждый узел которого будет хранить количество временных интервалов системных часов, оставшихся до истечения срока ожидания, номер кадра и указатель на следующий узел списка. Указатель на следующий таймер Номер кадра Интервал времени в тиках Рис. 3.12. Программная симуляция работы нескольких таймеров 264 Глава 3. Уровень передачи данных В качестве иллюстрации приводится рис. 3.12, на котором показана программная реализация нескольких таймеров. Предположим, что часы изменяют свое состояние каждые 100 мс.
Пусть начальное значение реального времени будет 10:00:00.0, и имеются три таймера тайм-аутов, установленные на время 10:00:00.5, 10:00:01.3 и 10:00:01.9. Каждый раз, когда аппаратные часы изменяют свое значение, реальное время обновляется н счетчик этих изменений в голове списка уменьшается на единицу. Когда значение счетчика становится равным нулю, инициируется тайм-аут, а узел удаляется из списка, как показано на рис.
3.12, б. Такая организация таймеров не требует выполнения большой работы при каждолт прерывании от системных часов, хотя при работе процедур эсагс сгвег и асор глюег требуется сканирование списка. В протоколе у данных процедур имеется входной параметр, означающий номер кадра, таймер которого нужно запустить или остановить. Протокол с выборочным повтором Протокол 5 хорошо работает, если ошибки встречаются нечасто, однако при плохой линии он тратит впустую много времени, передавая кадры по два раза. В качестве альтернативы можно использовать протокол, в котором получатель буферизирует кадры, принятые после потерянного тши испорченного кадра.
Такой протокол не отвергает кадры только лишь потому, что предыдущий кадр был поврежден или потерян. В атом протоколе и отправитель, и получатель работают с окнами допустимых номеров кадров. Размер окна отправителя начинается с нуля и растет до некоторого определенного уровня, МАХ 5Еф Размер окна получателя, напротив, всегда фиксированного размера, равного МАХ 3ЕО, Получатель должен иметь буфер для каждого кадра, номер которого находится в пределах окна.
С кахсдым буфером связан бит, показывающий, занят буфер или свободен. Когда прибывает кадр, функция бегыееп проверяет, попал лп его порядковый номер в окно. Если да, то кадр принимается и хранится в буфере. Это действие производится независимо от того, является лн данный кадр следующим кадром, ожидаемым сетевым уровнем. Он должен храниться на уровне передачи данных до тех пор, пока все предыдущие кадры не будут переданы сетевому уровню в правильном порядке. Алгоритм протокола показан в листинге 3.7. Листинг 3.7. Протокол скользящего окна о выборочным повтором /* Протокол б (выборочный повтор) принимает кадры в любом порядке, но передает их сетевоиу уровню.
соблюдая порядок. Е какдын неподтвериденныи кадром связан таймер. При срабатывании таймера передается повторно тольно этот кадр, а не все неподтверкденные кадры. как в протоколе Б. */ Йеттпе МАХ 5ЕО 7 /* долине быть 2"и-1 */ обет)пе Ий ВЕЕ5 (<МАХ 5ЕО + 1)/2) гуребет елею 1)гаюе аргт'та), сизою егг, г)юеоог, пегыогк )ауег геабу. аск гтюеоы11 еуепт гуре; /)зпс)йбе "ргогосо).П" Протоколы скользящего окна 266 Ьоо1еап по паК = Сгце; /* отрицательное подтверждение (паК) еще не посылалось */ вец пг о1безС тгаае = МАХ 5ЕО+1: /* начальное значение для сииулятора */ всаС1с Ьоо!еап Ьесыееп(зец пг а, зец пг Ь, зец пг с) ( !* то же.
что и в протоколе 5. но короче и понятнее */ гесцгп ((а .= Ь) аа (Ь < с)) (( ((с < а) аа (а <= Ь)) (( ((Ь < с) ВВ (с < а)); всас1с чотб зепб сгаае([гаже к1пб тк. зец пг /гаже пг. зец пг /гаже ехрессеб, раскес Ьцт[егп) ( !* сформировать и поспать данные, а также положктельное или отрицательное подтверждение */ тпаав 5: /* вреиенная переиенная */ 5.К1пб = тК: /* К1пб == баса, асК.
или паК */ 1/ ((К =- баса) 5.1пто = Ьцттег[тгаае пг Х Ий ВОГ5]; 5.5ец = тгаае пг; /* ииеет значение только для инфориационных кадров */ 5.асК = (Ггаае ехрестеб ч МАХ 5ЕО) Ж (ИАХ 5ЕО + 1): 1[ (Фк = паК) по пак = та15е: !* один пак на кадр, пожалуйста */ Со рпу51са1 1ауег(аз): /* переслать кадр */ 1т (тК =- баСа) 5СагС С(аег(тгаае пг Ж Ий ВОГ5); 5Сор асК С1аег(): /* отдельный кадр с подтверждениеи не нужен */ епаЬ)е песыогК 1ауег(): асК ехресСеб = 0; */ пехС тгаае Со зепб = 0; тгаае ехрессеб = 0: Соо таг = Ий ВОГ5: пЬОТ[егеб = 0: /* инициализация */ /* следующий номер подтверждения во входнои потоке /* номер следующего посылаемого кадра */ /* ноиер следующего ожидаеиого входящего кадра */ !* верхний край окна получателя + 1 */ /* вначале буфер пуст */ Сот (т = 0; т < Ий ВОГ5; т~+) аггтчеб[1] = Га!зе: ып11е (Сгце) ( чотб рготосо16(чотб) ( вец пг асК ехрессеб; вей пг пехС )гаже со зепб; ве) пг тгаае ехрессеб: вей пг Соо таг: )пС т: Егаае г; расхеС оцС Ьцт[йй ВОГ5]: Раскет 1п Ьцт[йй ВОГ5]; Ьоо1еап аггтчеб[йй ВОГ5]: вец пг пбцттегеб: /* количество я/ ечепС Суре ечепС; /* нкжний край окна отправителя */ /* верхний край окна отправителя + 1 */ /* нижний край окна получателя */ /* верхний край окна получателя + 1 */ /* индекс пассива буферов */ /* вреиенная переиенная */ /* буферы для исходящего потока */ /* буферы для входящего потока */ /* входящая битовая карта */ использующихся в данный иомент выходных буферов 266 Главе 3.
Уровень передачи данных пбоггегеб = поогтегеб ч 1: /* увеличить окно отправителя */ Ггош не[носк 1ауегйооС бог[мех[ /гаже Со вепб Ж Ий ВОЕ51): /* получить новый пакет у сетевого уровня */ вепб /гаже(баСа. пехС /гаже то вепб, /гаже ехрессеб, оот Ьог); /* передать кадр */ тпс(пехт /гаже [о вепб); /* увеличить верхний край окна отправителя */ Ьгеаи: сазе /гаже аггтча1; /* прибыл кадр с данными ипи с подтверждением */ Ггош рпуз1са) 1ауег($г): /* получить пришедшкй кадр у физического уровня */ тг (г.й(пб =- бата) ( /* падр прибыл в целости */ 1Г ((г.зец != (гаже ехрестеб) Ы по пах) зепб (гаже(пай, О, /саше ехрес(еб, оо( Ьцг): е1ве з1агС асй Стшег(): тг (Ьетиееп((гаже ехрестеб, г.вец. Жоо Гаг) Вй (аггтчеб[г.вецЖИВ ВОЕ5) = Га1ве)) ( /* кадры могут приниматься в побои порядке */ агг1чеб[г.зец Ж ИД ВОЕ5) = Сгое: /* понетить буфер как занятый тп Ьц/[г.зец Ж ИИ ВОЕ5) = г.1п(о; /* поместить данные в буфер ипт1е (аггтчеб[(гаже ехрессеб Ж Ий ВОЕ53) ( /* передать пакет сетевоиу уровню и сдвинуть окно */ Со летиогк 1ауегйтп Ьо([/гаже ехрессеб Ж Ий ВОЕ5)); по пак = 1гое, аггтчеб[ггаше ехрестеб Ж Ий ВОЕ5) = Га1зе: тпс(/гаже ехресСеб]; /* передвинуть нижний нрай окна получателя *l 1пс(тоо Гаг): /* передвинуть верхний край окна получателя */ з1аг[ аск Стшег(); !* запустит~ вспоногательный тайиер на случай.
если потребуется пересылка подтверждения отдельным кадром */ ) ) 1/((г.й1пб==пай) аа Ьетиееп(ася ехресСеб (г.аси+1)Ж(НАХ 5ЕО+1).пехт Глаше Ьо зепб)) зепб /гаже(ба(а, (г.асяч1) Ж (МАХ 5ЕО г 1), /саше ехрестеб, оо[ Ьот); иб(1е (Ьетиееп(ася ехрес(еб г.ася, пехт /гале Со зепб)) ( пбоггегеб = пЬыйгегеб - 1: /* отправить подтверждение виесте с информационным кадрон */ з1ор стшег(асх ехрестеб ж ид Вце5); /* кадр прибыл в целости */ тпс(асц ехрессеб); /* передвинуть нижний край окна отправителя */ ) Ьгеая. иа11 Гог ечептйечепс): я/ ви1тсЬ(ечепс) ( саве песиогй 1ауег геабу: и/ /* пять возиожных событий; см.
ечепт суре выше /* получить. сохранить и передать новый кадр 268 Глава 3. уровень передачи данных Причина неудачи в том, что прп сдвиге приемного окна новый интервал допустимых номеров кадров перекрыл старый интервал. Соответственно, присылаемый набор кадров может содержать как новые кадры (если все подтверждения были получены), так и повторно высланные старые кадры (если подтверждения были потеряны). У принимающей стороны нет возможности отличить одну ситуацию от другой.
Решением данной проблемы является предоставление гарантии того, что в сдвинутом положении окно не перекроет исходное окно. Для этого размер окна не должен превышать половины от количества порядковых номеров (это показано на рис. 3.13, в и г). Например, если для порядковых номеров используются 4 бита, они должны изменяться в пределах от О до 15.
В таком случае в любой момент времени только восемь кадров могут быть неподтвержденными. Таким образом, если будут получены кадры с О по 7 и будет передвинуто окно для приема кадров с 8 по 15, получатель сможет безошибочно отличить повторную передачу (кадры с О по 7) от новых кадров (с 8 по 15). Поэтому в протоколе 6 применяется окно размером (МАХ 5ЕЯ + 1)/2. Возникает новый вопрос сколько буферов должно быть у получателя? Ни при каких условиях он не должен принимать кадры, номера которых не попадают в окно. Поэтому количество необходимых буферов равно размеру окна, а не диапазону порядковых номеров.
В приведенном выше примере для 4-битовых порядковых номеров требуется восемь буферов с номерами от О до 7. Когда прибывает кадр 1, он помещается в буфер ( шод 8. Обратите внимание на то, что хотя ( и (1+ 8), взятые по модулю 8, «соревнуются» за один и тот же буфер, они никогда не оказываются в одном окне одновременно, потому что это привело бы к увеличению размера окна по крайней мере до 9. По этой же причине количество необходимых таймеров также равно числу буферов, а не диапазону порядковых номеров.
Таким образом, удобно связать каждый таймер со своим буфером. Когда интервал времени истекает, содержимое буфера высылается повторно. В протоколе 5 предполагалось, что загрузка канала довольно высока. Когда прибывал кадр, он не подтверждался сразу. Вместо этого подтверждение «ехало верхом» на встречном информационном кадре. Если обратный поток информации был невелик, подтверждения задерживались на довольно большой период времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
