Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 27
Текст из файла (страница 27)
Из инварианта P следует, что отправление пакета hpack, w, iiпроцессом p допустимо только тогда, когда i < ap + L.В заключение этого параграфа мы обсудим коротко допущения F1 и F2. Допущение F2 представляет собой минимальное требование, которое предъявляетсяк качеству канала связи, соединяющего процессы p и q, для того чтобы по этомуканалу мог осуществляться обмен данными.
Очевидно, что если какое-нибудьслово inp [i] нельзя передать по этому каналу, то обеспечить его неизбежную доставку невозможно. Допущение F1 обычно реализуется в протоколе посредствомусловия тайм-аута: если значение переменной ap не увеличивается на протяжении определенного отрезка времени, то сообщение in p [ap ] передается повторно.Как уже было упомянуто во введении в настоящую главу, обосновать свойствобезопасности для рассматриваемого протокола можно без привлечения понятиявремени.Д о к а з а т е л ь с т в о. Действие Sp сопровождается логическим условиемi < sp + lp ; выполнимость этого условия, как следует из леммы 3.3, влечет засобой выполнимость неравенства i < ap + L.Лемма 3.7. Из инварианта P следует, что в том случае, когда outp [i] 6== udef, выполняется неравенство i < sp + L.Д о к а з а т е л ь с т в о.
Согласно свойству (2p) справедливо соотношениеap > i − lq . Выполнимость соотношения i < ap + lq , как следует из леммы 3.3,влечет выполнимость неравенства i < ap + L.Эти две леммы приводят нас к следующей схеме, изображенной на рис. 3.2.Процесс p должен хранить в памяти только слова из отрезка in p [ap ..sp + lp − 1] ,поскольку он может отправлять только эти слова. Указанный отрезок назовемокном передачи процесса p (на рис. 3.2 оно обозначено буквами S). Как только значение переменной ap увеличивается, p избавляется от тех слов, которыевыходят за рамки окна передачи (на рис. 3.2 они обозначено буквами A).
Кактолько значение переменной sp увеличивается, p прочитывает следующие словав окне отправления из того источника, который генерирует эти слова. Согласнолемме 3.6 окно отправления процесса p содержит не более L слов.inpA A A A S S S SpinqA A A S S S SQ?. . .
. . . . . . . p. . . . . . . . . . . . ?q. . . . . . . . . . . . . . . . . . . . ..Qq3.1.3. Обсуждение протоколаОграничение памяти процессов. Алгоритм 3.1 в том виде, в котором он былпредставлен, непригоден для реализации в компьютерных сетях, ввиду того чтов каждом процессе хранится бесконечный объем информации (массивы in и out),а так же потому, что в нем используются неограниченные порядковые номера.1) Доказательство проведено не вполне корректно.
Из приведенных рассуждений всего лишь следует, что в каждом вычислении значение хотя бы одной из переменных sp или sq будет увеличиватьсябесконечно часто, в то время как нам нужно показать, что это будет иметь место сразу для обеих переменных. Все дело в том, что в предложенном доказательстве «от противного» было сделаноневерное допущение. Правильнее было бы предположить, что существует вычисление C, в которомзначения хотя бы одной из переменных sp и sq увеличиваются лишь конечное число раз.
Тогда,согласно лемме 3.3 значение другой переменной также не может увеличиваться бесконечно часто.Далее по тексту.— Прим. перев.?W W W W W W W u u R R u outpA = Сброшенный входS = Окно передачиW = Записанные словаR = Принятые слова?outq W W W W u R R u u u u uu = Неопределенные значения= Окно передачи/приемаРис. 3.2. Протокол раздвижного окнаПодобного же рода доводы позволяют ограничить объем памяти, необходимый процессу p для хранения массива outp . Коль скоро значения тех элементовoutp [i] , для которых выполняется неравенство i < s p , остаются неизменными,96Гл. 3. Коммуникационные протоколы3.1. Симметричный протокол раздвижного окнаможно предположить, что процесс p проводит окончательную выдачу этих слови перестает хранить их в памяти (на рис. 3.2 эти слова обозначены буквами W).Коль скоро outp [i] = udef для всех тех i, для которых выполняется неравенствоi > sp + L, эти элементы массива outp [i] также не нужно хранить в памяти процесса.
Отрезок массива outp [sp ..sp + L − 1] назовем окном приема процесса p.Окно приема обозначено на рис. 3.2 буквами u для тех элементов, значение которых еще не определено, и буквами R для тех слов, которые уже были получены.В памяти процесса хранятся только те слова, которые находятся в рамках окнаприема. Леммы 3.6 и 3.7 свидетельствуют о том, что каждый процесс в любоймомент времени хранит не более 2L слов.Ограничение порядковых номеров. Наконец, мы покажем, что в том случае, если каналы поддерживают очередность передачи сообщений, порядковыеномера слов также можно ограничить.
Воспользовавшись гипотезой об очередности передачи сообщений, можно показать, что порядковый номер пакета, который получает процесс p, отстоит от значения переменной s p не более чем на 2L.Мы обращаем внимание читателей на то, что это первый случай, когда нам пришлось обратиться к допущению об очередности передачи сообщений.Rp : Чтобы убедиться, что действие Rp сохраняет выполнимость условий (4p)и (4q), заметим, что Rp не добавляет никаких пакетов ни в очередь Q p , ни вочередь Qq .Чтобы убедиться, что действие Rp сохраняет выполнимость условия (5p), заметим, что при увеличении значения переменной a p (после приема пакета hpack, w0 , i0 i)до величины i0 − lq + 1 для всех оставшихся пакетов hpack, w, ii из очереди Q pбудет выполняться неравенство i > i0 − L (в силу свойства (4p)).
Следовательно, неравенство i > ap − lp сохраняет свою выполнимость и после увеличениязначения переменной ap .Чтобы убедиться, что действие Rp сохраняет выполнимость условия (5q), заметим, что Rp не изменяет состава очереди Qq и значения переменной aq .Lp : Действие Lp не добавляет никаких пакетов в очереди Qp и Qq и не изменяет значений переменных ap и aq . Поэтому оно сохраняет выполнимость условий(4p), (4q), (5p) и (5q).Как следует из симметричности рассматриваемого протокола, действия S q , Rqи Lq также сохраняют справедливость утверждения P 0 .Лемма 3.9.
Из утверждения P0 вытекают следующие соотношения:hpack, w, ii ∈ Qp =⇒ sp − L 6 i < sp + LЛемма 3.8. Утверждение P0 , определяемое следующей формулой:P0 ≡∧∧∧∧Phpack,hpack,hpack,hpack,97иw,w,w,w,iiiiiiiiследует за hpack, w0 , i0 i в очереди Qp =⇒ i > i0 − Lследует за hpack, w0 , i0 i в очереди Qq =⇒ i > i0 − L∈Qp =⇒ i > ap − lp∈Qq =⇒ i > aq − lq ,(4p)(4q)(5p)(5q)является инвариантом алгоритма 3.1.Д о к а з а т е л ь с т в о. Так как ранее нам удалось показать, что утверждение P является инвариантом, можно ограничиться обоснованием того, что свойства (4p), (4q), (5p) и (5q) выполняются в начальных конфигурациях и сохраняются при каждом переходе. Заметим, что в каждой начальной конфигурацииочереди сообщений пусты, и поэтому свойства (4p), (4q), (5p) и (5q), очевидно,выполняются.
Остается показать, что они сохраняются при переходах системы.Sp : Чтобы убедиться, что действие Sp сохраняет выполнимость условий (4p)и (5p), заметим, что Sp не добавляет новых пакетов в очередь Qp и не изменяетзначения переменной ap .Чтобы убедиться, что действие Sp сохраняет выполнимость условия (5q), заметим, что если Sp добавляет пакет hpack, w, ii в очередь Qq , то i > ap .
Согласнолемме 3.3 отсюда следует, что i > aq − lq .Чтобы убедиться, что действие Sp сохраняет выполнимость условия (4q), заметим, что если пакет hpack, w0 , i0 i уже находится в очереди Qq , то согласносвойству (1q) имеет место неравенство i0 < sp + lp . Поэтому если Sp добавляетв очередь пакет hpack, w, ii с порядковым номером i > a p , то согласно лемме 3.3будет выполняться неравенство i0 < ap + L 6 i + L.hpack, w, ii ∈ Qq =⇒ sq − L 6 i < sq + L.Д о к а з а т е л ь с т в о. Рассмотрим пакет hpack, w, ii∈ Q p .
Согласно свойству (1p) имеем неравенство i < sq + lq , из которого по лемме 3.3 следует неравенство i < sp + L. Согласно свойству (5p) имеем неравенство i > a p − lp , изкоторого по лемме 3.3 следует неравенство i > s p − L. Аналогичным образомдоказывется соотношение о пакетах из очереди Q q .Как видно из этой леммы, достаточно, чтобы нумерация пакетов проводиласьпо модулю k, где k > 2L. Действительно, располагая значением переменной s p ,а также значением переменной i по модулю k, процесс p может вычислить номер i.Выбор параметров.
Эффективность протокола в значительной степени зависит от выбора констант lp и lq . Вероятностный анализ зависимости пропускнойспособности протокола от этих констант был исследован в работе [173, гл. 2] .Оптимальные значения констант зависят от ряда системотехнических параметров, таких как1) время связи, т. е. промежуток времени между двумя последовательнымиоперациями процесса,2) задержка подтверждения приема, т. е. среднее время, которое требуется процессу p для передачи пакета процессу q и получения от него ответа,3) вероятность ошибки, т. е. вероятность потери пакета при передаче.Протокол чередующихся битов. Особо интересный вариант протокола раздвижного окна возникает в том случае, когда L = 1, т. е.
когда l p = 1 и lq = 0(или наоборот). В качестве начальных значений переменных a p и aq в этом случаеГл. 3. Коммуникационные протоколы3.2. Протокол с таймерамиТеперь мы перейдем к изучению той роли, которая отводится таймерам припроектировании и верификации коммуникационных протоколов; для этого рассмотрим упрощенный вариант ∆t-протокола сквозной передачи сообщений Флетчера и Ватсона. Этот протокол был описан в работе [85] , но та его слегка упрощенная версия, с которой мы будем иметь дело в этом разделе, заимствована изкниги [187, § 3.2] . Этот протокол поддерживает не только механизм обмена данными (как это делает симметричный протокол раздвижного окна, рассмотренныйнами в § 3.3.1), но также обеспечивает открытие и завершение соединений.
Протокол обладает устойчивостью относительно потери и дублирования сообщений,а также относительно нарушения порядка следования сообщений.Информация о состоянии протокола (вернее, той его части, которая обеспечивает передачу данных) содержится в структуре данных, которая называетсядосье соединения. (В § 3.2.1 будет рассказано о том, какая именно информациясодержится в досье соединения).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
