Efficient and Robust Overlay Networks (ERON)

Abstract

The goal of the ERON (Efficient and Robust Overlay Networks) project was to develop an efficient and robust peer-to-peer message routing protocol on top of the Internet protocol. Almost all existing peer-to-peer (P2P) protocols build an overlay network using the Internet as the underlying network. Most of such protocols completely disregard the topology of the underlying network when choosing peering neighbours and making routing decisions for messages. This has the consequence that the length of the paths taken by messages through the underlying network is not optimal.

For constructing a topology aware overlay network we developed a novel protocol for building overlay networks - a distributed fisheye view. Similar to round trip time (RTT) prediction approaches, we consider end systems to be embedded in a virtual metric space. Unlike other approaches, we use only the distances (measured RTTs) to build an RTT proximity aware overlay network. Therefore, we are able to construct a fisheye view without performing the embedding. Simultaneously, we are still able to guarantee the geographical diversity of the neighbors. Once built, the fisheye views on the end systems are continuously refined as information about new potential neighbors becomes available. This makes our overlay network adaptive to changes in the network topology. To evaluate our approach, we compared it with an existing topology aware overlay network construction approach - binning. We based this comparison on RTT measurements obtained using the King RTT measurement method and from the Planet Lab all-site-ping experiment. Our evaluation shows that the overlay network built using our approach outperforms binning in terms of relative RTT stretch. We also show that for an increasing number of neighbors the performance of our approach converges towards an optimal solution.

Further, we developed NetICE9, a novel landmark-less method for embedding RTTs into virtual spaces. NetICE9 is inspired by VIVALDI, the most commonly used landmark-less approach. VIVALDI chooses its neighbors randomly and optimizes only towards one neighbor at a time. With Net- ICE9, we propose a solution to those drawbacks. NetICE9 significantly improves both the stability of the simulation and the precision of how RTTs are embedded into a virtual space. Our evaluation based on RTTs measured in the Internet show that NetICE9 outperforms VIVALDI in terms of stability and precision of RTT prediction. NetICE9 improves RTT prediction also compared to Global Network Positioning (GNP).

We also investigated possible applications of embedding of end systems in a virtual space. Our goal was to introduce an efficient geographic routing protocol in an overlay network. The main issue of every routing protocol is to find a path in the overlay network between source and destination end systems. For the case, when end systems have positions in a Euclidean space, we could use geographic routing protocols such as greedy routing. The problem of greedy routing is that it can fail, if it reaches the so called local minimum of the overlay network. The local minimum is an end system within the overlay network which is surrounded by a nonconvex gap. In such a case, greedy routing fails, since it is unable to make progress towards the destination of the message. In mobile ad-hoc networks such situations cannot be avoided, since end systems have limited transmission range and are dealt with by using a backup routing strategy. In an overlay network on top of the fixed Internet, where every pair of end systems can communicate directly, it is possible to avoid such situations. With the nearest neighbour convex set (NNCS), we introduced one such overlay network building strategy. By being able to construct and maintain NNCS on every end system, we obtain an overlay network, in which greedy routing is always successful. Using NNCS and combining it with fisheye overlay, we are able to obtain a very efficient unicast routing protocol within the overlay network. Another use of NNCS is building topology aware multicast trees. Such a tree is constructed by forwarding multicast messages along the reverse of the unicast paths towards the position of the sender. Based on such a multicast flooding scheme, we also defined a service discovery protocol. This service discovery protocol is able to flood all end systems (within the given diameter) with a query message. This flooding mechanism can be used in order to find different services in the vicinity of the querying end system. Such a service can be the nearest copy of a file or the nearest end systems providing computing services such as storage or CPU time. We also used the NNCS overlay network in order to simplify the task of finding QoS paths. Finding a QoS path in an overlay network implies finding at least one path consisting of end systems from the overlay network, where required QoS parameters such as RTT, bandwidth, jitter etc. are fulfilled. In general, finding such paths involves flooding the whole overlay network with messages, which try finding all possible routes. In our approach we reduce the number of peers involved by limiting the flooding to the ellipsoid within the virtual space. This ellipsoid is defined by positions of the source and the destination end systems as well as the required RTT. By doing so, we can significantly reduce the number of messages and load of the overlay network.

Project Details