PDF de programación - Un Algoritmo Distribuido y Cooperativo para Balance de Carga

Un Algoritmo Distribuido y Cooperativo para Balance

de Carga Dinamico

Natalia L. Weinbach

[email protected]

Javier Echaiz Alejandro J. Garca
[email protected]

[email protected]

Departamento de Ciencias e Ingeniera de la Computacion

Universidad Nacional del Sur.

Av. Alem 1253, (8000) Baha Blanca, Argentina

Resumen

En este trabajo presentamos un algoritmo de balance de carga, que presenta las si-
guientes caractersticas: es dinamico, distribuido, cooperativo, global, de asignacion por
unica vez, sub-optimo y heurstico. En nuestra propuesta, cada nodo recibe informacion
de la carga de otros nodos en forma asincronica, lo que le permite calcular de antemano
cual nodo tiene la menor carga en ese momento. Al arribar un nuevo proceso P a un
nodo N , en funcion de la carga de N y el mnimo previamente calculado, N decide si
P se ejecuta localmente o directamente lo transere al mejor candidato considerado por
N . El algoritmo no requiere informacion provista por el usuario, ni archivos historicos de
ejecucion para clasicar los tipos de procesos. Es estable y escalable mediante el ajuste de
ciertos parametros como la cantidad de nodos que puede atravesar durante la migracion
o transferencia inicial de proceso, y el valor de un umbral, que regula la distancia hacia
el nodo receptor e inuye tambien en la conabilidad de la informacion de carga que se
conoce del resto de los nodos. Al ser distribuido, presenta tolerancia a fallas, ya que no se
asigna una responsabilidad diferenciada a solo algunos nodos del sistema.

Palabras clave: Sistemas distribuidos. Paralelismo. Algoritmos de balance de carga

1.

Introduccion

En sistemas distribuidos o arquitecturas paralelas, una buena distribucion de la carga per-
mite obtener sustanciales mejoras en la performance del sistema. Sin embargo, uno de los
principales problemas que enfrentan la mayora de los algoritmos de balance de carga, es poder
decidir con rapidez donde ejecutar un nuevo proceso. El tiempo empleado en obtener la car-
ga de nodos remotos puede retardar notoriamente el inicio de ejecucion de un nuevo proceso,
aumentando de esta forma el tiempo de ejecucion del proceso y degradando la performance
global del sistema.

En este trabajo presentamos un algoritmo de balance de carga, que siguiendo la clasicacion
de Casavant en [1], presenta las siguientes caractersticas: es dinamico, distribuido, cooperativo,
global, de asignacion por unica vez, sub-optimo y heurstico (ver seccion 3). Es importante
destacar que el balance de carga estatico resulta simple y efectivo cuando la carga puede
caracterizarse lo sucientemente bien de antemano, pero falla cuando existen uctuaciones
en la carga del sistema [11]. El algoritmo que se ha desarrollado es dinamico, ya que reacciona
ante parametros del entorno que cambian dinamicamente, y balancea la carga del sistema en
el momento que los procesos arriban a un nodo.

En nuestra propuesta, cada nodo recibe informacion de la carga de otros nodos en forma
asincronica, lo cual le permite calcular de antemano que nodo tiene la menor carga en ese
momento. Al arribar un nuevo proceso P a un nodo N , en funcion de la carga de N y el mnimo
previamente calculado, N decide si P se ejecuta localmente o directamente lo transere al mejor
candidato considerado por N . Al tratarse de un algoritmo distribuido la responsabilidad de la
asignacion dinamica de procesos no reside en un unico nodo, sino que la tarea esta fsicamente
distribuida entre los nodos por el intercambio de informacion que realizan. Esto provee mayor
conabilidad y tolerancia a fallas.

En un algoritmo de balance de carga pueden identicarse varias polticas a ser desarrolla-
das [6]: de intercambio de informacion de estados, de seleccion del nodo destino (ubicacion), de
transferencia de procesos, de estimacion de carga, de limitacion a la migracion y de determi-
nacion de prioridades en la ejecucion. Como se vera mas adelante, el algoritmo que se presenta
en este trabajo considera fundamentalmente las tres primeras.

