Xref: utzoo ont.events:1385 uw.talks:78 uw.cs.grad:65
Path: utzoo!utgpu!watmath!maytag!water!wlrush
From: wlrush@water.waterloo.edu (Wenchantress Wench Wendall)
Newsgroups: ont.events,uw.talks,uw.cs.grad
Subject: SYSTEMS SEMINAR
Keywords: Dr. Mohammad Malkawi, Dept. of Electrical Eng. & Comp. Sci.
Message-ID: <2760@water.waterloo.edu>
Date: 17 Nov 89 15:01:03 GMT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 47


DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

SYSTEMS SEMINAR

                    -Thursday, November 23, 1989

Dr.  Mohammad  Malkawi, Dept. of Electrical Engineering
and Computer Science, University of Wisconsin-Milwaukee
will   speak   on   ``Load   Balancing  in  Distributed
Systems.''

TIME:                 3:30 p.m.

ROOM:                 DC 1304

ABSTRACT

In  a  distributed  network,  it is very  important  to
balance  the   load among the processors in the network
such  that the average response time in the system is
imroved.  A  new  load   balancing algorithm  has  been
developed based on graph coloring. Each link connecting
any  two nodes is assigned a color such that the  links
adjacent   to  any  one node are colored with different
colors.  To  balance the load of the  system,  adjacent
processors   connected  with   a link of color C  share
                                                i
the  loads between them such that their load difference
is  reduced  to  a value <^H_ 1. To  balance the  load  in
the   system,  all  colors  have  to be considered in a
cyclic  order.   The  process  of  balancing  continues
until   the difference  between  the  loads of adjacent
processors is no more than 1.

The   described  algorithm  is  distributed,   dynamic,
and   requires   no   global  knowledge  of  any  type.
Simulation  results  will  be  discussed. The algorithm
achieves  significant  improvements   in response  time
and  throughput.   Simulation  is  performed  for  both
static   and   dynamic  systems.  Different  networking
topologies   are considered including random graphs and
n-cube structures.

                   November 15, 1989