(44.192.112.123) 您好!臺灣時間:2021/03/06 07:55
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:徐偉倫
研究生(外文):Woei-Luen Shyu
論文名稱:網際網路路由快取之架構設計與效能分析
論文名稱(外文):Architecture Design and Performance Analysis of Internet Route Caching
指導教授:吳承崧侯廷昭
指導教授(外文):Cheng-Shong WuTing-Chao Hou
學位類別:博士
校院名稱:國立中正大學
系所名稱:電機工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:中文
論文頁數:72
中文關鍵詞:路由快取網路時間局部性快取置換演算法字首快取平行路由器架構
外文關鍵詞:routing cachenetwork temporal localitycache replacement algorithmprefix cachingparallelism router architecture
相關次數:
  • 被引用被引用:0
  • 點閱點閱:249
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著網際網路的不斷擴充與成長, 人們對於網路頻寬的需求, 也似乎永無止盡. 除了持續建置高速的鏈結線路外, 如何有效地提升對封包的路由速度, 更是一大關鍵.
在此論文中, 我們審思應如何應用快取技術於路由設備最為有效, 包括路由快取的規劃設計及與路由設備的整合分析. 我們認為, 整合性的路由架構可有效地提高系統效能及降低資源需求, 特別是結合近年來已發表的高速路由技術與CAM晶片, 能在維持原路由效率的情況下, 大幅提昇系統容量.
為佐證路由快取效率的可能性, 我們進一步擷取並分析了台灣學術網路的骨幹訊務與路由表, 並藉此研究快取置換演算法與字首快取法, 在惡劣情況下的表現與差異. 其中, 我們提出的LFU實現例, 有最好的強健性與效能,AAP與APC則能有效地提高系統效能及降低資源需求. 另外, 據我們所知, 這也是第一篇分析骨幹訊務與路由表間關係的論文.
Things usually obey the 20/80 rule, the Pareto Principle, which means that relatively few of components account for relatively most of overall activity. If we can accelerate the activity of these intense components, the overall throughput can be significantly improved. In the activity of routing lookups in network routers, we also observe this 20/80 rule: relatively most of network packets are toward relatively few of destination addresses.
Therefore, assume the results of routing lookups are changed infrequently. By caching routing results in fast storage for future reuse, we can efficiently amortize the cost of routing-lookups over subsequently arrived packets and provide short average routing-lookup time. In particular, the assumption of infrequent changes can be relaxed.
Moreover, in recent years, the lookup speed of Content Address Memory (CAM), a hardware solution for IP caching, is greatly improved. So CAM is a good candidate for “lightweight” routing-lookup modules on input line-cards in parallelism router architecture, especially if lightweight modules can efficiently share a “full” module.
In this dissertation, we start from discussing the design considerations for routing caches of network routes. Then we collect two backbone traffic traces, and analyze the temporal locality in them to know how to exploit it efficiently. Next, several cache replacement algorithms, including FIFO, LRU, random, and a proposed LFU implementation alternative with three schemes, are investigated by trace-driven simulations. Especially, their efficiency and robustness are severely tested under the worst case scenarios.
Furthermore, we propose aligned-ancestor poisoning (AAP) and aligned-prefix caching (APC) to enhance IP caching. AAP is a marking scheme for tree-based routing tables. With limited additional routing overhead, routing results carry singleton information, which indicates whether predefined aligned prefixes are cacheable or not. APC is a caching scheme to utilize such routing results. To properly configure AAP and APC, we further investigate the relationship between network packets and referred singleton prefixes. Our trace-driven simulations show that our schemes can significantly reduce the required cache, compared with the conventional caching schemes.
1. INTRODUCTION 1
2. DESIGN CONSIDERATIONS FOR ROUTING CACHES 5
2.1 WRITE POLICY 6
2.2 CACHE SIZE 7
2.3 MAPPING FUNCTION 8
2.4 BLOCK SIZE 9
2.5 REPLACEMENT ALGORITHM 10
3. ROUTER ARCHITECTURE WITH DISTRIBUTED ROUTING CACHES 12
3.1 INPUT LINE-CARD 12
3.2 ROUTING-LOOKUP MODULE 13
3.3 UPDATE AND MANAGEMENT MODULE 14
3.4 SYSTEM EVALUATION 15
4. TEMPORAL LOCALITY ANALYSIS 17
4.1 TRACE COLLECTION SITES 17
4.2 TRACE COLLECTION METHODOLOGIES 19
4.3 TEMPORAL LOCALITY ANALYSES 20
5. EFFICIENCY OF CACHE REPLACEMENT ALGORITHMS 27
5.1 FIFO, LRU, AND RANDOM ALGORITHMS 28
5.2 LFU IMPLEMENTATION ALTERNATIVE 29
6. DESTINATION CACHING VS. PREFIX CACHING 40
6.1 DESTINATION CACHING 40
6.2 PREFIX CACHING 41
6.3 OUR DESIGNS 44
6.3.1 Aligned-Ancestor Poisoning Scheme 45
6.3.2 Aligned-Prefix Caching Scheme 49
7. SINGLETON PREFIX DISTRIBUTIONS 53
8. EFFICIENCY OF SINGLETON PREFIX CACHES 59
8.1 MERIT OF SINGLETON PREFIX CACHES 59
8.2 PERFORMANCE INVESTIGATION 61
9. SUMMARY AND FUTURE WORK 65
9.1 SUMMARY 65
9.2 FUTURE WORK 67
9.2.1 Requirement growth of Cache Size 67
9.2.2 Adaptive LFU Implementation Alternative 67
[1]W. Doeringer, G. Karjoth, M. Nassehi, Routing on longest-matching prefixes, IEEE/ACM Trans. Networking 4 (1) (1996) 86-97.
[2]M.A. Ruiz-Sanchez, E.W. Biersack, W. Dabbous, Survey and taxonomy of IP address lookup algorithms, IEEE Network 15 (2) (2001) 8-23.
[3]P. Newman, G. Minshall, T. Lyon, L. Huston, IP switching and gigabit routers, IEEE Commun. Mag. 35 (1) (1997) 64-69.
[4]P. Newman, G. Minshall, T.L. Lyon, IP switching-ATM under IP, IEEE/ACM Trans. Networking 6 (2) (1998) 117-129.
[5]E. Rosen, A. Viswanathan, R. Callon, Multiprotocol Label Switching Architecture, Internet RFC 3031, Jan. 2001.
[6]P. Gupta, S. Lin, N. McKeown, Routing lookups in hardware at memory access speeds, in Proc. IEEE INFOCOM '98, Mar. 1998, pp. 1240-1247.
[7]M. Degermark, A. Brodnik, S. Carlsson, S. Pink, Small forwarding tables for fast routing lookups, in Proc. ACM SIGCOMM '97, Oct. 1997, pp. 3-14.
[8]N.-F. Huang, S.-M. Zhao, J.-Y. Pan, C.-A. Su, A fast IP routing lookup scheme for gigabit switching routers, in Proc. IEEE INFOCOM '99, Mar. 1999, pp. 1429-1436.
[9]N.-F. Huang, S.-M. Zhao, A novel IP-routing lookup scheme and hardware architecture for multigigabit switching routers, IEEE J. Select. Areas Commun. 17 (6) (1999) 1093-1104.
[10]T. Chiueh, P. Pradhan, High-performance IP routing table lookup using CPU caching, in Proc. IEEE INFOCOM '99, Mar. 1999, pp. 1421-1428.
[11]Tzi-Cker Chiueh, P. Pradhan, Cache memory design for network processors, in Proc. HPCA-6, Jan. 2000, pp. 409-418.
[12]Tzi-cker Chiueh, P. Pradham, Cache memory design for Internet processors, IEEE Micro 20 (1) (2000) 28-33.
[13]A. Singhal, R. Jain, Terabit switching: a survey of techniques and current products, Computer Commun. 25 (6) (2002) 547-556.
[14]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, A 50-Gb/s IP router, IEEE/ACM Trans. Networking 6 (3) (1998) 237-248.
[15]C. Labovitz, G.R. Malan, F. Jahanian, Internet routing instability, IEEE/ACM Trans. Networking 6 (5) (1998) 515-528.
[16]D.C. Feldmeier, Improving gateway performance with a routing-table cache, in Proc. IEEE INFOCOM '88, Mar. 1988, pp. 298-307.
[17]T.-B. Pei, C. Zukowski, VLSI implementation of routing tables: tries and CAMs, in Proc. IEEE INFOCOM '91, Apr. 1991, pp. 515-524.
[18]A.J. McAuley, P. Francis, Fast routing table lookup using CAMs, in Proc. IEEE INFOCOM '93, Mar.-Apr. 1993, pp. 1382-1391.
[19]W. Stallings, Computer organization and architecture, 3rd edition, MacMillan, 1993.
[20]B. Talbot, T. Sherwood, B. Lin, IP caching for terabit speed routers, in Proc. IEEE GLOBECOM '99, Dec. 1999, pp. 1565-1569.
[21]D. Clark, The design philosophy of the DARPA Internet protocols, in Proc. Communications Architectures and Protocols, Aug. 1988, pp. 106-114.
[22]L.A. Belady, A study of replacement algorithms for a virtual-storage computer, IBM Systems J. 5 (2) (1966) 78-101.
[23]Michigan University and Merit Network, Internet Performance Management and Analysis (IPMA) Project, http://nic.merit.edu/~ipma/.
[24]M.D. Hill, A.J. Smith, Evaluating associativity in CPU caches, IEEE Trans. Computers 38 (12) (1989) 1612-1630.
[25]D. Estrin, D.J. Mitzel, An assessment of state and lookup overhead in routers, in Proc. IEEE INFOCOM '92, May 1992, pp. 2332-2342.
[26]X. Chen, Effect of caching on routing-table lookup in multimedia environment, in Proc. IEEE INFOCOM '91, Apr. 1991, pp. 1228-1236.
[27]E. Besson, P. Brown, Performance evaluation of hierarchical caching in high-speed routers, in Proc. IEEE GLOBECOM 98, Nov. 1998, pp. 2640-2645.
[28]Cisco Systems, Cisco XR 12000/12000 Series Routers, http://www.cisco.com/ en/US/products/hw/routers/products_announcement0900aecd8027c804.html.
[29]Cisco Systems, Cisco 12000 Series Two-Port OC-192c/STM-64c POS Line Card, http://www.cisco.com/en/US/products/hw/modules/ps2710/products_data_sheet09186a00801df205.html.
[30]Cisco Systems, Cisco 12000 Series One-port OC-192c/STM-64c POS/SDH Enhanced Services Line Card, http://www.cisco.com/en/US/products/hw/modules/ps2710/ products_data_sheet09186a0080091cd8.html.
[31]The computer center of the Ministry of Education, TANet Introduction, http://www.edu.tw/tanet/introduction.html (in Chinese) .
[32]K. Thompson, G.J. Miller, R. Wilder, Wide-area Internet traffic patterns and characteristics, IEEE Network 11 (6) (1997) 10-23.
[33]Cisco Systems, NetFlow services and applications, http://www.cisco.com/warp/public/cc/pd/iosw/ioft/neflct/tech/napps_wp.htm.
[34]D. Thiebaut, J.L. Wolf, H.S. Stone, Synthetic traces for trace-driven simulation of cache memories, IEEE Trans. Computers 41 (4) (1992) 388-410.
[35]D. Thiebaut, J. Wolf, H. Stone, Corrigendum to “synthetic traces for trace-driven simulation of cache memories,” IEEE Trans. Computers 42 (5) (1993) 635-636.
[36]R. Jain, S. Routhier, Packet trains: Measurements and a new model for computer network traffic, IEEE J. Select. Areas Commun. 4 (6) (1986) 986-995.
[37]H. Liu, Reducing cache miss ratio for routing prefix cache, in Proc. IEEE GLOBECOM '02, Nov. 2002, pp. 2323-2327.
[38]W.-L. Shyu, C.-S. Wu, T.-C. Hou, Efficiency analyses on routing cache replacement algorithms, in Proc. IEEE ICC '02, Apr.-May 2002, pp. 2232-2236.
[39]W.-L. Shyu, C.-S. Wu, T.-C. Hou, Multilevel aligned IP prefix caching based on singleton information, in Proc. IEEE GLOBECOM '02, Nov. 2002, pp. 2345-2349.
[40]M.H. MacGregor, Design algorithms for multi-zone IP address caches, in Proc. HPSR '03, Jun. 2003, pp. 281-285.
[41]J. Mogul, J. Postel, Internet standard subnetting procedure, Internet RFC 950, Aug. 1985.
[42]V. Fuller, T. Li, J. Tu, K. Varadhan, Classless Inter-Domain Routing (CIDR): an address assignment and aggregation strategy, Internet RFC 1519, Sep. 1993.
[43]J. Postel, Address mappings, Internet RFC 796, Sep. 1981.
[44]V. Srinivasan, G. Varghese, Fast address lookups using controlled prefix expansion, ACM Trans. on Computer Systems 17 (1) (1999) 1-40.
[45]H. Liu, Routing prefix caching in network processor design, in Proc. ICCCN '01, Oct. 2001, pp. 18-23.
[46]D. Shah, P. Gupta, Fast updating algorithms for TCAM, IEEE Micro 21 (1) (2001) 36-47.
[47]H. Liu, Routing table compaction in ternary CAM, IEEE Micro 22 (1) (2002) 58-64.
[48]K. Sklower, A tree-based routing table for Berkeley Unix, Technical report, University of California, Berkeley, 1993.
[49]M.J. Akhbarizadeh, M. Nourani, Efficient prefix cache for network processors, in Proc. 12th Annual IEEE Symposium on High Performance Interconnects, Aug. 2004, pp. 41-46.
[50]W.E. Leland, M.S. Taqqu, W. Willinger, D.V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Trans. Networking 2 (1) (1994) 1-15.
[51]T. Karagiannis, M. Molle, M. Faloutsos, Long-range dependence ten years of Internet traffic modeling, IEEE Internet Computing 8 (5) (2004) 57-64.
[52]J. Alghazo, A. Akaaboune, N. Botros, SF-LRU cache replacement algorithm, Proc. International Workshop on Memory Technology, Design and Testing '04, Aug. 2004, pp. 19-24.
[53]National Laboratory for Applied Network Research, Passive Measurement and Analysis (PMA) Project, http://pma.nlanr.net/.
[54]Po-Feng Lin, Master Thesis, Department of Electrical Engineering, National Chung Cheng University, 2005.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