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

doctoral thesis

• 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; 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: IP lookups; LPM; software packet processors; software routers; router performance
• Keywords (croatian): internetski usmjeritelji; pretraživanje najdužih prefiksnih podudaranja; programska komutacija paketa xv
• 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
• Created on: 2020-01-20 12:34:08