Funzionamento background

Il funzionamento background consiste nello svolgere una serie di azioni rivolte al mantenimento di una “fotografia” aggiornata della rete in esame. In particolare, siamo interessati ad ottenere informazioni riguardanti (1) la posizione degli host all’interno rete e (2) il numero e lo stato dei collegamenti.

Per semplificare la nomenclatura, eviteremo di utilizzare espressioni analo- ghe a “porzione unidirezionale di un collegamento bidirezionale”. Impiegheremo piuttosto il termine “collegamento” (o “link”) che, a meno d’indicazioni speci- fiche, dovr`a dunque essere inteso come unidirezionale. Ci`o nonostante, ribadia- mo il fatto che le reti emulate con Mininet possiedono link esclusivamente Full Duplex.

Posizione degli host

Per quanto concerne il primo punto, il componente `e abbonato agli eventi sol- levati dal modulo myARPModule.py (paragrafo 5.2), in particolare HostEvent, per la cui gestione `e stato predisposto il metodo handle HostEvent(). La me- morizzazione delle informazioni raccolte grazie a tale evento viene affidata al

Applicazione di controllo 61

(a) Rete reale (o virtuale), collegamenti Full Duplex 1 2 3 c12 c21 c₂₃ c₃₂ c₃₁ c₁₃ (b) Grafo associato

Figura 5.9: Rappresentazione di una rete reale (o virtuale) tramite un grafo

dizionario hosts, il quale mappa l’indirizzo IP di una workstation nella tupla contenente l’identificativo dello switch cui `e connessa, il numero di porta tramite la quale `e possibile raggiungerla ed il proprio indirizzo MAC. In breve:

s e l f. h o s t s [ h o s t _ i p ] = ( s w i t c h _ i d , s w i t c h _ p o r t , h o s t _ m a c ).

Si noti come detto dizionario differisca dal suo omonimo, descritto nel paragrafo 5.2.

Se myARPModule.py ha scoperto l’host cui l’evento fa riferimento, le informa- zioni corrispondenti vengono inserite nell’apposito dizionario. Ci si preoccupa, inoltre, d’installare una regola permanente nella tabella dello switch che lo ha in carico, la quale imponga d’inoltrare sulla porta appropriata tutto il traffico IP ad esso destinato (indipendentemente dall’indirizzo sorgente). Come risul- ter`a pi`u chiaro nel seguito, detta regola verr`a utilizzata soltanto dai pacchetti generati all’interno della sottorete cui appartiene la workstation. Il traffico pro- veniente dall’esterno, infatti, necessita di un’azione preliminare: la riscrittura degli indirizzi MAC.

Se invece myARPModule.py ha ritenuto che l’host in esame debba essere ri- mosso dall’insieme di quelli conosciuti, si rendono necessarie le azioni duali rispetto a quelle appena descritte. Pi`u precisamente, dovr`a avvenire la can- cellazione sia delle informazioni corrispondenti, memorizzate in host, sia della regola presente nella tabella dello switch cui la workstation era connessa.

Numero e stato dei collegamenti

Il secondo punto del funzionamento background si articola in due fasi: • ricostruzione della topologia;

• stima dell’utilizzazione relativa a ciascun collegamento e conseguente as- segnazione di un costo.

Esse sono necessarie al fine di popolare e mantenere aggiornato un database che rappresenti la struttura del grafo associato alla rete in esame, in accordo con quanto illustrato in precedenza. Ogni modifica apportata a detto database, sia essa l’aggiunta/rimozione di un arco o la modifica di un costo, innesca l’esecu- zione dell’algoritmo di Dijkstra. L’idea `e quella di avere sempre a disposizione un insieme di alberi dei cammini minimi aggiornati (uno per ogni nodo del gra- fo) dal quale attingere le conoscenze necessarie per l’installazione di un nuovo percorso.

Il database di cui sopra viene implementato dal dizionario topology, il quale contiene le strutture dati relative agli archi del grafo associati ai collegamenti realmente presenti nell’infrastruttura. Ogni arco viene rappresentato tramite la corrispondenza tra una coppia (tupla) di nodi, relativi a due switch OpenFlow della rete, ed una lista. Rispettando l’orientazione dell’arco, la coppia `e da considerarsi ordinata. Ci`o significa che il primo elemento costituisce il nodo associato allo switch trasmittente sul collegamento, mentre il secondo costituisce il nodo associato allo switch ricevente. La lista, nella quale si mappa la coppia di nodi, contiene nell’ordine:

