UOW ADMINISTRATION
Student to complete:
Copyright By PowCoder代写 加微信 powcoder
Family name
Other names
Student number
Table number
Telecommunication System Modeling
CCNU Wollongong Joint Institute
Examination Paper
Summer Session 2020
Exam duration 3 hours.
Items permitted by examiner UOW approved calculators. Open book.
Aids supplied Nil.
Directions to students Attempt all questions. Marks are indicated accordignly.
Make sure your answers are CLEAR and READABLE.
The examination paper is printed on BOTH SIDES.
Candidates should note that questions are to be answered as written –
no consultation (individual or group) on questions will be given.
Any assumptions made should be recorded with your answer.
Examination papers must be written in ink.
Papers written in pencil will NOT be marked.
This exam paper and answer booklet(s) must not be removed from the exam venue
2020 ECTE962 Summer Session 2020 Page 1 of 14
QUESTION 1 (18 marks)
In this exercise, we consider a M/M/2/3 queue with servers having identical service rates.
a) Draw the Markov chain associated to this M/M/2/3 queue. Label all the states and transitions clearly. (4
b) Let Xt be the random variable describing the state of the queue at time t, and assume the queue is in a
state i at time t. Let us consider a small time step Δt, such that Δt is very small in comparison to the
average time between arrivals and Δt is very small in comparison to the mean service times of the queue.
Give the transition probability matrix P(Δt) associated to this M/M/2/3 queue. We recall that we can define
the transition probability matrix P(Δt) such that its coefficients corresponds to Pij(Δt) = Pr(Xt+Δt=i| Xt=j). (4
2020 ECTE962 Summer Session 2020 Page 2 of 14
The transition rate matrix Q associated to a continuous time Markov chain can be defined as
p’t = pt·Q
where p’t is the time derivative of pt and pt corresponds to a row vector containing the state probabilities
at time t. If the chain contains n states then pt = ( Pr(Xt=0), Pr(Xt=1), … ,Pr(Xt=n) ) and Q is an nxn matrix.
Using the transition probability matrix computed in the previous question, we can also define Q as Q =
limΔt 0→0 (P-I)/Δt where I is the identity matrix.
c) Give the transition probability matrix Q associated to the M/M/2/3 queue. (4 marks)
d) Use p’t = pt·Q to find a system of linear equations involving the state probabilities in the steady-state for
the M/M/2/3 queue. (4 marks)
e) Can you solve this system of linear equations without any additional condition? If no, specify which
additional condition(s) is needed. (2 marks)
2020 ECTE962 Summer Session 2020 Page 3 of 14
QUESTION 2 (8 marks)
ATM switches have a fixed service time duration. A queue in an ATM switch is found to have a Poisson
arrival process. Over a long period of time, the average length of the queue is found to be 2.5 packets.
Find the fraction of time the queue is empty.
2020 ECTE962 Summer Session 2020 Page 4 of 14
QUESTION 3 (14 marks)
Consider the Jackson network shown below where all nodes are M/M/1. The arrival rate of external traffic
to nodes 1, 2, 3 and 4 are shown on the diagram. Also routing information is shown on each link. Assume
that the service rates are as follows: μ1 = 16, μ2 = 32, μ3 = 40, μ4 = 20, μ5 = 28.
(a) Give the routing matrix associated to this newtork. (3 marks)
(b) Compute the arrival rates at each node. (4 marks)
2020 ECTE962 Summer Session 2020 Page 5 of 14
(c) Are the conditions of stability satisfied for each node? Justify your answer. (4 marks)
(d) Find the probability that there are 5 customers in the network and all of them are in node 4. (3 marks)
2020 ECTE962 Summer Session 2020 Page 6 of 14
QUESTION 4 (8 marks)
Consider a general birth and death queuing system in which,
for k ≥ 0, 0 ≤ α < 1 (a) Find the steady-state probability p(k) of having k customers in the system. Express p(k) as a function of ρ, a and k. (4 marks) b) Show that this system is always stable (i.e. stable for any values of λ and μ) if 0 ≤ α < 1. (4 marks) 2020 ECTE962 Summer Session 2020 Page 7 of 14 QUESTION 5 (16 marks) Consider the following function: f(x) = x2 − 2 x3 + 2 exp( x ) − 4 + y2 with x = (x, y) R∈ R 2 . (a) Specify the gradient and the Hessian of the function. (2 marks) (b) The function x →0 x2 − 2 x3 + 2 exp( x ) admits three critical points at x≈-0.35, x≈1.27 and x≈3.51. Deduce how many critical points the function f admits. For each critical point, specificy if it is a minimum, a maximum or a saddle point. (4 marks) b) Show that the Hessian at x=(1,0.5) is not a positive semi-definite matrix and is not a negative semi- definite matrix. (4 marks) 2020 ECTE962 Summer Session 2020 Page 8 of 14 c) Since at x=(1,0.5) the Hessian is indefinite, it cannot be used as a local metric. To circumvent this issue, we propose to use the steepest descent method with the matrix 2I (i.e. twice the identity matrix) as the local metric. Apply the first minimization step using x0 = (1, 0.5 ) and μ0 =1. (3 marks) d) In view of the point x1 found in the previous question, do you think additional steps using the steepest descent method will allow to converge towards the global minimum? If no, towards which critical point do you think it will converge? Justify your answers. (3 marks) 2020 ECTE962 Summer Session 2020 Page 9 of 14 QUESTION 6 (18 marks) Consider the following system of equations were x, y, z and a are all positive integers (i.e. natural x = 2y, y = z – 1, a = 2x + 1 (a) Draw the graph associated to this constraint satisfaction problem with variables x, y, z and a as vertices. Give the degree of each vertex. (4 marks) (b) List the variables in the graph which are associated to cut-vertices. (3 marks) (d) We provide the following unary constraints : 0 < x < 10, 0 < y < 10, 0 < z < 10 and 0 < a < 10. Apply node consistency and arc consistency in order to find the resulting domains for each variable. Write down the domains for each variables in the first row of the table in question (e). (5 marks) 2020 ECTE962 Summer Session 2020 Page 10 of 14 (e) Find a solution of the problem using Forward Checking. Assign variables using the following order a, x, y, z and assign values for each variable in increasing order. Detail the steps in the following table. (4 marks) domains found in question (d) 2020 ECTE962 Summer Session 2020 Page 11 of 14 QUESTION 7 (10 marks) (a) Is the heuristic in this network admissible? Is the heuristic consistent? (4 marks) (b) Apply the A tree search algorithm∗ tree search algorithm to find the shortest path(s) from a to g. In the table below, make the following entry for each step of the algorithm (6 marks): • When node N is expanded, write expand N • When the value of node N is (re)-calculated, write N: g ( N ) + h ( N ) = f ( N ) 2020 ECTE962 Summer Session 2020 Page 12 of 14 QUESTION 8 (8 marks) (a) Give the order in which the nodes are visited depending on the search algorithm. The bold node is the goal node, the search should stop once the goal node is reached. Use the following conventions: when a direction of exploration is needed, navigate from left to right in the tree (i.e. always start from the left at a given depth). (4 marks) Depth-first search Breadth-first search Iterative deepening depth-first search (b) Is it possible to draw a tree where iterative deepening depth-first search reaches the goal node faster than breadth-first search? Justify your answer. (2 marks) (c) Is it possible to draw a tree where iterative deepening depth-first search reaches the goal node faster than depth-first search? Justify your answer. (2 marks) 2020 ECTE962 Summer Session 2020 Page 13 of 14 2020 ECTE962 Summer Session 2020 Page 14 of 14 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com