INTRODUCTION and COURSE GOALS:  Many complex real-time application systems are specified and constructed in a modular manner, in which individual components are composed to build larger systems, which may in turn be composed to form even larger systems. As such hierarchical design techniques come to be increasingly used in real-time system design, it is incumbent that scheduling theory develop the necessary tools and techniques to accurately and efficiently  analyze the timing properties of such hierarchically-constructed systems.   In this research seminar, we will study recently-proposed techniques for the scheduling-theoretic analysis of hierarchically specified and constructed real-time application systems.

The focus of the course is primarily theoretical; hence, a certain degree of mathematical sophistication is expected.  If you are unsure whether you have this, please consult the instructor prior to signing up for the course.

INSTRUCTOR: Sanjoy Baruah.

MEETINGS: Tuesdays 5:00 - 7:30; SN 325
SYLLABUS and RUBRIC: There is no text-book for the course.  We  will study a number of recently-published  papers which will be handed out in class (or made available in electronic form).  There will be no assignments, tests, or other similar stress-inducing activities.  Each participant will be required to make a series of presentations to the class, and to complete a major semester project of sufficiently high quality that it could be submitted for consideration towards presentation at a decent conference, or publication in a decent journal. 

SPECIAL NEEDS: If you are entitled to extra accommodation for any reason (such as a disability), I will make every reasonable attempt to accommodate you. However, it is your responsibility to discuss this with the instructor during the first week of the course.

READING MATERIAL:

1.  Abeni and Buttazzo. Integrating Multimedia applications in Hard-Real-Time Systems. RTSS 1998.
2. Bennett and Zhang.  Hierarchical Packet-Fair Queueing Algorithms.  ACM/ IEEE Transactions on Networking 5(5). October 1997.
3. Lipari and Baruah.  Greedy reclaimation of unused bandwidth in constant-bandwidth servers.  EuroMicro RTS 2000.
   
4. Lipari and Baruah.  A hierarchical extension to the constant bandwidth server framework.  RTAS 2001.
5. Buttazzo.  Rate-Monotonic vs EDF: Judgement Day.    EMSOFT 2003
6. Ramabhadran and Pasquale.  Stratified Round-Robin: A low-complexity packet scheduler with bandwidth fairness and bounded delay.  SIGCOMM 2003
7. Xu and Lipton.  On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms.  SIGCOMM 2002
8. Lenstra, Shmoys, and Tardos.   Approximation algorithms for scheduling unrelated parallel machines.  Mathematical Programming 46 (1990)