多欄位封包分流：演算法與效能評估

Abstract

整個網際網路已漸漸演變成由眾多大型商業網路建設所組合而成的，而其中多數的網路服務業者如今正面臨提供更多樣服務的挑戰。在技術上而言，這代表著我們必須根據一個或多個的封包表頭內容來辨識使用者的資料流，藉以提供不同的服務內容。如何在可接受的記憶體使用量下，於線速達成封包分流已成為高速路由器與交換器設計上的一大挑戰。在本論文中，我們提出了一個針對多欄位的封包分流演算法。實際的軟體模擬中，在事先定義好共四萬個二維規則的條件下，速度可達每秒近六百萬次的分流。

Internet has grown into a combination of many enormous commercial infrastructures. Most ISPs are facing the challenge to provide more kinds of services. Technically, it means we have to classify user traffic for different services based on one or more header fields of IP packets. How to classify traffic with an acceptable memory usage in the line speed has became one of the main challenges in the design of upcoming high-speed routers and switches. In this thesis, we proposed a classification algorithm specific in multiple dimensions. In a software simulation, the throughput is up to 6 million classifications per second with a pre-defined 40000 two-dimension rules.