Correct by Construction Networks Using Stepwise Refinement L. Ryzhyk, N. Bjorner, M. Canini, J. Jeannin, C. Schlesinger, D. Terry, G. Varghese, NSDI 2017 (applies stepwise refinement to networks)
ddNF: An Efficient Data Structure for Header Spaces. N. Bjorner, G. Juniwal, R. Mahajan, S. Seshia, G. Varghese. Haifa Verification Conference 2016, (Best Paper Award, a data structure to represent multiple header spaces and their intersections)
From Header Space to Control Space: Comprehensive Network Reachability Verification, S. Fayaz, T. Sharma, A. Fogel, R. Mahajan, T. Millstein, V. Sekar, G. Varghese, OSDI 2016 (extends header space verification to the control plane, especially BGP)
Packet Transactions: High-Level Programming for Line-Rate Switches, A. Sivaraman, A. Cheung, M. Budiu, C. Kim, M. Alizadeh, H. Balakrishnan, G. Varghese, N. McKeown, S. Licking, SIGCOMM 2016 (synthesizes stateful packet processing within a router from a higher level language to hardware)
Scaling Network Verification using Symmetry and Surgery. G. Plotkin, N. Bjorner, N. Lopes, A. Rybalchenko, G, Varghese, POPL 2016 (leveraging symmetries in the physical topologies of data centers)
High Speed Networks Need Proactive Congestion Control. L. Jose, L. Yan, M. Alizadeh, G. Varghese, N. Mckeown, S. Katti, HotNets 2015 (fast congestion control by solving rate equations directly without congestion signals)
Checking Beliefs in Dynamic Networks , N. Bjorner, P. Godefroid, K. Jayaraman, G. Varghese, NSDI 2015. Network Verification in the face of changing networks and incomplete specifications
Global analytics in the face of bandwidth and regulatory constraints , A. Vulimiri, C. Curino, B. Godfrey, J. Padhye, G. Varghese, NSDI 2015. Analytics across data centers.
Compiling Packet Programs to Recon?gurable Switches, L. Yan, L. Jose, G. Varghese, N. McKeown, NSDI 2015. Mapping from Logical Tables in a P4 Program to physical tables in a hardware pipeline
Life in the Fast Lane: A View from the Confluence Lens, G. Varghese, ACM CCR, Jan 15th based on SIGCOMM Keynote . Brief History of Network Algorithmics, and a framework for inter-disciplinary thinking.
> WANAlytics: Analytics for a Geo-Distributed Data-Intensive World, C. Curino, A. Vulimiri, B. Godfrey, K. Karanasos, G. Varghese, Proceedings Conference on Innovative Data Systems Research, CIDR 2015, Asilomar. General computation across data centers
P4: programming protocol-independent packet processors , P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C .Schlesinger, D. Talayco, A. Vahdat, G. Varghese, D. Walker: Computer Communication Review 44(3): 87-95 (2014) A new language for flexible routers that goes beyond OpenFlow
CONGA: Distributed Congestion-Aware Load Balancing for Datacenters M. Alizadeh et al, SIGCOMM 2014. Best paper award . Load balancing within network that goes beyond ECMP.
Adtributor: Revenue Debugging in Advertising Systems R. Bhagwan, R. Kumar, R. Ramjee, G. Varghese, S. Mohapatra, H. Manoharan, and P. Shah, NSDI 2014. Debugging Revenue Losses.
Gestalt: Fast, Unified Fault Localization for Networked Systems R. Mysore, R. Mahajan, A. Vahdat, G. Varghese: USENIX Annual Technical Conference 2014: 255-267. A taxonomy of fault localization.
Using Genome Query Language to uncover genetic variation. Bioinformatics. C. Kozanitis, A. Heiberg, G. Varghese, V. Bafna: 30(1): 1-8 (2014). Querying DNA Sequences.
Automatic Test Packet Generation H. Zeng, P. Kazemian, G. Varghese, N. McKeown. IEEE/ACM Trans. Netw. 22(2): 554-566 (2014) Automatically generating test vectors for a network.
Measuring Microscopic Latency and Loss in the Presence of Reordering. M. Lee, S. Goldberg, R. Kompella, G. Varghese. FineComb: IEEE/ACM Trans. Netw. 22(4): 1136-1149 (2014) Efficiently measuring microsecond latencies.
Forwarding Metamorphosis: Flexible Match Action processing for SDNs. P. Bosshart, G. Gibb, H. Kim, G. Varghese, M. Izzard, H. Mujica, M. Horowitz, SIGCOMM 2013.
MiG: Efficient Migration of Desktop VMs using Semantic Compression , A. Rai, R. Ramjee, A. Anand, V. Padmanabhan, G. Varghese, compressing OS pages to speedup VM migration, USENIX Annual Technical Conference, USENIX ATC 2013
Design Principles for Packet Parsers, G. Gibb, G. Varghese, M. Horowitz, N. Mckeown, ANCS 2013, Best Paper Award
Using Genome Query Language (GQL) to uncover genetic variation , C. Kozanitis, A. Heibert, G. Varghese, V. Bafna, HiTSeq Conference, July 2013.
Real time Network Policy Checking Using Header Space Analysis , P. Kazemanian, M. Chang, H. Zheng, G. Varghese, N. McKeown,S. Whyte, NSDI 2013.
Scalable Social Coordination using Enmeshed Queries , J. Chen, A Machanavajjhala, G. Varghese. Proceedings Conference on Innovative Data Systems Research, CIDR 2013, Asilomar, California.
Abstractions for genomics. Vineet Bafna, Alin Deutsch, Andrew Heiberg, Christos Kozanitis, Lucila Ohno-Machado, George Varghese: Communications of the ACM 56(1): 83-93 (2013)
Header Space Analysis: Static Checking for Networks , P. Kazemanian, G. Varghese, N. McKeown, NSDI 2012. Applied Networking Research Prize by the Internet Society in 2014, and presented to the IETF
Automatic Test Packet Generation , H. Zheng, P. Kazemanian, G. Varghese, N. McKeown, CoNEXT 2012. Fast tracked for IEEE Transactions Networking among best papers of CONEXT 2012
Lattice games and the Economics of aggregators , P. Jordan, U. Nadav, K. Punera, A. Skrzypacz, G. Varghese, World Wide Web conference,WWW 2012, Presentation at Stanford RAIN (Algorithms and Incentives) seminar 2012 . A game-theoretic model of aggregators such as Slashdot.
RadioJockey: mining program execution to optimize cellular data usage , P. Athivarapu, R. Bhagwan, S. Guha, V. Navda, R. Ramjee, D. Arora, V. Padmanabhan, G. Varghese, Mobicom 2012.
Biff (Bloom Filter) codes: Fast Error Correction for Large Data Sets , M. Mitzenmacher and George Varghese, IEEE International Symposium on Information Theory ISIT 2012,
Router Support for Fine-grained Latency Measurements , R. Kompella, K. Levchenko, A. Snoeren, G. Varghese, IEEE/ACM Transactions on Networking, 20(3), 2012.
The Complexity of Object Reconciliation and Open Problems related to Set Difference and Coding , M. Mitzenmacher and George Varghese, 2012 Annual Allerton Conference on Communication, Control and Computing
NetShare and Stochastic NetShare: predictable bandwidth allocation for data centers , V.T. Lam, S. Radhakrishnan, A. Vahdat, G. Varghese, ACM Computer Communications Review, 42(3): 5-11, 2012.
What's the Difference? Efficient Set Difference without Prior Context , D. Eppstein, M. Goodrich, F. Uyeda, G. Varghese, SIGCOMM 2011. Presentation at Stanford Information System Labs (ISL) seminar . First set difference algorithm that is optimal in computation and communication. Other questions on generalizations to graphs, sequences, and network coding in presentation.
Efficiently Measuring Bandwidth at all Time Scales , F. Uyeda, L. Fuschini, S. Suri, G. Varghese, NSDI 2011. A compact way of measuring bandwidth bursts at any time scale.
Fine Grain Latency and Loss Measurements in the Presence of Reordering , M. Lee, S. Goldberg, R. Kompella,G. Varghese, SIGMETRICS 2011. Extending a sketch for microsecond latency detection to allow for reordering.
Graption: a graph-based P2P traffic classification framework for the Internet Backbone , M. Iliotofu, H. Kim. M. Faloutsos, P. Papu, M. Mitzenmacher,G. Varghese, Computer Networks 55(8) 2011. A structure that reflects who talks to who in a network and its use in detecting P2P networks.
Compressing Genomic Sequence Fragments Using SlimGene. Christos Kozanitis, Christopher T. Saunders, Semyon Kruglyak, Vineet Bafna, George Varghese: Journal of Computational Biology 18(3): 401-413 (2011)
Carousel: Scalably Logging for Intrusion Prevention Systems, T. Lam, M. Mitzenmacher,G. Varghese, NSDI 2010. Logging infected sources despite small logging bandwidth and small local memory.
EndRE: An End-System Redundancy Elimination Service for Enterprises, B. Aggarwal, A. Akella, A. Anand, A. Balachandran, P. Chitis, C. Muthukrishnan, R. Ramjee, G. Varghese, NSDI 2010. Content compression as in companies like Riverbed but done end-to-end.
SlimGene: Compressing Genomic Sequences using SLIMGENE, C. Kozanitis, C. Saunders, S. Krugylak, V, Bafna, G. Varghese, RECCOMB 2010. Compressing 250 Gbytes of full sequence genomes. Being used in Illumina.
D. Gupta, S. Lee, M. Vrable, S. Savage, A. Snoeren, G. Varghese, G. Voelker, A. Vahdat: Difference engine: harnessing memory redundancy in virtual machines. Commun. ACM 53(10): 85-93 (2010) Invited as ACM Research Highlights
Leaping Multiple Headers in a Single Bound: Wire Speed Parsing using the Kangaroo System, C. Kozanitis, J. Huber, S. Singh G. Varghese, INFOCOM 2010. Making data planes (and not just control planes as in OpenFlow) flexible. Most network chip vendors are looking at flexible parsers today but Kangaroo was a little ahead of its time.
2009 Papers
Every Microsecond Counts: Tracking Fine-Grain Latencies with a Loss Difference Aggregator. SIGCOMM 2009,, R. Kompella, K. Levchenko, A. Snoeren, G. Varghese (see press articles in: Science Daily and Ars Technica
CrossTalk: Scalably Interconnecting Instant Messenger Networks, SIGCOMM WOSN Workshop, 2009,, M. Motoyama, G. Varghese. How can we make Yahoo IM talk to AIM?
Grassroots: Socially Driven Web Sites for the Masses, SIGCOMM WOSN Workshop, 2009,, F. Uyeda, D. Gupta, A. Vahdat, G. Varghese. Abstracts across different web sites such as YouTube, Flickr, Craig's List, and Facebook as "Search and Submit" websites and uses this to build a platform.
Mobiclique Middleware for Mobile Social Networking, SIGCOMM WOSN Workshop, 2009,, A. Pietilainen, E. Oliver, J. LeBrun, G. Varghese, C. Diot. Social Networks based on Bluetooth and Physical Propinquity. Was somewhat novel at the time.
Harnessing Memory Redundancy in Virtual Machines. OSDI 2008: 309-322 , D. Gupta, S. Lee, M. Vrable, S. Savage, A. Snoeren, G. Varghese, G. Voelker, A. Vahdat. Compressing memory across VMs. Award Paper
Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia, ,S. Kumar, B. Chandrasekaran J. Turner, G. Varghese, Proceedings ANCS 2007. Scaling the processing of multiple Regular Expressions.
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. A new measurement construct (who talks to who) that reflects causality and has some insights into P2P networks.
10 network papers that changed the world, George Varghese, Computer Communication Review 37(5) 77-80, 2007. My favorite networking papers.
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. One of 12 papers in the Wikipedia web page on self-stabilization. A way of making synchronous protocols self-stabilizing.
On Scalable Attack Detection in the Network, Ramana Rao Kompella, Sumeet Singh, George Varghese, IEEE/ACM Transactions on Networking, 2007. A sketch for DoS attack detection.
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 to Bloom State Machines, SIGCOMM 2006
Detecting Evasion Attacks at High Speeds without Reassembly, G. Varghese, J. A. Fingerhut, F. Bonomi, SIGCOMM 2006 , SIGCOMM 2006. Are reassembly and normalization (very expensive operations) needed for Intrusion Detection and Prevention?
An Improved Construction for Counting Bloom Filters, Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, George Varghese, European Symposium on Algorithms (ESA), 2006. Susprisingly fast algorithm for counting Bloom Filters.
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.