Full metadata record
DC FieldValueLanguage
dc.contributor.author郭國承en_US
dc.contributor.authorKuo-Chen Kuoen_US
dc.contributor.author陳耀宗en_US
dc.contributor.authorYaw-Chung Chenen_US
dc.date.accessioned2014-12-12T02:30:23Z-
dc.date.available2014-12-12T02:30:23Z-
dc.date.issued2002en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#NT910392102en_US
dc.identifier.urihttp://hdl.handle.net/11536/70164-
dc.description.abstract封包分類的功能在下一世代的路由器設計上扮演了極其重要的角色。 對於支援防火牆,MPLS,QoS之類的應用來說,封包分類是一項最基 本的要求。當網際網路服務提供者(ISP)為了適應使用者不同的需 求時,路由器便需要提供分類各種封包的功能。如何快速的執行封 包分類的動作是這篇論文所想討論的問題。 位元向量演算法是一個在解決封包分類問題方面令人感興趣的硬體方 式。不同於其他利用Ternary CAM解決的硬體方式,它有效地利用記 憶體資源,在中型過濾資料庫的環境下達到非常好的效能。在這篇論 文中,我們試圖改進原有位元向量的方式以擴充至更大的過濾資料庫 。我們結合位元向量和線性搜尋的概念提出一個新的演算法稱為濃縮 位元向量。藉由觀察數個位元向量中相關的資訊,我們濃縮數個相關 的位元向量成為一個單一的位元向量。根據不同的方式濃縮數個位元 向量,我們可以提供適應不同網路環境的靈活性,這是我們演算法中 一個重要的特性。實驗中也證明我們的演算法在需求的空間與搜尋的 速度上遠遠優於原本的位元向量演算法。zh_TW
dc.description.abstractPacket classification plays an important role in the design of new generation router. It is fundamental to the support of applications such as firewalls, MPLS, and QoS. Routers must provide this functionality to classify all kinds of incoming traffic, while ISPs try to offer these network applications for end users. Performing packet classification at wire speed is the main concern of this thesis. Bit vector algorithm proposed in [1] is an interesting hardware solution to solve the packet classification problem. Different from other hardware solutions such as ternary CAM, it efficiently utilize the memories to achieve an excellent performance in medium size filter database. In this thesis, we improve the original bit vector algorithm to scale up with the filter number increases. We proposed a novel algorithm called Bit Vector Condensation that combines the concept of both bit vector search and linear search and condense several bit vectors into one bit vector. With the flexibility of choosing different inclusion criteria, our algorithm could adapt to various environments in the backbone network. Experiments also showed that our proposed algorithm outperforms the bit vector algorithm in the storage requirements and search speed.en_US
dc.language.isoen_USen_US
dc.subject封包分類zh_TW
dc.subject位元向量zh_TW
dc.subject濃縮zh_TW
dc.subject聚集zh_TW
dc.subject擴充性zh_TW
dc.subjectpacket classificationen_US
dc.subjectbit vectoren_US
dc.subjectcondensationen_US
dc.subjectaggregationen_US
dc.subjectscalabilityen_US
dc.title利用濃縮的位元向量之可擴充性的封包分類演算法zh_TW
dc.titleScalable Packet Classification Using Bit Vector Condensationen_US
dc.typeThesisen_US
dc.contributor.department資訊科學與工程研究所zh_TW
Appears in Collections:Thesis