Luleå algoritm - Luleå algorithm
Den Luleå-algoritmen för datavetenskap , designad av Degermark et al. (1997) , är en teknik för att lagra och söka på internet -routingtabeller effektivt. Det är uppkallat efter Luleå tekniska universitet , teknikinstitutets författare. Algoritmens namn förekommer inte i originalpappret som beskriver det, men användes i ett meddelande från Craig Partridge till Internet Engineering Task Force som beskrev det arbetet innan det publicerades.
Nyckeluppgiften som ska utföras i internetruting är att matcha en given IPv4 -adress (ses som en sekvens med 32 bitar) till det längsta prefixet för adressen för vilken routningsinformation är tillgänglig. Detta prefixmatchningsproblem kan lösas av en trie , men trie -strukturer använder en betydande mängd utrymme (en nod för varje bit av varje adress) och sökning efter dem kräver att en sekvens av noder korsas med längden proportionell mot antalet bitar i adressen . Luleå -algoritmen genvägar denna process genom att bara lagra noder på tre nivåer av trie -strukturen, snarare än att lagra hela trie.
Innan Luleå -trie byggs måste routingtabellsposterna förbehandlas. Alla större prefix som överlappar ett mindre prefix måste delas upp flera gånger i mindre prefix, och endast de prefix som inte överlappar det mindre prefixet behålls. Det krävs också att prefixsträdet är komplett. Om det inte finns några routingtabellsposter för hela adressutrymmet måste det kompletteras med att lägga till dummy -poster, som bara innehåller informationen om att ingen rutt finns för det intervallet. Detta möjliggör den förenklade sökningen i Luleå trie ( Sundström 2007 ).
Den största fördelen med Luleå -algoritmen för routinguppgiften är att den använder väldigt lite minne, i genomsnitt 4–5 byte per post för stora routingtabeller. Detta lilla minnesavtryck tillåter ofta att hela datastrukturen passar in i routningsprocessorns cache, snabbare operationer. Det har dock nackdelen att den inte kan modifieras enkelt: små ändringar i routingtabellen kan kräva att de flesta eller hela datastrukturen rekonstrueras. En modern hemdator (PC) har tillräckligt med hårdvara/minne för att utföra algoritmen.
Första nivån
Den första nivån i datastrukturen består av
- En bitvektor bestående av 2 16 = 65 536 bitar, med en post för varje 16-bitars prefix för en IPv4- adress. En bit i denna tabell är satt till en om det finns routningsinformation associerad med det prefixet eller med en längre sekvens som börjar med det prefixet, eller om det angivna prefixet är det första som är associerat med routningsinformation på någon högre nivå av trie; annars är den inställd på noll.
- En uppsättning 16-bitars ord för varje icke-nollbit i bitvektorn. Varje datum tillhandahåller antingen ett index som pekar på andra-nivå datastrukturobjektet för motsvarande prefix, eller tillhandahåller routningsinformationen för det prefixet direkt.
- En uppsättning "basindex", en för varje på varandra följande delsekvens av 64 bitar i bitvektorn, som pekar på den första datum som är associerad med en icke -nollbit i den undersekvensen.
- En uppsättning "kodord", ett för varje på varandra följande undersekvens av 16 bitar i bitvektorn. Varje kodord är 16 bitar och består av ett 10-bitars "värde" och en 6-bitars "offset". Summan av förskjutningen och det associerade basindexet ger en pekare till den första nollpunkten associerad med en icke-nollbit i den givna 16-bitars undersekvensen. 10-bitarsvärdet ger ett index till en "anpassningsbar" från vilken den exakta positionen för lämplig datum kan hittas.
- En anpassningsbar. Eftersom prefixsträdet måste vara komplett kan det bara finnas en begränsad mängd möjliga 16-bitars bitmaskvärden i bitvektorn, 678. De anpassningsbara raderna motsvarar dessa 678 16-bitars kombinationer och kolumner antalet uppsatta bitar i bitmask vid bitplatsen som motsvarar kolumnen, minus 1. Så skulle kolumn 6 för bitmask 1010101010101010 ha värdet 2. Den anpassningsbara är konstant för alla routingtabellinnehåll.
För att slå upp datumet för en given adress x i den första nivån i datastrukturen beräknar Luleå -algoritmen tre värden:
- basindexet vid positionen i basindexmatrisen indexerat av de första 10 bitarna av x
- förskjutningen vid positionen i kodordmatrisen indexerad av de första 12 bitarna av x
- värdet i anpassningsbart [ y ] [ z ], där y är det anpassningsbara indexet från kodordmatrisen och z är bitarna 13–16 av x
Summan av dessa tre värden ger indexet som ska användas för x i uppsättningen objekt.
Andra och tredje nivå
Den andra och tredje nivån i datastrukturen är strukturerade på samma sätt som varandra; i var och en av dessa nivåer måste Luleå-algoritmen utföra prefixmatchning på 8-bitars kvantiteter (bitarna 17–24 respektive 25–32 i adressen). Datastrukturen är uppbyggd i "bitar", som var och en gör det möjligt att utföra denna prefixmatchningsuppgift på någon undersekvens av adressutrymmet; dataposterna från datastrukturen på första nivån pekar på dessa bitar.
Om det finns få tillräckligt många olika bitar av routningsinformation som är associerad med en bit, lagrar klumpen bara listan över dessa rutter och söker igenom dem med ett enda steg med binär sökning följt av en sekventiell sökning . Annars tillämpas en indexeringsteknik som är analog med den på den första nivån.
Anteckningar
Referenser
- Degermark, Mikael; Brodnik, Andrej; Carlsson, Svante; Pink, Stephen (1997), "Small forwarding tables for fast routing lookups", Proceedings of the ACM SIGCOMM '97 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication , s. 3–14, doi : 10.1145/263105.263133 , S2CID 17232414.
- US 6266706 , Degermark, Mikael; Brodnik, Andrej & Carlsson, Svante et al., "Snabbdirigeringsuppslagningssystem med fullständigt prefixträd, bitvektor och pekare i en routingtabell för att bestämma vart IP -datagram ska dirigeras", utfärdat 2001 .
- Medhi, Deepankar; Ramasamy, Karthikeyan (2007), Network Routing: Algorithms, Protocols, and Architectures , Elsevier, s. 510–513, ISBN 978-0-12-088588-6.
