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

基于Internet AS图的紧凑路由算法研究 被引量：1

Study on compact routing schemes based on Internet AS-graphs
下载PDF
导出
摘要 紧凑路由算法一直被认为是未来Internet上可扩展路由算法的有力候选者,因为它实现了近似最短路径路由机制的同时,路由表也比BGP(border gateway protocol)路由协议更加紧凑.TZ紧凑路由算法初始地标点的选取是随机生成的,没有充分利用网络拓扑信息,不是很适合真实网络.故分别提出了基于节点度和基于PageRank算法的地标节点选取机制,用于改进TZ紧凑路由算法.在2000年和2006年的Internet AS图上对两种改进算法和TZ算法进行仿真,实验结果表明,两种改进算法的平均路由表大小和平均伸长系数相比于TZ算法均有明显的改进. Compact routing has been proposed as a promising candidate for scalable routing on the futurInternet because it achieves the near-shortest path routing with considerably less forwarding state that BGP. In TZ compact routing, initial landmark nodes are randomly selected, which does not make the best use of network topology and thus does not perform well in the real network. Hence, degree-based and PageRank-based methods were proposed for selecting the initial landmark nodes to improve the capability of TZ compact routing respectively. Then, the improved methods and TZ compact routing were applied on the Internet AS graph datasets of 2000 and 2006. The simulation results show that the improved methods can efficiently reduce the average size of routing tables and the average stretch respectively compared to those of TZ compact routing.
作者 范涛 刘勇 蔡世民 傅忠谦
机构地区 中国科学技术大学电子科学与技术系
出处 《中国科学技术大学学报》 CAS CSCD 北大核心 2013年第1期73-78,共6页 JUSTC
基金 国家自然科学基金(60974079 61004102) 中央高校基本科研业务费专项资金(WK2100230004)资助
关键词 紧凑路由PageRank算法 TZ算法 INTERNET AS图 compact routing TZ algorithm PageRank Internet AS graph
分类号 TP301 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献10

  • 1Page L,Brin S,Motwani R,Winograd T. The PageRank citation ranking:Bringing order to the web[R].Stanford InfoLab,1999.
  • 2Zhou S,Mondragon R J. The rich-club phenomenon in the Internet topology[J].IEEE Communications Letters,2004,(03):180-182.doi:10.1109/LCOMM.2004.823426.
  • 3Faloutsos M,Faloutsos P,Faloutsos C. On power-law relationships of the Internet topology[A].Cambridge,USA:ACM Press,1999.251-262.
  • 4Strowes S D,Mooney G,Perkins C. Compact routing on the Internet AS-graph[A].Shanghai,China:IEEE Press,2011.852-857.
  • 5Krioukov D,Fall K,Yang X W. Compact routing on internet-like graphs[A].Hong Kong,China:IEEE Press,2004.209-219.
  • 6唐明董,张国清,杨景,张国强.针对无标度网络的紧凑路由方法[J].软件学报,2010,21(7):1732-1743. 被引量：6
  • 7Thorup M,Zwick U. Compact routing schemes[A].Acm Press,2001.1-10.
  • 8Brin S,Page L. The anatomy of a large-scale HyperTextual web search engine[J].Computer Networks and ISDN Systems,1998,(1-7):107-117.
  • 9Krioukov D,Claffy K C,Fall K,at el. On compact routing for the Internet[J].ACM SIGCOMM Computer Communication Review,2007,(07):43-52.
  • 10Cowen L J. Compact routing with minimum stretch[J].Journal of Algorithms,2001,(01):170-183.

二级参考文献23

  • 1Krioukov D,Claffy KC,Fall K,Brady A.On compact routing for the Internet.ACM SIGCOMM Computer Communication Review,2007,37(7):43-52.
  • 2Santoro N,Khatib R.Labeling and implicit routing in networks.The Computer Journal,1985,28(1):5-8.[doi:10.1093/comjnl/ 28.1.5].
  • 3Leeuwen J,Tan RB.Interval routing.The Computer Journal,1987,30(4):298-307.[doi:10.1093/comjnl/30.4.298].
  • 4Cowen L.Compact routing with minimum stretch.Journal of Algorithms,2001,38(1):170-183.[doi:10.1006/jagm.2000.1134].
  • 5Thorup M,Zwick U.Compact routing schemes.In:Proc.of the 13th ACM Symp.on Parallel Algorithms and Architecture (SPAA 2001).Heraklion:ACM Press,2001.1-10.
  • 6Gavoille C,Gengler M.Space-Efficiency for routing schemes of stretch factor three.Journal of Parallel and Distributed Computing,2001,61(5):679-687.[doi:10.1006/jpdc.2000.1705].
  • 7Faloutsos M,Faloutsos P,Faloutsos C.On power-law relationships of the Internet topology.ACM SIGCOMM Computer Communications Review,1999,29(4):251-262.[doi:10.1145/316194.316229].
  • 8Dorogovtsev SN.Clustering of correlated networks.Physical Review E,2004,69(027104).[doi:10.1103/PhysRevE.69.027104].
  • 9Newman MEJ.Assortative mixing in networks.Physical Review Letter,2002,89(208701).[doi:10.1103/PhysRevLett.89.208701].
  • 10Zhou S,Mondragon RJ.Accurately modeling the Internet topology.Physical Review E,2004,70(066108).[doi:10.1103/ PhysRevE.70.066108].

共引文献5

同被引文献15

  • 1Edwards B, Hofmeyr S,Stellc (;,et al. Internettopology over time [EB/OL]. http://arxiv. org/pdf/1202. 3993vl.pdf.
  • 2Meyer 1),Zhang L, Fall K. Report from the IAB works-hop on routing and addrcssing[EB/OL]. http://tcxils.ictf. org/pdf/rfc4984. pdf.
  • 3LiT.Recommendation for a routing architecture[_EB/OL]. http: //ftp. fi. netbsd. org/rfc/rft*6115. txt. pdf.
  • 4Krioukov,FallK,Brady A. ()n compact routing forInternet [ J ]? ACM SRX'OMM ComputerCommanication Review, 2007,37(3) ; 41 -52.
  • 5Co wen L J. Compact routing with minimum stretch[J].Journal of Algorithms’ 2001,38(1): 170 -183.
  • 6Thorup M, Zwick U. Compact routing schemes[C]//Proceedings of the 13th Annual ACM Symposium onParallel Algorithms and Architectures. Crete? Greece:ACM Press, 2001: 1-10.
  • 7Faloutsos M, Faloutsos D,Faloutsos C. C)n power -lawrelationships of the internet topology [ J ]. ACMS1GCOMM Computer Communication Review, 1999,29(4): 251 -262.
  • 8Brady A,Cowen L J. Compact Routing on power lawgraphs with additive stretch [C]// Proceedings of the8th Workshop on Algorithm Engineering andExperiments. 2006: 119 -128.
  • 9Strowes S D,Mooney G,Perkins C S. Compact routingon the Internet AS -graph[C]// IEEE Conference onComputer Communications Workshops. Shanghai,China: IEEE Press, 2011: 852 -857.
  • 10KrioukovD,Fall K,Yang X W. Compact routing onInternet -like graphs [ C ]// 23rd Annual JointConference of the IEEE Computer and CommunicationsSocieties. Hongkong, China; IEEE Press,2004,1 :209 -219.

引证文献1

二级引证文献1

中国科学技术大学学报
2013年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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