封包的分類被廣泛的應用在各種不同的網際網路應用上，包含網路安全、服務品質、多媒體傳輸等等。因此,封包的分類在現今也越來越受到重視。傳統上,我們利用三元內容位址記憶體(TCAM)作為硬體的分類引擎。然而,利用這個方法來儲存封包分類規則表是沒有效率的,因為封包的埠號Range欄位在存入TCAM之前必須被分成多個Prefixes後再存入。為了解決這個問題，一個多維的分類方法Parallel Packet Classification( )[2]跟著被提出來。

為了降低成本，當我們儲存封包分類規則表時我們不希望浪費太多的TCAM空間來儲存封包的埠號Range欄位。因此,我們採用 編碼的方法來儲存Range可以大大的降低TCAM空間的使用率。但我們也了解到這些編碼方法在更新封包分類表時是相當耗時的。這是因為這些方法在更新封包分類表時需要重新計算結果及重新對這些Range編碼。

在這篇論文中，我們利用Dynamic Segment Tree (DST)來改善這些將Range對應到TCAM上的編碼方式。DST是一種用來解決動態分類表搜尋問題的區間樹狀的資料結構。並且，我們這些方法發展到能動態地更新,及部分更TCAM單元而不是每次更新所有的TCAM單元。

Packet classification is extensively applied to a variety of Internet applications including network security, quality of service, multimedia communications and so on. Thus, packet classification is gaining more and more concerns nowadays. Traditionally, we consider using standard Ternary Content Addressable Memory (TCAM) as a hardware classification engine. However, this approach is inefficient to store classification tables because the port range fields of a packet have to be broken into prefixes before stored in TCAM. To solve the question, has been proposed, which a novel multifield classification scheme [2].
To reduce the cost, we don’t want waste too much TCAM space when we store the classification tables in TCAM since the port fields of the classification tables are arbitrary ranges. Thus, we adopt the -encoding schemes for the ranges can greatly reduce the usage of TCAM space. We noticed that these encoding schemes are time consuming when updating. This is because these schemes need to pre-compute results and encode the ranges in classification tables.
In this thesis, we improve these encoding schemes which can map the ranges into TCAM with incremental update by using dynamic segment tree (DST), where DST is a segment tree data structure for solving dynamic table lookup problems. And we develop these schemes which can update dynamically, partially update the TCAM entries but not all the ones.

[1] Huan Liu, “Efficient Mapping of Range Classifier into Ternary-CAM”, in Proc. IEEE, Symposium on High Performance Interconnects Hot Interconnects,2002
[2] Jan van Lunteren, “Fast and Scalable Packet Classification”, in IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL.21, NO.4, MAY 2003
[3] Yeim-Kuan Chang and Yung-Chieh Lin, “Dynamic Segment Trees for Ranges and Prefixes”.
[4] M.D. Berg, M.V. Kreveld, M. Overmars, and O. Schwarzkopf, ”Computational Geometry: Algorithms and Application,” Springer Verlag, 1997.
[5] P. Gupta and N.McKeown, “Packet Classification on Multiple Fields”, in Proc. Sigcomm, Comp. Commun. Rev., 29(4):147–60, Sept. 1999.
[6] T. Cormen, C. Lieserson, R. Rivest, and C. Stein, Introduction to Algorithms, second edition MIT Press, 2001.
[7] V. Srinivasan, “A packet classification and filter management system”, in Proc. IEEE INFOCOM, vol. 3, Apr. 2001, pp. 1464–1473.
[8] T. Y. C. Woo, “A modular approach to packet classification: algorithms and result,” in Proc. IEEE INFOCOM, vol. 3, Mar. 2000, pp. 1213–1222.
[9] J. Xu, M. Singhal, and J. Degroat, “A novel cache architecture to support layer four packet classification at memory access speeds” in Proc. IEEE INFOCOM, vol. 3, Mar. 2000, pp. 1445–1454.
[10] P. Gupta and N. McKeown, “Algorithms for packet classification”, in IEEE Network, vol. 15, no. 2, pp. 24–32, Mar. Apr. 2001.
[11] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “Fast and scalable layer four switching”, Comput. Commun. Rev., vol. 28, no. 4, pp. 191–202, Oct. 1998.
[12] P. Gupta and N. McKeown, “Packet classification using hierarchical intelligent cuttings”, in Proc. Hot Interconnects 7. Stanford University, Stanford, CA, Aug. 1999.
[13] T. Lakshman and D. Stiliadis, “High-speed policy-based packet forwarding using efficient multi-dimensional range matching”, Comput. Commun. Rev., vol. 28, no. 4, pp. 203–214, Oct. 1998.
[14] David E. Taylor and Jonathan S. Turner, “ClassBench: A Packet Classification
Benchmark,” WUCSE-2004-28, May 21 2004.
[15] Priyank Warkhede, Subhash Suri, and George Varghese, “Multiway range trees: scalable IP lookup with fast updates,” Computer Networks: The International Journal of Computer and Telecommunications Networking, vol. 44, no. 3, pages 289-303, February 2004.
[16] H. Lu and S. Sahni, “A B-tree dynamic router-table design,” IEEE Transactions on Computers, vol. 54, no. 7, pages 813-824, July 2005.