Selbstentwickelte Modellierungswerkzeuge


Reliability and Resilience of Networks (ResiNet3)

Herr Patrick Buchhardt integrierte ausfallfähige Knoten in das Tool ResiNeT2 (s. unten) und überarbeitete das Benutzerinterface. Damit lassen nun Netze analysiert, bei denen sowohl Knoten als auch Kanten ausfallen können. Das ausführbare Progamm (.exe) kann hier heruntergeladen werden: ResiNet3.exe


Über das Internet nutzbare Java-Applets:

Resilience of Network Topologies 2 (ResiNeT2)

Herr Malte Sprotte erweiterte das unten genannte Tool ResiNeT, um zwei wichtige Funktionen:
Zum einen können nun Dateien importiert und exportiert werden, welche die Daten einer bestimmten Topologie bzw. des entsprechenden Graphen beinhalten. Damit können auch Graphen mit anderen Programmen generiert bzw. generell ausgetauscht werden. So lässt sich beispielsweise ein Graph mit dem Tool Pajek (http://pajek.imfm.si/) generieren, nach ResiNeT2 importieren und dort bzgl. seiner Zuverlässigkeit und Resilienz analysieren. Umgekehrt lässt sich ein in ResiNeT2 gezeichneter Graph nach Pajek exportieren, um dort z.B. in anderer Weise als in ResiNeT selbst dargestellt zu werden.
Zum anderen ist es nun möglich in einem Experiment eine Topologie mehrmals mit unterschiedlichen Kantenzuverlässigkeiten zu analysieren. So lassen sich beispielsweise mit einem Programmaufruf Berechnungen durchführen, bei denen die Komponentenzuverlässigkeit von 0.9 bis 0.99 in Schritten von 0.01 ansteigt.
Gerechnet wird mit dem schnellesten Algorithmus. Soll die Rechnung vergleichsweise mit mehreren unterschiedlichen Algorithmen erfolgen, z.B. um ihre Effizienz zu vergleichen (s. Masterarbeiten unten), so kann dies durch das Anklicken des Kästchens mit der Bezeichung "Compare 3 algorithms" zusätzlich ausgewählt werden.
Mit der neuen Version von ResiNet wurden bereits umfangreiche Zuverlässigkeitsuntersuchungen von Datennetzen durchgeführt, u.a. von lokalen Fest- und Funknetzen (LAN, WLAN, WDS) sowie von Weitverkehrsnetzen wie dem Deutschen Forschungsnetz.

Sprotte M., Vergleichende Untersuchung der Zuverlässigkeit und Resilienz verschiedener Netztopologien, Masterarbeit, Universität Hamburg, FB Informatik, 2014
Heidtmann K., Untersuchung der Zuverlässigkeit physikalischer LAN- und WLAN-Topologien, 2015

 

Resilience of Network Topologies (ResiNeT)

Es handelt sich hierbei um eine Weiterentwicklung des unten genannten Tools ReNeT von Malte Sprotte, das zusätzlich auch die Resilienz einer Netztopologie berechnet. Ferner wurde gegenüber ReNeT nun auch die Möglichkeit geschaffen, die gleiche Wahrscheinlichkeit für alle Komponenten nur einmal einzugeben.
Resilienz meint hier dem Mittelwert der Zuverlässigkeiten für alle Teilmengen K von Netzknoten gleicher Mächtigkeit, also k-Resilienz heißt Mittelwert über alle Teilmengen K von Netzknoten mit |K|=k. Anders ausgedrückt ist dies die Wahrscheinlichkeit dafür, dass k beliebige Knoten miteinander verbunden sind (Farley T.R., Colbourn C.J., Multiterminal Measures for Network Reliability and Resilience, 7th Intern. Workshop on the Design of Reliable Communication Networks, DRCN, 2009). In ResiNeT gibt man das k durch eine beliebige Menge K von schwarzen Knoten mit |K|=k an.
Sprotte M., Entwicklung und Anwendung eines Werkzeugs zur Berechnung der Resilienz von Rechnernetztopologien, Bachelorarbeit, Universität Hamburg, FB Informatik, 2012

Reliability of Network Topologies (ReNeT)

Dieses Werkzeug wurde von Yang Xiang und Christian Blechschmidt im Rahmen ihrer Studienarbeiten entwickelt. Im Rahmen ihrer Diplomarbeiten verglichen sie damit die Effizienz verschiedener Algorithmen zur Zuverlässigkeitsberechnung:
Xiang Y., Statistischer Vergleich von Verfahren zur Zuverlässigkeitsanalyse von Netztopologien, Diplomarbeit, Universität Hamburg, FB Informatik, 2001.
Blechschmitdt C., Statistischer Vergleich von Faktorisierungs- und Zerlegungsverfahren zur Zuverlässigkeitsanalyse von Netztopologien, Diplomarbeit, Universität Hamburg, FB Informatik, 2005.

Zahlreiche Systeme in Mathematik, Naturwissenschaft, Technik und insbesondere in der Informatik lassen sich durch Graphen modellieren. Besonders anschaulich sind Graphen im Bereich der Telematik, z.B. zur graphischen Darstellung der physikalischen oder logischen Topologien von Kommunikationsnetzen. Von Bedeutung ist in diesem Zusammenhang u.a. die Wahrscheinlichkeit, mit der die Netzknoten, z.B. Endsysteme oder Vermittlungsrechner (Router), einer Teilmenge K aller Netzknoten V miteinander verbunden sind und somit miteinander kommunizieren können. Dabei werden im sogenannten K-Graphen alle Knoten aus K durch einen schwarz ausgefüllten Kreis und alle übrigen Knoten durch einen weiß ausgefüllten Kreis dargestellt. Die Kanten des Graphen können in diesem Beispiel die Leitungen des Kommunikationssystems repräsentieren.

Berechnet wird also für einen einzugebenden Graphen mit einzugebenden Intaktwahrscheinlichkeiten für seine Kanten die Wahrscheinlichkeit dafür, dass alle Knoten aus der zu markierenden Teilmenge K aller Knoten des Graphen miteinander verbunden sind.

Literatur zum Thema u.a.

Heidtmann K., Zuverlässigkeitsbewertung technischer Systeme - Modelle für Zuverlässigkeitsstrukturen und ihre analytische Auswertung, Teubner, 1997, jetzt Springer Fachmedien, dort auch als eBook erhältlich http://link.springer.com/book/10.1007/978-3-322-95379-7

Heidtmann K., Statistical Comparison of Two Sum-of-Disjoint-Products Algorithm for Reliability and Safety Evaluation, 21st Intern. Conf. on Computer Safety, Reliability and Security, SAFECOMP 2002, Catania, 2002, in: Anderson S., Bologna S., Felici M. (Eds.), Computer Safety, Reliability and Security, LNCS Vol. 2434, Springer, Berlin, 2002. 

Heidtmann K., Methoden zur Zuverlässigkeitsanalyse von Rechnernetztopologien, Informatik-Spektrum, Band 17, Nr. 4, 1994

Bertsch R., Monney P.A., A generalization of the algorithm of Heidtmann to non-monotone formulas, Journal of Computational and Applied Mathematics, 76, 1, S. 55-76, 1996 DOI: 10.1016/S0377-0427(96)00089-1

Anders Jürgen M., Methods for the reliability analysis of complex binary systems, Humboldt-Universität zu Berlin, Sektion Mathematik, PhD. Thesis, 1992

Heidtmann K., Smaller sums of disjoint products by subproduct inversion, IEEE Transaction on Reliability, 38, 3, 1989



Während bei K-Graphen die Komponenten einer bestimmten fest vorgegebenen Teilmenge K der Menge N der Systemkomponenten intakt sein sollen, wird bei der folgenden Zuverlässigkeitsstruktur lediglich eine Anzahl k der n Systemkomponenten vorgegeben, die intakt sein sollen. Somit ist das System intakt für jede Teilmenge K, die mindestens k intakte Komponenten enthält, d.h. n >= |K| >= k mit n=|N|.

Reliability of Voting Systems (ReVoS)

Auswahlsysteme bilden eine besonders wichtige Klasse von Zuverlässigkeitsstrukturen, u. a. im Bereich der fehlertoleranten Rechen- und Kommunikationssysteme und insbesondere in verteilten Systemen. Dabei wird durch redundante Komponenten erreicht, dass ein Fehlverhalten einer beliebigen, jedoch entsprechend kleinen Auswahl von Systemkomponenten nicht mehr zwangsläufig zum Ausfall des Gesamtsystems führt. Von Bedeutung ist also die Wahrscheinlichkeit, mit der mindestens k der n Systemkomponenten intakt sind unter Vorgabe der Intaktwahrscheinlichkeiten der Komponenten und der Annahme der stochastischen Unabhängigkeit ihres Ausfallverhaltens.
Eine Anwendungsmöglichkeit besteht darin, durch eine Auswahl bzw. Abstimmung (voting, mindestens k von n Komponenten stimmen überein) fehlerhafte Komponenten zu überstimmen und damit deren fehlerhaftes Verhalten auszublenden, z. B. durch Mehrheitsentscheidung (majority voting). Man spricht in diesem Zusammenhang auch von Fehlermaskierung mit Hilfe einer k-von-n Zuverlässigkeitsstruktur (k-out-of-n structure).
Von besonderer Bedeutung ist das Entscheidungskriterium der absoluten Mehrheit, dabei ist k gleich einer natürlichen Zahl grösser oder gleich n/2. In vielen Fällen wird die Redundanz durch n-fache Vervielfältigung (n-fache Replikation, N Modular Redundant, NMR) einer Komponente hergestellt, insbesondere bei verteilten Systemen liegt eine Anwendung durch die Replikation von Dateien und Prozessen sowie durch Verteilen der Kopien auf unterschiedliche Netzknoten nahe. Besonders häufig werden 2-von-3 Systeme verwendet, die auch als TMR-Systeme (Triple Modular Redundant) bezeichnet werden.

Ein allgemeinere Klasse von Zuverlässigkeitsstrukturen bilden die k-bis-l-von-n Systeme (k-to-l-out-of-n structure, Heidtmann, 1981). Sie bestehen aus n Komponenten und sind genau dann intakt, wenn mindestens k und höchstens l der n Systemkomponenten intakt sind. Ist l gleich n, so liegt ein k-von-n System vor. Somit sind die k-von-n Systeme in dieser Klasse vollständig enthalten. Aufgrund ihrer regelmäßigen Zuverlässigkeitsstruktur lassen sich Systeme aus dieser Klasse leicht beschreiben und ihre Zuverlässigkeitskenngrößen unter der Annahme der stochastischen Unabhängigkeit sehr effizient berechnen, z. B. mit dem vorliegenden, von Birger Asmus in seiner Studienarbeit entwickelten Werkzeug ReVoS. Deshalb werden sie häufig auch zur Approximation komplexerer Systeme herangezogen.

Literatur zum Thema u. a.
Heidtmann K., Zuverlässigkeitsbewertung technischer Systeme - Modelle für Zuverlässigkeitsstrukturen und ihre analytische Auswertung, Teubner, 1997, jetzt Springer Fachmedien, dort auch als eBook erhältlich http://link.springer.com/book/10.1007/978-3-322-95379-7
Kuo W., Zuo M.J., Optimal Reliability Modeling: Principles and Applications, Wiley, 2002
Barlow R.E., Heidtmann K.D., Computing k-out-of-n System Reliability, IEEE Transactions on Reliability, 33, 4, 1984
Heidtmann K., A class of noncoherent systems and their reliability analysis, 11th Intern. Symposium on Fault-Tolerant Computing, FTCS-11, Portland/USA, 1981



Performance, Reliabiliy and Quality of Service (QoS)Evaluation of Videocommunication (ViQoS)

Bei der Videokommunikation über Paketvermittlungsnetze kann die Qualität der vom Empfänger dargestellten Bewegtbildsequenz beeinträchtigt werden durch Störung, Verlust oder nicht rechtzeitiges Eintreffen der zu übertragenden Datenpakete. Das Ausmass dieser Beeinträchtigung hängt u.a. von der Codierung und Komprimierung der zu übertragenden Bilddaten ab und lässt dich mit dem vorliegenden Werkzeug analytisch und simulativ untersuchen. Dabei werden die Zusammenhänge zwischen den Codierungs- und Komprimierungsparametern beim Sender und der Bildqualität beim Empfänger in Form von Wahrscheinlichkeiten für Bildverluste als Leistungs-, Zuverlässigkeits- oder Verlässlichkeitskenngrösse quantitativ bestimmt. Dabei wird ein Bild als verloren gewertet, wenn mindestens eines seiner Datenpakete verloren geht.

Ausführliche Darstellung in: Heidtmann K., Wolfinger B., Analytische Leistungsbewertung von Videokommunikation gemäss H.261 über verlustbehaftete Paketvermittlungsnetze, 10. GI/ITG-Fachtagung über Messung, Modellierung und Bewertung von Rechen- und Kommunikationssystemen MMB'99, Trier, September 1999, 87-104 (0.5 MB Postscript)
 
 

Bildcodierung