1. Einleitung

Dieser Themenblock des Praktikums Kommunikationsnetze beschäftigt sich mit ARQ-Protokollen.

Im vorherigen Block des Praktikums Kommunikationsnetze wurden Eigenschaften und Parameter der physikalischen Schicht untersucht. Es wurden wichtige Eigenschaften des physikalischen Kanals auf der Bit-Ebene und der Ebene eines Rahmens (Frames) analysiert. Es wurde auch der Einfluss von Leitungscodes (“Non Return to Zero” (NRZ) und Manchester Codierung) und eines Scramblers auf die BER gezeigt. Mit den Kenntnissen der Eigenschaften des physikalischen Kanals wurden anschließend die Grundvoraussetzungen geschaffen, ein Protokoll zu konstruieren: Einzelne Bits wurden zu Rahmen zusammengefasst. Ein Rahmen besitzt die Eigenschaft, durch eine Prüfsumme Bitfehler zu erkennen (“Error Detection”). Eine wichtige Eigenschaft des Empfängers - sich auf den empfangenen Datenstrom zu synchronisieren - beeinflusst die Verlustrate von Rahmen.

In diesem Block sollen Protokolle entwickelt werden, die eine fehlerfreie Übertragung von Rahmen zwischen einem Sender und einem Empfänger gewährleisten. Hierzu wird ein Einblick in den Prozess zum Erstellen von Protokoll-Software gegeben. Dazu wird der Umgang mit der häufig benutzten Entwicklungsumgebung SDT vorgestellt und Erfahrungen mit dem Einsatz einer formalen Beschreibungssprache (SDL) für die Spezifikation von Kommunikationsprotokollen vertieft. Der komplette Entwicklungsprozess für eine Protokollsoftware lässt sich grob in folgende Phasen einteilen:

Spezifikation und Entwurf,
Simulation,
Validierung (Überprüfung),
Implementierung in eine Laufzeitumgebung (Plattform) und
Leistungsanalyse des Protokolls.

SDT unterstützt fast alle Phasen der Protokollentwicklung mit passenden Werkzeugen. Die einzige Ausnahme ist die Leistungsanalyse des Protokolls. Sie wird effektiv nur durch Simulationstools oder in einer realen Laufzeitumgebung durchgeführt. Die Phasen lassen sich oft zeitlich nicht genau voneinander abgrenzen, da man beim Aufdecken von Fehlern und Abweichungen von der Vorgabe zu früheren Arbeitsschritten zurückkehren muss.

Zunächst wird im Rahmen dieses Blocks die Protokolltechnik “Send-and-Wait” behandelt. Anschließend wird das “Go- Back-N”-Protokoll näher untersucht. Diese Protokolle gehören zur Gruppe der ARQ-Protokolle. ARQ-Protokolle besitzen eine Fehlererkennung (Error Detection) und -behebung (Error Control), d.h. sie fordern bei erkannten Fehlern automatisch die Wiederholung der letzten Übertragung an. In der Art und Weise wie sie das tun, unterscheiden sich diese Protokolle, was zum Teil erhebliche Auswirkungen auf die “Restfehlerwahrscheinlichkeit” hat. Benutzt werden ARQ-Protokolle immer dann, wenn es um zuverlässige Datenübertragungen zwischen Peer-Entities geht. Sie werden daher meistens in der Link- oder in der Transport-Ebene innerhalb des OSI Modells der ISO eingesetzt. Inwieweit und unter welchen Bedingungen dieses “zuverlässig” gilt und welche Unterschiede die Protokolltechniken aufweisen, wird in den nächsten Laborterminen genauer untersucht.

1.1 SDL - Specification and Description Language

Grundlegende Voraussetzung für den Block C des Praktikums sind Kenntnisse in der formalen Beschreibungssprache SDL.An dieser Stelle wird nicht näher auf SDL eingegangen. Eine mehr an die Entwicklungsumgebung SDT angelehnte Einführung in SDL liefern die SDT Dokumentationen in Kapitel 2.

1.2 SDL Design Tool

Die Entwicklungsumgebung SDT ist eine Ansammlung von Werkzeugen, die alle unter einer einheitlichen grafischen Benutzeroberfläche integriert sind. Die Bedienung des Programmpakets lässt sich in vielen Situationen intuitiv erfassen. Für das Verständnis wofür die einzelnen Werkzeuge eingesetzt werden und wie ihr Zusammenspiel aussieht, ist es allerdings erforderlich, sich mit dem Handbuch auseinanderzusetzen. Die in den Literatur-Tabellen mit “obligatorisch” gekennzeichneten Abschnitte sind unbedingt zu lesen, die anderen Abschnitte erleichtern das Verstehen, z.B. durch Tutorien oder sind in ihrer Darstellung etwas ausführlicher. Dort werden auch Themen behandelt, die für die Lösung der Praktikumsaufgaben nicht unbedingt erforderlich sind, aber helfen die Arbeit mit SDT zu vereinfachen

