Оптимальность интервальной маршрутизации: специальные топологии. 8 глава

 

Все обсужденные методы маршрутизации требуют чтобы решения маршрутизации делались в каждом промежуточном узле, что подразумевает что для маршрута длиной l  происходит l обращений к таблицам маршрутизации. Для стратегий минимального количества шагов l ограничено диаметром сети, но в общем, стратегии маршрутизация без циклов (такие как интервальная маршрутизация) N—1 – лучшая граница которая может быть достигнута. В этом разделе мы обсудим метод с помощью которого табличные поиски могут быть уменьшены.

Мы будем использовать следующую лемму, которая подразумевает существование подходящего разбиения сети на связные кластера.

 

Лемма 4.47 Для каждого s £ N существует разбиение сети на кластера C₁,..., C_m такие что

(1) каждый кластер – связный подграф,

(2) каждый кластер содержит по крайней мере s узлов, и

(3) каждый кластер имеет радиус не более чем 2s.

Доказательство. Пусть D₁,..., Dm будет максимальная коллекция разделенных связных подграфов таких что каждый D_i имеет радиус £ s и содержит по крайней мере s узлов. Каждый узел не принадлежащий  соединен с одним из подмножеств путем длиной не больше чем s, иначе муть может быть добавлен как отдельный кластер. Сформируеи кластеры С_i включением каждого узла не входящего в  в кластер ближайший к нему. Расширенные кластеры остаются содержат по крайней мере s узлов каждый, они остаются связными и разделенными, и они имеют радиус не более чем 2s.          []

 

Метод маршрутизации означивает цветом каждый пакет, и предполагается что используется только несколько цветов. Узлы теперь действуют следующим образом. В зависимости от цвета, пакет или отправляет немедленно по установленному каналу (соответствующему цвету) или вызывает более сложному решению. Это подразумевает, что узлы имеют различные протоколы для обработки пакетов.

Теорема 4.48 [LT86] For каждой сети из N узлов существует метод маршрутизации который требует не более чем 0() решений маршрутизации для каждого пакета, и использует три цвета.

Доказательство. Предположим что решения (по Лемме 4.47) даны и заметим что каждый C_i содержит узел c_i такой что d(v, c_i) £ 2s для каждого v Î C_i  потому что C_i имеет радиус не более чем 2s. Пусть T будет поддеревом минимального размера из G соединяющее все c_i. Так как T минимально то оно содержит не более чем m листьев, следовательно оно содержит не более чем m -2 узлов разветвлений (узлы степенью большей чем 2); см Упражнение 4.9. Рассмотрим узла T как центры (c_i), узлы разветвлений, и узлы пути.

 

Метод маршрутизации сначала посылает пакет к центру c_i кластера источника (зеленая фаза), затем через T к центру c_j кластера пункта назначения (синяя фаза), и наконец внутри C_j к пункту назначения (красная фаза). Зеленая фаза использует фиксированному дерево стока для центра каждого кластера, и не решений маршрутизации. Узлы пути в T имеют два инцидентных канала, и передают каждый синий пакет через канал ыв дереве которые не принимают пакет. Узлы ветвлений и центры в T должны принимать решения маршрутизации. Для красной фазы используется стратегия кротчайшего пути внутри кластера, которая ограничивает число решений в этой фазе до 2s. Это ограничивает число решений маршрутизации до 2 m - 2 + 2 s, что не более чем 2N/s - 2+ 2 s. Выбор s»  дает ограничение 0().                                                  []

 

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

 

Теорема 4.49 [LT86) Для каждой сети из N узелs и каждого положительного целого числа f £ log N существует метод маршрутизации который требует не более чем O(f N^1/f) решений маршрутизации для каждого пакета, и использует  2 f + 1 цветов.

Доказательство. Доказательство подобно доказательству теоремы 4.48, но вместо выбора s»  конструирование применяется рекурсивно к дереву T (оно кластер размера s). Дерево – связная сеть, по существу < 2 m узлов потому что узлы пути в T только перенаправляют пакеты из одного фиксированного канала в другой, и может быть игнорирован.

Кластеризация повторяется f  раз. Сеть G имеет N узлов. Дерево содержит после одного уровня кластеризации не более чем N/s центров и N/s узлов ветвления, т.е., N.(2/s) необходимых узлов. Если дерево полученное после i уровней кластеризации имеет m_i необходимых узлов, тогда дерево полученное после i +1 уровней кластеризации имеет не более чем m_i / s центров и m_i /s узлов ветвлений, т.е., m_i. (2/s) необходимых узлов. Дерево полученное после f уровней кластеризации имеет не более чем m_f = N.(2/s)^f необходимых узлов.

Каждый уровень кластеризации увеличивает количество цветов на два, следовательно с f уровнями кластеризации будут использоваться 2 f +1 цветов. Не более чем 2m _f решений необходимо на самом высоком уровне, и s решений необходимо нв каждом уровне кластеризации в кластере пункта назначения, отсюда количество решений маршрутизации 2m _f + fs. Выбирая s»2N^1/f получим m_f = O(1), следовательно число решений маршрутизации ограничено

f s = O(f N^1/f).               []

 

Использование приблизительно log N цветов приводит к методу маршрутизации которые требуют O(log N) решений маршрутизации.

 

Упражнения к Части 4

Раздел 4.1

Упражнение 4.1 Предположим что таблицы маршрутизации обновляются после каждого топологического изменения таким образом чтобы они были без циклов даже во время обновлений. Дает ли это гарантию что пакеты всегда обработаются даже когда сеть подвергается бесконечному числу топологических изменений? Докажите что алгоритм маршрутизации может гарантировать доставку пакетов при продолжающихся топологических изменениях.

Раздел 4.2

Упражнение 4.2 Студент предложил пренебречь посылкой сообщения

 < nys, w > из алгоритма 4.6; он аргументировал это тем что узел знает своего соседа и не сын в T_w, если нет сообщения < ys,w> принятого от этого соседа. Можно ли модифицировать алгоритм таким образом? Что случиться со сложностью алгоритма?

Упражнение 4.3 Докажите что следующее утверждение является инвариантом алгоритма Чанди-Мизра для вычисления путей до v_o (Алгоритм 4.7).

"u, w: < mydist,v_o,d> Î M_wu Þ  d(w, v_o) £ d

  Ù" u: d(u, v_o) £  D_u[vo]

Дайте пример для которого число сообщений экспоненциально относительно

числа каналов сети.

Раздел 4.3

Упражнение 4.4 Дайте значения всех переменных терминального состояния алгоритма Netchange когда алгоритм применяется к сети со следующей топологией:

После того как терминальное состояние достигнуто, добавляется канал между A и F. Какое сообщение F пошлет к A когда обработает уведомление < repair, A>? Какие сообщения A пошлет после получения сообщений от F?

 

Раздел 4.4

 

Упражнение 4.5 Дайте пример демонстрирующий что Лемма 4.22 не имеет силу для сетей с ассиметричной стоимостью каналов.

Упражнение 4.6 Существует ли ILS которая использует не все каналы для маршрутизации? Она применима? Она оптимальна?

Упражнение 4.7 Дайте граф G и дерево T поиска в глубину графа G такие что G имеет N = n² узлов, диаметр G и глубина T – 0(n), и существуют узлы u и  v такие что пакет от u к  v доставляется за N — 1 переходов схемой ILS поиска в глубину. (Граф может быть выбран таким образом что G непланарный, что предполагает (по Теореме 4.37) что G действительно имеет оптимальную ILS.)

Упражнение 4.8 Дайте схему ILS поиска в глубину для кольца из N узлов. Найдите узлы  u и v такие что d(u, v) = 2, и схема использует N — 2 переходов для передачи пакета от u к v.

Раздел 4.5

Упражнение 4.9 Докажите что минимальность дерева T в доказательстве Теоремы 4.48 предполагает что оно имеет не более чем m листьев. Докажите что любое дерево с m листьями имеет не более чем m — 2 узлов ветвления.

 

 

5 Беступиковая коммутация пакетов

 

Сообщения (пакеты), путешествующие через сеть с коммутацией пакетов должны сохраняться в каждом узле перед тем, отправлением к следующему узлу на пути к адресату. Каждый узел сети для этой цели резервирует некоторый буфер. Поскольку количество буферного места конечно в каждом узле, могут возникнуть ситуации, когда никакой пакет не может быть послан потому, что все буферы в следующем узле заняты, как иллюстрируется Рисунком 5.1. Каждый из четырех узлов имеет буфера B, каждый из которых может содержать точно один пакет. Узел s послал t B пакетов с адресатом v, и узел v послал u B пакетов с адресатом s. Все буфера в u и v теперь заняты, и, следовательно, ни один из пакетов, сохраненных в t и u не может быть послан к адресату.

Ситуации, когда группа пакетов никогда не может достигнуть их адресата, потому что они все ждут буфера, в настоящее время занятого другим пакетом в группе, называются как тупики с промежуточным накоплением. (Другие типы тупика будут кратко рассмотрены в конце этой главы.) Важная проблема в проектировании сетей с пакетной коммутацией - что делать с тупиками с промежуточным накоплением. В этой главе мы разберем несколько методов, называемых контроллерами, которые могут использоваться для того, чтобы избежать возможности тупиков с промежуточным накоплением, вводя ограничения на то, когда пакет может быть сгенерирован или послан. Методы избежания тупиков с промежуточным накоплением найдены в сетевом уровне модели OSI (Подраздел 1.2.2).

Figure 5.1 Пример тупика с промежуточным накоплением.

Два вида методов, которые мы рассмотрим, базируются на структурированных и неструктурированных буферных накопителях.

Методы, использующие структурированные буферные накопители (Раздел 5.2) идентифицируют для узла и пакета специфический буфер, который должен быть использован, если пакет генерируется или принимается. Если этот буфер занят, пакет не может быть принят. В методах, использующих неструктурные буферные накопители (Раздел 5.3) все буфера равны; метод только предписывает, может или нет пакет быть принят, но не определяет, в который буфер он должен быть помещен. Некоторые нотации и определения представляются в Разделе 5.1, и мы закончим главу обсуждением дальнейших проблем в Разделе 5.4.

 

5.1 Введение

Как обычно, сеть моделируется графом G = (V, E); расстояние между узлами измеряется в переходах. Каждая вершина имеет B буферов для временного хранения пакетов. Множество всех буферов обозначается B, и символы b, c, b_u, и т.д., используются для обозначения буферов.

Обработка пакетов узлами описывается с помощью трех типов перемещений, которые могут происходить в сети.

Генерация. Вершина 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, пусть Z_u  обозначает множество состояний вершины u, и M - множество возможных сообщений (пакетов).

Определение 5.1 Контроллер для сети G = (V, E)-набор пар con ={Gen_u, For_u}_{u Î V} , где Gen_u Í Z_u ´ M и For_u Í Z_u ´ M. Если c_u Î Z_u - состояние u, где все буферы пусты, то для всех p Î M, (c _u, p) Î Gen_u.

Контроллер con позволяет генерацию пакета p в вершине u, где состояние u - c_u, тогда и только тогда, когда (c_u, p) Î Gen_u, и позволяет продвижение пакета p из u в w тогда и только тогда, когда (c_w, p) Î For _w. Формальное определение контроллера не включает условия для выведения пакетов, потому что выведение пакета (в его месте назначения) всегда позволено. Передвижения сети под управлением контроллера con - это только те передвижения сети, которые разрешены con.

Пакет в сети в тупике, если он никогда не может достигнуть своего места назначения ни в какой последовательности передвижений.

 

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

Как показывает пример на Рисунке 5.1, тупиковая ситуация существует для всех контроллеров. Задача контроллера в том, чтобы не позволить сети войти в такую конфигурацию. Начальная конфигурация сети - конфигурация, когда в сети нет пакетов.

 

Определение 5.3 Контроллер беступиковый, если под управлением этого контроллера из начальной ситуации не достижима ни одна тупиковая.

5.2 Структурированные решения

Сейчас мы обсудим класс контроллеров, полагающихся на, так называемые, буферные графы, представленные Merlin и Schweitzer [MS80a]. Идея этих буферных графов базируется на наблюдении, что (при отсутствии контроллера) тупик обусловлен ситуацией циклического ожидания. В ситуации циклического ожидания есть последовательность p ₀,..., p _{s -1} пакетов, таких, что для каждого i, p_i хочет передвинуться в буфер, занятый p _i+1 (индексы считаются modulo s). Циклическое ожидание избегается продвижением пакетов вдоль путей в ациклическом графе (буферном графе). В Подразделе 5.2.1 будут определены буферные графы и связанный с ними класс контроллеров, а также представлены два простых примера буферных графов. В подразделе 5.2.2 будет дана более запутанная конструкция буферного графа, снова с двумя примерами.

 

5.2.1 Буферные Графы

Пусть дана сеть G с множеством буферов B.

Определение 5.4 Буферный граф (для G, B ) - направленный граф BG на буферах сети, т.е., BG = ( B ,), так, что

(1) BG - ациклический (не содержит прямых циклов);

(2) Из bc Î  следует, что b и c - буферы одной и той же вершины, или буферы двух вершин, соединенных каналом в G; и

(3) для каждого пути P Î P существует путь в BG, чей образ (см. ниже)-P.

 

Второе требование определяет отображение путей в BG на пути в G; если
b ₀, b ₁,..., b _s - путь в BG, то, если u- вершина, в которой располагается буфер b _i, u₀, u ₁ ,..., u _s - последовательность вершин таких, что для каждого i < s либо u _i u _i+1 Î E, либо u _i = u _i+1. Путь в G, который получается из этой последовательности пропусканием последовательных повторений, называется образом исходного пути b ₀, b ₁,..., b _s в 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 может быть использован для разработки беступикового контроллера bgc _BG, записывающий в каждый пакет буфер nb(p, b) и/или состояние вершины, где располагается p.

 

Определение 5.6 Контроллер bgc _BG определяется следующим образом.

Генерация пакета p в u позволяется тогда и только тогда, когда буфер fb(p) свободен. Сгенерированный пакет помещается в этот буфер.

Продвижение пакета p из буфера в u в буфер в w (возможно u = w) позволяется тогда и только тогда, когда nb(p, b) (в w) свободен. Если продвижение имеет место, то пакет p помещается в nb(p, b).

Theorem 5.7 Контроллер bgc _BG - беступиковый контроллер.

Доказательство. Если у вершины все буферы пусты, генерация любого пакета позволяется, откуда следует, что bgc _BG - контроллер.

Для каждого b Î B, определим класс буфера b как длину самого длинного пути в BG, который заканчивается в b. Заметим, что классы буферов на пути в BG (а точнее, на гарантированном пути) строго возрастающие, т.е., класс буфера nb(p, b) больше, чем класс буфера b.

Т.к. контроллер позволяет размещение пакетов только в подходящих буферах и т.к. изначально нет пакетов, каждая достижимая конфигурация сети под управлением bgc _BG содержит пакеты только в подходящих буферах. С помощью индукции "сверху вниз" по классам буферов можно легко показать, что ни один буфер класса r не содержит в такой конфигурации тупиковых пакетов. Пусть R - самый большой класс буфера.

Случай r = R: Буфер b вершины u, имеющий самый большой из возможных классов, не имеет исходящих ребер в BG. Следовательно, пакет, для которого b - подходящий буфер, имеет пункт назначения u и может быть выведен, когда он попадает в буфер b. Значит, ни один буфер класса R не содержит тупиковых пакетов.

