Idag består jordens befolkning av cirka 7,3 miljarder människor. Dessa personer använder tillsammans 1-2 miljarder mobiltelefoner med olika varianter av operativsystemet Linux. Det är här KTH-forskarnas arbete kommer in i bilden. De har skrivit kod som används i samtliga Linuxbaserade mobiler och datorer som säljs idag.

Gunnar Karlsson, professor vid Skolan för elektro- och systemteknik på KTH.
Foto: Peter Larsson

– Stefan Nilsson och jag utvecklade en algoritm för uppslagning av IP-adresser i routrar för cirka 15 år sedan. Detta arbete togs sedan upp av Robert Olsson, som numera jobbar på Skolan för informations- och kommunikationsteknik på KTH i Kista, och hans tidigare kollegor Jens Låås och Hans Liss i Uppsala. De implementerade algoritmen i Linux, säger Gunnar Karlsson, professor vid Skolan för elektro- och systemteknik på KTH.

Enkelt förklarat så innebär algoritmen att datorer och mobiler lätt och effektivt kan slå upp IP-nummer för att veta vart de skicka data vid kommunikation över internet.

Det var när Gunnar Karlsson och Stefan Nilsson 1997 träffades på Tekniska högskolan i Helsingfors (numera Aalto-universitetet) som arbetet med algoritmen tog fart. Några år senare var två vetenskapliga artiklar skrivna med tillhörande programkod.

– Att arbetet varit framgångsrikt beror nog bland annat på att programkoden tar väldigt lite plats. Motsvarande kod som fanns då skalade dessutom inte alls lika bra som vår. Det vill säga att ju större internet blev, desto sämre fungerade andras lösningar, berättar Gunnar Karlsson.

Hans och Stefans algoritm berördes dock inte av att antalet uppkopplade datorer blev fler, vilket passade bra då internet runt millenniumskiftet växte så det knakade. Algoritmen fungerade lika bra alldeles oavsett.

En anledning till framgången var också att koden var fri och öppen för alla att använda, och därtill väldokumenterad.

– Det var Robert Olsson och hans kollegor Jens Låås och Hans Liss som senare implementerade algoritmen i Linux. Först blev den ett tillägg, sedan standard när den visade sig fungera bättre än dåvarande standard. När Android så tog fart blev det en standard även där, från version 4.3 av mobiloperativsystemet. Det är därför som koden är så välanvänd jorden över, säger Gunnar Karlsson.

Han tillägger att de två vetenskapliga artiklarna han skrivit om algoritmen är bland de mest välciterade vetenskapliga arbete han någonsin gjort. Över 700 citeringar har det blivit sammanlagt.

Enligt Robert Olsson är algoritmen en framgång med tanke på den stora användning och spridning som arbetet fått. Att funktionaliteten används löpande i en av de mest utforskade och prövade områdena av internetkommunikation, det vill säga IP-uppslag, säger förstås något om dess storhet.

Internet baseras idag på version fyra av internetprotokollet (IP). Här är det värt att notera att varje uppkopplad enhet mot internet kräver en adress, och IPv4 innehåller en begränsning i antalet möjliga enheter som kan vara uppkopplade samtidigt.

I IPv4 är den siffran drygt 4 miljarder tillgängliga adresser. När IPv6 – med sina 340 sextiljoner möjliga adresser – slår igenom på bred front så finns det stöd för KTH-forskarnas kod även i denna version.

Den som vill veta mer kan vara behjälpt av att veta att kodfunktionen i Android kallas för fib_trie (i Linux lc_Trie).

Filed under: SvenskTeknik