Jackson nätverk

I köteori , en disciplin inom den matematiska sannolikhetsteorin, är ett Jackson-nätverk (ibland Jacksonian-nätverk ) en klass av könätverk där jämviktsfördelningen är särskilt enkel att beräkna eftersom nätverket har en produktformlösning . Det var den första betydande utvecklingen i teorin om nätverk av köer , och att generalisera och tillämpa teoremets idéer för att söka efter liknande produktformlösningar i andra nätverk har varit föremål för mycket forskning, inklusive idéer som används i utvecklingen av Internet. Nätverken identifierades först av James R. Jackson och hans artikel trycktes på nytt i tidskriften Management Sciences " Ten Most Influential Titles of Management Sciences First Fifty Years."

Jackson inspirerades av Burkes och Reichs arbete, även om Jean Walrand noterar "resultat i form av produkt ... [är] ett mycket mindre omedelbart resultat av outputteoremet än vad Jackson själv tycktes tro på hans grundläggande artikel".

En tidigare produktformlösning hittades av RRP Jackson för tandemköer (en ändlig kedja av köer där varje kund måste besöka varje kö i ordning) och cykliska nätverk (en slinga av köer där varje kund måste besöka varje kö i ordning).

Ett Jackson-nätverk består av ett antal noder, där varje nod representerar en kö där servicehastigheten kan vara både nodberoende (olika noder har olika servicehastigheter) och tillståndsberoende (servicehastigheterna ändras beroende på kölängder). Jobben färdas mellan noderna efter en fast routingmatris. Alla jobb på varje nod tillhör en enda "klass" och jobb följer samma servicetidsfördelning och samma routingmekanism. Följaktligen finns det ingen föreställning om prioritet när det gäller att betjäna jobben: alla jobb vid varje nod betjänas enligt först till kvarn- principen.

Jackson-nätverk där en begränsad population av jobb reser runt ett slutet nätverk har också en produktformlösning som beskrivs av Gordon-Newell-teoremet .

Nödvändiga förutsättningar för ett Jackson-nätverk

Ett nätverk med m sammankopplade köer är känt som ett Jackson-nätverk eller Jacksonian-nätverk om det uppfyller följande villkor:

1. om nätverket är öppet bildar alla externa ankomster till nod i en Poisson-process ,
2. Alla servicetider är exponentiellt fördelade och servicedisciplinen vid alla köer är först till kvarn, först till kvarn ,
3. en kund som slutför tjänsten i kö i kommer antingen att flytta till någon ny kö j med sannolikhet $P_{ij}$ eller lämna systemet med sannolikhet ${\displaystyle 1-\ summa _{j=1}^{m}P_{ij}} ,$ som för ett öppet nätverk är icke-noll för någon delmängd av köerna,
4. utnyttjandet av alla köerna är mindre än en .

Sats

I ett öppet Jackson-nätverk med m M/M/1-köer där utnyttjandet $\rho _{i}$ är mindre än 1 vid varje kö, existerar jämviktstillståndssannolikhetsfördelningen och för tillstånd $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$ ges av produkten av de individuella köjämviktsfördelningarna

$\pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi ​​_{i}(k_{i})= \prod _{i=1}^{m}[\rho _{i}^{k_{i}}(1-\rho _{i})].$

Resultatet $\pi (k_{1},k_{2},\ldots ,k_{m} )=\prod _{i=1}^{m}\pi ​​_{i}(k_{i})$ gäller även för M/M/c- modellstationer med c _i- servrar vid den $i^ {\text{th}}$ station, med användningskrav $\rho _{i}<c_{i}$ .

Definition

I ett öppet nätverk kommer jobb utifrån efter en Poisson-process med hastigheten $\alpha >0$ . Varje ankomst dirigeras oberoende till nod j med sannolikhet $p_{0j}\geq 0$ och $\sum _{j=1}^{J}p_ {0j}=1$ . När tjänsten är klar vid nod i kan ett jobb gå till en annan nod j med sannolikhet $p_{ij}$ eller lämna nätverket med sannolikhet $p_{i0}=1-\sum _{j=1}^{J}p_{ij}$ .

Därför har vi den totala ankomsthastigheten till nod i , $\lambda _{i}$ , inklusive både externa ankomster och interna övergångar:

$\lambda _{i}=\alpha p_{0i}+\sum _{j=1}^{J}\lambda _{j}p_{ji},i=1,\ldots , J.\qquad (1)$

(Eftersom utnyttjandet vid varje nod är mindre än 1, och vi tittar på jämviktsfördelningen, dvs. det långsiktiga genomsnittliga beteendet, begränsas hastigheten för jobb som övergår från j till i av en bråkdel av ankomsthastigheten vid j och vi ignorerar servicegraden $\mu _{j}$ i ovanstående.)

