An Efficient DHT Approach to Design a New Network Layer Routing Algorithm

Abstract

Routing algorithms such as Distance Vector andLinkStateshave the routing table size Ω(n), where n is the number of destination identifiers, thus providing only limited scalability for large networks when n is high. As the distributed hash table (DHT) techniques are extraordinarily scalable with n, our work aims at adapting a DHT approach to the design of a network layer routing algorithm so that the average routing table size can be significantly reduced to O (log n) without losing much routing efficiency. Nonetheless, this scheme requires a major breakthrough to address some fundamental challenges. Specifically, unlike a DHT, a network-layer routing algorithm must (1) exchange its control messages without an underlying network,(2) handle link insertion/deletion and link-cost updates, and (3) provide routing efficiency. Thus, we are motivated to propose a new network-layer routing algorithm, using DHT-like multilevel routing without an underlying network, aiming at exchanging its control messages only via physical links and to be self-configurable in response to linkage updates. To do this i.e. to achieve scalability and to overcome the problems of configuration we have proposed a network layer protocol  equipped with a function that automatically configures routing addresses and routing tables for a large scale network system made up of multiple connected physical networks. The goals of the work presented in this paper are to enable adding and deleting physical networks during practical use and designing the protocol in such a way that the auto-configuration is finished within a few minutes.