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

Термин «противодавление» при описании потока жидкости в трубопроводах и системах вентиляции см. обратное давление.

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

Вступление

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

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

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

Происхождение

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

Как это устроено

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

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

Рис. 1: Многоканальная сеть с 6 узлами. Стрелки между узлами показывают текущих соседей.

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

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

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

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

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

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

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

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

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

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

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

Рис. 2: Крупный план узлов 1 и 2. Оптимальным товаром для отправки по ссылке (1,2) является зеленый товар. Оптимальный товар для отправки в другом направлении (по ссылке (2,1)) - это синий товар.

Пример показан на рис. 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) в слоте т это зеленый товар. С другой стороны, оптимальный товар для отправки по обратной линии связи (2,1) в слоте т это синий товар.

Выбор μ_ab(т) матрица

После определения оптимальных товаров для каждой ссылки (а,б) сетевой контроллер вычисляет следующие веса ${\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]}$

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

${\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)}}$

В качестве примера решения о максимальном весе предположим, что в текущем слоте т, дифференциальные задержки на каждом звене сети из 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]}$

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

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

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

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

${\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}$.
• Вариант (c): ${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=1}$.
• Выбор (d): ${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=12}$.

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

Завершение переменных маршрутизации

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

${\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}}}$

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

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

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

Улучшение задержки

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

Также возможно реализовать противодавление по набору заранее заданных путей. Это может ограничить диапазон емкости, но может улучшить порядок доставки и задержку. Еще один способ улучшить задержку, не влияя на диапазон емкости, - использовать повышеннаяверсия, которая смещает веса ссылок в желаемое направление.^[9] Моделирование такого смещения показало значительное улучшение задержки.^[1][3]Обратите внимание, что противодавление не требует принципа «первым пришел - первым вышел» (ФИФО ) обслуживание в очередях. Было замечено, что последний вошел - первым ушел (LIFO ) может значительно уменьшить задержку для подавляющего большинства пакетов, не влияя на пропускную способность.^[7][14]

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

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

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

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

Математическое построение с помощью ляпуновского заноса

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

Ограничения управляющего решения и уравнение обновления очереди

Рассмотрим многоскачковую сеть с N узлы, как описано в предыдущем разделе. т, сетевой контроллер наблюдает за состоянием топологии S(т) и выберите скорость передачи ${\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)}$

куда ${\displaystyle A_{n}^{(c)}(t)}$ случайное количество нового товара cданные, которые поступают на узел экзогенно п на слоте т, и ${\displaystyle \mu _{nb}^{(c)}(t)}$ скорость передачи, относящаяся к товару c трафик по ссылке (п,б) на слоте т. Обратите внимание, что ${\displaystyle \mu _{nb}^{(c)}(t)}$ может быть больше, чем количество товара c данные, которые фактически передаются по ссылке (а,б) на слоте т. Это связано с тем, что может не хватить узла резервного входа п. По этой же причине уравнение. (6) - это не равенство, а неравенство, потому что${\displaystyle \sum _{a=1}^{N}\mu _{an}^{(c)}(t)}$ может быть больше, чем фактическое эндогенное поступление товара c узел п на слоте т. Важная особенность уравнения. (6) состоит в том, что оно выполняется, даже если ${\displaystyle \mu _{ab}^{(c)}(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 только для удобства дальнейшего анализа). Вышеупомянутая сумма аналогична суммированию по всем п, c такой, что ${\displaystyle n\neq c}$ потому что ${\displaystyle Q_{c}^{(c)}(t)=0}$ для всех ${\displaystyle c\in \{1,\ldots ,N\}}$ и все слоты т.

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

${\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 - конечная константа, которая зависит от вторых моментов поступления и максимально возможных вторых моментов скорости передачи.

Минимизация границы сноса путем переключения сумм

Алгоритм противодавления предназначен для наблюдения ${\displaystyle {\boldsymbol {Q}}(t)}$ иS(т) каждый слот т и выберите ${\displaystyle (\mu _{ab}(t))}$ и ${\displaystyle (\mu _{ab}^{(c)}(t))}$ чтобы минимизировать правую часть границы дрейфа (Ур. (7). Потому что B является константой и ${\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]}$

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

${\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)]}$

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

