Engset formel

I köteorin används Engset -formeln för att bestämma blockeringssannolikheten för en M/M/c/c/N-kö (i Kendalls notation ) .

Formeln är uppkallad efter dess utvecklare, TO Engset .

Exempelapplikation

Tänk på en flotta av $c$ -fordon och $N$ -operatörer. Operatörer går in i systemet slumpmässigt för att begära användning av ett fordon. Om inga fordon är tillgängliga, "blockeras" en begärande operatör (dvs operatören lämnar utan ett fordon). Ägaren av flottan skulle vilja välja $c$ liten för att minimera kostnaderna, men tillräckligt stor för att säkerställa att blockeringssannolikheten är acceptabel.

Formel

Låta

• $c>0$ vara (heltal) antalet servrar.
• $N>c$ vara (heltal) antalet trafikkällor;
• $\lambda >0$ vara den lediga källans ankomsthastighet (dvs. hastigheten med vilken en fri källa initierar förfrågningar);
• $h>0$ är den genomsnittliga hålltiden (dvs den genomsnittliga tid det tar för en server att hantera en begäran);

Sedan ges sannolikheten för blockering av

$P={\frac {{\binom {N-1}{c}}\left(\lambda h\right)^{c}}{\sum _{i=0}^{c}{\ binom {N-1}{i}}\left(\lambda h\right)^{i}}}.$

Genom att ordna om termer kan man skriva om ovanstående formel som

$P={\frac {1}{{}_{2}F_{1}(1,- c;Nc;-1/(\lambda h))}}$

där ${}_{2}F_{1}$ är Gaussisk hypergeometrisk funktion .

Beräkning

Det finns flera rekursioner som kan användas för att beräkna $P$ på ett numeriskt stabilt sätt.

Alternativt kan vilket numeriskt paket som helst som stöder den hypergeometriska funktionen användas. Några exempel ges nedan.

Python med SciPy

   
              från  scipy.special  import  hyp2f1  P  =  1,0  /  hyp2f1  (  1  ,  -  c  ,  N  -  c  ,  -  1,0  /  (  Lambda  *  h  )) 

MATLAB med Symbolic Math Toolbox

              P  =  1  /  hypergeom  ([  1  ,  -  c  ],  N  -  c  ,  -  1  /  (  Lambda  *  h  )) 

Ankomsthastighet för okänd källa

I praktiken är det ofta så att källankomsthastigheten $\lambda$ är okänd (eller svår att uppskatta) medan ${\displaystyle \alpha >0} ,$ den erbjudna trafiken per källa, är känd. I det här fallet kan man ersätta förhållandet

$\lambda h={\frac {\alpha }{1-\alpha (1-P)}}$

mellan källans ankomsthastighet och blockeringssannolikhet i Engset-formeln för att komma fram till fixpunktsekvationen

$P=f(P)$

var

$f(P)={\frac {1}{{}_{2}F_{1}(1,-c;Nc;1-P-1/\alpha )}}.$

Beräkning

Även om ovanstående tar bort det okända $\lambda$ från formeln, introducerar det ytterligare en komplexitetspunkt: vi kan inte längre beräkna blockeringssannolikheten direkt, utan måste använda en iterativ metod istället. Även om en iteration med fast punkt är frestande, har det visat sig att en sådan iteration ibland är divergerande när den tillämpas på $f$ . Alternativt är det möjligt att använda en av bisection eller Newtons metod , för vilken en implementering med öppen källkod är tillgänglig.