Definiera $a=(\alpha p_{0i})_{i=1}^{J}$ , då kan vi lösa $\lambda =(IP^{T})^{-1}a$ .

Alla jobb lämnar varje nod också efter Poisson-processen och definierar $\mu _{i}(x_{i})$ som servicehastigheten för nod i när det finns $x_ {i}$ jobb på nod i .

Låt $X_{i}(t)$ beteckna antalet jobb vid nod i vid tidpunkten t , och $\mathbf {X} =( X_{i})_{i=1}^{J}$ . Då är jämviktsfördelningen av $\mathbf {X}$ , $\pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )$ bestäms av följande system av balansekvationer:

${\begin{aligned}&\pi (\mathbf {x} )\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_ {i})(1-p_{ii})]\\={}&\sum _{i=1}^{J}[\pi (\mathbf {x} -\mathbf {e} _{i} )\alpha p_{0i}+\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)p_{i0}]+\summa _ {i=1}^{J}\sum _{j\neq i}\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _ {i}(x_{i}+1)p_{ij}.\qquad (2)\end{aligned}}$

där $\mathbf {e} _{i}$ betecknar den $i^{\text{th}}$ enhetsvektorn .

Sats

Antag en vektor med oberoende slumpvariabler $(Y_{1},\ldots ,Y_{J})$ där varje $Y_{i}$ har en sannolikhetsmassa fungera som

$P(Y_{i}=n)=p(Y_{i}=0)\ cdot {\frac {\lambda _{i}^{n}}{M_{i}(n)}},\quad (3)$

där $M_{i}(n)=\prod _{j=1}^{n}\mu _{i}(j)$ . Om $\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{ i}(n)}}<\infty$ dvs $P(Y_{i}=0) =\left(1+\summa _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\höger)^{- 1}$ är väldefinierad, så har jämviktsfördelningen för det öppna Jackson-nätverket följande produktform:

$\pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i}).$

för alla $\mathbf {x} \in {\mathcal {Z}}_{+}^{J}$ .⟩

Bevis

Det räcker för att verifiera att ekvation $(2)$ är uppfylld. Genom produktformen och formeln (3) har vi:

$\pi (\mathbf {x} )=\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1 )/\lambda _{i}=\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+ 1)\lambda _{j}/[\lambda _{i}\mu _{j}(x_{j})]$

Genom att ersätta dessa i höger sida av $(2)$ får vi:

$\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]=\summa _{i=1}^{J}[{\frac {\alpha p_{0i}}{\lambda _{i}}}\mu _{i}(x_{i})+\lambda _{i} p_{i0}]+\summa _{i=1}^{J}\summa _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij }\mu _{j}(x_{j}).\qquad (4)$

Använd sedan $(1)$ , vi har:

$\sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij}\mu _{j}(x_{j})=\summa _{j=1}^{J}[\summa _{i\neq j}{\frac {\lambda _{i}}{\lambda _{j }}}p_{ij}]\mu _{j}(x_{j})=\summa _{j=1}^{J}[1-p_{jj}-{\frac {\alpha p_{0j }}{\lambda _{j}}}]\mu _{j}(x_{j}).$

Genom att ersätta ovanstående med $(4)$ har vi:

$\sum _{i=1}^{J}\alpha p_{0i}=\summa _{i=1}^{ J}\lambda _{i}p_{i0}$

Detta kan verifieras med $\sum _{i=1}^{J}\alpha p_{0i}=\summa _{i=1}^ {J}\lambda _{i}-\summa _{i=1}^{J}\summa _{j=1}^{J}\lambda _{j}p_{ji}=\summa _{i =1}^{J}\lambda _{i}-\summa _{j=1}^{J}\lambda _{j}(1-p_{j0})=\summa _{i=1}^ {J}\lambda _{i}p_{i0}$ . Därför är båda sidor av $(2)$ lika.⟨

Detta teorem utökar den som visas ovan genom att tillåta tillståndsberoende tjänstehastighet för varje nod. Den relaterar fördelningen av $\mathbf {X}$ med en vektor av oberoende variabel $\mathbf {Y}$ .

Exempel

Ett öppet Jackson-nätverk med tre noder

Antag att vi har ett Jackson-nätverk med tre noder som visas i grafen, koefficienterna är:

$\alpha =5,\quad p_{01}=p_{02}=0,5,\quad p_{03}=0,\quad$

