Skip to content

Gedanken zum Scheduling mit dynamischen Zeitschlitzen

Jump to bottom
Ralf Wilke DH3WR edited this page Mar 18, 2018 · 2 revisions

Ich fasse hier mal zusammen, was ich mir zum Scheduling mit dynamischen Zeitschlitzen ausgedacht habe.

Datenstuktur

  • Es gibt eine NxN Matrix mit Typ boolean mit den Überschneidungen der Sender. Eigentlich reicht eine halbe Matrix, da sie symmtrisch ist. Ob dass den erhöhten Aufwand rechtfertigt, nur die eine Hälfte zu speichern, muss man noch sehen.
  • Jeder Sender hat eine Prio-Queue, die entsprechend mit den eingehenden Nachrichten gefüllt wird.
  • Jeder Sender hat außerdem einen "AirTime" Zähler in µs, der die Sendezeit dieses Senders in der Vergangenheit akkumuliert. Dieser wird für die Ermittlung der Reihenfolge benutzt.
  • Nachrichten werden an Sender nur für die unmittelbare Zukunft (tbd. wie viele Sekunden im Voraus) verteilt. Sowohl der Empfang der Nachricht als auch die erfolgte Aussendung werden quittiert und im DAPNET Core Netz festgehalten. So wird sichergestellt, dass jeder Sender alle Nachrichten sendet, auch wenn er mal kurz weg ist.
  • Eine Berechung der benötigten Sendezeit auf dem Core bei bekanntem Nachrichteninhalt ist notwendig.
  • Es gibt ein Guard-Zeit, welches immer auf die reine Sendezeit addiert wird. Dies gleicht jitter und ungleiche Uhren auf den Sendern sowie ein TX-Delay aus.

Algorithmus zum Bestimmen, in welcher Reihenfolge die Sender senden

Initialier Durchlauf

  • Es wird die Senderliste von Anfang bis Ende durchgegangen. Man beginnt mir dem ersten Sender in der Liste. Es wird nach Nachrichten mit der höchsten Prio-Stufe gesucht.
  • Gibt es welche, so werden sie zum Aussendung markiert, und die AirTime berechnet und auf den Zähler addiert
  • Es wird der nächste Sender angeschaut
  • Gibt es dort keine Nachrichten mit der höchste Prio-Stufe wartend, weiter
  • Gibt es dort welche, aber der Sender steht mit den Sendern, die bereits als "zum Senden freigegeben" markiert sind, in einem Konflikt in der Tabelle, wird der Sender übergangen.
  • Weiter bis zum Ende der Liste

Folgede Durchläufe

  • Es wird die Liste nach aufsteigender Air-Time sortiert. Es wird der Sender mit der geringsten AirTime und Meldungen der höchsten Prio-Klasse gesucht. Gibt es diese und besteht kein Konflikt für die Zeit der Aussendung, so wird diese zur Sendung markiert.

  • Weitere Sender, die aufsteigend die nächst-kleinere Airtime haben, werden betrachtet, ebenfalls unter Berücksichtigung der Matrix.

  • Gleiches Vorgehen für die anderen 4 Prio-Klassen.

Randbedingungen: Wegen der Totzeit der Präambel, sendet ein Sender, so er noch etwas potentiell zu Senden hat, immer mehrere Rufe aus. Die minimale Wunschlänge kann über einen Parameter angepasst werden. Ein Sender-Wechsel kostet also immer die Präambel- und die Guard-Time-Zeit.

Der AirTime-Zähler ist eine Art "Bestrafung" für den jeweiligen Sender, wenn es schon gesendet hat. Es wird bevorzugt als nächstes ein Sender gewählt, der die geringste Bestrafung erfahren hat.

Um den AirTime-Zähler nicht mit der Zeit überlaufen zu lassen, wird nach jedem Komplett-Durchlauf ermittelt, ob alle AirTime-Zähler einen festen Wert überschritten haben. Wenn ja, wir dieser bei allen Zählern abgezogen. Damit ändert sich die Bestrafungshärte nicht, wohl aber die absolute Zahl.

(Das Ganze ist noch nicht komplett durchdacht. Irgendwelche Vorschläge für Programme zum Simulieren des Alogrithmus?)

Clone this wiki locally