[WLANnews] Rubens Realisierungsidee zu dezentrale Suche in der Freifunk Wolke.

[Ruben Kelevra]

Hallo Christof,

Nun als erstes ist das sicher nicht meine Idee, im Grunde ist es eine
Anpassung von dem Echo-Algorithmus[1]. Ich hab eine Netzwerkanwendung
gerade in der Entwicklung und das dort verwendete Protokoll hab ich
grob umzeichnet und für den Anwendungsfall angepasst.

Am 7. April 2013 18:13 schrieb Christof Schulze <christof.schulze at gmx.net>:
> auf der Liste finden im selben Thread Diskussionen um Anforderungen an
> eine Suche und Diskussionen um Realisierungsformen einer Suche statt.
> Das sollten wir trennen, weshalb ich mit dieser Mail einen neuen Thread
> öffne.
DANKE! Fürs Trennen. :)

> Ich würde Deine Idee gern besser verstehen und möchte daher einige
> Fragen formulieren:
>> * Man installiert im Netzwerk Supernodes.
-Nun, hier muss ein Rechner mit LAN/WLAN oder über fastd mit einem der
Nodes/einem Gateway verbunden werden, damit er Zugang zum Mesh hat.
-Dann sollte im reservierbaren Bereich eine IP-Adresse reserviert
werden, entweder feste Zuweisung der Mac auf die IP oder eben
statische Configuration, das wäre Community-Abhängig.

>> * Die Supernodes machen sich untereinander bekannt.
Innerhalb der selben Broadcast-Domain erledigt das der Mulitcast
einmal die Stunde den jeder Supernode aussenden würde. Bei Netzwerken
die den Multicast blockieren oder in mehrere Subnetze aufgesplittet
sind, müsste das Multicast für diese Paketarten freigegeben werden,
bzw weitergeleitet werden zwischen den Subnetzen.

Andererseits kann man natürlich auch eine Wiki-Seite mit Supernodes
füttern, ein Git etc. So wie es schon bei Tinc für IC-VPN
Communityübergreifend passiert.

>> * Die Supernodes machen untereinander eine Reihenfolge aus.
Hierfür gibt es einige passende Algorithmen ... [2]

Und wenn der Ausfall eines Systems festgestellt wird währe wohl dieser
hier[3] passend.

>> * Jeder Supernode schickt einen Broadcast pro Stunde raus mit seinem
>>   Public Key.
> Wie sollten die ersten drei Punkte gelöst werden (Aushandeln der
> Supernodes, Bekanntmachung, Bildung der Hierarchie)? Wie machen das
> andere Netze/Protokolle z.B. Skype, Smb, Kazaa, ...? Daraus ergibt sich,
> wie viele Supernodes es geben kann.
Nun andere Netze machen das in lokalen Netzwerken größtenteils per
hundertfachem Broadcast die Stunde, das würden wir denke ich gerne
Vermeiden. Wenn du ein Konkretes Beispiel hast, was diesen Ansatz
verbessert könnten wir den natürlich diskutieren...

Zu deinen Beispielen:
Skype: Macht im lokalen Netzwerk nichts, ist propritär, brauchen wir
nicht drüber sprechen, weil wir eh nichts darüber wissen.
SMB: Versendet massenhaft Broadcast/Multicast und funktioniert
(meistens), aber nur in einem Subnetz. (AFAIK)
Kazaa: "Das Protokoll ist proprietär und aufgrund von
Verschlüsselungsalgorithmen bisher noch nicht voll bekannt."
--de.wikipedia.org

Die Menge an Supernodes wird die Dauer des Suchvorganges linear
bremsen. Allerdings auch Linear die Menge an Cache im Netzwerk erhöhen
und somit Suchergebnisse langfristig beschleunigen. Sollte ein
Supernode mit einem Suchergebnis ausfallen muss natürlich die Suche
neu gestartet werden. Das heißt um so mehr Supernodes um so höher die
Chance das ein Teil des Caches verloren geht.

