Internet网络拓扑建模

ＩＳＳＮ１０００－９８２５，ＣＯＤＥＮ

ＪｏｕｒｎａｌＲＵＸＵＥＷＥ ｍａｉｌ：ｊＯＳ＠ｉｓｃａｓ．ａｃ．ｃｎｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ

Ｔｅｌ腰ａｘ：＋８６．１０．６２５６２５６３ｏｆＳｏｆｔｗａｒｅ，Ｖ０１．２０，ＮｏＩ，Ｊａｎｕａｒｙ２００９，ＰＰ．１０９—１２３ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１００１．２００９．０３３９０

＠ｂｙＩｎｓｔｉｔｕｔｅＤ，Ｓｏｆｔｗａｒｅ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｉ＂Ｓｃｉｅｎｃｅｓ．Ａｌｌｒｉｇｈｔｓｒｅｓｅｒｖｅｄ．

Ｉｎｔｅｒｎｅｔ网络拓扑建模

周苗１＋，杨家海２，刘洪波２，吴建平１

１（清华大学计算机科学与技术系，北京

２（清华大学网络研究中心，北京１０００８４）１０００８４）

ＭｏｄｅｌｉｎｇｔｈｅＣｏｍｐｌｅｘＩｎｔｅｒｎｅｔＴｏｐｏｌｏｇｙ

ＺＨＯＵＭｉａ０１＋，ＹＡＮＧＪｉａ．Ｈａ［２，ＬＩＵＨｏｎｇ．Ｂ０２，ＷＵＪｉａｎ．ＰｉｎｇＩ

１（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８４，Ｃｈｉｎａ）

２（ＮｅｔｗｏｒｋＲｅｓｅａｒｃｈＣｅｎｔｅｒ，Ｔｓｉｎｇｈ岫Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８４，Ｃｈｉｎａ）

＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇａｕｔｈｏｒ：Ｅ—ｍａｉｌ：ｚｈｏｕｍ０５＠ｍａｉｌｓ．ｔｓｉｎｇｈｕａ．ｅｄｕ．ｃｎ

ＺｈｏｕＭ，ＹａｎｇＪＨ，ＬｉｕＨＢ，ＷｕＪＰ．ＭｏｄｅｌｉｎｇｔｈｅｃｏｍｐｌｅｘＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙ．Ｊｏｕｒｎａｌ０１＂Ｓｏｆｔｗａｒｅ，２００９，２０（１）：１０９－１２３．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ／１０００—９８２５／３３９０．ｈｔｍ

Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓｔｈｅｂａｓｉｃｃｏｎｃｅｐｔｏｆｔｏｐｏｌｏｇｙ’Ｓｐｒｏｐｅｒｔｉｅｓａｎｄｍｏｄｅｌｉｎｇｍｅｔｒｉｃｓ；ｃａｔｅｇｏｒｉｚｅｓａｎｄａｎａｌｙｚｅｓｂｏｔｈＡＳ－ｌｅｖｅｌ

ｏｎｍｏｄｅｌｓａｎｄｒｏｕｔｅｒ－ｌｅｖｅｒｍｏｄｅｌｓ．Ｍｏｒｅｏｖｅｒ，ｔｈｉｓｐａｐｅｒｓｕｍｍａｒｉｚｅｓｃｕｒｒｅｎｔｒｅｓｅａｒｃｈａｃｈｉｅｖｅｍｅｎｔｓＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙ’Ｓｍｏｄｅｌｉｎｇ，ｅｓｐｅｃｉａｌｌｙａｔｔｈｅｒｏｕｔｅｒ－ｌｅｖｅｌ．Ｆｉｎａｌｌｙ，ｉｔｉｄｅｎｔｉｆｉｅｓｆｕｔｕｒｅｄｉｒｅｃｔｉｏｎｓ

ａｎｄｏｐｅｎｐｒｏｂｌｅｍｓｏｆｔｈｅ

Ｋｅｙｗｏｒｄｓ：Ｉｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｍｏｄｅｌｉｎｇｒｅｓｅａｒｃｈ．ｍｏｄｅｌｉｎｇ；ｒｏｕｔｅｒ －ｌｅｖｅｌｍｏｄｅｌｉｎｇ；ｔｏｐｏｌｏｇｙｐｒｏｐｅｒｔｉｅｓ；ｍｅｔｒｉｃｓｔｏｐｏｌｏｇｙ；ＡＳ －ｌｅｖｅｌ

摘要：首先概述Ｉｎｔｅｒａｃｔ网络拓扑建模的意义和分类；总结现阶段已发现的主要网络拓扑特性与度量指标；然后分析、讨论自治域级和路由器级的Ｉｎｔｅｒｎｅｔ网络拓扑建模与最新的研究成果；最后针对目前拓扑建模中存在的难点和问题给出总结，并展望未来的研究发展方向．

关键词：Ｉｎｔｅｍｅｔ网络拓扑；自治域级拓扑建模；路由器级拓扑建模；拓扑特性；度量指标

