LEGUP è un algoritmo sviluppato da Andrew R. Curtis, S. Keshav and Alejandro Lopez-Ortiz, che crea espansioni di data center già esistenti. Può essere applicato anche su data center con molti vincoli, e opera costruendo un'eterogenea rete di Clos a partire dagli switch esistenti, e sfruttandone di nuovi, sempre considerando vincoli fisici e di costo. Il risultato di questo algoritmo è un data center con maggiore bisection bandwidth allo stesso costo, il quale include anche il costo dei nuovi switch e del ricablaggio della rete.
Per ottenere questo risultato, LEGUP risolve un problema di ottimizzazione, che massimizza le performance della rete, sotto un vincolo di budget e i vincoli fisici del data center.
Perché usare LEGUP? L'architettura base dei data center (DC) utilizzata al giorno d'oggi prevede: gli switch top-of-rack (ToR) connessi al secondo livello degli switch di aggregazione, a loro volta connessi al terzo livello, definito core level. Il core level è a sua volta connesso ad internet tramite dei router perimetrali. Nonostante il largo utilizzo, questa topologia presenta due grandi problematiche: poca affidabilità (i.e. robustezza della topologia nel mantenere la connessione a fronte di rottura di alcuni collegamenti della rete), e insufficiente bisection bandwidth.
LEGUP invece provvede come risultato finale una rete più avanzata rispetto a quella dell'architettura base descritta sopra, e risolve tre principali problematiche ignorate dalle euristiche standard:
Vincoli fisici: le soluzioni proposte devono essere realizzabili fisicamente, e il risultato del LEGUP è sempre una rete realizzabile. Riutilizzo degli switch: LEGUP non aggiunge progressivamente switch con il minimo rapporto bandwith/prezzo, poiché non sempre porta alla configurazione ottimale. LEGUP cerca di riutilizzare gli switch esistenti, controllando sempre se porta a un incremento delle performance della rete. Il costo dei nuovi switch e del ricablaggio della rete è tenuto in considerazione.
Misura della performance di una rete secondo LEGUP
Come sopra accennato, LEGUP massimizza una funzione di performance della rete, la quale è vista come una combinazione lineare pesata dei tre seguenti parametri: agilità, flessibilità, affidabilità.
Agilità Il LEGUP invece di tenere in considerazione la bisection bandwidth, focalizza la propria attenzione sul concetto più generale di agilità della rete. L'agilità di una rete viene definita come la massima costante , tale che la rete possa instradare effettivamente tutte le matrici appartenenti all'insieme delle Traffic Matrices () in . Perciò in questo caso, sarà semplicemente la frazione dei server che possono inviare/ricevere alla loro massima capacità. Una rete senza link sovrapposti, avrà un'agilità uguale a 1.
Flessibilità Definito un -attachment point come una porta inutilizzata tale che l'attacco di un uplink device di 1 unità, non diminuisca l'agilità della rete a meno di , allora una rete si dice -flessibile, se ha distinti -attachment point.
Affidabilità rappresenta il numero di rotture di collegamenti o switch necessarie per ottenere una partizione degli switch ToR. Ad esempio, un grafo completo con vertici, ha affidabilità pari a , dato che per ottenere una completa partizione dei nodi, ogni arco collegante un vertice deve essere rimosso. Al contrario, un albero è il peggior grafo in termini di affidabilità, dato che è sufficiente la rimozione di un solo arco per ottenere una partizione.
La Pipeline Input, Vincoli e Output Come input, LEGUP richiede:
Budget
Il budget è la somma economica a disposizione nel processo di miglioramento della rete e ha la funzione di vincolo nel problema di ottimizzazione.
Lista degli switch e delle line card a disposizione per migliorare la rete
La lista degli switch a disposizione deve contenere i dettagli e i prezzi degli switch acquistabili. I dettagli più rilevanti sono: le porte con relative velocità, line card slot (se è uno switch modulare), il consumo di energia, le unità rack e la potenza termica. Tra i dettagli di una line card, ci sono le sue porte, il prezzo e una lista di switch interoperabili.
Modello del Data Center
Un modello del Data Center è completo se e solo se include tutti i dettagli della rete, con tutte le informazioni sulle racks (disposizione fisica, contenuti, caratteristiche di potenza e termiche). Altre informazioni rilevati sono tutte quelle relative agli switch e dove sono localizzati all'interno della rete. LEGUP in base a queste informazioni troverà, se esiste, una soluzione realizzabile, che rispetta tutti i vincoli e che minimizza il numero e la lunghezza dei cavi.
Come output, LEGUP dà una dettagliata descrizione della rete estesa, compresa la sua topologia e la selezione degli switch e delle line card per ottenerlo. LEGUP da in output anche i rack dove ogni switch di aggregazione va posizionato e un wiring diagram che specifica ogni collegamento tra gli switch ToR e gli switch di aggregazione.
Il problema di ottimizzazione La funzione obiettivo del LEGUP, può anche essere rivista come una combinazione lineare pesata delle tre metriche, dove i pesi sono definiti dell'utente. Per la risoluzione di questo problema, è desiderabile un data center con una struttura ad albero (o simile), in quanto molti problemi simili operano meglio in questo tipo di strutture. LEGUP perciò assume anche che tutti i serve siano già connessi sufficientemente agli switch ToR, ma che i livelli degli switch di aggregazione e il core level debbano essere aggiornati.
Approccio Branch and bound LEGUP esplora lo spazio degli switch di aggregazione, tramite un approccio branch and bound, dato che l'insieme ottimale dei nuclei (core switch) è racchiuso in una sorta di rete di Clos eterogenea. Tramite il branch and bound, LEGUP trova una soluzione enumerando tutti gli elementi nell'insieme delle possibili soluzioni. In particolare trova ed esclude molte porzioni di questo insieme, dove sicuramente non può esserci una soluzione ottimale.
Per localizzare queste porzioni, LEGUP costruisce il cosiddetto "solution tree", un albero dove ogni nodo rappresenta un insieme di switch di aggregazione, il nodo radice è vuoto, e ogni child è costituito dagli switch di aggregazione del parent più quello che rappresenta lui stesso.
Soluzione Completa Quando una soluzione è tale che i propri switch di aggregazione hanno sufficienti porte per connettersi con gli switch ToR, è una soluzione completa. Data una soluzione completa, LEGUP minimizza i costi tramite una mappatura degli switch di aggregazione della soluzione, ai rack della rete, e trova l'insieme minimo dei nuclei da connettere agli switch di aggregazione. Una volta trovata la soluzione completa, l'algoritmo controlla se la soluzione rispetta tutti i vincoli, ed è perciò realizzabile e se rispetta il vincolo di budget.
Il processo di ottimizzazione Data una soluzione completa , dove ogni rappresenta uno switch, LEGUP agisce nel seguente modo:
Definisce un tetto massimo per il valore della funzione obiettivo di . Se quest'ultimo è minore di quello della migliore soluzione completa trovata fino a quel momento, il nodo che rappresenta nel solution tree viene potato. Altrimenti ne viene valutata la fattibilità, controllando che vengano rispettati i vincoli. Se è determinato come irrealizzabile, viene potato. Altrimenti viene calcolata la performance di , viene aggiornata la migliore soluzione, e viene ramificato.
Siano , , e i pesi delle metriche delle performance (rispettivamente agilità, flessibilità e affidabilità), la performance generale di una soluzione sarà = + + dove , , and sono i valori delle metriche normalizzati per il loro massimo valore.
Delimitando il valore della funzione obbiettivo Lo scopo principale della delimitazione del valore della funzione obiettivo, è quello di potare soluzioni non ottimali. Essendo un problema di massimizzazione, il risultato di questo step è una sovrastima dell'effettiva performance di una soluzione. Ogni parametro viene delimitato singolarmente, e dopo vengono combinati i risultati.
Agilità e flessibilità In realtà l'agilità e la flessibilità possono essere delimitate contemporaneamente. In particolare, considerando cosa permette il budget rimanente, LEGUP trova la massima agilità () aggiungendo continuamente switch con il massimo rapporto (somma delle velocità delle porte)/costo, fino a che il costo di supera il budget.
Successivamente, viene calcolata una stima per difetto di : siano , e le larghezze di banda degli switch ToR, degli switch di aggregazione e dei nuclei rispettivamente. La stima di , chiamata , sarà pari a: . Ovvero, l'ammontare di larghezza di banda che gli switch di aggregazione e core possono utilizzare senza decrementare l'agilità. Una volta trovato , viene utilizzato il seguente algoritmo, per massimizzare :
Algoritmo 1
Input: , , , , Output: ,
begin
= 0; While does not increase:
if :
else:
end
Ciò che fa l'algoritmo, è considerare quale posizione tra i nuclei e gli switch di aggregazione decresce la minima agilità, e successivamente massimizza la somma integrando quella posizione con una unità di capacità. Ripetendo questo processo fino a che trova un massimo, può portare al massimo globale, dato che la funzione obiettivo è la somma di due funzioni lineari.
Affidabilità può essere al massimo uno dei seguenti valori:
La metà del numero delle porte di ogni ∈ Il numero di porte aperte di ogni switch ToR switch.
Perciò si può definire come il massimo tra questi due valori.
Ricerca dell'insieme di switch core Per poter trovare l'insieme degli switch core di costo minimo, è necessario dividere questa ricerca in due parti:
trovare una topologia logica ottimale trovare gli switch che la realizzano al minor costo possibile
Selezione di una topologia logica Teorema 1:
Sia una topologia logica con nodi , e siano le radici di . Sia l'insieme degli nodi connessi al nodo radice , tale che e . Quando tutti gli archi di hanno capacità positiva, si avrà che instrada effettivamente tutte le Traffic Matrices con capacità degli archi ottimale, se per ogni , such that :
e .
Teorema 2:
Siano , e definiti come in Teorema 1, e siano e . Si avrà che instrada effettivamente tutte le Traffic Matrices con capacità degli archi ottimale se e solo se:
per ogni e ogni .
Il Teorema 2 permette che un ampio numero di topologie siano connesse ottimalmente ad un insieme di switch di aggregazione. Tuttavia, può accadere che una topologia con nuclei avrà nuclei: combinando più switch tra di loro, raggiungendo un totale di porte in un unico switch con almeno porte. Per di più, se non dovesse esistere una realizzazione fisica di una topologia con nuclei, allora sicuramente non esisterà nemmeno la realizzazione fisica per switch core. Infine, è sempre possibile massimizzare il numero di nuclei secondo il Teorema 1 e impostare la capacità di ogni arco in modo che essi siano minimizzati secondo il Teorema 2.
Realizzazione della topologia logica