| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Efficient Construction of Pipelined Multibit-Trie Router-Tables
January 2007 (vol. 56 no. 1)
pp. 32-43
Efficient algorithms to construct multibit tries suitable for pipelined router-table applications are developed. We first enhance the 1-phase algorithm of Basu and Narlikar [1], obtaining a 1-phase algorithm that is 2.5 to 3 times as fast. Next, we develop 2--phase algorithms that not only guarantee to minimize the maximum per-stage memory but also guarantee to use the least total memory subject to the former constraint. Our 2-phase algorithms not only generate better pipelined trees than those generated by the 1--phase algorithm, but they also take much less time. A node pull-up scheme that guarantees no increase in maximum per-stage memory as well as a partitioning heuristic that generates pipelined multibit tries requiring less maximum per-stage memory than required by the tries obtained using the 1-phase and 2-phase algorithms are also proposed.
[1] 32 A. Basu and G. Narlikar, “Fast Incremental Updates for Pipelined Forwarding Engines,” Proc. IEEE INFOCOM, 2003.[2] A. Bremler-Barr, Y. Afek, and S. Har-Peled, “Routing with a Clue,” Proc. ACM SIGCOMM, pp. 203-214, 1999.[3] G. Chandranmenon and G. Varghese, “Trading Packet Headers for Packet Processing,” IEEE Trans. Networking, 1996.[4] G. Cheung and S. McCanne, “Optimal Routing Table Design for IP Address Lookups under Memory Constraints,” Proc. IEEE INFOCOM, 1999.[5] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small Forwarding Tables for Fast Routing Lookups,” Proc. ACM SIGCOMM, pp. 3-14, 1997.[6] W. Doeringer, G. Karjoth, and M. Nassehi, “Routing on Longest-Matching Prefixes,” IEEE/ACM Trans. Networking, vol. 4, no. 1, pp.86-97, 1996.[7] G. Frederickson, “Optimal Algorithms for Tree Partitioning,” Proc. Second ACM-SIAM Symp. Discrete Algorithms, pp. 168-177, 1991.[8] G. Frederickson, “Optimal Parametric Search Algorithms in TreesI: Tree Partitioning,” Technical Report CS-TR-1029, Purdue Univ., West Lafayette, Ind., 1992.[9] G. Frederickson and D. Johnson, “Finding kth Paths and p-Centers by Generating and Searching Good Data Structures,” J. Algorithms, vol. 4, pp. 61-80, 1983.[10] G. Frederickson and D. Johnson, “Generalized Selection and Ranking: Sorted Matrices,” SIAM J. Computing, vol. 13, pp. 14-30, 1984.[11] E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of Data Structures in C++, p. 653. W.H. Freeman, 1995.[12] E. Horowitz, S. Sahni, and S. Rajasekaran, Computer Algorithms, p.769. W.H. Freeman, 1997.[13] K. Kim and S. Sahni, “IP Lookup by Binary Search on Length,” J.Interconnection Networks, vol. 3, pp. 105-128, 2002.[14] K. Kim and S. Sahni, “Efficient Construction of Pipelined Multibit-Trie Router-Tables,” www.cise.ufl.edu~sahni, 2004.[15] B. Lampson, V. Srinivasan, and G. Varghese, “IP Lookup Using Multi-Way and Multicolumn Search,” Proc. IEEE INFOCOM, 1998.[16] H. Lu and S. Sahni, “O(log n) Dynamic Router-Tables for Ranges,” Proc. IEEE Symp. Computers and Comm., pp. 91-96, 2003.[17] A. McAuley and P. Francis, “Fast Routing Table Lookups Using CAMs,” Proc. IEEE INFOCOM, pp. 1382-1391, 1993.[18] P. Newman, G. Minshall, and L. Huston, “IP Switching and Gigabit Routers,” IEEE Comm. Magazine, Jan. 1997.[19] S. Nilsson and G. Karlsson, “Fast Address Look-Up for Internet Routers,” IEEE Broadband Comm., 1998.[20] Ris, Routing Information Service Raw Data, http:/data.ris.ripe. net, 2003.[21] M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, “Survey and Taxonomy of IP Address Lookup Algorithms,” IEEE Network, pp.8-23, 2001.[22] S. Sahni and K. Kim, “Efficient Construction of Multibit Tries for IP Lookup,” IEEE/ACM Trans. Networking, vol. 11, no. 4, pp. 650-662, 2003.[23] S. Sahni, K. Kim, and H. Lu, “Data Structures for One-Dimensional Packet Classification Using Most-Specific-Rule Matching,” Int'l J. Foundations of Computer Science, vol. 14, no. 3, pp. 337-358, 2003.[24] S. Sahni and K. Kim, “O(log n) Dynamic Router-Table Design,” IEEE Trans. Computers, vol. 53, no. 3, pp. 351-363, Mar. 2004.[25] K. Sklower, “A Tree-Based Routing Table for Berkeley Unix,” technical report, Univ. of California, Berkeley, 1993.[26] V. Srinivasan and G. Varghese, “Faster IP Lookups Using Controlled Prefix Expansion,” ACM Trans. Computer Systems, pp.1-40, Feb. 1999.[27] S. Suri, G. Varghese, and P. Warkhede, “Multiway Range Trees: Scalable IP Lookup with Fast Updates,” Proc. GLOBECOM, 2001.[28] V. Thanvantri and S. Sahni, “Optimal Folding of Standard and Custom Cells,” ACM Trans. Design Automation of Electronic Systems, vol. 1, no. 1, pp. 123-143, 1996.[29] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable High Speed IP Routing Lookups,” Proc. ACM SIGCOMM, pp. 25-36, 1997.
Index Terms:
Packet routing, longest matching-prefix, controlled prefix expansion, multibit trie, pipelined router-table, dynamic programming.
Citation:
Kun Suk Kim, Sartaj Sahni, "Efficient Construction of Pipelined Multibit-Trie Router-Tables," IEEE Transactions on Computers, vol. 56, no. 1, pp. 32-43, Jan. 2007, doi:10.1109/TC.2007.12
