Implementazione dell'algoritmo

Alla accensione del controller vengono chiamate le funzioni di configurazione e di inizializzazione del sistema: install() e configure(). In install sono presenti due timer: uno riguarda il tempo da far passare per procedere alla creazione dei file che serviranno a raccogliere i dati ricevuti dalle varie porte; l'altro individua il tempo che deve passare affinchè il controller richieda allo switch le statistiche per la prima volta. Questo tempo è settabile dall'amministratore modificando nel file balancer.h l'oggetto const int FIRST_TIME_STATS.

Queste operazioni vengono effettuate attraverso due funzioni chiamate allo scadere di questi timer: new_file_stats() e ask_flows_stats().

post(boost::bind(&Prova::ask_flows_stats,this),FIRST_TIME_STATS )

Mentre new_file_stats() non verrà più usata, ask_flow_stats() sarà il primo scalino su cui ruoterà tutto l'algoritmo e verrà analizzata in seguito.

In questa fase vengono inizializzate tutte le variabili che serviranno nell'algoritmo.

Il primo step è il setup della connessione tra controller e switch nella quale la tabella di flusso viene resettata cancellando ogni flusso precedentemente attivo. Il NOX è event driven, quindi è necessario attendere l'arrivo del primo pacchetto, che sicuramente non avrà un match postivo nella tabella di flusso, per originare la catena di eventi che porterà il balancer a lavorare a regime.

Per ogni pacchetto non matchato ed inviato al controller, e quindi anche per il primo, viene chiamato l'handler “Packet_in”.

Questa funzione, semplicemente prende i valori dei campi del pacchetto appena arrivato e prepara un mesaggio Flow_mod da inviare allo switch per aggiungere la nuova entry in tabella.

L'azione corrispondente per ogni nuovo flusso sarà inviare tutti i pacchetti matchati verso una porta. Ma quale porta in particolare?

L'idea più semplice da considerare è quella di considerare un round- robin tra le varie porte cioè ruotare ciclicamente la porta di uscita in maniera brutale ogni volta che si vuole installare un nuovo flusso. Non avendo fatto alcuna assunzione sul traffico in arrivo, non ci è dato sapere se un dato flusso sarà composto da pochi o molti pacchetti ovvero non possiamo sapere quanto andrà ad incidere sul carico di ogni singola porta.

Questa strategia è quindi utilizzata all'avvio quando si cerca di ridistribuire un numero equo di flussi su ogni porta senza avere alcuna informazione su di essi.

In seguito, con a disposizione le statistiche di ogni porta, la stategia di selezione della porta portà essere più raffinata.

La scelta della porta è effettuata dalla funzione round() che viene chiamata ogni volta che l'handler deve scegliere la porta per il nuovo flusso.

Nel caso di round-robin, l'algoritmo è realizzato con una variabile static di tipo intero, r_robin_port, che viene incrementata di uno ad ogni chiamata della funzione round(); questa variabile fornisce la porta desiderata tramite la relazione :

r_robin_port mod Number_of_switch_port (2)

che fornisce il resto della divisione tra r_robin_port e Numero_porte_switch. Nel nostro caso, essendo le porte solo 4, può essere scritto come AND bit a bit tra r_robin_port e la maschera 11 (3 in binario):

(r_robin_port && 3) (3)

Questo sistema procede fino allo scadere del timer per la richiesta delle statistiche, al quel punto viene chiamata la funzione ask_flow_stats().

Questa funzione, prepara una serie di messaggi Aggregate_stats_request (uno per porta), nei quali vengono richieste allo switch le statistiche riguardanti il numero di flussi attivi, i pacchetti matchati inviati da quella porta e il numero di byte totali processati. Per ogni messaggio inviato, viene creato un numero che rappresenta un identificativo unico della richiesta. Le risposte a tale richiesta dovranno contenere al loro interno questo identificativo chiamato xid che permetterà la corretta associazione tra richiesta e risposta.

l'identificativo del messaggio inviato e come valore il numero della porta a cui la richiesta di statistiche è riferita. Questo consentirà poi di effettuare il giusto accoppiamento tra la risposta ricevuta e la porta a cui tale risposta è associata.

L'ultimo passo di questa funzione è il settaggio di un timer che allo scadere chiami nuovamente la funzione stessa. Questo timer è regolabile dall'utente ed è di particolare importanza perchè indica ogni quanto il sistema valuta il bilanciamento dei carichi sulle porte e di conseguenza la strategia da adottare.

Per modificare questo timer è necessario modificare nel file header la costante STATS_INTERVAL.

Le risposte generate dallo switch vengono raccolte da un handler chiamato handle_aggregate e specializzato per la gestione di un evento “ Aggegate_stats_in”.

All'arrivo dei messaggi, il controller scorre la mappa alla ricerca dello xid corrispondente: se non lo trova, c'è stato un errore e la mappa viene cancellata; altrimenti viene memorizzato il numero della porta con i dati ricevuti e infine cancellato l'entry nella mappa.

I dati in nostro possesso vengono quindi scritti nel file txt corrispondente alla porta e viene costruita un'altra mappa, chiamata packet_map, con queste caratteristiche: chiave uguale al numero della porta e valore numero di pacchetti inviati.

Se la scrittura va a buon fine, viene aggiornata la variabile sum ovvero la variabile che contiene il numero totale di pacchetti processati da tutte le porte. In caso di scrittura fallita, significa che una chiave uguale a quella che sto cercando di scrivere è già

presente nella mappa e quindi non faccio niente.

