Rechnernetze

Dezentrale Zuteilungsprotokolle

Aus den im letzten Abschnitt durchgeführten Betrachtungen folgt, dass in Rechnernetze variable Zuteilungsverfahren vorteilhafter sind als feste. Ein Beispiel für ein festes dezentrales Zuteilungsprotokoll ist das Bit-Map-Protokoll. In einer Reservierungsphase, in der ein Konkurrenzschlitz übertragen wird, teilen alle Rechner dem Netz (und somit allen anderen Rechnern) durch Setzen eines ihnen zugeordneten Bits mit, ob sie ein Paket senden wollen. Dieses wissen danach alle Rechner, und die sendewilligen können dann in einer vorgegebenen festen Reihenfolge ihre Pakete abschicken. Der Konkurrenzschlitz ist bei N Stationen gerade N Bits lang; sein Beginn ist allen Teilnehmern bekannt.

Ist das System nur sehr gering belastet, so werden praktisch nur Konkurrenzschlitze gesendet. Da die Station mit der Nummer n sich jeweils nur im n-ten Bit des Konkurrenzschlitzes anmelden kann, muss eine Station, die nach dem ihr zugeordneten Bit sendebereit wird, die restlichen Bits des laufenden Konkurrenzschlitzes, die evtl. nachfolgende Datenphase sowie sämtliche Bits des folgenden Konkurrenzschlitzes abwarten, ehe sie senden kann. Daher gilt für die Anzahl der Bits im Konkurrenzschlitz, die die Station n warten muss, wenn sie im m-ten Schlitz sendebereit wird:

Ist jeder Zeitpunkt für die Sendebereitschaft gleichwahrscheinlich (p=1/N), so ergibt sich für die mittlere Wartezeit der Station n (in Bits ohne Datenphase)

wie man leicht nachrechnet. Dieses Verfahren lässt Stationen mit kleiner Nummer n bis zu dreimal so lange warten wie solche mit großer Nummer. Dieses kann bei großer Zahl N zu merklichen Verzögerungen führen.

Bei hoher Auslastung des Kanals ist die Reservierungsphase in der Regel klein gegenüber der Belegung des Kanals durch übertragene Nutzdaten, so dass sich die Wartezeit vorwiegend aus der Übertragungszeit von Nutzdaten aller Stationen ergibt, die in der vorherigen Reservierungsphase Rahmen angemeldet haben.

Eine Abart des Bit-Map-Protokolls ist das BRAM-Protokoll (braodcast recognition access mechanism), auch MSAP (mini slotted alternating priorities) genannt, welches sofort, wenn eine Station einen Sendewunsch anmeldet, die Reservierungsphase unterbricht und die Sendung eines Pakets erlaubt. Nach dieser Übertragung ist die nächste Station in einem einmal festgelegten Zyklus anmeldungs- und sendeberechtigt. Somit gibt es keine Bevorzugung einzelner Stationen, d.h. die Wartezeit bei geringer Belastung beträgt im Mittel

W_BRAM = 0,5 · N + 0,5,

ist also nicht mehr von n abhängig und im Mittel so groß wie die kleinste mittlere Wartezeit beim Bit-Map-Protokoll bei geringer Belastung.

In den hier beschriebenen Fällen ist die Wartezeit von der Anzahl der Stationen N abhängig, die den Kanal benutzen könnten. Ist diese sehr große, so ist auch die Wartezeit recht groß. Es gibt verschiedene Vorschläge, diese Wartezeiten zu verringern. Die meisten dieser Vorschläge versuchen, die Stationen in Gruppen aufzuteilen. Die extremste Form dieser Einteilung wurde bereits mit dem BRAM Protokoll vorgestellt, bei dem nur eine Station um einen Schlitz konkurriert. Bei dieser Zuordnung ist garantiert, dass niemals Kollisionen auftreten. Auf der anderen Seite könnten alle Stationen in einer Gruppe zusammengefasst werden, was das Problem der Wartezeit minimiert, jedoch das Problem der Auswahl der Station deutlich erhöht. Es ist also ein Verfahren zu finden, welches das Problem der Wartezeit und der Auswahl einer Station minimiert. Ein Lösung bietet hier das adaptive Baumprotokoll. Bei diesem Verfahren kann die Nummer jeder Station z.B. binär kodiert werden, so daß eine Station einer Gruppe b angehört, wenn das b-te Bit ihrer Stationsnummer gesetzt ist (eine Station kann mehreren Gruppen angehören!). Im ersten Durchgang dürfen nach einer erfolgreichen Übertragung dann alle Stationen Sendewünsche anmelden, die in der Gruppe 1 sind.

Ist dieses erste Bit also 1, so möchte mindestens eine Station der Gruppe 1 senden, sonst keine Station aus dieser Gruppe. Die so ausgewählte Gruppe mit mindestens einer sendebereiten Station wird jetzt weiter halbiert, indem alle Stationen der Gruppe 2, wenn sie in der Gruppe 1 sind und bereits einen Sendewunsch genannt haben, das nächste Bit senden dürfen usw. Irgendwann sind alle Gruppen durchgeprüft und es kann nur noch eine sendebereite Station übrig bleiben. Damit kann bereits nach log2(N) Schritten festgestellt werden, welche Station senden will.

Bei geringer Belastung des Kanals ist dieses Verfahren somit sehr viel günstiger als die anderen Verfahren. Bei hoher Belastung hängt die Wartezeit jedoch stark von der Nummer der Station ab, da Stationen mit vielen gesetzten Bits in ihrer Nummer offenbar eine bessere Chance haben zu senden. Hier kann man versuchen, durch Austauschen der Stationsnummern gezielt einzelne Stationen zu bevorzugen. Man kann auch vereinbaren, dass Stationen nur dann an einer Bewerbung um den Kanal teilnehmen dürfen, wenn mindestens einmal ein leerer Konkurrenzschlitz gesendet wurde. Dadurch sammeln sich alle Stationen, die während eines solchen Zyklus sendebereit werden, in einer besonderen Gruppe, so dass hier eine Fairness mit festen Prioritäten garantiert werden kann. Der zusätzlich Overhead ist lediglich ein Konkurrenzschlitz je Abarbeitungszyklus.