2008年1月31日 星期四

關於"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

沒有留言: