Change search
ReferencesLink to record
Permanent link

Direct link
Implementation och jämförelse av ordnade associativa arrayer
Linköping University, Department of Computer and Information Science.
2011 (Swedish)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [sv]

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.

Place, publisher, year, edition, pages
2011. , 63 p.
Keyword [sv]
IP-uppslagning, binärt trie, van Emde Boas, y-fast
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-69220ISRN: LIU-IDA/LITH-EX-G–11/006-SEOAI: oai:DiVA.org:liu-69220DiVA: diva2:424605
Subject / course
Computer and information science at the Institute of Technology
Uppsok
Technology
Supervisors
Examiners
Available from: 2011-06-19 Created: 2011-06-19 Last updated: 2011-06-20Bibliographically approved

Open Access in DiVA

fulltext(836 kB)168 downloads
File information
File name FULLTEXT01.pdfFile size 836 kBChecksum SHA-512
d01e7274c4f5ebcbcc34b12bbf98acfd3dd8366232eb9b4f9bffbedc08ab6961f27013fcc82743655ff176fb9d758fbef8f059f385caee86cd8d8e75b4d69e08
Type fulltextMimetype application/pdf

By organisation
Department of Computer and Information Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 168 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 101 hits
ReferencesLink to record
Permanent link

Direct link