Ясно, что нужно выбрать ${\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)}$ выбор в соответствии с уравнениями. (3) - (5) определяются следующим образом: Сначала найдите товар ${\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)}$

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

${\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))}$ через максимальное дифференциальное отставание, как описано выше.

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

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

В этом разделе доказывается пропускная способность алгоритма противодавления.^[3][13] Для простоты рассматривается сценарий, в котором события независимы и одинаково распределены (i.i.d.) по слотам, хотя можно показать, что тот же алгоритм работает в non-i.i.d. сценарии (см. ниже под Без i.i.d. эксплуатация и универсальное планирование ).

Динамические прибытия

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

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

${\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(т) называется 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)}}$ равно 1, если ${\displaystyle n\neq c}$, и еще ноль. В этом случае есть S-только алгоритм, который дает следующее для всех ${\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-только алгоритмами

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

${\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]}$

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

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

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

Таким образом, дрейф квадратичной функции Ляпунова меньше или равен постоянной B for all slots т. This fact, together with the assumption that queue arrivals have bounded second moments, imply the following for all network queues:^[16]

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

For a stronger understanding of average queue size, one can assume the arrival rates ${\displaystyle (\lambda _{n}^{(c)})}$ are interior to ${\displaystyle \Lambda }$, so there is an ${\displaystyle \epsilon >0}$ such that Eq. (9) holds for some alternativeS-only algorithm. Plugging Eq. (9) into the right-hand-side of Eq. (10) yields:

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

from which one immediately obtains (see^[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 }}}$

This average queue size bound increases as the distance ${\displaystyle \epsilon }$ to the boundary of thecapacity region ${\displaystyle \Lambda }$ уходит в ноль. This is the same qualitative performance as a single M/M/1 queue with arrival rate${\displaystyle \lambda }$ and service rate ${\displaystyle \mu }$, whereaverage queue size is proportional to ${\displaystyle 1/\epsilon }$, куда ${\displaystyle \epsilon =\mu -\lambda }$.

Extensions of the above formulation

Non-i.i.d. operation and universal scheduling

The above analysis assumes i.i.d. properties for simplicity. However, the same backpressure algorithm can be shown to operate robustly in non-i.i.d. ситуации. When arrival processes and topology states are ergodic but not necessarily i.i.d., backpressure still stabilizes the system whenever ${\displaystyle (\lambda _{n}^{(c)})\in \Lambda }$.^[9] More generally, using a universal scheduling approach, it has been shown to offer stability and optimality properties for arbitrary (possibly non-ergodic) sample paths.^[17]

Backpressure with utility optimization and penalty minimization

Backpressure has been shown to work in conjunction with flow control via a drift-plus-penalty техника.^[10][11][3] This technique greedily maximizes a sum of drift and a weighted penalty expression. The penalty is weighted by a parameter V that determines a performance tradeoff. This technique ensures throughput utility is within О(1/V) of optimality while average delay is О(V). Thus, utility can be pushed arbitrarily close to optimality, with a corresponding tradeoff in average delay. Similar properties can be shown for average power minimization^[18] and for optimization of more general network attributes.^[13]

Alternative algorithms for stabilizing queues while maximizing a network utility have been developed using fluid model analysis,^[12] joint fluid analysis and Lagrange multiplier analysis,^[19] convex optimization,^[20] and stochastic gradients.^[21] These approaches do not provide the О(1/V), О(V) utility-delay results.

Смотрите также

• AODV
• Diversity backpressure routing (DIVBAR)^[1]
• Drift plus penalty
• ExOR
• Geographic routing
• List of ad hoc routing protocols
• Lyapunov optimization

Рекомендации

