Legup

LEGUP^[1] è 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.

Architecture of a Data Center

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 $p_{a}$ , tale che la rete possa instradare effettivamente tutte le matrici appartententi all'insieme delle Traffic Matrices ( $D$ ) in $p_{a}\cdot D$ . Perciò in questo caso, $p_{a}$ 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 $\delta$ -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 $\delta$ , allora una rete si dice $(p_{f},\delta )$ -flessibile, se ha $p_{f}$ distinti $\delta$ -attachment point.

Affidabilità

$p_{r}$ rappresenta il numero di rotture di collegamenti o switch necessarie per ottenere una partizione degli switch ToR. Ad esempio, un grafo completo con $n$ vertici, ha affidabilità pari a $n-1$ , 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 $S=\{s_{1},...,s_{k}\}$ , dove ogni $s_{i}$ rappresenta uno switch, LEGUP agisce nel seguente modo:

Definisce un tetto massimo per il valore della funzione obiettivo di $S$ .
Se quest'ultimo è minore di quello della migliore soluzione completa trovata fino a quel momento, il nodo che rappresenta $S$ nel solution tree viene potato. Altrimenti ne viene valutata la fattibilità, controllando che vengano rispettati i vincoli.
Se $S$ è determinato come irrealizzabile, viene potato. Altrimenti viene calcolata la performance di $S$ , viene aggiornata la migliore soluzione, e $S$ viene ramificato.

Siano $w_{a}$ , $w_{f}$ , e $w_{r}$ i pesi delle metriche delle performance (rispettivamente agilità, flessibilità e affidabilità), la performance generale di una soluzione $S$ sarà $p(S)$ = $b_{a}w_{a}$ + $b_{f}w_{f}$ + $b_{r}w_{r}$ dove $b_{a}$ , $b_{f}$ , and $b_{r}$ 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à ( $b_{a}^{max}$ ) aggiungendo continuamente switch con il massimo rapporto (somma delle velocità delle porte)/costo, fino a che il costo di $S$ supera il budget.

Successivamente, viene calcolata una stima per difetto di $b_{f}$ : siano $r(ToR)$ , $r(aggr)$ e $r(core)$ le larghezze di banda degli switch ToR, degli switch di aggregazione e dei nuclei rispettivamente. La stima di $b_{f}$ , chiamata $b_{f}^{min}$ , sarà pari a:

b_{f}^{min}=1/2r(aggr)-r(ToR)

. Ovvero, l'ammontare di larghezza di banda che gli switch di aggregazione e core possono utilizzare senza decrementare l'agilità. Una volta trovato

b_{f}^{min}

, viene utilizzato il seguente algoritmo, per massimizzare

w_{a}b_{a}+w_{f}b_{f}

:

Algoritmo 1

Input:  $r(core)$ ,  $r(aggr)$ ,  $r(ToR)$ ,  $b_{a}^{max}$ ,  $b_{f}^{min}$ 
Output:  $b_{a}$ ,  $b_{f}$

begin

  $b_{a}$  =  $b_{a}^{max}$ ;
  $b_{f}$  =  $b_{f}^{min}$ ;
  $r(cToR)$  = 0;
 While  $w_{a}b_{a}+w_{b}f_{b}$  does not increase:

     if  $r(cToR)<r(ToR)$ :

         $r(core)=r(core)+1$ 
         $r(aggr)=r(aggr)-2$ 
         $r(cToR)=r(cToR)+1$

     else:

         $r(aggr)=r(aggr)-1$ 
         $r(ToR)=r(ToR)+1$

      $b_{f}=b_{f}+1$ 
      $b_{a}=min{\Bigg \{}1,{\frac {r(core)}{r(ToR)}},{\frac {1/2r(aggr)}{r(ToR)}}{\Bigg \}}$

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 $w_{a}b_{a}+w_{f}b_{f}$ trova un massimo, può portare al massimo globale, dato che la funzione obiettivo è la somma di due funzioni lineari.

Affidabilità

$b_{r}$ può essere al massimo uno dei seguenti valori:

La metà del numero delle porte di ogni $s$ ∈ $S$
Il numero di porte aperte di ogni switch ToR switch.

Perciò si può definire $b_{r}$ 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 $T$ una topologia logica con $IO$ nodi $I=\{1,...,k\}$ , e siano $x_{1},...,x_{l}$ le radici di $T$ . Sia $X_{p}$ l'insieme degli $IO$ nodi connessi al nodo radice $x_{p}$ , tale che $X_{1}=I$ e $X_{1}\supset ...\supset X_{l}$ . Quando tutti gli archi di $T$ hanno capacità positiva, si avrà che $T$ instrada effettivamente tutte le Traffic Matrices con capacità degli archi ottimale, se per ogni $x_{p}$ , such that $2\leq p\leq l$ :

r(i)>\sum _{j\in X_{p-1}-X_{p}}r(j)\ {\text{for all}}\ i\in X_{p}

e $|X_{l}-X_{l-1}|\geq 2$ .

Teorema 2:

Siano $T,x_{1},...,x_{l},X_{1},...,X_{l}$ , e $I$ definiti come in Teorema 1, e siano $X_{0}=\emptyset$ e $X_{l+1}=\emptyset$ . Si avrà che $T$ instrada effettivamente tutte le Traffic Matrices con capacità degli archi ottimale se e solo se:

c(i,x_{p})={\begin{cases}\sum _{j\in X_{p}-X_{p+1}}r(j),&{\text{if }}i\in X_{p+1}\\r(j)-\sum _{j\in I-X_{p}}r(j),&{\text{otherwise}}\end{cases}}

per ogni

1\leq p\leq l

e ogni

i\in I

.

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 $k$ nuclei avrà $k-1$ nuclei: combinando più switch tra di loro, raggiungendo un totale di $l$ porte in un unico switch con almeno $l$ porte. Per di più, se non dovesse esistere una realizzazione fisica di una topologia con $k$ nuclei, allora sicuramente non esisterà nemmeno la realizzazione fisica per $k-1$ 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

Una volta selezionata una topologia logica, il passo successivo prevede la realizzazione di ogni nodo logico. Per prima cosa bisogna determinare quali porte ogni switch di aggregazione dovrebbe usare per connettersi agli switch ToR e quali porte usare per connettersi con gli altri switch core. Come detto in precedenza, metà della larghezza di banda per ogni switch dovrebbe puntare in ogni direzione. Le porte non connesse degli switch di aggregazione, possono essere trovate iterando sui switch ToR. Per ogni switch ToR, una delle sue porte libere viene selezionata e usata come collegamento, selezionando la porta libera con più alta velocità in modo tale che ci sia uno switch in $S$ con una porta aperta con una velocità maggiore o uguale. Quando esistono più di uno switch di questo tipo, lo switch ToR viene connesso allo switch $s\in S$ con maggiore capacità libera. La procedura viene ripetuta finché metà della capacità di ogni switch in $S$ è stata assegnata a uno switch ToR, o finché il tasso di collegamento di ogni switch ToR non sia uguale al livello di traffico.

Teorema 3:

Una realizzazione fisica $G$ di un albero logico $T$ con nodo radice $x$ and $IO$ nodi $I$ con $c(i,x)$ minimizzata secondo Teorema 2, instrada effettivamente tutte le Traffic Matrices. Inoltre, se $c(i,x)$ e $m(i)$ sono rispettivamente divisibili per $p(i)$ e $m_{min}$ per ogni $i\in I$ , allora l'ammontare della capacità degli archi utilizzata da $G$ coincide con il minimo di ogni interconnection network che può effettivamente instradare tutte le Traffic Matrices.

Con questo teorema è possibile calcolare il numero di nuclei e la velocità delle porte per ognuno di essi. Pertanto, una soluzione deve essere considerata non realizzabile, se e solo se, per ogni nodo, non c’è uno switch con porte sufficienti a soddisfare la richiesta.

Assumendo che la realizzazione della topologia $T$ sia realizzabile, siano $x_{1},...,x_{l}$ le radici di $T$ . Gli switch che soddisfano ogni $x_{i}$ sono imposti da $X_{i}$ , gli switch di aggregazione che sono children degli $x_{i}$ , e perciò ogni $x_{i}$ viene realizzato con lo switch dal costo minimo, che contemporaneamente soddisfa i requisiti di porta che ha. Questa assegnazione può essere ottenuta confrontando la richiesta di ogni $x_{i}$ con il tipo di switch disponibile.

Una buona soluzione per diminuire il costo dei nuclei è quella di impilare nello stesso switch fisico, più switch. LEGUP per compiere questo step, utilizza un'euristica descritto in un recente articolo^[2] di Johnson et al.. Nonostante la bontà di questa euristica, questa operazione potrebbe portare a due diversi scenari problematici: una soluzione dapprima realizzabile potrebbe trasformarsi in non realizzabile, violando, per esempio, dei vincoli fisici. Secondo, accumulare switch core potrebbe diminuire l’affidabilità descritta in precedenza. Dunque, il risultato dell’euristica verrà salvato se e solo se questi due scenari non accadono; in caso contrario, verrà utilizzato l’originale insieme di switch core.

