Messung, Modellierung und Bewertung von Rechensystemen

In order to follow the evolution of the computer systems, the specialists in performance evaluation have been forced to develop more and more complex models. In general, the exhibited models are discrete models and use the notions of the queueing theory. It is indeed very natural to associate the resources of a computer system to the servers of the theory, and the software processes to the customers.

Es wird ein Verfahren vorgestellt, mit dem die Wartezeitverteilungen in G/G/1-Systemen bei mittlerer bis hoher Verkehrsintensität näherungsweise berechnet werden können, der Reihe nach für jeden Kunden, ausgehend von einer Verteilung für die Wartezeit des ersten Kunden, also nicht nur im statistischen Gleichgewicht. Angewendet werden die Prinzipien der maximalen Entropie und der minimalen Kreuzentropie. Die dafür benötigten Erwartungswerte ermittelt das Verfahren selbst, sie brauchen nicht mit anderen Näherungsverfahren bestimmt zu werden. Vergleiche mit bekannten Werten zeigen, daß für die berechneten Wartezeitverteilungen drei bis fünf Momente gut mit den exakten Zahlen übereinstimmen.

A simple M/M/1/k queue with impatient customers is presented as a model for communications systems operating under overload conditions. The performance analysis and optimal control problem for this model are discussed. An efficient algorithm for computing the optimal control is presented along with numerical results.

Diensteintegrierende Nachrichtennetze — Grundlagenprobleme der Modellierung und des Traffic Engineering

Für die Planung von Systemen mit Rufabweisung sind Wiederholrufe ein schwer erfaßbares Phänomen. Sie entstehen durch das Verhalten abgewiesener Rufer, binnen kurzer Zeit weitere Versuche zur Belegung eines Kanals zu unternehmen.

In dieser Arbeit der Effekt von Wiederholrufen auf die Leistung von Verlustsystemen ermittelt. Hierzu werden Systeme, in denen Rufwiederholung auftritt, zum einen durch ein Modell ohne, zum anderen durch ein Modell mit expliziter Berücksichtigung der Wiederholrufe dargestellt. Dabei wird besonderen Wert darauf gelegt, daß beide Modellierungsansätze korrekt verfolgt werden. In diesem Fall läßt der Vergleich der Ergebnisse beider Modelle eine Abschätzung der Auswirkung von Wiederholrufen zu. Es wird gezeigt, daß dieser Effekt erheblich ist. Ferner wird eine starke Sensibilität der Ergebnisse bzgl. der Parameter, die das Wiederholerverhalten beschreiben, nachgewiesen. Die Konsequenzen der Ergebnisse für die Anwendung von Verlustmodellen in der Praxis werden kurz aufgezeigt.

Die Beobachtung (das Monitoring) der inneren Abläufe in Multiprozessor- und Multicomputer-Systemen ist ein hervorragendes Werkzeug, um die Ursachen für die extern festgestellte Gesamtleistung solcher Systeme zu analysieren und damit die Voraussetzungen für eine Leistungsverbesserung zu schaffen. Im vorliegenden Papier wird ein Monitorsystem vorgestellt, das speziell für (auch räumlich verteilte) Multiprozessor- und Multicomputer-Systeme entworfen wurde. Seine wesentlichen Eigenschaften sind die Kombination von verteilter und zentraler Instrumentierung des Objektsystems, die systemweite Ermittlung von Ereignisreihenfolgen und die quellbezogene Auswertung von Ereignisspuren. Neben dem globalen Konzept werden vertiefende Untersuchungen dargestellt, und es wird von ersten Meßerfahrungen berichtet.

Mit der Zahl der Rechnernetze steigt auch die Notwendigkeit für “intelligente” Systeme, die die komplexen und undurchsichtigen Vorgänge in einem Netz offenlegen und analysieren können. Aufgrund der Weiterentwicklung in Technologie und Standardisierung darf ein derartiges Diagnosesystem allerdings nicht nur auf ein spezielles Kommunikationssystem beschränkt sein, sondern muß vom Benutzer an unterschiedliche Kommunikationsprotokolle und -hierarchien anpaßbar sein. Im folgenden wird die Konzeption und Realisierung eines Datenmonitors vorgestellt, der es ermöglicht, “Protokollwissen” benutzerfreundlich zu integrieren, insbesondere Wissen über den Aufbau und die Struktur der einzelnen Protokolldateneinheiten. Hierzu wurde die Sprache FAN.l (Frame Analyzing Notation One) in Anlehnung an die Notation ASN.1 (Abstract Syntax Notation One) der internationalen Standardisierungsorganisation (ISO) entworfen und für die universelle Analyse von Paketstrukturen und Protokollparametern implementiert. Auf FAN.l aufbauend wurden komplexe Meß-, Auswertungs- und Analysefunktionen realisiert, die es, durch Angabe beliebiger Prädikate über die definierten Paketstrukturen, ermöglichen, das dynamische Ablaufgeschehen in einem groβen verteilten System transparent zu machen. Der hier beschriebene Datenmonitor ist Bestandteil des LAN Protocol Testers B5100 der Firma Siemens.

