Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 50
Текст из файла (страница 50)
Нетрудно показать, что если бы нашлась пара узлов x, y, кратчайшийпуть между которыми было бы нельзя представить в виде последовательногосоединения путей в указанных ориентированных графах, то величина d(x, y) былабы ближе к C/2, нежели d(u, v).Д о к а з а т е л ь с т в о. Согласно теореме 5.13 достаточно подобрать ациклическую ориентацию для дерева, которая сможет покрыть все простые пути.Выберем произвольную вершину r и рассмотрим два дерева: T 1 , в котором вседуги направлены к вершине r, и T2 , в котором все дуги направлены от вершины r(см.
рис. 5.5). Всякий простой путь из вершины u в вершину v представляет собой последовательное соединение пути из u в вершину, являющуюся наименьшимобщим предком вершин u и v в дереве T1 , и пути из этого наименьшего общегопредка в вершину v в дереве T2 .Поскольку описанную здесь схему можно применить к остовному дереву наименьшей глубины, построенному для произвольной сети, мы фактически установили, что для любой сети возможна беступиковая маршрутизация, требующая 2буфера в каждом узле. Но пути, которые при этом будут задействованы, в общемслучае могут оказаться неоптимальными.Применение AOC-контроллеров. Как показывает нам пример с кольцевыми сетями, для применения AOC-контроллеров могут потребоваться весьмаспециальные пути, по которым должны распространяться сообщения.
В связис этим возникает ряд вопросов, исследованию которых был посвящен ряд работпоследних лет.Можно ли, используя минимальное число буферов, переправлять пакеты пооптимальным путям? Если это невозможно, то какова взаимосвязь между буферной сложностью и эффективностью маршрутизации? Штефанкович в работе [179] показал, что AOC-контроллеры не столь уж экономны. Ему удалось построить класс сетей, для которых существует беступиковая оптимальнаямаршрутизация, требующая фиксированного постоянного числа буферов в каждом узле, но при этом наилучшему оптимальному AOC-контроллеру требуетсяиметь Ω (lg N/ lg lg N) буферов в каждом узле. До сих пор неизвестно, наскольковелик разрыв между наилучшим AOC-контроллером и наилучшим контроллеромобщего вида.5.3.
Неструктурированные решенияМожно ли задавать пути, которые используются AOC-контроллерами, припомощи компактных схем маршрутизации, наподобие интервальной маршрутизации? Для гиперкуба удалось установить, что 1) существует оптимальная схемаинтервальной разметки, 2) существует контроллер, которому для использованияоптимальных путей требуется иметь 2 буфера в каждом узле, но при этом 3) неттаких AOC-контроллеров, которые можно было бы так встроить в схему интервальной разметки, чтобы они могли ограничиться использованием только двухбуферов в каждом узле. Исследования в этом направлении еще продолжаются.ближе всего к своему узлу-адресату, т.
е. пакет, имеющий наименьшее значениесчетчика sp среди всех пакетов, оставшихся в конфигурации .Обратимся к узлу u, в котором расположен пакет p. Так как узел u не являетсяадресатом пакета p (иначе он был бы поглощен в конфигурации ), существуеттакой сосед w узла u, которому должен быть передан пакет p. Коль скоро FC неразрешает выполнить это действие, имеет место неравенствоsp − 1 > f w .Поскольку sp 6 k и при этом, согласно сделанному предположению, k < B,отсюда следует неравенство fw < B, которое означает, что в конфигурациихотя бы один пакет расположен в вершине w.
Из всех пакетов, размещенныхв узле w, выберем тот пакет q, который прибыл в узел w самым последним, и0в узле w непосредственно перед тем,рассмотрим число свободных буферов fwкак пакету q было разрешено переместиться в узел w. Ввиду того что пакет q0буферов, и коль скоро, (в силу выбора этого пакета)занимает один из этих fwвсе пакеты, попавшие в узел w после q, впоследствии были удалены из узла w,06 fw + 1.должно выполняться неравенство fwТак как пакету q было разрешено переместиться в узел w, справедливо нера0венство sq < fw. Сопоставив все четыре полученных нами неравенства, приходимк соотношению06 fw + 1 6 s p ,sq < f w5.3. Неструктурированные решения183Гл.
5. Неблокируемая коммутация пакетов182Теперь мы обратимся к классу контроллеров, предложенных Туэгом и Ульманом в работе [196] . Эти контроллеры не выдают предписаний, в какой буферследует поместить тот или иной пакет, и используют только простую локальнуюинформацию, наподобие счетчика шагов или числа буферов, занятых в узле.5.3.1. Контроллеры с прямым и обратным отсчетомКонтроллер с прямым отсчетом. Условимся, что для всякого пакета p запись sp будет обозначать число продвижений, которые необходимо совершитьпакету, чтобы достичь адресата; естественно, что 0 6 s p 6 k. Бывает так, чтозначение sp не нужно передавать вместе с пакетом, поскольку многие алгоритмы вычисляют эти данные в каждом узле (см., например, алгоритм Netchange,описанный в § 4.6.3).
Условимся также, что для каждого узла u запись f u будет обозначать количество свободных буферов узла u. Естественно, что всегдавыполняется неравенство 0 6 fu 6 B.Определение 5.16. Контроллер с прямым отсчетом FC разрешает узлуu принять пакет p в том и только том случае, когда выполняется неравенствоsp < f u .Контроллер разрешает прием пакета, если в узле имеется больше свободныхбуферов, чем число продвижений, которые необходимо совершить пакету.Теорема 5.17. Если B > k, то контроллер FC является беступиковым.Д о к а з а т е л ь с т в о.
Чтобы убедиться в том, что пакет разрешается сформировать в пустом узле, обратим внимание на то, что если все буферы узла uпусты, то fu = B. Новому пакету предстоит совершить не более k продвижений,и, вследствие того что B > k, этот пакет допускается в узле u.Беступиковость контроллера FC будет доказана от противного; Допустим, что— это достижимая тупиковая конфигурация контроллера. Теперь рассмотримконфигурацию , которая получается из конфигурации путем применения максимaльной последовательности действий продвижения и поглощения пакетов. Вконфигурации не может быть продвинут ни один пакет, но, ввиду того что конфигурация является предположительно тупиковой, в конфигурации остаетсяхотя бы один пакет. Рассмотрим пакет p, который в конфигурации расположенкоторое противоречит выбору p.Контроллер с обратным отсчетом. Чтобы построить контроллер, «двойственный» FC, разрешение на прием пакета нужно выдавать на основании числашагов, пройденных этим пакетом.
Условимся, что для всякого пакета p записьtp будет обозначать число продвижений, которые уже удалось совершить пакету.Естественно, что всегда верно неравенство 0 6 t p 6 k.Определение 5.18. Контроллер с обратным отсчетом BC разрешаетузлу u принять пакет p в том и только том случае, когда выполняется неравенствоtp > k − f u .Доказательство утверждения о том, что контроллер BC является беступиковым (упражнение 5.6), аналогично доказательству теоремы 5.17.5.3.2. Контроллеры с состояниями прямого и обратногоотсчетаВоспользовавшись более подробной информацией о пакетах, хранящихся вузле, можно построить контроллер, который функционирует почти так же, каки контроллер с прямым отсчетом, но разрешает при этом совершать большедействий.Контроллер с состояниями прямого отсчета. Запись sp будет обозначатьто же самое, что и в предыдущем параграфе.
Для узла u определим (как функцию184Гл. 5. Неблокируемая коммутация пакетов5.3. Неструктурированные решениясостояния процесса u) целочисленный вектор состояния hj 0 , . . . , jk i, где js —количество пакетов p, размещенных в узле u и удовлетворяющих условию s p = s.Определение 5.19. Контроллер с состояниями прямого отсчета FSразрешает прием пакета p в узле u, имеющем вектор состояния hj 0 , . . . , jk i, тогдаи только тогда, когда выполняется соотношение∀i, 0 6 i 6 sp : i < B −kXjs .s=iТеорема 5.20. Если B > k, то контроллер FS является беступиковым.Д о к а з а т е л ь с т в о. Читателю предоставляется возможность самостоятельно убедиться в том, что пустому узлу разрешается принять любой пакет. Допустим, что существует достижимая тупиковая конфигурация . Теперь рассмотрим конфигурацию , которая получается из конфигурации путем применениямаксимaльной последовательности действий продвижения и поглощения пакетов.В конфигурации есть хотя бы один пакет, но при этом ни один пакет не можетбыть перемещен.
Выберем пакет p с наименьшим значением характеристики s p ;предположим, что пакет p размещен в узле u и должен быть продвинут в узел w.Рассмотрим вектор состояний hj0 , . . . , jk i узла w в конфигурации .PkЕсли в узле w нет пакетов, тоs=0 js = 0, и отсюда следует, что узлу wразрешается принять пакет p, что противоречит выбору конфигурации . Значит,в узле w есть хотя бы один пакет. Из всех пакетов, размещенных в узле w,рассмотрим тот пакет q, который находится ближе всего к своему узлу-адресату,т.
е. удовлетворяет условию sq = min{s : js > 0}. Покажем, что тогда должновыполняться неравенство sq < sp , противоречащее выбору пакета p.Из всех пакетов, размещенных в узле w, обратим внимание на тот пакет r,которому в последнюю очередь разрешили попасть в узел w; для этого пакета,естественно, выполняется неравенство sq 6 sr . Рассмотрим вектор состоянийhj00 , . .
. , j0k i узла w непосредственно перед приемом пакета r. Так как пакету rбыло разрешено попасть в узел w, это означает, что было соблюдено условие∀i, 0 6 i 6 sr : i < B −kXj0s .s=iПосле приема пакета r некоторые пакеты покинули узел w, и, согласно выбору r,среди них были все те пакеты, которым было разрешено попасть в узел w, послетого как туда поступил пакет r.
Отсюда следуют соотношенияjs 6 j0sjsr 6 j0sr + 1.для s 6= sr ,Но это означает также, что должны выполняться неравенства∀i, 0 6 i 6 sr : i < B −kXs=ijs + 1.185Таким образом, для i = sq должно быть верно неравенствоsq 6 B −kXjs .s=sqТеперь мы воспользуемся тем обстоятельством, что пакету p не было разрешенопродвинуться в узел w, т.
е.∃i0 , 0 6 i0 6 sp − 1 : i0 > B −kXjs .s=i0Это приводит к неравенствуsp > s p − 1> i0kP>B−js>B−>B−> sq ,s=i0kPs=0kPсм. вышесм. вышеjsввиду того, что js > 0 (и i0 > 0)jsввиду того, что js = 0 для s < sqs=sqкоторое и составляет ожидаемое противоречие.Контроллер с состояниями обратного отсчета. Существует также и контроллер, «двойственный» контроллеру с состояниями прямого отсчета, в которомучитывается более подробная информация, нежели в контроллере с обратным отсчетом, и за счет этого разрешается большее количество действий. Будем считать,что запись tp используется в том же качестве, что и ранее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
