Generaliserad processordelning

Generaliserad processordelning ( GPS ) är en idealisk schemaläggningsalgoritm för processschemaläggare och nätverksschemaläggare . Det är relaterat till principen om rättvis kö som grupperar paket i klasser och delar servicekapaciteten mellan dem. GPS delar denna kapacitet enligt vissa fasta vikter .

I processschemaläggning är GPS "en idealiserad schemaläggningsalgoritm som uppnår perfekt rättvisa. Alla praktiska schemaläggare approximerar GPS och använder den som en referens för att mäta rättvisa."

Generaliserad processordelning förutsätter att trafiken är flytande ( oändligt små paketstorlekar) och kan delas upp godtyckligt. Det finns flera tjänstediscipliner som spårar prestanda för GPS ganska noggrant, såsom viktad rättvis kö (WFQ), även känd som paket-för-paket generaliserad processordelning (PGPS).

Berättigande

I ett nätverk som internet kräver olika applikationstyper olika prestandanivåer. Till exempel är e-post en applikation som verkligen lagras och vidarebefordras , men det är inte videokonferenser eftersom det kräver låg latens . När paket står i kö i ena änden av en överbelastad länk har noden vanligtvis en viss frihet att bestämma i vilken ordning den ska skicka de köade paketen. Ett exempel på beställning är helt enkelt först till kvarn, först till kvarn , vilket fungerar bra om storleken på köerna är små, men kan resultera i problem om det finns latenskänsliga paket som blockeras av paket från spruckna applikationer med högre bandbredd.

Detaljer

konfigureras en schemaläggare som hanterar ${\displaystyle N} -flöden (även kallade "klasser", eller "sessioner") med en vikt$ $w_{i}$ för varje flöde. Sedan säkerställer GPS:en att, med tanke på ett flöde $i$ , och ett visst tidsintervall $(s,t]$ så att flödet $i$ kontinuerligt backloggas på detta intervall ( dvs. kön är aldrig tom), då, för alla andra flöden $j$ , gäller följande relation

w_{j}O_{i}(s,t)\geq w_{i}O_{j}(s,t)

där $O_{k}(s,t)$ anger mängden bitar av flödet $k$ som produceras på intervall $(s, t]$ .

Sedan kan det bevisas att varje flöde $i$ kommer att få åtminstone en hastighet

R_{i}={\frac {w_{i}}{\summa _{j=1}^{N}w_{j}}}R

där $R$ är serverns hastighet.

Detta är ett minimalt pris. Om något flöde inte använder sin bandbredd under en period delas denna kvarvarande kapacitet av de aktiva flödena med avseende på deras respektive vikter. Tänk till exempel på en GPS-server med $w_{1}=2,w_{2}=w_{3}=1$ . Det första flödet kommer att få minst hälften av kapaciteten, medan de andra två bara får $1/4$ . Ändå, om på något tidsintervall $(s,t]$ , bara det andra och tredje flödet är aktiva, kommer de att få vardera hälften av kapaciteten.

Implementeringar, parametrisering och rättvisa

I GPS, och alla protokoll inspirerade av GPS, överlåts valet av vikter till nätverksadministratören.

Generaliserad processordelning förutsätter att trafiken är flytande, dvs oändligt delbar så att närhelst en applikationstyp har paket i kön kommer den att ta emot exakt den del av servern som ges av formeln ovan. Trafiken är dock inte flytande och består av paket, möjligen av varierande storlek. Därför är GPS mestadels en teoretisk idé, och flera schemaläggningsalgoritmer har utvecklats för att approximera detta GPS-ideal: PGPS, aka Weighted fair queuing , är den mest kända implementeringen av GPS, men den har några nackdelar, och flera andra implementeringar har föreslagits , som Deficit round robin eller WF2Q.

GPS anses vara ett rättvist ideal, och alla dess approximationer "använder det som en referens för att mäta rättvisa." Ändå finns det flera rättvisa åtgärder .

GPS är okänslig för paketstorlekar, eftersom den antar en flytande modell.

Se även