ref (Распределенные алгоритмы), страница 11

Доказательство. Конфигурации из F строятся одна за другой, и чтобы построить _i+1 достаточно показать, что f_i применимо в _i. Возьмем ₀ = ₀.

Предположим, что для всех j < i, f_j применимо в конфигурации _j и _j+1 = f_j (_j ). Пусть _i = (c_p1 , ..., c_pN , M) и пусть f_i =(c, x, y, d) будет событие в процессе р, тогда событие f_i применимо в _i, если с_p = c и х  М.

Чтобы показать, что с_p = c нужно различать два случая. В обоих случаях мы должны помнить, что каузальный порядок исполнения Е абсолютно упорядочивает события в процессе р. Это подразумевает, что события в процессе р появляются в точно таком же порядке и в f и в Е’.

Случай 1: f_i - первое событие в р из f, тогда с_р – это начальное состояние р. Но тогда f_i – также первое событие в р из Е’, что подразумевает, что с – это начальное состояние р. Следовательно, с = с_р.

Случай 2: f_i – не первое событие в р из f. Пусть последнее событие в р из f перед f_i будет f_i' = (c’, x’, y’, d’), тогда с_р = d’. Но тогда f_i' также последнее событие в р перед f_i из Е’, что подразумевает, что с = d’. Следовательно, с = с_р.

Чтобы показать, что х  М мы должны помнить, что соответствующие события приема и посылки встречаются в одном порядке и в f и в Е’. Если f_i не событие посылки, то х =  и х  М выполняется тривиально. Если f_i – это событие посылки, пусть f_i будет соответствующим событием посылки. Так как f_j  f_i , j < i выполняется, т.е., событие посылки предваряет f_i в f, следовательно, х  М.

Мы сейчас показали, что для каждого i, f_i применимо в _i, и _i+1 может быть взято как f_i(_i). Мы должны, наконец, показать, что последние конфигурации из F и Е совпадают, если Е конечно. Пусть _k будет последней конфигурацией из Е. Если Е’ не содержит события в р, то состояние р в _k равно его начальному состоянию. Так как f также не содержит события в р, то состояние р в _k также равно начальному состоянию, отсюда состояние р в _k равняется его состоянию в _k. Иначе, состояние р в _k есть состояние после последнего события в р из Е’. Это также последнее событие в р из f, так что это также состояние р в _k.

Сообщения в процессе передачи в _k есть такие сообщения, для которых событию посылки нет соответствующего события получения в Е’. Но так как Е’ и f содержат один и тот же набор событий, те же сообщения в процессе передачи в последней конфигурации из F. 

Р
ис. 2.2 Пространственно-временная диаграмма эквивалентная рис. 2.1

Исполнения F и Е имеют один набор событий, и каузальный порядок этих событий – один и тот же для Е и F. Поэтому, также, в этом случае Е – это перестановка событий из F, которая согласуется с каузальным порядком исполнения F. Если применить условие теоремы 2.21, мы можем сказать, что Е и F – эквивалентные исполнения, что обозначается как E ~ F.

Рис. 2.2 показывает временную диаграмму исполнения, эквивалентного исполнению, изображенному на рис. 2.1. Эквивалентные временные диаграммы могут быть получены с помощью «трансформаций резиновой ленты» [Mat89c]. Полагая, что временная ось процесса может быть сжата и растянута пока стрелки сообщений продолжают указывать направо, рис. 2.1 может быть деформирован до рис. 2.2.

Хотя изображенные исполнения эквивалентны и содержат одинаковый набор событий, они не могут содержать одинаковый набор конфигураций. Рис. 2.1 содержит конфигурацию (”), в которой сообщение, посланное в событии е и сообщение, посланное в событии l, передаются одновременно . Рис. 2.2 не содержит такой конфигурации, потому что сообщение, посланное в событии l, получено перед свершением события е.

Глобальный наблюдатель, кто имеет доступ к действительной последовательности событий, может различать два эквивалентных исполнения, т.е. может наблюдать либо одно, либо другое исполнение. Однако, процессы не могут различать две эквивалентных исполнения, т.к. для них невозможно решить, какое из двух исполнений имеет место. Это иллюстрируется следующим. Предположим, что мы должны решить будут ли посылаться сообщения в событии е и будут в передаче одновременно. Существует булевская переменная sim в одном из процессов, которая должна установлена в истину, если сообщения были в передаче одновременно, и ложь иначе. Таким образом, в последней конфигурации рис. 2.1 значение sim – истина, и в последней конфигурации на рис 2.2 значение – ложь. По теореме 2.21, конфигурации равны, что показывает, что требуемое присваивание sim невозможно.

Класс эквивалентности при отношении ~ полностью характеризуется набором событий и каузальным порядком на этих событиях. Классы эквивалентности называются вычислениями алгоритма.

Определение 2.22 Вычисление распределенного алгоритма – это класс эквивалентности (при ~) исполнений алгоритма.

Не имеет смысла говорить о конфигурациях вычисления, потому что различные исполнения вычисления могут не иметь одних и тех же конфигураций. Имеет смысл говорить о наборе событий вычисления, потому что все исполнения вычисления состоят из одного и того же набора событий. Также, каузальный порядок событий определен для вычисления. Мы будем называть вычисление конечным, если его исполнения конечны. Все исполнения вычисления начинаются в одной конфигурации и, если вычисление конечно, завершаются в одной конфигурации (теорема 2.21). Эти конфигурации называются начальными и конечными конфигурациями вычисления. Мы будем определять вычисление с помощью частично упорядоченного множества событий, принадлежащих ему.

Результат из теории частичных порядков подразумевает, что каждый порядок может встречаться для пары конкурирующих событий вычислений.

Факт 2.23 Пусть (Х, <) будет частичным порядком и а, b  Х удовлетворяют b  a. Существует линейное расширение <₁ операции < такое, что а <₁ b.

Следовательно, если а и b – конкурирующие события вычисления С, существуют исполнения Е_а и Е_b этого вычисления такие, что а имеет место раньше, чем b в Е_а, и b имеет место раньше, чем а в Е_b. Процессы в исполнении не имеют средств, чтобы решить, какое из двух событий произошло раньше.

Синхронная передача сообщений Версия теоремы 2.19 может быть сформулирована также для систем с синхронной передачей сообщений. В таких системах два последовательных событий независимы, если они воздействуют на различные процессы, как сформулировано в следующей теореме.

