FTI

FAULT-TOLERANT INTERNETWORKING

The Fault-Tolerant Internetworking project is funded by DARPA at the University of California, Santa Cruz (UCSC).

At UCSC, this project is part of the research carried out within the Computer Communication Research Group (CCRG) of the Baskin School of Engineering.

The principal investigator of this project is J.J. Garcia-Luna-Aceves.

Project Name:
Fault Tolerant Internetworking (FTI)
Contract No:
N6601-00-1-8942
Contractor:
University of California, Santa Cruz (UCSC)

Objective

Today’s Internet routing infrastructure is not fault tolerant. Although some advances have been made in the recent past to secure the Internet, it remains highly vulnerable to attacks and faults, and Requires considerable involvement of system administrators. Internet routing within and across autonomous systems is based on single-path routing algorithms whose performance is known to deteriorate rapidly in the presence of failures. Static link characteristics or policies are currently used for routing, which are oblivious to mounting congestion or attacks. Although there are proposals on how to protect information exchange in Internet routing protocols, no protocol built to date is capable of detecting and responding to attacks. Multicast routing support is based on multicast routing trees and single cores or rendezvous points, which are very easy to break. Furthermore, support for the creation and maintenance of secure multicast groups is in its infancy and research results have started to emerge only in recent years. The proposals for the provision of QoS in the Internet (i.e., the Diffserv and Intserv architectures) assume the same underlying single-path routing strategies, which renders them very susceptible to failures and attacks. Even TCP is vulnerable to simple attacks forcing packets to arrive out of order, in which case TCP reduces its congestion window and behaves as a stop-and-wait protocol. End-to-end solutions for protecting network infrastructures are also very limited. Today’s virtual private networks (VPNs) are designed based on tunnels, which are manually configured and become very difficult to manage when a VPN grows in size or mobile routers need to be supported. End-to-end security relies on firewalls and the notion that the routing infrastructure is trusted and stable for the distribution of critical information (e.g., key distribution).

The Fault-toletarnt Internetworking project aims at developing a new architecture and protocols for fault-tolerant internetworking, such that: (a) routers can protect efficiently against attacks and faults, and detect and respond to them in a timely manner; (b) no routing and multicasting function has single points of failure; and (c) QoS guarantees are provided in a scalable and fault-tolerant manner.

Approach

