Forschung in der AG Rechnernetze


 Projektpartner, Kooperationen und Drittmittelgeber

humboldt_logo.jpeginsta_logo_schwarz.jpgdfg_logo_schriftzug_blau.png


Die Arbeitsgruppe beschäftigt sich derzeit mit folgenden Forschungsthemen und -projekten:

Forschungsthemen

Aktuelle Projekte

Abgeschlossene Projekte

  


Forschungsthema: Lokales geographisches Routingarrow.png

Eines unserer Forschungsfelder ist die Datenkommunikation in drahtlosen Multihop-Netzen auf der Basis von lokalen Routingverfahren. Wir beschäftigen uns hier sowohl mit Unicast als auch mit Gruppenkommunikationsverfahren. Allen diesen Verfahren ist gemeinsam, dass Routing-Entscheidungen ohne globalen Nachrichtenaustausch gefällt werden. Hierzu ist jedoch notwendig, dass jeder Knoten seine Position kennt.

Zur Unicast-Kommunikation erforschen wir aktuell die von uns entwickelte Methode des Kurven-basierten planaren Face-Routings und Möglichkeiten mit dieser Methode Traffic-Engineering und Robustheit gegenüber Angreifern im Netz zu erreichen. Darüber hinaus analysieren wir generelle theoretische Aussagen zu Pfadlängen und Auslieferungsraten von Routing in planaren Graphen.

 

Forschungsthema: Vernetzung von und durch Flugroboterarrow.png

quadrocopterEin weiteres in unserer Arbeitsgruppe bearbeitetes Forschungsfeld sind Forschungsfragen zu Prototypen von kooperierenden Flugrobotern. Aktuell besteht der Prototyp aus vier fliegenden Quadro-Koptern. Die Quadro-Kopter basieren auf der MikroCopter-Architektur, die von uns um ein seriell angebundenes Embedded Linux Board erweitert wurden. Auf dem Board können komplexere Algorithmen empirisch untersucht werden. Die Plattform eignet sich für aktuelle grundlegende Fragestellungen. Zukünftig soll jedoch auf Kosten der Leistungsfähigkeit bzgl. MCU und Speicher der einzelnen Flugroboter wesentlich kleinere Hardware eingesetzt werden. Die Forschungsvision sind große Systeme bestehend aus hunderten von mobilen kooperierenden Kleinstrobotern.

Aktuell befassen wir uns mit Fragen der koordinierten Platzierung von Robotern, sodass mit den eingenommenen Positionen eine möglichst gute Netzstruktur für das Roboterteam bei maximal möglicher abgedeckter Fläche entsteht. Hierbei befassen wir uns mit dem Entwurf von Algorithmen auf Basis von Masse-Feder-Systemen und Grid-basierten Strukturen und deren Evaluation in realen Versuchsaufbauten. Darüber hinaus beschäftigen wir uns mit dem selbstorganisierten Aufbau von Supportnetzen. Dies beinhaltet zum einen die Bereitstellung einer drahtlosen Netz-Infrastruktur durch geeignete Positionierung der fliegenden Roboter selber, als auch den Abwurf von Relay-Knoten auf geeignete Positionen. Im Rahmen eines von der Arbeitsgruppe eingeworbenen Forschungspreises sollen für letzteres geeignete Kleinstknoten prototypisch in Hardware realisiert und auf diesen Knoten geeignete Netzformierungsprotokolle für sehr leistungsschwache Mikrocontroller realisiert werden.

 


 

Aktuelles Projekt: Planare Netzspanner für drahtlose Netzearrow.png

simulation_2Bei diesem Forschungsfeld geht es um die Konstruktion von planaren Netzspannern für drahtlose Netze. Ein Subgraph ist planar, wenn es eine Zeichnung des Graphen gibt, sodass sich keine Kanten überschneiden. Planare Netzspanner sind für drahtlose Netze mit großer Knotenanzahl von besonderem Interesse. Sie erlauben rein lokal operierende Routing-Verfahren, d.h. machen den globalen Austausch von Routinginformation überflüssig. Darüber hinaus weichen optimal arbeitende Routingverfahren auf solchen Spannern nur unwesentlich vom kürzesten Pfad ab.

Die Konstruktion von planaren Spannern ist schwer, aber algorithmisch gelöst. Die reaktive Konstruktion solcher Spanner ist noch schwerer und ungelöst. Im Rahmen des DFG-Projektes "ReactiveSpanner" verfolgen wir das Ziel, Spanner reaktiv zu konstruieren. Reaktiv bedeutet hierbei, dass ein Knoten keinerlei Kenntnis über seine Nachbarn besitzt. Erst bei Bedarf, z.B. wenn eine Nachricht weiterzuleiten ist, wird mit minimalem adresslosem Nachrichtenaustausch mit wenigen unmittelbaren Nachbarknoten eine lokale Sicht auf die ausgehenden Kanten des Spanners erzeugt.

 

Aktuelles Projekt: Zuverlässige drahtlose eingebettete Knotenarrow.png

gebaeude_funkkanaele_edited.pngForschungsgegenstand sind hier als Prototyp realisierte Netzknoten, darauf realisierte Netzorganisations- und Kommunikationsverfahren und deren empirische Evaluation und Gegenüberstellung in realen Versuchsaufbauten. Die Versuchsaufbauten umfassen in der Regel zwischen 50 bis 250 Netzknoten. Aktuell verwendete Knotenprototypen sind die in unserer Forschung schon länger eingesetzten TmoteSky-Knoten und die von dem Industriepartner Insta Elektro GmbH im Rahmen des LightOn Projektes realisierten Insta-Knoten für die Gebäudeautomatisierung. Die untersuchten Verfahren werden in der Regel unter der TinyOS Laufzeitumgebung implementiert. Diese läuft unter den TmoteSky-Knoten standardmäßig und wurde im Rahmen des LightOn Projektes auch für die Insta-Knoten portiert.

Ein aktuell untersuchtes Netzorganisationsverfahren ist die selbstorganisierte Strukturierung des Netzes mittels Clustering. Hierbei werden Knoten zu Clustern zusammengefasst und jeweils von einem so genannten Cluster-Head verwaltet. Mittels Cluster-Strukturen kann man Datenkommunikation signifikant beschleunigen und auch zuverlässiger machen. Eine große wissenschaftliche Herausforderung ist die strikte Speicherlimitierung von Embedded-Hardware und die hohe Dynamik und Unzuverlässigkeit des Drahtloskanals.

Aktuelles Projekt: Konvergenz von Routing-Algorithmenarrow.png

simplesourceloop.jpgIm Projekt Konvergenz von Routing-Algorithmen werden die Reorganisationsfähigkeiten von routergekoppelten Netzwerken untersucht. Ziel dieser Arbeit ist die Konvergenz und Skalierbarkeit speziell von Distanz-Vektor-Algorithmen zu verbessern. Von zentraler Bedeutung ist hierbei die Erkennung und Vermeidung von Routing Schleifen, da diese das Haupthindernis bei der Konvergenz von Routing-Algorithmen darstellen. Die Untersuchungen werden auf Basis von, zu Rechnernetzen zusammengeschalteten, virtuellen Maschinen durchgeführt. Es liegen bereits erfolgreiche neue Ansätze zur Vermeidung von Routing-Schleifen in Distanz-Vektor-Algorithmen vor. Die vektorbasierten Routing-Algorithmen (z.B. RIP, EIGRP, BGP) erlauben, im Gegensatz zu Link-State-Algorithmen (OSPF, IS-IS), die Anwendung von Routing Policies zur gezielten Weitergabe von Routinginformationen. Darüberhinaus bieten Distanz-Vektor-Algorithmen mithilfe der Aggregation von IP-Adressen (route summarization) eine einfache Möglichkeit der Skalierung von IP-Netzen, wodurch jedoch die Gefahr für das Auftreten von Routing-Schleifen erhöht wird.

