針對內部網路多重服務之重疊性封包區分法

Abstract

傳統上當一個進來的封包經過一個邊界器時需要多次查詢各個服務的規則資料庫才能得知各個服務所需要的動作，也就是所謂的封包區分。這篇論文在探討如何整合各個服務的區分規則以及藉由一次查詢這個資料庫而得到各個服務所需要的動作。以處理網際網路協定目的位址和來源位址欄位所組成的hierarchical tries演算法為基準，我們提出了兩個演算法，intersection 和 two-parent tree。它們各有其適用的範圍；前者對規則的各個欄位分別以tries或表格的結構來儲存並且在封包區分時將各個結構查詢的符合結果取交集，而後者藉由額外的母網路指標加速在hierarchical tries中的尋找過程。Intersection演算法適合在規則數不多的情形下可以有不錯吞吐量。而 two-parent tree這個演算法相較起在吞吐量上的表現比hierarchical tires好上二至三倍並不因為規則數的多寡而有太大的變化。結果也同時顯示對多重服務的封包區分法和針對單一服務的封包區分演算法比較起來是值得的。

Traditionally, to receive multiple services a packet going an edge router needs multiple table lookups, i.e. packet classification. In this work, we investigate how to integrate the classification rules of multiple services and lookup once to get the actions applied to an incoming packet. Taking hierarchical tries of source and destination IP addresses as the baseline algorithm, we present two alternatives, intersection and two-parent tree; the former maintains separate tries or tables for different fields and intersects the matching results on separate structures, while the latter speedups the traversal of hierarchical tries by the extra two-parent pointers. When the number of rules is small, the intersection algorithm performs well in throughput. Two-parent tree outperforms hierarchical tries 2 to 3 times in throughput regardless of the number of rules. The result also shows that one time classification for multiple services pays off.