Delarative Routing

ABSTRACT

This term paper discusses "Declarative routing- Extensible routing with declarative queries" by Boon Thau Loo, Joseph M. Hellerstein, Ion Stoica, Raghu Ramakrishnan.

At the end of our analysis we intend to be able to

- Understand the Declarative Routing

- Relationship between Datalog and KBS

- Understanding the fundamentals of the language components

The paper explores a new point in design space of Active Networks and hard-coded protocols aiming to strike a better balance between extensibility and robustness of the routing infrastructure. The authors propose the idea of 'declarative routing' which expresses routing protocols using a database query language.

MOTIVATION

The motivation behind devising this solution is lack of extensibility and flexibility in today's Internet routing. Though the internet protocols are considerably robust and efficient, they are hard to add, improve or update. Also designing of routing protocols is a very tedious and difficult process especially when it is distributed.

RELATED WORK

Prior to the authors' solution, several solutions have been proposed to address the lack of flexibility and extensibility in Internet Routing.

 Overlay Networks allow third parties to replace Internet routing with new implementations of routing functionality that run at the application layer. But

using overlay network method just shifts problem from network to application.

Overlay routing protocol still requires a complete protocol design and implementation and requires access to overlay nodes

 Active Networks: allows one to deploy new routing functionality without need o have direct access to routers but have problems with performance, security and reliability of infrastructure.

ROUTING BASICS [2]

Before we get into the details of the proposed solution, lets first understand the basics of routing and understand the problem space. Routing refers to selecting paths in a computer network along which to send data. Routing directs forwarding, the passing of logically addressed packets from their source toward their ultimate destination through intermediary nodes (called routers). The routing process usually directs forwarding on the basis of routing tables within the routers, which maintain a record of the best routes to various network destinations. Thus the construction of routing tables becomes very important for efficient routing. Dynamic routing attempts to solve this problem by constructing routing tables automatically, based on information carried by routing protocols, and allowing the network to act nearly autonomously in avoiding network failures and blockages.

Dynamic routing dominates the Internet. However, the configuration of the routing protocols often requires a skilled touch; one should not suppose that networking technology has developed to the point of the complete automation of routing.

Small networks may involve hand-configured routing tables. Large networks involve complex topologies and may change constantly, making the manual construction of routing tables very problematic. Nevertheless, most of the public switched telephone network (PSTN) uses pre-computed routing tables, with fallback routes if the most direct route becomes blocked; see routing in the PSTN.

Routing protocols facilitate the exchange of routing information between networks, allowing routers to build routing tables dynamically. Traditional IP routing stays simple because it uses next-hop routing where the router only needs to consider where it sends the packet, and does not need to consider the subsequent path of the packet on the remaining hops.

Although this dynamic routing can become very complex, it makes the Internet very flexible, and has allowed it to grow in size by more than eight orders of magnitude over the years since adopting IP.

PROPOSED SOLUTION

The key idea used by the authors is to use recursive query language for expressing routing protocols. Datalog which is a declarative recursive query language and is well-researched in the database community and well-suited for querying properties of graphs is used to implement the routing protocol. Declarative routing can be viewed as a restrictive instantiation of Active networks for control plane to balance performance, security and reliability concerns. The authors show that their query language fits for routing and can express a variety of routing protocols in a compact and clean fashion. They evaluate the solution against security in terms of its computational expressive power and language design

They validate the solution via simulation and deployment to prove the amenability to query optimizations and sustainability to long -lived routes under network congestions.

Using declarative routing is application of database techniques to networking domain as it is based on recursive query languages studied in deductive database literature are natural fit for expressing routing protocols. Deductive database query language focuses on identifying recursive relationships among nodes of a graph and well suited for describing paths among the nodes.

ADVANTAGES [1]

Following are the benefits provided by the solution:

 Expressiveness: Compact and clean representation of protocols

 Safety: Datalog has desirable safety properties on termination

 Efficiency: No fundamental overhead when executing standard protocols.

USAGE and EVOLUTION

An incremental view of usage of declarative routing is by ISP administrators to

Run different protocols for different nodes by issuing a query to the network and modify existing protocols in routers to easily implement different routing policies. Simplicity and safety features of declarative routing work well in a managed scenario.

Another extreme view is routing through individual end-hosts through explicit request of routes to set up customized routes for different quality-of-service and policy requirements of applications. The authors deal with the extreme view to explore the limits of their design.

The

...