Abstract-Packet klassificering är den centrala mekanismen som möjliggör många nätverkstjänster på Internet såsom brandvägg paket filtrering och trafik redovisning. Att använda Ternary Content Addressable Memories (TCAM) för att utföra höghastighetspaketklassificering har blivit den faktiska standarden inom industrin. TCAMs klassificerar paket i konstant tid genom att jämföra ett paket med alla klassificeringsregler för ternära kodning parallellt. Trots deras höga hastighet, TCAMs lider av den välkända intervallexpansionsproblem. Eftersom reglerna för paketklassificering vanligtvis har fält som anges som intervaller, kan omvandlingen av sådana regler till TCAM-kompatibla regler leda till en explosionsartad ökning av antalet regler. Detta är inget problem om TCAM har stora kapaciteter. Tyvärr har TCAMs mycket begränsad kapacitet, och fler regler innebär mer energiförbrukning och mer värmeproduktion för TCAMs. Ännu värre är att antalet regler för klassificering av paket har ökat snabbt i och med att antalet tjänster på Internet ökar. Intervallsexpansionsproblemet för TCAM kan åtgärdas genom att överflödiga regler tas bort i paketklassificerare. Denna ekvivalenta omvandling kan avsevärt minska det antal TCAM-poster som behövs av en paketsorterare. Våra experiment på verkliga paket klassificerare visar en genomsnittlig minskning med 58,2% i antalet TCAM poster genom att ta bort överflödiga regler. I detta dokument föreslår vi en all-match baserad komplett redundans borttagning algoritm. Detta är den första algoritmen som försöker lösa första-match problem ur ett all-match perspektiv. Vi formellt bevisa att vår redundans borttagning algoritm garanterar inga överflödiga regler i resulterande paket klassificerare. Vi utförde omfattande experiment på både verkliga och syntetiska paketsorterare. Dessa experimentella resultat visar att vår redundans borttagningsalgoritm både är effektiv när det gäller att minska TCAM-poster och effektiv i fråga om körtid.
Algoritmen för borttagning av redundans i REF kan minska användningen av TCAM genom att eliminera alla överflödiga regler i en paketklassificering.
All-Match Based Complete Redundancy Removal for Packet Classifiers in TCAMs
{'venue': 'IEEE INFOCOM 2008 - The 27th Conference on Computer Communications', 'journal': 'IEEE INFOCOM 2008 - The 27th Conference on Computer Communications', 'mag_field_of_study': ['Computer Science']}