Реферат: Распределенные алгоритмы

Контроллер принимает пакет, если пустых буферов в вершине больше, чем количество переходов, которые нужно сделать пакету.

Теорема 5.17 Если B > k, то FC - беступиковый контроллер.

Доказательство. Чтобы показать, что в пустой вершине позволяется генерация пакета, заметим, что если все буферы вершины u пусты, fu = B. Новому пакету нужно сделать не более k переходов, так что из B > k следует, что пакет принимается.

Отсутствие тупиков FC будет показано методом от противного: пусть g - достижимая конфигурация контроллера. Получим конфигурацию d , применяя к g максимальную последовательность из передвижений и выведения. В d ни один пакет не может двигаться, и, т.к. g - тупиковая конфигурация, то существует по крайней мере один пакет, оставшийся в сети в конфигурации. Пусть p - пакет в d с минимальным расстоянием до пункта назначения, т.е., sp - наименьшее значение для всех пакетов в d.

Пусть u - вершина, в которой размещается p. Т.к. u не является пунктом назначения p (иначе p мог бы быть выведен), то существует сосед w вершины u , в которую нужно продвинуть p. Т. к. это передвижение не позволяется FC, то

sp-1³ fw

Из sp£ k и из предположения k < B следует, что fu < B, что обозначает, что в вершине w располагается как минимум один пакет (в конфигурации d ). Из пакетов в w, пусть q будет последним пакетом, принятым вершиной w, и пусть f'w обозначает количество пустых буферов в w прямо перед принятием q вершиной w. Т.к. пакет q теперь занимает один из этих f'w  буферов и (из выбора q) все пакеты, принятые вершиной w после q были выведены из w, то

f'w £ fw +1

Из принятие  q вершиной w следует sq < f'w, и, комбинируя три полученных неравенства, получаем

sq < f'w £ fw +1£ sp,

что противоречит выбору p.                                       ÿ

Контроллер с обратным счетом (backward-count controller). Контроллер, " двойственный " FC , получается, когда решение, принимать ли пакет, основано на количестве шагов, которые пакет уже сделал. Пусть, для пакета p, tp - количество переходов, которые он сделал от источника. Конечно, 0 £ tp < k всегда верно.

Определение 5.18 Контроллер BC (Backward-Count) принимает пакет p в вершине u тогда и только тогда, когда tp > k—fu.

Доказательство того, что BC - беступиковый (Упражнение 5.6) очень похоже на доказательство  Теоремы 5.17.

5.3.2 Контроллеры с опережающим и отстающим состоянием

Используя более детальную информацию относительно пакетов, находящихся в узле, может быть дан контроллер, который подобен контроллеру с прямым счетом, но позволяет большое количество передвижений.

Контроллер с опережающим состоянием (forward-state controller). Используем обозначение sp как в предыдущем разделе. Для вершины u определим (как функцию состояния u) вектор состояния , где j - количество пакетов p в u с sp = s.

Определение 5.19 Контроллер FS (Forward-State) принимает пакет p в вершине u с вектором состояния  тогда и только тогда, когда

.

Теорема 5.20 Если B > k, то FS - беступиковый.

Доказательство. Оставляем читателю показать, что пустая вершина принимает все пакеты. Предположим, что существует достижимая тупиковая конфигурация g, и получим конфигурацию d , применяя максимальную последовательность из продвижений и выведения. Ни один пакет не может передвигаться и по крайней мере один пакет остался в d. Выберем пакет p с минимальным значением sp, и пусть u -вершина, в которой располагается p и  w - вершина, в которую p должен продвинуться. Пусть  - вектор состояния вершины w в d.

Если w не содержит пакетом, то , откуда следует, что w может принять p, что невозможно. Следовательно, w содержит по крайней мере один пакет; из пакетов в w, пусть q - пакет, расположенный ближе всего к пункту назначения, т.е., sq = min{s : js > 0}. Покажем, что sq < sp, что является противоречием. Из пакетов в w, пусть r - тот, который был принят w позже всех, конечно, sq £ sr выполняется. Пусть  - вектор состояния w прямо перед принятием r. Из принятия r следует

Когда  был вектором состояния w, r был принят вершиной w. После этого пакеты могли передвигаться из w, но все пакеты, принятые в w позже, чем r были выведены (из выбора r). Из этого следует

Но это означает, что

Таким образом, принимая i = sq,

Теперь используем факт, что p не принята w, т.е.,

Это дает неравенство

sp>sp-1

что и является противоречием.                                    ð

Контроллер с отстающим состоянием (backward-state controller.) Существует также и контроллер, "двойственный" FS, который использует более детальную информацию, чем контроллер BC, и позволяет больше передвижений. Пусть tp выбрано как раньше, и определим вектор состояния как , где  it равно количеству пакетов в вершине u , которые сделали t переходов.

Определение 5.21 Контроллер BS (Backward-State) принимает пакет p в вершине u с вектором состояния  тогда и только тогда, когда

Доказательство того, что BS беступиковый очень похоже на доказательство Теоремы 5.20.

Сравнение контроллеров. Контроллер с опережающим состоянием более либеральный, чем контроллер с прямым счетом, в том плане, что он позволяет больше передвижений:

Лемма 5.22 Каждое передвижение, позволяемое FC также позволяется FS.

Доказательство. Предположим, что принятие p вершиной u позвляется контроллером FC. Тогда , так что для  i£ sp ,следует , откуда видно, что FS позволяет передвижение.                                            D

В [TU81] было показано, что FC более либеральный, чем BC. FS - более либеральный, чем BS, и BS более либеральный, чем BC. Также было показано, что эти контроллеры самые либеральные из всех, использующих такую же информацию.

5.4 Дальнейшие проблемы

В результатах этой главы отметим, что число буферов, необходимых контроллеру, всегда играло большую роль. Пропускная способность обычно увеличивается, если доступно большое количество буферов. В неструктурированных решениях дано только нижняя граница числа буферов; большее число может использоваться без любой модификации. В структурированных решениях дополнительные буфера должны так или иначе быть вставлены в буферный граф, что может быть выполнено или статически или динамически. Если это выполнено статически, каждый буфер имеет фиксированное расположение в буферном графе, т.е., создается  "более широкий" буферный граф, чем в примерах, приведенных в Разделе 5.2.

Вместо одного буфера fb (p) или nb (p, b) обычно несколько буферов определяются как возможное начало или продолжение пути через буферный граф. Если вставка дополнительных буферов выполняется динамически, то буферный граф сначала создается содержащим как можно меньшее количество буферов; буфера в графе мы называем логическими буферами, во время операции каждый фактический буфер (называемый физическим буфером) может использоваться как любой из логических буферов, но всегда должно гарантироваться, что для каждого логического буфера имеется по крайней мере один физический буферный накопитель. При такой схеме, должен быть зарезервировано только небольшое число буферов, чтобы избежать тупиков, в то время как остальная часть буферов может использоваться свободно.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105