Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia, Sailesh Kumar, Balakrishnan Chandrasekaran, Jonathan S. Turner, George Varghese, Proceedings ANCS 2007.
Network monitoring using traffic dispersion graphs, Marios Iliofotou, Prashanth Pappu, Michalis Faloutsos, Michael Mitzenmacher, Sumeet Singh, George Varghese, Internet Measurement Conference 2007: 315-320, 2007.
10 network papers that changed the world, George Varghese, Computer Communication Review 37(5) 77-80, 2007.
A Time-Optimal Self-Stabilizing Synchronizer Using A Phase Clock, Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, George Varghese, IEEE Trans. Dependable Sec. Comput. 4(3): 180-190, 2007.
On Scalable Attack Detection in the Network, Ramana Rao Kompella, Sumeet Singh, George Varghese, IEEE/ACM Transactions on Networking, 2007.
Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines, F. Bonomi, M. Mitzenmacher, R. Panigraphy, S. Singh, G. Varghese, a generalization of Bloom Filters, SIGCOMM 2006
Detecting Evasion Attacks at High Speeds without Reassembly, G. Varghese, J. A. Fingerhut, F. Bonomi, SIGCOMM 2006 , SIGCOMM 2006
An Improved Construction for Counting Bloom Filters, Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, George Varghese, European Symposium on Algorithms (ESA), 2006.
Fast packet classification for two-dimensional conflict-free filters, Florin Baboescu, Priyank Ramesh Warkhede, Subhash Suri, George Varghese, Computer Networks 50(11): 1831-1842, 2006.
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.
Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines, Fan R. K. Chung, Ronald L. Graham, Jia Mao, George Varghese, Theory Comput. Syst. 39(6): 829-849 2006.
A lower bound for multicast key distribution, Jack Snoeyink, Subhash Suri, George Varghese, Computer Networks 47(3): 429-441 2005.
Scalable packet classification, Florin Baboescu, George Varghese, IEEE/ACM Trans. Netw. 13(1): 2-14 2005.
A Uniform Projection Method for Motif Discovery in DNA Sequences, B. Raphael, L. Liu, and George Varghese, IEEE Transactions on Bioinformatics and Computational Biology, 2004.
Tree bitmap: Hardware Software IP Lookups with Incremental Updates, W. Eatherton, Z. Dittia, and George Varghese ACM Computer Communications Review, volume = 34, 2004.
New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, Cristian Estan,George Varghese ACM Transactions Computer Systems 21(3): 270-313, 2003.
Fast and scalable conflict detection for packet classifiers, Florin Baboescu,George Varghese, Computer Networks 42(6): 717-735, 2003.
"The Measurement Manifesto", a call to arms, Proceedings of the 2nd ACM Workshop on Hot Topics in Networks (HotNets-II)
Automatically Inferring Patterns of Resource Consumption in Network Traffic , Tool to mine network logs for large bandwidth consumers identified at the right level of hierarchy (e.g., host, subnet, ISP) and with the right level of detail (protocol, destination-source combinations), Proceedings of the ACM SIGCOMM 2003.
Packet Classification Using Multidimensional Cutting, Fastest algorithmic classification algorithm we know of, Proceedings ACM SIGCOMM 2003
The Impact of Address Allocation and Routing on the Structure and Implementation of Routing Tables, Model to generate large lookup tables, Proceedings ACM SIGCOMM 2003
"Efficient Implementation of a Statistics Counter Architecture", techniques for implementing large amounts of statistics counters at high speeds, SIGMETRICS 2003.
A Pipelined Memory Architecture for High Throughput Network Processors, A Proposal for Building 40 Gbps Network Processors using an innovative memory design, Proceedings of the ACM International Symposium on Computer Architecture (ISCA), San Diego, California, June 2003.
Packet Classification for Core Routers: Is There an Alternative to CAMs?, Proceedings of IEEE Infocom 2003.
Bitmap Algorithms for Counting Active Flows on High Speed Links, Proceedings of the USENIX/ACM Internet Measurement Conference, October 2003.
Catching Accurate Profiles in Hardware, Extending some of our measurement ideas to hardware profiling for processors, Proceedings of the IEEE International Symposium on High Performance Computer Architecture (HPCA), February 2003.
Fast Conflict Detection, Proceeding International Symposium on Network Protocols (ICNP) 2003.
"New Directions in Traffic Measurement and Accounting", techniques for detecting elephant flows without keeping state for all flows, SIGCOMM 2002.
"Route Flap Damping Exacerbates Internet Routing Convergence}", We show that a well-known BGP Mechanisms for improved stability using hysteresis (Route Flap Damping) has undesirable interactions with route convergence. We explore this phenomenon and describe a solution to the problem. SIGCOMM 2002.
"Scalable Packet Classification" SIGCOMM 2001 Existing algorithms for packet classification reported in the literature scale poorly in either time or space as filter databases grow in size. However, even for large classifiers (say 100,000 rules), any packet is likely to match a few (say 10) rules. Our paper seeks to exploit this observation to produce a scalable packet classification scheme
"Memory Efficient State Lookups with Fast Updates". SIGCOMM 2000. Shows how fast memory allocation with low fragmentation is crucial for IP lookups (and other lookups) using limited fast memories, and describes some unusual allocators based on compaction that are different from ones found in the Prog. Languages Community.
"Fast Packet Classification for Two-Dimensional Conflict-Free Filters". Infocom 2001. Shows how conflict-free classifiers can be looked up much faster, at least in 2-D, providing partial confirmation that conflicts make packet classification hard. "A Lower Bound for Multicast Key Distribution" . Infocom 2001. Shows how the RFC 2093 scheme for multicast secret key distribution (co-invented by Wong, Gouda, and Lam) is essentially optimal assuming singly encrypted secret keys. Later work by Micciancio et al has shown that this lower bound technique can be generalized to most other common cryptographic techniques (such as the use of pseudo-random generators and multiple encryptions)
"Reducing Web Latency Using Reference Point Caching" . Infocom 2001. Shows how the scope of web caching can be greatly extended beyond proxies by allowing caching at any point that refers to a web page. Google introduced something similar in 2000 but we invented this idea around 1999, and have done a fair amount of analysis into its pros and cons.
"Fast Firewall Implementations for Software and Hardware Based Routers". ICNP 2001. Shows the power of simple backtracking search for classifiers including some novel ways to pipeline backtracking and various sundry other tricks. Also, compares with set pruning tries (proposed earlier by Decasper et al).
"Multiway Range Trees: Scalable IP lookups with Fast Updates", . Globecom 2001 Internet Symposium. Shows how to modify our earlier binary search methods for IP lookups to achieve fast updates as well.
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. Our implementation was ported to an older version of Snort but has been replaced by the Wu-Manber algorithm.
Latency Reduction Using Precomputing Girish's thesis talk describes more techniques for reducing web latencies. The actual thesis can be obtained from Washington University.