Publications | Paul Francis

Selected Publications

PhD Thesis

Here is my PhD Thesis from UCL, “Addressing in Internet Protocols“. Some people enjoy reading the epilogue to the thesis, which is a story about the interesting (and largely unknown) work being done in routing and addressing in the late 70’s by Postel, Sunshine, Cohen, Clark, and Cerf, and how most of that work failed to materialize in the Internet.

Diffix

Paul Francis, Sebastian Probst Eide, Reinhard Munz, “Diffix: High-Utility Database Anonymization” Annual Privacy Forum APF 2017, June 2017, Vienna

This paper gives an overview of Diffix, a technique for anonymously querying databases. I think it breaks new ground in the utility/privacy trade-off. For better or for worse, it is a departure from the formal approach to database privacy research that has dominated the CS community ever since Sweeney’s K-anonymity work in 2002. I’ve decided to put this at the top of my selected publications list. I think it is by far the best work I’ve ever done, for all that’s worth. The 2017 paper was the first version, which we’ve since labeled as Aspen. Subsequent versions are Birch (2019), Cedar (2020), Dogwood (2021), and Elm (2021).

Landmark Routing

Paul Tsuchiya*, “The Landmark Hierarchy: A New Hierarchy for Routing in Very Large Networks,” Proceedings SIGCOMM 88 Conference, Stanford, California, August, 1988

This is the first research I ever did, so I have a special nostalgia for it. One can argue against the practicality of this approach, but it would be hard to argue against the originality of it! Perhaps the key practical problem is that of how to deal with the massive address changes that can result from a single node (a high-level landmark) crashing. I designed an approach for dealing with this called “Assured Destination Binding“, which may very well be the first DHT (Distributed Hash Table). I owe a tremendous debt to Worth Kirkman, who was my office-mate at MITRE in those days. I was struggling with how to make landmarks work, and he suggested the hierarchy. Here are all of the MITRE technical reports associated with Landmark Routing: MTR-87W00050, MTR-87W00152, MTR-87W00174, MTR-89W00277.

*My name was later changed from Tsuchiya to Francis

Network Address Translation

Paul Tsuchiya*, Tony Eng, “Extending the IP Internet Through Address Reuse,” ACM SIGCOMM Computer Communications Review, 23(1):16-33, Jan. 1993

S. Guha and P. Francis. “Characterization and Measurement of TCP Traversal through NATs and Firewalls,” In Proceedings of Interet Measurement Conference (IMC), Berkeley, CA, Oct 2005

This is the original NAT paper, published in Sigcomm CCR. The original NAT paper did not include port translation, an improvement that increased the utility of NAT many times over. I am told by Rayan Zachariassen that Glenn Mackintosh independently invented NAT probably in 1993, and that immediately afterwards Rayan, Glenn, and Steve Lamb together invented the port translation enhancement. My big regret with NAT is not in having come up with the idea, but in giving into the community opinion on NAT and not working to enhance its functionality. The key improvement came some years later in 1998 when Dan Kegel discovered how two hosts behind NAT boxes can establish UDP connections (a technique now commonly known as STUN). Since then, my student Saikat Guha (and others) figured out how to do the same thing for TCP. Finally, over a decade since the first NAT RFC, the IETF is finally advising NAT vendors on how to build traversal-friendly NATs!

Shared Tree Multicast

Tony Ballardie, Paul Tsuchiya*, Jon Crowcroft, “Core Based Trees (CBT): An Architecture for Scalable Inter-Domain Multicast Routing,” SIGCOMM 93, San Francisco, Sept. 1993 (Best Student Paper Award)

This paper represents the first publication of the shared-tree concept. Up to this point, the Internet community was focusing on the Deering per-source tree approach to multicast, whereby a separate tree is built for each sender in the multicast group. This work triggered IETF standards activity which led to the PIM-SP (sparse mode) standard. Tony got the best student paper award in Sigcomm in 1993.

Shortcut Routing

Paul Tsuchiya*, “Internet Routing Over Large Public Data Networks using Shortcuts,” SIGCOMM 92, Baltimore Maryland, August 1992

This is the first paper to tackle the problem of how to scalably route over large (national or global) public data networks like ATM without resorting to the old ARPANET trick (or new IPv6 trick) of embedding the data network address inside the IP address. The approach in this paper, “shortcut routing”, assumes that the data network is IP unaware. This approach was adopted by the IPLPDN working group in the IETF. A better approach, which is to make the data network aware of IP routing, was originally suggested by Hiroshi Esaki and eventually became the basis for MPLS.

P2P Multicast

Paul Francis, “Yoid: Extending the Internet Multicast Architecture, ” Technical Report, April 2000

Vidhyashankar Venkatraman, Kaoru Yoshida, Paul Francis, “Chunkyspread: Heterogeneous Unstructured End System Multicast,” The 14th IEEE International Conference on Network Protocols, Nov. 2006

In 1998, Hui Zhang and I independently decided that end systems could self-form into multicast trees and themselves do multicast in lieu of (or in addition to) IP multicast. My original approach was called Yallcast, and was later renamed Yoid. This work spawned an entire research area that remains vibrant to this day, in part because of the creative shot-in-the-arm from BitTorrent. Our premise at the time was that IP multicast was not taking off, and that an end-system based approach might provide the way forward. As its turned out, the “problem” was mainly lack of a killer app, something that IPTV has now provided. As a result, both IP multicast and end-system (or P2P) multicast are today hot commercial items. Here are some protocol specifications (YDP, YTMP, YIDP) and talks (IETF, algorithms, future) on Yoid.

The “debate” in this area today centers around the question of how a “mesh” (or swarming) type approach compares with a more traditional “tree” approach. Though I’m in the minority, I think that meshes, if done right, has many advantages over trees, as the second paper above on Chunkyspread suggest.

Network Latency Estimation

Paul Francis, S. Jamin, C. Jin, Y. Jin, A. Kurc, D. Raz, Y. Shavitt, L. Zhang “IDMaps: A Global Internet Host Distance Estimation Service,” IEEE/ACM Transactions on Networking, Oct. 2001

One of the problems I encountered when trying to make end-system multicast trees is that of finding nearby peers (as measured by latency). That problem spawned this network latency estimation work, which was mainly carried out by Sugih Jamin. We imagined a network service (in the same sense that DNS is a network service) that would provide an estimate of the distance between any pair of IP addresses. In a nice piece of work, Eugene Ng later eliminated the need for an infrastructure service by simply having peers mutually calculate a coordinates-based “proximity address”.

Content Addressable Networks (CAN)

Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker, “A Scalable Content-Addressable Network,” SIGCOMM 2001, August, 2001, San Diego

One cannot, apparently, have a career in computer networking research without eventually co-authoring with Scott Shenker. This paper is one of the original “big three” DHT papers published all around the same time (along with Chord and Pastry). While these papers spawned a cottage industry in DHT research. For a long time I felt that DHTs were at best a niche technology, but they have proven themselves useful in file sharing networks and data centers.

IP Anycast Deployment

Hitesh Ballani, Paul Francis, “Towards a Global IP Anycast Service,” ACM SIGCOMM 2005, August, 2005, Philadelphia

Hitesh Ballani, Paul Francis, Sylvia Ratnasamy, “A Measurement-based Deployment Proposal for IP Anycast,” Proceedings of Internet Measurement Conference (IMC), Rio de Janeiro, Oct 2006 (Best Paper Award)

Our work in IP Anycast deployment started with an idea of how to solve a decade-old open problem: how to scale global IP Anycast by the number of anycast groups. Since publishing a solution in Sigcomm 2005, Hitesh has gone on to make extensive measurements of both existing IP anycast deployments (DNS roots mostly) and of his own deployment, and in so doing shedding light on issues such as proximity, affinity, and load balance. (For all its worth, I independently conceived of IP anycast in 1993: google for “tsuchiya nearcast”.)

Simplified Network Management

Hitesh Ballani, Paul Francis, “CONMan, a Step Towards Network Manageability,” ACM SIGCOMM 2007, August, 2007, Kyoto Japan

Network management is one of the biggest outstanding problems in networking today. It is expensive and error prone. While most work in this area focuses on new management tools that attack one problem or another, we believe that the network itself has to be made more amenable to management. Inspired by the 4D work, we are developing new abstractions, called Complexity Oblivious Network Management (CONMan), that present network protocols in simpler and semantically richer terms.

Complete List of Publications

Journal Publications

Paul Francis, S. Jamin, C. Jin, Y. Jin, A. Kurc, D. Raz, Y. Shavitt, L. Zhang “IDMaps: A Global Internet Host Distance Estimation Service,” IEEE/ACM Transactions on Networking, Oct. 2001

Paul Francis, “Comparison of Geographical and Provider-rooted Internet Addressing,” Computer Networks and ISDN Systems 27(3)437-448, 1994 (selected paper from INET 94/JENC 5)

Paul Tsuchiya*, Tony Eng, “Extending the IP Internet Through Address Reuse,” ACM SIGCOMM Computer Communications Review, 23(1):16-33, Jan. 1993

Refereed Conference Publications

Franziska Boenisch, Reinhard Munz, Marcel Tiepelt, Simon Hanisch, Christiane Kuhn, Paul Francis, “Side-channel attacks on query-based data anonymization”, CCS 2021

Paul Francis, Sebastian Probst Eide, Reinhard Munz, “Diffix: High-Utility Database Anonymization” Annual Privacy Forum APF 2017, June 2017, Vienna

Alexey Reznichenko, Paul Francis, “Private-by-Design Advertising Meets the Real World” ACM CCS, 2014

Ruichuan Chen, Istemi Ekin Akkus, Paul Francis, “SplitX: High-Performance Private Analytics,” ACM SIGCOMM 2013, August, 2013, Hong Kong

Stevens Le Blond, David Choffnes, Wenxuan Zhou, Peter Druschel, Hitesh Ballani, Paul Francis, “Towards Efficient Traffic-analysis Resistant Anonymity Networks,” ACM SIGCOMM 2013, August, 2013, Hong Kong

Istemi Ekin Akkus, Ruichuan Chen, Michaela Hardt, Paul Francis, Johannes Gehrke, “Non-tracking Web Analytics,” ACM Conference on Computer and Communications Security, CCS 2012

Ruichuan Chen, Alexey Reznichenko, Paul Francis, “Towards Statistical Queries over Distributed Private User Data,” USENIX Symposium on Networked Systems Design and Implementation, NSDI 2012

Zartash Afzal Uzmi, Markus Nebel, Ahsan Tariq, Sana Jawad, Ruichuan Chen, Aman Shaikh, Jia Wang, Paul Francis, “SMALTA: Practical and Near-Optimal FIB Aggregation,” ACM CONEXT 2011

Ruichuan Chen, Aman Shaikh, Jia Wang, Paul Francis, “Address-Based Route Reflection,” ACM CONEXT 2011

Alexey Reznichenko, Saikat Guha, Paul Francis, “Auctions in Do-Not-Track Compliant Internet Advertising”, ACM Conference on Computer and Communications Security, CCS 2011

Saikat Guha, Bin Cheng, Paul Francis, “Privad: Practical Privacy in Online Advertising,” USENIX Symposium on Networked Systems Design and Implementation, NSDI 2011

Saikat Guha, Alexey Reznichenko, Kevin Tang, Hamed Haddadi and Paul Francis, “Serving Ads from localhost for Performance, Privacy, and Profit,” In Proceedings of the 8th Workshop on Hot Topics in Networks HotNets ’09, 2009

Hamed Haddidi, Saikat Guha, Paul Francis, “Not All Adware is Badware: Towards Privacy-aware Advertising,” IFIP I3E 2009, Nancy, France, Sept. 2009

Hitesh Ballani, Paul Francis, Tuan Cao, Jia Wang, “Making Routers Last Longer with ViAggre,” ACM NSDI 2009, April 2009, Boston

Hitesh Ballani and Paul Francis, “Fault Management Using the CONMan Abstraction,” Infocom 2009, April 2009, Rio De Janeiro

Hitesh Ballani and Paul Francis, “Mitigating DNS DoS Attacks,” 15^th ACM Conference on Computer and Communication Security, CCS 2008, Alexandria, VA, Oct. 2008

Vivek Vishnamurthy and Paul Francis, “On the Difficulty of Finding the Nearest Peer in P2P Systems,” ACM SIGCOMM Internet Measurement Conference, IMC 2008, Oct. 2008, Vouliagmeni, Greece

Changxi Zheng, Lusheng Ji, Dan Pei, Jia Wang, Paul Francis, “A Light-Weight Distributed Scheme for Detecting IP Prefix Hijacks in Realtime,” ACM SIGCOMM 2007, August, 2007, Kyoto Japan

Hitesh Ballani, Paul Francis, “CONMan, a Step Towards Network Manageability,” ACM SIGCOMM 2007, August, 2007, Kyoto Japan

Hitesh Ballani, Paul Francis. Xinyang Zhang, “A Study of Prefix Hijacking and Interception in the Internet,” ACM SIGCOMM 2007, August, 2007, Kyoto Japan

Saikat Guha, Paul Francis, “An End-Middle-End Approach to Connection Establishment,” ACM SIGCOMM 2007, August, 2007, Kyoto Japan

Vivek Vishnumurthy, Paul Francis, “A Comparison of Structured and Unstructured P2P Approaches to Heterogeneous Random Peer Selection,” In Proceedings of the Usenix Annual Technical Conference, 2007, Santa Clara, CA

Vidhyashankar Venkatraman, Kaoru Yoshida, Paul Francis, “Chunkyspread: Heterogeneous Unstructured End System Multicast,” The 14th IEEE International Conference on Network Protocols, Nov. 2006

Xinyang Zhang, Paul Francis, Jia Wang, Kaoru Yoshida, “Scaling Global IP Routing with the Core Router-Integrated Overlay,” The 14th IEEE International Conference on Network Protocols, Nov. 2006

Vivek Vishnamurthy, Paul Francis, “On Heterogeneous Overlay Construction and Random Node Selection in Unstructured P2P Networks,” Infocom 2006, April 2006, Barcelona

S. Guha and P. Francis. “Characterization and Measurement of TCP Traversal through NATs and Firewalls,” Proceedings of Internet Measurement Conference (IMC), Berkeley, CA, Oct 2005

Hitesh Ballani, Paul Francis, “Towards a Global IP Anycast Service,” SIGCOMM 2005, August, 2005, Philadelphia

Manpreet Singh, Prashant Pradhan, Paul Francis, “MPAT: Aggregate TCP Congestion Management as a Building Block for Internet QoS” 12th IEEE International Conference on Network Protocols (ICNP 2004), October 2004

Paul Francis, Ramakrishna Gummadi, “IPNL: A NAT-Extended Internet Architecture,” SIGCOMM 2001, August, 2001, San Diego

Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker, “A Scalable Content-Addressable Network,” SIGCOMM 2001, August, 2001, San Diego

Paul Francis, Sugih Jamin, Vern Paxson, Lixia Zhang, Daniel Gryniewicz, Yixin Jin, “An Architecture for a Global Internet Host Distance Estimation Service,” Proceedings INFOCOM ’99, New York City, March 1999

Paul Francis, Susumu Shimizu, Takashi Kambayashi, and Shin-ya Sato, “A Framework for Multilingual Searching and Meta-information Extraction,” Proceedings INET 97, Kuala Lumpur, June 1997

Paul Francis, Shin-ya Sato, “Design of a Database and Cache Management Strategy for a Global Information Infrastructure,” Proceedings of the Third International Symposium on Autonomous Decentralized Systems, pp. 283-290, April 1997

