"Each packet’s service time at a switch is exponentially distributed
with mean 1/u, and packets must queue for service in a strict first
come, first served, order. The number of packets ahead of a newly
arriving packet has pdf p(n) = (1 – p)pn. What is the pdf of the
sojourn time of the packet? That is, what is the pdf of the total
time spent by a packet at the switch?"
Hi,Here is an answer to your first question.
I will assume that the number of packets ahead pdf is p[n]=(1-p)*p^n.
The statement "Each packet’s service time at a switch is exponentially
distributed with mean 1/u" implies that the pdf for the service time
is
tot[0,t] = ser[t]=u*Exp[-t*u].
We will use the notation
tot[n,t]
to denote the total time it take for a packet to be processed if there
are n packets ahead of it when it arrives at the que. So if the
packet arrives with no packets ahead of it,then the total time has the
distribution
tot[0,t] = ser[t].
If the packet arrives with 1 packet ahead of it,then the total time
has the distribution
tot[1,t] = Integral[ser[a]*ser[t-a],{a,0,t}]
where Integral[f[x],{x,c,d}] is the integral of f[x] from x=c to
x=d,ser[a] is the time to process the last packet,and ser[t-a] is the
time to process the first packet. If the packet arrives with 2
packets ahead of it,then the total time has the distribution
tot[2,t] = Integral[ser[a]*tot[1,t-a],{a,0,t}]
where ser[a] is the time to process the last packet, and tot[1,t-a] is
the time to process the first two packets. Continuing in this fashion
we see that
tot[n,t]=Integral[ser[a]*tot[n-1,t-a],{a,0,t}].
The mathematically sophisticated might recognize that as a convolution
of ser and tot[n-1]. We can apply Laplace Transforms to calculate
convolutions easily. Let's do the easy one first. Let TOT[n, s] be
the Laplace transform of tot[n,t]. Then
TOT[0, s] = LaplaceTransform[ ser[t], t, s]
= LaplaceTransform[ ser[t], t, s]
= LaplaceTransform[ u*Exp[-t*u], t, s]
= u / (s+u).
Now TOT[n, s] can be calculated from the rule that the laplace
transform of the convolution of two functions is merely the product of
the laplace transforms of the two functions. Thus
TOT[1,s] = LaplaceTransform[ Convolution[ ser[t], ser[t] ], t, s]
= LaplaceTransform[ ser[t], t, s] * LaplaceTransform[ ser[t], t,
s]
= u / (s+u) * u / (s+u).
Similarly, for TOT[n, s],
TOT[n,s] = LaplaceTransform[ Convolution[ tot[n-1, t], ser[t] ], t,
s]
= LaplaceTransform[ tot[n-1,t] , t, s] * LaplaceTransform[
ser[t], t, s]
= TOT[n-1, s]* u / (s+u).
We see that each time n increases, TOT[n, s] is multiplied by
u/(s+u). So in general,
TOT[n,s] = (u / (s+u))^n.
To get tot[n,t] we need to take the inverse laplace transform of
this expression. Looking up the laplace transforms of t^n Exp[-t u]
shows us that the inverse laplace transform of TOT[n, s] is
tot[n,t] = t^n u^(n+1) Exp[-t*u] / (n!).
Well that gives us the distribution function for the total service
time for our packet if we know that there are n packets ahead when our
packet arrives. Tot remove the dependence on n we simply add up the
probabilities for each n. Thus the distribution function for the
total service time is
tot[t] = Sum[ p[n] tot[n,t], {n, 0, Infinity}]
where Sum[ f[n], {n, 0, a}] is just f[0]+ f[1] + f[2] + ... + f[n].
We just need to do some algebra and recognize a Taylor Series to get
the final answer.
tot[t]
= Sum[ (1-p) p^n t^n u^(n+1) Exp[-t*u] / (n!) , {n, 0,
Infinity}]
= (1-p) u Exp[-t*u] Sum[ p^n t^n u^n / (n!) , {n, 0,
Infinity}]
= (1-p) u Exp[-t*u] Sum[ (p*t*u)^n / (n!) , {n, 0,
Infinity}]
= (1-p) u Exp[-t*u] Exp[ p t u]
= (1-p) u Exp[-t*u + p t u]
= (1-p) u Exp[-(1-p)*t*u ].
Great! The tot[t] function is just a simple Exponential decay with a
larger time constant! Very nice problem. |
