@ fnii.cn

登录邮箱

刘斌 NDN网络中的高速名字查找与内置缓存:技术与算法

发表日期:2013年12月13日      共浏览 2442 次      编辑:

大家好!

我跟大家分享的题目是名字路由查找与内置缓存路由器。第一个方面是对互联网应用需求再思考。其次介绍一下名字的特点,接下来介绍一下名字查找算法及成本计算,第四,内容储存路由器,最后做一个简单的总结。回顾一下互联网的发展,方面很多,我这里有四个信息。第一个信息互联网上的应用,生产力和生产关系,发生几个变化,第二个是互联网传输效率比较低需要改进,第三个是移动访问决定未来的互联网形态。我们说互联网上的通信模式正在发生质的变化,这不是一个骇人听闻的话,我们看到早期的互联网因为计算资源比较紧缺,远程用户只能远程登录到昂贵的计算机资源,分时计算计算资源,我们必须借助IP地址。因此我们用的是端到端的计算模式,现在随着云计算的兴起和虚拟化的技术发展,我们做的技术,出现了一种新的模式,P2C就是人到内容的结算模式,我们需要做一个计算,我们最关心的我们不关心计算资源在什么地方,我们最关心的是哪里可以帮助我们完成这项计算。最快最安全,最便宜就可以了。

上午提到了信息请求量发生了变化,过去很多信息流量是交互式的业务,现在很多是请求性的业务。早在20年以前,我讲课的时候给学生做过一个PPT示范,当时讨论的是SDN业务分类,现在的很多业务流量占了99%以上,面对这种情况,我们互联网的运行机制,就必须适应这种流量的变化。才能提高其效率。上午已经有好几个报告里面都看到这个了,我们提前没商量,我这是第三次还是第四次出现,虽然我们说互联网的信息爆炸,但是互联网传输冗余是非常高的,我们看到微博还有一些微视频,内容分法业务,储存了大量的储存冗余。优酷在2011年视频播放量超过1亿次,造成了互联网大量的传输冗余。像P2P、CDN、云计算也有大量的重复传输。我们希望没有冗余,而且时间还快。第三个思考,移动通信决定未来互联网的形态。怎么理解呢?将来的运营商,谁能抓住移动通信的用户群,谁就赢了。移动通信决定互联网形态很重要的作用。思科预测,明年无线通讯流量将会超过有线通信。我国会出现两个最大,第一个就是最大的移动用户群,这个可能成为一个不争的事实,这个大家没有时间担心。第二个就是很可能,未来还会成为最大的信息产量国,这个大家去思考。刚才讲了移动通信,谁很好的支持了移动通信,谁就获得了未来网络的先机。在这种情况下内容通信网络被提出了,早上张博士也做了一个很好的介绍。我们说IP网络是以IP地址为中心,我们找一个内容,第一步先找到IP地址所在地,第二步才能找到内容,以内容为中心,我撇开IP地址,就找内容。我是以最快捷、安全、方便的方式找到我想关心的内容。

另外一个特点就是网络里面要储存内容,这个是和我们以前是不一样。我这里有两个数据跟大家共享。谷歌一次搜索,你去搜索引擎,你敲一个搜索命令,消耗的能量,相当于100W的灯泡工作1个小时,大家如果上网的话,还要节省互联网的能源,第二个说的是这样,有一个报告,说网络延迟每增加0.4秒年收入就会损失掉1.6亿美元,网络延迟是非常重要的。第一个是基于名字的路由查找,第二个是内容缓存能力,第三个是多径数据传输。当下一个请求继续向网络送出的时候,目的就不用到达客户端了,就可以直接送到用户,减少了用户的时间。也节约了整个互联网的功耗。这样一来,我们就有两个大的叛逆的思想,第一个是基于名字的查找,为什么说是叛逆呢?这和我们长期以来遵循互联网的原则,网络要简单,边缘复杂相违背。基于名字查找,名字很复杂,接下来会讲。人们会担心基于名字的查找,你做的多么复杂,速度有多快,代价怎么样。下面一个PPT里面会跟大家做一个分享,第二个里面路由器里面要储存内容。过去互联网只是一个简单的管道产生内容,我们几十年以来都遵循这个道理。现在网络里面的内容,我们过去遵循的定理就发生了变化,这两个相悖的时间,是不是在我们未来的网络里面会造成改变。本报告就这两个问题跟大家做一个讨论,首先为了说明基于名字路由查找技术有多复杂,成本有多高,我想介绍一下名字查找是怎么工作。

