Question

Slotted non-persistent CSMA: Use the TWO-state Markov chain we discussed in class

to derive the throughput of non-persistent CSMA when nodes are required to transmit at the beginning of

a time slot, the length of a time slot is one propagation delay, and ideal acknowledgments are sent in 0

seconds over a secondary channel.

Answer 1

Semi-Markovian process We consider here a semi-Markovian system. In other words, we have a state-space I that is a subset of IN. When the process enters the state i, i ≥ 0, (i) it enters the state j, j ≥ 0, with the probability Pi,j , (ii) given that the following state is j, the time spent in the process i follows a distribution law Fi,j .

e Hi the time distribution of the semiMarkov process in the state i, in other words, Hi = X j Pi,jFi,j , and µi the average time spent in the i state, given by µi = Z ∞ 0 xH0 (x)dx.

Definition 1 A semi-Markov process is irreducible if for all pair (i, j), there exists a path a0 = i, . . . , ap = j, p ∈ IN, where ∀k ∈ {1, . . . , p} Pak−1,ak > 0. We also will note τi the time between two transitions to the state i. We also consider Yn as a discrete Markov chain and νi the number of transitions to come from state i to state i. Proposition 1 If Yn, n ∈ IN is irreducible and νi < ∞, we note d(i) = max [d |P{Yn = i|Y0 = i} > 0 ⇒ n ∈ dIN] , then the quantity πi = limn→∞P{Ynd(i) = i|Y0 = i} is strictly positive.

Theorem 1 Suppose that • the semi-Markovian process is irreducible, • τi > 0 and the distribution of τi is not a lattice, • νi < ∞. Then Pi := limt→∞ P{Z(t) = i|Z(0) = j} does not depend on j and is given by Pi = P πiµi j πjµj .

Result 1 A state e whose maximal duration is T and who can be interrupted by p poissonian processes of intensity λ1, . . . , λp, has, if it is interrupted, an average duration of E[We] = 1 µ − T e −µT 1 − e−µT , where µ = λ1 + · · ·+ λp. The interruption probability is 1 − e −µT , and the probability that the process exits by interruption i is (1 − e −µT )λi/µ. Proof. Let X1, . . . , Xp be p poissonian random variable of respective intensity λ1, . . . , λp. We know that Y = min(X1, . . . , Xp) follows a poissonian law of intensity µ, and therefore the process is interrupted if and only if Y ≤ T, which occurs with probability e −µT . On the other hand, the probability that the process exits by interruption i is given by the ratio λi/µ of intensity, which proves the second part of the proposition. The average waiting time in this process, if it is interrupted, is given by: E[We] = 1 P[Y < T] Z T 0 td[P[Y < t]] = 1 1 − e−µT Z T 0 µte−µtdt.