To understand, debug, and predict the performance of complex software systems, we develop the concept of probabilistic performance annotations. In essence, we annotate components (e.g., methods) with a relation between a measurable performance metric, such as running time, and one or more features of the input or the state of that component. We use two forms of regression analysis: regression trees and mixture models. Such relations can capture non-trivial behaviors beyond the more classic algorithmic complexity of a component. We present a method to derive such annotations automatically by generalizing observed measurements. We illustrate the use of our approach on three complex systems---the ownCloud distributed storage service; the MySQL database system; and the x264 video encoder library and application---producing non-trivial characterizations of the performance. Notably, we isolate a performance regression and identify the root cause of a second performance bug in MySQL.

Large-scale information processing often relies on subset matching for data classification and routing. Examples are publish/subscribe and stream processing systems, database systems, social media, and information-centric networking. For instance, an advanced Twitter-like messaging service where users might follow specific publishers as well as specific topics encoded as tag sets must join a stream of published messages with the users and their preferred tag sets so that the user tag set is a subset of the message tags.

Application-defined and location-independent addressing is a founding principle of information centric networking (ICN) that is inherently difficult to realize if one also wants scalable routing and forwarding. We propose an ICN architecture, called TagNet, intended to combine expressive application-defined addressing with scalable routing and forwarding. TagNet features two independent delivery services: one with application-defined and possibly location-independent content descriptors, and one with network-defined host locators. In this paper we develop and evaluate specialized forwarding algorithms for TagNet. We then implement and combine these algorithms in a forwarding engine built on a general-purpose commodity CPU, and show experimentally that, thanks to the dual addressing, by descriptor or by locator, this engine can achieve a throughput of over 20Gbps with large forwarding tables corresponding to hundreds of millions of users.