sin huvudsakliga roll som routrar är att vidarebefordra paket till sina slutdestinationer. För detta ändamål måste en router bestämma för varje inkommande paket var den ska skickas härnäst. Närmare bestämt består vidaresändningsbeslutet av att hitta adressen till nästa router och den utflyttningshamn genom vilken paketet ska skickas. Denna vidarebefordran information lagras i en vidarebefordran tabell som routern beräknar baserat på den information som samlas in genom routing protokoll. För att se vidarebefordran tabellen, routern använder paketets måladress som en nyckel; denna operation kallas adresslookup. När vidaresändningsinformationen hämtas kan routern överföra paketet från inkommande länk till lämplig utgående länk, i en process som kallas byte. Internets exponentiella tillväxt har betonat dess routingsystem. Även om datahastigheterna för länkarna har hållit jämna steg med den ökande trafiken, har det varit svårt för routrarnas pakethanteringskapacitet att hålla jämna steg med dessa ökade datahastigheter. I synnerhet är adresslookup-operationen en stor flaskhals i vidarebefordran av dagens routrar. I den här artikeln presenteras en undersökning av de senaste algoritmerna för effektiv IP-adresslookup. Vi börjar med att spåra utvecklingen av IP-adresseringsarkitekturen. Att ta itu med arkitekturen är av grundläggande betydelse för routingarkitekturen, och att se över den kommer att hjälpa oss att förstå problemet med adresslookup. I IPv4 är IP-adresserna 32 bitar långa och när de delas upp i 4 grupper om 8 bitar representeras de normalt av fyra decimaltal åtskilda av punkter. Till exempel motsvarar adressen 10000010_01010110_00010000_01000010 vid punkterad notering 130.86.16.66. Ett av de grundläggande målen med Internetprotokollet är att koppla samman nät, så det var ett naturligt val att routa på nätbasis (i stället för att routa på värdnivå). Därför använde IP-adresssystemet inledningsvis en enkel hierarki på två nivåer, med nätverk på toppnivå och värdar på bottennivå. Denna hierarki återspeglas i det faktum att en IP-adress består av två delar, en nätverksdel och en värddel. Nätverksdelen identifierar det nätverk som en värddator är ansluten till, och därmed kommer alla värdar som är anslutna till samma nätverk överens i nätverksdelen av sina IP-adresser. Eftersom nätverksdelen motsvarar de första delarna av IP-adressen kallas den för prefixet för adress. Vi kommer att skriva prefix som bitsträngar på upp till 32 bitar i IPv4 följt av en *. Till exempel representerar prefixet 1000001001010110* alla de 2 16 adresser som börjar med bitmönstret 1000001001010110. Alternativt kan prefix anges med hjälp av den streckade decimala notationen, så samma prefix kan skrivas som 130.86/16, där talet efter snedstrecket anger prefixets längd. Med en hierarki på två nivåer vidarebefordrade IP-routrar paket baserade endast på nätverksdelen, tills paketen nådde målnätverket. Som ett resultat, en vidarebefordran tabell bara behövde lagra en enda post för att vidarebefordra paket till alla värdar som är anslutna till samma nätverk. Denna teknik kallas adressaggregering och gör det möjligt att använda prefix för att representera en grupp adresser. Varje post i en vidarebefordran tabell innehåller ett prefix, som kan ses i tabell 1 På grund av den snabba tillväxten av trafiken på Internet, ryggrad länkar av flera gigabits per sekund är allmänt utplacerade. För att hantera gigabit per sekund trafikhastigheter, måste ryggrad routrarna kunna vidarebefordra miljontals paket per sekund på var och en av sina hamnar. Snabb uppslagning av IP-adresser i routrarna, som använder paketets destinationsadress för att bestämma för varje paket nästa humle, är därför avgörande för att uppnå den vidarebefordran av paket som krävs. IP-adress uppslagning är svårt eftersom det kräver en längsta matchande prefix sökning. Under de senaste åren har olika algoritmer för högpresterande IP-adressuppslagning föreslagits. Vi presenterar en undersökning av toppmoderna IP-adressuppslagningsalgoritmer och jämför deras prestanda när det gäller uppslagningshastighet, skalbarhet och uppdatering av overhead.
Multi-bit Trie algoritmer REF undersöka en grupp bitar på samma gång.
Survey and taxonomy of ip address lookup algorithms
{'venue': 'IEEE Network', 'journal': None, 'mag_field_of_study': ['Computer Science']}