Relay Discovery and Selection

In peer-to-peer networks, application relays have been commonly used to provide various networking services. The service performance often improves significantly if a relay is selected appropriately based on its network location. In this project, we study the location-aware relay discovery and selection problem for large-scale P2P streaming networks. In these large-scale and dynamic overlays, it incurs significant communication and computation cost to discover a sufficiently large relay candidate set and further to select one relay with good performance. The network location can be measured directly or indirectly with the tradeoffs between timeliness, overhead and accuracy. We conduct a measurement study and the associated error analysis to quantify these tradeoffs. Indirect measurements, such as King and Internet Coordinate Systems (ICS), can only achieve a coarse estimation of peers' network location and those methods based on pure indirect measurements cannot lead to a good relay selection. There may exist significant error amplification of the commonly used ``best-out-of-K" selection methodology. We propose a two-phase approach to achieve efficient relay discovery and accurate relay selection. Indirect measurements are used to narrow down a small number of high-quality relay candidates and the final relay selection is refined based on direct probing. This two-phase approach may enjoy an efficient implementation using the Distributed-Hash-Table (DHT). When the DHT is constructed, the node keys carry the location information and they are generated scalably using indirect measurements, such as the ICS coordinates. The relay discovery is achieved efficiently utilizing the DHT-based search. Various aspects of this DHT-based approach are evaluated, including the DHT indexing procedure, key generation under peer churn and message costs.<br>For indirect RTT measurements, we obtained the IP addresses of the Gnutella peers. This IP list is available at Gnutella_IP.zip. In our study, we utilize the King tool to measure RTT between each pair of remaining hosts. This RTT dataset is available at Gnutella_RTT.zip. For our experiments, we retain those hosts that have a full-rank RTT matrix between themselves. Our RTT matrix is available at RTT-matrix.zip.<br> <br>To illustrate the importance of the measurement accuracy, we conduct RTT measurements on PlanetLab nodes with two tools, RTTometer and King. We deploy RTTometer and King in randomly selected 260 accessible PlanetLab nodes as the end-hosts and probe all other PlanetLab nodes for RTT measurements. Each end-host probes other nodes one by one. After one round finishes, a new round starts. To achieve a fair comparison on the measurement accuracy, we measure RTTs between each pair of hosts using RTTometer and King during the same period time. For each end-host, it first probes one remote node with RTTometer 10 times with the inter-probe interval of 500 msec; then we use King to estimate RTTs of this node pair for 10 times with the interval of 1 second. After one remote node is finished, a new remote node is selected for RTT measurements. The measurement interval between RTTometer measurements and King measurements is set to be less than one minute, thus the time effect on the measurement accuracy is reduced. Each pair measurement takes less than 1 minute to finish, and it takes less than 1 day to finish the measurements of all pairs. Our direct RTT measurement dataset is available at pldirect.zip. The proposed two-phase relay selection dataset is available at plrelay.zip.