Internet (IP) adress uppslagning är en stor flaskhals i högpresterande routrar. IP-adress uppslagning är utmanande eftersom det kräver en längsta matchande prefix uppslagning. Det förvärras genom att öka routing tabellstorlekar, ökad trafik, länkar med högre hastighet, och övergången till 128-bitars IPv6-adresser. Vi beskriver hur IP-lookups och uppdateringar kan göras snabbare med hjälp av en uppsättning transformationstekniker. Vår huvudteknik, kontrollerad prefixexpansion, omvandlar en uppsättning prefix till ett likvärdigt set med färre prefixlängder. Dessutom använder vi optimeringstekniker baserade på dynamisk programmering och lokala omvandlingar av datastrukturer för att förbättra cachebeteendet. När våra tekniker tillämpas på trie-sökning ger de en rad algoritmer (expanderade försök) vars prestanda kan ställas in. Till exempel, med hjälp av en processor med 1 MB L2 cache, sök i MaeEast databasen som innehåller 38000 prefix kan göras i 3 L2 cache åtkomster. På en 300MHz Pentium II som tar 4 cykler för att komma åt det första ordet av L2 cachline, har denna algoritm en värsta fall söktid på 180 nsec., en värsta fall infoga / ta bort tid på 2,5 msec., och en genomsnittlig infoga / ta bort tid på 4 usec. Expanderade försök ger snabbare sökning och snabbare infoga / ta bort tider än tidigare uppslagningsalgoritmer. När våra tekniker tillämpas på Binary Search on Levels förbättrar de värsta söktiderna med nästan en faktor på 2 (med dubbelt så mycket lagring) för MaeEast-databasen. Vår strategi för algoritmdesign bygger på mätningar med hjälp av VTune-verktyget på en Pentium för att få dynamiska klockcykelräkningar. Våra tekniker gäller även liknande problem med adresssökning i andra nätverksprotokoll.
Srinivasan och Varghese presenterar en modifierad trie datastruktur för att utföra IP-adress uppslagning REF.
Fast address lookups using controlled prefix expansion
{'venue': 'TOCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}