>> - In den Routern wird eine Public-Keys-Liste konfiguriert, eine IP-Adresse
>> ist im eigenen Subnetz optional.
>> - Die Router indizieren die eigenen Dokumente.
>> - Die Router melden sich bei zwei der gültigen Supernodes und hinterlegt
>> dort seinen Public-Key und IP.
>> - Die Router aktualisieren ihren Eintrag beim Wechsel der IP, signiert mit
>> ihrem Schlüssel.
>> -Die Router melden sich nach 60 Minuten ohne Traffic zwischen Ihnen und den
>> beiden verwendeten Supernodes um zu bestätigen das sie noch aktiv sind.
>>   + Fällt dabei auf das einer der Supernodes nicht mehr zu erreichen ist
>> werden neue Verbindungen aufgebaut.
>> -Suchanfragen leiten die Router im Wechsel zu einem der beiden Supernodes.
>>   + Fällt dabei auf das einer der Supernodes nicht mehr zu erreichen ist
>> werden neue Verbindungen aufgebaut.
>> -Die Supernodes melden die Anfrage und eine Cachezeit (bis 24h) per
>> Flutungsalgorithmus an alle Supernodes bis sie das Handle auf die Anfrage
>> haben, dann:
>>   + Gilt dieser Supernode als Cache für diese Anfrage.
>>   + Fragt dieser Supernode die Clients lokal, sendet seine Liste mit
>> Clients an den Supernode mit der niedrigsten Nummer, dieser:
>>      - Sendet die Anfrage an seine Clients und erweitert die Liste und
>> sendet diese an den nächsten Supernode.
>>        +Der Supernode mit dem Handle wird dabei übersprungen.
>>        +Der letzte Supernode sendet die Daten zurück.
>>        +Alle Clientantworten werden direkt an den fragenden Supernode
>> gesendet.
>>        +Supernode die keine Clients hinzufügen senden nichts an den
>> fragenden Supernode.
>>        +Der erste Supernode gibt die Daten an den Client aus.
>> -Fällt bei der Suche auf das ein Supernode fehlt wird dieser übersprungen
>> und die Info per Flutungsalgorithmus bekannt gemacht. Hierbei überprüfen
>> alle angesprochenden Supernodes bevor sie diese Information bestätigen dass
>> das aus ihrer Sicht auch so ist.
> * Was genau ist die Funktion der Supernodes?
Dezentrale Caches für Suchanfragen. Außerdem einen beschleunigten
Zugriff auf viele Rechner, da diese im besten Fall direkt auf dem
Gateway laufen und alle Nodes (im Besten Fall) mit einem Hop erreichen
können.

Des weiteren sind sie die Computer die die Suchanfragen einleiten, das
heißt jeder Node der Suchen möchte muss einen seiner Supernodes
ansprechen.

> * Wo sind die Daten gespeichert, die die Suchergebnisse darstellen? Auf
>   den Clients?
Die Suchergebnisse werden auf dem Supernode zwischengespeichert der
das Handle darauf erlangt hat, per Flooding. Das heißt alle Supernodes
wissen auf welchem Supernode die gecachte Anfrage liegt.

Sofern der Timeout nicht abgelaufen ist wird das gecachte Ergebnis von
diesem Supernode an den Supernode der die Suche einleitet gesendet.

Sollte der Supernode der den Cache für die Anfrage hält nicht
erreichbar sein muss der Supernode der die Suche ausführen möchte dies
per Flooding bekannt machen und damit direkt den nächsten Lock auf die
Suchenanfrage erhalten.

Dies dürfen andere Supernodes natürlich nur quittieren wenn sie den
Supernode der nicht erreichbar ist, ebenfalls als nicht erreichbar
einschätzen. (hier müsste noch gefrickelt werden, damit nicht 100
Supernodes einen überlasteten Rechner vollkommen blockieren).

> * Dein Entwurf sieht Caching auf Supernodes vor. Was genau wird
>   gecached?
Jede Suchanfrage wird gecacht. Auf dem Supernode der als erstes die
Suche angestoßen hat, und somit das Lock erhalten hat.

Wenn das Caching nicht mehr möglich ist, weil der Speicher nicht mehr
ausreicht um die Timeout-Zeit zu erfüllen muss der Lock natürlich
aufgegeben werden und das dem Netzwerk bekannt gemacht werden, damit
die anderen Supernodes den Eintrag "$suchanfrage"->Supernode aus ihrem
Speicher löschen.

> * Woher weiß der Nutzer, wo er seine Suchanfrage absetzen kann?
Der Nutzer kann seine Anfrage an jeden Supernode absetzen.

Im Idealfall wäre das User Interface der Router selbst mit einer
HTML-Seite, eine Suchfenster wird dargestellt und wenn der Benutzer
eine Suche anstoßen möchte sendet der Node das an einen seiner beiden
Supernodes, und die kümmern sich um das Ergebnis, das der Router dann
hübsch formatiert wieder ausgibt.

> * Wo findet eine Bewertung der Suchergebnisse und die damit
>   zusammenhängende Sortierung nach Relevanz statt?
Das fehlt.

Interessant wäre natürlich ein offenes System zu schaffen was alle
Suchergebnisse direkt dezentral nach Relevanz sortiert und die
Supernodes diese nur noch abgrasen müssen, an den fragenden Supernode
schicken, der Sortiert die Ergebnisse lokal zusammen, speichert sie im
Cache und sendet sie an den Benutzer.

Problem wäre wohl (irgendwann) Spam.... aber ich denke da muss noch
einiges an Zeit vergehen.

Einen Suchalgorithmus zu schreiben ist ne Ecke mehr Arbeit, aber ich
denke da gibt es schon einges auf OpenSource-Basis was auch mit wenig
Arbeitspeicher, dank z.B. Binären Bäumen auf der Festplatte schnell zu
Ergebnissen kommt.



Ich hoffe ich konnte ein bisschen Klarheit schaffen.

Lieben Gruß aus Wermelskirchen

Ruben