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

что противоречит выбору 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) обычно несколько буферов определяются как возможное начало или продолжение пути через буферный граф. Если вставка дополнительных буферов выполняется динамически, то буферный граф сначала создается содержащим как можно меньшее количество буферов; буфера в графе мы называем логическими буферами, во время операции каждый фактический буфер (называемый физическим буфером) может использоваться как любой из логических буферов, но всегда должно гарантироваться, что для каждого логического буфера имеется по крайней мере один физический буферный накопитель. При такой схеме, должен быть зарезервировано только небольшое число буферов, чтобы избежать тупиков, в то время как остальная часть буферов может использоваться свободно.

В этой главе было принято, что пакеты имеют фиксированный размер: буфера  одинаково большие и каждый буфер может содержать точно один пакет. Проблему может также рассматривать, предположив, что пакеты могут иметь различные размеры. Решения Раздела 5.3 были адаптированы к этому предположению Bodlaender; см. [Bod86].

5.4.1 Топологические изменения

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

Воздействие этого на методы предотвращения тупиков, рассматриваемые в этой главе довольно не интуитивные. контроллер Dest, чья правильность основана на свойстве, что P содержит только простые пути, может использоваться без каких-либо модификаций. Контроллеры, которые рассматривают только верхнюю границу числа переходов, требуют дополнительных предосторожностей при использовании в этом случае.

Контроллер dest. За конечное время после последнего топологического изменения,  таблицы маршрутизации сводятся к таблицам свободным от циклов. Даже не смотря на то, что ситуация циклического ожидания может существовать во время вычисления таблиц, после завершения вычислений  буферный граф снова становится ациклическим, и все пакеты хранятся в подходящих буферах. Следовательно, когда таблицы маршрутизации вычислены,  возникшая в результате конфигурация не содержит никаких тупиковых пакетов.

Контроллеры, подсчитывающие переходы. Рассмотрим контроллер, который полагается на предположение, что пакет должен делать не больше k переходов. Можно выбрать k достаточно большим, чтобы гарантировать с большой вероятностью, что каждый пакет достигает адресата за k переходов, даже если в течение путешествия от источника до адресата происходят некоторые топологические изменения. Для всех пакетов, которые достигают своих адресатов за k переходов,  контроллеры сколько-было-переходов, с обратным счетом и с отстающим состоянием могут использоваться без какой-либо модификации. Однако, возможно, что пакет не достиг адресата после k переходов из-за неудачного образца топологических изменений и модификаций таблиц. Если дело обстоит так, пакет сохраняется в неподходящем буфере, и он будет навсегда блокирован в узле, отличном от адресата.

Такие ситуации могут быть решены только в кооперации с протоколами более высокого уровня. Самое простое решение в том, чтобы отбросить пакет. С точки зрения сквозного транспортного протокола, пакет теперь потерян; но с этой потерей можно справиться с помощью протокола транспортного уровня, как было показано в Разделе 3.2.

Отбрасывание пакетов также необходимо для выполнения предположения Раздела 3.2 о том, что максимальное время жизни пакета m. Если пересылка пакета занимает не более m0 единиц времени, то из ограничения времени жизни пакета p следует ограничение k =m /m0 на число переходов, которые может пройти пакет.

5.4.2 Другие виды тупиков

В этой главе рассматривались только тупики с промежуточным накоплением. Если предположения, сделанные в Разделе 5.1 имеют силу, тупики с промежуточным накоплением - единственно возможные виды тупиков. В практических сетях, однако, эти предположения не всегда выполняются и, как показали Merlin и Schweitzer [MS80b], возможны другие типы тупиков. Merlin и Schweitzer рассматривают четыре типа, а именно: тупик потомства, тупиком выпуска копии, тупик пошагового продвижения, и тупик перетрансляции, и показывают, как можно избежать эти типы тупиков расширением метода буферных графов.

Тупик потомства может возникнуть, когда пакет p может создать в сети другой пакет q, например, отчет об отказе, если произошло столкновение с испорченным каналом. Это ввело бы причинно-следственные отношение между порождением нового пакета (q) и пересылкой или выведением уже существующего (p), что нарушает предположение Раздела 5.1, что сеть всегда позволяет пересылку и выведение пакета.

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

Тупик выпуска копии может возникнуть, когда источник задерживает копию пакета, пока для пакета не получено (сквозное) подтверждение от адресата. (Сравните с протоколом основанном на таймере из Раздела 3.2, и предположите, что последовательность inp хранится в том же самом пространстве памяти, которое используется механизмом маршрутизации для временного хранения пакетов.) Это нарушает наше предположение (в Разделе 5.1), что буфер становится пустым, когда пакет, занимающий его, продвигается.

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

Тупик пошагового продвижения может возникнуть, когда сеть содержит узлы с ограниченной внутренней памятью, которые могут отказываться выводить сообщения, пока некоторые другие сообщения не были сгенерированы. Например, терминал телетайпа должен вывести некоторые символы прежде, чем он сможет принимать следующие символы для отображения. Это нарушает наше предположение, что пакет в адресате всегда может быть выведен.

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

Тупик перетрансляции может возникнуть в сетях, где большие сообщения для передачи разделяются на более мелкие пакеты, и ни один пакет не может быть удален из сети, пока все пакеты сообщения не достигли адресата. (Сравните с протоколом скользящего окна Раздела 3.1, где слова удаляются из outp только если были получены все слова с меньшим индексом.) Это нарушает наше предположение, что выведение пакета в адресате всегда возможно.

Тупиков перетрансляции можно избежать,  используя отдельные группы буферов для пересылки пакета и перетрансляции.

5.4.3 Лайфлок (livelock)

Из определения тупиковых пакетов (Определение 5.2) следует, что под управлением беступикового контроллера для каждого пакета существует по крайней мере одно вычисление, в котором пакет выводится. Т.к. в общем случае возможно большое количество различных вычислений, то это из этого не следует, что каждый пакет в конечном счете доходит до адресата, даже в бесконечном вычислении, как иллюстрируется Рисунок 5.6. Предположим, что u посылает в v бесконечный поток пакетов, и каждый раз, как только буфер в w становится пустым, принимается следующий пакет из u. Узел s имеет пакет для t, который не заходит в тупик, потому что каждый раз, когда буфер в w становится пустым, имеется возможное продолжение вычисления, в котором пакет принимается вершиной w и посылается к t. Это возможно, но не обязательно, и пакет может остаться в s навсегда. Ситуация этого вида называется лайфлок.

Контроллер, обсуждаемый в этой главе, может быть расширен так, чтобы вообще избежать лайфлоков.

Определение 5.23 Дана сеть, контроллер con, и конфигурация g, пакет p заблокирован (лайфлок), если существует бесконечная последовательность передвижений, применимых в g, в результате которых p не выводится. Конфигурация g - конфигурация лайфлока, если она содержит заблокированные пакеты.

Рисунок 5.6 Пример лайфлока.

Контроллер свободен от лайфлока, если ни одна конфигурация лайфлока не достижима из конфигурации, в которой нет пакетов.

В оставшейся части этого подраздела будет доказана свобода контроллера буферных графов от лайфлока;  в конце будут упомянуты расширения неструктурированных решений.

Страницы: 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