Messungen der Verteilungsfunktionen stochastischer Prozesse werden für die Modellierung und Analyse von Datenkommunikationssystemen benötigt. Die empirischen Verteilungsfunktionen müssen in eine für die Verkehrstheorie geeignete mathematische Beschreibung überführt werden, die die Anwendung bekannter Analysemethoden erlaubt. Im folgenden werden Anforderungen an ein Approximationsverfahren hergeleitet und zwei bereits bekannte Verfahren erläutert. Dann wird das neue Approximationsverfahren MEDA¹ vorgestellt, das diese verkehrstheoretischen Anforderungen erfüllt. Es verwendet eine spezielle Erlangmischverteilung als Approximierende. Die ersten drei empirischen Momente werden exakt abgeglichen und alle vorhandenen Stützstellen zur Näherung des Verteilungsfunktionsverlaufs herangezogen.

Anschließend wird ein Umrechnungsalgorithmus hergeleitet, mit dem die Erlangmischverteilung in eine äquivalente Coxverteilung überführt werden kann. Dadurch wird sie bereits etablierten Analysewerkzeugen zugänglich.

Sowohl MEDA als auch der letztgenannte Algorithmus wurden in PASCAL realisiert.

Choosing Ada as a base language for the process view of simulation, one would like to adopt the Ada rendezvous for process interaction. This paper investigates the implications of the rendezvous in the context of simulated time. To avoid the danger of deadlock (as exhibited by some proposed systems), a very thorough control of the rendezvous is shown to be necessary. A suitable simulation mechanism is presented and proven. But judged by the ensuing costs the rendezvous is considered to be no attractive choice for general simulation purposes.

Considering methods, this paper uses and contributes to the “space-time view” (L.Lamport) of processes: processes are sequences of actions, and simulated time is a mapping of actions to numerical values.

Queueing networks which contain finite capacities have proved useful in modeling actual computer systems and communication networks. The finite capacity of stations introduces blocking events which should be considered in the performance evaluation. Specifically, we shall examine the effects of rejection blocking upon queueing networks. Rejection blocking is defined in the following manner. Upon completion of its service of a particular station’s server, a job attempts to proceed to its next station. If, at that moment, its destination station is full, the job is rejected. The job goes back to the server of the source station and immediately receives a new service. This is repeated until the next station releases a job and a place becomes available. In the first part of this work the well known exact product form solution for the equilibrium state probabilities is presented for closed rejection blocking networks which have reversible routing. An algorithm is given for computation of performance measures in reversible networks with rejection blocking. In the second part nonreversible networks with rejection blocking are analyzed. The analysis is based on the transformation of the state space of a blocking queueing network into an equivalent state space of a nonblocking network with infinite station capacities. It is shown that the state spaces of both systems are isomorphic under a given condition. Markov processes describing the evolution of both networks over time have the same structure. This leads to the product form solution for blocking networks. Based on product form solution new formulae are given for the exact computation of performance measures.

An algorithmic method for computing the probability vector of finite irreducible Markov chains is developed. The block elimination scheme used is especially well suited for highly structured and/or sparse transition matrices. Special variants for block Hessenberg and tridiagonal matrices often occurring in queueing theory are derived. The algorithm is then applied to the embedded Markov chain describing the queue length in a discrete-time queue with state-dependent arrival rates.

Synchronized queueing networks (SQN) are a new type of models, which allow the analysis of queueing systems subject to synchronization constraints. SQN-models originate from traditional queueing networks which have been enlarged by a new type of nodes. These nodes, called counters, can be viewed as synchronization primitives, which are used by the tasks moving through the network. Due to this combination of synchronization and queueing features SQN-models are a new approach towards the unified representation of areas which have been studied separately for a long time.

The usability of this approach is demonstrated by the evaluation of models for parallel task systems and for serialization delays due to the presence of critical regions. Evaluation of SQN-models have been performed with the numerical modelling tool NUMAS, which provides various facilities for model construction and solution. In particular the use of aggregation methods, either for speeding up the convergence of iterative algorithms or for an “a priori” off-line analysis of queueing subnetworks embedded in the SQN-model, are efficient techniques to reduce the costs of an quantitative evaluation.

Features for the evaluation of SQN-models have been integrated with the modelling environments of the computer manufacturers NIXDORF CAG and SIEMENS AG.

This paper discusses single and multiple token rings, describes major aspects of their architecture, and discusses in detail the performance issues arising in the design of such local area networks. Following a survey of analytical queueing models to describe the basic token-ring operation, three topics are discussed in detail: 1) The IEEE 802.5 Token Ring and its performance; 2) performance aspects of the ANSI Fiber Distributed Data Interface (FDDI) token ring, and 3) performance questions arising in the interconnection of token-ring networks.

Die Kanalzugriffsverfahren CSMA/CD(Ethernet), Token-Bus, Token-Ring und Slotted-Ring werden hinsichtlich ihres Verhaltens bei Poisson-Ankunftsprozessen gegenüber unterbrochenen Poisson-Ankunftsprozessen untersucht. Für alle Kanalzugriffsverfahren werden Modelle vorgestellt, die simulativ untersucht werden.

This paper presents the study of a multi-hop packet radio network with spatial randomly located stations using the S-ALOHA protocol. We evaluate the one-hop throughput for the case of different transmission probabilities for newly generated and previously collided packets. It is shown that the impact of the retransmission probability on throughput is comparable for fully-connected and multi-hop networks. Our main interest, however, is the evaluation of the mean backlog-time of a packet, i.e. the mean number of slots between the first transmission attempt and the successful transmission of a packet. We show that multi-hop networks have better stability properties than fully-connected networks because the number of users who can interfere with each other is very small. Further, the influence of the station’s mobility on the mean backlog-time is treated.

Leistungsfăhige SpezialSysteme für die Logik-Simulation werden mehr und mehr benŏtigt, um den Zeitaufwand für die funktionale Evaluierung von VLSI-Entwürfen gering zu halten. Der Bericht skizziert die Leistungsbewertung des Munich Simulation Computer (MuSiC), eines hochparallel organisierten Ereignisflußrechners für die schnelle Simulation digitaler Systeme. Zwecks Überprüfung der getroffenen Leistungsaussagen ist ein in OCCAM formuliertes und auf einem Multi-Transputernetz implementiertes Modell in Entwicklung. Konzepte dieser Modellierung werden vorgestellt.

Das BS 2000 ist das Betriebssystem der Großrechner der Firma Siemens. Eine wichtige Funktion des BS 2000, das Catalog Management System (CMS) war Gegenstand einer mehrstufigen Simulationsuntersuchung von Dezember 1985 bis Mai 1987. Das CMS verwaltet die Charakteristika aller gültigen BS 2000-Dateien in einem Systemkatalog. Jeder Datei ist ein Eintrag im Systemkatalog zugeordnet, der alle wesentlichen Informationen über die Datei (Dateiname, Schutzeigenschaften, Zuordnung von logischen und physikalischen Seiten der Datei etc.) enthält. Der Zugriff auf Einträge im Systemkatalog ist nur über das CMS möglich. Da Benutzer-Tasks während ihres Zugriffs auf den Systemkatalog unterbrechbar sind, existieren Sperrmechanismen, um Inkonsistenzen in Katalogeinträgen und Verklemmungen beim Zugriff zu vermeiden. Aufgrund vorhersehbarer Mehrbelastung der Betriebssystemkomponente CMS durch eine geplante Vervielfachung der zulässigen Taskanzahl und um den Anforderungen künftiger schnellerer Anlagen gerecht zu werden, wurde eine weiterentwickelte CMS-Version mit neuem Sperrmechanismus entworfen. Die Sperren sollen möglichst kurz gehalten werden bzw. möglichst wenig Einträge blockieren.

Dieser Beitrag beschreibt ein Konzept und die Realisierung eines Prototyps zur interaktiven, wissensbasierten Unterstützung von Anwendern in den verschiedenen Phasen eines Modellierungsprozesses. Das vorliegende Konzept geht von der Annahme aus, daß in zunehmendem Maße Systemspezialisten aus verschiedensten Anwendungsbereichen detaillierte Systemanalysen als Grundlage für Entscheidungen benötigen, die den praktischen Einsatz dieser Systeme, deren Entwurf, Auswahl und Modifikation betreffen. Es wird davon ausgegangen, daß die meisten dieser Systemspezialisten nur über Grundkenntnisse im Bereich der Systemanalyse verfügen, einen mangelnden Überblick über Modellierungsmethoden und -Werkzeuge besitzen, aber andererseits mit zunehmender Verbreitung von PC’s einen direkten Zugang zu leistungsfähigen Verarbeitungssystemen haben.

Ausgehend von diesen Annahmen berichtet dieser Beitrag über die Zielsetzung, den aktuellen Realisierungsstand und eine typische Anwendung unseres INT³- Konzepts: über eine interaktive, intelligente und integrierte Modellierungsumgebung, die z. Zt. in einer Standard-PC-Umgebung (IBM-XT/AT) schrittweise realisiert wird. Neben einer Beschreibung des konzeptionellen Ansatzes konzentriert sich dieser Beitrag auf die Demonstration des Einsatzes des INT³-Prototyps zur schrittweisen Lösung eines typischen Leistungs- und Kapazitätsplanungsproblems für ein Rechensystem im Dialogbetrieb.

