Směrování protitlaku - Backpressure routing - Wikipedia

v teorie front, disciplína v rámci matematické teorie pravděpodobnosti, algoritmus směrování protitlaku je metoda pro směrování provozu kolem sítě ve frontě, která dosahuje maximální propustnosti sítě,^[1] který je založen pomocí konceptů Lyapunov drift. Směrování protitlaku zvažuje situaci, kdy každá úloha může navštívit více uzlů služby v síti. Jedná se o rozšíření plánování maximální hmotnosti kde každá úloha navštíví pouze jeden uzel služby.

Úvod

Směrování protitlaku je algoritmus pro dynamické směrování provozu přes multi-hopovou síť pomocí gradientů zahlcení. Algoritmus lze aplikovat na bezdrátové komunikační sítě, včetně senzorové sítě, mobilní sítě ad hoc (MANETY ) a heterogenní sítě s bezdrátovými a drátovými komponenty.^[2][3]

Principy protitlaku lze použít i v jiných oblastech, jako je studium systémů montáže produktů a sítí zpracování.^[4]Tento článek se zaměřuje na komunikační sítě, kam přicházejí pakety z více datových toků a musí být doručovány do příslušných destinací. Zpětný tlakový algoritmus pracuje v časovém úseku. Každý časový úsek se snaží směrovat data ve směrech, které maximalizují diferenciální nevyřízené položky mezi sousedními uzly. To je podobné tomu, jak voda protéká sítí potrubí tlakovými spády. Algoritmus protitlaku však lze použít pro sítě s více komoditami (kde mohou mít různé pakety různé cíle) a pro sítě, kde lze zvolit přenosové rychlosti ze sady (případně časově proměnných) možností. Atraktivní vlastnosti algoritmu protitlaku jsou: (i) vede k maximální propustnosti sítě, (ii) je prokazatelně robustní vůči časově se měnícím podmínkám sítě, (iii) lze jej implementovat, aniž by znal rychlost příjmu dat nebo pravděpodobnost stavu kanálu. Algoritmus však může způsobit velká zpoždění a může být obtížné jej přesně implementovat v sítích s interferencí. Níže jsou popsány úpravy zpětného tlaku, které snižují zpoždění a zjednodušují implementaci Zlepšení zpoždění a Distribuovaný protitlak.

Směrování protitlaku bylo studováno hlavně v teoretickém kontextu. V praxi bezdrátové sítě ad hoc obvykle implementovaly alternativní metody směrování založené na výpočtech nejkratší cesty nebo zaplavení sítě, jako je napříkladSměrování vzdálenosti na vyžádání ad hoc na vyžádání (AODV),geografické směrování, a extrémně oportunistické směrování (ExOR). Vlastnosti matematické optimality protitlaku však motivovaly nedávné experimentální demonstrace jeho použití na bezdrátových testech na University of Southern California a na North Carolina State University.^[5][6][7]

Počátky

Původní algoritmus protitlaku vyvinuli Tassiulas a Ephremides.^[2] Zvažovali a multi-hop paketová rádiová síť s náhodnými příchody paketů a pevnou sadou možností výběru spojení. Jejich algoritmus sestával z a výběr odkazu maximální hmotnosti etapa a diferenciální směrování nevyřízených položek stage.Algoritmus související s protitlakem, navržený pro výpočet toků více komoditních sítí, byl vyvinut v Awerbuchu a Leightonu.^[8]Algoritmus protitlaku byl později rozšířen Neelym, Modianem a Rohrsem o léčbu plánování pro mobilní sítě.^[9]Protitlak je matematicky analyzován pomocí teorie Lyapunov drift, a lze je použít společně s mechanismy řízení toku k zajištění maximalizace síťového nástroje.^{[10][11][3][12][13]}(viz také Protitlak s optimalizací nástroje a minimalizací pokut ).

Jak to funguje

Směrování protitlaku je navrženo tak, aby činilo rozhodnutí, která (zhruba) minimalizují součet čtverců nevyřízených front v síti z jednoho časového úseku do druhého. Přesný matematický vývoj této techniky je popsán ve vedlejších částech. Tato část popisuje obecný model sítě a fungování směrování protitlaku s ohledem na tento model.

Multi-hopový síťový model fronty

Obr. 1: 6 uzlová multihop síť. Šipky mezi uzly ilustrují aktuální sousedy.

