Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 49
Текст из файла (страница 49)
Ему удалось построить класс сетей, для которых существует беступиковая оптимальнаямаршрутизация, требующая фиксированного постоянного числа буферов в каждом узле, но при этом наилучшему оптимальному АОС-контроллеру требуетсяиметь fi(lgA /lglgA ) буферов в каждом узле. До сих пор неизвестно, наскольковелик разрыв между наилучшим АОС-контроллером и наилучшим контроллеромобщего вида.Гл. 5. Неблокируемая коммутация пакетов182Можно ли задавать пути, которые используются АОС-контроллерами, припомощи компактных схем маршрутизации, наподобие интервальной маршрутизации? Для гиперкуба удалось установить, что 1) существует оптимальная схемаинтервальной разметки, 2 ) существует контроллер, которому для использованияоптимальных путей требуется иметь 2 буфера в каждом узле, но при этом 3) неттаких АОС-контроллеров, которые можно было бы так встроить в схему интервальной разметки, чтобы они могли ограничиться использованием только двухбуферов в каждом узле.
Исследования в этом направлении еще продолжаются.5.3. Неструктурированные решенияТеперь мы обратимся к классу контроллеров, предложенных Туэгом и Ульманом в работе [196]. Эти контроллеры не выдают предписаний, в какой буферследует поместить тот или иной пакет, и используют только простую локальнуюинформацию, наподобие счетчика шагов или числа буферов, занятых в узле.5.3.1. Контроллеры с прямым и обратным отсчетомКонтроллер с прямым отсчетом. Условимся, что для всякого пакета р запись sp будет обозначать число продвижений, которые необходимо совершитьпакету, чтобы достичь адресата; естественно, что 0 ^ sp ^ k.
Бывает так, чтозначение sp не нужно передавать вместе с пакетом, поскольку многие алгоритмы вычисляют эти данные в каждом узле (см., например, алгоритм Netchange,описанный в §4.6.3). Условимся также, что для каждого узла и запись / ц будет обозначать количество свободных буферов узла и. Естественно, что всегдавыполняется неравенство 0 ^ / ц ^ В.Определение 5.16. Контроллер с прямым отсчетом FC разрешает узлуи принять пакет р в том и только том случае, когда выполняется неравенствоSp<fa-Контроллер разрешает прием пакета, если в узле имеется больше свободныхбуферов, чем число продвижений, которые необходимо совершить пакету.Теорема 5.17. Если В > k, то контроллер FC является беступиковым.Д о к а з а т е л ь с т в о . Чтобы убедиться в том, что пакет разрешается сформировать в пустом узле, обратим внимание на то, что если все буферы узла ипусты, то f u = В.
Новому пакету предстоит совершить не более k продвижений,и, вследствие того что В > k, этот пакет допускается в узле и.Беступиковость контроллера FC будет доказана от противного; Допустим, чтоу — это достижимая тупиковая конфигурация контроллера. Теперь рассмотримконфигурацию 8, которая получается из конфигурации у путем применения максимальной последовательности действий продвижения и поглощения пакетов.
Вконфигурации 8 не может быть продвинут ни один пакет, но, ввиду того что конфигурация у является предположительно тупиковой, в конфигурации 8 остаетсяхотя бы один пакет. Рассмотрим пакет р, который в конфигурации 8 расположен5.3. Неструктурированные решения183ближе всего к своему узлу-адресату, т. е. пакет, имеющий наименьшее значениесчетчика sp среди всех пакетов, оставшихся в конфигурации 8 .Обратимся к узлу и, в котором расположен пакет р. Так как узел и не являетсяадресатом пакета р (иначе он был бы поглощен в конфигурации 8 ), существуеттакой сосед да узла и, которому должен быть передан пакет р.
Коль скоро FC неразрешает выполнить это действие, имеет место неравенствоSp—1 ^fwПоскольку sp ^ k и при этом, согласно сделанному предположению, k < В,отсюда следует неравенство f w < В , которое означает, что в конфигурации 8хотя бы один пакет расположен в вершине да.
Из всех пакетов, размещенныхв узле да, выберем тот пакет q, который прибыл в узел да самым последним, ирассмотрим число свободных буферов f'w в узле да непосредственно перед тем,как пакету q было разрешено переместиться в узел да. Ввиду того что пакет qзанимает один из этих f'w буферов, и коль скоро, (в силу выбора этого пакета)все пакеты, попавшие в узел да после q, впоследствии были удалены из узла да,должно выполняться неравенство f'w ^ f w + 1 .Так как пакету q было разрешено переместиться в узел да, справедливо неравенство sq < f'w .
Сопоставив все четыре полученных нами неравенства, приходимк соотношениюSq С f w ^ fw Т 1 ^ S p ,которое противоречит выбору р.□Контроллер с обратным отсчетом. Чтобы построить контроллер, «двойственный» FC, разрешение на прием пакета нужно выдавать на основании числашагов, пройденных этим пакетом.
Условимся, что для всякого пакета р записьtp будет обозначать число продвижений, которые уже удалось совершить пакету.Естественно, что всегда верно неравенство 0 ^ tp ^ k.Определение 5.18. Контроллер с обратным отсчетом ВС разрешаетузлу и принять пакет р в том и только том случае, когда выполняется неравенствоtp>k-fa.Доказательство утверждения о том, что контроллер ВС является беступиковым (упражнение 5.6), аналогично доказательству теоремы 5.17.5.3.2.
Контроллеры с состояниями прямого и обратногоотсчетаВоспользовавшись более подробной информацией о пакетах, хранящихся вузле, можно построить контроллер, который функционирует почти так же, каки контроллер с прямым отсчетом, но разрешает при этом совершать большедействий.Контроллер с состояниями прямого отсчета.
Запись sp будет обозначатьто же самое, что и в предыдущем параграфе. Для узла и определим (как функцию184Гл. 5. Неблокируемая коммутация пакетовсостояния процесса и) целочисленный вектор состояния (/'о,Д), где Д —количество пакетов р, размещенных в узле и и удовлетворяющих условию sp = s.Определение 5.19. Контроллер с состояниями прямого отсчета FSразрешает прием пакета р в узле и, имеющем вектор состояния (Д, . .
. . Д), тогдаи только тогда, когда выполняется соотношениеkТеорема 5.20. ЕслиВ> k, то контроллер FS является беступиковым.Д о к а з а т е л ь с т в о . Читателю предоставляется возможность самостоятельно убедиться в том, что пустому узлу разрешается принять любой пакет. Д опустим, что существует достижимая тупиковая конфигурация у. Теперь рассмотрим конфигурацию 8 , которая получается из конфигурации у путем применениямаксимальной последовательности действий продвижения и поглощения пакетов.В конфигурации 8 есть хотя бы один пакет, но при этом ни один пакет не можетбыть перемещен. Выберем пакет р с наименьшим значением характеристики sp;предположим, что пакет р размещен в узле и и должен быть продвинут в узел да.Рассмотрим вектор состояний (/о, .
. . . Д) узла да в конфигурации 8 .Если в узле да нет пакетов, то J2s=oh = 0, и отсюда следует, что узлу даразрешается принять пакет р, что противоречит выбору конфигурации 8 . Значит,в узле да есть хотя бы один пакет. Из всех пакетов, размещенных в узле да,рассмотрим тот пакет q, который находится ближе всего к своему узлу-адресату,т. е.
удовлетворяет условию s q = min{s: Д > 0}. Покажем, что тогда должновыполняться неравенство s q < s p , противоречащее выбору пакета р.Из всех пакетов, размещенных в узле да, обратим внимание на тот пакет г,которому в последнюю очередь разрешили попасть в узел да; для этого пакета,естественно, выполняется неравенство s q Д s r.
Рассмотрим вектор состояний(/о> • • •, j'k ) узла да непосредственно перед приемом пакета г. Так как пакету гбыло разрешено попасть в узел да, это означает, что было соблюдено условиеkV/, 0 Д i Д sr: i < В -Д.s= iПосле приема пакета г некоторые пакеты покинули узел да, и, согласно выбору г,среди них были все те пакеты, которым было разрешено попасть в узел да, послетого как туда поступил пакет г. Отсюда следуют соотношенияДЛЯS фSr,Но это означает также, что должны выполняться неравенстваkV/, 0 ф i ф sr: i < В —’^ j js + 1.s= i5.3. Неструктурированные решения185Таким образом, для / = sq должно быть верно неравенствоkSqSs Вjs-—s=sqТеперь мы воспользуемся тем обстоятельством, что пакету р не было разрешенопродвинуться в узел да, т. е.k3 /0 , 0</о< sp - 1 :/о >В - ^ js s=ioЭто приводит к неравенствуSp> Sp — 1см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
