Search this Web site to find published papers and standard documents authored by our researchers.
Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases these works may not be reposted without the explicit permission of the copyright holder.
Event/Location
Internet Measurement Conference 2007
Monitoring network traffic and detecting unwanted applications has become a challenging problem, since many applications obfuscate their traffic using unregistered port numbers or payload encryption. Apart from some notable exceptions, most traffic monitoring tools use two types of approaches: (a) keeping traffic statistics such as packet sizes and interarrivals, flow counts, byte volumes, etc., or (b) analyzing packet content. In this paper, we propose the use of Traffic Dispersion Graphs (TDGs) as a way to monitor, analyze, and visualize network traffic. TDGs model the social behavior of hosts ("who talks to whom"), where the edges can be defined to represent different interactions (e.g. the exchange of a certain number or type of packets). With the introduction of TDGs, we are able to harness a wealth of tools and graph modeling techniques from a diverse set of disciplines.
Event/Location
Hot Interconnects, Stanford, CA, Aug. 2007.
This paper describes the design of ElephantTrap, a device which aims to cache the largest flows (the "elephants") on a network link. ElephantTrap differs from previous work on identifying large flows in one crucial sense: it does not attempt to accurately estimate the size of the flows it is trapping. This leads to an extremely lightweight design and a surprisingly good performance. ElephantTrap can be employed in the line cards of switches and routers and be used for diagnostics, anomaly detection and traffic engineering.
The Internet provides tremendous flexibility, in that it can support a wide variety of services, and accessibility, in that these services can be invoked from anywhere. However, the current Internet architecture does not easily support service portability. If users want their service names to be persistent then they must stick with the same service provider because service names, such as email addresses, are tied to administrative domains. In this paper we present a system called Permafind that gives users a persistent name for their services while allowing them to switch among service providers. Permafind applies to a wide range of services, and is immediately deployable. Serendipitously, Permafind also allows dynamic service insertion thus permitting many of the capabilities of more revolutionary proposals such as i3. Permafind embodies no technical innovation, but it does suggest that the notion of redirection, as embodied in HTTP, is a crucial feature for future service protocols.
Title
Beyond bloom filters: from approximate membership checks to approximate state machines.
Event/Location
SIGCOMM 2006
Many networking applications require fast state lookups in a concurrent state machine, which tracks the state of a large number of flows simultaneously. We consider the question of how to compactly represent such concurrent state machines. To achieve compactness, we consider data structures for Approximate Concurrent State Machines (ACSMs) that can return false positives, false negatives, or a "don't know" response. We describe three techniques based on Bloom filters and hashing, and evaluate them using both theoretical analysis and simulation. Our analysis leads us to an extremely efficient hashing-based scheme with several parameters that can be chosen to trade off space, computation, and the impact of errors. Our hashing approach also yields a simple alternative structure with the same functionality as a counting Bloom filter that uses much less space. We show how ACSMs can be used for video congestion control. Using an ACSM, a router can implement sophisticated Active Queue Management (AQM) techniques for video traffic (without the need for standards changes to mark packets or change video formats), with a factor of four reduction in memory compared to full-state schemes and with very little error. We also show that ACSMs show promise for real-time detection of P2P traffic.
Event/Location
Proceedings of the 6th ACM/USENIX Symposium on Operating System Design and Implementation (OSDI), San Francisco, CA, December 2004. http://www.cse.ucsd.edu/~savage/papers/OSDI04.pdf
Author
Yin Zhang, Sumeet Singh, Subhabrata Sen, Nick Duffield, and Carsten Lund
