Computer communication network reliability: Evaluation of two-terminal reliability

Abstract

Bilgisayar ağlarının güvenilirliği, hemen hemen tüm hassas uygulama alanlarının yönetilmesi ve gerçeklenmesinde önemli bir rol oynamaktadır. Ağların boyutu sürekli arttığından dolayı, uzun işlem yürütme zamanı sorunu, ciddi bir mesele haline gelmektedir. İstenen ağ topolojisini elde etmek için, güvenilirliği her aşamada hızlı bir şekilde değerlendirmemiz gerekmektedir. Bu nedenle, hızlı ve yanlışsız bir algoritma çok değerlidir. Bu çalışmada, bu görevi verimli bir şekilde yerine getirmek üzere bir algoritma önermekteyiz. Temel olarak değerlendirilecek bazı ağ güvenilirlik parametreleri için iki adımın atılması gerekmektedir.İlk olarak ağ topolojisi, kısa bir sürenin elverişli olmasından ötürü, bir sorun olarak kabul görülmeyen bir güvenilirlik formülüne dönüştürülürken, ikinci adımda ağın güvenilirliği, sayısal olarak hesaplanmaktadır. Önerilen algoritma, bir ağ içindeki tüm nesnelerin güvenilirliğini ölçmek üzere `en kısa bağlantı dizileri` (minimal tie-set) ile `grafik indirgeme` (graphic reduction) tekniklerine dayanan, bir `çok aşamalı melez algoritmadır (ÇMRT)` (multistage hybrid algorithm (MHRT)). Hem `çift yönlü` (bidirectional) hem `tek yönlü` (unidirectional) bağlantılar dikkate alınabilir. Söz konusu ağın şekli veya boyutu ile ilgili bir kısıtlama yoktur. `En kısa yolları` (minimal paths) takip etmek için yeni bir yaklaşım ortaya konmaktadır. Meşhur `Geri İzleme` (Backtracking), `Kenar Değiştirme` (Edge Replacement) ve `Dolamsız Yol Birleşimi` (Acyclic Path Mergence) algoritmaları ile karşılaştırıldığında, daha az belleğe ihtiyaç duymaktadır. `Matris Çarpımı` (Matrix Multiplication) ve `Düğüm Giderme` (Node Removal) ile karşılaştırıldığında, `Boolean Cebiri` (Boolean Algebra) uygulamasına gerek duymamaktadır.

Reliability of computer networks plays essential role in managing and performing almost all thesensitive applications fields. Since networks dimension is increasing continually, the problem oflong execution time becomes serious issue. In order to get the desired network topology, weneed to evaluate the reliability at every phase quickly. Hence, fast, accurate algorithm is highlyappreciated. That's way in this work we propose an algorithm to do this task efficiently. Forsome network reliability parameters to be basically evaluated there are two steps have to betaken. Firstly, interpreting the network topology into a reliability formula which does notconsidered to be a problem, since a little time is adequate to perform. Whereas, in the secondstep the reliability of a network is numerically computed. The proposed algorithm is a multistagehybrid algorithm (MHRT) based on graph reduction techniques with the minimal tie- setto measure the reliability of all commodities within a network.Both directional and unidirectional links can be considered. There are no restrictions on the sizeor the shape of handled network. A new approach has been introduced for tracing all minimalpaths. Compared with the well-known algorithms Backtracking, Edge Replacement, and AcyclicPath Mergence; it needs less memory. And comparing with Matrix Multiplication, and NodeRemoval; it does not require the application of Boolean algebra.