Frage zu Ad-hoc-Netzwerk-Architektur

[Locusta]

Ich beschäftige mich momentan ein bisschen mit Routing-Verfahren. Speziell geht es um Routing in Funknetzwerken, wo sich jederzeit neue Klienten einwählen und verschwinden.

Um das ganze besser anschaulich zu verstehen definiere ich einfach mal ein paar Dinge:
- ein Paket mit Informationen ist 100 Bit groß, egal mit welcher INformation es "gefüllt" ist
- die Bandbreite die zur Verfügung steht sind 100 MBit/s
- jeder Klient will je Sekunde 100 Pakete verschicken

=> maximal 1.000.000 Pakete pro Sekunde können übertragen werden.

So wie ich es verstanden habe gibt es verschiedene Prinzipen für kabellose Netzwerke:

1: anmelden an einem Klient, der das zentrale Routing übernimmt
2: alle Klienten kommunizieren untereinander und jeder übernimmt das Routing

Der erste Fall ist relativ langweilig, deswegen geht es im Grunde eigentlich nur um den 2. Fall. Der sieht in etwa so aus:


(Quelle: Wikipedia)

Zum 2. Verfahren gibt es wiederum mehrere Möglichkeiten die Organisation zu übernehmen, dafür muss aber vorher "festgelegt" werden wer überhaupt dabei ist, sprich mit dem Netzwerk verbunden ist. Dazu sendet jeder jede Sekunde 1 Paket an alle, dass er "dabei" ist, sprich es sind nur noch 99 Pakete zum eigentlichen Informationstransport übrig.

Nun gibt es mehrere Möglichkeiten das Routing zu übernehmen:
Die einfachste Lösung wäre, wenn jeder jede Information einfach an alle weitersendet. Jedes Paket wird also empfangen und auch weitergeleitet. Zusätzlich spaart man sich das Paket, welches die Information der Teilnehmer enthält, weil es jeder alles Empfängt. Leider sinkt die "maximale Anzahl an Paketen unterwegs" und somit auch die "maximale Zahl an Klienten". Damit nicht instantan die komplette Bandbreite verstopft ist, muss nachdem der Empfänger das Paket empfangen hat ein weiteres Paket losschicken worin gesagt wird, dass das Paket nun nicht mehr weitergesendet werden muss. Dieses letzte Paket wird nur 1x weitergeschickt, nachdem es empfangen wurde, wird es ein 2. mal empfangen wird es nicht mehr weitergeschickt. Also werden 3 Pakete insgesammt verschickt, sprich es können nur noch 333.333 Pakete real verschickt werden, vorausgesetzt das Paket wird gleich beim 1. mal empfangen. Ist dies nicht der Fall sinkt die Rate auf (1.000.000)/(3^n), wobei n die Anzahl der Versuche zur Datenübermittlung ist. Bei x Teilnehmern beträgt die maximale Datenübertragungsrate also nur noch (1.000.000)/(x*3^n). Also beträgt die maximale Anzahl an Teilnehmern x(n)=(10000)/(3^n). Bei einem Versuch wären es also 3333 Teilnehmer und schon nur bei 7 Versuchen nur noch 4 Teilnehmer.

Fazit: Keine akzeptable Lösung


Wenn man noch die Information hinzunimmt, wie weit jemand von jemandem entfernt ist kann eine durchaus größere Anzahl an Nutzern erreicht werden. Nun kann man dies wiederum in zwei Verfahren unterteilen. Entweder wird die Information immer zum nächstgelegenen geschicht aber nicht zu dem, von dem die Information kam oder es wird vorher ausgerechnet an wen ein paket geschickt werden muss, damit es den kürzesten Weg nimmt. Empfängt trotzdem jemand ein Paket, welches nicht an ihn gerichtet ist, wird es nicht weitergeleitet.


Nun gibt es noch viele andere Möglichkeiten zu routen. Mein Problem ist, dass es laut Wikipedia momentan mehr als 70 verschiedene Entwürfe für die Kommunikation innerhalb eines Netzwerks gibt. Das sind ein paar viele um sie alle zu kennen, geschweige denn die genauen Unterschiede zu kennen - zumindest momentan auf meinem Wisstensstand.
Im Grunde suche ich eine Möglichkeit mit möglichst vielen Teilnehmern möglichst viele Informationen zu übertragen. Als "zusätzliche Information" ist nur die Empfangsstärke der umliegenden Teilnehmer vorhanden. Kennt jemand so eine Architektur, mit der so etwas möglich ist?

