適用於高速路由器之三級訊務區分演算法

Abstract

根據事先定義的規則，針對若干IP封包的標頭進行的多欄位訊務區分成為日益重要的課題，它在許多複雜的加值服務諸如服務保證、網路安全、防火牆、訊務計費、策定路由、群址傳播等應用上，扮演極為重要的角色。但是當事先定義的規則數量增加時，現有的路由器架構無法提供以線速區分訊務的能力，因此造成網路傳輸上的瓶頸。 在本論文中，我們為邊際路由器提出一種三級訊務區分演算法，根據軟體模擬，它可以在適當的記憶體使用量下，即使面對數千個規則，亦能提供每秒數十萬次訊務區分的處理速度。

Multi-field classification which exams several fields in the IP header according some pre-defined rules is critical to providing many sophisticated value-added service, such as quality of service (QoS), security, firewall, traffic accounting, policy routing, multicast, etc. However, when the number of pre-defined rules increases, traditional routers cannot provide classification on wire speed and will easily become the bottleneck. In this thesis, we proposed a classification algorithm for high speed edge routers. The processing power of our algorithm is over 100 thousand packets per second for thousands of pre-defined rules with multiple fields by software implementation.