Abgeschlossenes Projekt: Overlays und Internet-Koordinatensystemearrow.png

Oberhalb der Routingebene ist das Internet ein vollständiger Graph, d.h. jeder Knoten kann unmittelbar mit jedem anderen Knoten kommunizieren. Aus Gründen der Skalierbarkeit, z.B. beim verteilten Suchen, ist es häufig sinnvoll, diese vollständige Sicht zu reduzieren und jedem Knoten nur einen Teil aller Teilnehmer bekannt zumachen. Eine solche Graphstruktur bezeichnet man als Internet-Overlay. Im Rahmen des SFB-901 Teilprojektes A2 „Realisierung und Optimierung von Overlays über physikalischen Netzen“ erforschen wir in Kooperation mit der Universität Paderborn die Konstruktion von effizienten Overlays und Routing auf der Basis von Internet-Koordinatensystemen. Darüber hinaus werden architekturelle Fragen behandelt, inwieweit ein Overlay das darunter liegende Netz zu Gunsten des Overlays modifizieren kann. Fragen zur Architektur und zur der Einsetzbarkeit der entwickelten Verfahren in realen Netzen wird durch empirische Evaluation in prototypischen Testaufbauten auf Basis von FPGA-basierten, programmierbaren, Open-Flow-fähigen Switches  untersucht.

Ein Internet-Koordinatensystem ist eine Einbettung der Internet-Knoten in einen Vektorraum, sodass man mittels Knotenkoordinaten und einer geeigneten Abstandsfunktion Kanteneigenschaften des darunterliegenden Netzes abschätzen kann. Gegenwärtige Internet-Koordinatensysteme sind für die Abschätzung von Latenzen geeignet. Für andere Kenngrößen wie beispielsweise die verfügbare Datenrate sind diese aber in der Regel nicht anwendbar. Dies ist insbesondere der Fall, wenn die Abstandsfunktion nicht-metrisch ist und die Dreiecksungleichung häufig verletzt wird. Aktuell untersuchen wir Internet-Koordinatensysteme auf Basis nicht-negativer Marix-Faktorisierung für nicht-metrische Abstandsfunktionen. Hierzu wird das Konzept der nicht-negativen Matrix-Faktorisierung von der üblichen reellwertigen Algebra auf die min-plus Algebra übertragen. Durch geeignete verteilte Kodierung des Resultats dieser Faktorisierung in den Netzknoten lassen sich die Abstände zwischen Knoten bzgl. der betrachteten Kenngröße durch einfache Vektormultiplikation bestimmen. Aktuellen empirischen Messungen zufolge ist das Verfahren vielversprechend genau. Offen ist aktuell eine verteilte Realisierung des Verfahrens.

Die Konstruktion von Overlays auf der Basis von Internetkoordinatensystemen funktioniert prinzipiell in der Form, dass Knoten, die in dem Koordinatensystem bzgl. der betrachteten Abstandsfunktion sehr nahe beieinander liegen, miteinander verbunden werden. Bei dieser Konstruktion müssen aber aus Skalierbarkeitsgründen weitere Grapheigenschaften wie beispielsweise Gradbeschränkung berücksichtigt werden. Um in dem konstruierten Subgraphen effiziente Routingverfahren zu ermöglichen, ist es notwendig, dass der konstruierte Graph die kürzesten Pfadlängen des Ausgangsgraphen bis auf einen konstanten Faktor erhält. Man spricht in diesem Fall von einem Netzspanner. Die Konstruktion von Netzspannern über Knoteneinbettungen aus Internet-Koordinatensystemen ist ein weitgehend noch unbekanntes Forschungsfeld. Als grundlegenden Ausganspunkt zu diesem Forschungsfeld befassen wir uns aktuell mit der Frage, ob und wann K-Sektor-Graphen unter der p-Mektrik Netzspanner sind.