Homework 2 CS 414, Spring 2011 Instructor: Klara Nahrstedt Note: Homework is an individual effort, i.e., no working in groups. Consider the homework as a preparation for your final exam. The deadline for HW1 is Monday, May 9, midnight. You can submit your solutions through Compass in pdf format or you can slide the homework solutions in paper form under the door of the office 3104 Siebel Center. The homework has 100 points together. Problem 1: Multimedia CPU Scheduling (25 Points) 1.1 Let T = (a,b,c) be the set of threads processing continuous media streams. Assume that the media threads are independent of each other. Let the average processing times e of the threads per medium data units be e(a) = 2 ms, e(b) = 18 ms, e(c) = 80 ms. Let the periods p of the media threads be p(a) = 50 ms, p(b) = 200 ms, p(c) = 250 ms. (1) (3 Points) Are the threads in the set T schedulable using preemptive Rate-Monotonic Scheduling (RMS) algorithm? Show the schedulability condition and calculation. (2) ( 5 Points) If schedule exists from threads in T, using preemptive RMS algorithm, provide the schedule ordering. If there does not exist schedule, explain why not. Draw the schedule (in case of yes) or show the deadline violation (in case of no).(3) (2 Points) Provide the schedulability test for preemptive EDF (Earliest Deadline First) scheduling algorithm. Show the work and calculation. (4) (5 Points) If the threads in T are schedulable using preemptive EDF, draw a schedule. If the threads in T are not schedulable via preemptive EDF, explain why not. 1.2. (10 Points) Assume that message size M of the media data unit (frame size of an uncompressed video) of each thread in set T is as follows: M(a) = 100 bytes, M(b) = 400 bytes, M(c) = 1024 bytes. Assume the messages arrive for processing to the corresponding buffers (i.e., thread a serves stream a and buffers data into buffer Bufa, thread b serves stream b and buffers data into buffer Bufb, and thread c serves stream c and buffers data into buffer Bufc) in a streaming fashion. How many bytes do you need to receive in order to avoid starvation and overflow buffer states (specify the number of bytes for each stream a, b, c)?Problem 2: Disk Scheduling (20 Points) Let us consider a single multimedia disk with a number of tracks from 1 to 100. Let us consider the following set of requests in a request queue for a multimedia disk. Note that each request is represented at the disk management level as a pair of values (deadline, track number). Let us assume that request queue is separate from the scheduling queue where the disk scheduling policy operates (makes a decision). Let us assume that the scheduling queue can store 5 items. The Request Queue and its Order of Requests (1, 20), (1, 1), (2, 89), (3, 13), (2, 70), (1, 10), (2, 60), (3, 40), (3, 20), (2, 85), (3, 35), (2, 76), (3, 96), (3, 36), (3, 95), (4, 48), (4, 1), (4, 50), (3, 5), (3, 45), (4,20). (1) (10 Points) Specify the scheduling order of these requests when using the enhanced Scan-EDF, using differentiating functions f(Ni) when head moves upwards and when head moves down-wards. Assume that the disk head starts at the track 20 and starts to move downwards when you start considering the request queue. (2) (10 Points) Specify the scheduling order of the requests above when using the EDF disk scheduling policy and compare which disk scheduling policy yields more efficient order of requests in terms of the number of tracks that the disk head needs to pass when requests are scheduled with EDF or enhanced SCA-EDF. Assume that the disk head starts at the track 20 and starts to move downwards when you start considering the order of requests in the above queue.Problem 3: Multimedia Networking (25 Points) Design a transmission system between two desktop clients being located at different coasts of USA, executing multimedia (audio/video) chat service. Assume that you have available all the standard protocols such as RSVP, RTP, RTCP, RTSP, SIP, SDP, UDP, TCP, IP. (1) (10 Points) Propose algorithms, protocols and architectural constructs for the control plane for your chat system, i.e., explain how you will setup audio/video connections (what functions, protocols, capabilities must be in place to allow for your chat service, in what order the function(s)/protocol(s) need to be used, and why did you decide to use particular function(s), protocol(s)) and how you will control/manage connections (what happens in control plane once the video/audio files are being streamed). Differentiate in your description how you deal with audio and video and what needs to be done in the control plane to have the audio and video delivered in synchronized manner.(1) (15 Points) Propose algorithms/functions, protocols, and architectural constructs for the data plane for your video/audio chat system, i.e., explain how you will stream video between clients, what needs to be considered to provide guaranteed delivery (what functions, protocols, capabilities must be in place to deliver guaranteed chat service to clients, in what order the functions/protocols need to be used, and why did you decide to use the particular functions, protocols, capabilities). Again, make it clear how you deal with audio and video and how you deliver synchronized audio and video.Problem 4. (10 Points) Synchronization Consider the following Interval-based specification: Audio1 while(5,0) RecordedInteractions Audio1 before(0) Video 1; Video1 before(0) Video2; Video2 before(50) Video3; Video3 while (5,10) UserInteraction; Video3 before(30) Audio2; Audio2 while(0,0) Animation; Slide1 before(100) UserInteraction; Slide1 before(0) Slide2; Transform the interval-based specification into (1) time-axis-based specification and (2) hierarchical specification. Argue clearly what synchronization information you could capture with the following (interval-based, time-axis-based and hierarchical) specifications and which synchronization information got lost.Problem 5: Peer-to-Peer Streaming (20 Points) Consider one VOD server and three peers (P1, P2, P3) that share playback of the same
View Full Document
Unlocking...