MathiasKurthRestricted: Difference between revisions

From
Jump to navigation Jump to search
Line 24: Line 24:
* Ack Ordering: Die Menge der Knoten, die das Paket empfangen haben, muss sich auf eine kollisionsarme Ack-Reihenfolge einigen.
* Ack Ordering: Die Menge der Knoten, die das Paket empfangen haben, muss sich auf eine kollisionsarme Ack-Reihenfolge einigen.
* Größe das Candidate Set: Potentiell sind jetzt alle Nachbarn Kandidaten. Das Ack-Fenster muss aber beschränkt bleiben (Das Ack hat feste Größe und feste Übertragungszeit.)
* Größe das Candidate Set: Potentiell sind jetzt alle Nachbarn Kandidaten. Das Ack-Fenster muss aber beschränkt bleiben (Das Ack hat feste Größe und feste Übertragungszeit.)

=== Frame Format ===


Ein Knoten s sendet folgendes Frame:
Ein Knoten s sendet folgendes Frame:
Line 29: Line 31:
| Final Destination d |
| Final Destination d |
|------------------------------------|
|------------------------------------|
| ETX(d)_max | ETX(d)_min |
| ETX(s->d)_max | ETX(n->d)_min |
|------------------------------------|
|------------------------------------|
| Source Address s |
| Source Address s |
Line 37: Line 39:
| .... |
| .... |
|------------------------------------|
|------------------------------------|
| Payload |
| ... |


d - Address of the final Destination
d - Address of the final Destination
s - Address of the source (sender)
s - Address of the source (sender)
ETX(d)_max - cuml. ETX from s to d
ETX(s->d)_max - cuml. ETX from s to d
ETX(d)_min - Min(cuml. ETX from Neighbor(s) to d)
ETX(n->d)_min - Min(cuml. ETX from n = Neighbor(s) to d)
Aorta Route - Best route from s to d (hop-count) with ETX values
Aorta Route - Best route from s to d (hop-count) with ETX values

=== Parameter ===

