Ingegneria del traffico IP : metodi di ottimizzazione per il risparmio energetico

La continua espansione dei servizi di rete basati su Internet sta diventando uno dei maggiori sostenitori della crescita dell'economia mondiale. Il principale problema consiste nel fatto che le infrastrutture di rete sono spesso sovradimensionate e attualmente non si hanno a disposizione degli algoritmi che permettono di ridurre il consumo di potenza della rete mantenendo buone performance. L'ingegneria del traffico tratta la redistribuzione del traffico mediante la modifica dei pesi virtuali dei collegamenti, mantenendo le specifiche di Quality of Service definite per la topologia. In questa tesi assumiamo che i pacchetti siano instradati secondo il protocollo Open Shortest Path First, proponiamo un modello matematico e sviluppiamo degli algoritmi di ottimizzazione per aiutare gli amministratori di reti IP locali a selezionare i pesi virtuali da assegnare ai collegamenti dell'Autonomous System in modo da minimizzare i consumi energetici spegnendo i collegamenti) mantenendo una buona congestione della rete. Dopo aver considerato semplici approcci greedy, particolarmente adatti al problema, abbiamo sviluppato un algoritmo greedy randomizzato adattativo (GRASP GTE) e successivamente lo abbiamo potenziato con una procedura di Path Relinking in modo da sfruttare le sequenze di soluzioni promettenti attraverso un meccanismo di memoria. Le euristiche sviluppate sono state valutate su vari tipi di istanze relative a tre topologie esistenti e matrici di traffico generate in modo realistico. I risultati computazionali indicano che, sulle istanze considerate, è possibile disattivare almeno il 50% dei nodi e dei collegamenti incrementando di non più del 30% la congestione, per alcune istanze permette di spegnere fino al 68% di nodi e il 60% di collegamenti con un incremento di solo il 20% della congestione.