Zvažte víceskokovou síť s N uzly (příklad viz. obr. 1) N = 6). Síť pracuje ve stanoveném čase ${ displaystyle t in {0,1,2, ldots }}$. Na každém slotu mohou do sítě dorazit nová data a jsou učiněna rozhodnutí o plánování směrování a přenosu ve snaze doručit všechna data do správného cíle. Nechte data, která jsou určena pro uzel ${ displaystyle c in {1, tečky, N }}$ být označen jako údaje o komoditě c. Data v každém uzlu se ukládají podle jeho komodity. Pro ${ displaystyle n in {1, ldots, N }}$ a ${ displaystyle c in {1, ldots, N }}$, nechť ${ displaystyle Q_ {n} ^ {(c)} (t)}$ být aktuální množství komodity C data v uzlu n, také nazývaný nevyřízené fronty. Detailní pohled na nevyřízené fronty uvnitř uzlu je uveden na obr. 2. Jednotky ${ displaystyle Q_ {n} ^ {(c)} (t)}$ závisí na kontextu problému. Například nevyřízené položky mohou nabývat celých jednotek balíčky, což je užitečné v případech, kdy jsou data segmentována do paketů pevné délky. Alternativně může brát skutečné oceňované jednotky bity. Předpokládá se, že ${ displaystyle Q_ {c} ^ {(c)} (t) = 0}$ pro všechny ${ displaystyle c in {1, ldots, N }}$ a všechny časové sloty t, protože žádný uzel neukládá data určená pro sebe. Každý časový úsek mohou uzly přenášet data ostatním. Data, která jsou přenášena z jednoho uzlu do druhého, jsou odstraněna z fronty prvního uzlu a přidána do fronty druhého. Data, která jsou přenášena na místo určení, jsou odstraněna ze sítě. Data mohou také do sítě dorazit exogenně a ${ displaystyle A_ {n} ^ {(c)} (t)}$ je definováno jako množství nových dat, která dorazí do uzlu n na slotu t které musí být nakonec doručeny do uzlu C.

Nechat ${ displaystyle mu _ {ab} (t)}$ být přenosová rychlost používaný sítí přes odkaz (A,b) na slotu t, představující množství dat, které může přenést z uzlu A do uzlu b na aktuálním slotu. Nechat ${ displaystyle ( mu _ {ab} (t))}$ být matice přenosové rychlosti. Tyto přenosové rychlosti musí být vybrány v rámci sady možných časově proměnných možností. Konkrétně může mít síť časově proměnné kanály a nodemobility, což může ovlivnit její přenosové schopnosti v každém slotu. S(t) představují stav topologie sítě, která zachycuje vlastnosti sítě na slotu t které ovlivňují přenos. Nechat ${ displaystyle Gamma _ {S (t)}}$ představují možnosti matice přenosové rychlosti přenosu dostupné ve stavu topologie S(tKaždý slot t, poznamenává síťový řadič S(t) a zvolí přenosové rychlosti ${ displaystyle ( mu _ {ab} (t))}$ v sadě ${ displaystyle Gamma _ {S (t)}}$Volba ${ displaystyle ( mu _ {ab} (t))}$ maticevybrat na každém slotu t je popsán v následující podkapitole.

Tento časově proměnný síťový model byl poprvé vyvinut pro případ, kdy byly přenosové rychlosti každého slotu t určeny obecnými funkcemi matice stavu kanálu a matice alokace energie.^[9] Model lze také použít, když jsou rychlosti určovány jinými rozhodnutími o řízení, jako je alokace serveru, výběr dílčího pásma, typ kódování atd. Předpokládá, že podporované přenosové rychlosti jsou známé a že nedochází k žádným chybám přenosu. Rozšířené formulace směrování protitlaku lze použít pro sítě s pravděpodobnými chybami kanálu, včetně sítí, které využívají výhody bezdrátového vysílání prostřednictvím rozmanitost více přijímačů.^[1]

Rozhodnutí o kontrole protitlaku

Každý slot t regulátor protitlaku dodržuje S(t) a provede následující 3 kroky:

• Nejprve pro každý odkaz (A,b), vybere optimální komodita ${ displaystyle c_ {ab} ^ {opt} (t)}$ použít.
• Dále určuje co ${ displaystyle ( mu _ {ab} (t))}$ matice v ${ displaystyle Gamma _ {S (t)}}$ použít.
• Nakonec určuje množství komodity ${ displaystyle c_ {ab} ^ {opt} (t)}$ bude přenášet přes odkaz (A,b) (maximálně ${ displaystyle mu _ {ab} (t)}$, ale v některých případech možná menší).

Výběr optimální komodity

Každý uzel A sleduje vlastní nevyřízené fronty a nevyřízené položky ve svých současných sousedech. A současný soused uzlu A je uzel b tak, že je možné zvolit nenulovou přenosovou rychlost ${ displaystyle mu _ {ab} (t)}$ sousedé jsou tedy určeni sadou ${ displaystyle Gamma _ {S (t)}}$. V extrémním případě může mít anoda vše N - 1 další uzly jako sousedé. Je však běžné používat sady ${ displaystyle Gamma _ {S (t)}}$ které vylučují přenosy mezi uzly, které jsou odděleny více než určitou geografickou vzdáleností, nebo které by měly šířenou sílu signálu pod určitou prahovou hodnotou. Je tedy typické, že počet sousedů je mnohem menší než N - 1. Příklad na obr. 1 ilustruje sousedy propojením, takže uzel 5 má sousedy 4 a 6. Příklad naznačuje symetrický vztah mezi sousedy (takže pokud 5 je sousedem 4, pak 4 je sousedem 5), ale obecně to tak nemusí být.

Sada sousedů daného uzlu určuje sadu odchozích odkazů, které může použít pro přenos na aktuálním slotu. Pro každý odchozí odkaz (A,b), optimální komodita ${ displaystyle c_ {ab} ^ {opt} (t)}$ je definována jako komodita ${ displaystyle c in {1, ldots, N }}$ který maximalizuje následující diferenciální nevyřízené položky Množství:

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

Veškeré vazby při výběru optimální komodity jsou přerušeny libovolně.

Obr. 2: Detailní pohled na uzly 1 a 2. Optimální komoditou pro odeslání přes linku (1,2) je zelená komodita. Optimální komoditou k odeslání v opačném směru (přes odkaz (2,1)) je modrá komodita.

Příklad je uveden na obr. 2. Příklad předpokládá, že každá fronta má v současné době pouze 3 komodity: Červené, zelená, amodrý, a ty se měří v celých jednotkách paketů. Se zaměřením na směrovaný odkaz (1,2) jsou rozdílné nevyřízené položky:

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

Proto je optimální komodita k odeslání přes odkaz (1,2) na slot t je zelená komodita. Na druhou stranu, optimální komodita pro odeslání přes zpětný odkaz (2,1) na slotu t je modrá komodita.

Výběr μ_ab(t) matice

Jakmile jsou pro každý odkaz stanoveny optimální komodity (A,b), síťový řadič vypočítá následující váhy ${ 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 vpravo]}$

