Multiple packet filters serving different purposes (e.g., firewalling, QoS) and different virtual routers are often deployed on a single physical router. The HyperCuts decision tree is one efficient data structure for performing packet filter matching in software. Constructing a separate HyperCuts decision tree for each packet filter is not memory efficient. A natural alternative is to construct shared HyperCuts decision trees to more efficiently support multiple packet filters. However, we experimentally show that naively classifying packet filters into shared HyperCuts decision trees may significantly increase the memory consumption and the height of the trees. To help decide which subset of packet filters should share a HyperCuts decision tree, we first identify a number of important factors that collectively impact the efficiency of the resulted shared HyperCuts decision tree. Based on the identified factors, we then propose to use machine learning techniques to predict whether any pair of packet filters should share a tree. Given the pair-wise prediction matrix, a greedy heuristic algorithm is used to classify packets filters into a number of shared HyperCuts decision trees. Our experiments using both real packets filters and synthetic packet filters show that the shared HyperCuts decision trees consume considerably less memory.

Detecting errors in traffic trajectories (i.e., packet forwarding paths) is important to operational networks. Several different traffic monitoring algorithms such as Trajectory Sampling, PSAMP, and Fatih can be used for traffic trajectory error detection. However, a straight-forward application of these algorithms will incur the overhead of simultaneously monitoring all network interfaces in a network for the packets of interest. In this paper, we propose a novel technique called router group monitoring to improve the efficiency of trajectory error detection by only monitoring the periphery interfaces of a set of selected router groups. We analyze a large number of real network topologies and show that effective router groups with high trajectory error detection rates exist in all cases. However, for router group monitoring to be practical, those effective router groups must be identified efficiently. To this end, we develop an analytical model for quickly and accurately estimating the detection rates of different router groups. Based on this model, we propose an algorithm to select a set of router groups that can achieve complete error detection and low monitoring overhead. Finally, we show that the router group monitoring technique can significantly improve the efficiency of trajectory error detection based on Trajectory Sampling or Fatih.

Recent studies have discovered that the Internet delay space has many interesting properties such as triangle inequality violations (TIV), clustering structures and constrained growth. Understanding these properties has so far benefited the design of network models and network-performance-aware systems. In this paper, we consider an interesting, previously unexplored connection between Internet delay space properties and network locations. We show that this connection can be exploited to select nodes from distinct network locations for applications such as replica placement in overlay networks even when an adversary is trying to mis-guide the selection process.

Many distributed systems rely on neighbor selection mechanisms to create overlay structures that have good network performance. These neighbor selection mechanisms often assume the triangle inequality holds for Internet delays. However, the reality is that the triangle inequality is violated by Internet delays. This phenomenon creates astrange environment that confuses neighbor selection mechanisms. This paper investigates the properties of triangle inequality violation (TIV) in Internet delays, the impacts of TIV on representative neighbor selection mechanisms, specifically Vivaldi and Meridian, and avenues to reduce these impacts. We propose a TIV alert mechanism that can inform neighbor selection mechanisms to avoid the pitfalls caused by TIVs and improve their effectiveness.

Understanding the characteristics of the Internet delay space (i.e., the all-pairs set of static round-trip propagation delays among edge networks in the Internet) is important for the design of global-scale distributed systems. For instance, algorithms used in overlay networks are often sensitive to violations of the triangle inequality and to the growth properties within the Internet delay space. Since designers of distributed systems often rely on simulation and emulation to study design alternatives, they need a realistic model of the Internet delay space.Our analysis shows that existing models do not adequately capture important properties of the Internet delay space. In this paper, we analyze measured delays among thousands of Internet edge networks and identify key properties that are important for distributed system design. Furthermore, we derive a simple model of the Internet delay space based on our analytical findings. This model preserves the relevant metrics far better than existing models, allows for a compact representation, and can be used to synthesize delay data for simulations and emulations at a scale where direct measurement and storage are impractical.