Paul Francis, Susumu Shimizu, “De-Centralized Web Searching: An Alternative Paradigm”, Proceedings 19^th Pacific Telecommunications Conference, Honolulu, Jan. 1997.

Paul Francis, Takashi Kambayashi, Shin-ya Sato, Susumu Shimizu, “Ingrid: A Self-Configuring Information Navigation Infrastructure,” Proceedings 4th International WWW Conference, Dec. 1995, pp. 519-538

Paul Francis, Ramesh Govindan, “Flexible Routing and Addressing for a Next Generation IP,” SIGCOMM 94, September 1994, London

Paul Francis, “Comparison of Geographical and Provider-rooted Internet Addressing,” Proceedings INET 94/JENC 5, Prague, June 1994

Tony Ballardie, Paul Tsuchiya*, Jon Crowcroft, “Core Based Trees (CBT): An Architecture for Scalable Inter-Domain Multicast Routing,” SIGCOMM 93, San Francisco, Sept. 1993. This paper won the Best Student Paper award

Tony McAuley, Paul Francis, “Fast Routing Table Lookup using Content Addressable Memory (CAM),” INFOCOM 93, March 1993

Paul Tsuchiya*, “Efficient Utilization of Contiguous Two-level Hierarchical Addresses,” Proceedings IEEE Globecom 92,Orlando Florida, December 1992

Paul Tsuchiya*, “Internet Routing Over Large Public Data Networks using Shortcuts,” Proceedings SIGCOMM 92 Conference, Baltimore Maryland, August 1992

Paul Tsuchiya*, “Efficient and Flexible Hierarchical Address Assignment,” Proceedings INET 92, Kobe Japan, June 1992

Paul Tsuchiya*, “Efficient and Robust Policy Routing using Multiple Hierarchical Addresses,” proceedings SIGCOMM 91 Conference, Zurich, Switzerland, September 1991

Paul Tsuchiya*, “On the Graceful Degradation of Routing Given Insufficient Resources,” Proceedings 14th Conference on Local Computer Networks, Minneapolis Minnesota, October, 1989

Paul Tsuchiya*, “Simulation of a Large Network Distributed Routing Algorithm using OPNET,” Proceedings DCA/JDSSC Computer-based Modeling Symposium, September 1988.

Paul Tsuchiya*, “The Landmark Hierarchy: A New Hierarchy for Routing in Very Large Networks,” Proceedings SIGCOMM 88 Conference, Stanford, California, August, 1988

Paul Tsuchiya*, “Team-of-Gateways: Design and Implementation,” Proceedings MILCOM ’87, Washington DC, October, 1987.

Refereed Workshop Publications

Saikat Guha, Paul Francis, “Identity Trail: Covert Surveillance Using DNS,” Workshop on Privacy Enhancing Technologies, PET 2007, June 2007, Ottawa Canada

Hitesh Ballani, Paul Francis, “A Simple Approach to DNS DoS Defense”, ACM Sigcomm Hotnets Workshop, Nov 2006

Hitesh Ballani, Paul Francis, “CONMan: Taking the Complexity out of Network Management,” Sigcomm Internet Network Management Workshop, Sept. 2006, Pisa

Vidhyashankar Venkatraman, Paul Francis, “Chunkyspread: Multi-tree Unstructured End System Multicast,” IPTPS 2006, February 2006

Hitesh Ballani, Paul Francis, “Towards a deployable IP Anycast service,” First Workshop on Real, Large Distributed Systems (WORLDS ’04), Dec 2004

Saikat Guha, Paul Francis, Takeda Yutaka, “NUTSS: A SIP-based Approach to UDP and TCP Network Connectivity,” Sigcomm Future Directions in Network Architecture (FDNA-04) Workshop, August 2004

Paul Tsuchiya*, “An Architecture for Network-Layer Routing in OSI,” SIGCOMM 87 Workshop, Stowe, Vermont, Computer Communication Review, Volume 17, Number 5, August, 1987

