Таненбаум Э. Компьютерные сети

Подождите немного. Документ загружается.

254 Глава 3. Уровень передачи данных

Протоколы скользящего окна 255

тверждение и окно сдвигается на одну позицию. В отличие от окна отправителя,

окно получателя всегда сохраняет свой изначальный размер. Окно единичного

размера говорит о том, что уровень передачи данных может принимать кадры

только в установленном порядке, однако при больших размерах окна это не так.

Сетевому уровню, напротив, данные всегда предоставляются в строгом порядке,

независимо от размера окна уровня передачи данных.

На рис. 3.9 показан пример для окна с максимальным размером 1. Вначале

кадров в окне нет, поэтому само окно пустое и его верхний и нижний края совпа-

дают.

Получатель

Рис. 3.9. Скользящее окно размера 1 с 3-битовым порядковым номером: начальная

ситуация (а); после отправки первого кадра (б); после приема первого кадра (в);

после приема первого подтверждения (г)

Протокол однобитового скользящего окна

Прежде чем рассматривать общий случай, изучим протокол скользящего окна

с максимальным размером окна, равным 1. Такой протокол использует метод ожи-

дания, поскольку, отослав кадр, отправитель, прежде чем послать следующий кадр,

должен дождаться подтверждения.

Данный протокол приведен в листинге 3.5. Как и другие протоколы, он начи-

нается с определения некоторых переменных. Переменная next_f rame_to_send со-

держит номер кадра, который отправитель пытается послать. Аналогично пере-

менная frame_expected хранит номер кадра, ожидаемого получателем. В обоих

случаях возможными значениями могут быть только 0 и 1.

В нормальной ситуации только один уровень передачи данных может начи-

нать передачу. Другими словами, только одна из программ должна содержать об-

ращения к процедурам to_physica1_layer и start_timer вне основного цикла. Если

оба уровня передачи данных начинают одновременно передавать, возникает не-

простая ситуация. Начинающая машина получает первый пакет от своего сете-

вого уровня, создает из него кадр и посылает его. Когда этот (или другой) кадр

прибывает, получающий уровень передачи данных проверяет, не является ли

этот кадр дубликатом, аналогично протоколу 3. Если это тот кадр, который ожи-

дался, он передается сетевому уровню и окно получателя сдвигается вверх.

Листинг 3.5. 1-битовый протокол скользящего окна

/* Протокол 4 (скользящее окно) является дуплексным и более надежным, чем протокол 3.

fdefine MAX_SEQ I /* в протоколе 4 должно быть равно 1 */

typedef enum {frame_arrival. cksum_err, timeout} event_type;

finclude "protocol.h"

void protocol4 (void)

