在第四層路由器中快速分類之旁路比對及有序性查表法

Abstract

為了能夠提供差別性的服務給個別或集合的封包流，整合服務網路內的第四層路由器需要分類出封包到不同的佇列，第四層路由器中的分類模組必需能夠快速地以每秒鐘分類百萬個封包的速度來支援 gigabit 的網路。在這篇論文裡，我們提出一個新的軟體方法以動態的查表順序來查找封包與分類資料庫中的數個欄位，來分類出該封包。這個方法還應用了旁路比對的技術，這個技術使用在當旁路比對能比查找有序性查表的下一個查表順序更快完成分類封包時。我們提出的方法能夠以超過每秒鐘分類一百萬個封包的速度及支援三十萬個封包流的容量來快速地分類封包。在這篇論文中我們也提出這個方法的複雜度的分析與實驗測量的數據。

In order to provide different service treatments to individual or aggregated flows, layer 4 routers in Integrated Services networks need to classify packets into different queues. The classification module of layer 4 routers must be fast enough in order to support gigabit links at a rate of millions of packets per second. In this work, we present a new software method that lookups multiple fields of the packet, in a dynamically pre-defined order, against the classification database. This algorithm also uses a technique called bypass matching if direct comparison of the packet with the classification database is faster than the sequential lookup of the remaining fields. Our ordered lookup with bypass matching algorithm could classify packets at a rate of well over 1 million packets per second while supporting more than 300K flows. Complexity analysis and experiment measurements are also presented in this study.