Département : Génie Electronique
UNIVERSITE LIBANAISE Semestre : 8ème
FACULTE DE GENIE Date : 06 Avril 2017
BRANCHE I Professeur : Dr. Nada Chendeb
Documents interdits Durée : Deux heures
Midterm Exam
Operational Research (2.8.5.T - 2.8.5.C)
Exercise 1:
Step through Dijkstra's algorithm to calculate the single-source shortest paths from A
to every other vertex. Show all your steps in a table, list the vertices in the order
which you marked them known. Finally, indicate the lowest-cost path from node A to
node F and draw the tree of paths from A to all other nodes.
Exercise 2:
Using the Hungarian algorithm, find the least cost assignment associated to the
following table, list alternative solutions if any.
P1 P2 P3 P4 P5
S1 2 2 11 9 9
S2 2 3 9 10 3
S3 4 10 5 3 6
S4 2 7 5 3 5
S5 5 1 9 2 10
Exercice 3 :
A tower of 6 floors (a ground floor and 5 other floors) is equipped by a lift having a
strange functioning: It cannot be called to go from a floor to the other but only from
the ground floor to other floors and reciprocate. The statistics of the usage of the lift
show that, at each time step:
– if the lift is on the ground floor, it stays there with a probability 1/6 and it is called
to any other floor with probability 1/6.
– if the lift is on floor i, it stays there with a probability 1/3 and goes to ground floor
with probability 2/3.
a. Show that the set (Xn) that gives the floor on which the lift resides is a
Markov chain with state space {0, 1, 2, 3, 4, 5}. Draw the transition matrix of
(Xn).
b. Is the chain irreducible? Calculate the stationary distribution.
Exercise 4 :
The network of Figure 1 is constituted of links having the rates presented in Table 1.
The traffic entering node E is a poissonian with an average 40 packets/s. These
packets have an exponential length of average 128 bytes. All traffic entering E goes to
S. The router N1 routes 60% of input traffic to router N2.
The links N1-N2, N2-N4, N4-N6 have a length of 1 Km each; links N1-N3, N3-N5,
N5-N6 have 0.5 Km of length. Finally, the propagation speed is 3.104 m/s.
Figure 1: Physical Network Table 1: Link data rates
a- We model the hops in this network by queue systems according to Figure 2.
What is the type of each queue in this model? Justify your answer.
Figure 2: Modeled Network
b- Fill in the following table. Conclude about the network stability
Link Rate (Kb/s) Departure rate (µ) Arrival rate (λ) Load (ρ)
(packet/s) (packet/s)
N1-N2 64
N2-N4 40
N4-N6 64
N6-S 64
N1-N3 32
N3-N5 50
N5-N6 32
c- Calculate the average sojourn time in each queue for a packet traveling
through the path N1-N2-N4-N6-S
d- What will be the average total transit time on the path N1-N2-N4-N6-S if we
neglect the propagation time on the link N6-S. Recall that the transit time on a
hop is equal to the sum of the sojourn time in the node and the propagation
time on the link (= link length/propagation speed).
e- Calculate the average sojourn time in each queue for a packet traveling
through the path N1-N3-N5-N6-S
f- What will be the average total transit time on the path N1-N3-N5-N6-S?
g- What is the conclusion that you can draw on the routing protocol at node N1.
Exercise 5 :
The requests to a database server can be modeled by a Poisson process. The average
time needed to process a request is S = 0.1s, with a standard deviation σS = 0.03s. We
suppose that the queue system is of type M/GI/1.
a. Give the average response time R as function of the number of requests per
second, λ.
b. We can accept an average response time R= 0.2s, what is the maximum
tolerated value of λ? What is the value of W (waiting time) in this case? N
(mean number of requests in the system)? and Nw (in the queue)?
c. Same questions for R = 0.5s.
d. Now, from the last value found for λ, what happens if we increase it again by
10%? by 20%?
E[ X 2 ]
Recall that for an M/GI/1 queue, the average waiting time is: E[W ]
2(1 )
Good luck
