ref (664672), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Информация о состоянии (передачи данных) протокола хранится в структуре данных, называемой запись соединения. (В Подразделе 3.2.1 будет показано, какая информация хранится в записи соединения). Запись соединения может быть создана и удалена для открытия и открытия соединения. Òàêèì îáðàçîì, ãîâîðÿò, ÷òî ñîåäèíåíèå îòêðûòî (на одной из станций), если существует запись соединения.

Чтобы сконцентрироваться на релевантных аспектах протокола (а именно, на механизме управления соединением и роли таймеров в этом механизме), будем рассматривать упрощенную версию протокола. Более практические и эффективные расширения протокола могут быть найдены [FW78] и [Tel91b, Раздел 3.2]. В протоколе, описанном здесь, сделаны следующие упрощения.

One direction. Подразумевается, что данные передаются в одном направлении, скажем от p к q. Иногда будем называть p отправителем, а q - адресатом (приемником). Однако, следует отметить, что протокол использует сообщения подтверждения, которые посылаются в обратном направлении, т.е. от q к p.

Обычно данные нужно передавать в двух направлениях. Чтобы предусмотреть подобную ситуацию, дополнительно выполняется второй протокол, в котором p и q поменяны ролями. Тогда можно ввести комбинированные data/ack (данные/подтверждения) сообщения, содержащие как данные (с соответствующим порядковым номером), так и информацию, содержащуюся в пакете подтверждения протокола, основанного на таймере.

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

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

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

Однословные пакеты. Отправитель может помещать только одиночное слово в каждый пакет данных. Протокол был бы более эффективным, если бы пакеты данных могли содержать блоки последовательных слов.

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

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

Ограниченное время жизни пакета. Время жизни пакета ограничено константой  (максимальное время жизни пакета). Òàêèì îáðàçîì, если пакет посылается во время  и принимается во время , то

 <  <  + .

Если пакет дублируется в канале, каждая копия должна быть принята в течение промежутка времени  после отправления оригинала (или стать потерянной).

Таймеры. Процессы не могут наблюдать абсолютное время своих действий, но они имеют доступ к таймерам. Таймер - действительная переменная процесса, чье значение непрерывно уменьшается со временем (если только ей явно не присваивают значение). Точнее, если Xt - таймер, мы обозначаем его значение в момент времени t как Xt(t) и если Xt между t₁ and t₂ не присвоено иное значение, то

Xt^(t1)-Xt^(t2)=t₂-t₁.

Заметим, что эти таймеры работают так: в течение времени  они уменьшаются точно на . В Подразделе 3.2.3 мы обсудим случай, когда таймеры страдают отклонением.

Входные слова для отправителя моделируются, как в Разделе 3.1, неограниченным массивом in_p. Снова этот массив не полностью хранится в p; p в каждый момент времени имеет доступ только к его части. Часть in_p, к которой p имеет доступ расширяется (в сторону увеличения индексов), êîãäà p получает следующее слово от процесса, который их генерирует. Эту операцию будем называть как принятие слова отправителем.

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

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

Нет потерь. Каждое слово inp доставляется процессом q или посылается отчет процессом p ("возможно потеряно" ) в течение ограниченного времени после принятия слова процессом p.

Упорядочение. Слова, доставляемые q принимаются в строго возрастающем порядке (так же, как они появляются в in_p).

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

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

Когда отправитель открывает новое соединение, он начинает нумеровать принятые слова с 0. Количество уже принятых слов в данном соединении обозначается High, и количество слов, для которых уже было получено подтверждение обозначается через Low. Это подразумевает (аналогично протоколу Раздела 3.1), что отправитель может передавать пакеты с порядковыми номерами в диапазоне от Low до High —1, но есть здесь и своя особенность. Отправитель может посылать слово только в течение промежутка времени длиной U, начиная с того момента, когда отправитель принял слово. Для этого с каждым словом in_p[i] ассоциируется таймер Ut[i], он устанавливается в U в момент принятия, и должен быть положительным для передаваемого слова. Òàêèì îáðàçîì, посылаемое окно p состоит из тех слов с индексами Low ...High - 1, для которых ассоциированный с ними таймер положителен.

Сетевые константы:

 : real ; (* Максимальное время жизни пакета *)

Константы протокола:

U : real ; (* Длина интервала отправки *)

R : real ; (* Значение тийм-аута приемника: R U+ *)

S : real ; (* Значение тайм-аута отправителя: S  R + 2 *)

Запись соединения отправителя:

Low : integer ; (* Подтвержденные слова текущего соединения *)

High : integer ; (* Принятые слова текущего соединения *)

St : timer ; (* Таймер соединения *)

Запись соединения приемника:

Exp : integer ; (* Ожидаемый порядковый номер *)

Rt : timer ; (* Таймер соединения *)

Подсистема связи:

Mq : channel ; (* Пакеты данных для q *)

Mp : channel ; (* Пакеты подтверждения для p *)

Вспомогательные переменные:

B : integer init 0 ; (* Слова в предыдущем соединении *)

cr : boolean init false ; (* Существование соединения для приемника *)

cs : boolean init false ; (*Существование соединения для отправителя *)

Ðèñóíîê 3.3 Переменные протокола, основанного на таймере.

Протокол посылает пакеты данных, состоящие из: бита (бит начала-последовательности; его значение будет обсуждаться позже), порядкового номера и слова. Для анализа протокола каждый пакет данных содержит четвертое поле, называемое оставшееся время жизни пакета. Оно показывает максимальное время, в течение которого пакет еще может находиться в канале до того, как он должен быть принят или стать потерянным согласно предположению об ограниченном времени жизни. В момент отправления оставшееся время жизни пакета всегда равно . Пакеты подтверждения протокола состоят только из порядкового номера, ожидаемого процессом q, но опять для целей анализа каждое подтверждение содержит оставшееся время жизни пакета.