Performance, data integrity, and user-friendly access to data are considered to be cardinal properties of database management systems (DBMSs). But performance will steadily receive more attention as more interactive application are designed and implemented for almost all domains of our life. (According to some rumors, DBMS is sometimes said to be another name for performance problems). In this paper, we discuss specific performance problems of centralized ‘conventional’ DBMSs, DB/DC systems, and DBMSs for ‘nonstandard’ applications (e.g. engineering, office, etc.). Then, a short survey attempts to sketch the solutions achieved and the problems remaining for the most important performance-critical functions/components in DBMSs. Finally, some aspects and mechanisms are discussed how database management system performance could be controlled and improved by measurement/monitoring techniques and subsequent adaption of DB-schema design.

We present a detailed simulation model for a distributed database system, which includes the following components: communication system, concurrency control, buffer management, recovery, and deadlock detection. The simulation is carried out using GPSS-Fortran and is driven by a reference-string recorded from a real database application. Reference-strings reflect the real reference patterns more accurately than random references. Three concurrency control schemes and two buffer replacement policies are compared. Due to the very detailed level of investigation in our approach, we yield a thorough understanding of the performance aspects of both buffer management and concurrency control in a distributed database environment.

Die Analyse von Warteschlangennetzen konnte in den letzten Jahren einige Fortschritte verzeichnen, jedoch erweist sich die Behandlung allgemeiner geschlossener Netze noch immer als schwieriges Problem. Da Produktformlösungen nur für spezielle Netztypen angegeben werden können und numerische Verfahren sehr aufwendig sind, gewinnen approximative Methoden stärker an Bedeutung. In der vorliegenden Arbeit wird ein funktionales Konzept zur Charakterisierung von Wartesystemen beschrieben, welches nicht nur eine relativ einfache approximative Analyse allgemeiner geschlossener Warteschlangennetze ermöglicht, sondern auch bei der Optimierung von Leistungsgrößen erfolgreich einsetzbar ist. Die einzelnen Knoten des Systems werden hier durch den Zusammenhang zwischen der mittleren Anzahl der Aufträge in der Station und dem Durchsatz charakterisiert. Ein Vergleich mit Ergebnissen aus der Mittelwertanalyse, beziehungsweise mit Simulationsergebnissen zeigt die Brauchbarkeit der gefundenen Lösungen.

Die Aggregierung separabler Teilnetze zu flußäquivalenten Ersatzstationen mit populationsabhängigen Bediengeschwindigkeiten und deren Einbettung sowohl in separabler als auch in nicht-separabler Umgebung wird in der Modellierung breit eingesetzt. Bekanntlich liefert die Verwendung von Aggregaten im Falle von separabler (bzw. nicht-separabler) Umgebung exakte (bzw. approximative) Mittelwerte(l) von Leistungsmaßen. Diese Methode der Ersatzdarstellungen verfälscht aber sogar in rein separablem Kontext die Verweilzeitverteilung(l) der Aufträge sowohl am betrachtetem Teilnetz als auch in der Umgebung. Diese Arbeit untersucht durch numerische Analyse geeigneter reduzibler Markovketten, wie sich die Variation diverser Netzparameter auf die Paßgüte der resultierenden Verweilzeit-Verteilungen auswirkt. Zur Verbesserung der Paßgüte werden, alternativ zur üblichen exponentiellen Ersatzstation, Cox-Stationen und Ersatzdarstellungen in Form von Zwei-Stationen-Netzen erprobt.

Im industriellen Alltag treten oft Aufgabenstellungen auf, die eine Analyse des Verhaltens eines Rechensystems bei vorgegebenen Durchsätzen der verschiedenen Anwendungen oder deren Verhältnissen zueinander erfordern. Die Modellierung als geschlossenes Netz erlaubt normalerweise diese Vorgaben der Durchsätze nicht. Die Ergänzung eines geschlossenen Warteschlangennetzwerkes um eine Verzögerungsstation ermöglicht jedoch die Einhaltung dieser Vorgaben in vielen Fällen. Ein aus der Bard/Schweitzer-Approximation abgeleiteter Algorithmus zur Berechnung der erforderlichen Verzögerungszeiten der verschiedenen Ketten wird angegeben.

Advances of the applications of artificial intelligence in modelling and simulation are viewed within the continuum of tool making. To have a proper perspective, the spectrums of the developments of physical tools as well as abstract tools such as software tools and modelling and simulation tools are presented. Then some promising directions for advanced research are highlighted under the following categories: