CSC 598.67: Senior Design II
Mid-term exam (take-home), 12th-17th, April 2024
(Answer all questions. The points for each question is indicated. Total = 65 points)
[Be brief in your answers (say, no more than 5 pages of answer-sheets)]
Email your answer scripts (as PDF) to: [email protected]
1. (10 pts) Consider two customers A and B walking to a bank that has two tellers x and y, for service. Each customer requires 8 minutes of service time from the teller x before going to the teller y to get a service which lasts for 10 minutes. Assuming that A and B arrive in the bank at the same time, what is the the minimum total time needed for both A and B to complete their work in the bank ??
2. (15 pts) An AIMD-based video rate adaptation system (say, during YouTube downloads) can be represented as a computational function of the form. L = net(λ, Bav ), where λ > 0 and L > 0, where λ is the video send rate over network path and L is the observed loss ratio arising due to congestion. Here, a fraction of the video data is lost or gets excessively delayed in the network when the bandwidth demand of video source: denoted as Bdem = F(λ), exceeds the available bandwidth Bav , i.e., the scenario Bdem > Bav depicts the likelihood of a congestion. The internal details of net( ···) to determine L for an input λ are not known to the network system programmer, i.e., net(λ) appears as a black-box taking λ as input and returning L as output. But the programmer knows how the net( ···) behaves when λ changes, as given by the relationship:
net(λ +∆, Bav ) > net(λ, Bav ) > net(λ — ∆, Bav )
for ∆ > 0. The main control program employs an AIMD (additive increase multiplicative decrease) algorithm. It invokes the net(λ, Bav ) function in the following way:
Suppose an initial value of λ causes the net(λ, Bav ) return a value L > δh , where δh > 0. In that case, the program reduces λ in multiple steps of β X L. In each step, the system nudges progressively towards a lower value for L such that net(λ, Bav ) < δl , where β > 0 and 0 < δl < δh. Thereupon, the program increases λ in multiple steps of α: namely, λ = λ + α such that net(λ, Bav ) > δh , where α > 0. Thereafter, the decrease procedure kicks in again.
The computation steps in the program interacting with net( ···) are shown in Figure 1-(a) in a C-like language. Figure 1-(b) shows the empirical behavior of AIMD, i.e., how λ changes over time when a reduction in Bav occurs (the passage of time is shown as computational iterations i). For this AIMD- based video rate control, explain the role of algorithm parameters δh and δl.
3. (20 pts) Consider two roads that merge into a single road along the way. See Figure 2. The car traffic in each of the roads is independently modeled as a Poisson process, with the arrival rates being λ 1 cars/minute and λ2 cars/minute respectively. Here, an inter-arrival time t1 for the cars on road1 as given by the exponential distribution:
prob(tmin < t1 ≤ x) = [1 — e −λ1 (x −tmin )];
prob(t1 ≤ tmin ) = 0;
where tmin specifies the granularity of time-points over which individual cars can be observed on the road. Likewise is the modeling of inter-arrival time t2 for the cars on road2 . Given this problem description, answer the following questions (refer to Figure 2):
Figure 1: Behavior of program that embodies L = net(λ) function as black-box
A: What is the value of tmin ? Assume that L ft separation needs to be maintained between cars, for safety reasons (at a vehicle speed of V ft/minute). Also, assume that all the cars on a road travel at the same speed of V ft/minute (≤ Vm ), where Vm is the posted speed-limit on the roads.
B: What is the probability that a car Z arriving on a road does not cause a slow down of the traffic (i.e., Z does not find another car within an unsafe distance when trying to merge) ??
C: Given that the traffic flow on road1 , road2 is a Poisson process each (when separately considered), can the combined traffic after the merge be modeled as a Poisson process too ?? Give reasons.
[Hint: When two Poissonian flows of events are merged (as a single event flow), their superposition should preserve the point-process property of event occurrences (i.e., should not disturb the time- points of individual event occurrences in the merged flow from that in the component flows).]
4. (20 pts) A cyber-physical system S is composed of two functional elements: i) a software module
CS that runs on digital computers, and mechanical and electrical components. ii) a physical sub-system PS that is often made up of, say, These functional elements CS and PS inter-work together continuously over time to generate useful behaviors for an application that makes use of the system S.
Figure 2: Modeling of car traffic-flows on merging roads
This functional composition, denoted as:
S = CS ⊕ PS ,
is realized having CS maintaining a discrete-event model of PS , denoted as Φ(S), that simulates the various events and actions incident on PS , and computes their expected effects on the visible outputs of PS . A realization of the discrete-event model Φ(S) involves codifying the interactions between CS and PS over multiple levels of time-granularity, as follows:
Simulation interval t1 : This depicts the time-duration programmed in CS over which the inputs to PS and/or the changes in visible outputs of PS are computationally represented.
Rendering interval t2 : This depicts the time-duration over which the model-computed events by CS are programmed to take effect on PS ;
Response interval t3 : This depicts the time-duration over which a response of PS to an input action triggered by CS becomes visible;
Action interval t4 : This depicts the minimum time-duration between two successive model-computed actions exercisable on PS that ought to elapse.
Persistence interval τ: This depicts the time-duration over which the effects of an input action exercised on PS linger on;
Explain these time intervals t1-t4 and τ for the cases of two different applications: i) cruise-control system in a car; and ii) soccer-game played by robots. Be sure to state reasonable numerical values for these time-intervals in the cases (i) and (ii).