Open Access Open Access  Restricted Access Subscription or Fee Access

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

P. N. Periyasamy


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.


DHT (Distributed Hash Table), Outing, Auto Configuration, Look Up, Service, Group Address

Full Text:



A. T. pat So and W. L. Chan. Intelligent building Systems. Kluwer Academic.

C. Hedrick. RFC1058 routing information protocol. Jun. 1988.

Gursharan S. Sidhu, Richard F. Andrews, Alan B. Oppenheimer. Inside AppleTalk. Addison Wesley, 1989.

JIS. X5003 open systems interconnection {basic Reference model. 1994.

J.Moy. RFC1583 ospf version 2. Mar 1994.

G. Malkin. RFC1721 rip version 2 protocol analysis. Nov.

Ratnasamy, S., Francis, P., Handley, M.,Karp, R., Schenker, S.: A scalable content addressable network. In: SIGCOMM ’01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, New York, NY, USA, ACM Press (2001) 161–172.

R. E. Tarjan. Data structures and network algorithms. pages 85,96, 1993.

Rowstron, A.I.T., Druschel, P.: Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In: Middleware. (2001) 329–350.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.