Load Balancing in Distributed Systems

Table of Contents:

People:

Overview:

The research project aims at developing a load balancing system that provides a high transparency for the user. Different methods for obtaining and evaluating the work load of a machine were investigated. A new approach is to use neural networks for computing the configuration parameters of the load balancing systems to ease the adaption to changing environments.

At present the system for transparent migration of communicating process groups between workstations is being implemented to enable research on dynamic preemptive process group scheduling techniques.

Software:

• YALB: Yet Another Loadbalancing System
  The YALB-System is a load balancing system for heterogeneous workstation environments. The YALB-System has been tested on Sun Sparcstations and SS 10/30 (sun4c, sun4m) under SunOS 4.1.1 and 4.1.3 respectively.
  The YALB-System consists of the following programs and files:
  • loaddaemon
    The Load-Daemon calculates the local load of a host (based on the CPU-runqueue and the speed factor of the machine) and sends it to all other hosts in the system. It also performs authentication checks (similar to RFC 931).
  • loadmanager
    The Load-Manager collects the local loads from all hosts and selects the fastest host for execution.
  • rexecmanager
    The Rexec-Manager executes remote jobs for a client.

• Lmake - A Parallel Make
  Lmake is a parallel make utility that speeds up program compilation by running commands in parallel on several hosts. Lmake needs either PVM 3 (version 3.3.6 or higher) or the loadbalancing system Yalb.

• : Load Balancing and Fault Tolerance for Distributed Applications in Workstation Clusters

  now has its own home page.
  It is still being developed in cooperation with the IBR of the TU BS.

  Current State of the Implementation

  can be made available freely to interested people.
  Send a mail to Stefan Petri

  Summary: The features that we described in the papers really do work :-)
  
  We have concentrated our efforts on the functionality to demonstrate that our ideas lead to a feasible and efficient implementation. Because of too low man power, we have not yet spent much effort on things like user interface, so the system currently runs only under ``laboratory conditions''. The current work focusses on debugging the support for transparent breakdown and reestablishment of TCP connections for migration or rollback (it mainly works, but we are hunting race conditions *sigh*), and on rewriting the name space maintenance in a more structured approach, so that we can more easily exchange and test different synchronization methods, to test performance and scalability.

Papers published in this Project:

• B. Schnor:
  Architectures and Algorithms for Group Scheduling,
  Proceedings of the International Conference on Parallel Computing Technologies 1993, Obninsk, 1993, pages 225--233.

• H. Langendörfer and B. Schnor:
  Verteilte Systeme, Lehrbuch in der Reihe ``Praktische Informatik'',
  Hanser Verlag, München (1994).

• B. Schnor:
  Dynamic Scheduling of Parallel Applications,
  Lecture Notes in Computer Science 964, Parallel Computing Technologies, Third International Conference, PaCT-95, St. Petersburg, 1995, pages 109-116.

• B. Schnor and H. Langendörfer and S. Petri:
  Einsatz neuronaler Netze zur Lastbalancierung in Workstationclustern.
  In Praxisorientierte Parallelverarbeitung, Ed. H. Langendörfer, Hanser, München, October 1994, pages 154-165 (in german).

• S. Petri and H. Langendörfer:
  Load Balancing and Fault Tolerance in Workstation Clusters - Migrating Groups of Communicating Processes
  Operating Systems Review, Vol. 29, No. 4, October 1995, pp. 25-36

• S. Petri and B. Schnor and H. Langendörfer:
  -- Fehlertoleranz für verteilte Anwendungen mittels Migration und Checkpointing
  In Workstations und ihre Anwendungen - Proceedings der Fachtagung SIWORK'96, Ed. C.H. Cap, May 14./15. 1996, vdf Hochschulverlag, Zürich, pages 91-102 (in german).

• B. Schnor and S. Petri and H. Langendörfer:
  Load Management for Load Balancing on Heterogeneous Platforms: A Comparison of Traditional and Neural Network Based Approaches
  In Euro-Par'96 -- Parallel Processing Proceedings of the Second International Euro-Par Conference, Volume II, Eds. L. Bouge, P. Fraigniaud, A. Mignotte, Y. Robert. Springer Lecture Notes in Computer Science 1124, pages 615-620. ENS Lyon, France, August 27-29, 1996.

• B. Schnor and S. Petri and R. Oleyniczak and H. Langendörfer:
  Scheduling of Parallel Applications on Heterogeneous Workstation Clusters
  In K. Yetongnon and S. Hariri (Ed.), Proceedings of PDCS'96 -- ISCA 9th International Conference on Parallel and Distributed Computing Systems, pages 330-337, Dijon, France, September 1996.

• B. Schnor and S. Petri and H. Langendörfer:
  A Detailed Comparison of Traditional and Neural Network Based Approaches for Load Metrics on Heterogeneous Platforms
  In H.G. Matthies und J. Schüle (Eds.), Paralleles und Verteiltes Rechnen -- Beiträge zum 4. Workshop über Wissenschaftliches Rechnen, pages 93-106, Braunschweig, 9.-11. Oktober 1996.

• S. Petri and B. Schnor and H. Langendörfer and Jens Steinborn:
  Consistent Global Checkpoints for Distributed Applications on Clusters of Workstations
  In H.G. Matthies und J. Schüle (Eds.), Paralleles und Verteiltes Rechnen -- Beiträge zum 4. Workshop über Wissenschaftliches Rechnen, pages 77-86, Braunschweig, 9.-11. Oktober 1996.

• S. Petri and B. Schnor and M. Becker and B. Hinrichs and T. Tscharntke and H. Langendörfer:
  Evaluation of Multicast Methods to Maintain a Global Name Space for Transparent Process Migration in Workstation Clusters
  In M. Zitterbart (Ed.), Kommunikation in Verteilten Systemen, GI/ITG Fachtagung KIVS'97, pages 224-234, Braunschweig, 18.-21. Februar 1997. Springer.

• S. Petri:
  Lastausgleich und Fehlertoleranz in Workstation-Clustern
  PhD Thesis, TU Braunschweig, 1997. Shaker Verlag, Aachen, ISBN 3-8265-2471-3 (in german).

• S. Petri and M. Bolz and H. Langendörfer:
  Migration and Rollback Transparency for Arbitrary Distributed Applications in Workstation Clusters
  Informatik-Bericht Nr. 98-02, TU Braunschweig, April 1998.