Váha ${ displaystyle W_ {ab} (t)}$ je hodnota rozdílu nevyřízených položek spojená s optimální komoditou pro spojení (A,b), max. 0. Regulátor poté zvolí přenosové rychlosti jako řešení následujícího maximální hmotnost problém (libovolné přetržení vazeb):

${ displaystyle { text {(rovnice 1)}} qquad { text {maximalizovat:}} součet _ {a = 1} ^ {N} součet _ {b = 1} ^ {N} mu _ {ab} (t) W_ {ab} (t)}$

${ displaystyle { text {(Rov. 2)}} qquad { text {Předmět:}} ( mu _ {ab} (t)) v Gama _ {S (t)}}$

Jako příklad rozhodnutí o maximální hmotnosti předpokládejme, že na aktuálním slotu t, rozdílové nevyřízené položky na každém odkazu v síti se 6 uzly vedou k hmotnosti odkazů ${ displaystyle W_ {ab} (t)}$ dána:

${ 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 a 0 0 a 0 }$

Zatímco set ${ displaystyle Gamma _ {S (t)}}$ může obsahovat nespočetně nekonečné množství možných matic přenosové rychlosti, předpokládejme pro jednoduchost, že aktuální stav topologie připouští pouze 4 možné volby:

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

ilustrace 4 možných voleb přenosové rychlosti za aktuálního stavu topologie S(t). Možnost (a) aktivuje jediný odkaz (1,5) s přenosovou rychlostí ${ displaystyle mu _ {15} = 2}$. Všechny ostatní možnosti používají dva odkazy s přenosovými rychlostmi 1 na každém z aktivovaných odkazů.

Tyto čtyři možnosti jsou v maticové formě reprezentovány:

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

${ displaystyle { boldsymbol { mu}} _ {c} = left [{ begin {array} {cccccc} 0 a 0 a 0 a 0 a 0 0 1 & 0 a 0 a 0 a 0 0 a 0 a 0 a 0 a 0 & 0 0 & 0 & 0 & 0 & 0 0 & 0 & 0 & 0 & 1 & 0 0 a 0 a 0 a 0 a 0 right], quad { boldsymbol { mu}} _ {d} = left [{ begin {array} {cccccc} 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 & 0 & 0 & 0 & 0 a 0 pole}} doprava]}$

Všimněte si, že uzel 6 nemůže pod žádnou z těchto možností odesílat ani přijímat. To může nastat, protože uzel 6 je aktuálně mimo komunikační rozsah. Vážený součet sazeb pro každou ze 4 možností je:

• Volba (a): ${ displaystyle sum _ {ab} W_ {ab} (t) mu _ {ab} (t) = 12}$.
• Volba (b): ${ displaystyle sum _ {ab} W_ {ab} (t) mu _ {ab} (t) = 1}$.
• Volba (c): ${ displaystyle sum _ {ab} W_ {ab} (t) mu _ {ab} (t) = 1}$.
• Volba (d): ${ displaystyle sum _ {ab} W_ {ab} (t) mu _ {ab} (t) = 12}$.

Protože existuje remíza pro maximální váhu 12, může síťový řadič libovolně přerušit remízu výběrem jedné z možností ${ displaystyle { boldsymbol { mu}} _ {a}}$ nebo možnost ${ displaystyle { boldsymbol { mu}} _ {d}}$.

Dokončení směrovacích proměnných

Předpokládejme, že nyní optimální komodity ${ displaystyle c_ {ab} ^ {opt} (t)}$byly stanoveny pro každé spojení a přenosové rychlosti ${ displaystyle ( mu _ {ab} (t))}$ Byly také stanoveny. Pokud je rozdíl nevyřízených pro optimální komoditu na daném odkazu (A,b) je negativní, pak se přes tento odkaz na aktuální pozici nepřenášejí žádná data. Jinak síť nabízí k odeslání ${ displaystyle mu _ {ab} (t)}$ komoditní jednotky ${ displaystyle c_ {ab} ^ { mathrm {opt}} (t)}$data přes tento odkaz. To se provádí definováním směrovací proměnné${ displaystyle mu _ {ab} ^ {(c)} (t)}$ pro každý odkaz (A,b) a každou komoditu C, kde:

${ 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 {jinak}} end {případy}}}$

Hodnota ${ displaystyle mu _ {ab} ^ {(c)} (t)}$ představuje přenosovou rychlost nabízenou komoditě C data přes odkaz (A,b) na slotu tUzly však nemusí mít dostatek určité komodity, aby podporovaly přenos za nabízené sazby na všech jejich odchozích odkazech. To vzniká na slotu t pro uzel n a zboží C li:

${ displaystyle Q_ {n} ^ {(c)} (t) < součet _ {b = 1} ^ {N} mu _ {nb} ^ {(c)} (t)}$

V tomto případě všechny ${ displaystyle Q_ {n} ^ {(c)} (t)}$ data se odesílají a nulová data se používají k vyplnění nevyužitých částí nabízených sazeb, alokace skutečných dat a nulových dat libovolně k alokaci odpovídajících odchozích odkazů (podle nabízených sazeb). podtečení fronty situace. Taková podtečení neovlivňují vlastnosti stability propustnosti sítě. Intuitivně je to proto, že podtečení vzniká, když má vysílací uzel malé množství nevyřízených položek, což znamená, že potom uzlu nehrozí nestabilita.

Zlepšení zpoždění

Algoritmus protitlaku nepoužívá žádné předem určené cesty. Cesty se učí dynamicky a mohou se u různých paketů lišit. Zpoždění může být velmi velké, zvláště když je systém lehce zatěžován, takže není dostatečný tlak na to, aby tlačil data směrem k cíli. Jako příklad předpokládejme, že jeden paket zadá síť a nic jiného nikdy nevstoupí. Tento paket může procházet sítí po smyčce a nikdy nedorazit do cíle, protože se nevytvoří žádné tlakové přechody. To není v rozporu s optimalizací propustnosti nebo stabilitních vlastností protitlaku, protože síť má nanejvýš jeden paket kdykoli, a proto je triviálně stabilní (dosažení rychlosti doručení 0, která se rovná rychlosti příchodu).

Je také možné implementovat protitlak na sadu předem určených cest. To může omezit oblast kapacity, ale může to zlepšit doručení a zpoždění v pořadí. Dalším způsobem, jak zlepšit zpoždění, aniž by to ovlivnilo kapacitní region, je použít vylepšenéverze, která předpojatě spojuje váhy směrem k žádoucímu směru.^[9] Simulace takového předpětí ukázaly významné zlepšení zpoždění.^[1][3]Všimněte si, že protitlak nevyžaduje First-in-First-Out (FIFO ) služba ve frontách. Bylo pozorováno, že Last-in-First-Out (LIFO ) služba může dramaticky zlepšit zpoždění drtivé většiny paketů, aniž by to ovlivnilo propustnost.^[7][14]

Distribuovaný protitlak

Všimněte si, že jakmile přenosové rychlosti ${ displaystyle ( mu _ {ab} (t))}$ byly vybrány proměnné rozhodování o směrování${ displaystyle mu _ {ab} ^ {(c)} (t)}$lze vypočítat jednoduchým distribuovaným způsobem, kde každý uzel vyžaduje pouze znalost rozdílu nevyřízených front mezi sebou a jeho sousedy. Výběr přenosových rychlostí však vyžaduje řešení problému maximální hmotnosti v rovinách. (1) - (2). Ve zvláštním případě, kdy jsou kanály ortogonální, má algoritmus přirozenou distribuovanou implementaci a redukuje se na samostatná rozhodnutí v každém uzlu. Problém s maximální hmotností je však problémem centralizovaného řízení pro sítě s mezikanálovým rušením. Může být také velmi obtížné to vyřešit i centralizovaným způsobem.

Distribuovaný přístup k interferenčním sítím s rychlostmi spojení, které jsou určeny poměrem signálu k šumu a interferenci (SINR), lze provést pomocí randomizace.^[9] Každý uzel se náhodně rozhodne vyslat každý slot t (přenos „nulového“ paketu, pokud aktuálně nemá paket k odeslání). Skutečné přenosové rychlosti a odpovídající skutečné pakety, které se mají odeslat, jsou určeny dvoufázovým potřesením rukou: V prvním kroku náhodně vybrané vysílací uzly posílají pilotní signál se silou signálu úměrnou síle skutečného přenosu. Ve druhém kroku všechny potenciální uzly přijímače měří výsledné rušení a odesílají tyto informace zpět do vysílačů. Úrovně SINR pro všechny odchozí odkazy (n,b) jsou pak známy všem uzlům na každý uzel n může rozhodnout ${ displaystyle mu _ {nb} (t)}$ a ${ displaystyle ( mu _ {nb} ^ {(c)} (t))}$ proměnné založené na těchto informacích. Výsledná propustnost nemusí být nutně optimální. Proces náhodného přenosu však lze považovat za součást procesu stavu kanálu (za předpokladu, že v případech podtečení jsou odesílány nulové pakety, takže proces stavu kanálu nezávisí na minulých rozhodnutích). Výsledná propustnost této distribuované implementace je tedy optimální ve třídě všech směrovacích a plánovacích algoritmů, které používají takové náhodné přenosy.

Alternativní distribuované implementace lze zhruba rozdělit do dvou tříd: První třída algoritmů zohledňuje aproximace konstantních multiplikativních faktorů problému maximální váhy a poskytuje výsledky propustnosti konstantních faktorů. Druhá třída algoritmů zvažuje aditivní aproximace problému maximální váhy na základě aktualizace řešení problému maximální hmotnosti v průběhu času. Zdá se, že algoritmy v této druhé třídě vyžadují statické podmínky kanálu a delší (často nepolynomiální) doby konvergence, i když prokazatelně mohou dosáhnout maximální propustnosti za vhodných předpokladů.^[15][4][13] Aditivní aproximace jsou často užitečné pro prokázání optimality protitlaku při implementaci pomocí zastaralých informací o nevyřízených frontách (viz Cvičení 4.10 textu Neely).^[13]

Matematická konstrukce pomocí driftu Lyapunov

Tato část ukazuje, jak algoritmus protitlaku vzniká jako přirozený důsledek toho, že se velmi minimalizuje omezení změny součtu čtverců nevyřízených front z jednoho slotu na druhý.^[9][3]

Omezení řízení a rovnice aktualizace fronty