[Thyrfing]

Peer to Peer

[Locusta]

Wie überträgt denn Peer to Peer die Informationen? Peer to Peer ist jat quasi "nur" der Überbegriff um das System an sich zu beschreiben. Im Grunde ist das Paket, welches von A nach B übertragen werden soll ja auch eine Art Peer to Peer Verbindung. Die Frage ist aber wie die Pakete geroutet werden. Das Netzwerk besteht ja leider nicht nur aus A und B sondern auch noch aus hunderten weiteren Teilnehmern. A und B müssen auch nicht umbedingt überhaupt in Funkreichweite liegen, so dass eben wie oben in dem Bild die Daten über mehrere zusätzliche Teilnehmer verschickt werden müssen.

Das System, welches sich dahinter verbirgt um einen möglichst einfachen Aufbau aber auch gleichzeitig möglichst hohe Datendichte zu ermöglichen interessiert mich.

[Thyrfing]

http://de.wikipedia.org/wiki/Peer_to_peer

[Locusta]

Ja, den Artikel kenne ich, nur wird dort meine Frage auch nicht beantwortet.

Es geht bei meinem Problem um ein Netzwerk, welches dezentral verwaltet wird. Wie findet der Datenaustausch der Teilnehmer untereinander statt? Klar, mit Peer to Peer aber ich meine eine Ebene tiefer. Die Antwort "aus der Steckdose" auf die Frage: "Woher kommt der Strom?" ist für mich momentan genau so hilfreich.

PS: Ich frage mich wirklich ob du nicht derjenige bist, der versucht mich zu verarschen.

[Thyrfing]

PS: Ich frage mich wirklich ob du nicht derjenige bist, der versucht mich zu verarschen.

Nein, die Antwort war absolut ehrlich gemeint.

Ein Seeder (der mit der Quelldatei) lässt andere Benutzer in seinem "Empfangsbereich" auf die Datei zugreifen und laden. Ist die Datei in Bruchstücken bereits auf den anderen Rechnern angekommen, können weitere Personen, die eventuell nicht an den Seeder kommen, also an die Quelldatei, wiederum auf die Daten der anderen zugreifen.

Das spiegelt in meinen Augen exakt die Lösung wieder, die du suchst. Wenn du nun ein P2P Netzwerkserver aufbauen willst, musst du natürlich im Netz nach einer Anleitung suchen. Ich glaube nicht, dass hier irgendjemand eine Lösung aus der Tasche zaubert (ok, einer vielleicht, aber das ist jetzt mal außen vor).

[Thyrfing]

Ich habe mir jetzt mal den Artikel bei Wikipedia zu deinem Bild durchgelesen. Da sind alle Antworten drinnen. Es werden Routingverfahren erklärt, die deinen Ansprüchen entsprechen.
Lies ihn dir noch einmal aufmerksam durch.

Nachtrag: http://de.wikipedia.org/wiki/File_sharing auch sehr interessant

[Patrick]

Ich denke, daß P2P im grundsätzlichen schon die Lösung ist, die Locusta bräuchte. Nur gibt es AFAIK noch keine Implementation in der Form, daß eine "komplette" Netzwerkstruktur mit Routing etc. abgebildet wird. Wenn es um einzelne Dienste geht, gibt es vielleicht die eine oder andere Lösung, mir fällt dann spontan noch Bonjour ein, ohne zu wissen, wie man das in einem P2P-Netz einsetzen könnte.

Wenn ich das richtig verstanden habe, geht es im Endeffekt darum, daß irgendein Peer (oder sogar mehrere) eine Verbindung zum Internet hat und der eigene Peer sich den Weg dahin quasi selbständig sucht.

[mbs]

Hm, hört sich an wie eine Studienarbeit in der Vorlesung "Rechnernetze".  

In der Aufgabenstellung sehe ich aber mehrere offene Fragen. Zum einen, warum man annehmen kann, dass die effektive Bandbreite im gesamten Netz konstant ist, obwohl es Teilnehmer gibt, die nicht direkt miteinander kommunizieren können. Die Bandbreite wird nur unter Partnern im umliegenden Empfangsbereich aufgeteilt. Da sich die Position der Teilnehmer offenbar ändern kann, haben wir in den einzelnen Ästen des Netzes völlig unterschiedliche Paketraten.

