C a p i t o l o 4 Risultati originali

C a p i t o l o 4

Risultati originali

4.1 Introduzione

Nel precedente capitolo, abbiamo visto che data una rete di Clos C(n,m,r) in ambiente multirate, il problema di determinare il minimo numero M(n,r) di switch centrali affinché la rete sia riconfigurabile è ancora irrisolto.

Chung e Ross [MRChRo91] hanno ipotizzato che M(n,r) valga al più 2n–1. Nel capitolo 3 sono stati presentati diversi upper bound ad M(n,r) ed alcuni algoritmi di routing per C(n,m,r) riconfigurabili.

In questo capitolo dimostreremo nuovi limiti superiori ad M(n,r) che, per opportuni valori di r ed n, risulteranno essere migliori di tutti gli altri proposti fino ad oggi. Questi risultati, li abbiamo raggiunti grazie ad un nuovo algoritmo di routing per reti di Clos riconfigurabili. Esso è basato su una nostra modifica a Routing_Solid_Connection (RSC), che abbiamo illustrato nel paragrafo 3.4.1. Di seguito ricordiamo l’algoritmo RSC.

Algoritmo Routing_Solid_Connection( T )

1. Su ogni ti,j di T risolviamo il problema del bin packing, con un’euristica E,

rispetto al peso di ciascuna delle connessioni di ti,j. Sia ui,j il numero di bin prodotti.

2. Costruiamo ora la matrice d’interi U ottenuta da T sostituendo ogni elemento ti,j con il valore ui,j determinato al passo precedente.

3. Risolviamo il problema TSA su U. Sia p1M1+...+pqMq la decomposizione della matrice U ottenuta . Costruiamo la decomposizione S prendendo le matrici Mi con la loro molteplicità:

S = ( M1, M1,

...

M1, M2 ,...., M2,

...,

Mq ,...., Mq ) 4. return S.

Grazie a RSC, con il teorema 3.12, si è potuto dimostrare che, per connessioni con peso w∈(0,1], vale la maggiorazione M(n,r) 2n r≤ + .

Nel capitolo 3, avevamo visto che RSC modella il problema di far passare in ogni link quante più connessioni possibili, come una particolare istanza del Bin Packing Problem. Abbiamo anche osservato che, il difetto principale dell’algoritmo, sta proprio nel modo con cui risolve il BPP. La modifica che presenteremo, migliorerà quest’aspetto.

Più precisamente, nel prossimo paragrafo studieremo RSC quando al passo 1, per risolvere il BPP, si utilizza l’euristica First Fit Decreasing. Come vedremo, questo comporterà un primo miglioramento al limite superiore 2n r+ , portandolo a 7 / 4n + . r

Nel paragrafo 4.3, invece presenteremo la seconda modifica ad RSC. Essa servirà a diminuire della metà l’addendo r nell’espressione 2n r+ , ottenendo M(n,r)≤2n+ r/ 2 .

Infine nel paragrafo 4.4., uniremo le due modifiche e dimostreremo che, • nel caso continuo, M(n,r) min{(7/4)n+(1/4)r+ r/ 2 , 2n+ r/ 2 } • nel caso weakly divisible, M(n,r) min{(5/3)n+r, 2n+ r/ 2 } • nel caso strongly divisible, M(n,r) min{(n+r, 2n+ r/ 2 } (gli ultimi due sono sottocasi dell’ambiente discreto ristretto).

Probabilmente però, il risultato più importante che abbiamo raggiunto, è quello di aver verificato che la congettura di Chung e Ross, è in generale troppo “pessimistica”. Infatti, dimostreremo l’esistenza d’infinite reti di Clos riconfigurabili, che hanno un numero di switch centrali inferiori a 2n–1.

4.2 Utilizzo dell’euristica FFD nell’algoritmo RSC.

Chiamiamo Routing_Solid_Connection_FFD (RSC_FFD), l’algoritmo ottenuto da Routing_Soild_Connection in cui al passo 1 si utilizza l’euristica First Fit Decreasing per risolvere il problema di bin packing.

Vogliamo rispondere alla seguente domanda.

Qual’è il minimo numero di switch centrali che RSC_FFD richiede, per essere utilizzato come algoritmo di routing per una rete C(n,m,r) riconfigurabile ?

Sia TF la matrice di traffico relativa ad un generico frame F di Φ (n,r). Indichiamo con |B(ti)| il numero di bin prodotti dall’applicazione dell’euristica E alle r liste di connessioni della riga i di T. Per come è stato definito l’algoritmo RSC_FFD, vale la relazione: 1 ( )i r ( )ij j B t FFD t = = ∀ ti di TF dove,

• tij è la lista di richieste tra lo switch d’ingresso i e quello di uscita j. • FFD t è il numero di bin prodotti da FFD quando applicata a t( )ij ij.

Dalla dimostrazione del teorema 3.12, segue che il numero m di switch centrali necessari a RSC_FFD per determinare una configurazione R compatibile con C(n,m,r) e che realizza F, corrisponde proprio al valore massimo di |B(ti)|.

Il nostro problema è quindi equivalente a quello di determinare,

( , ) ₁

sup | ( ) |i r ( ) con riga di ij i F

F∈Φn r B t = _j= FFD t t T (*)

Nei prossimi paragrafi, sfruttando i risultati noti su FFD, troveremo un limite superiore alla (*) per i casi continuo, discreto ristretto e due sottocasi di quest’ultimo.

C’è però un altro problema da risolvere. Come già anticipato nel paragrafo 3.3, in letteratura i limiti superiori a FFD t , sono forniti in termini di analisi ( )_ij

competitiva. Ad esempio, abbiamo visto che FFD t( )ij ≤ (11/9)|OTT(tij)|+1. A noi

invece serve esprimerli in funzione dei parametri r ed n. Nel prossimo paragrafo risolveremo questo problema.

4.2.1 Analisi euristica First Fit Decreasing

Nel paragrafo 3.3, abbiamo definito l’euristica, first fit decreasing per determinare una soluzione approssimata del BPP. Ricordiamone in breve il funzionamento. Sia l=( x1,..., xn) una lista di elementi ognuno avente un peso w(xi) t.c. 0<w(xi) C. Inizialmente gli elementi vengono ordinati in modo decrescente rispetto al loro peso. Sia x l’elemento corrente che FFD deve inserire in un bin. Se non esiste alcun bin dove x può stare, FFD ne utilizza uno nuovo. Altrimenti, tra tutti i bin aperti capaci di contenere x, l’euristica sceglie il bin di indice minore.

Esprimeremo il limite superiore di |FFD(l)| in funzione del peso della lista l. Più precisamente lo faremo per tre tipi di problemi di bin packing: classico, weakly divisible e strongly divisible. Questo ci consentirà nel paragrafo 4.2.2, di determinare degli upper bound alla (*) in termini di n ed r sia nel caso continuo, che in quello discreto ristretto.

4.2.1.1 Caso BPP classico

Questo è il caso più generale e coincide con la definizione di problema di bin packing che abbiamo dato nel paragrafo 3.3 .

Sia l=( x1,..., xn) una lista di elementi ognuno avente un peso w(xi) t.c. 0<w(xi) 1.

Definiamo una partizione (l–,l+) di l nel modo seguente.

1 ( ) 2 1 ( ) 2 i i i i i i l x x l w x l x x l w x + − = ∈ ∧ > = ∈ ∧ ≤

l+ _{lo chiameremo insieme degli elementi pesanti di l, mentre l}– _{quello degli} elementi leggeri.

In questo paragrafo vediamo una serie di proprietà che ci consentiranno di dimostrare che |FFD(l)|≤ |l+_{|+(3/2)w( l}−_)+1.

Lemma 4.1 [BPJohn76]

Supponiamo che Y ⊆ e che l

ϑ

={ ,..., }B₁ B_t sia una partizione di Y tale che: • ogni Bi∈ è non vuoto ϑ

• x∈B_j 1−w B( )_i per tutti gli interi i e j ,con 1

≤

i<j

≤

t allora, 1 ( ( )) 1 max 0, ( ( )) 1 i t y Y i b B P R y t P R b ∈ = ∈ > − + −

[ ]

{

1

}

è una funzione t.c. : 0,1 dove ,...., è una sequenza di elementi

è una funzione (detta funzione peso) definita

q R R l l x x P → = come segue 6 _<1 1 5 6 3 9 1 _<1 1 5 10 6 3 ( ) 6 1 _<1 1 5 10 3 2 6 4 _<1 ₁ 5 10 2 P

α

α

α

α

α

α

α

α

α

≤ − ≤ = + ≤ + ≤

Il lemma ci permette di dimostrare un upper bound a |FFD(l)| nel caso in cui la lista l sia composta da soli elementi “leggeri”.

Proprietà 4.1

Sia l ={x1,...,xq} una lista di elementi t.c. ∀ ∈ .w(xix_i l )≤1/2,allora : ( ) 3 ( ) 1

2

Dimostrazione

Per come è definita l’euristica FFD, siamo certi che per tutti gli interi i,j t.c. 1≤i<j≤|FFD(l)| vale la relazione:

( ) 1 ( )

j i

x B∈ w x > −w B (1)

Infatti, FFD mette x nel bin Bj solo se in tutti i bin Bi , precedenti a Bj ,non ha trovato spazio sufficiente per potervi mettere x.

Possiamo applicare il lemma 4.1 utilizzando la funzione w al posto di R :

| ( )| 1 ( ( )) | ( ) | 1 max 0, ( ( )) 1 i FFD l x l i b B P w x FFD l P w b ∈ = ∈ > − + −

da cui possiamo ottenere la seguente maggiorazione di |FFD(l)|:

| ( )| 1 | ( ) | ( ( )) 1 max 0, ( ( )) 1 i FFD l x l i b B FFD l P w x P w b ∈ = ∈ < + − − ( ) | ( ) | ( ( )) 1 x l FFD l P w x ∈ < + (2).

Verifichiamo che vale la relazione: 3

( ( )) ( )

2

P w x ≤ w x ∀ ∈ x_i l (3).

Dalla definizione di P segue che: se w(x) 0,1 ( ( )) 6 ( ) 6 P w x 5w x ∈ = e dunque la (3) è vera se w(x) 1 1, ( ( )) 9 ( ) 1 6 3 P w x 5w x 10 ∈ = − la (3) è vera se w(x) 1 1, ( ( )) 6 ( ) 1 3 2 P w x 5w x 10 ∈ = + la (3) è vera

Dalla (3) segue immediatamente che:

3 3

( ( )) ( ) ( )

2 2

Combinando la (4) e la (2) segue la tesi:

|FFD(l)|<3 ( ) 2w l +1

Proprietà 4.2

Sia l ={x1,...,xq} una lista di elementi e FFD l( )=

(

B B₁, ,...,₂ B_{FFD l( )}

)

.Allora: FFD l( ) (= FFD l FFD lH( ), ( ))L

dove,

• FFD l =_H( ) B B₁, ,...,₂ B_l+ ovvero tutti i bin di FFD l che contengono ( ) un elemento di peso strettamente maggiore di ½

• l =_L l− B1 B2 ... B_l+ , cioè tutti gli elementi che non appartengono ai primi |l+| bin di FFD(l).

Dimostrazione

Ricordiamo che FFD, è un algoritmo off line e che gli elementi sono ordinati in senso decrescente.

Il suo comportamento, al contrario di quelli on line, è deterministico. Quindi fissata una lista di elementi l, i bin prodotti da FFD saranno sempre gli stessi e riempiti allo stesso identico modo indipendentemente dall’ordine con cui si presentano.

Per definizione di FFD, i primi |l+| bin prodotti sono quelli che contengono gli elementi pesanti di l.

SianoFFD l i primi |l_H( ) +| bin di FFD(l). Togliamo da l tutti gli elementi che sono finiti nei bin di FFD l . Ovvero, eliminiamo da l tutti gli elementi di l_H( ) + e quelli “leggeri” che FFD ha messo nei primi |l+|. Gli elementi che rimangono (che indichiamo con lL) sono esattamente quelli contenuti nei bin di FFD(l) che non contengono alcun bin pesante.

Esempio

Se ora applichiamo FFD alla lista lL, proprio per il suo comportamento deterministico, otteniamo gli stessi bin di FFD(l) che contenevano solo elementi leggeri. Dunque,

1

( ) ( ,...., _l , ( ))L

FFD l = B B FFD l+ che è quanto volevamo dimostrare.

Possiamo adesso determinare l’upper bound di |FFD(l)|.

Proprietà 4.3

Sia l ={x1,...,xq} una lista di elementi. Allora:

( ) 3 ( ) 1 2

FFD l _≤ l+ ₊ w l− ₊

Dimostrazione

Consideriamo la sequenza di elementi lL cosi come è stata definita nella proprietà 4.2. Poiché tale sequenza è composta da soli elementi con peso non maggiore di ½, possiamo applicare la proprietà 4.1:

3

( ) ( ) 1

2

L L

FFD l < w l + (1)

Osserviamo che lL non è detto che contenga tutti gli elementi “leggeri” di l (cioè quelli di peso ≤1/2),poiché alcuni potrebbero essere stati inseriti da FFD nei bin che contengono gli elementi “pesanti”. Quindi:

|l+| ( ) H FFD l = FFD(l) elementi di l+ elementi di lL bin di FFD lH( ) Legenda

lL ⊆ l− ₍₂₎

per la (2) segue che w(lL)≤w(l−) e quindi, grazie alla (1), la quantità FFD l( )_L può essere maggiorata come segue:

3

( ) ( ) 1

2

L

FFD l < w l− + (3) Dalla proprietà 4.2 segue che

3

| ( ) | ( ) ( ) 1

2

H

FFD l _≤ FFD l ₊ w l− _{+ (4)}

Per definizione di l+ e poiché un bin può contenere un solo elemento pesante, si ha che FFD lH( ) = l+ . Combinando quest’ultima considerazione con la (4), otteniamo la tesi:

3

( ) ( ) 1

2

FFD l _≤ l+ ₊ w l− ₊

Con le due prossime proprietà, determiniamo un limite superiore a |FFD(l)| nel caso in cui i bin prodotti da FFD abbiano tutti un peso superiore a 1/2.

Proprietà 4.4

Sia l ={x1,...,xq} una lista di elementi t.c. ∀ ∈ .w(xix_i l )≤1/2. Supponiamo che tutti i bin prodotti da FFD, abbiano ciascuno un peso strettamente maggiore di 1/2. Vale la relazione,

FFD l( ) <3 ( ) 1 2w l + (1) 4

Dimostrazione

Dividiamo la dimostrazione in due casi: il primo quando |FFD(l)|≤ 1 ed il secondo per |FFD(l)|>1.

Caso1 |FFD(l)| ≤ 1

Per ipotesi ogni bin pesa almeno 1/2, quindi w(l)>1/2. In questa situazione dunque la (1) è rispettata: ( ) FFD l =1<3 1 1 2 2 4 + + =1+

Caso2 |FFD(l)|>1

Osserviamo che in queste ipotesi, ogni bin contiene almeno due elementi. Infatti, ogni elemento pesa al più 1/2, mentre ogni bin ha un peso≤ 1/2.

Chiamiamo gap di un bin B, lo spazio libero di B. Siano Bi e Bj due bin tali che 1≤ i<j ≤ |FFD(l)|.

Supponiamo che ciascuno abbia un peso ≤ 2/3. Per come funziona FFD, gli elementi in Bj devono avere ciascuno un peso strettamente maggiore del gap di Bi dunque ognuno deve pesare almeno 1/3. Sappiamo però che Bj contiene almeno due elementi, quindi il suo peso è > 2/3, contraddicendo l’ipotesi iniziale. Dunque tutti i bin, tranne al più uno, pesano più di 2/3.

Da quanto detto segue che,

w(l)=peso di tutti i bin > 2( ( ) 1) 3 FFD l − +1/2 quindi la (1) è verificata.

Proprietà 4.5

Sia l ={x1,...,xq} una lista di elementi. Supponiamo che tutti i bin prodotti da FFD, abbiano ciascuno un peso strettamente maggiore di 1/2. Vale la relazione, FFD l( ) ≤ || | 3 ( ) 1

2 4

l+ ₊ w l ₊

La dimostrazione ricalca quella della proprietà 4.3. Basta osservare che stavolta, per la proprietà 4.4, vale la relazione

3 1

( ) ( )

2 4

L

FFD l < w l + (dove lL è quella definita nella proprietà 4.2)

4.2.1.2 Caso BPP con elementi “divisibili”

In [BPJohn87] sono definiti due particolari problemi di BPP, in cui s’impongono nuovi vincoli ai pesi degli elementi.

Indichiamo con (l,C) un’istanza di BPP in cui i bin hanno capacità C. Sia

{

1, ,...,2 s

}

W = w w w l’insieme dei possibili valori che il peso di ogni elemento può assumere. Se W è tale che:

1. 0<w_s <w_s−1<...<w₂<w₁≤ 1

2. w ws| s−1|...|w w2| 1 (cioè ws divide ws-1 che divide ws-2 ecc.. )

allora diciamo che (l,C) è weakly divisible.

Se inoltre il peso più grande w1 divide la capacità C dei bin, allora parleremo di BPP Strongly Divisible.

Nei prossimi due paragrafi determiniamo un upper bound a |FFD(l)| quando FFD è utilizzata per risolvere il BBP nei due casi appena definiti.

Caso Strongly Divisible

Teorema 4.1[BPJohn87]

Consideriamo il BPP nel caso strongly divisible, vale la relazione: ( )

( ) ( ) w l

FFD l OTT l

C

= =

con C la capacita dei bin utilizzati e w(l) il peso degli elementi contenuti in l.

Dimostrazione

Sia B un qualsiasi bin parzialmente riempito da FFD.

Osserviamo che il gap di B, è un multiplo intero (anche nullo) del peso w Bm( ) del più “piccolo” elemento x contenuto in B. Ad esempio, consideriamo un bin B in cui è stato inserito un solo elemento x1. Poiché per ipotesi w(x1)|C, segue che o w(x1)=C, oppure C=kw(x1) con k≥ 2 intero. Nel secondo caso il gap varrà (k– 1)w(x1), quindi lo spazio libero in B è un multiplo intero di w(x1). Se in B viene inserito un secondo elemento x2, per come procede FFD, siamo certi che w(x2)≤ w(x1). Inoltre, per ipotesi, w(x2) divide w(x1), quindi (k-1)w(x1) è multiplo intero di w(x2). Siamo nelle stesse condizioni in cui eravamo quando abbiamo inserito x1 in B: o c’è spazio libero e questo è multiplo di w(x2), oppure il bin è pieno.

Da questa osservazione segue che un qualsiasi elemento x ancora da inserire, se non trova spazio in B può essere solo perché B è completamente pieno. Infatti, x

ha un peso w(x) sicuramente minore o uguale al più piccolo elemento presente in B e l’eventuale gap di B è un multiplo di w(x).

Possiamo concludere che, quando l’euristica termina, il peso di ogni bin vale uno, tranne al più l’ultimo. In altre parole FFD l( ) = w l C( ) / e FFD l( )è una soluzione ottima.

Caso Weakly Divisible

Anche nel caso weakly divisible, first fit decreasing fornisce una soluzione ottima al problema del bin packing. Vale infatti il teorema seguente:

Teorema 4.2 [BPJohn87]

Consideriamo il BPP nel caso weakly divisible . Sia l=( x1,..., xr) una lista di elementi , allora FFD(l)=OTT(l) .

Purtroppo stavolta non vale l’equazione FFD l( ) = OTT l( ) = w l C( ) / . Per poter ricavare un limite superiore a |FFD(l)| in funzione di w(l), dobbiamo procedere in modo simile a quanto fatto nel caso BPP classico.

Proprietà 4.6

Consideriamo il BPP nel caso weakly divisible.

Sia l ={x1,...,xq} la lista degli elementi e W =

{

w w₁, ,...,₂ w_s

}

t.c :

1 2 1 1 0 ... 2 s s w w₋ w w < < < < < ≤ Allora, * ( ) ( ) w l FFD l C ≤ con * 1 1 1 C w w = .

Dimostrazione

Risolviamo

( )

_{,lC applicando FFD. Poiché} * * 1|

w C , siamo nel caso stongly divisible. Dunque, dal teorema 4.1 segue che,

* * * ( ) ( , ) ( , ) w l FFD l C FFD l C C = = (1)

Poiché _C*_{≤ = è immediato verificare che 1 C} *

|OTT l C( , ) |≥ OTT l C( , ) (2)

Per ipotesi siamo nel caso weakly divisible, quindi applicando il teorema 4.2segue che:

( , ) ( , )

FFD l C = OTT l C (3)

combinando la (1) la (2) e la (3) segue la tesi:

* * ( ) ( , ) ( , ) w l FFD l C FFD l C C ≤ =

Il teorema 4.2, ci consente di dimostrare la seguente proprietà.

Proprietà 4.7

Sia (l,C) un istanza di BPP weakly divisibile. Allora,

( ) ( ) ( )

FFD l _≤ FFD l+ ₊ FFD l− _.

Dimostrazione

Dal teorema 4.2 segue che

( ) ( ) ( ) ( ) ( ) ( ) FFD l OTT l FFD l OTT l FFD l OTT l + + − − = = =

da cui essendo OTT l

( )

_≤ OTT l

( )

+ ₊OTT l

( )

− _{otteniamo la tesi.}

La prossima proprietà è molto semplice da dimostrare, ma mette in luce una caratteristica del caso weakly divisible che forse non è evidente.

Proprietà 4.8

Consideriamo il BPP nel caso weakly divisible.

Sia W =

{

w w1, ,...,2 ws

}

l’insieme dei possibili pesi degli elementi. Allora esiste

al più un elemento di W che sia strettamente maggiore di 1 2.

Dimostrazione

Supponiamo per assurdo che W contenga almeno due elementi strettamente maggiori di 1 2. Siano ad esempio 1 1 1 2 w = + ,ε ₂ 1 ₂ 2

w = + con ε ε ε₁, ₂ > .Dalla definizione di 0 weakly divisible segue che:

2 1

w w ovvero w1=kw2con k 2≥ intero (se fosse k=1 allora w2 = che è contro w1

l’ipotesi iniziale).

Quindi,

1 2

1 ₁

2

w =k +kε > che è impossibile per definizione di W.

Ora possiamo determinare il limite superiore a |FFD(l)| per il caso weakly divisible.

Proprietà 4.9

Consideriamo il BPP nel caso weakly divisible. Sia W =

{

w w₁, ,...,₂ w_s

}

con w1>1

2. Vale la seguente relazione:

* ( ) ( ) w l FFD l l C − + ≤ + dove, * 2 2 1 C w w = .

Dimostrazione Dalla proprietà 4.7, ( ) ( ) ( ) FFD l _≤ FFD l+ ₊ FFD l− ₍₁₎ Poiché FFD l

( )

+ ₌ l+ _{la (1) diventa,} ( ) ( ) FFD l _≤ l+ ₊ FFD l−

applicando la proprietà 4.6 otteniamo la tesi: * ( ) ( ) w l FFD l l C − + ≤ +

4.2.2 Studio di RSC_FFD e nuovi limiti superiori a M(n,r)

Andiamo ora ad analizzare il comportamento di RSC_FFD negli ambienti continuo e discreto ristretto. Più precisamente, grazie ai risultati ottenuti nel paragrafo precedente, determineremo il minimo numero di switch centrali che RSC_FFD richiede nei due casi, per rendere riconfigurabile una rete di Clos.

4.2.2.1 Caso continuo

Il prossimo risultato migliora quello del teorema 3.12 nel caso in cui w∈(0,1] che è poi la situazione più generale possibile.

Teorema 4.3 (Caso continuo)

Sia C(n,m,r) una rete di Clos simmetrica e w∈(0,1]. Se m≥ (7/4)n+r allora

utilizzando l’algoritmo di routing Routing_Solid_Connection_FFD (RSC_FFD), C(n,m,r) è riconfigurabile.

In altre parole,

M(n,r) 7 4n+r.

Dimostrazione

Da quanto osservato all’inizio del paragrafo 4.2, quello che dobbiamo dimostrare è che per ogni frame F di Φ (n,r), vale la relazione

1 ( )_i r ( )_ij j B t FFD t = = 7 4n+r ∀ =i 1,..,r(1) (con ti generica riga della matrice di traffico TF associata ad F).

Applicando la proprietà 4.3. a tij,otteniamo: 3 ( ) ( ) 1 2 ij ij ij FFD t ≤ t+ + w t− + ∀ ∈ t_ij T_F 1 ( , , ) ( , , ) 2 dove 1 ( , , ) ( , , ) 2 ij ij ij ij t i j w i j w t w t i j w i j w t w + − = ∈ ∧ > = ∈ ∧ ≤

Poiché t tij+, ij− costituiscono una partizione di tij segue che w t( )ij =w t( )ij+ +w t( )ij− , da

cui: 3 ( ) ( ) ( ) 1 2 ij ij ij ij FFD t _≤ t+ ₊ w t ₋w t+ ₊ ij F t T ∀ ∈ Per definizione di t_ij+_{, ( )} 1 2 ij ij w t+ _> t+ _{, quindi} 3 ( ) ( ) 1 4 2 ij ij ij t FFD t w t + ≤ + + ∀ ∈ t_ij T_F (2)

Poiché B t( )_i = r_j=1 FFD t( )_ij dalla (2) segue che:

1 1 1 1 3 ( ) ( ) ( ) 4 2 r r r i ij ij ij j j j B t FFD t t+ w t r = = = = ≤ + + (3) Osserviamo che: • 1 r ij j t+ =

è il numero di richieste che pesano più di ½ e che arrivano allo switch d’ingesso i.

Per la proprietà 1.1 segue che 1 r ij j t+ n = ≤ (4) • 1 ( ) r ij j w t =

è il peso totale delle richieste che arrivano allo switch d’ingresso i.

Per la proprietà 1.1 segue che

1 ( ) r ij j w t n = ≤ (5) per la (4) e la (5),la (3) può essere maggiorata come segue:

1 3 7 ( ) ( ) 4 2 4 r i ij j n B t FFD t n r n r = = ≤ + + = +

che è quanto volevamo dimostrare.

Rispetto al teorema 3.12, abbiamo quindi ottenuto un miglioramento per qualsiasi valore di n e r. Infatti con il teorema 3.12 era stato dimostrato che per w∈(0,1], M(n,r) 2n+r.

Dal teorema 4.3 segue il corollario.

Corollario 4.1

Sia C(n,m,r) una rete di Clos simmetrica e w∈(0,1/2]. Se m≥ (3/2)n+r allora

utilizzando l’algoritmo di routing RSC_FFD, C(n,m,r) è riconfigurabile. In altre parole,

M(n,r) 3 2n+r.

La dimostrazione si ricava da quella del teorema precedente osservando che

ij F

t T

∀ ∈ t_ij+ _{=0. Infatti per ipotesi w∈(0,1/2], quindi}

ij t+_{=∅ e} ij t−₌ ij t .

Diamo un’interpretazione in termini meno formali dei due risultati appena ottenuti.

Sia C(n,m,r) una rete di Clos che utilizza RSC_FFD come algoritmo di routing. Consideriamo la configurazione R calcolata da RSC_FFD, per un frame F.

Il teorema ci dice che in media, per ogni switch d’ingresso (uscita), 7/4n link della rete hanno un carico maggiore di 4/7 (≈ 0,57). Se il peso di ogni connessione vale al più 1/2, il corollario invece afferma che per ogni switch d’ingresso (uscita), 3/2n link hanno un carico di almeno 2/3. In entrambi i casi, per ogni switch d’ingresso e uscita, ci sono al più r link, che possono avere un carico che tende a zero.

La figura seguente mostra quanto appena detto per il teorema 4.3.

Ricordiamo che con Routing_Solid_Connection, avevamo dimostrato che M(n,r)≤ 2n+r. Diamo, anche per questo risultato, la stessa interpretazione data per il teorema 4.3 , in termini di utilizzo dei link della rete. Sia R una configurazione prodotta da RSC. Per ogni switch del primo e terzo stadio, il carico di 2n link è di almeno 1/2 mentre per i rimanenti r possiamo solo affermare che è maggiore di 0. Rispetto a RSC, l’utilizzo di FFD al passo 1, non ha quindi escluso lo “spreco” di r link per ogni switch d’ingresso e uscita. I rimanenti link però sono stati

n w>4/7 (7/4)n 1 (7/4)n+1 Ii Oj w>4/7 w>4/7 n w>4/7 (7/4)n+r w>0 w>0 w>0 w>0

“utilizzati meglio”. Infatti con RSC, il loro carico è garantito essere maggiore di 1/2, mentre con RSC_FFD vale per lo meno 4/7.

4.2.2.2 Caso discreto ristretto

Ricordiamo che nell’ambiente discreto ristretto il peso di ogni connessione appartiene all’insieme finito W={w1,w2,..,wh,...,wk} ed è tale che

• 1 ≥ w1>w2>……….>wh>1/2≥ wh+1>wh+2>………>wk>0 • wh+2|wh+1 , wh+3|wh+2 ,..., wk| wk-1

In analogia al BPP, definiamo due istanze particolari dell’ambiente discreto ristretto.

Sia W={w1,w2,...,ws} l’insieme dei possibili valori che il peso delle connessioni può assumere. Se W è tale che:

• 0<w_s <w_s−1<...<w₂<w₁≤ 1 • w ws| s−₁|...|w w₂| ₁

allora parliamo di ambiente discreto ristretto weakly divisible .

Se inoltre w1 divide 1, allora parleremo di ambiente discreto ristretto strongly divisible.

Ora determiniamo un limite superiore a M(n,r) per l’ambiente discreto ristretto mentre nei prossimi paragrafi lo faremo per i suoi due sottocasi.

Teorema 4.4 (Caso discreto ristretto)

Consideriamo una C(n,m,r) in ambiente discreto ristretto. Sia *

1 1/ 1

h h

C =w+ w+ :

se m≥_max

{

(

_{1 (1 )(1/} *₎

)

_{, /} *

}

h

n + −w C +r n C + allora, utilizzando l’algoritmo di r routing Solid_Connection_FFD, C(n,m,r) è riconfigurabile.

In altre parole,

M(n,r) max _n 1 1 w_*h _r , n_{* r}

C C

−

Dimostrazione

Analogamente a quanto visto nella dimostrazione del teorema 4.3, quello che dobbiamo verificare è che per orni frame F di Φ (n,r), vale la relazione

1 ( )i r ( )ij j B t FFD t = = max _n 1 1 w_*h _r , n_{* r} C C − + + + ∀ =i 1,..,r (con ti generica riga della matrice di traffico TF associata ad F).

Verifichiamo che nell’ambiente discreto ristretto vale la relazione, FFD(tij)≤| |tij+ +FFD t( )ij− (0)

Dalla proprietà 4.2 segue che ( )_ij

FFD t = ( )L

ij ij

t+ ₊ FFD t

Per definizione di ambiente discreto ristretto, ( L ij

t ,1) è un istanza del BPP weakly divisible. Per il teorema 4.2 segue che ( )L

ij FFD t = ( )L ij OTT t , quindi ( )_ij FFD t =t_ij+ _{+ ( )}L ij OTT t (1). Ma L ij t ⊆tij−, dunque ( )L ij OTT t ≤ OTT t( )ij− =|FFD t( ) |ij− (2). Dalla (1) e la (2) otteniamo la (0) ( )_ij FFD t =t_ij+ _{+ ( )}L ij OTT t ≤ t_ij+ _{+| ( ) |} ij FFD t− ₍₃₎

Poiché tij−soddisfa le condizioni del BPP weakly divisible, possiamo applicare la

proprietà 4.6: * * ( ) ( ) ( )ij ij ij ij + ij +1 w t w t FFD t t t C C − − + + ≤ + ≤ ∀ ∈ t_ij T_F con * 1 1 1 h h C w w + + = .

Essendo t t_ij+, _ij− _{una partizione di}

ij

* ( ) ( ) ( ) + ij ij +1 ij ij w t w t FFD t t C + + − ≤ ∀ ∈ (4). t_ij T_F

Per definizione,tij+ è composto da elementi con peso maggiore o uguale a wh,

quindi ( )w tij+ ≥w th ij+ . La (4) diventa: * ( ) ( )_{ij ij} +w tij w th ij +1 FFD t t C + + − ≤ ∀ ∈ t_ij T_F * * ( ) ( ) 1 h ij 1 ij ij w t w FFD t t C C + ≤ − + + ∀ ∈ tij TF da cui , ∀ ∈ t T_{i F} * * 1 1 1 1 ( ) r ( ) 1 h r r ( ) i ij ij ij j j j w B t FFD t t w t r C C + = = = = ≤ − + + (5)

Maggioriamo la (5) in due modi diversi a seconda del valore di 1 wh_*

C

− .

Se 1 w_*h 0 C

− ≥ , allora per la proprietà 1.1 sappiamo che

1 ( ) r ij j w t n = ≤ e 1 r ij j t+ n = ≤ . Quindi i F t T ∀ ∈ ( ) 1 _*h 1_* i w B t n n r C C ≤ − + + =_n 1 1 w_*h _r C − + + Osserviamo che 1 wh_* 0 C − ≥ è vera per * h C ≥w . Se invece 1 wh_* 0 C

− ≤ , allora la (5) può essere maggiorata per

1 0 r ij j t+ = = , ottenendo: * ( )i n B t r C ≤ +

Unendo le due maggiorazioni, otteniamo la tesi: 1 ( )_i r ( )_ij j B t FFD t = = ≤max _n 1 1 w_*h _r , n_{* r} C C − + + +

Il risultato che abbiamo appena esposto, esprime un limite superiore a M(n,r) in funzione anche di wh e wh+1. Questo è corretto, perché nel caso discreto ristretto, i valori di wh e wh+1 sono noti a priori.

Vogliamo ora dare un’espressione di tale limite superiore, solo in termini dei parametri r ed n. Si può facilmente verificare che le quantità

(

_{1 (1 )(1/} *₎

)

h

n + −w C + e r n_* r

C + hanno come estremo superiore rispettivamente (7/4)n+r e (3/2)n+r .In particolare si dimostra che

* 1 1 wh n r C − + + =7 4n r+ per wh (1/ 2) + → e wh+1→(1/ 3)+ * n _r C + = 32n r+ per wh+1 (1/ 3) + →

Dal teorema 4.4 , e da quanto appena osservato segue che, M(n,r) (7/4)n+r. ∀wh+₁,wh

Nel caso pessimo quindi, l’analisi che abbiamo condotto per l’ambiente discreto ristretto, non migliora il risultato ottenuto per l’ambiente continuo (si veda teorema 4.3)

Nei prossimi due paragrafi studieremo RSC_FFD, nei casi discreto ristretto weakly divisible e discreto ristretto strongly divisible.

4.2.2.3 Caso discreto ristretto weakly divisible

Ricordiamo che nell’ ambiente discreto ristretto weakly divisible, il peso di ogni connessione appartiene all’insieme finito W={w1,w2,...,ws} dove,

• 0<ws <ws−₁<...<w₂<w₁≤ 1 • w w_s| _s−1|...|w w₂| ₁

Osserviamo che la definizione corrisponde esattamente alle condizioni imposte dal problema di bin packing weakly divisible. Per la proprietà 4.8, segue che w1 è il solo valore strettamente maggiore di ½.

Teorema 4.5 (Caso discreto ristretto weakly divisible )

Consideriamo una C(n,m,r) in ambiente discreto ristretto weakly divisible. Sia

*

2 1/ 2

C =w w , se m≥

(

*

)

1

1 (1 )(1/ )

n + −w C + allora, utilizzando l’algoritmo di r routing RSC_FFD, C(n,m,r) è riconfigurabile. In altre parole, M(n,r) 1 * 1 1 w n r C − + + . Dimostrazione

Applichiamo il teorema 4.4 con wh=w1 e wh+1=w2

M(n,r) 1 * * 1 max n 1 w r , n r C C − + + + con * 2 1/ 2 C =w w .

Dalla dimostrazione del teorema 4.4, si ricava che

1 * * 1 max n 1 w r , n r C C − + + + = 1 * 1 1 w n r C − + + se e solo se 1 * 1 w 0 C − ≥ .

Poiché w1≤ 1 e w2|w1, segue che C*=w2 1/w2 ≥ w1. Ciò implica che, 1 * 1 w 0 C − ≥ . Quindi, 1 * * 1 max n 1 w r , n r C C − + + + = 1 * 1 1 w n r C − + +

Analogamente a quanto fatto per il caso discreto ristretto, determiniamo ora un limite superiore a M(n,r) che sia in funzione dei soli parametri r ed n. A questo scopo, con la prossima proprietà, calcoliamo, al variare di w1 e w2, l’estremo superiore della quantità

(

*

)

1

1 (1 )(1/ )

n + −w C + . Ricordiamo che nel caso r discreto ristretto avevamo ottenuto che M(n,r)≤ (7/4)n+r, un risultato poco interessante, poiché già noto dall’analisi del caso continuo (teorema 4.3). Come vedremo, stavolta sarà diverso ed otterremo un maggiorazione di M(n,r) migliore.

Proprietà 4.10

Sia 0 ₂ 1 ₁ 1

2

w w

< < < < ew₁ =βw₂ con β ≥2 intero,allora:

1 2 1 * * , 5 sup 1 3 w w w n n r n r C C − + + = + .

Prima di vederne la dimostrazione, verifichiamo che vale la seguente proprietà.

Proprietà 4.10.1

Sia k un intero t.c. β < ≤k 2β. Allora, 1. f w

( )

2 = *2

1 w C

β −

è continua e monotona decrescente per w2∈ 1 1,

1 k k− 2. 2 2 2 2 * * 1 1 1 1 1 1 sup

lim

w k k w k w w C C

β

β

+ < ≤ − → − ₌ − = 1 k k

β

− − con

β

≥ intero. 2 Dimostrazione Osserviamo che 2 * 1 w C

β

− = 2 2 2 1 1 w w w

β

− = 2 2 1 ( 1) w w k β − − per w2∈ 1 1, 1 k k− Poniamo f w

( )

₂ = 2 2 1 ( 1) w w k β − −

Per ipotesi k > ≥ , segue che β 2 w k₂( −1)≠ e visto che 0 f w

( )

₂ è il rapporto di due funzioni continue, segue che f w

( )

2 è continua nell’intervallo

1 1

, 1

k k− ⊇ 1 1k k, −1

Dimostriamo ora che f w

( )

2 è derivabile in 1, 1

1

k k− e che la derivata prima è negativa:

( )

2 ' f w =

(

)

2 2 1 ( 1) k w k − −

poiché k> ≥ e β 2 w₂ > segue che 0 f w'

( )

₂ <0 ₂ 1, 1 1 w

k k ∀ ∈

− . Possiamo quindi concludere che f w

( )

2 è monotona decrescente in

1 1 , 1 k k− e dunque che 2 2 2 2 * * 1 1 1 1 1 1 sup

lim

w k k w k w w C C β β + < ≤ − → − ₌ − .

Facendo i calcoli otteniamo

2 2 * 1 1 1

lim

w k w k C k β β + → − ₌ − −

Possiamo adesso passare alla dimostrazione della proprietà 4.10.

Dimostrazione

Osserviamo che la tesi può essere riscritta come

1 2 1 * , 1 5 sup 1 3 w w w n r n r C − + + = + (1)

Poiché n ed r sono indipendenti da w1,w2 e *1

1 w ₀ C − _{> segue che:} 1 2 1 * , 1 sup 1 w w w n r C − + + = 1 2 1 * , 1 sup 1 w w w n r C − _{+ + (2)}

Per ipotesi w₁ =βw₂ e 1 ₁ 1 2<w < , quindi: 1 2 2 1 2 * * , , 1 1 sup sup w w w w w C β C β − ₌ − = 2 2 * 2 1 1 2 1 max sup w w C β β β β ≥ < < − con β ≥ intero.(3) 2

Possiamo verificare che,

2 2 2 2 * ₂ * 1 1 1 1 2 1 1 1

sup max sup

k w w k k w w C β β C β β

β

β

< ≤ < < < ≤ − − ₌ − (4)

Infatti, poiché nel calcolo di

2 2 * 2 1 1 1 1 max sup k w k k w C β β

β

< ≤ < ≤ − − _consideriamo 2 w ∈ 1 1, 2

β β invece che w2∈ 1 1_{β β},₂ , segue che

2 2 2 2 * ₂ * 1 1 1 1 2 1 1 1

sup max sup

k w w k k w w C β β C β β β β < ≤ < < < ≤ − − _≤ −

Ma, come dimostrato nella proprietà 4.10.1, la funzione 2 * 1 w C β − è decrescente, quindi 2 2 * 1 1 1 1 sup w w C β β β < ≤ − −

è maggiore del valore che la funzione 2 * 1 w C β − assume in 1 β dunque la (4) è vera.

Dalla (4) e utilizzando la proprietà 4.10.1 segue che,

2 2 * ₂ 1 1 2 1 sup max 1 k w w k C β β k β β β β < ≤ < < − ₌ − − (5) Ma la funzione h k

( )

= 1 k k β −

− è monotona crescente per β ≥ ,2 β < ≤k 2β e , kβ interi. Dunque,

2 2 * ₂ 1 1 2 1 sup max 1 k w w k C β β k β β β β < ≤ < < − ₌ − − = 2 2 1 β β β − − =2 1 β β− . La funzione 2 1 β

β− è monotona decrescente per β ≥ intero. Quindi. il massimo 2 di 2 1 β β− si ha per β = ottenendo, 2 1 2 1 * , 1 sup w w w C − ₌ 2 2 * ₂ , 1 sup max 2 1 w w C β β β β β ≥ − ₌ − = 2 3 (6)

Dalle (2) e (6) segue che,

1 2 1 * , 1 sup 1 w w w n r C − + + = 2 1 3 n + + =r 5 3n r+

che è quanto volevamo dimostrare.

Dal teorema 4.5 e dalla proprietà 4.10, segue immediatamente il corollario:

Corollario 4.2

Consideriamo una C(n,m,r) in ambiente discreto ristretto weakly divisible. Se m≥ (5 / 3)n r+ allora, utilizzando l’algoritmo di routing RSC_FFD, C(n,m,r) è riconfigurabile.

In altre parole,

M(n,r) 5 3n r+ .

4.2.2.4 Caso discreto ristretto strongly divisibile

Nel caso discreto ristretto strongly divisile, vale il seguente teorema.

Teorema 4.6 (Caso discreto ristretto strongly divisible)

Consideriamo una rete di Clos C(n,m,r) in ambiente discreto ristretto strongly divisile. Se m≥ n r+ –1 allora, utilizzando l’algoritmo di routing RSC_FFD, C(n,m,r) è riconfigurabile.

In altre parole,

Dimostrazione

Analogamente a quanto già osservato negli altri casi, la tesi equivale alla relazione:

( )i 1

B t ≤ + −n r ∀t di Ti F (1)

Osserviamo che (tij,1) è un’istanza di BPP strongly divisible, in cui i bin hanno

capacità C=1. Possiamo quindi applicare il teorema 4.1 , ed ottenere,

( )ij ( )ij FFD t ₌ w t− ij F t T ∀ ∈ da cui, 1 1 1 ( )_i r ( )_ij r ( )_ij r ( )_ij j j j B t FFD t w t w t r = = = = = < + 1 i r≤ ≤ Per la proprietà 1.1 1 ( ) r ij j w t n = ≤ , quindi: 1 1 ( )i r ( )ij r ( )ij j j B t FFD t w t n r = = = = < + 1 i r≤ ≤

Poichè B t( )_i , r ed n sono valori interi e r,n≥ 2 segue

( )i

B t ≤ n r+ –1

Che è quanto volevamo dimostrare.

Analogamente a quanto abbiamo fatto per il caso continuo, diamo un’interpretazione di questo risultato in termini di utilizzo più o meno efficiente dei link della rete.

Sia C(n,m,r) una rete di Clos , F un suo frame ed R la configurazione calcolata da RSC_FFD, per F.

R è tale che possiamo garantire che su r link di ogni switch d’ingresso e uscita, ci sia un carico sicuramente maggiore di 0. I rimanenti n–1 link però sono utilizzati

4.3 Seconda modifica all’algoritmo Routing_ Solid_Connection

Nel capitolo 3, avevamo sottolineato che uno dei difetti dell’algoritmo Routing_Solid_Connection, era legato alla produzione di bin leggeri da parte dell’euristica E. Nel seguito, con un esempio, illustriamo tale difetto e il modo con cui cercheremo di attenuare i suoi effetti.

Siano TF e GF rispettivamente la matrice di traffico e il multigrafo delle

connessioni corrispondenti ad un frame F.

Al passo uno di RSC, viene applicata E ad ogni lista di connessioni tij

appartenente a TF.

Nella prossima figura abbiamo rappresentato un esempio per due elementi tij e tis.

tij ={ (i,j,w1), (i,j,w2) , (i,j,w3) } E(tij)={B1, B2}

tis ={ (i,s,w4), (i,s,w5) , (i,s,w4) } E(tis)={B3, B4}

Con il passo tre, l’ algoritmo Routing_Solid_Connection associa ad ogni bin un cammino diverso. A questo punto, tutte le richieste appartenenti ad un bin seguiranno il medesimo cammino, cioè attraverseranno gli stessi link e lo stesso switch centrale.

Nella figura seguente ad ogni cammino corrisponde un colore diverso. B1 B2 Oj Ii Os B3 B4

GF

B1 B2 Oj Ii Os B3 B4

Sottolineiamo il fatto che l’euristica è applicata solo a connessioni che hanno in comune sia lo switch d’ingresso che quello di uscita. Questo comporta che un link sia attraversato solo da connessioni che appartengono ad un unico bin. Il carico di un link quindi corrisponde esattamente al peso del bin associato. Come abbiamo visto nella dimostrazione, ad ogni applicazione dell’euristica, non è possibile escludere la produzione di un bin leggero (con peso massimo 1/2). Questo comporta che esistono link con un carico ≤ 1/2 e quindi sono “sottoutilizzati”. Nella figura seguente abbiamo evidenziato tali link.

L’idea della modifica a RSC che ora andiamo a presentare, è quella di “fondere” a due a due i bin leggeri, in modo che tutte le connessioni in essi contenuti passino attraverso un unico switch centrale. Come vedremo, rispetto all’algoritmo RSC, questo comporterà una riduzione del numero degli switch centrali necessari a rendere riconfigurabile una rete di Clos.

Nel prossimo paragrafo illustreremo nel dettaglio la modifica a RSC trascurando per il momento quella presentata nel paragrafo 4.2. Nel paragrafo 4.4, analizzeremo l’algoritmo che si ottiene utilizzando entrambe le modifiche.

n _i j n s 1/ 2 ≤ 1/ 2 ≤ ≤1/ 2 1/ 2 ≤

4.3.1 Algoritmo Routing_ Solid_Connection_Modificato

Consideriamo il seguente algoritmo.

Algoritmo Routing_Solid_Connection_Modificato( T )

1. Su ogni ti,j di T risolviamo il problema del bin packing, con un’euristica E.

Siano E(ti,j) i bin prodotti dall’applicazione di E a ti,j.

2. Indichiamo con H ij

u il numero di bin in E(ti,j) con peso strettamente

maggiore di ½ e L ij

u quello dei bin con peso minore o uguale ad ½. Costruiamo le matrici d’interi UH e UL ottenute da T sostituendo ogni elemento ti,j rispettivamente i valori uijHe uijL.

3. Costruiamo il grafo _{G che ha come matrice d’incidenza U}L L _{e i cui archi}

sono etichettati con il peso del bin a cui l’arco corrisponde. 4. Determiniamo un WEC di _{G .} L

5. Costruiamo il multigrafo _{G che ha come matrice d’incidenza U}H H _.

6. Determiniamo un EC minimo di _{G .} H

7. Ricomponiamo L

G e H

G in un unico multigrafo G. 8. return G.

Con il prossimo teorema, determiniamo il minimo numero di switch centrali che Routing_Solid_Connection_Modificato (RSC_Modificato) richiede per essere utilizzato come algoritmo di routing in una rete di Clos.

Teorema 4.7

Sia C(n,m,r) una rete di Clos simmetrica e w∈(0,1]. Se m ≥ 2n+ r/ 2 allora utilizzando l’algoritmo di routing RSC_Modificato, C(n,m,r) è riconfigurabile. In altre parole,

Dimostrazione

Siano TF e GF rispettivamente la matrice di traffico ed il multigrafo delle

connessioni associati ad un frame F di una C(n,m,r) con m≥ 2n+ r/ 2 .

Vogliamo dimostrare che l’algoritmo Routing_Solid_Connection_Modificato riesce a determinare un WEC per GF con al più 2n+ r/ 2 colori. Dalla proprietà

3.2, sappiamo che questo equivale a dire che l’algoritmo determina una configurazione R che realizza F ed è compatibile con la rete C(n,m,r).

Ricordiamo alcune notazioni viste nel capitolo precedente: • E è un euristica che risolve il BPP.

• Sia ti = ti,1 U ti,2U ...U ti,r-1U ti,r la lista di tutte le connessioni relative

alla riga i-esima di T.

• E(ti.j) = {B1,...,Bk} la soluzione ottenuta applicando l’euristica E alla lista

ti,j. Bs è un generico bin.(1 s k)

• B(ti) tutti i bin prodotti dall’applicazione di E alle r liste di connessioni

contenute nella riga i di T. Ad esempio per una riga ti di T vale

B(ti)=E(ti,1)U E(ti,2)U ...U E(ti,r-1)U E( ti,r ). Da cui |B(ti)|=

1 | ( ) | r ij j E t = • indichiamo con { Hi, Li } una partizione di B(ti) così definita:

Hi = { Bj | Bj ∈B(ti) ∧ w(Bj) > 1/2 } detto insieme dei bin “pesanti”

Li = { Bj | Bj ∈B(ti) ∧ w(Bj) 1/2 } detto insieme dei bin

“leggeri”.

Essendo { Hi, Li } una partizione di B(ti) vale

• |B(ti)|=|Hi|+|Li|

• w(B(ti))= w(ti)=w(Hi)+w(Li)

Consideriamo i multigrafi GH=(I,O,EH) e GL=(I,O,EL) che hanno come matrice d’incidenza rispettivamente UH e UL. Associamo ad ogni arco e di EH e EL, l’etichetta w(e) che è uguale al peso del bin a cui l’arco corrisponde.

Esempio

Sia Li={B1,B2,B3} la sequenza dei bin “leggeri” prodotti da E per la riga i di TF

Sia Hi={B1,B2,B3} la sequenza dei bin “pesanti” prodotti da E per la riga i di TF

Supponiamo di aver determinato un WEC su GL con k colori ed uno per GH con p. “Ricomponendo” GL _{e G}H _{nell’unico multigrafo G=(I,O,E}L_+EH_{), otteniamo un}

WEC per G con al più p+k colori.

Vediamo ora come, a partire dalla colorazione di G, si determina un WEC per GF

che usa al massimo p+k colori.

Il modo di procedere è analogo a quello visto nella dimostrazione del teorema 3.12. Infatti, il multigrafo G non è altro che GU dell’algoritmo

Routing_Solid_Connection.

Sia v un vertice di G. Indichiamo con Ac(v) gli archi di Gincidenti su v con stesso

colore c. Per definizione di WEC, il peso totale degli archi di Ac(v) è minore o

uguale ad uno. B3 Ii

G

L w(e1) w(e2) w(e3) B1 B2 w(B1)=w(e1) w(B2)=w(e2) w(B3)=w(e3) Ii

G

H _w(e 1) w(e2) w(e3) B1 B2 B3 w(B1)=w(e1) w(B2)=w(e2) w(B3)=w(e3)

Osserviamo che per ogni a∈Ac(v), corrisponde esattamente un bin Ba. Coloriamo

tutti gli archi e di G appartenenti a BF a con c.

Per costruzione, gli archi e di G incidenti su v con stesso colore c, hanno F

complessivamente un peso wc(v) uguale alla somma dei pesi dei bin a cui

appartengono. Quindi wc(v) corrisponde al peso degli archi Ac(v) di G ed è

sicuramente minore o uguale ad uno.

Ripetendo il procedimento per tutti gli archi di Gotteniamo un WEC per G . F

Ora determiniamo un limite superiore a k e p.

Limite superiore di p. Sia H i R = 1 r H ij j u =

la somma degli elementi della riga i della matrice UH.

H i

R rappresenta anche il numero |Hi| di bin “pesanti ”prodotti dall’applicazione di

E alle r liste di connessioni contenute nella riga i di TF. Dalla dimostrazione del

teorema 3.12 segue che,

H i

R =|Hi|≤ 2n (1)

La stessa considerazione vale per una qualsiasi colonna j di UH, dunque

L j C = 1 r L ij i u = ≤ 2n (2).

Poiché per ogni arco e di EH, vale w(e)>1/2, su nessun nodo di GH possono incidere più archi dello stesso colore. Da ciò segue che un WEC minimo di GH

corrisponde esattamente ad un EC minimo dello stesso multigrafo.

v

v

Per definizione di GH_{, il grado di un suo generico nodo I}

i∈I (Oj∈O) vale

H i

R ( L j

C ). Per la (1)e la (2) segue che GH ha un grado massimo 2n e per il lemma di Konig, GH ammette un EC minimo con 2n colori. In conclusione p≤ 2n.

Limite superiore di k.

Consideriamo la somma L i

R degli elementi della riga i di UL. Tale quantità è il numero |Li| dei bin “leggeri” in B(ti). Abbiamo già dimostrato (si veda teorema

3.12), che ad ogni applicazione dell’euristica E si produce al più un bin leggero, dunque L

i

R =|Li|≤ r. La stessa osservazione si può fare per una generica colonna j

di UL. Valgono quindi le relazioni,

1 1 r L L i ij j r L L i ij i R u r C u r = = = ≤ = ≤ (3)

Analogamente a quanto osservato per GH, dalle (3) e per il lemma di Konig, segue che GL ammette un EC minimo con r colori.

Osserviamo che l’EC di GL è anche un WEC sullo stesso grafo. Infatti, per costruzione, ogni etichetta w(e) vale il peso di un bin, quindi sicuramente w(e)≤ 1. Poiché i bin considerati sono quelli leggeri, ogni arco ha peso minore o uguale a ½. Possiamo quindi usare la metà degli r colori, ottenendo sempre un WEC per GL_.

Più precisamente:

• se r è pari il WEC di GL _{richiede al più r/2 colori k≤ r/2}

v

G

L w(e1) w(e2) w(e3) ≤ 1/2 ≤ 1/2 ≤ 1/2

• se r è dispari, ne occorrono r/ 2 k≤ r/ 2 . A questo punto la tesi del teorema è dimostrata:

GF ammette un WEC con al più 2n+ r/ 2 colori.

Osserviamo che al passo quattro non abbiamo specificato come determinare un WEC per GL. Un modo semplice per farlo e che garantisce di utilizzare al più

/ 2

r colori , è il seguente.

1. Determiniamo un EC minimo per GL. Sia C={c1,...,cd}, l’insieme dei

colori utilizzato e pmax il peso massimo che può avere un arco di GL, e

d=deg(GL) ≤ r.

2. Partizioniamo l’insieme C in sottoinsiemi di cardinalità z= 1/ p_max

ottenendo d/z sottoinsiemi. Ad esempio se d è multiplo di z con d=hz otteniamo, {c1,..,cz}, {cz+1,...,c2z},... ,{c(h-1)z,...,cd}

3. Per ogni sottoinsieme { ci,ci+1,...,ci+z-1} modifichiamo la colorazione di GL

nel seguente modo:

ricoloriamo tutti gli archi di colore ci+1,...,ci+z-1 con il colore ci.

Ricordiamo che per definizione di GL vale,

pmax≤ 1/2, quindi z= 1/ p_max ≥ 2.

deg(GL) ≤ r.

Quindi, poiché per il lemma di Konig GL ha un EC minimo con d= deg(GL) colori,

al termine della procedura avremo un WEC di GL con d/z ≤ r/2 .

Osserviamo che non potevamo utilizzare l’algoritmo RSC per ottenere il WEC di GL. Infatti GL è un grafo e non un multigrafo, quindi RSC avrebbe prodotto

Il teorema 4.7, fornisce un limite superiore a M(n,r) nell’ambiente continuo. Per quanto riguarda il caso discreto ristretto ed i suoi due sottocasi weakly e strongly divisible, purtroppo non siamo riusciti ad ottenere risultati migliori rispetto a quello appena visto.

4.4 Algoritmo RSC_FFD_Modificato

Vogliamo ora mettere assieme le modifiche presentate nei paragrafi 4.2 e 4.3. Chiamiamo RSC_FFD_Modificato, l’algoritmo ottenuto da RSC_Modificato utilizzando al passo uno, l’euristica FFD.

Algoritmo RSC_FFD_Modificato( T )

1. Su ogni ti,j di T risolviamo il problema del bin packing, con l’euristica

FFD. Siano FFD(ti,j) i bin prodotti dall’applicazione di FFD a ti,j.

2. Indichiamo con H ij

u il numero di bin in FFD(ti,j) con peso strettamente

maggiore di ½ e L ij

u quello dei bin con peso minore o uguale ad ½. Costruiamo le matrici d’interi UH e UL ottenute da T sostituendo ogni elemento ti,j rispettivamente con i valori uijHe

L ij u .

3. Costruiamo il grafo _{G che ha come matrice d’incidenza U}L L _{e i cui archi}

sono etichettati con il peso del bin a cui l’arco corrisponde. 4. Determiniamo un WEC di _{G .} L

5. Costruiamo il multigrafo _{G che ha come matrice d’incidenza U}H H _.

6. Determiniamo un EC minimo di _{G .} H

7. Ricomponiamo _{G e} L _{G in un unico multigrafo G.} H

8. return G.

Vogliamo determinare il minimo numero di switch centrali che RSC_FFD_Modificato richiede per essere utilizzato come algoritmo di routing in una rete di Clos.

Teorema 4.8

Sia C(n,m,r) una rete di Clos simmetrica e w∈(0,1].

Se m≥ min{(7/4)n+(1/4)r+ r/ 2 , 2n+ r/ 2 } allora, utilizzando l’algoritmo di routing RSC_FFD_Modificato, C(n,m,r) è riconfigurabile.

In altre parole,

M(n,r) min{(7/4)n+(r/4)+ r/ 2 , 2n+ r/ 2 }.

Dimostrazione

Vogliamo determinare cosa succede nell’algoritmo RSC_Modoficato utilizzando FFD come euristica.

Siano,

• TF, la matrice di traffico associata ad un frame F di ( , )Φ n r

• ti la riga i-esima di TF.

• |Hi| il numero di bin “pesanti ”prodotti dall’applicazione di FFD alle r

liste di connessioni contenute nella riga i di TF.

• |Li| il numero di bin “leggeri ”prodotti dall’applicazione di FFD alle r liste

di connessioni contenute nella riga i di TF.

Ripercorriamo la dimostrazione del teorema 4.7. Eravamo giunti alla conclusione che, grazie alla modifica apportata, il numero m di switch intermedi necessari a RSC_Modificato, sono

m=|Hi| +| | | / 2Li (1)

Utilizzando un’euristica E, che quando applicata produce al più un bin leggero, avevamo dimostrato anche che,

0≤ |Hi|≤ 2n

Dalla (1) segue che RSC_Modificato, per rendere riconfigurabile un C(n,m,r), richiede al più 2n+ r/ 2 switch centrali.

Quello che ora verificheremo è che utilizzando FFD in RSC_Modificato, otteniamo:

1. |Hi| min{(7/4)n+(1/4)r , 2n}

2. |Li|≤ r.

In questo modo, dalla (1) segue la tesi,

m=|Hi| +| | | / 2Li ≤ min{(7/4)n+(1/4)r , 2n}+ r/ 2 =

= min{(7/4)n+(1/4)r+ r/ 2 , 2n+ r/ 2 }

Osserviamo innanzi tutto che FFD, ogni volta che viene applicata, produce al più un bin “leggero” e tutti gli altri hanno un peso maggiore di ½. Quindi, anche per FFD vale,

0≤ |Hi|≤ 2n

0≤ |Li|≤ r

Per la (1) segue che m=|Hi| +| | | / 2Li ≤ 2n+ r/ 2 (2)

Rimane dunque solo da dimostrare che, |Hi| (7/4)n+(1/4)r (3) Per definizione |Hi|+|Li|= 1 | ( ) | r ij j FFD t = . Segue che |Hi|=|B(ti)|–|Li|= 1 | ( ) | r ij j FFD t = –|Li| con 0≤ |Li|≤ r

Un upper bound di |Hi|, si ha così quando ad ogni applicazione di FFD non si

produce nessun bin leggero (|Li|=0).

Determiniamo ora il limite superiore a

1 | ( ) | r ij j FFD t =

quando ogni bin prodotto pesa almeno 1/2.

Dalla proprietà 4.5, segue che, |FFD t( ) |ij ≤ 3 1 | | ( ) 2 4 ij ij t+ ₊ w t− ₊ ij F t T ∀ ∈

1 ( , , ) ( , , ) 2 dove 1 ( , , ) ( , , ) 2 ij ij ij ij t i j w i j w t w t i j w i j w t w + − = ∈ ∧ > = ∈ ∧ ≤

A questo punto i passaggi sono identici a quelli della dimostrazione del teorema 4.3. Per definizione di tij+, 1 ( ) 2 ij ij w t+ _> t+ _{, quindi} 3 1 ( ) ( ) 4 2 4 ij ij ij t FFD t w t + ≤ + + ∀ ∈ t_ij T_F (4)

Poiché H_i = r_j=1FFD t( )_ij dalla (4) segue che:

1 1 1 1 3 ( ) ( ) 4 2 4 r r r i ij ij ij j j j r H FFD t t+ w t = = = = ≤ + + (5) Osserviamo che: • 1 r ij j t+ =

è il numero di richieste che pesano più di ½ e che arrivano allo switch d’ingesso i.

Per la proprietà 1.1 segue che

1 r ij j t+ n = ≤ (6) • 1 ( ) r ij j w t =

è il peso totale delle richieste che arrivano allo switch d’ingresso i.

Per la proprietà 1.1 segue che

1 ( ) r ij j w t n = ≤ (7) per la (6) e la (7),la (5) può essere maggiorata come segue:

1 3 7 ( ) 4 2 4 4 4 r i ij j n r r H FFD t n n = = ≤ + + = +

Dunque abbiamo dimostrato che la (3) è vera, e così la tesi è provata.

Dal teorema segue immediatamente il corollario.

Corollario 4.3

Se m≥ min{(3/2)n+(1/4)r+ r/ 2 , 2n+ r/ 2 } allora, utilizzando l’algoritmo di routing RSC_FFD_Modificato, C(n,m,r) è riconfigurabile.

In altre parole,

M(n,r) min{(3/2)n+(1/4)r+ r/ 2 , 2n+ r/ 2 }

Per verificarlo, basta porre tij+ =0 nella dimostrazione del teorema precedente.

Per quanto riguarda l’ambiente discreto ristretto ed i suoi due sottocasi weakly e strongly divisible, non siamo riusciti a migliorare i risultati visti nel paragrafo 4.2. Più precisamente, conducendo per ognuno dei casi un’analisi del tutto simile a quella appena vista per il caso continuo, abbiamo ottenuto che:

M(n,r) min{(7/4)n+(1/4)r+ r/ 2 , 2n+ r/ 2 } nel caso discreto ristretto M(n,r) min{(5/3)n+r, 2n+ r/ 2 } nel caso discreto ristretto weakly divisible M(n,r) min{(n+r, 2n+ r/ 2 } nel caso discreto ristretto strongly divisible

La seguente tabella mostra una sintesi degli upper bound di M(n,r) che abbiamo ottenuto.

Valori ammissibili per il peso delle connessioni

Limite superiore (caso pessimo) M(n,r)

Continuo _{min{(7/4)n+(r/4)+ r/ 2 , 2n+ r/ 2 }} Continuo, con w∈(0,1/2] _{min{(3/2)n+(r/4)+ r/ 2 ,2n+ r/ 2 }} Discreto ristretto _{min{(7/4)n+(r/4)+ r/ 2 , 2n+ r/ 2 }} Discreto ristretto weakly divisible _{min{(5/3)n+r, 2n+ r/ 2 }}

Discreto ristretto strongly divisible min{n+r, 2n+ r/ 2 }

4.5 Confronto con i risultati precedenti

Vogliamo valutare la bontà dei limiti superiori a M(n,r) che abbiamo trovato rispetto a quelli noti fino ad oggi.