Оптимизация по Ляпунову для сетей массового

Рассмотрим ту же сеть массового обслуживания, что и в предыдущем разделе. Теперь определите p (t) {\displaystyle p(t)}, как в сеть штраф, понесенные на игровых t. {\displaystyle t.} предположим, что цель-стабилизировать сети массового обслуживания при минимальных временных среднем p (t). {\displaystyle p(t).}, например, для стабилизации сети при минимальном времени средняя мощность, p (t) {\displaystyle p(t)} может быть определена как общая мощность, понесенные в сети на T слот. ^[8] для лечения проблем максимизации времени, в среднем около желанная награда r (t), {\displaystyle r(t),} наказание может быть определено p (t) = − r (t). {\displaystyle p(t)=-r(t).} это полезно для максимизации пропускной способности сети полезности при стабильности. ^[3]

Для стабилизации сети при минимизации среднего времени штрафа p (t), {\displaystyle p(t),} сетевые алгоритмы могут быть разработаны для выполнения управляющих действий, которые жадно минимизируют ограничение на следующее выражение дрейфа плюс штраф в каждом слоте t {\displaystyle t}: ^[5]

Δ L (t) + V p (t) {\displaystyle \Delta L(t)+Vp(t)}

где V {\displaystyle V} -неотрицательный вес, который выбирается по желанию, чтобы повлиять на компромисс производительности. Ключевой особенностью этого подхода является то, что он обычно не требует знания вероятностей случайных сетевых событий (таких как случайное поступление заданий или реализация каналов). Выбор V = 0 {\displaystyle V=0} сводится к минимизации ограничения дрейфа в каждом слоте, а для маршрутизации в сетях массового обслуживания с несколькими переходами-к алгоритму маршрутизации с обратным давлением, разработанному Тассиуласом и Эфремидесом. ^{[1] [2]} Использование V > 0 {\displaystyle V>0} и определение p (t) {\displaystyle p(t)}, как использование сетевого питания в слоте t {\displaystyle t}, приводит к алгоритму дрейфа плюс штраф для минимизации средней мощности при условии стабильности сети, разработанной компанией Neely. ^[8] Использование V > 0 {\displaystyle V>0} и использование p (t) {\displaystyle p(t)} в качестве отрицательной метрики полезности контроля допуска приводит к алгоритму дрейфа плюс штраф для совместного управления потоком и сетевой маршрутизации, разработанному Нили, Модиано и Ли. ^[3]

В этом контексте важно обобщение теоремы о дрейфе Ляпунова, изложенной в предыдущем разделе. Для простоты изложения предположим p (t) {\displaystyle p(t)}, что он ограничен снизу:

p (t) ⩾ p min ∀ t ∈ { 0, 1, 2,... } {\displaystyle p(t)\geqslant p_{\min }\quad \forall t\in \{0,1,2,...\}}

Например, вышеизложенное удовлетворяется p min = 0 {\displaystyle p_{\min }=0} в случаях, когда штраф p (t) {\displaystyle p(t)} всегда неотрицателен. Пусть p ∗ {\displaystyle p^{*}} представляет желаемую цель для среднего значения по времени p (t). {\displaystyle p(t).} Let V {\displaystyle V} -параметр, используемый для оценки важности достижения цели. Следующая теорема показывает, что если выполняется условие дрейфа плюс штраф, то средний штраф по времени составляет не более O(1/V) выше желаемой цели, в то время как средний размер очереди составляет O(V). V {\displaystyle V} Параметр можно настроить так, чтобы среднее время штрафа было как можно ближе (или ниже) к цели по желанию, с соответствующим компромиссом размера очереди.

Теорема (Оптимизация по Ляпунову). Предположим, что существуют константы ε > 0, V, B ⩾ 0, {\displaystyle \varepsilon >0,V,B\geqslant 0,} и p ∗ {\displaystyle p^{*}} такие, что для всех t {\displaystyle t} и всех возможных векторов Q (t) {\displaystyle Q(t)} выполняется следующее условие дрейфа плюс штраф:

E [ Δ L (t) + V p (t) | Q (t) ] ⩽ B + V p ∗ − ε ∑ i = 1 N Q i (t) {\displaystyle \mathbb {E} [\Delta L(t)+Vp(t)|Q(t)]\leqslant B+Vp^{*}-\varepsilon \sum _{i=1}^{N}Q_{i}(t)}

Тогда за все t > 0 {\displaystyle t>0} время средний штраф и средние размеры очереди по времени удовлетворяют:

1 t ∑ τ = 0 t − 1 E [ p (τ) ] ⩽ p ∗ + B V + E [ L (0) ] V t {\displaystyle {\frac {1}{t}}\sum _{\tau =0}^{t-1}\mathbb {E} [p(\tau)]\leqslant p^{*}+{\frac {B}{V}}+{\frac {\mathbb {E} [L(0)]}{Vt}}}

1 t ∑ τ = 0 t − 1 ∑ i = 1 N E [ Q i (τ) ] ⩽ B + V (p ∗ − p min) ε + E [ L (0) ] ε t {\displaystyle {\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{i=1}^{N}\mathbb {E} [Q_{i}(\tau)]\leqslant {\frac {B+V(p^{*}-p_{\min })}{\varepsilon }}+{\frac {\mathbb {E} [L(0)]}{\varepsilon t}}}