针对无标度网络的紧凑路由方法

衡量一种路由算法优劣的两个重要指标是路由表的大小和路径的长度,但这两个方面通常是互相矛盾的.紧凑路由(compact routing)研究旨在设计路由算法在这两个指标上获得优化的平衡(tradeoff).目前,已有许多学者针对任意拓扑的网络提出了普适(universal)的紧凑路由方法(compact routing scheme).但是,真实的网络都具有特定的拓扑,普适的紧凑路由方法并没有利用真实网络呈现的特定拓扑特征,因而在这类网络上未必能取得最优的性能.最近的研究发现,许多真实网络都具有无标度特征和强聚集特征,利用这两类拓扑特征,提出了一种针对这类网络的紧凑路由方法.该路由方法将网络看成是由一个骨干树和一些捷径组成,在任意源节点和目的节点之间路由,使用路径的长度不超过它们的最短路径长度加上一个整数b.路由表大小限制在O(clog2n)比特,其中,b和c是由网络结构决定的参数.实验结果表明,在无标度网络上,b和c可以同时取较小的值.与以往的紧凑路由方法相比,该方法在平均性能上表现更好.

无标度网络上名字无关的紧凑路由研究

紧凑路由是一类可扩展路由方法,能够在使用较短路径路由的同时,大幅降低节点路由表的空间开销.为解决Internet的路由扩展问题,无标度网络上的紧凑路由最近引起了关注.然而,以往的紧凑路由方法大多是名字有关的,即必须对网络节点重新命名或编址,这对于真实网络是不太实际的.针对无标度网络提出了一种名字无关的紧凑路由方法,即不需要显式改变节点的名字,任何节点只需要知道目的节点的原始名字就可以将包送达,因此具有更好的实用性.该方法在名字有关的紧凑路由方法基础上,引入一种名字映射系统.路由过程一般分为两个阶段:先由目的节点的原始名字查询其隐藏的地址,然后根据该地址路由.为了优化路由的性能指标,选择无标度网络中度最大的部分节点作为路由用的地标,并在这些地标上均匀且分布地为所有节点建立名字到位置的映射.分析和仿真表明,该路由方法可以在无标度网络上取得很高的路由性能,与以往最优的名字无关紧凑路由方法相比,在拉伸系数和路由表大小方面都有显著提高.

紧凑路由研究

传统的最短路径路由策略通常需要在每个节点上维护到所有其他节点的路由信息,路由表大小随着网络规模的增加而快速增长,因此可扩展性不好。紧凑路由能够有效降低路由表的增长速度,允许通过路径的小幅拉伸来大幅缩减节点的路由表,从而在路径长度和路由表规模之间获得比最短路径路由更好的平衡。针对通用网络或特定拓扑类型的网络提出了许多紧凑路由策略,在尽可能缩减路由表的同时优化拉伸系数和包首部长度等路由参数。对紧凑路由的研究成果进行了综述,对提出的紧凑路由策略进行了分析和比较,并指出了紧凑路由面临的一些问题和未来的研究方向。

基于Internet AS图的紧凑路由算法研究

紧凑路由算法一直被认为是未来Internet上可扩展路由算法的有力候选者,因为它实现了近似最短路径路由机制的同时,路由表也比BGP(border gateway protocol)路由协议更加紧凑.TZ紧凑路由算法初始地标点的选取是随机生成的,没有充分利用网络拓扑信息,不是很适合真实网络.故分别提出了基于节点度和基于PageRank算法的地标节点选取机制,用于改进TZ紧凑路由算法.在2000年和2006年的Internet AS图上对两种改进算法和TZ算法进行仿真,实验结果表明,两种改进算法的平均路由表大小和平均伸长系数相比于TZ算法均有明显的改进.

基于地标节点覆盖面的TZ紧凑路由算法研究

通过地标节点选取机制,TZ紧凑路由算法很好地保证了路由系统的扩展性.但TZ紧凑路由算法并没有限制地标节点的覆盖面,也没分析覆盖面过小的地标节点是否利于信息的传递.本文研究发现覆盖面过小的地标节点不利于紧凑路由的性能,因此通过限制地标节点的覆盖面,并在地标节点选取过程中删除覆盖面过小的地标节点,改进了TZ紧凑路由算法;同时,系统地分析了地标节点的覆盖面与平均伸长系数、平均路由表的关系.在连续10年的Internet AS图上进行仿真,实验结果表明,随着地标节点最小覆盖面的增大,平均伸长系数先减小而后逐渐增加,平均路由表先减小而后保持不变;当选取一个合适的阈值时,改进的算法比原始算法有更小的平均伸长系数和平均路由表,有效提升了紧凑路由的性能.

一种紧凑的射频CMOS放大器LC输出匹配电路

提出了一种紧凑的射频互补金属氧化物半导体(Complementary Metal Oxide Semiconductor,CMOS)放大器LC输出匹配电路,利用放大器漏极偏置电感、输出端隔直电容与放大器输出端并联电感电容形成高阶LC谐振网络,可在占用较小芯片面积的条件下实现较传统L型匹配电路更宽频率范围的输出阻抗匹配。推导了该LC输出匹配电路元件值的计算式,并根据提出的设计方法,采用65 nm CMOS工艺设计了一款K频段放大器,其输出匹配电路尺寸仅98μm×150μm。仿真结果表明,在16.5~22.1 GHz频率范围内放大器的S 22<-10 dB,阻抗匹配带宽相比L型匹配电路增加166%。放大器实测S参数和仿真结果相符,验证了该LC匹配电路可实现紧凑的宽带阻抗匹配。

基于AP算法的Internet自治系统层紧凑路由研究

提出了一种基于AP算法的Internet自治系统层紧凑路由算法。用r近邻的负距离表示节点对的相似度,得到网络的相似度矩阵。基于相似度矩阵,利用AP算法对网络进行划分,得到每个聚类簇的基点。在聚类后的网络上进行紧凑路由。通过对Internet自治系统层网络拓扑数据进行大量实验,确定了AP算法中偏好参数的取值范围,并分析了该参数与路由性能中伸长系数和路由表长度的关系。实验结果表明该算法可以同时获得很小的平均伸长系数和很小的路由表长度,实现Internet自治系统层紧凑路由。

陷阱阵列:一个衡量几何路由可扩展性的通用模型

提出了一个新颖的陷阱阵列拓扑模型作为一个统一的框架来揭示一种代表性的几何路由算法的极限性能。以紧凑路由的性能为基准,本文给出了一系列新的路由性能的理论对比结果。鉴于这一种算法的利弊分析,我们尝试结合上述两类路由策略的优点,进一步设计出了一种紧凑几何路由算法(CGR)。理论分析和仿真都显示了本文提出的陷阱阵列拓扑模型和紧凑几何路由算法的优越之处。

可扩展路由协议研究

在层次化路由模式发展出现局限的现今,紧凑路由的研究已经受到了关注。针对扁平空间上的紧凑路由技术也逐步展开。现有的紧凑路由算法在完善性、动态性以及复杂性方面存在较多限制,针对典型的扁平命名紧凑路由策略在完善性和延展复杂性方面提出改进策略,并且实验验证改进策略的正确性。