An IP packet forwarding technique based on a new structure of lookup table

被引：0

作者：

Computers and Systems Dept., Faculty of Engineering, Mansoura University, Mansoura, Egypt ^{[1
]}

不详 ^{[2
]}

不详 ^{[3
]}

不详 ^{[4
]}

不详 ^{[5
]}

机构：

[1] Computers and Systems Dept., Faculty of Engineering, Mansoura University, Mansoura

[2] Deptartment of Computer Science, University of Connecticut, Storrs

[3] University of Mansoura, Faculty of Computer Science

[4] Computer and Control Department, Mansoura University

[5] Computer Engineering and Systems Department, Faculty of Engineering, Mansoura University, Mansoura

来源：

Int J Comput Appl | 2006年 / 2卷 / 112-121期

关键词：

Lookup time; LPM; Packet forwarding; RapidBase; Routing algorithm; Routing table;

D O I：

10.1080/1206212X.2006.11441794

中图分类号：

学科分类号：

摘要：

In computer networks nowadays, high-speed routers are compulsory to deliver the incoming packet to its destination. There are two parameters that exist in all lookup techniques that directly affect performance results: data structure size and number of lookup table accesses. With these remarks in mind, the specific goals of this paper are: (i) Design a data structure for storing an IP lookup table that enhances the lookup process, (ii) Produce an IP lookup algorithm that has a bounded worst-case number of accesses lower than contemporary techniques, and (iii) Improve updating and deletion operations that do not create a bottleneck to efficient forwarding. This paper investigates a suitable data structure of the routing table in order to minimize the total routing time. The investigated structure of the routing table is based on RapidBase technique. It contains all the information necessary to forward an IP data packet toward its destination. The properties of the created routing table facilitate searching for the best matching prefix quicker than when using the current routing table where packets do not have to be queued before lookup. Additionally, the proposed algorithm's effectiveness is deliberated via simulation. A comparative study with recently published algorithms shows that our proposed scheme has a great impact on shortening the route lookup and update operations. For more enhancements, combinations of the proposed algorithm with the most popular algorithms are also studied.

引用

页码：112 / 121

页数：9

共 20 条

[1]

Tzeng H., Przygienda T., On fast address lookup algorithms, IEEE Journal on Selected Areas in Communications, 17, 6, pp. 1067-1082, (1999)

[2]

Doeringer W., Karjoth G., Nassehi M., Routing on longest matching prefixes, IEEE/ACM Transactions on Networking, 4, 1, pp. 86-97, (1996)

[3]

Gavoille C., Routing in distributed networks: Overview and open problems, ACM SIGACT News - Distributed Computing Column, 32, 1, pp. 36-52, (2001)

[4]

Ruiz-Sanchez M., Biersack E., Dabbous W., Survey and taxonomy of IP address lookup algorithms, IEEE Network, 15, 2, pp. 8-23, (2001)

[5]

Cheung G., McCanne S., Optimal routing table design for IP address lookups under memory constraints, Proc. IEEE INFOCOM '99, pp. 1437-1444, (1999)

[6]

Buchsbaum L., Fowler G.S., Krishnamurthy B., Vo K., Wang J., Fast prefix matching of bounded strings, 5th Workshop on Algorithm Engineering and Experiments (ALENEX03), pp. 128-140, (2003)

[7]

Leon-Garcia, Widjaja I., Communication Networks, Fundamental Concepts and Key Structures, (2000)

[8]

Degermark M., Brodnik A., Carlsson S., Pink S., Small forwarding tables for fast routing lookups, Proc. of ACM SIGCOMM'97, pp. 3-14, (1997)

[9]

Kim K., Sahni S., IP lookup by binary search on prefix length, Journal of Interconnection Networks, 3, 3-4, pp. 105-128, (2002)

[10]

Lampson B., Srinivasan V., Varghese G., IP lookups using multiway and multicolumn search, Proc. INFOCOM, 3, pp. 1248-1256, (1998)

← 1 2 →