Performance Message Sequence Chart – Sprache zur Leistungsvorhersage mittels der Generierung eines Prototypen im Kontext des Protokollentwurfs mit SDL und MSC

Language
de
Document Type
Doctoral Thesis
Issue Date
2008-01-31
Issue Year
2007
Authors
Kerber, Kai Lennard
Editor
Abstract

During the development of communication systems, the languages MSC and SDL are used for the standardisation, development and implementation of protocols. Both languages are an essential part of today’s popular development methodologies with the UML language. In MSC specifications, the system is described by examples while in SDL specifications it is described completely by means of communicating automata. Depending on the point of view, communication systems are either real-time systems or resources used by different users. In either case, the functional and temporal behaviour is important. Thus, the temporal behaviour of different design possibilities must be evaluated in a model-based manner in early phases of the development. This also applies to the system design phase, where the architecture of the system is defined. The aim of this thesis is to analyse the temporal behaviour of the system subject to different variants of the architecture. To this end, a new concept is proposed with a view to generating an executable machine code from specified example runs. This thesis uses two existing approaches for the transformation of MSC and SDL specifications: On the one hand, different research groups work on correct transformations of MSC specifications to SDL specifications. On the other hand, SDL specifications have a long tradition in automated code generation for the target system. Based on these approaches the generation of a performance prototype from specified example runs is the obvious choice. The main idea for the analysis of the temporal behaviour of the system by means of the generation of a prototype is to use these approaches and add performance-specific extensions with functions that are called up from the prototype during run-time. The description of the systems behaviour includes two aspects: the description of the application and the description of the environment. They define the load that is executed by the system. The description of temporal characteristics of the system is formulated through requirements to be met by the system. The prototype is executed on the target platform or an emulator. Thus, the prototyping approach has the advantage that a separate machine model, which is a model of the hardware and system software, is not needed. The run of the prototype generates an event trace which can be evaluated automatically by means of the formulated requirements. This thesis proposes a concrete language approach Performance Message Sequence Chart (PMSC). The approach integrates the load description and the requirements description within a single document. The algorithms required for the transformation and the analysis are described. A fundamental problem associated with the described approach is discussed in the thesis: The automatically generated prototype can show unspecified behaviour. This behaviour can result from the known problem that the specification is not safely realizable, or it can be attributable to the distinction of message content and message type that becomes important when moving from the input action in MSC to the input action in SDL; this implies the introduction of additional deadlock states in the SDL specification and therefore in the prototype as well. During the analysis of the measured trace, the formulated requirements are added to the MSCs for the load description. A path through the MSC specification, that is consistent with the measured event trace must be found. Thereby only iterations of loops that can be derived from the measured event trace are considered. The evaluation of given requirements is achieved by a replay of the MSC specification in a simulation environment. In principle, the analysis exhibits a very high worst-case complexity where the run time grows exponentially with the trace length. With a favourable specification style, this complexity can be reduced so that the run time grows only quadratically with the trace length. The more general problem of considering all possible loop iterations is undecidable.

Abstract