Ap: (* Принятие следующего слова *)

begin if not cs then

begin (* Сначала соединение открывается *)

create (St, High, Low) ; (* cs := true *)

Low := High := 0 ; St := S

end;

Ut[B + High] := U, High := High + 1

end

Sp: (* Отправление i-го слова текущего соединения *)

{ cs /\ Low  i < High /\ Ut[B + i] > 0}

begin

send <data, (i = Low),i, in_p[B + i], > ;

St:=S

end

Rp: (* Принятие подтверждения *)

{ cs /\ <ack, i, > Mp }

begin receive <ack, i, > ; Low := max (Low, i) end

Ep: (* Генерация сообщения об ошибке для возможно потерянного слова *)

{cs /\ Ut[B + Low]  -2 -R}

begin error [B + Low] := true ; Low := Low + 1 end

Cp: (* Закрытие соединения *)

{cs /\ St < 0 /\ Low = High }

begin B := B + High , delete (St, High, Low) end

(* cs := false *)

Àëãîðèòì 3.4 Протокол отправителя.

Закрытие соединения контролируется таймерами, таймером St для отправителя и таймером Rt для приемника. Ограниченный интервал посылки каждого слова и ограниченное время жизни пакета приводят к тому, что каждое слово может быть найдено в каналах только лишь в течение интервала времени длиной  + U, начиная с момента принятия слова. Это позволяет приемнику отбрасывать информацию о конкретном слове через  + U единиц времени после принятия слова; после этого не могут появиться дубликаты, следовательно не возможна повторная доставка. Таймер Rt устанавливается в R каждый раз, когда слово доставляется, константа R выбирается так, чтобы удовлетворять неравенству R  U + . Если следующее слово принимается в течение R единиц времени, то таймер Rt обновляется, иначе соединение закрывается. Значение таймера отправители выбирается так, чтобы невозможно было принять подтверждение при закрытом соединении; для этого, соединение поддерживается в течение по крайней мере S единиц времени после отправления пакета, где S - константа, выбираемая так, чтобы удовлетворять S  R+2. Таймер St устанавливается в S каждый раз, когда посылается пакет, и соединение может быть закрыто только если St < 0. Если к этому времени еще остались незавершенные слова (ò.å. слова, для которых не было получено подтверждение), эти слова объявляются потерянными до закрытия соединения.

R_q: (* Принимаем пакет данных *)

{ <data, s, i,w,>  Mq }

begin receive <data, s, i,w,> ;

if cr then

if i = Exp then

begin Rt := R ; Exp := i + 1 ; deliver w end

else if s = true then

begin create (Rt, Exp) ; (* cr := true *)

Rt := R ; Exp := i +1 ; deliver w

end

end

S_q: (* Посылаем подтверждение *)

{cr}

begin send <ack, Exp, > end

(* Закрытие соединения по истечении времени Rt, см. В действии Time *)

Àëãîðèòì 3.5 Протокол приемника

Бит начало-последовательности используется приемником, если пакет получен при закрытом соединении, чтобы решить, может ли быть открыто соединение (и доставлено слово в пакете ). Отправитель устанавливает бит в true, если все предыдущие слова были подтверждены или объявлены (как возможно потерянные). Когда q получает пакет при уже открытом соединении, содержащееся слово доставляется тогда и только тогда, когда порядковый номер пакета равен ожидаемому порядковому номеру (хранится в Exp).

Остается обсудить значение переменной B в протоколе отправителя. Это вспомогательная переменная, введенная только с целью доказательства правильности протокола. Отправитель нумерует слова в каждом соединении, начиная с 0, но, чтобы различать слова в различных соединениях, все слова индексируются последовательно по возрастанию для анализа протокола. Таким образом, там, где отправитель индексирует слово как i, "абсолютный" номер указанного слова B + i, где B - общее количество пакетов, принятых p в предыдущих соединениях. Соответствие между "внутренними" и "абсолютными" номерами слов показывается на Рисунке 3.7. В реализации протокола B не хранится, и отправитель "забывает" все слова in_p [0 .. B-1].

Loss: { m  M } (* M - либо M_p, либо M_q *)

begin remove m from M end

Dupl: { m M } (*M - либо M_p, либо M_q *)

begin insert m in M end

Time: (*  > 0 *)

begin forall i do Ut[i] := Ut[i] - ,

St := St - ; Rt := Rt - ;

if Rt  0 then delete (Rt, Exp) ; (* cr := false *)

forall <.., >  M_p, M_q do

begin  := — ;

if   0 then remove packet

end

end

Àëãîðèòì 3.6 Дополнительные переходы Протокола.

Подсистема связи представляется двумя мультимножествами, M_p для пакетов с адресатом p и M_q для пакетов с адресатом q. Протокол отправителя - Алгоритм 3.4, протокол приемника - Алгоритм 3.5. Имеются дополнительные переходы системы, представленные Алгоритмом 3.6, которые не соответствуют шагам в протоколе процессов. Эти переходы представляют собой отказы канала и изменение времени. В переходах Loss и Dupl M означает или M_p, или M_q. Действие Time уменьшает все таймеры в системе на величину , это случается между двумя дискретными событиями, которые отличаются на  единиц времени. Когда таймер приемника достигает значения 0, соединение закрывается.

Ðèñóíîê 3.7 Порядковые номера протокола.

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

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

P₀  cs  St  S (1)

cr  0 < Rt R (2)

i < B+ High : Ut[i] U (3)

<... > M_p, M_q : 0  (4)

< data, s, i,w, > Mq  cs St +R (5)

cr cs /\ St Rt +  (6)

<ack,i, > M_p cs /\ St> (7)

s, i, w, >M_q  (w = in_p[B + i]/\i < High) (8)

Объяснение к (3): значение High предполагается равным нулю во всех конфигурациях, в которых со стороны приемника нет соединения.