Теорема 2.24 Пусть  будет конфигурацией распределенной системы с синхронной передачей сообщений и пусть е₁ будет переходом процессов р и q, и е₂ будет переходом процессов r и s, отличных от р и q, такие, что и е₁ и е₂ применим в . Тогда е₁ применим в е₂(), е₂ применим в е₁(), и е₁(е₂()) = е₂(е₁()).

Доказательство этой теоремы, которое основывается на тех же аргументах, что и доказательство теоремы 2.19, оставлено для упражнения 2.9. Понятие казуальности в синхронных системах может быть определено подобно определению 2.20. Интересующегося читателя можно отослать к [CBMT92]. Теорема 2.21 также имеет своего двойника для синхронных систем.

2.3.3 Логические часы

По аналогии с физическими часами, которые измеряют реальное время, в распределенных вычислениях часы могут быть определены, чтобы выразить каузальность. На протяжении всего этого раздела,  - функция, действующая из набора событий в упорядоченное множество (Х, <)

Определение 2.25 Часы есть функция , действующая из событий на упорядоченное множество такое, что

a  b  (а) < (b).

Далее в этом разделе обсуждаются некоторые примеры часов.

1. Порядок в последовательности. В исполнении Е, определенном последовательностью событий (е₀, е₁, е₂, …), множество _g(е_i) = i. Таким образом, каждое событие помечается своей позицией в последовательности событий.

Эта функция может использоваться глобальным наблюдателем системы, кто имеет доступ к порядку, в котором происходят события. Однако, невозможно наблюдать этот порядок внутри системы, или, иначе говоря, _g не может быть вычислена распределенным алгоритмом. Это следствие теоремы 2.19. Предположим, что некоторый распределенный алгоритм сохраняет значение _g(е_i) = i для события е_i (что удовлетворяет посылке теоремы). В эквивалентном исполнении, в котором это событие меняется со следующим событием, и следовательно имеет другое значение _g, то же значение i сохраняется в процессе. Говоря другими словами, _g определено для исполнений, но не для вычислений.

1. Часы реального времени. Имеется возможность расширить модель, что является предметом обсуждения этой главы, с помощью снабжения каждого процесса аппаратными часами. Этим путем возможно записывать для каждого события реальное время, в которое оно произошло. Полученные числа удовлетворяют определению часов.

Распределенные системы с часами реального времени не удовлетворяют определению 2.6, потому что физические свойства часов синхронизируют изменения состояний в разных процессах. Время идет во всех процессах, и это порождает переходы, которые меняют состояние (а именно, считыванием часов) всех процессов. Оказывается, что эти «глобальные переходы» ужасно меняют свойства модели. В самом деле, теорема 2.19 больше не действует, если приняты часы реального времени. Распределенные системы с часами реального времени используются на практике, однако, и они будут рассматриваться в этой книге (см. раздел 3.2) и главы 11 и 14.

Алгоритм 2.3 Логические часы Лампорта

1. Логические часы Лампорта. Лампорт [Lam78] представил часовую функцию, которая приписывает событию а длину k самой длинной последовательности (е₁, …, е_k) событий, удовлетворяющей

е₁  е₂  … е_k = a

В самом деле, если а  b, эта последовательность может быть расширена, чтобы показать, что _L(a) < _L(b). Значение _L может быть вычислено для каждого события распределенным алгоритмом, базируясь на следующих отношениях.

(а) Если а есть внутреннее событие или событие посылки, и а’ – предыдущее событие в том же процессе, то _L(a) = _L(a’) + 1.

(b) Если а – событие получение, а’ – предыдущее событие в том же процессе, и b –событие посылки, соответствующее а, то _L(a) = max(_L(a’), _L(b)) + 1.

В обоих случаях _L(a’) предполагается нулевым, если а – первое событие в процессе.

Чтобы вычислить значения часов распределенным алгоритмом, значение часов последнего события процесса р сохраняется в переменной _р (инициализируемой в 0). Для того, чтобы вычислить значение часов события получения, каждое сообщение m содержит значение часов _m события е, при котором оно было послано. Логически часы Лампорта даны как алгоритм 2.3. Для события е в процессе р, _L(е) есть значение _р сразу же после появления е, т.е. в момент, когда происходит изменение состояния процесса р. Оставлена для упражнения демонстрация того, что с этим определением _L является часами.

Не указывается при каких условиях сообщение должно быть послано или как меняется состояние процесса. Часы –это дополнительный механизм, который может быть добавлен к любому распределенному алгоритму, чтобы упорядочивать события.

1. Векторные часы. Для некоторых целей полезно иметь часы, который выражают не только каузальный порядок (как требуется по определению 2.25), но также и конкуренцию. Конкуренция выражается часами, если конкурентные события помечаются несравнимыми значениями часов, то есть, следствие в определении 2.25 заменяется на эквиваленцию, давая

a  b  (а) < (b). (2.1)

Существование конкурирующих событий подразумевает, что область таких часов (множество Х) – не-полностью-упорядоченное множество.

В векторных часах Маттерна [Mat89b] X = N^N, т.е. _v(a) есть вектор длины N. Вектора длины n естественным образом упорядочены векторным порядком, определенным следующим образом:

(а₁, …, а_n) _v (b₁, …, b_n)  i (1  i  n) : a_i  b_i. (2.2)

(Векторный порядок отличается от лексикографического порядка, определенного в упражнении 2.5, последний порядок абсолютен). Часы, определяемые _v(a) = (а₁, …, а_N), а_i – это число событий е в процессе р₁, для которого е  а. Как и часы Лампорта, эта функция может быть вычислена распределенным алгоритмом.

Чаррон-Бост [CB89] показал, что невозможно использовать более короткие векторы (с векторным порядком как в (2.2)). Если события произвольного исполнения из N процессов отображаются на вектора длины n таких, что (2.1) удовлетворяется, то n  N.

2.4 Дополнительные допущения, сложность

Определений сделанных до сих пор в этой главе достаточно, чтобы развивать оставшиеся главы. Определенная модель служит как основа для представления и проверки алгоритмов, так и для доказательств невозможности для решения распределенных проблем. В различных главах используются дополнительные допущения и нотация, если требуется. Этот раздел обсуждает некоторую терминологию, которая также общеупотребительна в литературе по распределенным алгоритмам. До сих пор, мы моделировали коммуникационную подсистему распределенной системы набором сообщений, находящихся в данный момент в процессе передачи. Далее, мы будем предполагать, что каждое сообщение может передаваться только одним процессом, называемым назначением сообщения. В общем, не обязательно чтобы каждый процесс мог посылать сообщения каждому другому процессу. Вместо этого, для каждого процесса определено подмножество других процессов (называемых соседями процесса), к которым он может посылать сообщения. Если процесс р может посылать сообщения процессу q, говорят, что существует канал от р до q. Если не утверждается обратное, предполагается, что каналы двунаправленные, то есть, тот же канал позволяет посылать q сообщения процессу p. Канал, который осуществляет только однонаправленный трафик от р к q, называется однонаправленным (или направленным) каналом от р до q.

Набор процессов и коммуникационная подсистема также упоминается как сеть. Структура коммуникационной подсистемы часто представляется как граф G = (V, E), в котором вершины – это процессы, и ребра между двумя процессами существуют, если и только если канал существует канал между двумя процессами. Система с однонапрвленными каналами может подобным образом представлена направленными графом. Граф распределенной системы также называется ее сетевой топологией.

Представление графом позволяет нам говорить о коммуникационной системе в терминах теории графов. См. дополнение Б для представления об этой терминологии. Так как сетевая топология происходит от основного влияния на существование, внешний вид, и сложность распределенных алгоритмов для многих проблем, мы включаем ниже краткое обсуждение некоторых повсеместно используемых здесь топологий. См. дополнение Б для дополнительных деталей. На протяжении этой книги, если не утверждается обратное, предполагается, что топология связана, то есть, существует путь между двумя вершинами.

1. Кольца. N-вершинное кольцо – граф на вершинах от v₀ до v_N-1 c ребрами v₀v_N-1 (индексы – по модулю N). Кольца часто используются для распределенного управления вычислениями, потому что они просты. Также, некоторые физические сети, такие как Token Rings [Tan88, раздел 3.4], распределяют узлы в кольцо.

2. Деревья. Дерево на N вершинах – это связанный граф с N –1 ребрами, он не содержит циклов. Деревья используются в распределенных вычислениях, потому что они позволяют проводить вычисление при низкой цене коммуникаций, и более того, каждый связанный граф содержит дерево, как подсеть охвата.

3. Звезды. Звезда на N вершинах имеет одну специальную вершину (центр) и N-1 ребер, соединяющих каждую из N-1 вершин с центром. Звезды используются в централизованных вычислениях, где один процесс действует как контроллер и все другие процессы сообщаются только с этим специальным процессом. Недостатки звездной топологии это узкое место, каким может стать центр и уязвимость такой системы из-за повреждений в центре.

4. Клики. Клика – это сеть, в которой ребро существует между любыми двумя вершинами.

5. Гиперкубы. Гиперкуб – это граф HC_N = (V, E) на N = 2ⁿ вершинах. Здесь V – множество битовых строк длины n:

V = {(b₀ , ..., b_n-1) : b_i  {0, 1}},

и ребро существует между двумя вершинами b и с, тогда и только тогда, когда битовые строки b и с различаются точно на один бит. Имя гиперкуба относится к графическому представлению сети как n-размерного куба, углы которого – вершины.

Рис. 2.4 Примеры часто используемых топологий

Примеры каждой из этих сетей приведены на рис 2.4. Топология может быть статической или динамической. Статическая топология означает, что топология остается фиксированной в течение распределенного вычисления. Динамическая топология означает, что каналы (иногда даже процессы) могут быть добавлены или удалены из системы в течение вычисления. Эти изменения в топологии могут быть также смоделированы переходами конфигураций, а именно, если состояния процесса отражают множество соседей процесса (см. главу 4).

2.4.2 Свойства каналов

Модель (как описана в подразделе 2.1.2) может быть усовершенствована при помощи представления содержимого каждого канала раздельно в конфигурации, то есть, замены множества М на набор множеств М_рq для каждого (однонаправленного) канала рq. Так как мы постулировали, что каждое сообщение неявно определяет свое назначение, то эта модификация не изменяет важных свойств модели. Далее обсуждаются некоторые общие допущения относительно соотношения событий приема и посылки.

1. Надежность. Говорят, что канал надежен, когда каждое сообщение, которое посылается в канал принимается точно один раз (обеспечив назначению возможность получить сообщение). Если не утверждается обратное, всегда предполагается в этой книге, что каналы надежны. Это допущение фактически добавляет (слабое) условие справедливости. В самом деле, после того как сообщение послано, получение этого сообщения (в приемлемом для назначения состоянии) применимо.

Канал, который ненадежен, может проявлять коммуникационные сбои, которые могут быть нескольких типов, например, утеря, искажение, дублирование, порождение. Эти сбои могут быть представлены переходами в модели определения 2.6, но эти переходы не соответствуют изменениям состояния процесса.

Утеря сообщения имеет место, когда сообщение посылается, но никогда не принимается. Это может быть смоделирована переходом, который удаляет сообщение из М. Искажение сообщение встречается, когда полученное сообщение отличается от посланного сообщения. Это может быть смоделировано переходом, который меняет одно сообщение из М. Дублирование сообщения появляется, если сообщение принимается более часто, чем оно посылалось. Это может быть смоделировано переходом, который копирует сообщение из М. Порождение сообщения, встречается, когда сообщение получено, но никогда не было послано, это моделируется переходом, который вставляет сообщение в М.

1. Свойство fifo. Говорят, что канал является fifo, если он соблюдает порядок сообщений, посланных через него. То есть, если р посылает два сообщения m₁ и m₂ процессу q и отправка m₁ происходит раньше в р, чем отправка m₂, то получение m₁ происходит раньше в q, чем получение m₂. Если не утверждается обратное, fifo каналы не будут предполагаться в этой книге.

Fifo каналы могут быть представлены в модели определения 2.6 при помощи замены набора М на множество очередей, одной для каждого канала. Отправка осуществляется добавлением сообщения к концу очереди, и событие получения удаляет сообщение с головы. Когда предполагаются каналы fifo, появляется новый тип коммуникационных сбоев, а именно, переупорядочивание сообщений в канале. Это может быть смоделировано переходом, который обменивает два сообщения в очереди.

Иногда случается, что распределенный алгоритм получает пользу от свойства fifo каналов, см., например, коммуникационный протокол в разделе 3.1. Использование порядка получение сообщений снижает количество информации, которая должна транспортироваться в каждом сообщении. Во многих случаях, однако, алгоритм может быть разработан так, чтобы функционировать правильно (и эффективно) даже, если сообщения могут быть переупорядочены в канале. В общем, реализация свойства fifo расределенных систем может понизить свойственный параллелизм вычислений, т.к. это может потребовать буферизации сообщений (на стороне получателя в канале) перед тем как сообщение будет обработано. По этой причине мы не выбираем предположение свойства fifo неявно в этой книге.

Более слабое допущение было предложено Ахуджа [Ahu90]. Выталкивающий канал – это канал, который соблюдает порядок только сообщений, для которых это было указано отправителем. Могут быть также определены более сильные допущения. Шипер и др. [SES89] определили каузально упорядоченную доставку сообщений, как описывается далее. Если р₁ и р₂ посылают сообщения m₁ и m₂ процессу q в событиях е₁ и е₂ и е₁  е₂ , то q получает m₁ перед m₂ . Иерархия допущений доставки, состоящая из полного асинхронизма, каузально упорядоченной доставки, fifo, и синхронных коммуникаций, обсуждалась Чаррон-Бостом и др. [CBMT92].

1. Емкость канала. Емкость – это число сообщений, которое может передаваться по каналу одновременно. Канал полон в каждой конфигурации, в которой он действительно содержит количество сообщений, равное его емкости. Событие посылки применимо, только если канал не полон.

Определение 2.6 моделирует каналы с неограниченной емкостью, т.е. каналы, которые никогда не наполняются. В этой книге всегда будет предполагаться, что емкость каналов не ограничена.

2.4.3 Допущения реального времени

Основное свойство представленной модели есть, конечно, ее распределенность: полная независимость событий в различных процессах, как выражает теорема 2.19. Это свойство теряется, когда предполагается кадр глобального времени и способность процессов наблюдать физическое время (устройство физических часов). В самом деле, когда некоторое реальное время истекает, это время истекает во всех процессах, и это проявится на часах каждого процесса.

Часы реального времени могут быть встроены при помощи снабжения каждого процесса переменной часов реального времени. Течение реального времени моделируется переходом, который передвигает вперед часы каждого процесса, см. раздел 3.2. Обычно, принимается ограничение на время передачи сообщения (время между отправкой и получением сообщения) вкупе с доступностью часов реального времени. Это ограничение может быть также включено в общую модель системы переходов.

Если не утверждается обратное, допущения реального времени не делаются в этой книге, т.е. мы предполагаем полностью асинхронные системы и алгоритмы. Допущения отсчета времени будут использованы в разделе 3.2, главе 11 и главе 14.

2.4.4 Знания процессов

Изначальные знания процесса – это термин, используемый для обращения к информации о распределенной системе, которая представляется в начальных состояниях процессов. Если алгоритму сказано полагаться на такую информацию, то предполагается, что релевантная информация правильно сохраняется в процессах, прежде чем начнется исполнение системы. Примеры таких знаний включают следующую информацию.

1. Топологическая информация. Информация о топологии включает: количество процессов, диаметр графа сети, и топологию графа. Говорят, что сеть имеет чувство направления, если согласующаяся с направлениями разметка ребер в графе известна процессам (см. дополнение Б).

2. Идентичность процессов. Во многих алгоритмах требуется, чтобы процессы имели уникальные имена (идентификаторы), и чтобы каждый процесс знал свое собственное имя изначально. Тогда предполагается, что процессы содержат переменную, которая инициализируется этим именем (т.е. различным для каждого процесса). Дальнейшие допущения могут быть сделаны касательно множества, из которого выбираются имена, - что имена линейно упорядочены или что они (положительные) целые. Если не утверждается обратное, в этой книге всегда будем предполагать, что процессы имеют доступ к их идентификаторам, в этом случае система называется именованной сетью. Ситуации, где это не так (анонимные сети) будут исследованы в главе 9.

3. Идентификаторы соседей. Если процессы различаются уникальным именем, то возможно предположить, что каждый процесс знает изначально имена соседей. Это допущение называется знание соседей и, если не утверждается обратное, не будет делаться. Имена процессов могут быть полезными для цели адресации сообщений. Имя назначения сообщения дается, когда сообщение посылается с прямой адресацией. Более сильные допущения состоят в том, что каждый процесс знает весь набор имен процессов. Более слабое допущение состоит в том, что процессы знают о существовании, но не знают имен своих соседей. Прямая адресация не может использоваться в этом случае, и процессы используют локальные имена для их каналов, когда хотят адресовать сообщение, что называется непрямой адресацией. Прямая и непрямая адресация показана на рис. 2.5. Прямая адресация использует идентификатор процесса как адрес, в то время как непрямая адресация процессов р, r и s использует различные имена (а, b и c, соответственно), чтобы адресовать сообщения в назначение q.

Рис. 2.5 Прямая (а) и непрямая (b) адресация

2.4.5 Сложность распределенных алгоритмов

Самое важное свойство распределенного алгоритма – его правильность: он должен удовлетворять требованиям, налагаемым проблемой, что алгоритм

3 Протоколы Связи

В этой главе обсуждаются два протокола, которые используются для надежного обмена данными между двумя вычислительными станциями. В идеальном случае, данными бы просто обменивались, посылая и получая сообщения. К сожалению, не всегда можно игнорировать возможность ошибок связи; сообщения должны транспортироваться через физическую среду, которая может терять, дублировать, переупорядочивать или искажать сообщения, передаваемые через нее. Эти ошибки должны быть обнаружены и исправлены дополнительными механизмами, выполняющимися на вычислительных станциях, которые традиционно называются протоколами.

Основная функция этих протоколов - передача данных, то есть, принятие информации на одной станции и получение ее на другой станции. Надежная передача данных включает повторную посылку сообщений, которые потеряны, отклонение или исправление сообщений, которые искажены, и отбрасывание дубликатов сообщений. Для выполнения этих функций протокол содержит информацию состояния, записывая, какие данные уже был посланы, какие данные считаются полученными и так далее. Необходимость использования информации состояния поднимает проблему управления соединением, то есть, инициализации и отбрасывания информации состояния. Инициализация называется открытием соединения, и отбрасывание называется закрытием соединения. Трудности управления соединением возникают из-за того, что сообщение может остаться в каналах связи, когда соединение закрыто. Такое сообщение могло бы быть получено, когда не существует никакого соединения или в течение более позднего соединения, и получение не должно нарушать правильную операцию текущего соединения.

