Reliable network topology design
- Global styles
- Apa
- Bibtex
- Chicago Fullnote
- Help
Abstract
ÖZET Bu tezde, zor bir kabşımsal optimizasyon problemi olan güvenilir bilgisayar ağlan için topoloji tasannu konusu incelenmiştir. Bu problemde, ağ elemanlarının güvenilirlikleri verilmesi halinde, hedef, maksimum güvenilirliğe sahip topolojiyi bulmaktır. Aynı zamanda, bir maliyet kısıtı kontrol edilmekte ve böylece en son bulunan topolojinin maliyetinin belli bir limitin üzerinde olmaması sağlanmaktadır. Bu problemi çözmek için tavlama benzetimi (simulated annealing) tekniği kullanılmıştır. Tavlama Benzetimi sonuçlarının doğruluğunu test etmek için, değişik testler gerçeUeştirilrniştir. Bu testleri iki ana grupta toplamak mümkündür: Küçük boyutlu ağlar üzerinde yapılan testler ve büyük boyutlu ağlar üzerinde yapılan testler. Güvenilirliğin hesaplanması sırasında, bir olasılık ifadesi bulunmakta, ve daha sonra bu ifade de yer alan olasılık terimlerinin yerine güvenilirlik değerleri yerleştirilmektedir. Olasılık ifadesini bulmak için de, her düğüm çifti arasındaki farklı yolların bulunması gerekmektedir. Bu amaçla Max- Flow algoritması kullanılmıştır. Tavlama benzetimi algoritmasındaki parametrelerin sonuca etkileri tartışılmış ve her bir algoritmanın zaman karmaşıklığı hesabedilmiştir. Test sonuçlan, tavlama benzetiminin bu problemde iyi sonuç verdiğini, ve problemin boyutunun artmasıyla, algoritmanın performansının da arttığını göstermiştir. IV ABSTRACT In this thesis, we have investigated the problem of reliable network topology design which is an NP-complete problem. In this problem, given the reliability of network elements, the goal is finding the topology with maximum reliability. At the same time, a cost constraint is checked so that the final topology has a cost below a given threshold. In order to solve this difficult problem, simulated annealing technique is used. In order to test the quality of the simulated annealing results, different kinds of tests with small and large size networks were performed. During the reliabiliy evaluation phase, a probability expression is found and then the probability terms are replaced with the reliability values so that the reliability of the topology is calculated. In order to find the probability expression, we have to find the disjoint paths between each node pairs. Max- Flow algorithm is used for that purpose. The effects of simulated annealing parameters on the results are discussed and the time complexity of each algorithm is also evaluated. The results show that simulated annealing performs well on this problem. Furthermore, this performance increases with the size of the networks.
Collections