MathiasKurthRestricted: Difference between revisions
Jump to navigation
Jump to search
(→ExOR) |
|||
(34 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
== Papers == |
|||
* [[EWS Papers]] |
|||
== Hardware == |
== Hardware == |
||
Line 10: | Line 6: | ||
* [[Kernel Stuff]] |
* [[Kernel Stuff]] |
||
* [http://www.gfz-potsdam.de/geofon/new/ge_inf.html SeisComP] ([ftp://ftp.gfz-potsdam.de/pub/pub/home/st/GEOFON/software ftp], [[:Image:Seiscomp-2_1.pdf|docu]]) |
|||
== Simulation == |
== Simulation == |
||
* Network Simulator ns2 [http://www.isi.edu/nsnam/ns/] |
|||
* JNS (ns2 ported to Java) [http://homepages.cs.ncl.ac.uk/einar.vollset/home.formal/jns.html] |
|||
* [[Java in Simulation Time]] |
* [[Java in Simulation Time]] |
||
* Network Animator Nam [http://www.isi.edu/nsnam/nam/] |
|||
* Javis [ftp://cs.ucl.ac.uk/nets/src/jns/javis-0.2/] |
|||
* Javis4SWANS [http://www.cs.technion.ac.il/~gabik/Javis4Swans.html] |
|||
* iNspect [http://merkur/svn/brn/archives/iNSpect-3.3/] |
|||
== Early Warning == |
== Early Warning == |
||
* [[Ideas on EWS]] |
* [[Ideas on EWS]] |
||
== ExOR == |
|||
* Statisches Candidate-Set kann bei einem Reverse Multicast gefählich werden. |
|||
* 3 Quellen wählen jeweils immer den gleichen Candidaten aus. |
|||
== 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.) |
|||
=== Hinweis === |
|||
* Unter ETX wird hier die Forward-Delivery-Ratio verstanden |
|||
=== Frame Format === |
|||
Ein Knoten s sendet folgendes Frame: |
|||
|------------------------------------| |
|||
| Final Destination d | |
|||
|------------------------------------| |
|||
| ETX(n->d)_max | ETX(n->d)_min | |
|||
|------------------------------------| |
|||
| slots | awnd size | NAV | |
|||
|------------------------------------| |
|||
| Source Address s | |
|||
|------------------------------------| |
|||
| ... | |
|||
| Fallback Route | |
|||
| .... | |
|||
|------------------------------------| |
|||
| Payload | |
|||
| ... | |
|||
d - Address of the final Destination |
|||
s - Address of the source (sender) |
|||
ETX(n->d)_max - Max(cuml. ETX from n = Neighbor(s) to d) |
|||
ETX(n->d)_min - Min(cuml. ETX from n = Neighbor(s) to d) |
|||
slots - Number of slots in the ack window (comparable to backoff window) |
|||
awnd size - number of acks that fit into the ack window |
|||
Fallback Route - Best route from s to d (hop-count? etx?) with ETX values |
|||
=== Parameter === |
|||
ttime(ack) - transmission time for an ack |
|||
awnd - Ack window (fixed size, awnd = n * (c+ttime(ack)) |
|||
slots - discredition of the ack window size (#slots of awnd) |
|||
=== 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(n->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 slots Zeitschlitze aufgeteilt und Knoten k scheduled sein Ack für den Slot slt=(ETX(k->d) - ETX(n->d)_min)/slots. |
|||
** 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). |
|||
** Knoten k lauscht weiter bis das awnd abgelaufen ist (Idee: Vermeiden von Duplikate a la ExOR) |
|||
** Kennt k das Ziel d nicht, kann es nicht 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. |
|||
=== Optimierung: Vermeidung von Ack-Kollisionen === |
|||
* Der Sender passt die Größe und die Rasterisierung des Ack-Windows dynamisch an, um Kollisionen zu vermeiden. |
|||
* Ziel: Keine Kollisionen, diese werden zu Überlappungen aufgelöst. |
|||
* Methode: Histogramm der Rasterisierung (Diskretisierung des Ack-Window) |
|||
=== Vorteile === |
|||
* Beseitigt die vorzeitige Festlegung auf ein Candidate Set. |
|||
* Höherer Grad an Opportunismus |
|||
* Kandidaten des ExOR haben evtl. keine Route zum Ziel, wodurch weitere Route Discoveries nötig sind. Durch benutzen von Source-Routen als Fallback-Option ist (i.d.R.) fällt kein zusätzliches Discovery an. |
|||
* Verringertes Kollisions-Risiko durch Optimierung des Senders (Histogramm-Ansatz) |
|||
* Potentielles Kollisions-Risiko der Acks kann durch höhere Layer behandelt werden (speziell Network Coding). Der Sender stellt ein Paket zurück, für das er kein Ack bekommen hat (z.B. weil Ack kollidiert sind). Dieses Paket kann nun durch NC später implizit geackt werden (Übertragung des Hashes Piggy-Bag). |
|||
=== Probleme & Offene Fragen === |
|||
* Es kann nicht ausgeschlossen werden, dass nicht zwei Empfänger zum gleichen Zeitpunkt acken |
|||
** Besonders wichtig bei sparse meshs |
|||
** Evtl. Lösungsansatz: Das awnd muss eine Mindestanzahl Slots haben |
|||
* Wie groß muss awnd sein? |
|||
* Wie groß muss slots sein? |
|||
* Für Fallback Route: hopcount oder etx? |
|||
* Koexistenz mit 802.11 Netzen (Collision Avoidance, NAV) |
|||
* Abhängigkeit von ETX |
|||
** Bootstrap, Burstiness |
|||
** Inkonsistenzen, Propagation Delays |
|||
== Resultate der Messungen im internen Testbed == |
== Resultate der Messungen im internen Testbed == |
||
Line 23: | Line 119: | ||
* [[Measurement Results]] |
* [[Measurement Results]] |
||
* [[Auswertung der Delivery Ratio Messung]] |
* [[Auswertung der Delivery Ratio Messung]] |
||
* [[Performance of a DHT Implementation in the BRN Indoor Testbed]] |
|||
== Todo == |
== Todo == |
||
* JiST |
|||
** Measured, predefined Link Quality in Fields (Ersetzen des Ausbreitungsmodells gegen unsere Meßdaten) |
|||
** How to measure with JiST/SWANS (generate diagrams & co.) -> java graph package gov.s... |
|||
** Vergleich McExOR - ExOR |
|||
** Vergleich McExOR orig - McExOR mit Kanaladaption |
|||
** Javis & EventGUI |
|||
** DeOR Impl + Performance |
|||
*** ns2: |
|||
** (Network Coding) |
|||
* Administrations-Tools für das Indoor-Testbed |
* Administrations-Tools für das Indoor-Testbed |
||
Line 51: | Line 159: | ||
During the experiment, existing Roofnet routing and user |
During the experiment, existing Roofnet routing and user |
||
tra±c are present. |
tra±c are present. |
||
* JiST |
|||
** Multichannel-Mac |
|||
** Network Coding |
|||
** Ersetzen des Ausbreitungsmodells gegen unsere Meßdaten |
Latest revision as of 13:01, 23 March 2006
Hardware
Software
Simulation
- Network Simulator ns2 [1]
- JNS (ns2 ported to Java) [2]
- Java in Simulation Time
- Network Animator Nam [3]
- Javis [4]
- Javis4SWANS [5]
- iNspect [6]
Early Warning
ExOR
- Statisches Candidate-Set kann bei einem Reverse Multicast gefählich werden.
- 3 Quellen wählen jeweils immer den gleichen Candidaten aus.
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.)
Hinweis
- Unter ETX wird hier die Forward-Delivery-Ratio verstanden
Frame Format
Ein Knoten s sendet folgendes Frame:
|------------------------------------| | Final Destination d | |------------------------------------| | ETX(n->d)_max | ETX(n->d)_min | |------------------------------------| | slots | awnd size | NAV | |------------------------------------| | Source Address s | |------------------------------------| | ... | | Fallback Route | | .... | |------------------------------------| | Payload | | ... |
d - Address of the final Destination s - Address of the source (sender) ETX(n->d)_max - Max(cuml. ETX from n = Neighbor(s) to d) ETX(n->d)_min - Min(cuml. ETX from n = Neighbor(s) to d) slots - Number of slots in the ack window (comparable to backoff window) awnd size - number of acks that fit into the ack window Fallback Route - Best route from s to d (hop-count? etx?) with ETX values
Parameter
ttime(ack) - transmission time for an ack awnd - Ack window (fixed size, awnd = n * (c+ttime(ack)) slots - discredition of the ack window size (#slots of awnd)
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(n->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 slots Zeitschlitze aufgeteilt und Knoten k scheduled sein Ack für den Slot slt=(ETX(k->d) - ETX(n->d)_min)/slots.
- 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).
- Knoten k lauscht weiter bis das awnd abgelaufen ist (Idee: Vermeiden von Duplikate a la ExOR)
- Kennt k das Ziel d nicht, kann es nicht 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.
Optimierung: Vermeidung von Ack-Kollisionen
- Der Sender passt die Größe und die Rasterisierung des Ack-Windows dynamisch an, um Kollisionen zu vermeiden.
- Ziel: Keine Kollisionen, diese werden zu Überlappungen aufgelöst.
- Methode: Histogramm der Rasterisierung (Diskretisierung des Ack-Window)
Vorteile
- Beseitigt die vorzeitige Festlegung auf ein Candidate Set.
- Höherer Grad an Opportunismus
- Kandidaten des ExOR haben evtl. keine Route zum Ziel, wodurch weitere Route Discoveries nötig sind. Durch benutzen von Source-Routen als Fallback-Option ist (i.d.R.) fällt kein zusätzliches Discovery an.
- Verringertes Kollisions-Risiko durch Optimierung des Senders (Histogramm-Ansatz)
- Potentielles Kollisions-Risiko der Acks kann durch höhere Layer behandelt werden (speziell Network Coding). Der Sender stellt ein Paket zurück, für das er kein Ack bekommen hat (z.B. weil Ack kollidiert sind). Dieses Paket kann nun durch NC später implizit geackt werden (Übertragung des Hashes Piggy-Bag).
Probleme & Offene Fragen
- Es kann nicht ausgeschlossen werden, dass nicht zwei Empfänger zum gleichen Zeitpunkt acken
- Besonders wichtig bei sparse meshs
- Evtl. Lösungsansatz: Das awnd muss eine Mindestanzahl Slots haben
- Wie groß muss awnd sein?
- Wie groß muss slots sein?
- Für Fallback Route: hopcount oder etx?
- Koexistenz mit 802.11 Netzen (Collision Avoidance, NAV)
- Abhängigkeit von ETX
- Bootstrap, Burstiness
- Inkonsistenzen, Propagation Delays
Resultate der Messungen im internen Testbed
- Measurement Results
- Auswertung der Delivery Ratio Messung
- Performance of a DHT Implementation in the BRN Indoor Testbed
Todo
- JiST
- Measured, predefined Link Quality in Fields (Ersetzen des Ausbreitungsmodells gegen unsere Meßdaten)
- How to measure with JiST/SWANS (generate diagrams & co.) -> java graph package gov.s...
- Vergleich McExOR - ExOR
- Vergleich McExOR orig - McExOR mit Kanaladaption
- Javis & EventGUI
- DeOR Impl + Performance
- 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
- z.B. [7]
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.