Tools for Computer Systems Analysis – Fall 2015

Technion - Israel Institute of Technology
Department of Electrical Engineering
Tools for Computer Systems Analysis – Fall 2015
Class Exercise 8
December 8, 2014
1
Renewal Theory - Part II
Example 1 (Nonpersistent Carrier Sense Multiple Access). In NPCSMA a user that generated a packet and found the channel to be busy refrains from transmitting the packet and
behaves exactly as if its packet collided, i.e., schedules (randomly) the retransmission of the
packet to some time in the future. We assume the following:
1. Infinite population of users aggregately generating new packets according to a Poisson
process with parameter λ.
2. All packets are of the same length and require T seconds of transmission.
3. When observing the channel, packets (new and retransmitted) arrive according to a
Poisson process with parameter g > λ (packets/sec).
4. Maximum propagation delay between the users is τ seconds.
Consider an idle channel and a user scheduling a transmission at some time t. This user
senses the channel, starts trasmitting at time t and does so for T seconds.
1. This transmission causes the channel to be busy for a period of T + τ seconds.
2. If at time t0 > t + τ another user schedules a packet for transmission, that user would
sense the channel busy and refrain from transmission.
3. If some other user schedules a packet for transmission during the period [t, t + τ ], that
user would sense the channel idle, transmit its packet, and cause a collision.
The initial period of the first τ seconds of transmission is called the vulnerable period since
only within this period is a packet vulnerable to interference. In the case of a collision the
channel will be busy for some random duration between T + τ and T + 2τ . This period
1
Tools for Computer Systems Analysis (EE925) - Class Exercise #8
2
Figure 1: Nonpersistent CSMA Timing
in which a transmission takes place is referred to as the transmission period (TP). Having
completed a TP the channel will be idle for some time until the next packet transmission
is scheduled. Since packet scheduling is memoryless, one observes a renewal process, with
renewal point at the start times of the cycles of TP and idle periods. Let:
˜ be the duration of the busy period having average B.
• B
˜ be the fraction of a cycle dedicated to successful transmissions having average U .
• U
• I˜ be the duration of an idle period having average I.
We are interested in the throughput of the protocol, which may be calculated, due to the
renewal theorems, as
U
S=
B+I
The idle period I: Its duration is the same as the duration between the end of packet transmission and the arrival of the next packet. Because packet scheduling is memoryless we
obtain:
n
o
n
o
FI (x) = P I˜ ≤ x = 1 − P I˜ > x = 1 − P {no packet scheduled during x} = 1 − e−gx
That is, I˜ is exponentially distributed with mean I = g1 .
The useful time U : When a packet is successful, the channel carries useful information for a
duration of T seconds - the time it takes to transmit the packet; in the unsuccessful case no
useful information is carried at all:
(
T
successful period
˜=
U
0 unsuccessful period
Tools for Computer Systems Analysis (EE925) - Class Exercise #8
3
Denote by Psuc the probability that a transmitted packed is successful and obtain:
˜ = T · Psuc + 0 · (1 − Psuc ) = T · Psuc
U = EU
Bearing in mind that a successful period means no packet scheduling during the vulnerable
period:
Psuc = P {no arrival in the period [t, t + τ ]} = e−gτ
and thus,
U = T e−gT
The busy period B: Let Y˜ be a random period between the beginning of the busy period
and the arrival of the last interfering packet for that BP. Clearly, Y˜ < τ and for a successful
transmission period Y˜ = 0. With this notation, the duration of the busy period:
˜ = T + τ + Y˜
B
The period Y˜ is characterized by the fact that no other packet is scheduled for transmission
during the period [t + Y˜ , t + τ ] for otherwise the packet that is transmitted at t + Y˜ would not
have been the last packet to be transmitted in [t + Y˜ , t + τ ]. Thus, the probability distribution
function of Y˜ is:
n
o
FY˜ (y) = P Y˜ ≤ y = P {no packet arrived during τ − y} = e−g(τ −y) , 0 ≤ y ≤ τ
Note the discontinuity of FY˜ (y) at y = 0, which causes a Dirac’s delta in the density:
fY˜ (y) = e−gτ δ(y) + ge−g(τ −y)
The mean of Y˜ is therefore EY˜ = τ −
1−e−gτ
g
and the average busy period is:
1 − e−gτ
B = E[T + τ + Y˜ ] = T + 2τ −
g
Combining all together we obtain the throughput expression for NPCSMA:
S=
U
gT e−gτ
=
B+I
g(T + 2τ ) + e−gτ
Example 2 (The Inspection Paradox). Assume Poisson arrivals with parameter λ. Clearly,
every interarrival time before the observation has average duration of 1/λ.
At the observation point, due to the memorylessness of the exponential distribution, the
average duration since the last arrival is 1/λ. The average duration until the next arrival is
also 1/λ. We obtain a paradox, whether this interval has an average duration of 2/λ or 1/λ
like every other interval. Denote:
• X - the length of the interval between two successive arrivals.
Tools for Computer Systems Analysis (EE925) - Class Exercise #8
4
Figure 2: The inspection paradox.
• A - age.
• Y - the excess time.
• L - the length of the interval that includes the observation point.
The sequence of the arrival times {tk } is a renewal process and we are interested in the
distribution of the interval that includes the observation point t.
Proposition 1.
fL (x) =
xfX (x)
EX
Proof: Define the indicator
(
In (x) =
0 Xn > x
1 Xn ≤ x
The fraction time of all intervals whose length is less or equal to x is:
Pk
Φk (x) =
n=1 In (x)Xn
Pk
n=1 Xn
=
1
k
Pk
n=1 In (x)Xn
1 Pk
n=1 Xn
k
Taking k to the limit:
E[In (x)Xn ]
lim Φk (x) =
=
k→∞
EX
Rx
0
αfX (α) dα
EX
On the other hand,
lim Φk (x) = P {L ≤ x} = FL (x)
k→∞
Taking the derivative of FL (x) completes the proof.
Consequently,
Z ∞
Z ∞ 2
α fX (α)
E[X 2 ]
EL =
αfL (α) dα =
dα =
EX
EX
0
0
and in particular, EL ≥ EX. To calculate the distribution of the excess time note:
Tools for Computer Systems Analysis (EE925) - Class Exercise #8
Proposition 2.
(
P {Y ≤ y | L = l} =
y/l 0 ≤ y ≤ l
0
otherwise
“Proof”: We consider an interval of a given length.
Finally,
1 xfX (x)
fX (x)
=
, 0≤y≤x
x EX
EX
Z ∞
Z ∞
1
1
fY,L (y, x) dx =
fX (x) dx =
fY (y) =
(1 − FX (y))
EX y
EX
y
fY,L (y, x) = fL (x)fY
| L (y
| x) =
5

Download Report