Statisches Scheduling in RT-Netzwerken Betrachtung zweier Ansätze

Statisches Schedulingin RT-Netzwerken

Betrachtung zweier Ansätze

Marcus [email protected]

21.01.2005


Inhalt des Vortrages

• Einführung• Backtracking• Antz• Agenten• Rückblick /Ausblick

Einführung



Folie 4

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Wissenswertes

•nur harte Echtzeit wird betrachtet

•Gesamtzykluszeit = kgV aller Zyklen

•kleinster Zeitschritt = ggT aller Sendezeiten

•Offset = Abstand Nullzeit bis ersten Sendung

Backtracking



Folie 6

Inhalt

Einführung

Backtracking

Antz

Agenten


Backtracking

•klassisches Verfahren

•betrachtet alle Konstellationen

•erschöpfende Suche

•rekursiv leicht formulierbar

•hoher Resourcenbedarf


Folie 7

Inhalt

Einführung

Backtracking

Antz

Agenten


Ablauf

Schedule(KL-Liste) {

1. wähle KL aus KL-Liste

2. Keine KL mehr vorhanden -> fertig

3. bestimme nächsten Sende-Offset

4. Falls kein Offset mehr vorhanden gehe zu 9.

5. prüfe auf Konflikt

6. bei Konflikt gehe zu 3.

7. Schedule(Restliche KLs)

8. Falls Misserfolg bei 7. meldet gehe zu 3.

9. Melde Mißerfolg

}


Entscheidungsbaum

KL-Wahl

Offset-Wahl

Entscheidungsbaum wird ggf. komplett durchgearbeitet

......

... ..

. .

.........

...... ... ...

.

.

.


Folie 9

Inhalt

Einführung

Backtracking

Antz

Agenten


