Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 48
Текст из файла (страница 48)
Принципустройства буферных графов определяется тем соображением, что тупиковая ситуация (при отсутствии контроллера) возникает, как только образуется цикл ожиданий. Цикл ожиданий предполагает наличие такой последовательности пакетовp0 , . . . , ps−1 , что для каждого i пакет pi стремится переместиться в буфер, занятый пакетом pi+1 (индексы вычисляются по модулю s). Циклических ожиданий можно избежать, если перемещать пакеты по путям в ациклическом графе(буферном графе).
В § 5.2.1 будут даны определения буферных графов и сопутствующего им класса контроллеров, а также будут приведены два простых примера буферных графов. В § 5.2.2 будет рассказано о более изощренном способепостроения буферных графов, а также будут приведены два иллюстрирующихпримера.5.2.1. Буферные графыПусть задана сеть G с множеством буферов B .Определение 5.4. Буферным графом (для графа G с буферами B) называется ориентированный граф BG, вершинами котрого служат буферы сети, т.
е.~ удовлетворяющий следующим условиям:BG = (B , BE),1) BG — ациклический граф (граф, не содержащий контуров);~ то b и c либо являются буферами одного и того же узла, либо2) если bc ∈ BE,являются буферами двух узлов, соединенных каналом связи в графе G;3) для каждого пути P ∈ P существует путь в графе BG, образом которого(см. ниже) является путь P.Второе условие задает отображение множества путей в графе BG в множествопутей в графе G. Это отображение устроено так. Рассмотрим произвольный путь174Гл. 5. Неблокируемая коммутация пакетовb0 , b1 , . . . , bs в графе BG и сопоставим каждому буферу bi тот узел ui , в которомрасполагается этот буфер.
В результате получим такую последовательность узловu0 , u1 , . . . , us , в которой для любого номера i < s выполняется либо включениеui ui+1 ∈ E, либо включение ui = ui+1 . Тот путь в графе G, который получается изэтой последовательности за счет удаления последовательно идущих дубликатоводного и того же узла, будем называть образом исходного пути b 0 , b1 , . . . , bs изBG.Пакет нельзя помещать в произвольно выбранный буфер; он должен бытьпомещен в такой буфер, из которого сможет впоследствии достичь узла-адресата,следуя по пути в графе BG. В приведенном ниже определении как раз говоритсяо том, какой буфер следует считать подходящим.Определение 5.5.
Пусть пакет p, адресованный узлу v, пребывает в узле u.Буфер b узла u считается подходящим для пакета p, если в графе BG существуетпуть из вершины b в какой-нибудь буфер c узла v, и образом этого пути в графеBG является один из тех путей в графе G, по которому пакет p может следоватьв сети G.Один из таких путей в графе BG будет выделен как гарантированный путь,и запись nb(p, b) будет использоваться для обозначения следующего буферав этом гарантированном пути. Для каждого вновь сформированного в узле uпакета p существует предписанный этому пакету подходящий буфер fb(p).175Д о к а з а т е л ь с т в о. Если в узле u все буферы пусты, то в узле u разрешается сформировать любой пакет.
Это означает, что bgc BG действительноявляется контроллером.Для каждого буфера сети b ∈ B назовем классом буфера b длину самого протяженного пути в графе BG, который оканчивается в вершине b. Нужно заметить,что классы буферов в любом пути в графе BG (в частности, в гарантированномпути) строго возрастают, т. е. класс буфера nb(p, b) превосходит класс буфера b.Так как контроллер разрешает помещать пакеты только в подходящие буферыи в самом начале нет никаких пакетов, в каждой достижимой конфигурации сети,находящейся под управлением контроллером bgc BG , пакеты содержатся тольков подходящих буферах.
Воспользовавшись нисходящей индукцией по классамбуферов, нетрудно показать, что в такой конфигурации ни один буфер класса rне содержит заблокированного пакета. Обозначим символом R наивысший классбуферов.Случай r = R. Буфер b наивысшего класса R, расположенный в узле u, неимеет исходящих дуг в графе BG. Следовательно, всякий пакет, для которогобуфер b является подходящим, адресован узлу u и может быть поглощен, кактолько он окажется в буфере b. Отсюда следует, что ни один буфер класса R несодержит заблокированных пакетов.Случай r < R.
Индуктивная гипотеза гласит, что для любого числа r 0 , удовлетворяющего неравенству r < r0 6 R, ни один буфер класса r0 не содержитв достижимых конфигурациях заблокированного пакета.Рассмотрим произвольную достижимую конфигурацию , в которой пакет pпомещен в буфер b класса r < R, приписанный узлу u. Если узел u является адресатом пакета p, то пакет p может быть поглощен и поэтому не можетсчитаться заблокированным. В противном случае рассмотрим следующий буферnb(p, b) = c в гарантированном пути из вершины b и заметим, что класс r 0 буфера c превосходит число r. По индуктивной гипотезе буфер c не может содержатьзаблокированного пакета, и поэтому есть конфигурация , достижимая из конфигурации , в которой буфер c пуст.
В конфигурации пакет p может быть перемещен в буфер c, и на основании индуктивной гипотезы этот пакет не считаетсязаблокированным в результирующей конфигурации 0 . Следовательно, пакет p незаблокирован в конфигурации .Контроллер буферного графа. Буферный граф BG можно использовать дляреализации беступикового контроллера bgc BG при условии, что буфер nb(p, b)будет закодирован в каждом пакете p и/или состоянии того узла, в котором оказывается пакет p.Определение 5.6. Контроллер bgcBG устроен следующим образом.1.
Пакет p разрешается сформировать в узле u в том и только том случае,когда буфер fb(p) свободен. Как только этот пакет будет сформирован, он помещается в указанный буфер.2. Пакет p разрешается переправить из буфера в узле u в буфер узла w (приэтом возможно, что u = w) в том и только том случае, когда буфер nb(p, b)(в узле w) свободен. Если это перемещение происходит, то пакет p помещаетсяв буфер nb(p, b).Теорема 5.7.
Контроллер bgcBG является беступиковым.Знакосочетания fb и nb являются акронимами выражений «first buffer» и «nextbuffer». Следует иметь в виду, что буфер nb(p, b) всегда является подходящим дляпакета p. Во всех буферных графах, которые мы будем рассматривать в этом параграфе, буфер nb(p, b) будет располагаться в другом узле, нежели тот, которомуприписан буфер b. Впоследствии мы обсудим использование «внутренних» реберв графе BG, т. е. тех ребер, которые инцидентны двум буферам одного и того жеузла.5.2.
Структурированные решенияКак видно из доказательства теоремы, если в гарантированном пути встречаются «внутренние» дуги буферного графа (дуги между буферами одного и тогоже узла), то контроллер обязан разрешить выполнить дополнительное действие,в результате чего пакет перемещается в другой буфер того же самого узла. Обычно гарантированный путь не содержит таких дуг. Они используются только в качестве необязательных действий, чтобы повысить эффективность продвиженияпакетов, как это происходит в следующей ситуации.
Предположим, что пакет pпомещен в буфер b1 узла u, а буфер nb(p, b1) в узле w занят. Однако в узле uможет быть свободный буфер b2 , подходящий для пакета p, и, кроме того, буферnb(p, b2) в узле w может оказаться свободным. В таком случае пакет может бытьперемещен через буферы b2 и nb(p, b2).176Гл. 5. Неблокируемая коммутация пакетовТеперь мы обсудим два примера использования буферных графов, а именносхему назначения и схему пройденных шагов.Схема назначения. В схеме назначения в каждом узле u выделяется N буферов, по одному буферу bu [v] для каждой возможной вершины-адресата v. Узелv называется назначением буфера bu [v] .
В этой схеме предполагается, что алгоритм маршрутизации продвигает все пакеты, адресованные узлу v, по ориентированному дереву Tv , корнем которого является узел v. (На самом деле это допущение можно ослабить; достаточно того, чтобы каналы, предназначенные дляпостроения маршрутов к узлу v, образовывали ациклический подграф графа G.)~ в котором bu [v1 ] bw [v2 ] ∈ BE~ тоПусть задан буферный граф BGd = (B , BE),гда и только тогда, когда v1 = v2 и пара uw образует дугу в дереве Tv1 . Чтобыубедиться в том, что в графе BGd отсутствуют контуры, заметим, что в нем нетдуг между буферами с разными назначениями, а буферы с одним и тем же назначением v образуют дерево, изоморфное дереву Tv . Всякий путь P ∈P , оканчивающийся в узле v, является путем в дереве Tv , и по определению рассматриваемогобуферного графа BGd в нем существует такой путь, проходящий по буферам сназначением v, образом которого является путь P.
Именно этот путь в графеBGd и будет считаться гарантированным путем. Это означает, что для пакета p,адресованного узлу v и сформированного в узле u, должно выполняться равенство fb(p) = bu [v] , и если его нужно отправить в узел w, то должно выполнятьсяравенство nb(p, b) = bw [v] .Определение 5.8. Контроллер dest — это контроллер буферного графа bgcBGd ,в котором функции fb и nb определены так, как в предыдущем абзаце.Теорема 5.9.
Для произвольной связной сети существует беступиковый контроллер, который использует N буферов в каждом узле и позволяет перемещать пакеты по произвольным заранее выбранным входнымдеревьям.5.2. Структурированные решения177.u.u.1 .................@..... .z.. u@uw2w1 u. . . .: v..@.......@.......@R@ .u. . . . .u2I@@Рис.
5.2. Маршрутизация, недопустимая для контроллера destную схему источников, в которой каждый буфер соответствует вершине v i ииспользуется для хранения пакетов, сформированных в узле v i .Схема пройденных шагов. В схеме пройденных шагов каждый узел u имеетk + 1 буферов bu [0] , . . . , bu [k] .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
