[Wien] Firmware Doku

[Harald Geyer]

Hallo,

> Hat schon markus kittenberger hm, sagen wir experimentell bewiesen,  
> dass das genau so viel bringt wie die summe.
> Es werden bei uns im netz fast die selben routen zum subway ausgewaehlt.
> Zumindest sagt das sein javascript+SVG code.
> Interessant, ich verstehs auch nicht ganz. Das muss entweder ein bug  
> in der berechnung sein, oder bei uns einfach bei den ETX werten und  
> links die wir so haben, zufaellig fast die selben routen ergeben.

Ist doch eigentlich naheliegend:

Betrachten wir für einen Moment einmal ein Netz mit guten ETX Werten
(also zwischen 1 und 2). Eine (z.B. 3 Hop) Route sei durch die 
Werte A, B und C beschrieben, dann können wir auch schreiben
A = 1 + a
B = 1 + b
C = 1 + c
mit a, b, c jeweils zwischen 0 und 1.

Damit bekommen wir für eine
Additionsmetrik: A+B+C = 3 + a + b + c
Multiplikationsmetrik: A*B*C = (1+a)*(1+b)*(1+c) = 1 + a + b + c +ab+ac+bc+abc

Es ist zu beachten, dass a, b, c zwischen 0 und 1 sind. Dadurch sind die
hinteren Terme, wo mehr als einer der Faktoren a, b, c vorkommt sehr
klein und können vernachlässigt werden. Was also übrig bleibt ist, dass
in der Multiplikationsmetrik der Pfad(A,B,C) die Gestalt 1 + a + b + c
hat, also genau wie in der Additionsmetrik, aber die Information dass
es sich um eine 3-Hop Route handelt, ist nicht mehr berücksichtigt -- Loops
sind wahrscheinlich die Folge.

Im realen 0xff Netz ist die Situation etwas verändert, weil nicht alle
Links einen guten ETX haben. Eine typische Route vom subway ausgehend
sieht ca. so aus: Die ersten paar Links (z.B. 5 GHz) ein guter
ETX und erst der letzte Hop hat vielleicht einen schlechten ETX. Was
in diesem Fall passiert ist, dass die Multiplikationsmetrik dem Hop
mit dem hohen ETX mehr Gewicht gibt als den anderen und der Gesamtlänge
der Route. Es werden also Routen bevorzugt, bei denen der letzte Hop
möglichst guten ETX hat -- da die meisten Knotenbetreiber ihre Antennen
so ausrichten, dass sie einen möglichst guten ETX zu einem Knoten mit
kurzem Uplink haben, dürfte dieser Effekt in der Simulation mit dem
bestehenden Netz nicht weiter auffallen...

Man kann die beiden Metriken auch recht einfach mathematisch
interpretieren:

Die Additionsmetrik ist ihrer Art nach eine Kostenfunktion. Jeder
Link hat seine Kosten und die Kosten eines Pfades sind gleich der
Summe der Kosten der einzelnen Links. Wenn man davon ausgeht, dass
das Wachstum des Netzes vor allem durch die vorhandene air time 
begrenzt ist, dann ist dieser Ansatz recht gut, weil jeder Versuch
ein Frame zu senden tatsächlich Kosten für das Netz verursacht (falls
der Frame über Funk geht). Die ETX-Metrik ist immerhin eine grobe
Näherung einer EAT (estimated air time) Metrik - vielleicht
wird/würde die ETT-Metrik etwas besser sein, ich erwarte aber keinen
wesentlichen Unterschied. Viel erfolgversprechender scheint mir die
Topologie zu vereinfachen, wofür Markus Kittenberger auch schon
eine (im 0xff Netz laufende!) proof of concept Implementation hat.

Die Multiplikationsmetrik ist keine Kostenfunktion (da käme man ja
auf Quadratkosten und Kubikkosten, was sollte denn das sein), sondern
eine Wahrscheinlichkeit oder genauer der Kehrwert davon. (Dieser
Unterschied, ob Kehrwert oder nicht, ist egal, weil Kehrwertbildung
mit Multiplikation vertauscht). Was uns die Mulitplikationsmetrik
sagt ist nichts anderes als wie oft wir Daten über einen Pfad
schicken müssen, damit sie am anderen Ende im Mittel einmal ankommen.
Dabei macht sie aber einen großen Fehler: Sie vergisst, dass es am
Layer 2 Fehlerkorrektur und retransmit Mechanismen gibt. Wie
schwerwiegend dieser Fehler ist wird klar, wenn man bedenkt, dass ohne
Fehlerkorrektur am Layer 2 im Funknetz TCP/IP gar nicht sinnvoll
betreibbar wäre.

Liebe Grüße,
Harald