Ëåììà 3.10 P₀ - инвариант протокола, основанного на таймере.

Äîêàçàòåëüñòâî. Первоначально не соединения, нет пакетов, и B = 0, из чего следует, что P₀ - true.

A_p: (1) сохраняется, т.к. St всегда присваивается значения S (St = S). (3) сохраняется, т.к. перед увеличением High, Ut[B + High] присваивается значение U. (5), (6) и (7) сохраняются, т.к. St может только увеличиваться. (8) сохраняется, т.к. High может только увеличиваться.

S_p: (1) сохраняется, т.к. St всегда присваивается значения S. (4) сохраняется, т.к. каждый пакет посылается с оставшимся временем жизни равным . (5) сохраняется, т.к. пакет <..,  посылается и St устанавливается в S, и S = R + 2. (6) и (7) сохраняется, т.к. St может только увеличиться в этом действии. (8) сохраняется, т.к. новый пакет удовлетворяет w = inp[B + i] и i < High.

R_p: Действие Rp не меняет никаких переменных из P₀, и удаление пакета сохраняет (4) и (7).

E_p: Действие Ep не меняет никаких переменных из P₀.

C_p: Действие Cp делает равным false заключения (5), (6) и (7), но ((2), (5), (6) и (7)) применимы только когда их посылки ложны. C_p также меняет значение B, но, т.к. пакетов для передачи нет, (по (5) и (7)), (8) сохраняется.

R_q: (2) сохраняется, т.к. Rt всегда присваивается значение R (если присваивается). (6) сохраняется, т.к. Rt устанавливается только в R только при принятии пакета <data, s,i,w,, è из (4) и (5) следует cs  St R +  когда это происходит.

S_q: (4) сохраняется, т.к. каждый пакет посылается с оставшимся временем жизни, равным . (7) сохраняется, т.к. пакет < ack,i, > посылается с  =  когда cr истинно, так что из (2) и (6) St > .

Loss: (4), (5), (7) и (8) сохраняются, т.к. удаление пакета может фальсифицировать только их посылку.

Dupl: (4), (5), (7) и (8) сохраняются, т.к. ввод пакета m применимо только если m уже был в канале, из чего следует, что заключение данного предложения было истинным и перед введением.

Time: (1), (2) и (3) сохраняются, т.к. St, Rt, и Ut[i] может только уменьшаться, и соединение приемника закрывается, когда Rt становится равным 0. (4) сохраняются, т.к.  может только уменьшиться, и пакет удаляется, когда его -поле достигает значения 0. Заметим, что Time уменьшает все таймеры (включая -поле пакета) на одну и ту же величину, значит сохраняет все утверждения вида Xt > Yt +C, где Xt и Yt -таймеры, и C - константа. Это показывает, что (5), (6) и (7) сохраняются. 

Первое требование к протоколу в том, что каждое слово в конце концов доставляется или объявляется потерянным. Определим предикат 0k(i) как

0k(i)  error [i] = true \/ q доставил inp [i].

Сейчас может быть показано, что протокол не теряет никаких слов, не объявляя об этом. Определим утверждение P₁ как

P₁ P₀

/\ ^cs  i < B: 0k(i) (9)

/\ cs i < B + Low : 0k(i) (10)

/\ <data,true,I,w, M_qi(11)

/\ cr i < B+ Exp : 0k(i) (12)

/\ <ack,I,M_p i<B+I: 0k(i) (13)

Ëåììà 3.11 P₁ - инвариант протокола, основанном на таймере.

Äîêàçàòåëüñòâî. Сначала заметим, что как только 0k(i) стало true для некоторого i, он никогда больше не становится false. Сначала нет соединения, нет пакетов, и B = 0, откуда следует, что P₁ выполняется.

A_p: Действие A_p может открыть соединение, но при этом сохраняется (10), т.к. соединение открывается с Low = 0 и i < B : 0k(i) выполняется из (9).

S_p: Действие S_p может послать пакет < data, s, I, w,  >, но т.к. s истинно только при I = Low, то это сохраняет (11) из (10).

R_p: Значение Low может быть увеличено, если принят пакет < ack, I,  >. Тем не менее, (10) сохраняется, т.к. из (13) i < B + I : 0k(i) выполняется, если получено это подтверждение.

E_p: Значение Low может быть увеличено, когда применяется действие Ep, но генерация сообщения об ошибке гарантирует, что (10) сохраняется.

C_p: Действие C_p обращает cs в false, но оно применимо только если St < 0 и Low == High. Из (10) следует, что i < B+ High : 0k(i) выполняется прежде выполнения C_p, следовательно (9) сохраняется. Посылка (10) обращается в false в этом действии, и из (5), (6) и (7) следует, что посылки (11), (12) и (13) ложны; следовательно (10), (11), (12) и (13) сохраняются.

R_q: Сначала рассмотрим случай, когда q принимает < data, true,l,w, при не существующем соединении (cr - false). Тогда i < B+I : 0k(i) из (11), и w доставляется в действии. Т.к.
w = inp[B+I] из (8), присваивание Exp := I + 1 сохраняет (12).

Теперь рассмотрим случай, когда Exp увеличивается в результате принятия
< data, s,Exp,w, при открытом соединении. Из (12), i < B + Exp : 0k(i) выполнялось перед принятием, и слово w = Wp[B + Exp] доставляется действием, следовательно приращение Exp сохраняет (12).

S_q: Отправление <ack, Exp, > сохраняет (13) из (12).

Loss: Выполнение Loss может только фальсифицировать посылки предложений.

Dupl: Введение пакета m возможно только если посылка соответствующего предложения (и, следовательно, заключение) была истинна еще до введения.

Time: Таймеры не упоминались явно в (9)-(13). Выведение пакета или закрытие процессом q может только фальсифицировать посылки (11), (12) или (13).

