一個快速的IP位址路由平行演算法

Abstract

隨著高速網路的急速發展，造就了高頻寬與高品質的網路環境，但也引發了許多網路相關議題。目前影響網路傳輸效能最重要的關鍵為路由器處理封包的能力。一個良好的IP位址路由演算法能夠有效率的縮短封包在路由器上的停留時間，以加快封包在整個網路傳輸的速度。 封包在網路傳輸中，透過查詢路由器中的路由表決定封包下一個前往的節點。路由表中包含前置碼與輸出埠，利用目的地位址查詢路由表中最長長度符合前置碼，將封包傳送到最長長度符合前置碼相對應的輸出埠，此舉確保封包在傳遞過程中越來越靠近目的端，並且成功的傳送到目的端。有鑑於目前提升路由器處理封包速度主要都是仰賴硬體設備的能力，不僅成本高且在一般的路由器並不常見。因此本論文提出一個硬體依賴度低的封包平行搜尋演算法。 本論文分成兩部份，第一部分將路由表資訊以表格方式儲存，以表格表示路由表不僅建構快速且查詢方法簡易。然而此作法會有查詢錯誤情形出現，因此透過加入前置碼，將最差情形時記憶體讀取次數降低到限制的範圍內。此外亦提供IPv6版本的路由演算法；第二部分將本論文提出的IP位址路由搜尋平行化，透過拆解雜湊表到不同的記憶體區塊中，當封包搜尋時能透過在不同的記憶體區塊讀取資訊，以達到平行搜尋的能力。 根據實驗結果顯示，封包查詢到符合前置碼所需耗費的平均記憶體讀取次數約為兩次，而最差記憶體讀取次數則能在所限定的範圍內。在IP位址路由搜尋平行化後，除了不同記憶體區塊的空間大小能達到平衡，且每次搜尋平均讀取記憶體區塊個數大於平行化後所增加的記憶體空間比率。此外本論文提出的平行化搜尋方法不需要額外的硬體支援，也能保障封包在平行搜尋時的傳輸順序。

The development of high speed Internet created a high bandwidth and high quality network environment, and led to a lot of network related issues. The IP address lookup algorithms are the most important key on network transmissions. An efficient IP address lookup algorithm could reduce the router packet processing time to speed up the packets transmission on the network. The router''s routing tables decide the packet''s next hop node. The routing table contains prefixes and output ports. The router compares packet and prefixes to find the longest prefix matching (LPM). The LPM operations transfer packet increasingly close to the final destination node and successful transmission to the final destination node. The current methods of speed up packet processing are dependent on the ability of router hardware, but it is high cost and not common. Therefore this paper presents a fast IP address lookup algorithm with parallel implementation, and it dependences on the hardware in low level. This paper is divided into two sections. The first section describes the information presentation of routing table, it utilizes tabular table to present in this paper. This paper appended prefixes to the tables, and the operation could reduce the memory read times in the set limit times. The IP address lookup parallel algorithm is introduction in the second section. The strategy of parallel algorithm is cutting the hash table to different memory blocks. The packets search through different blocks of memory to read information and achieve the capacity of parallel search. According to the experimental results, the LPM operations memory read average times are about twice, and the memory read times are in the set limit times. The difference memory blocks are mutually balance memory spaces in the IP address lookup parallel algorithm. And the ratio of memory reads to memory spaces is less than one. The IP address lookup parallel algorithm does not require extra hardware support for transmission packets in sequence. Furthermore, this paper provides IPv4 and IPv6 versions of the routing algorithm.