簡易檢索 / 詳目顯示

回結果列表
研究生： 林勇傑
Lin, Yung-Chieh
論文名稱： 動態路由表查詢演算法及封包分類演算法
Algorithms for Dynamic Routing Lookups and Packet Classification
指導教授： 張燕光
Chang, Yeim-Kuan
學位類別： 博士
Doctor
系所名稱： 電機資訊學院 - 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2016
畢業學年度： 104
語文別： 英文
論文頁數： 105
中文關鍵詞： 網際網路位址查詢 、動態路由表 、最長前綴比對 、二元搜尋樹 、B樹 、路由表更新 、封包分類 、網路處理器
外文關鍵詞： IP address lookup, dynamic routing table, longest-prefix matching, binary search tree, B-trees, route update, packet classification, network processor
相關次數： 點閱：114  下載：4 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 當今的網際網路是由網路路由器相互連結所構成。路由器最主要的功能是把通過此路由器的網路封包正確地往下一個路由器傳送。這個功能是以封包的網路目的地位址在路由器內的路由表做查詢而達成。由於封包的網路目的地位址查詢是個很複雜的程序，且路由器內的路由表有越來越大的趨勢，這些原因都是造成網路目的地位址查詢是影響路由器性能最重要的因素。此外網際網路是一個動態的系統。也就是說路由表會有新增或刪除一筆(或多筆)路由資訊的可能。因此對於這些路由資訊的更新，路由器要有能力對這些路由資訊的更新動態地調整路由表。如果對於這些路由資訊的更新，路由器需要花大量的計算、多次的記憶體存取、或甚至需要再把一張新產生的路由表重新載入到記憶體中，這都將會嚴重影響路由器的效能。

    本篇論文著重在開發一個快速且有效率的方法，讓路由器能保有快速的路由查詢效能，且同時能有效率地支援動態的路由表更新。我們提出了一個名為Collection of Simple and Balanced search Tree (CSBT)的方法。目前文獻上已存在的方法通常均使用複雜的資料結構來實作。有別於目前文獻上已存在的方法，CSBT可以在不做任何的變動下以任何已知的平衡搜尋樹資料結構(例如: 紅黑樹、AVL樹、B樹)來實現。因此CSBT可以比目前文獻上已存在的方法使用更少的記憶體空間。對於一張擁有N筆路由資訊的路由表而言，CSBT的路由表查詢時間、完成一筆路由資訊更新的時間均為O(logN)時間。實驗數據顯示我們所提出的CSBT在路由表查詢速度、更新路由表時間、及記憶體需求量都比目前已知的方法優秀。因此我們相信對於需要高效能的網路路由器來說，我們所提出的CSBT會是一個大有可為的方法。

    除了網路位址查詢，路由器會把收到的封包按照已經事先定義好的封包分類規則，分類成各種封包流。這個過程稱為封包分類。路由器對於屬於同一個封包流的封包將依據對應的封包分類規則做一致的處理。例如:保留固定頻寬給某一封包流的封包。對於很多網路應用，如存取控制、封包流量工程、及侵入偵測，封包分類是很重要的一環。在本論文中，我們提出了一個名為Binary Search on Buckets (BSOB)的方法來處理多維度的封包分類問題。BSOB改進了傳統以決策樹為基礎的封包分類演算法的搜尋方式，如HiCuts和HyperCuts。傳統以決策樹為基礎的封包分類演算法需要從根起點開始一路往下搜尋到尾端樹葉節點才能完成封包分類。而BSOB則是直接在所有依序排列的樹葉節點上做二元搜尋。對於一個樹高為H的決策樹來說，其尾端樹葉節點的數目通常遠小於2H。因此BSOB會比傳統以決策樹為基礎的封包分類演算法擁有更好的效能是由於BSOB的搜尋複雜度是把尾端樹葉節點的總數取以二為基底的對數。這個數值由上述而知會遠小於樹高H。我們以真實的封包分類規則在Intel IXP2400網路處理器上實驗驗證。實驗數據顯示我們所提出的BSOB不管是在封包分類的速度或記憶體的需求量都比目前已知的方法優秀。並且BSOB只需要使用到IXP2400上三顆微處理引擎(IXP2400上總共八顆微處理引擎可供使用)，即可以達到IXP2400的線性輸出效能。

    The Internet consists of meshes of routers that are interconnected by physical links. The main function of routers is to perform a forwarding decision on an incoming packet to determine the packet’s next-hop router. This per-packet forwarding decision is achieved by looking up the destination address of the incoming packet in a forwarding table. The complexity of the forwarding lookup mechanism and the large size of forwarding tables have made routing lookups a bottleneck in the routers. Moreover, the Internet is a dynamic system. New routes and new sub-networks can be added to the Internet. Corresponding to these changes, the routers have to process the changes on the fly and to adjust the routing tables. However, if the update of the routing table requires extensive computation, vast amount of memory accesses, or even total reconstruction of the search structure, it can degrade the performance of a router considerably.

    The works presented in this thesis are motivated by the perspectives described above. In this thesis, we focus on fast and efficient routing lookup algorithms that attempt to overcome the bottleneck of the router. A scheme named the Collection of Simple and Balanced Search Trees (CSBT) is proposed in this thesis. CSBT is designed for dynamic routing tables that can dynamically insert and delete prefixes. Unlike the existing schemes proposed in the literature usually use augmented data structures to implement, CSBT can be implemented with any balanced search tree data structures (e.g., red-black tree, AVL tree, or B-tree) without any modification. As a result, CSBT needs smaller memory consumption than existing schemes. Moreover, the search, insertion, and deletion operations of CSBT can be finished in O(logN) time, where N is the number of prefixes in the routing table. Experimental results with real IPv4 routing tables show that CSBT outperform existing schemes in terms of the search speed, insertion time, deletion time, and memory consumption. We believe CSBT is a promising design for the high speed routers.

    In addition to IP address lookups, routers categorize incoming packets into “flow” according to the pre-defined rules maintained by routers. This process in routers is called packet classification. All packets belonging to the same flow obey the pre-defined rule and are processed in a similar manner (e.g., receive a certain bandwidth to a certain flow) by routers. Packet classification is an essential building block for many emerging network applications such as access control, traffic engineering and intrusion detection. In this thesis, we propose a scheme called Binary Search on Buckets (BSOB) for multi-dimensional packet classification problem. BSOB improves the traditional decision-tree-based schemes like HiCuts and HyperCuts by performing binary searches on the list of ordered leaf nodes in the decision tree, instead of traversing the decision tree from the root node to the leaf node. The search key used in BSOB is a partial set of bits extracted from the 5-dimensional header fields of the packets according to the pre-built decision tree. BSOB is much faster than the traditional decision-tree-based schemes because, for a real-world classifier, the number of leaf nodes is much smaller than 2H, where H is the height of the decision tree. In other words, the search complexity of BSOB, which is log(number of leaf nodes), is much smaller than those of the traditional decision-tree-based schemes, which are H. The experimental results conducted on Intel IXP2400 network processor show that BSOB outperforms HyperCuts in terms of the classification speed and the memory consumption, and is able to achieve the line speed of IXP2400 while only three micro-engines are used.

    Chapter 1 Introduction 1 1.1 The functions of current high speed routers 2 1.1.1 IP header processing 3 1.1.2 Packet forwarding 4 1.1.3 Non-time-critical tasks 5 1.2 Classless Inter-Domain Routing (CIDR) and longest prefix match 6 1.3 Goals and metrics for IP lookup algorithms 8 1.4 Layer 4 switching 11 Chapter 2 Previous Works on IP Lookup Problem 13 2.1 Ternary CAMs 14 2.2 Static algorithmic schemes 16 2.2.1 The Lulea algorithm 17 2.2.2 Binary search on prefix lengths 19 2.2.3 Binary search on intervals 20 2.3 Dynamic algorithmic schemes 23 2.3.1 Binary trie 23 2.3.2 Path-compressed trie 25 2.3.3 Priority search trees 28 2.3.4 CRBT 31 2.3.5 Enhanced interval trees 33 2.3.6 Multiway range trees 35 2.3.7 PIBT 38 2.4 Existing schemes can be suitable for the pipeline architectures 40 2.4.1 Trie-based pipeline architecture 41 2.4.2 Segment-tree-based pipeline architecture 46 2.5 Complexity comparison of previous works 47 Chapter 3 Dynamic Routing Tables Using Simple Balanced Search Trees 48 3.1 Characteristics of BGP routing tables 48 3.2 Proposed CSBT 50 3.2.1 The search process of CSBT 51 3.2.2 Insert a prefix 52 3.2.3 Delete a prefix 52 3.2.4 (W + 1)-bit Prefix format 53 3.3 Performance Evaluations 54 Chapter 4 IP Packet Filtering and Classification 59 4.1 Packet classification problem 60 4.2 Importance of packet classification 62 4.3 Performance metric of packet classification algorithms 64 4.4 Previous works on packet classification problem 65 Chapter 5 Scalable Packet Classification on Network Processor 68 5.1 Proposed BSOB 69 5.1.1 Partition Phase 70 5.1.2 Classification Phase 73 5.2 Correctness of the Search Procedure of BSOB 76 5.3 Improve the Search Performance by Using the Segmentation Table 77 5.4 Three Heuristics to Reduce the Memory Requirement of BSOB 80 5.4.1 Heuristic 1: Simple Grouping Method 80 5.4.2 Heuristic 2: The Duplicated Rules Are Retained in the Internal Nodes 82 5.4.3 Heuristic 3: Combine Heuristic 1 and Heuristic 2 85 5.5 Why Binary Decision Tree 86 5.6 Performance Evaluation 88 5.6.1 IXP2400 Network Processor 89 5.6.2 Resource Allocation 90 5.6.3 Classifiers and Parameters Setup 92 5.6.4 The Worst Case Analysis 93 5.6.5 Memory Usage 94 5.6.6 Performance on IXP2400 95 Chapter 6 Summary and Future Work 97 References 99

    [1] F. Baboescu, D. Tullsen, G. Rosu, and S. Singh, “A Tree Based Router Search Engine Architecture With Single Port Memories,” Proceeding of IEEE International Symposium on Computer Architecture (ISCA), pages 123-133, June 2005.
    [2] F. Baboescu, and G. Varghese, “Scalable packet classification,” IEEE-ACM Transactions on Networking, vol. 13, no. 1, pp. 2-14, Feb. 2005.
    [3] F. Baker, “Requirements for IP Version 4 Routers,” RFC 1812, June 1995.
    [4] M. Bando, S. Artan, and H. Chao, “FlashLook: 100-Gbps Hash-Tuned Route Lookup Architecture,” Proceeding of IEEE International Workshop on High Performance Switching and Routing (HPSR), June 2009.
    [5] M. Bando and H. Chao, “FlashTrie: Hash-based Prefix-Compressed Trie for IP Route Lookup Beyond 100Gbps,” Proceeding of IEEE INFOCOM, pages 1-9, March 2010.
    [6] A. Basu and G. Narlikar, “Fast Incremental Updates for Pipelined Forwarding Engines,” IEEE/ACM Transactions on Networking, vol. 13, no. 3, pages 690-703, June 2005.
    [7] M. Behdadfar, H. Saidi, H. Alaei, and B. Samari, “Scalar Prefix Search: A New Route Lookup Algorithm for Next Generation Internet,” Proceeding of IEEE INFOCOM, pages 2509-2517, April 2009.
    [8] M.D. Berg, M.V. Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications. Springer Verlag, 1997.
    [9] BGP Routing Table Analysis Reports, http://bgp.potaroo.net/.
    [10] Y. Chang, “Fast Binary and Multiway Prefix Searches for Packet Forwarding,” Computer Network, vol. 51, no. 3, pages 588-605, 2007.
    [11] Y. K. Chang, “Efficient Multidimensional Packet Classification with Fast Updates,” IEEE Transactions on Computers, vol. 58, no. 4, pp. 463-479, Apr. 2009.
    [12] Y. Chang, F. Kuo, H. Kuo, and C. Su, “Layered Trees: Most Specific Prefix-Based Pipelined Design On-Chip IP Address Lookups,” IEEE Transactions on Computers, vol. 63, no. 12, pages 3039-3052, May 2013.
    [13] Y. Chang and Y. Lin, “Dynamic Routing Tables Using Simple Balanced Search Tree,” Lecture Notes in Computer Science (LNCS), vol. 3961, pages 389-398, 2006. Springer.
    [14] Y. Chang and Y. Lin, “Dynamic Segemnt Trees for Ranges and Prefixes,” IEEE Transactions on Computers, vol. 56, no. 6, pages 769-784, June 2007.
    [15] Y. Chang, Y. Lin, and C. Su, “Dynamic Multiway Segment Trees for IP Lookups and the Fast Pipelined Search Engine,” IEEE Transactions on Computers, vol. 59, no. 4, pages 492-506, April 2010.
    [16] H. Chao, “Next Generation Routers,” Proceeding of the IEEE, vol. 90, no. 9, pages 1518-1558, September 2002.
    [17] Y. Cheng and P. Wang, “Packet Classification Using Dynamically Generated Decision Trees,” IEEE Transactions on Computers, vol.64, no. 2, pages 582-586, Feb. 2015.
    [18] Z. Chicha, L. Milinkovic, and A. Smiljanic, “FPGA Implementation of Lookup Algorithms,” Proceeding of IEEE International Workshop on High Performance Switching and Routing (HPSR), pages 270-275, July 2011.
    [19] Z. Cica and A. Smiljanic, “Frugal IP Lookup based on a Parallel Search,” Proceeding of IEEE International Conference on High Performance Switching and Routing (HPSR), pages 1-6, June 2009.
    [20] T. Cormen, C. Lieserson, R. Rivest, and C. Stein, Introduction to Algorithms, second edition MIT Press, 2001.
    [21] Cypress Semiconductor Corp., “CY7C1347G, 4-Mbit (128K X 36) Pipelined Sync SRAM,” Document #: 38-05516, Jan. 2009.
    [22] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small forwarding tables for fast routing lookups,” Proceeding of ACM SIGCOMM, pages 3-14, September 1997.
    [23] S. Demetriades, M. Hanna, S. Cho, and R. Melhem, “An Efficient Hardware-based Multi-hash Scheme for High Speed IP Lookup,” Proceeding of IEEE Symposium on High Performance Interconnects (HOTI), pages 103-110, August 2008.
    [24] W. Eatherton, G. Varghese, and Z. Dittia, “Tree Bitmap: Hardware/Software IP lookups with Incremental Updates,” ACM SIGCOMM Computer Communication Review, vol. 34, no. 2, pages 97-122, 2004.
    [25] A. Feldman and S. Muthukrishnan, “Tradeoffs for packet classification,” Proceeding of IEEE INFOCOM, vol. 3, pages 1193-1202, March 2000.
    [26] S. Fuller, T. Li, J. Yu, and K. Varadhan, “Classless inter-domain routing (CIDR): An address assignment and aggregation strategy,” RFC 1519, September 1993.
    [27] F. Geraci, M. Pellegrini, and P. Pisata, “Packet classification via improved space decomposition techniques,” in Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005, pp. 304-312 vol. 1.
    [28] P. Gupta, S Lin, and N. McKeown, “Routing lookups in hardware at memory access speeds,” Proceeding of IEEE INFOCOM, pages 1240-1247, April 1998.
    [29] P. Gupta, and N. McKeown, “Packet classification on multiple fields,” in Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, 1999, pp. 147-160.
    [30] P. Gupta, and N. McKeown, “Classifying packets with hierarchical intelligent cuttings,” IEEE Micro, vol. 20, no. 1, pp. 34-41, Jan.Feb. 2000.
    [31] P. Gupta and N. McKeown, “Algorithms for packet classification,” IEEE Network Special Issue, vol. 15, no. 2, pages 24-32, March/April 2001.
    [32] J. Hasan and T. Vijaykumar, “Dynamic Pipelining: Making IP Lookup Truly Scalable,” Proceeding of ACM SIGCOMM, pages 205-216, August 2005.
    [33] E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of data structures in C++. New York: W.H. Freeman, 1995.
    [34] S. Hsieh, Y. Huang, Y. Yang, “Multiprefix Trie: A New Data Structure for Designing Dynamic Router-Tables,” IEEE Transactions on Computer, vol. 60, no. 5, pages 693-706, 2011.
    [35] N. Huang, S. Zhao, J. Pan, and C. Su, “A fast IP routing lookup scheme for gigabit switching routers,” Proceeding of IEEE INFOCOM, pages 1429-1436, March 1999.
    [36] W. Jiang and V. Prasanna, “A Memory-Balanced Linear Pipeline Architecture for Trie-based IP Lookup,” Proceeding of IEEE Symposium on High-Performance Interconnects (HOTI), pages 83-90, August 2007.
    [37] W. Jiang, and V. Prasanna, “Multi-Terabit IP Lookup Using Parallel Bidirectional Pipelines,” Proceeding of ACM International Conference on Computing Frontiers, pages 241-250, 2008.
    [38] W. Jiang, Q. Wang, and V. Prasanna, “Beyond TCAMs: An SRAM-based Paralle Multi-Pipeline Architecture for Terabit IP Lookup,” Proceeding of IEEE INFOCOM, pages 1786-1794, April 2008.
    [39] S. Kumar, M. Becchi, P. Crowley, and J. Turner, “CAMP: Fast and Efficint IP Lookup Architecture,” Proceeding of ACM/IEEE Symposium on Architecture for Networking and Communications Systems (ANCS), pages 51-60, December 2006.
    [40] C. Labovitz, G. Malan and F. Jahabnian, “Internet routing instability,” IEEE/ACM Transactions on Networking, vol. 6, no. 5, pages 515-528, October 1998.
    [41] T. V. Lakshman, and D. Stiliadis, “High-speed policy-based packet forwarding using efficient multi-dimensional range matching,” in Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, 1998, pp. 203-214.
    [42] B. Lampson, V. Srinivasan, and G. Varghese, “IP lookups using multiway and multicolumn search,” Proceeding of IEEE INFOCOM, page 1248-1256, April 1998.
    [43] H. Le, W. Jiang, and V. Prasanna, “A SRAM-based Architecture for Trie-based IP Lookup Using FPGA,” Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM), pages33-42, April 2008.
    [44] H. Le, W. Jiang, and V. Prasanna, “Scalable High Throughput SRAM Based Architecture for IP Lookup Using FPGA,” Proceeding of IEEE International Conference on Field Programmable Logic and Applications, pages 137-142, 2008.
    [45] H. Le and V. Prasanna, “Scalable High Throughput and Power Efficient IP-Lookup on FPGA,” Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM), pages 167-174, April 2009.
    [46] H. Le and V. Prasanna, “Scalable Tree-based Architectures for Ipv4/v6 Lookup Using Prefix Partitioning, ” IEEE Transactions on Computers, vol. 61, no. 7, pages 1026-1039, July 2012.
    [47] Y. Lin, (2005). Dynamic Routing Lookup Algorithms Based on Segment Trees (Master’s thesis, National Cheng Kung University).
    [48] H. Lu, K. Kim, and S. Sahni, “Prefix and interval-partitioned dynamic IP router-tables,” IEEE Transactions on Computers, vol. 54, no. 5, pages 545-557, May 2005.
    [49] H. Lu and S. Sahni, “O(logn) dynamic router-tables for prefixes and ranges,” IEEE Transactions on Computers, vol. 53, no. 10, pages 1217-1230, October 2004.
    [50] H. Lu and S. Sahni, “Enhanced interval trees for dynamic IP router-tables,” IEEE Transactions on Computers, vol. 53, no. 12, pages 1615-1628, December 2004.
    [51] H. Lu and S. Sahni, “A B-tree dynamic router-table design,” IEEE Transactions on Computers, vol. 54, no. 7, pages 813-824, July 2005.
    [52] H. Lu and S. Sahni, "O(log W) multidimensional packet classification," IEEE-ACM Transactions on Networking, vol. 15, pp. 462-472, Apr 2007.
    [53] Y. Luo, L. Bhuyan, and X. Chen, “Shared Memory Multiprocessor Architectures for Software IP Routers,” IEEE Transactions on Parallel and Distributed System, vol. 14, no. 12, pages 1240-1249, December 2003.
    [54] C. Matsumoto, “Cam vendors consider algorithmic alternatives,” EETimes, May 2002.
    [55] A. McAuley and P. Francis, “Fast Routing Table Lookups Using Cams,” Proceeding of IEEE INFOCOM, pages 1382-1391, March 1993.
    [56] E. McCreight, “Priority Search Trees,” SIAM Journal on Computing, vol. 14, no. 1, pages 257-276, 1985.
    [57] D. Medhi and K. Ramasamy, Network Routing: Algorithms, Protocols, and Architectures, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2007.
    [58] D. Meyer, University of Oregon Route Views Archive Project, at http://archive.routeviews.org/.
    [59] S. Nilsson and G. Karlsson, “IP-Address lookup using LC-trie,” IEEE Journal of Selected Areas in Communications, vol. 17, no. 6, pages 1083-1092, June 1999.
    [60] D. Pao, Z. Lu, and Y. Poon, “Bit-Shuffled Trie: IP Lookup with Multi-Level Index Tables,” Proceeding of IEEE International Conference on Communications (ICC), pages 1-5, June 2011.
    [61] C. Partridge, P.P. Carvey, E. Burgess, I. Castineyra, T. Clarke, L. Graham, M. Hathaway, P. Herman, A. King, S. Kohalmi, T. Ma, J. Mcallen, T. Mendez, W.C. Milliken, R. Pettyjohn, J. Rokosz, J. Seeger, M. Sollins, S. Storch, B. Tober, G.D. Troxel, D. Waitzman and S. Winterble, “A 50-Gb/s IP router,” IEEE/ACM Transactions on Networking, vol. 6, no. 3, pages 237-248, June 1998.
    [62] M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, “Survey and taxonomy of IP address lookup algorithms,” IEEE Network, vol. 15, no. 2, pages 8-23, March/April 2001.
    [63] S. Sahni, Data Structures, Algorithms, and Applications in Java, second edition Silicon Press, 2005.
    [64] S. Sahni and K. Kim, “An O(logn) dynamic router-table design,” IEEE Transactions on Computers, vol. 53, no. 3, pages 351-363, March 2004.
    [65] S. Sahni, K. Kim, and H. Lu, “Data structures for one-dimensional packet classification using most-specific-rule matching,” International Journal of Foundations of Computer Science, vol. 14, no. 3, pages 337-358, 2003.
    [66] D. Shah and P. Gupta, “Fast updating algorithms for TCAMs,” IEEE Micro, vol. 21, pages 36-47, January-February 2001.
    [67] P. Shivakumar and N. Jouppi, CACTI, http://www.hpl.hp.com/research/cacti/.
    [68] S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet classification using multidimensional cutting,” in Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, 2003, pp. 213–224.
    [69] K. Sklower, “A Tree-Based Packet Routing Table for Berkely UNIX,” Technical report, University of California, Berkeley, 1993.
    [70] V. Srinivasan and G. Varghese, “Fast IP lookups using controlled prefix expansion,” ACM Transactions on Computer Systems, pages 1-40, February 1999.
    [71] V. Srinivasan, G. Varghese, S. Suri et al., “Fast and scalable layer four switching,” in Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, 1998, pp. 191-202.
    [72] X. Sun and Y. Zhao, “An On-Chip IP Address Lookup Algorithm,” IEEE Transactions on Computers, vol. 54, no. 7, pages 873-885, July 2005.
    [73] D. E. Taylor, “Survey and taxonomy of packet classification techniques,” ACM Computing Surveys, vol. 37, no. 3, pp. 238-275, Sep. 2005.
    [74] D. E. Taylor, and J. S. Turner, “ClassBench: A packet classification benchmark,” IEEE-ACM Transactions on Networking, vol. 15, no. 3, pp. 499-511, Jun. 2007.
    [75] G. Varghese, Network Algorithmics: An Interdisciplinary Approach to Designing Fast Netwroked Devices, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004.
    [76] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable high-speed IP routing lookups,” Proceeding of ACM SIGCOMM, pages 25-36, September 1997.
    [77] Priyank Warkhede, Subhash Suri, and George Varghese, “Multiway range trees: scalable IP lookup with fast updates,” Computer Networks: The International Journal of Computer and Telecommunications Networking, vol. 44, no. 3, pages 289-303, February 2004.
    [78] T.Y. Woo, “A modular approach to packet classification: algorithms and results,” in Proceedings of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, 2000, pp. 1213-1222 vol.3.
    [79] Y. Yang and V. Prasanna, “High Throughput and Large Capacity Pipelined Dynamic Search Tree on FPGA,” Proceeding of ACM/SIGDA International Symposium on Field Programmable Gate Arrays, pages 83-92, 2010.
    [80] Q. Yaxuan, et al., "Packet Classification Algorithms: From Theory to Practice," in Proceedings of INFOCOM 2009, 2009, pp. 648-656.
    [81] Intel Corporation, “Intel® IXP2400 Network Processor Hardware Reference Manual”, November 2003.
    [82] Intel Corporation, “Intel® IXP2400/IXP2800 Network Processors Microengine C Language Support Reference Manual”, November 2003.
    [83] http://www.baymicrosystems.com/
    [84] http://www.lsi.com/networking_home/networking_products/network_processors/index.html
    [85] http://www.netronome.com/pages/network-flow-processors
    [86] http://www.xelerated.com/en/hx/

    下載圖示 校內：2020-06-28公開
    校外：2020-06-28公開
    QR CODE