Improving performance in software internet routers through compact lookup structures and efficient datapaths

Zec, Marko

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

APA 6th Edition

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

MLA 8th Edition

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

Chicago 17th Edition

Harvard

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 25 March 2025, https://urn.nsk.hr/urn:nbn:hr:168:455203

Vancouver

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 March 25] Available at: https://urn.nsk.hr/urn:nbn:hr:168:455203

IEEE

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

Cite this item: https://urn.nsk.hr/urn:nbn:hr:168:455203

Please login to the repository to save this object to your list.

Metadata

Title	Improving 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
Author	Marko Zec
Mentor	Miljenko Mikuc (mentor)
Committee member	Miljenko Mikuc (član povjerenstva)
Granter	University of Zagreb Faculty of Electrical Engineering and Computing (Department of Telecommunications) Zagreb
Defense date and country	2019, 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)
Language	english
URN:NBN	urn:nbn:hr:168:455203
Study programme	Title: 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 resource	Text
Extent	77 str. ; 30 cm
File origin	Born digital
Access conditions	Open access
Terms of use
Repository	FER Repository
Created on	2020-01-20 12:34:08