Протоколы, обсуждаемые в этой главе разработаны для различных уровней в иерархии протокола, типа модели OSI (Подраздел 1.2.2). Они включены в эту книгу по различным причинам; первый протокол полностью асинхронный, в то время как второй протокол полагается на правильное использование таймеров. В обоих случаях заостряется внимание на требуемом свойстве безопасности, а именно на том, что приемник получит только правильные данные.

Первый протокол (Раздел 3.1) разработан для обмена данными между двумя станциями, которые имеют прямое физическое соединение (типа телефонной линии), и, следовательно, принадлежит канальному уровню модели OSI. Второй протокол (Раздел 3.2) разработан для использования двумя станциями, которые связываются через промежуточную сеть (возможно содержащую другие станции и соединяющую станции через различные пути), и этот протокол следовательно принадлежит к транспортному уровню OSI модели. Это различие отражается на функциональных возможностях, требуемых от протоколов, следующим образом.

1. Рассматриваемые ошибки. Для двух протоколов будут рассматриваться различные классы ошибок передачи. Сообщения не могут пересекаться при физическом соединении, и они не могут быть продублированы; таким образом, в разделе 3.1 рассматривается только потеря сообщений (об искажении сообщений см. ниже). В сети сообщения могут передаваться различными путями, и, следовательно, пересекаться; также, из-за отказов промежуточных станций сообщения могут быть продублированы или потеряны. В Разделе 3.2 будут рассматриваться потеря, дублирование и переупорядочение сообщений.

1. Управление соединением. Далее, управление соединением не будет рассматриваться для первого протокола, но будет для второго. Предполагается, что физическое соединение функционирует непрерывно в течение очень длительного времени, а не открывается и закрывается неоднократно. Для соединений с удаленными станциями это не так. Такое соединение может быть необходимо временно для обмена некоторыми данными, но обычно слишком дорого поддерживать соединение с каждой удаленной станцией неопределенно долго. Следовательно, для второго протокола будет требоваться способность открывать и закрывать соединение.

При рассмотрении первого протокола показывается, что не только механизмы, основанные на таймерах, могут обеспечить требуемые свойства безопасности протоколов передачи данных. Раздел 3.1 служит первым большим примером доказательства свойств безопасности с помощью инструментальных средств, описанных в Разделе 2.2. Многие полагают [Wat81], что правильное использование таймеров и ограничение на время, в течение которого сообщение может передаваться , необходимы для безопасного управления соединением. Таким образом, для того, чтобы доказать безопасность протоколов, нужно принимать во внимание роль таймеров в управлении соединением. Раздел 3.2 показывается, как модель распределенных систем (Определение 2.6) может быть расширена до процессов, использующих таймеры, и дает пример этого расширения.

