Internet拓扑的社团特性分析及建模
|
摘要
自Internet拓扑的幂律特性被发现以后,Internet拓扑复杂性的研究就越来越受到人们的关注,对其宏观拓扑特性的分析与建模是当前的研究热点。近年来该领域取得了长足的发展,发现了许多隐藏的网络特征规律,但仍存在着一些研究空白点,比如,社团结构是许多真实网络都存在着的一种结构,而目前没有针对于Internet拓扑社团结构特性的研究,也没有相关的建模分析。
本文采用CAIDA (The Cooperative Association for Internet Data Analysis)提供的海量Internet拓扑数据,对Internet拓扑的社团结构特性进行了分析。首先采用模块度分裂曲线对几种简单网络模型的社团特性进行了分析,发现随机网络所具有的独特社团特性。Internet拓扑的社团结构进行了分析的显示,Internet拓扑的模块度在0.40左右,这表明Internet拓扑也是具有社团结构的网络。而当前流行的Internet拓扑模型的模块度大多小于0.30,表明了这些模型在社团特性上与真实Internet的不符合。
对Internet拓扑的社团结构成因的分析发现,处于同一个社团内的AS大多属于相同或者邻近的国家,揭示了地理因素是Internet的社团结构形成的一个重要原因。而AS类型对Internet社团结构划分的影响则比较小。对Internet国家级拓扑的社团分析显示,Internet国家级拓扑的几个主要社团正好对应到世界的几个主要大洲,进一步说明了地理因素对Internet结构的影响。
线路开销是建立网络时需要考虑到一个问题,出于降低成本的考虑,邻近地区建立Internet连接的倾向性更强。为此设计了一种基于地理演化的AS级拓扑模型——GeoPFP模型,该模型在建立节点连接时,考虑了地理距离的影响,优先在邻近节点之间建立连接。实际的实验分析表明,该模型在大多数性质上都能重现Internet,并且具有和Internet相接近的模块度,这在某种程度上也验证了本文的结论。
相对于当前的模型,GeoPFP模型具有明显的优势,可以进一步的应用于与Internet拓扑有关的研究中。比如可以用来实现更完善的Internet拓扑生成器。而其对于下一代Internet的建设和Internet路由协议的设计也有一定的参考价值及应用意义。
Since the discover of the power-law relationship in Internet topology, research on the complexity of Internet topology brought more and more people's concern, the analysis and modeling on Internet topology is a popular topic. There is great achievement in this area in recent years and many unknown topology characteristics have been revealed in recent years. However, there is still some blank in this area, for example, community structure is a common property in many real networks, but there isn't any research on the community structure of Internet topology, or related modeling method.
In this work, the community property of Internet topology is analyzed, on the basis of the mass topology data provided by CAIDA. First, a basic analysis on community property for simple network models using modularity curve shows that random network has a very strange behaviors compared with other simple network models. And the analysis on real Internet topology shows that Internet AS-level topology has a modularity around 0.40, which indicates that Internet is also a network with community structure, while at the same time, most of the popular Internet models'modularity is less than 0.30, indicating their inconsistence with the real Internet.
The analysis on the origin of community structure of Internet topology shows that most ASes in the same community belongs to the same country or adjacent countries, which means that geographical consideration is an important cause of the community structure in Internet topology. The influence of AS classes on this property is relatively weak. A further analysis on Internet country-level topology shows that the several communities correspond to the several continents in the world, which further strength our conclusion.
Connection cost is important aspect which should be considered when deploying real networks. Because of the consideration to reduce the cost, the probability to establish connections between adjacent areas is relatively large. A new model which has taken geographical location into consideration is introduced to model the evolution of Internet topology. In the new model, which is called GeoPFP model, there is more preference for new nodes to connect with nearby nodes. And the experiment show that the new model is in consistent with the real Internet in most graph properties, and has a similar modularity as Internet, which further proved our conclusion.
Compared with current Internet models, GeoPFP model has obvious advantages and can be further used in topology-related researches, such as being used to develop a more precise topology generator. Also, it is significant for the development of next-generation Internet and better routing protocols.
本文采用CAIDA (The Cooperative Association for Internet Data Analysis)提供的海量Internet拓扑数据,对Internet拓扑的社团结构特性进行了分析。首先采用模块度分裂曲线对几种简单网络模型的社团特性进行了分析,发现随机网络所具有的独特社团特性。Internet拓扑的社团结构进行了分析的显示,Internet拓扑的模块度在0.40左右,这表明Internet拓扑也是具有社团结构的网络。而当前流行的Internet拓扑模型的模块度大多小于0.30,表明了这些模型在社团特性上与真实Internet的不符合。
对Internet拓扑的社团结构成因的分析发现,处于同一个社团内的AS大多属于相同或者邻近的国家,揭示了地理因素是Internet的社团结构形成的一个重要原因。而AS类型对Internet社团结构划分的影响则比较小。对Internet国家级拓扑的社团分析显示,Internet国家级拓扑的几个主要社团正好对应到世界的几个主要大洲,进一步说明了地理因素对Internet结构的影响。
线路开销是建立网络时需要考虑到一个问题,出于降低成本的考虑,邻近地区建立Internet连接的倾向性更强。为此设计了一种基于地理演化的AS级拓扑模型——GeoPFP模型,该模型在建立节点连接时,考虑了地理距离的影响,优先在邻近节点之间建立连接。实际的实验分析表明,该模型在大多数性质上都能重现Internet,并且具有和Internet相接近的模块度,这在某种程度上也验证了本文的结论。
相对于当前的模型,GeoPFP模型具有明显的优势,可以进一步的应用于与Internet拓扑有关的研究中。比如可以用来实现更完善的Internet拓扑生成器。而其对于下一代Internet的建设和Internet路由协议的设计也有一定的参考价值及应用意义。
Since the discover of the power-law relationship in Internet topology, research on the complexity of Internet topology brought more and more people's concern, the analysis and modeling on Internet topology is a popular topic. There is great achievement in this area in recent years and many unknown topology characteristics have been revealed in recent years. However, there is still some blank in this area, for example, community structure is a common property in many real networks, but there isn't any research on the community structure of Internet topology, or related modeling method.
In this work, the community property of Internet topology is analyzed, on the basis of the mass topology data provided by CAIDA. First, a basic analysis on community property for simple network models using modularity curve shows that random network has a very strange behaviors compared with other simple network models. And the analysis on real Internet topology shows that Internet AS-level topology has a modularity around 0.40, which indicates that Internet is also a network with community structure, while at the same time, most of the popular Internet models'modularity is less than 0.30, indicating their inconsistence with the real Internet.
The analysis on the origin of community structure of Internet topology shows that most ASes in the same community belongs to the same country or adjacent countries, which means that geographical consideration is an important cause of the community structure in Internet topology. The influence of AS classes on this property is relatively weak. A further analysis on Internet country-level topology shows that the several communities correspond to the several continents in the world, which further strength our conclusion.
Connection cost is important aspect which should be considered when deploying real networks. Because of the consideration to reduce the cost, the probability to establish connections between adjacent areas is relatively large. A new model which has taken geographical location into consideration is introduced to model the evolution of Internet topology. In the new model, which is called GeoPFP model, there is more preference for new nodes to connect with nearby nodes. And the experiment show that the new model is in consistent with the real Internet in most graph properties, and has a similar modularity as Internet, which further proved our conclusion.
Compared with current Internet models, GeoPFP model has obvious advantages and can be further used in topology-related researches, such as being used to develop a more precise topology generator. Also, it is significant for the development of next-generation Internet and better routing protocols.
引文
1.汪小帆,李祥,陈关荣.复杂网络理论与应用[M].北京.清华大学出版社.2006.
2. Faloutsos M., Faloutsos P., Faloutsos C. On power-law relationships of the Internet topology[J]. ACM SIGCOMM.1999,29(4):251-262.
3. Zhou Shi,Mondragon Raul J. Accurately modeling the internet topology[J]. Physical Review E.2004,70(6):066108-8.
4. Vazquez A., Pastor-Satorras R., Vespignani A. Large-scale topological and dynamical properties of the Internet[J]. Physical Review E.2002,65(6):66130.
5. Chen Q., Chang H., Govindan R., Jamin S. The origin of power laws in Internet topologies revisited[C]. INFOCOM.2002(2):608-617.
6. Doyle J. C., Alderson D. L., Li L., Low S., Roughan M., Shalunov S., Tanaka R., Willinger W. The "robust yet fragile" nature of the Internet[J]. PNAS.2005,102(41): 14497-14502.
7. Cohen Reuven, Erez Keren, Ben-Avraham Daniel, Havlin Shlomo. Resilience of the Internet to Random Breakdowns [J]. Physical Review Letters.2000,85(21):4626.
8. Cohen Reuven, Erez Keren, Ben-Avraham Daniel, Havlin Shlomo. Breakdown of the Internet under Intentional Attack[J]. Physical Review Letters.2001,86(16):3682.
9. Eriksen Kasper Astrup, Simonsen Ingve, Maslov Sergei, Sneppen Kim. Modularity and Extreme Edges of the Internet[J]. Physical Review Letters.2003,90(14):148701-4.
10. Pastor-Satorras R., Vazquez A., Vespignani A. Dynamical and Correlation Properties of the Internet[J]. Physical Review Letters.2001,87(25):258701.
11. Alderson D.,Willinger W. A contrasting look at self-organization in the Internet and next-generation communication networks[J]. Communications Magazine, IEEE.2005, 43(7):94-100.
12. Chang H., Jamin S., Willinger W. To Peer or Not to Peer:Modeling the Evolution of the Internet's AS-Level Topology[C]. INFOCOM.2006(25):1-12.
13. Li L., Alderson D., Willinger W., Doyle J. A first-principles approach to understanding the internet's router-level topology[C]. SIGCOMM.2004:3-14.
14. Mahadevan P., Krioukov D., Fomenkov M., Dimitropoulos X., Vahdat A. The internet AS-level topology:three data sources and one definitive metric[J]. ACM SIGCOMM Computer Communication Review.2006,36(1):17-26.
15. Siganos G, Faloutsos M., Faloutsos P., Faloutsos C. Power laws and the AS-level internet topology[J]. IEEE/ACM Transactions on Networking.2003,11(4):514-524.
16. Krioukov D.,Yang K. X. Compact routing on internet-like graphs[C]. INFOCOM. 2004(1):208-219.
17. Chang H.,Willinger W. Difficulties Measuring the Internet's AS-Level Ecosystem[C]. Proceedings of CISS.2006:1479-1483. Princeton.
18. Wang X.,Loguinov D. Wealth-based evolution model for the Internet AS-level topology[C]. INFOCOM.2006:1-11.
19. Dimitropoulos X., Krioukov D., Riley G. Revisiting Internet AS-level topology discovery[J]. Proc. PAM.2005:177-188.
20. Krioukov D., Fomenkov M., Chung F., Vespignani A., Willinger W. The workshop on internet topology (wit) report[J]. ACM SIGCOMM Computer Communication Review. 2007,37(1):69-73.
21. Toward mathematically rigorous next-generation routing protocols for realistic network topologies.[EB/OL].2006. http://www.caida.org/projects/nets-nr/
22.张宇,张宏莉,方滨兴.Internet拓扑建模综述[J].软件学报.2004,15(8)：1220-1226.
23.张国强,张国清.互联网AS级拓扑的局部聚团现象研究[J].复杂系统与复杂性科学.2006,3(3)：34-41.
24. Caida. skitter[EB/OL].2006. http://www.caida.org/tools/measurement/skitter/
25. Oregon Route Views Project[EB/OL].2007. http://www.routeviews.org/
26. CAIDA skitter AS Links Topology[EB/OL].2007. http://imdc.datcat.org/collection/1-OOOW-X=CAIDA+skitter+AS+Links+Topology
27. The DIMES Project[EB/OL]. http://www.netdimes.org/
28. Internet Routing Registry[EB/OL]. http://www.irr.net/
29. Oliveira R. V., Zhang B., Zhang L. Observing the evolution of internet as topology[J]. ACM SIGCOMM.2007,37(4):313-324.
30. Zhou S., Zhang G, Zhang G, Zhuge Z. Towards a Precise and Complete Internet Topology Generator[J]. Proceedings,2006 International Conference on Communications, Circuits and Systems 2006,3:1830-1834.
31. Mahadevan P., Krioukov D., Fall K., Vahdat A. Systematic topology analysis and generation using degree correlations[J]. SIGCOMM Computer Communication Review. 2006,36(4):135-146.
32. Jin-Li Guo. The classification and analysis of dynamic networks[J]. Chinese Physics. 2007,16(5):1239-7.
33.姜誉,方滨兴,胡铭曾,何仁清.大型ISP网络拓扑多点测量及其特征分析实例[J].软件学报.2005,16(5)：846-856.
34. Waxman B. M. Routing of multipoint connections[J]. Selected Areas in Communications, IEEE Journal on.1988,6(9):1617-1622.
35. Doar M. B., Inc A. N., Acton M. A. A better model for generating test networks[C]. GLOBECOM.1996:86-93.
36. Calvert K. I., Doar M. B., Zegura E. W. Modeling Internet topology[J]. Communications Magazine, IEEE.1997,35(6):160-163.
37.张听,赵海,张文波,李超.面向Internet的CFR算法研究[J].通信学报.2006,27(009)：58-65.
38. Jin C., Chen Q., Jamin S. Inet:Internet topology generator[J]. University of Michigan Technical Report CSE-TR-433-00.2000.
39.解(亻刍),汪小帆.复杂网络中的社团结构分析算法研究综述[J].复杂系统与复杂性科学.2005,2(3)：1-12.
40. Girvan M.,Newman M. E. J. Community structure in social and biological networks[J]. PNAS.2002,99(12):7821.
41. Clauset A., Newman M. E. J., Moore C. Finding community structure in very large networks[J]. Physical Review E.2004,70(6):66111.
42. Newman M. E. J.,Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E.2004,69(2):26113.
43. W Zachary W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research.1977(33):452-473.
44. Watts Dj,Strogatz Sh. Collective dynamics of 'small-world'networks[J]. Nature.1998, 393:440-442.
45. Barabasi A. L.,Albert R. Emergence of Scaling in Random Networks[J]. Science.1999, 286:509-512.
46. Albert R.,Barabasi A. L. Topology of Evolving Networks:Local Events and Universality[J]. Physical Review Letters.2000,85(24):5234-5237.
47. Bu T.,Towsley D. On distinguishing between Internet power law topology generators[C]. Proc of INFOCOM.2002(2):12-26.
48. Uijterwaal Henk,Wilhelm Rene. ASN Missing In Action,ripe-353[EB/OL].2005. http://www.ripe.net/ripe/docs/ripe-353.html
49. Colizza V., Flammini A., Serrano M. A., Vespignani A. Detecting rich-club ordering in complex networks[J]. Nature Physics.2006,2(2):110-115.
50. Lakhina A., Byers J. W., Crovella M., Matta I. On the geographic location of Internet resources[J]. IEEE Journal on Selected Areas in Communications.2003,21(6):934-948.
51. Rozenfeld Alejandro F., Cohen Reuven, Ben-Avraham Daniel, Havlin Shlomo. Scale-Free Networks on Lattices[J]. Physical Review Letters.2002,89(21):218701.
2. Faloutsos M., Faloutsos P., Faloutsos C. On power-law relationships of the Internet topology[J]. ACM SIGCOMM.1999,29(4):251-262.
3. Zhou Shi,Mondragon Raul J. Accurately modeling the internet topology[J]. Physical Review E.2004,70(6):066108-8.
4. Vazquez A., Pastor-Satorras R., Vespignani A. Large-scale topological and dynamical properties of the Internet[J]. Physical Review E.2002,65(6):66130.
5. Chen Q., Chang H., Govindan R., Jamin S. The origin of power laws in Internet topologies revisited[C]. INFOCOM.2002(2):608-617.
6. Doyle J. C., Alderson D. L., Li L., Low S., Roughan M., Shalunov S., Tanaka R., Willinger W. The "robust yet fragile" nature of the Internet[J]. PNAS.2005,102(41): 14497-14502.
7. Cohen Reuven, Erez Keren, Ben-Avraham Daniel, Havlin Shlomo. Resilience of the Internet to Random Breakdowns [J]. Physical Review Letters.2000,85(21):4626.
8. Cohen Reuven, Erez Keren, Ben-Avraham Daniel, Havlin Shlomo. Breakdown of the Internet under Intentional Attack[J]. Physical Review Letters.2001,86(16):3682.
9. Eriksen Kasper Astrup, Simonsen Ingve, Maslov Sergei, Sneppen Kim. Modularity and Extreme Edges of the Internet[J]. Physical Review Letters.2003,90(14):148701-4.
10. Pastor-Satorras R., Vazquez A., Vespignani A. Dynamical and Correlation Properties of the Internet[J]. Physical Review Letters.2001,87(25):258701.
11. Alderson D.,Willinger W. A contrasting look at self-organization in the Internet and next-generation communication networks[J]. Communications Magazine, IEEE.2005, 43(7):94-100.
12. Chang H., Jamin S., Willinger W. To Peer or Not to Peer:Modeling the Evolution of the Internet's AS-Level Topology[C]. INFOCOM.2006(25):1-12.
13. Li L., Alderson D., Willinger W., Doyle J. A first-principles approach to understanding the internet's router-level topology[C]. SIGCOMM.2004:3-14.
14. Mahadevan P., Krioukov D., Fomenkov M., Dimitropoulos X., Vahdat A. The internet AS-level topology:three data sources and one definitive metric[J]. ACM SIGCOMM Computer Communication Review.2006,36(1):17-26.
15. Siganos G, Faloutsos M., Faloutsos P., Faloutsos C. Power laws and the AS-level internet topology[J]. IEEE/ACM Transactions on Networking.2003,11(4):514-524.
16. Krioukov D.,Yang K. X. Compact routing on internet-like graphs[C]. INFOCOM. 2004(1):208-219.
17. Chang H.,Willinger W. Difficulties Measuring the Internet's AS-Level Ecosystem[C]. Proceedings of CISS.2006:1479-1483. Princeton.
18. Wang X.,Loguinov D. Wealth-based evolution model for the Internet AS-level topology[C]. INFOCOM.2006:1-11.
19. Dimitropoulos X., Krioukov D., Riley G. Revisiting Internet AS-level topology discovery[J]. Proc. PAM.2005:177-188.
20. Krioukov D., Fomenkov M., Chung F., Vespignani A., Willinger W. The workshop on internet topology (wit) report[J]. ACM SIGCOMM Computer Communication Review. 2007,37(1):69-73.
21. Toward mathematically rigorous next-generation routing protocols for realistic network topologies.[EB/OL].2006. http://www.caida.org/projects/nets-nr/
22.张宇,张宏莉,方滨兴.Internet拓扑建模综述[J].软件学报.2004,15(8)：1220-1226.
23.张国强,张国清.互联网AS级拓扑的局部聚团现象研究[J].复杂系统与复杂性科学.2006,3(3)：34-41.
24. Caida. skitter[EB/OL].2006. http://www.caida.org/tools/measurement/skitter/
25. Oregon Route Views Project[EB/OL].2007. http://www.routeviews.org/
26. CAIDA skitter AS Links Topology[EB/OL].2007. http://imdc.datcat.org/collection/1-OOOW-X=CAIDA+skitter+AS+Links+Topology
27. The DIMES Project[EB/OL]. http://www.netdimes.org/
28. Internet Routing Registry[EB/OL]. http://www.irr.net/
29. Oliveira R. V., Zhang B., Zhang L. Observing the evolution of internet as topology[J]. ACM SIGCOMM.2007,37(4):313-324.
30. Zhou S., Zhang G, Zhang G, Zhuge Z. Towards a Precise and Complete Internet Topology Generator[J]. Proceedings,2006 International Conference on Communications, Circuits and Systems 2006,3:1830-1834.
31. Mahadevan P., Krioukov D., Fall K., Vahdat A. Systematic topology analysis and generation using degree correlations[J]. SIGCOMM Computer Communication Review. 2006,36(4):135-146.
32. Jin-Li Guo. The classification and analysis of dynamic networks[J]. Chinese Physics. 2007,16(5):1239-7.
33.姜誉,方滨兴,胡铭曾,何仁清.大型ISP网络拓扑多点测量及其特征分析实例[J].软件学报.2005,16(5)：846-856.
34. Waxman B. M. Routing of multipoint connections[J]. Selected Areas in Communications, IEEE Journal on.1988,6(9):1617-1622.
35. Doar M. B., Inc A. N., Acton M. A. A better model for generating test networks[C]. GLOBECOM.1996:86-93.
36. Calvert K. I., Doar M. B., Zegura E. W. Modeling Internet topology[J]. Communications Magazine, IEEE.1997,35(6):160-163.
37.张听,赵海,张文波,李超.面向Internet的CFR算法研究[J].通信学报.2006,27(009)：58-65.
38. Jin C., Chen Q., Jamin S. Inet:Internet topology generator[J]. University of Michigan Technical Report CSE-TR-433-00.2000.
39.解(亻刍),汪小帆.复杂网络中的社团结构分析算法研究综述[J].复杂系统与复杂性科学.2005,2(3)：1-12.
40. Girvan M.,Newman M. E. J. Community structure in social and biological networks[J]. PNAS.2002,99(12):7821.
41. Clauset A., Newman M. E. J., Moore C. Finding community structure in very large networks[J]. Physical Review E.2004,70(6):66111.
42. Newman M. E. J.,Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E.2004,69(2):26113.
43. W Zachary W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research.1977(33):452-473.
44. Watts Dj,Strogatz Sh. Collective dynamics of 'small-world'networks[J]. Nature.1998, 393:440-442.
45. Barabasi A. L.,Albert R. Emergence of Scaling in Random Networks[J]. Science.1999, 286:509-512.
46. Albert R.,Barabasi A. L. Topology of Evolving Networks:Local Events and Universality[J]. Physical Review Letters.2000,85(24):5234-5237.
47. Bu T.,Towsley D. On distinguishing between Internet power law topology generators[C]. Proc of INFOCOM.2002(2):12-26.
48. Uijterwaal Henk,Wilhelm Rene. ASN Missing In Action,ripe-353[EB/OL].2005. http://www.ripe.net/ripe/docs/ripe-353.html
49. Colizza V., Flammini A., Serrano M. A., Vespignani A. Detecting rich-club ordering in complex networks[J]. Nature Physics.2006,2(2):110-115.
50. Lakhina A., Byers J. W., Crovella M., Matta I. On the geographic location of Internet resources[J]. IEEE Journal on Selected Areas in Communications.2003,21(6):934-948.
51. Rozenfeld Alejandro F., Cohen Reuven, Ben-Avraham Daniel, Havlin Shlomo. Scale-Free Networks on Lattices[J]. Physical Review Letters.2002,89(21):218701.