Abstract-Internet Protocol (IP) adressuppslagning är en central bearbetningsfunktion för Internet routers. Medan ett brett utbud av lösningar på detta problem har utarbetats, mycket få samtidigt uppnå höga uppslagshastigheter, bra uppdateringsprestanda, hög minneseffektivitet och låga hårdvarukostnader. Högpresterande lösningar med innehållstillgängliga minnesenheter är en populär men dyr lösning, särskilt när den appliceras på stora databaser. Vi presenterar en effektiv maskinvaruimplementering av en tidigare opublicerad IP-adresslookuparkitektur, uppfunnen av Eatherton och Dittia. Vår experimentella implementering använder en enda råvara synkron slumpmässig åtkomst minneschip och mindre än 10% av de logiska resurserna för en kommersiell konfigurerbar logik enhet, som arbetar på 100 MHz. Med dessa ganska blygsamma resurser, kan det utföra över 9 miljoner lookups / s, samtidigt behandla tusentals uppdateringar / s, på databaser med över 100000 poster. Uppslagningsstrukturen kräver 6,3 byte per adressprefix: mindre än hälften av det som krävs enligt andra metoder. Arkitekturen gör det möjligt att skala upp prestandan med hjälp av parallell snabb IP-lookup (FIPL) motorer, som kopplar upp åtkomsten till ett gemensamt minne gränssnitt. Denna arkitektur gör det möjligt för prestanda att skala upp direkt med tillgänglig minnesbandbredd. Vi beskriver Tree Bitmap algoritmen, vårt genomförande av den i en dynamiskt extensibel gigabit router utvecklas vid Washington University i Saint Louis, och resultaten av prestanda experiment utformade för att bedöma dess prestanda under realistiska driftsförhållanden. Index Terms-Field-programmerbar grind array (FPGA), Internet router, IP-lookup, slumpmässig åtkomst minne (RAM), omkonfigurerbar hårdvara.
En implementering av Tree Bitmap algoritm, kallad Fast IP Lookup (FIPL) REF, visar att ett lagringskrav på cirka 6,3 byte per prefix och prestanda på över en miljon uppslagningar per FIPL motor kan uppnås.
Scalable IP Lookup for Internet Routers
{'venue': 'IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS', 'journal': None, 'mag_field_of_study': ['Computer Science']}