Schedule of Presentations (around 20 minutes each) If you are not presenting on the specified day, you are still expected to attend, and take brief notes of the talks and ask questions. Please turn in these notes with your final project report (due on last day of class). 4/14/2004 ---------------------------------------------------------------- Avula, Sai Krishna Feedback EDF scheduling algorithm Design and evaluation of a feedback control EDF scheduling algorithm Lu, C.; Stankovic, J.A.; Tao, G.; Son, S.H.; Imprecise computations Liu, J.W.S.; Wei-Kuan Shih; Kwei-Jay Lin; Bettati, R.; Jen-Yao Chung; Misconceptions about realtime systems",J. Stankovic. http://www.cc.gatech.edu/classes/AY2001/cs6235_spring/papers/02-2 6-L14-FB_EDF.pdf ---------------------------------------------------------------- Chandrasekhar, Raj Intelligent GPS-based routing system Digital Map/GPS Based Routing and Addressing Scheme for Wireless Ad-hoc Networks^Ô, Albert M.K. Cheng;, Koushik Rajan, Intelligent Vehicle symposium, IEEE 2003. (=Department of Computer Science, University of Houston). ^ÓGPS-Based Message Broadcast for Inter-vehicle Communications^Ô, Min-Te-Sun¥, Wu-chi Feng¥, Ten-Hwang Lai¥, Kentaro Yamada^À, Hiromi Okada^À, Kikuo Fujimura£, Vehicular Technology Conference, IEEE 2000. (¥=Department of Computer & Information Science, Ohio State University, ^À=Department of Electrical Engineering, Kansai University, £=Honda R&D Americas, Fundamental Research Laboratories). GPS-Based Message Broadcast for Adaptive Inter-vehicle Communications, Min-Te-Sun, Wu-chi Feng, Ten-Hwang Lai¥, Kentaro Yamada^À, Hiromi Okada^À, Kikuo Fujimura£, Vehicular Technology Conference, IEEE 2000. (¥=Department of Computer & Information Science, Ohio State University, ^À=Department of Electrical Engineering, Kansai University, £=Honda R&D Americas, Fundamental Research Laboratories). Geographical Routing Using Partial Information for Wireless Ad Hoc Networks^Ô, Rahul Jain, Anuj Puri, Raja Sengupta, Technical Memorandum, UCB/ERL M99/69. (=University of Calfornia, Berkeley). GPS-based Geographic Addressing, Routing and Resource Discovery, Tomasz Imielinski, Julio C. Navas, Communications of the ACM, 4,4(1999), 86-92. (=Computer Science Department, Rutgers University). http://www.lirc.org/receivers.html ---------------------------------------------------------------- Chen, Hua Replacement policy of Nonuniform Objects in Web caches, with the focus on Least-Unified Value algorithm. 0. A. M. K. Cheng and Z. Zhang, ``Adaptive Proxy Caching for Web Servers in Soft Real-Time Applications,'' Proc. WIP Session, 23rd IEEE Real-Time Systems Symposium, Austin, TX, December 3-5, 2002. 1. H. Bahn et al., ^ÓEfficient Replacement of Nonunfiorm Objects in Web Caches^Ô, Computer, 2002, pp. 65-73. 2. T. M. Kroeger et al. ^ÓExploring the Bounds of Web Latency Reduction from Caching a Prefetching^Ô, Proc. Usenix Symp. Internet Technologies and Systems (USITS 97), Usenix, Berkeley, Calif., 1997, pp. 13-22 3. H. Bahn et al., ^ÓUsing Full Reference History for Efficient Document Replacement in Web Caches^Ô, Proc. Usenix Symp. Internet Technology and Systems, 1999, pp. 187-196 4. D. Lee et al., ^ÓLRFU: A spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies^Ô, IEEE Trans. Computers, vol. 50, no. 12, 2001, pp. 1352-1361 5. L. Rizzo and L. Vicisano, ^ÓReplacement Policies for a Proxy Cache^Ô, IEEE/ACM Trans. Networking, vol. 8, no. 2, 2000, pp. 158-170 6. M. Abrams, C. Standridge, G. Abdulla, S. Williams, and E. Fox, ^ÓCaching proxies: Limitations and Potentials^Ô, Proc. 4th International WWW Conference, 1995, pp. 119-133 7. N. Niclausse, Z. Liu, and P. Nain, ^ÓA new and efficient caching policy for the world wide web^Ô, In Workshop on Internet Server Performance, 1998. 8. S. Williams, M. Abrams, C. Standridge, G. Abdulla, and E. Fox, ^ÓRemoval policies in network caches for world-wide web documents^Ô, Proc. ACM SIGCOMM^Ò96, 1996, pp. 293-305 9. C. Aggarwal, J. Wolf, and P. Yu, ^ÓCaching on the World Wide Web^Ô, IEEE Trans. Knowledge and Data Eng., vol. 11, no. 1, 1999, pp. 94-107 10. D. Wessels and K. Claffy, ^ÓInternet Cache Protocol (ICP) v2^Ô, 1997, http://icp.ircache.net/rfc2186.txt 11. V. Valloppillil and K. W. Ross, ^ÓCache Array Routing Protocol v1.0^Ô, 1998, http://icp.ircache.net/carp.txt 12. P. Rodriguez, C. Spanner, and E. W. Biersack, Analysis of Web Caching Architectures: Hierarchical and Distributed Caching, IEEE/ACM Trans. Networking, 2001, pp. 404-418 ---------------------------------------------------------------- 4/19/2004 ---------------------------------------------------------------- Chen, Yingchun "Transaction Scheduling Study in Mobile Real-time Databases System" References: 1. J. Stankovic etc., Misconceptions About Real-Time Databases, Cybersquare, 1999 IEEE, pp. 29-35 2. Pasi Porkka, http://www.cs.helsinki.fi/u/kraatika/Courses/Old/RTS97/porkka.htm l, Overview of Real-Time Databases, 1997 3. Broadcast Transaction Scheduling in Mobile Computing Environments Proceedings of the Third International Conference on Mobile Data Management (MDM.02), 2002, IEEE Computer Society ---------------------------------------------------------------- Cole, Ryan Energy-efficient scheduling ---------------------------------------------------------------- Dandu, Satish Multiprocessor Scheduling ---------------------------------------------------------------- Feng, Shih-Chen Multiprocessor Scheduling Via Resource Augmentation. Materials of the talk mainly will come from these papers: Optimal Time-Critical Scheduling Via Resource Augmentation, ACM 1997 by Cynthia A. Phillips, Cliff Stein, Eric Torng, and Joel Wein On-line Scheduling on Uniform Multiprocessors, IEEE 2001, by Shelby Funk, Joel Goossens, and Sanjoy Baruah Static-priority scheduling on multiprocessors, IEEE 2001, by Bjorn Andersson, Sanjoy Baruah, and Jan Jonsson ---------------------------------------------------------------- Chen, Dajun MAKE LINUX A REAL-TIME OPERATING SYSTEM references: http://www.embedded.com/story/OEG20010418S0044 http://www.cs.helsinki.fi/u/kraatika/Courses/sem02a/abukar.pdf http://www.cse.ucsc.edu/~vaibhav/cs221/cs221propos.html ---------------------------------------------------------------- 4/21/2004 ---------------------------------------------------------------- Gonuguntla, Sai Prasad DVS Algorithm for Fixed-Priority Real-Time Systems Using Work-Demand Analysis (RM Scheduling, algorithm simulation, analysis and improvement) Authors: Woonseok Kim, wskim@archi.snu.ac.kr Jihong Kim, jihong@davinci.snu.ac.kr, Sang Min, School of Computer Science and Engineering Seoul National University ENG4190, Seoul, Korea, 151-742 [1] T. Sakurai and A. Newton. Alpha-power Law MOSFET Model and Its Application to CMOS Inverter Delay and Other Formulas. IEEE Journal of Solid State Circuits, 25(2):584^Ö594, 1990. [2] J. P. Lehoczky and S. Ramos-Thuel. An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems. In Proceedings of the IEEE Real-Time Systems Symposium, pages 110^Ö123, Dec 1992. [3] T. S. Tia, J. W. S., and M. Shankar. Algorithms and Optimality of Scheduling of Soft Aperiodic Requests in Fixed- Priority Preemptive Systems. Journal of Real-Time Systems, 10(1):23^Ö43, 1996. [4] H. Aydin, R. Melhem, D. Mosse, and P. M. Alvarez. Dynamic and Aggressive Scheduling Techniques for Power- Aware Real-Time Systems. In Proceedings of IEEE Real-Time Systems Symposium, pages 95^Ö105, December 2001. [5] P. Pillai and K. G. Shin. Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems. In Proc. of 18th ACM Symposium on Operating Systems Principles, 89^Ö102, Oct 2001. [6]F. Yao, A. Demers, and A. Shenker. A Scheduling Model for Reduced CPU Energy. In Proceedings of the IEEE Foundations of Computer Science, pages 374^Ö382, 1995. [7] W. Kim, D. Shin, J. Jeon, J. Kim, and S. L. Min. Performance Comparison of Dynamic Voltage Scaling Algorithms for Hard Real-Time Systems. In Proc. of Real-Time and Embedded Technology and Applications Symp., 219^Ö228, Sept. 2002. [8] Y. Shin, K. Choi, and T. Sakurai. Power Optimization of Real-Time Embedded Systems on Variable Speed processors. In Proceedings of the International Conference on Computer-Aided Design, 365^Ö368, Nov 2000. [9] J. Lehoczky, L. Sha, and Y. Ding. The Rate Monotonic Scheduling Algorithm : Exact Characterization and Average Case Behavior. In Proceedings of the IEEE Real-Time Systems Symposium, pages 166^Ö171, December 1989. [10] D. Shin, W. Kim, J. Jeon, J. Kim, and S. L. `Min. SimDVS: An Integrated Simulation Environment for Performance Evaluation of Dynamic Voltage Scaling Algorithms. In Proceedings of Workshopon Power-Aware Computer Systems, February 2002. Other references: [1]DVS technique for low-power multimedia applications using buffers Chaeseok Im et.al., ISLPED'01 [2]The Performance and Energy Consumption of Three Embedded Real-Time Operating Systems Kathleen Baynes, Chris Collins, Eric Fiterman, Brinda Ganesh, Paul Kohout, Christine Smit, and Bruce Jacob CASES'01, November 16-17, 2001, [3]T. Pering,T. Burd,R. Brodersen,"The simulation and evaluation of dynamic voltage scaling algorithms", ISLPED, Aug. 98. [4]Quantitative Analysis of Dynamic Voltage Scaling Algorithms for Hard Real-Time Systems Woonseok Kim Jihong Kim Sang Lyul Min [5]H. Saputra, M. Kandemir, N. Vijaykrishnan, M. J.Irwin, J. S. Hu, C.-H. Hsu, and U. Kremer. Energy-Conscious Compilation based on Voltage Scaling. In Proceedings of the joint conference on Languages, Compilers and Tools for Embedded Systems, pages 2^Ö11. ACM Press, 2002. [6]A Dynamic Voltage Scaling Algorithm for Dynamic-Priority Hard Real-Time Systems Using Slack Time Analysis Woonseok Kim_ Jihong Kim_ Sang Lyul Min_School of Computer Science and Engineering Seoul National University ENG4190, Seoul, Korea, 151-742 Useful Simulation Tools: SimDVS, SimBed, DEW, BEE, PARSEC simulation platform. ---------------------------------------------------------------- Lian, Xiaomeng "Machine Learning Algorithm Applied to Real Time Network Surveillance System". The content and idea mostlycome from Ricardo Vilalta, Sheng Ma, Predicting Rare Events In Temporal Domains, IEEE 2002 Zhen Zhu, Albert M K Cheng, Worst Case Round Trip Time Prediction and Statistical Analysis Using Extreme Values Theory, IEEE RTSS WIP 2003. ---------------------------------------------------------------- Ma, Zhibin "Real-time Packet Capture and Analyze" I wrote a program to real-time monitor the network card, and capture the specific packets. This program is useful for Network security and intrusion detection. Reference: 1. Packet Capture With libpcap and other Low Level Network Tricks http://www.cet.nau.edu/~mc8/Socket/Tutorials/section1.html 2. BPF+: exploiting global data-flow optimization in a generalized packet filter architecture Cambridge, Massachusetts Year of Publication: 1999 3. Papers: mmdump: a tool for monitoring internet multimedia traffic Jacobus van der Merwe, Ramón Cáceres, Yang-hua Chu, Cormac Sreenan October 2000 4. TCP structure http://mictlan.sfsu.edu/~dachen/documents/Overview.htm 5. Packet Capture With libpcap and other Low Level Network Tricks http://www.cet.nau.edu/~mc8/Socket/Tutorials/section1.html 6. IP Packet Structure http://www.freesoft.org/CIE/Course/Section3/7.htm 7. Libpcap online ducument ---------------------------------------------------------------- Mallampati, Silpa "Real-time Networking".I prepare to present my ideas of making the network more reliable for transmission,without missing the deadlines and the packets, by using the UserDatagram Protocol. http://www.ietf.org/rfc.html TCP: RFC 793 http://www-et.cs.umass.edu/kurose/transport/UDP.html FEC:http://www.ece.wpi.edu/courses/ee535/hwk97/hwk4cd97/bad/paper lhtm http://web.haystack.mit.edu/e-vlbi/dudevoir.pdf http://www.laynetworks.com/Comparative%20analysis_TCP%20Vs%20UDP. htm http://www.startap.net/euro-link/images/PDF/RayFangFEC1999.pdf http://www.vhml.org/theses/cechner/html/node18.html http://phptr.com/articles/article.asp?p=169578&seqNum=3 http://www.gweep.net/~rocko/mqp/node13.html#SECTION00730000000000 TCP/IP Protocol Suite,by Forouzan. ---------------------------------------------------------------- 4/26/2004 ---------------------------------------------------------------- McClain, Joel (absent, talk on 4/28 or 5/3) ---------------------------------------------------------------- Patel, Amisha Energy reduction utilizing a Pseudo Sprint and Halt Scheduling Technique My references are 1)Sprint and Halt Scheduling for Energy Reduction in Real Time Systems with Software Power-Down by Padmanabhan Pillai and Kang G. Shin 2)A Survey of Design Techniques for System-Level Dynamic Power Management by L. Benini, A. Bogliolo and G. De Micheli (IEEE Transactions on very large scale integration (VLSI) systems, Vol. 8, No.3, June 2000 ---------------------------------------------------------------- Rai, Swetha Topic : Energy Efficient Real Time Transaction Management In Mobile Ad-Hoc Networks References : ^ÓTransaction Processing in Mobile Computing Environments^Ô,Chrysanthis, P.K., IEEE Workshop on Advances in Parallel and Distributed Systems, October 1993 ^ÓA Transaction Model for Mobile Computing^Ô, Madria, S. K., B. K. Bhargava, International Database Engineering and Application Symposium (IDEAS 1998), July 1998. http://ipdps.eece.unm.edu/1998/wpdrts/kylam.pdf http://www.cse.cuhk.edu.hk/~acm-hk/activity/pg/cityu-kylam3.pdf http://www.ee.surrey.ac.uk/Personal/G.Aggelou/MANET_PUBLICATIONS.html ^ÓEvaluating the Performance of Mobile Agent-Based Communication among Mobile Hosts in Large Ad-Hoc Wireless Network"] Bandyopadhyay, S., and K. Paul, ^ÓA Mobile Transaction Model that Captures Both the Data and Movement Behavior^Ô,Dunham M., A. Helal, S. Balakrishnan S., Mobile Network and Applications, Vol. 2, No. 2, October 1997. ---------------------------------------------------------------- Shaikh, Aysha "A Fair Resource Allocation Protocol for Multimedia Wireless Networks, providing QoS guarantees". I will be giving a brief introduction about what is Quality of Service(QoS), and then will switch over to describe the above mentioned protocol, which talks about satisfying the QoS requirements in a multimedia network. It basically stresses on two QoS parameters: Admission Control and Bandwidth Allocation. Following are the references used in the making of this project: Anjilica Malla, Mona El-Kadi, Stephen Olariu and Petia Todorova, " A Fair Resource Allocation Protocol for Multimedia Wireless Networks," IEEE Transactions on Parallel and Distributed Systems Vol 14. NO. 1., January 2003. A. Acampora and M. Naghshineh, "Control and Quality-of-Service Provisioning in High-Speed Microcellular Networks," IEEE Personal COlumn, vol.1, 1994. P.Agarwal, D.K. Anvekar, and B.Narendran, "Channel Management Policies for Handovers in Cellular Networks," Bell Labs Technical J.., vol. 1, pp.96-109,1996 A.Aljadahai and T.F. Znati, "A framework for Call ADmission Control and Qos Support in Wireless Environments," Proc INFOCOMM Int'l,pp.1019-1027, 1999 D.Bertsekas and R.Gallager, "Data Networks," Prentice Hall, 1992 R.Bolla, F.Davoli, and M.Marchese, "Bandwidth Allocation and Admission Control in ATM Networks with Service Separation," IEEE Comm, pp. 130-137,1997. ---------------------------------------------------------------- 4/28/2004 ---------------------------------------------------------------- Shrivastava, Rishabh ---------------------------------------------------------------- Srinivasan, Suraj ---------------------------------------------------------------- Varada, Soujanya Power conscious fixed prority scheduing for hard real time systems. The refences are: [1] J. Lehoczky, L. Sha, and Y. Ding, ^ÓThe rate monotonic scheduling algorithm: exact characterization and average case behavior,^Ô in Proc. IEEE Real-Time Systems Symposium, pp. 166^Ö171, Dec. 1989. [2] M. Joseph and P. Pandya, ^ÓFinding response times in a real-time system,^Ô The Computer J., vol. 29, pp. 390^Ö395, Oct. 1986. [3] N. Audsley, A. Burns,M. Richardson, and A.Wellings, ^ÓHard real-time scheduling: The deadline-monotonic approach,^Ô in Proc. IEEE Workshop on Real-Time Operating Systems and Software, pp. 133^Ö137, May 1991. [4] C. Park and A. C. Shaw, ^ÓExperiments with a program timing tool based on source-level timing schema,^Ô IEEE Computer, pp. 48^Ö57, May 1991. [5] S. Lim, Y. Bae, G. Jang, B. Rhee, S. Min, C. Park, H. Shin, K. Park, and C. Kim, ^ÓAn accurate worst case timing analysis for RISC processors,^Ô in Proc. IEEE Real-Time Systems Symposium, pp. 97^Ö108, Dec. 1994. [6] Y. S. Li, S. Malik, and A. Wolfe, ^ÓPerformance estimation of embedded software with instruction cache modeling,^Ô in Proc. Int^Òl Conf. on Computer Aided Design, pp. 380^Ö387, Nov. 1995. [7] R. Ernst and W. Ye, ^ÓEmbedded program timing analysis based on path clustering and architecture classification,^Ô in Proc. Int^Òl Conf. on Computer Aided Design, pp. 598^Ö604, Nov. 1997. [8] S. Gary, ^ÓPowerPC: A microprocessor for portable computers,^Ô IEEE Design & Test of Computers, pp. 14^Ö23, Dec. 1994. [9] M. B. Srivastava, A. P. Chandrakasan, and R. W. Brodersen, ^ÓPredictive system shutdown and other architectural techniques for energy efficient programmable computation,^Ô IEEE Trans. on VLSI Systems, vol. 4, pp. 42^Ö55, Mar. 1996. [10] C. Hwang and A. Wu, ^ÓA predictive system shutdown method for energy saving of event-driven computation,^Ô in Proc. Int^Òl Conf. on Computer Aided Design, pp. 28^Ö32, Nov. 1997. [11] F. Yao, A. Demers, and S. Shenker, ^ÓA scheduling model for reduced CPU energy,^Ô in Proc. IEEE Annual Foundations of Computer Science, pp. 374^Ö382, 1995. [12] D. Katcher, H. Arakawa, and J. Strosnider, ^ÓEngineering and analysis of fixed priority schedulers,^Ô IEEE Trans. on Software Eng., vol. 19, pp. 920^Ö934, Sept. 1993. [13] A. Burns, K. Tindell, and A. Wellings, ^ÓEffective analysis for engineering realtime fixed priority schedulers,^Ô IEEE Trans. on Software Eng., vol. 21, pp. 475^Ö 480, May 1995. [14] T. Pering, T. Burd, and R. Brodersen, ^ÓThe simulation and evaluation of dynamic voltage scaling algorithms,^Ô in Proc. Int^Òl Symposium on Low Power Electronics and Design, pp. 76^Ö81, Aug. 1998. [15] C. Locke, D. Vogel, and T. Mesler, ^ÓBuilding a predictable avionics platform in Ada: a case study,^Ô in Proc. IEEE Real-Time Systems Symposium, Dec. 1991. [16] J. Liu, J. Redondo, Z. Deng, T. Tia, R. Bettati, A. Silberman, M. Storch, R. Ha, and W. Shih, ^ÓPERTS: A prototyping environment for real-time systems,^Ô Tech. Rep. UIUCDCS-R-93-1802, University of Illinois, 1993. [17] N. Kim,M. Ryu, S. Hong,M. Saksena, C. Choi, and H. Shin, ^ÓVisual assessment of a real-time system design: a case study on a CNC controller,^Ô in Proc. IEEE Real-Time Systems Symposium, Dec. 1996. The paper contains a power conservation algorithm using RAte monotonic scheduling. Essentially, I want to talk about power conservation using deadline monotonic scheduling using the algorithm. ---------------------------------------------------------------- Vassilaros, Nicholas ---------------------------------------------------------------- 5/3/2004 Regular lecture