一种基于哈希表和Trie树的快速内容路由查找算法

《一种基于哈希表和Trie树的快速内容路由查找算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第２６卷第１０期计算机应用与软件Ｖｏｌ２６Ｎｏ．１０２００９年１０月ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅＯｃｔ．２００９一种基于哈希表和Ｔｒｉｅ树的快速内容路由查找算法汪志莉沈富可（华东师范大学信息学院上海２００２４１）摘要内容分发网络ＣＤＮ（ＣｏｎｔｅｎｔＤｅｌｉｖｅｒｙＮｅｔｗｏｒｋ）是一个建立并覆盖在互联网之上的一层特殊网络，专门用于通过互联网高效传递丰富的多媒体内容。与传统的网络一样，要求核心路由器每秒能转发几百万个以上的分组，而实现高速分组转发的关键是路由表的组织和快速的路由查找算法。首先概述了内容路由网络的背景，罗列出了几种常见

2、的路由查找算法，并在此基础上，引入基于Ｈａｓｈ和Ｔｒｉｅ树的路由查找算法，最后在试验的基础上对平均查找时间、平均查找次数以及最大匹配次数进行了比较分析，试验结论显示该算法缩短了查找时间，提高了系统性能。关键词　　ＣＤＮ（内容分发网络）最长后缀匹配哈希　Ｔｒｉｅ树ＡＦＡＳＴＣＯＮＴＥＮＴＲＯＵＴＩＮＧＬＯＯＫＵＰＡＬＧＯＲＩＴＨＭＯＮＨＡＳＨＡＮＤＴＲＩＥＴＲＥＥＢＡＳＩＳＷａｎｇＺｈｉｌｉ　ＳｈｅｎＦｕｋｅ（ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎ，ＥａｓｔＣｈｉｎａＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２００２４１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ　　Ｃｏｎｔ

3、ｅｎｔＤｅｌｉｖｅｒｙＮｅｔｗｏｒｋ（ＣＤＮ）ｉｓａｌａｙｅｒｏｆｓｐｅｃｉａｌｎｅｔｗｏｒｋ，ｗｈｉｃｈｉｓｂｕｉｌｔａｎｄｃｏｖｅｒｅｄｏｎｔｈｅＩｎｔｅｒｎｅｔａｎｄｄｅｖｏｔｅｓｔｏｄｅｌｉｖｅｒｉｎｇｒｉｃｈｍｕｌｔｉｍｅｄｉａｃｏｎｔｅｎｔｅｆｆｅｃｔｉｖｅｌｙｖｉａｔｈｅＩｎｔｅｒｎｅｔ．Ｌｉｋｅｔｈｅｔｒａｄｉｔｉｏｎａｌｎｅｔｗｏｒｋ，ＣＤＮｒｅｑｕｉｒｅｓｔｈｅｃｏｒｅｒｏｕｔｅｒｔｏｂｅａｂｌｅｔｏｆｏｒｗａｒｄｍｏｒｅｔｈａｎｏｎｅｍｉｌｌｉｏｎｐａｃｋｅｒｓｐｅｒｓｅｃｏｎｄ．Ａｎｄｔｈｅｋｅｙｏｆｆｏｒｗａｒｄｉｎｇｐａｃｋｅｒｓｉｎｈｉ

4、ｇｈｓｐｅｅｄｉｓｔｈｅｏｒｇａｎｉｚａｔｉｏｎｏｆｒｏｕｔｉｎｇｔａｂｌｅｓａｎｄｈｉｇｈｓｐｅｅｄＩＰａｄｄｒｅｓｓｌｏｏｋｕｐａｌｇｏｒｉｔｈｍ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｂａｃｋｇｒｏｕｎｄｏｆｔｈｅＣＤＮｗａｓｆｉｒｓｔｌｙｉｎｔｒｏｄｕｃｅｄｔｏｇｅｔｈｅｒｗｉｔｈｅｎｕｍｅｒａｔｉｎｇｓｅｖｅｒａｌｃｏｍｍｏｎｒｏｕｔｉｎｇａｌｇｏｒｉｔｈｍｓ．Ｏｎｔｈｉｓｂａｓｉｓ，ｔｈｅｐａｐｅｒｉｎｔｒｏｄｕｃｅｄａｎｅｗｒｏｕｔｉｎｇｌｏｏｋｕｐａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＨａｓｈａｎｄＴｒｉｅＴｒｅｅ．Ａｔｌａｓｔ，ｔｈｅａｖｅｒａｇｅｓｅａｒｃｈｔｉ

5、ｍｅ，ａｖｅｒａｇｅｎｕｍｂｅｒｏｆｓｅａｒｃｈａｎｄｔｈｅｌａｒｇｅｓｔｍａｔｃｈｔｉｍｅｗｅｒｅｃｏｍｐａｒａｔｉｖｅｌｙａｎａｌｙｚｅｄｔｈｒｏｕｇｈｔｈｅｅｘｐｅｒｉｍｅｎｔｓ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｎｔｈａｔｔｈｉｓａｌｇｏｒｉｔｈｍｓｈｏｒｔｅｎｓｔｈｅｓｅａｒｃｈｔｉｍｅａｎｄａｌｓｏｉｍｐｒｏｖｅｓｔｈｅｓｙｓｔｅｍｐｅｒｆｏｒｍａｎｃｅ．Ｋｅｙｗｏｒｄｓ　　ＣＤＮ（Ｃｏｎｔｅｎｔｄｅｌｉｖｅｒｙｎｅｔｗｏｒｋ）　Ｌｏｎｇｅｓｔｐｏｓｔｆｉｘｍａｔｃｈ　Ｈａｓｈ　Ｔｒｉｅｔｒｅｅ网站的内容发布到最接近用户的网络０　引言“边缘”，

6、使用户能以最快的速度、从最接近用户的地方获得所需的信息，从目前，互联网整体带宽过剩和局部带宽不足的矛盾日渐突技术上全面解决了由于网络带宽小、出，ＣＤＮ技术的广泛应用为缓解这一矛盾作出了突出的贡献。用户访问量大、网点分布不均等对用其基本思路就是尽可能避开互联网上有可能影响数据传输速度户访问效果的影响，大大提高网络的和稳定性的瓶颈和环节，使内容传输得更快、更稳。响应速度。ＣＤＮ的网络层次如图１图１　ＣＤＮ网络层次图本文在深入了解ＣＤＮ的基础上，着重研究了基于名字的内所示。容路由查找算法。名字路由选路的大小取决于互联网中内容服１．２　基于名字的ＣＤＮ路由务器的数量。当内容服

7、务器的数量很大时，选路表将变得很庞基于名字的ＣＤＮ路由不同于传大。路由查找算法的效率将影响名字路由的往返时间。本文在统的基于ＩＰ地址的路由思想，它是基于用户需求的内容的名字经典的Ｈａｓｈ算法的基础上，引入基于Ｈａｓｈ和Ｔｒｉｅ树的查找算（通常是一个ＵＲＬ）进行路由，如图２所示。法，对原有的查找算法进行了改进，将原来的Ｈａｓｈ表按顶级域名划分成多个Ｈａｓｈ表，大大减少了冲突的次数，节约了查找时间。１　几个重要的概念１．１　ＣＤＮ的概念ＣＤＮ是一个经策略性部署的整体系统，能够帮助用户解决图２　基于名字的内容路由的用户访问流程图分布式存储、负载均衡、网络请