Теперь может быть доказана первая часть спецификации протокола, но после дополнительного предположения. Без этого предположения отправитель может быть чрезвычайно ленивым в объявлении слов возможно потерянными; в Àëãîðèòìе 3.4 указано только, что это сообщение может и не возникнуть в промежуток времени 2 + R после окончания интервала для отправления слова, но не указано, что оно вообще должно появиться. Итак, позвольте сделать дополнительное предположение, что действие Ep на самом выполниться процессом p и в течение разумного времени, а именно прежде, чем Ut[B + Low] = —2 —R—.

Òåîðåìà 3.12 (Нет потерь) Каждое слово in_p доставляется q или объявляется p как возможно потерянное в течение U+2+R+ после принятия слова процессом p.

Äîêàçàòåëüñòâî. После принятия слова in_p[I], B+High > I начинает выполняться. Если соединение закрывается в течение указанного периода после принятия слова in_p[I], то B > I, и результат следует из (9). Если соединение не закрывается в этот промежуток времени и B + Low  I, отчет обо всех словах из промежутка B + Low..I возможен ко времени 2 + R после окончания интервала отправления inp[I]. Из этого следует, что этот отчет имел место 2 + R + после окончания интервала отправления, ò.å., U+ 2 +R+ после принятия. Из этого также следует I < B+ Low, и, значит, слово было доставлено или объявлено (из (10)). 

Чтобы установить второе требование корректности протокола, должно быть показано, что каждое принимаемое слово имеет больший индекс (в in_p), чем ранее принятое слово. Обозначим индекс самого последнего доставленного слова через pr (для удобства запишем, что изначально
pr =-1 and Ut[-1] = - ). Определим утверждение P₂ как:

P₂ P₁

/\ <data,s,i,w,>  M_q  Ut[B+i] > - (14)

/\ i1  i2 < B + High  Ut[i₁]  Ut[i₂] (15)

/\ cr  Rt  Ut[pr] +  (16)

/\ pr < B + High /\ ( Ut[pr] > -  cr) (17)

/\ cr  B + Exp = pr + 1 (18)

Ëåììà 3.13 P₂ - инвариант протокола, основанного на таймере.

Äîêàçàòåëüñòâî. Изначально M_q пусто, B + High равно нулю, ^cr выполняется, и
Ut[pr] < -, откуда следуют (14)-(18).

A_p: (15) сохраняется, т.к. каждое новое принятое слово получает значение таймера U, что из (3) по крайней мере равно значениям таймеров ранее принятых слов.

S_p: (14) сохраняется, т.к. Ut[B +i] > 0 и пакет отправляется с  .

C_p: (14), (16) и (18) сохраняются, т.к. из (5) è (6) их посылки ложны, когда Cp применимо. (15) сохраняется, т.к. B принимает значение B + High è таймеры не меняются. (17) сохраняется, т.к. B присваивается значение B + High è pr è cr не меняются.

R_q: (16) сохраняется, т.к. когда Rt устанавливается в R (при принятии слова) Ut[pr]  U из (3), è R 2+U. (17) сохраняется, т.к. pr < B+High, что следует из (8), è cr становится true. (18) сохраняется, т.к. Exp устанавливается в i +1 è pr в B + i, откуда следует, что (18) становится true.

Time: (14) сохраняется, т.к. Ut[B + i] è  уменьшаются на одно и то же число (è выведение пакета только делает ложной посылку). (15) сохраняется, т.к. Ut[i₁] è Ut[i₂] уменьшаются на одну и туже величину. (16) сохраняется, т.к. cr не становится истинным в этом действии, è Rt è Ut[pr] уменьшаются на одну и ту же величину. (17) сохраняется, т.к. его заключение становится ложным только, если Rt становится  0, откуда следует (по (16)), что Ut[pr] становится < -. (18) сохраняется, т.к., если cr не обратился в false, B, Exp è pr не меняются.

Действия R_p, E_p, è S_q, не меняют никакие переменные в (14)-(18). Loss è Dupl сохраняют (14)-(18) исходя из тех же соображений, что и в предыдущих доказательствах. 

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

< data, s,i₁,w,  M_q  (cr \/ B+i₁ > pr).

Äîêàçàòåëüñòâî. По (14), из <data,s,i₁,w,>  M_q следует Ut[B+i₁] >- > -.

Если B +i₁  pr то, т.к. pr < B + High из (15), Ut[pr] > -, так что из (17) cr true. 

Òåîðåìà 3.15 (Упорядочение) Слова, доставляемые q появляются в строго возрастающем порядке в массиве in_p.

Äîêàçàòåëüñòâî. Предположим q получает пакет <data, s,i₁,w, > è доставляет w. Если перед получением не было соединения, B + i₁ > pr (по Ëåììе 3.14), так что слова w располагается в in_p после позиции pr. Если соединение было, i₁ = Exp, значит B+i₁ = B+Exp = pr+1 из (18), откуда следует, что w = in_p[pr+1]. 

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

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

Качество протокола. Требования Нет потерь è Упорядочение являются свойствами безопасности, è они позволяют получить чрезвычайно простое решение, а именно протокол, который не посылает или получает никакие пакеты, и объявляет каждое слово потерянным. Само собой разумеется, что такой протокол, который не дает никакой транспортировки данных от отправителя к приемнику, не является очень "хорошим" решением.

Хорошие решения проблемы не только удовлетворяют требованиям Нет потерь и Упорядочение, но также объявляют потерянными как можно меньше слов. Для этой цели, протокол этого раздела может быть расширен механизмом, который посылает каждое слово неоднократно (пока не конец посылки интервала), пока не получит подтверждение. Интервал посылки должен быть достаточно длинным, чтобы можно было повторить передачу некоторого слова несколько раз, и чтобы вероятность, что слово потеряется, стала очень маленькой.

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

