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

disertacija

• Naslov (hrvatski): Poboljšanje izvedbe programskih internetskih usmjeritelja pomoću kompaktnih preglednih struktura i efikasnih podatkovnih staza
• Autor: Marko Zec
• Mentor: Miljenko Mikuc (mentor)
• Član povjerenstva: Miljenko Mikuc (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; (Zavod za telekomunikacije); Zagreb
• Datum i država obrane: 2019, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo; Informacijski sustavi
• Univerzalna decimalna klasifikacija (UDC): 621.3 - Elektrotehnika

Sažetak

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.

Sažetak (hrvatski)

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.

• Ključne riječi: IP lookups; LPM; software packet processors; software routers; router performance
• Ključne riječi (hrvatski): internetski usmjeritelji; pretraživanje najdužih prefiksnih podudaranja; programska komutacija paketa xv
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:455203
• Studijski program: Naziv: Elektrotehnika i računarstvo; Vrsta studija: sveučilišni; Stupanj studija: poslijediplomski doktorski; Akademski / stručni naziv: Doktor znanosti elektrotehnike i računarstva (dr.sc.)
• Vrsta resursa: Tekst
• Opseg: 77 str. ; 30 cm
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-01-20 12:34:08