1.3 SDL Framework

1.3.1 Grundidee

Für die anstehenden Aufgaben soll ein vorhandenes Kommunikationssystem benutzt werden, das an das OSI Modell angelehnt ist. Dieses System ist modular aufgebaut und besteht aus den Modulen source, transmitter, medium, receiver und destination (siehe Abb. 1). Hierbei stellen source und destination die Anwendungen der Schicht (N+1) dar, die Daten austauschen möchten. transmitter und receiver bilden die eigentliche Protokollschicht (Schicht (N)). medium ist der darunter liegende Transportservice der Schicht (N-1), der für Simulationen so eingestellt werden kann, dass er entweder zuverlässig oder unzuverlässig funktioniert.

Abb. 1: Framework

Die Übertragung der Nutzdaten erfolgt im vorliegenden Framework unidirektional: von source zu destination. Ein Verbindungsaufbau und -abbau, sowie ein automatischer Abbruch der Verbindung bei n vergeblichen Versuchen ein Paket zu übermitteln, werden in diesem Framework nicht modelliert.

Damit die Schichten, insbesondere die zwei jeweils beteiligten Prozesse, miteinander kommunizieren können, müssen passende Schnittstellen spezifiziert werden. Über die Schnittstellen werden Signale zwischen zwei Prozessen übermittelt. Die Festlegung der über die Signale ausgetauschten Datenformate stellt dabei nur einen Teil der Schnittstellenspezifikation dar. Zusätzlich müssen in SDL Regeln definiert sein, welche Signale es gibt und was sie bedeuten. Zusätzlich muss entsprechend des OSI Modells ein Service Access Point (SAP) bereitgestellt werden. Das geschieht in SDL z. B. durch Spezifikation der Signal-Routen. Für die Signale zwischen Anwendungsschicht (N+1) und Protokollschicht (N) wurde folgendes Format festgelegt:

newtype IDUType
	struct
		data DataType;
		bool Boolean;
endnewtype IDUType;
}

Listing 1: SDL Darstellung einer Interface Data Unit (IDU)

wobei mit der Komponente data die Nutzdaten und mit bool Schnittstellensteuerinformationen transportiert werden können. Für die Kommunikation zwischen den Protokoll-Entities wird ein anderes Datenformat benutzt (siehe Listing 2 bzw. vgl. Abb. 9):

newtype PDUType
	struct
		seqno Natural;
		data DataType;
		acknakBoolean;
endnewtype PDUType;
}

Listing 2: SDL Darstellung einer Protocol Data Unit (PDU)

wobei auch hier die Komponente data für die Übermittlung der Nutzdaten vorgesehen ist. Darüber hinaus können Protokollsteuerinformationen wie Sequenznummer und/oder Empfangsquittung (Komponenten: seqno und acknak) ausgetauscht werden. Da die Schnittstellen zwischen den Modulen definiert sind, lassen sich die Inhalte der Module relativ leicht austauschen. Auf diese Weise kann man ein und dasselbe Kommunikationssystem für verschiedene Protokolle bzw. Protokollvarianten benutzen - es müssen einfach nur die Inhalte der Module transmitter und receiver ausgetauscht werden.

1.3.2 Funktionsweise

In diesem Kapitel wird die Funktionsweise und das Zusammenspiel der einzelnen Blöcke und Prozesse erläutert. Die entsprechenden Variablennamen, Signale, Zustände etc. sind in den entsprechenden SDL-Diagrammen dargestellt, welche sie rechts in der Menüleiste unter "SnW" oder hier finden können.

source

Die in der Anwendungsschicht unidirektional versendeten Nutzdaten sind natürliche Zahlen. Die source generiert hierbei mit einem einstellbaren Takt (s_clk) eine Folge natürlicher Zahlen von “1” beginnend aufwärts. Jede Zahl wird einzeln an das Modul transmitter gesendet (Signal DataReq). Wenn der transmitter bereit ist, ein weiteres Signal DataReq von der source entgegenzunehmen, dann sendet er das Signal DataConf mit dem Parameterwert “True” zurück; ist er nicht bereit, weitere Signale DataReq entgegenzunehmen, dann verwirft er das nächste ankommende Signal DataReq und antwortet mit dem Parameterwert “False”. Die source wiederholt dann das letzte Signal DataReq solange, bis sie ein Signal DataConf mit einem “True” erhält und die nächste natürliche Zahl versenden darf (siehe source_process).

transmitter

Im transmitter-Modul ist die Sendeseite des jeweiligen Kommunikationsprotokolls enthalten. Hier werden die von der source mit dem Signal DataReq gesendeten Daten entgegengenommen, “verpackt” und mit dem Signal MDatReq dem Transportservice medium übergeben. Das Signal MDatReq ist dabei so definiert, dass es neben den Nutzdaten auch eine Sequenznummer transportieren kann, wenn dies vom Protokoll vorgesehen ist (siehe PDUType). Die Antworten der Empfängerseite werden durch das medium mit Hilfe des Signals MDatConf signalisiert. Dieses Signal kann außer der Sequenznummer ein Flag besitzen, das anzeigt, ob es sich hierbei um eine positive oder negative Quittung handelt (1=ACK, 0=NAK).

