Abstract
Ternary content-addressable memory has been widely used to perform fast routing lookups. It is able to accomplish the best matching prefix problem in O(1) time without considering the number of prefixes and its lengths. As compared to the software-based solutions, the Ternary content-addressable memory can offer sustained throughput and simple system architecture. It is attractive for IPv6 routing lookup. However, it also comes with several shortcomings, such as the limited number of entries, expansive cost and power consumption. Accordingly, we propose an efficient algorithm to reduce the required size of Ternary content-addressable memory. The proposed scheme can eliminate 98 percentage of Ternary content-addressable memory entries by adding tiny DRAM. We also address related issues in supporting IPv6 anycasting.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Rekhter, Y., Li, T.: An Architecture for IP Address Allocation with CIDR. RFC 1518 (September 1993)
Degermark, M., Brodnik, A., Carlsson, S., Pink, S.: Small Forwarding Tables for Fast Routing Lookups. In: Proc. ACM SIGCOMM 1997, Cannes, France, September 1997, pp. 3–14 (1997)
Gupta, P., Lin, S., McKeown, N.: Routing Lookups in Hardware at Memory Access Speeds. In: Proc. IEEE INFOCOM 1998, San Francisco, USA (March 1998)
Huang, N.F., Zhao, S.M., Pan, J.Y.: A Fast IP Routing Lookup Scheme for Gigabit Switch Routers. In: Proc. IEEE INFOCOM 1999, New York, USA (March 1999)
Srinivasan, V., Varghese, G.: Fast IP lookups using controlled prefix expansion. ACM Trans. On Computers 17, 1–40 (1999)
Nilsson, S., Karlsson, G.: IP-Address Lookup Using LC-Tries. IEEE JSAC 17(6), 1083-1029 (1999)
Waldvogel, M., Vargnese, G., Turner, J., Plattner, B.: Scalable High Speed IP Routing Lookups. In: Proc. ACM SIGCOMM 1997, Cannes, France, September 1997, pp. 25–36 (1997)
Lampson, B., Srinivasan, V., Varghese, G.: IP Lookups Using Multiway and Multicolumn Search. IEEE/ACM Trans. On Networking 7(4), 324–334 (1999)
Shah, D., Gupta, P.: Fast updating Algorithms for TCAMs. IEEE Micro Mag. 21(1), 36–47 (2001)
Merit Networks, Inc. Internet Performance Measurement and Analysis (IPMA) Statistics and Daily Reports, See http://www.merit.edu/ipma/routingtable/
NLANR Project, See http://moat.nlanr.net/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chan, CT., Wang, PC., Hu, SC., Lee, CL., Chen, RC. (2003). Scalable IP Routing Lookup in Next Generation Network. In: Kahng, HK. (eds) Information Networking. ICOIN 2003. Lecture Notes in Computer Science, vol 2662. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45235-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-45235-5_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40827-7
Online ISBN: 978-3-540-45235-5
eBook Packages: Springer Book Archive