Detta examensarbete har som syfte att titta på om strukturer, så som van Emde Boas och y-fastträd är snabbare än en standardstruktur som binärt trie på att göra IP-uppslagningar i routingtabeller vid vidarebefordring av paket i nätverk. Detta är en av de mest utförda operationerna i dag. Den utförs varje gång ett paket passerar en router och går ut på att hitta den mest lämpliga vägen för paketet att ta sig till värden. Det är i denna operation ett framtida problem kan uppkomma på grund av den ständigt ökande trafiken över nätverken. Att minska tiden för IP-uppslagning med hjälp av strukturerna van Emde Boas eller y-fast kan vara en dellösning för att undvika att routern blir en framtida flaskhals. Resultaten från java-implementationerna visar dock att varken van Emde Boas eller y-fastträd genererar ett bättre resultat än ett binärt trie, trots att uppslagning i dessa strukturer har lägre asymptotisk tidskomplexitet än uppslagning i ett binärt trie. Det finns olika anledningar till att det är så; ett är att de routingtabeller som används ej är tillräckligt stora för att van Emde Boas- eller y-faststrukturernas fördelar ska visas. En annan orsak är att fler minnesaccesser till minnet görs i dessa jämfört med det binära triet. En gräns som länge ifrågasatts är om datagenomströmningen för en router kan överstiga en gigabyte per sekund(GB/s) genom att endast ändra routerns mjukvara och köra denna på standardhårdvara. Detta examensarbete och flera andra arbeten visar att det går att öka datagenomströmningen med lämplig implementation av routingtabellerna och IP-uppslagning. Trots att van Emde Boas eller y-fastträdet inte är bättre än det binära triet i antalet uppslagningar per sekund, visar van Emde Boas träd och det binära triet att dataöverföring i GB/s är möjliga att göra i mjukvara.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-69220 |
| Date | January 2011 |
| Creators | Björklund, Rebecka |
| Publisher | Linköpings universitet, Institutionen för datavetenskap |
| Source Sets | DiVA Archive at Upsalla University |
| Language | Swedish |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds