Маршрутизация противодавления

В теории массового обслуживания , дисциплине в рамках математической теории вероятностей , алгоритм маршрутизации с обратным давлением представляет собой метод направления трафика вокруг сети массового обслуживания, который обеспечивает максимальную пропускную способность сети ^[1], которая устанавливается с использованием концепций смещения Ляпунова . Маршрутизация противодавления рассматривает ситуацию, когда каждое задание может посещать несколько сервисных узлов в сети. Это расширение расписания с максимальным весом, когда каждое задание посещает только один сервисный узел.

Введение [ править ]

Маршрутизация с обратным давлением - это алгоритм динамической маршрутизации трафика по многозвенной сети с использованием градиентов перегрузки. Алгоритм может применяться к сетям беспроводной связи, включая сенсорные сети , мобильные одноранговые сети ( MANETS ) и гетерогенные сети с беспроводными и проводными компонентами. ^{[2] [3]}

Принципы противодавления также могут применяться в других областях, например, при исследовании систем сборки изделий и технологических сетей. ^[4] Эта статья посвящена сетям связи, в которые поступают пакеты из нескольких потоков данных и должны быть доставлены в соответствующие пункты назначения. Алгоритм противодавления работает в интервале времени. Каждый временной интервал он пытается направить данные в направлениях, которые максимизируют дифференциальное отставание.между соседними узлами. Это похоже на то, как вода течет по сети труб через градиенты давления. Однако алгоритм противодавления может применяться к многопрофильным сетям (где разные пакеты могут иметь разные места назначения) и к сетям, где скорость передачи может быть выбрана из набора (возможно, изменяющихся во времени) опций. Привлекательными особенностями алгоритма противодавления являются: (i) он приводит к максимальной пропускной способности сети, (ii) он доказуемо устойчив к изменяющимся во времени условиям сети, (iii) он может быть реализован без знания скорости поступления трафика или вероятностей состояния канала. Однако алгоритм может вызвать большие задержки, и его может быть трудно реализовать точно в сетях с помехами. Модификации противодавления, которые уменьшают задержку и упрощают реализацию, описаны ниже в разделеУлучшение задержки и распределенного противодавления .

Маршрутизация противодавления в основном изучалась в теоретическом контексте. На практике специальные беспроводные сети обычно реализуют альтернативные методы маршрутизации, основанные на вычислениях кратчайшего пути или лавинной сети, такие как прямая векторная дистанционная маршрутизация по требованию (AODV), географическая маршрутизация и чрезвычайно гибкая маршрутизация (ExOR). Однако свойства математической оптимальности противодавления послужили причиной недавних экспериментальных демонстраций его использования на беспроводных испытательных стендах в Университете Южной Калифорнии и Университете штата Северная Каролина. ^{[5] [6] [7]}

Истоки [ править ]

Первоначальный алгоритм противодавления был разработан Тассиулас и Ефремидес. ^[2] Они рассмотрели многозвенную пакетную радиосеть со случайным поступлением пакетов и фиксированным набором опций выбора канала. Их алгоритм состоял из этапа выбора канала с максимальным весом и этапа дифференциальной маршрутизации невыполненных запросов . Алгоритм, связанный с противодавлением, предназначенный для вычисления потоков в сети с несколькими товарами, был разработан в Awerbuch и Leighton. ^[8] Алгоритм противодавления был позже расширен Нили, Модиано и Рорсом для обработки расписания для мобильных сетей. ^[9] Противодавление математически анализируется с помощью теории Ляпуновского дрейфа., и может использоваться совместно с механизмами управления потоком для обеспечения максимальной полезности сети. ^{[10] [11] [3] [12] [13]} (см. Также Обратное давление с оптимизацией утилит и минимизацией штрафов ).

Как это работает [ править ]

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

Модель сети с многозвенной очередью [ править ]

Рассмотрим многоскачковую сеть с N узлами (см. Рис. 1 для примера с N  = 6). Сеть работает в установленное время . В каждом слоте новые данные могут поступать в сеть, и решения о маршрутизации и планировании передачи принимаются в попытке доставить все данные в надлежащее место назначения. Пусть данные, предназначенные для узла, будут помечены как данные о товаре c . Данные в каждом узле хранятся в соответствии с его товаром. Для и пусть будет текущий объем данных о товаре c в узле n , также называемый невыполненной работой очереди . Крупный план незавершенных очередей внутри узла показан на рис. 2. Единицы${\ Displaystyle т \ в \ {0,1,2, \ ldots \}}$${\ Displaystyle с \ в \ {1, \ точки, N \}}$${\ Displaystyle п \ в \ {1, \ ldots, N \}}$${\ Displaystyle с \ в \ {1, \ ldots, N \}}$${\ Displaystyle Q_ {п} ^ {(с)} (т)}$${\ Displaystyle Q_ {п} ^ {(с)} (т)}$зависят от контекста проблемы. Например, невыполненная работа может принимать целые единицы пакетов , что полезно в случаях, когда данные сегментируются на пакеты фиксированной длины. В качестве альтернативы он может принимать единицы битов с действительным знаком . Предполагается, что для всех и всех временных интервалов t , поскольку ни один узел не хранит данные, предназначенные для себя. В каждом временном интервале узлы могут передавать данные другим. Данные, которые передаются от одного узла к другому, удаляются из очереди первого узла и добавляются в очередь второго. Данные, которые передаются по назначению, удаляются из сети. Данные также могут поступать в сеть экзогенно и определяется как количество новых данных, которые поступают в узел n.${\ Displaystyle Q_ {с} ^ {(с)} (т) = 0}$${\ Displaystyle с \ в \ {1, \ ldots, N \}}$${\ Displaystyle А_ {п} ^ {(с)} (т)}$на слоте t, который в конечном итоге должен быть доставлен на узел c .

Пусть будет скорость передачи, используемая сетью по каналу ( a , b ) в слоте t , представляющая объем данных, которые она может передать от узла a к узлу b в текущем слоте. Позвольте быть матрице скорости передачи. Эти скорости передачи должны выбираться из набора возможных вариантов, изменяющихся во времени. В частности, сеть может иметь изменяющиеся во времени каналы и мобильность узлов, и это может влиять на ее возможности передачи в каждом временном интервале. Чтобы смоделировать это, пусть S ( t ) представляет состояние топологии сети, которое фиксирует свойства сети в слоте t.${\ Displaystyle \ му _ {ab} (т)}$${\ Displaystyle (\ му _ {ab} (т))}$которые влияют на передачу. Позвольте представить набор опций матрицы скорости передачи, доступных в состоянии топологии S ( t ). Каждый слот t сетевой контроллер наблюдает за S ( t ) и выбирает скорости передачи из набора . Выбор матрицы для выбора в каждом слоте t описан в следующем подразделе.${\ displaystyle \ Gamma _ {S (t)}}$${\ Displaystyle (\ му _ {ab} (т))}$${\ displaystyle \ Gamma _ {S (t)}}$${\ Displaystyle (\ му _ {ab} (т))}$

Эта изменяющаяся во времени сетевая модель была впервые разработана для случая, когда скорости передачи в каждом временном интервале t определялись общими функциями матрицы состояния канала и матрицы распределения мощности. ^[9] Модель также может использоваться, когда скорости определяются другими решениями управления, такими как выделение сервера, выбор поддиапазона, тип кодирования и так далее. Предполагается, что поддерживаемые скорости передачи известны и ошибок передачи нет. Расширенные формулировки маршрутизации противодавления могут использоваться для сетей с вероятными ошибками канала, включая сети, которые используют преимущество беспроводного вещания через разнесение множества приемников . ^[1]

Решения по контролю противодавления [ править ]

Каждый слот t контроллер противодавления наблюдает за S ( t ) и выполняет следующие 3 шага:

• Во-первых, для каждой ссылки ( a , b ) он выбирает оптимальный товар для использования.${\ displaystyle c_ {ab} ^ {opt} (t)}$
• Затем он определяет, какую матрицу использовать.${\ Displaystyle (\ му _ {ab} (т))}$${\ displaystyle \ Gamma _ {S (t)}}$
• Наконец, он определяет количество товара, которое он будет передавать по ссылке ( a , b ) (максимум , но в некоторых случаях, возможно, меньше).${\ displaystyle c_ {ab} ^ {opt} (t)}$${\ Displaystyle \ му _ {ab} (т)}$

Выбор оптимального товара [ править ]

Каждый узел a наблюдает за своими собственными невыполненными заданиями в очереди и за своими текущими соседями. Тока сосед из узла A является узлом B таким образом, что можно выбрать скорость передачи ненулевой на текущем слоте. Таким образом, соседи определяются набором . В крайнем случае, узел может иметь все N  - 1 других узлов в качестве соседей. Однако обычно используются наборы, которые исключают передачи между узлами, которые разделены большим, чем определенное географическое расстояние, или которые имеют мощность распространяемого сигнала ниже определенного порога. Таким образом, количество соседей обычно намного меньше N${\ Displaystyle \ му _ {ab} (т)}$${\ displaystyle \ Gamma _ {S (t)}}$${\ displaystyle \ Gamma _ {S (t)}}$ - 1. Пример на рис. 1 иллюстрирует соседей по связям связи, так что узел 5 имеет соседей 4 и 6. Пример предлагает симметричные отношения между соседями (так, что если 5 является соседом 4, то 4 является соседом 5), но в общем случае это не обязательно.

Набор соседей данного узла определяет набор исходящих каналов, которые он может использовать для передачи в текущем слоте. Для каждой исходящей ссылки ( a , b ) оптимальный товар определяется как товар, который максимизирует следующее дифференциальное количество невыполненных заказов:${\ displaystyle c_ {ab} ^ {opt} (t)}$${\ Displaystyle с \ в \ {1, \ ldots, N \}}$

${\ displaystyle Q_ {a} ^ {(c)} (t) -Q_ {b} ^ {(c)} (t)}$

Любые связи в выборе оптимального товара разрываются произвольно.

Пример показан на рис. 2. В этом примере предполагается, что каждая очередь в настоящее время имеет только 3 товара: красный , зеленый и синий , и они измеряются в целых единицах пакетов. Если говорить о направленном звене (1,2), то дифференциальные отставания составляют:

${\ displaystyle Q_ {1} ^ {({\ text {red}})} (t) -Q_ {2} ^ {({\ text {red}})} (t) = 1}$

${\displaystyle Q_{1}^{({\text{green}})}(t)-Q_{2}^{({\text{green}})}(t)=2}$

${\displaystyle Q_{1}^{({\text{blue}})}(t)-Q_{2}^{({\text{blue}})}(t)=-1}$

Следовательно, оптимальным товаром для отправки по ссылке (1,2) в слоте t является зеленый товар. С другой стороны, оптимальным товаром для отправки по обратной линии связи (2,1) в слоте t является синий товар.

Выбор матрицы μ _ab ( t ) [ править ]

После определения оптимальных товаров для каждого звена ( a , b ) сетевой контроллер вычисляет следующие веса :${\displaystyle W_{ab}(t)}$

${\displaystyle W_{ab}(t)=\max \left[Q_{a}^{(c_{ab}^{\mathrm {opt} }(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t),0\right]}$

Вес - это значение дифференциального бэклога, связанного с оптимальным товаром для линии ( a , b ), максимальное значение которого равно 0. Затем контроллер выбирает скорость передачи в качестве решения следующей задачи максимального веса (разрывая связи произвольно):${\displaystyle W_{ab}(t)}$

${\displaystyle {\text{(Eq. 1)}}\qquad {\text{Maximize: }}\sum _{a=1}^{N}\sum _{b=1}^{N}\mu _{ab}(t)W_{ab}(t)}$

${\displaystyle {\text{(Eq. 2)}}\qquad {\text{Subject to: }}(\mu _{ab}(t))\in \Gamma _{S(t)}}$

В качестве примера решения о максимальном весе предположим, что в текущем слоте t дифференциальные резервы на каждом канале сети из 6 узлов приводят к весам каналов, определяемым по формуле :${\displaystyle W_{ab}(t)}$

${\displaystyle (W_{ab}(t))=\left[{\begin{array}{cccccc}0&2&1&1&6&0\\1&0&1&2&5&6\\0&7&0&0&0&0\\1&0&1&0&0&0\\1&0&7&5&0&0\\0&0&0&0&5&0\end{array}}\right]}$

Хотя набор может содержать бесчисленное множество возможных матриц скорости передачи, для простоты предположим, что текущее состояние топологии допускает только 4 возможных варианта:${\displaystyle \Gamma _{S(t)}}$

${\displaystyle \Gamma _{S(t)}=\{{\boldsymbol {\mu }}_{a},{\boldsymbol {\mu }}_{b},{\boldsymbol {\mu }}_{c},{\boldsymbol {\mu }}_{d}\}}$

иллюстрация 4 возможных вариантов выбора скорости передачи в текущем состоянии топологии S ( t ). Вариант (а) активирует одиночный канал (1,5) со скоростью передачи . Все остальные варианты используют два канала со скоростью передачи 1 на каждом из активированных каналов.${\displaystyle \mu _{15}=2}$

Эти четыре возможности представлены в матричной форме:

${\displaystyle {\boldsymbol {\mu }}_{a}=\left[{\begin{array}{cccccc}0&0&0&0&2&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right],\quad {\boldsymbol {\mu }}_{b}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\0&0&1&0&0&0\\0&0&0&0&0&0\\0&0&0&0&1&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right]}$

${\displaystyle {\boldsymbol {\mu }}_{c}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\1&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&1&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right],\quad {\boldsymbol {\mu }}_{d}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\0&0&0&0&0&0\\0&1&0&0&0&0\\0&0&0&0&0&0\\0&0&0&1&0&0\\0&0&0&0&0&0\end{array}}\right]}$

Обратите внимание, что узел 6 не может ни отправлять, ни получать ни при одной из этих возможностей. Это может возникнуть из-за того, что узел 6 в настоящее время находится вне зоны действия связи. Взвешенная сумма ставок для каждой из 4 возможностей составляет:

• Выбор (а): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=12}$
• Выбор (б): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=1}$
• Выбор (с): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=1}$
• Выбор (г): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=12}$

Поскольку максимальный вес равен 12, сетевой контроллер может разорвать связь произвольно, выбрав вариант или вариант .${\displaystyle {\boldsymbol {\mu }}_{a}}$${\displaystyle {\boldsymbol {\mu }}_{d}}$

Завершение работы с переменными маршрутизации [ править ]

Предположим теперь, что оптимальные товары были определены для каждого канала, а также определены скорости передачи . Если дифференциальное отставание для оптимального товара на данном канале ( a , b ) отрицательное, то данные по этому каналу в текущем слоте не передаются. В противном случае сеть предлагает отправлять единицы товарных данных по этой ссылке. Это делается путем определения переменных маршрутизации для каждой ссылки ( a , b ) и каждого товара c , где:${\displaystyle c_{ab}^{opt}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle \mu _{ab}(t)}$${\displaystyle c_{ab}^{\mathrm {opt} }(t)}$${\displaystyle \mu _{ab}^{(c)}(t)}$

${\displaystyle \mu _{ab}^{(c)}(t)={\begin{cases}\mu _{ab}(t)&{\text{ if }}c=c_{ab}^{opt}(t){\text{ and }}Q_{a}^{(c_{ab}^{opt}(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t)\geq 0\\0&{\text{ otherwise}}\end{cases}}}$

Значение представляет скорость передачи, предлагаемую для данных товара c по каналу ( a , b ) в слоте t . Однако узлам может не хватить определенного товара для поддержки передачи с предлагаемой скоростью по всем исходящим каналам. Это возникает в слоте t для узла n и товара c, если:${\displaystyle \mu _{ab}^{(c)}(t)}$

${\displaystyle Q_{n}^{(c)}(t)<\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)}$

В этом случае отправляются все данные, а пустые данные используются для заполнения неиспользованных частей предлагаемых тарифов, произвольно распределяя фактические данные и нулевые данные по соответствующим исходящим каналам (в соответствии с предлагаемыми тарифами). Это называется ситуацией опустошения очереди . Такое недополнение не влияет на свойства пропускной способности или стабильности сети. Интуитивно это связано с тем, что недополнение возникает только тогда, когда передающий узел имеет небольшой объем невыполненной работы, что означает, что этому узлу не грозит нестабильность.${\displaystyle Q_{n}^{(c)}(t)}$

Улучшение задержки [ править ]

Алгоритм противодавления не использует заранее заданные пути. Пути изучаются динамически и могут отличаться для разных пакетов. Задержка может быть очень большой, особенно когда система слабо загружена, так что не хватает давления для продвижения данных к месту назначения. В качестве примера предположим, что один пакет входит в сеть, и больше ничего не входит. Этот пакет может совершать круговой обход по сети и никогда не прибыть к месту назначения, потому что не нарастает градиент давления. Это не противоречит свойствам противодавления оптимальности пропускной способности или стабильности, поскольку сеть имеет не более одного пакета в любой момент времени и, следовательно, является тривиально стабильной (достигая скорости доставки 0, равной скорости поступления).

Также возможно реализовать противодавление по набору заранее заданных путей. Это может ограничить диапазон емкости, но может улучшить доставку и задержку заказа. Другой способ улучшить задержку, не влияя на область пропускной способности, - это использовать улучшенную версию, которая смещает веса каналов в желаемое направление. ^[9] Моделирование такого смещения показало значительное улучшение задержки. ^{[1] [3]} Следует отметить , что противодавление не требует First-In-First-Out ( FIFO службы) в очередях. Было замечено, что служба Last-in-First-Out ( LIFO ) может значительно улучшить задержку для подавляющего большинства пакетов, не влияя на пропускную способность. ^{[7] [14]}

Распределенное противодавление [ править ]

Обратите внимание, что после выбора скоростей передачи переменные решения о маршрутизации могут быть вычислены простым распределенным способом, когда каждому узлу требуется только знание различий в очереди между собой и его соседями. Однако выбор скоростей передачи требует решения проблемы максимального веса в уравнениях. (1) - (2). В частном случае, когда каналы ортогональны, алгоритм имеет естественную распределенную реализацию и сводится к отдельным решениям в каждом узле. Однако проблема максимального веса - это проблема централизованного управления для сетей с межканальными помехами. Это также может быть очень сложно решить даже централизованно. ${\displaystyle (\mu _{ab}(t))}$${\displaystyle \mu _{ab}^{(c)}(t)}$

Распределенный подход для сетей с помехами со скоростями передачи, которые определяются отношением сигнал-шум-плюс-помеха (SINR), может быть реализован с использованием рандомизации. ^[9] Каждый узел случайным образом решает передать каждый интервал t (передача «нулевого» пакета, если в настоящее время у него нет пакета для отправки). Фактические скорости передачи и соответствующие фактические пакеты для отправки определяются двухэтапным квитированием: на первом этапе случайно выбранные узлы передатчика отправляют пилот-сигнал с силой сигнала, пропорциональной фактической передаче. На втором этапе все потенциальные узлы-приемники измеряют результирующие помехи и отправляют эту информацию обратно передатчикам. Уровни SINR для всех исходящих ссылок ( n ,б ) затем известны всем узлам п , а каждый узел п может решать свою и переменные на основе этой информации. Результирующая пропускная способность не обязательно оптимальна. Однако процесс случайной передачи можно рассматривать как часть процесса состояния канала (при условии, что нулевые пакеты отправляются в случаях недостаточного заполнения, так что процесс состояния канала не зависит от прошлых решений). Следовательно, результирующая пропускная способность этой распределенной реализации является оптимальной для класса всех алгоритмов маршрутизации и планирования, которые используют такие рандомизированные передачи.${\displaystyle \mu _{nb}(t)}$${\displaystyle (\mu _{nb}^{(c)}(t))}$

Альтернативные распределенные реализации можно грубо разделить на два класса: первый класс алгоритмов рассматривает приближения постоянного множителя к задаче максимального веса и дает результаты с постоянным коэффициентом пропускной способности. Второй класс алгоритмов рассматривает аддитивные приближения к проблеме максимального веса, основанные на обновлении решений проблемы максимального веса с течением времени. Алгоритмы этого второго класса, по-видимому, требуют статических условий канала и более длительного (часто неполиномиального) времени сходимости, хотя они могут обеспечить максимальную пропускную способность при соответствующих предположениях. ^{[15] [4] [13]}Аддитивные аппроксимации часто полезны для доказательства оптимальности противодавления, когда они реализованы с устаревшей информацией о невыполнении очереди (см. Упражнение 4.10 текста Neely). ^[13]

Математическое построение через Ляпуновский занос [ править ]

В этом разделе показано, как алгоритм противодавления возникает как естественное следствие жадной минимизации ограничения на изменение суммы квадратов невыполненных требований очереди от одного слота к другому. ^{[9] [3]}

Ограничения управляющих решений и уравнение обновления очереди [ править ]

Рассмотрим многоскачковую сеть с N узлами, как описано в предыдущем разделе. Каждый слот t сетевой контроллер наблюдает за состоянием топологии S ( t ) и выбирает скорости передачи и переменные маршрутизации с учетом следующих ограничений:${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 3)}}\qquad (\mu _{ab}(t))\in \Gamma _{S(t)}}$

${\displaystyle {\text{(Eq. 4)}}\qquad 0\leq \mu _{ab}^{(c)}(t)\qquad \forall a,b,c,\forall t}$

${\displaystyle {\text{(Eq. 5)}}\qquad \sum _{c=1}^{N}\mu _{ab}^{(c)}(t)\leq \mu _{ab}(t)\qquad \forall (a,b),\forall t}$

Как только эти переменные маршрутизации определены, выполняются передачи (при необходимости с использованием незанятого заполнения), и результирующие невыполненные очереди очереди удовлетворяют следующим требованиям:

${\displaystyle {\text{(Eq. 6)}}\qquad Q_{n}^{(c)}(t+1)\leq \max \left[Q_{n}^{(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{(c)}(t),0\right]+\sum _{a=1}^{N}\mu _{an}^{(c)}(t)+A_{n}^{(c)}(t)}$

где - случайный объем данных нового товара c, который экзогенно поступает в узел n в слоте t , и - скорость передачи, выделенная трафику товара c на канале ( n , b ) в слоте t . Обратите внимание, что это может быть больше, чем количество данных о товаре c , которое фактически передается по ссылке ( a , b ) в слоте t . Это связано с тем, что на узле n может не хватить очереди . По этой же причине уравнение. (6) является неравенством, а не равенством, потому что${\displaystyle A_{n}^{(c)}(t)}$${\displaystyle \mu _{nb}^{(c)}(t)}$${\displaystyle \mu _{nb}^{(c)}(t)}$${\displaystyle \sum _{a=1}^{N}\mu _{an}^{(c)}(t)}$может быть больше, чем фактическое эндогенное поступление товара c в узел n в слоте t . Важная особенность уравнения. (6) состоит в том, что оно выполняется, даже если переменные решения выбираются независимо от невыполненных заказов очереди.${\displaystyle \mu _{ab}^{(c)}(t)}$

Предполагается, что для всех слотов t и все , поскольку ни одна очередь не хранит данные, предназначенные для себя.${\displaystyle Q_{c}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$

Ляпуновский занос [ править ]

Определить как матрицу текущих невыполненных заказов. Определите следующую неотрицательную функцию, называемую функцией Ляпунова :${\displaystyle {\boldsymbol {Q}}(t)=(Q_{n}^{(c)}(t))}$

${\displaystyle L(t)={\frac {1}{2}}\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)^{2}}$

Это сумма квадратов незавершенных заказов в очереди (умноженная на 1/2 только для удобства дальнейшего анализа). Вышеупомянутая сумма аналогична суммированию по всем n , c , так как для всех и всех слотов${\displaystyle n\neq c}$${\displaystyle Q_{c}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$ t .

Условный дрейф Ляпунова определяются:${\displaystyle \Delta (t)}$

${\displaystyle \Delta (t)=E\left[L(t+1)-L(t)\mid {\boldsymbol {Q}}(t)\right]}$

Обратите внимание , что выполняется неравенство имеет место для всех , , :${\displaystyle q\geq 0}$${\displaystyle a\geq 0}$${\displaystyle b\geq 0}$

${\displaystyle (\max[q-b,0]+a)^{2}\leq q^{2}+b^{2}+a^{2}+2q(a-b)}$

Возводя в квадрат уравнение обновления очереди (уравнение (6)) и используя указанное выше неравенство, нетрудно показать, что для всех слотов t и при любом алгоритме выбора переменных передачи и маршрутизации и : ^[3]${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 7)}}\qquad \Delta (t)\leq B+\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)E\left[\lambda _{n}^{(c)}(t)+\sum _{a=1}^{N}\mu _{an}^{(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)|{\boldsymbol {Q}}(t)\right]}$

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

Минимизация границы дрейфа путем переключения сумм [ править ]

Алгоритм противодавления предназначен для наблюдения и S ( t ) каждого слота t, выбора и минимизации правой части уравнения смещения границы. (7). Поскольку B является константой и являются константами, это означает максимизацию:${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$${\displaystyle \lambda _{n}^{(c)}}$

${\displaystyle E\left[\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)\left[\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)-\sum _{a=1}^{N}\mu _{an}^{(c)}(t)\right]|{\boldsymbol {Q}}(t)\right]}$

где конечные суммы были вытеснены через ожидания, чтобы пролить свет на решение о максимизации. По принципу приспосабливаемой максимизации ожидания , указанное ожидание максимизируется путем максимизации функции внутри него (учитывая наблюдаемым , ). Таким образом, каждый выбирает и подчиняется уравнениям ограничений. (3) - (5), чтобы максимизировать:${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle S(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle \sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)\left[\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)-\sum _{a=1}^{N}\mu _{an}^{(c)}(t)\right]}$

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

${\displaystyle \sum _{a=1}^{N}\sum _{b=1}^{N}\sum _{c=1}^{N}\mu _{ab}^{(c)}(t)[Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)]}$

Вес называется текущим дифференциальным отставанием по товару c между узлами a и b . Идея состоит в том, чтобы выбрать переменные решения так, чтобы максимизировать вышеупомянутую взвешенную сумму, где веса являются дифференциальными невыполненными задачами. Интуитивно это означает распределение больших ставок в направлении большего дифференциального отставания.${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

Ясно, что нужно выбирать когда угодно . Далее, учитывая конкретную ссылку , нетрудно показать, что оптимальный выбор с учетом ур. (3) - (5) определяются следующим образом: Сначала найдите товар, который максимизирует дифференциальное отставание для ссылки ( a , b ). Если максимальное дифференциальное отставание отрицательно для ссылки ( a , b ), назначьте для всех товаров на ссылке ( a , b ). В противном случае назначьте полную скорость ссылки для товара и нулевую ставку для всех других товаров по этой ссылке. При таком выборе следует, что:${\displaystyle \mu _{ab}^{(c)}(t)=0}$${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)<0}$${\displaystyle \mu _{ab}(t)}$${\displaystyle (a,b)}$${\displaystyle \mu _{ab}^{(c)}(t)}$${\displaystyle c_{ab}^{opt}(t)\in \{1,\ldots ,N\}}$${\displaystyle \mu _{ab}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle \mu _{ab}(t)}$${\displaystyle c_{ab}^{opt}(t)}$

${\displaystyle \sum _{c=1}^{N}\mu _{ab}^{(c)}(t)[Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)]=\mu _{ab}(t)W_{ab}(t)}$

где - дифференциальное отставание от оптимального товара для ссылки ( a , b ) в слоте t (с максимальным значением 0):${\displaystyle W_{ab}(t)}$

${\displaystyle W_{ab}(t)=\max[Q_{a}^{(c_{ab}^{opt}(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t),0]}$

Осталось только выбрать . Это делается путем решения следующих задач:${\displaystyle (\mu _{ab}(t))\in \Gamma _{S(t)}}$

${\displaystyle \mathrm {Maximize:} \sum _{a=1}^{N}\sum _{b=1}^{N}\mu _{ab}(t)W_{ab}(t)}$

${\displaystyle \mathrm {Subjectto:} (\mu _{ab}(t))\in \Gamma _{S(t)}}$

Вышеупомянутая проблема идентична проблеме максимального веса в уравнениях. (1) - (2). Алгоритм противодавлением использует решения макс-вес для , а затем выбирает переменные маршрутизации с помощью максимального дифференциального отставании , как описано выше.${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

Замечательным свойством алгоритма противодавления является то, что он жадно действует на каждый слот t, основываясь только на наблюдаемом состоянии топологии S ( t ) и невыполненных очередях очереди для этого слота. Таким образом, это не требует знания скорости поступления или вероятностей состояния топологии .${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \pi _{S}=Pr[S(t)=S]}$

Анализ производительности [ править ]

В этом разделе доказывается пропускная способность алгоритма противодавления. ^{[3] [13]} Для простоты рассматривается сценарий, в котором события независимы и одинаково распределены (iid) по слотам, хотя можно показать, что тот же алгоритм работает в сценариях без идентификаторов (см. Ниже в разделе « Операции без идентификаторов» и «Универсальные»). планирование ).

Динамическое прибытие [ править ]

Пусть - матрица экзогенных приходов на слот t . Предположим, что эта матрица независима и одинаково распределена (iid) по слотам с конечными вторыми моментами и со средствами:${\displaystyle (A_{n}^{(c)}(t))}$

${\displaystyle \lambda _{n}^{(c)}=E\left[A_{n}^{(c)}(t)\right]}$

Предполагается, что для всех , поскольку не поступают данные, предназначенные для них самих. Таким образом, матрица показателей прибытия представляет собой матрицу неотрицательных действительных чисел с нулями на диагонали.${\displaystyle \lambda _{c}^{(c)}=0}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle N\times N}$

Область пропускной способности сети [ править ]

Предположим, что состояние топологии S ( t ) является iid по слотам с вероятностями (если S ( t ) принимает значения в несчетно бесконечном наборе векторов с действительными элементами, то это распределение вероятностей, а не функция массы вероятностей). Общий алгоритм для сети наблюдает за S ( t ) в каждом слоте t и выбирает скорости передачи и переменные маршрутизации в соответствии с ограничениями в уравнениях. (3) - (5). Область пропускной способности сети - это замыкание набора всех матриц скорости поступления.${\displaystyle \pi _{S}=Pr[S(t)=S]}$${\displaystyle \pi _{S}}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$ ${\displaystyle \Lambda }$${\displaystyle (\lambda _{n}^{(c)})}$для которого существует алгоритм, стабилизирующий сеть. Стабильность всех очередей подразумевает, что общая скорость входящего трафика в сеть такая же, как общая скорость данных, доставленных к месту назначения. Можно показать, что для любой матрицы скорости поступления в области пропускной способности существует стационарный и рандомизированный алгоритм, который выбирает переменные решения и каждый слот t на основе только S ( t ) (и, следовательно, независимо от незавершенных заказов очереди), который дает следующее для все : ^{[9] [13]}${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle (\mu _{ab}^{*}(t))}$${\displaystyle (\mu _{ab}^{*(c)}(t))}$${\displaystyle n\neq c}$

${\displaystyle {\text{(Eq. 8)}}\qquad E\left[\lambda _{n}^{(c)}+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)\right]\leq 0}$

Такой стационарный и рандомизированный алгоритм, который основывает решения только на S ( t ), называется S-only алгоритмом . Часто бывает полезно предположить, что это внутреннее по отношению к , так что существует такое, что , где 1 if , и ноль else. В этом случае существует алгоритм S -only, который для всех дает следующее :${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle \epsilon >0}$${\displaystyle (\lambda _{n}^{(c)}+\epsilon 1_{n}^{(c)})\in \Lambda }$${\displaystyle 1_{n}^{(c)}}$${\displaystyle n\neq c}$${\displaystyle n\neq c}$

${\displaystyle {\text{(Eq. 9)}}\qquad E\left[\lambda _{n}^{(c)}+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)\right]\leq -\epsilon }$

В качестве технического требования предполагается, что вторые моменты скоростей передачи конечны при любом алгоритме выбора этих скоростей. Это тривиально выполняется, если существует конечная максимальная скорость .${\displaystyle \mu _{ab}(t)}$${\displaystyle \mu _{max}}$

Сравнение с S-алгоритмами [ править ]

Поскольку алгоритм противодавления наблюдает и S ( t ) каждый слот t и выбирает решения и минимизирует правую часть границы дрейфа Ур. (7) имеем:${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 10)}}\qquad \Delta (t)\leq B+\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)E\left[\lambda _{n}^{(c)}(t)+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)|{\boldsymbol {Q}}(t)\right]}$

где и - любые альтернативные решения, которые удовлетворяют уравнениям. (3) - (5), включая рандомизированные решения.${\displaystyle (\mu _{ab}^{*}(t))}$${\displaystyle (\mu _{ab}^{*(c)}(t))}$

Теперь предположим . Тогда существует только S- алгоритм, удовлетворяющий уравнению. (8). Вставив это в правую часть уравнения. (10) и отмечая, что условное ожидание, данное в этом алгоритме S -only, такое же, как безусловное ожидание (поскольку S ( t ) имеет идентификатор по слотам, а алгоритм S -only не зависит от текущих незавершенных работ в очереди) дает:${\displaystyle (\lambda _{n}^{(c)})\in \Lambda }$${\displaystyle {\boldsymbol {Q}}(t)}$

${\displaystyle \Delta (t)\leq B\,}$

Таким образом, дрейф квадратичной функции Ляпунова меньше или равен константе B для всех интервалов t . Этот факт, вместе с предположением, что поступления в очередь имеют ограниченные вторые моменты, означает следующее для всех сетевых очередей: ^[16]

${\displaystyle \lim _{t\rightarrow \infty }{\frac {Q_{n}^{(c)}(t)}{t}}=0{\text{ with probability 1}}}$

Для более четкого понимания среднего размера очереди, можно предположить, что скорости поступления являются внутренними , поэтому существует такое, что уравнение. (9) выполняется для некоторого альтернативного S- единственного алгоритма. Подключение уравнения. (9) в правую часть уравнения. (10) дает:${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle \epsilon >0}$

${\displaystyle \Delta (t)\leq B-\epsilon \sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)}$

откуда сразу получаем (см. ^{[3] [13]} ):

${\displaystyle \limsup _{t\rightarrow \infty }{\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{n=1}^{N}\sum _{c=1}^{N}E\left[Q_{n}^{(c)}(\tau )\right]\leq {\frac {B}{\epsilon }}}$

Эта средняя граница размера очереди увеличивается по мере того, как расстояние до границы области емкости приближается к нулю. Это такая же качественная производительность, как у одиночной очереди M / M / 1 со скоростью поступления и скоростью обслуживания , где средний размер очереди пропорционален , где .${\displaystyle \epsilon }$${\displaystyle \Lambda }$${\displaystyle \lambda }$${\displaystyle \mu }$${\displaystyle 1/\epsilon }$${\displaystyle \epsilon =\mu -\lambda }$

Расширения вышеуказанной формулировки [ править ]

Операции без идентификаторов и универсальное планирование [ править ]

Приведенный выше анализ для простоты предполагает использование свойств iid. Однако можно показать, что тот же алгоритм противодавления надежно работает в ситуациях, не связанных с iid. Когда процессы поступления и состояния топологии эргодичны, но не обязательно iid, противодавление по-прежнему стабилизирует систему всякий раз . ^{[9] В} более общем плане, с использованием универсального подхода к планированию было показано, что он предлагает свойства стабильности и оптимальности для произвольных (возможно, неэргодических) путей выборки. ^[17]${\displaystyle (\lambda _{n}^{(c)})\in \Lambda }$

Противодавление с оптимизацией утилит и минимизацией штрафов [ править ]

Было показано, что противодавление работает в сочетании с управлением потоком с помощью метода « дрейф плюс штраф» . ^{[10] [11] [3]} Этот метод жадно максимизирует сумму дрейфа и взвешенное выражение штрафа. Штраф взвешивается параметром V, который определяет компромисс производительности. Этот метод гарантирует, что полезная пропускная способность находится в пределах O (1 / V ) от оптимальности, в то время как средняя задержка составляет O ( V ). Таким образом, полезность может быть произвольно приближена к оптимальной с соответствующим компромиссом в средней задержке. Подобные свойства могут быть показаны для минимизации средней мощности ^[18] и для оптимизации более общих сетевых атрибутов. ^[13]

Альтернативные алгоритмы для стабилизации очередей при максимизации полезности сети были разработаны с использованием анализа модели жидкости ^[12], совместного анализа жидкости и анализа множителя Лагранжа, ^[19] выпуклой оптимизации ^[20] и стохастических градиентов. ^[21] Эти подходы не обеспечивают результатов задержки полезности O (1 / V ), O ( V ).

См. Также [ править ]

• AODV
• Разнесенная маршрутизация противодавления (DIVBAR) ^[1]
• Дрифт плюс штраф
• ExOR
• Географическая маршрутизация
• Список специальных протоколов маршрутизации
• Оптимизация по Ляпунову

Ссылки [ править ]

Первоисточники [ править ]

• Л. Тассиулас и А. Ефремидес, "Свойства устойчивости систем массового обслуживания с ограничениями и политики планирования для максимальной пропускной способности в многоступенчатых радиосетях", IEEE Transactions on Automatic Control , vol. 37, нет. 12. С. 1936–1948, декабрь 1992 г.
• Л. Георгиадис, М. Дж. Нили и Л. Тассиулас, «Распределение ресурсов и межуровневое управление в беспроводных сетях», « Основы и тенденции в сетевых технологиях» , вып. 1, вып. 1. С. 1–149, 2006.
• MJ Neely. Стохастическая оптимизация сети с приложением к системам связи и массового обслуживания , Morgan & Claypool, 2010.