A questo punto l'handler controlla se la dimensione della mappa è minore, maggiore o uguale al numero delle porte:

– Maggiore: c'è un ovvio errore quindi considerando la mappa non attendibile questa viene cancellata e ripristinata la variabile sum a zero

– Minore: La mappa delle statistiche non è ancora completa, proseguo

– Uguale: La mappa è completa, si esegue la funzione balance_ok()

La funzione balance_ok () è preposta al controllo del bilanciamento dei pacchetti sulle varie porte e, a seconda dei risultati prodotti, determina la scelta del comportamento da seguire.

In questa funzione agiscono due pair C++ formate da un booleano e da un intero (balance_flag_up e balance_flag_down). Il booleano indica se il bilanciamento è corretto o meno, l'intero il numero della porta da considerare.

Il ragionamento è questo: nel caso ci sia un bilanciamento corretto, si continua con il round robin. Se c'è una porta che ha un carico troppo basso oltre una soglia impostata dall'amministratore (BALANCE_DOWN_BOUND_PERCENTAGE) tutti i nuovi flussi saranno inviati a quella porta. Altrimenti, nel caso che ci siano alcune porte cariche oltre ad una certa soglia percentuale rispetto alle altre, queste vengono escluse dal round-robin che prosegue solo sulle porte più scariche.

Il primo passo, è resettare tutte le flag sul bilanciamento che io pongo di default a true. Alla prima esecuzione avrò il vettore c++ port_vector che in seguito conterrà le porte in grado di accettare

nuovi flussi con un solo elemento contenente un numero di porta non valido (nel nostro caso tale valore è 5).

Se la packet_map è di dimensione pari al numero delle porte, scorro la mappa e guardo se per ogni porta c'è il bilanciamento. Su ogni porta eseguo la funzione packet_load_control() che calcola la percentuale di pacchetti presenti su ogni porta e la confronta con la soglia:

a=100*(packet_map.second/sum) (3)

Se a è < BALANCE_DOWN_BOUND_PERCENTAGE, allora il flag balance_down_flag è impostato a false.

Se DOWN_BOUND_PERCT < a < UP_BOUND_PERCT il numero della porta considerata viene aggiunto in cima al port_vector.

Se a > UP_BOUND_PERCT allora il flag balance_up_flag è impostato a false.

La funzione provvede a scrivere le statistiche (numero flussi attivi, numero pacchetti e carico in percentuale) dentro il file corrispondente a quella porta.

Al termine la funzione perfeziona, insieme alla funzione round(), a seconda dei vari casi la strategia da seguire:

se il balance_down_flag è false ovvero almeno una porta è sotto la soglia minima, viene cercata tramite la funzione template pairSecondCompare() la porta associata al minimo carico e tutti i nuovi flussi vengono indirizzati verso quella porta;

se il balance_down_flag è true cioè nessun flusso è così scarico e il balance_up_flag è false allora viene scorso il port_vector che

contiene tutte le porte sotto la soglia di bilanciamento.

Lo scorrimento del port-vector comporta una serie di operazioni aggiuntive per evitare errori a run-time.

Questo vettore è di dimensione variabile dal momento che il numero delle porte coinvolte può in teoria essere diverso di volta in volta. In più ogni volta che ricevo le statistiche aggiornate, questo vettore è riportato alla condizione iniziale di un solo elemento. L'elemento che resta ha come contenuto il numero di una porta non valida, e viene utilizzato come marca di fine array: ogni volta che scorriamo l'array e troviamo il valore fasullo da assegnare alla nostra porta significa che siamo arrivati alla fine dell'array stesso e che dobbiamo ripartire da capo.

Rimane un altro problema da risolvere, per scorrere il vettore si utilizzano degli iteratori che vengono poi deferenziati al valore da loro puntato. Questi iteratori non possono puntare ad aree di memoria vuote quindi nel momento in cui vengono cancellati gli elementi dall'array è necessario assicurarsi che tali iteratori non puntino agli elementi cancellati.

Per ovviare a questo inconveniente, si estende il port-vector ad un numero di elementi pari a quello del numero delle porte aumentato di uno. A questo punto si esegue lo swap con un vettore ausiliario che ha come ultimo elemento (ed anche unico, la prima volta) il valore della porta non valido. Adesso le informazioni sono sul vettore ausiliario che rimane sempre della stessa dimensione (Numero_porte_switch+1) ed è su quello che si faranno scorrere gli iteratori senza rischiare mai che puntino ad elementi non più

presenti. Il port-vector originario, privo di qualsiasi informazione utile viene quindi riportato alla condizione iniziale di singolo elemento. Nel caso invece di entrambi i flag posti a true, siamo nelle condizioni iniziali di buon bilanciamento e proseguo con il round-robin.

Le attività sono divise in due funzioni distinte con l'obbiettivo di far eseguire il minor numero di operazioni possibili:

in balance_ok() c'è la valutazione dei carichi e la preparazione delle strutture necessarie al funzionamento dell'algoritmo che viene effettuata una sola volta alla ricezione delle statistiche; in round() che invece viene chiamata ogni volta che arriva un pacchetto al controller (quindi molto più spesso), si utilizzano i risultati ottenuti da balance_ok() per determinare solamente la porta di uscita eseguendo il minimo numero di operazioni possibili.

A questo punto il processo è completo, infatti ogni volta che vengono richieste le statistiche, il controller è grado di calcolare il peso relativo a ciascuna porta e di indirizzare ogni nuovo pacchetto in arrivo verso la giusta destinazione.