Geri basınç yönlendirme - Backpressure routing - Wikipedia

İçinde kuyruk teorisi matematiksel bir disiplin olasılık teorisi, geri basınç yönlendirme algoritması maksimum ağ verimine ulaşan bir kuyruk ağı etrafındaki trafiği yönlendirmek için bir yöntemdir,^[1] kavramları kullanılarak kurulan Lyapunov kayması. Geri basınç yönlendirme, her bir işin ağdaki birden çok hizmet düğümünü ziyaret edebileceği durumu dikkate alır. Bu bir uzantısıdır maksimum ağırlık planlaması her işin yalnızca tek bir hizmet düğümünü ziyaret ettiği yer.

Giriş

Geri basınç yönlendirme tıkanıklık gradyanlarını kullanarak trafiği çok sekmeli bir ağ üzerinden dinamik olarak yönlendirmek için bir algoritmadır. Algoritma, aşağıdakiler dahil kablosuz iletişim ağlarına uygulanabilir: sensör ağları, mobil ad hoc ağlar (MANETLER ) ve kablosuz ve kablolu bileşenlere sahip heterojen ağlar.^[2][3]

Geri basınç ilkeleri, ürün montaj sistemleri ve işleme ağlarının incelenmesi gibi diğer alanlara da uygulanabilir.^[4]Bu makale, birden çok veri akışından gelen paketlerin geldiği ve uygun hedeflere teslim edilmesi gereken iletişim ağlarına odaklanmaktadır. Geri basınç algoritması yarıklı zamanda çalışır. Her zaman dilimi, veriyi en üst düzeye çıkaran yönlerde yönlendirmeye çalışır. diferansiyel birikim komşu düğümler arasında. Bu, suyun basınç değişimleri yoluyla bir boru ağından nasıl aktığına benzer. Bununla birlikte, geri basınç algoritması, çok mallı ağlara (farklı paketlerin farklı hedeflere sahip olabileceği yerlerde) ve iletim hızlarının bir dizi (muhtemelen zamanla değişen) seçeneklerden seçilebildiği ağlara uygulanabilir. Geri basınç algoritmasının çekici özellikleri şunlardır: (i) maksimum ağ verimliliğine yol açar, (ii) zamanla değişen ağ koşullarına karşı dayanıklı olduğu kanıtlanır, (iii) trafik geliş oranları veya kanal durum olasılıkları bilinmeden uygulanabilir. Bununla birlikte, algoritma büyük gecikmelere neden olabilir ve belki de tam olarak parazitli ağlarda uygulanması zor olabilir. Gecikmeyi azaltan ve uygulamayı basitleştiren geri basınç değişiklikleri aşağıda açıklanmıştır. Gecikmeyi iyileştirmek ve Dağıtılmış karşı basınç.

Geri basınç yönlendirme esas olarak teorik bir bağlamda incelenmiştir. Uygulamada, özel kablosuz ağlar tipik olarak en kısa yol hesaplamalarına veya ağ taşmasına dayanan alternatif yönlendirme yöntemlerini uygulamıştır.Ad Hoc İsteğe Bağlı Uzaklık Vektörü Yönlendirme (AODV),coğrafi yönlendirme, ve son derece fırsatçı yönlendirme Bununla birlikte, geri basıncın matematiksel optimallik özellikleri, Güney Kaliforniya Üniversitesi ve Kuzey Carolina Eyalet Üniversitesi'ndeki kablosuz test yatakları üzerindeki kullanımının son deneysel gösterilerini motive etti.^[5][6][7]

Kökenler

Orijinal geri basınç algoritması Tassiulas ve Ephremides tarafından geliştirilmiştir.^[2] Düşündüler çoklu atlama rastgele paket varışları ve sabit bir dizi bağlantı seçim seçeneği olan paket radyo ağı. Algoritmaları bir maksimum ağırlık bağlantısı seçimi sahne ve bir farklı biriktirme listesi yönlendirme Awerbuch ve Leighton'da, çok mallı ağ akışlarını hesaplamak için tasarlanmış karşı basınçla ilgili bir algoritma geliştirildi.^[8]Geri basınç algoritması daha sonra Neely, Modiano ve Rohrs tarafından mobil ağlar için programlamayı ele almak üzere genişletildi.^[9]Geri basınç, teorisi aracılığıyla matematiksel olarak analiz edilir. Lyapunov kayması ve ağ hizmetini maksimize etmek için akış kontrol mekanizmalarıyla birlikte kullanılabilir.^{[10][11][3][12][13]}(Ayrıca bakınız Şebeke optimizasyonu ve ceza minimizasyonu ile geri basınç ).

Nasıl çalışır

Geri basınç yönlendirme, bir zaman diliminden diğerine ağdaki kuyruk biriktirme günlüklerinin karelerinin toplamını (kabaca) en aza indiren kararlar almak için tasarlanmıştır. Bu tekniğin kesin matematiksel gelişimi sonraki bölümlerde anlatılmıştır. Bu bölüm, genel ağ modelini ve bu modele göre geri basınç yönlendirmesinin işleyişini açıklamaktadır.

Çok sekmeli kuyruk ağı modeli

Şekil 1: 6 düğümlü çok ağlı bir ağ. Düğümler arasındaki oklar, mevcut komşuları gösterir.