• Priorisierung der KL (# Konflikte, RT-Klasse)

• Verwendung sinnvoller Offsets

• Änderung der Konfliktauflösung

• wie gehabt: Offsets durchgehen

• Backtracking nur auf Konflikt-KL

• Notnagel: normales Verhalten

Verbesserungen


Folie 10

Inhalt

Einführung

Backtracking

Antz

Agenten


• Algorithmus springt durch den Entscheidungsbaum

->Verringerung des Backtracking

-> schneller

• Lösung wird immer noch gefunden

• Erhöhung der logischen Komplexität

Folgen der Verbesserung


Folie 11

Inhalt

Einführung

Backtracking

Antz

Agenten


Fazit

• Basisalgorithmus einfach

• Verbesserung komplex -> fehlerträchtig

• wg. Komplexität schwer auf andere RT-Klassen erweiterbar

• schwer nachvollziehbar

Antz



Folie 13

Inhalt

Einführung

Backtracking

Antz

Agenten


ACO (Ant Colony Optimization) Ansatz

• Abbildung des Problems auf eine Ameisenkolonie

• jede Ameise erfüllt nur einfache Aufgaben

• Kommunikation erfolgt nur über Duftstoffe

• viele Ameisen zusammen lösen ein komplexes Problem (z.B. Shortest Path)

-> emergente Intelligenz


Folie 14

Inhalt

Einführung

Backtracking

Antz

Agenten


Netzwerk aus Ameisensicht

• Netzwerk = Ameisenhaufen

• Teilnehmer = Kammern

• Switches = Abzweigungen

• Verbindungen = Tunnel

• KL = Wege

• Kleinster Zeitschritt = Paket

• Sendung = mehrer Pakete


Folie 15

Inhalt

Einführung

Backtracking

Antz

Agenten


Problemspezifisches

• exklusive Nutzung der Tunnel

• Ameisen vertreten je eine KL

• Ameisen haben eine gewisse Priorität

• Markierungen identifizieren Ameisen (ID + Priorität) = Duftstoff


Folie 16

Inhalt

Einführung

Backtracking

Antz

Agenten


Aufgaben einer Ameise

• Transport eines Pakets

• Durchführung einer Sendung

• Markierungen setzen

• Markierungen bei Konflikt entfernen

• Zyklus einhalten

• Erfolge merken

• eigene Priorität ändern


Folie 17

Inhalt

Einführung

Backtracking

Antz

Agenten


Ablauf eines Schedulingschrittes

Dauer: 1. Paket

1. alle Ameisen markieren bei Bedarf ihren Weg

2. Ameisen gehen nacheinander ihre Wege zurück (nach Folge Ihrer Priorität)

o ggf. Entfernung ihrer Markierung

3. Alle Ameisen fertig -> neuer Schritt


Folie 18

Inhalt

Einführung

Backtracking

Antz

Agenten


Ablauf eines Schedulingschrittes

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Alle Ameisen markieren ihren Weg

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Rot prüft auf stärkere Markierungen auf dem Weg -> nein -> Rot gewinnt

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Grün prüft auf stärkere Markierungen auf dem Weg -> Rot ist stärker

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Grün hat verloren -> Entfernung der Markierung

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Blau prüft auf stärkere Markierung auf dem Weg -> nein -> Blau gewinnt

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Priorität:

1. Rot

2. Grün

3. Blau


Folie 19

Inhalt

Einführung

Backtracking

Antz

Agenten


Falsche Abfolge beim Scheduling

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Alle Ameisen markieren ihren Weg

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Rot prüft auf stärkere Markierungen auf dem Weg -> nein -> Rot gewinnt

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Blau prüft auf stärkere Markierungen auf dem Weg -> Grün ist stärker

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Priorität:

1. Rot

2. Grün

3. Blau

Blau hat verloren -> Entfernung der Markierungen

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Grün prüft auf stärkere Markierungen auf dem Weg -> Rot ist stärker

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Grün hat verloren -> Entfernung der Markierungen

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN


Folie 20

Inhalt

Einführung

Backtracking

Antz

Agenten


Priorisierung

• wichtigster Mechanismus

• Ameisen ändern Priorität

• + falls der Bedarf steigt

• + bei Weg-Gewinn

• - je regelmäßiger eine Sendung durchgeht

-> Chance für alle Ameisen


Folie 21

Inhalt

Einführung

Backtracking

Antz

Agenten


Wie ergibt sich ein Plan?

• System erreicht stabilen Zustand

• alle Ameisen sind immer erfolgreich

• die Prioritäten sind ausgeglichen

• Zeitstempel des ersten Pakets einer Sendung = Offset


Folie 22

Inhalt

Einführung

Backtracking

Antz

Agenten


Fazit

• Einfacher Ansatz

• Komplexität entsteht durch Zusammenwirken einfacher Algorithmen

• Leicht zu implementieren

• Leicht erweiterbar

• Brute-Force Suche

• Problem: Abbruchbedingung!!!

Agenten



Folie 24

Inhalt

Einführung

Backtracking

Antz

Agenten


Einführung

• Agentensystem löst eine Aufgabe

• Jeder Agent versucht seine Aufgabe zu erfüllen

• Interaktion mit anderen Agenten

• Verhandlungen / Diskussion der Argumente

• mode(rner) Ansatz


Folie 25

Inhalt

Einführung

Backtracking

Antz

Agenten


Agenten beim Scheduling

• allg. Ziel: Schedule erstellen

• egoistisches Ziel: Anforderungen einer KL erfüllen

• Argumente für Verhandlungen z.B.:

• Wichtigkeit

• Bedarf (Ablauf des Zyklus)

• aktuelle Sendung beenden


Folie 26

Inhalt

Einführung

Backtracking

Antz

Agenten


Fazit

• benötigt ausgeklügelte Synchronisation

• erweiterbar über Abänderung der Verhandlungstaktik

• gute Nachvollziehbarkeit

Rückblick /Ausblick



Folie 28

Inhalt

Einführung

Backtracking

Antz

Agenten


Rückblick

• Ansätze zeigen Schwierigkeit des Problems

• Backtracking

+ terminiert, erschöpfend

- resourcenhungrig, schwer erweiterbar, komplex

• Antz

+ erweiterbar, leicht implementierbar

- Abbruchbedingung unklar, nur eine Lösung, Brute-Force


Folie 29

Inhalt

Einführung

Backtracking

Antz

Agenten


Ausblick

• Ameisenlösung vielversprechend

• geschickte Priorisierung nötig

• Abbruchbedingung ist zu bestimmen

• mehr Intelligenz für Ameisen -> Verringerung der Berechnungsschritte

Das wars....

Noch Fragen?Marcus Merz

[email protected]

Documents

Statisches Scheduling in RT-Netzwerken Betrachtung zweier Ansätze