Предыдущая страница реферата | 18  19  20  21  22  23  24  25  26  27  28 | Следующая страница реферата

Rq: (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[i1] и Ut[i2] уменьшаются на одну и туже величину. (16) сохраняется, т.к. cr не становится истинным в этом действии, и Rt и Ut[pr] уменьшаются на одну и ту же величину. (17) сохраняется, т.к. его заключение становится ложным только, если Rt становится ( 0, откуда следует (по (16)), что Ut[pr] становится < -(.

(18) сохраняется, т.к., если cr не обратился в false, B, Exp и pr не меняются.

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

Лемма 3.14 Из P2 следует, что
< data, s,i1,w,(> ( Mq ( (cr / B+i1 > pr).
Доказательство. По (14), из ( Mq следует Ut[B+i1] >( -( >
-(.
Если B +i1 ( pr то, т.к. pr < B + High из (15), Ut[pr] > -(, так что из
(17) cr true. (

Теорема 3.15 (Упорядочение) Слова, доставляемые q появляются в строго возрастающем порядке в массиве inp.
Доказательство. Предположим q получает пакет и доставляет w. Если перед получением не было соединения, B + i1 > pr (по Лемме 3.14), так что слова w располагается в inp после позиции pr. Если соединение было, i1 = Exp, значит B+i1 = B+Exp = pr+1 из (18), откуда следует, что w = inp[pr+1]. (

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

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

Ограниченные порядковые номера. Порядковые номера, используемые в протоколе, могут быть ограничены, если получить для протокола результат, аналогичный Лемме 3.9 для сбалансированного протокола скользящего окна
[Tel91b, Section 3.2]. Для этого нужно предположить, что скорость принятия слов (процессом p) ограничена следующим образом: слово может быть принято только если первое из предыдущих слов имеет возраст по крайней мере U + 2(+
R единиц времени. Для этого нужно к действию Ap добавить сторож
{(High < L) V ( Ut[B + High - L] 0} begin (* Таймеры в p уменьшаются на ( ' *)
( ' := ... ; (* [pic]( ( ' ( ( ( (1 + () *) forall i do Ut[i] := Ut[i] - ( ' ;
St := St - ( ' ;
(*Таймеры в q уменьшаются на ( ' *)
(":=...; (* [pic]( ( '' ( ( ( (1 + () *)
Rt := Rt - ( " ; if Rt < 0 then delete (Rt, Exp) ;
(* ( -поле передается явно *) forall (..,() ( Mp, Mq do begin ( := ( - (, if ( < 0 then remove packet end end
Алгоритм 3.8 Измененное действие Time.

Все инвариантные предложения P2 относительно пакетов имеют форму
(m ( M : A(m) и в самом деле легко видеть, что подобное предложение сохраняется при дублировании и потере пакетов. В дальнейших главах мы увидим инварианты в более общей форме, например
[pic] или условие ( (m ( M : A(m).
Утверждения, имеющие этй форму могут быть фальсифицированы потерей или дублированием пакетов, и следовательно не могут использоваться в доказательстве корректности Алгоритмов, которые должны допускать подобные дефекты.
Подобные же наблюдения применимы к форме инвариантов в действии Time. Уже было отмечено, что это действие сохраняет все утверждения формы Xt ( Yt +
C, где Xt и Yt -таймеры и C -константа.
P1( = cs ( St( S
(1()
/ cr ( 0 < Rt ( R
(2')
/ (i < B + High : Ut[i] < U
(3')
/ ( ( Mp, Mq : 0 < ( (( (4')
/ ( M, ( cs / St ( (1+()((+ (+(1+()R) (5')
/ cr( cs / St ( (l+()((i+()Rt+() (6')
/ ( Mp ( cs / St > (1 + ()(( (7')
/ (Mq, ( (w = inp[B + i] / i < High) (8')
/ (cs ( /i < B: 0k(i)
(9')
/ cs ( /i < B + Low : 0k(i) (10')
/ 1, из
(Xt ( r2 Yt + c) / ([pic] ( ( '( ( ( r) / ([pic] ( ( ''( ( ( r) следует
(Xt-( ')( r2(Yt- (") + c.
Следовательно, Time-( сохраняет утверждение формы
Xt ( (1 + ()2 Yt + c.
Теперь протокол может быть адаптирован к работе с отклоняющимися таймерами, если соответствующим образом изменить инварианты. Для того, чтобы другие действия тоже сохраняли измененные инварианты, константы R и S протокола должны удовлетворять
R ( (1 + ()((1 + ()U + (I + ()2) и S ( (1 + ()(2( + (1 + ()R).
Исключая измененные константы, протокол остается таким же. Его инвариант приведен на Рисунке 3.9.
Теорема 3.16 P2'- инвариант протокола, основанного на таймере с (- ограниченным отклонением таймера. Протокол удовлетворяет требованиям Нет потерь и Упорядочение.

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

Раздел 3.1

Упражнение 3.1 Покажите, что сбалансированный протокол скользящего окна не удовлетворяет требованию окончательной доставки, если из предположений Fl и
FS, выполняется только F2.
Упражнение 3.2 Докажите, что если L = 1 в сбалансированном протоколе скользящего окна и ap и aq, инициализируются значениями -lq и -lp, то всегда верно ap+lq = sp и aq+lp = sq.

Раздел 3.2

Упражнение 3.3 В протоколе, основанном на таймере отправитель может объявить слово возможно потерянным, когда на самом деле оно было корректно доставлено приемником.
(1) Опишите выполнение протокола, при котором возникает этот феномен.
(2)Можно ли спроектировать протокол, в котором отправитель генерирует сообщение об ошибке в течение ограниченного промежутка времени, тогда и только тогда, когда слово не доставлено приемником?
Упражнение 3.4 Предположим, что из-за выхода из строя часового устройства, приемник не может закрыть соединение вовремя. Опишите работу протокола, основанного на таймере, когда слово теряется без сообщений отправителя.
Упражнение 3.5 Опишите работу протокола, основанного на таймере, в котором приемник открывает соелинение при принятии пакета с порядковым номером, большим нуля.
Упражнение 3.6 Действие Time-( не моделирует отклонение в оставшемся времени жизни пакетов. Почему?

Упражнение 3.7 Докажите Теорему 3.16.

Упражнение 3.8 Инженер сети хочет использовать протокол, основанный на таймере, но хочет, чтобы отчет о возможно потерянных словах приходил раньше, в соответствии со следующей модификацией Ep.
Ep: (* Генерация сообщения об ошибке для возможно потерянных слов *)
{ 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()=C()+C().

Следовательно, стоимости пустого пути (это - путь от u0 до u0) удовлетворяет C() = 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 = . Пусть uj1 будет первым и uj2 будет последним вхождением vi в Pi-1 и положим

Pi = по построению 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= от vi+1 к d, и пусть l будет наименьшим индексом таким, что ul (
Ti (такое l существует, потому что ul = d ( Ti ; возможно l = 0). Теперь:

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

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

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

[pic]
Рисунок 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> определяется как [pic] . Дистанция от u до v, обозначенная d(u, v), наименьший вес любого пути от u к v (( если нет такого пути). Проблема кротчайших путей всех пар - вычисление d(u, v) для каждых u и v.
Для вычисления всех расстояний, алгоритм Флойда-Уошала использует понятие
S-путей; это пути, в которых все промежуточные вершины принадлежат к подмножеству S из V.

Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини.



Предыдущая страница реферата | 18  19  20  21  22  23  24  25  26  27  28 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки