Visualizza wikitesto di Legup

'''LEGUP'''<ref>{{Cita web|url=https://conferences.sigcomm.org/co-next/2010/CoNEXT_papers/14-Curtis.pdf|titolo=LEGUP: Using Heterogeneity to Reduce the Cost of Data Center Network Upgrades|cognome=|nome=|data=|urlarchivio=|accesso=}}</ref> è un algoritmo sviluppato da [https://scholar.google.com/citations?user=p1fGnF0AAAAJ&hl=en Andrew R. Curtis], [https://scholar.google.it/citations?user=-EMkK7QAAAAJ&hl=it&oi=ao S. Keshav] and [https://scholar.google.com/citations?user=JX5VMAkAAAAJ&hl=en 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.''

[[File:DCNetworkConventional.png|alt=|centro|thumb|upright=1.9|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 <math>p_a </math>, tale che la rete possa instradare effettivamente tutte le matrici appartententi all'insieme delle ''Traffic Matrices'' (<math>D</math>) in <math>p_a\cdot D</math>. Perciò in questo caso, <math>p_a </math> 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 <math>\delta</math>-''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 <math>\delta</math>, allora una rete si dice <math>(p_f, \delta)</math>-flessibile, se ha <math>p_f</math> distinti <math>\delta</math>-''attachment point.''

=== Affidabilità ===
<math>p_r</math> rappresenta il numero di rotture di collegamenti o switch necessarie per ottenere una partizione degli switch ToR. Ad esempio, un grafo completo con <math>n</math>vertici, ha affidabilità pari a <math>n-1</math>, 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 (informatica)|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 <math>S = \{s_1, ..., s_k\}</math>, dove ogni <math>s_i</math>rappresenta uno switch, LEGUP agisce nel seguente modo:

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

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

Successivamente, viene calcolata una stima per difetto di <math>b_f</math>: siano <math>r(ToR)</math>, <math>r(aggr)</math> e <math>r(core)</math> le larghezze di banda degli switch ToR, degli switch di aggregazione e dei nuclei rispettivamente. La stima di <math>b_f</math>, chiamata <math>b_{f}^{min}</math>, sarà pari a: <math display="block">b_{f}^{min} = 1/2r(aggr)-r(ToR) </math>. Ovvero, l'ammontare di larghezza di banda che gli switch di aggregazione e ''core'' possono utilizzare senza decrementare l'agilità. Una volta trovato <math>b_{f}^{min}</math>, viene utilizzato il seguente algoritmo, per massimizzare <math>w_a b_a + w_f b_f</math>:

 '''Algoritmo 1'''

 Input: <math>r(core)</math>, <math>r(aggr)</math>, <math>r(ToR)</math>, <math>b_a^{max}</math>, <math>b_f^{min}</math>
 Output: <math>b_a
   </math>, <math>b_f</math>

 '''''begin'''''

  <math>b_a
   </math> = <math>b_a^{max}</math>;
  <math>b_f</math> = <math>b_f^{min}</math>;
  <math>r(cToR)</math> = 0;
  While <math>w_ab_a + w_bf_b</math> does not increase:

      '''if''' <math>r(cToR) < r(ToR)</math>:

         <math>r(core) = r(core) +1</math>
         <math>r(aggr) = r(aggr) -2</math>
         <math>r(cToR) = r(cToR)+1</math>

      '''else:'''

         <math>r(aggr)=r(aggr)-1</math>
         <math>r(ToR) = r(ToR) +1</math>

      <math>b_f = b_f +1</math>
      <math>b_a = min\Bigg\{1, \frac{r(core)}{r(ToR)}, \frac{1/2 r(aggr)}{r(ToR)}\Bigg\}</math>

 '''''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 <math>w_a b_a + w_f b_f</math> trova un massimo, può portare al massimo globale, dato che la funzione obiettivo è la somma di due funzioni lineari.

==== Affidabilità ====
<math>b_r</math>può essere al massimo uno dei seguenti valori:

* La metà del numero delle porte di ogni <math>s</math> ∈ <math>S</math>
* Il numero di porte aperte di ogni switch ToR switch.

Perciò si può definire <math>b_r</math> 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 <math>T</math> una topologia logica con <math>IO</math> nodi <math>I = \{1,...,k\}</math> , e siano <math>x_1,...,x_l</math> le [[Albero (informatica)|radici]] di <math>T</math>. Sia <math>X_p</math> l'insieme degli <math>IO</math> nodi connessi al nodo radice <math>x_p</math>, tale che <math>X_1 = I</math> e <math>X_1 \supset ... \supset X_l</math>. Quando tutti gli archi di <math>T</math> hanno capacità positiva, si avrà che <math>T</math> instrada effettivamente tutte le ''Traffic Matrices'' con capacità degli archi ottimale, se per ogni <math>x_p</math>, such that <math>2 \leq p \leq l</math>:

<math display="block">r(i) > \sum_{j \in X_{p-1} - X_p} r(j) \ \text{for all} \ i \in X_p</math>

e <math>|X_l - X_{l-1}| \geq 2</math>.
----
'''Teorema 2:'''

Siano <math>T, x_1,...,x_l, X_1,...,X_l</math>, e <math>I</math> definiti come in Teorema 1, e siano <math>X_0 =\O</math>e <math>X_{l+1} =\O</math>. Si avrà che <math>T</math> instrada effettivamente tutte le ''Traffic Matrices'' con capacità degli archi ottimale se e solo se:

<math display="block">
    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}

</math>
per ogni <math>1 \leq p \leq l</math> e ogni <math>i \in I</math>.
----
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 <math>k</math> nuclei avrà <math>k-1</math> nuclei: combinando più switch tra di loro, raggiungendo un totale di <math>l</math> porte in un unico switch con almeno <math>l</math> porte. Per di più, se non dovesse esistere una realizzazione fisica di una topologia con <math>k</math> nuclei, allora sicuramente non esisterà nemmeno la realizzazione fisica per <math>k-1</math> 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 <math>S</math> 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 <math>s \in S</math> con maggiore capacità libera. La procedura viene ripetuta finché metà della capacità di ogni [[switch]] in <math>S</math> è 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 <math>G</math> di un [[Albero (informatica)|albero]] logico <math>T</math> con nodo radice <math>x</math> and <math>IO</math> nodi <math>I</math> con <math>c(i, x)</math> minimizzata secondo Teorema 2, instrada effettivamente tutte le Traffic Matrices. Inoltre, se <math>c(i, x)</math>e <math>m(i)</math> sono rispettivamente divisibili per <math>p(i)</math>e <math>m_{min}</math>per ogni  <math>i \in I</math>, allora l'ammontare della capacità degli archi utilizzata da <math>G</math> 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 <math>T</math> sia realizzabile, siano <math>x_1, ..., x_l</math> le radici di <math>T</math>. Gli switch che soddisfano ogni <math>x_i</math>sono imposti da <math>X_i</math>, gli switch di aggregazione che sono ''children'' degli <math>x_i</math>, e perciò ogni <math>x_i</math> 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 <math>x_i</math>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<ref>{{Cita web|url=http://compalg.inf.elte.hu/~tony/Kutatas/BinPacking/JohnsonGareyUllman-WorstCase-1974-SIAM.pdf|titolo=Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms}}</ref> 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 (informatica)|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 (<math>S</math>), 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 <math>k</math> nearest ToR switches;

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

  Sort each list in increasing order of distance to <math>k</math> ToR switches;

 '''''end'''''

 '''Mapping'''

 Input: data center model <math>M</math> and <math>S</math>
 Output: map <math>S \rightarrow</math> Racks

 '''''begin'''''

 ''Phase I''

 '''For''' each switch <math>x \in S</math>
      '''For''' each aggregation switch <math>y \in M</math>
 	find the closeness of <math>x</math> and <math>y</math>

 <math>S' = \O</math>
 '''For''' <math>y \in M</math>

     Map the closest <math>x \in S</math> to <math>y</math>
     <math>S' = S' \cup \{x\}</math>

 ''Phase II''

 '''For''' each switch <math>x \in S-S'</math>
      Map <math>x</math> to the first rack in <math>r \in R[x.U]</math>
      Update <math>r</math>’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 <math>S</math>. ''La similarità'' tra due switch <math>s_1</math> and <math>s_2</math> viene definita come <math>closeness(s1, s2)</math>, ed è uguale a 0 se <math>s_1</math>non possiede tante porte quante quelle di  <math>s_2</math> per qualsiasi velocità, dove le porte possono operare a qualsiasi velocità inferiore rispetto alla loro ''line speed''. Vale 1 se <math>s_1</math> ha almeno tante porte quanto <math>s_2</math> per ogni velocità, e di nuovo le porte di <math>s_1</math>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 <math>i</math> con capacità <math>r(i)</math>, deve avere almeno <math>r(i)</math> di larghezza di banda per instradare effettivamente tutte le ''Traffic Matrices''. In particolare, se <math>u</math>è la somma delle larghezze di banda di tutte le porte di <math>i</math>, l'agilità della rete sarà al massimo pari a <math>u/r(i)</math>. 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 <math>\delta</math>.

==== Ricerca del valore massimo per ogni metrica ====
Per comparare le metriche di performance, queste possono essere riscalate nell'intervallo <math>[0,1]</math>, 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.

== Note ==
<references />

== Voci correlate ==
* [[Data center|Data Center]]
* [[Rete di Clos]]
* [[Topologia di rete]]
* [[Branch and bound|Branch and Bound]]

{{Portale|informatica|telematica}}

[[Categoria:Algoritmi di rete]]