1. il numero di porta relativo allo switch trasmittente; 2. il numero di porta relativo allo switch ricevente;

3. il costo associato all’arco rappresentante il collegamento (costo del colle- gamento);

4. la stima dell’utilizzazione di tale collegamento. Riassumendo:

s e l f. t o p o l o g y [( s w i t c h T x _ i d , s w i t c h R x _ i d )] = [ s w i t c h T x _ p o r t , s w i t c h R x _ p o r t , l i n k _ c o s t , l i n k _ u t i l ].

Ricordiamo che, in generale, i costi associati alle due porzioni Simplex nelle quali `e possibile scomporre un collegamento Full Duplex saranno diversi.

L’insieme dei cammini minimi `e, a sua volta, realizzato tramite un dizionario – cheapestPaths – che mappa un nodo del grafo in un ulteriore dizionario, il quale costituisce una corrispondenza tra una possibile destinazione e la tupla contenente:

1. il predecessore nell’albero dei cammini minimi avente come radice il nodo di partenza;

Applicazione di controllo 63

3. il numero di porta relativo allo switch associato alla destinazione. Radici, destinazioni e predecessori sono tutti rappresentati tramite gli identifi- cativi degli switch corrispondenti. Riassumendo:

s e l f. c h e a p e s t P a t h s [ s w i t c h R a d i x _ i d ][ s w i t c h D e s t _ i d ] = ( s w i t c h P r e v _ i d , s w i t c h P r e v _ p o r t , s w i t c h D e s t _ p o r t ).

Ricostruzione della topologia La fase di ricostruzione topologica si svolge in corrispondenza del lancio dell’applicazione. Una volta raggiunta una situa- zione di apparente stabilit`a, essa esaurisce la sua funzione e viene perci`o termi- nata. Ulteriori modifiche allo stato dell’infrastruttura (dovute, ad esempio, a dei malfunzionamenti) verranno gestite tramite modalit`a alternative, descritte nel seguito dell’elaborato.

La classe RoutingHandler possiede due contatori: uno relativo al numero di switch presenti nella rete, numSwitches; l’altro ai collegamenti tra di essi, numLinks. Le modalit`a di aggiornamento di numSwitches sono identiche a quelle gi`a descritte per il suo analogo, presente in myStatsModule.py (paragrafo 5.3).

Il componente `e abbonato agli eventi sollevati dal modulo discovery.py (paragrafo 5.1), in particolare LinkEvent, per la cui gestione `e stato predisposto il metodo handle LinkEvent(). Finch´e il numero di link rivelati `e ritenuto “instabile”, alla ricezione di un tale evento seguiranno alcune azioni. Come detto poc’anzi, dal momento in cui il contatore numLinks raggiunge un’apparente condizione di stabilit`a, gli eventi sollevati da discovery.py saranno ignorati.

Se l’evento possiede il flag added settato, la struttura dati corrispondente al link in esame viene inserita all’interno del database topology. In particolare, al collegamento verranno assegnati costo unitario ed utilizzazione nulla. Fanno eccezione alcuni link, specificabili da linea di comando, cui `e riservato un costo “esageratamente” elevato. Il ruolo ricoperto da questi ultimi verr`a trattato nelle pagine seguenti.

Inoltre, nella tabella dei due switch che costituiscono i capi del collegamento notificato viene installata una regola OpenFlow, pensata appositamente per lo scarto di tutti i pacchetti ARP ricevuti sulla porta appropriata. Come detto nel paragrafo 5.2, infatti, esiste la possibilit`a che tali pacchetti vengano inoltrati tramite flooding. Se non si eliminassero tutti i messaggi ARP ricevuti da altri switch, una pratica di questo tipo renderebbe inutilizzabile l’infrastruttura.