• Studien- und Diplomarbeiten (Students' and Master's Theses, in german):
  • Matthias Becker: Vergleich zuverlässiger multicastbasierter Synchronisationsverfahren zur Verwendung in CSCW-Systemen. Diplomarbeit, TU Braunschweig, April 1997. (pbeam-becker97.ps.gz) (352163 Bytes)
    Source and Trace Data

  • Matthias Bolz: Transparente Umlenkung von Systemaufrufen für unmodifizierte Programme in P-Beam. Diplomarbeit, TU Braunschweig, November 1997. (pbeam-bolz97.ps.gz) (435952 Bytes)

  • Henrik Carlsson: Konfiguration von Lastbalancierungssystemen. Diplomarbeit, TU Braunschweig, 1994. (yalb-carlsson94.ps.gz)

  • Lars Düning: Migrationstransparenz für verbindungsorientierte Kommunikation in Workstation Clustern. Diplomarbeit, TU Braunschweig, Oktober 1997. (pbeam-duening97.ps.gz) (260276 Bytes)

  • Marc Gehrke: Ressourcemanagement für PVM-Anwendungen. Diplomarbeit, TU Braunschweig, 1996. (yalb-gehrke96.ps.gz) (247744 Bytes)

  • Thomas Gottschalk: Entwurf und Implementierung eines Monitoring-Systems für verteilte Anwendungen. Diplomarbeit, TU Braunschweig, April 1997. (pbeam-gottschalk97.ps.gz) (319865 Bytes)

  • Carsten-Marcel Grabb: Einsatz neuronaler Netze zur Lastermittlung in verteilten Systemen. Diplomarbeit, TU Braunschweig, 1995. (yalb-grabb95.ps.gz)

  • Martin Hauner: Simulation von Schedulingverfahren für parallele Anwendungen in homogenen und heterogenen verteilten Systemen. Diplomarbeit, TU Braunschweig, Juli 1997. (yalb-hauner97.tar.gz) (simulator source and thesis text) and the corresponding trace data

  • Bernd Hinrichs und Titus Tscharntke: Aufbau eines echt verteilten Namensraumservices für die transparente Prozeßmigration zwischen Workstations. Studienarbeit, TU Braunschweig, 1996.

  • Michael Höding: Aufbau eines globalen Namensraumes für die transparente Prozeßmigration zwischen Workstations. Diplomarbeit, TU Braunschweig, 1994.

  • Steffen Jobst: Lastverteilung in verteilten Systemen als Ansatz zur Wirtschaftlichkeitssteigerung von EDV-Investitionen . Studienarbeit, TU Braunschweig, 1995.

  • Carsten Kämmerer: Fehlersuche in verteilten Systemen. Diplomarbeit, TU Braunschweig, 1994.

  • Eva Körber: Werkzeuge zur Bewertung von Lastverteilungsverfahren. Studienarbeit, TU Braunschweig, 1995. (yalb-koerber95.ps.gz)

  • Sven Kühne: Gruppen-Scheduling. Studienarbeit, TU Braunschweig, 1993.

  • Martin Loitz: Entwurf und Implementierung eines parallelen make-Programms. Diplomarbeit, TU Braunschweig, 1993.

  • Martin Loitz: Entwurf und Implementierung einer Lastverteilungskomponente für Lmake unter PVM. Studienarbeit, TU Braunschweig, 1995.

  • Reinhard Oleyniczak: Simulation von Schedulingverfahren für parallele Anwendungen in homogenen und heterogenen verteilten Systemen . Diplomarbeit, TU Braunschweig, Februar 1997. (yalb-oleyniczak97.ps.gz) (283587 Bytes)

  • Susann Sattler: Leistungsanalyse von Algorithmen für Gruppen-Scheduling. Studienarbeit, TU Braunschweig, 1995.

  • Jens Steinborn: Globale konsistente Checkpoints für verteilte Anwendungen in Workstation Clustern. Diplomarbeit, TU Braunschweig, 1996. (pbeam-steinborn96.ps.gz) (180935 Bytes)

  • Stefan Stille: Lastbalancierung in verteilten Systemen . Diplomarbeit, TU Braunschweig, 1993. (yalb-stille93.ps.gz)

  • Dirk Wodtke: Effizienz von Broadcast-Primitiven. Studienarbeit, TU Braunschweig, 1992.

• Seminarausarbeitungen (in german):
  • Paralleles und Verteiltes Rechnen, Sommer 1994.

  • Paralleles und Verteiltes Rechnen - Fehlersuche und Fehlertoleranz in verteilten Systemen, Sommer 1995.

  • Paralleles und Verteiltes Rechnen - Lastausgleich in Verteilten Systemen, Sommer 1996.

Pointers to related Work:

• Our page with references to process migration related work

  ---

• Mor Harchol-Balter's Papers, notably A note on 'The Limited Performance Benefits of Migrating Active Processes for Load Sharing' and Exploiting Process Lifetime Distributions for Dynamic Load Balancing.

•     From: Alan Heirich <heirich@cacr.caltech.edu>
      Message-Id: <199606192242.PAA20245@delilah.cacr.caltech.edu>
      Subject: online load balancing and mapping references
      To: petri@ibr.cs.tu-bs.de
      Date: Wed, 19 Jun 1996 15:42:21 -0700 (PDT)
      

  Hi, I would like you to visit my home page to find two published articles about using diffusion algorithms to solve the problems of load balancing and mapping on distributed systems. I hope you will include them on your web site. Thanks very much!

      -- 
      :::::[ ALAN HEIRICH, URL http://www.cs.caltech.edu/~heirich/heirich.html ]:::::
      :::     Computational Scientist, Center for Advanced Computing Research     :::
      ::[ heirich@caltech.edu  (818) 395-4600, 256-80 Caltech, Pasadena, CA 91125 ]::