關於"Packet Classification on Multiple Fields"的報告

在網路的應用上常需要對封包分類，為封包分類的目的有很多，通常目的是為了有不同的service
為封包分類之所以不能快的原因是因為你想要用多少欄位來分類，你就必需查多少次的表(table lookup)，而查表除了用硬體的TCAM能達到O(1)的時間外，用軟體的速度最快也只是O(log n)

在封包的分類上通常是時間和空間的tradeoff，理論上，只要你的記憶體夠大，那麼你可以在一次memory access之後就得到分類結果，完全不需要考慮演算法這種東西，比如說，若要分類的packet header 欄位寬度總合為120bit，那麼你可以建一張2^120大小的表格，然後填入規則，然後在packet到達後，直接用120bit的欄位當index去在取表格，從查表結果就可以知道這個packet該分成哪一類，該採取什麼動作

一般來說，速度快的演算法秏記憶體大，秏記憶體小的演算法速度慢，那麼是不是存在一種演算法可以達到平衡？即，速度讓人滿意，而秏的記憶體空間也可以讓人接受

我想，Packet Classification on Multiple Fields應是可以讓人接受的solution，
Packet Classification on Multiple Fields是sigcomm99的paper，距今快有十年了，paper本身寫得不是那麼容昜讓人看懂(坦白說，我覺得他演算法的psudo code那裡有地方寫錯)，不過Idea很好，Idea 簡單講就是利用分類規則之間的相似性，將相同結果的規則算做一類

就結果來看，他可以在使用120bit寬度資料做分類時，只需要9次的記憶體存取(memory access)以及3次的計算就可以完成分類了，速度算很快了，畢竟，查表(table lookup)跟記憶體存取（memory access）這120bit的資料分別是src ip(32), dst ip(32), L4 proto & flags, L4 src port(16), L4 dst port(16), ToS(8)

這篇paper也不是沒缺點，缺點就是
建表的時間無法預測
建表時用到的暫在記憶體大小無法預測
建完表的表格大小也無法預測

不過這些缺點對你來講不甚重要的話，例如，規則不常更動（即不常建表），device的其它功能記憶體需求沒有那麼緊（即，有足夠的記憶體空間留給演算法建表），那麼這篇paper的Idea就很有價值

這是我用來present的power point file