Il contatore numLinks viene quindi incrementato ed il numero dei collega- menti dichiarato “instabile”. Trascorso un certo intervallo di tempo, esso viene esaminato nuovamente: se il suo valore non ha subito ulteriori modifiche, il nu- mero di link viene assunto “stabile” e pari al contatore stesso; in caso contrario, la condizione d’instabilit`a si protrae fino alla prossima verifica.

La procedura termina con l’esecuzione dell’algoritmo di Dijkstra.

Coinvolgendo esclusivamente la fase iniziale del funzionamento dell’appli- cazione, `e verosimile supporre che i link segnalati da discovery.py dovranno essere solamente aggiunti al database topologico. Ad ogni modo, il metodo

handle LinkEvent() prevede anche la possibilit`a che il relativo evento pos- sieda il flag removed settato. In tal caso, si procede alla rimozione del link dall’apposito dizionario e delle reletive regole per lo scarto dei pacchetti ARP dalle tabelle degli switch interessati.

Il contatore numLinks viene quindi decrementato ed il numero dei collega- menti dichiarato “instabile”. Segue la consueta procedura per verificarne la stabilit`a.

Come ultima azione, il metodo invoca l’esecuzione dell’algoritmo di Dijkstra.

Stima dell’utilizzazione ed assegnazione dei costi Diversamente da quan- to accade per la ricostruzione topologica, la stima dell’utilizzazione relativa ai collegamenti, assieme all’aggiornamento dei costi corrispondenti, avviene rego- larmente durante tutto il funzionamento dell’applicazione. La cadenza con la quale si effettuano tali stime ed aggiornamenti `e dettata dal passo d’interroga- zione per la raccolta di statistiche dagli switch della rete.

Il modulo `e abbonato agli eventi sollevati da myStatsModule.py (paragra- fo 5.3), in particolare NewPortStats, per la cui gestione `e stato predisposto il metodo handle NewPortStats(). Tale evento riporta la stima del carico osservato su ciascuna porta di ogni switch connesso al controller, sia in tra- smissione che in ricezione. La memorizzazione dei dati viene affidata al dizio- nario portStats, la cui struttura ricalca esattamente quella di lastPortLoad, illustrata nel paragrafo 5.3.

In seguito alla ricezione di un evento di tipo NewPortStats, viene invocata la procedura modifyLinkCost(). Essa `e responsabile della stima dell’utilizzazione di ciascun collegamento e della (eventuale) modifica dei costi associati gli archi corrispondenti. Se almeno una di dette modifiche `e effettivamente avvenuta, la rappresentazione corrente della rete sotto osservazione non coincide pi`u con quella disponibile al passo precedente. Si rende necessaria, dunque, una nuova esecuzione dell’algoritmo di Dijkstra, al fine di aggiornare gli alberi dei cammi- ni minimi dai quali attingere le informazioni necessarie per l’installazione dei prossimi percorsi.

Metriche Passiamo adesso alla descrizione della strategia adottata per l’assegnazione dei costi a ciascun link della topologia sotto osservazione.

Rifacendoci alla trattazione portata avanti nelle pagine precedenti, l’algorit- mo di Dijkstra determina l’albero dei cammini minimi in un grafo per il quale i costi degli archi siano non negativi. Detto in altri termini, fissato un nodo ap- partenente alla rete in esame, l’algoritmo identifica i cammini di costo minimo che consentono di muoversi da detto nodo verso i rimanenti.

Come gi`a menzionato nel capitolo 1, una pratica comunemente adottata nel mondo delle reti di calcolatori consiste nello stabilire una volta per tutte la bont`a dei percorsi (dei cammini) in corrispondenza dell’avvio dell’infrastruttura. Si osservi come per conseguire un tale obiettivo sia sufficiente mantenere costanti i costi degli archi del grafo. Nel seguito dell’elaborato, tale pratica verr`a indicata come Fixed Cost policy (FC). Ad esempio, applicando l’algoritmo di Dijkstra

Applicazione di controllo 65

ad un grafo nel quale venga assegnato un costo unitario a ciascun arco presente al suo interno faremmo seguire al traffico generato dagli host esclusivamente il percorso pi`u breve verso la propria destinazione. Il costo di un cammino sar`a infatti pari al numero di archi che lo costituiscono, assumendo cos`ı il significato di contatore del numero di salti (hop counter ) che separano sorgente e desti- nazione10_{. Se i costi degli archi risultano fissati, tali saranno anche gli alberi} di costo minimo determinati da esecuzioni successive dell’algoritmo di Dijkstra. Come risultato, i pacchetti che fluiscono tra due sottoreti verranno istradati costantemente sullo stesso percorso. Sempre nel capitolo 1 vengono citati alcu- ni punti a sfavore riguardanti l’adozione di una strategia di questo tipo che ci hanno spinto ad allontanarcene.

