From 2000 to the present, my students (Cristi Estan, Ramana Kompella, Sumeet Singh, Mike Fisk, Terry Lam, and Frank Uyeda) and I have worked on a new direction called Introspective Routers. I was inspired by the IBM autonomic computing manifesto which sought to move beyond "bigger and faster" to making computational artifacts (in this case networks) easier to use. We started by identifying a set of measurement primitives. We then ventured to use these measurement ideas for network security, being fortunate enough to tap into the "worm" craze of 2003-2005.

Router Measurement Papers

New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, Cristian Estan,George Varghese SIGCOMM 2001 and ACM TOCS 2003. Well referenced paper that started the direction of routers maintaining compact measurement sketches for specific functions in hardware as an alternative to the data storage and overhead of NetFlow. Many of these ideas are implemented in a chip called Hawkeye that was fabricated in Cisco.

Automatically Inferring Patterns of Resource Consumption in Network Traffic Autofocus Tool to mine network logs for heavy bandwidth flows identified at the right level of hierarchy (e.g., host, subnet, ISP) and with the right level of detail (protocol, destination-source combinations), SIGCOMM 2003. By contrast, the previous paper assumed a fixed definition of a flow

"Efficient Implementation of a Statistics Counter Architecture", techniques for implementing large amounts of statistics counters at high speeds, SIGMETRICS 2003. Goes beyond the earlier papers by Iyer et al by showing to avoid sorting overhead involved in storing some parts of a counter in DRAM and some in SRAM. Similar ideas used in Nemo, acquired by Cisco.

Building a Better NetFlow, Cristian Estan, Ken Keys, David Moore, and George Varghese. Ways to go beyond Cisco's NetFlow in terms of flow counting and graceful degradation.

Bitmap algorithms for counting active flows on high-speed links, Cristian Estan, George Varghese, Michael E. Fisk, IEEE/ACM Trans. Netw. 14(5): 925-937, 2006. A useful building block that can be used for example to herald the start of a DoS attack since the number of flows often increases.

Every Microsecond Counts: Tracking Fine-Grain Latencies with a Lossy Difference Aggregator. SIGCOMM 2009,, R. Kompella, K. Levchenko, A. Snoeren, G. Varghese. Made relevant by financial trading and the use of Ethernet switches in computing clusters. (see press articles in: Science Daily and Ars Technica

Carousel: Scalably Logging for Intrusion Prevention Systems, T. Lam, M. Mitzenmacher,G. Varghese, NSDI 2010. A way to log every data item in a stream even with small logging bandwidth and small memory assuming data items repeat. Made relevant by the need to log infected sources after an attack.

Efficiently Measuring Bandwidth at all Time Scales , F. Uyeda, L. Fuschini, S. Suri, G. Varghese, NSDI 2011. A way to estimate bandwidth usage at every time scale without excessive storage. Made relevant by the need to spot the sources of microbursts.

Fine Grain Latency and Loss Measurements in the Presence of Reordering , M. Lee, S. Goldberg, R. Kompella,G. Varghese, SIGMETRICS 2011. Allows the LDA structure to handle reordering, necessary for end-to-end latency detection.

Network Security Papers

Fast Content-Based Packet Handling for Intrusion Detection, UCSD Technical Report CS2001-0670. Shows how to modify signature based IDS systems to do string searches in packet data in one pass as opposed to multiple passes as was done in an early version of Snort. Mike's implementation was ported to an older version of Snort but has been replaced by the Wu-Manber algorithm.

Automated Worm Fingerprinting (Basis of NetSift, later acquired by Cisco) Sumeet Singh, Cristian Estan, George Varghese, and Stefan Savage, Proceedings of the 6th ACM/USENIX Symposium on Operating System Design and Implementation (OSDI) 2004

On the Difficulty of Scalably Detecting Network Attacks, Kirill Levchenko, Ramamohan Paturi, and George Varghese, Proceedings of the ACM Conference on Computer and Communications Security, Washington, D.C., October 2004. Shows why compact sketches for certain commonly required security functions are impossible. However, in many cases by appropriately redefining the measurement primitive compact implementation becomes possible. Connects the theory to real Intrusion Detection Systems that were in the market in 2004.

Detecting Evasion Attacks at High Speeds without Reassembly, G. Varghese, J. A. Fingerhut, F. Bonomi, SIGCOMM 2006 , SIGCOMM 2006. Revisits the assumption that normalization and reassembly are required for IDS devices.

On Scalable Attack Detection in the Network, Ramana Rao Kompella, Sumeet Singh, George Varghese, IEEE/ACM Transactions on Networking, 2007. A sketch to detect DoS attacks based on SYN flooding and other similar approaches.


Prepared by George Varghese
Last Modified Feb 2012 .