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

Institutional repository: FER Repository

Cite this document

Zec, M. (2019). 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. 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 01 January 2025, 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 2025 January 01] 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

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 - 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
Created on2020-01-20 12:34:08