Partner und Internationale Organisationen
(Englisch)
|
BE, CH, CY, CZ, DE, EE, ES, FI, FR, GR, HU, IL, IS, IT, NL, NO, PL, PT, SE, SI, UK
|
Abstract
(Englisch)
|
This project dealt with highly dynamic communication networks and the issues that arise in dealing with changes in these networks. Specifically, we studied distributed solutions for maintaining a spanning tree of an underlying communication graph in case of temporary failures. Our approach is to reconnect the graph with a 'swap edge', in such a way that the resulting temporary network is still of high quality. This approach allows to adjust routing in case of failures in an inexpensive and distributed fashion. We have developed a distributed algorithm that efficiently precomputes all the best swap edges of a minimum diameter spanning tree in a weighted undirected graph [10]. In addition, we found a compact routing scheme for trees which can quickly and efficiently adapt to the use of a temporary swap edge, and has several advantages compared to the previously best solution. We developed a new efficient algorithm for computing all best swaps of a minimum diameter spanning tree [13]. This improves the previously best algorithm for that problem which had been known for ten years. Furthermore, we found efficient algorithms for computing best swap edges in tree spanners (spanning trees which minimize the maximum stretch). For unweighted graphs, we gave a tailored algorithm which is more efficient for dense graphs. We also found an efficient distributed algorithm for this problem [14]. Astonishingly, failures of components correspond exactly to certain types of payments in mechanism design problems. In connection with our studies of edge failures of minimum diameter spanning trees, we proposed a truthful mechanism for this problem and showed how payments can be computed in polynomial time [1]. When the measure of choice is not the diameter, but the radius, and the objective is to find a partition (instead of suffering from it) with minimum sum of radii, we proved NP-hardness in general, but provided a polynomial algorithm for small number of components [2]. Our studies of the role of facility location and clustering questions led to a new, faster algorithm for partitioning a graph into subgraphs so that the sum of the individual radii is minimum [11]. The implications of our findings in a dynamic scenario remain to be studied. Furthermore, we started an effort towards designing a distributed reliable storage system, which stores incoming messages in an online fashion, and strives to minimize the average flow time of each message in the system. As a starting point, we have looked at this problem in a centralized setting, and provided a competitive algorithm for it [3]. A Master Thesis on this subject later revealed that distributing data efficiently across a dynamic network will remain a challenge [9]. We started an effort towards tracking moving targets with cameras, in such a way that tracking accuracy is optimized. As a starting point, we have looked at this problem in a centralized setting, which turned out to be already surprisingly difficult [15]. For dynamic communication networks, a highly suitable class of algorithms are so-called 'local' algorithms, which have a very small running time: if a computation completes quickly, it is less likely to face a network change which renders the result obsolete. An important example of highly dynamic networks are wireless ad-hoc networks. We developed two local algorithms for wireless ad-hoc networks. The first is an efficient randomized distributed algorithm for computing a Maximal Independent Set in Growth-Bounded Graphs [6]. Maximal Independent Sets are an important building block for many distributed algorithms, because they capture some of the symmetry-breaking difficulties arising in many distributed computations. Furthermore, we designed an efficient distributed algorithm for computing a (1+epsilon)-approximation of a Minimum Connected Dominating Set (MCDS) [7]. Connected dominating sets are a popular structure for wireless ad-hoc networks, because they can be used as a virtual backbone for routing (as an alternative to flooding). The MCDS computed by our algorithm induces a subgraph with constant degree and constant stretch, which has additional benefits for routing. The aforementioned paper was invited and accepted in a special journal issue [16]. For access to huge, distributed graphs, we studied the problem of answering approximate shortest path queries by means of a small index. Our first results [8] make us confident that the proposed technique might be amenable to dynamically changing graphs, without the need to update the index for every change that the graph undergoes. In addition, we examined routing techniques for wireless ad hoc networks, a basic functionality that needs to be available in any computer network. Our main focus was on simple routing algorithms such as greedy and geographic routing which are promising also for mobile networks where the network participants (nodes) move constantly. In wireless networks, mobility not only covers the case of physically moving nodes, but also the fact that the wireless medium is not perfect. I.e. the links between nodes may vary over time even though the nodes are not moved. In geographic routing, we assume that each node knows its position (coordinates) and the coordinates of its neighbouring nodes. The routing of the messages is greedy in the sense that a node forwards a message to its neighbour which is closest to the destination node. Thus, the sender needs to know the position of the destination. To support a reliable delivery of messages in truly mobile networks where even the destination node may be moving while messages are routed towards the node, we built a distributed location server to keep track of the positions [4]. We show that the delivery can be guaranteed even if the nodes move at a speed of up to 1/15th of the routing speed. Geographic routing works quite well unless a message ends up at a local minimum, a node that has no neighbour which is closer to the destination. Whereas standard techniques are known for 2D networks to recover from such dead-ends, there is no deterministic algorithm for 3D networks. We derived routing techniques for this case in [17] and show that any local memoryless routing algorithm has a cubic routing overhead in the worst case. The simulator for network algorithms [5] helped us to analyze and improve our randomized routing techniques. As the recovery from local minima always increases the overhead compared to the optimal path, we describe the construction of a coordinate assignment that guarantees a purely greedy delivery without ever falling in local minima [18]. In addition, we show that the routes chosen by this greedy algorithm are only a small constant longer than the optimal routes. Greedy and geographic routing techniques are mainly suited for unicast routing, the delivery of a message to a single receiver. Therefore, we built a routing system that not only supports unicast, but also anycast (delivery to any destination of a given set) and multicast (delivery to a given subset) [12].
|