medium

Der Block medium repräsentiert den der Protokollschicht untergeordneten Transportservice der Schicht (N-1). Das medium arbeitet mit einer einstellbaren Taktgeschwindigkeit (m_clk bzw. r_clk) und funktioniert je nach Einstellung zuverlässig oder unzuverlässig. Die Fehlerarten, die hierbei im medium auftreten können, sind:

Verlust (lose)
Verdopplung (duplicate - kurz dup
Vertauschung (reorder)

Im Block medium sind vier Prozesse enthalten (siehe Abb. 14 bis Abb. 24). Die Prozesse message_manager und response_manager übernehmen die „Durchleitung“ der Signale durch das medium. Wenn sie dabei nicht durch irgendwelche Signale der hazarddemons “gestört” werden, dann läuft das medium im reliable mode, d.h. es treten keine Fehler im medium auf. Ansonsten versenden die Prozesse msg_hazarddemon und resp_hazarddemon je nach Einstellung der zu generierenden Fehlerart in periodischen Abständen das entsprechende Fehler-Signal (MsgLose, MsgDup, MsgReord, RespLose, RespDup bzw. RespReord) an den jeweiligen Manager- Prozess.
Dieser behandelt dann die nach der Verarbeitung dieses Fehler-Signals eintreffenden Nachrichten vom transmitter (MDatReq) bzw. Antworten vom receiver (MDatResp) entsprechend.

Trifft z.B. ein MsgLose beim message_manager ein, dann verwirft er einfach das nächste Signal MDatReq. Bei einem MsgDup schickt er dem receiver zwei mal das gleiche Signal MDatInd. Da die im Block medium enthaltenen Prozesse Input-Queues besitzen (wie alle Prozesse in SDL), kann es vorkommen, dass sich mehrere Nachrichten gleichzeitig im medium befinden. Nur wenn das der Fall ist, funktioniert auch das Vertauschen von Nachrichten - der message_manager schickt dabei kein MDatInd an den receiver, sondern ein MDatReq an sich selbst bzw. an die eigene Input-Queue. Auf diese Weise wird dieses MDatReq verzögert (Delay). Sind dann noch andere MDatReq-Signale in der Input-Queue des message_managers, dann kommt es zu Überholungen (Reordering).

receiver

Das receiver-Modul enthält die Empfangsseite des jeweiligen Kommunikationsprotokolls. Hier werden die vom medium mit dem Signal MDatInd gesendeten Nutzdaten entgegengenommen und gegebenenfalls mit einem DataInd an die destination weitergeleitet. Das geschieht natürlich nur, wenn der receiver “der Überzeugung ist”, dass das gerade empfangene Datenpaket gültig ist. Das Format des mit dem Signal MDatInd ausgelieferten Pakets ist hierbei das gleiche wie das Format des vom Transmitter gesendeten Signals MDatReq. Für die Quittierung der ankommenden MDatInd-Signale steht dem receiver das Signal MDatResp zur Verfügung. Es transportiert die gleiche Datenstruktur wie die Signale MDatReq, MDatInd und MDatConf (siehe Abb. 9). Mit dem in MDatResp enthaltenen Flag hat der receiver die Möglichkeit zu signalisieren, ob es sich um eine positive oder eine negative Quittung (1=ACK, 0=NAK) handelt. Das Feld für die Sequenznummer kann dann für die jeweils aktuelle Sequenznummer oder für die Sequenznummer next_expected benutzt werden.

destination

Mit Hilfe des Signals DataInd werden die Nutzdaten vom receiver zur destination transportiert. Dabei wird das gleiche Datenformat wie bei DataReq und DataConf verwendet, allerdings wird das Bool nicht interpretiert (siehe Listing 1). Im Block destination werden die durch das DataInd übermittelten Nutzdaten entgegengenommen und analysiert. Wenn in bestimmten Fehlersituationen das Protokoll der Schicht (N) versagt, dann ist der in der destination eintreffende Datenstrom nicht mehr der gleiche wie der von der source generierte. Die in der destination integrierte Fehlererkennung meldet die Art des entdeckten Fehlers mit Hilfe des Signals ErrorSign. Der Wert des dabei an die Umgebung (env) ausgegebenen Tupels stellt die aktuellen Zählerstände für die Fehlerarten Lose, Dup und Reord dar. Wohlgemerkt: dies sind die Fehler im Datenstrom, die das Protokoll nicht entdeckt bzw. behandelt hat. Die an dieser Stelle identifizierten Fehler sind nicht notwendigerweise die gleichen wie die, die gerade im medium auftreten.