早上在介绍的时候,按照名字可以分解成很多的子名,我请求是用两个包,网络路由器里面,还有一张路由表,路由表是由什么组成呢?是由名字前缀组成,遵循最长前的匹配。查找这张表是需要实时的,速度要求比较快,不能花很长时间。我们说为什么名字查找是非常复杂的呢?我们就看看这个图上的比较,左侧是IPv4的路由表,名字无非是长度相同。比特的长度是相同,右侧是名字的前缀,我们看到名字前缀是这样,不仅仅是数字组成,还有字数,还有其他的符号。第二个长度不定长和变长,第三个它的长度还没有一个明显的,可能非常非常长。这是说它本身名字构成就比较复杂。第二个这个名字路由表可能非常大,大到什么程度?现在路由表大概在500k到400k,基于名字的路由表,我们依据当前在整个互联网上活动的域名的数量,大概在130兆左右的域名。我们就是简单储存这些域名,路由表的表象数要到100多兆以上。如果是你把一个ip路由表想象成乒乓球这么大,名字路由表就有大气层那么大,我们技术上能够做好吗?不但名字路由表大,更新速度还快。基于内容网络里面,频繁的发布消息,此外,我互联网上的链路在不断的增加。我们能把它做好吗?我们有5个衡量指标,首先我们想取得很高的速度,其次,我们想让储存占的很小,再者,我们想让更新的速率很快,算法有很多,我这里只介绍其中一种,看看结果怎么样,怎么理解呢?我们看到左边这张表,就是一个四个表象名字路由表,这一个查找数可以用一个两维转移表来表示。好处就是说我从一个状态输入一个字符,我就可以依次进行访问,查找下一个状态。我搞成对齐的搜索,挤在一位数字里面,目的也是发生紧凑,我需要把地址进行散列。一个大的路由表,在计算机上运行的话,一个礼拜十几天都做不完路由表。同时,我每次去查找一个字符太慢,我想每次查找两个或者多个字符。查找两个字符或者多个字符的好处是速度快。这样使得一位的数字,储存数字不支持多步径的查找,这样我就有很多很多小数组,使得我这个速度加快了。第二个,我支持增长。要加入一个新的名字影响一个小的数字内部,其他的数字不影响,这是它的好处。储存大大压缩,保持了速率比较快的优点,这两条都可以保证,有了这个算法以后,要想办法加速查找,我们现在采取的方法,就是用GPU加速查找。我们在一个服务器上通过CPU和GPU的合作方式进行查找。首先我们把名字路由表通过结构变成一个字符串,对字符串数进行改,使其支持更新功能。然后我们把这个测试的压力加在系统上,去测试。实际上为了充分利用GPU大容量的并行处理能力,我是采用数据的批处理,批处理好处是说处理速度很快,坏处是说一大批大家的延迟比较大。因此我在提高速度的同时,还必须要控制我的查找时间。

在这个GPU系统上做的实验表明,得出这个结果,我们GPU查找引擎可以达到63Mb的查找速度,这么一个硬件平台上做的查找速度,等价于我今天IP地址,IP路由表的查找速度,我不用担心我查找速度跟不上。储存侠侣,可以放在我这个系统上。具有很好的拓展性。

有了这么一个系统,目前我们支持64M,现在互联网上活动域名数量接近130多M,现在用新的更新卡可以去掉130M大小没问题。我现在64M名字完成系统,买一块590的GPU卡是1000美金,全部服务器加起来,不需要大板差不多是1000美金,总共加起来是2000美金,2000美金我可以做到64M名字大小的查找,速度可以到大于100G以上。这个结论就是我用现有的技术,把已有的产品拿来完全可以做到高速的查找,以内容为中心了网络里面大客户不用担心。