Ограниченные порядковые номера. Порядковые номера, используемые в протоколе, могут быть ограничены, если получить для протокола результат, аналогичный Ëåììе 3.9 для сбалансированного протокола скользящего окна [Tel91b, Section 3.2]. Для этого нужно предположить, что скорость принятия слов (процессом p) ограничена следующим образом: слово может быть принято только если первое из предыдущих слов имеет возраст по крайней мере U + 2+ R единиц времени. Для этого нужно к действию A_p добавить сторож

{(High < L) V ( Ut[B + High - L] <-R -2)}.

Учитывая это предположение, можно показать, что порядковые номера принимаемых пакетов лежат в 2L-окрестности вокруг Exp, è порядковые номера подтверждений - в L-окрестности вокруг High. Следовательно, можно передавать порядковые номера modulo 2L.

Форма действий и инвариант. Благодаря использованию утверждений, рассуждения относительно протокола связи уменьшены до (большого) манипулирования формулами. Манипулирование формулами - "безопасная" методика потому, что каждый шаг может быть проверен в очень подробно, так что возможность сделать ошибку в рассуждениях мала. Но есть риск, что читатель может потеряет идею протокола и его отношение к рассматриваемым формулам. Проблемы проектирования протокола могут быть поняты и с прагматической, и с формальной точки зрения. Fletcher и Watson [FW78] утверждают, что упрафляющая информация должна быть "защищена" в том смысле, что ее значение не должно измененяться потерей или дублированием пакетов; это - прагматическая точка зрения. При использовании в проверке утверждений, "значение" информации управления отражено в выборе специфических утверждений в качестве инвариантов. Выбор этих инвариантов и проектирование переходов, сохраняющих их, составляет формальную точку зрения. Действительно, как будет показано, наблюдение Fletcher и Watson может быть вновь показано в терминах "формы" формул, которые могут или не могут быть выбран как инварианты протокола, устойчивые к потере и дублированию пакетов.

Time-: {  > 0}

begin (* Таймеры в p уменьшаются на  ' *)

 ' := ... ; (*   '    (1 + ) *)

forall i do Ut[i] := Ut[i] -  ' ;

St := St -  ' ;

