skip to content



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.

 

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.  There is a misconception, which is entirely my fault, that the idea came from Van Jacobsen---it did not.  This is hugely embarrassing, but the credit that got published in the subsequent RFC (RFC 1631) is incorrect.  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 trees, if done right, has many advantages over meshes, 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, I've since come to believe that the useful niche for DHT technology is awfully small (those applications where the economic model doesn't support a data-center approach, and the hash semantics are appropriate, and the scale is so large that a gossip-style approach doesn't work . . .).

 

Establishing Connections over the Internet

P. Francis, "Is the Internet Going NUTSS?," In IEEE Internet Computing, vol. 7, no. 6, pp. 94—96, Nov 2003

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

It is astonishing that, 25 years after RFC791 was published, one often cannot establish a connection over the Internet even when all parties involved wish to allow the connection.  While the blame is commonly laid at the feet of NAT, I think that firewalls have at least as much to do with it, which means that we wouldn't be much better off even were IPv6 to somehow take hold.  We suggest an alternative name-based signaling approach that allows the ends and the middle to explicitly negotiate terms.  An implementation that does NAT traversal for both UDP and TCP can can be found at http://nutss.net.

 

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

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

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)

Vivek Vishnumurthy, 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 19th 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

Tyler Steele, Vivek Vishnumurthy, Paul Francis, "A Parameter-free Load Balancing Mechanism for P2P Networks," IPTPS 2008, Feb 2008, Tampa Bay

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, “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

Paul Francis, "Pip Near-term Architecture," RFC 1621, May 1994

Jon Crowcroft, Paul Tsuchiya*, Tony Ballardie, "Core Based Trees - Scalable Multicast Routing," Internet Draft, July 1992

Paul Tsuchiya*, "Mutual Encapsulation Considered Dangerous," RFC 1326, May 1992

Paul Tsuchiya*, "On the Assignment of Subnet Numbers," RFC 1219, April 1991