Progetto di programmazione

Link State Routing

(Descrizione delle specifiche del progetto durante la lezione di lunedi 27/1)

Ogni gruppo deve inviare il codice prodotto (programmi sorgente) per posta elettronica a rdc@dei.unipd.it
Per i gruppi costituiti da due o piu' studenti la scadenza e':

ore 24 del giorno 6 marzo 2003

Per i gruppi costituiti da un singolo studente la scadenza e':

ore 24 del giorno 13 marzo 2003

Sara' applicata una penalita' del 10% nel punteggio per ogni giorno di ritardo nella consegna del programma.

Il programma puo' essere scritto in un linguaggio di programmazione scelto fra C, C++, e Java.

Descrizione del progetto

Il progetto consiste della simulazione del protocollo di routing link state per una data topologia di rete. La rete e' simulata mediante la creazione e gestione di processi, uno per ogni nodo della rete. I processi utilizzano l'interfaccia socket per la comunicazione.
Il protocollo Simple Link State Routing da realizzare e' una versione ridotta e modificata dei protocolli di rete link state (ad esempio OSPF ) ed ha le seguenti caratteristiche:

Assume che non ci siano guasti nella rete
Non prevede un meccanismo di autenticazione
Non utilizza acknowledgments (se non nella fase di inizializzazione)
Il pacchetto LSP (Link State Packet) che contiene informazione di connettivita' e' inviato una sola volta da ogni nodo a tutti gli altri mediante una procedura di flooding perche', come si e'gia' detto, si assume che la topologia della rete resti invariata.

Input

Il programma legge da file la topologia della rete, con il seguente formato. La prima riga del file specifica il numero dei nodi della rete. Ogni riga successiva consiste di tre campi, i primi due contengono un numero intero identificatore di un nodo e il terzo campo il costo del link tra i due nodi.

Inizializzazione

Questa fase (decisamente diversa dal protocollo OSPF) consiste di uno scambio di messaggi fra un processo (master) e tutti i processi corrispondenti ai nodi della rete (slave) per distribuire l'informazione ai nodi circa la topologia della rete. Alla fine di questa fase ogni nodo avra' un certo numero di socket aperti e avra' comunicato al master i numeri di porta di tali socket. Questa comunicazione prevede l'invio di messaggio di ACK dagli slaves al master. Quando il master ha ricevuto gli ACK da tutti gli slaves, fa partire il Link State Routing mediante l'invio di un messaggio di START a tutti i nodi.

Formato dei Pacchetti

Il formato del pacchetto e' a scelta dello studente. Si suggerisce che ogni messaggio contenga un campo TYPE per identificare il tipo di messaggio.
Piu' precisamente tale campo specifica se si tratta di un messaggio di Hello tra master e slave per la inizializzazione, oppure di un ACK inviato da uno slave al master, oppure e' un messaggio del tipo Link State Update inviato da un nodo ad un altro per aggiornare le informazioni, e cosi via.

Output

L'output e' un insieme di file, ogni file e' associato ad un nodo della rete e contiene la lunghezza del cammino minimo ad ogni altro nodo. Alternativamente, ogni file di output contiene una rappresentazione (a scelta) dell'albero di costo minimo con radice nel nodo dato. Altre forme di output, ad esempio mediante interfacce grafiche, sono a scelta dello studente.

IMPORTANTE:
I gruppi costituiti da tre studenti devono seguire una delle due strade:
1) realizzare un flooding come nell'algoritmo standard di link state, che prevede l'invio periodico di pacchetti di aggiornamento circa la connettivita' (con simulazione di guasti)
2) proporre al docente una versione diversa del protocollo

I gruppi costituiti da due studenti devono seguire una delle due strade:
1) realizzare una interfaccia grafica per l'output del programma
2) proporre al docente una versione diversa del protocollo
Ci sara' un premio (in termini di punteggio assegnato) per versioni piu' sofisticate del protocollo.