Number of cases campus Koblenz: 1 (warning level Gelb until 12.02.2021) Action plan

Research in the Computer Networks Group


Partners, Cooperations and Third-party funds

 humboldt_logo.jpeginsta_logo_schwarz.jpgdfg_logo_schriftzug_blau.png


The following research topics and projects are content of the Computer Networks Group:

Research topics

Current research projects

Completed projects

  


 

This translation of the following articles is still in progess.

Research topic: Local geographic routingarrow.png

A main field of research in our working group is data communication in wireless multihop networks based on local routing techniques, meaning that routing decisions are made without any global exchange of messages. At this juncture,  both methods of unicast and group communication are considered. Necessarily each node needs to know its position.
One method developed by our working group, concerning unicast communication, is a curve-based planar face routing for the purpose of exploring traffic engineering and robustness against attacks in network.
Furthermore we research general theoretical statements referring to path  lengths and delivery rates of routing in planar graphs.

 

Research topic: Networking with flying robotsarrow.png

quadrocopterOther research topics of our working group include prototypes of cooperating flying robots, currently composing of four quadcopters. These base upon the MikroKopter architecture, extended by a serially tethered Embedded Linux Board, on which complex algorithms can be analyzed empirically. Thus the platform is suitable for answering principle questions at the present time; in the future we want to apply a substantial smaller hardware at the expense of the efficiency of MCU and memory. Our aim is to establish large systems of hundreds of mobile midget robots cooperating.
We are also interested in questions of a coordinated robot positioning for achieving a preferable network structure providing a maximized covered area with the taken positions. Here important parts represent the design of algorithms involving spring-mass-systems and grid-based structures as well as the evaluation in real experimental set-ups.
A self-organized installation of support networks is an other topic of our research, including on the one hand the allocation of a wireless network infrastructure by the appropriate positioning of the flying robots, and on the other hand the dropping of relay nodes on adequate positions. For the latter, midget nodes are to be prototypically realized in hardware (in the context of a raised research award), on which network forming protocols serve inefficient microcontrollers.
 


 

Current project: Planar spanner construction for wireless networksarrow.png

simulation_2A subgraph is called planar, if it admits a drawing of it without any two overlapping edges. Planar network spanner are of interest to wireless networks with a large number of nodes. They permit pure locally operating routing techniques, the global exchange of routing information becomes redudant. Ideally working routing procedures on those spanners differ rarely from the shortest path.
The construction of planar spanners is difficult but solved algorithmically. By contrast the reactive construction of those spanners is more difficult and yet not solved. Within the project "ReactiveSpanner", funded by the German research funding organisation DFG, our goal is to construct these reactive spanners. Reactive means, that a node does not know anything about its neigbours. Only if necessary, e.g. when a message needs to be transmitted, a local view on outgoing edges of the spanner is provided. This happens with minimal, addressless exchanging of messages and few neigbour nodes.

 

Current project: Reliable wireless embedded nodesarrow.png

gebaeude_funkkanaele_edited.png

Object of research are prototypes of nodes on which operations of network organization and communication are realized, including their empirical evaluation and comparisons in real test set-ups. Normally, these set-ups comprise from 50 up to 250 nodes. For quite some time we use TmoteSky-nodes and Insta-nodes as prototypes for our research, the latter realized by our industry partner Insta Elektro GmbH for a building automation within in the scope of the LightOn project.

The analyzed operations are usually implemented in a TinyOs runtime environment, by default running for the TmoteSky-node but also ported for the Insta-node within the LightOn project.

A currently investigated organization technique is a self-organized structuring of the netwerk with the aid of clustering. Nodes are summarized as clusters where each clusters gets managed by a so-called cluster head. Structures of clusters can significantly accelerate data communication and make them reliable.
A big challenge is a strictly limited memory of embedded hardware and a high dynamic and untrustowrthiness of the wireless channel.

Current project: Convergence of routing algorithmsarrow.png

simplesourceloop.jpg

In this project we investigate the ability of reorganization of router coupled networks. The goal is to improve the convergence and scalability of distance-vector-algorithms in particular. Here a recognition and  avoidance of routing loops becomes important as they form the main obstacle relating to the convergence of routing algorithms.
The analyses are carried out on virtual machines, interconnected as computer networks. There exists already new successful approaches for avoiding routing loops in distance-vector-algorithms.
Vectorbased routing algorithms (e.g. RIP, EIGRP, BGP) permit the appliance of routing policies for a targeted propagation of routing information, contrary to link-state-algorithms (like OSPF, IS-IS). In addition, distance-vector-algorithms offer an easy possibility for the scaling of IP-networks using aggregation of IP-addresses (route summarization); however, the risk of an appearance of routing loops is getting increased.
 


Completed project: Overlays and internet coordinate systemsarrow.png

Above the routing level, the internet represents a complete graph, i.e. each node is able to communicate directly with other nodes. For reasons of scalability, e.g. distributed search, it is often reasonable to reduce this entire view and to let each node making acquaintance to only a part of all participants. Such a graph structure is called internet overlay.
In cooperation with the university of Paderborn, we investigate the construction of efficient overlays and routing on the basis of internet coordinate systems. Thereby architectural questions are treated, e.g. to what extent an overlay can modify the underneath network in favor of the overlay. Questions of architecture and applicability of the developped proceedings are analyzed via an empirical evaluation in prototpical test environments, using FPGA-based switches, being programmable and open-flow capable.

An internet coordinate system is an embedding of internet nodes in a vector space, so that an estimation of edge characteristics is possible using node coordinates and an adequate distance function. Present internet coordinate systems are convenient for the estimation of latencies; normally, they are not applicable for other parameters like the available data rate. This is the case, if the distance function is not metrical and the triangle inequality is violated. Currently we examine the internet coordinate systems with a nonnegative factorization of matrices and non-metrical distance functions. For this, the concept of the nonnegative matrix factorization gets translated of the common real-valued algebra to the min-plus algebra. Through an appropriate distributed encoding of the factorization outcome, one can determine the distance between nodes (with respect to examined characteristic)  with simple vector multiplication. According to present empirical measurements, this method is promising accurate. A distributed realization of it remains unsettled.

For the construction of overlays on internet coordinate systems, nearby nodes (with regard to the distance function) are getting connected. Further graph properties like limitation of degree need to be considered for reasons of scalability. To allow efficient routing in the constructed subgraph, it is necessary that the graph gets the shortest pathlengths of the origin graph except for an constant factor. The construction of spanners via embedding of nodes of the internet coordinate systems is still a widely  unknown research topic.
As an fundamental aspect of this topic, we deal with the question, if and when k-sector-graphs are spanners under the p-metric.