prikaz prve stranice dokumenta Improving performance in software internet routers through compact lookup structures and efficient datapaths
  Download
PDF 1.09 MB
doctoral thesis
Improving performance in software internet routers through compact lookup structures and efficient datapaths
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2019. urn:nbn:hr:168:455203
Zec, Marko
University of Zagreb
Faculty of Electrical Engineering and Computing
Department of Telecommunications

Cite this document

Zec, M. (2019). Improving performance in software internet routers through compact lookup structures and efficient datapaths (Doctoral thesis). Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:455203

Zec, Marko. "Improving performance in software internet routers through compact lookup structures and efficient datapaths." Doctoral thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2019. https://urn.nsk.hr/urn:nbn:hr:168:455203

Zec, Marko. "Improving performance in software internet routers through compact lookup structures and efficient datapaths." Doctoral thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2019. https://urn.nsk.hr/urn:nbn:hr:168:455203

Zec, M. (2019). 'Improving performance in software internet routers through compact lookup structures and efficient datapaths', Doctoral thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 26 November 2020, https://urn.nsk.hr/urn:nbn:hr:168:455203

Zec M. Improving performance in software internet routers through compact lookup structures and efficient datapaths [Doctoral thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2019 [cited 2020 November 26] Available at: https://urn.nsk.hr/urn:nbn:hr:168:455203

M. Zec, "Improving performance in software internet routers through compact lookup structures and efficient datapaths", Doctoral thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2019. Available at: https://urn.nsk.hr/urn:nbn:hr:168:455203

Islandora Bookmark - Please login to use this feature
Metadata
TitleImproving performance in software internet routers through compact lookup structures and efficient datapaths
Title (croatian)Poboljšanje izvedbe programskih internetskih usmjeritelja pomoću kompaktnih preglednih struktura i efikasnih podatkovnih staza
AuthorMarko Zec
MentorMiljenko Mikuc (mentor)
Committee memberMiljenko Mikuc (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
(Department of Telecommunications)
Zagreb
Defense date and country2019, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Information Systems
Universal decimal classification
(UDC)		621.3
APPLIED SCIENCES. MEDICINE. TECHNOLOGY
Electrical engineering
Abstract
Expensive, inflexible, closed yet fast hardware packet datapath implementations have dominated the high-speed and core Internet routing scene over the past two decades due to the lack of performance offered by software routers running on commodity hardware. This thesis challenges the aforementioned status-quo by asserting that the performance potential of multi-core microprocessors for Internet routing applications may be far greater than what is currently thought. The results show that significant improvements in software-based Internet routing performance may be achieved by carefully engineering data structures and algorithms to permit modern CPUs to efficiently leverage its fast and sizable cache hierarchies, thereby extracting more parallelism across multiple execution cores, while preserving the precious main memory bandwidth for packet input and output, or other memory-intensive I/O tasks. The thesis focuses on longest prefix matching (LPM) as a fundamental operation which simultaneously presents a major performance bottleneck and implementation challenge in Internet routers, hardware and software based alike. The proposed algorithm and the accompanying data structures sustain nearly 3.5 billion random LPM lookups per second in a contemporary routing database containing 739561 IPv4 prefixes with 148 unique next-hops, while running on conventional, commodity PC hardware. The thesis dissects how the principles and techniques applied in the design and implementation of the experimental prototype contribute to achieving those throughput levels.
Abstract (croatian)
Tijekom posljednjih dvadesetak godina skupi su, nefleksibilni, zatvoreni, ali visokopropusni usmjeritelji u jezgri Interneta temeljeni na specijaliziranim sklopovljima u potpunosti istisnuli iz upotrebe programski ostvarene usmjeritelje temeljene na mikroprocesorskim platformama opće namjene. Ovaj rad preispituje navedeni status-quo hipotezom da potencijal modernih višejezgrenih mikroprocesora može biti dostatan za učinkovitu primjenu u podatkovnim stazama brzih Internetskih usmjeritelja. Rezultati pokazuju da se povećanja propusnosti programski ostvarenih usmjeritelja mogu postići pažljivim odabirom i konstrukcijom podatkovnih struktura i algoritama koji modernim mikroprocesorima omogućuju učinkovito korištenje priručnih memorija, što se posredno odražava i na učinkovito paralelno izvođenje na više procesorskih jezgri uz malu učestalost pristupa glavnoj memoriji, čija sabirnica više vremena ostaje slobodna za prihvat i odašiljanje paketa, te ostale memorijski zahtjevne ulazno / izlazne zadaće. Disertacija je fokusirana na pretraživanje tablica usmjeravanja kao temeljni postupak pri obradi paketa u Internetskim usmjeriteljima. Predložene klase algoritama s pripadajućim podatkovnim strukturama tijekom izvođenja na računalu opće namjene omogućuju postizanje propusnosti od približno 3.5 milijarde pretraživanja u sekundi u tablici s 739561 IPv4 zapisa i 148 moguća odredišta. U radu se analizira kako načela i postupci primjenjeni u oblikovanju i ostvarenju eksperimentalnog prototipa doprinose postizanju ovakvih razina propusnosti.
Keywords
Keywords (croatian)
Languageenglish
URN:NBNurn:nbn:hr:168:455203
Study programmeTitle: Electrical Engineering and Computing
Study programme type: university
Study level: postgraduate
Academic / professional title: Doktor znanosti elektrotehnike i računarstva (Doktor znanosti elektrotehnike i računarstva)
Type of resourceText
Extent77 str. ; 30 cm
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
RepositoryFER Repository
Created on2020-01-20 12:34:08

(©) Nacionalna i sveučilišna knjižnica u Zagrebu 2015. Sva prava pridržana. | Hrvatske bratske zajednice 4 p.p. 550, 10000 Zagreb, Hrvatska Tel. ++ 385 1 616-4040
OIB: 84838770814 | IBAN: HR66 2340 0091 1000 1008 1, Porezni broj (PDV identifikacijski broj) - VAT Number: HR84838770814
Prijava u repozitorij