Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 47
Текст из файла (страница 47)
Действиями сети под управлением контроллера con являютсявсе те и только те действия сети, которые разрешены контроллером con.Говорят, что пакет заблокирован в сети, если никакая последовательностьдействий сети не позволяет доставить этот пакет по назначению.5.2. Структурированные решения173Определение 5.2. Для заданной сети G, контроллера con для G и конфигурации у сети G пакет р (присутствующий в конфигурации у) называется заблокированным, если не существует никакой последовательности действий подуправлением контроллера con, применимой к конфигурации у, в результате выполнения которых пакет р будет поглощен. Конфигурация называется тупиковой, если в ней присутствует заблокированный пакет.Как следует из примера, изображенного на рис.
5.1, тупиковые конфигурациисуществуют для любого контроллера. Задача контроллера состоит в том, чтобы непозволить сети попасть в такие конфигурации. Начальными конфигурациями сетиобъявляются такие конфигурации, в которых отсутствуют какие-либо пакеты.Определение 5.3. Контроллер называется беступиковым, если под управлением этого контроллера невозможно попасть из начальной конфигурации втупиковую.5.2. Структурированные решенияМы рассмотрим здесь класс контроллеров, в основу которых положены т. н.буферные графы, введенные Мерлином и Швейцером в работе [148].
Принципустройства буферных графов определяется тем соображением, что тупиковая ситуация (при отсутствии контроллера) возникает, как только образуется цикл ожиданий. Цикл ожиданий предполагает наличие такой последовательности пакетовРо, ■■■, ps-\, что для каждого i пакет pi стремится переместиться в буфер, занятый пакетом pi+\ (индексы вычисляются по модулю s). Циклических ожиданий можно избежать, если перемещать пакеты по путям в ациклическом графе(буферном графе).
В §5.2.1 будут даны определения буферных графов и сопутствующего им класса контроллеров, а также будут приведены два простых примера буферных графов. В §5.2.2 будет рассказано о более изощренном способепостроения буферных графов, а также будут приведены два иллюстрирующихпримера.5.2.1. Буферные графыПусть задана сеть G с множеством буферов В.Определение 5.4. Буферным графом (для графа G с буферами В) называется ориентированный граф BG, вершинами котрого служат буферы сети, т.
е.BG = (В, BE), удовлетворяющий следующим условиям:1) BG — ациклический граф (граф, не содержащий контуров);2) если bcE.BE, то b и с либо являются буферами одного и того же узла, либоявляются буферами двух узлов, соединенных каналом связи в графе G;3) для каждого пути Р e V существует путь в графе BG, образом которого(см.
ниже) является путь Р.Второе условие задает отображение множества путей в графе BG в множествопутей в графе G. Это отображение устроено так. Рассмотрим произвольный путь174Гл. 5. Неблокируемая коммутация пакетовЬо, Ь\, . . . , bs в графе BG и сопоставим каждому буферу ф тот узел щ, в которомрасполагается этот буфер. В результате получим такую последовательность узловмо, мь • • •, ms, в которой для любого номера i < s выполняется либо включениещщ+ 1 е Е, либо включение щ = щ+\.
Тот путь в графе G, который получается изэтой последовательности за счет удаления последовательно идущих дубликатоводного и того же узла, будем называть образом исходного пути Ьо, Ь\, ... , bs изBG.Пакет нельзя помещать в произвольно выбранный буфер; он должен бытьпомещен в такой буфер, из которого сможет впоследствии достичь узла-адресата,следуя по пути в графе BG. В приведенном ниже определении как раз говоритсяо том, какой буфер следует считать подходящим.Определение 5.5.
Пусть пакет р, адресованный узлу v, пребывает в узле и.Буфер b узла и считается подходящим для пакета р, если в графе BG существуетпуть из вершины Ь в какой-нибудь буфер с узла v, и образом этого пути в графеBG является один из тех путей в графе G, по которому пакет р может следоватьв сети G.Один из таких путей в графе BG будет выделен как гарантированный путь,и запись nb(p, Ь) будет использоваться для обозначения следующего буферав этом гарантированном пути. Для каждого вновь сформированного в узле ипакета р существует предписанный этому пакету подходящий буфер fb(p).Знакосочетания fb и nb являются акронимами выражений «first buffer» и «nextbuffer». Следует иметь в виду, что буфер nb(p, b) всегда является подходящим дляпакета р.
Во всех буферных графах, которые мы будем рассматривать в этом параграфе, буфер nb(p, Ь) будет располагаться в другом узле, нежели тот, которомуприписан буфер Ь. Впоследствии мы обсудим использование «внутренних» реберв графе BG, т.
е. тех ребер, которые инцидентны двум буферам одного и того жеузла.Контроллер буферного графа. Буферный граф BG можно использовать дляреализации беступикового контроллера bgcBG при условии, что буфер nb(p, Ь)будет закодирован в каждом пакете р и/или состоянии того узла, в котором оказывается пакет р.Определение 5.6. Контроллер bgcBG устроен следующим образом.1. Пакет р разрешается сформировать в узле и в том и только том случае,когда буфер fb(p) свободен. Как только этот пакет будет сформирован, он помещается в указанный буфер.2. Пакет р разрешается переправить из буфера в узле и в буфер узла w (приэтом возможно, что и = w) в том и только том случае, когда буфер nb(p, Ь)(в узле w) свободен.
Если это перемещение происходит, то пакет р помещаетсяв буфер nb(p, b).Теорема 5.7. Контроллер bgcBG является беступиковым.5.2. Структурированные решения175Д о к а з а т е л ь с т в о . Если в узле и все буферы пусты, то в узле и разрешается сформировать любой пакет. Это означает, что bgcBG действительноявляется контроллером.Для каждого буфера сети Ь еВ назовем классом буфера b длину самого протяженного пути в графе BG, который оканчивается в вершине Ь. Нужно заметить,что классы буферов в любом пути в графе BG (в частности, в гарантированномпути) строго возрастают, т. е. класс буфера nb{p, Ь) превосходит класс буфера Ь.Так как контроллер разрешает помещать пакеты только в подходящие буферыи в самом начале нет никаких пакетов, в каждой достижимой конфигурации сети,находящейся под управлением контроллером bgcBG, пакеты содержатся тольков подходящих буферах.
Воспользовавшись нисходящей индукцией по классамбуферов, нетрудно показать, что в такой конфигурации ни один буфер класса гне содержит заблокированного пакета. Обозначим символом R наивысший классбуферов.Случай г = R . Буфер b наивысшего класса R, расположенный в узле и, неимеет исходящих дуг в графе BG. Следовательно, всякий пакет, для которогобуфер b является подходящим, адресован узлу и и может быть поглощен, кактолько он окажется в буфере Ь. Отсюда следует, что ни один буфер класса R несодержит заблокированных пакетов.Случай г < R .
Индуктивная гипотеза гласит, что для любого числа г', удовлетворяющего неравенству г < г' ^ R, ни один буфер класса г' не содержитв достижимых конфигурациях заблокированного пакета.Рассмотрим произвольную достижимую конфигурацию у, в которой пакет рпомещен в буфер Ь класса г < R, приписанный узлу и. Если узел и является адресатом пакета р, то пакет р может быть поглощен и поэтому не можетсчитаться заблокированным. В противном случае рассмотрим следующий буферnb(p, Ь) = с в гарантированном пути из вершины Ь и заметим, что класс г' буфера с превосходит число г.
По индуктивной гипотезе буфер с не может содержатьзаблокированного пакета, и поэтому есть конфигурация 8 , достижимая из конфигурации у, в которой буфер с пуст. В конфигурации 8 пакет р может быть перемещен в буфер с, и на основании индуктивной гипотезы этот пакет не считаетсязаблокированным в результирующей конфигурации 8 '. Следовательно, пакет р незаблокирован в конфигурации у.□Как видно из доказательства теоремы, если в гарантированном пути встречаются «внутренние» дуги буферного графа (дуги между буферами одного и тогоже узла), то контроллер обязан разрешить выполнить дополнительное действие,в результате чего пакет перемещается в другой буфер того же самого узла. Обычно гарантированный путь не содержит таких дуг.
Они используются только в качестве необязательных действий, чтобы повысить эффективность продвиженияпакетов, как это происходит в следующей ситуации. Предположим, что пакет рпомещен в буфер Ь\ узла и, а буфер nb(p, Ь\) в узле w занят. Однако в узле иможет быть свободный буфер Ьч, подходящий для пакета р, и, кроме того, буферnb(p, Ьч) в узле w может оказаться свободным. В таком случае пакет может бытьперемещен через буферы Ьч и nb(p, Ьч).176Гл.
5. Неблокируемая коммутация пакетовТеперь мы обсудим два примера использования буферных графов, а именносхему назначения и схему пройденных шагов.Схема назначения. В схеме назначения в каждом узле и выделяется N буферов, по одному буферу bu[v] для каждой возможной вершины-адресата v. Узелv называется назначением буфера bu[v], В этой схеме предполагается, что алгоритм маршрутизации продвигает все пакеты, адресованные узлу v, по ориентированному дереву Т„, корнем которого является узел v. (На самом деле это допущение можно ослабить; достаточно того, чтобы каналы, предназначенные дляпостроения маршрутов к узлу и, образовывали ациклический подграф графа G.)Пусть задан буферный граф BGa = {В, BE), в котором bu[v\\bw[v2 \ € BE тогда и только тогда, когда щ = V2 и пара uw образует дугу в дереве Тщ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
