Finding the nearest peer, in terms of latency, is an important problem in many Internet applications. In this paper, we argue that existing solutions, which only examine inter-peer latencies as part of their operation will find it costly, in certain commonly occurring scenarios, to discover the nearest peer in P2P systems. The difficulty arises out of the way the PoP access networks are laid out in the Internet, where a single PoP (point of presence) belonging to an ISP provides connectivity to numerous client networks. This setup makes a group of peers all appear roughly the same distance from each other, leading to inefficiencies in the existing solutions. In this paper, we use large-scale measurements to show that the problematic topology does occur, use simulations of the Meridian closest-server algorithm to show that the condition does indeed lead to difficulty in finding the exact-closest peer, and propose solutions.

Fast IP flow rate estimation has many potential applications in network management, monitoring, security, and traffic engineering. Recently, low cost and memory efficient techniques to accurately estimate flow-rates in real-time have been developed. These techniques rely on flow definitions being constrained to being subsets of the fields in the packet header making flow-membership tests relatively inexpensive. In this paper, we consider a more general flow-rate estimation problem where flow membership testing is non-trivial and may involve more complex processing such as packet-payload based tests. An example is to estimate the amount of traffic that contains a given set of patterns (e.g., virus or worm signatures). We design new flow estimation techniques to reduce the number of membership tests. These techniques track pairs of arrivals that have the given property of interest and use lazy membership testing to avoid complex property testing unless absolutely necessary. The efficiency of the new schemes is evaluated by both analysis and simulation. I.

Abstract — Unstructured p2p and overlay network applications often require that a random graph be constructed, and that some form of random node selection take place over that graph. A key and difficult requirement of many such applications is heterogeneity: peers have different node degrees in the random graph based on their capacity. Using simulations, this paper compares a number of techniques—some novel and some variations on known approaches—for heterogeneous graph construction and random node selection on top of such graphs. Our focus is on practical criteria that can lead to a genuinely deployable toolkit that supports a wide range of applications. These criteria include simplicity of operation, support for node heterogeneity, quality of random selection, efficiency and scalability, load balance, and robustness. We show that all these criteria can more-or-less be met by all the approaches. Our novel approach, however, stands out as the best from a practical perspective because of its simplicity: it achieves the criteria while requiring each node to set only a single tuning parameter, its desired relative load. I.