soluzione rete dati

Dato il funzionamento previsto per il sistema (ogni calcolatore può funzionare tanto da punto di interrogazione o di risposta, quanto da centralino che avvia le transazioni verso la macchina cui sono destinate) il problema è di installare delle linee in modo che ogni calcolatore risulti connesso direttamente o indirettamente con tutti gli altri e che la soluzione scelta sia quella a minimo costo tra tutte quelle proponibili. La soluzione è quindi rappresentata dall’albero minimo che si può ricavare dal grafo ottenuto connettendo i calcolatori tra loro in tutti i modi possibili. E’ infatti evidente che la presenza di un qualsiasi ciclo aumenta i costi delle linee di trasmissione senza apportare nessun vantaggio (in termini di prestazioni) al sistema. Per ottenere l’albero minimo si utilizza il cosiddetto algoritmo greedy che prevede di scegliere ad ogni passo l’arco del grafo a peso minimo (nel nostro caso a distanza minima) che non chiuda un ciclo con gli archi già selezionati in precedenza. L’algoritmo termina quando sono stati selezionati un numero di archi pari al numero dei nodi presenti meno uno (quindi 8 nel nostro caso).

7) Ve-Tn (170) (Gli archi Ge-To (160) e Ao-Mi (170) vengono scartati perchè chiuderebbero dei cicli).

8) Mi-Bo (210) (L’arco To-Bo (200) viene scartato perchè chiuderebbe un ciclo).

In figura è riportata la soluzione con l’ordine di selezione segnato su ogni arco.

E’ evidente che, qualora il progetto dovesse essere realmente implementato, verrebbe probabilmente scelta una rete più complessa (e quindi più costosa) dell’albero minimo. Questo perché è generalmente preferibile avere una certa ridondanza delle linee per migliorare l’affidabilità complessiva del sistema. Nel caso dell’albero minimo infatti, un guasto ad una linea o ad un calcolatore non terminale dell’albero dividerebbe la rete in due sottoreti sconnesse. La presenza di qualche ciclo potrebbe consentire invece di assicurare il servizio anche in caso di guasti.