The approach followed in this project consists of advancing the state of the art in the following areas:

  1. Trust Algebra For Access Control With Delegation: This project applies a set theoretic approach to extend the traditional access matrix model of access control to permit multiple routing and certificate authorities to be trusted by routers from different networks and domains, permitting a router or host to delegate trust to another node (router or host) and be configured with just the public key and name (IP address) of a single routing authority in addition to its own private key.
  2. Fault-Tolerant, Secure Internetworking: This project extends the existing IP Internet model for inter-connection of physical networks into an architecture in which IP and a signaling protocol for establishing and maintaining secure meshes are used for the creation of virtual secure networks (VSN). A VSN can change its topology according to its user constituency and may span multiple physical networks. Within such VSNs, fault-tolerant protocols are used for routing and multicasting.
  3. Efficient authentication of routing updates: This project is analyzing the use of techniques developed for forward error correction to reduce the overhead incurred in processing signed routing updates at routers.
  4. Fault-tolerant QoS guarantees: Routing and multicasting protocols that support fault-tolerant QoS guarantees within VSNs, or in the Internet in general, will be developed. These protocols are intended to: aggregate flows based on their classes and destinations, thus eliminating a key scaling problem of the Intserv architecture; use multiple loop-free paths (called multipaths to distribute aggregated flows, which eliminates the failure-prone nature of virtual circuits; establish signaling to reserve resources for aggregated flows only between trusted neighbors, which is much more robust and adaptive than end-to-end signaling; integrate routing and reservation control so that packets are forwarded over multipaths, which reduces congestion and tolerates link and node failures; and forward time-critical or priority packets over multiple segments of a multipath to reduce latency or increase the likelihood of delivery.

Recent Accomplishments

The research work in this project has resulted in four refereed papers published in conference proceedings. With support from this project, one Ph.D. thesis was completed and one Ph.D.thesis proposal accepted at UCSC. The thesis completed and articles published are the following:

  1. Srinivas Vutukury, “Multipath Routing Mechanisms for Traffic Engineering and Quality of Service in The Internet,” PhD Thesis, Computer Science, University of California, Santa Cruz, March 2001.
    http://www.cse.ucsc.edu/research/ccrg/publications/vutukury.phd.pdf
  2. S. Vutukury and J.J. Garcia-Luna-Aceves, “A Multipath Framework Architecture for Integrated Services,” Proc. IEEE Globecom 2000, San Francisco, California, USA, Nov. 27 – Dec. 30, 2000.
    http://www.cse.ucsc.edu/research/ccrg/reports/FTI/qlob00cr.pdf
  3. S. Vutukury and J.J. Garcia-Luna-Aceves, “A Traffic Engineering Approach based on Minimum-Delay Routing,” Proc. IEEE IC3N 2000, Las Vegas, Nevada, USA, October 16–19, 2000.
    http://www.cse.ucsc.edu/research/ccrg/reports/FTI/ic3n00.pdf
  4. S. Vutukury and J.J. Garcia-Luna-Aceves, “SMART: A Scalable Multipath Architecture for Intra-domain QoS Provisioning,” QOS-IP 2001, International Workshop on QoS in Multiservice IP Networks, Rome, Italy, January 24–26, 2001.
    http://www.cse.ucsc.edu/research/ccrg/reports/FTI/qosip00cr.pdf
  5. S.. Vutukury and J.J. Garcia-Luna-Aceves, “A Simple MPLS-based Flow Aggregation Scheme for Providing Scalable Quality of Service,” SPIE ITCom 2001: International Symposium on The Converge of IT and Communications, 19-24 August 2001, Denver, Colorado.
    http://www.cse.ucsc.edu/research/ccrg/reports/FTI/qosip00cr.pdf

The key technical contributions and progress made over the past year can be summarized as follows:

  • Started developing an architecture for secure multicasting and secure routing infrastructures that operates by separating group authorization from group membership, which in prior approaches to secure multicasting were bound together. The main implication of the architecture is the ability to build virtual secure networks (VSNs) without requiring every router in the Internet to be allowed to be part of every VSN, which would not be feasible.
  • Developed better heuristics for the creation and maintenance of fault-tolerant group meshes, such that the topologies of VSNs have as few single points of failure as possible (e.g., single routers or links that represent a cut in the subgraph of a VSN).
  • Developed new multicast build and repair methods that save bandwidth, render wasteful general floods unnecessary, and repair reliable-traffic multicast trees with maximum speed and bandwidth efficiency.
  • Developed an architecture and protocols for providing deterministic QoS guarantees in the presence of failures, attacks, or node mobility. This architecture aggregates flows based on their classes and destinations, uses multiple loop-free paths computed distributedly, and establishes signaling to reserve resources for aggregated flows only between neighbors. This is the only solution to date for the provisioning of QoS guarantees that does not rely on any form of virtual circuits.
  • Developed the notion of label-switched multipaths (LSMPs) and a simple technique for aggregating label-switching paths, such as those maintained by MPLS, into LSMPs. The result of this is that the number of labels required in the routers is significantly reduced. Based on LSMPs we developed an architecture for providing deterministic guarantees that is far more scalable than architectures based on simple LSPs or those that use only multipoint-to-point LSP aggregation. Our architecture employs new flow aggregation schemes to provide deterministic guarantees in the presence of flow aggregation. The LSMP aggregation is more powerful than the well-known multipoint-to-point aggregation and can also be used in other contexts such as Traffic Engineering and Differential Services architectures.
  • Developed a new approach to connection-less traffic engineering, which is much more fault-tolerant than the connection-oriented approach advocated in the Internet today.

Current Plan

The following are the anticipated development milestones during the following 12 months of this project. Milestones related to the publication of fundamental theoretical results or journal and conference papers are not listed:

  • 4 months: Complete simulation of tree repair protocols supporting qualified multicasting and protocols for building and maintaining group meshes for VSNs.
  • 6 months: Complete specification of “differentiated multicast architecture” for secure multicasting using trust algebra.
  • 8 months Release ns2 simulation code to other research groups.
  • 12 months: Implementation of secure unicast routing protocol and Mesh Administration Protocol (MAP) in gated.

Technology Transition

The following steps will be taken to foster technology transition in this project:

  • CAIRN Community: An integral part of the development effort will be to disseminate protocol specifications and implementations to the CAIRN community. To this end, the protocol implementations will use gated. The source code of simulations in ns2 and gated code will be made available toother research groups.
  • Virtual Secure Networking: This project will collaborate with NRL in applying the results on VSNs and mesh multicasting in general to scenarios and applications that are relevant to the Navy.
  • Protocol Specification: The members of this project will collaborate with SRI International (SRI) and Stanford on the use of the Maude Tool for the specification and implementation in Maude of fault-tolerant protocol(s).