Unter Queuing versteht man die Theorie von Warteschlangen, welche, obschon sehr alltäglich und klar definiert, einige Schwierigkeiten mit sich bringt. Eine wichtige Anwendung ist die Überlastungskontrolle in Netzwerken. Die Theorie wird deshalb hier auch anhand von dieser Anwendung erklärt.
Im folgenden betrachten wir einen anfangs leeren Router, der Pakete erhält und weitersendet. Ein Router setzt sich zusammen aus einer Warteschlange und einem Server (der die Pakete weitersendet). Der ganze Router wird hier auch System genannt.| Symbol | Erklärung |
|---|---|
| T | Zeit, die ein Paket im Router verbringt = Service-Zeit [s] |
| a(n) | Zeit, die seit der letzten Ankunft vergeht, bis das n-te Paket ankommt. [s] |
| A(t) | Anzahl Ankünfte während der Zeit 0 bis zur Zeit t [Pakete] |
| D(t) | Anzahl Abgänge während der Zeit 0 bis zur Zeit t [Pakete] |
| N(t) | Anzahl Pakete zur Zeit t [Pakete] |
| λ | Ankunftsrate. Mittlere Anzahl Pakete, die während einer Sekunde beim Router ankommen (= average arrival rate). [Pakete/s] |
| μ | Bandbreite. Mittlere Anzahl Pakete, die während einer Sekunde verarbeitet (weitergesendet) werden können (= Throughput). [Pakete/s] |
| ρ | Verkehrsdichte [Zahl] |
| E(T) | Mittlere Bearbeitungszeit pro Paket (Warteschlange und Weitersenden) [s] |
| E(Q) | Mittlere Queuing-Zeit (die, die in der Warteschlange verbracht wird). [s] |
| E(S) | Mittlere Service-Zeit (die, die für das Weitersenden verbraucht wird). [s] |
| E(N) | Mittlere Anzahl Pakete im Router [Pakete] |
| E(Nq) | Mittlere Anzahl Pakete in der Warteschlange [Pakete] |
| E(Ns) | Mittlere Anzahl Pakete in Bearbeitung [Pakete] |
a(0) ist 0.
Das erste Paket, das ankommt, kommt zur Zeit a(1).
Das zweite Paket kommt zur Zeit a(1)+a(2).
das n-te Paket kommt zur Zeit a(1)+a(2)+ ... +a(n) = ∑a(i), i=0..n
λ ist somit definiert als λ = n ⁄ ∑a(i).
Der Reziprokwert ist ∑a(i) ⁄ n. Man nennt diesen Wert die "average interarrival rate" = die Anzahl Sekunden, in denen ein Paket ankommt.
λ ist (korrekterweise mit limes) auch definiert durch λ = A(t) ⁄ t.
μ ist definiert durch (wiederum mit limes) μ = D(t) ⁄ t
Die mittlere Bearbeitungszeit E(S) = 1 ⁄ μ: Die Anzahl Sekunden, die im Durchschnitt pro Paket gebraucht werden.
ρ = λ ⁄ μ. Je näher dieser Wert zu 1 kommt, desto verstopfter ist die Leitung. Ist der Wert über 1, dann ist der Router überlastet.
E(T) = E(Q) + E(S)
E(N) = E(Nq) + E(Ns)
Das Little-Gesetz:
E(N) = λ · E(T)
E(Nq) = λ · E(Q)
Beim Queuing kommen nun auch noch Zufallsvariablen ins Spiel. Die wichtigsten Verteilungen sind dabei:
Die Binomialverteilung kann durch die Poissonverteilung angenähert werden:
Wenn man die Wahrscheinlichkeit innerhalb eines Zeitintervalls [0,t] betrachtet, so ergibt sich daraus:
(λ·t) kann auch umschrieben werden durch (n·p). Die Bedeutung von (λ·t) kann folgendermassen umschrieben werden: p ist die Wahrscheinlichkeit, dass ein Paket innerhalb einer n-tel-Sekunde ankommt. Anders gesagt: Unterteilt man eine Sekunde in n Untereinheiten, so hat jede Untereinheit also die Wahrscheinlichkeit p, dass ein Paket ankommt. Den gesamten Intervall zusammengenommen ergibt sich somit der Wert n*p, welcher besagt, wieviele Pakete in einer Sekunde ankommen. Dies ist genau der Wert λ. Wenn nun aber nicht nur eine Sekunde, sondern t Sekunden betrachtet werden, so ergibt die Rechnung λ·t die Anzahl Pakete, die in dieser Zeitspanne ankommen.
Man beachte, dass das letzte Gleichheitszeichen ein "Ungefähr gleich" ist. Die Exponentialverteilung wird auch eine Gedächnislose Verteilung genannt, was bedeutet, dass, wenn nach h Sekunden noch kein Paket angekommen ist, ist die Wahrscheinlichkeit, dass man nochmals h Sekunden warten muss gleich gross wie die Wahrscheinlichkeit, dass man überhaupt nur h Sekunden warten musste
Warteschlangen können verschiedene Formen annehmen. Um diese zu definieren, gibt es folgende Festlegungen:
- Wie kommen die Pakete an?
- Wie schnell werden die Pakete bearbeitet?
- Wie viele Server (Weiterleiter) gibt es?
- Wieviele Pakete können maximal insgesamt bearbeitet werden (normalerweise unendlich)?
- Wieviele Benutzer, die auf die Warteschlange zugreifen können (normalerweise unendlich)?
- Typ der Schlange: FIFO, LIFO (normalerweise FIFO)?
Die Werte, die bei 1 und 2 eingesetzt werden können sind entweder
M (Markov= Poisson oder Exponential) oder
D (Deterministisch=festes Muster) oder
Ek (Erlang? mit einem parameter k) oder
G (allgemein).
Die Bekannteste und in der Informatik am meisten gebrauchte Warteschlange ist die M/M/1-Queue.
M/M/1-Queue
Die MM1-Queue ist definiert durch eine Warteschlange, zu die Pakete exponentialverteilt eintreffen (A(t) = λ·t) und einen Server, der die Pakete exponentialverteilt bearbeiten kann (D(t)=μ·t). Zur Zeit 0 ist die Warteschlange leer, das System ist idle. Bei der MM1-Queue gilt zudem folgendes: Was hineinkommt, muss auch hinauskommen. Das will heissen, dass irgendwann in der Unendlichkeit, wenn das System wieder leer ist, genausoviele Pakete abgegangen sind (Abgangsrate), wie eingetroffen waren (Ankunftsrate)(tönt irgendwie logisch, oder?). Somit ist hier definiert, dass Abgangsrate = Ankunftsrate, oder A(t) = D(t). Daraus folgt folgende Erkenntnis:
Sei nun p0 die Wahrscheinlichkeit, dass das System nichts zu tun hat (idle). λ ist dann folgendermassen definiert:
λ = p0 · 0 + (1 − p0) * μ
Das will folgendes heissen: Die Anzahl Pakete, die aus dem System entlassen werden ist 0, wenn das System nichts zu tun hatte (p0). Und sie ist gleich μ, genau dann, wenn es eben etwas zu tun gab (1−p0). Somit muss gelten:
(1 − p0) = λ ⁄ μ = ρ
Dies bedeutet auch, dass ρ die Wahrscheinlichkeit ist, dass das System nicht idle, also in Betrieb ist. Aus diesem Grund nennt man ρ auch die Verkehrsdichte oder Benutzungsrate. Damit kann man sich auch in ungefähr vorstellen, was es heisst, wenn ρ grösser ist als 1. Mathematisch ist dies eigentlich nicht möglich, doch bedeuten tut es das, wonach es aussieht: Die Wahrscheinlichkeit, dass ich mit meinem Paket nicht durch den Router durchkomme, da er beschäftigt ist, ist grösser als 100%, was soviel bedeutet wie: Keine Chance. Man hat eventuell bereits Mühe, in die Warteschlange zu geraten, denn es hat anscheinend noch ein paar andere Benutzer, die auch auf diesen Router zugreifen wollen, und die werden dann in die Warteschlange geschoben, und die füllt sich langsam aber sicher.
Markovsches Model:
Um zu erklären, was genau in einer Warteschlange vor sich geht, muss noch das Markovsche Model erklärt werden. Dieses Model unterteilt ein ganzes System in kleine Staten (Mehrzahl von Status, nicht etwa Statussis oder Statunten), die einen kleinen Zeitintervall beschreiben. Hier ist diese Status-Unterteilung gleich der Unterteilung in die Anzahl Pakete, die sich im System befinden. Status 0 bedeutet also: kein Paket im System. Satus 1: 1 Paket, Status 2: 2 Pakete, usw.
Status 0 ist dabei gleich dem idle-Status mit der Wahrscheinlichkeit p0.
Wenn man sich nun im Status 0 befindet, so kann man mit der Wahrscheinlichkeit (λ·t) in den Status 1 wechseln. Zur Erinnerung: λ·t ist die Anzahl Pakete die in der Zeit t ankommen. Da nun im Markovschen Model die Zeiteinheit t genug klein gewählt werden kann, kann (λ·t) sowie (μ·t) kleiner als 1 angenommen werden. Die Wahrscheinlichkeit, dass man sich im Status 1 befindet ist also p1=p0*(λ·t)
Wenn man sich im Status 1 befindet, so kann man mit der Wahrscheinlichkeit (μ·t) wieder in den Status 0 wechseln. somit gilt also p0=p1*(λ·μ).
Diese Berechnung der Wahrscheinlichkeit, dass man sich in einem bestimmten Status i befindet lautet also allgemein:
p(i+1)=p(i)*λ*t
p(i)=p(i+1)*μ*t
Und somit:
ρ*p(i)=p(i+1)
Und allgemein:
p(i) = ρi * p0
Des weiteren können folgende Regeln geltend gemacht werden:
Durch diese letzte Formel sieht man, was passiert, wenn ρ gegen eins geht. Die Anzahl Pakete im Router strebt gegen unendlich. Dadurch wird die Wartezeit natürlich ebenfalls unendlich gross.