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

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

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

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

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

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