1.1.2 互联网拓扑建模的研究现状

互联网作为当今人类社会信息化的标志，其规模正以指数级速度高速增长。与其原型ARPANET相比，如今的互联网已经大相径庭，由于其具有高度的复杂性，因此可以将其视为一个由计算机构成的“生态系统”。虽然人类亲手建造了这个“生态系统”，但由于它的复杂和多变性，没有人能说出它看上去到底是什么样子，运作得如何。

互联网拓扑建模研究就是探求在这个看似混乱的网络之中蕴涵着哪些还不为我们所知的规律。发现互联网拓扑的内在机制是认识互联网的必然过程，是在更高层次上开发利用互联网的基础。然而，互联网与生俱来的异构性、动态性、发展的非集中性，以及如今庞大的规模都给互联网拓扑建模带来巨大挑战。

互联网拓扑结构是互联网这个自组织系统的“骨骼”，它与流量、协议在一起，决定了互联网的本质特征。对互联网拓扑结构进行建模，既是刻画互联网在宏观上的特征，反映互联网的总体趋势的需要；也是作为一种工具，人们可用其对互联网进行分析、预报、决策或控制。因此对互联网拓扑进行研究具有重大意义。

互联网拓扑建模是一项复杂的工作，涉及网络测量、图论、算法设计、统计学、数据挖掘、可视化及数学建模等多个研究领域。正是由于其复杂性及高难度，吸引了大量专家在此领域展开研究。迄今为止，互联网拓扑研究经历了从经验假设到客观分析，从单纯的计算机网络研究到复杂系统特征化研究的过程，大体上可按时间顺序分为三代。

第一代为20世纪80年代的随机图产生器。在研究早期，由于缺乏真实测量数据支持，拓扑模型都是研究人员基于经验假设建立的。最早的互联网拓扑模型是1988年Waxman提出的Waxman模型，这是一种随机模型，沿用了很多年，直到90年代第二代互联网拓扑模型出现。

第二代为20 世纪90 年代的结构产生器，如Tiers（等级）模型与Transit-Stub模型是明显的基于层次结构设计思想的两类拓扑生成器。1996 年，Doar提出了Tiers模型，该模型刻画了互联网所具有的层次特征。1997 年，Zegura等人提出了另一种层次模型——Transit-Stub模型。此时，从1995 年开始的大规模互联网拓扑测量工作已经逐步展开，并采集到了大量拓扑数据。这些数据对科研机构都是免费开放的，这极大地推动了拓扑研究的发展。互联网拓扑研究也进入了一个成果不断累加的阶段，发现多于改进，新旧成果共同描绘了互联网拓扑图景。

第三代始于1999 年Faloutsos等人发现互联网拓扑结构中存在幂律（power-law），从而产生基于网络节点度的拓扑模型与拓扑产生器。幂律的发现将互联网拓扑与一些生物学、社会学中的复杂网络联系起来，使其成为“无尺度（scale-free）”网络的一个实例，在互联网拓扑研究与系统学研究之间架起了一座桥梁。2000 年以来，研究人员开发了许多遵循幂律的拓扑生成算法及拓扑模型，如Medina等人使用Waxman概率与线性优先结合的方法研究的BRITE模型，Winick等人根据非线性优先原则研究的Inet模型，以及AB模型、GLP模型、PFP模型、DP模型、TANG模型与MLW模型等。这些拓扑生成算法及拓扑产生器为互联网模拟提供了有利的支持。不过，新的发现也对现有成果提出了挑战。

互联网拓扑建模至今仍然是一个开放性问题，在计算机网络研究中占有重要的地位。