ttime(ack) - transmission time for an ack
awnd - Ack window (fixed size, awnd = n * (c+ttime(ack))

=== Arbeitsweise ===

* Knoten s sendet einen Frame mit dem oben angegebenen Format
* Der Frame f wird von einer Teilmenge der Nachbarn der Knoten s empfangen. Sei also Knoten k ein Knoten dieser Teilmenge.
** if ETX(k->d) > ETX(s->d)_max then drop f
** if ETX(k->d) < ETX(n->d)_min then drop f (evtl Aufheben für andere Layer wie NC)
** Das awnd wird in (ETX(s->d)_max - ETX(n->d)_min) slots aufgeteilt und Knoten k scheduled sein Ack für den Slot slt=(ETX(k->d) - ETX(n->d)_min).
** Knoten k lauscht bis slt, ob 'höherwertige' acks auf dem medium liegen (Gleiches Vorgehen wie bei ExOR, die Forwarding Node wird zu s propagiert)
** Zum Zeitpunkt slt sendet k sein Ack, wenn nicht gerade das Medium belegt ist
** Ist das Medium belegt, wird f gedroppt (Beschränken der Größe des dyn. Candidate Set, evtl Aufheben für später).
** Kennt k das Ziel d nicht, kann es keine ETX(k->d) berechnen.
*** Die Aorta Route liefert eine Anzahl an Join Points, für die ETX bekannt ist (mitgeschickt wird).
*** Kennt Knoten k nun einen Knoten x der Aorta (und damit ETX(k->x)), kann er rechnen: ETX(k->d) = ETX(k->x) + ETX(x->d)
** Empfängt ein anderer Knoten das Datenpaket von s, so updatet er seinen NAV-Vektor und schützt damit das awnd vor Kollisionen.

=== Vorteile ===

* Beseitigt die vorzeitige Festlegung auf ein Candidate Set.
* Höherer Grad an Opportunismus

=== Probleme & Offene Fragen ===

* Es kann nicht ausgeschlossen werden, dass nicht zwei Empfänger zum gleichen Zeitpunkt acken
** Besonders wichtig bei grobmaschigen Netzen
** Evtl. Lösungsansatz: Das awnd muss eine Mindestanzahl Slots haben
* Wie groß muss awnd sein?


== Resultate der Messungen im internen Testbed ==
== Resultate der Messungen im internen Testbed ==

Revision as of 17:44, 8 February 2006

Hardware

Software

Simulation

Early Warning

Devilish Opportunistic Routing

  • Beobachtung: Kein Candidate Set ist eine große Einschränkung des Opportunismus.
  • Idee: Das Candidate Set wird nicht vorgegeben, sondern 'dynamisch' ermittelt.

Dadurch entstehen die folgenden Probleme:

  • Richtung: Das Paket muss mit jedem Hop einen Fortschritt richtung Final Destination machen.
  • Ack Ordering: Die Menge der Knoten, die das Paket empfangen haben, muss sich auf eine kollisionsarme Ack-Reihenfolge einigen.
  • Größe das Candidate Set: Potentiell sind jetzt alle Nachbarn Kandidaten. Das Ack-Fenster muss aber beschränkt bleiben (Das Ack hat feste Größe und feste Übertragungszeit.)

Frame Format

Ein Knoten s sendet folgendes Frame:

|------------------------------------|
| Final Destination d                |
|------------------------------------|
| ETX(s->d)_max | ETX(n->d)_min      |
|------------------------------------|
| Source Address s                   |
|------------------------------------|
| ...                                |
| Aorte Route                        |
| ....                               |              
|------------------------------------|
| Payload                            |
| ...                                |
d - Address of the final Destination
s - Address of the source (sender)
ETX(s->d)_max - cuml. ETX from s to d
ETX(n->d)_min - Min(cuml. ETX from n = Neighbor(s) to d)
Aorta Route - Best route from s to d (hop-count) with ETX values

Parameter

ttime(ack) - transmission time for an ack
awnd - Ack window (fixed size, awnd = n * (c+ttime(ack))

Arbeitsweise

  • Knoten s sendet einen Frame mit dem oben angegebenen Format
  • Der Frame f wird von einer Teilmenge der Nachbarn der Knoten s empfangen. Sei also Knoten k ein Knoten dieser Teilmenge.
    • if ETX(k->d) > ETX(s->d)_max then drop f
    • if ETX(k->d) < ETX(n->d)_min then drop f (evtl Aufheben für andere Layer wie NC)
    • Das awnd wird in (ETX(s->d)_max - ETX(n->d)_min) slots aufgeteilt und Knoten k scheduled sein Ack für den Slot slt=(ETX(k->d) - ETX(n->d)_min).
    • Knoten k lauscht bis slt, ob 'höherwertige' acks auf dem medium liegen (Gleiches Vorgehen wie bei ExOR, die Forwarding Node wird zu s propagiert)
    • Zum Zeitpunkt slt sendet k sein Ack, wenn nicht gerade das Medium belegt ist
    • Ist das Medium belegt, wird f gedroppt (Beschränken der Größe des dyn. Candidate Set, evtl Aufheben für später).
    • Kennt k das Ziel d nicht, kann es keine ETX(k->d) berechnen.
      • Die Aorta Route liefert eine Anzahl an Join Points, für die ETX bekannt ist (mitgeschickt wird).
      • Kennt Knoten k nun einen Knoten x der Aorta (und damit ETX(k->x)), kann er rechnen: ETX(k->d) = ETX(k->x) + ETX(x->d)
    • Empfängt ein anderer Knoten das Datenpaket von s, so updatet er seinen NAV-Vektor und schützt damit das awnd vor Kollisionen.

Vorteile

  • Beseitigt die vorzeitige Festlegung auf ein Candidate Set.
  • Höherer Grad an Opportunismus

Probleme & Offene Fragen

  • Es kann nicht ausgeschlossen werden, dass nicht zwei Empfänger zum gleichen Zeitpunkt acken
    • Besonders wichtig bei grobmaschigen Netzen
    • Evtl. Lösungsansatz: Das awnd muss eine Mindestanzahl Slots haben
  • Wie groß muss awnd sein?

Resultate der Messungen im internen Testbed

Todo

  • JiST
    • Multichannel-Mac
    • Javis & EventGUI
    • Measured, predefined Link Quality in Fields (Ersetzen des Ausbreitungsmodells gegen unsere Meßdaten)
    • How to measure with JiST/SWANS (generate diagrams & co.)
    • ExOR: slotted ack
      • ns2:
    • (Network Coding)


  • Administrations-Tools für das Indoor-Testbed
  • Telnet-Zugang auf Knoten des Indoor-Testbed ohne Ethernet
  • Methode zur Durchführung von Tests im Indoor-Testbed
Each experiment measures throughput between 65 randomly
selected node pairs. First, the nodes broadcast 1500-
byte packets every ten seconds for ten minutes and report
the measured delivery probabilities from all other nodes to
a central server. The server distributes this information
to all the nodes. The measurements are used to compute
ETX metrics and traditional routes. Next, the server contacts
each of the 65 node pairs in sequence, telling the pair
to measure the time required to transfer a 1.0 megabyte
¯le using traditional routing, then to wait 15 seconds, then
to measure the time required to transfer 1.1 megabytes using
ExOR. The evaluation does not use the combination of
ExOR and traditional routing, so the extra 0.1 megabyte is
to compensate for the 10% of packets which may not have
been delivered ordinarily. The reported throughput is one
megabyte divided by the total time required to transfer the
data. Every twenty minutes, the central server suspends the
experimental runs to recollect the link loss measurements.
During the experiment, existing Roofnet routing and user
tra±c are present.