-
Research Overview
Our research focus is computer networking, including overlays, with a focus on routing and addressing issues. Our approach is practical in nature. Where possible, we base our work on prototype implementations, measurements, and deployments. We try to operate in that thin slice between blue sky ideas with no immediate practical need, and ideas that are so obviously practical that industry is already working on them. We prefer ideas that are incrementally deployable.
Active Research Projects:
Scaling Global IP Routing
Global IP routing scalability is based on hierarchical routing, which requires that the IP address hierarchy be aligned with the physical topology. Both site multi-homing and switching ISPs without renumbering break this alignment, resulting in large and constantly growing routing tables. A tangible problem caused by this is that ISPs must periodically upgrade their router hardware because the global routing table outgrows the physical memory. The goal of this research is to design new approaches to IP scalability for both global and VPN routing. In previous work, we designed an approach called the Core Router-Integrated Overlay (CRIO), that uses tunneling and virtual prefixes to decouple address hierarchy and physical topology, effectively giving ISPs the ability to trade-off routing table size for path length. Although CRIO works with existing data-plane router mechanisms, it required changes to router software and new control protocols. We have since figured out how to apply the basic ideas of CRIO without requiring any changes to routers, and without requiring coordination between ISPs. Rather, all that is needed is a a novel configuration of routers and route reflectors.
P. Francis, H. Ballani, T. Cao, "A White Paper on Reducing FIB Size through Virtual Aggregation,"
X. Zhang, P. Francis, J. Wang, K. Yoshida, "Scaling Global IP Routing with the Core Router-Integrated Overlay," The 14th IEEE International Conference on Network Protocols, Nov. 2006
CRIO Talk at the Cisco Routing Research Summit, Aug 2006
Complexity Oblivious Network Management (CONMan)
Network management is difficult, costly, and error prone, and this is becoming more so as network complexity increases. We argue that this is an outcome of two fundamental flaws in the existing architecture: the management plane depends on the data plane, and network device management interfaces are varied, complex, and constantly evolving. The goal of this research project is to design and build a new approach to network management whereby the management plane does not depend on the data plane and all data plane protocols expose a simple generic management interface. This restricts the operational complexity of protocols to their implementation and allows the management plane to achieve high level policies in a structured fashion.
Name- and Signaling-based Network Connection Establishment (aka NUTSS)
Fifteen years after the first firewalls and NAT boxes were installed, accurate access control on the Internet is still out-of-reach---allowed flows are often blocked, disallowed flows sometimes occur. The goal of this research is to use name-based signaling (think SIP) to provide much richer information to end users and firewalls to increase access control accuracy as well as to traverse NATs (including v4-v6 NATs). As a first step, we have characterized and largely solved the NAT traversal problem for TCP. Now we are designing and building the set of signaling protocols needed to do this. An IRTF research group is being created to further this work within a broader community.
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.
S. Guha et al. "NAT Behavioral Requirements for Unicast TCP," Internet Draft: draft-ietf-behave-tcp-00, February 2006. Work in progress.
S. Guha, Y. Takeda and P. Francis. "NUTSS: A SIP based approach to UDP and TCP connectivity," In Proceedings of Special Interest Group on Data Communications (SIGCOMM) Workshops, Portland, OR, Aug 2004, pp. 43—48.
P. Francis. "Is the Internet Going NUTSS?," In IEEE Internet Computing, vol. 7, no. 6, pp. 94—96, Nov 2003
P2P Multicast
Multicast has finally found its killer app, IPTV. While ISPs are using IP multicast for mainstream TV channels, a number of startups are using P2P to distribute niche content. There are broadly two technical approaches to P2P multicast: traditional multi-tree based, and mesh-based, with or without network coding. While the research community is leaning towards mesh-based as the best approach, we are not convinced that it is clearly better than tree-based, especially with regards to latency and processing overhead. Using our own unstructured tree-based P2P multicast protocol as a basis of comparison, the goal of this research is to deeply understand the characteristics of these two approaches.
Vidhyashankar Venkataraman, Paul Francis, John Calandrino, "Chunkyspread: Multi-tree Unstructured Peer to Peer Multicast," IPTPS 2006
Vidhyashankar Venkataraman, Kaoru Yoshida, Paul Francis, "Chunkyspread: Heterogeneous Unstructured End System Multicast," The 14th IEEE International Conference on Network Protocols, Nov. 2006.
"Trees Versus Meshes: Is the Debate Over?" talk presented at the P2P Streaming Workshop, Sept. 2006, Pisa Italy
Building random P2P networks, random node selection in P2P networks, and proximity addressing in P2P networks
Many P2P applications require an unstructured mesh topology between peers. The goal of this research is two-fold. First, we want to be able to build random P2P networks, and do random node discovery in those networks, with good control over peers' node degrees and the probability of selection. The idea is to accommodate resource heterogeneity among nodes: peers with greater capacity could have proportionally higher node degree or probability of selection. This portion of the project is largely done in the form of a simple algorithm called Swaplinks, which is now being used to support other projects (Chunkyspread and NUTSS). The second goal of this project is to design a proximity addressing scheme that is far more accurate than approaches like GNP or Vivaldi. The main insight here is to form hierarchical proximity addresses, where different levels of the hierarchy encode proximity at different time-scales. We envision using hierarchically nested mesh networks (using Swaplinks) to support discovery and creation of the addresses.
Vivek Vishnumurthy, Paul Francis, "On Overlay Construction and Random Node Selection in Heterogeneous Unstructured P2P Networks," IEEE Infocom 2006, April 2006, Barcelona
Transport protocol for high bandwidth-delay networks
TCP performance over high bandwidth-delay networks is notoriously poor. Not only does slow-start take a long time to reach its max throughput, but in the face of even a small packet loss rate, the throughput drops dramatically. There has been nice progress towards solving this problem, in the form of FastTCP, which uses RTT measurements in addition to lost packets to improve throughput, and XCP, where routers take an active and explicit role in determining the appropriate throughput for flows. We are researching an approach, called Priority-layered Transport (PLT), that is complementary to the above, particularly FastTCP. PLT assigns packets from a given single transport flow into two strict priority classes. This results in two flows, a high-priority flow and a low-priority flow. The high-priority flow, which runs at the same priority level as competing TCP flows (i.e. best effort), operates conservatively (AIMD). The low-priority flow, however, operates aggressively, thus exploiting spare capacity in the network. Because the two flows are strictly prioritized, however, the aggressive low-priority flow never interferes with the conservative high-priority flow or other TCP flows. This isolation affords us considerable flexibility in the design of the aggressive low-priority component of the congestion control algorithm.
Vidhyashankar Venkataraman, T. V. Lakshman, Paul Francis, Saikat Guha,
Murali. S. Kodialam, Manpreet Singh, "A priority-layered approach to transport for high bandwidth-delay product networks," Submitted to ACM Hotnets 2006
Current PhD Student Researchers
Hitesh Ballani
Vidhyashankar Venkataraman
Xinyang (Joy) Zhang
Previous Research Projects:
IP Anycast Deployment
IP Anycast has long been a promising IP addressing mode for low-level service discovery and failover. It is used today, for instance, to replicate root DNS services. Native IP Anycast, however, is difficult to deploy, scales poorly with the number of groups, and is wasteful of the IP address space. The goal of this research is to find new ways to deploy IP Anycast that overcomes these problems as well as offers good service in terms of flow affinity, proximity, load balance, and fast failover. We have designed a proxy/tunnel based deployment model called PIAS (Proxy IP Anycast Service), and are doing a measurement-based study of how best to deploy native IP Anycast.
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)
Firebreak Cross-ISP IP-level DoS Defense Architecture
For a while I was working on an IP Anycast / Tunneling based architecture for DoS Defense which I called Firebreak. A rejected Hotnets 2004 paper on the subject is posted below. I also gave a talk on this at a number of places in the summer of 2004. I stopped working in this area when I came to realize that the model being put in place by major ISPs, based for instance on the Riverhead model, is quite similar to the Firebreak model. The main difference is that Firebreak is cross-ISP, and has a different control model, but I doubt that this difference is really compelling in practice.
P. Francis, "Firebreak: An IP Perimeter Defense Architecture," Rejected by Hotnets 2004
Past PhD Student Researchers
Manpreet Singh, ``End-to-End Techniques for Network Resource Management,'' Department of Computer Science, Cornell University, Summer 2006. Co-advised by Prashant Pradhan, IBM. Employment: Google. (Also received offers from Cisco, Oracle, AskJeeves, Citigroup and Lehman Brothers)