Non-refereed Publications

Paul Francis, Sebastian Probst-Eide, David Wagner, Felix Bauer, Cristian Berneanu, Edon Gashi, “Diffix Elm: Simple Diffix,” ArXiv, 2022.

Paul Francis, “Procedures and Rules for the 2020 Diffix Bounty Program,” Technical Report MPI-SWS-2021-002, 2021.

Paul Francis, “Specification of Diffix Dogwood,” Technical Report MPI-SWS-2021-001, 2021.

Paul Francis, “Specification of Diffix Cedar,” Technical Report MPI-SWS-2020-006, 2020.

Paul Francis, “Dear Differential Privacy: Put Up or Shut Up,” Technical Report MPI-SWS-2020-005, 2020.

Paul Francis, “Formal Vs Empirical Approaches to Data Anonymity,” Data, Privacy, and the Individual. Madrid: Center for the Governance of Change, 2019

Paul Francis, “Procedures and Rules for Phase 1 of the Diffix Bounty Program,” Technical Report MPI-SWS-2018-007, 2018.

Paul Francis, Sebastian Probst Eide, Pawel Obrok, Cristian Berneanu, Sasa Juric, Reinhard Munz, “Diffix-Birch: Extending Diffix-Aspen,” ArXiv, 2018

Paul Francis, “Is the Internet Going NUTSS?,” IEEE Internet Computing, Nov-Dec 2003

Paul Francis, “IPNL Architecture and Protocol Description,” May, 2000

Paul Francis, Yukata Ogawa, “Next-Generation Protocol for Internetworking,” NTT R&D Journal, 43(9):41-50, 1994, in Japanese.

Paul Francis, “A Near-term Architecture for Deploying Pip,” IEEE Network Magazine, 7(6):30-37, May 1993.

Paul Tsuchiya*, “Inter-domain Routing in the Internet,” Connexions Interoperability Report, Volume 5, No. 1, January 1991.

Paul Tsuchiya*, “The Landmark Hierarchy: A New Hierarchy for Routing in Very Large Networks,” Reprint Collection: Outstanding Papers on Key Topics in Computer Networking, ARTECH House, 1989 (reprinted from SIGCOMM 88).

Paul Tsuchiya*, “IS-IS Intra-Domain Routing,” Connexions Interoperability Report, Volume 3, No. 8, August 1989.

Paul Tsuchiya*, “An Overview of OSI Routing,” Connexions Interoperability Report, Volume 3, No. 8, August 1989.

Paul Tsuchiya*, “Landmark routing: Architecture, algorithms, and issues”, MTR-87W00174, The MITRE Corp., May 1988

Paul Tsuchiya*, “The Landmark Hierarchy: Description and Analysis,” MTR-87W00152, McLean, VA: The MITRE Corp., June 1987

Paul Tsuchiya*, “Assured Destination Binding: A Technique for Dynamic Address Binding,” MTR-87W00050, McLean, VA: The MITRE Corporation, March 1987

Standards Publications

P. Francis, S. Guha, S. Brim, M. Shore, “An EME Signaling Protocol Design,” Internet Draft: draft-irtf-eme-francis-nutss-design-00.txt, April 2007

S. Guha, P. Francis, “Requirements for the End-Middle-End Research Group,” Internet Draft: draft-guha-emerg-requirements-00.txt, Feb 2007

S. Guha, K. Biswas, B. Ford, P. Francis, S. Sivakumar, P. Shrisuresh, “NAT Behavioral Requirements for Unicast TCP,” Internet Draft: draft-hoffman-behave-tcp-04, Feb 2006

P. Francis, “IPv6 Site Definition,” Internet Draft: draft-francis-ipngwg-site-def-00.txt, April 1, 2001

K. Egevang, Paul Francis, “The IP Network Address Translator (Nat),” RFC 1631, May 1994

Paul Francis, “Pip Header Processing,” RFC 1622, May 1994