Per ottenere la funzionalit`a di LB che ci siamo promessi di attuare, l’idea `

e quella di far variare il costo associato ad un arco del grafo in funzione del- l’utilizzazione che il link corrispondente sta sperimentando. Come linea guida, possiamo affermare che se assegnassimo ad un arco associato ad un link conge- stionato un costo pi`u elevato rispetto a quello riservato ad un arco relativo ad un collegamento attualmente scarico, il primo risulterebbe sfavorito rispetto al secondo nella selezione del cammio di costo minimo all’interno del grafo. Tutto ci`o si tradurrebbe nell’identificazione del percorso meno congestionato in rete, che `e esattamente ci`o che vogliamo.

Formalmente, ammesso di fissare un costo massimo cmax ed uno minimo cmin tali che 0 ≤ cmin < cmax, dobbiamo determinare una funzione (metrica) f : [0, 1] → [cmin, cmax] che associ all’utilizzazione u del link sotto osservazione il costo c = f (u), da assegnare all’arco corrispondente. Per i nostri scopi, `e necessario che f risulti monotona crescente, almeno in senso lato, ovvero

f (u1) ≥ f (u2) ∀ u1, u2∈ [0, 1] : u1> u2. Inoltre, dovr`a essere verificato che f (0) = cmin e f (1) = cmax.

Tra tutte le funzioni che rispettano detti requisiti, abbiamo deciso di focaliz- zarci su tre tipologie di metriche, le quali si differenziano per la “velocit`a” con la quale un certo collegamento viene penalizzato.

In maniera del tutto arbitraria, fissiamo

cmin= 10Y, cmax= 10X con X, Y ∈ N : X > Y.

Una relazione “ragionevole” tra cmax e cmin pu`o essere ricavata imponendo che un percorso costituito da un unico link massimamente congestionato (u = 1) venga sempre sfavorito rispetto al percorso pi`u lungo esistente in rete, qualora tutti i collegamenti che lo compongono risultino inutilizzati (u = 0). Indicando con C il costo di un cammino all’interno del grafo, con L il numero di archi che lo compongono, con ci, i = 1, . . . , L il costo di ciascuno di essi e con ui, i = 1, . . . , L 10<sub>Un risultato analogo pu`o essere raggiunto anche con costi non unitari, purch´e questi restino</sub> costanti da arco ad arco. In un tale scenario, il costo di un cammino risulter`a proporzionale (non pi`u uguale) al numero di archi che lo compongono.

le utilizzazioni dei link corrispondenti, possiamo scrivere C = L X i=1 ci= L X i=1 f (ui) .

Indicando con n il numero degli switch che compongono la rete in esame, possia- mo affermare che L ≤ n − 1. Come abbiamo gi`a osservato, infatti, un qualsiasi albero di copertura relativo ad un grafo connesso11<sub>composto da n nodi contiene</sub> esattamente n − 1 archi. Il criterio di cui sopra pu`o allora essere espresso dalla disequazione cmax> (n − 1) cmin, da cui segue cmax cmin > n − 1 o, secondo le convenzioni adottate,

X > Y + log10(n − 1) . (5.9)

All’interno dell’applicazione implementata, si `e posto X = 3 ed Y = 1. Si osservi che, con una scelta di questo tipo, la (5.9) `e rispettata per un numero n di switch al pi`u pari a 100.

Le tre metriche sopra citate, illustrate in figura 5.10a, possono essere espresse dalle relazioni

f1(u) = 10Y + 10X− 10Y
u, (5.10) f2(u) = 10Y + 10uX− 10uY, (5.11) f3(u) = 10X− 10(1−u)X+ 10(1−u)Y. (5.12) `