Im Telekommunikationsbereich werden die Sprachen MSC und SDL zur Normierung, Entwicklung und Implementierung von Protokollen eingesetzt. Beide Sprachen bilden einen wesentlichen Bestandteil der heute so populären UML-Entwicklungsmethodik. In MSC-Spezifikationen wird das System mit Hilfe von Beispielabläufen beschrieben, in SDL-Spezifikationen wird es vollständig mit kommunizierenden Automaten beschrieben. Kommunikationssysteme sind je nach Sichtweise zum einen Echtzeitsysteme und werden zum anderen von verschiedenen Benutzern gemeinsam genutzt. Deshalb ist neben dem funktionalen auch das zeitliche Verhalten wesentlich. Entwurfsmöglichkeiten müssen bezüglich ihres Zeitverhaltens bereits in den frühen Entwicklungsphasen modellgestützt bewertet werden. Dies gilt auch für die Phase des Systementwurfs, in dem eine Architektur festgelegt wird. Ziel dieser Arbeit ist es, das Zeitverhalten des Systems in Abhängigkeit von verschiedenen Architekturvarianten in dieser Phase zu analysieren. Dazu wird ein neues Konzept vorgestellt, bei dem ausführbarer Maschinencode aus spezifizierten Beispielabläufen erzeugt wird. Die vorliegende Arbeit greift zwei bestehende Ansätze zur Transformation von MSC- und SDL-Spezifikationen auf: Einerseits wird von verschiedenen Forschergruppen eine korrekte Transformation von MSC-Spezifikationen auf SDL-Spezifikationen untersucht. Andererseits werden SDL-Spezifikationen seit langem als Ausgangspunkt zur Codegenerierung für das Zielsystem genutzt. Aufgrund dieser Ansätze ist die Erzeugung eines Prototypen aus Beispielabläufen nahe liegend. Der grundlegende Gedanke für die Analyse des Zeitverhaltens des Systems mit Hilfe der Prototypengenerierung ist es, auf der Grundlage der oben genannten Ansätze die spezifischen Erweiterungen für die Leistungsbewertung auf Funktionen abzubilden, die zur Ausführungszeit des Prototypen ablaufen. Die Beschreibung des Verhaltens des Systems beinhaltet zwei Aspekte: die Beschreibung der Anwendung und die Beschreibung der Umgebung. Sie definieren die Last, die das System ausführen muss. Die Beschreibung zeitlicher Eigenschaften des Systems wird durch Anforderungen an das System formuliert. Der Prototyp wird auf der Zielplattform oder einem Emulator ausgeführt. Deshalb hat der Ansatz, einen Prototypen zu generieren, den Vorteil, dass ein Modell der Maschine, also der Hardware und der Systemsoftware, nicht definiert werden muss. Die Ausführung des Prototypen erzeugt eine Messspur, die mit Hilfe der formulierten Anforderungen automatisiert bewertet werden kann. Die Arbeit stellt einen konkreten Sprachansatz Performance Message Sequence Chart (PMSC) vor. Der Ansatz integriert die Spezifikationen für die Lastbeschreibung und die Anforderungsbeschreibung in einem Dokument. Die für die Transformation der MSC-Spezifikation in eine SDL-Spezifikation und die für die Analyse der Messspur benötigten Algorithmen werden dargestellt. Mit diesem Ansatz ist das grundsätzliche Problem verbunden, dass der erzeugte Prototyp neues, nicht spezifiziertes Verhalten zeigen kann. Dies ist zum einen auf das bekannte Problem der nicht sicher realisierbaren Spezifikation zurückzuführen, zum anderen auf die Unterscheidung von Nachrichteninhalt und Nachrichtentyp, wie sie beim Übergang von der MSC-Spezifikation in die SDL-Spezifikation zu unterscheiden sind. Aufgrund der Unterscheidung werden zusätzliche Verklemmungszustände in die SDL-Spezifikation und damit in den Prototypen eingeführt. Während der Analyse der Messspur werden die formulierten Anforderungen in die MSCs der Lastbeschreibung eingefügt. Ein zur Messspur konsistenter Weg durch die MSC-Spezifikation, der die Anforderungen erfüllt, muss bestimmt werden. Dabei werden nur solche Schleifendurchläufe betrachtet, die beobachtet wurden. Die Überprüfung eines konsistenten Weges wird durch eine wiederholte Ausführung der MSC-Spezifikation in einer Simulationsumgebung erreicht. Die Analyse besitzt grundsätzlich eine sehr hohe Worst-Case-Komplexität, bei der die Analysezeit exponentiell mit der Länge der Messspur wächst. Bei einem günstigen Spezifikationsstil kann diese Komplexität auf eine quadratisch mit der Spurlänge wachsende reduziert werden. Das allgemeinere Problem, bei dem während der Analyse alle möglichen Schleifendurchläufe betrachtet werden, ist unentscheidbar.

DOI
Document's Licence
Faculties & Collections
Zugehörige ORCIDs