Zum anderen ist unklar, an wen überhaupt die Nutzdaten gesendet werden. Will jeder immer wirklich alle anderen erreichen, oder nur bestimmte Partner, und falls ja, ist es gleichwahrscheinlich, dass ein beliebiger Client x seine Daten an einen anderen Client y sendet?

Peer-to-Peer wäre eine Lösung für das Spezialproblem, das eine bestimmte Information an alle Teilnehmer des Netzes verteilt werden muss. Sobald es aber um beliebige Netzwerkkommunikation geht, muss erst einmal das Routing-Problem gelöst werden, also die Frage "existiert der Zielpunkt für ein Paket überhaupt und wenn ja, wie kommt das Paket dorthin". Das sind zwei völlig unterschiedliche Dinge.

[Locusta]

Ok, vielleicht sollte ich alles erklären:

Es geht um eine tatsächliche Anwendung. Wir haben eine Art "Hardwarepraktikum", wo wir jeder ein eigenes kleines Projekt haben. Diese Projekte können wir mehr oder eher weniger freiwillig auswählen. Ich wurde der Robotik-Gruppe zugewiesen. Meine Aufgabe hier ist es mir etwas zu überlegen und zu basteln wie man im ISM-Band bei ca. 433 Mhz eine Art Ad-hoc-Netzwerk betreiben kann.

Die konkrete Anwendung besteht darin, dass auf einer ebenen Fläche Tonnen herumstehen. 5 Roboter kommunizieren untereinander und auch die TOnnen. Die Tonnen haben RGB-LEDs eingebaut und können ihre Farbe ändern, wenn bestimmte Sachen passieren, z.B. ein Roboter eine Tonne einsammelt oder die Tonnen untereinander kommunizieren. Im Grunde ist es ein Spiel Roboter vs. Tonnen. Die 5 Roboter müssen 10/15/20 Tonnen einsammeln und an einen Ort bringen. Schaffen die Roboter es nicht innerhalb einer vorgegebenen Zeit alle Tonnen einzusammeln haben sie verloren. Die Roboter kommunizieren über Licht miteinander und die Tonnen via Funk. Die Funkreichweite der Tonnen ist sehr begrenzt (ca. 50cm Durchmesser). Weil das Spielfeld zu groß ist als das alle Tonnen in der Reichweite voneinander stehen, ist es nötig, dass die Tonnen untereinander als Ad-Hoc-Netzwerk kommunizieren. Wird eine Tonne eingesammelt teilt sie dies den anderen Tonnen mit und diese versuchen dann die anderen Roboter dazu zu bewegen, dass die Tonne losgelassen wird.

Meine Aufgabe an den Tonnen ist es ein möglichst effizientes Verfahren zu verwenden um theoretisch mindestens 65536 Tonnen auf einem Spielfeld haben zu können. Ob dieses sehr theoretische Konzept der blinkenden Tonnen jemals überhaupt in einer echten Anwendung verwendet werden ist fraglich aber das ist auch nicht meine Aufgabe über Sinn bzw. Unsinn der Aufgabe nachzudenken.

Meine Idee war es nun jeweils 4 Tonnen am Anfang in je eine der Ecken des Spielfeldes zu stellen um eine Art Nullung zur relativen Positionsbestimmung über die empfangene Feldstärke zu machen. Somit wären die Tonnen in der Lage ihre jeweilige Position zu bestimmen und so könnte man eine Art geodaten-basierendes-System verwenden. Eine Alternative wäre wiederum die Empfangsstäke zu messen und dann über die Empfangssärke das ganze Routen zu lassen, wenn wir die Tonnen nicht so hinstellen dürfen wie wir wollen.

Vielleicht kommt die Frage auf, warum überhaupt geroutet werden muss: Die Tonnen dürfen nur alle 3 Sekunden je eine Sekunde lang leuchten, somit muss vorher "ausdiskutiert" werden, welche Tonne nun wie leuchten soll und vor allem wann. Leider reagieren die Roboter wenn sie eine Tonne eingesammelt haben nicht mehr auf Befehle von den Tonnen, nur noch von den anderen Robotern. Also muss die eingesammelte Tonne den anderen mitteilen, dass sie gerade "geraubt" wird. Zusätzlich gibt es eine Art "Regelwerk" welches besagt wann auf was die Roboter reagieren. Die Strategie der Roboter ist es jeweils eine Tonne von den anderen zu isolieren, damit sie nicht mehr in der Lage ist zu kommunizieren.

Ich hoffe das hat die Frage geklärt, warum ich eine so komische Frage gestellt habe.

