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
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
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
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
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
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)
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
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
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
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
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
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 Tsuchiya*, "Efficient Utilization of Contiguous Two-level Hierarchical Addresses," Proceedings IEEE Globecom 92, Orlando Florida, December 1992
Paul Tsuchiya*, "Efficient and Flexible Hierarchical Address Assignment," Proceedings INET 92, Kobe Japan, June 1992
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*, "Team-of-Gateways: Design and Implementation," Proceedings MILCOM '87, Washington DC, October, 1987.
Refereed Workshop Publications
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.
Standards Publications
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