Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 50
Текст из файла (страница 50)
выше^ /о>в-}sЕсм. вышеs=io> B - Z jss= 0ввиду того, что js ^> B- tввидуisТОГО, ЧТО0(и г'о ^js = 0 ДЛЯкоторое и составляет ожидаемое противоречие.S0)< Sq□Контроллер с состояниями обратного отсчета. Существует также и контроллер, «двойственный» контроллеру с состояниями прямого отсчета, в которомучитывается более подробная информация, нежели в контроллере с обратным отсчетом, и за счет этого разрешается большее количество действий. Будем считать,что запись tp используется в том же качестве, что и ранее. Определим вектор состояния (г’о, . .
. , ip), где it равно числу пакетов в узле и, которые уже совершилив точности t продвижений.Определение 5.21. Контроллер с состояниями обратного отсчета BSразрешает прием пакета р в узле и , имеющем вектор состояния (г'о, . . . , г'*), тогдаи только тогда, когда выполняется соотношение/V /,tp К, j К, k: j >it ~ В + k.t=оДоказательство утверждения о том, что контроллер BS является беступиковым, аналогично доказательству теоремы 5.20.Сравнительный анализ контроллеров. Контроллер с состояниями прямогоотсчета более либерален, чем контроллер с прямым отсчетом, поскольку позволяет совершать большее количество действий.186Гл.
5. Неблокируемая коммутация пакетовЛемма 5.22. Каждое действие, разрешенное контроллером FC, такжеразрешено контроллером FS.Доказательство.Предположим, что контроллер FC разрешает узлуkи принять пакет р. Тогда должно быть выполнено неравенство sp < fa = B - J 2 j s,ks= 0и поэтому для всех i К sp верно неравенство / < В —^2js, откуда следует, чтоs=iконтроллер FS разрешает совершить указанное действие.□В работе [196] было показано, что контроллер FC более либерален, чем контроллер ВС, контроллер FS более либерален, чем контроллер BS, а контроллерBS более либерален, чем контроллер ВС.
Кроме того, было установлено, чтокаждый из этих четырех контроллеров является наиболее либеральным средивсех контроллеров, которые используют ту же самую информацию.5.4. Прочие вопросыКак видно из результатов, представленных в этой главе, важная роль в нихотводится количеству буферов, которые требуются контроллеру. Обычно пропускная способность сети возрастает с увеличением числа доступных буферов.Для неструктурированных решений дается только нижняя оценка числа буферов;для использования большего числа буферов контроллеры не нужно модифицировать.
А вот в структурированных решениях дополнительные буферы нужносуметь каким-то образом ввести в буферный граф, и это можно сделать либо статически, либо динамически. Если это сделать статически, то каждыйбуфер будет иметь заданное положение в буферном графе, т. е. буферный графстроится более «просторно», нежели это описано в примере из §5.5.2. Обычновместо одиночного буфера fb(p) или nb(p, Ь) сразу несколько буферов назначаются в качестве возможных точек начала или продолжения пути в буферномграфе.
Если введение дополнительных буферов проводится динамически, то вначале при построении буферного графа используется как можно меньше буферов;эти буферы в графе мы будем называть логическими буферами. Е1ри выполненииопераций каждый реальный буфер (который мы будем называть физическим буфером) может быть использован в качестве любого логического буфера, но приэтом для каждого логического буфера должен быть хотя бы один физическийбуфер, которому отводится роль этого логического буфера.
В такой схеме дляпредотвращения блокировки необходимо отвести место только для небольшогочисла буферов, а остальные буферы можно использовать свободно, гибко варьируя их назначение.В этой главе мы исходили из предположения о том, что пакеты имеют одини тот же размер и поэтому буферы имеют одинаковый размер и могут вмещатьв точности один пакет.
Задачу можно исследовать и в рамках предположенияо том, что размер пакетов может варьироваться. Для этого случая Бодлаендерв работе [30] адаптировал те решения, которые мы рассматривали в §5.5.3.5.4. Прочие вопросы1875.4.1. Изменения топологииДо сих пор мы не принимали во внимание возможность того, что по мерепродвижения пакетов от источника к адресату топология сети может измениться.После того как происходит такое изменение, таблицы маршрутизации в каждомузле уточняются, и после этого продвижение пакетов осуществляется на основеуточненных таблиц. В результате такой модификации таблиц пакет может последовать таким путем в сети, который никогда не был бы избран, если бы измененияне случились; может случиться даже так, что весь путь пакета в целом будет содержать циклы.Влияние, которые оказывают приведенные соображения на методы предотвращения блокировки, изученные в этой главе, на первый взгляд противоречатнашей интуиции.
Контроллер dest, корректность которого опирается на предположение о том, что в множестве V содержатся только простые пути, можнопродолжать использовать без всяких модификаций. А вот контроллеры, зависящие только от верхней оценки числа звеньев в путях по которым следуют пакеты,требуют серьезного внимания.Контроллер dest. Спустя какое-то определенное время, после того как случится последнее топологическое изменение, таблицы маршрутизации должны стабилизироваться и стать ациклическими таблицами.
И даже в том случае, если вовремя вычисления таблиц образуется ситуация циклического простоя, как только вычисление таблиц завершится, буферный граф снова станет ациклическим,и все пакеты окажутся помещенными в подходящие буферы. Следовательно, едвалишь таблицы маршрутизации установятся, образовавшаяся в результате конфигурация не будет содержать заблокированных пакетов.Контроллеры пройденных шагов.
Рассмотрим контроллер, который зависит от предположения о том, что всякий пакет следует путем, состоящим самоебольшее из k звеньев. Можно выбрать достаточно большое значение k, чтобыможно было гарантировать с высокой вероятностью , что каждый пакет достигает своего адресата, совершив не более k шагов, даже в том случае, когда походу его пересылки от источника к адресату случаются топологические изменения. Для всех пакетов, которые достигают своего адресата за k шагов, контроллерпройденных шагов, а также контроллеры с прямым и обратным отсчетом можноиспользовать без всяких ограничений.
Однако может случиться так, что пакет недостигает своего адресата за k шагов в связи с тем, что изменения в топологиисети и соответствующие уточнения таблиц произошли неудачно. Если это так, топакет будет помещен в неподходящий буфер, и он будет навсегда заблокированв узле, не дойдя до адресата.Ситуации такого рода могут быть разрешены только во взаимодействии с протоколами более высокого уровня в иерархии протоколов. Простейшее решениепредусматривает отмену пакета.
С точки зрения протокола сквозной передачиданных пакет теперь считается потерянным, но с этой потерей можно справитьсяпри помощи протокола сеансового уровня, как было показано в §3.3.2.188Гл. 5. Неблокируемая коммутация пакетовОтмена пакетов необходима и для того, чтобы реализовать допущение, которое было сделано в §3.3.2, о том, что всякий пакет имеет максимальный срокжизни pi.
Если для продвижения пакета требуется время pio, ограничение времени жизни пакета в сквозной передаче данных величиной pi приводит к тому, чтомаксимальное число шагов, которые может совершить пакет, ограничено числомk = pi/pio.5.4.2. Другие типы блокировокВ этой главе рассматривались только блокировки хранения-продвижения.Если верны те допущения, которые были сделаны в § 5.5.1, блокировка храненияпродвижения— это единственно возможный тип блокировки, который может случиться. Однако в сетях, которые применяются на практике, эти допущения справедливы не всегда, и, как было отмечено в работе Мерлина и Швейцера [149],это приводит к тому, что возникают другие типы блокировок. Мерлин и Швейцер выделили четыре типа блокировок, а именно, потомственную блокировка,блокировку высвобождения копий, блокировку темпа и блокировку сборки пакетов, и показали, как предотвратить блокировки этих типов, распространив наних метод буферных графов.Потомственная блокировка возникает, когда пакет р может порождать в сети другой пакет q, например отчет об отказе, который направляется в узел, являющийся источником исходного пакета, если ему пришлось столкнуться с неисправностью канала.
В связи с этим возникает причинно-следственная связь междуформированием нового пакета (q) и продвижением или поглощением уже существующего пакета (р), и тем самым нарушается допущение, сделанное в §5.5.1,которое гласит, что сеть всегда разрешает продвижение и поглощение пакета.Для предотвращения потомственной блокировки нужно завести две копии буферного графа, один из которых будет использоваться для основных сообщений,а другой для производных сообщений (потомков). Если потомки могут в своюочередь порождать новое потомство, нужно использовать несколько уровней буферных графов.Блокировка высвобождения копий возникает, когда узел-источник сохраняет копию пакета, до тех пор пока от узла-адресата не поступит подтверждениео получении пакета.
(Вспомните, как устроен протокол передачи сообщений стаймерами, описанный в §3.3.2, и представьте себе, что последовательность словinp размещена в той же самой области памяти, которая используется механизмоммаршрутизации для временного хранения пакетов.) Вследствие этого нарушаетсянарушается допущение о том, что после продвижения пакета занятый им буферосвобождается (см. §5.5.1).Для предотвращения блокировки высвобождения копий можно предложитьдве модификации метода буферных графов. В первом случае мы опираемся напредположение о том, что блокировка высвобождения копий всегда возникает засчет того, что образуется циклический простой основных сообщений, а также5.4.
Прочие вопросы189подтверждающих сообщений. Решение состоит в том, чтобы рассматривать подтверждения как производные сообщения (потомки) и помещать их в отдельныекопии буферного графа. Второй вариант решения в большинстве случаев требуетменьшего числа буферов. Суть его состоит в том, что вновь порожденные пакетыпомещаются в специальные отведенные для них ключевые буферы, в которыезапрещается помещать переправляемые пакеты.Блокировка темпа возникает, когда в сети есть узлы, у которых внутренняяпамять ограничена, и поэтому они не могут поглощать сообщения, до тех порпока не будут сформированы какие-то другие сообщения.
Например, терминалтелетайпа должен сначала выдать некоторый символ, а уже потом принять следующий символ для печати. Вследствие этого нарушается наше допущение о том,что пакет, который достиг узла-адресата, может быть всегда поглощен.Чтобы предотвратить блокировку темпа, нужно проводить различие междупродвигающимися пакетами и откликами на продвижение, имея в виду, что поглощение пакетов первого типа может произойти только после того, как будутсформированы пакеты второго типа. Для сообщений этих двух типов используются разные копии буферного графа.Блокировка сборки пакета может возникнуть в сетях, в которых для доставки больших сообщений приходится разбивать их на маленькие порции и передавать по частям; при этом ни один из маленьких пакетов нельзя изъять изсети до тех пор, пока все части большого сообщения не достигнут своего адресата.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