Habitualmente se identican dos categoras de algoritmos de balance de carga [1, 7, 11]: los
iniciados por el emisor y los iniciados por el receptor. En los primeros cada nodo al recibir un
proceso, toma la iniciativa de balancear la carga decidiendo si lo ejecuta local o remotamente.
En los iniciados por el receptor o servidor, los nodos poco cargados piden procesos para ser
ejecutados por ellos. El algoritmo aqu presentado cae en la categora de iniciado por el emisor.

El trabajo esta organizado de la siguiente manera. En la seccion siguiente, se describira el
algoritmo propuesto, las polticas mencionadas, y se ilustrara el funcionamiento del algoritmo
en un ejemplo. En la seccion 3 se evaluaran las caractersticas y propiedades del algoritmo
de acuerdo a clasicaciones conocidas. En la seccion 4 se hara una comparacion con otros
algoritmos citados en la literatura. Finalmente se incluyen las conclusiones y el trabajo futuro.

2. Algoritmo propuesto

El algoritmo trabaja sobre un conjunto de nodos que estan conectados entre s y que pueden
tener cualquier topologa de conexion. En forma abstracta, este conjunto de nodos puede verse
como un grafo no dirigido etiquetado G = (V; A), que consta de un conjunto nito de vertices
V que representan los sitios de procesamiento o nodos, y un conjunto A de aristas o arcos que
representan las conexiones entre sitios. Estas conexiones son logicas y son fundamentales para
el intercambio de informacion de estado. En la realidad pueden existir mas conexiones fsicas de
las que se muestran en el grafo, pero para no disminuir la performance del sistema, es deseable
que las conexiones logicas que se establezcan cuenten con una conexion fsica subyacente (ver
gura 1).

nodo

conexin lgica y fsica
conexin fsica

Figura 1: Tipos de conexiones

Cada nodo tiene una etiqueta que representa la informacion sobre su carga actual, que
puede ser calculada, por ejemplo, utilizando el numero de procesos que estan en la cola de
listos. Nuestro algoritmo asume una funcion c(N ) que calcula la carga de un nodo N . El lector
interesado puede encontrar informacion sobre este tipo de funciones en [4, 10].

Cada nodo N mantiene ademas una tabla interna compuesta por tuplas de la forma
< nodo; carga; longitud; destino >. Cada tupla indica el nodo vecino que la genera, la carga
mnima informada por dicho vecino, el nodo destino que posee dicha carga y la longitud del
camino que separa a ambos nodos (ver gura 2).

A

B

9

12

8

E

10
C

5

D

<nodo, carga, longitud, destino>

Tabla interna de B:

<A, 9, 0, A>
<E, 8, 0, E>
<C, 5, 1, D>

Figura 2: Tuplas para el intercambio de datos

Como puede verse en la gura 2, por cada arco que llega al nodo se tiene la mnima carga que
hay en alguno de los nodos alcanzables por esa va. Esta informacion es provista directamente
por un vecino en forma asincronica. Al llegar esta informacion, el nodo puede calcular el mnimo
entre su propia carga y la proveniente de los nodos vecinos. Una vez calculado, propaga este
mnimo a los sitios vecinos, que a su vez haran el mismo procedimiento.

De este modo, la carga de los nodos y la carga mnima se encuentra en actualizacion continua
y asincronica. Cuando un nodo recibe de un vecino un nuevo mnimo, o cuando su carga
cambia, recalcula el mnimo y enva un mensaje a los nodos adyacentes para hacerles conocer
la modicacion. As, la informacion del nodo menos cargado se propagara por el grafo, y cada
nodo conocera como acceder a dicho mnimo (por el nodo que le transmitio la informacion).

Es claro que la propagacion de informacion lleva tiempo. Por lo tanto, la informacion de un
mnimo en un nodo muy distante puede estar desactualizada. Para solucionar este problema,
el algoritmo tiene denido un umbral que establece la distancia maxima a la que se propaga
un mnimo en el grafo. Si el umbral es 0, entonces cada nodo solo conocera su carga actual y
no propagara informacion. Si el umbral es mayor o igual al camino mas largo en el grafo que
representa al sistema, entonces el mnimo se propagara a todos los nodos. Como se mostrara en
el ejemplo de la seccion 2.4, si el umbral es menor al camino mas largo, entonces cada nodo
tendra la informacion del mnimo a una distancia menor o igual al umbral. El valor del umbral
podra adecuarse al sistema en forma manual o automatica.

Cuando se crea un proceso nuevo en el sistema, el nodo que lo orig