I grafi e il linguaggio C++ applicati ai protocolli di routing

In questo articolo studieremo alcuni problemi di base definiti su grafi e reti di elaboratori. In particolare si propone di esaminare le analogie tra le reti e la teoria matematica dei grafi pesati e non pesati, applicati ai protocolli di routing. In una rete un host mittente è connesso direttamente al cosiddetto default router origine (o di primo hop) presente nel suo segmento di rete e ad esso trasferisce tutti i pacchetti che deve spedire. Il problema da risolvere, che è quello di instradare un pacchetto tra host di origine e quello di destinazione, si riconduce chiaramente al problema d’instradare il pacchetto tra questi due router. Effettuare l’instradamento di un pacchetto in una rete equivale a individuare un “percorso” tra sorgente e destinazione: inoltre il cammino ricercato deve essere il più corto possibile, cioè siamo alla ricerca di un cammino minimo.Concettualmente possiamo identificare una rete di elaboratori con una struttura dinamica informatica (o matematica) particolare, il grafo. Quindi, effettuare la ricerca del cammino minimo tra due router equivale a quella di un cammino minimo in un grafo.