Uppslagning av Internetadresser är ett utmanande problem på grund av ökande bordsstorlekar för routing, ökad trafik, länkar med högre hastighet och övergången till 128 bitars IPv6-adresser. IP routing lookup kräver dator det bästa matchande prefixet, för vilket standardlösningar som hashing ansågs vara otillämpliga. Den bästa befintliga lösning vi känner till, BSD radix försöker, skalar dåligt som IP flyttar till 128 bit adresser, Vårt papper beskriver en ny algoritm för bästa matchning prefx med binär sökning på hash tabeller organiserade av prefix längder. Vårt schema skalar mycket bra samt adress och routing tabellstorlekar öka: oberoende av tabellens storlek, det kräver en värsta fall tid av log~ (adress bits) hash lookups. Således behövs bara 5 hash-lookups för IPv4 och 7 för IPv6. Vi introducerar också Mutating Binary Search och andra optimeringar som, för en typisk IPv4 ryggrad router med över 33.000 poster, avsevärt minska det genomsnittliga antalet hascher till mindre än 2, av vilka en hash kan förenklas till en indexerad array access. Vi förväntar oss liknande genomsnittliga fall beteende för IPv6.
Waldvogel et al anställd binär sökning på en hash tabell organiseras av prefix längd, som behöver log 2 W minnesåtkomst i värsta fall REF.
Scalable high speed IP routing lookups
{'venue': "SIGCOMM '97", 'journal': None, 'mag_field_of_study': ['Computer Science']}