[Nachtrag]
Falls die Frage kommt, wie lange Zeit ich dazu habe: Das Praktikum beginnt erst im nächsten Semester, nur wurde uns geraten uns vorher mit unserem Thema zu beschäftigen, damit wir möglichst bald anfangen können zu Arbeiten. Der eigentliche "Kampf" findet irgendwann im Februar statt.

[Thyrfing]

Auch wenn ich auf die Schnelle nichts dazu sagen kann, aber diese Erklärung ist eindeutig besser zu verstehen, als die 5 Seiten, die du vorher formuliert hast. Evtl. beschränkst du dich demnächst einfach auf die Aufgabenstellung. Zumindest bei diesen Fragen, denn wenn du bereits eine Art Lösung angeschaut hast, führst du alle anderen auf das Glatteis.

Nun, wo ich jetzt so schreibe, fällt mir Blue Tooth dazu ein. Das ist in der Lage Ad-hoc-Netze aufzubauen, allerdings müsste man nun noch rausfinden, wieviele Clients in solchen Netzen verbunden werden können.

[fränk]

Hm, hört sich an wie eine Studienarbeit in der Vorlesung "Rechnernetze".  

Manchmal macht mir mbs Angst!

[Thyrfing]

Artikel
Ein Bluetooth-Netzwerk (Piconet) kann bis zu 260 Teilnehmer umfassen, von denen acht Geräte gleichzeitig aktiv sein können (3bit adressiert) und 252 (8bit adressiert) währenddessen geparkt werden. Alle nicht aktiven Geräte können im Parkmodus die Synchronisation halten und auf Anfrage im Netz aktiviert werden. Das Piconetz besteht aus einem Master und bis zu sieben weiteren Teilnehmern (Slave). Der Master steuert die Kommunikation und vergibt Sendeslots an die Slaves. Ein Bluetooth-Gerät kann in mehreren Piconetzen angemeldet sein, allerdings nur in einem Netz als Master fungieren. Bis zu zehn Piconetze bilden ein Scatternet (von to scatter = ausstreuen), wobei die Teilnehmer untereinander in Kontakt treten können. Hierbei wird jedes Piconet durch eine unterschiedliche Frequency-Hopping-Folge identifiziert. Die Datenrate leidet in diesem Scatternet jedoch meist erheblich.
Dieses selbstorganisierende Funknetzwerk – Scatternet – ist bis heute nicht standardisiert. Dies ist dadurch begründet, dass bis heute kein Algorithmus entwickelt wurde, der allen Anforderungen an ein Scatternet gleichzeitig gerecht wird.

[Locusta]

Hm, hört sich an wie eine Studienarbeit in der Vorlesung "Rechnernetze". 

Fast richtig getroffen .

In der Aufgabenstellung sehe ich aber mehrere offene Fragen. Zum einen, warum man annehmen kann, dass die effektive Bandbreite im gesamten Netz konstant ist, obwohl es Teilnehmer gibt, die nicht direkt miteinander kommunizieren können. Die Bandbreite wird nur unter Partnern im umliegenden Empfangsbereich aufgeteilt. Da sich die Position der Teilnehmer offenbar ändern kann, haben wir in den einzelnen Ästen des Netzes völlig unterschiedliche Paketraten.

So habe ich es noch nicht gesehen. Ich dachte, dass die Bandbreite komplett aufgeteilt wird, was aber ja natürlich auch Unfug ist, wenn nicht alle Teilnehmer sich im gleichen Bereich befinden.

Zum anderen ist unklar, an wen überhaupt die Nutzdaten gesendet werden. Will jeder immer wirklich alle anderen erreichen, oder nur bestimmte Partner, und falls ja, ist es gleichwahrscheinlich, dass ein beliebiger Client x seine Daten an einen anderen Client y sendet?

Peer-to-Peer wäre eine Lösung für das Spezialproblem, das eine bestimmte Information an alle Teilnehmer des Netzes verteilt werden muss. Sobald es aber um beliebige Netzwerkkommunikation geht, muss erst einmal das Routing-Problem gelöst werden, also die Frage "existiert der Zielpunkt für ein Paket überhaupt und wenn ja, wie kommt das Paket dorthin". Das sind zwei völlig unterschiedliche Dinge.

Jede Tonne soll in der Lage sein mit allen anderen aber auch mit einer speziellen zu kommunizieren.

Für die KI der Tonnen bin ich (zum Glück ) nicht zuständig, ich soll es nur ermöglichen, dass die Daten die ausgetauscht werden sollen auch ausgetauscht werden können. Bei mir kommt nur ein Datenstrom an, der dann umgewandelt werden muss um übertragen werden zu können. Zusätzlich bin ich dafür verantwortlich, dass die Daten wirklich dorthin kommen wohin sie auch sollen. Das eigentliche Problem warum ich mich überhaupt näher mit den Ad-Hocs beschäftigen muss ist der, dass diese theoretischen 2^16 Benutzer Daten übertragen können sollen, ohne dass es größere Probleme dabei gibt.

Auch wenn ich auf die Schnelle nichts dazu sagen kann, aber diese Erklärung ist eindeutig besser zu verstehen, als die 5 Seiten, die du vorher formuliert hast. Evtl. beschränkst du dich demnächst einfach auf die Aufgabenstellung. Zumindest bei diesen Fragen, denn wenn du bereits eine Art Lösung angeschaut hast, führst du alle anderen auf das Glatteis.

Tut mir leid deswegen. Es ist eben doch besser wenn man gleich von vorne herein sagt, was man machen möchte, dann gibt es viel weniger Probleme.

Nun, wo ich jetzt so schreibe, fällt mir Blue Tooth dazu ein. Das ist in der Lage Ad-hoc-Netze aufzubauen, allerdings müsste man nun noch rausfinden, wieviele Clients in solchen Netzen verbunden werden können.

ZigBee unterstützt bis zu 2^16 Teilnehmer, nur scheint es nicht umbedingt das Richtige zu sein, was ich suche - kommt mir zumindest so vor und wenn ich den Vortag darüber richtig verstanden habe.



[Nachtrag]
Ich habe mich jetzt durch eine halbe Masterarbeit durchgelesen und festgestellt, dass einiges an Arbeit auf mich zukommt. Man muss ja doch sehr viel mehr Informationen mitschicken als nur von wem es konnt und an wen es soll. Z.B. muss noch eine Zeitinformation eingetragen werden und komplexe Routingtabellen müssen erstellt werden, dann muss jeder Knoten aktiv mitdenken und nicht einfach senden sondern überlegen ob er dieses Paket schon mal hatte, dann ist die Bandbreite auch noch nicht mal konstant sondern unterscheidet sich unter den Knoten usw. Sehr viele Informationen, die übertragen werden müssen. Wenn ich es richtig verstanden habe braucht es um ein Paket zu verschicken mindestens noch 7 weitere um festzustellen, dass das Paket auch wirklich angekommen ist, sprich ewig Bandbreite geht verloren. Alles doch eine Ecke komplizierter, als ich es mir vorgestellt habe... Ich denke, dass ich mich bedeutend intensiver mit der Thematik beschäftigen muss, bevor ich überhaupt dran denken kann irgendwas Hardwaremäßig zu basteln.
Wer Interesse an der Arbeit hat kann sie sich hier ansehen.

[mbs]

Wir haben eine Art "Hardwarepraktikum"

  Ha! Sowas habe ich doch herausgehört...  Bevor fränk Angst kriegt: Ich habe in meinem früheren Leben öfter selber Studenten mit solchen Aufgabenstellungen gequält beschäftigt...

Vielleicht sollte ich aus pädagogisch-didaktischen Gründen lieber keine Tipps hierzu geben... 

Nur soviel: Sich klassische Routing- und Ad-Hoc-Verfahren anzuschauen, bringt viele Ideen und Hintergrundwissen, Du musst aber bedenken, dass die Aufgabenstellung sich in einigen Punkten doch deutlich von einem "normalen" Computernetz unterscheidet:

- "alte" Funknetze wie Aloha leben davon, dass man per Funk jeden erreichen kann. Das ist hier nicht gegeben.
- WLANs leben davon, dass es mindestens eine dedizierte Basisstation gibt, die von allen erreichbar bleiben muss und nicht verschwinden darf. Auch das ist hier nicht gegeben.
- Routing im Internet wird dadurch einfacher, dass die Umgebung jedes Kommunikationsknotens über längere Zeiträume hinweg konstant bleibt. Zwar ändern sich auch hier die Netzlasten ständig, und Leitungen können beliebig gekappt werden, aber die Topologie kann sich nicht so abrupt verändern, wie in Deinem Modell.

Du brauchst also ein sehr dynamisches und extrem adaptives Routing. Dass ein Großteil der Bandbreite für die Selbstorganisation draufgeht, lässt sich nach meiner Einschätzung kaum vermeiden.