ㄧ個基於平行處理的高速IPv6位址查表機制

Abstract

網際網路協定第四版（Internet Protocol version 4）早在七零年代末期就被發表出來，並且是目前在網際網路上被廣泛使用的通訊協定。但是隨著網際網路使用者的迅速增加，IPv4的位址數量早已不敷使用。下一代的網際網路通訊協定，也就是IPv6，在1996年左右被發展出來以解決位址短缺的問題。IPv6將位址的長度從32 bits 擴展到 128 bits。 IP位址查表是基於最長字首比對（Longest prefix matching）。在IPv6將位址格式擴展到128 bits的情況下，大部分現有的查表方法難以延伸至IPv6。本篇論文提出ㄧ個基於二元搜尋字首長度（Binary search among prefix lengths） [1] 和平行處理的IPv6查表方法來改善查表效能。首先我們合併 [1] 中的hash tables來改善在最糟情況（Worst case）下所需的查表時間。然後我們利用管線（Pipeline）和多執行緒（Multi-threading）的技巧來改善平均情況（Average case）下的流通量（Throughput）。我們將所提出的查表方法在Intel IXP2400 network processor上實作。IXP2400的平行處理架構幫助我們實現管線和多執行緒的設計。模擬結果顯示最大產出可達平均100個cycles完成一個查表結果，這也表示，在600 MHz處理器速度下，我們提出之方法每秒可完成6百萬個IPv6封包查表。相較於現有之高檔商用產品，我們的方法有明顯較佳的性能改進。