Performance evaluation of networks: class #3

Lots of math stuff on Markov processes, please someone put notes as I was late!

Some notes of the second part:

(1)
\begin{align} q(i, j) = \textrm{transition rate} \ i \rightarrow j \end{align}
(2)
\begin{align} \frac 1 {-q(i, i) } = \textrm{average sojourn time in state}\ i \end{align}
(3)
\begin{align} \Rightarrow -q(i, i) = \textrm{transition rate out of state}\ i \end{align}

Interpretation of $pQ = 0$

Birth and death process

Packets arrive at something?

(4)
\begin{align} X(T) = #\textrm{packets at time}\ t \end{align}
(5)
\begin{align} {X(t), t \geq 0} \textrm{C-MC} \end{align}
(6)
\begin{align} X(t) \in { 0, 1, 2 \dots} = E \end{align}

Birth rate: $q(i, i + 1) = \lambda_i$
Death rate: $q(i, i - 1) = \mu_i, i > 0$

(7)
\begin{align} Q = \left[ \begin{array}{ccccc} -q(0,0) & q(0, 1) \\ q(1,0) & -q(1,1) & q(1,2) \\ & & & \ddots \\ & q(i-1, i) & -q(i, i) & q(i, i + 1) \\ & & & & \ddots \\ \end{array} \right] = \left[ \begin{array}{ccccc} -\lambda_0 & \lambda_0 \\ \mu_1 & -(\lambda_1 + \mu_1) & \lambda_1 \\ & & \ddots \\ & \mu_i & -(\lambda_i + \mu_i) & \lambda_i \\ & & & \ddots \\ \end{array} \right] \end{align}
(8)
\begin{align} \left\{ \begin{array}{l} -\lambda_0 p_0 + \mu_1 p_1 = 0 \\ \lambda_0 p_0 - (\lambda_1 + \mu_1) p_1 + \mu_2 p_2 = 0 \\ \vdots \\ \lambda_{i-1} p_{i-1} - (\lambda_i + \mu_i) p_i + \mu_{i+1} p_{i+1} = 0 \\ \end{array} \right. \end{align}
(9)
\begin{align} p_i = \frac { \lambda_0 \lambda_1 \dots \lambda_{i-1} } { \mu_0 \mu_1 \dots \mu_{i-1} } p_0, \forall i \geq 1 \end{align}
(10)
\begin{align} p_0 \left( \sum_{i\in E} \frac {\lambda_0 \lambda_1 \dots \lambda_{i-1} } { \mu_0 \mu_1 \dots \mu_{i-1} } \right) = 1 \end{align}
(11)
\begin{align} \textrm{case 1:}\ \ S < \inf \Rightarrow \left\{ \begin{array}{rcl} p_0 & = & \frac 1 S \\ p_i & = & \frac {\lambda_0 \lambda_1 \dots \lambda_{i-1} } { \mu_0 \mu_1 \dots \mu_{i-1} } \frac 1 S, \forall i \in E \\ \end{array} \right. \end{align}
(12)
\begin{align} \textrm{case 2:}\ \ S = \inf \Rightarrow \textrm{I don't know (with the course material)} \end{align}

Rules to check if a stochastic process is a C-MC

Rule #1

  • Stays in state i an exponential duration with parameter $\tau_i$
  • Jumps instantaneously in state j with probability $m_ij$.
(13)
\begin{align} \sum_{j\in E, j \neq i} M_{ij} = 1 \end{align}

Then, it is a C-MC with generator defined as:

(14)
\begin{align} q(i, j) = \left\{ \begin{array}{ll} \tau_iM_{ij} & i \neq j \\ -\tau_i & i = j \end{array} \right. \end{align}

Rule #2

GAH, got lost while copying

Queues

I have a server with an infinite queue.

  • Poisson process with parameter $\lambda$.
  • $P[ \textrm{service of a packet} \leq x] = 1 - e^{-\mu x}$ (simple assumption, not usually true)

With this system we can get some answers to these questions:

  • stability?
  • throughput?
  • waiting time?
  • sojourn time?

Let's define $X(t) = #\textrm{customers at time} t, t \geq 0$
…..

Unclear, need to ask the teachers, since most is obviously derived works.