Max-min rättvisa
Inom kommunikationsnätverk , multiplexering och uppdelning av knappa resurser sägs max-min rättvisa uppnås genom en tilldelning om och endast om tilldelningen är genomförbar och ett försök att öka tilldelningen av någon deltagare nödvändigtvis leder till att tilldelningen minskar . av någon annan deltagare med lika eller mindre tilldelning.
Vid bästa möjliga statistisk multiplexering används ofta en schemaläggningspolicy för först till kvarn ( FCFS). Fördelen med max-min rättvisa jämfört med FCFS är att det resulterar i trafikformning , vilket innebär att ett illa uppfört flöde, bestående av stora datapaket eller skurar av många paket, bara kommer att straffa sig själv och inte andra flöden. Nätöverbelastning undviks därför till viss del.
Fair queuing är ett exempel på en max-min fair paketschemaläggningsalgoritm för statistisk multiplexering och bästa ansträngningsnätverk, eftersom det ger schemaläggningsprioritet till användare som har uppnått lägsta datahastighet sedan de blev aktiva. I fallet med datapaket av samma storlek round-robin schemaläggning max-min rättvist.
Jämförelse med andra policyer för resursdelning
Generellt sett ger policyer för att dela resurser som kännetecknas av låg nivå av rättvisa (se rättvisa åtgärder ) hög genomsnittlig genomströmning men låg stabilitet i tjänstekvaliteten, vilket innebär att den uppnådda servicekvaliteten varierar i tid beroende på beteendet hos andra användare. Om denna instabilitet är allvarlig kan det leda till missnöjda användare som väljer en annan mer stabil kommunikationstjänst.
Max-min rättvis resursdelning resulterar i högre genomsnittlig genomströmning (eller systemspektral effektivitet i trådlösa nätverk) och bättre utnyttjande av resurserna än en arbetsbesparande policy för lika delning av resurserna. [ ytterligare förklaring behövs ] Vid lika delning kanske vissa dataflöden inte kan utnyttja sin "rättvisa andel" av resurserna. En policy för lika delning skulle förhindra ett dataflöde från att erhålla fler resurser än något annat flöde och från att använda lediga resurser i nätverket.
Å andra sidan ger max-min fairness lägre genomsnittlig genomströmning än maximal genomströmning resurshantering , där de billigaste flödena tilldelas all kapacitet de kan använda, och ingen kapacitet kanske finns kvar för de dyraste flödena. I ett trådlöst nätverk är en dyr användare vanligtvis en mobilstation på långt avstånd från basstationen, utsatt för hög signaldämpning. En policy för maximal genomströmning skulle dock leda till att dyra flöden svälter ut och kan resultera i färre "nöjda kunder".
En kompromiss mellan max-min-rättvisa och maximal genomströmningsplanering är proportionell rättvisa , där resurserna delas upp med målet att uppnå samma kostnad för varje användare, eller för att minimera den maximala kostnaden per enhet som ett dataflöde når. Dyra dataflöden uppnår lägre servicekvalitet än andra i proportionell rättvisa, men lider inte av svält. Max-min rättvisa resulterar i mer stabil servicekvalitet och därför kanske fler "nöjda kunder".
Max-min rättvis länkkapacitet förtilldelning
Max-min rättvisa i kommunikationsnätverk förutsätter att resurser (kapaciteten hos kommunikationslänkar) allokeras till flöden i förväg, till skillnad från bästa möjliga nätverk.
Tänk på i dataflöden , ibland kallade användare eller källor . Varje dataflöde har en definierad initialnod, en destinationsnod och en önskad datahastighet. Ett flöde på dess väg genom nätverket kan delas mellan "parallella" länkar i ett lastbalanseringsschema .
En allokeringsvektor x vars i -te koordinat är allokeringen för flöde i , dvs den hastighet med vilken användaren i tillåts sända ut data.
En tilldelning av taxa x är "max-min rättvis" om och endast om en höjning av någon kurs inom området för genomförbara tilldelningar måste ske till bekostnad av en minskning av någon redan mindre takt. Beroende på problemet kan en max-min rättvis tilldelning existera eller inte. Men om det finns är det unikt.
Namnet "max-min" kommer från idén att det är hastigheten för de mindre (eller minsta) flödena som görs så stora som möjligt (maximeras) av algoritmen. Därför ger vi högre relativ prioritet till små flöden. Först när ett flöde ber om att förbruka mer än C/N (länkkapacitet/antal flöden) löper det någon risk att få sin bandbredd strypt av algoritmen.
Flaskhalslänkar
En flaskhalslänk för ett dataflöde i är en länk som är fullt utnyttjad (är mättad ) och av alla flöden som delar denna länk uppnår dataflödet i total maximal datahastighet. Observera att denna definition skiljer sig väsentligt från en vanlig betydelse av en flaskhals . Observera också att denna definition inte förbjuder att en enda flaskhalslänk delas mellan flera flöden.
En datahastighetsallokering är max-min rättvis om och endast om ett dataflöde mellan två valfria noder har minst en flaskhalslänk.
Progressiv fyllningsalgoritm
Om resurser allokeras i förväg i nätverksnoderna kan max-min rättvisa erhållas genom att använda en algoritm för progressiv fyllning. Du börjar med alla hastigheter lika med 0 och växer alla hastigheter tillsammans i samma takt, tills en eller flera länkkapacitetsgränser nås. Priserna för de källor som använder dessa länkar höjs inte längre, och du fortsätter att höja priserna för andra källor. Alla källor som stoppas har en flaskhalslänk. Detta beror på att de använder en mättad länk, och alla andra källor som använder den mättade länken stoppas samtidigt, eller stoppades tidigare, har alltså en mindre eller lika stor hastighet. Algoritmen fortsätter tills det inte går att öka. Slutligen, när algoritmen avslutas, har alla källor stoppats någon gång och har därmed en flaskhalslänk. Denna tilldelning är max-min rättvis.
Se även
- Rättvisemått
- Schemaläggning i multitasking-operativsystem.
- Jämlik social valregel - att välja mellan alternativ utifrån max-min-principen.