Declarative routing: extensible routing with declarative queries

ABSTRACT

The Internet's core routing infrastructure, while arguably robust and efficient, has proven to be difficult to evolve to accommodate the needs of new applications. Prior research on this problem has included new hard-coded routing protocols on the one hand, and fully extensible Active Networks on the other. In this paper, we explore a new point in this design space that aims to strike a better balance between the extensibility and robustness of a routing infrastructure. The basic idea of our solution, which we call declarative routing, is to express routing protocols using a database query language. We show that our query language is a natural fit for routing, and can express a variety of well-known routing protocols in a compact and clean fashion. We discuss the security of our proposal in terms of its computational expressive power and language design. Via simulation, and deployment on PlanetLab, we demonstrate that our system imposes no fundamental limits relative to traditional protocols, is amenable to query optimizations, and can sustain long-lived routes under network churn and congestion.

REFERENCES

• 1: GT-ITM. http://www.cc.gatech.edu/projects/gtitm/.
• 2: PIER. http://pier.cs.berkeley.edu.
• 3: SafetyNet. http://www.cogs.susx.ac.uk/projects/safetynet/.
• 4: WorldCom's Global UUNET Internet network. http://library.mobrien.com/manuals/mprm_group/uunet.jpg.
• 5: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 6: Rakesh Agrawal, Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries, IEEE Transactions on Software Engineering, v.14 n.7, p.879-885, July 1988 [doi>10.1109/32.42731]
• 7: Hari Balakrishnan , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Looking up data in P2P systems, Communications of the ACM, v.46 n.2, February 2003 [doi>10.1145/606272.606299]
• 8: I. Balbin , K. Ramamohanarao, A generalization of the differential approach to recursive query evaluation, Journal of Logic Programming, v.4 n.3, p.259-262, Sept. 1987 [doi>10.1016/0743-1066(87)90004-5]
• 9: Tony Ballardie , Paul Francis , Jon Crowcroft, Core based trees (CBT), Conference proceedings on Communications architectures, protocols and applications, p.85-95, September 13-17, 1993, San Francisco, California, United States
• 10: C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
• 11: B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
• 12: Diego Calvanese , Giuseppe De Giacomo , Moshe Y. Vardi, Decidable Containment of Recursive Queries, Proceedings of the 9th International Conference on Database Theory, p.330-345, January 08-10, 2003
• 13: W. F. Clocksin , C. S. Mellish, Programming in Prolog, Springer-Verlag New York, Inc., New York, NY, 1987
• 14: D. Tennenhouse and J. Smith and W. Sincoskie and D. Wetherall and G. Minden. A Survey of Active Network Research. In IEEE Communications Magazine, 1997.
• 15: Nick Feamster , Hari Balakrishnan , Jennifer Rexford , Aman Shaikh , Jacobus van der Merwe, The case for separating routing from routers, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016707.1016709]
• 16: M. Handley, A. Ghosh, P. Radoslavov, O. Hodson, and E. Kohler. Designing IP Router Software. In NSDI, 2005.
• 17: D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Mobile Computing, volume 353. 1996.
• 18: Ravi Krishnamurthy , Raghu Ramakrishnan , Oded Shmueli, A framework for testing safety and effective computability, Journal of Computer and System Sciences, v.52 n.1, p.100-124, Feb. 1996 [doi>10.1006/jcss.1996.0009]
• 19: T. V. Lakshman, T. Nandagopal, R. Ramjee, K. Sabnani, and T. Woo. The SoftRouter Architecture. In HotNets-III, 2004.
• 20: Larry L. Peterson , Bruce S. Davie, Computer Networks: A Systems Approach, 3rd Edition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 21: PlanetLab. http://www.planet-lab.org/.
• 22: R. Ramakrishnan, K. A. Ross, D. Srivastava, and S. Sudarshan. Efficient Incremental Evaluation of Queries with Aggregation. In SIGMOD, 1992.
• 23: R. Ramakrishnan and J. D. Ullman. A Survey of Research on Deductive Database Systems. Journal of Logic Programming, 23(2):125--149, 1993.
• 24: Michael Stonebraker, Inclusion of New Types in Relational Data Base Systems, Proceedings of the Second International Conference on Data Engineering, p.262-269, February 05-07, 1986
• 25: S. Sudarshan , Raghu Ramakrishnan, Aggregation and Relevance in Deductive Databases, Proceedings of the 17th International Conference on Very Large Data Bases, p.501-511, September 03-06, 1991
• 26: S. Thibault , C. Consel , G. Muller, Safe and Efficient Active Network Programming, Proceedings of the The 17th IEEE Symposium on Reliable Distributed Systems, p.135, October 20-23, 1998
• 27: Arie van Deursen , Paul Klint , Joost Visser, Domain-specific languages: an annotated bibliography, ACM SIGPLAN Notices, v.35 n.6, p.26-36, June 2000 [doi>10.1145/352029.352035]
• 28: Xiaowei Yang, NIRA: a new Internet routing architecture, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 25-27, 2003, Karlsruhe, Germany

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Design, Languages, Security

Keywords:
declarative queries, extensible routing, routing languages