Datum:14.12.2014
Moderatoren:marcus, matou

Marcus hat versucht den Titel kurz zu fassen, aber es geht nicht. Es geht um einen wissenschaftlichen Artikel, der eine Zusammenfassung ist, nach welchen Strategien ein Router ein Paket wählt, dass er als nächstes weiter leitet.
Es geht irgendwie um paketvermittelnde Netze, Scheduling, Bedeutung für Netzneutralität unter Erklärung ganz vieler Algorithmen.

Modelle zum Nachschlagen: Fair Queuing, Fluid Fair Queuing, Weighted Fair Queuing, Virtual Clock, Round Robin, Hierachical Round Robin, Stop and Go, Earliest Due Date, Jitter Earliest Due Date, Rate Controlled Static Priority,

Ich muss die Aussagen einschränken, welchen Algorithmus ein Router benutzt: Ich habe noch nie einen Router gebaut und weiß nicht, was die Hersteller implementieren. Aber wenn ich an meine Erfahrungen mit Consumergeräten denke und den Aufwand möglicher Strategien als Implementierungsaufwand in Software und Hardware sehe, dann kann ich Schlussfolgerungen ziehen:

ca 500sec Das Queuing-Modell hängt vom Router ab. Alle werden mindestens eine Art Fair Queuing mithilfe nicht-gewichtetes-Round-Robin unterstützen, weil es leicht zu implementieren ist.

ca 590sec Das Zustandekommen einer TCP-Verbindung hängt vom Handshake ab. Die drei Pakete müssen es einmal über die Leitung schaffen. Das wird beschränkt durch die Frage, ob das Paket in die Eingangswarteschlange des Routers (oder eines Folgerouters) aufgenommen werden kann - anderenfalls wird es der Router verwerfen. Wie oft TCP versucht ein Paket noch einmal zu senden und in welchen Zeitintervallen das passiert ist konfigurationsabhängig. Nehmen wir für unser Modell vereinfacht an, TCP mache zehn Zustellversuche, wobei die Zeit zwischen Fehlschlägen exponentiell anwächst. Wenn dich Details interessieren, dann schlage die Implementierung deiner Socket-API nach! (Tut mir Leid für die Leute, die Java-Beans benutzen :P) Die TCP-Verbindungsgeschwindigkeitsausprobierstrategien sind alle nach Städten benannt. Ein mögliches Schlagwort zum Selbstrecherchieren "Manhatten".

Hierachical Round Robin: Bild zur Veranschaulichung
Hieracical Round Robin
Bild Creative Commons Attribution /dev/radio
Diese Warteschlange würde vorausberechnet aussehen:
C1,C1,C2,C3,*,C1,C1,C2,C3,*,C1,C1,C2,C4,*...

Stop and Go: Bild zur Veranschaulichung
Stop and Go
Bild Creative Commons Attribution /dev/radio

Weighted Fair Queuing: Bild zur Veranschaulichung
Weighted Fair Queuing
Bild Creative Commons Attribution /dev/radio

Paket P3 der Verbindung C2 wird zuerst in die Ausgangswarteschlange gebracht, weil es nach Referenzberechnung bei idealem Modell zuerst vollständig übertragen wäre.

Virtual Clock: Bild zur Veranschaulichung
Virtual Clock
Bild Creative Commons Attribution /dev/radio

Wenn Verbindung C2 zu Beginn des Diagramms einen Burst von 10Paketen auf den Router wirft, sieht die Scheduling-Reihenfolge unverändert aus, mit der Ausnahme, dass der Router den freien zehnten Slot benutzen kann, um die Zusatzlast von C2 zu bedienen. Der zehnte Slot würde sich gut für eine nicht-periodische Datenverbindung eignen.

pi