Распределенные алгоритмы (стр. 37 из 85)
Figure 5.1 Пример тупика с промежуточным накоплением.
Два вида методов, которые мы рассмотрим, базируются на структурированных и неструктурированных буферных накопителях.
Методы, использующие структурированные буферные накопители (Раздел 5.2) идентифицируют для узла и пакета специфический буфер, который должен быть использован, если пакет генерируется или принимается. Если этот буфер занят, пакет не может быть принят. В методах, использующих неструктурные буферные накопители (Раздел 5.3) все буфера равны; метод только предписывает, может или нет пакет быть принят, но не определяет, в который буфер он должен быть помещен. Некоторые нотации и определения представляются в Разделе 5.1, и мы закончим главу обсуждением дальнейших проблем в Разделе 5.4.
Как обычно, сеть моделируется графом G = (V, E); расстояние между узлами измеряется в переходах. Каждая вершина имеет B буферов для временного хранения пакетов. Множество всех буферов обозначается B, и символы b, c, bu, и т.д., используются для обозначения буферов.
Обработка пакетов узлами описывается с помощью трех типов перемещений, которые могут происходить в сети.
Генерация. Вершина u "создает" новый пакет p (на самом деле, принимая пакет от протокола более высокого уровня) и размещает его в пустом буфере в u. Вершина u в таком случае называется источником пакета p.
Продвижение. Пакет p продвигается от вершины u в пустой буфер следующей в его маршруте вершины w (маршрут определяется, используя алгоритмы маршрутизации). В результате передвижения буфер, прежде занятый p становится пустым. Хотя контроллеры, которые мы определим, могут запретить передвижения, предполагается, что сеть всегда позволяет это движение, т.е., если контроллер его не запрещает, то оно применимо.
В системах с синхронной передачей сообщений это перемещение, как легко видно, является одиночным переходом, как в Определении 2.7. В системах с асинхронной передачей сообщений, перемещение - не один переход, как в Определении 2.6, но оно может быть выполнено, например, следующим образом. Узел u неоднократно передает p к w, но не отбрасывает пакет из буфера, пока не получено подтверждение. Когда узел w получает пакет, он решает, примет ли он пакет в одном из буферов. Если примет, пакет помещается в буфер, и посылается подтверждение u, иначе пакет просто игнорируется. Конечно, могут быть разработаны более эффективные протоколы для выполнения таких перемещений, например те, где u не передает p, пока u не уверен, что w примет p. В любом случае перемещение состоит из нескольких переходов типа упомянутых в Определении 2.6, но в целях этой главы оно будет рассматриваться как одиночный шаг.
(3) Выведение. Пакет p, занимающий буфер в вершине назначения, удаляется из буфера. Предполагается, что сеть всегда позволяет это передвижение.
Обозначим через P множество всех путей, по которым следуют пакеты. Это множество определяется алгоритмами маршрутизации (см. Главу 4); как это делается, нас здесь не интересует. Пусть k - количество переходов в самом длинном пути в P. Это не предполагает, что k равен диаметру G; k может превосходить диаметр, если алгоритм маршрутизации не выбирает кратчайшие пути, и k может быть меньше диаметра, если все коммуникации между узлами происходят на ограниченных дистанциях.
Как видно из примера, данного в начале этой главы, тупики могут возникнуть, если разрешены произвольные перемещения (исключая тривиальное ограничение, что u должна иметь пустой буфер, если в u генерируется пакет и w должна иметь пустой буфер, если пакет продвигается в w). Теперь мы определим контроллер как алгоритм, разрешающий или запрещающий различные движения в сети в соответствии со следующими требованиями.
(1) Выведение пакета (в месте его назначения) всегда позволяется.
(2) Генерация пакета в вершине, в которой все буферы пустые, всегда позволяется.
(3) Контроллер использует только локальную информацию, т.е., решение, может ли пакет быть принят в вершине u, зависит только от информации, известной u или содержащейся в пакете.
Второе требование исключает тривиальное решение избежания заблокированных пакетов (см. Определение 5.2), отказываясь принимать какие-либо пакеты в сети. Как в Главе 2, пусть Zu обозначает множество состояний вершины u, и M - множество возможных сообщений (пакетов).
Определение 5.1 Контроллер для сети G = (V, E)-набор пар con={Genu, Foru}uÎ V , где Genu Í Zu ´ M и Foru Í Zu ´ M. Если cu Î Zu - состояние u, где все буферы пусты, то для всех p Î M, (cu, p) Î Genu.
Контроллер con позволяет генерацию пакета p в вершине u, где состояние u - cu, тогда и только тогда, когда (cu, p) Î Genu, и позволяет продвижение пакета p из u в w тогда и только тогда, когда (cw, p) Î Forw. Формальное определение контроллера не включает условия для выведения пакетов, потому что выведение пакета (в его месте назначения) всегда позволено. Передвижения сети под управлением контроллера con - это только те передвижения сети, которые разрешены con.
Пакет в сети в тупике, если он никогда не может достигнуть своего места назначения ни в какой последовательности передвижений.
Определение 5.2 Дана сеть G, контроллер con для G, и конфигурация g G, пакет p (возникающий в конфигурации g) в тупике, если не существует последовательности передвижений под управлением con, применимой в g, в которой p выводится. Конфигурация называется тупиковой, если она содержит пакеты в тупике.
Как показывает пример на Рисунке 5.1, тупиковая ситуация существует для всех контроллеров. Задача контроллера в том, чтобы не позволить сети войти в такую конфигурацию. Начальная конфигурация сети - конфигурация, когда в сети нет пакетов.
Определение 5.3 Контроллер беступиковый, если под управлением этого контроллера из начальной ситуации не достижима ни одна тупиковая.
Сейчас мы обсудим класс контроллеров, полагающихся на, так называемые, буферные графы, представленные Merlin и Schweitzer [MS80a]. Идея этих буферных графов базируется на наблюдении, что (при отсутствии контроллера) тупик обусловлен ситуацией циклического ожидания. В ситуации циклического ожидания есть последовательность p0, ..., ps -1 пакетов, таких, что для каждого i, pi хочет передвинуться в буфер, занятый pi+1 (индексы считаются modulo s). Циклическое ожидание избегается продвижением пакетов вдоль путей в ациклическом графе (буферном графе). В Подразделе 5.2.1 будут определены буферные графы и связанный с ними класс контроллеров, а также представлены два простых примера буферных графов. В подразделе 5.2.2 будет дана более запутанная конструкция буферного графа, снова с двумя примерами.
Пусть дана сеть G с множеством буферов B.
Определение 5.4 Буферный граф (для G, B) - направленный граф BG на буферах сети, т.е., BG = (B, ), так, что
(1) BG - ациклический (не содержит прямых циклов);
(2) Из bc Î следует, что b и c - буферы одной и той же вершины, или буферы двух вершин, соединенных каналом в G; и
(3) для каждого пути P Î P существует путь в BG, чей образ (см. ниже)-P.
Второе требование определяет отображение путей в BG на пути в G; если
b0, b1, ..., bs - путь в BG, то, если u- вершина, в которой располагается буфер bi, u0, u1,..., us - последовательность вершин таких, что для каждого i < s либо uiui+1 Î E, либо ui = ui+1. Путь в G, который получается из этой последовательности пропусканием последовательных повторений, называется образом исходного пути b0, b1,..., bs в BG.
Пакет не может быть помещен в произвольно выбранный буфер; он должен быть помещен в буфер, из которого он еще может достигнуть своего места назначения через путь в BG, т.е., буфер, подходящий для пакета в соответствии с определением.
Определение 5.5 Пусть p - пакет в вершине u с пунктом назначения v. Буфер b в u подходит для p, если существует путь в BG из b в буфер c в v, чей образ - путь, которому p может следовать в G.
Один из таких путей в BG будет называться гарантированным путем и nb(p, b) обозначает следующий буфер на гарантированном пути. Для каждого вновь сгенерированного пакета p в u Существует подходящий буфер fb(p) в u.
Здесь fb и nb - аббревиатура первого буфера (first buffer) и следующего буфера (next buffer). Заметим, что буфер nb(p, b) всегда подходит для p. Во всех буферных графов, используемых в этом разделе, nb(p, b) располагается в вершине, отличной от той, где располагается b. Использование "внутренних" ребер в BG, т.е., ребер между двумя буферами одной вершины, обсудим позже.
Контроллер буферного графа. Буферный граф BG может быть использован для разработки беступикового контроллера bgcBG , записывающий в каждый пакет буфер nb(p, b) и/или состояние вершины, где располагается p.