Design and Implementation of a Hybrid algorithm for communication network reliability calculation

Abstract

İletişim ağının güvenilirliği, işletim ağlarının kullanılabilirliğini ve esnekliğini tanımlayan hizmet faktörlerinin kalitesi faktörlerinden biri olarak kullanılır. Birçok klasik algoritma mevcuttur, ancak bunların çoğu, hesaplama yükünün karmaşıklığın bir işlevi olarak arttığı karmaşık ağlarda gerçek zamanlı güvenilirlik değerlendirmesi için uygulanamaz. Mevcut çalışmada, her tür ağ için (basit ve karmaşık) iki uçlu güvenilirlik değerlendirmesi sorununu çözmek için yeni bir hibrit algoritma önerilmiş ve tam bir çözüm sağlanmıştır. Algoritma, verimli bir hibrit algoritma sağlayan iki klasik güvenilirlik yönteminin kombinasyonuna dayanmaktadır. Grafik dönüştürme yöntemi ve bağ setleri yöntemleri, çok aşamalı algoritma ile birleştirilmiştir. Ağ, karmaşık bir ağı daha basit bir ağa dönüştürmek için seri, paralel, kenar faktörleme ve delta-yıldız grafik dönüşümlerine dayalı birçok basitleştirme katmanından geçer. Basitleştirilmiş topoloji daha sonra klasik bir algoritma için girdi olarak kullanılır; burada iki uçlu güvenilirlik değerlendirmesi için bağlantı setleri. Algoritmayı doğrulamak ve hesaplama süresinde yapılan iyileştirme hakkında net bir vizyon vermek için birçok vaka çalışmasının simülasyonu gerçekleştirilir. 6 düğümlü 9 bağlantılı, 10 düğümlü 15 bağlantılı ve 30 düğümlü 41 bağlantılı ağlar değerlendirme aşamasındadır. Önerilen algoritmanın sonuçları, hesaplama süresi açısından bağ setleri algoritmasının (standart klasik algoritma) kullanımından kaynaklananlarla karşılaştırılmıştır. Algoritmaların MATLAB tarafından uygulanması, güvenilirlik hesaplama süresinde gözle görülür bir gelişme olduğunu göstermektedir. İyileştirme, kaynak-hedef çifti olarak seçilen ürüne, ağ topolojisi karmaşıklığına ve düğüm ve bağlantıların sayısına bağlıdır. Örneğin, 6 düğümlü ağ, emtia (2-4) için klasik bağ set algoritmasına kıyasla zaman hesaplamasında% 379'luk bir gelişme gösterirken, 10 düğümlü ağ için gelişme çok büyük. 30 düğümlü ağ durumunda, klasik algoritmalar çözümü bulmada başarısız olurken, önerilen algoritma, küçük basit ağlar için karşılaştırılabilir hesaplama süresi ile güvenilirliği bulmayı başarır.

The reliability of the communication network is used as one of the quality of service factors defining the availability and resilience of operating networks. Many classical algorithms exist but most of them fail to be applied for real-time reliability assessment in complex networks where the calculation load is increased in the function of the complexity. In this work, a new hybrid algorithm is proposed to resolve the problem of the two-terminal reliability evaluation for all kinds of networks (simple and complex), giving an exact solution. The algorithm is based on the combination of two classical reliability methods giving an efficient hybrid algorithm. Graph transformation method and tie sets methods are fused into multi stages algorithm. The network passes through many simplification layers based on series, parallel, edge factoring, and delta-star graph transformations to transform a complex network into a simpler network. The simplified topology is then used as input for a classical algorithm; here the tie sets for the two-terminal reliability evaluation. The simulation of many case studies are performed to validate the algorithm and to give a clear vision about the improvement made in computing time. A 6-node 9-link, 10-node 15-link, and 30- node 41-link networks are under evaluation. The results of the proposed algorithm are compared to those resulting from the use of tie sets algorithm (standard classical algorithm) in terms of computing time. The implementation of the algorithms by MATLAB shows a noticeable improvement in the time for reliability calculation. The improvement depends on the selected commodity as source-destination pair, the network topology complexity, and the number of nodes and links. For example, the 6-node network shows an improvement in time computing compared to classical tie-set algorithm of 379% for the commodity (2- 4) while for 10-node network the improvement is high. In the case of 30-node network, the classical algorithms fail to find the solution, while the proposed algorithm succeeds to find the reliability with computing time comparable to that for small simple networks.