Искажение сообщений. Естественно принять во внимание возможность того, что сообщения могут быть искажены в течение передачи. Содержание сообщения, переданного через физическое соединение, может быть повреждено из-за атмосферных шумов, плохо функционирующих модулей памяти, и т.д. Однако можно предположить, что искажение сообщения может быть обнаружено процессом-получателем, например, посредством контроля четности или более общих механизмов контрольной суммы ( [Tan88, Глава 41). Получение искаженного сообщения затем обрабатывается так, как будто не было получено никакого сообщения, и таким образом, искажение сообщения фактически вызывает его потерю. По этой причине искажение не обрабатывается явно; вместо этого всегда рассматривается возможность потери сообщения.

3.1 Сбалансированный протокол скользящего окна

В этом разделе изучается симметричный протокол, который обеспечивает надежный обмен информацией в обоих направлениях. Протокол взят из [Sch91, Глава 2]. Поскольку он используется для обмена информацией между станциями, которые непосредственно соединены через линию, можно предположить, что каналы имеют дисциплину fifo. Это предположение не используется, однако, до Подраздела 3.1.3, где показано, что числа последовательности, используемые протоколом могут быть ограничены. Протокол представлен в Подразделе 3.1.1, а в Подразделе 3.1.2 доказывается его правильность.

Два процесса связи обозначаются как p и q. Предположения, требования и протокол абсолютно симметричны. Вход p состоит из информации, которую он должен послать q, и моделируется неограниченным массивом слов in_p. Выход p состоит из информации, которую он получает от q, и также моделируется неограниченным массивом слов, out_p. Предполагается, что p имеет случайный доступ по чтению к in_p и случайный доступ по записи к out_p. Первоначально значение out_p[i] не определено и представлено как udef для всех i. Вход и выход процесса q моделируется массивами in_q и out_q соответственно. Эти массивы нумеруются натуральными числами, т.е. они начинаются со слова с номером 0. В подразделе 3.1.3 будет показано, что произвольный доступ может быть ограничен доступом к "окну" конечной длины, передвигающемуся вдоль массива. Поэтому протокол называется протоколом «скользящего окна».

Процесс p содержит переменную s_p, показывающую наименьшее нумерованное слово, которое p все еще ожидает от q. Таким образом, в любой момент времени, p уже записал слова от out_p[0] до out_p[sp - 1]. Значение s_p никогда не уменьшается. Аналогично q содержит переменную s_q. Теперь могут быть установлены требуемые свойства протокола. Свойство безопасности говорит о том, что каждый процесс передает только корректные данные; свойство живости говорит о том, что все данные когда-либо будут доставлены.

1. Свойство безопасности. В каждой достижимой конфигурации протокола

out_p[0..s_p — 1] = in_q[0..Sp — 1] и out_q[0..s_q — 1] = in_p [0...s_q — 1].

1. Окончательная доставка. Для каждого целого k  0, конфигурации с s_p  k и
   s_q  k когда-либо достигаются.

3.1.1 Представление протокола

Протоколы передачи обычно полагаются на использование сообщений подтверждения. Сообщение подтверждения посылается процессом получения, чтобы сообщить отправителю о данных, которые он получил корректно. Если отправитель данных не получает подтверждение, то он предполагает, что данные (или подтверждение) потеряно, и повторно передает те же самые данные. В протоколе этого раздела, однако, не используются явные сообщения подтверждения. В этом протоколе обе станции имеют сообщения, которые нужно послать другой станции; сообщения станции служат также подтверждениями для сообщений другой станции.

Сообщения, которыми обмениваются процессы, называют пакетами, и они имеют форму
< pack, w, i >, где w - слово данных, а i - натуральное число (называемое порядковым номером пакета). Этот пакет, посылаемый процессом p (к q), передает слово = in_p[i] для q, но также, как было отмечено, подтверждает получение некоторого количества пакетов от q. Процесс p может быть «впереди» q не более, чем на l_p пакетов, если мы потребуем, что пакет данных < pack, w, i >, посланный p, подтверждает получение слов с номерами 0.. i— l_p от q. (q посылает аналогичные пакеты.) Константы l_p и l_q неотрицательны и известны обоим процессам p и q. Использование пакета данных в качестве подтверждения имеет два последствия для протокола:

1. Процесс p может послать слово in_p[i] (в виде пакета < pack, in_p[i], i >) только после того, как запишет все слова от out_p[0] до out_p[i — l_p], т. е. , если i < s_p + l_p.

2. Когда p принимает < pack, w,i>, повторная передача слов с in_p[0] до in_p[i — l_q] уже не нужна.

Объяснение псевдокода. После выбора модели нетрудно разработать код протокола; см. Алгоритм 3.1. Для процесса p введена переменная a_p (и a_q для q), в которой хранится самое первое слово, для которого p (или q, соответственно) еще не получил подтверждение..

В Алгоритме 3.1 действие S_p - посылка i-го слова процессом p, действие R_p - принятие слова процессом p, и действие L_p - потеря пакета с местом назначения p. Процесс p может послать любое слово, индекс которого попадает в указанные ранее границы. Когда сообщение принято, в первую очередь делается проверка - было ли идентичное сообщение принято ранее (на случай повторной передачи). Если нет, слово, содержащееся в нем, записывается в выход, и a_p и s_p корректируются. Также вводятся действия S_q, R_q и L_q , где p и q поменяны ролями.

var s_p, a_p : integer init 0, 0 ;

in_p : array of word (* Посылаемые данные *) ;

out_p : array of word init udef, udef, ...',

S_p: {a_p  i < S_p+l_p}

begin send < pack,in_p[i],i> to q end

R_p: { < pack, w, i > Q_p }

begin receive <pack, w, i> ;

if out_p[i] = udef then

begin out_p[i] := w ;

a_p := max(a_p,i-l_p+1) ;

S_p := min{j|out_p[j]= udef}

end

(* else игнорируем, пакет передавался повторно *)

end

Lp: {<pack,w,i>Q_p}

begin Q_p := Q_p\ {<pack,w,i>} end

Алгоритм 3.1 Протокол скользящего окна (для p).

Инвариант протокола. Подсистема связи представляется двумя очередями, Q_p для пакетов с адресатом p и Q_q, для пакетов с адресатом q. Заметим, что перевычисление s_p в R_p никогда не дает значение меньше предыдущего, поэтому s_p никогда не уменьшается. Чтобы показать, что этот алгоритм удовлетворяет данным ранее требованиям, сначала покажем, что утверждение P - инвариант. (В этом и других утверждениях i - натуральное число.)

P  i < s_p : out_p[i] udef (0p)

/\ i < s_q, : out_q[i]  udef (0q)

/\ < pack, w, i >  Q_p  w = in_q[i] /\ (i < s_q + l_q) (lp)

/\ < pack, w, i >  Q_q  w = in_p[i] /\ (i < s_p + l_p) (lq)

/\ out_p[i] udef  out_p[i] = in_q[i] /\ (a_p > i— l_q) (2p)

/\ out_q[i] udef  out_q[i] = in_p[i] /\ (a_q > i— l_p) (2q)

/\ a_p  s_q, (3p)

/\ a_q  s_p (3q)

Лемма 3.1 P - инвариант Алгоритма 3.1.

Доказательство. В любой начальной конфигурации Q_p и Q_q - пустые, для всех i, out_p[i] и out_q[i] равны udef, и a_p,a_p, s_p и s_q равны нулю 0; из этого следует, что P=true. Перемещения протокола рассмотрим с точки зрения сохранения значения P. Во-первых, заметим, что значения in_p и in_q, никогда не меняются.

S_p: Чтобы показать, что S_p сохраняет (0p), заметим, что S_p не увеличивает s_p и не делает ни один из out_p[i] равным udef.

Чтобы показать, что S_p сохраняет (0q), заметим, что S_p не увеличивает s_q, и не делает ни один из out_q[i] равным udef.

Чтобы показать, что S_p сохраняет (1p), заметим, что S_p не добавляет пакеты в Q_p и не уменьшает s_p.

Чтобы показать, что S_p сохраняет (lq), заметим S_p добавляет < pack, w, i > в Q_p с w = in_p[i] и i < s_p + l_p, и не изменяет значение s_p.

Чтобы показать, что S_p сохраняет (2p) и (2q), заметим, что S_p не изменяет значения out_p, out_q, a_p, или a_q.

Чтобы показать, что S_p сохраняет (3p) и (3q), заметим, что S_p не меняет значения a_p , a_p , s_q , или s_p.

Rp: Чтобы показать, что R_p сохраняет (0p), заметим, что R_p не делает ни одно out_p[i] равным udef, и если он перевычисляет s_p, то оно впоследствии также удовлетворяет (0p).

Чтобы показать, что R_p сохраняет (0q), заметим, что R_p не меняет out_q или s_q.

Чтобы показать, что R_p сохраняет (lp), заметим, что R_p не добавляет пакеты в Q_p и не уменьшает s_q.

Чтобы показать, что R_p сохраняет (lq), заметим, что R_p не добавляет пакеты в Q_q и не уменьшает s_p.

Чтобы показать, что R_p сохраняет (2p), заметим, что R_p изменяет значение out_p[i] на w при принятии < pack, w,i>. Т.к. Q_p содержала этот пакет до того, как выполнился R_p, из (1p) следует, что w = in_p[i]. Присваивание a_p:= max (a_p, i— l_q+1) гарантирует, что a_p > i— l_q сохраняется после выполнения. Чтобы показать, что R_p сохраняет (2q), заметим, что R_p не меняет значения out_q или a_q.

Чтобы показать, что R_p сохраняет (3p), заметим, что когда R_p присваивает
a_p:= max(a_p, i— l_q+1) (при принятии ), из (lp) следует, что i < s_q+l_q, следовательно a_p  s_q сохраняется после присваивания. R_p не меняет s_q. Чтобы показать, что R_p сохраняет (3q), заметим, что s_p может быть увеличен только при выполнении R_p.

L_p : Чтобы показать, что L_p сохраняет (0p), (0q), (2p), (2q), (3p), и (3q), достаточно заметить, что L_p не меняет состояния процессов. (lp) и (lq) сохраняются потому, что L_p только удаляет пакеты (а не порождает или искажает их).

Процессы S_q, R_q, и L_q сохраняют P , что следует из симметрии. 

3.1.2 Доказательство правильности протокола

Сейчас будет продемонстрировано, что Алгоритм 3.1 гарантирует безопасную и окончательную доставку. Безопасность следует из инварианта, как показано в Теореме 3.2, а живость продемонстрировать труднее.

Теорема 3.2 Алгоритм 3.1 удовлетворяет требованию безопасной доставки.

Доказательство. Из (0p) и (2p) следует, что out_p[0..s_p —1] =in_q[0..s_p—1], а из (0q) и (2q) следует out_p[0..Sq -1] = in_p[0..Sq -1].

Чтобы доказать живость протокола, необходимо сделать справедливых предположений и предположение относительно l_p и l_q. Без этих предположений протокол не удовлетворяет свойству живости, что может быть показано следующим образом. Неотрицательные константы l_p и l_q еще не определены; если их выбрать равными нулю, начальная конфигурация протокола окажется тупиковой. Поэтому предполагается, что l_p + l_q > 0.

Конфигурация протокола может быть обозначена  = (c_p, c_q, Q_p, Q_q), где c_p и c_q - состояния p и q. Пусть  будет конфигурацией, в которой применим S_p (для некоторого i). Пусть

 = S_p() = (c_p, c_q, Q_p, (Q_q  {m})),
и отметим, что действие L_q применимо в . Если L_q удаляет m, L_q() = . Отношение L_q(S_p()) =  äàåò íà÷àëî íåîãðàíè÷åííûì âû÷èñëåíèÿì, â êîòîðûõ íè s_p , ни s_q не уменьшаются.

Протокол удовлетворяет требованию «окончательной доставки», если удовлетворяются два следующих справедливых предположения.

Fl. Если посылка пакета возможна в течение бесконечно долгого временно, пакет посылается бесконечно часто.

F2. Если один и тот же пакет посылается бесконечно часто, то он принимается бесконечно часто.

Предположение Fl гарантирует, что пакет посылается снова и снова, если не получено подтверждение; F2 исключает вычисления, подобные описанному выше, когда повторная передача никогда не принимается.

Ни один из двух процессов не может быть намного впереди другого: разница между s_p и s_q остается ограниченной. Поэтому протокол называется сбалансированным, а также из этого следует, что если требование окончательной доставки удовлетворяется для s_p, тогда оно также удовлетворяется для s_q, и наоборот. Понятно, что протокол не следует использовать в ситуации, когда один процесс имеет намного больше слов для пересылки, чем другой.

Ëåììà 3.3 Из P следует s_p— l_q  a_p  s_q  a_q+ l_p s_p + l_p.

Äîêàçàòåëüñòâî. Из (0p) и (2p) следует s_p— l_q a_p, из (3p) следует a_p s_p . Из (0q) и (2q) следует s_p a_p + l_p . Из (3q) следует a_p + l_p  s_p + l_p .

Òåîðåìà 3.4 Àëãîðèòì 3.1 удовлетворяет требованию окончательной доставки.

Äîêàçàòåëüñòâî. Сначала будет продемонстрировано, что в протоколе невозможны тупики. Из инварианта следует, что один из двух процессов может послать пакет, содержащий слово с номером, меньшим, чем ожидается другим процессом.

Утверждение 3.5 Из P следует, что посылка < pack, in[s_q], s_q> процессом p или посылка
< pack, inq[sp], sp ) процессом q возможна.