Zvažte víceskokovou síť s N uzly, jak je popsáno ve výše uvedené části. Každý slot t, síťový řadič sleduje stav topologie S(t) a vybrané přenosové rychlosti ${ displaystyle ( mu _ {ab} (t))}$ a směrování proměnných${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ s výhradou následujících omezení:

${ displaystyle { text {(rovnice 3)}} qquad ( mu _ {ab} (t)) v gama _ {S (t)}}$

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

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

Jakmile jsou tyto směrovací proměnné určeny, jsou prováděny přenosy (je-li to nutné, použijte nečinnou výplň) a výsledné fronty zpětných hlášení splňují následující podmínky:

${ displaystyle { text {(rovnice 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)}$

kde ${ displaystyle A_ {n} ^ {(c)} (t)}$ je náhodné množství nové komodity Cdata, která exogenně dorazí do uzlu n na slotu t, a ${ displaystyle mu _ {nb} ^ {(c)} (t)}$ je přenosová rychlost přidělená komoditě C provoz na odkazu (n,b) na slotu t. Všimněte si, že ${ displaystyle mu _ {nb} ^ {(c)} (t)}$ může být více než množství ubytování C data, která jsou skutečně přenášena na linku (A,b) na slotu t. Je to proto, že nemusí existovat dostatek uzlu backlogin n. Ze stejného důvodu rovnice. (6) je spíše nerovnost než rovnost, protože${ displaystyle sum _ {a = 1} ^ {N} mu _ {an} ^ {(c)} (t)}$ může být více než skutečné endogenní příchody komodit C do uzlu n na slotu tDůležitou vlastností ekv. (6) je, že platí, i když ${ displaystyle mu _ {ab} ^ {(c)} (t)}$ rozhodovací proměnné jsou vybírány nezávisle na nevyřízených frontách.

Předpokládá se, že ${ displaystyle Q_ {c} ^ {(c)} (t) = 0}$ pro všechny sloty t a všechno ${ displaystyle c in {1, ldots, N }}$, protože žádná fronta neukládá data určená pro sebe.

Lyapunov drift

Definovat ${ displaystyle { boldsymbol {Q}} (t) = (Q_ {n} ^ {(c)} (t))}$ jako matice aktuálních nevyřízených front Definujte následující nezápornou funkci nazvanou a Lyapunovova funkce:

${ displaystyle L (t) = { frac {1} {2}} součet _ {n = 1} ^ {N} součet _ {c = 1} ^ {N} Q_ {n} ^ {(c )} (t) ^ {2}}$

Jedná se o součet čtverců nevyřízených front (vynásobený 1/2 pouze pro pohodlí při pozdější analýze). Výše uvedený součet je stejný jako součet všech n, c takhle ${ displaystyle n neq c}$ protože ${ displaystyle Q_ {c} ^ {(c)} (t) = 0}$ pro všechny ${ displaystyle c in {1, ldots, N }}$ a všechny sloty t.

The podmíněný Lyapunov drift ${ displaystyle Delta (t)}$ je definováno:

${ displaystyle Delta (t) = E doleva [L (t + 1) -L (t) střední { boldsymbol {Q}} (t) doprava)}$

Všimněte si, že následující nerovnost platí pro všechny ${ 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)}$

Srovnáním rovnice aktualizace fronty (rovnice (6)) a použitím výše uvedené nerovnosti není těžké ukázat, že pro všechny sloty t a pod jakýmkoli algoritmem pro výběr proměnných přenosu a směrování ${ displaystyle ( mu _ {ab} (t))}$a ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$:^[3]

${ displaystyle { text {(rovnice 7)}} qquad Delta (t) leq B + součet _ {n = 1} ^ {N} součet _ {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) vpravo] }$

kde B je konečná konstanta, která závisí na druhých okamžicích příchodu a maximálních možných druhých okamžicích přenosových rychlostí.

Minimalizace driftu vázaného přepínáním součtů

Algoritmus protitlaku je navržen k pozorování ${ displaystyle { boldsymbol {Q}} (t)}$ aS(t) každý slot t a vybrat ${ displaystyle ( mu _ {ab} (t))}$ a ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ minimalizovat pravou stranu driftu vázaného ekv. (7). Protože B je konstanta a ${ displaystyle lambda _ {n} ^ {(c)}}$ jsou konstanty, to znamená maximalizaci:

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

kde konečné částky byly prosazeny očekáváními, aby osvětlily maximalizační rozhodnutí. Principem oportunisticky maximalizuje očekávání, výše uvedené očekávání je maximalizováno maximalizací funkce uvnitř něj (vzhledem k pozorovanému ${ displaystyle { boldsymbol {Q}} (t)}$, ${ displaystyle S (t)}$Jeden si tedy vybere ${ displaystyle ( mu _ {ab} (t))}$ a ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$s výhradou omezení Rovnice (3) - (5) pro maximalizaci:

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

Není okamžitě zřejmé, jaká rozhodnutí maximalizují výše uvedené. To lze osvětlit přepínáním součtů. Výše ​​uvedený výraz je ve skutečnosti stejný jako níže:

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

Váha ${ displaystyle Q_ {a} ^ {(c)} (t) -Q_ {b} ^ {(c)} (t)}$ se nazývá proud diferenciální nevyřízené položky zboží C mezi uzly A a b. Cílem je vybrat rozhodovací proměnné ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ tak, aby se maximalizoval váhový součet, kde váhy jsou rozdílné nevyřízené položky. To intuitivně znamená přidělení větších sazeb ve směru většího rozdílu nevyřízených položek.

Jednoznačně by si měl vybrat ${ displaystyle mu _ {ab} ^ {(c)} (t) = 0}$kdykoli ${ displaystyle Q_ {a} ^ {(c)} (t) -Q_ {b} ^ {(c)} (t) <0}$. Dále, vzhledem k tomu ${ displaystyle mu _ {ab} (t)}$ pro konkrétní odkaz ${ displaystyle (a, b)}$, není těžké ukázat, že optimální ${ displaystyle mu _ {ab} ^ {(c)} (t)}$ výběry, s výhradou ekv. (3) - (5), jsou určeny následovně: Nejprve najděte komoditu ${ displaystyle c_ {ab} ^ {opt} (t) in {1, ldots, N }}$že maximalizuje rozdíl nevyřízených položek pro odkaz (A,bPokud je maximalizace rozdílu nevyřízených záporných pro odkaz (A,b),přiřadit ${ displaystyle mu _ {ab} ^ {(c)} (t) = 0}$ pro všechny komodity ${ displaystyle c in {1, ldots, N }}$na odkazu (A,b). Jinak přidělte rychlost celého odkazu ${ displaystyle mu _ {ab} (t)}$ na komoditu ${ displaystyle c_ {ab} ^ {opt} (t)}$a nulová sazba pro všechny ostatní komodity na tomto odkazu. Z této volby vyplývá, že:

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

kde ${ displaystyle W_ {ab} (t)}$ je rozdíl nevyřízených položek optimální komodity pro odkaz (A,b) na slotu t (max. s 0):

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

Zbývá jen vybrat ${ displaystyle ( mu _ {ab} (t)) v gama _ {S (t)}}$. To se děje řešením následujících:

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

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

Výše uvedený problém je totožný s problémem maximální hmotnosti v Eqs. (1) - (2) algoritmus protitlaku používá rozhodnutí o maximální hmotnosti pro ${ displaystyle ( mu _ {ab} (t))}$a poté zvolí proměnné směrování ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ prostřednictvím maximálního rozdílu nevyřízených položek, jak je popsáno výše.

Pozoruhodnou vlastností algoritmu protitlaku je, že chamtivě působí na každý slot t pouze na základě pozorovaného stavu topologie S(t) a nevyřízené fronty ${ displaystyle { boldsymbol {Q}} (t)}$ pro tento slot. Nevyžaduje tedy znalost míry příjezdu ${ displaystyle ( lambda _ {n} ^ {(c)})}$ nebo pravděpodobnosti stavu topologie ${ displaystyle pi _ {S} = Pr [S (t) = S]}$.

Analýza výkonu

Tato část dokazuje propustnost optimality algoritmu protitlaku.^[3][13] Pro zjednodušení je uvažován scénář, kdy jsou události nezávislé a identicky distribuované (i.i.d.) na sloty, i když lze ukázat, že stejný algoritmus funguje i v jiných než i.i.d. scénáře (viz níže níže) Jiné než i. provoz a univerzální plánování ).

Dynamické příjezdy

Nechat ${ displaystyle (A_ {n} ^ {(c)} (t))}$ být maticí exogenních příjezdů do slotu t. Předpokládejme, že tato matice je nezávislá a identicky rozdělená (i.i.d.) na sloty s konečnými sekundovými momenty a prostředky:

${ displaystyle lambda _ {n} ^ {(c)} = E vlevo [A_ {n} ^ {(c)} (t) vpravo]}$

Předpokládá se, že ${ displaystyle lambda _ {c} ^ {(c)} = 0}$ pro všechny ${ displaystyle c in {1, ldots, N }}$, protože nedorazí žádná data, která jsou určena sama sobě. Tedy matice příchozích sazeb ${ displaystyle ( lambda _ {n} ^ {(c)})}$ je ${ displaystyle N krát N}$ matice nezáporných reálných čísel s nulami na úhlopříčce.

Region kapacity sítě

Předpokládejme stav topologie S(t) je i.i.d. s automaty s pravděpodobností ${ displaystyle pi _ {S} = Pr [S (t) = S]}$(li S(t) bere tedy hodnoty v nespočetně nekonečné sadě vektorů se skutečnými hodnotami ${ displaystyle pi _ {S}}$ je rozdělení pravděpodobnosti, nikoli hmotnostní funkce pravděpodobnosti). Obecný algoritmus pro síť dodržuje S(t) každý slot t a volí přenosové rychlosti ${ displaystyle ( mu _ {ab} (t))}$ a směrování proměnných ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ podle omezení v rovnicích. (3) - (5). The oblast kapacity sítě ${ displaystyle Lambda}$ je uzavření sady všech matic míry příchodu ${ displaystyle ( lambda _ {n} ^ {(c)})}$ pro které existuje algoritmus, který stabilizuje síť. Stabilita všech front znamená, že celková vstupní rychlost provozu do sítě je stejná jako celková rychlost dat dodávaných do jejího cíle. Je možné ukázat, že pro jakoukoli matici rychlosti příjezdu ${ displaystyle ( lambda _ {n} ^ {(c)})}$ v kapacitním regionu ${ displaystyle Lambda}$, tady je stacionární a randomizovaný algoritmus který vybírá rozhodovací proměnné ${ displaystyle ( mu _ {ab} ^ {*} (t))}$ a ${ displaystyle ( mu _ {ab} ^ {* (c)} (t))}$každý slot t pouze na základě S(t) (a tedy nezávisle na nevyřízených frontách), která pro všechny přináší následující ${ displaystyle n neq c}$:^[9][13]

${ displaystyle { text {(rovnice 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}$

Takový stacionární a randomizovaný algoritmus, který zakládá rozhodnutí pouze na S(t) se nazývá an Algoritmus pouze S. To je často užitečné předpokládat ${ displaystyle ( lambda _ {n} ^ {(c)})}$ je interiér na ${ displaystyle Lambda}$, takže existuje ${ displaystyle epsilon> 0}$ takhle ${ displaystyle ( lambda _ {n} ^ {(c)} + epsilon 1_ {n} ^ {(c)}) v Lambda}$, kde ${ displaystyle 1_ {n} ^ {(c)}}$ je 1, pokud ${ displaystyle n neq c}$a nic jiného. V takovém případě existuje S- pouze algoritmus, který poskytuje následující pro všechny ${ displaystyle n neq c}$:

${ displaystyle { text {(rovnice 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}$

Jako technický požadavek se předpokládá, že druhé momenty přenosových rychlostí ${ displaystyle mu _ {ab} (t)}$ jsou konečné podle jakéhokoli algoritmu pro výběr těchto sazeb. Toto triviálně platí, pokud existuje konečná maximální rychlost ${ displaystyle mu _ {max}}$.

Ve srovnání s algoritmy pouze S

Protože algoritmus protitlaku pozoruje ${ displaystyle { boldsymbol {Q}} (t)}$ a S(t) každý slot t a vybírá rozhodnutí ${ displaystyle ( mu _ {ab} (t))}$ a ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ minimalizovat pravou stranu driftu vázaného ekv. (7), máme:

${ displaystyle { text {(rovnice 10)}} qquad Delta (t) leq B + součet _ {n = 1} ^ {N} součet _ {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) že jo]}$

kde ${ displaystyle ( mu _ {ab} ^ {*} (t))}$ a ${ displaystyle ( mu _ {ab} ^ {* (c)} (t))}$jsou alternativní rozhodnutí, která uspokojí ekv. (3) - (5), včetně randomizovaných rozhodnutí.

Nyní předpokládejme ${ displaystyle ( lambda _ {n} ^ {(c)}) v Lambda}$. Pak existuje S-jen algoritmus, který vyhovujeEq. (8). Zapojením na pravou stranu ekv. (10) a bere na vědomí, že je dáno podmíněné očekávání ${ displaystyle { boldsymbol {Q}} (t)}$ pod tím S- pouze algoritmus je stejný jako bezpodmínečné očekávání (protože S(t) je i.i.d. přes sloty a S- pouze algoritmus je nezávislý na aktuálních nevyřízených frontách) výnosy:

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

Thus, the drift of a quadratic Lyapunov function is less than or equal to a constant B for all slots t. This fact, together with the assumption that queue arrivals have bounded second moments, imply the following for all network queues:^[16]

${displaystyle lim _{t ightarrow infty }{frac {Q_{n}^{(c)}(t)}{t}}=0{ ext{ 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 ightarrow infty }{frac {1}{t}}sum _{ au =0}^{t-1}sum _{n=1}^{N}sum _{c=1}^{N}Eleft[Q_{n}^{(c)}( au ) ight]leq {frac {B}{epsilon }}}$

This average queue size bound increases as the distance ${ displaystyle epsilon}$ to the boundary of thecapacity region ${ displaystyle Lambda}$ jde na nulu. 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}$, kde ${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. situacích. 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 technika.^[10][11][3] This technique greedily maximizes a sum of drift and a weighted penalty expression. The penalty is weighted by a parameter PROTI that determines a performance tradeoff. This technique ensures throughput utility is within Ó(1/PROTI) of optimality while average delay is Ó(PROTI). 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/PROTI), Ó(PROTI) utility-delay results.

Viz také

• AODV
• Diversity backpressure routing (DIVBAR)^[1]
• Drift plus penalty
• ExOR
• Geographic routing
• Seznam směrovacích protokolů ad hoc
• Lyapunov optimization

Reference

Primární zdroje

• L. Tassiulas and A. Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks," Transakce IEEE na automatickém ovládání, sv. 37, č. 12, pp. 1936–1948, Dec. 1992.
• L. Georgiadis, M. J. Neely, and L. Tassiulas, "Resource Allocation and Cross-Layer Control in Wireless Networks," Základy a trendy v oblasti sítí, sv. 1, č. 1, pp. 1–149, 2006.
• M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010.