再跟大家讨论另一个问题就是内容储存路由器,早期的互联网路由器是不储存内容的,现在我们要求路由器要把储存内容的功能加上,我现在的路由器和大容量的储存相捆绑,怎么捆绑?怎么集成,集成完了以后怎么开始网络内容,怎么服务后续到达的需求,这就是成为我们研究的问题。在这个问题里面有三个大的问题,首先是路由器的结构,我们要有硬件支持,第二个要有好的调度策略,读写请求要很好的设计。再一个有良好的缓存策略。在讲路由器设计选择之前,我先跟大家讨论一点最近储存器技术的发展,相比在座很多老师都有了解,可能少数个别人还不了解,我们快速讲一下技术的发展。我们很习惯于硬盘储存介质,已经成为我们一个固定的概念。可是最近有一个发展很快的技术,叫做高速Flash技术,是DRAM容量的32到64倍,目前最大的单片是8GB,很难再提升了。高速Flash是我们未来发展的方向。一般的Flash是DRAM的3到24倍,可以有几百到上千倍的容量提升。成本怎么样呢?我们大家看到,在现在这个时候,Flash的成本已经低于DRAM数量集。交易网站上公布的,FLash大幅度下降,每GB是62美分。我们知道Flash是在硬盘和DRAM之间的,他花的是Flash的价格,得到的是Flash容量。Flash使用寿命有限,技术上说现在Flash,按照每天20G速度写,可以使用5年,我们用网络设备淘汰率,大概也就是5年左右。我们在网络里面储存内容的时候还有一个特点,什么特点呢?大家想一想,网络路由器要储存内容,肯定储存那些流行的内容,什么意思呢,路由器储存器读写是极其不平衡,我们估计大概是写一次读100次,我写一个内容很多用户至少要访问100次才值得存下来,恰好符合于Flash的特点。市场上已经有这样的产品,Flash速率可以达到100G带宽。其他不同速率的Flash在网上都可以找到。

这种情况下,让网络路由器里面储存大量的,设计大量的储存器,从成本上我就不用担心,但是我现在担心的什么呢?我怎么去设计内容储存路由器的结构呢?方案有很多,只是跟大家讨论两种选择,第一种选择,我们叫做紧偶合专用方案。我们把储存器放在每一块线卡上,扩展内存。好处是说我把线卡扩展的储存器比较客观,不好处也是有的。不好处有哪些呢?就是这个线卡储存的内容,只从它本身的角度去看,没有站在路由器全部的角度,我要不要储存这个内容,在本显卡里面的频率是不是要储下来,储存效率不够高。另外一个储存的内容很难被大家共享,在一个线卡储存的内容被别的线卡访问的时候很难共享。在工厂也有限制,本身已经很拥挤,密度已经非常高了。一个线卡我已经没有更多的空间去装其他的部件,本来就很复杂,速度很高,性能要求很高。如果是再去加很大容量的储存器,这个显然是空间上不够。再一个不利用线卡的设计和储存器,我们觉得这种方式是不可取的方式。第二个选择就是让所有的线卡共享一个储存器池,储存器池的好处是说,从所有线卡上到达的包,如果流行的话,我就可以把它存在一个公共的储存器里面去,这个公共的储存器池里面可以为所有的线卡进行服务。用整个路由器的角度,你看访问的频率有多高,我储存的针对性比较好。不好是说我操作的复杂,所有线卡都要对储存池进行读和写,因此我处理的速度,要管理内容的读写的一致性方面,复杂性就比较高。我们认为尽管技术上复杂性比较高,我们还是喜欢这种方式,这是两种不同结构的选择,还有很多其他的方案,结构本身决定了存下内容以后,它的系统性。

我们按照这样的计算,每个Flash的芯片可以提供512G小b的容量,如果一台路由器装了10块这样的卡,就可以提供100TB的容量。价格多贵呢?刚才我讲过了,每GB是62美分,在今天去做这个100T,是花到6万美元,这个数字大家想象一下是不是可以担负的起,62美分不是太高。每块卡可以提供40到100个的速度。

最后总结一下我的两个基础点,基于名字的查找和内容在储存器上,路由器上储存,是中心网络中的两项最关键的技术,从查找角度来讲,目前可以存大于100M的前缀,成本可以做到每Gbw的查找2美分,从储存角度来讲,我们使用3DFlash的话,可以做到让路由器数百G,价格在不断下降,可以提供的带宽也在不断提升。从这两个角度讲,基于名字查找和内容,在路由器上储存下来,从技术和经济上这两个方面都是可行的,我的报告到这儿,谢谢大家!