Äîêàçàòåëüñòâî. Т.к. lp + lq > 0, хотя бы одно из неравенств Ëåììы 3.3 строгое, т.е.,

sq < sp + lp \/ sp < sq+lq.

Из P также следует ap  sq (3p) и aq  sp (3q), а также следует, что

(ap  sqp+lp) \/ (aq  spq+lq)

это значит, что Sp применим с i = sq или Sq применим с i = sp. 

Теперь мы можем показать, что в каждом из вычислений sp и sq увеличиваются бесконечно часто. Согласно Утверждению 3.5 протокол не имеет терминальных конфигураций, следовательно каждое вычисление неограниченно. Пусть C - вычисление, в котором sp и sq увеличиваются ограниченное число раз, и пусть _p and _q - максимальные значения, которые эти переменные принимают в C. Согласно утверждению, посылка <pack, in_p[_q], _q> процессом p или посылка <pack, in _q[_p], _p > процессом q применима всегда после того, как s_p, s_q, a_p и a_q достигли своих окончательных значений. Таким образом, согласно Fl, один из этих пакетов посылается бесконечно часто, и согласно F2, он принимается бесконечно часто. Но, т.к. принятие пакета с порядковым номером sp процессом p приводит к увеличению sp (и наоборот для q), это противоречит допущению, что ни s_p, ни s_q не увеличиваются более. Таким образом Òåîðåìà 3.4 доказана. 

Мы завершаем этот подраздел кратким обсуждением предположений Fl и F2. F2-ìèíèìàëüíîå требование, которому должен удовлетворять канал, соединяющий p и q, для того, чтобы он мог передавать данные. Очевидно, если некоторое слово inp[i] никогда не проходит через канал, то невозможно достичь окончательной доставки слова. Предположение Fl обычно реализуется в протоколе с помощью условия превышения времени: если ap не увеличилось в течение определенного промежутка времени, inp[ap] передается опять. Как уже было отмечено во введении в эту главу, для этого протокола безопасная доставка может быть доказана без принятия во внимания проблем времени (тайминга).

3.1.3 Обсуждение протокола

Ограничение памяти в процессах. Àëãîðèòì 3.1 не годится для реализации в компьютерной сети, т.к. в каждом процессе хранится бесконечное количество информации (массивы in и out) и т.к. он использует неограниченные порядковые номера. Сейчас будет показано, что достаточно хранить только ограниченное число слов в каждый момент времени. Пусть L = lp + lq.

Ëåììà 3.6 Из P следует, что отправление < pack, w,i> процессом p применимо только для i < ap+L.

Äîêàçàòåëüñòâî. Сторож Sp требует i < sp+lp, значит согласно Ëåììе 3.3 i < ap+L. 

Ëåììà 3.7 Из P следует, что если outp[i] udef, то i < sp + L.