E immediato verificare che

fi(0) = 10Y, fi(1) = 10X ∀ i = 1, 2, 3.

Qualitativamente, la (5.10) rappresenta un comportamento “neutrale” o Neutral policy (NE), imposto dalla relazione lineare che sussiste tra le utiliz- zazioni ed i relativi costi. L’andamento concavo della (5.11), invece, si addice maggiormente ad un approccio in “stile consolidation” o Best Fit policy (BF). Prima di penalizzare in maniera significativa l’arco associato ad un link, infatti, si attende che la relativa utilizzazione assuma livelli prossimi ad 1. Infine, la funzione convessa (5.12) costituisce un “load balancing puro” o Worst Fit policy (WF), dal momento che tende ad assegnare costi elevati gi`a per basse utilizza- zioni. Ci`o non significa che le altre due non tentino di bilanciare i carichi dei collegamenti; semplicemente, fanno riferimento a strategie meno “scattanti”.

Per raggiungere una maggiore robustezza, le metriche effettivamente imple- mentate all’interno dell’architettura rappresentano una versione quantizzata, “a

Applicazione di controllo 67 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 100 200 300 400 500 600 700 800 900 1000 Utilizzazione Costo NE BF WF

(a) Andamento teorico

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 100 200 300 400 500 600 700 800 900 1000 Utilizzazione Costo NE BF WF

(b) Andamento “a gradini”

Figura 5.10: Costo associato ad un collegamento in funzione della sua utilizzazione (X = 3, Y = 1)

gradini”, delle (5.10), (5.11) e (5.12), come mostrato in figura 5.10b. Inoltre, l’effetto di eventuali valori “proibiti”, assunti dalla stima dell’utilizzazione, viene contrastato saturando gli andamenti delle metriche proposte, ovvero

(

fi(λ) = fi(0) ∀ λ ≤ 0 fi(µ) = fi(1) ∀ µ ≥ 1

∀ i = 1, 2, 3. (5.13)

La scelta di quale strategia utilizzare (BF, NE o WF) `e affidata all’utente, il quale ha libert`a di specificare, da riga di comando, il valore da assegnare alla stringa policy. Omettere di specificare un valore per tale variabile comporta l’adozione della metrica NE. Fissare invece i valori ’bf’ o ’wf’ significa optare per le policy BF o WF, rispettivamente.

Calcolo delle utilizzazioni Supponiamo che esista un collegamento tra la porta a dello switch sX e la porta b dello switch sY . Il primo dispositivo agisce da trasmettitore, mentre il secondo da ricevitore12.

Idealmente, l’utilizzazione usX→sY di un tale collegamento `e pari a usX→sY =

RsX→sY

B ∈ [0, 1], (5.14)

dove RsX→sY `e la porzione banda occupata (in ‘bit/s’), mentre B `e la velocit`a nominale massima (sempre in ‘bit/s’). Una volta nota l’utilizzazione, il costo associato al link in esame si ottiene grazie alla relazione

csX→sY = f (usX→sY) ,

dove f `e la versione quantizzata e saturata di una tra le (5.10), (5.11) e (5.12). Relativamente al numeratore della (5.14), possediamo due quantit`a teori- camente coincidenti13_{: la stima ˆR}a

tx del carico in trasmissione associato alla porta a e la stima ˆRb

rx del carico in ricezione associato alla porta b. In realt`a, nella maggior parte dei casi, si osserva che ˆRa

tx 6= ˆRbrx. Due sono le possibili motivazioni che portano a detta diversit`a.

1. In condizioni di funzionamento “ordinarie”, le variazioni tra le due quan- tit`a potrebbero essere dovute agli scostamenti (se pur minimi) tra gli istan- ti d’interrogazione relativi agli switch sX ed sY . In questa situazione si ha che ˆRatx≈ ˆRbrx. Per ricondursi ad un singolo valore, potremmo pensare di effettuare un’operazione di media. Agendo in questo modo, si ottiene la stima ˆ usX→sY = ˆ Ra tx+ ˆRbrx 2B . (5.15)

12_{Si ricordi che, in Mininet, i collegamenti sono Full Duplex: sar`a dunque presente anche la} porzione unidirezionale duale, dalla porta b di sY alla porta a di sX.

