Abstract-I detta dokument, introducerar vi ett nytt IP-lookup system med värsta fall sökning och uppdateringstid för O(log n), där n är antalet prefix i vidarebefordran tabellen. Vårt system bygger på en ny datastruktur, ett flervägsträd. Även om befintliga uppslagningssystem är bra för IPv4 kommer de inte så bra i fråga om både uppslagningshastighet och uppdateringskostnader när adresser växer längre som i IPv6-förslaget. Således är vårt uppslagningssystem det första uppslagningssystemet för att erbjuda snabba uppslag och uppdateringar för IPv6 samtidigt som det förblir konkurrenskraftigt för IPv4. Möjligheten till ett globalt Internet med adresserbara apparater har motiverat ett förslag att gå från det äldre Internet Ipv4 routing protokollet med 32 bit adresser till ett nytt protokoll, IPv6 med 128 bit adresser. Även om det finns osäkerhet om IPv6, kommer alla framtida Internet-protokoll att kräva minst 64 bitar, och möjligen även 128 bitars adresser som i IPv6. Således använder vi helt enkelt IPv6 och 128 bitar för att hänvisa till nästa generations IP-protokoll och dess adresslängd. Vårt dokument handlar om adresssökning, en viktig flaskhals för internetroutrar. Vårt papper beskriver det första IP-lookup-schemat som skalar sig och adresslängderna ökar som i IPv6, samtidigt som det ger snabba söktider och snabba uppdateringstider. Det finns fyra krav på ett bra uppslagningsschema: söktid, minne, skalbarhet och uppdateringstid. Söktid är viktigt för uppslagning att inte vara en flaskhals. System som är minneseffektiva leder till snabbare sökning eftersom kompakta datastrukturer passar in i snabbt men dyrt statiskt RAM-minne. Skalbarhet i både antal prefix och adresslängd är viktigt eftersom prefix-databaser växer, och en övergång till IPv6 kommer att öka adressprefixlängderna. Slutligen är system med snabb uppdateringstid önskvärda eftersom i) instabilitet i ryggradsprotokoll [4] kan orsaka snabb insättning och radering av prefix. ii) Stöd för multisändnings vidaresändning kräver att ruttposter läggs till som en del av vidaresändningsprocessen och inte genom ett separat routingprotokoll iii) Varje uppslagningsprogram som inte stöder snabba inkrementella uppdateringar kommer att kräva två kopior av uppslagsstrukturen i snabbt minne, en för uppdateringar och en för uppslagning. Den största nackdelen med befintliga uppslagningssystem är bristen på både skalbarhet och snabb uppdatering. Nuvarande IP-uppslagningsprogram finns i två kategorier: de som använder precomputation, och de som inte gör det. System som "binär sökning på prefix längder" [9], "Lulea komprimerade försök" [1], eller "binary sökning på intervaller" [5] utföra precomputation för att påskynda sökningen; dock, lägga till ett prefix kan orsaka att datastrukturen byggs om. Således, precomputation-baserade system har en värsta fall uppdateringstid på (n). Å andra sidan använder triebaserade system (t.ex. [8], [7] ) inte precomputation, men deras söktid växer linjärt med prefixets längd. Vi introducerar ett nytt IP-lookup system vars sämsta fall sökning och uppdateringstid är O(log n), där n är antalet prefix i vidarebefordran tabellen. Vårt schema är baserat på en ny datastruktur, ett multiway range träd, som uppnår optimal uppslagningstid för binär sökning, men kan också uppdateras snabbt när ett prefix läggs till eller tas bort. (Som kontrast är vanlig binär sökning [5] ett precomputation-baserat system vars värsta fall uppdateringstid är (n). Vårt huvudsakliga bidrag är att ändra binär sökning efter prefix för att ge snabba uppdateringstider. I standard binär sökning [5], varje prefix kartor till en adressområde. En uppsättning n prefix partitionerar adressraden i högst 2n intervall. Vi bygger ett träd, vars blad motsvarar intervallslutpunkter. Alla pakethuvuden som kartlagts till ett intervall har samma längsta prefixmatchning. Söktid är O(log n). Problemet är uppdatering: ett prefix intervall kan delas i (n) intervall, som behöver uppdateras när prefixet läggs till eller tas bort. Således vår första idé är att associera en adress spännvidd med varje träd nod v; spännvidden av v är det maximala intervallet av adresser som den slutliga sökningen kan falla efter att ha nått v. Således är rot spännvidden hela adressområdet. Vi associerar sedan med varje nod v uppsättningen prefix som innehåller spännvidden av v. Detta resulterar dock i lagring redundant prefix. För att ta bort denna redundans lagrar vi ett prefix med en nod v om och endast om samma prefix inte lagras hos föräldern w av noden. Eftersom spännvidden av v är en subrange av spännvidden av w, varje prefix som innehåller spännvidden av w, kommer att innehålla spännvidden av v. Med hjälp av denna komprimering regel kan vi bevisa att endast ett litet antal prefix behöver förhandsberäknas och lagras; därmed uppdateringar ändra information endast vid O(log n) noder. Genom att öka arity av trädet, kan vi minska höjden av trädet till O(log d n), för alla heltal d. Vi väljer d så att hela noden kan passa i en cache linje. Till exempel ger 256 bitars cachelinje och arity-14 en trädhöjd på cirka 5 eller 6 för de största IPv4-databaserna. Vårt tredje bidrag är att utöka flervägsträden till IPv6. På en 32-bitars maskin, en enda 128-bitars adress kommer att kräva 4 minnesåtkomster. Ett system för IP-lookup som utformats för IPv4 kan därför sakta ner med en faktor 4 när det används för IPv6. I praktiken, eftersom vi antar breda minnen av minst 128 bitar, kan vi hantera så breda prefix i en minnesåtkomst. Tyvärr resulterar användningen av 128 bitars adresser i användningen av en liten förgreningsfaktor och därmed stora trädhöjder. För att undvika detta problem generaliserar vi vårt schema 0-7803-7206-9/01/$17.00
Antalet cachefel som inträffar när REF:s datastruktur används är Oðlog n på varje operation.
Multiway range trees: scalable IP lookup with fast updates
{'venue': "GLOBECOM'01. IEEE Global Telecommunications Conference (Cat. No.01CH37270)", 'journal': "GLOBECOM'01. IEEE Global Telecommunications Conference (Cat. No.01CH37270)", 'mag_field_of_study': ['Computer Science']}