期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

一种基于哈希表和Trie树的快速IP路由查找算法 被引量：7

A Fast Routing Lookup Algorithm Based on Hash and Trie
下载PDF
导出
摘要 Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。论文提出了一种基于8比特的前向查找表(LFT)和7比特的简单二进制回退查找Trie树(HBT)的IP路由查找算法。算法综合考虑了IP地址的分布特点,兼顾了查找速度、存储空间利用、硬件实现,以及向IPv6过渡等几个因素。具有算法简单、查找速度较快、存储空间利用率较高、易于扩展和便于硬件实现等特点。 With rapid development of Internet,it orders the core router to be able to forward ten millions of packets per second.High speed IP address lookup algorithm is the key component of high speed packet forwarding.This paper proposes a new scheme witch based on 8-bit level fronted lookup table(LFT)and 7-bit backward searching Trie(HBT).It considers the distributions of IP address and the transition towards IPv6,it's algorithm is simple,lookup speed is quick,and requiring a small number of memory,expand easy,and convenient for implementing with hardware.
作者 崔尚森 张白一
机构地区 西安交通大学电信学院 长安大学信息工程学院西安 长安大学信息工程学院
出处 《计算机工程与应用》 CSCD 北大核心 2005年第9期156-158,共3页 Computer Engineering and Applications
关键词 路由查找 最长前缀匹配 哈希 TRIE树 route lookup,longest matching prefix,Hash,Trie-tree
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献11

  • 1Rekhter Y,Li T.An Architecture for IP Address Allocation with CIDR[S].RFC 1518,1993
  • 2Deering S, Hinden R.Internet Protocol, Version 6 (Ipv6) Specification,Request for Comments(Proposed Standard)[S].RFC 1883,Internet Engineering Task Force, 1996
  • 3Morrison D R.PATRICIA-practical algorithm to retrieve information coded in alphanumeric[J].Journal of ACM, 1968; 15 (4) :514～534
  • 4Miguel a et al. Survey and taxonomy of IP address lookup algorithms[J].IEEE Network,2001; (2) :8～22
  • 5Doeringer W,Karjoth G,Nassehi M.Routing on longest matching prefixes[J].IEEE/ACM Trans Networking, 1996; 14(1) :86～97
  • 6Lampson B,Srinivasan V,Varghese G.IP lookups using multiway and multicolumn search[C].In:IEEE INFOCOM'98,1248～1256
  • 7Henry Hong-Yi T,Tony Przygienda. On fast address-lookup algorithms[J].IEEE Journal on Selected Areas in Communications, 1999;17(6): 1067～1082
  • 8Huang Nen-fu,Zhao Shi-ming. A novel IP-routing lookup scheme and hardware architecture for multigigabit switching routers[J].IEEE Journal on Selected Areas in Communications, 1999; 17(6): 1093～1104
  • 9Lih-Chyau Wuu,Shou-Yu Pin. A Fast IP lookup scheme for longestmatching prefix[C].In:2001 International Conference on Computer Networks and Mobile Computing(ICCNMC'01)Beijing,CHINA.407～412,http://csdl.computer.org/comp/proceedings/iccnmc/2001/1381/00/1381toc.htm
  • 10徐恪,徐明伟,吴建平,吴剑.路由查找算法研究综述[J].软件学报,2002,13(1):42-50. 被引量：43

二级参考文献34

  • 1Radia Perlman. Interconnections, Bridges and Routers [ M ].Addison- Wesley, 1992.
  • 2Keith Sklower.A tree-based routing table for Berkeley Unix[R].Technical report,University of Califomia,Berke-ley, 1993.
  • 3A McAuley,P Francis.Fast routing table lookup using CAMs[C].In: Proceedingsof INFOCOM, 1993 : 1382-1391.
  • 4Peter Newman,Greg Minshall,Larry Huston.IP Switching and gigabit routers[J].IEEE Communications Magazine, 1997.
  • 5Xu, Ke, Wu, Jian-ping, Wu, Jian. The analysis and design of fast route lookupalgorithms for high performance router. In: Kim, Kiseon, ed. Proceedings of the IEEEInternational Conference on ATM. San Francisco: IEEE Computer Society Press, 2001. 320～325.
  • 6Srinivasan, V. Fast and efficient Internet lookups [Ph.D. Thesis]. WashingtonUniversity, 1999.
  • 7Rekhter, Y., Li, T. An Architecturefor IP Address Allocation with CIDR. RFC 1518, 1993.
  • 8Fuller, V., Li, T., Yu, J., et al. Classless Inter-domain Routing (CIDR): anAddress Assignment and Aggregation Strategy. RFC 1519, 1993.
  • 9Hinden, R., Deering, S. IP Version 6 Addressing Architecture. RFC 2373, 1998.
  • 10Partridge, C. Locality and route caches. In: Claffy, K., Garrett, M., Braun, H.-W.,eds. Proceedings of the NSF workshop on Internet Statistics Measurement and Analysis.Diego, CA: NSF Press, 1996. 32～34.

共引文献42

同被引文献50

引证文献7

二级引证文献19

计算机工程与应用
2005年 第9期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部