Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19664
標題: 一個快速的IP位址路由平行演算法
A Fast IP Address Lookup Algorithm with Parallel Implementation
作者: 謝政哲
Xie, Zheng-Zhe
關鍵字: Internet
網際網路
IPv6
IP Routing Lookup
Longest Prefix Matching
High-Speed Network
Parallel Search
網際網路協定第六版
位址路由
最長前置碼符合
高速網路
平行搜尋
出版社: 資訊科學與工程學系所
引用: [1] W. Doeringer, G. Karjoth, and M. Nassehi, “Routing on Longest-Matching Prefixes,” IEEE/ACM Transactions Networking, vol. 4, no. 1, pp. 86-97, Feb. 1996. [2] K. Zheng, C. Hu, H. Lu, “A TCAM-Based Distributed Parallel IP Lookup Scheme and Performance Analysis,” IEEE/ACM Transactions on Networking, vol. 14, no. 4, pp. 863-875, Aug. 2006. [3] W. Jiang, Q. Wang, and V. K. Prasanna, “Beyond TCAMs: An SRAM-Based Parallel Multi-Pipeline Architecture for Terabit IP Lookup,” IEEE INFOCOM 2008, 2008, pp.1786-1794. [4] V. Srinivasan, G. Varghese, S. Suri, and M. Wald-Vogel, “Fast and Scalable Layer Four Switching,” ACM SIGCOMN Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 1998, pp.191-202. [5] V. Fuller, T. Li, J. Yu, and K. Varadhan, “Classless Inter-Domain Routing(CIDR): an address assignment and aggregation strategy,” Internet Request for Comments 1519, September 1993. [6] D.R. Morrison, “PATRICIA-Pratical Algorithm to Retrieve Information Coded in Alphanumeric,” Journal of the ACM, vol. 15, no. 4, pp 514-534, Oct. 1968. [7] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small Forwarding Tables for Fast Routing Lookups,” ACM SIGCOMM Computer Communication Review, vol. 27, no. 4, pp 3-14, Sep 1997. [8] S. Nilsson and G. Karlsson, “IP-Address Lookup Using LC-tries,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 6, pp.1083-1092, June 1999. [9] V. Srinivasan and G.Varghese, “Faster IP Lookups Using Controlled Prefix Expansion,” ACM SIGMETRICS Performance Evaluation Review, vol. 26, no. 1, pp. 1-10, June 1998. [10] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable High Speed IP Routing Lookups,” ACM SIGCOMM Computer Communication Review, vol. 27, no. 4, pp. 25-36, Oct. 1997. [11] B. Lampson, V. Srinivasan, and G. Varghese, “IP Lookup Using Multiway and Multicolumn Search,” IEEE/ACM Transactions on Networking (TON), vol. 7, no. 3, pp. 58-64, June 1999. [12] S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor, “Longest Prefix Matching Using Bloom Filters,” Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, 2003, pp. 201-212. [13] S. Deering and R. Hinden: Internet Protocol Version 6(IPv6) Specification. RFC 1883, Dec. 1995. [14] C. Huitema, IPv6: The New Internet Protocol. USA: Prentice-Hall, 1996. [15] D. Pao, “TCAM Organization for IPv6 Address Lookup”, The 7th International Conference on Advanced Communication Technology, 2005, pp. 26-31. [16] K. Zheng, Z. Liu, and B. Liu, “A Scalable IPv6 Route Lookup Scheme via Dynamic Variable-Stride Bitmap Compression and Path Compression,” Elsevier Computer Communication, vol. 29, no. 16, pp. 3037-3050 ,Oct. 2006. [17] Q. Sun, X. Huang, X. Zhou, and Y. Ma, “A Dynamic Binary Hash Scheme for IPv6 Lookup,” IEEE GLOBECOM 2008, 2008, pp. 1-5. [18] X. Huang, X. Zhao, G. Zhao, W. Jiang, D. Zheng, Q. Sun, and Y. Ma, “A Novel Level-Based IPv6 Routing Lookup Algorithm,” IEEE GLOBECOM 2008, 2008, pp. 1-5. [19] BGP Routing Table Analysis Reports, http://bgp.potaroo.net/. [20] APNIC, Asia Pacific Network Information Center, http://www.apnic.net/. [21] Merit Networks, Internet performance measurement and analysis (IPMA) statistics and daily reports, http://www.merit.edu/ipma/routingtable/. [22] UCLA CSD Packet Traces, http://www.lasr.cs.ucla.edu/ddos/traces/. [23] M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, “Survey and Taxonomy of IP Address Lookup Algorithms,” IEEE Network, vol. 15, no. 2, pp. 8-23, Apr. 2001.
摘要: 隨著高速網路的急速發展,造就了高頻寬與高品質的網路環境,但也引發了許多網路相關議題。目前影響網路傳輸效能最重要的關鍵為路由器處理封包的能力。一個良好的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.
URI: http://hdl.handle.net/11455/19664
其他識別: U0005-3007200900225000
文章連結: http://www.airitilibrary.com/Publication/alDetailedMesh1?DocID=U0005-3007200900225000
Appears in Collections:資訊科學與工程學系所

文件中的檔案:

取得全文請前往華藝線上圖書館



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.