Mappatura degli switch di aggregazione ai rack e agli switch ToR

Una volta ottenuto il set dei nuclei, LEGUP continua posizionandoli in rack e connettendo ogni switch ToR a uno switch di aggregazione. A questo punto, viene assunto che i nuclei siano centralmente localizzati, e che gli switch ToR sono stati posizionati, in modo da ridurre il problema alla sola mappatura degli switch di aggregazione.

L'algoritmo che usa LEGUP per questa fase, prende in input un insieme di switch di aggregazione ( $S$ ), e un modello di data center. L'obiettivo di questa parte del LEGUP, è quello di minimizzare i costi del layout fisico degli switch di aggregazione, sotto i vincoli fisici del modello del data center.

L'algoritmo che performa la mappatura è il seguente:

Algoritmo 2

Preprocessing

Input: data center model
Output: lists of racks

begin

For each rack

 find the sizes of its contiguous free rack units,
 and the distance to the  $k$  nearest ToR switches;

 Separate the racks into lists  $R[u]$  such that the largest
   contiguous free rack units of racks in  $R[u]$  is  $u$ ;

 Sort each list in increasing order of distance to  $k$  ToR switches;

end

Mapping

Input: data center model  $M$  and  $S$ 
Output: map  $S\rightarrow$  Racks

begin

Phase I

For each switch  $x\in S$ 
     For each aggregation switch  $y\in M$ 
	find the closeness of  $x$  and  $y$

 $S'=\emptyset$ 
For  $y\in M$

    Map the closest  $x\in S$  to  $y$ 
     $S'=S'\cup \{x\}$

Phase II

For each switch  $x\in S-S'$ 
     Map  $x$  to the first rack in  $r\in R[x.U]$ 
     Update  $r$ ’s largest contiguous rack units, and move it to the appropriate list

end

In Phase I l'algoritmo prova a sostituire gli switch di aggregazione esistenti nel data center model con uno switch simile in $S$ . La similarità tra due switch $s_{1}$ and $s_{2}$ viene definita come $closeness(s1,s2)$ , ed è uguale a 0 se $s_{1}$ non possiede tante porte quante quelle di $s_{2}$ per qualsiasi velocità, dove le porte possono operare a qualsiasi velocità inferiore rispetto alla loro line speed. Vale 1 se $s_{1}$ ha almeno tante porte quanto $s_{2}$ per ogni velocità, e di nuovo le porte di $s_{1}$ possono operare a una velocità minore rispetto alla loro massima. Phase II ftrova la migliore collocazione per gli switch di aggregazione non posizionati nella prima fase.

Calcolo della performance di una soluzione

Dal momento che la rete è stata costruita secondo il Teorema 2, un nodo $i$ con capacità $r(i)$ , deve avere almeno $r(i)$ di larghezza di banda per instradare effettivamente tutte le Traffic Matrices. In particolare, se $u$ è la somma delle larghezze di banda di tutte le porte di $i$ , l'agilità della rete sarà al massimo pari a $u/r(i)$ . Perciò, possiamo determinare l'agilità della rete, determinando la massima agilità che ogni switch ToR e di aggregazione può avere.

Dall'altra parte, l'affidabilità può essere determinata usando un algoritmo min-cut. In questo caso, il numero di uplink da uno switch ToR al suo switch di aggregazione, e da uno switch di aggregazione al suo switch core, delimita un'affidabilità di una rete di Clos eterogenea, e l'algoritmo può essere calcolato più facilmente.

La flessibilità dipende strettamente dalle regole specificate per aggiungere nuove periferiche alla rete. Nell'implementazione sopra descritta, i device sono stati aggiunti continuamente alla porta disponibile dove l'agilità fosse ridotta meno possibile. La flessibilità è calcolata ripetendo questo processo fino a quando non è più possibile aggiungere dispositivi con larghezza di banda unitaria, senza che essi riducano l'agilità sotto il livello $\delta$ .

Ricerca del valore massimo per ogni metrica

Per comparare le metriche di performance, queste possono essere riscalate nell'intervallo $[0,1]$ , dividendole per il massimo valore che possono raggiungere. Per l'agilità il massimo valore sarà sempre pari a 1, mentre per la flessibilità e per l'affidabilità, possono essere calcolati usando la funzione di delimitazione di questi valori sopra descritta, sul nodo radice che è vuoto.