Rechnernetze
Home Nach oben

Grundbegriffe

Wartestationen (queueing station) können u.a. durch folgende Eigenschaften charakterisiert werden:

Zugangsprozeß (arrival process): Verteilung der Zeiten zwischen dem Eintreffen zweier Pakete in der Wartestation

Bedienprozeß (service process): Verteilung der Zeiten, die ein Paket übertragen (oder allgemeiner ein Auftrag bedient) wird

Anzahl der Bediener (oder paralleler Leitungen)

Bedienstrategie (queueing discipline oder service discipline): Reihenfolge, in der Pakete zur Bedienung aus der Warteschlange herausgeholt werden. Üblich sind FCFS (First Come First Served) oder FIFO (First In First Out) für Bedienung des am längsten wartenden Pakets, LCFS (Last Come First Serve) oder LIFO (Last In First Out) für die Bedienung des am kürzesten wartenden Pakets, sowie PRIO (Priority) für bestimmte Prioritäten, und SJN (Shortst Job Next) bzw. LJN (Longest Job Next) für Pakete mit den kürzesten bzw. längsten Bedienzeiten.

Pufferkapazität (queueing capacity) der Warteschlange: Anzahl der Pakete, die in der Warteschlange oder Puffer (queue) gespeichert werden können.

Eine verbreitete Notation (nach Floyd) zählt diese Parameter in einer Liste auf, z.B. M/G/1/FIFO/10 für eine Wartestation mit gedächtnislosem Zugangsprozeß, allgemeinem Bedienprozeß, einem Bediener, FIFO-Bedienstrategie und 10 Warteplätzen. In der Regel werden nur die ersten drei Werte geschrieben, z.B. M/D/2. Für die Verteilungen bedeuten die Buchstaben u.a.

M (Markov): Gedächtnislose Verteilung: . Das folgende Bild zeigt den Verlauf dieser Verteilung für l = 0,1 .. 10.

NEGEXP.WMF (24010 Byte)
Dichte der negativ exponentiellen Verteilung mit l = 0,1 .. 10.
NEGEXPDICHTE.WMF (24480 Byte)

G (General): Beliebige Verteilung.

D (Deterministic): Konstante Verteilung, d.h.: .
Beispiel: Deterministische Verteilung mit d = 4,5.

DISKRETEVERTEILUNG.WMF (17930 Byte)

Bin (Binomial): Binomiale (diskrete) Verteilung, d.h. und damit .

BINOMIAL.WMF (39564 Byte)

Dabei ist V eine Zufallsvariable, d.h. der Ausgang eines Zufallsexperiments. Wir gehen hier nicht weiter auf die stochastische Notation: P[V<x] ein; sie wird im folgenden nicht benötigt.

In der Wartetheorie zeigt man, wie die Verzögerungszeit von Paketen berechnet werden kann. Da sich die Verzögerungszeit eines Pakets aus der eigentlichen Bedienzeit und einer Wartezeit zusammensetzt, ist die Berechnung nicht einfach. Außerdem kann die Zeit nur im statistischen Sinne bestimmt werden, da die Wartezeit von den zufällig anwesenden anderen Paketen abhängt. In vielen Fällen kann nicht die Verteilung, sondern können nur Momente der Wartezeiten berechnet werden. In diesen Abschnitten sollen die grundlegenden Begriffe aus der Wartetheorie eingeführt werden.