Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 32
Текст из файла (страница 32)
. , i ∈ Mp , Mq : 0 < 6hdata, s, i, w, i ∈ Mq =⇒ cs ∧ St > (1 + ) ( + + (1 + )R)cr =⇒ cs ∧ St > (1 + ) ((1 + )Rt + )hack, i, i ∈ Mp =⇒ cs ∧ St > (1 + ) ×hdata, s, i, w, i ∈ Mq =⇒ (w = inp [B + i] ∧ i < High)¬cs =⇒ ∀ i < B : Ok(i)cs =⇒ ∀ i < B + Low : Ok(i)hdata, true, I, w, i ∈ Mq =⇒ ∀ i < B + I : Ok(i)cr =⇒ ∀ i < B + Exp : Ok(i)hack, I, i ∈ Mp =⇒ ∀ i < B + I : Ok(i)hdata, s, i, w, i ∈ Mq =⇒ Ut [B + i] > (1 + ) ( − )i1 6 i2 < B + High =⇒ Ut [i1 ] 6 Ut [i2 ]cr =⇒ Rt > (1 + ) ((1 + )Ut [pr] + (1 + ) 2 )pr < B + High ∧ Ut [pr] > − (1 + ) =⇒ crcr =⇒ B + Exp = pr + 1 ∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧≡P20114(1 )(20)(30)(40)(50)(60)(70)(80)(90)(100)(110)(120)(130)(140)(150)(160)(170)(180)0Рис. 3.9.
Инвариант протокола с расходящимися таймерами.Теорема 3.16. Формула P20 является инвариантом протокола с таймерами, имеющими -ограниченное расхождение. Этот протокол удовлетворяет требованиям отсутствия потерь и упорядочения.3.3. Упражнения к главе 33.3.1Упражнение 3.1. Покажите, что симметричный протокол раздвижного окнане удовлетворяет требованию непременной доставки сообщения, если из двухдопущений справедливости F1 и F2 выполняется только допущение F2.Упражнение 3.2.
Докажите, что если в симметричном протоколе раздвижного окна L = 1 и начальные значения переменных a p и aq равны −lq и −lp , торавенства ap + lq = sp и aq + lp = sq всегда выполняются.3.3.2Упражнение 3.3. В протоколе с таймерами отправитель может занести в отчет слово как возможно утраченное, в то время как это слово было благополучнодоставлено получателю.1. Опишите выполнение этого протокола, в ходе которого происходит подобный эффект.2. Можно ли разработать такой протокол, в котором отправитель за ограниченное время составляет отчет об ошибке в том и только том случае, когдаслово не доставляется получателю?115Упражнение 3.4.
Предположим, что в связи с выходом из строя часовогомеханизма получатель не может закрыть сеанс связи вовремя. Опишите вычисление протокола с таймерами, в ходе которого слово будет утрачено, но отправительне сможет отметить это в отчете.Упражнение 3.5. Опишите такое вычисление протокола с таймерами, в ходекоторого получатель открывает сеанс связи после получения пакета с порядковым номером, большим нуля.Упражнение 3.6. Действие Time- не моделирует расхождение оставшегосявремени жизни пакета. Почему?Упражнение 3.7. Докажите теорему 3.16.Упражнение 3.8.
Проектировщик сети хотел бы воспользоваться протоколом с таймерами, но при этом желает, чтобы о возможно утраченных словахзапись в отчете осуществлялась ранее. Для этого он модифицирует действие E pследующим образом:Ep : (* Сформировать отчет об ошибке для возможно утраченного слова *){ Ut [B + Low] < 0 }begin error [B + Low] := true ; Low := Low + 1 endБудет ли модифицированный таким образом протокол удовлетворять требованиям отсутствия потерь и упорядочения или для этого необходимо внести такжедругие изменения? Каковы, по Вашему мнению, преимущества и недостатки указанной модификации?117ГЛАВА 4АЛГОРИТМЫ МАРШРУТИЗАЦИИВ общем случае процесс (узел в компьютерной сети) непосредственно не соединен каналами связи с каждым другим процессом.
Из каждого узла пакетыинформации могут непосредственно передаваться только некоторому подмножеству других узлов, которые называются соседями этого узла. Маршрутизация —это термин, который используется для описания процедуры принятия решенияо том, какому соседу (иногда не единственному) следует переслать пакет, чтобыон в конце концов был доставлен по назначению.
Цель, которая ставится припроектировании алгоритма маршрутизации, состоит в том, чтобы снабдить каждый узел процедурой, которая сможет выполнять эту функцию и гарантироватьдоставку каждого пакета.Ясно, что в каждом узле должна храниться некоторая информация о топологии сети, и локальная процедура должна принимать решение на основе этойинформации; эту информацию мы будем называть таблицей маршрутизации.Как только введены эти таблицы, задачу маршрутизации можно разбить на двеалгоритмические составляющие; определение структуры таблицы, конечно, является составной частью разработки алгоритма.1. Вычисление таблиц. Таблицы маршрутизации должны быть вычисленыпри инициализации сети и должны быть обновлены при изменении топологиисети.2.
Продвижение пакета. Когда пакет пересылается по сети, для его продвижения используются таблицы маршрутизации.Критерии оценки качества методов маршрутизации учитывают следующие показатели.1. Корректность. Алгоритм должен доставлять каждый пакет, поступивший в сеть, в точности по назначению.2. Эффективность. Алгоритм должен отправлять пакеты по «наилучшим»путям; например, ожидается, что выбранные пути приводят к небольшой задержке и обеспечивают высокую пропускную способность всей сети. Алгоритм называется оптимальным, если он позволяет задействовать «наилучшие» пути.3. Сложность. Алгоритм вычисления таблиц должен использовать как можно меньше сообщений, расходовать как можно более экономно время и память.Другим аспектам сложности, учитывающим, насколько быстро может быть построен маршрут, насколько быстро пакет может быть подготовлен для пересылки,и т. п., в этой главе будет уделяться меньше внимания.4.
Устойчивость. В случае изменения топологии (добавления или удаленияканала или вершины) алгоритм вносит изменения в таблицы маршрутизации, длятого чтобы задачу маршрутизации можно было решить в модифицированной сети.5. Адаптивность. Для того чтобы выровнять загруженность каналов и вершин, алгоритм приспосабливает к этому таблицы, избегая прокладывать путичерез те каналы и вершины, которые чрезмерно загружены, и отдавая предпочтение тем каналам и вершинам, на которые в это время возложена наименьшаянагрузка.6.
Справедливость. Алгоритм должен обслуживать всех пользователей в равной мере.Эти требования порой вступают в конфликт друг с другом, и большинство алгоритмов имеют хорошую производительность только относительно некоторого ихподмножества.Сеть, как обычно, представляется графом, вершины которого соответствуютузлам сети, и при этом соседние вершины соединены ребром, если между ними имеется канал связи. Оптимальность алгоритма зависит от того, какой путьв графе считается «наилучшим»; существует несколько вариантов понятия «наилучший путь», и для каждого из них имеется свой класс алгоритмов маршрутизации.1.
Минимальное количество звеньев. Стоимость использования пути определяется количеством звеньев (пройденных каналов или шагов от одной вершины к другой) в этом пути. Алгоритм маршрутизации с минимальным числомзвеньев выбирает пути, имеющих наименьшее возможное число звеньев.2. Кратчайший путь. Каждому каналу связи придается неизменный (неотрицательный) вес, и стоимость пути полагается равной суммарному весу всех каналов пути.
Алгоритм кратчайшего пути выбирает путь наименьшей стоимости.3. Минимальная задержка. Каждому каналу связи придается динамическиизменяемая характеристика, зависящая от трафика через этот канал. Алгоритмминимальной задержки постоянно пересматривает таблицы так, чтобы всегда выбирались пути с (почти) минимальной общей задержкой. Так как задержка, приписанная каналам, зависит от фактического трафика, различные пакеты, переправляемые по сети, влияют друг на друга; степень этого влияния на алгоритмымаршрутизации мы обсудим в конце § 4.6.1.Другие варианты понятия оптимальности пути могут оказаться полезными в специальных приложениях, но мы не будем их обсуждать здесь.Содержание главы.
В этой главе будет рассматриваться следующий материал. В § 4.6.1 будет показано, что по крайней мере для задачи маршрутизациис наименьшим числом звеньев и по кратчайшему пути можно проложить оптимальные маршруты для всех пакетов, адресованных одному и тому же адресатуd, посредством остовного дерева с корнем в вершине d. Вследствие этого привыборе маршрута источник сообщения может не приниматься во внимание.В § 4.6.2 описан алгоритм вычисления таблиц маршрутизации для статической сети со взвешенными каналами.
Алгоритм проводит распределенное вычисление кратчайшего пути между любыми двумя парами вершин и помещает118Гл. 4. Алгоритмы маршрутизациив память каждой вершины-источника первого соседа на пути к тому или иному узлу-адресату. Недостатком этого алгоритма является то, что все вычислениенужно проводить повторно всякий раз, когда топология сети изменяется, т. е.алгоритм неустойчив.Алгоритм Netchange, который рассматривается в § 4.6.3, свободен от этогонедостатка: он адаптируем к отказам и восстановлениям, возникающим в каналах связи, путем частичного перевычисления таблиц маршрутизации.
Для тогочтобы упростить анализ алгоритма, мы рассмотрим тот его вариант, в которомстоимость пути определяется числом звеньев в этом пути. Алгоритм Netchangeможно модифицировать так, чтобы применять его и для случая взвешенных каналов, в которых возможны отказы и восстановления.В алгоритмах маршрутизации, представленных в § 4.6.2 и 4.6.3, в каждойвершине используются таблицы маршрутизации в зависимости от возможныхпроцессов-адресатов. Для больших сетей, состоящих из компактных вершин,хранение этой информации может быть обременительным.
В § 4.6.4 будут рассмотрены некоторые стратегии маршрутизации, которые кодируют топологическую информацию в адресе вершины для сокращения объема таблиц маршрутизации и упрощения поиска в этих таблицах. Эти «компактные» алгоритмы маршрутизации обычно не используют оптимальных путей. Мы проанализируем древесные схемы, схемы интервальной и префиксной маршрутизации.В § 4.6.5 рассматриваются иерархические методы маршрутизации. Эти методыпредусматривают разбиение сети на связанные друг с другом кластеры; маршрутизация внутри кластера и между кластерами проводится по-разному. Такойподход позволяет сократить число решений, которые нужно принять, для тогочтобы проложить маршрут или для того чтобы сократить объем памяти, необходимой для хранения таблиц маршрутизации в каждой вершине.4.1. Маршрутизация на основе узлов-адресатовВыбор маршрута для продвижения пакета обычно проводится только с учетомузла-адресата пакета (и содержимого таблиц маршрутизации) и независимо отисходного отправителя (источника) пакета.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