1. M. J. Neely and R. Urgaonkar, "Optimal Backpressure Routing in Wireless Networks with Multi-Receiver Diversity," Ad Hoc Networks (Elsevier), vol. 7, вып. 5, pp. 862-881, July 2009.
2. L. Tassiulas and A. Ephremides,"Stability Properties of Constrained Queueing Systems andScheduling Policies for Maximum Throughput in MultihopRadio Networks, IEEE Transactions по автоматическому контролю, т. 37, нет. 12, pp. 1936-1948, Dec. 1992.
3. L. Georgiadis, M. J. Neely, and L. Tassiulas, "Resource Allocation and Cross-Layer Control in Wireless Networks,"Foundations and Trends in Networking, т. 1, вып. 1, pp. 1-149, 2006.
4. L. Jiang and J. Walrand. Scheduling and Congestion Control for Wireless and Processing Networks,Morgan & Claypool, 2010.
5. A. Sridharan, S. Moeller, and B. Krishnamachari,"Making Distributed Rate Control using Lyapunov Drifts a Reality in Wireless Sensor Networks,"6th Intl. Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt),April 2008.
6. A. Warrier, S. Janakiraman, S. Ha, and I. Rhee, "DiffQ: Practical Differential Backlog Congestion Control for WirelessNetworks," Proc. IEEE INFOCOM, Rio de Janeiro, Brazil, 2009.
7. S. Moeller, A. Sridharan, B. Krishnamachari, and O. Gnawali,"Routing Without Routes: The Backpressure Collection Protocol,"Proc. 9th ACM/IEEE Intl. Конф. on Information Processing in Sensor Networks (IPSN),April 2010.
8. B. Awerbuch and T. Leighton, "A Simple Local-Control Approximation Algorithm for Multicommodity Flow," Proc. 34th IEEE Conf.on Foundations of Computer Science, Oct. 1993.
9. M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic Power Allocation and Routingfor Time Varying Wireless Networks," Журнал IEEE по избранным областям коммуникаций, т. 23, нет. 1, pp. 89-103,January 2005.
10. M. J. Neely. Dynamic Power Allocation and Routing for Satellite and Wireless Networks with Time Varying Channels.Ph.D. Dissertation, Massachusetts Institute of Technology, LIDS. Ноябрь 2003 г.
11. M. J. Neely, E. Modiano, and C. Li, "Fairness and Optimal Stochastic Control for Heterogeneous Networks," Proc. IEEE INFOCOM, March 2005.
12. A. Stolyar,"Maximizing Queueing Network Utility subject to Stability: Greedy Primal-Dual Algorithm,"Queueing Systems, т. 50, нет. 4, pp. 401-457, 2005.
13. M. J. Neely.Stochastic Network Optimization with Application to Communication and Queueing Systems,Morgan & Claypool, 2010.
14. L. Huang, S. Moeller, M. J. Neely, and B. Krishnamachari, "LIFO-Backpressure Achieves Near Optimal Utility-Delay Tradeoff,"Proc. WiOpt, May 2011.
15. E. Modiano, D. Shah, and G. Zussman, "Maximizing throughput in wireless networks via gossiping," Proc. ACM SIGMETRICS, 2006.
16. M. J. Neely, "Queue Stability and Probability 1 Convergence via Lyapunov Optimization," Journal of Applied Mathematics, vol. 2012, Дои:10.1155/2012/831909.
17. M. J. Neely, "Universal Scheduling for Networks with Arbitrary Traffic, Channels,and Mobility," Proc. IEEE Conf. on Decision and Control (CDC), Atlanta, GA, Dec. 2010.
18. M. J. Neely, "Energy Optimal Control for Time Varying Wireless Networks,"IEEE Transactions по теории информации, т. 52, нет. 7, pp. 2915-2934,July 2006
19. A. Eryilmaz and R. Srikant, "Fair Resource Allocation in Wireless Networks using Queue-Length-Based Schedulingand Congestion Control," Proc. IEEE INFOCOM, March 2005.
20. X. Lin and N. B. Shroff, "Joint Rate Control and Scheduling in Multihop Wireless Networks,"Proc. of 43rd IEEE Conf. on Decision and Control, Paradise Island, Bahamas, Dec. 2004.
21. J. W. Lee, R. R. Mazumdar, and N. B. Shroff, "Opportunistic Power Scheduling for Dynamic Multiserver Wireless Systems,"IEEE Transactions on Wireless Communications, т. 5, no.6, pp. 1506–1515, June 2006.

Основные источники

• L. Tassiulas and A. Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks," IEEE Transactions по автоматическому контролю, т. 37, нет. 12, pp. 1936–1948, Dec. 1992.
• L. Georgiadis, M. J. Neely, and L. Tassiulas, "Resource Allocation and Cross-Layer Control in Wireless Networks," Foundations and Trends in Networking, т. 1, вып. 1, pp. 1–149, 2006.
• M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010.