Open Access Open Access  Restricted Access Subscription or Fee Access

An Efficient Dynamic Cluster Head Table Design for Time Minimization using BVLI‟s Data Structures

A. Daison Raj, M. BalaAnand, C. Leena

Abstract


IP lookup affects the speed of an incoming packet and the time required to determine which output port the packet should be sent to; hence, it plays an important role in the design of cluster-tables. In this paper, we propose a new data structure, called a BVLI – Binary Value Level based Index Data Structure for use in designing dynamic cluster-tables for reduce the time minimization process for searching the availability of next cluster head in the cluster table and retrieve the particular cluster network information quickly during the communication among the systems in the wireless networks. One key feature of our data structure is that each node can store only one Level in the cluster head table, which reduces the number of memory accesses. When performing lookup, the structure can search more prefixes in one node and may find the longest matching prefix in an internal node rather than on a leaf. Moreover, when updating the cluster head-table, it does not need to reconstruct the table. As a by-product, the proposed data structure minimizes the time required for dynamic cluster head table operations, including lookup, insertion, deletion, and also reduces the number of memory accesses. We report the results of experiments conducted to compare the proposed data structure with other structures using MATLAB.

Keywords


BVLI, Cluster, lookup, Unique ID.

Full Text:

PDF

References


BGP Table, http://bgp.potaroo.net/, 2010.

Basu A. And Narlikar G.,(June 2005) “Fast Incremental Updates for Pipelined Forwarding Engines,” IEEE/ACM Trans. Networking, vol. 13, no. 3, pp. 690-703.

Berger M. (Sep. 2003), “IP Lookup with Low Memory Requirement and Fast Update,” Proc. IEEE High Performance Switching and Routing, pp. 287-291.

Carla F. Chiasserini, Michele Garetto, Michela Meo (MAY 2000), “Improving TCP over Wireless by Selectively Protecting Packet Transmissions.

Chang Y.K., “Simple and Fast IP Lookups Using Binomial Spanning Trees(Mar. 2005),” Computer Comm., vol. 28, no. 5, pp. 529-539.

Chang Y.K. and Lin Y.C.( 30 April 2007), “Dynamic Segment Trees for Ranges and Prefixes,” IEEE Trans. Computers, vol. 56, no. 6, pp. 769-784.

Chulho Won, Ben Lee, Kyoung Park and Myung-Joon Kim(December 2008), “Eager Data Transfer Mechanism for Reducing Communication Latency in User-Level Network Protocol”.

Doeringer W., Kernot G., and Nassehi M. (02 Aug. 2006), “Routing on Longest- Matching Prefixes,” IEEE/ACM Trans. Networking, vol. 4, no. 1, pp. 86 97.

EIRakabawy S.M., and Lindeman C (2 Apr 2007), “Peer-to-peer file transfer in wireless mesh networks”.

Huang N.F. and Zhao S.M.( 02 Aug. 2006), “A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers,” IEEE Selected Areas in Comm., vol. 17, no. 6, pp. 1093-1104.

Jiang W., Wang Q., and Prasanna V.( 02 May 2008), “Beyond TCAMs: An SRAMBased Parallel Multi-Pipeline Architecture for Terabit IP Lookup,” Proc. IEEE INFOCOM, pp. 1786-1794.

Lu H., Kim K.S., and Sahni S. (Mar. 2005), “Prefix and Interval-Partitioned Dynamic IP Router-Tables,” IEEE Trans. Computers, vol. 54, no. 5, pp. 545-557.

Mun J.H., Lim H., and Yim C.( 19 June 2006), “Binary Search on Prefix Lengths for IP Address Lookup,” IEEE Comm. Letters, vol. 10,pp. 492-494.

Wentao Zhang, Qian Wu , Wang Yang and Hewu Li (Aug 2010), “Reliable Multipath Transfer Scheduling Algorithm Research and Prototype Implementation”.

G. Apostolopoulos, V. Peris, P. Pradhan, and D. Sara, “Securing Electronic Commerce: Reducing the SSL Overhead,” IEEE Network, 2000.

S. Bohacek, J.P. Hespanha, K. Obraczka, J. Lee, and C. Lim,“ Enhancing Security via Stochastic Routing,” Proc. 11th Int‟l Conf

Computer Comm. and Networks (ICCCN), 2002.

D. Collins, Carrier Grade Voice over IP. McGraw-Hill, 2003.

T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms. MIT Press, 1990.

P. Erdo¨s and A. Re´nyi, “On Random Graphs,” Publications Math.Debrecen, vol. 6, 1959.

M. Faloutsos, P. Faloutsos, and C. Faloutsos, “On Power-Law Relationships of the Internet Topology,” Proc. ACM SIGCOMM‟99, pp. 251-262, 1999.

Free S/WAN, http://www.freeswan.org, 2008.


Refbacks

  • There are currently no refbacks.


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