Rechnernetze
Home Nach oben

Bewertungskriterien für Routing-Algorithmen

Rechnernetze unterscheiden sich außer in ihrer Topologie auch in den Anwendungen, für die sie eingesetzt werden (z.B. Bürokommunikation, Maschinensteuerungen usw.). Aus diesem Grunde sind für die einzelnen Aufgabenbereiche auch unterschiedliche Routingverfahren einzusetzen, um eine möglichst effiziente Datenübertragung zu gewährleisten. Diese Auswahl sollte nach objektiven Entscheidungskriterien geschehen, welche in der Regel von bestimmten Parametern des Netzes abhängen. Solche Randbedingungen umfassen insbesondere die Topologie des Netzes, die Übertragungsgeschwindigkeit der Leitungen, langfristige mittlere Belastungen sowie die geforderte Dienstqualität. In einem begrenzten Umfang können auch schwankende Größen wie die Auslastung einzelner Leitungen oder die Belegung der Puffer vor den Ausgangsleitungen für bestimmte Entscheidungen herangezogen werden. Darüber hinaus sollten die folgenden allgemeinen Bewertungskriterien berücksichtigt werden:.

Dauerhaftigkeit: Bei gleichen Verhältnissen soll das Routing immer nach dem gleichen Verfahren ablaufen.
Robustheit: Bei Änderungen des Netzes (Ausfall von Knoten oder Leitungen; Hinzufügen neuer Knoten; Änderung der Belastung) soll das Netz weiterhin im Rahmen der noch verfügbaren Kapazität Pakete übertragen.
Einfachheit: Die Routing-Algorithmen sollen einfach zu verstehen, zu implementieren und gegebenenfalls zu verifizieren sein.
Zuverlässigkeit: Die Pakete sollen immer beim Empfänger eintreffen.
Optimalität: Bezüglich der gewünschten Bewertungskriterien (Kosten, Verzögerung, Sicherheit, Ausnutzung, Auslastung usw.) soll das Netz die bestmögliche Dienstqualität liefern.
Fairness: Alle Teilnehmer sollen möglichst gleich gut bedient werden.

Ein stabiles Netz verhält sich bezüglich seiner Kenngrößen, z.B. Antwortzeiten oder verfügbarer Kapazität, immer ähnlich, was für viele Anwendungen wichtig ist. Viele Anwendungen verlangen, dass die Reihenfolge der Pakete erhalten bleibt; dann darf in der Regel während des Betriebs einer Verbindung die Route nicht geändert werden.

Ein robustes Netz passt sich bei Änderung seiner Parameter automatisch der neuen Situation an. Solch ein selbstadaptierendes Verhalten wird mit gewissen Risiken bezüglich der Stabilität und Zuverlässigkeit erkauft, da die damit notwendig werdende Regelung der Wegewahl zu schwingendem Verhalten führen kann, Fehler provoziert und die Komplexität erhöht. Letzteres widerspricht der Forderung nach Einfachheit der Algorithmen.

Die Zuverlässigkeit des Algorithmus soll garantieren, dass Pakete stets beim richtigen Empfänger eintreffen. Insbesondere bei dynamischen oder optimalen Routingstrategien können Pakete u.U. nur zwischen zwei Knoten oder zyklisch über mehrere Knoten im Kreis geschickt werden, ohne jemals den eigentlichen Zielknoten zu erreichen, was nur schwierig zu erkennen ist, aber dennoch auf jeden Fall vermieden werden muss.

Wie jedes technische System, so müssen auch Rechnernetze insbesondere bezüglich der Kosten optimiert werden. Dennoch hängen die Kosten häufig von den Gebühren öffentlicher Anbieter ab (z.B. bei Leitungen der Telekom), welche sich kurzfristig aus politischen Gründen ändern können. In solchen Fällen muss man sich mit suboptimalen Lösungen zufrieden geben. Auch steigen die Kosten häufig bei größeren Übertragungsleistungen sprunghaft an; z.B. stellt der Übergang von DATEX-P zu FDDI eine enorme Kostensteigerung dar, bei gleichzeitig großer Leistungssteigerung. Hier sind die Kosten, auch in Hinblick auf zukünftige Anforderungen, praktisch nicht mehr objektiv optimierbar.

Um die Kenngrößen zu bestimmen, sind entsprechende Formeln anzugeben, aus denen die jeweiligen Werte errechnet werden können. Die Verzögerung muss als Zeit angegeben werden, die von der Absendung einer Nachricht bis zu dessen Empfang vergeht. Als Zeitpunkte kann man entweder den der Übergabe eines Pakets (der Referenz auf ein Paket) oder die Absendung des ersten Bits und Empfang des letzten Bits definieren. Dieses hängt jedoch u.U. stark von der jeweiligen Anwendung ab, so dass hier genaue Definitionen zu den jeweiligen Kennzahlen erforderlich sind.

Die Zuverlässigkeit eines Netzes wird in der Regel als Wahrscheinlichkeit angegeben, dass ein Paket korrekt beim Empfänger eintrifft. Sie kann nur als statistische Größe gesehen werden (wie die meisten anderen auch) und muss entsprechend durch ein statistisches Modell ermittelt werden.

Unter Auslastung wird das Verhältnis zwischen der Zeit, die ein System überhaupt arbeitet, und der gesamten Zeit verstanden. Die Ausnutzung wird hingegen als das Verhältnis zwischen der geleisteten Arbeit und der maximal möglichen Arbeit eines Systems definiert. Beide Größen können bei Systemen, die mehrere Aufträge gleichzeitig bearbeiten können, sehr unterschiedlich sein. In Rechensystemen kann z.B. durch die Nutzung paralleler Einheiten die Ausnutzung vergrößert werden, während sich gleichzeitig die Auslastung verringern kann.

Fairness ist nur dann gegeben, wenn alle Teilnehmer gleichberechtigt sind. Allerdings kann in manchen Umgebungen für gewisse Nutzergruppen die Dienstqualität verbessert werden, falls diese Nutzer bereit sind, höhere Kosten zu tragen. Ebenso können aufgrund rechtlicher oder technischer Bedingungen bestimmte Dienste bevorzugt werden, z.B. Alarme, Managementinformation oder kurze Nachrichten. Daher kann Fairness in der Regel nur bezüglich einzelner Nutzergruppen gefordert werden.

FAIRNESSUNDOPTIMALITAET.WMF (6352 Byte)

Auch kann die Fairness zu anderen Anforderungen, z.B. der Optimalität, im Widerspruch stehen. Braucht ein einzelner Teilnehmer einen sehr langen Weg, während alle anderen nur kurze Wege benötigen, so erreicht man einen optimalen Durchsatz (und damit vermutlich einen maximalen Nutzen für den Netzbetreiber), wenn nur die kurzen Verbindungen bedient werden, da dann bei geringerer Arbeit die Anzahl übertragener Pakete, maximal ist. Im obigen Bild ist die Verbindung A–E für das Netz sehr kostspielig, während die Verbindungen B–H, C–G und D–F besonders einträglich sind. Liegt in den letzteren Knoten genügend Arbeit vor, so würde die Verbindung A–E bei rein nutzenoptimaler Strategie niemals bedient werden.