{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:53Z","timestamp":1750308773712,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>IP address lookup is a critical operation for high-bandwidth routers in packet-switching networks, such as Internet. The lookup is a nontrivial operation, since it requires searching for the longest prefix, among those stored in a (large) given table, matching the IP address. Ever increasing routing table size, traffic volume, and links speed demand new and more efficient algorithms. Moreover, the imminent move to IPv6 128-bit addresses will soon require a rethinking of previous technical choices. This article describes a the new data structure for solving the IP table lookup problem christened the adaptive stratified tree (AST). The proposed solution is based on casting the problem in geometric terms and on repeated application of efficient local geometric optimization routines. Experiments with this approach have shown that in terms of storage, query time, and update time the AST is at a par with state of the art algorithms based on data compression or string manipulations (and often it is better on some of the measured quantities).<\/jats:p>","DOI":"10.1145\/1227161.1278376","type":"journal-article","created":{"date-parts":[[2008,10,8]],"date-time":"2008-10-08T13:57:58Z","timestamp":1223474278000},"page":"1-28","source":"Crossref","is-referenced-by-count":0,"title":["Efficient IP table lookup via adaptive stratified trees with selective reconstructions"],"prefix":"10.1145","volume":"12","author":[{"given":"Marco","family":"Pellegrini","sequence":"first","affiliation":[{"name":"Istituto di Informatica e Telematica, Pisa, Italy"}]},{"given":"Giordano","family":"Fusco","sequence":"additional","affiliation":[{"name":"Istituto di Informatica e Telematica, Pisa, Italy"}]}],"member":"320","published-online":{"date-parts":[[2008,6,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796252"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875514"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301323"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/179812.179818"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Broder A. Z. and Mitzenmacher M. 2001a. Using multiple hash functions to improve IP lookups. In INFOCOM. 1454--1463.","DOI":"10.1109\/INFCOM.2001.916641"},{"key":"e_1_2_1_6_1","first-page":"1454","article-title":"Using multiple hash functions to improve IP lookups","volume":"3","author":"Broder A. Z.","year":"2001","unstructured":"Broder, A. Z. and Mitzenmacher, M. 2001b. Using multiple hash functions to improve IP lookups. In IEEE Computer and Communications Societies (INFOCOM). Vol. 3. 1454--1463.","journal-title":"IEEE Computer and Communications Societies (INFOCOM)."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of Alenex","author":"Buchsbaum A. L.","year":"2003","unstructured":"Buchsbaum, A. L., Fowler, G. S., Krishnamurthy, B., Vo, K.-P., and Wang, J. 2003. Fast prefix matching of bounded strings. In Proceedings of Alenex 2003."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Cheung G. and McCanne S. 1999. Optimal routing table design for IP address lookups under memory constraints. In INFOCOM (3). 1437--1444.","DOI":"10.1109\/INFCOM.1999.752164"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/647909.740302"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Degermark M. Brodnik A. Carlsson S. and Pink S. 1997. Small forwarding tables for fast routing lookups. In SIGCOMM. 3--14. 10.1145\/263105.263133","DOI":"10.1145\/263105.263133"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863979"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/997150.997160"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90002-X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365791"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/646679.702311"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of INFOCOM","volume":"3","author":"Feldmann A.","unstructured":"Feldmann, A. and Muthukrishnan, S. 2000. Tradeoffs for packet classification. In Proceedings of INFOCOM, Vol. 3. IEEE, Los Alamitos. 1193--1202."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies (March 13--17)","volume":"1","author":"Geraci F.","unstructured":"Geraci, F., Pellegrini, M., Pisati, P., and Rizzo, L. 2005. Packet classification via improved space decomposition techniques. In Proceedings of INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies (March 13--17). Vol. 1. 304--312."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Gupta P. Prabhakar B. and Boyd S. P. 2000. Near optimal routing lookups with bounded worst case performance. In INFOCOM (3). 1184--1192.","DOI":"10.1109\/INFCOM.2000.832490"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1090191.1080116"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","unstructured":"Ioannidis I. Grama A. and Atallah M. J. 2005. Adaptive data structures for IP lookups. ACM Journal of Experimental Algorithms 10. 10.1145\/1064546.1064548","DOI":"10.1145\/1064546.1064548"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786986"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780635"},{"key":"e_1_2_1_23_1","unstructured":"Knuth D. E. 1973. The Art of Computer Programming Vol. 3---Sorting and Searching. Addison-Wesley Reading MA."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.779199"},{"volume-title":"IEEE Workshop on High Performance Switching and Routing","author":"Liu Y.-C.","key":"e_1_2_1_25_1","unstructured":"Liu, Y.-C. and Lea, C.-T. 2001. Fast IP table lookup and memory reduction. In IEEE Workshop on High Performance Switching and Routing. Dallas, TX. 228--232."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1126253.1126619"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.81"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.104"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.83"},{"volume-title":"Hot interconnects tutorial slides","author":"McKeown N.","key":"e_1_2_1_30_1","unstructured":"McKeown, N. 1999. Hot interconnects tutorial slides. Stanford University, available at http:\/\/klamath.stanford.edu\/talks\/."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321481"},{"volume-title":"Computational Geometry, an Introduction through Randomized Algorithms","author":"Mulmuley K.","key":"e_1_2_1_32_1","unstructured":"Mulmuley, K. 1993. Computational Geometry, an Introduction through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.772439"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132551"},{"key":"e_1_2_1_35_1","volume-title":"Tech. Rep. TR IMC B4-01-13, Istituto di Matematica Computazionale del CNR, Area della Ricerca, Pisa, Italy. November.","author":"Pellegrini M.","year":"2001","unstructured":"Pellegrini, M. and Vecchiocattivi, G. 2001. Empirical study of search trees for ip addressing look up. Tech. Rep. TR IMC B4-01-13, Istituto di Matematica Computazionale del CNR, Area della Ricerca, Pisa, Italy. November. Available at www.iit.cnr.it\/staff\/marco.pellegrini."},{"key":"e_1_2_1_36_1","volume-title":"Tech. Rep. TR IIT 22\/2002, Istituto di Informatica e Telematica del CNR (IIT-CNR), Pisa, Italy (Nov.)","author":"Pellegrini M.","year":"2002","unstructured":"Pellegrini, M., Fusco, G., and Vecchiocattivi, G. 2002. Adaptive stratified search trees for ip table lookup. Tech. Rep. TR IIT 22\/2002, Istituto di Informatica e Telematica del CNR (IIT-CNR), Pisa, Italy (Nov.)"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_38_1","unstructured":"Raman R. 1995. Improved data structures for predecessor queries in integer sets."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/874065.875755"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/646465.691552"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.815288"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054104002625"},{"volume-title":"Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM-01)","author":"Sharp J.","key":"e_1_2_1_43_1","unstructured":"Sharp, J., Ergun, F., Mittra, S., Sahinalp, C., and Sinha, R. 2001. A dynamic lookup scheme for bursty access patterns. In Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM-01). IEEE Computer Society, Los Alamitos, CA. 1444--1453."},{"key":"e_1_2_1_44_1","volume-title":"USENIX","author":"Sklower K.","year":"1991","unstructured":"Sklower, K. 1991. A tree-based packet routing table for berkeley unix. In USENIX Winter 1991. 93--104."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","unstructured":"Srinivasan V. and Varghese G. 1999. Fast address lookups using controlled prefix expansion. ACM Transactions on Computer Systems 1--40. 10.1145\/296502.296503","DOI":"10.1145\/296502.296503"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Sun X. Sahni S. K. and Zhao Y. Q. 2004. Fast update algorithm for IP forwarding table using independent sets. In High Speed Networks and Multimedia Communications (HSNMC 2004) Z. Mammeri and P. Lorenz Eds. Lecture Notes in Computer Science Toulouse France. vol. 3079. Springer New York. 324--335.","DOI":"10.1007\/978-3-540-25969-5_29"},{"key":"e_1_2_1_47_1","first-page":"1641","article-title":"High-performance longest prefix matching supporting high-speed incremental updates and guaranteed compression","volume":"3","author":"Sundstr\u00f6m M.","year":"2005","unstructured":"Sundstr\u00f6m, M. and Larzon, L.-\u00c5. 2005. High-performance longest prefix matching supporting high-speed incremental updates and guaranteed compression. In IEEE Computer and Communications Societies (INFOCOM). Vol. 3. 1641--1652.","journal-title":"IEEE Computer and Communications Societies (INFOCOM)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90064-9"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2003.810507"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780636"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683268"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","unstructured":"Waldvogel M. Varghese G. Turner J. and Plattner B. 1997. Scalable high speed IP routing lookups. In SIGCOMM. 25--36. 10.1145\/263105.263136","DOI":"10.1145\/263105.263136"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2003.09.004"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90075-3"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90020-5"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214071"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797322425"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/850923.851470"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1278376","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1278376","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1278376"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":59,"alternative-id":["10.1145\/1227161.1278376"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1278376","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}