文献标识码：Ａ中图法分类号：ＴＰ３９３

近年来。大规模的复杂Ｉｎｔｅｒｎｅｔ网络拓扑分析研究引起了计算机及物理、数学等多个领域研究人员的兴趣【ｌ＿６１．然而，Ｉｎｔｅｒｎｅｔ网络自身具有复杂性和多变性，导致直接将其作为实验对象进行研究和分析变得十分困难．因此，人们希望根据真实网络数据和关键特征对Ｉｎｔｅｒｎｅｔ网络拓扑进行模型抽象，以拓扑模型代替真实Ｉｎｔｅｍｅｔ网络作为实验对象进行研究分析，达到通过拓扑建模认识Ｉｎｔｅｍｅｔ基本特性并指导实际网络建设的目的１１．ｚ卜１０Ｊ．

针对Ｉｎｔｅｒｎｅｔ网络拓扑建模的研究历程和未来发展方向，张宇【１１】、曾伟【１２Ｉ都曾对网络拓扑建模问题作过综述．但是，上述工作均只针对自治域级（ＡＳ（ａｕｔｏｎｏｍｏｕｓｓｙｓｔｅｍ）－ｌｅｖｅｌ）拓扑建模，极少涉及路由器级（ｒｏｕｔｅｒ－ｌｅｖｅｌ）的拓扑建模．可是，作为Ｉｎｔｅｒｎｅｔ网络拓扑建模的重要方面，人们已开始越来越关注路由器级的网络拓扑建模［１，３，１３１．相对自治域级网络拓扑结构，路由器级拓扑更大程度上受到网络服务提供商（ＩＳＰ）各自的技术水平和用户需求等相关因素的影响．并且，已有研究成果［２，１４１表明，路由器级别的Ｉｎｔｅｒｎｅｔ网络拓扑特性极有可能存在与自治域级

ＳｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔ

ＲｅｃｅｉｖｅｄＮｏ．６０４７３０８３（国家自然科学基金）２００８－０１ ０８；Ａｃｃｅｐｔｅｄ２００８－０５—０５

１１０ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．２０，Ｎｏ．１，Ｊａｎｕａｒｙ２００９Ｉｎｔｅｍｅｔ网络拓扑特性不一样的生成机理．另外，Ｌｉ等人【１３１也对路由器级拓扑的无标度性提出了质疑，并基于设计优化方法提出路由器级启发式优化模型（简称ＨＯＴ（ｈｅｕｒｉｓｔｉｃａｌｌｙ

设计原则的全局优化模型的转变．

本文将首先概要介绍Ｉｎｔｅｒｎｅｔ网络拓扑建模的意义和分类，总结现阶段已发现的主要网络拓扑特性与度量指标，然后分析、讨论自治域级和路由器级的Ｉｎｔｅｒｎｅｔ网络拓扑建模与最新的研究成果，最后将展望该领域未来的研究发展方向，并针对目前Ｉｎｔｅｒａｃｔ拓扑建模中存在的难点问题及全文主要内容进行总结．

１ｏｐｔｉｍａｌｔｏｐｏｌｏｇｉｅｓ）ｍｏｄｅｌ）与新的相关度量指标，这为路由器级拓扑建模指出了新的发展方ｔ２，１４１，即从基于随机原则的无标度网络模型（ＳＦｍｏｄｅｌ）至Ｕ基于Ｉｎｔｅｒｎｅｔ拓扑建模概述

一直以来，不同领域的研究者都对Ｉｎｔｅｒｎｅｔ网络拓扑建模进行了大量的研究工作．对网络理论研究者来说，其建模目的是根据所获得的真实网络拓扑数据进行网络模拟，从而分析预测新的路由协议等对不同层面Ｉｎｔｅｒｎｅｔ网络连通性的影响，以及拓扑变化对网络性能的影响，并最终改善网络技术、提高网络服务性能；对非网络理论研究者，尤其是对数理学领域的研究人员，其对Ｉｎｔｅｒｎｅｔ网络拓扑建模的研究出发点是探索普遍存在的规则原理．例如，数理学者希望发现小范围网络模型与大规模嘲络模型之间的必然联系，研究复杂网络领域的普遍规律【１＇４】．不同领域的研究方法和目的的差异造成Ｉｎｔｅｒｎｅｔ网络拓扑建模可能存在不同的模型生成算法和相关度量指标，在具体建模过程中，要根据研究需要进行选择；但是总体说来，无论何种领域的研究者，其建模研究的共同思路是一致的．

概括来说，可将网络拓扑建模研究分为以下３个方面：（１）在实验获得真实网络连接的基础上，获得实际网络的拓扑图，如Ｒｏｃｋｅｔｆｕｅｌ［１５１，Ｓｋｉｔｔｅｒｔｌ６，１７１等；（２）探索能够刻画实际网络拓扑特征的度量指标，包括简单度量，如节点平 …… 此处隐藏：2290字，全部文档内容请下载后查看。喜欢就下载吧 ……