(*Таймеры в q уменьшаются на  ' *)

":=...; (*   ''    (1 + ) *)

Rt := Rt -  " ;

if Rt < 0 then delete (Rt, Exp) ;

(*  -поле передается явно *)

forall (..,)  M_p, M_q do

begin  :=  - ,

if  < 0 then remove packet

end

end

Àëãîðèòì 3.8 Измененное действие Time.

Все инвариантные предложения P₂ относительно пакетов имеют форму

m  M : A(m)

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

èëè

условие  m  M : A(m).

Утверждения, имеющие этй форму могут быть фальсифицированы потерей или дублированием пакетов, è следовательно не могут использоваться в дîêàçàòåëüñòâе корректности Àëãîðèòìов, которые должны допускать подобные дефекты.

Подобные же наблюдения применимы к форме инвариантов в действии Time. Уже было отмечено, что это действие сохраняет все утверждения формы Xt  Yt + C,

где Xt è Yt -таймеры è C -константа.

P₁ = cs  St S (1)

/\ cr  0 < Rt  R (2')

/\ i < B + High : Ut[i] < U (3')

/\  <..,  >  M_p, M_q : 0 <   (4')

/\ <data, s, i, w,  > M,  cs /\ St  (1+)(+ +(1+)R) (5')

/\ cr cs /\ St  (l+)((i+)Rt+) (6')

/\ < ack, i,  >  M_p  cs /\ St > (1 + ) (7')

/\ <data, s, i, w,  > M_q,  (w = in_p[B + i] /\ i < High) (8')

/\ ^cs  \/i < B: 0k(i) (9')

/\ cs  \/i < B + Low : 0k(i) (10')

/\<data,true,I,w, ) M_qi (11')

/\ cr  i < B + Exp : 0k(i) (12')

/\ <ack,I,  > M_pi <B+I: Ok(i) (13')

/\ <data, s, i, w, ) M_q  Ut[B+i] > (l+)(  -) (14')

/\ i₁ i₂ < B + High  Ut[i₁] < Ut[i₂] (15')

/\ cr  Rt  (1 + )((l + ) Ut[pr] + (1 + )² ) (16')

/\ pr < B + High /\ Ut[pr] >-(1+) cr (17')

/\ cr  B + Exp = pr+1 (18')

Ðèñóíîê 3.9 инвариант протокола с отклонением таймеров.

Неаккуратные таймеры. Действие Time моделирует идеальные таймеры, которые уменьшаются точно на  в течение  единиц времени, на на практике таймеры страдают неточности, называемой отклонением. Это отклонение всегда предполагается -ограниченным, ãäå -известная константа, что означает, что в течение  единиц времени таймер уменьшается на величину  ', которая удовлетворяет  /(l + )  '    (1 + ). (Обычно  бывает порядка 10^-5 или 10^-6.) Такое поведение таймеров моделируется действием Time-, приведенном в Àëãîðèòìе 3.8.

Было замечено, что Time сохраняет утверждения специальной формы Xt  Yt + C потому, что таймеры обеих частей неравенства уменьшаются на в точности одинаковую величину, è из
Xt  Yt + C следует (Xt - )  ( Yt - ) + C. Такое жн наблюдение может быть сделано для Time-. Для действительных чисел Xt, Yt, ,  ', ", r, è c, удовлетворяющих  > 0 è r > 1, из

(Xt  r² Yt + c) /\ (   '   r) /\ (   ''   r)

следует

(Xt- ') r²(Yt- ") + c.

Следовательно, Time- сохраняет утверждение формы

Xt  (1 + )² Yt + c.

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

R  (1 + )((1 + )U + (I + )²) è S  (1 + )(2 + (1 + )R).

Исключая измененные константы, протокол остается таким же. Его инвариант приведен на Ðèñóíêе 3.9.

Òåîðåìà 3.16 P₂'- инвариант протокола, основанного на таймере с -ограниченным отклонением таймера. Протокол удовлетворяет требованиям Нет потерь и Упорядочение.

Упражнения к главе 3

Раздел 3.1

Óïðàæíåíèå 3.1 Покажите, что сбалансированный протокол скользящего окна не удовлетворяет требованию окончательной доставки, если из предположений Fl è FS, выполняется только F2.

Óïðàæíåíèå 3.2 Докажите, что если L = 1 в сбалансированном протоколе скользящего окна è a_p è a_q, инициализируются значениями -l_q è -l_p, то всегда верно a_p+l_q = s_p è a_q+l_p = s_q.

Раздел 3.2

Óïðàæíåíèå 3.3 В протоколе, основанном на таймере отправитель может объявить слово возможно потерянным, когда на самом деле оно было корректно доставлено приемником.

(1) Опишите выполнение протокола, при котором возникает этот феномен.

(2)Можно ли спроектировать протокол, в котором отправитель генерирует сообщение об ошибке в течение ограниченного промежутка времени, тогда и только тогда, когда слово не доставлено приемником?

Óïðàæíåíèå 3.4 Предположим, что из-за выхода из строя часового устройства, приемник не может закрыть соединение вовремя. Опишите работу протокола, основанного на таймере, когда слово теряется без сообщений отправителя.

Óïðàæíåíèå 3.5 Опишите работу протокола, основанного на таймере, в котором приемник открывает соелинение при принятии пакета с порядковым номером, большим нуля.

Óïðàæíåíèå 3.6 Действие Time- не моделирует отклонение в оставшемся времени жизни пакетов. Почему?

Óïðàæíåíèå 3.7 Докажите Теорему 3.16.

Óïðàæíåíèå 3.8 Инженер сети хочет использовать протокол, основанный на таймере, но хочет, чтобы отчет о возможно потерянных словах приходил раньше, в соответствии со следующей модификацией E_p.

E_p: (* Генерация сообщения об ошибке для возможно потерянных слов *)

{ Ut[B + Low] < 0 }

begin error[B + Low] := true ; Low := Low + 1 end

Продолжает ли тàêèì îáðàçîì измененный протокол удовлетворять требованиям Нет потерь и Упорядочение или должны быть сделаны какие-то изменения? Укажите преимущества и недостатки этих изменений.

4 Алгоритмы маршрутизации

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

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

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

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

Критерии для "хороших" методов маршрутизации включают следующие.

(1) Корректность. Алгоритм должен доставить каждый пакет, предложенный сети окончательному адресату.

(2) Комплексность. Алгоритм для вычисления таблиц должен использовать несколько сообщений, время, и память (хранение) насколько возможно.

(3) Эффективность. Алгоритм должен послать пакеты через "хорошие" пути, например, пути, которые доставляют только маленькую задержку и гарантируют высокую производительность всей сети. Алгоритм называется оптимальным, если он использует "самые лучшие" пути.

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

(4) Живучесть. В случае топологического изменения (добавление или удаление канала или узла) алгоритм модифицирует таблицы маршрутизации для выполнения функции маршрутизации в изменяемой сети.

(5) Адаптивность. Алгоритм балансирует загрузку каналов и узлов, адаптируя таблицы, чтобы избежать маршрутов через каналы или узлы, которые перегружены, предпочитая каналы, и узлы с меньшей загруженностью в настоящее время .

(6) Справедливость. Алгоритм должен обеспечить обслуживание каждому пользователю в равной мере.

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

Как обычно, сеть представляется как граф, где узлы графа - узлы сети, и существует ребро между двумя узлами, если они - соседи (то есть, они имеют канал связи между ними). Оптимальность алгоритма зависит от того, что называется "самым лучшим" путем в графе; существует, несколько понятий "самый лучший", каждый с собственным классом алгоритмов маршрутизации:

(1)Минимальное количество переходов. Стоимость использования пути измеряется как число переходов (пройденные каналы или шаги от узла до узла) пути. Минимальный переход, направляющий алгоритм, использует путь с самым маленьким возможным числом переходов.

(2)Самый короткий путь. Каждый канал статически назначен (неотрицательным) весом, и стоимость пути измеряется как сумма весов каналов в пути. Алгоритм с самой короткой дорожкой использует путь с самой низкой возможной стоимостью.

(3)Минимальная задержка. Каждый канал динамически означивается весом, в зависимости от трафика в канале. Алгоритм с минимальной задержкой неоднократно перестраивает таблицы таким способом, при котором пути с (близкой) минимальной общей задержкой выбираются всегда.

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

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

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

Алгоритм изменяемой сети, обсужденный в Разделе 4.3, не страдает из этого недостатка: он может адаптироваться к потере или восстановлению каналов частичным перевычислением таблиц маршрутизации. Чтобы анализ был простым, он реализован как минимальный переход, то есть число шагов принимается как стоимость пути. Возможно " изменить Netchange алгоритм, для работы с взвешенными каналами, которые могут теряться или восстанавливаться.

Алгоритмы маршрутизации Разделов 4.2 и 4.3 используют таблицы маршрутизации (в каждом узле) с записями для каждого возможного адресата. Это может слишком отяготить больших сетей из маленьких узлов. В Разделе 4.4 будут обсуждены некоторые стратегии маршрутизации, которые кодируют топологическую информацию в адресе узла, чтобы использовать более короткие таблицы маршрутизации или меньшее количество таблиц. Эти так называемые "компактные" алгоритмы маршрутизации обычно не используют оптимальные пути. Схема основой - деревом, интервальная маршрутизация, и префиксная маршрутизация также будет обсуждена.

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

4.1 Адресат-основанная маршрутизация

Решение маршрутизации, сделанное, когда пересылается пакет обычно основано только на адресате пакета (и содержании таблиц маршрутизации), и не зависит от первоначального отправителя (источника) пакета. Маршрутизация может игнорировать источник и использовать оптимальные пути, таковы выводы этого раздела. Выводы не зависят от выбора частного критерия оптимальности для путей. (Положим, что путь прост, если он содержит каждый узел только один раз, и путь - цикл, если первый узел равняется последнему узлу.)

(1)Стоимость посылки пакета через путь P не зависит от фактического использования пути, в частности использование ребер P в соответствии с другими сообщениями. Это предположение позволяет нам оценивать стоимость использования пути P как функцию пути; таким образом, обозначим стоимость P как C(P) ..

(2) Стоимость конкатенации двух путей равняется сумме стоимостей составных путей, то есть, для всякого i= 0,..., k
C(o,u1,...,uk>)=C(o,...,ui>)+C(i,...,uk>).
Следовательно, стоимости пустого пути <u0>(это - путь от u0 до u0) удовлетворяет C(0>) = 0.

(3)Граф не содержит циклов отрицательной стоимости.

( Этот критерий удовлетворяется критерием самого короткого пути и критерием минимального перехода). Путь от u до v, называется оптимальным, если не существует никакой путь от u до v с более низкой стоимостью. Заметьте, что оптимальный путь не всегда единственен; могут существовать различные пути с той же самой (минимальной) стоимостью.

Лемма 4.1. Пусть u, v V. Если путь из u в v существует в G, тогда и существует простой путь, который оптимален.

Доказательство. Так как количество простых путей конечное число, то существует простой путь от u до v, назовем его So, с наименьшей стоимостью, т.е., для каждого простого пути P' из u в v C(So)C(P’). Осталось показать что C(So) нижняя граница стоимостей всех (не простого) путей

Запишем V = {v1, ..., vn}. Следовательно, удаляя из P циклов, включающие v1, v1, v2 и т.д., покажем что для каждого пути P из u в v существует простой путь P' с C(P') C(P). Положим Po =P, и построим для i = 1,..., N путь Pi следующим образом. Если vi входит в Pi-1 тогда Pi = Pi-1. Иначе, запишем Pi-1 = <uo, ...,uk>. Пусть uj1 будет первым и uj2 будет последним вхождением vi в Pi-1 и положим

Pi = o, . . . , uj1(=uj2), uj2+1, . . .,uk>

по построению Pi - путь из u к v и содержит все вершины из {v1, ..., vn} только единожды, следовательно PN -простой путь из u в v. Pi-1 состоит из Pi и цикла Q= uo, . . . , uj2 следовательно C(Pi-1) = C(Pi) + C(Q). Так как не существует циклов отрицательного веса, это предполагает C(Pi)  C(Pi-1) и, следовательно, C(PN ) C(P).

По выбору So, C(So)  C(PN,), из которого следует C(So)  C(P) []

Если G содержит циклы отрицательного веса, оптимальный путь не обязательно существует; каждый путь может быть «побежден» другим путем, который пройдет через отрицательный цикл еще раз. Для следующей теоремы, примите, что G связный (для несвязных графов, теорема может применяться к каждому связному компоненту отдельно).

Теорема4.2. Для каждого d  V существует Td = (V, Ed) такое что Ed  E и такое что для каждой вершины v  V, путь из v к d в Td - оптимальный путь от v к d в G.

Доказательство. Пусть V = { v1, ..., vN }. Мы индуктивно построим последовательность деревьев Ti = (Vi, Ei) (для i = 0, ...,N) со следующими свойствами

(1) Каждое Ti - поддерево G, т.е., Vi  V, Ei  E, и Ti - дерево.

(2) Каждое Ti (для i < N) поддерево Ti+1.

(3) Для всех i > 0, vi  Vi и d  Vi.

(4) Для всех wVi, простой путь от w к d в T, - оптимальный путь от w к d в G.

Эти свойства подразумевают, что TN соответствует требованиям для Td.

Конструируя последовательность деревьев, положим Vd = {d} и Eo =  . Дерево Ti+1 построим следующим образом. Выберем оптимальный простой путь P=<uo, . . ., uk> от vi+1 к d, и пусть l будет наименьшим индексом таким, что ul  Ti (такое l существует, потому что ul = d  Ti ; возможно l = 0). Теперь:

Vi = Vi { uj: j } и Ei+1 = Ei  {( uj, uj+1) : j < 1}.

(Построение иллюстративно представлено на Рисунке 4.1.) Нетрудно видеть что Ti поддерево Ti+1 и что vi+1  Vi+1. Чтобы увидеть что Ti+1 дерево, заметим что по построению Ti+1 связный, и число вершин превосходит число ребер на одно. (T_o имеет последнее свойство, на каждом шаге много вершин и ребер добавлено)

Рисунок 4.1 Построение T_i+1.

Осталось показать, что для всех w  Vi+1 , (уникальный) путь от w к d в Ti+1 - оптимальный путь от w к d в G. Для вершин w  Vi  Vi+1 это следует, потому что Ti поддерево Ti+1 ; путь от w к d в Ti+1 точно такой же, как путь в Ti, который оптимален. Теперь пусть w = uj, j < l будет вершиной в Vi+1 \V,. Запишем Q для пути от ui к d в Ti, тогда в Ti+1 uj соединена с d через путь <uj, . . . , ul> соединенный с Q, и осталось показать, что этот путь оптимальный в G. Во-первых, суффикс P' = <ul, . . . , uk> в P оптимальный путь от ul до d, т.е., C(P') = C(Q): оптимальность Q подразумевает что C(P') C(Q), и C(Q)< C(P') подразумевает (добавлением стоимости пути) что путь <uo, . . . , ul> соединен с Q имеющий меньший путь, чем P, противоречащий оптимальности P. Теперь положим, что R из uj к d имеет меньшую стоимость, чем путь <uj, . . . , ul> соединенный с Q. Тогда, по предыдущим наблюдениям, R имеет меньшую стоимость, чем суффикс <uj, . . . , uk> P, и это предполагает что путь <uo, . . . , uj> соединенный с R имеет меньшую стоимость, чем P, противоречащий оптимальности P. 

Дерево охвата, приложенное к d , называется деревом стока для d, и дерево со свойством, данным в Теореме 4.2 , называется оптимальным деревом стока. Существование оптимальных деревьев стока не является компромиссом оптимальности, если только алгоритмы маршрутизации рассматриваются, для которого механизм пересылки, как в Алгоритме 4.2. В этом алгоритме, table_lookupu локальная процедура с одним параметром, возвращая соседа u (после консультации с таблицами маршрутизации). Действительно, поскольку все пакеты для адресата d могут быть направлены оптимально используя дерево обхвата, приложенное к d, пересылка оптимальна, если, для всего ud, table_lookupu(d) возвращает отца u в дереве охвата Td.

Когда механизм пересылки имеет эту форму, и никакие (дальнейшие) изменения топологии не происходят, корректность таблиц маршрутизации может быть удостоверена, используя следующий результат. Таблицы маршрутизации, как говорят, содержат цикл (для адресата d), если существуют узлы u1, . . . , uk такие, что для всех i , ui d, для всех i < k, table_lookupu(d) = ui+1, и table_lookupu(d) = uj+1.. Таблицы, как говорят, являются свободным от циклов, если они не содержат циклов для любого d.

(* Пакет с адресатом d был получен или сгенерирован в узле u *)

if d=u

then доставить «местный» пакет

else послать пакет к table_lookupu (d)

А лгоритм 4.2 Адресат-основанная пересылка (для узла u).

Лемма 4.3 Механизм пересылки доставляет каждый пакет адресату, тогда и только тогда когда таблицы маршрутизации цикл-свободны.

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

Примем, что таблицы цикл-свободны и позволяют пакету с адресатом d (и источник uo) быть посланным через uo, u1, u2, . .. если один встречается дважды в этой последовательности, скажем ui = uj, тогда таблицы содержат цикл, а именно < ui ..., uj> противореча предположению, что таблицы являются цикл-свободными. Таким образом, каждый узел входит единожды, что подразумевает, что эта последовательность конечна, заканчивающаяся, скажем, в узле Великобританию uk (k < N). Согласно процедуре пересылки последовательность может заканчиваться только в d , то есть, uk = d, и пакет достиг адресата за не больше чем N — 1 шагов 

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

Ветвящаяся маршрутизация с минимальной задержкой. При маршрутизации через пути с минимальной задержкой требуется, и задержка канала зависит от использования (таким образом, предположение (1) в начале этого раздела не имеет силу), стоимость использования пути не может просто быть оценена как функция этого единственного пути. Кроме того, трафик на канал должен быть принят во внимание. Избегать скопления пакетов (и возникающую в результате этого задержку) на пути, обычно необходимо посылать пакеты, имеющие ту же самую пару исходный-адресат через различные пути; трафик для этой пары "распределяется" в один или большее количество узлов промежуточного звена как изображено в Рисунке 4.3. Методы маршрутизации, которые используют различные пути к одному адресату, называются много-путевыми или ветвящимися методами маршрутизации. Потому что ветвящиеся методы маршрутизация являются, обычно, очень запутанными, они не будет рассматриваться в этой главе

Рисунок 4.3 Пример буферизованной маршрутизации.

4.2 Проблема кротчайших путей всех пар

Этот раздел обсуждает алгоритм Toueg [Tou80a] одновременного вычисления таблицы маршрутизации для всех узлов в сети. Алгоритм вычисляет для каждой пары (u, v) узлов длину самый короткий пути от u до v и сохраняет первый канал такого пути в u. Проблема вычисления самого короткого пути между любыми двумя узлами графа известна как проблема кротчайшего пути всех пар. Распределенный алгоритм Toueg для этой проблемы основан на централизованном алгоритме Флойда-Уошалла [CLR90, Раздел 26.4]. Мы обсудим алгоритм Флойда-Уошалла в Подразделе 4.2.1, и впоследствии алгоритм Toueg в Подразделе 4.2.2. Краткое обсуждение некоторых других алгоритмов для проблемы кротчайших путей всех пар следует в Подразделе 4.2.3 ..

4.2.1 Алгоритм Флойда-Уошала

Пусть дан взвешенный граф G = (V, E) , где вес ребра uv дан wuv . Не обязательно допускать что wuv= wvu , но допустим, что граф не содержит циклов с общим отрицательным весом. Вес пути < uo, ..., uk> определяется как . Дистанция от u до v, обозначенная d(u, v), наименьший вес любого пути от u к v ( если нет такого пути). Проблема кротчайших путей всех пар - вычисление d(u, v) для каждых u и v.

Для вычисления всех расстояний, алгоритм Флойда-Уошала использует понятие S-путей; это пути, в которых все промежуточные вершины принадлежат к подмножеству S из V.

Определение 4.4. Пусть S - подмножество V. Путь < uo ..., uk> -S-путь если для любого i, 0 j  S. S-расстояние от u до v, обозначенное d^S(u. v), наименьший вес любого S-пути от u до v ( если такого пути нет).

Алгоритм стартует рассмотрением всех -путей, и увеличивая вычисления S-путей для больших подмножеств S, до тех пор пока V-пути будут рассмотрены. Могут быть сделаны следующие наблюдения.

Утверждение 4.5 Для всех u и S, d^S(u, u) = 0. Более того, S-пути удовлетворяют следующим правилам для u v.

(1) Существует  -путь от u к v тогда и только тогда когда uv E.

(2) Если uv  E тогда d^S(u, v) = w_uv иначе d^S(u, v) = .

(3) Если S'=S {w} тогда простой S'-путь от и к v - S-путь от u к v или S-путь от u к w соединенные S-путем от w к v.

Характеристики

Список файлов реферата