網際網路路徑選擇硬體之研究

Abstract

本篇論文網際網路上的路徑選擇問題，亦即最長字首比對問題。網際網路的路徑選擇問題首先被討論，接著將會介紹前人在最長字首比對問題上下的工夫，軟體與硬體的解法兼顧。三個解網路網路路徑選擇問題的提案在這裡被提出。第一個提案在實作了傳統網路網路路徑選擇硬體之後發現了一些在整合的角度上值得考慮的問題；接下來我們使用內容可定址記憶體尋求高速低價的網際網路路徑選擇方法，前人在內容可址址記憶體上的偏見在研究之後一一被反駁，唯一剩下的缺點是內容可定址記憶體的高功率消耗問題，而功率消耗的主要原因在這篇論文裡被分析且模型化，最後一個低功率內容可定址記憶體的設計被提出，內容可定址記憶體亦可用於解決封包分類的問題上；最後一個設計將網際網路路徑選擇的問題以一個全新的典範處理，這裡使用了可重定組態的邏輯電路來解決最長字首比對問題。

This thesis studies on the internet routing problem, which is known as the longest prefix match problem. Issues on internet routing is discussed. Previous works on longest prefix match, either hardware or software designs are touched. Three proposals to deal with the internet routing problem is presented here. The first one implements the internet routing hardware in a conventional way and finds some integration issues to be taken into further considerations. Another uses content addressable memories (CAMs) for high speed low-cost internet routing. Previous biased opinions on CAMs are studied and rebuttied one by one, while the only remaining drawback is the power consumption. The major power consuming sources of CAM operations are analyzed and modeled in this thesis, after that a low-power CAM design is proposed. CAM is also suitable for packet classification problem. The last design treats internet routing in an all new paradigm. It employs reconfigurable logic circuits to solve the longest prefix match problem. What is Internet Routing? 2 Trends of Internet Routing in Next Step 3 Motivation 4 Thesis Outline 4 Convention 5 CHAPTER 2 Internet Routing Issues 7 Internet Addressing Architecture 9 Routing protocols 10 Routing tables 11 Linear chart 13 Encompass chart 14 Graph/Tree notation 14 About Router Throughput 15 Layer-3 processing 15 Shared-bus backplane 16 Switching backplane 17 Prefix distribution 19 Supplies and Alternatives of High-Performance Internet Routers 19 Layer-2 function and Ethernet 20 Asynchronous Transfer Mode 20 Wavelength Division Multiplexing 22 IP switching 22 Flow-driven IP switching 23 Topology-driven IP switching 25 CHAPTER 3 Longest Prefix Match 29 Data Structures and Algorithms for Longest Prefix Match 30 Tree expansion 30 Tries 32 Compression scheme [Dege97] 34 Organized tables of hash values [Wald97] 38 Modified binary search [Lamp98] 40 Graph encoding [Tzen99] 41 Dedicated Hardware Solutions For Longest Prefix Match 43 Ternary Content Addressable Memories [Hsia01] 43 Tuned CPU caching [Chiu99b] 46 ASIC routing engines [Hsia00b] 49 Reconfigurable computing [Hsia00a] 50 CHAPTER 4 Internet Routing to Memory Access Speeds 51 Relating Longest Prefix Matching to Memory Access 52 A Feasible Approach to Match Longest Prefix at Memory Access Speed [Gupt98] 53 Two-level indirection: the DIR-24-8 scheme 53 Three-level indirection: the DIR-21-3-8 scheme 54 Compression of Routing Table to Be Looked up at Memory Access Speed [Huan99] 55 Chip Implementation Issues [Hsia00b] 56 Pad and Core of a Silicon Die 56 Architectural Outline of the Trial Version 58 Multi-chip partitioning: looking for very deep submicron environment 60 Design integration 60 A fully pipelined memory access speed architecture 61 Summary 63 CHAPTER 5 Content Addressable Memories 65 Critiques in the public literatures 65 CAM doesn't work trivially 66 CAM is small 66 CAM is expensive 67 CAM cannot keep up with RAM 67 CAM is slow 67 CAM is inefficient 67 CAM gets obsolete when technology advances 69 CAM consumes too much power 69 Content Addressable Memories 69 Binary static CAM [Kado85] 70 Binary static CAM for higher density 72 Pros and cons to use the 9T cell instead of 10T 72 Further modification 74 Low-Power Content Addressable Memories 80 Transistor sizing for lower power 81 Active self-sensed match pulse [Higu95] 82 Selective Precharge [Zuko97] 83 A switched discharging path [Juan97] 84 Nanded match line [Shaf98] 85 Our Low-Power Content Addressable Memory Design 87 Two types of CAM cells 88 The CAM word 88 Write, read and match operations 89 Simulation results 90 Comparison on low-power CAMs 91 Delay analysis on nand-structure match path 92 Ternary extension from static CAM 93 Ternary dynamic CAMs [Wade89] 94 Summary 95 CHAPTER 6 Beyond Memory Access Speed 97 On Memory Access Speed 97 Hierarchical RAM design 100 Memory access speed 100 Another Way to treat Best Match 100 The concept behind FPGA-based routing table 102 Trial on FPGA Implementation 102 Simulation results 105 Summary 106 CHAPTER 7 Contributions and Concluding Ramarks 107 References 109