Maks-min adaleti - Max-min fairness

Olarak iletişim ağları , çoğullama ve kıt kaynaklarının bölünmesi, min-max eşitlik ayırma mümkündür, ancak ve ancak bir ayırma ve tahsis azalma zorunlu sonucu herhangi bir katılımcı tahsisini artırmak amacıyla ile elde edilebilir olduğu söylenir eşit veya daha küçük bir tahsise sahip başka bir katılımcının.

En iyi çaba istatistiksel çoğullamada , ilk gelen ilk hizmet alır (FCFS) zamanlama politikası sıklıkla kullanılır. Maksimum-min adaletinin FCFS'ye göre avantajı, trafik şekillendirme ile sonuçlanmasıdır , yani büyük veri paketlerinden veya birçok paketin patlamalarından oluşan kötü niyetli bir akışın diğer akışları değil, yalnızca kendisini cezalandıracağı anlamına gelir. Sonuç olarak ağ tıkanıklığı bir dereceye kadar önlenir.

Adil kuyruğa alma , istatistiksel çoğullama ve en iyi çaba gerektiren paket anahtarlamalı ağlar için bir max-min adil paket zamanlama algoritmasının bir örneğidir , çünkü aktif olduklarından beri en düşük veri hızına ulaşan kullanıcılara zamanlama önceliği verir. Eşit boyutta veri paketleri olması durumunda, döngüsel zamanlama , maksimum minimum düzeydedir.

Kaynak paylaşımı için diğer politikalarla karşılaştırma

Genel olarak, düşük düzeyde adalet ile karakterize edilen kaynakları paylaşma politikaları (bakınız adalet önlemleri ), hizmet kalitesinde yüksek ortalama verim ancak düşük istikrar sağlar, bu da elde edilen hizmet kalitesinin diğer kullanıcıların davranışlarına bağlı olarak zaman içinde değiştiği anlamına gelir. Bu istikrarsızlık şiddetli ise, daha kararlı başka bir iletişim hizmeti seçecek olan mutsuz kullanıcılarla sonuçlanabilir.

Maks-min adil kaynak paylaşımı, kaynakların işi koruyan eşit paylaşım politikasına göre daha yüksek ortalama çıktı (veya kablosuz ağlarda sistem spektral verimliliği ) ve kaynakların daha iyi kullanılmasıyla sonuçlanır . Eşit paylaşımda, bazı veri akışları kaynaklardan "adil paylarını" kullanamayabilir. Eşit paylaşım politikası, bir veri akışının diğer akışlardan daha fazla kaynak elde etmesini ve ağdaki ücretsiz kaynakları kullanmasını engeller.

Öte yandan, maks-min adaleti, en düşük maliyetli akışlara kullanabilecekleri tüm kapasitenin atandığı ve en pahalı akışlar için hiçbir kapasite kalmayabileceği maksimum aktarım hızı kaynak yönetiminden daha düşük ortalama aktarım hızı sağlar . Bir kablosuz ağda, pahalı bir kullanıcı, tipik olarak, yüksek sinyal zayıflamasına maruz kalan baz istasyonundan çok uzakta bulunan bir mobil istasyondur. Bununla birlikte, maksimum verim politikası , pahalı akışların aç kalmasına ve daha az "mutlu müşteri" ile sonuçlanabilir.

Maks-min adaleti ve maksimum verim planlaması arasındaki bir uzlaşma , kaynakların her kullanıcı için aynı maliyeti elde etme veya bir veri akışının ulaştığı birim başına maksimum maliyeti en aza indirme hedefiyle bölündüğü orantılı adalettir . Pahalı veri akışları, orantılı adalet içinde diğerlerinden daha düşük hizmet kalitesi elde eder, ancak açlıktan zarar görmez. Maks-min adaleti, daha istikrarlı hizmet kalitesi ve dolayısıyla belki de daha "mutlu müşteriler" ile sonuçlanır.

Maks-min adil bağlantı kapasitesi ön tahsisi

İletişim ağlarında maksimum-min adaleti, kaynakların (iletişim bağlantılarının kapasitelerinin) en iyi çaba gerektiren ağların aksine akışlara önceden tahsis edildiğini varsayar .

Düşünün i akar verileri , bazen denilen kullanıcıları veya kaynaklar . Her veri akışının tanımlanmış bir başlangıç ​​düğümü, bir hedef düğümü ve istenen bir veri hızı vardır. Ağ boyunca kendi yolundaki bir akış, bir yük dengeleme şemasında "paralel" bağlantılar arasında bölünebilir .

i- inci koordinatı, akış i için tahsis olan bir tahsis vektörü x , yani, i kullanıcısının veri yaymasına izin verilen oran .

x oranının tahsisi, ancak ve ancak uygulanabilir tahsisler alanındaki herhangi bir orandaki bir artışın, zaten daha küçük bir oranın düşüşü pahasına olması gerekiyorsa, "maksimum-min adil"dir. Soruna bağlı olarak, bir max-min adil tahsisi olabilir veya olmayabilir. Ancak, varsa, benzersizdir.

"Max-min" adı, algoritma tarafından mümkün olduğunca büyük (maksimumlaştırılmış) yapılan daha küçük (veya minimum) akışların oranı olduğu fikrinden gelir. Bu nedenle, küçük akışlara daha yüksek göreceli öncelik veriyoruz. Yalnızca bir akış C/N'den (bağlantı kapasitesi/akış sayısı) daha fazlasını tüketmeyi istediğinde, bant genişliğinin algoritma tarafından daraltılması riski vardır.

Darboğaz bağlantıları

Bir veri akışı i için bir darboğaz bağlantısı , tam olarak kullanılan ( doymuş ) bir bağlantıdır ve bu bağlantıyı paylaşan tüm akışlardan, veri akışı i, genel maksimum veri hızına ulaşır. Bu tanımın yaygın bir darboğaz anlamından önemli ölçüde farklı olduğuna dikkat edin . Ayrıca, bu tanımın birden çok akış arasında tek bir darboğaz bağlantısının paylaşılmasını yasaklamadığına dikkat edin.

Bir veri hızı tahsisi, yalnızca ve ancak herhangi iki düğüm arasındaki bir veri akışında en az bir darboğaz bağlantısı varsa, maksimum-min adildir.

Aşamalı doldurma algoritması

Ağ düğümlerinde kaynaklar önceden tahsis edilirse, aşamalı doldurma algoritması kullanılarak maksimum-min adaleti elde edilebilir. 0'a eşit tüm oranlarla başlarsınız ve bir veya birkaç bağlantı kapasitesi sınırına ulaşılana kadar tüm oranları aynı hızda birlikte büyütürsünüz. Bu bağlantıları kullanan kaynakların oranları artık artmaz ve diğer kaynaklar için oranları artırmaya devam edersiniz. Durdurulan tüm kaynakların bir darboğaz bağlantısı vardır. Bunun nedeni, doymuş bir bağlantı kullanmaları ve doymuş bağlantıyı kullanan diğer tüm kaynakların aynı anda durdurulması veya daha önce durdurulması, dolayısıyla daha küçük veya eşit bir orana sahip olmalarıdır. Algoritma, artırmak mümkün olmayana kadar devam eder. Son olarak, algoritma sona erdiğinde, tüm kaynaklar bir anda durdurulmuştur ve dolayısıyla bir darboğaz bağlantısına sahiptir. Bu tahsis, max-min adildir.

Ayrıca bakınız

Referanslar

Dış bağlantılar