Efficient network and I/O throttling for fine-grain cycle stealing

ABSTRACT

This paper proposes and evaluates a new mechanism, rate windows, for I/O and network rate policing. The goal of the proposed system is to provide a simple, yet effective way to enforce resource limits on target classes of jobs in a system. This work was motivated by our Linger Longer infrastructure, which harvests idle cycles in networks of workstations. Network and I/O throttling is crucial because Linger Longer can leave guest jobs on non-idle nodes and machine owners should not be adversely affected. Our approach is quite simple. We use a sliding window of recent events to compute the average rate for a target resource. The assigned limit is enforced by the simple expedient of putting application processes to sleep when they issue requests that would bring their resource utilization out of the allowable profile. Our I/O system call intercept model makes the rate windows mechanism light-weight and highly portable. Our experimental results show that we are able to limit resource usage to within a few percent of target usages.

REFERENCES

• 1: Mohit Aron , Peter Druschel, Soft timers: efficient microsecond software timer support for network processing, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.232-246, December 12-15, 1999, Charleston, South Carolina, United States
• 2: Remzi H. Arpaci , Andrea C. Dusseau , Amin M. Vahdat , Lok T. Liu , Thomas E. Anderson , David A. Patterson, The interaction of parallel and sequential workloads on a network of workstations, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.267-278, May 15-19, 1995, Ottawa, Ontario, Canada
• 3: Alia Atlas , Azer Bestavros, Design and Implementation of Statistical Rate Monotonic Scheduling in KURT Linux, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.272, December 01-03, 1999
• 4: Gaurav Banga , Peter Druschel , Jeffrey C. Mogul, Resource containers: a new facility for resource management in server systems, Proceedings of the third symposium on Operating systems design and implementation, p.45-58, February 1999, New Orleans, Louisiana, United States
• 5: J. Bruno, E. Gabber, B. Ozden, and A. Silberschatz, "The Eclipse operating system: Providing Quality of Service via Reservation Domains," USENIX 1998 Annual Technical Conference. June 1998, New Orleans, Louisiana.
• 6: Edouard Bugnion , Scott Devine , Mendel Rosenblum, Disco: running commodity operating systems on scalable multiprocessors, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.143-156, October 05-08, 1997, Saint Malo, France
• 7: Theodore Faber , Lawrence H. Landweber , Amarnath Mukherjee, Dynamic Time Windows: packet admission control with feedback, Conference proceedings on Communications architectures & protocols, p.124-135, August 17-20, 1992, Baltimore, Maryland, United States
• 8: Wu-chang Feng , Dilip D. Kandlur , Debanjan Saha , Kang G. Shin, Understanding and improving TCP performance over networks with minimum rate guarantees, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.173-187, April 1999 [doi>10.1109/90.769766]
• 9: R. P. Goldberg, "Survey of Virtual Machine Research," IEEE Computer Magazine,7(6), 1974, pp. 34-45.
• 10: John S. Heidemann , Gerald J. Popek, File-system development with stackable layers, ACM Transactions on Computer Systems (TOCS), v.12 n.1, p.58-89, Feb. 1994 [doi>10.1145/174613.174616]
• 11: P. Krueger and R. Chawla, "The Stealth Distributed Scheduler," International Conference on Distributed Computing Systems (ICDCS). May 1991, Arlington, TX, pp. 336-343.
• 12: M. Litzkow, M. Livny, and M. Mutka, "Condor --- A Hunter of Idle Workstations," International Conference on Distributed Computing Systems. June 1988, pp. 104-111.
• 13: Matt W. Mutka , Miron Livny, The available capacity of a privately owned workstation environment, Performance Evaluation, v.12 n.4, p.269-284, July 1991 [doi>10.1016/0166-5316(91)90005-N]
• 14: V. N. Padmanabhan and R. H. Katz, "TCP Fast Start: A Techniques for Speeding Up Web Transfers," IEEE GLOBECOMM. Nov. 1998, Sydney, Australia, pp. 41-46.
• 15: D. Reed and R. Fairbairns, The Nemesis KernelOverview, http://citeseer.nj.nec.com/reed97nemesis.html, May 20, 1997.
• 16: Kyung Dong Ryu , Jeffrey K. Hollingsworth, Exploiting Fine-Grained Idle Periods in Networks of Workstations, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.683-698, July 2000 [doi>10.1109/71.877793]
• 17: Kyung Dong Ryu , Jeffrey K. Hollingsworth , Peter J. Keleher, Mechanisms and policies for supporting fine-grained cycle stealing, Proceedings of the 13th international conference on Supercomputing, p.93-100, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305170]
• 18: SiliconGraphics, IRIX 6.4 Technical Brief, http://www.sgi.com/software/irix6.5/techbrief.pdf, 1998.
• 19: J. S. Turner, "New Directions in Communications (or Which Way to the Information Age?)," IEEE Communications Magazine,24(10), 1986, pp. 8-15.
• 20: Ben Verghese , Anoop Gupta , Mendel Rosenblum, Performance isolation: sharing and isolation in shared-memory multiprocessors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.181-192, October 02-07, 1998, San Jose, California, United States
• 21: L. Zhang, Virtual clock: a new traffic control algorithm for packet switching networks, Proceedings of the ACM symposium on Communications architectures & protocols, p.19-29, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 22: Songnian Zhou , Xiaohu Zheng , Jingwen Wang , Pierre Delisle, Utopia: a load sharing facility for large, heterogeneous distributed computer systems, Software—Practice & Experience, v.23 n.12, p.1305-1336, Dec. 1993 [doi>10.1002/spe.4380231203]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Parallel I/O

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Measurement, Performance