{

seq_nr next_frame_to_send:

seq_nr frame_expected;

frame r. s:

packet buffer;

event_type event:

next_frame_to_send = 0:

frame_expected = 0;

from_network_layer(&buffer);

s.info = buffer:

s.seq = next_frame_to_send;

s.ack = 1 - frame_expected:

данных */

to_physical_layer(&s):

start_timer(s.seq);

while (true) {

wait_for_event(&event):

"err или timeout */

if (event = frame_arrival) •

from_physical_layer(&r);

/* только 0 или 1 */

/* временная переменная */

/* текущий посланный пакет */

/* номер следующего кадра в исходящем потоке */

/* номер ожидаемого кадра */

/* получить первый пакет у сетевого уровня */

/* подготовить первый кадр для передачи */

/* вставить порядковый номер в кадр */

/* подтверждение, посылаемое «верхом» на кадре

/* послать кадр по каналу */

/* запустить таймер ожидания подтверждения */

/* ждать возможного события: frame_arrival, cksum_

/* кадр прибыл в целости */

/* получить кадр */

if (r.seq == frame_expected) {

/* обработать входящий поток кадров */

to_network_layer(&r.info); /* передать пакет сетевому уровню */

inc(frame_expected); /* инвертировать порядковый номер кадра,

ожидаемого в следующий раз */

уровня */

кадра */

if (r.ack == next_frame_to_send) { /* обработать исходящий поток кадров */

from_network_layer(&buffer): /* получить следующий пакет у сетевого

inc(next_frame_to_send): /* инвертировать порядковый номер посылаемого

•^j^.

256 Глава 3. Уровень передачи данных

Протоколы скользящего окна 257

s.info = buffer:

s.seq = next_frame_to_send;

s.ack = 1 - frame_expected;

to_physica1_layer(&s);

startjtimer(s.seq):

/* подготовить кадр для передачи */

/* вставить порядковый номер в кадр */

/* порядковый номер последнего полученного кадра

/* передать кадр */

/* запустить таймер ожидания подтверждения */

Поле подтверждения содержит номер последнего полученного без ошибок

кадра. Если этот номер совпадает с номером кадра, который пытается передать

отправитель, последний понимает, что этот кадр успешно принят получателем, и

что он может пересылать следующий кадр. В противном случае он должен про-

должать попытки переслать тот же кадр.

Теперь давайте изучим протокол 4 и посмотрим, насколько он устойчив к не-

стандартным ситуациям. Предположим, что машина А пытается послать кадр О

машине В, а машина В пытается послать кадр 0 машине А. Предположим также,

что на машине А установлен слишком короткий период ожидания подтвержде-

ния. Соответственно, машина А посылает серию одинаковых кадров со значе-

ниями полей seq=0 и ack=l.

Когда первый неповрежденный кадр прибудет на машину В, он будет принят,

и значение переменной frame_expected будет установлено равным 1. Все после-

дующие кадры будут проигнорированы, поскольку машина В будет теперь ожи-

дать кадра с порядковым номером 1, а не 0. Более того, поскольку у всех кадров

дубликатов значение поля аск=1, а машина В продолжает ожидать подтвержде-

ния для кадра 0, то В и не станет запрашивать новый пакет у своего сетевого

уровня.

В ответ на каждый отвергнутый дубликат, присылаемый машиной А, маши-

на В посылает кадр, содержащий поля seq=O и аск=О. Наконец, один из этих кад-

ров принимается машиной Л, в результате чего машина А переходит к передаче

А отправляет (0, 1, АО)

А получает (О, О, ВО)*

А отправляет (1, О, А1)

А получает (1, 1, В1)*

А отправляет (0, 1, А2)

А получает (О, О, В2)*

А отправляет (1,0, A3)

В получает (0, 1, АО)*

В отправляет (0, 0, ВО)

В получает (1, 0, А1)*

8 отправляет (1, 1, В1)

В получает (0,1, А2)*

В отправляет (0, О, В2)

В получает (1, 0, A3)*

В отправляет (1,1, ВЗ)

Л отправляет (0, 1, АО) \/ В отправляет (0, 1, ВО)

/** В получает (0, 1, АО)*

/ .В отправляет (0, 0, ВО)

* /

А получает (0, 1, ВО)* /

А отправляет (0, 0, АО) -vC^w

/ *• В получает (0, 0, АО)

У В отправляет (1, О, В1)

А получает (0, 0, ВО)

А отправляет (1, 0, А1) - -__sw

^""^ В получает (1, 0, А1 )*

В отправляет (1, 1, В1)

А получает (1, 0, В1)*

А отправляет (1, 1, А1)

В получает (1, 1,А1)

В отправляет (0, 1, В2)

Время

Рис. 3.10. Два сценария для протокола 4: нормальная ситуация (а); нештатная ситуация (б).

Обозначения: (seq, ack, номер пакета). Звездочка означает,

что сетевой уровень принял пакет

следующего пакета. Никакая комбинация потерянных кадров или преждевре-

менно истекших интервалов ожидания не может заставить этот протокол ни вы-

дать сетевому уровню дубликат пакета, ни пропустить пакет, ни зависнуть.

Однако, если обе стороны одновременно вышлют друг другу начальный па-

кет, возникает запутанная ситуация, проиллюстрированная на рис. 3.10. В левой

части рисунка показано нормальное функционирование протокола. Правая часть

рисунка демонстрирует аномальную ситуацию. Если машина В ожидает первого

кадра от машины А, прежде чем послать свой первый кадр, то последователь-

ность будет такой, как показана в левой части рисунка. При этом принимается

каждый кадр. Однако если машины А и В одновременно начнут передачу, их пер-

вые кадры пересекутся и уровни передачи данных попадут в ситуацию 6. В си-

туации а с каждым кадром прибывал новый пакет и дубликатов нет. В ситуа-

ции б половина кадров содержит дубликаты несмотря на то, что ошибок в канале

связи не было. Подобные ситуации могут возникнуть в результате преждевре-

менного истечения периода ожидания, даже если одна сторона начнет диалог пер-

вой. В самом деле, если время ожидания истечет слишком быстро, кадр может

быть послан три и более раз.

Протокол с возвратом на п

До сих пор мы по умолчанию подразумевали, что время, необходимое на переда-

чу кадра от отправителя к получателю, и время, необходимое на передачу под-

тверждения от получателя к отправителю, пренебрежимо малы. Иногда это пред-

положение является совершенно неверным. В таких ситуациях большое время

прохождения кадров по сети может значительно снижать эффективность исполь-

зования пропускной способности канала. В качестве примера рассмотрим спутни-

ковый канал связи с пропускной способностью 50 Кбит/с и временем, требуемым

для прохождения сигнала в оба конца, равным 500 мс. Попытаемся использовать

протокол 4 для пересылки кадров размером в 1000 бит через спутник. В момент

времени t = 0 отправитель начинает посылать первый кадр. В момент времени

~1= 20 мс кадр полностью послан. В момент времени £ = 270 мс получатель принял

кадр полностью и отправил обратно подтверждение. В итоге в лучшем случае

только через 520 мс после начала передачи кадра подтверждение будет получено

отправителем. В данном случае еще предполагается, что приемник не тратит вре-

мени на обработку принятого кадра и подтверждение такое короткое, что вре-

менем его передачи и приема можно пренебречь. Это означает, что передающая

машина была заблокирована в течение 500/520, или 96 % времени. Другими сло-

вами, использовалось только 4 % доступной пропускной способности. Очевидно,

что сочетание большого времени прохождения сигнала, высокой пропускной

способности и коротких кадров совершенно неприемлемо с точки зрения эффек-

тивности.

Описанная проблема является следствием правила, заставлявшего отправите-

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

это требование, можно значительно повысить эффективность. Решение пробле-

мы заключается в разрешении отправителю послать не один кадр, а несколько,

например да, прежде чем остановиться и перейти в режим ожидания подтвержде-

258 Глава 3. Уровень передачи данных

Протоколы скользящего окна 259

ний. Можно подобрать число w так, чтобы отправитель мог безостановочно по-

сылать кадры. В приведенном ранее примере w должно быть равно, по меньшей

мере, 26. Отправитель начинает, как и ранее, с передачи кадра 0. К тому моменту,

когда он закончит отправку 26 кадров (в момент времени t = 520 мс), как раз

прибудет подтверждение кадра 0. Затем подтверждения станут прибывать каж-

дые 20 мс. Таким образом, отправитель будет получать разрешения на передачу

следующего кадра как раз вовремя. В любой момент времени у отправителя бу-

дет 25 или 26 неподтвержденных кадров и, следовательно, достаточно будет окна

размером 26.

Такая техника называется конвейерной обработкой. Если пропускная спо-

собность канала равна Ь бит/с, размер кадра равен / бит, то время передачи одно-

го кадра составит 1/Ь с. Пусть время прохождения сигнала по каналу в оба конца

равно R с. После отправки последнего бита информационного кадра в течение

R/2 с происходит его пересылка получателю и в течение еще по крайней мере

R/2 с — прием подтверждения отправителем. Поэтому общая задержка составля-

ет R с. В протоколе с ожиданием линия занята в течение 1/Ь с и свободна в тече-

ние R с, что дает коэффициент эффективности использования линии равный

//(/ + ЬК). При / < bR эффективность использования линии будет менее 50 %.

Конвейерный режим может использоваться для загрузки избежания простаива-

ния линии, если время прохождения сигнала значительно по сравнению со вре-

менем самой передачи. Если же задержка распространения сигнала мала, допол-

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

При конвейерном режиме передачи кадров по ненадежному каналу возникает

ряд серьезных проблем. Во-первых, что произойдет, если повредится или поте-

ряется кадр в середине длинного потока? Большое количество последующих кад-

ров прибудет к получателю прежде, чем отправитель обнаружит, что произошла

ошибка. Когда поврежденный кадр приходит получателю, он, конечно, должен

быть отвергнут, однако что должен делать получатель со всеми правильными по-

следующими кадрами? Как уже говорилось, получающий уровень передачи дан-

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

рис. 3.11 изображен эффект, оказываемый конвейерной обработкой на исправле-

ние ошибок. Сейчас мы рассмотрим этот вопрос более подробно.

Есть два способа решения проблемы возникновения ошибок при конвейери-

зации кадров. Первый способ называется возвратом на и и заключается просто в

игнорировании всех кадров, следующих за ошибочным. Для таких кадров под-

тверждения не посылаются. Эта стратегия соответствует приемному окну раз-

мера 1. Другими словами, уровень передачи данных отказывается принимать

какой-либо кадр, кроме кадра со следующим номером, который он должен пере-

дать сетевому уровню. Если окно отправителя заполнится раньше, чем истечет

время ожидания, конвейер начнет простаивать. Наконец, лимит времени у от-

правителя истечет, и он начнет передавать повторно сразу все кадры, не полу-

чившие подтверждения, начиная с поврежденного или потерянного кадра. Такой

подход при высоком уровне ошибок может привести к потере большой доли про-

пускной способности канала.

На рис. 3.11, а изображен возврат на п для случая большого окна приемника.

Кадры 0 и 1 корректно принимаются, и высылается подтверждение этого факта.

Однако кадр 2 потерялся или был испорчен. Ничего не подозревающий отправи-

тель продолжает посылать кадры, пока не выйдет время ожидания кадра 2. Толь-

ко после этого он возвращается к месту сбоя и заново передает все кадры, начи-

ная с кадра 2 (отправляя 2, 3, 4 и т. д.)

Ошибка Кадры, отвергнутые

уровнем передачи данных

Время >

Интервал ожидания •!

Ошибка Буферизированы уровнем

передачи данных

Пакеты 2-8 переданы

сетевому уровню

Рис. 3.11. Конвейеризация и коррекция ошибок: эффект при размере окна 1 (а);

эффект при размере окна > 1 (б)

Другая общая стратегия обработки ошибок при конвейерной передаче кад-

ров, называемая выборочным повтором, заключается в том, что получатель хра-

нит в буфере все правильные кадры, принятые им после неверного или потерян-

ного кадра. При этом неверный кадр отбрасывается. Когда отправитель наконец

замечает, что что-то случилось (то есть заканчивается время ожидания подтвер-

ждения), он просто отправляет еще раз только потерянный или испорченный

кадр, не повторяя отправку всех последующих, как это продемонстрировано на

рис. 3.11, б. Если вторая попытка будет успешной, получающий уровень переда-

чи данных сможет быстро передать накопившиеся пакеты сетевому уровню, по-

сле чего выслать подтверждение получения кадра с наибольшим номером. Выбо-

рочный повтор часто комбинируется с отправкой получателем «отрицательного

260 Глава 3. Уровень передачи данных

Протоколы скользящего окна 261

подтверждения» (NAK — Negative Acknowledgement) при обнаружении ошибки,

например, при неверной контрольной сумме или при измененном порядке сле-

дования кадров. NAK стимулируют повторную отправку еще до того, как закон-

чится время ожидания подтверждения от отправителя. Таким образом, эффек-

тивность работы несколько повышается.

На рис. 3.11, б кадры 0 и 1 снова принимаются корректно, а кадр 2 теряется.

После получения кадра 3 уровень передачи данных приемника замечает, что

один кадр выпал из последовательности. Для кадра 2 отправителю посылается

NAK, однако кадр 3 сохраняется в специальном буфере. Далее прибывают кадры

4 и 5, они также буферизируются уровнем передачи данных вместо передачи на

сетевой уровень. NAK 2 приходит к отправителю, заставляя его переслать кадр 2.

Когда последний оказывается у получателя, у уровня передачи данных уже име-

ются кадры 2, 3, 4 и 5, которые сразу же в нужном порядке отдаются сетевому

уровню. Теперь уже можно выслать подтверждение получения всех кадров, вклю-

чая пятый, что и показано на рисунке. Если NAK вдруг потеряется, то отправи-

тель по окончании времени ожидания 2 сам отправит кадр 2 (и только его!), од-

нако это может произойти значительно позже, чем при помощи NAK. Короче го-

воря, NAK ускоряет процесс повторной пересылки испорченного кадра.

Метод выборочного повтора соответствует приемному окну размером более 1.

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

в буфере до тех пор, пока все предыдущие кадры не будут переданы сетевому

уровню. При большом окне данный способ может потребовать значительного раз-

мера буфера.

Листинг 3.6. Протокол скользящего окна с возвратом на п

I* Протокол 5 (конвейерный) допускает наличие нескольких неподтвержденных кадров.

Отправитель может передать до MAX_SEQ кадров, не ожидая подтверждения. Кроме того, в

отличие от предыдущих протоколов, не предполагается, что у сетевого уровня всегда есть

новые пакеты. При появлении нового пакета сетевой уровень инициирует событие network_

layer_ready */

#define MAX_SEQ 7 /* должно быть 2

n-l */

typedef enum {frame_arrival. cksum_err, timeout, network_layer_ready} event_type:

linclude "protocol,h"

static boolean between(seqjir a, seq_nr b, seqjir c)

/* возвращает true, если (a <=b < с циклично: иначе false */

|| b

(((a

&& (b

c))

return(true);

else

return(false);

((c

&& (a <=

b)) || ((b

&& (c

a)))

static void send_data(seq_nr framejir, seqjir frame_expected, packet buffer[])

/* подготовить и послать информационный кадр */

frame s: /* временная переменная */

s.info = buffer[frame_nr]; /* вставить пакет в кадр */

s.seq = framejir; /* вставить порядковый номер в кадр */

s.ack = (frame_expected + MAXjSEQ) % (MAXjSEQ +1); /* подтверждение, посылаемое

«верхом» на кадре данных */

tojphysical_layer(&s); /* послать кадр по каналу */

start_timerСframejir); /* запустить таймер ожидания подтверждения */

void protocol5(void)

{

seqjir next_frame_to_send; /* MAXjSEQ > 1; используется для исходящего потока

seqjir ack_expected; /* самый старый неподтвержденный кадр */

seqjir frame_expected: /* следующий кадр, ожидаемый во входящем потоке */

frame г; /* временная переменная */

packet buffer[MAX_SEQ+l]; /* буферы для исходящего потока */

seqjir nbuffered; /* количество использующихся в данный момент выходных буферов

seqjir i: /* индекс массива буферов */

event_type event;

enablejietwork_layer(); /* разрешить события networkjayerj^eady */

ack_expected = 0; /* номер следующего ожидаемого входящего подтверждения

next_framej;o_send = 0: /* номер следующего посылаемого кадра */

frame_expected = 0; /* номер следующего ожидаемого входящего кадра */

nbuffered = 0; /* вначале буфер пуст */

while (true) {

wait_for_event(&event); /* четыре возможных события: см. event_type выше */

switch(event) {

case network_layerj"eady: /* у сетевого уровня есть пакет для передачи */

/* получить, сохранить и передать новый кадр */

from_networkjayer(&buffer[next_frame_to_send]): /* получить новый пакет

у сетевого уровня */

nbuffered = nbuffered +1; /* увеличить окно отправителя */

send_data(next_frame_to_send. frame_expected. buffer); /* передать кадр

inc(next_frame_tojsend): /* увеличить верхний край окна отправителя */

break;

case frame arrival:

/* прибыл кадр с данными или с подтверждением

Уровня */

т. д. */

fromjDhysical_layer(&r); /* получить пришедший кадр у физического

if (r.seq = frame_expected) {

/* кадры принимаются только по порядку номеров */

tojietwork_layer(&r.info): /* передать пакет сетевому уровню */

inc(frame_expected); /* передвинуть нижний край окна получателя

/* подтверждение для кадра п подразумевает также кадры п - 1. п - 2

262 Глава 3. Уровень передачи данных

while (between(ack_expected, rack, next_frame_to_send)) {

/* отправить подтверждение вместе с информационным кадром */

nbuffered = nbuffered - 1; /* в буфере на один кадр меньше */

stop_timer(ack_expected): /* кадр прибыл в целости; остановить

таймер */

inc(ack_expected):

}

break;

case cksum_err: ;

break;

/* уменьшить окно отправителя */

/* плохие кадры просто игнорируются */

case timeout: /* время истекло; передать повторно все неподтвержденные

кадры */

next_frame_to_send = ack_expected: /* номер первого посылаемого

повторно кадра */

for (i = 1; i <= nbuffered: i++) {

send_data(next_frame_to_send, frame_expected. buffer); /* переслать

повторно 1 кадр */

inc(next_frame_to_send); /* приготовиться к пересылке следующего

кадра */

}

if (nbuffered < MAXJEQ)

enabi ejietworkj ауег ();

else

disable_network_layer();

}

Выбор одной из двух приведенных ранее стратегий является вопросом ком-

промисса между пропускной способностью и размером буфера уровня передачи

данных. В зависимости от того, что в конкретной ситуации является более кри-

тичным, может использоваться тот или иной метод. В листинге 3.6 показан кон-

вейерный протокол, в котором принимающий уровень передачи данных прини-

мает кадры по порядку. Все кадры, следующие за ошибочным, игнорируются.

В данном протоколе мы впервые отказались от предположения, что у сетевого

уровня всегда есть неограниченное количество пакетов для отсылки. Когда у се-

тевого уровня появляется пакет, который он хочет отправить, уровень иниции-

рует событие networkJ ayer_ready. Однако чтобы ограничить количество непод-

твержденных пакетов числом MAX_SEQ, уровень передачи данных должен иметь

возможность отключать на время сетевой уровень. Для этой цели служит пара

библиотечных процедур — enabl e_network_l ауег и disabl ejietworkj ауег.

Обратите внимание на то, что в любой момент времени может быть МАХ_

SEQ, а не MAX_SEQ + 1 неподтвержденных пакетов, хотя различаются МАХ_

SEQ + 1 порядковых номеров: от 0 до MAX_SEQ. Чтобы понять, почему необхо-

димо такое ограничение, рассмотрим сценарий с MAX__SEQ = 7.

1. Отправитель посылает кадры с 0 по 7.

2. Подтверждение для кадра 7 наконец прибывает к отправителю.

Протоколы скользящего окна 263

3. Отправитель посылает следующие восемь кадров, снова с номерами с 0 по 7.

4. Еще одно подтверждение для кадра 7 прибывает к отправителю.

Но вот вопрос: все восемь кадров, входящих во второй набор, благополучно

дошли до адресата или все они потерялись (включая игнорированные кадры по-

сле ошибочного)? В обоих случаях получатель отправит кадр 7 в качестве под-

тверждения. У отправителя нет способа отличить один случай от другого. По

этой причине максимальное количество неподтвержденных кадров должно быть

ограничено числом MAX_SEQ.

Хотя в протоколе 5 кадры, поступившие после ошибки, не буферизируются

получателем, тем не менее, отправитель должен хранить отправленные кадры в

своем буфере, пока не получит на них подтверждение. Если поступает подтвер-

ждение на кадр п, кадры я - 1, « - 2 (то есть все предыдущие кадры) автоматически

считаются подтвержденными. Эта особенность наиболее важна в случае потери

или повреждения какого-либо кадра с подтверждением. Получив подтвержде-

ние, уровень передачи данных проверяет, не освободился ли у него какой-нибудь

буфер. Если буфер освобождается, то заблокированному ранее сетевому уровню

можно снова разрешить инициировать события network_layer_ready.

Для этого протокола предполагается, что всегда есть обратный трафик, по ко-

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

то никакие подтверждения отосланы не будут. Протокол 4 не нуждается в по-

добном допущении, поскольку за каждым принятым кадром следует обратный,

даже если только что уже был отправлен какой-то кадр в сторону отправителя.

В следующем протоколе проблема отсутствия обратного трафика будет решена

гораздо элегантней.

Поскольку протокол 5 хранит несколько неподтвержденных кадров, ему тре-

буется несколько таймеров, по одному на кадр. Для каждого кадра время считает-

ся независимо от других. Все таймеры могут симулироваться программно, исполь-

зую единственные аппаратные часы, вызывающие периодические прерывания.

Данные таймеров могут храниться в программе в виде связанного списка, каж-

дый узел которого будет хранить количество временных интервалов системных

часов, оставшихся до истечения срока ожидания, номер кадра и указатель на сле-

дующий узел списка.

/-Реальное время

\\\

N. N^ Указатель на следующий таймер

Номер кадра

^ Интервал времени в тиках

а б

Рис. 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, б. Такая

организация таймеров не требует выполнения большой работы при каждом пре-

рывании от системных часов, хотя при работе процедур start_timer и stop_timer

требуется сканирование списка. В протоколе у данных процедур имеется вход-

ной параметр, означающий номер кадра, таймер которого нужно запустить или

остановить.

Протокол с выборочным повтором

Протокол 5 хорошо работает, если ошибки встречаются нечасто, однако при пло-

хой линии он тратит впустую много времени, передавая кадры по два раза. В ка-

честве альтернативы можно использовать протокол, в котором получатель буфе-

ризирует кадры, принятые после потерянного или испорченного кадра. Такой

протокол не отвергает кадры только лишь потому, что предыдущий кадр был по-

врежден или потерян.

В этом протоколе и отправитель, и получатель работают с окнами допусти-

мых номеров кадров. Размер окна отправителя начинается с нуля и растет до не-

которого определенного уровня, MAX_SEQ. Размер окна получателя, напротив,

всегда фиксированного размера, равного MAX_SEQ. Получатель должен иметь

буфер для каждого кадра, номер которого находится в пределах окна. С каждым

буфером связан бит, показывающий, занят буфер или свободен. Когда прибывает

кадр, функция between проверяет, попал ли его порядковый номер в окно. Если

да, то кадр принимается и хранится в буфере. Это действие производится неза-

висимо от того, является ли данный кадр следующим кадром, ожидаемым сете-

вым уровнем. Он должен храниться на уровне передачи данных до тех пор, пока

все предыдущие кадры не будут переданы сетевому уровню в правильном поряд-

ке. Алгоритм протокола показан в листинге 3.7.

Листинг 3.7. Протокол скользящего окна с выборочным повтором

/* Протокол б (выборочный повтор) принимает кадры в любом порядке, но передает их

сетевому уровню, соблюдая порядок. С каждым неподтвержденным кадром связан таймер. При

срабатывании таймера передается повторно только этот кадр, а не все неподтвержденные

кадры, как в протоколе 5. */

/* должно быть 2*п-1 */

#define MAX_SEQ 7

#define NR_BUFS ((MAX_SEQ

typedef enum {frame_arrival, cksum_err, timeout, network_layer_ready, ack_timeout}

event_type:

linciude "protocol,h"

Протоколы скользящего окна

265

boolean nojiak = true;

seq_nr oldest_frame = MAX_SEQ+1:

/* отрицательное подтверждение (nak) еще не посылалось

/* начальное значение для симулятора */

static boolean between(seq_nг a. seqjir b, seqjir c)

/* то же. что и в протоколе 5, но короче и понятнее */

return ((а <= Ь) && (Ь < с)) || ((с < а) && (а <= b)) || ((b < с)

(с < а));

static void send_frame(frame_kind fk, seqjir framejir, seqjir frame_expected. packet

buffer[])

{

/* сформировать и послать данные, а также положительное или отрицательное

подтверждение */

frame s: /* временная переменная */

s.kind = fk: /* kind == data, ack, или nak */

if (fk = data) s.info = buffer[frame_nr % NR_BUFS];

s.seq = framejir; /* имеет значение только для информационных кадров

s.ack = (framejexpected + MAXjSEQ) % (MAXjSEQ + 1);

if (fk = nak) nojiak = false; /* один nak на кадр, пожалуйста */

to_physical_layer(&s): /* переслать кадр */

if (fk = data) start_timer(framejir % NR_BUFS);

stop_ack_timer(); /* отдельный кадр с подтверждением не нужен */

}

void protoco!6(void)

{

seqjir ack_expected:

seqjir next_frame_to_send;

seqjir frame_expected;

seqjir too_far;

jfit i;

^frame r;

packet out_buf[NR_BUFS]:

packet in_buf[NR_BUFS];

boolean arrived[NRj3UFS];

seqjir nbuffered; /* количество

eventjtype event;

/* нижний край окна отправителя */

/* верхний край окна отправителя + 1 */

/* нижний край окна получателя */

/* верхний край окна получателя + 1 */

/* индекс массива буферов */

/* временная переменная */

/* буферы для исходящего потока */

/* буферы для входящего потока */

/* входящая битовая карта */

использующихся в данный момент выходных буферов

enabl ejietworkj ayer ():

ack_expected = 0;

next_frame_toj3end = 0;

frame_expected = 0:

too_far = NR_BUFS:

nbuffered = 0:

for (i = 0; i < NR_BUFS:

while (true) {

/* инициализация */

/* следующий номер подтверждения во входном потоке

/* номер следующего посылаемого кадра */

/* номер следующего ожидаемого входящего кадра */

/* верхний край окна получателя + 1 */

/* вначале буфер пуст */

arrived[i] = false:

266 Глава 3. Уровень передачи данных

Протоколы скользящего окна 267

wait_for_event(&event):

/* пять возможных событий: см. event_type выше

switch(event) {

case network_layer_ready: /* получить, сохранить и передать новый кадр

nbuffered = nbuffered +1; /* увеличить окно отправителя */

from_network_layer(&out_buf[next_frame_to_send % NRJ3UFS]): /* получить

новый пакет у сетевого уровня */

send_frame(data, next_frame_to_send. frame_expected, out_buf): /*

передать кадр */

inc(next_frame_to_send): /* увеличить верхний край окна отправителя */

break;

уровня */

timer!);

case frame_arrival: /* прибыл кадр с данными или с подтверждением */

from_physical_1ayer(&r); /* получить пришедший кадр у физического

if (г.kind = data) {

/* кадр прибыл в целости */

if ((r.seq != frame_expected) && nojiak)

send_frame(nak, 0. frame_expected, out_buf): else start_ack_

BUFS] == false)) {

if (between(frame_expected, r.seq. too_far) && (arrived[r.seq^NR_

/* кадры могут приниматься в любом порядке */

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(); /* запустить вспомогательный таймер на

случай, если потребуется пересылка подтверждения отдельным кадром */

}

получателя */

}

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_

frame_to_send))

buf);

while (between(ack_expected. r.ack. next_frame_to_send)) {

nbuffered = nbuffered - 1: /* отправить подтверждение вместе с

информационным кадром */ *,

stop timerCack expected % NR_BUFS): /* кадр прибыл в целости /

inc(ack_expectid); /* передвинуть нижний край окна отправителя /

}

break:

case cksum_err: if (no_nak) send_frame(nak, 0, frame_expected, out_buf);

break: /* поврежденный кадр */

case timeout: send_frame(data, oldest_frame. frame_expected. out_buf);

break: /* время истекло */

case ack_timeout: send_frame(ack.O.frame_expected, out_buf): /* истек

период ожидания «попутки» для подтверждения: послать подтверждение */

}

if (nbuffered < NR_BUFS) enable_network_layer(); else disable_network_layer():

Способность протокола принимать кадры в произвольном порядке вызывает

некоторые проблемы, отсутствовавшие в предыдущих протоколах, в которых все

пакеты принимались строго по порядку номеров. Проще всего проиллюстриро-

вать это на примере. Предположим, что порядковый номер кадра состоит из 3 бит,

так что отправитель может посылать до семи кадров, прежде чем перейти в ре-

жим ожидания подтверждения. Начальное состояние окон отправителя и получа-

теля изображено на рис. 3.13, а. Отправитель передает кадры с 0 по 6. Окно полу-

чателя позволяет ему принимать любые кадры с номерами от 0 по 6 включительно.

Все семь кадров прибывают успешно, поэтому получатель подтверждает их при-

ем и передвигает окно для приема кадров с номерами 7, 0, 1, 2, 3, 4 и 5, как пока-

зано на рис. 3.12, б. Все семь буферов помечаются как свободные.

Отправитель

Получатель

0 12 3 4 5 6 7 0 12 3 4 5 6 7 0 12 3 4 5 6 7 0 12 3 4 5 6 7

0 12 3 4 5

0 12 3

4 5 6 7 0 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. Уровень передачи данных

Протоколы скользящего окна

269

Причина неудачи в том, что при сдвиге приемного окна новый интервал до-

пустимых номеров кадров перекрыл старый интервал. Соответственно, присы-

лаемый набор кадров может содержать как новые кадры (если все подтверждения

были получены), так и повторно высланные старые кадры (если подтверждения

были потеряны). У принимающей стороны нет возможности отличить одну си-

туацию от другой.

Решением данной проблемы является предоставление гарантии того, что в сдви-

нутом положении окно не перекроет исходное окно. Для этого размер окна не

должен превышать половины от количества порядковых номеров (это показано

на рис. 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,

если таймер уже был запущен, его параметры переустанавливаются на отсчет

полного интервала времени.

Важно, что период времени вспомогательного таймера должен быть сущест-

венно короче интервала ожидания подтверждения. При этом условии подтвер-

ждение в ответ на полученный правильный кадр должно приходить прежде, чем

у отправителя истечет период ожидания и он пошлет этот кадр второй раз.

Протокол б использует более эффективную стратегию обработки ошибок, чем

протокол 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. Все остальные состояния могут рассматриваться как временные,

промежуточные между этими двумя. Обычно выбираются состояния, соответст-

вующие ожидаемым событиям (это соответствует вызову процедуры wait (event)

в наших примерах протоколов). Состояние протокольной машины полностью оп-

ределяется состоянием ее переменных. Количество состояний равно 2", где п —

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

Состояние всей системы представляет собой комбинацию всех состояний двух

протокольных машин и состояний канала. Состояние канала определяется его

содержимым. При использовании протокола 3 у канала может быть четыре воз-

можных состояния: кадр 0 или кадр 1, перемещающийся от отправителя к полу-

чателю, кадр подтверждения, двигающийся в противоположном направлении, или

Верификация протоколов 271

пустой канал. Если отправитель и получатель могут находиться в двух различ-

ных состояниях, то вся система будет иметь 16 различных состояний.

Следует сказать несколько слов о состоянии канала. Концепция кадра, нахо-

дящегося в канале, конечно, является абстракцией. Имеется в виду, что кадр час-

тично передан, частично принят, но еще не обработан получателем. Кадр остает-

ся «в канале» до тех пор, пока протокольная машина не выполнит процедуру

from_physical_layer и не обработает его.

Каждое состояние может быть соединено с другими состояниями несколькими

(0 или больше) переходами. Переходы всегда соответствуют каким-либо собы-

тиям. Для протокольной машины переход происходит, когда прибывает новый

кадр, истекает время ожидания какого-либо таймера, происходит прерывание и т. д.

Для канала обычными событиями являются следующие: помещение протоколь-

ной машиной в канал нового кадра, доставка кадра протокольной машине или

потеря кадра вследствие всплеска шума. Имея полное описание протокольной

машины и характеристик канала, можно нарисовать направленный граф, изобра-

жающий все состояния в виде узлов, а переходы — в виде направленных дуг.

Одно особое состояние обозначается как начальное. Оно соответствует состоя-

нию системы в момент ее запуска или состоянию, близкому к нему. Из началь-

ного состояния можно попасть во многие (вероятно, даже во все) другие состоя-

ния с помощью серии переходов. Применяя хорошо известные методы теории

графов (например, вычисляя транзитивное замыкание графа), можно опреде-

лить, какие из состояний достижимы, а какие нет. Такой метод называется ана-

лизом достижимости (Lin и др., 1987). Данный анализ может быть полезен для

определения правильности протокола.

Формально модель протокола машины конечных состояний можно рассмат-

ривать как набор их четырех множеств (5, М, /, Т), где S — множество состояний,

в которых могут находиться процессы и канал; М — множество кадров, передаю-

щихся по каналу; / — множество начальных состояний процессов; Т — множе-

* ство переходов между состояниями.

В начальный момент времени все процессы находятся в исходном состоянии.

Затем начинают происходить события — например, появляются кадры, которые

нужно передать по каналу, или срабатывает таймер. Каждое событие может пе-

реключить один из процессов или канал в новое состояние. Тщательно нумеруя

все возможные предшественники каждого состояния, можно построить дерево

достижимости и проанализировать протокол.

Анализ достижимости может применяться для обнаружения разнообразных

ошибок спецификации протокола. Например, если какой-либо кадр может ока-

заться в таком состоянии, в котором конечный автомат не сможет определить,

какое действие следует предпринять, это означает, что спецификация ошибочна

(неполнота протокола). Если имеется ряд состояний, из которых нет выхода (то

есть никакие кадры больше не смогут передаваться), это также означает ошибку

спецификации (тупик). Менее серьезной ошибкой спецификации протокола яв-

ляется описание обработки события в состоянии, в котором это событие не мо-

жет произойти (лишний переход). Могут быть обнаружены и другие ошибки.

272 Глава 3. Уровень передачи данных

В качестве примера конечного автомата рассмотрим рис. 3.14, а. Этот граф

соответствует протоколу 3, описанному ранее, — у каждой протокольной маши-

ны может быть два состояния, а у канала — четыре состояния. Итого возможны

16 состояний, некоторые из которых недоступны из начального состояния. Не-

достижимые состояния не показаны на рисунке. Для упрощения также опущены

ситуации с ошибками контрольных сумм.

Каждое состояние помечено тремя символами: SRC, где S является 0 или 1

и соответствует номеру кадра, который пытается послать отправитель; R также

может быть равно 0 или 1 и означает номер кадра, ожидаемого получателем, а С

может принимать значения 0, 1, Л или пусто (-), в соответствии с состоянием ка-

нала. В данном примере было выбрано исходное состояние (000). То есть отпра-

витель только что послал кадр 0, получатель ожидает кадра 0, и кадр 0 находится

в канале.

Переход

Кто

управляет?

Получатель

Отправитель

Получатель

Отправитель

Получатель

Отправитель

Кадр

принят

Кадр

передан

(кадр потерян)

Подтверждение

(тайм-аут)

Подтверждение

Сетевому

уровню

Да

Нет

Рис. 3.14. Диаграмма состояний для протокола 3 (а); переходы (б)

На рис. 3.14 показаны девять типов переходов. Переход 0 заключается в по-

тере каналом содержимого. Переход 1 состоит в том, что канал успешно до-

ставляет пакет 0 получателю, при этом получатель передает пакет 0 своему се-

Верификация протоколов 273

тевому уровню, изменяет свое состояние на ожидание кадра 1 и пересылает

подтверждение. Остальные переходы приведены на рис. 3.14, б. Прибытие кадра

с неверной контрольной суммой не показано, так как оно не изменяет состоя-

ния в протоколе 3.

При нормальной работе протокола переходы 1, 2, 3 и 4 повторяются друг за

другом снова и снова. На каждом цикле доставляются два пакета, возвращая от-

правителя в исходное состояние, в котором он пытается переслать новый кадр с

последовательным номером 0. Если канал теряет кадр 0, происходит переход из

состояния (000) в состояние (00-). Наконец у отправителя срабатывает таймер

(переход 7), и система возвращается в состояние (000). Потеря подтверждения

является более сложной ситуацией, так как требует для восстановления два пе-

рехода — 7 и 5 (или 8 и 6 в симметричной ситуации).

Одно из свойств, которыми должен обладать протокол с 1-битовым порядко-

вым номером, заключается в том, что ни при каких обстоятельствах получатель

не должен передавать своему сетевому уровню два нечетных пакета подряд, не

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

графа это требование может быть перефразировано более формально так: «не долж-

но быть пути, начинающегося в исходном состоянии, при котором переход 1 осу-

ществляется два раза подряд без перехода 3 между ними, и наоборот». Из рисун-

ка видно, что данное требование удовлетворяется.

Другим сходным требованием является отсутствие пути, при котором отпра-

витель изменяет свое состояние дважды (например, с 0 на 1 и обратно на 0) при

неизменном состоянии получателя. Существование такого пути означало бы, что

два кадра подряд были безвозвратно потеряны, причем так, что получатель этого

не заметил. При этом в последовательности доставляемых сетевому уровню па-

кетов образовалась бы незамеченная брешь в два пакета.

Еще одним важным свойством протоколов является отсутствие тупиков. Ту-

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

(то есть доставлять пакеты сетевому уровню) ни при каких обстоятельствах.

_ Втерминах графической модели наличие тупика характеризуется существова-

нием подмножества состояний, достижимого из исходного состояния и обладаю-

щего двумя следующими свойствами:

1. Из этого подмножества состояний нет перехода.

2. В подмножестве нет переходов, обеспечивающих дальнейшую работу прото-

кола.

Попав в тупиковую ситуацию, протокол остается в ней навсегда. По графу

видно, что в протоколе 3 нет тупиков.

Сети Петри

Конечный автомат является не единственным методом формального описания

протокола. В данном разделе будет описана другая методика — сеть Петри

(Danthine, 1980). Сетевая модель Петри состоит из четырех основных элементов:

позиций, переходов, дуг и маркеров (или фишек). Позицией называется состоя-

ние, в котором может находиться система или ее часть. На рис. 3.15 показана сеть