Hardware-based IP routing using partitioned lookup table

ABSTRACT

We present a search algorithm implementable by a parallel architecture based on partitioned forwarding table. This scheme effectively reduces the complexity of finding "the longest prefix match" problem to "a prefix match" problem. The main feature of this algorithm is twofold. First, it advocates intelligent partitioning of the forwarding table to enhance and parallelize the lookup operation. Second, it takes advantage of ternary CAM to achieve low lookup time. The resulting architecture has better throughput and much better update time than the traditional TCAM. Our experimental results show that such features can significantly elevate the flexibility and scalability of the next generation packet processing devices.

REFERENCES

• 1: Alberto Leon-Garcia , Indra Widjaja, Communication Networks: Fundamental Concepts and Key Architectures, McGraw-Hill School Education Group, 1999
• 2: {2} F. Baker, "Requirements for IPv4 Routers," IETF, RFC 1812, htp://www.ietf.org/rfc/rfc1812.txt, Jun. 1995.
• 3: Pankaj Gupta , Nicholas W. Mckeown, Algorithms for routing lookups and packet classification, 2000
• 4: {4} V. Fuller, T. Li, J. Yu, and K. Varadhan, "Classless Inter-Domain Routing (CIDR): An Address Assignment and Aggregation Strategy," IETF, RFC 1519, http://www.ietf.org/rfc/rfc1519.txt, 1993.
• 5: Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
• 6: {6} M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, "Survey and taxonomy of IP address lookup algorithms," IEEE Network Mag., vol. 15, no. 2, pp. 8-23, Mar.-Apr. 2001.
• 7: {7} H. Tzeng and T. Przygienda, "On fast address lookup algorithms," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1067-1082, Jun. 1999.
• 8: Willibald Doeringer , Günter Karjoth , Mehdi Nassehi, Routing on longest-matching prefixes, IEEE/ACM Transactions on Networking (TON), v.4 n.1, p.86-97, Feb. 1996 [doi>10.1109/90.503764]
• 9: V. Srinivasan , G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems (TOCS), v.17 n.1, p.1-40, Feb. 1999 [doi>10.1145/296502.296503]
• 10: {10} V. Srinivasan and G. Varghese, "IP address lookups using LC-tries," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1083-1092, Jun. 1999.
• 11: Marcel Waldvogel , George Varghese , Jon Turner , Bernhard Plattner, Scalable high speed IP routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.25-36, September 14-18, 1997, Cannes, France
• 12: Butler Lampson , Venkatachary Srinivasan , George Varghese, IP lookups using multiway and multicolumn search, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.324-334, June 1999 [doi>10.1109/90.779199]
• 13: {13} T. Pei and C. Zukowski, "Putting routing tables in silicon," IEEE Network Mag., vol. 6, no. 1, pp. 42-50, Jan. 1992.
• 14: Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.3-14, September 14-18, 1997, Cannes, France
• 15: {15} P. Gupta, S. Lin, and N. McKeown, "Routing lookups in hardware at memory access speeds," in Proc. IEEE INFOCOM, Apr. 1998, pp. 1240-1247.
• 16: {16} N. Huang, S. Zhao, J. Pan, and C. Su, "A fast IP routing lookup scheme for gigabit switching routers," in Proc. IEEE INFOCOM, vol. 3, 1999, pp. 1429-1436.
• 17: {17} A. McAuley and P. Francis, "Fast routing table lookup using CAMs," in Proc. IEEE INFOCOM, 1993, pp. 1382-1391.
• 18: {18} V. Srinivasan, B. Nataraj, and S. Khanna, "Method for longest prefix matching in a content addressable memory," U.S. Patent 6,237,061, May 22, 2001.
• 19: {19} R. Kempke and A. McAuley, "Ternary CAM memory architecture and methodology," U.S. Patent 5,841,874, Nov. 24, 1998.
• 20: {20} T. Hayashi and T. Miyazaki, "High speed table lookup engine for IPv6 longest prefix match," in Proc. IEEE GLOBECOM, Dec. 1999, pp. 1576-1581.
• 21: Devavrat Shah , Pankaj Gupta, Fast Updating Algorithms for TCAMs, IEEE Micro, v.21 n.1, p.36-47, January 2001 [doi>10.1109/40.903060]
• 22: Huan Liu, Routing Table Compaction in Ternary CAM, IEEE Micro, v.22 n.1, p.58-64, January 2002 [doi>10.1109/40.988690]
• 23: {23} M. Akhbarizadeh and M. Nourani, "An IP packet forwarding technique based on partitioned lookup table," in Proc. IEEE Int. Conf. Communications (ICC'02), May 2002, pp. 2263-2267.
• 24: {24} M. Akhbarizadeh and M. Nourani, "Reconfigurable memory architecture for scalable IP forwarding engines," in Int. Conf. Computer Communications and Networks (ICCCN'02), Oct. 2002, pp. 432-437.
• 25: {25} N. Yazdani and P. Min, "Fast and scalable schemes for the IP address lookup problem," in Proc. High Performance Switching and Routing Conf., 2000, pp. 83-92.
• 26: E. Stewart Lee, Algorithms and data structures in computer engineering, Jones and Bartlett Publishers, Inc., 1992
• 27: {27} "The Internet Performance Measurement and Analysis Project," Merit Network, Inc., http://www.merit.edu, 2001.
• 28: {28} M. Akhbarizadeh, "Algorithms for Fast Hardware Based IP Route Lookup," Master's Thesis, Dept. of Electrical Eng., Univ. of Texas at Dallas, Dec. 2002.
• 29: Kenneth J. Schultz, Content-addressable memory core cells: a survey, Integration, the VLSI Journal, v.23 n.2, p.171-188, Nov. 1997 [doi>10.1016/S0167-9260(97)00021-7]
• 30: {30} Synopsys Design Analyzer, User Manuals for SYNOPSYS Toolset Version 2002.05, Synopsys, Inc., 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
IP address, content addressable memory, forwarding table, internet protocol, longest prefix matching, partitioned forwarding