Verificarea topologiei

După ce liderul a fost ales și topologia a fost distribuită către toate nodurile, este util ca informația să fie validată. Validarea poate implica procese foarte complexe, însă pentru acest laborator vom folosi o validare bazată pe numărul de noduri prezente în cluster.

Calcularea numărului de noduri se poate realiza folosind un algoritm de tipul epidemic.

Calcularea numărului de noduri folosind algoritm epidemic

Funcționalitatea unui algoritm de tipul epidemic se aseamănă cu răspândirea unei boli în care există un pacient 0:

1. "pacientul 0" transmite informația vecinilor săi
2. vecinii pacientului 0 devin "infectați" și transmit și ei, mai departe, informația către vecinii lor

Pentru calcularea numărului de noduri, pacientul 0 va fi nodul lider. Acesta va deține o valoare de început, egală cu 1. Toate celelalte noduri dețin valoarea 0. Nodul lider va realiza media aritmetică dintre valoarea sa și valoarea vecinilor săi. Informația va fi sincronizată în ambele părți. Celelalte noduri vor executa aceeași operație cu vecinii lor.

Algoritmul se repetă până când se atinge convergența soluției. La final, toate nodurile vor deține o aceeași valoare subunitară. Împărțirea lui 1 la această valoare va rezulta în numărul de noduri al clusterului.

Pseudocod:

val = 0
if (rank == leader)
    val = 1
else
    val = 0

for (pas = 0; pas < convergență; pas++) {
    for (i = 0 to nr_vecini) {
        trimite val către procesul vecin[i]
	primește recv_val de la vecin[i]
	val = (val + recv_val) / 2;
    }
}

return (1 / val); // numărul de noduri din rețea

sugestie

Un exemplu de rulare a acestui algoritm poate fi observat aici.

Construirea matricei de topologie folosind algoritmul arbore

Algoritmul arbore reprezintă un algoritm undă, folosit pentru topologii de tip arbore sau pentru o topologie de tip graf pentru care avem un arbore de acoperire, unde avem ca noduri inițiatori nodurile de tip frunză din topologie. În cadrul acestui algoritm, nodurile transmit mesaje părinților lor, acestea fiind transmise mai departe prin aceeași cale până la rădăcina topologiei (rădăcina arborelui), care la final va lua o decizie ce va fi distribuită în toată rețeaua de noduri.

Putem să construim matricea întregii topologii folosind algoritmul arbore, mai precis aplicând acest algoritm pe arborele de acoperire al rețelei graf de noduri. La început, fiecare nod are matricea sa de topologie, unde, inițial, vor apărea doar vecinii nodului respectiv.

Pașii sunt următorii:

• fiecare nod, cu excepția liderului, care este nodul rădăcină în cadrul arborelui de acoperire, va trimite topologia sa către nodul părinte, care va completa topologia sa cu topologiile primite de la nodurile copil.
• liderul va avea topologia completă a rețelei de noduri și o va răspândi în întreaga rețea de noduri. Mai precis, fiecare nod, care nu este frunză, va trimite topologia completată către nodurile copil.

Pseudocod:

// se primesc informații de la toți copiii nodului curent și se actualizează matricea de topologie
for (i = 0 to nr_proc) {
    // pentru copiii nodului curent
    if (rank == parents[i]) {
        for (j = 0 to nr_proc) {
	    // se primește, linie cu linie, topologia locală nodului i
	    se primeste recvTop[j] de la nodul i
	    for (k = 0 to nr_proc) {
	        if (top[j][k] == 0) {
		    // actualizăm matricea de topologie
		    top[j][k] = recvTop[j][k];
                }
            }
        }
    }
}

// nodul curent trimite matricea de topologie proprie către părinte, rând cu rând
for (i = 0 to nr_proc) {
    // dacă nodul curent are părinte
    if (parents[rank] != -1) {
        se trimite top[i] către parents[rank]
    }
}

// dacă nodul curent nu e lider, primește topologia, rând cu rând, de la părinte
if (rank != leader) {
    // nodul lider nu are părinte
    for (i = 0 to nr_proc) {
	se primește top[i] de la parents[rank]
    }
}

// se trimite topologia completă către nodurile-copii, linie cu linie
for (i = 0 to nr_vecini) {
    if (vecin[i] != parents[rank]) {
	for (j = 0 to nr_proc) {
            trimite top[j] către vecin[i]
        }
    }
}

sugestie

Un exemplu de rulare a acestui algoritm poate fi observat aici.