$P={\begin{bmatrix }0&0.5&0.5\\0&0&0\\0&0&0\end{bmatrix}},\quad \mu ={\begin{bmatrix}\mu _{1}(x_{1})\\\mu _{2} (x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin{bmatrix}15\\12\\10\end{bmatrix}}{\text{ för alla }}x_{i}>0$

Sedan kan vi med satsen beräkna:

$_ \displaystyle \lambda =(IP^{T})^{-1}a={\begin{bmatrix}1&0&0\\-0.5&1&0\\-0.5&0&1\end{bmatrix}}^{-1}{\begin {bmatrix}0.5\times 5\\0.5\times 5\\0\end{bmatrix}}={\begin{bmatrix}1&0&0\\0.5&1&0\\0.5&0&1\end{bmatrix}}{\begin{bmatrix} 2.5\\2.5\\0\end{bmatrix}}={\begin{bmatrix}2.5\\3.75\\1.25\end{bmatrix}}}$

Enligt definitionen av $\mathbf {Y}$ , har vi:

$P(Y_{1}=0)=\left(\summa _{n=0}^{\ infty }\left({\frac {2.5}{15}}\right)^{n}\right)^{-1}={\frac {5}{6}}$

$P(Y_{2}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {3.75}{12}}\right)^{n}\right)^{-1}={\frac {11}{16}}$

$P(Y_{3}=0)=\left(\summa _{n=0}^{\infty }\left({\frac {1.25}{10}}\ höger)^{n}\right)^{-1}={\frac {7}{8}}$

Därför är sannolikheten att det finns ett jobb vid varje nod:

$\pi (1,1,1,c) }\cdot {\frac {2.5}{15}}\cdot {\frac {11}{16}}\cdot {\frac {3.75}{12}}\cdot {\frac {7}{8}}\ cdot {\frac {1.25}{10}}\approx 0.00326$

Eftersom servicehastigheten här inte beror på tillstånd, följer ${\displaystyle Y_{i}} helt enkelt en$ geometrisk fördelning .

Generaliserat Jackson-nätverk

Ett generaliserat Jackson-nätverk tillåter ankomstprocesser för förnyelse som inte behöver vara Poisson-processer, och oberoende, identiskt fördelade icke-exponentiella servicetider. I allmänhet har detta nätverk inte en stationär distribution i produktform , så approximationer eftersträvas.

Brownsk uppskattning

Under vissa milda förhållanden kan kölängdsprocessen $Q(t)$ för ett öppet generaliserat Jackson-nätverk approximeras av en reflekterad Brownsk rörelse definierad som ${\displaystyle \operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).} ,$ där $\theta$ är processens drift, $\Gamma$ är kovariansmatrisen, och $R$ är reflektionsmatrisen. Detta är en tvåordningsapproximation erhållen genom förhållandet mellan det allmänna Jackson-nätverket med homogent vätskenätverk och reflekterad Brownsk rörelse.

Parametrarna för den reflekterade Brownska processen specificeras enligt följande:

$\theta =\alpha -(IP^{T})\mu$

$\Gamma =(\Gamma _{k\ell}){\text{ med }}\Gamma _{k\ell }=\summa _{j=1}^{J}(\lambda _{j }\wedge \mu _{j})[p_{jk}(\delta _{k\ell }-p_{j\ell })+c_{j}^{2}(p_{jk}-\delta _ {jk})(p_{j\ell }-\delta _{j\ell })]+\alpha _{k}c_{0,k}^{2}\delta _{k\ell }$

$R=IP^{T}$

där symbolerna definieras som:

Definitioner av symboler i approximationsformeln

symbol	Menande
$\alpha =(\alpha _{j})_{j=1}^{J}$	en J -vektor som specificerar ankomsthastigheterna till varje nod.
$\mu =(\mu )_{j=1}^{J}$	en J -vektor som specificerar servicehastigheterna för varje nod.
$P$	routingmatris.
$\lambda _{j}$	effektiv ankomst av ${\displaystyle j^{\text{th}}}-$ noden.
$c_{j}$	variation av servicetid vid ${\displaystyle j^{\text{th}}}-$ noden.
$c_{0,j}$	variation av inter-ankomsttid vid ${\displaystyle j^{\text{th}}}-$ noden.
$\delta _{ij}$	koefficienter för att specificera korrelation mellan noder. De definieras på detta sätt: Låt $A(t)$ vara ankomstprocessen för systemet, sedan $A(t)- \alpha t{}\approx {\hat {A}}(t)$ i distribution, där ${\hat {A}}(t)$ är en driftlös Brownsk process med kovariatmatris $\Gamma ^{0}=(\Gamma _{ij}^{0})$ , med ${\displaystyle \Gamma _ {ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}} , för alla i ,$ j $i, j\in \{1,\dots ,J\}}$

Se även

• Gordon–Newell nätverk
• BCMP-nätverk
• G-nätverk
• Littles lag