Çok sekmeli bir ağ düşünün N düğümler (bir örnek için Şekil 1'e bakın) N = 6). Ağ, dilimli zamanı çalıştırır ${ displaystyle t in {0,1,2, ldots }}$. Her yuvada, ağa yeni veriler ulaşabilir ve tüm verileri uygun hedefine ulaştırmak için yönlendirme ve iletim programlama kararları verilir. Düğüm için hedeflenen verilere izin verin ${ displaystyle c in {1, noktalar, N }}$ olarak etiketlenmek emtia c verileri. Her düğümdeki veriler, mallarına göre saklanır. İçin ${ displaystyle n in {1, ldots, N }}$ ve ${ displaystyle c in {1, ldots, N }}$, İzin Vermek ${ displaystyle Q_ {n} ^ {(c)} (t)}$ mevcut emtia miktarı c düğümdeki veriler n, aynı zamanda kuyruk biriktirme listesi. Bir düğüm içindeki kuyruk biriktirmelerinin bir yakından görünümü Şekil 2'de gösterilmektedir. ${ displaystyle Q_ {n} ^ {(c)} (t)}$ sorunun bağlamına bağlıdır.Örneğin, biriktirme listesi tam sayı birimlerini alabilir. paketler, verilerin sabit uzunlukta paketlere bölündüğü durumlarda kullanışlıdır. Alternatif olarak, gerçek değerli birimleri alabilir bitler. Varsayılmaktadır ki ${ displaystyle Q_ {c} ^ {(c)} (t) = 0}$ hepsi için ${ displaystyle c in {1, ldots, N }}$ ve tüm zaman dilimleri tçünkü hiçbir düğüm kendisine yönelik verileri depolamaz. Her zaman dilimi, düğümler verileri başkalarına iletebilir. Bir düğümden diğerine iletilen veriler, birinci düğümün kuyruğundan çıkarılır ve ikinci düğümün kuyruğuna eklenir. Hedefine iletilen veriler ağdan kaldırılır. Veriler ayrıca ağa dışsal olarak da gelebilir ve ${ displaystyle A_ {n} ^ {(c)} (t)}$ düğüme gelen yeni veri miktarı olarak tanımlanır n yuvada t sonunda düğüme teslim edilmesi gerekir c.

İzin Vermek ${ displaystyle mu _ {ab} (t)}$ ol aktarım hızı ağ tarafından bağlantı üzerinden kullanılır (a,b) yuvada t, düğümden aktarabileceği veri miktarını temsil eder a düğüme b geçerli yuvada. İzin Vermek ${ displaystyle ( mu _ {ab} (t))}$ iletim hızı matrisi olabilir. Bu aktarım hızları, muhtemelen zamanla değişen bir dizi seçenek içinde seçilmelidir. Spesifik olarak, ağın zamanla değişen kanallara ve nodemobilitesine sahip olabilir ve bu, iletim yeteneklerini her yuvaya etkileyebilir. S(t) temsil eder topoloji durumu ağın özelliklerini yuvadaki ağın özelliklerini yakalayan t iletimi etkileyen. İzin Vermek ${ displaystyle Gama _ {S (t)}}$ topoloji durumu altında mevcut olan iletim hızı matrisi seçeneklerini temsil eder S(tHer yuva tağ denetleyicisi gözlemler S(t) ve iletim oranlarını seçer ${ displaystyle ( mu _ {ab} (t))}$ set içinde ${ displaystyle Gama _ {S (t)}}$. Hangisinin seçimi ${ displaystyle ( mu _ {ab} (t))}$ her yuvada seçmek için matris t sonraki alt bölümde açıklanmaktadır.

Bu zamanla değişen ağ modeli ilk olarak, her dilim t iletim hızlarının bir kanal durum matrisinin ve bir güç tahsis matrisinin genel fonksiyonları tarafından belirlendiği durum için geliştirilmiştir.^[9] Model ayrıca, oranlar sunucu tahsisi, alt bant seçimi, kodlama türü ve benzeri gibi diğer kontrol kararları tarafından belirlendiğinde de kullanılabilir. Desteklenebilir aktarım hızlarının bilindiğini ve aktarım hatası olmadığını varsayar. Geri basınç yönlendirmesinin genişletilmiş formülasyonları, kablosuz yayın avantajını kullanarak kablosuz yayın avantajından yararlanan ağlar dahil, olasılıklı kanal hataları olan ağlar için kullanılabilir. çoklu alıcı çeşitliliği.^[1]

Geri basınç kontrol kararları

Her yuva t geri basınç kontrolörü gözlemler S(t) ve aşağıdaki 3 adımı gerçekleştirir:

• İlk olarak, her bağlantı için (a,b), bir optimal emtia ${ displaystyle c_ {ab} ^ {opt} (t)}$ kullanmak.
• Sonra, ne olduğunu belirler ${ displaystyle ( mu _ {ab} (t))}$ matris içinde ${ displaystyle Gama _ {S (t)}}$ kullanmak.
• Son olarak, emtia miktarını belirler ${ displaystyle c_ {ab} ^ {opt} (t)}$ bağlantı üzerinden iletecek (a,b) (en fazla ${ displaystyle mu _ {ab} (t)}$, ancak bazı durumlarda muhtemelen daha azdır).

En uygun emtiayı seçmek

Her düğüm a kendi kuyruk biriktirme günlüklerini ve mevcut komşularındaki birikmiş günlükleri gözlemler. Bir mevcut komşu düğümün a bir düğüm b sıfır olmayan bir iletim hızı seçmek mümkün olacak şekilde ${ displaystyle mu _ {ab} (t)}$ mevcut yuvada. bu nedenle, komşular set tarafından belirlenir ${ displaystyle Gama _ {S (t)}}$. Aşırı durumda, anot her şeye sahip olabilir N - Komşu olarak 1 diğer düğüm. Bununla birlikte, setleri kullanmak yaygındır ${ displaystyle Gama _ {S (t)}}$ belirli bir coğrafi uzaklıktan daha fazla ayrılan veya belirli bir eşiğin altında yayılan sinyal gücüne sahip olan düğümler arasındaki iletimleri engelleyen, bu nedenle, komşuların sayısının çok daha az olması tipiktir. N - 1. Şekil 1'deki örnek, bağlantı bağlantılarıyla komşuları gösterir, böylece düğüm 5, komşuları 4 ve 6'ya sahiptir. Örnek, komşular arasında simetrik bir ilişki önerir (böylece 5, 4'ün komşusuysa, 4, 5), ancak genel olarak durumun böyle olması gerekmez.

Belirli bir düğümün komşu kümesi, geçerli aralıkta iletim için kullanabileceği giden bağlantılar kümesini belirler. Her giden bağlantı için (a,b), optimal emtia ${ displaystyle c_ {ab} ^ {opt} (t)}$ emtia olarak tanımlanır ${ displaystyle c in {1, ldots, N }}$ aşağıdakileri maksimize eden diferansiyel birikim miktar:

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

En uygun emtia seçimindeki herhangi bir bağ keyfi olarak koparılır.

Şekil 2: 1. ve 2. düğümlerin kısa bir özeti. Bağlantı (1, 2) üzerinden gönderilecek en uygun emtia yeşil metadır. Diğer yönde (bağlantı (2, 1) üzerinden) gönderilecek en uygun emtia mavi emtiadır.

Şekil 2'de bir örnek gösterilmektedir. Örnek, her bir kuyruğun şu anda yalnızca 3 mala sahip olduğunu varsaymaktadır: kırmızı, yeşil, vemavive bunlar tamsayı paket birimleriyle ölçülür. Yönlendirilmiş bağlantıya (1,2) odaklanıldığında, farklı biriktirme listeleri şunlardır:

${ displaystyle Q_ {1} ^ {({ text {kırmızı}})} (t) -Q_ {2} ^ {({ text {kırmızı}})} (t) = 1}$

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

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

Bu nedenle, yuvadaki bağlantı (1,2) üzerinden göndermek için en uygun emtia t yeşil metadır. Öte yandan, yuva üzerindeki ters bağlantı (2,1) üzerinden göndermek için en uygun emtia t mavi emtia.

Seçmek μ_ab(t) matris

Her bağlantı için en uygun mallar belirlendikten sonra (a,b), ağ denetleyicisi aşağıdaki ağırlıkları hesaplar ${ displaystyle W_ {ab} (t)}$:

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

Ağırlık ${ displaystyle W_ {ab} (t)}$ bağlantı için en uygun emtia ile ilişkili farklı birikimin değeridir (a,b), 0 ile maks. Kontrolör daha sonra aşağıdakilerin çözümü olarak iletim hızlarını seçer. maksimum ağırlık sorun (keyfi olarak bağları koparmak):

${ displaystyle { text {(Denklem 1)}} qquad { text {Büyüt:}} sum _ {a = 1} ^ {N} sum _ {b = 1} ^ {N} mu _ {ab} (t) W_ {ab} (t)}$

${ displaystyle { text {(Eşitlik 2)}} qquad { text {Konu:}} ( mu _ {ab} (t)) in Gama _ {S (t)}}$

Maksimum ağırlık kararına bir örnek olarak, mevcut aralıkta t6 düğümlü ağın her bir bağlantısındaki farklı biriktirme listeleri, bağlantı ağırlıklarına yol açar ${ displaystyle W_ {ab} (t)}$ veren:

${ displaystyle (W_ {ab} (t)) = sol [{ başla {dizi} {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 & end 0 & end }$

Set iken ${ displaystyle Gama _ {S (t)}}$ sayılamayacak kadar sonsuz sayıda olası iletim hızı matrisi içerebilir, basit olması için mevcut topoloji durumunun yalnızca 4 olası seçeneği kabul ettiğini varsayın:

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

mevcut topoloji durumu altında olası 4 aktarım hızı seçiminin resmi S(t). Seçenek (a), tek bağlantıyı (1,5), bir iletim hızı ile etkinleştirir. ${ displaystyle mu _ {15} = 2}$. Diğer tüm seçenekler, etkinleştirilen bağlantıların her birinde 1 iletim hızına sahip iki bağlantı kullanır.

Bu dört olasılık matris biçiminde şu şekilde temsil edilir:

${ displaystyle { boldsymbol { mu}} _ {a} = sol [{ begin {array} {cccccc} 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 & 0 & 0 & 0 0 & 0 & 0 & 0 & 0 & 0 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 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & dizi}} sağ]}$

${ displaystyle { boldsymbol { mu}} _ {c} = sol [{ 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 & 0 & 0 & 1 & 0 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 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 & 0 & 0 & 0 & 0 & 0 & 0 0 & 0 & 0 & 0 & 0 & 0 & 0 ve dizi}} sağ]}$

6 nolu düğümün bu olasılıklardan herhangi biri altında ne gönderebildiğini ne alabildiğini gözlemleyin. 6 nolu düğüm şu anda iletişim aralığının dışında olduğu için bu ortaya çıkabilir. 4 olasılığın her biri için ağırlıklı oranların toplamı:

• Seçenek (a): ${ displaystyle toplamı _ {ab} W_ {ab} (t) mu _ {ab} (t) = 12}$.
• Seçenek (b): ${ displaystyle toplamı _ {ab} W_ {ab} (t) mu _ {ab} (t) = 1}$.
• Seçenek (c): ${ displaystyle toplamı _ {ab} W_ {ab} (t) mu _ {ab} (t) = 1}$.
• Seçilmiş): ${ displaystyle toplamı _ {ab} W_ {ab} (t) mu _ {ab} (t) = 12}$.

Maksimum 12 ağırlık için bir bağ olduğundan, ağ denetleyicisi her iki seçenekten birini seçerek bağı keyfi olarak bozabilir. ${ displaystyle { boldsymbol { mu}} _ {a}}$ veya seçenek ${ displaystyle { boldsymbol { mu}} _ {d}}$.

Yönlendirme değişkenlerinin sonlandırılması

Şimdi varsayalım ki en uygun mallar ${ displaystyle c_ {ab} ^ {opt} (t)}$her bağlantı için belirlenmiş ve iletim hızları ${ displaystyle ( mu _ {ab} (t))}$ Belirli bir bağlantıdaki optimal emtia için farklı birikim varsa (a,b) negatifse, geçerli yuvada bu bağlantı üzerinden veri aktarılmaz. Aksi takdirde, ağ göndermeyi teklif eder ${ displaystyle mu _ {ab} (t)}$ emtia birimleri ${ displaystyle c_ {ab} ^ { mathrm {opt}} (t)}$bu bağlantı üzerinden veri. Bu tanımlanarak yapılır yönlendirme değişkenleri${ displaystyle mu _ {ab} ^ {(c)} (t)}$ her bağlantı için (a,b) ve her emtia c, nerede:

${ displaystyle mu _ {ab} ^ {(c)} (t) = { başla {vakalar} mu _ {ab} (t) & { text {if}} c = c_ {ab} ^ { opt} (t) { text {ve}} Q_ {a} ^ {(c_ {ab} ^ {opt} (t))} (t) -Q_ {b} ^ {(c_ {ab} ^ {opt } (t))} (t) geq 0 0 & { text {aksi halde}} end {vakalar}}}$

Değeri ${ displaystyle mu _ {ab} ^ {(c)} (t)}$ emtiaya sunulan iletim oranını temsil eder c bağlantı üzerinden veri (a,b) yuvada tBununla birlikte, düğümler, tüm giden bağlantılarında sunulan oranlarda iletimi desteklemek için yeterli mala sahip olmayabilir. Bu yuvada ortaya çıkıyor t düğüm için n ve emtia c Eğer:

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

Bu durumda, tümü ${ displaystyle Q_ {n} ^ {(c)} (t)}$ veriler gönderilir ve boş veriler, sunulan oranların kullanılmayan kısımlarını doldurmak, gerçek verileri ve boş verileri keyfi olarak karşılık gelen giden bağlantılar üzerinden (sunulan oranlara göre) tahsis etmek için kullanılır. kuyruk alt akışı durum. Bu tür alt akışlar, ağın kullanıcı kararlılık özelliklerini etkilemez. Sezgisel olarak, bunun nedeni, yalnızca ileten düğümün düşük miktarda birikim kaydına sahip olduğu zaman ortaya çıkmasıdır; bu, düğümün kararsızlık tehlikesi olmadığı anlamına gelir.

Gecikmeyi iyileştirmek

Geri basınç algoritması önceden belirlenmiş herhangi bir yolu kullanmaz. Yollar dinamik olarak öğrenilir ve farklı paketler için farklı olabilir. Gecikme, özellikle sistem hafifçe yüklendiğinde, verileri hedefe doğru itmek için yeterli baskı olmadığında çok büyük olabilir. Örnek olarak, bir paketin ağa girdiğini ve başka hiçbir şeyin girmediğini varsayalım. Bu paket, ağda döngüsel bir yürüyüşe çıkabilir ve hiçbir zaman hedefine varmayabilir çünkü basınç gradyanları oluşmaz. Bu, geri basıncın verim optimalliği veya kararlılık özellikleriyle çelişmez, çünkü ağ herhangi bir zamanda en fazla bir pakete sahiptir ve bu nedenle önemsiz bir şekilde kararlıdır (varış hızına eşit, 0'lık bir teslim hızına ulaşılır).

Bir dizi önceden belirlenmiş yol üzerinde geri basınç uygulamak da mümkündür. Bu, kapasite bölgesini kısıtlayabilir, ancak sipariş içi teslimatı ve gecikmeyi iyileştirebilir. Kapasite bölgesini etkilemeden gecikmeyi iyileştirmenin bir başka yolu, bir geliştirilmişağırlıkları istenen yönlere doğru yönlendiren versiyon.^[9] Bu tür önyargının simülasyonları, önemli gecikme iyileştirmeleri göstermiştir.^[1][3]Geri basıncın İlk Giren İlk Çıkar (FIFO ) kuyruklarda hizmet. Son Giren İlk Çıkar'ın (LIFO ) hizmet, verimi etkilemeden paketlerin büyük çoğunluğu için gecikmeyi önemli ölçüde artırabilir.^[7][14]

Dağıtılmış karşı basınç

Aktarım hızlarının ${ displaystyle ( mu _ {ab} (t))}$ seçildi, yönlendirme karar değişkenleri${ displaystyle mu _ {ab} ^ {(c)} (t)}$basit dağıtılmış bir şekilde hesaplanabilir, burada her bir düğüm yalnızca kendisiyle komşuları arasındaki sıra birikimi farklılıkları hakkında bilgi gerektirir. Bununla birlikte, iletim hızlarının seçimi, Denklemlerdeki maksimum ağırlık problemine bir çözüm gerektirir. (1) - (2). Kanalların ortogonal olduğu özel durumda, algoritma doğal olarak dağıtılmış bir uygulamaya sahiptir ve her düğümde ayrı kararlara indirgenir. Bununla birlikte, maksimum ağırlık sorunu, kanallar arası parazitli ağlar için merkezi bir kontrol sorunudur. Ayrıca merkezi bir şekilde bile çözmek çok zor olabilir.

Sinyal-gürültü artı interefernans oranı (SINR) tarafından belirlenen bağlantı hızlarına sahip girişim ağları için dağıtılmış bir yaklaşım, rasgele seçim kullanılarak gerçekleştirilebilir.^[9] Her düğüm rastgele olarak her yuvayı iletmeye karar verir t (şu anda gönderilecek bir paket yoksa "boş" paket iletmek). Gerçek aktarım hızları ve gönderilecek karşılık gelen gerçek paketler, 2 adımlı bir el sıkışma ile belirlenir: İlk aşamada, rastgele seçilen verici düğümleri, gerçek bir iletiminki ile orantılı sinyal gücüne sahip bir pilot sinyal gönderir. İkinci adımda, tüm potansiyel alıcı düğümleri ortaya çıkan girişimi ölçer ve bu bilgiyi aktarıcılara geri gönderir. Tüm giden bağlantılar için SINR seviyeleri (n,b) daha sonra tüm düğümler tarafından bilinir nve her düğüm n karar verebilir ${ displaystyle mu _ {nb} (t)}$ ve ${ displaystyle ( mu _ {nb} ^ {(c)} (t))}$ Bu bilgiye dayalı değişkenler. Ortaya çıkan verim mutlaka optimal değildir. Bununla birlikte, rastgele iletim süreci, kanal durum sürecinin bir parçası olarak görülebilir (boş paketlerin yetersiz paketlerin gönderilmesi koşuluyla, kanal durum süreci geçmiş kararlara bağlı kalmaz). Bu nedenle, bu dağıtılmış uygulamanın sonuçta elde edilen verimi, bu tür rastgele iletimleri kullanan tüm yönlendirme ve programlama algoritmaları sınıfı üzerinde optimaldir.

Alternatif dağıtılmış uygulamalar kabaca iki sınıfa ayrılabilir: Birinci sınıf algoritmalar, maksimum ağırlık problemine sabit çarpan faktör yaklaşımlarını dikkate alır ve sabit faktörlü çıktı sonuçları verir. İkinci sınıf algoritmalar, maksimum ağırlık problemine zaman içinde çözümleri güncellemeye dayalı olarak maksimum ağırlık problemine ek yaklaşımları dikkate alır. Bu ikinci sınıftaki algoritmalar, statik kanal koşulları ve daha uzun (genellikle polinom olmayan) yakınsama süreleri gerektiriyor gibi görünmektedir, ancak uygun varsayımlar altında kanıtlanabilir bir şekilde maksimum verim elde edebilirler.^[15][4][13] İlave yaklaşımlar, güncel olmayan kuyruk biriktirme listesi bilgileriyle uygulandığında geri basıncın optimal olduğunu kanıtlamak için genellikle yararlıdır (bkz. Neely metni, Alıştırma 4.10).^[13]

Lyapunov drift yoluyla matematiksel yapı

Bu bölüm, bir yuvadan diğerine kuyruk biriktirme listelerinin karelerinin toplamındaki değişimin genel olarak en aza indirilmesinin doğal bir sonucu olarak geri basınç algoritmasının nasıl ortaya çıktığını gösterir.^[9][3]

Karar kısıtlamalarını ve kuyruk güncelleme denklemini kontrol edin

Çok sekmeli bir ağ düşünün N düğümler, yukarıdaki bölümde açıklandığı gibi. t, ağ denetleyicisi topoloji durumunu gözlemler S(t) ve seçme aktarım oranları ${ displaystyle ( mu _ {ab} (t))}$ ve yönlendirme değişkenleri${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ aşağıdaki kısıtlamalara tabidir:

${ displaystyle { text {(Denklem 3)}} qquad ( mu _ {ab} (t)) in Gama _ {S (t)}}$

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

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

Bu yönlendirme değişkenleri belirlendikten sonra, iletimler yapılır (gerekirse boşta doldurma kullanılarak) ve ortaya çıkan kuyruk günlükleri aşağıdakileri karşılar:

${ displaystyle { text {(Eşitlik 6)}} qquad Q_ {n} ^ {(c)} (t + 1) leq max sol [Q_ {n} ^ {(c)} (t ) - toplam _ {b = 1} ^ {N} mu _ {nb} ^ {(c)} (t), 0 sağ] + toplamı _ {a = 1} ^ {N} mu _ {an} ^ {(c)} (t) + A_ {n} ^ {(c)} (t)}$

nerede ${ displaystyle A_ {n} ^ {(c)} (t)}$ yeni malın rastgele miktarı ceksojen olarak düğüme gelen veriler n yuvada t, ve ${ displaystyle mu _ {nb} ^ {(c)} (t)}$ emtiaya tahsis edilen iletim oranı c bağlantıdaki trafik (n,b) yuvada t. Bunu not et ${ displaystyle mu _ {nb} ^ {(c)} (t)}$ emtia miktarından fazla olabilir c aslında bağlantı üzerinden iletilen veriler (a,b) yuvada t. Bunun nedeni, yeterli backlogin düğümü olmayabilmesidir n. Aynı nedenle, Denk. (6) bir eşitlikten ziyade bir eşitsizliktir, çünkü${ displaystyle toplamı _ {a = 1} ^ {N} mu _ {an} ^ {(c)} (t)}$ emtianın gerçek içsel gelişlerinden daha fazlası olabilir c düğüme n yuvada tDenklemin önemli bir özelliği. (6), ${ displaystyle mu _ {ab} ^ {(c)} (t)}$ karar değişkenleri kuyruk biriktirme listelerinden bağımsız olarak seçilir.

Varsayılmaktadır ki ${ displaystyle Q_ {c} ^ {(c)} (t) = 0}$ tüm slotlar için t ve tüm ${ displaystyle c in {1, ldots, N }}$hiçbir kuyruk kendisine yönelik verileri depolamadığından.

Lyapunov kayması

Tanımlamak ${ displaystyle { boldsymbol {Q}} (t) = (Q_ {n} ^ {(c)} (t))}$ mevcut kuyruk biriktirme listelerinin matrisi olarak. a adı verilen aşağıdaki negatif olmayan işlevi tanımlayın. Lyapunov işlevi:

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

Bu, kuyruk biriktirme listelerinin karelerinin toplamıdır (daha sonraki analizlerde kolaylık olması açısından 1/2 ile çarpılır). Yukarıdaki toplam, tümünün toplamı ile aynıdır n, c öyle ki ${ displaystyle n neq c}$ Çünkü ${ displaystyle Q_ {c} ^ {(c)} (t) = 0}$ hepsi için ${ displaystyle c in {1, ldots, N }}$ ve tüm yuvalar t.

koşullu Lyapunov kayması ${ displaystyle Delta (t)}$ tanımlanmış:

${ displaystyle Delta (t) = E sol [L (t + 1) -L (t) orta { boldsymbol {Q}} (t) sağ]}$

Aşağıdaki eşitsizliğin tümü için geçerli olduğuna dikkat edin ${ 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)}$

Kuyruk güncelleme denkleminin (Denklem (6)) karesini alarak ve yukarıdaki eşitsizliği kullanarak, tüm slotlar için bunu göstermek zor değildir. t ve iletim ve yönlendirme değişkenlerini seçmek için herhangi bir algoritma altında ${ displaystyle ( mu _ {ab} (t))}$ve ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$:^[3]

${ displaystyle { text {(Denklem 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) - toplam _ {b = 1} ^ {N} mu _ {nb} ^ {(c)} (t) | { kalın sembol {Q}} (t) sağ] }$

nerede B ikinci varış anlarına ve aktarım hızlarının olası maksimum ikinci anlarına bağlı olan sonlu bir sabittir.

Toplamları değiştirerek sürüklenme sınırını en aza indirme

Geri basınç algoritması gözlemlemek için tasarlanmıştır ${ displaystyle { boldsymbol {Q}} (t)}$ veS(t) her yuva t ve Seç ${ displaystyle ( mu _ {ab} (t))}$ ve ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ sürüklenmeye bağlı Denklemin sağ tarafını en aza indirmek için. (7). Çünkü B sabittir ve ${ displaystyle lambda _ {n} ^ {(c)}}$ sabitler, bu maksimize eder:

${ displaystyle E sol [ toplamı _ {n = 1} ^ {N} toplamı _ {c = 1} ^ {N} Q_ {n} ^ {(c)} (t) sol [ toplamı _ {b = 1} ^ {N} mu _ {nb} ^ {(c)} (t) - toplam _ {a = 1} ^ {N} mu _ {an} ^ {(c)} ( t) sağ] | { kalın sembol {Q}} (t) sağ]}$

maksimize edici kararı aydınlatmak için sonlu toplamların beklentiler üzerinden itildiği yer. fırsatçı olarak bir beklentiyi maksimize etmekYukarıdaki beklenti, içindeki işlevi maksimuma çıkararak maksimize edilir (gözlenen ${ displaystyle { boldsymbol {Q}} (t)}$, ${ displaystyle S (t)}$Böylece kişi seçer ${ displaystyle ( mu _ {ab} (t))}$ ve ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$kısıtlamalara tabi Denklemler. (3) - (5) maksimize etmek için:

${ displaystyle toplamı _ {n = 1} ^ {N} toplamı _ {c = 1} ^ {N} Q_ {n} ^ {(c)} (t) sol [ toplamı _ {b = 1 } ^ {N} mu _ {nb} ^ {(c)} (t) - toplam _ {a = 1} ^ {N} mu _ {an} ^ {(c)} (t) sağ ]}$

Hangi kararların yukarıdakileri maksimize ettiği hemen belli değildir. Bu, toplamları değiştirerek aydınlatılabilir. Aslında yukarıdaki ifade aşağıdaki ile aynıdır:

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

Ağırlık ${ displaystyle Q_ {a} ^ {(c)} (t) -Q_ {b} ^ {(c)} (t)}$ Akım denir diferansiyel birikim emtia c düğümler arası a ve b. Fikir, karar değişkenlerini seçmektir ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ ağırlıklar farklı birikmiş işler olduğunda yukarıda belirtilen toplamı maksimize etmek için. Sezgisel olarak bu, daha büyük farklı birikimlerin yönlerine daha büyük oranlar tahsis etmek anlamına gelir.

Açıkça biri seçmeli ${ displaystyle mu _ {ab} ^ {(c)} (t) = 0}$her ne zaman ${ displaystyle Q_ {a} ^ {(c)} (t) -Q_ {b} ^ {(c)} (t) <0}$. Dahası, verilen ${ displaystyle mu _ {ab} (t)}$ belirli bir bağlantı için ${ displaystyle (a, b)}$optimum olduğunu göstermek zor değil ${ displaystyle mu _ {ab} ^ {(c)} (t)}$ seçimler, Denklemlere tabidir. (3) - (5) aşağıdaki gibi belirlenir: Önce malı bulun ${ displaystyle c_ {ab} ^ {opt} (t) in {1, ldots, N }}$o farklı birikimi en üst düzeye çıkarır bağlantı için (a,bMaksimize eden fark birikimi bağlantı için negatifse (a,b),atamak ${ displaystyle mu _ {ab} ^ {(c)} (t) = 0}$ tüm mallar için ${ displaystyle c in {1, ldots, N }}$bağlantıda (a,b). Aksi takdirde, tam bağlantı oranını tahsis edin ${ displaystyle mu _ {ab} (t)}$ metaya ${ displaystyle c_ {ab} ^ {opt} (t)}$ve bu bağlantıdaki diğer tüm metalara sıfır oran. Bu seçimle şunu takip eder:

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

nerede ${ displaystyle W_ {ab} (t)}$ bağlantı için optimal emtianın farklı birikimidir (a,b) yuvada t (0 ile maks.):

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

Sadece seçmek için kalır ${ displaystyle ( mu _ {ab} (t)) içinde Gama _ {S (t)}}$. Bu, aşağıdakileri çözerek yapılır:

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

${ displaystyle mathrm {Konu:} ( mu _ {ab} (t)) içinde Gama _ {S (t)}}$

Yukarıdaki problem, Denklemlerdeki maksimum ağırlık problemiyle aynıdır. (1) - (2). geri basınç algoritması maks. ağırlık kararlarını kullanır ${ displaystyle ( mu _ {ab} (t))}$ve ardından yönlendirme değişkenlerini seçer ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ yukarıda açıklandığı gibi maksimum fark birikimi aracılığıyla.

Geri basınç algoritmasının dikkate değer bir özelliği, her yuvaya açgözlülükle davranmasıdır. t sadece gözlemlenen topoloji durumuna göre S(t) ve biriktirme listeleri ${ displaystyle { boldsymbol {Q}} (t)}$ bu yuva için. Böylece varış oranları hakkında bilgi sahibi olmayı gerektirmez. ${ displaystyle ( lambda _ {n} ^ {(c)})}$ veya topoloji durum olasılıkları ${ displaystyle pi _ {S} = Pr [S (t) = S]}$.

Performans analizi

Bu bölüm, geri basınç algoritmasının verim optimalliğini kanıtlamaktadır.^[3][13] Basitlik açısından, olayların bağımsız olduğu ve yuvalar üzerinden aynı şekilde dağıtıldığı (i.i.d.) senaryo dikkate alınır, ancak aynı algoritmanın i.i.d olmayanlarda çalıştığı gösterilebilir. senaryolar (aşağıya bakın) Non-i.i.d. operasyon ve evrensel çizelgeleme ).

Dinamik gelenler

İzin Vermek ${ displaystyle (A_ {n} ^ {(c)} (t))}$ yuvadaki dışsal gelişlerin matrisi olun t. Bu matrisin bağımsız olduğunu ve sonlu saniye momentli yuvalara ve araçlara aynı şekilde dağıtıldığını (i.i.d.) varsayalım:

${ displaystyle lambda _ {n} ^ {(c)} = E sol [A_ {n} ^ {(c)} (t) sağ]}$

Olduğu varsayılmaktadır ${ displaystyle lambda _ {c} ^ {(c)} = 0}$ hepsi için ${ displaystyle c in {1, ldots, N }}$Kendisine yönelik hiçbir veri gelmediğinden. Böylece, varış oranlarının matrisi ${ displaystyle ( lambda _ {n} ^ {(c)})}$ bir ${ displaystyle N times N}$ köşegende sıfırlar ile negatif olmayan gerçek sayıların matrisi.

Ağ kapasitesi bölgesi

Topoloji durumunu varsayın S(t) i.i.d. olasılıklı alanlar üzerinden ${ displaystyle pi _ {S} = Pr [S (t) = S]}$(Eğer S(t) gerçek değerli girdilerle sayılamayacak kadar sonsuz bir vektörler kümesindeki değerleri alır, sonra ${ displaystyle pi _ {S}}$ bir olasılık dağılımıdır, bir olasılık kütle fonksiyonu değildir). Ağ için genel bir algoritma gözlemler S(t) her yuva t ve iletim hızlarını seçer ${ displaystyle ( mu _ {ab} (t))}$ ve yönlendirme değişkenleri ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ Denklemlerdeki kısıtlamalara göre. (3) - (5). ağ kapasitesi bölgesi ${ displaystyle Lambda}$ tüm varış hızı matrisleri kümesinin kapanmasıdır ${ displaystyle ( lambda _ {n} ^ {(c)})}$ bunun için ağı stabilize eden bir algoritma vardır. Tüm kuyrukların kararlılığı, ağa gelen trafiğin toplam giriş hızının, hedefine teslim edilen toplam veri hızı ile aynı olduğu anlamına gelir. Herhangi bir varış hızı matrisi için gösterilebilir ${ displaystyle ( lambda _ {n} ^ {(c)})}$ kapasite bölgesinde ${ displaystyle Lambda}$, var sabit ve rastgele algoritma karar değişkenlerini seçen ${ displaystyle ( mu _ {ab} ^ {*} (t))}$ ve ${ displaystyle ( mu _ {ab} ^ {* (c)} (t))}$her yuva t sadece dayalı S(t) (ve dolayısıyla kuyruk biriktirme listelerinden bağımsız olarak) tümü için aşağıdakileri verir: ${ displaystyle n neq c}$:^[9][13]

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

Sadece kararları temel alan böyle sabit ve rastgele bir algoritma S(t) denir Yalnızca S algoritması. Genellikle şunu varsaymak yararlıdır: ${ displaystyle ( lambda _ {n} ^ {(c)})}$ dır-dir iç -e ${ displaystyle Lambda}$, böylece bir ${ displaystyle epsilon> 0}$ öyle ki $Lambda} içinde { displaystyle ( lambda _ {n} ^ {(c)} + epsilon 1_ {n} ^ {(c)})$, nerede ${ displaystyle 1_ {n} ^ {(c)}}$ 1 ise ${ displaystyle n neq c}$ve başka sıfır. Bu durumda, bir S- tümü için aşağıdakileri veren tek algoritma ${ displaystyle n neq c}$:

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

Teknik bir gereklilik olarak, iletim hızlarının ikinci anlarının ${ displaystyle mu _ {ab} (t)}$ bu oranları seçmek için herhangi bir algoritma altında sonludur. Sonlu bir maksimum oran varsa bu önemsiz şekilde geçerlidir ${ displaystyle mu _ {max}}$.

Yalnızca S algoritmalarıyla karşılaştırma

Geri basınç algoritması gözlemlediğinden ${ displaystyle { boldsymbol {Q}} (t)}$ ve S(t) her yuva t ve kararları seçer ${ displaystyle ( mu _ {ab} (t))}$ ve ${ displaystyle ( mu _ {ab} ^ {(c)} (t))}$ sürüklenmeye bağlı Denklemin sağ tarafını en aza indirmek için. (7), bizde:

${ displaystyle { text {(Denklem 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) - toplam _ {b = 1} ^ {N} mu _ {nb} ^ {* (c)} (t) | { boldsymbol {Q}} (t) sağ]}$

nerede ${ displaystyle ( mu _ {ab} ^ {*} (t))}$ ve ${ displaystyle ( mu _ {ab} ^ {* (c)} (t))}$Denklemleri karşılayan alternatif kararlardır. (3) - (5), rastgele kararlar dahil.

Şimdi varsayalım ${ displaystyle ( lambda _ {n} ^ {(c)}) Lambda'da}$. Sonra bir var S-Eq'i tatmin eden tek algoritma. (8). Bunu Denklemin sağ tarafına takmak. (10) ve verilen koşullu beklentinin ${ displaystyle { boldsymbol {Q}} (t)}$ bunun altında S-yalnızca algoritma, koşulsuz beklentiyle aynıdır (çünkü S(t) i.i.d. yuvalar üzerinde ve S-yalnızca algoritma, mevcut kuyruk biriktirme listelerinden bağımsızdır):

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

Bu nedenle, ikinci dereceden bir Lyapunov fonksiyonunun kayması, bir sabite eşit veya daha azdır. B tüm slotlar için 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}$ sıfıra gider. 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}$, nerede ${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. durumlar. 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-ceza tekniği.^[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.

Ayrıca bakınız

• AODV
• Diversity backpressure routing (DIVBAR)^[1]
• Drift artı ceza
• ExOR
• Coğrafi yönlendirme
• Geçici yönlendirme protokollerinin listesi
• Lyapunov optimizasyonu

Referanslar

Birincil kaynaklar

• L. Tassiulas and A. Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks," Otomatik Kontrolde IEEE İşlemleri, cilt. 37, hayır. 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, cilt. 1, hayır. 1, pp. 1–149, 2006.
• M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010.