Scalable Internetworking

SCALABLE INTERNETWORKING

(1 April 1993 to 31 December 1995)

The Scalable Internetworking project was funded by DARPA/ITO at the University of California, Santa Cruz (UCSC) from 1 April 1993 to 31 December 1995.

This project was part of the research carried out within the Computer Communication Research Group (CCRG) of the Baskin School of Engineering at UCSC.

The principal investigators of this project were J.J. Garcia-Luna-Aceves and Anujan Varma.

Objective

Route computation in today’s internet routing protocols relies on mechanisms that either require replicating full topology information at each router, or communicating path-oriented information that leads to a combinatorial explosion when numerous service types or policies have to be supported. On the other hand, today’s ATM networks require fixed topologies and centralized handling of state data.

The objective of this project was to develop routing algorithms that can accommodate hundreds of thousands or millions of routing nodes and destinations; routing architectures that support connectionless services over ATM internets with multiple types of transmission media and mobile nodes; and multicasting algorithms applicable to large, high-speed networks.

Approach

Our approach consisted of advancing the state of the art in routing technology by developing, validating, and analyzing

  • Link-vector algorithms (LVA) that implement the selective diffusion of link states based on distributed computation of preferred paths that can take into account service types, policy restrictions, and the characteristics of transmission media.
  • More efficient mechanisms for termination detection in distance-vector and link-state algorithms, which can be used to improve the performance of existing interdomain and intradomain routing protocols.
  • Distributed approaches to multicasting, capable of optimizing both network cost and destination cost, and of supporting multiple types of service within the same multipoint session.
  • Scalable routing solutions for ATM networks, including: alternate virtual-path routing based on the algorithms listed above, scalable support of connectionless services within the current routing structure of ATM, and a routing structure for ATM different from virtual circuits and paths and aimed at connectionless traffic.

Our methodology consisted of algorithm design, verification, and performance analysis. The performance analysis of algorithms was based on analytical techniques and simulation.

Technology Transfer

Many of our results have been transitioned to other projects. Our research has direct applicability to the ongoing efforts within the Internet Engineering Task Force (IETF) on the development of scalable route computation solutions for internet routing.

Intra-domain and inter-domain routing protocols can be developed based on LVA and LPA that would be much more scalable than OSPF, RIP, and BGP/IDRP.

In the long term, our results will assist the Internet community in its migration toward an integrated-services internet able to support connection-oriented and connectionless services efficiently, based on ATM technology.

Publications

The following is the list of published papers describing our research results in this project. A more complete list of CCRG publications, including PDF format, can be found here.

  • F. Bauer and A. Varma, “ARIES: A Rearrangeable Inexpensive Edge-based On-line Steiner Algorithm,” Technical Report UCSC-CRL-95-36, July 1995. A shortened version appears in Proc. IEEE INFOCOM ’96.
  • F. Bauer and A. Varma, “Degree-Constrained Multicasting in Point-to-Point Networks,” Technical Report UCSC-CRL-95-08, February 1995. Proc. IEEE INFOCOM ’95, Boston, MA, April 1995.
  • F. Bauer and A. Varma, “Distributed Algorithms for Multicast Path Setup in Data Networks,” Technical Report UCSC-CRL-95-10, August 1995. Proc. IEEE GLOBECOM ’95, Singapore, Nov. 13-17, 1995.
  • F. Bauer and A. Varma, “Distributed Degree-Constrained Multicasting in Point-to-Point Networks,” Technical Report UCSC-CRL-95-09, March 1995.
  • Jochen Behrens and J.J. Garcia-Luna-Aceves, “Distributed, Scalable Routing Based on Link-State Vectors,” Proc. ACM SIGCOMM 94, London, UK, October 1994.
  • J.J. Garcia-Luna-Aceves and Y. Zhang, “Reliable Broadcasting in Dynamic Networks,” Proc. IEEE ICC 96, Dallas, Texas, June 23-27, 1996.
  • J.J. Garcia-Luna-Aceves and Jochen Behrens, “Distributed, Scalable Routing Based on Vectors of Link States,” IEEE Journal on Selected Areas in Communications, October 1995.
  • J.J. Garcia-Luna-Aceves and Shree Murthy, “A Path Finding Algorithm for Loop-Free Routing,” accepted for publication in IEEE/ACM Trans. Networking.
  • J.J. Garcia-Luna-Aceves and Shree Murthy, “A Loop-Free Path-Finding Algorithm: Specification, Verification and Complexity,” Proc. IEEE INFOCOM 1995, Boston, MA, April 1995.
  • L. Kalampoukas, A. Varma, and K. K. Ramakrishnan, An efficient rate allocation algorithm for ATM networks providing max-min fairness, Proc. Sixth IFIP International on High-Performance Networking (HPN ’95), Sept. 1995.
  • L. Kalampoukas and A. Varma, “Performance of TCP over Multi-Hop ATM Networks: A Comparative Study of ATM Layer Congestion Control Schemes,” Technical Report UCSC-CRL-95-13, Univ. of California at Santa Cruz, February 1995. A shortened version appears in Proc. IEEE ICC ’95, June 1995.
  • Shree Murthy and J.J. Garcia-Luna-Aceves, “Congestion-Oriented Shortest Multipath Routing,” Proc. IEEE INFOCOM 1996, San Francisco, March 1996.
  • Shree Murthy and J.J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks,” Wireless Networks, Special issue on Routing in Mobile Communication Networks, 1996.
  • Shree Murthy and J.J. Garcia-Luna-Aceves, “A Routing Protocol for Packet Radio Networks,” Proc. ACM Mobile Computing and Networking, Nov. 14-15, 1995.
  • Shree Murthy and J.J. Garcia-Luna-Aceves, “Dynamics of a Loop-Free Path-Finding Algorithm,” Proc. IEEE Globecom ’95, Singapore, Nov. 13-17, 1995.
  • Shree Murthy and J.J. Garcia-Luna-Aceves, “A More Efficient Path-Finding Algorithm,” Proc. 28th Asilomar Conference, Pacific Grove, CA, October 31-November 2, 1994.
  • Shree Murthy and J.J. Garcia-Luna-Aceves, “A Loop-Free Algorithm based on Predecessor Information,” Proc. ICCCN 1994, San Francisco, CA, 1994.
  • M. Parsa and J.J. Garcia-Luna-Aceves, “Scalable Internet Multicast Routing,” Proc. ICCCN 95, Las Vegas, Nevada, Sept. 20–23, 1995.
  • Q. Zhu, M. Parsa, and J.J. Garcia-Luna-Aceves, “A Source-Based Algorithm for Delay-Constrained Minimum-Cost Multicasting,” Proc. IEEE INFOCOM 95, Boston, MA, April 1995.