Applicazione di controllo 69

2. In condizioni di “carico elevato”, pu`o capitare (in Mininet) che ˆRa tx > B. Si ricade in una situazione di questo tipo quando pi`u flussi, la cui banda aggregata supera la velocit`a nominale di un link, combaciano con delle regole che impongano tutte l’inoltro su quest’ultimo. Ci`o nonostante, per il corrispondente valore in ricezione si ha ˆRb

rx ≈ B. In un tale scenario, l’impiego della relazione (5.15) porterebbe a dichiarare l’utilizzazione del collegamento superiore all’unit`a. Volendo evitare incongruenze tra stime e valori teorici, una relazione alternativa alla precedente potrebbe essere

˜ usX→sY = ˆ Rb rx B . (5.16) `

E possibile dimostrare che le stime (5.15) e (5.16) portano all’assegnazione di due costi ˆcsX→sY = f (ˆusX→sY) e ˜csX→sY = f (˜usX→sY) sostanzialmente coincidenti. Per la (5.13), infatti, f (µ) = f (1) , ∀ µ ≥ 1.

Dimostrazione. • ˆRa tx< B ⇒ ˆRbrx≈ ˆRatx: ˆ usX→sY ≈ 2 ˆRb rx 2B = ˜usX→sY ⇒ ˆcsX→sY ≈ ˜csX→sY; • ˆRa tx> B ⇒ ˆRbrx≈ B:      ˆ usX→sY = 1 2 ˆ_Ra tx B + ˆ Rb rx B ! > 1 ˜ usX→sY ≈ 1 ⇒ ˆcsX→sY ≈ ˜csX→sY.

Eventuali scostamenti tra ˆcsX→sY e ˜csX→sY vengono ulteriormente attenuati dall’andamento “a gradini” della metrica f . Si segnala che, nell’applicazione di controllo implementata, si `e scelto di adottare la stima (5.15).

Per determinare il valore assunto dal denominatore della (5.14) esistono, fondamentalmente, tre strade.

La prima consiste nel mettere in campo ulteriori strategie di stima, rivolte in questo caso alla determinazione della velocit`a del collegamento. Esulando dagli obiettivi di questo lavoro di tesi, una soluzione di questo tipo non `e stata presa in considerazione.

La seconda confida nella possibilit`a di ricavare tale valore da un campo pre- sente in una qualche informazione “circolante” in rete. In effetti, `e previsto che la struttura dati descritta in [42], impiegata per la rappresentazione delle porte fisiche appartenenti ad uno switch OpenFlow, contenga al suo interno dei campi – curr, advertised, supported e peer – i quali, tramite una bitmap, dovrebbe- ro indicare i cosidetti link modes: da 10 Mbit/s a 10 Gbit/s Full e Half Duplex.

Tipo di flusso Strategia di recovery

Bronze Restoration (reattiva) – RP calcolato solamente in caso di guasto al WP.

Silver Protection (proattiva) – RP calcolato contestual- mente all’installazione del WP; le regole del RP han- no priorit`a inferiore rispetto a quelle del WP: in caso di guasto, le seconde andranno rimosse.

Gold Protection (proattiva) – RP calcolato contestual- mente all’installazione del WP; le regole del RP hanno la stessa priorit`a di quelle del WP: invio simultaneo del traffico su due percorsi disgiunti. Platinum Protection (proattiva) – RP calcolato contestual-

mente all’installazione del WP; le regole del RP hanno la stessa priorit`a di quelle del WP: invio simultaneo del traffico su due percorsi disgiunti e separazione fisica rispetto al resto dei flussi.

Tabella 5.2: Strategie di TR adottate per le diverse tipologie di flusso

In POX, i campi di cui sopra figurano effettivamente all’interno dell’attributo ofp (paragrafo 4.2), relativo all’evento associato alla connessione di uno switch al controller. Abbiamo per`o osservato come il valore corrispondente all’attribu- to in esame non subisca modifiche, pur facendo variare la banda nominale dei link emulati con Mininet. Avendo scelto di non approfondire le cause di detto comportamento, anche questa strategia `e stata abbandonata.