Äîêàçàòåëüñòâî. Из (2p), ap > i— lq, значит i < ap + lq, и i < sp + L (из Ëåììы 3.3). 

Ðèñóíîê 3.2 Скользящие окна протокола.

Последствия этих двух лемм отображены на Ðèñóíêе 3.2. Процессу p необходимо хранить только слова inp[ap..sp + lp — 1] потому, что это слова, которые p может послать. Назовем их как посылаемое окно p (представлено как S на Ðèñóíêе 3.2). Каждый раз, когда ap увеличивается, p отбрасывает слова, которые больше не попадают в посылаемое окно (они представлены как A на Ðèñóíêе 3.2). Каждый раз, когда sp увеличивается, p считывает следующее слово из посылаемого окна от источника, который производит слова. Согласно Ëåììе 3.6, посылаемое окно процесса p содержит не более L слов.

Подобным же образом можно ограничить память для хранения процессом p массива outp. Т.к. outp[i] не меняется для i < sp, можно предположить, что p выводит эти слова окончательно и более не хранит их (они представлены как W на Ðèñóíêе 3.2). Т.к. outp[i] = udef для всех i  sp + L, эти значения outp[i] также не нужно хранить. Подмассив outp[sp..sp +L—1] назовем принимаемое окно p. Принимаемое окно представлено на Ðèñóíêе 3.2 как u для неозначенных слов и R для слов, которые были приняты. Только слова, которые попадают в это окно, хранятся процессом. Леммы 3.6 и 3.7 показывают, что не более 2L слов хранятся процессом в любой момент времени.

Ограничение чисел последовательности. В заключение будет показано, что числа последовательности могут быть ограничены, если используются fifo-каналы. При использовании fifo предположения можно показать, что номер порядковый номер пакета, который получен процессом p всегда внутри 2L-окрестности s_p. Обратите внимание, что fifo предположение используется первый раз.

Ëåììà 3.8 Утверждение P', определяемое как

P'  P

/\ <pack, w, i> is behind <pack, w', i'> in Qp  i > i' - L (4p)

/\ <pack, w, i> is behind <pack, w', i'> in Qq  i > i' - L (4q)

/\ <pack,w,i> Qp  i ap - lp (5p)

/\ <pack,w,i> Qq  i aq - lq (5q)

является инвариантом Àëãîðèòìа 3.1.

Äîêàçàòåëüñòâî. Т.к. уже было показано, что P - инвариант, мы можем ограничиться доказательством того, что (4p), (4q), (5p) и (5q) выполняются изначально и сохраняются при любом перемещении. Заметим, что в начальном состоянии очереди пусты, следовательно (4p), (4q), (5p) и (5q) очевидно выполняются. Сейчас покажем, что перемещения сохраняют истинность этих утверждений.

Sp: Чтобы показать, что S_p сохраняет (4p) и (5p), заметим, что S_p не добавляет пакетов в Qp и не меняет ap.

Чтобы показать, что S_p сохраняет (5q), заметим, что если S_p добавляет пакет <pack, w, i> в Q_q, то i  ap, откуда следует, что i aq - lq (из Ëåììы 3.3).

Чтобы показать, что S_p сохраняет (4q), заметим, что если < pack, w', i'> в Q_q, тогда из (lq)
i' < sp + lp, следовательно, если S_p добавляет пакет < pack, w, i> с i  ap, то из Леммы 3.3 следует i' < ap+L  i+L.

Rp: Чтобы показать, что R_p сохраняет (4p) and (4q), заметим, что Rp не добавляет пакеты в Qp или Qq.

Чтобы показать, что R_p сохраняет (5p), заметим, что когда ap увеличивается (при принятии <pack, w', i'>) до i' - lq +1, тогда для любого из оставшихся пакетов <pack, w, i> в Qp мы имеем i > i' - L (из 4р). Значит неравенство i  ap - lp сохраняется после увеличения ap.

Чтобы показать, что R_p сохраняет (5q), заметим, что Rp не меняет Qq и aq.

Lp: Действие Lp не добавляет пакетов в Qp или Qq, и не меняет значения ap или aq; значит оно сохраняет (4p), (4q), (5p) и (5q).

Из симметрии протокола следует, что Sq, Rq и Lq тоже сохраняет P'. 

Ëåììà 3.9 Из P' следует, что

w,i> Qp  sp -L i< sp +L

и

w,i> Qq  sq -L i< sq +L.

Äîêàçàòåëüñòâî. Пусть w,i>  Qp. Из (lp), i < sq + lq, и из Ëåììы 3.3 i < sp + L. Из (5p), i  ap— lp, и из Ëåììы 3.3 i  sp— L. Утверждение относительно пакетов в Qq доказывается так же. 

Согласно Ëåììе достаточно посылать пакеты с порядковыми номерами modulo k, где
k  2L. В самом деле, имея sp и i mod k, p может вычислить i.

Выбор параметров. Значения констант lp и lq сильно влияют на эффективность протокола. Их влияние на пропускную способность протокола анализируется в [Sch91, Chapter 2]. Оптимальные значения зависят от числа системно зависимых параметров, таких как

время связи, т.е., время между двумя последовательными операциями процесса,

время задержки на обмен, т.е., среднее время на передачу пакета от p к q и получение ответа от q к p,

вероятность ошибки, вероятность того, что конкретный пакет потерян.

Протокол, чередующий бит. Интересный случай протокола скользящего окна получается, когда L = 1, ò.å., lp = 1 и lq= 0 (или наоборот). Переменные ap и aq, инициализируется значениями -lp и -lq, а не 0. Можно показать, что ap + lq = sp и aq + lp = sq всегда выполняется, значит только одно ap и sp (и aq и sq) нужно хранить в протоколе. Хорошо известный протокол, чередующий бит [Lyn68] получается, если использование таймеров дополнительно ограничивается, чтобы гарантировать, что станции посылают сообщения в ответ.

3.2 Протокол, основанный на таймере

Теперь мы изучим роль таймеров в проектировании и проверке протоколов связи, анализируя упрощенную форму t-протокола Флэтчера и Уотсона (Fletcher и Watson) для сквозной передачи сообщений. Этот протокол был предложен в [FW78], но (несколько упрощенный) подход этого раздела взят из [Tel91b, Раздел 3.2]. Этот протокол обеспечивает не только механизм для передачи данных (как сбалансированный протокол скользящего окна Раздела 3.1), но также открытие и закрытие соединений. Он устойчив к потерям, дублированию и переупорядочению сообщений.