Случай r < R: Выдвинем гипотезу, что для всех r' таких, что r < r' £ R, ни один буфер класса r' не содержит тупиковый пакет (в достижимой конфигурации).
Пусть g - достижимая конфигурация с пакетом p в буфере b класса r < R вершины u. Если u - место назначения p, то p может быть выведен и, следовательно, он не в тупике. Иначе, пусть nb(p, b) = c - следующий буфер на гарантированном пути b, и заметим, что класс r' буфера c превосходит r. По гипотезе индукции, c не содержит тупиковых пакетов, значит существует конфигурация d, достижимая из g, в которой c - пуст. Из d p может продвинуться в c, и, по гипотезе индукции, p не тупиковый в результирующей конфигурации d '. Следовательно, p в конфигурации g не в тупике.

Из доказательства видно, что если гарантированный путь содержит "внутренние" ребра буферного графа (ребра между двумя буферами одной вершины), то контроллер должен позволять дополнительные передвижения, с помощью которых пакет помещается в буфер той же вершины. Обычно гарантированный путь не содержит таких ребер. Они используются только для увеличения эффективности продвижения, например, в следующей ситуации. Пакет p размещается в буфере b ₁ вершины u и буфер nb(p, b ₁ ) в вершине w занят. Но существует свободный буфер b ₂ в u, который подходит для p; более того, nb(p, b ₂) в вершине w свободен. В таком случае, пакет может быть перемещен через b ₂ и nb (p, b ₂).

Сейчас рассмотрим два примера использования буферных графов, а именно, схема адресата(destination scheme) и схема сколько-было-переходов (hops-so-far scheme).

 

Схема адресата. Схема адресата использует N буферов в каждой вершине u, с буфером b_u [ v ] для каждого возможного адресата v. Вершина v называется цель буфера b_u [ v ]. Для этой схемы нужно предположить, что алгоритмы маршрутизации продвигают все пакеты с адресатом v по направленному дереву T _v, ориентированному по направлению к v. (На самом деле это предположение может быть ослаблено; достаточно, чтобы каналы, используемые для продвижения по направлению к v, формировали ациклический подграф G.)

Буферный граф определяется как BG _d = ( B ,), где b_u[v ₁ ]b_w[v ₂ ] Î тогда и только тогда, когда v ₁ = v ₂ и uw - ребро в T _{v 1}. Чтобы показать, что BG _d- ациклический, заметим, что не существует ребер между буферами с различными целями и, что буферы, с одинаковой целью v формируют дерево, изоморфное T _v. Каждый путь P Î P с точкой назначения v - путь в T _v, и по построению существует путь в BG _d из буферов с целью v, чей образ - P. Этот путь выбирается в качества гарантированного. Это означает, что для пакета p с адресатом v, сгенерированного в вершине u, fb(p) = b_u[v], и, если этот пакет должен продвинуться в w, то nb (p, b) = b_w [ v ].

Определение 5.8 Контроллер dest определяется как bgc _BG, с fb и nb определенными как в предыдущем параграфе.

Theorem 5.9 Существует беступиковый контроллер для сети произвольной топологии, который использует N буферов в каждой вершине и позволяет проводить пакеты через произвольно выбранные деревья стока.

Доказательство. dest - беступиковый контроллер, использующий такое количество буферов. ð

 

Как было отмечено ранее, требование маршрутизации по деревьям стока может быть ослаблено до требования того, что пакеты с одинаковыми пунктами назначения посылаются через каналы, которые формируют ациклический граф. Не достаточно, чтобы P содержало только простые пути, как это показано на примере, данном на Рисунке 5.2. Здесь пакеты из u ₁ в v направляются через простой путь
á u ₁, w ₁, u ₂ ,..., v ñ, и пакете из u ₂ в v посылаются через простой путь

Предыдущая12345678910111213141516Следующая

Поделиться:

Воспользуйтесь поиском по сайту: